§ 3. Алгебраические методы построения решающих правил

В последнее время широкое распространение получили алгебраические методы построения алгоритмов распознавания и прогнозирования [42,62,63,116,138]. Суть алгебраического подхода коротко может быть описана так. Представим, что некоторая задача распознавания решается с помощью конечного набора  решающих функций: , например, линейная решающая функция,  — квадратичная,  — правило  ближайших соседей. Если качество полученных этими функциями решений окажется неудовлетворительным, то можно расширить круг используемых функций и среди этого расширенного множества попытаться найти функцию, которая давала бы более высокий результат.

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

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

Алгебраический подход успешно применяется при решении задач распознавания образов, в частности в распознавании и анализе изображений и в задачах прогнозирования многомерных динамических процессов. В русле этого подхода находятся, например, метод коллективов решающих правил (КРП) [138] и метод комитетов [116].

Идея метода КРП состоит в следующем. Пусть в нашем распоряжении имеется обучающая выборка  в пространстве  и несколько решающих правил. Предполагается, что разные правила могут оказаться «хорошими» в одной части пространства  и «плохими» в другой. Каждый признак системы  имеет конечное число градаций, так что пространство  можно представить состоящим из конечного количества «клеточек» (гиперпараллелепипедов). Распознаваемый объект  поместим в произвольную клеточку пространства  и применим для его распознавания все решающие правила по очереди. Отметим те правила, которые приняли правильное решение. Затем переместим объект  в другую клеточку пространства  и повторим распознавание. Снова отметим правила, успешно работавшие в этой части пространства. Таким способом просмотрим все части пространства  и для каждого решающего правила укажем границы области или перечень клеточек, в которых оно оказалось наиболее компетентным. На этом этап обучения заканчивается.

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

В методе комитетов в начале рассматривается широкий набор решающих правил, например параметрическое семейство из конечного числа гиперплоскостей. Каждая плоскость делит пространство  на две части, и при распознавании двух образов ( и ) можно указать вероятность присутствия представителей этих образов в одной  и другой  части пространства: ,  и , . Если в каждой из частей вероятности разных образов окажутся одинаковыми (и ), то такая плоскость интереса не представляет. Более полезными будут плоскости, которые отделяют друг от друга области с преобладающим присутствием одного из двух образов, например  и . По этой информации можно выбрать подмножество (коллектив) из  наиболее «информативных» плоскостей.

Решение о принадлежности распознаваемого объекта  к тому или иному образу принимается коллективом правил путем голосования. Если объект  относительно плоскости  находится в области , то эта плоскость голосует в пользу образа  с весом , а в пользу образа  — с весом . Можно просуммировать голоса, поданные всеми  плоскостями за -й образ, и получить оценку . Аналогично получается сумма голосов  за -й образ. Решение в пользу -го образа принимается, если . Можно пользоваться не суммами, а произведениями голосов.

Процедура построения коллективного решающего правила хорошо иллюстрирует важную роль методов распознавания в процессе познания. Исходная ситуация характеризовалась высокой степенью неопределенности, отсутствием какой бы то ни было модели изучаемого явления. Каждая отдельная гиперплоскость не позволяла надежно отличать один образ от другого, т. е. была «некорректной» распознающей моделью. Параметрический класс линейных решающих правил позволил сформировать из своего состава «корректную» распознающую модель. Как подчеркивает Ю. И. Журавлев [62], именно таким путем с помощью методов распознавания ситуации в неформализованных или слабо формализованных естественнонаучных областях оснащаются формализованными средствами познания. Создаваемые при этом модели позволяют ответить хотя бы на вопрос «Что происходит?». Если в обучающей выборке имеется соответствующая информация, то ее дальнейший анализ может привести к обнаружению закономерностей причинно-следственного характера и сформировать модель для ответа на вопрос «Как это происходит?» или даже на вопрос «Почему именно так, а не иначе?».