Archiv/Statistické metody zpracování přirozených jazyků I

{{Předmět|Statistické metody zpracování přirozených jazyků I|Jan Hajič|PFL067}}

Statistical NLP (Natural Language Processing)

(Informace k druhému dílu předmětu jsem přesunul na zvláštní stránku -- Tuetschek 18:50, 18 May 2009 (CEST).)

Písemka

2008/2009

6.1.2009 místo přednášky

Písemka na hodinu, zadání velmi podobné ukázce na Hajičově webu. Probrané slajdy byly do 173, ale otázka i na Viterbiho algoritmus, takže se asi hodí zběžně projít i neprobrané.

Mnoho užitečných informací (ukázky pololetních písemek + řešení, ukázka finální písemky) je v adresáři na následující adrese.

2005/2006

10.1.2006 místo přednášky

Rozsah: začátek až "třídy slov" (poslední slajd je 192)<br/>

(písemka asi na hodinu)

Témata na písemkové otázky:

pravděpodobnost
entropie, vyhlazování
co je to ... ? (jazykový model, ...
(možná) teorie - značkování, morfologie, ...

Na webu předmětu je ukázka písemky (v zadání prvního příkladu je chyba - aby něco vycházelo například pomáhá, když se zamění hodnota p(a,a) a pL(a) (vymění se 1/2 a 1/4)).

Věci k zapamatování

Probability

Joint and conditional probability: <math>p(A,B) = p(A \cap B)</math>;<math>p(A|B) = \frac{p(A,B)}{p(B)}</math>
Bayes Rule: <math>p(A|B) = p(B|A)\cdot\frac{p(A)}{p(B)}</math>
Chain Rule: <math>p(A_1, A_2, \dots, A_n) = p(A_1|A_2, ..., A_n) \cdot p(A_2|A_3, ..., A_n) \cdot \vdots \cdot p(A_n)</math>
The Golden Rule (of stat. NLP): <math>A_{\mathrm{best}} = \mathrm{argmax}_A\ p(B|A)\cdot p(A)</math>

Information Theory

Entropy: <math>H(X) = - \sum_x p(x)\cdot \log_2(p(x))</math>
Perplexity: <math>G(p) = 2^H(p)\,\!</math>
Conditional entropy: <math>H(Y|X) = - \sum_{x,y} p(x,y)\cdot\log_2(p(y|x))</math>
- Chain Rule: <math>H(X,Y) = H(Y|X) + H(X) = H(X|Y) + H(Y)\,\!</math>
Kullback-Leibler distance: <math>D(p||q) = \sum p(x)\cdot\log_2(\frac{p(x)}{q(x)})</math>
Mutual Information: <math>I(X,Y) = D(p(x,y)||p(x)\cdot p(y))</math>
- <math>I(X,Y) = \sum_{x,y} p(x,y) \cdot log_2( \frac{p(x,y)}{(p(x)\cdot p(y)} )</math>
- <math>I(X,Y) = H(X) - H(X|Y)\,\!</math>
- <math>D(p||q) \geq 0</math>
Cross Entropy: <math>H_{p'}(p) = - \sum_x p'(x)\cdot\log_2(p(x))</math>
- conditional: <math>H_{p'}(p) = - \sum_{x,y} p'(x,y)\cdot\log_2(p(y|x))</math>
- conditional over data: <math>-\frac{1}{|T'|}\cdot\sum_{i\mathrm{\ over\ data}}\log_2(p(y_i|x_i))</math>

Language Modeling

The Golder Rule (again): <math>A_{\mathrm{best}} = \mathrm{argmax}_A\ p(B|A)\cdot p(A)</math>, where
- <math>p(B|A)\,\!</math> – application specific model
- <math>p(A)\,\!</math> – the language model
Markov Chain (n-gram LM): <math>p(W) = \prod_i P(w_i|w_{i-n+1}, w_{i-n+2}, ..., w_{i-1})\,\!</math>
Maximum Likelihood Estimate (3-grams): <math>p(w_i|w_{i-2}, w_{i-1}) = \frac{c(w_{i-2}, w_{i-1}, w_i)}{c(w_{i-2}, w_{i-1})}</math>

Smoothing

Adding 1: <math>p'(w|h) = \frac{c(w,h) + 1}{c(h) + |V|}</math>
Adding less than 1 <math>p'(w|h) = \frac{c(w,h) + \lambda}{c(h) + \lambda\cdot|V|}</math>
Good-Turing: <math>p'(w_i) = \frac{c(w_i + 1)*N(c(w_i) + 1)}{|T|*N(c(w_i))}</math>
- + normalize
Linear Interpolation using MLE:
- <math>p'_{\lambda}(w_i|w_{i-2}, w_{i-1}) = \lambda_3\cdot p_3(w_i|w_{i-2}, w_{i-1}) + \lambda_2\cdot p_2(w_i|w_{i-1}) + \lambda_1\cdot p_1(w_i) + \lambda_0\cdot\frac{1}{|V|}</math>
- minimize entropy: <math>-\frac{1}{|H|}\sum_{i=1}^{|H|}\log_2(p'_{\lambda}(w_i|h_i))</math>
- compute expected counts for lambdas: <math>c(\lambda_j) = \sum_{i=1}^{|H|}\frac{\lambda_j\cdot p_j(w_i|h_i)}{p'_{\lambda}(w_i|h_i)}</math>
- compute next lambdas: <math>\lambda_{j,\mathrm{next}} = \frac{c(\lambda_j)}{\sum_k c(\lambda_k)}</math>
Bucketed Smoothing – divide heldout data into buckets according to frequency and use LI+MLE

Linguistic Essentials

Většina věcí z této kapitoly se probírá také v rámci předmětu Úvod do počítačové lingvistiky.

Mutual Information and Word Clasess

Word Classes

3-gram LM using classes: <math>p_k(w_i|c_{i-2}, c_{i-1}) = p(w_i|c_i)\cdot p_k(c_i|c_{i-2}, c_{i-1})</math>
Which classes (words) to merge - objective function: <math>-H(W) + I(D|E)\,\!</math>, where <math>D, E\,\!</math> are LHS and RHS classes of the bigrams in <math>W\,\!</math>
Greedy Algorithm
- Start with each word in separate class
- Merge classes <math>k, l\,\!</math>, so that: <math>(k,l) = \mathrm{argmax}_{k,l}\ I_{\mathrm{merge}\;k,l} (D,E)</math>
- Repeat the previous step until <math>|C|\,\!</math> is as small as desired

Zápočet

Zádání obsahuje dva příklady. První je o počítání entropie, druhý je o vyhlazování jazykového modelu pomocí EM (Expectation Maximization) algoritmu.

Níže jsou vybrané číselné výsledky úkolů. Využívejte je prosím výhradně jako kontrolu výsledků vlastních. Měly by být správně, výsledky obou úkolů jsou potvrzeny nezávislým zdrojem.

Conditional bigram entropy

texten1.txt

Conditional bigram entropy of text in file "texten1.txt", characters were messed up with probability messProb.