2.3. Градиентный спуск для линейной регрессии
2.3.1. Случай парной регрессии
В случае парной регрессии признак всего один, а линейная модель выглядит следующим образом:
a(x) = w
1
x + w
0
,
где w
1
и w
0
— два параметра.
Среднеквадратичная ошибка принимает вид:
Q(w
0
, w
1
, X) =
1
`
`
X
i=1
(w
1
x i
+ w
0
− y i
)
2
Для нахождения оптимальных параметров будет применяться метод градиентного спуска, про который уже было сказано ранее. Чтобы это сделать, необходимо сначала вычислить частные производные функции ошиб- ки:
∂Q
∂w
1
=
2
`
`
X
i=1
(w
1
x i
+ w
0
− y i
)x i
,
∂Q
∂w
0
=
2
`
`
X
i=1
(w
1
x i
+ w
0
− y i
).
2.3.2. Демонстрация градиентного спуска в случае парной регрессии
Следующие два графика демонстрируют применение метода градиентного спуска в случае парной регрес- сии. Справа изображены точки выборки, а слева — пространство параметров. Точка в этом пространстве обозначает конретную модель.
Рис. 2.2: Демонстрация метода градиентного спуска.
4
График зависимости функции ошибки от числа произведенных операции выглядит следующим образом: 0 20 40 60 80 100 0 50 100 150 200 250 300 номер итерации ошибки Рис. 2.3: Ошибка в зависимости от номера итерации 2.3.3. Выбор размера шага в методе градиентного спускаОчень важно при использовании метода градиентного спуска правильно подбирать шаг. Каких-либо конкрет- ных правил подбора шага не существует, выбор шага — это искусство, но существует несколько полезных закономерностей. w 1 w 2 w 3 w 4 w 5 w 1 w 3 w 5 w 7 w 2 w 4 w 6 Рис. 2.4: Случаи маленького и большого шага Если длина шага слишком мала, то метод будет неспеша, но верно шагать в сторону минимума. Если же взять размер шага очень большим, появляется риск, что метод будет перепрыгивать через минимум. Более того, есть риск того, что градиентный спуск не сойдется. Имеет смысл использовать переменный размер шага: сначала, когда точка минимума находится еще да- леко, двигаться быстро, а позже, спустя некоторое количество итерации — делать более аккуратные шаги. Один из способов задать размер шага следующий: η t = k t , где k — константа, которую необходимо подобрать, а t — номер шага. 2.3.4. Случай многомерной линейной регрессииВ случае многомерной линейной регрессии используется тот же самый подход — необходимо решать задачу минимизации: Q(w, X) = 1 ` kXw − yk 2 → min w , где kxk — норма вектора x. Формула для вычисления градиента принимает следующий вид: ∇ w Q(w, X) = 2 ` X T (Xw − y) 5 Стоит отметить, что вектор Xw − y, который присутствует в данном выражении, представляет собой вектор ошибок. 2.4. Стохастический градиентный спускВ этом блоке речь пойдет о стохастическом градиентном спуске, который особенно хорошо подходит для обучения линейных моделей. 2.4.1. Недостатки обычного метода градиентного спускаВ обычном методе градиентного спуска на каждом шаге итерации следующее приближение получается из предыдущего вычитанием вектора градиента, умноженного на шаг η t : w t = w t−1 − η t ∇Q(w t−1 , X). При этом выражение для градиента в матричной форме имеет вид: ∇ w Q(w, X) = 2 ` X T (Xw − y) Выражение для j-ой компоненты градиента, таким образом, содержит суммирование по всем объектам обу- чающей выборки: ∂Q ∂w j = 2 ` ` X i=1 x j i (hw, x i i − y i ). В этом и состоит основной недостаток метода градиентного спуска — в случае большой выборки даже одна итерация метода градиентного спуска будет производиться долго. 2.4.2. Стохастический градиентный спускИдея стохастического градиентного спуска основана на том, что в сумме в выражении для j-компоненты градиента i-ое слагаемое указывает то, как нужно поменять вес w j , чтобы качество увеличилось для i-го объекта выборки. Вся сумма при этом задает, как нужно изменить этот вес, чтобы повысить качество для всех объектов выборки. В стохастическом методе градиентного спуска градиент функции качества вычисляется только на одном случайно выбранном объекте обучающей выборки. Это позволяет обойти вышеупомянутый недостаток обычного градиентного спуска. Таким образом, алгоритм стохастического градиентного спуска следующий. Сначала выбирается началь- ное приближение: w 0 = 0 Далее последовательно вычисляются итерации w t : сначала случайным образом выбирается объект x i из обучающей выборки X и вычисляется вектор градиента функции качества на этом объекте, а следующее приближение получается из предыдущего вычитанием умноженного на шаг η t полученного вектора: w t = w t−1 − η t ∇Q(w t−1 , {x i }). Итерации прекращаются при достижении определенного условия, например: kw t − w t−1 k < ε. 2.4.3. Сходимость стохастического градиентного спускаПоказательно посмотреть на графики сходимости градиентного спуска и стохастического градиентного спус- ка. В обычном градиентном спуске на каждом шаге уменьшается суммарная ошибка на всех элементах обу- чающей выборки. График в таком случае обычно получается монотонным. 6 0 20 40 60 80 100 0 50 100 150 200 250 300 номер итерации ошибки Рис. 2.5: Ошибка в зависимости от номера итерации Напротив, в стохастическом методе весовые коэффициенты меняются таким образом, чтобы максимально уменьшить ошибку для одного случайно выбранного объекта. Это приводит к тому, что график выглядит пилообразным, то есть на каждой конкретной итерации полная ошибка может как увеличиваться, так и уменьшаться. Но в итоге с ростом номера итерации значение функции уменьшается. 2.4.4. Особенности стохастического градиентного спускаСтохастический градиентный спуск (SGD) обладает целым рядом преймуществ. Во-первых, каждый шаг вы- полняется существенно быстрее шага обычного градиентного метода, а также не требуется постоянно хранить всю обучающую выборку в памяти. Это позволяет использовать для обучения выборки настолько большие, что они не помещаются в память компьютера. Стохастический градиентный спуск также можно использовать для онлайн-обучения, то есть в ситуации, когда на каждом шаге алгоритм получает только один объект и должен учесть его для коррекции модели. 2.5. Линейная классификация2.5.1. Задача бинарной классификацииВ этом разделе рассматривается задача линейной классификации, то есть применение линейных моделей к задаче классификации. Речь пойдет о самом простом виде классификации — бинарной классификации. В случае бинарной классификации множество возможных значений ответов состоит из двух элементов: Y = {−1, +1}. Как уже было сказано, чтобы работать с той или иной моделью нужно: • Выбрать функционал (функцию) ошибки, то есть задать способ определения качества работы того или иного алгоритма на обучающей выборке. • Построить семейство алгоритмов, то есть множество алгоритмов, из которого потом будет выбираться наилучший с точки зрения определенного функционала ошибки. • Ввести метод обучения, то есть определить способ выбора лучшего алгоритма из семейства. 2.5.2. Линейный классификаторРанее была рассмотрена задача линейной регрессии. В этом случае алгоритм представлял собой линейную комбинацию признаков с некоторыми весами и свободным коэффициентом. Линейные классификаторы устроены похожим образом, но они должны возвращать бинарные значения, а следовательно требуется также брать знак от получившегося выражения: a(x) = sign w 0 + d X j=1 w j x j 7 Как и раньше, добавлением еще одного постоянного для всех объектов признака можно привести формулу к более однородному виду: a(x) = sign d+1 X j=1 w j x j = signhw, xi 2.5.3. Геометрический смысл линейного классификатораВыражение hw, xi = 0 является уравнением некоторой плоскости в пространстве признаков. y z x w Рис. 2.6: Геометрический смысл линейного классификатора При этом для точек по одну сторону от этой плоскости скалярное произведение hw, xi будет положитель- ным, а с другой — отрицательным. Таким образом, линейный классификатор проводит плоскость в пространстве признаков и относит объ- екты по разные стороны от нее к разным классам. Согласно геометрическому смыслу скалярного произведения, расстояние от конкретного объекта, который имеет признаковое описание x, до гиперплоскости hw, xi = 0 равно |hw,xi| kwk . С этим связано такое важное понятие в задачах линейной классификации как понятие отступа: M i = y i hw, x i i. Отступ является величиной, определяющей корректность ответа. Если оступ больше нуля M i > 0 , то клас- сификатор дает верный ответ для i-го объекта, в ином случае — ошибается. Причем чем дальше отступ от нуля, тем больше уверенность как в правильном ответе, так и в том, что алгоритм ошибается. Если отступ для некоторого объекта отрицательный и большой по модулю, это значит, что алгоритм неправильно описывает данные: либо этот объект является выбросом, либо алгоритм не пригоден для решения данной задачи. 2.6. Функции потерь в задачах классификации2.6.1. Пороговая функция потерьВ случае линейной классификации естественный способ определить качество того или иного алгоритма — вычислить для объектов обучающей выборки долю неправильных ответов: Q(a, x) = 1 ` ` X i=1 [a(x i ) 6= y i ] 8 С помощью введенного ранее понятия отступа можно переписать это выражение для случая линейной клас- сификации в следующем виде: Q(a, x) = 1 ` ` X i=1 y i hw, x i i < 0 = 1 ` ` X i=1 M i < 0 Функция, стоящая под знаком суммы, называется функцией потерь. В данном случае это пороговая функция потерь, график которой в зависимости от отступа выглядит следующим образом: M i 0 1 Рис. 2.7: График пороговой функции потерь Такая функция является разрывной в точке 0, что делает невозможным применение метода градиентного спуска. Можно, конечно, использовать методы негладкой оптимизации, о которых шла речь в прошлом курсе, но они сложны в реализации. 2.6.2. Оценка функции потерьИспользуя любую гладкую оценку пороговой функции: M i < 0 ≤ ˜ L(M i ) можно построить оценку ˜ Q(a, X) для функционала ошибки Q(a, X): Q(a, X) ≤ ˜ Q(a, X) = 1 ` ` X i=1 ˜ L(M i ). В этом случае минимизировать нужно будет не долю неправильных ответов, а некоторую другую функцию, которая является оценкой сверху: Q(a, X) ≤ ˜ Q(a, X) = 1 ` ` X i=1 ˜ L(M i ) → min a Здесь используется предположение, что в точке минимума этой верхней оценки число ошибок также будет минимально. Строго говоря, это не всегда так. 2.6.3. Примеры оценок функции потерьПримерами таких оценок функции потерь являются: • Логистическая функция потерь (используется в логистической регрессии, о которой пойдет речь позже в данном курсе): ˜ L(M ) = log 2 exp(−M) • Экспоненциальная функция потерь: ˜ L(M ) = exp(−M) 9
• Кусочно-линейная функция потерь (используется в методе опорных векторов):
˜
L(M ) =
max(0, 1 − M)
M
i
0 1
2
Рис. 2.8: Графики различных функций потерь: пороговая (красная линия), экспоненциальная (синяя), логи- стическая (оранжевая) и кусочно-линейная (серая).
2.6.4. Логистическая функция потерь
В случае логистической функции потерь функционал ошибки имеет вид:
˜
Q(a, X) =
1
`
`
X
i=1
ln exp(−M
i
)
=
1
`
`
X
i=1
ln exp(−y i
hw, x i
i)
.
Получившееся выражение является гладким, а, следовательно, можно использовать, например, метод гради- ентного спуска.
Следует обратить внимание, что в случае, если число ошибок стало равно нулю, все равно в ходе обучения алгоритма линейной классификации будут увеличиваться отступы, то есть будет увеличиваться уверенность в полученных результатах.
10
| 
Скачать 1.57 Mb.