5.5. МИНИМИЗАЦИЯ ПЕРСЕПТРОННОЙ ФУНКЦИИ КРИТЕРИЯ

5.5.1. ПЕРСЕПТРОННАЯ ФУНКЦИЯ КРИТЕРИЯ

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

где - множество выборок, классифицируемых с ошибкой посредством а. (Если выборок, классифицируемых с ошибкой, нет, то полагается равной нулю.) Так как если у классифицируется с ошибкой, то функция не может быть отрицательной. Она достигает нулевого значения, когда а является вектором решения или же находится на границе области решений. Геометрически функция пропорциональна сумме расстояний от выборок, классифицируемых с ошибкой, до границы области решений. На рис. 5.8 изображена функция для простого двумерного случая.

Поскольку компонента градиента выражается в виде частной производной из формулы (12) следует, что

и при этом основной алгоритм (8) приводится к следующему виду:

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

Рис. 5.8. Персептронная функция критерия, а — весовое пространство, б — функция критерия.

Рис. 5.9; Определение области решения методом градиентного анализа.

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

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

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

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

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

где

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

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

Рис. 5.10. Шаг, соответствующий правилу постоянного приращения.

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

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

тогда

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

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

и

то

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

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

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

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

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

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

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

5.5.3. НЕКОТОРЫЕ НЕПОСРЕДСТВЕННЫЕ ОБОБЩЕНИЯ

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

где теперь для всех k. Можно показать, что, если выборки линейно разделяемы и если

и

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

Следующим вариантом, представляющим интерес, является первоначально рассмотренный алгоритм градиентного спуска для

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

Таким образом, если выборки являются линейно разделяемыми, то все возможные виды корректирующих векторов составляют линейно разделяемое множество, и если удовлетворяет соотношениям (21) — (23), то последовательность весовых векторов, получаемая посредством алгоритма градиентного спуска для всегда будет сходиться к вектору решения.

Интересно заметить, что условия, налагаемые на удовлетворяются в тех случаях, когда является положительной константой и когда убывает как или даже возрастает с ростом k. Вообще говоря, предпочтение следует отдавать уменьшающемуся с течением времени. Это замечание становится особенно существенным, когда есть основание считать, что множество выборок линейно неразделяемо, поскольку в данном случае уменьшается отрицательное влияние нескольких «плохих» выборок. Однако то, что в случае разделяемых выборок при увеличении получение решения оказывается все же возможным, кажется довольно странным.

Из данного наблюдения вытекает одно из различий между теоретическим и практическим взглядами на эту проблему. С теоретической точки зрения представляется интересным тот факт, что решение можно получить при наличии конечного числа шагов в случае любого ограниченного множества разделяемых выборок, при любом начальном весовом векторе при любом неотрицательном значении допуска b и при любом скалярном коэффициенте удовлетворяющем соотношениям практической точки зрения желательно производить разумный выбор указанных величин. Рассмотрим, например, допуск b. Если b намного меньше т. е. той величины, на которую возрастает в результате коррекции, то очевидно, что b будет оказывать совсем малое влияние. Если b намного превосходит величину то потребуется большое число коррекций, чтобы добиться выполнения условия Часто в качестве компромиссного подхода используют величину, близкую к Кроме указанных вариантов выбора и b, большое влияние на результат может оказывать масштабирование компонент вектора у. Наличие теоремы сходимости не избавляет от необходимости сознательного подхода при использовании данных методик.