Роль простого классификатора

В этом разделе мы уделим внимание фундаменту всех методов усиления простых классификаторов - семейству простых классификаторов

Что это такое? Для ясности приведём пример: пусть входные данные это n-мерные вектора X = Rⁿ, пусть тогда

,
то есть это порог по k-той координате. Такой классификатор в англоязычной литературе носит имя "пень" (stump) - основа дерева.

Как при таком множестве H происходит выбор наилучшего классификатора h^{Θ, k} на каждой итерации (шаг алгоритма 2.a)? В данном случае делается следующее - для каждого k = 1 ..n, вычисляется порог Θ'_k, реализующий минимум взвешенной ошибки e_m, затем из полученных классификаторов h^{Θ, k}, k = 1 ..n выбирается соответствующий минимальной e_m.

Несмотря на свою простоту, этот классификатор, усиленный алгоритмом AdaBoost, дает весьма впечатляющие результаты. Система поиска объектов на изображении Viola-Jones находит 95% всех искомых объектов и с 0.0001% ложных срабатываний.

Какими свойствами должен обладать простой классификатор? В первую очередь, вероятность его ошибки должна быть хотя бы немного меньше 1/2, то есть он должен работать лучше чем "орел/решка":

Так же, простой классификатор должен быть максимально простой структуры (обладать малой VC-размерностью [11]) - это связано с оценкой ошибки обобщения сильного классификатора; более подробную информация можно найти здесь [1][3][4].

Самыми часто используемыми на практике простыми классификаторами являются пороги (stumps) и CART решающие деревья [12], [13].