Оптимизация отбора оптимальных признаков на основе приме-нения методов моделирования эволюции для задачи распозна-вания текста (стр. 2 из 2)

Формула 4

Введём двоичную переменную y_p такую, что y_p=0, если j(L_p,X)=-1, и y_p=1, если j(L_p,X)=1. Совокупность m таких переменных может рассматриваться как искомое промежуточное изображение.

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

Формула 5

j=1,2,..,S.

где d^*₁ - достаточно малая величина. Критерий определяет условие совпадения признака для большинства изображений каждого образа.

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

Итак, первый этап обучения сводится к отысканию m оптимальных признаков j(L,X) первого уровня и фиксации m параметров L. Это позволяет на первом этапе распознавания преобразовать любое исходное изображение в некоторое промежуточное изображение с малым числом компонентов. Последующие процедуры выполняются с этими малокомпонентными изображениями.

Как следует из описания, в данном методе качество распознавания можно повышать путем ужесточения критериев на первом этапе, однако при этом значительно увеличивается время обучения. Важно понимать, что именно первый этап обучения существенно влияет на время обучения системы. Это происходит потому, что второй этап обучения (см. [1],[2],[3]) реализуется за счет перебора конечного числа точечных признаков, а именно 2^m. Число всех этих признаков зависит, конечно, от числа признаков первого этапа m, и все-таки оно является конечным и относительно небольшим.

В противоположность признакам второго этапа обучения, которые выявляются из небольшого конечного числа точечных признаков, признаки первого этапа обучения (полосовые признаки) генерируются случайным образом, и процесс этот, при достаточно жестких критериях, может стать «бесконечным». Здесь следует уточнить, что на самом деле общее число полосовых признаков ограничено, но это число зависит от размера растра и для сколько-нибудь практических задач настолько велико, что при существующих вычислительных мощностях практически недостижимо. Например, для растра 32*32, общее число полосовых признаков составит 17976,93134861Е+304.

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

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

5. Генетическая модификация МООП

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

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

Основные отличия ГА состоят в следующем:

ГА осуществляют поиск из множества (популяции) точек, а не из единственной точки;

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

Рассмотрим механизм простого ГА (ПГА): сначала ГА случайно генерирует популяцию последовательностей (стрингов); далее он копирует последовательности и переставляет их части; затем ГА применяет некоторые операторы к начальной популяции и генерирует новые популяции.

В ПГА используется 3 оператора: репродукция, кроссовер, мутация. Поясним кратко действие некоторых используемых генетических операторов.

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

Оператор Кроссовера (ОК): оператор кроссовера может выполниться в 2 шага. На первом шаге элементы множества стрингов случайно разбиваются на пары. Затем из каждой пары стрингов формируется новая пара по правилу: случайно выбирается целочисленная позиция вдоль стринга между 1 и длиной стринга L - точка скрещивания. Новая пара стрингов создается вследствие обмена частями исходных стрингов, относительно точки скрещивания. Например, X и Y представляют собой два стринга (родители). Если теперь случайным или заранее заданным способом выбрать точку скрещивания, то смешивая части исходных векторов можно получить два новых потомка:X' и Y'.

X: x₁x₂x₃x₄x₅ |x₆x₇x₈

Y: y₈y₇y₆y₅y₄ |y₃y₂y₁

X': x₁x₂x₃x₄x₅ |y₃y₂y₁

Y': y₈y₇y₆y₅y₄ |x₆x₇x₈

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

Оператор Мутации (ОМ): соответствует случайному нарушению последовательности битов в стринге; например, применяя ёоператор мутации к X', можно получить X''₁:x₁x₂x₃x₄x₅y₂y₃y₁ или X''₂:x₁x₃x₂x₄x₅y₃y₂y₁ и т.д. Обычно выбирают одну мутацию на 1000 бит. Считается, что мутация - вторичный механизм в ГА.

Для оптимизации поиска оптимальных признаков использование ГА может быть описано следующим образом.

Сначала определяется соответствие между хромосомой и полосовым признаком. В данном случае полосовой признак (растровое изображение) "вытягивается" в вектор (стринг). Далее случайным образом генерируется некоторое множество возможных полосовых признаков - начальная популяция P₀=X⁰₁, X⁰₂, … X⁰_n. Затем для каждой хромосомы вычисляется функция фитности, которая в данном случае представляет собой комплексную оценку, вычисляемую с учетом критериев отбора оптимальных признаков первого рода.

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

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

Список литературы

Ефимов Ю.Н. Распознавание изображений с использованием оптимальных признаков АВТ.-1992.-№2.-С. 69-75.

1531115 СССР. Устройство для распознавания образов/ Ефимов Ю.Н. -заявлено 08.10.87// Открытия. Изобретения. Пром. образцы. Товар. знаки.-1989.-№47.- С.162.

1799359 СССР. Устройство для распознавания образов/ Ефимов Ю.Н. -заявлено 12.12.89// Открытия. Изобретения. Пром. образцы. Товар. знаки.-1992.-№4.- С.195.

Holland. I. Adaptation in Natural and Artifical Systems. University of Michigan Press, Ann Arbor, 1975.

Курейчик В. М. Применение генетических методов для компоновки схем СБИС. сб. Интеллектуальные САПР №4, 1994.

Хант Э. Искусственный интеллект, «Мир», М. 1978.

Rosenblatt F. The perceptron: A probalistic model for information storage and organization in the brain, Psychol. Rev., 65, 386-408, 1958.

Rosenblatt F. Principles of neurodynamics, Baltimore, 1962, (Русскийперевод: РозенблаттФ., Принципынейродинамики, «Мир», М., 1966).

Selfridge O. Pandemonium. A paradigm for learning, всб. «Proceedings of the Symposium on the Mechanization of Tought Processes» подред. Blake D., Utteley A., London, 1959.

McCulloch W., Pitts W. A logical calculus of the ideas imminent in nervous activiti, Bull. Math. Biophys., 5, 115-137., (Русский перевод в сб. «Автоматы» под ред. Маккарти Дж. и Шеннона К., ИЛ. М., 1956).

Hebb D. The organization of behavior, New York, 1948.