Сравнение разных подходов к поиску именованных сущностей на примере

Мы в проекте RedForester заинтересованы в использовании системы поиска именованных сущностей для улучшения навигации пользователей по их знаниям, эта статья о нашем исследовании в этом направлении.

В статье мы сравним два инструмента: Natasha[i] и DeepPavlov / ner_rus[l], реализующих различные подходы решения задачи поиска именованных сущностей (на данный момент только для именованных сущностей типа person).

Поиск именованных сущностей

Поиск именованных сущностей (Named Entity Recognition — NER) — частная задача  извлечения информации, состоит в поиске именованных сущностей в слабоструктурированных текстах (как правило на естественных языках).

Именованная сущность — имя предмета или явления. Например: имена людей, организаций, событий, мест (географических и политических); дат и др.

Пример:

Методы решения задачи

Задачу NER решают различными методами:

  • Методы, основанные на грамматиках лингвистических моделей языков (grammar based), например правила для парсеров контекстно свободных грамматик.
  • Статистические модели (машинное обучение) — моделей много, но чаще всего при решении задачи используют CRF как в отдельности, так и в составе комплексных систем.

Подготовка текста

Первым этапом подготовки текста к обработке является токенизация — разделение входного текста на токены.

Токен — достаточно широкое понятие и зависит от задачи, в самом простом случае токенами могут быть любые последовательности символов, а разбиение происходит по пробельным (whitespace) символам.

Или же токенами могут быть только словоформы без пунктуации и других специальных символов. Токены могут быть дополнительно обработаны на предмет исключений — сложные фамилии, части речи после апострофа, фамильная приставка «де» — все это может быть составной частью одного токена.[a]

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

Широкая электрификация южных губерний даст мощный толчок подъёму сельского хозяйства
['Широкая', 'электрификация', 'южных', 'губерний', 'даст', 'мощный', 'толчок', 'подъёму', 'сельского', 'хозяйства']

После первичной токенизации принято убирать стоп слова[b] из последовательностей токенов.

Далее возможно потребуется провести лемматизацию или стемминг полученных токенов.

Лемматизация — процесс приведения словоформы к лемме — её нормальной (словарной) форме.

Стемминг — это процесс нахождения основы слова для заданного исходного слова. Основа слова не обязательно совпадает с морфологическим корнем слова.

Grammar based подходы

С помощью правил для парсеров контекстно-свободных грамматик парсеры (например Яндекс Томита[c], Ярги парсер[d] и другие) могут извлекать структурированную информацию, в частности именованные сущности.

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

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

Машинное обучение

Для решения задачи используются модели классического машинного обучения, работающие с последовательностями. К таким моделям относятся модели условных случайных полей (CRF), скрытая марковская модель (HMM), метод максимальной энтропии (ME) и пр.

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

Признаки для обучения

Стандартным набором признаков для обучения и использования вышеуказанных моделей являются:

  1. Начинается ли токен с заглавной буквы
  2. Разметка части речи (Part Of Speech tagging — POS тег)
  3. Длина токена (просто длина строки)
  4. Лемма токена
  5. Стемма токена
  6. Является ли токен числом
  7. Является ли токен акронимом (эвристика или словарь акронимов)
  8. Входит ли токен в словарь известных персон
  9. Входит ли токен в словарь известных географических наименований (газетир[e]).

Недостатки: требуют разработки и валидации алгоритмов извлечения признаков экспертом, часто разных для разных предметных областей.

Преимущества: стабильность работы, как правило не самая высокая вычислительная сложность обучения и использования (в силу простоты моделей).

Глубокое обучение

К наиболее современным методам решения задачи относится глубокое обучение[f].

Глубокое обучения (применительно к любой задаче) позволяет перенести процесс извлечения признаков из входных данных (необходимый этап экспертной работы в классическом машинном обучении) в саму модель, т.е. модель учится извлекать признаки самостоятельно.

Недостатки: высокая вычислительная сложность обучения и использования, отсюда и низкая скорость работы моделей. Глубокое обучение требует большого объема обучающей выборки (минимальная планка — десятки и сотни мегабайт текста).

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

Инструменты и модели

Инструменты для создания датасета

ipyannotate[g] — Плагин для jupyter notebook, позволяет аннотировать некоторую последовательность данных произвольными классами.

ipymarkup[h] — как и ipyannotate, плагин для jupyter notebook, позволяет подсвечивать и показывать теги в определенных позициях в текстах (спанах).

Тестируемые модели/системы

Natasha[i] — гибридный grammar based инструмент, работает поверх Ярги парсера[j], использует CRF POS теггер, а также обладает набором готовых правил (Яндекс не делится своими правилами для Томита парсера).

DeepPavlov[k] — библиотека для разработки чат ботов, вопросно ответных систем и других систем обработки естественного языка (NLP)

DeepPavlov / ner_rus[l] — обученная модель для поиска именованных сущностей, архитектурно представляет из себя Bi-LSTM + CRF.

Датасет

Для теста был составлен собственный датасет из комментариев карты нашей компании в RedForester.

Почему реальные данные?

Потому что большое количество датасетов слишком правильные — составлены из новостей, статей и прочей литературы, где принято писать правильно, например на датасете Persons-1000 ner_rus набирает 99.26%[m] по F1 score, наш датасет не такой 🙂

Датасет составлен путем отбора множества верно распознанных именованных сущностей с помощью моделей Natasha или ner_rus. В итоговый датасет были отобраны только те документы, именованные сущности в которых были распознаны с точностью до токена (по крайней мере я к этому стремился), а также равное количество документов гарантированно не содержащих именованных сущностей (итого 800 + 800 документов). Отбор производился в интерактивном режиме с помощью ipyannotate.

Проблемой, помимо монотонности и трудозатратности процесса, стало то, что ner_rus и Natasha отдают в качестве результата данные в совершенно разных форматах: Natasha отдает на выход для каждого документа оригинальный текст и список объектов, описывающих спаны с найденными сущностями, когда как модель ner_rus (как и другие модели NER из DeepPavlov) отдает для каждого документа список токенов и их разметку в IOB формате[n].

Чтобы провести прямое сравнение требовалось конвертировать результаты работы NamesExtractor в IOB разметку.

Сравнение Natasha и DeepPavlov / ner_rus

В таблице ниже представлены сравнительные оценки работы Natasha и модели ner_rus.

Сравнение моделей производилось оценкой точности поиска имен (класс persons) на собственном датасете, соответственно для Natasha использовался NamesExtractor, а результаты разметки DeepPavlov отфильтровывались.

Модель

F1

Precision

Recall

Natasha

82.96

95.61

73.26

DeepPavlov ner_rus

90.35

85.11

96.27

Короткая справка по F1, precision, recall[o]

Точность (precision) — отношение верно распознанных именованных сущностей к общему количеству найденных именованных сущностей.

Полнота (recall) — отношение найденных системой именованных сущностей, к общему количеству именованных сущностей.

F мера (F1 score) — представляет собой гармоническое среднее между точностью и полнотой:

Почему не используется обычная точность (accuracy)?

Простая оценка точности (TP + TN) / total даст 90+ процентов (в моем случае 99.4 и 99.6 для Natasha и ner_rus соответственно) просто потому что токенов не являющихся именованной сущностью в нормальных условиях гораздо больше.

Разбор ошибок Natasha

У Natasha.NamesExtractor есть проблемы с полнотой и стабильностью работы (видно по низкому показателю recall из таблицы выше). Ниже примеры текстов, в которых желтыми маркерами отмечены спаны с именованными сущностями типа person.

Результаты для оригинального текста:

Результат странный. Немного поможем POS теггеру Наташи, добавив в предложения глагол:

Неплохо, хотя-бы стабильный результат. Еще сильнее поможем, добавим наречие в начало предложений:

Отлично, а если теперь упростить? Уберем глагол:

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

Разбор ошибок DeepPavlov / ner_rus

Со стабильностью и полнотой работы у ner_rus все гораздо лучше, чем у Наташи. Но ner_rus «страдает» другой проблемой — большим количеством ложных срабатываний, короткий пример (зеленый спан — персона):

Эту проблему решить сложнее, чем проблему Natasha. Предполагаю, что только постобработкой по словарям заведомо неодушевленных слов?

Заключение

Как итог — Natasha и DeepPavlov / ner_rus работают без дополнительной подготовки на достаточном уровне, чтобы использовать их на практике. При этом есть возможность доработать каждый из подходов, чем я и займусь далее.

Ссылки

,

Версия RF от 24.12.18

Команда разработчиков Red Forester поздравляет всех пользователей с наступающим Новым Годом и представляет последнее в 2018 году обновление, в котором была переработана система прав и исправлены досадные ошибки предыдущего релиза.

Спасибо, что вы с нами, дальше — больше!

 

Нововведения и улучшения:

Система прав:

  • Переработана логика приглашения пользователя в карту:
    • Пригласить пользователя в карту возможно только через меню администратора.
    • Приглашать в карту может только администратор или владелец карты.
    • Теперь вы можете легко управлять видимостью узлов для пользователей, которых вы приглашаете в карту. Вам не придется назначать для каждого нового пользователя права на все требуемые узлы. Просто установите один раз в нужных новым пользователям узлах настройку, которая называется “При приглашении в карту, пользователи получают доступ” и находится в первой строчке таблицы прав доступа к узлу.
  • Изменено окно управления правами доступа к узлу:
    • Главное изменение: если пользователя нет в списке — доступа у пользователя к узлу нет.
    • Добавлена новая опция “При приглашении в карту, пользователи..”, которая определяет, будет ли автоматически добавлен пользователь в список доступа к узлу при приглашении его в карту. Если нет, то доступа к узлу у него не будет, пока владелец или админ вручную не добавят его к узлу. Данная опция доступна только владельцу карты.
    • Смена правила для пользователя во всей ветке теперь осуществляется с помощью выбора действия в столбике “Применить к ветке”.
    • Появилась возможность поиска по пользователям в окне изменения прав доступа к узлу.
    • Добавлена сортировка столбцов таблицы настроек доступа к узлу.
  • Изменение прав доступа теперь происходит в соответствии с иерархией ролей пользователей:
    • Владелец карты имеет полные права на изменение всех ролей у всех пользователей, удаление пользователей из карты и т.д.
    • Администраторы карты не могут назначать или отзывать админские права другим пользователям и менять другим админам правила доступа к узлу. Остальным пользователям администраторы могут менять и задавать доступ к узлам в полной мере, кроме удаления правил (но могут запретить доступ, что равносильно).
    • Пользователи с уровнем прав “Полный перечень действий над узлом”, не являющиеся администраторами, могут менять правила всем пользователям, ниже своего уровня доступа, но не могут дать им доступ “Полный перечень действий над узлом” или сделать админами.
    • Пользователи с правами доступа ниже “Полный перечень действий над узлом” и не являющиеся администраторами не имеют возможности менять правила доступа к узлам.
    • Пользователь с правами ниже “Редактирование узла и его связей” не может удалять узлы, даже созданные когда-то им самим.
  • Экспорт карты теперь отдельное правило, которое может задавать для пользователей-администраторов владелец карты.

Другие улучшения:

  • При удалении узла из любимых теперь всплывает нотификация.
  • Улучшение позиционирования всплывающих уведомлений при открытом боковом меню.
  • Комбобокс выбора карты теперь закрывается по нажатию вне его.
  • Изменять масштаб карты теперь можно по “Ctrl +” и “Ctrl -” — сделано переопределение стандартных браузерных клавиш.
  • Добавлен индикатор загрузки комментариев.
  • Пустые типовые поля теперь не переносятся в пользовательские при смене типа.
  • Не переносились типовые свойства в пользовательские, если изменить тип узла через контекстное меню.

Исправления:

  • При переходе к узлу по ссылке теперь не сбивается фокус экрана.
  • Исправлены ошибки в перемещении карты.
  • Окно редактора узла теперь не перекрывается боковой панелью.
  • Исправлено отображение линий, соединяющих узлы.
  • Комментарии, при указанной опции в расширенной вставке скопированного узла, теперь копируются корректно.
  • Исправлены различные ошибки с отображением ветки как карты.
  • Исправлена работа “тихой вставки” при вырезании узла.
  • Перемещение узлов с помощью alt+стрелки теперь происходит быстрее.
  • Последний редактирующий узел типа задача теперь не становится её постановщиком 🙂
  • Если вводить текст второго комментария сразу после отправки первого, то текст мог пропасть после публикации первого комментария — исправлено.
  • Исправлены случаи не отправки письма с активацией нового пользователя.
  • Исправлены проблемы с копированием/вставкой множества ссылок в пределах карты.
  • Свойство “логическое значение” теперь отображается, если в выборе стоит “нет”.
  • Исправлены зафиксированные случаи, когда не обновлялся счётчик комментариев.
,

Версия RF от 07.11.18

Нововведения:

  • Главная страница приложения полностью изменена и теперь представляет из себя меню выбора карт с сортировкой по созданным и расшаренным Вам. На плитке каждой карты информация об общем количестве узлов, количестве приглашённых в неё пользователей, метка публичности и email владельца, если Вы таковым не являетесь.
  • Любимые узлы” — долгожданное нововведение, позволяющее добавлять узлы в список, для быстрого перехода к ним из любого места данной или любой другой карты. Для этого необходимо пометить узел, нажав на иконку  и ссылка на него сохранится во вкладке “Любимые узлы” бокового меню. Вы сможете сразу увидеть результат, если нажмёте на уведомление при добавлении узла в “любимые”.
  • Отображение в стиле Kanban для менеджмента и ведения запущенных спринтов по методологии Agile. Применяется только к узлам типа “спринт” и отображает все вложенные в него узлы типа “Задача”, отсортированные по статусу. Вы можете менять статусы задач, перетаскивая их из одного столбика в другой. Чтобы вызвать данное отображение, необходимо выбрать пункт “Открыть канбан” в меню “Действия”  на узле.
    В будущих обновлениях мы реализуем фильтр по исполнителям и настройки отображения статусов.
    Работает в тестовом режиме. Если вы хотите, чтобы данное отображение работало в вашей карте, пожалуйста, обратитесь в техническую поддержку (support@redforester.com)
  • Счётчик комментариев. В узле, у иконки типа, отображается число общих и непрочитанных комментариев.
  • Новое меню справки по горячим клавишам поможет разобраться, как удалить узел из середины ветки, не потеряв его потомки.
    Вы найдёте подсказку, наведя курсор на значок
     у строки поиска.
  • Результаты поиска теперь содержат иконку типа узла! Разбираться в длинном списке поисковой выдачи стало проще.
  • Всплывающие уведомления для большинства ошибок и некоторых успешных действий.
  • Иконка ограниченного отображения карты, которая появляется при открытии скопированной ветки как карты, позволяет вернуться к полной карте, не перезаходя в неё.
  • Отобразить ветку как карту теперь можно быстрее и удобнее, если выбрать в контекстном меню узла пункт “Скрыть ветки, кроме текущей”.
  • Групповое изменение цвета узлов. Если выделить несколько узлов, то через пункт “Сменить цвет” в контекстном меню на одном из них можно изменить цвет всей группе.
  • Расширенная вставка по комбинации ctrl+shift+v позволяет вставлять скопированные ветки или узлы с применением опций, например, без пользовательских свойств или не раскрывая скрытую ветку.
  • Переделано меню создания карты, теперь в нём можно сразу импортировать карту из файла json или только типы из неё.
  • Правила доступа к узлу на чтение теперь имеет два уровня — “только чтение” и “чтение и комментирование”

Улучшения UI и UX

  • При вставке в другую ветку вырезанного узла, к нему применяются права нового родителя, как происходит при копировании.
  • Окно подтверждения создания нового родителя ограниченно по высоте и добавлен скроллинг, чтобы при большом количестве элементов оно не уходило за экран.
  • В контекстном меню теперь указываются сочетания клавиш у тех операций, у которых они присутствуют.
  • В боковом меню скучные названия заменены на иконки.
  • Меню навигации по карте приобрело дизайн и ровную вёрстку.
  • Выпадающее меню выбора карт также приобрело дизайн и ровную вёрстку. Теперь отображается аватарка создателя и иконка публичности карты.
  • Смена аватарки стала чуть более понятнее.

Исправление ошибок

  • Наложение узлов друг на друга и  разрыв путей между ними.
  • Не работало отображение цвета узла в результатах поиска.
  • Исправлен перенос слов в превью содержимого узла.
  • HTML-свойства теперь отображаются в превью узла.
  • В публичных картах теперь нельзя оставлять комментарии, если ты не приглашён в карту и у тебя нет прав доступа, как минимум, на чтение и комментирование.
  • Исправлено дублирование комментариев (проявлялось вновь).
  • Пользовательские свойства не удалялись группой сразу после смены типа узла.
  • Не ставился пробел в пользовательских свойствах.
  • При создании узла-ссылки она теперь наследует права родителя, однако, если кому то источник недоступен, то и узел-ссылка будет автоматически недоступен.
  • Кнопка отписки от карты теперь работает корректно.
  • Иногда не переходило к целевым узлам по результату поиска.
  • Сбивался фокус при переходе к узлу по ссылке извне.
  • Различные проблемы с импортом.
  • Различные оптимизации в загрузке карт и узлов, стало быстрее.