Лекции. ММО. Сенько (all in one) (2015 Лекции (Сенько)), страница 2

. . dxn ,Mгде p(x) – плотность вероятности в точке x.Интегрирование ведётся по области M , принадлежащей пространствуRn вещественных векторов размерности n, из которой принимаютзначения X1 , . . . , Xn .Сенько Олег Валентинович ()ММО - основные понятия19 / 47Обобщающая способностьПри решении задач прогнозирования основной целью являетсядостижение максимальной обобщающей способности.Сенько Олег Валентинович ()ММО - основные понятия20 / 47Эффект переобученияРасширение модели M̃ = {A : X̃ → Ỹ }, увеличение её сложности,всегда приводит к повышению точности аппроксимации на обучающейвыборке. Однако повышение точности на обучающей выборке,связанное с увеличением сложности модели, часто не ведёт кувеличению обобщающей способности.

Более того, обобщающаяспособность может даже снижаться. Различие между точностью наобучающей выборке и обобщающей способностью при этомвозрастает. Данный эффект называется эффектом переобучения.Сенько Олег Валентинович ()ММО - основные понятия21 / 47Примеры эффекта переобученияЗадача восстановления регрессии по одному признаку.Восстановление кубической зависимости поПрименениевосстановленнойобучающим данным:зависимости к тестовым данным изтой же генеральной совокупности: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Применениектестовымпереобучение:3ММО - основные понятия−25−3−2−101сложнойданным−1023зависимостиобнаруживает12322 / 47Примеры эффекта переобученияЗадача классификации на два класса по двум признакам.Поиск простой разделяющей кривой по Применение разделяющей кривой кобучающим данным (ошибка 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Сенько Олег Валентинович ()123ММО - основные понятия−3−3−2−1012323 / 47Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?В случае, если при прогнозе 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}.Сенько Олег Валентинович ()ММО - основные понятия24 / 47Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?Здесь мы воспользовались простейшими свойствами условныхматематических ожиданий.

Для произвольных случайных функций ζ1и ζ2E[(ζ1 + ζ2 )|x] = E[ζ1 |x] + E[ζ2 |x].Для произвольной константы C и произвольной случайной функции ζE[Cζ|x] = CE[ζ|x].Также E[1|x] = 1.Сенько Олег Валентинович ()ММО - основные понятия25 / 47Для какого алгоритма прогнозирования достигаетсямаксимальная обобщающая способность?Однако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).Сенько Олег Валентинович ()ММО - основные понятия26 / 47Байесовский классификаторПокажем, что при справедливости предположения о том, что всюдоступную информацию о распределении объектов по классамсодержат переменные X1 , .

. . , Xn , байесовский классификаторобеспечивает наименьшую ошибку распознавания. Пусть используетсяклассификатор, относящий в некоторой точке x в классы K1 , . . . , KLдоли объектов ν1 (x), . . . , νL (x), соответственно. Из предположении осодержаннии всей информации о классах переменными X1 , .

. . , Xnследует, что внутри множества объектов с фиксированным xистинный номер класса не зависит от вычисленного прогноза. Откудаследует, что вероятность отнесения в класс Ki объекта, которыйклассу Ki в действительности принадлежит составляет nu(x)P (Ki |x).Вероятность ошибочного отнесения в классы отличные от Ki объекта,в действительности принадлежа- щего Ki , составляет[1 − nu(x)]P (Ki |x).Сенько Олег Валентинович ()ММО - основные понятия27 / 47Байесовский классификаторОбщая вероятность ошибочных классификаций в точке x составляетLX[1 − νi (x)]P (Ki |x) = 1 −i=1LXν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.Сенько Олег Валентинович ()ММО - основные понятия28 / 47Байесовский классификаторОдна из вершин симплекса, задаваемого ограничениями задачилинейного программирования, является её решением. Данное решениепредставляет собой бинарный вектор размерности L, имеющий вид (0,. . . , 1, . . .

, 0). При этом значение 1 находится в позиции i0 , длякоторой выполняется набор неравенств P (Ki0 |x) ≥ P (Ki |x),i = 1, . . . , L. В случае, если максимальная условная вероятностьдостигается только для одного класса Ki0 , решение задачи линейногопрограммирования достигается в единственной точке, задаваемойбинарным вектором с единственной 1, находящейся в позиции i0 .Сенько Олег Валентинович ()ММО - основные понятия29 / 47Байесовский классификаторПредположим, что максимальная условная вероятность достигаетсядля нескольких классов Kj(1) , . . .

, Kj(l0 ) . Тогда решением задачиявляется вектор ν1 , . . . , νL , компоненты которого удовлетворяютусловиям:νi = 0, i 6= j(r), r = 1, . . . , l0 .Из этого следует, что любая стратегия, при которой объектыотносятся в один из классов Kj(1) , . . . , Kj(l0 ) , является оптимальной.Сенько Олег Валентинович ()ММО - основные понятия30 / 47Поиск оптимальных алгоритмов прогнозирования ираспознаванияОднако для вычисления условных математических ожиданий E(Y |x)или условных вероятностей P (Ki |x), i = 1, . .

. , L, необходимы знанияконкретного вида вероятностных распределений, присущих решаемойзадаче. Такие знания в принципе могут быть получены сиспользованием известного метода максимального правдоподобия.Сенько Олег Валентинович ()ММО - основные понятия31 / 47Метод максимального правдоподобияМетод максимального правдоподобия (ММП) используется вматематической статистике для аппроксимации вероятностныхраспределений по выборкам данных. В общем случае ММП требуетаприорных предположений о типе распределений. Значенияпараметров (θ1 , .

. . , θr ), задающих конкретный вид распределений,ищутся путём максимизации функционала правдоподобия.Функционал правдоподобия представляет собой произведениеплотностей вероятностей на объектах обучающей выборки.Сенько Олег Валентинович ()ММО - основные понятия32 / 47Метод максимального правдоподобияФункционал правдоподобия имеет видL(S̃t , θ1 , . . . , θr ) =mYp(yj , xj , θ1 , . .

. , θr ).j=1Наряду с методом минимизации эмпирического риска метод ММПявляется одним из важнейших инструментов настройки алгоритмовраспознавания или регрессионных моделей. Следует отметить теснуюсвязь между обоими подходами.Сенько Олег Валентинович ()ММО - основные понятия33 / 47Метод максимального правдоподобияПримерПусть X1 , X2 , . . . , Xm – независимые одинаково распределённыеслучайные величины (н.о.р.с.в), причём(xi − θ)212exp −Xi ∼ N (xi |θ, σ ) = √.2σ 22πσТребуется с помощью метода максимального правдоподобия оценитьзначение θ.Сенько Олег Валентинович ()ММО - основные понятия34 / 47Метод максимального правдоподобияПримерПусть X1 , X2 , .

. . , Xm – независимые одинаково распределённыеслучайные величины (н.о.р.с.в), причём(xi − θ)212exp −Xi ∼ N (xi |θ, σ ) = √.2σ 22πσТребуется с помощью метода максимального правдоподобия оценитьзначение θ.Запишем совместное распределение величин X1 , . . . , Xm :p(x|θ, σ 2 ) = p(x1 , x2 , .

. . , xm |θ, σ 2 ) = {Нез-ть} =mmYY=p(xi |θ, σ 2 ) =N (xj |θ, σ 2 ).j=1Сенько Олег Валентинович ()ММО - основные понятияj=134 / 47Продолжение примера 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Сенько Олег Валентинович ()ММО - основные понятия35 / 47Продолжение примера 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 .Сенько Олег Валентинович ()ММО - основные понятия36 / 47Поиск оптимальных алгоритмов прогнозирования ираспознаванияДля подавляющего числа приложений ни общий вид распределений,ни значения конкретных их параметров неизвестны.

В связи с этимвозникло большое число разнообразных подходов к решению задачпрогнозирования, использование которых позволяло добиватьсяопределённых успехов при решении конкретных задач.Сенько Олег Валентинович ()ММО - основные понятия37 / 47Методы прогнозированияСтатистические методыЛинейные модели регрессионного анализаРазличные методы, основанные на линейной разделимостиМетоды, основанные на ядерных оценкахНейросетевые методыКомбинаторно-логические методы и алгоритмы вычисленияоценокАлгебраические методыРешающие или регрессионные деревья и лесаМетоды, основанные на опорных векторахСенько Олег Валентинович ()ММО - основные понятия38 / 47Эмпирические методы оценки обобщающей способностиОбобщающая способность может оцениваться по случайной выборкеобъектов из одной и той же генеральной совокупности,соответствующей исследуемому процессу, которую принято называтьконтрольной выборкой.