Динамічне вирівнювання часу: узгодження часових рядів

Чому порівняння прямої лінії не спрацьовує

Двоє людей, які підписують одне й те саме слово, або два датчики, що фіксують один і той самий жест, рідко рухаються з абсолютно однаковою швидкістю. Порівняйте записи по пунктах у часі, і навіть найменша затримка робить їх зовсім різними, незважаючи на те, що форми ідентичні. Динамічне викривлення часу вирішує цю проблему, дозволяючи локально змінювати часову вісь одного ряду, розтягуючи або стискаючи її, щоб подібні ознаки співпадали, а потім вимірюючи вартість найкращого такого вирівнювання.

Матриця вартості

Враховуючи серію X довжиною n та серію Y довжиною m, побудуйте матрицю розміром n x m, де елемент (i, j) містить найдешевшу сукупну вартість вирівнювання X до i з Y до j. Кожен елемент потребує лише поточної відстані між X[i] та Y[j], а також найдешевшу з трьох сусідніх елементів, з яких він міг прийти – безпосередньо зверху, безпосередньо зліва або діагонально зверху-зліва, що відповідає лише просуванню в Y, лише в X або разом.

D[0][0] = 0;
for (let i = 1; i <= n; i++) D[i][0] = Infinity;
for (let j = 1; j <= m; j++) D[0][j] = Infinity;
for (let i = 1; i <= n; i++)
  for (let j = 1; j <= m; j++) {
    const cost = Math.abs(X[i-1] - Y[j-1]);
    D[i][j] = cost + Math.min(D[i-1][j], D[i][j-1], D[i-1][j-1]);
  }
// D[n][m] is the DTW distance; backtrack from (n,m) to (0,0) for the warping path

Викривлений шлях та його обмеження

Відстежування найдешевшого шляху через матрицю від верхнього лівого кута до нижнього правого дає викривлення шляху – фактичну відповідність між індексами X та індексами Y. Три правила забезпечують розумність вирівнювання: він повинен починатися з (1,1) і закінчуватися в (n,m) (межа), може рухатися лише праворуч, вниз або по діагоналі, ніколи назад у будь-якій серії (монотонність), і не може пропускати індекс у будь-якій серії (безперервність). Разом це означає, що будь-яка окрема точка в X може відображатися на кілька послідовних точок у Y і навпаки – саме локальне розтягування, яке підтримує невідповідність швидкості.

Обмеження пошуку: смуга Сакоє-Чіба

Необмежений алгоритм, описаний вище, коштує O(n разів m) як за часом, так і за пам’яттю. Необмежена траєкторія теоретично може спотворитися настільки агресивно, що виробляє технічно дешевий, але семантично беззмістовний вирівнювання – дуже короткий сегмент, розтягнутий для відповідності довгому. Смуга Сакоє-Чіба, представлена в літературі з розпізнавання мовлення, обмежує траєкторію коридором навколо діагоналі, зав шириною фіксованої кількості кроків, що запобігає дегенеративним вирівнюванням і зменшує обчислювальні витрати приблизно до O(n разів ширині смуги).

Де це використовується

Відстань DTW була центральною в ранжових розпізнавачах мовлення, де одна й та сама вимовлена фраза ніколи не займає точно однакової кількості часу двічі. Вона залишається стандартним показником подібності для розпізнавання жестів, аналізу ходи, порівняння патернів цін на акції різної тривалості та, загалом, кластеризації або класифікації часових рядів, зазвичай у поєднанні з класифікатором найближчого сусіда, оскільки саме відстань DTW, а не навчена модель, виконує порівняння.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Dynamic Time Warping і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.