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

. , βn ) дополнительнойштрафной компоненты. Введение такой компоненты позволяетполучить решение, на котором Q(S̃t , β0 , β1 , . . . , βn ) достаточно близокк своему глобальному минимуму. Однако данное решение оказываетсязначительно более устойчивым и благодаря устойчивости позволяетдостигать существенно более высокой обобщающей способности.Подход к получению более эффективных решений с помощьювключения штрафного слагаемого в оптимизируемый функционалпринято называть регуляризацией по Тихонову.Сенько Олег Валентинович ()ММО - Регрессия31 / 13Методы регуляризацииНа первом этапе переходим от исходных переменных {X1 , .

. . , Xn } кстандартизированным {X1s , . . . , Xns } , где Xis = Xiσ̂−iX̂i ,√ ∑m1 ∑m12X̂i = m j=1 xji , σ̂i = mj=1 (X̂i − xji ), а также от исходнойпрогнозируемой переменнойY к стандартизованной прогнозируемой1 ∑msпеременной Y = Y − m j=1 yj . Пусть x̆sj1 = 1 , x̆sji = xsj(i−1) приi > 1 , где xsj(i−1) - значение признака Xis для j-го объекта.

Пусть1 xs11 . . . xs1n. . . . . . . . . . . . ssтакже Xs = 1 xj1 . . . xjn . - матрица плана для. . . . . . . . . . . . 1 xsm1 . . . xsmns ) - вектор значенийстандартизированных переменных, y s = (y1s , . . . , ymстандартизованной переменной Ys .Сенько Олег Валентинович ()ММО - Регрессия32 / 13Методы регуляризацииОдним из первых методов регрессии, использующих принципрегуляризации, является метод гребневой регрессии (ridge regression).В гребневой регрессии в оптимизируемый функционал дополнительновключается сумма квадратов регрессионных коэффициентов припеременных {X1s , .

. . , Xns } . В результате функционал имеет видQridge (S̃t , β0 , . . . , βn ) =∑∑1 ∑[yj − β0 −βi x̆sji ]2 + γβi2 ,mmnnj=1i=1i=1(24)где γ - положительный вещественный параметр. Пусть β r являетсявектором оценок регрессионных коэффициентов, полученным врезультате минимизации Qridge (S̃t , β0 , . .

. , βn ).Сенько Олег Валентинович ()ММО - Регрессия33 / 13Методы регуляризацииОтметим, что увеличение регрессионных коэффициентов приводит кувеличению Qridge (S̃t , β0 , . . . , βn ) . Таким образом использованиегребневой регрессии приводит к снижению длины векторарегрессионных коэффициентов при переменных {X1s , . . . , Xns } .Рассмотрим конкретный вид вектора регрессионных коэффициентовβ r в гребневой регрессии. Необходимым условием минимумафункционала Qridge (S̃t , β0 , .

. . , βn ) является выполнение системы изn + 1 уравнений:Сенько Олег Валентинович ()ММО - Регрессия34 / 13Методы регуляризацииmm n+1∑∑∂Qridge (S̃t , β0 , . . . , βn )2 ∑yj x̆sj1 −βi x̆sji x̆sj1 ] + 2γβ0 = 0=− [∂β0mj=1j=1 i=1(25).........................................................mm n+1∑∑∂Qridge (S̃t , β0 , . . . , βn )2 ∑=− [yj x̆sjn −βi x̆sji x̆sjm ] + 2γβn = 0∂βnmj=1j=1 i=1Поэтому вектор оценок регрессионных коэффициентов в методегребневая регрессия является решением системы (25).Сенько Олег Валентинович ()ММО - Регрессия35 / 13Методы регуляризацииВ матричной форме система (25) может быть записана в виде−2Xts y ts + (2Xts Xs + 2γI)β tr = 0(26)β tr = Xts y ts (Xts Xs + γI)−1(27)или в видегде I - единичная матрица.

Отметим, что произведение Xts Xsпредставляет собой симметрическую неотрицательно определённуюматрицу. Матрица Xts Xs + γI также является симметрическойматрицей. Каждому собственному значению λk матрицы Xts Xsсоответствует собственное значение λk + γ матрицы Xts Xs + γI . Пустьλγmin минимальное собственное значение матрицы Xts Xs + γIудовлетворяет неравенству λγmin > γ . Откуда следует, что всегдаdet(Xts Xs + γI) > 0 , а обратная матрица (Xts Xs + γI)−1 всегдасуществует.

Достаточно большая величина det(Xts Xs + γI) приводит котносительно небольшим изменениям оценок регрессионныхкоэффициентов при небольших изменениях в обучающих выборках.Сенько Олег Валентинович ()ММО - Регрессия36 / 13Методы регуляризацииНаряду с гребневой регрессией в последние годы получилраспространение метод Лассо, основанный на минимизациифункционалаmnn∑∑∑Qlasso (S̃t , β0 , . . .

, βn ) =[yj − β0 −βi x̆sji ]2 + γ| βi |.j=1i=1(28)i=1Интересной особенностью метода Лассо является равенство 0 части изрегрессионных коэффициентов . Однако равенство 0 коэффициента насамом деле означает исключение из модели соответствующей емупеременной. Поэтому метод Лассо не только строит оптимальнуюрегрессионную модель, но и производит отбор переменных.

Методможет быть использован для отбора переменных в условиях, когдаразмерность данных превышает размер выборки. Отметим, что общеечисло отобранных переменных не может превышать размераобучающей выборки . Эксперименты показали, что эффективностьотбора переменных методом Лассо снижается, при высокой взаимнойкорреляции некоторых из них.Сенько Олег Валентинович ()ММО - Регрессия37 / 13Методы регуляризацииДанными недостатками не обладает другой метод построениярегрессионной модели, основанный на регуляризации по Тихонову,который называется эластичная сеть. Метод эластичная сеть основанна минимизации функционалаQelnet (S̃t , β0 , . . . , βn ) =m∑j=1nn∑∑[yj −β0 −βi x̆sji ]2 +γ[βi2 θ + (1 − θ) | βi |],i=1i=1(29)где θ ∈ [0, 1] . Метод эластичная сеть включает в себя метод гребневаярегрессия и Лассо как частные случаи.Сенько Олег Валентинович ()ММО - Регрессия38 / 13Лекция 4Задачи прогнозирования,Линейная машина, Теоретические методы оценкиобобщающей способности,Лектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 41 / 35Содержание лекции1Методы, основанные на формуле Байеса2Линейный дискриминант Фишера3Логистическая регрессия4K ближайших соседей5Распознавание при заданной точности распознаваниянекоторых классовСенько Олег Валентинович ()МОТП, лекция 42 / 35Использование формулы БайесаРанее было показано, что максимальную точность распознаванияобеспечивает байесовское решающее правило, относящеераспознаваемый объект, описываемый вектором x переменных(признаков) X1 , .

. . , Xn к классу K∗ , для которого условнаявероятность P (K∗ | x) максимальна. Байесовские методы обученияоснованы на аппроксимации условных вероятностей классов в точкахпризнакового пространства с использованием формулы Байеса.Рассмотрим задачу распознавания классов K1 , . . . , KL . ФормулаБайеса позволяет рассчитать Условные вероятности классов в точкепризнакового пространства могут бфыть рассчитаны с использованиемформулы Байеса.

В случае, если переменные X1 , . . . , Xn являютсядискретными формула Байеса может быть записана в виде:P (x | Ki )P (Ki )P (Ki | x) = PLi=1 P (Ki )P (x | Ki )(1)где P (K1 ), . . . , P (KL ) - вероятность классов K1 , . . . , KLбезотносительно к признаковым описаниям (априорная вероятность).Сенько Олег Валентинович ()МОТП, лекция 43 / 35Использование формулы БайесаВ качестве оценок априорных вероятностейP (K1 ), . . . , P (KL )могут быть взяты доли объектов соответствующих классов вобучающей выборке.

Условные вероятности P (x | K1 ), . . . , P (x | KL )могут оцениваться на основании сделанных предположений. Например,может быть использовано предположение о независимости переменныхдля каждого из классов. В последнем случае вероятность P (xj | Ki )для вектора xk = (xj1 , . . . , xjn ) может быть представлена в виде:P (xj | Ki ) =nYP (Xj = xki | Ki ).(2)i=1Предположим, переменная Xj принимает значения из конечногоfi на объектах из класса Ki при j = 1, .

. . , n имножества Mji = 1, . . . , L. Предположим, чтоfji = {a1ji , . . . , ar(i,j). }MjiСенько Олег Валентинович ()МОТП, лекция 44 / 35Наивный байесовский классификаторДля того, чтобы воспользоваться формулой (2) достаточно знатьвероятность выполнения равенства Xj = akji для произвольного классаи произвольной переменной. Для оценки вероятности P (Xj = akji |Ki )Tможет использоваться доля объектов из Set Ki , для которыхXj = akji . В случае, если переменные X1 , . . .

, Xn являютсянепрерывными, формула Байеса может быть записана сиспользованиемpi (x)P (Ki )P (Ki | x) = PL,i=1 P (Ki )pi (x)(3)где p1 (x), . . . , pL (x) - значения плотностей вероятностей классовK1 , . . . , KL в пространстве Rn .лотности вероятностейp1 (x), . . . , pL (x)также могут оцениваться исходя из предположения взаимнойнезависимости переменных X1 , . . . , Xn .Сенько Олег Валентинович ()МОТП, лекция 45 / 35Наивный байесовский классификаторВ этом случае pi (x) может быть представлена в виде произведенияодномерных плотностейpi (x) =nYpji (Xj ),j=1где pji (Xj ) - плотность распределения переменной Xj для класса Ki .Плотности pji (Xj ) могут оцениваться в рамках предположения о типераспределения.

Например, может использоваться гипотеза онормальности распределений1epji (Xj ) = √2πDji−(Xj −Mji )22Dji,где Mji ,Dji являются математическим ожиданием и дисперсиейпеременной Xj . Данне параметры легко оцениваются по Set .Сенько Олег Валентинович ()МОТП, лекция 46 / 35Методы, основанные на формуле БайесаМетоды распознавания, основанные на использовании формулыБайеса в форме (1) и (3) и гипотезе о независимости переменныхобычно называют наивными байесовскими классификаторами.Отметим, что знаменатели в правых частях формул (1) и (3)тождественны для всех классов. Поэтому при решении задачраспознавания достаточно использовать только числители.Сенько Олег Валентинович ()МОТП, лекция 47 / 35Аппроксимация плотности с помощь многомерного нормальногораспределенияПри решении задач распознавания с помощью формулы Байеса вформе (3) могут использоваться плотности вероятностиp1 (x), .

. . , pL (x), в которых переменные X1 , . . . , Xn не обязательноявляются независимыми. Чаще всего используется многомерноенормальное распределения. Плотность данного распределения вобщем виде представляется выражениемp(x) =1exp[− (x − µ)Σ−1 (x − µ)t ],2(2π) | Σ |1n212(4)гдеµ - математическое ожидание вектора признаков x; Σ - матрицаковариаций признаков X1 , . . . , Xn ; | Σ | -детерминант матрицы Σ.Для построения распознающего алгоритма достаточно оценитьвектора математических ожиданий µ1 , . . .