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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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