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.
Oorsig
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.
'n Konkrete voorbeeld
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.
Uitbreidings
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.
Kyk ook Baum Welch-algoritme Verborge Markovmodel Lineêre foutkorreksiekode
Bronnelys
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.
Eksterne skakels