Про связь между линейной регрессией, несовместными системами линейных уравнений и прикольным свойством выпуклых функций

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

Итак, в курсах по линейной алгебре практически всегда с самого начала рассказывается про разные способы решения систем алгебраических линейных уравнений (СЛАУ). И зачастую новичкам эта тема кажется скучной ? (мне тоже так казалось, когда я изучала её на первом курсе).

Однако, после изучения других областей математики (и не только), студенту становится понятно, что СЛАУ используются буквально везде, и через них можно выражать практически все что угодно.

В частности, решение СЛАУ (с ненулевыми коэффициентами) равносильно "идеальному" обучению линейной регрессии - то есть, нахождению таких коэффициентов регрессии, которые соответствуют глобальному минимуму среднеквадратичной ошибки (ПРИМЕЧАНИЕ: если вы не знаете, что такое линейная регрессия, можно почитать об этом, например, тут: https://www.alpharithms.com/simple-linear-regression-modeling-502111 , а потом вернуться к посту).

Чтобы понять, как это работает, давайте сопоставим стандартную запись СЛАУ (рис. 1) и список уравнений, которые показывают, как уже обученная линейная регрессия применяется к n примерам (рис. 2).

На случай, если читателю эквивалентность не очевидна, я приложила на рис. 3 вариант того же самого, что изображено на рис. 2, только с заменами:

b? = ?? + ?? - y?,

x? = a?

Как видите, в данном случае a и b приняли на себя роль коэффициентов, а ?? - переменной. А на рис. 4 я привела формулу самой линейной регрессии в качестве напоминания, чтобы читатель имел ее под рукой.

Далее, легко представить себе вместо одной ?? последовательность коэффициентов ??, ??, ... , ??, умноженных на x??, x??, ... , x??, ... , x??, x??, ... , x?? (или a??, a??, ... , a??, ... , a??, a??, ... , a??, если хотите). Тогда у вас будет СЛАУ общего вида с k переменными, уже точь-в-точь как на рис. 1.

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

Теперь про несовместные системы. Часто встречающимся вариантом несовместной СЛАУ является такая система, в которой уравнений больше, чем неизвестных, и ни одно уравнение не является линейной комбинацией других. И в самом деле: в случае линейной регрессии, уравнений ровно столько, сколько есть примеров в обучающем множестве. Размер же обучающего множества для линейной регрессии обычно берется больший, чем количество её параметров.

(Конечно, если мы возьмём количество примеров меньше, чем параметров, то получим решение без ошибки, но зато коэффициенты модели не будут определены однозначно. Это одна из причин, почему так обычно не делают.)

Так вот. Когда мы имеем несовместную систему уравнений, мы можем решить её не только градиентным спуском, но и аналитически, выписав решение явно. Это делается с помощью Метода Наименьших Квадратов (МНК). В применении к линейной регрессии этот метод хорошо описан, например, здесь:

https://www.alpharithms.com/simple-linear-regression-modeling-502111

в разделе "Building the Model".

Кстати, все формулы для линейной регрессии я взяла оттуда же.

Остаётся, тем не менее, вопрос: а будет ли решение, полученное МНК, таким же, как решение, полученное градиентным спуском?

Оказывается, что в пределе это так, благодаря тому, что наша функция ошибки в данном случае описывается суммой квадратов разностей, то есть, суммой выпуклых функций, а значит, и сама выпуклая. Дело в том, что если функция ошибки гладкая, то градиентный спуск стремится сойтись к её локальному минимуму (насколько именно близко он к нему подходит - зависит от шага обучения; однако, можно подобрать такой шаг, чтобы градиентный спуск подобрался к этому минимуму сколь угодно близко). В случае же строго выпуклой функции минимум только один, и он одновременно является и локальным, и глобальным (см. рис.5 для интуитивного понимания и https://ai.stanford.edu/~gwthomas/notes/convexity.pdf для строгого доказательства - оно дано в Proposition 2). Именно поэтому для линейной регрессии градиентный спуск стремится именно к тому решению, что даётся МНК.

Вот сколько интересного таит в себе простая система линейных уравнений...

Источник: www.alpharithms.com

Комментарии: