Глава 4. Некоторые методы определения словаря признаков, используемого при построении системы распознавания

Выбор словаря признаков, используемого при построении системы распознавания, — самостоятельная и сложная задача. При разработке словаря признаков приходится сталкиваться со следующими ограничениями: 1) в словарь включают только признаки, отно сительно которых может быть получена априорная информация, достаточная для описания классов на языке этих признаков (будем называть словарь признаков, построенный с учетом этого ограничения, априорным словарем); 2) некоторые из признаков нецелесообразно включать в априорный словарь ввиду того, что они малоинформативны; 3) некоторые из признаков, как правило, наиболее информативные, не могут быть определены, ввиду отсутствия соответствующих измерителей, а ресурсы, ассигнованные на создание системы распознавания, ограничены. Именно поэтому априорный словарь признаков в общем случае может быть применен лишь в качестве основы для построения реально используемого в системе распознавания рабочего словаря. В рабочем словаре следует использовать лишь признаки, которые, с одной стороны, наиболее информативны и, с другой стороны, могут определяться имеющейся или специально созданной измерительной аппаратурой.

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

§ 4.1. Определение словаря признаков в условиях ограничений на стоимость создания технических средств наблюдений

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

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

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

тогда и только тогда, когда Далее, не нарушая общности рассуждений, будем пользоваться эвклидовой метрикой:

где есть значения признака объекта класса, т. е. объекта значение признака объекта класса, т. е. объекта

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

которую назовем среднеквадратичным разбросом класса или среднеквадратичным разбросом объектов внутри класса в качестве меры близости между объектами данной пары классов величину

которую назовем среднеквадратичным разбросом объектов классов

Совокупность признаков объектов, используемых в рабочем словаре, можно описать -мерным вектором компоненты которого принимают значения 1 или 0 в зависимости от того, имеется или отсутствует возможность определения соответствующего признака объекта, т. е.

С учетом квадрат расстояния между двумя объектами

Следовательно, среднеквадратичные разбросы класса и объектов классов могут быть записаны соответственно так:

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

Таким образом, затраты на создание средств наблюдений

где затраты на создание технического средства, обеспечивающего определение признака.

В качестве показателя качества или эффективности проектируемой системы распознавания рассмотрим функционал, зависящий в общем случае от функций решающего правила

Пусть величина собой меру близости между распознаваемым объектом со и классом заданным своими объектами . В качестве этой меры близости

рассмотрим величину

которая является среднеквадратичным расстоянием между объектом о и объектами класса

Решающее правило состоит в следующем:

Важно отметить, что уменьшение величины т. е. «сжатие» объектов, принадлежащих каждому данному классу, при одновременном увеличении т. е. «разведение» объектов, принадлежащих разным классам, обеспечивает в конечном счете улучшение качества системы распознавания. Поэтому повышение эффективности системы будем связывать с достижением экстремума функционала

Постановка задачи может быть сформулирована следующим образом.

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

Таким образом, задача сводится к нахождению условного экстремума функционала вида (4.10), т. е. к определению реализующего при

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

Возможные виды функционала. Рассмотрим некоторые частные виды функционала (4.13). Если требуемая эффективность системы распознавания может быть достигнута за счет более компактного расположения объектов каждого класса при соблюдении некоторых условий относительно величины то задача сводится к нахождению

при

Если требуемая эффективность системы может быть достигнута за счет «удаления» друг от друга объектов, принадлежащих разным классам при соблюдении некоторых условий относительно величины то задача сводится к нахождению

при

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

при

Возможны и другие постановки задачи и соответствующие им виды функционалов.

Метод решения задачи. Решим задачу определения набора признаков, максимизирующего минимальное расстояние между парами классов при ограничении на общую сумму стоимостей технических средств измерения признаков [8].

Квадрат расстояния между парой классов

где если признак используется в словаре признаков, или в противном случае.

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

Если выражение в квадратных скобках (4.19) обозначить через -номер пары классов, номер признака), то расстояние для пары

где величина, характеризующая информативность признака для пары классов.

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

где

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

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

где некоторые положительные постоянные, штрафные функции [9].

Если условия связи выполнены, то Если условия связи не выполнены, то второе слагаемое в правой части (4.23) характеризует меру отклонения точки от поверхности

Если для отыскания максимума функции применить градиентный метод, т. е. использовать рекуррентное соотношение

величина шага), то второе слагаемое будет направлено таким образом, чтобы компенсировать дефект в выполнении условий связи. Чем больше тем больше штраф за нарушение условий связи.

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

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

Например, в качестве можно взять функцию

Введем в рассмотрение функцию

Обозначим через точки, в которых функция достигает своего максимального значения на Е при данном А, через множество точек когда изменяется от 0 до

Так как множество Е компактно, то можно выделить сходящиеся подпоследовательности точек обладающих свойством

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

Возвращаясь к исходной задаче, введем в рассмотрение функцию

где рассматривается на -мерном единичном кубе

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

Так как слагаемое не зависит от то его можно ввести под знак

Далее, воспользовавшись методом сведения максмина к простому максимуму [11], имеем

где

представляет собой прямое произведение множеств: -мерного куба и отрезка

Объединив (4.30) и (4.31), получим

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

Докажем это. Обозначим максимизируемую функцию в (4.33) через ее производная по

при этом если

то для любого Кроме того, для любого Следовательно,

но при

и реализующем этот максмин,

т.е.

Правая часть этого неравенства не зависит от и при в силу (4.29) стремится к Первое слагаемое зависит только от К и при в силу (4.29) стремится к второе слагаемое зависит только от стремится к нулю. Следовательно,

что и требовалось доказать.

В частности, можно положить тогда

Нетрудно также показать, что реализующее максимум в правой части последнего равенства для некоторого фиксированного значения А, гарантирует при результат, сколь угодно близкий к максимальному гарантированному результату, т. е. для любого существует такое Ко, что для любого справедливо неравенство

Для практических расчетов по (4.41) задаются точностью в и произвольной последовательностью чисел для каждого

находят максимум правой части в (4.34), который обозначают через

Когда последовательно расположенные члены последовательностей начинают отличаться не более чем на считают, что найдены с заданной степенью точности максимальный гарантированный результат и оптимальный набор признаков распознаваемых объектов №. При определении максимума в (4.41) для каждого применимы, например, обычные градиентные методы.

Изложенный метод нахождения оптимального набора признаков можно использовать для решения задачи, когда функционал имеет вид (4.14) или (4.17).

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

Пусть априорные вероятности появления объектов классов соответственно равны Тогда априорная вероятность появления объектов обоих классов в предположении независимости этих событий Математическое ожидание квадрата среднеквадратичного расстояния между всеми парами классов

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

при ограничении вида

Наличие дополнительной априорной информации позволяет более рационально выбрать признаковое пространство, что приводит к увеличению критерия эффективности системы распознавания.

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

Пример. Пусть множество объектов подразделено на классы а априорный словарь признаков содержит признаки Заданные массивы данных указаны в следующей таблице:

(см. скан)

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

Рассмотрим решение задачи, когда Со изменяется с дискретностью, равной единице, от 13 до 33. В качестве критерия используем величину определяемую (4.22). Результаты решения задачи сведены в таблицу:

С ростом увеличивается значение критерия эффективности системы (рис. 4.1).

Рис. 4.1

В случае, когда известны значения критерия эффективности системы, определяемые (4.44), существенно выше.

Применительно к вариантам значений сведенным в таблицу:

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

(см. скан)