Лексический анализ от шаблонов

Даниил Скатов
26 февраля 2010 г.
ООО «Диктум»
г. Нижний Новгород

Объекты…
Даниил Скатов
26 февраля 2010 г.
ООО «Диктум»
г. Нижний Новгород

Объекты…
Даниил Скатов
ООО «Диктум»
г. Нижний Новгород
Персона
Имя
Фамилия
Отчество
"Даниил"
"Скатов"
Ø
Организация
Название
"Диктум"
Тип
"ООО"
Населенный пункт
Имя
Нижний Новгород
Тип
Город
День
Месяц
Год
26
02
2010
26 февраля 2010 г.
Дата

Объекты…
Даниил Скатов
ООО «Диктум»
г. Нижний Новгород
Персона
Имя
Фамилия
Отчество
"Даниил"
"Скатов"
Ø
Организация
Название
"Диктум"
Тип
"ООО"
Населенный пункт
Имя
Нижний Новгород
Тип
Город
День
Месяц
Год
26
02
2010
26 февраля 2010 г.
Дата
Скатов Даниил
; Скатов Д.
Даниил Сергеевич Скатов; Скатов Д.С.
Даниил Сергеевич; Скатов
Общество с огр. отв-ю «Диктум»
компания «Диктум»
; Dictum Ltd
Диктум
Н. Новгород;
НН; столица Поволжья; город Горький
Горький; НН; Нижний
г. Н. Новгород
26.02.2010
; Feb 26, 2010
Двадцать шестое февраля
Последняя пятница февраля 2010 года

Объекты, факты …
Сотрудник ( )
посетил конференцию
«Поисковые технологии»
компании «Диктум»
26.02.2010
г. Н. Новгород
Скатов Даниил

Должность
Объекты, факты …
Сотрудник ( )
посетил конференцию
«Поисковые технологии»
компании «Диктум»
26.02.2010
г. Н. Новгород
Скатов Даниил
Даты: 20/03/06, 7 февраля 2007 г., 1991-2006 гг.
Персоны: Петров И.С., Иван Петров, Иван Сергеевич, Петров И.
Адреса Интернет и e-mail: http://www.dictum.ru
Географические адреса: Россия, г. Н.Новгород, пр-т Гагарина, 23, корп. 7
Названия организаций: Университет им. Н.И.Лобачевского, КБ «Квазар», Школа № 7
Спортивные события: Зимняя олимпиада, Кубок УЕФА, Чемпионат мира по хоккею
Числа прописью: две тысячи восемьсот единиц техники
Результаты измерений: 8 кг., не более 50 км/ч
Денежные единицы: 2 000 р., 80 454,2 USD
Порядковые числительные: 1-ый, 18-ого
Номера телефонов: [phone], [phone]
Номера кредитных карт, ИНН
…
Факты —
отношения
между объектами
Факт посещения

Объекты, факты и не только
Фразы-определения авторских терминов, их синонимов и связанных атрибутов: «Лексический анализ — это …»
Нормализация слабоструктурированных источников данных: автоматизированное формирование и коррекция номенклатурных списков (имущества, оборудования и т.д.): «Квартира 2-х комнатная 80 кв. м. …»
Прошивка законодательства: извлечение инструкций (связанных с обновлением текстов во времени) для их последующего применения: «Часть первую статьи 41 дополнить словами "или его заместителем"»
Графематический анализ: выявление в тексте простых лексических конструкций (ФИО с инициалами, электронные адреса, имена файлов), а также предложений, абзацев, заголовков, примечаний
Выявление составных слов — напр.: для того чтобы

Лексический анализ
Задача: выявить в неразмеченном ЕЯ-тексте лексические конструкции — цепочки слов входного текста (возможно, разрывные), каждая из которых снабжается набором данных определенной структуры:
имя класса, которому принадлежит конструкция (Дата);
нормальная форма конструкции, которая состоит из нормализованного текстового представления (удобного для прочтения человеком) и набора именованных полей с присвоенными значениями
(День = 26, Месяц = 2, Год = 2010)
Базовый механизм для выявления объектов (именованные сущности, как правило, являются непрерывными конструкциями)
Вспомогательный механизм для выявления фактов (выявление утверждений — разрывных конструкций: «Василий Петров, мечтая о научной карьере, долгое время успешно трудился в НИИ ЧАВО», м. быть установление кореференции объектов, но не логический вывод фактов)
Вспомогательный механизм для деления текста на слова (поиск составных слов типа союзов, но не полноценная символьная токенизация — японский, арабский, «первыйвторой»)
Это лексический анализ естественного языка (LANL):

Лексический анализ

Принцип наследования
Председатель совета директоров ОАО «Газпром нефть» А. Миллер
9 июля 2008 г. посетил г. Нижний Новгород с рабочим визитом

Принцип наследования
Председатель совета директоров ОАО «Газпром нефть» А. Миллер
9 июля 2008 г. посетил г. Нижний Новгород с рабочим визитом
Geography
Date
Person
Organization

Принцип наследования
Председатель совета директоров ОАО «Газпром нефть» А. Миллер
9 июля 2008 г. посетил г. Нижний Новгород с рабочим визитом
Geography
Date
Job
Person
Organization

Принцип наследования
Председатель совета директоров ОАО «Газпром нефть» А. Миллер
9 июля 2008 г. посетил г. Нижний Новгород с рабочим визитом
Geography
Date
Job
Person
Organization
Attendance

Регулярные выражения as is?
Председатель совета директоров ОАО «Газпром нефть» А. Миллер
9 июля 2008 г. посетил г. Нижний Новгород с рабочим визитом
Geography
Date
Job
Person
Organization
Attendance
Отсутствие механизмов повторного использования уже написанных выражений (наследования): можно лишь подставить одно выражение в другое

Регулярные выражения as is?
Отсутствие механизмов повторного использования уже написанных выражений (наследования): можно лишь подставить одно выражение в другое
26/02/2010;
[email protected]
; 85 кг.
Вчера заместителю управляющего делами президента Российской Федерации Павлу Бородину …
Хорошо, но…
?!

Регулярные выражения as is?
Отсутствие механизмов повторного использования уже написанных выражений (наследования): можно лишь подставить одно выражение в другое
Отсутствие специфических возможностей: проверка вхождения слов и их цепочек в заданные множества, работа с грамматическими значениями слова…
26/02/2010;
[email protected]
; 85 кг.
Вчера заместителю управляющего делами президента Российской Федерации Павлу Бородину …
Хорошо, но…
?!

Регулярные выражения as is?
Отсутствие механизмов повторного использования уже написанных выражений (наследования): можно лишь подставить одно выражение в другое
Отсутствие специфических возможностей: проверка вхождения слов и их цепочек в заданные множества, работа с грамматическими значениями слова…
Быстрый рост сложности выражений (для их составителя)
Нетривиальная обработка разделителей (переносы строк, пробелы) и их сочетаний
Увеличение времени анализа с ростом количества описаний: каждое описание (регулярное выражение) приходится применять к тексту отдельно
Машинное обучение? ? Об этом позже

История
DSTL = Шаблоны + Наследование + Предикаты

DSTL: простой пример

Наследование

Наследование

Работа с морфологией
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
Александра
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
{«Александр», Сущ, Имя, Муж, Род, Ед}
{«Александр», Сущ, Имя, Муж, Вин, Ед}
{«Александра», Сущ, Имя, Жен, Им, Ед}
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
Александра
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
2. Двуместные функции: (1) из первого и второго слова выбираются подмножества S1 и S2 грамматических форм с заданными характеристиками, (2) проверяется, существует ли пара (v1,v2) такая, что v1∈S1, v2∈S2, и обе формы имеют требуемый набор характеристик с попарно совпадающими значениями
AreConcordant (Case_, Number_,
V, PartOfSpeech_, Noun_, Gender_, Masc_,
W, PartOfSpeech_, Noun_, Gender_, Masc_)
W
{«Александр», Сущ, Имя, Муж, Род, Ед}
{«Александр», Сущ, Имя, Муж, Вин, Ед}
{«Александра», Сущ, Имя, Жен, Им, Ед}
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
Александра
{«Александр», Сущ, Имя, Муж, Род, Ед}
{«Александр», Сущ, Имя, Муж, Вин, Ед}
{«Александра», Сущ, Имя, Жен, Им, Ед}
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
2. Двуместные функции: (1) из первого и второго слова выбираются подмножества S1 и S2 грамматических форм с заданными характеристиками, (2) проверяется, существует ли пара (v1,v2) такая, что v1∈S1, v2∈S2, и обе формы имеют требуемый набор характеристик с попарно совпадающими значениями
AreConcordant (Case_, Number_,
V, PartOfSpeech_, Noun_, Gender_, Masc_,
W, PartOfSpeech_, Noun_, Gender_, Masc_)
W
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Работа с морфологией
Александра
{«Александр», Сущ, Имя, Муж, Род, Ед}
{«Александр», Сущ, Имя, Муж, Вин, Ед}
{«Александра», Сущ, Имя, Жен, Им, Ед}
1. Одноместные функции: проверка существования
грамматической формы с заданными характеристиками
HasGrammarForm (V, PartOfSpeech_, Noun_, Gender_, Masc_)
2. Двуместные функции: (1) из первого и второго слова выбираются подмножества S1 и S2 грамматических форм с заданными характеристиками, (2) проверяется, существует ли пара (v1,v2) такая, что v1∈S1, v2∈S2, и обе формы имеют требуемый набор характеристик с попарно совпадающими значениями
AreConcordant (Case_, Number_,
V, PartOfSpeech_, Noun_, Gender_, Masc_,
W, PartOfSpeech_, Noun_, Gender_, Masc_)
W
V
механика
{«механик», Сущ, Од, Муж, Род, Ед}
{«механик», Сущ, Од, Муж, Вин, Ед}
{«механика», Сущ, Неодуш, Жен, Им, Ед}

Согласование и нормальная форма

Неоднозначность и конфликты
SN {
T := SName;
C := IsCapitalized (SName)
& Length (SName) >= 2;
A := { CW := 1 - (IsVoc (SName)
& !IsPOS (SName, Surname_));};
};
NP {
T := N \. P \.;
C := Length (N) = 1
& Length (P) = 1;
A := { CW := 1; };
};
Person_1 { T := [SN][NP]; A := {CW := NP.CW + SN.CW; };};
Person_2 { T := [NP][SN]; A := {CW := NP.CW + SN.CW + 0.5;};};
Пушкин А.С. Поэмы
Person_1
Person_2
CW=2
CW=1.5
В г. Сочи В.В. Путин
Person_2
CW=2.5
Person_1
CW=1.5

Неоднозначность и конфликты

Сравнение языков

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Механизм анализа
Задача: найти все вхождения образцов из в

Проблемы и решения
Правила, составляемые экспертом, дают лучший результат в сравнении с результатом применения машинного обучения (обучение с учителем, распознавание образов …)
Проблема: высокая трудоемкость работы эксперта
Машинное обучение:
Хорошо применимо для распознавания узких классов (напр., в Named Entities Recognition — имена людей — популярно у зарубежных исследователей)
Позволяет распознать текстовый фрагмент и приписать класс, но не заполнить поля или отразить структуру наследования (следствие — трудность разрешения конфликтов)
Обучение — возможно, не менее трудоемко, чем составление правил, и результат иногда недетерминирован для учителя
Неполнота обучающей выборки
Возможное решение: возьмем лучшее из обоих подходов

Проблемы и решения
Механизм
анализа
Результат
анализа
Обучающая
выборка
Текст
Механизм
анализа
Результат
анализа
Правила
Текст
Машинное обучение
Система правил

Проблемы и решения
Механизм
анализа
Результат
анализа
Правила
Текст
Набор
атрибутов
Корпус
Механизм анализа не меняется
Эксперт формирует набор атрибутов, система
выявляет в текстах корпуса устойчивые сочетания

Использование для поиска
Запрос: «февраль 2010»
Вхождения
образца из
запроса
в текст

Использование для поиска
Проблема — сравнение объектов сложнее сравнения слов:
Частичное совпадение («2 февраля 2010» и «февраль 2010»)
Частичное несовпадение («февраль 2010» и «февраль 2009»)
«Семантическая» близость («3 февраля 2010» и «4 февраля 2010» ближе, чем «3 февраля 2010» и «3 февраля 2009»)
Пусть вместе с базой правил определена функция d(x,y):
d(x,y) = 0 для одинаковых объектов
d(x,y) = ∞ для объектов разных классов
Частичное совпадение «лучше» частичного несовпадения
Решение — степень схожести вместо булевского равенства: