Содержание к диссертации
Введение
1. Обзор существующих методов контекстной обработки 9
1.1. N-граммы 9
1.2. Динамическое программирование
1.2.1. Дискретный процесс управления 13
1.2.2. Метод динамического программирования 13
1.2.3. Алгоритм Левенштейна 14
1.2.4. Обзор работ 16
1.3. Скрытые марковские модели 17
1.3.1. Определение СММ. 17
1.3.2. Обзор работ
1.4. Нейронные сети 20
1.5. Методы коррекции и валидации текстов
1.5.1. Словарные методы 22
1.5.2. Вероятностные методы 23
1.5.3. Техника похожих ключей. 23
1.5.4. Сравнение методов
1.6. Классификационные методы 25
1.7. Методы синтаксического анализа
1.7.1. Формальные языки. Компилирование 28
1.7.2. Естественные языки. Компьютерная лингвистика 30
1.8. Выводы 32
2. Синтаксические методы контекстной обработки 33
2.1. Представление результатов распознавания. ар-сеть, ар-цепь, ар-матрица 33
2.2. Формальные языки и грамматики, синтаксические диаграммы
2.2.1. Язык 36
2.2.2. Понятие грамматики. ГрамматикаХомского 37
2.2.3. Нотация Бэкуса-Наура 38
2.2.4. Синтаксические диаграммы 39
2.2.5. PDSграмматика. 39
2.3. Классификация типов полей на формах 42
2.3.1. Словарное поле.. 42
2.3.2. Текст на естественном языке 43
2.3.3. Поле с заданным синтаксисом 43
2.3.4. Поле, описываемое синтаксисом частично 44
2.3.5. Поле с нефиксированным текстовым представлением 44
2.3.6. Поля со специальными ограничениями 45
2.4. Постановка задачи контекстной обработки 45
2.4.1. Восстановление текстового значения 45
2.4.2. Классификация текстового значения 46
2.4.3. Приведение распознанного значения к нормальной форме 47
2.4.4. Оценка степени надежности распознанного значения 47
2.4.5. Локализация ненадежных фрагментов 48
2.4.6. Нахождение опорных фрагментов 48
2.5. Поиск заданного текстового фрагмента в ар-цепи. алгоритм MCHSR 49
2.5.1. Структура результатов распознавания 49
2.5.2. Описание алгоритма MCHSR 50
2.6. синтаксический подход 55
2.6.1. О подходе 55
2.6.2. Основная алгоритмическая схема 55
2.6.3. ОП-процедура 57
2.6.4. Эксперименты и результаты 61
2.7. Подход с использованием частично-определенного синтаксиса 63
2.7.1. Предпосылки создания. 63
2.7.2. Схема алгоритма. 64
2.7.3. Эксперименты и результаты 67
2.7.4. Выводы 69
2.8. Классификация полей с нефиксированным текстовым представлением 70
2.8.1. Признаки и функции выделения признаков 71
2.8.2. Построение первичного классификатора 72
2.8.3. Сравнение функций выделения признаков 73
2.8.4. Задача с неизвестными классами 74
2.8.5. Сглаживание 75
2.8.6. Проблема зависимости признаков 76
2.8.7. Реализация и выводы 79
2.9. Выводы 79
3. Внедрения и особенности технической реализации 82
3.1. Система массового ввода структурированных документов 82
3.1.1. Обзор системы 82
3.1.2. Стадии технологической цепочки ввода документов 82
3.1.3. Основные компоненты системы 87
3.2. Подсистема контекстной обработки 92
3.2.1. Назначение подсистемы 92
3.2.2. Структура подсистемы 92
3.2.3. Процесс создания функций контекстной обработки 95
3.3. Внедренные проекты и особенности технической реализации 102
3.3.1. Ввод документов пенсионного страхования 102
3.3.2. Ввод анкет школьников и студентов 107
3.3.3. Ввод банковских документов. 108
3.3.4. Ввод отгрузочныхразнадядок в ОАО "Сибнефть" 109
3.3.5. Ввод счетов-фактур в Магнитогорском Металлургическом Комбинате 777
Заключение. Выводы 113
Список литературы
- Дискретный процесс управления
- Понятие грамматики. ГрамматикаХомского
- Классификация полей с нефиксированным текстовым представлением
- Процесс создания функций контекстной обработки
Введение к работе
Актуальность темы исследования
В настоящее время системы массового автоматизированного ввода деловых документов и форм широко используются в сфере информационных технологий Ввод документа подразумевает его сканирование с бумажного носителя, сортировку, распознавание, верификацию, маршрутизацию и т п В рамках процесса идентификации и распознавания структурированного документа контекстная обработка является одним из ключевых этапов Если в конце 80-х и начале 90-х годов основные усилия разработчиков программ оптического распознавания текста (OCR) были направлены на повышение точности распознавания "гладкого" текста, то в последние годы все более актуальным свойством систем автоматизированного ввода информации с отсканированного графического образа становится возможность "понимания" структуры бумажного документа и создания адекватной электронной модели В частности, важным элементом описания структуры документа является задание синтаксических ограничений на его содержание.
Современные методы оптического распознавания достигли такого качества, которое вряд ли может быть улучшено существенно без использования информации о контексте распознавания Как правило, поля ввода на формах имеют определенную синтаксическую структуру, либо серьезные семантические связи с другими полями Информацию такого рода необходимо использовать в процессе распознавания для получения качественно более высоких результатов Известные подходы контекстной обработки включают статистические и лингвистические методы, основанные на скрытых марковских моделях, нейронных сетях, п-граммах над символами, словами и частями речи, конечных автоматах, алгоритмах нечеткого отображения строк Также применяются методы, использующие внешнюю семантическую информацию, комбинированные методы и методы, основанные на эвристиках
Основной качественной характеристикой при вводе документов с бумажного носителя является скорость ввода В промышленных системах доля автоматически вводимых полей составляет 70-90% Более высокий процент достигается редко -реальные документы, как правило, имеют дефекты, привнесенные при печати и сканировании, помарки при ручном заполнении полей Для профессионального оператора среднее время, затрачиваемое на проверку поля обычно в 1 5-2 раза больше чем при последовательном чтении и вводе текстового значения В связи с этим, если для подтверждения предъявляется более 50% полей, скорость автоматизированного ввода сравнима с вариантом ручного ввода Учитывая, что вариант автоматизированного ввода использует более дорогостоящие технические средства,
0$
системы с долей автоматической обработки менее 60-70% обычно становятся неэффективными Априорное знание синтаксической структуры поля позволяет существенно сократить количество ошибок распознавания, а также уменьшить число правильно распознанных полей с признаком сомнительности, тем самым увеличивая скорость Таким образом, синтаксические методы контекстной обработки в целом могут существенно повысить эффективность промышленных систем ввода деловых документов, а задача разработки таких методов является весьма актуальной
Предмет работы
Предметом диссертации является анализ и изучение существующих методов контекстной обработки полей ввода на формах, построение новых методов и алгоритмов основанных на синтаксическом описании распознаваемого поля В работе приведена оценка повышения производительности систем массового ввода структурированных документов при использовании данных методов, являющаяся следствием повышения качества распознавания полей ввода
В рамках диссертации проводится исследование и разработка методологических основ, а также конкретных моделей, методов и средств для решения задач
моделирования структуры полей ввода на документах с точки зрения задачи распознавания и контекстной обработки,
автоматической коррекции результатов распознавания с учетом синтаксической и семантической структуры поля,
автоматического определения достоверности результатов распознавания полей на структурированных документах в задачах ввода стандартных форм,
локализации недостоверных фрагментов распознанного поля,
нормализации распознанного значения,
классификации значений полей ввода на формах,
практической реализации алгоритмов контекстной обработки в рамках систем автоматизированного ввода деловой информации
Цель работы
Целью диссертации является разработка универсальных синтаксических методов и алгоритмов контекстной обработки полей ввода на структурированных документах и анализ их качественных характеристик Также целью является комплексное рассмотрение задачи контекстной обработки - классификация типов полей ввода, изучение, построение и сравнение методов, пригодных для улучшения качества их распознавания Практическая цель работы заключается в реализации подсистемы контекстной обработки, использующей алгоритмы и методы, предложенные в работе, к решению практических задач автоматизированного ввода деловой информации в рамках системы Cognitive Forms, далее по тексту - Системы
Методы исследования
Теоретические исследования основываются на методах теории формальных языков и грамматик, математической статистики, теории вероятностей, системного анализа, теории оптимального управления, методах математического моделирования и многокритериальной оптимизации При практической реализации подсистемы контекстной обработки использованы принципы объектно-ориентированного программирования
Научная новизна
Новизна предложенных в диссертации подходов к обработке результатов распознавания полей ввода состоит, в создании универсальных алгоритмов синтаксической обработки, принимающих полное либо частичное грамматическое описание поля в качестве параметра Разработан специальный метаязык синтаксического описания множества допустимых текстовых значений на основе предложенной автором PDS-грамматики, определяемой при помощи нотации Бэкуса-Наура Это позволило в рамках единой алгоритмической схемы обрабатывать широкий спектр полей с учетом специфики их структуры При этом, несмотря на независимость алгоритмического ядра от особенностей конкретных полей ввода, обеспечена возможность использования специальных знаний, что существенно улучшает качество контекстной обработки. Кроме того, в диссертации задача контекстной обработки полей ввода рассмотрена комплексно - приведена математическая постановка задачи, описана классификация типов полей, встречаемых на формах, и приведен обзор алгоритмов для обработки указанных классов полей
Практическая ценность и апробация работы
В диссертации разработан ряд эффективных и универсальных алгоритмов контекстной обработки полей ввода. Их применение к решению практических задач позволило создать надежную высокопроизводительную систему автоматизированного ввода структурированных документов
За счет использования универсальных синтаксических методов Система работает с большим количеством типов полей, структура которых имеет различную степень жесткости Наличие единых средств синтаксического описания при помощи PDS-грамматики и синтаксических диаграмм позволило разработать специальные алгоритмы обработки конкретных типов полей в сжатые сроки При этом процедуры обработки различных полей ввода используют единое алгоритмическое ядро Заложенные в синтаксических алгоритмах идеи по их практической реализации позволяют использовать код повторно и строить галереи стандартных функций отображения синтаксических атомов на результаты распознавания поля, представленные АР-сетями
Особое внимание при реализации уделено эффективности и надежности Разработанные алгоритмы позволяют настраивать систему ввода на заданный уровень надежности, достоверности и скорости ввода
Результаты исследований подтвердили, что использование синтаксических алгоритмов дает качественно высокие результаты и позволяет строить системы ввода документов с малым числом ошибок, а также минимизировать общее время ввода Реализация и внедрение результатов работы. Результаты диссертационной работы были использованы при создании подсистемы контекстной обработки, являющейся частью промышленной системы автоматизированного ввода документов Cognitive Forms На основе алгоритмов представленных в работе были реализованы и введены в эксплуатацию проекты, среди которых
ввод документов персонифицированного учета в Московском и Санкт-
петербургском отделениях Пенсионного фонда России,
ввод платежных документов в Сбербанке РФ и других коммерческих банках,
« ввод отгрузочных разнарядок для ОАО "Сибнефть",
ввод анкет школьников и студентов, анкет-заявок на изготовление "Социальной карты москвича",
ввод счетов-фактур, договоров, актов, накладных и товаросопроводительных документов в Магнитогорском металлургическом комбинате
Доклады на научных конференциях и семинарах. Основные положения и результаты диссертационной работы докладывались и обсуждались на ряде международных научных конференций в России и за рубежом, среди них
6-ая Международная конференции «Распознавание образов и анализ изображений новые информационные технологии» Великий Новгород, 2002,
The International Conference on Machine Learning, Technologies and Applications (MLMTA'03), 2003, USA,
6th German-Russian Workshop on Pattern Recognition and Image Understanding (OGRW-6), 2003,
The International Conference on Machine Learning, Technologies and Applications (MLMTA'04), 2004, USA
Кроме того, подходы, отраженные в работе, неоднократно представлялись на семинарах Института системного анализа РАН и Института проблем информатики РАН
Публикации
По теме диссертации автором опубликовано одиннадцать работ Шесть из них опубликованы в рецензируемых научных изданиях, рекомендуемых ВАК
Структура и объем работы
Дискретный процесс управления
Методы динамического программирования используются в таких научных областях, как оптимальное управление, дискретная математика (алгоритмы на графах), экономико-математическое моделирование.
Алгоритмы, основанные на динамическом программировании, широко применяются в задачах контекстной обработки результатов распознавания, например, методах связанных с коррекцией неверно распознанных слов, при использовании статистических моделей языка. Укажем работы, использующие динамическое программирование в области контекстной обработки результатов распознавания, а также в смежных областях.
Первым применил методы динамического программирования к задаче постобработки распознанного текста Вагнер [Wag74] используя алгоритм Левенштейна для коррекции ошибок в словах, далее в совместной работе с Фишером [WF74] они обобщили используемые методы для коррекции текстов допускающих несколько ошибок в слове.
Отдельным вопросом при использовании метода динамического программирования остается вопрос метрики при вычислении расстояния между словами. Выбор метрики часто зависит от характера ошибок распознавателя. Кроме распространенных метрик, таких как расстояние Левенштейна [Лев65Ь], расстояние редактирования, используются метрики, допускающие перестановку соседних букв в качестве базовой операции [Kim99], фонетические замены. Также большое количество работ посвящено настройке весов операций при использовании обобщенного расстояния Левенштейна для конкретных прикладных задач. К работам, использующим различные метрики можно отнести [LV75], [WCh76], [Oku76].
Методы нечеткого поиска текстовых подстрок, основанные на динамическом программировании, переносимы в смежные области. Например, с их помощью осуществляется поиск вирусов в цепочках ДНК, проводится сравнение хроматограмм при спектральном анализе газов, производится поиск искаженных сигналов в речевом потоке в задачах распознавания речи [SK83].
Работа [Муе95] посвящена нечеткому отображению текстовой строки на контекстно-свободную грамматику. В данном случае ищется минимальное расстояние от заданной текстовой строки до ближайшей строки порождаемой грамматикой. Задача по своей тематике близка к задаче контекстной обработки, в случае, если структура поля полностью описана в виде синтаксических диаграмм, см. п. 2.6.
В пункте 2.5 рассматривается предложенный Постниковым [ПосОІ] алгоритм MCHSR, основанный на технике динамического программирования, реализующий поиск фрагмента текста в АР-цепи. При этом искомый фрагмент текста не обязательно должен начинаться или заканчиваться одновременно с началом или концом распознанного фрагмента.
Также в работе рассматривается обобщение данного алгоритма для поиска наиболее подходящего значения по лексикографически упорядоченному словарю, в этом случае в алгоритм внесен ряд оптимизаций, дающий возможность работать со словарями, состоящими из десятков тысяч значений. Следует отметить, что алгоритм MCHSR является базовым "кирпичиком" для более высокоуровневых синтаксических и классификационных алгоритмов описанных в главе 2. Интересный алгоритм отображения словаря на АР-цепь описан в работе [СММ99]. В данном случае словарь упакован в виде дерева, вершины которого со держат символы, алгоритм находит оптимальное решение, которое одновременно укладывается как в словарное дерево, так и в АР-цепь.
Марковские модели являются средством моделирования процессов и распознавания образов. Они позволяют учитывать пространственно-временные характеристики сигналов, и получили широкое применение в задачах обработки сигналов, распознавании речи, изображений лиц и т.д.
Скрытые марковские модели также широко используются в области контекстной обработки распознанного текста, обзор работ по данной тематике приведен в п. 1.3.2. Задача интерпретации АР-цепи в соответствии с заданным синтаксисом близка к задаче интерпретации речевого потока в соответствии с СММ. Действительно, задачи схожи - имеется линейный объект, такой как речевой поток или распознанная строка текста, интерпретируемый в соответствии с заданной грамматикой. В случае обработки распознанного текста потоком является АР-цепь - набор знакомест с альтернативами распознавания, см. рисунок 6.
Следует отметить, что часто в задаче распознавания речи используется высокоуровневый синтаксис, задаваемый, например, в форме БНФ, существуют стандарты его описания, например, Speech Recognition Grammar Specification, разработанный консорциумом W3C, см. [SRG04].
Грамматики и способы их задания описаны в главе 2. В синтаксических методах контекстной обработки, грамматика задается как в виде синтаксических диаграмм (см. п. 2.6), так и при помощи нотации Бэкуса-Наура (см. п. 2.7).
Введем понятие скрытой марковской модели. Рисунок 1. Пример схемы скрытой марковской модели Скрытой марковской моделью назовем пятерку Я = S, У,А,В,л . S = {S,},0 i N - конечный набор состояний модели. На рисунке 1 состояния соответствуют вершинам графа. СММ изменяет свое состояние в дискретные моменты времени г=0,1,... В каждый момент времени система находится в строго определённом состоянии. Обозначим состояние СММ в момент времени t через qt. V = {vk},0 k M - конечный набор символов, порождаемых СММ. A = {аЛ, О і, J N - распределение вероятностей переходов между состояниями, здесь а у = p(qt=Sj\ qtA = S,) - вероятность перехода из состояния S, в состояние Sj В = {bjk} - распределение плотностей вероятностей для каждого состояния S,. При переходе в каждое состояние генерируется наблюдаемый символ, который соответствует физическому сигналу с выхода моделируемой системы. Обозначим символ, сгенерированный в момент времени / через о,. Символ в состоянии qt = S, в момент времени / генерируется с вероятностью bJk = p{ot =vk \qt = Sj).
В реальных процессах, как правило, последовательность состояний является скрытой от наблюдения и остаётся неизвестной, а известен только выход системы - последовательность наблюдаемых символов 0 = охог...от. Поэтому такие модели называют скрытыми марковскими моделями.
Модель X с настроенными параметрами А,В,її используется для генерирования последовательности наблюдений. Для этого случайно, в соответствии с начальными вероятностями ті выбирается начальное состояние, затем на каждом шаге вероятность В используется для генерации наблюдаемого символа, а вероятность А - для выбора следующего состояния.
В задачах классификации (см. п.п. 1.6, 2.4.2) скрытые марковские модели применяются следующим образом. Каждому классу С, соответствует своя модель Л. Распознаваемый образ представляется в виде последовательности наблюдений О. Затем для каждой модели Л вычисляется вероятность того, что эта последовательность могла быть сгенерирована именно этой моделью. Модель Лі, получившая наибольшую вероятность, считается наиболее подходящей, и образ относят к классу С,.
Понятие грамматики. ГрамматикаХомского
Обычно в задачах классификации используется понятие признака. Признак (атрибут) -это некоторая характеристика образца, возможно, не имеющая физической природы. Признак может принимать значения из некоторого множества А. В случае А = {0,1} признак называется бинарным. Должна быть определена функция выделения признака a: Q. — Р , которая по образцу выдает вероятностное распределение на множестве значений данного признака. В случае бинарного признака, т.е. принимающего значения 0 или 1, функция выделения выдает вероятность (либо оценку) того, что признак присутствует в образце а(сй) = р. В случае, если р Є {0,1}, функция выделения признака а называется однозначной. Серьезными подзадачами классификации являются задачи определения множества признаков, а также выделения их независимого подмножества. При классификации текстового значения, образец (О соответствует результату распознавания текста, т.е. представляет собой АР-сеть. В некоторых случаях информация об альтернативах распознавания в целях оптимизации по скорости не используется, тогда образец СО - это строка текста. Описания Fi класса С,- - это, как правило, нормальные текстовые значения, либо уникальный код класса, например, соответствующий коду в некоторой базе данных.
Пример. Поле "Наименование товара" на отгрузочных разнарядках см. п.3.3.4, содержит текстовое описание товара. Товар может быть указан различными способами. Например, бензин неэтелированный 95 может быть записан как "н/э АИ95", "Неэт. бензин АИ 95", бенз. неэтил. 95" и т.д. В данном случае требуется поставить в соответствие результату распознавания номер товара в заданной базе данных.
В системах распознавания форм возникает задача не только распознать значение поля с учетом структурных ограничений, но также привести распознанный результат к нормальной форме. Множество значений в нормальной форме может быть задано, например, при помощи грамматики, тогда требуется для распознанного значения подобрать наиболее близкое значение из множества нормальных. В случае, если множество нормальных значений задано в виде списка, задача нахождения нормальной формы схожа с задачей классификации текстового фрагмента (см. п.2.4.2).
Пример 1. Распознанную дату требуется привести к типу, совместимому с типом DATE в языке SQL для того, чтобы впоследствии экспортировать распознанное значение в БД.
Пример 2. Распознанный адрес необходимо привести к формату БД КЛАДР Федеральной налоговой службы России, в котором адрес представлен в виде семи реквизитов: регион, город, населенный пункт, улица, дом, корпус, квартира. В нормальном представлении данные реквизиты следуют друг за другом в указанном порядке через запятую.
Очень важная задача - оценить степень надежности распознанного значения. Процесс ввода документа состоит из этапов распознавания и верификации. При этом оператор верифицирует только те поля, на которых система распознавания поставила флаг сомнительности. Обычно задана цена двух типов ошибок: "ложного срабатывания" и "пропуска цели". "Ложное срабатывание" - это ошибка, при которой на правильно распознанное значение система распознавания установила флаг сомнительности. При этом оператору нужно лишний раз посмотреть на поле и убедиться, что оно распознано правильно. Это занимает от 5 до 20 секунд. "Пропуск цели " - это, как правило, более грубая ошибка системы, когда на неправильно распознанное значение система распознавания не установила флаг сомнительности. При этом неправильно распознанное значение попадает на более поздние стадии ввода документа. Иногда, например, при распознавании суммы платежа, ошибки второго рода совершенно недопустимы. Как правило, на их устранение требуется существенное время - от 10 минут до нескольких часов. Для некоторых полей ошибки 2-го рода не столь
Спецификация формата базы данных "КЛАДР" ГНИВЦ ФНС РФ приведена по адресу http://www.gnivc.ru в разделе "Информационное обеспечение". критичны. При распознавании полей ввода зачастую имеется возможность настраивать пороги сомнительности для ошибок 1-го и 2-го рода.
Формально. Пусть имеется множество алгоритмов F, каждый элемент которого ставит в соответствие исходной АР-сети финальное текстовое значение и флаг сомнительности, определяющий степень надежности текстового значения, т.е. F = {/: ARN — А х {0,1} }, где ARN— множество АР-сетей, А - множество строк текста в алфавите А. Алгоритм/ принимает на вход АР-цепь и выдает на выходе текстовое значение вместе с флагом сомнительности. Пусть заданы цены ошибок 1-го и 2-го рода Р1 и Р2 соответственно. Пусть
Ql (/) - количество ошибок 1 рода которое выдает алгоритм / є F на тестовом наборе исходных данных WT, т.е. количество случаев, когда в результате работы алгоритма / получена правильная текстовая строка, но ошибочно выставлен флаг сомнительности, а Q2 (/) - количество ошибок 2-го рода, т.е. когда получена не правильная текстовая строка, и при этом флаг сомнительности не выставлен. Задача состоит в нахождении такого алгоритма f ., для которого функция Q(f) = PXQX (/) + P2Q2 (/) минимальна.
При выставлении флага сомнительности на распознанное поле возникает необходимость не только проставить флаг, но и локализовать ненадежные (сомнительные) фрагменты поля. Это сильно помогает оператору при верификации полей с большим количеством символов. Например, если флаг сомнительности выставляется из-за низкой оценки одного символа, то вряд ли имеет смысл верифицировать все поле целиком. Достаточно предъявить оператору только сомнительный символ. Часто в системах распознавания форм оператору предъявляются только символы, оценка которых ниже некоторого порога. При использовании контекстной обработки поля, сомнительные фрагменты указываются не только исходя из качества распознавания, но также исходя из структуры поля - синтаксиса, семантики или других контекстных соображений.
Например, если номер квартиры при распознавании поля "Почтовый адрес" состоит из пяти уверенно распознанных символов, то, несмотря на хорошее качество распознавания, все равно логично будет поставить сомнительность на данный фрагмент. Исходя из семантических соображений, маловероятно, что в доме имеется десять тысяч квартир.
Классификация полей с нефиксированным текстовым представлением
Классификатор был реализован в рамках системы массового ввода документов Cognitive Forms. В 1999-2001 г.г. и был успешно применен при вводе и обработке анкет школьников и студентов в Москве с целью регистрации категорий лиц, пользующихся льготами при проезде в метрополитене. При вводе анкет классифицировались средние и высшие учебные заведения города Москвы. Также классификатор использовался при обработке поля "Наименование товара" в проекте по вводу отгрузочных разнарядок для ОАО "Сибнефть". Подробнее данные внедрения описаны в п.п. 3.3.2,3.3.4. Всего при использовании классификатора было введено более 2.000.000 документов.
Классификатор показал высокое качество на тестовом наборе документов. Для поля "Наименование учебного заведение" оно составило около 90%. Серьезным плюсом использования классификатора является наличие полностью автоматической процедуры обучения, также имеется возможность динамически дообучать классификатор в процессе работы. Использование техники сглаживания дает возможность обучать классификатор на недостаточно репрезентативной выборке. Также стоит отметить, что существенное улучшение качества работы дает процедура поиска зависимых признаков и построения классов эквивалентности словосочетаний. Кроме того, процедура селекции замен словосочетаний с учетом их веса позволяет использовать зашумленную обучающую выборку.
Реализация классификатора в виде отдельных компонент допускает использование нестандартных функций выделения признаков из образца и функций построения набора признаков по обучающей выборке для решения специальных задач.
Во второй главе были рассмотрены эффективные синтаксические алгоритмы предложенные автором для контекстной обработки таких полей как "Почтовый адрес", "Сумма прописью", "Назначение платежа", "Наименование организации". Алгоритмы реализованы в программном комплексе по массовому вводу форм Cognitive Forms. На данный момент с их использованием обработаны десятки миллионов документов. Синтаксический подход, представленный в данной главе существенно улучшил как качество, так и надежность распознавания полей со сложной структурой. Например, качество распознавания почтовых адресов на пенсионных анкетах увеличилось с 55% до 90%. Благодаря этому, общее время обработки документа значительно сократилось.
Синтаксический подход, с одной стороны, является общим, поскольку содержит в своей основе универсальное ядро, позволяющее применять его к широкому кругу задач. С другой стороны, переборная схема работает с синтаксическим описанием конкретного поля, тем самым привносится довольно узкий контекст задачи, используя существенные ограничения на структуру поля. Также следует отметить, что описанные алгоритмы позволяют подключать специальные семантические знания, например базы данных адресов, при распознавании почтового адреса, не уходя от основной схемы алгоритма. Фактически синтаксический подход является уникальным в своем классе, совмещая общее ядро алгоритма с возможностью использования специальных методов постобработки в рамках единой алгоритмической схемы.
Также в настоящей главе был рассмотрен подход, использующий частично определенный синтаксис, который применяется в тех случаях, когда поле не может быть описано грамматикой полностью. В этом случае грамматически описываются только набор типичных для данного поля текстовых конструкций. Описание производится при помощи разработанной PDS-грамматики, см. п.2.2.5. PDS-грамматика позволяет оперировать сравнительно высокоуровневыми синтаксическими примитивами, такими как число, статический текст, словарь. В главе приведены результаты сравнения синтаксического подхода и подхода основанного на частично-определенном синтаксисе (PDS-подхода). Сравнение проводилось на примере обработки рукопечатного поля "Почтовый адрес". Качество работы синтаксического подхода составило примерно 90% правильно распознанных полей, а PDS-подхода - примерно 85%. При этом настройка PDS-алгоритма заняла гораздо меньше времени, так как алгоритм с частично-определенным синтаксисом использует процедуру автоматического обучения, т.е. при наличии необходимого объема данных не требует описывать структуру поля вручную. Данный фактор очень важен для быстрой разработки и настройки алгоритма.
Какой из синтаксических подходов использовать, зависит от специфики задачи и условий разработки. Если требуется быстро разработать алгоритм с относительно хорошим качеством распознавания, следует использовать подход, основанный на частичном синтаксисе. Если же, напротив, требования к качеству распознавания чрезвычайно высоки, а также имеется достаточное время, то предпочтительнее использовать синтаксический подход, который, во-первых, является более гибким, а во-вторых, позволяет использовать семантику.
В конце главы описан предложенный автором метод, позволяющий успешно решать задачи классификации таких текстовых полей ввода, как "Наименование учебных заведений", "Наименование товаров", "Наименование организаций". Метод включает полностью автоматическую процедуру обучения, дает возможность динамического дообучения классификатора в процессе работы. Использование техники сглаживания и классов эквивалентности словосочетаний позволяет обучать классификатор на недостаточно репрезентативной и за-шумленной выборке образцов. Классификатор реализован в виде отдельных компонент, до пускает использование нестандартных функций выделения признаков из образца и функций построения набора признаков на основании обучающей выборки
Предложенные в главе алгоритмы являются универсальными в том смысле, что ядро алгоритма не привязано к конкретному полю, специфика поля передается алгоритму лишь в качестве параметра, например, описания в виде набора синтаксических диаграмм. При этом рассмотренные алгоритмы позволяют решать целый пласт задач контекстной обработки, которые решаются в настоящий момент специальными методами совершено не применимыми к аналогичным задачам.
Помимо этого, в главе приведена классификация типов полей встречающихся на формах и предложены методы для их обработки, введены базовые понятия теории формальных языков, при помощи которых определена PDS-грамматика. 3. Внедрения и особенности технической реализации.
В предыдущей главе были рассмотрены методы и алгоритмы, предложенные автором для контекстной обработки широкого спектра полей ввода. На их базе была реализована подсистема контекстной обработки, позволяющая в короткие сроки реализовывать функции для обработки конкретных типов полей. На основе описанных алгоритмов, имеется возможность разрабатывать специальные и комбинированные методы и подключать их в качестве отдельных модулей к подсистеме контекстной обработки, которая является частью системы массового ввода структурированных документов Cognitive Forms [АПШ02]. В третьей главе приведено описание подсистемы контекстной обработки, реализованной автором в рамках системы Cognitive Forms, и дан общий обзор самой системы. В конце главы указаны примеры внедрений рассматриваемых в диссертации алгоритмов.
Процесс создания функций контекстной обработки
В частности это касается случая, когда бланки изготовляются несколькими тиражами и имеют небольшие (1-3 мм) расхождения в размерах и расположении элементов. Так как вводимые документы имеют жестко фиксированное расположение элементов, наличие версий затрудняет идентификацию бланков на этапе сортировки и распознавания.
Изменения правил заполнения документа. Отдельной проблемой является частое изменение правил заполнения документов, например, связанные с изменением налогового законодательства. В связи с этим присутствует необходимость оформлять правила логического контроля, используемые на этапе контекстной обработки, в виде отдельных модулей.
Разработанный в рамках системы и реализованный в данном проекте подход позволил автоматизировать процесс комплектации документов из непрерывного потока страниц, полностью исключив предварительную ручную сортировку и минимизировав необходимые вмешательства со стороны оператора в нештатных случаях. С практической точки зрения это позволило максимально использовать возможности скоростных сканеров, имеющих большой объем устройства автоматической подачи документов.
Технически данная проблема была решена следующим образом. При обработке пакета документов, в автоподатчик загружается максимальный объем, в котором документы следуют один за другим, в том виде как они поступили на обработку - возможно, перевернутые на 180 градусов, без разделяющих белых страниц. Несколько модулей сортировки и комплектации пакетов работают в автоматическом режиме параллельно с процессом сканирования (на рисунке 35 - «станция сортировки и комплектации»). В процессе работы модули идентифицируют типы страниц и распознают поля ввода, контролирующие комплектность документа. При распознавании данных полей были задействованы алгоритмы контекстной обработки. Имея синтаксическое описание структуры пакета, определяющее возможные варианты следования типов страниц, а также описания полей, контролирующих комплектность, система автоматически идентифицирует как начало нового многостраничного документа, так и его целостность.
Модули работают в автоматическом режиме, безостановочно. Корректно скомплектованные документы ставятся в очередь на распознавание. В случае если документ скомплектован некорректно, он отсылается на рабочее место корректирования результатов комплектации. Оператор анализирует причину, по которой документ не корректен. В некоторых случаях может требоваться ручной пересчет документов в пакете. После выяснения причины, пакет документов может быть либо отсканирован повторно, либо отбракован, либо поставлен в очередь на распознавание в том виде, в котором был изначально отсканирован.
В результате из непрерывного потока документов, сканируемого с максимальной для данного сканера скоростью, после этапа автоматической сортировки и комплектации на этап распознавания подаются корректно скомплектованные пакеты документов. Отклонения в структуре документов быстро фиксируются, так как проблема выявляется практически сразу после того, как отсканирован пакет, а рабочие места сканирования и корректирования расположены рядом и могут обслуживаться одним оператором.
При распознавании анкет Пенсионного Фонда России - форм АДВ-1, СЗВ-1, СЗВ-1а были использованы алгоритмы, предложенные автором, в частности синтаксический подход, см. п.2.6. В процессе ввода, анкеты сканировались с разрешением 200dpi и сохранялись в формате TIFF с использованием сжатия CCITT Group 4.
Анкета АДВ-1, см. рисунок 36, представляет собой форму, разработанную для рукопе-чатного заполнения. Она содержит ряд полей ввода, имеющих определенную синтаксическую структуру. Синтаксический подход был применен для обработки таких полей, как "Почтовый адрес", "Дата рождения", "Дата заполнения", "Серия и номер паспорта", а также поля "Кем выдан паспорт". Из перечисленных полей "Почтовый адрес" и "Кем выдан паспорт" имеют наиболее сложную структуру - синтаксические диаграммы для них состоят из 45 и 29 вершин соответственно. Синтаксический подход показал хорошие результаты в обоих случаях. Количество правильно распознанных полей "Почтовый адрес" составляет около 90%, более подробные результаты приведены в таблице 2. Примеры руко-печатного заполнения поля "Почтовый адрес" приведены ниже на рисунке 37.
Что касается временных характеристик алгоритма, то на компьютере Pentium IV 1500 MHz среднее время обработки почтового адреса составило примерно 0.16 сек. при средней длине текста 47 символов. При этом общее время распознавания анкеты АДВ-1 составило 1.4 секунды.
Следует отметить, что при обработке анкет пенсионного фонда использовались контекстные функции, одновременно обрабатывающие несколько полей. Например, на формах СЗВ-1, СЗВ-1а, СЗВ-3, СЗВ-За имеются группы полей, содержащие индивидуальные сведенья о стаже работы застрахованного лица за отчетный период, см. рисунок 38. Каждая группа состоит из 12 полей, которые содержат информацию о территориальных и особых условиях труда, трудовом стаже и выслуге лет. Поля взаимосвязаны, множество допустимых значений регулируется при помощи набора специальных правил, разработанных ПФ РФ.
Для контекстной обработки полей данной группы был разработан следующий механизм. Каждое поле группы предварительно распознается отдельно, при этом допускается использование функций локальной контекстной обработки, т.е. можно трактовать результат распознавания поля как значение из определенного словаря, число определенного формата и т.д. После этого более высокоуровневый контекстный алгоритм получает набор АР-цепей, соответствующих полям группы. Для каждой АР-цепи отбирается фиксированное число вариантов, соответствующих путям-кандидатам в АР-цепи с наивысшей оценкой. Далее функция контекстной обработки рассматривает варианты комбинаций отобранных значений в порядке убывания их качества и для каждой комбинации значений производит проверку на предмет соответствия правилам заполнения. Если найден допустимый вариант, он считается результатом работы алгоритма. Данная схема позволила устранить на этапе контекстной обработки порядка 40% ошибок в полях указанной группы.
