Автореферат (Модели, алгоритмы и программные комплексы обработки текстовых данных на основе решеток замкнутых описаний)

На правах рукописиИЛЬВОВСКИЙДмитрий АлексеевичМОДЕЛИ, АЛГОРИТМЫ И ПРОГРАММНЫЕ КОМПЛЕКСЫОБРАБОТКИ ТЕКСТОВЫХ ДАННЫХ НА ОСНОВЕ РЕШЕТОКЗАМКНУТЫХ ОПИСАНИЙСпециальность 05.13.18Математическое моделирование, численные методы икомплексы программАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата технических наукМосква, 2014Работа выполнена в федеральном государственном автономном образовательном учреждениивысшего профессионального образования Национальный исследовательский университет «Высшаяшкола экономики»Научный руководительКузнецов Сергей Олегович, доктор физикоматематических наук, заведующий кафедройанализа данных и искусственного интеллектаНационального исследовательского университета«Высшая школа экономики»Официальные оппоненты:Аншаков Олег Михайлович, доктор физикоматематическихнаук,доценткафедрыматематики, логики и интеллектуальныхсистем в гуманитарной сфере Российскогогосударственного гуманитарного университетаЛукашевич Наталья Валентиновна, кандидатфизико-математических наук, ведущий научныйсотрудникНаучно-исследовательскоговычислительногоцентраМосковскогогосударственногоуниверситетаим.М.В.ЛомоносоваВедущая организация:Институт системного анализа РАНЗащита состоится «16» февраля 2015 г.

в 11:00 на заседании диссертационного совета Д 212.048.09Национального исследовательского университета «Высшая школа экономики», по адресу: 105187,г. Москва, ул. Кирпичная, д.33, ауд. 503.С диссертацией можно ознакомиться в библиотеке НИУ «Высшая школа экономики» по адресу:101990, г.

Москва, ул. Мясницкая, д. 20, и на сайте http://www.hse.ru/sci/diss/.Автореферат разослан « » октября 2014 г.Ученый секретарьдиссертационного совета,д.т.н., профессорНазаров Станислав Викторович3Общая характеристика работыАктуальность работы. Моделирование языковых процессов порождаетзначительноеколичествооткрытыхпроблем,связанныхсразвитиемсоответствующего математического аппарата, созданием и реализациейэффективных алгоритмов и комплексов программ. К настоящему моментуразработано значительное количество хорошо развитых моделей текста,позволяющих (помимо представления текста) вычислять сходство междутекстами: «мешок слов», n-граммы, синтаксические деревья разбора и т.д.Средиисследователей,внесшихзначительныйвкладвразработкуиприменение этих моделей в прикладных задачах (для английского языка),можно отметить C.Manning, H.Schutze, D.Jurafsky, S.Abney, M.Collins,A.Moschitti и многих других.

Подавляющее большинство реализованных напрактике моделей не полностью учитывает структурные особенности текста,ограничиваясь либо частотными характеристиками слов и n-грамм, либосинтаксическими связями внутри отдельных предложений. Эти модели непозволяют работать с текстом на уровне фрагментов, состоящих из несколькихсвязанных предложений ‒ абзацев. К другому классу моделей относятсямногочисленныелингвистическиетеории,втойилиинойстепениучитывающих семантические связи между предложениями. Здесь можноотметить работы таких исследователей как W.Mann, D.Marcu, J.Searle,I.Mel’cuk, H.Kamp, M.Recaesens, D.Jurafsky и многих других.

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

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

Включенный втеорию аппарат проекций позволяет эффективно работать с приближеннымиописаниями, в той или иной мере учитывающими основные свойства структурыи понижающими вычислительную и временную сложность обработки этихописаний.Объект исследований – математические модели текстов на естественномязыке. Предмет исследований – модели текстов на естественном языке,предназначенные для поиска, классификации и кластеризации текстовыхданных.Цельюдиссертационногоисследованияявляетсяразработкаоригинальных моделей, методов, алгоритмов и программных комплексов,предназначенных для поиска, классификации и кластеризации текстовыхданных.5К задачам исследования относятся: Разработкаструктурноймоделитекстовнаестественном языке,ориентированной на поиск, классификацию и кластеризацию текстов ииспользующей синтаксические и семантические связи внутри текста; Применение построенной модели в задаче поиска сходства текстов сцелью улучшения релевантности поиска по сложным запросам; Применение построенной модели в задаче классификации текстов сцельюповышениякачествасуществующихметодовзасчетиспользования семантической информации; Построениенапредставленияосноветекстовыхразработаннойдокументовмоделистаксономическогоиспользованиемрешетокзамкнутых структурных описаний и применение представления в задачекластеризации текстов; Разработка математической модели и метода для определения связи «таже сущность» в формальных описаниях, построенных на основетекстовых данных и ее эффективная алгоритмическая реализация. Реализация разработанных моделей, методов и алгоритмов в видепрограммного комплекса.К методам, использовавшимся в исследовании, относятся: Методы построения и анализа решёток замкнутых описаний; Методы фильтрации решеток понятий на основе индексов качествамоделей; Методы построения проекций моделей на узорных структурах; Методы построения структурных моделей для текстовых данных; Методы построения синтаксических и семантических моделей текста; Методы порождения моделей, основанных на графовом представлении.6Научная новизна.

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

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

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

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

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

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

Компания Авикомп внедрила методвыявления тождественных денотатов для оптимизации прикладной онтологии.8Все разработанные методы были реализованы в виде программного комплекса,предназначенного для решения исследовательских и прикладных задач.Достоверность полученных результатов подтверждена строгостьюпостроенныхматематическихмоделей,экспериментальнойпроверкойрезультатов численных расчетов и практической эффективностью программныхреализаций.Апробациярезультатовработы.Основныерезультатыработыобсуждались и докладывались на следующих научных конференциях исеминарах: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-й международной конференции по компьютерной лингвистике RANLP2013, Хисаря, Болгария.7.