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.