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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

хорошую работу на сайт">

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

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Новосибирский государственный университет экономики и управления «НИНХ»

Информационно-технический факультет

Кафедра прикладных информационных технологий

по дисциплине Нечеткая логика и нейронные сети

Распознавание образов

Направление: Бизнес-информатика (электронный бизнес)

Ф.И.О студента: Мазур Екатерина Витальевна

Проверил: Павлова Анна Илларионовна

Новосибирск 2016

  • Введение
  • 1. Понятие распознавания
    • 1.1 История развития
    • 1.2 Классификация методов распознавания образов
  • 2. Методы распознавания образов
  • 3. Общая характеристика задач распознавания образов и их типы
  • 4. Проблемы и перспективы развития распознавания образов
    • 4.1 Применение распознавания образов на практике
  • Заключение

Введение

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

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

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

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

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

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

распознавание образ применение

1. Понятие распознавания

Долгое время проблема распознавания привлекала внимание только ученых области прикладной математики. В результате, работы Р. Фишера, созданные в 20-х годах , привели к формированию дискриминантного анализа - одного из разделов теории и практики распознавания образов. В 40-х годах А. Н. Колмогоровым и А. Я. Хинчиным была поставлена цель о разделении смеси двух распределений. А в 50-60-е годы ХХ века на основе большого количества работ появилась теория статистических решений. В рамках кибернетики начало складываться новое направление, связанное с разработкой теоретических основ и практической реализацией механизмов, а также систем, предназначенных для распознавания объектов и процессов. Новая дисциплина получила название "Распознавание образов".

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

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

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

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

Примерами задач распознавания образов являются:

Распознавание букв;

Распознавание штрих-кодов;

Распознавание автомобильных номеров;

Распознавание лиц и других биометрических данных;

Распознавание речи и др..

1.1 История развития

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

Рисунок 1 - Схема Персептрона

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

Рис. 2 Схема нейронной сети.

Кроме того, топология нейронной сети могла быть еще более усложненной. Например, такой:

Рисунок 3 - Схема нейронной сети Розенблатта.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Область применения

Ограничения (недостатки)

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

Методы, основанные на оценках плотностей

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

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

Методы, основанные на предположениях

Классы должны быть хорошо разделяемыми

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

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

Задачи небольшой размерности

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

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

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

Экстенсиальные методы распознавания

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

Задачи небольшой размерности пространства признаков

Высокая зависимость результатов классификации от метрики. Неизвестность оптимальной метрики

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

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

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

Задачи небольшой размерности по количеству классов и признаков

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

Коллективы решающих правил (КРП) - синтетический метод.

Задачи небольшой размерности по количеству классов и признаков

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

3. Общая характеристика задач распознавания образов и их типы

Общая структура системы распознавания и ее этапы показаны на рисунке 4:

Рисунок 4 - Структура системы распознавания

Задачи распознавания имеют следующие характерные этапы:

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

Распознавание (указание принадлежности объекта определенному классу).

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

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

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

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

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

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

Задача выбора информативного набора атрибутов при распознавании;

Задача приведения исходных данных к удобному виду;

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

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

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

Проблема «1001 класса» - добавление 1 класса к 1000 существующим вызывает трудности с переобучением системы и проверке данных, полученных до этого;

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

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

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

4.1 Применение распознавания образов на практике

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

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

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

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

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

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

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

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

Заключение

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

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

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

Список литературы

1. Дэвид Формайс, Жан Понс Компьютерное зрение. Современный подход, 2004

2. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 2004.

3. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. М.: Наука, 2005. - Вып. 33.

4. Мазуров В.Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 2004, № 2.

5. Потапов А.С. Распознавание образов и машинное восприятие. - С-Пб.: Политехника, 2007.

6. Минский М., Пейперт С. Персептроны. - М.: Мир, 2007.

7. Растригин Л. А., Эренштейн Р. Х. Метод коллективного распознавания. М. Энергоиздат, 2006.

8. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. - М.: Наука, 2007.

9. Фу К. Структурные методы в распознавании образов. - М.: Мир, 2005.

Размещено на Allbest.ru

...

Подобные документы

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

    курсовая работа , добавлен 15.01.2014

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

    презентация , добавлен 06.01.2014

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

    дипломная работа , добавлен 13.10.2017

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

    курсовая работа , добавлен 05.04.2015

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

    курсовая работа , добавлен 15.08.2011

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

    дипломная работа , добавлен 06.04.2014

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

    реферат , добавлен 10.04.2010

    Понятие системы распознавания образов. Классификация систем распознавания. Разработка системы распознавания формы микрообъектов. Алгоритм для создания системы распознавания микрообъектов на кристаллограмме, особенности его реализации в программной среде.

    курсовая работа , добавлен 21.06.2014

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

    курсовая работа , добавлен 14.11.2013

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

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

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

Традиционно задачи распознавания образов включают в круг задач искусственного интеллекта .

Направления в распознавании образов

Можно выделить два основных направления :

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

Формальная постановка задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программы распознавания образов

См. также

Примечания

Ссылки

  • Юрий Лифшиц. Курс «Современные задачи теоретической информатики» - лекции по статистическим методам распознавания образов, распознаванию лиц, классификации текстов
  • Journal of Pattern Recognition Research (Журнал исследования распознавания образов)

Литература

  • Дэвид А. Форсайт, Джин Понс Компьютерное зрение. Современный подход = Computer Vision: A Modern Approach. - М.: «Вильямс» , 2004. - С. 928. - ISBN 0-13-085198-1
  • Джордж Стокман, Линда Шапиро Компьютерное зрение = Computer Vision. - М.: Бином. Лаборатория знаний, 2006. - С. 752. - ISBN 5947743841
  • А.Л.Горелик, В.А.Скрипкин , Методы распознавания, М.: Высшая школа, 1989.
  • Ш.-К. Чэн , Принципы проектирования систем визуальной информации, М.: Мир, 1994.

Wikimedia Foundation . 2010 .

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

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

Англ. recognition, image; нем. Gestalt alterkennung. Раздел математической кибернетики, разрабатывающий принципы и методы классификации и идентификации объектов, описываемых конечным набором признаков, характеризующих их. Antinazi. Энциклопедия… … Энциклопедия социологии

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

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

РАСПОЗНАВАНИЕ ОБРАЗОВ - раздел математической кибернетики, разрабатывающий и методы классификации, а также идентификации предметов, явлений, процессов, сигналов, ситуаций всех тех объектов, к рые могут быть описаны конечным набором нек рых признаков или свойств,… … Российская социологическая энциклопедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мотивация

Рассмотрим такую задачу. У нас есть яблоки двух классов - вкусные и не вкусные, 1 и 0. Яблоки обладают признаками - цветом и размером. Цвет изменятся непрерывно от 0 до 1, т.е. 0 -полностью зеленое яблоко, 1 - полностью красное. Размер может меняться аналогично, 0 - яблоко маленькое, 1 - большое. Мы хотели бы разработать алгоритм, который бы получал на вход цвет и размер, а на выходе отдавал класс яблока - вкусное оно или нет. Весьма желательно, чтобы число ошибок при этом было чем меньше тем лучше. При этом мы обладаем конечным списком, в котором указаны исторические данные о цвете, размере и классе яблок. Как бы мы могли решать такую задачу?

Логический подход

Решая нашу задачу, первый метод, который возможно придет на ум, может быть такой: давайте вручную составим правила типа if-else и в зависимости от значений цвета и размера будем присваивать яблоку определенный класс. Т.е. у нас есть предпосылки - это цвет и размер, и есть следствие - вкус яблока. Вполне разумно, когда признаков немного и можно на глаз оценить пороги для сравнения. Но может случится так, что придумать четкие условия не получится, и из данных не очевидно какие пороги брать, да и число признаков может увеличиваться в перспективе. А что делать, если в нашем списке с историческими данными, мы обнаружили два яблока с одинаковыми цветом и размером, но одно помечено как вкусное, а другое нет? Таким образом наш первый метод не настолько гибкий и масштабируемый, как нам бы хотелось.

Обозначения

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

Вероятностный подход

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

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

Рассмотрим правую часть этого выражения более подробно. Множитель называется априорной вероятностью и означает вероятность встретить вкусное яблоко среди всех возможных яблок. Априорная вероятность встретить невкусное яблоко есть . Эта вероятность может отражать наше личное знание о том, как распределены вкусные и невкусные яблоки в природе. Например, по нашему прошлому опыту мы знаем, что 80% всех яблок - вкусные. Или мы можем оценить это значение просто посчитав долю вкусных яблок в нашем списке с историческими данными S. Следующий множитель - показывает, насколько вероятно получить конкретное значение цвета и размера для яблока класса 1. Это выражение так же называется функцией правдоподобия и может иметь вид какого-нибудь конкретного распределения, например, нормального. Знаменатель мы используем в качестве нормировочной константы, что бы искомая вероятность изменялась в пределах от 0 до 1. Нашей конечной целью является не поиск вероятностей, а поиск решающего правила, которое бы сразу давало нам класс. Конечный вид решающего правила зависит от того, какие значения и параметры нам известны. Например, мы можем знать только значения априорной вероятности, а остальные значения оценить невозможно. Тогда решающее правило будет такое - ставить всем яблокам значение того класса, для которого априорная вероятность наибольшая. Т.е. если мы знаем, что 80% яблок в природе вкусные, то каждому яблоку ставим класс 1. Тогда наша ошибка составит 20%. Если же мы к тому же можем оценить значения функции правдоподобия $p(X=x_m | Y=1)$, то можем и найти значение искомой вероятности по формуле Байеса, как написано сверху. Решающее правило здесь будет таким: поставить метку того класса, для которого вероятность максимальна:

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

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

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

Потери от ошибок классификатора

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

Условный и байесовский риск

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

В нашем случае бинарной классификации когда получается:

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

Некоторые типовые функции потерь

Одной из наиболее частовстречающихся функций потерь является симметричная функция, когда потери от первого и второго типов ошибок равнозначны. Например, функция потерь 1-0 (zero-one loss) определяется так:

Тогда условный риск для a(x) = 1 будет просто значением вероятности получить класс 0 на объектке :

Аналогично для a(x) = 0:

Функция потерь 1-0 принимает значение 1, если классификатор делает ошибку на объекте и 0 если не делает. Теперь сделаем так, чтобы значение на ошибке равнялось не 1, а другой функции Q, зависящей от решающего правила и реальной метки класса:

Тогда условный риск можно записать так:

Замечания по нотации

Предыдущий текст был написан согласно нотации, принятой в книге Дуды и Харта. В оригинальной книге В.Н. Вапника рассматривался такой процесс: природа выбирает объект согласно распределению $p(x)$, а затем ставит ему метку класса согласно условному распределению $p(y|x)$. Тогда риск(матожидание потерь) определяется как

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

Эмпирический риск

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

Пример: пусть множество всех функций вида

Все функции этого множества будут отличаться друг от друга только коэффициентами Когда мы выбрали такое семейство, мы предположили, что в координатах цвет-размер между точками класса 1 и точками класса 0 можно провести прямую линию с коэффициентами таким образом, что точки с разными классами находятся по разные стороны от прямой. Известно, что у прямой такого вида вектор коэффициентов является нормалью к прямой. Теперь делаем так - берем наше яблоко, меряем у него цвет и размер и наносим точку с полученными координатами на график в осях цвет-размер. Далее меряем угол между этой точкой и вектором $w$. Замечаем, что наша точка может лежать либо по одну, либо по другую сторону от прямой. Тогда угол между и точкой будет либо острый, либо тупой, а скалярное произведение либо положительное, либо отрицательное. Отсюда вытекает решающее правило:

После того как мы зафиксировали класс функций $Н$, возникает вопрос - как выбрать из него функцию с нужными коэффициентами? Ответ - давайте выберем ту функцию, которая доставляет минимум нашему байесовскому риску $R()$. Опять проблема - чтобы посчитать значения байесовского риска, нужно знать распределение $p(x,y)$, а оно нам не дано, и восстановиь его не всегда возможно. Другая идея - минимизировать риск не на всех возможных объектах, а только на выборке. Т.е. минимизировать функцию:

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

Гарантии сходимости. Простейший случай

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

Теорема

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

Что значит «небольшое значение» и «достаточный размер» см. в литературе ниже.

Идея доказательства

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

Практические результаты

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

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

Для логистической регресии:

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

Заключение

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

Используемая литература

  • The Nature of Statistical Learning Theory, Vladimir N. Vapnik
  • Pattern Classification, 2nd Edition, Richard O. Duda, Peter E. Hart, David G. Stork
  • Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David
P.S. Просьба писать в личку обо всех неточностях и опечатках

Теги: Добавить метки

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


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