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

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

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

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

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

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

Каждому конструктивному объекту соответствует функция ${displaystyle Phi _ {x} (k)}$ натурального числа k - журнала минимальной мощности x-содержащих множеств, допускающих определения сложности не выше k. Если сам элемент x допускает простое определение, то функция ${displaystyle Phi}$ падает до 0 даже при малых k. Без такого определения элемент является «случайным» в отрицательном смысле. Но положительно «вероятностно случайный» только тогда, когда функция ${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 |: xin S, K (S) leq alpha}}

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

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

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

{Displaystyle K (S) + K (x | S) = K (x) + O (1)}

.

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

{displaystyle L (альфа) + альфа = K (x)}

.

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

{Displaystyle K (S) + журнал | 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) + журнал | S | + O (1) leq K (x) + O (1)}

,

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

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

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

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

Главное свойство

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

Вариант MDL

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

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

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

Главное свойство

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

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

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

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

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

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

.

Например, если ${displaystyle P}$ некоторое вычислимое распределение на множестве ${displaystyle S}$ струн длины ${displaystyle n}$ , то каждый ${displaystyle xin 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}}

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

Главное свойство

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

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

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

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

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

Главное свойство

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

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

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

использованная литература

^ ^а ^б ^c Обложка, Томас М .; Томас, Джой А. (1991). Элементы теории информации. Нью-Йорк: Вили. стр.175–178. ISBN 978-0471062592.
^ Тезисы доклада Московского математического общества в УМН. Наук Том 29, Выпуск 4 (178) в Сообщениях Московского Математического Общества стр.155 (в русском издании, на английском языке не переведено)
^ ^а ^б ^c ^d ^е ^ж ^г Верещагин, Н.К .; Витани, П.М. (1 декабря 2004 г.). «Структурные функции Колмогорова и выбор модели». IEEE Transactions по теории информации. 50 (12): 3265–3290. arXiv:cs / 0204037. Дои:10.1109 / TIT.2004.838346.
^ Gacs, P .; Tromp, J.T .; Витани, П.М. (2001). «Алгоритмическая статистика». IEEE Transactions по теории информации. 47 (6): 2443–2463. arXiv:математика / 0006233. Дои:10.1109/18.945257.
^ Риссанен, Йорма (2007). Информация и сложность статистического моделирования (Online-Ausg. Ed.). Нью-Йорк: Спрингер. ISBN 978-0-387-36610-4.
^ А.Х. Шен, Понятие (α, β) -стохастичности по Колмогорову и его свойства, Советская математика. Докл., 28: 1 (1983), 295--299
^ Верещагин, Николай К .; Витани, Пол М. (1 июля 2010 г.). "Искажение скорости и уменьшение шума индивидуальных данных с использованием колмогоровской сложности". IEEE Transactions по теории информации. 56 (7): 3438–3454. arXiv:cs / 0411014. Дои:10.1109 / TIT.2010.2048491.
^ де Рой, Стивен; Витаньи, Пол (1 марта 2012 г.). «Приближение графиков скорости искажения индивидуальных данных: эксперименты по сжатию с потерями и шумоподавлению». Транзакции IEEE на компьютерах. 61 (3): 395–407. arXiv:cs / 0609121. Дои:10.1109 / TC.2011.25.

Литература

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

[CT91-1] а ^б ^c Обложка, Томас М .; Томас, Джой А. (1991). Элементы теории информации. Нью-Йорк: Вили. стр.175–178. ISBN 978-0471062592.

[2] Тезисы доклада Московского математического общества в УМН. Наук Том 29, Выпуск 4 (178) в Сообщениях Московского Математического Общества стр.155 (в русском издании, на английском языке не переведено)

[VV04-3] а ^б ^c ^d ^е ^ж ^г Верещагин, Н.К .; Витани, П.М. (1 декабря 2004 г.). «Структурные функции Колмогорова и выбор модели». IEEE Transactions по теории информации. 50 (12): 3265–3290. arXiv:cs / 0204037. Дои:10.1109 / TIT.2004.838346.

[4] Gacs, P .; Tromp, J.T .; Витани, П.М. (2001). «Алгоритмическая статистика». IEEE Transactions по теории информации. 47 (6): 2443–2463. arXiv:математика / 0006233. Дои:10.1109/18.945257.

[5] Риссанен, Йорма (2007). Информация и сложность статистического моделирования (Online-Ausg. Ed.). Нью-Йорк: Спрингер. ISBN 978-0-387-36610-4.

[6] А.Х. Шен, Понятие (α, β) -стохастичности по Колмогорову и его свойства, Советская математика. Докл., 28: 1 (1983), 295--299

[7] Верещагин, Николай К .; Витани, Пол М. (1 июля 2010 г.). "Искажение скорости и уменьшение шума индивидуальных данных с использованием колмогоровской сложности". IEEE Transactions по теории информации. 56 (7): 3438–3454. arXiv:cs / 0411014. Дои:10.1109 / TIT.2010.2048491.

[8] де Рой, Стивен; Витаньи, Пол (1 марта 2012 г.). «Приближение графиков скорости искажения индивидуальных данных: эксперименты по сжатию с потерями и шумоподавлению». Транзакции IEEE на компьютерах. 61 (3): 395–407. arXiv:cs / 0609121. Дои:10.1109 / TC.2011.25.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]