книги из ГПНТБ / Журавлёв, Ю. И. Алгоритмы вычисления оценок и их применение [монография]

АКА ДЕМ И Я Н А У К У З Б Е К С К О Й ССР

ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ИНСТИТУТ КИБЕРНЕТИКИ С ВЫЧИСЛИТЕЛЬНЫМ ЦЕНТРОМ

Ю. И. Ж У Р А В Л Ё В , М. М. КАМИЛОВ, Ш . Е. ТУЛЯ ГАН О В

АЛГОГ /1ТМЫ ВЫЧИСЛЕНИЯ ОЦЕНОК И ИХ ПРИМЕНЕНИЕ

Издательство ,,Фан” Узбекской ССР

Т АШКЕНТ1974

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

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

О т в е т с т в е н н ы й р е д а к т о р академик АН УзССР

В. К. КАБУЛ ОВ

Журавлев Ю. И. и др.

Алгоритмы вычисления оценок и их применение. (Отв. ред. акад. В. К. Ка-

518

Издательство «Фан» УзССР. 1974 г.

В В Е Д Е Н И Е

Быстрое развитие кибернетики за последние два десятилетия открыло огромные возможности для решения большого количества теоретических и. прикладных задач в различных областях знаний и народного хозяйства. До появления ЭВМ и методов кибернетики нельзя было не только найти пути решения некоторых задач, но даже четко определить их постановку. К числу таких можно отнести, например, множество задач, примыкающих по характеру их постановки и решения к большой и чрезвычайно интересной про­ блеме создания искусственного интеллекта. Хотя в делом в этой области не получены какие-либо законченные результаты, в отдель­ ных направлениях проблемы, например, в теории и практике рас­ познавания предметов и явлений наметились весьма обнадеживаю­ щие сдвиги, позволяющие уже сейчас эффективно решать доста­ точное число теоретических и прикладных задач.

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

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

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

3

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

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

Общая проблема распознавания образов состоит в создании тео­ рии и принципов построения систем, разделяющих сложные ситуа­ ции и явления на классы. Число возможных ситуаций в классах велико и их практически невозможно запомнить. Необходимо разработать такую распознающую систему, которая была бы спо­ собна классифицировать на основании информации о разделении ограниченного числа ситуаций на классы J Данный принцип пост­ роения системы распознавания фактически заимствован из живой природы. Так, вначале системе (например, ЭВМ) предъявляются ситуации (эталоны), принадлежность которых к тому или иному классу известна (информация о классах также сообщается систе­ ме). В этот период система обучается — составляет и запоминает описания классов. Степень обученности ее устанавливается на «экзамене», проверяющем способность ЭВМ правильно классифи­ цировать с помощью выработанных описаний классов новые, ранее не встречавшиеся ситуации. Экстраполяционные способности систе­ мы, естественно, зависят от качества первоначального обучения и могут быть улучшены при дополнительном цикле обучения или до­ учивания. В результате достигается желаемая степень качества системы, позволяющая решать задачу распознавания ситуаций с заранее заданной точностью,-

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

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

4

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

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

атакже многих других алгоритмов, называемых «нестрогими».

Внастоящей монографии описывается и исследуется один, до­ статочно широкий, класс алгоритмов, при разработке которого

соблюден основной принцип обеспечения методического единооб­ разия в задании этих алгоритмов. Применительно к задаче рас­ познавания они получили название'алгоритмов распознавания, ос­ нованных на вычислении оценок4 [30]. В то же время возможность использования при решении множества других важных прикладных задач позволяет именовать их просто алгоритмами вычисления оценок. Некоторые нз таких прикладных задач рассмотрены в раз­ делах пятой главы, однако основное содержание книги ориентиро­ вано на круг вопросов, связанных с проблемой распознавания образов.

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

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

В третьей главе описывается одно из наиболее мощных прило­ жений алгоритмов вычисления оценок — задача определения меры важности объектов в сложных системах.

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

5

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

Программный распознающий комплекс (ПРАСК-1), представ­ ленный в приложении, объединяет всю совокупность программ на АЛГОЛ-60 для БЭСМ-6, служащих для решения задач в классе алгоритмов распознавания, основанных на вычислении оценок.

Первое сообщение об этих алгоритмах (называемых тогда ал­ горитмами голосования) было сделано Ю. И. Журавлевым на Все­ союзной конференции по проблемам теоретической кибернетики (Новосибирск, июнь 1969 г.). Дальнейшему развитию теоретиче­ ских и прикладных исследований в данной области во многом спо­ собствовали работы летних школ-семинаров в Хумсане под Таш­ кентом в 1969—1970 гг. Труды этих семинаров, а также последую­ щие результаты, полученные в ВЦ АН СССР и Институте кибернетики с ВЦ АН УзССР, были достаточно полно доложены на Международных конференциях по теории автоматов (Берлин, май 1971 г.) и по практическим методам распознавания образов (Москва, октябрь 1971 г.). Некоторые теоретические аспекты пост­ роения экстремальных алгоритмов вычисления оценок обсужда­ лись на семинаре ИТОРЭС им. А. С. Попова «Теоретические и прикладные вопросы построения вычислительных машин для рас­ познавания образов» (Москва, ноябрь 1972 г.).

Первой публикацией по алгоритмам вычисления оценок явля­ ется работа [31]. За сравнительно короткий срок, уже к моменту написания настоящей монографии, количество опубликованных ра­ бот в данной области существенно увеличилось [18, 19, 27—33, 35—48, 55, 67]. Это свидетельствует о полезности и эффективности тех принципов и методов, которые заложены в основу построения класса алгоритмов вычисления оценок.

С самого начала и до настоящего времени исследования по алгоритмам вычисления оценок стимулировались неослабным вни­ манием и поддержкой действительного члена АН СССР А. А. До­ родницына, чл.-корр. АН СССР С. В. Яблонского и акад. АН УзССР В. К. Кабулова. Авторы считают своим приятным долгом выразить им свою искреннюю признательность. Авторы благодарны также своим коллегам по работе каид. техн. наук Э. М. Алиеву, канд. фнз.-мат. наук В. Бузурханову, канд. техн. наук Д. X. Гулямову, А. Н. Киму и Р. Юнусову, оказавшим неоценимую помощь в подго­ товке материалов монографии.

6

Г л а в а I

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

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

Вобщем плане проблема распознавания образов заключается

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

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

Изучение уникальных способностей и особенностей восприятия

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

Теоретический аспект проблемы распознавания образов связан с необходимостью разработки научной концепции и соответствую­

7

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

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

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

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

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

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

8

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

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

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

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

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

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

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

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

9