Редактирование: Бустинг, AdaBoost

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Описание==
 
==Описание==
'''Бустинг''' (англ. ''boosting'') {{---}} [[Мета-обучение|мета-алгоритм машинного обучения]]. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как [[Виды ансамблей|бэггинг]] (англ. ''bagging'') и стэкинг<ref>[https://dyakonov.org/2017/03/10/c%D1%82%D0%B5%D0%BA%D0%B8%D0%BD%D0%B3-stacking-%D0%B8-%D0%B1%D0%BB%D0%B5%D0%BD%D0%B4%D0%B8%D0%BD%D0%B3-blending/#more-4558 Стекинг {{---}} Дьяконов Александр]</ref> (англ. ''stacking''). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.  
+
'''Бустинг''' (англ. ''boosting'') — это [[Мета-обучение|мета-алгоритм машинного обучения]]. Основной идеей бустинга является комбинирование слабых функций, которые строятся в ходе итеративного процесса, где на каждом шаге новая модель обучается с использованием данных об ошибках предыдущих. Сильный обучающий алгоритм является классификатором, хорошо [[Корреляция случайных величин|коррелирующим]] с верной классификацией, в отличие от слабого. Наравне с бустингом в мета-обучении также рассматривают такие понятия, как [[Виды ансамблей|бэггинг]] (англ. ''bagging'') и стэкинг<ref>[https://dyakonov.org/2017/03/10/c%D1%82%D0%B5%D0%BA%D0%B8%D0%BD%D0%B3-stacking-%D0%B8-%D0%B1%D0%BB%D0%B5%D0%BD%D0%B4%D0%B8%D0%BD%D0%B3-blending/#more-4558 Стекинг {{---}} Дьяконов Александр]</ref> (англ. ''stacking''). Бэггинг, в отличии от бустинга, использует параллельное обучение базовых классификаторов. Стэкинг же комбинирует результаты различных алгоритмов, получая тем самым более точный ответ.  
  
 
Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
 
Одним из недостатков бустинга является то, что он может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Такие композиции исключают возможность содержательной интерпретации, требуют больших объёмов памяти для хранения базовых алгоритмов и существенных затрат времени на вычисление классификаций.
Строка 6: Строка 6:
 
==Алгоритмы бустинга==
 
==Алгоритмы бустинга==
 
{{Определение
 
{{Определение
|definition='''Композицией''' $T$ '''алгоритмов''' <tex>a_t(x) = C(b_t(x)),\ t = 1,...,T</tex> называется [[Суперпозиции|суперпозиция]] алгоритмических операторов <tex>b_t\ :\ X\to R</tex>, корректирующей операции <tex>F\ :\ R^T\to R</tex> и решающего правила <tex> C\ :\ R\to Y</tex>, где <tex>R</tex> {{---}} пространство оценок,<br><center><tex>a(x) = C(F(b_1(x),...,b_T(x))), x \in X</tex></center><br>, Алгоритмы $a_t$ называют ''базовыми алгоритмами''.}}
+
|definition='''Композицией''' $T$ '''алгоритмов''' <tex>a_t(x) = C(b_t(x)),\ t = 1,...,T</tex> называется [[Суперпозиции|суперпозиция]] алгоритмических операторов <tex>b_t\ :\ X\to R</tex>, корректирующей операции <tex>F\ :\ R^T\to R</tex> и решающего правила <tex> C\ :\ R\to Y</tex>, где <tex>R</tex> {{---}} пространство оценок,<br><center><tex>a(x) = C(F(b_1(x),...,b_T(x))), x \in X</tex></center><br>Алгоритмы $a_t$ называют ''базовыми алгоритмами''.}}
 
Бустинг представляет собой композицию алгоритмов, в которых ошибки отдельных алгоритмов взаимно компенсируются. Например, в задаче классификации на два класса $Y = {-1, +1}$ в качестве пространства оценок принимают $R = \mathbb{R}$ и <tex>C(b(x)) = \textrm{sign}(b(x))</tex>. Тогда базовые алгоритмы возвращают ответы $−1, 0, +1$. Ответ $b_t(x) = 0$ означает, что базовый алгоритм $b_t$ отказывается от классификации объекта $x$, и ответ $b_t(x)$ не учитывается в композиции. Получаем искомую композицию:
 
Бустинг представляет собой композицию алгоритмов, в которых ошибки отдельных алгоритмов взаимно компенсируются. Например, в задаче классификации на два класса $Y = {-1, +1}$ в качестве пространства оценок принимают $R = \mathbb{R}$ и <tex>C(b(x)) = \textrm{sign}(b(x))</tex>. Тогда базовые алгоритмы возвращают ответы $−1, 0, +1$. Ответ $b_t(x) = 0$ означает, что базовый алгоритм $b_t$ отказывается от классификации объекта $x$, и ответ $b_t(x)$ не учитывается в композиции. Получаем искомую композицию:
<center><tex>a(x) = C(F(b_1(x),...,b_T(x))) = \textrm{sign}\left(\sum\limits_{t=1}^T \alpha_t b_t(x)\right),\ x\in X</tex></center>,
+
<center><tex>a(x) = C(F(b_1(x),...,b_T(x))) = \textrm{sign}\left(\sum\limits_{t=1}^T \alpha_t b_t(x)\right),\ x\in X</tex></center>
  
 
Большая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с [[Общие понятия|точностью обучения]]. После добавления слабого классификатора, веса пересчитываются ('''«пересчёт весовых коэффициентов»'''). Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Таким образом, дальнейшее слабое обучение фокусируется на примерах, где предыдущие слабые обучения дали ошибочную классификацию.
 
Большая часть алгоритмов бустинга основывается на итеративном обучении слабых классификаторов с дальнейшей сборкой их в сильный классификатор. Когда они добавляются, им обычно приписываются веса, обычно связанные с [[Общие понятия|точностью обучения]]. После добавления слабого классификатора, веса пересчитываются ('''«пересчёт весовых коэффициентов»'''). Неверно классифицированные входные данные получают больший вес, а правильно классифицированные экземпляры теряют вес. Таким образом, дальнейшее слабое обучение фокусируется на примерах, где предыдущие слабые обучения дали ошибочную классификацию.
Строка 18: Строка 18:
 
==Прикладное использование алгоритмов бустинга==
 
==Прикладное использование алгоритмов бустинга==
 
===Задача классификации объектов===
 
===Задача классификации объектов===
Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов {{---}} путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.
+
Если даны изображения, содержащие различные известные в мире объекты, классификатор может быть обучен на основе них для автоматической классификации объектов в будущих неизвестных изображениях. Простые классификаторы, построенные на основе некоторых признаков изображения объекта, обычно оказываются малоэффективными в классификации. Использование методов бустинга для классификации объектов — это путь объединения слабых классификаторов специальным образом для улучшения общей возможности классификации.
  
 
Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]], обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT'''<ref>[https://en.wikipedia.org/wiki/Scale-invariant_feature_transform Wikipedia {{---}} Scale-invariant feature transform]</ref>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]<sup>[на 28.01.19 не создан]</sup>, [[Метод опорных векторов (SVM)|методы опорных векторов]]<sup>[на 28.01.19 не создан]</sup>, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.
 
Классификация признаков является типичной задачей компьютерного зрения, где определяется, содержит ли изображение некоторую категорию объектов или нет. Идея тесно связана с распознаванием, идентификацией и обнаружением. Классификация по обнаружению объекта обычно содержит выделение [[Общие понятия|признаков]], обучение классификатора и применение классификатора к новым данным. Есть много способов представления категории объектов, например по анализу формы, с помощью модели '''«мешок слов»''', с помощью локальных описателей, таких как '''SIFT'''<ref>[https://en.wikipedia.org/wiki/Scale-invariant_feature_transform Wikipedia {{---}} Scale-invariant feature transform]</ref>, и так далее. Примерами классификаторов с учителем служат наивные [[Байесовская классификация|байесовские классификаторы]]<sup>[на 28.01.19 не создан]</sup>, [[Метод опорных векторов (SVM)|методы опорных векторов]]<sup>[на 28.01.19 не создан]</sup>, смесь гауссиан и [[Нейронные сети, перцептрон|нейронные сети]]. Однако исследования показали, что категории объектов и их положение в изображениях могут быть обнаружены также с помощью обучения без учителя.
Строка 51: Строка 51:
 
   '''return''' $H$
 
   '''return''' $H$
 
Выражение для обновления распределения <tex>D^t</tex> должно быть сконструировано таким образом, чтобы выполнялось условие:
 
Выражение для обновления распределения <tex>D^t</tex> должно быть сконструировано таким образом, чтобы выполнялось условие:
<center><tex>\exp^{\alpha_t y_i h_t(x_i)} \begin{cases}<1,\ y(i) = h_t(x_i) \\ >1,\ y(i) \neq h_t(x_i)\end{cases}</tex></center>,
+
<center><tex>\exp^{\alpha_t y_i h_t(x_i)} \begin{cases}<1,\ y(i) = h_t(x_i) \\ >1,\ y(i) \neq h_t(x_i)\end{cases}</tex></center>
  
 
Таким образом, после выбора оптимального классификатора <tex>h_t</tex> для распределения <tex>D^t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D^{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
 
Таким образом, после выбора оптимального классификатора <tex>h_t</tex> для распределения <tex>D^t</tex>, объекты <tex>x_i</tex>, которые классификатор <tex>h_t</tex> идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении <tex>D^{t+1}</tex>, он будет выбирать классификатор, который лучше идентифицирует объекты неверно распознаваемые предыдущим классификатором.
Строка 68: Строка 68:
 
===Достоинства и недостатки===
 
===Достоинства и недостатки===
 
'''Достоинства:'''
 
'''Достоинства:'''
# Простота реализации;
+
# Простота реализации
# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов;
+
# Хорошая обобщающая способность. В реальных задачах удаётся строить композиции, превосходящие по качеству базовые алгоритмы. Обобщающая способность может улучшаться по мере увеличения числа базовых алгоритмов.
# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов;
+
# Время построения композиции практически полностью определяется временем обучения базовых алгоритмов.
 
# Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.
 
# Возможность идентифицировать выбросы. Это наиболее «трудные» объекты $x_i$, для которых в процессе наращивания композиции веса $w_i$ принимают наибольшие значения.
 
'''Недостатки:'''
 
'''Недостатки:'''
# Склонен к переобучению при наличии значительного уровня шума в данных;
+
# Склонен к переобучению при наличии значительного уровня шума в данных.
 
# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
 
# Требует достаточно длинных обучающих выборок. Другие методы линейной коррекции, в частности, бэггинг, способны строить алгоритмы сопоставимого качества по меньшим выборкам данных.
  
Строка 79: Строка 79:
 
Классификатор sklearn.ensemble.'''AdaBoostClassifier'''<ref>[https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html Документация AdaBoostClassifier]</ref> имеет 5 параметров: '''base_estimator''', '''n_estimators''', '''learning_rate''', '''algorithm''', '''random_state'''.
 
Классификатор sklearn.ensemble.'''AdaBoostClassifier'''<ref>[https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.AdaBoostClassifier.html Документация AdaBoostClassifier]</ref> имеет 5 параметров: '''base_estimator''', '''n_estimators''', '''learning_rate''', '''algorithm''', '''random_state'''.
 
Наиболее важными являются:  
 
Наиболее важными являются:  
# '''base_estimator''' {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1);
+
# '''base_estimator''' {{---}} базовый алгоритм. По умолчанию используется DecisionTreeClassifier(max_depth=1)
# '''n_estimators''' {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше;
+
# '''n_estimators''' {{---}} максимальное количество оценок, после которого бустинг прекращается. Если произойдет полное совпадение, то закончится раньше.
 
# '''learning_rate''' {{---}} вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
 
# '''learning_rate''' {{---}} вклад каждой модели в весовые коэффициенты и значение по умолчанию равно $1$. Снижение этого параметра будет означать, что весовые коэффициенты буду увеличиваться или уменьшаться в небольшой степени, вынуждая модель дольше обучаться (но иногда повышается производительность).
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: