Извлечение информации и формальные грамматики

Все описанное ниже основано на домыслах и догадках, если я в чем-то не прав – буду рад комментариям и поправкам.

Извлечение информации (Information Extraction или коротко - IE) – это задача обработки текста, цель которой - перевод тех фактов, что записаны естественным языком в структурированную форму.

Мотивейшн

Самое главное в начале любого дела – это разобраться зачем это все нужно, не даром любой зарубежный курс начинается с Motivation, попробуем разобраться и мы.

Рассмотрим пример - у нас в БД есть набор текстов, содержащих какую-то информацию о фильмах, но программно с этой информацией мы ничего сделать не можем, строки "Фильм Титаник снят Кэмероном" для машины не достаточно чтобы ответить на вопрос "кто режиссер фильма Титаник?", для этого нам нужна структурированная табличка:

Фильм Режиссер Дата выхода
Титаник Джеймс Кэмерон 1997 год
Интерстеллар Кристофер Нолан 2014 год

Теперь уже можно сделать SQL запрос и получить нормальный ответ. А вот чтобы сформировать такую табличку нам и нужны методы IE.

Если копнуть глубже, то окажется что для извлечения фактов нам надо решить несколько подзадач – найти слова, которые являются именоваными сущностями (Named Entity Detection) и примерно разобраться что именно это за сущности (Named Entity Recognition, коротко - NER). После этапа NER мы получаем выделенные сущности с проставленными им тегами - PERSON, LOCATION, ORGANIZATION и т.д. Естественно, никто не мешает вам использовать для вашей задачи любые другие теги, но крупные соревнования-сравнения различных систем NER проводятся именно по этим тегам (например RuFactEval). Опционально можно ещё заняться Entity Linking, но об этом как-нибудь потом. Далее, после NER, хорошо бы провести разрешение кореференции и собственно извлечь связи между объектами (Relation Extraction), эти связи и будут фактами, которые мы будем сохранять в нашу табличку.

Подходы к извлечению информации

Вообще, готовых инструментов уже придумано полно, но, как обычно, для русского языка подходят далеко не все, а свободнодоступных и production-ready решений для русского практически и нет. Кому интересно посмотреть на длинные списки - велком сюда или сюда.

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

А вот первый пункт рассмотреть стоит – имея какую-нибудь узкую задачу (такую как извлечение минимальной информации о фильме), голову и немного времени вполне возможно сделать систему, которая успешно будет обрабатывать большую часть подобных текстов.

Самый простой и известный вид правил - это регексы, которые позволяют извлекать наборы символов удовлетворяющие некоторому правилу. Они прекрасно подходят для чего-то с фиксированой структурой, например, дат (да, дата это тоже сущность), но плохо подходят для сложных и длинных конструкций естественного языка. Тем не менее регексы – это неотъемлемая часть любой системы извлечения информации, где они используются хотя бы для предобработки текстов.

Второй элемент - словари, да это не правила, но это обязательный элемент любой системы, построенной на правилах. Словари хорошо подходят для извлечения чего-либо, что имеет небольшую вариабельность - например список стран довольно постоянен и подглядывая в этот список можно с хорошей точностью понимать что это страна (но не 100%, например Украина, Россия - это страны, но ещё и гостиницы). В задаче извлечения информации о фильмах словарь подойдет чтобы хранить, например, жанры - их не много, но не подойдет чтобы хранить режиссеров.

Словарями и регексами уже можно собрать какую-нибудь простенькую систему IE, но качество и сложность шаблонов на регексах будет не очень (мягко говоря) оптимальным. Развивать и поддерживать такую систему будет тяжело.

Попробуем найти что-то более адекватное задаче.

(G)LR-парсер

И более адекватная форма шаблонов, для извлечения фактов - это формальные грамматики.

Сделаем серьезное лицо и пробежимся по основам и определениям.

Формальная грамматика - набор правил, которые описывают некоторые допустимые выражения в рамках какого-либо языка (языка описания фильма, например) за подробностями в вики. Рассмотрим простой пример - язык математических формул: (2*3)+(3*4). Попробуем описать правила такого языка:

Валидное выражение такого языка должно быть формулой, формула может быть композицией других формул, соединенных знаком арифметической операции – Формула => Формула Знак Формула, тогда Знак => + | - | * | \. Но что является самой простой формулой, которая не является комбинацией других? Число! Формула => Число. А число – это уже либо просто цифра, либо цифра соединенная с другим числом - Число => Цифра | Число Цифра. Цифра – символ из некоторого набора Цифра => 0 | ... | 9. И не забудем про скобки - любая формула может быть взята в скобки - Формула => (Формула). И в итоге получился следующий набор правил:

1) ФОРМУЛА => ФОРМУЛА ЗНАК ФОРМУЛА
2) ФОРМУЛА => ЧИСЛО
3) ЧИСЛО => ЦИФРА | ЧИСЛО ЦИФРА
4) ФОРМУЛА => (ФОРМУЛА)
5) ЦИФРА => 0 | … | 9
6) ЗНАК => + | - | * | /

В грамматиках, те символы, которые не раскладываются дальше, называются терминалы (в примере это 0,...,9,+,-,*,\,(,)), а остальные - нетерминалы (это все ключевые слова, которые стоят в левой части).

Для разбора строки в соответствии с заданной грамматикой используется LR-алгоритм. Подробно (и довольно понятно) принцип его работы описан, например, тут.

Самое главное, что нам нужно знать - посимвольно считываем строку слева на право, и складываем в стек считанные символы, содержимое стека пытаемся свернуть по какому-нибудь из правил, если ничего не подходит - сдвигаем ещё один символ и пытаемся снова.

Например - строка 2+3, считываем 2 и применяем правила 5, 3, 2, так что 2 сворачивается в ФОРМУЛА. Дальше +, в стеке теперь ФОРМУЛА + сворачиваем по 6 - ФОРМУЛА ЗНАК. Считываем последний символ, теперь в стеке ФОРМУЛА ЗНАК 3, применяем правила и получаем ФОРМУЛА ЗНАК ФОРМУЛА, и делаем последнюю свертку (правило 1) до ФОРМУЛА.

Вооружившись новыми знаниями, можно описать какую-нибудь простую грамматику.

Название => 'фильм' <Слово с большой буквы>
Режиссер => 'снят' <Существительное с большой буквы в творительном падеже>

Такая грамматика уже сможет распарсить строку Фильм Титаник снят Кэмероном, однако она очень специфична и ее надо развивать и делать более обобщенной.

Проблема только в том, что естественному языку свойственны разнообразие и неоднозначность, а это может сыграть злую шутку, если вы начнете расширять эту грамматику другими шаблонами. При парсинге LR-алгоритмом У вас будут возникать случаи, при которых, после очередного сдвига можно применить одновременно разные правила, и если пойти не верным путем мы уткнемся в тупик. Чтобы избавится от этих проблем связанных с неоднозначностью, японцем Масару Томита была предложена реализация LR-парсера с приставкой GeneralizedGLR-парсер. Главная особенность в том, что встречая какую-то неоднозначную конструкцию, к которой подходит несколько правил, мы разветвляем стек и начинаем обрабатывать все варианты параллельно, если какой-то вариант заводит в тупик - отбрасываем его.

Писать с нуля свой GLR-парсер занятие не очень полезное, особенно, если учесть, что сам парсер далеко не единственный элемент системы – не менее важны токенизатор и модуль морфологического анализа. Для русского такой парсер со всей обвязкой уже есть и называется он Томита-парсер. В следующий раз мы познакомимся с ним и научимся извлекать факты с его помощью.

Продолжение в следующем посте


comments powered by HyperComments
Яндекс.Метрика