{"id":4773,"date":"2022-02-09T04:57:58","date_gmt":"2022-02-09T04:57:58","guid":{"rendered":"https:\/\/lamarr-institute.org\/blog\/gan-vorhersage-von-wartezeiten\/"},"modified":"2025-11-12T14:54:47","modified_gmt":"2025-11-12T14:54:47","slug":"gan-vorhersage-von-wartezeiten","status":"publish","type":"blog","link":"https:\/\/lamarr-institute.org\/de\/blog\/gan-vorhersage-von-wartezeiten\/","title":{"rendered":"Die Vorhersage von Wartezeiten mit GANs"},"content":{"rendered":"\n<p>Wir verbringen einen Gro\u00dfteil unseres allt\u00e4glichen Lebens damit, auf verschiedene Dinge zu warten. Wir warten jeden Morgen bei B\u00e4cker*innen, um unser Brot zu kaufen. Wir warten jedes Mal, wenn wir eine Arztpraxis aufsuchen. Wir warten im Taxi darauf unser Ziel zu erreichen oder auf Antworten unserer Kontakte in sozialen Netzwerken. Und Warten betrifft nicht nur uns Menschen. Die Auftr\u00e4ge, die wir auf unseren Computern ausf\u00fchren, warten darauf, verarbeitet zu werden. Genau wie neue Gesetze und Vorschriften darauf warten, genehmigt zu werden.<\/p>\n\n\n\n<p>Naturgem\u00e4\u00df m\u00f6chten wir so wenig Zeit wie m\u00f6glich mit Warten verbringen. So verfolgen auch Dienstleistungssysteme in der Regel das Ziel unsere Wartezeit zu minimieren. Klar ist, dass es f\u00fcr beide Seiten extrem wertvoll sein kann, zu wissen, wie lange eine bestimmte Situation mehr oder weniger andauern wird. Denn mit solchen Informationen kann man vorausschauend planen und Dienstleister k\u00f6nnen ihre Prozesse optimieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span style=\"font-size: 18pt;\">Ein Blick auf die Queuing Theorie<\/span><\/h2>\n\n\n\n<p>Ein Teilgebiet der Mathematik namens \u201eQueuing Theory\u201d untersucht Wartezeiten und Warteschlangen mit dem Ziel, vorherzusagen, wie lange man auf eine bestimmte Dienstleistung warten wird. Lassen Sie uns einige Begriffe aus diesem Teilgebiet festlegen. Wie bereits erw\u00e4hnt, hat jede Warteschlange zwei Komponenten: den wartenden Auftrag oder die wartende Kundschaft und das System, das sich um die Kundschaft k\u00fcmmert (das Dienstleistungssystem). Um vorherzusagen, wie lange ein Kunde oder eine Kundin warten wird, muss man zun\u00e4chst vorhersagen, wann er oder sie beziehungsweise der Auftrag beim Dienstleister ankommt (Ankunftszeit), und sodann, abh\u00e4ngig von der Ankunftszeit, vorhersagen, wie lange das System brauchen wird, um seinen Dienst abzuschlie\u00dfen (Servicezeit).<\/p>\n\n\n\n<p>Ein Beispiel: Stellen Sie sich vor, Sie sitzen im Wartezimmer Ihrer Arztpraxis. Um sich die Zeit zu vertreiben, beschlie\u00dfen Sie vorherzusagen, ob ein neuer Patient oder eine neue Patientin genau in dem Moment die Praxis betreten wird, als Sie zur T\u00fcr schauen. Es gibt viele Faktoren, die Sie unm\u00f6glich wissen k\u00f6nnen, die aber beeinflussen, ob eine Person &#8211; nennen wir sie Sarah &#8211; genau in diesem Moment eintreffen wird. Sarah hat m\u00f6glicherweise den Zug verpasst oder hat eine alte Bekanntschaft getroffen, die immer gerne etwas zu viel plaudert. Ihr bester Sch\u00e4tzansatz in einem solchen Szenario ist es, Sarahs Ankunft &#8211; sagen wir in den n\u00e4chsten sechzig Sekunden &#8211; eine Wahrscheinlichkeit zuzuweisen. Zudem k\u00f6nnen Sie nur eine Wahrscheinlichkeit daf\u00fcr angeben, dass Sarahs Behandlung genau f\u00fcnfzehn Minuten dauern wird, wenn ihr Termin beginnt. Auch diese Wahrscheinlichkeit ist somit eindeutig von der Ankunftszeit abh\u00e4ngig.<\/p>\n\n\n\n<p>Gemeinsam haben Forschende der Mathematik und Statistik eine Vielzahl statistischer Modelle entwickelt, die eben diese Wahrscheinlichkeiten vorhersagen. Die Modelle machen jedoch starke Annahmen sowohl \u00fcber den Prozess der Ankunftszeit der Kundschaft (zum Beispiel, dass im Durchschnitt jede halbe Stunde eine Kundin oder ein Kunde einen Auftrag vergibt) als auch \u00fcber den Prozess der Dienstleistung (zum Beispiel, dass eine Person nach der anderen bedient wird, und zwar in der Reihenfolge der Ankunftszeit). Diese Annahmen sind entweder zu grob, um tats\u00e4chliche Ablaufprozesse beschreiben, oder viel zu spezifisch auf eine bestimmte Klasse von Dienstleistungssystemen zugeschnitten.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span style=\"font-size: 18pt;\">Generierung von Servicezeiten mit GANs<\/span><\/h2>\n\n\n\n<p>Anstatt Wahrscheinlichkeiten zu sch\u00e4tzen, schlagen wir vor, direkt Zufallszahlen entsprechend der Wahrscheinlichkeitsverteilung eines Datensatzes mit aufgezeichneten Servicezeiten zu generieren. Bei geeigneter Wahl k\u00f6nnen diese Zufallszahlen unseren Vorhersagen f\u00fcr die Servicezeit entsprechen. Schauen wir genauer hin:<\/p>\n\n\n\n<p>Wir nehmen an, dass wir einen gro\u00dfen Datensatz mit aufgezeichneten Ankunfts- und Servicezeiten f\u00fcr einen bestimmten Dienstleister haben. Wie oben beschrieben, geben solche Aufzeichnungen kein vollst\u00e4ndiges Bild \u00fcber die Ankunfts- oder Dienstleistungsprozesse ab. Daher spezifizieren wir unsere Unsicherheiten in Bezug auf die Prozesse in Form von unbekannten Wahrscheinlichkeitsverteilungen. Dies sind Funktionen, die die Wahrscheinlichkeiten f\u00fcr unsere Ankunfts- und Abgangsereignisse angeben. Eine M\u00f6glichkeit implizit auf die Wahrscheinlichkeitsverteilung der Servicezeiten zu schlie\u00dfen, besteht darin, einen Zufallsgenerator zu w\u00e4hlen, mit ihm Zufallszahlen zu generieren und diese in ein tiefes neuronales Netz hineinzugeben. Das neuronale Netz kann dann so trainiert werden, dass die Wahrscheinlichkeitsverteilung seiner Zufallsausgaben mit der Wahrscheinlichkeitsverteilung \u00fcbereinstimmt, die den aufgezeichneten (das hei\u00dft realen) Servicezeiten zugrunde liegt.<a href=\"https:\/\/lamarr-institute.org\/de\/generative-neuronale-modelle-gan\/\" target=\"_blank\" rel=\"noopener\"> Generative Adversarial Networks (GANs)<\/a> tun genau das, indem sie eine Form der Un\u00e4hnlichkeit zwischen realen und k\u00fcnstlichen Verteilungen minimieren. Die Un\u00e4hnlichkeit wird in GANs hierbei ebenfalls mit einem neuronalen Netz modelliert, das in der Literatur zum Maschinellen Lernen gew\u00f6hnlich als Diskriminator bezeichnet wird. Das neuronale Netz der Zufallszahlen wird hingegen als Generator bezeichnet.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span style=\"font-size: 18pt;\">Inferenz bedingter Servicezeitverteilungen<\/span><\/h2>\n\n\n\n<p>Es bleibt jedoch eine Herausforderung &#8211; n\u00e4mlich die Frage, wie man Servicezeiten in Abh\u00e4ngigkeit von Ankunftszeiten ermitteln kann. Wir haben dieses Problem gel\u00f6st, indem wir es in zwei Teile aufgeteilt haben. Erstens verwenden wir eine Klasse von rekurrenten neuronalen Netzen, die speziell daf\u00fcr entwickelt wurden, Darstellungen von Ankunftsprozessen zu erlernen. Diese Darstellungen sind nichts anderes als eine Umformulierung der Ankunftszeiten, die die Geschichte der Ank\u00fcnfte besser zusammenfasst. Nachfolgend geben wir diese Darstellung sowohl in den Generator (zusammen mit den Zufallszahlen) als auch in den Diskriminator (zusammen mit unseren Vorhersagen) des GANs ein. Als Ergebnis lernt unser Generator, wie er aus einer Servicezeitverteilung, die durch einen kontinuierlichen zeitlichen Ankunftsprozess bedingt wird, eine Stichprobe ziehen kann. Wir empfehlen unser<a href=\"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/17112\" target=\"_blank\" rel=\"noopener\"> AAAI-Paper<\/a> f\u00fcr weitergehende Informationen zur entwickelten Methode.<\/p>\n\n\n\n<p>Der Nutzen unseres Ansatzes ist, dass wir keine Annahmen \u00fcber die eigentlichen Dienstleistungssysteme, die wir analysieren wollen, machen m\u00fcssen. Wir brauchen einzig die Ankunfts- und Servicezeiten.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span style=\"font-size: 18pt;\">Modellierung von realen Dienstleistern<\/span><\/h2>\n\n\n\n<p>Wir haben unseren maschinellen Lernansatz auf die Verteilungen der Servicezeiten von drei sehr unterschiedlichen Dienstleistern angewandt: Github (ein Versionsverwaltungs-Repository), Stack Overflow (eine Frage-Antwort-Plattform f\u00fcr Programmierer*innen) und das New York City (NYC) Taxinetz. Abbildung 1 zeigt Histogramme f\u00fcr die empirischen Verteilungen der Servicezeiten dieser Anbieter (blaue Punkte) im Vergleich zu den von uns generierten Verteilungen (gelbe Punkte).<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" src=\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/\/Bild-1-1-1024x306.jpg\" alt=\"- Lamarr Institute for Machine Learning (ML) and Artificial Intelligence (AI)\" class=\"wp-image-25068\" title=\"\"><figcaption class=\"wp-element-caption\">\u00a9 ML2R <br>Abb. 1. Vergleich zwischen empirischen Servicezeitverteilungen von realen Dienstleistern (Testsatz) und den von unserem Modell generierten Daten. F\u00fcr Github definieren wir die Erstellung von Github-Issues als Ankunft und deren Abschluss als Abg\u00e4nge, so dass die Nutzer des Repository das Dienstleistungssystem darstellen. \u00c4hnlich ist es bei Stack Overflow, hier betrachten wir das Stellen von Fragen als Ankunftszeit und die Annahme einer Antwort als Abgang, wobei die Antwortgebenden das Dienstleistungssystem darstellen. Zuletzt identifizieren wir f\u00fcr das NYC Taxinetz den Beginn einer Fahrt als Ankunftszeit und ihr Ende als Abgang, so dass sowohl das Taxi, das die Dienstleistung erbringt, als auch das Verkehrsnetz von NYC als Dienstleistungssystem fungieren.<\/figcaption><\/figure>\n\n\n\n<p>Das Modell erfasst sowohl das lang- als auch das kurzfristige Verhalten in allen Systemen. Die \u00dcbereinstimmung ist bemerkenswert. Sehr wichtig ist hierbei, dass unser Modell es erm\u00f6glicht, neue Servicezeiten vorherzusagen. Man braucht nur die Ankunftszeit eines neuen Ereignisses einzugeben (Input), und das Modell gibt aus, wie lange der Dienst dauern wird (Output).<\/p>\n\n\n\n<p>Weitere Informationen im entsprechenden Paper:<\/p>\n\n\n\n<p><strong>Learning Deep Generative Models f\u00fcr Queuing Systems<\/strong><br>Cesar Ojeda, Kostadin Cvejoski, Bogdan Georgiev, Christian Bauckhage, Jannis Schuecker, Ramses Sanchez (Proceedings of the AAAI Conference on Artificial Intelligence), 2021,<a href=\"https:\/\/ojs.aaai.org\/index.php\/AAAI\/article\/view\/17112\" target=\"_blank\" rel=\"noreferrer noopener\"> PDF<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Die Sch\u00e4tzung von Wartezeiten bei Dienstleistungen ist essenziell f\u00fcr ihre Verbesserung. Durch Generative Adversarial Networks (GANs) k\u00f6nnen Wartezeiten genau gesch\u00e4tzt werden, mit wenigen oder keinen Annahmen \u00fcber die tats\u00e4chlichen Dienstleister.<\/p>\n","protected":false},"author":9,"featured_media":3681,"template":"","meta":{"_acf_changed":false,"footnotes":""},"blog-category":[1416,396],"blog-tag":[1512,1514,1518],"class_list":["post-4773","blog","type-blog","status-publish","has-post-thumbnail","hentry","blog-category-alle-blogbeitraege","blog-category-forschung","blog-tag-gans-de","blog-tag-generative-ki","blog-tag-hybrides-maschinelles-lernen"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4773","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/blog"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/9"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog\/4773\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media\/3681"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=4773"}],"wp:term":[{"taxonomy":"blog-category","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-category?post=4773"},{"taxonomy":"blog-tag","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/blog-tag?post=4773"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}