Probably Approximately Consensus: On the Learning Theory of Finding Common Ground

Título: Probavelmente Consenso Aproximado: Sobre a Teoria da Aprendizagem para Encontrar Terreno Comum

1. O Problema

O objetivo central é identificar regiões de "acordo amplo" (consenso) em plataformas de deliberação online (como Polis ou Remesh). O desafio reside em ir além da simples agregação de pontos de aprovação isolados e considerar a saliência (importância relativa) dos tópicos discutidos.

• Contexto: As opiniões são representadas como pontos em um espaço de alta dimensão, que são projetados em uma dimensão única (1D) através de técnicas de embedding e redução de dimensionalidade.
• Modelo: Assume-se que as preferências dos eleitores são unimodais (picos únicos) ao longo dessa dimensão 1D. Cada eleitor aprova um intervalo contíguo de opiniões.
• Desafio: Encontrar um intervalo hipotético $\hat{I}$ que maximize o acordo líquido (net agreement) ponderado pela distribuição subjacente das questões (o que garante que tópicos mais frequentes/salientes tenham maior peso).
• Configuração: O trabalho foca no cenário de aprendizagem passiva, onde um conjunto de amostras de questões é fornecido e rotulado pelos eleitores, sem interação estratégica inicial.

2. Metodologia

Definição Formal:

• Função de Rótulo Individual ($L_c$): Para um eleitor $c$ e uma questão $x$, $L_c(x) = +1$ se $x$ está no intervalo de aprovação do eleitor, e $-1$ caso contrário.
• Função de Rótulo Combinada ($l(x)$): Soma dos rótulos de todos os $n$ eleitores para uma questão $x$. Representa o acordo líquido ($l(x) = 2k - n$, onde $k$ é o número de aprovações).
• Função Objetivo ($\Phi(I)$): Maximizar o valor esperado do acordo líquido dentro de um intervalo candidato $I$, ponderado pela distribuição de probabilidade $P(x)$ das questões:
  $$\Phi(I) = \mathbb{E}_{x \sim P} [l(x) \cdot \mathbb{1}\{x \in I\}]$$

Algoritmo Proposto (ERM - Minimização de Risco Empírico):
Como a distribuição $P(x)$ é desconhecida, o algoritmo utiliza uma amostra finita $S$ de questões para maximizar o objetivo empírico $\hat{\Phi}_S(I)$.

1. Cálculo de Pontuação: Para cada questão na amostra, calcula-se $l(x)$.
2. Ordenação: As questões são ordenadas no espaço 1D.
3. Busca de Subarray Máximo: O problema de encontrar o intervalo ótimo reduz-se ao problema clássico de Soma Máxima de Subarray (Maximum Subarray Sum) sobre a sequência de pontuações ordenadas.
4. Implementação: Utiliza-se o Algoritmo de Kadane para encontrar o intervalo $[x_{(j)}, x_{(k)}]$ que maximiza a soma das pontuações em tempo linear $O(m)$, onde $m$ é o tamanho da amostra.

Análise Teórica (PAC Learning):

• Os autores estabelecem garantias de Aprendizagem Provavelmente Aproximadamente Correta (PAC).
• Dimensão Pseudo: A classe de funções associada ao problema tem uma dimensão pseudo-dimension ($Pdim$) de 2.
• Complexidade de Amostragem: Derivaram um limite superior para o número de amostras $m$ necessário para garantir que o intervalo empírico esteja dentro de $\epsilon$ do ótimo verdadeiro com probabilidade $1-\delta$. A complexidade escala com $O(n^2/\epsilon^2)$, onde $n$ é o número de eleitores.

3. Contribuições Principais

1. Definição Formal do Problema: Formalização da busca por consenso em 1D incorporando a saliência das questões através de uma distribuição subjacente.
2. Algoritmo Eficiente: Proposta de um algoritmo ERM baseado no Algoritmo de Kadane, que resolve o problema de forma computacionalmente eficiente.
3. Garantias Teóricas: Derivação de limites de complexidade de amostragem baseados na análise de dimensão pseudo, fornecendo garantias rigorosas de desempenho.
4. Validação Experimental e Estratégias de Consulta: Demonstração de que é possível reduzir drasticamente o número de consultas necessárias através de estratégias inteligentes (como busca binária adaptativa) em vez de consultas passivas massivas.

4. Resultados Experimentais

Os experimentos foram realizados com dados sintéticos ($n=100$ eleitores) sob diferentes distribuições (Uniforme, Normal Truncada, Exponencial).

• Tightness do Limite Teórico: Os resultados mostraram que, na prática, o algoritmo alcança regiões quase ótimas com muito menos amostras do que o limite superior teórico sugerido.
• Redução de Consultas (Estratégias Ativas):
  • Consultar menos eleitores por ponto: Reduzir o número de eleitores consultados para cada ponto amostrado degrada rapidamente a qualidade do consenso encontrado, especialmente se as preferências não forem correlacionadas.
  • Consultar menos pontos por eleitor (Busca Inteligente): Ao invés disso, os autores propuseram um método de busca binária para determinar os limites do intervalo de aprovação de cada eleitor.
  • Resultado Chave: Com essa abordagem ativa, foi possível identificar o intervalo ótimo com apenas ~30 consultas por eleitor, mesmo quando a amostra total continha $10^5$ pontos. Isso reduz drasticamente o custo computacional e de interação humana.

5. Significado e Impacto

Este trabalho fornece a base teórica e algorítmica para sistemas de deliberação coletiva mais robustos.

• Teórico: Conecta a teoria de escolha social (como o modelo de espaço de opinião) com a teoria da aprendizagem computacional (PAC learning), oferecendo garantias de generalização que faltavam em abordagens heurísticas anteriores.
• Prático: O algoritmo e as estratégias de consulta ativa são vitais para plataformas reais (como o Polis), onde o custo de obter feedback de milhares de usuários para milhares de questões é proibitivo. A capacidade de encontrar consenso com poucas interações torna a aplicação em larga escala viável.
• Futuro: O trabalho abre caminho para extensões em espaços de alta dimensão, aprendizado ativo estratégico e aplicações em alinhamento de IA (usando consenso para filtrar ou recompensar expressões de IA aceitáveis).

Em resumo, o paper transforma a busca por consenso de um problema heurístico em um problema de otimização com garantias matemáticas, demonstrando como encontrar "terreno comum" de forma eficiente e escalável.