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

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

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

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

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

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

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

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

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

Задачи, возникающие при построении автоматических систем распознавания образов, можно обычно отнести к нескольким основным областям. Первая из них связана с представлением" исходных данных, полученных как результаты измерений для подлежащего распознаванию объекта. Это проблема чувствительности . Каждая измеренная величина является некоторой "характеристикой образа или объекта. Допустим, например, что образами являются буквенно-цифровые символы. 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 Обзор задач биоинформатики связанных с анализом и обработкой генетических текстов

   Лекция

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

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

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

Размещено на 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


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

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

Мотивация

Рассмотрим такую задачу. У нас есть яблоки двух классов - вкусные и не вкусные, 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. Просьба писать в личку обо всех неточностях и опечатках

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 / 4

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

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

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

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

Субтитры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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