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

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Statistické metody zpracování přirozených jazyků I
Kód předmětu: NPFL067
Přednáší: Jan Hajič

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í
Citováno z „http://wiki.matfyz.cz/index.php?title=Statistické_metody_zpracování_přirozených_jazyků_I&oldid=19121“