Байесовская классификация

Содержание

Слайд 2

Вероятность: основные понятия Определения (неформальные) Вероятность – число, сопоставляемое событию и

Вероятность: основные понятия

Определения (неформальные)
Вероятность – число, сопоставляемое событию и показывающее «насколько

часто» будет происходить это событие при проведении случайного эксперимента
Закон распределения вероятностей в случайном эксперименте – правило, сопоставляющее вероятности событиям в эксперименте
Пространство исходов S случайного эксперимента – множество всех возможных итогов эксперимента

вероятность

события

Закон распределения

Слайд 3

Вероятность: свойства Свойство 1: Свойство 2: Свойство 3: Свойство 4: Для

Вероятность: свойства

Свойство 1:
Свойство 2:
Свойство 3:
Свойство 4: Для если ,то
Свойство 5:
Свойство 6:
Свойство

7: Если то
Слайд 4

Условная вероятность Если A и B – события, то вероятность события

Условная вероятность

Если A и B – события, то вероятность события A

при условии, что B уже произошло, определяется соотношением
Интерпретация
Новое обстоятельство «В произошло» имеет следующий эффект
Исходное вероятностное пространство S (весь квадрат) сужается до B (правый круг)
Событие A становится A∩B
Таким образом, P[B] просто нормирует вероятность событий, происходящих совместно с B
Слайд 5

Формула полной вероятности Пусть B1, B2, …, BN, – взаимоисключающие события,

Формула полной вероятности

Пусть B1, B2, …, BN, – взаимоисключающие события, которые

в объединении дают пространство исходов S (т.е разбиение S)
Событие A может быть представлено как
Поскольку B1, B2, …, BN – взаимоисключающие, то
и, следовательно,
Слайд 6

Формула Байеса Пусть B1, B2, …, BN дают разбиение S. Предположим,

Формула Байеса

Пусть B1, B2, …, BN дают разбиение S. Предположим, что произошло

A. Какова вероятность Bj?
Из определения условной вероятности и формулы полной вероятности следует
Это соотношение известно как формула Байеса (правило Байеса, теорема Байеса) и является одним из самых полезных соотношений в теории вероятностей и статистике
В распознавании образов формула Байеса – один из фундаментальных результатов

Томас Байес (Thomas Bayes) 1702-1761

Слайд 7

Формула Байеса и статистическое распознавание образов Для решения задачи классификации формула

Формула Байеса и статистическое распознавание образов

Для решения задачи классификации формула Байеса

может быть переписана следующим образом:
где ωj – j-й класс, x – вектор характеристик образа
Типичное решающее правило: выбрать класс ωj, для которого P[ωj |x] – наибольшая
Интуитивно: выбираем класс, который наиболее ожидаемо даст x
Каждый член в формуле Байеса имеет специальное название
P[ωj] априорная вероятность (класса ωj)
P[ωj |x] апостериорная вероятность (класса ωj при условии, что в результате наблюдения получен x)
P[x|ωj ] правдоподобие (условная вероятность появления наблюдения x, при условии, что наблюдается класс ωj)
P[x] нормализующая константа, не влияющая на выбор решения
Слайд 8

Простой пример Диагностическая задача: необходимо решить, болен ли пациент, основываясь на

Простой пример

Диагностическая задача: необходимо решить, болен ли пациент, основываясь на несовершенном

тесте заболевания
Некоторые больные могут быть не распознаны (ложно-отрицательный результат теста)
Некоторые здоровые могут быть отнесены к больным (ложно-положительный результат теста)
Терминология
Вероятность P[ОТР|ЗДОРОВ] истинно-отрицательного результата теста – избирательность
Вероятность P[ПОЛ|БОЛЕН] истинно-положительного результата теста – чувствительность
Слайд 9

Простой пример Задача Имеется выборка из 10000 человек, в которой больными

Простой пример

Задача
Имеется выборка из 10000 человек, в которой больными являются по

1 человеку из каждых 100
Используется тест заболевания с избирательностью – 98% и чувствительностью – 90%
Допустим для Вас тест – положительный.
Какова вероятность, что Вы больны?
Решение 1: Заполнить таблицу сопряженности
Решение 2: Воспользоваться формулой Байеса
Слайд 10

Простой пример Задача Имеется выборка из 10000 человек, в которой больными

Простой пример

Задача
Имеется выборка из 10000 человек, в которой больными являются по

1 человеку из каждых 100
Используется тест заболевания с избирательностью – 98% и чувствительностью – 90%
Допустим для Вас тест – положительный.
Какова вероятность, что Вы больны?
Решение 1: Заполнить таблицу сопряженности
Решение 2: Воспользоваться формулой Байеса
Слайд 11

Простой пример Задача Имеется выборка из 10000 человек, в которой больными

Простой пример

Задача
Имеется выборка из 10000 человек, в которой больными являются по

1 человеку из каждых 100
Используется тест заболевания с избирательностью – 98% и чувствительностью – 90%
Допустим для Вас тест – положительный.
Какова вероятность, что Вы больны?
Решение 1: Заполнить таблицу сопряженности
Решение 2: Воспользоваться формулой Байеса
Слайд 12

Наивный байесовский классификатор Наивный байесовский классификатор – простой вероятностный классификатор, основанный

Наивный байесовский классификатор

Наивный байесовский классификатор – простой вероятностный классификатор, основанный
на

формуле Байеса
на предположении независимости наблюдаемых признаков (что наивно)
Графически
ω – класс (метка, номер класса), требуется оценить P[ω |x1,x2,…,xN]
xi – наблюдаемые признаки
все признаки независимы

ω

x1

x2

xN

……

Слайд 13

Наивный байесовский классификатор Вероятностная модель наивного байесовского классификатора Строго говоря, Но

Наивный байесовский классификатор

Вероятностная модель наивного байесовского классификатора
Строго говоря,
Но в виду условной

независимости признаков и
Тогда распределение условной вероятности класса ω есть где Z – константа, не зависящая от ω
Слайд 14

Наивный байесовский классификатор Наивный байесовский классификатор – комбинация вероятностной модели и

Наивный байесовский классификатор

Наивный байесовский классификатор – комбинация вероятностной модели и решающего

правила «максимум апостериорной вероятности»
Решающее правило
Содержательно: «Выбрать тот класс, который наиболее ‘вероятен’ для измерения x»
Формально: Вычислить апостериорную вероятность для каждого класса P[ωj|x] и выбрать класс с ее наибольшим значением
Для построения наивного байесовского классификатора
Оценить P[ω=ωj], как долю объектов в обучающей выборке, для которых ω=ωj
Оценить P[xi=fi | ω=ωj ], как долю объектов, для которых ω= ωj и при этом xi=fi
Для предсказания значения ω, найти то j, которое дает максимальное значение апостериорной вероятности
Слайд 15

Наивный байесовский классификатор Задача. Отнести текстовые документы к одному из предопределенных

Наивный байесовский классификатор

Задача. Отнести текстовые документы к одному из предопределенных классов

(спорт, политика, экономика,…)
Дано. Имеется выборка из N текстов, разбитая на К групп
Решение
Вычислить априорные вероятности классов
Посчитать количество текстов в каждом классе (группе) – Nj
Оценить априорную вероятность P[ωj] = Nj / N, j=1,…,K
Вычислить условные вероятности появления слов в текстах разных классов
Пусть есть словарь из M слов: x1,x2,…xM
Вычислить cij – сколько раз слово xi встретилось в текстах класса ωj
Вычислить nj, сколько слов из словаря встречается в текстах класса ωj
Условные вероятности слов есть P[xi | ωj] = cij / nj , j=1,…,K
Слайд 16

Наивный байесовский классификатор Задача. Отнести текстовые документы к одному из предопределенных

Наивный байесовский классификатор

Задача. Отнести текстовые документы к одному из предопределенных классов

(спорт, политика, экономика,…)
Дано. Имеется выборка из N текстов, разбитая на К групп
Решение
Классифицировать новый текст t:
Вычислить признаки t (посчитать сколько раз входит слово xi в t)
P[ωj | t] = P[ωj | x1,x2,…xM] = P[ωj] P[x1| ωj] P[x2| ωj]… P[xM| ωj]
Отнести t к классу ωj с максимальной апостериорной вероятностью P[ωj | t]
Слайд 17

Наивный байесовский классификатор Задача. Отнести текстовые документы к одному из предопределенных

Наивный байесовский классификатор

Задача. Отнести текстовые документы к одному из предопределенных классов

(спорт, политика, экономика,…)
Дано. Имеется выборка из N текстов, разбитая на К групп
Решение
Предобработка
Устранение пунктуации
Устранение чисел
Приведение регистра (все буквы - строчные)
Устранение слов короче 4 символов
Построение словаря и оценка встречаемости слов производится с помощью хэш-таблицы
Как выбрать ключевые слова (признаки)?
Взять k наиболее популярных слов в каждом классе
Взять k наиболее популярных слов в выборке
Объединить все эти слова. Вектор признаков – количества этих слов.
Слайд 18

Наивный байесовский классификатор Задача. Отнести текстовые документы к одному из предопределенных

Наивный байесовский классификатор

Задача. Отнести текстовые документы к одному из предопределенных классов

(спорт, политика, экономика,…)
Дано. Имеется выборка из N текстов, разбитая на К групп
Решение
Прочие нюансы
Нулевые вероятности «убивают» байесовский классификатор
Если слово встречается только в одном классе, то условные вероятности такого слова «обнулятся»
Для предотвращения этого условные вероятности следует оценивать как P[xi | ωj] = ε / nj , где ε – малая настраиваемая константа
Все вероятности имеет смысл логарифмировать, чтобы избежать переполнения (особенно при вычислении длинного произведения)
Непрерывные признаки имеет смысл квантовать (дискретизировать)
Слайд 19

Критерий отношения правдоподобия Пусть объект классифицируется на основании измерения (вектора характеристик)

Критерий отношения правдоподобия
Пусть объект классифицируется на основании измерения (вектора характеристик) x
Разумное

решающее правило:
«Выбрать тот класс, который наиболее ‘вероятен’ для измерения x»
Более формально: вычислить апостериорную вероятность для каждого класса P(ωj |x) и выбрать класс с ее наибольшим значением
Слайд 20

Критерий отношения правдоподобия В случае 2-классовой задачи классификации: Если P(ω1 |x)

Критерий отношения правдоподобия

В случае 2-классовой задачи классификации:
Если P(ω1 |x) > P(ω2

|x), выбрать ω1, иначе выбрать ω2
Или, короче:
Используя формулу Байеса, получим
P(X) не влияет на решающее правило и может быть исключено
Λ(x) называется отношением правдоподобия, а решающее правило известно как критерий отношения правдоподобия (КОП)
Слайд 21

Критерий отношения правдоподобия: пример Используя критерий отношения правдоподобия, построить решающее правило

Критерий отношения правдоподобия: пример

Используя критерий отношения правдоподобия, построить решающее правило для

следующих условных плотностей классов (полагая априорные вероятности равными):
Решение
КОП для заданных плотностей:
Упрощаем:
Меняем знаки и логарифмируем:
В итоге:
Слайд 22

Критерий отношения правдоподобия: пример Предыдущий пример понятен с интуитивной точки зрения,

Критерий отношения правдоподобия: пример

Предыдущий пример понятен с интуитивной точки зрения, т.к.

правдоподобия идентичны и отличаются только средними значениями
Как изменится критерий отношения правдоподобия, если, например, априорные вероятности такие, что P(ω1) = 2P(ω2)?
Слайд 23

Вероятность ошибки Мерой качества любого решающего правила может выступать с вероятность

Вероятность ошибки

Мерой качества любого решающего правила может выступать с вероятность ошибки

P[error]
В соответствии с формулой полной вероятности может быть представлена как
Условная вероятность ошибки класса P[error | ωi]:
Для 2-классовой задачи вероятность ошибки примет вид
где εi – интеграл правдоподобия P(x | ωi) по области Rj, соответствующей выбору ωj
Слайд 24

Вероятность ошибки Для решающего правила из рассмотренного примера интегралы ε1 и

Вероятность ошибки
Для решающего правила из рассмотренного примера интегралы ε1 и ε2

показаны на рисунке
Поскольку априорные вероятности полагались равными, то
Слайд 25

Вероятность ошибки Выясним, насколько хорош критерий отношения правдоподобия в смысле вероятности

Вероятность ошибки

Выясним, насколько хорош критерий отношения правдоподобия в смысле вероятности ошибки
Для

этого удобно выразить P[error] в терминах апостериорной вероятности P[error | x]
Оптимальное решающее правило – правило, минимизирующее P[error | x] для любого x, чтобы минимизировать весь интеграл
В каждой точке x’ вероятность P[error | x’] = P(ωi|x’), если выбран другой класс ωj
Слайд 26

Вероятность ошибки АЛТ Вероятность для решающего правила АЛТ АЛТ КОП КОП

Вероятность ошибки

АЛТ

Вероятность

для решающего правила АЛТ

АЛТ

КОП

КОП

для решающего правила КОП

В каждой точке x’ вероятность P[error

| x’] = P(ωi|x’), если выбран другой класс ωj
Очевидно, что для КОП дает наименьшую вероятность ошибки P[error | x’] в любой точке x’
Слайд 27

Вероятность ошибки Для любой задачи минимальная вероятность ошибки достигается, если в

Вероятность ошибки

Для любой задачи минимальная вероятность ошибки достигается, если в качестве

решающего правила
используется критерий отношения правдоподобия.

Эта вероятность ошибки называется байесовским уровнем ошибки
и является наилучшим значением среди
всех возможных классификаторов.

Слайд 28

Байесовский риск До сих пор полагалось, что цена ошибочного отнесения к

Байесовский риск
До сих пор полагалось, что цена ошибочного отнесения к классу

ω1 образца, принадлежащего классу ω2, совпадает с ценой противоположной ошибки. В общем случае это не верно.
Ошибочное отнесение больного раком к здоровым имеет несравненно более печальные последствия, чем обратная ошибка
Это формализуется введением функции стоимости ошибок Cij
Cij – цена отнесения образца к классу ωi если на самом деле он принадлежит классу ωj
Байесовский риск определяется как мат. ожидание стоимости
Слайд 29

Байесовский риск Какое решающее правило минимизирует байесовский риск? Заметим, что Байесовский

Байесовский риск

Какое решающее правило минимизирует байесовский риск?
Заметим, что
Байесовский риск выражается как
Для

любого правдоподобия
Слайд 30

Байесовский риск Подставим последнее уравнение в выражение байесовского риска Избавимся от

Байесовский риск

Подставим последнее уравнение в выражение байесовского риска
Избавимся от интегралов по

R2
Т.к. первые два слагаемых – константы, ищем R1, минимизирующее остальное:
Слайд 31

Байесовский риск На уровне интуиции: к каким областям R1 приводит минимизация

Байесовский риск

На уровне интуиции: к каким областям R1 приводит минимизация байесовского

риска?
Отыскивается R1, минимизирующая интеграл
Иными словами, ищутся области, в которых g(x) < 0
Таким образом, R1 выбирается так, чтобы
Слайд 32

Байесовский риск На уровне интуиции: к каким областям R1 приводит минимизация

Байесовский риск

На уровне интуиции: к каким областям R1 приводит минимизация байесовского

риска?
Отыскивается R1, минимизирующая интеграл
Иными словами, ищутся области, в которых g(x) < 0
Таким образом, R1 выбирается так, чтобы
Или, после нехитрых преобразований:
Итак, минимизация байесовского риска снова приводит к критерию отношения правдоподобий
Слайд 33

Байесовский риск: пример Классификация на два класса с функциями правдоподобия Пусть

Байесовский риск: пример

Классификация на два класса с функциями правдоподобия
Пусть P(ω1) = P(ω2)

= 0.5, С11 = С22 = 0, С12 = 1, С21 = 31/2
Построить решающее правило, минимизирующее вероятность ошибки
Слайд 34

Вариации критерия отношения правдоподобия Решающее правило КОП, минимизирующее байесовский риск обычно

Вариации критерия отношения правдоподобия

Решающее правило КОП, минимизирующее байесовский риск обычно называется

критерием Байеса
В частном случае, при минимизации вероятности ошибки, решающее правило называется максимальным апостериорным критерием (МАК)
В случае равных априорных вероятностей P(ωi) = ½ решающее правило называется критерием максимального правдоподобия

Критерий максимального правдоподобия

Слайд 35

Правило минимизации P[error] для многоклассовых задач Правило минимизации вероятности ошибки P[error]

Правило минимизации P[error] для многоклассовых задач

Правило минимизации вероятности ошибки P[error]

легко обобщается на случай многих классов
Для простоты вводится дополнительная вероятность – вероятность правильного выбора класса: P[error] = 1 – P[correct]
Вероятность корректного распознавания
Задача минимизации P[error] эквивалентна максимизации P[correct]
P[correct] в терминах апостериорных вероятностей:
Слайд 36

Правило минимизации P[error] для многоклассовых задач Правило минимизации вероятности ошибки P[error]

Правило минимизации P[error] для многоклассовых задач

Правило минимизации вероятности ошибки P[error]

легко обобщается на случай многих классов
P[correct] в терминах апостериорных вероятностей:
Для максимизации P[correct] нужно максимизировать каждый из интегралов Ji. Интегралы максимизируются выбором классов ωi, дающих максимум P[ωi|x], т.е. определением области Ri, в которой P[ωi|x] максимальна.
Таким образом, правило минимизации P[error] – максимальный апостериорный критерий
Слайд 37

Минимизация байесовского риска для многоклассовых задач Новые обозначения αi – решение

Минимизация байесовского риска для многоклассовых задач

Новые обозначения
αi – решение о

выборе класса ωi
α(x) – общее правило выбора, отображающее вектор x на классы ωi: α(x) ? {α1, α2, …, αC}
Условный риск R(αi|x) отнесения вектора x к классу ωi есть
Байесовский риск, связанный с решающим правилом α(x) есть
Слайд 38

Минимизация байесовского риска для многоклассовых задач Байесовский риск, связанный с решающим

Минимизация байесовского риска для многоклассовых задач

Байесовский риск, связанный с решающим

правилом α(x) есть
Для минимизации этого выражения необходимо минимизировать условный риск R(α(x)|x) в каждой точке пространства x, что эквивалентно выбору класса ωi, такого, что R(αi|x) минимален
Слайд 39

Разделяющие функции Все решающие правила, рассмотренные в этой лекции, имеют одинаковую

Разделяющие функции

Все решающие правила, рассмотренные в этой лекции, имеют одинаковую структуру
В

каждой точке x пространства признаков выбрать класс ωi такой, что минимизируется (максимизируется) некоторая мера gi(x)
Эта структура может быть формализована с помощью множества разделяющих функций gi(x), i=1,…,C и следующего решающего правила
Тогда решающее правило может быть визуализировано как сеть или автомат, вычисляющий C разделяющих функций и выбирающий класс, соответствующий наибольшему значению

“отнести x к классу ωi, если gi(x)>gi(x) ∀j≠i”

Характеристики

Разделяющие функции

Класс

Слайд 40

Разделяющие функции Основные критерии как разделяющие функции

Разделяющие функции

Основные критерии как разделяющие функции

Слайд 41

Байесовские классификаторы для нормально распределенных классов Для случая нормально распределенных классов

Байесовские классификаторы для нормально распределенных классов

Для случая нормально распределенных классов критерий

минимизации ошибки (максимизации апостериорной вероятности, МАВ) где gi(x) = P(ωi | x), может быть существенно упрощен

“отнести x к классу ωi, если gi(x)>gi(x) ∀j≠i”

Слайд 42

Байесовские классификаторы для нормально распределенных классов Выражения для гауссовых плотностей в

Байесовские классификаторы для нормально распределенных классов

Выражения для гауссовых плотностей в общем

виде
Плотность многомерного нормального распределения
Преобразованная разделяющая функция критерия МАВ (по формуле Байеса)
Исключая постоянные члены, получим
После логарифмирования
Это выражение называется квадратичной разделяющей функцией
Слайд 43

Случай 1: Σi = σ2I Случай возникает. когда характеристики образцов статистически

Случай 1: Σi = σ2I

Случай возникает. когда характеристики образцов статистически независимы

и имеют одинаковую вариацию по всем классам
Т.к. gi(x) линейны, границы классов – гиперплоскости
Если априорные вероятности равны, то
Это – классификатор по минимальному расстоянию (по ближайшему среднему)
ГМТ с постоянной вероятностью – гиперсферы
Для единичной дисперсии, расстояние становится еклидовым
Слайд 44

Случай 1: Σi = σ2I, пример Двумерная задача, три класса со следующими средними и ковариациями:

Случай 1: Σi = σ2I, пример

Двумерная задача, три класса со следующими

средними и ковариациями:
Слайд 45

Случай 2: Σi = Σ (Σ – диагональная) Классы по-прежнему имеют

Случай 2: Σi = Σ (Σ – диагональная)
Классы по-прежнему имеют одинаковую

матрицу ковариации, но характеристики имеют разные дисперсии
Функция линейна, границы классов – гиперплоскости
ГМТ точек с одинаковой вероятностью – гиперэллипсоиды
Единственное отличие от предыдущего случая – нормализация осей
Слайд 46

Случай 2: Σi = Σ (Σ – диагональная), пример Двумерная задача,

Случай 2: Σi = Σ (Σ – диагональная), пример

Двумерная задача, три

класса со следующими средними и ковариациями:
Слайд 47

Случай 3: Σi = Σ (Σ – не диагональная) Классы по-прежнему

Случай 3: Σi = Σ (Σ – не диагональная)

Классы по-прежнему имеют

одинаковую матрицу ковариации, но матрица – не диагональная
Функция линейна, границы классов – гиперплоскости
ГМТ точек с одинаковой вероятностью – гиперэллипсоиды, натянутые на собственные вектора матрицы ковариации
При равных априорных вероятностях – классифкатор по минимальному расстоянию Махаланобиса:
Слайд 48

Случай 3: Σi = Σ (Σ – не диагональная), пример Двумерная

Случай 3: Σi = Σ (Σ – не диагональная), пример

Двумерная задача,

три класса со следующими средними и ковариациями:
Слайд 49

Случай 4: Σi = σi2I Классы имеют разные матрицы ковариации, которые

Случай 4: Σi = σi2I

Классы имеют разные матрицы ковариации, которые пропорциональны

единичной матрице
Границы классов – гиперэллипсоиды
ГМТ точек с одинаковой вероятностью – гиперсферы, определяемые осями пространства характеристик
Слайд 50

Случай 4: Σi = σi2I, пример Двумерная задача, три класса со следующими средними и ковариациями:

Случай 4: Σi = σi2I, пример

Двумерная задача, три класса со следующими

средними и ковариациями:
Слайд 51

Случай 5: Σi ≠ Σj (общий случай) Для общего случая разделяющая

Случай 5: Σi ≠ Σj (общий случай)

Для общего случая разделяющая функция

выглядит так:
Или, после преобразований:
Границы классов – гиперэллипсоиды и гиперпараболоиды
ГМТ точек с одинаковой вероятностью – гиперэллипсоиды, определяемые собственными векторами матриц Σi для каждого из классов в отдельности
Слайд 52

Случай 5: Σi ≠ Σj (общий случай), пример Двумерная задача, три

Случай 5: Σi ≠ Σj (общий случай), пример

Двумерная задача, три класса

со следующими средними и ковариациями:
Слайд 53

Построить линейную разделяющую функцию для трехмерной двухклассовой задачи распознавания по следующим

Построить линейную разделяющую функцию для трехмерной двухклассовой задачи распознавания по следующим

данным:
Решение
Классифицировать тестовый образец xt = [0.1 0.7 0.8]T

Численный пример