Заметки об изучении алгоритма градиентного спуска
Содержание взято из «Открытого курса машинного обучения и интеллектуального анализа данных» Стэнфордского университета.
В алгоритме используется много знаний линейной алгебры. Поэтому я чувствую необходимость сначала просмотреть и разобраться в основах линейной алгебры.
1 Основные понятия и обозначения
Линейная алгебра предоставляет удобный способ выражения и обработки линейных уравнений, таких как следующие уравнения:
4x1-5x2=13
-2x1+3x2=-9
Его можно просто выразить следующим образом:
X также является матрицей, то есть (x1,x2)T, конечно, вы можете думать о ней как о вектор-столбце.
1.1 Основные обозначения
Пусть A ∈ представляет собой матрицу A с m строками, n столбцами, и каждый элемент матрицы является вещественным числом.
Используйте x ∈ , чтобы представить n-мерный вектор. Обычно вектор-столбец. Если вы хотите представить вектор-строку, он обычно представлен транспонированием вектора-столбца (добавьте T после него).
1.2 Внутреннее и внешнее произведение векторов
Согласно определению в классе, если форма xT y или yT x, она выражается как скалярный продукт, и результатом является действительное число, что означает:, если он имеет форму xyT, он представляет внешний продукт:
.
1.3 Умножение матрицы на вектор
Для матрицы A ∈ Rm×n и вектора x ∈ Rn их произведение есть вектор y = Ax ∈ Rm. То есть следующее представление:
Если A — матрица, представленная строками (то есть представленная как), то представление y:
И наоборот, если A - матрица, представленная столбцами, представление y:
То есть: y рассматривается как линейная комбинация столбцов A, каждый столбец умножается на коэффициент и добавляется, а коэффициент получается через x.
Так же,
yT=xT*A выражается как:
yT представляет собой линейную комбинацию строк A, каждая строка умножается на коэффициент и складывается, коэффициент задается x.
1.4 Матричное умножение матриц
Также есть два представления:
Первый: A представлен в виде строки, B представлен в виде столбца
Во втором A представлен в виде столбца, а B представлен в виде строки:
По сути то же самое, только выражено по-разному.
1.5 Градиентная операция матрицы (это настраивается учителем)
Определите функцию f, которая является отображением матрицы m x n в действительное число, тогда градиент f на A определяется следующим образом:
Я понимаю здесь, что f(A) = выражение об элементах в A, которое является действительным числом, и тогда так называемый градиент для A является матрицей того же масштаба, что и A, и каждый элемент в матрице равен f(A ) относительно вывода исходного элемента.
1.6 Другие концепции
Из-за недостатка места я не буду повторять их здесь.Другие требуемые понятия включают единичную матрицу, диагональную матрицу, транспонированную матрицу, симметричную матрицу (AT=A), антисимметричную матрицу (A=-AT), след матрицы, модуль векторов, линейный независимость, ранг матриц, матрица полного ранга, обратная матрица (обратимая тогда и только тогда, когда матрица имеет полный ранг), ортогональная матрица, пространство столбцов матрицы (диапазон значений), определитель, собственный вектор и собственное значение……
2 Используемая формула
В курсе используется много формул, перечислите их. Ну, доказательства некоторых формул очень просты, а доказательства некоторых сложных мне тоже не известны, а думать об этом лень.
Транспонировать связанные:
• (АТ)Т = А
• (АВ)Т = ВТ В
• (А + В)Т = АТ + ВТ
Связанные с трассировкой:
• Для A ∈ Rn×n trA = trAT.
• Для A, B ∈ Rn×n tr(A + B) = trA + trB.
• Для A ∈ Rn×n, t ∈ R, tr(tA) = t trA.
• Для A, B таких, что AB квадратная, trAB = trBA.
• Для A, B, C, таких что ABC квадратная, trABC = trBCA = trCAB. То же самое верно и при большем количестве умножений, то есть каждый раз, когда матрица берется с конца и помещается впереди, следы матриц, полученных таким умножением матриц, согласуются.
ранговая корреляция
• Для A ∈ Rm×n rank(A) ⩽ min(m, n).Если rank(A) = min(m, n), то A называется полным рангом.
• Для A ∈ Rm×n, rank(A) = rank(AT).
• Для A ∈ Rm×n, B ∈ Rn×p, rank(AB) ≤ min(rank(A), rank(B)).
• Для A, B ∈ Rm×n, rank(A + B) ≤ rank(A) + rank(B).
Обратная корреляция:
• (А-1)-1 = А
• Если Ax = b, умножьте и влево, и вправо на A−1, чтобы получить x = A−1b.
• (АВ)-1 = В-1А-1
• (A-1)T = (AT)-1 F обычно выражается как A-T.
Связанный определитель:
• Для A ∈ Rn×n |A|=|AT|.
• Для A, B ∈ Rn×n |AB|=|A||B|.
• Для A ∈ Rn×n |A|=0, что указывает на то, что матрица A является сингулярной и необратимой.
• Для A ∈ Rn×n и A обратим, |A|−1 = 1/|A|.
Корреляция градиента:
• ∇x(f(x) + g(x)) = ∇xf(x) + ∇xg(x) • Для t ∈ R ∇x(t f(x)) = t∇xf(x).
• ∇xbT x = b
• ∇xxT Ax = 2Ax (если A симметрична)
• ∇2xxT Ax = 2A (если A симметрично)
• ∇A|A|=(adj(A))T = |A|A−T , adj=присоединенный
3 Алгоритм градиентного спуска и применение нормальных уравнений
В примере используется пример цены жилья в предыдущем классе.Есть набор данных, в том числе площадь дома и цена дома.Пример формата ввода:
Переменные, определяемые учителем, следующие:
m: количество обучающих выборок
x: входные переменные (вводные характеристики, в данном случае площадь дома, а позже добавлено количество спален в доме)
y : выходная переменная (целевая переменная, в данном случае цена дома)
(x,y): представляет выборку
: представляет i-й образец, обозначаемый как
.
3.1 Концепции контролируемого обучения
Так называемое обучение с учителем заключается в том, чтобы сообщать алгоритму правильный ответ для каждого образца, и обученный алгоритм также может вводить правильный ответ для нового ввода. Наблюдение относится к наблюдению за ответами обучающей выборки, а h представляет собой функцию обучения под наблюдением.
В этом примере мы предполагаем, что выходная целевая переменная представляет собой линейную комбинацию входных переменных, то есть наше предположение состоит в том, чтобы хранить следующее h(x):
Тета-представление — это параметр перед функцией (также называемый весом функции). То есть то, что вы получаете после h(x), является предсказанным результатом.
Если предполагается x0=1, то исходный h(x) можно просто выразить следующим образом:
, где n — количество признаков.Для простоты мы записываем тета и х в виде векторов. Вот как найти θ (вектор) так, чтобы h(x) был как можно ближе к фактическому результату, по крайней мере, в пределах обучающей выборки, к правильному ответу в обучающей выборке.
Мы определяем функцию стоимости, которая вычисляет разницу между h(x) и фактическим значением для каждого набора θ. Определяется следующим образом:
Это также идея метода наименьших квадратов, но причина умножения на 1/2 заключается в упрощении последующих вычислений. для каждого набора данных в обучающем наборе. Оставшаяся проблема состоит в том, чтобы получить значение θ, когда minJ(θ), потому что J(θ) изменяется с изменением θ, поэтому θ, когда мы запрашиваем minJ(θ), является желаемым θ (этот минимум также известен как функция минимальной стоимости), как найти этот набор тета? Используемый метод представляет собой алгоритм градиентного спуска и систему нормальных уравнений. Давайте сначала посмотрим на алгоритм градиентного спуска.
3.2 Алгоритм градиентного спуска
Алгоритм градиентного спуска — алгоритм поиска, основную идею можно понять так: мы начинаем с определенной точки на горе, находим самый крутой склон и делаем шаг (то есть находим направление градиента), а затем находим самый крутой склон после достижения точки. , и делаем еще один шаг, пока не продолжим идти в том же духе, пока не достигнем «самой низкой» точки (точки, где сходится функция минимальной стоимости).
Как показано на рисунке выше, x и y представляют собой theta0 и theta1, а направление z представляет функцию стоимости Очевидно, что начальные точки разные, и конечная точка сходимости может быть другой. Конечно, если он чашеобразный, то точка схождения должна быть такой же.
Тета-обновление алгоритма выражается следующим образом:
Для каждого тета (j) сначала найдите частную производную (направление градиента) от J (θ) до тета (j), затем уменьшите α, а затем введите текущую тета (j), чтобы получить новую тета (j) до Обновить. Где α — размер шага, вы можете понимать его как размер шагов, которые мы делаем, когда спускаемся с горы. Если шаг слишком мал, скорость сходимости низкая, а если шаг слишком велик, он может колебаться взад и вперед вблизи точки сходимости и не может достичь самой нижней точки. P.S.По словам преподавателя, этот символ понимается в программе как символ присваивания (знак =), если это знак =, то понимается, что значение равно (знак == в программировании).
Давайте сначала разберемся, предположив, что в обучающем наборе есть только один набор данных для нахождения частной производной тета (j):
принестиМожно получить выражение тета(j) о группе данных Ну, эта группа данных является i-й группой, которая выражается как:
Затем мы распространяем этот метод обновления theta(j) на m обучающих выборок и можем получить следующую формулу:
P.S. Под самым внешним xj(i) понимается: j-е значение признака в i-й группе данных.
3.2.1 Алгоритм пакетного градиентного спуска (алгоритм пакетного gxxxx dxxxx)
Повторяйте описанный выше шаг обновления до сходимости, вы можете получить значение этого набора θ. Это процесс:
.
Этот алгоритм представляет собой алгоритм пакетного градиентного спуска, почему он называется пакетным градиентным спуском? Поскольку отмечено, что каждое обновление θj в приведенной выше формуле требует расчета всех выборочных значений, поэтому, когда количество выборок очень велико (например, десятки тысяч или даже сотни тысяч), такое обновление происходит очень медленно, и найти θ тоже сложно, очень медленно, поэтому есть еще один улучшенный алгоритм градиентного спуска.
3.2.2 Стохастический градиентный спуск/Пошаговый градиентный спуск
Сделайте небольшое улучшение, обновив образец тета. Преимущество этого метода в том, что скорость определенно выше, чем у алгоритма пакетного градиентного спуска, и чем больше выборочных данных, тем более очевидной должна быть производительность. Недостатком является то, что значение результирующей точки сходимости может быть неоптимальным по сравнению с алгоритмом пакетного градиента.
3.2.3 Краткое изложение алгоритма градиентного спуска
Будь то алгоритм пакетного градиента или алгоритм стохастического градиентного спуска, у них есть следующее общее:
1. Временная сложность O(mn) (m — количество выборок, n — количество собственных значений/влияющих факторов)
2. Оба обладают свойством градиентного спуска: при приближении к сходимости каждый «шаг» (имеется в виду реально вычитаемое число, а не определенное ранее α, α — параметр, задаваемый вручную, и изменится он только после искусственных изменений) станет все меньше и меньше. Причина этого в том, что каждый раз, когда вы вычитаете α, умноженное на градиент, но по мере сходимости градиент будет становиться все меньше и меньше, поэтому вычитаемое значение будет уменьшаться.
3. Существует два метода определения сходимости:
1) Изменение значения двух итераций крайне мало
2) Значение J(θ) меняется очень мало
3.3 Нормальные уравнения
Написано ранее: Этот метод является другим методом, и он не имеет ничего общего с алгоритмом градиентного спуска! ! ! ! ! !
Сначала просмотрите операцию матричного градиента, определенную ранее:
Например:
но:
Определите матрицу, называемую матрицей плана, которая представляет все образцы входных данных:
Из-за предыдущих выводов:(Результат транспонирования * θ для θT * x (i) и x (i) одинаков), вы можете получить
Его можно записать в следующем виде:
А поскольку для любого вектора, поэтому вы можете получить:
Используйте набор свойств, описанный ниже:
(5) получается из (2) и (3), следующий вывод
Причина, по которой добавление tr в середине не изменилось, заключается в том, что это действительное число (как матрица 1x1), а трассировка равна самой себе.
Установите приведенную выше формулу на 0, чтобы получить нормальную систему уравнений.
Решите, чтобы получить