{{predmet|Statistické metody zpracování přirozených jazyků I|Jan Hajič|PFL067}}
{{predmet|Statistické metody zpracování přirozených jazyků II|Jan Hajič|PFL068}}
''Statistical NLP (Natural Language Processing)''
== Písemka ==
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 [http://ufal.mff.cuni.cz/~hajic/courses/pfl043/0304/midterm.html 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í ==
TODO: prepsat do texu
=== Probability ===
* Joint and conditional probability: p(A,B) = p(A intersect B); p(A|B) = p(A,B)/p(B)
* Bayes Rule: p(A|B) = p(B|A)*p(A)/p(B)
* Chain Rule: p(A1, A2, ..., An) = p(A1|A2, ..., An) * p(A2|A3, ..., An) * ... * p(An)
* The Golden Rule (of stat. NLP): best A : argmax_A p(B|A)*p(A)
=== Information Theory ===
* Entropy: H(X) = - Suma_x p(x)*log_2(p(x))
* Perplexity: G(p) = 2^H(p)
* Conditional entropy: H(Y|X) = - Suma_x,y p(x,y)*log2(p(y|x))
** Chain Rule: H(X,Y) = H(Y|X) + H(X) = H(X|Y) + H(Y)
* Kullback-Leibler distance: D(p||q) = Suma p(x)*log2(p(x)/q(x))
* Mutual Information: I(X,Y) = D(p(x,y)||p(x)*p(y))
** I(X,Y) = Suma_x,y p(x,y)*log2(p(x,y)/(p(x)*p(y))
** I(X,Y) = H(X) - H(X|Y)
** D(p||q) >= 0
* Cross Entropy: H_p'(p) = - Suma_x p'(x)*log2(p(x))
** conditional: H_p'(p) = - Suma_x,y p'(x,y)*log2(p(y|x))
** conditional over data: = -1/|T'| * Suma_{i over data} log2(y_i|x_i)
=== Language Modeling ===
* The Golder Rule (again): best A : argmax_A p(B|A)*p(A)
** p(B|A) – application specific model
** p(A) – the language model
* Markov Chain (n-gram LM): p(W) = Product_i P(w_i|w_i-n+1, w_i-n+2, ..., w_i-1)
* Maximum Likelihood Estimate (3-grams): p(w_i|w_i-2, w_i-1) = c(w_i-2, w_i-1, w_i) / c(w_i-2, w_i-1)
==== Smoothing ====
* Adding 1: p'(w|h) = (c(w,h) + 1) / (c(h) + |V|)
* Adding less than 1 p'(w|h) = (c(w,h) + lambda) / (c(h) + lambda*|V|)
* Good-Turing: p'(w_i) = c(w_i + 1)*N(c(w_i) + 1) / |T|*N(c(w_i))
** + normalize
* Linear Interpolation using MLE (l ~ lambda):
** p'_l(w_i|w_i-2, w_i-1) = l_3*p_3() + l_2*p_2() + l_1*p_1() + l_0*1/|V|
** minimize entropy: -1/|H| * Suma_{i=1..|H|} log2(p'_l(w_i|h_i))
** c(l_j) = Suma_{i=1..|H|} l_j*p_j(w_i|h_i) / p'_l(w_i|h_i)
** l_j,next = c(l_j) / Suma_k c(l_k)
* Bucketed Smoothing – divide heldout data into buckets according to frequency and use LI+MLE
=== Linguistic Essentials ===
...
=== Mutual Information and Word Clasess ===
==== Word Classes ====
* 3-gram LM using classes: p_k(w_i|c_i-2, c_i-1) = p(w_i|c_i)*p_k(c_i|c_i-2, c_i-1)
* Which classes (words) to merge - objective function: -H(W) + I(D|E), where D, E are LHS and RHS classes of the bigrams in W
* Greedy Algorithm
** Start with each word in separate class
** Merge classes k, l so that: (k,l) = argmax_k,l I_{merge k,l} (D,E)
** Repeat the previous step until |C| is as small as desired
== Odkazy ==
* [http://ufal.mff.cuni.cz/~hajic/courses/pfl043/0304/syllabus.html web předmětu] - termíny odevzdání úkolů jsou sice težce neaktuální, ale jinak stránka obsahuje spoustu užitečných informací
