Алгоритм обучение перцептрона

y=(y¹, …, y^N) -векторы из спрямляющего пр-во Y принадлежащие w₁ или w₂

Задачи обучения перцептрона: на данной обуч. Посл. найти w=(w₁, …, w_k) с помощью которой данная обуч. посл. Y классифицируется безошибочно.

Алг.: на k-м шаге:

если y(k)Î w₁и w^T(k)y(k)< =0, то w(k+1)=w(k)+cy(k)

если y(k)Î w₂и w^T(k)y(k)> =0, то w(k+1)=w(k)-cy(k)

иначе w(k+1)=w(k)

c -корректирующее приращение

Останов. когда вся обуч. последовательность распознана правильно при неизменном в-ре весов.

Замечания: 1) приведенный алгоритм реализует принцип подкрепления и наказания.

2) при построении модели предполагалось, что распрямляющая плоскость проходит через 0, но реально м-т оказ-ся иначе. Это испрвляется путем ввода доп. координаты y=(y1, y2,.., yn1, 1).

3) преобразуем обуч. посл-ть Y в , где

тогда алгоритм проще: если (k)Î w₁и w^T(k) (k)< =0, то w(k+1)=w(k)+c (k) иначе w(k+1)=w(k)

Сходимость алгоритма обучения перцептрона. Теорема Новикова.

1). Есть беск. преобраз. обуч. посл., её эл-ты принадлеж. и классу w₁ и w₂.

={ , …, , …}

2). В спрям. пр-ве сущ. разделяющ. гиперплоскость, т.е. имеется единич. в-р, кот. > , для любого i.

3). D<

Тогда при началь. w(1)=0, c=1 (корректир. приращ.) алг. обуч. перцеп. сход-ся, причём кол-во исправлений в-ра весов k< =

Итеративные процедуры распознав. на основе градиентных методов: минимизация одной ф-ии.

Z=(Z1,.., Zn) – вектор признаков. Даны 2 класса: W1 и W2 (m=2). Функ-я f(α, Z)> 0, если Z? W1, < 0- Z? W2, α =(α 1, …, α k)-вектор нек-х параметров. ОП Z=(Z¹,.., Z^N). Найти вектор α *, для кот-го ∆: f(α *, Zⁱ)> 0, если Zⁱ? W1, для i=1..N; < 0- Zⁱ? W2 для i=1..N. Возможна ситуация: $ одна функция Ф(α; Z¹,.., Z^N ) такая, что Ф(α *; Z¹,.., Z^N )=minпоα Ф(α; Z¹,.., Z^N ) ó ∆. Алгоритм поиска min одной функции: α (K)-значение вектора α на к-том шаге работы алгоритма. α (K+1)= α (K)-сgrad f(α )|по α = α (K), C-величина шага grad. Зададим α (0). Его сходимость зависит от вида функции f, величины шага с. Далее решить задачу мин-и с помощью подходящей модификации метода град-го спуска, т.е. решить задачу ∆.

Итеративные процедуры распознав. на основе градиентных методов: совместная минимизация нескольких ф-ий.

N ф-ий F( , zⁱ), i=1, …, N таких что точка явл. точкой совместного минимума всех этих ф-ий, т.е. F( , zⁱ)= (1).Если имеет место такая ситуация, то необходимо определить стратегию применения алгоритма градиентного спуска к набору ф-ий F( , zⁱ).

Стратегия совместной минимизации:

Берём начальную точку ⁰, применим алгоритм гр. спуска к F( , z¹). Находим соот. точку минимума ¹. Берём ¹ в качестве начальной и применяем алг. гр. спуска к F( , z²), действуя так, чтобы не выходить за обл. экстр. предыд. ф-ии F( , z¹); получаем точку ² – совместный экстремум и т.д.

^N^-1 – точка совмест. экстремума предыдущих ф-ий. - решение всей задачи.

Другая стратегия совместной минимизации:

Берём начальную точку (0), применим алгоритм гр. спуска к F( , z¹). Получим (1). Берём (1) в качестве начальной и применяем алг. гр. спуска к F( , z²), получаем точку (2) и т.д.Если все grad=0, то это – точка совместного минимума.

Схема останавливается, когда найдётся , в кот. grad F( , zⁱ), i=1, …, N будут равны нулю, иначе – с самого начала, вместо (0) берём (N) и т.д.

Недостаток: Отыскание не гарантировано, но для нек. видов ф-ий F применение этой стратегии оказывается успешным.

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

Стратегия совместной минимизации:

Берём начальную точку (0), прим. алг. гр. спуска к F( , z¹). Получим (1).

(1) - в кач. нач. и прим. алг. гр. спуска к F( , z²), имеем точку (2) и т.д.

Если все grad=0, то это – точка совместного минимума.

Покажем, что применение этой стратегии при нек. F даёт алгоритм обучения перцептрона:

Z=(z₁, …, z_n) y=(y₁, …, y_n₁, y_n₁₊₁); w₁, w₂; =( ₁, …, _k) w=(w₁, …, w_n₁, w_n₁₊₁)

f( , z)> 0, если z w₁,

w^Ty

f( , z)< 0, если z w₂.

Выберем F(w, )=0, 5(|w^T|- w^T), i=1, …, N Cв-ва: а). F(w, )> =0

б). F(w, )> 0 w^T< =0.

Выбираем w(1) и с. w(k+1)=w(k)-c*grad F(w, )|_w₌_w₍_k₎= F(w, )=0, 5(|w^T|- -w^T)=0, 5(| |- )

=0, 5(sign(w^T) - )

F(w, )=0, 5(|w^T|- w^T), i=1, …, N (3) а). F(w, )> =0, i=1, …, N

б). F(w, )=0 w^T> 0, i=1, …, N

при усл., что в спрям. пр-ве сущ. раздел. гиперпл-ть; w_k+1=w_k-c* F(w, )

grad F(w, )= =0, 5(sign(w^T ) - ); =0, 5(sign(w^T ) - ) и т.д.

w_k-c*0, 5( - ), w^T > 0 w_k, w^T > 0

w_k+1=

w_k-c*0, 5(- - ), w^T < =0 w_k+c* , w^T < =0

Т.о. выглядит алг. гр. спуска для конкрет. ф-ии F(w, ). Пусть теперь для поиска совмест. мин. набора ф-ий (3) исп-с описанная ранее стратегия, когда очеред. шаг исп-ся для след. послед-ти ф-ий F(w, ), а w_k (зн-ие в-ра весов) – получен. для предшест. ф-ии, тогда обозначим ч/з то зн-ие , кот.будет исп-ся на данном шаге. Алг. поиска совмест. мин. – в виде:

w_k(k), w^T(k) > 0 При w(1)=0 и с=1 получаем не

w_k₊₁= что иное, как алг. обуч. перцеп.,

w_k(k)+c* , w^T(k) < =0 сход-ть которого гарантир-ся

⇐ Предыдущая 1 23