ИИМО ПИАШ 2022 Л02

Пусть существуют два множества:
Множество объектов – образов X
Множество ответов Y
Существует целевая функция
значения которой известны только на конечном
подмножестве объектов
Совокупность пар «объект-ответ»
- обучающая выборка.
Задача обучения заключается в том, чтобы по
выборке построить решающую функцию ,
, которая бы приближала целевую
функцию , причём не только на объектах
обучающей выборки, но и на всем множестве
Задача машинного обучения с учителем
Постановка задачи распознавания образов
Обучающая выборка
Данные, с неизвестными ответами
/45

Модель алгоритма
Требуется построить отображение (гипотезу)
Пусть А – параметрическое семейство отображений
Г – пространство допустимых значений параметра γ (пространство поиска)
Будем выбирать отображение для решение задачи из А
Процесс выбора – обучение
Построение отображения
по обучающей выборке – метод бучения
Обучение сводится к поиску точки в пространстве поиска Г
Простейшая модель:
Пространство поиска – значения вектора γ и смещения с
Гипотеза a – какая-то конкретная прямая
/45

Замечание
Гипотез, имеющих нулевой эмпирический риск может существовать неограниченное количество:
Наиболее общая гипотеза
Наиболее частная гипотеза
Золотая середина?
Вопрос:
Какую модель выбрать?
/45

Эмпирический риск
- обучающая выборка
Эмпирический риск (ошибка тренировки):
Метод минимизации эмпирического риска*:
Таким образом задача машинного обучения сводится к задаче оптимизации
– функция потерь = величине ошибки алгоритма a на объекте
характеризует отличие правильного ответа от ответа данного построенным отображением
/45

Обобщающая способность
Обобщающая способность (generalization ability, generalization performance).
Алгоритм обучения обладает способностью к обобщению, если вероятность ошибки на тестовой выборке достаточно мала или хотя бы предсказуема, то есть не сильно отличается от ошибки на обучающей выборке.
complex model
simpler model
Проблема обобщения: малый эмпирический риск Remp не означает, что истинный ожидаемый риск R будет мал
/45

Основы теории вероятностей:
Виды событий
Достоверные события всегда происходят при осуществлении данной совокупности условий
Невозможные события никогда не происходят при осуществлении данной совокупности условий
Случайные события могут произойти или не произойти при осуществлении данной совокупности условий
/45

Основы теории вероятностей:
Случайные события
Несовместными называются события, которые не могут одновременно произойти в одном испытании
Совокупность случайных событий А1, А2, А3,… Аn называется полной группой для данного испытания, если в результате испытания обязательно происходит только одно из событий этой совокупности
Два события (А и Ā) называются противоположными, если появление одного из них равносильно непоявлению другого
/45

Основы теории вероятностей:
Случайные события
Совместными называются события, которые могут одновременно произойти в одном испытании
События называются независимыми, если появление одного из них не изменяет вероятности появления второго.
События называются зависимыми если появление одного из них зависит от появления другого
Равновозможными называются события, если ни у одного из них нет объективного преимущества перед другим
/45

Основы теории вероятностей:
Классическое определение вероятности
Вероятностью события А называют отношение числа благоприятствующих этому событию элементарных событий (m) к общему числу всех равновозможных несовместных элементарных событий (n), образующих полную группу:
Чтобы рассчитать классическую вероятность необходимо до проведения испытаний теоретически подсчитать:
общее число всех равновозможных несовместных элементарных событий (n)
число благоприятствующих этому событию равновозможных несовместных элементарных событий (m)
Вероятность достоверного события Р = 1
Вероятность невозможного события Р = 0
Вероятность случайного события 0 < P < 1
/45

Статистическая модель, используемая для прогнозирования вероятности возникновения некоторого события путём его сравнения с логистической кривой. Эта регрессия выдаёт ответ в виде вероятности бинарного события (1 или 0).
Для этого вводится так называемая зависимая переменная, принимающая лишь одно из двух значений — как правило, это числа 0 (событие не произошло) и 1 (событие произошло), и множество независимых переменных (также называемых признаками, предикторами или регрессорами) — вещественных значений на основе которых требуется вычислить вероятность принятия того или иного значения зависимой переменной.
Делается предположение о том, что вероятность наступления события
Логистическая регреcсия
Для оценки коэффициентов регрессии обычно применяется метод оценки максимального правдоподобия
– логистическая функция
– регрессия
/45

Thomas Bayes
(c. 1702 – April 17, 1761)
Томас Байес
Математические интересы Байеса относились к теории вероятностей. Он сформулировал и решил одну из основных задач этого раздела математики (теорема Байеса). Работа, посвящённая этой задаче, была опубликована в 1763 году, посмертно. Формула Байеса, дающая возможность оценить вероятность событий эмпирическим путём, играет важную роль в современной математической статистике и теории вероятностей.
То́мас Ба́йес (в части источников: Бейес, более точная транскрипция: Бейз, англ. Thomas Bayes [beɪz]) — английский математик, пресвитерианский священник, член Лондонского королевского общества (1742).
/45

Определение.
Пусть Р(А)>0.
Условной вероятностью Р(В/А) события В при условии, что
событие А наступило, называется число
Обозначения:
Условная вероятность удовлетворяет всем аксиомам вероятности.
В частности,
Условная вероятность
/45

Независимые события
Определение.
События А и В называются независимыми, если
Определение. Пусть Р(А)>0 и Р(В)>0.
Событие А не зависит от В, если
Следствие.
Если событие А не зависит от В, то и событие В не зависит от А.
Доказательство.
На практике из физической независимости событий делают вывод о теоретико-вероятностной независимости.
/45

События образуют полную группу, если они
1) попарно несовместны
2) в результате эксперимента обязательно какое- либо одно из них наступит
Пример.
В стохастическом эксперименте рассмотрим события
Они образуют полную группу.
Полная группа событий
- гипотезы
/45

Формула полной вероятности
Теорема.
Если события
образуют полную группу ,
то для любого события А справедлива формула
/45

Формула Байеса
Теорема.
Пусть события
образуют полную группу.
Пусть событие А наступило ( Р(А)>0 ).
Тогда вероятность того,
что при этом была реализована гипотеза (наступило событие)
вычисляется по формуле
Формула Байеса позволяет переоценить вероятности гипотез после того, как проведено испытание, в результате которого произошло событие А.
/45

Формула Байеса. Частный случай
Рассмотрим события
они образуют полную группу.
Пусть событие А наступило ( Р(А)>0 ).
Тогда вероятность того,
что при этом была реализована гипотеза
вычисляется по формуле
/45

Пример:
Какова вероятность увидеть на улице динозавра?
Идя по улице вы видите такую сцену:
Правдоподобие – вероятность того, что будь это действительно динозавр наблюдение было бы таким
Априорная вероятность встретить динозавра
Априорная вероятность увидеть такую сцену
(это и есть наблюдение X)
Вычислим вероятность того, что наблюдая такую сцены мы действительно видим динозавра
/45

Пример:
Какова вероятность увидеть на улице динозавра?
Идя по улице вы видите такую сцену:
Правдоподобие – вероятность того, что будь это действительно динозавр наблюдение было бы таким
Априорная вероятность встретить динозавра
(это и есть наблюдение X)
Вычислим вероятность того, что наблюдая такую сцены мы действительно видим динозавра
Априорная вероятность увидеть такую сцену
/45

Вероятностная формулировка задачи машинного обучения
Эмпирический риск:
Общий риск:
рассчитать невозможно
требуется минимизировать
Модель алгоритма и метод обучения определяются так же
/45

Пример расчёта вероятности
/45

Пример расчёта вероятности
/45

Пример расчёта вероятности
/45

Домашнее задание 1:
Пример расчёта вероятности
Пусть некий тест на какую-нибудь болезнь имеет вероятность успеха 95%
5% — вероятность как позитивной, так и негативной ошибки.
Всего болезнь имеется у 1% респондентов.
Пусть некий человек получил позитивный результат теста
тест говорит, что он болен.
С какой вероятностью он действительно болен?
Ответ на «Домашнее задание 3.1» разместить на странице курса.
/45

Наивный байесовский классификатор
Предположения:
Известна функция правдоподобия:
Известны априорные вероятности:
Принцип максимума апостериорной вероятности:
Вероятность класса
Вероятность наблюдения
Правдоподобие – условная вероятность наблюдения
Наи́вный ба́йесовский классифика́тор — простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими (наивными) предположениями о независимости.
Алгоритм:
Для каждой гипотезы вычислить апостериорную вероятность.
Выбрать гипотезу с максимальной апостериорной вероятностью
Эмпирический риск:
/45

Example. Play Tennis
x=(Sunny, Cool, High, Strong)
/45

Example. Learning.
P(Play=Yes) = 9/14
P(Play=No) = 5/14
/45

Example.Test
x=(Outlook=Sunny, Temperature=Cool, Humidity=High, Wind=Strong)
P(Outlook=Sunny|Play=No) = 3/5
P(Temperature=Cool|Play==No) = 1/5
P(Huminity=High|Play=No) = 4/5
P(Wind=Strong|Play=No) = 3/5
P(Play=No) = 5/14
P(Outlook=Sunny|Play=Yes) = 2/9
P(Temperature=Cool|Play=Yes) = 3/9
P(Huminity=High|Play=Yes) = 3/9
P(Wind=Strong|Play=Yes) = 3/9
P(Play=Yes) = 9/14
P(Yes|x) ≈ [P(Sunny|Yes)P(Cool|Yes)P(High|Yes)P(Strong|Yes)]P(Play=Yes) = 0.0053
P(No|x) ≈ [P(Sunny|No) P(Cool|No)P(High|No)P(Strong|No)]P(Play=No) = 0.0206
P(Yes|x) P(No|x)
Решение “No”.
Домашнее задание 3.2 – для указанного варианта определить вероятность благоприятного и неблагоприятного исхода, сделать вывод!
/45

Особенности наивного байесовского классификатора
Нужно знать функцию правдоподобия и априорные вероятности
Отсутствуют априорные причины верить, что одна из гипотез более вероятна чем другая (наивность)
Отвечает на вопрос – Какова наиболее вероятная гипотеза при имеющихся данных?
Надо ответить на вопрос – Какова наиболее вероятная классификации нового примера при имеющихся данных?
/45

Построение границы классов
/45

Разбиение пространства,
как задача классификации
Задача классификации: определить вектор x в один из K классов Y .
В итоге у нас так или иначе всё пространство разобьётся на эти классы.
Т.е. на самом деле мы ищем разделяющую поверхность (decision surface, decision boundary).
Рассмотрим линейную дискриминантную функцию:
/45

Разделение на несколько классов
Классифицируем в Yk если соответствующий yk – максимален
Можно рассмотреть поверхности вида «один против всех»
Можно рассмотреть поверхности вида «каждый против каждого»
Можно рассмотреть единый дискриминант из k линейных функций вида
/45

Задача линейной регрессии
Нужно найти функцию, которая отображает зависимость одних переменных или данных от других.
Зависимые данные называются зависимыми переменными, выходами или ответами.
Независимые данные называются независимыми переменными, входами или предсказателями.
Обычно в регрессии присутствует одна непрерывная и неограниченная зависимая переменная.
Входные переменные могут быть неограниченными, дискретными или категорическими данными
/45

Задача линейной регрессии
Через две точки на плоскости можно провести прямую и только одну
А если точек на плоскости – три и более?
Метод наименьших квадратов (МНК) состоит в том, чтобы найти такие коэффициенты регрессии, при которых достигается минимум следующего функционала качества на заданной обучающей выборки
/45

Scikit-learn
Библиотека Scikit-learn — самый распространённый выбор для решения задач классического машинного обучения.
Scikit-learn специализируется на алгоритмах машинного обучения для решения задач
обучения с учителем:
классификации (предсказание признака, множество допустимых значений которого ограничено)
регрессии (предсказание признака с вещественными значениями)
обучения без учителя:
кластеризации (разбиение данных по классам, которые модель определит сама),
понижения размерности (представление данных в пространстве меньшей размерности с минимальными потерями полезной информации)
детектирования аномалий.
/45

Scikit-learn
Вход-выход (x-y) (зелёные круги) – результаты наблюдений.
Оценочная функция регрессии (чёрная линия) выражается уравнением f(x) = b₀ + b₁x.
Предсказанные ответы (красные квадраты) – точки линии регрессии, соответствующие входным значениям.
Остатки (вертикальные пунктирные серые линии) – при реализации линейной регрессии минимизируется сумма квадратов расстояний.
/45

Пример: Ирисы Фишера
150 цветков трех классов:
Два параметра: длина чашелистика и длина лепестка.
Два новых цветка со следующими значениями длины чашелистика и лепестка: 5,3 и 1,6 (цветок 1), 6,1 и 4,8 (цветок 2).
Задание 1. Построить регрессию
/45

Метод «k-ближайших соседей». Классификатор
K-nearest neighbor – kNN
Метод решения задачи классификации, который относит объекты к классу, которому принадлежит большинство из k его ближайших соседей в многомерном пространстве признаков.
Число k – это количество соседних объектов в пространстве признаков, которое сравнивается с классифицируемым объектом.
Использование только одного ближайшего соседа (1NN) ведёт к ошибкам из-за:
нетипичных примеров
ошибок в ручной привязке единственного обучающего примера.
Более устойчивой альтернативой является k наиболее похожих примеров и определение большинства
Величина k типично нечётная: 3, 5
/45

1-Nearest Neighbor
/45

3-Nearest Neighbor
/45

Нормализация и вычисление расстояния
Расстояние Махаланобиса
Евклидово расстояние
Предложено индийским статистиком Махаланобисом в 1936 году. С помощью расстояния Махаланобиса можно определять сходство неизвестной и известной выборки. Оно отличается от расстояния Евклида тем, что учитывает корреляции между переменными и инвариантно к масштабу.
/45

Ирисы Фишера: Простое голосование
Класс цветка 1: Iris Setosa
/45

Ирисы Фишера: Простое голосование
Класс цветка 2: Iris Virginica
/45