Closed-Loop Generative Selection: Convergence, Memory, and Noisy Oracles

Resumo Técnico: Seleção Generativa de Ciclo Fechado

Definição do Problema
A seleção generativa de ciclo fechado emergiu como uma metodologia primária na descoberta computacional de fármacos. Neste fluxo de trabalho, um modelo generativo aprendido propõe moléculas candidatas, um oráculo de aptidão (ex: docking ou ensaio) pontua elas, e os melhores candidatos são retidos para retreinar o modelo para a próxima rodada. Apesar de sua utilidade prática, o método carece de uma teoria de convergência rigorosa. A análise clássica de algoritmos evolucionários baseia-se na propriedade de Markov do processo de população; entretanto, na seleção generativa, o modelo $G_t$ é retreinado a cada rodada com base no histórico de pools de elite. Essa adaptação quebra a propriedade de Markov da sequência de populações $(P_t)$, tornando as ferramentas analíticas padrão inaplicáveis. Além disso, a área carece de uma teoria unificada que aborde o papel da memória (o quanto o passado informa o modelo), o impacto de oráculos ruidosos e o custo real da busca, medido em avaliações de oráculo em vez de rodadas algorítmicas.

Metodologia e Estrutura Matemática
Os autores desenvolvem uma teoria autossuficiente reformulando o problema em um espaço de estados ampliado para recuperar uma estrutura de Markov.

1. Formulação de Markov: Em vez de analisar apenas a população $P_t$, os autores definem um estado aumentado $Z_t = (P_t, G_t)$ ou um processo de histórico $H_t = (P_0, \dots, P_t)$. Eles provam que, sob regras de atualização determinísticas, esses processos aumentados são cadeias de Markov homogêneas no tempo.
2. Elitismo e Absorção: O algoritmo emprega uma regra de seleção elitista (retendo os top-$N$ moléculas), garantindo que a aptidão da elite $f(P_t)$ seja não decrescente. Isso cria uma estrutura de absorção onde o conjunto alvo de moléculas $\epsilon$-ótimas é um estado absorvente.
3. Método de Nível de Aptidão: A análise decompõe a busca em "estadias" (sojourns) em níveis discretos de aptidão. O tempo de espera esperado é limitado pela soma dos tempos esperados para escapar de cada nível. A probabilidade de escape no nível $k$ depende da capacidade do kernel generativo de propor moléculas estritamente mais aptas que o nível atual.
4. Modelos de Memória: O artigo analisa três regimes:
   • Estático/Passo único: $G_t$ depende apenas de $P_t$.
   • Memória Total: $G_t$ depende de todo o histórico.
   • Memória de $m$-passos finitos: $G_t$ depende dos últimos $m$ pools.
5. Tratamento de Ruído: A teoria se estende a oráculos ruidosos substituindo avaliações únicas por consultas replicadas e estimadores robustos (ex: média-da-mediana, testes de sinal) para certificar lacunas de aptidão sob distribuições de ruído sub-Gaussianas e de cauda pesada.

Principais Contribuições e Resultados

• Convergência e Limites de Tempo de Impacto (Hitting-Time):
  O artigo prova a convergência quase certa para qualquer algoritmo de seleção generativa que satisfaça uma condição de positividade uniforme (um piso de exploração uniforme). Estabelece um "Limite de Tempo de Impacto em Camadas" onde o número esperado de rodadas é limitado pela soma das probabilidades inversas de escape através dos níveis de aptidão. Este limite é mais agudo que os limites de cauda geométrica padrão, pois considera a estrutura do landscape.

• Hierarquia de Memória e Aprendizado Monótono:
  Sob uma condição de "aprendizado monótono" (onde condicionar a dados passados adicionais nunca diminui a probabilidade de propor uma molécula melhor), os autores provam uma hierarquia de memória: a memória mais profunda melhora estritamente (ou pelo menos não prejudica) as probabilidades de escape e reduz o tempo de impacto esperado. Neste regime, a memória total é ótima, e o benefício da memória exibe retornos decrescentes, saturando exponencialmente.

• Aprendizado Não Monótono e Profundidade de Memória Ótima:
  O artigo identifica que o aprendizado monótono frequentemente falha na prática (ex: quando a média de pools ruidosos introduz viés de obsolescência/estagnação). Na ausência de monotonicidade, os autores derivam uma teoria de tempo de saída não monótona. Eles definem um "perfil de aprendizado" $\rho_k(j)$ que representa a probabilidade de escape como uma função do número de pools do nível atual na janela. O tempo de estadia esperado mostra-se uma função em forma de U da profundidade de memória $m$. Consequentemente, existe uma profundidade de memória ótima finita $m^*$ que equilibra a redução de variância de mais dados contra o viés de dados obsoletos. Essa profundidade ótima corresponde ao primeiro pico do perfil de aprendizado.

• Estratégia de Avaliação Mínima:
  Recategorizando a teoria em termos de avaliações de oráculo (o verdadeiro gargalo no design de fármacos), os autores provam que a operação sequencial ($M=1$) minimiza o número total de avaliações. Embora tamanhos de lote maiores ($M > 1$) reduzam o número de rodadas, eles desperdiçam avaliações em candidatos que são pontuados mesmo após um candidato melhor já ter sido encontrado no mesmo lote. A estratégia ótima é propor um candidato por vez, potencialmente combinada com memoização e interrupção precoce.

• Oráculos Ruidosos:
  Para ruído sub-Gaussiano, o custo de certificação infla por um fator proporcional a $\sigma^2/\Delta^2$, onde $\Delta$ é a lacuna de aptidão. Para ruído de cauda pesada (onde a variância pode ser infinita), a média amostral mostra-se insuficiente. Os autores demonstram que estimadores robustos (média-da-mediana) ou testes de sinal livres de distribuição restauram a correção, com custos de consulta que degradam graciosamente com a densidade da cauda.

Significância e Alegações
O artigo afirma fornecer a primeira análise rigorosa de convergência e tempo de execução para seleção generativa de ciclo fechado que considera kernels de aprendizado adaptativos. Sua significância reside em:

1. Resolver a Quebra de Markov: Ao construir um espaço de estados aumentado, ele preenche a lacavra entre modelos generativos adaptativos e a teoria clássica de algoritmos evolucionários.
2. Quantificar a Memória: Ele vai além do heurístico "mais dados é melhor" para fornecer uma análise precisa de compensação entre viés e variância, identificando condições sob as quais a memória finita é ótima.
3. Otimização de Recursos: Estabelece que, para a descoberta de fármacos com restrição de custo, a avaliação sequencial ($M=1$) é teoricamente ótima para minimizar chamadas de oráculo, desafiando a prática comum de avaliação paralela em grandes lotes.
4. Robustez: Oferece um framework para lidar com dados experimentais ruidosos e realistas, incluindo distribuições de cauda pesada comuns em ensaios biológicos, sem sacrificar as garantias de convergência.

Os autores concluem que, embora a teoria seja abstrata e dependa de limites inferiores para probabilidades de escape que dependem de implementações específicas de modelos, ela fornece um framework fundamental para analisar e projetar algoritmos de seleção generativa. Eles identificam três problemas abertos: quantificar probabilidades de escape para arquiteturas neurais específicas, projetar aprendizes que sejam simultaneamente não monótonos e composicionalmente homogêneos para realizar ganhos de memória adaptativos ao nível, e estender a certificação robusta para espaços latentes contínuos e ruído assimétrico.