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

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

00^430"-

Степанова Надежда Александровна

МОДЕЛИРОВАНИЕ ПРОЦЕССА АВТОМАТИЧЕСКОГО ИЗВЛЕЧЕНИЯ ЗНАНИЙ В ВОПРОСНО-ОТВЕТНЫХ СИСТЕМАХ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

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

2008

Москва - 2008

003458221

Работа выполнена в Государственном образовательном учреждении "Новгородский государственный университет им. Ярослава Мудрого"

доктор технических наук, профессор Емельянов Геннадий Мартинович

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

кандидат физико-математических

наук, профессор

Козырев Олег Рамазанович

Государственное учреждение «Научно-исследовательский институт прикладной математики и

кибернетики Нижегородского

государственного университета им. Н. И. Лобачевского».

Защита состоится 29 декабря 2008 г. в 12.00 часов на заседании диссертационного совета Д 212.048.09 при Государственном университете -Высшей школе экономики по адресу: 105187, Москва, ул. Кирпичная, д. 33/5.

С диссертацией можно ознакомиться в библиотеке Государственного университета - Высшей школы экономики по адресу: 101990, Москва, ул. Мясницкая, д. 20.

7%

Автореферат разослан " ^ " ноября 2008 г.

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

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

Ведущая организация:

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

д.т.н., доцент В.А. Фомичев

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

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

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

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

В настоящее время одними из самых распространенных лексических ресурсов являются пополняемые вручную компьютерные словари, построенные по модели \УогсЗ№1. Несмотря на высокий уровень развития современных лексических баз данных, область их покрытия остается узкой, особенно для русскоязычных лексических ресурсов, поэтому разработка лексических ресурсов, специализированных для ВОС, на данном этапе развития технологий ОЕЯ должна опираться на автоматическое извлечение знаний из корпусов текстов.

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

Цель и задачи работы. Целью настоящей диссертационной работы является разработка модели автоматического извлечения знаний из неструктурированного текста на ЕЯ для повышения эффективности работы ВОС. Для достижения поставленной цели в работе решаются следующие задачи:

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

использования в ВОС, формулирование требований к лексическим ресурсам, необходимым для ВОС;

2. Построение модели лексикона и модели семантических отношений в лексиконе для ВОС;

3. Разработка алгоритма сегментации лексикона и формирования классов схожих лексем;

4. Разработка методов классификации вопросов, снятия семантической многозначности для ВОС;

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

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

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

1. Разработана модель Концептно-Ориентированного Лексикона (КОЛ), представленного решеткой формальных понятий, толкование лексического значения получено в виде содержания формальных понятий решетки, а сами лексемы представлены в объеме формальных понятий;

2. Впервые предложена модель автоматического извлечения знаний из неструктурированного текста на ЕЯ на основе формализации семантики генитивной конструкции на языке интенсиональной логики, знания представлены формальными понятиями в КОЛ;

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

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

5. В результате вычислительного эксперимента выполнено оценивание полноты и репрезентативности исходного текста на ЕЛ, используемого для пополнения лексикона, выработаны общие требования, предъявляемые к таким текстам, а также получена количественная оценка КОЛ относительно эталонного лексического ресурса.

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

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

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

Разработанный программный комплекс позволяет провести исследование каждого этапа извлечения знаний и формирования КОЛ, что позволяет внедрить его в учебный процесс НовГУ.

Результаты проведенных исследований использовались в работе по гранту РФФИ № 06-01-00028.

Достоверность и эффективность. Достоверность полученных теоретических результатов подтверждается серией вычислительных экспериментов, демонстрирующих автоматическое формирование и пополнение КОЛ на основе различных текстов на ЕЯ.

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

Апробация работы и публикации. Основные положения и полученные результаты диссертационной работы апробированы в докладах на международных конференциях: DC-я международная конференция «Cognitive Modeling in Linguistics» (София, Болгария, 2007), 7-я международная конференция «Pattern Recognition and Image Analysis: New Information Technologies» (С.-Петербург, 2004), 6-я международная научно-техническая конференция «Interactive Systems And Technologies: The Problems of HumanComputer Interaction» (Ульяновск, 2005), 2-я международная конференция IASTED «Automation, Control, and Information Technologies» (Новосибирск, 2005), Vl-й международный конгресс по математическому моделированию (Нижний Новгород, 2004), 7-я международная научно-техническая конференция «Interactive Systems And Technologies: The Problems of HumanComputer Interaction» (Ульяновск, 2007) и на Всероссийской конференции «Математические методы распознавания образов ХП1» (г. Зеленогорск, 2007), а также опубликованы в 8 работах, список которых приводится в конце автореферата.

Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы, включающего 144 наименования. Основная часть работы изложена на 156 страницах, содержит 21 рисунок и 7 таблиц.

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

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

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

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

Показано, что подход на основе Интенсиональной Логики (ИЛ) и грамматики Монтегю является наиболее приемлемым для формализации семантики ГК. В качестве основы для формализации ГК используются сорта и сортовые сдвиги, формализация семантики всех ГК осуществляется по единой схеме, опорное существительное всегда рассматривается как реляционное.

Выполнен анализ существующих методов и подходов к кластеризации значений слов, извлечению семантических отношений и разрешению многозначности. Предложен теоретико-решеточный подход к моделированию лексикона на основе записи ГК на языке ИЛ.

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

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

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

В разделе 1.5 предлагается использовать теоретико-решеточный подход к моделированию лексического значения, извлекаемого из теорий сортов ГК. Приводятся основные определений теории решеток.

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

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

Во второй главе описываются методы построения решетки формальных понятий на основе ГК, извлекаемых из неструктурированного текста. Описана формализация ГК на языке ИЛ. Получены выражения для записи теории лексемы и теории сорта, принадлежности лексемы к сорту.

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

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

В разделе 2.2 разрабатывается формальная модель ГК на языке ИЛ. ГК состоит из опорного слова (главное существительное), генитивной группы (зависимое существительное) и Генитивного Отношения (ГО) между опорным словом и генитивной группой. В ИЛ собственные имена относятся к типу <е>. Вне ГК опорное существительное задается функцией Лх[5(д:)] (для нереляционных существительных) или ЛхуГ^МЫ]. (для реляционных существительных). Именная группа русского языка принадлежит к типу «е, />, /> и обозначается функцией ЛР[Р(с)] (абстрактор высших порядков), где с -индивидная константа типа <е>. Данное множество предикатов можно интерпретировать как множество свойств, которыми обладает индивидная константа типа <е>. Формула и<-> ар, [у/>,(*)] задает множество постулатов

значения, описывающих теорию нереляционного опорного существительного, соответствующего лексеме V/, где м> - сущность типа <е>, Р, - предикаты типа <е, />. Тип лексем всегда совпадает с типом сорта, к которому относятся эти лексемы. Теория сорта состоит из набора свойств, связанных логическими операциями. Если mng{w) = АР[Р(х)] - значение лексемы >е, а 7, - теория сорта и лексема м принадлежит сорту я, то

3 Т, (ЛР[В2(Р(г) л 0Лг(Р(х) -> Т, (г)«)))]) (1)

Будем обозначать через fss(w) набор свойств лексемы w, принадлежащих сорту j. При описании семантики генитивной группы будем использовать подход:

Gg = XyXR[txlR{y){x)}], (2)

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

Для формализации семантики ГК необходимо задать формальное описание оператора метонимического сдвига, смещающего опорное существительное типа <е, t> к типу реляционного существительного <е, <e,t». Второй функцией оператора сдвига является связывание опорного существительного и генитивной группы для формирования правильной ГК. Сорта si и s2 удовлетворяют селективным ограничениям оператора сдвига Sft, если Tsi*~* Т;2 или существует сорт s, приемлемый для Sft, что Тл -» Т, л Тп Г,, где Tsi, TS2, Ts, - теории сортов si, s2, s соответственно.

Принятый в данной работе подход на основе компонентного анализа не предполагает разложения значения лексемы до элементарных семантических элементов, поэтому невозможно требовать, чтобы теории сортов si, s2 содержали общее элементарное свойство. Однако это общее свойство Р должно выводиться из теорий Tsi и Ts2:

AP[3T(3z(P(z) Л V*(7-(JC) Р(х)) л V*l(7-„(*1) ?(xl)) л Чх2(Т,г(х2) Р(х2))))] (3)

Сопряжение в ГК достигается за счет ГО. Будем задавать ГО через постулаты значения. ГО полностью определяется сортом ГК и имеет тип <е, <e,t».

Оператор сдвига конструируется из теории опорного слова и ГО и имеет тип <e,<e,t>>:

Sft = ЛаЛЬ[Я1е„ (a)(b) л (fs, (w))] ^ (4)

где w - лексема, соответствующая опорному слову, we Sort,, Rge„ - теория ГО. Применяя эту функцию к выражению для генитивной группы (2), получим выражение для ГК:

= где - лексема

существительного генитивной группы, w, - " лексема опорного существительного. Последовательно применяя оператор лямбда-конверсии, получим формулу, описывающую семантику ГК на языке ИЛ:

Gc = НХаЩЯ1е„{а){Ъ) A(ÄK))](^g(we)Xx)] (5)

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

В разделе 2.3 выполняется сопоставление выражений ИЛ для записи семантики ГК и элементов теории решеток. Свойства ЯР[Р(х)] (толкование)

опорного существительного не могут извлекаться непосредственно из текста, поэтому встает задача извлекать это толкование опосредованно на основе дополнительного анализа значений элементов ГК. Пусть Gel и Gc2 ГК такие, что Gel е Sortt и Gc2eSorit, их ГО Rlgt„ и R2ge„ полностью определяются сортами ГК, поэтому Rlgc„=R2ge„ и на сорта существительных GelJ Gel gg и Gc2JGc2u должны накладываться одинаковые селективные ограничения. В этом случае из формулы (3) следует, что теории опорных существительных (или генитивных групп) должны содержать общее свойство Р. Пусть wl и w2 лексемы, соответствующие Gel ¡к Gc2„ и сорта опорных существительных si и s2, что wl £ Sort^ и w2 6 Sorts2. Теорию лексемы wl обозначим через набор свойств PI (mng(w,) = ЛР1[?1(х)]), и аналогично mng(w2) = ЛР2[Р2(х)]. Теории wl и w2 в общем случае не будут совпадать, однако из них будет обязательно следовать общее свойство Р по формуле (3). Рассматривая теории wl и w2 только как это общее свойство Р, из формулы (1) получим выражение для двух опорных существительных, используемых в ГК одного сорта: I/>l[Hzl( Л(г1)л (V*l(/>1(jrl) -> />(zl)(il))))] л ЯP2[3z2(P2(z2) л (Vx2(P2(x2) -> />(г2)(*2))))] (6)

Формула (6) означает, что, выбирая из текста ГК, принадлежащие к одному сорту и имеющие различные опорные существительные, сравнивая значения этих опорных существительных, получим общую часть их значения, описываемую общим свойством Р (аналогично для существительных генитивной группы). С некоторой вероятностью ГК относятся к одному сорту при совпадении форм опорных существительных или генитивных групп.

При извлечении Р из текста возможно оперировать только формами опорного существительного и генитивной группы. Пусть V, - множество форм опорных существительных и v, е V,, Vgg - множество существительных генитивных групп и vffi бИв, Упорядоченная пара (vgg, vj называется правильной генитивной конструкцией, если найдется оператор сдвига Sft, такой, что сорта лексем, соответствующих v, и vgg, удовлетворяют селективным ограничениям оператора сдвига Sft.

Бинарным отношением I назовем множество пар (vgg,vj правильных ГК и IczV^xV,. Запись vggIvs означает, что при синтаксическом разборе текста

выделена ГК с опорным существительным vs и существительным генитивной группы v^ такая, что при подстановке лексем, соответствующих и vgg, в формулу (5) будет получена правильная ГК определенного сорта. Отношение 1 может быть представлено в виде формального контекста K=(Vgg, VS,I). Опорные существительные рассматриваются как признаки объектов, означающие, что объекты имеют общие свойства. По формальному контексту К с заданным отношением порядка может быть построена полная решетка формальных понятий 23 (Vgg, VS,I). На Рисунке 1 перечислены примеры русских ГК меры и соответствующий им формальный контекст.

Ящик яблок Бутылка воды Коробка печенья

Ящик конфет Бутылка вика Тарелка картошки

Стакан воды Бутылка шва Мешок яблох

Стакан вина Банка пива Мешок конфет

Стакан пива Банка воды Мешок картошка

Ведро воды Коробка конфет

А с р О н

Яблоко к те?... р . X

Конфета 9 X

Воде X х X

Вино Я я

Орпи X

П«ч»иь» X

Кзртошм X X

Пию X X х

Рисунок 1. Генитивные конструкции и формальный контекст.

Решетка формальных понятий ¿£>(¥^¥¡,1) представлена на Рисунке 2 в виде диаграммы линий.

Рисунок 2. Формальная решетка на основе ГК меры.

Формальное Понятие (ФП) (А, А') характеризуется объемом и содержанием. Для ФП, обозначенного на диаграмме как ФП1, объем - А={Пшо, Вода}, содержание А' ={Банка, Бутылка, Стакан}. Все объекты из объема ФП обладают набором общих свойств А', которые описываются признаками из содержания ФП. Набор признаков - это толкования значений соответствующих слов из объема ФП. Таким образом, через генитивные конструкции из неструктурированного текста происходит извлечение знаний, представленных формальными понятиями. Отношение порядка решетки (<) задает иерархию объектов и признаков решетки. По решетке возможно выделять объекты, относящиеся к одному сорту на основе отношения порядка. Решетка формальных понятий представляет собой лексикон, который далее возможно использовать в ВОС.

В разделе 2.4 вводится критерий полезности решетки, для максимизации которого контекст K=(V№V¡,I) расширяется до Kg=(V№ fs u Vg ,1), где Vg -множество глаголов, в модели управления которых ПС занимает место одного из актантов. Критерий полезности описывается коэффициентом F:

где J - индексное множество цепочек, jeJ- номер цепочки, n¡ - количество ФП в цепочке j, i - порядковый номер ФП (A¡, B¡) в цепочке, / - коэффициент взаимной зависимости, mgí* - глагольный признак mg, который непосредственно относится к i-му ФП (A¡, B¡) и имеет номер к среди всех глагольных признаков К, непосредственно принадлежащих ФП (A¡, B¡), Ge, - t-я генитивная конструкция из набора генитивных конструкций, получаемых из ФП (A¡, B¡). Для повышения полезности решетки и максимизации коэффициента F необходимо включать в формальный контекст глаголы с сильными селективными ограничениями.

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

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

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

В разделе 3.3 предлагается метод вычисления меры схожести для ФП C¡ и Q решетки:

jpc(C#,C,) = -log(l—*L)x-Щ-,

'' ЪК path/ + + (8)

где ФП С=(А,В) - Наибольшее Общее Суперпонятие (НОСП) для формальных понятий Ci=(A¡,B¡) и Cj=(Aj,Bj), D(X,C)~ кратчайшее расстояние между ФП С и 1, Dc - кратчайшее расстояние между ФП С и Т, paíhc = Dc+D( 1, С).

В разделе 3.4 приводится алгоритм сегментации решетки для целей выделения интерпретируемых классов (сортов). Результатом работы алгоритма сегментации является набор классов ФП {L}, также являющихся решетками. Классы максимальны по количеству элементов, количество элементов классов не задается перед началом работы алгоритма. Критерием выделения решетки L, б {L'} из первоначальной формальной решетки L является условие, что каждое ФП С е L, более схоже с другими формальными понятиями из решетки

Ь,, чем с формальными понятиями из решеток е {!'}, что Щ. Итоговый алгоритм сегментации решетки описывается так:

Шаг 0. Получить из размеченного корпуса текстов формальный контекст сгенерировать на его основе формальную решетку Ь;

Шаг 1. В массив ЬС8_Аггау записать все формальные понятия Се Л, что СчТ;

Шаг 2. Для каждого ФП С, из ЬСБ_Аггау, где 1=1 до М (М - количество элементов массива ЬС8_Апау);

Шаг 2.1. Пусть Ц - /-ый класс формальных понятий, тогда 1,:= С, ;

Шаг 2.2. Для каждого ФП Су, что Су<С, и Су#±, где /=7 до И] (Щ - количество

подпонятий ФП С,);

Шаг 2.2.1. Если для каждого С„ е I, что С1 -< С„, также выполняется СШ<С„ то ¿¡:= 1(+Су и пропустить Шаг 2.2.2 и Шаг 2.2.3, иначе отметить С, как спорное ФП и выполнить Шаг 2.2.2 и Шаг 2.2.3;

Шаг 2.2.2. Для спорного ФП С, вычислить й]:=Брс(С}, Сщ) и равное максимальному из значений ¡рс(Ср С>), где Ь - номер ФП, что выполняется CJ<CI, и СЛ<С,.

Если (¡¡=й2, то сравнить количество (с1'2) ФП в области, где НОСП является ФП С,-, и количество (ФП в области, где НОСП является ФП Си< Т и Ст<,См, и количество ФП максимально по сравнению с другими областями, к которым принадлежит ФП Ст. Если £ то выполнить Шаг 2.2.2.1, иначе выполнить Шаг 2.2.2.2.

ЕСЛИ </г></;, ТО

Шаг 2.2.2.1. Вариант 1: для каждого из объектов а1 из "объемов ФП, меньших либо равных Су. выполнить а) - г):

а) добавить в формальный контекст Ке два объекта: а1 и а,_Ви, где Сы=(Ам,Вм), См*ТнСа<См;

б) добавить в формальный контекст К^ отношения а,_В,11Ь, для каждого Ь, е В1 такое, что также выполняется Ъщ е Вг для каждого ФП СГ=(АГ,ВГ), что О<С, и С1<СГ, и отношения а1_Ви11Ьг для каждого Ьр еВ1 такое, что также выполняется Ьге£щ;

в) для каждого признака Ьр 6 Вр из подмножества признаков с Я, содержания формальных понятий Ск, таких, что и С*<Су, выполнить:

• добавить в формальный контекст Кг два признака Ь1Ш_ 1 и 2, если такие признаки не были добавлены на предыдущих итерациях данного Шага;

• добавить в формальный контекст отношения а1__В111Ь/а_ 1 и а1_Ви1[Ь1с_2, если такие признаки не были добавлены на предыдущих итерациях данного Шага;

• добавить в формальный контекст Kg отношения 0,7,6^ _1 и а,1гЬр_2 для всех объектов а, из объема подпонятий ФП Q, если они уже не содержатся в контексте Ке\

• отметить признак Ь^ и все отношения этого признака с объектами контекста Kg на удаление;

г) отметить объект а, и все отношения этого объекта со всеми признаками контекста/^ на удаление.

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

Шаг 2.2.2.1. Вариант 2: для каждого признака bJ е Bt, C]=(Aj,BJ, для которого также выполняется е Вт, удалить из формального контекста Kg отношение 1е для признака Ьп что а11гЬ! для всех объектов at из объема ФП Cj (полное переформирование решетки L не требуется, возможно только необходимо объединить ФП С, с ФП Си, если после удаления из контекста признаков выполняется Bj=Bh), иначе если dj>d2, то

Шаг 2.2.2.2. Вариант1: Аналогично Шаг 2.2.2.1, Вариант 1. Шаг 2.2.2.2. Вариант 2: для каждого признака Cj=(Aj,BJ, для которого

также выполняется Ь1 е в, для каждого ФП Сг=(АпВг), что О < С,, выполнить: удалить из формального контекста Kg отношение 1г для признака Ь:, что а11Ъ1 для всех объектов а; из объема ФП С/,

(полное переформирование решетки L не требуется, возможно, иногда необходимо объединить ФП Cj с ФП Сш, если после удаления из контекста признаков выполняется Bj=Bm).

Шаг 2.2.3. Если на Шаге 2.2.2 для каждого С, е L выполнялось только условие di>d/ и Вариант 2, то £,:= L,+Cp иначе, если выполнялся Вариант 1 и условие d2>di или di>d2, то после переформирования первоначальной решетки найти в ней ФП с объемом, в котором содержатся все объекты at_Bn где а1&А1 и Cj=(Aj,Bj) - спорное ФП первоначальной решетки. Далее выполнять алгоритм по переформированной решетке.

Шаг 3. К множеству формальных понятий L, добавить наименьшее ФП 1. Добавить решетку L, к итоговому множеству формальных решеток {L }.

В четвертой главе описываются методы поиска ответов в ВОС с помощью КОЛ. Анализируется представление в КОЛ лексики различных типов. Рассматривается метод снятия семантической омонимии слов в объеме формальных понятий.

В разделе 4.2 описываются архитектура типовой ВОС и модули системы, в которых происходит обращение к лексическим знаниям. На Рисунке 3 представлена диаграмма потоков данных типовой ВОС. ■

Рисунок 3. Диаграмма потоков данных типовой ВОС.

В разделе 4.3 рассматриваются два подхода к классификации вопросов: классификация по форме ответов и семантическая классификация ответов. Семантическая классификация вопроса задает семантический класс, к которому должны принадлежать вопрос и набор ответов. Чем выше детализация семантических классов, тем более точно можно сравнить вопрос и ответ, поэтому использование специализированного, пополняемого в автоматическом режиме и содержащего детальные семантические классы лексикона является преимуществом ВОС. Рассмотрено применение КОЛ при сопоставлении семантического класса вопроса с извлеченными из поисковой системы параграфами, которое учитывается ВОС при определении оценок параграфов. Семантический компонент в оценке параграфов вычисляется по формуле:

ЗетТуре _ зсоге =

\,еслиС. = С

в Ч

8рс, (С.,С,),еслиС, < С,шшС„ > С, ттСЗрс^ (С„,С),5рс1ч(С,,С)),еслиВС б I, |

С, <С&С„ <С&ЭС,|С1 <С&С, <С, &С„ <С,

(9)

где q - главное ключевое слово вопроса, а - ключевое слово ответа в параграфе, С, = 0?".?'), С„=(а*,а'), L„ - решетка КОЛ, SpcL (C„Cr) - мера схожести между ФП С, и Су, нормированная к максимальному значению меры схожести для всех ФП решетки L„, ФП С - НОСП ФП С, и С„.

В разделе 4.4 исследуются свойства КОЛ. Анализируется специфика представления в КОЛ собирательных и абстрактных существительных. В решетке формальных понятий собирательные существительные и соответствующие им конкретные существительные не связаны отношением порядка. Показано, что для ВОС отсутствие отношения порядка позволяет использовать собирательные существительные при сопоставлении типа вопроса и ответа по формуле (9). Проверка объема покрытия абстрактных существительных выполнена относительно списка существительных, обозначающих эмоции, из частотного словаря Шарова. Степень покрытия КОЛ, построенного на основе ГК, извлеченных из корпуса «Классика» библиотеки Мошкова, составляет 94%. Показано, что ФП, к объему которых принадлежат абстрактные существительные, образуют в КОЛ классы, которые возможно выделить с помощью алгоритма сегментации решетки.

Для использования КОЛ в ВОС разработан метод снятия семантической омонимии слов в объеме формальных понятий, который предполагает работу алгоритма сегментации по Варианту 1. Работа алгоритма сегментации по Варианту 2 позволяет получить наборы классов формальных понятий, при этом суммарное количество ФП в этих классах будет меньше, чем в первоначальной решетке из-за удаления отношений между некоторыми объектами и признаками.

В разделе 4.5 описываются дополнительные методы использования КОЛ в ВОС: расширение ключевых слов вопроса, обработка собственных имен в вопросах и ответах, удаление избыточности в ответах.

В пятой главе выполняется экспериментальная проверка модели извлечения знаний для ВОС. Формулируются требования по полноте и репрезентативности, предъявляемые к корпусу текстов, используемому для построения на его основе КОЛ. Анализируются алгоритмы генерации решетки, выбирается наиболее эффективный для генерации КОЛ. Выполняется оценка КОЛ.

В разделе 5.2 показано, что распределение частоты встречаемости ГК соответствует закону Ципфа по формуле (10) для достаточно больших текстов русского языка.

log(/=') = c-AIog(r), (10)

где F- частота встречаемости слова, г - ранг слова в частотном распределении, с и ¿-константы, специфические для каждого ЕЯ.

На Рисунке 4 представлен график распределения частот употребления ГК для текста различного объема (текст №1-4 млн. слов, текст №2 - 8 млн. слов, текст №3 - 16 млн. слов, текст №4 - 25 млн. слов, текст №5 - 34 млн. слов, текст №6 - 41 млн. слов, текст №7 - 50 млн. слов, текст №8 - 85 млн. слов).

Рисунок 4. Распределение частот употребления ГК для текста различного

объема.

Согласно закону Ципфа, объем корпуса текстов для построения на его основе КОЛ должен быть не менее 50 млн. слов. Серия экспериментов доказывает, что с увеличением объема используемого корпуса текстов снижение репрезентативности этого корпуса не происходит, при этом покрытие слов, используемых для построения КОЛ, примерно соответствует всему лексикону русского языка.

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

Набор

Рисунок 5. Схема обмена данными между модулями программного комплекса.

В Таблице 1 дано краткое описание модулей программного комплекса.

Наименование модуля Описание модуля

Dwarf Программа синтаксического разбора «Cognitive Dwarf», разработка компании ООО "Когнитивные технологии". Используется для построения дерева синтаксического разбора для текста на русском языке.

Gen_Gc Программа для извлечения четверок (Verb, Fn, Ga, Free) из дерева синтаксического разбора.

LatticeBuild Программа для генерации решетки формальных понятий по контексту.

LatticeSegment Программа для сегментации решетки формальных понятий на классы формальных понятий. Входной параметр задает работу алгоритма сегментации по Варианту 1 или по Варианту 2.

Таблица 1. Описание модулей программного комплекса.

Для генерации решетки формальных понятий используется комбинация двух инкрементальных алгоритмов Ferre и Norris. Выбор'алгоритмов генерации решетки формальных понятий выполнялся с учетом параметров формального контекста. Результаты оценки параметров расширенного формального контекста, построенного по полному корпусу «Классика» (85 млн. слов) только с участием ГК с частотой выше 0,00005, приведены в Таблице 2.

Описание параметра Значение параметра

Количество объектов, (|С|) 5974

Количество признаков, 193580

Размер контекста, (|/|=|С|х\М\) 1156446920

Среднее количество признаков на один объект 32,4037

Максимальное количество признаков на один объект 6473

Таблица 2. Параметры расширенного формального контекста.

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

Проведена оценка сложности алгоритма сегментации решетки, сложность описывается формулой (11):

0(\L?-\og(\L\)-p), (11)

где L - первоначальная решетка, сегментация которой выполняется, р -максимальная длина цепочки в решетке L.

В разделе 5.4 предложена методика оценки построенного КОЛ относительно эталонного лексического ресурса по двум критериям: точность (Precision) и степень охвата (Recall). В качестве эталонного лексического ресурса используется словарь синонимов Н. Абрамова, имеющий область покрытия 19108 статей. Экспериментальная оценка для 50-ти наиболее частотных лексем показала: Recall=24,36% и Precision=9,78%. Низкое значение точности обусловлено большим покрытием лексики в КОЛ относительно эталонного лексического ресурса. Степень охвата КОЛ примерно соответствует результатам аналогичных работ для английского языка.

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

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

• разработка методов интеграции КОЛ, содержащего только существительные русского языка, с другими лексическими ресурсами для расширения области охвата лексиконом других частей речи;

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

• включение в расширенный формальный контекст дополнительно к элементам генитивной конструкции и глаголам других^ частей речи;

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

III. Основные результаты диссертационной работы

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

2. Сформулированы требования к лексическим ресурсам для ВОС. Разработана модель KOJI, представленного решеткой формальных понятий, отвечающая этим требованиям. Толкование лексического значения получено в виде содержания формальных понятий решетки, а сами лексемы представлены в объеме формальных понятий.

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

4. Предложен критерий полезности решетки КОЛ для извлечения лексического значения, а также разработан метод максимизации этого критерия.

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

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

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

8. Предложена методика оценки КОЛ относительно эталонного лексического ресурса, а также критерий полезности решетки КОЛ для целей извлечения лексического значения, получена экспериментальная оценка КОЛ.

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

Работы, опубликованные автором в ведущих рецензируемых научных

журналах и журналах рекомендованных ВАК Министерства образования и

науки России:

1. Stepanova N. A. Analysis of Semantic Relations in Classification of Sense Images of Statements // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications, EDITOR-IN-CHIEF: Yuri I. Zhuravlev, Vol. 17, No. 2, 2007, pp. 274-278. 0,3 p.l. (CO-AUTORSHIP: Emel'yanov G. M., Mikhailov D. V.; autor's part 0,2 p.l.).

Другие работы, опубликованные автором по теме кандидатской

диссертации:

2. Степанова Н.А. Анализ семантических отношений в задаче классификации смысловых образов высказываний // Труды международного семинара PRIA-7-2004 по распознаванию образов и обработке изображений. - Т.П. -С.-Петербург, 2004. - С. 460-461. 0,2 п.л. (в соавторстве Емельянов Г.М., Михайлов Д.В.; вклад автора 0,1 п.л.).

3. Степанова Н. А. Формирование и кластеризация понятий в задаче распознавания образов в пространстве знаний // Математические методы распознавания образов: 13-я Всероссийская конференция, Ленинградская обл., г. Зеленогорск: Сборник докладов. - М.: МАКС Пресс, 2007. - С. 206209. 0,2 п.л. (в соавторстве Емельянов Г.М.; вклад автора 0,1 п.л.).

4. Stepanova N.A. Model of types in intensional logic // Interactive Systems And Technologies: The Problems of Human-Computer Interaction. - Collection of scientific papers. - Ulyanovsk: U1STU, 2005, pp. 66-71. 0,3 p.l. (CO-AUTORSHIP: Emel'yanov G. M.; autor's part 0,2 p.l.).

5. Stepanova N.A. Semantic relation modeling using Formal Concept Analysis in Russian lexical databases // In proceeding of the Second IASTED International Multi-Conference on Automation, Control, and Information Technologies, Novosibirsk, Russia, 2005, pp. 9-12. 0,4 p.l. (CO-AUTORSHIP: Emel'yanov G. M.; autor's part 0,3 p.l.).

6. Stepanova N.A. Application of the computer thesaurus for automation of updating of the government patterns's dictionary // In proceeding of VI International Congress on Mathematical Modeling, Nizhny Novgorod, Russia, Sept 20-26, 2004, p. - 352. 0,1 p.l. (CO-AUTORSHIP: Emel'yanov G. M., Mikhailov D. V.; autor's part 0,1 p.l.).

7. Stepanova N.A. Concept-oriented lexicon application for Question Answering systems // Interactive Systems And Technologies: The Problems of HumanComputer Interaction. - Collection of scientific papers. - Ulyanovsk: U1STU, 2007, pp. 31^10. 0,5 p.l. (CO-AUTORSHIP: Emel'yanov G. M.; autor's part 0,4 p.l.).

8. Stepanova N. Knowledge acquisition process modeling for question answering systems // Cognitive Modeling in Linguistics: Proceedings of the IX-th International Conference CML-2007, Sofia (Bulgaria) / Edited by V. Solovyev, R. Potapova, V. Polyakov - Kazan: KSU, 2007, pp. 344-354. 0,8 p.l. (CO-AUTORSHIP: Emel'yanov G. M.; autor's part 0,7 p.l.).

Лицензия ЛР № 020832 от 15 октября 1993 г. Подписано в печать 26 ноября 2008 г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тирах 100 экз. Заказ

Типография издательства ГУ-ВШЭ 125319, г. Москва, Кочновский пр-д, д. 3

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

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

1.1 Общие положения.

1.2 Лексическое значение.

1.2.1 Компонентный анализ н постулаты значения.

1.2.2 Отношения синонимии, антонимии, гипонимии.

1.2.3 Полисемия.

1.2.4 Толкование лексического значения.

1.3 Анализ методов обработки корпуса текстов.

1.4 Метод формализация семантики генитивной конструкции.

1.4.1 Интенсиональная логика.

1.4.2 Теория сорта н сортовые сдвиги.

1.5 Теория решеток.

1.6 Анализ существующих методов классификации и разрешения многозначности.

1.7 Выводы по главе 1.

Глава 2 Модель концептно-ориентированного лексикона на основе генитивных конструкций.

2.1 Постановка задачи.

2.2 Формализация семантики генитивной конструкции.

2.3 Генитивная конструкция в решетке формальных понятий.

2.3.1 Анализ формальных понятий.

2.3.2 Формальная решетка генитивных конструкций.

2.4 Критерий полезности решетки.

2.5 Модель семантических отношений порядка в решетке.

2.6 Выводы по главе 2.

Глава 3 Метод разбиения решетки для извлечения сортов и снятия семантической многозначности.

3.1 Общие положения.

3.2 Семантическое расстояние.

3.2.1 Семантическая близость.

3.2.2 Семантическая схожесть и связность.

3.3 Мера схожести в решетке формальных понятий.

3.4 Алгоритм сегментации решетки.

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

Глава 4 Методы поиска ответов в ВОС с помощью Концептно-ориентированного Лексикона (КОЛ).

4.1 Общие положения.

4.2 Архитектура типовой ВОС.

4.3 Классификация вопросов.

4.4 Исследование свойств концептно-ориентированного лексикона.

4.4.1 Собирательные и абстрактные существительные в решетке формальных понятий.

4.4.2 Снятие семантической многозначности в концептно-ориентнрованном лексиконе.

4.5 Методы использования концептно-ориентированного лексикона в ВОС

4.6 Выводы по главе 4.

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

5.1 Общие положения.

5.2 Описание используемого корпуса текстов и методов его обработки.

5.2.1 Оценка качества исходных данных.

5.2.2 Описание требований к корпусу текстов.

5.3 Описание программного комплекса.

5.3.1 Выбор алгоритма порождения формальных понятий.

5.3.2 Оценка сложности алгоритма сегментации решетки.

5.4 Испытания программного комплекса.

5.5 Выводы по главе 5.

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

Для поиска ответа могут использоваться коллекции документов, например, из сети Интернет, или локальные хранилища информации. Узкоспециализированные ВОС работают в конкретных областях (медицина, юриспруденция и т.д.), а общие - по всем областям знаний. Построение общих ВОС является более сложной и менее проработанной задачей, хотя подобные системы имеют широкое применение и позволяют вести поиск в смежных областях знаний. Методы поиска ответа в ВОС могут использоваться в системах тестирования с открытым ответом, оценивая близость полученного и эталонного ответов. Вопросно-ответные системы в настоящее время встраиваются в состав комплексных информационных систем, например, в [122] описано взаимодействие вопросно-ответной системы NetWIQA и Rational Unified Process - методологии создания программного обеспечения, оформленной в виде размещаемой на Web базы знаний, которая снабжена поисковой системой.

Первые ВОС были разработаны в 1960-х годах и являлись естественноязыковыми оболочками для экспертных систем, ориентированных на конкретные области знаний. Современные разработки позволяют обрабатывать множество вариантов запросов: дихотомические вопросы, вопросы-факты, вопросы-списки, вопросы-определения, вопросы типа «Как», вопросы типа «Почему», гипотетические вопросы (что-если), межъязыковые вопросы, контекстные вопросы.

Последние исследования в области ВОС стимулируются специальными программами (AQUAINT1 ) и специализированными соревнованиями (TREC22, NTCIR33, CLEF44, РОМИР55). Необходимость работать с большими объемами текстовой информации заставляет крупные компании создавать собственные ВОС, например, исследовательские группы из Microsoft, IBM, NTT, Oracle [40], Sun ежегодно принимают участие в соревновании TREC. Сложность специализированных соревнований растет год от года. Так, в 1999 году на соревновании TRJEC системы участников в качестве ответа должны были выдать кусочки текста, содержащие ответ, вопросы составлялись участниками самостоятельно, а ответы гарантированно содержались в корпусе текстов. В 2004 году вопросы уже извлекались из журналов регистрации запросов к реальным поисковым системам, ответ не обязательно содержался в корпусе текстов и системы должны были выдать точный ответ на запросы фактов и списков.

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

Типовая архитектура современных ВОС состоит из модулей (Рисунок 1). На самой ранней стадии работает модуль — анализатор вопросов, который определяет тип вопроса и, соответственно, ожидаемого ответа, а

1 www.ic-arda.org/InfoExploit/aquaint/index.html

2 trec.nist.gov

3 research.nii.ac.jp/ntcir/index-en.html

4 clef.iei.pi.cnr.it

5 romip.narod.ru/ также расширяет список ключевых слов вопроса за счет слов, связанных с ключевым словом. Например, вопрос «Какая страна является ведущим поставщиком газа?» должен быть классифицирован как МЕСТОПОЛОЖЕНИЕ, т.к. ожидаемый ответ связан с местоположением. При определении типа вопроса на практике система часто сталкивается с различного рода неопределенностями, вызванными помехами и дефектами процесса предикации, поэтому необходимо использовать специальную методику идентификации и кодирования вопросов [34].

Вопрос

Ответы

Рисунок 1. Типовая архитектура вопросно-ответной системы.

Выполнив анализ вопроса, система может выполнять поиск ответа по двум направлениям: локальное хранилище ответов и поиск ответа в корпусе текстов. Локальное хранилище ответов содержит ответы на наиболее вероятные вопросы, причем поиск ответов осуществляется на подготовительном этапе, еще до того, как фактические вопросы были заданы. Решение использовать корпус текстов основывается на типе вопроса и отсутствии необходимой информации в хранилище ответов. При работе с корпусом текстов используются стандартные механизмы информационного поиска, при котором ключевые слова вопроса сравниваются со словами, найденными в корпусе текстов. В ВОС возвращаются не целые документы, а отдельные параграфы, которые затем ранжируются с использованием механизмов Обработки Естественного Языка (ОЕЯ). Пример схемы поиска ответа приведен в работе [37]: вопросу сопоставляется синтаксический, а затем семантический граф, который далее сопоставляется с сетью, строится граф ответа, на основе которого строится синтаксическая структура предложения ответа. В итоге ответ извлекается из наиболее информативного параграфа.

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

Значительный успех был достигнут вопросно-ответными системами для вопросов-фактов, таких как «Кто является основателем Санкт-Петербурга?». Точность ответов (доля правильных ответов) для таких вопросов составила 71% на испытании TREC-2005 [135]. Для остальных типов вопросов точность намного ниже. Для вопросов-списков («Какие страны входят в организацию ОПЕК?») максимальная точность уже 47%, а для вопросов-определений («Кем был Сергей Павлович Королев?») и остальных типов вопросов точность составила лишь 25%. Причем максимальную точность в каждом классе вопросов показали разные системы.

Вопросы-определения остаются наименее исследованной областью вопросно-ответных систем, такие вопросы составляют наибольшую сложность как для поиска ответа, так и для его последующей оценки [134, 88]. Данная ситуация связана с тем, что для корректной обработки вопросов-определений требуется применение всего инструментария ОЕЯ. Задача понимания естественного языка играет важную роль не только для вопросов-определений, но и для всех остальных типов вопросов [112].

Являясь одним из пионеров исследований в области компьютерной лингвистики и активным разработчиком современных систем понимания Естественно-Языковых (ЕЯ) текстов, А. С. Нариньяни критически оценивает состояние в области создания лингвистических моделей, подчеркивая смещение акцентов в сторону бесперспективного алгоритмического подхода, и утверждает [30], что «следующее поколение технологии автоматической обработки текста должно ориентироваться на принципы, в корне отличные от тех, на которых до последнего времени базировалось подавляющее большинство проектов в этой области». Оценивая результаты более трех десятилетий исследований и разработок в области автоматического понимания ЕЯ текста, Нариньяни в работе [30] отмечает, что «результатов до обидного мало, . в рамках общепринятой на сегодня методологии никакая прикладная задача, включающая понимание ЕЯ текста, не может быть решена по крайней мере в ближайшие десять (а, скорее всего, и тридцать) лет».

Нариньяни отмечает, что только семантически-ориентированный подход к обработке ЕЯ, основанный на моделях, а не на алгоритмах, может дать практические результаты [31]. Семантически-ориентированный подход к анализу ЕЯ текста определяется Нариньяни следующим образом: «пытайся восстановить смысл текста, используя всю доступную семантическую и прагматическую информацию; обращайся к синтаксическим компонентам только тогда, когда это необходимо для разрешения неоднозначности».

Эффективное использование знаний во время и после лингвистических этапов процесса анализа-понимания ЕЯ является основой семантически-ориентированного подхода. Использование различных лексических ресурсов является практически обязательной частью наиболее эффективных ВОС [73, 105, 67, 117] и позволяет приблизиться к решению следующих проблем вопросно-ответных систем:

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

2. Предварительное извлечение ответов для наиболее часто встречающихся вопросов. Часто вопросы задаются про функции человека в какой-то организации, например, «Кто является главой компании РОСНЕФТЬ?». Предварительные ответы извлекаются из корпуса текстов на основании синтаксических шаблонов. При этом необходимо исключать слова, которые не указывают на функции человека, но встречаются в шаблонах типа «Петр являлся моим коллегой в МТС», что невозможно сделать только с помощью синтаксиса.

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

4. Перефразирование вопроса и ответа. Для вопроса «Кто является автором «Илиады?» следующее предложение должно быть расценено системой как релевантное: «Гомер написал «Илиаду» и «Одиссею».

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

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

Разработка и пополнение лексических ресурсов связаны со следующими задачами ОЕЯ:

• кластеризация слов для выделения семантических классов;

• извлечение семантических отношений (гипонимия, меронимия, синонимия);

• снятие семантической омонимии.

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

Несмотря на впечатляющие достижения, которые были достигнуты в построении ручных тезаурусов типа WordNet, область покрытия тезаурусов, особенно для русского языка, все еще является ограничителем для развития вопросно-ответных систем. Теория Смысл-Текст (ТСТ) [27], являясь практически первой в СССР «кибернетической» теорией в области лингвистики, ставящей перед собой прикладные цели — создать двунаправленный лингвистический процессор, использовала Толково-Комбинаторный Словарь (ТКС) для задания морфологических, синтаксических, семантических характеристик и толкований заглавного слова. В [92] приведены данные о том, что первый вариант ТКС, включающий описание 750 лексем, объединенных в 250 вокабул, составлялся группой из 20 участников в течение 10 лет. Этот факт говорит о том, что средства, методика формирования базы лингвистических знаний и

11 формализация лексической информации являются важнейшими компонентами и задачами при построении систем ОЕЯ.

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

• методы, основанные на лексико-синтаксических шаблонах;

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

Оба подхода дополняют друг друга: методы, основанные на шаблонах, показывают хорошую производительность для извлечения гипонимии, а дистрибутивный подход обычно используется для извлечения синонимии и меронимии. Как показано в [111], подход, основанный на шаблонах, должен быть обязательно дополнен методами автоматического извлечения шаблонов из корпуса текстов.

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

Для кластеризации используются иерархические и неиерархические алгоритмы: снизу-вверх на основе дистрибутивной схожести [45], алгоритмы, допускающие вхождение в несколько классов и работающие с мерой принадлежности к классу (Clustering by Committee) [100], классификатор на основе графов и скрытой модели Маркова [51], метод к-средних [16], метод максимума правдоподобия (Expectation Maximization) [50]. Большинство иерархических алгоритмов имеют сложность 0(п2). Результатом кластеризации обычно является неименованная иерархия и далее, как правило, применяются алгоритмы для назначения имен кластеров [101, 137, 129]. При семантической классификации большое значение имеет выбор степени различия смысла слов, а кластеризация может помочь в нахождении и разделении различных смыслов слов [114].

В данной работе для задачи автоматического извлечения лексико-семантических знаний применяются методы Анализа Формальных Понятий (АФП) [61]. Знания — совокупность сведений о мире, включающих в себя информацию о свойствах объектов, закономерностях процессов и явлений, а также правилах использования этой информации для принятия решений. Лексико-семантические знания включают денотативный и смысловой компоненты связанной с лексемой информации. Практически все перечисленные выше методы в той или иной степени оперируют идеей концепта (понятия). Формализация понятий и их последующий анализ с помощью решетки позволяют оперировать данными на семантическом уровне без потери или недопустимого упрощения объектов и их признаков, в отличие от представления атрибутов с помощью векторов и их статистической обработки. Классификация объектов и результаты анализа данных с помощью АФП могут быть интерпретированы исследователем для предметной области.

Анализ формальных понятий — это метод анализа данных, основанный на математической теории решеток. Основой АФП является доказанная Г. Биркгофом теорема [7] о том, что для любого бинарного отношения можно построить полную решетку. Исследуемая область описывается в терминах набора объектов и атрибутов, вводится описание формального контекста, формальных понятий и решетки, отображаемой с помощью линейных диаграмм.

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

107] обосновывается возможность использования АФП в компьютерной лингвистике для анализа семантических отношений в словарях типа Wordnet

108] и лексических функций [53], создания тезаурусов [124, 99], разрешения многозначности глаголов [42], пополнения онтологии [48]. В работе [123] описывается формальный язык концептуальных графов для представления знаний, а в работе [95] описывается сопоставление концептуальных графов с АФП.

Основой данной работы является установление соответствия между Генитивными Конструкциями (ГК) русского языка и анализом формальных понятий, которое базируется на семантических отношениях между опорным словом и генитивной именной группой [125]. Выбор семантического отношения, как правило, определяется опорным существительным, даже когда оно не является реляционным, что дает возможность применить методы теории решеток к формализации данного отношения. Правильность ГК (рост Пети, но высота столба) определяется в терминах сортов [9], также сорта позволяют составить формулы для записи семантики ГК на языке категориальной грамматики.

Сорта — элементы «наивной картины мира» [8], классы, к которым язык относит более конкретные реалии, сущности, вещи. Сорта можно рассматривать как онтологическую классификацию. Классификация лексики по сортам обсуждалась у Джекендофа, Пустейовского, Фомичева [75, 110, 38]. В работе будет использоваться теория сортов (постулаты значения) для классификации и извлечения семантических отношений из неструктурированного текста.

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

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

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

2. Построение модели лексикона и модели семантических отношений в лексиконе для ВОС;

3. Разработка алгоритма сегментации лексикона и формирования классов схожих лексем;

4. Разработка методов классификации вопросов, снятия семантической многозначности для ВОС;

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

Диссертационная работа состоит из введения, пяти глав, заключения и библиографического списка.

5.5 Выводы по главе 5

В пятой главе выполняется экспериментальная проверка описанной в предыдущих главах модели извлечения знаний на основе решетки формальных понятий. Формулируются требования по полноте и репрезентативности, предъявляемые к корпусу текстов, используемому для построения на его основе KOJI. Показано, что распределение частоты встречаемости ГК соответствует закону Ципфа для больших текстов русского языка. Согласно закону Ципфа объем корпуса текстов для построения на его основе КОЛ должен быть не менее 50 млн. слов.

Показано, что с увеличением объема используемого корпуса текстов снижение репрезентативности этого корпуса не происходит, при этом покрытие слов, используемых для построения КОЛ, примерно соответствует всему лексикону русского языка.

Описывается процесс обработки корпуса для извлечения знаний. Формулируются требования к исходным данным в виде корпуса текстов и предлагаемому способу извлечения ГК из текста для получения КОЛ, предлагаются методы оптимизации методов извлечения исходной информации.

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

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

ЗАКЛЮЧЕНИЕ

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

Основные научные результаты состоят в следующем:

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

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

• Разработана модель автоматического извлечения знаний, представленных формальными понятиями в концептно-ориентированном лексиконе, из неструктурированного текста на русском языке. Концептно-ориентированный лексикон генерируется на основе формального контекста, состоящего из элементов генитивных конструкций и глаголов, в модели управления которых генитивная конструкция занимает место одного из актантов. Формальный контекст автоматически формируется из неструктурированного текста на русском языке.

• Предложен критерий полезности решетки концептно-ориентированного лексикона для извлечения лексического значения, а также разработан метод максимизации этого критерия.

• Получены модели семантических отношений порядка и меронимии для слов на основе решетки формальных понятий.

Основные практические результаты состоят в следующем: Предложена количественная оценка меры схожести между формальными понятиями решетки.

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

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

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

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

Предложена методика оценки концептно-ориентированного лексикона относительно эталонного лексического ресурса, получена экспериментальная оценка.

По теме диссертации опубликовано 8 печатных работ [126, 15, 55, 56, 54, 35, 125, 53]. Основные результаты апробировались на международных конференциях и опубликованы в сборниках докладов и журналах: IX-й международной конференции «Cognitive Modeling in Linguistics» (София, Болгария, 2007), 7-й международной конференции «Pattern Recognition and Image Analysis: New Information Technologies» (С.-Петербург, 2004), 6-ой международной научно-технической конференции «Interactive Systems And Technologies: The Problems of Human-Computer Interaction» (Ульяновск, 2005), 2-й международной конференции IASTED «Automation, Control, and Information Technologies» (Новосибирск, 2005), VI-м международном конгрессе по математическому моделированию (Нижний Новгород, 2004), 13-й всероссийской конференции «Математические методы распознавания образов» (г. Зеленогорск, 2007), 7-ой международной научно-технической конференции «Interactive Systems And Technologies: The Problems of Human-Computer Interaction» (Ульяновск, 2007) и в публикации в журнале «Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications» (Vol. 17, No. 2, 2007).

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

Дальнейшие исследования по тематике диссертационной работы целесообразно провести в направлении:

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

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

1. Абрамов Н. Словарь русских синонимов и сходных по смыслу выражений: Около 5 ООО синонимических рядов. Более 20 ООО синонимов // 7-е изд., изд.: Русские словари, Москва, 1999.

2. Азарова И.В., Митрофанова О.А., Синопальникова А.А. Компьютерный тезаурус русского языка типа WORDNET // Труды международной конференции Диалог'2003, Протвино.

3. Азарова И.В., Секликов Ю.В., Иванов В.Л. Интерпретация текстовых документов с использованием формальной грамматики AGFL и компьютерного тезауруса RussNet // сборник: Доклады международной конференции Диалог2004.

4. Апресян Ю.Д. Избранные труды, том I. Лексическая семантика // 2-е изд., испр. и доп., Издательская фирма «Восточная литература» РАН, Москва, 1995.-с. 472.

5. Апресян Ю.Д. О регулярной многозначности // Известия АН СССР, Отделение литературы и языка, Вып. 6, Москва, 1971. — С. 509-523.

6. Биркгоф Г. Теория решеток // изд.: Наука, Москва, 1984. с. 568.

7. Борщев В.Б. Естественный язык наивная математика для описания наивной картины мира // Московский лингвистический альманах, вып. 1, 1996.-С. 203-225.

8. Борщев В.Б., Кнорина Л.В. Типы реалий и их языковое восприятие // Всб. "Вопросы кибернетики. Язык логики и логика языка" Под ред. Иванова В.В., Москва. С. 106-134.

9. Борщев В.Б., Партии Б.Х. Семантика генитивной конструкции: разные подходы к формализации // В сб. Типология и теория языка: от описания к объяснению. К 60-летию А.Е. Кибрика, Под ред. Е.В. Рахилиной и Я.Г. Тестельца, Москва, 1999. С. 159-172.

10. Герасимова И.А. Формальная грамматика и интенсиональная логика // РАН, Институт философии, Москва, 2000. с. 156.

11. Готтлоб Ф. Логика и логическая семантика: Сборник трудов // Пер. с нем. Б.В. Бирюкова под ред. З.А. Кузичевой, Учебное пособие для студентов вузов, изд: Аспект Пресс, Москва, 2000. С. 213-284.

12. Гретцер Г. Общая теория решеток // изд: Мир, Москва, 1982. с. 452.

13. Евтушенко С. А. Система анализа данных "Concept Explorer". // Труды. седьмой Международной научно-технической конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы", Кацивели, Крым, Украина, 2006. С. 127-134.

14. Загоруйко Н.Г. Прикладные методы анализа данных и знаний // Издательство Ин-та математики, Новосибирск, 1999. — с. 270.

15. Карнап Р. Постулаты значения // Москва, 1959. С. 321-331.

16. Кибрик А. Е., Брыкина М.М., Хитров А.Н. Опыт фронтального корпусного исследования конструкций с внутренним и внешним посессором // В сб: Доклады международной конференции Диалог2004. С. 265-275.

17. Кобозева И.М. Лингвистическая семантика: Учебник // Изд. 2-е, изд: Едиториал УРСС, Москва, 2004.

18. Кобрицов Б.П., Ляшевская О.Н., Шеманаева О.Ю. Снятие лексико-семантической омонимии в новостных и газетно-журнальных текстах: поверхностные фильтры и статистическая оценка // Сборник работ стипендиатов Yandex 2005.

19. Кузнецов С.О. Теория машинного обучения в решетках формальных понятий // Всероссийский Институт Научной и Технической Информации, РАН, Москва, 2002. с. 147.

20. Лайонз Дж. Лингвистическая семантика: Введение // Пер. с англ. В.В. Морозова и И.Б. Шатуновского, под общ. ред. И.Б. Шатуновского, изд: Языки славянской культуры, Москва, 2003.

21. Леонтьева Н.Н. Русский общесемантический словарь (РОСС): структура, наполнение // Науч.-техн. информ., сер. 2, вып. 12, 1997. С. 5-20.

22. Мандельброт Б. Фракталы, случай и финансы // Пер. с англ., НИЦ «Регулярная и хаотическая динамика», Москва-Ижевск, 2003. с. 255.

23. Мельчук И. А. Опыт теории лингвистических моделей «Смысл Текст» // Наука, Москва, 1974.

24. Мозговой М. Простая вопросно-ответная система на основе семантического анализатора русского языка // Вестник Санкт-Петербургского университета, сер. 10, вып. 1, 2006. С. 116-122.

25. Нариньяни А.С. Кентавр по имени ТЕОН: Тезаурус + Онтология // Труды международного семинара Диалог'2001 по компьютерной лингвистике и ее приложениям, Т.1, Аксаково, 2001. С. 184-188.

26. Нариньяни А.С. Модель или алгоритм: новая парадигма информационной технологии // Информационные Технологии, 1997. — С. 11-16

27. Постмодернизм: Энциклопедия // изд.: Интерпрессервис, Книжный Дом, Москва, 2001. с. 1040.

28. Сокирко А.В., Толдова С.Ю. Сравнение эффективности двух методик снятия лексической и морфологической неоднозначности для русского языка (скрытая модель Маркова и синтаксический анализатор именных групп) // Сборник работ стипендиатов Yandex 2005.

29. Соснин П.И. Человеко-компьютерная диалогика // Ульяновский государственный технический университет, Ульяновск, 2001. — с. 285.

30. Падучева Е.В. Коммуникативное выделение на уровне синтаксиса и семантики // Сборник "Семиотика и информатика", вып. 36, 1998.

31. Попов Э.В. Общение с ЭВМ на естественном языке // Проблемы искусственного интеллекта, изд: Наука, Москва, 1982 г. с. 360.

32. Фомичев В.А. Формализация структуры основных словарейлингвистической базы данных // Качество и ИПИ (САЬЗ)-технологии, #3,2005.-С. 30-38.

33. Языкознание: Большой энциклопедический словарь // В.Н. Ярцева (гл. ред.), изд.: Русский язык, Москва, 1998.

34. Alpha S., Dixon P., Liao С., Yang С. Oracle at TREC 10: Filtering and Question-Answering // In Proceedings of the Tenth Text REtrieval Conference (TREC 2001), Gaithersburg, Maryland, 2001. p. 423.

35. Anquetil N., Vaucher J. Extracting Hierarchical graphs of concepts from an object set: Comparison of two methods // In Knowledge Acquisition Workshop, ICCS'94, 1994.

36. Bertagna F., Chiran L., Simi M. QA at ILC-UniPI: Description of the Prototype // In Working Notes of the CLEF 2004 Workshop, Bath, Uk, 2004. -pp. 435-444.

37. Bordat J.P. Calcul pratique du treillis de Galois d'une correspondance // Math. Sci. Hum., no. 96, 1986. pp. 31-47.

38. Brown P.F., Delia Pietra V.L., deSouza P.V., Lai J.C., Mercer R. Class-based n-gram models of natural language // Computational Linguistics 18(4), 1992. -pp. 467-479.

39. Budanitsky A., Hirst G. Evaluating WordNet-based measures of semantic distance // Computational Linguistics, 32(1), 2006.

40. Chang Y., Xu H., Bai S. Question Answering Track at CAS-ICT // In NIST Special Publication : SP 500-255, The Twelfth Text Retrieval Conference (TREC 2003), 2003. p. 147.

41. Cimiano P., Hotho A., Staab S. Learning Concept Hierarchies from Text Corpora using Formal Concept Anaylsis // Journal of Artificial Intelligence146

42. Research, Volume 24, 2005. pp. 305-339.

43. Dahlberg I. Conceptual Structures and Systematization // In Negrini G. edition, Categorie, Ogetti e Strutture della Conoscenza, Roma, 1994.

44. Dempster A., Laird N., Rubin D. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society, Series B, 39(1), 1977.-pp. 1-38.

45. Dorow В., Widdows D. Discovering corpus-specific word-senses // Proceedings of the 10th Conference of the European Chapter of the Association for Computational Linguistics, Budapest, Hungary, 2003. pp. 79-82.

46. Edmundson H. P. Computational Linguistics, axiomatic characterization of synonymy and antonymy // Proceedings of the 1967 conference on Computational linguistics, Morristown, USA, 1967. pp. 1-11.

47. Emelyanov G.M., Stepanova N.A. Model of types in intensional logic // Interactive Systems And Technologies: The Problems of Human-Computer Interaction, Collection of scientific papers, Ulyanovsk: U1STU, 2005. pp. 66-71.

48. Evens M. W. Relational Models of the Lexicon // Cambridge University Press, 1988.

49. Fellbaum C. WordNet: An Electronic Lexical Database // Cambridge, 1998.

50. Ferre S. The Use of Associative Concepts for Fast Incremental Concept Formation in Sparse Contexts // In B. Ganter and A. de Moor editors, Using Conceptual Structures, Contributions to ICCS 2003, 2003.

51. Fisher D., Langley P. Approaches to Conceptual Clustering // In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85, volume 1, 1985. pp. 691-697.

52. Ganter В., Wille R. Formal Concept Analysis Mathematical Foundations // Berlin: Springer-Yerlag, 1999.

53. Gideon S.M. Fine-Grained Proper Noun Ontologies for Question Answering // SemaNet'02: Building and Using Semantic Networks, 2002

54. Glickman O., Dagan I. Identifying lexical paraphrases from a single corpus: A case study for verbs // In Proceedings of Recent Advantages in Natural Language Processing, 2003.

55. Godin R., Missaoui R., Alaoui H. Incremental Concept Formation Algorithms Based on Galois Lattices // Computation Intelligence, 1995.

56. Harris Z. Distributional structure // The Philosophy of Linguistics, in J.J. Katz editor, New York: Oxford University Press, USA, 1985. pp. 26-47.

57. Hearst M. Automatic acquisition of hyponyms from large text corpora // In Proceedings of the 14th International Conference on Computational Linguistics (COLING), 2002. pp. 539-545.

58. Heit E., Rubinstein J. Similarity and property effects in inductive reasoning // Journal of Experimental Psychology: Learning, Memory, and Cognition, 20, 1994.-pp. 411-422.

59. Hirst G., Budanitsky A. Correcting real-word spelling errors by restoring lexical cohesion // In Natural Language Engineering, 11(1), 2005. pp. 87111.

60. Hirst G., St-Onge D. Lexical chains as representations of context for the detection and correction of malapropisms // In C. Fellbaum editor, WordNet: An Electronic Lexical Database, the MIT Press, Cambridge, Massachusetts, 1998.-pp. 305-332.

61. Hovy E., Hermjakob U. The Use of External Knowledge of Factoid QA // In Proceedings of the Tenth Text Retrieval Conference (TREC-10), Gaithersburg, Maryland, USA, 2001. pp. 644-652.

62. Iris M., Litowitz В., Evens M. Problems of Part-Whole Relations // In Evens M. edition, Relational Models of the Lexicon, Cambridge University Press, 1988.-pp. 261-288.

63. Jackendoff R. The Architecture of the Language Faculty // Cambridge, Mass.: MIT Press, 1997.

64. James R. Curran and Marc Moens. Improvements in automatic thesaurus extraction // In Proceedings of the Workshop of the ACL Special Interest Group on the Lexicon (SIGLEX), Philadelphia, USA, 2002. pp. 59-66.

65. Jiang J.J., Conrath D.W. Semantic similarity based on corpus statistics and lexical taxonomy // In Proceedings of the International

66. Conference on Research in Computational Linguistics, Taiwan, 1997. — pp. 19-33.

67. Kilgarriff A. I Don't Believe in Word Senses // Computers and the Humanities, Volume 31, Number 2, 1997. -pp. 91-113.

68. Kilgarriff A., Yallop C. What's in a thesaurus? // In Proceedings of the Second Conference on Language Resource an Evaluation, 2000. pp. 13711379.

69. Kolliakou D. De-Phrase extractability and Individual/Property denotation // Natural Language and Linguistic Theory 17, 1999. pp. 713-781.

70. Kuznetsov S.O. A fast algorithm for computing all intersections of objects in a finite semilattice // Automatic Documentation and Mathematical Linguistics, 27 (5), 1993. pp. 11 -21.

71. Kuznetsov S.O., Obiedkov S.A. Comparing performance of algorithms for generating concept lattices // Journal of Experimental & Theoretical Artificial Intelligence, Volume 14, Issue 2 & 3, 2002. pp. 189-216.

72. Leacock C., Chodorow M. Combining local context and WordNet similarity for word sense identification // In Christiane Fellbaum editor, WordNet: An Electronic Lexical Database, The MIT Press, Cambridge, Massachusetts, 1998.-pp. 265-283.

73. Lin D. An information-theoretic definition of similarity // In Proceedings of the International Conference on Machine Learning, Madison, Wisconsin, 1998.-pp. 296-304.

74. Lin D. Automatic retrieval and clustering of similar words // In COLING-ACL, 1998.-pp. 768-774.

75. Lin D. Extracting Collocations from Text Corpora // Proceedings of the Workshop on Computational Terminology, Montreal, Canada, 1998. pp. 57-63.

76. Lin D., Pantel P. Discovery of inference rules for question answering // Natural Language Engineering 7(4):343-360, 2001.

77. Lin J., Demner-Fushman D. Automatically Evaluating Answers to Definition150

78. Questions // Technical Report: LAMP-TR-119/CS-TR-4695/UMIACS-TR-2005-04, University of Maryland, College Park, USA, 2005.

79. Luce R.D. Semiorders and a theory of utility discrimination // Econometrica, 1956.-pp. 178-191.

80. Masterman M. Semantic message detection for machine translation, using an interlingua //1961 International Conference on Machine Translation of Languages and Applied Language Analysis, London, UK, 1962. pp. 437475.

81. Matsuo Y., Sakaki Т., Uchiyama K., Ishizuka M. Graph-based Word Clustering using Web Search Engine // in processing 2006 conference on Empirical Methods in Natural Language Processing (EMNLP 2006), Sydney, Australia. pp. 542-550.

82. Melchuk LA. The Russian Language in the Meaning Text Perspective // Wiener Slawistischer Almanach, Moskau-Wien, 1995. - p. 39.

83. Miller G.A., Charles W.G. Contextual correlates of semantic similarity // Language and Cognitive Processes, no.6(1), 1991.-pp. 1-28.

84. Miller G.A. Nouns in WordNet: a lexical inheritance system // International Journal of Lexicography, volume 3. pp. 245-264.

85. Mohammad S., Hirst G. Distributional measures as proxies for semantic relatedness. Электронный ресурс. Режим доступа: http://www.cs.toronto.edu/pub/gh/Mohammad+Hirst-2005.pdf. - Загл. с экрана.

86. Nieminen J. Rough tolerance equality // Fundamenta Informaticae, 1988. -pp. 289-296.

87. Norris E. M., An algorithm for computing the maximal rectangles in a binaryrelation // Revue Roumaine de Mathermatiques Pures et Appliqueres, 23 (2), 1978.-pp. 243-250.

88. Osswald R., Petersen W. Induction of Classifications from Linguistic Data // In proceedings of the ECAI-Workshop on Advances in Formal Concept Analysis for Knowledge Discovery in Databases, 2002.

89. Pantel P., Lin D. Discovering word senses from text // In Proceedings of ACM Conference on Knowledge Discoveiy and Data Mining (KDD-02), 2002.-pp. 613-619.

90. Pantel P., Ravichandran D. Automatically labeling semantic classes // HLTNAACL 2004: Main Proceedings, in Marcu D., Dumais S., Roukos S. editors, Boston, Massachusetts, USA, 2004. pp. 321-328.

91. Partee B.H. Formal Semantics, Lectures // RGGU, 2003.

92. Polkowski L., Skowron A., Zytkow J. Tolerance based rough sets // In Soft Computing: Rough Sets, Fuzzy Logic, Neural Networks, Uncertainty Management, edited by T. Lin and A. Wildberger. pp. 55-58.

93. Prager J., Chu-Carroll J., Czuba K. Use of WordNet Hypernyms for Answering What-Is Questions // In Proceedings of the TREC 2002.

94. Prager J., Radev D., Brown E., Coden A., Samn V. The use of predictive annotation for question answering in TREC8 // Proceedings of TREC8, Gaithersburg, 2000.

95. Priss U. Linguistic Applications of Formal Concept Analysis // In Ganter; Stumme; Wille editions, Springer-Verlag, LNAI 3626, 2005. pp. 149-160.

96. Priss U. Relational Concept Analysis: Semantic Structures in Dictionaries and Lexical Databases //Verlag Shaker, 1998. pp. 67-86.

97. Priss U. The Formalization of WordNet by Methods of Relational Concept152

98. Analysis // In Fellbaum C. edition, WordNet: An Electronic Lexical Database and Some of its Applications, MIT press, 1998. pp. 179-196.

99. Pustejovsky J. The Generative Lexicon // The MIT Press.

100. Ravichandran D., Hovy E. Learning Surface Text Patterns for a Question Answering System // ACL '02: Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, Philadelphia, Pennsylvania, USA, 2001.-pp.41-47.

101. Renxu Sun, Jing Jiang, Yee Fan Tan, Hang Cui, Tat-Seng Chua, Kan M.Y. Using Syntactic and Semantic Relation Analysis in Question Answering // Proceedings of the 14th Text Retrieval Conference (TREC 2005).

102. Schiitt D. Abschatzungen fur die Anzahl der Begriffe von Kontexten // Diplomarbeit TH Darmstadt, Darmstadt, 1988.

103. Seco N. Computational models of similarity in lexical ontologies // Master's thesis, University College, Dublin, Ireland, 2005.

104. Seung-Hoon Na In-Suang, Sang-Yool Lee, Jong-Hyeok Lee Question Answering Approach Using a WordNet-based Answer Type Taxonomy // In Proceedings of the TREC 2002, 2002. p. 512.

105. Sharoff S. Meaning as use: exploitation of aligned corpora for the contrastive study of lexical semantics // in proccessing of Language Resources and Evaluation Conference (LREC02), Las Palmas, Spain, 2002.

106. Smeaton A.F., van Rijsbergen C.J. The retrieval effects of query expansion on a feedback document retrieval system // The Computer Journal, 26(3), 1983.-pp. 239-46.

107. Slator B.M., Wilks Y.A. Towards semantic structures forom dictionary entries // Proceedings of the 2nd Annual Rocky Mountain Conference on

108. Artificial Intelligence, Boulder, Colorado, 1987. pp. 85-96.

109. Slowinski R., Vanderpooten D. Similarity relations as a basis for rough approximations // ICS Research Report 53/95, Warsaw University of Technology, 1995. ftp://ftp.ii.pw.edu.pl/pub/Rough.

110. Sowa J. F. Knowledge-Based Systems // Special Issue on Conceptual Graphs, vol.5, no.3, 1992.

111. Sporleder C., Lattice G. Approach to Lexical Inheritance Learning // ECAI 2002 Workshop on Machine Learning and Natural Language Processing for Ontology Engineering (OLT2002), Lyon, France, 2002.

112. Stepanova N.A., Emelyanov G.M. Concept-oriented lexicon application for Question Answering systems // Interactive Systems And Technologies: The Problems of Human-Computer Interaction, Collection of scientific papers, Ulyanovsk: U1STU, 2007. pp. 31-40.

113. Stumme G., Maedche A.: FCA-Merge: A Bottom-Up Approach for Merging Ontologies // In International Joint Conference on Artificial Intelligence, Washington, USA, 2001. pp. 225-234.

114. Sussna M. Word sense disambiguation for free-text indexing using a massive semantic network // In Proceedings of the Second International Conference on Information and Knowledge Management, Washington, 1993. pp. 6774.

115. Treeratpituk P., Callan J. Automatically labeling hierarchical clusters // Proceedings of the 2006 international conference on Digital government research, ACM Press, San Diego, California, USA, 2006. pp. 167-176.

116. Tversky, A. Features of similarity // Psychological Review, 84, 1977. pp. 327-352.

117. Van der Plas L., Bouma G., Mur J. Automatic Acquisition of lexico-semantic knowledge for QA // Ontologies and Lexical Resources for Natural Language Processing, in C.-R. Huang edition, Cambridge University Press, University of Sinica, Cambridge, UK.

118. Van Dongen S. A cluster algorithm for graphs // Technical Report INS-R0010, National Research Institute for Mathematics and Computer Science, Amsterdam, The Netherlands.

119. Vikner C., Jensen P. A. Semantic analysis of the English genitive // Interaction of lexical and formal semantics, volume 56. — pp. 191-226.

120. Voorhees Ellen M. Evaluating answers to definition questions // In Proceedings of the TREC 2003.

121. Voorhees Ellen M. Overview of the TREC 2003 question answering track // In Proceedings of the Twelfth Text REtrieval Conference, 2004. pp. 54-68.

122. Vossen P. Euro WordNet: A Multilingual Database with Lexical Semantic Networks//Dodrecht, 1998.

123. Widdows D., Dorow B. A-graph model for unsupervised lexical acquisition // In Proceedings of the 19th International Conference on Computaional Linguistics (Coling), 2002. pp. 1093-1099.

124. Wille R. Concept Lattices and Conceptual Knowledge Systems in Semantic Networks in Artificial Intelligence // F. Lehmann editor, Pergamon Press, 1992.-pp. 493-516.

125. Winston M. E., Chan R., Herrmann D. A Taxonomy of Part-Whole Relations // Cogn. Science, vol. 11, 1987. pp. 417-444.

126. Worboys M.F. Nearness Relations in Environmental Space // International Journal of Geographical Information Science, 15 (7), 2002. pp. 633-652.155

127. Yang D., Powers D.M.W. Measuring semantic similarity in the taxonomy of WordNet I I In V. Estivill-Castro editor, Proceedings of the 28th Australasian Computer Science Conference, Newcastle, Australia, 2005. pp. 315-322.

128. Yarowsky D. One sense per collocation // In the Proceedings of ARPA Human Language Technology Workshop, Morristown, NJ, USA, 1993. pp. 266-271.

129. Yarowsky D. Unsupervised word sense disambiguation rivaling supervised methods // Proceedings of the 33rd annual meeting on Association for Computational Linguistics, Morristown, NJ, USA 1995. pp. 189-196.

130. Zipf G. K. Human Behaviour and the Principle of Least-Effort // Cambridge MA: Addison-Wesley, 1949.У156