5.12.1. МЕТОД КЕСЛЕРА

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

при этом X относится к тому классу, которому соответствует наибольшая gi (х). Это довольно естественное обобщение с точки зрения результатов, полученных в гл. 2 для задачи с многомерным нормальным распределением. Следующий шаг, очевидно, может быть связан с обобщением понятия линейной разделяющей функции; введем вектор-функцию у(х), зависящую от х, и напишем выражение

где X снова ставится в соответствие ю^, если gi(x) >gj(x) для всех /^і.

Обобщение процедур, рассмотренных для линейного классификатора двух к^іассов, на случай линейной машины для многих классов наиболее просто осуществляется при линейно разделяемых выборках. Пусть имеется множество помеченных выборок уі, Уг, . . .

     у„, причем число Пі выборок, принадлежащих подмножеству

&і, помечены о),, число «2 выборок, принадлежащих подмножеству 2/2, помечены Юз, ... и число Пс выборок подмножества 2/с помечены Юс- Говорят, что данное множество линейно разделяемо в том случае, если существует такая линейная машина, которая правильно классифицирует все выборки. Далее, если эти выборки линейно разделимы, то существует множество весовых векторов Яі, . . ., ас, таких, что если    то

для всех

Одним из преимуществ такого определения является то, что, несколько видоизменив неравенства (89), можно свести задачу для многих классов к случаю двух классов. Предположим на минуту,

что у ^ 2/і, так что выражение (89) принимает вид

Это множество (с — 1) неравенств можно интерпретировать как требование существования cd-мерного весового вектора

который бы правильно классифицировал все (с—1) cd-мерных выборок

В более общем случае, если у то формируется (с — I) семерных выборок Tj,7 с разбиением тіг;- на cd-мерные подвекторы, причем t-й подвектор равен у, /-й равен —у, а все остальные являются нулевыми. Очевидно, что если a^Ti,,>0 для всех }фі, то линейная машина, соответствующая компонентам вектора а, будет правильно классифицировать у.

В описанной процедуре, которая была предложена К. Кеслером, размерность исходных данных увеличивается в с раз, а число выборок—в с—1 раз; это делает ее непосредственное применение достаточно трудоемким и поэтому малопригодным. Значение же данного метода определяется тем, что он позволяет свести процедуру коррекции ошибок в задаче многих классов к случаю двух классов, а последнее чрезвычайно важно для доказательства- сходимости указанной процедуры.