Сложность байесовской процедуры индуктивного вывода. Дискретный случай

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2006
Hauptverfasser:	Белецкий, Б.А., Вагис, А.А., Васильев, С.В., Гупал, Н.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки и защиты информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/206934
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Сложность байесовской процедуры индуктивного вывода. Дискретный случай / Б.А. Белецкий, А.А. Вагис, С.В. Васильев, Н.А. Гупал // Проблемы управления и информатики. — 2006. — № 6. — С. 55-70. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-206934
record_format	dspace
spelling	irk-123456789-2069342025-09-27T00:20:10Z Сложность байесовской процедуры индуктивного вывода. Дискретный случай Складність байєсівської процедури індуктивного виводу. Дискретний випадок Complexity of Bayesian procedure of inductive inference. Discrete case Белецкий, Б.А. Вагис, А.А. Васильев, С.В. Гупал, Н.А. Методы обработки и защиты информации Досліджено поведінку індуктивних процедур в залежності від змісту навчальної вибірки. Показано, що у випадку, коли в навчальній вибірці відсутня інформація про якийнебудь клас об’єктів або статистична інформація про апріорні імовірності класів, то будьяка процедура працює погано і її похибка строго додатна. Дано оцінку похибки байєсівської процедури розпізнавання в залежності від обсягу навчальної вибірки та інших параметрів. Доведено субоптимальність байєсівського підходу, визначено складність класу задач. Behavior of inductive procedures depending on composition of learning sample is studied. It is shown that if in the learning sample there is no information about some class of objects or statistical information about a priori probabilities of classes then any procedure works badly and its error is strictly positive. The lower bound of an error for the Bayes recognition procedure is obtained depending on a learning sample size and other parameters. It is proved that Bayesian procedure is suboptimal. 2006 Article Сложность байесовской процедуры индуктивного вывода. Дискретный случай / Б.А. Белецкий, А.А. Вагис, С.В. Васильев, Н.А. Гупал // Проблемы управления и информатики. — 2006. — № 6. — С. 55-70. — Бібліогр.: 7 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206934 519.68 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки и защиты информации Методы обработки и защиты информации
spellingShingle	Методы обработки и защиты информации Методы обработки и защиты информации Белецкий, Б.А. Вагис, А.А. Васильев, С.В. Гупал, Н.А. Сложность байесовской процедуры индуктивного вывода. Дискретный случай Проблемы управления и информатики
description	Досліджено поведінку індуктивних процедур в залежності від змісту навчальної вибірки. Показано, що у випадку, коли в навчальній вибірці відсутня інформація про якийнебудь клас об’єктів або статистична інформація про апріорні імовірності класів, то будьяка процедура працює погано і її похибка строго додатна. Дано оцінку похибки байєсівської процедури розпізнавання в залежності від обсягу навчальної вибірки та інших параметрів. Доведено субоптимальність байєсівського підходу, визначено складність класу задач.
format	Article
author	Белецкий, Б.А. Вагис, А.А. Васильев, С.В. Гупал, Н.А.
author_facet	Белецкий, Б.А. Вагис, А.А. Васильев, С.В. Гупал, Н.А.
author_sort	Белецкий, Б.А.
title	Сложность байесовской процедуры индуктивного вывода. Дискретный случай
title_short	Сложность байесовской процедуры индуктивного вывода. Дискретный случай
title_full	Сложность байесовской процедуры индуктивного вывода. Дискретный случай
title_fullStr	Сложность байесовской процедуры индуктивного вывода. Дискретный случай
title_full_unstemmed	Сложность байесовской процедуры индуктивного вывода. Дискретный случай
title_sort	сложность байесовской процедуры индуктивного вывода. дискретный случай
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2006
topic_facet	Методы обработки и защиты информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/206934
citation_txt	Сложность байесовской процедуры индуктивного вывода. Дискретный случай / Б.А. Белецкий, А.А. Вагис, С.В. Васильев, Н.А. Гупал // Проблемы управления и информатики. — 2006. — № 6. — С. 55-70. — Бібліогр.: 7 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT beleckijba složnostʹbajesovskojproceduryinduktivnogovyvodadiskretnyjslučaj AT vagisaa složnostʹbajesovskojproceduryinduktivnogovyvodadiskretnyjslučaj AT vasilʹevsv složnostʹbajesovskojproceduryinduktivnogovyvodadiskretnyjslučaj AT gupalna složnostʹbajesovskojproceduryinduktivnogovyvodadiskretnyjslučaj AT beleckijba skladnístʹbajêsívsʹkoíproceduriínduktivnogovivodudiskretnijvipadok AT vagisaa skladnístʹbajêsívsʹkoíproceduriínduktivnogovivodudiskretnijvipadok AT vasilʹevsv skladnístʹbajêsívsʹkoíproceduriínduktivnogovivodudiskretnijvipadok AT gupalna skladnístʹbajêsívsʹkoíproceduriínduktivnogovivodudiskretnijvipadok AT beleckijba complexityofbayesianprocedureofinductiveinferencediscretecase AT vagisaa complexityofbayesianprocedureofinductiveinferencediscretecase AT vasilʹevsv complexityofbayesianprocedureofinductiveinferencediscretecase AT gupalna complexityofbayesianprocedureofinductiveinferencediscretecase
first_indexed	2025-09-27T01:17:15Z
last_indexed	2025-09-28T01:13:40Z
_version_	1844468274665881600
fulltext	© Б.А. БЕЛЕЦКИЙ, А.А. ВАГИС, С.В. ВАСИЛЬЕВ, Н.А. ГУПАЛ, 2006 Проблемы управления и информатики, 2006, № 6 55 МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ УДК 519.68 Б.А. Белецкий, А.А. Вагис, С.В. Васильев, Н.А. Гупал СЛОЖНОСТЬ БАЙЕСОВСКОЙ ПРОЦЕДУРЫ ИНДУКТИВНОГО ВЫВОДА. ДИСКРЕТНЫЙ СЛУЧАЙ В работе [1] исследована эффективность байесовской процедуры распознава- ния в булевом случае. Был использован подход, развитый в [2] для исследования сложности класса задач и эффективности методов оптимизации. В [1] показано, что нижняя и верхняя оценки погрешности байесовской процедуры распознава- ния совпадают с точностью до абсолютной константы, т.е. в этом смысле байе- совская процедура распознавания субоптимальна и неулучшаема. В настоящей работе результаты, полученные в [1], обобщаются на дискретный случай. Постановка задачи. Пусть имеется конечное множество B описаний объек- тов );,,,,( 21 fxxxb n= здесь n — натуральное число, },1,,1,0{ − gx j  ;,,2,1 nj = };1,,1,0{ − hf  g, 2h — натуральные числа. Предположим, на множестве B задано распределение вероятностей P, которое заранее не извест- но. Из этого множества выделена обучающая выборка V, структура и способ по- лучения которой описаны ниже. Пусть некоторое описание объекта получено из множества B независимо от выборки V в соответствии с распределением P, при- чем известны только значения признаков .,,, 21 nxxx  Требуется по этим значе- ниям и по обучающей выборке V определить значение целевого признака f. Обозначим ).,,,( 21 nxxxx = Величины x, f, V — случайные элементы. Пусть }{ — множество значений, которые принимает следующий элемент . Функция распознавания )(xA принимает значения в множестве }.1,,1,0{ −h Известно, что количество (мощность) таких функций )(xA равно ngh [3]. Счита- ем, что процесс распознавания объекта по его описанию x осуществляется при помощи :)(xA в качестве предполагаемого значения целевого признака f выбира- ется ).(xA Функцию )(xA целесообразно выбирать таким образом, чтобы как можно бóльшим было значение )).(())(,( xAfPdAfdxP d ==== Так как количество функций )(xA конечно, то среди них существует наилучшая функция распознавания )(xA такая, что для всех )(xA справедливо ).()( APAP  Погрешность функции A на распределении P — величина )).(,()(,(),( dAdPdAdPPA d −=   (1) 56 ISSN 0572-2691 В работах по распознаванию [4, 5] рассматривается функция потерь в виде индикаторной функции штрафа, что приводит к усложнению задачи; в [5] рас- смотрен частный случай задачи распознавания с одним признаком. Процедура распознавания Q — однозначная функция, которая определена на множестве }{V допустимых значений обучающей выборки и принимает значения из множества функций распознавания; процедура Q строит функцию A по выбор- ке V, т.е. ).(VQA = Погрешность процедуры Q на распределении P — величина ),(),(),( 1 WVPPAPQ V ==  (2) здесь ),(VQA = )(1 WVP = — вероятность события, состоящего в том, что обу- чающая выборка V принимает значение W. Для независимых признаков вероят- ность )(1 VP полностью определяется вероятностным распределением P. Усред- нение в (2) — ключевой момент в оценивании погрешности индуктивных проце- дур, без него невозможно получить полиномиальные оценки погрешности байесовской процедуры распознавания, как это видно, например, по работам [4, 5]. Структура обучающей выборки. Подмножество объектов из B, у которых целевой признак равен i, называется i-м классом объектов. В обучающей выборке V количества объектов различных классов заданы; более того, на практи- ке они часто определяются заранее. Поэтому считаем, что выборка V состоит из 1+h части, ).,,,( 10 hVVVV = Пусть hmmm ,,, 10  — целые неотрицательные де- терминированные числа; обозначим ).,,,( 10 )( h h mmmm = В случае, когда  im0 и ,hi  часть iV представляет собой целочисленную матрицу размер- ностью .nmi  Каждая строка этой матрицы — наблюдаемое значение вектора ),,,,( 21 nxxxx = описывающего объект класса i, который выбран из множества B в соответствии с распределением вероятностей P при условии .if = Используя матрицу ,iV можно вычислить частоты событий },{ sx j = ,1,,1,0 −= gs  при условии .if = Если ,0  hm то последняя часть hV представляет собой целочисленный вектор размерностью .hm Каждая компонента этого вектора — наблюдаемое зна- чение целевого признака f, которое выбирается в соответствии с распределением P. Иными словами, вероятность того, что j-я компонента вектора hV принимает значение i, равна ).( ifP = Все строки матрицы ,iV ,1,,1,0 −= hi  и компоненты вектора hV — независимые случайные элементы. Индуктивный шаг. Требуется построить такую процедуру индуктивного вывода, которая по измерениям ),,,( 21 nxxxx = любого следующего объекта и обучающей выборке V определяет значение целевого признака f. Сложность класса задач. Класс задач ),,,( )( nmhgCC h — совокупность всевозможных распределений вероятности P на множестве B вместе с величинами .,,, )( nmhg h Множество задач и множество распределений данного класса нахо- дятся во взаимно-однозначном соответствии. Погрешностью процедуры распо- знавания Q на классе C служит число ),,(sup),( PQCQ CP =  а сложностью класса C — ).,(supinf),(inf)( PQCQC CpQQ ==  Проблемы управления и информатики, 2006, № 6 57 Ясно, что 1),()(0  CQC и следует пользоваться такими процедурами распознавания Q, для которых ),( CQ мало отличается от ).(C Пусть ),,,( 21 ndddd = — целочисленный вектор. Считаем, что распреде- ления P из класса C при каждом d удовлетворяют условию ,)(),,,( 1 2211 ifdxPifdxdxdxP jj n j nn =======  =  ,1,,1,0 −= hi  что означает независимость признаков jx для каждого класса объектов. Считаем, что выполняются неравенства ,2 ngh  ,0)( = ifP ,1,,1,0 −= hi  а также, для простоты изложения, неравенство ,1// + hmhmgn где .min 10 i hi mm − = Байесовская индуктивная процедура. Определим случайные величины ),,( id зависящие от d и i как от параметров, при помощи формулы , ),( ),( 1 i j n jh i m idk m k id  = = },1,,1,0{ − hi  (3) где ),( idk j — количество значений, равных ,jd j-го признака в j-м столбце мат- рицы ;iV ik — количество значений целевого признака f, равных i, в векторе .hV Выберем )(dA равным минимальному числу s из множества }1,,1,0{ −h такому, что ),,(),( idsd  }.1,,1,0{ − hi  (4) Процедуру распознавания, определяемую соотношениями (3), (4), обозначим .BQ Заметим, что величины ),(),( 1 0 / jdid h j   − = представляют собой приближенные значения вероятностей ),,,,( 2211 nn dxdxdxifP ====  вычисленных по формуле Байеса, поэтому процедуру распознавания BQ будем называть байе- совской. Дадим оценку сверху погрешности процедуры BQ на классе C. Воспользу- емся следующей теоремой [6]. Теорема 1. Существует абсолютная константа 0a такая, что справедливо неравенство ,,1min),( 0         +   h B m h m gn aCQ где .min 10 i hi mm − = Покажем, что если в обучающей выборке отсутствует один из классов объек- тов, то любая процедура работает плохо и ее погрешность строго положительна. Лемма 1. Если ,00 =m то для любой индуктивной процедуры Q существует такое распределение P, что ее погрешность .0),(  CPQ Доказательство. Рассмотрим два вероятностных распределения (две задачи). Пусть для обоих выполняются соотношения , 2 1 )1()0( −==== fPfP ,2, 2 2 )(  −  == i h ifP 58 ISSN 0572-2691 ,1)0( === ifxP j ,2j ,1,,1,0 −= hi  (5) , 2 1 )1()0( 11 ====== ifxPifxP ,1i .2, 256 1 = h Из этих соотношений видно, что априорные вероятности классов известны. По- этому ответ процедуры Q есть 0 или 1, т.е. }.1,0{)( xA В задаче 0 выберем распределение ,1)00( 1 0 === fxP в задаче 1 – распре- деление ,1)01( 1 1 === fxP т.е. ,1)0( 1 === fsxP s .1,0=s Таким образом, оба эти распределения различаются на классе 0 по первой переменной .1x Ясно, что процедура Q строит ответ 0 или 1 по переменной ,1x а из (5) сле- дует, что ,)( 11 xsxAs = где  — операция сложения по модулю 2. Действи- тельно, ===−== )01()00( 11 xfPxfP ss = =+=== ===−=== = )1()10()0()00( )1()10()0()00( 11 11 fPfxPfPfxP fPfxPfPfxP ss ss =      −       ++      −       = = −       = = = 2 1 2 1 2 1 2 1 1,0 0,1 2 1 1,0 0,1 s s s s       −  − =      −  −− = 2 1 )( )( 2 1 2 1 )( 2 1 1 11 xsxs . Аналогично для 1=d ===−== )1()0( 11 dxfPdxfP ss . 2 1 )1()1()0()0( )( 2 1 11       − =+=== − = fPfdxPfPfdxP ds s Поэтому . 1 если1, 0 если,0 )( 1 ds ds ds dxAs      = = = == Пусть процедура Q такова, что при входе 01 =x выполняется неравенство . 2 1 )0)0(:( 11 ==xAVP (6) Заметим, что по определению вероятности .1)1)0(:()0)0(:( 1111 ===+== xAVPxAVP Погрешность процедуры Q определяется соотношением [6] ),())(()(),( 1 1 0 dxPidAPdPQ i h id ===  − = (7) где ).())(()( dxifPdxdAPdi ==−==  Проблемы управления и информатики, 2006, № 6 59 В случае (6) используем задачу ),1(1 =s для которой == )0( 1 1 xP 4 1 2 1 2 1       += и .1)0( 11 ==  xA Из соотношения (7) получаем, что , 2 1 )00()01()0( 1 1 1 1 10 ==−==== = xfPxfPxi так как , 2 1 2 1 2 1 2 1 2 1 )01( 1 1        +       − === xfP .0)00( 1 1 === xfP Поэтому . 16 1 4 1 2 1 2 1 ),( 1 = PQ Если у процедуры Q при входе 01 =x выполняется условие , 2 1 )1)0(:( 11 ==xAVP то переходим к задаче 0 ),0( =s для которой .0)0( 10 == xA В таком случае , 8 1 )01()00()0( 1 0 1 0 11 ==−==== = xfPxfPxi . 2 1 2 1 2 1 2 1 )0( 1 0       ++−==xP Поэтому из (7) следует . 32 1 2 1 8 1 2 1 ),( 0  PQ Заметим, что переход от одной задачи к другой возможен, поскольку вероят- ность выборки )(1 VP для двух распределений одна и та же. Следующая лемма показывает, что при отсутствии в выборке V вектора hV любая процедура работает неудовлетворительно. Лемма 2. Если ,0=hm то для любой индуктивной процедуры существует такое распределение P, что .0),(  CPQ Доказательство. Рассмотрим два распределения (две задачи). Задача 0: при 0=s . 2, 2 2 ),0,,0( 4 3 )1,0,,0( 4 1 )0,0,,0( 0 1 1 1 P i h ifxxP fxxP fxxP n n n             −  ==== −==== −====    60 ISSN 0572-2691 Задача 1: при 1=s . 2, 2 2 ),0,,0( 4 1 )1,0,,0( 4 3 )0,0,,0( 1 1 1 1 P i h ifxxP fxxP fxxP n n n           −  ==== −==== −====    Из определений вероятностных распределений видно, что на вход процедуры Q поступает всегда один вектор ,0x поэтому ответ процедуры на этот вход тоже один, так как )(xA — однозначная функция. Поскольку в выборке V отсутствует вектор ,hV ответ процедуры Q может указывать на любой из клас- сов, т.е. },1,,1,0{)0()( −== hxAxA  при этом .)0( sAs = Если ответ процедуры Q не совпадает с 1, то рассматривается задача 0, для которой .1)0(0 == xA Тогда ,1, 2 1 )0()01()0( 00 ==−==== ixifPxfPxi ,1))0((0 1 === ixAP .1)0(0 ==xP Поэтому . 2 1 ),( 0  PQ Если ,0)0( A то переходим к задаче 1, для которой .0)0(1 == xA В этом случае выполняются соотношения 0, 2 1 )0()00()0( 11 0 ==−==== ixifPxfPx , ,1))0((1 1 === ixAP .1)0(1 ==xP Следовательно, погрешность процедуры удовлетворяет условию . 2 1 ),( 1  PQ Лемма доказана. Нижняя оценка погрешности. Для оценки снизу сложности класса задач C используется следующая лемма. Лемма 3. Пусть m — натуральное число, s — булева случайная величина, ),,,( 21 muuuu = — троичный случайный вектор, },2,1,0{iu ],1,0( ],2/1,0( ),,0( t }{w — множество всех троичных векторов =w ),,,,( 21 mwww = },2,1,0{iw .,,1 mi = Пусть вероятность P, определенная на декартовом произведении },{}1,0{ w удовлетворяет соотношениям ,2/1)1()0( ==== sPsP ,)()( 1 kswuPkswuP ii m i =====  =       =− =−−− =−+ === ,2 ,1 ,1 ),)1(1( ,0 ),)1(( )( i i k i k ii w wt wt kswuP ;,,2,1 mi = .1,0=k Проблемы управления и информатики, 2006, № 6 61 Тогда существует абсолютная константа 0c такая, что справедливо нера- венство ,/),( 2 0  tmcusI где ),( usI — шенноновское количество информации относительно случайной величины s, содержащееся в случайном элементе u. Доказательство. Очевидно, что =+=−=−= 2/)]1()0([)()(M)(),( suHsuHuHsuHuHusI },2/)]1()0([)({ 111 =+=− suHsuHuHm здесь H обозначает энтропию, M — математическое ожидание. Поскольку ,2/)]1()0([)0( 111 ===+==== sruPsruPuP ),1()1( 1 −==uP то +−−−−−−− )1(log)1())1((log)1()(log(),( 222musI +−−−−++++ ))1((log))1(())((log))((( 22 tttt ++−+−+−−+−−+ ))1((log))1(())((log))(()1(log)1( 222 tttt +−−−−=−−+ ))1((log)1(2)ln(2)(2/)((log)2/))1(log)1( 222 me +++++−−−−= ))/1(ln)()(ln())1((log)1(2)ln(2)(2/)((log 22 ttme +−+−+−−+−−−+ ))/1(ln))(ln(()))1/(1ln())1()(ln(1( tttt +++=−++−+−+ )/1(ln)(()2/)((log))))1/(1(ln))1(((ln)1( 2 ttmett −++−+−−−−+−−+ )))1/(1(ln)1())1/(1(ln)1()/1(ln)( tttttt +−−−−+−−++ ))1/()(1()/)((/))((2/)((log2 ttttttme .)(log2 1 )(log))1/()1( 2 2 22 2           − +  =−+−+ t me tt mett Здесь использовалось неравенство ,)1ln( xx + .0x Лемма доказана. Дадим оценку снизу сложности класса задач. Теорема 2. Существует абсолютная константа 01 a такая, что каковы бы ни были натуральные числа g, h, n, удовлетворяющие неравенствам ,2g ,22 ngh  целые неотрицательные числа hmmm ,,, 10  и процедура распозна- вания Q, существует такое распределение вероятностей P из класса C, что выпол- няется неравенство ,,1min),( 1         +   hm h m gn aPQ где .min 10 i hi mm − = 62 ISSN 0572-2691 Доказательство. Ситуация, когда 0=m или ,0=hm уже рассматривалась. Предположим, погрешность некоторой процедуры Q на классе C не превосходит числа ).1,0( При условии hm докажем неравенство ,/1 hmhc (8) где 01 c — абсолютная константа. Если ,16/1 то неравенство (8 ) справед- ливо. Пусть .16/1 Обозначим 12 − наибольшее нечетное число из множества =I }.1,,1,0{ −= h Тогда ,1 ,22 ngh  .ng Из класса C выделим под- класс задач следующим образом. Пусть ),,,( 110 −= ssss  — булев вектор; t — вещественное число, );2/1,0(t  — вещественное число такое, что     −=− −− = .112,/1 ,112,2/1 h h (9) Выберем  различных векторов ,,,, )1()1()0( −ddd  все компоненты которых принадлежат множеству }.1,,1,0{ −g Если ,2 h то ;ng поэтому суще- ствует n-мерный вектор ,)(d отличный от векторов ,,,, )1()1()0( −ddd  каждая компонента )( jd которого принадлежит множеству }.1,,1,0{ −g Определим на множестве B распределение вероятностей :sP .1,,1,0 ,1)12(,1)2( ),)1(2/1()12( ),)1(2/1()2( )()( −= =+===== −−=+= −+== i ifdxPifdxP tifP tifP isis ss ss i i В случае 112 −− h дополнительно определим ,2/1)1( =−= hfP s .1)1( )( =−==  hfdxP s Нетрудно видеть, что множество распределений веро- ятностей sP при каждом t принадлежит классу C. Считаем, что компоненты js вектора s — независимые случайные величины, принимающие значения 0 и 1 с вероятностями .1,,1,0,2/1)1()0( )0()0( −===== jsPsP jj Это определяет на декартовом произведении }{}{}{}{ sVfx  распределение вероятностей P, которое для всех }{ },{ },{ },{ skVWfixd  удовлетворяет соотношению ===== ),,,( ksWVifdxP );()()()( )0( 1 0 1 jj j kkk ksPWVPifPifdxP ======  − = (10) вероятность kP1 определяется по вероятности kP и способу построения выборки V. Проблемы управления и информатики, 2006, № 6 63 Используя определение (10) вероятности P, для всех }{sk  выводим соот- ношение ),\|()())((),( )()()( 1 0 1 0 ksdxPdksjdAPPQ ii jk i h ji k ====  − = − = (11) где ),(),)(()( )()()()( iii k i jk dxksjfPdxksdAfPd ===−==== ; )( dAk — определенная ранее наилучшая функция распознавания ),(* dA соответствующая распределению .kP Аналогично неравенству (7) ,)()())((),( )()()( 1 1 0 1 0 ii jk ik h ji k dxPdksjdAPPQ ===  − = − = (12) где ),,()(),( )()( VdQdAVQA ii == −=== ))(()( )()()( ii k ki jk dxdAfPd ),( )(ik dxjfP ==− }.1,,1,0{ −= hIj  ={0,1,…,h-1}. Таким образом, }.)(},{:{)(( )( 1 )( 1 jdAVWWPjdAP ikik === (13) Заметим, что = = == == )( )()( )( )0( )0( 1 1 ksP ksPWVP WVP k k = = ===== =  )( )()()()( )0( )0( 1 )( )( ksP ksPWVPjfPjfdxP kkik jd i ).( )( ),( ),,,( ),,,( )( )( )( )( ksWVP ksP ksWVP ksWVjfdxP ksWVjfdxP i Wjd i jd i i === = == = ==== ==== =   Из последнего соотношения и из (13) следует === )(())(( )()( 1 iik dAPjdAP ).ksj == Аналогично булевому случаю [1] ).()( )()()( iki dxPksdxP ==== Из формул , )( )2()2( )2( )( )( )( ik kik ik dxP ifPifdxP dxifP = === === , )( )12()12( )12( )( )( )( ik kik ik dxP ifPifdxP dxifP = +=+== ==+= +===== )2()2()( )()( ifPifdxPdxP ikik =+=+==+ )12()12( )( ifPifdxP ik 64 ISSN 0572-2691 получаем соотношения ,)1(2/1),2( )( tdxksifP ikik −+==== .)1(2/1),12( )( tdxksifP ikik −−===+= Отсюда при условии )( )( i k dAj  следуют неравенства 1,,1,0,2)( )( −= itd i jk (14) и соотношения .1,,1,0,2)( )(* −=+= ikidA i i k (15) Из (11), (14) и (15) получаем .2)2)(( )( 1 0 vtsidAP i i i + − = (16) Пусть q — целое число такое, что 10 − q и выполняются неравенства .1,,1,0 ),2)(()2)(( )()( −=++ isidAPsqdAP i i q q Из соотношений (9) следует     =  = .2,1 ,2,2/1 h h Выбирая в (16) ,4=t если ,2 h и ,2=t если ,2 h= получаем .4/1)2)(( )( − q q sqdAP Обозначим ,2)( )( qdAz q −= тогда . 4 1 )(  qszP (17) Из последнего неравенства и соотношений 2/1)1()0( ==== qq sPsP для шенноновской взаимной информации случайных величин ,qs z следует оценка ,),( 2czsI q  где 02 c — абсолютная константа [2, с. 205]. Величина z пред- ставляет собой однозначную функцию случайных элементов ,,,, 10 hVVV  поэтому ).,(),( 10 hqq VVVsIzsI  Из свойств распределения вероятностей (10) следует ).,(),( 10 hqhq VsIVVVsI = Таким образом, .),( 2cVsI hq  Пусть  hV — случайный вектор размерно- стью ,hm компоненты hi которого определяются по компонентам hi векто- ра hV согласно формулам     + +− = }.12,2{,2 },12,2{,2 qq qqq hi hivhi hi Как следует из определения вероятности ),( fP s компонента qs вектора s задает вероятности только двух значений целевого признака )2(: qfPf s = и ).12( += qfPs Поэтому ).,(),( hqhq VsIVsI = Применяя лемму 3, получаем , 32 ),( 2 0 h mc VsI h hq   а так как ,),( 2cVsI hq  то из последней оценки вытекает неравенство (8). Проблемы управления и информатики, 2006, № 6 65 Теперь докажем соотношения ,1,,1,0,,1min3 −=          hu m gn c u  (18) где 03 c — абсолютная константа. Не ограничивая общности, число g считаем четным: .1,2 =g Пусть S — булева матрица, состоящая из элементов ,ijs ;1,,1,0 −= i ;,,2,1 nj = ).2/1,0(t Доказательство проводим для произвольного }.1,,1,0{ − hu  Пола- гаем без ограничения общности     =  = .0,1 ,1,0 u u w Определим на множестве B распределение вероятностей .SP Пусть };{),()( 1 ddfdxPfdsP jj S n j S ===  = }{d — множество всех векторов ),,,( 21 ndddd = таких, что ),1,,1,0{ − gd j  ;,,2,1 nj = здесь и далее со- отношения выполняются с вероятностью 1. В случае 2=h выбираем == )0( fPS ;2/1)1( === fPS в случае 2h выбираем }.,{\}1,,1,0{, )2(4 1 )(, 8 3 )()( wuhi h ifPwfPufP SSS − − ======  Пусть также для 2h , 2 1 ))1(1()2(       −+=== gn tufixP ijs j S , 4 1 ))1(1(1 2 2 1 ))1(1( 2 )\|12(             −+−=      −+−==+= n t ggn t g ufixP ijij ss j S , 2 1 )2( gn kfixP j S === , 4 1 1 2 2 12 )12(       −=−==+= nggng kfixP j S .,1,,1,0 ;1,,1,0;,,2,1 ukhkinj −=−==  Рассматриваемый способ задания вероятностей корректен. Из приведенных соотношений видно, что компоненты ijs матрицы S определяют вероятностное распределение признаков ,,,1, njx j = только в классе ;uf = в остальных классах они не принимают участия. Кроме того, каждая компонента ijs при фик- сированных i, j задает вероятности двух значений признака ,jx а именно ix j 2= и .12 += ix j Множество распределений вероятностей SP при фиксированном параметре t образуют подкласс задач, принадлежащий классу C. Считаем, что компоненты ijs матрицы S — независимые случайные величи- ны, принимающие значения 0 и 1 с вероятностями ==== )0()0( )0()0( ijij sPsP .,,2,1;1,,1,0,2/1 nji  =−== Таким образом, на декартовом произведении 66 ISSN 0572-2691 }{}{}{}{ SVfx  выбрано распределение вероятностей P, которое для всех }{},{},{},{ SKVWfixd  удовлетворяет соотношению ===== ),,,( KSWVifdxP ),()()()( )0( 1 1 0 1 ijij n ji KKK ksPWVPifPifdxP ======  = − = (19) где ijk — элементы матрицы K. Рассмотрим множество )( jD всех векторов ),,,( 21 ndddd = таких, что ,,,2,1},1,,1,0{ nigdi  =− причем компонента jd — четное число, а все остальные компоненты — нечетные. На основании (19) для всех }{SK  получаем соотношение ;)\|()())(( 1 0)(1 vKSdxPdKSidAP K i h ijDd n j ==== − == (20) здесь );(VQA = ).,(),)(()( * dxKSifPdxKSdAfPd k K i ===−==== В случае, когда 2=h (для удобства используем те же обозначения для целе- вого признака f, что и при ),2h }.1,0{u Согласно определению (19) вероят- ности P для векторов )( jDd ==== ),( dxKSufP = =====+===== ===== = )](),()(),([ )(),( KSwfPwfKSdxPKSufPufKSdxP KSufPufKSdxP , wu u +  = (21) ,),( wu wdxKSwfP +  ==== (22) , 4 )1(1 1))1(1( ,2/)1( ,2/ 1         −+ −−+= −   = n t t iid jjd kn ji i k u . 4 1 1 1−       −= n w n В случае )(,2 jDdh  точно так же , 53 3 8 5 8 3 8 3 ),( wu u wu u dxKSufP +  = +  ==== (23) , 53 3 ),( wu wdxKSwfP +  ==== (24) , )53)(2( 2 ),( wu w h dxKSifP +−  ==== .,,1,,1,0 wiuihi −=  (25) Из соотношений (21)–(25) следует, что если ),(,2),(* jDdhdAi K  то ; 53 },3min{ )( wu wwuK i d + −  (26) кроме этого, },{)(* wudAK  .2h Проблемы управления и информатики, 2006, № 6 67 Если ,0,2/ =jd j k то, учитывая, что ),2/1,0(t получаем =      −−      −−+− −− 11 4 1 1 44 1 1)1( nn wu nn t n t       −−        − −      −+= −−− 111 4 1 1 4)4/11( 1 4 1 1)1( nnn nnn t n t       −−      − − −+      − −− 11 4 1 1 14 )1( 1)1( 4 1 1 nn nn nt t n =      −−      − − −+      − −− 11 4 1 1 )1(4 )1( 1)1( 4 1 1 nn nn nt t n . 8 3 444 1 1 4 1 1)4/1)(1( 4 1 1 2111 ttt t nn tt n nnn          −−      −=      −−−+      −= −−− Здесь используется неравенство .1,1)1( −++ anaa n В этом случае .)(* udAK = Если ,1,2/ =jd j k то аналогично =      −−      +−−− −− 11 4 1 1 44 1 1)1( nn wu nn t n t       −−      − +      −−= −−− 111 4 1 1 4)4/11( 1 4 1 1)1( nnn nnn t n t       −−      − − +−      − −− 11 4 1 1 14 )1(2 1)1( 4 1 1 nn nn nt t n =      −−      − − +−      − −− 11 4 1 1 )1(4 )1(2 1)1( 4 1 1 nn nn nt t n =      −−+−      −= −− 11 4 1 1)2/1)(1( 4 1 1 nn n tt n . 8 3 4 1 1 24 1 1 2224 1 1 121 tt n tt t t n nn −=      −−      −−         −−      −= −− Здесь используется неравенство .0,2/1,21)1( ++ ananaa n В этом случае .)(* wdAK = Из этих соображений, а также из (26) при )(),(* jDddAi K  сле- дует, что     = = = 1, ,0, )( ,2/ ,2/ * jd jd K j j kw ku dA (27) . 53 },8/9min{ )( wu wK i t d +   (28) Таким образом, значение наилучшей функции распознавания на векторе определяется только одним значением компоненты матрицы K (для получения окончательного результата этот момент важен). 68 ISSN 0572-2691 Поскольку ,1, 2 3 1 ,21, 4 3 4 1 1 1 +      −= − wu n w tt n то из (28) следует . 981 9 8 40 2 9 8 9 5 2 3 3 2 3 , 8 9 min )( ttt tt dK i =       + = +        Из последнего неравенства и (20) заключаем, что для всех SK  справедливы соотношения .)())()(( 9 * )(1 === = KSdxPKSdAdAP t k jDd n j (29) Учитывая условие ,2/1t при )( jDd  получаем +======== )(),()( KSufPufKSdxPKSdxP ===+ )(),( KSufPufKSdxP                −+      + −−             −− 11 4 1 1 4 )1( 1)1( 8 32 4 1 nnn nn t t gn . 2 11 1 4 3 8 3 1 2 1 32 321 nn gngn             +      −             Из этой оценки и из (29) для всех }{SK получаем неравенства ,))()(( 2 100 * )(1 =       = KSdAdAP gn t K jDd n j n из которых следует соотношение .))()(( 2 100 * )(1        = dAdAP gn t S jDd n j n (30) Обозначим .)( 1  n j jDD = = Пусть d  — такой вектор, что Dd  и для всех Dd  выполняется неравенство )).()(())()(( ** dAdAPdAdAP SS  Из (30) следует ,))()(( 100 *  dAdAP t S (31) поскольку мощность множества )( jD равна .)2/( ng Если , 800 1  то очевидно ,,1min 800 1          um gn т.е. неравенство (18) справедливо. Пусть .800/1 Выберем .400=t Условие 2/1t выполнено; из (31) получаем . 4 1 ))()(( *  dAdAP S (32) Проблемы управления и информатики, 2006, № 6 69 На основании определения случайной матрицы S и из (27) заключаем, что 2/1))(())(( ** ==== wdAPudAP SS ; из этих соотношений и (32) следует оценка ,))(),(( 4 * cdAdAI S  где 04 c — абсолютная константа. Поскольку )(dA  — однозначная функция от случайного элемента V, то справедливо неравенство );,())(),(( ,2/ * VsIdAdAI qqdS  здесь q таково, что qd  — четное число. Поскольку каждая компонента ijs матри- цы S одинаковым образом определяет вероятности значения признаков j, ,,,1 nj = и выполняются соотношения ,2/1)0()0( )0()0( ==== ijij sPsP то справедлива цепочка равенств ),,(),(),(),( )1( 0101,2/,2/ uuudd sIVsIVsIVsI qqqq ===  где )1( u — первый столбец матрицы .uV Таким образом, .),( 4 )1( 01 csI u  Пусть u — случайный вектор размерно- сти ,um компоненты ui которого определяются по компонентам )1( ui вектора )1( u согласно формулам       = .2,2 ,1, )1( )1()1( u uu ui Из (19) следует ).,(),( 01 )1( 01 uu sIsI = Последнее утверждение справедливо, так как компонента 01s определяет вероятности значений 01 =x и 11 =x и не влияет на остальные значения .1x Используя лемму 3 и соотношение ,400=t получаем , 4 1 4 2 ),( 2 5 2 0014 / gn mc nn t g mcsIc u uu                     где 5c — абсолютная константа. Из этих неравенств вытекают соотноше- ния (18), а из неравенств (8) и (18) — утверждение теоремы. Согласно теоремам 1 и 2 , ),1max( )( ),( 1 0 a a C CQB    т.е. отношение погрешности ),( CQB к сложности )(C класса задач C не пре- восходит абсолютную константу. В этом смысле байесовская процедура распо- знавания BQ субоптимальна. Таким образом, установлена (с точностью до абсо- лютной мультипликативной константы) сложность класса задач C. С начала 90-х годов стремительно развиваются компьютерные методы в био- логии. В 2003 г. завершен международный проект «Геном человека», благодаря которому стала известна нуклеотидная последовательность ДНК человека, состо- ящая примерно из трех миллиардов нуклеотидов четырех типов и содержащая 20–25 тысяч белоккодирующих генов. Анализ огромнейших баз данных биологи- ческой информации привел к использованию новых подходов в информатике — методов компьютерного обучения (machine learning). Основная идея этого подхо- да состоит в том, что вывод и получение результатов непосредственно осуществ- ляются из данных. В настоящее время разработано много методов обучения и распознавания: генетические и энтропийные алгоритмы, методы марковских це- пей со скрытыми параметрами, методы нейронных и байесовских сетей [7]. Ос- 70 ISSN 0572-2691 новной недостаток этих методов состоит в том, что они не имеют строгого мате- матического обоснования, гарантированных оценок решений, сложность задач недостаточно исследована. Байесовские процедуры распознавания имеют полиномиальные гарантиро- ванные оценки погрешности от входа задачи и поэтому оптимальны для незави- симых признаков. Например, исследовалась проблема предсказания вторичных структур белков по их аминокислотным последовательностям. Обучающая вы- борка состояла примерно из 30 тысяч белковых молекул. Расчеты показали, что байесовские процедуры распознавания дают точность предсказания вторичной структуры белка на уровне 90 %. Б.О. Білецький, О.А. Вагіс, С.В. Васильєв, М.А. Гупал СКЛАДНІСТЬ БАЙЄСІВСЬКОЇ ПРОЦЕДУРИ ІНДУКТИВНОГО ВИВОДУ. ДИСКРЕТНИЙ ВИПАДОК Досліджено поведінку індуктивних процедур в залежності від змісту навчаль- ної вибірки. Показано, що у випадку, коли в навчальній вибірці відсутня інфо- рмація про який-небудь клас об’єктів або статистична інформація про апріорні імовірності класів, то будь-яка процедура працює погано і її похибка строго до- датна. Дано оцінку похибки байєсівської процедури розпізнавання в залежності від обсягу навчальної вибірки та інших параметрів. Доведено субоптимальність байєсівського підходу, визначено складність класу задач. B.A. Beletskiy, A.A. Vagis, S.V. Vasilyev, N.A. Gupal COMPLEXITY OF BAYESIAN PROCEDURE OF INDUCTIVE INFERENCE. DISCRETE CASE Behavior of inductive procedures depending on composition of learning sample is studied. It is shown that if in the learning sample there is no information about some class of objects or statistical information about a priori probabilities of classes then any procedure works badly and its error is strictly positive. The lower bound of an er- ror for the Bayes recognition procedure is obtained depending on a learning sample size and other parameters. It is proved that Bayesian procedure is suboptimal. 1. Гупал А.М., Пашко С.В., Сергиенко И.В. Эффективность байесовской процедуры распозна- вания // Кибернетика и системный анализ. — 1995. — № 4. — С. 76–89. 2. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. — М. : Наука, 1979. — 383 с. 3. Хаусдорф Ф. Теория множеств. — М.; Л. : Главная редакция технико-теоретической лите- ратуры, 1937. — 304 с. 4. Алгоритмы и программы восстановления зависимостей / Под ред. В.Н. Вапника. — М. : Наука, 1984. — 816 с. 5. Беликов В.Б., Лбов Г.С. Байесовские оценки качества распознавания по конечному множе- ству событий // Докл. Академии наук. — 2005. — 402, № 1. — С. 10–13. 6. Сергиенко И.В., Гупал А.М., Пашко С.В. О сложности задач распознавания образов // Ки- бернетика и системный анализ. — 1996. — № 4. — С. 70–88. 7. Baldi P., Brunak S. Bioinformatics: machine learning approach. — Cambridge : Massachusets In- stitute of Technology, 2001. — 452 p. Получено 10.08.2006

Сложность байесовской процедуры индуктивного вывода. Дискретный случай

Institution

Ähnliche Einträge