Hinter all den Informationen von Google - von der Ermittlung der wichtigsten Suchergebnisse bis zum Lesen und Verfolgen Ihrer E-Mails - steckt eine interessante Mathematik. Und kürzlich hielt Javier Tordable, ein Software-Ingenieur, eine Präsentation darüber und öffnete ein Fenster in die geekige Google-Welt, nur ein Riss.
Beginnen wir mit Google Mail. Manchmal bekommt man Spam-Mails, aber Google Mail kann ziemlich gut herausfinden, dass ein Korrespondent, der versucht, Sie dazu zu bringen, in einen nigerianischen Prinzen zu investieren, diese Mail wahrscheinlich nicht in Ihrem Posteingang haben möchte. Woher weiß es das? Schritt eins: Maschine trainieren. Schritt zwei: Lass es funktionieren.
Es heißt maschinelles Lernen und Google macht eine Menge davon. In Schritt eins müssen Sie das tun, was Informatiker „eine Instanz charakterisieren“ nennen. In mathematischer Sprache bedeutet das:
Im Allgemeinen können die Eigenschaften einer Instanz als Elemente in einem Vektor eines eindimensionalen euklidischen Raums für ein großes n betrachtet werden (100-1000 Dimensionen sind normal, 1M-10M sind keine Seltenheit).
Aber hier ist, wie man darüber nachdenkt, wenn man nach Calc 1 aufgehört hat zu rechnen. Google Mail kann einige wichtige Informationen aus einer bestimmten E-Mail abrufen. Wie lange ist es? Wie viele Großbuchstaben gibt es? Ist dies von jemandem, von dem Sie zuvor eine E-Mail erhalten haben? Sie möchten nicht, dass die Informationen, die erforderlich sind, um eine Entscheidung zu treffen, zu schwer sind, da dies die Genauigkeit Ihrer Maschine verlangsamt und verringert. Google zieht also eine Linie, basierend auf dem, was es über Spam weiß. Die E-Mails, die durchkommen, fallen auf die eine und die spammigen auf die andere Seite.
Mehr Mathe sprechen:
Ein einfaches Klassifikationsmodell ist eine Hyperebene im Raum der Merkmale. Dateninstanzen auf einer Seite der Hyperebene werden als gültige E-Mails und Instanzen auf der anderen Seite als Spam klassifiziert.
Was ist mit der Sprachsuche - auch automatische Spracherkennung oder ASR genannt? Ähnlich wie beim maschinellen Lernen besteht ASR aus zwei Teilen: dem Verarbeiten des eingehenden Klangs und dem Herausfinden, was Sie sagen. Der erste Teil beinhaltet Fourier-Transformationen, die die wichtigen Bits isolieren, die der Computer übersetzen kann. Der zweite Teil ist das Modellieren von Sprache unter Verwendung eines so genannten "Hidden-Markov-Modells". Tordable erklärt:
In diesem Modell sind die Zustände die Buchstaben der Nachricht und die Abfolge der Ereignisse ist das Tonsignal. Der Viterbi-Algorithmus kann verwendet werden, um die Folge von Zuständen maximaler Wahrscheinlichkeit zu erhalten.
Google würde gerne die Spracherkennung verbessern und vereinfachen. In dieser Fallstudie schreibt eine Gruppe von Google-Whizzes:
Ein Ziel bei Google ist es, den Sprachzugriff allgegenwärtig verfügbar zu machen. Wir möchten dem Benutzer die Wahl lassen - er sollte davon ausgehen können, dass gesprochene Interaktion immer eine Option ist. Um Allgegenwart zu erreichen, sind zwei Dinge erforderlich: Verfügbarkeit (dh Integration in jede mögliche Interaktion, in der Spracheingabe oder -ausgabe sinnvoll sein kann) und Leistung (dh Funktioniert so gut, dass die Modalität der Interaktion keine Reibung hinzufügt).
Ein weiterer Bereich, in dem Google Mathematik einsetzt, sind die Karten - im Rampenlicht der jüngsten Kritik, als Apple sein Kartensystem auf den Markt brachte. Das Herzstück von Google Maps ist die grundlegende Graphentheorie - die Mathematik, von einem Ort zum anderen zu gelangen, während Sie die kürzeste Strecke zurücklegen. Aber es ist natürlich komplexer. Tordable schreibt: "Ein einzigartiges Problem ist, dass die in Google Maps verwendeten Grafiken Millionen von Knoten enthalten, die Algorithmen jedoch in Millisekunden ausgeführt werden müssen."
Google wird uns nicht sagen, wie sie das tun. Andernfalls wäre Apple nicht auf das Problem gestoßen, aber die Grundlagen bestehen darin, den Dijsktra-Algorithmus (wahrscheinlich den am häufigsten verwendeten Graphensuchalgorithmus) zu entfernen. Vor einigen Jahren haben Informatiker der Universität Karlsruhe eine neue Methode beschrieben, um Pfadabfragen zu ordnen, um viel schnellere Ergebnisse zu erzielen. Sie schrieben:
Unser Algorithmus verarbeitet die achtstellige Anzahl von Knoten, die für Karten der USA oder Westeuropas benötigt werden, in wenigen Stunden im linearen Raum vor. Kürzeste (dh schnellste) Pfadabfragen benötigen dann ungefähr acht Millisekunden, um exakt kürzeste Pfade zu erzeugen. Dies ist ungefähr 2000-mal schneller als bei Verwendung des Dijkstra-Algorithmus.
Tordable führt eine Reihe weiterer mathematischer Tools durch, die von Google verwendet werden, darunter diejenigen, die an Google Books, Bildersuchen, Analysen, YouTube, Google Translate, Google Earth und Picasa beteiligt sind. Sie können den gesamten Foliensatz hier sehen.
Mehr von Smithsonian.com:
Smithsonian erhält Google Mapped
Verfolgen Sie Food-Trends mit Google Books
