www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Быстрая Word Сегментация Шумного текста

Дата публикации Apr 16, 2018

Вергилий Ватикан

TL; DR

БыстрееСегментация слов с использованием треугольной матрицы вместо динамического программирования. ИнтегрированныйИсправление орфографиипозволяетшумный ввод текста,C # исходный кодна GitHub.


Для людей на Западе кажется очевидным, что слова разделены пробелом, в то время как на китайском, японском, корейском (языки CJK), тайские и яванские слова пишутся без пробелов между словами.

Даже классический греческий и поздний классический латинский были написаны без этих пробелов. Это было известно какПродолжение сценария,

И кажется, что мы еще не потеряли свои возможности: мы можем легко расшифровать

Быстрая коричневая лиса прыгает через ленивую собаку

как

Быстрая коричневая лиса прыгает через ленивую собаку

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

Зачем?

Но зачем нам внедрять сегментацию слов программно, если люди все равно могут читать несегментированный текст?

Для языков CJK без пробелов между словами,это более очевидно.

Поисковые системыкак Google или Baidu должны индексировать этот текст таким образом, который позволяет эффективный и быстрый поиск. Эти веб-поисковые системы основаны наинвертированные индексы, При сканировании каждого слова создается отдельный список ссылок. Каждый список содержит ссылки на все веб-страницы, где встречается это конкретное слово.

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

Исправление орфографиипозволяет исправить слова с ошибками. Это делается путем поиска возможных слов с ошибками в словаре. Если слово найдено, слово считается правильным. Если слово не найдено, то те слова из словаря, которые наиболее близки к кандидату (согласно метрике расстояния редактирования, напримерDamerau-Левенштейна) представлены как предложения по исправлению орфографии. Конечно, наивный подход вычисления расстояния редактирования для каждой словарной статьи очень неэффективен.SymSpellэто гораздо более быстрый алгоритм. Но в любом случае, предварительным условием является сначала определить границы слова, чтобы в первую очередь иметь вход для алгоритма исправления орфографии.

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

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

  • Нормализующий английский составное существительноеs, которые написаны по-разному: например, ice box = ice-box = icebox; pig sty = pig-sty = pigsty) для поиска и индексации.
  • Сегментация слов для соединений:как оригинальные слова, так и разделенные части слова должны быть проиндексированы.
  • Опечаткиможет вызвать пропуски.
  • Ошибки конвертации: во время преобразования некоторые пробелы между словами могут быть потеряны, например, удаляя разрывы строк вместо замены их пробелами.
  • Ошибки распознавания: низкое качество оригинальных документов или рукописного текста может привести к тому, что не все пробелы между словами будут правильно распознаны.
  • Ошибки передачи:во время передачи по шумным каналам могут быть потеряны пробелы или допущены орфографические ошибки.
  • Извлечение ключевых словиз URL-адресов, доменных имен, описания столбцов таблицы или переменных программирования, которые пишутся без пробелов.
  • Дляанализ пароля, извлечение терминов из паролей может потребоваться.
  • Распознавание речи, если пробелы между словами не распознаются должным образом в разговорной речи.
  • автоматическаяCamelCasingпрограммирования переменных.

Но сегментация слов может представлять интерес и за пределами естественных языков, например длясегментирование последовательности ДНК в слова(PDF).

Генерация варианта сегментации

Строка может быть разделена несколькими способами. Каждый отдельный вариант сегментации называетсясостав, Сколько существует разных композиций?

  • В строке длиной nколичество потенциальных границ словявляетсяп»= п-1(между каждым символом строки).
  • Каждая из этих позиций может фактически использоваться в качестве границы слова или нет. Мы можем думать об этом как о числе в двоичной форме, где каждый бит может быть установлен или нет.
  • В двоичной системе счисления число с n цифрами может представлять x = 2 ^ n различных чисел. Поэтому число вариантов сегментации такжех = 2 ^ п»(n ’количество потенциальных границ слов)
  • Каждая строка длиной n может быть сегментирована на2 ^ п-1возможныйкомпозиции

Состав струны должен оцениваться по двум критериям:

  1. Является ли композиция допустимой сегментацией слов, то есть состоит ли она из подлинных слов (мы научимся обращаться с неизвестными словами).
  2. Какое из допустимых сегментов слова (их может быть несколько) для этой конкретной входной строки имеет наибольшую вероятность и будет выбрано как конечный результат.

Рекурсивный подход

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

Следующий рекурсивный алгоритм перечисляет все композиции:

Для "это»В качестве входных данных он будет генерировать все8 возможных композиций:

i s i t
i s it
i si t
i sit
is i t
is it
isi t
isit

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

Но существует проблема. Каждая строка длиной n может быть сегментирована на2 ^ п-1возможныйкомпозиции, Это огромно!

Наивный алгоритмэкспоненциальныйа такжене будет масштабироватьсядля более длинных строк!

Например. наша строкаБыстрая коричневая лиса прыгает через ленивую собакуимеет длину 35. Это приводит к более17 миллиардовгенерируемые варианты сегментации, все их слова для проверки в словаре и, наконец, варианты, ранжируемые по вероятности.

У нас обычно не так много времени и вычислительной мощности. Нам нужно придумать что-то умнее и эффективнее.

Инкрементный расчет локального оптимума

Мыне нужно создавать всекомпозиции на заказнайти лучшееодин!

В наивном алгоритме генерируется все дерево вариантов сегментации. Дляповторяющиеся подстрокисегментация также генерируется неоднократно, И только в конце все сгенерированные полные сегментации сравниваются, чтобы найти лучшую.

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

выбор местного оптимумаоснован напредположение, что последовательные частичные сегментации независимы,

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

Два разных подходаДля достижения этой цели представлены в следующих разделах.

Подход динамического программирования

Одним из способов улучшения алгоритма является использованиеДинамическое программирование:

Это метод решения сложной проблемы, разбитый на набор простых подзадач, решение каждой из этих подзадач только один раз и сохранение их решений. В следующий раз, когда возникает та же самая подзадача, вместо повторного вычисления ее решения, каждый просто ищет ранее вычисленное решение, тем самым экономя время вычислений. Каждое из решений подзадачи каким-то образом индексируется, как правило, на основе значений его входных параметров, чтобы облегчить его поиск. Техника хранения решений подзадач вместо их пересчета называется «мемоизации». [Источник: Википедия]

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

Этот метод использовался для сегментации слов несколько раз:

Поскольку я не смог найти порт C # в Интернете, вот моя реализация подхода динамического программирования:

Исходный код WordSegmentationDP

Треугольный матричный подход

Динамическое программированиеиспользуемый подходрекурсияитолковый словарьдля запоминания оптимальной сегментацииостальные подстроки,

Треугольный матричный подходиспользованиявложенные циклыиКруговой массивхранить оптимальную сегментациюпрефиксные подстрокивместо.

Создается треугольная матрица деталей с увеличивающейся длиной, организованная как круговой массив. этопозволяет постоянное потребление памяти O (1)(по сравнению с линейным O (n) для динамического программирования), поскольку промежуточные варианты сегментации перезаписываются, если они больше не требуются. Вместо того, чтобы хранить полные сегментированные строки, толькобитовый вектор потенциальных пространственных положенийиспользуется этоуменьшает потребление памятихранить варианты сегментации (1 бит вместо 1 символа) иСборка мусора,

Треугольный матричный алгоритм

И реализация C # треугольной матрицы:

Исходный код WordSegmentationTM

Динамическое программирование против треугольной матрицы

Итак, каковы сходства и различия между двумя подходами?

  • Оба алгоритма обеспечиваютидентичные результаты,
  • У обоих одинаковыелинейная вычислительная сложность O (n).
  • Оба хранят лучший вариант сегментации для конкретной подстроки, так что она должна быть рассчитана только один раз.
  • DP рассчитывает все варианты сегментации для конкретногоостальная подстрокапоследовательно, Лучший вариантхранится в кеш-словаре (хэш-таблица), Чтобы получить доступ к результату сегментации для определенного остаткаподстрока используется в качестве ключа,
  • TM рассчитывает варианты сегментации для конкретногопрефиксная подстрокане-последовательнов определенной позиции внутреннего цикла. Лучший вариантхранится в массиве, Чтобы получить доступ к результату сегментации для определенной подстроки префиксапозиция цикла используется в качестве индекса,
  • ТМ имеетпостоянное потребление памяти(размер массива = O (1) = maxSegmentationWordLength)в то время как DP имеетлинейное потребление памяти(количество записей в кеш-словаре = O (n) = длина входного текста).
  • Кроме того, даже для того же количества записейпотребление памяти массива (MT) нижечем потребление памяти словаря (DP).
  • Кроме того, ТМ хранит толькобитовый вектор потенциальных пространственных положенийв то время как DP хранит полные сегментированные строки. Это дальшеуменьшает потребление памятихранить варианты сегментации (1 бит вместо 1 символа) иСборка мусора,
  • доступ к массиву через индекс (MT) быстреечем доступ к словарю кеша через ключ (DP).
  • номер поиска к словарю частоты слов похождля обоих.
  • Итерация обычно быстрее, чем рекурсияи предотвращает возможные пределы рекурсии (превышение максимальной глубины рекурсии / переполнение стека).

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

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

Максимальная длина слова

Кандидаты в слова генерируются из строки только до максимальной длины. Norvig выбрал максимальную длину слова произвольно до 20. Каксамое длинное слово зависит от языка(максимум 6 символов на китайском языке) лучше всего извлечь из самого длинного слова в словаре. Хотя это эвристический подход, очень маловероятно, что существует действительное подлинное слово, которое больше, чем самое длинное из словаря. Это также предотвращает поиск слов, которые, как мы уже знаем, отсутствуют в словаре, и создание композиций, содержащих такие несуществующие слова. Это обеспечит максимальную скорость сегментации.

Вычислительная сложность

Как динамическое программирование, так и подход треугольной матрицы имеютлинейное время выполнения O (n)найти оптимальный состав.

Точная связь между длиной текста n и временем выполненияO (n * Min (n, максимальная длина слова в словаре) / 2),

Выбор варианта сегментации

Может быть несколько допустимых вариантов разбить строку на слова:

этовозможноэтоилиэто

Частоты слова (или вероятности появления слова) используются для определения наиболее вероятного варианта сегментации.

слововероятность появления P = количество слов C / размер корпуса N

Размер корпуса Nобщее количество слов в текстовом корпусе, используемое для создания частотного словаря. N равно сумме всех значений c в частотном словаре, только если словарь полон, но не в том случае, если словарь урезан или отфильтрован.

Наивное байесовское правило

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

Р (АВ) = Р (А) * Р (В)

Качество сегментации может быть улучшено путем использованиябиграмм вероятностивместо тоговероятности одного слова,

Логарифмическая шкала

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

Журнал (Р (АВ)) = лог (Р (А)) + журнал (Р (В))

Известные слова

Чтобы рассчитать вероятности появления слова, мы можем использовать разные подходы:

  1. Создайте наш собственный словарь частоты слов, считая слова в большом текстовом корпусе.Если словарь получен из корпуса, похожего на документы, которые вы будете обрабатывать,подобные вероятности появления словараспределение обеспечитоптимальные результаты,
  2. Используйте существующий частотный словарь, который содержит количество слов, например,Данные Google Книг Ngram, Недостатком является то, что данные Google Книг Ngram содержат не только правильные слова, но и орфографические ошибки и другие фрагменты. Хотя многие орфографические ошибки в любом случае не будут влиять из-за их низкой вероятности, это не всегда гарантируется. Например. частые орфографические ошибки частых слов могут победить подлинные редкие слова.
  3. Качество словаря имеет первостепенное значение для качества сегментации. Для достижения этого два источника данных могут быть объединены пересечением: огромныйДанные Google Книг Ngramобеспечиваетрепрезентативные частоты слов(но содержит много записей с орфографическими ошибками)даже для редких слова такжеSCOWL - Списки слов, ориентированные на проверку орфографиикоторыйобеспечивает подлинный английский словарь(но не содержит частот слов, необходимых для ранжирования предложений в пределах одного и того же расстояния редактирования).

Я решил использовать вариант 3, пересечение подлинного словаря английских слов с частотами слов из корпуса Google Книг Ngram из-за соответствующих частот слов даже для редких слов. Нонедостатокпо сравнению с вариантом 1 этокорпус Google был получен изкниги разных веков,использование языков со временем изменилосьи использование языка отличается в разных областях (например, медицина, право, проза, новости, наука).

Неизвестные слова

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

Поэтому мы должны оценить вероятность появления слова по неизвестным словам. Информация, которую мы имеем даже для неизвестных слов, является их длиной.

Джордж Кингсли ЦипфЗамечено, что длина слов обратно пропорциональна их частоте. Слова, которые часто используются, такие как «,», как правило, короткие (Зипф Г. Психобиология языка). Ципф объяснил это «Принципом наименьшего усилия» (Ципф Г. Поведение человека и Принцип наименьшего усилия).

Следующая формула для расчета вероятности неизвестного слова была предложенаПитер Норвиг в «Корпусе естественных языков», стр. 224:

Приблизительная вероятность появления слова P = 10 / (N * 10 ^ длина слова l)

Мы должны знать, что этогрубая оценкакоторый содержитэвристические параметры, который может быть скорректирован дляязыки кроме английского, Более подробную информацию о соотношении длины слова и частоты слова можно найти в«Частотно-частотная статистика для письменного английского »Миллер, Ньюманн, Фридмани для аспекта разных языков в«Длина слова и частота слова»Штраус, Грзыбек, Альтманн,

Конечно, мы могли бы придумать более сложные вычисления вероятности, например, используяМарковские цепиилиизвестные префиксы и суффиксыоценить вероятность того, что конкретная подстрока будет подлинным словом. Это сделало бы возможнымправильно разделить последовательные неизвестные слова,

Языки

Слово сегментацияСам алгоритм не зависит от языка, Нословарь частоты слов зависит от языка, Чтобы составить словосочетание текста, написанного на определенном языке, необходим частотный словарь для этого конкретного языка.Google Книги n-граммовые данныевключает в себя частоты слов для многих языков.

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

Сегментация слов и исправление орфографии

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

SymSpell.WordSegmentationсочетает в себе сегментацию слов и исправление орфографии,

Во время сегментации генерируется много потенциальных кандидатов в слова - все они должны быть проверены орфографией, а кандидаты в предложения должны быть ранжированы

Это было возможно только при использованииэкстремальная скорость поиска SymSpell:

По параметру длямаксимальное расстояние редактирования, мы можем контролировать, насколько исправление орфографии мы хотим разрешить. При maxEditDistance = 0 мы имеем чистую сегментацию слов без исправления орфографии. При maxEditDistance = 2 мы рассматриваем все слова из словаря в качестве допустимых кандидатов для подстроки, если они находятся в пределахDamerau-Левенштейнарасстояние редактирования ≤2.

Более высокое максимальное расстояние редактирования позволяетисправить больше ошибок, но приходит за счетложноположительные исправленияи более низкая производительность сегментации. Фактический компромисс зависит от качества исходного материала. Это может сделать ошибочный ввод читабельным, но он также может вносить ошибки в идеальный ввод.

Пример 1

input:                 isit
Norvig segment: is it -> no spelling correction
WordSegmentation ed=0: is it -> no spelling correction
WordSegmentation ed=1: visit -> spelling correction
LookupCompound ed=0: i sit -> no spelling correction
LookupCompound ed=1: visit -> spelling correction

Пример 2

input:                 independend
Norvig segment: in depend end -> no spelling correction
WordSegmentation ed=0: in depend end -> no spelling correction
WordSegmentation ed=1: independent -> spelling correction
LookupCompound ed=0: independend -> no spelling correction
LookupCompound ed=1: independent -> spelling correction

Пример 3

input:                 whocouqdn’tread
Norvig segment: who couqdn’t read -> no spelling correction
WordSegmentation ed=0: who co uqdn’t read -> no spelling correction
WordSegmentation ed=1: who couldn’t read -> segmentation+correction
LookupCompound ed=0: whocouqdn’tread -> more than 1 space/token
LookupCompound ed=1: whocouqdn’tread -> more than 1 space/token

* Чтобы сделать алгоритмы сопоставимыми для SymSpell.WordSegmentation и сегментации слов Norvig, то же самоечастотный словарьбыл использован.

WordSegmentation vs. LookupCompound

SymSpellИсправление орфографии и библиотека нечеткого поиска поставляется с методомLookupCompound, Он поддерживает автоматическую коррекцию орфографии составных строк ввода из нескольких слов в трех случаях:

  1. ошибочно вставленный пробел в правильном слове привел к двум неверным терминам
  2. ошибочно пропущенный пробел между двумя правильными словами привел к одному неверному комбинированному термину
  3. множественные условия ввода с / без орфографических ошибок

Ошибки разделения, ошибки конкатенации, ошибки замещения, ошибки транспонирования, ошибки удаления и ошибки вставки могут смешиваться в одном и том же слове.

Итак, в чем же разница междуSymSpell.WordSegmentationа такжеSymSpell.LookupCompoundа на что похоже?

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

Исходный код

Сегментация словбезИсправление орфографии:

WordSegmentationTMа такжеWordSegmentationDPи выпущены наGitHubкакОткрытый источникподЛицензия MIT.

Сегментация словсИсправление орфографии:

WordSegmentationа такжеLookupCompoundявляются частьюSymSpellбиблиотека и выпущена наGitHubкакОткрытый источникподЛицензия MIT,

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map