DeepMind verwendet GNNs, um die ETA-Genauigkeit von Google Maps um bis zu 50% zu steigern

Google Maps wurde vor 15 Jahren gestartet und ist laut dem deutschen Online-Portal Statista mit Abstand die beliebteste Navigations-App der Welt. In einem im vergangenen September veröffentlichten Google Cloud-Blogbeitrag sagte der Produktdirektor von Google Maps, Ethan Russell, dass mehr als eine Milliarde Menschen jeden Monat Google Maps verwenden und rund fünf Millionen aktive Apps und Websites jede Woche auf die Kernprodukte der Google Maps Platform zugreifen.

Die stets fleißigen DeepMind-Forscher haben inzwischen daran gearbeitet, Google Maps weiter zu verbessern. Diese Woche haben das in Großbritannien ansässige KI-Unternehmen und das Forschungslabor eine Partnerschaft mit Google Maps bekannt gegeben, die fortschrittliche Graph Neural Networks (GNNs) genutzt hat, um die geschätzte Ankunftszeit zu verbessern (ETA) Genauigkeit.

Die koordinierten Bemühungen haben die Genauigkeit von Echtzeit-ETAs in Städten wie Berlin, Jakarta, São Paulo, Sydney, Tokio und Washington DC um bis zu 50 Prozent erhöht.

ETAs und Verkehrsprognosen sind nützliche Tools, mit denen Benutzer Abfahrtszeiten effizient planen, Staus vermeiden und Freunde und Familienmitglieder über unerwartete verspätete Ankünfte informieren können. Diese Funktionen sind auch für Unternehmen wie Mitfahrzentralen und Bereitstellungsplattformen von entscheidender Bedeutung.

Zur Berechnung von ETAs analysiert Google Maps globale Live-Verkehrsdaten für relevante Straßensegmente. Dies liefert zwar ein genaues Bild der aktuellen Bedingungen, berücksichtigt jedoch nicht, was ein Fahrer 10, 20 oder sogar 50 Minuten nach seiner Fahrt erleben kann.

Um den zukünftigen Verkehr genau vorherzusagen, verwendet Google Maps maschinelles Lernen, um Live-Verkehrsbedingungen mit historischen Verkehrsmustern für Straßen zu kombinieren. Dies ist ein komplexer Prozess aufgrund von Schwankungen der Straßenqualität, Geschwindigkeitsbegrenzungen, Unfällen, Bauarbeiten und Straßensperrungen sowie beispielsweise des Zeitpunkts der Hauptverkehrszeiten an verschiedenen Orten.

Während sich die prädiktiven ETAs von Google Maps für rund 97 Prozent der Reisen als genau erwiesen haben, haben sich die DeepMind-Forscher zum Ziel gesetzt, die verbleibenden Ungenauigkeiten zu minimieren. Um dies auf globaler Ebene zu tun, verwendeten sie GNNs – eine verallgemeinerte Architektur des maschinellen Lernens -, um raumzeitliche Überlegungen anzustellen, indem sie relationale Lernverzerrungen einbezogen, um die Konnektivitätsstruktur realer Straßennetze zu modellieren.

Die Forscher teilten Straßennetze in „Supersegmente“ ein, die aus mehreren benachbarten Straßensegmenten bestehen, die ein erhebliches Verkehrsaufkommen aufweisen. Ihr Modell behandelt das lokale Straßennetz als Grafik, wobei jedes Streckensegment einem Knoten entspricht und Kanten zwischen Segmenten existieren, die auf derselben Straße aufeinander folgen oder durch eine Kreuzung verbunden sind. Diese Supersegmente als Straßensubgraphen werden im Verhältnis zur Verkehrsdichte zufällig ausgewählt.

In einem GNN wird ein Nachrichtenübermittlungsalgorithmus ausgeführt, bei dem die Nachrichten und ihre Auswirkung auf Kanten- und Knotenzustände von neuronalen Netzen gelernt werden. Ein einzelnes Modell kann daher unter Verwendung der abgetasteten Untergraphen trainiert und in großem Maßstab eingesetzt werden.

Während das ultimative Ziel des neuen Modellierungssystems darin besteht, Fehler bei Reiseschätzungen zu reduzieren, stellten die Forscher fest, dass die Verwendung einer linearen Kombination mehrerer Verlustfunktionen (entsprechend gewichtet) die Generalisierungsfähigkeit des Modells erheblich verbessert.

Eine große Herausforderung für die Forscher war die Sensibilität der GNN für Änderungen im Lehrplan. Beim Training von ML-Systemen wird die Lernrate häufig im Laufe der Zeit reduziert, da ein Kompromiss zwischen dem Lernen neuer Dinge und dem Vergessen wichtiger bereits erlernter Funktionen besteht. Die Forscher entwickelten eine neuartige Verstärkungstechnik, die es ihrem Modell ermöglichte, einen eigenen optimalen Zeitplan für die Lernrate zu erlernen, stabilere Ergebnisse zu erzielen und ihn schneller einzusetzen.