В повышении, почему ученики «слабые»?

28

Смотрите также похожий вопрос на stats.SE .

В таких алгоритмах повышения , как AdaBoost и LPBoost, известно, что «слабые» ученики, которых нужно объединить, должны работать лучше, чем шанс быть полезными, из Википедии:

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

  • Каковы преимущества использования слабых по сравнению с сильными учениками? (например, почему бы не повысить с помощью «сильных» методов обучения - мы более склонны к переобучению?)

  • Есть ли какая-то «оптимальная» сила для слабых учеников? И связано ли это с количеством учеников в ансамбле?

Есть ли теория, подтверждающая ответы на эти вопросы?

TDC
источник
Слабые ученики также избегают чрезмерной подгонки к тренировочным данным
Аман Дип Гаутам

Ответы:

15

Таким образом, бустинг - это алгоритм обучения, который может генерировать высокоточные прогнозы, используя в качестве подпрограммы другой алгоритм, который, в свою очередь, может эффективно генерировать гипотезы чуть лучше (с помощью обратного полинома), чем случайное угадывание.

Это главное преимущество - скорость.

Когда Шапире представил его в 1990 году, это был прорыв в том, что он показал, что учащийся за полиномиальное время, генерирующий гипотезы с ошибками, немного меньшими 1/2, может быть преобразован в учащийся за полиномиальное время, генерирующий гипотезы со сколь угодно малой ошибкой.

Итак, теория, подтверждающая ваш вопрос, находится в «Силе слабой обучаемости» ( pdf ), где он в основном показал, что «сильное» и «слабое» обучение эквивалентны.

И, возможно, ответ на первоначальный вопрос таков: «Нет смысла создавать сильных учеников, когда вы можете создавать слабых учеников дешевле».


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

andreister
источник
1
+1 хорошие ссылки. Поэтому, возможно, ответ таков: «нет смысла создавать сильных учеников, когда можно создавать более дешевых»?
тдк
да, звучит так - я обновил ответ! Кроме того, если я правильно понимаю, это не зависит от силы ваших слабых учеников - они просто должны быть «немного» лучше случайных.
andreister
1
Я думаю, что вы оба на самом деле имеете в виду: нет смысла создавать дорогих сильных учеников, когда можно достичь сходного или даже лучшего навыка, просто объединив много дешевых слабых учеников . В самом деле, если навык, достигнутый сильными учениками, был намного выше, чем навык, достигнутый слабыми учениками, тогда я мог бы полностью понять смысл построения сильных учеников ...
Антуан
9

Я рассмотрю переоснащение, которое еще не упоминалось, с более интуитивным объяснением. Ваш первый вопрос был:

Каковы преимущества использования слабых по сравнению с сильными учениками? (например, почему бы не повысить с помощью «сильных» методов обучения - мы более склонны к переобучению?)

Основными причинами, на мой взгляд, являются:

  • Скорость , как хорошо видно в других ответах;
  • Повышение точности : если у вас уже есть сильный ученик, преимущества повышения менее значимы;
  • Избегайте переоснащения , как вы уже догадались. Подумайте об этом таким образом:

Что стимулирует, так это объединяет много разных гипотез из пространства гипотез, чтобы мы в итоге получили лучшую окончательную гипотезу. Следовательно, великая сила ускорения проистекает из разнообразия гипотез.

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

Артур Коломбини Гужман
источник
4
Это настоящий ответ.
Мэтью Друри
6

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

Допустим, я использую 100 учеников. Я тренирую NN за 100 секунд и дерево решений за 10 секунд. Мое первое повышение с помощью NN займет 100 * 100 секунд, а второе повышение с помощью дерева решений займет 100 * 10 секунд.

Тем не менее, я видел статьи, которые используют сильные ученики в повышении. Но в этих проблемах сильные ученики были быстрыми, по моему мнению.

Я пытался обучить MLP на наборе данных обнаружения вторжений KDD99 (4+ миллиона), используя Weka. На моей машине это заняло более 72 часов. Но повышение (AdaBoostM1 с Decision Tree - Decision Stump) заняло всего 3 часа. В этой проблеме ясно, что я не могу использовать повышение с сильным учеником, то есть учеником, который занимает слишком много времени.

Атилла Озгур
источник
1
«Я видел статьи, которые используют сильные ученики в повышении» - какие-нибудь ссылки?
tdc