Перейти к основному содержимому

Orthogonal matching pursuit

Orthogonal Matching Pursuit (OMP) - комбинация отбора признаков и линейной регрессии, в которой строится максимально точная линейная модель с числом признаков, равным K.

Алгоритм применяется, когда число признаков слишком велико, и требуется построить компактную модель, зависящую лишь от небольшого их числа. Это полезно для повышения интерпретируемости модели, повышения скорости её работы и уменьшения переобучения.

Будем использовать следующие обозначения:

  • A={1,2,...D}A=\{1,2,...D\} - множество всех признаков,

  • A∖SA\setminus S - разность множеств (множество элементов AA, не содержащиеся в SS),

  • ∣S∣|S| - число элементов множества SS.

Алгоритм итеративный, в котором на каждой итерации расширяется число используемых признаков SS на единицу, а вектор ошибок текущей итерации на всех объектах выборки обозначим через E∈RNE\in \mathbb{R}^N.

Тогда алгоритм OMP работает следующим образом:

Начальное множество признаков - пустое множество, а начальная модель - тождественный ноль: S:={}S:=\{\}

Поскольку начальная модель - тождественный ноль, то ошибки вначале совпадают с верными ответами: E:=YE:=Y

пока ∣S∣<K|S|<K:

  1. выбрать признак i∈A∖Si\in A\setminus S, у которого максимальная ковариация с ошибками текущей модели EE.

  2. добавить этот признак в число отобранных: S:=S∪{i}S:=S\cup\{i\}

  3. обучить линейную регрессию предсказывать YY, используя только отобранные признаки из SS

  4. обновить вектор EE ошибками обновлённой модели

Таким образом, алгоритм OMP жадным образом (greedy search) добавляет максимально скоррелированные признаки с откликом по одному, пока не наберёт необходимое количество. В число признаков должна входить константа 1, чтобы модель могла выучить смещение.

Можно досрочно прерывать алгоритм, как только средние потери модели становятся ниже заданного порога. В этом случае достаточное число признаков может быть и меньше KK.

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

Для построения модели с минимальным числом признаков также можно использовать лассо-регрессию с гиперпараметром λ\lambda, подбираемым таким образом, чтобы настроенная модель зависела только от KK признаков.