WikiDer > Динамическое искажение времени

Dynamic time warping
Динамическое искажение времени
Два повтора ходьбы, записанные с помощью системы захвата движения. Несмотря на то, что скорость ходьбы между повторениями различается, пространственные траектории конечностей остаются очень похожими.[1]

В анализ временных рядов, динамическое искажение времени (DTW) один из алгоритмы для измерения сходства между двумя временными последовательностями, которые могут различаться по скорости. Например, сходство в ходьбе можно было обнаружить с помощью DTW, даже если один человек шел быстрее, чем другой, или если были ускорения и замедления во время наблюдения. DTW был применен к временным последовательностям видео, аудио и графических данных - действительно, любые данные, которые можно преобразовать в линейную последовательность, можно проанализировать с помощью DTW. Известное приложение было автоматическим распознавание речи, чтобы справиться с разной скоростью речи. Другие приложения включают распознавание говорящего и онлайн признание подписи. Его также можно использовать в частичном соответствие формы Приложения.

В общем, DTW - это метод, который вычисляет оптимальное совпадение между двумя заданными последовательностями (например, Временные ряды) с определенными ограничениями и правилами:

  • Каждый индекс из первой последовательности должен совпадать с одним или несколькими индексами из другой последовательности, и наоборот.
  • Первый индекс из первой последовательности должен совпадать с первым индексом из другой последовательности (но это не обязательно должно быть его единственным совпадением)
  • Последний индекс из первой последовательности должен совпадать с последним индексом из другой последовательности (но это не обязательно должно быть его единственным совпадением)
  • Отображение индексов из первой последовательности в индексы из другой последовательности должно быть монотонно возрастающим, и наоборот, т.е. если индексы из первой последовательности, то двух индексов быть не должно. в другой последовательности, такой что index совпадает с индексом и индекс совпадает с индексом , наоборот

В оптимальное совпадение обозначается совпадением, которое удовлетворяет всем ограничениям и правилам и имеет минимальную стоимость, где стоимость вычисляется как сумма абсолютных разностей для каждой согласованной пары индексов между их значениями.

Последовательности "искажены" нелинейно во временном измерении, чтобы определить меру их подобия независимо от некоторых нелинейных изменений во временном измерении. Этот выравнивание последовательностей Метод часто используется при классификации временных рядов. Хотя DTW измеряет величину, подобную расстоянию между двумя заданными последовательностями, он не гарантирует неравенство треугольника держать.

В дополнение к мере сходства между двумя последовательностями создается так называемый «путь деформации», посредством деформации в соответствии с этим путем два сигнала могут быть выровнены во времени. Сигнал с оригинальным набором точек Икс(оригинал), Y(оригинал) преобразуется в Икс(деформированный), Y(деформировано). Это находит применение в генетической последовательности и синхронизации звука. В родственной технике последовательности с переменной скоростью могут быть усреднены с использованием этой техники, см. средняя последовательность раздел.

Это концептуально очень похоже на Алгоритм Нидлмана – Вунша.

Выполнение

Этот пример иллюстрирует реализацию алгоритма динамического преобразования времени, когда две последовательности s и т представляют собой цепочки дискретных символов. Для двух символов Икс и у, д (х, у) расстояние между символами, например д (х, у) = .

int DTWDistance (s: array [1..n], t: array [1..m]) {DTW: = array [0..n, 0..m] для i: = от 0 до n для j: = От 0 до m DTW [i, j]: = бесконечность DTW [0, 0]: = 0 для i: = от 1 до n для j: = от 1 до m стоимость: = d (s [i], t [j]) DTW [i, j]: = cost + minimum (DTW [i-1, j], // вставка DTW [i, j-1], // удаление DTW [i-1, j-1]) // соответствие return DTW [n, m]}

куда DTW [i, j] это расстояние между s [1: i] и т [1: j] с лучшим выравниванием.

Иногда мы хотим добавить ограничение местоположения. То есть мы требуем, чтобы если s [i] совпадает с т [j], тогда не больше чем ш, параметр окна.

Мы можем легко изменить приведенный выше алгоритм, добавив ограничение местоположения (различия отмеченОднако данная модификация работает только в том случае, если не больше чем ш, т.е. конечная точка находится в пределах длины окна от диагонали. Чтобы алгоритм заработал, параметр окна ш должны быть адаптированы так, чтобы (см. строку, отмеченную (*) в коде).

int DTWDistance (s: массив [1..n], t: массив [1..m], w: int) {DTW: = массив [0..n, 0..m] ш: = макс (ш, абс (н-м)) // адаптируем размер окна (*) для i: = 0 к n для j: = 0 до m DTW [i, j]: = infinity DTW [0, 0]: = 0 для i: = от 1 до n        для j: = max (1, i-w) to min (m, i + w)            DTW [i, j]: = 0    для i: = от 1 до n для j: = от max (1, i-w) до min (m, i + w)            cost: = d (s [i], t [j]) DTW [i, j]: = cost + minimum (DTW [i-1, j], // вставка DTW [i, j-1], // удаление DTW [i-1, j-1]) // соответствие return DTW [n, m]}

Деформирующие свойства

Алгоритм DTW производит дискретное сопоставление существующих элементов одной серии с другой. Другими словами, он не позволяет масштабировать сегменты в последовательности по времени. Другие методы допускают непрерывную деформацию. Например, оптимизированное корреляционное искажение (COW) делит последовательность на однородные сегменты, которые масштабируются во времени с помощью линейной интерполяции, чтобы обеспечить наилучшее соответствие искажения. Масштабирование сегмента приводит к потенциальному созданию новых элементов путем масштабирования сегментов вниз или вверх и, таким образом, дает более чувствительное искажение, чем дискретное сопоставление исходных элементов DTW.

Сложность

Временная сложность алгоритма DTW составляет , куда и - длины двух входных последовательностей. При условии, что , временную сложность можно назвать . 50-летняя квадратичная временная граница была недавно нарушена, реализация, созданная Голдом и Шариром, позволяет вычислять DTW в время и место.[2]

Естественная реализация DTW также имеет космическая сложность. Эта граница была недавно нарушена с помощью алгоритма «разделяй и властвуй» Трали и Демпси, что дало линейную пространственную сложность . У этого алгоритма есть дополнительное преимущество, заключающееся в возможности параллельных вычислений.[3]

Быстрое вычисление

Быстрые методы вычисления DTW включают PrunedDTW,[4] SparseDTW,[5] FastDTW,[6] и MultiscaleDTW.[7][8]Распространенную задачу, получение аналогичных временных рядов, можно ускорить, используя нижние границы, такие как LB_Keogh[9] или LB_Improved.[10] В обзоре Wang et al. сообщил о несколько лучших результатах с нижней границей LB_Improved, чем с границей LB_Keogh, и обнаружил, что другие методы были неэффективными.[11]

Средняя последовательность

Усреднение для динамического преобразования времени - это проблема нахождения средней последовательности для набора последовательностей. NLAAF[12] - это точный метод усреднения двух последовательностей с использованием DTW. Для более чем двух последовательностей проблема связана с одной из множественное выравнивание и требует эвристики.DBA[13] в настоящее время является эталонным методом для усреднения набора последовательностей в соответствии с DTW.COMASA[14] эффективно рандомизирует поиск средней последовательности, используя DBA как локальный процесс оптимизации.

Контролируемое обучение

А классификатор ближайшего соседа может достичь высочайшего уровня производительности при использовании динамического преобразования времени в качестве меры расстояния.[15]

Альтернативные подходы

В функциональный анализ данных, временные ряды рассматриваются как дискретизации гладких (дифференцируемых) функций времени. Просматривая наблюдаемые образцы на гладких функциях, можно использовать непрерывную математику для анализа данных.[16] Гладкость и монотонность функций деформации времени могут быть получены, например, путем интегрирования изменяющейся во времени радиальная базисная функция, таким образом являясь одномерным диффеоморфизм.[17] Оптимальные нелинейные функции деформации времени вычисляются путем минимизации меры расстояния набора функций до их деформированного среднего. Условия штрафа за шероховатость для функций деформации могут быть добавлены, например, путем ограничения размера их кривизны. Получаемые в результате функции деформации гладкие, что облегчает дальнейшую обработку. Этот подход успешно применялся для анализа паттернов и вариативности речевых движений.[18][19]

Другой связанный подход: скрытые марковские модели (HMM), и было показано, что Алгоритм Витерби используется для поиска наиболее вероятного пути через HMM эквивалентно стохастическому DTW.[20][21][22]

DTW и связанные с ним методы деформации обычно используются в качестве этапов предварительной или последующей обработки при анализе данных. Если наблюдаемые последовательности содержат как случайные вариации в своих значениях (форме наблюдаемых последовательностей), так и (случайное) временное рассогласование, искажение может чрезмерно соответствовать шуму, что приводит к смещению результатов. Одновременная формулировка модели со случайным изменением как значений (по вертикали), так и с параметризацией во времени (по горизонтали) является примером нелинейная модель смешанных эффектов.[23] При анализе движений человека одновременное нелинейное моделирование смешанных эффектов показало лучшие результаты по сравнению с DTW.[24]

Программное обеспечение с открытым исходным кодом

  • В фунт улучшенный Библиотека C ++ реализует алгоритмы быстрого поиска ближайшего соседа под Стандартной общественной лицензией GNU (GPL). Он также предоставляет C ++ реализацию динамического преобразования времени, а также различные нижние границы.
  • В FastDTW библиотека - это реализация DTW и FastDTW на Java, которая обеспечивает оптимальное или почти оптимальное согласование с О(N) время и сложность памяти, в отличие от О(N2) требование для стандартного алгоритма DTW. FastDTW использует многоуровневый подход, рекурсивно проецирующий решение с более грубым разрешением и уточняющий проецируемое решение.
  • Форк FastDTW (Java) опубликовано в Maven Central.
  • В DTW люкс предоставляет Python (dtw-python) и пакеты R (dtw) со всесторонним охватом членов семейства алгоритмов DTW, включая множество правил рекурсии (также называемых пошаговыми шаблонами), ограничений и сопоставления подстрок.
  • В mlpy Библиотека Python реализует DTW.
  • В pydtw Библиотека Python реализует меры DTW с манхэттенским и евклидовым вкусом, включая нижние границы LB_Keogh.
  • В Cudadtw Библиотека C ++ / CUDA реализует выравнивание подпоследовательностей евклидовых DTW и z-нормализованное евклидово расстояние аналогично популярному UCR-Suite на ускорителях с поддержкой CUDA.
  • В JavaML библиотека машинного обучения реализует DTW.
  • В ndtw Библиотека C # реализует DTW с различными параметрами.
  • Зарисовка использует Greedy DTW (реализованный на JavaScript) как часть программы классификатора символов LaTeX.
  • В Коробок спичек реализует DTW для согласования мелкочастотных кепстральных коэффициентов аудиосигналов.
  • Усреднение последовательности: реализация DBA под GPL Java.[13]
  • В Набор инструментов распознавания жестов | GRT Набор инструментов C ++ для распознавания жестов в реальном времени реализует DTW.
  • В PyHubs программный пакет реализует классификаторы DTW и ближайшего соседа, а также их расширения (классификаторы, учитывающие концентрацию).
  • В simpledtw Библиотека Python реализует классический О(НМ) Алгоритм динамического программирования и основывается на Numpy. Он поддерживает значения любого измерения, а также использует пользовательские функции норм для расстояний. Он находится под лицензией MIT.
  • В учиться Библиотека Python реализует DTW в контексте временных рядов.
  • В ОБРАЩЕННЫЙ Библиотека CUDA Python реализует улучшенное состояние искусства Искажение времени Edit Distance используя только линейную память с феноменальным ускорением.
  • DynamicAxisWarping.jl Это реализация Julia DTW и связанных алгоритмов, таких как барицентры FastDTW, SoftDTW, GeneralDTW и DTW.

Приложения

Распознавание разговорного слова

Из-за разной скорости речи в речевом паттерне в зависимости от оси времени возникают нелинейные колебания, которые необходимо устранить.[25] Сопоставление DP - это алгоритм сопоставления с образцом, основанный на динамическое программирование (DP), который использует эффект временной нормализации, когда флуктуации временной оси моделируются с помощью нелинейной функции временной деформации. Рассматривая любые два речевых паттерна, мы можем избавиться от их временных различий, искривив временную ось одного так, чтобы было достигнуто максимальное совпадение с другим. Более того, если функция деформации может принимать любое возможное значение, очень меньше[уточнить] можно различать слова, принадлежащие к разным категориям. Итак, чтобы усилить различение слов, принадлежащих к разным категориям, были наложены ограничения на наклон функции деформации.

Корреляционный анализ мощности

Нестабильные часы используются, чтобы победить наивных анализ мощности. Для противодействия этой защите используются несколько методов, одна из которых - динамическое искажение времени.

Смотрите также

Рекомендации

  1. ^ Olsen, NL; Маркуссен, B; Ракет, Л.Л. (2018), «Одновременный вывод для несовпадающих многомерных функциональных данных», Журнал Королевского статистического общества, серия C, 67 (5): 1147–76, arXiv:1606.03295, Дои:10.1111 / rssc.12276, S2CID 88515233
  2. ^ Золото, Омер; Шарир, Миха (2018). «Динамическое искажение времени и геометрическое расстояние редактирования: преодоление квадратичного барьера». Ассоциация вычислительной техники. 14 (4). Дои:10.1145/3230734. S2CID 52070903.
  3. ^ Трали, Кристофер; Демпси, Элизабет (2020). «Точное, параллелизируемое динамическое выравнивание деформации времени с линейной памятью». Труды Международной конференции по поиску музыкальной информации (ISMIR).
  4. ^ Сильва, Д. Ф., Батиста, Г. Е. А. П. А. (2015). Ускорение попарного вычисления матрицы динамического искажения времени.
  5. ^ Аль-Наймат, Г., Чавла, С., Тахери, Дж. (2012). SparseDTW: новый подход к ускорению динамического искажения времени.
  6. ^ Стэн Сальвадор, Филип Чан, FastDTW: К точному динамическому искажению времени в линейном времени и пространстве. KDD Workshop on Mining Temporal and Sequential Data, pp. 70–80, 2004.
  7. ^ Мейнард Мюллер, Хеннинг Маттес и Франк Курт (2006). Эффективный многомасштабный подход к синхронизации звука. Труды Международной конференции по поиску музыкальной информации (ISMIR), стр. 192–197.
  8. ^ Томас Претцлих, Джонатан Дридгер и Мейнард Мюллер (2016). Мультимасштабное динамическое искажение времени с ограничением памяти. Труды Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP), стр. 569–573.
  9. ^ Keogh, E .; Ратанамахатана, К. А. (2005). «Точная индексация динамической деформации времени». Знания и информационные системы. 7 (3): 358–386. Дои:10.1007 / s10115-004-0154-9. S2CID 207056701.
  10. ^ Лемир, Д. (2009). «Более быстрое извлечение с помощью двухпроходной нижней границы с динамическим искажением времени». Распознавание образов. 42 (9): 2169–2180. arXiv:0811.3301. Дои:10.1016 / j.patcog.2008.11.030. S2CID 8658213.
  11. ^ Ван, Сяоюэ; и другие. (2010). «Экспериментальное сравнение методов представления и мер расстояния для данных временных рядов». Интеллектуальный анализ данных и обнаружение знаний. 2010: 1–35. arXiv:1012.2789.
  12. ^ Gupta, L .; Molfese, D. L .; Tammana, R .; Симос, П. Г. (1996). «Нелинейное согласование и усреднение для оценки вызванного потенциала». IEEE Transactions по биомедицинской инженерии. 43 (4): 348–356. Дои:10.1109/10.486255. PMID 8626184. S2CID 28688330.
  13. ^ а б Petitjean, F. O .; Ketterlin, A .; Гансарский, П. (2011). «Метод глобального усреднения для динамического преобразования времени с приложениями для кластеризации». Распознавание образов. 44 (3): 678. Дои:10.1016 / j.patcog.2010.09.013.
  14. ^ Petitjean, F. O .; Гансарски, П. (2012). «Обобщение набора временных рядов путем усреднения: от последовательности Штейнера до компактного множественного выравнивания». Теоретическая информатика. 414: 76–91. Дои:10.1016 / j.tcs.2011.09.029.
  15. ^ Дин, Хуэй; Трайцевски, Гоче; Шойерманн, Питер; Ван, Сяоюэ; Кио, Имонн (2008). «Запросы и интеллектуальный анализ данных временных рядов: экспериментальное сравнение представлений и мер расстояния». Proc. VLDB Endow. 1 (2): 1542–1552. Дои:10.14778/1454159.1454226.
  16. ^ Lucero, J.C .; Munhall, K. G .; Gracco, V. G .; Рамзи, Дж. О. (1997). «О регистрации времени и паттернах речевых движений». Журнал исследований речи, языка и слуха. 40 (5): 1111–1117. Дои:10.1044 / jslhr.4005.1111. PMID 9328881.
  17. ^ Дуррлеман, S; Pennec, X .; Trouvé, A .; Braga, J .; Гериг, Г. и Аяче, Н. (2013). «На пути к всеобъемлющей основе для пространственно-временного статистического анализа данных продольной формы». Международный журнал компьютерного зрения. 103 (1): 22–59. Дои:10.1007 / s11263-012-0592-х. ЧВК 3744347. PMID 23956495.
  18. ^ Howell, P .; Андерсон, А .; Лусеро, Дж. К. (2010). «Моторное время речи и беглость». In Maassen, B .; ван Лисхаут, П. (ред.). Управление речевой моторикой: новые достижения в фундаментальных и прикладных исследованиях. Издательство Оксфордского университета. С. 215–225. ISBN 978-0199235797.
  19. ^ Koenig, Laura L .; Лусеро, Хорхе К.; Перлман, Элизабет (2008). «Вариативность речи во фрикативных формах детей и взрослых: результаты функционального анализа данных». Журнал акустического общества Америки. 124 (5): 3158–3170. Bibcode:2008ASAJ..124.3158K. Дои:10.1121/1.2981639. ISSN 0001-4966. ЧВК 2677351. PMID 19045800.
  20. ^ Накагава, Сейичи; Наканиси, Хиробуми (1 января 1988 г.). «Независимое от говорящего распознавание английских согласных и японских слов методом стохастической динамической деформации времени». Журнал исследований IETE. 34 (1): 87–95. Дои:10.1080/03772063.1988.11436710. ISSN 0377-2063.
  21. ^ Фанг, Чуньшэн. «От динамического искажения времени (DTW) к скрытой марковской модели (HMM)» (PDF).
  22. ^ Хуанг, Б. Х. (сентябрь 1984 г.). «О скрытой марковской модели и динамическом искажении времени для распознавания речи # x2014; Единый взгляд». Технический журнал AT&T Bell Laboratories. 63 (7): 1213–1243. Дои:10.1002 / j.1538-7305.1984.tb00034.x. ISSN 0748-612X. S2CID 8461145.
  23. ^ Ракет Л.Л., Соммер С., Маркуссен Б. (2014). «Нелинейная модель смешанных эффектов для одновременного сглаживания и регистрации функциональных данных». Письма с распознаванием образов. 38: 1–7. Дои:10.1016 / j.patrec.2013.10.018.
  24. ^ Ракет Л.Л., Гримме Б., Шенер Г., Игель С., Маркуссен Б. (2016). «Разделение времени, условий движения и индивидуальных различий в анализе движения человека». PLOS вычислительная биология. 12 (9): e1005092. Bibcode:2016PLSCB..12E5092R. Дои:10.1371 / journal.pcbi.1005092. ЧВК 5033575. PMID 27657545.
  25. ^ Сакоэ, Хироаки; Чиба, Сейби (1978). «Оптимизация алгоритмов динамического программирования для распознавания речи». Транзакции IEEE по акустике, речи и обработке сигналов. 26 (1): 43–49. Дои:10.1109 / тассп.1978.1163055.

дальнейшее чтение