binary_ring.md

Рассмотрим множество бинарных строк $S$ с одинаковой длиной и одинаковым количеством активных клеток, различающихся инициализированным положением активных клеток. При этом все множество строк представляют собой объединение непересекающихся непустых замкнутых множеств конечного числа возможных состояний строки — колец $R_i$.

Предположим, что перцептрон способен научиться распознавать по произвольным двум строкам их принадлежность одному кольцу. Для простоты предположим существование такого отображения, ставящего во взаимно однозначное соответствие два различных состояния из одного кольца в одинаковый элемент векторного пространства, и две различные строки, принадлежащие разным кольцам — в разные элементы векторного пространства. $$ \varphi : S \rightarrow V $$ Такое отображение обладает следующими свойствами относительно колец $$ s_1 \in R \subset S, s_2 \in S $$

$$ \varphi(s_1) = \varphi(s_2) \Leftrightarrow s_2 \in R $$

$$ \varphi(s_1) \neq \varphi(s_2) \Leftrightarrow s_2 \notin R $$

Тогда утверждение заключается в том, что перцептрон способен обучиться воспроизводить отображение $ \varphi $

Рассмотрим случай двух колец, строк длины $n > 2$ с количеством активных клеток $m < n$. Тогда кольца будут состоять из $n$ элементов. Просуммируем значения сумматорной функции на входе перцептрона всевозможных строк из одного кольца. Обозначим это кольцо $R_1$ и для элементов этого кольца перцептрон возвратит положительную активацию. $$ \sum_{i=1}^{n}m \cdot w_i + n \cdot b > 0 $$

Проделаем идентичную операцию для кольца $R_0$ с отрицательной активацией перцептрона. $$ \sum_{i=1}^{n}m \cdot w_i + n \cdot b \leqslant 0 $$

Исследуя эту систему методом интервалов мы приходим к тому, что эта система не имеет решения $ \Rightarrow $ набора векторов весов не существует $ \Rightarrow $ перцептрон обучиться этому отображению не способен.

Однако для случая, когда два кольца различаются по количеству активных клеток, проделав предыдущие операции, мы получим условия на вектор весов и смещение, при котором перцептрон обучится. Действительно, для колец $R_m, m < n$ и $R_k, k \neq m, k < n$ выразим из первого неравенства смещение $b$ $$ n \cdot b > -\sum_{i=1}^{n}m \cdot w_i $$

Подставив смещение во второе уравнение мы только усилим неравенство $$ \sum_{i=1}^{n}k \cdot w_i - \sum_{i=1}^{n}m \cdot w_i \leqslant 0 $$

Преобразовав, получим достаточные условия того, что перцептрон обучен $$ (m - k) \cdot \sum_{i=1}^{n} w_i > 0 $$ $$ b > -\frac{m}{n} \cdot \sum_{i=1}^{n} w_i $$

Рассмотрим теперь вопрос о построении эффективно реализуемого отображения $ \varphi $. Сложность этой задачи заключается в выборе векторного пространства, в котором удобно сводить произвольную строку кольца в начальную форму. Начальная форма строки или инициализированное положение активных клеток будет удовлетворять свойствам отображения, а следовательно пространство начальных форм можно использовать в качестве векторного пространства. Тогда отображение $ \varphi $ будет процедурой нормализации.

Выберем удобный формат кодирования нашей строки. Пусть это будет вектор $ (u_i, v_i) $, где $u_i$ — состояние клетки, $v_i$ — количество клеток с одинаковым состоянием. Пример: $$ x = 1011001110 $$ $$ vector(x) = [(1,1), (0,1), (1,2), (0,2), (1,3), (0,1)] $$

Кодирование несколько избыточно, но нас будет интересовать процедура нормализации. Для небольших $n$ наше кольцо можно некоторым образом отсортировать и выбрать первый элемент в качестве начальной формы. Построим однозначную процедуру сортировки для таких векторов. Возьмем в качестве первого вектора тот, у которого первый символ повторяется больше всего $ max(v_i) $, если таких векторов несколько, повторим для следующего символа, пока не останется один вектор.

Для нашего примера, нормальной формой окажется вектор $$ vector(x) = [(1,3), (0,1), (1,1), (0,1), (1,2), (0,2)] $$ $$ x = 1110101100 $$

Таким образом, отображение в пространство начальных форм реализуется при помощи сортировки кольца. И это далеко не единственное решение. При этом принадлежность двух строк одному кольцу легко определяется по нормальной форме.