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

, µ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.....................................................................Зад.

L. Класс K10 = KL , класс K20 = Ω \ KLДля каждой из L задач ищется оптимальное направление. Врезультате получается набор из L направлений w1 , . . . , wL .Сенько Олег Валентинович ()МОТП, лекция 415 / 35Линейный дискриминант Фишера.В результате получается набор из L направлений w1 , . . . , wL . Прираспознавании нового объекта s∗ по признаковому описанию x∗вычисляются проекции на w1 , .

. . , wL :tt1 ,x∗ )L ,x∗ )γ1 (x∗ ) = (w|w, . . . . . . . . . . . . . . . . . . . . . . . . . . ., γL (x∗ ) = (w|w.1|L|Распознаваемый объект относится к тому классу, соответствующемумаксимальной величине проекции. Распознавание может производитсятакже по величинам[γ1 (x∗ ) − b1 ], . . . . . . . . . . . . . . . . . . . .

. . . . . . ., [γL (x∗ ) − bL ].Сенько Олег Валентинович ()МОТП, лекция 416 / 35Логистическая регрессия.Целью логистической регрессии является аппроксимация плотностиусловных вероятностей классов в точках признакового пространства.При этом аппроксимация производится с использованиемлогистической функции.1ez=g(z) =1 + ez1 + e−zРис 1. Логистическая функция.Сенько Олег Валентинович ()МОТП, лекция 417 / 35Логистическая регрессия.В методе логистическая регрессия связь условной вероятности классаK с прогностическими признаками осуществляются через переменнуюZ , которая задаётся как линейная комбинация признаков:z = β0 + β1 X1 + . .

. + βn Xn .Условная вероятность K в точке векторного пространстваx∗ = (x1∗ , . . . , xn∗ ) задаётся в видеP (K | x) =eβ0 +β1 X1 +...+βn Xn1=β+βX+...+βX−β−βX1 −...−βn Xnnn011011+e1+eСенько Олег Валентинович ()МОТП, лекция 4(7)18 / 35Логистическая регрессия.Оценки регрессионных параметров β0 , β1 , . . . , βn могут бытьвычислены по обучающей выборке с помощью различных вариантовметода максимального правдоподобия.

Предположим, что объектыобучающей выборки сосредоточены в точках признаковогоe = {x1 , . . . , xr } . При этомпространства из множества xраспределение объектов обучающей выборка по точкам задаётся спомощью набора пар {(m1 , k1 ), . . . , (mr , kr )} , где mi - общее числообъектов в точке xi , ki - число объектов класса K в точке xi .Вероятность данной конфигурации подчиняется распределениюБернулли. Введём обозначение %(x) = P (K | x) .

Оценка векторарегрессионных параметров β = (β0 , . . . , βn ) может быть получена спомощью метода максимального правдоподобия. Функцияправдоподобия может быть записана в видеe) =L(β, xrYkiCm[%(x)j ]kj [1 − %(x)j ](mj −kj )i(8)j=1Сенько Олег Валентинович ()МОТП, лекция 419 / 35Логистическая регрессия.Принимая во внимание справедливость равенств%(x)= eβ0 +β1 X1 +...+βn Xn ,1 − %(x)1 − %(x) =1,1 + eβ0 +β1 X1 +...+βn Xnприходим равенствуe) =L(β, xrYki ki β0 +β1 xj1 +...+βn xjnCmeij=1Сенько Олег Валентинович ()1(1 +МОТП, лекция 4eβ0 +β1 xj1 +...+βn xj n )mi(9)20 / 35Логистическая регрессия.Поиск оптимального значения параметров удобнее производить, решаязадачу максимизации логарифма функции правдоподобия, который внашем случае принимает вид:e )] =ln[L(β, xrXkln Cmjj+j=1+rXj=1Сенько Олег Валентинович ()rX[kj (β0 + β1 xj1 + .

. . + βn xjn )]+j=1mj ln(11+eβ0 +β1 xj1 +...+βn xjnМОТП, лекция 4)21 / 35K-ближайших соседей.Простым, но достаточно эффективным подходом к решению задачраспознавания является метод k-ближайших соседей. Оценкаусловных вероятностей P (Ki | x) ведётся по ближайшей окрестностиVk точки x , содержащей k признаковых описаний объектовобучающей выборки. В качестве оценки выступает отношение kki , гдеki - число признаковых описаний объектов обучающей выборки из Kiвнутри Vk . Окрестность Vk задаётся с помощью функции расстоянияe ×Xe , где Xe ρ(x0 , x00 ) заданной на декартовом произведении Xобласть допустимых значений признаковых описаний.

В качествефункции расстояния может быть использована стандартная эвклидоваметрика. То есть расстояние между двумя векторами x0 = (x01 , . . . , x0n )и x00 = (x001 , . . . , x00n )vu nu1 X000(x0i − x”i )2 .ρ(x , x ) = tni=1Сенько Олег Валентинович ()МОТП, лекция 422 / 35K-ближайших соседей.Для задач с бинарными признаками в качестве функции расстоянияможет быть использована метрика Хэмминга, равная числусовпадающих позиций в двух сравниваемых признаковых описаниях.Окрестность Vk ищется путём поиска в обучающей выборке Setвекторных описаний, ближайших в смысле выбранной функциирасстояний, к описанию x∗ распознаваемого объекта s∗ .Единственным параметром, который может быть использован длянастройки (обучения) алгоритмов в методе k–ближайших соседейявляется собственно само число ближайших соседей. Дляоптимизации параметра k обычно используется метод, основанный наскользящем контроле.

Оценка точности распознавания производитсяпо обучающей выборке при различных k и выбирается значениеданного параметра, при котором полученная точность максимальна.Сенько Олег Валентинович ()МОТП, лекция 423 / 35Распознавание при заданной точности распознавания некоторыхклассовБайесовский классификатор обеспечивает максимальную общуюточность распознавания.