Оптимизация отбора оптимальных признаков на основе применения
методов моделирования эволюции для задачи распознавания текста
В.В. Хашковский,
А.Н.Толкачёв
1.
Введение
За последние почти 40
лет, прошедшие после появления первых работ, посвященных проблеме распознавания
образов, были достигнуты значительные успехи. Научно-технический прогресс
привел к появлению новых как узкоспециализированных методов, так и методов,
предназначенных для решения широкого круга задач. Методы распознавания образов
применяются для идентификации различных визуальных и слуховых образов, а также
для выработки оптимальных решений в управлении различными технологическими
процессами.
Круг задач, которые
могут решаться с помощью распознающих систем, очень широк. Сюда относятся не
только задачи распознавания зрительных и слуховых образов, но и задачи
распознавания сложных процессов и явлений, возникающих, например, при выборе
целесообразных действий руководителем предприятия или выборе оптимального
управления технологическими, экономическими или транспортными операциями.
2.
Распознавание образов
В целом задача
распознавания образов состоит из 2-х частей: обучения и распознавания. Обучение
осуществляется путём показа отдельных объектов или явлений, в результате чего
распознающая система должна приобрести способность реагировать одинаковыми реакциями
на изображения одинаковых образов и различными на изображения различных образов.
Распознавание характеризует действия уже обученной системы. Автоматизация этих
процедур и составляет проблему обучения распознаванию образов. В тех случаях,
когда человек придумывает и навязывает машине правило классификации, проблема
распознавания решается лишь частично, так как основную и главную часть проблемы
человек берёт на себя.
Кроме того, характерное
свойство образа состоит в том, что объекты, входящие в образ, могут претерпевать
существенные изменения и вместе с тем оставаться объектами одного и того же
образа. Однако, обладая этим свойством, образы в некотором смысле неопределённы,
расплывчаты. Часто трудно определить к какому образу принадлежит объект.
Примером может служить превращение головастика в лягушку. Так как не все образы
имеют четкие границы, то человек, а тем более машина, не всегда может
гарантировать безошибочное распознавание. Тем не менее были определены основные
подходы к решению задачи распознавания, и значительное число разработанных
методов было создано в рамках этих подходов. Рассмотрим кратко эти подходы.
В своей работе Селфридж
(1959) предложил осуществлять распознавание образов вычислением взвешенной
суммы ряда «рекомендованных» классификаций, каждая из которых основана на
разных характеристиках распознаваемого объекта (признаках). Хотя индивидуальные
рекомендации могут носить почти случайный характер, система в целом может быть
достаточно точной. Можно считать, что каждый объект имеет простейшее описание,
представляемое вектором, элементы которого служат аргументами для ряда функций,
и значения этих функций в свою очередь служат аргументами для некоторой
решающей функции, которая определяет окончательную классификацию.
Другой подход к проблеме
распознавания образов заключается в аналогии с биологическими процессами.
Поскольку распознавание образов должно быть функцией нейронов, можно искать
ключ к биологическому распознаванию образов в свойствах самого нейрона. Мак-Каллок
и Питтс (1943) доказали, что любую вычислимую функцию можно реализовать с
помощью должным образом организованной сети идеальных нейронов - пороговых элементов,
логические свойства которых с достаточным основанием можно приписать реальному
нейрону. Проблема состоит в том, можно ли найти какой-то разумный принцип реорганизации
сети, позволяющий случайно объединенной вначале группе идеальных нейронов
самоорганизоваться в «вычислительное устройство», способное решать произвольную
задачу распознавания образов. К настоящему времени разработано достаточно
большое число архитектур искусственных нейронных сетей (ИНС), но рассмотрение
их выходит за рамки данной статьи.
Нейрологическая теория
обучения, выдвинутая канадским психологом Хеббом (1948), хотя и была вначале
рассчитана на использование в области психологии, оказала большое влияние на
искусственный интеллект. Ее модификация применялась при определении принципов
системы распознавания образов, получившей название персептрон (Розенблатт 1958,
1962).
3.
Постановка задачи
В настоящее время
существует большое число методов, позволяющих с меньшей или большей точностью
решать задачу распознавания текста. Создано много систем, реализующих те или
иные методы, так называемые OCR-системы. Кроме того,
что эти системы разнятся по качеству распознавания, существуют серьезные
ограничения на пределы применимости тех или иных методов. Так, например,
совершенно очевидно, насколько различные требования будут предъявляться к
настольной системе распознавания текста и к системе автоматического определения
индекса на почтовом конверте.
Несколько слов следует
сказать о различиях в текстах, подлежащих распознаванию. Они могут быть печатными
и рукописными. Разница весьма существенна - при распознавании рукописного
текста требуется решить дополнительно задачу разделения изображений, сложность
которой не меньше, чем сложность задачи непосредственно распознавания.
Абстрагируясь от частных проблем, связанных с выделением изображения,
нормализацией его по размерам и положению на растре, имеет смысл ввести в
рассмотрение задачу распознавания нормализованных растровых изображений.
Примером такой задачи может служить задача распознавания почтового индекса.
Однако, вследствие того,
что вопросы нормализации могут быть успешно решены для печатного текста,
составные элементы которого (далее - изолированные изображения) могут быть
выделены без применения сложных специальных алгоритмов, задачу распознавания
почтового индекса можно считать частным случаем задачи распознавания печатного
текста.
В [1], [2], [3]
предложен метод распознавания изолированных изображений, главными характеристиками
которого являются:
довольно длительное
обучение.
малое время
распознавания.
Для данного метода
полагается, что распознаванию подлежат изображения X=xn...x1,
где компоненты xÎ{0,1}. В обучающую
выборку входит по N0 изображений каждого образа. Функция
принадлежности f(X) равна +1 или -1 в зависимости от принадлежности изображения
к образу с номером j=1 или к образу с номером j=2. Обучение сводится к
вычислению весов q разложения f(X) в ряд по системе признаков j(L,X). При этом на основе случайного
поиска отбирается и фиксируется в памяти M признаков.
Критерий оптимальности
p-го признака
Формула
1
где d - малая величина, означает сложение по всем изображениям каждого из двух
образов. Результат обучения - М пар Lp sign(qp) или Lp,
qp.
Распознавание сводится к
восстановлению знака f(X) по формуле
Формула 2
где означает сложение по
всем М оптимальным признакам.
Проведенные эксперименты
показали, что для достижения достаточно хороших результатов распознавания,
необходимо использовать относительно жесткие условия (критерии) при обучении.
При этом длительность обучения может быть неприемлемо велика (в экспериментах -
до 10 часов).
В данной работе
предлагается способ ускорить обучение, что позволит в значительной мере усилить
критерии обучения и, при этом, оставить время обучения в разумных пределах.
Описание предложенной
модификации начнем с того, что рассмотрим кратко метод отбора оптимальных
признаков, предложенный в [1], в части, требующей модификации.
4.
Метод отбора оптимальных признаков
Многоальтернативная
задача с S образами может быть сведена к S элементарным дихотомиям, каждая из
которых позволяет отделить изображения какого-либо образа от остальных. В
каждой дихотомии отыскивается определённое число оптимальных признаков, так что
длительность обучения, по крайней мере, в S
раз превышает длительность обучения в одной дихотомии. Фактически
длительность обучения оказывается ещё большей, так как обучающая выборка
содержит SN0 изображений.
Так как обработка
многокомпонентных изображений X=xn...x1 требует
определённых временных затрат, тем больших, чем больше n, то общее время
обучения может оказаться неприемлемо большим.
Один из способов
ускорения обучения связан с преобразованием исходных изображений в промежуточные
изображения Y=ym...y1, где m