Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жасырын күйлердің ең мүмкін тізбесін табу
Finds likely sequence of hidden states
Витерби алгоритмі – бұл динамикалық бағдарламалау алгоритмі. Ол байқалатын оқиғалар тізбесін тудыратын жасырын күйлердің ең мүмкін тізбесін – Витерби жолы деп аталатын – максималды апостериорлы ықтималдық бойынша бағалауға арналған. Бұл әсіресе Марков ақпарат көздері және жасырын Марков модельдері (ЖММ) контекстінде қолданылады. Алгоритм CDMA және GSM цифрлық ұялы байланысы, телефондық модемдер, спутниктер, терең ғарыш байланыстары және 802.11 сымсыз желілерінде қолданылатын конволюциялық кодтарды декодтауда кеңінен таралған. Қазір ол сөйлеуді тану, сөйлеу синтезі, сөйлеуді бөлу, кілт сөздерді анықтау, есептеу лингвистикасы және биоинформатикада да жиі қолданылады. Мысалы, сөйлеуден мәтінге аударғанда (сөйлеуді тану), дыбыстық сигнал байқалатын оқиғалар тізбегі ретінде қарастырылады, ал мәтін тізбегі – бұл дыбыстық сигналдың "жасырын себебі" болып саналады. Витерби алгоритмі дыбыстық сигналға сәйкес ең мүмкін мәтін тізбесін анықтайды.
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events. This is done especially in the context of Markov information sources and hidden Markov models (HMM). The algorithm has found universal application in decoding the convolutional codes used in both CDMA and GSM digital cellular, dial up modems, satellite, deep space communications, and 802.11 wireless LANs. It is now also commonly used in speech recognition, speech synthesis, diarization, keyword spotting, computational linguistics, and bioinformatics. For example, in speech to text (speech recognition), the acoustic signal is treated as the observed sequence of events, and a string of text is considered to be the "hidden cause" of the acoustic signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.
Тарих
Витерби алгоритмі 1967 жылы Эндрю Витерби ұсынған, шулы цифрлық байланыс желілерінде конволюциялық кодтарды декодтауға арналған алгоритм ретінде оның есімімен аталады. Дегенмен, оның бірнеше рет ойлап табылу тарихы бар, кем дегенде жеті тәуелсіз ашылу тіркелген, оның ішінде Витерби, Нидлман және Вунш, сондай-ақ Вагнер мен Фишердің еңбектері де бар. 1987 жылға дейін ол табиғи тілді өңдеуде сөздердің түрлерін анықтау әдісі ретінде қолданыла бастады. Витерби жолы және Витерби алгоритмі ықтималдықтарды қолданатын максимизациялық мәселелерді шешу үшін динамикалық бағдарламалау алгоритмдерін қолданудың стандартты терминдеріне айналды. Тағы бір қолданылу саласы – нысананы қадағалау, онда бақылаулар тізбегіне ең жоғары ықтималдық беретін траектория есептеледі.
The Viterbi algorithm is named after Andrew Viterbi, who proposed it in 1967 as a decoding algorithm for convolutional codes over noisy digital communication links. It has, however, a history of multiple invention, with at least seven independent discoveries, including those by Viterbi, Needleman and Wunsch, and Wagner and Fischer. It was introduced to natural language processing as a method of part of speech tagging as early as 1987. Viterbi path and Viterbi algorithm have become standard terms for the application of dynamic programming algorithms to maximization problems involving probabilities. Another application is in target tracking, where the track is computed that assigns a maximum likelihood to a sequence of observations.
Ұзартулар
Витерби алгоритмінің жалпылануы, ең жоғары жиынтық алгоритмі (немесе ең жоғары өнім алгоритмі) деп аталады, және оны көптеген графикалық модельдерде, мысалы, Байес желілері, Марков кездейсоқ өрістері және шартты кездейсоқ өрістерде, жасырын айнымалылардың барлық немесе кейбір кіші жиынтығының ең ықтимал тағайындауын табу үшін қолдануға болады. Жасырын айнымалылар, әдетте, жасырын Марков моделіне (ХММ) ұқсас түрде, айнымалылар арасындағы шектеулі байланыс санымен және айнымалылар арасындағы сызықтық құрылымның кейбір түрімен байланысты болуы керек. Жалпы алгоритм хабар алмасуды қамтиды және сенім тарату алгоритміне (алдыңғы-артқа қарай алгоритмнің жалпылануы) өте ұқсас. Итеративті Витерби декодтау деп аталатын алгоритм арқылы берілген жасырын Марков моделіне ең жақсы сәйкес келетін байқау тізбегін табуға болады. Бұл алгоритмді Qi Wang және авторлар тобы түрбо кодты өңдеу үшін ұсынды. Итеративті Витерби декодтау модификацияланған Витерби алгоритмін итеративті түрде шақыру арқылы жұмыс істейді, конвергенцияға дейін толтырғыштың бағасын қайта есептейді. Сонымен қатар, Жалқау Витерби алгоритмі ұсынылған. Көптеген практикалық қолданыстар үшін, қолайлы шу деңгейінде, Жалқау декодер (Жалқау Витерби алгоритмін пайдалана отырып) бастапқы Витерби декодерінен (Витерби алгоритмін пайдалана отырып) әлдеқайда жылдам жұмыс істейді. Алғашқы Витерби алгоритмі мүмкін нәтижелер тізбегіндегі әрбір түйінді есептейді, ал Жалқау Витерби алгоритмі бағалау үшін түйіндердің басымдық тізімін сақтайды, соның салдарынан қажетті есептеулер саны сол нәтижеге арналған қарапайым Витерби алгоритміне қарағанда әдетте аз (немесе ешқашан көп емес). Дегенмен, аппараттық жағынан оны параллельдеу оңай емес.
A generalization of the Viterbi algorithm, termed the max sum algorithm (or max product algorithm) can be used to find the most likely assignment of all or some subset of latent variables in a large number of graphical models, e. g. Bayesian networks, Markov random fields and conditional random fields. The latent variables need, in general, to be connected in a way somewhat similar to a hidden Markov model (HMM), with a limited number of connections between variables and some type of linear structure among the variables. The general algorithm involves message passing and is substantially similar to the belief propagation algorithm (which is the generalization of the forward backward algorithm). With an algorithm called iterative Viterbi decoding, one can find the subsequence of an observation that matches best (on average) to a given hidden Markov model. This algorithm is proposed by Qi Wang et al. to deal with turbo code. Iterative Viterbi decoding works by iteratively invoking a modified Viterbi algorithm, reestimating the score for a filler until convergence. An alternative algorithm, the Lazy Viterbi algorithm, has been proposed. For many applications of practical interest, under reasonable noise conditions, the lazy decoder (using Lazy Viterbi algorithm) is much faster than the original Viterbi decoder (using Viterbi algorithm). While the original Viterbi algorithm calculates every node in the trellis of possible outcomes, the Lazy Viterbi algorithm maintains a prioritized list of nodes to evaluate in order, and the number of calculations required is typically fewer (and never more) than the ordinary Viterbi algorithm for the same result. However, it is not so easy to parallelize in hardware.
Жай шығыс Viterbi алгоритмі
Жай шығыс Витерби алгоритмі (SOVA) – классикалық Витерби алгоритмінің бір түрі. SOVA классикалық Витерби алгоритмінен кіріс символдарының алдын ала ықтималдықтарын ескеретін өзгертілген жол метрикасын пайдалануымен ерекшеленеді және шешімнің сенімділігін көрсететін жұмсақ шығыс тудырады. SOVA-ның бірінші қадамы – әр уақыт мезгілінде (t) бір ғана түйірден өтетін аман қалған жолды таңдау. Әрбір түйірге 2 тармақ жиналады (біреуі аман қалған жолды құру үшін таңдалады, ал екіншісі жобаланады), сондықтан таңдалған және жобаланған тармақтар арасындағы тармақ метрикасының (немесе құнының) айырмасы таңдаудағы қателік деңгейін көрсетеді. Бұл құн бүкіл жылжымалы терезе бойында жинақталады (әдетте кем дегенде бес шектеу ұзындығына тең), Витерби алгоритмінің қатты бит шешімінің сенімділігін жұмсақ шығыс түрінде көрсетеді.
The soft output Viterbi algorithm (SOVA) is a variant of the classical Viterbi algorithm. SOVA differs from the classical Viterbi algorithm in that it uses a modified path metric which takes into account the a priori probabilities of the input symbols, and produces a soft output indicating the reliability of the decision. The first step in the SOVA is the selection of the survivor path, passing through one unique node at each time instant, t. Since each node has 2 branches converging at it (with one branch being chosen to form the Survivor Path, and the other being discarded), the difference in the branch metrics (or cost) between the chosen and discarded branches indicate the amount of error in the choice. This cost is accumulated over the entire sliding window (usually equals at least five constraint lengths), to indicate the soft output measure of reliability of the hard bit decision of the Viterbi algorithm.
Жалпы сілтемелер
(ескертпе: Витербидің декодилеу алгоритмі IV бөлімде сипатталған.) Абоненттік жазылым қажет. Абоненттік жазылым қажет. (Жасырын Марков модельдері үшін тікелей алгоритмі және Витерби алгоритмін сипаттайды). Шингхал, Р. және Годфрид Т. Туссент, "Өзгертілген Витерби алгоритмімен мәтінді танудағы тәжірибелер", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI l, 1979 жылғы сәуір, 184–193-беттер. Шингхал, Р. және Годфрид Т. Туссент, "Өзгертілген Витерби алгоритмінің бастапқы статистикаға сезімталдығы", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI 2, 1980 жылғы 2 наурыз, 181–185-беттер.
(note: the Viterbi decoding algorithm is described in section IV.) Subscription required. Subscription required. (Describes the forward algorithm and Viterbi algorithm for HMMs). Shinghal, R. and Godfried T. Toussaint, "Experiments in text recognition with the modified Viterbi algorithm," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI l, April 1979, pp. 184–193. Shinghal, R. and Godfried T. Toussaint, "The sensitivity of the modified Viterbi algorithm to the source statistics," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI 2, March 1980, pp. 181–185.