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

1. Il Problema

L'obiettivo principale delle piattaforme di deliberazione online (come Polis o Remesh) è identificare idee ampiamente condivise da una comunità di utenti basandosi sulle loro preferenze espresse. Tuttavia, l'estrazione del consenso presenta due sfide fondamentali:

1. Generalizzazione: Il consenso non dovrebbe limitarsi alle singole dichiarazioni fornite dagli utenti, ma dovrebbe rappresentare una regione continua di punti di vista correlati nello spazio delle opinioni.
2. Salienza degli argomenti: Non tutte le opinioni sono ugualmente importanti. Un'opinione potrebbe ricevere un'unanime approvazione ma essere banale (presa per scontata), mentre un'altra, dibattuta ma approvata, potrebbe rappresentare un vero consenso su un tema cruciale.

Il problema è formalizzato come la ricerca di un intervallo di consenso in uno spazio unidimensionale (1D) derivato da dati potenzialmente ad alta dimensionalità (tramite embedding e riduzione della dimensionalità). L'obiettivo è massimizzare l'accordo netto, tenendo conto della distribuzione sottostante delle questioni (che riflette la loro salienza).

2. Metodologia e Formalizzazione

Modello di Apprendimento

Il lavoro si inserisce nel framework dell'Apprendimento Passivo (Passive Learning):

• Si dispone di un campione di $m$ questioni (punti) $x_i$ estratti indipendentemente e identicamente (i.i.d.) da una distribuzione sottostante $P(x)$ (spesso sconosciuta).
• Ogni votante $c$ ha un intervallo di approvazione $I_c \subset \mathbb{R}$.
• Si assume che le preferenze siano single-peaked lungo una singola dimensione.

Funzioni di Etichettatura

• Etichetta Individuale: $L_c(x) = 2 \cdot \mathbb{1}\{x \in I_c\} - 1$. Vale $+1$ se il votante approva, $-1$ altrimenti.
• Etichetta Combinata: $l(x) = \sum_{c=1}^n L_c(x)$. Rappresenta l'accordo netto: positivo se la maggioranza approva, negativo altrimenti.

Funzione Obiettivo

L'obiettivo è trovare un intervallo ipotetico $\hat{I}$ che massimizzi il valore atteso dell'accordo netto pesato dalla probabilità delle questioni:
$$\Phi(I) = \mathbb{E}_{x \sim P} [l(x) \cdot \mathbb{1}\{x \in I\}] = \int_{I} l(x) dP(x)$$
Poiché $P(x)$ è sconosciuta, si utilizza la versione empirica su un campione $S$:
$$\hat{\Phi}_S(I) = \frac{1}{m} \sum_{i=1}^m l(x_i) \cdot \mathbb{1}\{x_i \in I\}$$

Algoritmo ERM (Empirical Risk Minimization)

Il problema di massimizzare la somma empirica $\sum l(x_i)$ all'interno di un intervallo è risolto efficientemente:

1. Proprietà Strutturale: L'intervallo ottimale può essere scelto in modo che i suoi estremi coincidano con punti del campione.
2. Riduzione: Il problema si riduce a trovare la sottoarray sum massima (Maximum Subarray Sum) su un array di punteggi ordinati.
3. Implementazione: Viene utilizzato l'algoritmo di Kadane per trovare l'intervallo ottimale in tempo lineare rispetto al numero di campioni, dopo averli ordinati.
   • Complessità totale: $O((n + m) \log(n + m))$ usando un algoritmo sweep-line per calcolare i punteggi $l(x_i)$, o $O(nm + m \log m)$ con un approccio ingenuo.

3. Contributi Chiave

1. Definizione Formale del Problema: Una definizione rigorosa per la ricerca di consenso basato su intervalli 1D, incorporando la salienza delle questioni tramite una distribuzione sottostante.
2. Algoritmo Efficiente: Un algoritmo ERM basato su Kadane che trova la soluzione empirica ottima in modo computazionalmente efficiente.
3. Garanzie Teoriche (PAC Learning):
   • Analisi della complessità del campione basata sulla pseudo-dimensione della classe di funzioni.
   • È stato dimostrato che la pseudo-dimensione della classe di funzioni è 2.
   • Derivazione di un limite superiore per la complessità del campione: $m = O\left(\frac{n^2}{\epsilon^2} (\ln \frac{n}{\epsilon} + \ln \frac{1}{\delta})\right)$, garantendo che l'intervallo trovato sia $\epsilon$-vicino all'ottimo vero con probabilità $1-\delta$.
4. Validazione Sperimentale: Esperimenti che mostrano come la complessità empirica necessaria sia spesso molto inferiore ai limiti teorici superiori e l'esplorazione di strategie di query attive.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti con $n=100$ votanti e diverse distribuzioni di campionamento (Uniforme, Normale Troncata, Esponenziale Troncata).

• Complessità del Campione: I risultati mostrano che è possibile identificare regioni di consenso quasi ottimali utilizzando un numero di campioni molto inferiore rispetto al limite teorico superiore (spesso di ordini di grandezza).
• Query su Sottogruppi di Votanti: Ridurre il numero di votanti interrogati per ogni punto campione degrada rapidamente la qualità del consenso trovato, specialmente se le regioni di approvazione dei votanti non sono correlate.
• Query Intelligente (Active Learning): È stata proposta una strategia di ricerca binaria per determinare gli intervalli di approvazione di ogni votante.
  • Invece di chiedere a tutti i votanti su tutti i punti, si chiede a ogni votante di identificare i confini del proprio intervallo tramite una ricerca adattiva.
  • Risultato: Questo approccio riduce drasticamente il numero di query necessarie per votante (es. da $10^5$ punti a ~30 query per votante) mantenendo alta la qualità della regione di consenso identificata.

5. Significato e Implicazioni

Questo lavoro fornisce una base teorica solida per l'estrazione del consenso in contesti di deliberazione digitale, spostando l'attenzione da approcci euristici a metodi con garanzie di apprendimento automatico provate (PAC).

• Teorico: Collega la teoria della scelta sociale e la geometria delle opinioni con l'apprendimento statistico, fornendo limiti di generalizzazione rigorosi.
• Pratico: L'algoritmo proposto è scalabile e può essere integrato in piattaforme reali per ridurre il carico cognitivo sui partecipanti (riducendo le query) pur mantenendo un consenso rappresentativo.
• Futuro: Il framework apre la strada a:
  • Estensioni a spazi multidimensionali (più adatti a dati testuali complessi).
  • Applicazioni nell'allineamento dell'IA (AI Alignment), dove gli intervalli di consenso possono filtrare o guidare i meccanismi di ricompensa (RLAIF).
  • Validazione su dataset reali provenienti da piattaforme come Pol.is.

In sintesi, il paper propone un metodo matematicamente fondato per trovare il "terreno comune" in modo efficiente, bilanciando l'accordo quantitativo con la rilevanza qualitativa delle discussioni.