Итоги дня 054
День 054, мы рассмотрели работу со временем; как работает динамическое искажение времени. Мы узнали, что динамическая деформация времени не только позволяет нам вычислять значимое расстояние, когда одна последовательность смещается раньше или позже во времени. Динамическое искажение времени также позволяет нам вычислить значимое расстояние, когда две последовательности имеют разную длину во времени.
Сегодня мы продолжим с того места, на котором остановились в день 054.
Работа со временем
Как работает динамическая деформация времени (продолжение)
Динамическое искажение времени можно рассматривать как решение проблемы оптимизации. Здесь наша целевая функция — это расстояние между двумя нашими последовательностями после того, как мы исказили одну, чтобы максимально соответствовать другой, и наша задача — найти искривление, которое минимизирует это расстояние.
Чтобы решить эту проблему оптимизации, мы будем использовать метод, называемый динамическим программированием. Вот почему алгоритм называется динамической деформацией времени. Этот базовый шаблон решения задачи оптимизации с помощью динамического программирования встречается во всех областях применения, от создания средств проверки орфографии до выравнивания последовательностей ДНК.
Давайте рассмотрим несколько замечаний о вычислительной эффективности этого алгоритма и некоторые связанные с ним практические соображения. Вспомните, когда мы говорили о нейронных сетях и машинах опорных векторов, нам приходилось решать задачу оптимизации во время обучения.
Однако здесь мы решаем проблему оптимизации во время выполнения всякий раз, когда пытаемся вычислить нашу степень соответствия новой последовательности. Конечно, обычно это гораздо более простая проблема оптимизации, чем та, с которой мы сталкиваемся при обучении нейронных сетей или SVM, но она все же может оказаться дорогостоящей в вычислительном отношении.
В частности, решить эту проблему будет все труднее и труднее по мере того, как наши последовательности становятся длиннее. Если мы не будем осторожны, мы можем обнаружить, что динамическая деформация времени требует так много времени для вычисления расстояний, что она не может успевать за новыми функциями, поступающими в режиме реального времени. На практике принято немного адаптировать алгоритмы динамической деформации времени, чтобы ускорить вычисления.
Многие реализации динамической деформации времени накладывают дополнительные ограничения на процесс деформации, предотвращая сопоставление точек в одной последовательности с точками, которые очень далеки во времени от другой последовательности.
Это все, что касается дня 055. Надеюсь, вы нашли это информативным. Спасибо, что нашли время в своем графике и позволили мне быть вашим проводником в этом путешествии. И до следующего раза, будь легендой.
Справочник
