Что такое PageRank
PageRank – это алгоритм, который был представлен Ларри Пейджем в 1999 году. На его основе в том же году был запущен поисковик под названием Google. В данный момент этот показатель используется крайне редко при ранжировании документов, хотя влияние связей между ссылками сохранилось и по сей день.
PageRank имеет вид числовой характеристики страницы. Ее расчет можно произвести интеграционным способом воспользовавшись следующей формулой:
где PR(A) – PageRank страницы; Aи d является коэффициентом затухания. T – ссылающиеся страницы, С(T) – количество исходящих ссылок.
Далее давайте рассмотрим рисунок, на котором изображен пример того, как проводится вычисление PageRank для четырех страниц. На этом примере отлично видна связь между страницами А и С.
Давайте разберемся, как можно повысить PageRank страницы:
-
Добывать ссылки, которые имеют высокий PageRank и маленьким числом исходящих ссылок со страницы.
-
Грамотно расставлять ссылки, исходящие со страницы.
-
Построить внутреннею структуру навигации и связи между страницами, целью чего будет создание максимальной обратной связи.
Машинное обучение в алгоритмах ранжирования
Из-за роста Интернета поисковые системы сталкиваются все с большими сложностями ранжирования документов. Применяемые ими алгоритмы становятся мало эффективными, потому как признак релевантности, который является главной их основой, с легкостью могут быть накручены веб-мастерами. Благодаря разнообразности документов и запросов и разных документов необходимо использовать самые разные наборы признаков. Анализируя большое количество документов и запросов, которые применяют как обучающую выборку, естественным шагом для разработчиков поисковиков стало применение машинного обучения. Оно в свою очередь позволяет проводить автоматический подбор ранжирующих моделей. Главной целью таких моделей является приближение и обобщение способов ранжирования в обучающей выборке на какие-либо новые данные, имеющие достаточную точность в конкретной метрике.
Давайте разделим применяемые факторы на три группы:
-
Внутренние факторы, которые определяются для каждого отдельного документа коллекции локальным образом. Таковыми являются количество или размер изображений.
-
Внешние факторы. Их получают при помощи анализа коллекции документов в виде графика.
-
Поведенческие факторы. Они характеризуют поведение людей при просмотре результатов поиска и документа.
Теперь давай рассмотри еще одну классификацию, которая использует наличие или отсутствие зависимости фактора от самого запроса.
-
Статические факторы. То есть те, которые полностью зависят конкретно от документа, а не от запроса.
-
Факторы, напрямую зависящие только от самого запроса.
-
Динамические факторы. Они зависят и от запроса и от документа непосредственно.
Для того чтобы сконструировать ранжирующую модель, программистам поисковых машин необходимо решить несколько задач. К ним относится тестирование, построение обучающей выборки, какая-либо корректировка модели и т.д. Модель, которая будет выбрана должна быть устойчивой к переобучению, главной проблемой которого является обнаружение обучающей выборки случайных зависимостей, отсутствующих в генеральной совокупности. Также система может проводить определение ложных факторов, которые якобы свидетельствуют о релевантности.
Модели ранжирования, которые построены методом машинного обучения, в наше время применяются большинством современных поисковиков. В 2013 году Mail.ru запустил собственный поиск, использующий подобные технологии. Компания Google к машинному обучению имеет иное отношение и не доверяет поисковой системе самостоятельно проводить ранжирование. Основной мотивацией этого является то, что одели, созданные автоматическим путем, могут иметь не предсказуемое поведение на новых классах запросов в сравнении с разработанными специалистами.
Что представляет собой алгоритм ранжирования Яндекс
Яндекс использует модель поиска, которая основывается в первую очередь на обучении деревьев принятия решение. Ее принято называть «Matrixnet». Со слов ее создателей, данная модель является довольно устойчивой к переобучению и может проводить эффективный подбор значений для ранжирования. Зависит это от запроса и документов.
Для построения функции ранжирования поисковиком Яндекс учитывается более 400 факторов. Конечно же, не все они применяются в процессе ранжирования такой пары как «запрос-документ» Обучающей выборкой рассматривается довольно большое количество пар «запрос-документ», с которым происходит сопоставление оценки релевантности, предложенная асессорами. Оценка каждого документа производится качественным образом и принимает такие значения как «нерелевантный», «витальный» и другие.
Для того чтобы построить регрессию функции релевантности, которую задают при помощи обучающей выборки, применяется древо решений. Оптимизационная задача имеет следующий вид
где fr – это функция релевантности, F – класс доступных функций, L – мера расстояния, rel – оценка релевантности, n – число элементов присутствующих в задачнике.
Функцию fr можно найти:
Функция fr(q,d) выстраивается итерационно и на каждой новой итерации прибавляется новое слагаемое. Также на каждой итерации выполняется алгоритм необходимый для нахождения коэффициента а и функции h(q,d), который состоит всего из трех шагов. Давайте их рассмотрим:
-
Происходит аппроксимация градиента функции релевантности. Вектор градиента вычеслется следующим образом:
-
Подбор функции h(q,d) как функционального приближения градиента при решении задачи оптимизации:
-
Подбор параметра а. Для этого необходимо решить однопараметрическую оптимизационную задачу:
В конечном результате алгоритм Matrixnet выстраивает функцию релевантности, благодаря значением которой происходит ранжирование результатов поиска поисковой машиной. Главной задачей данного алгоритма является использование кусочно-постоянных функций, что позволяет факторам в некоторых случаях сильно изменять значение функции релевантности.