Ранжирование веб-страниц

Что такое PageRank

PageRank – это алгоритм, который был представлен Ларри Пейджем в 1999 году. На его основе в том же году был запущен поисковик под названием Google. В данный момент этот показатель используется крайне редко при ранжировании документов, хотя влияние связей между ссылками сохранилось и по сей день.

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

интеграционный способ

где PR(A) – PageRank страницы; Aи d является коэффициентом затухания. T – ссылающиеся страницы, С(T) – количество исходящих ссылок.

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

вычисление PageRank

Давайте разберемся, как можно повысить PageRank страницы:

  1. Добывать ссылки, которые имеют высокий PageRank и маленьким числом исходящих ссылок со страницы.

  2. Грамотно расставлять ссылки, исходящие со страницы.

  3. Построить внутреннею структуру навигации и связи между страницами, целью чего будет создание максимальной обратной связи.

Машинное обучение в алгоритмах ранжирования

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

машинное обучение

Давайте разделим применяемые факторы на три группы:

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

  2. Внешние факторы. Их получают при помощи анализа коллекции документов в виде графика.

  3. Поведенческие факторы. Они характеризуют поведение людей при просмотре результатов поиска и документа.

Теперь давай рассмотри еще одну классификацию, которая использует наличие или отсутствие зависимости фактора от самого запроса.

  1. Статические факторы. То есть те, которые полностью зависят конкретно от документа, а не от запроса.

  2. Факторы, напрямую зависящие только от самого запроса.

  3. Динамические факторы. Они зависят и от запроса и от документа непосредственно.

Для того чтобы сконструировать ранжирующую модель, программистам поисковых машин необходимо решить несколько задач. К ним относится тестирование, построение обучающей выборки, какая-либо корректировка модели и т.д. Модель, которая будет выбрана должна быть устойчивой к переобучению, главной проблемой которого является обнаружение обучающей выборки случайных зависимостей, отсутствующих в генеральной совокупности. Также система может проводить определение ложных факторов, которые якобы свидетельствуют о релевантности.

Модели ранжирования, которые построены методом машинного обучения, в наше время применяются большинством современных поисковиков. В 2013 году Mail.ru запустил собственный поиск, использующий подобные технологии. Компания Google к машинному обучению имеет иное отношение и не доверяет поисковой системе самостоятельно проводить ранжирование. Основной мотивацией этого является то, что одели, созданные автоматическим путем, могут иметь не предсказуемое поведение на новых классах запросов в сравнении с разработанными специалистами.

Что представляет собой алгоритм ранжирования Яндекс

Яндекс использует модель поиска, которая основывается в первую очередь на обучении деревьев принятия решение. Ее принято называть «Matrixnet». Со слов ее создателей, данная модель является довольно устойчивой к переобучению и может проводить эффективный подбор значений для ранжирования. Зависит это от запроса и документов.

алгоритм ранжирования Яндекс

Для построения функции ранжирования поисковиком Яндекс учитывается более 400 факторов. Конечно же, не все они применяются в процессе ранжирования такой пары как «запрос-документ» Обучающей выборкой рассматривается довольно большое количество пар «запрос-документ», с которым происходит сопоставление оценки релевантности, предложенная асессорами. Оценка каждого документа производится качественным образом и принимает такие значения как «нерелевантный», «витальный» и другие.

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

оптимизированная задача

где fr – это функция релевантности, F – класс доступных функций, L – мера расстояния, rel – оценка релевантности, n – число элементов присутствующих в задачнике.

Функцию fr можно найти:

функция fr

Функция fr(q,d) выстраивается итерационно и на каждой новой итерации прибавляется новое слагаемое. Также на каждой итерации выполняется алгоритм необходимый для нахождения коэффициента а и функции h(q,d), который состоит всего из трех шагов. Давайте их рассмотрим:

  1. Происходит аппроксимация градиента функции релевантности. Вектор градиента вычеслется следующим образом:

    аппроксимация градиента

  2. Подбор функции h(q,d) как функционального приближения градиента функциональное приближение градиента при решении задачи оптимизации:

    решение задач оптимизации

  3. Подбор параметра а. Для этого необходимо решить однопараметрическую оптимизационную задачу:

    однопараметрическая оптимизационная задача

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