Лекция 4. Байесовский классиф_ линейн дискримин Фишера_ логистическая регрессия_ К-ближ соседей_ ROC-кривые (2014 Лекции (Сенько)), страница 2

Простой, ноэффективной, стратегией является выбор в качестве пороговогопараметра 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Распознавание при заданной точности распознавания некоторыхклассовБайесовский классификатор обеспечивает максимальную общуюточность распознавания.

Однако при решении конкретныхпрактических задач потери, связанные с неправильнойклассификацией объектов, принадлежащих к одному из классов,значительно превышают потери, связанные с неправильнойклассификацией объектов других классов. Для оптимизации потерьнеобходимо использование методов распознавания с учётомпредпочтительной точности распознавания для некоторых классов.Одним из возможных подходов является фиксирование порога дляточности распознавания одного из классов. Оптимальное решающееправило в задаче распознавания с двумя классами K1 и K2 ,обеспечивающее максимальную точность распознавания K2 прификсированной точности распознавания K1 , описывается критериемНеймана-Пирсона.Сенько Олег Валентинович ()МОТП, лекция 424 / 35Распознавание при заданной точности распознавания некоторыхклассовКритерий Неймана-Пирсона Максимальная точность распознаванияK2 при точности распознавания K1 равной α обеспечиваетсяправилом: Объект с описанием x относится в класс K1 , еслиP (K1 | x) ≥ ηP (K2 | x)где параметр η определяется из условияZP (K1 | x)p(x)dx = αΘΘ = {x | P (K1 | x) ≥ ηP (K2 | x)}Sp(x) - плотность распределения K1 K2 в точке x.

КритерийНеймана-Пирсона может быть использован, если известны плотностираспределения распознаваемых классов. Плотности могут бытьвосстановлены в рамках Байесовских методов обучения на основегипотез о виде распределений. ,Сенько Олег Валентинович ()МОТП, лекция 425 / 35Распознавание при заданной точности распознавания некоторыхклассовКритерий Неймана-Пирсона может быть использован, если известныплотности распределения распознаваемых классов.

Плотности могутбыть восстановлены в рамках Байесовских методов обучения наоснове гипотез о виде распределений. Однако существуютэффективные средства регулирования точности распознавания припредпочтительности одного из классов, которые не требуют гипотез овиде распределения. Данные средства основаны на структурераспознающего алгоритма. Каждый алгоритм распознавания классовK1 , . . . , Kl может быть представлен как последовательное выполнениераспознающего оператора R и решающего правила :A = R ⊗ C.Оператор оценок вычисляет для распознаваемого объекта sвещественные оценки γ1 , .

. . , γL за классы K1 , . . . , Kl соответственно.Сенько Олег Валентинович ()МОТП, лекция 426 / 35Распознавание при заданной точности распознавания некоторыхклассовРешающее правило производит отнесение объекта s по векторуоценок γ1 , . . . , γL к одному из классов. Распространённым решающимправилом является простая процедура, относящая объект в тот класс,оценка за который максимальна.В случае распознавания двух классов K1 и K2 распознаваемый объектs будет отнесён к классу K1 , если γ1 (s) − γ2 (s) > 0 и классу K2 впротивном случае.

Назовём приведённое выше правило правиломC(0) . Однако точность распознавания правила C(0) может оказатьсяслишком низкой для того, чтобы обеспечить требуемую величинупотерь, связанных с неправильной классификацией объектов, насамом деле принадлежащих классу K1 . Для достижения необходимойвеличины потерь может быть использовано пороговое решающееправило C(δ).Сенько Олег Валентинович ()МОТП, лекция 427 / 35Распознавание при заданной точности распознавания некоторыхклассовПрравило C(δ): распознаваемый объект s будет отнесён к классу K1 ,если γ1 (s) − γ2 (s) > δ и классу K2 в противном случае.

Обозначимчерез pci (δ, s) вероятность правильной классификации правилом C(δ)объекта s , на самом деле принадлежащего Ki , i ∈ {1, 2}. При δ < 0pc1 (δ, s) ≥ pc1 (0, s) , но pc2 (δ, s) ≤ pc2 (0, s). Уменьшая δ , мыувеличиваем pc1 (δ, s) и уменьшаем pc2 (δ, s) . Напротив, увеличивая δ ,мы уменьшаем pc1 (δ, s) и увеличиваем pc2 (δ, s). Зависимость междуpc1 (δ, s) и pc2 (δ, s) может быть приближённо восстановлена пообучающей выборке Set , включающей описания объектов {s1 , . . . , sm }.Сенько Олег Валентинович ()МОТП, лекция 428 / 35Распознавание при заданной точности распознавания некоторыхклассовПустьγ1 (s1 ) .