N gram

Bir n- gram , belirli bir diziden oluşturulan n öğenin bir alt dizisidir. Fikir, Claude Shannon'ın bilgi teorisindeki çalışmasından geliyor gibi görünüyor . Onun fikri, belirli bir harf dizisinden (örneğin " örneğin ") bir sonraki harfin görünüşünün olabilirlik fonksiyonunu elde etmenin mümkün olduğuydu. Bir öğrenme külliyatından , büyüklük geçmişi olan bir sonraki harf için bir olasılık dağılımı oluşturmak kolaydır . Bu modelleme aslında bir sonraki harfin tahmini için yalnızca son gözlemlerin kullanıldığı bir Markov düzen modeline karşılık gelir . Böylece bir bigram, 2. dereceden bir Markov modelidir. $olumsuzluk$ $olumsuzluk$ $olumsuzluk$

Örneğin , Fransızcada en sık kullanılan bigram , "de" makalesinde olduğu gibi "de"dir, ancak " de main", "mon de " veya "mo de" kelimelerinde olduğu gibi. Olarak doğal dil işleme, kelimeler arasında olup harflerin belirlemek için, N-gram söz yaygındır.

Örnek

“Örneğin” (kısa) korpustan şunu elde ederiz:

Geçmiş yok (unigram):

p: 10 harf üzerinde 2 tekrar = 1/5;
e: 10 harfte 3 tekrar = 3/10;
x: 10 harften 1'i = 1/10;

... Olasılıkların toplamı mutlaka 1'e eşittir.

1 boyutun tarihi (mektubu ve halefi olarak kabul ediyoruz):

pa: 9 çiftten 1'i = 1/9;
pl: 9 çiftten 1 oluşum = 1/9;
pe: 9 çiftten 0 oluşum = 0;

... Olasılıkların toplamı her zaman zorunlu olarak 1'e eşittir.

Bir alt diziden, aşağıdaki dizinin olasılığını bilmemizi sağlayan koşullu olasılıklar elde ederiz. Örneğimizde, bir eleman görünümü olasılığı a elemanı bilerek p göründü. ${\ görüntü stili P (a | p) = 1/2}$

N-gram kullanımı

N-gramlar, otomatik doğal dil işlemede ve aynı zamanda sinyal işlemede yaygın olarak kullanılmaktadır . Kullanımları, bir dizi k eleman ( ) verildiğinde , bir elemanın i konumunda ortaya çıkma olasılığının yalnızca önceki n-1 elemanlara bağlı olduğu basitleştirici varsayıma dayanmaktadır . ${\ displaystyle k \ geq n}$

Yani biz varız . ${\ displaystyle P (w_ {i} | w_ {1}, ..., w_ {i-1}) = P (w_ {i} | w_ {i- (n-1)}, w_ {i- ( n-2)}, ..., w_ {i-1})}$

İle (vaka trigram ), elimizdeki . $n = 3$ ${\ displaystyle P (w_ {i} | w_ {1}, ..., w_ {i-1}) = P (w_ {i} | w_ {i-2}, w_ {i-1})}$

Olasılığı dizisi : ${\ displaystyle P (w_ {1, k}) = P (w_ {1}) \ kere P (w_ {2} | w_ {1}) \ kere P (w_ {3} | w_ {1}, w_ { 2}) \ kez ... \ kez P (w_ {k} | w_ {1}, w_ {2} ... w_ {k-1})}$

dönüştürülür: (. orada 0 konumunda bir element olup -1 dizisinin bu boş koşullar sokulmasıyla düzeltilebilir, ilk iki terim muhafaza fark eder, ama bu çok az önem değildi). ${\ displaystyle P (w_ {1, k}) = P (w_ {1}) \ çarpı P (w_ {2} | w_ {1}) \ prod _ {i = 3} ^ {n} P (w_ { i} | w_ {i-2}, w_ {i-1})}$

N-gram eğitimi

Bu hipotezden yola çıkarak, bir korpustan n-gramları öğrenmek mümkündür . ile tek yapmanız gereken tümceye göz atmak ve bir eleman üçlüsünün her oluşumu için (örneğin, her karakter veya kelime üçlüsü için) bu üçlünün görünüş sayısını, başlangıçtaki çiftin görünüş sayısını not etmektir. üçlünün ve birinciyi ikinciye bölün. $n = 3$

Basit bir örnekte, “aabaacaab” öğrenme külliyatından başlayarak, aşağıdaki üçüzlere sahibiz:

aab
aba
baa
aac
Buna
caa
aab

Çiftlerin yanı sıra onları da sıralayalım:

aab: 2 tekrar
aba: 1 olay
baa: 1 olay
aac: 1 oluşum
aca: 1 oluşum
caa: 1 olay

aa: 3 tekrar
ab: 2 tekrar
ba: 1 olay
ac: 1 oluşum
ca: 1 olay

Aşağıdaki tri-gramları elde ederiz:

${\ textstyle P (b | aa) = {\ frac {P (aab)} {P (aa)}} = {\ frac {P (aab)} {\ toplam _ {X \ in \ {a, b, c \}} P (aaX)}} = {\ frac {2/7} {0 + 2/7 + 1/7}} = {\ frac {2} {3}}}$
${\ displaystyle P (c | aa) = {\ frac {P (aac)} {P (aa)}} = 1/3}$
${\ displaystyle P (a | ab) = {\ frac {P (aba)} {P (ab)}} = 1/2}$
...

Bu bütünceden, eğer "aa" çifti ortaya çıkarsa, bir sonraki elemanın "b" olma olasılığı 2/3, bir sonraki elemanın "c" olma olasılığı 1/3 olduğunu çıkarırız.

Önemsiz ama önemli bir özellik . Bu, herhangi bir n değeri için önemsiz bir şekilde genellenir. ${\ displaystyle \ forall w_ {i}, w_ {j}, \ toplam _ {k} P (w_ {i}, w_ {j}, w_ {k}) = \ toplam _ {k} P (w_ {k) } | w_ {i}, w_ {j}) P (w_ {i}, w_ {j}) = P (w_ {i}, w_ {j}) \ toplam _ {k} P (w_ {k} | w_ {i}, w_ {j}) = P (w_ {i}, w_ {j})}$

Eşdeğer Markov zincirini elde ederiz :

N-gram sınırı

İlk sorun ortaya çıkar: bazı üçüzler eğitim korpusunda görünmez (bu nedenle olasılıkları 0'da sabitlenmiştir), ancak kullanım sırasında risk ortaya çıkar. Gerçekten de, bir dilin tüm n-gramlarını tam olarak dağıtılmış bir şekilde (yani gerçek dağılıma karşılık gelen) içeren temsili bir külliyat oluşturmanın imkansız olduğunu biliyoruz ("dil" ile burada doğal bir dili kastediyoruz, ancak uzatma ile kişinin n-gram ile öğrenmeye tabi tutmak istediği herhangi bir özel dizi kümesini kastediyoruz).

Bu sorunun üstesinden gelmek için olasılıklar "düzeltilir". Tri-gramın hesaplanması yaklaşıktır ve şöyle olur:

${\ displaystyle P (w_ {n-2} w_ {n-1} w_ {n}) = \ lambda _ {1} P (w_ {n-2}) \ kere \ lambda _ {2} P (w_ { n-1} | w_ {n-2}) \ kere \ lambda _ {3} P (w_ {n} | w_ {n-2}, w_ {n-1})}$

ile , unigramın olasılığı ve bigramın olasılığı. ${\ displaystyle \ lambda _ {1} + \ lambda _ {2} + \ lambda _ {3} = 1}$ ${\ displaystyle P (w_ {n-2})}$ ${\ displaystyle P (w_ {n-1} | w_ {n-2})}$

N-gramların Kullanımı

N-gram kullanımının tam bir örneği Viterbi Algoritması makalesinde sunulmaktadır .

Şuna da bakın:

N-gram kullanarak verimli bilgi işleme için Viterbi algoritması .
Gizli Markov modeli
diyagram
Google Ngram Viewer , yıllara göre bir kitap külliyatındaki bir dizi kelimenin sıklığını görüntüler