4.5.2. Кусочно-линейные разделяющие функции.

Линейные разделяющие функции находят широкое применение в задачах.

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

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

Рис. 4.11. Четыре распределения: а) байесовский классификатор; б) кусочно-линейный классификатор.

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

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

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

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

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

(функция исключена из рассмотрения).

Рис. 4.12. Реализация кусочио-лниейиого классификатора.

Наличие заштрихованной области на рис. 4.11, б показывает, что М областей определяемые условиями (4.116), не обязательно покрывают пространство. Если объект попадает в эту область, то кусочнолинейный классификатор не может принять решение о его

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

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

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

Вероятность ошибки решения для каждого класса 8 можно выразить через -мерную функцию распределения вероятности:

(функция — исключена из рассмотрения). Тогда общая ошибка решения

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

Кратко отметим три приближенных метода решения задачи.

1) Можно подстраивать коэффициенты так, чтобы минимизировать вероятность ошибки решения определяемую формулой (4.118).

Поскольку для в трудно получить явное математическое выражение, то 8 следует оценивать численными методами всякий раз, когда корректируются параметры V и Если Случайные величины X для всех классов распределены по нормальному закону, то возможно некоторое упрощение решения, так как а этом случае разделяющие функции также распределены нормально, а для существует явное

математическое выражение. Однако даже в этом случае интегрированно -мерного нормального распределения в первом квадранте, по-видимому, проще выполнить численным методом, например, таким, как метод Монте-Карло.

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

3) Можно задать требуемый выход кусочно-линейной разделяющей функции и для нахождения оптимальных значений минимизировать среднеквадратичную ошибку между требуемым и действительным выходом.

Таблица 4.2

Вероятность ошибки для задачи с четырьмя классами

Требуемые выходные величины могут быть фиксированными или подстраиваемыми, как переменные, на которые наложены ограничения. К сожалению,

даже для случая кусочно-линейной разделимости классов не существует доказательства сходимости этой процедуры.

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

В табл. 4.2 для различных пар классов приведены вероятности ошибок обусловленных использованием соответствующих оптимальных линейных классификаторов. Кроме того, в табл. 4.2 приводится сумма вероятностен ошибок: . В случае, когда кусочно-линейный классификатор был синтезирован с помощью линейных классификаторов без дополнительной коррекции параметров, ошибка решения вычислялась по формулам (4.117) и (4.118) и обозначена в таблице 4.2 через .

Рис. 4.13. Изменение общей ошибки в зависимости от компонент вектора [Фукунага, 1970а]. Примечание: компонента вектора

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

вероятности являются преобладающими слагаемыми в Как видно из рис. 4.13, оптимальное значение смещено относительно значения , соответствующего линейному классификатору для классов Однако при этом изменение ошибки находится в пределах 0,3%. Влияние же других компонент вектора V намного меньше. Этот результат оправдывает для данного частного примера применение совокупности оптимальных классификаторов без дополнительной коррекции параметров.