Раньше всегда читал ультрасовременные статьи.Для реальной реализации задач промышленного уровня мне все же нужен прочный хардкорный фундамент.Наша компания выбрала HANLP в качестве компонента словесной сегментации.Только в процессе его использования я ощутил слабость мой фундамент. Недавно я решил хорошо позаботиться о сегментации слов. Давайте разберемся с лежащим в основе алгоритмом.
1. Введение
Основные задачи НЛП можно условно разделить на лексический анализ, синтаксический анализ и семантический анализ от простого к сложному. Сегментация слов — это самая основная задача лексического анализа (включая маркировку частей речи и распознавание именованных сущностей), которую можно назвать одновременно простой и сложной. Это просто, потому что алгоритм исследования сегментации слов очень зрел, и большинство показателей точности могут достигать более 95%, это сложно, потому что трудно сделать прорыв в оставшихся 5%, в основном из-за трех моментов:
- Детализация. Различные приложения предъявляют разные требования к степени детализации. Например, «iPhone» может состоять из одного или двух слов.
- Неоднозначность, например: «Оставь людей на черный день, но не меня».
- Незарегистрированные слова, такие как «skrrr», «call» и другие появляющиеся слова
Однако в реальных приложениях вышеуказанные трудности часто приводят к плохому эффекту сегментации слов, что, в свою очередь, сказывается на последующих задачах. Для детской обуви, которая преследует производительность алгоритма, они должны не только иметь возможность настраивать пакет сегментации слов, но также иметь определенное представление об этих базовых технологиях и иметь возможность настраивать устройство сегментации слов при выполнении реальных промышленных приложений. Эта статья не фокусируется на представлении определенного достижения SOTA, но представляет часто используемые алгоритмы сегментации слов (не только машинное обучение или нейронные сети, но также динамическое программирование и т. д.) и их основные идеи.
2. Алгоритм сегментации слов
Я думаю, что алгоритм сегментации слов в основном делится на два типа в соответствии с его основной идеей.Первый - сегментация слов на основе словаря.Сначала предложение делится на слова в соответствии со словарем, а затем находится наилучшее сочетание слов; вторая - сегментация слов на основе слов.То есть, чтобы сформировать слова из слов, сначала разделить предложения на слова, а затем объединить слова в слова, чтобы найти оптимальную стратегию сегментации.В то же время он также может быть преобразован в последовательность проблема с маркировкой. В конечном итоге оба вышеперечисленных метода сводятся к задаче поиска кратчайшего пути на графе или графе вероятностей. Дальше будет "То, что он сказал, действительно имеет смысл«Это предложение является примером, объясняющим основные идеи различных алгоритмов сегментации слов.
2.1 Сегментация слов на основе словаря
2.1.1 Алгоритм сегментации максимального совпадающего слова
Чтобы найти наилучшую комбинацию для максимальной сегментации совпадающих слов, нужно объединить вместе самые длинные совпадающие слова. Основная идея состоит в том, чтобы сначала построить словарь в виде дерева Trie, также известного как дерево словарей, как показано ниже:
Древовидное дерево состоит из общих префиксов слов, что уменьшает объем памяти и повышает эффективность поиска. Причастие с максимальным совпадением соответствует предложению с деревом Trie и начинает поиск со следующего слова, когда совпадает корневой узел. Например, «вперед» (слева направо) соответствует «то, что он сказал, верно», а результат — «он сказал/правда/правда/разумно». Если выполняется обратное максимальное сопоставление, это «он/говорит/делает/делает/не имеет значения».
Видно, что хотя словарная сегментация может сегментировать предложения за время O(n), эффект очень слабый, и этот метод практически не используется в практических ситуациях.
2.1.2 Алгоритм сегментации слова кратчайшего пути
Алгоритм сегментации слов кратчайшего пути сначала сопоставляет все слова в предложении, чтобы сформировать граф слов (направленный ациклический граф DAG), а затем находит кратчайший путь от начальной точки до конечной точки как лучший метод комбинации, ссылаясь на «Statistical Natural Language». Обработка» Рисунок в:
Каждое ребро в графе имеет вес 1.
При решении задачи о кратчайшем пути графа DAG всегда используется свойство: то есть кратчайший путь между двумя точками также включает в себя кратчайший путь между другими вершинами пути. Например, S->A->B->E — кратчайший путь из S в E, тогда S->A->B должен быть кратчайшим путем из S в B, иначе найдется точка C такая, что d (S->C->B)
- алгоритм сегментации слов кратчайшего пути
Найдите кратчайший путь на основе алгоритма Дейкстры. Этот алгоритм применим ко всем взвешенным ориентированным графам, находит кратчайший путь от исходного узла ко всем другим узлам и может получить глобальное оптимальное решение. Дейкстра — это, по сути, жадный алгоритм: на каждом шаге он переходит к узлу с кратчайшим текущим путем и рекурсивно обновляет расстояние от исходного узла до других узлов. Однако применительно к проблеме сегментации слов, поскольку граф слов является взвешенным ориентированным ациклическим графом, глобальное оптимальное решение не может быть получено. Однако для текущей задачи результат вычисления алгоритма Дейкстры таков: «он/говорит/правда/действительно». Можно видеть, что алгоритм сегментации слов кратчайшего пути может удовлетворить некоторые требования сегментации слов.
2. Алгоритм сегментации N-кратчайших слов пути
Сегментация N-кратчайших путей является расширением алгоритма Дейкстры, который сохраняет N кратчайших путей на каждом шаге, записывает предшественников текущих узлов на этих путях и выполняет возврат для получения кратчайшего пути, когда наконец будет получено оптимальное решение. Точность этого метода лучше, чем у алгоритма Дейкстры, но он больше по временной и пространственной сложности.
2.1.3 Алгоритм сегментации слов на основе n-граммной модели
В предыдущем словесном графе все веса ребер равны 1. В действительности, однако, частота/вероятность часто используемых слов определенно выше, чем у редких слов. Следовательно, задача решения кратчайшего пути графа слов может быть преобразована в задачу решения пути максимальной вероятности, то есть результатом сегментации слов является «наиболее вероятное сочетание слов». Для расчета вероятности появления слова недостаточно только словаря, требуется также достаточный корпус. Таким образом, задача сегментации слов превратилась из простого «алгоритма» в «моделирование», то есть использование статистических методов в сочетании с анализом больших данных для моделирования «языка».
Целью языковой модели является построение вероятности p(s) появления предложения.Согласно формуле условной вероятности мы знаем:
Чтобы действительно рассчитать вероятность того, что «то, что он сказал, правда», мы должны вычислить все вышеупомянутые формы, такие какВероятность n=1,...,6 слишком велика для расчета, поэтому мы приблизительно думаем, что:
в,
для слова или слова. Мы называем приведенную выше модель 2-граммовой моделью. Точно так же, если подсчитывается только частота слов, это модель языка униграмм. Из-за ограничения объема вычислений n обычно принимается равным 3 в практических приложениях.
Мы применяем распределение вероятностей, рассчитанное с помощью языковой модели, основанной на словах, к графу слов, и мы можем получитькарта вероятностей:
Используйте алгоритм из 2.1.2 для решения пути максимальной вероятности графа слов, после чего можно получить результат сегментации слов.
2.2 Сегментация на основе слов
В отличие от сегментации слов на основе словаря, сегментация слов на основе слов не выполняет предварительное сопоставление слов в предложениях, а рассматривает сегментацию слов как проблему маркировки последовательности и помечает слово как B (начало), I (внутри), O ( Снаружи) , E(Конец), S(Один). Следовательно, это также можно рассматривать как проблему классификации каждого символа.Вход — это функция, состоящая из каждого символа и его предшествующих и последующих символов, а выход — классификационный знак. Для задач классификации для их решения могут использоваться методы статистического машинного обучения или нейронных сетей.
Статистические методы машинного обучения абстрагируют проблему с помощью ряда алгоритмов, а затем получают модель, а затем используют полученную модель для решения аналогичных задач. Вы также можете думать о модели как о функции, ввести X и получить f(X)=Y. Кроме того, модели обычно делятся на две категории в машинном обучении: генеративные модели и дискриминационные модели, Существенная разница между ними заключается в генеративной связи между X и Y. Генеративная модель моделирует совместную вероятность P(X,Y) с предположением, что «выход Y генерирует вход X в соответствии с определенным правилом»; дискриминантная модель считает, что Y определяется X, и напрямую определяет апостериорную вероятность Модель P(Y|X). У обоих есть свои плюсы и минусы: генеративные модели более четко описывают взаимосвязь переменных, тогда как дискриминационные модели легче построить и изучить. Ниже приводится краткое введение в несколько методов аннотирования последовательностей.
2.2.1 Алгоритм сегментации слова генеративной модели
Генеративные модели в основном включают модель n-грамм, скрытую марковскую модель HMM, наивную байесовскую классификацию и т. д. Модель n-грамм и модель HMM широко используются при сегментации слов. Если узлы в 2.1.3 изменить со слов на слова, сегментация слов может быть выполнена на основе n-граммной модели слов, но эффект от этого метода не так хорош, как на основе слов.
Модель HMM — это широко используемая модель сегментации слов.И токенизатор jieba на основе Python, и токенизатор HanLP на основе Java используют HMM. Следует отметить, что график вероятностей, созданный этой моделью, не совпадает с графом DAG выше, потому что узел имеет вероятность наблюдения, поэтому он больше не может быть решен с помощью вышеуказанного алгоритма, но алгоритм Витерби следует использовать для решить путь с максимальной вероятностью.
2.2.2 Алгоритм сегментации слов дискриминантной модели
Дискриминантные модели в основном включают перцептроны, машины опорных векторов SVM, условные случайные поля CRF и модели максимальной энтропии. Модели персептрона и модели CRF, обычно используемые при сегментации слов:
- Алгоритм сегментации среднего персептрона
Персептрон представляет собой простую линейную модель бинарной классификации, которая делит выборки в пространстве признаков (входном пространстве) на положительные и отрицательные категории путем построения гиперплоскости. Благодаря композиции персептроны также могут решать проблемы множественной классификации. Однако, поскольку все веса модели обновляются на каждой итерации, неправильно классифицированные выборки будут иметь большое влияние, поэтому метод усреднения используется для усреднения обновленных весов после обработки части выборок.
2. Алгоритм сегментации слов CRF
Можно сказать, что CRF является наиболее часто используемым алгоритмом для сегментации слов, маркировки частей речи и распознавания сущностей.Он обладает хорошей способностью идентифицировать незарегистрированные слова, но имеет большие накладные расходы.
2.2.3 Алгоритм сегментации слов нейронной сети
В настоящее время для задач маркировки последовательностей признано, что лучшей моделью является BiLSTM+CRF. Структура представлена на рисунке:
Используя двунаправленную циклическую нейронную сеть BiLSTM, по сравнению с другими моделями, описанными выше, она может лучше кодировать контекстную информацию, такую как текущее слово, и, наконец, добавить слой CRF.Ядро заключается в использовании алгоритма Витерби для декодирования для получения глобального оптимального Решение Избегайте B, Появление результата маркировки S,E.
3. Структура данных в алгоритме сегментации слов
В предыдущей статье в основном говорилось об алгоритмах и моделях, используемых в задачах сегментации слов, но в практических промышленных приложениях одних только алгоритмов недостаточно, в помощь также нужны эффективные структуры данных.
3.1 Словарь
В китайском языке насчитывается более 7 000 общеупотребительных слов и более 56 000 общеупотребительных слов. Хотя загрузить эти данные в память несложно, сложно выполнять операции с высокой степенью параллелизма на миллисекундном уровне, что требует хитроумных структур данных и методов хранения. Упомянутое выше дерево Trie может завершить сопоставление одного шаблона только за время O (n).После определения «истина» оно достигает узла пары дерева Trie, и указатель предложения затем указывает на «true», а затем распознает « правда", но не может распознать "истину". Действительно" слово. Если вы хотите выполнить сопоставление нескольких шаблонов за время O (n) и построить граф слов, вам нужно использовать алгоритм Ахо-Корасика для предварительной обработки строки шаблона в автомат с конечным состоянием.Например, строка шаблона - он/ она / его / ее, а текст - «ашеры». Построенный автомат показан на рисунке:
Таким образом, при первом достижении конечного узла 5 следующее сопоставление может начаться непосредственно с узла 2, и все строки шаблона могут быть идентифицированы за один проход.
Для хранения структур данных обычно можно использовать связанные списки или массивы, оба из которых имеют свои преимущества в сложности операций поиска, вставки и удаления. В высокопроизводительном токенизаторе HanLP на основе Java автор использует двойные массивы для полного хранения Trie-деревьев и автоматов.
3.2 Карта слов
Как общая структура данных, графики обычно хранятся двумя способами:
- матрица смежности
Матрица смежности использует нижний индекс массива для представления узла, а значение представляет вес ребра, то есть d[i][j]=v означает, что вес ребра между узлами i и j равен v. Как показано ниже:
Хранение графов в матрицах занимает много места и не рекомендуется при хранении разреженных графов.
2. Список смежности
Список смежности устанавливает односвязный список для каждого узла в графе, что может значительно сэкономить место для хранения разреженных графов. Узел в i-м односвязном списке представляет ребро, присоединенное к вершине i, как показано на следующем рисунке:
В практических приложениях, особенно когда алгоритм Витерби используется для нахождения оптимального пути, поскольку обход графа осуществляется в соответствии со стратегией обхода в ширину, для хранения графа лучше использовать список смежности, чтобы облегчить доступ ко всем узлы под узлом.
4. Резюме
Как одна из основных задач НЛП, сегментация слов одновременно проста и важна.Во многих случаях ошибки алгоритмов верхнего уровня вызваны результатами сегментации слов. Поэтому разработчику алгоритма базовой реализации необходимо не только глубоко понимать алгоритм сегментации слов, но и знать, как его эффективно реализовать. Для разработчиков алгоритмов приложений верхнего уровня при фактической сегментации слов вышеперечисленные алгоритмы необходимо применять выборочно в соответствии с бизнес-сценариями.Например, когда поисковая система анализирует содержимое крупномасштабных веб-страниц, скорость сегментации слов больше, чем точность.Из-за коротких предложений требования к точности для сегментации слов больше, чем скорость.