{{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 zvláštní stránku -- User: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)<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 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 ⋮\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 lo{g}_2(\frac{p(x,y)}{(p(x)\cdot p(y)})$

  • $I(X,Y)=H(X)-H(X|Y)$

  • $D(p||q)\ge 0$

• Cross Entropy: $H_{p^{\prime }}(p)=-{\sum }_x{p}^{\prime }(x)\cdot {\log }_2(p(x))$

  • conditional: $H_{p^{\prime }}(p)=-{\sum }_{x,y}{p}^{\prime }(x,y)\cdot {\log }_2(p(y|x))$

  • conditional over data: $-\frac{1}{|T^{\prime }|}\cdot {\sum }_{i\mathrm{over}\mathrm{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^{\prime }(w|h)=\frac{c(w,h)+1}{c(h)+|V|}$

• Adding less than 1 $p^{\prime }(w|h)=\frac{c(w,h)+\lambda }{c(h)+\lambda \cdot |V|}$

• Good-Turing: $p^{\prime }(w_i)=\frac{c(w_i+1)\ast N(c(w_i)+1)}{|T|\ast N(c(w_i))}$

  • • normalize

• Linear Interpolation using MLE:

  • $p_{\lambda }^{\prime }(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 }^{\prime }(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 }^{\prime }(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í

Category:Matematická%20lingvistika