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

От состояний наблюдателя к физике через алгоритмическую вероятность

В теории информации алгоритмической алгоритмическая вероятность , также известная как вероятность Соломонова , представляет собой математический метод присвоения априорной вероятности данному наблюдению. Его изобрел Рэй Соломонов в 1960-х годах. Он используется в теории индуктивного вывода и анализе алгоритмов. В своей общей теории индуктивного вывода Соломонов использует этот метод вместе с правилом Байеса для получения вероятностей предсказания будущих результатов алгоритма.

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

Формально вероятность $P$ не является вероятностью и не поддается вычислению. Это всего лишь «нижняя полувычислимая» и «полумера». Под «полумерой» подразумевается, что $0\leq \sum _{x}P(x)<1$. То есть «вероятность» на самом деле не равна единице, в отличие от реальных вероятностей. Это связано с тем, что некоторые входные данные машины Тьюринга заставляют ее никогда не останавливаться, а это означает, что масса вероятности, присвоенная этим входным данным, теряется. Под «нижней полувычислимостью» подразумевается, что существует машина Тьюринга, которая по входной строке $x$, можно распечатать последовательность $y_{1}<y_{2}<\cdots$ который сходится к $P(x)$ снизу, но не существует такой машины Тьюринга, которая делала бы то же самое сверху.

Обзор

Алгоритмическая вероятность является основным компонентом теории индуктивного вывода Соломонова, теории предсказания, основанной на наблюдениях; его изобрели с целью использовать его для машинного обучения; Учитывая последовательность символов, какой из них будет следующим? Теория Соломонова дает ответ, в определенном смысле оптимальный, хотя и неисчислимый. В отличие, например, Карла Поппера , от неформальной теории индуктивного вывода Соломонова математически строга.

Четырьмя основными источниками вдохновения для алгоритмической вероятности Соломонова были: бритва Оккама , принцип множественных объяснений Эпикура , современная теория вычислений (например, использование универсальной машины Тьюринга) и правило предсказания Байеса.

Бритва Оккама и принцип Эпикура, по сути, являются двумя разными нематематическими аппроксимациями универсального априора .

• Бритва Оккама: среди теорий, согласующихся с наблюдаемыми явлениями, следует выбрать самую простую теорию .
• Принцип множественных объяснений Эпикура: если наблюдениям соответствует более одной теории, сохраняйте все такие теории .

В основе универсального априора лежит абстрактная модель компьютера, такая как универсальная машина Тьюринга. Подойдет любой абстрактный компьютер, если он тьюринг-полный, т. е. каждая вычислимая функция имеет хотя бы одну программу, которая будет вычислять ее применение на абстрактном компьютере.

Абстрактный компьютер используется для придания точного значения фразе «простое объяснение». В используемом формализме объяснения или теории явлений представляют собой компьютерные программы, которые генерируют строки наблюдений при запуске на абстрактном компьютере. Каждой компьютерной программе присвоен вес, соответствующий ее длине. Универсальное распределение вероятностей — это распределение вероятностей для всех возможных выходных строк со случайными входными данными, при котором для каждого конечного выходного префикса q назначается сумма вероятностей программ, которые вычисляют что-то, начинающееся с q . Таким образом, простое объяснение – это короткая компьютерная программа. Сложное объяснение — это длинная компьютерная программа. Простые объяснения более вероятны, поэтому цепочка наблюдений с высокой вероятностью генерируется короткой компьютерной программой или, возможно, любой из большого количества немного более длинных компьютерных программ. Строка наблюдения с низкой вероятностью может быть сгенерирована только с помощью длинной компьютерной программы.

Алгоритмическая вероятность тесно связана с понятием колмогоровской сложности . Введение Колмогоровым сложности было мотивировано теорией информации и проблемами случайности, тогда как Соломонов ввел алгоритмическую сложность по другой причине: индуктивным рассуждениям. Единственная универсальная априорная вероятность, которой можно заменить каждую фактическую априорную вероятность в правиле Байеса, была изобретена Соломоновым с колмогоровской сложностью в качестве побочного продукта. Он предсказывает наиболее вероятное продолжение этого наблюдения и дает представление о том, насколько вероятным будет это продолжение.

Перечислимая мера Соломонова универсальна в определенном смысле, но время вычислений может быть бесконечным. Одним из способов решения этой проблемы является вариант алгоритма поиска Леонида Левина: что ограничивает время, затрачиваемое на вычисление успеха возможных программ, при этом более коротким программам уделяется больше времени. При работе в течение все более и более длительных периодов времени он будет генерировать последовательность аппроксимаций, сходящихся к универсальному распределению вероятностей. Другие методы решения этой проблемы включают ограничение пространства поиска путем включения обучающих последовательностей.

Соломонов доказал, что это распределение машинно-инвариантно в пределах постоянного множителя (так называемая теорема инвариантности ).

Фундаментальные

Теорема инвариантности И. Колмогорова

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

$\forall x\in \{0,1\}^{*},|K_{U}(x)-K_{U'}(x)|\leq {\mathcal {O}}(1)$

где $K_{U}(x)=\min _{p}\{|p|:U(p)=x\}$.

Интерпретация

Минимальное описание $p$ такой, что $U\circ p=x$ служит естественным представлением строки $x$ относительно полного по Тьюрингу языка $U$. Более того, как $x$ невозможно сжать дальше $p$ является несжимаемой и, следовательно, невычислимой струной. Это соответствует представлению ученых о случайности и проясняет причину, по которой колмогоровская сложность не поддается вычислению.

Отсюда следует, что любой фрагмент данных имеет необходимое и достаточное представление в виде случайной строки.

Доказательство

Следующее взято из

Из теории компиляторов известно, что для любых двух Тьюринг-полных языков $U_{1}$ и $U_{2}$, существует компилятор $\Lambda _{1}$ выраженный в $U_{1}$ который переводит программы, выраженные в $U_{2}$ в функционально эквивалентные программы, выраженные в $U_{1}$.

Отсюда следует, что если мы позволим $p$ быть самой короткой программой, которая печатает заданную строку $x$ затем:

$K_{U_{1}}(x)\leq |\Lambda _{1}|+|p|\leq K_{U_{2}}(x)+{\mathcal {O}}(1)$

где $|\Lambda _{1}|={\mathcal {O}}(1)$, и по симметрии получаем противоположное неравенство.

II. Левина

Учитывая, что любой однозначно декодируемый код удовлетворяет неравенству Крафта-Макмиллана, беспрефиксная колмогоровская сложность позволяет нам вывести универсальную Распределение:

$P(x)=\sum _{U\circ P=x}P(U\circ p=x)=\sum _{U\circ p=x}2^{-K_{U}(p)}\leq 1$

где тот факт, что $U$ может имитировать UTM без префиксов, подразумевает, что для двух различных описаний $p$ и $p'$, $p$ не подстрока $p'$ и $p'$ не является подстрокой $p$.

Интерпретация

В Вычислимой Вселенной, учитывая явление с кодированием $x\in \{0,1\}^{*}$ генерируемый физическим процессом, вероятность этого явления четко определена и равна сумме вероятностей различных и независимых причин. Критерий без префиксов — это именно то, что гарантирует причинную независимость.

Доказательство

Это непосредственное следствие неравенства Крафта-Макмиллана .

Неравенство Крафта утверждает, что данная последовательность строк $\{x_{i}\}_{i=1}^{n}$ существует префиксный код с кодовыми словами $\{\sigma _{i}\}_{i=1}^{n}$ где $\forall i,|\sigma _{i}|=k_{i}$ тогда и только тогда, когда:

$\sum _{i=1}^{n}s^{-k_{i}}\leq 1$

где $s$ размер алфавита $S$.

Без ограничения общности предположим, что мы можем упорядочить $k_{i}$ такой, что:

$k_{1}\leq k_{2}\leq ...\leq k_{n}$

Теперь префиксный код существует тогда и только тогда, когда на каждом шаге $j$ можно выбрать хотя бы одно кодовое слово, которое не содержит ни одного из предыдущих $j-1$ кодовые слова в качестве префикса. Из-за существования кодового слова на предыдущем шаге $i<j,s^{k_{j}-k_{i}}$ кодовые слова запрещены, поскольку они содержат $\sigma _{i}$ в качестве префикса. Отсюда следует, что в общем случае префиксный код существует тогда и только тогда, когда:

$\forall j\geq 2,s^{k_{j}}>\sum _{i=1}^{j-1}s^{k_{j}-k_{i}}$

Разделив обе части на $s^{k_{j}}$, мы находим:

$\sum _{i=1}^{n}s^{-k_{i}}\leq 1$

ЯВЛЯЕТСЯ

История

Соломонов изобрел концепцию алгоритмической вероятности и связанную с ней теорему инвариантности примерно в 1960 году. опубликовав отчет об этом: «Предварительный отчет по общей теории индуктивного вывода». Он более полно разъяснил эти идеи в 1964 году в «Формальной теории индуктивного вывода», часть I. и Часть II.

Ключевые люди

• Рэй Соломонов
• Andrey Kolmogorov
• Леонид Левин

См. также

• Теория индуктивного вывода Соломонова
• Алгоритмическая теория информации
• Байесовский вывод
• Индуктивный вывод
• Индуктивная вероятность
• Колмогоровская сложность
• Универсальная машина Тьюринга
• Информационная сложность

Источники

• Ли М. и Витаньи П., Введение в колмогоровскую сложность и ее применение , 3-е издание, Springer Science and Business Media, Нью-Йорк, 2008 г.
• Хаттер, Маркус (2005). Универсальный искусственный интеллект: последовательные решения, основанные на алгоритмической вероятности . Тексты по теоретической информатике. Берлин Гейдельберг: Springer. ISBN  978-3-540-22139-5 .

Дальнейшее чтение

• Ратманнер С. и Хаттер М., « Философский трактат об универсальной индукции » в Entropy 2011, 13, 1076–1136: Очень четкий философский и математический анализ теории индуктивного вывода Соломонова.

Внешние ссылки

• Алгоритмическая вероятность в Scholarpedia
• Публикации Соломонова