[ЗАСТАВКА] Многомерная линейная регрессия — это классическая тема не только для машинного обучения, но и для прикладной статистики. Мы с вами, однако, не будем вдаваться во многие статистические свойства метода наименьших квадратов, а обсудим вопросы, как строить многомерную линейную регрессию, как проходит процесс обучения, и какие-то чисто конструктивные алгоритмические моменты нас будут интересовать больше. Итак, пусть у нас имеется n числовых признаков, имеется обучающая выборка l объектов, и мы хотим построить по обучающей выборке модель многомерной линейной регрессии, то есть это просто взвешенная сумма значений признаков, весовые коэффициенты αj. Перейдем к матричным обозначениям. Матрица объекты-признаки у нас вводилась еще на первой лекции — это матрица, в которой строки соответствуют объектам, столбцы — признакам. Еще нам понадобится вектор ответов или целевой вектор — число строк равно числу объектов обучающей выборки, столбец, естественно, один. И вектор коэффициентов — число строк равно числу признаков, столбец один. Вот в этих трех векторно-матричных обозначениях очень удобно записать постановку задачи наименьших квадратов. Если мы запишем сумму по всем объектам обучающей выборки квадрата разности правильного ответа yi, и ответа нашей модели f (xi, α), то в матричной записи это не что иное, как квадрат нормы разности двух векторов. Вектор y — это вектор правильных ответов, а произведение Fα, матрица F * вектор α, — это есть вектор, который аппроксимирует вектор правильных ответов согласно нашей линейной модели. И наша задача — это найти вектор α при известной матрице F и известном вектор-столбце y. Сделать это можно очень просто. Запишем необходимые условия минимума. Ну мы их здесь записываем в матричном виде, поэтому все получается очень действительно просто и быстро. Мы получаем систему уравнений, опять-таки в матричном виде, из которой мы можем выразить искомый вектор α, и если опять-таки в матричном виде записать этот вектор α, то получается такая очень простая формула — нам нужно псевдо-обратную матрицу F с крестом умножить на вектор правильных ответов y. Это и есть решение. Вопрос лишь в том, как искать эту матрицу F с крестом и какие могут быть проблемы в процессе ее вычисления. Проблем может быть много, и, в частности, проблема может быть в той же самой мультиколлинеарности, о которой мы с вами уже говорили, что если столбцы матрицы F линейно-зависимы, то нам вообще не удастся найти обратную матрицу к F транспонированное, F, она будет вырождена. Если же столбцы этой матрицы F почти линейно-зависимы, то обращаемая матрица будет плохо обусловлена и у нас возникнет масса вычислительных проблем с обращением этой матрицы. Как же считать псевдо-обратную и произведение псевдо-обратной на y, чтобы найти решение нашей системы? Воспользуемся очень распространенным в настоящее время в вычислительно-линейной алгебре, понятием сингулярного разложения. Ну сейчас оно наверное является одним из центральных для решения огромного класса задач анализа данных, в которых данные представляются в виде матриц. Это очень полезное разложение, которое позволяет произвольную прямоугольную матрицу представить в виде произведения трех матриц. Две из них — левая V и правая — U транспонированная, являются ортогональными матрицами, а матрица, которая стоит посерединке — диагональна. Причем ортогональные матрицы не простые, а их столбцы являются собственными векторами, соответственно матриц F на F транспонированное и F транспонированное F. Из линейной алгебры известно, что эти две матрицы имеют хотя и разные собственные векторы, но собственные значения у них совпадают, именно эти собственные значения и записаны на диагонали матрицы D, точнее корни квадратные из этих собственных значений, которые называются сингулярными числами матрицы F. Это представление очень полезно, так как мы сейчас с его помощью буквально за несколько матричных операций получим другое, гораздо более удобное и понятно интерпретируемое представление для вектора решения задачи наименьших квадратов. Итак, псевдо-обратная матрица, то есть F транспонированное F в минус первой степени на F транспонированное, но если F мы подставим сюда, мы знаем его сингулярное разложение, это VD на U транспонированное, если мы подставим и воспользуемся ортогональностью матриц U и V, диагональностью матрицы D, то мы получим очень простое выражение для матрицы F с крестом, которое говорит, что эта сумма матриц ранга один, которая образована произведениями соответственных собственных векторов Uj и Vj транспонированное и еще взятое с коэффициентами, где в знаменателе стоят сингулярные числа. Следующий шаг. Мы хотим получить теперь вектор α со звездой, который является решением задачи наименьших квадратов. Мы должны умножить эту самую F с крестом на y, ну умножаем, и тут же получаем простую формулу, которая означает, что вектор α у нас представим в виде разложения по базису собственных векторов Uj. И опять-таки коэффициенты содержат сингулярные числа знаменателя. Следующий шаг. Давайте посмотрим чему равен вектор, которым наша линейная модель аппроксимирует целевой вектор y, то есть это вектор произведения матрицы F * α. Опять-таки подставляем F в виде сингулярного разложения, подставляем α в виде представления, которые мы только что нашли, снова воспользуемся ортогональностью матрицы U, диагональностью матрицы D, все упростится, и мы получим выражение, которое означает, что аппроксимирующий вектор, который приближает наш вектор y, есть ни что иное, как вот такое представление в базисе собственных векторов Vj. То есть, когда мы нашли сингулярное разложение, собственные векторы Uj и Vj, мы по ним очень быстро вычисляем решение задачи наименьших квадратов. Но и еще можно посчитать, например, такую интересную величину, как квадрат нормы вектора коэффициентов. Опять-таки, пользуясь известными очень простыми формулами из линейной алгебры получаем, что эта норма тоже зависит от сингулярных чисел, которые стоят в знаменателе. И вот, присмотревшись к этим четырем формулам, мы понимаем, что в трех из них сингулярные числа оказались в знаменателе. Если имеются сингулярные числа, приближающиеся к нулю, то мы получаем ту самую проблему мультиколлинеарности. Близкие к нулю собственные значения или сингулярные числа — это как раз и есть свидетельство того, что среди признаков, среди столбцов матрицы F, есть почти линейно-зависимая. И эта проблема приводит к тому, что и псевдо-обратная матрица, и вектор α, и его квадрат нормы становятся очень вычислительно неустойчивыми — близкое к нулю число оказывается в знаменателе. А вот вектор, который аппроксимирует наш целевой вектор y оказывается от сингулярных чисел не зависит. И это означает очень коварный эффект, что нам будет казаться, что этот вектор очень хорошо приближает наш целевой вектор y и, тем не менее, у нас будет вот эта вот проблема мультиколлинеарности и неустойчивости решения в случае, если признаки почти линейно зависимы. Дальше мы с вами будем рассматривать различные способы, каким образом избежать вот этого эффекта мультиколлинеарности. К счастью его можно избежать ничего практически не меняя в том ходе решения, которое я только что рассказал. Тем и хорошо использование сингулярного разложения для решения задач наименьших квадратов, тем, что посмотрев на спектр матрицы, то есть на сингулярные числа, можно сделать совсем небольшие поправки, которые исправят положение и сделают решение устойчивым. Стратегий основных три: либо мы делаем отбор признаков, то есть заранее выкидываем те признаки, которые могут оказаться линейно-зависимыми, либо мы делаем регуляризацию опять-таки, о которой мы говорили в прошлой лекции, мы накладываем дополнительные ограничения на вектор коэффициентов, чтобы он был как можно меньше по норме. Ну и еще один путь — это попытаться сделать преобразование признаков так, чтобы в новом признаковом пространстве у нас признаков оказалось меньше, но они хорошо восстанавливали бы исходные признаки, и, в частности, мы рассмотрим метод главных компонент, который эту задачу решает. И регуляризация и метод главный компонент можно сделать таким образом, чтобы они были основаны на том же самом сингулярном разложении. Итак, резюмируя. Задача многомерной линейной регрессии может быть эффективно решена, если мы умеем решать задачу о сингулярном разложении. И к счастью эта задача на современном уровне развития вычислительно-линейной алгебры очень хорошо решается и есть очень много готовых пакетов, которые решают ее для всевозможных частных случаев, больших матриц, разреженных матриц и так далее. Проблема мультиколлинеарности — это бич, который преследует линейные модели повсюду, но с ним можно справиться. И, наконец, методы устранения мультиколенеарности, которые мы рассмотрим далее — это гребневая регрессия и метод главных компонент. [ЗАСТАВКА]