колмогоровская сложность для сжатия с потерями

[ded_maxim]

А вот, оказывается, японцы Мурамацу и Каная придумали обобщение сложности по Колмогорову для lossy compression! Определяется для данной последовательности X^n = (X_1,...,X_n) и для заданного уровня потерь D как минимальная длина программы для универсальной машины Тьюринга, с помощью которой можно получить аппроксимацию X^n с точностью D. Если X^n это кусок стационарного эргодического процесса, то эта сложность равна примерно nR(D), где R(D) -- функция зависимости скорости передачи от искажения по Шеннону. (Связь с эпсилон-энтропией etc.) Круто (хотя и совершенно бесполезно с практической точки зрения)!

Comments

[scriptum.livejournal.com]

Почему бесполезно? Зная максимально допустимую потерю информации, можно подобрать секретаршу, измеряя ее череп. См. здесь (http://www.livejournal.com/users/bo_ba/109398.html?nc=4)

[ded-maxim.livejournal.com]

Мерять черепа секретаршам, увы, неполиткорректно. А идея хорошая, да.

[scriptum.livejournal.com]

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

[ded-maxim.livejournal.com]

Живым когнитивным системам, в принципе, пофигу всякая там "информация". Их интересует, что они будут есть на ужин.

Колмогоровская сложность -- штука чрезвычайно полезная и увлекательная. Но с ее помощью оптимальный по Шеннону алгоритм сжатия не построишь.

[scriptum.livejournal.com]

Вы видно очень голодны... А на ужин можно заработать только построив оптимальный по Шенону алгоритм сжатия. Понимаю.

[ded-maxim.livejournal.com]

Спасибо!