Нелинейный классификатор. Многослойный персептрон

5.1. Задача исключающего ИЛИ

Рассмотрим булеву функцию $$xor(x_1,x_2)$$ как некий классификатор. Вектор признаков имеет вид $$x=(x_1,x_2)$$. В данном случае имеется четыре прецедента и два класса. Напомним таблицу значений функции $$xor(x_1,x_2)$$.

Как видно из рисунка тут нельзя построить разделяющую прямую, поскольку выпуклые оболочки точек, относящихся к первому классу и ко второму классу, пересекаются. Следовательно, и линейный классификатор построить нельзя. Попытаемся построить необходимый нелинейный классификатор как суперпозицию несколько линейных.

Рассмотрим две вспомогательные булевы функции $$or(x_1,x_2)$$ и $$and(x_1,x_2)$$. Напомним таблицы значений этих функций:

5.1.1. Построение линейного классификатора функции $$or(x_1,x_2)$$. Очевидно, что разделяющей прямой является линия:$$x_1+x_2=\frac12$$

Соответствующий персептрон имеет вид:

5.1.2. Построение линейного классификатора функции $$and(x_1,x_2)$$. Здесь также можно построить разделяющую прямую:$$x_1+x_2=\frac32$$

Соответствующий персептрон имеет вид:

5.1.3. Построение нелинейного классификатора функции $$xor(x_1,x_2)$$. Пусть на выходе персептрона для функции $$or(x_1,x_2)$$ - $$y_1$$, а на выходе персептрона для функции $$and(x_1,x_2)$$ – $$y_2$$. Посмотрим, какие значения принимает вектор $$(y_1,y_2)$$.

Обозначив классы как показано в таблице, получаем разделяющую прямую, изображенную на рисунке и соответствующий линейный классификатор:$$y_1-y_2=\frac12$$

Учитывая вышеизложенное, получаем нелинейный классификатор, который задается через два линейных классификатора, как показано на рисунке слева:$$x_1+x_2=\frac12 \text{ и } x_1+x_2=\frac32$$

Соответствующий двухслойный персептрон изображен на рисунке справа.

5.2. Классификационные способности двухслойного персептрона

Рассмотрим общий случай двухслойного персептрона. Пусть $$x\in R^l$$ и в скрытом слое $$p$$ нейронов. Скрытый слой нейронов отображает $$R^l$$ в $$H_p\in R^p$$, где $$H_p=\{(y_1,y_2,\ldots,y_p)\in R_p,\; y_i\in[0,1],\;1\leq i\leq p\}$$ – гиперкуб. Другими словами, каждый нейрон задает гиперплоскость, которая разделяет пространство пополам, т.е. скрытый слой нейронов делит пространство $$R_l$$ на полиэдры. Все вектора из каждого полиэдра отображаются в вершину $$p$$ -мерного единичного куба. Выходной нейрон разделяет вектора в классах, описанных полиэдрами, т.е. производит сечение гиперкуба, полученного в скрытом слое.

Пример. Рассмотрим нейронную сеть с двумя входами $$(l=2)$$ и тремя нейронами $$(k=3)$$. Тогда пространство $$R^l=R^2$$. Пусть первый слой нейронов задает разбиение признакового пространства (плоскости) как показано на рисунке. В каждом многоугольнике (возможно, бесконечном) все точки соответствуют одному классу (A или B). При этом в каждом многоугольнике знаки линейных функционалов $$g_1, g_2, g_3$$ остаются постоянными. Следовательно, с каждым многоугольником связано определенное значение вектора выходов нейронов первого слоя, причем для разных многоугольников эти значения различны. Поскольку значениями компонент этого вектора являются 0 либо 1, получаем, что каждому многоугольнику соответствует некоторая вершина единичного куба $$H^3$$ в пространстве $$R^3$$. При этом каждой вершине куба сопоставлен один класс A или B. На рисунке изображен единичный куб $$H^3$$, у которого закрашенные вершины относятся к классу $$A$$, а не закрашенные – к классу $$B$$. Задача нейрона второго слоя состоит в разделении вершин этого куба. Нетрудно видеть, что в нашем примере плоскость $$y_1+y_2-y_3=\frac12$$ является разделяющей для куба $$H^3$$. Она и задает параметры нейрона второго слоя. Заметим, что вершина $$(1,0,1)$$ в кубе не загружена, т.е. в нее не отображается ни один многоугольник.

5.3. Трехслойный персептрон

Внешний (выходной) нейрон реализует лишь одну гиперплоскость. Очевидно, что одна разделяющая гиперплоскость не всегда может обеспечить желаемое разделение вершин гиперкуба. Например, если два конца одной его главной диагонали относятся к классу A, а два конца другой диагонали – к классу B. С аналогичной ситуацией мы уже сталкивались в задаче исключающего или. Попробуем ввести еще один слой нейронов.

Утверждение. Трехслойная нейронная сеть позволяет описать любые разделения объединений полиэдров.

Доказательство. Рассмотрим первый слой из $$p$$ нейронов. На первом формируются гиперплоскости, т.к. строится полиэдральное разбиение пространства гиперплоскостями. Очевидно, что для заданного конечного множества прецедентов всегда можно построить разбиение пространства признаков на полиэдры такое, что ни в каком полиэдре не окажется пары точек из разных классов. Как было показано выше, первый слой отображает полиэдры в вершины $$p$$ -мерного единичного гиперкуба. Поскольку с каждым полиэдром связаны образы одного класса, то и с каждой вершиной гиперкуба связан лишь один класс.

Каждый нейрон второго слоя описывает сечение полученного гиперкуба. Выберем в качестве таких сечений гиперплоскости, отсекающие ровно одну вершину гиперкуба. Поскольку число вершин в гиперкубе равно $$2^p$$, число нейронов второго слоя также равно $$2^p$$. Таким образом, выход нейронов второго слоя имеет следующий вид. Это вектор размерности $$2^p$$, у которого всегда лишь одно значение равно 1, а остальные равны нулю. Назовем нейроны второго слоя нейронами класса A или B в соответствии с классом вершины гиперкуба, которую отсекает этот нейрон. Теперь становится понятно, каким образом строить третий слой нейронной сети. Нужно в выходном нейроне третьего слоя реализовать оператор логического сложения выходов нейронов второго слоя, относящихся к классу A. Таким образом разделяющая гиперплоскость выходного нейрона задается уравнением:$$c_1 z_1,c_2 z_2,\ldots,c_k z_k=\frac12,\text{ где }k=2^p,\text{ а }c_i= \left\{ \begin{aligned} 1\quad\text{если нейрон } i\text{ относится к классу }A \\ 0\quad\text{в противном случае} \end{aligned} \right.$$

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

Рассмотрим, как строится уравнение гиперплоскости, отсекающей вершину $$p$$ -мерного единичного гиперкуба. Диагональ куба имеет длину $$\sqrt{p}$$. Длины диагоналей $$(p-1)$$ -мерных единичных гиперкубов, являющихся боковыми гранями $$p$$ -мерного куба, равны $$\sqrt{p-1}$$. Центр куба находится в точке $$\left(\frac12,\frac12,\ldots,\frac12\right)$$. Расстояние от центра куба до любой вершины равно $$\frac{\sqrt{p}}{2}$$. Плоскость проводим перпендикулярно главной диагонали куба, инцидентной вершине, которую надо отсечь, так, чтобы расстояние от этой вершины до секущей плоскости было равно $$\frac{\sqrt{p}-\sqrt{p-1}}{2}$$, причем данная точка должна находиться на диагонали куба, проведенной к отсекаемой вершине.

Пусть $$V$$ – отделяемая вершина, $$\overline{V}$$ – диагонально противоположная вершина ( $$\overline{V}=E-V$$, где $$E$$ обозначает $$p$$ -мерный вектор, состоящий из единиц). Следовательно, $$W=V-\overline{V}$$ – направляющий вектор разделяющей гиперплоскости. Тогда гиперплоскость проходит через точку:$$U=\overline{V}+(V-\overline{V})\cdot\frac{\sqrt{p}-\sqrt{p-1}}{2\sqrt{p}}$$ Обозначим:$$\gamma=\frac{\sqrt{p}-\sqrt{p-1}}{2\sqrt{p}}=\frac12\cdot\left(1+\sqrt{1-\frac1p}\right)$$ Тогда$$U=\overline{V}+(V-\overline{V})\cdot\gamma$$ и уравнение гиперплоскости запишется в виде: $$((z-U),W)>0$$.

5.4. Построение нейронной сети

Существует два подхода к задаче построения нейронной сети-классификатора. Первый подход заключается в построении сети, варьируя архитектуру. Данный метод основан на точной классификации прецедентов. Второй подход состоит в подборке параметров (весов и порогов) для сети с заданной архитектурой.

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

Рассмотрим более подробно алгоритм. Начинаем с одного нейрона $$n(X)$$, называемого мастером. После его тренировки получаем разделение множества $$X$$ на $$X^+$$ и $$X^-$$. Если $$X^+$$ содержит вектора из двух классов, то вводим новый узел $$n(X^+)$$, называемый последователем.

Таким образом, на первом слое нейронов находится один мастер и несколько последователей. Никакие вектора из разных классов не имеют одинакового выхода из первого слоя.$$X_1=\{y:y=f_1(x),x\in X\},$$ где $$f_1$$ – отображение, задаваемое первым слоем.

Аналогичным образом строим второй слой, третий слой и т.д.

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

Таким образом, получаем архитектуру, имеющую конечное число слоев, правильно классифицирующие все прецеденты.

Нейроны первого слоя – это биссекторы, разделяющие пары. Второй слой – нейроны $$and$$, определяющие полиэдры. Третий слой – нейроны $$or$$, определяющие классы.

Основным недостатком данного метода является слишком большое количество нейронов.

5.4.2. Алгоритм, основанный на подборе весов для сети с заданной архитектурой. Идея данного метода состоит в том, чтобы ввести критерий в виде функции стоимости, которую необходимо минимизировать.

Пусть

Текущем состоянии сеть при обучении дает результат $$\widehat{y}(i)$$ не совпадающий с $$y(i)$$. Обозначим:$$J=\sum_{i=1}^N\varepsilon(i)$$ где $$N$$ – число прецедентов; $$\varepsilon(i)$$ – ошибка на $$i$$ -ом прецеденте;$$\varepsilon(i)=\frac12\sum_{m=1}^{k_L}e_m^2(i)=\frac12\sum_{m=1}^{k_L}(y_m(i)-\widehat{y}_m(i))^2,$$ где $$i=1,2,\ldots,N$$. $$J$$ – функция всех синоптических весов и порогов. Таким образом, целью обучения является решение оптимизационной задачи:$$J(W)\rightarrow\min,$$ где $$W$$ – множество синоптических весов.

Пусть $$y_k^{r-1}$$ – выход $$k$$ -ого нейрона $$(r-1)$$ -ого слоя; $$W-j^r$$ – весовой вектор (включая порог) $$j$$ -ого нейрона в $$r$$ -ом слое, т.е. $$W-j^r=(W_{j0}^r,W_{j1}^r,\ldots,W_{jk_{r-1}}^r)$$, где $$k_{r-1}$$ а – число нейронов в $$(r-1)$$ -ом слое. Таким образом, $$J$$ – разрывная функция $$M$$ переменных, где$$M=\sum_{r=1}^L k_{r-1}k_r$$ $$J$$ разрывна, т.к. разрывна функция активации $$f$$:$$f(x)= \left\{ \begin{aligned} 1, x>0\\ 0, x<0 \end{aligned} \right.$$