Проблема универсального предсказания

Как строить модель универсального интеллектуального агента, если не дано μ(q)? Нужно вспомнить, что под μ(q) подразумевается не истинное, а некое лучшее (с учетом имеющейся априорной информации) распределение. Но в реальности это распределение построить крайне проблематично. Какое распределение стоит принять при минимуме априорной информации?

Пусть это распределение ξ. Для соблюдения универсальности необходимо, чтобы для любой программы q было верно ξ(q)≠0, то есть ни одна модель не отвергается априори. Максимальная непредвзятость должна была бы означать, что ξ(q)=const, но это невозможно, если полагать, что ξ(q) – (нормированное) распределение вероятностей. Даже если считать ξ(q) просто весами, с которыми та или иная модель учитывается при предсказании, такое решение привело бы к эффекту чрезмерно близкой подгонки (переобучения), что хорошо известно из практики при использовании метода максимального правдоподобия даже в случае алгоритмически неполных пространств моделей.

Адекватное решение дается в рамках алгоритмической теории информации, в которой не количество информации определяется по вероятности, а вероятность определяется по количеству информации, что, согласно А.Н. Колмогорову, должно иметь чисто комбинаторную основу. Как результат, вводится \xi(q)= 2^{-l(q)}, где l(q) – количество двоичных символов в записи программы q. При использовании префиксных кодов или других кодов с саморазграничением суммарная вероятность 2^{-l(q)} всех битовых строк (программ) оказывается равной 1.

Данное определение является весьма разумным: вероятность и количество информации связаны указанным соотношением, а количество информации в модели естественно определить через число бит в ее описании. Последнее, разумеется, вряд ли можно обосновать абсолютно строго; скорее, это определение имеет характер аксиомы, которая, однако, доказывает свою полную адекватность реальности. На этом можно было бы остановиться и просто использовать ξ(q) вместо μ(q), но необходимо сделать пояснения насчет того, что значимость универсального распределения ξ(q) выходит далеко за рамки его использования в (2.1.4) и (2.1.5).

В области машинного обучения, индукции и предсказания фундаментальный характер носит проблема априорных вероятностей. Ее игнорирование или неполное решение ведет к проблеме переобучения, которая свойственна большинству слабых методов машинного обучения, в том числе и искусственным нейронным сетям большинства типов. В рамках статистического подхода априорные вероятности при решении какой-то задачи могут определяться только по выборке задач данного класса, которые уже должны быть решены. Но даже в этом случае для оценивания априорного распределения вероятностей, заданного в какой-то форме, нужны будут априорные вероятности для самих распределений вероятностей. Это замкнутый круг, из которого статистическими методами выбраться принципиально нельзя. В итоге, априорное распределение, задающее (мета)модель, вводится эвристически разработчиком.

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

При такой неопределенности оказывается необходимым искать оптимальную модель источника информации в пространстве всех возможных моделей (в качестве которого выступает пространство алгоритмов). Но если знание оптимальной модели позволяет осуществлять наиболее эффективное сжатие, то обращение задачи оптимального кодирования должно позволять найти наилучшую модель. Иными словами, если нам нужно передать данные, закодированные наиболее компактным образом, то универсальный способ это сделать – передать наикратчайшую программу, воспроизводящую эти данные. Длина этой программы и будет количеством информации в этих данных, или, точнее, их Колмогоровской (алгоритмической) сложностью, а вероятность ξ(q) этой программы может быть приписана и данным. Однако с учетом того, что одни и те же данные могут быть порождены разными программами, априорную (алгоритмическую) вероятность соответствующей строки данных корректнее определить как сумму вероятностей всех этих программ. Таким образом, алгоритмическая сложность и алгоритмическая вероятность имеют вид:

formula_45

где Λ – пустая строка.

Стоит отметить, что в [Hutter, 2005] и [Hutter, 2007] обозначения для распределения вероятностей программ \xi(q)= 2^{-l(q)} и для алгоритмической вероятности произвольных строк P_{ALP}}(x) смешиваются. Мы, однако, будем использовать разные обозначения.

Данный подход позволяет ввести базовое распределение априорных вероятностей, которое «разрывает» замкнутый круг оценки априорных вероятностей в статистическом подходе: если у нас на каком-то уровне статистического вывода отсутствует информация, необходимая для ввода априорных вероятностей, используем универсальные приоры. На основе алгоритмической вероятности можно построить [Solomonoff, 1986] универсальный метод предсказания. Несколько вольно можно записать алгоритмическую вероятность того, что имеющаяся строка x будет продолжена строкой x’, как

formula_46

Вольность заключается в том, что в случае предсказания под P_{ALP}}(x) следует понимать вероятность того, что некоторая программа породит не в точности строку x, а некую строку, для которой x является префиксом. Также и P_{ALP}(xx^{'}) – вероятность порождения строки, начинающейся с конкатенации xx’.

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

Тем не менее, это понятие весьма продуктивно и позволяет избежать некоторых рискованных шагов. К примеру, в [Hutter, 2005] можно встретить необоснованное предположение, что модель среды имеет конечную сложность. Это делает среду в точном смысле детерминированной. Но в то же время у нас нет никаких гарантий, что при неограниченном увеличении сенсорной истории x_{1:k} обязательно наступит такой момент, что длина наикратчайшей программы q, способной воспроизвести эту историю, перестанет возрастать. Процесс, содержащий «истинную» случайность, как раз и характеризуется тем, что сложность порождаемых им данных неограниченно возрастает с ростом числа элементов в данных. С «практической» точки зрения, однако, не столь важно, является ли «истинная» случайность физически реальной или нет, поскольку сложность среды будет выше сложности накопленной агентом информации, и хотя бы поэтому момент стабилизации длины наикратчайшей адекватной программы q не наступит. И учет того, что точная модель среды q* будет иметь сложность, обязательно превышающую количество сенсорной информации агента (то есть не будет существовать такого момента, когда q* может быть реконструирована), может быть важным при развитии моделей алгоритмического ИИ.

Здесь мы не будем детально описывать все следствия из алгоритмической теории информации и вероятностей, поскольку они в достаточном объеме представлены во многих работах (см., напр., [Solomonoff, 1997], [Li and Vitanyi, 1997], [Потапов, 2007] и приведенные в них ссылки). Однако по мере необходимости будем обсуждать некоторые вопросы, важные для развития моделей алгоритмического ИИ.

В частности, в уравнении (2.1.6) упущен тот очевидный факт, что программы (алгоритмические модели) запускаются на некоторой универсальной машине U (или соответствуют некоторому способу программирования), в зависимости от которой длина одного и того же алгоритма будет разной. Для явного указания этого факта будем писать U(q) вместо q(Λ). Это ставит под сомнение универсальность распределения ξ(q).

Традиционный ответ на эту проблему заключается в том, что любая универсальная машина U может быть проэмулирована на другой машине V с помощью некоторой программа u, причем для любой программы q, V(uq)=U(q). Следовательно,

formula_47

и аналогично P_{V}(x)\leq2^{l(v)}P_{U}(x), где P_{V},P_{U} – алгоритмические вероятности, определяемые соответствующими машинами. То есть, задаваемые ими априорные вероятности будут отличаться не более чем на константный сомножитель. В этой связи говорят, что при достаточном объеме исходных данных зависимость индукции и предсказания от выбора опорной машины пропадает. Этот вывод нельзя сделать для неуниверсальной машины V, поскольку для нее будут существовать такие q, что P_{V}(q)=0, то есть соответствующая модель будет непредставима и невыводима при использовании данной машины. В этом смысле, распределения, задаваемые разными универсальными машинами, являются оптимальными по Парето: если взять множество сред (описываемых алгоритмическими моделями), то любое универсальное распределение будет лучше (в плане предсказания) любого другого хотя бы в одной среде (или не хуже во всех средах). О распределениях, задаваемых неуниверсальными машинами, такого сказать нельзя. Отметим также, что если ограничиваться оптимальностью по Парето в указанном виде, то это означает безразличие к тому, насколько то или иное распределение оказывается эффективным в конкретном классе сред, то есть предсказание оказывается максимально непредвзятым (но не в смысле ξ(q)=const, а в смысле выбора самого ξ(q) независимо от среды).

Однако можно сразу заметить, что «достаточный объем данных» может оказаться очень большим, и его накопление будет нереалистично долгим. Этот вопрос относится к моделям универсального интеллекта следующих уровней детальности, и мы к нему вернемся потом. Здесь же отметим, что правильнее говорить не о том, что выбор машины значения не имеет, а о том, что алгоритмические вероятности в случае разных машин являются ненулевыми для всех алгоритмических моделей, а также оказываются примерно одинаково «отсортированными». То есть нельзя задать априорные вероятности так, чтобы частичное упорядоченье моделей по вероятностям для обычной универсальной машины сменилось на противоположное. В этой связи можно сказать, что универсальным является не распределение априорных вероятностей, задаваемое какой-то одной опорной машиной, а сам способ их задания через сложность алгоритмов на универсальных машинах.