Задача нелинейного разделения двух классов

Метод максимума правдоподобия

Рассмотрим задачу разделения двух классов, с каждым из которых связано вероятностное распределение в пространстве векторов $$x$$ значений признаков. Будем обозначать плотности этих распределений $$P(x|C_i), i = 1,2, C_i$$ - событие, состоящее в том, что объект принадлежит { $$i$$ }-му классу. Нас интересует апостериорная вероятность: $$P(C_i|x)$$ — вероятность принадлежности объекта к { $$i$$ }-му классу при условии, что он характеризуется вектором признаков $$x.$$ Известная из теории вероятности формула Байеса дает

$$P(C_i|x) = P(C_i)P(x|C_i)/ \sum_{j} P(C_j)P(x|C_j)$$

где $$P(C_i)$$ — вероятность появления объектов { $$i$$ }-го класса. Для нормальных $$k$$ -мерных распределений

$$P(x|Ci) = 1/ \{(2\pi )^{k/2}({det \sum}^i)^{1/2}exp [-\frac{1}{2}(x - M^i), ( {\sum}^i)^{-1}(x - M^i)]\},$$

где $$M^i$$ — математическое ожидание $$x$$ в { $$i$$ }-м классе, { $$\sum^i$$ } — ковариационная матрица для { $$i$$ }-го класса. В результате обработки данных находят статистические оценки { $$\sum^i$$ } и $$M^i$$: пусть для { $$i$$ }-го класса имеются векторы $$x^1 \ldots x^r$$, тогда полагаем

$$M^i = ( \sum^r_{j=1} x^j)/r, ( {\sum}^i)_{pq} = \frac{1}{r} \sum^r_{j=1} (x_p^j - M_p^i) (x_q^j - M_q^i).$$

Минимизация в формуле Байеса дает простое решающее правило: $$x$$ принадлежит $$i$$ -му классу, если $$P(C_i|x) > P(C_j|x)$$ для всех $$j\neq i$$, т.е выбирается такой класс, для которого вероятность $$P(C_i|x)$$ максимальна. Поскольку в формуле Байеса для всех $$C_i$$ знаменатель общий, то решающее правило приобретает следующий вид: выбираем то $$i$$, для которого $$P(C_i)P(x|C_i)$$ максимально. Для нормального распределения удобно прологарифмировать эту величину. Окончательно получаем:

$$x$$ принадлежит $$i$$ -му классу, если среди величин

$$P_j = ln P(C_j) - (ln det {\sum}^j)/2 - [({x - M^j}), ({\sum}^j)^{-1}(x - M^j)]/2 $$

величина $$P_i$$ - максимальная. Таким образом, разделяющей является поверхность второго порядка, а операцию разделения на два класса выполняет квадратичный адаптивный сумматор в комбинации с пороговым нелинейным элементом. Пороговый элемент вычисляет ступенчатую функцию $$f(P_1 - P_2)$$, в результате для первого класса получим ответ 1, для второго - 0.

Нейрофизиологическая аналогия

Идея использования НС с квадратичными сумматорами для улучшения способности сети к обобщению базируется на хорошо известном факте индукции в естественных НС, когда возбуждение в одних областях мозга влияет на возбуждение в других. Простейшей формализацией этого является введение коэффициента, пропорционального сигналу от $$j$$ -го нейрона, в величину веса $$i$$ -го сигнала $$k$$ -го нейрона. Снабдив такое произведение весом $$q_{ij}$$ — "коэффициентом индукции", получим рассматриваемую архитектуру

$$y = f[Q(x) + L(x) + P],$$

где $$Q(x)$$ и $$L(x)$$ - соответственно квадратичная и линейная функция, $$P = const$$, $$f$$ - функция активации нейрона. Коэффициенты функций $$Q, L$$ и константа $$P$$ являются подстроечными параметрами, определяющимися в ходе обучения.

Реализация булевых функций нейронными сетями

Простой персептрон (нейрон МакКаллока-Питса) с весовым вектором $$w = ( -0.5, 1, 1)$$ реализует гиперплоскость

$$x_1 + x_2 = 0.5 $$

и булеву функцию ИЛИ от двух аргументов $$x_1$$ и $$x_2$$, каждый из которых может быть нулем или единицей. При $$w = ( - 1.5, 1, 1)$$ персептрон реализует гиперплоскость

$$x_1 + x_2 = 1.5 $$

и булеву функцию И. Однако, персептрон не может воспроизвести даже такую простую функцию как ИСКЛЮЧАЮЩЕЕ ИЛИ. Она принимает значение единицы, когда один из аргументов равен единице (но не оба) (табл.1).

Булева функция ИСКЛЮЧАЮЩЕЕ ИЛИ

$$x_1$$	$$x_2$$	$$x_1\oplus x_2$$
0	0	0
0	1	1
1	0	1
1	1	0

Эту функцию реализует двухслойная нейронная сеть, представленная на рис.1 (сигнал $$x_0=1$$ не указан). Первый слой такой сети состоит из двух нейронов, каждый из которых реализует разделяющую гиперплоскость в двумерном пространстве входных данных. Первая гиперплоскость описывается уравнением

$$x_1 + x_2 = 0.5,$$

а вторая - уравнением

$$- x_1 - x_2 = - 1.5.$$

Соответствующие векторы весов имеют вид $$w^1 = (- 0.5, 1, 1)$$ и $$w^2 = (1.5, - 1, - 1).$$ Нейрон во втором слое реализует функцию И от двух выходных сигналов нейронов первого слоя.

(рис 2) Двухслойная сеть, реализующая функцию ИСКЛЮЧАЮЩЕЕ ИЛИ(рис 1) Гиперплоскости, реализующие функцию ИСКЛЮЧАЮЩЕЕ ИЛИ

Выходным сигналом сети будет 1, если входные сигналы сети соответствуют точкам пространства входных сигналов, расположенным между вышеуказанными гиперплоскостями, т.е. точкам (0,1) и (1,0) (рис.2).

Выделение выпуклых областей

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

Выше приведен пример выделения выпуклой области двумя гиперплоскостями (реализация функции ИСКЛЮЧАЮЩЕЕ ИЛИ). Аналогично в первом слое может быть использовано 3 нейрона с дальнейшим разбиением плоскости и созданием области треугольной формы (на рис. 3, 4, $$w^1=(0,1,0), w^2=(0,0,1), w^3=(-1,-1,-1)$$, входы с нулевыми весами не указаны).

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

(рис 4) Гиперплоскости, выделяющие на плоскости выпуклую (треугольную) область(рис 3) Нейронная сеть, выделяющая на плоскости выпуклую (треугольную) область

Выделение невыпуклых областей

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

При добавлении нейронов число сторон многоугольников может неограниченно возрастать. Это позволяет аппроксимировать область любой формы с любой точностью. Вдобавок не все выходные области второго слоя должны пересекаться. Следовательно, возможно объединить различные области, выпуклые и невыпуклые, выдавая на выходе 1 всякий раз, когда входной вектор принадлежит одной из них.

На рис.5 приведен пример выделения невыпуклой области, представленной в виде объединения двух треугольных областей. Пять нейронов первого слоя реализуют разделяющие гиперплоскости, два нейрона второго слоя реализуют трехвходовые функции И, нейрон третьего слоя реализует функцию ИЛИ. Весовые векторы, описывающие соответствующие гиперплоскости, имеют вид:

$$w^1 = (0, 1, 0),\quad w^2 = (- 1, - 1, 1),\quad w^3 = ( -1, - 1, -1), \\ w^4 = ( -1, 1, - 1),\quad w^5 = (0, 0, 1).$$(рис 5) Пример выделения невыпуклой области