|
Y |
^N ^ |
<; |
Qo |
|
|
|
d(x) = W |
X = ^ WjXj |
0 ^ X I |
|
|
|
|
|
г= о |
X |
Qi |
|
|
|
|
|
|
|
||
где |
W ={wo,wi,...,wjp_i,wjpf |
пополненный |
вектор |
весовых |
||
коэффициентов. |
|
|
|
|
|
|
Пусть - обучающая выборка объемом К. Обозначим х{к) -
элемент выборки, используемый на к-м шаге алгоритма настройки, W (к) -
оценка искомого вектора W на к-м шаге алгоритма.
Классический алгоритм обучения перцептрона, предложенный Розенблатом в [7], выглядит следующим образом:
W(k), |
x(k)eQiHJV^(k)x(k)>0 или x(k)e QQnJV^ (k)x(k) <0, |
|
W{k + \) = W{k) + cx{k), |
х{к)&О.1-а¥^{к)х{к)<0, |
|
W{k)-cx{k\ |
х(к)еОди1¥^(к)х(к)>0. |
|
Выбор параметра с в алгоритме обучения перцептрона производится в соответствии с одним из нижеследующих правил.
Правило 1. Правило фиксированного приращения Выбирается произвольное постоянное значение с>0.
Правило 2. Правило полной коррекпии Значение параметра с выбирается таким, чтобы текущий вектор
признаков был проклассифицирован верно. А именно:
W^(k)x{k)
с>
вэтом случае параметр с является переменным: с = с{к).
Правило 3. Градиентное правило коррекпии Данное правило используется, если качество линейной дискриминантной
функции определяется некоторым функционалом J(W ) , минимизацию или
максимизацию которого необходимо произвести в процессе настройки классификатора. Экстремум функционала может быть найден, если двигаться вдоль градиента функции качества, то есть использовать градиентное правило коррекции коэффициентов:
45
И ^ + 1 ) = г ( 4 ) - р ^ ^
w = w { k )
где р > О - параметр градиентного алгоритма. Нагфимер, при минимизации СКО, когда
j ( ic ) = i( Y ( x ) - ic A 0
алгоритм обучения выглядит следующим образом:
W{k +l)=w{k)+ рх(4)(у(х(4)) - |
{k)x{Y) ■ |
Вэтом случае параметр с, очевидно, равен:
с= -р(у(х(4))- 1C ^ Е)х(4))
итакже, как и в предшествующем случае, зависит от к. с = с{к).
Примечание Алгоритм обучения перцептрона сходится за конечное число итераций
(то есть строится классификатор, безошибочно классифицирующий все элементы выборочных данных), если классы являются линейно разделимьши (рис.3.4). В противном случае алгоритм обучения зацикливается.
3.1.6 Последовательная корректировка линейного классификатора: стохастическая аппроксимация и процедура Роббинса-Монро
Алгоритм обучения перцептрона не сходится, если классы, заданные обучающими выборками, не являются линейно разделимыми. Этот факт вьщвигает задачу построения алгоритма оценивания вектора коэффициентов
линейной разделяющей функции W , сходимость которого была бы гарантирована всегда. Такой алгоритм может быть построен с помощью метода стохастической аппроксимации.
Идея метода состоит в том, что критерий T (I T ) рассматривают как
функцию регрессии вида |
= |
), |
где |
- значение |
функционала качества, наблюдаемого |
в точке |
X . Метод |
стохастической |
|
аппроксимации позволяет определять по результатам наблюдений корень следующего уравнения:
46
M ^ F ( k X X ) =Mh{ W, X) = 0, dw
которое яазываетсяуравнением регрессии.
Рис.3.4 Итюстрация линейной разделимости классов:
а - линейно разделимые классы; б - линейно неразделимые классы
47
Процедура Роббинса-Монро - это итеративная процедура поиска корня уравнения регрессии. Обозначим lP(l) произвольную начальную оценку
корня W и w{k) - оценку этого корня, полученного на к-м шаге итерации.
Тогда решение уравнения регрессии может быть получено в результате следующего итерационного процесса:
W{k +\)=W {k)-a,kh{W {k\X{k)), (3.21)
где щ - элемент последовательности положительных чисел, удовлетворяющий следующим условиям:
|
со |
СО |
|
И ш а^,= 0, |
V a^, = oo, |
V a ? < o o . |
(3.22) |
|
к= \ |
к = \ |
|
Утверждение [12]: Если |
последовательность |
удовлетворяет |
|
условиям (3.22) и выполнены некоторые дополнительные условия, то оценка
(3.21) сходится к корню W в среднеквадратическом и с вероятностью
равной единице, то есть |
|
\ i m M L { k ) - W ] = ^, |
\ i m P ^ { k ) = w ) = \ . |
Примером последовательности, удовлетворяющей условиям (3.22), |
|
является последовательность |
вида |
3.1.7 Общая схема построения линейных классификаторов, основанная на методе стохастической аппроксимации
|
Зададимся критерием J{W) вида |
|
|
j ( w ) = |
X - y(X)) , |
где |
некоторая выпуклая |
функция (например, модуль), у(Х)- |
требуемый выход разделяющей функции. Дифференцируя по IV , имеем
48
щ ю |
dF |
W ^ X - Y ( X ) |
=М - |
■= 0 . |
|
dW |
|
dW |
Полученное уравнение является уравнением регрессии. Воспользовавшись теперь процедурой Роббинса-Монро, можно получить последовательность оценок вектора коэффициентов линейного классификатора, положив
dF W ^ X - YY )
h Y ^{k\x{k%
dW
W=W(k),X=X{k)
и записав алгоритм в виде
dF W ^ X - Y И
Ик(к+1)=Ик(к)-щ-
dW
w = w ( k ) ( x = x ( k )
где начальный вектор IV(l) выбирается произвольно, а последовательность
Y-kX=\ удовлетворяет условиям (3.22). Рассмотрим два из возможных
алгоритмов, основанных на методе стохастической аппроксимации.
Ал г о р и т м корректирующих приращений (АКП-алгоритм)
ВАКП-алгоритме критерий качества классификатора задается в виде
J{W) =M r ( X ) - W ' ^ X
где
L X e Q
г(Х) =
-l,X e Q ,■О
-случайная переменная правильной классификации. Поскольку производная критерия
dJ[W
f l = - M X sgn(r(X) - W x ) , dW
49