«Введение в компьютерное зрение» Владимир Вежневец, Антон Конушин Александр Вежневец МГУ ВМК, Graphics & Media Lab, Осень 2006. - презентация

1 «Введение в компьютерное зрение» Владимир Вежневец, Антон Конушин Александр Вежневец МГУ ВМК, Graphics & Media Lab, Осень 2006

2 План лекции Деревья классификации Деревья классификации Байесовский подход к классификации Байесовский подход к классификации «Наивный» Байесовский классификатор (Idiot Bayes) «Наивный» Байесовский классификатор (Idiot Bayes) Нормальный дискриминантный анализ Нормальный дискриминантный анализ Нейронные сети Нейронные сети Метод опорных векторов Метод опорных векторов Комитетные методы Комитетные методы Bagging Bagging Boosting Boosting

3 Вопросы с предыдущей лекции Почему не рассказываем про обучение «на лету»? Почему не рассказываем про обучение «на лету»? Почему же скользящий контроль лучше повторного удерживания? Почему же скользящий контроль лучше повторного удерживания?

4 Обучение на лету Модель: Модель: Множество состояний S Множество состояний S Множество действий A Множество действий A Скалярный «выигрыш» r Скалярный «выигрыш» r В каждый момент времени t : В каждый момент времени t : Агент получает свое состояние Агент получает свое состояние и набор возможных действий и набор возможных действий Агент выбирает действие и получает «выигрыш» Агент выбирает действие и получает «выигрыш» Требуется максимизировать выигрыш Требуется максимизировать выигрыш Ясно, что выигрыш можно оптимизировать «жадно» и «дальне- срочно» - определяется задачей Ясно, что выигрыш можно оптимизировать «жадно» и «дальне- срочно» - определяется задачей

5 Особенности Нет готовых ответов, есть «запоздалый выигрыш » Нет готовых ответов, есть «запоздалый выигрыш » Требует от системы возможности постоянно получать отклик о качестве работы (выигрыш); Требует от системы возможности постоянно получать отклик о качестве работы (выигрыш); Зачастую, невозможное требование для коммерческих систем компьютерного зрения; Зачастую, невозможное требование для коммерческих систем компьютерного зрения; Применение Применение Игры; Игры; Робот в лабиринте; Робот в лабиринте; Частичная видимость среды; Частичная видимость среды; Для задач допускающих формулировку в виде задач обучения с учителем применение обучения «на лету» дает заведомо худший результат! Для задач допускающих формулировку в виде задач обучения с учителем применение обучения «на лету» дает заведомо худший результат!

6 Почему же скользящий контроль лучше повторного удерживания? Основной довод скользящего контроля: Основной довод скользящего контроля: Каждый элемент гарантированно попадет в контрольную выборку хотя бы один раз Каждый элемент гарантированно попадет в контрольную выборку хотя бы один раз Довод 5-2 контроля: Довод 5-2 контроля: Тренировочные выборки абсолютно декоррелированы (не пересекаются) Тренировочные выборки абсолютно декоррелированы (не пересекаются) Каждый прецедент учувствует в тренировке и контроля ровно по 5 раз Каждый прецедент учувствует в тренировке и контроля ровно по 5 раз

7 Почему же скользящий контроль лучше повторного удерживания? Вероятность пропустить хотя бы один прецедент при повторном удерживании: Вероятность пропустить хотя бы один прецедент при повторном удерживании: - доля прецедентов в контрольной выборке - доля прецедентов в контрольной выборке - количество прецедентов всего - количество прецедентов всего - количество итераций - количество итераций При При Вероятность, что прецеденты будут выбраны в равных долях еще меньше!!! Вероятность, что прецеденты будут выбраны в равных долях еще меньше!!!

8 Деревья классификации Classification trees

9 Деревья классификации Модель алгоритма Двоичное дерево Двоичное дерево Узлы: Узлы: Помечены некоторым предикатом Помечены некоторым предикатом Связи: Связи: Помечены Помечены Листья: Листья: Помечены ответами из Y Помечены ответами из Y *Вопрос: кто помнит, что такое предикат?

10 Деревья классификации Модель алгоритма Выходом классификатора является значение листа, полученного при обходе: Выходом классификатора является значение листа, полученного при обходе: Начинаем от корня Начинаем от корня Переходим в тот узел, в который ведет связь помеченная значением предиката в текущем узле Переходим в тот узел, в который ведет связь помеченная значением предиката в текущем узле Заканчиваем, попав в лист Заканчиваем, попав в лист

11 Пример ВАЖНО: каждый лист определяет собой область пространства Х

12 Деревья классификации Пример работы

13 Деревья классификации Модель алгоритма: пространство поиска Количество ветвлений - сильно влияет на сложность алгоритма и соответственно на размерность Вапника-Червоненкиса и склонность к переобучению Количество ветвлений - сильно влияет на сложность алгоритма и соответственно на размерность Вапника-Червоненкиса и склонность к переобучению Предикаты – обычно, используются пороги по проекциям на оси координат (на элементы вектора признаков) Предикаты – обычно, используются пороги по проекциям на оси координат (на элементы вектора признаков)

14 Деревья классификации Метод обучения Введем меру «неоднородности» для листа дерева Введем меру «неоднородности» для листа дерева Пусть, при обходе дерева до вершины m из тренировочной выборке «доходят» N m прецедентов; Пусть, при обходе дерева до вершины m из тренировочной выборке «доходят» N m прецедентов; Из них N m y прецедентов принадлежат классу y Из них N m y прецедентов принадлежат классу y Пусть, Пусть, Тогда «неоднородность» листа m - Тогда «неоднородность» листа m -

15 Деревья классификации Метод обучения Пусть, дана обучающая выборка Пусть, дана обучающая выборка Строим от корня: Строим от корня: Если текущая вершина однородная, то она лист; алгоритм останавливается Если текущая вершина однородная, то она лист; алгоритм останавливается Если же нет, делаем разбиение, минимизирующие «неоднородность» Если же нет, делаем разбиение, минимизирующие «неоднородность» Для каждой из получившихся вершин повторяем процедуру Для каждой из получившихся вершин повторяем процедуру

16 Особенности Плюсы Плюсы Просто и наглядно Просто и наглядно Легко анализируемо Легко анализируемо Быстро работает Быстро работает Легко применяется для задач со множеством классов и к регрессии Легко применяется для задач со множеством классов и к регрессии Минусы Минусы Плохо аппроксимирует сложные поверхности Плохо аппроксимирует сложные поверхности В общем случае, требует сложных алгоритмов «обрезания» для контроля сложности В общем случае, требует сложных алгоритмов «обрезания» для контроля сложности

17 Иллюстрация Верный источник как Недо- так пере-обучения!

18 Байесовская стратегия классификации Bayesian classification

19 Статистическая формулировка Пусть – вероятностное пространство Пусть – вероятностное пространство Пусть мера пространства P Пусть мера пространства P Множество прецедентов выбрано случайно и независимо согласно распределению P (случайная выборка); для них известны ответы Множество прецедентов выбрано случайно и независимо согласно распределению P (случайная выборка); для них известны ответы Требуется построить отображение Требуется построить отображение

20 Статистическая формулировка Бинарная классификация Эмпирический риск: Эмпирический риск: Общий риск: Общий риск: рассчитать невозможно рассчитать невозможно требуется минимизировать требуется минимизировать

21 Байесовский классификатор Предположения: Предположения: Известна функция правдоподобия: Известна функция правдоподобия: Известны априорные вероятности: Известны априорные вероятности: Принцип максимума апостериорной вероятности: Принцип максимума апостериорной вероятности: Вероятность класса Вероятность наблюдения Правдоподобие – условная вероятность наблюдения Формула Байеса

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

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

24 Свойства классификатора Модель алгоритма и метод обучение строго не определены (не нужны даже обучающая выборка) – классификатор строится непосредственно по функциям априорных вероятностей и правдоподобия данным «свыше» Модель алгоритма и метод обучение строго не определены (не нужны даже обучающая выборка) – классификатор строится непосредственно по функциям априорных вероятностей и правдоподобия данным «свыше» Дает наименьший общий риск (состоятелен) при выполнении предположений Дает наименьший общий риск (состоятелен) при выполнении предположений

25 Практическое применение На практике, функция правдоподобия и априорные вероятности обычно не известны; На практике, функция правдоподобия и априорные вероятности обычно не известны; Для применения Байесвокого подхода на практике требуется каким либо образом их оценить Для применения Байесвокого подхода на практике требуется каким либо образом их оценить Зачастую, предполагается что объекты принадлежат какому- то статистическому распределению, параметры которого оцениваются на обучающей выборке; Зачастую, предполагается что объекты принадлежат какому- то статистическому распределению, параметры которого оцениваются на обучающей выборке; Априорные оценки так же вычисляются на обучающей выборке Априорные оценки так же вычисляются на обучающей выборке

26 «Наивный» Байесовский классификатор Пусть, множество X является конечным Пусть, множество X является конечным Множество цветов в системе RGB Множество цветов в системе RGB Набор логических атрибутов (наличие в письме того или иного слова) Набор логических атрибутов (наличие в письме того или иного слова) Для каждого значения из X по обучающей выборке оценим функцию правдоподобия Для каждого значения из X по обучающей выборке оценим функцию правдоподобия Так же, оценим априорную вероятности Так же, оценим априорную вероятности

27 «Наивный» Байесовский классификатор Сегментация кожи Для всех возможных цветов по обучающей выборке строится таблица правдоподобия и рассчитывается априорная вероятность Для всех возможных цветов по обучающей выборке строится таблица правдоподобия и рассчитывается априорная вероятность

28 Нормальный дискриминантный анализ Normal discriminant analyzes

29 Нормальный дискриминантный анализ Предположения: Предположения: Функции правдоподобия имеют нормальное распределение: Функции правдоподобия имеют нормальное распределение: Дана обучающая выборка прецедентов (случайных и независимых) Дана обучающая выборка прецедентов (случайных и независимых)

30 Нормальное распределение Поверхность, на которой точки имеют равную вероятность представляет собой эллипсоид Поверхность, на которой точки имеют равную вероятность представляет собой эллипсоид Мат. ожидание – центр эллипса, ковариационная матрица – матрица поворота и растяжения (задает оси эллипса) Мат. ожидание – центр эллипса, ковариационная матрица – матрица поворота и растяжения (задает оси эллипса)

31 Расчет разделяющей поверхности Обозначим: Обозначим: Запишем уравнение разделяющей поверхности (на этой поверхности вероятности равны): Запишем уравнение разделяющей поверхности (на этой поверхности вероятности равны): Распишем: Распишем: С=const(x)

32 Расчет разделяющей поверхности

33 Поверхность становится квадратичной!

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

35 Метод обучения Для построения классификатора требуется по обучающей выборке оценить параметры распределений Для построения классификатора требуется по обучающей выборке оценить параметры распределений С учётом их случайности и независимости, можно применять стандартный механизм оценки параметров из математической статистики С учётом их случайности и независимости, можно применять стандартный механизм оценки параметров из математической статистики Например, метод максимального правдоподобия Например, метод максимального правдоподобия

36 Свойства классификатора В случае точной оценки параметров распределений и априорных вероятностей является Байесовским (дает минимум общего риска); В случае точной оценки параметров распределений и априорных вероятностей является Байесовским (дает минимум общего риска); Строит простую для вычисления поверхность (линейную или квадратичную); Строит простую для вычисления поверхность (линейную или квадратичную); Делает сильное предположение о нормальности распределений Делает сильное предположение о нормальности распределений В случае невыполнения предположений даёт непредсказуемый результат В случае невыполнения предположений даёт непредсказуемый результат

37 Советы по практическому применению Проверить классы на нормальность! Проверить классы на нормальность! Хи-квадрат статистика Хи-квадрат статистика В случае наличия выбросов использовать робастные оценки В случае наличия выбросов использовать робастные оценки MLESAC MLESAC Аккуратно оценить априорные вероятности Аккуратно оценить априорные вероятности

38 Развитие метода Обобщение на множество классов Обобщение на множество классов Введение риска Введение риска

39 Нейронные сети Neural Networks

40 Нейоронные сети Предпосылка: Предпосылка: Известно, что биологические системы (люди, животные) прекрасно справляются со сложными задачами распознавания образов; Известно, что биологические системы (люди, животные) прекрасно справляются со сложными задачами распознавания образов; Основная идея: Основная идея: Применить знания о работе мозга (людей, животных) для решения задач распознавания образов; Применить знания о работе мозга (людей, животных) для решения задач распознавания образов;

41 Биологические нейронные сети гг гг. Понятие нейрона и нейронной сети; Понятие нейрона и нейронной сети; Первые предположения о принципе работы; Первые предположения о принципе работы;

42 Биологический нейрон

43

44 Биологический нейрон Передача импульса Дендриты Например, могут быть присоединены к рецепторам Аксон Может быть присоединен к мышцам

45 Нейронная сеть Совокупность соединенных между собой нейронов; Совокупность соединенных между собой нейронов; Сеть осуществляет преобразование входного сигнала с рецепторов в выходной, являющейся реакцией организма на внешнюю среду Сеть осуществляет преобразование входного сигнала с рецепторов в выходной, являющейся реакцией организма на внешнюю среду

46 Модель кибернетического нейрона McCulloch, W. and Pitts, W. (1943) Входной сигнал Синаптические веса Блок суммирования Блок преобразования Выходной сигнал

47 Персептрон Розенблата Модель алгоритма Входной сигнал Слой нейронов Функция преобразования - линейная Порог Выходной сигнал Кибернетический нейрон Rosenblatt (1962) *Вопрос: зачем x 0 ?

48 Персептрон Розенблата Модель алгоритма Свойства Свойства Линейная классификация Линейная классификация Легко обобщается на множество классов Легко обобщается на множество классов ?

49 Персептрон Розенблата Метод обучения Пусть дана обучающая выборка Пусть дана обучающая выборка Пусть, матрица есть матрица весов, где элемент есть вес связи нейрона j и входа i Пусть, матрица есть матрица весов, где элемент есть вес связи нейрона j и входа i Проинициализируем, случайными малыми значениями Проинициализируем, случайными малыми значениями Для Для Пусть, на входной образ сеть дает ответ Пусть, на входной образ сеть дает ответ Вычисляем ошибку Вычисляем ошибку Правим веса Правим веса Повторяем, пока ошибка не будет меньше некоторого малого числа Повторяем, пока ошибка не будет меньше некоторого малого числа

50 Персептрон Розенблата Метод обучения Особенности обучения Особенности обучения Прецеденты выучиваются по очереди Прецеденты выучиваются по очереди Оптимизируется эмпирический риск Оптимизируется эмпирический риск Процесс сходится к некоторому локальному минимуму Процесс сходится к некоторому локальному минимуму Зависит от начальной точки Зависит от начальной точки

51 Многослойный персептрон Rumelhart et al. (1986)

52 Настройка методом обратного распространения ошибки Основная идея Ошибку на последнем слое можно рассчитать явно Ошибку на последнем слое можно рассчитать явно Ошибку на промежуточном слое, распространим с последнего с текущими весами Ошибку на промежуточном слое, распространим с последнего с текущими весами Фактически, сеть запускается «наоборот» и вместо сигнала распространяется ошибка Фактически, сеть запускается «наоборот» и вместо сигнала распространяется ошибка Для её минимизации применяется градиентный спуск Для её минимизации применяется градиентный спуск Подробнее Подробнее

53 Многослойный персептрон Rumelhart et al. (1986) Производная ошибки по весу

54 Проблема локальных минимумов Идеальный классификатор (глобальный минимум) Локально оптимальны классификатор (локальный минимум)

55 Особенности Плюсы Плюсы Универсальность Универсальность Возможность решать задачи со множеством классов, регрессии и т.д. Возможность решать задачи со множеством классов, регрессии и т.д. Высокая степень параллельности Высокая степень параллельности Почти неограниченный простор для модификаций Почти неограниченный простор для модификаций Минусы Минусы Грубая минимизация эмпирического риска Грубая минимизация эмпирического риска Проблема локальных минимумов Проблема локальных минимумов Очень большая склонность к переобучению Очень большая склонность к переобучению

56 Где почитать подробней: Вежневец А. «Популярные нейросетевые архитектуры» сетевой журнал «Графика и Мультимедиа» Вежневец А. «Популярные нейросетевые архитектуры» сетевой журнал «Графика и Мультимедиа» Вежневец А. «Нестандартные нейросетевые архитектуры» сетевой журнал «Графика и Мультимедиа» Вежневец А. «Нестандартные нейросетевые архитектуры» сетевой журнал «Графика и Мультимедиа» Ресурс Сергея Терехова посвященный нейронным сетям Ресурс Сергея Терехова посвященный нейронным сетям

57 Нейронные сети Практическое применение В свое время, пользовались большой популярностью за счет универсальности и простоты применения (фактически, первое семейство универсальных методов) В свое время, пользовались большой популярностью за счет универсальности и простоты применения (фактически, первое семейство универсальных методов) Фактически, нейронной сети можно было скормить все что угодно и она что-то выдавала Фактически, нейронной сети можно было скормить все что угодно и она что-то выдавала Однако, нейронные сети во многом являются «дилетантским» подходом к машинному обучению и с точки зрения теории (и экспериментальных замеров) представляют собой очень ненадежный и неточный механизм Однако, нейронные сети во многом являются «дилетантским» подходом к машинному обучению и с точки зрения теории (и экспериментальных замеров) представляют собой очень ненадежный и неточный механизм

58 Метод опорных векторов Support Vector Machine

59 SVM 1. Максимизация отступа Прямых, разделяющих точки, может быть множество А почему бы не брать ту, которая равно и максимально удалена от обоих классов?

60 SVM 2. Опорные вектора Измениться ли разделяющая поверхность? Прецеденты, которые нельзя убрать без изменения поверхности

61 SVM Случай линейной разделимости Задача формулируется как поиск гиперплоскости максимально от выпуклой оболочки классов Задача формулируется как поиск гиперплоскости максимально от выпуклой оболочки классов Как выяснилось, такую гиперплоскость всегда можно записать в виде линейной комбинации «опорных векторов» - прецедентов, принадлежащих выпуклой оболочке Как выяснилось, такую гиперплоскость всегда можно записать в виде линейной комбинации «опорных векторов» - прецедентов, принадлежащих выпуклой оболочке

62 SVM Случай линейной разделимости Задачу поиска такой гиперплоскости можно записать как задачу оптимизации: Задачу поиска такой гиперплоскости можно записать как задачу оптимизации: Чисто геометрическая задача Глобальный минимум находится методом квадратичного программирования

63 SVM Случай линейной разделимости Плюсы Плюсы Глобальный минимум Глобальный минимум Теоретически доказана минимальность оценки общего риска (Вапник) Теоретически доказана минимальность оценки общего риска (Вапник) Требует знания только скалярных произведений Требует знания только скалярных произведений Минусы Минусы Работает только для линейно разделимых классов Работает только для линейно разделимых классов

64 SVM Случай шума Просто переформулируем оптимизационную задачу, допустив ошибку, но штрафуя за неё: Просто переформулируем оптимизационную задачу, допустив ошибку, но штрафуя за неё: Регулирует баланс точности и толерантности

65 SVM Случай нелинейной разделимости

66 Идея «ядровых» преобразований: Идея «ядровых» преобразований: Отобразить данные в пространство, в котором разделяющая поверхность будет линейной (или близкой к линейной) Отобразить данные в пространство, в котором разделяющая поверхность будет линейной (или близкой к линейной) Ядровые преобразования можно быстро вычислять для скалярных произведений, даже при бесконечной размерности целевого пространства Ядровые преобразования можно быстро вычислять для скалярных произведений, даже при бесконечной размерности целевого пространства

67 SVM Плюсы Плюсы Однозначность решения (глобальный минимум) Однозначность решения (глобальный минимум) Теоретически доказана минимальность оценки общего риска (Вапник) Теоретически доказана минимальность оценки общего риска (Вапник) При помощи ядровых преобразований обобщается на случай сложных поверхностей При помощи ядровых преобразований обобщается на случай сложных поверхностей Минусы Минусы Требует подбора множества параметров (ядро, параметры ядра, штраф за ошибки) Требует подбора множества параметров (ядро, параметры ядра, штраф за ошибки) Теор. оценки верны только для случая разделимости (схема со штрафами - эвристика) Теор. оценки верны только для случая разделимости (схема со штрафами - эвристика) Очень чувствителен к нормализации данных! Очень чувствителен к нормализации данных!

68 SVM Практическое применение Метод являлся наилучшим методом классификации до, примерно, 2000 года наголову обгоняя нейронные сети и т.п. Метод являлся наилучшим методом классификации до, примерно, 2000 года наголову обгоняя нейронные сети и т.п. Фактически, метод опорных векторов – практический выход теории Вапника-Червоненкиса Фактически, метод опорных векторов – практический выход теории Вапника-Червоненкиса Однако, необходимость подбора большого числа не интуитивных параметров сильно снижала его применение в простых разработках (требовала наличия эксперта) Однако, необходимость подбора большого числа не интуитивных параметров сильно снижала его применение в простых разработках (требовала наличия эксперта)

69 Коммитетные методы Classifier ensembles

70 Подсказка зала Когда родился Ленин? (по новому стилю) Когда родился Ленин? (по новому стилю) 19 апреля 19 апреля 7 ноября 7 ноября 22 апреля 22 апреля 19 мая 19 мая

71 Основная идея Если взять множество правил (экспертов), с некоррелированной ошибкой (ошибаются в разных местах), то их комбинация может быть работать во много раз лучше Если взять множество правил (экспертов), с некоррелированной ошибкой (ошибаются в разных местах), то их комбинация может быть работать во много раз лучше

72 Bagging (Bootstrapped aggregation) Пусть, дана обучающая выборка Пусть, дана обучающая выборка Пусть дан метод обучения Пусть дан метод обучения На каждом шаге: На каждом шаге: Выберем из выборке выборку из т прецедентов, но с повторениями (один прецедент может попасть в выборку несколько раз); Выберем из выборке выборку из т прецедентов, но с повторениями (один прецедент может попасть в выборку несколько раз); Натренируем некоторый классификатор Натренируем некоторый классификатор Повторим предыдущие шаги несколько раз Повторим предыдущие шаги несколько раз Финальный классификатор построим по схеме голосования Финальный классификатор построим по схеме голосования

73 Bagging (Bootstrapped aggregation) Эффективно повышает качество обучения при нестабильности метода обучения Эффективно повышает качество обучения при нестабильности метода обучения В случае стабильности, может понизить качество за счет искажения истинного распределения выборки В случае стабильности, может понизить качество за счет искажения истинного распределения выборки

74 Weak learners Boosting Основная идея: Основная идея: Последовательно производить поиск элементов Т, которые сложнее классифицировать. Последовательно производить поиск элементов Т, которые сложнее классифицировать. На каждой итерации выделять правила для классификации именно этих «сложных» элементов. На каждой итерации выделять правила для классификации именно этих «сложных» элементов. Скомбинировать полученные на каждой итерации правила. Скомбинировать полученные на каждой итерации правила. Требует только, чтобы базовые методы классификации были немного лучше гадания. Требует только, чтобы базовые методы классификации были немного лучше гадания.

75 Пример хорошего классификатора

76 Итерация 1 из D2D2 1 = =0.424 h1h1

77 Итерация 2 из D2D2 h2h2 2 = =0.704

78 Итерация 3 из h3h3 3 = =0.323 СТОП

79 Конечная гипотеза

80 Проинициализируем D 1 (i) = 1/m Ошибка h t рассчитывается с учётом D t 1. Обучим h k с минимальной ошибкой 2. Рассчитаем вес гипотезы 3. Для всех i = 1 to m Результат: Вес Adaптируется. Чем больше k тем меньше k Z t нормализующий коэф. AdaBoost (Discreet) Усилем пример если на нём ошибка Линейная комбинация Пусть T: (x 1, y 1 ), …, (x m, y m ) где Для Пусть есть набор {h} – слабых классификаторов

81 AdaBoost на пальцах На каждой итерации мы используем некоторый метод обучения, так чтобы он выдал гипотезу которая минимизирует ошибку с учётом «важности» примеров На каждой итерации мы используем некоторый метод обучения, так чтобы он выдал гипотезу которая минимизирует ошибку с учётом «важности» примеров Мы выбираем тот классификатор, который на данном шаге сделал наименьшую ошибку, с учётом «важности» прецедентов (распределение) Мы выбираем тот классификатор, который на данном шаге сделал наименьшую ошибку, с учётом «важности» прецедентов (распределение) Составляем Л.К. всех отобранных классификаторов Составляем Л.К. всех отобранных классификаторов Был рассказан самый примитивный алгоритм, но концептуально идея всех методов Boosting такова Был рассказан самый примитивный алгоритм, но концептуально идея всех методов Boosting такова

82 AdaBoost (пороги)

83 Эмпирический риск Как показали Freund и Schapire Как показали Freund и Schapire Эмпирический риск падает по экспоненте – высокая скорость обучения Эмпирический риск падает по экспоненте – высокая скорость обучения

84 Общий риск Опираясь на результаты Baum и Haussler, Freund и Schapire показали, что почти наверное Опираясь на результаты Baum и Haussler, Freund и Schapire показали, что почти наверное Таким образом, общий риск зависит только от слабого классификатора, которая мала Таким образом, общий риск зависит только от слабого классификатора, которая мала

85 Boosting Плюсы Плюсы Универсальность Универсальность Высокая скорость сходимости Высокая скорость сходимости Высокая обобщающая способность Высокая обобщающая способность Возможность очень эффективной программной реализации и распараллеливания Возможность очень эффективной программной реализации и распараллеливания Простота метода и отсутствия параметров Простота метода и отсутствия параметров Минусы Минусы Трудность определения нужного числа итераций обучения (зачастую, ошибка на контроле продолжает падать и после нуля эмпирического риска) Трудность определения нужного числа итераций обучения (зачастую, ошибка на контроле продолжает падать и после нуля эмпирического риска)

86 Конец Были использованы материалы Lecture slides for «Introduction to Machine Learning» ETHEM ALPAYDIN © The MIT Press, 2004 Lecture slides for «Introduction to Machine Learning» ETHEM ALPAYDIN © The MIT Press, 2004 Слайды доклада «Supervised Learning of Edges and Object Boundaries» Piotr Dollár, Zhuowen Tu, Serge Belongie Слайды доклада «Supervised Learning of Edges and Object Boundaries» Piotr Dollár, Zhuowen Tu, Serge Belongie «Short introduction to boosting» Rob Schapire «Short introduction to boosting» Rob Schapire Wikipedia Wikipedia