3.8.3. ЕМКОСТЬ РАЗДЕЛЯЮЩЕЙ ПЛОСКОСТИ

Наличие избыточных данных для классификации столь же важно, как и для оценки. В качестве сравнительно простого примера рассмотрим разбиение d-мерного пространства признаков гиперплоскостью \ѵ*х+Шо=Оі Допустим, что имеется общее расположение п выборочных точек^), с каждой из которых можно сопоставить метку соі или ©2. Среди 2" возможных дихотомий (разделений на два класса) п точек в d-мерном пространстве имеется некоторая доля f{n, d), так называемых линейных дихотомий. Это такая маркировка точек, при которой существует гиперплоскость, отделяющая точки, помеченные wi, от точек, помеченных соа. Можно показать, что эта

доля определяется выражением

Г рафик этой функции для разных значений d приведен на рис. 3.4. Заметим, что все дихотомии для d+1 и менее точек линейны. Это значит, что гиперплоскость не ограничивается требованием пра вильной классификации d+l или меньшего числа точек. Фактически при большом d, пока п не составляет значительной части от 2(d+l), это не означает, что задача начинает становиться трудной. При значении числа п=2 {d+1), которое иногда называется емкостью гиперплоскости, половина из возможных дихотомий еще линейна.

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