_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007).pdf), страница 6

Обобщенные линейные модели31Регуляризация задачи• Заметим, что формула для весов линейной регрессии представляет собой псевдорешение уравненияΦw = tX Упр.• Матрица ΦT Φ ∈ Rm×m вырождена при m > n• Регуляризуя вырожденную матрицу, получаем¡¢−1 Tw = ΦT Φ + λIΦ t• Отсюда формула для прогноза объектов обучающей выборки по их правильным значениям¡¢−1 Tt̂ = y = Φ ΦT Φ + λIΦ t = HtС историческим обозначением прогноза — навешиванием шляпки связано неформальное название матрицы H, поанглийски звучащее как hat-matrixОсобенности квадратичной функции потерь• Достоинства– Квадратичная функция потерь гладкая (непрерывная и дифференцируемая)– Решение может быть получено в явном виде– Существует простая вероятностная интерпретация прогноза и функции потерь• Недостатки– Решение неустойчиво (не робастно) относительно даже малого количества выбросов.

Это связано с быстрым возрастанием квадратичной функции потерь при больших отклонениях отнуля– Квадратичная функция неприменима к задачам классификации3.2.3Вероятностная постановка задачиНормальное распределение ошибок• Рассмотрим вероятностную постановку задачи восстановления регрессии. Регрессионная переменнаяt — случайная величина с плотностью распределения p(t|x)• В большинстве случаев предполагается, что t распределена нормально относительно некоторого мат.ожидания y(x), определяемого точкой xt = y(x) + ε,ε ∼ N (ε|0, σ 2 )• Необходимо найти функцию y(x), которую мы можем отождествить с уравнением регрессии• Предположение о нормальном распределении отклонений можно обосновать ссылкой на центральную предельную теоремуГлава 3.

Обобщенные линейные модели32Метод максимального правдоподобия для регрессии• Используем ММП для поиска y(x)• Правдоподобие задается следующей формуло鵶1(ti − yi )2√p(t|y) =exp −→ max2σ 22πσi=1nY• Взяв логарифм и отбросив члены, не влияющие на положение максимума, получимnnXX(ti − yi )2 =(ti − wT φ(xi ))2 → mini=1wi=1• Таким образом, применение метода максимального правдоподобия в предположении о нормальности отклонений эквивалентно методу наименьших квадратовВероятностный смысл регуляризации• Теперь будем максимизировать не правдоподобие, а апостериорную вероятность• По формуле условной вероятностиp(w|t, X) =p(t|X, w)p(w)→ max,wp(t, X)знаменатель не зависит от w, поэтому им можно пренебречь³ ¯ ³ 2´ ´¯• Пусть p(w) ∼ N w ¯0, σλ I .

Тогдаp(w|t, X) ∝ ¡√µµ¶¶1λm/2λ−222exp−σkΦw−tk+kwk¢m+n2σ22πσ• Логарифмируя и приравнивая производную по w к нулю, получаемw = (ΦT Φ + λI)−1 Φt• Регуляризация эквивалентна введению априорного распределения, поощряющегонебольшие веса3.33.3.1Применение регрессионных методов для задачи классификацииЛогистическая регрессияОсобенности задачи классификации• Рассмотрим задачу классификации на два класса t ∈ {−1, +1}• Ее можно свести к задаче регрессии, например, следующим образомt̂(x) = sign(y(x)) = signmXj=1wj φj (x)Глава 3.

Обобщенные линейные модели33• Возникает вопрос: что использовать в качестве значений регрессионной переменной на этапе обучения?• Наиболее распространенный подход заключается в использовании значения +∞ для t = +1 и −∞для t = −1• Геометрический смысл: чем дальше от нуля значение y(x), тем увереннее мы в классификацииобъекта xПравдоподобие правильной классификации• Метод наименьших квадратов, очевидно, неприменим при таком подходе• Воспользуемся вероятностной постановкой для выписывания функционала качества• Определим правдоподобие классификации следующим образомp(t|x, w) =11 + exp(−ty(x))• Это логистическая функция (см.

рис. 3.2). Легко показать, чтозначит, она является функцией правдоподобияPtp(t|x, w) = 1 и p(t|x, w) > 0, а,10.80.60.40.20−5−4−3−2−1012345Рис. 3.2. Логистическая функция переводит выход линейной функции в вероятностные значения. Черная кривая показываетправдоподобие для случая ti = 1, а серая кривая — для случая ti = −1Функционал качества в логистической регрессии• Правдоподобие правильной классификации всей выборки имеет видp(t|X, w) =nYi=13.3.2p(ti |xi , w) =nY³i=1 1 + exp −ti1Pm´j=1 wj φj (xi )Метод IRLSОсобенности функции правдоподобия классификации• Приравнивание градиента логарифма правдоподобия к нулю приводит к трансцендентным уравнениям, которые неразрешимы аналитически• Легко показать, что гессиан логарифма правдоподобия неположительно определен∂ 2 log p(t|x, w)≤0∂w2Глава 3.

Обобщенные линейные модели34• Это означает, что логарифм функции правдоподобия является вогнутым.• Логарифм правдоподобия обучающей выборки L(w) = log p(t|X, w), являющийся суммой вогнутыхфункций, также вогнут, а, значит, имеет единственный максимумМетод оптимизации НьютонаОсновная идея метода Ньютона — это приближение в заданной точке оптимизируемой функции параболой и выбор минимума этой параболы в качестве следующей точки итерационного процесса:f (x) → minw1f (x) ' g(x) = f (x0 ) + (∇f (x0 )) (x − x0 ) + (x − x0 )T (∇∇f (x0 ))(x − x0 )2∇g(x∗ ) = ∇f (x0 ) + (∇∇f (x0 ))(x∗ − x0 ) = 0Tx∗ = x0 − (∇∇f (x0 ))−1 (∇f (x0 ))g(x)f(x)x1x02Рис. 3.3.

Пример оптимизации с помощью метода Ньютона. Функция f (x) = log(1 + exp(x)) + x5 . В точке x0 = 6 проведеноприближение функции f (x) параболой g(x). Точка минимума этой параболы x1 = −2.4418 является следующей точкойитерационного процессаИтеративная минимизация логарифма правдоподобия• Так как прямая минимизация правдоподобия невозможна, воспользуемся итерационным методомНьютона• Обоснованием корректности использования метода Ньютона является унимодальность оптимизируемой функции L(w) и ее гладкость во всем пространстве весов• Формула пересчета в методе Ньютонаwnew = wold − H −1 ∇L(w),где H = ∇∇L(w) — гессиан логарифма правдоподобия обучающей выборкиФормулы пересчета1Обозначим si = 1+exp(−t, тогда:i yi )∇L(w) = ΦT diag(t)s,∇∇L(w) = ΦT RΦГлава 3.

Обобщенные линейные модели35s1 (1 − s1 )0R=...0wnew = wold − (ΦT RΦ)−1 ΦT diag(t)s =0...s2 (1 − s2 ) . . ..........000...sn (1 − sn )¡¢(ΦT RΦ)−1 ΦT RΦwold − ΦT RR−1 diag(t)s = (ΦT RΦ)−1 ΦT Rz,где z = Φwold − R−1 diag(t)sНазвание метода (метод наименьших квадратов с итеративно пересчитываемыми весами) связано стем, что последняя формула является формулой для взвешенного МНК (веса задаются диагональнойматрицей R), причем на каждой итерации веса корректируютсяЗаключительные замечания• На практике матрица ΦT RΦ часто бывает вырождена (всегда при m > n), поэтому обычно прибегаютк регуляризации матрицы (ΦT RΦ + λI)• !! Параметр регуляризации λ является структурным параметром!!• !! Базисные функции φj (x), а значит и матрица Φ являются структурными параметрами!!• С поиском методов автоматического выбора базисных функций связана одна из наиболее интригующих проблем современного машинного обученияГлава 4Метод опорных векторов ибеспризнаковое распознавание образовВ главе подробно рассматривается метод опорных векторов для классификации и восстановления регрессии.

Особое внимание уделено формулировке двойственной задачи и использованию правила множителейЛагранжа. Описывается т.н. ядровой переход, представляющий нелинейное обобщение метода опорныхвекторов, показана связь между этим методом и методом максимального правдоподобия с регуляризацией,а также со статистической теорией обучения Вапника-Червоненкиса. В конце главы приведены обобщения метода опорных векторов на задачи, в которых подсчет признаков невозможен или нецелесообразен,но в которых естественным образом можно ввести функцию близости между объектам.36Глава 4.

Метод опорных векторов и беспризнаковое распознавание образов37Рис. 4.1. Иллюстрация к задаче оптимизации с ограничениям в виде равенства. В оптимальной точке градиенты ∇f и ∇gдолжны быть параллельны друг другу4.1Ликбез: Условная оптимизацияЗадача условной оптимизацииПусть f (x) : Rd → R — гладкая функция. Предположим, что нам необходимо найти ее экстремум:f (x) → extrxДля того, чтобы найти экстремум (решить задачу безусловной оптимизации), достаточно проверить условие стационарности:∇f (x) = 0Предположим, что нам необходимо найти экстремум функции при ограничениях:f (x) → extrxg(x) = 0Поверхность ограничения (см.

рис. 4.1)Заметим, что ∇g(x) ортогонален поверхности ограничения g(x) = 0. Пусть x и x + ε — две близкиеточки поверхности. Тогдаg(x + ε) ' g(x) + εT ∇g(x)Т.к. g(x + ε) = g(x), то εT ∇g(x) ' 0. При стремлении kεk → 0 получаем εT ∇g(x) = 0. Т.к. ε параллеленповерхности g(x) = 0, то ∇g(x) является нормалью к этой поверхности.Функция ЛагранжаНеобходимым условием оптимальности является ортогональность ∇f (x) поверхности ограничения (впротивном случае вектор проекции градиента ∇f (x) на поверхность ограничения имеет ненулевую длину,и можно найти большее значение функции, двигаясь вдоль вектора проекции), т.е.:∇f + λ∇g = 0Здесь λ 6= 0 — коэффициент Лагранжа. Он может быть любого знака.Функция ЛагранжаL(x, λ) , f (x) + λg(x)Глава 4.