Особенности разработки алгоритма, обеспечивающего числовые термы в логико-марковской сети. Знакомство с основными понятиями марковской сети. Рассмотрение способов регулирования целевой функции с введением темпоральной семантико-синтаксической меры.
Аннотация к работе
Эта задача связана с проблемой определения описания временных выражений в тексте, а также определения самого события. После того как эта информация уже была извлечена, она может использована для создания более структурированной базы знания, которую можно легко использовать в других системах обработки естественного языка (ОЕЯ), таких как, система поиска, система реферирования документов и вопросно-ответная система,… Аппараты логики, например логика первого порядка и нечеткая логика, имеют широкие возможности для представления различных связей между явлениями в естественном языке, но они ограничены в способности обучении. Для каждого события, определены предикаты, описывающие разные его грамматические характеристики: Tense(e,!t), Perfect(e,!p), Aspect(e,!a), Class(e,!c), Modal (e,!m), Polarity(e,!p), Verb Class(e,!v), где e - событие, знак «!» означает, что каждое событие е принадлежит только одному классу Для описания случая, когда специальные слова (союзы) присутствуют между событиями (мы, предложено, считаем момент времени как специальное событие), мы приводим предикат Have Connected Word (e1,e2, c), где е1, е2 - события, с есть союзное слово, например, перед тем как, после, во время, с тех пор, когда, пока, как, в то время как,…В работе предложен новый подход решения задаче извлечения временной информации с помощью аппарата логико-марковской сети.
Введение
В связи с увеличением количества доступных электронных текстов, требование к системам автоматической обработки и извлечения информации из документов на естественном языке для различных целей, таких, как добыча данных, значительно возросло. Например, мы, возможно, будем интересоваться, когда и за сколько время одно событие, описано в новости случилось. Эта задача связана с проблемой определения описания временных выражений в тексте, а также определения самого события. Например, дано следующее предложение: «С 1-ого января в Москве подорожает проезд в общественном транспорте»
Исходя из этого предложения, мы можем извлекать что «подорожание» - это событие, и что оно случится с«1-ого января». После того как эта информация уже была извлечена, она может использована для создания более структурированной базы знания, которую можно легко использовать в других системах обработки естественного языка (ОЕЯ), таких как, система поиска, система реферирования документов и вопросно-ответная система,…
Задача извлечения временной информации из текста на естественном языке интенсивно исследуется в последние годы. Она можно разделиться на четыре подзадачи: · Идентификация временных выражений;
· Идентификация событий в тексте;
· Поиск описания времени для события;
· Определение временных отношений между событиями в тексте.
Различные подходы были проанализированы и применяются для решения этой задачи. Три основные подходы включают: традиционный подход,основанный на использование правил, полученных от экспертов лингвистических знаний, подход, основанный на статистические методы, использованы одно из нескольких алгоритмов машинного обучения, и гибридный подход. В работе [1] авторы объяснили преимущества и недостатки каждого из этих подходов. По сути, задача обработки естественного языка сложна изза двусмысленности и неполноты знания. Это вызывает трудность и неэффективность при применении статистических методов, так как большинство из них требует представить объект обучения в виде признаковых векторов. Аппараты логики, например логика первого порядка и нечеткая логика, имеют широкие возможности для представления различных связей между явлениями в естественном языке, но они ограничены в способности обучении. Самые эффективные системы индуктивного обучения и вывода, такие как ALEPH [3], FOIL [4], Claudien достигли не очень высокой адекватности.
В данной работе, мы предлагаем новый метод для решения задачи извлечения временной информации с помощью аппарата логико-марковской сети (Markovlogicnetworks), которая разработана в 2006г. (ряд работы Домингоса и др. с 2006г. по 2008). Этот аппарат является вероятностным обобщением логики первого порядка, статистического обучения, позволяющего автоматически оценивать обоснованность выбранной модели явления и индуктивных правил, описывающих нестрогие зависимости между данными. Аппарат логико-марковской сети является самым удачным механизмом объединения мощности представления знания в традиционной двоичной логике и эффективности статистического обучения. Мы также разработали алгоритм, обеспечивающий числовые термы в логико-марковской сети и регулирование целевой функции с введением темпоральной семантико-синтаксической меры.
Структура статьи состоит из четырех частей. Мы начинаем с описанием основных понятий марковской сети, логики первого порядка и логико-марковской сети. Потом мы будем подробно описывать ее применение в решении нашей задачи. В конце мы представляем меру близости для временных отношений и их интеграцию в Марковской сети.
1. Логико-марковская сеть сеть синтаксический числовой
Логико-марковская сеть (Markov logic networks) комбинирует логику первого порядка и марковскую сеть. В обычной базе знания на основе правилах продукции (логике первого порядка) типа «IFXISETHENYISA», если хотя одно утверждение не выполняется, то полнота БЗ (мира) нарушается. MLNS можно рассмотреть как обобщение логики первого порядка, при которой, когда одна формула не выполняется, то БЗ (мира) имеет меньшую возможности существования.
Логико-марковская сеть представляет собой множество пар {(Fi,wi)}, где: Fi - Формула в логике первого порядка wi - Действительное число
{(Fi,wi)} вместе с набором констант C = (c1,c2,…,c|C|) используются как шаблон для создания марковской сети ML,C , содержащей: · одну вершину для каждой возможной интерпретации (grounding) любого предиката в L. Данной вершине присваивается значение 1 если ее интерпретация верна, и 0 в обратном случае;
· один фактор для каждой интерпретации любой формулы Fi в L с соответствующим весом wi.
Распределение вероятностей возможного мира (БЗ) марковской сети ML,Сопределяется: , где ni(x) является количеством верных интерпретаций (truegrounding) формулы Fiв x, x{i} есть состояние (state) атомов, появляющихся в Fi и .
Вывод в нее часто требует и вероятных, и детерминированных методов. Даны некоторые факты (evidences), требуется найти значения запрошенных предикатов для максимизации их частного распределения. Структура сети обычно бывает сложным, и в этом случае точный вывод является трудноразрешимой проблемой. Поэтому метод приблизительного рассуждения как MCMC сэмплинг (Markovcha in Monte Carlo sampling) станет хорошим выбором. В связи с тем, что для решения нашей задачи мы используем и вероятностные правила, и строгие правила (deterministic dependencies), семплирование по Гиббсу([2])не эффективно обращается с детерминированными зависимостями, поэтому мы используем моделирование темперирования ([2]) для вывода.
2. Модель извлечения временной информации в логико-марковских сетях
В данной работе мы рассмотрим проблему определения временных отношений между событиями, описанных в документе. Извлечение временных отношений заключается в определении взаимосвязей между событиями или между событиями и моментами времени [1]. В процессе вывода временных отношений возникает проблема, связанная с тем, что временная информация выражается в тексте на естественном языке явным или неявным образом. В любом случае остается неоспоримым тот факт, что события всегда связаны друг с другом или с моментами времени. Как было написано в работе [1], на построение временного порядка влияет множество различных грамматических категорий, например видо-временные формы глаголов, наречия времени, грамматические единицы (краткое прилагательное, отглагольное имя существительное). Кроме того событиячасто связываются временными союзами. Это временные предлоги, наречия, местоимения и частицы.
3.1 Предикаты
В нашей модели, мы определяем различные предикаты для охвата этих появления.
Для каждого события, определены предикаты, описывающие разные его грамматические характеристики: Tense(e,!t), Perfect(e,!p), Aspect(e,!a), Class(e,!c), Modal (e,!m), Polarity(e,!p), Verb Class(e,!v), где e - событие, знак «!» означает, что каждое событие е принадлежит только одному классу
Таблица 2. Предикаты для описания события
Мы так же используем предикат HASVERB(e, w) для указания, что событие е имеет слово w.
Для описания случая, когда специальные слова (союзы) присутствуют между событиями (мы, предложено, считаем момент времени как специальное событие), мы приводим предикат Have Connected Word (e1,e2, c), где е1, е2 - события, с есть союзное слово, например, перед тем как, после, во время, с тех пор, когда, пока, как, в то время как,…
Два события, имеющие одинаковый объект, выражаются предикатом Have Same Object (e1,e2).
Для события, которые описываются в одном предложении, мы выражаем их предикатом In Same Sentence (e1,e2).
Главным предикатом запроса является In Group (e1,e2,g), означающий, что временное отношение между e1,e2 принадлежит группе g. Приняв классификацию временных отношений в работе [1], мы определяем девять групп временных отношений: {AFTER, BEFORE, DURING, INCLUDES, OVERLAPS, IS_OVERLAPPED, EQUALS, BEGIN, END}
В нашей работе, мы рассмотрели два варианта задания предиката запроса: In Group (e1,e2,!g) и In Group (e1,e2, g). Первый вариант строго означает, что временное отношение между e1,e2 принадлежит только одной из девяти возможных групп, в то время второй разрешает мультигрупового случая.
3.2 Формула
Мы построили правила, чтобы описать нашу гипотезу о влиянии различных грамматических аспектов на временные отношения.
Для представления связи между видо-временной формой глаголов и временным отношением двух событий, мы предлагаем следующее правило: Tense(e1, t1) ^ Tense(e2, t2) ^ Perfect(e1, p1) ^ Perfect(e2, p2) => INGROUP(e1,e2,g)
Для описания влияния аспектуального класса, модальности и полярности на временное отношение двух событий, мы определяем следующее правило: Aspect (e1, a1) ^ Aspect (e2, a2) ^ Modal(e1, m1) ^ Modal(e2, m2) ^ Polarity(e1, p1) ^ Polarity (e2, p2) => In Group (e1,e2,g)
Когда между событиями существуют союзные слова, тогда с большой вероятностью эти слова играют важную роль в построении временного порядка. Для этого случая мы используем простое правило:
Have Connected Word (e1,e2, c) =>INGROUP (e1,e2,g)
Иногда сами имени события, т.е. слова, описывающие события, сильно влияют на их временной порядок. Посмотрим пример: «Я упал на полу. Кто-то меня толкнул»
В этом примере, между событиями нет ни какого связного слова. Но, исходя из знания о познавательном мире, мы знаем, что падение всегда происходит после толкования, и сможем сделать правильное заключение об их временном отношении. Для описания этого появления мы определяем правило: HASVERB(e1, w1) ^ HASVERB(e2, w2) =>INGROUP(e1,e2,g)
Детерминированные правила
MLNS допускает написать строгие правила, и этим правилам будут присваиваться весы с бесконечным значением. Это можно рассмотреть как обычные продукционные правила, и они всегда выполняются. Мы построили 5 групп экспертных правил для разных случаев появления событий.
Транзитные правила
В других работах до нашей работы, транзитные правила используются для повышения количества найденных временных отношений. Но во всех этих работах, это происходит как пост-процесс только после процесса классификации [6]. Это приводит к не согласованности в базе знания. В работе [7] авторы предлагали метод, гарантирующий глобальную согласованность в базе знания с помощью линейного целочисленного программирования, но ограничены только два возможных отношений. С помощью MLNS мы интегрируем эти правила в процессе вывода, следовательно, гарантируются согласованность и эффективность при выводе.
Некоторые транзитные правила являются строгими, некоторые выполняются с большой вероятностью, поэтому имеет вес с большим значением, а другие являются «мягкими» правилами, например: INGROUP(e1,e2, BEFORE) ^ INGROUP(e2,e3, BEFORE) => INGROUP(e1,e3, BEFORE)
4. Интеграция меры близости в логико-марковских сетях
Хотя MLNS является очень мощным аппаратом для обучения и вывода, но она ограничена тем, что все означенные формулы (ground formula) одной формулы имеют одинаковый вес. Тем более в СТАНДАРТНОЙMLNS не рассматривается возможность использования числовых термов. Числовые термы пригодны в случае, когда мы хотим добавить некоторые числовые оценки для объектов обучения. В решении нашей задачи, мы вводим темпоральную меру близости для двух пар событий и используем ее для повышения адекватности модели и избегаем от проблемы переобучения.
В основе семантико-синтаксическая меры сходства лежит использование следующих двух техник: синтаксическая структура предложения и мера семантической близости слов на основе тезауруса Russian Word Net [5].
С помощью синтаксического анализа мы построим дерево синтаксического разбора. На основе полученных деревьев, мы вычисляем меру семантической близости для соответственных пар слов на 2-х деревьях. Полученная семантико-синтаксическая мера нормируется в интервале [0,1].
Интеграция меры близости в MLNS
Интеграция обоснована на такой идее, что два объекта близко друг к другу высоковероятно находятся в одной группе. Для введения меры близости мы будем расширять СТАНДАРТНУЮMLNS для поддержки числовых термов и определим новый предикат Similar(e1,e2,e3,e4).
Similar(e1,e2,e3,e4) вычисляет меру близости между 2-мя парами событий (e1,e2) и (e3,e4).
Обучение и вывод в MLNS реализуются посредством максимизации логарифмической функции правдоподобия, являющейся маргинальной вероятностью запрошенных предикатов при некоторых заданных свидетельствах.
Для стандартной MLNS, при постановке дискриминационного обучения условная функция правдоподобия вычисляется по формуле:
где Fy есть множество формул, содержащих, по крайней мере, один атом запроса (queryatoms) ni(x,y) является количеством верных означений (truegrounding) формулы Fiв (x,y) и Zx является коэффициентом нормализации.
Для обеспечения ограничения о соседних объектах мы составим целевую функцию:
где wявляется весом формулы (1)
sijявляется весом близости между 2-мя объектами
Эта модель позволяет включить глобальную согласованности объектов на определенной мере близости.
Сумма S вычисляется во время вывода на модели с помощью метода MCMC [2].
Вывод
В работе предложен новый подход решения задаче извлечения временной информации с помощью аппарата логико-марковской сети. Интеграция приорных знаний всегда является большой проблемой в обработке естественного языка. Логико-марковской сеть дает естественный способ решения с поддержкой строгих правил и «мягких» правил, за счет которых смягчит условие согласованности базы знания. Однако в логико-марковской сети никак нельзя влиять на процессе выбора обучаемой выборки, потому что вес для всех означенных формул (groundingformula) одной формулы зафиксирован. Предложенный в данной работе метод использования меры близости дает возможность регулировать целевую функцию и поэтому влиять на определение значимости обучаемой выборки.
Список литературы
1. Заболеева-Зотова А.В., Фамхынг Д.К., Захаров С.С. Гибридный подход к обработке временной информации в тексте на русском языке//Труды 11-ой национальной конференции по искусственному интеллекту с международным участием (Дубна, 28 сентября - 3 октября 2008 г.). - М.: URSS, 2008. - С.228-235.
2. Richardson M., Domingos P. Markov Logic Networks// Machine Learning. - 2006. - Vol.62. - P.107-136.