Разница между «информацией» и «полезной информацией» в алгоритмической теории информации

16

Согласно Википедии :

Неформально, с точки зрения алгоритмической теории информации, информационное содержание строки эквивалентно длине кратчайшего возможного автономного представления этой строки.

Каково аналогичное неофициальное строгое определение «полезной информации»? Почему «полезная информация» не воспринимается как более естественная или более фундаментальная концепция; на первый взгляд кажется, что чисто случайная строка по определению должна содержать нулевую информацию, поэтому я пытаюсь осознать тот факт, что по стандартному определению она содержит максимальную информацию.

user1247
источник
2
Добро пожаловать! Обратите внимание, что вы можете изменить свое имя пользователя на то, что люди с большей вероятностью узнают, когда вы станете постоянным посетителем.
Рафаэль

Ответы:

12

Центральным понятием здесь является колмогоровская сложность , а точнее сжимаемость . Чтобы получить интуитивное ощущение сжимаемости, рассмотрим две строки и B B , где B =ABBB . ПозволятьB={0,1}

1010A=1010 1010 1010 и1010 1010

0110B=1011 0110 1001 .0111 1001

Обратите внимание, что . Как мы можем определить, сколько информации имеет A или B ? Если мы думаем о классической теории информации, то в общем случае передача строки длиной n занимает в среднем n битов. Однако мы не можем сказать, сколько бит нам нужно для передачи определенной строки длины n .|A|=|B|=16ABnnn

Почему информативность случайной строки не равна нулю?

При ближайшем рассмотрении мы видим, что на самом деле . Тем не менее, это гораздо труднее сказать , если B имеет какие - либо очевидные закономерности в его структуре, по крайней мере, кажется , и чувствует себя более случайным , чем A . Поскольку мы можем найти шаблон в A , мы можем легко сжать A и представить его менее чем 16 битами. Точно так же, так как не легко обнаружить какие-либо шаблоны в B , мы не можем сжать их так сильно. Поэтому мы можем сказать, что BA=108BAAA16BB имеет больше информации , чем . Более того, случайная строка длиной nAnимеет максимальную информацию, так как мы не можем сжать ее, и, следовательно, представить ее менее чем с битами.n

Чем же полезна информация?

Для полезной информации , да, есть определение с помощью машины Тьюринга . Полезная информация в х B * являетсяTxB

minT { l(T)+C(x|T):T{T0,T1,...}},

где обозначает длину самоограничивающего кодирования для машины Тьюринга T . Обозначения обычно таковы, что C ( x ) обозначает колмогоровскую сложность x, а C ( x | y ) условную колмогоровскую сложность x при y .l(T)TC(x)xC(x|y)xy

Здесь воплощает количество полезной информации, содержащейся в x . Мы могли бы спросить, какую такую T выбрать среди тех, которые удовлетворяют требованию. Задача состоит в том, чтобы разбить кратчайшую программу x на части x = p q st p, представляющую соответствующий TTxTxx=pqpT . Это на самом деле та самая идея, которая породила минимальную длину описания (MDL) .

Юхо
источник
4

Это может быть потому, что «полезное» трудно определить. Скажем, у нас есть высоко структурированное, насыщенное информацией сообщение которое может быть сжато не более чем в α раз на сообщение y . Интуитивно понятно, что x и y содержат одинаковое количество полезной информации; действительно, они содержат одинаковое количество информации в соответствии с обычным определением. Теперь представьте префикс г из х такой же длины , как и у ; он должен содержать не более полезной информации, чем x , следовательно, не более y . Тем не менее, у является более "случайным", чем г , так как гxαyxyzxyxyyzzможет быть сжат, а нет. Поэтому, если мы попытаемся связать «полезную» информацию со сжимаемостью, мы можем столкнуться со следующим парадоксом: префикс сообщения может иметь более «полезную» информацию, чем все сообщение, что, по-видимому, противоречие.y

Patrick87
источник
Это может быть трудно определить, и может случиться так, что он не может тривиально полагаться на сжимаемость, как это делает «информация», но это кажется более важным определением! В данном случае «информация» представляется псевдонимом «колмогоровской сложности», а не серьезной попыткой определить информацию в обычном смысле, который в других контекстах должен, по определению, быть полезным! Это активная область исследований? Есть ли предложенные определения?
user1247
@ user1247 Почему вы видите колмогоровская сложность как не серьезно?
Юхо
@mrm Я считаю это очень серьезным и интересным понятием, но мне неудобно называть это понятие «информация». Что означает, что абсолютно случайная строка содержит информацию? «Полезная информация» кажется более применимой и интересной, когда речь идет о обсуждении информации (где «полезность» подразумевается) в реальном мире, например, в философских или квантово-механических дискуссиях о передаче или получении информации.
user1247
1
@ user1247 Возможно, интересный способ интерпретации моего ответа заключается в следующем: информация полезна или бесполезна только в зависимости от того, как она интерпретируется. Для фиксированной интерпретации одно сообщение может содержать больше или меньше полезной информации, чем другое. Любая теория полезной информации, по моему мнению, должна принимать во внимание такие интерпретации (обычные меры, такие как энтропия, тоже делают это, хотя и неявно).
Patrick87
@ Patrick87 Я абсолютно согласен, что любая хорошая теория "полезной информации" должна учитывать механизм дешифрования. Вот что делает это интересной проблемой! Если вы отправите мне битовую строку, и в принципе я не могу ее расшифровать, то она должна быть определена так, чтобы не содержать полезной информации.
user1247
4

С менее формальной точки зрения, я думаю, что это может помочь, если вы отсоединяетесь от слова «случайный», поскольку вы правы в том, что набор действительно случайных битов не хранит никакой информации в практическом смысле. (Если я зашифрую набор имен и отправлю вам зашифрованные значения, они могут иметь очень высокую колмогоровскую сложность, но это не поможет вам выяснить имена).

Но подумай об этом таким образом. Если вы видите веб-сайт на иностранном языке (скажем, на шведском, если вы не говорите на нем), он будет выглядеть более или менее случайным. Там будет какой-то порядок слов, но не много. Однако, если вы посмотрите на веб-страницу с текстом, который выглядит следующим образом: 123456123456123456123456 ... и т. Д., Вы сможете быстрее понять его. Если вы не говорите по-шведски, вы, вероятно, сможете получить от этого гораздо больше, даже если на шведской веб-странице будет указан эквивалент «первых шести чисел, повторенных последовательно». Веб-сайты содержат ту же информацию, но один выглядит случайным для вас. Что касается количества места, то, которое вы понимаете, гораздо менее эффективно, чем шведская веб-страница, даже если она хранит ту же информацию. Вы можете не найти эту информацию «полезной», потому что она

Понятие «информация» должно быть универсальным, поэтому то, что для вас выглядит случайным - и потому бесполезным - битом, может хранить много информации для кого-то другого. Предполагается, что мера информации является внутренним свойством строки и не может зависеть от того, что для вас имеет и не имеет смысла, а также от того, что вы можете и не можете интерпретировать.

Еще один (более технический) момент, который может помочь, заключается в том, что я здесь немного неискренен. Как Юхо указывает, информация являетсяопределяется относительно того, кто его интерпретирует. Вы можете найти шведскую веб-страницу совершенно бесполезной в качестве средства для получения информации, но кто-то, кто говорит по-шведски, может найти для нее много информации. Определение действительно отражает это. Однако из математики мы можем узнать, что разница между самой короткой (самой информативной для космоса) веб-страницей, предназначенной для сообщения вам этого веб-сайта, и самой короткой веб-страницей, которая может сообщить ее тому, кто говорит по-шведски, может отличаться только аддитивной константой. Почему? Потому что для вас, как для говорящих не на шведском языке, самый короткий способ сохранить страницу, которую вы можете понять, это «первые шесть целых чисел, повторенных последовательно». Это может быть немного дольше, чем шведские.

(Most efficient representation of information in English)(Most efficient representation in Swedish)+(Length of Swedish-English dictionary)
, Это немного выходит за рамки вашего первоначального вопроса, но я пытаюсь подчеркнуть, что не имеет большого значения, кто читает информацию. Случайно выглядящая шведская веб-страница была не «полезна» для вас, но «полезна» для кого-то другого, и вы только в постоянном объеме информации не можете ее использовать самостоятельно.
Samm
источник