Описание подходов к упорядочению текстов выдачи поисковой системы по близости к запросу с использованием модели машинного обучения, основанной на сравнении деревьев синтаксического разбора. Результаты использования выборки запросов на английском языке.
Аннотация к работе
Повышение релевантности мета-поиска с использованием деревьев синтаксического разбора Московский Физико-Технический Институт, Москва В работе описаны подходы к упорядочению текстов выдачи поисковой системы по близости к запросу с использованием модели машинного обучения, основанной на сравнении деревьев синтаксического разбора.Использование синтаксической структуры предложений для анализа семантики предложений встречается в различных методах извлечения информации и при создании вопросно-ответных систем [Allen, 1987], [Cardie et al., 1999], [Ravichandran et al., 2002]. В этой работе сначала схематически излагается процесс построения общей части двух предложений, использующий деревья синтаксического разбора. В работе используется идея и программная реализация построения обобщения двух предложений, предложенная в работах [Galitsky et al., 2008], [Galitsky, 2010]. Она выделяет семантическую информацию о схожести двух предложений в виде синтаксической структуры, которая может быть семантически интерпретирована как общий смысл двух предложений. Общее двух предложений находится следующим образом: Для каждого предложения производится синтаксический разбор.Результаты компьютерных экспериментов говорят о том, что сходство структур предложений, описанное даже небольшим набором простых числовых признаков, может быть эффективно использовано для восстановления порядка близости предложений в списках к целевому предложению (запросу).
Введение
Использование синтаксической структуры предложений для анализа семантики предложений встречается в различных методах извлечения информации и при создании вопросно-ответных систем [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.