§ 9. Упорядочение по относительным расстояниямПриведенные выше метод упорядочения по размерностям и вытекающие из него рекомендации для построения оптимального алгоритма представляются достаточно грубыми: они учитывают только внешнюю характеристику задачи – размерность и никак не принимают во внимание более тонкие ее характеристики, например геометрию расположения разделяемых множеств. О существовании иных и, возможно, более эффективных методов упорядочения свидетельствуют также и оценки качества решающего правила, которые могут быть получены для персептрона, использующего многократно обучающую последовательность. Рассмотрим такие оценки качества. В главе I была доказана теорема Новикова, утверждающая, что если в спрямляющем пространстве два множества векторов разделимы гиперплоскостью, расстояние от начала координат до выпуклой оболочки множеств Теорема 6.1. Качество персептронного алгоритма
Доказательство. Доказательство этой теоремы основывается на доказанном в § 7 утверждении о несмещенности оценок, полученных с помощью процедуры «скользящий контроль». Поэтому вместо оценки качества нам достаточно оценить математическое ожидание частоты ошибок при скользящем контроле. При скользящем контроле из обучающей последовательности выделяется один элемент, на оставшейся части проводится обучение, строится решающее правило и затем проверяется классификация выделенного элемента этим решающим правилом. Эта операция проделывается с каждым элементом. Если при использовании полной обучающей последовательности в ходе обучения персептрон всегда правильно опознает элемент
а значит, и
Итак, для любой обучающей последовательности число ошибок при скользящем контроле не превосходит Следовательно, математическое ожидание частоты ошибок в этом случае оценивается
Теорема доказана. Теорема может быть несколько усилена. Рассмотрим выпуклые оболочки математическое ожидание отношения
Аналогичные утверждения справедливы и для некоторых других (но не для любых!) алгоритмов построения разделяющей гиперплоскости, основанных на минимизации эмпирического риска, в частности, для метода обобщенного портрета (см. главу XIV). Доказанное здесь утверждение показывает, что эффективность обучения тем выше, чем больше относительное расстояние между классами. Рассмотрим теперь два подпространства
Согласно теореме, качество решения задачи в первом подпространстве оценивается величиной
в то время как качество решения во втором – величиной
Поскольку никаких иных сведений о качестве решающих правил нет, то, очевидно, следует предпочесть то правило, для которого отношение Таким образом, критерий Конечно, можно их оценить по выборке и с помощью соответствующих оценок вычислять качество подпространств. Однако такой прием будет уже эвристическим. Теорема 6.1 справедлива не для оценок величин Хотелось бы построить метод, который позволял бы оценивать качества подпространств не по величинам Такому методу будут посвящены следующие параграфы. В них будет приведен метод, позволяющий эффективно выделять экстремальные подпространства. Однако подобные алгоритмы решения задачи обучения распознаванию образов возможны лишь в постановке, отличной от той, которую мы рассматривали до сих пор. В заключение этого параграфа обратим внимание читателя на интересную аналогию, которая может быть проведена между рассматриваемым здесь критерием упорядочения и хорошо изученным в классическом дискриминантном анализе понятием – расстоянием Махаланобиса [62]. Пусть требуется построить гиперплоскость, разделяющую два множества векторов Расстояние Махаланобиса
позволяет вычислить вероятность правильной классификации оптимального решающего правила
Геометрически расстояние Махаланобиса выражает отношение расстояния между математическими ожиданиями векторов двух различных классов к дисперсии величины проекции векторов каждого класса на направляющий вектор разделяющей гиперплоскости:
Структура расстояния Махаланобиса (6.8), (6.9) очень напоминает структуру ранее исследованного отношения
И расстояние Махаланобиса и число Однако, в отличие от характеристики «разделимости» Махаланобиса, характеристика Характеристика разделимости Махаланобиса уменьшается с уменьшением размерности пространства и вместе с ней уменьшается вероятность правильной классификации с помощью оптимального в этом подпространстве линейного решающего правила. Заметим, что расстояние Махаланобиса характеризует нижнюю оценку качества решающего правила, построенного по выборкам фиксированного объема, а число
|