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

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

= .

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

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

,

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

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

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

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

Пусть

если , , если ,

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

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

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

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

2. , если и , .

3. , если и .

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

.

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

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

, если ,

, если .

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