Что такое машинное обучение? • Обучение ? «заучивание наизусть». • Заучить наизусть – для машины не проблема • Мы хотим научить машину делать выводы! •


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
Машинное обучение Slides dpted from Fei - Fei Li, Rob Fergus, Antonio Torrlb , Jen Ponce nd Svetln Lzebnik Антон Конушин Проблемы распознавания • Признаков может быть много (несколько моментов, площадь, положение, гистограммы яркости, каналов цвета и т.д.) • Подбирать правила приходится вручную, много гипотез, когда признаков много и распределение сложно, это невозможно. 0 0. 0.2 0.3 0.4 0.5 0.6 0.7 0. 0.9  0 2000 4000 6000 000 Эксцентриситет Площадь Шум Ложки Сахар Геометрические признаки для выделенных сегментов Как должно быть в идеале Данные Алгоритм обучения Обученная машина Ответ Вопрос Что такое машинное обучение? • Обучение  «заучивание наизусть • Заучить наизусть – для машины не проблема • Мы хотим научить машину делать выводы! • Машина должна корректно работать на новых данных, которые мы ей раньше не давали • По конечному набору обучающих данных машина должна научиться делать выводы на новых данных Машинное обучение История: • Нейронные сети - Перспептрон ( Розенблатт , 95), Когнитрон ( Фукушима , 975) • Метод опорных векторов (990е) • Бустинг (конец 990х ) • Рандомизированный решающий лес (начало 2000х) • Обучение Марковских случайных полей (2000е) • Глубокое обучение (2006) Нам придётся знакомиться с методами распознавания образом и машинного обучения для изучение современных алгоритмов компьютерного зрения Некоторые понятия из теории вероятностей Теория вероятностей • Frequentist interprettion of probbilities : • Вероятность = частота повторяемого события • Byesin interprettion of probbilities: • Вероятность = мера неопределенности исхода эксперимента Теория вероятностей • Эксперимент : • выбираем коробку • вынимаем оттуда фрукт • кладем его обратно • Две случайные величины : • X: отвечает за цвет коробки • Y: отвечает за то, какой фрукт нам попался (апельсин или яблоко) Теория вероятностей • Будем проводить такие эксперименты и заносить число исходов в таблицу • Вероятность пересечения событий • Условная вероятность Формула Байеса Идя по улице вы видите такую сцену: (это и есть наблюдение X ) Вычислим вероятность того, что наблюдая такую сцены мы действительно видим динозавра Y : Формула Байеса ( ) ) ( ) ( ) | ( |  P y P y  P  y P  = Какой процент динозавров выглядит так? вероятность встретить динозавра вероятность увидеть такую сцену Формула Байеса Идя по улице вы видите такую сцену: (это и есть наблюдение Y ) Вероятность того, что наблюдая такую сцену, мы действительно видим динозавра Y : Полезные соотношения • Полезные соотношения: • правило суммы • правило произведения • правило Байеса • если две случайные величины независимы, то Задача классификации образов • Дано множество объектов, каждый из которых принадлежит одному из нескольких классов. Нужно определить, какому классу принадлежит данный экземпляр • Каждый объект c номером  можно описать вектором признаков   • Каждому объекту можно приписать метку класса y  • Всё множество известных наблюдений (конечное) можно записать в следующем виде: Каждое наблюдение ( ,y ) ещё называют прецедентом Задача классификации образов • Задача построить функцию y=f() , которая для каждого вектора - признаков  даёт ответ y , какому классу принадлежит объект  • Функция f() назвается решающее правило или классификатор • Любое решающее правило делит пространство признаков на решающие регионы разделенные решающими границами Решающее правило Другие постановки: регрессия • Дана обучающая выборка • Каждому объекту  соответствует вещественное число y • Цель : построить функцию f() , которая для всех новых  даёт оценку y • Задача интерполяции / экстраполяции X , ii yYY = m (,)R×R ( ) ( ) { }  ,, mmm Xyy = ,..., Y Другие постановки: кластеризация • Дана обучающая выборка • Все объекты  i независимы и взяты из некоторого неизвестного распределения P() • Разбить множество объектов на классы (кластеры) на основе некоторой меры сходства объектов и для каждого  оценить P() i  m R { }  mm X = ,..., X 2 X  Другие постановки: кластеризация X 2 X  • Дана обучающая выборка • Все объекты  i независимы и взяты из некоторого неизвестного распределения P() • Разбить множество объектов на классы (кластеры) на основе некоторой меры сходства объектов и для каждого  оценить P() i  m R { }  mm X = ,..., Классификация • Будем выбирать функции f t из параметрического семейства F (т.е. будем выбирать подходящий набор параметров t ) • Введем некоторую функцию потерь L( f t (), y) , • В случае классификации часто используют ,где - предсказанный класс • Можем использовать и другие функции потерь • Задача обучения состоит в том, чтобы найти набор параметров классификатора f , при котором потери для новых данных будут минимальны • «Метод классификации = параметрическое семейство F  алгоритм оценки параметров по обучающей выборке ((),)() LfyIyf =  () f  Общий риск • Общий риск – математическое ожидание потерь: • рассчитать невозможно, поскольку распределение P неизвестно ( ) ( ) , ()(),((),) y RfLfyLfydP ==    Эмпирический риск • Дано - обучающая выборка • Эмпирический риск (ошибка обучения): • Метод минимизации эмпирического риска: C мысл: подбираем параметры t решающего правила f таким образом, чтобы эмпирический риск R emp был минимален { } m X = m ,..., ( )   ,((),) m m empii i RfXLfy m = =  ( ) rgmin, m emp fF fRfX  = Статистические основы • Почему принцип минимизации эмпирического риска работает? • Нас интересует качество работы алгоритма на неизвестных данных («предсказание • надо связать имеющиеся данные с теми, которые придется обрабатывать в будущем • Выход: использование теории вероятностей и мат. статистики • Значения признаков, внутренние состояния системы считаем случайными величинами • Будем считать, что имеющиеся данные и данные, которые придется обрабатывать в будущем одинаково распределены Обучающая выборка Данные, с неизвестными ответами Замечание • Гипотез, имеющих нулевой эмпирический риск может также существовать неограниченное количество: Наиболее общая гипотеза Наиболее частная гипотеза Золотая середина? Простой эксперимент • Искусственный пример: задача регрессии • На самом деле , - нормально распределенный шум • Но мы этого не знаем • Есть обучающая выборка, требуется восстановить зависимость Простой эксперимент • Будем выбирать целевую зависимость среди параметризованного множества - полиномов порядка M • Введем функция потерь • Среди множества полиномов будем выбирать тот, который приносит наименьшие суммарные потери на обучающей выборке ( минимальный эмпирический риск ) Простой эксперимент Простой эксперимент Простой эксперимент Что будет, если мы воспользуемся полиномом 9ой степени? Простой эксперимент Какой эмпирический риск и какой общий риск? Простой эксперимент Простой эксперимент Видим, что есть некоторая связь между сложностью параметрического семейства (количеством параметров) и размером обучающей выборки Явление переобучения • При уменьшении эмпирического риска с определенного момента может наблюдаться увеличение общего риска (уменьшением предсказательной способности) • Причина – гипотеза хорошо описывает свойства не объектов в целом, но только лишь объектов из обучающей выборки: • Слишком много степеней свободы параметров модели алгоритма (слишком сложная модель) • Шум в данных • Плохая обучающая выборка Теория Вапника - Червоненкиса • Теория, предложенная русским математиком Владимиром Вапником , для оценки обобщающей способности алгоритмов • Основные результаты теории: • Оценка сложности (емкости) параметрического семейства функций • Оценка качества алгоритма через эмпирический риск и сложность модели Принцип структурной минимизации риска • Основная идея - «Выбрать модель наиболее простую из достаточно точных • Пусть есть последовательность вложенных параметрических семейств возрастающей сложности • Выберем семейство с минимальной сложностью, но обеспечивающее нужную точность 2 ... h FFFF = Практический вывод из VC теории • Требуется баланс между сложностью модели, обеспечивающей низкий эмпирический риск и простотой, обеспечивающей способность к обобщению • Как нам оценить предсказательную способность алгоритма? Оценка общего риска • Общий риск: • Его минимизация для нас является основной целью • Однако, напрямую его посчитать невозможно (требует вычислений на неограниченном множестве) ( )   (,)()()() m X X RfXPfyPfyd ==  Удерживание • Оценим общий риск ошибкой на некотором конечном подмножестве X не пересекающимся с обучающей выборкой: ( )   (,)~()|() c c   RfXPfyXfy c =  =   Удерживание • Пусть, имеется набор данных с известными ответами • Разобьем • Будем использовать для обучения , а для контроля • То есть: { } k k   X ,...,  = 0 : = = c l k c l X X X X X   l X c X ( ) (())()| c PfyPfyX  Характеристики «удерживания • Быстро и просто рассчитывается • Некоторые «сложные прецеденты могут полностью попасть в только одну из выборок и тогда оценка ошибки будет смещенной Контроль Обучение Ошибка произойдет не по вине классификатора, а из - за разбиения! Скользящий контроль • D - fold cross - vlidtion • Разделим выборку на d непересекающихся частей и будем поочередно использовать одно из них для контроля а остальные для тренировки • Разбиваем: • Приближаем риск: { } k d i i  i d i X X  i X X X    , 0 : = =  =    i i d i i k X y X f P d y X f P  =   =  ) | ) ( (  *) ) ( ( *  Иллюстрация { } k k   X ,...,  = Контроль Обучение 2 X 3 X 5 X 4 X  X Результат считается как средняя ошибка по всем итерациям Свойства • В пределе равен общему риску • Каждый прецедент будет один раз присутствовать в контрольной выборке • Обучающие выборки будут сильно перекрываться (чем больше сегментов, тем больше перекрытие) • Если одна группа «сложных прецедентов попала полностью в один сегмент, то оценка будет смещенной • Предельный вариант – leve one out” • Обучаемся на всех элементах, кроме одного • Проверяем на одном • Повторяем для всех элементов 5 - 2 контроль • 5 - 2 с ross - vlidtion • Некоторый компромисс: • Разделим выборку случайным образом пополам • Обучим на одной половине, протестируем на другой, и наоборот • Повторим этот эксперимент пять раз и усредним результат • Свойства: • Каждый из прецедентов будет учувствовать в контрольных выборках на каждом из 5 этапов Вернёмся к классификации и посмотрим один из методов Парадигмы машинного обучения • Воспроизводящий подход (genertive pproch) • Используем формулу Байеса • моделируем каждый класс отдельно, для этого оцениваем • подход основан на идее вероятностного моделирования • постановка задачи напоминает кластеризацию • Дискриминантный подход (discrimintive pproch) • нас интересует , ее и будем оценивать • постановка задачи напоминает регрессию • Можем решать и более узкую задачу – rg m P( y| ) ( ) | Py ( ) |,() PyPy ( ) (|)() | () PyPy Py P  = Линейная классификация • Рассмотрим случай линейно разделимых данных • Только для 2х классов • Т.е. таких, что вектора в пространстве признаков можно отделить друг от друга гиперплоскостью Обучающая выборка Данные, с неизвестными ответами Линейный классификатор • Найдем линейную функцию (гиперплоскость) и разделим положительные {y=} и отрицательные {y= - } примеры 0 : 0 :       b ные отрицатель b ные положитель i i i i w   w   Какая гиперплоскость наилучшая ? Линейный классификатор • Найдем линейную функцию (гиперплоскость) и разделим положительные {y=} и отрицательные {y= - } примеры 0 : 0 :       b ные отрицатель b ные положитель i i i i w   w   Какая гиперплоскость наилучшая ? Для всех рассмотренных плоскостей эмпирический риск одинаковый Метод опорных векторов (SVM ) • Support Vector Mchine (SVM) • Найдем гиперплоскость, максимизирующую отступ между положительными и отрицательными примерами C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 Метод опорный векторов • Найдем гиперплоскость, максимизирующую отступ между положительными и отрицательными примерами  : ) (  : ) ( -    - =    = b y ные отрицатель b y ные положитель i i i i i i w   w   Отступ Опорные вектора C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 Расстояние от точки до гиперплоскости : || || | | w w  b i   Для опорных векторов ,   =   b i w  Поэтому отступ равен 2 / || w || Поиск гиперплоскости . Максимизируем 2/|| w || 2. Правильно классифицируем все данные : • Квадратичная оптимизационная задача : • Минимизируем При условии y i ( w ·  i  b ) ≥  • Решается с помощью методом множителей Лагранжа C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 w w T 2   : ) (  : ) ( -    - =    = b y ные отрицатель b y ные положитель i i i i i i w   w   Поиск гиперплоскости • Решение : • Для большей части векторов вес = 0! • Все вектора, для которых вес 0 называются опорными • Определяется только опорными векторами  = i i i i y  w  C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 Опорные вектора Обученные веса Поиск гиперплоскости • Решение : b = y i – w ·  i для любого опорного вектора • Решающая функция : • Решающая функция зависит от скалярных произведений (inner product) от тестового вектора  и опорных векторов  i • Решение оптимизационной задачи также требует вычисления скалярных произведений  i ·   между всеми парами векторов из обучающей выборки  = i i i i y  w  C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 b y b i i i i   =       w  Реальный случай ξ i ξ  Минимизируем При условии С – параметр регуляризации  =  n i i T C  2   w w ( ) T n    ,...,  = Вводим дополнительные « slck  переменные: i i i b w y  -    ) ( В реальном случае идеально разделить данные невозможно (эмпирический риск всегда больше 0) • На линейно разделимых данных МОВ работает отлично: • Но на более сложных данных не очень: • Можно отобразить данные на пространство большей размерности и разделить их линейно там: 0  0  0   2 Нелинейные SVM Slide credit: Andrew Moore Φ :  → φ (  ) Нелинейные SVM • Идея: отображение исходного пространства параметров на какое - то многомерное пространство признаков ( feture spce) где обучающая выборка линейно разделима: Slide credit: Andrew Moore Нелинейные SVM • Вычисление скалярных произведений в многомерном пространстве вычислительно сложно • The kernel trick : вместо прямого вычисления преобразования φ (  ) , мы определим ядровую функцию K: K (  i ,   ) = φ (  i ) · φ (   ) • Чтобы все было корретно, ядро должно удовлетворять условию Мерсера ( Mercer’s condition ) • Матрица K( i ,  ) должна быть неотрицательно определенной • С помощью ядра мы сможем построить нелинейную решающую функцию в исходном пространстве: b K y i i i i   ) , (    C. Burges, A Tutoril on Support Vector Mchines for Pttern Recognition , Dt Mining nd Knowledge Discovery, 99 Пример ядра • Полиномиальное: • Пусть d=2, =(  , 2 ): • Т.е. из 2х мерного в 6и мерное пространство d c y y  K ) ) , (( ) , (  =  ) ( ) ( ) ( ) ) , (( ) , ( 2 2 2   2 y  c y  y  c y y  K    =   =  =  ) , 2 , 2 , 2 , , ( ) ( 2  2  2 2 2  c  c  c      =  Использование SVM . Составить обучающую выборку 2. Выбрать ядро 3. Вычислить матрицу значений ядра для каждой пары примеров из обучающей выборки 4. Загрузить матрицу в библиотеку SVM для получения весов и опорных векторов 5. Во время вывода: вычислить значения ядра для тестового образца и каждого опорного вектора и взять взвешенную сумму для получения значения решающей функции Многоклассовые SVM • Нет специальной формулировки SVM для случая многих классов • На практике SVM для нескольких классов получается путем комбинации нескольких двухклассовых SVM • Один против всех • Обучение: обучаем SVM для каждого класса против всех остальных • Вывод : применим все SVM к образцу и назначим класс, SVM для которого выдал наиболее достоверное решение • Один против одного: • Обучение: обучим SVM для каждой пары классов • Вывод: каждый SVM голосует за классы, выбираем класс с наибольшим числом голосов SVM - резюме • Плюсы • Много доступных библиотек : http://www.kernel - mchines.org/softwre • Мощный и гибкий подход на основе ядер • На практике работает очень хорошо, даже для маленьких обучающих выборок • Минусы • Нет прямых многоклассовых метод, нужно объединять двухклассовые SVM • Вычисления, память – При обучении нужно строить полную матрицу ядра для всех примеров – Обучение занимает много времени для больших задач Применение классификаторов • Мы умеем: • Обучать классификатор (например, SVM) • Измерять эмпирический риск • Оценивать обобщающую способность – Удерживание, кросс - валидация • Всего ли нам достаточно для применения на практике? • Ошибка ошибке рознь • У метода могут быть параметры, как их подбирать? Виды ошибок • Измерения ошибки как «вероятности выдать неверный ответ может быть не всегда достаточно • 5% ошибки при постановке диагноза может означать как и то что, 5 % больных будут признаны здоровыми (и возможно умрут от отсутствия лечения), так и то, что 5% здоровых больными (и деньги на лечение будут потрачены зря) • При неравнозначности ошибок для разных классов вводят понятие ошибки первого и второго рода и замеряют их по отдельности Ошибки I и II рода • Пусть, существует «основной класс • Обычно, это класс, при обнаружении которого, предпринимается какое - либо действие; • Например, при постановке диагноза основным классом будет «болен, а вторичным классом «здоров. • Ошибка первого рода равна вероятности принять основной класс за вторичный • Вероятность «промаха, когда искомый объект будет пропущен • Ошибка второго рода равна вероятности принять вторичный класс за основной • Вероятность «ложной тревоги, когда за искомый объект будет принят «фон Ошибки I и II рода Истинная гипотеза Ошибка II рода Ошибка I рода Построенная гипотеза Будем считать красные точки «основным классом Ошибки I и II рода • Что считать основным классом зависит полностью от специфики прикладной задачи • В компьютерном зрении – почти всегда сильно несбалансированы • Особенно важно оценивать ошибки I и II рода раздельно при несбалансированности классов: • Пусть • Тогда при ошибке II рода 0 и ошибке I рода 0.5 • Общая ошибка всего лишь 99 . 0 )  ( ; 0 . 0 )  ( = - = =  = y P y P (()|)0.5 Pfy =-== 005 . 0 ) ) ( ( =  y   P Чувствительность vs Избирательность • Чувствительность – вероятность дать правильный ответ на пример основного класса • Также уровень обнаружения ( detection rte) • Избирательность – вероятность дать правильный ответ на пример вторичного класса • Обычно считают долю ложных обнаружений Flse positive rte =  - specificity (()|) sensitivityPfyy === (()|) specificityPfyy ===- Другие метрики • Точность ( Precision) • Доля истинных объектов основного класса среди всех классифицированных, как первый класс • Полнота ( Recl l ) • Доля правильно распознанных объектов основного класса среди всех объектов основного класса из тестовой выборки • Интегральный показатель F ( F - mesure) • F = 2 × ௉௥௘௖௜௦௜௢௡ × ோ௘௖௔௟௟ ௉௥௘௖௜௦௜௢௡ ା ோ௘௖௔௟௟ Регулировка баланса • Почти все алгоритмы классификации допускают регулировку соотношения ошибки I и II рода за счет варьирования некоторого параметра ROC кривая • ROC – Receiver Operting Chrcteristic curve • Кривая, отражающая зависимость чувствительности и ошибки второго рода монетка Лучший случай (Доля ложных обнаружений) (Уровень обнаружения) ROC кривая - Построение • Для различных значений параметра строится таблица ошибок • Сам параметр в таблице не участвует! • Классификатор строится и оценивается на разных выборках! Sensitivity Flse Positive 0.0 0.0 0.25 0.5 0.5 0. … … .0 .0 • По таблице строиться набор точек в плоскости sensitivity  ( flse positive) – Каждая строка таблицы - точка • По точкам строиться кривая Анализ ROC кривой • Площадь под графиком – AUC • Дает некоторый объективный показатель качества классификатора • Позволяет сравнивать разные кривые • Соблюдение требуемого значения ошибок I и II рода • Зачастую, для конкретной задачи существуют рамки на ошибку определенного рода. С помощью ROC можно анализировать возможность текущего решения соответствовать требованию Пример • Данные – точки на плоскости • Параметрическое семейство – порог по оси X      -    =   2  ,  ,  ) , (      Удерживание Тренировочная выборка Контрольная выборка Ошибка: 0.33 Ошибка: 0.433 Повторное удерживание • Тренировочная ошибка: • { 0.097 0.236 0.20 0.250 0.250 } • Среднее = 0.20 • Ошибка на контроле • { 0.33 0.222 0.333 0.222 0.67 } • Среднее = 0.356 Скользящий контроль : разбиение Скользящий контроль: Итеративно измеряем ошибку Скользящий контроль • Тренировочная ошибка: • { 0.236 0.20 0.250 0.097 0.306 } • Среднее = 0.29 • Ошибка на контроле • { 0.500 0.333 0.222 0.77 0.000 } • Среднее = 0.367 Построение ROC : таблица • Меняем порог и оцениваем ошибку • Строим таблицу Sensitivity Flse Positive 0.0 0.0 0.25 0.5 0.5 0. … … .0 .0 (|) p  Построение ROC - кривой • По таблице строим точки • Точки интерполируем кривой Резюме лекции • Машинное обучение позволяет использовать большое количество неинтуитивных простых признаков • Чем больше признаков и сложнее метод – тем больше нам нужно данных для обучения • Идеального решения задачи не существуют – нам нужно выбирать оптимальный баланс параметров • Запоминаем и применяем алгоритм SVM для бинарной классификации

Приложенные файлы

  • pdf 42043488
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий