Por que o n-grama é usado na identificação do idioma do texto em vez das palavras?

12

Em duas bibliotecas populares de identificação de idiomas, o Compact Language Detector 2 para C ++ e o detector de idiomas para java, ambos usavam n-gramas (baseados em caracteres) para extrair recursos de texto. Por que um pacote de palavras (única palavra / dicionário) não é usado e qual é a vantagem e a desvantagem do pacote de palavras e n gramas?

Além disso, quais são alguns outros usos do modelo n-gramas na classificação de texto?

Oh oops. Parece que existe uma pergunta semelhante aqui: Quanto ao uso do modelo bigram (N-gram) para criar vetor de recurso para documento de texto

Mas alguém pode dar uma resposta mais abrangente? Qual é o melhor no caso da identificação de idioma?

(Espero que o significado de n-gramas e palavras-chave esteja correto, haha, se não, por favor, me ajude com isso.)

dennis97519
fonte

Respostas:

20

Acho que as respostas mais detalhadas podem ser encontradas no extenso trabalho de Mehryar Mohri sobre o assunto. Aqui está um link para um de seus slides de palestras sobre o tema: http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

O problema da detecção de linguagem é que a linguagem humana (palavras) possui estrutura. Por exemplo, em inglês, é muito comum a letra 'u' seguir a letra 'q', embora esse não seja o caso em árabe transliterado. n-gramas funcionam capturando essa estrutura. Assim, certas combinações de letras são mais prováveis ​​em alguns idiomas do que em outros. Esta é a base da classificação n-grama.

As palavras-chave, por outro lado, dependem da pesquisa em um grande dicionário e, essencialmente, da correspondência de modelos. Existem duas desvantagens principais aqui: 1) cada idioma precisaria ter um extenso dicionário de palavras em arquivo, o que levaria um tempo relativamente longo para pesquisar e 2) palavras-chave falharão se nenhuma das palavras em o conjunto de treinamento está incluído no conjunto de testes.

Supondo que você esteja usando bigrams (n = 2) e existindo 26 letras em seu alfabeto, existem apenas 26 ^ 2 = 676 possíveis bigrams para esse alfabeto, muitos dos quais nunca ocorrerão. Portanto, o "perfil" (para usar as palavras do detector de idioma) para cada idioma precisa de um banco de dados muito pequeno. Um classificador de saco de palavras, por outro lado, precisaria de um dicionário completo para CADA idioma, a fim de garantir que um idioma pudesse ser detectado com base em qualquer sentença que fosse dada.

Em resumo, cada perfil de idioma pode ser gerado rapidamente com um espaço de recursos relativamente pequeno. Curiosamente, n-gramas funcionam apenas porque as letras não são desenhadas iid em um idioma - isso é explicitamente alavancado.

Nota: a equação geral para o número de n-gramas para as palavras é l ^ n onde l é o número de letras no alfabeto.

justanotherbrain
fonte
Eu acho que para algumas línguas próximas, o uso de listas de palavras além de n-gramas ajudaria. Às vezes, tenho visto texto norueguês classificado como dinamarquês. Duvido que n-gramas seja uma boa maneira de distinguir esses dois idiomas.
precisa saber é o seguinte
Obrigado pela sua resposta detalhada. No entanto, tenho algumas perguntas sobre isso. Em primeiro lugar, você poderia explicar 'o saco de palavras falhará se nenhuma das palavras do conjunto de treinamento estiver incluída no conjunto de testes'? e segundo, por que o CLD2 está usando 4 gramas, o que resultará em 456976 entradas para o idioma inglês, quando o uso de um método de dicionário pode trazer cerca da metade do tamanho do perfil ( oxforddictionaries.com/words/… )?
precisa saber é o seguinte
1
@ dennis97519 re: "bag-of-words ..." Suponha que seu dicionário consista apenas nas palavras {"cachorro", "gato", "tartaruga", "animal"} para inglês e {"perro", "gato" , "tortuga", "animal"} para espanhol. Seu dicionário não conseguiria classificar a seguinte frase: "Um burro é um animal" porque a palavra "animal" aparece nos dois dicionários, mas nenhuma das outras palavras existe. Este é um exemplo extremo. Re 4 gramas: 1) Lembre-se de que você precisa de um dicionário para cada idioma, 2) n-gramas tendem a ser esparsos (pesquisa mais rápida) e 3), como Dougal disse, eles podem ser representados em apenas alguns bytes.
Justinotherbrain
1
@loretoparisi - Existem duas compensações: a primeira é entre a complexidade do modelo (grande N = mais complexo) e o erro de generalização (quão bem você se sai em algum conjunto de testes) - você não deseja se superestimar. O segundo compromisso é a complexidade computacional. A complexidade da memória aumenta exponencialmente com N. O treinamento é tipicamente linear com o número de palavras no texto, portanto, ter um texto muito longo geralmente não é um problema. Dito isto, texto grande geralmente significa mais palavras em seu dicionário D. Então, novamente, a complexidade da memória é O (D ^ N). Na prática, geralmente é melhor usar um N tão grande quanto computacionalmente possível.
justanotherbrain
1
@loretoparisi - Continuando com isso, como mencionado anteriormente, os N-gramas tendem a ser esparsos, mas isso nem sempre é verdade. Se for escasso para o seu texto em particular, a validação cruzada com N diferente é a melhor abordagem para encontrar N ideal (novamente, com restrições computacionais).
Justinotherbrain 29/11
3

A letra N-gramas é usada em vez de palavras por vários motivos:

1) A lista de palavras necessárias para um determinado idioma é bastante grande, talvez 100.000, se você considerar rápido, mais rápido, mais rápido, mais rápido, mais rápido, mais rápido, mais rápido ... como todas as palavras diferentes. Para 80 idiomas, você precisa de cerca de 80x mais palavras, ocupando muito espaço - mais de 50 megabytes.

2) O número de trigramas de letras para um alfabeto de 26 letras é 26 ** 3 ou cerca de 17.000 e, para quadrogramas (N = 4), cerca de 450.000 cobrindo TODOS os idiomas usando esse alfabeto. Números semelhantes, mas um pouco maiores, para N-gramas em alfabetos maiores de 30 a 100 caracteres. Para os idiomas CJK com mais de 4000 letras no script Han, os unigramas (N = 1) são suficientes. Para alguns scripts Unicode, há apenas um idioma por script (grego, armênio), portanto, nenhuma combinação de letras é necessária (os chamados nil-gramas N = 0)

3) Com palavras, você não tem nenhuma informação quando uma palavra que não está no dicionário, enquanto que com a letra N-gramas você costuma ter pelo menos algumas combinações úteis de letras nessa palavra.

O CLD2 usa quadgrams para a maioria dos scripts Unicode (alfabetos), incluindo unigramas em latim, cirílico e árabe, para os scripts CJK, nilgramas para outros scripts e também inclui um número limitado de palavras e pares de palavras completas bastante distintas e bastante comuns para distinguir em grupos difíceis de idiomas estatisticamente semelhantes, como indonésio e malaio. Os bigrams e trigramas de letras talvez sejam úteis para distinguir entre um pequeno número de idiomas (cerca de oito, consulte https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), mas são inúteis para distinguir dezenas de idiomas. Assim, o CLD2 usa quadramas, associando a cada combinação de letras os três principais idiomas mais prováveis ​​usando essa combinação. Isso permite cobrir 80 idiomas com cerca de 1,5 MB de tabelas e 160 idiomas com mais detalhes, com cerca de 5 MB de tabelas.

Dick Sites
fonte