NERC Обзор методов поиска и классификации именованных сущностей Сильвестров Алексей 9 марта 2010 г

Введение Методы машинного обучения Пространство признаков Оценивание NERC систем Nymble

Введение NERC – подзадача Information Extraction. Задача NERC системы - распознать такие информационные единицы, как имена людей, названия организаций и мест, выражения с цифрами. Термин Named Entity появился в 1996 году на muc-6. Первые системы были основаны на созданных вручную правилах и эвристиках. Большинство современных систем основано на методах машинного обучения

Языковые факторы: большое количество работ было посвящено изучению английского языка. Такое же или большее количество адресовано языковой независимости и мултиязыковым задачам. европейские языки, хинди, русский, арабский, корейский

Жанровый фактор и фактор тематики Фактор жанра текста и тематики в литературе почти не рассматривается. Всего несколько исследований посвящены разным жанрам и тематикам. Причина- приспособление системы к новым жанрам и тематикам проблематично- происходит падение производительности на 20%-40%.

Фактор типа сущности Named в Named Entity говорит о том, что задача ограничена поиском сущностей, на которые указывают строгие указатели, в частности имена собственные. enamex:"persons","locations","organizations timex: date time, etc marginal: project name, adress,film В нескольких недавних работах кол-во типов было огромно - open domain

Методы машинного обучения :SL Обучение с учителем: HMM, support vector machines, CRF, decision trees. Baseline алгоритм: поиск NE, присутствующих в тренировочном корпусе и разметка – любой другой метод обязан быть не хуже данного. Недостаток этих методов - большой размер тренировочного корпуса

Методы машинного обучения :SSL Обучение с частичным привлечением учителя: главная техника - bootstrapping - начальная загрузка. Пример: предложения The city like New York, My name is John, Улица ак. Варги будут приведены к виду The city like X,My name is Y, Улица ак. Z, так же будут найдены предложения содержащие эти сущности и т.д.

Методы машинного обучения :SSL mutual bootstrapping(1999): за один ход увеличить набор entities и набор контекстов, для чего дается богатый набор NE. Техника была успешно использована для поиска синонимов и гипонимов. Но в случае «шума» производительность резко падает.

Методы машинного обучения:UL Обучение без учителя: поиск NE в тексте, кластеризованном по признакам Другие подходы: лексические ресурсы и статистический анализ уже размеченного корпуса. Предоставляется доступ к внешним ресурсам

Пространство признаков Пространство признаков: vector(bool,w_len,low_case_ver) The president of Apple eats an apple.,,,,,,, Остается ввести правила распознавания и классификации

Признаки слов: На уровне слов рассматривают: слово прописное/строчное, знаки препинания, морфология, части речи, числовое значение. Функции над словами: шаблонизация, сокращение до корня. Поиск имен нарицательных в словаре позволяет не обращать внимание на слова, написанные с большой буквы, не являющиеся NE.

Признаки слов: Поиск слов, типичных для названия организации: inc., Bank", "General Приемы, для fuzzy-matched слов: например, Frederick и Frederik можно считать одним словом, т.к. edit-distance между ними - 1 буква

Признаки корпуса и документов: Признаки документа относятся к структуре документа и его содержанию: multiple casing, coreference Признаки корпуса также основаны на мета-информации о нем и статистике.

Признаки корпуса и документов: множественные вхождения - Одна сущность с большой и малой буквы - Анафора, перекрестные ссылки синтаксис - перечисление - Позиция в предложении, абзаце, документе Мета- информация -Uri, заголовок , XML section, - списки, таблицы, графики Корпусная статистика - Частота появления слов и фраз - Co-occurrences - Multiword unit permanency

Оценивание NERC систем Результат работы системы сравнивают с результатом работы лингвиста. MUC,IREX,CONNL

MUC оценки TYPE засчитывается корректным, если тип сущности был определен правильно, независимо от границ. TEXT засчитывается, если границы сущности определены верно независимо от типа.

MUC оценки F-мера: COR-кол-во правильно определенных NE ACT- кол-во определенных NE POS- сколько NE в тексте на самом деле

IREX and CONLL Обе конференции используют простые правила: считается F(pre,recall) Precision - процент правильно определенных NE Recall - процент определенных NE

Nymble NERC система основанная на HMM near-human производительность 90% Разработана в 1999г.

Теория Изначальная идея: предполагается, что текст проходит через шумный канал, где он попутно размечается NE. Цель скрытой марковской модели: смоделировать этот процесс.

Теория Иначе говоря, найти наиболее вероятную последовательность name-classes(NC) соответствующую последовательности слов(W). Теорема Байеса: Откуда видно, что нужно максимизировать

Обзор модели:

На концептуальном уровне, у нас есть HMM с 8 внутренними и 2 специальными состояниями. Каждое NC состояние обладает собственным набором состояний, с соответствующими вероятностями (биграммы), мощности |V| (размер словаря).

Генерация слов и NC проходит в три шага: 1.выбор NC,основанный на типе предыдущего NC и предшествующем слове 2.Генерация первого слова внутри NC, зависящая от текущего и предыдущего NC. 3.Генерация всех последующих слов внутри NC: Джон Ро́нальд Руэл То́лкин Обзор модели:

Слова и их особенности:

Реализация: Генерация первого слова в NC Последующие слова Последнее слово

Реализация: Подсчет вероятностей Где с() - число произошедших событий

Реализация: словарь системы пополняется в процессе тренировки. Очевидно, что система будет знать всё о словах, для которых построены биграммы вероятностей. что делать, если: 1.текущее слово неизвестно 2.предыдущее неизвестно 3.оба слова неизвестны

Реализация: лучше всего тренировать систему на незнакомых словах отдельно, для этого используется упрощенная модель - unknown word-model.

Реализация: порядок: 1.на первой половине тренировочного файла тренируем систему в обычном режиме -> получаем набор биграмм_1 2.на второй половине тренировочного файла обучаем unknown word-model -> набор биграмм_2 3.конкатенируем набор биграмм_2 и набор биграмм_1

Реализация: при декодировании : 1.если одно из двух или оба слова незнакомы, то используются вероятности для unknown word model 2.Иначе – вероятности для нормальной модели

Упрощенные модели В случае незнакомых слов используются упрощенные формулы:

Упрощенные модели При подсчете P(X|Y) считают вес для прямых расчетов и для упрощенной модели.

Декодирование Задача системы- максимизировать Иначе- наиболее правильным образом декодировать зашумленный текст. Благодаря алгоритму декодирования Витерби предложение с m словами может быть декодировано за время O(m)

Имплементация и результаты Система написана на C++ При должном количестве RAM обучается за 5 минут и обрабатывает 6мб/час (1999г)

Имплементация и результаты При оценке использовалась f-мера:

Имплементация и результаты

Обучающий файл содержит слов на английском. В ходе эксперимента обучающий материал уменьшали в 2,4,8 раз.