Последовательные методы распознавания образов. Экспертные методы выбора. Методы распознавания образов и их характеристики

Простой случай, одномерное разделение

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

И напоследок

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

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

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

4. История распознавания образов

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

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

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

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

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

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

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

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

Рис 1. Схема Персептрона

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

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

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

Кроме того топология нейронной сети могла быть значительно сложнее той, что рассматривал Розенблатт, например такой:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Документ

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

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

   Обзор

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

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

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

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

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

   Лекция

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

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

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

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

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

Энциклопедичный YouTube

1 / 4

Введение в распознавание образов

Р.В. Шамин. Лекция № 6 Сети Хопфилда и Хемминга в задачах распознавания образов

[ДДШ-2016]: Нейронные сети и современное компьютерное зрение

Лекция 9. Экспоненциальное сглаживание. Распознавание образов: метод к-го ближайшего соседа

Субтитры

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

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

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

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

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

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

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

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

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

Некоторые методы распознавания графических образов

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

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

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

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

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

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

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

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

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

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

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

Мотивация

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

Заключение

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

• 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

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