Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 31
Текст из файла (страница 31)
В дальнейшем еще придется вернуться ко всем этим вопросам. Гл. Б. Линейные рануеллаялне фрллдлл и при этом основной алгоритм (8) приводится к следующему виду: а„е,=ада ра ~~.', у, (13) ус о'е где ба есть множество выборок, классифицируемых с ошибкой посредством аа. Таким образом, процедуру спуска для нахождения вектора решения можно определить очень просто: следующий ве- а | Ряс. 5.8.
Персептронная функция критерия. а — весовое пространство, б — функция критерия. Рис. 6.9. Определение области решения методом градиентного анализа, совой вектор получается путем прибавления к данному весовому вектору некоторого кратного суммы выборок, классифицируемых с ошибкой. На рис. 5.9 приведен пример определения вектора решения с помощью указанного алгоритма для простого двумерного случая при значениях аз =0 и рл —— 1.
Покажем теперь, что данный алгоритм будет давать решение для любой задачи с линейно разделяемым множеством. 5Д. Мин»ми»»чик персе»тронной фиккции кркккрик 159 5.5.2. ДОКАЗАТЕЛЬСТВО СХОЛИМОСТИ ДЛЯ СЛУЧАЯ КОРРЕКЦИИ ПО ОЙНОЙ ВЫБОРКЕ Исследование сходимости алгоритма спуска удобно начать с варианта, более легкого для анализа. Вместо определения а» по всем выборкам и осуществления коррекции по множеству классифицируемых с ошибкой выборок б1» выборки будут рассматриваться последовательно, и весовой вектор будет изменяться всякий раз, когда некоторая выборка будет классифицироваться с ошибкой. Для доказательства сходимостн подробная характеристика данной последовательности неважна, коль скоро каждая выборка появляется в последовательности бесконечно большое число раз.
Наиболее просто убедиться в атом, повторяя выборки циклически. Два последующих упрощения помогут лучшему пониманию излагаемого материала. Во-первых, временно ограничимся случаем, когда р» является константой. Это так называемый случай с постоянным приращением. Из соотношения (13) следует, что если р„— величина постоянная, то она служит лишь для масштабирования выборок. Таким образом, в случае с постоянным приращением можно, без ущерба для общности, положить р» — — 1.
Второе упрощение состоит лишь в введении обозначений. Когда выборки рассматриваются последовательно, некоторые из ннх классифицируются с ошибкой. Поскольку весовой вектор изменяют лишь прн наличии ошибки, внимание фактически сосредоточивается только на выборках, классифицируемых с ошибкой. Таким образом, последовательность выборок обозначается через у', у'... У»,..., где каждый у" является одной из и выборок у„..., у„и каждая выборка у» классифицируется с ошибкой.
Например, при циклическом повторении выборок у„у, и у„если отмеченные выборки Уз~ Узз Узз Ум Уз Узз Уз Узз классифицируются с ошибкой, то последовательность у', у', у', у', у',... обозначает последовательность у„у„у„у„у„... Исходя из данного объяснения, для образования гюследовательности весовых векторов может быть записано правило постоянного приращения: аз пРоизвольно, 1 (14) а»,, — — а„+ у», к Ъ 1, где а»зу»(0 для всех й. Правило постоянного приращения является простейшим из чнс. ла многих алгоритмов, которые предлагались для решения систем линейных неравенств.
Впервые оно появилось при введении схемы обучения с подкреплением, предложенной Ф. Розенблаттом для его персептронной модели мозга и доказательства сходимостн послед- ней, известного под названием теоремьз сходимости персептрона, Ге. о. Линейные разде»навине фрннчни 160 В частности, можно дать ее геометрическую интерпретацию в весовом пространстве.
Поскольку вектор а„классифицирует у» с ошибкой, то а» не будет находиться с положительной стороны у», принадлежащего гиперплоскости а'у»=0. Прибавление у» к вектору а» смещает весовой вектор непосредственно в направлении к данной гиперплоскости при возможности ее пересечения (рнс. 5.10). Независимо от того, пересечется ли гиперплоскость или нет, новое скалярное произведение а»„у' будет больше прежнего произведения (г Рис. 0.10. Шаг, соответствующий правилу постояииото приращения. щу» на величину йу»йв, в результате получаем, что вследствие коррекции весовой вектор смещается в нужном направлении.
Покажем теперь, что, если выборки линейно разделяемы, последовательность весовых векторов будет ограничиваться вектором решения. При доказательстве необходимо отметить, что каждая процедура коррекции сдвигает весовой вектор ближе к области решения. То есть следует показать, что если а является любым вектором решения, то значение )~ໄ— а11 меньше значения йа»вЂ” — ай. Хотя в общем случае данное утверждение оказывается несправедливым, будет показано, что оно выполняется для векторов решения, имеющих достаточную длину. Пусть а — вектор решения, так что величина а'у, строго положительна для всех 1, а а — положительный скалярный коэффициент, Из соотношения (14) следует, что (а„„вЂ” аа) = (а„— аа) + у»; тогда !! а». — а!1* = !! ໠— а 1). + 2 (໠— а)ту" + Ь»!!'.
Б,Ю. Мииимиэация лереелтреллоа 4рлкиии критерия 161 Пеащгояьку у» классифицировался с ошибкой, то аеу"(О, и, таким образом, можно записать следующее выражение: ~~ аа+,— аа 11е (й аа — аа((е — 2аасуе-1- ~! у" ~!е. )1(к как величина а'у' строго положительна, второй член будет пб модулю превосходить третий при условии, что значение са достаточно велико. В частности, если положить ре = шах )~ ус (!е (15) с и у =ш(па'у, > О, (16) с то !~нее,— аа)!е()!а — сса ((е — 2ау+ре, и если выбрать ,„Р У' (17) то получим следующее выражение: (~ а„+ „— аа йе ( ~! ае — сса 11е — () е. Таким образом, квадрат расстояния от а» до ееа прн каждой коррек.
ции будет уменьшаться„по крайней мере на величину ре, и после й коррекций представится в следующем виде: й аа,, — аа (~' ( !) а, — аа )~е — кре. Поскольку величина квадрата расстояния не может быть отрицательной, из этого следует, что последовательность коррекций должна быть ограничена числом коррекций, ие большим чем л„ где 11 ас — аа 11е (18) е ре Поскольку коррекция осуществляется всякий раз, когда выборка классифицируется с ошибкой, и поскольку каждая выборка появляется бесконечно большое число раз в последовательности, отсюда следует, что после прекращения процесса коррекций полученный весовой вектор должен правильно осуществлять классификацию всех выборок.
Число й, определяет предельное значение числа коррекций. Если а,=О, получается следующее достаточно простое выражение для ке: лсак1!у ~)е))а11е ае11ас~е рейаие С" с Гм й. Линейные риедееннияие функции 162 Данное выражение показывает, что трудность задачи в основном определяется наличием выборок, наиболее близких к ортогональным по отношению к вектору решения.
К сожалению, указанное выражение невозможно использовать при рассмотрении нерешенной задачи, поскольку в данном случае граница должна определяться исходя из неизвестного вектора решения. Очевидно, что в общем случае задачи с линейно разделяемыми множествами могут представлять известные трудности для определения решения в условиях компланарности выборок. Тем ие менее, если выборки линейно разделяемы, правило постоянного приращения будет давать решение после конечного числа коррекций. 5.5.3, НЕКОТОРЫЕ НЕПОСРЕДСТВЕННЫЕ ОБОБЩЕНИЯ Правило постоянного приращения можно обобщить с целью выделения связанных между собой алгоритмов. Коротко будут рассмотрены два наиболее интересных варианта. В первом варианте вводится понятие переменного приращения р„и допуск Ь и предусматривается коррекция, когда величина а(у» является недостаточной для превышения допуска. Алгоритм задается в следующем виде: произвольно, й)1, а„ а»„= а„+ р»у", (20) р»~О, 1пп ~ р»=ии ы-~и» $ (21) (22) а» сходится к вектору решения а, удовлетворяющему условию а'уе)Ь при всех значениях Е В частности, условия, налагаемые на р,, выполняются в том случае, если р» является положительной константой или убывает как !!й.
Следующим вариантом, представляющим интерес, является первоначально рассмотренный алгоритм градиентного спуска для 1„: а, произвольно, 1 ໄ— — а„+р» ~ у, ~ у»Э» (24) где теперь а»у»(Ь для всех й. Можно показать, что, если вы- борки линейно разделяемы и если Б.а, Минимизация неаееияеианнаа фяннции нритеяия гвз где гзя — множество выборок, классифицируемых с ошибкой посредством ая. Легко видеть, что данный алгоритм будет также давать решение, принимая во внимание, мто если а является вектором решения для последовательности у„..., у„, то он правильно классифицирует корректирующий вектор у'= Х у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
