Dynamiczne zakrzywianie czasu

Dwa powtórzenia sekwencji chodu nagrane za pomocą systemu motion-capture. Chociaż istnieją różnice w szybkości chodu między powtórzeniami, przestrzenne ścieżki kończyn pozostają bardzo podobne.

W analizie szeregów czasowych dynamiczne dopasowanie czasu ( DTW ) to algorytm pomiaru podobieństwa między dwiema sekwencjami czasowymi, które mogą różnić się szybkością . Na przykład podobieństwa w chodzeniu można wykryć za pomocą DTW, nawet jeśli jedna osoba szła szybciej niż druga lub jeśli podczas obserwacji występowały przyspieszenia i opóźnienia. DTW zostało zastosowane do czasowych sekwencji danych wideo, audio i graficznych — w rzeczywistości każde dane, które można przekształcić w sekwencję liniową, można przeanalizować za pomocą DTW. Dobrze znaną aplikacją jest automatyczne rozpoznawanie mowy , aby poradzić sobie z różnymi prędkościami mówienia. Inne zastosowania obejmują rozpoznawanie mówców i rozpoznawanie podpisów online . Może być również używany w dopasowywania częściowego kształtu .

Ogólnie rzecz biorąc, DTW jest metodą, która oblicza optymalne dopasowanie dwóch danych sekwencji (np. szeregów czasowych ) z pewnymi ograniczeniami i regułami:

Każdy indeks z pierwszej sekwencji musi być dopasowany do jednego lub większej liczby indeksów z drugiej sekwencji i odwrotnie
Pierwszy indeks z pierwszej sekwencji musi być dopasowany do pierwszego indeksu z drugiej sekwencji (ale nie musi to być jej jedyne dopasowanie)
Ostatni indeks z pierwszej sekwencji musi być dopasowany do ostatniego indeksu z drugiej sekwencji (ale nie musi to być jej jedyne dopasowanie)
Odwzorowanie indeksów z pierwszej sekwencji na indeksy z drugiej sekwencji musi być monotonicznie rosnące i odwrotnie, tj. jeśli są indeksami z pierwszej sekwencji, to nie $indeksów$ ${\ Displaystyle l> k}$ w drugiej kolejności, tak że indeks $j$ dopasowany do indeksu, a indeks jest dopasowany do indeksu ${\ displaystyle j}$ $}$ $\ displaystyle$ i odwrotnie

Optymalne dopasowanie oznacza dopasowanie, które spełnia wszystkie ograniczenia i reguły oraz ma minimalny koszt, gdzie koszt jest obliczany jako suma bezwzględnych różnic, dla każdej dopasowanej pary indeksów, między ich wartościami.

Sekwencje są „wypaczane” nieliniowo w wymiarze czasu, aby określić miarę ich podobieństwa, niezależnie od pewnych nieliniowych zmian w wymiarze czasu. Ta dopasowania sekwencji jest często stosowana w klasyfikacji szeregów czasowych. Chociaż DTW mierzy wielkość podobną do odległości między dwoma danymi sekwencjami, nie gwarantuje to utrzymania nierówności trójkąta .

Oprócz miary podobieństwa między dwiema sekwencjami, tworzona jest tak zwana „ścieżka odkształcenia”, przez odkształcenie zgodnie z tą ścieżką dwa sygnały mogą być wyrównane w czasie. Sygnał z oryginalnym zestawem punktów X (oryginalny), Y (oryginalny) jest przekształcany na X (wypaczony), Y (wypaczony). Znajduje to zastosowanie w sekwencji genetycznej i synchronizacji dźwięku. W pokrewnej technice sekwencje o różnej szybkości mogą być uśredniane za pomocą tej techniki, patrz uśredniania sekwencji .

Jest to koncepcyjnie bardzo podobne do algorytmu Needlemana – Wunscha .

Realizacja

Ten przykład ilustruje implementację algorytmu dynamicznego dopasowania czasu, gdy dwie sekwencje s i t są ciągami dyskretnych symboli. Dla dwóch symboli x i y d(x, y) jest odległością między symbolami, np. d (x, y) = ${\ Displaystyle | xy |}$ .

int DTWOdległość(s: tablica [1..n], t: tablica [1..m]) { DTW := tablica [0..n, 0..m] dla i := 0 do n dla j := 0 do m DTW[i, j] := nieskończoność DTW[0, 0] := 0 dla i := 1 do n dla j := 1 do m koszt := d(s[i], t[j]) DTW[i, j] := koszt + minimum(DTW[i-1, j ], // wstawienie DTW[i , j-1], // usunięcie DTW[i-1, j-1]) // dopasowanie powrót DTW[n, m] }

gdzie DTW[i, j] to odległość między s[1:i] a t[1:j] z najlepszym wyrównaniem.

Czasami chcemy dodać ograniczenie dotyczące lokalizacji. Oznacza to, że jeśli s[i] jest dopasowane do t[j] , to ${\ Displaystyle | ij|}$ nie jest większy niż w , parametr okna.

Możemy łatwo zmodyfikować powyższy algorytm, dodając ograniczenie lokalności (różnice zaznaczono ). Jednak powyższa modyfikacja działa tylko wtedy, gdy ${\ Displaystyle | nm|}$ nie jest większy niż w , tj. punkt końcowy znajduje się w obrębie długości okna od przekątnej. Aby algorytm działał, parametr okna w musi być dostosowany tak, aby ${\ Displaystyle | nm | \ równoważnik w}$ (patrz linia oznaczona (*) w kodzie).

        
             int DTWOdległość(s: tablica [1..n], t: tablica [1..m]  , w: int  ) { DTW := tablica [0..n, 0..m]  w := max(w, abs(nm))  // dostosowanie rozmiaru okna (*) dla i := 0 do n dla j:= 0 do m DTW[i, j] := nieskończoność DTW[0, 0] := 0 dla i :=  1 do n  dla j := max(1, iw) do min(m, i+w)  DTW[i, j] := 0  dla i := 1 do n dla j :=  max(1, iw) do min( m, i+w)  koszt := d(s[i], t[j]) DTW[i, j] := koszt + minimum(DTW[i-1, j ], // wstawienie DTW[i , j -1], // usuwanie DTW[i-1, j-1]) // powrót dopasowania DTW[n, m] }

Właściwości wypaczające

Algorytm DTW tworzy dyskretne dopasowanie między istniejącymi elementami jednej serii do drugiej. Innymi słowy, nie pozwala na skalowanie czasowe segmentów w sekwencji. Inne metody pozwalają na ciągłe wypaczanie. Na przykład Correlation Optimized Warping (COW) dzieli sekwencję na jednorodne segmenty, które są skalowane w czasie przy użyciu interpolacji liniowej, aby uzyskać najlepiej dopasowane wypaczenie. Skalowanie segmentów powoduje potencjalne tworzenie nowych elementów poprzez skalowanie segmentów w czasie w dół lub w górę, a tym samym powoduje bardziej czułe wypaczanie niż dyskretne dopasowywanie surowych elementów przez DTW.

Złożoność

$Złożoność$ algorytmu $,$ $są$ gdzie i dwóch 50-letnia kwadratowa granica czasu została złamana w 2016 roku: algorytm dzięki Goldowi i Sharir umożliwia obliczenie DTW w ${\ Displaystyle O ({N ^ {2}}/\ log \ log N)}$ czas i przestrzeń dla dwóch sekwencji wejściowych o długości ${\ displaystyle N}$ . Algorytm ten można również dostosować do sekwencji o różnej długości. $ϵ$ wykazano, że silnie subkwadratowy czas działania postaci niektórych $\ Displaystyle \$ cannot exist unless the Strong exponential time hypothesis fails.

Podczas gdy algorytm programowania dynamicznego dla DTW wymaga $(N,M))}$ $)$ implementacji, zużycie miejsca można zmniejszyć do $\ Displaystyle O ($ za pomocą algorytmu Hirschberga .

Szybkie obliczenia

Szybkie techniki obliczania DTW obejmują Early Abandoned i Pruned DTW, PrunedDTW, SparseDTW, FastDTW i MultiscaleDTW.

Typowe zadanie, pobieranie podobnych szeregów czasowych, można przyspieszyć, stosując dolne granice, takie jak LB_Keogh, LB_Improved, LB_Enhanced, LB_Webb lub LB_Petitjean. Jednak algorytm Early Abandon and Pruned DTW zmniejsza stopień przyspieszenia, jaki zapewnia dolna granica, a czasami czyni go nieefektywnym.

W ankiecie Wang i in. zgłosił nieco lepsze wyniki z dolną granicą LB_Improved niż LB_Keogh i stwierdził, że inne techniki były nieefektywne. Po tej ankiecie opracowano ograniczenie LB_Enhanced, które jest zawsze ściślejsze niż LB_Keogh, a jednocześnie jest bardziej wydajne w obliczeniach. LB_Petitjean jest najściślejszą znaną dolną granicą, którą można obliczyć w czasie liniowym.

Średnia sekwencja

Uśrednianie dla dynamicznego dopasowania czasu to problem znalezienia średniej sekwencji dla zestawu sekwencji. NLAAF to dokładna metoda uśredniania dwóch sekwencji przy użyciu DTW. W przypadku więcej niż dwóch sekwencji problem jest związany z wielokrotnym dopasowaniem i wymaga zastosowania heurystyki. DBA jest obecnie metodą referencyjną do uśredniania zestawu sekwencji zgodnie z DTW. COMASA skutecznie randomizuje wyszukiwanie średniej sekwencji, wykorzystując DBA jako lokalny proces optymalizacji.

Nadzorowana nauka

najbliższego sąsiedztwa może osiągnąć najnowocześniejszą wydajność, używając dynamicznego dopasowania czasu jako miary odległości.

Dynamiczne wypaczanie czasu Amerced

Amerced Dynamic Time Warping (ADTW) to wariant DTW zaprojektowany w celu lepszej kontroli permisywności DTW w wyrównaniach, na które pozwala. Okna, których używa klasyczne DTW do ograniczania linii trasowania, wprowadzają funkcję schodkową. Jakiekolwiek wypaczenie ścieżki jest dozwolone w obrębie okna i żadne poza nim. W przeciwieństwie do tego ADTW stosuje dodatkową karę, która jest nakładana za każdym razem, gdy ścieżka jest wypaczona. Dowolna ilość wypaczeń jest dozwolona, ale każde wypaczenie pociąga za sobą bezpośrednią karę. ADTW znacznie przewyższa DTW z okienkowaniem, gdy jest stosowany jako klasyfikator najbliższego sąsiada w zestawie wzorcowych zadań klasyfikacji szeregów czasowych.

Alternatywne podejścia

W funkcjonalnej analizie danych szeregi czasowe są traktowane jako dyskretyzacje gładkich (różniczkowalnych) funkcji czasu. Oglądając obserwowane próbki przy gładkich funkcjach, można wykorzystać ciągłą matematykę do analizy danych. Gładkość i monotoniczność funkcji dopasowania czasowego można uzyskać na przykład przez całkowanie zmiennej w czasie radialnej funkcji bazowej , będąc tym samym jednowymiarowym dyfeomorfizmem . Optymalne nieliniowe funkcje dopasowania czasu są obliczane poprzez minimalizację miary odległości zestawu funkcji do ich odkształconej średniej. Wyrazy kary za chropowatość dla funkcji wypaczania mogą być dodane, np. poprzez ograniczenie wielkości ich krzywizny. Wynikowe funkcje wypaczania są gładkie, co ułatwia dalszą obróbkę. Podejście to zostało z powodzeniem zastosowane do analizy wzorców i zmienności ruchów mowy.

Innym pokrewnym podejściem są ukryte modele Markowa (HMM) i wykazano, że algorytm Viterbiego używany do wyszukiwania najbardziej prawdopodobnej ścieżki przez HMM jest równoważny stochastycznemu DTW.

DTW i powiązane metody wypaczania są zwykle używane jako etapy przed lub po przetwarzaniu w analizach danych. Jeśli obserwowane sekwencje zawierają zarówno przypadkowe zmiany zarówno ich wartości, kształtu obserwowanych sekwencji, jak i przypadkowe przesunięcie czasowe, wypaczenie może nadmiernie dopasować się do szumu, co prowadzi do tendencyjnych wyników. Równoczesne sformułowanie modelu z losową zmiennością zarówno wartości (pionowych), jak i parametryzacji czasowej (poziomej) jest przykładem nieliniowego modelu z efektami mieszanymi . W analizie ruchu człowieka wykazano, że jednoczesne nieliniowe modelowanie efektów mieszanych daje lepsze wyniki w porównaniu z DTW.

Oprogramowanie typu open source

Biblioteka tempo C++ z powiązaniami Pythona implementuje dolne granice DTW Early Abandoned i Pruned, a także Early Abandoned and Pruned ADTW i DTW LB_Keogh, LB_Enhanced i LB_Webb.
UltraFastMPSearch implementuje algorytm UltraFastWWSearch do szybkiego dostrajania okna wypaczania .
Udoskonalona biblioteka C++ implementuje algorytmy Fast Nearest-Neighbor Retrieval na licencji GNU General Public License (GPL) . Zapewnia również implementację dynamicznego dopasowania czasu w C++, a także różne dolne granice.
Biblioteka FastDTW jest implementacją DTW w Javie i implementacją FastDTW, która zapewnia optymalne lub prawie optymalne dopasowanie ze ^{złożonością czasową i pamięciową} O ( N ), w przeciwieństwie do wymagań O ( N2 ) dla standardowego algorytmu DTW. FastDTW wykorzystuje podejście wielopoziomowe, które rekursywnie projektuje rozwiązanie z bardziej zgrubnej rozdzielczości i udoskonala projektowane rozwiązanie.
Widelec FastDTW (Java) opublikowany w Maven Central.
time-szereg-klasyfikacja (Java) pakiet do klasyfikacji szeregów czasowych przy użyciu DTW w Weka.
Pakiet DTW zapewnia pakiety Pythona ( dtw-python ) i R ( dtw ) z kompleksowym pokryciem członków rodziny algorytmów DTW, w tym różnych reguł rekurencji (zwanych także wzorcami krokowymi), ograniczeń i dopasowywania podłańcuchów.
Biblioteka mlpy Python implementuje DTW.
Biblioteka Pythona pydtw implementuje miary DTW o smaku Manhattanu i Euklidesa, w tym dolne granice LB_Keogh.
Biblioteka cudadtw C++/CUDA implementuje wyrównanie podsekwencji DTW o smaku euklidesowym i znormalizowanej odległości euklidesowej, podobnie jak popularny pakiet UCR-Suite na akceleratorach obsługujących CUDA.
uczenia maszynowego JavaML implementuje DTW .
Biblioteka ndtw C# implementuje DTW z różnymi opcjami.
Sketch-a-Char wykorzystuje Greedy DTW (zaimplementowany w JavaScript) jako część programu klasyfikującego symbole LaTeX.
MatchBox implementuje DTW w celu dopasowania współczynników cepstralnych częstotliwości mel sygnałów audio.
Uśrednianie sekwencji : implementacja DBA w GPL Java.
Zestaw narzędzi do rozpoznawania gestów|GRT C++ do rozpoznawania gestów w czasie rzeczywistym implementuje DTW.
Pakiet oprogramowania PyHubs implementuje klasyfikatory DTW i najbliższego sąsiedztwa, a także ich rozszerzenia (klasyfikatory uwzględniające hubness).
Biblioteka simpledtw Python implementuje klasyczny algorytm programowania dynamicznego O ( NM ) i bazuje na Numpy. Obsługuje wartości dowolnego wymiaru, a także używa niestandardowych funkcji norm dla odległości. Jest licencjonowany na licencji MIT.
Biblioteka tslearn Pythona implementuje DTW w kontekście szeregów czasowych.
Biblioteka cuTWED CUDA Python implementuje najnowocześniejszą ulepszoną odległość edycji Time Warp przy użyciu tylko pamięci liniowej z fenomenalnymi przyspieszeniami.
DynamicAxisWarping.jl Jest implementacją Julii DTW i powiązanych algorytmów, takich jak FastDTW, SoftDTW, GeneralDTW i DTW barycenters.
Multi_DTW implementuje DTW w celu dopasowania dwóch tablic 1-D lub plików mowy 2-D (tablica 2-D) .

Aplikacje

Rozpoznawanie słów mówionych

Ze względu na różne tempo mówienia występuje nieliniowa fluktuacja wzorca mowy w funkcji osi czasu, którą należy wyeliminować. Dopasowanie DP to algorytm dopasowywania wzorców oparty na programowaniu dynamicznym (DP) , który wykorzystuje efekt normalizacji czasu, w którym fluktuacje na osi czasu są modelowane za pomocą nieliniowej funkcji dopasowania czasu. Biorąc pod uwagę dowolne dwa wzorce mowy, możemy pozbyć się ich różnic czasowych, wypaczając oś czasu jednego z nich, tak aby osiągnąć maksymalną zbieżność z drugim. Co więcej, jeśli pozwolimy funkcji wypaczania przyjąć jakąkolwiek możliwą wartość, ^{[ wyjaśnij ]} rozróżnienie między słowami należącymi do różnych kategorii będzie znacznie mniejsze . Tak więc, aby zwiększyć rozróżnienie między słowami należącymi do różnych kategorii, nałożono ograniczenia na nachylenie funkcji wypaczania.

Analiza mocy korelacji

Niestabilne zegary są używane do pokonania naiwnej analizy mocy . Aby przeciwdziałać tej obronie, stosuje się kilka technik, z których jedną jest dynamiczne zakrzywianie czasu.

Finanse i ekonometria

Dynamiczne dopasowanie czasu jest wykorzystywane w finansach i ekonometrii do oceny jakości prognozy w porównaniu z danymi ze świata rzeczywistego.

Zobacz też

Dalsza lektura

Pavel Senin, Przegląd algorytmu dynamicznego dopasowania czasu
Vintsyuk, TK (1968). „Dyskryminacja mowy przez programowanie dynamiczne”. Kibernetika . 4 : 81–88.
Sakoe, H.; Chiba (1978). „Optymalizacja algorytmu programowania dynamicznego do rozpoznawania słów mówionych”. Transakcje IEEE dotyczące akustyki, mowy i przetwarzania sygnałów . 26 (1): 43–49. doi : 10.1109/tassp.1978.1163055 . S2CID 17900407 .
Myers, CS; Rabiner, LR (1981). „Studium porównawcze kilku dynamicznych algorytmów wypaczania czasu w celu rozpoznawania połączonych słów”. Dziennik techniczny systemu Bell . 60 (7): 1389-1409. doi : 10.1002/j.1538-7305.1981.tb00272.x . ISSN 0005-8580 . S2CID 12857347 .
Rabiner, Lawrence; Juang, Biing-Hwang (1993). „Rozdział 4: Techniki porównywania wzorców”. Podstawy rozpoznawania mowy . Englewood Cliffs, NJ: PTR Prentice Hall. ISBN 978-0-13-015157-5 .
Müller, Meinard (2007). Dynamiczne wypaczanie czasu. W Wyszukiwanie informacji o muzyce i ruchu, rozdział 4, strony 69-84 (PDF) . Skoczek. doi : 10.1007/978-3-540-74048-3 . ISBN 978-3-540-74047-6 .
Rakthanmanon, Thanawin (wrzesień 2013). „Adresowanie szeregów czasowych Big Data: wydobywanie bilionów podsekwencji szeregów czasowych w ramach dynamicznego dopasowania czasu” . Transakcje ACM dotyczące odkrywania wiedzy na podstawie danych . 7 (3): 10:1–10:31. doi : 10.1145/2513092.2500489 . PMC 6790126 . PMID 31607834 .