Optimaler Transport und seine Anwendung auf Gerechtigkeit

Übersetzer |. Li Rui. Die Ursprünge der Theorie des optimalen Transports lassen sich bis ins Jahr 1781 zurückverfolgen, als der französische Wissenschaftler Gaspard Monge eine Methode untersuchte, angeblich „die Erde zu bewegen“ und Befestigungen für Napoleons Armee zu bauen. Insgesamt besteht beim optimalen Transport das Problem, wie alle Ressourcen (z. B. Eisenerz) von einer Reihe von Ursprüngen (Minen) zu einer Reihe von Zielen (Stahlwerken) transportiert werden können und gleichzeitig die Gesamtentfernung, die die Ressourcen zurücklegen müssen, minimiert wird. Mathematisch wollten die Forscher eine Funktion finden, die jeden Ursprung einem Ziel zuordnet und gleichzeitig die Gesamtentfernung zwischen dem Ursprung und dem entsprechenden Ziel minimiert. Trotz seiner harmlosen Beschreibung stagnierte der Fortschritt bei der ursprünglichen Konzeption des Problems, bekannt als Mungers Konzeption, fast 200 Jahre lang.

In den 1940er Jahren adaptierte der sowjetische Mathematiker Leonid Kantorowitsch die Formulierung des Problems in eine moderne Version, die heute als Monge Kantorows Theorie bekannt ist, was den ersten Schritt zu einer Lösung darstellte. Die Neuheit besteht darin, dass ein Teil des Eisenerzes aus derselben Mine an verschiedene Stahlwerke geliefert werden kann. Beispielsweise können 60 % des Eisenerzes aus einer Mine an ein Stahlwerk geliefert werden, während die restlichen 40 % des Eisenerzes aus der Mine an ein anderes Stahlwerk geliefert werden können. Mathematisch gesehen ist dies keine Funktion mehr, da derselbe Ursprung nun potenziell mehreren Zielen zugeordnet ist. Im Gegensatz dazu wird dies als Kopplung zwischen der Ursprungsverteilung und der Zielverteilung bezeichnet, wie in der Abbildung unten gezeigt. Wenn Sie eine Mine aus der blauen Verteilung (Ursprung) auswählen und sich vertikal entlang der Abbildung bewegen, wird angezeigt, wohin das Eisenerz geschickt wird Stahlwerke (Ziel).

Als Teil dieser neuen Entwicklung führte Kantorivich ein wichtiges Konzept namens Wasserstein-Distanz ein. Ähnlich wie der Abstand zwischen zwei Punkten auf einer Karte misst die Wasserstein-Distanz (in Anlehnung an das ursprüngliche Szenario auch als Bulldozer-Distanz bekannt) den Abstand zwischen zwei Verteilungen, wie in diesem Fall der blauen und der magentafarbenen Verteilung. Wenn alle Eisenminen weit von allen Eisenwerken entfernt sind, ist der Wasserstein-Abstand zwischen der Verteilung (Standort) der Minen und der Verteilung der Stahlwerke groß. Trotz dieser neuen Verbesserungen ist immer noch unklar, ob es wirklich die beste Möglichkeit für den Transport von Eisenerzressourcen gibt, geschweige denn welche Methode. In den 1990er Jahren begann sich die Theorie schließlich rasch weiterzuentwickeln, da Verbesserungen in der mathematischen Analyse und Optimierung zu Teillösungen des Problems führten. Im 21. Jahrhundert begann sich der optimale Transport auch auf andere Bereiche wie die Teilchenphysik, die Fluiddynamik und sogar Statistik und maschinelles Lernen auszudehnen.

moderner optimaler Transport

Mit der Explosion neuer Theorien ist der optimale Transport in den letzten zwei Jahrzehnten Gegenstand vieler neuer statistischer und künstlicher Intelligenzalgorithmen geworden. In fast jedem statistischen Algorithmus werden Daten explizit oder implizit so modelliert, dass sie einer zugrunde liegenden Wahrscheinlichkeitsverteilung unterliegen. Wenn beispielsweise Daten zum individuellen Einkommen in verschiedenen Ländern erhoben werden, ergibt sich eine Wahrscheinlichkeitsverteilung des Einkommens dieser Bevölkerung in jedem Land. Wenn man zwei Länder anhand der Einkommensverteilung ihrer Bevölkerung vergleichen möchte, muss man die Lücke zwischen den beiden Verteilungen messen können. Genau aus diesem Grund ist die Optimierung des Transports (insbesondere der Wasserstein-Entfernung) in der Datenwissenschaft so nützlich. Allerdings ist die Wasserstein-Distanz nicht das einzige Maß für den Abstand zwischen zwei Wahrscheinlichkeitsverteilungen. Aufgrund ihrer Verbindung zur Physik und Informationstheorie waren die beiden Optionen L-2-Distanz und Kullback-Leibler (KL)-Divergenz historisch gesehen häufiger anzutreffen. Der Hauptvorteil der Wasserstein-Distanz gegenüber diesen Alternativen besteht darin, dass sie bei der Berechnung der Distanz sowohl die Werte als auch deren Wahrscheinlichkeiten berücksichtigt, während die L-2-Distanz und die KL-Divergenz nur Wahrscheinlichkeiten berücksichtigen. Das Bild unten zeigt ein Beispiel eines künstlichen Einkommensdatensatzes für drei fiktive Länder.

In diesem Fall beträgt der L-2-Abstand (oder die KL-Divergenz) zwischen der blauen und der magentafarbenen Verteilung ungefähr den Entspricht dem L-2-Abstand zwischen der blauen und der grünen Verteilung. Andererseits wird der Wasserstein-Abstand zwischen der Blau- und der Magenta-Verteilung viel kleiner sein als der Wasserstein-Abstand zwischen der Blau- und der Grün-Verteilung, da zwischen den Werten ein erheblicher Unterschied besteht (horizontale Trennung). Diese Eigenschaft des Wasserstein-Abstands macht ihn ideal für die Quantifizierung von Unterschieden zwischen Verteilungen, insbesondere von Unterschieden zwischen Datensätzen.

Erreichen Sie Fairness mit optimalem Transport

Da täglich große Datenmengen erfasst werden, wird maschinelles Lernen in vielen Branchen immer häufiger eingesetzt, und Datenwissenschaftler müssen immer vorsichtiger sein, nicht wahr? Lassen Sie nicht zu, dass ihre Analysen und Algorithmen bestehende Verzerrungen und Verzerrungen in den Daten aufrechterhalten. Wenn beispielsweise ein Datensatz zur Genehmigung einer Eigenheimhypothek Informationen über die Rasse der Antragsteller enthält, im Erhebungsprozess jedoch Minderheiten aufgrund der verwendeten Methoden oder unbewusster Voreingenommenheit diskriminiert wurden, spiegelt ein auf diesen Daten trainiertes Modell die zugrunde liegende Abweichung wider.

Die Optimierung des Versands kann dazu beitragen, diese Tendenz zu mildern und die Fairness auf zwei Arten zu verbessern. Die erste und einfachste Methode besteht darin, mithilfe der Wasserstein-Distanz zu bestimmen, ob im Datensatz eine potenzielle Verzerrung vorliegt. Beispielsweise kann man den Wasserstein-Abstand zwischen der Verteilung der für Frauen genehmigten Kreditbeträge und der Verteilung der für Männer genehmigten Kreditbeträge abschätzen. Ist der Wasserstein-Abstand sehr groß, also statistisch signifikant, kann ein potenzieller Bias vermutet werden. Diese Idee, zu testen, ob es einen Unterschied zwischen zwei Gruppen gibt, wird in der Statistik als Hypothesentest mit zwei Stichproben bezeichnet.

Alternativ kann der optimale Versand sogar verwendet werden, um Fairness im Modell durchzusetzen, wenn der zugrunde liegende Datensatz selbst verzerrt ist. Dies ist aus praktischer Sicht nützlich, da viele reale Datensätze ein gewisses Maß an Verzerrungen aufweisen und das Sammeln unvoreingenommener Daten sehr teuer, zeitaufwändig oder nicht durchführbar sein kann. Daher ist es praktischer, vorhandene Daten zu verwenden, egal wie unvollkommen sie sind, und zu versuchen, sicherzustellen, dass das Modell diese Verzerrung abmildert. Dies wird erreicht, indem eine Einschränkung im Modell erzwungen wird, die als starke demografische Parität bezeichnet wird und die Modellvorhersagen dazu zwingt, statistisch unabhängig von sensiblen Attributen zu sein. Ein Ansatz besteht darin, die Verteilung von Modellvorhersagen auf die Verteilung angepasster Vorhersagen abzubilden, die nicht von sensiblen Attributen abhängen. Allerdings verändert die Anpassung der Vorhersagen auch die Leistung und Genauigkeit des Modells, sodass ein Kompromiss zwischen der Modellleistung und dem Grad, in dem das Modell auf sensible Attribute angewiesen ist (d. h. Fairness), besteht.

Stellen Sie eine optimale Modellleistung sicher, indem Sie Vorhersagen so wenig wie möglich ändern und gleichzeitig sicherstellen, dass neue Vorhersagen unabhängig von sensiblen Attributen sind, was zu einem optimalen Versand führt. Die von diesem angepassten Modell vorhergesagte neue Verteilung wird Wasserstein-Schwerpunkt genannt und war im letzten Jahrzehnt Gegenstand umfangreicher Forschung. Der Wasserstein-Schwerpunkt ähnelt dem Mittelwert einer Wahrscheinlichkeitsverteilung darin, dass er den Gesamtabstand von sich selbst zu allen anderen Verteilungen minimiert. Das Bild unten zeigt drei Verteilungen (grün, blau und magenta) zusammen mit ihren Wasserstein-Schwerpunkten (rot).

Nehmen wir im obigen Beispiel an, dass ein Modell erstellt wird, um das Alter und Einkommen einer Person auf der Grundlage eines Datensatzes vorherzusagen, der ein sensibles Attribut (z. B. Familienstand) enthält, das drei mögliche Werte annehmen kann: ledig (blau), verheiratet (grün) und verwitwet/geschieden (magenta). Das Streudiagramm zeigt die Verteilung der Modellvorhersagen für jeden unterschiedlichen Wert. Wenn Sie diese Werte jedoch so anpassen möchten, dass die Vorhersagen des neuen Modells den Familienstand einer Person nicht berücksichtigen, kann jede dieser Verteilungen mithilfe optimaler Transportmittel auf den Schwerpunkt in Rot abgebildet werden. Da alle Werte der gleichen Verteilung entsprechen, kann man den Familienstand einer Person nicht mehr anhand von Einkommen und Alter beurteilen oder umgekehrt. Der Schwerpunkt bewahrt die Wiedergabetreue des Modells so weit wie möglich.

Die zunehmende Allgegenwärtigkeit von Daten und Modellen des maschinellen Lernens, die bei der Entscheidungsfindung in Wirtschaft und Regierung eingesetzt werden, hat zur Entstehung neuer sozialer und ethischer Fragen darüber geführt, wie die faire Anwendung dieser Modelle sichergestellt werden kann. Viele Datensätze enthalten aufgrund der Art ihrer Erhebung eine gewisse Verzerrung. Daher ist es wichtig, dass auf ihnen trainierte Modelle diese Verzerrung oder historische Diskriminierung nicht verschärfen. Optimaler Transport ist nur eine Möglichkeit, dieses in den letzten Jahren zunehmende Problem zu lösen. Heutzutage gibt es schnelle und effiziente Möglichkeiten, optimale Transportkarten und Entfernungen zu berechnen, sodass dieser Ansatz für moderne große Datenmengen geeignet ist. Da sich die Menschen zunehmend auf datenbasierte Modelle und Erkenntnisse verlassen, ist Fairness ein Kernthema der Datenwissenschaft und wird auch weiterhin ein zentrales Thema sein, und optimale Transportmöglichkeiten werden eine Schlüsselrolle bei der Erreichung dieses Ziels spielen.

Originaltitel: ​​Optimal Transport and its Applications to Fairness​​​, Autor: Terrence Alsup​

Das obige ist der detaillierte Inhalt vonOptimaler Transport und seine Anwendung auf Gerechtigkeit. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!