Повышение релевантности мета-поиска с использованием деревьев синтаксического разбора
Описание подходов к упорядочению текстов выдачи поисковой системы по близости к запросу с использованием модели машинного обучения, основанной на сравнении деревьев синтаксического разбора. Результаты использования выборки запросов на английском языке.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | статья |
Язык | русский |
Дата добавления | 19.01.2018 |
Размер файла | 17,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Повышение релевантности мета-поиска с использованием деревьев синтаксического разбора
Б.А. Галицкий (bgalitsky@hotmail.com)
Университет Girona, Испания
Д.А. Дремов (dremovd@gmail.com)
Московский Физико-Технический Институт, Москва
С.О. Кузнецов (skuznetsov@yandex.ru)
Высшая Школа Экономики, Москва
Аннотация
поисковый система запрос синтаксический
В работе описаны подходы к упорядочению текстов выдачи поисковой системы по близости к запросу с использованием модели машинного обучения, основанной на сравнении деревьев синтаксического разбора. Для машинного обучения используется выборка запросов и упорядоченных ответов на английском языке.
Введение
Использование синтаксической структуры предложений для анализа семантики предложений встречается в различных методах извлечения информации и при создании вопросно-ответных систем [Allen, 1987], [Cardie et al., 1999], [Ravichandran et al., 2002]. В последнее десятилетие произошел существенный сдвиг в компьютерной лингвистике от полностью ручного конструирования грамматик и баз знаний до частичной и полной автоматизации процесса, с использованием статистических методов с обучением на больших языковых корпусах.
В этой работе сначала схематически излагается процесс построения общей части двух предложений, использующий деревья синтаксического разбора. Затем для задачи поиска описана модель использования результатов сравнения для упорядочения предложений.
Для указанной модели предложен способ сведения задачи к задаче обучения по множеству поисковых запросов и соответствующих запросу правильно упорядоченных найденных фрагментов текста. Обучающая выборка строится при помощи поиска в Yahoo, через поисковый API Yahoo ручным упорядочиванием и фильтрацией.
1. Построение общего двух предложений
В работе используется идея и программная реализация построения обобщения двух предложений, предложенная в работах [Galitsky et al., 2008], [Galitsky, 2010].
Операция построения общего двух предложений является формальной операцией на деревьях синтаксического разбора предложений. Она выделяет семантическую информацию о схожести двух предложений в виде синтаксической структуры, которая может быть семантически интерпретирована как общий смысл двух предложений.
1.1 Обобщение пары предложений
Общее двух предложений находится следующим образом:
Для каждого предложения производится синтаксический разбор. Результатом являются деревья синтаксического разбора, каждая из вершин которых - слово (lemma), часть речи (Part of speech, POS), информация о форме слова. Для этих целей используется open source продукт OpenNLP, реализованный на java.
Разобранные предложения разбиваются на поддеревья-фразы разных типов: verb, noun, prepositional и другие. Поддеревья хранятся так, что сохраняется информация об их вхождении в дерево синтаксического разбора предложения.
Все поддеревья разбиваются на группы по типам фраз.
В множество всех поддеревьев добавляются деревья, полученные из них рядом эквивалентных преобразований, меняющих структуру предложения с сохранением семантики. Например: «Cell phone can be easily grasped by a hand palm» и «Hand palm can easily grasp the cell phone»
Обобщается каждая пара поддеревьев одного типа разных предложений:
Для каждой пары поддеревьев производится выравнивание. Выравнивние здесь обозначает -- соответствие конечных вершин-слов. Выравнивание производится при помощи алгоритма выравнивания последовательностей принятого в биоинформатике «protein sequence alignment» [Smith et al., 1981].
Затем для полученного выравнивания производится обобщение поддеревьев по парам соответствующих вершин (как производится обобщение пары вершин описано ниже). Для полученного множества деревьев результатов обобщения вычисляем числовую функцию, отвечающую за общность полученного обобщения (она описана ниже).
Для каждой пары поддеревьев по каждой фразе из множества фраз выбирается дерево, полученное обобщением с наибольшим значением функции посчитанной выше (наименее общую).
Полученные деревья группируются в множества по типам фразы (verb, noun, и др.).
Из каждого множества, соответствующего типу фразы, исключаются все деревья-обобщения, более общие, чем другие деревья-обобщения этого множества.
1.2 Обобщение пары вершин
Для пары вершин, представляемых тройкой (POS, lemma, form), обобщение происходит следующим образом:
Если тройки совпадают -- обобщением является та же тройка.
Если различается только форма (например, для слов в единственном и множественном числе), обобщением является тройка (POS, lemma, *).
Если различается только слово, обобщением является (POS, *, *), то есть у слов считается общей только часть речи.
Если различается часть речи, то обобщение пустое: (*, *, *), даже если слова одинаковые.
1.3 Функция, используемая для выбора наименее общего дерева
Для каждой вершины являющейся обобщением пары вершин вычисляется вес, быстро убывающих в таком порядке: noun и verb, другие части речи, совпадения части речи без совпадения слова. Веса для дерева складываются.
2. Обобщение предложений в задаче поиска документов
По каждому запросу предлагается осуществлять обычный полнотекстовый поиск, использующий поиск документов по включению в них слов, содержащихся в запросе, и затем производить операцию поиска общего предложения запроса-фразы и отрывков документа, где встречаются найденные слова запроса. Далее, используя функцию оценки релевантности (описанную ниже), считаемую на обобщении, можно переупорядочить документы, в частности фильтровать документы, имеющие малое отношение к запросу.
2.1 Переход к числовому признаковому описанию
Мы строим дискретные числовые признаки описания общего двух предложений:
Для каждой общей части двух фраз определяются количества совпавших одновременно частей речи вместе со словом.
Когда слова разные, определяются количества совпавших частей речи.
Группировка некоторых близких форм частей речи (например, разные единственная и множественная формы одной части речи).
Тем самым осуществляется переход от структурного описания общего к числовому признаковому описанию, которое представляется в виде столбца неотрицательных целых чисел. На данном этапе мы теряем информацию о структуре «общего», но полагаем что информация о структуре, в первую очередь, нужна для нахождения общих частей, а для оценки «значимости» общей части достаточно выбранного признакового описания.
В данной работе рассматривается линейный вид функции релевантности, параметрами которой являются указанные выше числовые признаки. Таким образом, функция релевантности - линейная комбинация количества появлений в обобщениях фраз каждой из частей речи (с совпадением слова и без, то есть имеющие разные признаки и коэффициенты).
3. Сведение задачи оптимизации коэффициентов модели к задаче машинного обучения
Одним из способов оптимизации коэффициентов функции релевантности является использование обучающей выборки правильно упорядоченных предложений, связанных с некоторым запросом. Данные получаются при помощи поиска Yahoo, через поисковый API Yahoo.
В рамках модели предложенной выше, на выборке отсортированной и отфильтрованной вручную из запросов на тему налогов, было произведено обучение с использованием метода опорных векторов, в частности пакета svm_rank (часть пакета svm_light, оптимизированного для обучения по наборам упорядоченных величин).
Результаты оцениваются по следующей мере: среднее отклонение верного порядка от порядка, получаемого при сортировке по функции релевантности. Отклонения порядков считаются как расстояния тау кендала между списками, которое определяется, как отношение количества пар элементов стоящих в неверном порядке, к общему числу пар элементов списка. Расстояние, таким образом, лежит в интервале [0; 1].
4. Компьютерный эксперимент и обсуждение результатов
Экспериментальные расчеты производились для данных, полученных из 200 предложений (запросов и ответов в сумме), состоящих из примерно 1000 неравенств в обучающей выборке и 500 в тестовой.
Вычисления производились на персональном компьютере с процессором Intel Core 2DUO T8100 (2.1GHz) и 2Гб оперативной памяти под управлением ОС Ubuntu linux. Время, затраченное на обучение, зависело от параметров обучения и составляло от ~100 мс до ~100 с.
В таблице 1 приведены экспериментальные значения ошибок для некоторых обучающей и тестовой выборок, параметр “с” отвечает за соотношение важности ошибки обучения и зазора. Больший параметр “c” приводит к переобученности.
Ошибку следует сравнивать с ошибкой случайно упорядоченного списка, которая составляет примерно 0,5 (примерно, так как для части элементов списка функция релевантности будет совпадать, что будет считаться за неверный порядок).
Для обучающей выборки ошибка считается для тех же значений, по которым проводилось обучение.
Таблиця 1
Описание |
Ошибка на обучающей выборке |
Ошибка на тестовой выборке |
|
Линейная (с=10) |
0,36 |
0,37 |
|
Линейная (с=1) |
0,35 |
0,36 |
|
Линейная (с=0,1) |
0,36 |
0,35 |
|
Полиномиальная (с=0,1) |
0,26 |
0,43 |
|
Полиномиальная (с=0,01) |
0,29 |
0,39 |
|
Полиномиальная (с=0,001) |
0,34 |
0,37 |
|
Полиномиальная (с=0,0001) |
0,34 |
0,34 |
Используемая модель оценки сходства структур предложений позволяет среди поисковых ответов на заданный запрос частично восстановить верный порядок, отвечающий пользовательскому ранжированию релевантности ответов. Важно заметить, что ранжирование происходит среди уже отфильтрованных поисковой машиной по релевантности первых 30 отрывках документа (с удалением дубликатов), то есть среди отрывков, которые имеют большую оценку поискового движка схожести с запросом. Эта схожесть обычно выражается в наличии в отрывках документа слов запроса, в соответствии с моделью “Bag of words”.
Заключение
Результаты компьютерных экспериментов говорят о том, что сходство структур предложений, описанное даже небольшим набором простых числовых признаков, может быть эффективно использовано для восстановления порядка близости предложений в списках к целевому предложению (запросу). Имея обучающую выборку запросов и найденных документов, упорядоченных пользователем, можно автоматически восстанавливать функцию релевантности, отвечающую за близость запроса к документу. Функция релевантности, в свою очередь, может быть использована для улучшения релевантности поиска путем переупорядочивания результатов поисков документов по включению слов запроса.
Список литературы
[Вапник, 1979] Вапник В.Н., Восстановление зависимостей по эмпирическим данным. - М.: Наука, 1979.
[Allen, 1987] Allen J. F., Natural Language Understanding // Benjamin Cummings.
[Cardie et al., 1999] Cardie C., Mooney R.J. Machine Learning and Natural Language // Machine Learning, 1(5), 1999.
[Galitsky et al.] Galitsky B., Lluis de la Rosa J., Dobrocsi G. Inferring semantic properties of sentences mining syntactic parse trees Galitsky, Lluis de la Rosa и Dobrocsi // В печати.
[Galitsky et al., 2008] Galitsky B., Kuznetsov SO Learning communicative actions of conflicting human agents // J. Exp. Theor. Artif. Intell. 20(4): 277-317 (2008).
[Ravichandran et al., 2002] Ravichandran D., Hovy E. Learning surface text patterns for a Question Answering system // In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL 2002), Philadelphia, PA.
[Smith et al., 1981] Comparative biosequence metrics // Springer New York.
Размещено на Allbest.ru
...Подобные документы
Конструкции условных операторов if-else и простые типы языка Си. Общая схема работы компилятора. Алгоритм построения дерева разбора, строки вывода синтаксического разбора. Построение обратной польской записи как формы внутреннего представления программы.
курсовая работа [1,3 M], добавлен 01.06.2013Понятие семантики; обзор и анализ существующих средств семантического разбора естественно-языковых текстов. Разработка алгоритма работы системы на основе семантического анализа, его реализация на языке программирования; проектирование интерфейса системы.
дипломная работа [1,7 M], добавлен 18.03.2012Понятие синтаксического анализа. Программный продукт для обработки данных строкового типа. Построение сканера текстов с использованием утилиты flex, синтаксического анализатора с помощью утилиты bison. Грамматика языка программирования обработки строк.
курсовая работа [261,7 K], добавлен 29.10.2012Изображения древовидной структуры. Десятичная система обозначений Дьюи. Стандартные формы представления деревьев. Представление деревьев с использованием списков, с использованием списков сыновей. Полное бинарное дерево. Основные операции над кучей.
презентация [495,0 K], добавлен 19.01.2014Место компилятора в программном обеспечении. Принципы работы и автоматизация построения синтаксического анализатора. Дерево разбора и его преобразование в дерево операций. Назначение и этапы семантического анализа. Идентификация языков программирования.
реферат [265,1 K], добавлен 20.12.2007Общая характеристика и оценка возможностей языка программирования си-шарп, его сходные и отличительные черты от С++ и Java. Разработка с помощью данного языка программирования лексического и синтаксического анализатора. Составление таблиц разбора.
курсовая работа [111,6 K], добавлен 11.06.2010Основные понятия теории грамматик простого и операторного предшествования, алгоритмы синтаксического разбора предложения для классов КС-грамматик; разработка дерева вывода для грамматики входного языка в форме Бэкуса-Наура с указанием шагов построения.
лабораторная работа [28,0 K], добавлен 24.07.2012Методы грамматического разбора. Разработка структуры учебного транслятора на базовом языке программирования Object Pascal в среде объектно-ориентированного визуального программирования Borland DELPHI 6.0 с использованием операционной системы Windows XP.
курсовая работа [493,8 K], добавлен 12.05.2013Разработка приложения для проверки использования времен глаголов в английском языке. Создание базы данных. Анализ используемых средств для реализации автоматического разбора текста. Проектирование мобильного приложения с помощью диаграмм деятельности.
дипломная работа [2,6 M], добавлен 13.09.2017Проектирование базы данных, отражающей информацию о поездах дальнего следования с использованием алгоритма деревьев. Разновидности деревьев и принцип выбора оптимального из них для создания программы. Модули программы и их функции, анализ работы ПО.
курсовая работа [28,1 K], добавлен 11.07.2009Методы грамматического разбора при разработке учебного транслятора. Проектирование лексического анализатора и магазинного автомата. Программная реализация синтаксического анализатора текстового языка высокого уровня. Разработка модуля интерпретации.
курсовая работа [697,2 K], добавлен 06.01.2013Рассмотрение принципов поисковой системы и процедуры проведения поиска по запросам пользователей "Яндекса". Изучение структуры запросов, вспомогательных программ поиска, модулей и этапов их преобразования. Описание дополнительной информации в сниппете.
реферат [135,6 K], добавлен 27.12.2014Разработка информационной системы для регистрации постояльцев в гостинице с использованием структур данных и алгоритмов. Методы хеширования и сортировки данных. Обходы бинарных деревьев. Линейный однонаправленный список. Описание и тестирование программы.
курсовая работа [2,3 M], добавлен 09.03.2014Разработка технического задания на проектирование, определение требований к программе. Предварительный выбор метода решения синтаксического анализатора, проектирование программного приложения, конфигурация технических средств программы и её тестирование.
курсовая работа [28,5 K], добавлен 28.06.2011Разработка программной системы для поддержки генеалогических деревьев. Модели вариантов использования и анализа системы. Морфологическая и функциональная модели, диаграммы состояний, деятельности и взаимодействия. Хранение сведений в базах данных.
курсовая работа [535,2 K], добавлен 01.02.2013Понятие и принципы работы, внутренняя структура и элементы, история формирования и развития поисковой системы "Rambler". Исследование и анализ, а также оценка эффективности данной поисковой системы для поиска экономической информации в интернете.
курсовая работа [4,0 M], добавлен 10.05.2015Создание алгоритма для построения синтаксического анализатора полиномов и его реализация в среде Visual Studio 2005 на языке программирования C#. Программное решение задачи поиска максимального числа единиц в бинарном представлении простых чисел.
курсовая работа [723,5 K], добавлен 04.10.2010Понятие и принципы построения трансляторов. Методика написания программы на языке программирования С++, реализующей определенные действия над математическими выражениями. Написание транслятора с языка математических выражений на язык деревьев вывода.
курсовая работа [423,3 K], добавлен 24.08.2009Изучение символьных и строковых типов данных, алгоритма задачи на языке программирования Паскаль. Описания получения и установки отдельного символа строки, изменения регистра символов. Анализ создания и просмотра файла, поиска и сортировки информации.
курсовая работа [440,7 K], добавлен 13.06.2011Структура оптимальных бинарных деревьев поиска. Рекурсивное решение; вычисление математического ожидания стоимости поиска; выбор ключа, который приводит к его минимальному значению. Вычисленные с помощью процедуры Optimal_BST для распределения ключей.
доклад [1,2 M], добавлен 14.11.2011