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

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

Цель работы: изучить историю систем распознавания образов.

Указать качественные изменения произошедшие в области распознавания образов как теоретические, так и технические, с указанием причин;

Обсудить методы и принципы, применяемые в вычислительной технике;

Привести примеры перспектив, которые ожидаются в ближайшем будущем.

1. Что такое распознавание образов?

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

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

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

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

Определения

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

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

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

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

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

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

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

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

Примеры задач распознавания образов: - Распознавание букв;

Лекция № 17. МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

Различают следующие группы методов распознавания:

Методы функций близости

Методы дискриминантных функций

Статистические методы распознавания.

Лингвистические методы

Эвристические методы.

Первые три группы методов ориентированы на анализ признаков, выражаемых числами либо векторами с числовыми компонентами.

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

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

Методы функций близости

Методы данной группы основаны на использовании функций, оценивающих меру близости между распознаваемым образом с вектором x * = (x * 1 ,….,x * n ), и эталонными образами различных классов, представленными векторами x i = (x i 1 ,…, x i n ), i= 1,…,N , где i – номер класса образов.

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

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

r (x,y )= r (y,x );

r (x,y ) > 0, если x не равен y и r (x,y )=0 если x=y ;

r (x,y ) <= r (x,z )+ r (z,y )

Перечисленным аксиомам удовлетворяют, в частности, следующие функции

a i = 1/2 , j =1,2,…n .

b i =sum, j =1,2,…n .

c i =max abs (x i ‑ x j * ), j =1,2,…n .

Первая из них называется евклидовой нормой векторного пространства. Соответственно пространства, в которых в качестве метрики используется указанная функция называется Евклидовым пространством.

Часто в качестве функции близости выбирают среднеквадратическую разность координат распознаваемого образа x * и эталона x i , т.е. функцию

d i = (1/n ) sum(x i j ‑ x j * ) 2 , j =1,2,…n .

Величина d i геометрически интерпретируется как квадрат расстояния между точками в пространстве признаков, отнесенный к размерности пространства.

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

В таком случае d i = (1/n ) sum w j (x i j ‑ x j * ) 2 , j =1,2,…n ,

где w j – весовые коэффициенты.

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

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

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

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

Методы дискриминантных функций

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

Общий вид линейной решающей функции задается формулой

d (x )=w 1 x 1 + w 2 x 2 +…+ w n x n + w n +1 = Wx +w n

где x - вектор образа, w= ( w 1 , w 2 ,…w n ) – вектор весовых коэффициентов.

В случае разбиения на два класса X 1 и X 2 дискриминантная функция d (x) позволяет осуществить распознавание в соответствии с правилом:

x принадлежит X 1 , если d (x )>0;

x принадлежит X 2 , если d (x )<0.

Если d (x )=0, то имеет место случай неопределенности.

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

Например, если введены три дискриминантные функции, то возможен следующий вариант выделения классов образов:

x принадлежит X 1 , если d 1 (x )>0, d 2 (x )<0, d 3 (x )<0;

x принадлежит X 2 , если d (x )<0, d 2 (x )>0, d 3 (x )<0;

x принадлежит X 3 , если d (x )<0, d 2 (x )<0, d 3 (x )>0.

При этом считается, что для других комбинаций значений d 1 (x ), d 2 (x ), d 3 (x ) имеет место случай неопределенности.

Разновидностью метода дискриминантных функций является метод решающих функций. В нем при наличии m классов предполагается существование m функций d i (x ), называемых решающими, таких, что если x принадлежит X i , то d i (x ) > d j (x ) для всех j не равных i ,т.е. решающая функция d i (x ) имеет максимальное значение среди всех функций d j (x ), j =1,...,n ..

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

Евклидово расстояние между вектором признаков распознаваемого образа x и вектором эталонного образа определяется формулой ||x i ‑ x || = 1/2 , j =1,2,…n .

Вектор x будет отнесен к классу i , для которого значение ||x i ‑ x * || минимально.

Вместо расстояния можно сравнивать квадрат расстояния, т.е.

||x i ‑ x || 2 = (x i ‑ x )( x i ‑ x ) т = x x - 2x x i + x i x i

Поскольку величина x x одинакова для всех i , минимум функции ||x i ‑ x || 2 будет совпадать с максимумом решающей функции

d i (x ) = 2x x i - x i x i .

то есть x принадлежит X i , если d i (x ) > d j (x ) для всех j не равных i .

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

d i (x )=w i 1 x 1 + w i 2 x 2 +…+ w in x n + w i n +1

Она может быть наглядно представлена соответствующей структурной схемой.

Для машины, осуществляющей классификацию по минимуму расстояния имеют место равенства: w ij = -2x i j , w i n +1 = x i x i .

Эквивалентное распознавание методом дискриминантных функций может быть осуществлено, если определить дискриминантные функции как разности d ij (x )= d i (x )‑ d j (x ).

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

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

При этом алгоритм автоматического обучения оказывается весьма простым в сравнении с другими методами распознавания.

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

Процедуры самообученя распознаванию образов

Рассмотрим методы построения дискриминантной функции по заданной (обучающей) выборке применительно к задаче о разделении образов на два класса. Если заданы два множества образов, принадлежащих соответственно классам А и В, то решение задачи построения линейной дискриминантной функции ищется в виде вектора весовых коэффициентов W =(w 1 ,w 2 ,...,w n ,w n +1), обладающего тем свойством, что для любого образа выполняются условия

x принадлежит классу A, если >0, j =1,2,…n .

x принадлежит классу B, если <0, j =1,2,…n .

Если обучающую выборку составляют N образов обоих классов, задача сводится к отысканию вектора w, обеспечивающего справедливость системы неравенств Если обучающую выборку составляют N образов обоих классов, задача сводится к отысканию вектора w , обеспечивающего справедливость системы неравенств

x 1 1 w i +x 21 w 2 +...+x n 1 w n +w n +1 >0;

x 1 2 w i +x 22 w 2 +...+x n 2 w n +w n +1 <0;

x 1 i w i +x 2i w 2 +...+x ni w n +w n +1 >0;

................................................

x 1 N w i +x 2N w 2 +...+x nN w n +w n + 1>0;

здесь x i =(x i 1 ,x i 2 ,...,x i n ,x i n+ 1 ) - вектор значений признаков образа из обучающей выборки, знак > соответствует векторам образов x , принадлежащих классу A, а знак < - векторам x , принадлежащих классу B.

Искомый вектор w существует, если классы A и B разделимы и не существует в противном случае. Значения компонент вектора w могут быть найдены либо предварительно, на этапе, предшествующем аппаратной реализации СРО, либо непосредственно самой СРО в процессе ее функционирования. Последний из указанных подходов обеспечивает большую гибкость и автономность СРО. Рассмотрим его на примере устройства, называемого перцентроном. изобретенного в 1957 году американским ученым Розенблатом. Схематичное представление перцентрона, обеспечивающего отнесение образа к одному из двух классов, представлено на следующем рисунке.

Сетчатка S Сетчатка A Сетчатка R

о о x 1

о о x 2

о о x 3

о (sum)-------> R (реакция)

о о x i

о о x n

о о x n +1

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

Обозначив через x i реакцию i -го ассоциативного элемента и через w i - весовой коэффициент реакции i -го ассоциативного элемента, реакцию системы можно записать как R =sum(w j x j ), j =1,..,n . Если R >0, то предъявленный системе образ принадлежит классу A, а если R <0, то образ относится к классу B. Описание этой процедуры классификации соответствует рассмотренным нами раньше принципам классификации, и, очевидно, перцентронная модель распознавания образов представляет собой, за исключением сенсорной сетчатки, реализацию линейной дискриминантной функции. Принятый в перцентроне принцип формирования значений x 1 , x 2 ,...,x n соответствует некоторому алгоритму формирования признаков на основе сигналов первичных датчиков.

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

Схему перцентрона можно распространить на случай, когда число классов более двух, путем увеличения числа элементов сетчатки R до числа различаемых классов и введение блока определения максимальной реакции в соответствии со схемой, представленной на выше приведенном рисунке. При этом образ причисляется к классу с номером i , если R i >R j , для всех j .

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

Рассмотрим алгоритм действия перцентрона на примере распознавания объектов двух классов: A и B. Объектам класса A должно соответствовать значение R = +1, а классу B - значение R = -1.

Алгоритм обучения состоит в следующем.

Если очередной образ x принадлежит классу A, но R <0 (имеет место ошибка распознавания), тогда коэффициенты w j c индексами, которым соответствуют значения x j >0, увеличивают на некоторую величину dw , а остальные коэффициенты w j уменьшают на dw . При этом значение реакции R получает приращение в сторону ее положительных значений, соответствующих правильной классификации.

Если x принадлежит классу B, но R >0 (имеет место ошибка распознавания), то коэффициенты w j с индексами, которым соответствуют x j <0, увеличивают на dw , а остальные коэффициенты w j уменьшают на ту же величину. При этом значение реакции R получает приращение в сторону отрицательных значений, соответствующих правильной классификации.

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

Статистические методы распознавания.

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

P = sum[p (i )·prob(D (x )+i | x классу i )]

где m - число классов,

p (i ) = prob (x принадлежит классу i ) - априорная вероятность принадлежности произвольного образа x к i -му классу (частота появления образов i -го класса),

D (x ) - функция, принимающая классификационное решение (вектору признаков x ставит в соответствие номер класса i из множества {1,2,...,m }),

prob(D (x ) не равно i | x принадлежит классу i ) - вероятность события "D (x ) не равно i " при выполнении условия принадлежности x классу i , т.е. вероятность вынесения ошибочного решения функцией D (x ) для данного значения x , принадлежащего i -му классу.

Можно показать, что вероятность неправильной классификации достигает минимума, если D (x )=i в том и только в том случае, если p (x |i )·p (i )>p (x|j )·p (j ), для всех i+j , где p (x|i ) - плотность распределения образов i -го класса в пространстве признаков.

Согласно приведенному правилу точка x относится к тому классу, которому соответствует максимальное значение p (i ) p (x|i ), т.е. произведение априорной вероятности (частоты) появления образов i -го класса и плотности распределения образов i -го класса в пространстве признаков. Представленное правило классификации называется байесовским, т.к. оно следует из известной в теории вероятности формулы Байеса.

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

Каждый входной сигнал представляет собой 0 или 1. В результате передачи сигнала на выходе канала появляется величина x , на которую налагается Гауссовский шум с нулевым средним значением и дисперсией б.

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

В класс №1 объединим сигналы, представляющие единицы, в класс №2 - сигналы, представляющие нули. Пусть заранее известно, что в среднем из каждой 1000 сигналов a сигналов представляют собой единицы и b сигналов - нули. Тогда значения априорных вероятностей появления сигналов 1-го и 2-го классов (единиц и нулей), соответственно можно принять равными

p(1)=a/1000, p(2)=b/1000.

Т.к. шум является гауссовским, т.е. подчиняется нормальному (гауссовскому) закону распределения, то плотность распределения образов первого класса в зависимости от значения x , или, что тоже самое, вероятность получения на выходе величины x при подаче на входе сигнала 1 определяется выражением

p (x ¦1) =(2piб) -1/2 exp(-(x -1) 2 /(2б 2)),

а плотность распределения в зависимости от значения x образов второго класса, т.е. вероятность получения на выходе величины x при подаче на входе сигнала 0 определяется выражением

p (x ¦2)= (2piб) -1/2 exp(-x 2 /(2б 2)),

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

p (2) p (x ¦2) > p (1) p (x ¦1)

или, более конкретно, если

b exp(-x 2 /(2б 2)) > a exp(-(x -1) 2 /(2б 2)),

Поделив левую часть неравенства на правую, получим

(b /a ) exp((1-2 x )/(2б 2)) >1,

откуда после логарифмирования находим

1-2x > 2б 2 ln(a/b)

x < 0.5 - б 2 ln(a/b)

Из полученного неравенства следует, что при a=b , т.е. при одинаковых априорных вероятностях появления сигналов 0 и 1, образу присваивается значение 0 когда x <0.5, а значение 1, когда x >0.5.

Если заранее известно, что один из сигналов появляется чаще, а другой реже, т.е. в случае неодинаковых значений a и b , порог срабатывания классификатора смещается в ту или другую сторону.

Так при a/b =2.71 (что соответствует в 2.71 раза более частой передаче единиц) и б 2 =0.1, образу присваивается значение 0, если x <0.4, и значение 1, если x >0.4. Если информация об априорных вероятностях распределения отсутствует, то могут быть использованы статистические методы распознавания, в основу которых положены иные, отличные от байесовского, правила классификации.

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

Лингвистические методы распознавания образов.

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

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

Пример. Пусть заданы три изображения буквы А, полученные в результате предварительной обработки изображений. Обозначим эти изображения идентификаторами А1, А2 и А3.

Для лингвистического описания представленных образов воспользуемся языком PDL (Picture Description Language). Словарь языка PDL включает следующие символы:

1. Имена простейших изображений (примитивов). Применительно к рассматриваемому случаю примитивы и соответствующие им имена следующие.

Изображения в виде линии, направленной:

вверх и влево (leF t), на север(north)), вверх и вправо (right), на восток(east)).

Имена: L, N, R, E .

2. Символы бинарных операций. {+,*,-} Их смысл соответствует последовательному соединению примитивов (+), соединению начал и окончаний примитивов (*), соединению только окончаний примитивов (-).

3. Правую и левую скобки. {(,)} Скобки позволяют определять последовательность выполненияопераций в выражении.

Рассматриваемые изображения А1, А2 и А3 описываются на языке PDL соответственно следующими выражениями.

T(1)=R+((R-(L+N))*E-L

T(2)=(R+N)+((N+R)-L)*E-L

T(3)=(N+R)+(R-L)*E-(L+N)

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

Очевидно, буква А всегда содержит следующие структурные элементы: левую "ножку", правую "ножку" и головную часть. Назовем эти элементы соответственно STL, STR, TR.

Тогда на языке PDL класс символов А - SIMB A описывается выражением

SIMB A = STL + TR - STR

Левая "ножка" STL всегда есть цепочка элементов R и N, что можно записать так

STL ‑> R ¦ N ¦ (STL + R)¦(STL + N)

(STL есть символ R или N, или цепочка, полученная добавлением кисходной цепочке STL символов R или N)

Правая "ножка" STR всегда есть цепочка элементов L и N, что можно записать так, т.е.

STR ‑> L¦N¦ (STR + L)¦(STR + N)

Головная часть буквы - TR представляет собой замкнутый контур, составленный из элемента E и цепочек типа STL и STR.

На языке PDLструктура TR описывается выражением

TR ‑> (STL - STR) * E

Окончательно получим следующее описание класса букв А:

SIMB A ‑> (STL + TR - STR),

STL ‑> R¦N¦ (STL + R)¦(STL + N)

STR ‑> L¦N¦ (STR + L)¦(STR + N)

TR ‑> (STL - STR) * E

Процедура распознавания в данном случае может быть реализована следующим образом.

1. Выражение, соответствующее образу, сравнивается с эталоннойструктурой STL + TR - STR.

2. Каждому элементу структуры STL, TR, STR, если это возможно, т.е. если описание изображения сравнимо с эталоном, ставится в соответствиенекоторое подвыражение из выражения T(А). Например,

для А1: STL=R, STR=L, TR=(R-(L+N))*E

для А2: STL = R + N, STR = L, TR = ((N + R) - L) * E

для А3: STL = N + R, STR = L + N, TR = (R - L) * E 3.

Выражения STL, STR, TR сравниваются с соответствующими им эталонными структурами.

4. Если структура каждого выражения STL, STR, TR соответствует эталонной, делается вывод о принадлежности образа к классу букв А. Если на каком-либо из этапов 2, 3, 4 обнаруживается несоответствие структуры анализируемого выражения эталону, делается вывод о непринадлежности образа классу SIMB A. Сопоставление структур выражений может проводиться с помощью алгоритмических языков LISP, PLANER, PROLOG и других подобных им языков искусственного интеллекта.

В рассматриваемом примере все цепочки STL составлены из символов N и R, а цепочки STR из символов L и N, что соответствует заданной структуре этих цепочек. Структура TR в рассматриваемых образах также соответствует эталонной, т.к. состоит из "разности" цепочек типа STL, STR, "умноженной" на символ E.

Т.о., приходим к выводу о принадлежности рассматриваемых образов классу SIMB A.

Синтез нечеткого регулятора электропривода постоянного тока в среде «MatLab»

Синтез нечеткого регулятора с одним входом и выходом.

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

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

Рис.5 Принципиальная схема нечеткого регулятора с двумя лингвистическими переменными.

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

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

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

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

Рассмотрим сначала самый простой случай, когда для управления следящим электроприводом вводятся всего две лингвистические переменные:

«угол» - входная переменная;

«управляющее воздействие» - выходная переменная.

Синтез регулятора будем осуществлять в среде «MatLab» с помощью тулбокса «Fuzzy Logic». Он позволяет создавать системы нечеткого логического вывода и нечеткой классификации в рамках среды MatLab, с возможностью их интегрирования в Simulink. Базовым понятием Fuzzy Logic Toolbox является FIS-структура - система нечеткого вывода (Fuzzy Inference System). FIS-структура содержит все необходимые данные для реализации функционального отображения “входы-выходы” на основе нечеткого логического вывода согласно схеме, приведенной на рис. 6.

Рисунок 6. Нечеткий логический вывод.

X - входной четкий вектор; - вектор нечетких множеств, соответствующий входному вектору X;
- результат логического вывода в виде вектора нечетких множеств;Y - выходной четкий вектор.

Модуль fuzzy позволяет строить нечеткие системы двух типов - Мамдани и Сугэно. В системах типа Мамдани база знаний состоит из правил вида “Если x 1 =низкий и x 2 =средний, то y=высокий” . В системах типа Сугэно база знаний состоит из правил вида “Если x 1 =низкий и x 2 =средний, то y=a 0 +a 1 x 1 +a 2 x 2 " . Таким образом, основное отличие между системами Мамдани и Сугэно заключается в разных способах задания значений выходной переменной в правилах, образующих базу знаний. В системах типа Мамдани значения выходной переменной задаются нечеткими термами, в системах типа Сугэно - как линейная комбинация входных переменных. В нашем случаем будем использовать систему Сугэно, т.к. она лучше поддается оптимизации.

Для управления следящим электроприводом, вводятся две лингвистические переменные: «ошибка» (по положению) и «управляющее воздействие». Первая из них является входной, вторая – выходная. Определим терм-множество для указанный переменных.

Основные компоненты нечеткого логического вывода. Фаззификатор.

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

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

Рис.7. Лингвистическая переменная «ошибка».

Лингвистическую переменную «управление» удобнее представить в виде таблицы:

Таблица 1

Блок правил .

Рассмотрим последовательность определения нескольких правил, которые описывают некоторые ситуации:

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

Теперь рассмотрим другой случай: ошибка по положению сильно больше нуля. Естественно мы должны её компенсировать, формируя большой положительный сигнал управления.

Т.о. составлены два правила, которые могут быть формально определены так:

если ошибка = нуль, то управляющее воздействие = нуль.

если ошибка = большая положительная, то управляющее воздействие = большое положительное.

Рис.8. Формирование управления при малой положительной ошибке по положению.

Рис.9. Формирование управления при нулевой ошибке по положению.

Ниже в таблице приведены все правила, соответствующие всем ситуациям для этого простого случая.

Таблица 2

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

Дефаззификатор.

Таким образом, результирующее воздействие U будет определяться соответственно выполнению какого-либо правила. Если возникает ситуация, когда выполняются сразу несколько правил, то результирующее воздействие U находится по следующей зависимости:

, где n-число сработавших правил (дефаззификация методом центра области), u n – физическое значение управляющего сигнала, сответствующее каждому из нечетких множеств UBO , UMo , U Z , UMp , UB P . m Un(u) – степень принадлежности управляющего сигнала u к соответствующему нечеткому множеству Un={UBO , UMo , U Z , UMp , UB P }. Существуют также и другие методы дефаззификации, когда выходная лингвистическая переменная пропорциональна самомому «сильному» или «слабому» правилу.

Промоделируем процесс управления электроприводом с помощью вышеописанного нечеткого регулятора.

Рис.10. Структурная схема системы в среде Matlab .

Рис.11. Структурная схема нечеткого регулятора в среде Matlab .

Рис.12. Переходный процесс при единичном ступенчатом воздействии.

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

Анализ характеристик привода с синтезированным алгоритмом управления показывает, что они далеки от оптимальных и хуже, чем при синтезе управления другими методами (слишком большое время регулирования при единичном ступенчатом воздействии и ошибка при гармоническом). Объясняется это тем, что параметры функций принадлежности выбирались достаточно произвольно, а в качестве входов регулятора использовалась только величина ошибки по положению. Естественно ни о какой оптимальности полученного регулятора не может идти и речи. Поэтому актуальной становится задача оптимизации нечеткого регулятора, с целью достижения им максимально возможных показателей качества управления. Т.е. стоит задача оптимизации целевой функции f(a 1 ,a 2 …a n), где a 1 ,a 2 …a n – коэффициенты, определяющие вид и характеристики нечеткого регулятора. Для оптимизации нечеткого регулятора воспользуемся блоком ANFIS из среды Matlab. Также одним из способов улучшения характеристик регулятора может являться увеличение числа его входов. Это сделает регулятор более гибким и улучшит его характеристики. Добавим еще одну входную лингвистическую переменную – скорость изменения входного сигнала (его производную). Соответственно возрастет и число правил. Тогда принципиальная схема регулятора примет вид:

Рис.14 Принципиальная схема нечеткого регулятора с тремя лингвистическими переменными.

Пусть - значение скорости входного сигнала. Базовое терм-множество Тn определим в виде:

Тn={”отрицательная (ВО)”, “нулевая (Z)”, ”положительная (ВР)”}.

Расположение функций принадлежности для всех лингвистических переменных показано на рисунке.

Рис.15. Функции принадлежности лингвистической переменной «ошибка».

Рис.16. Функции принадлежности лингвистической переменной «скорость входного сигнала» .

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

Таблица 3

Нечеткий сигнал управления		Ошибка по положению
Скорость

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

Рис.17. Формирование управления при трех лингвистических переменных.

В связи с увеличением числа входов и соответственно самих правил, усложнится и структура нечеткого регулятора.

Рис.18. Структурная схема нечеткого регулятора с двумя входами.

Добавить рисунок

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

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

Промоделируем работу нечеткого регулятора с двумя входами в среде Matlab. Структурная схема модели будет точно такой же, как на рис. 19. Из графика переходного процесса для гармонического входного воздействия можно видеть, что точность системы значительно возросла, но при этом увеличилась её колебательность, особенно в местах, где производная выходной координаты стремится к нулю. Очевидно, что причинами этого, как уже говорилось выше, является неоптимальный выбор параметров функций принадлежности, как для входных, так и для выходных лингвистических переменных. Поэтому оптимизируем нечеткий регулятор с помощью блока ANFISedit в среде Matlab.

Оптимизация нечеткого регулятора.

Рассмотрим использование генетических алгоритмов для оптимизации нечеткого регулятора. Генетические алгоритмы – адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на подобии генетическим процессам биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы.

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

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

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

1. Инициализация начальной популяции – генерация заданного числа решений задачи, с которых начинается процесс оптимизации;

2. Применение операторов кроссовера и мутации;

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

В среде Matlab генетические алгоритмы представлены отдельным тулбоксом, а также пакетом ANFIS. ANFIS - это аббревиатура Adaptive-Network-Based Fuzzy Inference System - адаптивная сеть нечеткого вывода. ANFIS является одним из первых вариантов гибридных нейро-нечетких сетей - нейронной сети прямого распространения сигнала особого типа. Архитектура нейро-нечеткой сети изоморфна нечеткой базе знаний. В нейро-нечетких сетях используются дифференцируемые реализации треугольных норм (умножение и вероятностное ИЛИ), а также гладкие функции принадлежности. Это позволяет применять для настройки нейро-нечетких сетей быстрые и генетические алгоритмы обучения нейронных сетей, основанные на методе обратного распространения ошибки. Ниже описываются архитектура и правила функционирования каждого слоя ANFIS-сети.

ANFIS реализует систему нечеткого вывода Сугено в виде пятислойной нейронной сети прямого распространения сигнала. Назначение слоев следующее: первый слой - термы входных переменных; второй слой - антецеденты (посылки) нечетких правил; третий слой - нормализация степеней выполнения правил; четвертый слой - заключения правил; пятый слой - агрегирование результата, полученного по различным правилам.

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

Рис.23. Структура ANFIS -сети.

Введем следующие обозначения, необходимые для дальнейшего изложения:

Пусть - входы сети;

y - выход сети;

Нечеткое правило с порядковым номером r;

m - количество правил,;

Нечеткий терм с функцией принадлежности , применяемый для лингвистической оценки переменной в r-ом правиле (,);

Действительные числа в заключении r-го правила (,).

ANFIS-сеть функционирует следующим образом.

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

,

где a, b и c - настраиваемые параметры функции принадлежности.

Слой 2. Количество узлов второго слоя равно m. Каждый узел этого слоя соответствует одному нечеткому правилу. Узел второго слоя соединен с теми узлами первого слоя, которые формируют антецеденты соответствующего правила. Следовательно, каждый узел второго слоя может принимать от 1 до n входных сигналов. Выходом узла является степень выполнения правила, которая рассчитывается как произведение входных сигналов. Обозначим выходы узлов этого слоя через , .

Слой 3. Количество узлов третьего слоя также равно m. Каждый узел этого слоя рассчитывает относительную степень выполнения нечеткого правила:

Слой 4. Количество узлов четвертого слоя также равно m. Каждый узел соединен с одним узлом третьего слоя а также со всеми входами сети (на рис. 18 связи с входами не показаны). Узел четвертого слоя рассчитывает вклад одного нечеткого правила в выход сети:

Слой 5. Единственный узел этого слоя суммирует вклады всех правил:

.

Типовые процедуры обучения нейронных сетей могут быть применены для настройки ANFIS-сети так как, в ней использует только дифференцируемые функции. Обычно применяется комбинация градиентного спуска в виде алгоритма обратного распространения ошибки и метода наименьших квадратов. Алгоритм обратного распространения ошибки настраивает параметры антецедентов правил, т.е. функций принадлежности. Методом наименьших квадратов оцениваются коэффициенты заключений правил, так как они линейно связаны с выходом сети. Каждая итерация процедуры настройки выполняется в два этапа. На первом этапе на входы подается обучающая выборка, и по невязке между желаемым и действительным поведением сети итерационным методом наименьших квадратов находятся оптимальные параметры узлов четвертого слоя. На втором этапе остаточная невязка передается с выхода сети на входы, и методом обратного распространения ошибки модифицируются параметры узлов первого слоя. При этом найденные на первом этапе коэффициенты заключений правил не изменяются. Итерационная процедура настройки продолжается пока невязка превышает заранее установленное значение. Для настройки функций принадлежностей кроме метода обратного распространения ошибки могут использоваться и другие алгоритмы оптимизации, например, метод Левенберга-Марквардта.

Рис.24. Рабочая область ANFISedit.

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

Рис.25. Желаемый переходный процесс.

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

Таблица 4

Значение ошибки	Значение управления
Значение ошибки	Значение управления
Значение ошибки	Значение управления

Рис.26. Вид обучающей выборки.

Обучение будем проводить на 100 шагах. Этого более чем достаточно для сходимости используемого метода.

Рис.27. Процесс обучения нейросети.

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

Рис.28. График зависимости управления от ошибки поп положению внутри регулятора.

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

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

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

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

Sun, Mar 29, 2015

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

Рассмотрим общие элементы модели классификации.

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

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

Верификация - процесс сопоставления экземпляра объекта с одной моделью объекта или описанием класса.

Под образом будем понимать наименование области в пространстве признаков, в которой отображается множество объектов или явлений материального мира. Признак - количественное описание того или иного свойства исследуемого предмета или явления.

Пространство признаков это N-мерное пространство, определенное для данной задачи распознавания, где N - фиксированное число измеряемых признаков для любых объектов. Вектор из пространства признаков x, соответствующий объекту задачи распознавания это N-мерный вектор с компонентами (x_1,x_2,…,x_N), которые являются значениями признаков для данного объекта.

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

Примерами задач классификации являются:

• распознавание символов;
• распознавание речи;
• установление медицинского диагноза;
• прогноз погоды;
• распознавание лиц
• классификация документов и др.

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

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

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

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

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

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

где d - размерность вектора признака.

Разделяют 3 группы методов распознавания образов:

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

Классификация по ближайшему среднему значению

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

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

где x(i,j)- j-й эталонный признак класса i, n_j- количество эталонных векторов класса i.

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

Трудности возникнут, если классы будут иметь несколько более сложную структуру, например, как на рисунке. В данном случае класс 2 разделен на два непересекающихся участка, которые плохо описываются одним средним значением. Также класс 3 слишком вытянут, образцы 3-го класса с большими значениями координат x_2 ближе к среднему значению 1-го класса, нежели 3-го.

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

Будем учитывать характеристику «разброса» значений класса - σ_i, вдоль каждого координатного направления i. Среднеквадратичное отклонение равно квадратному корню из дисперсии. Шкалированное евклидово расстояние между вектором x и вектором математического ожидания x_c равно

Эта формула расстояния уменьшит количество ошибок классификации, но на деле большинство задач не удается представить таким простым классом.

Классификация по расстоянию до ближайшего соседа

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

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

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

Кроме того, решение будет лучше, если искать в базе не одного ближайшего соседа, а k. Тогда при k > 1 обеспечивает наилучшую выборку распределения векторов в d-мерном пространстве. Однако эффективное использование значений k зависит от того, имеется ли достаточное количество в каждой области пространства. Если имеется больше двух классов то принять верное решение оказывается сложнее.

Литература

• M. Castrillón, . O. Déniz, . D. Hernández и J. Lorenzo, «A comparison of face and facial feature detectors based on the Viola-Jones general object detection framework,» International Journal of Computer Vision, № 22, pp. 481-494, 2011.
• Y.-Q. Wang, «An Analysis of Viola-Jones Face Detection Algorithm,» IPOL Journal, 2013.
• Л. Шапиро и Д. Стокман, Компьютерное зрение, Бином. Лаборатория знаний, 2006.
• З. Н. Г., Методы распознавания и их применение, Советское радио, 1972.
• Дж. Ту, Р. Гонсалес, Математические принципы распознавания образов, Москва: “Мир” Москва, 1974.
• Khan, H. Abdullah и M. Shamian Bin Zainal, «Efficient eyes and mouth detection algorithm using combination of viola jones and skin color pixel detection» International Journal of Engineering and Applied Sciences, № Vol. 3 № 4, 2013.
• V. Gaede и O. Gunther, «Multidimensional Access Methods,» ACM Computing Surveys, pp. 170-231, 1998.

Обзор существующих методов распознавания образов

Л.П. Попова , И.О. Датьев

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

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

В теории распознавания образов можно выделить два основных направления:

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

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

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

Проблемы построения систем распознавания образов

Задачи, возникающие при построении автоматических систем распознавания образов, можно обычно отнести к нескольким основным областям. Первая из них связана с представлением" исходных данных, полученных как результаты измерений для подлежащего распознаванию объекта. Это проблема чувствительности . Каждая измеренная величина является некоторой "характеристикой образа или объекта. Допустим, например, что образами являются буквенно-цифровые символы. B таком случае, в датчике может быть успешно использована измерительная сетчатка, подобно приведенной на рис. 1(а). Если сетчатка состоит из n-элементов, то результаты измерений можно представить в виде вектора измерений или вектора образа ,

где каждый элемент xi, принимает, например, значение 1, если через i-ю ячейку сетчатки проходит изображение символа, и значение 0 в противном случае.

Рассмотрим рис. 2(б). B этом случае образами служат непрерывные функции (типа звуковых сигналов) переменной t. Если измерение значений функций производится в дискретных точках t1,t2, ..., tn, то вектор образа можно сформировать, приняв x1= f(t1),x2=f(t2),... , xn = f(tn).

Рисунок 1. Измерительная сетчатка

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

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

Третья проблема, связанная с построением систем распознавания образов, состоит в отыскании оптимальных решающих процедур, необходимых при идентификации и классификации. После того как данные, собранные о подлежащих распознаванию образах, представлены точками или векторами измерений в пространстве образов, предоставим машине выяснить, какому классу образов эти данные соответствуют. Пусть машина предназначена для различения M классов, обозначенных w1, w2, ... ..., wm. B таком случае, пространство образов можно считать состоящим из M областей, каждая из которых содержит точки, соответствующие образам из одного класса. При этом задача распознавания может рассматриваться как построение границ областей решений, разделяющих M классов, исходя из зарегистрированных векторов измерений. Пусть эти границы определены, например, решающими функциями d1(х),d2(x),..., dm(х). Эти функции, называемые также дискриминантными функциями, представляют собой скалярные и однозначные функции образа х. Если di (х) > dj (х), то образ х принадлежит классу w1. Другими словами, если i-я решающая функция di(x) имеет наибольшее значение, то содержательной иллюстрацией подобной схемы автоматической классификации, основанной на реализации процесса принятия решения, служит приведенная на рис. 2 (на схеме «ГР» - генератор решающих функций).

Рисунок 2. Схема автоматической классификации.

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

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

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

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

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

Различные авторы (Ю.Л. Барабаш , В.И. Васильев , А.Л. Горелик, В.А. Скрипкин , Р. Дуда, П. Харт , Л.Т.Кузин , Ф.И. Перегудов, Ф.П. Тарасенко , Темников Ф.Е., Афонин В.А., Дмитриев В.И. , Дж. Ту, Р. Гонсалес , П. Уинстон , К. Фу , Я.З. Цыпкин и др.) дают различную типологию методов распознавания образов. Одни авторы различают параметрические, непараметрические и эвристические методы, другие – выделяют группы методов, исходя из исторически сложившихся школ и направлений в данной области.

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

Интенсиональное представление - в виде схемы связей между атрибутами (признаками).

Экстенсиональное представление - с помощью конкретных фактов (объекты, примеры).

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

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

Интенсиональные методы

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

Группа интенсиональных методов распознавания образов обширна, и ее деление на подклассы носит в определенной мере условный характер:

– методы, основанные на оценках плотностей распределения значений признаков

– методы, основанные на предположениях о классе решающих функций

– логические методы

– лингвистические (структурные) методы.

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

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

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

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

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

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

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

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

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

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

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

Известным представителем эволюционного моделирования в распознавании образов является метод группового учета аргументов (МГУА). В основу МГУА положен принцип самоорганизации, и алгоритмы МГУА воспроизводят схему массовой селекции. В алгоритмах МГУА особым образом синтезируются и отбираются члены обобщенного полинома, который часто называют полиномом Колмогорова-Габора. Этот синтез и отбор производится с нарастающим усложнением, и заранее нельзя предугадать, какой окончательный вид будет иметь обобщенный полином. Сначала обычно рассматривают простые попарные комбинации исходных признаков, из которых составляются уравнения решающих функций, как правило, не выше второго порядка. Каждое уравнение анализируется как самостоятельная решающая функция, и по обучающей выборке тем или иным способом находятся значения параметров составленных уравнений. Затем из полученного набора решающих функций отбирается часть в некотором смысле лучших. Проверка качества отдельных решающих функций осуществляется на контрольной (проверочной) выборке, что иногда называют принципом внешнего дополнения. Отобранные частные решающие функции рассматриваются далее как промежуточные переменные, служащие исходными аргументами для аналогичного синтеза новых решающих функций и т. д. Процесс такого иерархического синтеза продолжается до тех пор, пока не будет достигнут экстремум критерия качества решающей функции, что на практике проявляется в ухудшении этого качества при попытках дальнейшего увеличения порядка членов полинома относительно исходных признаков.

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

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

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

В самом общем виде логические методы можно охарактеризовать как разновидность поиска по обучающей выборке логических закономерностей и формирование некоторой системы логических решающих правил (например, в виде конъюнкций элементарных событий), каждое из которых имеет собственный вес. Группа логических методов разнообразна и включает методы различной сложности и глубины анализа. Для дихотомических (булевых) признаков популярными являются так называемые древообразные классификаторы, метод тупиковых тестов, алгоритм “Кора” и другие. Более сложные методы основываются на формализации индуктивных методов Д.С.Милля. Формализация осуществляется путем построения квазиаксиоматической теории и базируется на многосортной многозначной логике с кванторами по кортежам переменной длины .

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

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

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

Например, Е.А. Бутаков, В.И. Островский, И.Л. Фадеев предлагают следующую структуру системы для обработки изображений (рис. 3), использующую лингвистический подход, где каждый из функциональных блоков является программным (микропрограммным) комплексом (модулем), реализующим соответствующие функции.

Рисунок 3. Структурная схема распознающего устройства

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

Экстенсиональные методы

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

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

метод сравнения с прототипом;

метод k–ближайших соседей;

коллективы решающих правил.

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

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

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

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

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

Метод k-ближайших соседей. Метод k-ближайших соседей для решения задач дискриминантного анализа был впервые предложен еще в 1952 году. Он заключается в следующем.

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

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

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

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

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

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

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

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

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

Нейросетевые методы

Нейросетевые методы - это методы, базирующиеся на применении различных типов нейронных сетей (НС). Основные направления применения различных НС для распознавания образов и изображений :

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

классификация самих образов или уже извлечённых из них характеристик (в первом случае извлечение ключевых характеристик происходит неявно внутри сети),

решение оптимизационных задач.

Многослойные нейронные сети. Архитектура многослойной нейронной сети (МНС) состоит из последовательно соединённых слоёв, где нейрон каждого слоя своими входами связан со всеми нейронами предыдущего слоя, а выходами - следующего.

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

МНС так же используется для непосредственной классификации изображений – на вход подаётся или само изображение в каком-либо виде, или набор ранее извлечённых ключевых характеристик изображения, на выходе нейрон с максимальной активностью указывает принадлежность к распознанному классу (рис. 4). Если эта активность ниже некоторого порога, то считается, что поданный образ не относится ни к одному из известных классов. Процесс обучения устанавливает соответствие подаваемых на вход образов с принадлежностью к определённому классу. Это называется обучением с учителем . Такой подход хорош для задач контроля доступа небольшой группы лиц. Такой подход обеспечивает непосредственное сравнение сетью самих образов, но с увеличением числа классов время обучения и работы сети возрастает экспоненциально. Поэтому для таких задач, как поиск похожего человека в большой базе данных, требует извлечения компактного набора ключевых характеристик, на основе которых можно производить поиск.

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

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

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

МНС применяются и для обнаружения объектов определённого типа. Кроме того, что любая обученная МНС в некоторой мере может определять принадлежность образов к “своим” классам, её можно специально обучить надёжному детектированию определённых классов. В этом случае выходными классами будут классы принадлежащие и не принадлежащие к заданному типу образов. В применялся нейросетевой детектор для обнаружения изображения лица во входном изображении. Изображение сканировалось окном 20х20 пикселей, которое подавалось на вход сети, решающей принадлежит ли данный участок к классу лиц. Обучение производилось как с использованием положительных примеров (различных изображений лиц), так и отрицательных (изображений, не являющихся лицами). Для повышения надёжности детектирования использовался коллектив НС, обученных с различными начальными весами, вследствие чего НС ошибались по разному, а окончательное решение принималось голосованием всего коллектива.

Рисунок 5. Главные компоненты (собственные лица) и разложение изображения на главные компоненты

НС применяется так же для извлечения ключевых характеристик изображения, которые затем используются для последующей классификации. В , показан способ нейросетевой реализации метода анализа главных компонент. Суть метода анализа главных компонент заключается в получении максимально декореллированных коэффициентов, характеризующих входные образы. Эти коэффициенты называются главными компонентами и используются для статистического сжатия изображений, в котором небольшое число коэффициентов используется для представления всего образа. НС с одним скрытым слоем содержащим N нейронов (которое много меньше чем размерность изображения), обученная по методу обратного распространения ошибки восстанавливать на выходе изображение, поданное на вход, формирует на выходе скрытых нейронов коэффициенты первых N главных компонент, которые и используются для сравнения. Обычно используется от 10 до 200 главных компонент. С увеличением номера компоненты её репрезентативность сильно понижается, и использовать компоненты с большими номерами не имеет смысла. При использовании нелинейных активационных функций нейронных элементов возможна нелинейная декомпозиция на главные компоненты. Нелинейность позволяет более точно отразить вариации входных данных. Применяя анализ главных компонент к декомпозиции изображений лиц, получим главные компоненты, называемые собственными лицами , которым так же присуще полезное свойство – существуют компоненты, которые в основном отражают такие существенные характеристики лица как пол, раса, эмоции. При восстановлении компоненты имеют вид, похожий на лицо, причём первые отражают наиболее общую форму лица, последние – различные мелкие отличия между лицами (рис. 5). Такой метод хорошо применим для поиска похожих изображений лиц в больших базах данных. Показана так же возможность дальнейшего уменьшения размерности главных компонент при помощи НС . Оценивая качество реконструкции входного изображения можно очень точно определять его принадлежность к классу лиц.

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

Нейронные сети Хопфилда. НС Хопфилда (НСХ) является однослойной и полносвязной (связи нейронов на самих себя отсутствуют), её выходы связаны со входами. В отличие от МНС, НСХ является релаксационной – т.е. будучи установленной в начальное состояние, функционирует до тех пор, пока не достигнет стабильного состояния, которое и будет являться её выходным значением. Для поиска глобального минимума применительно к оптимизационным задачам используют стохастические модификации НСХ .

Применение НСХ в качестве ассоциативной памяти позволяет точно восстанавливать образы, которым сеть обучена, при подаче на вход искажённого образа. При этом сеть “вспомнит” наиболее близкий (в смысле локального минимума энергии) образ, и таким образом распознает его. Такое функционирование так же можно представить как последовательное применение автоассоциативной памяти, описанной выше. В отличие от автоассоциативной памяти НСХ идеально точно восстановит образ. Для избежания интерференционных минимумов и повышения ёмкости сети используют различные методы .

Самоорганизующиеся нейронные сети Кохонена. Самоорганизующиеся нейронные сети Кохонена (СНСК) обеспечивают топологическое упорядочивание входного пространства образов. Они позволяют топологически непрерывно отображать входное n-мерное пространство в выходное m-мерное, m<

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

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

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

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

Заключение

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

Распознавание образов формальными методами как фундаментальное научное направление является неисчерпаемым.

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

Нейросетевые методы обеспечивают быстрое и надёжное распознавание изображений. Данный подход имеет массу достоинств и является одним из наиболее перспективных.

Литература

Д.В. Брилюк, В.В. Старовойтов. Нейросетевые методы распознавания изображений // /

Кузин Л.Т. Основы кибернетики: Основы кибернетических моделей. Т.2. - М.: Энергия, 1979. - 584с.

Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: Учебное пособие. – М.: Высшая школа, 1997. - 389с.

Темников Ф.Е., Афонин В.А., Дмитриев В.И. Теоретические основы информационной техники. - М.: Энергия, 1979. - 511с.

Ту Дж., Гонсалес Р. Принципы распознавания образов. /Пер. с англ. - М.: Мир, 1978. - 410с.

Уинстон П. Искусственный интеллект. /Пер. с англ. - М.: Мир, 1980. - 520с.

Фу К. Структурные методы в распознавании образов: Пер.с англ. - М.: Мир, 1977. - 320с.

Цыпкин Я.З. Основы информационной теории идентификации. - М.: Наука, 1984. - 520с.

Поспелов Г.С. Искусственный интеллект - основа новой информационной технологии. - М.: Наука, 1988. - 280с.

Ю. Лифшиц, Статистические методы распознавания образов ///modern/07modernnote.pdf

Бор Н. Атомная физика и человеческое познание. /Пер.с англ. - М.: Мир, 1961. - 151с.

Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ.1987.-236с.

Дуда Р., Харт П. Распознавание образов и анализ сцен. /Пер.с англ. - М.: Мир, 1978. - 510с.

Дюк В.А. Компьютерная психодиагностика. - СПб: Братство, 1994. - 365с.

Aizenberg I. N., Aizenberg N. N. and Krivosheev G.A. Multi-valued and Universal Binary Neurons: Learning Algorithms, Applications to Image Processing and Recognition. Lecture Notes in Artificial Intelligence – Machine Learning and Data Mining in Pattern Recognition, 1999, pp. 21-35.

Ranganath S. and Arun K. Face recognition using transform features and neural networks. Pattern Recognition 1997, Vol. 30, pp. 1615-1622.

Головко В.А. Нейроинтеллект: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями – Брест:БПИ, 1999, - 260с.

Vetter T. and Poggio T. Linear Object Classes and Image Synthesis From a Single Example Image. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp. 733-742.

Головко В.А. Нейроинтеллект: Теория и применения. Книга 2. Самоорганизация, отказоустойчивость и применение нейронных сетей – Брест:БПИ, 1999, - 228с.

Lawrence S., Giles C. L., Tsoi A. C. and Back A. D. Face Recognition: A Convolutional Neural Network Approach. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, pp. 1-24.

Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика, 1992 – 184с.

Rowley H. A., Baluja S. and Kanade T. Neural Network-Based Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, pp. 23-37.

Valentin D., Abdi H., O"Toole A. J. and Cottrell G. W. Connectionist models of face processing: a survey. IN: Pattern Recognition 1994, Vol. 27, pp. 1209-1230.

Документ

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

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

   Обзор

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

2. Имени Глазкова Валентина Владимировна ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ПОСТРОЕНИЯ ПРОГРАММНЫХ СРЕДСТВ КЛАССИФИКАЦИИ МНОГОТЕМНЫХ ГИПЕРТЕКСТОВЫХ ДОКУМЕНТОВ Специальность 05

   Автореферат диссертации

   Гипертекстовых документов. В главе приведён обзор существующих методов решения рассматриваемой задачи, описание... отсечением наименее релевантных классов // Математические методы распознавания образов : 13-я Всероссийская конференция. Ленинградская обл...

3. Слайд 0 Обзор задач биоинформатики связанных с анализом и обработкой генетических текстов

   Лекция

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

→

Глава 3: Аналитический обзор методов распознавания образов и принятия решений

Теория распознавания образов и автоматизация управления

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

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

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

Задача формализации предметной области

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

Задача формирования обучающей выборки

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

Задача обучения системы распознавания

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

Задача снижения размерности пространства признаков

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

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

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

Задача контроля качества распознавания

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

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

Задача адаптации

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

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

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

Задачи кластерного и конструктивного анализа

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

Конструктом (в контексте, рассматриваемом в данном разделе) называется система противоположных кластеров. Таким образом, в определенном смысле конструкты есть результат кластерного анализа кластеров.

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

Задача когнитивного анализа

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

Если для двух классов распознавания является характерным один и тот же признак, то это вносит вклад в сходство этих двух классов. Если же для одного из классов этот признак является нехарактерным, то это вносит вклад в различие.

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

Результаты когнитивного анализа могут быть представлены в форме когнитивных диаграмм.

Методы распознавания образов и их характеристики

Принципы классификации методов распознавания образов

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

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

Различные авторы (Ю.Л. Барабаш , В.И. Васильев , А.Л. Горелик, В.А. Скрипкин , Р. Дуда, П. Харт , Л.Т. Кузин , Ф.И. Перегудов, Ф.П. Тарасенко , Ф.Е. Темников , Дж. Ту, Р. Гонсалес , П. Уинстон , К. Фу , Я.З. Цыпкин и др.) дают различную типологию методов распознавания образов. Одни авторы различают параметрические, непараметрические и эвристические методы, другие — выделяют группы методов, исходя из исторически сложившихся школ и направлений в данной области. Например, в работе , в которой дан академический обзор методов распознавания, используется следующая типология методов распознавания образов:

• методы, основанные на принципе разделения;
• статистические методы;
• методы, построенные на основе «потенциальных функций»;
• методы вычисления оценок (голосования);
• методы, основанные на исчислении высказываний, в частности на аппарате алгебры логики.

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

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

Д.А.Поспелов (1990) выделяет два основных способа представления знаний :

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

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

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

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

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

• интенсиональные методы, основанные на операциях с признаками.
• экстенсиональные методы, основанные на операциях с объектами.

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

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

Интенсиональные методы

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

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

Методы, основанные на оценках плотностей распределения значений признаков

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

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

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

Методы, основанные на предположениях о классе решающих функций

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

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

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

Достаточно высокое качество решающего правила может быть достигнуто с помощью алгоритмов, не имеющих строгого математического доказательства сходимости решения к глобальному экстремуму. К таким алгоритмам относится большая группа процедур эвристического программирования, представляющих направление эволюционного моделирования. Эволюционное моделирование является бионическим методом, заимствованным у природы. Оно основано на использовании известных механизмов эволюции с целью замены процесса содержательного моделирования сложного объекта феноменологическим моделированием его эволюции. Известным представителем эволюционного моделирования в распознавании образов является метод группового учета аргументов (МГУА) . В основу МГУА положен принцип самоорганизации, и алгоритмы МГУА воспроизводят схему массовой селекции.

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

Логические методы

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

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

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

Лингвистические (структурные) методы

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

Для различных классов объектов выделяются непроизводные (атомарные) элементы (подобразы, признаки) и возможные отношения между ними. Грамматикой называют правила построения объектов из этих непроизводных элементов.

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

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

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

Экстенсиональные методы

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

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

Метод сравнения с прототипом

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

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

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

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

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

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

Метод k ближайших соседей

Метод k ближайших соседей для решения задач дискриминантного анализа был впервые предложен еще в 1952 году . Он заключается в следующем.

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

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

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

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

Алгоритмы вычисления оценок (»голосования»)

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

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

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

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

• правила вычисления близости объектов по отдельным признакам;
• правила вычисления близости объектов в подпространствах признаков;
• степень важности того или иного эталонного объекта как диагностического прецедента;
• значимость вклада каждого опорного множества признаков в итоговую оценку сходства распознаваемого объекта с каким-либо диагностическим классом.

Параметры АВО задаются в виде значений порогов и (или) как веса указанных составляющих.

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

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

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

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

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

Коллективы решающих правил

В завершение обзора методов распознавания образов остановимся еще на одном подходе. Это так называемые коллективы решающих правил (КРП) .

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

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

Сравнительный анализ методов распознавания образов

Сравним описанные выше методы распознавания образов и оценим степень их адекватности сформулированным в разделе 3.3.3 требованиям к моделям СОУ для адаптивных АСУ сложными системами.

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

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

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

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

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

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

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

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

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

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

Следовательно, остается недостаточно разработанным вопрос о практической применимости тех или иных теоретических методов распознавания для решения практических задач при реальных (т.е. довольно значительных) размерностях данных и на реальных современных компьютерах.

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

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

Это задачи:

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

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

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

• классификация методов распознавания;
• области применения методов распознавания;
• классификация ограничений методов распознавания.

Классификация методов распознавания		Область применения	Ограничения (недостатки)
Интенсиальные методы распознавания	Методы, основанные на оценках плотностей распределения значений признаков (или сходства и различия объектов)	Задачи с известным распределением, как правило, нормальным, необходимость набора большой статистики	Необходимость перебора всей обучающей выборки при распознавании, высокая чувствительность к непредставительности обучающей выборки и артефактам
	Методы, основанные на предположениях о классе решающих функций	Классы должны быть хорошо разделяемыми, система признаков — ортонормированной	Должен быть заранее известен вид решающей функции. Невозможность учета новых знаний о корреляциях между признаками
	Логические методы		При отборе логических решающих правил (коньюнкций) необходим полный перебор. Высокая вычислительная трудоемкость
	Лингвистические (структурные) методы	Задачи небольшой размерности пространства признаков	Задача восстановления (определения) грамматики по некоторому множеству высказываний (описаний объектов), является трудно формализуемой. Нерешенность теоретических проблем
Экстенсиальные методы распознавания	Метод сравнения с прототипом	Задачи небольшой размерности пространства признаков	Высокая зависимость результатов классификации от меры расстояния (метрики). Неизвестность оптимальной метрики
	Метод k ближайших соседей		Высокая зависимость результатов классификации от меры расстояния (метрики). Необходимость полного перебора обучающей выборки при распознавании. Вычислительная трудоемкость
	Алгоритмы вычисления оценок (голосования) АВО	Задачи небольшой размерности по количеству классов и признаков	Зависимость результатов классификации от меры расстояния (метрики). Необходимость полного перебора обучающей выборки при распознавании. Высокая техническая сложность метода
	Коллективы решающих правил (КРП)	Задачи небольшой размерности по количеству классов и признаков	Очень высокая техническая сложность метода, нерешенность ряда теоретических проблем, как при определении областей компетенции частных методов, так и в самих частных методах

Таблица 3.1 — Сводная таблица классификации методов распознавания, сравнения их областей применения и ограничений

Роль и место распознавания образов в автоматизации управления сложными системами

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

Управляющая система осуществляет следующие функции:

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

Распознавание образов есть не что иное, как идентификация состояния некоторого объекта.

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

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

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

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

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

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

Однако в других случаях этот метод малоэффективен.

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

Если нет однозначной связи между входными и выходными параметрами объекта управления (т.е. между входными параметрами и состоянием объекта), иначе говоря, если эта связь имеет выраженный вероятностный характер, то детерминистские модели, в которых предполагается, что результатом измерения некоторого параметра является просто число, изначально неприменимы. Кроме того, вид этой связи просто может быть неизвестным, и тогда необходимо исходить из самого общего предположения: что она вероятностная, либо не определена совсем.

Автоматизированная система управления, построенная на традиционных принципах, может работать только на основе параметров, закономерности связей которых уже известны, изучены и отражены в математической модели, в данном же исследовании поставлена задача разработки таких методов проектирования АСУ, которые позволят создать системы, способные выявлять и набор наиболее значимых параметров, и определять характер связей между ними и состояниями объекта управления.

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

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

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

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

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

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

Факторы могут быть разделены на следующие группы:

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

Таким образом, системы распознавания образов могут быть применены в составе АСУ: в подсистемах идентификации состояния объекта управления и выработки управляющих воздействий.

Это целесообразно в случае, когда объект управления представляет собой сложную систему.

Принятие решения об управляющем воздействии в АСУ

Решение проблемы синтеза адаптивных АСУ сложными системами рассматривается в данной работе с учетом многочисленных и глубоких аналогий между методами распознавания образов и принятия решений.

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

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

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

Многообразие задач принятия решений

Принятие решений как реализация цели

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

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

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

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

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

Принятие решений как снятие неопределенности (информационный подход)

Процесс получения информации можно рассматривать как уменьшение неопределенности в результате приема сигнала, а количество информации — как количественную меру степени снятия неопределенности.

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

Классификация задач принятия решений

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

Перечислим только некоторые из этих вариантов:

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

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

Языки описания методов принятия решений

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

Самым простым, наиболее развитым и наиболее популярным является критериальный язык .

Критериальный язык

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

Пусть, например, {X} — множество альтернатив, а x — некоторая определенная альтернатива, принадлежащая этому множеству: x∈X. Тогда считается, что для всех x может быть задана функция q(x), которая называется критерием (критерием качества, целевой функцией, функцией предпочтения, функцией полезности и т.п.), обладающая тем свойством, что если альтернатива x 1 предпочтительнее x 2 (обозначается: x 1 > x 2), то q(x 1) > q(x 2).

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

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

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

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

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

1. Условная максимизация (находится не глобальный экстремум интегрального критерия, а локальный экстремум основного критерия).
2. Поиск альтернативы с заданными свойствами.
3. Нахождение множества Парето.
4. Сведение многокритериальной задачи к однокритериальной путем ввода интегрального критерия.

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

Введем интегральный критерий q 0 (x), как скалярную функцию векторного аргумента:

q 0 (x) = q 0 ((q 1 (x), q 2 (x), ..., q n (x)).

Интегральный критерий позволяет упорядочить альтернативы по величине q 0 , выделив тем самым наилучшую (в смысле этого критерия). Вид функции q 0 определяется тем, как конкретно мы представляем себе вклад каждого критерия в интегральный критерий. Обычно используют аддитивные и мультипликативные функции:

q 0 = ∑a i ⋅q i /s i

1 - q 0 = ∏(1 - b i ⋅q i /s i)

Коэффициенты s i обеспечивают:

1. Безразмерность или единую размерность числа a i ⋅q i /s i (различные частные критерии могут иметь разную размерность, и тогда над ними нельзя производить арифметических операций и свести их в интегральный критерий).
2. Нормировку, т.е. обеспечение условия: b i ⋅q i /s i <1.

Коэффициенты a i и b i отражают относительный вклад частных критериев q i в интегральный критерий.

Итак, в многокритериальной постановке задача принятия решения о выборе одной из альтернатив сводится к максимизации интегрального критерия:

x * = arg max(q 0 (q 1 (x), q 2 (x), ..., q n (x)))

Основная проблема в многокритериальной постановке задачи принятия решений состоит в том, что необходимо найти такой аналитический вид коэффициентов a i и b i , который бы обеспечил следующие свойства модели:

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

Язык последовательного бинарного выбора

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

Таким образом, основные предположения этого языка сводятся к следующему:

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

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

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

Обобщенный язык функций выбора

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

Групповой выбор

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

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

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

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

Кроме того, существуют так называемые «парадоксы голосования», наиболее известный из которых парадокс Эрроу.

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

Выбор в условиях неопределенности

Определенность — это частный случай неопределенности, а именно: это неопределенность, близкая к нулю.

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

1. Информационная (статистическая) неопределенность исходных данных для принятия решений.
2. Неопределенность последствий принятия решений (выбора).
3. Расплывчатость в описании компонент процесса принятия решений.

Рассмотрим их по порядку.

Информационная (статистическая) неопределенность в исходных данных

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

В этих условиях используется теория статистических решений.

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

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

Необходимо отметить, что существует ряд причин, которые приводят к некорректному применению статистических методов:

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

Неопределенность последствий

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

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

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

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

Рассмотрим такой вид неопределенности, как расплывчатая неопределенность

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

Известно, что все шкалы размыты, но в разной степени. Под термином «размытие» понимается свойство шкал, состоящее в том, что всегда можно предъявить такие две альтернативы, которые различимы, т.е. различны в одной шкале и неразличимы, т.е. тождественны, в другой — более размытой. Чем меньше градаций в некоторой шкале, тем более она размыта.

Таким образом, мы можем четко видеть альтернативы и одновременно нечетко их классифицировать, т.е. иметь неопределенность в вопросе о том, к каким классам они относятся.

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

О некоторых ограничениях оптимизационного подхода

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

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

Для этого заключения имеются достаточно веские основания. Рассмотрим некоторые из них:

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

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

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

Экспертные методы выбора

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

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

На работу эксперта оказывают влияние следующие факторы:

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

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

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

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

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

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

Автоматизированные системы поддержки принятия решений

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

В наше время информационная инфраструктура принятия решений немыслима без автоматизированных систем итерактивной оценки решений и особенно систем поддержки решений (DDS — Decision Support Systems) , т.е. автоматизированных систем, которые специально предназначены для подготовки информации, необходимой человеку для принятия решения. Разработка систем поддержки решений ведется, в частности, в рамках интернационального проекта, осуществляемого под эгидой Международного института прикладного системного анализа в Лаксенбурге (Австрия).

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

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

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