Обычное руководство по контролируемому обучению с помощью scikit-learn — Orthogonal Matching Pursuit (OMP) — Generalized Linear Models (10)

Это десятая часть из серии из 92 частей традиционного руководства по обучению с учителем с помощью scikit-learn, написанного с целью овладеть навыками реализации алгоритмов для продуктивного использования и объяснить алгоритмическую логику, лежащую в их основе. Ссылки на все части смотрите в первой статье.

Ортогональное совпадающее преследование

Это алгоритм разреженной аппроксимации, который включает в себя поиск «наилучшего соответствия» проекции многомерных данных на диапазон чрезмерно полного словаря.

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

Рассмотрим следующий очень простой пример: даны следующие разреженные сигналы, которые представляют собой матрицу

Ниже представлена ​​матрица измерений A (2 x 3):

Поэтому y = A · x дает:

Теперь, учитывая, что:

Как найти оригинальный x?
Интересно, не правда ли? Итак, давайте найдем х.

Столбцы в матрице A называются ОСНОВОЙ, и у нас есть нечто, называемое атомами, которые

Интерпретация уравнения Ах = у

Так как A = [b1 b2 b3]; и если мы допустим: x = [a b c], то

A · x = a · b1 + b · b2 + c · b3

A · x является линейной комбинацией b1, b2, b3.

Из приведенного выше уравнения видно, что атом b1 вносит наибольший вклад в y, следующий за ним атом b2 и последний атом b3.

ОРТОГОНАЛЬНОЕ СОГЛАСОВАННОЕ ПРЕСЛЕДОВАНИЕ работает в обратном порядке. мы начинаем искать, какие из b1, b2, b3 будут СИЛЬНЕЕ влиять на y. Затем ВТОРОЙ СИЛЬНЕЙШИЙ из остаточных и так далее.

СИЛЬНОЕ влияние измеряется с использованием алгоритма DOT PRODUCT / INNER PRODUCT OMP.

  1. найти атом с наибольшим внутренним произведением на y

2. рассчитать остаток

3. найти атом с наибольшим внутренним произведением на ri

4. повторять шаги 2 и 3, пока остаток не достигнет определенного порога

Геометрически вы можете представить процесс как:

Здесь скалярное произведение y на любое из b1, b2, b3:

Взяв абсолютное значение, мы видим, что b1 дает самый большой внутренний продукт. Затем b1 выбирается в качестве атома на первом этапе DOT PRODUCT -1,34. Далее считаем остаток:

Затем мы считаем скалярное произведение этого остатка на b2 и b3 (нет необходимости считать с b1, так как этот остаток должен быть перпендикулярен b1).

Взяв абсолютное значение, мы получаем b2 как следующее по силе влияние. Далее снова считаем остаток:

От остатка r2 мы, наконец, отсчитываем окончательный DOT PRODUCT между r2 и последним b3:

Следующее основание находится в СИЛЬНОМ влиянии в порядке: b1, b2, b3, с мерой влияния от скалярного произведения: -1,34, 1 и -0,099.

Следовательно, реконструированный x равен

Оригинал был:

Формально мы определяем:
OrthogonalMatchingPursuit и orthogonal_mp реализует алгоритм OMP для аппроксимации соответствия линейной модели с ограничениями, наложенными на количество ненулевых коэффициентов (т. е. псевдонормой L0).

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

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

примечание: источник информации выше.

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

Кредиты

Все кредиты относятся к документации Scikit-learn, а все ссылки соответствуют официальному руководству пользователя.

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

об авторе

Я Венали Сононе, специалист по данным по профессии, а также изучаю менеджмент и стремлюсь продвинуться по карьерной лестнице в финансовой сфере.