Adaptive boosting

    Здравствуйте, на Хабре уже была статья Indalo, посвященная AdaBoost, точнее, некоторому его применению. Я же хочу более детально остановиться на самом алгоритме, заглянуть в его реализацию и продемонстрировать его работу на примере моей программы.

    Итак, в чем же заключается суть методики Adaboost?

    Суть заключается в том, что если у нас есть набор эталонных объектов (точки на плоскости), т.е. есть значения и класс, к которому они принадлежат (например, -1 – красная точка, +1 – синяя точка), кроме того имеется множество простых классификаторов (набор вертикальных или горизонтальных прямых, которые разделяют плоскость на две части с наименьшей ошибкой), то мы можем составить один лучший классификатор. При этом в процессе составления или обучения финального классификатора акцент делается на эталоны, которые распознаются «хуже», в этом и заключается адаптивность алгоритма, в процессе обучения он подстраивается под наиболее «сложные» объекты.

    Псевдокод алгоритма хорошо описан на Вики. Приведем его здесь.

    Псевдокод


    Дано: image, где image.

    Инициализируем image

    Для каждого image:

    * Находим классификатор image, который минимизирует взвешенную ошибку классификации:
    image, где image

    * Если величина image, то останавливаемся.
    * Выбираем image, обычно image, где ?t взвешенная ошибка классификатора ht.
    * Обновляем:

    image,
    где Zt является нормализующим параметром (выбранным так, чтобы Dt + 1 являлось распределением вероятностей, то есть image).

    Строим результирующий классификатор:

    image.

    Далее будем придерживаться его в наших объяснениях.

    Простой классификатор



    Итак, простой классификатор. Как я уже говорил, это вертикальная или горизонтальная прямая, которая разделяет плоскость на две части, минимизируя ошибку классификации: image (квадратные скобки от булевого выражения равны 1, ели true, и 0, если false). На языке С# процедуру такого обучения можно написать следующим образом:

    //Обучение простого классификатора

    public override void Train(LabeledDataSet<double> trainingSet)
      {
       // Инициализируем наши коэффициенты D_i
       if (_weights == null)
       {
        _weights = new double[trainingSet.Count];
        for (int i = 0; i < trainingSet.Count; i++)
         _weights[i] = 1.0 / trainingSet.Count;
       }
     
       Random rnd = new Random();
              double minimumError = double.PositiveInfinity;
       _d = -1;
       _threshold = double.NaN;
       _sign = 0;
     
       // Цикл по всем координатам пространства
       for (int d = 0; d < trainingSet.Dimensionality; d++)
       {
        // Для оптимизации в случае, если пространство огромной размерности
        if (rnd.NextDouble() < _randomize)
         continue;
     
        // Сортируем данные для эффективного поиска прямой x_d = threshold
        double[] data = new double[trainingSet.Count];
        int[] indices = new int[trainingSet.Count];
        for (int i = 0; i < trainingSet.Count; i++)
        {
         data[i] = trainingSet.Data[i][d];
         indices[i] = i;
        }
        Array.Sort(data, indices);
     
        // Определяем максимальную ошибку
        double totalError = 0.0;
        for (int i = 0; i < trainingSet.Count; i++)
         totalError += _weights[i];
     
        // Инициализируем значение ошибки для поиска минимальной ошибки
        double currentError = 0.0;
        for (int i = 0; i < trainingSet.Count; i++)
         currentError += trainingSet.Labels[i] == -1 ? _weights[i] : 0.0;
     
        // Ищем в отсортированном массиве лучший параметр threshold, который будет минимизировать
                                   //ошибку, и определяем знак классификатора
        for (int i = 0; i < trainingSet.Count - 1; i++)
        {
         // Обновляем ошибку при рассмотрении текущего объекта
         int index = indices[i];
         if (trainingSet.Labels[index] == +1)
          currentError += _weights[index];
         else
          currentError -= _weights[index];
     
         // Если идут одинаковые данные, то порог не ищем
         if (data[i] == data[i + 1])
          continue;
     
         // Определяем потенциально возможное значение для threshold
         double testThreshold = (data[i] + data[i + 1]) / 2.0;
     
         // Запоминаем значение threshold, если ошибка минимальна, и определяем знак
         if (currentError < minimumError) // Классификатор с _sign = +1
         {
          minimumError = currentError;
          _d = d;
          _threshold = testThreshold;
          _sign = +1;
         }
         if ((totalError - currentError) < minimumError) // Классификатор с _sign = -1
         {
          minimumError = (totalError - currentError);
          _d = d;
          _threshold = testThreshold;
          _sign = -1;
         }
        }
       }
      }


    Если Вы заметили, то процедура обучения простого классификатора написана таким образом, что если ему передать веса, которые получаются на протяжении работы алгоритма AdaBoost, то тогда будет искаться тот классификатор, который минимизирует взвешенную ошибку классификации п.1. Тогда сам алгоритм на С# будет выглядеть следующим образом:

    «Сложный» классификатор



    //Обучение с помощью AdaBoost

    public override void Train(LabeledDataSet<double> trainingSet)
      {
       // Инициализируем веса D_i
       if (_weights == null)
       {
        _weights = new double[trainingSet.Count];
        for (int i = 0; i < trainingSet.Count; i++)
         _weights[i] = 1.0 / trainingSet.Count;
       }
     
       // Делаем непосредственно обучение простых классификаторов
       for (int t = _h.Count; t < _numberOfRounds; t++)
       {
        // Создаем простой классификатор и обучаем его
        WeakLearner h = _factory();
        h.Weights = _weights;
        h.Train(trainingSet);
     
        //Вычисляем ввзвешенную ошибку классификации
        int[] hClassification = new int[trainingSet.Count];
        double epsilon = 0.0;
        for (int i = 0; i < trainingSet.Count; i++)
        {
         hClassification[i] = h.Classify(trainingSet.Data[i]);
         epsilon += hClassification[i] != trainingSet.Labels[i] ? _weights[i] : 0.0;
        }
     
        // Если величина epsilon >= 0.5, то останавливаемся
        if (epsilon >= 0.5)
         break;
     
        // Выбираем \alpha_{t}
        double alpha = 0.5 * Math.Log((1 - epsilon) / epsilon);
     
        // Обновляем коэффициенты D_i
        double weightsSum = 0.0;
        for (int i = 0; i < trainingSet.Count; i++)
        {
         _weights[i] *= Math.Exp(-alpha * trainingSet.Labels[i] * hClassification[i]);
         weightsSum += _weights[i];
        }
        // Нормируем полученные коэффициенты
        for (int i = 0; i < trainingSet.Count; i++)
         _weights[i] /= weightsSum;
     
        // Запоминаем классификатор с найденным коэффициентом
        _h.Add(h);
        _alpha.Add(alpha);
     
        // Останавливаем обучение, если ошибка равна нулю
        if (epsilon == 0.0)
         break;
       }
      }


    Таким образом, после выбора оптимального классификатора h_{t} \, для распределения D_i, объекты x_{i} \,, которые классификатор h_{t} \, идентифицирует корректно, имеют веса меньшие, чем те, которые идентифицируются некорректно. Следовательно, когда алгоритм тестирует классификаторы на распределении D_{t+1}, он будет выбирать классификатор, который лучше идентифицирует объекты, неверно распознаваемые предыдущим классификатором.

    Пример



    В случае классификации таких данных:
    image

    классифицированый рисунок с помощю AdaBoost будет выглядеть так:
    image

    Для сравнения можно привести простой алгоритм, который для каждой точки определяет ее ближайшего соседа, класс которого известен. (Понятно, что затраты такого алгоритма очень велики.)
    image

    Заключение



    Как видим, алгоритм, построенный с помощью AdaBoost, классифицирует намного лучше, чем один классификатор, но и он имеет ошибки. Но простота и изящность алгоритма позволила ему войти в Top 10 algorithms in data mining. Надеюсь, код, приведенный в статье, помог вам разобраться с этим алгоритмом.

    Полноценный исходник программы и саму программу можно скачать здесь.
    P.S. Как продолжение статьи можно расмотреть тот случай, когда общий классификатор строится не как линейная функция слабых классификаторов, а, например, квадратичная. Авторы статьи утверждают, что нашли способ, как эффективно обучать в этом случае квадратичную функцию. Или же в продолжение статьи можно рассмотреть случай, когда классов объектов больше двух.
    Share post

    Comments 21

      +4
      не минусуйте меня, это мой первый пост на Хабре)
        +2
        Я знаком с такими алгоритмами (в теории), поэтому представляю их область применения, но всё же приведите пример использования в начале статьи, чтобы хоть было понятно, что Вы объясняете.
          +2
          Моей целью было объяснение именно самого алгоритма, основываясь на программе, которую я написал, чтобы объяснить эту методику объединения слабых классификаторов в более сильный. О самом же применении раньше рассказывал Indalo. На самом деле эта статья должна быть продолжена рассказом о том случае, когда сложный классификатор берется как квадратичная функция слабых, а не линейная как это принято, что не есть таким известным фактом.
        –6
        где ты был год назад? Мне как раз нужна была такая лабораторная работа. Пришлось писать самому
          +1
          Хорошая статья. Переноси в публичный блог. :) В «Алгоритмы» например.
            +1
            Спасибо. Перенес. :)
            +3
            Не могу сказать, что статья удалась. Для интуитивного подхода я бы: добавил картинок, убрал формулы, не писал бы сорс в статье, рассказал о ensemble, weak/strong learner и начал с Маркиза де Кондорсе

            К чему я это? К тому, что те кто «не в курсе» мало что узнали, так как материал подан далеко не с нуля и скорее всего не осел и не усвоился. Те кто знает о чём речь ничего нового не узнали. Получилось много Вики и мало Хабры. Выиграли те, кому не придётся теперь писать лабораторку самому…
              0
              К сожалению Вы правы… обещаю исправиться в следующей статье.
                +1
                Могу подкинуть свои универские слайды (на английском) по теме.
                  0
                  Да, спасибо! Киньте на почту! Возможно там есть что-то интересное о случае больше двух классов? Вы знакомы с работой, о которой я упоминал в статье? А именно, portal.acm.org/citation.cfm?id=1285185. Хочу о ней рассказать в следующей статье…
                    0
                    Вообще-то моей темой тогда были имплементация и тестирование мультикласовой версии, а квадратичными наработками я не знаком.

                    Слайды я предложил для расширения ваших знаний, а как источник картинок к этой статье — там как раз вводная по бусту есть с классическим примером слабого линейного классификатора :)
                      +1
                      Блин, slf-fix:
                      НЕ для расширения ваших знаний. Они на более низком уровне…
                        0
                        Извините, не понял Ваш последний комментарий…
                        з.ы. Жду слайди. :)
              +1
              В принципе, классификатор по ближайшему соседу в 2D можно реализовать достаточно эффективно. O(n log n) препроцессинг, O(log n) на запрос, где n — количество изначально классифицированных точек.
                +1
                И решается єто с помощью kd-tree :)
                  0
                  В kd-дереве O(log n) будет в среднем случае, с помощью диаграммы Вороного можно добиться и worst-case O(log n). С другой стороны, kd проще пишется и неплохо раширяется на большие размерности
                +2
                Автор молодец, действительно научные статьи публикуют редко, а эту можно применять для взлома капчи на хабре для действительно полезных приложений, например графики.

                Хочу добавить к winger:
                Поиск ближайшей точки реализуется через триангуляцию Делоне/диаграммы Вороного. Предмет очень хорошо изучен, особенно для двумерного случая и работает довольно быстро на персональном компьютере. Adaboosting ещё быстрее, и предназначен не столько для повседневного использования, сколько для встроенных систем, наподобие автопилота для самодельного летающего робота.
                  0
                  * про взлом капчи было в strike теге. Юзернейм, объясни, почему парсер мне не поверил, ну пожалуйста.
                    0
                    При отрицательной карме теги не работают
                    0
                    Чтобы уметь быстро отвечать на запросы, нужно на диаграмму Вороного сверху навесить какую-нибудь point-location структуру, типа уточнения триангуляции или метода трапециоидов.Алгоритм получается монструозный и скорее всего внутри O()шек прячутся большие константы, зато качество классификации в общем случае должно получиться лучше
                    0
                    Некропост:

                    Если возможно, обновите картинки и перезалейте код на github.

                    Only users with full accounts can post comments. Log in, please.