_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185319), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

Метод БайесаОдним из наиболее распространенных и хорошо зарекомендовавших себя напрактике методов получения коллективных решений является метод Байеса. В данномслучаедляпостроенияколлективногорешенияпредполагаетсяиспользоватьстатистические свойства выборки. Допустим, что отдельные алгоритмы комитетаявляются попарно-независимыми. Пусть имеется p алгоритмов - классификаторов A j и lклассов K i .

Для каждого классификатора A j вычисляется матрица «отметок»LMjразмерности l  l путем применения A j к обучающей выборке. Элементы матрицыпредставляют собой оценки условных вероятностей:P( K t | A j ( S )  K u ), t , u  1,2,..., l .Далее, в предположении о независимости классификаторов, оценкаi (S )апостериорной вероятности принадлежности к классу K i вычисляется как произведениеусловных вероятностей возникновенияi -огокласса при условии, что каждыйклассификатор отнес текущий объект S к некоторому своему классу K j , т.е.pi ( S )   P( Ki | Aj ( S )  K j ) , i  1,2,..., l .j 1Метод Байеса обладает высокой скоростью работы и, как следствие, может бытьиспользован в случае большого количества алгоритмов, составляющих комитет.92Ограничения на его применение накладывает требование независимости отдельныхклассификаторов.

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

Для определения наилучшего алгоритма необходимо провестипроцедуру обучения алгоритма синтеза коллективного решения. Для этого используетсяконтрольная выборка, которая, в частном случае, может совпадать с обучающей. Введемотображения D : R  {1,..., f } , ставящее в соответствие каждой точке пространстваnобъектов номер соответствующей подобласти, F :{1,..., f }  {1,..., p} , по которому длякаждой подобласти осуществляется выбор соответствующего классификатора, иE : R n  {1,..., p} , которое каждой точке пространства ставит в соответствие номерклассификатора. Тогда в общем виде можно записать схему работы полученногоалгоритма следующим образомA( S )  AE ( S ) ( S )Агрегирующиеалгоритмыэтойгруппыразличаютсяспособамивыбораотображений E(.).

Рассмотрим некоторые из них. Если удается представить отображениеE(.) в виде декомпозиции E ( S )  F ( D( S )) , то говорят о статическом выборе областейкомпетенции. В противном случае происходит динамический выбор алгоритмараспознавания. Среди первой группы методов обычно функция F(.) имеет видF ( j )  arg max i ( D j ) , где D j - соответствующая подобласть, а  i ( D ) - некоторый1i  pпоказатель эффективности работы (например, доля правильных ответов) i-ого алгоритма вобласти D.

В качестве отображения D(.) обычно используются те или иные методыкластеризации /19/. Соответствующие подобласти называются областями компетенции. Вметодеобластейкомпетенции,реализованномвпрограммномкомплексе93РАСПОЗНАВАНИЕ, используется кластеризация исходного признакового пространстваметодом k-средних. Работа метода существенно зависит от количества областейкомпетенции, заданного пользователем. При k=1 имеет место классификация всехобъектов наилучшим из исходных алгоритмом. При слишком большом числе областейкомпетенции возможны многочисленные неоправданные переключения с метода наметод, приводящие к неустойчивой классификации и деградации коллективного решения.Методобластейкомпетенцииотличаетсявысокойскоростьюраспознаванияиотносительно небольшим временем обучения /47/.Одним из подходов при динамическом выборе алгоритма является использованиенекоторого алгоритма распознавания в качестве E(.).

В этом случае получается следующаядвухуровневая задача распознавания образов. На первом этапе каждый объект относится кодному из классов исходными алгоритмами, а на втором – объект ассоциируется с однимиз этих алгоритмов (который и будет использоваться для окончательного распознавания) спомощью другого алгоритма распознавания.Другим подходом является определение меры компетенции каждого алгоритма вокрестности заданного объекта, например следующим образомE ( S )  arg max i (U  ( S ))1i  pгде U  ( S ) - дельта-окрестность объекта S.

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

Создатели метода рекомендуютиспользовать для этого порядка 10 объектов.3.10.4. Шаблоны принятия решенийДанный метод коллективных решений использует подход так называемого слиянияалгоритмов распознавания. В рамках данного подхода отдельные методы коллективарассматриваются не как дополняющие друг друга в различных областях пространстваобразов, а как конкурирующие между собой. Мы можем рассматривать результатыработы алгоритмов коллектива как входную информацию некоторого классификаторавторого уровня в промежуточном признаковом пространстве. Пусть имеетсяp94классификаторов и l классов. Тогда выходы классификаторов первого уровня можнопредставить в виде матрицы профиля принятия решений: d1,1 ( S )  d1, j ( S )  d1,l ( S ) DP( S )   d ( S ) d ( S ) d ( S ) p, jp ,l p ,1Здесь di , j ( x) - оценкаi -ого классификатора объектаисходное признаковое пространствоRnnсS заj -ый класс.

Таким образом,признаками, переходит в новоепромежуточное пространство с p  l признаками.Метод шаблонов принятия решений предполагает вычисление шаблонов длякаждого класса. Шаблон для класса K i , который обозначим черезсобой центрi -огоDTi , представляеткласса в промежуточном признаковом пространстве.DTiможнорассматривать как ожидаемое значение профиля DP (S ) для класса K i . Оценка i (S ) закласс K i , получаемая по p классификаторам, определяется как мера сходстваDTiиDP (S ) .

В качестве меры сходства используется евклидова метрика. Если выходыклассификаторов первого уровня рассматривать как оценки апостериорных вероятностейP( K j | S ), j  1,2,..., l , , шаблон принятия решенийоценку математического ожидания переменнойDTiпредставляет собой несмещеннуюDP( x) размерностиp  l при условии,что правильным классом является K i .«Шаблоны принятия решений» считается одним из наилучших методовколлективных решений и обладает устойчивыми характеристиками в большом числеэкспериментов.3.11. Средства контроля качества распознавания.Проблема оценки качества распознавания является весьма важной с прикладнойточки зрения, т.к. при решении реальных задач необходимо иметь объективную оценкувероятности правильного распознавания произвольного объекта.

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

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

В этомслучае для оценки неизвестной величины вероятности успеха по относительной частотеуспехов, необходимо решить следующие уравнения относительно p и pmCk 0kmpk (1  p )mk  1   ,m Ck mгдеkmpk (1  p )mk  1   ,- доля правильно распознанных объектов тестовой выборки, m – объем тестовойвыборки, а - уровень значимости, с которым строится доверительный интервал[ p , p ] .

Последний показывает вероятность того, что искомая вероятность правильногораспознавания произвольного объекта будет лежать внутри доверительного интервала.Чем выше уровень значимости, тем шире получается интервал. Так, при  1 в качестведоверительного интервала будет взята вся область возможных значений вероятности, т.е.отрезок [0,1], поэтому выбор уровня значимости представляет собой компромисс междушириной интервала (т.е. ценностью данной информации) и частотой попадания в негоискомой вероятности (т.е. точностью данной информации).Выписанные выше формулы позволяют получить точные значения границдоверительного интервала в рамках принятой статистической модели. К сожалению,прямой подсчет этих вероятностей наталкивается на большие вычислительные сложности(ошибки округления, большое время работы и т.д.) и при больших объемах выборкипрактически невозможен.

В теории вероятностей получены приближенные выражения дляграниц доверительного интервала при различных условиях. При достаточно больших m и96,существенно отличных от нуля и единицы, можно использовать теорему Муавра-Лапласа, позволяющую приблизить биномиальное распределение нормальным. Дляпоследнегосуществуютявныеформулы,позволяющиеопределитьграницыдоверительного интервала2m z2 (1  )  z p    zm  z2 mm 2m 2m z2 (1  )  z p    zm  z2 mm 2m где z является соответствующей квантилью нормального распределения, которая можетбыть найдена из уравнения  0 ( z ) 2при помощи таблиц.При значениях частоты ошибок близкой к нулю или единице использоватьнормальное приближение нельзя. В этом случае можно воспользоваться малойпредельной теоремой (теорема Пуассона), которая позволяет приблизить биномиальноераспределение пуассоновским.

Характеристики

Список файлов книги