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

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

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

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

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

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

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

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

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

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

   Лекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 / 4

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

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

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

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

Субтитры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мотивация

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

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

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

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

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

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

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

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

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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