N-grama

Nos campos de linguística computacional e probabilidade, um n-grama é uma sequência contígua de n itens de uma determinada amostra de texto ou fala. Os itens podem ser fonemas, sílabas, letras, palavras ou pares de bases de acordo com a aplicação. Os n-gramas normalmente são coletados de um corpus de texto ou fala.

Alguns n-gramas frequentemente encontrados em títulos em ingles de publicações sobre a COVID-19.VID-19

Usando prefixos numéricos latinos, um n -grama de tamanho 1 é referido como um "unigrama"; o tamanho 2 é um " bigrama " (ou um "digrama"); o tamanho 3 é um " trigrama ". Os números cardinais são às vezes usados, por exemplo, "quatro grama", "cinco grama" e assim por diante. Em biologia computacional, um polímero ou oligômero de tamanho conhecido é chamado k-mero, em vez de n-grama, com nomes específicos usando prefixos numéricos gregos, como "monômero", "dímero", "trímero", "tetrâmero", "pentamer".

Aplicações

Um modelo de n-grama é um tipo de modelo de linguagem probabilístico para prever o próximo item em tal sequência na forma de um modelo de Markov d. Modelos de n-grama são agora amplamente usados em probabilidade, teoria da comunicação, linguística computacional (por exemplo, processamento estatístico de linguagem natural), biologia computacional (por exemplo, análise de sequência biológica) e compressão de dados. Dois benefícios dos modelos de n-grama (e algoritmos que os usam) são simplicidade e escalabilidade - com n maior, um modelo pode armazenar mais contexto com uma compensação espaço-tempo bem compreendida, permitindo que pequenos experimentos sejam escalonados com eficiência.

Exemplos

Figura 1 exemplos de n -grama em várias disciplinas

Campo	Unidade	Sequência de amostra	Sequência de 1 grama	Sequência de 2 gramas	Sequência de 3 gramas
Nome vernáculo			unigrama	bigrama	trigrama
Ordem do modelo de Markov resultante			0	1	2
Sequenciamento de proteínas	aminoácido	… Cys-Gly-Leu-Ser-Trp…	..., Cys, Gly, Leu, Ser, Trp, ...	..., Cys-Gly, Gly-Leu, Leu-Ser, Ser-Trp, ...	…, Cys-Gly-Leu, Gly-Leu-Ser, Leu-Ser-Trp,…
Sequenciamento de DNA	par de base	... AGCTTCGA ...	..., A, G, C, T, T, C, G, A, ...	..., AG, GC, CT, TT, TC, CG, GA, ...	..., AGC, GCT, CTT, TTC, TCG, CGA, ...
Lingüística computacional	caractere	…to_be_or_not_to_be…	…, t, o, _, b, e, _, o, r, _, n, o, t, _, t, o, _, b, e, …	…, 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,…
Lingüística computacional	palavra	… Ser ou não ser …	…, Ser ou não ser, …	..., ser ou, ou não, não ser,...	..., ser ou não, ou não ser ...

A Figura 1 mostra várias sequências de exemplo e as sequências de 1 grama, 2 gramas e 3 gramas correspondentes.

Aqui estão outros exemplos; esses são 3 gramas e 4 gramas no nível da palavra (e contagens do número de vezes que apareceram) do corpus Google n-gram (em inglês).

3-gramas

• ceramics collectables collectibles (55)
• ceramics collectables fine (130)
• ceramics collected by (52)
• ceramics collectible pottery (50)
• ceramics collectibles cooking (45)

4-gramas

• serve as the incoming (92)
• serve as the incubator (99)
• serve as the independent (794)
• serve as the index (223)
• serve as the indication (72)
• serve as the indicator (120)

Modelos de n-grama

Um modelo de n-grama modela sequências, principalmente linguagens naturais, usando as propriedades estatísticas de n-gramas.

Essa ideia pode ser rastreada até um experimento do trabalho de Claude Shannon em teoria da informação. Shannon fez a pergunta: dada uma sequência de letras (por exemplo, a sequência "para ex"), qual é a probabilidade da próxima letra? A partir dos dados de treinamento, pode-se derivar uma distribuição de probabilidade para a próxima letra, dado um histórico de tamanho $n$ : a = 0,4, b = 0,00001, c = 0, ....; onde as probabilidades de todas as "próximas letras" possíveis somam 1,0.

Mais concisamente, um modelo n -gram prevê $x_{i}$ baseado em $x_{i-(n-1)},\dots ,x_{i-1}$ . Em termos de probabilidade, isso é$P(x_{i}\mid x_{i-(n-1)},\dots ,x_{i-1})$ . Quando usado para modelagem de linguagem, as suposições de independência são feitas de modo que cada palavra dependa apenas do último n - 1 palavras. Este modelo de Markov é usado como uma aproximação da verdadeira linguagem subjacente. Essa suposição é importante porque simplifica enormemente o problema de estimar o modelo de linguagem a partir dos dados. Além disso, devido à natureza aberta da linguagem, é comum agrupar palavras desconhecidas no modelo de linguagem.

Observe que em um modelo de linguagem simples de n- grama , a probabilidade de uma palavra, condicionada a algum número de palavras anteriores (uma palavra em um modelo de bigrama, duas palavras em um modelo de trigrama, etc.) pode ser descrita como seguindo uma distribuição categórica (muitas vezes chamada de forma imprecisa de "distribuição multinomial").

Na prática, as distribuições de probabilidade são suavizadas atribuindo probabilidades diferentes de zero a palavras não vistas ou n-gramas; veja as técnicas de suavização .

Aplicações e considerações

Modelos de n -gram são amplamente usados no processamento estatístico de linguagem natural. No reconhecimento de fala, os fonemas e sequências de fonemas são modelados usando uma distribuição de n-grama. Para análise, as palavras são modeladas de forma que cada n-grama seja composto por n palavras. Para a identificação da linguagem, sequências de caracteres / grafemas (ppor exemplo, letras do alfabeto) são modeladas para diferentes idiomas. Para sequências de caracteres, os trigramas que podem ser gerados a partir de "bom dia" são "bom", "om ", "m d", " di" e "dia", contando o caractere de espaço como um grama (às vezes o início e o fim de um texto são modelados explicitamente, adicionando-se" _ ⁠_b "," _bo ","ia_ "e" a_ ⁠_ "). Para sequências de palavras, os trigramas que podem ser gerados a partir de "o cachorro cheirava a gambá" são "# o cachorro", "o cachorro cheirava", "cachorro cheirava a", "cheirava a gambá", e "a gambá# ".

Os n-gramas também podem ser usados para sequências de palavras ou quase qualquer tipo de dados. Por exemplo, eles têm sido usados para extrair recursos para agrupar grandes conjuntos de imagens terrestres de satélite e para determinar de que parte da Terra veio uma imagem específica. Eles também tiveram muito sucesso como a primeira passagem na busca de sequências genéticas e na identificação das espécies das quais se originaram sequências curtas de DNA.

Os modelos de n-grama são frequentemente criticados porque não possuem qualquer representação explícita da dependência de longo alcance. Isso ocorre porque o único intervalo de dependência explícito é (n - 1) tokens para um modelo de n -grama, e uma vez que as linguagens naturais incorporam muitos casos de dependências ilimitadas (como o movimento-wh), isso significa que um modelo de n -grama não pode, em princípio, distinguir dependências de ruído (já que as correlações de longo alcance caem exponencialmente com a distância para qualquer modelo de Markov). Por esse motivo, os modelos de n-grama não causaram muito impacto na teoria lingüística, onde parte do objetivo explícito é modelar tais dependências.

Outra crítica que foi feita é que os modelos de linguagem de Markov, incluindo os modelos n -gram, não captam explicitamente a distinção desempenho / competência. Isso ocorre porque os modelos n -gram não são projetados para modelar o conhecimento linguístico como tal, e não reivindicam ser (mesmo potencialmente) modelos completos de conhecimento linguístico; em vez disso, eles são usados em aplicações práticas.

Na prática, modelos de n -grama têm se mostrado extremamente eficazes na modelagem de dados de linguagem, que é um componente central em aplicativos modernos de linguagem estatística.

A maioria das aplicações modernas baseadas baseados em n-grama, como parte da tradução automática, não dependem exclusivamente de tais modelos; em vez disso, eles normalmente também incorporam a inferência bayesiana. Os modelos estatísticos modernos são normalmente compostos de duas partes, uma distribuição anterior (probabilidade a priori) que descreve a probabilidade inerente de um resultado possível e uma função de probabilidade usada para avaliar a compatibilidade de um resultado possível com os dados observados. Quando um modelo de linguagem é usado, ele é usado como parte da distribuição anterior (por exemplo, para avaliar a "bondade" inerente de uma possível tradução) e, mesmo assim, muitas vezes não é o único componente dessa distribuição.

Palavras fora do vocabulário

Um problema ao usar modelos de linguagem n-gram são palavras fora do vocabulário (do ingles, OOV, out-of-vocabulary). Eles são encontrados em linguística computacional e processamento de linguagem natural quando os textos de entrada incluem palavras que não estavam presentes em um dicionário ou banco de dados do sistema durante sua preparação. Por padrão, quando um modelo de idioma é estimado, todo o vocabulário observado é usado. Em alguns casos, pode ser necessário estimar o modelo de linguagem com um vocabulário fixo específico. Nesse cenário, os n-gramas no corpus que contêm uma palavra fora do vocabulário são ignorados. As probabilidades de n-gram são suavizadas em todas as palavras do vocabulário, mesmo que não tenham sido observadas.

No entanto, em alguns casos é necessário modelar explicitamente a probabilidade de palavras fora do vocabulário através da introdução de um símbolo especial (por exemplo <unk>). Palavras fora do vocabulário no corpus são efetivamente substituídas por este token especial antes que as contagens de n-gramas sejam feitas. Com esta opção, é possível estimar as probabilidades de transição de n-gramas envolvendo palavras fora do vocabulário.

n-gramas para correspondência aproximada

n-gramas também podem ser usados para correspondência aproximada eficiente. Ao converter uma sequência de itens em um conjunto de n-gramas, ela pode ser embutida em um espaço vetorial, permitindo assim que a sequência seja comparada a outras sequências de maneira eficiente. Por exemplo, se convertermos strings com apenas letras do alfabeto inglês em um único caractere de 3 gramas, obteremos um espaço de $26^{3}$ dimensões (a primeira dimensão mede o número de ocorrências de "aaa", a segunda "aab" e assim por diante para todas as combinações possíveis de três letras). Usando essa representação, perdemos informações sobre a string. Por exemplo, ambas as strings "abc" e "bca" dão origem exatamente aos mesmos 2 gramas "bc" (embora {"ab", "bc"} não seja o mesmo que {"bc", "ca" }). No entanto, sabemos empiricamente que se duas sequências de texto real têm uma representação vetorial semelhante (medida pela similaridade por cosseno), é provável que sejam semelhantes. Outras métricas também foram aplicadas a vetores de n -gramas com resultados variáveis, às vezes melhores. Por exemplo, os escores z já foram usados para comparar documentos examinando quantos desvios-padrão cada n -grama difere de sua ocorrência média em uma grande coleção, ou corpus de texto, de documentos (que formam o vetor de "fundo").

Também é possível adotar uma abordagem em princípios para as estatísticas de n-gramas, modelando similaridade como a probabilidade de que duas strings tenham vindo da mesma fonte diretamente em termos de um problema na inferência bayesiana .

Outras aplicações

Os n-gramas são usados em várias áreas da ciência da computação, linguística computacional e matemática aplicada.

Eles já foram usados para:

• projetar kernels que permitem que algoritmos de aprendizado de máquina, como máquinas de vetores de suporte, aprendam a partir de dados de strings
• encontrar candidatos para a grafia correta de uma palavra com grafia incorreta
• melhorar a compressão em algoritmos de compressão de dados onde uma pequena área de dados requer n-gramas de maior comprimento
• avaliar a probabilidade de uma determinada sequência de palavras aparecer no texto de um idioma de interesse em sistemas de reconhecimento de padrões, reconhecimento de voz, OCR (reconhecimento óptico de caracteres), ICR (Reconhecimento inteligente de caracteres), tradução automática e aplicações semelhantes
• melhorar a sistemas de recuperação de informação quando se espera encontrar "documentos" semelhantes dado um único documento de consulta e um banco de dados de documentos de referência
• melhorar o desempenho de recuperação na análise de sequência genética como na família de programas BLAST
• identificar o idioma de um texto, ou a espécie da qual uma pequena sequência de DNA foi retirada
• criptanálise

Espaço necessário para um n-grama

Considere um n-grama onde as unidades são caracteres e um texto com t caracteres. O espaço que este n -gram requer é exponencial:

$n(t-2(n-1))+\sum _{i=1}^{n-1}2i\qquad n,t\in {\mathcal {N}}$

Uma parábola pode ser ajustada através de cada ponto de dados discretos, obtendo três pares de coordenadas e resolvendo um sistema linear com três variáveis, o que leva à fórmula geral:

$-n^{2}+(t+1)n$

Compensação de viés versus variância

Para escolher um valor para n em um modelo de n -grama, é necessário encontrar o trade-off correto entre a estabilidade da estimativa e sua adequação. Isso significa que o trigrama é uma escolha comum com grandes corpora de treinamento (milhões de palavras), enquanto um bigrama é frequentemente usado com os menores.

Técnicas de suavização

Existem problemas de equilíbrio de peso entre gramas pouco frequentes (por exemplo, um nome próprio que aparace nos dados de treino) e gramas frequentes. Além disso, os itens não vistos nos dados de treinamento terão uma probabilidade de 0,0 caso não haja suavização. Para dados não vistos, mas plausíveis, de uma amostra, pode-se introduzir pseudocontas. As pseudocontas são geralmente motivadas por motivos bayesianos.

Na prática, é necessário suavizar as distribuições de probabilidade atribuindo também probabilidades diferentes de zero a palavras ou n-gramas não- vistas. A razão é que para os modelos derivados diretamente do n -gram, contagens de freqüência têm problemas graves quando confrontado com qualquer n-grams que explicitamente não foram vistas antes - o problema da frequência zero. Vários métodos de suavização são usados, desde a suavização simples "adicionar um" (suavização de Laplace, atribuir uma contagem de 1 a n-gramas invisíveis) até modelos mais sofisticados, como modelos de desconto Good – Turing . Alguns desses métodos são equivalentes a atribuir uma distribuição anterior às probabilidades dos n-gramas e usar a inferência Bayesiana para calcular as probabilidades posteriores de n-gramas resultantes.

• Interpolação linear (por exemplo, tomando a média ponderada do unigrama, bigrama e trigrama)
• Desconto de Good–Turing
• Desconto de Witten-Bell
• Alisamento de Lidstone
• Modelo de recuo de Katz (trigrama)
• Alisamento Kneser-Ney

Skip-gram

No campo da linguística computacional, em particular na modelagem de linguagem, skip-gramas, ou pulogramas, são uma generalização de n-gramas em que os componentes (normalmente palavras) não precisam ser consecutivos, mas podem ter lacunas que são puladas (do ingles, skipped). Eles fornecem uma maneira de superar o problema de dispersão de dados encontrado com a análise convencional de n-gramas.

Formalmente, um n-grama é uma subsequência consecutiva de comprimento n de alguma sequência de tokens w₁ … w_n. Um k -skip-n-gram é uma subseqüência de comprimento-n onde os componentes ocorrem a uma distância de no máximo k entre si.

Por exemplo, no texto de entrada:

a chuva na Espanha cai principalmente na planície

o conjunto de 1-pulo-2-gramas inclui todos os bigramas (2-gramas) e, além das subsequências

a na, chuva Espanha, na cai, Espanha principalmente, cai na, e principalmente planície.

N-gramas sintáticos

Os n-gramas sintáticos são n-gramas definidos por caminhos árvores de dependência sintática, em vez da estrutura linear do texto. Por exemplo, a frase "notícias econômicas têm pouco efeito nos mercados financeiros" pode ser transformada em n-gramas sintáticos seguindo a estrutura de árvore de suas relações de dependência: notícias-econômicas, pouco-efeito, efeito-nos-mercados-financeiros.

Os n-gramas sintáticos destinam-se a refletir a estrutura sintática com mais fidelidade do que os n-gramas lineares e têm muitas das mesmas aplicações, especialmente como recursos em um modelo de espaço vetorial. Os n-gramas sintáticos para certas tarefas fornecem melhores resultados do que o uso de n-gramas padrão, por exemplo, para atribuição de autoria.

Outro tipo de n-gramas sintáticos são n-gramas de classe gramatical, definidos como subseqüências sobrepostas contíguas de comprimento fixo que são extraídas de sequências gramaticais de texto. Os n-gramas de parte da fala têm várias aplicações, mais comumente na recuperação de informações.

Ver também

• Colocação
• Modelo de Markov oculto
• n-tupla
• Kernel string
• MinHash
• Extração de recursos
• Problema comum de substring mais longo

Leitura adicional

• Christopher D. Manning, Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press: 1999.ISBN 0-262-13360-1ISBN 0-262-13360-1 .
• White, Owen; Dunning, Ted; Sutton, Granger; Adams, Mark; Venter, J.Craig; Fields, Chris (1993). «A quality control algorithm for dna sequencing projects». Nucleic Acids Research. 21: 3829–3838. PMC 309901. PMID 8367301. doi:10.1093/nar/21.16.3829 
• Frederick J. Damerau, Markov Models and Linguistic Theory . Mouton. Haia, 1971.
• Figueroa, Alejandro; Atkinson, John (2012). «Contextual Language Models For Ranking Answers To Natural Language Definition Questions». Computational Intelligence. 28: 528–548. doi:10.1111/j.1467-8640.2012.00426.x 
• Brocardo, Marcelo Luiz; Issa Traore; Sherif Saad; Isaac Woungang (2013). Authorship Verification for Short Messages Using Stylometry (PDF). IEEE Intl. Conference on Computer, Information and Telecommunication Systems (CITS) 

Ligações externas

• Google Book do Google n -gram espectador e banco de dados -grams Web n (Setembro de 2006)
• Serviço web n -grams da Microsoft
• STATOPERATOR N-gramas Projeto ponderada n espectador -gram para cada domínio em Alexa Top 1M
• 1.000.000 mais frequentes 2,3,4,5 gramas do Corpus de inglês contemporâneo americano de 425 milhões de palavras
• Visualizador de ngram de música do Peachnote
• Especificação de Modelos de Linguagem Estocástica ( n- Grama) (W3C)
• Notas de Michael Collins sobre modelos de linguagem n- grama
• OpenRefine: Clustering em profundidade