Dynamic Time Warping 에 대한 고찰..

EATS 논문을 읽던 중, loss function에 Soft dynamic time warping 이 사용된 것을 확인하였다. 

Dynamic Time Warping 은 연속적인 시퀀스 를 비교할 때, 유클리디안 거리 보다 더 알맞게 거리 측정을 해주는 좋은 녀석이다. 설명을 해 보도록 하겠다. 

Dynamic Time Warping

A = [2,2,3,4,5]
B = [1,2,3,3,4]

다음과 같은 두 sequence 데이터를 비교한다고 생각 해보자. (EATS를 기준으로 생각해 보면.. 사실 offset의 기준에 따라 generator 가 sqeuence를 만들어 내긴 하지만 그 기준이 제대로 학습되지 않았을 때는 시작과 끝이 다를 수도 있을 것이다.) Euclidian distance를 생각해 본다면 단순히 계산할 수 있겠지만, 우리가 원하는 건 알맞은 time step의 element들 끼리 제대로 비교가 되어서 gradient 가 흐르도록 하는 것이다. 여기서 Dynamic Time Warping 을 사용하여 그 문제를 해결해 줄 수 있다. 

먼저, 각 element 끼리의 거리를 계산해서 다음과 같이 cost matrix를 만들어 준다. 

다음에, 행렬을 쫙 늘려서 skewing 을 해준다. (i 번째 열을 i만큼 내려준다..) 

다음으로, size*2 -1 번 for loop를 돌며 최적의 경로를 찾아준다. 
보통의 경우는 아니지만, EATS 에서는 warping이 일어난다면 (대각선으로 이동하는 것이 아니라 위 또는 옆으로 이동할 경우) warp penalty 라는 것을 줘서 경로가 대각선에서 크게 벗어나지 않도록 한다. EATS에서의 warp penalty는 1.0이다. 

 

pred_cost_next = cost[i] + 
	min(prev_path_cost[:-1], path_cost[1:] + warp_penalty, path_cost[:-1] + warp_penalty)

인데 이를 시각화 해 본다면 

다음과 같이 된다.. 또 이제 이걸 

path_cost_next = concatenate([[INFINITY], path_cost_next])
path_cost, path_cost_prev = path_cost_next, path_cost

이렇게 할당해 준다. 

이렇게 for loop을 도는 과정을 다시한번 시각화를 해 본다면 

 

 

다음과 같이 됨을 알 수 있다.. 

시퀀스를 비교할 때 단순한 유클리드 거리로 비교하는 것 보다 더 정확한 거리 표현이 가능하다. 

DTW를 다뤄보았으니.. 다음에는 soft dtw를 다루어보도록 하곘당