5. Логические функции

Маша вчера поссорилась с Пашей. Он сказал, что у неё нет логики. Чтобы доказать Паше обратное, Маша нашла теорему, которая говорит о том, что с помощью нейросетки можно аппроксимировать почти любую функцию, и теперь собирается заняться аппроксимацией логических функций. Для начала она взяла самые простые логические функции, заданные следующими таблицами истинности

Первые два столбика идут на вход, третий получается на выходе. Первая операция — логическое «и», вторая — «или». Операция из третьей таблицы называется «исключающим или», XoR. Если внимательно приглядеться, то можно заметить, что XoR — это то же самое что и \([x_1 \ne x_2].\) Квадратные скобки обозначают индикатор. Он выдаёт \(1\), если внутри него стоит правда и \(0\), если ложь. Такая запись называется скобкой Айверсона. Попробуйте записать через неё единичную ступеньку Хевисайда, а затем помогите Маше с нейросетями.

Решение

В предыдущем упражнении мы уже построили нейрон для пересечения. Он располагался на последнем слое нейросети. Посмотрим на тот же нейрон под другим углом.

Если нарисовать все наши четыре точки на плоскости, становится ясно, что мы хотим отделить точку \((1,1)\) от всех остальных. Сделать это можно большим числом способов. Например, в нейроне выше задана линия \(x_2 = 1.5 - x_1\). Подойдёт и любая другая линия, отделяющая \((1,1)\) от остальных точек. Пропустим ради приличия точки через наш нейрон и убедимся, что он работает корректно:

\[\begin{equation*} \begin{aligned} & [-1.5 + 1 + 1 > 0] = [0.5 > 0] = 1 \\ & [-1.5 + 0 + 0 > 0] = [-1.5 > 0] = 0 \\ & [-1.5 + 0 + 1 > 0] = [-0.5 > 0] = 0 \\ & [-1.5 + 1 + 0 > 0] = [-0.5 > 0] = 0 \\ \end{aligned} \end{equation*}\]

С объединением та же ситуация, только на этот раз линия должна пройти чуть ниже. Подойдёт \(x_2 = 0.5 - x_1\).

С третьей операцией, исключающим или, начинаются проблемы. Чтобы разделить точки, нужно строить две линии. Сделать это можно многими способами. Но линий всегда будет две. Надо посмотреть первым слоем нейросетки, где мы оказались относительно каждой из линий, а вторым слоем соединить результаты.

Можно даже записать эту нейросеть через объединение и пересечение:

\[ \hat y = [1 \cdot (x_1 \cup x_2) - 1 \cdot (x_1 \cap x_2) - 0.5 > 0] \]

Нейрон \((x_1 \cup x_2)\) выясняет по какую сторону от сплошной линии мы оказались, нейрон \(x_1 \cap x_2\) делает то же самое для пунктирной линии. А дальше мы просто объединяем результат. Получается, что \(XoR\) можно описать двухслойной нейронной сетью.