автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Модели и методы извлечения знаний из текстов на естественном языке

На правах рукописи

СИМАКОВ Константин Васильевич

МОДЕЛИ И МЕТОДЫ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ТЕКСТОВ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ

Специальность 05 13 17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук профессор В.Н. Голубкин

Москва - 2008

Работа выполнена на кафедре «Компьютерные системы и сети» (ИУ-6) факультета «Информатика и системы управления» (ИУ) Государственного образовательного учреждения высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» (МГТУ имени Н Э Баумана)

Научный руководитель: Официальные оппоненты

доктор технических наук, профессор Голубкин Виктор Николаевич

доктор физико-математических наук, профессор

Осипов Геннадий Семенович

кандидат технических наук Шабанов Владислав Игоревич

Ведущая организация. ЗАО «Концерн ВНИИНС»

(Всероссийский научно-исследовательский институт автоматизации управления в непромышленной сфере)

Защита состоится 13 марта 2008 г в _ часов _ минут на

заседании диссертационного совета Д 212 141 10 по защите диссертаций при Московском государственном техническом университете имени Н.Э Баумана по адресу 105005, г Москва, ул 2-я Бауманская, д 5

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета имени Н.Э Баумана- по адресу 105005, г Москва, ул 2-я Бауманская, д 5

Ученый секретарь

Диссертационного совета Д 212.141 10 кандидат технических наук, доцент

Иванов С Р

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Проблеме извлечения посвящено множество зарубежных работ, объединяемых в единый класс задач извлечения информации из текстов Извлекаемая информация представлена структурами данных, поля которых заполняются текстовыми фрагментами Недостатком зарубежных разработок является сильная зависимость от конкретной грамматики языка Среди отечественных работ известны только две законченные системы компаний RCO и Yandex, имеющие крайне ограниченное применение, поскольку не существует простого способа их адаптации к произвольной предметной области Более того, в современных работах нет сведений о системах сопоставляющего анализа, находящихся в эксплуатации

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

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

Правила обоих типов наравне с извлекаемыми структурами данных являются знаниями предметной области Формирование таких правил в существующих отечественных разработках осуществляется вручную, что является причиной сложности настройки системы извлечения

В связи с этим разработка методов автоматизированного составления правил извлечения и правил морфологического анализа является актуаль-

ной задачей, решение которой в общем виде без привязки к конкретному языку в настоящий момент отсутствует

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

1 исследование современных моделей извлечения информации из текстов и методов обучения таких моделей,

2 разработка модели представления знаний, позволяющей эффективно выполнять сопоставляющий анализ текстов,

3 создание модели извлечения знаний из предметно-ориентированных текстов,

4 разработка метода обучения модели извлечения знаний из текстов,

5 создание модели морфологического анализа слов и метода ее обучения,

6 экспериментальная проверка предложенных моделей и методов

Объект и предмет исследования. Объектом исследования являются естественно-языковые тексты как форма представления знаний предметной области Предметом исследования являются процессы автоматизированного выявления и формализации знаний, представленных в форме естественноязыковых текстов

Методы исследования Теоретические исследования проведены с использованием теоретико-множественного аппарата, методов теории вероятностей и теории информации, аппарата логических исчислений При разработке моделей и методов был применен аппарат алгебраических систем, в том числе алгебраических решеток и графов, а также аппарат формальных грамматик и теория автоматов

Научная новизна работы заключается в следующем

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

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

3 Предложена модификация принципа аналогии морфологического анализа текстов, позволяющая существенно сократить объем морфологического словаря и снизить вычислительную сложность алгоритма анализа

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

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

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

Реализация модели извлечения использовалась при разработке

- «Системы семантического контроля текстов редактируемых документов», применяемой для выявления несоответствий в текстах стенограмм заседаний Совета Федерации Федерального Собрания Российской Федерации

- «Интеллектуальной системы выявления и исправления ошибок в почтовых адресах клиентов банка», применяемой для валидации российских почтовых адресов, представленных в текстовой форме

Разработанный метод обучения модели извлечения избавляет эксперта от ручного формирования правил извлечения

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

Кроме приведенных выше систем модель морфологического анализа и метод ее обучения встроены в следующие программные комплексы

- Информационно-поисковая система «Обзор СМИ», эксплуатируемая в Совете Федерации РФ, в рамках которой встроен модуль морфологического анализа для задачи автоматического построения аннотаций

- Комплекс программных средств специального назначения по классификации и кластеризации текстов документов, разработанный и использованный в рамках НИР, выполненной ВНИИНС для МО

Апробация результатов работы Результаты проведенных в диссертационной работе исследований опубликованы в 11 работах, из них в журналах из перечня ВАК - 2 статьи Основные положения работы докладывались и обсуждались

- на 5-ой, 6-ой, 7-ой, 8-ой и 9-ой всероссийской научной конференции «Электронные библиотеки перспективные методы и технологии, электронные коллекции» в 2003, 2004, 2005, 2006 и 2007 годах,

- на научной конференции «Информатика и системы управления в XXI веке» в 2003 году на факультете «Информатика и системы управления» МГТУ им Н Э Баумана

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Диссертация состоит из семи глав, введения, заключения, списка литературы и двух приложений Общий объем диссертации - 267 страниц, включая 88 рисунков и 24 таблицы Библиография включает 116 наименований, из которых 83 иностранных источника

Во введении обосновывается актуальность темы диссертации Формулируется цель и основные задачи работы, характеризуется ее научная новизна

В главе 1 «Постановка задачи извлечения знаний из текстов» дается определение решаемым в диссертации задачам

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

В главе приводится классификация знаний, пополнение которых целесообразно выполнять с минимальным участием эксперта К ним отнесены процедурные знания о языке предметной области (правила словообразования и согласования слов), экземпляры декларативных знаний предметной области и правила их выявления На рис 1 приведена функциональная схема системы извлечения этих знаний _ _

Эксперт-лингвист

,—к. (Тексты!!:

Обучение

г

Эксперт предметной области

-Обученйё~|<-|Текстъ|| <^==

......... "Т___I ! «

'Правила словообразования!- Правипа извлечения \ " .имппиров

п гппй^ I декларативных знании

П|1.1НИ'М .-СИ 11.11 Ш'.ЛНИИ | ппп

~ Лингвистическая^ ~ | подготовка текстов ; >

I Экспертная ¡; {подготовка текстов

Сегментатор

Морфологический Синтактико-семантический

анализ анализ

Рис 1 Функционирование системы извлечения Темными блоками выделены знания, извлекаемые из текстов на каждом из трех крупных этапов формирование правил о языке, формирование правил извлечения и непосредственное извлечение экземпляров На первом этапе человек-эксперт по лингвистике подбирает типовые тексты предметной области Эти тексты пропускаются через процедуру автоматического обучения, которая формирует правила словообразования и согласования слов На втором этапе другой человек-эксперт предметной области выполняет подготовку другого массива текстов Эта подготовка подразумевает явное выделение в текстах экземпляров декларативных знаний предметной области

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

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

В главе 2 «Обзор методов извлечения знаний» проведено исследование современного положения дел в области машинного обучения и извлечения информации из текстов

В области машинного обучения выделено два класса методов, основывающихся на объяснении и на подобии, второй класс отмечен, как наиболее подходящий для поставленных задач

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

- Нет ограничений на итерацию элементов правил снизу и сверху

- Ни одна из существующих систем не позволяет налагать запреты на употребление в тексте отдельных слов или их классов, заданных признаками

- Применяемые методы обучения реализуют покрывающую стратегию, возможности сжимающей стратегии исследованы слабо

- В основном используется формирование правила на основе одного единственного обучающего примера, групповое обобщение не реализовано ни в одной из систем

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

1 В настоящий момент не существует обучаемых моделей извлечения знаний из текстов, не привязанных к конкретному языку, обладающих должным качеством извлечения

2 Необходимо иметь возможность как точной ручной настройки модели, так и автоматической - на основе обучающих примеров Данному требованию в большей степени удовлетворяют символьные модели

3 Модель извлечения должна оперировать с неограниченным числом атомарных признаков, приписываемых словам текста (в том числе морфологических), и не должна привязываться к конкретному синтаксису

4 Чтобы правила извлечения можно было использовать в качестве компонентов более сложных моделей, их синтаксис должен быть предельно простым Должно быть минимизировано количество обязательных предварительных анализаторов

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

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

1 Ус е С Зс/ е О (с,с?)еДсо, где с ив - множества классов и простых свойств классов онтологии, Кс[) - отношение принадлежности свойств классам

2 V/ее,? (/>)ейга, где ^ - множество фреймов, 51 - множество слотов, - отношение принадлежности слотов фреймам

Оба свойства необходимы, т к при извлечении экземпляра фрейма доступными являются лишь значения его слотов, без которых невозможно выявить наличие в тексте целевого экземпляра Для обеспечения наложения схем сформулированы следующие необходимые и достаточные условия 1 У(/>)еДга (*, Г) е => Б1 (с, ) е йсо л 31 Г ) е Иит, где Д5Т - отношение, СВЯзывающее с каждым слотом « область его допустимых значений 1], Ясо -аналогичное отношения для простых свойств классов

с, ¥=с2=> ЗС/(с,,с2)

где Сг(с,,с2) - цепь классов вида с,, .с,, с, такая, что

[31 (с„/)еЛС£л(/,с,+;)еД

цидентности между связями и классами онтологии Классы указанной цепи должны удовлетворять условию \/с: еСг(с,,с2)=>(/->с,), где /->с обозначает тот факт, что одним из классов, на которые наложен фрейм /, является класс с

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

Для обучения морфологического анализатора и модели извлечения предложена единая стратегия обучения (см рис 2)

гпа а „ О _ отношения ин-

< Экземпляры знаний, явно выделенные в текстах

Вербализатор

Человек

Эвристический алгоритм Черный ящик

I Метод конструктивной индукции

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

Рис 2 Схематичное отражение стратегии обучения

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

Описанной стратегии присвоено название «Акцентированная Аппроксимирующая Абстракция» (сокращенно АЗ) Абстракция заключается в том, что в процессе обучения выполняется смена формулировки Исходные знания представлены в виде неявных правил, которыми руководствовался автор при составлении текстов Поскольку о формулировке этих правил ничего не известно, можно считать, что она не удовлетворительна и требуется ее замена В главе 2 такая замена в рамках машинного обучения отнесена к классу дедуктивной абстракции Аппроксимация обусловлена тем, что знания, полученные в результате обучения, не претендуют на точное отражение знаний, которыми руководствовался составитель текстов Акцентированность заключается в том, что в результате обучения отражены только те знания, которые задействованы в выборке наблюдаемых текстов, хотя на самом деле вербализатор может располагать куда большими знаниями о текстах предметной области Выборка наблюдений является своего рода акцентом, позволяющим выполнить вербализацию и обобщить только ту часть знаний, которая отражена в этой выборке

В главе 4 «Разработка модели извлечения экземпляров фреймов» предложена сегментная модель текста тм, которой должен отвечать любой текст, подлежащий обработке, а также модель извлечения фреймовых слотов ЕМ

Модель текста определяется алгебраической системой вида тм=<т,ж,121,»>, позволяющей представлять произвольный текст в виде сцепленных сегментов, где Т - множество текстовых сегментов, ж - множество слов модели, - пустой текстовый сегмент, • - операция сцепления на т Операция • позволяет из произвольной пары текстовых сегментов сформировать новый сегмент, является нейтральным элементом по отношению к операции сцепления

Использование /0 позволяет рассматривать текстовые сегменты разной длины в виде сцеплений из одного и того же числа п сегментов вида г = (;.(г. »гп, что определяет возможность построения текстовых шаблонов (образцов), являющихся основным компонентом правил извлечения Мини-

мальными сегментами являются слова РР, к которым также отнесены знаки препинания Любой текстовый сегмент может быть представлен в виде сцепления слов

Модель извлечения определяется как алгебраическая система вида ЕМ=<У,РЛ,Рс,°,<р>, где V - множество правил извлечения, Р - множество образцов текстовых сегментов, II - множество элементов образцов, р0 -пустой образец, ° - операция сцепления образцов, <р - отношение порядка между элементами образца р<вР Компоненты модели ЕМ обладают следующими свойствами

- Ур, € Р л Vр2 е Р 3/? = р, о р2

- Ре>^Рл\/р^Р^>р = Р0°рлр = р°ре>

- \Л> е V у = рь орс °ра - правила извлечения представляют собой сцепление тройки образцов префиксный рь, извлекающий рс и постфиксный ра

Следствия приведенных свойств модели

- УреР=>ре.У - образец может быть представлен в виде правила

- \/геЯ=>геУ - элемент может быть представлен в виде правила

- VреР=>р = г1° °г„лг, ер - образец представим сцеплением элементов Данные следствия необходимы, чтобы ввести единую для элементов, образцов и правил извлечения функцию покрытия а тхУ {истина,ложь) Функция покрытия аО,у) для любого правила VеУ и любого текстового сегмента IеТ позволяет ответить на вопрос, покрывает ли правило данный сегмент

Чтобы дать интерпретацию функции покрытия для элементов образцов, рассмотрим структуру элемента г, =<с,е,!,,!2 >, где сс(Г - лексическое ограничение элемента, есГ - исключение лексического ограничения, I, и 12

- минимальная и максимальная длина покрытия элемента

Лексическое ограничение с и его исключение е определяют множество слов с\ес=Ж, которые могут встречаться в текстовых сегментах ГсГ, покрываемых элементом г, Значения I, и 12 определяют допустимый диапазон длин текстовых сегментов Тп Функция покрытия а^.г) для элементов и а (/,/>) для образцов имеет вид

Образец Р = г,°г2о о г покрывает сегмент / е г, если геГ может быть представлен в виде сцепления / = • ¡я, так что /,-ый сегмент покрывается соответствующим >;-ым элементом При этом допускается, что некоторые сегменты из г,л2, л„ могут быть пустыми Данный факт позволяет судить об образцах, как о шаблонах фраз, состоящих из элементов, связанных отношением предшествования Функция покрытия для правила извлечения задается следующим образом

(у = рь°рсорал1 = 1ьчсча Те правило покрывает текстовый сегмент а«,у)<=> а(Ч,ръ)Ла(1с,рс)д'е г' если он представим в виде сцепления

трех сегментов I, • / • г„ , каждый из которых

— результат извлечения аса г

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

- УяЗ УуеГ, лЫ еТла^,у) = истина ^-¡еТ, ¡Я^Т, ,

- КЛсК Г„пУ,2=0

В главе также описаны три способа описания лексических ограничений и их исключений в виде множества непосредственно перечисленных слов, в виде объединения орфографических признаков и в виде пересечения морфологических признаков Любой способ описания должен удовлетворять требованию - множество с лексических ограничений должно образовывать алгебраическую решетку а Данное требование необходимо, чтобы существовала возможность обучения модели ЕМ, этот факт сформулирован и доказан в виде теоремы «О существовании и поиске модели извлечения»

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

В главе 5 «Разработка метода обучения модели извлечения» приводится описание метода формирования правил извлечения на основе обучающих примеров Метод следует стратегии АЗ (см рис 2) и реализует второй этап работы системы извлечения (см рис 1) В качестве вербализатора выступает человек-эксперт, выполняющий разметку текстов, формируя тем самым обучающую выборку Метод включает четыре этапа формирование предельно конкретных правил, групповое сжимающее обобщение, унарное обобщение и формирование исключений элементов правил

Все этапы объединяет требование о возрастании функции качества

= где /(у,Тс) = ^ - Р-мера качества извлечения

правила V, Ыу,те) - общее количество извлеченных сегментов правилом V, из которых а(у,Те) - число корректных извлечений, Ир - количество позитивных обучающих примеров, которые должно покрыть в идеале правило V

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

г., а с каждым ребром связано правило у <=г полученное в результате

парного обобщения правил ^ е ¥т и vJ е Ут, вершины которых соединяет данное ребро Граф задан матрицей смежности так, что С[= С[у/,у1] =

Полученный граф анализируется на предмет наличия циклов Для каждой вершины V, графа находится оптимальный цикл С, = у, ук V, такой, чтобы для каждой вершины ук цикла из всех ребер уь=С[ук,у3] графа, инцидентных ей, циклу принадлежало бы ребро V,, = а^тах /3(^,7;)

Комплексный показатель качества правила р(уи,Т,'.) рассчитывается как р{уи,Те)= Кг /(уи,Т) + Кр р(ум)+К5 5^), где /(ум,т~) - Р-мера извлечения правила уи, р(уы) - качество обобщения правила уа, £(ун) - абсолютная степень специфичности правила Мера р(уи) количественно оценивает погрешность обобщения пары правил мк и у, при формировании нового правила уи Мера 5(уи) учитывает количество элементов в правиле и мощности их лексических ограничений так, что чем больше информации заложено в правиле, тем больше значение Числовые коэффициенты Кп Кр и к8 определяют значимость соответствующей составляющей комплексного показателя р(ук„те) При проведении экспериментов коэффициенты выбирались в следующих отношениях КГ>КР>

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

Особенностями предложенного алгоритма являются следующие

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

- группа обобщенных правил, соответствующих вершинам цикла, заменяется не на одно правило, а на целую группу правил, соответствующих ребрам цикла

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

Тем не менее, в основе группового обобщения лежат парные обобщения правил у4 и у,, что сведено к независимому обобщению их образцов Более точно задача обобщения образцов формулируется так имеются два образца р, = г, ог2 о огм и р1 =q,^'q2o одм, необходимо на их основе сформировать множество обобщенных образцов Ру, обеспечив при этом минимальную погрешность обобщения Для решения этой задачи введена матрица соответствий А размерностью ЫхМ, где строкам соответствуют элементы образца р, = г, о г2 ° ° Гу, а столбцам - элементы образца р1=д,°дг<> °дм, при

этом А[1,]] = с,1, где си =с,у с1 - лексическое ограничение, полученное операцией наименьшей верхней границы у решетки лексических ограничений сь, примененной к лексическим ограничениям элементов =< с,,0,1',,^ > и д] =<с, ,0,> исходных образцов С каждой ячейкой также связано значение я(ся) = 1-егг(ся), где егг(ся)= ^Jp(w)- - погрешность обобщения

и-ес, V с} weC|^JCj

с, = с, у с, по решетке СЬ, р(к) - вероятность встретить слово и- в текстах предметной области Далее формирование обобщенных образцов на основе р, и р1 сводится к поиску маршрутов Р = а„а2, ,аь опорных ячеек матрицы, удовлетворяющих требованиям

- \/а,,а„,еР а, = А[г1^,] = А[ц^2] => (г, < 12 л^ < ]2),

- Уа, еР а1=А[к,1]^>з{са)>0

Анализ матрицы сводится к поиску опорных маршрутов длины 1<ь<тт{ы,м) наиболее близких в геометрическом смысле к эталонному маршруту той же длины

Эталонный маршрут размещен на диагонали матрицы так, что его ячейки равноудалены друг от друга (см рис 3) Близость маршрутов Ра и Р рассчитывается по формуле

ф

Гч

—

—

к— л

® эталонный маршрут о опорный маршрут Рис 3 Маршруты матрицы А

= '.»,*) яО/.Л-).

где

Н(1„г2) = -

функция, подобная энтропии, позволяющая оценить геометрическую близость для произвольной пары ячеек матрицы, чем сильнее отличаются индексы I, и 12, тем ближе значение н{1„12) к нулю Элементы обобщенного образца формируются на основе ячеек найденного опорного маршрута двумя правилами с?^,?,) и с2[ '*""° °Гк~

- О, = ((1=<С,0,11,12>) с = А[к,1]л11=тт(1к,,1'1)л12=тах{1к2,1'2)

к-1 1-1 { к-1 1-1 Л ( к-1 1-1 Л

- в2 ={(!=< с,0,1„12>) с = УС, V у сгл!1=тт\ л/,=1иах ЭД, Е'Л

Правило С, формирует элемент нового образца на основе элементов гк е р: и д, е р1 исходных образцов, соответствующих опорным ячейкам матрицы Правило С2 формирует элемент нового образца на основе фрагментов исходных образцов гт1 о °гк_, а р1 и од1ч а р}, размещенных между парами элементов, соответствующих двум соседним опорным ячейкам маршрута Глава 6 «Разработка модели морфологического анализа и метода ее обучения» посвящена описанию модифицированного принципа аналогии и разработанной на его основе обучаемой модели морфологического анализа

Данная разработка обусловлена необходимостью качественного морфологического анализа текстов на третьей стадии работы системы извлечения (см рис 1)

Оригинальный принцип аналогии, предложенный Г Г Белоноговым и А А Хорошиловым, формулируется следующим образом «Слова с одинаковыми концевыми буквосочетаниями имеют одинаковые морфологические признаки» Предложенная модификация действует согласно парадигме «Слова с одинаковыми концевыми буквосочетаниями имеют одинаковые морфологические признаки, а также одинаковое концевое буквосочетание канонических Форм»

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

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

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

Предложенная модель морфологического анализатора имеет вид МА=<Р„,Рс,тт,^ст,а>, где Рм и тт - множества образцов слов и морфологических шаблонов (наборов морфологических признаков слов), Рс - множество образцов канонических форм, - отношение на Р„хРсхТ, а - отображение вида а IV => Уи< е и/Эа(и')с Отношение Яа,ст позволяет задать связь образцов слов и канонических форм с морфологическими шаблонами так, что каждая тройка отражает тот факт, что у любого слова,

соответствующего образцу и имеющего морфологический шаблон г, каноническая форма соответствует образцу рс

Морфологический анализ слова у> сводится к следующим действиям

- определение тройки (р„,рс,{)<=а(™) для слова и- такой, что р„ является максимально длинным образцом слова и-,

- замена в слове и- на рс с образованием канонической формы с

В проводимых экспериментах словарь обученного морфологического анализатора содержал -130 тыс образцов, что на порядок меньше совокупного объема словаря, использованного в работе Белоногова и Хорошилова

В главе также описан метод обучения модели МА Метод полностью отвечает стратегии АЗ (см рис 2) и реализует первый этап работы системы извлечения (см рис 1)

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

2 Анализатор-учитель должен обладать высокой точностью, однако к его полноте жестких требований не предъявляется

Особенностью получаемого в результате обучения морфологического анализатора является высокая Р-мера качества его работы в сравнении с качеством анализатора-учителя, т к обученный анализатор имеет как высокую точность, так и высокую полноту

Метод обучения основывается на большом массиве слов, корректно разобранных учителем (см рис 4) В экспериментах этот массив содержал -430 тыс слов, из которых было сформировано ~830 тыс обучающих примеров Обучение выполняется в три этапа

Рис 4 Этапы метода обучения модели МА На первом этапе примеры группируются по морфологическим шаблонам На втором этапе в каждой группе выделяются образцы, объединяющие примеры с совпадающими концевыми буквосочетаниями на основе четырех критериев

1 е 1¥, Зр„12 => тах(}р„,2) - Максимизация длины общего для пары слов (»,,№,) концевого буквосочетания

2 Зр„12 => Зрс1,рс2 рс1 = рс2 - Образцы канонических форм слов и^ и и>2 должны совпадать

3 Эр„12лЗа{к,)*0=>{ч{ру„,рс„1,)еа{у»1) к, е=> 1рш < 1Р„12) - Прежде чем генерировать образец р„12 на основе слова , необходимо проверить, не удовлетворяет ли -м, существующим образцам в других группах 1¥п Если для у»! удается найти существующие образцы {рт}, то необходимо потребовать, чтобы р„12 был длиннее всех {рш}

4 Зр„12лЗк> {р„12,рс12,()еа(-№)=>3{р„,рс,1)еа(уу) >/р„!2 -После генерации образца рш12 на основе слова к, необходимо проверить, не существует ли среди уже проанализированных слов, относящихся к другим морфологическим шаблонам \¥и, такого слова и-, которое также удовлетворяло бы образцу р„12 Если такое слово найдено, то необходимо убедиться, что его образец р„ длиннее, чем р„12, в противном случае необходимо отказаться от принятия рЫ2 и пытаться создать более короткий образец на основе п>;

На последнем этапе обучения выполняется постепенное сокращение максимизированных на предыдущем этапе длин образцов

В главе 7 «Экспериментальное исследование свойств разработанных моделей и методов» приведены результаты экспериментов, где исследованы свойства обучаемой модели морфологического анализа МА и свойства обу-чг\емой модели извлечения ЕМ

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

Основная масса образцов слов распределена в диапазоне длин от 4 до 11 символов На формирование этих образцов приходится 90% всех обучающих примеров Точность и полнота анализатора на известных словах зависит линейно от объема обучающей выборки и при максимальной выборке достигают абсолютных значений, близких к 1 Обученный анализатор в состоянии разобрать 70% слов, неизвестных учителю

Эксперименты с обучением модели извлечения позволили сделать следующие выводы Для текстов рассмотренных жанров наблюдается сравнительно малое отставание полноты извлечения от точности, что является уникальным в сравнении с зарубежными аналогами В зависимости от жанра текстов характер зависимости показателей качества от объема обучающей выборки различен Кроме того, для достижения значения F-мерой отметки 0,85 требуется разное количество примеров Чем меньше степень свободы автора при составлении текста, тем сильнее ограничена форма контекстов, окружающих извлекаемые значения фреймовых слотов Как следствие, требуется меньшее количество примеров для формирования правил извлечения, покрывающих тестовую выборку Так для текстов телеграммного жанра потребовалось всего 40 примеров, чтобы добиться значения F=0,98, для текстов жанра официальных документов F=0,85 после обучения на 250 примерах, тогда как для жанра информационной заметки F=0,85 достигается после обучения на 1000 примерах

В целом результаты экспериментов показали адекватность разработанных моделей и практическую применимость методов их обучения для задачи извлечения знаний из текстов

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1 Предложена комбинированная модель представления знаний, сочетающая современные достижения в области онтологического представления

знаний и достоинства фреймовых моделей и предоставляющая инструмент для разработки систем сопоставляющего анализа

2 Разработана модель извлечения знаний из текстов и метод ее обучения В модели выделена решетка лексических ограничений, на основе которой доказана теорема о возможности обучения модели извлечения Простота структуры правил извлечения обеспечивает практическую реализуемость механизмов обучения, а также обеспечивает реализацию метода извлечения на основе конечного автомата

3 Предложена модель морфологического анализа и метод ее обучения В качестве учителя используется другой морфологический анализатор с высокими показателями качества на неполном лексиконе языка Обучение не требует вмешательства человека Важное свойство обученной модели - способность разбирать изначально неизвестные слова

4 Все разработанные модели и методы доведены до программной реализации в виде самостоятельных продуктов для использования в задачах автоматизированной обработки текстов

5 Разработан программный комплекс для выполнения экспериментальной проверки работоспособности моделей Проведенные эксперименты показали для морфологического анализа точность обученной модели составляет 0,99 Для модели извлечения значение 0,85 F-меры качества достигается на 30% обучающих примеров от общего числа примеров для текстов жанра информационной заметки Для текстов телеграммного жанра F-мера достигает значения 0,98 на 20% обучающих примеров

6 Разработанные модели и методы

6 1 Внедрены в Системе семантического контроля текстов редактируемых документов, используемой в Совете Федерации Федерального Собрания Российской Федерации для выявления кадровых несоответствий в текстах стенограмм заседаний Совета Федерации, 6 2 Внедрены в Информационно-поисковой системе «Обзор СМИ» в части автоматического построения аннотаций к документам, используемой в Совете Федерации Федерального Собрания Российской Федерации, 6 3 Используются в Интеллектуальной системе выявления и исправления ошибок в почтовых адресах, разработанной компанией НПЦ «ИНТЕЛ-ТЕК ПЛЮС»,

6 4 Использованы в НИР по кластеризации и классификации текстовых документов для систем специального назначения, выполненной ВНИ-ИНС для МО

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Симаков К В Метод обучения модели извлечения знаний из естественноязыковых текстов / А М Андреев, Д В Березкин, К В Симаков // Вестник МГТУ Приборостроение -2007 - №3 - С 75-94

2 Симаков К В Модель извлечения знаний из естественно-языковых текстов / А М Андреев, Д В Березкин, К В Симаков // Информационные технологии -2007 -№12 - С 57-63

3 Андреев А М , Березкин Д В , Симаков К В Архитектура системы машинного понимания текстов // Информатика и системы управления в XXI веке Сборник трудов - М Изд-во МГТУ им НЭ Баумана, 2003 - №1 -С 419423

4 Березкин Д В , Симаков К В Формальный V - язык описания морфологии и синтаксиса текстов на естественном языке // Информатика и системы управления в XXI веке Сборник трудов - М Изд-во МГТУ им Н Э Баумана, 2003 - №1 - С 364-368

5 Андреев А М , Березкин Д В , Симаков К В Снятие синтаксической омонимии в задачах машинного понимания естественных текстов // Информатика и системы управления в XXI веке Сборник трудов - М Изд-во МГТУ им НЭ Баумана, 2003- №1 -С 415-418

6 Автоматическая классификация текстовых документов с использованием нейросетевых алгоритмов и семантического анализа / А М Андреев, Д В Березкин, В В Морозов, К В Симаков // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды пятой всероссийской научной конференции (RCDL'2003) - Санкт-Петербург НИИ Химии СПбГУ, 2003 - С 140-149

7 Андреев А М , Березкин Д В , Симаков К В Особенности проектирования модели и онтологии предметной области для поиска противоречий в правовых электронных библиотеках // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды шестой всероссийской научной конференции (RCDL'2004) - Пущино, 2004 - С 93-102

8 Андреев А М , Березкин Д В , Симаков К В Обучение морфологического анализатора на большой электронной коллекции текстовых документов // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды седьмой всероссийской научной конференции -Ярославль Ярославский государственный университет, 2005 - С 173-181

9 Андреев А М , Березкин Д В , Симаков К В Модель извлечения фактов из естественно-языковых текстов и метод ее обучения // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды восьмой всероссийской научной конференции (RCDL'2006) - Ярославль Ярославский государственный университет, 2006 - С 252-262

10 Использование технологии Semantic Web в системе поиска несоответствий в текстах документов / А М Андреев, Д В Березкин, В С Рымарь, К В Симаков // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды восьмой всероссийской научной конференции (RCDL'2006) - Ярославль Ярославский государственный университет им П Г Демидова, 2006 - С 263-269

11 Автоматизация обнаружения и исправления опечаток в названиях географических объектов для системы семантического контроля документов электронной библиотеки / А М Андреев, Д В Березкин, А С Нечкин, К В Симаков, Ю Л Шаров // Электронные библиотеки перспективные методы и технологии, электронные коллекции Труды девятой всероссийской научной конференции (RCDL'2007) - Переславль-Залесский Университет города Переславль, 2007 - Т 2 - С 49-56

Подписано к печати 23 01 08 Заказ № 31 Объем 1,0 печ л Тираж 100 экз Типография МГТУ им. Н.Э Баумана 105005, Москва, 2-я Бауманская ул, д 5 263-62-01

Введение.6

Актуальность работы.6

Цель и основные задачи работы.!.8

Объект и предмет исследования.8 *

Научная новизна.8

Области применения результатов диссертации.9

Глава 1. Постановка задачи извлечения знаний из текстов.12

1.1. Структура системы сопоставляющего анализа.12

1.2. Классификация знаний.14

1.3. Функционирование системы извлечения.16

1.4. Основные задачи диссертации.18

1.5. Оценка качества работы системы извлечения.21

Глава 2. Обзор методов извлечения знаний.22

2.1. Основные подходы к машинному обучению.22

2.1.1. Анализ и синтез при обучении.23

2.1.2. Дедуктивное обучение.25

2.1.3. Индуктивное обучение.26

2.1.4. Обучение на основе подобия.28

2.1.5. Типовые алгоритмы обобщения на основе подобия.30

2.2. Обучение в задачах извлечения информации.32

2.2.1. Детерминированный подход.32

2.2.1.1. Пропозиционные методы.33

2.2.1.2. Реляционные методы.46

2.2.1.3. Предварительные выводы.64

2.2.2. Вероятностный подход.68

2.2.2.1. Классификатор Байеса и стохастические грамматики.68

2.2.2.2. Скрытые Марковские Модели.70

2.2.2.3. Максимизация энтропии.76

2.2.2.4. Условные случайные поля.82

2.2.2.5. Предварительные выводы.87

2.3. Анализ подходов к извлечению знаний.89

2.4. Выводы по главе.92

Глава 3. Разработка принципов построения систем сопоставляющего анализа и извлечения знаний.94

3.1. Модель знаний предметной области.94

3.1.1. Онтологическое представление знаний.95

3.1.2. Фреймовое представление знаний.98

3.1.3. Наложение фреймов.100

3.2. Извлечение в сопоставляющем анализе.103

3.3. Функционирование системы извлечения.105

3.4. Единая стратегия обучения: A3.108

3.5. Выводы по главе.111

Глава 4. Разработка модели извлечения экземпляров фреймов.112

4.1. Модель представления текста.112

4.2. Компоненты модели извлечения.115

4.2.1. Описание модели.115

4.2.2. Элементы образцов и функция покрытия.117

4.3. Синтаксис правил извлечения.121

4.3.1. Способы описания лексических ограничений.121

4.3.2. Синтаксис правил извлечения.122

4.3.3. Примеры правил извлечения.126

4.4. Решетка лексических ограничений.130

4.5. Метод извлечения.132

4.5.1. Автомат извлечения.133

4.5.2. Алгоритм извлечения.139

4.6. Теорема о поиске модели извлечения.144

4.7. Выводы по главе.149

Глава 5. Разработка метода обучения модели извлечения.152

5.1. Описание метода.152

5.1.1. Представление обучающих примеров.153

5.1.2. Оценки качества результатов обучения.156

5.1.3. Фазы и этапы обучения.157

5.2. Описание этапов обучения.159

5.2.1. Формирование предельно конкретных правил.159

5.2.2. Итеративное обобщение.160

5.2.2.1. Алгоритм обобщения пары правил.165

5.2.2.2. Алгоритм обобщения пары образцов.168

5.2.3. Деградация незадействованных примеров.182

5.2.4. Генерация исключений.183

5.3. Выводы по главе.185

Глава 6. Разработка модели морфологического анализа и метода ее обучения.188

6.1. Выбор основополагающего метода анализа.188

6.1.1. Методы анализа на основе аффиксов.189

6.1.2. Словарные методы.191

6.1.3. Принцип аналоги.192

6.1.4. Обоснование выбора основополагающего метода.196

6.2. Модифиция принципа аналогии.197

6.2.1. Описание модели морфологического анализа.198

6.2.2. Вычислительная сложность морфологического анализа.201

6.3. Метод обучения модели морфологического анализа.204

6.3.1. Обучение согласно стратегии A3.204

6.3.2. Алгоритм обучения.206

6.4. Выводы по главе.213

Глава 7. Экспериментальное исследование свойств разработанных моделей.215

7.1. Свойства модели морфологического анализа.215

7.1.1. Исходные данные.215

7.1.2. Свойства алгоритма обучения.216

7.1.3. Точность и полнота морфологического анализа.222

7.2. Свойства модели извлечения.225

7.2.1. Исходные данные для эксперимента.226

7.2.2. Качество извлечения для текстов новостей.228

7.2.3. Качество извлечения для текстов стенограмм.230

7.2.4. Качество извлечения для текстов почтовых адресов.231

7.2.5. Зависимость показателей качества от длины контекста.233

7.2.6. Качественное сопоставление с зарубежными аналогами.236

7.3. Выводы по главе.239

ОБЩИЕ ВЫВОДЫ

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

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

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

3. Предложена модель морфологического анализа и метод ее обучения. В качестве учителя используется другой морфологический анализатор с высокими показателями качества на неполном лексиконе языка. Обучение не требует вмешательства человека. Обученная модель получает способность разбирать изначально неизвестные слова.

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

5. Разработан программный комплекс для выполнения экспериментальной проверки работоспособности моделей. Проведенные эксперименты показали: для морфологического анализа точность обученной модели составляет 0,99. Для модели извлечения значение 0,85 Б-меры качества достигается на 30% обучающих примеров от общего числа примеров для текстов жанра информационной заметки. Для текстов телеграммного жанра Б-мера достигает значения 0,98 на 20% обучающих примеров.

6. Разработанные модели и методы

6.1.Внедрены в Системе семантического контроля текстов редактируемых документов, используемой в Совете Федерации Федерального Собрания Российской Федерации для выявления кадровых несоответствий в текстах стенограмм заседаний Совета Федерации.

6.2.Внедрены в Информационно-поисковой системе «Обзор СМИ» в части автоматического построения аннотаций к документам, используемой в Совете Федерации Федерального Собрания Российской Федерации.

6.3.Используются в Интеллектуальной системе выявления и исправления ошибок в почтовых адресах, разработанной компаний НПЦ «ИНТЕЛТЕК ПЛЮС».

6.4.Использованы в НИР по кластеризации и классификации текстовых документов для систем специального назначения, выполненной ВНИИНС для МО.

244

ЗАКЛЮЧЕНИЕ

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

Согласно выполненной классификации из естественно-языковых текстов извлекаются следующие виды знаний.

- Экземпляры фреймов модели предметной области, которые после извлечения преобразуются в объекты онтологии с означенными свойствами и взаимосвязями. Преобразование задается путем наложения схемы фреймов на схему онтологии. Экземпляры фреймов извлекаются автоматически путем применения правил извлечения.

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

- Правила словообразования модели морфологического анализатора MA. Обучение данной модели, также как и модели ЕМ, выполняется на основе естественно-языковых текстов. Результатом обучения являются образцы слов и канонических форм, с которыми связаны наборы морфологических признаков. В совокупности эти компоненты модели MA образуют целевые правила словообразования.

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

Для извлечения знаний второго и третьего вида разработана единая стратегия обучения АЗ (Акцентированная аппроксимирующая абстракция). Данная стратегия задает основные принципы извлечения процедурных знаний на основе естественно-языковых текстов. Стратегия АЗ подразумевает наличие дополнительного этапа, выполняющего преобразование наблюдений, представленных естественно-языковыми текстами, в формализованные обучающие примеры. Основным методом обучения является конструктивная индукция.

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

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

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

1. Hahn U., Schnattinger K. Knowledge mining from textual sources // Proceedings of the sixth international conference on Information and knowledge management. 1997. - P. 83 - 90.

2. Hahn U., Schnattinger K. A text understander that learns // Proceedings of the 17th international conference on Computational linguistics. 1998. - Vol.1. — P. 476 - 482.

3. Hahn U., Marko K.G. Joint knowledge capture for grammars and ontologies // Proceedings of the 1st international conference on Knowledge capture. 2001. -P. 68-75.

4. Chinchor N. MUC-4 evaluation metrics // Proceedings of the 4th conference on Message understanding. 1992. - P. 22 - 29.

5. Chinchor N., Sundheim B. MUC-5 evaluation metrics // Proceedings of the 5th conference on Message understanding. 1993. - P. 69 - 78.

6. Grishman R., Sundheim B. Message Understanding Conference-6: a brief history // Proceedings of the 16th conference on Computational linguistics. -1996.-Vol.l.-P. 466-471.

7. C. J. van Rijsbergen. Information Retrieval / C. J. van Rijsbergen. 2nd edition. - London: Butterworth & Co (Publishers) Ltd., 1979. - 147 p.

8. Michalski R.S. Multistrategy Constructive Learning: Toward a Unified Theory of Learning // Reports of the Machine Learning and Inference Laboratory (MLI 90-1). George Mason University, Fairfax, VA, 1989. -January. — 35 p.

9. Mitchel T.M., Keller R.M., Kedar-Cabelli S.T. Explanation-based generalization: A unifying view // Machine Learning. 1986. - No. 1. - P. 4780.

10. Michalski R.S. A theory and methodology of inductive learning // Artificial intelligence. 1983. - No. 20. - P. 111-161.

11. Huffman S.B. Learning to extract information from text based on user-provided examples // Proceedings of the fifth international conference on Information and knowledge management. Rockville, Maryland, (United States), 1996.-P. 154-163.

12. Zelenko D., Aone C., Richardella A. Kernel methods for relation extraction // The Journal of Machine Learning Research. 2003. - No. 3. - P. 1083-1106.

13. Кормалев Д.А. Автоматическое построение правил извлечения информации из текста // Системный анализ и информационные технологии (САИТ-2005): Труды 1-ой международной конференции. — Т. 1.-М.: КомКнига, 2005. С. 205-209.

14. Rigau G., Rodrigues H., Agirre E. Building Accurate Semantic Taxonomies from Monolingual MRDs // Proceedings of the 36th annual meeting on Association for Computational Linguistics. Montreal, Quebec, (Canada), 1998.-Vol. 2.-P. 1103-1109.

15. Rigau G., Atserias J., Agirre E. Combining Unsupervised Lexical Knowledge Methods for Word Sense Disambiguation // Proceedings of the 35th annual meeting on Association for Computational Linguistics. Madrid, (Spain), 1997. -P. 48-55.

16. Califf M.E., Mooney R.J. Bottom-up relational learning of pattern matching rules for information extraction // The Journal of Machine Learning Research. -2003.-No. 4.-P. 177-210.

17. Dejean H. Learning rules and their exceptions // The Journal of Machine Learning. 2002. - No. 2. - P. 669-693.

18. Claveau V., Sebillot P., Fabre C. Learning Semantic Lexicon from a Part-of-Speech and Semantically Tagged Corpus Using Inductive Logic Programming // The Journal of Machine Learning Research. 2003. - No. 4. - P. 493-525.

19. Тшшо J., Ageno A., Catala N. Adaptive information extraction // ACM Computing Surveys archive. 2006. - Vol. 38, Issue 2. - Article No. 4.

20. Riloff E. Automatically Constructing a Dictionary for Information Extraction Tasks // In Proceedings of the 11th National Conference on Artificial Intelligence (AAAI). 1993. - P. 811-816.

21. Riloff E. Automatically generating extraction patterns from untagged texts // In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI). 1996. - Vol. 2. - P. 1044-1049:

22. Kim J., Moldovan D. PALKA: A System for Lexical Knowledge Acquisition // Proceedings of the 2nd international conference on Information and. knowledge management. Washington, D.C., (USA), 1993. - P. 124-131.

23. Kim J., Moldovan D. Acquisition of Linguistic Patterns for Knowledge-Based Information Extraction // IEEE Transactions on Knowledge and Data Engineering archive. 1995. - Vol. 7, Issue 5. - P. 713-724.

24. CRYSTAL: Inducing- a conceptual* dictionary / S. Soderland, D: Fisher, J. Aseltine, We. Lehnert // In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. 1995. - P. 1314—1319.

25. Soderland S. Learning to extract text-based information from the World Wide Web // In Proceedings of Third International Conference on Knowledge Discovery and Data Mining (KDD-97). 1997. - P. 251-254.

26. Aseltine J. WAVE: An Incremental Algorithm for Information Extraction: Technical Report WS-99-11 // In Proceedings of the AAAI Workshop on Machine Learning for Information Extraction. 1999. - P. 21-24.

27. Chai J.Y., Biermann A.W., Guinn C.I. Two dimensional generalization in information extraction // In Proceedings of the Sixteenth National Conference on Articial Intelligence. 1999. - July. - P. 431-438.

28. Chai J. Y., Biermann A. The use of lexical semantics in information extraction // In Proceedings of the Workshop in Automatic Information Extraction and Building of Lexical Semantic Resources. 1997. - P. 61-70.

29. Miller G.A. WordNet: a lexical database for English // Communications of the ACM archive. 1995. - Vol. 38, Issue 11. - P. 39^1.

30. Richardson S.D., Dolan W.B., Vanderwende L. MindNet: acquiring and structuring semantic information from text // Proceedings of the 17th international conference on Computational linguistics. 1998. — Vol. 2, — P. 1098-1102.

31. Moldovan D., Girju R., Rus V. Domain-specific knowledge acquisition from text // Proceedings of the sixth conference on Applied natural language processing. 2000. - P. 268-275.

32. Argamon S., Dagan I., Krymolowski Y. A memory-based approach to learning shallow natural language patterns // Proceedings of the 17th international conference on Computational linguistics. 1998. - Vol. 1. — P. 67-73. •

33. Leroy G., Chen H., Martinez J.D. A shallow parser based on closed-class words to capture relations in biomedical text // Journal of Biomedical Informatics archive. 2003. - Vol. 36, Issue 3. - P. 145-158.

34. Freitag D. Machine Learning for Information Extraction in Informal Domains // Machine Learning. 2000. - Vol. 7. - P. 169-202.

35. Califf M.E., Mooney RJ. Bottom-up relational learning of pattern matching rules for information extraction // Journal of Machine Learning Research. -2003.-Vol. 4.-P. 177-210.

36. Soderland S. Learning information extraction rules for semi-structured and free text. Machine Learning. 1999. - Vol. 34, Issue 1-3. P. 233-272.

37. Pazienza M.T., Stellato A., Vindigni M. Combining ontological knowledge and wrapper induction techniques into an e-retail system // In: Workshop on Adaptive Text Extraction and Mining (ATEM03) held with ECML/PKDD. -Cavtat, 2003.-P. 50-57.

38. Dejean H. Learning rules and their exceptions // The Journal of Machine Learning Research archive. 2002. - Vol. 2 (March). - P. 669-693.

39. Learning Semantic Lexicons from a Part-of-Speech and Semantically Tagged Corpus Using Inductive Logic Programming / V. Claveau, P. Sebillot, C. Fabre, P. Bouillon // Journal of Machine Learning Research. 2003. - Vol. 4. - P. 493-525.

40. Srinivasan A. The ALEPH Manual Version 4 and above Электронный ресурс. / A. Srinivasan; Oxford University Computing Laboratory. Режим доступа: httpV/web.comlab ox.ac.uk/oucl/research/areas/rriach1carn/Alcph/a1ephtoc.html. свободный.

41. Relational learning as search in a critical region / M. Botta, A. Giordana, L. Saitta, M. Sebag // The Journal of Machine Learning Research archive. — 2003. -Vol. 4.-P. 431-463.

42. Costa V.S., Srinivasan A., Camacho R. Query transformations for improving the efficiency of ILP systems // The Journal of Machine Learning Research archive. 2003. - Vol. 4. - P. 465^91.

43. Dzeroski S. An introduction to inductive logic programming and learning language in logic / S. Dzeroski, J. Cussens, S. Manandhar // Learning language in logic. — Berlin: Springer, 2000. P. 3-35.

44. Appelt D.E., Onyshkevych B. The common pattern specification language / Annual Meeting of the ACL archive // Proceedings of a workshop on held at Baltimore. 1998. - October. - P. 23-30.

45. Теория вероятностей: Учебник для вузов / А.В. Печенкин, О.И. Тескин, Г.М. Цветкова, П.П. Бочаров, Н.Е. Козлов; Под ред. B.C. Зарубина, А.П. Крищенко. 4-е изд., стереотип. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2006.-455 с.

46. Androutsopoulos I., Koutsias J., Konstantinos V. An experimental comparison of naive Bayesian and keyword-based anti-spam filtering with personal e-mail messages // Proceedings of the 23rd annual international ACM

47. SIGIR conference on Research and development in information retrieval. — 2000.-P. 160-167.

48. Androutsopoulos I., Paliouras G., Michelakis E. Learning to filter unsolicited commercial e-mail: Technical Report 2004/2 / National Centre for Scientific Research «Demokritos». Athens, 2004. - October. - 52 p.

49. Hovold J. Naive bayes spam filtering using word-position-based attributes // Proceedings of the 2nd Conference on Email and Anti-Spam (CEAS 2005). -Palo Alto, CA, 2005. July. - 8 p.

50. Pedersen T. A simple approach to building ensembles of Naive Bayesian classifiers for word sense disambiguation // Proceedings of the first conference: on North American chapter of the Association for Computational Linguistics. — 2000.-P. 63-69.

51. Feldman R., Rosenfeld В., Fresko M. TEG a hybrid approach to information extraction // Knowledge and Information Systems archive. - 2006. -Vol. 9, Issue 1.-P. 1-18.

52. Abney S.P. Stochastic attribute-value grammars // Computational,Linguistics archive. 1997. - Vol! 23, Issue 4. - P. 597-618.

53. Дискретная математика: Учеб. для вузов / А.И. Белоусов, С.Б. Ткачев; Под ред: В;С. Зарубина, А.П. Крищенко. 4-е изд., стереотип. - М.: Изд— во МГТУ им. Н.Э. Баумана, 2006. - 743 с.

54. Rabiner L., Juang B. An introduction to hidden Markov models // IEEE ASSP Magazine. 1986.-Vol. 3, Issue 1, Part 1.-P. 4-16.

55. Sang-Zoo Lee, Jun-ichi Tsujii, Hae-Chang Rim. Part-of-Speech Tagging Based on Hidden Markov Model Assuming Joint Independence // In Proceedings of the 38 th Annual Meeting of the ACL. 2000. - P. 263-269.

56. Rabiner L.R. A tutorial on hidden Markov models and selected applications in speech recognition^// Proceedings of the IEEE. 1989. - Vol. 77, Issue 2. - P. 257-286.

57. Freitag D., McCallum A.K. Information Extraction with HMMs and Shrinkage // Proceedings of the AAAI-99 Workshop on Machine Learning for Information Extraction. — 1999. — P. 31 36.

58. Borkar V., Deshmukh K., Sarawagi S. Automatic segmentation of text into structured records // Proceedings of the 2001 ACM SIGMOD international conference on Management of data. 2001. - P. 175-186.

59. Berger A.L., Delia Pietra V.J., Delia Pietra S.A. A maximum- entropy approach-to naturaLlanguage processing5// Computational*Linguistics archive. -1996.-Vol. 22, Issue 1,-P: 39-71.

60. Chieu H.L., Hwee Tou Ng. Named entity recognition: a maximum entropy approach using global information1 // Proceedings of the 19th international conference on Computational linguistics. 2002. - Vol. 1. - P. 1-7.

61. Hai Leong Chieu, Hwee Tou Ng. Named entity recognition with a maximumentropy approach // Proceedings of the seventh conference on NaturaManguagelearning at HLT-NAACL 2003. 2003. - Vol. 4. - P. 160-163.

62. Hai Leong Chieu, Hwee Tou Ng. A maximum entropy approach to information extraction from semi-structured and free text // Eighteenth national conference on Artificial intelligence. -2002. P. 786-791.

63. McCallum A., Freitag D., Fernando C. N. Pereira. Maximum Entropy Markov Models for Information Extraction and Segmentation // Proceedings of the Seventeenth International Conference on Machine Learning. 2000. — P. 591598.

64. McCallum A. An Introduction to Conditional Random Fields for Relational Learning / C. Sutton, A. McCallum // Introduction to Statistical Relational Learning / Edited by Lise Getoor and Ben Taskar. MIT Press, 2007. - P. 95130.

65. Lafferty J., McCallum A., Pereira F. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data // In Proc. 18th International Conference on Machine Learning (ICML'01). 2001. - P. 282-289.

66. Wallach H.M. Conditional Random Fields: An Introduction: Technical Report No. MS-CIS-04 21 / University of Pennsylvania Department of Computer and Information Science. 2004: - 10 p.

67. McCallum A. Efficiently inducing features of conditional random fields // In Proceedings of Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI03). 2003. - P. 403-410.

68. Ермаков A.E., Плешко В.В., Митюнин В.А. RCO Pattern Extractor: компонент выделения особых объектов в тексте Электронный ресурс. — Режим доступа: http://www.rco.ru/article.asp7ob по=237, свободный.

69. Пресс-портреты. на Яндекс.Новостях. Описание технологии Электронный ресурс. Режим доступа: http://news.yandex.ru/people-search-tech.html. свободный.

70. Кормалев Д.А. Индуктивный алгоритм машинного обучения для построения правил извлечения информации из текста. // Девятая

71. Национальная конференция по искусственному интеллекту с международным участием КИИ-2004: Труды конференции. — М.: Физматлит, 2004. -Т.1. С. 154-161.

72. Кормалев Д.А. Приложения методов машинного обучения в задачах анализа текста // Труды международной конференции «Программные системы: теория и приложения». Переславль-Залесский, М.: Физматлит, 2004. - Т.2. - С. 35-48.

73. Peter F. Patel-Schneider, Ian Horrocks. OWL Web Ontology Language Semantics and Abstract Syntax Section 2. Abstract Syntax Электронный ресурс. — Режим доступа: http://www.w3.org/TR/owl-semantics/syntax.htmK свободный.

74. Peter F. Patel-Schneider, Ian Horrocks. OWL Web Ontology Language. Semantics and Abstract Syntax Section 3. Direct Model-Theoretic Semantics! Электронный ресурс. Режим доступа: http://www. w3 .org/TR/o wl-semantics/direct.html, свободный.

75. Гаврилова T.A., Червинская K.P. Извлечение и структурирование знаний для экспертных систем. — М:: Радио и связь, 1992. 200 с.

76. Peter D: Karp, Thomas Gruber. The Generic Frame Protocol, Электронный ресурс. — Режим доступа: http://www.ai.sri.com/~gfp/spec/paper/paper.html, свободный.

77. Осипов Г.С. Методы поиска и анализа информации. Автоматическое извлечение данных / Д.А. Кормалев, Е.П. Куршев, Г.С. Осипов, Е.А. Сулейманова, И.В. Трофимов. Переславль-Залесский: ИПС РАН, 2003. — 48 с.

78. Alpha К. Luk. Statistical sense disambiguation with relatively small corpora using dictionary definitions // Proceedings of the 33rd annual meeting on Association for Computational Linguistics. 1995. - P. 181-188.

79. Rigau G., Rodriguez H., Agirre E. Building accurate semantic taxonomies from monolingual MRDs // Proceedings of the 36th annual meeting on Association for Computational Linguistics. 1998: - Vol. 2.-P. 1103-1109.

80. Yael Karov, Shimon Edelman. Similarity-based word sense disambiguation // Computational Linguistics archive. 1998. - Vol. 24, Issue 1; (March 1998), SPECIAL ISSUE: Special issue on word sense disambiguation. - P. 41-59.

81. German Rigau, Jordi Atserias, Eneko Agirre. Combining unsupervised lexical knowledge methods for word sense disambiguation // Proceedings of the eighth conference on European chapter of the Association for Computational Linguistics. 1997. - P. 48-55.

82. Patrick Pantel, Dekang Lin. Discovering word senses from text. Conference on Knowledge Discovery in Data archive // Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. — 2002.-P. 613-619.

83. Mihalcea R., Moldovan D.I. A method for word sense disambiguation of unrestricted text // Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics. 1999. - P. 152158.

84. Rebecca Bruce, Louise Guthrie. Genus disambiguation: a study in weighted preference // Proceedings of the 14th conference on Computational linguistics. -1992.-Vol. 4.-P. 1187-1191.

85. Сухоногов A.M., Яблонский C.A. Разработка русского WordNet // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды шестой всероссийской научной конференции (RCDL'2004) Пущино, 2004. - С.113-116.

86. Henry S. Thompson. XML Schema Part 1: Structures (Second Edition) Электронный ресурс. / Henry S. Thompson, David Beech, Murray Maloney, Noah Mendelsohn; W3C Recommendation. Режим доступа: http://www.w3.org/TR/xmlschema-l/, свободный.

87. Брик A.B. Исследование и разработка вероятностных методов синтаксического анализа текста на естественном языке: автореф. дис. . канд. техн. наук: 05.13.11: защищена 06.06.2002 / A.B. Брик; МГТУ им. Н.Э. Баумана. М., 2002. - 16 с.

88. Сегалович И. Русский морфологический анализ и синтез с генерацией моделей словоизменения для не описанных в словаре слов Электронный ресурс. / И. Сегалович, М. Маслов. Режим доступа: http://companv.vandex.ru/articles/articlel.html, свободный.

89. Попов Э.В. Общение с ЭВМ на естественном языке. 2-е изд., стереотипное. - М.: Едиториал УРСС, 2004. - 358 с.

90. Зализняк A.A. Грамматический словарь русского языка (словоизменение). 2-е изд. - М.: Русский язык, 1980. - 880 с.

91. Старостин С.А. Морфологический анализ Электронный ресурс. / С.А. Старостин. Режим доступа: http://starling.rinet.ru/morph.htm, свободный.

92. Автоматическая обработка текста Электронный ресурс. Режим доступа: http://www.aot.ru, свободный.

93. Белоногов Г.Г., Калинин Ю.П., Хорошилов A.A. Компьютерная лингвистика и перспективные информационные технологии М.: Русский мир, 2004. -203 с.

94. УНИВЕРСИТЕТ ИМ. Н.Э. БАУМАНА1. На правах рукописи

95. Симаков Константин Васильевич10420 0.8 0921 7

96. МОДЕЛИ И МЕТОДЫ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ТЕКСТОВ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ

97. Специальность 05.13.17 — Теоретические основы информатики

98. Диссертация на соискание ученой степени кандидата технических наук

99. Научный руководитель — доктор технических наук профессор В.Н. Голубкин1. Москва-2008