2010 Лекции МОТП (Ветров) (1185317), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

. . , MЛинейнаярегрессияКлассическаялинейнаярегрессияМетоднаименьшихквадратовВероятностнаяпостановказадачиПрименениерегрессионныхметодов длязадачиклассификацииM =11t0−10x1Зачем нужна реугляризация весовОбобщенныелинейные моделиВетровНапоминаниеРассмотрим задачу восстановления регрессии сполиномиальными базисными функциями: x ∈ R, φj (x) = xj ,j = 0, . . . , MЛинейнаярегрессияКлассическаялинейнаярегрессияМетоднаименьшихквадратовВероятностнаяпостановказадачиПрименениерегрессионныхметодов длязадачиклассификацииM =31t0−10x1Зачем нужна реугляризация весовОбобщенныелинейные моделиВетровНапоминаниеРассмотрим задачу восстановления регрессии сполиномиальными базисными функциями: x ∈ R, φj (x) = xj ,j = 0, .

. . , MЛинейнаярегрессияКлассическаялинейнаярегрессияМетоднаименьшихквадратовВероятностнаяпостановказадачиПрименениерегрессионныхметодов длязадачиклассификацииM =91t0−10x1Значения наиболее правдоподобных весовОбобщенныелинейные моделиВетровweight M = 0 M = 1 M = 3w00.19M=90.820.310.35-1.277.99232.37Напоминаниеw1Линейнаярегрессияw2-25.43-5321.83w317.3748568.31КлассическаялинейнаярегрессияМетоднаименьшихквадратовВероятностнаяпостановказадачиПрименениерегрессионныхметодов длязадачиклассификацииw4-231639.30w5640042.26w6-1061800.52w71042400.18w8-557682.99w9125201.43Таблица: Значения наиболее правдоподобных весов взависимости от степени полинома. С увеличением степени,абсолютные значения весов быстро растутПлан лекцииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS1 НапоминаниеФормула БайесаРешение нерешаемых систем уравнений2 Линейная регрессияКлассическая линейная регрессияМетод наименьших квадратовВероятностная постановка задачи3 Применение регрессионных методов для задачи классификациЛогистическая регрессияМетод IRLSОсобенности задачи классификацииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS• Рассмотрим задачу классификации на два классаt ∈ {−1, +1}• Ее можно свести к задаче регрессии, например,следующим образомt̂(x) = sign(y(x)) = signmXwj φj (x)j=1• Возникает вопрос: что использовать в качествезначений регрессионной переменной на этапе обучения?• Наиболее распространенный подход заключается виспользовании значения +∞ для t = +1 и −∞ дляt = −1• Геометрический смысл: чем дальше от нуля значениеy(x), тем увереннее мы в классификации объекта xПравдоподобие правильной классификацииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS• Метод наименьших квадратов, очевидно, неприменимпри таком подходе• Воспользуемся вероятностной постановкой длявыписывания функционала качества• Определим правдоподобие классификации следующимобразом1p(t|x, w) =1 + exp(−ty(x))• Это логистическая функция.

Легко показать, чтоPt p(t|x, w) = 1 и p(t|x, w) > 0, а, значит, она являетсяфункцией правдоподобияФункционал качества в логистическойрегрессииОбобщенныелинейные модели1ВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификации0.5ЛогистическаярегрессияМетод IRLS0−505• Правдоподобие правильной классификации всейвыборки имеет видnnYYp(t|X, w) =p(ti |xi , w) =i=1i=11³ P´m1 + exp −ti j=1 wj φj (xi )План лекцииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS1 НапоминаниеФормула БайесаРешение нерешаемых систем уравнений2 Линейная регрессияКлассическая линейная регрессияМетод наименьших квадратовВероятностная постановка задачи3 Применение регрессионных методов для задачи классификациЛогистическая регрессияМетод IRLSОсобенности функции правдоподобияклассификацииОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS• Приравнивание градиента логарифма правдоподобия кнулю приводит к трансцендентным уравнениям,которые неразрешимы аналитически• Легко показать (Упр.), что гессиан логарифмаправдоподобия неположительно определен∂ 2 log p(t|x, w)≤0∂w2• Это означает, что логарифм функции правдоподобияявляется вогнутым.• Логарифм правдоподобия обучающей выборкиL(w) = log p(t|X, w), являющийся суммой вогнутыхфункций, также вогнут, а, значит, имеет единственныймаксимумМетод оптимизации НьютонаОбобщенныелинейные моделиВетровОсновная идея метода Ньютона — это приближение взаданной точке оптимизируемой функции параболой ивыбор минимума этой параболы в качестве следующейточки итерационного процесса:НапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLSf (x) → minwTf (x) ' g(x) = f (x0 ) + (∇f (x0 )) (x − x0 ) +1T(x − x0 ) (∇∇f (x0 ))(x − x0 )2∇g(x∗ ) = ∇f (x0 ) + (∇∇f (x0 ))(x∗ − x0 ) = 0 ⇒ x∗ = x0 − (∇∇f (x0 ))Пример.

Функция f (x) = log(1 + exp(x)) +x0 = 6, x1 = −2.4418.g(x)f(x)x1x0x25.−1(∇f (x0 ))Итеративная минимизация логарифмаправдоподобияОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLS• Так как прямая минимизация правдоподобияневозможна, воспользуемся итерационным методомНьютона• Обоснованием корректности использования методаНьютона является унимодальность оптимизируемойфункции L(w) и ее гладкость во всем пространствевесов• Формула пересчета в методе Ньютонаwnew = wold − H −1 ∇L(w),где H = ∇∇L(w) — гессиан логарифма правдоподобияобучающей выборкиФормулы пересчетаОбобщенныелинейные моделиВетровНапоминаниеЛинейнаярегрессияПрименениерегрессионныхметодов длязадачиклассификацииЛогистическаярегрессияМетод IRLSОбозначим si =11+exp(−ti yi ) ,тогда:∇L(w) = ΦT (s − t∗ ), ∇∇L(w) = ΦT RΦs1 (1 − s1 )0...00s2 (1 − s2 ) .

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

ОбщеепредставлениеВетровЛикбезГрафическиемоделиЛекция 2. Графические модели. ОбщеепредставлениеБайесовские сетиМарковские сетиЮ. И. Журавлев1 , Д. П. Ветров11МГУ, ВМиК, каф. ММПКурс «Математические основы теориипрогнозирования»ПланЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезГрафическиемоделиБайесовские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделейМарковские сети3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиПланЛекция 2.Графическиемодели. ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети1 ЛикбезФормула БайесаУсловная независимость случайных величин2 Графические моделиЗадачи со структурными ограничениямиОсновные проблемы в анализе графических моделей3 Байесовские сетиФакторизация байесовских сетейТри элементарных графаПример использования4 Марковские сетиПотенциалы и энергия кликПример использованияСвязь с байесовскими сетямиУсловная вероятностьЛекция 2.Графическиемодели.

ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Пусть X и Y — случайные величины с плотностями p(x)и p(y) соответственно• В общем случае их совместная плотностьp(x, y) 6= p(x)p(y). Если это равенство выполняется,величины называют независимыми• Условной плотностью называется величинаp(x, y)p(x|y) =p(y)• Смысл: как факт Y = y влияет на распределение X.RRЗаметим, что p(x|y)dx ≡ 1, но p(x|y)dy не обязан равнятьсяединице, т.к. относительно y это не плотность, а функцияправдоподобия• Очевидная система тождествp(x|y)p(y) = p(x, y) = p(y|x)p(x) позволяет легкопереходить от p(x|y) к p(y|x)p(x|y) =p(y|x)p(x)p(y)Правило суммирования вероятностейЛекция 2.Графическиемодели.

ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличин• Все операции над вероятностями базируются наприменении всего двух правил• Правило суммирования: Пусть A1 , . . . , Akвзаимоисключающие события, одно из которых всегдапроисходит. ТогдаkXP(Ai ∪ Aj ) = P(Ai ) + P(Aj )ГрафическиемоделиБайесовские сетиМарковские сетиP(Ai ) = 1i=1• Очевидное следствие (формула полной вероятности):∀B верноPki=1P(Ai |B) = 1, откудаkXP(B|Ai )P(Ai )i=1P(B)=1P(B) =P(B|Ai )P(Ai )i=1• В интегральной формеZp(b) =kXp(b, a)da =Zp(b|a)p(a)daПравило произведения вероятностейЛекция 2.Графическиемодели.

ОбщеепредставлениеВетровЛикбезФормула БайесаУсловнаянезависимостьслучайныхвеличинГрафическиемоделиБайесовские сетиМарковские сети• Правило произведения гласит, что любую совместнуюплотность всегда можно разбить на множителиp(a, b) = p(a|b)p(b)P(A, B) = P(A|B)P(B)• Аналогично для многомерных совместныхраспределенийp(a1 , . . . , an ) =p(a1 |a2 , . . . , an )p(a2 |a3 , . . . , an ) . . .

Характеристики

Список файлов лекций