ЭФФЕКТИВНОСТЬ БАЙЕСОВСКИХ ПРОЦЕДУР РАСПОЗНАВАНИЯ часть 2

ЭФФЕКТИВНОСТЬ БАЙЕСОВСКИХ ПРОЦЕДУР РАСПОЗНАВАНИЯ часть 1
ЭФФЕКТИВНОСТЬ БАЙЕСОВСКИХ ПРОЦЕДУР РАСПОЗНАВАНИЯ часть 2

Теорема 1. Существует абсолютная константа???, такая, что справедливо неравенство
При условии min (m, m )? 2n оценка сверху погрешности байесовской процедуры задается квадратным 0 1 корнем, в противном случае (для малых выборок) она не превосходит единицы. Из доказательства теоремы вытекает, что абсолютная константа a? 4
2. При выводе этой теоремы не нужно требовать, как в методах минимизации эмпирического риска, равномерную сходимость частот к их вероятностям, поскольку в силу усреднения (3) математическое ожидание и дисперсии частот в формуле (4) совпадает с вероятностями и дисперсиями бернуллиевских случайных величин. Показано, что если в обучающей выборке отсутствует один из классов, т.е. min (m, m )? 0, то любая процедура, в том числе и 0 1 байесовская, работает плохо и ее погрешность строго положительна.
В теории минимизации эмпирического риска [Вапник, 1979] отсутствуют нижние оценки погрешности процедур, поэтому нельзя сделать вывод относительно эффективности предложенного подхода. Для доказательства оптимальности байесовской процедуры распознавания необходимо показать, что никакая другая процедура распознавания не может «работать лучше», чем байесовская процедура. В монографии [Гупал, Сергиенко, 2008] с помощью нетривиальных контрпримеров построены такие «плохие» распределения вероятностней, для которых нижняя оценка погрешности произвольной процедуры распознавания отличается от верхней оценки погрешности байесовской процедуры на абсолютную константу, т.е. байесовская процедура распознавания является субоптимальной.
Теорема 2. Существует абсолютная константа? 0 такая, что справедливо следующее: каковы бы ни были целые числа m, m, m, натуральное число n, и процедура распознавания Q, существует такое распределение вероятностей P из класса C, что выполняется неравенство? (Q, P)? a n? 1 min(m, m )m.(7)0 1 2
Получен также интересный результат относительно того, что байесовская процедура распознавания в булевом случае эквивалентна процедуре распознавания, построенной на использовании отделяющей гиперплоскости.

Байесовская процедура. Дискретный случай
С точки зрения получения оценок погрешностей дискретный случай сложнее, чем булев случай, так как необходимо дополнительно учесть такие параметры, как число классов и количество значений признаков. Построение оценок в дискретном случае – нетривиальная задача, поскольку заранее неизвестно как количество классов, количество признаков и число значений признаков будут представлены в оценке погрешности байесовской процедуры распознавания.
Пусть имеется конечное множество X описаний объектов b? ( x, x ,..., x, f ); здесь n – натуральное 1 2 n число, x ?{0,1,..., g? 1}, j? 1,2,..., n; f ?{0,1,..., h ?1}; g – число значений признаков, h – количество классов (состояний), g? 2, h? 2. В обучающей выборке V количества объектов различных классов заданы; более того, на практике они часто определяются заранее. Поэтому считаем, что выборка V состоит из h? 1 части, V? (V ,V ,...,V ). Пусть m, m ,..., m – целые неотрицательные 0 1 h 0 1 h детерминированные числа. Часть V представляет собой целочисленную матрицу размерностью m? n.
Каждая строка этой матрицы является наблюдаемым значением вектора x? ( x, x ,..., x ), 1 2 n описывающего объект класса i, который выбран из множества X в соответствии с распределением вероятностей P при условии f? i. Последняя часть V представляет собой целочисленный вектор размерностью m. Каждая компонента этого вектора есть наблюдаемое значение целевого признака f, которое выбирается в соответствии с распределением P. Иными словами, вероятность того, что j –я компонента вектора V принимает значение i, равна P( f? i). Все строки матрицы V, i? 0,1,..., h? 1 и компоненты вектора h i V являются независимыми случайными элементами. Считаем? m? ...mh?1 выполнение этого неравенства всегда можно обеспечить путем перенумерации классов объектов.
Байесовская процедура распознавания определяется на основе формулы? (d, i)? k (i)hn?j ?1 k (d, i) i, i ?{0,1,..., h? 1}. (8)
Здесь k (d, i) – количество значений, равных d, j -го признака в j – м столбце матрицы V; k (i) – j j i количество значений целевого признака f, равных i, в векторе V. Значение функции распознавания A(d ) равно минимальному числу s из множества {0,1,..., h? 1} такому, что? (d, s)?? (d, i), i ?{0,1,..., h? 1}. (9)
Приведем оценку сверху погрешности процедуры Q на классе C [Белецкий, 2006].
Теорема 3. Существует абсолютная константа a?? такая, что справедливо неравенство? (Q, C)? a gn? 0 h. (10)
Нижняя оценка сложности класса задач отличается от верхней оценки (10) на абсолютную константу. Таким образом, проблема минимизации среднего риска решена для дискретных объектов с независимыми признаками: построены оптимальные оценки погрешности процедур распознавания в зависимости от входных параметров задачи.
Байесовская процедура распознавания на цепях Маркова
Процедуры распознавания для независимых признаков имеют ограниченную область практических приложений. Большой интерес представляет развитие байесовских процедур распознавания на случай зависимых испытаний, связанных в цепь Маркова. Для того чтобы исследовать эффективность процедур распознавания на цепях Маркова и обосновать применение этих процедур на практике, необходимо изучить поведение оценок переходных вероятностей.
Рассмотрим ситуацию, когда x, x ,..., x образуют последовательность зависимых случайных величин,1 2 n связанных в цепь Маркова. Для модели цепи Маркова первого порядка вероятность цепочки x, x ,..., x задается соотношением 2 n P( x, x ,..., xf )? P( x| f )? P( x| x, f )? ...? P( x | x, f ). (11) 1 2 n 1 2 1 n n?1
Здесь P( x | f ) – начальное распределение вероятностей величины x, P( xk ?1, f ) ,k? 2,..., n, – нестационарные переходные вероятности. Как и в дискретном случае полагаем, что величины? {0,1,..., g? 1} ,j? 1,2,..., n; f ?{0,1,..., h ?1}; g – число значений признаков, h – число классов. Начальное распределение вероятностей P( x? d | f? i) аппроксимируется частотой k (d, i) 1, где 1k (d, i) – количество значений, равных d в первом столбце матрицы V. В байесовской процедуре распознавания используются оценки переходных вероятностей, построенных в виде частот p? ( x? d x? d, i)? k ((dj ?1, d ), i), j? 2,..., n (12) j j j ?1j ?1k (dj ?1, i)
Здесь k ((dj ?1, d ), i) – число пар j ?1 j в строках матрицы V ,k (d j ?1, i) – число значений, равных d в (j–1)-м столбце матрицы V, i ?{0,1,..., h? 1} .j ?1 i
В монографии [Гупал, Сергиенко, 2008] исследовались свойства оценок переходных вероятностей (12). На основе этих результатов получены асимптотические оценки погрешности байесовской процедуры распознавания, которые аналогичны оценкам для независимых признаков.

Индуктивный подход в математике
В монографии [Гупал, Сергиенко, 2008] излагаются основные принципы дедуктивного и индуктивного подходов в математике. Дедуктивно-аксиоматический подход используется в искусственной среде, созданной человеком, где основным требованием является получение точного решения и строгое доказательство теорем. Дедуктивный вывод проводится на основе лишь одного класса – истинных утверждений, ложные утверждения не используются. Отсюда следует неполнота формальных систем.
Индуктивный подход имеет непосредственное отношение к естественным наукам, поскольку объекты и явления природы изучаются на основе измерений и опытных данных. В индуктивном подходе на основе конечного числа наблюдений и исходов предыдущих экспериментов невозможно точно предсказать исход следующего эксперимента. Принципы индуктивных вычислений кардинально отличаются от дедуктивных принципов. Индуктивные процедуры формируют приближенное решение задачи, оценка погрешности которого (как мы видели для байесовских процедур) зависит от входных параметров задачи, причем она стремительно убывает при увеличении объемов обучающих выборок. В математике и образовании индуктивный подход широко не использовался, поскольку до последнего времени он не имел убедительного обоснования.
Дедуктивные вычисления проводятся на основе одного класса – истинных утверждений. Индуктивные процедуры строятся на основе информации, которая представлена в обучающих выборках. Причем, обучающие выборки содержат информацию относительно конечного числа классов наблюдаемых объектов (по крайней мере, не менее двух). Поэтому для них удается построить эффективные и даже оптимальные процедуры распознавания.
В монографии, по сути, впервые проведено обоснование индуктивного подхода с точки зрения построения эффективных процедур распознавания. Сделан вывод о том, что современную математику следует считать объединением дедуктивного и индуктивного подходов. Сфера применения дедуктивного подхода – получение точных решений в задачах малой размерности; область применения индуктивного подхода – решение задач распознавания и прогнозирования большой размерности на основе информации в обучающих выборках. На наш взгляд, эти выводы будут полезны математикам, изучающим проблемы построения оснований современных математических дисциплин.

Заключение

Опыт решения задач в области компьютерного материаловедения (наплавочные материалы, качественные стали, сложные материалы) показал высокую достоверность методов индуктивного вывода. Разработанные методы продемонстрировали свою эффективность при решении сложных биологических задач, в частности, при моделировании процесса селекции сельскохозяйственных культур и прогнозировании белковых соединений. На основе байесовских процедур исследуются диагностические способы определения степени злокачественных опухолей головного мозга. Можно сделать вывод о том, что индуктивные процедуры имеют серьезные перспективы развития, поскольку процессы, протекающие в живой природе, выполняются на основе индуктивных вычислений.
  • +2
  • 3 ноября 2009, 17:27
  • yxom

Комментарии (0)

RSS свернуть / развернуть

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