Разбитие текста на предложения лингво-независимым методом на примере библиотеки AIF
В прошлой статье мы уже рассказывали о новой NLP библиотеке. Однако тогда мы рассказали «обовсем» и не о чем конкретном. Сегодня мы поговорим о теоретических аспектах разбития предложения на токены лингво-независимыми алгоритмами. Теоретические выкладки будут подкреплены практической реализацией в библиотеке AIF. Поехали…ТерминыМы решили указать термины, которыми мы пользуемся, чтобы строить нашу статью на их базе.
токен — часть текста (массив символов), отделенная проблемами или концом/началом строки; технические символы — символы, которые используются для логического группирования токенов в тексте (:,.?!»;); технические символы первой группы — символы, которые чаще всего используются в тексте для деления текста на предложения; технические символы второй группы — символы, которые чаще всего используются в тексте для деления предложений на части; Теперь перейдем к более запутанному дефиницию — предложению. Берем определение из википедии:
Предложе́ние (в языке) — это единица языка, которая представляет собой грамматически организованное соединение слов (или слово), обладающее смысловой и интонационной законченностью.[1] С точки зрения пунктуации, предложение как законченная единица речи оформляется в конце точкой, восклицательным или вопросительным знаками — или многоточием.
Данное определение можно использовать почти как есть, немного переделав вторую его часть (пунктуационную):
предложение — часть токенов, разделенных между собой техническими символами, которые используются для разбития текста на предложения;
Так мы оставляем за кадром какие именно символы используются для разбития текста на предложения.
Процесс разбития текста на предложения лингво-независимым методом
Для начала давайте определимся с условием задачи:
на вход подается токинизированный текст (массив токенов); нету никаких данных о языке текста; нету данных о том, какие символы используются или могут использоваться для разделения текста на предложения. Задача разбития текста на предложения в таких условиях разбивается на 4 подзадачи:
найти в тексте технические символы; поделить найденные технические символы на группы; определить какая из групп технических символов является первой, а какая второй; разбить текст на предложения при помощи выделенных групп символов; Каждая из этих задач довольно независима и может быть рассмотрена в отрыве от остальных. Давайте понемногу разбираться. Для каждого шага будет дана ссылка на вики с английской версией описания алгоритма.
1 Поиск технических символов в тексте
wiki
Как можно найти технические символы в тексте?
Просмотрев бегло текст на большинстве языков, можно обнаружить, что данные символы (технические символы) всегда стоят в конце токенов. Эта гипотеза сразу же вносит ограничения на язык входящего сообщения (в языке должны использоваться пробелы). Давайте теперь подумаем как можно определить технические символы, если наша гипотеза верна.
Первое, что может прийти на ум — посчитать для каждого символа вероятность того, что этот символ в данном тексте стоит в конце токенов. А после отобрать символы, которые имеют самую высокую вероятность.
Данное предположение разбивается о первый же эксперимент с разными языками, показывая, что во многих языках существуют буквы стоящие с завидной регулярностью в самом начале токенов или в конце. Использовать этот подход так наивно нельзя.
В результате формула вероятности того, что символ является техническим выглядит так:
(1) P1(ch)*(P2(ch)^2)
где:
P1(ch) — это вероятность того, что символ ch в данном тексте стоит в конце токеновP2(ch) — это вероятность того, что символ стоящий перед символом ch в данном тексте — тоже стоит в конце токенов
давайте рассмотрим пример расчета вероятности P2. Допустим, у нас есть такие символы:
. y a b
и вероятность того, что они стоят в конце токенов: P1(.) = 0.8P1(y) = 0.9P1(a) = 0.01P1(b) = 0.02
символ точка в конце токенов встретился 4 раза, а перед точкой стояли такие символы: y — 3 разаa — 1 раз
в этом случае P2('.') будет рассчитываться следующим образом:¾ * P1(y) + ¼ * P1(a) = 0.75×0.9 + 0.25×0.01 = 0.6775
Это уже более интересно. И вроде даже работает. Однако, если покопаться в коде AIF, то можно увидеть, что анализ проводится немного более сложный, чем просто подсчет вероятностей по этой формуле.
Дело в том, что даже эта формула не дает 100% желаемого результата. Ибо есть языки, в которых слова часто оканчиваются на одни и те же два символа. Ну, например, текст в котором существенно преобладает окончание «ec». И при этом сам по себе символ «е» часто стоит в конце токенов. В результате символ «с» будет выделен в качестве технического, так как он стоит часто в конце токенов и перед ним символ, который также встречается в конце токенов.
Но и это довольно просто лечиться — необходимо отфильтровать технические символы, которые были получены первой формулой. Фильтровать можно по двум простым критериям. Во-первых, по вероятности того, что символ всегда стоит в конце токена. Да-да, мы говорили, что это плохой критерий, но он же является прекрасным фильтром символов, найденных нашей эвристикой. Во-вторых, нужно убрать символы, которые встречались в тексте очень мало. Нам не очень хочется получить на выходе символ, который в тексте встретился аж один раз и в это раз он был в конце токена. Вероятно, этот символ разделитель, но мы это узнать никак не можем.
В результате AIF делает нечто следующее:
Отбирает N-символов с самой высокой вероятностью, рассчитанной по формуле 1, а из них отбирает N2-символов, которые имеют наибольшую вероятность P1. Как правильно подобрать N/N2 числа — это еще та задача, но углубляться в ее подробности мы сейчас не будем, так как AIF пока берет эти числа в некотором роде «с потолка». Нам еще предстоит проверить на практике несколько гипотез на этот счет.
В первой статье на Хабре был показан график первого прохода формулой по тексту. Я хочу лишь сказать, что с того момента формула была изменена и теперь работает точнее (намного точнее).
А теперь давайте немного поговорим о качественном анализе.
Качественный анализ подхода показывает такие результаты (на 186 книг):12 книг, в которых не удается найти точку на 186 книг;2 книги, в которых не удается найти запятую;3 книги, в которых в качестве технического символа была выделена буква;
2 Деление технических символов на группы
wiki
На предыдущем этапе мы смогли определить список технических символов. Список может выглядеть, например, так:
.,?!:;()»-
Теперь необходимо поделить этот список на группы. В этом примере символы могут быть поделены на группы следующим образом:
.?!()»-:;,
Задача деления на группы была решена простой гипотезой — в каждом языке есть символы, которые чаще употребляются в начале предложений. Соответственно для каждого технического символа можно составить граф связей с символами, которые следуют после технического символа.
В результате мы получим для каждого разделительного символа приблизительно следующий граф связей:
связи точки:.P=32, S=16, T=63, F=15, W=44, {=67, N=14
связи запятой:, p=47, a=59, b=84, c=52, s=102, d=76, t=295, e=49, w=318, m=59
связи латинской буквы «y»: ys=3, t=2, w=6
Данные связи взяты из реального текста и они отфильтрованы. Дело в том, что AIF для анализа оставляет только наиболее весомые связи. Без фильтрации граф будет выглядеть несколько иначе.
Само собой, абсолютные весы нам неинтересны и данные связи будут переконвертированные в вероятностные.
Имея для каждого символа такой граф связей, мы можем поделить символы на два кластера, для этого лишь необходимо определить алгоритм сравнений двух графов.
Реализацию сравнения графов в AIF лучше всего рассмотреть на примере. Допустим у нас есть два графа связей:.А 0.2П 0.6а 0.05п 0.15
, а 0.4п 0.6
А теперь алгоритм сравнения:
P (ch1, ch2) = ch1.connections.keys.mapToDouble (connectionKey → (ch1.connections.get (connectionKey) + ch2.connections.get (connectionKey)) / 2).sum () / ch1.connections.keys.size ()
вот как-то так. Да, тут есть свои нюансы, например, P (ch1, ch1) может не быть равным P (ch2, ch1). Но никто и не говорит, что Alpha2 — это финальная версия;)
Особенно хорошо этот подход работает на языках, в которых используется регистр (т.е. большая или маленькая буквы). Чуть хуже, но все равно эффективно, работает на арабском и подобных языках.
Качество работы данного модуля:~0.5 книги на 100 книг, где точка и запятая попадают в одну и ту же группу.
Само собой, в этом пункте ОЧЕНЬ много осталось за кадром. Например, после какого порога вероятности P (ch1, ch2) считаем, что два графа будут равными, и что два символа, которые образуют эти графы из одного кластера?
Случайные примеры групп для разных книг: книга 1: [»; ,] [.]книга 2: [! .] [:; ,]
3 Определить, какая из групп технических символов отвечает за разбитие текста на предложения
wiki
А вот тут все совсем просто. Отображаем массив токенов в новый массив, где каждому токену ставится в соответствие номер группы технического символа, которым заканчивается токен. Если в токенах нету технического символа, то ставим ему нулевую группу. Например, у нас есть такие токены:
Привет! Как твои дела? Я, думаю, что все в порядке. Нет?
И на прошлом этапе у нас были выделены такие группы разделителей:1 — [?!,]2 — [,]
Соответственно после отображения мы получим такой массив:1 0 0 1 2 2 0 0 0 1 1
Имея такой массив, мы можем построить связь между группой (например, между 1ой группой) и символами, с которых начинается следующий токен.
Ну и пример: вот связи первой группы с символами — взято из реальной книги (связи нормализованы по отношению к максимуму):
{A=0.36, B=0.26,»=0.39, C=0.10, D=0.08, E=0.1, H=0.37, I=0.72, L=0.08, M=0.14, N=0.1, O=0.15, S=0.26, T=1.0, W=0.26, Y=0.08}
А вот связи для второй группы:
{A=0.05, a=1.0,»=0.11, b=0.24, c=0.08, d=0.06, e=0.05, f=0.11, h=0.17, I=0.09, i=0.22, m=0.07, n=0.06, o=0.16, p=0.05, s=0.21, t=0.40, w=0.35}
Как и в прошлый раз, AIF фильтрует связи, оставляя только самые весомые. Так что до фильтрации связи будут немного другими.
А вот связи нулевой группы:
{a=0.61, b=0.25, c=0.26, d=0.18, e=0.15, f=0.26, g=0.12, h=0.41, I=0.05, i=0.35, l=0.17, m=0.26, n=0.13, o=0.48, p=0.22, r=0.14, s=0.42, t=1.0, u=0.07, v=0.06, w=0.43, y=0.06}
Имея эти данные, нам лишь необходимо посчитать какой из графов ближе к графу нулевой группы. Технические символы образующие эту группу (самую близкую к нулевой группе) — это символы, которые используются для разделения токенов внутри предложения. В то же время граф, который максимально удален от графа нулевой группы, образован группой технических символов, которые отвечают за разделение текста на предложения.
В данном примере первая группа — это та группа технических символов, которая разделяет токены на предложения, а вторая группа содержит символы, которые делят токены внутри предложения.
Качественный анализ результатов показывает:4 книги из 180, где точка была отнесена к неверной группе;2 книги из 180, где запятая была отнесена к неверной группе;
4 Разбить текст на предложения при помощи выделенных групп символов
wiki
Ну хорошо. Есть у нас группы символов и мы знаем какая группа за что отвечает. Но как же теперь понять, в каких случаях символы первой группы используются для разбития текста на предложения, а в каких — нет?
Например, как понять, что точка в конце «С.С. С.Р.» не для конца предложения, а просто окончание аббревиатуры. Ну или сокращения типа «тыщ.» и т.д.
И опять же, все просто.
Зная символы, которые относятся к первой группе, мы можем пробежаться по всем токенам и посчитать среднюю длину предложений. После этого для каждого случая использования символов из первой группы мы можем: посмотреть первый символ следующего токена и сказать для какой группы технических символов характерна эта связь; посмотреть расстояние до предыдущего символа первой группы и до следующего;
Если символ следующего токена характерен для второй группы символов и размер предыдущего и следующего предложения меньше или равно среднему размеру предложения в тексте, то в этом конкретном случае символ первой группы НЕ используется для разбития текста на предложения.
Примеры из книги с местами найденными AIF, где разделитель первой группы был отмечен как разделитель второй группы:
«Последнее восстание» в Сеуле Международная биеннале«Этот убийца… он такой мягкий иЭльдара Рязанова. «Ирония судьбы», «Служебный роман»5–7 мин. также может стать простым1 мин. горячая вода (+37–38°), 15–10 сек. — холодная вода (5 тыс. лет назад и выполняли
Когда смотришь на этот результат очень забавно осознавать, что он работает абсолютно языково независимо, без какой-либо входной информации, кроме самого текста. Вот пример из другой книги на английском языке:
by U.S. federal laws andthe U.S. unless a copyright
К сожалению, для текущего шага у нас нету никаких результатов качества =(
Послесловие
Все увиденное — это лишь Alpha2, мы еще даже не начинали заботиться о качестве и скорости работы.
Согласно с планами Alpha3 мы в следующем релизе уделим внимание качеству и скорости, а также рефакторинг. Единственной новой функцией библиотеки будет построение словаря языка водного
Сам алгоритм и API библиотеки детально расписаны на вики проекта: github.com/b0noI/AIF2/wiki
В месте с библиотекой мы так же обновили простенький консольный клиент — AIF-CLI, который теперь умеет показывать найденные технические символы и группы этих символов.
Наша команда
Kovalevskyi Viacheslav — algorithm developer, architecture design, team lead (viacheslav@b0noi.com / b0noi)Ifthikhan Nazeem — algorithm designer, architecture design, developerSviatoslav Glushchenko — REST design and implementation, developerOleg Kozlovskyi QA (integration and qaulity testing), developer.Balenko Aleksey (podorozhnick@gmail.com) — added stammer support to CLI, junior developerEvgeniy Dolgikh — QA assistance, junior developer
PS: Если у вас есть интересный проект NLP, свяжитесь с нами ;)
Ссылки на проект и подробности
project language: Java 8license: MIT licenseissue tracker: github.com/b0noI/AIF2/issueswiki: github.com/b0noI/AIF2/wikisource code: github.com/b0noI/AIF2developers mail list: aif2-dev@yahoogroups.com (subscribe: aif2-dev-subscribe@yahoogroups.com)
Условия тестирования
Все тесты проводились на 186 книгах следующих языков:
польский; итальянский; французский; немецкий; английский; русский.
