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

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

ЛИТВИНОВ МАКСИМ ИГОРЕВИЧ

МЕТОДЫ АВТОМАТИЧЕСКОЙ ПРЕДОБРАБОТКИ ТЕКСТА ПРОЕКТНОЙ ДОКУМЕНТАЦИИ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ О СОЧЕТАЕМОСТИ СЛОВ

Специальность - 05.13.12 «Системы автоматизации проектирования (информатика) (технические науки)».

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Москва 2012

005020089

Работа выполнена на кафедре «Информационные технологии и автоматизированные системы» Московского института электроники и математики (технического университета).

Научный руководитель: кандидат технических наук, доцент Клышинский Эдуард Станиславович.

Официальные оппоненты:

Хорошилов Александр Алексеевич, д.т.н., ИПИ РАН, ведущий научный сотрудник.

Дроздов Вячеслав Вадимович, к.т.н., ООО "Телеформ ИС", инженер-программист.

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт прикладной математики им. М.В. Келдыша РАН, г. Москва.

Защита состоится « 24 » апреля 2012 г. в 12:00 часов на заседании диссертационного совета Д 212.133.03 Московского государственного института электроники и математики (технического университета) по адресу:

109028 Москва, Б. Трехсвятительский пер., д. 3.

С диссертацией можно ознакомиться в библиотеке МИЭМ Автореферат разослан « 19 » марта 2012 г.

Ученый секретарь диссертационного совета, доктор технических наук, доцент

Ю.Л. Леохин

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

Актуальность темы.

На различных этапах разработки изделий, особенно в процессе проектирования, предприятия накапливают большие объемы документации, которая может быть: техническим заданием, эскизом проекта, чертежами, протоколами информационного обмена, отчетами, приказами, служебными записками и даже электронной перепиской. Эффективным и действенным средством контроля информационных потоков на предприятии выступают следующие технологии: ILM (Information Lifecycle Management) и PLM (Product Lifecycle Management). Под этими технологиями понимается комплекс аппаратных и программных средств, обеспечивающих доступ к различным информационным ресурсам в процессе разработки продукта и выпуска сопутствующей документации по нему.

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

Research Ф»-------------------:----

РММЮК* едкий« - UnM^fanskmrne

Рисунок 1 Общий вид системы, описывающей жизненный цикл продукта.

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

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

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

Для достижения цели данной диссертационной работы были поставлены и решены следующие задачи:

• Анализ существующих методов устранения морфологической неоднозначности;

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

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

• Разработка структуры программы и её реализация на языке программирования С++.

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

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

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

При решении задач, поставленных в диссертационной работе, получены следующие новые научные результаты:

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

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

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

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

Полученные в рамках данной диссертационной работы алгоритмы вошли в состав машинного переводчика «Кросслейтор», который разрабатывается в ИПМ им. М.В. Келдыша РАН и при выполнении гос. контракта П-261 в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., заключенного между Министерством образования и науки и МИЭМ. Работа была поддержана грантом РФФИ № 10-01-00800. Проведенные вычислительные эксперименты показали практическую эффективность предложенных подходов.

Реализация п внедрение результатов. Описанные в данной работе алгоритмы и методы реализованы автором в виде компьютерной подпрограммы, что позволяет подтверждать теоретические исследования в области моделирования естественного языка, а также использовать в машинном переводчике «Кросслейтор», разрабатываемом в ИПМ им. М.В. Келдыша РАН.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», Москва, МИЭМ, 17 февраля - 01 марта 2010.

• «Новые информационные технологии в автоматизированных системах», МИЭМ, 25 марта 2010 года.

• Компьютерная лингвистика и интеллектуальные технологии ежегодная Международная конференция «Диалог» (2010).

• ХН-ая Национальная конференция по искусственному интеллекту с международным участием.

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», Москва, МИЭМ, 17 февраля - 01 марта 2011.

• «Автоматическая обработка естественного языка», СпбГУ, Санкт-Петербург, 26-ое марта 2011.

Основное содержание диссертационной работы и ее результатов отражено в 6 научных работах, из них 2 в журнале из перечня ВАК. Объем и структура диссертации. Диссертационная работа содержит введение, четыре главы с выводами, заключение, список литературы и приложения, включающие в себя акты внедрения и результаты расчетов. Основная часть работы изложена на 121 страницах машинописного текста, содержит 18 таблиц и 8 рисунков. Список литературы включает 103 наименования.

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

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

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

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

Предсинтаксический анализ предназначен для того, чтобы устранить неоднозначность более вычислительно эффективными средствами. В зависимости от конечных задач, предсинтаксический анализ может быть последним или промежуточным этапом при обработке текста на естественном языке. Сам процесс указания однозначной морфологической интерпретации (снятие омонимии) для слов в тексте на естественном языке называется тэггингом (от англ. tagging) или морфологической разметкой. При разметке текста, есть задачи, для которых необходимо определить часть речи, от которой образовано слово, так называемый POS-тэггинг (частеречная разметка). Есть задачи, для которых необходимо знать нормальную форму слова со всем набором грамматических параметров, так называемый Lemma-тэггинг (лексическая разметка).

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

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

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

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

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

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

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

исследователей и разработчиков. Например, в проекте Национальный корпус русского языка по различным оценкам процент ошибок колеблется от 3 до 5. Кроме того, приходится соглашаться с тем, что невозможно создать эталонные корпуса на все случаи жизни, особенно для узкоспециализированных предметных областей.

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

Используя опыт систем разработанных в компании Яндекс и группой Чешских исследователей было решено разработать метод устранения морфологической неоднозначности, использующий базу данных синтаксического подчинения и вероятностные правила, содержащие морфологические параметры. В данной работе под правилами понимается упорядоченная тройка <т,-, у,», У;+2>, где V, = <р„, {рг}> - краткое описание слова, р„ - часть речи слова, а {рг} -множество морфологических параметров слова. Таким образом, в правиле не учитывается лексема слова, однако учитываются его морфологические параметры. Правило может трактоваться произвольным образом и может быть записано как вхождение V,- с учетом его правых соседей, как вхождение у,+2 с учетом его левых соседей или с учетом вхождения его соседей с двух сторон.

Эксперименты показали, что в текстах на русском языке встречается порядка 40-50% однозначных словоупотреблений. В связи с этим вероятность встретить группу из двух неомонимичных слов достаточно велика, более того, она растет с длиной предложения. При отсутствии

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

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

Р,м = argmax(fl P(v, | vM, v,.2) ),

¿=i

где ns - число слов в предложении. Вместо этого критерий для предложения в целом формулируется следующим образом:

Psent 11 Pfragm i» ¡=1

*fl

где Pfragmi = argmax(]~J P(v,-1 v,-.i, v,-.2) ) - вероятность встретить i-й

¡=1

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

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

Для автоматического определения связей между словами в предложении прежде всего необходимо решить проблему лексической и синтаксической неоднозначностей и автоматически определить связи в предложении. Как было сказано выше, в текстах на русском языке встречается порядка 40-50% слов с однозначно определенной частью речи и, как следствие, вероятность встретить однозначную группу достаточно велика. Для этих целей были выдвинуты две гипотезы.

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

1. Следующая за единственным в предложении глаголом группа существительного синтаксически подчиняется данному глаголу.

2. Единственная группа существительного, расположенная в начале предложения перед единственным глаголом, синтаксически подчиняется данному глаголу.

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

4. Положения 1-3 могут быть применены к деепричастиям и причастиям.

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

Таким образом, на основании вышеприведенных гипотез удалось получить 6 достаточно простых правил:

I. verb + noun* ( глагол + существительное )

II. adj + noun* ( прилагательное + существительное)

III. deepr + noun* (деепричастие + существительное )

IV. participle + noun* ( причастие + существительное )

V. adv + verb ( наречие + глагол)

VI. adv + deepr ( деепричастие + наречие )

* Возможно наличие предлога (prep).

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

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

P{w,) = argmax Р(ч\ \ ил_,) )

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

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

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

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

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

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

В четвертой главе представлены результаты практической реализации разработанных методов. Написанная подпрограмма была интегрирована в машинный переводчик «Кросслейтор». Разработанный комплексный метод устранения морфологической неоднозначности позволил значительно сократить число гипотез при проведении синтаксического анализа и тем самым ускорить сам анализ в 2..10 раз. Данная программа автоматической предобработки текстов принимала участие в соревновании морфологических парсеров международной конференции Диалог 2010, где заняла 3 место в конкурсе программ по

снятию частеречной неоднозначности (см. Рисунок 1).

«ДизамВигуаиия: POS>

Участник t нет f Accur.

Olwe 1991 22 33 97.3%

Pine 1991 5 50 97.3%

Cadet 1958 43 45 95.7%

Maroon 1943 0 103 95.0%

S Herbert 1934 75 37 94.5%

Apricot 1769 11 266 86.5%

Shamrock 1394 547 105 68.1%

2046 95.0%

Рисунок 2 Рейтинг систем на дорожке с дизамбигуацией POS.

Модуль устранения морфологической неоднозначности для программы автоматического перевода «Кросслятор», в его текущей реализации, работает со скоростью 7500 слов/сек.

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

метод.

Таблица 1 Сравнительная оценка работы различных методов устранения

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

Random First Метод 1 Три+ г- ' Три ! База , Правила f Итерация

PfBcision POS Precision Lemma Accuracy POS Accuracy Lemma 91.55 90.30 94.28 94.30 99.90 98.45 98.41 97.45

68.07 60.29 70.53 70.60 99.90 98.2 96.08 93.54

91.54 90.30 94.26 94.26 43.32 44 52.5 56.2

68.06 60.28 70.53 70.60 43.32 43.89 51.25 53.94

F-measure POS F-measure Lemma 91.54 90.30 94.27 94.29 60.43 60.82 68.47 71.29

68.06 60.28 70.53 70.60 60.43 60.67 66.84 68.42

Пояснения к Таблице 1:

Precision - процент правильных ответов из всех ответов, который выдала

система.

Accuracy - процент покрытия тех слов из предложенной дорожки,

которые были размечены на уровне морфологического анализа.

F measure - интегральная оценка работы каждого метода, которая

вычисляется согласно выражению 1.7, с весовым коэффициентом р = 1.0.

Random - случайной выбор тэга для неизвестного слова.

First - выбор первого тэга для неизвестного слова из списка возможных

вариантов.

Метод - определение значение неизвестного слова с помощью предложенного в рамках данной работы метода.

Трн+ - тегирование неизвестного слова с помощью триграмм, вероятностных правил и итерационного применения вероятностных правил.

Три - тегирование слов только с помощью триграмм.

База - определение значения неизвестного слова только с помощью базы

синтаксического подчинения.

Правила - разметка слов только с помощью вероятностных правил. Итерация - разметка слов только с помощью итерационного применения вероятностных правил.

При снятии частеречной омонимии реализованный метод Триграмм и Базы Сочетаемости Слов даёт сопоставимый результат, с высоким качеством выдаваемых результатов, но в то же время и с низким процентом разбора дорожки. Добавление метода, основанного на применении вероятностных правил и итерационного применения вероятностных правил, значительно повышает процент разбора дорожки, но с несколько меньшим качеством. На основании того, что настройки системы «Триграммы + Правила + Итерация», «База+ Правила + Итерация» дают не сильно различающиеся результаты как по показателю Precision, так и no Accuracy, то можно использовать что-то одно в качестве базового метода для снятия морфологической неоднозначности. Но в то же время, по точности оценки (Precision) предложенный метод

превосходит случайный выбор варианта и первый попавшийся вариант разбора, особенно при разметке слова с полным набором морфологических параметров. Последнее обуславливается тем, что в русском языке ( в данном случае идёт про проектную документацию на русском языке ), в среднем 1.16 части речи на слово и 2.01 леммы на слово. В конечном итоге результаты по показателю Precision отражается на F-мере, как в случае разметке по части речи, так и в случае разметки с полным набором морфологических параметров.

Заключение. Получен новый комбинированный метод устранения морфологической неоднозначности в текстах проектной документации на естественном языке. В качестве входных данных для разработанного метода используются результаты морфологической разметки, проводимой словарём «Кросслятор». В рамках данной работы, в интересах снижения стоимости разработки систем предсинтаксического анализа было предложено использовать обучение без учителя на неразмеченных коллекциях проектной документации с использованием правил синтаксического подчинения слов в предложении. Собранная статистика с использованием свойства синтаксического подчинения слов используется для устранения морфологической неоднозначности: в общем случае, можно определить нормальную форму, от которой образована данная словоформа; в частном же случае можно определить полный набор морфологических параметров слов. Такой метод сбора статистики употребления слов позволил получить значительно меньшее число сочетаний слов по сравнению с теоритической оценкой возможных сочетаний N-грамм. В случае отсутствия в базе статистики совместного употребления слов применяются вероятностные правила, содержащие морфологические параметры. Декомпозиция предложения на фрагменты позволяет применять вероятностные морфологические правила в случае наличия большого количества неоднозначных слов, идущих подряд. Предложенный комбинированный метод предсинтаксического анализа показал свою эффективность в практической реализации и, в том числе,

на соревнованиях, проводимых в рамках международной конференции Диалог 2010.

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

Описанные в данной работе алгоритмы и методы, реализованы автором в виде компьютерной подпрограммы, что позволяет подтверждать теоретические исследования в области моделирования естественного языка, а также использовать в машинном переводчике «Кросслейтор», разрабатываемом в ИПМ им. М.В. Келдыша РАН. Проведенные вычислительные эксперименты показали практическую эффективность предложенных алгоритмов и программных решений.

В приложении к данной диссертационной работе приведен акт внедрения результатов.

1. Литвинов М.И. Метод повышения качества снятия омонимии с использованием статистики совместного употребления слов, журнал «Качество Инновации Образование», 2010 г. , 11-Й выпуск, с. 113-115.

2. Клышинский Э.С., Кочеткова Н.А., Литвинов М.И., Максимов В.И. Метод разрешения частеречной омонимии на основе применения корпуса синтаксической сочетаемости слов в русском языке // Научно-техническая информация, сер. 2, № 1,2011 г. с. 31-35.

3. Литвинов М.И. «Комплексный метод снятия частеречной омонимии с использованием статистики совместного употребления слов в

тексте на русском языке», по материалам ХИ-ой Национальной конференции по искусственному интеллекту с международным участием.

4. Клышинский Э.С., Кочеткова H.A., Литвинов М.И., Максимов В.Ю. Автоматическое формирование базы сочетаемости слов на основе очень большого корпуса текстов // Компьютерная лингвистика и интеллектуальные технологии. Труды международного семинара Диалог'2010., 2010 г. с. 181-186.

5. Литвинов М.И. Модели управления на основе сочетаний из трёх слов и глагольное управление для поверхностного синтаксического анализа // Сб. трудов научно-практического семинара «Новые информационные технологии в автоматизированных системах-13». М.: МИЭМ, 2010 г. с. 107-112.

6. Литвинов М.И. Модели управления на основе сочетаний из трёх слов и глагольное управление // материалы ежегодной научно-технической конференция студентов, аспирантов и молодых специалистов МИЭМ, 2010 г. с. 93-95.

Подписано в печать 19.03.2012 г. Формат 60x90 1/16 Печать на pro 265. Тираж 100 экз. Заказ 19.03.2012.24 Отпечатано в типографии ООО «Техноком», ИНН:7709736259, г. Москва, ул. Покровка, д.12, стр.3, т. 956-32-14, www.funcopy.ru

61 12-5/2497

Министерство образования Российской Федерации Московский государственный институт электроники и математики

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

Литвинов Максим Игоревич

МЕТОДЫ АВТОМАТИЧЕСКОЙ ПРЕДОБРАБОТКИ ТЕКСТА ПРОЕКТНОЙ ДОКУМЕНТАЦИИ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ

О СОЧЕТАЕМОСТИ СЛОВ

Специальность - 05.13.12 « Системы автоматизации проектирования (информатика) (технические науки) ».

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

Научный руководитель: к.т.н., доцент Э.С. Клышинский

Москва - 2012

Оглавление

Введение......................................................................................................................................................3

ГЛАВА 1. Основы обработки текстов на естественном языке и прикладные системы....................11

1.1 Перспективные задачи в области обработки текстов проектной документации на естественном языке..............................................................................................................................11

1.2 Методы автоматической обработки текста..................................................................................12

1.3 Детерминированный и вероятностный подходы.........................................................................15

1.4 Наивный классификатор Байеса..................................................................................................18

1.5 N-граммный тэггер.........................................................................................................................19

1.6 Способы сокращения вычислений при морфологической разметке предложений.................21

1.8 Выбор тэггера на основе принципа максимальной энтропии (Maximum Entropy Principle) и методы оценки качества работы морфологических тэггеров...........................................................22

1.9 Сглаженные вероятностные N-граммные модели.......................................................................24

1.10 Другие виды вероятностных моделей снятия морфологической неоднозначности..............28

1.11 Деревья принятия решений и списки трансформаций..............................................................30

1.12 Обзор прикладных систем...........................................................................................................31

1.12.1 Модель Зеленкова-Сегаловича-Титова................................................................................31

1.12.2 Тэггер Чешских исследователей..........................................................................................35

1.12.3 Trigram А.В. Сокирко............................................................................................................37

1.12.4 Анализатор компании «Гарант-Парк-Интернет»...............................................................39

Выводы к Главе 1.................................................................................................................................40

ГЛАВА 2. Теоретические основы методов устранения неоднозначности в тексте на естественном языке..........................................................................................................................................................42

2.1 Модель морфологического анализа программы «Кросслятор».................................................42

2.2 Методы определения синтаксических связей между словами в предложении для сбора статистики совместного употребления слов......................................................................................49

2.3 Метод сбора статистики сочетаемости слов с использованием свойства синтаксического подчинения слов в предложении........................................................................................................54

2.4 Вероятностные правила снятия неоднозначности с использованием морфологических параметров............................................................................................................................................58

2.5 Декомпозиция предложения на сегменты при проведении предсинтаксического анализа.... 60

Выводы к Главе 2.................................................................................................................................63

ГЛАВА 3. Метод сбора статистики совместного употребления слов и комбинированный метод устранения морфологический неоднозначности в тексте проектной документации на естественном языке 64

3.1 Эксперимент по оценке уровня неоднозначности в текстах проектной документации и в текстах общей лексики.........................................................................................................................64

3.2 Метод выделения сочетаемости слов...........................................................................................66

3.3 Комбинированный метод снятия морфологической неоднозначности в тексте проектной документации на естественном языке................................................................................................73

1

3.4 Использование статистики совместного употребления слов для снятия частеречной омонимии..............................................................................................................................................76

3.5 Описание алгоритма устранения частеречной неоднозначности с использованием собранной статистики синтаксического подчинения слов..................................................................................77

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

3.7 Алгоритм итерационного применения вероятностных правил при недетерминированных соседях...................................................................................................................................................89

Выводы к Главе 3.................................................................................................................................96

ГЛАВА 4. Состав базы синтаксического подчинения слов и техническая реализация комбинированного метода устранения морфологической неоднозначности.....................................97

4.1 Состав базы синтаксического подчинения слов..........................................................................97

4.2 Качественные оценки работы комбинированного метода устранения морфологической неоднозначности.................................................................................................................................104

4.3 Выводы к Главе 4..........................................................................................................................108

Список используемой литературы........................................................................................................112

Введение

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

Эффективным и действенным средством решения обозначенных проблем выступают следующие информационные технологии: ILM (Information Lifecycle Management) и PLM (Product Lifecycle Management). Под этими технологиями понимается комплекс аппаратных и программных средств, обеспечивающих доступ к различным информационным ресурсам в процессе разработки продукта и выпуска сопутствующей документации по нему.

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

задаваемой пользователями. Решения на основе технологии ILM

3

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

Рисунок 1 Общий вид систем Information Life Cycle Management1

Жизненный цикл продукта можно описать следующими пятью основными этапами: разработка продукта; начало реализации продукта потребителям; совершенствование продукта; прекращение

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

- управлять созданием и обработкой документов;

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

- обеспечивать электронное хранение файлов;

- управлять служебными документами;

1 Рисунок взят с сайта http://-www.provost.ku.edu/infomanagement/info.shtml

4

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

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

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

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

Research

Performance Engineering

Usability Engineering

Performance Engineering

Maintenance

Product Development Life-cycle

Development

Testing & OA

Documentation

Рисунок 2 Общий вид систем Product Lifecycle Management2

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

2 Рисунок взят с сайта http://www.dbvdx.com/services__productLifecyclemanagement.html

обеспечение возможности групповой работы над проектом, исключение «пустых мест» - операций, за которые не отвечают конкретные отделы или люди. Коротко говоря, PLM-системы позволяют объединить техническую документацию на изделие и логистику.

Среди инструментов, необходимых для разработки, как самого продукта, так и выпуска сопутствующей документации можно выделить, например, следующие: текстовые процессоры; графические программы; программные пакеты по созданию и анализу таблиц и баз данных; программы, анализирующие требования к изделию и его рыночную стоимость; программы для электронной переписки. В задачи PLM и ILM систем входит анализ содержимого документов и обеспечение доступа к ним со стороны внешних программ, не касаясь напрямую того вопроса, какими средствами эти документы были созданы. Такие технологии позволяют отказаться от бумажных хранилищ текстовых документов. Развитие информационных технологий позволяет обеспечивать качественно новый подход по обработке электронной документации. В настоящее время производится интеллектуализация обработки текстовой информации среди таких задач как: выделение требований к изделию; поиск прецедентных документов; контроль структурной и информационной целостности документации; автогенерация документации; автоматический подбор компонентов изделия. Перечисленный круг задач далеко неполный и, до недавнего времени, решался лишь с помощью человека, без какой-либо автоматизации.

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

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

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

Для достижения цели данной диссертационной работы были поставлены и решены следующие задачи:

• Анализ существующих методов устранения морфологической неоднозначности;

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

• Разработка комплексного метода устранения морфологической неоднозначности с использованием статистики совместного употребления слов и лексических правил.

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

При решении задач, поставленных в диссертационной работе, получены следующие новые научные результаты:

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

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

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

Реализация и внедрение результатов. Описанные в данной работе алгоритмы и методы, реализованы автором в виде компьютерной подпрограммы, что позволяет подтверждать теоретические исследования в области моделирования естественного языка, а также использовать в машинном переводчике «Кросслейтор», разрабатываемом в ИПМ им. М.В. Келдыша РАН. Проведенные вычислительные эксперименты показали практическую эффективность предложенных подходов.

Апробация работы и публикации. Основные положения диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», Москва, МИЭМ, 17 февраля - 01 марта 2010.

• «Новые информационные технологии в автоматизированных

системах», МИЭМ, 25 марта 2010 года.

• Компьютерная лингвистика и интеллектуальные технологии ежегодная Международная конференция «Диалог» (2010).

• ХИ-ая Национальная конференция по искусственному интеллекту с международным участием.

• «Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ», Москва, МИЭМ, 17 февраля - 01 марта 2011.

• «Автоматическая обработка естественного языка», Санкт-Петербург, СпбГУ, 26-ое марта 2011.

Основное содержание диссертационной работы и ее результатов отражено в следующих научных и научно-технических работах автора: всего автором опубликовано 6 научных работ из них 2 в журнале из перечня ВАК.

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

Основные научные результаты, выносимые на защиту:

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

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

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

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

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

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

ГЛАВА 1. Основы обработки текстов на естественном языке и

прикладные системы

1.1 Перспективные задачи в области обработки текстов проектной документации на естественном языке.

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