§ 1. Алгоритмы построения решающих правил

В идеальном случае (если бы он кому-нибудь встретился в жизни) каждый образ был бы представлен не обучающей выборкой конечного объема, а полным аналитическим описанием распределения всех существующих в природе объектов этого образа (генеральной совокупностью). Для самых простых вариантов этого идеального случая, когда распределения подчиняются унимодальному закону (лучше всего, если нормальному) и все характеристики измерены в сильных шкалах, в литературе по математической статистике (например, в [5,111]) описаны строгие и изящные методы построения решающих правил, гарантирующих минимум суммарных потерь  от ошибок распознавания. Практически все реальные задачи распознавания отличаются от такого идеального случая самым важным свойством: отсутствием знаний о генеральной совокупности изучаемых объектов.

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

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

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

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

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