diss005-ilvovsky_AvtoRef (Методы и алгоритмы обработки текстовых данных на основе графовых дискурсивных моделей), страница 4

Обучениена текстах со страницМетод MoschittiДисс. методПродуктыТочность56,858,7Полнота75,284,6F-мера64,967,5Таблица 3.2. Результаты для запросов, связанных с мнением о продуктах. Обучениена поисковых сниппетахМетод MoschittiДисс. методПродуктыТочность56,363,2Полнота78,483,1F-мера61,767Таблица 3.3. Результаты для запросов, сформированных на базе вопросов из YahooAnswers. Обучение на текстах со страницМетод MoschittiДисс. метод (толькоДисс. методYahooкореферентные связи)AnswersТочность51,750,854,4Полнота73,679,283,3F-мера60,154,662,819Таблица 3.4. Результаты для запросов, сформированных на базе вопросов из YahooAnswers.

Обучение на поисковых сниппетахМетод MoschittiДисс. метод (толькоДисс. методYahooкореферентные связи)AnswersТочность59,562,667,9Полнота73,374,979F-мера62,564,370,7Эксперименты демонстрируют, что добавление новых признаков безизменениясхемыэкспериментаулучшаеткачествоклассификациисуществующего подхода.

Это улучшение колеблется в диапазоне от 2 до 8 %для текстов из нескольких областей, имеющих различную структуру. При этомулучшение и внедрение дополнительных признаков не требуют доработкисамого алгоритма обучения на деревьях.В задаче классификации технических документов рассматриваютсядокументы, относящиеся к двум классам:1. Action-plan (описание оригинальной разработки) - документ, которыйсодержит четкое и хорошо структурированное описание того, как построитьконкретную систему в какой-либо области.2. Meta-document (мета-описание) – документ, объясняющий, как писатьдокументы, относящиеся к первому классу, например, инструкция, учебник,технический стандарт и т.д.Данная задача важна с практической точки зрения.

«Мета-документы»,как правило, содержат общедоступную информацию и могут распространятьсясвободно. Описание же оригинальных разработок является собственностьюкомпаний и не может передаваться и копироваться без их разрешения.Эксперименты проводились на наборе из нескольких тысяч документов,имеющих сходную тематику и практически совпадающие ключевые слова. Этиданные были разбиты на 3 группы для проведения обучения и тестирования пометоду кросс-валидации20Таблица 3.5. Результаты классификации технических документов.Метод«Ближайшие соседи» (на основе TF*IDF)Наивный БайесовскийЯдра на синтаксических деревьяхЯдра на расширенных деревьях (толькоанафора), Дисс.Ядра на расширенных деревьях (толькоRST), Дисс.Ядра на расширенных деревьях (анафора+RST), Дисс.Точность, %53.955.371.4Полнота,%6259.776.9F-мера,%57.67+-0.6257.42+-0.8474.05+-0.5577.881.479.56+-0.7080.180.580+-1.0383.383.683.45+-0.78Эксперименты демонстрируют, что обучение на расширенных деревьяхсущественнопревосходитпокачествуклассификацииальтернативныеподходов, основанные на использовании синтаксических деревьев и «мешкаслов» (наивный байесовский классификатор и метод ближайших соседей).Преимущество по F-мере по сравнению с обучением на синтаксическихдеревьях составляет 9%, по сравнению с классификаторами на основе «мешкаслов» - 30%.В четвертой главе рассматривается задача выявления тождественныхденотатов для случая формальных описаний, построенных на основепредварительно обработанных текстовых данных.

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

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

Поиск тождественных денотатов в формальном контексте.2.1Построение множества формальных понятий с помощью алгоритмаAddIntent.2.2Фильтрация множества формальных понятий.2.3Формирование списков тождественных объектов в автоматическом илиполуавтоматическом (с участием эксперта) режиме.Висследованиипредлагаетсячисловойкритерий(индекс)дляфильтрации формальных понятий. Чем выше значение индекса, тем выше22уверенность в том, что понятие содержит тождественные объекты. При подборекритериев были учтены основные свойства, которыми должны обладать этипонятия. Во-первых, критерий должен принимать большее значение, если, припрочих равных, число признаков, которыми отличаются объекты понятия,будет меньше:I1( A, B) | A || B | gA gВторое свойство - увеличение значение индекса при увеличении числаобщих признаков (при прочих равных).

При этом распространенный признакделает меньший вклад в значение критерия, чем редкий признак, так как чемпризнак более распространен, тем больше шансов, что понятие с даннымпризнаком возникло из-за случайного пересечения признаков:I 2 ( A, B)  mBAmИтоговый критерий DII представляет собой комбинацию (используютсядва варианта) данных индексов:DII   I1  kI 2DII  I1  I 2kНеизвестный коэффициент может определяться с помощью экспертнойоценки, так как интерпретация обоих индексов достаточно легка дляпонимания. Алгоритм предусматривает два режима работы: автоматическоепринятие решения и полуавтоматический режим с привлечением экспертааналитика.В исследовании проводится сравнительный анализ разработанногометода с методами попарного сравнения объектов на основе расстояния23Хэмминга и абсолютного сходства, применявшимися для решения задачи допроведения исследования, а также с методом, основанным на индексеэкстенсиональной устойчивости понятия.В исследовании приводятся результаты экспериментов на реальныхданных (онтология) и на искусственно сгенерированных данных (формальныеконтексты) с заранее известными тождественными объектами.

При генерацииданных учитывались особенности прикладной онтологии. Для оценки качестваметода использовались: полнота, точность, среднее значение полнотыалгоритма при 100% значении точности, Mean Average Precision (MAP): AveP( Ki )Map( K )  i 1KKAveP(k )  cC ( P(c)) ,kCkгде K - множество контекстов, Ck - множество релевантных формальныхпонятий контекста k, P(c) - доля релевантных понятий среди всех понятий,имеющих ранг не ниже, чем у понятия c.Результаты экспериментов демонстрируют, что алгоритм на основе обоихвариантовновогоиндексапоказалболеевысокиерезультаты,чемрассмотренные альтернативы.

Основной отличительной особенностью методаявляется весьма небольшое падение точности алгоритма (до 90%) при ростеполноты вплоть до 70%. Вариант DII был менее стабилен на больших порогах.24Рис. 4.1. Зависимость точности алгоритмов от полноты.Рис. 4.2. Зависимость точности от полноты для двух вариантов нового индекса DII25Таблица 4.1. Максимальная полнота алгоритмов при максимальной точностиАлгоритмМаксимальная полнота приточности 100% (наэкспериментальных данных)Алгоритм на основеабсолютного расстояния6.22%Алгоритм на основерасстояния Хэмминга0.56%Алгоритм на основе индексаустойчивости22.44%Алгоритм на основе индекса21.78%DII Алгоритм на основе индекса9.49%DIIПрисравненииметодовнаосновеиндексаэкстенсиональнойустойчивости и вариантов нового индекса DII  и DII по мере MAP очевидноепреимущество имеет новый индекс (таблица 4.2).Таблица 4.2.

Результаты по метрике Mean Average Precision.АлгоритмMAPАлгоритм на основе индекса устойчивости0.499Алгоритм на основе нового индекса DII 0.935Алгоритм на основе нового индекса DII0.938Для каждого метода был подобран оптимальный порог (максимальноерасстояние от начала координат кривой «точность-полнота»), при которомалгоритм имеет оптимальную полноту при минимальных потерях точности(таблица4.3).Новыйметодпродемонстрировалпреимуществоальтернативами.Таблица 4.3. Оптимальные пороги для методов и качество поискаАлгоритмПорог вПолнотаТочностьалгоритмеНа основе абсолютного расстояния3.5019.35%98.82%На основе расстояния Хэмминга0.5034.37%86.32%На основе индекса устойчивости0.5022.44%100%На основе нового индекса DII 1.1540.09%99.58%На основе нового индекса DII0.9031.80%99.55%перед26Для экспериментов на реальных данных использовалась онтология,построенная по новостным документам политической направленности (12006объектов различных классов), в которой проводился поиск тождественныхденотатов среди объектов классов «Персона» и «Компания» (9821 объект).Признаки формального контекста строились с использованием всех объектов исвязей в онтологии.

Алгоритм на основе индекса DII (использовался вариантDII  ) выделил 905 групп объектов, размеры которых варьируются от 2 до 41.98% выделенных групп полностью состоят из тождественных объектов, чтосоответствует точности в 98%.В пятой главе описывается построенный в рамках исследованияпрограммный комплекс, предназначенный для обработки текстовых данных спомощью чащ разбора и включающий в себя оригинальные модули,предназначенные для работы с чащами разбора, для построения узорныхструктур на чащах разбора и их проекциях, для поиска и обучения на текстах ит.д.В проекте используются следующие технологии и программные средства: OpenNLP/StanfordNLPпарсеры–дляпостроениядеревьевсинтаксического разбора; Stanford NLP Coreference – для построения кореферентных связей; Bing API – для реализации базового поиска; Apache SOLR – для обеспечения интеграции с поисковыми системами; РиторическийпарсерJoty–дляавтоматическогопостроениядискурсивных деревьев на основе машинного обучения. TK-Light ‒ для обучения на деревьях с использованием ядер.Архитектура комплекса предусматривает возможность интеграции сдругими системами, в том числе с поисковыми приложениями.27Также в работе рассматривается Formal Concept Analysis Research Toolbox(FCART) – программный комплекс для анализа данных методами АФП.

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