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

Sun, Mar 29, 2015

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

Рассмотрим общие элементы модели классификации.

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

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

Верификация - процесс сопоставления экземпляра объекта с одной моделью объекта или описанием класса.

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

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

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

Примерами задач классификации являются:

• распознавание символов;
• распознавание речи;
• установление медицинского диагноза;
• прогноз погоды;
• распознавание лиц
• классификация документов и др.

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

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

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

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

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

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

где d - размерность вектора признака.

Разделяют 3 группы методов распознавания образов:

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

Классификация по ближайшему среднему значению

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

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

где x(i,j)- j-й эталонный признак класса i, n_j- количество эталонных векторов класса i.

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

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

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

Будем учитывать характеристику «разброса» значений класса - σ_i, вдоль каждого координатного направления i. Среднеквадратичное отклонение равно квадратному корню из дисперсии. Шкалированное евклидово расстояние между вектором x и вектором математического ожидания x_c равно

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

Классификация по расстоянию до ближайшего соседа

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

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

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

Кроме того, решение будет лучше, если искать в базе не одного ближайшего соседа, а k. Тогда при k > 1 обеспечивает наилучшую выборку распределения векторов в d-мерном пространстве. Однако эффективное использование значений k зависит от того, имеется ли достаточное количество в каждой области пространства. Если имеется больше двух классов то принять верное решение оказывается сложнее.

Литература

• M. Castrillón, . O. Déniz, . D. Hernández и J. Lorenzo, «A comparison of face and facial feature detectors based on the Viola-Jones general object detection framework,» International Journal of Computer Vision, № 22, pp. 481-494, 2011.
• Y.-Q. Wang, «An Analysis of Viola-Jones Face Detection Algorithm,» IPOL Journal, 2013.
• Л. Шапиро и Д. Стокман, Компьютерное зрение, Бином. Лаборатория знаний, 2006.
• З. Н. Г., Методы распознавания и их применение, Советское радио, 1972.
• Дж. Ту, Р. Гонсалес, Математические принципы распознавания образов, Москва: “Мир” Москва, 1974.
• Khan, H. Abdullah и M. Shamian Bin Zainal, «Efficient eyes and mouth detection algorithm using combination of viola jones and skin color pixel detection» International Journal of Engineering and Applied Sciences, № Vol. 3 № 4, 2013.
• V. Gaede и O. Gunther, «Multidimensional Access Methods,» ACM Computing Surveys, pp. 170-231, 1998.

Мотивация

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема

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

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

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

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

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

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

Заключение

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

• The Nature of Statistical Learning Theory, Vladimir N. Vapnik
• Pattern Classification, 2nd Edition, Richard O. Duda, Peter E. Hart, David G. Stork
• Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Ссылки

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

Литература

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

• А.Л.Горелик, В.А.Скрипкин , Методы распознавания, М.: Высшая школа, 1989.
• Ш.-К. Чэн , Принципы проектирования систем визуальной информации, М.: Мир, 1994.

Wikimedia Foundation . 2010 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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