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

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

Оглавление

Оглавление

1. Введение

1.1 Актуальность проблемы

1.2 Цель и задачи работы

1.3 Методы исследования

1.4 Научные результаты

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

1.6 Апробация работы

1.7 Положения, выносимые на защиту

2. Теоретические основы распознавания образов

2.1 Основные понятия задачи распознавания

2.2 Распознавание образов в задаче верификации подписей

2.3 Функциональная схема системы распознавания

3. Байесовский метод распознавания

3.1 Применение байесовских методов при решении задачи распознавания образов

3.2 Основы байесовского метода

3.3 Байесовская сегментация изображений

3.4 Задача классификации алгоритмом Байеса при распознавании образов

3.5 Модель TAN при решении задачи классификации образов

3.6 Моделирование по принципу Монте-Карло

4. Оценка эффективности

4.1 Точность

4.2 Погрешность

4.3 Ресурсоемкость

Заключение

Литература



1. Введение

1.1 Актуальность проблемы

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

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

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

При этом не стоит забывать, что эти механизмы часто встречаются и в жизни обычного человека: камеры контроля скорости (распознающие номера автомобилей-нарушителей), голосовые помощники в новейших операционных системах (Siri, Cortana, Google Now), системы доступа (Touch ID, Face ID), автоответчики в call-центрах (яркий пример в России - call-центр Ростелекома).

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

Актуальность данной задачи обуславливается потребностью общества в глубокой интеграции мультимедиа-сервисов в повседневную жизнь. Например, примерно 7% запросов к поисковым системам Google и Яндекс переданы в виде изображений. Кроме того, популяризация систем дополненной реальности, таких как Google Glass, так же вносит огромный вклад в дальнейшее развитие технологий.

1.2 Цель и задачи работы

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

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

1.3 Методы исследования

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



1.4 Научные результаты

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

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

2). Применение байесовского метода сегментации при помощи распределения Гиббса.

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

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

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

1.6 Апробация работы

Основные результаты работы докладывались и получили положительную оценку на следующих конференциях: XII Международной научно-технической конференции: «Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования» (Вологда, 2017 г.); девятой Международной научно-технической конференции: «Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования» (Вологда, 2014 г.); «Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта» (Вологда, 2015 г.); Российской научно-практической конференции с международным участием: «Бизнес. Наука. Образование: проблемы, перспективы, стратегии» (Вологда, 2015 г.).

1.7 Положения, выносимые на защиту

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



2. Теоретические основы распознавания образов

2.1 Основные понятия задачи распознавания

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

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

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

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

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

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

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

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

Цель распознавания образов - это классификация объектов по категориям или классам.

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

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

Примеры интеллектуальных компьютерных систем:

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

Символьное распознавание -распознавание цифр и букв.

Диагностика в медицине.

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

Геология.

Распознавание отпечатков пальцев в дактилоскопии, распознавание лиц, подписей, жестов.

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

Классификатор или решающее правило - это правило отнесения образа к одному из классов на основании его вектора признаков.

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

2.2 Распознавание образов в задаче верификации подписей

Рассмотрим применение распознавания образов в рамках решаемой задачи автоматизации верификации подписей.

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

Процесс аутентификации по подписи разделяют на несколько этапов:

Регистрация эталона подписи. Человек вводит несколько раз подпись, собирается статистика.

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

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

Сравнение характеристик эталона и образца.

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

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

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

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

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

Одним из наиболее популярных на данный момент алгоритмов распознавания подписей является распознавание образов.

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

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

Помимо того, существуют и другие алгоритмы:

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

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

(2.1)

Где - расстояние между -й и -й координатами.

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

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

2.3 Функциональная схема системы распознавания

Рис. 2.1 - Функциональная схема системы распознавания

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

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

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

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

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

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

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



3. Байесовский метод распознавания

3.1 Применение байесовских методов при решении задачи распознавания образов

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

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

Формула Байеса вытекает из определения условной вероятности. Вероятность совместного события AB двояко выражается через условные вероятности:

(3.1)

Отсюда:

(3.2)



В данной формуле:

- априорная вероятность гипотезы A,

- вероятность гипотезы A при наступлении события B (апостериорная вероятность),

- вероятность наступления события B при истинности A,

- полная вероятность наступления события B.

Преимущества байесовского подхода:

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

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

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

3.2 Основы байесовского метода

распознавание образ байесовский изображение

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

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

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

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

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

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

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

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

(3.3)

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

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

Пусть это плотность распределения элементов вектора при том условии, что он принадлежит классу . Известно, что вероятность принадлежности к классу определяется формулой Байеса:

(3.4)

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

(3.5)

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

(3.6)

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

+, (3.7)

а при выборе стратегии (гипотезы) -

+. (3.8)

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

+

+ (3.9)



или:

(3.10)

Считается, что потери от неверно принятого решения выше «потерь» при верном выборе. Этому соответствует неравенство . В этом случае байесовское решающее правило (3.10) примет следующий вид:

(3.11)

или

(3.12)

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

(3.13)

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

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

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



3.3 Байесовская сегментация изображений

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

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

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

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

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

Оптимальная сегментация, основывающаяся на байесовском принципе, должна вырабатывать результат , которому будет соответствовать максимум апостериорного распределения вероятностей (АРВ):

, (3.14)

где - результат оптимальной сегментации.

Располагая совместным распределением:

(3.15)

Возможно найти апостериорное распределение вероятностей, так как:

(3.16)

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

Эти выкладки позволяют вместо выражения (3.14) для отыскания оптимального результата использовать следующее:

(3.17)

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

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

На первом шаге итерационного процесса случайное поле формируется при помощи датчика случайных чисел с равномерным распределением вероятностей на интервале [0, 1]. Для этого интервал разбивают на два подынтервала, а в качестве граничной точки принимают значение вероятности того, что . При неизвестном значении его принимают равным 0,5. С помощью датчика формируется число , которое далее путем сравнения с порогом преобразуется в по следующему правилу:

(3.18)

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

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

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

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

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

Пусть - это результат работы датчика. Тогда результат данного микрошага сформируется по правилу:

(3.19)

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

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

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

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

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

, (3.20)

где

(3.21)

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

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

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

3.4 Задача классификации алгоритмом Байеса при распознавании образов

Одной из наиболее распространенных задач в распознавании образов является задача классификации.

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

Существует несколько подходов к распознаванию образов:

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

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

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

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

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

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

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

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

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

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

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

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

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

(3.22)



для всех атрибутов Xi, Xj и значений класса C. Данное предположение во многих случаях неправомерно, поэтому сам факт эффективности классификации «наивным» алгоритмом Байеса является весьма неожиданным.

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

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

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

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

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



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

Рис. 3.1 - Байесовская сеть

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

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

Рис. 3.2 - «Наивный» алгоритм Байеса

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

Основные недостатки метода:

Высокая сложность вычисления

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

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

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

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

Рис. 3.3 - Модифицированный древовидный алгоритм Байеса

В данной модели, совместное распределение вероятности переменных {X1, …, Xn} определяется заданием структуры графа (т.е. набором родительских переменных Пi для каждой переменной Xi) и параметрами модели (т.е. величинами иi(x, y):=P(Xi=x|ПXi=y)). Оценка параметров модели, заданной графом G, методом максимального правдоподобия по выборке D равна соответствующим выборочным значениям. Оптимальная структура модели (с точки зрения функции правдоподобия) соответствует модели с максимальной суммарной взаимной информацией между узлами и их родителями.

3.5 Модель TAN при решении задачи классификации образов

Рассмотрим байесовские модели для решения задач классификации. Т.е. среди рассматриваемых случайных переменных мы выделяем одну переменную C (переменная класса), которую в дальнейшем мы будем обозначать отдельно от остального набора переменных {X1, …, Xn}.

За основу возьмем модель «наивного» (упрощенного) Байеса, т.е. модель, где каждый узел зависит только от классифицирующей переменной.

Для данной модели имеем:

(3.23)

(3.24)

Это условие можно сформулировать как:

(3.25)

Мы расширим «наивную» модель Байеса добавив взаимосвязи между узлами модели. Однако, ограничимся рассмотрением только таких графов, где у каждого узла не может быть более одного родителя за исключением узла C. Модель с такими ограничениями называется в литературе TAN (Tree Augmented Naive Bayes).

Модель TAN можно описать как:

(3.26)

Определим оптимальную структуру для модели TAN. Введем понятия условной по случайной величине Z взаимной информации случайных величин X и Y:

(3.27)

Таким образом справедливо следующее:

(3.28)

Так как у классифицирующего узла С отсутствуют родители, то:

(3.29)

Далее, по определению модели TAN справедливо. Обозначим - множество родителей узла Xi за исключением узла С. Тогда - либо пустое множество, либо содержит только один узел из {X1,…,Xn}. Отсюда получаем:

(3.30)

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

3.31

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

Для каждой пары переменных определяем величину взаимной условной по C информации .

Строим ненаправленный полный граф с узлами из {X1,…,Xn} и дугами с весами .

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

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

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

Добавляем дуги из классифицирующего узла C ко всем остальным узлам графа.

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

Очевидными недостатками приведенного алгоритма являются:

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

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

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

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

(3.32)

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

(3.33)

3.6 Моделирование по принципу Монте-Карло

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