Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии по
Машинное обучение
и
интеллектуальный анализ данных
Многослойная нейронная сеть-Vector-Blank.svg
Проблемы
Кластеризация
Снижение размерности
Структурированный прогноз
  • Графические модели
    • Сеть Байеса
    • Условное случайное поле
    • Скрытый Марков
Обнаружение аномалий
  • k -NN
  • Фактор местного выброса
Искусственная нейронная сеть
  • Автоэнкодер
  • Когнитивные вычисления
  • Глубокое обучение
  • DeepDream
  • Многослойный перцептрон
  • RNN
    • LSTM
    • ГРУ
    • ESN
  • Ограниченная машина Больцмана
  • GAN
  • SOM
  • Сверточная нейронная сеть
    • U-Net
  • Трансформатор
  • Пиковая нейронная сеть
  • Мемтранзистор
  • Электрохимическая RAM (ECRAM)
Обучение с подкреплением
  • Q-обучение
  • SARSA
  • Временная разница (TD)
Теория
  • Компромисс смещения и дисперсии
  • Теория вычислительного обучения
  • Минимизация эмпирического риска
  • Обучение Оккама
  • PAC обучение
  • Статистическое обучение
  • Теория ВК
Площадки для машинного обучения
  • NeurIPS
  • ICML
  • ML
  • JMLR
  • ArXiv: cs.LG
Статьи по Теме
  • Глоссарий искусственного интеллекта
  • Список наборов данных для исследований в области машинного обучения
  • Краткое описание машинного обучения
  • v
  • т
  • е

В машинном обучении , повышение является ансамблем меты-алгоритм для уменьшения прежде всего смещения , а также дисперсии [1] в подконтрольном обучении , и семейство алгоритмов машинного обучения, преобразующих слабые учащиеся сильные. [2] Повышение квалификации основано на вопросе, поставленном Кирнсом и Валиантом (1988, 1989): [3] [4] «Может ли группа слабых учеников создать одного сильного ученика?» Слабый ученик определяется как классификаторэто лишь слегка коррелирует с истинной классификацией (она может помечать примеры лучше, чем случайное предположение). Напротив, сильный ученик - это классификатор, который произвольно хорошо коррелирует с истинной классификацией.

Утвердительный ответ Роберта Шапира в статье 1990 года [5] на вопрос Кернса и Валианта имел значительные разветвления в машинном обучении и статистике , что в первую очередь привело к развитию бустинга. [6]

При первом введении проблема подтверждения гипотез просто относилась к процессу превращения слабого ученика в сильного ученика. «Неформально [проблема подтверждения гипотезы] задается вопросом, подразумевает ли эффективный алгоритм обучения […], который выводит гипотезу, производительность которой лишь немного лучше, чем случайное предположение [то есть слабый обучающийся], существование эффективного алгоритма, который выводит гипотезу произвольного точность [т.е. сильный ученик] ". [3] Алгоритмы, которые обеспечивают подтверждение гипотез, быстро стали известны как «повышение». Дуга Фрейнда и Шапира (Adapt [at] ive Resampling and Combining) [7] в качестве общей техники более или менее синонимична с усилением. [8]

Алгоритмы повышения [ править ]

Хотя усиление алгоритмически не ограничено, большинство алгоритмов повышения состоят из итеративного изучения слабых классификаторов по отношению к распределению и добавления их к окончательному сильному классификатору. Когда они добавляются, они взвешиваются в зависимости от точности слабых учеников. После добавления слабого ученика веса данных корректируются, что называется «повторным взвешиванием ». Неправильно классифицированные исходные данные приобретают больший вес, а примеры, классифицированные правильно, теряют вес. [примечание 1] Таким образом, будущие слабые ученики больше сосредотачиваются на примерах, которые предыдущие слабые ученики неправильно классифицировали.

Иллюстрация, демонстрирующая интуицию алгоритма повышения, состоящего из параллельных учащихся и взвешенного набора данных.

Есть много алгоритмов повышения. Первоначальные, предложенные Робертом Шапиром ( формулировка рекурсивных ворот большинства) [5] и Йоавом Фройндом (усиление большинством) [9], не были адаптивными и не могли полностью использовать преимущества слабых учеников. Затем Шапир и Фройнд разработали AdaBoost , алгоритм адаптивного повышения, который получил престижную премию Гёделя .

Только алгоритмы, которые являются доказуемыми алгоритмами повышения в возможно приблизительно правильной формулировке обучения, могут точно называться алгоритмами повышения . Другие алгоритмы, которые по духу [ необходимы разъяснения ] схожи с алгоритмами повышения, иногда называют «алгоритмами повышения», хотя их также иногда неправильно называют алгоритмами повышения. [9]

Основное различие между многими алгоритмами повышения - это метод взвешивания точек обучающих данных и гипотез . AdaBoost очень популярен и является наиболее значимым с исторической точки зрения, поскольку это был первый алгоритм, который мог адаптироваться к слабым ученикам. Это часто является основой вводного курса повышения квалификации в университетских курсах машинного обучения. [10] Есть много более поздних алгоритмов , такие как LPBoost , TotalBoost, BrownBoost , xgboost , MadaBoost, LogitBoost и другие. Многие алгоритмы повышения вписываются в структуру AnyBoost, [9] что показывает, что повышение производительностиградиентный спуск в функциональном пространстве с использованием выпуклой функции стоимости .

Категоризация объектов в компьютерном зрении [ править ]

Основная статья: Категоризация объектов из поиска изображений

Учитывая изображения, содержащие различные известные объекты в мире, из них можно изучить классификатор, чтобы автоматически классифицировать объекты в будущих изображениях. Простые классификаторы, построенные на основе некоторых характеристик изображения объекта, обычно неэффективны при категоризации. Использование методов повышения для категоризации объектов - это способ объединить слабые классификаторы особым образом, чтобы повысить общую способность категоризации.

Проблема категоризации объектов [ править ]

Категоризация объектов - это типичная задача компьютерного зрения, которая включает определение того, содержит ли изображение какую-либо определенную категорию объекта. Идея тесно связана с распознаванием, идентификацией и обнаружением. Внешний вид объекта на основе категоризации обычно содержит выделение признаков , обучение в классификатор , и применяя классификатор к новым примерам. Существует множество способов представления категории объектов, например, из анализа формы , моделей набора слов или локальных дескрипторов, таких как SIFT , и т. Д. Примерами контролируемых классификаторов являются наивные байесовские классификаторы ,опорные векторные машины , смеси гауссианов и нейронные сети . Однако исследование [ какое? ] показал, что категории объектов и их расположение на изображениях можно также обнаруживать неконтролируемым образом . [11]

Статус-кво для категоризации объектов [ править ]

Распознавание категорий объектов на изображениях - сложная проблема компьютерного зрения , особенно когда количество категорий велико. Это связано с высокой внутриклассовой изменчивостью и необходимостью обобщения по вариациям объектов в одной и той же категории. Объекты в одной категории могут выглядеть совершенно по-разному. Даже один и тот же объект может казаться непохожим под разными углами обзора, масштабом и освещением . Беспорядок на заднем фоне и частичная окклюзия также усложняют распознавание. [12] Люди способны распознавать тысячи типов объектов, в то время как большинство существующих систем распознавания объектов обучены распознавать только некоторые, [ количественно ]например, человеческие лица , автомобили , простые предметы и т. д. [13] [ требуется обновление? ] Исследования были очень активными, чтобы иметь дело с большим количеством категорий и обеспечивать возможность постепенного добавления новых категорий, и хотя общая проблема остается нерешенной, было разработано несколько детекторов многокатегорийных объектов (до сотен или тысяч категорий [14] ). Одним из способов является совместное использование функций и повышение их уровня.

Повышение бинарной категоризации [ править ]

AdaBoost можно использовать для обнаружения лиц в качестве примера двоичной категоризации . Две категории - это лица по сравнению с фоном. Общий алгоритм следующий:

  1. Сформируйте большой набор простых функций
  2. Инициализировать веса для обучающих изображений
  3. Для Т-раундов
    1. Нормализовать веса
    2. Для доступных функций из набора обучите классификатор, используя одну функцию, и оцените ошибку обучения.
    3. Выберите классификатор с наименьшей ошибкой
    4. Обновите веса обучающих изображений: увеличьте, если классифицируют неправильно, уменьшите, если правильно
  4. Сформируйте окончательный сильный классификатор как линейную комбинацию T-классификаторов (коэффициент больше, если ошибка обучения мала)

После усиления классификатор, состоящий из 200 функций, может дать 95% -ный уровень обнаружения при ложных срабатываниях . [15]

Еще одно применение повышения для двоичной категоризации - это система, которая обнаруживает пешеходов по шаблонам движения и внешнего вида. [16] Эта работа является первой, в которой информация о движении и информация о внешнем виде объединяются в качестве функций для обнаружения идущего человека. Он использует аналогичный подход к платформе обнаружения объектов Виолы-Джонса .

Повышение для мультиклассовой категоризации [ править ]

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

Основной поток алгоритма аналогичен бинарному случаю. Отличие состоит в том, что мера ошибки совместного обучения должна быть определена заранее. Во время каждой итерации алгоритм выбирает классификатор одной функции (функции, которые могут быть разделены несколькими категориями, должны поощряться). Это может быть сделано путем преобразования мультиклассовой классификации в двоичную (набор категорий по сравнению с остальными) [17] или путем введения штрафной ошибки из категорий, которые не имеют функции классификатора. [18]

В статье «Совместное использование визуальных функций для обнаружения многоклассовых и многоракурсных объектов» A. Torralba et al. использовал GentleBoost для повышения и показал, что, когда данные обучения ограничены, обучение с помощью функций совместного использования работает намного лучше, чем отсутствие совместного использования при тех же раундах повышения. Кроме того, для заданного уровня производительности общее количество требуемых функций (и, следовательно, стоимость времени работы классификатора) для детекторов совместного использования функций, как наблюдается, масштабируется приблизительно логарифмически с количеством классов, то есть медленнее, чем линейный рост в случай отказа от совместного использования. Подобные результаты показаны в статье «Пошаговое обучение детекторов объектов с использованием визуального алфавита фигур», но авторы использовали AdaBoost для повышения.

Выпуклые и невыпуклые алгоритмы повышения [ править ]

Алгоритмы повышения могут быть основаны на алгоритмах выпуклой или невыпуклой оптимизации. Выпуклые алгоритмы, такие как AdaBoost и LogitBoost , могут быть «побеждены» случайным шумом, так что они не могут изучить базовые и обучаемые комбинации слабых гипотез. [19] [20] Это ограничение было указано Long & Servedio в 2008 году. Однако к 2009 году несколько авторов продемонстрировали, что алгоритмы повышения, основанные на невыпуклой оптимизации, такие как BrownBoost , могут учиться на зашумленных наборах данных и могут специально изучать базовый классификатор набора данных Long – Servedio.

См. Также [ править ]

  • AdaBoost
  • Случайный лес
  • Альтернативное дерево решений
  • Агрегирование бутстрапа (упаковка)
  • Каскадный
  • BrownBoost
  • CoBoosting
  • LPBoost
  • Логистическая регрессия
  • Методы максимальной энтропии
  • Нейронные сети
  • Опорные векторные машины
  • Повышение градиента
  • Классификаторы маржи
  • Перекрестная проверка
  • Машинное обучение
  • Список наборов данных для исследования машинного обучения

Реализации [ править ]

  • Scikit-learn , библиотека машинного обучения с открытым исходным кодом для Python
  • Orange , бесплатный программный пакет для интеллектуального анализа данных, модуль Orange.ensemble
  • Weka - это набор инструментов для машинного обучения, который предлагает различные реализации алгоритмов повышения, таких как AdaBoost и LogitBoost.
  • Пакет R GBM (Generalized Boosted Regression Models) реализует расширения для алгоритма AdaBoost Фрейнда и Шапира и машины повышения градиента Фридмана.
  • jboost ; AdaBoost, LogitBoost, RobustBoost, Boostexter и чередующиеся деревья решений
  • Пакет R adabag : применяет Multiclass AdaBoost.M1, AdaBoost-SAMME и Bagging
  • Пакет R xgboost : реализация повышения градиента для линейных и древовидных моделей.

Заметки [ править ]

  1. ^ Некоторые алгоритмы классификации, основанные на бустинге, фактически уменьшают вес многократно неправильно классифицируемых примеров; например буст большинством и BrownBoost .

Ссылки [ править ]

  1. ↑ Лео Брейман (1996). "КЛАССИФИКАТОРЫ СКОРОСТИ, ДИГНОСТИКИ И ДУГИ" (PDF) . ТЕХНИЧЕСКИЙ ОТЧЕТ. Архивировано из оригинального (PDF) 19 января 2015 года . Проверено 19 января 2015 года . Создание дуги [Boosting] более эффективно, чем уменьшение дисперсии
  2. ↑ Чжоу Чжи-Хуа (2012). Ансамблевые методы: основы и алгоритмы . Чепмен и Холл / CRC. п. 23. ISBN 978-1439830031. Термин усиление относится к семейству алгоритмов, которые могут превращать слабых учеников в сильных.
  3. ^ а б Майкл Кернс (1988); Мысли об усилении гипотез , неопубликованная рукопись (проект класса машинного обучения, декабрь 1988 г.)
  4. ^ Майкл Кернс ; Лесли Валиант (1989). Криптографические [ sic ] ограничения на изучение булевых формул и конечных автоматов . Симпозиум по теории вычислений . 21 . ACM. С. 433–444. DOI : 10.1145 / 73007.73049 . ISBN 978-0897913072. S2CID  536357 .
  5. ^ a b Schapire, Роберт Э. (1990). «Сила слабой обучаемости» (PDF) . Машинное обучение . 5 (2): 197–227. CiteSeerX 10.1.1.20.723 . DOI : 10.1007 / bf00116037 . S2CID 53304535 . Архивировано из оригинального (PDF) 10-10-2012 . Проверено 23 августа 2012 .   
  6. ↑ Лео Брейман (1998). «Классификатор дуги (с обсуждением и ответом автора)» . Аня. Стат . 26 (3): 801–849. DOI : 10.1214 / AOS / 1024691079 . Schapire (1990) доказал, что повышение возможно. (Стр. 823)
  7. ↑ Йоав Фройнд и Роберт Э. Шапир (1997); Теоретико- решающее обобщение онлайн -обучения и приложение для повышения эффективности , Журнал компьютерных и системных наук, 55 (1): 119-139
  8. ↑ Лео Брейман (1998); Классификатор дуги (с обсуждением и ответом автора) , Annals of Statistics, vol. 26, вып. 3, pp. 801-849: «Концепция слабого обучения была введена Кирнсом и Валиантом (1988, 1989), которые оставили открытым вопрос о том, эквивалентны ли слабая и сильная обучаемость. Этот вопрос был назван проблемой повышения, поскольку [a решение должно] повысить низкую точность слабого обучаемого до высокой точности сильного. Шапайр (1990) доказал, что повышение возможно. Алгоритм повышения - это метод, который берет слабого обучаемого и превращает его в сильного обучаемого. Фройнд и Schapire (1997) доказали, что алгоритм, похожий на arc-fs, ускоряется.
  9. ^ a b c Лью Мейсон, Джонатан Бакстер, Питер Бартлетт и Маркус Фрин (2000); Алгоритмы повышения как градиентный спуск , в С.А. Солла, Т.К. Лин и К.-Р. Мюллер, редакторы, Успехи в системах обработки нейронной информации 12, стр. 512-518, MIT Press
  10. ^ Эмер, Эрик. «Повышение (алгоритм AdaBoost)» (PDF) . Массачусетский технологический институт . Проверено 10 октября 2018 .
  11. ^ Сивик, Рассел, Эфрос, Фриман и Зиссерман, «Обнаружение объектов и их местоположения на изображениях», ICCV 2005
  12. ^ А. Опельт, А. Пинц и др., "Распознавание общих объектов с повышением", транзакции IEEE на PAMI 2006
  13. ^ М. Маршалек, "Семантические иерархии для распознавания визуальных объектов", 2007
  14. ^ «Крупномасштабная проблема визуального распознавания» . Декабрь 2017 г.
  15. ^ П. Виола, М. Джонс, "Надежное обнаружение объектов в реальном времени", 2001
  16. ^ Альт, P .; Jones, M .; Сноу, Д. (2003). Обнаружение пешеходов по шаблонам движения и внешнего вида (PDF) . ICCV.
  17. ^ A. Torralba, KP Murphy и др., "Совместное использование визуальных функций для обнаружения многоклассовых и многоэкранных объектов", IEEE Transactions on PAMI 2006
  18. ↑ A. Opelt, et al., «Постепенное обучение детекторов объектов с использованием алфавита визуальных форм», CVPR 2006
  19. ^ П. Лонг и Р. Серведио. 25-я Международная конференция по машинному обучению (ICML), 2008 г., стр. 608-615.
  20. ^ Лонг, Филип М .; Серведио, Рокко А. (март 2010 г.). «Шум случайной классификации побеждает все выпуклые потенциальные ускорители» (PDF) . Машинное обучение . 78 (3): 287–304. DOI : 10.1007 / s10994-009-5165-Z . S2CID 53861 . Проверено 17 ноября 2015 .  

Дальнейшее чтение [ править ]

  • Йоав Фройнд и Роберт Э. Шапир (1997); Теоретико-решающее обобщение онлайн-обучения и приложение для повышения эффективности , Журнал компьютерных и системных наук, 55 (1): 119-139
  • Роберт Э. Шапир и Йорам Сингер (1999); Улучшенные алгоритмы повышения с использованием предсказателей с рейтингом достоверности , машинное обучение, 37 (3): 297-336

Внешние ссылки [ править ]

  • Роберт Э. Шапир (2003 г.); Подход к машинному обучению: обзор , семинар ИИГС (научно-исследовательский институт математических наук) по нелинейному оцениванию и классификации
  • Чжоу Чжи-Хуа (2014) Повышение 25 лет , CCL 2014 Keynote.
  • Чжоу, Чжихуа (2008). «На полях пояснения алгоритма повышения» (PDF) . В: Материалы 21-й ежегодной конференции по теории обучения (COLT'08) : 479–490.
  • Чжоу, Чжихуа (2013). «О сомнении в маржинальном объяснении повышения» (PDF) . Искусственный интеллект . 203 : 1–18. arXiv : 1009.3613 . DOI : 10.1016 / j.artint.2013.07.002 . S2CID  2828847 .