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