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



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

ИЛЬВОВСКИИ Дмитрий Алексеевич

МОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНЫЕ КОМПЛЕКСЫ ОБРАБОТКИ ТЕКСТОВЫХ ДАННЫХ НА ОСНОВЕ РЕШЕТОК ЗАМКНУТЫХ ОПИСАНИЙ

Специальность 05.13.18

Математическое моделирование, численные методы и комплексы программ

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

13 КОЯ 2014

Москва, 2014

005554819

005554819

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

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

Кузнецов Сергей Олегович, доктор физико-математических наук, заведующий кафедрой анализа данных и искусственного интеллекта Национального исследовательского университета «Высшая школа экономики»

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

Аншаков Олег Михайлович, доктор физико-математических наук, доцент кафедры математики, логики и интеллектуальных систем в гуманитарной сфере Российского государственного гуманитарного университета

Лукашевич Наталья Валентиновна, кандидат физико-математических наук, ведущий научный сотрудник Научно-исследовательского

вычислительного центра Московского государственного университета им. М.В. Ломоносова

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

Институт системного анализа РАН

Защита состоится «16» февраля 2015 г. в 11:00 на заседании диссертационного совета Д 212.048.09 Национального исследовательского университета «Высшая школа экономики», по адресу: 105187, г. Москва, ул. Кирпичная, д.ЗЗ, ауд. 503.

С диссертацией можно ознакомиться в библиотеке НИУ «Высшая школа экономики» по адресу: 101990, г. Москва, ул. Мясницкая, д. 20, и на сайте ШуМчтч/.hse.ru/sci/diss/.

Автореферат разослан <5,3 октября 2014 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

Назаров Станислав Викторович

Общая характеристика работы

Актуальность работы. Моделирование языковых процессов порождает значительное количество открытых проблем, связанных с развитием соответствующего математического аппарата, созданием и реализацией эффективных алгоритмов и комплексов программ. К настоящему моменту разработано значительное количество хорошо развитых моделей текста, позволяющих (помимо представления текста) вычислять сходство между текстами: «мешок слов», п-граммы, синтаксические деревья разбора и т.д. Среди исследователей, внесших значительный вклад в разработку и применение этих моделей в прикладных задачах (для английского языка), можно отметить СМашшщ, Н-всЫ^е, Б^г^ку, вЛЬпеу, М.СоИшэ, А.МоэсЫШ и многих других. Подавляющее большинство реализованных на практике моделей не полностью учитывает структурные особенности текста, ограничиваясь либо частотными характеристиками слов и п-грамм, либо синтаксическими связями внутри отдельных предложений. Эти модели не позволяют работать с текстом на уровне фрагментов, состоящих из нескольких связанных предложений - абзацев. К другому классу моделей относятся многочисленные лингвистические теории, в той или иной степени учитывающих семантические связи между предложениями. Здесь можно отметить работы таких исследователей как АУ.Мапп, Б-Магси, 1.8еаг1е, 1.Ме1'сик, Н.Катр, МАесаезепя, БЛигаГвку и многих других. Однако эти модели обладают уже другим недостатком: они носят по большей части теоретический характер, не имеют полного математического или алгоритмического описания и не могут напрямую быть использованы для решения прикладных задач. В то же время учет семантических связей внутри абзаца является критическим фактором в таких важных задачах, как поиск по сложным и редким запросам, кластеризация поисковой выдачи по сложным запросам, классификация текстовых описаний. Всё это делает применение

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

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

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

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

К задачам исследования относятся:

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

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

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

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

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

• Реализация разработанных моделей, методов и алгоритмов в виде программного комплекса.

К методам, использовавшимся в Исследовании, относятся:

• Методы построения и анализа решёток замкнутых описаний;

• Методы фильтрации решеток понятий на основе индексов качества моделей;

• Методы построения проекций моделей на узорных структурах;

• Методы построения структурных моделей для текстовых данных;

• Методы построения синтаксических и семантических моделей текста;

• Методы порождения моделей, основанных на графовом представлении.

Научная новизна. В диссертации получен ряд новых научных

результатов, которые выносятся на защиту:

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

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

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

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

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

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

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

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

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

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

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

1. 9-й международной конференции «Интеллектуализация обработки информации» (ИОИ-2012), Будва, Черногория.

2. Семинаре по анализу формальных понятий и информационному поиску (FCAIR-2013) в рамках 35-й европейской конференции по информационному поиску (ECIR-2013), Москва, Россия.

3. 11-й международной конференции по анализу формальных понятий (ICFCA-2013), Дрезден, Германия.

4. 8-й международной конференции по компьютерной лингвистике ДИАЛОГ-2013, Москва, Россия.

5. 3-м семинаре по представлению знаний в виде графов (GKR-2013) в рамках 23-й объединенной международной конференции по искусственному интеллекту (IJCAI-2013), Пекин, Китай.

6. 7-й международной конференции по компьютерной лингвистике RANLP-2013, Хисаря, Болгария.

7. Ежегодном весеннем симпозиуме ассоциации искусственного интеллекта (2014 AAAI Spring Simposium).

8. 14-й международной конференции по интеллектуальной обработке текста и компьютерной лингвистике С1СЬП<Ю-2014, Катманду, Непал.

9. 52-й международной конференции Ассоциации компьютерной лингвистики АСЬ-2014, Балтимор, США.

Публикация результатов. Основные результаты работы изложены в 12 научных статьях. 9 статей опубликованы в рецензируемых трудах международных конференций, 3 статьи опубликованы в журналах из списка ВАК.

Структура диссертации. Диссертация изложена на 160 страницах и включает в себя введение, 5 глав, заключение и список литературы, состоящий из 110 пунктов.

Содержание работы

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

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

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

существуют инфимум и супремум. Решетки замкнутых описаний, называемые также узорными структурами (pattern structures) предназначены для работы со сложными данными. Узорная структура - это тройка (G,(D,n),<y), где G -

множество объектов, (ДП) - полная полурешетка всевозможных описаний, а

ô:G—>D - функция, которая сопоставляет каждому объекту из множества G его описание из D. Операция П позволяет вычислить сходство между двумя описаниями. Проекция узорной структуры - это функция у/ : D —> D, которая является монотонной х<у=>у/{х)<у/(у), сжимающей <//(х)<х и идемпотентной y/{y/(xf} — ^(*)• Для получения проекции узорной структуры

мы должны спроецировать функцию — описание объектов, а также полурешетку описаний:

Dv = y,{D) = [d 6 D13d' s D : y/(d') = d] и Vx, y e D, хп^ y = ц/(хПy).

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

Модель «мешка слов» («bag-of-words») дает упрощенное представление текста, применяемое, в частности, в задаче информационного поиска. В этой модели текст представляется как неупорядоченный набор слов (или словосочетаний) без учета грамматики и порядка слов.

Дерево синтаксического разбора (syntactic parse tree) - это упорядоченное дерево, которое отражает синтаксическую структуру предложения или строки согласно некоторой формальной грамматике. Выделяют два основных класса: деревья составляющих (constituency tree) и деревья зависимостей (dependency

tree). Деревья синтаксического разбора используются и для компьютерных языков, и для обработки текстов на естественных языках.

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

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

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

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

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

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

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

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

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

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

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

• Синтаксические или регулярные группы;

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

• Риторические группы (ИЯТ). Две группы (каждая из них может быть и чащевой, и синтаксической), соединенные риторическим отношением.

• Коммуникативные группы (СА). Здесь возможны два случая:

' Синтаксическая или обычная группа с выделенным в ней коммуникативным действием.

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

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

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

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

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

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

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

2. Найти семантические связи внутри абзаца.

3. Используя семантические связи, построить на основе синтаксических групп расширенные группы.

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

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

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

• Применение ключевых слов: базовый подход, в котором тексты представляются в виде «мешка слов», а затем вычисляется набор общих ключевых слов / N-грамм и их частот.

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

Таблица 2.1. Оценка релевантности поиска

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

Поиск рекомендаций по товарам 1 составное предложение 62.3 69.1 72.4 72.9 73.3

2 предложения 61.5 70.5 71.9 72.8 71.6

3 предложения 59.9 66.2 72.0 73.4 71.4

4 предложения 60.4 66 68.5 692 66.7

Поиск рекомендаций по путешествиям 1 составное предложение 64.8 6S 72.6 74.7 74.2

2 предложения 60.6 65.8 73.1 76.9 73.5

3 предложения 62.3 66.1 70.9 70.8 72.9

4 предложения 58.7 65.9 72.5 73.9 71.7

Поиск рекомендаций контента на РасеЬоок 1 составное предложение 54.5 63.2 65.3 68.1 67.2

2 предложения 52.3 60.9 62.1 63.7 63.9

3 предложения 49.7 57 61.7 63.0 61.9

4 предложения 50.9 58.3 62.0 64.6 62.7

Средние показатели 58.15 64.75 68.75 7033 69.25

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

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

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

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

1. Взять множество текстов (поисковую выдачу) Т.

2. Для каждого результата еТ построить чащу разбора деР.

3. Используя операцию обобщения чащ разбора в качестве решеточной операции пересечения П, построить узорную решетку (7\(Р,П),<?) для всех

текстов с помощью любого стандартного алгоритма (например, АдсШ^еп! или Замыкай-По-Одному).

4. Получить иерархические кластеры - узорные понятия решетки.

При использовании приближенного представления последовательность действий немного модифицируется:

1. Взять множество текстов (поисковую выдачу) Т.

2. Для каждого результата еТ * построить проекцию чащи разбора

3. Используя операцию обобщения проекций в качестве решеточной операции пересечения, построить проекцию узорной решетки [т,(Ру,,Гу),V «

4. Для всех текстов с помощью любого стандартного алгоритма (например, АсЗсПг^еШ или Замыкай-По-Одному).

5. Получить иерархические кластеры - проекции узорных понятий решетки.

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

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

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

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

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

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

Задача обучения представляет собой классификацию множества поисковых результатов по двум классам: релевантные и нерелевантные. Соответствующая обучающая выборка формируется как множество ответов с высоким рейтингом (положительные примеры) и множество ответов с низким рейтингом (отрицательные примеры). Тестовая выборка формируется из оставшегося множества путем случайного выбора. Для каждого результата используется его «сниппет» (выдаваемый поисковой системой фрагмент), а также соответствующий ему фрагмент текста, извлеченный со страницы (два независимых эксперимента). Этот эксперимент базируется на предположении, что верхние (нижние) результаты, выдаваемые Bing, так или иначе релевантны (нерелевантны) исходному запросу, несмотря на то что они могут быть неверно упорядочены.

Таблица 3.1. Результаты для запросов, связанных с мнением о продуктах. Обучение

на текстах со ст раниц

Продукты Исходный метод Модифицированный метод

Точность 0,5679 0,5868

Полнота 0,7516 0,8458

F-мера 0,6485 0,6752

Таблица 3.2. Результаты для запросов, связанных с мнением о продуктах. Обучение

на поисковых сниппетах

Продукты Исходный метод Модифицированный метод

Точность 0,5625 0,6319

Полнота 0,7840 0,8313

F-мера 0,6169 0,6695

Таблица 3.3. Результаты для запросов, сформированных на базе вопросов из Yahoo Answers. Обучение на текстах со страниц_________

Yahoo Answers Исходный метод Модифицированный метод (только кореферентные связи) Модифицированный метод

Точность 0,5167 0,5083 0,5437

Полнота 0,7361 0,7917 0,8333

F-мера 0,6008 0,5458 0,6278

Таблица 3.4. Результаты для запросов, сформированных на базе вопросов из Yahoo Answers. Обучение на поисковых сниппетах ____

Yahoo Answers Исходный метод Модифицированный метод (только кореферентные связи) Модифицированный метод

Точность 0,5950 0,6264 0,6794

Полнота 0,7329 0,7492 0,7900

F-мера 0,6249 0,6429 0,7067

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

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

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

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

Алгоритм состоит из двух этапов (второй этап может рассматриваться как самостоятельный алгоритм поиска тождественных денотатов в формальном контексте):

1. Преобразование онтологии в формальный контекст.

1.1 Преобразование онтологии в многозначный контекст;

1.2 Преобразование (шкалирование) мнозначного контекста в формальный контекст;

2. Поиск тождественных денотатов в формальном контексте.

2.1 Построение множества формальных понятий с помощью алгоритма АсМЬиеп!.

2.2 Фильтрация множества формальных понятий.

2.3 Формирование списков тождественных объектов в автоматическом или

полуавтоматическом (с участием эксперта) режиме.

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

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

Итоговый критерий йП представляет собой комбинацию (используются два варианта) данных индексов:

И'

2

БН. = * /2

к

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

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

В исследовании приводятся результаты экспериментов на реальных данных (онтология) и на искусственно сгенерированных данных (формальные контексты) с заранее известными тождественными объектами. При генерации данных учитывались особенности прикладной онтологии. Для оценки качества метода используются: полнота, точность, среднее значение полноты алгоритма при 100% значении точности, Mean Average Precision (MAP):

где К - множество контекстов, Ск - множество релевантных формальных понятий контекста к, Р{с) - доля релевантных понятий среди всех понятий, имеющих ранг не ниже, чем у понятия с.

Результаты экспериментов демонстрируют, что алгоритм на основе нового индекса (с использованием как одного, так и другого варианта комбинации) показал более высокие результаты, чем рассмотренные альтернативы. Основной отличительной особенностью метода является весьма небольшое падение точности алгоритма (до 90%) при росте полноты вплоть до 70%. Результаты для DII+ и Dil, оказались весьма схожими. Отличием Dil, стало менее стабильное поведение: иногда ошибаясь при большом пороге, в ряде случаев алгоритм не делал ошибок при малых порогах, выделяя при этом 42% тождественных объектов.

Тонкость

Рис. 4.1. Зависимость точности алгоритмов от полноты.

Точность

Рис. 4.2. Зависимость точности от полноты для двух вариантов нового индекса £>// Таблица 4.1. Максимальная полнота алгоритмов при максимальной точности

Алгоритм Максимальная полнота прн точности 100% (на экспериментальных данных)

Алгоритм на основе абсолютного расстояния 6.22%

Алгоритм на основе расстояния Хэмминга 0.56%

Алгоритм на основе индекса устойчивости 22.44%

Алгоритм на основе нового индекса 21.78%

Алгоритм на основе нового индекса £>//. 9.49%

При сравнении методов на основе индекса экстенсиональной устойчивости и вариантов нового индекса D//+ и DII, по мере MAP очевидное преимущество имеет новый индекс (таблица 4.2).

Таблица 4.2. Результаты по метрике Mean Average Precision.

Алгоритм MAP

Алгоритм на основе индекса устойчивости 0.499

Алгоритм на основе нового индекса О//,. 0.935

Алгоритм на основе нового индекса О//. 0.938

Для каждого метода был подобран оптимальный порог (максимальное расстояние от начала координат кривой «точность-полнота»), при котором алгоритм имеет оптимальную полноту при минимальных потерях точности (таблица 4.3). Новый метод продемонстрировал преимущество перед альтернативами.

Таблица 4.3. Оптимальные пороги для методов и качество поиска

Алгоритм Порог в алгоритме Полнота Точпость

На основе абсолютного расстояния 3.50 19.35% 98.82%

На основе расстояния Хэмминга 0.50 34.37% 86.32%

На основе индекса устойчивости 0.50 22.44% 100%

На основе нового индекса йН, 1.15 40.09% 99.58%

На основе нового индекса £>//. 0.90 31.80% 99.55%

Для экспериментов на реальных данных использовалась онтология, построенная по новостным документам политической направленности (12006 объектов различных классов). Количество признаков и связей с другими объектами распределено по закону Ципфа. В анализируемой онтологии проводился поиск тождественных денотатов среди объектов классов «Персона» и «Компания» (9821 объект). Признаки формального контекста строились с использованием всех объектов и связей в онтологии. Алгоритм на основе индекса Dil (использовался вариант DIIt) выделил 905 групп объектов. Размеры групп варьируются от 2 до 41 объекта. 98% выделенных групп полностью состоят из тождественных объектов, что соответствует точности в 98%.

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

• Работа с чащами разбора;

• Построение узорных структур на чащах разбора и их проекциях;

• Поиск: нахождение результатов и повторное ранжирование;

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

• Риторический парсер;

• Выделение коммуникативных действий.

В проекте используются следующие технологии:

• OpenNLP/Stanford NLP парсеры - для построения деревьев синтаксического разбора;

• Stanford NLP Coreference - для разрешения анафор и построения кореферентных связей;

• Bing API - для реализации базового поиска;

• Apache SOLR - для обеспечения интеграции с другими поисковыми системами;

• TK-Light - для обучения на деревьях с использованием ядер.

Часть компонентов проекта интегрирована в проект Apache OpenNLP.similarity. К ним относятся риторический парсер и модуль для работы с чащами. Архитектура комплекса предусматривает возможность интеграции с другими системами: например, он может быть подключен к библиотеке Lucene. В состав системы включен обработчик запросов SOLR, позволяющий интегрировать её в другие поисковые приложения.

Также в работе рассматривается модифицированный автором Formal Concept Analysis Research Toolbox (FCART) - программный комплекс анализа данных методами АФП. В текущей версии комплекса присутствуют следующие основные возможности по работе с Анализом Формальных Понятий:

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

2. Загрузка, редактирование, сохранение формальных контекстов.

3. Автоматическое построение решеток формальных понятий.

4. Работа с решетками формальных понятий:

4.1 Построение порядковых фильтров и идеалов, айсберга решетки;

4.2 Преобразование и настройка визуального представления решетки;

4.3 Сохранение решетки в нескольких форматах.

5. Построение базисов ассоциативных правил и импликаций.

6. Фильтрация формальных понятий с помощью индексов, реализованных в виде скриптов:

6.1 Индексы экстенсиональной и интенсиональной устойчивости;

6.2 Индекс отделимости;

6.3 Разработанный в рамках диссертационного исследования индекс £>//, предназначенный для выявления тождественных денотатов.

7. Сохранение результатов в виде отчетов.

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

В заключении приводятся основные выводы и ближайшие планы развития исследования.

Основные результаты работы

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

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

3. Таксономическое представление текстовых данных на основе решетки замкнутых структурных описаний и применение представления в задаче кластеризации коротких текстов.

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

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

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

Комплекс апробирован на нескольких реальных задачах, связанных с поиском и рекомендацией данных.

Публикации по теме диссертации

Публикации в журналах, входящих в перечень ВАК:

1. Ильвовский Д., Климушкин М. Выявление дубликатов объектов в прикладных онтологиях с помощью методов анализа формальных понятий. //НТИ, Сер. 2.-2013. - № 1. - С.10-17, 0.75 п.л. (вклад автора 0.5 п.л.)

2. Ильвовский Д., Применение семантически связанных деревьев синтаксического разбора в задаче поиска ответов на вопросы, состоящие из нескольких предложений. НТИ. Сер.2 - 2014. - № 2. - С.28-37, 0.9 пл. (вклад автора 0.9 п.л.)

3. Ильвовский Д. А., Черняк Е. JI. Системы автоматической обработки текстов// Открытые системы. СУБД. 2014. №01. С. 51-53. 0.45 п.л. (вклад автора 0.3 п.л.)

Прочие публикации:

1. Galitsky, В., Ilvovsky, D., Lebedeva, N., Usikov, D. Improving Trust in Automation of Social Promotion // 2014 AAAI Spring Symposium Series. -2014. 0.7 пл. (вклад автора 0.2 п.л.)

2. Ilvovsky D. A., Klimushkin M. A. FCA-based Search for Duplicate Objects in Ontologies, in: Proceedings of the Workshop Formal Concept Analysis Meets Information Retrieval / Отв. ред.: S. О. Kuznetsov, С. Carpineto, A. Napoli. Vol. 977. M.: CEUR Workshop Proceeding, 2013.0.5 пл. (вклад автора 0.3 пл.)

3. Neznanov A., Ilvovsky D. A., Kuznetsov S. FCART: A New FCA-based System for Data Analysis and Knowledge Discovery, in: Contributions to the 11th

International Conference on Formal Concept Analysis. Dresden: Qucoza, 2013. P. 31-44.0.6 п.л. (вклад автора 0.2 пл.)

4. Kuznetsov S. 0., Strok F. V., Ilvovsky D. A., Galitsky B. Improving Text Retrieval Efficiency with Pattern Structures on Parse Thickets , in: Proceedings of the Workshop Formal Concept Analysis Meets Information Retrieval / Отв. ред.: S. О. Kuznetsov, С. Carpineto, A. Napoli. Vol. 977. M.: CEUR Workshop Proceeding, 2013. P. 6-21. 0.77 п.л. (вклад автора 0.25 п.л.)

5. Galitsky В., Ilvovsky D. A., Kuznetsov S. O., Strok F. V. Parse thicket ■ representations of text paragraphs // По материалам ежегодной

Международной конференции «Диалог». Т.1. Вып. 12 (19). М.: РГГУ, 2013. С. 134-145. 0.73 пл. (вклад автора 0.2 пл.)

6. Ильвовский Д. А., Климушкин М. А. Выявление дубликатов объектов в прикладных онтологиях на основе методов анализа формальных понятий // Сборник докладов 9-й международной конференции ИОИ-2012. Торус Пресс, 2012. С.625-628. 0.2 пл. (вклад автора 0.1 пл.)

7. Galitsky В., Ilvovsky D., Kuznetsov S. О., Strok F. Matching sets of parse trees for answering multi-sentence questions // Proceedings of the Recent Advances in Natural Language Processing, RANLP 2013. - INCOMA Ltd. - 2013. - P. 285294. 0.8 пл. (вклад автора 0.3 пл.)

8. Galitsky, В. A., Ilvovsky, D., Kuznetsov, S. О., Strok, F. Finding Maximal Common Sub-parse Thickets for Multi-sentence Search. II Graph Structures for Knowledge Representation and Reasoning. Springer. - 2014. - P. 39-57. 1.1 п.л. (вклад автора 0.3 п.л.)

9. Ilvovsky D. Going beyond sentences when applying tree kernels // Proceedings of the Student Research Workshop - ACL 2014 - P. 56-63. 0.75 пл. (вклад автора 0.75 п.л.)

Лицензия ЛР № 020832 от 15 ноября 1993 г.

Подписано в печать 22 Ок-'?. 2014 г.

Формат 60 х 84/16

Бумага офсетная.

Печать офсетная.

Усл. печ. л. 1

Тираж 100 экз. Заказ №_ 6

Типография издательства

Национального исследовательского университета - Высшей школы

экономики,

125319, г. Москва, Кочновский проезд, д.З