| dbpprop:abstract
|
- The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events. These algorithms belong to the realm of information theory. The algorithm makes a number of assumptions. First, both the observed events and hidden events must be in a sequence. This sequence often corresponds to time. Second, these two sequences need to be aligned, and an instance of an observed event needs to correspond to exactly one instance of a hidden event. Third, computing the most likely hidden sequence up to a certain point t must depend only on the observed event at point t, and the most likely sequence at point t − 1. These assumptions are all satisfied in a first-order hidden Markov model. The terms "Viterbi path" and "Viterbi algorithm" are also applied to related dynamic programming algorithms that discover the single most likely explanation for an observation. For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is sometimes called the "Viterbi parse". The Viterbi algorithm was conceived by Andrew Viterbi in 1967 as an error-correction scheme for noisy digital communication links, finding 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, 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.
- Der Viterbi-Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese Zustandssequenz wird auch als Viterbi-Pfad bezeichnet. Er wurde von Andrew J. Viterbi 1967 zur Dekodierung von Faltungscodes entwickelt, er fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. G. D. Forney leitete daraus 1972 den Optimalempfänger für verzerrte und gestörte Kanäle her. Der Viterbi-Algorithmus wird heutzutage zum Beispiel in Handys oder Wireless LANs zur Entzerrung oder Fehlerkorrektur der Funkübertragung verwendet. Ebenso in Festplatten, da bei der Aufzeichnung auf die Magnetplatten ebenfalls Verzerrungen entstehen. Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet: Die Informationstheorie, Spracherkennung, Bioinformatik und Computerlinguistik verwenden gerne den Viterbi-Algorithmus. Spracherkennung ohne diesen Algorithmus wäre schwer zu realisieren.
- El algoritmo de Viterbi permite encontrar las secuencia de estados más probable en un Modelo oculto de Márkov (MOM), S=(q_{1},q_{2}, \ldots, q_{T}), a partir de una observación O=(o_{1},o_{2},\ldots, o_{T}), es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones. Consideremos la variable \delta_{t}{(i)} que se define como: \delta_{t}{(i)} = \max_{q_{1},q_{2},\ldots,q_{t-1}}{P(q_{1},q_{2},\ldots,q_{t}=i,o_{1},o_{2}, \ldots, o_{t}|\mu)} \delta_{t}{(i)} es la probabilidad del mejor camino hasta el estado i habiendo visto las t primeras observaciones. Esta función se calcula para todos los estados e instantes de tiempo. \delta_{t+1}{(i)} = \biggl[\max_{1 \leq i \leq N}{\delta_{i}(a_{ij})}\biggr] b_{j}(o_{t+1}) Puesto que el objetivo es obtener las secuencia de estados más probable, será necesario almacenar el argumento que hace máxima la ecuación anterior en cada instante de tiempo t y para cada estado j y para ello utilizamos la variable \varphi_{t}{(j)}. A continuación se detalla el proceso completo utilizando las funciones \delta y \varphi.
- L'algorithme de Viterbi, d'Andrew Viterbi, permet de corriger les erreurs survenues lors d'une transmission à travers un canal bruité (dans une certaine mesure). Son utilisation s'appuie sur la connaissance du canal bruité (la probabilité qu'une information ait été modifiée en une autre) et permet de simplifier radicalement la complexité de la recherche du plus probable message d'origine (d'exponentielle, cette complexité devient linéaire). Cet algorithme a pour but de trouver la séquence d'états la plus probable ayant produit la séquence mesurée.
- L'Algoritmo Viterbi è un algoritmo ideato da Andrea Viterbi e generalmente utilizzato per trovare la migliore sequenza di stati (detta Viterbi path) in una sequenza di eventi osservati in un processo markoviano. L'algoritmo è usato per la decodifica di codici convoluzionali nel caso siano necessari elevati guadagni di decodifica del segnale.
- ビタビアルゴリズム（{{lang-en-short|Viterbi algorithm）は、観測された事象系列を結果として生じる隠された状態の最も尤もらしい並び（ビタビ経路と呼ぶ）を探す動的計画法アルゴリズムの一種であり、特に隠れマルコフモデルに基づいている。観測された事象系列の確率計算のアルゴリズムである 前向きアルゴリズム（forward algorithm）も密接に関連している。これらのアルゴリズムは情報理論の一部である。 このアルゴリズムには、いくつかの前提条件がある。まず、観測された事象と隠されている事象は1つの系列上に並んでいる。この系列は多くの場合時系列である。次に、これら2つの並びには一対一の対応があり、1つの観測された事象は正確に1つの隠されている事象に対応している。第三に、時点 t での最も尤もらしい隠されている事象の計算は、t での観測された事象と t − 1 での最も尤もらしい隠された事象の系列のみに依存している。これらの前提条件は、全て一次隠れマルコフモデルで満たされている。 「ビタビ経路; Viterbi path」および「ビタビアルゴリズム」という用語は、観測結果について1つの最も尤もらしい説明を与える動的計画法のアルゴリズムに関して使われる。例えば、動的計画法のアルゴリズムを使った統計的構文解析は、文字列について1つの最も尤もらしい解析結果を生じる。そのため、これを「ビタビ構文解析; Viterbi parse」と呼ぶこともある。 ビタビアルゴリズムは、アンドリュー・ビタビがノイズのあるデジタル通信経路における誤り検出訂正手法として生み出したものである。CDMAやGSMといったデジタル携帯電話、ダイヤルアップ接続用モデム、通信衛星、宇宙探査での通信、IEEE 802.11 無線LAN などの畳み込み符号の復号に広く利用されている。また、音声認識、自然言語処理、計算言語学、バイオインフォマティクスなどにも使われている。例えば、音声認識では、音声信号を観測された事象の系列として扱い、それを文字に変換したものがその音声信号に対応した「隠された原因」と見なされる。ビタビアルゴリズムは、与えられた音声信号から最も尤もらしい文字列を見つけ出す。
- Algorytm Viterbiego - algorytm dekodujący opracowany przez Andrew Viterbiego i opublikowany przez niego w 1967 roku w IEEE Transactions on Information Theory, IT-13 w artykule Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (str. 260-269). Jego pierwszym zastosowaniem było, i nadal jest, dekodowanie kodów splotowych. Jednak stosowany jest również w innych zaawansowanych technologiach telekomunikacyjnych, np. jako odbiornik nieliniowy dla kanału z interferencją międzysymbolową. Działanie tego algorytmu oparte jest o kryterium maksymalnej wiarygodności, a jego ideą jest to, że optymalna ścieżka dojścia przez dekoder do aktualnego stanu składa się ze ścieżki o najmniejszej metryce dojścia do któregoś ze stanów poprzednich oraz przejścia do aktualnego stanu. Jak widać proces ten jest procesem iteracyjnym. Im dłuższy czas obserwacji i działania tego algorytmu, tym bardziej wiarygodny wynik otrzymujemy. Można jednak zauważyć, że już po mniej więcej 3L do 5L krokach (gdzie L jest długością wymuszenia kodu) otrzymujemy na wykresie kratowym, wspólną ścieżkę, tzw. pień, dla kolejnych stanów. Możemy więc ograniczyć opóźnienie dekodowania właśnie do tego okresu i przyjąć wynik za wystarczająco dokładny. Algorytm Viterbiego sprawdza się zarówno w przypadku dekodowania twardo-, jak również miękkodecyzyjnego (przy użyciu algorytmu SOVA - Soft Output Viterbi Algorithm). Nie jest on oczywiście jedynym algorytmem dekodowania kodów splotowych, aczkolwiek na pewno najbardziej popularnym ze względu na łatwość jego realizacji sprzętowej.
- В 1967 году Витерби разработал и проанализировал алгоритм, в котором, по сути, реализуется декодирование, основанное на принципе максимального правдоподобия; однако в нем уменьшается вычислительная нагрузка за счет использования особенностей структуры конкретной решётки кода. Преимущество декодирования Витерби, по сравнению с декодированием по методу полного перебора, заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени <math>t_I</math>, и всеми путями решётки, входящими в каждое состояние в момент времени <math>ti</math>. В алгоритме Витерби не рассматриваются те пути решётки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решётку, принимая решения путём исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия. Отметим, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.
- Viterbis algortim används framför allt inom området telekommunikation. Dels för avkodning av faltningskoder samt som utjämnare i radiomottagaren. Viterbis algoritm uppfanns av Andrew Viterbi för att användas som felrättande kod i brusiga kommunikationslänkar.
|
| rdfs:comment
|
- The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models. The forward algorithm is a closely related algorithm for computing the probability of a sequence of observed events. These algorithms belong to the realm of information theory.
- Der Viterbi-Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese Zustandssequenz wird auch als Viterbi-Pfad bezeichnet. Er wurde von Andrew J. Viterbi 1967 zur Dekodierung von Faltungscodes entwickelt, er fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. G. D.
- El algoritmo de Viterbi permite encontrar las secuencia de estados más probable en un Modelo oculto de Márkov (MOM), S=(q_{1},q_{2}, \ldots, q_{T}), a partir de una observación O=(o_{1},o_{2},\ldots, o_{T}), es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones.
- L'algorithme de Viterbi, d'Andrew Viterbi, permet de corriger les erreurs survenues lors d'une transmission à travers un canal bruité (dans une certaine mesure). Son utilisation s'appuie sur la connaissance du canal bruité (la probabilité qu'une information ait été modifiée en une autre) et permet de simplifier radicalement la complexité de la recherche du plus probable message d'origine (d'exponentielle, cette complexité devient linéaire).
- L'Algoritmo Viterbi è un algoritmo ideato da Andrea Viterbi e generalmente utilizzato per trovare la migliore sequenza di stati (detta Viterbi path) in una sequenza di eventi osservati in un processo markoviano. L'algoritmo è usato per la decodifica di codici convoluzionali nel caso siano necessari elevati guadagni di decodifica del segnale.
- Algorytm Viterbiego - algorytm dekodujący opracowany przez Andrew Viterbiego i opublikowany przez niego w 1967 roku w IEEE Transactions on Information Theory, IT-13 w artykule Error bounds for convolutional codes and an asymptotically optimum decoding algorithm (str. 260-269). Jego pierwszym zastosowaniem było, i nadal jest, dekodowanie kodów splotowych. Jednak stosowany jest również w innych zaawansowanych technologiach telekomunikacyjnych, np.
- Viterbis algortim används framför allt inom området telekommunikation. Dels för avkodning av faltningskoder samt som utjämnare i radiomottagaren. Viterbis algoritm uppfanns av Andrew Viterbi för att användas som felrättande kod i brusiga kommunikationslänkar.
|
![[RDF Data]](/statics/sw-cube.png)
