Выпуклой оболочкой мн-ва наз-ся наименьшее вып-е мн-во, содержащее данное множество. Выпуклая оболочка-U-е всех выпуклых множеств, содержащих данное множество. Выпук-й оболоч-й конечного мн-ва точек будет выпуклый многогранник (n-мерный симплекс), содерж-й все эти точки, вершины кот-го совпадают с нек-ми (возможно со всеми) точками исходного мн-ва. Точки ОП м\б разделены перцептроном на классы w1 и w2, если в спрямл-м прост-ве существует раздел-я гиперплоскость, т.е. $W,
что wTyi>ρ0>0 для любого i=1..N. Теорема Новикова: пусть 1)имеется ¥ преобраз-я ОП 
, элементы кот-й относятся как к классу w1, так и w2. 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=(Z1,.., ZN). Найти вектор α*, для кот-го ∆: f(α*,Zi)>0, если Zi ?W1, для i=1..N; <0- Zi ?W2 для i=1..N. Возможна ситуация: $ одна функция Ф(α; Z1,.., ZN ) такая, что Ф(α*; Z1,.., ZN )=minпоα Ф(α; Z1,.., ZN ) ó∆. Алгоритм поиска 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=(Z1,.., ZN), элементы кот-й как из w1, так из w2. Найти вектор α*, для кот-го ∆: f(α*,Zi)>0, если Zi ?W1, для i=1..N; <0- Zi ?W2 для i=1..N. Возможна ситуация: $ N функций F(α, Zi ),i=1..N, таких что каждая из них достигает минимума в т. α*, так что F(α*, Zi )=min F(α, Zi ) для всех i=1..N тогда и только тогда, когда выполнено ∆. Предположим, что F(α, Zi ), i=1..N со св-ми: 1) они непрерывны и дифф-мы по α1,…,αk; 2) имеют каждая единственный минимум (но не обяз-но единств-ю тчк минимума). Тогда используем понятие градиента для отыскания тчк экстремума функции. Нужно определить стратегию применения алгоритмов град-го спуска к набору функций F(α, Zi ), i=1..N. Стратегия1: провести град-й спуск для F(α, Z1 ), начав с нек-й тчк α0=> получили тчк мин-ма этой функ. α1(далее эта тчк начальная)=> для F(α, Z2 ), не выходя из области наим-го зн-я F(α, Z1 )=>тчк совместного экстремума для F(α, Z1 ), F(α, Z2 ) и т.д. => αN-1(т. мин всех предыдущих функций)=> F(a,zN)=> a*-решение. Стратегия2: провести град-й спуск для F(α, Z1 ), начав с нек-й тчк α(0)=> вектор α(1)->grad F(α, Z2 ),…, α(N-1)->grad F(α, ZN )=> α(N)-> α(0)(в качестве нач тчк), если не все grad=0. Схема-стоп, когда найдена т. α*, в кот-й grad F(a*,zi)=0 для всех i=1..N. -: отыскание точки α* не гарантировано, даже если она $. Но для нек-х видов функ-и F применение этих стратегий оказывается успешным.
Алгоритм обучения перцептрона как реализация спецстратегии совместной минимизации неск-х функций с помощью градиентных методов.
Установим соответствия: Z=(Z1,…,Zn)=>y=(y1,…, yn1); α=(α1,…,αk)=>(k=n) W=(W1,…,Wn1,Wn1+1); f(α,Z)óWTy. ОП Z={z1,.., zN}=>Y= y=( y1,…, yN). Задача заключается в отыскании такого набора значений w*, для кот-го w*Tyi >0, i = 1,...,N (**). Рассмотрим функции: F(wT ,yi)=1/2(|wTyi |-wTyi)=1/2(|∑j=1n1+1Wjy2j | - ∑j=1n1+1Wjyij),i=1..N. Их св-ва: 1) F(wT ,yi )≥0; 2) min F(wT ,yi)=0 и дост-ся титт, когда (wT ,yi)>0,i=1..N, если только $ раздел-я гиперплоск-ть wTyi =0. Для каждой ф-и F(w,yi) АГС имеет вид: W(k+1)=W(k)-C1/2(sign(wT ,yi)yi -yi), т.к. gradw F(w,yi)=1/2(sign(wT ,yi)yi -yi), где sign(wT ,yi)=1, wTyi>0; -1, wTyi ≤0. Поэтому W(k+1)=W(k)-C/2(yi -yi)= W(k), если wT(k) yi>0; W(k+1)=W(k)-C/2(-yi -yi)= W(k)+cyi , если wT(k) yi ≤ 0. Таков АГС для данной ф-и F(w,yi ). Пусть для поиска совместного минимума функций F(w,yi ), i=1..N, используется стратегия, когда очередной шаг данного алгоритма исп-ся для след=й в последовательности функции, а Wk-значение вектора весов, полученное для предшествующей функции. Обозначим ч/з y(k) то значение yi, кот-е используется на шаге к+1, получим W(k+1)=W(k)+ y(k), если wT(k) y(k)≤0; иначе W(k+1)=W(k). Алгоритм-стоп, усли найден набор w*, для кот-го все ф-и F(w,yi ) принимают мин-е значение. При с=1 имеем АО перцептрона, сходимость кот-го гарантируется теоремой Новикова.