Из Википедии, свободной энциклопедии
  (Перенаправлено с Ngrams )
Перейти к навигации Перейти к поиску
Для приложений в вычислительной геномике см. K-mer . Графики использования фраз Google см. В Google Ngram Viewer .
Не путать с энграммой .

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

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

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

Приложения [ править ]

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

Примеры [ править ]

Рисунок 1 Примеры n- диаграмм из различных дисциплин
ПолеЕд. измПоследовательность выборки1-граммовая последовательность2-граммовая последовательность3-граммовая последовательность
Народное названиеуниграммабиграмматриграмма
Порядок результирующей марковской модели012
Секвенирование белковаминокислота… Цис-Гли-Лей-Сер-Трп……, 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]

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 слов. Для языковой идентификации последовательности символов / графем ( например , букв алфавита ) моделируются для разных языков. [4] Для последовательностей символов 3-граммы (иногда называемые «триграммами»), которые могут быть сгенерированы из «доброго утра», - это «goo», «ood», «od», «dm», «mo», «mor». "и так далее, считая пробел в граммах (иногда начало и конец текста моделируются явно, добавляя" _ ⁠_g "," _go "," ng_ "и" g_ ⁠_ "). Для последовательностей слов триграммы (опоясывающий лишай), которые могут быть образованы из «от собаки пахло скунсом»: «# собака», «собака пахла», «собака пахла как», «пахла как», «как скунс »и« скунс # ».

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

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

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

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

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

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

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

Слова вне словарного запаса [ править ]

Основная статья: Статистический машинный перевод

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

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

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

Основная статья: Приблизительное соответствие строк

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

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

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

Другие приложения [ править ]

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

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

  • разрабатывать ядра, которые позволяют алгоритмам машинного обучения , таким как поддержка векторных машин, учиться на строковых данных
  • найти вероятных кандидатов на правильное написание слова с ошибкой
  • улучшить сжатие в алгоритмах сжатия, где небольшая область данных требует n -грамм большей длины
  • оценить вероятность появления данной последовательности слов в тексте на интересующем языке в системах распознавания образов , распознавании речи , OCR ( оптическое распознавание символов ), интеллектуальном распознавании символов ( ICR ), машинном переводе и подобных приложениях
  • улучшить поиск в информационно-поисковых системах, когда есть надежда найти похожие «документы» (термин, для которого обычное значение иногда растягивается, в зависимости от набора данных) с учетом единственного документа запроса и базы данных справочных документов
  • повысить производительность поиска при анализе генетической последовательности, как в семействе программ BLAST
  • определить язык, на котором написан текст, или вид, из которого была взята небольшая последовательность ДНК
  • предсказывать буквы или слова наугад, чтобы создать текст, как в алгоритме диссоциированной прессы .
  • криптоанализ

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

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

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

Компромисс между смещением и дисперсией [ править ]

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

Методы сглаживания [ править ]

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

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

  • Линейная интерполяция (например, взятие средневзвешенного значения униграммы, биграммы и триграммы)
  • Дисконтирование Гуда – Тьюринга
  • Дисконтирование Виттена – Белла
  • Сглаживание Лидстоуна
  • Модель отступления Каца (триграмма)
  • Сглаживание Кнезера – Нея

Скип-грамм [ править ]

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

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

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

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

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

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

Синтаксические n -граммы [ править ]

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

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

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

См. Также [ править ]

  • Словосочетание
  • Скрытая марковская модель
  • n-кортеж
  • Строковое ядро
  • MinHash
  • Извлечение признаков
  • Самая длинная общая проблема с подстрокой

Ссылки [ править ]

  1. ^ Бродер, Андрей З .; Глассман, Стивен С .; Manasse, Mark S .; Цвейг, Джеффри (1997). «Синтаксическая кластеризация сети». Компьютерные сети и системы ISDN . 29 (8): 1157–1166. DOI : 10.1016 / s0169-7552 (97) 00031-7 .
  2. ^ https://www.coursera.org/learn/natural-language-processing/lecture/UnEHs/07-01-noisy-channel-model-8-33
  3. ↑ Алекс Франц и Торстен Бранц (2006). «Все наши N -граммы принадлежат Вам» . Блог Google Research . Проверено 16 декабря 2011 года .
  4. ^ Тед Даннинг (1994). «Статистическая идентификация языка». Технический отчет MCCS . Государственный университет Нью-Мексико: 94–273. CiteSeerX 10.1.1.48.1958 . 
  5. ^ Софер, A (1997). «Категоризация изображений с использованием функций текстуры». Материалы Четвертой Международной конференции по анализу и распознаванию документов . Материалы Четвертой Международной конференции по . 1 . п. 237. CiteSeerX 10.1.1.31.1649 . DOI : 10.1109 / ICDAR.1997.619847 . ISBN  978-0-8186-7898-1. S2CID  16285579 .
  6. ^ Tomović Андрия; Яничич, Предраг; Кешель , Владо (2006). « Классификация на основе n- грамм и неконтролируемая иерархическая кластеризация последовательностей генома». Компьютерные методы и программы в биомедицине . 81 (2): 137–153. DOI : 10.1016 / j.cmpb.2005.11.007 . PMID 16423423 . 
  7. ^ Wołk, K .; Marasek, K .; Глинковский, В. (2015). «Телемедицина как частный случай машинного перевода». Компьютеризированная медицинская визуализация и графика . 46, Пет 2: 249–56. arXiv : 1510.04600 . Bibcode : 2015arXiv151004600W . DOI : 10.1016 / j.compmedimag.2015.09.005 . PMID 26617328 . S2CID 12361426 .  
  8. ^ Волк К., Марасек К. (2014). Статистические системы машинного перевода речи с польского на английский для IWSLT 2014 . Материалы 11-го международного семинара по устному переводу. Озеро Тахо, США.
  9. ^ Хуанг, Сюэдун; Аллева, Филено; Хон, Сяо-вуэнь; Хван, Мэй-юх; Розенфельд, Рональд (1 января 1992 г.). «Система распознавания речи SPHINX-II: обзор». Компьютерная речь и язык . 7 (2): 137–148. CiteSeerX 10.1.1.45.1629 . DOI : 10,1006 / csla.1993.1007 . 
  10. ^ Дэвид Гатри; и другие. (2006). «Более пристальный взгляд на моделирование скип-грамм» (PDF) . Архивировано из оригинального (PDF) 17 мая 2017 года . Проверено 27 апреля 2014 года .
  11. ^ а б Сидоров Григорий; Веласкес, Франсиско; Стамататос, Эфстафиос; Гельбух Александр; Чанона-Эрнандес, Лилиана (2013). «N-граммы на основе синтаксических зависимостей как классификационные признаки» (PDF) . В Батыршине, И .; Мендоса, MG (ред.). Достижения в области вычислительного интеллекта . Конспект лекций по информатике. 7630 . С. 1–11. DOI : 10.1007 / 978-3-642-37798-3_1 . ISBN  978-3-642-37797-6.
  12. ↑ Сидоров, Григорий (2013). «Синтаксические n -граммы на основе зависимостей в автоматическом английском языке на основе правил как исправление грамматики второго языка». Международный журнал компьютерной лингвистики и приложений . 4 (2): 169–188.
  13. ↑ Фигероа, Алехандро; Аткинсон, Джон (2012). «Контекстные языковые модели для ранжирования ответов на вопросы определения естественного языка» . Вычислительный интеллект . 28 (4): 528–548. DOI : 10.1111 / j.1467-8640.2012.00426.x . S2CID 27378409 . 
  14. ^ Сидоров, Григорий; Веласкес, Франсиско; Стамататос, Эфстафиос; Гельбух Александр; Чанона-Эрнандес, Лилиана (2014). «Синтаксические n -граммы как функции машинного обучения для обработки естественного языка». Экспертные системы с приложениями . 41 (3): 853–860. DOI : 10.1016 / j.eswa.2013.08.015 .
  15. ^ Lioma, C .; ван Рейсберген, CJK (2008). "Части речи н-граммы и поиск информации" (PDF) . Французский обзор прикладной лингвистики . XIII (1): 9–22 - через Каирн.

Дальнейшее чтение [ править ]

  • Кристофер Д. Маннинг, Хинрих Шютце, Основы статистической обработки естественного языка , MIT Press: 1999. ISBN 0-262-13360-1 . 
  • Белый, Оуэн; Даннинг, Тед; Саттон, Грейнджер; Адамс, Марк; Вентер, Дж. Крейг; Поля, Крис (1993). «Алгоритм контроля качества для проектов секвенирования ДНК» . Исследования нуклеиновых кислот . 21 (16): 3829–3838. DOI : 10.1093 / NAR / 21.16.3829 . PMC  309901 . PMID  8367301 .
  • Фредерик Дж. Дамерау, Марковские модели и лингвистическая теория . Мутон. Гаага, 1971 год.
  • Фигероа, Алехандро; Аткинсон, Джон (2012). «Контекстные языковые модели для ранжирования ответов на вопросы определения естественного языка» . Вычислительный интеллект . 28 (4): 528–548. DOI : 10.1111 / j.1467-8640.2012.00426.x . S2CID  27378409 .
  • Брокардо, Марсело Луис; Исса Траоре; Шериф Саад; Исаак Вунганг (2013). Проверка авторства коротких сообщений с помощью стилометрии (PDF) . IEEE Intl. Конференция по компьютерным, информационным и телекоммуникационным системам (CITS).

Внешние ссылки [ править ]

  • Google, Google Book п -gram Зритель и Web п -grams базы данных (сентябрь 2006)
  • Сервис Microsoft Web N -grams
  • STATOPERATOR Программа просмотра n-грамм Project Weighted n -gram для каждого домена в рейтинге Alexa Top 1M
  • 1000000 наиболее часто встречающихся 2,3,4,5-граммов из корпуса современного американского английского, состоящего из 425 миллионов слов.
  • Программа просмотра музыки от Peachnote
  • Спецификация стохастических языковых моделей ( n- грамм) (W3C)
  • Заметки Майкла Коллинза о моделях n- грамматического языка
  • OpenRefine: углубленная кластеризация