Обучение ранжированию I. Попарный подход. Часть 3: Экспериментальная оценка RankBoost

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

Мета-поиск

Сначала мы представим эксперименты по обучению для объединения результатов нескольких систем информационного поиска. Эта задача проявляет много аспектов, которые требуют общего подхода. Например, подходы, сочетающие подобные оценки не применимы, так как схожие значения поисковых систем часто имеют различную семантику или недоступны.

Описание задачи и набора данных

Задавая отображение задачи ранжирования в нашей структуре, мы можем сразу же применить RankBoost. Отметим, что функция обратной связи для этой задачи является суммой двусторонней обратной связи. При этом отображении, каждый слабый рейтинг определяется шаблоном поиска i (что соответствует признаку ранжирования fi) и пороговой величиной θ. Задавая базовый запрос q и URL-адрес u, этот слабый рейтинг принимает значения 1 или 0, если u ранжировано выше или ниже порога θ в списке URL-адресов, возвращаемых расширенным запросом, связанным с шаблоном поиска i, что применяется для базового запроса q. Принято, что окончательный рейтинг Н является взвешенной суммой слабых рейтингов. Для оценки, мы разделили данные на учебные и тестовые наборы, используя кросс-проверку, состоящую из четырех частей. Мы разделили данные на четыре группы, каждая из них содержала 75% базовых запросов для обучения и 25% для тестирования. Конечно, алгоритмы обучения не имели доступ к тестовым данным во время испытания.

Экспериментальные параметры и оценка

Поскольку все шаблоны поиска имели доступ к схожему набору документов то, если URL не был среди ТОП-30 документов согласно шаблону, мы расценивали это как то, что рейтинг URL ниже рейтингов всех возвращенных документов. Таким образом, мы установили параметр qdef, значение по умолчанию для слабых рейтингов, равный 0. Наша реализация RankBoost использовала определение рейтинга потери:

формула

Если полученный рейтинг был отранжирован как равный паре экземпляров (x0,x1) так, что обратная связь была упорядочена неодинаково то, мы присваивали рейтингу погрешность 1/2 вместо 1. Это представляет то, что если бы мы использовали ранжирование, чтобы создать упорядоченный список документов, разрывая связи случайно, то его ожидаемая погрешность на (x0,x1) равнялась бы 1/2, так как вероятность того, что x0, ранжирован выше x1, равна вероятности того, что x1 ранжирован выше х0. Модифицированное определение представлено следующим образом:

формула

Параметры RankBoost. Так как WeakLearn выводит двоичные слабые рейтинги, мы можем установить параметр α с использованием либо второго, либо третьего методов, представленных ранее. Второй метод устанавливает α, как минимум Z, а третий метод — приблизительно минимуму Z. Третий способ может быть более легко реализован и работает быстрее. Мы реализовали оба метода и назвали их WeakLearn.2 и WeakLearn.3, чтобы определить, было необходимое дополнительное время для второго метода (почти в десять раз больше, чем в третьем способе на наборе данных ML) оправдано уменьшением частоты тестовых погрешностей. Мы также реализовали слабых учащихся, которые ограничивали их рейтинги, чтобы иметь положительные кумулятивные веса с тем, чтобы проверить были ли такие рейтинги полезными для снижения тестовой погрешности. Мы назвали их WeakLearn.2.cum и WeakLearn.3.cum. Для измерения точности слабого ученика на данном наборе данных, после каждого цикла усиления были заданы обучающие и тестовые погрешности созданного до тех пор комбинированного рейтинга. Мы прогнали каждого слабого учащегося за 1000 циклов усиления на каждой из четырех частей данных и получили усредненные результаты. Рисунок 9 показывает графики обучающей (слева) и тестовой погрешностей (справа) для первых 200 циклов усиления на наборе данных ML. (Наклоны кривых не изменились в течение оставшихся 800 циклов). Графики для набора данных UNIV были похожи.

Производительность слабых обучающихся WeakLearn

Рисунок 9. Производительность 4-х слабых обучающихся WeakLearn. {2,3,2.cum,3.cum} на наборе данных ML. Слева: обучающая погрешность / Справа: тестовая погрешность.

WeakLearn.2 достиг низкой обучающей погрешности, далее следовали WeakLearn.3, и, наконец, WeakLearn.2.cum и WeakLearn.3.cum, производительность которых была почти идентична. Тем не менее, WeakLearn.2.cum и WeakLearn.3.cum выдали минимальную тестовую погрешность (опять же ведя себя почти одинаково) и сопротивлялись переобучению, в отличие от своих прототипов. Итак, мы видим, что ограничение слабых рейтингов дает положительные кумулятивные веса и затрудняет процесс обучения, но улучшает процесс проверки. Кроме того, когда мы подвергаем рейтинг этому ограничению, мы не видим никакой разницы между вторым и третьим методами выбора α. Таким образом, в наших экспериментах мы использовали WeakLearn.3.cum, третий способ выбора значения α, что допускает только положительные кумулятивные веса ранжирования.

Оценка. Мы сначала запустили RankBoost на каждой части данных и создали график средней погрешности обучения для того чтобы определить большое количество циклов усиления. Для набора данных ML, ошибка обучения после 50 циклов усиления не уменьшилась значительно (см. рисунок 9, слева), поэтому мы использовали окончательный рейтинг, построенный после 50 циклов. Для набора данных UNIV, ошибка обучения после 40 циклов усиления не уменьшилась значительно (график отсутствует), поэтому мы использовали окончательный рейтинг, построенный за 40 циклов. Чтобы оценить работу отдельных шаблонов поиска по сравнению с результатом комбинированного рейтинга по RankBoost, мы измерили количество запросов, для которых правильный документ был среди топ- k отранжированных документов, k = 1, 2, 5, 10, 20, 30. Затем мы сравнили работу комбинированного рейтинга для лучших шаблонов поиска каждого значения k. Результаты для доменов ML и UNIV приведены в Таблице 2. Все столбцы, кроме последнего, приводят количество базовых запросов, у которых истинная домашняя страница получила ранг больший или равный k. Цифры, выделенные жирным шрифтом, указывают на максимальное значение всех шаблонов поиска для тестовых данных. Обратите внимание, что самый лучший шаблон поиска определяется относительно того, как он работает с тестовыми данными, в то время как RankBoost имеет доступ только к обучающим данным.

ML ТОП 1 ТОП 2 ТОП 5 ТОП 10 ТОП 20 ТОП 30 Средний ранг
RankBoost 102 144 173 184 194 202 4.38
Лучший (ТОП 1) 117 137 154 167 177 181 6.80
Лучший (ТОП 10) 112 147 172 179 185 187 5.33
Лучший (ТОП 30) 95 129 159 178 187 191 5.68
UNIV  
RankBoost 95 141 197 215 247 263 7.74
Лучший единственный запрос 112 144 198 221 238 247 8.17

Таблица 2. Сравнение комбинированного рейтинга и индивидуальных шаблонов поиска (search template)

Для набора данных ML, объединенный рейтинг приближается к результатам лучшего эксперта на каждом значении k, что особенно интересно, так как ни один шаблон не был лучшим для всех значений k. Для набора данных UNIV, единственный шаблон был лучшим для всех значений k, а комбинированный рейтинг дал результаты почти так же хорошо, как и лучший шаблон для k = 1, 2, …, 10, а затем превзошел лучший шаблон для k = 20, 30. Конечно же, найдя единственный наилучший шаблон, нет необходимости использовать RankBoost. Мы также вычислили (приблизительно) средний ранг, т. е. ранг корректно определенной домашней страницы URL, усредненный по всем базовым запросам в тестовом наборе. Для этого расчета, мы рассматривали каждый шаблон поиска как ранг от 1 до 30, присвоенный к возвращенным URL. Рейтинг 1 означал наилучшее значение. Поскольку правильный URL иногда не был отранжирован по шаблону поиска, мы искусственно присваивали рейтинг 31 для каждого неотранжированного документа. Для каждого базового запроса, RankBoost ранжировал каждый URL, возвращенный каждым шаблоном поиска. Таким образом, если общее количество URL-адресов было больше, чем 30, то RankBoost присваивал некоторым экземплярам рейтинг больше, чем 30. Чтобы избежать несправедливого сравнения с шаблонами поиска, мы ограничили максимальное значение рейтинга RankBoost до 31. В последнем столбце Таблицы 2 приведен средний рейтинг.

Рекомендации фильма

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

Описание задачи и набор данных

Для этих экспериментов мы использовали общедоступные данные, представленные Digital Equipment Corporation, которая тестировала свое приложение рекомендаций EachMovie в течение восемнадцати месяцев с марта 1996 г. по сентябрь 1997 года и собрала данные о пользовательских предпочтениях. Зрители фильмов смогли присвоить рейтинг фильму из значений R = {0.0,0.2,0.4,0.6,0.8,1.0}, где значение 1,0 являлось лучшим. Мы использовали данные 61 625 зрителей, вводя в общей сложности 2 811 983 числовых рейтингов для 1 628 различных фильмов (фильмов и видео). Большинство отображений этой задачи в нашем фреймворке мы описали ранее. Для наших экспериментов мы выбрали подмножество зрителей С в качестве признака ранжирования: каждый зритель в C определял упорядочение множества фильмов, которые он или она просмотрели. Функция обратной связи Φ была определена, как описано ранее, используя рейтинги фильмов одного целевого пользователя. Мы использовали половину просмотренных фильмов целевого пользователя для функции обратной связи для обучения и другую половину просмотренных фильмов для тестирования, как описано ниже. Далее мы усреднили все результаты по нескольким прогонам со многими различными целевыми пользователями.

Экспериментальные параметры

Мы предположили в задаче мета-поиска, что все поисковые системы имеют доступ ко всем документам и, следовательно, отсутствие документа в списке поисковой системы указывало бы на его низкое предпочтение. Такое предположение отсутствовало в задаче по выбору фильма, так как не ясно, какое предпочтение будет у зрителя, относительно не просмотренного фильма. Таким образом, мы не устанавливали параметр qdef, что позволило слабому ученику выбрать его адаптивно. Как и в задаче мета-поиска мы использовали модифицированное определение рейтинга потерь, заданного в уравнении (50). Мы также использовали WeakLearn.3.cum, потому что предварительные эксперименты показали, что этот слабый ученик достиг более низкой частоты ошибок тестирования, чем WeakLearn.3, а также сопротивлялся переобучению. В этих экспериментах, мы установили количество циклов T как 40+N/10, где N являлся количеством признаков. Этот выбор основан на работе с задерживаемыми данными, которые не использовались ни в одном из наших экспериментах.

Алгоритмы для сравнения

Мы сравнили работу RankBoost на этом наборе данных с тремя другими алгоритмами: алгоритмом регрессии, алгоритмом ближайших соседей и алгоритмом сопоставления, называемым вектором сходства.

Алгоритм регрессии. Мы использовали алгоритм регрессии, похожий на тот, что использовали Hill и соавт. (1995) . Алгоритм использует предположение о том, что рейтинги фильмов, присвоенные целевым пользователем Алисой, могут быть описаны в виде линейной комбинации рейтингов, присвоенных этим фильмам другими зрителями. Формально пусть a будет вектором-строкой, компоненты которого являются значениями, которые Алиса присвоила фильмам (исключая неоцененные фильмы). Пусть С будет матрицей, что содержит в себе значения других пользователей для подмножества фильмов, отранжированного Алисой. Так как некоторые из зрителей не оценили фильмы, которые были оценены Алисой, мы должны выбрать рейтинг по умолчанию для этих фильмов. Для каждого зрителя, представленного в строке C, установим значение для неоценённых фильмов как среднее значение, присвоенное зрителями для всех фильмов. Далее воспользуемся линейной регрессией, чтобы найти вектор минимальной длины w, который минимизирует ||wC − a||. Это можно сделать с помощью стандартных численных методов (мы использовали пакет, доступный в Matlab). Задавая значение w, мы можем предсказать рейтинги, присвоенные Алисой всем фильмам.

Алгоритм ближайших соседей. Учитывая целевого пользователя Алису с определенными предпочтениями в фильмах, алгоритм ближайших соседей (БС) находит зрителя Бориса, предпочтения которого наиболее близки к Алисиным, и затем использует его предпочтения, чтобы сделать рекомендации для Алисы. Более конкретно, мы находим признак ранжирования fi (соответствующий одному из других зрителей фильма), который задает упорядочение наиболее близкое целевому пользователю, закодированное с помощью функции обратной связи Φ. В качестве степени сходства мы используем потери ранжирования для fi по отношению к тому же начальному распределению D, которое было построено по RankBoost. Таким образом, в некотором смысле, БС можно рассматривать как единый слабый рейтинг, полученный после одного цикла RankBoost (хотя никакой порог для fi не представлен). Как и в случае с алгоритмом регрессии, проблемой БС является то, что «сосед» не может оценить все фильмы, оцененные целевым пользователем. Чтобы исправить это, мы изменили алгоритм. Мы привязывались к каждому признаку, если значение по умолчанию qdef∈ R, fi которого присваивались неоцененным фильмам. При поиске лучших признаков, БС выбирает qdef путем расчета и минимизации потери ранжирования (на обучающей выборке) для каждого возможного значения qdef. Если бывает так, что этот зритель оценивает все (в процессе обучения) фильмы, просмотренные целевым пользователем, то БС устанавливает qdef как среднее значение по всем фильмам, которые он оценил (в том числе те, что не были оценены целевым пользователем).

Вектор сходства (ВС). Этот алгоритм был предложен Breese, Heckerman и Kadie (1998) и базируется на понятии сходства между векторами, которое обычно используется в информационном поиске. В области информационного поиска, сходство между двумя документами часто измеряется путем обработки каждого документа в качестве вектора частоты встречаемости термина. Сходство между двумя документами определяется как нормированное скалярное произведение, образованное двумя векторами частоты, представляющими различные документы (Salton и McGill, 1983). Breese, Heckerman и Kadie приняли эту формальную систему для задачи совместной фильтрации, рассмотрев рейтинги каждого зрителя в качестве разреженного вектора вещественных чисел. Согласно их определению, пользователи берут на себя роль документов, фильмы берут на себя роль терминов, появляющихся в документах, а рейтинги зрителей берут на себя роль частоты встречаемости термина. Пусть Ci обозначает рейтинги i-того зрителя. Тогда корреляция между j-м зрителем и i-м зрителем:

формула

где скалярное произведение и нормы рассчитаны по подмножеству фильмов, оцененных каждым зрителем. Чтобы приспособить различные шкалы, Breese, Heckerman и Kadie также вычислили для каждого зрителя i его среднее значение, которое обозначается как Ci. Чтобы спрогнозировать рейтинг нового зрителя, индексированного k, мы сначала вычисляем коэффициенты подобия wk,i с каждым предыдущим зрителем i, а затем присваиваем вещественное значение C^k,j для каждого фильма j следующим образом,

формула

где α является нормирующим коэффициентом, который гарантирует, что ∑i|wk,i|=1. ВС и другой алгоритм на основе корреляции показали наилучшие результаты в экспериментах, проведенных Breese, Heckerman и Kadie (1998) с набором данных EachMovie. Кроме того, в этих экспериментах ВС превзошел четыре других алгоритма, когда количество оцененных фильмов была небольшой (менее 5).

Критерии производительности

Для того чтобы оценить и сравнить качество работы, мы использовали четыре меры погрешности: несогласованность, прогнозируемый топовый рейтинг (predicted-rank-of-top), охват и среднюю точность (average precision). Несогласованность сравнивает прогнозируемое упорядочение с правильным, в то время как остальные три меры касаются лишь прогнозируемого рейтинга тех экземпляров, которые должны были получить наивысший рейтинг. Мы предполагаем, что каждый из алгоритмов, описанный в предыдущем разделе порождает действительную функцию H, которая упорядочивает фильмы в обычном порядке: x1 имеет более высокий рейтинг, чем x0, если H(x1) > H(x0). Правильный порядок тестируемых фильмов (С) также представлен в виде действительной функции. Для каждого из следующих мер, мы сначала приведем определение, когда H является общим порядком, то есть она присваивает уникальное значение каждому фильму. Если H является частичным порядком, как это имеет место для некоторых алгоритмов, то мы предполагаем, что зависимости становятся случайными, когда создается список фильмов, упорядоченный по Н. В этой ситуации мы вычисляем математическое ожидание меры ошибки по случайным вариантам нарушенных зависимостей.

Несогласованность. Несогласованность является долей различных пар фильмов (в тестовом наборе), порядок которых нарушен H в отношении c. Если N является числом различных пар фильмов, упорядоченных с, то несогласованностью d является:

формула

Это равносильно потери ранжирования H (уравнение (30)) где c используется для построения функции обратной связи. Если H является частичным порядком, то ее ожидаемая несогласованность относительно с равняется:

формула

что эквивалентно уравнению (50), где с используется для построения функцию обратной связи. Эта мера расхождения пропорциональна другой мере двух линейных порядков (коэффициенту корреляции Пирсона r), которая была определена Shardanand и Maes для наилучшего результата в их совместных экспериментах фильтрации (Shardanand и Maes, 1995).

Меры точности / полноты. Несогласованность является одним из способов сравнения двух упорядочений, и это та функция, которую алгоритмы RankBoost и БС пытаются свести к минимуму. Мы должны рассмотреть оценку рейтингов этих алгоритмов с помощью других мер по ряду причин. Одна из причин заключается в проверке того, приводит ли минимизация потери ранжирования согласно RankBoost к высококачественному упорядочению по отношению к другим мерам. Это можно оценить также, глядя на сравнительное качество работы другой меры RankBoost и алгоритма регрессии, так как последний не минимизирует разногласия непосредственно. Еще одна причина обусловлена применением: люди, ищущие рекомендации относительно фильмов, вероятно, будут больше заинтересованы в более высоких рейтингах. То есть, они хотят знать, какие фильмы стоит посмотреть, а на какие не стоят тратить свое время. По этим причинам мы рассмотрели три другие меры погрешностей, которые представляют задачу по рекомендации фильмов как ту, что имеет двудольную обратную связь. В соответствии с этими мерами, цель задачи по выбору фильма состоит в том, чтобы найти фильмы, которые понравятся Алисе. Таким образом, любой набор фильмов, которые она видела, разбивается на две части: фильмы, которым она присвоила наивысший рейтинг, и фильмы, которым она присвоила наименьший рейтинг. Это пример задачи по ранжированию в области информационного поиска, где только те фильмы, которым Алиса присвоила высокие рейтинги, считаются актуальными. Как уже говорилось, наша цель состоит не в классификации, а в ранжировании. Мы считаем, что фильмы, которым Алиса присвоила высокий рейтинг, являются хорошими. Мы основываем наши меры погрешностей на метриках точности, используемых для выполнения данной задачи. Точность k-го хорошего фильма в отранжированном списке определяется как k, разделенное на число фильмов в списке вплоть до этого фильма. Например, если все хорошие фильмы появляются один за другим в верхней части списка, то точность каждого хорошего фильма равняется 1. Более формально, определяем рейтинг (m), рейтинг фильма m в списке, упорядоченном по H, как положение m в списке, например, первый = 1, второй = 2 и т.д. Предположим, что существует K хороших фильмов (согласно Алисе), и обозначим их последовательность в списке H как {tk}Kk=1. Другими словами, H(t1) ≥ … ≥ H(tK). Тогда точность первого хорошего фильма равняется 1/rank(t1), и, в более общем смысле, точность k-го хорошего фильма равняется k/rank(tk). Опять же, если все K хороших фильма появляются один за другим в верхней части списка H, что означает rank(tk) = k для каждого k, то точность каждого хорошего фильма равняется 1.

Средняя точность (СТ). Средняя точность широко используется в сообществах, занимающихся информационным поиском, и она показывает, насколько высоко Н упорядочивает хорошие фильмы в своем списке. Она определяется как:

формула

Если H является частичным порядком, то tk является случайной величиной, и, следовательно, таким же является rank(tk), и мы рассчитываем ожидаемую среднюю точность. Пусть N будет общим количеством фильмов, упорядоченных по H. Тогда,

формула

Формула для Pr[rank(tk) = i] представляет собой отношение с биномиальными коэффициентами в числителе и знаменателе. Пусть М будет множеством всех фильмов. Пусть R является числом фильмов, которые, появляются перед tk в списке H,

формула

Пусть r будет количеством хороших фильмов, которые появляются перед tk

формула

Пусть Q будет количеством фильмов, связанных с tk,

формула

Пусть q будет количеством хороших фильмов, связанных с tk,

формула

Тогда,

формула

Докажем это следующим образом. Пусть j = k − r. Затем, когда tk размещен на позиции i, tk является j-ым хорошим фильмом, что появляется в списке Q связанных фильмов. Определим случайную величину Yj как ранг tk в списке связанных фильмов. Например, если tk является вторым фильмом в списке, то Yj = 2. Тогда

формула

где l = i − R. Так что теперь нам нужно вычислить вероятность того, что, в группе одинаково оцененных фильмов, j-ый хороший фильм появляется в позиции l. Этот процесс можно смоделировать как выборку без возвращения Q раз из урны с Q шарами, q зелеными и Q − q красными. (Шары одного цвета неразличимы.) Событие Yj = l означает, что j-ый зеленый шар был использован из l-ого изображения. Глядя на всю последовательность изображений, это означает, что j − 1 зеленые шары столкнулись с изображениями 1,…,l − 1, j-ый зеленый шар был использован из l изображения, а q − j зеленые шары столкнулись с изображениями l + 1,…,Q. Существует (l-1 / j-1) способов, чтобы ранжировать все изображения первых j-1 зеленых шаров, и (Q-l / q-j) способов, чтобы упорядочить изображения остальных q-j зеленых шаров. Общее количество всех возможных последовательностей изображений равняется (Q / q). Таким образом

формула

Подставляя l = i − R из (52) в это уравнение, получаем (51) — желаемый результат.

Прогнозируемый топовый рейтинг (ПТР). ПТР является точностью первого хорошего фильма в списке H и показывает, насколько высоко Н ранжирует один хороший фильм в своем списке. Он равняется

формула

Если H является частичным порядком, ожидается, что прогнозируемый топовый рейтинг равняется

формула

Охват. Охват является точностью последнего хорошего фильма в списке H (также известной как точность при полноте 1), и он показывает, насколько хорошо Н ранжирует самый плохой фильм. Формально, это можно записать:

формула

Если H является частичным порядком, ожидается, что охват равняется

формула

Экспериментальные результаты

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

Сначала мы экспериментировали с рядом признаков, используемых для ранжирования. Мы выбрали два непересекающихся случайных множества T и T’ по 2000 зрителей в каждом. Подмножества зрителей в T были использованы в качестве наборов характеристик, и каждый из пользователей в T’ был использован в качестве обратной связи. В частности, мы разделили T на шесть подмножеств T1, T2,…,T6 соответствующих размеров 100, 200, 500, 750, 1000, 2000, так что T1 ⊂ T2 ⊂ … ⊂ T6. Каждый Tj служил набором характеристик для обучения на половине фильмов целевого пользователя и тестирования на другой половине для каждого пользователя в T’. Для каждого алгоритма, мы рассчитали четыре меры, описанные выше, усредненные по 2000 целевым пользователям. Мы прогнали алгоритмы по пяти непересекающимся случайным разбиениям этих данных во множествах характеристик и обратной связи, затем усреднили результаты, которые показаны на рисунке 10. Метод RankBoost превзошел алгоритмы регрессии и БС по всем четырем показателям производительности. RankBoost также превзошел ВС, когда размер множества характеристик был больше 200. Для средних и крупных размеров множества характеристик, RankBoost достиг наиболее низкого показателя несогласованности и самых высоких СТ, ПТР, и охвата. Кроме того, наклон кривых показал, что RankBoost лучше всех улучшал свою роботу при увеличении количества характеристик. БС имел хорошие результаты на несогласованности, СТ и охвате, но на ПТР его результат был хуже случайного угадывания (ПТР которого составляло 0,45). Это говорит о том, что, хотя БС помещает хорошие фильмы относительно высоко в своем списке (из-за его хорошей СТ), он не помещает одиночный хороший фильм в верхней части списка (из-за его плохого ПТР). Исследование данных показало, что почти всегда алгоритм ближайших соседей не рассматривает все фильмы в тестовой обратной связи и, следовательно, БС присваивал некоторым фильмам значение по умолчанию. Иногда значение по умолчанию было высоким и помещало не просмотренные фильмы в верхнюю часть списка БС, что может ухудшить ПРТ, если большинство не просмотренных фильмов не являются хорошими (в соответствии с обратной связью). RankBoost и БС непосредственно старались свести к минимуму несогласованность, в отличие от алгоритма регрессии, и их показатели несогласованности были немного лучше, чем у случайного угадывания (чья несогласованность составляла 0,5). Алгоритм регрессии имел лучшие ПРТ и охват, чем случайное угадывание, но СТ была хуже, чем у случайного угадывания (чья СТ равнялась 0,41). Это говорит о том, что большинство хороших фильмов появляются в конце списка, даже при том, что первый хороший фильм появляется почти в начале списка. Кроме того, судя по наклонам кривых характеристик, алгоритм регрессии не использовал дополнительной информации, представленной большим количеством характеристик. Работа ВС была очень близка к RankBoost для множеств характеристик размером 100 и 200. Его результаты особенно впечатляют, если учесть тот факт, что RankBoost пытается свести к минимуму количество несогласованностей, в то время как ВС является довольно простым подходом, основанным на корреляции. Аналогичное поведение для ВС наблюдали Breese, Heckerman и Kadie (1998), эксперименты они проводили с набором данных EachMovie. Тем не менее, ВС, кажется, не масштабируется, также как RankBoost, если размер множества характеристик увеличивается. Как и алгоритм регрессии, кажется, что ВС не использовал дополнительную информацию, представленную большим количеством характеристик, и, по сути, его работа ухудшается при изменении размера множеств характеристик от 750 до 1000.

Эффективность алгоритмов в зависимости от размера наборов характеристик

Рисунок 10. Эффективность алгоритмов в зависимости от размера наборов характеристик

В нашем следующем эксперименте мы исследовали влияние плотности характеристик, количества фильмов, оцененных каждым зрителем. Мы разделили множество характеристик на группки в зависимости от их плотности. Эти группки состояли из 10-20, 21-40, 41-60, 61-100, 101-1455, где 1455 являлось максимальным количеством фильмов, которые были оценены одним зрителем в наборе данных. Мы выбрали случайное множество из 1000 характеристик (зрителей) от каждой группки для оценки на случайном непересекающемся множестве 1000 целевых пользователей обратной связи (разной плотности). Мы прогнали алгоритмы на таких шести случайных разбиениях, вычислили средние значения четырех мер погрешности каждого разбиения, а затем усреднили их. Результаты показаны на рисунке 11. Координата x каждой точки является средней плотностью характеристик в одной группке; например, 80 — средняя плотность характеристик, которая находится в диапазоне 61-100. Относительная эффективность алгоритмов была такой же как на рисунке 10. Алгоритм RankBoost снова показал себя лучшим, и это проявилось лучше всего, когда была представлена дополнительная информация, полученная более плотными характеристиками. При увеличении плотности характеристик, эффективность БС на СТ, несогласованности и охвате улучшилась более существенно, чем просто при увеличении количества характеристик (рис. 10). Тем не менее, на ПРТ-БС он продолжал работать хуже, чем случайное угадывание (ПРТ которого было 0,45). Кроме того, эффективность БС уменьшается при увеличении плотности характеристик. Алгоритм регрессии поддерживал ту же относительную эффективность, что и случайное угадывание, как и в предыдущем эксперименте, и она в значительной степени не зависела от увеличения плотности характеристик.

Эффективность алгоритмов в зависимости от плотности характеристик

Рисунок 11. Эффективность алгоритмов в зависимости от плотности характеристик

В данном случае ВС снова занимает второе место и его результаты близки к RankBoost в отношении всех четырех показателей эффективности. Кроме того, как и RankBoost, ВС также хорошо масштабируется с увеличением плотности характеристик. Темпы роста, кажется, сравнимы с RankBoost для показателей охвата, СП и ПРТ, и немного медленный рост наблюдается в случае с показателем несогласованности. Хотя различия эффективности между RankBoost и ВС являются статистически значимыми, преимущество RankBoost над ВС гораздо менее выраженно, по сравнению с БС и алгоритмом регрессии.

В предыдущих двух экспериментах мы изменяли количество информации, предоставленную характеристиками; в следующем эксперименте мы изменим количество информации, полученную от обратной связи. Мы меняли плотность обратной связи, количество фильмов, ранжированных целевым пользователем. Мы распределили пользователей по группкам в зависимости от плотности, таким же образом, как и в предыдущем эксперименте. Мы прогнали алгоритмы на 1000 целевых пользователях каждой плотности, используя половину фильмов, которые были оценены каждым пользователем для обучения, а другую половину для тестирования. Мы использовали случайно выбранное устойчивое множество из 1000 характеристик. Мы повторили этот эксперимент на шести случайных разделениях данных и усреднили результаты, которые представлены на рисунке 12.

Эффективность алгоритмов в зависимости от плотности обратной связи

Рисунок 12. Эффективность алгоритмов в зависимости от плотности обратной связи

Наиболее заметный эффект от увеличения плотности обратной связи проявляется в снижении эффективности всех четырех алгоритмов относительно охвата и СТ и эффективности ВС, БС и алгоритма регрессии относительно ПРТ (RankBoost способен улучшить ПРТ). Кроме этого, сравнительная эффективность алгоритмов друг относительно друга была аналогична результатам предыдущих экспериментов, за исключением того, что различия между RankBoost и ВС, в зависимости от плотности обратной связи, были более выраженными.

Производительность случайного угадывания

Рисунок 13. Слева: производительность случайного угадывания, когда изменяется доля хороших фильмов (количество фильмов — 60). Справа: производительность случайного угадывания, когда изменяется количество отранжированных фильмов (доля хороших фильмов составляет 0,25).

Особый интерес вызывает производительность ВС, когда плотность обратной связи составляет не более 40. В этом случае, ВС является лучшим алгоритмом по отношению к показателям несогласованности, СТ и ПРТ и достигает практически того же охвата, что и RankBoost. Однако при увеличении плотности обратной эффективность ВС ухудшается, и для плотности обратной связи свыше 100 эффективность ВС становилась средней, что сопоставимо с БС относительно всех показателей эффективности, за исключением ПРТ. В противоположность этому, RankBoost стабильно улучшается при увеличении размера множества обратной связи. Такое поведение RankBoost распространено среди алгоритмов контролируемого обучения, которые, как правило, улучшаются пропорционально контролю. Изначально, кажется, что алгоритмы должны работать хуже при увеличении количества фильмов, отранжированных целевыми пользователями. Можно было бы ожидать, что алгоритмы справятся лучше с более обученной обратной связью. Действительно это так для меры несогласованности (за исключением алгоритма регрессии и ВС, как и в первой серии экспериментов). Это дает основание предположить о недостатке мер точности: они зависят от количества фильмов, участвующих в обратной связи. С другой стороны, мы наблюдали, что эффективность случайного угадывания также ухудшается при увеличении плотности обратной связи, что предполагает то, что задача ранжирования по своей природе более сложная. Это, несомненно, тот случай, когда доля хороших фильмов в обратной связи уменьшается при увеличении плотности обратной связи. Мы обнаружили, что оба эффекта имеют место. Сначала мы рассчитали долю хороших фильмов, участвующих в обратной связи, для каждой ее плотности. Для плотностей 10-20, 21-40, 41-60, 61-100 и более 100, доли, соответственно, составляли 0,33; 0,26; 0,22; 0,20; 0,18. При уменьшении этой доли, задача ранжирования становится более трудной. Например, левый график на Рисунке 13 показывает эффективность случайного угадывания, в отношении трех показателей, при изменении доли хороших фильмов как 1/2 , 1/3 , 1/4 , 1/5 (число отранжированных фильмов составляло 60) . Тем не менее, правый график на Рисунке 13 показывает эффективность случайного угадывания, когда доля хороших фильмов постоянна (0,25), а количество фильмов, которые были отранжированы, варьируется. Здесь измерительная характеристика ухудшается, что зависит от измерений, а не от сложности самой задачи. То есть, это результат выбора обучающей выборки данных и (фиксированное) копирование каждой пары (фильма, рейтинга), что не обеспечивает дополнительную информацию или вызов для описанных алгоритмов. Эта зависимость от количества фильмов, которые были оценены, является недостатком этих трех мер точности, так как в идеале мы хотели бы, чтобы они оставались постоянными для задач той же сложности.

Наши эксперименты показывают, что RankBoost работает лучше, чем алгоритм регрессии и БС относительно задачи рекомендации фильмов. Он также работает лучше, чем ВС, если размер плотности характеристик или обратной связи относительно велик. Подход RankBoost к упорядочению, основанном на относительных сравнениях, работает гораздо лучше, чем алгоритм регрессии, который рассматривает рейтинг фильма как абсолютные числовые значения. Одной из причин низкой эффективности алгоритма регрессии может являться переобучение: его решение подвергается только слабому ограничению (наиболее короткая длина). Тем не менее, пока не ясно, связано ли это улучшение RankBoost с использованием относительных предпочтений или с усилением или с тем и другим. Чтобы попытаться разделить эти эффекты, мы могли бы проверить алгоритм регрессии на относительных предпочтениях путем нормализации рейтинга каждого зрителя фильма так, чтобы распределение рейтингов одного зрителя имело то же значение и дисперсию, что и распределение рейтингов каждого другого зрителя. RankBoost также работал лучше, чем представленный здесь алгоритм ближайших соседей. Основываясь на этих экспериментах, мы смогли разработать лучший алгоритм ближайших соседей, выбирая рейтинги по умолчанию в лучшую сторону и, принимая во внимание при выборе ближайшего соседа количество фильмов, отранжированных по соседству. Было бы также целесообразно сравнить RankBoost с алгоритмом, который находит k ближайших соседей целевого пользователя и усредняет их прогнозирование. Такой эксперимент, отличит простой поиск, комбинацию подобных пользователей, метод усиления поиска и комбинацию. Усреднение прогноза k ближайших соседей вводит зависимость абсолютных значений, так что этот предложенный эксперимент будет способствовать дальнейшей проверке нашей гипотезы о том, что относительные предпочтения более информативны. В наших экспериментах ВС являлся алгоритмом, который по эффективности приближался к RankBoost, и в большинстве случаев для несложных задач он представляется более эффективным, чем RankBoost. Тем не менее, при увеличении сложности обучающих данных (то есть их размера) или контроля (обратной связи) усиливается эффективность RankBoost, в то время как эффективность ВС только приближается к нему или даже ухудшается. Возможное объяснение заключается в том, что RankBoost, будучи алгоритмом обучения, который пытается минимизировать целевую функцию, предназначенную для ранжирования, в состоянии построить более сложные предположения при увеличении количества и разнообразия образцов, участвующих в процессе обучения. ВС, с другой стороны, использует постоянный коэффициент корреляции, который основан на памяти, и, таким образом проявляет меньшую гибкость и приспособляемость при росте числа обучающих примеров. Другими словами, так как RankBoost строит разные функции ранжирования отдельно для каждого пользователя, то он имеет более высокий потенциал в использовании той информации, что передается отдельными пользователями, которые оценили большое количество фильмов. Мы также хотели бы отметить то, что можно взять лучшее из каждого подхода: RankBoost может использовать ВС как одну из возможных слабых функций ранжирования, которую он может выбрать на каждом цикле. Конечным результатом будет алгоритм, который прибегает к простой корреляции, основанной на памяти, когда объем данных мал, и постепенно переходит к дифференциальным подходам, если количество обучающих данных растет.

В ряде приложений возникает задача объединения предпочтений, включая задачу объединения результатов различных поисковых систем и совместной фильтрации, такие как создание рекомендаций к фильму. Важным свойством этих задач является то, что наиболее релевантная информация для объединения, представляет собой относительные предпочтения, а не абсолютные рейтинги. Мы дали формальную основу и эффективный алгоритм для задачи объединения предпочтений, которые хорошо показали себя в наших практических опытах. Наша система обучения состоит из двух алгоритмов: алгоритм усиления RankBoost и слабый обучающийся. Ввод в систему включает в себя пространство экземпляров X, n признаков ранжирования и функцию обратной связи размера |Φ|, которая ранжирует подмножество экземпляров XΦ⊆ X. Учитывая этот ввод, RankBoost обычно работает за O(|Φ|) время, и наивная реализация слабого ученика работает за O(n|Φ|XΦ) время. Если мы используем бинарные слабые рейтинги и ищем лучший слабый рейтинг, используя третий метод, то мы можем реализовать слабого ученика за время равное O(n|XΦ|+|Φ|). Если мы используем бинарную функцию обратной связи, то мы можем реализовать RankBoost за время, которое линейно зависит от количества экземпляров в обратной связи. Если дополнительно использовать двоичные слабые рейтинги, мы можем реализовать слабого ученика за O(n|XΦ|) время. Эти два условия являются как естественными, так и полезными. Бинарные рейтинги довольно просты, и это делает их легкими для эффективного создания, анализа и вычисления. Хотя один такой рейтинг может иметь только слабую прогнозирующую способность, многие из них могут быть объединены с помощью усиления высокоточного прогнозирования, как показали наши эксперименты. Что касается ограничения функции обратной связи, чтобы сделать ее двоичной, то это часто не уменьшает применимость алгоритма, так как многие приложения используются с бинарной обратной связью, например, информационный поиск.

В наших экспериментах мы использовали слабого обучающегося, который выводит ограниченный признак ранжирования в качестве слабого рейтинга. Хотя это ограничило работу, RankBoost, тем не менее, был в состоянии объединить рейтинги для высокоточного прогнозирования. В задаче мета-поиска RankBoost показал себя лучшей поисковой стратегией для каждой меры погрешности. В задаче по рекомендации фильма, RankBoost стабильно превзошел стандартные алгоритмы регрессии и ближайших соседей и был постоянно лучше, чем метод ВС для средних и крупных условий задачи. Наши эксперименты также показывают, что RankBoost может работать хорошо на наборах данных различных размеров. Задача мета-поиска имела небольшое количество признаков ранжирования (от 16 до 22), большое пространство экземпляров (10000 URL-адресов) и большую обратную связь (10000 URL-адресов). Задача по рекомендации фильма имела большое количество признаков ранжирования (от 100 до 2000), меньшее пространство экземпляров (1628 фильмов), а диапазон размеров обратной связи составлял 10-1455. Одним из важных внутренних свойств RankBoost, как алгоритма усиления, является его способность объединять различные подходы к ранжированию. В то время как задача объединения общих признаков ранжирования может задавать не двудольную обратную связь, концепция усиления ранжирования, которую мы представили в данной статье, предлагает принципиальную и эффективную инфраструктуру алгоритма. Поэтому RankBoost также может быть использован в качестве инструмента для построения гибридной системы ранжирования, которая сочетает различные алгоритмы ранжирования, давая высокую точность и повторное ранжирование мета-алгоритма. Имеются многочисленные направления для будущей работы. Мы утверждаем, что относительные предпочтения могут быть важнее, чем абсолютные значения. Результаты наших экспериментов по задаче рекомендации фильма следующие: RankBoost значительно опережает алгоритмы ближайших соседей и регрессии. С целью дальнейшего различия значений и рейтингов, мы предложили два эксперимента: протестировали алгоритм регрессии на относительных предпочтениях путем нормализации значений каждого зрителя, и протестировали усредненную комбинацию из k ближайших соседей. Как мы уже указывали ранее, многие задачи ранжирования имеют двустороннюю обратную связь и, следовательно, их также можно рассматривать как задачи бинарной классификации. Для таких задач было бы интересно сравнить RankBoost с AdaBoost в сочетании со слабым обучающимся для минимизации ошибки классификации. AdaBoost выдает действительное значение для каждого экземпляра, который затем ограничивается для проведения классификации. Мы можем сравнить упорядочение по RankBoost с упорядочением по AdaBoost для экземпляров по весу классификации, чтобы увидеть, превосходит ли минимизация рейтинга потерь минимизацию ошибки классификации. Что же касается самого алгоритма RankBoost, первый способ установки αt является наиболее общим и требует числового поиска. Schapire и Зингер (1999) предлагают использовать общие итеративные методы, такие как метод Ньютона-Рафсона. Из-за того, что такие методы часто не имеют никаких доказательств сходимости или могут быть численно неустойчивым, мы хотели бы найти итерационный метод специального назначения с доказательством сходимости. Конечно, для практичности, метод также должен быстро сходиться. Возможно, наиболее важным практическим направлением исследований является применение RankBoost для проблем поиска информации, в том числе поиска текста, речи и изображений. Эти проблемы важны сегодня в связи с огромным количеством данных, доступных другим пользователям через Глобальную паутину и крупномасштабных баз данных, и им уделяют внимание различные научные сообщества. В недавней работе (Iyer и др.., 2000), две версии RankBoost сравнили с традиционными подходами поиска информации. Эксперименты данной работы показывают, что RankBoost может обеспечить альтернативный подход комбинирования весов показателей, однако, производительность RankBoost во многом зависит от качества обратной связи. Различные варианты RankBoost могут оказаться полезными в задачах обучения, которые на первый взгляд, кажется, не связаны с ранжированием. Например, Walker, Rambow и Rogati (2001) недавно успешно использовали RankBoost, чтобы обучить систему генерирования предложений. В другой работе, Коллинз (2000), описывает эксперименты, используя RankBoost для задачи обработки естественного языка, в частности, для переранжирования возможного грамматического разбора, проводимого возможным парсером. Парадигма, предложенная Коллинзом, может быть применена к другим параметрам, для которых результаты приближенного или точного поиска дают упорядоченный список «кандидатов» с появлением «правильного» элемента где-нибудь в упорядоченном списке. Этот список может быть пересортирован с помощью RankBoost для новых наборов функций. Наконец, мы хотели бы отметить, что эта работа является частью общей научно-исследовательской работы по алгоритмам обучения для порядковых данных. Мы надеемся, что эта работа вызовет дальнейший интерес к таким проблемам, которые являются сложными и относительно неисследованными. Действительно, последние работы (Crammer и Singer, 2001, 2002, Lebanon и Lafferty, 2002) по проблемам ранжирования показывают, что некоторые из методов, исследуемые в этой работе, могут распространяться на обучение функций ранжирования в режиме онлайн и на экспоненциальные модели ранжирования.

Оригинал: «An Efficient Boosting Algorithm for Combining Preferences»

Ссылки:

Will Hill, Larry Stead, Mark Rosenstein, and George Furnas. Recommending and evaluating choices in a virtual community of use. In Human Factors in Computing Systems CHI’95 Conference Proceedings, pages 194–201, 1995.

John S. Breese, David Heckerman, and Carl Kadie. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, pages 43–52, 1998.

Gerard Salton and Michael J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.

Robert E. Schapire and Yoram Singer. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 37(3):297–336, December 1999.

Raj D. Iyer, David D. Lewis, Robert E. Schapire, Yoram Singer, and Amit Singhal. Boosting for document routing. In Proceedings of the Ninth International Conference on Information and Knowledge Management, 2000.

Marilyn A. Walker, Owen Rambow, and Monica Rogati. SPoT: A trainable sentence planner. In Proceedings of the 2nd Annual Meeting of the North American Chapter of the Associataion for Computational Linguistics, 2001.

Michael Collins. Discriminative reranking for natural language parsing. In Proceedings of the Seventeenth International Conference on Machine Learning, 2000.

Koby Crammer and Yoram Singer. Pranking with ranking. In Advances in Neural Information Processing Systems 14, 2001.

K. Crammer and Y. Singer. A new family of online algorithms for category ranking. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2002.

Guy Lebanon and John Lafferty. Cranking: Combining rankings using conditional probability models on permutations. In Proceedings of the Nineteenth International Conference on Machine Learning, 2002.