- Динамическое искажение времени в сильно субквадратичном времени: алгоритмы для режима малых расстояний и приближенная оценка (arXiv)
Автор:Уильям Кусмаул
Аннотация. Динамическое расстояние искривления времени (DTW) — это широко используемый показатель расстояния между временными рядами. Наиболее известные алгоритмы вычисления DTW работают почти за квадратичное время, а условные нижние границы запрещают существование значительно более быстрых алгоритмов. Однако нижние границы не мешают более быстрому алгоритму для особого случая, когда DTW мал. Для произвольного метрического пространства Σ с нормированными расстояниями, так что наименьшее ненулевое расстояние равно единице, мы представляем алгоритм, который вычисляет dtw(x,y) для двух строк x и y над Σ за время O(n⋅dtw(x, у)). Мы также представляем алгоритм аппроксимации, который вычисляет dtw(x,y) с точностью до множителя O(nε) за время O~(n2−ε) для 0‹ε‹1. Алгоритм позволяет брать строки x и y по произвольной хорошо разделенной метрике дерева с логарифмической глубиной и не более чем экспоненциальным соотношением сторон. Расширяя наши методы, мы также получаем алгоритм первого приближения для расстояния редактирования для работы с символами, взятыми из произвольного метрического пространства, обеспечивая nε-аппроксимацию за время O~(n2−ε) с высокой вероятностью. Кроме того, мы представляем простое сокращение от вычисления расстояния редактирования до вычисления DTW. Применяя наше сокращение к условной нижней границе Брингмана и Кюннемана, относящейся к расстоянию редактирования над {0,1}, мы получаем условную нижнюю границу для вычисления DTW над трехбуквенным алфавитом (с расстояниями, равными нулю и единице). Это улучшает предыдущий результат Аббуда, Бакурса и Уильямса. Используя аналогичный подход, мы доказываем сокращение от вычисления расстояния редактирования до вычисления наибольшей длины LCS. Это означает, что можно восстановить условные нижние границы для LCS непосредственно из оценок для расстояния редактирования, что ранее не считалось возможным.
2. Сложность односторонней связи динамической деформации времени (arXiv)
Автор:Владимир Браверман, Моисей Чарикар, Уильям Кузмаул, Дэвид П. Вудрафф, Лин Ф. Янг
Вывод:мы решаем случайную сложность односторонней связи расстояния с динамическим искажением времени (DTW). Мы показываем, что существует эффективный протокол односторонней связи, использующий O˜(n/α) битов для задачи вычисления α-аппроксимации для DTW между строками x и y длины n, и мы доказываем нижнюю границу Ω( n/α) бит для той же задачи. Наш протокол связи работает со строками с произвольной метрикой полиномиального размера и соотношения сторон, и мы оптимизируем логарифмические коэффициенты в зависимости от свойств базовой метрики, например, когда точки представляют собой целочисленные векторы малой размерности, снабженные различными метриками, или имеют ограниченное удвоение. измерение. Мы также рассматриваем линейные эскизы DTW, показывая, что такие эскизы должны иметь размер Ω(n).
3. Общая оценка навигации, обусловленной инструкциями, с использованием динамической деформации времени (arXiv)
Автор: Габриэль Ильхарко, Вихан Джайн, Александр Ку, Юджин Ие, Джейсон Болдридж.
Вывод: при навигации, основанной на инструкциях, агенты интерпретируют естественный язык и свое окружение для навигации по окружающей среде. Наборы данных для изучения этой задачи обычно содержат пары этих инструкций и эталонных траекторий. Тем не менее, большинство показателей оценки, используемых до сих пор, не учитывают должным образом последнее, полагаясь вместо этого на недостаточное сравнение сходства. Мы устраняем фундаментальные недостатки в ранее использовавшихся метриках и показываем, как динамическое искажение времени (DTW), давно известный метод измерения сходства между двумя временными рядами, можно использовать для оценки навигационных агентов. Для этого мы определяем нормализованную метрику Dynamic Time Warping (nDTW), которая мягко наказывает отклонения от эталонного пути, естественно чувствительна к порядку узлов, составляющих каждый путь, подходит как для непрерывных, так и для графических оценок и может эффективно рассчитываться. Кроме того, мы определяем SDTW, который ограничивает nDTW только успешными путями. Мы собираем суждения о сходстве людей для смоделированных путей и обнаруживаем, что nDTW лучше коррелирует с человеческими рейтингами, чем все другие показатели. Мы также демонстрируем, что использование nDTW в качестве сигнала вознаграждения для навигационных агентов обучения с подкреплением повышает их производительность как в наборах данных «Комната-комната» (R2R), так и «Комната-комната» (R4R). Результаты R4R, в частности, подчеркивают превосходство SDTW над предыдущими показателями, ограничивающими успех.
4. Сверточные сети с динамической временной деформацией (arXiv)
Автор : Янив Шульман
Аннотация. При работе с временными последовательностями справедливо предположить, что те же виды деформаций, которые послужили мотивом для разработки алгоритма динамической деформации времени, могут иметь отношение и к вычислению скалярного произведения («свертка» ) в одномерном слое свертки. В этой работе предлагается метод выравнивания фильтра свертки и входных данных, где они локально не совпадают по фазе, с использованием алгоритма, аналогичного динамическому искажению времени. Предлагаемый метод позволяет внедрить непараметрическую деформацию временных последовательностей для повышения сходства непосредственно в глубоких сетях и может расширить возможности обобщения и емкость стандартного одномерного слоя свертки, где на входе присутствуют локальные последовательные деформации. Экспериментальные результаты показывают, что предлагаемый метод превосходит или соответствует стандартному одномерному сверточному слою с точки зрения максимальной точности, достигнутой в ряде задач классификации временных рядов. Кроме того, исследуется влияние различных настроек гиперпараметров с учетом различных наборов данных, и результаты подтверждают выводы предыдущей работы, проделанной в отношении выбора значений параметров DTW. Предлагаемый слой может свободно интегрироваться с другими типовыми слоями для составления глубоких искусственных нейронных сетей произвольной архитектуры, обучаемых с помощью стандартного стохастического градиентного спуска.
5. Обнаружение вибраций при токарной обработке с использованием машинного обучения и мер подобия временных рядов с помощью динамической деформации времени (arXiv)
Автор: Мелих С. Есилли, Фирас А. Хасауна, Андреас Отто
Аннотация. Обнаружение вибрации по сигналам датчиков является активной областью исследований. Хотя сообщалось об определенных успехах с использованием нескольких инструментов определения характеристик и алгоритмов машинного обучения, существующие методы имеют несколько недостатков, таких как ручная предварительная обработка и необходимость большого набора данных. В этой статье мы представляем альтернативный подход к обнаружению дребезга, основанный на алгоритме K-ближайших соседей (kNN) для классификации и динамической деформации времени (DTW) в качестве меры сходства временных рядов. Используемые временные ряды представляют собой сигналы ускорения, полученные от держателя инструмента в серии экспериментов по токарной обработке. Наши результаты показывают, что этот подход обеспечивает точность обнаружения, которая в большинстве случаев превосходит существующие методы. Мы сравниваем наши результаты с традиционными методами, основанными на вейвлет-пакетном преобразовании (WPT) и ансамблевой эмпирической модовой декомпозиции (EEMD), а также с более поздним подходом, основанным на топологическом анализе данных (TDA). Мы показываем, что в трех из четырех конфигураций резки наш подход на основе DTW обеспечивает наивысшую среднюю скорость классификации, достигающую в одном случае точности 99%. Наш подход не требует извлечения признаков, позволяет повторно использовать классификатор для различных конфигураций резки и использует обучающие наборы разумного размера. Хотя полученная в результате высокая точность в нашем подходе связана с большими вычислительными затратами, это характерно для реализации DTW, которую мы использовали. В частности, мы выделяем доступные, очень быстрые реализации DTW, которые можно реализовать даже на небольшой бытовой электронике. Таким образом, дальнейшая оптимизация кода и значительное сокращение вычислительных затрат на этапе реализации делают наш подход жизнеспособным вариантом для обнаружения дребезга в процессе.
