Оценка длины обучающей последовательности в задаче распознавания образов (биоиндикация)

Содержательная (а не формальная) постановка задачи распознавания образов появилась в конце 50-х годов прошлого века и заключалась в том, чтобы построить систему, способную обучаться классификации ситуаций так же, как это делают живые существа. Такое широкое понимание проблемы привело к возникновению различных направлений этих исследований [1, 2]: одни считали главным построение модели восприятия [3], другие видели проблему в том, чтобы используя априорные сведения о свойствах образов, найти такое их описание, при котором отыскание принципа классификации не составляет труда [4], третьи понимали задачу распознавания образов как задачу минимизации риска в специальном классе решающих правил [5], четвёртые определяли распознавание образов как процесс, не требующий точного описания и основанный на обнаружении сходства объектов [6-8], а в работе [9] в деятельности по распознаванию образов находят сходство с процессом проектирования объектов. Эта «пестрота» подходов к задаче распознавания образов объясняется тем, что разные авторы различно представляют как само понятие «образ», так и процесс распознавания. Главным препятствием, стоящим на пути исследователей в этой обширной области, является отсутствие чёткого понимания того, какие процессы происходят при обучении человека.

Распознавание представляет собой информационный процесс, реализуемый некоторым преобразователем информации (системой распознавания), имеющим вход и выход. На вход системы подаётся информация о том, какими признаками обладают предъявляемые объекты; на выходе системы отображается информация о том, к каким классам (обобщённым образам)

отнесены распознаваемые объекты. При создании и эксплуатации автоматизированной системы распознавания образов решается ряд задач.

Рассмотрим кратко основные из них [10]:

• 1)    задача формализации предметной области (задача кодирования);

• 2)    задача формирования обучающей выборки (база данных, содержащая описание объектов в пространстве признаков, дополненная информацией о принадлежности этих объектов к определенным классам распознавания);

• 3)    задача обучения системы распознавания (обучающая выборка используется для формирования обобщенных образов классов распознавания);

• 4)    задача снижения размерности пространства признаков (после обучения системы распознавания можно определить для каждого признака его ценность для решения задачи распознавания; наименее ценные признаки могут быть удалены из системы признаков; затем система распознавания должна быть обучена заново и этот процесс может повторяться, т.е. быть итерационным);

• 5)    собственно задача распознавания (по степени сходства распознаваемого объекта с обучающей выборкой);

• 6)    задача контроля качества распознавания (адекватность; определение фактической средней вероятности ошибки по всем классам распознавания, а также вероятности ошибки при отнесении распознаваемого объекта к определённому классу; результаты распознавания должны интерпретироваться с учётом имеющейся информации о качестве распознавания);

• 7)    задача адаптации (если контроль качества распознавания неудовлетворителен, то необходимо переформатировать распознаваемую и обучающую выборки, вновь решить задачу обучения системы распознавания, стремясь повысить адекватность классификации распознаваемых объектов);

• 8)    обратная задача распознавания (для данного класса распознавания системой устанавливается, какие признаки наиболее характерны для объектов данного класса);

• 9)    задачи кластерного и конструктивного анализа (результатом кластерного анализа является классификация объектов по кластерам);

• 10)    задача когнитивного анализа (анализ пространства признаков по сходству классов распознавания: наличие одного признака у разных классов распознавания или различных признаков у разных классов вносит определённый [интерпретируемый] вклад в их сходство и различие).

В данной статье более подробно формализуется и решается задача 2.

• 1    Оценка длины обучающей последовательности

Задача распознавания образов «с учителем» может быть сформулирована в следующем виде: пусть для l объектов {oi} (i = 1, l; назовем их обучающей последовательностью) известна принадлежность каждого объекта к одному из классов {Aj}, где j = 1, к. Каждый объект задается набором N признаков и, следовательно, может быть представлен точкой в N-мерном пространстве признаков Х. В пространстве Х строится разделяющая функция (решающее правило) Ф таким образом, чтобы она разбила Х на к непересекающихся подпространств {Xj}, в каждом из которых будут находиться объекты {oi} только одного класса; например, для к = 2 имеем: Ф(oi) > 0 для oi е A 1 и Ф(oi) < 0 для oi е A2, где A 1 иA2, A 1 n A2 = 0. Следует ожидать, что качество решающего правила, представляющее собой степень соответствия построенного разбиения пространства Хна подпространства {Xj} действительным классам {Aj}, должно быть функцией длины обучающей последовательности l, размерности пространства признаков Nи числа классов обучения к, то есть Ф = Ф(l, N, k, oi).

Существует мнение, что в качестве исходных признаков необходимо задавать всё, что только можно заподозрить в информативности. С другой стороны, замечено, что при практическом решении задач распознавания образов увеличение размерности пространства признаков не только не улучшает качество распознавания, но, в некоторых случаях, ухудшает его [11, 12]. Отсюда возникает задача оценки длины обучающей последовательности в зависимости от размерности пространства признаков N . Приводимое в литературе решение этой задачи [13, 14] содержит лишь грубую оценку, что не позволяет воспользоваться полученными результатами во многих теоретических и прикладных работах. Данная статья ставит своей целью получение более точных формул решения этой задачи.

Пусть Z - некоторая случайная величина, элементарными событиями которой являются { Z i } с вероятностями {p i }, и пусть S - некоторая совокупность элементарных событий из множества { Z i }. Пусть предстоит провести l независимых повторных наблюдений над случайной величиной Z . Через v A * = n A 1 1 обозначим частоту появления события A е S для некоторой выборки длиной l , где n_A - число элементов выборки, принадлежащих А . Классическая теорема Бернулли утверждает, что при фиксированном событии А последовательность v Al ) подчиняется биномиальному закону распределения и сходится к р ( А ) по вероятности при l ^ да , то есть для любого б > 0 справедливо

P^Л* - P ( A ) > б }-^ °.

Обозначим через Y ( l ) = sup v A' * - P ( A ) случайную величину, представляющую собой A e S                ¹

наибольшее уклонение частоты v A * от вероятности события A по всем A е S . Если для любого б > 0 справедливо

PY(l*>-  ..   • °, то можно говорить о равномерной сходимости частоты к своей вероятности [15-17]. Событие Y(l) > б произойдет в том случае, если хотя бы для одного из событий Aj е S, где j = 1, T (Т -число наблюдений за реализацией Z в классе Aj), будет справедливо |v Al * - P (A * > б . Так как наблюдения над Z проводятся независимо друг от друга, используя теорему о сложении вероятностей [15, 17], получим:

P { Y ( l * >  б } <  £ P L A * - P ( A j * >  б } < T ■ P { v A * - P ( A *| >  б } , j = 1

где в качестве A взято событие, для которого P{vA'* - P(Aj *| > б} принимает наибольшее зна-

чение. Учитывая, что v Al ) подчиняется биномиальному закону распределения, при больших l справедлива следующая оценка [6]:

P i v A ¹ - P ( A * >  б } <

2 P ( A * [ 1 - P ( A *

n l б б

exp

-

7 2 А l б 2

( 2 P ( A *[ 1 - P ( A *] У

Подставляя эту оценку в (1) и полагая Р ( А ) = Р , получим:

P { Y ( l ) >  8 <  T •

2 P ( 1 - P )

—tt ^exP

П l 8

l 8 8

V

2 P ( 1 - P ) J

Если потребовать, чтобы вероятность P { Y ( l ) >  8 } не превосходила некоторого достаточно малого 5, то из уравнения

_т 2 P ( 1 - P )

T •            exp

П 1 8 8

(      7 2 А l 8

V 2 P ( 1 - P ) ^J

= 5

при заданных Р и 8 можно определить l.

Проведённые выше рассуждения справедливы для фиксированного конечного Т . Если представить Т как некоторую функцию длины выборки l и размерности пространства элементарных событий N , то есть Т = Т ( l , N) , то условие равномерной сходимости (1) будет выполнено только в том случае, если Т = Т ( l , N) будет возрастать с ростом l медленнее, чем

exp

l 8 ²

V 2 P ( 1 - P ) ^J

В общем случае, если не учитывать вид решающего правила, число всевозможных классификаций l объектов на к классов будет kl, так как каждый объект может принадлежать любому из к классов. Однако в зависимости от положения объектов в пространстве Х и от вида решающего правила Ф, число классификаций может быть значительно меньше. В ряде работ [18, 19] получена точная формула числа линейных дихотомий, то есть числа разбиения сово- купности объектов на два класса с помощью гиперплоскостей:

2 ^l

T 2 ( l , N ) Н

N

2 • У См l -1

для N >  l , для N <  l .

i = 0

Таким образом, подставляя в (2) значение Т = Т ₂( l , N) для l >  N , получим