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

Линейное разделение классов

состоит в построении линейного решающего правила, т.е. такого вектора $$w = (w_0, \ldots, w_n)$$, где $$w_0$$ — порог, что при $$wx > 0$$ вектор $$x$$ относится к первому классу, а при $$wx \le 0$$ — ко второму.

Разделение центров масс - простейший способ построения решающего правила. Суть этого способа заключается в вычислении вектора весов персептрона по следующей формуле

$$\begin{align*} w = ( \sum_{i=1}^{n}X^i - \sum_{j=1}^{m}Y^j)/(n+m), \end{align*} $$

где $$X^i$$, $$i=1, \ldots, n$$ относятся к первому классу, а $$Y^j, j=1, \ldots, m$$ - ко второму.

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

Алгоритм обучения персептрона по отдельным примерам

1. При изначально заданных значениях весов $$w_i$$ на вход нейрона подается обучающий вектор $$x$$ и рассчитывается значение выходного сигнала $$y.$$ По результатам сравнения $$y$$ с $$d$$ уточняются значения весов.

2. Если $$y = d$$, то $$w_i, i=1, \ldots, N$$ не изменяются.

3. Если $$y = 0$$, а $$d = 1$$, то значения весов уточняются по формуле

$$\begin{align*} w_i(t+1) = w_i(t) + \alpha x_i, \alpha\in (0,1), \end{align*} $$

где $$\alpha$$ — коэффициент обучения, $$t$$ — номер предыдущего цикла.

4. Если $$y = 1$$, а $$d = 0$$, то значения весов уточняются по формуле

$$\begin{align*} w_i(t+1) = w_i(t) - \alpha x_i. \end{align*} $$

В обобщенной форме обучение персептрона на векторе $$x$$ выражается формулой

$$\begin{align*} w_i(t+1) = w_i(t) + \alpha (d - y)x_i, i=1, \ldots, N. \end{align*} $$

По завершении уточнения весовых коэффициентов представляются очередной обучающий вектор $$x$$ и связанное с ним ожидаемое значение $$d$$, и значения весов уточняются заново. Этот процесс многократно повторяется на всей обучающей выборке, пока не будут ликвидированы различия между всеми значениями $$y$$ и соответствующими им ожидаемыми значениями $$d.$$

Обучение по всему задачнику

Построим обучающую выборку

$$\begin{align*} (V^1, \ldots, V^n,V^{n+1}, \ldots, V^{n+m}) = (X^1, \ldots, X^n,- Y^1, \ldots, - Y^m). \end{align*} $$

В обучающей выборке выделяются все $$V_i, i{\in} (1,\ldots,n,{n{+}1}, \ldots, {n{+}m})$$, для которых не выполняется неравенство $$(V^i,w) > 0$$, где $$w$$ — вектор весовых коэффициентов нейрона. Обозначим это множество через Err. Вектор $$w$$ модифицируется только после проверки всей обучающей выборки:

$$\begin{align*} w = w + \alpha \sum_{V^{i}\in Err} V^{i}. \end{align*} $$

Не требуется хранить все множество Err - достаточно накапливать сумму тех $$V^i$$, на которых персептрон ошибается:

$$\begin{align*} \Delta w = w + \alpha\sum_{V^{i}\in Err}V^{i}. \end{align*} $$

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

Промежуточный вариант: обучение по страницам

Обучающее множество разбивается на подмножества (страницы) и задается последовательность прохождения страниц: столько-то циклов по первой странице, потом столько-то по второй и т. д. Коррекция вектора $$w$$ проводится после прохождения страницы. Задачник разбивается на страницы по различным эвристическим правилам, например, по правилу "от простого к сложному". Как показывает практика, чаще всего наилучшим является обучение по всему задачнику, иногда (при большом задачнике) - обучение по страницам, размеры которых определяются объемом доступной оперативной памяти.

Геометрическая интерпретация линейного разделения классов

Пусть в нейроне в качестве функции активации используется ступенчатая функция (см. формулу (1) Лекции 2). Линейное разделяющее правило делит входное пространство на две части гиперплоскостью, классифицируя входные векторы как относящиеся к 1-му классу (выходной сигнал - 1) или 2-му классу (выходной сигнал - 0). Критическое условие классификации (уравнение разделяющей гиперплоскости)

$$(w,x) = \sum_{i=0}^{N} w_i x_i = 0$$

В { $$N$$ }-мерном пространстве (пространстве входных сигналов) разделяющая гиперплоскость перпендикулярна вектору $$w' = (w_1, \ldots, w_N).$$ Вектор входных сигналов $$x'=(x_1, \ldots, x_N)$$ дает выход $$1$$, если его проекция $$x_w' = (x',w')/||w'||$$ на вектор $$w'$$ больше, чем расстояние $$-w_0/||w'||$$ от нуля до гиперплоскости. В $$N+1$$ -мерном (расширенном) пространстве гиперплоскость, описываемая уравнением $$(w,x)=0$$, ортогональна вектору $$w$$ и проходит через начало координат пространства признаков (образов).

Пример

В двухмерном пространстве входных сигналов уравнение гиперплоскости имеет вид

$$w_0 + w_{1x1} + w_{2x2} = 0.$$

При $$w_1 = w_2 = 1$$ и $$w_0 = -1.5$$ получаем уравнение $${x_1 + x_2 - 1,5 = 0}$$ гиперплоскости, которая представлена на рис.1 пунктирной линией, пересекающей оси координат в точках (1.5, 0) и (0, 1.5) соответственно. Здесь: $$w=(1,1)$$ — нормаль к разделяющей гиперплоскости; $$P$$ — вектор, относящийся к первому классу, поскольку проекция $$(w,P)$$ вектора $$P$$ на нормаль $$w$$ больше $$-w_0/||w||$$ ; $$Q$$ — вектор, относящийся ко второму классу, поскольку $$(w,Q) < - w_0/||w||.$$

(рис 1)

Настройка весового вектора

Мы требуем, чтобы вектор весов в расширенном пространстве был ортогонален решающей гиперплоскости, и плоскость проходила через начало координат. Обучающую выборку (задачник) для нейрона можно рассматривать как множество пар $$(V,d)$$, где $$V$$ - входной вектор, $$d$$ - класс (выход, принимающий одно из двух значений, например, 0 или 1), которому принадлежит $$V.$$ Такой тип обучения называется обучением с учителем, т.к. мы сообщаем сети, каким должен быть выходной сигнал для каждого вектора входных сигналов.

Пусть для некоторого $$V$$ выполняется $$d = 1$$, но выход сети

$$y=f[(V,W)] = 0,$$

где $$f(u) = 1$$ при $$u>0$$, и $$f(u) = 0$$ при $$u < 0$$, т.е. $$(V,W) < 0$$ (угол $$\varphi$$ на рис.2 между векторами $$V$$ и $$W$$ больше $$\pi /2$$ ). Чтобы исправить ситуацию, нужно повернуть вектор весов $$W$$, приближая его направление к направлению вектора $$V.$$ В то же время изменение не должно быть слишком резким, чтобы не испортить уже выполненное обучение. Мы достигнем обеих целей, если добавим к вектору $$W$$ часть вектора $$V$$, чтобы получить новый вектор

$$W' = W + \alpha V, \quad 0 < \alpha < 1.$$

Предположим теперь, что $$d = 0$$, а $$y = 1$$ (угол $$\varphi$$ на рис.2 между векторами $$V$$ и $$W$$ меньше $$\pi /2$$ ). Теперь нужно увеличить угол между $$W$$ и $$V$$, что получается путем вычитания части $$V$$ из $$W$$:

$$\begin{align*} W' = W - \alpha V. \end{align*} $$(рис 2) Настройка вектора весов

Результирующая запись имеет вид:

$$\begin{align*} W' = W + \alpha (d - y)V. \end{align*} $$

Параметр $$\alpha$$ называется скоростью обучения.

Алгоритм обучения нейрона (персептрона) будет иметь вид:

repeat
for $$\ \forall (V,d)$$ 
    begin
        y = h[(W,V)]; $$if y \neq d then W' = W + \alpha (d - y)V;$$ 
    end    
until $$(y = d\ for\ \forall (V,d))$$