Viterbi-algoritme

Die Viterbi-algoritme, vernoem na die ontwikkelaar daarvan Andrew Viterbi, is 'n dinamiese programmering-algoritme om die mees waarskynlike opeenvolging van verborge toestande te vind – bekend as die Viterbi-pad – wat lei tot 'n opeenvolging van waargenome gebeurtenisse, veral teen die agtergrond van verborge Markovmodelle. Die voorwaartse algoritme (Engels: forward algorithm) is 'n naverwante algoritme vir die berekening van die waarskynlikheid van 'n opeenvolging van waargenome gebeurtenisse. Dit is 'n subafdeling van 'n breër onderwerp wat bekend staan as inligtingsteorie.

Die Viterbi-algoritme is oorspronklik bedink is as 'n foutkorreksie-skema vir ruiserige digitale kommunikasieverbindings, met universele toepassing in dekodering van die konwolusionele kodes wat in beide CDMA en GSM digitale sellulêre, skakelmodems, satelliet, buitenste ruim-kommunikasie, en 802.11 radio LANs gebruik word. Dit word nou ook algemeen gebruik in spraakherkenning, spraaksintese, sleutelwoorduitkenning, rekenaarlinguistiek, en bioinformatika. In spraak-na-teks spraakherkenning, word die akoestiese sein byvoorbeeld behandel soos 'n waargenome opeenvolging van gebeurtenisse, en 'n string teks beskou as die "verborge oorsaak" van die akoestiese sein. Die Viterbi-algoritme vind die mees waarskynlike teksstring gegewe die akoestiese sein.

Die algoritme is nie veralgemeen nie; dit maak 'n aantal aannames. Eerstens moet beide die waargenome en verborge gebeurtenisse in 'n opeenvolging voorkom. Die opeenvolging kom dikwels met tyd ooreen. Tweedens moet die twee opeenvolgings belyn wees, en 'n waargenome gebeurtenis moet ooreenstem met presies een verborge gebeurtenis. Derdens moet berekening van die mees waarskynlike verborge opeenvolging tot by 'n sekere punt t, afhang van slegs die waargenome gebeurtenis by punt t, en die mees waarskynlike opeenvolging by punt t − 1. Hierdie aannames word almal bevredig in 'n eerste-orde-Markovmodel.

Die terme "Viterbi-pad" en "Viterbi-algoritme" word ook gebruik vir verwante dinamiese programmeringsalgoritmes wat die enkele mees waarskynlike verduideliking vir 'n waarneming vind. Byvoorbeeld, in stogastiese ontleding kan 'n dinamiese programmeringsalgoritme gebruik word om die enkele mees waarskynlike konteksvrye afleiding (sinstaksontleding) van 'n string te vind wat soms 'n "Viterbi-ontleding" genoem word.

Vir 'n vereenvoudigde beskrywing, moet bogenoemde aannames verstaan word. Eerstens moet ons verstaan dat die Viterbi-algoritme volgens 'n toestandsmasjien-aanname werk. Dit wil sê daar is 'n eindige aantal toestande, hoe groot ookal, wat gelys kan word. Vir elke toestand, of node, kan slegs een opeenvolging of pad daartoe lei. Dit is 'n fundamentele aanname van die algoritme omdat die algoritme alle moontlike paaie wat na 'n toestand lei ondersoek en net die mees waarskynlike een behou. Op dié wyse hoef die algoritme nie tred te hou met meervoudige paaie nie, maar slegs met een per toestand. 'n Tweede sleutelaanname is dat die oorgang van 'n vorige toestand na 'n nuwe toestand gemerk word deur 'n inkrementele maatstaf, gewoonlik 'n getal. Die oorgang word bereken uit die gebeurtenis. Die derde aanname is dat die gebeurtenisse in 'n sekere sin kumulatief is oor 'n pad, gewoonlik additief. Die kruks van die algoritme is dus om 'n nommer vir elke toestand te hou. Wanneer die gebeurtenis dan plaasvind, ondersoek die algoritme voorwaartse beweging na 'n nuwe stel toestande deur die maatstaf van 'n moontlike vorige toestand te kombineer met die inkrementele maatstaf van die oorgang weens die gebeurtenis en kies die beste een daaruit. Daar moet hier daarop gelet word dat die inkrementele maatstaf wat met 'n gebeurtenis geassosieer word afhanklik is van die oorgangswaarskynlikheid van die ou toestand na die nuwe toestand. Byvoorbeeld in datakommunikasie, is dit moontlik om slegs die helfte van die simbole vanaf 'n onewe-genommerde toestand te stuur en die ander helfte vanaf 'n ewe-genommerde toestand. Verder, is die toestandoorgangstabel in baie gevalle nie ten volle verbind nie. 'n Eenvoudige voorbeeld is 'n motorvoertuig wat 3 toestande het, vorentoe, stop en agteruit. 'n Oorgang van vorentoe na agteruit word nie toegelaat nie. Dit moet eers na die stop toestand gaan. Ná berekening van die kombinasies van inkrementele maatstawwe en die toestandmaatstaf, oorleef slegs die bestes en al die ander paaie word verwerp. Dit is die kruks van die algoritme. Daar is aanpassings aan die basiese algoritme wat toelaat vir 'n vorentoe soektog bo en behalwe die truwaartse soektog wat hier beskryf is.

Padgeskiedenis moet gestoor word. In sommige gevalle is die soekgeskiedenis eindig omdat die toestandmasjien by die enkodeerder in 'n bekende toestand begin en is daar genoeg geheue om al die paaie te behou. In sommige ander gevalle, byvoorbeeld konwolusionele enkodering, moet die dekodeerder die geskiedenis snoei op 'n diepte groot genoeg om verrigting op 'n aanvaarbare vlak te hou. Alhoewel die Viterbi-algoritme baie doeltreffend is, is daar aanpassings wat die berekeningslas kan verminder; die geheuebehoeftes neig om dieselfde te bly.

Neem aan jy het 'n vriend wat ver weg bly en met wie jy elke dag praat oor wat elkeen van julle die dag gedoen het. Jou vriend het net drie dinge wat hom interesseer: in die park wandel, winkels toe gaan en sy woonstel skoonmaak. Die keuse van wat om te doen word uitsluitlik bepaal deur die weer op 'n gegewe dag. Jy het geen besliste inligting oor die weer waar jou vriend woon nie, maar jy is bekend met die algemene tendense. Gegrond op wat hy jou vertel hy elke dag doen, probeer jy raai hoe die weer moes gewees het.

Jy glo dat die weer as 'n diskrete Markovketting optree. Daar is twee toestande, "Reën" en "Mooiweer", maar jy kan dit nie direk waarneem nie, met ander woorde, dit is van jou verborge. Elke dag is daar 'n sekere waarskynlikheid dat jou vriend een van die volgende aktiwiteite gaan uitvoer, afhangende van die weer: "wandel", "inkopies", of "skoonmaak". Aangesien jou vriend jou vertel van sy aktiwiteite, is hierdie waarnemings. Die hele stelsel is die van 'n verborge Markovmodel (VMM). Jy ken die algemene weerpatrone in die omgewing en jy weet wat jou vriend gemiddeld doen. Met ander woorde, die parameters van die VMM is bekend. Om die waarheid te sê jy kan dit in Pythonprogrammeertaal neerskryf:

toestande = ('Reën', 'Mooiweer')

waarnemings = ('wandel', 'inkopies', 'skoonmaak')

begin_waarskynlikheid = {'Reën': 0.6, 'Mooiweer': 0.4}

oorgang_waarskynlikheid = {
   'Reën' : {'Reën': 0.7, 'Mooiweer': 0.3},
   'Mooiweer' : {'Reën': 0.4, 'Mooiweer': 0.6},
   }

uitsending_waarskynlikhede = {
   'Reën' : {'wandel': 0.1, 'inkopies': 0.4, 'skoonmaak': 0.5},
   'Mooiweer' : {'wandel': 0.6, 'inkopies': 0.3, 'skoonmaak': 0.1},
   }

In hierdie fragment verwys begin_waarskynlikheid na jou onsekerheid oor die toestand waarin die VMM is wanneer jou vriend jou die eerste keer skakel (al wat jy weet dat dit op die gemiddeld geneig is om te reën). Die spesifieke waarskynlikheidsverspreiding wat hier gebruik word is nie die ekwilibrium verspreiding nie, wat (gegee die oorgangswaarskynlikhede) eintlik ongeveer {'Reën': 0.571, 'Mooiweer': 0.429} is. Die oorgang_waarskynlikheid verwys na die verandering in die weer in die onderliggende Markovketting. In die voorbeeld is daar slegs 'n 30% kans dat dit môre mooiweer sal wees as dit vandag reën. Die uitsending_waarskynlikhede dui aan hoe waarskynlik dit is dat jou vriend 'n sekere aktiwiteit elke dag uit sal voer. As dit reën is daar 'n 50% kans dat hy sy woonstel sal skoonmaak; as dit mooiweer is, is daar 'n 60% kans dat hy uit sal gaan vir 'n wandeling.

Jy praat drie dae opeenvolgend met 'n vriend en vind uit dat hy op die eerste dag gaan wandel het, op die tweede dag gaan inkopies doen het, en op die derde dag sy woonstel skoongemaak het. Jy het twee vrae: Wat is die algehele waarskynlikheid van hierdie reeks waarnemings? En wat is die mees waarskynlike opeenvolging van reën/mooiweer dae wat die waarnemings kan verklaar? Die eerste vraag word deur die voorwaartse algoritme beantwoord; die tweede, deur die Viterbi-algoritme. Hierdie twee algoritmes vertoon struktureel soveel ooreenkoms (om die waarheid te sê, hulle is beide verskillende gevalle van dieselfde abstrakte algoritme) dat hulle deur 'n enkele funksie geïmplementeer kan word:

def forward_viterbi(y, X, sp, tp, ep):
   T = {}
   for state in X:
       ##          prob.      V. path  V. prob.
       T[state] = (sp[state], [state], sp[state])
   for output in y:
       U = {}
       for next_state in X:
           total = 0
           argmax = None
           valmax = 0
           for state in X:
               (prob, v_path, v_prob) = T[state]
               p = ep[state][output] * tp[state][next_state]
               prob *= p
               v_prob *= p
               total += prob
               if v_prob > valmax:
                   argmax = v_path + [next_state]
                   valmax = v_prob
           U[next_state] = (total, argmax, valmax)
       T = U
   ## apply sum/max to the final states:
   total = 0
   argmax = None
   valmax = 0
   for state in X:
       (prob, v_path, v_prob) = T[state]
       total += prob
       if v_prob > valmax:
           argmax = v_path
           valmax = v_prob
   return (total, argmax, valmax)

Die funksie forward_viterbi bevat die volgende argumente: y is die opeenvolging van waarnemings, b.v. ['wandel', 'inkopies', 'skoonmaak']; X is die stel verborge toestande; sp is die beginwaarskynlikhede; tp is die oorgangswaarskynlikhede; en ep is die uitsendwaarskynlikhede.

Die algoritme werk op die afbeeldings T en U. Elkeen is 'n afbeelding van 'n toestand na 'n tripleks (prob, v_path, v_prob), waar prob die totale waarskynlikheid van alle paaie van die begin tot by die huidige toestand is, v_path die Viterbi-pad tot by die huidige toestand is, en v_prob die waarskynlikheid van die Viterbi-pad tot by die huidige toestand is. Die afbeeldingkode T hou die inligting vir 'n gegewe tydstip t, en die hooflus bou U, wat soortgelyke inligting vir tydstip t+1 hou. Weens die Markoveienskap is inligting rakende enige tydstip voor t oorbodig.

Die algoritme begin deur die T te inisialiseer om die waarskynlikhede aan die gang te sit: die totale waarskynlikheid van 'n toestand is net die begin-waarskynlikheid van die toestand; en die Viterbi-pad na 'n begintoestand is die eenduidige pad wat slegs uit daardie toestand bestaan; die waarskynlikheid van die Viterbi-pad is dieselfde as die begin-waarskynlikheid.

Die hooflus oorweeg die waarnemings van y opeenvolgend. Die lusinvariant daarvan is dat T die korrekte inligting bevat tot by, maar uitgesluit die tydstip van die huidige waarneming. Die algoritme bereken die tripleks (prob, v_path, v_prob) vir elke moontlike volgende toestand. Die totale waarskynlikheid van 'n gegewe volgende toestand, total word verkry deur die waarskynlikheid van al die paaie wat die toestand bereik op te tel. Meer noukeurig gestel, die algoritme herhaal oor alle moontlike brontoestande. Vir elke brontoestand hou T die totale waarskynlikheid van alle paaie na die toestand. Hierdie waarskynlikheid word dan vermenigvuldig met die uitsend-waarskynlikheid van die huidige waarneming en die oorgang-waarskynlikheid van die brontoestand na die volgende toestand. Die gevolglike waarskynlikheid prob word dan bygetel by die total. Die waarskynlikheid van die Viterbi-pad word op 'n soortgelyke manier bereken, maar in plaas van optelling oor alle paaie, voer mens 'n diskrete maksimering uit oor alle paaie. Aanvanklik is die maksimumwaarde valmax nul. Vir elke brontoestand is die waarskynlikheid van die Viterbi-pad na die toestand bekend. Dit word ook vermenigvuldig met die uitsend- en oorgang-waarskynlikhede en vervang valmax as dit groter is as die huidige waarde. Die Viterbi-pad self word bereken as die ooreenstemmende argmax van daardie maksimering, deur die Viterbi-pad wat lei tot die huidige toestand met die volgende toestand uit te brei. Die tripleks (prob, v_path, v_prob) wat op die manier bereken word, word in U gestoor en wanneer U bereken is vir alle moontlike volgende toestande, vervang dit T en verseker daarmee dat die lusinvariant behou bly aan die einde van die iterasie.

Uiteindelik word nog 'n sommering/maksimering uitgevoer (dit kan ook binne die hooflus gedoen word na die laaste werklike waarneming).

In die voorbeeld word die voorwaartse/Viterbi-algoritme as volg gebruik:

def example():
   return forward_viterbi(['walk', 'shop', 'clean'],
                          states,
                          start_probability,
                          transition_probability,
                          emission_probability)

Dit dui aan dat die totale waarskynlikheid van ['wandel', 'inkopies', 'skoonmaak'] 0.033612 is en dat die Viterbi-pad ['Mooiweer', 'Reën', 'Reën', 'Reën'] is. Die Viterbi-pad bevat vier toestande omdat die vierde waarneming gegenereer word deur die derde toestand en die oorgang na 'n oorgang na die vierde toestand. Met ander woorde, gegewe die waargenome aktiwiteite, was dit mees waarskynlik mooiweer toe jou vriend gaan wandel het, gevolg deur 'n dag waarop dit begin reën het, 'n reën wat mees waarskynlik aangehou het.

Met die algoritme genaamd Iteratiewe Viterbi-dekodering kan 'n mens die subopeenvolging vind van 'n waarneming wat (gemiddeld) die beste sal pas vir 'n gegewe VMM. Iteratiewe Viterbi-dekodering, ontwikkel deur M.C. Silaghi (1998), werk deur die iteratiewe roep van 'n aangepaste Viterbi-algoritme wat die telling vir 'n 'vuller' herberaam totdat konvergensie behaal word.

'n Alternatiewe algoritme, genaamd die Lui Viterbi-algoritme (Engels: Lazy Viterbi algorithm, is onlangs (2002) voorgestel. Dit werk deur nie enige nodes uit te brei totdat dit werklik nodig is nie, en slaag gewoonlik daarin om oor die weg te kom met baie minder werk (wat betref sagteware-aanwending) as die gewone Viterbi-algoritme vir dieselfde resultaat. Dit is egter moeilik om in hardeware te paralleliseer.

• Baum Welch-algoritme
• Verborge Markovmodel
• Lineêre foutkorreksiekode

• Andrew J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory 13(2):260–267, April 1967. (Die Viterbi-dekoderingsalgoritme word in afdeling IV beskryf.)

• G. D. Forney. The Viterbi algorithm. Proceedings of the IEEE 61(3):268–278, Maart 1973.

• L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2):257–286, February 1989. (Beskryf die voorwaartse algoritme en Viterbi-algoritme vir VMM'e).

• J Feldman, I Abou-Faycal and M Frigo. A Fast Maximum-Likelihood Decoder for Convolutional Codes.

• 'n Onderhoud met Andrew Viterbi, insluitend agtergrond tot die ontdekking van die Viterbi-algoritme Geargiveer 8 Maart 2005 op Wayback Machine