Лекция 1. Задачи прогнозирования_ обобщающая способность_ скользящий контроль (1185278), страница 2
Текст из файла (страница 2)
. . dxn ,Mгде p(x) – плотность вероятности в точке x.Интегрирование ведётся по области M , принадлежащей пространствуRn вещественных векторов размерности n, из которой принимаютзначения X1 , . . . , Xn .Сенько Олег Валентинович ()МОТП, лекция 121 / 50Обобщающая способностьПри решении задач прогнозирования основной целью являетсядостижение максимальной обобщающей способности.Сенько Олег Валентинович ()МОТП, лекция 122 / 50Эффект переобученияРасширение модели M̃ = {A : X̃ → Ỹ }, увеличение её сложности,всегда приводит к повышению точности аппроксимации на обучающейвыборке.
Однако повышение точности на обучающей выборке,связанное с увеличением сложности модели, часто не ведёт кувеличению обобщающей способности. Более того, обобщающаяспособность может даже снижаться. Различие между точностью наобучающей выборке и обобщающей способностью при этомвозрастает. Данный эффект называется эффектом переобучения.Сенько Олег Валентинович ()МОТП, лекция 123 / 50Примеры эффекта переобученияЗадача восстановления регрессии по одному признаку.Восстановление кубической зависимости поПрименениевосстановленнойобучающим данным:зависимости к тестовым данным изтой же генеральной совокупности:050−5−5−10−10−15−15−20−20−25−30−3−25−2−1012−30−33Увеличение сложности восстанавливаемойзависимости (степень полинома = 20)приводит к повышению точности наобучающих данных:−5−5−10−10−15−15−20−20−25−3−2−10Сенько Олег Валентинович ()12−2Применениектестовымпереобучение:−25−33МОТП, лекция 1−2−101сложнойданным−1023зависимостиобнаруживает12324 / 50Примеры эффекта переобученияЗадача классификации на два класса по двум признакам.Поиск простой разделяющей кривой по Применение разделяющей кривой кобучающим данным (ошибка 5%):тестовым данным из той же генеральнойсовокупности (ошибка 6%):33221100−1−1−2−2−3−3−2−1012−3−33Увеличение сложности разделяющей кривойприводит к 100-процентной точности наобучающих данных:33221100−1−1−2−3−3−2−10123Применениесложнойразделяющейкривой к тестовым данным обнаруживаетпереобучение (ошибка 14%):−2−2−10Сенько Олег Валентинович ()12−3−33МОТП, лекция 1−2−1012325 / 50Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?В случае, если при прогнозе Y в точке x используется величина A(x),а величиной потерь является квадрат ошибки (т.е.λ[yj , A(xj )] = (yj − A(xj ))2 ), справедливо разложение:E{λ[Y, A(x)]|x} = E{[Y − A(x)]2 |x} =E{[Y − E(Y |x) + E(Y |x) − A(x)]2 |x} =E{[Y − E(Y |x)]2 |x} + E{[A(x) − E(Y |x)]2 |x}+2[A − E(Y |x)]E{[Y − E(Y |x)]|x}.Сенько Олег Валентинович ()МОТП, лекция 126 / 50Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?Далее мы воспользуемся простейшими свойствами условныхматематических ожиданий.
Для произвольных случайных функций ζ1и ζ2E[(ζ1 + ζ2 )|x] = E[ζ1 |x] + E[ζ2 |x].Для произвольной константы C и произвольной случайной функции ζE[Cζ|x] = CE[ζ|x].Также E[1|x] = 1.Сенько Олег Валентинович ()МОТП, лекция 127 / 50Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?Однако2[E(Y |x) − A(x)]E{[Y − E(Y |x)]|x} = 0.Отсюда следует, чтоE{[Y − A(x)]2 |x} = [E(Y |x) − A(x)]2 + E{[Y − E(Y |x)]2 |x}.Из этой формулы хорошо видно, что наилучший прогноз долженобеспечивать алгоритм, вычисляющий прогноз как A(x) = E(Y |x).Сенько Олег Валентинович ()МОТП, лекция 128 / 50Классификатор с максимальной обобщающей способностьюПусть в точке x ∈ Rn объекты из классов K1 , .
. . , KL встречаются свероятностями P(K1 |x), . . . , P (KL |x). Тогда распознаваемый объектсо значением вектора прогностических переменных x должен бытьотнесён в класс Ki0 , для которого выполнены все неравенстваP (Ki0 |x) ≥ P(Ki |x), i ∈ {1, .
. . , L}.Иными словами распознаваемый объект должен быть отнесён кодному из классов, вероятность принадлежности которому в точке xмаксимальна . В случае, если максимальная условная вероятностьдостигается только для одного из классов K1 , . . . , KL , распознаваемыйобъект должен быть однозначно отнесён только к этому классу.Такое решающее правило получило название байесовскогоклассификатора.Сенько Олег Валентинович ()МОТП, лекция 129 / 50Байесовский классификаторПокажем, что при справедливости предположения о том, что всюдоступную информацию о распределении объектов по классамсодержат переменные X1 , .
. . , Xn , байесовский классификаторобеспечивает наименьшую ошибку распознавания. Пусть используетсяклассификатор, относящий в некоторой точке x в классы K1 , . . . , KLдоли объектов ν1 (x), . . . , νL (x), соответственно. Из предположении осодержании всей информации о классах переменными X1 , . . . , Xnследует, что внутри множества объектов с фиксированным xистинный номер класса не зависит от вычисленного прогноза. Откудаследует, что вероятность отнесения в класс Ki объекта, которыйклассу Ki в действительности принадлежит составляет νi (x)P (Ki |x).Вероятность ошибочного отнесения в классы отличные от Ki объекта,в действительности принадлежа- щего Ki , составляет[1 − νi (x)]P (Ki |x).Сенько Олег Валентинович ()МОТП, лекция 130 / 50Байесовский классификаторОбщая вероятность ошибочных классификаций в точке x составляетLXLX[1 − νi (x)]P (Ki |x) = 1 −i=1νi (x)P (Ki |x).i=1Задача поиска минимума ошибки сводится к задаче линейногопрограммирования видаLXi=1LXνi P (Ki |x) → max ,ν1 ,...,νLνi = 1,i=1νi ≥ 0, i = 1, .
. . , L.Сенько Олег Валентинович ()МОТП, лекция 131 / 50Байесовский классификаторОдна из вершин симплекса, задаваемого ограничениями задачилинейного программирования, является её решением. Данное решениепредставляет собой бинарный вектор размерности L, имеющий вид (0,. . . , 1, . . . , 0). При этом значение 1 находится в позиции i0 , длякоторой выполняется набор неравенств P (Ki0 |x) ≥ P (Ki |x),i = 1, .
. . , L. В случае, если максимальная условная вероятностьдостигается только для одного класса Ki0 , решение задачи линейногопрограммирования достигается в единственной точке, задаваемойбинарным вектором с единственной 1, находящейся в позиции i0 .Сенько Олег Валентинович ()МОТП, лекция 132 / 50Байесовский классификаторПредположим, что максимальная условная вероятность достигаетсядля нескольких классов Kj(1) , .
. . , Kj(l0 ) . Тогда решением задачиявляется вектор ν1 , . . . , νL , компоненты которого удовлетворяютусловиям:νi = 0, i 6= j(r), r = 1, . . . , l0 .Из этого следует, что любая стратегия, при которой объектыотносятся в один из классов Kj(1) , . . . , Kj(l0 ) , является оптимальной.Сенько Олег Валентинович ()МОТП, лекция 133 / 50Поиск оптимальных алгоритмов прогнозирования ираспознаванияОднако для вычисления условных математических ожиданий E(Y |x)или условных вероятностей P (Ki |x), i = 1, .
. . , L, необходимы знанияконкретного вида вероятностных распределений, присущих решаемойзадаче. Такие знания в принципе могут быть получены сиспользованием известного метода максимального правдоподобия.Сенько Олег Валентинович ()МОТП, лекция 134 / 50Метод максимального правдоподобияМетод максимального правдоподобия (ММП) используется вматематической статистике для аппроксимации вероятностныхраспределений по выборкам данных. В общем случае ММП требуетаприорных предположений о типе распределений.
Значенияпараметров (θ1 , . . . , θr ), задающих конкретный вид распределений,ищутся путём максимизации функционала правдоподобия.Функционал правдоподобия представляет собой произведениеплотностей вероятностей на объектах обучающей выборки.Сенько Олег Валентинович ()МОТП, лекция 135 / 50Метод максимального правдоподобияФункционал правдоподобия имеет видL(S̃t , θ1 , .
. . , θr ) =mYp(yj , xj , θ1 , . . . , θr ).j=1Наряду с методом минимизации эмпирического риска метод ММПявляется одним из важнейших инструментов настройки алгоритмовраспознавания или регрессионных моделей. Следует отметить теснуюсвязь между обоими подходами.Сенько Олег Валентинович ()МОТП, лекция 136 / 50Метод максимального правдоподобияПримерПусть x1 , x2 , . . . , xm – независимые одинаково распределённыеслучайные величины (н.о.р.с.в), причём1(xi − θ)22xi ∼ N (xi |θ, σ ) = √exp −.2σ 22πσТребуется с помощью метода максимального правдоподобия оценитьзначение θ.Сенько Олег Валентинович ()МОТП, лекция 137 / 50Метод максимального правдоподобияПримерПусть x1 , x2 , .
. . , xm – независимые одинаково распределённыеслучайные величины (н.о.р.с.в), причём1(xi − θ)22xi ∼ N (xi |θ, σ ) = √exp −.2σ 22πσТребуется с помощью метода максимального правдоподобия оценитьзначение θ.Принимая во внимание условие независимости наблюдений запишемсовместное распределение величин x1 , . .
. , xm :p(x|θ, σ 2 ) = p(x1 , x2 , . . . , xm |θ, σ 2 ) =mmYY=p(xi |θ, σ 2 ) =N (xj |θ, σ 2 ).j=1Сенько Олег Валентинович ()МОТП, лекция 1j=137 / 50Продолжение примера IФункция p(x|θ, σ 2 ):какот x – условная плотность, в частности,R функция2p(x|θ, σ )dx = 1;как функция от θ, σ 2 – функция правдоподобия.Оценка θ с помощью максимизации правдоподобия соответствуетзадаче оптимизации:L(θ, σ 2 ) = p(x|θ, σ 2 ) → max .θПри работе с функционалами в форме произведений удобнопереходить к логарифму:θM L = arg max L(θ, σ 2 ) = arg max log L(θ, σ 2 ) =θθmm1 X2= arg max − 2(xj − θ) − log 2π − m log σθ2σ| 2{z}j=1constСенько Олег Валентинович ()МОТП, лекция 138 / 50Продолжение примера IIДифференцируя log L(θ, σ 2 ) по θ и приравнивая производную к нулю,получаем:mX1∂log L(θ, σ 2 ) = − 2 2mθ − 2xj = 0.∂θ2σj=1ОтсюдаmθM L =1 Xxj .mj=1Заметим, что оценка θM L не зависит от дисперсии σ 2 .Сенько Олег Валентинович ()МОТП, лекция 139 / 50Поиск оптимальных алгоритмов прогнозирования ираспознаванияДля подавляющего числа приложений ни общий вид распределений,ни значения конкретных их параметров неизвестны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
