The AdaBoost Flow

AdaBoost алгоритм бы придуман Робертом Шапиро и Иовом Фройндом в 1997 году и сейчас не нуждается в рекламе среди специалистов по анализу даных. За этот алгоритм они получили геделевскую премию в 2003 году. Сегодня считается, что AdaBoost, так же как и PageRank алгоритм Брина и Пэйджа, один из 10 наиболее важных алгоритмов в анализе данных.
Математик, не интересующейся ничем кроме математики, может забыть обо всем этом и рассматривать AdaBoost как метод решения некоторой специальной оптимизационной задачи.
В нашей работе мы вводим непрерывную по времени систему, которую называем AdaBoost Flow. Она задается системой дифференциальных уравнений с контролем. Мы показываем, что при соответствующем выборе контроля дискретный AdaBoost алгоритм может быть вложен в непрерывную систему. Оказывается, что уравнения, определяющие нетривиальную часть динамики на мерах, совпадают с уравнениями для цепочки Тоды в спектральных переменных. Наиболее интересным и неожиданным является то, что конструкция AdaBoost Flow напоминает конструкцию Перельмана, которую он применил для изучения Потоков Ричи. Мы приводим словарь соответствия между объектами этих двух задач.