Achter alle informatieverwerking van Google - van het uitzoeken welke zoekresultaten het belangrijkst zijn tot het lezen en bijhouden van uw e-mail - is er een aantal interessante wiskunde. En onlangs heeft Javier Tordable, een software-ingenieur, er een presentatie over gegeven, die een venster opende in de geeky Google-wereld, gewoon een scheur.
Laten we beginnen met Gmail. Soms krijg je spam-mail, maar Gmail is er behoorlijk goed in om uit te vinden dat, wanneer een correspondent je probeert te krijgen om te investeren in een Nigeriaanse prins, je dat stuk post waarschijnlijk niet in je inbox wilt hebben. Hoe weet het Stap één: train de machine. Stap twee: zet het aan het werk.
Het wordt machine learning genoemd en Google doet er veel van. In stap één moet je doen wat computerwetenschappers 'een instantie karakteriseren' noemen. In wiskunde-spreken betekent dat:
Over het algemeen kunnen de kenmerken van een instantie worden beschouwd als elementen in een vector van een e-dimensionale euclidische ruimte voor een grote n (100-1000 dimensies zijn normaal, 1M-10M is niet ongehoord)
Maar hier is hoe je erover kunt nadenken als je na Calc 1 stopt met rekenen. Gmail kan een paar belangrijke stukjes informatie uit een bepaalde e-mail halen. Hoe lang is het? Hoeveel hoofdletters zijn er? Is dit van iemand van wie je eerder een e-mail hebt ontvangen? U wilt niet dat de informatie die nodig is om de beslissing te nemen te moeilijk is om te krijgen of af te handelen, omdat dat de nauwkeurigheid van uw machine zal vertragen en verminderen. Google trekt dus een lijn, gebaseerd op wat het weet over spam. De e-mails die erdoorheen komen vallen aan de ene kant van de regel, en de spamachtige, aan de andere kant.
Meer wiskunde spreken:
Een eenvoudig classificatiemodel is een hyperplaneet in de ruimte van kenmerken. Gegevensinstanties aan de ene kant van het hyperplane worden geclassificeerd als geldige e-mails en instanties aan de andere kant worden geclassificeerd als spam.
Hoe zit het met zoeken naar spraak - ook wel automatische spraakherkenning of ASR genoemd? Net als machine learning gebeurt ASR in twee delen: het binnenkomende geluid verwerken en uitzoeken wat je zegt. Het eerste deel omvat Fourier-transformaties, die de belangrijke bits isoleren die de computer kan vertalen. Het tweede deel is het modelleren van spraak met behulp van een zogenaamd 'verborgen Markov-model'. Tordable legt uit:
In dit model zijn de toestanden de letters van het bericht en de volgorde van gebeurtenissen is het geluidssignaal. Het Viterbi-algoritme kan worden gebruikt om de volgorde van maximale waarschijnlijkheden te verkrijgen.
Google wil graag spraakherkenning beter en eenvoudiger maken. In deze case study schrijft een groep Google-whizzes:
Een doel bij Google is om gesproken toegang overal beschikbaar te maken. We willen de gebruiker laten kiezen - ze moeten ervan kunnen uitgaan dat gesproken interactie altijd een optie is. Het bereiken van alomtegenwoordigheid vereist twee dingen: beschikbaarheid (dwz ingebouwd in elke mogelijke interactie waar spraakinvoer of -uitgang zinvol kan zijn), en prestaties (dwz werkt zo goed dat de modaliteit geen wrijving toevoegt aan de interactie).
Een ander gebied waar Google wiskunde gebruikt, staat in hun kaarten - recent in de schijnwerpers nadat Apple hun kaartensysteem debuteerde met veel kritiek. De kern van Google Maps is de basistheorie: de wiskunde om van de ene plaats naar de andere te komen terwijl u over de kortste afstand reist. Maar het is natuurlijk complexer dan dat. Tordable schrijft: "Een uniek probleem is dat de grafieken in Google Maps miljoenen knooppunten bevatten, maar de algoritmen moeten in milliseconden lopen."
Google zal ons niet vertellen hoe ze dat doen. Anders zou Apple het probleem niet zijn tegengekomen, maar de basis houdt in dat het algoritme van Dijsktra moet worden weggenomen (waarschijnlijk het meest gebruikte algoritme voor het zoeken naar grafieken). Een paar jaar geleden beschreven computerwetenschappers van de Universiteit van Karlsruhe een nieuwe manier om padvragen te rangschikken om veel snellere resultaten te krijgen. Zij schreven:
Ons algoritme verwerkt het achtcijferige aantal knooppunten dat nodig is voor kaarten van de VS of West-Europa in een paar uur met behulp van lineaire ruimte. Kortste (dat wil zeggen snelste) padquery's duren vervolgens ongeveer acht milliseconden om exact kortste paden te produceren. Dit is ongeveer 2.000 keer sneller dan het algoritme van Dijkstra.
Tordable doorloopt een aantal andere wiskundige hulpmiddelen die door Google worden gebruikt, waaronder die betrokken zijn bij Google Boeken, Afbeeldingen zoeken, Analytics, YouTube, Google Translate, Google Earth en Picasa. Je kunt hier de hele set dia's zien.
Meer van Smithsonian.com:
Smithsonian krijgt Google in kaart gebracht
Houd voedseltrends bij met Google Boeken
