Об оценке эффективности методов распознавания образов

On the assessment of the effectiveness of the methods of pattern recognition

Г. В. Данилов, О. В. Качан, Н. К. Борисова

G. V. Danilov, O. V. Kachan, N. K. Borisova

Ухтинский государственный технический университет, г. Ухта;

Институт психологического консультирования «Новый век», Санкт-Петербург, Россия

Ukhta state technical University, Ukhta;

Institute of psychological counseling «Novyy Vek», Saint Petersburg,

Russia

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

The article is devoted to theoretical evaluation of the efficiency of classification algorithms, deduces a formula for the calculation of the guaranteed estimation of reliability of recognition depending on the specific ratio of the objects A and B in the training set for the case of dichotomy, gives an example of calculations using this formula.

Ключевые слова: классификация, оценка эффективности распознавания, надёжность обучения с учителем, теория вероятности.

Keywords: classification, performance evaluation of recognition reliability learning with a teacher, the theory of probability.

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

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

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

В начале напомним задачу распознавания образов в её простейшей постановке.

Пусть имеются N объектов, каждый из которых обладает некоторым набором признаков (X1, X2, …). Известно, что часть из этих объектов принадлежит к классу А, другая часть – к классу В (случай дихотомии). Это так называемые эталонные объекты. В совокупности эти объекты представляют собой точки в признаковом пространстве и образуют «обучающую выборку». Конкретный алгоритм классификации по этой обучающей выборке пытается отнести каждый объект экзаменуемой выборки объёма n к одному из этих двух классов (так называемое «обучение с учителем»).

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

Обозначим через Qmin долю правильно распознанных объектов (0 ≤ Qmin ≤ 1), гарантированную самим методом, её мы в дальнейшем и будем называть эффективностью метода распознавания. Как уже говорилось, ни один метод теоретических оценок Qmin не даёт.

Поэтому в инженерной практике поступают так: применяют акт распознавания к l экзаменуемым выборкам (каждая объёмом n) и в качестве Qmin принимают число:

,

где Qi – доля правильного распознанных объектов в i-й выборке. Такая оценка никак не может быть признана удовлетворительной хотя бы потому, что не гарантирует для (l+1)-й выборки несоблюдения неравенства Qi+1 q.

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

Сравнивая эту оценку с оценкой, полученной «содержательным» методом (альтернатива Н1), решаем вопрос о значимости величины q, т. е. действительно ли данный метод распознавания работает эффективно или же ничем не отличается от простого случайного гадания.

Случайный процесс распознавания будем реализовывать путём подбрасывания специально сконструированной монеты, которая ложится гербом кверху с вероятностью w, и решкой – с вероятностью 1-w. Если выпал герб, то мы относим объект, например, к классу А, если решка – к классу В.

Под успехом будем понимать отнесение объекта к тому классу, к которому он на самом деле принадлежит. В противном случае – неудача.

Обозначив через р вероятность успеха, будем иметь:

p = φ(w, t) = wt +(1 – w)(1 – t)    (1)

где    t – вероятность того, что наугад взятый объект принадлежит классу А, (доля объектов типа А в выборке). Если мы сравниваем процесс случайного гадания с результатами любого содержательного метода распознавания, то поскольку мы имеем дело с сериями испытаний Бернулли, речь идёт об оценке величины:

    (2)

где [ • ] – целая часть.

Более того, желательно найти точную нижнюю грань этой величины по р:

    Inf f(p) = Qmin (случайного распознавания)

Из теории вероятностей известно (например, 1), что

,

где     

– неполная бета-функция с параметрами а и b, (В(а, b) – полная бета-функция с теми же параметрами).

С другой стороны [1] Iх(а, b) есть функция бета-распределения со степенями свободы 2а и 2b и как всякая функция распределения, есть неубывающая по X функция:


где     и – независимые случайные величины, имеющие хи-квадрат распределение со степенями свободы ν1 и ν2
соответственно.

Следовательно f(p) есть неубывающая по р функция и при любом фиксированном W* (с учётом (1)):

    (3)

где        t1 и t2 – нижняя и верхняя границы доверительного интервала для t. Дело в том, что на практике значение t (доля объектов типа А или В в обучающей выборке) оценивают с помощью доверительного интервала (t1, t2), где t1 и t2 определяют, соответственно, решением уравнений [2]:

    (4)

    (5)

где    Р – заданный коэффициент доверия (0.5 ≤ Р ≤ 1), r – общее количество независимых испытаний, µ
– число успехов, Iх(а, b) – функция В – распределения.

Кроме того учтём, что равенство (3), строго говоря, справедливо при ½ ≤ w* ≤ 1 (это следует из (1)). Но распространение его на весь диапазон w*Π[0,1] делается очень просто. В силу симметрии классов А и В, если 0 ≤ w* ≤ ½, мы относим объект к классу А, если монета ложится решкой, а не гербом (с вероятностью w1 = l – w, где уже ½ ≤ w1 ≤ 1)

Желая достичь наибольшей эффективности модели Бернулли как метода классификации, необходимо так выбрать параметр w, чтобы обеспечивать при фиксированном t.

Таким образом задача сводится к отысканию

    (6)

Рассмотрим 3 возможных случая.

1. t2 ≤ ½

Тогда и

    (7)

2.  t1 ≥ ½

Тогда и

    (8)

3.  t1 < ½ < t2

При равновероятном попадании t в любую точку интервала (t1, t2) максимальное значение w будет в среднем равно:


и        (9)

Теперь достаточно в выражение для S вместо р подставить правую часть (7), (8) или (9) (в зависимости от конкретного соотношения объектов А и В в обучающей выборке) и мы получим гарантированную оценку (в виде точной нижней грани) эффективности случайного гадания, как метода распознавания образов, которую можно сравнивать с результатами того или иного конкретного «содержательного» метода.

Вот некоторые численные примеры:

Таблица 1

p

0,5

0,7

0,8

n

10

20

10

20

10

20

q·100 %

80

70

80

70

80

70

inf S

0,055

0,058

0,383

0,608

0,678

0,913

Напомним, что в инженерной практике H1 отвергают в пользу Н0 уже при inf S ≥ 0,05, поэтому в данном примере результаты распознавания по «содержательному» методу не могут быть признаны убедительными, причём такое утверждение на практике справедливо с надёжностью 0,95–0,99.

Список литературы

1. Справочник по специальным функциям с формулами, графиками и математическими таблицами. Пер. с англ. / Под ред. М. Абрамовича, И. Стиган. М. : Наука, 1979. 830 с.

2. Большев Л. Н., Смирнов Н. В. Таблицы математической статистики. М. : Наука, 1983. 416 с.

List of references

1. Abramovich M., Stigan I. (editors), Handbook of special functions with formulas, graphs and mathematical tables. Moscow, Nauka, 1979, 830 p.

2. Bolshev L. N., Smirnov N. V. Tables of mathematical statistics. Moscow, Nauka, 1983, 416 p.

VN:F [1.9.17_1161]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.17_1161]
Rating: 0 (from 0 votes)
VN:F [1.9.17_1161]
Стиль изложения
Информативность
Сложность вопроса
Научная новизна
Коммерциализуемость
Rating: 0.0/5 (0 votes cast)