8.4. Экспериментальное изучение порождения признаков в распознавании образов

Число различных комбинаций выделения признаков и распознавания образов слишком велико. Взаимодействуют ли этапы выделения признаков и распознавания образов, и если да, то как? Для того чтобы пролить некоторый свет на эти вопросы, я вместе с Марком Стикелем провел эксперимент. Его результаты дают интересный пример того, как выделение признаков может изменить логические характеристики задачи распознавания образов.

Рис. 8.5. (см. скан) Различные этапы в процедуре распознавания образов.

Основная схема эксперимента приведена на рис. 8.5. На вход программы предъявлялись двумерные плоские фигуры, спроектированные на сетку размером 25x25. Внутри программы предъявляемые образы представлялись в терминах положения двух подобразов (признаков) размером 5x5, подобных тем, что использовались У ром и Восслером. Сначала программа выбирала эти два признака случайным образом, затем эти признаки выбирались путем имитации признаков в классифицируемых данных. Вектор у обнаруженных признаков определял входную информацию для части программы, распознающей образы. Она указывала, сколько раз появлялся каждый признак и его среднее положение по горизонтали и вертикали. Устройство распознавания образов затем

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

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

В экспериментах, изложенных ниже, варьировалось число описаний, которые программа могла хранить в памяти в данный момент. Обучение заканчивалось, когда либо классифицировались 100 изображений, либо на работу центрального процессора машины ИБМ-7094 уходило 15 минут. После обучения применялось последнее из построенных правил для классификации 100 новых образов, которые выбирались независимо от выбранных при обучении.

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

знаки или (рис. 8.6), на сетку размером в соответствии со следующими правилами.

(1) В случае линейной задачи для класса 1 вероятность помещения на подполе была больше 0,5 для двух верхних строк подполей размером вероятность помещения X на подполе была больше 0,5 для двух нижних строк. Для класса 2 распределение вероятностей было обратным.

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

Рис. 8.6. Компоненты для построения образов, использовавшиеся в экспериментах.

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

(3) В случае последовательной задачи классы определялись отношением между положениями знаков их. Для класса 1 знаки помещались с высокой вероятностью в верхний левый угол, а знаки х — в нижний правый, или помещались в верхний правый, в нижний левый. Для класса 2 примеров вероятнее всего можно было найти над X как в правой, так и в левой части сетки. Таким образом, задача представляла собой классификацию, основанную на двух „моделях" образов на каждый класс.

Для класса 1 было

и для класса 2

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

Рис. 8.7. (см. скан) Средняя точность правил классификации для различных программ распознования образов: а - линейные задачи; б - задачи группирования; в - последовательные задачи.

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

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

Рис. 8.8. Признаки, порожденные устройством линейного распознавания образов при решении последовательной задачи: а — нижняя часть знака + над пустым полем; б — пустое поле над верхней частью знака X; в - + над X.

Самая яркая иллюстрация — пример того, как линейное устройство решает последовательную задачу. Напомним, что для решения последовательной задачи надо выявить, имеют ли знаки + тенденцию появляться над X в любом месте сетки размером Рассматриваемое устройство линейного распознавания образов требовало, чтобы новые признаки порождались до тех пор, пока устройство выделения признаков не выделит их (рис. 8.8). Программа нашла характеристики границы между областями с высокой и низкой плотностями знаков + и X.

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