{{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 [[Statistické metody zpracování přirozených jazyků II|zvláštní stránku]] -- [[User:Tuetschek|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é [http://ufal.mff.cuni.cz/~hajic/courses/pfl043/0304/midterm.html 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í [http://ufal.mff.cuni.cz/~hajic/courses/pfl043/0607/ 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 [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í ==
=== 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 ==
[http://ufal.mff.cuni.cz/~hajic/courses/pfl043/0304/assign1.html 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.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 5.287 5.287 5.287 5.284 5.251 5.057 4.731
Conditional bigram perplexity of text in file "texten1.txt",
characters were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 39.055 39.054 39.044 38.961 38.075 33.295 26.549
Conditional bigram entropy of text in file "texten1.txt",
words were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 5.287 5.287 5.288 5.289 5.306 5.380 5.457
Conditional bigram perplexity of text in file "texten1.txt",
words were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 39.055 39.055 39.058 39.106 39.573 41.646 43.926
==== textcz1.txt ====
Conditional bigram entropy of text in file "textcz1.txt",
characters were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 4.748 4.748 4.747 4.739 4.658 4.335 4.008
Conditional bigram perplexity of text in file "textcz1.txt",
characters were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 26.868 26.866 26.850 26.698 25.251 20.189 16.088
Conditional bigram entropy of text in file "textcz1.txt",
words were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 4.748 4.748 4.748 4.747 4.739 4.698 4.636
Conditional bigram perplexity of text in file "textcz1.txt",
words were messed up with probability messProb.
messProb: 0.00000 0.00001 0.00010 0.00100 0.01000 0.05000 0.10000
avg: 26.868 26.868 26.866 26.852 26.710 25.962 24.862
=== EM smoothing and cross-entropy ===
(epsilon v ukoncujici podmince = 0.0001)
====texten1.txt====
Getting probabilities from "texten1.txt-train"...
Training lambdas on "texten1.txt-heldout" (terminate condition epsilon: 0.0001) ...
iteration 1 (l3...l0): 0.323 0.313 0.194 0.170
...
iteration 13 (l3...l0): 0.184 0.492 0.254 0.070
Testing model on "texten1.txt-test"...
original lambdas, l3..l0 = 0.184 0.492 0.254 0.070 cross-entropy: 7.4684
l3 boosted by 10%, l3..l0 = 0.265 0.443 0.229 0.063 cross-entropy: 7.4700
...
l3 boosted by 99%, l3..l0 = 0.992 0.005 0.003 0.001 cross-entropy: 10.5014
l3 discounted to 90%, l3..l0 = 0.165 0.503 0.260 0.072 cross-entropy: 7.4723
...
l3 discounted to 0%, l3..l0 = 0.000 0.603 0.311 0.086 cross-entropy: 7.7042
====textcz1.txt====
Getting probabilities from "textcz1.txt-train"...
Training lambdas on "textcz1.txt-heldout" (terminate condition epsilon: 0.0001) ...
iteration 1 (l3...l0): 0.202 0.251 0.357 0.190
...
iteration 13 (l3...l0): 0.186 0.245 0.429 0.140
Testing model on "textcz1.txt-test"...
original lambdas, l3..l0 = 0.186 0.245 0.429 0.140 cross-entropy: 10.2209
l3 boosted by 10%, l3..l0 = 0.267 0.220 0.386 0.126 cross-entropy: 10.2253
...
l3 boosted by 99%, l3..l0 = 0.992 0.002 0.004 0.001 cross-entropy: 13.1658
l3 discounted to 90%, l3..l0 = 0.167 0.250 0.439 0.144 cross-entropy: 10.2241
...
l3 discounted to 0%, l3..l0 = 0.000 0.301 0.527 0.172 cross-entropy: 10.4895
=== Perl vs Python ===
Požadovaným jazykem je Perl. Špatnou volbou nemusí být ani Python, mně osobně prošel bez potíží. Navíc se mi zdá mnohem elegantnější. Níže je srovnání obou jazyků (jádro EM algoritmu). Není to asi úplně objektivní, protože fragmenty pocházejí od jiných autorů a nejsou zcela ekvivalentní...
====Perl====
sub smooth
{
my $self = shift;
my $epsilon = shift;
my $heldout = shift;
# iterate over heldout keys
my $k;
# initialize correction vector
my @corr;
my $j;
my $w;
my $anotherRound = 1;
# rounds
my $round = 0;
while($anotherRound)
{
$round ++;
# print lambda vector
my @bits = map {sprintf "%.4f", $_ } @{$self->{lambda}};
my $lambdaVector = join(",", @bits);
print STDERR "Smoothing round $round (vector: $lambdaVector)\n";
# reset correction vector
for($j = 0; $j <= $self->{size}; $j++)
{
$corr[$j] = 0;
}
# calculate corrections
foreach $k (keys %{$heldout->{db}[$self->{size}]})
{
my $topKey = $k;
# calculate lambdaProbability
my $lp = $self->lambdaProb($self->{size}, $k);
my $level;
for($level = $self->{size}; $level > -1; $level--)
{
my $cp = $self->conditionalProb($level, $topKey)
* $self->{lambda}[$level];
my $update = $heldout->{db}[$self->{size}]{$k} * $cp / $lp;
$corr[$level] += $update;
($topKey,$w) = $self->decomposeKey($topKey);
}
}
# should we take another round ?
$anotherRound = 0;
# sum corrections
my $correctionSum = 0;
for($j = 0; $j <= $self->{size}; $j++)
{
$correctionSum += $corr[$j];
}
# adjust lambdas
for($j = 0; $j <= $self->{size}; $j++)
{
my $newLambda = $corr[$j]/$correctionSum;
my $diff = $self->{lambda}[$j] - $newLambda;
# if difference is bigger than epsilon, we should continue
if($diff > $epsilon)
{
$anotherRound = 1;
}
$self->{lambda}[$j] = $newLambda;
}
}
}
====Python====
def trainLambdas(self, heldoutFileName):
for iteration in xrange(500): # prevents livelock, counts iterations
expectedCounts = [0.0] * 4
# calculate expected counts
for trigram in TrigramStream(heldoutFileName):
for i in xrange(4):
expectedCounts[i] += \
self.lambdas[i] * self.getProbs[i](trigram) / self.getSmoothProb(trigram)
# update lambdas
doBreak = True
for i in xrange(4):
# leave duplicities for better readability
if abs(self.lambdas[i] - expectedCounts[i] / sum(expectedCounts)) >= emEpsilon:
doBreak = False
self.lambdas[i] = expectedCounts[i] / sum(expectedCounts)
#print info
print ' iteration %2i (l3...l0):' % (iteration + 1),
self.printLambdas()
print ''
sys.stdout.flush()
if doBreak:
break
== Odkazy ==
* [http://ufal.mff.cuni.cz/~hajic/courses/npfl067/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í
[[Category:Matematická lingvistika]]
