Зад цялото разрушаване на информацията на Google - от измислянето кои резултати от търсенето са най-важни, до четенето и воденето на раздели в имейла ви - има някаква интересна математика. И наскоро Хавиер Тордидж, софтуерен инженер, направи презентация на него, като отвори прозорец в страховития свят на Google само пукнатина.
Нека започнем с Gmail. Понякога получавате спам поща, но Gmail е доста добър да разбере, че когато кореспондент се опитва да ви накара да инвестирате в нигерийски принц, вероятно не искате това парче поща във вашата пощенска кутия. Как се знае? Първа стъпка: обучете машината. Стъпка втора: пуснете го на работа.
Нарича се машинно обучение и Google прави много от това. В първа стъпка трябва да направите това, което компютърните учени наричат „характеризиране на инстанция.“ В математика-говоренето това означава:
Като цяло характеристиките на един екземпляр могат да се разглеждат като елементи във вектор на двуизмерно евклидово пространство за голям n (100-1000 измерения са нормални, 1M-10M не е нечувано)
Но ето как да мислите за това, ако сте спрели математиката след Calc 1. Gmail може да изтегли няколко ключови информации от всеки конкретен имейл. Колко е дълго? Колко главни букви има? Това ли е от някой, от когото сте получили имейл от преди? Не искате информацията, необходима за вземане на решението, е твърде трудно да се получи или да се справи, защото това ще забави и ще намали точността на вашата машина. Така Google изготвя линия въз основа на това, което знае за спама. Имейлите, които получават, попадат от едната страна на линията, а спам - от другата.
Повече математика говори:
Един прост класификационен модел е хиперплан в пространството от характеристики. Примери за данни от едната страна на хиперплана са класифицирани като валидни имейли, а случаите от другата страна са класифицирани като спам.
Какво ще кажете за гласовото търсене - наричано също автоматизирано разпознаване на реч или ASR? Подобно на машинното обучение, ASR се случва в две части: обработка на звука, който влиза и измисляне на това, което казвате. Първата част включва преобразувания на Фурие, които изолират важните битове, които компютърът може да преведе. Втората част е моделиране на реч, използвайки така наречения „скрит модел на Марков“.
В този модел състоянията са буквите на съобщението, а последователността на събитията е звуковият сигнал. Алгоритъмът на Витерби може да се използва за получаване на последователността на състояния с максимална вероятност.
Google би искал да направи разпознаването на гласа по-добро и по-лесно. В този случай група от уиски на Google пише:
Целта на Google е да предоставят повсеместно достъп до говорим достъп. Бихме искали да позволим на потребителя да избере - те трябва да могат да го приемат за даденост, че разговорното взаимодействие винаги е опция. Постигането на повсеместност изисква две неща: наличност (т.е., вградена във всяко възможно взаимодействие, където въвеждането или извеждането на реч може да има смисъл) и производителността (т.е. работи толкова добре, че модалността не добавя триене към взаимодействието).
Друга област, в която Google използва математиката, е в техните карти - в светлината на прожекторите наскоро, след като Apple дебютира системата им за картографиране до значителна критика. В основата на Google Maps е основната теория на графиките - математиката да стигате от едно място на друго, докато изминавате най-краткото разстояние. Но, разбира се, е по-сложно от това. Изкусително пише: „Един уникален проблем е, че графиките, използвани в Google Maps, съдържат милиони възли, но алгоритмите трябва да работят в милисекунди.“
Google няма да ни каже как правят това. В противен случай Apple не би се сблъскал с проблема си, но основните са свързани с разклащане на алгоритъма на Dijsktra (вероятно най-често използваният алгоритъм за търсене на графики). Преди няколко години компютърните учени от университета в Карлсруе описаха нов начин за класиране на заявките по пътя, за да получат много по-бързи резултати. Те написаха:
Нашият алгоритъм преработва осемцифрения брой възли, необходими за карти на САЩ или Западна Европа за няколко часа, използвайки линейно пространство. Най-късите (т.е. най-бързите) заявки за път след това отнемат около осем милисекунди, за да се получат точни най-кратки пътища. Това е около 2000 пъти по-бързо от използването на алгоритъма на Dijkstra.
Tordable преминава през редица други математически инструменти, използвани от Google, включително тези, които участват в Google Книги, Търсене на изображения, Анализ, YouTube, Google Translate, Google Earth и Picasa. Можете да видите целия набор от слайдове тук.
Още от Smithsonian.com:
Smithsonian получава Google Mapped
Проследявайте тенденциите в храните с Google Книги
