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

Titel: Probably Approximately Consensus: Over de Lerende Theorie van het Vinden van Gemeenschappelijk Grond

Auteurs: Carter Blair, Ben Armstrong, Shiri Alouf-Heffetz, Nimrod Talmon, Davide Grossi.

1. Probleemdefinitie

Het paper richt zich op het probleem van het identificeren van "gemeenschappelijk grond" (consensus) binnen online deliberatieplatforms (zoals Pol.is of Remesh). Het doel is om gebieden te vinden waar een gemeenschap van gebruikers breed akkoord gaat, rekening houdend met de relevantie (salience) van specifieke onderwerpen.

• De uitdaging: Bestaande methoden identificeren vaak punten die algemeen worden goedgekeurd, maar deze kunnen triviaal zijn (bijv. "AI-vooruitgang is belangrijk") en niet het kerndebat vertegenwoordigen. Een ideale consensus moet gebieden omvatten die zowel hoog worden goedgekeurd als salient (veel voorkomend of belangrijk) zijn.
• Het Model: Het paper modelleert meningen in een één-dimensionale (1D) opinieruimte. Deze ruimte wordt afgeleid van hogere dimensionale data (bijv. tekst-embeddings) via dimensiereductie.
  • Elke stemmer $c$ heeft een keuzestreek (interval) $I_c \subset \mathbb{R}$ waarbinnen ze een onderwerp $x$ goedkeuren.
  • De salience van een onderwerp wordt gemodelleerd door een onderliggende verdeling $P(x)$ van de problemen (stemmen).
• Het Doel: Vind een hypothees-interval $\hat{I}$ dat de verwachte netto-instemming maximaliseert over de verdeling $P(x)$. Dit betekent dat we een interval zoeken waar de som van goedkeuringen (gewogen naar hoe vaak dat onderwerp voorkomt) het grootst is.

2. Methodologie

Formalisatie

• Labelfunctie: Voor een stemmer $c$ en een onderwerp $x$ is de labelfunctie $L_c(x) = 2 \cdot \mathbb{1}\{x \in I_c\} - 1$. Dit geeft $+1$ voor goedkeuring en $-1$ voor afkeuring.
• Gecombineerde labelfunctie: $l(x) = \sum_{c=1}^n L_c(x)$. Dit is de netto-instemming op punt $x$.
• Doelfunctie (Waarheid): $\Phi(I) = \mathbb{E}_{x \sim P}[l(x) \cdot \mathbb{1}\{x \in I\}]$. Dit is de verwachte netto-instemming binnen het interval $I$.
• Empirische Doelfunctie: Omdat $P(x)$ onbekend is, wordt er gewerkt met een steekproef $S = \{x_1, ..., x_m\}$. De empirische doelstelling is het gemiddelde van de netto-instemming binnen het interval over de steekproef: $\hat{\Phi}_S(I) = \frac{1}{m} \sum_{i=1}^m l(x_i) \mathbb{1}\{x_i \in I\}$.

Algoritme: Empirical Risk Minimization (ERM)

Het paper presenteert een efficiënt algoritme om het interval te vinden dat $\hat{\Phi}_S(I)$ maximaliseert.

1. Berekening van scores: Bereken voor elk steekproefpunt $x_i$ de waarde $l(x_i)$ op basis van de bekende intervallen van de $n$ stemmers.
2. Sorteren: Sorteer de steekproefpunten zodat $x_{(1)} \leq x_{(2)} \leq ... \leq x_{(m)}$.
3. Maximum Subarray Sum: Het probleem reduceert tot het vinden van een subarray in de gesorteerde scores die de maximale som oplevert. Dit wordt opgelost met Kadane's algoritme.
   • Complexiteit: Met een naive benadering is dit $O(nm + m \log m)$. Met een "sweep-line" algoritme kan dit worden geoptimaliseerd naar $O((n+m) \log(n+m))$.
4. Output: Het interval $[x_{(j^*)}, x_{(k^*)}]$ dat de maximale som oplevert.

Theoretische Analyse (PAC-Leren)

Het paper levert Probably Approximately Correct (PAC) garanties voor het ERM-algoritme.

• Pseudo-dimensie: De complexiteit van de functieklasse wordt bepaald door de pseudo-dimensie ($Pdim$). Het paper bewijst dat de pseudo-dimensie van de functieklasse $G = \{l(x)\mathbb{1}\{x \in R\}\}$ gelijk is aan 2.
• Steekproefcomplexiteit: Er wordt een bovengrens afgeleid voor het aantal benodigde steekproeven $m$ om met waarschijnlijkheid $1-\delta$ een foutmarge $\epsilon$ te garanderen. De complexiteit is $O(\frac{n^2}{\epsilon^2} (\ln \frac{n}{\epsilon} + \ln \frac{1}{\delta}))$. Dit betekent dat het algoritme theoretisch gegarandeerd goed presteert met een redelijk aantal steekproeven.

3. Experimentele Resultaten

De auteurs hebben experimenten uitgevoerd met synthetische data (100 stemmers, verschillende verdelingen zoals Uniform, Truncated Normal en Exponentieel).

1. Dichtheid van de theoretische grens:
   • De experimenten tonen aan dat in de praktijk veel minder steekproeven nodig zijn dan de theoretische bovengrens suggereert om een bijna optimaal consensusgebied te vinden.
2. Strategieën voor query-reductie:
   • Minder stemmers per punt: Als men slechts een fractie van de stemmers vraagt om hun oordeel over elk punt, daalt de kwaliteit van het gevonden gebied snel. Dit komt doordat de intervallen van individuele stemmers in de synthetische data onafhankelijk zijn.
   • Intelligente queries (Actief leren): In plaats van minder stemmers te vragen, kunnen stemmers strategisch worden gevraagd over een subset van punten.
     • Methode: Gebruik een binaire zoekopdracht (binary search) voor elke stemmer om de randen van hun goedkeuringsinterval te vinden.
     • Resultaat: Deze aanpak reduceert het aantal benodigde queries per stemmer drastisch (bijv. van 100.000 punten naar slechts ~30 queries per stemmer) terwijl de kwaliteit van het gevonden consensusgebied behouden blijft.

4. Belangrijkste Bijdragen

1. Formele definitie: Een nieuwe definitie van consensus die niet alleen kijkt naar goedkeuring, maar ook naar de salience (frequentie/verdeling) van de onderwerpen via een onderliggende kansverdeling.
2. Efficiënt algoritme: Een $O((n+m) \log(n+m))$ algoritme voor het vinden van het optimale interval in 1D, gebaseerd op Kadane's algoritme.
3. PAC-theorie: Het afleiden van steekproefcomplexiteitsgrenzen gebaseerd op een pseudo-dimensie van 2, wat theoretische garanties biedt voor de prestaties.
4. Praktische validatie: Experimenten die aantonen dat het aantal queries aanzienlijk kan worden gereduceerd door slimme, actieve query-strategieën (binaire zoekopdracht) in plaats van willekeurige steekproeven.

5. Betekenis en Toekomstperspectief

Dit werk vormt een theoretisch fundament voor het verbeteren van online deliberatieplatforms.

• Toepassing: Het biedt een wiskundig onderbouwde manier om "gemeenschappelijk grond" te vinden dat relevant is voor het debat, in plaats van alleen triviaal eensgezinde punten.
• Toekomstig werk:
  • Uitbreiding naar actief leren om stemmers strategisch te bevragen.
  • Uitbreiding naar hogere dimensies (bijv. 2D of 3D ruimtes voor complexere tekst-embeddings).
  • Toepassing op AI-uitlijning (AI Alignment), waarbij consensusintervallen kunnen worden gebruikt om filters te creëren voor veilige AI-generatie of om beloningssystemen in Reinforcement Learning from AI Feedback (RLAIF) te informeren.
  • Validatie op real-world datasets van platforms zoals Pol.is.

Kortom, het paper combineert machine learning-theorie (PAC-learning) met sociale keuzetheorie om een robuuste en efficiënte methode te bieden voor het vinden van consensus in complexe menigteruimtes.