Fritt skolevalg del 3 - Segregering

Generelt om “fritt skolevalg”

Det har gått en debatt rundt “fritt skolevalg” i det siste. Regjeringen har et forslag på høring som omhandler å innføre karakterbasert opptak i alle fylker. Det er en del meninger blant politikere og andre rundt ulike modeller.

Uansett hvilket system som ender opp med å bli brukt, er det til slutt en modell som vil fordele elevene til skoler. Debatten mangler en mer konkret tilnærming til modeller – politikerne har ønsker uten å nødvendigvis ha forståelse for hva som kan gjennomføres og hva implikasjonene av en modell kan være.

Første artikkel om “fritt skolevalg” handlet om geografi, og den andre tok for seg karakterer. I denne artikkelen fokuserer vi på segregering.

I denne artikkelen: Segregering

Forskere ved Oslo Met har testet fem ulike modeller for inntak i Oslo, og sier:

Det er ikke opplagt hvilken modell som er best. Hvis målet er å unngå segregering, er loddtrekning best.” [kilde]

Loddtrekning er best av modellene som er testet, men det er minst to utfordringer:

  • Loddtrekning skaper mindre segregering fordi det fører til mer variasjon av elever med høyt og lavt snitt i skolene. Loddtrekning jobber ikke aktivt med å minske segregering.
  • Loddtrekning er en grådig algoritme som fordeler elever én etter én uten å se på helheten. Loddtrekning ofrer elevenes ønsker som helhet til fordel elever med gode lodd.

Når loddtrekning skaper lite segregering, er det et resultat av tilfeldigheter i rekkefølgen på loddene. Dersom målet er lav segregering, hvorfor ikke teste en modell som optimerer for lav segregering direkte?

I denne artikkelen gjør vi nettopp dette. Vi kommer til å se at en slik modell både resulterer i flere oppfylte ønsker og lavere segregering.

Innhold

Definisjon av segregering

Vi legger følgende sitat, fra SV-leder Audun Lysbakken, til grunn for vår tolkning av segregering (eller sosial ulikhet) i skolen:

Vi tror ikke på et system som samler elever med lave karakterer i samme klasserom. Det forsterker forskjellene i samfunnet vårt. Vi vil ha mindre ulikhet, ikke mer.” [kilde]

Vår definisjon av segregering er enkel: segregeringen er lav dersom variansen til gjennomsnittskarakterene i skolene er lav.

Med denne definisjonen er en fordeling som fører til at gjennomsnittskarakterene i tre ulike skoler blir \((4, 4, 4)\) helt uten segregering. Hvis snittkarakterene er \((2, 4, 6)\) har vi relativt stor segregering.

Formalisering av optimeringsproblemet

Vi formulerer fordeling av elever på skoler som et optimeringsproblem med to målsetninger: (1) lav segregering og (2) høy innfrielse av elevenes prioriteringer. Dette kalles et bi-objektivt optimeringsproblem. Løsningen (fordelingen) \(X\) er definert ved hjelp av følgende variabler:

\begin{align} x_{ij}= \begin{cases} 1 \quad \text{ hvis elev } e_i \text{ er plassert på skole } s_j\\ 0 \quad \text{ hvis ikke}. \end{cases} \end{align}

Segregering

Vi regner først ut gjennomsnittskarakteren for hver skole \(s_j\) som

\begin{align} \bar{k}_j = \frac{\sum_i k_i x_{ij}}{\sum_i x_{ij}}. \end{align}

Deretter definerer vi segregering som variansen av gjennomsnittskarakterene:

\begin{align} \operatorname{segregering}(X) = \operatorname{Var}(\bar{k}_1, \bar{k}_2, \dots, \bar{k}_j, \dots). \end{align}

Definisjonen ovenfor er ikke absolutt, det finnes andre funksjoner som på en fornuftig måte kvantifiserer segregering. Beregningsmessig er det viktigste at vi bruker en funksjon av fordelingen \(X\) som kan evalueres (og derfor optimeres).

Prioriteringer

Vi antar at hver elev får oppgi tre prioriterte ønsker, og omgjør prioritetene til kostnader. Vi omgjør prioriteter til kostnader for å formulere oppgaven som et minimeringsproblem, der vi ønsker å minimere kostnaden forbundet med å plassere en elev på en bestemt skole. Med andre ord: lav kostnad betyr at eleven er blitt tildelt en skole som er høyt på ønskelisten.

Fra elevenes prioriteringer lager vi en kostnadsmatrise \(C\), der elementet \(c_{ij}\) er kostnaden forbundet med at elev \(e_i\) begynner på skole \(s_j\). Vi setter opp kostnadsmatrisen slik at:

  • Elevenes førsteprioritet har kostnad \(0\).
  • Elevenes andreprioritet har kostnad \(1\).
  • Elevenes tredjeprioritet har kostnad \(2\).
  • Alle andre skoler har kostnad \(9\).

Merk at en perfekt fordeling der alle får sin førsteprioritet gir en kostnad lik null.

Kostnaden av å ikke innfri elevenes prioriteringer er summen av hver elevs kostnader, delt på det totale antallet elever:

\begin{align} \operatorname{prioriteringer}(X) = \frac{\sum_i \sum_j c_{ij} x_{ij}}{\sum_i \sum_j x_{ij}} \end{align}

Igjen er det ikke kritisk hvordan vi formulerer dette, så lenge det er en funksjon av \(X\) som vi kan evaluere. Dersom vi ønsker å straffe tredjevalg og ikke-prioriterte skoler strengere kan vi eksempelvis erstatte kostnadene \((0, 1, 2, 9, 9, 9, \dots)\) med \((0, 1, 5, 99, 99, 99, \dots)\).

Prioriteringer som tar hensyn til karakterer

Vi kan generalisere kostnadene \(c_{ij}\) til å ta hensyn til elevenes karakterer. I del 2 (Karakterer) introduserte i rangeringen til elev \(e_i\) som \(r_i\). Rangeringen \(r_i\) er jevnt fordelt over intervallet \([0, 1]\), og sier hvor godt karaktersnittet til elev \(e_i\) er i forhold til de andre elevene. Vi definerer en ny kostnad \(c'_{ij}\) som er avhengig av rangeringen til elev \(e_i\) som:

\begin{align} \mathbf{c}'_{i \cdot} = \exp (\alpha r_i) \, \mathbf{c}_{i \cdot} \end{align}
  • Når \(\alpha=0\) er kostnaden av å ikke innfri elevenes prioriteter lik uansett elevenes karakter.
  • Når \(\alpha \to \infty\) reduseres minimering av \(\operatorname{prioriteringer}(X)\) til ren karakterbasert modell.

Vi setter \(\alpha = 0\) i denne artikkelen. I praksis kan en beslutningstaker velge en passende verdi for \(\alpha\), avhengig av hva som er målet. Eksempelvis kan \(\alpha = \ln 5\) tolkes omtrent som at “å innfri én elev med toppkarakterer sine prioriteter er like viktig som \(5\) elever med bunnkarakterer”.

Matematisk modell

Den matematiske modellen minimerer en bi-objektiv funksjon (to målfunksjoner), og er:

\begin{align} & \operatorname{minimer} && \left( \operatorname{prioriteringer}(X) , \operatorname{segregering}(X) \right) \\ & \operatorname{gitt} && \sum_i x_{ij} = K_j && \forall \, j \\ & && \sum_j x_{ij} = 1 && \forall \, i \\ & && x_{ij} \in \{0, 1\} && \forall \, (i, j) \\ \end{align}

Den første betingelsen sier at skolenes kapasiteter må fylles. Vi antar at summen av kapasitetene er lik antall elever, men modellen kan enkelt generaliseres til problemer der dette ikke er tilfellet. Den andre betingelsen sier at alle elevene må plasseres på én (og bare én) skole.

Stokastisk optimering

Modellen ovenfor er et Quadratic Mixed Integer Program (QMIP): “integer” fordi vi er ute etter heltallsløsninger for \(x_{ij}\) og “quadratic” fordi \(\operatorname{segregering}(X)\) er en kvadratisk funksjon av \(x_{ij}\).

Selv programvare som løser QMIP-problemer (såkalte solvere) er tilgjengelige, velger vi å bruke stokastisk optimering. Dette gjør vi fordi:

  • En solver vil ikke klare å finne en optimal løsning på et problem av realistisk størrelse.
  • Vi ønsker å returnere en mengde med løsninger (solvere returnerer én løsning).

Ulempene med stokastisk optimering er at:

  • Vi har ingen garanti for optimalitet (det kan finnes bedre løsninger som vi ikke finner).
  • Ulike kjøringer av algoritmen vil returnere ulike resultater.

Det samme gjelder imidlertid også for den foreslåtte loddtrekningen, derfor bør man ikke være ukomfortabel med stokastisk optimering om man er komfortabel med loddtrekning. Vi beskriver en algoritme som vi kaller populasjonsbasert søk med simulert størkning (PSMSS) som effektivt løser problemet ovenfor.

En enkel operator

Gitt at vi har en foreslått løsning \(X\), trenger PSMSS en operator som kan gjøre en liten endring i \(X\) for å teste ut en lignende løsning \(X'\). Med andre ord:

\begin{align} X' = \operatorname{operator}(X). \end{align}

Minimumskravene til en fornuftig operator er at den:

  • Lar oss utforske hele søkerommet (komposisjon kan generere alle løsninger).
  • Målfunksjonene \(\operatorname{prioriteringer}(X)\) og \(\operatorname{segregering}(X)\) gjør ingen store hopp når \(X\) endres til \(X'\).

Vi bruker en enkel operator kalt \(\operatorname{swap}\).

Operatoren \(\operatorname{swap}\) tar inn en løsning \(X\) og bytter om \(2\) tilfeldige elevers skoler. Det er fullt mulig å bruke flere operatorer, eller å lage smartere operatorer. En smartere operator kan f.eks. ha mindre sannsynlighet for å bytte klasse på elever som allerede er plassert på førstevalget. Likevel bruker vi kun \(\operatorname{swap}\), fordi denne enkle operatoren alene gjør det ekstremt godt.

Beskrivelse av algoritmen PSMSS

Gitt en løsning \(X\) bruker PSMSS operatoren \(\operatorname{swap}\) til å lage en ny løsning \(X'\):

\begin{align} X' = \operatorname{swap}(X). \end{align}

Dersom \(X'\) er bedre enn \(X\) beholder vi alltid \(X'\), men dersom \(X'\) er verre enn \(X\) beholder vi også av og til \(X'\). Sannsynligheten for at vi beholder en verre løsning reduseres etter hvert som PSMSS leter etter gode løsninger. Dette fører til at vi utforsker søkerommet i starten, og utnytter gode løsninger mot slutten av søket. Dette er kalt simulert størkning (simulated annealing).

Gitt en løsning \(X\), utfører PSMSS tre parallelle søk i tre ulike retninger:

  • Et søk prøver å minimere både \(\operatorname{segregering}(X)\) og \(\operatorname{prioriteringer}(X)\).
  • Et søk prøver kun å minimere \(\operatorname{prioriteringer}(X)\), uten å bry seg om \(\operatorname{segregering}(X)\).
  • Et søk prøver kun å minimere \(\operatorname{segregering}(X)\), uten å bry seg om \(\operatorname{prioriteringer}(X)\).

Når vi initialiserer algoritmen med en løsning \(X\), lager de tre søkene ulike stier i løsningsrommet. Dette er vist til venstre i figuren nedenfor. Søkene er mer tilfeldige i starten, fordi da godtar vi ofte løsninger som ikke er bedre. Etter hvert synker sannsynligheten for at vi godtar løsninger som ikke er bedre, og søkene jobber mer aktivt for å minimere målfunksjonene.

Figuren til høyre viser alle løsninger som har blitt funnet i den første iterasjonen.

En løsning \(X'\) dominerer \(X\) dersom (1) ingen av målfunksjonene i \(X'\) er verre enn \(X\) og (2) minst én av målfunksjonene i \(X'\) er bedre enn \(X\). Dersom \(X'\) dominerer \(X\) er det aldri noen grunn til å foretrekke \(X\) fremfor \(X'\).

Etter å ha fullført første iterasjon går PSMSS gjennom alle løsningene som er funnet og beholder de ikke-dominerte løsningene. Alle ikke-dominerte løsninger danner grunnlaget for søket i neste iterasjon.

Koden for PSMSS ser omtrent slik ut:

non_dominated_solutions = [solution] # Initial solution (e.g. random)

for search_iteration in range(100): # Main loop, with e.g. 100 iterations
    found_solutions = []
    for solution in non_dominated_solutions:
        for search_direction in search_directions:
            # Run simulated annealing with 'tweak', add found solutions
            solutions = simulated_annealing(solution, search_direction)
            found_solutions.append(solutions)

    # Update by adding solutions and removing dominated solutions
    non_dominated_solutions = update(found_solutions, non_dominated_solutions)

PSMSS returnerer til slutt en mengde løsninger som ikke er dominerte av noen andre.

Resultater på et realistisk problem

La oss sammenligne loddtrekning med PSMSS på et realistisk problem.

  • Problemet har \(500\) elever og \(5\) skoler, og alle skolene har lik kapasitet.
  • Hver skole har en popularitet, som angir sannsynligheten for at elevene plasserer den høyt.

At skolene varierer i popularitet begrenser hvor mange elever som kan få førsteønsket sitt oppfylt, og simulerer at det er konkurranse om de populære skolene.

Vi kan begynne første iterasjon i PSMSS med en tilfeldig løsning \(X\), men vi kan også være smartere. Vi løser først et min-cost flow problem og bruker det som utgangspunkt. Min-cost flow brukes her til å minimere total kostnad av prioriteringer \(\sum_i \sum_j c_{ij} x_{ij}\). Dette tilsvarer det vi gjorde i del 1 (Geografi), men da minimerte vi summen av distansene \(\sum_i \sum_j d_{ij} x_{ij}\).

Når vi starter med en min-cost flow løsning er utgangspunktet vårt en optimal fordeling med tanke på prioritetene. Halve jobben er gjort – PSMSS finner i praksis ut hvor mange av elevenes ønsker vi må ofre for lav segregering. Første iterasjon er vist i figuren nedenfor. Merk at søket starter i et punkt som er optimalt med tanke på \(\operatorname{prioriteringer}(X)\).

PSMSS evaluerer titusenvis av mulige fordelinger \(X\) per sekund. Etter hver iterasjon oppdateres settet av ikke-dominerte løsninger med nye, bedre løsninger.

Figuren nedenfor viser mengden løsninger funnet av PSMSS, sammen med \(1\,000\) loddtrekninger, \(1\,000\) tilfeldige løsninger og en karakterbasert modell. Resultatet er slående, men ikke uventet – PSMSS er betraktelig bedre enn loddtrekning. Løsningene har både lavere segregering og elevene er mer fornøyde med prioritetene.

En beslutningstaker kan velge trade-off mellom objektivene: vil man ha lav segregering går det på bekostning av prioritetene. Figuren nedenfor viser en versjon som er zoomet inn.

I velger den løsningen fra PSMSS som har lavest \(\operatorname{prioriteringer}(X)\), gitt at \(\operatorname{segregering}(X) < 0.01\). Figuren nedenfor sammenligner denne løsningen med en loddtreking og en karakterbasert modell.

Legg merke til at:

  • PSMSS får flere elever inn på første- og andrevalg. Ingen blir tilfeldig plassert.
  • Den karakterbaserte fordelingen innfrir prioritetene til de som har best karakter først. Fordi vi valgte \(\alpha = 0\) bruker PSMSS ikke elevenes karakterer på noen måte.
  • Segregeringen er klart størst i den karakterbaserte modellen. PSMSS har litt lavere segregering enn loddtrekning.

Oppsummering

Loddtrekning reduserer segregering sammenlignet med en karakterbasert modell, men loddtrekning optimerer ikke for lavere segregering direkte. Den lave segregeringen som oppstår i loddtrekningen er et resultat av tilfeldigheter.

Fordelingsproblemet kan formuleres som et bi-objektivt optimeringsproblem der man ønsker å både minimere \(\operatorname{segregering}(X)\) og \(\operatorname{prioriteringer}(X)\). Kostnaden av prioriteringene kan parametriseres ved hjelp av \(\alpha\). Når \(\alpha=0\), behandles elevene likt uansett karakter. Når \(\alpha \to \infty\), vil elevene med høyest karaktersnitt alltid få sine valg først.

Vi løser optimeringsproblemet ved hjelp av algoritmen PSMSS, som tar utgangspunkt i en min-cost flow løsning der \(\operatorname{prioriteringer}(X)\) allerede er minimert. Algoritmen er stokastisk, men (1) er man komfortabel med tilfeldigheten i loddtrekning bør man også være komfortabel med stokastisk optimering og (2) vi starter med en optimal løsning med tanke på elevenes ønsker. Vi finner i praksis minste tap av prioriteringer som vi må ofre for lavere segregering.

På simulerte data gir optimering langt bedre resultater enn loddtrekning. Dette gjelder både for segregering og prioriteringer. En beslutningstaker kan velge en verdi for \(\alpha\) som kvantifiserer villigheten til å redusere innfrielsen av ønsker for elever med lavt karaktersnitt for de med høyt karaktersnitt. PSMSS leverer en mengde ikke-dominerte løsninger, og en beslutningstaker kan velge i hvilken grad man ønsker å se bort fra elevenes ønsker til fordel for lavere segregering.

Optimeringsmodellen vil levere bedre resultater enn alle andre foreslåtte modeller med hensikt om å redusere segregering, fordi det er den eneste modellen som direkte optimerer for lav segregering. Den tillater også parametrisering av hvor mye karakterer skal telle.

I del 2 av artikkelserien drøftet vi strategisikkerhet. Optimeringsmodellen er teknisk sett ikke strategisikker. En elev som har informasjon om andres prioriteringer og modellens parametervalg vil kunne gjøre strategiske valg, men i praksis vil det være krevende for en elev å manipulere valgene sine for å oppnå en fordel.

Notater og referanser

  • Både definisjonen av \(\operatorname{segregering}(X)\) og \(\operatorname{prioriteringer}(X)\) er åpen for debatt. Det er også mulig å optimere flere enn to målfunksjoner, men da blir modellen mindre ryddig.
  • Stokastisk optimering er et fagfelt med mange algoritmer og mye terminologi. Algoritmen vi brukte ble laget spesifikt for å løse dette problemet uten å måtte skrive alt for mye kode. Det enkleste er ofte det beste, og en mer avansert algoritme ville nok ikke levert betraktelig bedre resultater på dette problemet.
  • Fordeling av elever i klasser er også et optimeringsproblem. I artikkelen “Optimizing the Assignment of Students to Classes in an Elementary School” av Krauss et al. benyttes en evolusjonsbasert algoritme. Med små endringer vil PSMSS kunne løse dette problemet. Vi kan eksempelvis optimere for at (1) elever blir plasser med venner, (2) klassene ikke blir segregerte med hensyn på karakterer og (3) klassene ikke blir segregerte med hensyn på kjønn. Her burde alle skoler vurdere å bruke optimering som utgangspunkt.
  • Boka “Essentials of Metaheuristics” av Sean Luke er en lettleselig introduksjon til simulert størkning, populasjonsbaserte metoder og stokastisk optimering generelt.

En stor takk til Sean Meling Murray og Gunvor Lemvik for verdifulle innspill på artikkelen.