Почему n-грамм используется в идентификации текста вместо слов?

12

В двух популярных библиотеках идентификации языка, Compact Language Detector 2 для C ++ и Language Detector для Java, обе они использовали (на основе символов) n-граммы для извлечения текстовых функций. Почему пакет слов (одно слово / словарь) не используется, и каковы преимущества и недостатки пакета слов и n-грамм?

Кроме того, каковы некоторые другие применения модели n-грамм в классификации текста?

Ой Похоже, здесь есть похожий вопрос: что касается использования модели Bigram (N-грамма) для построения векторного элемента для текстового документа

Но может ли кто-нибудь дать более полный ответ? Что лучше в случае идентификации языка?

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

dennis97519
источник

Ответы:

20

Я думаю, что самые подробные ответы можно найти в обширной работе Мехьяра Мохри по этой теме. Вот ссылка на один из его слайдов лекции на эту тему: http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

Проблема обнаружения языка состоит в том, что человеческий язык (слова) имеют структуру. Например, на английском языке очень часто буква «u» следует за буквой «q», а в транслитерированном арабском это не так. n-граммы работают, захватывая эту структуру. Таким образом, определенные комбинации букв более вероятны в некоторых языках, чем в других. Это основа классификации n-грамм.

Мешок слов, с другой стороны, зависит от поиска в большом словаре и, по сути, от поиска соответствия шаблону. Здесь есть два основных недостатка: 1) каждый язык должен иметь обширный словарь слов в файле, поиск по которому займет относительно много времени, и 2) мешок слов потерпит неудачу, если ни одно из слов в Учебный комплект входит в комплект тестирования.

Предполагая, что вы используете биграммы (n = 2) и в вашем алфавите 26 букв, тогда для этого алфавита будет только 26 ^ 2 = 676 возможных биграмм, многие из которых никогда не появятся. Следовательно, «профиль» (для использования слов детектора языков) для каждого языка требует очень маленькой базы данных. С другой стороны, классификатору мешков слов понадобится полный словарь для КАЖДОГО языка, чтобы гарантировать, что язык может быть обнаружен на основе того предложения, которое было ему дано.

Короче говоря, каждый языковой профиль может быть быстро создан с относительно небольшим пространством объектов. Интересно, что n-граммы работают только потому, что буквы не нарисованы на языке - это явно рычаг.

Примечание: общее уравнение для числа n-граммов для слов равно l ^ n, где l - количество букв в алфавите.

justanotherbrain
источник
Я предполагаю, что для некоторых близких языков использование списков слов в дополнение к n-граммам поможет. Иногда я видел норвежский текст, обозначаемый как датский. Я сомневаюсь, что n-граммы - хороший способ различить эти два языка.
kjetil b halvorsen
Спасибо за ваш подробный ответ. Однако у меня есть несколько вопросов по этому поводу. Во-первых, не могли бы вы объяснить, «мешок слов потерпит неудачу, если ни одно из слов в обучающем наборе не будет включено в набор для тестирования»? и во-вторых, почему CLD2 использует 4 грамма, что приведет к 456976 записям для английского языка, когда использование словарного метода может привести к примерно половине размера профиля ( oxforddictionaries.com/words/… )?
dennis97519
1
@ dennis97519 re: "bag-of-words ..." Предположим, ваш словарь состоит только из слов {"dog", "cat", "turtle", "animal"} для английского языка и {"perro", "gato" , "tortuga", "animal"} для испанского. Ваш словарь не сможет классифицировать следующее предложение: «Осел - это животное», потому что слово «животное» присутствует в обоих словарях, но ни одно из других слов не существует. Это крайний пример. По 4 грамма: 1) Помните, что вам нужен словарь для каждого языка, 2) n-граммы, как правило, разрежены (более быстрый поиск), и 3) как сказал Дугал, они могут быть представлены всего несколькими байтами.
justanotherbrain
1
@loretoparisi - есть два компромисса: первый - между сложностью модели (большое N = более сложное) и ошибкой обобщения (насколько хорошо вы справляетесь с некоторым набором тестов) - вы не хотите перефразировать. Второй компромисс - вычислительная сложность. Сложность памяти растет экспоненциально с N. Обучение обычно линейно с количеством слов в тексте, поэтому очень длинный текст обычно не является проблемой. Тем не менее, большой текст часто означает больше слов в вашем словаре D. Итак, опять же, сложность памяти равна O (D ^ N). На практике обычно лучше использовать как можно большее значение N в вычислительном отношении.
justanotherbrain
1
@loretoparisi - В продолжение этого, как упоминалось ранее, N-граммы, как правило, редки, но это не всегда так. Если он невелик для вашего конкретного текста, тогда перекрестная проверка с разными N является лучшим подходом для поиска оптимального N (опять же, с вычислительными ограничениями).
justanotherbrain
3

Буквы N-граммы используются вместо слов по нескольким причинам:

1) Список слов, необходимых для данного языка, довольно большой, возможно, 100 000, если вы считаете быстрый, быстрый, быстрый, быстрый, быстрый, быстрый, ... как все разные слова. Для 80 языков требуется примерно в 80 раз больше слов, занимающих много места - 50+ мегабайт.

2) Количество буквенных триграмм для 26-буквенного алфавита составляет 26 ** 3 или около 17 000, а для квадраграмм (N = 4) около 450 000, охватывающих ВСЕ языки, использующие этот алфавит. Аналогичные, но несколько большие цифры для N-граммов в больших алфавитах из 30-100 символов. Для языков CJK с 4000+ букв в ханьском языке достаточно униграмм (N = 1). Для некоторых сценариев Unicode существует только один язык для каждого сценария (греческий, армянский), поэтому буквенные комбинации не нужны (так называемые нильграммы N = 0)

3) Со словами у вас нет никакой информации, когда слово отсутствует в словаре, в то время как с буквами N-грамм у вас часто есть хотя бы несколько полезных буквенных комбинаций в этом слове.

CLD2 использует квадратики для большинства сценариев Unicode (алфавитов), включая латиницу, кириллицу и арабский язык, униграммы для сценариев CJK, нильграммы для других сценариев, а также включает в себя ограниченное количество вполне различимых и довольно распространенных полных слов и пар слов для различения в сложных группах статистически похожих языков, таких как индонезийский и малайский. Буквенные биграммы и триграммы, возможно, полезны для различения небольшого количества языков (около восьми, см. Https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), но бесполезны для различения десятков языков. Таким образом, CLD2 использует квадрограммы, связывая каждую комбинацию букв с тремя наиболее вероятными языками, использующими эту комбинацию. Это позволяет охватить 80 языков с примерно 1,5 МБ таблиц и более 160 языков более примерно с 5 МБ таблиц.

Дик Сайты
источник