Курс лекций по специальному курсу «Теория принятия решений и распознавания образов» (стр. 1 )

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет радиофизики и электроники

Кафедра интеллектуальных систем

КУРС ЛЕКЦИЙ

по специальному курсу

«Теория принятия решений и распознавания образов»

Учебное пособие для студентов

факультета радиофизики и электроники

Минск

2005

УДК 681.31:621.38

ББК 32.841я43+32.85я43

ISBN 7

Р е ц е н з е н т ы

доктор технических наук

кандидат технических наук, доцент

Рекомендовано

Ученым советом факультета радиофизики и электроники

__ __________2003 г., протокол №___

Р15

Курс лекций по специальному курсу «Теория принятия решений и распознавания образов»: Учебное пособие для студентов факультета радиофизики и электроники. – Мн.: БГУ, 2005. – . ISBN Рассматривается методика формирования описаний классов и ситуаций, составления алфавита признаков и его минимизации, распознавания образов по цветовому описанию, геометрическим параметрам, а также по принятию решений в интеллектуальных системах. Теоретические сведения помогают разрабатывать рациональные алгоритмы процедур поддержки принятия решений, распознавания образов и реализовывать их в современных средах программирования. Предназначено для студентов факультета радиофизики и электроники.

УДК 681.31:621.38

ББК 32.841я43+32.85я43

ISBN 7

© БГУ, 2005

ВВЕДЕНИЕ

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

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

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

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

Учебное пособие ориентировано и на специалистов, работающих в области компьютерных систем и технологий.

1. Истоки курса теории принятия решений и распознавания образов

1.1. Введение в проблематику курса

Курс тесно связан с понятием – “интеллектуальные системы”. В прошлом термин «интеллект» можно было применить напрямую только к человеку. Различные науки выделяли отдельные признаки, пытаясь дать определение данному понятию. Вот некоторые из них.

Наука	Биология	Психология	Философия
Что такое интеллект	Способность человека адекватно реагировать на изменение окружающей среды.	Характеристика умственного развития, определяющая его способность целесообразно действовать, рационально мыслить.	Познание, понимание, рассудочная способность к абстрактноаналитическому расчленению (Гегель); способность к образованию понятий (Кант).

В двадцатом столетии в области исследования интеллекта сформировались два важных научных направления:

- распознавание образов;

- принятие решений.

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

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

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

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

Но реально, только в сороковые годы прошлого столетия началось освоение предметной области.

в связи с началом работ по моделированию интеллектуальной деятельности человека ввел понятие “самоорганизующаяся система”.

В г. Дж. Маккарти впервые употребил термин “искусственный интеллект”, который и получил дальнейшее развитие, став обозначением обширной области науки и техники. Между ними работа Алана Тьюринга “ Может ли машина мыслить” (1950), в которой наиболее просто ставится вопрос о достижении границы искусственного разума.

Стала стандартом и процедура Тьюринга: А задает вопросы В и С отвечают, В или С – машина. Необходимо по ответам распознать машину. Испытания по данному тесту продолжаются до сего времени.

Интересно и то, что одновременно были высказаны количественные оценки требуемой мощности аппаратных средств. Например, объем памяти компьютера в миллиард бит должен быть достаточен для 5 минутного общения среднего человека с 70% вероятностным исходом не распознавания машины, как источника ответов. Достижение этой границы автор предсказывал через 50 лет.

Однако по мере развития науки о искусственном интеллекте изменяются и прогнозы. Один из них – компьютер производительностью в миллиард операций в секунду, с памятью объемом бит с временем доступа 50 нс потенциально достаточен для принятия решений при неполном описании ситуации с логической надежностью близкой к человеку. Сегодня данным требованиям практически удовлетворяет персональный компьютер.

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

- Сможет ли человек познать процесс анализа ситуации, принятия решений идущий в его мозге?

- Можно ли вложить полученные знания в архитектуру технической системы, ее программное обеспечение?

- Сможет ли искусственная система превзойти своего создателя, быть «умнее» его?

Как шутил кибернетик «Определите, что такое мышление и мы его быстренько запрограммируем».

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

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

«Разумные» решения дают наибольший выигрыш по апостериорным данным, полученным по прошествии принятия решения.

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

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

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

В двадцатом столетии значительную нагрузку в области умственной деятельности взяли на себя САПР, созданные для различных областей деятельности человека, сократив в десятки и сотни раз затраты человеко-часов, необходимых для выполнения явно интеллектуальных задач в разработке, проектировании, проведении экспериментов и анализе их результатов. Эти системы не конкурируют с человеком, а дополняют его способности. Но без них создание конкурентно способных изделий не реально.

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

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

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

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

Рис.1. Последовательность действий при распознавании образов (а) и принятии решений (б)

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

1.2. Краткий анализ рекомендуемых литературных источников

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

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

В определенной степени указанные науки вошли в математический базис кибернетики [1]. Математические модели, описывающие случайные процессы рассматриваемые в курсе, достаточно полно изложены в учебном пособии [2]. Однако, каждый слушатель в вопросах связанных с приложениями теории вероятностей [3] может опираться и только на полученные знания в университете и те литературные источники, которые он изучал.

В работах [4-9] рассмотрена специфика наработанного материала по формирования образов, идентификации объектов в различных областях.

Монография Себестиана [10], вышедшая в 1962 году, в области распознавания образов является первой работой, интегрирующей результаты исследований в США. Как говорится в предисловии редактора перевода, только эта страна в то время обладала вычислительными машинами с огромной оперативной памятью в 100 тысяч слов, которые необходимы для ведения работ в данной области.

Книга написана как учебное пособие, математический аппарат строг, но просто изложен. Практически все узловые вопросы современной теории распознавания образов обозначены. Изображения трактуются как вектора в пространстве признаков. В этом пространстве определены метрики и расстояние. Распознаваемые подмножества в этом пространстве, определены как классы.

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

В монографии и [11] основной акцент делается на обучение систем распознавания образов, в частности применительно к нейросетевым структурам.

В работе [12] очень хорошо изложены основы байесовского подхода к распознаванию образов и принятия решений.

Цикл лекций [13-15] подытоживает развитее науки о распознавании в период ее становления.

В монографии [16] излагаются вопросы теории распознавания образов на академическом уровне, с довольно абстрактным математическим аппаратом. Она полезна для углубленного изучения вопроса.

Учебные пособия [17-18] образуют предельно минимальный набор литературных источников, дополняющих курс лекций.

В последние годы наибольшее применение в описании проблематики теории принятия решений находит понятие нечеткой информации, модели и их анализа. Такой подход можно изучить по работам [19-23].

Последующие работы [24-44] дополняют список литературы, конкретизируя отдельные вопросы, рассматриваемые в курсе. Как правило, смысловое содержание названия книги соответствует специфике рассматриваемого в ней вопроса.

Лабораторные практикумы позволят Вам получить навыки в формировании образов – [42], их обработке и принятию решений применительно к специфике курса – [43].

2. Случайные события и процессы

2.1. Статистические модели в описании объектов, признаков, образов, классов, ситуаций и процедур

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

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

Модель должна быть при последующем использовании

Ÿ адекватна оригиналу с заданной точностью, удерживать частное в общем в конкретной группе задач,

Ÿ эффективна (проще, удобнее или давать новую информацию об объекте),

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

Ÿ Процесс создания модели включает в себя следующие механизмы:

Ÿ определения состава (кортежа, алфавита) свойств объекта, подлежащих исследованию,

Ÿ составление набора технических средств для оценки выбранных свойств объекта,

Ÿ получения сведений (опыта, знаний), от других систем об свойствах подобных объектов,

Ÿ использование аналогий,

Ÿ анализ всех данных для формирования описания области существования объекта в пространстве обозначенных свойств.

Можно выделить две цели, преследуемых при анализе конкретного объекта:

1. Составление описания группы схожих объектов (класса), в пространстве выбранных свойств (признаков);

2. Отнесения текущего объекта к одной из обозначенных групп (классов).

В системах с самообучением, как правило, параллельно стремятся достичь обе цели.

Свойства объекта в математической формулировке – переменные могут быть детерминированными и случайными, числовыми и лингвистическими. Детерминированные числовые не требуют пояснения. Числовые случайные и лингвистические переменные рассмотрим подробнее.

Лингвистическая переменная описывается кортежем

[X, T(X),U, G,P],

где: X – имя переменной (пример из [19] о возрасте на шкале лет - молодой);

T(X) – множество значений переменной (термы) (очень молодой, молодой, старый, очень старый);

U – универсальное множество (универсум), на котором задана переменная (возраст), такое множество удерживает свойства всех объектов (например: множество всех действительных чисел, на шкале которого задается возраст, или множество всех комплексных чисел используемых для отображения спектральных образов колебательных процессов);

G – синтаксическое правило, порождающее термы;

P – семантическое правило, ставящее каждому X его смысл, P(X) – нечеткое множество заданное на U (27 лет – молодой, 62 года – старый или очень старый).

Семантическое правило может выдавать и цифры, например вероятности, в данной точке U существования конкретного терма.

Область существования свойств X на U реально может быть ограничена. Ограничения на существование x в u отображаются зависимостями R(x;u). Они допускают только те x=u, которые удовлетворяют условию . Например: возраст человека ограничивается диапазоном чисел от 0 до 200.

Рис.2. Области задания лингвистических переменных (ин, ик, нн, нк, ндн, ндк – начало и конец идеальной, нечеткой, недопустимой областей)

На рис.2 представлены примеры областей задания логических переменных: 2а – на оси одного свойства, 2б – в пространстве трех свойств на поверхности.

Наряду с ограничениями задается и семантическое правило формирования имени переменной. На рис. 2в приведен пример задания вероятности P определения конкретного значения переменной в границах нечеткой области.

Причиной появления не четкого описания переменных служат:

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

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

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

4. В описании цели присутствует ряд не четко заданных словесных конструкций.

Различают так же синтаксическую нечеткость (Железные болты и гайки. Ограничение, железные, действует только на болты или и на гайки тоже) и семантическую – не ясен смысл фразы. Часто в литературе встречаются термины: случайные исходы, нечеткая информация, нечеткая функция полезности, нечеткая цель и т. п. Новая терминология порождает и новую формулировку задач, как, например. Интерпретация вероятности и возможности на основе распределения уверенности.

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

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

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

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

Трех компонентное пространство в целочисленном представлении для полутонового описания пикселя может быть представлено в формате с перекодировкой, это 16 - и 256 - цветные модели. Такой файл описания изображений сопровождается перекодировочной таблицей. По таблице коды преобразуются в представление без кодировки с . Эти форматы получили еще название индексированных. Элемент матрицы ai, j является указателем на таблицу цветов. Число используемых цветов равно 2K, где K - количество бит, используемый для хранения элемента матрицы. Цвета в указываемой таблице могут кодироваться другим числом бит. Например, в 256 цветовых режимах видеоадаптеров выбирается 256 цветов из 262144 возможных, так как выбираемые цвета представляются в RGB формате и для каждой цветовой компоненты кодируется 6-ю битами. Существует много методов преобразования многоканальных изображения в индексированные (Error diffusion, ближайшего цвета ...).

Форматы без перекодировки включают в себя и варианты с комбинациями , , и .

Однако в практике систем распознавания образов более правильно обрабатывать сигналы непосредственно с АЦП CCD или SMOS матриц приборов наблюдения.

Монохромные приборы дают однокомпонентное описание точки с , 10, 12, 14 и у приборов ультра высокого качества .

Описание точки с цветных приборов существенно усложнено. На рисунках 3, 4 приведены варианты нанесения цветовых фильтров на фотоприемники матрицы.

Рис.3. Однородное заполнение

Рис.4. Выделен зеленый цвет

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

Представление пикселя в распространенных цветовых системах приведено в таблице 1.

Таблица 1.

Цветовая система	Бит	1-ый компонент	2-ой компонент	3-ий компонент
RGB Truecolor	8:8:8	Красный 0-255	Зеленый 0..255	Синий 0-255
RGB Highcolor	5:6:5 5:5:5	Красный 0-31 0-31	Зеленый 0-63 0-31	Синий 0-31 0-31
RGB Extended	12:12:12 16:16:16	Красный 0-4095 0-65535	Зеленый 0-4095 0-65535	Синий 0-4095 0-65535
CMY	8:8:8	Голубой 0-255	Пурпурный 0-255	Желтый 0-255
LAB	8:8:8	Яркость 0-255	Канал A 0-100%	Канал B 0-100%
YIQ	8:8:8	Яркость 0-255	Синфазный 0-255	Суммарный 0-255
HLS	8:8:8	Тон 0-3600	Яркость 0-100%	Насыщенность 0-100%
HSB	8:8:8	Тон 0-3600	Насыщенность 0-100%	Яркость 0-100%

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