5.10. ПРОЦЕДУРЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

5.10.1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Классическая задача линейного программирования формулируется следующим образом: найти вектор

который минимизирует линейную целевую функцию

и удовлетворяет ограничению

где а есть -вектор цен, — -вектор и -матрица.

Для решения поставленной задачи может быть использован симплекс-метод; его описание можно найти в любой книге по линейному программированию. Симплекс-метод представляет собой классическую итеративную процедуру. Его использование требует введения еще одного ограничения для вектора и, а именно

Если искать и в виде некоторого весового вектора а, то такое ограничение неприемлемо, так как в большинстве случаев вектор решения будет иметь как положительные, так и отрицательные компоненты. Однако если представить а в виде

где

и

то и будут неотрицательны. Отождествляя компоненты и, например, с компонентами мы можем наложить ограничение .

5.10.2. СЛУЧАЙ ЛИНЕЙНО РАЗДЕЛЯЕМЫХ МНОЖЕСТВ

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

и

Если t достаточно велико, эти условия выполняются без труда, например если Однако такой случай не представляет

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

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

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

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

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

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

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

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

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

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

и

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

где

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

5.10.4. ЗАМЕЧАНИЯ

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

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

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

Таблица 5.1. Процедуры спуска для отыскания линейных разделяющих функций

(см. скан)

Продолжение табл. 5.1. (см. скан)