Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/misc_lecture/page.html on line 23
Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/misc_lecture/page.html on line 23
Warning: main() [function.include]: Failed opening '/home/gurugail/header.php' for inclusion (include_path='.:/usr/local/lib/php') in /home/gurugail/misc_lecture/page.html on line 23
|
커뮤니티 게시판 |
|
A.I Section
자연어 처리 |
|
GGOP
GGOP 소개
|
| DP ( Dynamic Programming ) | |
|
작성 |
정현철 (lifegear@hanmail.net) |
|
작성 날짜 |
2001.08.20 |
|
개요 |
... |
|
|
|
DP의 원리
음성 인식의 경우, 음성 패턴을 추출한 후 저장한 A패턴과, 입력된 B패턴과 비교를 한다. 하지만 A 패턴과 B패턴은 항상 동일한 개수일 수 없다. 왜냐하면, 같은 음성일지라도 동일한 시간동안 입력되는 것이 아니기 때문이다. 개수가 같다면 서로 패턴 비교하기가 쉬울텐데 여러 가지 상황에서 패턴의 개수가 다를 수 있다. 이와 같이 패턴의 개수가 다를 때 패턴을 서로 비교할 수 있는 알고리즘이 Dynamic Programming이다.
A = a1, a2, ..., aI
B = b1, b2, ..., bJ, 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 포인트까지의 거리라 하면, 아래와 같이 구할 수 있다.
g1(c(1)) = d(c(1)) ?
w(1)
gk(c(k) = min [gk-1 (c(k-1)) + d(c(k)) ?
w(k)] - - - (1)
패턴 A와 패턴 B가 최소가 되는 warping 함수를 간단하게는 이처럼 구할 수 있다. 우선, 초기 매칭값에서부터 구하고, 그 다음 매칭값이 최소가 되는 바로 다음(next) 비교점을 찾아가면서 구하는 방법이다.
실례
A = {0, 2}
B = {0, 1, 4} 이라 하자. 이 때 DP를 적용한
결과의 매칭값을 구해보자. 이 때 가중치는 1이라 가정하자.
우선 g1 = d(0, 0) = 0
g2
= min [ 0 + d(0, 1), 0 + d(0, 4), 0 + d(2, 0), 0 + d(2, 1), 0 + d(2, 4) ]
=
1
g3 = 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
|
Reference |
|
|
||
|
|
||
|
