Zgięcie Dynamiczne Czasu: Dopasowywanie Sekwencji Czasowych

Dlaczego porównywanie w linii prostej zawodzi

Dwie osoby podpisujące to samo słowo lub dwa czujniki rejestrujące tę samą gest, rzadko poruszają się dokładnie z tym samym tempem. Porównując te nagrania punkt po punkcie w czasie, nawet niewielkie opóźnienie sprawia, że wyglądają zupełnie inaczej, mimo że kształty są identyczne. Dynamiczne wyglenie czasu rozwiązuje to, pozwalając na lokalne rozciąganie i ściskanie osi czasowej jednej serii tak, aby podobne cechy się dopasowały, a następnie mierząc koszt najlepszego takiego dopasowania.

Macierz kosztów

Dany szereg X o długości n i szereg Y o długości m, zbuduj macierz n x m, w której komórka (i, j) zawiera najtańszą sumaryczną cenę dopasowania X do i z Y do j. Każda komórka potrzebuje jedynie odległości punktowej między X[i] a Y[j] plus najniższą wartość spośród trzech sąsiednich komórek, z których mogła pochodzić – bezpośrednio powyżej, bezpośrednio w lewo lub po przekątnej powyżej i w lewo, co odpowiada postępowi tylko w Y, tylko w X lub razem.

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

Wypukła ścieżka i jej ograniczenia

Śledząc najtańszą drogę przez macierz, od lewego górnego rogu do prawego dolnego, otrzymujemy wypukłą ścieżkę – rzeczywistą korespondencję między indeksami X i Y. Trzy zasady utrzymują sensowność wyrównania: musi się ona rozpocząć w punkcie (1,1) i zakończyć w punkcie (n,m) (graniczny), może poruszać się tylko w prawo, w dół lub po przekątnej, nigdy wstecz w żadnym z szeregów (monotoniczność) oraz nie może pomijać żadnego indeksu w żadnym z szeregów (ciągłość). Razem to oznacza, że każdy pojedynczy punkt w X może mapować się na kilka kolejnych punktów w Y i odwrotnie – dokładnie lokalne rozciąganie, które wyrównuje różnice w tempie.

Ograniczanie poszukiwań: pasma Sakoe-Chiba

Niekontrolowany algorytm powyżej kosztuje O(n razy m) pod względem czasu i pamięci, a niekontrolowana ścieżka w zasadzie może się tak bardzo wygiąć, że generuje semantycznie bezsensowną wyrównanie - bardzo krótki segment rozciągnięty, aby pasował do długiego. Pasmo Sakoe-Chiba, wprowadzone w literaturze o rozpoznawaniu mowy, ogranicza ścieżkę do korytarza wokół przekątnej, o szerokości równej stałemu liczbie kroków, co zapobiega degeneracyjnym wyrównaniom i redukuje obliczenia do około O(n razy szerokość pasma).

Gdzie jest używane

Algorytm DTW był centralny dla wczesnego rozpoznawania mowy, gdzie to samo wypowiedzone słowo nigdy nie zajmuje dokładnie tych samych sekund. Pozostaje standardową miarą podobieństwa do rozpoznawania gestów, analizy chodu, dopasowywania wzorców cen akcji o różnej długości oraz ogólnie klasyfikacji lub grupowaniu szeregów czasowych, zwykle w połączeniu z klasyfikatorem najbliższego sąsiada, ponieważ miara DTW sama w sobie, a nie model nabytego, dokonuje porównania.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Dynamic Time Warping i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.