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

Date: 2005-12-17 01:50 am (UTC)
From: [identity profile] ygam.livejournal.com
А мне кажется полезным. Ведь если сжатие такое lossy, что от данных ничего не остается, то сложность результата равна нулю. Можно построить график потери сложности относительно степени сжатия.

Date: 2005-12-17 01:54 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Такой график уже есть -- это график rate-distortion function R(D). Говоря о практической стороне дела, я имел в виду во-пверых тот факт, что при разработке алгоритмов для сжатия с потерями фиксируют число уровней квантования и минимизируют математическое ожидание функции потерь. Это дело описывается обратной функцией от R(D). А во-вторых, эта штука невычислима, точно так же как и обычная сложность по Колмогорову.

Date: 2005-12-17 02:12 am (UTC)
From: [identity profile] http://users.livejournal.com/_qwerty/
Насчет фиксации числа уровней квантизации и минимизации мат.ожидания - не обязательно. См., например, потерьный jpg. Перед беспотерьным кодировщиком (обычно статическим Хаффманом с фискированной стандартом таблицей) вставлено необратимое преобразование для данной предметной области (в данном случае - учитывающее зрительное восприятие).

Date: 2005-12-17 02:14 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
JPEG заведомо неоптимален (по Шеннону) -- это обычный transform coder, его не для оптимальности придумывали, а адаптивности ради.

Date: 2005-12-17 07:50 am (UTC)
From: [identity profile] http://users.livejournal.com/_qwerty/
Причем тут оптимальность? Нигде в дискуссии выше оптимальность не фигурировала.

Date: 2005-12-17 03:46 pm (UTC)
From: [identity profile] ded-maxim.livejournal.com
В самом посте фигурирует функция R(D), предписывающая минимальное число уровней квантования при заданном среднем значении функции потерь.

Date: 2005-12-18 07:33 am (UTC)
From: [identity profile] http://users.livejournal.com/_qwerty/
Кстати, а каково определение оптимальности для потерьного сжатия? Оно должно быть асимпотически точное и асимпотитически же с нулевой избыточностью?

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

Date: 2005-12-20 04:06 pm (UTC)
From: [identity profile] 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 это объем квантования в битах на входной символ. Еще можно рассмотреть случай квантования с переменной скоростью передачи.

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

Date: 2005-12-20 05:43 pm (UTC)
From: [identity profile] http://users.livejournal.com/_qwerty/
А действительно ли хороша эта модель на практике? Насколько я помню свои упражнения, по крайней мере для беспотерьного сжатия асимптотическая оптимальность алгоритма вовсе не означает, что он выдающимся образом жмет конечные последовательности. А модель источника и кодирования можно и другую построить.

Date: 2005-12-17 02:20 am (UTC)
From: [identity profile] ygam.livejournal.com
Колмогоровская сложность по определению не имеет отношения ни к чему практическому.

Date: 2005-12-17 02:35 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Ага, ага, скажи это П. Витаньи (http://homepages.cwi.nl/~paulv/). И потом, если универсальная машина Тьюринга не имеет отношения ни к чему практическому, то, выходит, Минский зря столько времени потратил, чтоб придумать наиболее компактную ее форму? И язык программирования Brainfuck (http://www.muppetlabs.com/~breadbox/bf/) существует исключительно для мозгоебства?

Date: 2005-12-17 01:51 am (UTC)
From: [identity profile] scriptum.livejournal.com
Почему бесполезно? Зная максимально допустимую потерю информации, можно подобрать секретаршу, измеряя ее череп. См. здесь (http://www.livejournal.com/users/bo_ba/109398.html?nc=4)

Date: 2005-12-17 02:36 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Мерять черепа секретаршам, увы, неполиткорректно. А идея хорошая, да.

Date: 2005-12-17 02:59 am (UTC)
From: [identity profile] scriptum.livejournal.com
Но вообще-то, я имел в виду, что живые когнитивные системы всегда теряют информацию, поэтому, понимание этой взаимосвязи с Колмогоровской сложностью - штука полезная.

Date: 2005-12-17 03:35 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Живым когнитивным системам, в принципе, пофигу всякая там "информация". Их интересует, что они будут есть на ужин.

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

Date: 2005-12-17 04:12 am (UTC)
From: [identity profile] scriptum.livejournal.com
Вы видно очень голодны... А на ужин можно заработать только построив оптимальный по Шенону алгоритм сжатия. Понимаю.

Date: 2005-12-17 04:16 am (UTC)
From: [identity profile] ded-maxim.livejournal.com
Спасибо!

Profile

ded_maxim: (Default)
ded_maxim

December 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
2425 2627282930
31      

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 28th, 2025 03:43 am
Powered by Dreamwidth Studios