Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода
Important inequality is shown out in relation to Shennon mutual information on two dependent boole casual sizes. It is used for proof of estimations from below in the theory of complication oftasks of optimization and Bayesian pattern recognition procedures.
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2006 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84948 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода / А.А. Вагис // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 10-15. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84948 |
|---|---|
| record_format |
dspace |
| spelling |
Вагис, А.А. 2015-07-17T16:31:54Z 2015-07-17T16:31:54Z 2006 Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода / А.А. Вагис // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 10-15. — Бібліогр.: 4 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84948 519.68 Important inequality is shown out in relation to Shennon mutual information on two dependent boole casual sizes. It is used for proof of estimations from below in the theory of complication oftasks of optimization and Bayesian pattern recognition procedures. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода About one informative inequality in the theory of complication of optimizations tasks and inductive conclusion procedures Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| spellingShingle |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода Вагис, А.А. |
| title_short |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| title_full |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| title_fullStr |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| title_full_unstemmed |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| title_sort |
об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода |
| author |
Вагис, А.А. |
| author_facet |
Вагис, А.А. |
| publishDate |
2006 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
About one informative inequality in the theory of complication of optimizations tasks and inductive conclusion procedures |
| description |
Important inequality is shown out in relation to Shennon mutual information on two dependent boole casual sizes. It is used for proof of estimations from below in the theory of complication oftasks of optimization and Bayesian pattern recognition procedures.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84948 |
| citation_txt |
Об одном информационном неравенстве в теории сложности задач оптимизации и процедур индуктивного вывода / А.А. Вагис // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 10-15. — Бібліогр.: 4 назв. — рос. |
| work_keys_str_mv |
AT vagisaa obodnominformacionnomneravenstvevteoriisložnostizadačoptimizaciiiprocedurinduktivnogovyvoda AT vagisaa aboutoneinformativeinequalityinthetheoryofcomplicationofoptimizationstasksandinductiveconclusionprocedures |
| first_indexed |
2025-11-24T05:55:04Z |
| last_indexed |
2025-11-24T05:55:04Z |
| _version_ |
1850842934016999424 |
| fulltext |
Теорія оптимальних рішень. 2006, № 5 10
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Выведено важное неравенство
относительно шенноновской вза-
имной информации относительно
двух зависимых булевых случайных
величин. Оно используется при до-
казательстве оценок снизу в тео-
рии сложности задач оптими-
зации и байесовской процедуры
распознавания.
А.А. Вагис, 2006
ÓÄÊ 519.68
À.À. ÂÀÃÈÑ
ÎÁ ÎÄÍÎÌ ÈÍÔÎÐÌÀÖÈÎÍÍÎÌ
ÍÅÐÀÂÅÍÑÒÂÅ Â ÒÅÎÐÈÈ
ÑËÎÆÍÎÑÒÈ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ
È ÏÐÎÖÅÄÓÐ ÈÍÄÓÊÒÈÂÍÎÃÎ
ÂÛÂÎÄÀ
Введение. В теории сложности задач опти-
мизации важную роль играет одно неравенс-
тво относительно шенноновской информа-
ции между случайными величинами [1].
Аналогичное неравенство используется при
оценке эффективности байесовской проце-
дуры распознавания или обучения [2].
В работе проводится доказательство такого
неравенства.
Количество информации относительно
двух случайных величин 0z и 1z определя-
ется соотношением
),()()(),( 011001 zzHzHzHzzI −+= , (1)
)(zH – энтропия случайной величины z [3].
Величина ),( 01 zzI обозначает убыль энтро-
пии случайной величины 1z при наблюдении
случайной величины 0z и наоборот, по-
скольку ),(),( 1001 zzIzzI = . Убыль понима-
ют как количество информации о случайной
величине 1z , полученной при наблюдении
случайной величины 0z .
Теорема. Пусть 0z и 1z – булевы случай-
ные величины, для которых выполняются
неравенства
8
3
)( 10 ≤≠ zzP ,
2
1
)1()0( 10 ==== zPzP . (2)
ОБ ОДНОМ ИНФОРМАЦИОННОМ НЕРАВЕНСТВЕ В ТЕОРИИ СЛОЖНОСТИ ЗАДАЧ ОПТИМИЗАЦИИ…
Теорія оптимальних рішень. 2006, № 5 11
Тогда выполняется соотношение
0),( 01 >≥ aCzzI , (3)
где aC – абсолютная константа.
Доказательство. Из соотношений (2) вытекают неравенства
8
5
)( 01 ≥= zzP ,
8
5
)1,1()0,0( 0101 ≥==+== zzPzzP ,
4
5
)11()00( 0101 ≥==+== zzPzzP ,
4
1
)00( 01 ≥== zzP ,
4
1
)11( 01 ≥== zzP , (4)
так как
)0(
)0,0(
)00(
0
01
01
=
==
===
zP
zzP
zzP ,
)1(
)1,1(
)11(
0
01
01
=
==
===
zP
zzP
zzP ,
1)00( 01 ≤== zzP , 1)11( 01 ≤== zzP .
Далее получаем цепочку неравенств
8
1
)0,0( 01 ≥== zzP ,
8
1
)1,1( 01 ≥== zzP ,
8
3
)1,0( 01 ≤== zzP ,
8
3
)0,1( 01 ≤== zzP ,
8
1
)0( 1 ≥=zP ,
8
1
)1( 1 ≥=zP . (5)
Информация ),( 01 zzI выражается следующим образом:
А.А. ВАГИС
Теорія оптимальних рішень. 2006, № 5 12
+==−==−= )1(log)1()0(log)0(1),( 111101 zPzPzPzPzzI
+====+====+ )1,0(log)1,0()0,0(log)0,0( 01010101 zzPzzPzzPzzP
)1,1(log)1,1()0,1(log)0,1( 01010101 ====+====+ zzPzzPzzPzzP . (6)
Здесь log обозначает двоичный логарифм
1)1(log)1()0(log)()( 00000 ===−=−= zPzPzPzPzH .
Обозначим
azP == )0( 1 , bzzP === )0,0( 01 .
Из формулы (6), учитывая соотношения
,
2
1
)0()0,1()0,0( 00101 =====+== zPzzPzzP
,
2
1
)1()1,1()1,0( 00101 =====+== zPzzPzzP
,)0()1,0()0,0( 10101 azPzzPzzP =====+==
1)1()0( 11 ==+= zPzP , (7)
получаем
+−−−−=≡ )1log()1(log1),(),( 01 aaaabazzI ϕ
+
−
−+−−++ bbbababb
2
1
log
2
1
)log()(log
+−
+−+ baba
2
1
log
2
1
.
Из формул (5), (7) заключаем, что величины a и b должны удовлетворять усло-
виям
8
1
≥b ,
8
1
≥a ,
2
1
≤b , ab ≤ ,
16
1
2
+≥
a
b .
Последнее неравенство следует из второго в (4).
Множество допустимих значений a и b лежит в треугольнике ABC (рисунок).
ОБ ОДНОМ ИНФОРМАЦИОННОМ НЕРАВЕНСТВЕ В ТЕОРИИ СЛОЖНОСТИ ЗАДАЧ ОПТИМИЗАЦИИ…
Теорія оптимальних рішень. 2006, № 5 13
0
1/8
2/8
3/8
4/8
5/8
6/8
7/8
1
0 1/8 2/8 3/8 4/8 5/8 6/8 7/8 1
a
b
B C
A
РИСУНОК
Имеем
−−
+−
=
+−+
−−−−=
bba
bab
babbabebab
2
1
)(
2
1
log
2
1
ln
2
1
ln)ln(lnlog),('ϕ .
Так как
2
a
b ≥ , то
0
22
1
2
22
1
2
log),(' =
−
−
≥
aa
aa
babϕ
при каждом a из допустимой области. Поэтому минимальное значение функции
),( baϕ лежит на отрезке AC , т.е. при
16
1
2
+=
a
b .
Таким образом,
+
−−
+
++
+−−−−≥
16
18
log
16
18
16
18
log
16
18
)1log()1(log1),( 01
aaaa
aaaazzI
)(
16
89
log
16
89
16
87
log
16
87
a
aaaa
ϕ≡
−−
+
−−
+ , где
8
7
8
1
≤≤ a .
Отсюда следует, что
А.А. ВАГИС
Теорія оптимальних рішень. 2006, № 5 14
=
−
−
−
−
−
+
+
+−+−=
16
89
ln
2
1
16
87
ln
2
1
16
18
ln
2
1
16
18
ln
2
1
)1ln(lnlog)('
aaaa
aaeaϕ
)89)(87(
)18)(18()1(
log
2
1
2
2
aaa
aaa
−−
−+−
= .
Поэтому, если +→ aa
8
1
, то −∞→)(' aϕ , и если −→
8
7
a , то ∞→)(' aϕ . Таким
образом, )(' aϕ принимает значение 0 только в одной точке
2
1
=a .
Действительно,
)89)(87()164()1( 222
aaaaa −−=−− ,
)6412863()164)(21( 2222
aaaaaa +−=−+− ,
4322432 6412863642128164 aaaaaaaa +−=−++−− ,
2
1
=a .
Значит функция )(aϕ достигает минимума в точке
2
1
:
=
++≥
16
3
log
16
3
16
5
log
16
5
12),( 01 zzI
( ) =−+=
−+= 163log35log5
8
1
13log
16
3
5log
16
5
2
0
2
35
log
8
1
16
35
>
⋅
= , так как 1635 2655368437535 =>=⋅ .
Неравенство (3) доказано.
Результат теоремы показывает, что взаимная шенноновская информация
двух случайных величин 0z и 1z , связанных соотношениями (2), оказывается не
слишком малой, т.е. при проведении опытов над этими случайными величинами
приобретается конечная полезная информация.
ОБ ОДНОМ ИНФОРМАЦИОННОМ НЕРАВЕНСТВЕ В ТЕОРИИ СЛОЖНОСТИ ЗАДАЧ ОПТИМИЗАЦИИ…
Теорія оптимальних рішень. 2006, № 5 15
Выведенное неравенство используется при доказательстве оценок снизу в
теории сложности задач оптимизации и байесовской процедуры распознавания.
О.А. Вагіс
ПРО ОДНУ ІНФОРМАЦІЙНУ НЕРІВНІСТЬ В ТЕОРІЇ СКЛАДНОСТІ ЗАДАЧ
ОПТИМІЗАЦІЇ ТА ПРОЦЕДУР ІНДУКТИВНОГО ВИВОДУ
Виведено важливу нерівність щодо шеноновської взаємної інформації стосовно двох
залежних булевих випадкових величин. Воно використовується при доказі оцінок знизу в
теорії складності задач оптимізації та байєсовської процедури розпізнавання.
A.A. Vagis
ABOUT ONE INFORMATIVE INEQUALITY IN THE THEORY OF COMPLICATION OF
OPTIMIZATIONS TASKS AND INDUCTIVE CONCLUSION PROCEDURES
Important inequality is shown out in relation to Shennon mutual information on two dependent
boole casual sizes. It is used for proof of estimations from below in the theory of complication of
tasks of optimization and Bayesian pattern recognition procedures.
1. Немировский А.С.,Юдин Д.Б. Сложность задач и эффективность методов оптимизации. –
М.: Наука, 1979. – 383 с.
2. Гупал А.М., Пашко С.В., Сергиенко И.В. Эффективность байесовской процедуры классифи-
кации объектов // Кибернетика и системный анализ. – 1995. – №4. – С. 76–89.
3. Гупал А.М., Сергиенко И.В. Оптимальные процедуры распознавания. Обоснование проце-
дур индуктивного вывода // Там же. – 2003. – №1. – С. 33–39.
4. Яглом А.М., Яглом И.М. Вероятность и информация. – М.: Наука, 1973. –512 с.
Получено 14.02.2006
|