Лекция 4. Байесовский классиф_ линейн дискримин Фишера_ логистическая регрессия_ К-ближ соседей_ ROC-кривые (2014 Лекции (Сенько))
Описание файла
Файл "Лекция 4. Байесовский классиф_ линейн дискримин Фишера_ логистическая регрессия_ К-ближ соседей_ ROC-кривые" внутри архива находится в папке "2014 Лекции (Сенько)". PDF-файл из архива "2014 Лекции (Сенько)", который расположен в категории "". Всё это находится в предмете "(ммо) методы машинного обучения" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Лекция 4Статистические методы распознавания,Распознавание при заданной точности для некоторых классов,ROC-анализЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»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 оказались бы максимально разделёнными.