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

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

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)
(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: $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

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

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

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

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: $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

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

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í

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

Obsah

Písemka

2008/2009

2005/2006

Věci k zapamatování

Probability

Information Theory

Language Modeling

Smoothing

Linguistic Essentials

Mutual Information and Word Clasess

Word Classes

Zápočet

Conditional bigram entropy

texten1.txt

textcz1.txt

EM smoothing and cross-entropy

texten1.txt

textcz1.txt

Perl vs Python

Perl

Python

Odkazy

Navigační menu

Zobrazení

Osobní nástroje

Navigace

Hledat

Nástroje