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

Выпуклой оболочкой мн-ва наз-ся наименьшее вып-е мн-во, содержащее данное множество. Выпуклая оболочка-U-е всех выпуклых множеств, содержащих данное множество. Выпук-й оболоч-й конечного мн-ва точек будет выпуклый многогранник (n-мерный симплекс), содерж-й все эти точки, вершины кот-го совпадают с нек-ми (возможно со всеми) точками исходного мн-ва. Точки ОП м\б разделены перцептроном на классы w1 и w2, если в спрямл-м прост-ве существует раздел-я гиперплоскость, т.е. $W,

что wTy i> ρ 0> 0 для любого i=1..N. Теорема Новикова: пусть 1)имеется ¥ преобраз-я ОП , элементы кот-й относятся как к классу w₁, так и w₂. 2)в СП Y $ разд-я гиперплоскость, т.е. $ такой един-й век-р |w*|=1, что . 3) величина D< ¥ (конечна). Тогда при нач. в-ре w(1)=0 и корр. прир. С=1 алгоритм обучения перцептрона сходится, причем число исправлений вектора весов

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

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, величины шага с. Далее решить задачу мин-и с помощью подходящей модификации метода град-го спуска, т.е. решить задачу ∆.

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

Пусть изображение хар-ся вектором признаков Z=(Z1,.., Zn). Рассмотрим случай 2-х классов W1 и W2 (m=2). Предположим, что $ функ-я f(α, Z)> 0, если Z? W1, < 0- Z? W2, где α =(α 1, …, α k)-вектор нек-х параметров. ОП Z=(Z¹,.., Z^N), элементы кот-й как из w1, так из w2. Найти вектор α *, для кот-го ∆: f(α *, Zⁱ)> 0, если Zⁱ? W1, для i=1..N; < 0- Zⁱ? W2 для i=1..N. Возможна ситуация: $ N функций F(α, Zⁱ ), i=1..N, таких что каждая из них достигает минимума в т. α *, так что F(α *, Zⁱ )=min F(α, Zⁱ ) для всех i=1..N тогда и только тогда, когда выполнено ∆. Предположим, что F(α, Zⁱ ), i=1..N со св-ми: 1) они непрерывны и дифф-мы по α 1, …, α k; 2) имеют каждая единственный минимум (но не обяз-но единств-ю тчк минимума). Тогда используем понятие градиента для отыскания тчк экстремума функции. Нужно определить стратегию применения алгоритмов град-го спуска к набору функций F(α, Zⁱ ), i=1..N. Стратегия1: провести град-й спуск для F(α, Z¹ ), начав с нек-й тчк α 0=> получили тчк мин-ма этой функ. α 1(далее эта тчк начальная)=> для F(α, Z² ), не выходя из области наим-го зн-я F(α, Z¹ )=> тчк совместного экстремума для F(α, Z¹ ), F(α, Z² ) и т.д. => α N-1(т. мин всех предыдущих функций)=> F(a, z^N)=> a*-решение. Стратегия2: провести град-й спуск для F(α, Z¹ ), начав с нек-й тчк α (0)=> вектор α (1)-> grad F(α, Z² ), …, α (N-1)-> grad F(α, Z^N )=> α (N)-> α (0)(в качестве нач тчк), если не все grad=0. Схема-стоп, когда найдена т. α *, в кот-й grad F(a*, zⁱ)=0 для всех i=1..N. -: отыскание точки α * не гарантировано, даже если она $. Но для нек-х видов функ-и F применение этих стратегий оказывается успешным.

 

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

Установим соответствия: Z=(Z1, …, Zn)=> y =(y _{1, …,} y _n1); α =(α 1, …, α k)=> (k=n) W=(W1, …, Wn1, Wn1+1); f(α, Z)ó W^Ty. ОП Z={z¹,.., z^N}=> Y = y =( y ¹_{, …,} y ^N ). Задача заключается в отыскании такого набора значений w*, для кот-го w*^T y ⁱ > 0, i = 1,..., N (**). Рассмотрим функции: F( w^T, y ⁱ)=1/2(| w^T y ⁱ |- w^T y ⁱ)=1/2(|∑ _j=1ⁿ¹⁺¹Wjy ²_j | - ∑ _j=1ⁿ¹⁺¹Wjy ⁱ_j), i=1..N. Их св-ва: 1) F( w^T, y ⁱ )≥ 0; 2) min F( w^T, y ⁱ)=0 и дост-ся титт, когда ( w^T, y ⁱ)> 0, i=1..N, если только $ раздел-я гиперплоск-ть w^T y ⁱ =0. Для каждой ф-и F(w, y ⁱ) АГС имеет вид: W(k+1)=W(k)-C1/2(sign( w^T, y ⁱ)y ⁱ -y ⁱ), т.к. grad_w F(w, y ⁱ)=1/2(sign( w^T, y ⁱ)y ⁱ -y ⁱ), где sign( w^T, y ⁱ)=1, w^T y ⁱ> 0; -1, w^T y ⁱ ≤ 0. Поэтому W(k+1)=W(k)-C/2(y ⁱ -y ⁱ)= W(k), если w^T(k) y ⁱ> 0; W(k+1)=W(k)-C/2(-y ⁱ -y ⁱ)= W(k)+cy ⁱ, если w^T(k) y ⁱ ≤ 0. Таков АГС для данной ф-и F( w, y ⁱ ). Пусть для поиска совместного минимума функций F( w, y ⁱ ), i=1..N, используется стратегия, когда очередной шаг данного алгоритма исп-ся для след=й в последовательности функции, а Wk-значение вектора весов, полученное для предшествующей функции. Обозначим ч/з y (k) то значение y ⁱ, кот-е используется на шаге к+1, получим W(k+1)=W(k)+ y (k), если w^T(k) y (k)≤ 0; иначе W(k+1)=W(k). Алгоритм-стоп, усли найден набор w*, для кот-го все ф-и F( w, y ⁱ ) принимают мин-е значение. При с=1 имеем АО перцептрона, сходимость кот-го гарантируется теоремой Новикова.

 

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Популярное:

1. TRAINING PROGRAM ПРОГРАММАОБУЧЕНИЯ
2. Активные методы обучения (деловые игры, научные проекты)
3. Активные формы организации обучения. Урок-лекция.
4. Анализ техники и методика обучения движению ног способов плавания кроль на груди, кроль на спине.
5. Аудиолингвальный и аудиовизуальный методы обучения иностранным языкам и их критический анализ.
6. Блок-схема алгоритма решения задачи
7. Вид управления оптимального по быстродействию, теорема об n-интервалах.
8. Глава 1. Основные принципы восстановительного обучения
9. Глава 1. Основные принципы коррекционного обучения
10. Глава 3. Техника и методика обучения основным легкоатлетическим упражнениям
11. Глава 6. Основы методики обучения и тренировки
12. Глава двадцатая. Пятый курс - конец учебы, но не конец обучения.