[논문리뷰] Soft Dynamic Time Warping

Dynamic Time Warping은 두 시간 시퀀스를 더 잘 비교하기 위한 metric 

Soft Dynamic Time Warping은 optimal 한 Path 만을 고려하는 DTW 와는 다르게 다른 path들도 같이 고려하는 metric 

Differentiable 해서 딥러닝에도 사용이 가능하다고 한다. 

arxiv.org/pdf/1703.01541.pdf

이 그림에 보면 보라색 부분 cost 가 optimal 이다..

이 알고리즘을 설명하면 

이거인데 이거 그냥 a1, an까지의 선택지가 있을때 gamma=0일때는 일반적인 DTW 로 minimum만 고르는거고 아닐 때는 위의 식처럼 모든 path들을 계산해 주는 거다. 시간복잡도는 O(nm)인데 줄이자면 O(2n)으로 줄일 수 있지만 어차피 backward 에 보내야 할 때 다시 계산해야하기때문에 그냥 O(nm)의 방식으로 했다고 한다. 

자 미분.. 을 해보자. 

결국 우리가 알고싶은건 이 gradient 값인데 

R = [ri,j] 를 얻었다고 했을 때 r n,m에는 모든 경로들의 계산값이 다들어있다. 결국 r n, m을 통해서 gradient를 흘려보내줘야 한다는 뜻인데, 이는 chain rule을 통해서 구해볼 수 있다. 

이렇게 ... 된다. 

임에 주목한다면 . 여기서 eats의 경우, warping penalty가 추가된다. warping penalty c 도 식에 추가해 넣어보자. 
글씨가 좀 이상하지만.. 다음과 같다. 

r i,j 에 대해서 미분한 값은 다음 결과를 주는데,

dtw 의 경우는 다음과 같음 

따라서 이 식에 그냥 -1 값이 된 거.. 계산은 되겠고 이제 EATS 수도코드 랑 조합해서 생각해봐야겠다 .. 투비 컨티뉴..