cg2014_04_recognition (Раздаточные материалы)

Распознавание изображений имашинное обучениеАнтон КонушинSlides adapted from Fei-Fei Li, Rob Fergus, Antonio Torralba, Jean Ponce and Svetlana LazebnikЭвристические методы распознаванияСхема простого алгоритма выделения и распознавания объектовЧто было сложно?•Признаков может быть много (несколько моментов, площадь,положение, гистограммы яркости, каналов цвета и т.д.)Подбирать правила приходится вручную, много гипотез, когдапризнаков много и распределение сложно, это невозможно.Эксцентрисите т•10.90.80.70.60.50.40.30.20.10ШумЛожкиСахар020004000Площадь60008000Как должно быть в идеалеАлгоритм обученияОбученная машинаДанныеОтветВопросЧто такое машинное обучение?• Обучение ≠ «заучивание наизусть»• Заучить наизусть – для машины не проблема• Мы хотим научить машину делать выводы!• Машина должна корректно работать на новых данных,которые мы ей раньше не давали• По конечному набору обучающих данных машина должнанаучиться делать выводы на новых данныхМашинное обучение• Нейронные сети - Перспептрон (Розенблатт, 1958),когнитрон (Фукушима, 1975)• Обратное распространение ошибки (1980е)• Метод опорных векторов (1990е)• Бустинг (конец 1990х)• Рандомизированный решающий лес (начало 2000х)• «Глубинное обучение» (2006 и далее)• Мы рассмотрим «на пальцах» один метод – «методопорных векторов»Задача классификации образов••••Дано множество объектов, каждый из которых принадлежитодному из нескольких классов.

Нужно определить, какому классупринадлежит данный экземплярКаждый объект c номером j можно описать вектором признаков xjКаждому объекту можно приписать метку класса yjВсё множество известных наблюдений (конечное) можнозаписать в следующем виде:Каждое наблюдение (x,y) ещё называют прецедентомЗадача классификации образов•••Задача построить функцию y=f(x), которая для каждоговектора-признаков x даёт ответ y, какому классу принадлежитобъект xФункция f() назвается решающее правило или классификаторЛюбое решающее правило делит пространство признаков нарешающие регионы разделенные решающими границамиРешающаяграницаПространствопризнаковКлассификация•Будем выбирать функции ft из параметрическогосемейства F (т.е.

будем выбирать подходящий наборпараметров t)•Введем некоторую функцию потерь L(ft(x,t), y),• В случае классификации часто используют L ( f (x ), y )  I[ y  f ( x)],где f (x) - предсказанный класс• Можем использовать и другие функции потерь•Задача обучения состоит в том, чтобы найти наборпараметров t классификатора f, при котором потери дляновых данных будут минимальны•«Метод классификации» = параметрическое семейство F +алгоритм оценки параметров по обучающей выборкеОбщий риск• Общий риск – математическое ожидание потерь:=,,=,,,• Наша задача – найти такие параметры t, прикоторых общий риск минимален• Но общий риск рассчитать невозможно, посколькураспределение P для множества наших объектов(x,y) неизвестноЭмпирический риск• Дано X m  x1 , ..., xm  - обучающая выборка• Эмпирический риск (ошибка обучения):m1Remp  f , X m    L ( f ( xi ), yi )m i1• Метод минимизации эмпирического риска:f  arg min Remp  f , X m f FCмысл: подбираем параметры t решающегоправила f таким образом, чтобы эмпирический рискRemp был минималенЛинейная классификация• Рассмотрим случайлинейно разделимыхданныхДанные, с неизвестнымиответами• Только для 2х классов• Т.е.

таких, что вектора впространстве признаковможно отделить друг отдруга гиперплоскостьюОбучающаявыборкаЛинейный классификатор•Найдем линейную функцию (гиперплоскость) и разделимположительные {y=+1} и отрицательные {y=-1} примерыx i положитель ные :x i отрицатель ные :xi  w  b  0xi  w  b  0Для всехрассмотренныхплоскостейэмпирический рискодинаковыйКакаягиперплоскостьнаилучшая?Метод опорных векторов••Support Vector Machine (SVM)Найдем гиперплоскость, максимизирующую отступ междуположительными и отрицательными примерамиxi положитель ные ( yi  1) :xi отрицатель ные ( yi  1) :xi  w  b  1x i  w  b  1Для опорных векторов,x i  w  b  1Расстояние от точки догиперплоскости:| xi  w  b ||| w ||Поэтому отступ равенОпорные вектораОтступhttp://www.machinelearning.ru/wiki/index.php?title=SVM2 / ||w||Поиск гиперплоскости1.2.••Максимизируем отступ 2/||w||Правильно классифицируем все данные:x i позитивные ( yi  1) :xi  w  b  1x i негативные ( yi  1) :x i  w  b  1Квадратичная оптимизационная задача:МинимизируемПри условии•1 Tw w2yi(w·xi+b) ≥ 1Решается с помощью методом множителей Лагранжаhttp://www.machinelearning.ru/wiki/index.php?title=SVMПоиск гиперплоскости• Решение:w  i  i yi x iОбученныевесаОпорныевектора• Для большей части векторов вес = 0!• Все вектора, для которых вес >0 называютсяопорными• Определяется только опорными векторамиhttp://www.machinelearning.ru/wiki/index.php?title=SVMПоиск гиперплоскости•Решение:w  i  i yi x ib = yi – w·xi для любого опорного вектора•Решающая функция:w  x  b  i  i y i x i  x  b••Решающая функция зависит от скалярных произведений (innerproduct) от тестового вектора x и опорных векторов xiРешение оптимизационной задачи также требует вычисленияскалярных произведений xi · xj между всеми парами векторовиз обучающей выборкиhttp://www.machinelearning.ru/wiki/index.php?title=SVMРеальный случайВводим дополнительные «slack»переменные:Tξj  1 ,..., n ξin1 Tw w  C  iМинимизируем2i 1При условииyi ( wx i  b)  1  iС – параметр регуляризацииВ реальном случае идеально разделить данные невозможно(эмпирический риск всегда больше 0)Нелинейные SVM•На линейно разделимых данных SVM работает отлично:x0•Но на более сложных данных не очень:x0•Можно отобразить данные на пространство большей размерности иразделить их линейно там:x20xSlide credit: Andrew MooreНелинейные SVM• Идея: отображение исходного пространствапараметров на какое-то многомерное пространствопризнаков (feature space) где обучающая выборкалинейно разделима:Φ: x → φ(x)Slide credit: Andrew MooreНелинейные SVM••Вычисление скалярных произведений в многомерномпространстве вычислительно сложноThe kernel trick: вместо прямого вычисления преобразованияφ(x), мы определим ядровую функцию K:K(xi , xjj) = φ(xi ) · φ(xj)•Чтобы все было корретно, ядро должно удовлетворять условиюМерсера (Mercer’s condition)••Матрица K(xi,xj) должна быть неотрицательно определеннойС помощью ядра мы сможем построить нелинейную решающуюфункцию в исходном пространстве:  y K (x , x )  biiiiПример ядра• Полиномиальное:K ( x, y )  ((x, y )  c )d• Пусть d=2, x=(x1,x2):K ( x, y )  ((x, y )  c ) 2  ( x1 y1  x2 y2  c )2   ( x )   ( y )2122 ( x )  ( x , x , 2 x1 x2 , 2c x1 , 2c x2 , c )• Т.е.

из 2х мерного в 6и мерное пространствоSVM - резюме• Мощный и гибкий подход на основе ядер• Придумано много разных ядер• На практике работает очень хорошо, даже длямаленьких обучающих выборок• Много доступных библиотек:http://www.kernel-machines.org/softwareПредсказательная способность• Научились обучать классификатор SVM наобучающей выборке• Нам нужно, чтобы классификатор хорошо работал наданных, которые не использовались при обучении• «Предсказательная способность» - качествоклассификации вне обучающей выборки• Как оценить предсказательную способность?• Обучать на одной части известных данных,проверять на другой• «Удерживание»• «Скользящий контроль» (Cross-validation)ОтветОбщая идея• Будем разбивать имеющуюся обучающую выборкуна части• На одной части будем обучать классификатор(минимизировать эмпирический риск)• На другой будем измерять ошибки обученногоклассификатора (оценивать предстказательнуюспособность)1 cR( f , X ) ~ P  f ( x )  y | X     f ( x j )  y j c j 1cX k  x1 ,..., xk X1X2Свойства «удерживания»•Быстро и просторассчитывается•Некоторые «сложные»прецеденты могутполностью попасть в толькоодну из выборок и тогдаоценка ошибки будетсмещеннойОбучениеОшибка произойдет непо винеклассификатора, а из-заразбиения!КонтрольСкользящий контроль• Разделим выборку на d непересекающихся частейи будем поочередно использовать одно из нихдля контроля а остальные для тренировки• Разбиваем:X  : Xi d1i X j  0, i  jdikXXi 1• Приближаем риск:d1P ( f ( X k )  y*)   P ( f ( X i )  y * |  X i )d i 1i jИллюстрацияX k  x1 ,..., xk X1X2X3КонтрольОбучениеX4X5Результат считается каксредняяошибка по всемитерациямСвойства• В пределе равен общему риску• Каждый прецедент будет один раз присутствоватьв контрольной выборке• Обучающие выборки будут сильно перекрываться(чем больше сегментов, тем больше перекрытие)• Если одна группа «сложных прецедентов» попалаполностью в один сегмент, то оценка будет смещенной• Предельный вариант – “leave one out”• Обучаемся на всех элементах, кроме одного• Проверяем на одном• Повторяем для всех элементовПример•Данные – точки наплоскости•«Классификатор» – порогпо оси X 1, x1  a (x , x )   1, x1  1•2Будем обучать его,пользуясь разнымиподходами и измерятьошибки• Удерживание• Скользящий контрольУдерживаниеОшибка: 0.1133Тренировочная выборкаОшибка: 0.1433Контрольная выборкаРазобъём данные на 2 части, обучим на одной,проверим на другойСкользящий контроль: разбиениеРазобъём данные на 5 частейСкользящий контроль: измерениеОбучим и измерим ошибку 5 разСкользящий контроль• Тренировочная ошибка:• {0.1236 0.1208 0.1250• Среднее = 0.12190.10970.1306}0.17780.1000}• Ошибка на контроле• {0.1500 0.1333 0.1222• Среднее = 0.1367Ошибки I и II рода• В наших задачах обычно классы объектовнеравнозначны• Лицо человека – «основной» класс (положительныепримеры)• Фон – «вторичный» класс (отрицательные примеры)• Ошибка первого рода равна вероятностипринять основной класс за вторичный• Вероятность «промаха», когда искомый объект будетпропущен (пропустить лицо)• Ошибка второго рода равна вероятностипринять вторичный класс за основной• Вероятность «ложной тревоги», когда за искомый объектбудет принят «фон»Ошибки I и II родаОшибка II рода(ложные срабатывания)Построенная гипотезаИстинная гипотезаБудем считатькрасные точки«основным классом»Ошибка I рода(пропущенные объекты)Ошибки I и II рода• При анализе изображений классы обычнонесбалансированы• Объектов основного класса («лица») - мало• Объектов второго класса («фон») - много• Особенно важно оценивать ошибки I и II родараздельно при несбалансированности классов:• ПустьP ( y  1)  0.0000001; P( y  1)  0.9999999• Тогда при ошибке II рода 0 и ошибке I рода 0.5P ( f ( x)  1 | y  1)  0.5• Общая ошибка всего лишьP ( a( x )  y)  0.00000005Точность и полнота• Точность (Precision)• Доля истинных объектов основного класса среди всехклассифицированных, как основной класс• Полнота (Recall)• Доля правильно распознанных объектов основногокласса среди всех объектов основного класса изтестовой выборки• Интегральный показатель F (F-measure)• F=2××Точность и полнота• Полнота – 10 из 13, т.е.