Dynamic Time Warping

• 다른 이름: DTW
• 카테고리: Learning & autonomy › Learning from demonstration
• 태그: time-series, sequence-alignment, dynamic-programming, learning-from-demonstration, trajectory-analysis

속도나 길이가 다른 두 시계열을, 순서를 보존하면서 총거리가 가장 작은 샘플 짝짓기를 찾아 정렬하는 동적 계획법 알고리즘.

정의

동적 시간 워핑(dynamic time warping, DTW)은 비슷한 패턴을 따르지만 속도가 다른 두 시퀀스를 비교한다. 예를 들어 같은 동작을 두 번 시연했는데 한 조작자는 중간에 멈췄고 다른 조작자는 빠르게 움직인 경우가 그렇다. DTW는 i번째 샘플을 i번째 샘플과 비교하는 대신 워핑 경로를 찾는다. 워핑 경로는 두 시퀀스의 샘플을 짝지은 것으로, 두 시퀀스의 시작에서 출발해 두 시퀀스의 끝에서 끝나며 시간을 거슬러 가지 않는다. 각 샘플은 다른 시퀀스의 샘플 하나 또는 여러 개와 짝지어질 수 있으므로, 시간상의 늘어남과 줄어듦이 정렬에 흡수된다. DTW 거리는 최적 경로를 따른 총비용이며, 경로 자체는 어느 순간들이 서로 대응하는지를 알려 준다.

표준 알고리즘은 동적 계획법으로 비용 행렬을 채운다. 한 시퀀스의 샘플 i와 다른 시퀀스의 샘플 j 사이의 국소 거리를 d(i, j)라 하면, 누적 비용은 D(i, j) = d(i, j) + min(D(i−1, j), D(i, j−1), D(i−1, j−1))이고, 마지막 셀에서 역추적하면 경로를 복원할 수 있다. 이 계산에는 두 길이의 곱에 비례하는 시간과 메모리가 든다. Sakoe와 Chiba(1978)는 이 방법을 음성 단어 인식에 대중화했고, 정렬이 얼마나 멀리 벗어날 수 있는지를 제한하는 대각선 주위의 띠를 도입했다. Itakura 평행사변형은 이와 관련된 제약이다. 이런 윈도는 계산을 빠르게 하고, 한 샘플이 다른 시퀀스의 긴 구간과 짝지어지는 병적인 워핑을 막는다.

로봇공학에서는 여러 변형이 중요하다. Subsequence DTW는 시작과 끝 조건을 완화하여 짧은 질의를 긴 궤적에서 가장 잘 맞는 구간과 짝지을 수 있게 하며, 이는 대규모 로그에서의 검색을 뒷받침한다. Derivative DTW는 원시 값이 아니라 국소 기울기로 정렬한다. 2017년 Cuturi와 Blondel이 도입한 Soft-DTW는 최솟값을 매끄러운 버전으로 바꾸어 정렬 비용을 미분 가능하게 만들므로 학습 손실로 쓸 수 있다. DTW는 시간 축으로만 정렬한다. 특징은 서로 비교 가능해야 하고 보통 정규화해야 하며, 결과 거리는 삼각 부등식을 만족하지 않으므로 진정한 거리 함수(metric)가 아니다.

중요한 이유

로봇 데이터가 같은 속도로 들어오는 경우는 드물다. 시연, 실행된 궤적, 센서 기록은 타이밍이 서로 다르며, DTW는 이들을 평균 내거나, 비교하거나, 검색하거나, 점수를 매기기 전에 공통 시간축 위에 놓는 표준 도구이다.

주요 응용

• 평균을 내거나 모션 프리미티브를 맞추기 전에 여러 시연을 정렬하기
• 실행된 로봇 궤적을 기준 궤적과 비교하기
• 대규모 궤적 로그나 센서 로그에서 일치하는 구간 검색하기
• 모션 데이터나 관성 데이터로부터의 제스처 및 활동 인식
• 정규화된 DTW 지표로 내비게이션 경로를 기준 경로와 비교해 점수 매기기
• 서로 다른 속도로 기록된 센서 스트림 동기화하기

실제 사례

한 팀이 붓기 동작의 운동 감각 교시 시연을 열 번 수집하는데, 각 시연은 지속 시간이 다르고 서로 다른 곳에서 멈춘다. 모션 프리미티브를 위한 단일 기준을 만들기 위해, 팀은 시연 하나를 템플릿으로 고르고, 정규화된 관절 위치와 엔드 이펙터 속도에 대한 DTW로 나머지 시연을 각각 템플릿에 정렬한 뒤, 워핑 경로를 써서 모두를 템플릿의 시간축 위로 다시 샘플링한다. 정렬된 궤적을 평균 내면 깨끗한 평균 동작과, 시연들이 어디서 일치하는지 보여 주는 시간 단계별 분산을 얻는다. Sakoe-Chiba 밴드는 정렬이 멈춤 구간을 단일 샘플로 뭉개지 않게 한다. 나중에는 같은 Subsequence DTW 코드가 로봇 군단이 저장한 궤적에서 짧은 질의 동작과 가장 잘 맞는 구간을 찾는다.

흔한 오해

• DTW 거리는 거리 함수(metric)이다 — 삼각 부등식을 만족하지 않으며, 이는 삼각 부등식을 가정하는 인덱싱과 군집화 방법에서 중요하다
• DTW는 시퀀스 사이의 어떤 차이든 처리한다 — DTW가 흡수하는 것은 타이밍의 차이이지 값의 오프셋이나 스케일 차이가 아니므로, 보통 먼저 특징을 정규화해야 한다
• 제약 없는 DTW가 가장 좋은 정렬을 준다 — 윈도가 없으면 한 샘플을 다른 시퀀스의 긴 구간과 짝지어, 물리적 의미가 없는 워핑을 만들 수 있다
• DTW는 실제로 쓰기에는 너무 느리다 — 띠 제약, 하한, 근사 방법 덕분에 많은 실시간 및 대규모 용도에 충분히 빠르다

알아야 할 사람

• 시연 학습 연구자
• 로봇 궤적과 로그를 분석하는 엔지니어
• 제스처 및 활동 인식 개발자
• 내비게이션 및 매니퓰레이션 정책을 평가하는 연구자

관련 기술

• Soft-DTW
• Sakoe-Chiba 밴드
• Subsequence DTW
• FastDTW
• tslearn

관련 용어

• Dynamic Movement Primitive
• Imitation Learning
• Kinesthetic Teaching
• Behavior Cloning
• Success Weighted by Path Length

관련 프로젝트

• PlotJuggler: Fast time-series visualization tool for ROS topics, rosbags, and robot debugging

동영상

• How DTW (Dynamic Time Warping) algorithm works: Thales Sehn Körting