Функции правдоподобия

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

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

Представим игру формально в виде тройки G = (Y, Z, L), где Y и Z — множества произвольной природы, L — ограниченная числовая функция, определённая на множестве прямых произведений (Y × Z). Элементы y ∈ Y и
z ∈ Z представляют стратегии первого и второго игроков соответственно, а функция L интерпретируется как функция выигрыша или функция потерь. На каждом шаге игры первый игрок выбирает элемент своей стратегии y ∈ Y, а второй — элемент z ∈ Z своей. Если побеждает первый игрок, он получает выигрыш, равный значению L (y, z), который выплачивается вторым игроком. Если побеждает второй игрок, то сумму L (y, z) выплачивает ему первый игрок. Игра G называется конечной, если множества Y и Z содержат конечные количества элементов:

В этом случае функцию L можно задать в виде матрицы размером M × N с элементами L_ij = L (y_i, z_j), которую называют матрицей выигрышей или матрицей потерь. Элемент L_ij матрицы потерь определяет проигрыш первого игрока, выбравшего ход y_i, при условии, что второй игрок выбрал ход z_j. Принято считать положительные значения L_ij истинными потерями, а отрицательные — выигрышами.

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

В каждой игре, т.е. на каждом сеансе распознавания, природа предъявляет объект x, принадлежащий классу ω _i в соответствии с априорной вероятностью p (ω _i). Эта вероятность просто определяет вероятность встретить произвольный объект класса ω _i.

Таким образом, в распоряжении второго игрока оказывается описание объекта x с неизвестной принадлежностью к одному из классов. Его задача как распознавателя заключается в выборе элемента свой стратегии, соответствующего задуманного первым игроком классу. Следует отметить, что игрок-природа не является «разумным противником», который осуществляет свои ходы с целью максимизировать свой выигрыш и принести наибольшие убытки своему сопернику. Можно допустить, что стратегия этого игрока полностью определяется набором априорных вероятностей p (ω ₁), p (ω ₂), …, p (ω _M). Следовательно, это знание может быть использовано игроком-распознавателем при построении своей стратегии.

Итак, игрок-природа предъявляет образ x. Вероятность его принадлежности классу ω _i определяется величиной p (ω _i | x). Если распознаватель относит объект к классу ω _j, а на самом деле он принадлежит классу ω _i, то распознаватель терпит убытки в размере L_ij. Т.к. объект может принадлежать любому из классов, то математическое ожидание потерь, возможных в результате отнесения его классу ω _j, будет равно величине

(4.7)

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

Если для каждого предъявленного объекта x вычисляются значения условных средних потерь r ₁(x), r ₂(x), …, r_M (x) и классификатор причисляет объект к классу, которому соответствует наименьшая из этих величин, то и математическое ожидание полных потерь на множестве всех решений будет минимизировано. Классификатор, минимизирующий математическое ожидание общих потерь, называется байесовским классификатором. Со статистической точки зрения такой классификатор соответствует оптимальному качеству классификации (распознавания).

Используя формулу Байеса

представим (4.7) в следующем виде:

Выражение 1/ p (x) присутствует во всех выражениях r_i (x), i = 1, …, M, следовательно его можно исключить:

(4.8)

p (x | ω _i) называется функцией правдоподобия для класса ω _i.

При рассмотрении задачи разделения на два класса, объект x будет отнесён к классу ω ₁ при выполнении условия r ₁(x) < r ₂(x). Раскрывая это условие при помощи (4.8) с подстановкой M = 2, получим следующую его запись:

или

Обычно считается, что L_ij > L_ii при i ≠ j. При этом допущении получаем

(4.9)

Выполнение этих условий определяет отнесение объекта x к классу ω ₁. При этом левую часть неравенства (4.9) называют отношением правдоподобия:

Итак, для случая двух классов, имеем следующее байесовское решающее правило:

• если выполнено l ₁₂(x) > θ ₁₂, то образ x зачисляется в класс ω ₁;

1. если выполнено l ₁₂(x) < θ ₁₂, то образ x зачисляется в класс ω ₂;

2. если выполнено l ₁₂(x) = θ ₁₂, то решение принимается произвольным образом.

Величину θ ₁₂ называют пороговым значением:

Рассмотрим случай разделения пространства образов на M > 2 классов. В этом случае байесовское правило относит объект x к классу ω _i при выполнении условия r_i (x) < r_j (x), j = 1, 2, …, M; j ≠ i, которое в расширенной форме выглядит как

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

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

L_ij = 0, i = j

L_ij = 1, i ≠ j

При использовании такой функции величину средних потерь можно записать как

Тогда отнесение объекта x к классу ω _i выполняется байесовским правилом при истинности условия

или

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

(4.10).

Образ x зачисляется в класс ω _i при выполнении условия d_i (x) > d_j (x), ∀ j ≠ i, что соответствует случаю 3 разбиения пространства на несколько классов решающими функциями.

Если преобразовать полученное выражение решающей функции с помощью формулы Байеса, получим формулу

в которой множитель p (x) может быть исключён, что даёт

(4.11).

Формула (4.11) по сравнению с (4.10) избавляет решающее правило от необходимости знания в явном виде вероятностей p (x | ω _i) и p (ω _i). Заметим, что хотя оба выражения эквивалентны, они представляют разные правила классификации.

Поскольку оценка априорной вероятности классов p (ω _i), i = 1, …, M обычно не вызывает затруднений, основное различие состоит в том, что в первом случае используются функции правдоподобия p (x | ω _i), а во втором — вероятности p (ω _i | x) ω принадлежности объекта x к классу ω _i.

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