Gurugail

DP의 원리

음성 인식의 경우, 음성 패턴을 추출한 후 저장한 A패턴과, 입력된 B패턴과 비교를 한다. 하지만 A 패턴과 B패턴은 항상 동일한 개수일 수 없다. 왜냐하면, 같은 음성일지라도 동일한 시간동안 입력되는 것이 아니기 때문이다. 개수가 같다면 서로 패턴 비교하기가 쉬울텐데 여러 가지 상황에서 패턴의 개수가 다를 수 있다. 이와 같이 패턴의 개수가 다를 때 패턴을 서로 비교할 수 있는 알고리즘이 Dynamic Programming이다.

 A =  a_1, a_2, ..., a_I  
 B =  b_1, b_2, ..., b_J   I ≠ J

그림. DP와 warping 함수

위의 그림에서 보듯이 개수가 다른 패턴 A, B를 비교(matching)하기 위해 warping 함수 F를 설정한다.

F = c(1), c(2), ... , c(k), ..., c(K) 단, c(k) = (i(k), j(k))

예를 들어, warping 함수는 패턴 A의 1번째 값과 패턴 B의 3번째 값과 비교를 한다면 c(k) = (1, 3)이 된다. 쉽게 표현하면, 패턴 A값들과 패턴 B 값들을 연결시켜주는 역할을 한다. 만약, 패턴의 개수가 같다면 warping 함수는 일직선이 되는 것이다.

그럼 이번에는 패턴 A와 패턴 B의 거리(distance)를 구해보자.

단, d(c) = d(i, j) = || ai, bj || w(k) 는 가중치

수식을 보면, 패턴 A와 패턴 B의 거리가 최소가 되는 warping 함수를 찾아야 됨을 알 수 있다. 여기서 DP의 좀 더 formal한 정의가 나올 수 있다. 즉, DP는 개수가 서로 다른 패턴 A, B 사이의 거리가 최소가 되는 warping 함수를 찾아서 A, B의 매칭값(matching value)을 산출하는 알고리즘이다.

DP - Equation

간단히 DP를 이용하는 방법은 gk를 k 포인트까지의 거리라 하면, 아래와 같이 구할 수 있다.

  g_1(c(_1)) = d(c(1)) * w(1) 
  g_k(c(k) = min [g_{k-1} (c(k-1)) + d(c(k)) * w(k)]  

패턴 A와 패턴 B가 최소가 되는 warping 함수를 간단하게는 이처럼 구할 수 있다. 우선, 초기 매칭값에서부터 구하고, 그 다음 매칭값이 최소가 되는 바로 다음(next) 비교점을 찾아가면서 구하는 방법이다.

실례

A = {0, 2} B = {0, 1, 4} 이라 하자. 이 때 DP를 적용한 결과의 매칭값을 구해보자. 이 때 가중치는 1이라 가정하자.

 우선
  g_1 = d(0, 0) = 0 
  g_2 = min [ 0 + d(0, 1), 0 + d(0, 4), 0 + d(2, 0), 0 + d(2, 1), 0 + d(2, 4) ] = 1 

  g_3 = min [ 1 + d(2, 4) ] = 3 

참조

• Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE Transactions on acoustics, speech, and signal processing, Vol. ASSP-26, No. 1, February 1978

\\