Лекция 4. Задачи прогнозирования_ Линейная машина_ Теоретические методы оценки обобщающей способности (1185306)
Текст из файла
Лекция 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.....................................................................Зад.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
