У нас осталась задача: найти минимум функции Q(a0,a1).
Мы будем использовать итерационный метод, т.е. шаг за шагом перебирать параметры a0 и a1, приближаясь к минимуму (примерно так, как я это делал вручную в предыдущем выпуске). Основной вопрос в том, как именно подбирать значения a0 и a1, чтобы они приближали нас к минимуму функции Q.
Рассмотрим один из наиболее простых и универсальных методов. Метод градиентного спуска (gradient desent). Для простоты рассмотрим функцию одной переменной Q(a). Нам нужно найти её минимум. Выберем произвольное начальное значение a.
*** Метод градиентного спуска основан на производных. Для тех кто знаком с производными, этот абзац не обязателен. Для остальных опишу основную идею. У функции f(x) в каждоый точке можно вычислить производную, которая по сути является скорость роста функции. Обозначается производная штрихом, т.е. f'(x). Если производная f'(x)>0, то по мере роста x, функция будет расти, и наоборот при f'(x)<0 функция убывает с ростом x. Причём чем больше значение производной, тем сильнее изменение функции. А там где функция почти не меняется, производная приближается к нулю. В частности, вблизи точки минимума производная почти равна нулю. Для нас важно, что производная указывает нам направления роста/убывания функции. И при этом практически для любой функции можно выписать её производную. Например, для функции f(x)=x*x производная f'(x)=2*x. Знание производной позволяет экономить вычислительные ресурсы, ведь не вычисляя f(x) для разных х мы уже знаем, растёт ли или убывает функция и насколько быстро. http://img-fotki.yandex.ru/get/2714/140873241.0/0_70611_da8979bb_M.png
Вычислим значение функции Q(a) и её производную в этой точке Q'(a). Далее мы изменяем переменную a в сторону минимума, как нам "подсказывает" производная. Если производная положительная -- это означает, что нам нужно уменьшить a, чтобы приблизиться к минимуму. И наоборот при отрицательной производной следует увеличить a.
Хорошо, нам понятно увеличивать или уменьшать параметр a, но не понятно на сколько сильно его изменять. К сожалению в общем случае нет идеального решения, поэтому можно просто шагать по чуть-чуть. Кроме того можно учесть, что чем ближе к минимуму, тем меньше становится производная. Поэтому на каждом шаге a изменяется по следующей формуле a = a - alpha * Q'(a), где alpha -- параметр, задающий величину шага. Пример на графике, где идёт движение a0 -> a1 -> a2 http://img-fotki.yandex.ru/get/2710/140873241.0/0_70612_ffe6e9b6_M.png
Осталось решить, каков же должен быть параметр alpha? Если выбрать alpha слишком большим, то есть шанс перескочить через минимальное значение (как на рисунке ниже: мы делаем шаг от a0 к a1 в правильном направлении, но шаг настолько большой, что мы удаляемся от минимума). В таком случае мы никогда не найдём минимум, и даже наоборот будем от него уходить. Значит alpha нужно уменьшать. При правильном выборе aplha на каждом шаге градиентного спуска значение функции Q(a) должно уменьшаться. Однако если выбрать alpha слишком маленьким, то мы будем очень долго идти к минимуму. Рано или поздно мы до него дойдём, но потратим много лишнего времени. Таким образом нам нужно будет "поиграть" с параметром alpha, настраивая алгоритм под свои данные. Ниже графически пример со слишком большим alpha (перескочили минимум), и довольно маленьким alpha, когда мы делаем очень много маленьких шагов к минимуму (график ниже) http://img-fotki.yandex.ru/get/6004/140873241.0/0_70613_14c3f622_L.png
И возвращаясь к исходной задаче, мы вспоминаем, что у нас то была функция двух переменных Q(a0,a1). Здесь в точности такой же принцип, только считаются частные производные***. И итоговая формула изменения параметров a0 и a1 выглядит так: http://img-fotki.yandex.ru/get/6005/140873241.0/0_70614_b982f493_M.png *** Для тех кто не знаком с производными: частные производные определяются для функции нескольких переменных. Так частная производная Q по переменной a0 -- это скорость роста функции Q при увеличении параметра a0 и фиксированном параметре a1. Для программирования алгоритма это знание не обязательно, а приводится лишь для желающих глубоко понимать, как это работает.
Нам осталось вычислить производные функции Q. Вспоминая формулу для Q(a0,a1) из прошлого выпуска, вычисляем частные производные: http://img-fotki.yandex.ru/get/6005/140873241.0/0_70615_c8bab496_M.png
У нас получились разные выражения для производной по a0 и a1. Их можно сделать внешне одинаковыми, введя формальную переменную x0i, которая будет всегда равна 1. Тогда http://img-fotki.yandex.ru/get/6003/140873241.0/0_70616_3b9bb8f1_M.png , где j=0,1 Этот трюк упростит нам в дальнейшем написание кода, и является общепринятой практикой.
Итак мы готовы к программированию линейной регрессии, чем и займёмся в следующем выпуске.
