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

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

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

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

АЛГОГ /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