Понять, как SVD помогает получить согласованный вектор весов методом наименьших квадратов для пере- и недоопределенных линейных систем.
В этой статье обсуждается разница в весовых векторах методом наименьших квадратов между переопределенными и недоопределенными линейными системами, а также то, как разложение по сингулярным значениям (SVD) может быть применено для получения согласованного выражения. Он в значительной степени основан на курсе профессора Ребекки Уиллет Математические основы машинного обучения и предполагает базовые знания линейной алгебры.
«Типичные» наименьшие квадраты
Наименьшие квадраты можно описать следующим образом: с учетом матрицы признаков X формы n × p и целевого вектора y формы n × 1, мы хотим найти вектор коэффициентов w ' формы n × 1 , которая удовлетворяет w ' = argmin {∥ y - Xw ∥²}. Интуитивно метод наименьших квадратов пытается аппроксимировать решение линейных систем, минимизируя сумму квадратов невязок, полученных в результате каждого отдельного уравнения.
В большинстве случаев мы предполагаем, что n ≥ p и rank (X) = p. Другими словами, количество наблюдений не меньше, чем количество функций, и ни одна из функций не является линейной комбинацией других (без избыточных функций). Линейная система y = Xw переопределена, если n ≥ p. Мы можем получить w ’ с помощью нормального уравнения :
Однако, если n ‹p или когда некоторые столбцы в X линейно зависимы, матрица A не может быть обратимым. Когда количество функций больше, чем количество наблюдений, мы называем линейную систему y = Xw недоопределенной.
Недоопределенные наименьшие квадраты
Когда n ‹p и rank (X) = n, существует бесконечно много решений для системы y = Xw. Среди этих решений мы можем найти решение с наименьшей нормой с помощью метода множителя Лагранжа и использовать его в качестве весового вектора наименьших квадратов для недоопределенной линейной системы.
Однако почему желательно решение, отвечающее минимальным нормам? Представьте себе простой случай, когда у вас есть следующая матрица обучающих функций и целевой вектор:
Оба следующих вектора веса идеально подходят для данных обучения:
Можно взглянуть на это с трудом: третья особенность мала по размеру. Если он уязвим для ошибки измерения и мы приписываем ему большой вес, наши прогнозы на основе невидимых данных могут быть сильно искажены одной только третьей особенностью и, таким образом, далеки от истинной цели. Поэтому первое решение лучше.
Ниже показано, как мы получаем решение с наименьшей нормой с множителем Лагранжа: мы хотим минимизировать ∥ w ∥² с ограничением, которое y = Xw . Введите множитель Лагранжа L:
В оптимальных условиях:
Уравнение вектора весов для недоопределенных наименьших квадратов сильно отличается от уравнения для переопределенных наименьших квадратов.
Разложение по сингулярным значениям
В этом разделе представлено базовое введение в SVD. Рассмотрим матрицу X формы n × p. Всегда существуют матрицы U, Σ, V такое, что:
Если оба элемента U и V ортогональны:
Σ по диагонали:
Столбцы U являются левыми сингулярными векторами, они образуют ортонормированный базис для столбцов X.
Диагональные элементы Σ называются сингулярными значениями (σ₁ ≥ σ₂ ≥… ≥ σₚ ≥ 0). Количество ненулевых сингулярных значений - это ранг матрицы X, а столбцы Σ являются основой для строк X .
Строки V называются правыми сингулярными векторами, они являются базисными коэффициентами в столбцах UΣ для представления каждого столбца X.
СВД и метод наименьших квадратов
С помощью SVD мы можем переписать весовые векторы методом наименьших квадратов. Используйте в качестве примера метод недоопределенных наименьших квадратов:
Выражение выше может показаться немного устрашающим, но если мы присмотримся внимательнее:
Здесь Σ⁺ является псевдо-инверсией Σ и имеет форму p × n . Мы можем получить это, переставив Σ и взяв обратные величины его диагональным элементам. Тогда вектор наименьших квадратов недоопределенной линейной системы можно переписать как:
То же самое и с переопределенным методом наименьших квадратов (не стесняйтесь проверить). С SVD у нас есть согласованное выражение вектора весов.
Проверка
Чтобы проверить наши выводы, мы будем использовать подвыборку наборов данных Jester. Выборка содержит 100 наблюдений и 7200 объектов и доступна здесь. Каждое наблюдение - это шутка, а каждая особенность - это известная оценка этой шутки существующим пользователем по шкале от -10 до 10.
Предположим, мы работаем в компании, которая дает клиентам шутливые рекомендации на основе их известных рейтингов. Для нового клиента Джоан, который оценил 25 шуток, мы хотим знать, как ей понравятся оставшиеся 75 шуток, и рекомендовать ей ту, которая имеет самый высокий прогнозируемый рейтинг.
Для этого рассмотрим m (m ≤ 7200) пользователей, чьи оценки по 100 анекдотам нам известны. Они представляют собой разнообразный набор вкусов. Мы можем рассматривать рейтинги Джоан как взвешенную сумму оценок этих клиентов. Затем мы будем использовать 25 шутливых оценок этих m клиентов в качестве характеристик, а известные рейтинги Джоан - в качестве цели для обучения регрессору. Он должен иметь возможность обобщить другие шутки, которые Джоан еще не оценила, с хорошими прогнозами, чтобы мы могли порекомендовать шутку с наивысшим прогнозируемым баллом. Оценки Жанны доступны здесь.
Загрузите данные и разделите их на обучающий и тестовый набор с помощью следующего фрагмента. Обратите внимание, что неизвестные рейтинги Джоан представлены как -99.
Когда m = 20, мы будем использовать первых 20 пользователей в качестве типичных пользователей для простоты. Мы найдем весовые коэффициенты на основе их оценок 25 шуток, которые Джоан оценила как особенности, а оценки Джоан - как целевые. Линейная система переопределена. Когда m = 7200, линейная система недоопределена. Используйте следующие коды для подготовки данных.
Оценщик наименьших квадратов в стиле scikit-learn с использованием SVD реализован следующим образом:
Вычислите вектор весов и сравните его с полученным из нормального уравнения:
Я получил «Истина» как для m = 20, так и для m = 7200. Не стесняйтесь проверить это сами.
Чтобы проиллюстрировать, как недоопределенный метод наименьших квадратов обеспечивает идеальное соответствие обучающим данным, мы можем визуализировать предсказанные значения и истинную цель как для обучающих, так и для тестовых наборов. Соответствующие коды доступны здесь.
Эта статья написана Кунью Хэ. Кунью сейчас учится в магистратуре Чикагского университета. Ему интересно понимать методы статистического моделирования и машинного обучения, применять их к реальным данным и помогать создавать комплексные решения в индустрии финансовых услуг. Свяжитесь с Кунью в LinkedIn! 🐷
