Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Информация, кодирование и предсказание.

Покупка
Артикул: 682463.01.99
Предлагаемая книга это одновременно учебник и оригинальная монография по теории информации. Две независимые друг от друга части, составляющие книгу, написаны авторами на основе собственных лекций, читающихся в Школе анализа данных Яндекса. Автор первой части, Е. В.Щепин, рассматривает понятия теории информации как базу для решения задач машинного обучения, и преж- де всего задач построения классификатора по эмпирическим данным. Специальное внимание автор уделяет изучению случаев многомерных ограниченных данных, когда прямые методы оценки функций распре- деления вероятностей неприменимы. Обсуждение этих вопросов редко встречается в работах по теории информации. В предлагаемой книге изложение доведено до описания практических методов. Во второй части, написанной Н.К.Верещагиным, исследуются за- дачи о поиске на базе понятия информации по Хартли. В этой части описаны различные применения теории колмогоровской сложности (сложности описаний), даны основы логики знаний и теории ком- муникационной сложности. К теоретическому материалу прилагается множество задач для самостоятельного решения. В обеих частях отводится много места основам классической теории информации Шеннона и её применению к кодированию информации. В первой части это изложение ведется с позиций конструирования ал- горитмов решения проблем, во второй части большое внимание уделено концептуальным аспектам классической теории Шеннона. Книга завершается дополнением, взятым из выдающейся книги М.М. Бонгарда ¾Проблема узнавания¿ (1967), где с позиций теории информации изучается вопрос об оценке степени истинности описания. Эта важная тема, непосредственно примыкающая к рассматриваемым в книге проблемам, служит подтверждением перспективности теории информации для развития новых методов анализа данных.
Верещагин, Н. К. Информация, кодирование и предсказание.: Монография / Верещагин Н.К., Щепин Е.В. - Москва :МЦНМО, 2012. - 236 с.: ISBN 978-5-94057-920-5. - Текст : электронный. - URL: https://znanium.com/catalog/product/958645 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Н.К.Верещагин, Е.В.Щепин

Информация, кодирование
и предсказание

Москва
ФМОП
МЦНМО
2012

УДК 519.72
ББК 32.81
В31

Издание осуществлено при поддержке Фонда
Математического образования и Просвещения

Верещагин Н. К., Щепин Е. В.

В31
Информация, кодирование и предсказание. — М.: ФМОП,
МЦНМО, 2012. — 236 с.
ISBN 978-5-904696-05-4 (ФМОП)
ISBN 978-5-94057-920-5 (МЦНМО)

Предлагаемая книга — это одновременно учебник и оригинальная
монография по теории информации. Две независимые друг от друга
части, составляющие книгу, написаны авторами на основе собственных
лекций, читающихся в Школе анализа данных Яндекса.
Автор первой части, Е. В. Щепин, рассматривает понятия теории
информации как базу для решения задач машинного обучения, и прежде всего — задач построения классификатора по эмпирическим данным.
Специальное внимание автор уделяет изучению случаев многомерных
ограниченных данных, когда прямые методы оценки функций распределения вероятностей неприменимы. Обсуждение этих вопросов редко
встречается в работах по теории информации. В предлагаемой книге
изложение доведено до описания практических методов.
Во второй части, написанной Н. К. Верещагиным, исследуются задачи о поиске на базе понятия информации по Хартли. В этой части
описаны различные применения теории колмогоровской сложности
(сложности описаний), даны основы логики знаний и теории коммуникационной сложности. К теоретическому материалу прилагается
множество задач для самостоятельного решения.
В обеих частях отводится много места основам классической теории
информации Шеннона и её применению к кодированию информации.
В первой части это изложение ведется с позиций конструирования алгоритмов решения проблем, во второй части большое внимание уделено
концептуальным аспектам классической теории Шеннона.
Книга завершается дополнением, взятым из выдающейся книги
М. М. Бонгарда «Проблема узнавания» (1967), где с позиций теории
информации изучается вопрос об оценке степени истинности описания.
Эта важная тема, непосредственно примыкающая к рассматриваемым
в книге проблемам, служит подтверждением перспективности теории
информации для развития новых методов анализа данных.

ББК 32.81

978-5-904696-05-4 (ФМОП)
978-5-94057-920-5 (МЦНМО)
c⃝ Верещагин Н. К., Щепин Е. В., 2012.
c⃝ ООО «Яндекс», 2012.

Оглавление

Предисловие
8

Часть первая

Введение
12

Глава 1. Информационная емкость символа
13
1.1
Двоичные коды
. . . . . . . . . . . . . . . . . . . . . . . .
13
1.2
Оптимальное кодирование . . . . . . . . . . . . . . . . . .
14
1.3
Объединение в блоки . . . . . . . . . . . . . . . . . . . . .
15
1.4
Бит и трит . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1.5
Формула Хартли . . . . . . . . . . . . . . . . . . . . . . . .
17
1.6
Задача сжатия файла . . . . . . . . . . . . . . . . . . . . .
18
1.7
Равночастотное кодирование . . . . . . . . . . . . . . . . .
18
1.8
Задача поиска . . . . . . . . . . . . . . . . . . . . . . . . .
20
1.9
Количество информации по Хартли
. . . . . . . . . . . .
21

Глава 2. Энтропия
22
2.1
Вывод формулы Шеннона из формулы Хартли
. . . . .
22
2.2
Информативность двоичного слова с произвольной декомпозицией . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.3
Вывод формулы Шеннона . . . . . . . . . . . . . . . . . .
23
2.4
Асимптотические оценки . . . . . . . . . . . . . . . . . . .
24
2.5
Сжатие файла с данной декомпозицией . . . . . . . . . .
24
2.6
Вероятностный подход . . . . . . . . . . . . . . . . . . . .
25
2.7
Префиксный код . . . . . . . . . . . . . . . . . . . . . . . .
26
2.8
Алгоритм Хаффмана . . . . . . . . . . . . . . . . . . . . .
27
2.9
Свойства функции энтропии . . . . . . . . . . . . . . . . .
28
2.10 Энтропия как мера неопределенности
. . . . . . . . . . .
29
2.11 Отгадывание слов: вариант 1
. . . . . . . . . . . . . . . .
30
2.12 Отгадывание слов: вариант 2
. . . . . . . . . . . . . . . .
31

ОГЛАВЛЕНИЕ

Глава 3. Информационная зависимость
32
3.1
Энтропия и информация . . . . . . . . . . . . . . . . . . .
32
3.2
Совместное распределение . . . . . . . . . . . . . . . . . .
32
3.3
Условная и взаимная информация
. . . . . . . . . . . . .
33
3.4
Функциональная зависимость . . . . . . . . . . . . . . . .
33
3.5
Критерий независимости . . . . . . . . . . . . . . . . . . .
35
3.6
Относительное кодирование . . . . . . . . . . . . . . . . .
36
3.7
Случайные последовательности . . . . . . . . . . . . . . .
37
3.8
Суперпозиция неопределенностей . . . . . . . . . . . . . .
37

Задачи к главам 2 и 3
40

Глава 4. Защита от шума
51
4.1
Ошибки при передаче информации . . . . . . . . . . . . .
51
4.2
Контроль четности
. . . . . . . . . . . . . . . . . . . . . .
51
4.3
Контрольная сумма . . . . . . . . . . . . . . . . . . . . . .
52
4.4
Локализация ошибки . . . . . . . . . . . . . . . . . . . . .
52
4.5
Построение кода Хэмминга
. . . . . . . . . . . . . . . . .
53
4.6
Декодирование . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.7
Определение фальшивой монеты . . . . . . . . . . . . . .
54
4.8
Дерево алгоритма . . . . . . . . . . . . . . . . . . . . . . .
54

Задачи к главе 4
58

Глава 5. Информативность классификатора
61
5.1
Задача распознавания логов интернет-сессии . . . . . . .
61
5.2
Кривая «точность–покрытие» . . . . . . . . . . . . . . . .
62
5.3
Информативность классификатора . . . . . . . . . . . . .
63
5.4
Неравенство Фано . . . . . . . . . . . . . . . . . . . . . . .
65
5.5
Закон геометрической прогрессии (ЗГП) . . . . . . . . . .
66
5.6
Проверка ЗГП . . . . . . . . . . . . . . . . . . . . . . . . .
67

Задачи к главе 5
69

Глава 6. Проблема недостаточной статистики
71
6.1
Вычисления H1
. . . . . . . . . . . . . . . . . . . . . . . .
71
6.2
Байесовская регуляризация
. . . . . . . . . . . . . . . . .
72
6.3
Вторичная статистика
. . . . . . . . . . . . . . . . . . . .
73
6.4
Типичные вероятности . . . . . . . . . . . . . . . . . . . .
74

ОГЛАВЛЕНИЕ
5

6.5
Третичная статистика
. . . . . . . . . . . . . . . . . . . .
75
6.6
Алгоритм Малыхина . . . . . . . . . . . . . . . . . . . . .
76
6.7
Закон сложения вероятностей . . . . . . . . . . . . . . . .
79

Часть вторая

Введение
81

Глава 7. Информация по Хартли
82
7.1
Игра в 10 вопросов
. . . . . . . . . . . . . . . . . . . . . .
83
7.2
Упорядочивание n чисел: верхняя и нижняя оценки . . .
84
7.3
Упорядочивание 5 различных чисел с помощью 7 сравнений 85
7.4
Поиск фальшивой монетки из 81 за 4 взвешивания
. . .
87
7.5
Поиск фальшивой монетки из 12 за 3 взвешивания
. . .
88
7.6
Цена информации . . . . . . . . . . . . . . . . . . . . . . .
90
7.7
Задачи для самостоятельной работы . . . . . . . . . . . .
91

Глава 8. Логика знания
94
8.1
Карточки с цифрами . . . . . . . . . . . . . . . . . . . . .
95
8.2
Задача о шляпах . . . . . . . . . . . . . . . . . . . . . . . .
97
8.3
Задачи для самостоятельной работы . . . . . . . . . . . .
97

Глава 9. Коммуникационная сложность
101
9.1
Среднее арифметическое и медиана мультимножества . .
102
9.2
Предикат равенства . . . . . . . . . . . . . . . . . . . . . .
103
9.3
Разбиения на одноцветные прямоугольники . . . . . . . .
105
9.4
Метод трудных множеств и метод размера прямоугольников
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106
9.5
Метод ранга матрицы . . . . . . . . . . . . . . . . . . . . .
107
9.6
Вероятностные протоколы . . . . . . . . . . . . . . . . . .
108

Глава 10. Энтропия Шеннона
111
10.1 Определение . . . . . . . . . . . . . . . . . . . . . . . . . .
111
10.2 Коды
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
111
10.3 Коммуникационная сложность в среднем и энтропия
Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . . .
121
10.4 Неравенство Макмиллана
. . . . . . . . . . . . . . . . . .
122
10.5 Энтропия пары случайных величин
. . . . . . . . . . . .
123
10.6 Условная энтропия
. . . . . . . . . . . . . . . . . . . . . .
125

ОГЛАВЛЕНИЕ

10.7 Независимость и энтропия . . . . . . . . . . . . . . . . . .
129
10.8 «Релятивизация» и информационные неравенства . . . .
130
10.9 Задачи для самостоятельной работы . . . . . . . . . . . .
134

Глава 11. Кодирование текстов с учетом частотных закономерностей
136
11.1 Безошибочные кодирования . . . . . . . . . . . . . . . . .
136
11.2 Кодирования с ошибками: теорема Шеннона . . . . . . .
138
11.3 Учёт частот пар, троек и т. д. . . . . . . . . . . . . . . . .
141
11.4 Передача информации при наличии дополнительной информации у принимающей стороны. Теорема Вольфа–
Слепяна . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
152
11.5 Каналы с помехами . . . . . . . . . . . . . . . . . . . . . .
157

Глава 12. Предсказания и игры
165

Глава 13. Колмогоровская сложность
173
13.1 Что такое колмогоровская сложность? . . . . . . . . . . .
173
13.2 Оптимальные способы описания
. . . . . . . . . . . . . .
175
13.3 Сложность и случайность
. . . . . . . . . . . . . . . . . .
178
13.4 Невычислимость KS и парадокс Берри
. . . . . . . . . .
180
13.5 Перечислимость сверху колмогоровской сложности
. . .
181
13.6 Сложность и информация . . . . . . . . . . . . . . . . . .
183
13.7 Сложность пары слов . . . . . . . . . . . . . . . . . . . . .
185
13.8 Условная колмогоровская сложность . . . . . . . . . . . .
189
13.9 Сложность и энтропия . . . . . . . . . . . . . . . . . . . .
199
13.10Применения колмогоровской сложности . . . . . . . . . .
201

Дополнительные задачи
208

Библиография
216

Дополнение: два приложения к книге М. М. Бонгарда «Проблема узнавания»

Приложение 1. Гипотезы, содержащие только истину, и оптимальная гипотеза
217

ОГЛАВЛЕНИЕ
7

Приложение 2. Вопрос об оптимальных решающих алгоритмах при функциях цены трудности, отличных от логарифмической
227

Предисловие к книге Евгения Щепина и Николая Верещагина «Информация, кодирование и предсказание»

Интерес к применению методов теории информации к проблемам распознавания образов, и, более общо, к машинному обучению и анализу
данных, возник очень давно. Норберт Винер в книге «Кибернетика» в
1947г. отмечал важность применения теоретико-информационного подхода для построения распознающей машины. Через 20 лет в 1967 Михаил Бонгард в книге «Проблема узнавания» впервые дал конкретный
пример такого применения. Он показал, что с помощью такого подхода
можно естественным образом количественно анализировать качество
работы обученного распознающего автомата. Двумя годами позже, в
1969 году, примерно эту же проблему количественного анализа качества узнавания и догадки рассмотрел Сатоши Ватанабе в книге «Узнавать и догадываться: количественное изучение вывода и информация».
В последние годы сильно возрос интерес к применению теории информации для исследования задач машинного обучения и анализа данных,
особенно в связи с необходимостью решения этих задач для поиска среди очень больших массивов текстовой информации. Эта область приложений, в свою очередь, породила исследования, расширяющие базовые
представления и предлагающие новые методы во внутренней структуре
теории информации. Теория информации, можно сказать, переживает
сейчас новый период развития. Хорошей иллюстрацией этого является предлагаемая Вам книга Евгения Щепина и Николая Верещагина.
Задуманная как учебное пособие по теории информации, она параллельно с изложением фундаментальных моделей и методов традици
Предисловие
9

онной теории информации ясно обозначает современные тенденции в
ее развитии. Несмотря на небольшой объем, книга содержит модели
и алгоритмы, определяющие новые направления развития теории информации, не представленные в современных публикациях по теории
информации. Читатель, работающий в области анализа данных и желающий использовать в своих исследованиях теорию информации, найдет в этой книге много направляющих идей.
Книга состоит из двух частей. Первая написана Евгением Щепиным, вторая — Николаем Верещагиным. Для полноты изложения современного теоретико-информационного подхода к проблемам анализа
данных, в конце книги в качестве дополнения мы приводим текст раздела из упомянутой выше монографии М. Бонгарда, одного из пионеров
и классиков теории обучения машин.
Обе части книги написаны независимо и их можно читать независимо. Они обьединены тем, что обе нацелены на самые новейшие
приложения теории информации, как сугубо инженерные, так и теоретические (ряд интереснейших задач, как отмечалось, в книге описан
впервые). Изложение в обеих частях почти не требует вузовских знаний, однако требует определенного навыка точного мышления. Однако
и при отсутствии такого навыка изучение материала книги доступно
благодаря его структурной организации, позволяющей «не часто возвращаться назад» при чтении. Авторы обеспечили это подбором очень
интересных вопросов-примеров, и в особенности тем, что многие из
этих примеров даны в форме простых исследовательских задач, решение которых не только способствует лучшему усвоению материала, но
и позволяет приобрести навыки придумывания и решения новых задач.
В первой части большое внимание уделено задачам, непосредственно примыкающим к проблемам машинного обучения, особенно связанным с построением классификатора на основе примеров. В частности, разбираются трудные задачи оценки функции плотности вероятностей в пространствах очень большой размерности по малым выборкам. Я назвал бы эти исследования Е. Щепина основами нового
теоретико-информационного напрвления в построении классификаторов. Уже предложенные процедуры представляют большую практическую ценность и являются источником, вдохновляющим на новые
глубокие теоретические разработки, особенно в деле поиска регуляризаторов для оценки редко наблюдаемых событий.
Одна из особенностей второй части заключается в том, что в ней

Предисловие

в рамках общей схемы теории информации рассматриваются задачи
оценки колмогоровской сложности (в современной зарубежной литературе эти задачи часто объединяют термином «алгоритмическая теория
информации»). В традиционных учебниках по классической теории информации, и в особенности в учебниках, ориентированных на инженеров, эта проблематика не рассматривается, несмотря на то, что сами
задачи активно исследуются (по ним не только имеется большой поток
научных статей, но и публикуются монографии). Поэтому этот относительно маленький раздел второй части представляется важным, особенно для студентов и специалистов, которые впервые изучают теорию
информацию и методы ее применения. Николай Верещагин построил
изложение этого раздела таким образом, что он может служить базой и для чтения других быстро развивающихся направлений в анализе данных, например, для теории машинного обучения, для которой
критическими являются (1) изучение существующих оценок гарантий
качества моделей, построенных на анализе примеров, и (2) разработка
новых оценок. Исследования по решению проблем машинного обучения
на основе моделей колмогоровской сложности — активная область, в
развитии которой Н. Верещагин непосредственно участвует. Поэтому
ему удалось, несмотря на краткость, настолько выразительно описать
это перспективное направление, что впервые изучающий книгу читатель имеет возможность включиться в эти исследования.
В обеих частях, как уже говорилось, подробно разбираются и классические задачи теории информации. Особенно подробно разбираются
задачи представления и кодирования данных для их сжатого хранения и передачи, а также задачи возможности и оценки предсказания в
различных условиях.
В описании классических задач теории информации в текстах первой и второй части имеются дублирования, но они полезны, так как
по-разному построены и дополняют друг друга. Особенно хорошо этот
разный подход к изложению проявляется в подборе задач-упражнений.
Если Е. Щепин старается показать, как сложные процедуры можно
заменить эффективными аппроксимациями и на каких идеях можно
строить эти хорошие аппроксимации, то Н. Верещагин ищет наиболее
понятное, простое и короткое описание точных процедур.
Самое большое "дублирование"имеет место в описании базовых понятий — энтропии и информации и их свойств. В обех частях читатель найдет ясное и полное их обсуждение. И тем не менее, и даже в

Предисловие
11

этих описаниях читатель найдет полезные дополнения. В частности,
интересным представляется, что Н. Верещагин наиболее детально описывает алгебраическую природу необходимых конструкций, а Е. Щепин подчеркивает их вероятностную природу. Н. Верещагин уделяет
большое внимание асимптотическим свойствам методов, а Е. Щепин —
свойствам, которые проявляются на конечных конструкциях. В итоге
читатель получает обьемную картину всего здания теории.
Книга Е. Щепина и Н. Верещагина — не просто техническое пособие
к лекциям. Получилась новая интересная монография по основам и
приложениям теории информации, которая будет полезна и студентам,
и ученым, работающим в различных областях, использующих модели
теории информации.

И. Б. Мучник

август 2011 г.

Часть первая

Введение

Курс нацелен на изучение способов применения теории информации
в практических задачах распознавания образов. Хотя все требуемое
от теории информации по существу является вариацией одной и той
же формулы энтропии, многие из тех, кто изучал теорию информации, часто бывают поставлены в тупик простейшими вопросами, возникающими при ее применении. Например, большинство выпускников
мехаенико-математического факультета МГУ не понимают, как посчитать количество информации, которую сумма цифр трехзначного числа несет об их произведении.
Интуитивное понятие информации, возникающее из обычного языка, хорошо согласуется с определением количества информации, с которым оперирует наука. Развитию интуитивного понятия способствует
решение задач и разбор доказательств основных теорем.
Доказательства теорем в курсе не отличаются строгостью, ведь все
эти теоремы и так хорошо известны, их цель — дать читателю лучше
прочувствовать формулировки и показать в работе основные приемы.
Данный курс лекций может быть использован как для первичного ознакомления с теорией информации, так и для более глубокого ее
изучения. В последних двух лекциях излагаются новые экспериментальные подходы к применению теории информации в распознавании
образов, возникшие у автора при работе в группе разработчиков Яндекса.

Глава 1. Информационная емкость символа

Информация может быть заключена в словах, числах, цветах, звуках и
многом другом, но в конечном счете всякую информацию можно выразить словами любого человеческого языка. Всякий язык имеет свой алфавит — множество символов (букв, цифр, знаков препинания и т. д.).
Последовательности символов представляют слова языка. Вопрос, который мы решим сегодня — сколько информации может нести одно
слово. Единицей измерения информации служит бит: один ответ на
вопрос типа да-нет. Количество битов информации, которое содержит
данное слово, означает, на сколько вопросов типа да-нет может отвечать это слово. Например, информационная емкость символа трехбуквенного алфавита (то есть однобуквенного слова в языке с алфавитом
из трех символов), как мы увидим в дальнейшем, приблизительно равна 1.5849625 битам.

1.1
Двоичные коды

Алфавит языка компьютера состоит из нуля и единицы, а словами являются последовательности нулей и единиц, называемые двоичными
словами. Число элементов двоичного слова называется его длиной. Память компьютера состоит из ячеек, называемых битами, в каждом
из которых записан либо ноль, либо единица. Биты объединяются в
восьмерки, называемые байтами. Таким образом, каждый байт памяти компьютера хранит двоичное слово длины 8. Как следует из нижеприведенной леммы, всего имеется 28 = 256 различных байтовых
слов.

Лемма 1.1. Общее количество двоичных слов длины n равно 2n.

Доказательство. Доказательство проводится индукцией по длине последовательности. Для n = 1 утверждение верно. Пусть уже доказано,

Глава 1. Информационная емкость символа

что число двоичных слов длины n равно 2n. Все двоичные слова длины n + 1 делятся на два типа: начинающиеся с нуля и начинающиеся
с единицы. Число слов каждого типа совпадает с числом слов длины n, то есть в силу предположения индукции равно 2n. Тогда число
последовательностей длины n + 1 равно 2n + 2n = 2n+1.

Количества байтовых слов хватает, чтобы представить все буквы
русского и английского алфавитов, цифры, знаки препинания и все
символы, изображенные на клавиатуре компьютера. Например, стандартным двоичным кодом русской буквы «а» является «10100000», код
цифры «0» — «00110000», пробела — «00100000».
Таким образом, любое предложение русского языка может быть
представлено с помощью двоичных кодов таким образом, что займет
ровно столько байт, сколько символов (включая пробелы и знаки препинания) оно содержало.

1.2
Оптимальное кодирование

Одна из важных практических задач — как поместить в компьютер
как можно больше информации.
Например, мы хотим внести в компьютер данные переписи населения России таким образом, чтобы они занимали как можно меньше
памяти. Рассмотрим для начала только данные о поле граждан. Для
кодирования пола человека достаточно одного бита — например, можно
обозначать женский пол нулем, а мужской единицей. Получается очень
компактный способ кодирования, более того, как мы сейчас докажем,
лучшего способа кодирования пола не существует.
Двоичным кодированием множества M называется отображение c,
ставящее в соответствие каждому элементу множества x ∈ M двоичное
слово c(x) — его код. Кодирование называется инъективным, если коды
различных элементов множества M различны.

Лемма 1.2. Множество M допускает двоичное инъективное кодирование с длиной кода, равной n, в том и только том случае, когда
число элементов множества M не превосходит 2n.

Доказательство. Так как число двоичных слов длины n равно 2n по
лемме 1.1, то теорема сводится к следующему очевидному утверждению: одно множество можно инъективно отобразить в другое в том и