Эксклюзив: Как алгоритм Google управляет интернетом

[arh_lelik1]

От переводчика: не думаю, что открываю Америку этим переводом, по большому счету искушенный хабрапользователь не найдет для себя много нового и необычного. Однако, на мой взгляд, это неплохая общеобразовательная статья, в которой удобно собраны и рассмотрены основные вехи и принципы работы поисковых машин. Оригинал статьи опубликован в журнале Wired за март 2010 года. Предупреждаю сразу — статья длинная.

 

Хотите ли вы узнать, как Google собирается изменить вашу жизнь? Остановитесь около комнаты совещаний Уагадугу во вторник утром. Это решается здесь, в Калифорнии, в Маунтин Вью, в головном офисе самой влиятельной интернет-компании в мире, в комнате, наполненной тремя десятками инженеров, менеджеров и руководителей, которые определяют, как сделать поисковую машину еще умнее. В этом году компания Google представила около 550 усовершенствований в свой легендарный алгоритм, и каждое определяет выдачу информации. Благодаря решениям, принятым на еженедельном совещании по качеству поиска, результаты поиска чего угодно — «Samsung SF-755p принтер», «Эд Харди страничка на MySpace» или, может быть, «столица Буркина Фасо» поднимутся в списке результатов поиска только потому, что эти запросы будут упомянуты на совещании. Руководит процессом Уди Мэнбер, глава Google по поиску с 2006 года. Предполагаемые изменения вместе с результатами месяцев тестирования в различных странах и на всевозможных языках представляются одно за другим. На экранах рядом друг с другом отображаются результаты запросов до и после изменения. Следом за выдачей результата поиска «гитарный центр вау-вау» — Мэнбер кричит: «Получилось!»

 

Возможно, вы считаете, что после десятилетнего безусловного доминирования на поисковом рынке Google может расслабиться. Сейчас эта компания контролирует 65 процентов всех поисковых запросов, и она единственная, чье имя синонимично слову «поиск». Но так же как Google не готов почивать на лаврах, так и его конкуренты не готовы признать поражение. Согласно заявленым целям и задачам, в течение многих лет гигант Силиконовой долины использовал свой таинственный, кажущийся всеведущим алгоритм для «организации мировой информации». Но за несколько последних лет множество компаний бросили вызов Google в сфере его основной деятельности: они бросили вызов поисковой машине, которая благодаря технологическому волшебству и постоянному усовершенствованию может удовлетворить любой возможный запрос. Facebook приблизился к позициям Google, расчитывая, что люди будут больше доверять советам друзей, а не результатам работы безликой формулы. Благодаря возможностям синтаксического разбора своего непрерывного потока сообщений, Twitter представил концепцию поиска в режиме реального времени, перехватывая последние разговоры и обсуждения по мере того как они разворачиваются. Yelp помогает людям найти рестораны, уборщиков и нянек, используя поиск по рейтингу. Ни один из этих новых сервисов не представляет угрозы сам по себе, однако все вместе они прогнозируют будущее, в котором поиск будет открытым и широким, и в котором царит не просто поисковая машина, а скорее набор различных поисковых сервисов.

 

Кроме того, наибольшая угроза для Google находится в полуторе тысяч километрах к северу: Bing. Переделанный и переименованный компанией Microsoft поисковый сервис с именем, которое, по задумке, должно напоминать о восклицании «Bingo!» — «Эврика!» (а может, это имя известного американского певца или название стрип-бара из сериала The Sopranos), был запущен в июне прошлого года с довольно оптимистичными прогнозами. (The Wall Street Journal назвал ее «более привлекательным, чем Google»). Обновленный внешний вид и рекламная кампания в 100 миллионов долларов помогли увеличить долю запросов на поисковом рынке США с 8 до примерно 11 процентов, и это количество увеличится вдвое, как только регулирующие органы позволят использовать поисковую машину Bing для Yahoo.

 

Команда Bing сосредоточилась на отдельных случаях, в которых алгоритмы Google не всегда показывают удовлетворительные результаты. Например, в то время как Google отлично справляется с индексированием публичных интернет-сайтов, он не имеет доступа в режиме реального времени к запутанным и постоянно меняющимся массивам данных о вылетах и прибытях самолетов. Microsoft покупает Farecast — интернет сайт, который постоянно отслеживает тарифы авиаперевозчиков для предсказания роста или падения цен на билеты — и предоставляет свои данные в поисковой выдаче Bing. Microsoft совершил подобные приобретения в области здравоохранения, нормативных документов, а также покупки и продажи товаров и услуг — в областях, где по их расчетам, алгоритмы Google несовершенны.

 

Но даже в компании Bing признают, что если нужно просто ввести слово для поиска и получить релевантные результаты, Google все еще очень далеко впереди. Однако в Bing полагают, что даже при хороших результатах в некоторых предметных областях, где Bing превосходит Google, люди не будут использовать только их сервис и для других запросов. «Алгоритмы необычайно важны в поиске, однако они не единственное, на что нужно обращать внимание», — говорит Брайан Макдональд, вице-президент Microsoft по поиску, — «вы выбираете машину не только по мощности двигателя».

 

Ответ Google можно резюмировать в четырех словах: «mike siwek lawyer mi».

 

Амит Сингал написал, что решение этого коана — в поисковой строке его компании. Сингал, сорокалетний джентельмен, носитель почетного звания «Коллега Google», награжденный четыре года назад премией за переписанный код поисковой машины в 2001 году. Он нажал клавишу «ввод». В мгновение ока появилась страница ссылок. Верхний результат списка ведет к юристу Майклу Сивеку из города Гранд Рапидс в штате Мичиган. Это совершенно безобидный результат поиска — один из тех, которые сервера Google обрабатывают миллиарды раз в день, но он обманчиво сложен. Наберите тот же самый запрос в Bing, к примеру, и первая запись на странице будет о членах национальной футбольной лиги США, одним из которых является игрок по имени Lawyer Milloy. Результаты поиска занимают несколько страниц, но ни на одной нет прямой ссылки на Сивека.

 

Это сравнение показывает силу и даже интеллектуальность алгоритмов Google, отточенных бесчисленное количество раз. Они обладают, кажется, волшебной способностью понимать запросы пользователей, независимо от того, как и насколько грамотно они составлены. Google называет эту способность качеством поиска, и за годы своего существования компания тщательно скрывала процесс, благодаря которому получаются такие точные результаты. Но сейчас я сижу с Сингалом в Здании №43 поискового гиганта, где работает отдел разработки поискового ядра, так как Google дала мне беспрецендентную возможность посмотреть, каким образом достигается качество поиска. Причина этого очевидна: вы можете думать, что алгоритм это немного больше, чем вся машина, но подождите, пока мы не приоткроем завесу и не увидим, на что способен этот алгоритм.

 

Ключевые особенности поиска Google

 

«Алгоритмы поиска Google постоянно изменяются и совершенствуются для получения результатов высочайшего качества. Представляем несколько наиболее знаменательных расширений и улучшений с появления индекса цитирования страниц». — Стивен Леви.

 

Backrub (сентябрь 1997) — поисковая машина, которая работала на серверах Стэнфордского университета почти два года, получившая название Google. Ее основа — ранжирование страниц в зависимости от количества и качества внешних ссылок — было крупным техническим достижением.

 

Новый алгоритм (август 2001) — поисковый алгоритм был полностью реорганизован, чтобы упростить добавление новых факторов ранжирования.

 

Анализ взаимосвязей (февраль 2003) — первая запатентованная особенность Google, которая ранжирует более высоко те сайты, на которые ссылаются более авторитетные источники.

 

Fritz (лето 2003) — это улучшение позволяет Google модернизировать индексацию в любой момент, а не только крупными блоками обновлений.

 

Персонализированные результаты (июнь 2005) — пользователи могут разрешать Google отслеживать историю их поиска для обеспечения персонализированных результатов.

 

Bigdaddy (декабрь 2005) — обновление машины позволило более полную индексацию сети интернет.

 

Универсальный поиск (май 2007) — новый универсальный поиск, построенный на поиске картинок, новостях Google и поиске по книгам позволил пользователям получать информацию, представленную в различном виде на единой странице результатов поиска.

 

Поиск в режиме реального времени (декабрь 2009) — отображает результаты из Twitter и блогов сразу после публикации.

 

История алгоритма Google начинается с введения индекса цитирования страниц, системы, изобретенной в 1997 году сооснователем Google Ларри Пейджем во время учебы в Стэнфорде. Ставшее легендарным озарение Пейджа заключалось в ранжировании страниц в зависимости от количества и важности ссылок, ведущих на них. Таким образом использовался коллективный разум сети интернет для определения релевантности сайтов. Эта концепция проста и обладает широкими возможностями, и, поскольку Google быстро стал наиболее успешной поисковой машиной в интернете, Пейдж и Сергей Брин, второй основатель Google, расценивают индекс страниц как фундаментальную инновацию их компании.

 

Однако это еще не все. «Люди поддержали идею индекса цитирования страниц, потому что она понятна», — говорит Мэнбер, — «но существует множество других особенностей, которые улучшают релевантность выдачи». Это использование определенных факторов, контекстных признаков, которые помогают поисковой машине ранжировать миллионы возможных результатов запроса, обеспечивая попадание наиболее полезных в верх списка.

 

Поиск по сети интернет — это процесс, состоящий их нескольких этапов. Сначала Google анализирует веб-страницы, собирая информацию со всех доступных сайтов. Затем эта информация разделяется и индексируется (организуется по алфавиту, примерно как в словаре). Поиск нужной страницы основывается на информации, которую она содержит. Каждый раз, когда пользователь вводит запрос, проиндексированная информация прочесывается в поисках нужного ответа и пользователю возвращается список, обычно содержащий сотни тысяч или миллионов вхождений. Весь фокус, однако, состоит в ранжировании — определении, какой из ответов поставить во главу списка.

 

Вот где приходят на помощь контекстные признаки. Все поисковые машины используют их, но ни одна не учитывает такое количество факторов, а может, не использует их с таким опытом, как Google. Индекс цитирования страницы — это один из факторов, атрибут веб-страницы (получается, что его величина важна для каждого сайта в сети интернет), который помогает определить релевантность страницы. Некоторые факторы сейчас кажутся очевидными. На ранних этапах алгоритмы Google уделяли особое внимание заголовку страницы — это, безусловно, важный признак для определения релевантности. Другой ключевой фактор использует текст тела рабочих ссылок, которые ведут с одной страницы на другую. В результате «когда производится поиск, нужная страница будет сверху, даже если она сама не содержит слов, которые вы ввели в запрос», — говорит Скотт Хасан, который был архитектором Google на ранних этапах и работал вместе с Пейджем и Брином в Стэнфорде, — «это было круто». Позже факторами стали также свежесть информации (по одинаковым запросам более поздние страницы могут быть более полезными, чем старые) и географический фактор (Google может грубо определить географические координаты пользователя и предпочтет результаты, которые ближе к его местоположению). Сейчас поисковая машина использует более 200 факторов для ранжирования результатов.

 

Инженеры Google открыли, что некоторые из наиболее важных факторов могут быть найдены благодаря самой сути работы Google. Индекс цитирования страницы признан выдающейся системой для определения популярности поисковыми машинами: миллионы людей сами определяют, на что ссылаться в сети. Это настоящая демократия. Но Сингал заметил, что инженеры из здания №43 используют еще одну демократию — работу сотен миллионов людей, которые ищут через Google. Данные, создаваемые пользователями в процессе поиска — по каким результатам они переходят, какие слова они заменяют в запросе, если результат их не удовлетворяет, как их запросы зависят от географического местоположения — оказываются бесценными сведениями для определения новых факторов и улучшения поисковой выдачи. Самый очевидный пример этого процесса — это персонализированный поиск Google, особенность, которая использует историю запросов пользователя и его местоположение как факторы для определения релевантности результата. Но в основном Google использует эту огромную массу накопленных данных для корректировки алгоритма. Таким же образом используется необычайно глубокая база знаний, которая помогает интерпретировать общий смысл критически важных запросов.

 

Возьмем, к примеру, метод, по которому Google определяет синонимы. «Мы нашли ловкий способ», — говорит Сингал, — «люди изменяют слова в запросах. Например, кто-то набирает «картинки собак», а потом «картинки щенков». Таким образом мы понимаем, что, возможно, «щенки» и «собаки» взаимозаменяемы. Мы также учли, что если вы вскипятили воду, то это горячая вода. Благодаря пользователям мы заново выучили семантику, и это дало очень большой шаг вперед».

 

Однако существуют некоторые преграды. Система определения синонимов Google понимает, что собаки похожи на щенков и что вскипяченая вода горячая. Но она также решит, что горячая собака (хот-дог) это тоже самое, что вскипяченый щенок. Эта проблема была устранена в конце 2002 года новаторским обновлением, основанном на теориях философа Людвига Витгенштейна о зависимости смысла слова от контекста. Так как Google собрает и хранит миллиарды документов и веб-страниц, они были проанализированы, для того чтобы понять, какие слова близки по смыслу друг к другу. Словосочетание «Горячая собака» (hot dog) было найдено в запросах, содержащих также «хлеб», и «горчица», и «бейсбол» — не с кипячеными дворнягами. Это помогло алгоритму понимать, что означает слово «хот-дог» и миллионы других терминов. «Сейчас, если вы введете «Gandhi bio», мы знаем, что bio значит биография», — говорит Сингал, — «а если вы введете «bio warfare», то bio значит «биологическая»».

 

На протяжении своей истории Google разработала несколько способов добавления новых факторов ранжированя так, что бы не нарушалась работа пользователей. Каждую пару лет происходит глобальное изменение системы — вроде того, как выходят новые версии Windows. Это большое событие в Маунтин Вью, но оно не выносится на публику. «Наша работа похожа на смену двигателей самолета, который летит со скоростью 1000 километров в час на высоте десяти тысяч метров над землей», — говорит Сингал. В 2001 году, чтобы приспособиться к быстрому росту интернета, Сингал полностью переписал изначальный алгоритм Пейджа и Брина, включив систему быстрого добавления новых факторов поиска. (Один из первых добавленных факторов новой системы разделяет коммерческие и некоммерческие страницы, обеспечивая нужные результаты для пользователей, которые ищут товары или услуги). В том же году инженер Кришна Бхарат предположил, что ссылки с общепризнанных авторитетных сайтов должны иметь больший вес, и разработал влиятельный фактор, который увеличивал степень доверия к ссылкам на компетентных сайтах. (На это был получен первый патент Google). Самое последнее глобальное изменение, названное Caffeine, поправляло систему внесения индексов так, чтобы упростить инженерам добавление новых факторов.

 

Google известна изобретательностью в поощрении подобных нововведений; каждый год компания проводит внутреннюю демонстрационную выставку, называемую CSI (Crasy Search Ideas — безумные поисковые идеи) для выявления необычных, но полезных предложений. Однако, большей частью процесс изменения поисковой машины — это непрекращающаяся изнурительная работа перебора плохих результатов для определения неточностей. Один из безуспешных поисков вошел в легенду: где-то в 2001 году Сингал узнал о плохих результатах поиска по запросу «audrey fino». Google направлял пользователей на итальянские сайты, посвященные Одри Хепберн (fino по-итальянски значит «милая»). «Мы понимали, что на самом деле это чье-то имя», — говорит Сингал, — «но система была не настолько сообразительной».

 

Неудача с «audrey fino» привела Сингала к многолетней разработке способа обработки системой имен собственных — а это 8% всех запросов. Чтобы решить задачу, ему пришлось освоить тайное искусство биграммного шифра, который разделяет различные слова в отдельные взаимосвязанные элементы. Например «new york» представляет собой два неразрывных слова (биграмма). Но также есть «new york times», который очевидно указывает на другой вид поиска. И все снова меняется, если запрос будет «new york times square». Человек сразу видит различие, но у Google нет подвала, заполненного сотнями тысяч операторов за маленькими столиками. Google полагается на алгоритм.

 

Запрос «mike siwek lawyer mi» иллюстрирует, как Google достигает совершенства. Когда Сингал набирает команду чтобы продемонстрировать код под каждым найденным результатом, становится понятно, какие факторы повлияли на выбор самых вырхних ссылок: биграммная связь показывает, что это имя, синоним и географическое местоположение. «Разберем этот запрос с точки зрения инженера», — объясняет Сингал, — «мы видим — ага! Мы можем разбить запрос вот так. Мы вычисляем, что «lawyer» — это не фамилия, а «siwek» — это не имя. И заодно что «lawyer» это не город в Мичигане. «lawyer» — это адвокат».

 

Эта добытая ценой больших усилий реализация внутренней работы поисковой машины Google, собранная благодаря данным, введенным миллиардами пользователей: «rock» — это скала. Еще это камень, а может быть и булыжник. Напишите его как «rokc», и это все равно будет «rock». Но напишите спереди «little» и он станет столицей Арканзаса (Little Rock). А Арканзас (Arkansas) — это не ковчег (ark), но если только рядом нет Ноя (Noah's Ark). «Заветная цель поиска — понять, что хочет пользователь», — говорит Сингал, — «поэтому нужно подбирать не слова, а их значения».

 

И Google продолжает совершенствоваться. Недавно поисковый инженер Морин Хейманс обнаружил проблему с запросом «Cindy Louise Greenslade». Алгоритм понимает, что ему нужно искать человека — в этом случае это психолог из города Гарден Гроув в Калифорнии, но разместить домашнюю страничку Гринслейд в первую десятку результатов не получалось. Хейманс обнаружил, что Google снижает релевантость ее страницы, так как Гринслейд использовала не полное второе имя, как в поисковом запросе, а только его инициал. «Нам нужно учитывать и это», — говорит Хейманс. Поэтому он добавил фактор, который ищет по инициалу второго имени. Сейчас домашняя страница Гринслейд на пятом месте.

 

Сейчас десятки подобных изменений проходят через хорошо отлаженный процесс тестирования. Сотни работников Google по всему миру за своими домашними компьютерами оценивают результаты различных запросов, отмечая, когда изменения в системе улучшают или ухудшают выдачу. Но у Google также есть армия тестировщиков — это миллиарды пользователей, которые невольно виртуально участвуют в постоянном эксперименте над качеством поиска. Каждый раз, когда инженеры тестируют изменения, они запускают новый алгоритм для небольшого процента случайных пользователей, используя их как большую контрольную группу. Исследований изменений настолько много, что Google пришлось отказаться от традиционного научного принципа — в один момент времени должен проводится только один эксперимент. «По большинству запросов к Google вы находитесь в нескольких контрольных или экспериментальных группах одновременно», — говорит инженер по поисковому качеству Патрик Рили и затем поправляет себя — «по правде говоря, все запросы включены в какой-нибудь тест». Другими словами, каждый раз, когда вы что-то ищете через Google, вы являетесь подопытным кроликом.

 

Гибкость — возможность добавлять новые факторы, обновление кода и одновременное тестирование результатов — вот что позволяет Google утверждать, что они выдержат любое соревнование с Bing, или с Twitter, или с Facebook. На самом деле, за последние шесть месяцев Google ввел более 200 улучшений, некоторые из которых кажутся подражаниями, если не сказать больше, предложений их конкурентов. (Google говорит, что это простое совпадение, и обращает внимание на то, что новые особенности добавляются регулярно уже много лет). Одно из них — это поиск в режиме реального времени, с нетерепнием ожидавшийся с тех пор, как Пейдж заявил несколько месяцев назад, что Google будет сканировать весь интернет каждую секунду. Сейчас, когда кто-то вводит интересующий его запрос, среди десяти синих ссылок Google добавляет область с „последними результатами“ — проматывающийся список свеженаписанных записей с новостных ресурсов, блогов и микроблогов. Для этого Google еще раз использует факторы для добавления самых релевантных записей в непрерывно обновляющийся поток. «Мы наблюдаем за ответами на записи, за тем, сколько людей читают их, определяем кто автор — человек или робот», — говорит Сингал, — «мы знаем, как это определить, потому что мы занимаемся этим уже десять лет».

 

Вместе с поиском в режиме реального времени Google представил другие новые особенности, включая сервис, названный Goggles, который в процессе поиска анализирует фотографии с мобильных телефонов. Это — часть непрекращающегося движения навстречу постоянному и повсеместному присутствию поиска в жизни человека. С распознаванием образов и голоса смартфоны стали глазами и ушами. Если найден правильный фактор, предметом поиска может быть что угодно.

 

Грандиозная вычислительная мощность и пропускная способность дает Google неоспоримое преимущество. Некоторые наблюдатели говорят, что это приемущество сильно затрудняет новым сервисам путь от тестов до рабочего режима. Но Мэнбер говорит, что не одна ифраструктура сделала Google лидером: «Очень, очень, очень важная ключевая составляющая — это то, что мы набираем правильных людей».

 

По всем признакам Ки Лу относится к одним из таких людей. «Я испытываю к нему огромное уважение», — говорит Мэнбер, который работал с 48-летним специалистом в области теории вычислительных машин из Yahoo. Но Лу присоединился к Microsoft в начале прошлого года для того чтобы возглавить команду Bing. Когда его спрашивают о его целях, Лу, миниатюрный мужчина, одетый в джинсы и рубашку с логотипом Bing, тихо и размеренно цитирует: „Очень важно помнить, что это долгое путешествие“. При этом он смотрит как Ума Турман в фильме „Убить Билла“ и весь его вид говорит «я не собираюсь уходить».

 

На самом деле, у компании, выигравшей браузерную войну последнего десятилетия, отличный потенциал для хорошего поиска. В то же время эти люди обладают сверхестественной уверенностью, они желают больше, чем может обеспечить алгоритм Google. «Если парадигма не изменится, будет очень-очень трудно соревноваться с сегодняшними триумфаторами», — говорит Гарри Шам, глава разработки ядра поиска в Microsoft. «Но, с другой стороны, парадигма может и измениться».

 

Так или иначе, даже если произойдет подобное изменение, алгоритм Google может приспособиться и к нему. Вот почему Google — грозный противник, он построил машину, достаточно быструю для того, чтобы учесть почти любую угрозу, и пока что конкурентам нечего противопоставить высококачественным результатам поиска Google. Любой может предложить новый способ покупки билетов на самолет. Но только Google знает, как найти Майка Сивека. habrahabr.