n -грамма - n-gram

Некоторые n-граммы часто встречаются в заголовках публикаций о коронавирусной болезни 2019 года .

В области компьютерной лингвистики и вероятности , п -gram (иногда также называемый Q-грамма ) представляет собой непрерывную последовательность п элементов из данного образца текста или речи. Элементами могут быть фонемы , слоги , буквы , слова или пары оснований в зависимости от приложения. П -grams обычно собирают из текста или речевого корпуса . Когда элементы представляют собой слова, n -граммы также могут называться черепицей .

Используя латинские числовые префиксы , n -грамма размера 1 называется «униграммой»; размер 2 - « биграмма » (или, реже, «биграмма»); размер 3 - это « триграмма ». Иногда используются английские количественные числа , например, «четыре грамма», «пять граммов» и так далее. В вычислительной биологии полимер или олигомер известного размера называется k -мером вместо n -граммы, с конкретными названиями с использованием греческих числовых префиксов, таких как «мономер», «димер», «тример», «тетрамер», «пентамер» и т. д. или английские количественные числа, «один-мер», «два-мер», «три-мер» и т. д.

Приложения

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

Примеры

Рисунок 1 n -граммы, примеры из различных дисциплин
Поле Ед. изм Последовательность выборки 1-граммовая последовательность 2-граммовая последовательность 3-граммовая последовательность
Народное название униграмма биграмма триграмма
Порядок результирующей марковской модели 0 1 2
Секвенирование белков аминокислота … Цис-Гли-Лей-Сер-Трп… …, Cys, Gly, Leu, Ser, Trp,… …, Cys-Gly, Gly-Leu, Leu-Ser, Ser-Trp,… …, Cys-Gly-Leu, Gly-Leu-Ser, Leu-Ser-Trp,…
Секвенирование ДНК базовая пара … AGCTTCGA… …, A, G, C, T, T, C, G, A,… …, AG, GC, CT, TT, TC, CG, GA,… …, AGC, GCT, CTT, TTC, TCG, CGA,…
Компьютерная лингвистика персонаж …быть или не быть… …, быть или не быть, … …, To, o_, _b, be, e_, _o, or, r_, _n, no, ot, t_, _t, to, o_, _b, be,… …, To_, o_b, _be, be_, e_o, _or, or_, r_n, _no, not, ot_, t_t, _to, to_, ​​o_b, _be,…
Компьютерная лингвистика слово … быть или не быть … …, быть или не быть, … …, Быть, быть или, или нет, не быть, быть,… … Быть или, быть или не быть, или не быть, не быть,…

На рисунке 1 показаны несколько примеров последовательностей и соответствующие последовательности 1, 2 и 3 грамма.

Вот еще примеры; это 3-граммы и 4-граммы на уровне слов (и количество их появлений) из корпуса n -граммов Google .

3 грамма

  • керамика коллекционные предметы коллекционирования (55)
  • коллекционные предметы из керамики (130)
  • керамика собрана (52)
  • керамика коллекционная керамика (50)
  • керамика, предметы коллекционирования, кулинария (45)

4 грамма

  • служить входящим (92)
  • служить инкубатором (99)
  • служить независимым (794)
  • служить указателем (223)
  • служат индикатором (72)
  • служат индикатором (120)

n -граммные модели

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

Эта идея восходит к эксперименту Клода Шеннона в области теории информации . Шеннон задал вопрос: учитывая последовательность букв (например, последовательность «для бывшего»), какова вероятность появления следующей буквы? Из обучающих данных можно получить распределение вероятностей для следующей буквы с учетом истории размера : a = 0,4, b = 0,00001, c = 0, ....; где сумма вероятностей всех возможных "следующих букв" равна 1,0.

Говоря более кратко, модель n -граммы предсказывает на основе . С точки зрения вероятности это так . При использовании для языкового моделирования принимаются допущения о независимости, так что каждое слово зависит только от последних n  - 1 слова. Эта марковская модель используется как приближение к истинному базовому языку. Это предположение важно, поскольку оно значительно упрощает задачу оценки языковой модели по данным. Кроме того, из-за открытой природы языка слова, неизвестные языковой модели, обычно группируются вместе.

Обратите внимание , что в простой п языковой модели -gram, вероятность слова, обусловлено некоторым количество предыдущих слов (одно слова в модели Биграммной, два слова в модели триграммы и т.д.) может быть описана как после категорического распределения (часто неточно называют « полиномиальным распределением »).

На практике распределения вероятностей сглаживаются путем присвоения ненулевых вероятностей невидимым словам или n -граммам; см. техники сглаживания .

Приложения и соображения

Модели n -грамм широко используются в статистической обработке естественного языка . В распознавания речи , фонемы и последовательность фонем моделируются с использованием п распределения -gram. Для синтаксического анализа слова моделируются таким образом, что каждая n -грамма состоит из n слов. Для языковой идентификации последовательности символов / графем ( например , букв алфавита ) моделируются для разных языков. Для последовательностей символов 3-граммы (иногда называемые «триграммами»), которые могут быть сгенерированы из «доброго утра», - это «goo», «ood», «od», «dm», «mo», «mor». "и так далее, считая пробел в граммах (иногда начало и конец текста моделируются явно, добавляя" _ ⁠_g "," _go "," ng_ "и" g_ ⁠_ "). Для последовательностей слов триграммы (опоясывающий лишай), которые могут быть образованы из «от собаки пахло скунсом»: «# собака», «собака пахла», «собака пахла как», «пахла как», «как скунс »и« скунс # ».

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

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

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

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

На практике было показано , что модели n -грамм чрезвычайно эффективны при моделировании языковых данных, которые являются основным компонентом современных статистических языковых приложений.

Большинство современных приложений, которые полагаются на модели на основе n- граммов, такие как приложения машинного перевода , не полагаются исключительно на такие модели; вместо этого они обычно также включают байесовский вывод . Современные статистические модели обычно состоят из двух частей: априорного распределения, описывающего внутреннюю вероятность возможного результата, и функции правдоподобия, используемой для оценки совместимости возможного результата с наблюдаемыми данными. Когда используется языковая модель, она используется как часть предшествующего распределения (например, для оценки присущей «добротности» возможного перевода), и даже в этом случае она часто не единственный компонент в этом распределении.

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

Слова вне словарного запаса

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

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

n -граммы для приблизительного соответствия

n -граммы также могут использоваться для эффективного приблизительного сопоставления. Преобразуя последовательность элементов в набор n -грамм, она может быть встроена в векторное пространство , что позволяет эффективно сравнивать последовательность с другими последовательностями. Например, если мы преобразуем строки, состоящие только из букв английского алфавита, в односимвольные 3-граммы, мы получим -мерное пространство (первое измерение измеряет количество вхождений «ааа», второе «ааб» и т. Д. для всех возможных комбинаций из трех букв). Используя это представление, мы теряем информацию о строке. Например, обе строки «abc» и «bca» дают одно и то же 2-граммовое «bc» (хотя {«ab», «bc»} явно не то же самое, что {«bc», «ca» }). Однако мы эмпирически знаем, что если две строки реального текста имеют одинаковое векторное представление (измеренное косинусным расстоянием ), то они, вероятно, будут похожи. Другие показатели также применялись к векторам n -грамм с разными, иногда лучшими результатами. Например, z-значения использовались для сравнения документов путем изучения того, на сколько стандартных отклонений каждая n -грамма отличается от своего среднего вхождения в большой коллекции или текстовом корпусе документов (которые образуют «фоновый» вектор). В случае небольшого подсчета g-оценка (также известная как g-тест ) может дать лучшие результаты для сравнения альтернативных моделей.

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

Поиск по n- диаграммам также может использоваться для обнаружения плагиата .

Другие приложения

n -граммы находят применение в нескольких областях компьютерных наук, компьютерной лингвистики и прикладной математики.

Они привыкли:

Место, необходимое для n -граммы

Рассмотрим n -грамму, где единицами измерения являются символы, и текст из t символов, где . Есть всего строк, где каждая строка требует единиц пространства. Таким образом, общее пространство, необходимое для этой n -граммы, составляет , что упрощается до:

Компромисс между смещением и дисперсией

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

Техники сглаживания

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

На практике необходимо сглаживать распределения вероятностей, также присваивая ненулевые вероятности невидимым словам или n -граммам. Причина в том, что модели, полученные непосредственно из подсчетов частот n -грамм, имеют серьезные проблемы при столкновении с любыми n -граммами, которые явно не наблюдались раньше - проблема нулевой частоты . Используются различные методы сглаживания, от простого сглаживания «прибавляемая единица» (Лапласа) (присвоение счету 1 невидимым n -граммам; см. Правило последовательности ) до более сложных моделей, таких как модели дисконтирования Гуда – Тьюринга или модели отсрочки. . Некоторые из этих методов эквивалентны назначению априорного распределения вероятностям n -грамм и использованию байесовского вывода для вычисления результирующих апостериорных вероятностей n -грамм. Однако более сложные модели сглаживания обычно выводились не таким образом, а на основании независимых соображений.

Скип-грамм

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

Формально n -грамма - это последовательная подпоследовательность длины n некоторой последовательности лексем w 1w n . A K -skip- п -gram является длина- п подпоследовательности , где компоненты происходят на расстоянии не более к друг от друга.

Например, во вводимом тексте:

дождь в Испании падает в основном на равнину

набор 1-скип-2-грамм включает все биграммы (2-граммы), а также подпоследовательности

в , дождь Испания , падениям , Испания в основном , приходится на , в основном , и на равнине .

Синтаксические n -граммы

Синтаксические n -граммы - это n -граммы, определяемые путями в синтаксической зависимости или составляющими деревьями, а не линейной структурой текста. Например, предложение «экономические новости мало влияют на финансовые рынки» можно преобразовать в синтаксические n -граммы, следуя древовидной структуре их отношений зависимости : новости-экономические, эффект-незначительный, влияние-на-рынки-финансы.

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

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

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки