Основные задачи в проблеме распознавания образов

ОСНОВНЫЕ ЗАДАЧИ В ПРОБЛЕМЕ РАСПОЗНАВАНИЯ ОБРАЗОВ

 

План

1. Проблема распознавания образов

2. Классификация и характеристика основных задач распознавания образов

1. Проблема  распознавания образов

В общем плане проблема распознавания  образов заключается в изучении умения человека воспринимать предметы и явления окружающего мира и классифицировать их на основе каких-то присущих только ему способностей.; На первый взгляд может показаться, что при такой даже «нестрогой» формулировке проблема ясна и не должна вызывать серьезных затруднений при решении. Мы располагаем достаточным количеством примеров, когда те или иные процессы, протекающие в человеческом организме, достаточно полно раскрыты (например, в медицине и физиологии) и с успехом используются в практических целях.

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

Изучение уникальных способностей и особенностей восприятия человеком  предметов и явлений окружающего  мира — феномена восприятия [1],—  хотя и представляет самостоятельный  интерес, но чрезвычайно важно для проблемы распознавания образов. Раскрытие и изучение этого феномена позволило бы ответить на вопросы Н. Винера, поставленные им в известной книге «Кибернетика»: «Как мы узнаем индивидуальное лицо, когда видим его в разных положениях: в профиль, в три четверти или анфас? Как мы узнаем круг как таковой, независимо от того, большой он или маленький, вблизи ли он или вдали?.. Как мы видим лица животных и географические карты в облаках?.. Как мы перекладываем в слова крик птицы или стрекотание насекомого?».

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

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

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

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

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

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

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

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

Методы обучения машин распознаванию  образов с учителем в литературе называются обучением с учителем и им посвящено уже достаточно большое число научных работ [1, 3-4]. В. С. Пугачев предложил общую модель байесовских обучающихся систем с учителем, позволяющую объединить различные схемы обучения в одну формулировку и учитывающую даже случай реального учителя, когда он не знает точно правильного ответа [6]. Обучение демонстрацией примеров в некоторых работах именуется также обучением с эталонами. Это определение мы используем далее в данной работе.

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

2. Классификация  и характеристика основных задач распознавания образов

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

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

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

Объект распознавания  под номером j обозначим через , -ый признак этого объекта —через . Если признаки , принимают свои значения из некоторых заданных множеств , , то набор назовем допустимым, а множество объектов , , представляемых такими наборами, отметим буквой D. Непересекающиеся подмножества — классы, получаемые при разбиении множества D (если они существуют), обозначим через В некоторых случаях отдельный объект (например, контрольный, вновь предъявленный для распознавания) удобно обозначать через и сопоставлять с ним набор признаков .

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

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

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

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

В решении А-задачи различают детерминистскую и вероятностную постановки. Детерминистская постановка подразумевает, что измерения признаков дают детерминированные величины , а суждения учителя об объектах, используемых в процессе обучения, с точки зрения их отнесения к тому или иному классу вполне однозначны.

В таком случае А-задача связана с построением так называемых разделяющих функций [4,8,9]. Пусть , тогда разделяющая функция , относящаяся к классу , , выбирается таким образом, что если , величина

  (1.1)

Уравнение

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

Можно подобрать много различных  форм для  , удовлетворяющих условию (1.1). Широко распространены линейные разделяющие, функции с использованием линейной комбинации признаков :

Решающая граница между классами и имеет вид

   (1.2)

где

 и 

Уравнение (I. 2) есть уравнение гиперплоскости в пространстве признаков.

В литературе [5, 9] можно найти еще ряд интересных форм для в виде кусочно-линейных или полиномиальных функций. Применение эталонов классов при обучении сводится к построению с их помощью определенного набора .весовых коэффициентов , позволяющего достигать удовлетворительного распознавания.

Большое развитие получил подход к решению А-задачи, названный методом потенциальных функций и использующий гипотезу компактности. Мы не будем специально останавливаться на этом методе, так как он полно освещен в периодической и даже монографической литературе [3,10]. Заметим лишь, что исследованиями авторов метода потенциальных функций доказана глубокая аналогия между работой персептрона, предложенного Ф. Розенблаттом [11], и алгоритмом потенциалов в пространстве рецепторов.

Из алгоритмов, решающих задачу классификации объектов с помощью заданных эталонов, на практике применяются еще два— алгоритм построения «обобщенного портрета» [1] и алгоритм «Кора» [13]. Первый заключается в построении разделяющей гиперплоскости, минимизирующей число ошибок на эталонном материале (при этом используются некоторые эвристические приемы), второй основан на выделении достаточных признаков (например, если классов эталонных объектов два, то достаточным признаком для первого называется признак, который на всех объектах второго класса принимает значение 0, а на некоторых объектах первого — 1).

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

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

Обозначим через  потери, связанные с принятием гипотезы , в то время как верна гипотеза . Условный риск для гипотезы равен

    (1.3)

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

 (1.4)

Подставив (1.3) в (1.4) и положив

,

получим для (1.4)

. (1.5)

где величина - есть апостериорный условный средний риск решения R при данном S.