Прийшов час осідлати справжнього Буцефала🏇🏻Приборкай норовливого коня разом з Newxel🏇🏻Умови на сайті
×Закрыть

Еще один способ определения качества работы NER-систем

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Задача NER (named entity recognition) — является одной из базовых задач в NLP. Поэтому, данная тема заезжена вдоль и поперек, но каждый раз находится что-то новое. В нашем случае поговорим о метриках.

Как это делают обычно

Определение качества работы ML-алгоритмов (называемых метриками) — обязательная составляющая процесса разработки. Пока не налажен подсчет метрик, бессмысленно улучшать алгоритм.
Для такой задачи, как NER, имеются уже давно отработанные решения. Например, разобьем текст на токены (в нашей задаче это последовательности слов, символов пунктуации и других лексем). Далее, пометим каждый токен следующим образом:

TokensIliveinPaloAlto.
CodesOOOB-LOC I-LOCO

Это, так называемое, BIO-кодирование (Begin-Inside-Outside). Здесь O означает, что данный токен не принадлежит к какой-то из распознаваемых сущностей. B-LOC означает, что это первый «B» токен в последовательности типа «LOC» (location). I-LOC — для второго и последующего токенов этой же последовательности. Для других сущностей будет меняться вторая часть кода. Примеры типичных типов, которые часто встречаются в статьях, работах и датасетах: PER — person, MISC — разное, ORG — organization.

Типичные метрики для измерения качества NER-систем, это:

  • Precision
  • Recall
  • F1

Перед тем, как описать эти понятия, введем еще некоторые определения:

  • TP — true positive, количество элементов, правильно определенных, как принадлежащих классу.
  • FP — false positive — количество элементов, которые алгоритм пометил, как принадлежащие классу, но это было неверно.
  • TN — true negative — элементы, которые правильно были определены, как не принадлежащие классу.
  • FN — false negative — элементы, которые алгоритм пометил, как не принадлежащие классу, но это неверно.

FP & FN также называются ошибками первого и второго рода. Чтобы лучше запомнить ошибки первого и второго рода, в сети ходит масса разных мемчиков. Я здесь просто оставлю один из самых удачных (на мой взгляд):


Изображение: Effect Size FAQs by Paul Ellis

В разных случаях они имеют разную цену и нам необходимо сдвигать баланс в ту или иную сторону (об этом ниже)

Precision (точность) — показывает, какая доля из найденных элементов класса, найдена правильно:

Recall (полнота) — доля правильно спрогнозированных элементов, относительно всех действительных элементов класса:

Данные метрики (если у нас нет идеального классификатора), тянут результаты в разные стороны. Часто, мы можем «подкрутить» что-то в настройках классификатора так, чтобы он практически не ошибался при выборе элементов. Но это будет означать также, что он будет крайне осторожен, и не будет промаркировано много элементов, которые на самом деле нужно было промаркировать. И наоборот.

Чтобы совместить эти две цели, вводят среднее гармоническое от точности и полноты. Такая метрика называется F1:

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

Или, в терминах ошибок первого и второго рода:

Таким образом, используя метрику F2, мы делаем полноту важнее точности (это может быть полезно при оценке тех, кто мог заболеть чем-то), а если используем F0.5, наоборот — важнее будет безошибочность. Такой вариант может быть полезен, если дальнейшие действия связаны с большим риском или затратами в случае ошибочного решения.

Распространенный вариант метрик с использованием BIO-кодирования реализован в библиотеке seqeval. Минимальный код можно посмотреть и запустить в Colab, используя следующую ссылку:

colab.research.google.com/...​r/notebooks/seqeval.ipynb

Что не устраивает

Казалось бы — все уже сделано, можно брать существующее и расходиться. Что же не устроило в обычном подходе?

Наша компания Phase One Karma разрабатывает legal tech продукт Loio, который помогает юристам быстрее и с меньшим количеством ошибок работать с контрактами. Одним из важных моментов в такой работе является выделение достаточно специфических сущностей. И попытки применить к ним стандартный подход натолкнулись на сложности.

  • Подсчет на уровне токенов зависит от метода разбиения на токены. А каждый парсер может это делать немного иначе.
  • Некоторые сущности, те же спейсинги (это оставленные под заполнение в документе места), могут вообще не содержать токенов в общепринятом смысле.
  • При наличии большой разницы в длине сущностей, идет перекос в сторону большего веса более длинных из них.

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

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

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

  • Сильный перекосу в сторону большего учета длинных последовательностей.
  • Спейсинги (да, это во многом необычная сущность), могут быть нулевой длины. Например, когда пишут «Name:», после чего идет окончание строки. И посимвольный подход не учитывает такие сценарии.
Один из подходов к учету частичных перекрытий можно посмотреть в статье David S. Batista «Named-Entity evaluation metrics based on entity-level». Если очень коротко, он предлагает учитывать частичные совпадения с коэффициентом ½. Это конечно лучше, чем совсем не учитывать, но мы пойдем дальше.

Наш подход

Входные данные

Прежде всего, определимся с данными. В Loio есть большое количество сущностей и они, в отличие от того, что ожидают большинство стандартных библиотек, могут перекрываться. Приведу пример, где размечена одна из сторон контракта и некоторые сущности, пересекающиеся с ней (данные фейковые, использовался сервис fakenamegenerator.com, любые совпадения случайны):

Здесь мы видим «матрешку» — в определении стороны находится адрес этой стороны, внутри которого встречаются локации (Location). Обычно, пользователю не стоит показывать именно в таком виде, но находить все географические и административные объекты для дальнейшего анализа — необходимо.

Поэтому далее мы считаем, что каждый тип сущности мы учитываем отдельно, а внутри каждого типа сущности пересечения границ недопустимы.

Общие принципы

Считаем, что основные метрики Precision, Recall, F1 рассчитываем по приведенным ранее формулам на основании значений TP, FP, FN. Единственное отличие заключается в том, как мы подсчитываем эти самые TP, FP, FN.

Количество правильных совпадений, подсчитываем как:

где:

  • exact_matches — количество точных совпадений (включая совпадения с нулевой длиной). Спаны с нулевой длиной проверяются только на точные совпадения.
  • overlapping_factor(i) — коэффициент перекрытия для частичного совпадения с номером i. Он считается как отношение символов в пересечении gold standard и найденных системой, к длине наибольшей из сущностей, задействованных в пересечении.
  • s — коэффициент поддержки (stimulation) частичных совпадений. Должен быть в диапазоне от 0 до 1.

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

FN — аналогично, только используем количество спанов в gold standard последовательности:

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

Если коэффициент стимуляции равен единице, то мы никак не штрафуем то, что совпадение частичное. Сколько перекрылось (в процентах), столько и учитываем. На практике хочется немного штрафовать в том случае, когда перекрытие частичное. Поэтому в своих проектах я часто использую коэффициент 0.75.

Сложные случаи и полное описание алгоритма

Описанная выше схема — пока описание принципов. Теперь рассмотрим сложные случаи, которые требуют более сложной схемы учета частичных перекрытий.

Чаще всего у нас идут такие вот частичные совпадения ожидаемых (expected) и найденных тестируемой системой (actual) сущностей:

Gold standard (он же Expected):
Some text with one long span

Tested (он же Actual):
Some text with one long span
Some text with one long span
Some text with one long span

Здесь мы видим пересечение одного диапазона символов в expected и одного в actual последовательности.

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

Gold standard (Expected):
Some text with one long span

Tested (Actual):
Some text with one long span

Нелогично учитывать все частичные совпадения — мы должны стимулировать алгоритм находить идентичное количество сущностей с тем, что находит человек (точнее тем, что есть в gold standard). Поэтому, окончательная процедура подсчета полных и неполных совпадений следующая:

  1. Считаем, что алгоритму переданы списки expected и actual сущностей, которые отсортированы по позиции первого символа, и на каждой из сторон нет наложений.
  2. Подсчитываем полные совпадения.
  3. Убираем в обеих последовательностях из дальнейшего рассмотрения сущности с нулевой длиной и те, что совпали полностью.
  4. Продвигаемся по отсортированным сущностям actual-последовательности.
    1. Если есть частичное совпадение, считаем коэффициент перекрытия (как было указано выше) только с первой от начала текста сущностью в expected последовательности, и учитываем его в подсчете TP.
    2. Удаляем из дальнейшего рассмотрения все сущности expected-последовательности, затронутые в частичном совпадении.
Пункты 4.1/4.2. дают нам необходимое поведение, когда не стимулируется учет большого количества мелких частичных совпадений на фоне длинной сущности в оригинальной последовательности (и наоборот).

Пример

Чтобы алгоритм стал более понятен, пройдем по шагам алгоритма на искусственном примере, который небольшой, но покажет нужные нам особенности. Давайте, вернемся к примеру с определением сторон договора. Правильное выделение определения двух сторон (gold standard or expected):

This DIAGNOSTIC PLATFORM BENCHMARKING STUDY AND EVALUATION AGREEMENT (the «Agreement») is made and entered into as of the last date of signature below (the «Effective Date»), by and between ProYard Services, a Delaware corporation having its principal place of business at 2140 Science Center Drive Burley, San Diego, CA, USA, ID 83318 («PartyA») and ZOEMENS AG, a German corporation having its principal place of business at Nuernbergerstrasse 89, 23626 Ratekau («PartyB»).

У нас здесь 2 стороны договора. Теперь представим, что какой-то алгоритм отдал нам обратно следующую разметку сущностей:

This DIAGNOSTIC PLATFORM BENCHMARKING STUDY AND EVALUATION AGREEMENT (the «Agreement») is made and entered into as of the last date of signature below (the «Effective Date»), by and between ProYard Services, a Delaware corporation having its principal place of business at 2140 Science Center Drive Burley, San Diego, CA, USA, ID 83318 («PartyA») and ZOEMENS AG, a German corporation having its principal place of business at Nuernbergerstrasse 89, 23626 Ratekau («PartyB»).

Здесь мы видим, что алгоритм выделил 4 текстовых фрагмента как сущность «сторона договора». При этом, идеальное совпадение с ожидаемым, только у одного — последний фрагмент, начинающийся с «ZOEMENS AG».

Идем по шагам алгоритма.
У нас есть отсортированные сущности:

Expected Actual
(1) This DIAGNOSTIC PLATFORM BENCHMARKING STUDY AND EVALUATION AGREEMENT (the «Agreement»)
(1) ProYard Services, a Delaware corporation having its principal place of business at 2140 Science Center Drive Burley, San Diego, CA, USA, ID 83318 («PartyA»)(2) ProYard Services, a Delaware corporation having its principal place of business at 2140 Science Center Drive Burley, San Diego, CA, USA,
(3) 83318 («PartyA»)
(2) ZOEMENS AG, a German corporation having its principal place of business at Nuernbergerstrasse 89, 23626 Ratekau («PartyB»)(4) ZOEMENS AG, a German corporation having its principal place of business at Nuernbergerstrasse 89, 23626 Ratekau («PartyB»)

Есть одно полное совпадение Expected (2) и Actual (4). Убираем эти фрагменты из дальнейшего рассмотрения, запомнив 1 как exact_matches.

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

Actual (1) — не пересекается ни с чем в Expected. Соответственно, далее не учитывается.
Actual (2) — частично пересекается с Expected (1). Длина пересечения — 135 символов, длина самой длинной сущности из пересечения, Expected(1)=156 символов.

Соответственно, коэффициент пересечения = 135 / 156 = 0.8654. Убираем Expected(1) из дальнейшего рассмотрения, поскольку он уже был задействован.
Actual(3) — несмотря на то, что он пересекается с фрагментом Expected(1), мы не будем учитывать это пересечение, поскольку Expected(1) уже был учтен в другом частичном пересечении.

Считаем TP по нашей формуле со значением коэффициента стимуляции 0.75:

TP = exact_matches + s * sum(overlapping_factor) = 1 + 0.75 * 0.8654 = 1.6490
FP = total_actual — TP = 4 — 1.6490 = 2.351
FN = total_expected — TP = 2 — 1.6490 = 0.351

Теперь мы можем посчитать метрики Precision, Recall, F1. Формулы стандартные, но используются откорректированные с учетом частичных перекрытий TP, FP, FN:

Precision = TP / (TP + FP) = 1.649 / 4 = 0.4122
Recall = TP / (TP + FN) = 1.649 / 2 = 0.8245
F1 = 2 * (Precision * Recall) / (Precision + Recall) = 2 * (0.4122 * 0.8245) / (0.4122 + 0.8245) = 0.5496

Аналогично, можно подсчитать любые другие метрики, которые базируются на TP, FP, FN.

Исходные коды

Описанный алгоритм реализован в виде open-source библиотеки loio_metrics и выложен в открытый доступ.

Пример использования можно посмотреть на Google Colab:
colab.research.google.com/...​s/Loio_metrics_demo.ipynb.

LinkedIn

Похожие статьи

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Подписаться на комментарии