UK 
EnglishТипова
Polski〰️ Динамічна трансформація часу — вирівнювання рядів
Динамічна трансформація часу вирівнює два часові ряди різної швидкості, деформуючи вісь часу. ДП-матриця вартості знаходить найдешевший шлях деформації — основа розпізнавання мовлення й жестів.
Про динамічну трансформацію часу — вирівнювання часових рядів
Динамічна трансформація часу (DTW) — алгоритм, що вимірює подібність між двома часовими рядами, які можуть відрізнятися швидкістю, довжиною чи фазою, еластично деформуючи вісь часу. Він будує накопичену матрицю вартості за допомогою динамічного програмування, а потім відновлює оптимальний шлях деформації — найдешевшу послідовність пар індексів, що вирівнює обидва ряди від початку до кінця. Ця симуляція дозволяє спостерігати матрицю вартості як теплову карту, стежити за формуванням жовтого шляху деформації та порівнювати відстань DTW з наївною евклідовою відстанню.
DTW вперше формалізували для автоматичного розпізнавання мовлення в 1970-х роках, і він досі залишається наріжною технікою в аналізі часових рядів, біоінформатиці, фінансах і розпізнаванні жестів.
Часті запитання
Що насправді вимірює динамічна трансформація часу?
DTW вимірює мінімальну загальну вартість вирівнювання двох часових рядів, дозволяючи кожній точці одного ряду відповідати одній чи кільком послідовним точкам іншого. На відміну від евклідової відстані, яка жорстко пов'язує точки на однакових часових індексах, DTW розтягує й стискає вісь часу, тож подібні форми з різними швидкостями чи зсувами дають малу відстань. Результат — єдина скалярна відстань: менше значення означає більшу подібність форми.
Як користуватися цією симуляцією?
Оберіть пресетну пару сигналів (зсув фази, деформація швидкості чи два горби) кнопками режиму на лівій панелі. Налаштуйте повзунок смуги Сакое-Чіба, щоб обмежити шлях деформації, і повзунок шуму, щоб додати випадковість до сигналів, потім натисніть Recompute для перерахунку. Теплова карта праворуч показує накопичену матрицю вартості D, жовта діагональна лінія — оптимальний шлях деформації, а лінії вирівнювання на верхній правій панелі показують, які індекси зіставлені між двома рядами.
Чому відстань DTW менша за евклідову для зсунутих у часі сигналів?
Коли два сигнали ідентичні за формою, але зсунуті в часі, евклідова відстань вимірює порівняння точка-в-точку на кожному індексі, що може бути великим навіть для дуже подібних форм. DTW натомість знаходить оптимальну відповідність між точками, фактично зсуваючи й розтягуючи вісь часу, тож піки збігаються з піками, а западини — з западинами. Для пресету «Зсув фази» в цій симуляції ви зазвичай побачите, що відстань DTW значно менша за евклідову.
Яка рекурентність динамічного програмування лежить в основі DTW?
Для рядів X довжини n і Y довжини m визначте локальну вартість d(i,j) = (X[i] - Y[j])^2. Накопичена матриця вартості D підкоряється D(i,j) = d(i,j) + min(D(i-1,j), D(i,j-1), D(i-1,j-1)), з D(0,0) = d(0,0). Це дозволяє кожному кроку йти зліва (повтор Y), зверху (повтор X) чи по діагоналі (просування обох). Відстань DTW дорівнює sqrt(D(n-1, m-1)), а оптимальний шлях відновлюється жадібним зворотним проходом з нижнього правого кута до верхнього лівого.
Що таке смуга Сакое-Чіба і чому вона важлива?
Смуга Сакое-Чіба — глобальне обмеження, введене Хіроакі Сакое та Сейбі Чіба в їхній роботі 1978 року, яке обмежує шлях деформації в межах |i - j| <= r кроків від головної діагоналі. Без смуги DTW має складність O(nm) за часом і пам'яттю та може створювати патологічні деформації, коли одна точка одного ряду зіставляється з усім іншим рядом. Додавання смуги зменшує складність до O(n * r), запобігає екстремальним деформаціям і часто покращує точність класифікації на практиці. У цій симуляції можна побачити, як обмежені смугою комірки темніють на тепловій карті.
Де DTW використовується в реальному світі?
DTW використовується в системах розпізнавання мовлення (зіставлення вимовлених слів з різними швидкостями), розпізнаванні рукописного тексту й жестів на сенсорних екранах і датчиках руху, кластеризації фінансових часових рядів, аналізі медичних сигналів (порівняння ЕКГ чи ЕЕГ між пацієнтами) та біоінформатиці (вирівнювання часових профілів експресії генів). Багато сучасних бібліотек машинного навчання, як-от tslearn і stumpy, включають оптимізовані реалізації DTW.
Яке поширене хибне уявлення про DTW?
Поширене хибне уявлення полягає в тому, що DTW завжди кращий за евклідову відстань для задач часових рядів. Насправді для дуже довгих рядів або рядів без значущої варіації осі часу DTW може перенавчитися на деформації та фактично працювати гірше за евклідову відстань у класифікації. Дослідження Дінга та ін. (2008) показало, що для багатьох еталонних наборів даних метод одного найближчого сусіда з евклідовою відстанню конкурентоспроможний з DTW.
Хто винайшов DTW і коли?
Формальне формулювання DTW динамічного програмування для розпізнавання мовлення представили Хіроакі Сакое та Сейбі Чіба в NTT в Японії, з їхньою знаковою роботою «Dynamic programming algorithm optimization for spoken word recognition», опублікованою в IEEE Transactions on Acoustics, Speech, and Signal Processing в 1978 році. Однак подібні ідеї еластичного зіставлення з'явилися незалежно на початку 1970-х у роботі Вінцюка (1968, СРСР) з вирівнювання мовлення та алгоритмі Нідлмана-Вунша для вирівнювання послідовностей у біоінформатиці (1970).
Які інші алгоритми пов'язані з DTW?
DTW тісно пов'язаний з алгоритмами Нідлмана-Вунша та Сміта-Уотермана, що використовуються для вирівнювання біологічних послідовностей і вирішують по суті ту саму задачу динамічного програмування з різними штрафами за розриви. Відстань редагування (відстань Левенштейна) на послідовностях символів є дискретним аналогом. Для ймовірнісного моделювання часових послідовностей приховані марковські моделі узагальнюють ідею DTW у стохастичну структуру. Uniform Time Warping і Derivative DTW (DDTW), що обчислює DTW на першій похідній ряду, є прямими варіантами.
Як DTW використовується в сучасному машинному навчанні та інженерії?
В інженерії та машинному навчанні DTW слугує метрикою відстані в класифікаторах k-найближчих сусідів для часових рядів, функцією втрат для нейронних мереж послідовність-у-послідовність (soft-DTW) та мірою подібності в кластеризації часових рядів і виявленні аномалій. Використовується в промисловому IoT для порівняння показань датчиків машин, що працюють з різними швидкостями, у спортивній аналітиці для порівняння рухів атлетів, і в обробці аудіо для вирівнювання записів.
Які поточні напрями досліджень у вирівнюванні часових рядів?
Активні напрями досліджень включають Soft-DTW — диференційовне наближення DTW, що дозволяє оптимізацію на основі градієнта і використовується як функція втрат при навчанні нейронних моделей послідовностей. FastDTW і PrunedDTW — наближені алгоритми, що досягають майже лінійної часової складності. Методи на основі шейплетів навчають дискримінативні підпослідовності замість обчислення повних попарних відстаней. Також зростає інтерес до відстаней оптимального транспорту, як-от відстань Вассерштейна, та до DTW з прискоренням на GPU для дуже довгих біомедичних і кліматичних часових рядів.