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

[ded_maxim]

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

Comments

[ygam.livejournal.com]

А мне кажется полезным. Ведь если сжатие такое lossy, что от данных ничего не остается, то сложность результата равна нулю. Можно построить график потери сложности относительно степени сжатия.

[ded-maxim.livejournal.com]

Такой график уже есть -- это график rate-distortion function R(D). Говоря о практической стороне дела, я имел в виду во-пверых тот факт, что при разработке алгоритмов для сжатия с потерями фиксируют число уровней квантования и минимизируют математическое ожидание функции потерь. Это дело описывается обратной функцией от R(D). А во-вторых, эта штука невычислима, точно так же как и обычная сложность по Колмогорову.

[http://users.livejournal.com/_qwerty/]

Насчет фиксации числа уровней квантизации и минимизации мат.ожидания - не обязательно. См., например, потерьный jpg. Перед беспотерьным кодировщиком (обычно статическим Хаффманом с фискированной стандартом таблицей) вставлено необратимое преобразование для данной предметной области (в данном случае - учитывающее зрительное восприятие).

[ded-maxim.livejournal.com]

JPEG заведомо неоптимален (по Шеннону) -- это обычный transform coder, его не для оптимальности придумывали, а адаптивности ради.

[http://users.livejournal.com/_qwerty/]

Причем тут оптимальность? Нигде в дискуссии выше оптимальность не фигурировала.

[ded-maxim.livejournal.com]

В самом посте фигурирует функция R(D), предписывающая минимальное число уровней квантования при заданном среднем значении функции потерь.

[http://users.livejournal.com/_qwerty/]

Кстати, а каково определение оптимальности для потерьного сжатия? Оно должно быть асимпотически точное и асимпотитически же с нулевой избыточностью?

И чем вам интересны именно оптимальные алгоритмы?

[ded-maxim.livejournal.com]

Нет, потерьное сжатие в общем случае не может быть асимптотически точным. Оптимальность определяется так: пусть k заданное число уровней квантования, пусть P распределение входного сигнала X, и пусть d(x,y) - функция потерь при передаче входного символа x выходным символом y. Тогда оптимальное k-уровневое квантование X определяется как любая функция q, отображающая множество всех X в некоторое подмножество всех Y, состоящее из k выходных символов, так что мат. ожидание d(X,q(X)) по P достигает минимума. Теперь рассмотрим ситуацию когда мы берем n-блоки входных символов и отображаем их в n-блоки выходных символов; берем предел минимума (1/n) E[d(X^n,q(X^n))] по всем квантованиям с k уровнями на входной символ при n стремящемся к бесконечности. Доказано, что этот предел будет равен шенноновской функции D(R) зависимости среднего уровня потерь от скорости передачи, где R = log k это объем квантования в битах на входной символ. Еще можно рассмотреть случай квантования с переменной скоростью передачи.

Оптимальные алгоритмы интересны во-первых с теоретической точки зрения (теория Шеннона гарантирует их существование, но не предлагает эффективного метода их построения), а во-вторых с практической --- в распределенных вычислениях, скажем, могут быть ограничения на пропускную способность каналов между узлами сети.

[http://users.livejournal.com/_qwerty/]

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

[ygam.livejournal.com]

Колмогоровская сложность по определению не имеет отношения ни к чему практическому.

[ded-maxim.livejournal.com]

Ага, ага, скажи это П. Витаньи (http://homepages.cwi.nl/~paulv/). И потом, если универсальная машина Тьюринга не имеет отношения ни к чему практическому, то, выходит, Минский зря столько времени потратил, чтоб придумать наиболее компактную ее форму? И язык программирования Brainfuck (http://www.muppetlabs.com/~breadbox/bf/) существует исключительно для мозгоебства?

[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]

Спасибо!