Съемочная группа ПостНауки во главе с главным редактором отправилась не абы куда, а в Яндекс, чтобы посмотреть, какое прикладное значение имеет в мире современных технологий фундаментальная наука. Мы встретились с Андреем Райгородским, доктором физико-математических наук, руководителем отдела теоретических и прикладных исследований компании «Яндекс», и профессором МГУ и МФТИ.
Введение
Есть подозрение, что пытаться рассказать своими словами речь Райгородского здесь, на Хабре, неслыханная наглость и нелепица. Хаброчитатели, наверняка, разбираются в этом и не нуждаются в повторении. Поэтому, чтобы не переливать из пустого в порожнее, я приведу цитаты Андрея, а вы можете их дополнить в комментариях.
Андрей Райгородский: «Для человека, который совсем не знает, что такое граф, правильно рассказывать в совершенно конкретных терминах. Представьте себе, что у вас есть большая пространственная молекула, которая состоит из жестких шариков, неважно, из чего сделанных (из картона, из металла). И эти шарики между собой перелинкованы, то есть соединены проволочками, прямолинейными отрезками. Получается жесткая конструкция, которую в математике принято называть графом. Это чисто наглядная интерпретация – в виде молекулы. Хотя мне думается, она кажется удобной всякому, кто пытается представить, что такое граф.
Абстрактно же граф устроен таким образом – у него есть множество вершин и множество ребер. Собственно, те шарики, которые мы видим в пространстве – это вершины графа. А проволочки, которые их соединяют – это ребра графа. Если говорить в абстрактных терминах, вершины – это просто некоторые конечные множества каких-то элементов.
Неважно, какой природы эти элементы. Это могут быть люди, например, между которыми есть какие-то отношения. Это могут быть натуральные числа, сайты в интернете, биологические объекты, например, белки. Могут быть совершенно абстрактные элементы какого-то множества.
Ребра, которые соединяют некоторые пары, – это суть пары этих элементов. То есть, мы говорим, что два элемента соединены ребром. И всё. Про каждые два элемента мы можем сказать, они соединены ребром или нет. Но это зависит от того, как мы определим.
В абстрактной ситуации мы можем определить как угодно, просто взяв конечное множество элементов, и какие-то пары этих элементов, соединив ребрами. Получится конструкция в пространстве, например, расположенная или на плоскости. Как вы ее нарисуете, так и будет».
«Еще в XIX веке была классически поставленная задача, которая касалась раскраски карт. Вот у вас есть карта мира. На ней нарисованы какие-то страны. Естественно, вам нужно каждую страну покрасить в определенный цвет таким образом, чтобы страны, которые граничат между собой, были разных цветов. Если они будут одинакового цвета, они просто сольются воедино. И вы не сможете их отличить. Спрашивается, как много цветов потребовалось для произвольной карты, чтобы осуществить такую покраску?
Гипотеза была, что четырех красок всегда хватит, если выполнены какие-то естественные ограничения относительно свойств границ этих стран, их взаимного расположения. Если нет анклавов типа Калининграда, то карта считается правильной, грубо говоря. И хочется ее покрасить каким-то образом в четыре цвета. Это естественным образом связывается с теорией графов. Мы просто каждой стране присваиваем абстрактную вершину (если угодно, ее столицу). И получаются вершины графа – столицы этих стран.
Дальше мы соединяем ребром (если хотите дорогой) две столицы, которые являются главными городами тех стран, которые между собой граничат. У нас получается граф. Его вершины отвечают странам. Ребра – это пары вершин, которые отвечают столицам граничащих между собой стран. И мы хотим покрасить вершины этого графа (то есть, страны) в минимальное количество цветов таким образом, чтобы вершины, соединенные ребром, были покрашены в разные цвета. Задача четырех красок – это великая классическая проблема, которая до сих пор полностью не решена. Она решена с помощью компьютерного перебора, но ручного, чисто аналитического доказательства того, что четырех красок всегда хватит, до сих пор нет».
Случайность
Направление случайных графов — одно из самых интересных в математике сейчас. Оно связано с теорией Эрдеша – Реньи, эти венгерские математики предложили ввести случайность на множестве графов.
А.Р.: «Они сказали так: «Давайте рассмотрим какое-нибудь фиксированное множество из n. вершин, неважно, из чего состоящее. Пусть это будет абстрактное n. объектов. Например, натуральные числа 1, 2…n. Мы хотим ребра проводить между ними случайно».
Понятно, какое количество есть ребер. Но каждые две вершины потенциально могли бы быть соединены ребром. Давайте возьмем какие-нибудь две вершины – бросим монету. Монетка, правда, со смещенным центром тяжести. Она теоретически или практически (я не знаю, как лучше сказать, но правильней всего сказать – статистически) падает «орлом» чаще, чем решкой. Когда вы ее бросаете на стол, вероятность того, что она упадет «орлом» кверху не такая же, как вероятность того, что она упадет кверху решкой. То есть, если бы монетка была сделана из идеально однородного материала, тогда такого бы, конечно, не произошло. В среднем в половине раз она бы выпадала решкой кверху, в половине раз орлом. Этого довольно естественно ожидать. Но у нас смещенная нехорошая монетка. Вероятность того, что она упадет решкой кверху – это какое-нибудь число Р. из отрезка 0 – 1. А вероятность того, что она упадет кверху «орлом» – это, соответственно, 1 – Р, потому что, конечно, мы предполагаем, что монетка не падает на бок – на ребро не становится и в воздухе не зависает. То есть, есть только две возможности: или она падает «орлом» кверху или она падает кверху решкой.
Давайте считать, что если она решкой падает кверху с вероятностью Р., то при выпадении решкой мы проводим, соответственно, ребро между фиксированными нами вершинами. А если нам не посчастливилось, она упала ребром, то ребра не появится. И так делаем с каждой парой вершин, которая есть в нашем распоряжении. У нас n. вершин. И каждую пару мы испытываем с помощью такой монетки. Это называется в науке (в теории вероятности) схема испытания бернулли. Мы просто много раз бросаем монетку и каждый раз фиксируем – выпала она кверху решкой или «орлом». В зависимости от этого, либо мы принимаем решение провести очередное ребро – эту связь между вершинами, либо принимаем решение его не проводить. В итоге у нас, конечно, получается случайный граф – то есть граф, у которого ребра возникли в результате бросания монеты, по воле случая. Такие графы называются классическими или графами Эрдеша – Реньи».
Степенной закон
«Задач в теории случайных графов великое множество. Можно говорить о том же хроматическом числе случайного графа. Есть очень красивая интересная наука о том, как ведет себя хроматическое число случайного графа по модели Эрдеша – Реньи. Задачи практического характера, которые очень интересны с точки зрения случайных графов, это задачи построения адекватных моделей случайных графов, которые описывают поведение каких-то реальных сетей.
Под реальными сетями можно понимать, например, интернет, у которого вершины – это (в зависимости от интерпретации) либо сайты, либо страницы, либо еще какие-то структурные единицы. А ребра – это, как правило, гиперссылки. Получается здоровенный объект, который изменяется со временем. Граф как-то эволюционирует. Новые сайты появляются, появляются новые связи между ними.
Если вернуться к пространственной интерпретации, то у нас получается молекула, которая с течением времени прирастает, что-то у нее, наоборот, исчезает, схлопывается. Связи пропадают, появляются новые.
Оказывается, что молекула, которая описывает, например, интернет или описывает какие-то биологические сети, транспортные сети, сети, возникающие в социологии, не совершенно хаотически изменяется, а подчиняется некоторым интересным статистическим закономерностям. Можно, с одной стороны, наблюдать на практике как устроены эти закономерности, а с другой стороны, пытаться придумать адекватные модели случайных графов, отличные от классической модели (потому что классическая модель этого все таки не описывает), которые бы с высокой вероятностью обладали бы теми же самыми свойствами, что мы и пронаблюдали на практике.
Например, известно. Что распределение степеней вершин в интернете, то есть, грубо говоря, вероятность того, что случайно выбранная вершина в графе интернета имеет заданную наперед степень количества ребер, которые с ней соединены. Это распределение себя ведет очень специфическим образом. Это называется степенной закон».
Что делать со спамом
«Представьте себе, что у вас есть какая-то модель случайного графа, которая действительно очень адекватно и хорошо описывает интернет в том смысле, что по своим вероятностным характеристикам она великолепно ложится на эмпирически данные, полученные нами из интернета. То есть, мы знаем, что веб-граф развивается по определенным закономерностям. И, о чудо, мы придумали такую модель случайного графа, в которой с высокой вероятностью все эти закономерности выполнены. Это сложная задача, но частично она решена. Мы уже имеем некоторое первое приближение к тому, как правильно смоделировать поведение интернета. Представим себе, что она полностью решена.
У нас, допустим, есть идеальная модель, которая предсказывает нам, как должен вести себя интернет, если в нем нет внешних неправильных воздействий. Теперь давайте представим себе, что нам надо поймать какой-нибудь спам, который имеет, что называется, ссылочный характер. Ссылочный характер спама устроен следующим образом – есть какая-нибудь структура, построенная зловредными оптимизаторами.
Структура рассчитана, естественно на то, чтобы те сайты, которые находятся внутри этой структуры, легче находились в процессе поиска. То есть, вы задаете какой-то поисковый запрос. Вы хотите получить на него адекватный ответ. А спамеры стараются сделать так, чтобы вы на него получили ответ, состоящий из тех сайтов, которые интересны спамерам. И они эти сайты искусственно накручивают в выдаче. В частности, важным фактором выдачи является, конечно, количество ссылок на этот сайт или количество каких-то цитирований тех ребят, которые цитируют тебя и так далее.
Важно смотреть на локальную структуру графа вокруг той конструкции, которую, возможно, построили спамеры. Как правило, они строят такие конструкции, которые действительно достаточно плотно перелинкованы для того, чтобы обмануть поисковую систему. Поисковая система подумает «О, это крутой участок. Тут действительно находятся сайты, которые высоко цитируемы. Поэтому их стоит выдавать наверх в топ выдачи». И таким образом спамеры победят.
Что мы можем сделать? Мы можем с помощь какого-то алгоритма (естественно, не собираюсь говорить, какого) изловить много-много структур, которые потенциально могли бы оказаться плохими, то есть, достаточно плотно, густо перелинкованными. А потом посмотреть: в этой идеальной модели мира, которую мы придумали с помощью теории графов и теории вероятности, появление каждой конкретной структуры (из найденных с помощью алгоритма), имеет высокую вероятность или низкую?
Если с точки зрения модели случайного графа, которая призвана описывать поведение разумного интернета, вероятность такой структуры высока, то спамерская конструкция, наверное, ее не может никак понижать в выдаче. Не нужно ей присваивать утяжеляющие места, чтобы она все-таки улетала. А если у нее вероятность крайне низкая в рамках нашей идеальной модели, тут уже надо как-то ее заподозрить. Может быть, поставить ей какой-то флажок в рамках ранжирования, чтобы она появлялась, возможно, не на самой высокой позиции. А может быть, забанить. Надо уже глазами посмотреть. Если она действительно плохая, давайте забаним. Таких структур не очень много. Почему бы и нет. Но это все можно делать в автоматическом режиме, пользуясь ожиданием, которое мы имеем в рамках хорошей модели, и реальностью. То есть, действительно, количеством ребер (ссылок) и так далее. Тут я никаких секретов не открываю. Это очень естественные вещи».
Будущие ловцы спама: кто это?
Чтобы решить задачи, лежащие в области теории графов, и проблемы, связанные с интернетом и новыми технологиями, нужны учены, которые занимаются комбинаторикой и теорией графов, теорией вероятности и случайными процессами. Во всем мире сейчас открываются лаборатории, а в университетах делают на эту область большой акцент. Кроме того, с этим связана и биоинформатика. О задаче хранения и обработки данных, получаемых биологами, мы уже говорили, точнее, рассказывал микробиолог Константин Северинов.
Такие специалисты нужны не только в интернете, не только в связи с контролем и распространением информации, но и в банковских структурах, в исследовании вопросов о финансовых кризисах, которые также связаны с теорией случайных графов.
Андрей Райгородский: «Я скажу вкратце, чем конкретно занимается мой отдел в «Яндекс». Это довольно большой отдел, в котором сейчас работает больше тридцати исследователей и разработчиков. Он построен по такой схеме, что есть довольно значительный кусок отдела, который встроен в продуктовую часть «Яндекса», и он получает часть своих заданий от непосредственных разработчиков – от тех, кто занимается поиском, задачами, в первую очередь интересными «Яндексу» как поисковой системе, строит какие-то сервисы. Эти люди занимаются исследованиями не чисто математического характера, а скорее, наоборот – попытками прилагать какие-то математические идеи к реализации содержательных проектов.
А есть кусок отдела, который, собственно, генерирует такие идеи. То есть, все построено достаточно естественным образом. Есть кусок, который непосредственно в продаже. Есть кусок, который занимается генерацией идей, производством научных публикаций как на индустриальных конференциях, так и в журналах чисто математического содержания. И здесь какие основные направления исследований, которые мы ведем? Конечно, нам очень интересны графы. И мы строим модели различных графов, которые адекватно описывают VEB. Наверное, мы пока еще не успели построить идеальную модель. Но у нас есть довольно неплохие продвижения в этом направления. У нас получаются модели, действительно достаточно адекватно описывающие поведение веба. Их тоже удается применять на практике, как я уже говорил.
Есть направление, связанное с исследованием машинного облучения. Есть направление, связанное с задачами абстрактной теории случайных графов".
Послушать Андрея и посмотреть на интерьеры Яндекса можно по ссылке.
Автор: JuliaP
