4.2. КЛАССИФИКАЦИЯ ОБРАЗОВ КАК ЗАДАЧА ТЕОРИИ СТАТИСТИЧЕСКИХ РЕШЕНИЙ

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

ведет с природой. Этот процесс аналогичен игре двух лиц с нулевой суммой, в которой игроком А является природа, а игроком В — классификационный механизм системы распознавания. Игрой с нулевой суммой называется такая игра, в которой выигрыш одного участника точно равен по величине проигрышу другого участника. В играх такого типа используются различные стратегии, в частности байесовская стратегия, минимаксная стратегия и стратегия Неймана — Пирсона. Задача классификационного механизма заключается в том, чтобы определить такое оптимальное решение, которое обеспечит минимизацию среднего риска или стоимости потерь.

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

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

и

то пространство представляет собой множество пар

Матрица размера элементами

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

использует стратегию , а игрок А — стратегию . Принято считать, что положительное значение потерь представляет истинные потери, а нулевое и отрицательное значение потерь — выигрыш.

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

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

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

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

в теории статистических решений эту величину часто называют условным средним риском или условными средними потерями.

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

Воспользовавшись формулой Байеса

выражение (4.2.5) можно представить в следующем виде:

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

При и выборе стратегии 1 средние потери для предъявленного образа равны

а при выборе стратегии 2 —

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

или, что то же самое,

Обычно считается, что При этом допущении выражение (4.2.12) приводит к получению условий

выполнение которых определяет зачисление образа в класс Левую часть неравенства (4.2.13) часто называют отношением правдоподобия:

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

1) образ зачисляется в класс если выполняется условие

2) образ зачисляется в класс если выполняется условие

3) решение выбирается произвольным образом, если имеет место равенство

Величину часто называют пороговым значением и используют для ее определения следующее выражение:

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

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

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

Рис. 4.1. Пример простой задачи классификации.

Пусть и — априорные вероятности того, что переданными символами были 0 и 1 соответственно. Пусть матрица потерь имеет вид

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

а плотность вероятности принятого сигнала при условии передачи символа 1 — выражением

Итак, отношение правдоподобия имеет вид

и, следовательно, принимается решение о принадлежности классу если выполнены условия

Другими словами, применение байесовского решающего правила приводит к выводу о передаче символа 0, если выполнено условие

Эти результаты совпадают с интуитивными предположениями только в тех случаях, когда или

В общем случае разделения на несколько классов образ причисляется к классу если условие справедливо при другими словами, образ причисляется к классу если справедливо условие

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

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

Байесовский классификатор обеспечивает отнесение образа к классу если выполняется условие

или условие

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

причем образ зачисляется в класс если для него выполняется условие при всех Это соответствует случаю 3 разбиения на несколько классов, рассмотренному в § 2.2.

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

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

Формулы (4.2.21) и (4.2.23) выражают два различных, хотя и эквивалентных подхода к решению одной и той же задачи. Поскольку оценка априорной вероятности классов , обычно не вызывает затруднений, основное различие этих двух постановок заключается в том, что в первом случае используется функция правдоподобия , а во втором — вероятность принадлежности образа классу .

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

Рис. 4.2. Принципиальная схема байесовского классификатора.

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

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

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

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