맨위로가기

비터비 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

비터비 알고리즘은 1967년 앤드류 비터비가 제안한 알고리즘으로, 잡음이 있는 통신 링크에서 길쌈 부호 해독에 사용되었다. 확률과 관련된 극대화 문제의 동적 계획법 알고리즘의 표준 용어로 사용되며, 은닉 마르코프 모델(HMM)에서 관찰 시퀀스를 생성했을 가능성이 가장 높은 상태 시퀀스를 찾는 데 활용된다. 알고리즘은 두 개의 행렬을 구성하여 각 시간 단계에서 최대 확률을 계산하고, 이를 역추적하여 최적의 경로를 찾는다. 자연어 처리, 대상 추적 등 다양한 분야에 응용되며, 최대-합 알고리즘, 반복 비터비 디코딩, 지연 평가 비터비 알고리즘, 소프트 출력 비터비 알고리즘 등의 확장된 형태가 존재한다. 매스매티카, C++, 자바 등 다양한 프로그래밍 언어로 구현되어 있다.

더 읽어볼만한 페이지

  • 동적 계획법 - 배낭 문제
    배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다.
  • 동적 계획법 - 차원의 저주
    차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다.
  • 오류 검출 정정 - 부호 이론
    부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
  • 오류 검출 정정 - 패리티 비트
    패리티 비트는 이진 데이터에서 1의 개수가 짝수인지 홀수인지 나타내는 비트로서, 오류 감지 및 수정에 사용되며, 통신 프로토콜과 RAID 시스템 등 다양한 분야에서 활용된다.
  • 마르코프 모형 - 강화 학습
    강화 학습은 에이전트가 환경과의 상호작용을 통해 누적 보상을 최대화하는 최적의 정책을 학습하는 기계 학습 분야이며, 몬테카를로 방법, 시간차 학습, Q-러닝 등의 핵심 알고리즘과 탐험과 활용의 균형, 정책 경사법 등의 다양한 연구 주제를 포함한다.
  • 마르코프 모형 - 칼만 필터
    칼만 필터는 잡음이 있는 측정값들을 이용하여 선형 동적 시스템의 상태를 추정하는 재귀 필터로, 예측과 보정 단계를 반복하며 항법 시스템, 레이더 추적, 컴퓨터 비전 등 다양한 분야에 응용된다.
비터비 알고리즘
개요
비터비 알고리즘 그래프의 예시
비터비 알고리즘 그래프의 예시
유형동적 프로그래밍
고안자앤드루 비터비
발견 연도1967년
시간 복잡도O(Tm²) (T: 관측값 개수, m: 상태 개수)
공간 복잡도O(Tm) (T: 관측값 개수, m: 상태 개수)
적용 분야
통신이동통신
CDMA
GSM
디지털 TV
음성 인식음성 인식
키워드 스포팅
전산 생물학유전자 예측
RNA 컴퓨팅
숨겨진 마르코프 모델
기타기계 학습
자연어 처리
오류 정정 코드
관련 알고리즘
관련 알고리즘포워드 알고리즘
바움-웰치 알고리즘

2. 역사

1967년 앤드류 비터비가 잡음 섞인 통신 링크 상에서 길쌈 부호를 해독하기 위한 알고리즘으로 제안하면서 처음 등장했다.[11] 하지만 비터비 외에도 니들만과 분쉬, 와그너와 피셔 등 여러 연구자들이 독립적으로 유사한 알고리즘을 발견하여, 최소 7번 이상의 복수 발명을 거친 것으로 알려져 있다.[3] 1987년에는 자연어 처리 분야에서 품사 태깅에 도입되면서 응용 범위가 확장되었다.

3. 알고리즘

비터비 알고리즘은 앤드류 비터비가 제안한 알고리즘으로, 잡음이 있는 통신 링크에서 길쌈 부호를 해독하는 데 사용되었다.[1] 하지만 이 알고리즘은 비터비 외에도 여러 번 독립적으로 발견되었다.[11]

비터비 알고리즘은 은닉 마르코프 모형(HMM)에서 관측된 시퀀스를 생성할 확률이 가장 높은 숨겨진 상태 시퀀스를 찾는다. 각 시간 단계 t에서, t까지의 관측만 고려하는 부분 문제를 해결한다.

알고리즘은 크기가 T x |S| 인 두 행렬 P와 Q를 구성한다. (T: 관찰 시퀀스 길이, S: 숨겨진 상태 집합)


  • P_{t,s}는 모든 가능한 상태 시퀀스 중에서 관찰 t에서 상태 s로 끝날 최대 확률을 포함한다.
  • Q_{t,s}는 이 최대 확률 상태 시퀀스에서 s 전에 사용된 이전 상태를 추적한다.


\pi_s와 a_{r,s}를 각각 초기 확률 및 전이 확률이라고 하고, b_{s,o}를 상태 s에서 o를 관찰할 확률이라고 할 때, P의 값은 다음과 같은 재귀 관계에 의해 주어진다.[8]



P_{t,s} =

\begin{cases}

\pi_s \cdot b_{s,o_t} & \text{if } t=0, \\

\max_{r \in S} \left(P_{t-1,r} \cdot a_{r,s} \cdot b_{s,o_t} \right) & \text{if } t>0.

\end{cases}



Q_{t,s}의 공식은 t>0에 대해 동일하지만, \max는 \arg\max로 대체되고, Q_{0,s} = 0이다.

비터비 경로는 마지막 시간 단계에서 P의 최댓값을 선택하고 Q를 역순으로 따라가서 찾을 수 있다.

알고리즘의 시간 복잡도는 O(T\times\left|{S}\right|^2)이다. 상태 전이 확률이 0이 아닌 경우를 알고 있다면, 내부 루프를 최적화하여 복잡도를 O(T\times(\left|{S}\right| + \left|{E}\right|))로 줄일 수 있다. (E: 그래프의 에지 수)

"비터비 경로"와 "비터비 알고리즘"은 확률과 관련된 극대화 문제의 동적 계획법 알고리즘의 표준 용어가 되었다. 예를 들어 통계적 파싱 분야에서 문맥으로부터 자유로운, 가장 가능성 높은 단일 유도체 문자열을 찾아내는 데 사용되는 동적 계획법 알고리즘은 "비터비 파스(Viterbi Parse)"라고 부른다.

3. 1. 예제

마을 의사의 진료 예시를 통해 비터비 알고리즘의 작동 방식을 살펴본다.

모든 마을 주민이 건강(Healthy)하거나 열(Fever)이 나는 두 가지 상태만 있는 마을이 있다고 가정한다. 이 마을에서 오직 마을 의사만이 각자가 열이 나는지 아닌지 판단할 수 있다. 의사는 환자들에게 몸 상태가 어떤지 질문하여 열의 유무를 진단한다. 마을 사람들은 멀쩡하다(normal), 춥다(cold), 어지럽다(dizzy) 중에서 하나의 답변만을 할 수 있다.

의사는 환자들의 건강 상태가 이산적인 마르코프 연쇄를 따른다고 생각한다. "건강함", "열이 남"의 두 가지 상태가 존재하지만 의사는 이를 직접적으로 관찰할 수 없고 '숨겨져' 있다. 하루에 한 번 환자는 의사에게 자신의 건강 상태에 따라 "멀쩡함", "추움", "어지러움" 중 한 가지를 얘기할 수 있다.

관측값(멀쩡함, 추움, 어지러움)은 은닉 상태(건강함, 열이 남)와 함께 은닉 마르코프 모형(HMM)을 구성하며, 파이썬으로 나타내면 다음과 같다.

```python

obs = ('normal', 'cold', 'dizzy')

states = ('Healthy', 'Fever')

start_p = {'Healthy': 0.6, 'Fever': 0.4}

trans_p = {

'Healthy': {'Healthy': 0.7, 'Fever': 0.3},

'Fever': {'Healthy': 0.4, 'Fever': 0.6}

}

emit_p = {

'Healthy': {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},

'Fever': {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6}

}

```

이 코드에서 `start_p`는 환자의 첫 방문 시 HMM이 어느 상태에 있는가에 대한 의사의 생각을 반영한다. (의사는 대부분의 환자가 건강할 것이라는 것을 알고 있다.) 주어진 전이 확률에 따르면 여기서는 평형 상태가 아닌 특정한 확률 분포 `Healthy영어: 0.6, Fever영어: 0.4`를 사용하였다. `trans_p`는 기저의 마르코프 연쇄에 따른 건강 상태의 변화를 나타낸다. 이 예제에서 오늘 건강한 주민이 다음 날 열이 날 확률은 30%뿐이다. `emit_p`는 매일 환자가 자신의 몸 상태를 어떻게 느끼는지를 나타낸다. 건강하다면 50%의 확률로 "멀쩡하다"고 느끼며, 열이 난다면 60%의 확률로 "어지럽다"고 느낀다.

본 예제의 HMM에 대한 그래픽적 표현


환자는 3일간 연속으로 의사를 방문하였고, 의사는 첫날 환자가 "멀쩡하다"고 느꼈고, 이튿날 "춥다"고 느꼈으며, 셋째 날에는 "어지럽다"고 느꼈다는 것을 알게 되었다. 의사에게 질문이 하나 생겼다. 환자가 설명한 관측값에 맞는 가장 가능성 높은 건강 상태의 순서는 무엇인가? 이 질문은 비터비 알고리즘으로 답할 수 있다.

```python

def viterbi(obs, states, start_p, trans_p, emit_p):

V = [{}]

for st in states:

V[0][st] = {"prob": start_p[st] * emit_p[st][obs[0]], "prev": None}

# Run Viterbi when t > 0

for t in range(1, len(obs)):

V.append({})

for st in states:

max_tr_prob = max(V[t-1][prev_st]["prob"]*trans_p[prev_st][st] for prev_st in states)

for prev_st in states:

if V[t-1][prev_st]["prob"] * trans_p[prev_st][st] == max_tr_prob:

max_prob = max_tr_prob * emit_p[st][obs[t]]

V[t][st] = {"prob": max_prob, "prev": prev_st}

break

for line in dptable(V):

print(line)

opt = []

# The highest probability

max_prob = max(value["prob"] for value in V[-1].values())

previous = None

# Get most probable state and its backtrack

for st, data in V[-1].items():

if data["prob"] == max_prob:

opt.append(st)

previous = st

break

# Follow the backtrack till the first observation

for t in range(len(V) - 2, -1, -1):

opt.insert(0, V[t + 1][previous]["prev"])

previous = V[t + 1][previous]["prev"]

print('The steps of states are ' + ' '.join(opt) + ' with highest probability of %s' % max_prob)

def dptable(V):

# Print a table of steps from dictionary

yield " ".join(("%12d" % i) for i in range(len(V)))

for state in V[0]:

yield "%.7s: " % state + " ".join("%.7s" % ("%f" % v[state]["prob"]) for v in V)

```

함수 `viterbi`는 관측값들의 순서 `obs`, 숨겨진 상태들의 집합 `states`, 초기 확률 `start_p`, 전이 확률 `trans_p`, 출력 확률 `emit_p`를 인수로 받는다. 코드를 단순하게 하기 위해 관측값들의 순서 `obs`는 비어 있는 경우가 없으며, `trans_p[i][j]`, `emit_p[i][j]`는 모든 상태 i, j에 대하여 정의되어 있다고 가정한다.

실제 예제에서 전향/비터비 알고리즘은 다음과 같이 사용한다.

```python

viterbi(obs,

states,

start_p,

trans_p,

emit_p)

```

스크립트의 실행 결과는 다음과 같다.

```console

$ python viterbi_example.py

0 1 2

Healthy: 0.30000 0.08400 0.00588

Fever: 0.04000 0.02700 0.01512

The steps of states are Healthy Healthy Fever with highest probability of 0.01512

```

이에 따르면 ['normal', 'cold', 'dizzy']는 상태 ['Healthy', 'Healthy', 'Fever']에 의해 생성될 가능성이 가장 높다는 것을 알 수 있다. 다시 말하면, 주어진 관측값 하에서 환자는 첫 이틀 동안은 건강했지만 첫날은 '멀쩡함', 둘째 날은 '추위'를 느꼈고, 셋째 날엔 열이 나게 되었다는 것이다.

비터비 알고리즘의 과정은 트렐리스 다이어그램에 의해 도식화될 수 있다. 비터비 경로는 트렐리스 다이어그램에서의 최단 경로와 같다. 이 병원 예제는 아래와 같이 나타난다. 비터비 경로는 진하게 표시하고 있다.

비터비 알고리즘을 나타낸 트렐리스 다이어그램. 셋째 날 이후 가장 가능성 높은 상태 순서는 이다.

4. 확장

비터비 알고리즘은 다양한 그래프 모델에서 활용될 수 있도록 여러 형태로 확장되었다.


  • 최대-합 알고리즘 (Max-Sum Algorithm) 또는 최대-곱 알고리즘 (Max-Product Algorithm): 베이즈 네트워크, 마르코프 랜덤 필드, 조건부 무작위장 등 다양한 그래프 모델에서 사용되는 일반화된 형태이다. 신뢰 전파 알고리즘과 유사하게 메시지 전달 방식을 사용한다.[8]
  • 반복 비터비 디코딩 (Iterative Viterbi Decoding): 주어진 은닉 마르코프 모델(HMM)에 가장 잘 맞는 부분 관측 시퀀스를 찾는다. 터보 코드 처리를 위해 제안되었으며, 수정된 비터비 알고리즘을 반복적으로 호출하여 수렴할 때까지 필러의 점수를 다시 추정한다.[9]
  • 지연 평가 비터비 알고리즘 (Lazy Viterbi Algorithm): 필요할 때까지 노드 확장을 지연하여 계산 효율성을 높인다. 일반적인 비터비 알고리즘보다 적은 계산으로 동일한 결과를 얻을 수 있지만, 하드웨어 병렬화는 어렵다.[10]
  • 소프트 출력 비터비 알고리즘 (Soft Output Viterbi Algorithm, SOVA): 입력 심볼의 사전 확률을 고려하고 결정의 신뢰도를 나타내는 소프트 출력을 생성하는 고전적인 비터비 알고리즘의 변형이다. 생존 경로와 버려진 경로 사이의 분기 메트릭 차이를 누적하여 소프트 출력 신뢰도를 측정한다.

5. 응용

비터비 알고리즘은 다음과 같은 다양한 분야에서 활용되고 있다.


  • 통신: 오류 정정 부호(길쌈 부호, 터보 부호 등)의 해독, 채널 등화 등에 사용된다.[2]
  • 음성 인식: 음성 신호를 분석하여 가장 가능성 높은 단어 시퀀스를 추정한다.
  • 자연어 처리: 품사 태깅, 개체명 인식 등에 사용된다.[3]
  • 생물 정보학: DNA 염기서열 분석, 단백질 구조 예측 등에 활용된다.
  • 컴퓨터 비전: 객체 추적, 행동 인식 등에 사용된다.[7]

6. 구현


  • Mathematica는 확률 과정 지원의 일부로 구현되어 있다.
  • 순방향 오류 정정 코드 및 채널 이퀄라이제이션을 위한 C++ 구현은 [https://github.com/libsusa/susa/blob/master/inc/susa/channel.h Susa] 신호 처리 프레임워크에서 제공된다.
  • [https://github.com/xukmin/viterbi C++]
  • [http://pcarvalho.com/forward_viterbi/ C#]
  • [http://www.cs.stonybrook.edu/~pfodor/viterbi/Viterbi.java 자바]
  • [https://adrianulbona.github.io/hmm/ 자바 8]
  • [https://juliahub.com/ui/Packages/HMMBase/8HxY5/ 줄리아](Julia)(HMMBase.jl)
  • [https://metacpan.org/module/Algorithm::Viterbi 펄]
  • [http://www.cs.stonybrook.edu/~pfodor/viterbi/viterbi.P 프롤로그]
  • [https://hackage.haskell.org/package/hmm-0.2.1.1/docs/src/Data-HMM.html#viterbi 하스켈]
  • [https://github.com/nyxtom/viterbi 고]
  • [http://tuvalu.santafe.edu/~simon/styled-8/ SFIHMM]은 비터비 디코딩 코드를 포함한다.

참조

[1] 간행물 "Speaker Diarization: A Review of Recent Research" http://www1.icsi.ber[...] IEEE TASLP 2010-08-19
[2] 문서 G. David Forney Jr: The Viterbi Algorithm: A Personal History https://arxiv.org/ab[...] 2005-04-29
[3] 서적 Speech and Language Processing Pearson Education International
[4] 학회 Efficient parsing of highly ambiguous context-free grammars with bit vectors http://www.aclweb.or[...]
[5] 학회 A* parsing: fast exact Viterbi parse selection http://ilpubs.stanfo[...]
[6] 논문 AUGUSTUS: Ab initio prediction of alternative transcripts
[7] 학회 Maximum Likelihood Track Formation with the Viterbi Algorithm 1994
[8] 문서 Xing E, slide 11
[9] 논문 Iterative Viterbi Decoding, Trellis Shaping, and Multilevel Structure for High-Rate Parity-Concatenated TCM
[10] 학회 A fast maximum-likelihood decoder for convolutional codes http://people.csail.[...] 2002-12
[11] 문서 G. David Forney Jr: The Viterbi Algorithm: A Personal History https://arxiv.org/ab[...] 2005-04-29


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com