Сегодня мы поговорим о моделировании реальности как о способе мышления, восприятия информации и анализа данных. Будем вместе заново изобретать и улучшать модели, которые сегодня используются в поисковых системах: в метриках качества поиска, при создании факторов ранжирования и даже при построении новых интернет-сервисов. Именно этому посвящена лекция Федора Романенко.
Однако прежде чем переходить к основной теме нашей лекции, стоит рассмотреть некоторые философские вопросы, связанные с моделированием.
Человек мыслит моделями, и с их помощью воспринимает и понимает окружающий мир. В качестве иллюстрации этой мысли приведем простую модель мира, в котором существуют только плохие и хорошие парни. Плохие всегда врут, а хорошие говорят правду. Если человек нам один раз соврал, то мы будем считать его плохим парнем, и доверять ему не будем. Но если этот плохой парень вдруг начнет говорить правду, у нас может возникнуть когнитивный диссонанс: несоответствие наблюдаемого, имеющейся у нас модели. Реагировать на это можно по-разному. Некоторые, например, могут отрицать увиденное, и оставаться в рамках своей модели. Однако такой подход очень далек от научного. Правильнее было бы отказаться от принятой модели, либо попытаться ее расширить.
Наиболее удачный подход к получению знаний заключается в следующем: у нас есть некоторый опыт (эмпирическое знание), на основе которого мы создаем некие теории и модели. Все гипотезы, которые мы можем придумать, изначально равноправны. Они могут объяснять имеющийся у нас опыт или его часть, а также предсказывать новый опыт. Модель не обязательно должна быть точной, она может быть и приблизительной, главное, чтобы она помогала нам что-либо понять, объяснить или предсказать. Вообще говорить о правильность или неправильности модели — не совсем верно, модель нужно воспринимать с точки зрения ее полезности. Например, после изобретения теории относительности стало ясно, что ньютоновская механика не совсем верна. Но при этом модель, которую она представляет, очень полезна, она помогает объяснять и предсказывать многие вещи.
Очень полезен для ученых принцип, известный как «бритва Оккама». Он подразумевает, что вводить в модель сущности без необходимости не нужно. Если можно составить более простую модель с той же полезностью, то пользоваться лучше ей.
Разработка поиска и анализ данных — тоже своего рода научная работа из области выявления высокоуровневых закономерностей. У нас есть огромные массивы данных, логи действий пользователей, на основе которых можно составлять модели, предсказывать действия, и, опираясь на это, делать хорошие сервисы. При этом пространства для моделирования тут гораздо больше, чем, например, в физике, где новые модели появляются крайне редко. В поиске новые модели можно придумывать хоть каждый день, и каждая из них будет в чем-то полезна.
Для примера поговорим о модели PageRank, которая считается на графе веб-страниц и веб-ссылок. Интернет можно представить в виде графа, где вершинами будут страницы, а ребрами — ссылки. Страницы могут быть важными и полезными, а могут быть результатом автоматической генерации, не нести вообще никакой смысловой нагрузки и ценности для большинства пользователей. Наша задача — посчитать некую авторитетность страницы, определить, какова вероятность того, что нам вообще будет интересно с ней иметь дело. На основе этого показателя мы сможем отбирать страницы для поисковой выдачи и ранжировать их.
Есть очень простой классический алгоритм PageRank, придуманный в компании Google. В качестве вдохновения был использован граф научных работ, т.к. в каждой научной работе есть ссылки на использованную литературу и смежные публикации. При этом, чем больше ссылаются на ту или иную работу, тем более авторитетной она считается в научном мире. Соответственно, модель устроена достаточно просто, это так называема модель случайного блуждателя. В ней есть веб-страницы с разной популярностью, между которыми есть связи в виде ссылок. Пользователь ходит по этим страницам и с некоторой вероятностью кликает на какую-нибудь исходящую ссылку. Допустим, что у нас таких пользователей много, стартуют они со случайной страницы. И нам нужно посчитать вероятность того, что пользователь окажется на некой странице. Считается все это следующим образом. Предположим, то у нас есть N страниц, в начальный момент пользователь с вероятностью 1/N попадает на случайную страницу. Вероятность того, что ему надоедает читать, мы принимаем за 15 процентов, соответственно, с 85-процентной вероятностью, пользователь продолжает серфинг и равновероятно переходит по случайной исходящей ссылке. В том случае, когда пользователю все надоедает, он заново начинает со случайной страницы. Функция на графе считается итеративно. На некоей итерации значение PR от некоторого узла на итерацию t. Мы берем этот PageRank и равномерно раздаем по исходящим ссылкам, на ссылке-ребре возникает значение, называемое дельтой PageRank — dPR. Утверждается, что если произвести достаточно много итераций, веса в узлах практически перестанут меняться.
Интересно, что на реальном веб-графе у такой простой модели обнаруживаются достаточно интересные свойства. Например, у страницы, на которую есть очень много ссылок, PR будет высоким, так как он складывается из дельт исходящих ссылок. И станица, на которую она ссылается, также будет достаточно высокий PR.
Эта модель может предсказывать посещаемость страниц, хотя у нее есть и проблемы, связанные с тем, что в те времена, когда она придумывалась, интернет был другим. Страниц было не так много, а все ссылки проставлялись вручную. Сейчас в базе Яндекса только по рунету около 20 миллиардов страниц, и полезных среди них не очень много. И главная проблема алгоритма в классическом виде заключается в том, что можно сделать спам-сайт, и генерировать на нем страницы, единственная цель которых — иметь ссылки на определенную страницу, которой нужно поднять PR. Кроме того, классический PR отдает предпочтение старым страницам.
Посмотрев лекцию до конца, вы узнаете, как бороться с проблемами классического PageRank, как измерять и улучшать качество поиска, что такое модели pfound и widepfound, а также, зачем в поиске нужно машинное обучение.
Однако прежде чем переходить к основной теме нашей лекции, стоит рассмотреть некоторые философские вопросы, связанные с моделированием.
Человек мыслит моделями, и с их помощью воспринимает и понимает окружающий мир. В качестве иллюстрации этой мысли приведем простую модель мира, в котором существуют только плохие и хорошие парни. Плохие всегда врут, а хорошие говорят правду. Если человек нам один раз соврал, то мы будем считать его плохим парнем, и доверять ему не будем. Но если этот плохой парень вдруг начнет говорить правду, у нас может возникнуть когнитивный диссонанс: несоответствие наблюдаемого, имеющейся у нас модели. Реагировать на это можно по-разному. Некоторые, например, могут отрицать увиденное, и оставаться в рамках своей модели. Однако такой подход очень далек от научного. Правильнее было бы отказаться от принятой модели, либо попытаться ее расширить.
Научный метод
Наиболее удачный подход к получению знаний заключается в следующем: у нас есть некоторый опыт (эмпирическое знание), на основе которого мы создаем некие теории и модели. Все гипотезы, которые мы можем придумать, изначально равноправны. Они могут объяснять имеющийся у нас опыт или его часть, а также предсказывать новый опыт. Модель не обязательно должна быть точной, она может быть и приблизительной, главное, чтобы она помогала нам что-либо понять, объяснить или предсказать. Вообще говорить о правильность или неправильности модели — не совсем верно, модель нужно воспринимать с точки зрения ее полезности. Например, после изобретения теории относительности стало ясно, что ньютоновская механика не совсем верна. Но при этом модель, которую она представляет, очень полезна, она помогает объяснять и предсказывать многие вещи.
Очень полезен для ученых принцип, известный как «бритва Оккама». Он подразумевает, что вводить в модель сущности без необходимости не нужно. Если можно составить более простую модель с той же полезностью, то пользоваться лучше ей.
Разработка поиска и анализ данных — тоже своего рода научная работа из области выявления высокоуровневых закономерностей. У нас есть огромные массивы данных, логи действий пользователей, на основе которых можно составлять модели, предсказывать действия, и, опираясь на это, делать хорошие сервисы. При этом пространства для моделирования тут гораздо больше, чем, например, в физике, где новые модели появляются крайне редко. В поиске новые модели можно придумывать хоть каждый день, и каждая из них будет в чем-то полезна.
PageRank
Для примера поговорим о модели PageRank, которая считается на графе веб-страниц и веб-ссылок. Интернет можно представить в виде графа, где вершинами будут страницы, а ребрами — ссылки. Страницы могут быть важными и полезными, а могут быть результатом автоматической генерации, не нести вообще никакой смысловой нагрузки и ценности для большинства пользователей. Наша задача — посчитать некую авторитетность страницы, определить, какова вероятность того, что нам вообще будет интересно с ней иметь дело. На основе этого показателя мы сможем отбирать страницы для поисковой выдачи и ранжировать их.
Есть очень простой классический алгоритм PageRank, придуманный в компании Google. В качестве вдохновения был использован граф научных работ, т.к. в каждой научной работе есть ссылки на использованную литературу и смежные публикации. При этом, чем больше ссылаются на ту или иную работу, тем более авторитетной она считается в научном мире. Соответственно, модель устроена достаточно просто, это так называема модель случайного блуждателя. В ней есть веб-страницы с разной популярностью, между которыми есть связи в виде ссылок. Пользователь ходит по этим страницам и с некоторой вероятностью кликает на какую-нибудь исходящую ссылку. Допустим, что у нас таких пользователей много, стартуют они со случайной страницы. И нам нужно посчитать вероятность того, что пользователь окажется на некой странице. Считается все это следующим образом. Предположим, то у нас есть N страниц, в начальный момент пользователь с вероятностью 1/N попадает на случайную страницу. Вероятность того, что ему надоедает читать, мы принимаем за 15 процентов, соответственно, с 85-процентной вероятностью, пользователь продолжает серфинг и равновероятно переходит по случайной исходящей ссылке. В том случае, когда пользователю все надоедает, он заново начинает со случайной страницы. Функция на графе считается итеративно. На некоей итерации значение PR от некоторого узла на итерацию t. Мы берем этот PageRank и равномерно раздаем по исходящим ссылкам, на ссылке-ребре возникает значение, называемое дельтой PageRank — dPR. Утверждается, что если произвести достаточно много итераций, веса в узлах практически перестанут меняться.
Интересно, что на реальном веб-графе у такой простой модели обнаруживаются достаточно интересные свойства. Например, у страницы, на которую есть очень много ссылок, PR будет высоким, так как он складывается из дельт исходящих ссылок. И станица, на которую она ссылается, также будет достаточно высокий PR.
Эта модель может предсказывать посещаемость страниц, хотя у нее есть и проблемы, связанные с тем, что в те времена, когда она придумывалась, интернет был другим. Страниц было не так много, а все ссылки проставлялись вручную. Сейчас в базе Яндекса только по рунету около 20 миллиардов страниц, и полезных среди них не очень много. И главная проблема алгоритма в классическом виде заключается в том, что можно сделать спам-сайт, и генерировать на нем страницы, единственная цель которых — иметь ссылки на определенную страницу, которой нужно поднять PR. Кроме того, классический PR отдает предпочтение старым страницам.
Посмотрев лекцию до конца, вы узнаете, как бороться с проблемами классического PageRank, как измерять и улучшать качество поиска, что такое модели pfound и widepfound, а также, зачем в поиске нужно машинное обучение.
