_пособие_ Ветров Д.П._ Кропотов Д.А. Байесовские методы машинного обучения_ учебное пособие (2007) (1185333), страница 5
Текст из файла (страница 5)
Вероятностная постановка задачи распознавания образов22Рис. 2.4. Пример парзеновского оцениванияИдея метода• Как было получено ранее, значение плотности может быть приближено величинойp̂(x) =k,nVгде V – объем области D, содержащей точку x• Потребуем, чтобы D являлась сферой минимального радиуса с центром в точке x, содержащей ровноk точек обучающей выборкиX Упр.• Можно показать , что для сходимости p̂(x) к p(x) при n → ∞ необходимыми условиями являютсятребованияklim k = ∞lim=0n→∞n→∞ n• В случае нарушения первого требования оценка плотности будет почти всюду ноль, а при нарушениивторого – почти всюду бесконечность, т.к.
V → 0 при неограниченном возрастании nОсобенности использования методов ближайших соседей• !! Количество ближайших соседей k является структурным параметром!!√• В большинстве приложений выбор k ∼ n является адекватным• Серьезным недостатком метода является тот факт, что получающаяся оценка p̂(x) не является плотностью, т.к. интеграл от нее, вообще говоря, расходится• Так в одномерном случае функция p̂(x) имеет хвост порядка1x• С ростом размерности пространства и объема выборки этот недостаток становится менее критическимГлава 2.
Вероятностная постановка задачи распознавания образов23Рис. 2.5. Пример восстановления плотности с помощью метода ближайщего соседа с различным значением K2.42.4.1EM-алгоритмПараметрическое восстановление плотностейПараметрический подход• При параметрическом восстановлении плотностей предполагается, что искомая плотность нам известна с точностью до параметра p(x|θ)• Оценка плотности происходит путем оптимизации по θ некоторого функционала• Обычно в качестве последнего используется правдоподобие или его логарифмp(X|θ) =nYp(xi |θ) → maxθi=1• В курсе математической статистики доказывается, что оценки максимального правдоподобия являются состоятельными, ассимптотически несмещенными и эффективными (т.е. имеют наименьшуювозможную дисперсию)Пример использования• Пусть имееется выборка из нормального распределения N (x|µ, σ 2 ) с неизвестными мат. ожиданиеми дисперсией• Выписываем логарифм функции правдоподобияL(X|µ, σ) = −nX(xi − µ)2i=1nX(xi − µ)∂L=−∂µi=1n2σ 22σ 2− n log σ −nlog(2π) → maxµ,σ2n= 0 ⇒ µM L =1Xxin i=1nn1X∂L X (xi − µ)22=−=0⇒σ=(xi − µ)2ML3∂σσσni=1i=1Глава 2.
Вероятностная постановка задачи распознавания образов2.4.224Задача разделения смеси распределенийБолее сложная ситуация• Часто возникают задачи, в которых генеральная совокупность является смесью нескольких элементарных распределенийPlPl• Дискретная смесь: X ∼ j=1 wj p(x|θj ), j=1 wj = 1, wj ≥ 0RR• Непрерывная смесь: X ∼ w(ξ)p(x|θ(ξ))dξ, w(ξ)dξ = 1, w(ξ) ≥ 0• Даже в случае, когда коэффициенты смеси известны, оптимизация правдоподобия крайне затруднительна• Существует специальный алгоритм, позволяющий итеративно проводить оценивание коэффициентов смеси и параметров каждого из распределенийОсобенности функционала качества• Основная трудность при применении стандартного метода максимального правдоподобия заключается в необходимости оптимизации по θ величиныnlXXL(X|θ) =log wj p(xi |θ j )i=1j=1• Этот функционал имеет вид «логарифм суммы» и крайне сложен для оптимизации• Необходимо перейти к функционалу вида «сумма логарифмов», который легко оптимизируется вявном видеСуть ЕМ-алгоритма• Если бы мы знали, какой объект из какой компоненты смеси взят, т.е.
функцию j(i) (будем считать,что соответствующая информация содержится в ненаблюдаемой переменной z), то правдоподобиевыглядело бы куда прощеnXL(X, Z|θ) =log wj(i) p(xi |θ j(i) )i=1• Идея ЕМ-алгоритма заключается в введении латентных, т.е. ненаблюдаемых переменных Z, позволяющих упростить вычисление правдоподобия• Оптимизация проводится итерационно методом покоординатного спуска: на каждой итерации последовательно уточняются возможные значения Z (Е-шаг), а потом пересчитываются значения θ(М-шаг)Схема ЕМ-алгоритма• На входе: выборка X, зависящая от набора параметров θ, w• Инициализируем θ, w некоторыми начальными приближениями• Е-шаг: Оцениваем распределение скрытой компонентыp(X, Z|θ, w)p(Z|X, θ, w) = PZ p(X, Z|θ, w)Глава 2.
Вероятностная постановка задачи распознавания образов25Рис. 2.6. Выборка из смеси трех нормальных распределений• М-шаг: ОптимизируемEZ log p(X, Z|θ, w) =Xp(Z|X, θ, w) log p(X, Z|θ, w) → maxθ,wZЕсли бы мы точно знали значение Z = Z0 , то вместо мат. ожидания по всевозможным (с учетом наблюдаемыхданных) Z, мы бы оптимизировали log p(X, Z0 |θ, w)• Переход к Е-шагу, пока процесс не сойдется2.4.3Разделение гауссовской смесиСмесь гауссовских распределенийPl• Имеется выборка X ∼ j=1 wj N (x|µj , Σj )) ∈ Rd (см.
рис. 2.6)• Требуется восстановить плотность генеральной совокупностиЕМ-алгоритм• Выбираем начальное приближение µj , wj , Σj• Е-шаг: Вычисляем распределение скрытых переменных z i ∈ {0, 1},к какой компоненте смеси принадлежит объект xiγ(zij ) = PlPjzij = 1, которые определяют,wj N (xi |µj , Σj ))k=1wk N (xi |µk , Σk ))• М-шаг: С учетом новых вероятностей на zi , пересчитываем параметры смесиµnew=jΣnew=jn1 Xγ(zij )xi ,Nj i=1wjnew =Nj,nNj =n1 Xγ(zij )(xi − µnew)T (xi − µnew)jjNj i=1• Переход к Е-шагу, пока не будет достигнута сходимостьnXi=1γ(zij )Глава 2. Вероятностная постановка задачи распознавания образов26Недостатки ЕМ-алгоритма• В зависимости от выбора начального приближения может сходиться к разным точкам• ЕМ-алгоритм находит локальный экстремум, в котором значение правдоподобия может оказатьсянамного ниже, чем в глобальном максимуме• ЕМ-алгоритм не позволяет определить количество компонентов смеси l• !! Величина l является структурным параметром!!Глава 3Обобщенные линейные моделиДанная глава посвящена описанию простейших методов решения задачи восстановления регрессии и классификации.
Изложение ведется в контексте т.н. обобщенных линейных моделей. Дается подробное описание метода построения линейной регрессии. Особое внимание уделено вопросам регуляризации задачи.Приводится описание метода наименьших квадратов с итеративным перевзвешиванием, используемогодля обучения логистической регрессии27Глава 3.
Обобщенные линейные модели3.128Ликбез: Псевдообращение матриц и нормальное псевдорешениеПсевдообращение матриц• Предположим, нам необходимо решить СЛАУ вида Ax = b• Если бы матрица A была квадратной и невырожденной (число уравнений равно числу неизвестныхи все уравнения линейно независимы), то решение задавалось бы формулой x = A−1 b• Предположим, что число уравнений больше числа неизвестных, т.е.
матрица A прямоугольная. Домножим обе части уравнения на AT слеваAT Ax = AT b• В левой части теперь квадратная матрица и ее можно перенести в правую часть¡¢−1 Tx = AT AA b¡¢−1 T• Операция AT AA называется псевдообращением матрицы A, а x – псевдорешениемНормальное псевдорешение• Если матрица AT A вырождена, псевдорешений бесконечно много, причем найти их на компьютеренетривиально• Для решения этой проблемы используется ридж-регуляризация матрицы AT AAT A + λI,где I – единичная матрица, а λ – коэффициент регуляризации.
Такая матрица невырождена длялюбых λ > 0• Величина¡¢−1 Tx = AT A + λIA bназывается нормальным псевдорешением. Оно всегда единственно и при небольших положительныхλ определяет псевдорешение с наименьшей нормойГрафическая иллюстрация• Псевдорешение соответствует точке, минимизирующей невязку, а нормальное псевдорешение отвечает псевдорешению с наименьшей нормой (см.
рис. 3.1)¡¢−1 T• Заметим, что псевдообратная матрица AT AA совпадает с обратной матрицей A−1 в случаеневырожденных квадратных матрицГлава 3. Обобщенные линейные модели29(0.0175,0.0702)5x1.=12+1-x+xx1=21-2x2=1(a)(b)Рис. 3.1. На рисунке (a) показан пример единственного псевдорешения (которое одновременно является и нормальнымпсевдорешением), на рисунке (b) пунктирная линия обозначает множество всех псевдорешений, а нормальное псевдорешениеявляется основанием перпендикуляра, опущенного из начала координат3.23.2.1Линейная регрессияКлассическая линейная регрессияЗадача восстановления регрессии• Задача восстановления регрессии предполагает наличие связи между наблюдаемыми признаками xи непрерывной переменной t• В отличие от задачи интерполяции допускаются отклонения решающего правила от правильныхответов на объектах обучающей выборки• Уравнение регрессии y(x, w) ищется в некотором параметрическом виде путем нахождения наилучшего значения вектора весовw∗ = arg max F (X, t, w)wЛинейная регрессия• Наиболее простой и изученной является линейная регрессия• Главная особенность: настраиваемые параметры входят в решающее правило линейно• Заметим, что линейная регрессия не обязана быть линейной по признакам• Общее уравнение регрессии имеет видy(x, w) =mXwj φj (x) = wT φ(x)j=1Особенность выбора базисных функций• Общего метода выбора базисных функций φj (x) — не существует• Обычно они подбираются из априорных соображений (например, если мы пытаемся восстановитькакой-то периодический сигнал, разумно взять функции тригонометрического ряда) или путем использования некоторых «универсальных» базисных функций• Наиболее распространенными базисными функциями являются– φ(x) = xkГлава 3.
Обобщенные линейные модели30– φ(x) = xk1 xk2 . . . xkl– φ(x) = exp(−γkx − x0 kp ), γ, p > 0.• Метод построения линейной регрессии (настройки весов w) не зависит от выбора базисных функцийФормализация задачи• Пусть S(t, t̂) — функция потерь от ошибки в определении регрессионной переменной t• Необходимо минимизировать потери от ошибок на генеральной совокупностиZ ZES(t, y(x, w)) =S(t, y(x, w))p(x, t)dxdt → minw• Дальнейшие рассуждения зависят от вида функции потерь• Во многих случаях даже не нужно восстанавливать полностью условное распределение p(t|x)Важная теорема• Теорема. Пусть функция потерь имеет вид– S(t, t̂) = (t − t̂)2 — «Потери старушки»;– S(t, t̂) = |t − t̂| — «Потери олигарха»;– S(t, t̂) = δ −1 (t − t̂) — «Потери инвалида».Тогда величиной, минимизирующей функцию ES(t, y(x, w)), является следующая– y(x) = Ep(t|x);– y(x) = med p(t|x);– y(x) = mod p(t|x) = arg maxt p(t|x).• В зависимости от выбранной системы предпочтений, мы будем пытаться оценивать тот или инойфункционал от апостериорного распределения вместо того, чтобы оценивать его самого3.2.2Метод наименьших квадратовМинимизация невязки• Наиболее часто используемой функцией потерь является квадратичная S(t, t̂) = (t − t̂)2• Значение регрессионной функции на обучающей выборке в матричном виде может быть записанокак y = Φw, где Φ = (φij ) = (φj (xi )) ∈ Rn×m• Таким образом, приходим к следующей задачеky − tk2 = kΦw − tk2 → minwВзяв производную по w и приравняв ее к нулю, получаем∂kΦw − tk2∂[wT ΦT Φw − 2wT ΦT t + tT t]== 2ΦT Φw − 2ΦT t = 0∂w∂ww = (ΦT Φ)−1 ΦT tГлава 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
