Файл: 2.1.3.3 - Три подхода к определению количества информации.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 170
Скачиваний: 1
Три
подхода
к
определению
количества
информации
(
По
Колмогорову
).
В
своей
классической
работе
“
Три
подхода
к
определению
количества
информации
” [4]
советский
математик
академик
Колмогоров
А
.
Н
.
предложил
три
способа
измерения
количества
информации
:
комбинаторный
,
вероятностный
и
алгоритмический
.
Вероятностный
подход
уже
был
рассмотрен
выше
,
поэтому
ограничимся
только
двумя
остальными
.
1.
Комбинаторный
подход
Пусть
переменное
х
способно
принимать
значения
,
принадлежащие
конечному
множеству
X
,
которое
состоит
из
N
элементов
.
Говорят
,
что
«
энтропия
»
переменного
равна
Н
(
х
)
= log
2
N
Указывая
определенное
значение
х
=
а
переменного
х
,
мы
«
снимаем
»
эту
энтропию
,
сообщая
«
информацию
»
I
= log
2
N
Если
переменные
x
1
,x
2
,…,x
k
способны
независимо
пробегать
множества
,
которые
состоят
соответственно
из
N
1
, N
2
,..., N
k
элементов
,
то
H
(
x
1
,x
2
,…,x
k
) =
H
(
x
1
)+H(x
2
)+…+H(x
k
)
(3.3.1)
Для
передачи
количества
информации
приходится
употреблять
I,
при
I
целом
,
[
I
] + 1,
при
I
дробном
двоичных
знаков
.
Например
,
число
различных
«
слов
»,
состоящих
из
k
нулей
и
единиц
и
одной
двойки
,
равно
2
k
(k + 1).
Поэтому
количество
информации
в
такого
рода
собщении
равно
I = k+log
2
(k+1),
т
.
е
.
для
«
кодирования
»
такого
рода
слов
в
чистой
двоичной
системе
требуется
I’
≈
k +
log
2
k
нулей
и
единиц
.
В
случае
комбинаторного
подхода
к
делу
необходимо
подчеркнуть
его
логическую
независимость
от
каких
бы
то
ни
было
вероятностных
допущений
.
Пусть
,
например
,
нас
занимает
задача
кодирования
сообщений
,
записанных
в
алфавите
,
состоящем
из
s
букв
,
причем
известно
,
что
частоты
P
r
= s
r
/s
(3.3.2)
появления
отдельных
букв
в
сообщении
длины
удовлетворяют
неравенству
h
p
p
r
s
r
r
r
≤
⋅
−
=
∑
=
1
log
χ
(3.3.3)
Легко
подсчитать
,
что
при
больших
п
двоичный
логарифм
числа
сообщений
,
подчиненных
требованию
(3.3.3),
имеет
асимптотическую
оценку
:
Н
=
log
2
N
~
nh.
Поэтому
при
передаче
такого
рода
сообщений
достаточно
употребить
примерно
nh
двоичных
знаков
.
Универсальный
метод
кодирования
,
который
позволит
передавать
любое
достаточно
длинное
сообщение
в
алфавите
из
s
букв
,
употребляя
не
многим
более
чем
nh
двоичных
знаков
,
не
обязан
быть
чрезмерно
сложным
,
в
частности
,
не
обязан
начинаться
с
определения
частот
р
r
для
всего
сообщения
.
Чтобы
понять
это
,
достаточно
заметить
:
разбивая
сообщение
S
на
т
отрезков
S
1
,
S
2
,..., S
m
получим
неравенство
]
[
2
2
1
1
1
χ
χ
χ
χ
m
m
n
n
n
n
+
+
+
≥
−
K
Вполне
естественным
является
чи
c
то
комбинаторный
подход
к
понятию
«
энтропии
речи
»,
если
иметь
в
виду
оценку
«
гибкости
»
речи
-
показателя
разветвленности
возможностей
продолжения
речи
при
данном
словаре
и
данных
правилах
построения
фраз
.
Для
двоичного
логарифма
числа
N
русских
печатных
текстов
,
составленных
из
слов
,
включенных
в
«
Словарь
русского
языка
»
С
.
И
.
Ожегова
и
подчиненных
лишь
требованию
«
грамматической
правильности
»
длины
n
,
выраженной
в
«
числе
знаков
» (
включая
«
пробелы
»),
М
.
Ратнер
и
Н
.
Светлова
получили
оценку
h= (log
2
N)/n =
1,9 ± 0,1.
Это
значительно
больше
,
чем
оценки
сверху
для
«
энтропии
литературных
текстов
»,
получаемые
при
помощи
различных
методов
«
угадывания
продолжений
».
Такое
расхождение
вполне
естественно
,
так
как
литературные
тексты
подчинены
не
только
требованию
«
грамматической
правильности
».
Посмотрим
теперь
,
в
какой
мере
чисто
комбинаторный
подход
позволяет
оценить
«
количество
информации
»,
содержащееся
в
переменном
x
относительно
связанного
с
ним
переменного
у
.
Связь
между
переменными
х
и
у
,
пробегающими
соответственно
множества
Х
и
У
,
заключается
в
том
,
что
не
все
пары
x
,
у
,
принадлежащие
прямому
произведению
Х
х
Y
,
являются
«
возможными
».
По
множеству
возможных
пар
U
определяются
при
любом
а
∈
Х
множества
Y
a
тех
у
,
для
которых
(
а
,y)
∈
U
Естественно
определить
условную
энтропию
равенством
H
(y | a) =
log
2
N
(
Y
a
)
(3.3.4)
1 2 3 4
1 + + + +
2 + - + -
3 - + - -
y
x
(
где
N(Y
x
) -
число
элементов
в
множестве
Y
x
),
а
информацию
в
x
относительно
у
-
формулой
I(
х
:
у
) =
Н
(
у
) -
Н
(
у
|
х
) (3.3.5)
Например
,
в
случае
,
изображенном
в
таблице
имеем
I(
х
=1:
у
) = 0,
I(
х
=2 :
у
)=1,
I(
х
=
3
:
у
)
=
2
.
Понятно
,
что
Н
(
у
|
x
)
и
I(
x
:
у
)
являются
функциями
от
х
(
в
то
время
как
у
входит
в
их
обозначение
в
виде
«
связанного
переменного
»).
Без
труда
вводится
в
чисто
комбинаторной
концепции
представление
о
”
количестве
информации
,
необходимом
для
указания
объект
x
при
заданных
требованиях
к
точности
указания
”.
Очевидно
,
Н
(
х
|
х
) = 0 ,
I
(
х
:
х
)=
Н
(
х
)
(3.3.6)
2.
Алгоритмический
подход
По
существу
,
наиболее
содержательным
является
представление
о
количестве
информации
«
в
чем
-
либо
» (
х
)
и
«
о
чем
-
либо
» (
у
).
Реальные
объекты
,
подлежащие
нашему
изучению
,
очень
(
неограниченно
?)
сложны
,
но
связи
между
двумя
реально
существующими
объектами
исчерпываются
при
более
простом
схематизированном
их
описании
.
Если
географическая
карта
дает
нам
значительную
информацию
об
участке
земной
поверхности
,
то
все
же
микроструктура
бумаги
и
краски
,
нанесенной
на
бумагу
,
никакого
отношения
не
имеет
к
микроструктуре
изображенного
участка
земной
поверхности
.
Практически
нас
интересует
чаще
всего
количество
информации
об
индивидуальном
объекте
,
х
относительно
индивидуального
объекта
у
.
Правда
,
уже
заранее
ясно
,
что
такая
индивидуальная
оценка
количества
информации
может
иметь
разумное
содержание
лишь
в
случаях
достаточно
больших
количеств
информации
.
Не
имеет
,
например
,
смысла
спрашивать
о
количестве
информации
в
последовательности
цифр
0110
относительно
последовательности
1100.
Но
если
мы
возьмем
вполне
конкретную
таблицу
случайных
чисел
обычного
в
статистической
практике
объема
и
выпишем
для
каждой
ее
цифры
цифру
единиц
ее
квадрата
по
схеме
0 1 2 3 4 5 6 7 8 9
0 1 4 9 6 5 6 9 4 1 ,
то
новая
таблица
будет
содержать
примерно
(log
2
10 – 8/10)
n
информации
о
первоначальной
(
п
-
число
цифр
в
столбцах
).
В
соответствии
с
только
что
сказанным
предлагаемое
далее
определение
величины
I
А
(
x
:
у
)
будет
сохранять
некоторую
неопределенность
.
Разные
равноценные
варианты
этого
определения
будут
приводить
к
значениям
,
эквивалентным
лишь
в
смысле
I
I
A
A
2
1
≈
,
т
.
е
.
C
I
I
A
A
A
A
2
1
1
1
|
|
≤
−
где
константа
C
A
A
2
1
зависит
от
положенных
в
основу
двух
вариантов
определения
универсальных
методов
программирования
А
1
и
А
2
.
Будем
рассматривать
«
нумерованную
область
объектов
»,
т
.
е
.
счетное
множество
X = {
x
},
каждому
элементу
которого
поставлена
в
соответствие
в
качестве
«
номера
»
п
(
х
)
конечная
последовательность
нулей
и
единиц
,
начинающаяся
с
единицы
.
Обозначим
через
l
(x)
длину
последовательности
п
(
х
).
Будем
предполагать
,
что
1)
соответствие
между
Х
и
множеством
D
двоичных
последовательностей
описанного
вида
взаимно
однозначно
;
2)
D
⊂
X,
функция
n(x)
на
D
общерекурсивна
,
причем
для
х
∈
D
l(n(x))
≤
l(x) +
С
,
где
С
-
некоторая
константа
;
3)
вместе
с
х
и
у
в
X
входит
упорядоченная
пара
(
х
,
у
),
номер
этой
пары
есть
общерекурсивная
функция
номеров
х
и
у
и
l(
х
,
у
)
≤
С
x
+ l(
у
),
где
С
x
зависит
только
от
х
.
Не
все
эти
требования
существенны
,
но
они
облегчают
изложение
.
Конечный
результат
построения
инвариантен
по
отношению
к
переходу
к
новой
нумерации
п
'(
х
),
обладающей
теми
же
свойствами
и
выражающейся
общерекурсивно
через
старую
,
и
по
отношению
к
включению
системы
X
в
более
обширную
систему
X'
(
в
предположении
,
что
номера
п
'
в
расширенной
системе
для
элементов
первоначальной
системы
общерекурсивно
выражаются
через
первоначальные
номера
п
).
При
всех
этих
преобразованиях
новые
«
сложности
»
и
количества
информации
остаются
эквивалентными
первоначальным
в
смысле
≈
.
“
Относительной
сложностью
”
объекта
у
при
заданном
x
будем
считать
минимальную
длину
l(p)
программы
р
получения
у
из
x.
Сформулированное
так
определение
зависит
от
«
метода
п
po
граммирования
».
Метод
программирования
есть
не
что
иное
,
как
функция
ϕ
(p, x) =
у
,
ставящая
в
соответствие
программе
р
и
объекту
х
объект
у
.
В
соответствии
с
универсально
признанными
в
современной
математической
логике
взглядами
следует
считать
функцию
у
частично
рекурсивной
.
Для
любой
такой
функции
полагаем
=
∞
=
=
y
x
p
что
p
такого
нет
если
p
l
x
y
y
x
p
K
)
,
(
,
,
)
(
min
)
|
(
)
,
(
ϕ
ϕ
ϕ
K
A
(y) = K
A
(y | 1)
можно
считать
просто
«
сложностью
объекта
у
»
и
определить
«
количество
информации
в
х
относительно
у
»
формулой
I
A
(x:y) = K
A
(y) - K
A
(y|x)