동적 시간 워핑(DTW)은 속도, 지속 시간 또는 위상이 다를 수 있는 두 시계열 시퀀스 간의 최적 정렬을 계산하는 알고리즘입니다. 동일한 시간 인덱스의 점들을 비교하는 유클리드 거리와 같은 단순한 거리 측정과 달리, DTW는 시간 축의 비선형 워핑을 허용하여 시퀀스 간의 최상의 일치를 찾습니다. 이러한 특성으로 인해 DTW는 서로 다른 속도로 발화된 음성, 필기 문자 또는 서로 다른 장치의 센서 판독값과 같이 시간적 변동성을 보이는 신호를 비교하는 데 특히 효과적입니다.
이 알고리즘은 1970년대 음성 인식 맥락에서 도입되었으며, 기계 학습 모델이 널리 채택되기 전의 기초 기술이 되었습니다. 핵심 원리는 동적 프로그래밍입니다. 두 시퀀스의 모든 점 쌍 간의 거리를 누적하는 비용 행렬을 구성한 다음, 총 누적 거리를 최소화하는 이 행렬을 통과하는 경로를 찾습니다. 결과 워핑 경로는 한 시퀀스의 어느 점이 다른 시퀀스의 어느 점에 해당하는지 나타내며, 최종 DTW 거리는 이 최적 경로를 따른 거리의 합입니다.
역사적 발전
DTW에 대한 최초의 발표된 연구는 종종 히로아키 사코에와 세이비 치바에 기인하며, 이들은 1978년 효율성과 견고성을 개선하기 위한 제약 조건으로 알고리즘을 공식화했습니다. 그들의 논문 "동적 프로그래밍 알고리즘 최적화를 통한 음성 단어 인식"은 허용 가능한 워핑 창을 제한하여 계산 비용을 줄이고 병리적 정렬을 방지하는 일반적인 제약 조건인 사코-치바 밴드를 도입했습니다. 같은 시기에 제록스 팔크 및 다른 기관의 연구자들도 패턴 매칭을 위한 유사한 동적 프로그래밍 접근 방식을 탐구했지만, 사코와 치바의 공식화가 표준 참조가 되었습니다.
1980년대 동안 DTW는 음성 시스템의 고립 단어 인식에서 지배적인 방법이었으며, 종종 전용 하드웨어에 구현되었습니다. 이후 은닉 마르코프 모델(HMM)과 더 최근에는 딥 러닝 기반 접근 방식(예: 신경망 기반 음향 모델)으로 대체되었습니다. 그러나 DTW는 벤치마크 및 훈련 데이터 정렬 도구로서 영향력을 유지했습니다.
알고리즘 세부 사항
DTW 알고리즘은 X = (x1, x2, ..., xn) 및 Y = (y1, y2, ..., ym)의 두 시퀀스에서 작동하며, 여기서 각 xi 및 yj는 특징 벡터(종종 스칼라 값 또는 다차원 점)입니다. 알고리즘은 n x m 행렬 D를 구축하며, 각 셀 D(i, j)는 해당 셀에서 끝나는 최상의 정렬의 누적 거리를 포함합니다. 반복 관계는 다음과 같습니다.
D(i, j) = d(xi, yj) + min(D(i-1, j), D(i, j-1), D(i-1, j-1))
여기서 d(xi, yj)는 국소 거리 측정으로, 연속 데이터의 경우 일반적으로 유클리드 거리, 스칼라 값의 경우 절대 차이입니다. 최종 DTW 거리는 D(n, m)이며, 최적 워핑 경로는 해당 셀에서 역추적하여 복구할 수 있습니다.
효율성을 개선하고 퇴화 정렬을 피하기 위해 몇 가지 제약 조건이 일반적으로 적용됩니다. 사코-치바 밴드는 워핑 경로를 고정 폭 대각선 밴드로 제한하여 탐색 공간을 O(nm)에서 O(n대역폭)으로 줄입니다. 후미타다 이타쿠라의 이름을 딴 이타쿠라 평행사변형은 경로의 기울기를 제한하는 기울기 제약 조건을 사용합니다. 또한 경계 조건은 경로가 (1,1)에서 시작하여 (n,m)에서 끝나야 하며, 단조성은 인덱스가 절대 감소하지 않도록 보장합니다.
응용 분야
DTW는 많은 분야에서 응용되고 있습니다. 음성 인식에서는 특히 소규모 어휘 작업에서 음성 단어를 템플릿과 비교하는 데 사용되었습니다. 시계열 분석(관련 분야이지만 제공된 슬러그 목록에는 없음)에서 DTW는 클러스터링 및 분류를 위한 표준 도구이며, 시간적 정렬이 잘못된 데이터 세트에서 종종 유클리드 거리보다 우수한 성능을 보입니다. 예를 들어, 가속도계 데이터의 제스처 인식에서 DTW는 서로 다른 속도로 수행된 제스처를 일치시킬 수 있습니다.
생물정보학에서 DTW는 유전자 발현 프로필 또는 단백질 서열을 정렬하는 데 적용되었지만, Needleman-Wunsch와 같은 서열 정렬 알고리즘보다는 덜 일반적입니다. 금융에서 DTW는 시간에 따른 주가 움직임 또는 경제 지표를 비교하는 데 사용됩니다. 로봇 공학에서 DTW는 시연 학습을 위해 서로 다른 시행의 센서 판독값을 정렬하는 데 도움이 됩니다. 이 알고리즘은 또한 기존 시계열을 워핑하여 합성 훈련 예제를 생성하는 데이터 증강에도 사용됩니다.
변형 및 확장
특정 한계를 해결하기 위해 여러 DTW 변형이 개발되었습니다. 미분 DTW(DDTW)는 원시 값 대신 시퀀스의 1차 도함수를 사용하여 오프셋 및 스케일 차이에 더 강건합니다. 가중 DTW는 특징 벡터의 다른 차원에 다른 가중치를 할당합니다. 2017년 Marco Cuturi와 Mathieu Blondel이 도입한 Soft-DTW는 min 연산을 소프트 최소값으로 대체하여 거리를 미분 가능하게 만들고 딥 러닝 파이프라인에서 손실 함수로 사용할 수 있게 합니다.
다변량 DTW는 여러 채널이 있는 시퀀스를 처리하고, 부분 시퀀스 DTW는 더 긴 시퀀스 내에서 최상의 일치 부분 시퀀스를 찾습니다. 대규모 데이터 세트의 경우 FastDTW와 같은 근사 방법은 다중 스케일 접근 방식을 사용하여 계산 복잡성을 줄입니다. 이러한 확장은 특히 미분 가능한 버전이 엔드투엔드 훈련을 가능하게 하는 기계 학습 맥락에서 DTW를 현대 연구에서 관련성 있게 유지했습니다.
현대 AI와의 관계
DTW는 딥 러닝 방법은 아니지만 인공 지능 시대에도 여전히 관련성이 있습니다. 시계열을 신경망 모델(예: 시퀀스 예측을 위한 잔차 네트워크 또는 유넷 아키텍처)에 공급하기 전에 정렬하는 전처리 단계로 자주 사용됩니다. 음성 인식(슬러그 목록에 없는 개념)에서 DTW는 저자원 환경의 키워드 스팟팅에 여전히 사용됩니다. 동적 프로그래밍의 알고리즘 원리는 시퀀스-투-시퀀스 모델에도 나타나며, 여기서 정렬은 주의 메커니즘을 통해 암시적으로 학습됩니다.
MIT CSAIL 및 스탠포드 AI 랩과 같은 기관의 연구자들은 시계열 분류 및 이상 탐지 작업을 위해 DTW와 딥 러닝을 결합한 하이브리드 접근 방식을 탐구했습니다. Soft-DTW의 미분 가능성은 시간적 정렬이 필요한 모델 훈련을 위한 손실 함수에 통합할 수 있게 했습니다. 2020년대 초반 현재 DTW는 시계열 벤치마크에서 표준 기준선으로 계속 사용되며, 계산 효율성은 GPU 및 AWS 트레이니엄 하드웨어 최적화와 함께 연구 주제로 남아 있습니다.