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

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

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

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

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

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

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

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

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

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

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

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

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

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

В литературе, посвященной проблеме обучения распознавания образов (ОРО), часто вместо понятия образа вводится понятие класса.

Проблема обучения распознаванию образов (ОРО)

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

Рассмотрим пример задач из области ОРО.

Рис. 3.1.

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

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

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

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

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

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

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

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

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

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

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

Цели науки распознавания образов:

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

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

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

1.Это информационные задачи, состоящие из двух основных этапов: приведение исходных данных к виду, удобному для распознавания и собственно распознавание.

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

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

4. Для этих задач трудно строить формальные теории и применять классические математические методы.

5. В этих задачах возможна «плохая» информация.

Типы задач распознавания:

Отнесение предъявленного объекта к одному из классов (обучение с учителем);

Автоматическая классификация – разбиение множества объектов (ситуаций) по их описанияю на систему непересекающихся классов;

Выбор набора информатиыных признаков при распощнавании;

Приведение исходных данных к виду, удобному для распознавания;

Динамическое распознавание и динамическая классификация;

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

Основные определения

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

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

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

ОБЪЕКТ->Nпризнаков->M-мерный вектор признаков

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

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

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

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

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

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

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

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

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

Глава 3: Системы распознавания образов (идентификации)

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

Понятие образа

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

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

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

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

В литературе, посвященной проблеме обучения распознавания образов (ОРО), часто вместо понятия образа вводится понятие класса.

Проблема обучения распознаванию образов (ОРО)

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

Рассмотрим пример задач из области ОРО.

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

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

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

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

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

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

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

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

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

Геометрический и структурный подходы.

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

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

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

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

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

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

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

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

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

Гипотеза компактности

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

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

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

Обучение и самообучение. Адаптация и обучение

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

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

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

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

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

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

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

Лекция № 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. Сигнал ошибки при гармоническом входном воздействии для модели с нечетким регулятором, содержащим две входные лингвистические переменные.

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

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