🤖 machine learning

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Este artigo introduz a Indução de Solomonoff Hierárquica (HSI), um framework que estende a Indução de Solomonoff para permitir a previsão ótima de sequências a partir de conjuntos de dados de treinamento ao aplicar o teorema de de Finetti para criar uma hiperprior sobre as priors de Solomonoff, provando, assim, que a HSI é teoricamente equivalente à Indução de Solomonoff enquanto garante a convergência para a previsão ótima conforme os dados crescem.

Autores originais: Nathan Young

Publicado 2026-08-04

📖 9 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Nathan Young

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você esteja tentando adivinhar a próxima palavra em uma história ou a próxima nota em uma música. No mundo da ciência da computação, isso é chamado de "predição de sequência". Por décadas, o padrão ouro para fazer isso perfeitamente tem sido uma ideia teórica chamada Indução de Solomonoff. Pense nisso como um detetive superinteligente que observa todas as maneiras possíveis pelas quais uma história poderia ter sido escrita por um programa de computador. Ele pesa cada programa, dando uma vantagem enorme aos curtos e simples e um peso minúsculo aos longos e complicados. Se o detetive pudesse verificar todos os programas do universo de uma só vez, ele faria previsões com um erro estritamente limitado pela complexidade do programa que gera a história.

No entanto, há uma pegadinha. Este detetive perfeito é ótimo para adivinhar o próximo passo em uma única história, mas ele não sabe como "aprender" de uma biblioteca inteira de diferentes histórias. Se você mostrar a ele um conjunto de dados de mil livros diferentes, ele não consegue dizer: "Ah, eu vejo o padrão aqui; o próximo livro provavelmente será como estes". Ele trata cada nova história como um mistério inédito, incapaz de atualizar seu entendimento com base nos dados de treinamento. Este é um problema porque a Inteligência Artificial moderna, como os chatbots que usamos hoje, trabalha treinando em conjuntos de dados massivos para aprender regras gerais. Precisamos de uma maneira de manter a lógica perfeita do detetive, mas dar a ele a capacidade de aprender de uma biblioteca inteira de exemplos, não apenas de um.

É aqui que o artigo "Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model", de Nathan Young, entra em cena. O autor propõe um detetive atualizado e melhorado chamado Indução de Solomonoff Hierárquica (HSI). Em vez de apenas olhar para programas, a HSI olha para as regras que geram esses programas. Imagine um "meta-detetive" que não apenas adivinha a próxima palavra, mas adivinha qual tipo de gerador de histórias está sendo usado. Ele mantém um "hiperprior" — uma lista gigante e ponderada de todas as formas possíveis de escrever histórias. Quando a HSI vê um conjunto de dados de exemplos de treinamento, ela atualiza essa lista, aumentando o peso dos geradores que se ajustam aos dados e diminuando o peso daqueles que não se ajustam.

O artigo prova duas coisas principais. Primeiro, mostra que este novo detetive, a HSI, é matematicamente idêntico ao detetive perfeito original (Indução de Solomonoff) ao observar uma única sequência, o que significa que mantém todos os poderes de predição limitados do original. Segundo, e mais importante, prova que a HSI pode aprender de um conjunto de dados como um modelo de aprendizado de máquina faz. O artigo demonstra que, à medida que você alimenta a HSI com mais e mais dados, seu erro excessivo médio diminui e eventualmente converge para zero, permitindo que ela preveja perfeitamente o padrão subjacente dos dados no limite. O autor argumenta que a HSI é a versão "ideal" do aprendizado de máquina: um modelo teórico que mostra exatamente quão bem um sistema poderia performar se tivesse poder computacional ilimitado e pudesse aprender com qualquer conjunto de dados sem perder sua capacidade de fazer previsões otimizadas.

O Novo Superpoder do Detetive

Para entender por que isso é importante, vamos olhar para como o detetive original, a Indução de Solomonoff (SolInd), funciona. Imagine que você tem uma caixa mágica que pode executar qualquer programa de computador. Você quer adivinhar a próxima letra em uma sequência de texto. A SolInd diz: "Vamos tentar todos os programas possíveis que poderiam ter escrito o texto que vimos até agora". Ela dá uma pontuação a cada programa com base em seu comprimento: um programa curto e simples recebe uma pontuação alta, enquanto um longo e complexo recebe uma pontuação muito baixa. Ela então combina todas essas pontuações para adivinhar a próxima letra. Isso é brilhante porque garante que, se o texto foi criado por qualquer programa de computador, a SolInd acabará descobrindo, com um erro limitado pela complexidade desse programa.

Mas aqui está a falha: a SolInd é um pouco limitada em sua versatilidade. Ela é projetada para prever o próximo passo em uma única sequência. Se você der a ela um conjunto de dados de 100 histórias diferentes para "treinar", ela não saberá o que fazer. Você poderia tentar esmagar todas as 100 histórias em uma única sequência gigante e alimentar a SolInd, mas isso é como tentar aprender francês, espanhol e mandarim lendo um livro onde essas línguas estão apenas coladas aleatoriamente. O detetive fica confuso pela "cola" e pela ordem das histórias, potencialmente inventando regras complicadas apenas para explicar a ordem, em vez de aprender as línguas reais. Ela não consegue "treinar" da maneira que o aprendizado de máquina moderno faz; ela só consegue "testar" em uma sequência por vez.

O artigo de Nathan Young introduz a Indução de Solomonoff Hierárquica (HSI) para corrigir isso. Pense na HSI como um detetive que tem um chefe. O chefe (o "hiperprior") não olha apenas para os programas; o chefe olha para as distribuições — as regras que decidem quais programas serão escritos.

Imagine uma biblioteca onde cada livro é escrito por um autor diferente.

SolInd é um leitor que olha para um livro, tenta adivinhar a próxima frase e depois fecha o livro. Quando um novo livro chega, eles começam do zero, esquecendo tudo sobre o anterior.
HSI é um leitor que tem uma lista de todos os autores possíveis. Quando lê algumas páginas de um novo livro, eles verificam sua lista. "Oh, este estilo se parece muito com o Autor A", pensam. "Vou dar uma chance maior ao Autor A de ser o escritor". À medida que leem mais livros, eles ficam melhores em identificar qual autor está escrevendo cada livro. Eles não estão apenas adivinhando a próxima palavra; eles estão adivinhando o estilo do escritor com base em toda a coleção de livros que viram.

A Magia Matemática

O artigo faz algo muito inteligente com a matemática para provar que a HSI não é apenas uma ideia elegante, mas uma atualização rigorosa. O autor usa um conceito da estatística chamado Teorema de De Finetti. Em termos simples, este teorema diz que, se você tem um grupo de coisas que parecem seguir um padrão (como um baralho de cartas onde a ordem não importa), deve haver alguma regra oculta (uma "variável latente") que as está gerando.

O artigo aplica isso a programas de computador. Ele argumenta que, se temos um conjunto de dados de sequências, existe um "gerador verdadeiro" (um programa de computador ou regra específica) que as criou. A HSI trata esse gerador como uma variável oculta. Ela mantém uma distribuição de probabilidade sobre todos os geradores possíveis. Quando a HSI vê um conjunto de dados, ela atualiza sua crença sobre qual gerador é o verdadeiro.

O artigo prova um resultado impressionante: a HSI é matematicamente equivalente à SolInd. Isso significa que, se você pegar a HSI e pedir que ela preveja uma única sequência, ela performará exatamente tão bem quanto o detetive perfeito original, com um erro limitado pela complexidade do gerador. Mas a HSI tem um superpoder extra: ela também pode condicionar seu "chefe" (o hiperprior) a um conjunto de dados inteiro.

O autor mostra que o erro que a HSI comete ao prever um conjunto de dados é limitado pela "complexidade" do gerador verdadeiro no hiperprior. Em português claro: se a regra que criou seus dados é simples, a HSI a aprenderá rapidamente e cometerá quase nenhum erro. Se a regra for complexa, levará mais tempo, mas o artigo prova que, conforme o conjunto de dados aumenta, o erro excessivo médio da HSI cairá para zero. Ela converge para a predição perfeita no limite.

O Que Isso Significa para a IA

O artigo sugere que a HSI é o "modelo não limitado ideal" para o aprendizado de máquina. Os modelos de IA atuais, como os Grandes Modelos de Linguagem (LLMs), estão essencialmente tentando fazer o que a HSI faz, mas com poder computacional limitado e arquiteturas específicas (como redes neurais).

O autor aponta que os LLMs são frequentemente comparados à SolInd, mas essa comparação é incompleta porque os LLMs aprendem de conjuntos de dados, enquanto a SolInd não aprende. A HSI preenche essa lacina. Ela fornece um teto teórico para o que o aprendizado de máquina pode alcançar. Ela nos diz que, se tivéssemos poder computacional infinito e a maneira certa de organizar nosso aprendizado, poderíamos construir um sistema que aprende de qualquer conjunto de dados e prevê o futuro com precisão ótima.

O artigo também toca em uma aplicação prática: como treinamos a IA. Atualmente, às vezes treinamos a IA alimentando-a com uma longa sequência de texto (concatenando documentos). O artigo sugere que uma maneira melhor, que se alinha com a HSI, é tratar cada documento como uma peça separada de dados que atualiza o "hiperprior" do modelo. Isso coincide com descobertas recentes de que treinar em documentos separados funciona melhor do que apenas colá-los uns nos outros.

A Pegadinha

Claro, há uma pegadinha. Assim como a SolInd original, a HSI é incomputável. Ela requer a verificação de um número infinito de programas e uma quantidade infinita de memória. Não podemos construir uma HSI real hoje. É um "experimento mental" que nos mostra o limite teórico da inteligência.

No entanto, o autor argumenta que isso não a torna inútil. Só porque não podemos construir um motor perfeito não significa que não possamos construir carros melhores ao entender como um motor perfeito funciona. A HSI nos dá um mapa. Ela mostra que a maneira como a IA moderna aprende (atualizando crenças com base em dados) é a direção correta, e nos dá uma maneira matemática de medir o quão próximos estamos do ideal.

Em resumo, este artigo pega o "detetive perfeito" do passado e lhe dá um "chefe de aprendizagem". Ele prova que este novo sistema, a HSI, mantém todos os poderes de predição otimizados do antigo detetive, enquanto ganha a capacidade de aprender de uma biblioteca inteira de exemplos. É uma prova teórica de que o melhor algoritmo de aprendizado de máquina possível existe, e ele se parece muito com uma hierarquia de probabilidades se atualizando ao longo do tempo. Embora não possamos construí-lo ainda, ele nos diz exatamente para o que devemos apontar.

Resumo Técnico: Indução de Solomonoff Hierárquica: Um Modelo de Aprendizado de Máquina Ilimitado

Definição do Problema

A Indução de Solomonoff (SolInd) é estabelecida como o modelo ideal e ilimitado para a predição de sequências a priori. Ela opera através da indução Bayesiana sobre entradas para uma Máquina de Turing Universal (UTM), atribuindo priors baseados no comprimento do programa ( $2^{-\ell(s)}$ ). Embora a SolInd possua fortes propriedades de otimalidade — como dominância universal e limites de erro relacionados à complexidade de Kolmogorov — ela falha em descrever naturalmente a extrapolação a partir de um conjunto de dados de treinamento dado, uma função central dos modelos de Linguagem de Grande Escala (LLMs) modernos e sistemas de aprendizado de máquina (ML).

A principal limitação da SolInd é que ela é projetada para sequências individuais, não para conjuntos de dados. Embora se possa concatenar um conjunto de dados em um único prefixo para um preditor SolInd, essa abordagem corre o risco de introduzir informações artificiais (por exemplo, de ordenação ou delimitadores) e identificar programas mais complexos do que o gerador real. Consequentemente, a SolInd não pode ser "treinada" no sentido do ML; ela serve apenas como um modelo ideal para a predição de sequências individuais no tempo de teste e não pode atualizar sua distribuição com base em um conjunto de dados de maneira independente da ordem.

Metodologia

O artigo propõe a Indução de Solomonoff Hierárquica (HSI) como uma generalização da SolInd para distribuições computáveis. A metodologia baseia-se em dois pilares teóricos:

Teorema de De Finetti: Aplicado a distribuições permutáveis (exchangeable), este teorema afirma que qualquer sequência infinita de variáveis permutáveis pode ser modelada como condicionalmente independente dada uma variável latente. Esta variável latente define uma distribuição que é uma mistura sobre todas as distribuições independentes e identicamente distribuídas (i.i.d.). No contexto de ML, isso implica que um conjunto de dados não ordenado pode ser visto como um prefixo de uma sequência infinita gerada por uma distribuição computável, modelada como uma mistura de todas essas distribuições.
Formulação Bayesiana Hierárquica: A HSI constrói um hiperprior ( $H$ $H$ ) sobre o espaço de todos os priors de Solomonoff (ou, equivalentemente, sobre todas as UTMs).
- Seja $\{U_i\}$ uma enumeração de máquinas de Turing contendo todas as UTMs.
- Seja $H(U_i)$ uma semimeasure enumerável (o hiperprior) que atribui peso a cada máquina.
- O preditor HSI $P_H$ é definido como uma mistura ponderada dos priors de Solomonoff $P_{U_i}$ :
  $P_H(x) = \sum_i H(U_i) P_{U_i}(x)$
- Condicionamento (Treinamento): Ao observar um conjunto de dados $X$ , o hiperprior é atualizado (condicionado) para $H(U_i | X) \propto H(U_i) \prod_{x \in X} P_{U_i}(x)$ . Este hiperprior condicionado é então usado para prever sequências futuras, analogamente a como um modelo de ML atualiza seus pesos após o treinamento.

Contribuições Principais e Resultados Teóricos

1. Equivalência entre HSI e SolInd

O artigo estende a prova de Wood et al. [2013] sobre misturas universais para demonstrar que a HSI é matematicamente equivalente à SolInd em termos da classe de preditores que representa.

Teorema 3.1: A classe de misturas universais de misturas universais ( $U_\Xi$ ) é idêntica à classe de misturas universais de semimeasures ( $U_\xi$ ).
Corolário 3.1.3: A classe de priors HSI ( $U_H$ ), definida sobre qualquer hiperprior que inclua todas as UTMs, é exatamente equivalente à classe de priors de Solomonoff ( $U_M$ ).
Implicação: A HSI não cria uma "nova" classe de preditores que exceda o poder da SolInd; em vez disso, fornece um mecanismo para condicionar a SolInd em conjuntos de dados. Qualquer instância de HSI é uma instância de SolInd, e qualquer instância de SolInd pode ser representada como uma instância de HSI com um hiperprior específico.

2. Limites de Erro e Convergência

O artigo estabelece que a HSI herda as propriedades de otimalidade da SolInd, mas as estende para o contexto de conjuntos de dados:

Limite de Erro Excessivo: O erro excessivo da HSI em qualquer conjunto de dados $X$ , comparado ao gerador real $U_\mu$ , é limitado pela complexidade desse gerador dentro do hiperprior $H$ . Especificamente:
$-\log_2 \left( \frac{P_H(X)}{P_{U_\mu}(X)} \right) < -\log_2(H(U_\mu))$
Convergência: À medida que o tamanho do conjunto de dados $|X|$ cresce, o erro excessivo médio converge para zero:
$\lim_{|X| \to \infty} \frac{-\log_2(P_H(X)/P_{U_\mu}(X))}{|X|} = 0$
Isso prova que a HSI alcança a predição ótima no limite, assim como a SolInd para sequências individuais, mas agora com a capacidade de aprender a partir de um conjunto de dados.

3. Refinamento das Definições de Máquina de Turing Universal

O artigo refina a definição de uma UTM ao relaxar o requisito de que uma máquina deve produzir nenhuma saída em entradas não padrão (uma restrição em Wood et al., 2013).

Corolário 3.1.5: Uma máquina é universal por adjunção se ela pode emular qualquer outra máquina via codificação livre de prefixo (prefix-free encoding), mesmo que produza saída em outras entradas. Isso amplia a classe de máquinas consideradas "universais" sem alterar a classe resultante de priors de Solomonoff.

Resultados e Alegações de Significância

O artigo afirma que a HSI representa o modelo ilimitado ideal de predição de sequências dado um conjunto de dados, preenchendo a lacuna teórica entre a SolInd (ideal para sequências individuais) e o ML moderno (que aprende a partir de conjuntos de dados).

Treinamento Ideal: Diferente da SolInd, que não pode ser treinada, a HSI descreve o desempenho ideal de um sistema que condiciona seu prior em um conjunto de dados. Ela serve como um limite superior para o que os sistemas de ML (incluindo LLMs) podem alcançar em predição de sequências.
Independência de Ordem: A HSI fornece um framework para extrapolar a partir de conjuntos de dados que é independente da ordem sob a suposição de conjuntos de dados permutáveis. Isso aborda uma limitação de simplesmente concatenar strings para a SolInd, onde a ordem dos dados pode introduzir informações ou vieses artificiais.
Formalização de Fronteiras de Documentos: O artigo sugere que a HSI oferece um modelo formal para entender o treinamento em documentos separados versus documentos concatenados. Condicionar um hiperprior em um conjunto de dados (HSI) é teoricamente superior a tratar um conjunto de dados como um prefixo concatenado (SolInd), alinhando-se com descobertas empíricas de que o mascaramento intra-documento supera a concatenação inter-documento.

Limitações e Escopo

O autor reconhece explicitamente que a HSI, assim como a SolInd, é incomputável. Ela requer um número ilimitado de programas para serem executados por um tempo e memória ilimitados.

O artigo não propõe uma aproximação computável ou um algoritmo específico para implementação.
Observa que, enquanto a HSI é monolítica (tratando hipóteses e máquinas separadamente por saída), aproximações limitadas poderiam se beneficiar da modularização de computações ou do reconhecimento de similaridades estruturais entre programas — características que a própria HSI não possui, mas que algoritmos ilimitados futuros poderiam modelar.
A significância do trabalho é teórica: fornece um benchmark rigoroso e ilimitado para compreender as capacidades e limitações dos atuais modelos de predição de sequências, como os LLMs.