§ 12. Некоторые статистические особенности метода обобщенного портрета

В главе VI были получены оценки качества алгоритмов, строящих разделяющие гиперплоскости методом минимизации эмпирического риска.

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

,

где  – константа,  – емкость класса.

Были получены и верхние оценки качества. Верхние оценки были двух типов – зависящие от размерности пространства (эти оценки следует из общей теории равномерной сходимости) и оценки, зависящие от относительного расстояния (эти оценки следуют из обобщенной теоремы Новикова 6.2).

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

Итак, пусть задача такова, что для любой выборки длины  при заданном параметре  существует обобщенный портрет множества  относительно .

Оказывается, что при этом качество  алгоритма, использующего метод обобщенного портрета, может быть оценено:

,                    (14.36)

где  – размерность пространства.

Эта оценка может быть еще усилена. В § 3 было показано, что обобщенный портрет  всегда может быть разложен по своим крайним векторам в виде

.

Это разложение, вообще говоря, не единственно. Назовем крайний вектор информативным, если он входит с ненулевым весом во все разложения вектора . Обозначим через  – математическое ожидание числа информативных векторов в выборке длины . Ниже будет показано, что справедлива оценка

.                    (14.37)

Будет показано также, что всегда имеет место неравенство

.

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

Для вывода оценок (14.36) и (14.37) воспользуемся свойством несмещенности оценки скользящего контроля (см. § 7 главы VI). Несмещенность означает, что математическое ожидание частоты ошибок на экзамене после обучения на последовательности длины  равно математическому ожиданию частоты ошибок при скользящем контроле на последовательности длины . Применительно к методу обобщенного портрета скользящий контроль проводится так: из обучающей выборки последовательно (каждый раз по одному) удаляются векторы ; по оставшейся части выборки строится обобщенный портрет  и проверяется правильность опознания удаленного вектора; после этого подсчитывается частота ошибок.

Справедлива теорема

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

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

В самом деле, если вектор  не является информативным, то существует разложение обобщенного портрета

,

; , , ,

, ,                 (14.38)

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

или

,

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

Из теоремы, с учетом несмещенности оценки скользящего контроля, немедленно вытекает неравенство (14.37).

Покажем еще, что число информативных векторов никогда не превосходит размерность пространства . Для этого достаточно построить разложение вида (14.38), в которое с ненулевым весом входит не более  векторов.

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

,

причем в это разложение входят только те векторы, которые входят в (14.38) с ненулевым весом, и по крайней мере одно  положительно.

Тогда выражение

                     (14.39)

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

Для метода обобщенного портрета при  удается получить также оценку качества, зависящую от относительного расстояния между классами. При  оценка совпадает с выведенной в главе VI (теорема 6.2) оценкой качества для персептронного алгоритма с многократным повторением обучающей последовательности, а именно:

,                 (14.40)

где

,

 – расстояние от начала координат до выпуклой оболочки множества векторов , . Математическое ожидание берется по всем выборкам фиксированной длины.

Нетрудно убедиться, что число  и модуль обобщенного портрета, полученного при , связаны соотношением

.

Если, как и раньше, воспользоваться несмещенностью оценки скользящего контроля, то для вывода (14.40) достаточно доказать следующую теорему.

Теорема 14.12. Число ошибок при скользящем контроле для метода обобщенного портрета при  не превосходит .

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

Соответственно  – обобщенный портрет. Обозначим через  точку, доставляющую максимум функции  на множестве , . Очевидно, что ей соответствует обобщенный портрет, построенный по выборке без вектора :

.

Обозначим через  значение функции  в точке  , , . Очевидно, что

и одновременно

.

Поэтому

.                    (14.41)

Далее,

.

Для крайнего вектора

.                (14.42)

Будем считать далее, что обобщенный портрет  неправильно опознает вектор . Это значит, что

.                   (14.43)

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

Исследуем теперь левую часть неравенства (14.41). Для этого рассмотрим один шаг максимизации функции  из точки  вдоль оси  и выберем оптимальное значение . Имеем

.

Отсюда получаем оптимальное значение :

.

Увеличение  на этом шаге составит

.

Так как  не больше, чем приращение функции при полной максимизации, то

.                      (14.44)

Объединяя (14.41), (14.42), (14.44), получим

,

откуда, учитывая (14.43)

.

Аналогично оценивается :

.

Учитывая, что , , имеем

,

.

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

,

где  и  берутся только по тем векторам, которые неправильно опознаются при скользящем контроле.

Далее,

.

Окончательно при

.

При

.

В случае

.

Теорема доказана.