Denne artikkelen presenterer matematikken bak valgomater. Den består av tre hoveddeler:

• Del 1: Valgomater og geometri
• Del 2: Hvordan forklarer en valgomat resultatene?
• Del 3: Hvordan bør en valgomat presentere spørsmål for brukeren?

Artikkelen begynner på lavt matematisk nivå og blir progressivt mer krevende. En fordel med dette er at det er noe å lære for alle, uansett nivå. Ulempen er at artikkelen ikke har én tydelig målgruppe.

PS: I 2023 visualiserte jeg partiene i kommunevalget. Fokuset i den artikkelen var innsikt i partienes politikk. Denne artikkelen retter seg mer mot design av valgomater.

PSS: Idéene i denne artikkelen er implementert i min egen Valgomat for Stortingsvalget 2025.

Del 1: Valgomater og geometri

Meninger og matriser

For å lage en valgomat spør man politiske partier hvor enige de er i ulike påstander. Resultatet kvantifiseres ved at svar som “Helt enig!” blir oversatt til tall. Svarene kan deretter visualiseres i en tabell med en rad per påstand og en kolonne per parti. Nedenfor er “Helt enig” oversatt til \(2\) og “Helt uenig” oversatt til \(-2\).

Tabellen utgjør en matrise \(X\). Radene og kolonnene har en geometrisk tolkning som vektorer. En vektor er en liste med tall, e.g. \((1, 2)\), og kan tolkes geometrisk som en pil eller som et punkt.

Påstander og partier

Påstander som vektorer

For å visualisere påstander og partier som vektorer må vi holde oss til to eller tre dimensjoner. Høyere dimensjoner lar seg ikke visualisere.

La oss studere geometrisk hva partiene SV og Sp mener om et utvalg påstander.

Oppe til høyre i figuren finner vi påstander som begge partiene er enige i. Nede til høyre finner vi påstander som SV er enige i, men som Sp er uenige i. Vi kan gjøre tilsvarende observasjoner for de to andre kvadrantene.

Hvilke påstander er gode og dårlige?

En god påstand lar oss skille partiene fra hverandre:

• I figuren ovenfor er “Bygg jernbane nordover til Tromsø” en dårlig påstand. Uansett om du er enig eller uenig, avklarer ikke påstanden hvilket av de to partiene du er nærmest politisk. Trivielle påstander, som “Et rettferdig samfunn er bra”, er alle partiene enige i. Derfor gir de heller ingen informasjon. Det samme gjelder trivielle påstander som alle partiene er uenige i, for eksempel “Fylkeskommunen bør avskaffes” i figuren ovenfor.
• “Dropp ferjefri E39 langs Vestlandet” er en god påstand fordi den diskriminerer mellom partiene. Om du er enig ligger du nærmere SV politisk. Er du derimot uenig ligger du nær Sp.

I to dimensjoner (to partier) er påstander gode dersom de ligger langt fra underrommet som spennes av vektoren \(\boldsymbol{e} = (1, 1)\), altså den diagonale linja \(y=x\). På slutten av denne artikkelen skal vi generalisere denne idéen for å konstruere en algoritme som finner en god rekkefølge å stille spørsmål på.

Partier som vektorer

Ovenfor betraktet vi radene (påstandene) i tabellen som vektorer. La oss nå se på det komplementære vektorrommet der kolonnene (partiene) er vektorer. Vi velger to tilfeldige påstander: en om ulv og en om statens eierskap i bedrifter.

To partier ligner hverandre dersom de ligger nær hverandre i meningsrommet. Vi kan for eksempel måle avstand som distanse på den horisontale aksen pluss distanse på den vertikale aksen.

• Partiene R og AP er nær hverandre. Distansen er \(0 + 1 = 1\).
• Partiene R og V er langt fra hverandre. Distansen er \(3 + 4 = 7\).

Distansen i dette rommet er nøkkelen til hvordan en valgomat avgjør hvilke partier du er mest enig med når du tar valgomaten. Det er dette vi nå skal ta for oss i del 2.

Del 2: Hvordan forklarer en valgomat resultatene?

Forklaring: rangering av partiene etter avstand

Ovenfor så vi at partienes likhet kan kvantifiseres ved å se på avstanden mellom partiene. Vi visualiserte dette i to dimensjoner, men beregningen er den samme i et vilkårlig antall dimensjoner.

Her er en matrise med tallene fra den første figuren i denne artikkelen:

Hvis du tar valgomaten og dine meninger er vektoren \(\boldsymbol{y} = (-1, -2, 2, -2, 0, 0)\), så blir din avstand til AP \(13\), Sp \(14\), Frp \(5\) og H \(4\). Du ligger med andre ord sannsynligvis på høyresiden politisk, og bør vurdere å stemme Frp eller H.

Distansen \(d_j\) mellom dine meninger \(\boldsymbol{y}\) og et parti \(j\) sine meninger er gitt av summen av avstandene mellom hver påstand \(i\):

Avstander, \(p\)-normer og vekting

Vi kan generalisere til en vilkårlig \(p\)-norm og legge til en vekting \(w_i\):

Vektene \(w_i\) er gjerne lik \(1\) for de fleste påstander, mens \(w_i = 2\) for kjernesaker eller saker som er spesielt viktige for deg. For saker der du ikke har noen mening kan vi sette \(w_i = 0\). Verdien som velges for \(p\) er avhengig av hvordan man vil måle distanse.

Dersom du mener at \(\boldsymbol{y}\) er nærmere partiet \(A\) i eksempelet nedenfor bør du velge \(p=2\). Mener du derimot at \(\boldsymbol{y}\) er nærmere \(B\) bør du velge \(p=1\).

Dette er en subjektiv vurdering, og personlig lener jeg mot \(p=1\). Det samme gjør både NRK og VG; begge bruker \(p=1\) i sine valgomater.

Beregningene resulterer til slutt i en liste av partier, sortert etter distanse:

1. H   (avstand 4 )
2. Frp (avstand 5 )
3. AP  (avstand 13)
4. Sp  (avstand 14)

En slik liste, sortert etter avstand, er én mulig måte å forklare brukerens resultater på. Men det er ikke den eneste; neste seksjon tar for seg en annen type forklaring.

Forklaring: Ditt standpunkt som en kombinasjon av partienes standpunkter

Partienes vektorer setter retning i rommet av meninger. Etter å ha tatt en valgomat får du også en plassering i dette rommet.

I figuren ovenfor er ditt standpunkt \(\boldsymbol{y} = (1, -2)\).

Én måte å nå ditt standpunkt på med vektorregning er å ta MDGs standpunkt og legge på KrFs. Dette kan observeres geometrisk i figuren ovenfor, eller algebraisk:

Utkast til optimeringsmodell

Her er en alternativ idé til distansebasert forklaring: vi uttrykker ditt standpunkt som en kombinasjon av partienes standpunkter. Vi leter da etter en kombinasjon av partier som beskriver deg ved at de tar oss så nært ditt standpunkt som mulig. Med andre ord er vi på jakt etter en vektor \(\boldsymbol{\beta}\) som løser optimeringsproblemet

Denne modellen har noen praktiske utfordringer:

• Den tillater kompliserte forklaringer i form av lange vektorer \(\boldsymbol{\beta}\). For eksempel kan vi nå frem til \(\boldsymbol{y}\) ved den lineære kombinasjonen
  \begin{align} \text{V} + \text{R} + \text{H} + \text{Ap}  + \text{MDG} = \boldsymbol{y}. \end{align}
• Modellen tillater negative retninger fordi \(\boldsymbol{\beta}\) kan bestå av negative tall. Dette er vanskelig å tolke. For eksempel er \(-R = \boldsymbol{y}\) i eksempelet ovenfor, men du ønsker naturligvis å vite hvem du er enig med, heller enn å få vite at du er uenig med Rødt.
• Modellen tillater forklaringer der summen av partienes bidrag \(\boldsymbol{\beta}\) overskrider \(1\). Dette er tilfellet i \(\text{MDG} + \text{KrF} = \boldsymbol{y}\) og i den lange forklaringen ovenfor. Igjen er det vanskelig å tolke et slikt svar.

Alle disse problemene kan løses om vi begrenser oss til konvekse kombinasjoner.

Endelig optimeringsmodell

Vi fikser problemene til modellen ovenfor ved å utvide den. Heller enn å leter etter en hvilken som helst lineær kombinasjon av partier, leter vi etter den korteste konvekse kombinasjonen:

Begge noremen ovenfor er \(2\)-normer. Setter vi \(\alpha = \epsilon\) (et lite positivt tall) i regulariseringsleddet, så vil modellen foretrekke løsninger der elementene i \(\boldsymbol{\beta}\) jevnt over er små. Dersom \(\alpha \to \infty\) så velges \(\boldsymbol{\beta} \propto \boldsymbol{1}\), dersom \(\alpha = -\epsilon\) vil modellen foretrekke løsninger som bruker så få partier som mulig, og dersom \(\alpha \to -\infty\) er vi tilbake til en typisk valgomat som velger ett parti. Merk at når \(\alpha < 0\) så er ikke problemet konvekst. Vi setter \(\alpha = \epsilon\) i resten av artikkelen.

De to bibetingelsene på \(\boldsymbol{\beta}\) er definisjonen på en konveks kombinasjon, og gjør at vi unngår negative retninger og summer som overskrider \(1\). Summen \(\sum_j \beta_j\) må være lik \(1\), heller enn mindre enn \(1\), fordi dersom \(\boldsymbol{y} = (0, 1)\), \(A = (0, 1)\) og \(B = (0, 2)\) så forventer vi \(\boldsymbol{\beta} = (1, 0)\) som svar, ikke \(\boldsymbol{\beta} = (0, 0.5)\).

Med \(2\)-norm på begge leddene i objektivfunksjonen blir løsningen på optimeringsproblemet:

Om du går tilbake til figuren og sammenligner geometrien med denne løsningen, ser du at løsningen er fornuftig. Når det er sagt er det ingen absolutt fasit i matematisk modellering og andre variasjoner av en slik modell kan være hensiktsmessige.

Optimeringsmodellen på et større eksempel

La oss kjøre optimeringsmodellen på samme eksempel som tidligere:

Svaret er gitt nedenfor, og samsvarer godt med rangeringen som vi fikk tidligere.

1. H   (51 %)
2. Frp (45 %)
4. Sp  ( 4 %)
3. AP  ( 0 %)

Forskjellen på distansebasert og kombinasjonsbasert forklaring

Vi har sett to måter å forklare en brukers resultater på i en valgomat:

1. Distansebasert forklaring - rangerer partiene etter distanse fra brukeren. Svarer på spørsmålet “Hvilket enkeltparti er nærmest meg?”
2. Kombinasjonsbasert forklaring - brukeren uttrykkes som den nærmeste konvekse kombinasjonen av partiene. Svarer på spørsmålet “Hvilken koalisjon av partier er nærmest meg?”

Forskjellen mellom forklaringene er illustrert i figuren nedenfor.

• Distansebasert forklaring sier at \(\boldsymbol{y}\) er nærmest \(B\), deretter \(A\) og til slutt \(C\). Distansebasert forklaring er innbyrdes uavhengig; avstanden til \(B\) påvirker ikke avstanden til \(A\). Dersom \(B\) hadde forsvunnet ville avstanden til \(A\) vært uendret.
• Kombinasjonsbasert forklaring uttrykker standpunktet \(\boldsymbol{y}\) som en konveks kombinasjon. Svaret i figuren ovenfor blir \(\boldsymbol{\beta} = (\beta_A, \beta_B, \beta_C) = (0, 0.7, 0.3)\). Optimeringsmodellens forklaring er innbyrdes avhengig. Dersom \(B\) hadde forsvunnet ville forklaringen lent seg på \(A\), men når \(B\) finnes trengs ikke \(A\) i det hele tatt for å forklare \(\boldsymbol{y}\).

Figuren nedenfor viser et eksempel der forklaringene blir helt ulike.

Målt i distanse er \(C\) nærmere \(\boldsymbol{y}\) enn både \(A\) og \(B\). Likevel forklares \(\boldsymbol{y}\) ved hjelp av \(\boldsymbol{\beta} = (\beta_A, \beta_B, \beta_C) = (0.5, 0.5, 0)\) uten å bruke \(C\). Korteste distanse forteller deg hvilket enkeltparti som er nærmest. Optimeringsmodellen forteller deg hvilken kombinasjon av partier som står deg nærmest.

Del 3: Hvordan bør en valgomat presentere spørsmål for brukeren?

I denne seksjonen presenterer vi en algoritme som velger påstander som diskriminerer godt mellom partiene. Det kan være to grunner til at man ønsker dette:

• Man skal bruke et utvalg påstander. Om partiene har svart på mange spørsmål, ønsker vi gjerne å begrense oss til et utvalg. Hvordan velger vi gode påstander som differensierer mellom partiene?
• Tidlig avslutning. Man ønsker at brukeren skal kunne avslutte valgomaten etter et vilkårlig antall spørsmål. Hvordan garanterer vi at brukeren har blitt presentert for et allsidig sett med påstander?

For å motivere algoritmen begynner vi med å se på samme eksempel som tidligere i artikkelen.

Spør vi om jernbane til Tromsø eller om fylkeskommunen bør avskaffes, innhenter vi ingen informasjon fordi brukerens svar ikke diskriminerer mellom partiene. Underrommet som spennes av vektoren \(\boldsymbol{e} = (1, 1)\) består av slike trivielle påstander. Den beste påstanden å presentere for brukeren er derimot “Dropp ferjefri E39 langs Vestlandet”, ettersom denne påstanden ligger lengst i fra \(\operatorname{span} (\{ \boldsymbol{e} \} )\).

Algoritme for å velge påstander i rekkefølge

La oss generalisere fra to dimensjoner til et vilkårlig antall dimensjoner:

• Start med det trivielle underrommet som spennes av påstanden \(\boldsymbol{e} = (1, 1, \ldots, 1)\).
• Den første påstanden som velges er den som er lengst fra \(\operatorname{span} (\{ \boldsymbol{e} \} )\). Dette er \(\boldsymbol{v}_1 = \arg \max_j \| P_S \boldsymbol{v}_j - \boldsymbol{v}_j \|_2\), der \(P_S\) er en projeksjonsmatrise som projiserer en vektor på \(S\). Formelen for en slik projeksjonsmatrise er \(P_S = S S^{+} = S (S^T S)^{-1} S^T\), der kolonnene i matrisen \(S\) er vektorene som spenner rommet vi ønsker å projisere på (her bare \(\boldsymbol{e}\)).
• Den neste påstanden som velges skal være langt fra både det trivielle underrommet \(\boldsymbol{e}\), og langt fra den forrige valgte påstanden \(\boldsymbol{v}_1\). Vi velger altså påstanden som er lengst fra \(\operatorname{span} (\{ \boldsymbol{e}, \boldsymbol{v}_1 \} )\). I matematisk notasjon blir dette \(\boldsymbol{v}_2 = \arg \max_j \| P_S \boldsymbol{v}_j - \boldsymbol{v}_j \|_2\), der \(S\) i denne iterasjonen er en matrise med kolonner \(\boldsymbol{e}\) og \(\boldsymbol{v}_1\).
• Slik fortsetter vi og velger påstander som er lengst fra de vi allerede har valgt. Dersom \(\operatorname{rank} \operatorname{span} (\{ \boldsymbol{e}, \boldsymbol{v}_1, \ldots, \boldsymbol{v}_n \} )\) blir lik dimensjonaliteten til rommet (antall partier), så er alle gjenværende påstander i rommet. Da blir distansen \(\| P_S \boldsymbol{v}_j - \boldsymbol{v}_j \|_2 \approx 0\) for alle gjenværende påstander \(\boldsymbol{v}_j\). Løsningen er å behandle de valgte påstandene som en FIFO-kø: vi fjerner den første valgte påstanden \(\boldsymbol{v}_1\) og prøver på nytt. Da er neste påstand vi velger alltid langt fra de siste valgte påstandene.

Python-kode for algoritmen er vedlagt nederst i artikkelen. Figuren nedenfor illustrerer konseptet i tre dimensjoner. Den neste påstanden som velges er alltid den som er lengst i fra rommet som spennes av den trivielle retningen og tidligere valgte påstander.

Resultater - dårlige påstander

La oss se på et eksempel med påstander som innbyrdes ligner på hverandre.

De første to påstandene er veldig like. Den tredje påstanden om Erna er på motsatt side av vektorrommet, men gir likevel ikke mye ny informasjon fordi det er nær rommet som spennes av de første to spørsmålene. Spørsmålet om Erna avdekker altså lite ny informasjon, på tross av at påstanden er på motsatt side av vektorrommet.

Resultater - gode påstander

Her er et utvalg påstander som er ulike hverandre, avdekket av algoritmen ovenfor.

Den første påstanden er langt fra triviell, fordi halvparten av partiene er uenige og den andre halvparten er enige. Den andre påstanden er ulikt besvart av seks partier, og skiller seg både fra den trivielle påstanden og den første påstanden. Slik fortsetter algoritmen med å velge påstander som hele tiden er annerledes enn det brukeren av valgomaten har blitt presentert for.

Oppsummering og referanser

Valgomater kvantifiserer politiske meninger. Partienes svar kan representeres som en matrise, der radene (påstander) og kolonnene (partier) kan tolkes vektorer. En slik geometrisk tolkning gir oss verdifull innsikt: vi kan definere hva det vil si at en person er nær et parti og vi kan formalisere hva det vil si at en påstand diskriminerer mellom partier.

Idéen som å se på partier som vektorer og rangere brukeren etter nærhet er rimelig åpenbar, og for kommunevalget 2019 brukte NRK \(p=1\) som metrikk. (At NRKbetas artikkel pakker ungdomsskolematematikk inn i fraser som “forklar utregningen for meg som ikke har matteskrekk” og “Jeg får vondt i hodet!” er sørgelig.) Idéen om å beskrive en bruker som en konveks kombinasjon av partier er min egen. I praksis er det vanskeligere å implementere i kode, samt mer krevende å forstå for en gjennomsnittlig bruker. Enkle algoritmer har iboende verdi og distanse-beregning gir en enkel og forståelig forklaring.

Idéen om å se på påstander som vektorer og velge ut påstander som er langt fra hverandre er min egen. Inspirasjonen kommer fra QR-dekomposisjon med pivotering, som er en algoritme for å ortogonalisere en matrise. Pivot-kolonnene i QR kan sees på som en grådig approksimasjon av D-optimalitet i optimal eksperimentdesign, som maksimerer volumet av en høydimensjonell parallellepiped. Forskjellene mellom min algoritme og QR-dekomposisjon er at (1) vi alltid holder oss borte fra den trivielle påstanden \(\boldsymbol{e} = \boldsymbol{1}\) og at (2) vi bruker en FIFO-kø.

Denne artikkelen fokuserte mest på matematikk, men en valgomat må selvsagt ha politisk relevante påstander, godt grafisk design, potensielt mulighet for å hoppe over påstander eller vekte påstander opp, subjektive analyser av resultatene, og så videre.

Kode

Her er en enkel implementasjon av algoritmen som finner påstander som er langt fra hverandre. Jeg har ikke vektlagt kjøretid, numerisk stabilitet, caching av beregninger, etc. Koden er absolutt god nok for bruksområdet, men for større datasett bør man skrive om.

import collections  # Python 3.12
import numpy as np  # NumPy 2.1.3


def away_from_last_k(A, k=None, verbose=False):
    """Yields the column indices of A that are as far away from a continually
    updated subspace spanned by (1, 1, 1, ...) and a First-In-First-Out (FIFO)
    queue of length k. When a column index is yielded, it is added to the queue.

    Parameters
    ----------
    A : np.ndarray
        A matrix (2D array) with columns [v1 | v2 | ... ].
    k : int, optional
        Numbers of elements to keep in the FIFO queue. None means no limit.
    verbose : bool, optional
        Whether to print information. The default is False.

    Examples
    --------
    >>> A = np.array([[3, 0, 0], [0, 2, 0], [0, 0, 1], [2.5, 0, 0]]).T
    >>> list(away_from_last_k(A, k=None))
    [0, 1, 3, 2]
    >>> list(away_from_last_k(A, k=0)) #  Distance from span({(1, 1, 1)}) only
    [0, 3, 1, 2]
    >>> list(away_from_last_k(A, k=1))
    [0, 1, 3, 2]
    """
    subspace = collections.deque([], maxlen=k)  # Vectors in FIFO subspace
    ones = np.ones(A.shape[0])  # Vector of ones, always in subspace
    remaining = dict(enumerate(A.T))  # Remaining column indices of A

    def distance_from_subspace(tuple_):
        idx, v = tuple_
        S = np.vstack([ones] + list(subspace)).T  # Full space as col. mat.
        P_S = S @ np.linalg.pinv(S)  # Projection matrix onto span(S)
        return np.linalg.norm(P_S @ v - v)  # Distance between v and span(S)

    while remaining:
        if verbose:
            inds = list(remaining.keys())
            print(f"\nCol idx of {len(remaining)} remaining vectors: {inds}")
            print(f"Vectors in subspace (excl. ones): {len(subspace)}")

        # Get idx of col vector furthest from S = [ones | subspace]
        idx, _ = max(remaining.items(), key=distance_from_subspace)
        maxdist = distance_from_subspace((idx, remaining[idx]))
        if np.isclose(maxdist, 0):
            if verbose:
                print("Distance was 0. Popping from subspace.")
            subspace.popleft()
            continue

        if verbose:
            print(f"Col idx {idx} furthest from subspace. Dist: {maxdist:.6f}")
        subspace.append(remaining.pop(idx))
        yield idx