Sortierung, Seitengrössen und algorithmische Ungerechtigkeit

Marc Sommerhalder Mesa, Python

Angenommen wir hätten ein System, dass Suchresultate paginiert (d.h. die Resultate werden in mehrere Seiten aufgeteilt) und nach Anzahl Interaktionen sortiert auflistet. Ein solches System könnte zum Beispiel ein Online Shop (Käufe), eine Suchmaschine (Clicks), ein Social Media Feed (Clicks) oder ein News-Aggregator (Clicks) sein. Hat die Darstellung der Resultate einen Einfluss auf die resultierende Verteilung der Interaktionen? Führt dies zu einer durch den Algorithmus eingeführte Ungerechtigkeit, d.h. werden einige Resultate mit der Zeit ungerechtfertigt bevorzugt behandelt? Eine erste Idee der Auswirkungen eines solches Systems kann durch Simulation gewonnen werden!

Modell

Für die Simulation wird eine agentenbasierte Modellierung verwendet. Jeder Agent durchstöbert eine paginierte, sortierte Liste von Elementen und interagiert mit einem zufällig ausgewählten Element. Es besteht die Möglichkeit, dass der Verbraucher nur die erste Seite durchblättert. Nach einigen Interaktionen wird die Liste absteigend nach Anzahl Interaktionen sortiert.

Zur Bestimmung der Ungleichverteilung wird der Hoover Index (der normierten mittleren absoluten Abweichung) berechnet:

Resultat

Eine Simulation mit 100 Elementen und 50 Interaktionen / Agenten pro Sortierung zeigt, dass je kleiner die Seitengrösse und je grösser die Wahrscheinlichkeit, nur die erste Seite zu durchstöbern, desto grösser die resultierende Ungleichverteilung. Überraschend ist dabei, dass bereits sehr geringe Wahrscheinlichkeiten zu einer merkbaren Ungleichverteilung führen.

Abbildung 1: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit.

Weiter ist zu sehen, dass die Ungleichverteilung bereits nach wenigen Neusortierungen entsteht und relativ konstant bleibt (100 Items, Seitengrösse 20). Das Histogramm zeigt eine bimodale Verteilung: Einige wenige Elemente besitzen viele Interaktionen, viele Elemente haben nur sehr wenige Interaktionen.

Abbildung 2: Entwicklung der Ungleichverteilung und finale Verteilung.

Moderierende Faktoren

In einem solchen System kann es weitere moderierende Faktoren geben, welche zum Beispiel den Effekt der Ungleichverteilung abschwächen. Ein solcher Faktor könnte zum Beispiel ein maximales Alter der Elemente sein, z.B. in einem Shop Artikel, welche nicht mehr geliefert werden.

Das Modell wird so angepasst, dass jedes Element ein Alter in Anzahl Sortierungszyklen besitzt und nach einer bestimmten Anzahl Zyklen durch ein neues (mit Alter 0) ersetzt wird. Die initialen Elemente werden mit zufälligem Alter initialisiert.

Eine Simulation mit 100 Elementen, 50 Interaktionen / Agenten pro Neusortierung und einer Seitengrösse von 20 zeigt, dass die Ungleichverteilung dadurch bereits zu Beginn höher ist. Allgemein ist die Ungleichverteilung grösser, je kleiner das maximale Alter.

Abbildung 3: Ungleichverteilung in Abhängigkeit der Seitengrösse und Wahrscheinlichkeit, mit rotierendem Bestand.

Ein Blick auf die zeitliche Entwicklung (100 Items, Seitengrösse 20) zeigt den Unterschied zu vorher: Zwar gibt es auch hier bereits nach wenigen Neusortierungen bereits eine Ungleichverteilung, diese variiert mit der Zeit aber stärker. Zudem gibt nun eine unimodale Verteilung statt einer bimodalen Verteilung: die meisten Elemente besitzen nur wenige Interaktionen. Die Verteilung scheint ein kleines Bisschen fairer.

Abbildung 4: Entwicklung der Ungleichverteilung und finale Verteilung, mit rotierendem Bestand.

Weiterführende Informationen

Proxy Cache Simulation

Marc Sommerhalder Python, SimPy

Im modernen Web findet man oft den für eine Webapplikation typischen Aufbau mit Webserver und Applikation. Ein Benutzer macht dabei die Requests alle an einen Webserver (NGINX, Apache, Traefik) welche seinerseits die Requests an eine Applikation (z.B. Django) weiterleitet.

Der Webserver kümmert sich dabei typischerweise um Themen wie SSL Terminierung oder Load Balancing. Neben diesen Aufgaben kann aber der Webserver aber auch als sogenannter Proxy Cache agieren, dabei werden die Antworten bestimmter Requests im Cache gespeichert und von da aus beantwortet, die Requests gelangen nie zur Applikation.

Wie viel bringt ein solches Proxy Caching in welchen Situationen? Ein Experimentieren am laufenden System erfordert teure Load Tests und mühsame Auswertung von Serverlogs. Einen ersten Einblick in das Verhalten und das Auswirken von Variieren der Parameter kann aber auch einfacher mittels Simulation erhalten werden.

Modell

Für die Simulation wird SimPy verwendet, ein Python Paket für diskrete Ereignissimulation. Das ganze System wird über verschiedene Klassen modelliert, welche sich an der Übersicht weiter oben orientieren:

  • Der UserGenerator erzeugt exponentialverteilt mit einer gegeben Ankunftsrate neue User.

  • Ein User erzeugt einen initialen Page-Request (z.B. HTML Seite) und anschliessend 5 gleichzeitige Asset-Requests (z.B. JavaScript, CSS, Webfonts).

  • Der Page- oder Asset-Request wartet der Reihe nach auf einen Webserver-Worker, eine Applikations-Instanz (falls ohne Cache), die Application-Antwort (falls ohne Cache) und schliesslich auf die Webserver-Antwort.

  • Der Webserver ist eine Warteschlange mit einer Kapazität von 768 Worker und einer triangular-verteilten Verarbeitungszeit von 10/15/20ms.

    • Optional werden für den Cache Page-Requests für 5s respektive Asset-Requests unendlich lange beim ersten Request gespeichert.

  • Die Application ist eine Warteschlange mit einer Kapazität von 4 Instanzen und triangular-verteilten Verarbeitungszeit von 0.5/5/60s für Page-Requests respektive 100/150/200ms für Asset-Requests.

Währen der Simulation werden pro Request verschiedene Zeiten gemessen:

  • waiting_time_webserver : Wie lange auf einen Webserver-Worker gewartet wird.

  • waiting_time_application : Wie lange auf eine Applikations-Instanz gewartet wird.

  • response_time_application: Wie lange die Applikation für die Antwort braucht.

  • response_time_webserver: Wie lange der Webserver für die Antwort braucht.

  • total_time: Die Gesamtzeit des Requests.

Baseline: Ohne Cache

Ohne Cache – d.h. jeder Request wird vom Webserver direkt an die Applikation weitergereicht – steigt die Drop Rate – d.h. die Anzahl Requests, welche während der Simulationszeit von einer Stunde nie eine Antwort erhalten – ab einer Rate von rund 10 Benutzern pro Minute.

Bei nur einem Benutzer pro Minute gibt es keine Wartezeiten und die Antwortzeiten bestimmen sich durch die vorgegebenen Verteilungen. Die Gesamtzeit ist praktisch nur von der langsamen Applikation bestimmt. Bei 50 Benutzern pro Minute zeigt sich hingegen ein anderes Bild: Hier sind nun die Antwortzeiten verhältnismässig irrelevant, am meisten Zeit braucht das Warten auf eine Applikations-Instanz sowie das Warten auf einen Webserver-Worker. Das Bottleneck ist wie zu erwarten die langsame Applikation.

Caching von Assets

Assets wie JavaScript-, CSS- und Webfont-Dateien verändern sich relativ selten und können daher meist problemlos für einen längeren Zeitraum im Cache des Webserver gespeichert werden. Request für solche Dateien werden dadurch bereits vom Webserver beantwortet, die Applikation wird weniger belastet. Zwar steigt auch hier die Drop Rate ab ca. 10 Benutzern pro Minute, allerdings etwas weniger steil.

Deutlich gesunken ist hingegen die durchschnittlich Gesamtzeit (aufgrund der schneller beantworteten Assets-Requests). Immer noch ist jedoch das Warten auf freie Applikationsinstanzen das Bottleneck, da jeder User einen intitialen Page-Request benötigt. Mit steigender Anzahl Benutzer werden auch diese Requests nicht mehr beantwortet und der Assets-Cache ist wirkungslos.

Wie wirkt sich eigentlich eine Erhöhung der Anzahl Instanzen und Worker aus? Mit der Erhöhung der Anzahl Instanzen sinkt die Drop Rate stark, da mehr Requests gleichzeitig abgearbeitet werden können. Aber auch die Erhöhung der Anzahl Worker wirkt sich positiv auf die Drop Rate aus, da diese die stark variierende Antwortzeit der Applikation aber auch die unterschiedlichen Ankunftszeiten der User glätten können.

Caching von Pages und Assets

HTML Seiten sind generell kritischer bezüglich Cache, da sie meist dynamisch sind. Die Anzahl möglicher Benutzer pro Minute ohne Drop Rate steigt um den Faktor 100. Bereits eine nur kurze Cache Dauer von 5s für Page-Requests kann aber bereits einen starken Einfluss haben, da damit Spitzen gebrochen werden können.

Auch die mittlere Antwortzeit sinkt mit nur wenigen Sekunden Pages Cache. Schlussendlich ist auch hier wieder die langsame Applikation das Bottleneck respektive das Warten auf freie Applikations-Instanzen.

Ressourcen

Parlamentspositionen, Wähleranteile, Inserate und Abstimmungsergebnisse

Marc Sommerhalder KNIME

Können eigentlich Abstimmungsergebnisse vorhergesagt werden? Genauer gefragt: Gibt es Indikatoren, zum Beispiel die Position der Bundesversammlung, welche das Ergebnis von eidgenössischen Abstimmungen voraussagen (sogenannte Prädiktoren)?

Um dieser Frage nachzugehen und dabei einige Möglichkeiten der mathematischen Grundlagen zum simulationsgestützten Experimentierens und Evaluieren aufzuzeigen, wird im Folgenden der Zusammenhang zwischen verschiedenen Merkmalen und dem Abstimmungsergebnis untersucht. Da es sich hier nicht um Experiment handelt, können wir leider nur eine Aussage über die Korrelation, nicht aber über die Kausalität machen. Wir haben zwar immer eine zeitliche Abfolge, jedoch können wir weder Störfaktoren beeinflussen noch die unabhängigen Merkmale systematisch setzen. Insbesondere kann es gut sein, dass es sich um eine Scheinkorrelation handelt: Ein drittes Merkmal bestimmt sowohl Abstimmungsergebnis als auch das (vermeintlich) unabhängige Merkmal.

Die gesamte Analyse basiert auf dem Swissvotes-Datensatz der Universität Bern und ist mit der freien verfügbaren Datenanalysesoftware KNIME Analytics durchgeführt worden.

Rechtsform und Position

Im Datensatz gibt es einige nominalskalierte Merkmale, welche wir für eine erste Analyse verwendet werde können:

  • Abstimmungsergebnis (angenommen, abgelehnt)
  • Position des Bundes-, Stände- und Nationalrates sowie der gesamten Bundesversammlung (befürwortend, ablehnend, ohne)
  • Rechtsform (obligatorisches oder fakultatives Referendum sowie Volksinitiative, Gegenentwurf und Stichfrage)

Diese Merkmale sind aufgrund des politischen Systems und dessen Prozessen natürlich nicht unabhängig voneinander.

Nominale Merkmale sind stets qualitativ, alle Merkmalswerte sind gleichbedeutend (mehr Informationen zu statistischen Grundbegriffen). Der Zusammenhang zwischen nominalen Merkmalen kann zum Beispiel mit einem χ²-Test bestimmt werden. Bei einem χ²-Test wird eine empirisch beobachtete Häufigkeitsverteilung mit einer theoretisch angenommenen Häufigkeitsverteilung verglichen (mehr Informationen zu Testverfahren).

In diesem Fall können wir mit einer Kontingenztabelle arbeiten: In den Zeilen sind die entsprechenden Merkmalswerte, in den Spalten die Merkmalswerte des Ergebnisses, hier am Beispiel der Bundesratsposition:

Abbildung 1: Kontingenztabelle Bundesratsposition – Abstimmungsergebnis

 Aus der Tabelle ist ersichtlich, dass tatsächlich sehr oft (91%) eine Abstimmung abgelehnt wurde, falls der Bundesrat eine Ablehnung empfohlen hat. Bei einer empfohlenen Annahme wurde diese oft (64%) angenommen. Um festzustellen, ob dieses Resultat nicht auch zufällig entstanden sein könnte, müssen wir diese Verteilung mit einer alternativen theoretischen Verteilung vergleichen: Alle Zellen sind gleichverteilt:

Abbildung 2: Resultat des χ²-Tests Bundesratsposition – Abstimmungsergebnis

Wie wir sehen, ist der Zusammenhang zwischen den beiden Merkmalen nur mit sehr, sehr geringer Wahrscheinlichkeit zufällig (mehr Informationen zur Signifikanz). Wir können also davon ausgehen, dass es einen signifikanten Zusammenhang zwischen Position des Bundesrates und dem Ergebnis einer Abstimmung gibt: Abstimmungsergebnisse folgen der Empfehlung des Bundesrates.

Dasselbe gilt für die Position des Ständerates:

Abbildung 3: Kontingenztabelle Ständeratsposition – Abstimmungsergebnis

Abbildung 4: Resultat des χ²-Tests Ständeratsposition – Abstimmungsergebnis

Als auch für die Position des Nationalrates:

Abbildung 5: Kontingenztabelle Nationalratsposition – Abstimmungsergebnis

Abbildung 6: Resultat des χ²-Tests Nationalratsposition – Abstimmungsergebnis

Dementsprechend ist es wenig überraschend, dass dieselbe Aussage auch für die Bundesversammlung (National- und Ständerat) gilt:

Abbildung 7: Kontingenztabelle Bundesversammlung – Abstimmungsergebnis

Abbildung 8: Resultat des χ²-Tests Bundesversammlungssposition – Abstimmungsergebnis

Findet sich auch ein Zusammenhang zwischen Abstimmungsergebnis und Rechtsform?

Abbildung 9: Kontingenztabelle Rechtsform – Abstimmungsergebnis

Abbildung 10: Resultat des χ²-Tests Rechtsform – Abstimmungsergebnis

Die Kontingenztabelle zeigt, dass Volksinitiativen mehrheitlich abgelehnt werden, Referenden hingegen mehrheitlich angenommen werden. Auch dieser Zusammenhang ist signifikant:

Wähleranteile und Inserate

Der Swissvotes-Datensatz beinhaltet auch einige kardinalskalierte Merkmale, welche wir für einen weiteren Analyseschritt verwenden können:

  • Prozentanteil der Ja-Stimmen
  • Summe der Wähleranteile aller Parteien, welche die Ja-Parole ausgaben.
  • Prozentanteil der Inserate, die für ein Ja warben.

Zwischen zwei kardinalskalierten Merkmalen (mehr Informationen zu statistischen Grundbegriffen) kann mittels Regression untersucht werden, ob ein linearer Zusammenhang besteht (mehr Informationen zur Regression) – also ein Zusammenhang in der Form “je mehr x, desto mehr/weniger y”.

Eine Regression zwischen der Wähleranteile und dem Abstimmungsergebnis liefert eine Regressionsgerade:

Abbildung 11: Regressionsgerade und Scatterplot Wähleranteile – Abstimmungsergebnis

Zwischen beiden Merkmalen gibt es einen positiven linearen Zusammenhang: Je mehr Wähleranteil die Ja-Parole besitzt, desto mehr Ja-Stimmen erhält eine Abstimmung.

Die Güte einer Regression wird durch den Korrelationskoeffizienten (R) respektive den Determinationskoeffizient (R²) gemessen. Der Korrelationskoeffizient variiert von -1 (perfekter negativer Zusammenhang) über 0 (kein Zusammenhang) bis 1 (perfekter positiver Zusammenhang). In diesem Fall liegt der Korrelationskoeffizient bei 0.7, es handelt sich um einen starken linearen Zusammenhang. Der Determinationskoeffizient gibt an, wie viel der Gesamtvarianz durch die Regression erklärt wird. In diesem Fall wird rund die Hälfte der Gesamtvarianz durch die Regression erklärt.

Eine Regression zwischen den Inserateanteilen und dem Abstimmungsergebnis liefert die folgende Regressionsgerade:

Abbildung 12: Regressionsgerade und Scatterplot Inserateanteile – Abstimmungsergebnis

Auch hier gibt es zwischen beiden Merkmalen einen positiven linearen Zusammenhang: Je mehr Inserateanteile für ein Ja werben, desto mehr Ja-Stimmen erhält eine Abstimmung. Der lineare Zusammenhang ist hier jedoch schwächer (R=0.4) und es wird sehr viel weniger der Gesamtvarianz durch die Regression erklärt (rund 15%).

Ressourcen

Monte-Carlo-Simulation des Kartenspiels “Tschau Sepp”

Marc Sommerhalder Monte Carlo, Python

Wie oft sagt man eigentlich im Spiel “Tschau Sepp” durchschnittlich “Tschau”? Die kurze Antwort: Einmal, und zwar egal ob man verliert oder gewinnt. Die etwas längere Antwort: Es kommt auf die Anzahl Spieler und Anzahl Karten zu Beginn des Spieles an. Bei zwei Spielern sind es ungefähr eineinhalb Mal, bei vier oder mehr Spielern weniger als ein Mal, siehe Abbildung 1.

Abbildung 1: Durschnittliche Anzahl gesagter “Tschau” pro Spiel.

 

Die Resultate stammen nicht etwa aus einer langwierigen Versuchsreihe, in der Angehörige der Hochschule tagelang “Tschau Sepp” gespielt haben, sondern aus einer sogenannten Monte-Carlo-Simulation. Bei einer Monte-Carlo-Simulation – der Name ist eine Anlehnung an die gleichnamige Spielbank in Monaco – wird versucht, ein analytisch nicht oder nur schlecht lösbares Problem mit Hilfe von Wahrscheinlichkeitstheorie numerisch zu lösen. Dazu wird in diesem Fall zuerst die Spielmechanik, also die Spielregeln und der Spielablauf, programmiert. Anschliessend wird eine grosse Anzahl Spiele simuliert (hier 100’000) und dabei gewisse Parameter zufällig gewählt: die initiale Reihenfolge der Karten im Stapel, welche Karte gespielt wird, usw. Zählt man nun alle gesuchten Ereignisse (also zum Beispiel wie oft in einem Spiel das Wort “Tschau” gefallen ist), kann man daraus mit der Gesamtanzahl Spiele die durchschnittlichen Werte schätzen.

Genauso ist es nun auch möglich, die Anzahl gespielter Züge und damit die Dauer des Spieles abzuschätzen. Je mehr Spieler und Anzahl Karten zu Beginn, desto länger dauert das Spiel. Bei zwei Spielern sind es durchschnittlich etwas mehr als 30 Züge pro Spiel, bei fünf Spielern 40 bis 50, siehe Abbildung 2.

Abbildung 2: Durchschnittliche Anzahl Züge.

Wir können auch abschätzen, wie viele Karten man durchschnittlich auf der Hand hat. Das ist bei Spielen mit Kindern eine durchaus relevante Frage. Auch hier gilt wieder: je mehr Spieler und Karten zu Beginn des Spieles, desto mehr Karten hat man auch durchschnittlich auf der Hand. Bei fünf Karten zu Beginn sind es im Schnitt etwas mehr als drei, bei sieben Karten und mehr als vier Spieler beinahe vier, siehe Abbildung 3.

Abbildung 3: Durschnittliche Anzahl Karten auf der Hand.

Mehr Informationen:

Der Tetrapolyser, ein Simulationswerkzeug zur Optimierung des Polycom Netzes der Schweiz

Marc Sommerhalder Allgemein

Ein Praxisbeitrag von Wüthrich Markus und Simon Boschetti, Bundesamt für Bevölkerungsschutz

Polycom ist das flächendeckende Sicherheitsnetz Funk der Behörden und Organisationen für Rettung und Sicherheit (BORS). Es ermöglicht den Funkkontakt innerhalb wie zwischen den verschiedenen Organisationen Grenzwacht, Polizei, Feuerwehr, sanitätsdienstliches Rettungswesen, Zivilschutz und unterstützende Verbände der Armee. Sämtliche BORS des Bundes, der Kantone und der Gemeinden können heute über eine einheitliche und homogene Infrastruktur Funkgespräche sowie Daten übertragen. Aufgebaut wurde das Sicherheitsnetz schrittweise mit Teilnetzen unter der Leitung des Bundesamtes für Bevölkerungsschutz (BABS).

Das Netz wurde inkrementell ab 1999 von den Kantonen in Betrieb genommen.  Ab 2014 war Polycom Netz schweizweit verfügbar. Mit dem fortschreitenden Aufbau von Polycom kamen jedoch schrittweise neben rein kantonalen sowohl überregionale, als auch nationale Bedürfnisse zum Vorschein. Insbesondere mangelte es bisher an geeigneten Hilfsmitteln, welche eine Gesamtsystembetrachtung hinsichtlich Planungsvorgaben und Ausfallsicherheit unterstützen.

Das BABS ist verantwortlich, die bestehende Kommunikationsinfrastruktur, welche tagtäglich von rund 55‘000 Nutzern genutzt wird, nachhaltig in die Zukunft zu führen.

Zwischen 2013 und 2015 entwickelte die HSR im Auftrag vom BABS ein Simulationswerkzeug, welches Optimierungsarbeiten im Tetrapol-TDM-BackBone des POLYCOM Netzwerks in der Schweiz ermöglichte. Das Simulationswerkzeug steht heute für Optimierungs- und Neukonfigurationsarbeiten erfolgreich im Einsatz.

Ein grosser Teil der im System Polycom genutzten Komponenten ist mehr als zehn Jahre in Betrieb und muss aufgrund des Technologiewandels erneuert werden. Das BABS hat deshalb das Projekt Polycom Werterhaltung 2030, welches von den eidgenössischen Parlamenten beauftragt wurde, initiiert, um die Nutzung bis 2030 sicherzustellen und somit für eine nachhaltige Werterhaltung des Gesamtsystems zu sorgen. Mit dem Umbau von Time Division Multiplexing (TDM) auf die IP-Technologie kann die Funktionsfähigkeit bis mindestens 2030 sichergestellt werden.

Für die Vorbereitung dieser Migration, im Jahr 2017, wurde das bestehende Tetrapolyzer Simulations Software für die Simulation der zukünftigen Belastung im IP basierten System, sowie für die Simulation während des Parallelbetriebes (TDM-IP) erweitert.

Während diesen Jahren haben mehrere Semester- und Bachelorarbeiten stattgefunden während diesen die Tetrapolyzer Software mit neuen Bedürfnissen ergänzt wurde. Diese Applikation ermöglicht dem BABS und der Industrie nicht nur, das Polycom Netz und seine Ressourcen optimal zu nutzen und zu konfigurieren, sondern auch, Probleme von einzelnen Ausfällen durch die Simulation in kurzer Zeit zu beheben. Die Applikation wurde dem Hersteller von Tetrapol, Airbus SLC, präsentiert. Gemäss Airbus SLC ist die Applikation in ihrer Ausprägung weltweit einzigartig und deckt die Simulationsbedürfnisse von komplexen Tetrapolprojekten umfassend ab.

Das Bundesamt für Bevölkerungsschutz ist mit der Zusammenarbeit sehr zufrieden und dankt Herrn Professor Rinkel und der FH Rapperswil für ihren Beitrag über diese Jahre.

 

Quelle: BA 2019 J. Egger, M. Stocker