Statistické metody zpracování přirozených jazyků I
Statistické metody zpracování přirozených jazyků I | ||||
|
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[editovat | editovat zdroj]
2008/2009[editovat | editovat zdroj]
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[editovat | editovat zdroj]
10.1.2006 místo přednášky
Rozsah: začátek až "třídy slov" (poslední slajd je 192)
(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í[editovat | editovat zdroj]
Probability[editovat | editovat zdroj]
- Joint and conditional probability: $ p(A,B) = p(A \cap B) $;$ p(A|B) = \frac{p(A,B)}{p(B)} $
- Bayes Rule: $ p(A|B) = p(B|A)\cdot\frac{p(A)}{p(B)} $
- Chain Rule: $ 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) $
- The Golden Rule (of stat. NLP): $ A_{\mathrm{best}} = \mathrm{argmax}_A\ p(B|A)\cdot p(A) $
Information Theory[editovat | editovat zdroj]
- Entropy: $ H(X) = - \sum_x p(x)\cdot \log_2(p(x)) $
- Perplexity: $ G(p) = 2^H(p)\,\! $
- Conditional entropy: $ H(Y|X) = - \sum_{x,y} p(x,y)\cdot\log_2(p(y|x)) $
- Chain Rule: $ H(X,Y) = H(Y|X) + H(X) = H(X|Y) + H(Y)\,\! $
- Kullback-Leibler distance: $ D(p||q) = \sum p(x)\cdot\log_2(\frac{p(x)}{q(x)}) $
- Mutual Information: $ I(X,Y) = D(p(x,y)||p(x)\cdot p(y)) $
- $ I(X,Y) = \sum_{x,y} p(x,y) \cdot log_2( \frac{p(x,y)}{(p(x)\cdot p(y)} ) $
- $ I(X,Y) = H(X) - H(X|Y)\,\! $
- $ D(p||q) \geq 0 $
- Cross Entropy: $ H_{p'}(p) = - \sum_x p'(x)\cdot\log_2(p(x)) $
- conditional: $ H_{p'}(p) = - \sum_{x,y} p'(x,y)\cdot\log_2(p(y|x)) $
- conditional over data: $ -\frac{1}{|T'|}\cdot\sum_{i\mathrm{\ over\ data}}\log_2(p(y_i|x_i)) $
Language Modeling[editovat | editovat zdroj]
- The Golder Rule (again): $ A_{\mathrm{best}} = \mathrm{argmax}_A\ p(B|A)\cdot p(A) $, where
- $ p(B|A)\,\! $ – application specific model
- $ p(A)\,\! $ – the language model
- Markov Chain (n-gram LM): $ p(W) = \prod_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}) = \frac{c(w_{i-2}, w_{i-1}, w_i)}{c(w_{i-2}, w_{i-1})} $
Smoothing[editovat | editovat zdroj]
- Adding 1: $ p'(w|h) = \frac{c(w,h) + 1}{c(h) + |V|} $
- Adding less than 1 $ p'(w|h) = \frac{c(w,h) + \lambda}{c(h) + \lambda\cdot|V|} $
- Good-Turing: $ p'(w_i) = \frac{c(w_i + 1)*N(c(w_i) + 1)}{|T|*N(c(w_i))} $
- + normalize
- Linear Interpolation using MLE:
- $ 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|} $
- minimize entropy: $ -\frac{1}{|H|}\sum_{i=1}^{|H|}\log_2(p'_{\lambda}(w_i|h_i)) $
- compute expected counts for lambdas: $ c(\lambda_j) = \sum_{i=1}^{|H|}\frac{\lambda_j\cdot p_j(w_i|h_i)}{p'_{\lambda}(w_i|h_i)} $
- compute next lambdas: $ \lambda_{j,\mathrm{next}} = \frac{c(\lambda_j)}{\sum_k c(\lambda_k)} $
- Bucketed Smoothing – divide heldout data into buckets according to frequency and use LI+MLE
Linguistic Essentials[editovat | editovat zdroj]
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[editovat | editovat zdroj]
Word Classes[editovat | editovat zdroj]
- 3-gram LM using classes: $ 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}) $
- 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) = \mathrm{argmax}_{k,l}\ I_{\mathrm{merge}\;k,l} (D,E) $
- Repeat the previous step until $ |C|\,\! $ is as small as desired
Zápočet[editovat | editovat zdroj]
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[editovat | editovat zdroj]
texten1.txt[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
(epsilon v ukoncujici podmince = 0.0001)
texten1.txt[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
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[editovat | editovat zdroj]
- 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í