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

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

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

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

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

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

(3.34)

Пусть при этом

(3.35)

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

(3.36)

будет приблизительно нормальным с параметрами , .

На основе теоремы Муавра-Лапласа получим соотношение:

(3.37)

где - функция распределения стандартного нормального распределения.

Это соотношение очень важно в условиях применения метода Монте-Карло. Оно предоставляет оценку погрешности, а так же метод расчета .

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

В зависимости от того, какая преследуется цель, можно использовать последнее соотношение по-разному:

Для получения так называемого «правила » можно взять :

(3.38)

2. Для получения же конкретного уровня надежности вычислений получаем следующее выражение:

(3.39)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эффективность моделирования оценивается рядом критериев:

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

Погрешностью (разность между результатом моделирования и истинным значением моделируемой величины).

Затратой машинных ресурсов (времени и памяти).

Стоимостью разработки и эксплуатации модели.

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

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

4.1 Точность

У классификатора как правило используются следующие метрики, входящие в понятие точности:

1). Accuracy (правильность) - данные, по которым классификатор принял правильное решение.

Accuracy=P/N (4.1)

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

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

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

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

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

Таблица 1 - Таблица контингентности

В таблице 1:

TP -- истинно-положительное решение;

TN -- истинно-отрицательное решение;

FP -- ложноположительное решение;

FN -- ложноотрицательное решение.

Тогда точность и полнота определяются следующим образом:

Precision=TP/(TP+FP) (4.2)

Recall=TP/(TP+FN) (4.3)

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

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

Результирующая точность классификатора рассчитывается как арифметическое среднее его точности по всем классам. То же самое с полнотой. Технически этот подход называется macro-averaging.

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

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

F=2(PrecisionЧRecall)/(Precision+Recall) (4.4)

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

F=(в2+1)(PrecisionЧRecall)/(в2Precision+Recall) (4.5)

где в принимает значения в диапазоне 0<в<1 если вы хотите отдать приоритет точности, а при в>1 приоритет отдается полноте. При в=1 формула сводится к предыдущей, и вы получаете сбалансированную F-меру (также ее называют F1).

Рис. 4.1 - Сбалансированная F-мера

Рис. 4.2 - F-мера с приоритетом точности

Рис. 4.3 - F-мера с приоритетом полноты

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

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

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

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

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

(4.6)

Обозначим как истинное значение вероятности ошибочной классификации объектов класса :

(4.7)

Наилучшей точечной оценкой вероятности является относительная частота события :

(4.8)

Качество оценки можно охарактеризовать величиной ее относительной погрешности:

(4.9)

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

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

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

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

2). Вторые добавляют связи между атрибутами. Т.е. учитывают зависимости между атрибутами. Эту группу можно также разделить на eager learning methods, которые обучаются в фазе обучения и lazy learning methods, которые откладывают обучение до начала классификации новых данных

Итак, основные методы классификации:

1). Backwards Sequential Elimination (BSE). Метод BSE оставляет только подмножество изначальных атрибутов. Это достигается с помощью последовательного удаления атрибутов, каждый раз выбирая тот, удаление которого сильнее всего улучшит точность классификатора. Процесс останавливается, когда уже больше нельзя достичь улучшения точности. Классификация производится как и в NB, только на выбранном множестве атрибутов.

2). Forward Sequential Selection (FSS). FSS отличается от предыдущего метода только тем, что начинает с пустого множества атрибутов и на каждом шаге добавляет по одному атрибуту.

3). Backward Sequential Elimination and Joining (BSEJ). Еще одним подходом при обнаружении зависимостей между атрибутами, является создание составных атрибутов. BSEJ использует точность предсказаний в качестве критерия объединения двух атрибутов. В результате получается новых атрибут, принимающий значения из их Декартова произведения. Во время работы алгоритм объединяет или удаляет атрибуты, исходя из того, какое действие сильнее всего улучшит точность предсказаний. Процесс останавливается, когда уже больше нельзя достичь улучшения точности.

4). Tree Augment Naive Bayes (TAN). Этот метод устанавливает зависимости между атрибутами на основе следующего алгоритма: для каждого класса вычисляется I - взаимная информация между всеми парами атрибутов. Затем стоится неориентированный граф, вершинами которого являются атрибуты, а ребро между ними имеет вес I. В этом графе находится максимальное покрывающее дерево. После чего в произвольном порядке расставляются направления ребер.

5). SuperParent TAN (SP-TAN). SP-TAN - это вариация TAN, в которой используется другой подход для построения функции зависимостей между атрибутами.

6). NBTree - это комбинация NB и дерева принятие решений. Идея состоит в том, что на основании значений некоторых атрибутов мы разделяем данные, так, что получается дерево. А затем в каждом листе этого дерева создаем локальный NB.

7). Lazy Bayesian Rules (LBR). Результаты работы LBR похожи на NBTree, только LBR использует lazy learning и для каждого тестового примера генерирует новый путь в дереве решений. Классификация производится аналогично NBTree. Так как NBTree строит одно дерево для всей обучающей выборки, то в нем могут образоваться листья, содержащие всего несколько элементов из выборки. И это может ухудшить классификацию. С этой проблемой и борется LBR. LBR хорошо подходит, когда надо классифицировать немного элементов.

8). Averaged One-Dependence Estimators (AODE). AODE усредняет предсказания всех подходящих классификаторов. Это делается, чтобы не производить выбор модели и сохранить эффективность классификаторов.

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

В результате экспериментов (Zheng and Webb, 2005) были получены следующие результаты:

1). Алгоритмы с наименьшим смещением: NBTree, BSJE, LBR, AODE, TAN, SP-TAN.

2). Алгоритмы с наименьшей дисперсией: NB, AODE, LBR, SP-TAN, BSE.

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

Рис. 4.4 - Вычислительная сложность методов классификации

Заключение

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

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

Рассмотрено сравнение качества работы алгоритмов.

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

Рассмотрены задачи классификации.

Изучены методы оценки качества и эффективности классификации.

Изучен метод моделирования по принципу Монте-Карло.

Литература

Денисов, И.Е. Верификация подписей и ее алгоритмы / И.Е. Денисов, А.А. Суконщиков // Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования : материалы XII Международной научно-технической конференции / Вологодский государственный университет. - Вологда, 2017. - С. 77-80.

Денисов, И.Е. Применение байесовских методов при решении задачи распознавания образов / И.Е. Денисов, А.А. Суконщиков // Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования : Материалы девятой Международной научно-технической конференции / Вологодский государственный университет. - Вологда, 2014. - С. 74-76.

Денисов, И.Е. Модель TAN при решении задачи классификации образов / И.Е. Денисов, А.А. Суконщиков // Информатизация процессов формирования открытых систем на основе СУБД, САПР, АСНИ и систем искусственного интеллекта / Вологодский государственный университет. - Вологда, 2015. - С. 53-57.

Денисов, И.Е. Задача классификации алгоритма Байеса при распознавании образов / И.Е. Денисов, А.А. Суконщиков // Бизнес. Наука. Образование: проблемы, перспективы, стратегии : Материалы Российской научно-практической конференции с международным участием / Вологодский институт бизнеса, 2015. - С. 464-467.

Грузман И.С., Киричук В.С., Косых В.П., Перетягин Г.И., Спектор А.А. Цифровая обработка изображений в информационных системах: Учебное пособие - Новосибирск, издательство НГТУ, 2002, 352 с.

H.B. Верденская, Байесовский риск как критерий качества в задаче сегментации изображений., VII Международная конференция «Радиолокация. Навигация. Связь.» Россия, Воронеж, Сб. трудов, т.2, 2001 г.

Шапиро Л., Стокман Дж. Компьютерное зрение. - М., БИНОМ. - 2008

С.А. Шумский. Байесова регуляризация обучения. сб. Лекции по нейроинформатике, часть 2, 2002

Математические методы распознавания образов: курс лекций / сост.: Л.М. Местецкий. - МГУ: кафедра «Математические методы прогнозирования», 2004.

Business Data Analytics [Электронный ресурс]: Статьи. - Режим доступа: http://www.businessdataanalytics.ru.

Соболь, И.М. Популярные лекции по математике / И.М. Соболь // Наука. -1968. - №46. - С. 46.

Шлезингер, М. И. Десять лекций по статистическому и структурному распознаванию / М. И. Шлезингер, В. Главач. - Киев: Наукова думка, 2004. - 554 c.

Математические методы распознавания образов: курс лекций / сост.: Л.М. Местецкий. - МГУ: кафедра «Математические методы прогнозирования», 2004.

Размещено на Allbest.ru