AdaBoost в OpenCV / OpenCV / Recog.ru - Распознавание образов для программистов


AdaBoost в OpenCV

AdaBoost – алгоритм машинного обучения. Алгоритмы типа Boosting предназначены для обучения T «слабых» классификаторов. По отдельности эти классификаторы как правило просты. Каждый классификатор Kt (t = {1, 2, … T}) ассоциирован с весом at, который применяется при объединении результатов со всех классификаторов. Входной вектор признаков
X = (x1, x2, …xi, …, XM)
(где i – номер признака) помечается бинарными метками yi = {-1, +1} (для других Boosting алгоритмов может быть диапазон значений).
Распределение Dt(i), которое должно быть инициализировано заранее, сообщает сколько «стоит» неправильная оценка каждого признака. Ключевой особенностью Boostingа является то, что, когда алгоритм прогрессирует, эта «стоимость» будет развиваться так, что обучение «слабых» классификаторов будет сфокусировано на тех признаках, которые ранее в «слабых» классификаторах давали плохие результаты.
Алгоритм:
1. D1(i) = 1/m, для i = 1,...,m.
2. Для t = 1,...,T:
2.1. Найти классификатор Kt минимизирующий Dt(i) весовую ошибку:

где

Для yj ≠ K_j(X), пока ε_j < 0.5, иначе выход.
2.2. Установить для K_t вес

где ε_t – минимальная ошибка на предыдущем шаге.
2.3. Обновить весовые коэффициенты для признаков

где Zt нормализует по всем признакам.

По окончании описанного алгоритма берется новый входной вектор X и классифицируется на основе взвешенной суммы

Более подробно теорию вы можете почитать в других источниках, а мы посмотрим практический пример. В библиотеке OpenCV – это файл letter_recog.cpp.
Для обучения используется база letter-recognition.data с сайта http://archive.ics.uci.edu/ml/. Выборка состоит из 20000 элементов. Каждый элемент состоит из 17 атрибутов: 1 – категория элемента, т.е. символ текста A, B, C, D… — всего 26 вариантов; 16 атрибутов – признаки распознавания. О признаках распознавания можно почитать в описании выборки на указанном сайте. Для обучения используется 10000 элементов, для проверки тоже 10000 элементов.
Пример letter_recog.cpp был упрощен следующим образом:
#include "opencv2/core/core_c.h"
#include "opencv2/ml/ml.hpp"
#include <cstdio>
#include <vector> 

int
read_num_class_data( const char* filename, int var_count,
                     CvMat** data, CvMat** responses )
{
    const int M = 1024;
    FILE* f = fopen( filename, "rt" );
    CvMemStorage* storage;
    CvSeq* seq;
    char buf[M+2];
    float* el_ptr;
    CvSeqReader reader;
    int i, j;

    if( !f )
        return 0;

    el_ptr = new float[var_count+1];
    storage = cvCreateMemStorage();
    seq = cvCreateSeq( 0, sizeof(*seq), (var_count+1)*sizeof(float), storage );

    for(;;)
    {
        char* ptr;
        if( !fgets( buf, M, f ) || !strchr( buf, ',' ) )
            break;
        el_ptr[0] = buf[0];
        ptr = buf+2;
        for( i = 1; i <= var_count; i++ )
        {
            int n = 0;
            sscanf( ptr, "%f%n", el_ptr + i, &n );
            ptr += n + 1;
        }
        if( i <= var_count )
            break;
        cvSeqPush( seq, el_ptr );
    }
    fclose(f);

    *data = cvCreateMat( seq->total, var_count, CV_32F );
    *responses = cvCreateMat( seq->total, 1, CV_32F );

    cvStartReadSeq( seq, &reader );

    for( i = 0; i < seq->total; i++ )
    {
        const float* sdata = (float*)reader.ptr + 1;
        float* ddata = data[0]->data.fl + var_count*i;
        float* dr = responses[0]->data.fl + i;

        for( j = 0; j < var_count; j++ )
            ddata[j] = sdata[j];
        *dr = sdata[-1];
        CV_NEXT_SEQ_ELEM( seq->elem_size, reader );
    }

    cvReleaseMemStorage( &storage );
    delete[] el_ptr;
    return 1;
} 

int build_boost_classifier( char* data_filename )
{
    const int class_count = 26;
    CvMat* data = 0;
    CvMat* responses = 0;
    CvMat* var_type = 0;
    CvMat* temp_sample = 0;
    CvMat* weak_responses = 0;

    int ok = read_num_class_data( data_filename, 16, &data, &responses );
    int nsamples_all = 0, ntrain_samples = 0;
    int var_count;
    int i, j, k;
    double train_hr = 0, test_hr = 0;
    CvBoost boost;

    if( !ok )
    {
        printf( "Could not read the database %s\n", data_filename );
        return -1;
    }

    printf( "The database %s is loaded.\n", data_filename );
    nsamples_all = data->rows;
    ntrain_samples = (int)(nsamples_all*0.5);
    var_count = data->cols;

    CvMat* new_data = cvCreateMat( ntrain_samples*class_count, var_count + 1, CV_32F );
    CvMat* new_responses = cvCreateMat( ntrain_samples*class_count, 1, CV_32S );

    // 1. unroll the database type mask
    printf( "Unrolling the database...\n");
    for( i = 0; i < ntrain_samples; i++ )
    {
        float* data_row = (float*)(data->data.ptr + data->step*i);
        for( j = 0; j < class_count; j++ )
        {
            float* new_data_row = (float*)(new_data->data.ptr +
                            new_data->step*(i*class_count+j));
            for( k = 0; k < var_count; k++ )
                new_data_row[k] = data_row[k];
            new_data_row[var_count] = (float)j;
            new_responses->data.i[i*class_count + j] = responses->data.fl[i] == j+'A';
        }
    }

    // 2. create type mask
    var_type = cvCreateMat( var_count + 2, 1, CV_8U );
    cvSet( var_type, cvScalarAll(CV_VAR_ORDERED) );
    // the last indicator variable, as well
    // as the new (binary) response are categorical
    cvSetReal1D( var_type, var_count, CV_VAR_CATEGORICAL );
    cvSetReal1D( var_type, var_count+1, CV_VAR_CATEGORICAL );

    // 3. train classifier
    printf( "Training the classifier (may take a few minutes)...\n");
    boost.train( new_data, CV_ROW_SAMPLE, new_responses, 0, 0, var_type, 0,
        CvBoostParams(CvBoost::REAL, 100, 0.95, 5, false, 0 ));
    cvReleaseMat( &new_data );
    cvReleaseMat( &new_responses );
    printf("\n");
   
    temp_sample = cvCreateMat( 1, var_count + 1, CV_32F );
    weak_responses = cvCreateMat( 1, boost.get_weak_predictors()->total, CV_32F );

    // compute prediction error on train and test data
    for( i = 0; i < nsamples_all; i++ )
    {
        int best_class = 0;
        double max_sum = -DBL_MAX;
        double r;
        CvMat sample;
        cvGetRow( data, &sample, i );
        for( k = 0; k < var_count; k++ )
            temp_sample->data.fl[k] = sample.data.fl[k];

        for( j = 0; j < class_count; j++ )
        {
            temp_sample->data.fl[var_count] = (float)j;
            boost.predict( temp_sample, 0, weak_responses );
            double sum = cvSum( weak_responses ).val[0];
            if( max_sum < sum )
            {
                max_sum = sum;
                best_class = j + 'A';
            }
        }

        r = fabs(best_class - responses->data.fl[i]) < FLT_EPSILON ? 1 : 0;

        if( i < ntrain_samples )
            train_hr += r;
        else
            test_hr += r;
    }

    test_hr /= (double)(nsamples_all-ntrain_samples);
    train_hr /= (double)ntrain_samples;
    printf( "Recognition rate: train = %.1f%%, test = %.1f%%\n",
            train_hr*100., test_hr*100. );

    printf( "Number of trees: %d\n", boost.get_weak_predictors()->total );
    

    cvReleaseMat( &temp_sample );
    cvReleaseMat( &weak_responses );
    cvReleaseMat( &var_type );
    cvReleaseMat( &data );
    cvReleaseMat( &responses );

    return 0;
}
 

int main()
{
	// Чтение данных из файла
	build_boost_classifier( "letter-recognition.data");
	return 0;
}


Все действия происходят в функции build_boost_classifier, которую мы и рассмотрим. Первоначально с помощью описанной функции read_num_class_data осуществляется загрузка файла, т.е. создание матрицы с признаками (16 признаков на элемент) read_num_class_data, а также матрицы responses, в которой указывается — к какому классу относится образ. Далее происходит инициализация, включая создание матриц для обучения. Заметим, что количество элементов для обучений в матрице new_data умножается на количество классов (26 различных букв), а размерность не 16 элементов, а 17. Матрица new_responses также увеличивается в размерах в class_count раз (26). Ниже (после // 1. unroll the database type mask) происходит заполнение матриц и становится понятно, для чего изменялись размеры матриц.
Каждый элемент обучающей выборки соответствует только одному классу – букве A, S, T,….и т.п. Однако также необходимо учитывать, что этот элемент говорит нам, что подобная комбинация признаков не может быть у других классов образов. Поэтому все признаки дублируются по количеству классов. Увеличение до 17 элементов происходит потому, что мы с каждым из этих признаков связываем номер класса (0, 1,… 25).
Что касается матрицы результатов – то там указывается TRUE или FALSE для каждого класса, которое и говорит, к какому классу относятся эти данные. Т.е. из 26 классов, только один будет TRUE для одного элемента обучающей выборки.
После заполнение матриц создается еще одна матрица-маска, которая разделяет данные на признаки образов и на категории образов:
CV_VAR_ORDERED – числовое значение признака образа;
CV_VAR_CATEGORICAL – категория образа.
После этого переходим к обучению – функция train из класса CvBoost. Не вдаваясь в подробности описания класса, рассмотрим функцию train.

bool CvBoost::train(
	const Mat& trainData, 
	int tflag, 
	const Mat& responses, 
	const Mat& varIdx=Mat(), 
	const Mat& sampleIdx=Mat(), 
	const Mat& varType=Mat(), 
	const Mat& missingDataMask=Mat(), 
	CvBoostParams params=CvBoostParams(), 
	bool update=false 
);

В описании функции указано, что она совпадает с CvStatModel::train(). Ответы должны быть категорическим, что означает, что boosted деревья не могут быть построены для регрессии, и там должно быть два класса.
Параметры:
trainData
Данные для обучения. По умолчанию вектор данных находится в rows.
tflag
Флаг, который указывает в каком формате данные:
CV_ROW_SAMPLE – означает, что вектор данных располагается в row (строках);
CV_COL_SAMPLE – в столбцах.
responses
Ответы.
varIdx
В документации про это написано мало, но я так понимаю, что этот параметр для того, чтобы использовать не все выборку для обучения, а часть. Т.е. выбираем подмножество из входного множества, если не надо – ставим 0.
sampleIdx
Вроде бы имеет тот же смысл что и varIdx, хотя в документации опять же не освещено. Возможно один параметров для данных, другой для ответов. Но его обычно не используют и пишут также 0.
varType
Тип входных переменных в виде матрицы, описывающей где данные, а где категории этих данных.
missingDataMask
Поскольку некоторые обучающие алгоритмы обрабатывают отсутствие данных (например, не был измерен один из признаков), то можно заполнить эту матрицу, указав какие признаки в каких элементах пропустить. Если не используется, то указывается 0.
params
Настройки Boosted-классификатора. Передается структура CvBoostParams.
update
Указывает, будет ли классификатор обновляться, по умолчанию – нет.

CvBoostParams::CvBoostParams(
	int boost_type, 
	int weak_count, 
	double weight_trim_rate, 
	int max_depth, 
	bool use_surrogates, 
	const float* priors
);

Параметры:
boost_type
Тип алгоритма:
CvBoost::DISCRETE Дискретный AdaBoost.
CvBoost::REAL Реальный AdaBoost.
CvBoost::LOGIT LogitBoost.
CvBoost::GENTLE Нежный AdaBoost.
weak_count
Количество «слабых» классификаторов.
weight_trim_rate
Пороговое значение – уровень значимость. Ставим 0.95, чтобы уменьшить время эксперимента, но при этом оставить хорошее качество.
max_depth
Максимальная глубина дерева.
use_surrogates
priors
Массив априорных вероятностей классов, отсортированный по значению класса.

В приведенном примере написано следующее:
boost.train( new_data, CV_ROW_SAMPLE, new_responses, 0, 0, var_type, 0,
        CvBoostParams(CvBoost::REAL, 100, 0.95, 5, false, 0 ));

На первый взгляд непонятно, почему размер матрицы будет в этом случае из 18 элементов. Однако, если посмотреть размерность new_data + размерность new_responses, то будет 17 +1 = 18. Ну и далее: реальный AdaBoost, 100 «слабых» классификаторов, 0.95 уровень значимости, 5 максимальная глубина.

Далее идет проверка результатов обучения на тренировочной и проверочной выборках. Поэлементно выбираются данные, и вызывается функция:

float CvBoost::predict(
	const CvMat* sample, 
	const CvMat* missing=0, 
	CvMat* weak_responses=0, 
	CvSlice slice=CV_WHOLE_SEQ, 
	bool raw_mode=false, 
	bool return_sum=false 
);

Параметры:
sample
Входная выборка признаков одного элемента.
missing
Дополнительная маска, которая может указывать, какие признаки надо пропустить. Если не надо ничего пропускать, то 0.
weak_responses
Необязательный выходной параметр, вектор с плавающей точкой с ответами каждого отдельного слабого классификатора. Число элементов в векторе должна быть равна длине среза.
slice
Непрерывное подмножество последовательности слабых классификаторов, которые будут использоваться для предсказания. По умолчанию, все слабые классификаторы используются.
raw_mode
Указывать false.
return_sum
Если true, то вернуть сумму голосов.

В примере данная функция вызывается для каждого класса, вычисляя, для какого класса сумма весов «слабых» классификаторов weak_responses больше. Ну и собственно, если результат такой же, как и в ответах к признакам, то увеличиваем значения правильно распознанных ответов для обучаемой (train_hr) и проверочной (test_hr) выборок. В конце на экран выводится результат достоверности распознавания для обучаемой и проверочной выборок, а также число «слабых» классификаторов.



Да, 70% это небольшой процент правильного распознавания. Однако здесь не стоит грешить на сам алгоритм обучения. Во-первых, надо разбираться, что за признаки использовались в выборке и собственно, что за символы – качество. Во-вторых, для обучаемых методов, подобная выборка, при сложных и постоянно меняющихся условиях, будет недостаточна.
Но в целом, здесь был рассмотрен один из алгоритмов обучения, который вы можете использовать в своих целях.
  • 0
  • 27 апреля 2013, 10:01
  • vidikon

Комментарии (0)

RSS свернуть / развернуть

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.