Структурная функция Колмогорова

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

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

Определение Колмогорова [ править ]

Колмогоров (слева) рассказывает о структурной функции (см. Рисунок на доске) в ( Таллинн , 1973).

Структурная функция была первоначально предложена Колмогоровым в 1973 г. на симпозиуме по советской теории информации в Таллинне, но эти результаты не были опубликованы ^[1] с. 182. Но результаты были объявлены в ^[2] в 1974 г., единственной письменной записи самого Колмогорова. Одно из его последних научных высказываний (перевод с русского оригинала Л.А. Левина):

Каждому конструктивному объекту соответствует функция натурального числа k - журнал минимальной мощности x-содержащих множеств, которые позволяют определять сложность не выше k. Если сам элемент x допускает простое определение, то функция падает до 0 даже при малых k. Без такого определения элемент является «случайным» в отрицательном смысле. Но это положительно «вероятностно случайное» только тогда, когда функция, приняв значение относительно небольшого , затем изменяется примерно как .${\ displaystyle \ Phi _ {x} (k)}$${\ displaystyle \ Phi}$${\ displaystyle \ Phi}$${\ displaystyle \ Phi _ {0}}$${\ displaystyle k = k_ {0}}$${\ Displaystyle \ Phi (k) = \ Phi _ {0} - (k-k_ {0})}$

-  Колмогоров , цитируемое выше объявление.

Современное определение [ править ]

Это обсуждается в Кавер и Томас. ^[1] Он подробно изучен у Верещагина и Витани ^[3], где также разрешены основные свойства. Структурную функцию Колмогорова можно записать как

${\ displaystyle h_ {x} (\ alpha) = \ min _ {S} \ {\ log | S |: x \ in S, K (S) \ leq \ alpha \}}$

где двоичная строка длины с , где находится рассматриваемая модель (набор строк н-Length) для , является Колмогоров сложностью из и является неотрицательным целым числом , ограничивающее сложности предполагается «с. Очевидно, что эта функция возрастает и достигает для где есть необходимое количество бит для изменения INTO и является Колмогоров сложностью из .${\ displaystyle x}$${\ displaystyle n}$${\ displaystyle x \ in S}$${\ displaystyle S}$${\ displaystyle x}$${\ Displaystyle K (S)}$${\ displaystyle S}$${\ displaystyle \ alpha}$${\ displaystyle S}$${\ Displaystyle \ журнал | \ {х \} | = 0}$${\ Displaystyle \ альфа = К (х) + с}$${\ displaystyle c}$${\ displaystyle x}$${\ Displaystyle \ {х \}}$${\ Displaystyle К (х)}$${\ displaystyle x}$

Алгоритмическая достаточная статистика [ править ]

Определим набор, содержащий такие, что ${\ displaystyle S}$${\ displaystyle x}$

${\ Displaystyle К (S) + К (х | S) = К (х) + О (1)}$.

Функция никогда не убывает больше, чем фиксированная независимая константа ниже диагонали, называемой линией достаточности L, определяемой формулой ${\ Displaystyle ч_ {х} (\ альфа)}$

${\ Displaystyle L (\ альфа) + \ альфа = К (х)}$.

К нему с точностью до постоянного расстояния приближается график для определенных аргументов (например, для ). Для них у нас есть и связанная модель (свидетель для ) называется оптимальным набором для , и поэтому ее описание битов является алгоритмически достаточной статистикой . Мы условно пишем "алгоритмическую" для "колмогоровской сложности". Основными свойствами алгоритмической достаточной статистики являются следующие: если - алгоритмическая достаточная статистика для , то ${\displaystyle h_{x}}$${\displaystyle \alpha =K(x)+c}$${\displaystyle \alpha }$${\displaystyle \alpha +h_{x}(\alpha )=K(x)+O(1)}$${\displaystyle S}$${\displaystyle h_{x}(\alpha )}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle x}$

${\displaystyle K(S)+\log |S|=K(x)+O(1)}$.

Таким образом, описание использования модели из двух частей и в качестве кода преобразования данных в модель с индексом в перечислении в битах столь же кратко, как и кратчайший код из одной части в битах. Это легко увидеть следующим образом: ${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle \log |S|}$${\displaystyle x}$${\displaystyle K(x)}$

${\displaystyle K(x)\leq K(x,S)+O(1)\leq K(S)+K(x|S)+O(1)\leq K(S)+\log |S|+O(1)\leq K(x)+O(1)}$,

используя простые неравенства и свойство достаточности, мы находим это . (Например, если мы можем описать само-delimitingly (вы можете определить его конец) в битах.) Таким образом, дефект случайности из в является постоянной, что означает , что является типичным (случайным образом ) элемент S. Тем не менее, существует могут быть модели, содержащие недостаточную статистику. Алгоритмическая достаточная статистика для имеет дополнительное свойство, помимо того , что модель наилучших, что и , следовательно , от сложности Колмогорова симметрии информации (информация о в${\displaystyle K(x|S)=\log |S|+O(1)}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle \log |S|+O(1)}$ ${\displaystyle \log |S|-K(x|S)}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle S}$${\displaystyle x}$${\displaystyle K(x,S)=K(x)+O(1)}$${\displaystyle x}$${\displaystyle S}$примерно такая же, как информация о в x), которую мы имеем : достаточная алгоритмическая статистика - это модель наилучшего соответствия, которая почти полностью определяется . ( является самой короткой программой для .) Алгоритмическая достаточная статистика, связанная с наименьшей таковой , называется алгоритмической минимальной достаточной статистикой .${\displaystyle S}$${\displaystyle K(S|x^{*})=O(1)}$${\displaystyle S}$${\displaystyle x}$${\displaystyle x^{*}}$${\displaystyle x}$${\displaystyle \alpha }$

Что касается рисунка: структурная функция MDL объясняется ниже. Структурная функция согласия является наименьшим недостатком случайности (см. Выше) любой модели для такой, что . Эта структурная функция дает степень согласия модели (содержащей x) для строки x. Когда он низкий, модель подходит хорошо, а когда высокий - модель не подходит. Если для некоторых, то существует типичная модель для такой, что и является типичной (случайной) для S. То есть, это наиболее подходящая модель для x. Подробнее см. ^[1] и особенно ^[3] и. ^[4]${\displaystyle \lambda _{x}(\alpha )}$${\displaystyle \beta _{x}(\alpha )}$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle S}$${\displaystyle \beta _{x}(\alpha )=0}$${\displaystyle \alpha }$${\displaystyle S\ni x}$${\displaystyle x}$${\displaystyle K(S)\leq \alpha }$${\displaystyle x}$${\displaystyle S}$

Выбор свойств [ править ]

В рамках ограничений, согласно которым график спускается вниз под углом не менее 45 градусов, что он начинается в n и заканчивается примерно в , каждый граф (с точностью до аддитивного члена в аргументе и значении) реализуется структурной функцией некоторых данных x и наоборот. Если график первым попадает в диагональ, аргумент (сложность) - это минимально достаточная статистика. Невозможно определить это место. Видеть. ^[3]${\displaystyle K(x)}$${\displaystyle O(\log n)}$

Основное свойство [ править ]

Доказано, что на каждом уровне сложности структурная функция позволяет выбрать лучшую модель для отдельной строки x в пределах полосы с уверенностью, а не с большой вероятностью. ^[3]${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle O(\log n)}$

Вариант MDL [ править ]

Функция минимальной длины описания (MDL): длина минимального двухчастного кода для x, состоящего из стоимости модели K (S) и длины индекса x в S, в модельном классе множеств данного максимального Колмогорова. сложность , сложность S, ограниченная сверху , задается функцией MDL или ограниченной оценкой MDL:${\displaystyle \alpha }$${\displaystyle \alpha }$

${\displaystyle \lambda _{x}(\alpha )=\min _{S}\{\Lambda (S):S\ni x,\;K(S)\leq \alpha \},}$

где - полная длина двухчастного кода x с помощью модели S.${\displaystyle \Lambda (S)=\log |S|+K(S)\geq K(x)-O(1)}$

Основное свойство [ править ]

Доказано, что на каждом уровне сложности структурная функция позволяет выбрать лучшую модель S для отдельной строки x в пределах полосы с уверенностью, а не с большой вероятностью. ^[3]${\displaystyle \alpha }$${\displaystyle O(\log n)}$

Применение в статистике [ править ]

Разработанная выше математика была взята за основу MDL его изобретателем Йормой Риссаненом . ^[5]

Вероятностные модели [ править ]

Для любого вычислимого распределения вероятностей можно доказать ^[6], что${\displaystyle P}$

${\displaystyle -\log P(x)=\log |S|+O(\log n)}$.

Например, если есть некоторое вычислимое распределение на множестве строк длины , то каждая из них имеет вероятность . Структурная функция Колмогорова принимает вид ${\displaystyle P}$${\displaystyle S}$${\displaystyle n}$${\displaystyle x\in S}$${\displaystyle P(x)=\exp(O(\log n))/|S|=n^{O(1)}/|S|}$

${\displaystyle h'_{x}(\alpha )=\min _{P}\{-\log P(x):P(x)>0,K(P)\leq \alpha \}}$

где х представляет собой бинарная строка длины п с , где находится рассматриваемая модель (вычислима вероятность -длина строк) для , является Колмогоров сложностью из и представляет собой целое значение , ограничивающее сложность предусматриваемых -х гг. Очевидно, что эта функция не возрастает и достигает для где с необходимым количеством бит к изменению во и является Колмогоров сложностью из . Тогда . Для каждого уровня сложности функция является версией максимального правдоподобия (ML) по Колмогорову .${\displaystyle -\log P(x)>0}$${\displaystyle P}$${\displaystyle n}$${\displaystyle x}$${\displaystyle K(P)}$${\displaystyle P}$${\displaystyle \alpha }$${\displaystyle P}$${\displaystyle \log |\{x\}|=0}$${\displaystyle \alpha =K(x)+c}$${\displaystyle x}$${\displaystyle \{x\}}$${\displaystyle K(x)}$${\displaystyle x}$${\displaystyle h'_{x}(\alpha )=h_{x}(\alpha )+O(\log n)}$${\displaystyle \alpha }$${\displaystyle h'_{x}(\alpha )}$

Основное свойство [ править ]

Доказано, что на каждом уровне сложности структурная функция позволяет выбрать лучшую модель для отдельной строки в пределах полосы с уверенностью, а не с большой вероятностью. ^[3]${\displaystyle \alpha }$${\displaystyle S}$${\displaystyle x}$${\displaystyle O(\log n)}$

Вариант MDL и вероятностные модели [ править ]

Функция MDL: длина минимального двухчастного кода для x, состоящего из стоимости модели K (P) и длины в модельном классе вычислимых вероятностно-массовых функций заданной максимальной колмогоровской сложности сложности P, ограниченной сверху by , задается функцией MDL или оценкой MDL с ограничениями:${\displaystyle -\log P(x)}$${\displaystyle \alpha }$${\displaystyle \alpha }$

${\displaystyle \lambda '_{x}(\alpha )=\min _{P}\{\Lambda (P):P(x)>0,\;K(P)\leq \alpha \},}$

где - общая длина двухчастного кода x с помощью модели P.${\displaystyle \Lambda (P)=-\log P(x)+K(P)\geq K(x)-O(1)}$

Основное свойство [ править ]

Доказано, что на каждом уровне сложности функция MDL позволяет выбрать лучшую модель P для отдельной строки x в пределах полосы с определенностью, а не с большой вероятностью. ^[3]${\displaystyle \alpha }$${\displaystyle O(\log n)}$

Расширение для оценки искажений и шумоподавления [ править ]

Оказывается, что подход может быть расширен до теории искажения скорости отдельных конечных последовательностей и шумоподавления отдельных конечных последовательностей ^[7] с использованием сложности Колмогорова. Эксперименты с использованием реальных компрессорных программ прошли успешно. ^[8] Здесь предполагается, что для естественных данных сложность Колмогорова недалеко от длины сжатой версии с использованием хорошего компрессора.

Ссылки [ править ]

Литература [ править ]

• Обложка, ТМ; П. Гач; Р. М. Грей (1989). «Вклад Колмогорова в теорию информации и алгоритмическую сложность» . Анналы вероятности . 17 (3): 840–865. DOI : 10.1214 / AOP / 1176991250 . JSTOR  2244387 .
• Колмогоров, АН; Успенский В.А. (1 января 1987 г.). «Алгоритмы и случайность» . Теория вероятностей и ее приложения . 32 (3): 389–412. DOI : 10.1137 / 1132060 .
• Ли, М., Витани, PMB (2008). Введение в сложность Колмогорова и ее приложения (3-е изд.). Нью-Йорк: Спрингер. ISBN 978-0387339986., Особенно стр. 401–431 о структурной функции Колмогорова и стр. 613–629 об искажении скорости и шумоподавлении отдельных последовательностей.
• Шен А. (1 апреля 1999 г.). «Дискуссия о колмогоровской сложности и статистическом анализе». Компьютерный журнал . 42 (4): 340–342. DOI : 10.1093 / comjnl / 42.4.340 .
• Вьюгин, В.В. (1987). «О дефекте случайности конечного объекта относительно мер с заданными границами сложности» . Теория вероятностей и ее приложения . 32 (3): 508–512. DOI : 10.1137 / 1132071 .
• Вьюгин В.В. (1 апреля 1999 г.). «Алгоритмическая сложность и стохастические свойства конечных двоичных последовательностей». Компьютерный журнал . 42 (4): 294–317. DOI : 10.1093 / comjnl / 42.4.294 .