Dynamické borcení časové osy (DTW) jako metoda synchronizace (nejen) stratigrafických sekvencí "Problemstellung" ● ●
●
●
Referenční a srovnávaný signál (např. MS-křivka), sekvence měřených bodů. Časovou osu neznáme, pouze víme, že je v nelineárním monotónním vztahu k hloubkové ose (proměnlivá sedimentační rychlost, neúplnost sedim. záznamu). Též amplitudy srovnávaných signálů korelují jen volně (MS vlastnosti materiálu, kondenzovaná sedimentace. Cíl: přiřadit každému bodu srovnávané sekvence metráž sekvence referenční (stratigrafická "korelace", synchronizace).
Zdánlivě neřešitelná situace je-li nejistota v časové i amplitudové ose, jak vůbec mohu synchronizovat signály?
Ale ....
Podobný problém řeší i jiné obory : ●
●
● ●
počítačové rozpoznávání řeči , slov, řečníků, podpisů, rukopisu... medicína (EKG, EEG) , boinformatika, genová exprese... kapalinová a plynová chromatografie dolování sekvenčních dat (data mining) (Al-Naymat, 2009)
(všude, kde je třeba synchronizovat dvě časové křivky)
Existující metody ● ●
okometrie :-) Bessel’s inequality, the Fraga-Synovec 2D alignment method DTW, COW (correlation optimized warping) , OBI-Warp (Ordered Bijective Interpolated Warping)
DTW non-linear time warping
metoda synchronizace signálů se zachováním vnitřního pořadí měřených bodů zvláště vhodná pro synchronizaci sekvencí s chybějícími úseky, za předpokladu dostatečné délky sekvencí poprvé použita pro analýzu řeči (Sakoe & Chiba, 1978; Rabiner & Juang, 1993) optimalizační úloha, kombinatorická, řeší se pomocí dynamického programování (Cormen et al., 1990).
Popis metody DTW máme 2 numerické sekvence (signály): A = a1, a2, ..., ai, ..., aI ' B = b1, b2, ..., bj, ..., bJ , a míru ceny za synchronizaci: d(a[i],b[j]) hledáme nejkratší cestu maticí cen, zpravidla z bodu [1,1] do [I,J] (viz níže): F(x) | min (sum(d(1)...d(k)) .
Společná časová osa (warping function) funkce, která přibližně mapuje sekvenci A do sekvence B při minimalizaci celkové ceny .
Restriktivní podmínky 1. Monotonicita i(k – 1) ≤ i(k) and j(k – 1) ≤ j(k) 2. Kontinuita i(k) – i(k – 1) ≤ 1 and j(k) – j(k – 1) ≤ 1 3. Hraniční podmínky i(1) = 1, j(1) = 1 and i(K) = I, j(K) = J uvolněna)
neklesající funkce žádný bod se nesmí vynechat začátky a konce sekvencí si odpovídají (může být
4. Adjustační okno | i(k) – j(k) | ≤ r
5. Omezení strmosti funkce
funkce se musí vejít do určitého okolí diagonály
funkce nesmí růst, ani klesat příliš strmě
OBI-Warp Ordered Bijective Interpolated Warping
Výsledky
Co dál? Analýza spolehlivosti, odhad chyby synchronizace nejlépe posteriorní rozdělení pravděpodobnosti synchronizace daného bodu srovnávané sekvence se všemi body referenční sekvence, pro každý bod nebo alespoň 'Bayesovský interval spolehlivosti': Bayesian confidence intervals Bayesian confidence intervals are very simple. A Bayesian (1 − α)% confidence interval is simply a continuous interval on θ such that the posterior probability mass contained in that interval is 1 − α.
Jak na to?
? (chyba měření, včetně rozptylu uvnitř jedné vrstvy + prior pdf + naměřená hodnota ➳ posteriorní pdf pro intenzitu signálu v daném bodě ➳ iterace: (vzorkování + OBI-Warp) ➳ posterior pdf pro synchronizaci daného bodu ➳ B. interval spolehlivosti)
Literatura Using dynamic time warping to find patterns in time series. D Berndt, J Clifford - AAAI-94 workshop on knowledge discovery in …, 1994 - aaai.org Exact indexing of dynamic time warping. E Keogh, CA Ratanamahatana - Knowledge and Information Systems, 2005 - Springer Scaling up dynamic time warping for datamining applications. EJ Keogh, MJ Pazzani - Proceedings of the sixth ACM SIGKDD …, 2000 portal.acm.org Performance trade‐offs in dynamic time warping algorithms for isolated word … CS Myers, LR Rabiner, AE Rosenberg - The Journal of the Acoustical …, 1979 - link.aip.org Derivative dynamic time warping. EJ Keogh, MJ Pazzani - First SIAM international conference on data …, 2001 - Citeseer Correlation optimized warping and dynamic time warping as preprocessing methods for chromatographic data. G Tomasi, F van den Berg, C … Journal of …, 2004 - interscience.wiley.com Word image matching using dynamic time warping. T Rath, R Manmatha - IEEE Computer Society Conference on Computer …, 2003 - Citeseer Considerations in dynamic time warping algorithms for discrete word … L Rabiner, A Rosenberg, S Levinson - IEEE Transactions on …, 1978 caip.rutgers.edu Synchronization of batch trajectories using dynamic time warping. A Kassidas, JF MacGregor, PA Taylor - AIChE Journal, 1998 interscience.wiley.com A Comparative Analysis of Regional Correlation, Dynamic Time Warping, and Skeletal Tree Matching for Signature Verification. M Parizeau, R Plamondon - … on Pattern Analysis …, 1990 - doi.ieeecomputersociety.org Toward accurate dynamic time warping in linear time and space. S Salvador, P Chan - Intelligent Data Analysis, 2007 - IOS Press Alignment of curves by dynamic time warping. K Wang, T Gasser - The Annals of Statistics, 1997 - jstor.org Dynamic Time Warping. R Niels - Artificial Intelligence, 2004 - Citeseer Iterative Deepening Dynamic Time Warping for Time Series. S Chu, E Keogh, D Hart, M Pazzani - Proc. SIAM Int. Conf. on Data …, 2002 - Citeseer Aligning Noisy Parallel Corpora Across Language Groups : Word Pair Feature Matching by Dynamic Time Warping. P Fung, K McKeown Proceedings of the First Conference of the …, 1994 - Citeseer On-line signature verification by dynamic time-warping. R Martens, L Claesen - Proc. ICPR, 1996 - doi.ieeecomputersociety.org Everything you know about dynamic time warping is wrong. CA Ratanamahatana, E Keogh - Third Workshop on Mining Temporal …, 2004 Citeseer Continuous Dynamic Time Warping for Translation-Invariant Curve Alignment with Applications to Signature Verification. ME Munich, P Perona Proceedings of the Eighth …, 1999 - doi.ieeecomputersociety.org Aligning gene expression time series with time warping algorithms. J Aach, GM Church - Bioinformatics, 2001 - Oxford Univ Press Dynamic programming algorithm optimization for spoken word recognition. H Sakoe, S Chiba - Readings in speech recognition, 1990 books.google.com Dynamic time warping of spectroscopic BATCH data. HJ Ramaker, ENM van Sprang, JA Westerhuis, AK … - Analytica Chimica …, 2003 - Elsevier
Děkuji za pozornost
