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

О совершенно другой «структурной функции», также введенной Колмогоровым, см. Колмогоровскую теорию турбулентности .

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

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

Определение Колмогорова

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

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

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

— Колмогоров , заявление цитировано выше.

Современное

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

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

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

Алгоритмическая достаточная статистика

Мы определяем набор $S$ содержащий $x$ такой, что

$K(S)+K(x|S)=K(x)+O(1)$.

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

$L(\alpha )+\alpha =K(x)$.

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

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

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

$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)$,

Structure functions $h_{x}(\alpha ),\beta _{x}(\alpha ),\lambda _{x}(\alpha )$ and minimal sufficient statistic.

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

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

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

В тех условиях, что график опускается под углом не менее 45 градусов, он начинается в n и заканчивается примерно в $K(x)$, каждый граф (с точностью до $O(\log n)$ аддитивный член по аргументу и значению) реализуется структурной функцией некоторых данных x и наоборот. Там, где график первым достигает диагонали, аргументом (сложностью) является минимально достаточная статистика. Определить это место невозможно. Видеть.

Основная собственность

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

Вариант MDL

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

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

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

Основная собственность

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

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

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

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

Для каждого вычислимого распределения вероятностей $P$ это можно доказать что

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

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

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

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

Основная собственность

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

Вариант MDL

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

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

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

Основная собственность

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

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

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

Литература

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