Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
Н. = H(Xt) = Н(тп/т., т.21т., т.к/т^.
Обозначим
т т~ т
Н(у/х) = - Я. + - Я, + ... + - Я .
' п 1 П 2 п г
П р е д л о ж е н и е 1.11.
I0(y/x) = n(H(y/x)-O( 1)), где 0(1) = (<?
Предложение 1.12. Н(х) минимальна и равна нулю при х = (а, а,..., а).
Максимум достигается, когда mjn = ...
... = mjn = 1/г. При этом Я(дс) = log г.
Доказательство. Рассмотрим логарифмическую функцию In х. Поскольку (1п%)'
= 1/х, то справедливо неравенство
30
lax ^ х - 1, которое означает, что график функции Inх лежит ниже прямой у
= х - 1, являющейся касательной к этой функции в точке х = 1. Равенство
достигается лишь в точке х = 1. Далее,
Щх) = Н
т.
т
Г
-log г =
= V -- log -- V -- log Г = -- log
*-> п т. *-> п *-> п тг
т.
т.
Поскольку
получаем
, п 1 , /г _ 1
log--------- = ~ In-------- < -=¦
mr In 2 mr In 2
I I
mr
i
- 1
Щх) < 1^2 (1 - 1) = 0.
Здесь равенство имеет место только лишь при n/{mr) = 1. Пример
вычисления:
х - (ЪЪсс), у = (аЪаЪ), IQ(y) = 4#(1/2) = 4.
a b
b 1 1 2Щ1/2) = 2
с 1 1 2Я(1/2) = 2
2 2 4
^(у/х) = 4, /0(х:у) = 0.
Следовательно, слова х и у независимы.
Теоремы кодирования в асимптошческой форме принимают следующий вид:
Т еорема 1.5. Если log N < С, то найдется код мощности N, для которого е
-" 0 с ростом п. Если log N> С, то для любого кода мощности N е -*• 1 с
ростом п.
1.14. Прямое произведение слов
Введем в заключение одну важную операцию над словами, которая позволяет
"соединить" два слова произвольной длины. Пусть
х = (av аг...,ат), у = (b', Ьг ..., Ьп).
Прямым произведением х X у слов х, у назовем слово
X X У = (far ?j), (av Ь2), ..., (ar bj, (ay b{), ..., (ащ, bj).
31
Полученное слово имеет длину тп в алфавите, который является декартовым
произведением алфавитов. Удобно представлять слово х х у в виде двух
столбцов:
х' У'
а\
а\ Ь2
а1 "п
а2
а2 "п
ат "п
Если слово х имеет композицию (т1, ..., тг), а слово у-композицию (Ир
..., п^), то слово х' имеет композицию (т^п, ... ..., тп), а слово у'-
композицию (п^т, ..., п^т). Поэтому
Н{х'),= Н(т^п/тп, ...,тп! тп) = Н(т{/т, ...,mj т) = Н{х),
Н(у') = Н(у).
Очевидно,
х х у = х' (r) У,
Н(х х у) = Я
(т^п1 т^п2
тп
т п.
г к
тп
тп
= -2
m л. т.п.
-^log-^ = m/г тп
--2
т. /г.
- ^ log - т п т
т.
I
ч т. п.
т. п. п.
2 Ти ~п log ~п -*-1 т п п
ч
ч
п.
т.
= 2 ям + я^ = Я(Л)+ я^)-/ <¦
Таким образом, доказано следующее утверждение:
Т еорема 1.6. Прямое произведение слов х х у, где т-длина слова х, а п-
длина слова у, может быть представлено в виде
х х у = х' (r) У,
где х' и у'-взаимно независимые слова длины тп, причем Н(х') = Я(х), Н(У)
= Н(у), Н(х X у) = Н(х) + Н(у).
2. РАСПОЗНАВАНИЕ ОБРАЗОВ
2.1. Постановка задачи распознавания.
Информационная матрица
Задача распознавания образов была впервые сформулирована Ф. Розенблаттом
[14] при попытке моделирования операций, выполняемых живыми организмами в
процессе коммуникации и восприятия окружающего мира. Им же была построена
обучающая машина, известная под названием "Персептрон", позволившая
решить задачу автоматической классификации.
Каждый объект описывается набором признаков XI, Х2, ... ...,Хп. Различают
качественные признаки, когда Х = = {1, 2, ..., т}, и количественные,
когда X-любое действительное число. В последнем случае признак с помощью
квантования можно превратить в качественный, т. е, представить в виде
конечной последовательности целых чисел (слова). (Эта процедура описана в
пункте 1.8.) Кроме того, каждый контрольный объект должен быть отнесен к
тому или иному классу из некоторого множества Y = {\, 2, ..., к].
Информация о признаках представляется в виде таблицы (информационной
матрицы), которая используется для обучения.
Пример 2.1.
Номер объекта Признаки Класс
XI Х2 ХЗ Х4 Х5 Х6 XI Х8 У
1 2 2 2 1 2 2 1 1 1
2 2 2 2 2 2 2 1 1 1
3 2 2 2 1 1 2 1 1 1
4 2 1 1 2 1 1 1 2 2
5 2 1 1 2 1 1 2 1 2
б 1 1 1 2 1 1 1 2 2
7 2 1 1 1 2 2 1 2 3
8 2 1 1 2 2 2 г 3
9 2 2 1 1 2 2 1 2 3
В обучающую выборку, как правило, включается только часть контрольных
объектов, остальные используются для настройки (т. е. для достижения
наиболее четкого распознавания). Например, из 60 объектов 40 можно
использовать для обучения
2 В.Д.Гоппа
33
и 20 для контроля при настройке, причем последние 20 объектов должны
равномерно распределяться между классами.
Пример 2.2 (прогнозирование запаса руды для месторождения [17]).
Значения признаков:
Y-запас руды (У = 1о У > 1 млн тонн, У=0"У< 1 млн тонн),
*1-приуроченность к горизонтам слюдистых сланцев,
Х2-приуроченность к горизонтам амфиболитов,
ХЗ-близость к контакту со слюдистыми сланцами,
Х4-близость к контакту с амфиболитами,
Х5-присутствие тел амфиболитов,
Хб-обилие даек,
XI-пиритизация,
X 8-пропилитизация,
Х9-ожелезнение,
.Х10-аргиллитизация,
.XII-наличие вторичных ореолов свинца и цинка,
.XI2-развитие складок.
Информационная матрица
*1 Х2 ХЗ Х4 Х5 *6 XI *8 Х9 *10 XII Х12
У
1 0 1 0 0 0 1 1 1 0 0 1 1
1
2 0 1 1 1 0 0 1 0 1 0 1 1
1
