Файл: Журавлёв, Ю. И. Алгоритмы вычисления оценок и их применение [монография].pdf

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

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

Практика распознавания образов интересна тем, что разраба­ тываемые в этой проблеме методы позволяют решать большое количество задач классификации (и прогнозирования) не только в традиционных областях знаний, но даже в гуманитарных науках. Особенно полезным при рассмотрении вопросов в таких областях представляется то, что возникает необходимость в новых математи­ ческих постановках или математических формулировках задач, которые, как оказывается, не могут быть решены методами «обыч­ ной» математики непрерывных процессов [21]. Это является стиму­ лом к разработке новых разделов самой математической науки.

И, наконец, социально-философская значимость проблемы рас­ познавания образов вытекает из того, что впервые в рамках этой проблемы предпринимается попытка искусственно создать устрой­ ство, наделенное чертами разумй.

Как отмечает А. А. Дородницын [21],Гобщей чертой задач рас­ познавания объектов весьма различной физической природы явля­ ется то, что по совокупности признаков (внешняя информация), которые проявляет неизвестный объект из определенного класса, необходимо установить (достоверно или с достаточной степенью вероятности), какому именно объекту из этого класса соответствует данная конкретная совокупность признаков]''.

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

8

Поэтому в проблеме распознавания образов описанный триви­ альный случай не рассматривается и при построении алгоритмов и теории распознавания (обычно называемой теорией обучения ма­ шин распознаванию образов) используются иные пути.

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

Методы обучения машин распознаванию образов с учителем в литературе называются обучением с учителем п им посвящено уже достаточно большое, число научных работ [2, 11, 56—57]. В. С. Пу­ гачев предложил общую модель байесовских обучающихся систем с учителем, позволяющую объединить различные схемы обучения в одну формулировку и учитывающую даже случай реального учи­ теля, когда он не знает точно правильного ответа [59]. Обучение демонстрацией примеров в некоторых работах именуется также обучением с эталонами. Это определение мы используем далее в данной работе.

Второй путь в решении задач распознавания связан с отсут­ ствием обучающего учителя и при классификации объектов исполь­ зуется только информация, заложенная в описании самих объектов, подлежащих классификации. Такой подход к классификации на­ зывается методом распознавания без учителя, пли классификацией без эталонов, или самопроизвольным разбиением множества объ­ ектов. Большой цикл работ, связанных с разработкой алгоритмов для этих разбиений, проведен Н. Г. Загоруйко и его ученика­ ми [23, 34].

§2. Классификация и характеристика основных

задач распознавания образов

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

К настоящему времени не выработана единая, достаточно пол­ ная классификация таких задач, однако уже имеется несколько интересных попыток, заслуживающих внимания как в теоретиче-

9

еком, так и в прикладном смысле. Особенно полезным представля­ ется принцип, предложенный в [34], позволяющий свести все мно­ гообразие задач распознавания к нескольким типам и указать ал­ горитмы, пригодные для их решения. Ввиду того, что в данном па­ раграфе (да и во всей работе) не ставилась цель разработать новую классификацию, мы в дальнейшем будем использовать ре­ комендации, данные в работе [34] с той лишь разницей, что к переч­ ню описанных там вопросов добавим еще один — вычисление меры важности признаков или наборов признаков, участвующих в опи­ сании объектов распознавания. Необходимость и полезность от­ дельного изучения такой задачи подтверждаются соображениями, приводимыми в третьей главе.

Для удобства последующего изложения введем некоторые обо­

ляемых такими наборами, отметим буквой D. Непересекающнеся подмножества — классы, получаемые при разбиении множества D (если они существуют), обозначим через ЛГ, , /С2 , ...,КЦ, ... ,КГ

смотрению некоторых алгоритмов. При этом будем подразумевать, что заданы ограничения на общую сумму затрат Q, складываю­ щихся из стоимости процедуры (объем памяти, количество опера­ ций на ЭВМ, вес, габариты, стоимость оборудования и т. д., необходимые для реализации, т>е. для построения и использования данного распознающего устройства или имитирующего его машин­ ного алгоритма) и стоимости потерь (стоимость ошибок распозна­ вания, зависящая от их вероятности).

1. Задача классификации объектов с эталонами. Эта задача яв ляется основной в теории обучения машин распознаванию образов и содержательно формулируется следующим образом.

Задано некоторое множество M R c:D эталонных объектов и

известно разбиение этого множества на I непересекающихся под­ множеств— классов /<] , ЛГ2, ... , Ки, ... , Kt . Совокупность объек­ тов, составляющих определенное подмножество, представляет

следует отличать друг от. друга. Требуется найти решающее правило (алгоритм), обеспечивающее распознавание (отнесение к

К)