Методы машинного обучения в задаче распознавания символов

Размещено на http://www.allbest.ru

МЕТОДЫ МАШИННОГО ОБУЧЕНИЯ В ЗАДАЧЕ РАСПОЗНАВАНИЯ СИМВОЛОВ

Л.А. Ицкович (Lev_I@abbyy.com)

С.О. Кузнецов (skuznetsov@yandex.ru)

Москва

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

признаковый классификатор распознавание символ

ВВЕДЕНИЕ

Важная составная часть программ оптического распознавания символов - признаковые классификаторы, основанные на методах обучения по прецедентам (методах машинного обучения или методах обучения с учителем) [Mitchell, 1997]. Эти методы позволяют автоматически строить правила классификации объектов по их описаниям на основе имеющихся примеров классификации.

Цель данной работы - определить, какие из известных признаковых классификаторов и в какой степени подходят для распознавания символов. В качестве базовой рассматривается схема печатного анализатора, принятая в ABBYY OCR Technologies. Исходя из её устройства, формулируются требования, предъявляемые к признаковым классификаторам, которые могут быть использованы для решения задачи распознавания символов. Результаты, полученные на алгоритмах, входящих в состав этой схемы, рассматриваются в качестве базы для сравнения с альтернативными классификаторами.

1. БАЗОВЫЕ АЛГОРИТМЫ

Классификаторы будем описывать в следующих обозначениях [Журавлёв и др., 2007]. - множество всевозможных объектов (символов), каждый из которых характеризуется признаками . Значение признака объекта обозначается как . Для конечной обучающей выборки определена функция , сопоставляющая объекту его класс из конечного множества классов . Задача обучения классификатора - приближённое построение функции , связывающей значения числовых признаков и класс любого объекта из , а не только из .

1.1 Метод ближайшего соседа

В простейшем варианте метода классом объекта считается класс ближайшего (в смысле функции ) объекта обучающей выборки:

.

Множество модификаций метода использует различные функции расстояния [Терещенко, 1999]. Возможны также различные преобразования обучающей выборки: например, при большом её размере часто ограничиваются множеством «типичных представителей» классов, полученным с помощью кластеризации исходной выборки.

1.2 Наивный байесовский классификатор

В качестве представителя статистического подхода к классификации рассмотрим наивный байесовский классификатор [Hastie et al., 2001]. Его решающее правило предпочитает наиболее вероятный при данных значениях признаков классу объекта:

. (0.1)

С использованием теоремы Байеса и «наивных» предположений о независимости признаков выражение (0.1) может быть преобразовано:

. (0.2)

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

1.3 Дерево решений

В качестве представителя иерархических методов классификации рассмотрим дерево решений [Mitchell, 1997]. Это древовидный граф, с помощью которого классификация объекта происходит путём перемещений по рёбрам этого графа от корня в одну из листовых вершин. Каждой листовой вершине присвоена метка класса , которая и является выходным значением такого классификатора. К каждой нелистовой вершине приписан один из признаков ; в зависимости от его значения переход происходит в одного из её потомков (соответствующих значениям или интервалам значений признака).

1.4 Классификатор на основе решётки формальных понятий

Этот классификатор представляет собой решётку формальных понятий [Ganter et al., 1999]. Подробно его устройство описано в [Guillas et al., 2006]. Здесь же лишь отметим, что процесс классификации сходен с древесным (начинается в корне и заканчивается в одном из листьев), но преимущество его состоит в том, что учитываются логические взаимосвязи между признаками объектов обучающей выборки.

2. СХЕМА РАСПОЗНАВАНИЯ ПЕЧАТНОГО АНАЛИЗАТОРА ABBYY FINEREADER

2.1 Общее устройство и используемые классификаторы

Общая схема печатного анализатора представлена на рисунке 1.

Рис.1. Схема печатного анализатора ABBYY OCR Technologies

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

Тема растровой классификации лежит за пределами данной работы. Признаковые классификаторы - омнифонтовый и контурный - используют одинаковое решающее правило. Набор символов каждого класса кластеризуется, а классификация происходит методом ближайшего соседа, где в качестве функции расстояния от классифицируемого объекта до кластера используется расстояние Махаланобиса [Ян, 2003].

Функция признаковых классификаторов - породить упорядоченный по уверенности список гипотез (возможных вариантов класса символа) и передать их на вход дифференциальному классификатору. Его функция - переупорядочить список гипотез путём их попарных сравнений.

2.2 Требования к признаковым классификаторам

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

2.2.1 Высокий процент распознанных символов

2.2.2 Способность генерировать варианты распознавания

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

Таким образом, требование 2.2.1 ужесточается: недостаточно получать в 95% случаев верную первую гипотезу; нужно, чтобы и в значительной части из оставшихся 5% правильный вариант лежал в списке гипотез.

2.2.3 Способность оценивать уверенность гипотез

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

2.2.4 Требования по скорости

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

3. МОДИФИКАЦИИ БАЗОВЫХ АЛГОРИТМОВ

То, насколько рассмотренные алгоритмы удовлетворяют требованиям по точности распознавания, может быть проверено только экспериментально (это сделано в разделе 4). Сейчас же речь пойдёт о том, возможно ли модифицировать эти методы, чтобы они удовлетворяли остальным перечисленным требованиям.

3.1 Метод ближайшего соседа

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

С точки зрения скорости предпочтительным оказывается уже упомянутый вариант алгоритма с кластеризацией: в качестве эталонов достаточно хранить не все объекты обучающей выборки, а только центры кластеров. Отметим, что такой вариант алгоритма используется в ABBYY FineReader и потому рассматривается в качестве базового [Ян, 2003].

3.2 Наивный байесовский классификатор

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

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

3.3 Дерево решений

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

3.3.1 Post-fuzzification

Не изменяя алгоритм построения дерева C4.5 [Quinlan, 1993], модифицируем процесс классификации способом, рассмотренным в [Chiang et al., 2001] (так называемый post-fuzzification).

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

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

Ввести уверенности можно следующими способами. Первый - аппроксимировать распределение значений признака в вершинах нормальным распределением:

. (0.3)

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

. (0.4)

В формуле (0.4) , - минимальное и максимальное значение признака среди объектов из .

3.3.2 Random forest

Другим решением является random forest [Breiman, 2001] - голосование деревьев. Прямое его назначение - повышение точности (и в разделе 4 будет показано, что оно присутствует); но, кроме того, это и способ генерации гипотез.

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

3.3.3 Комбинация перечисленных способов

Отметим, что способы 3.3.1 и 3.3.2 могут быть скомбинированы: деревья, входящие в random forest, могут, в свою очередь, также выдавать несколько гипотез. Возможны различные варианты их комбинирования: например, по сумме уверенностей каждой буквы или по её максимуму.

3.4 Классификатор на основе решётки формальных понятий

Этот классификатор также может быть включён в состав random forest.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ

Эксперименты проводились на обучающей (около 9000 символов) и тестовой (около 300000 символов) выборках, принятых в ABBYY OCR Technologies. Все описанные результаты получены на омнифонтовых признаках (73 числовых признака), но их проверка на контурных признаках (74 числовых признака) значительных расхождений не выявила.

4.1. Способ построения дерева решений

Дерево решений может быть построено несколькими способами. Данные могут быть дискретизированы (с применением той или иной меры качества разбиения), и к ним может быть применён алгоритм C4.5 для дискретных признаков. Кроме того, может быть применена модификация C4.5 для числовых данных (подбор точки разбиения оси значений признака непосредственно в вершине). Наконец, возможен выигрыш от применения решётки формальных понятий вместо дерева решений. Поэтому перед дальнейшими экспериментами было произведено сравнение данных алгоритмов (табл. 1).

Табл. 1.

Таким образом, лучший результат достигается деревом решений, построенным напрямую по числовым признакам. Решёточный алгоритм не обеспечивает такого выигрыша, как на малых выборках [Ицкович и др., 2008], - вероятно, потому, что среди 9000 объектов сложно выявить априорные логические связи между признаками.

4.2 Деревья решений с вариантами

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

Сразу отметим, что аппроксимация нормальным распределением результатов не даёт (уже на 2 вариантах точность падает до 80%). Причина в том, что уверенность в середине интервала зависит от ширины интервала, что приводит к немотивированным изменениям уверенности правильного варианта в широком диапазоне.

Лучшие результаты даёт применение трапецеидальной функции, а ещё лучшие - random forest. На рисунке 2 приведена зависимость процента распознанных символов от числа гипотез (для post-fuzzification это ширина фронта лучевого поиска, для random forest - число деревьев).

Рис.2. Сравнение способов генерации гипотез

4.3 Сравнение рассматриваемых алгоритмов

Теперь сравним лучшие варианты всех рассматриваемых алгоритмов. На рисунке 3 приведены проценты символов, для которых правильная гипотеза встречается среди первых N гипотез (N - по оси абсцисс).

ВЫВОДЫ

Таким образом, существуют модификации наивного байесовского классификатор, метода ближайшего соседа (с кластеризацией) и random forest, которые достигают точности 1-й гипотезы более 95%, а 8 гипотез - более 99%. Лучшего результата достигает random forest (более 97%), причём для этого достаточно уже небольшого количества деревьев (порядка 5).

Рис.3. Сравнение признаковых классификаторов

СПИСОК ЛИТЕРАТУРЫ

[Журавлёв и др., 2007] Журавлев Ю.И., Рязанов В.В., Сенько О.В. «Распознавание». Математические методы. Программная система. Практические применения. - М.: Фазис, 2005.

[Ицкович и др., 2008] Ицкович Л.А., Колотиенко С.С., Кузнецов С.О. Распознавание символов с помощью решёток формальных понятий и сравнительный анализ метода с другими алгоритмами распознавания символов // Труды 51-й научной конференции МФТИ - М., 2008.

[Терещенко, 1999] Терещенко В.В. Разработка и реализация новых принципов автоматического распознавания рукописных документов в компьютерных системах обработки данных: дисс. канд. физ.-мат. наук: 05.13.06 - М., 1999.

[Ян, 2003] Ян Д.Е. Исследование, развитие и реализация методов автоматического распознавания рукописных текстов в компьютерных системах: дисс. канд. физ.-мат. наук: 05.13.18 - М., 2003.

[Breiman, 2001] Breiman L. Random forests // Machine Learning, Volume 45, Number 1, 2001.

[Chiang et al., 2001] Chiang I-Jen, Jane Yung-jen Hsu. Fuzzy classification trees for data analysis // Fuzzy Sets and Systems 130, 2002.

[Ganter et al., 1999] Ganter B., Wille R. Formal Concept Analysis: Mathematical Foundations. Springer, 1999.

[Guillas et al., 2006] Guillas S., Bertet K., Ogier J.-M. A Generic Description of the Concept Lattices' Classifier: Application to Symbol Recognition // In Graphics recognition: ten years review and future perspectives - selected papers from GREC'05, 2006.

[Hastie et al., 2001] Hastie T., Tibshirani R., Friedman J.. The elements of statistical learning. Springer-Verlag, New York, 2001.

[Mitchell, 1997] Tom M. Mitchell, Machine Learning. McGraw-Hill, 1997.

[Quinlan, 1993] Quinlan J.R. C4.5: Programs for Machine Learning, Morgan Kaufmann, Los Altos, CA, 1993.

Размещено на Allbest.ru