Динамическое искажение времени - Dynamic time warping

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

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

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

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

Каждый индекс из первой последовательности должен соответствовать одному или нескольким индексам из другой последовательности, и наоборот.
Первый индекс из первой последовательности должен совпадать с первым индексом из другой последовательности (но это не обязательно должно быть его единственным совпадением)
Последний индекс из первой последовательности должен совпадать с последним индексом из другой последовательности (но это не обязательно должно быть его единственным совпадением)
Отображение индексов из первой последовательности в индексы из другой последовательности должно быть монотонно возрастающим, и наоборот, т.е. если это индексы из первой последовательности, то в другой последовательности не должно быть двух индексов , так что индекс будет сопоставлен. с индексом и индекс сопоставляется с индексом , и наоборот ${\ displaystyle j> i}$ ${\ displaystyle l> k}$ ${\ displaystyle i}$ ${\ displaystyle l}$ ${\ displaystyle j}$ ${\ displaystyle k}$

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

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

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

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

Реализация

Этот пример иллюстрирует реализацию алгоритма динамического преобразования времени, когда две последовательности s и t являются строками дискретных символов. Для двух символов х и у , d(x, y)это расстояние между символами, например , d(x, y)= . ${\ displaystyle | xy |}$

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]
    
    for i := 0 to n
        for j := 0 to m
            DTW[i, j] := infinity
    DTW[0, 0] := 0
    
    for i := 1 to n
        for j := 1 to m
            cost := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match
    
    return DTW[n, m]
}

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

Иногда мы хотим добавить ограничение местоположения. То есть мы требуем, чтобы if было s[i]сопоставлено с t[j], then было не больше, чем w , параметр окна. ${\ displaystyle | ij |}$

Мы можем легко изменить приведенный выше алгоритм, чтобы добавить ограничение местоположения (различия отмечен). Однако данная модификация работает, только если не больше w , т.е. конечная точка находится в пределах длины окна от диагонали. Для того, чтобы алгоритм работал, параметр окна w должен быть адаптирован так (см. Строку, отмеченную (*) в коде). ${\ displaystyle | нм |}$ ${\ displaystyle | нм | \ leq w}$

int DTWDistance(s: array [1..n], t: array [1..m], w: int) {
    DTW := array [0..n, 0..m]

    w := max(w, abs(n-m)) // adapt window size (*)

    for i := 0 to n
        for j:= 0 to m
            DTW[i, j] := infinity
    DTW[0, 0] := 0
    for i := 1 to n
        for j := max(1, i-w) to min(m, i+w)
            DTW[i, j] := 0

    for i := 1 to n
        for j := max(1, i-w) to min(m, i+w)
            cost := d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match

    return DTW[n, m]
}

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

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

Сложность

Временная сложность алгоритма DTW равна , где и - длины двух входных последовательностей. 50-летняя квадратичная временная граница была недавно нарушена, алгоритм, созданный Голдом и Шариром, позволяет вычислять DTW во времени и пространстве для двух входных последовательностей длины . Этот алгоритм также можно адаптировать к последовательностям разной длины. Несмотря на это улучшение, было показано, что строго субквадратичное время выполнения формы для некоторых не может существовать, если только гипотеза сильного экспоненциального времени не верна. ${\ displaystyle O (NM)}$ ${\ displaystyle N}$ ${\ displaystyle M}$ ${\ Displaystyle О ({N ^ {2}} / \ log \ log (N))}$ ${\ displaystyle N}$ ${\ Displaystyle О (N ^ {2- \ epsilon})}$ ${\ displaystyle \ epsilon> 0}$

В то время как алгоритм динамического программирования для DTW требует места в наивной реализации, потребление пространства можно уменьшить, используя алгоритм Хиршберга . ${\ displaystyle O (NM)}$ ${\ Displaystyle O (мин (N, M))}$

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

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

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

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

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

Ближайший сосед классификатор может достичь состояния из самых современной производительности при использовании динамического временного масштаба в качестве меры расстояния.

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

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

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

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

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

Библиотека lbimproved C ++ реализует алгоритмы быстрого поиска ближайшего соседа под Стандартной общественной лицензией GNU (GPL). Он также предоставляет C ++ реализацию динамического преобразования времени, а также различные нижние границы.
Библиотека FastDTW - это реализация DTW и FastDTW на Java, которая обеспечивает оптимальное или почти оптимальное согласование с O ( N ) временем и сложностью памяти, в отличие от требования O ( N ² ) для стандартного алгоритма DTW. FastDTW использует многоуровневый подход, который рекурсивно проецирует решение с более грубым разрешением и уточняет проецируемое решение.
Форк FastDTW (Java) опубликован в Maven Central.
классификация временных рядов (Java) пакет для классификации временных рядов с использованием DTW в Weka.
Пакет 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 с различными параметрами.
Sketch-a-Char использует Greedy DTW (реализованный на JavaScript) как часть программы классификатора символов LaTeX.
В MATCHBOX реализует DTW , чтобы соответствовать Mel-частотных кепстральных коэффициентов звуковых сигналов.
Усреднение последовательности : реализация DBA под GPL Java.
Набор средств распознавания жестов | GRT C ++ Набор средств распознавания жестов в реальном времени реализует DTW.
В PyHubs пакет реализует программные DTW и ближайшие соседи классификатор, а также их расширение (hubness-зависимых классификаторы).
Simpledtw Python библиотека реализует классический O ( NM алгоритм программирования) Динамические и основы на Numpy. Он поддерживает значения любого измерения, а также использует пользовательские функции норм для расстояний. Он находится под лицензией MIT.
Библиотека tslearn Python реализует DTW в контексте временных рядов.
Библиотека cuTWED CUDA Python реализует современное улучшенное расстояние редактирования Time Warp Edit Distance с использованием только линейной памяти с феноменальным ускорением.
DynamicAxisWarping.jl - это реализация Julia DTW и связанных алгоритмов, таких как барицентры FastDTW, SoftDTW, GeneralDTW и DTW.

Приложения

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

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

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

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

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

использованная литература

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

Винцюк, Т.К. (1968). «Распознавание речи с помощью динамического программирования». Кибернетика . 4 : 81–88.
Sakoe, H .; Чиба (1978). «Оптимизация алгоритмов динамического программирования для распознавания речи». Транзакции IEEE по акустике, речи и обработке сигналов . 26 (1): 43–49. DOI : 10.1109 / tassp.1978.1163055 .
Майерс, CS; Рабинер, Л.Р. (1981). «Сравнительное исследование нескольких алгоритмов динамического искажения времени для распознавания связанных слов». Технический журнал Bell System . 60 (7): 1389–1409. DOI : 10.1002 / j.1538-7305.1981.tb00272.x . ISSN 0005-8580 . S2CID 12857347 .
Рабинер, Лоуренс; Хуанг, Бин-Хван (1993). «Глава 4: Методы сравнения шаблонов». Основы распознавания речи . Энглвуд Клиффс, Нью-Джерси: PTR Prentice Hall. ISBN 978-0-13-015157-5.
Мюллер, Мейнард (2007). Динамическое искажение времени. В «Поиск информации для музыки и движения», глава 4, страницы 69-84 (PDF) . Springer. DOI : 10.1007 / 978-3-540-74048-3 . ISBN 978-3-540-74047-6.
Рактанманон, Танавин (сентябрь 2013 г.). «Обращение к временным рядам больших данных: добыча триллионов подпоследовательностей временных рядов при динамическом искажении времени» . ACM-транзакции при обнаружении знаний из данных . 7 (3): 10: 1–10: 31. DOI : 10.1145 / 2513092.2500489 . PMC 6790126 . PMID 31607834 .

Languages

In other projects