понедельник, января 07, 2008

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(n2), но это разработчиков как-то не особенно расстраивает.
Вот на этой картинке показано, как меняется порядок страниц в некой тестовой поисковой выдаче с течением времени, пока шло обучение нейронной сети.


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

В свои работы они также включают критику 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
Ссылочное ранжирование в Рунете
Глубокий веб

14 коммент.:

Fahrain комментирует...

Сдается мне, что эти товарищи сильно привирают, когда говорят что "это у нас просто PageRank плохо считается" :) По крайней мере я уже давно убедился что искать на сайте www.microsoft.com их собственным поисковиком - последнее дело. Запрос в гугле вида "что ищем" site:microsoft.com дает на порядки более релевантные результаты. Причем нужные ссылки - обычно первые три. Родной поисковик в половине случаев вообще выдает ничего полезного или же где-то на 5-10 странице.

P.S.: сейчас подумалось что MSN Search и встроенный поиск на сайте - разные вещи. Но это, имхо, маловероятно...

Лаврентий Палыч комментирует...

Интересно. Но вообще говоря система ранжирования и борьба со спамерами это конечно пересекающиеся задачи, но всё же не обязательно полностью пересекающиеся. Особенно учитывая наличие дорвейщиков - руками вычищать их труды это утопия. Я в своё время наткнулся на статьи на тему борьбы того же майкрософт с поисковым спамом: заметка майкрософт vs seo-спам.

P.S. Забавно что много упрёков в сторону Microsoft по поводу закрытости и т.п., однако на их открытые публикации частенько натыкаются в последнее время. :)

Алёна комментирует...

2Лаврентий Палыч:
Забавно что много упрёков в сторону Microsoft по поводу закрытости и т.п., однако на их открытые публикации частенько натыкаются в последнее время.

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

ALEX_KS комментирует...

Собственно говоря вы уже и сама пришли к решению что нужне интеллектуальные системы. Вы этом отношенни поступлю нехорошо и начну хвалить свой угол -- но ИМХО будущее в этом вопросе за смысловаым анализом текста и, соответственно, получением релевантности именно на уровне соответствия смысла запросу. В этом отношении еть серьезные подозрения что Гугл это уже использует, а вышеуказанные негры на плантациях популярных запросов занимаются не выборкой нормальных результатов поиска, а выборкой тех результатов поиска, на осонвие которых можно сторить базу знаний по предметной сфере запроса.

RunneR комментирует...

А вот мой опят говорит мне, что Live.com предоставляет более релевантные результаты.
А насчёт открытости гугла - это вообще смешно.

Vii комментирует...

Так уж совпало, что как раз с 7 января началось "альфа-тестирование" нового поисковика Wikia, от разработчиков wikipedia, одним из основных принципов которого и является т.н. "открытость и прозрачность" используемых алгоритмов. Вот здесь есть некое описание новинки.

Yuriy Volkov комментирует...

ну использовать искусственный интеллект для поиска сам бог велел. Однако этот ИИ еще сделать нужно. А они (насколько я разобрался из документа) еще и использовали метод градиентного спуска для обучения сети, который хоть и является "рабочей лошадкой" нейроинформатики, но никак нельзя назвать его самым эффективным.

Если использовать обученную сеть для аппроксимации функции ранжирования, то также нужно учитывать, что функция качества сети может иметь свои локальные минимумы, максимумы, площадки, т.е. не факт, что они получили наилучшие параметры настройки сети.

Лаврентий Палыч комментирует...

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

Ну если и подражают то переплюнули по детализации описания... Гугл обычно любит отговариваться общими фразами вроде такой: "да мы это учитываем, но в какой мере не можем сказать". Ну или сообщать подробности когда уже опытным путём их и так уже разгадали... Хотя возможно я просто редко натыкаюсь на их статьи...

Анонимный комментирует...

Что там Майкрософт переплюнул ?
Покажите мне, пожалуйста, аналог Google Tech Talks у Сайкрософта. Вот, к примеру, лекция майкрософтовцев в гугле: http://www.youtube.com/watch?v=WPhE5JCP2Ak
Есть что-либо подобное от Майкрософт ?

http://www.43n39e.ru/ - еще один поисковик с ранжированием при помощи нейронной сети.

Виталий Бондарь комментирует...

Спасибо за статью - интересно.

И вспомнились мне нейронные сети. Их много критикуют в последнее время, не оправдали они возложенных на них надежд.
Нейронные сети не опревдали надежд фантастов :) А ученые, которые занимаются ими вплотную, продолжают развивать тему. Сейчас уже даже очень сложно уследить за всеми новинками в этой области.

salnsg комментирует...

В основе нейтронных сетей лежит определенная математика, суть которой сводится ктому, что любую функцию можно интерполировать при помощи некоторой линейной комбинации других достаточно просто устроенных функций. Не хочется тут вдаваться в подробности, но хорошая или плохая математика (а здесь фундаментальные результаты восходят еще к Колмогорову, последнему великому математику) никак не связана (не коррелирует, как говорят статистики) с хорошими или плохими практическими применениями этих результатов. В применении к распознаванию образов это работает потому, что образы, в отличии от спамеров не эволюционирую так быстро и человек, например, в 30 и 35 лет выглядит примерно одинаково (при прочих равных условиях, конечно).
Спамер же сегодня пишет "честно", а завтра "4естно", а послезавтра "ч-е-с-т-н-о". Согласитесь, Вы прекрасно все поняли в этом примере, а вот как это объяснить машине, тем более обучить этому конкретную нейтронную сеть?!

dimbo комментирует...

Хм...
Все-таки, как мне кажется, должен существовать способ нахождения всех вариантов написания слова так, чтобы оно оставалось понятным человеку. Например, слово "ч-е-с-т-н-о" понятно, а слово "чжежсжтжнжо" - непонятно. В первом случае разделитель между буквами "-", а во втором - "ж". Это я к тому, что способов скрытия "спамерской сущности" текста много, но число этих способов не бесконечно и, следовательно, поддается машинному анализу.
Но создать универсальную программу, отсеивающую даже будущие уловки спамеров, скорее всего, невозможно. Это будет равносильно созданию программы, которая будет лучше пользователя знать, что же он хочет найти ;).

Виталий Бондарь комментирует...

Если бы не существовало способа узнавать образы, то и человек не смог бы их узнавать - это же очевидно :)
Ведь человек в крайней абстракции тоже является функтором (отображением одного пространства значений в другое).

В основе нейтронных сетей лежит определенная математика, суть которой сводится ктому, что любую функцию можно интерполировать при помощи некоторой линейной комбинации других достаточно просто устроенных функций.
О том, что линейная комбинация функций не может представить произвольную функцию строго математически доказали еще Минский и Пейпетр в 1969 (если не перепутал год). Только вот с тех пор было очень много новых наработок и очень много строго математических доказательств о возможности отображения произвольной функции тем или иным видом нейронных сетей.
Сейчас все не так просто как линейная комбинация функций :)

Колмогорову, последнему великому математику
Андрей Николаевич, конечно же, великий человек и сделал многое. Но, слово "последний" излишне :)

в 30 и 35 лет выглядит примерно одинаково (при прочих равных условиях, конечно)
Вы явно не представляете насколько технически отличается лицо одного и того же человека с разным настроением, даже в одном возрасте. И с этими задачами справляются вполне успешно, так что "честно" и "4естно" навряд ли проблема для разработчиков этой поисковой системы.

Didro комментирует...

Тут уже ALEX_KS говорил про смысловатый поиск :), вот пример от наших (Российских) разработчиков:

http://www.exactus.ru/