MSN Search

Когда говорят о поисковых машинах и ранжировании сайтов всегда вспоминают гугловский PageRank как единственно правильный способ ранжирования. Но, как известно, что один человек придумал, другой завсегда поломать сможет. Линкопомойки и другие сомнительные изобретения человечества очень портят жизнь поисковым машинам, использующим PageRank в качестве базового алгоритма. Бороться с подобным поисковым спамом сложно. Спамеры изобретательны. По слухам, весьма высокая релевантность Гугловского поисковика объясняется тем, что там работает куча народу, которая вручную проверяет популярные запросы и вытирает определенные сайты из поисковой выдачи. Вот такие вот высокие технологии.
На самом деле это все уже проходили. Я помню еще лохматые времена, когда никакого PageRank'а не было. Поисковая выдача строилась исключительно по содержимому документа. Тогда поисковый спам был другой. Больше пытались играть с содержимым страничек. Нужные ключевые слова подпихивали в meta и писали белым по белому.
Я тут на досуге поразмыслила, а какой технологией можно PageRank заменить, кто будет следующим? Когда спамерские технологии разовьются до того момента, что PageRank потеряет смысл в принципе. Я, правда, не специалист в области поиска, ну и ладно.
Человек ведь может отличить спамерский сайт от хорошего правильного релевантного сайта, который он искал. Не все, правда, могут.
И вспомнились мне нейронные сети. Их много критикуют в последнее время, не оправдали они возложенных на них надежд. Правда, вот, в распознавании образов они очень хорошо себя ведут. Я знаю, я видела :-).
Итак, поиск на основе нейронных сетей. Ищем гуглом и находим... Что в MSN Search эта технология применяется уже довольно давно. Первые публикации, которые я нашла по этому поводу, относятся к 2005 году, есть публикации 2006 года.
Так что для тех, кто, как и я, все это время пребывал в танке, небольшой рассказ о том, что собственно делают (или делали?) в MSN Search.
Вся нижеследующая информация взята из двух статей: Beyond PageRank: Machine Learning for Static Ranking и FRank: A Ranking Method with Fidelity Loss.

В MSN Search используют fRank - нейронную сеть, основанную на их алгоритме RankNet. Эта нейронная сеть расставляет сайты в правильном порядке. Сами сайты находятся с помощью других алгоритмов, того же PageRank'а, например. Сеть учат понимать, что одна страница лучше другой, а не пробегают каждую страницу и проставляют ей рейтинг. Видно, что количество операций повышается с O(n) до O(n²), но это разработчиков как-то не особенно расстраивает.
Вот на этой картинке показано, как меняется порядок страниц в некой тестовой поисковой выдаче с течением времени, пока шло обучение нейронной сети.


Тут не очень очевидная картинка. Зеленый сайт самый релевантный, за ним должен идти желтый, а потом уже красные.

В свои работы они также включают критику PageRank. Слегка перегибают они палку с этой критикой. Видно, что они PageRank сильно не любят. Тем не менее, их аргументация заслуживает внимания.

PageRank стал популярен благодаря мощной рекламе Гугла. Ну, во-первых, никто не мешал им свои технологии рекламировать. А во-вторых - хороший алгоритм PageRank. Интересный, нестандартный на тот момент подход к решению проблемы.

При проставлении ссылок, повышается релевантность сайтов, интересных авторам, а не читателям. Вот это важный момент, о котором я никогда раньше не задумывалась. Авторы сайтов и читатели - это разные категории, их интересы не всегда совпадают. PageRank доверяет авторам выбирать за всех.

Один из недостатков PageRank'а, так называемый topic drift. Этому алгоритму важно только количество ссылок, содержимое сайтов неважно.

PageRank усиливает и без того популярные страницы. Чем выше ранг, тем проще страницу найти. Чем проще найти, тем чаще ссылаются. Чем чаще ссылаются, тем выше PageRank.

По ходу своей работы они активно сравнивают свой результат с PageRank'ом. Но, внимание, с каким PageRank'ом? Со своей собственной реализацией. Сами они говорят, что реализация у них отличная и хуже себя показывает исключительно по причине алгоритма. Кто их знает, может оно так и есть.

Ссылки по теме:
Learning to Rank using Gradient Descent, .pdf описание RankNet, присутствует некоторое количество математики.
Beyond PageRank, RankNet, and fRank
Web spam and TrustRank
Ссылочное ранжирование в Рунете
Глубокий веб