Лекция 4. Задачи прогнозирования_ Линейная машина_ Теоретические методы оценки обобщающей способности (2015 Лекции (Сенько))
Описание файла
Файл "Лекция 4. Задачи прогнозирования_ Линейная машина_ Теоретические методы оценки обобщающей способности" внутри архива находится в папке "2015 Лекции (Сенько)". PDF-файл из архива "2015 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 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 , . .
. , µL и матрицы ковариацийΣ1 , . . . , ΣL для классов K1 , . . . , KL , соответственно.Сенько Олег Валентинович ()МОТП, лекция 48 / 35Аппроксимация плотности с помощь многомерного нормальногораспределенияОценка вектора математических ожиданий µi вычисляется каксреднее значение векторов признаков по объектам обучающейвыборки Set из класса Ki :X1xjµ̂i =miTetsj ∈ SKi, где mi - число объектов класса Ki в обучающей выборке. Элементматрицы ковариаций для класса Ki вычисляется по формулеX1iσ̂kk(xjk − µik )(xjk0 − µik0 ),0 =miTetsj ∈ SKiгде xjk − µik - k-я компонента вектора µi .
Матрицу ковариации,iсостоящую из элементов σ̂kk0 обозначим Σ̂i . Очевидно, что согласноформуле Байеса максимум P (Ki | x) достигается для тех же самыхклассов для которых максимально произведение P (Ki )pi (x) .Сенько Олег Валентинович ()МОТП, лекция 49 / 35Использование формулы Байеса. Многомерное нормальноераспределениеОчевидно, что для байесовской классификации может использоватьсятакже натуральный логарифм ln[P (Ki )pi (x)] который согласновышеизложенному может быть оценён выражением1gi (x) = − xΣ̂−1xt + wi xt + gi0 ,2 igi0 - не зависящее от x слагаемое:где wi = µ̂i Σ̂−1iνi - доля объектов класса Ki в обучающей выборке.
Слагаемое gi0имеет вид11ntgi0 = − µ̂i Σ̂−1ln (| Σ̂i |) + ln(νi ) − ln(2π).i µ̂i −222Сенько Олег Валентинович ()МОТП, лекция 410 / 35Использование формулы Байеса. Многомерное нормальноераспределениеТаким образом объект с признаковым описанием x будет отнесёнпостроенной выше аппроксимацией байесовского классификатора кклассу, для которого оценка gi (x) является максимальной.
Следуетотметить, что построенный классификатор в общем случае являетсяквадратичным по признакам. Однако классификатор превращается влинейный, если оценки ковариационных матриц разных классовоказываются равными.Сенько Олег Валентинович ()МОТП, лекция 411 / 35Использование формулы Байеса. Многомерное нормальноераспределениеРассмотрим вариант метода Линейный дискриминант Фишера (ЛДФ)для распознавания двух классов K1 и K2 .
В основе метода лежитпоиск в многомерном признаковом пространстве такого направленияw , чтобы средние значения проекции на него объектов обучающейвыборки из классов K1 и K2 максимально различались. Проекциейпроизвольного вектора x на направление w является отношение(wxt ).|w|В качестве меры различий проекций классов на используетсяфункционал(X̂w1 − X̂w2 )2Φ(w, Set ) =,dˆw1 + dˆw2Сенько Олег Валентинович ()МОТП, лекция 412 / 35Линейный дискриминант ФишерагдеX̂wi =1mi(wxtj )|w|Xetsj ∈ STKi- среднее значение проекции векторов переменных X1 , . . . , Xn ,описывающих объекты из класса Ki ;1dˆwi =miXet T Kisj ∈S[(wxtj )− X̂wi ]2|w|- дисперсия проекций векторов, описывающих объекты из классаKi , i ∈ {1, 2}.
Смысл функционала Φ(w, Set ) ясен из его структуры. Онявляется по сути квадратом отличия между средними значениямипроекций классов на направление w , нормированным на суммувнутриклассовых выборочных дисперсий.Сенько Олег Валентинович ()МОТП, лекция 413 / 35Линейный дискриминант Фишера.Можно показать, что Φ(w, Set ) достигает максимума приttw = Σ̂−112 (µ̂1 − µ̂2 ),(5)где Σ̂12 = Σ̂1 + Σ̂2 . Таким образом оценка направления, оптимальногодля распознавания K1 и K2 может быть записана в виде ( 5 )Распознавание нового объекта s∗ по векторному описанию x∗производится по величине его проекции на направление w:γ(x∗ ) =(w, xt∗ ).|w|(6)При этом используется простое пороговое правило: при γ(x∗ ) > bобъект s∗ относится к классу K1 и s∗ относится к классу K2 впротивном случае.Сенько Олег Валентинович ()МОТП, лекция 414 / 35Линейный дискриминант Фишера.Граничный параметр b подбирается по обучающей выборке такимобразом, чтобы проекции объектов разных классов на оптимальноенаправление w оказались бы максимально разделёнными.
Простой, ноэффективной, стратегией является выбор в качестве пороговогопараметра b средней проекции объектов обучающей выборки на w.Метод ЛДФ легко обобщается на случай с несколькими классами. Приэтом исходная задача распознавания классов K1 , . . . , KL сводится кпоследовательности задач с двумя классами K10 и K20 :Зад. 1. Класс K10 = K1 , класс K20 = Ω \ K1.....................................................................Зад.