5.5.2. ДОКАЗАТЕЛЬСТВО СХОДИМОСТИ ДЛЯ СЛУЧАЯ КОРРЕКЦИИ ПО ОДНОЙ ВЫБОРКЕ

Исследование сходимости алгоритма спуска удобно начать с варианта, более легкого для анализа. Вместо определения по всш выборкам и осуществления коррекции по множеству классифицируемых с ошибкой выборок S/fe выборки будут рассматриваться последовательно, и весовой вектор будет изменяться всякий раз, когда некоторая выборка будет классифицироваться с ошибкой. Для доказательства сходимости подробная характеристика данной последовательности неважна, коль скоро каждая выборка появляется в последовательности бесконечно большое число раз. Наиболее просто убедиться в этом, повторяя выборки циклически.

Два последующих упрощения помогут лучшему пониманию излагаемого материала. Во-первых, временно ограничимся случаем, когда pfe является константой. Это так называемый случай с постоянным приращением. Из соотношения (13) следует, что если р^ — величина постоянная, то она служит лишь для масштабирования выборок. Таким образом, в случае с постоянным приращением можно, без ущерба для общности, положить Ph==l. Второе упрощение состоит лишь в введении обозначений. Когда выборки рассматриваются последовательно, некоторые из них классифицируются с ошибкой. Поскольку весовой вектор изменяют лишь при наличии ошибки, внимание фактически сосредоточивается только на выборках, классифицируемых с ошибкой. Таким образом, последовательность выборок обозначается через у\ y^ . . . , у*, . . . , где каждый у* является одной из п выборок уі, . • . , Уп и каждая выборка у* классифицируется с ошибкой. Например, при циклическом повторении выборок уі, уа и уа, если отмеченные выборки

классифицируются с ошибкой, то последовательность у\ у^, у®, у^, у®, . . . обозначает последовательность уі, уз, уі, уа, уа, . . . . Исходя из данного объяснения, для образования последовательности весовых векторов может быть записано правило постоянного приращения:

где а1у*<0 для всех k.

Правило постоянного приращения является простейшим из числа многих алгоритмов, которые предлагались для решения систем линейных неравенств. Впервые оно появилось при введении схемы обучения с подкреплением, предложенной Ф. Розенблаттом для его персептронной модели мозга и доказательства сходимости последней, известного под названием теоремы сходимости персептрона.

в частности, можно дать ее геометрическую интерпретацию в весовом пространстве. Поскольку вектор классифицирует у* с ошибкой, то не будет находиться с положительной стороны у*, принадлежащего гиперплоскости аѴ=0- Прибавление у* к вектору смещает весовой вектор непосредственно в направлении к данной гиперплоскости при возможности ее пересечения (рис. 5.10). Независимо от того, пересечется ли гиперплоскость или нет, новое скалярное произведение а^+^у* будет больше прежнего произведения

аіу* на величину Цу*1Р, в результате получаем, что вследствие коррекции весовой вектор смещается в нужном направлении.

Покажем теперь, что, если выборки линейно разделяемы, последовательность весовых векторов будет ограничиваться вектором решения. При доказательстве необходимо отметить, что каждая процедура коррекции сдвигает весовой вектор ближе к области решения. То есть следует показать, что если а является любым вектором решения, то значение 1|а;^+і—аЦ меньше значения Ца^^— —а1|. Хотя в общем случае данное утверждение оказывается несправедливым, будет показано, что оно выполняется для векторов решения, имеющих достаточную длину.

Пусть а — вектор решения, так что величина а*у; строго положительна для всех t, а а — положительный скалярный коэффициент. Из соотношения (14) следует, что

тогда

 

поскольку у* классифицировался с сшибкой, то а^у*<0, и, таким обозом, можно записать следующее выражение:

Трі как величина а*у* строго положительна, второй член будет модулю превосходить третий при условии, что значение а достаточно велико. В частности, если положить

и

ТО

и если выбрать

то получим следующее выражение:

Таким образом, квадрат расстояния от а* доаа при каждой коррекции будет уменьшаться, по крайней мере на величину р®, и после к коррекций представится в следующем виде:

Поскольку величина квадрата расстояния не может быть отрицательной, из этого следует, что последовательность коррекций должна быть ограничена числом коррекций, не большим чем ka, где

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

Число ka определяет предельное значение числа коррекций. Если аі=0, получается следующее достаточно простое выражение для ka.

Данное выражение показывает, что трудность задачи в основном определяется наличием выборок, наиболее близких к ортогональным по отношению к вектору решения. К сожалению, указанное выражение невозможно использовать при рассмотрении нерешенной зад^и, поскольку в данном случае граница должна определяться исходя из неизвестного вектора решения. Очевидно, что в общем случае задачи с линейно разделяемыми множествами могут представлять известные трудности для определения решения в условиях компланарности выборок. Тем не менее, если выборки линейно разделяемы, правило постоянного приращения будет давать решение после конечного числа коррекций.