Линейные решающие правила

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

= .

Рис. 4. Линейное решающее правило для распознавания
двух образов

Одна граница при этом разделяет области двух образов. Если >2, то требуется несколько линейных функций и граница является, вообще говоря, кусочно линейной. Для наглядности будем считать =2. Если на множестве объектов выполняется условие

,

если  – реализация первого образа ,

если  – реализация второго образа ,

то образы и  называют линейно разделимыми.

Существуют различные методы построения линейных решающих правил. Рассмотрим один из них, реализованный в 50-х годах Розенблатом, в устройствах распознавания изображений, названных персептронами (рис. 5).

 Пусть

где  – некоторый объект одного из образов, .

Рис. 5. Упрощённая схема однослойного персептрона

Выбор  осуществляется пошаговым образом. Текущее значение  заменяется новым  после предъявления персептрону очередного объекта обучающей выборки. Эта корректировка производится по следующему правилу:

1.  , если  и  или если  и .

2.  , если  и , .

3.  , если  и .

 Это правило вполне логично. Если очередной объект системой классифицирован правильно, то нет оснований изменять . В случае (2)  следует изменить так, чтобы увеличить . Предложенное правило удовлетворяет этому требованию. Действительно,

.

Соответственно в случае (3) .

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

  , если ,

  , если .

Если же выборки линейно неразделимы (рис. 6), то сходимость отсутствует и оценку , минимизирующую число неправильных распознаваний, находят методом стохастической аппроксимации.