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

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

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

Базисная персептронная функция критерия задается следующим выражением:

где У (а) — множество выборок, классифицируемых с ошибкой посредством вектора а. Для того чтобы исключить тривиальное решение а=0, введем положительный вектор допуска Ь и напишем выражение

где  если а*уг<Ьг- Очевидно, что Jp является не линейной,

а кусочно линейной функцией от а, и поэтому непосредственное применение метода линейного программирования здесь невозможно. Однако если ввести п искусственных переменных и соответствующих им ограничений, то можно построить некоторую эквивалентную линейную целевую функцию. Рассмотрим задачу отыскания векторов а и t, минимизирующих линейную функцию

при ограничениях и

Очевидно, что для любого фиксированного значения вектора а минимальное значение z в точности равно ./р(а), поскольку при имеющихся ограничениях мы получим наилучший результат, если положим ^і=тах (О, bj—а*Уг)- Если теперь найти минимум z по всем возможным значениям t и а, то мы получим минимально возможное значение Jp(a). Таким образом, задачу минимизации Jp{a) мы свели к задаче минимизации линейной функции г при наличии ограничений в виде линейных неравенств. Приняв и„ за л-мерный единичный вектор, приходим к следующей задаче с m=2d+n переменными и 1=п ограничениями: минимизировать а‘и при условии

где

Выбор а=0 и ti=bi обеспечивает базисное допустимое решение, которое позволяет теперь применить алгоритм симплекс-метода. В результате за конечное число шагов может быть определено то значение а, которое доставляет минимум Jp{a).