Afstand grondverzet || Wiskunde ∩ Programmeren

Probleem: Bereken de afstand tussen punten met onzekere locaties (gegeven door monsters, of verschillende waarnemingen, of clusters).

Als ik bijvoorbeeld de volgende drie “punten” in het vlak heb, zoals aangegeven door hun kleuren, wat is dan dichterbij, blauw naar groen of blauw naar rood?

Het is niet duidelijk en er spelen meerdere factoren een rol: de rode punten hebben minder monsters, maar we kunnen zekerder zijn over de positie; de blauwe punten zijn minder zeker, maar het niet-blauwe punt dat het dichtst bij een blauw punt ligt, is groen; en de groene punten zijn even plausibel ‘dicht bij rood’ als ‘dichtbij blauw’. De massacentra van de drie monstersets liggen dicht bij een gelijkzijdige driehoek. In ons voorbeeld overlappen de “punten” elkaar niet, maar dat zou natuurlijk wel kunnen. En in het bijzonder zou er waarschijnlijk een afstand niet nul moeten zijn tussen twee punten waarvan de monstersets hetzelfde massamiddelpunt hebben, zoals hieronder. De afstand kwantificeert de onzekerheid.

Dit alles wil zeggen dat het niet duidelijk is hoe je een afstandsmaatstaf definieert die consistent is met perceptuele ideeën over wat geometrie en afstand zouden moeten zijn.

Oplossing (grondverzetmachine afstand): Behandel elke steekproef $ A$ die overeenkomt met een “punt” als een discrete kansverdeling, zodat elke steekproef $ x \in A$ een waarschijnlijkheidsmassa $ p_x = 1 / |A|$ heeft. De afstand tussen $ A$ en $ B$ is de optionele oplossing voor het volgende lineaire programma.

Elke $ x \in A$ komt overeen met een hoop aarde met een hoogte van $ p_x$, en elke $ y \in B$ komt overeen met een gat met een diepte van $ p_y$. De kosten voor het verplaatsen van een eenheid vuil van $ x$ naar $ y$ zijn de Euclidische afstand $ d(x, y)$ tussen de punten (of welke hipster-metriek je ook wilt gebruiken).

Laat $ z_{x, y}$ een reële variabele zijn die overeenkomt met de hoeveelheid vuil die moet worden verplaatst van $ x \in A$ naar $ y \in B$, met kosten $ d(x, y)$. Dan zijn de beperkingen:

• Elke $ z_{x, y} \geq 0$, dus vuil beweegt alleen van $ x$ naar $ y$.
• Elke stapel $ x \in A$ moet verdwijnen, dwz voor elke vaste $ x \in A$, $ \sum_{y \in B} z_{x,y} = p_x$.
• Op dezelfde manier moet elk gat $ y \in B$ volledig gevuld zijn, dwz $ \sum_{y \in B} z_{x,y} = p_y$.

Het doel is om de kosten hiervan te minimaliseren: $ \sum_{x, y \in A \times B} d(x, y) z_{x, y}$.

In Python, met behulp van de ortools-bibliotheek (en een paar docstrings en standaard importinstructies weggelaten, volledige code op Github):

from ortools.linear_solver import pywraplp

def earthmover_distance(p1, p2):
    dist1 = {x: count / len(p1) for (x, count) in Counter(p1).items()}
    dist2 = {x: count / len(p2) for (x, count) in Counter(p2).items()}
    solver = pywraplp.Solver('earthmover_distance', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    variables = dict()

    # for each pile in dist1, the constraint that says all the dirt must leave this pile
    dirt_leaving_constraints = defaultdict(lambda: 0)

    # for each hole in dist2, the constraint that says this hole must be filled
    dirt_filling_constraints = defaultdict(lambda: 0)

    # the objective
    objective = solver.Objective()
    objective.SetMinimization()

    for (x, dirt_at_x) in dist1.items():
        for (y, capacity_of_y) in dist2.items():
            amount_to_move_x_y = solver.NumVar(0, solver.infinity(), 'z_{%s, %s}' % (x, y))
            variables((x, y)) = amount_to_move_x_y
            dirt_leaving_constraints(x) += amount_to_move_x_y
            dirt_filling_constraints(y) += amount_to_move_x_y
            objective.SetCoefficient(amount_to_move_x_y, euclidean_distance(x, y))

    for x, linear_combination in dirt_leaving_constraints.items():
        solver.Add(linear_combination == dist1(x))

    for y, linear_combination in dirt_filling_constraints.items():
        solver.Add(linear_combination == dist2(y))

    status = solver.Solve()
    if status not in (solver.OPTIMAL, solver.FEASIBLE):
        raise Exception('Unable to find feasible solution')

    return objective.Value()

Discussie: Ik heb vaak over deze metriek gehoord als een manier om kansverdelingen te vergelijken. Het komt bijvoorbeeld naar voren in een invloedrijk artikel over eerlijkheid bij machinaal leren, en in een paar andere CS-theorieartikelen over distributietesten.

Je zou je kunnen afvragen: waarom zouden we geen andere maten van ongelijkheid gebruiken voor kansverdelingen (Chi-kwadraatstatistiek, Kullback-Leibler-divergentie, enz.)? Eén antwoord is dat deze andere metingen alleen nuttige informatie opleveren voor paren verdelingen met dezelfde ondersteuning. Een voorbeeld uit een lezing van Justin Solomon maakt kort en bondig duidelijk wat grondverzetafstand oplevert

Waarom modelleren we de steekproeven niet gewoon met bijvoorbeeld een normale verdeling, en berekenen we vervolgens de afstand op basis van de parameters van de verdelingen? Dat is mogelijk en zorgt in feite voor een potentieel efficiëntere techniek, maar je verliest hierdoor wel wat informatie. Als u negeert dat uw gegevens mogelijk niet bij benadering normaal zijn (het kan enige kromming hebben), krijgt u met de Earthmover-afstand puntsgewijze details over hoe elk gegevenspunt de uitkomst beïnvloedt.

Dit soort aandacht voor detail kan in bepaalde situaties erg belangrijk zijn. Eén waar ik de laatste tijd veel aandacht aan heb besteed, is het probleem van het bestuderen van gerrymandering vanuit een wiskundig perspectief. Justin Solomon van MIT is een kampioen van de Earthmover-afstand (zie zijn fascinerende lezing hier voor meer informatie, met dia’s), wat slechts één onderwerp is in een veld dat ‘optimaal transport’ wordt genoemd.

Dit kan nuttig zijn bij herverdeling, vanwege de aard van het herverdelingsprobleem. Zoals ik eerder schreef, zitten discussies over herverdeling boordevol geometrie – of op zijn minst geometrisch klinkende taal – en zijn mensen erg bezorgd over de schijnbare ‘compactheid’ van een districtsplan. Maar de onderliggende gegevens die worden gebruikt om herverdeling uit te voeren, zijn niet erg nauwkeurig. De mensen die de kaarten maken, beschikken niet over precieze gegevens over stemgedrag, of zelfs over locaties waar mensen wonen. Censustraktaten zijn misschien niet perfect op elkaar afgestemd, en gegevens kunnen in andere opzichten gewoonweg fouten en onzekerheid bevatten. De gegevens waar de tekenaars van districtskaarten om geven zijn dus net zo onzeker als onze puntenwolken. Met een geometrietheorie die rekening houdt met onzekerheid (en de grondverzetafstand is het ‘afstands’-gedeelte daarvan), kan men robuustere, betere instrumenten bedenken voor herverdeling.

Solomon’s website bevat een heleboel bronnen hierover, onder de namen ‘optimaal transport’ en ‘Wasserstein-metriek’, en zijn werk strekt zich uit van het berekenen van afstanden tot het berekenen van belangrijke geometrische waarden zoals het zwaartepunt, en computationele voordelen zoals parallellisme.

Anderen in het veld hebben transparantietechnieken bedacht om duidelijker te maken hoe de afstand van de grondverzetmachine zich verhoudt tot de geometrie van de onderliggende ruimte. Deze is vooral leuk omdat de uitleg resulteert in een pad dat van het begin tot het einde wordt afgelegd, en door de onderliggende metriek op precies zo’n manier in te stellen, kun je zien hoe de distributie door een doolhof navigeert om haar doel te bereiken. Ik stel me graag kleine mieren voor die al dat vuil met zich meedragen.

Ten slotte levert het werk van Shirdhonkar en Jacobs benaderingsalgoritmen op die lineaire tijdberekeningen mogelijk maken, in plaats van de kubieke looptijd van een lineaire oplosser in het slechtste geval.