Viterbi-Algorithmus

d(S,0) = 1

d(PP,1) = d(S,0) p(PP|S) p(I|PP) = 1 * 0.25 * 0.3 = 0,075
psi(PP,1) = S

d(AUX,2) = d(PP,1) p(AUX|PP) p(can|AUX) = 0,075 * 0,2 * 0,5 = 0,0075
d(NN,2) = d(PP,1) p(NN|PP) p(can|NN) = 0,075 * 0,2 * 0,3 = 0,0045
d(VB,2) = d(PP,1) p(VB|PP) p(can|VB) = 0,075 * 0,01 * 0,1 = 0,000075
psi(AUX,2) = PP
psi(NN,2) = PP
psi(VB,2) = PP

d(AUX,3) = max(d(AUX,2) p(AUX|AUX) p(can|AUX),
               d(NN,2) p(AUX|NN) p(can|AUX),
               d(VB,2) p(AUX|VB) p(can|AUX))
         = max(0,0075 * 0.01 * 0.5, 0.0045 * 0.2 * 0.5, 0,000075 * 0.94 * 0.5) = max(0.0000375 , 0.00045, 0,000000375) = 0.00045

d(NN,3) = max(d(AUX,2) p(NN|AUX) p(can|NN),
               d(NN,2) p(NN|NN) p(can|NN),
               d(VB,2) p(NN|VB) p(can|NN))
         = max(0,0075 * 0.01 * 0.3, 0.0045 * 0.1 * 0.3, 0,000075 * 0.22 * 0.3) = max(0.0000225 , 0.000135, 0.00000495) = 0.000135

d(VB,3) = max(d(AUX,2) p(VB|AUX) p(can|VB),
               d(VB,2) p(VB|NN) p(can|VB),
               d(VB,2) p(VB|VB) p(can|VB))
        = max(0,0075 * 0.94 * 0.1, 0.0045 * 0.01 * 0.1, 0,000075 * 0.01 * 0.1) = max(0.000705 , 0.0000045, 0.00000075) = 0.000705
psi(AUX,3)= NN
psi(NN,3) = NN
psi(VB,3) = AUX

d(S,4) = max(d(AUX,3) p(S|AUX), d(NN,3) p(S|NN), d(VB,3) p(S|VB))
       = max(0.00045 * 0.01, 0.000135 * 0.1, 0.000705 * 0.05)
       = max(0.0000045, 0.0000135, 0.00003525) = 0.0003525
psi(S,4) = VB

beste Tagfolge: PP AUX VB


Forward-Algorithmus

a(S,0) = 1

a(PP,1) = a(S,0) p(PP|S) p(I|PP) = 1 * 0.25 * 0.3 = 0,075

a(AUX,2) = a(PP,1) p(AUX|PP) p(can|AUX) = 0,075 * 0,2 * 0,5 = 0,0075
a(NN,2) = a(PP,1) p(NN|PP) p(can|NN) = 0,075 * 0,2 * 0,3 = 0,0045
a(VB,2) = a(PP,1) p(VB|PP) p(can|VB) = 0,075 * 0,01 * 0,1 = 0,000075

a(AUX,3) = a(AUX,2) p(AUX|AUX) p(can|AUX)+
           a(NN,2) p(AUX|NN) p(can|AUX)+
           a(VB,2) p(AUX|VB) p(can|AUX)
         = 0,0075 * 0.01 * 0.5 + 0.0045 * 0.2 * 0.5 + 0,000075 * 0.01 * 0.5 = 0.0000375 + 0.00045 + 0,000000375 = 0.000487875

a(NN,3) = a(AUX,2) p(NN|AUX) p(can|NN) +
          a(NN,2) p(NN|NN) p(can|NN) +
          a(VB,2) p(NN|VB) p(can|NN)
         = 0,0075 * 0.01 * 0.3 + 0.0045 * 0.1 * 0.3 + 0,000075 * 0.22 * 0.3 = 0.0000225 + 0.000135 + 0.00000495 = 0,00016245

a(VB,3) = a(AUX,2) p(VB|AUX) p(can|VB) +
          a(VB,2) p(VB|NN) p(can|VB) +
          a(VB,2) p(VB|VB) p(can|VB)
        = 0,0075 * 0.94 * 0.1 + 0.0045 * 0.01 * 0.1 + 0,000075 * 0.01 * 0.1 = 0.000705 + 0.0000045 + 0.00000075 = 0.000709575

a(S,4) = a(AUX,3) p(S|AUX) + a(NN,3) p(S|NN) + a(VB,3) p(S|VB)
       = 0.000487875 * 0.01 + 0.00016245 * 0.1 + 0.000709575 * 0.05
       = 0.00000487875 + 0.000016245 + 0.00003547875 = 0,0000566025


Backward-Algorithmus

b(S,4) = 1

b(AUX,3) = b(S,4) p(S|AUX) = 0.01
b(NN,3) = b(S,4) p(S|NN) = 0.1
b(VB,3) = b(S,4) p(S|VB) = 0.05

b(AUX,2) = b(AUX,3) p(AUX|AUX) p(can|AUX) +
           b(NN,3) p(NN|AUX) p(can|NN) +
           b(VB,3) p(VB|AUX) p(can|VB)
         = 0.01 * 0.01 * 0.5 + 0.1 * 0.01 * 0.3 + 0.05 * 0.94 * 0.1
	 = 0.00005 + 0.0003 + 0.0047 = 0.00505

b(NN,2) = b(AUX,3) p(AUX|NN) p(can|AUX) +
           b(NN,3) p(NN|NN) p(can|NN) +
           b(VB,3) p(VB|NN) p(can|VB)
         = 0.01 * 0.2 * 0.5 + 0.1 * 0.1 * 0.3 + 0.05 * 0.01 * 0.1
	 = 0.001 + 0.003 + 0.00005 = 0.00405

b(VB,2) = b(AUX,3) p(AUX|VB) p(can|AUX) +
           b(NN,3) p(NN|VB) p(can|NN) +
           b(VB,3) p(VB|VB) p(can|VB)
         = 0.01 * 0.01 * 0.5 + 0.1 * 0.22 * 0.3 + 0.05 * 0.01 * 0.1
	 = 0.00005 + 0.0066 + 0.00005 = 0.0067

b(PP,1) = b(AUX,2) p(AUX|PP) p(can|AUX) +
           b(NN,2) p(NN|PP) p(can|NN) +
           b(VB,2) p(VB|PP) p(can|VB)
         = 0.00505 * 0.2 * 0.5 + 0.00405 * 0.2 * 0.3 + 0.0067 * 0.01 * 0.1
	 = 0.000505 + 0.000243 + 0.0000067 = 0.0007547


b(S,0) = b(PP,1) p(PP|S) p(I|PP) = 0.0007547 * 0.25 * 0.3 = 0.0000566025

Kontrolle: b(S,0) = a(S,4)  also alles OK

g(PP,1) = a(PP,1) * b(PP,1) / a(S,4) = 0,075 * 0.0007547 / 0.0000566025 = 1.00