[БЕЗ_ЗВУКА] В этом видео
мы поговорим о том, как обучать линейную регрессию, как настраивать ее параметры.
В прошлый раз мы договорились, что измерять качество линейной модели мы будем
с помощью среднеквадратичного функционала ошибки,
который считает квадрат отклонения прогноза линейной модели от истинного
ответа и усредняет эти квадраты отклонений по всем объектам обучающей выборки.
Здесь параметрами являются веса при признаках.
Всего у нас d признаков, весов, значит, тоже d, а значит у нас d неизвестных,
d чисел, которые нам нужно настроить.
При этом мы считаем, что среди признаков есть константный признак,
значения которого на всех объектах равны 1,
благодаря этому нам не нужно включать константные члены в нашу формулу.
Но прежде чем мы перейдем к оптимизации этого функционала, давайте обсудим,
как записать в матричном виде среднеквадратичную ошибку.
Начнем мы с матрицы «объекты–признаки».
Это матрица, в которой l строк, то есть столько, сколько объектов,
и d столбцов, то есть столько, сколько признаков.
В i-том j-том элементе этой матрицы записаны значения j-того признака на
i-том объекте.
Таким образом, мы получаем что в i-той строке этой матрицы
записаны все признаки i-того объекта, а в j-том столбце этой
матрицы записаны значения j-того признака на всех объектах.
Также нам понадобится вектор ответов — это вектор y, i-тый элемент которого равен
yi-тому, то есть истинному ответу на i-том объекте обучающей выборки.
В этом случае мы можем записать в матричном виде среднеквадратичную ошибку,
она будет выглядеть вот так.
Обратите внимание, когда мы умножаем матрицу
«объекты–признаки» X на вектор весов w, мы получаем вектор размера l,
то есть такого размера, сколько у нас всего объектов,
и i-тый элемент этого вектора — это и есть прогноз нашей модели,
скалярное произведение вектора весов на значение признаков на i-том объекте.
Вычитаем из этого вектора вектор y, получаем отклонение прогнозов
алгоритма от истинных ответов, и, вычисляя евклидову норму, возводя ее в квадрат и
после этого поделив на число объектов, получаем среднеквадратичную ошибку.
Это то, что нам нужно минимизировать.
Нам эта формула пригодится, например, для реализации на компьютере.
Так очень удобно вычислять значение среднеквадратичной ошибки на всей выборке.
Можно показать, что если взять градиент от этой функции,
приравнять его к нулю, выразить вектор весов через все остальное, то можно
получить аналитическое решение задачи минимизации среднеквадратичной ошибки.
Оно будет выглядеть вот так.
Чтобы найти оптимальный вектор весов,
нужно умножить матрицу X транспонированное на X, обратить это произведение,
умножить на матрицу X транспонированное и умножить на вектор ответов y.
Конечно, очень хорошо, что решение записывается аналитически.
В этом случае можно не заниматься оптимизацией,
но у аналитического решения есть ряд очень серьезных проблем.
Самая главная проблема состоит в том,
что вам нужно обращать матрицу X транспонированное на X.
Обращение это очень тяжелая операция.
Матрица X транспонированное на X имеет размеры d на d,
то есть число признаков на число признаков.
Обращение такой матрицы требует порядка d в кубе операций, Если у вас тысячи
или десятки тысяч признаков, обращение будет занимать очень много времени.
Также при этом обращении могут возникнуть численные проблемы,
если матрица X транспонированное на X устроена не очень хорошо.
Поэтому гораздо более простым и удобным подходом является оптимизационный.
Несмотря на то что решение можно записать аналитически, давайте все равно с помощью
метода оптимизации искать его, а именно с помощью градиентного спуска.
Можно показать, что среднеквадратичная ошибка — это выпуклая и гладкая функция.
Из выпуклости следует, что у нее всего 1 минимум, а из гладкости следует,
что в каждой ее точке можно посчитать градиент,
и поэтому можно использовать градиентный спуск для оптимизации.
Давайте подробно обсудим алгоритм градиентного спуска.
Начинается он с того, что мы каким-то образом находим начальное приближение
для вектора весов w с верхним индексом 0.
Его можно искать самыми разными способами.
Один из самых простых — это инициализировать
все элементы вектора весов нулями.
То есть w0...
каждая компонента w0 — это ноль.
Есть и другие подходы.
Например, можно инициализировать случайными и не очень большими числами.
Далее в цикле мы повторяем следующие операции.
На t-той итерации цикла мы берем приближение с предыдущей итерации,
то есть wt − 1, и вычитаем из него вектор градиента в этой точке,
умноженный на некоторый коэффициент ηt, который называет шагом.
Почему мы именно так изменяем вектор весов?
Мы обсуждали в прошлом курсе, что градиент показывает в сторону наискорейшего
возрастания функции, а антиградиент, то есть вектор градиента с минусом,
показывает в сторону наискорейшего убывания.
Таким образом, если мы хотим как можно сильнее уменьшить функционал ошибки Q,
нам нужно изменять вектор весов именно в сторону антиградиента,
что здесь и происходит.
Коэффициент ηt (или шаг) нужен для того, чтобы регулировать,
насколько далеко мы шагаем в сторону антиградиента.
Дело в том, что оказывается оптимальным шагать не очень сильно,
мы увидим с вами это чуть дальше.
Эти градиентные шаги повторяются до тех пор, пока не наступит сходимость.
Сходимость можно определять по-разному.
В нашем случае мы ее определяем как ситуацию,
в которой векторы весов от шага к шагу начали меняться не слишком сильно.
То есть норма отклонения вектора весов на текущем шаге от
вектора весов на предыдущем шаге, должна отличаться не более, чем на ε.
В этом случае мы завершаем градиентный спуск.
Если же изменение довольно большое, мы продолжаем его.
Есть и другие подходы к определению сходимости.
Например, можно сравнивать значение функционала ошибки между текущей итерацией
и предыдущей, или использовать еще какие-то способы.
Итак, мы с вами обсудили, как в матричном виде записать
среднеквадратичный функционал ошибки для линейной регрессии, и выяснили,
что у него есть аналитическое решение,
которое тем не менее обладает рядом проблем, его довольно тяжело вычислить.
Поэтому гораздо проще использовать градиентный спуск.
Мы с вами обсудили,
как он устроен и почему в нем шаг делается именно в сторону антиградиента.
В следующем видео мы посмотрим, как выглядит применение градиентного спуска
конкретно для задачи линейной регрессии.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
