§ 13. Алгоритм Кора

Все рассмотренные до сих пор конструктивные идеи алгоритмов обучения распознаванию образов были связаны с построением в спрямляющем пространстве разделяющей гиперплоскости. Алгоритм обучения распознаванию образов «Кора» исходит из иных конструктивных идей.

Пусть обучающая последовательность распадается на два множества векторов – множество векторов первого класса  и множество векторов второго, класса . Задается множество характеристических функций , которые называются признаками. Из множества признаков алгоритм выделяет так называемые достаточные признаки. Достаточным признаком для векторов первого класса называется признак , который на всех векторах второго класса принимает значение 0, а на некоторых векторах первого класса 1.

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

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

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

Для каждого класса отбор конъюнкций (признаков) производится по следующим правилам:

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

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

3. Из оставшихся достаточных признаков производится окончательный отбор  признаков. Принцип отбора таков, чтобы в окончательный набор вошли признаки, которые «покрывают» все множество примеров, данное на обучение, и чтобы, по возможности, все примеры обладали приблизительно одинаковым количеством признаков (признаки должны «покрывать» множество примеров «равномерно»).

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

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

.

Следовательно,  и, согласно (5.17), в случае, если величина эмпирического риска близка к нулю, вероятность неправильной классификации с помощью найденного правила уклонится от эмпирической оценки не более чем на величину

.

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