§ 9. Упорядочение по относительным расстояниям

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

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

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

.

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

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

,

а значит, и

.

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

Следовательно, математическое ожидание частоты ошибок в этом случае оценивается

.

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

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

математическое ожидание отношения , где  - диаметр множеств  и , а  – расстояние между ними. По существу, не меняя доказательства, убеждаемся, что

.

Аналогичные утверждения справедливы и для некоторых других (но не для любых!) алгоритмов построения разделяющей гиперплоскости, основанных на минимизации эмпирического риска, в частности, для метода обобщенного портрета (см. главу XIV).

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

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

.

Согласно теореме, качество решения задачи в первом подпространстве оценивается величиной

,

в то время как качество решения во втором – величиной

.

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

Таким образом, критерий  позволяет оценивать качество подпространств при построении линейных решающих правил. На практике же пользоваться этим критерием трудно: как правило, нам не известны величины  и .

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

Хотелось бы построить метод, который позволял бы оценивать качества подпространств не по величинам  и , а по их оценкам.

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

В заключение этого параграфа обратим внимание читателя на интересную аналогию, которая может быть проведена между рассматриваемым здесь критерием упорядочения и хорошо изученным в классическом дискриминантном анализе понятием – расстоянием Махаланобиса [62].

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

Расстояние Махаланобиса

                     (6.8)

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

.

Геометрически расстояние Махаланобиса выражает отношение расстояния между математическими ожиданиями векторов двух различных классов к дисперсии величины проекции векторов каждого класса на направляющий вектор разделяющей гиперплоскости:

 .               (6.9)

Структура расстояния Махаланобиса (6.8), (6.9) очень напоминает структуру ранее исследованного отношения

.

И расстояние Махаланобиса и число  характеризуют взаимное расположение множеств с помощью относительного расстояния. В первом случае это относительное расстояние между «центрами» множеств, во втором случае – относительное расстояние между выпуклыми оболочками непересекающихся множеств.

Однако, в отличие от характеристики «разделимости» Махаланобиса, характеристика  с уменьшением размерности пространства может расти, а вместе с ним (согласно теореме) растет и оценка математического ожидания вероятности правильной классификации с помощью гиперплоскости, построенной по выборке фиксированного объема.

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

Заметим, что расстояние Махаланобиса характеризует нижнюю оценку качества решающего правила, построенного по выборкам фиксированного объема, а число  – верхнюю оценку этого качества. То, что оценки по своей структуре близки, свидетельствует об эффективности полученного критерия оптимизации.