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

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

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

Колмогоровское определение

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

Структурная функция была первоначально предложена Колмогоровым в 1973 году на симпозиуме по советской теории информации в Таллинне, но эти результаты не были опубликованы с. 182. Но результаты были объявлены в 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})}$

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

Современное определение

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

${\ 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 \ альфа = К (х) + с}$${\ displaystyle \ alpha}$${\ Displaystyle \ альфа + ч_ {х} (\ альфа) = К (х) + О (1)}$${\ displaystyle S}$${\ Displaystyle ч_ {х} (\ альфа)}$${\ displaystyle x}$${\ Displaystyle К (S) \ leq \ альфа}$${\ displaystyle S}$${\ displaystyle x}$

${\ Displaystyle К (S) + \ журнал | S | = К (х) + О (1)}$ .

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

${\ Displaystyle К (Икс) \ Leq К (Икс, S) + О (1) \ Leq К (S) + К (х | S) + О (1) \ Leq К (S) + \ журнал | S | + O (1) \ leq K (x) + O (1)}$ ,

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

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

Подбор недвижимости

В рамках ограничений, что график спускается вниз под углом не менее 45 градусов, что он начинается в n и заканчивается примерно в , каждый граф (до аддитивного члена в аргументе и значении) реализуется структурной функцией некоторых данных x и наоборот. Если график первым попадает в диагональ, аргумент (сложность) - это минимально достаточная статистика. Невозможно определить это место. Видеть. ${\ Displaystyle К (х)}$${\ Displaystyle О (\ журнал п)}$

Основное свойство

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

Вариант 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) = \ журнал | S | + К (S) \ GEQ К (х) -O (1)}$

Основное свойство

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

Применение в статистике

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

Вероятностные модели

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

${\ Displaystyle - \ журнал P (x) = \ журнал | S | + O (\ журнал п)}$ .

Например, если есть некоторое вычислимое распределение на множестве строк длины , то каждая имеет вероятность . Структурная функция Колмогорова принимает вид ${\ displaystyle P}$${\ displaystyle S}$${\ displaystyle n}$${\ displaystyle x \ in S}$${\ Displaystyle Р (х) = \ ехр (О (\ журнал п)) / | S | = п ^ {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 \ журнал | \ {х \} | = 0}$${\ Displaystyle \ альфа = К (х) + с}$${\ displaystyle x}$${\ Displaystyle \ {х \}}$${\ Displaystyle К (х)}$${\ displaystyle x}$${\ displaystyle h '_ {x} (\ alpha) = h_ {x} (\ alpha) + O (\ log n)}$${\ displaystyle \ alpha}$${\ Displaystyle ч '_ {х} (\ альфа)}$

Основное свойство

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

Вариант 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) = - \ журнал P (x) + K (P) \ geq K (x) -O (1)}$

Основное свойство

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

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

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

Рекомендации

Литература

• Обложка, ТМ; П. Гакс; Р. М. Грей (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 .