Машинное обучение, ФКН ВШЭ

Семинар №22

1 Обучение модели попарных соотношений

Ранее в курсе мы рассматривали задачи обучения с учителем, в которых данные
имеют вид {(xi , yi )}ℓi=1 , где xi — вектор признаков, а yi — таргет, который необходимо
предсказать по признакам (задачи классификации и регрессии). Также мы рассмат-
ривали задачи, где данные имеют вид {xi }ℓi=1 – задачи кластеризации или задачи
понижения размерности.
На лекции мы рассмотрели новую постановку — задачу ранжирования и крат-
ко рассмотрели существующие подходы (pointwise, pairwise, listwise). Несмотря на
то, что во всех подходах целью является верное ранжирование объектов, считается,
что заранее известно некоторое истинное значение релевантности (которое может
быть основано на некоторой оценке ассессора, клике по документу или каком-либо
другом сигнале), которое используется в оптимизируемом функционале качества.
Однако зачастую данные в подобных задачах представлены лишь попарными взаи-
модействиями между объектами, то есть для некоторого набора объектов {xi }ni=1 обу-
чающая выборка представлена случайным подмножеством попарных соотношений:
{xik > xjk }ℓk=1 . Также для таких соотношений может быть известен некий контекст.
Далее мы будем рассматривать модели для попарных соотношений в контек-
сте матчей между двумя игроками xi , xj , при этом наши рассуждения могут быть
полностью перенесены на все остальные случаи применения этих моделей.
В общем случае данные о попарных соотношениях выглядят следующим обра-
зом:

• признаки объектов — для каждого игрока известно его признаковое описание

xi ∈ Rd (id, вес, рост, национальность и т.п.);

• признаки контекста — для каждого матча известно его признаковое описание

zk ∈ RD (погода, время, место и т.п.);

• набор соотношений — история матчей в виде троек {(xik , xjk , zk )}, где на первом
месте стоит победитель матча.

1
 2

Задача 1.1. Придумайте признаки объектов и признаки контекста для следующих

задач:

• игра в теннис,

• рекомендации ресторанов,

• идентификация личности,

• клики на поисковую выдачу.

Решение.

• В игре в теннис объектом является игрок (теннисист), а соотношением яв-

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

• При рекомендации ресторанов объектом является ресторан, а соотноше-

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

• Для идентификации личности можно поставить следующую задачу – есть

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

• Пусть у нас есть задача попарного сравнения документов в контексте одного за-
проса. Выборку набираем следующим образом – документ, на который кликнул
человек в поисковой выдаче лучше всех документов, которые стоят выше него
и на которые человек не кликнул. Признаки объекта это признаки документа:
bm25, ctr, порядковый номер в выдаче и т.д., признаки контекста – длина за-
проса, размер выдачи на странице, версия поисковика (мобильная, браузерная)
и т.д.


 3

§1.1 Rote learning (зазубривание)

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

Pℓ
k=1 [xik = xi ][xjk = xj ]
P (xi победит xj ) = Pℓ . (1.1)
k=1 ([xik = xi ][xjk = xj ] + [xik = xj ][xjk = xi ])

Так как могут быть ситуации, когда игроки никогда не встречались до этого (то
есть в числителе и знаменателе стоят нули), то необходимо произвести сглаживание
формулы (1.1):

Pℓ
k=1 [xik = xi ][xjk = xj ] + 1
P (xi победит xj ) = Pℓ .
k=1 ([xik = xi ][xjk = xj ] + [xik = xj ][xjk = xi ]) + 2

Минусы:

• Необходимо очень много данных.

• Не учитывает никаких признаков.

• Не даёт оценки на исход матча между игроками, которые не встречались преж-

де.

§1.2 Модель Брэдли-Терри

Следующая модель, которую мы рассмотрим, сопоставляет каждому игроку xi
некоторый параметр γi , который может быть интерпретирован как сила (уровень)
игрока. Вероятность победы игрока xi над игроком xj , в такой модели записывается
как:

exp(γi )
P (xi победит xj ) =
exp(γi ) + exp(γj )
1
= = σ(M(xi , xj )),
1 + exp(γj − γi )

где σ(x) – сигма-функция, а функция M(xi , xj ) = γi − γj – функция мат-

ча (matchup function). Функцию матча M(xi , xj ) можно задать произвольным об-
разом, но при этом должны выполняться условия:

1. M(xi , xj ) ∈ R, при этом положительные значения означают, что с большей веро-

ятностью победит i, а отрицательные — наоборот. Вероятность победы любого
из игроков при M(xi , xj ) = 0 равняется 0.5;

2. при M(xi , xj ) → +∞, P (xi победит xj ) → 1, и наоборот;

 4

3. M(xi , xj ) = −M(xj , xi ) — данное условие необходимо, чтобы выполнялось

P (xi победит xj ) = 1 − P (xj победит xi ).

Плюсы:
• Обладает небольшим числом параметров;

• Даёт оценки на исход матча между игроками, которые не встречались прежде.

Минусы:
• По-прежнему не учитывает никаких признаков.

Задача 1.2. Запишите оптимизационную задачу, которую необходимо решить для

настройки параметров этой модели. Рассчитайте градиенты полученного функцио-
нала.
Решение.
ℓ
X
log P (xik победит xjk ) → max
{γi }
k=1

ℓ ℓ
∂ X ∂ X
log P (xik победит xjk ) = [ik = s] log P (xik победит xjk )
∂γs k=1 ∂γs k=1
ℓ
∂ X
+ [jk = s] log P (xik победит xjk )
∂γs k=1
ℓ  
X 1
= [ik = s] σ(M(s, xjk ))(1 − σ(M(s, xjk )))
σ(M(s, x jk ))
k=1
ℓ  
X 1
+ −[jk = s] σ(M(xik , s))(1 − σ(M(xik , s)))
k=1
σ(M(x ik , s))

ℓ   X ℓ  
X exp(γjk ) exp(γs )
= [ik = s] − [ik = s]
k=1
exp(γs ) + exp(γjk ) k=1
exp(γik ) + exp(γs )

§1.3 Pairwise logistic regression model

Модель Брэдли-Терри может быть легко расширена для учёта признаков иг-
роков, если вместо в качестве параметров рассматривать не γi , а обучить линейную
модель для оценки силы игрока, то есть сила γi игрока xi будет выражаться следу-
ющим образом:

γi = w T xi .
Заметим, что если в качестве признакового описания игрока мы возьмём его
id, представленный с помощью one-hot-encode вектора, то получим модель Бредли-
Терри в явном виде.
 5

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

Тем не менее, модель по-прежнему не может учесть признаки матча. Действи-
тельно, попробуем добавить признаки матча zg к признаковому вектору каждого
игрока:
     
T xi xj T xi − xj
M(a, b) = w − =w .
zk zk 0
Видим, что признаковое описание матча не влияет на функцию M(xi , xj ), а по-
тому не участвует в оптимизируемом функционале. Попробуем переписать функцию
M(xi , xj ) так, чтобы она явно учитывала признаки матча линейным образом:

M(xi , xj ) = w T (xi − xj ) + wkT zk ,

но заметим, что в этом случае не выполняется условие 3 для функции мат-

ча M(xi , xj ).

§1.4 Blade-chest model

Следующий подход, который мы рассмотрим, предлагает оригинальный вари-
ант функции M(a, b). Идея подхода заключается в том, что представление силы
игрока одним числом плохо описывает данные, в частности, такая модель не мо-
жет описать соотношение "камень-ножницы-бумага"между тремя игроками. Поэто-
му предлагается обучать для каждого игрока xi два вектора — xbladei и xchest
i . Чтобы
оценить вероятность победы игрока xi над игроком xj необходимо сравнить расстоя-
ния между представлениями — если xblade
i ближе к xchest
j , чем xblade
j ближе к xchest
i , то
вероятнее победит игрок xi . Названия представлений (клинок и грудь) дают понят-
ную интерпретацию этих векторов. На рис. 1 эта интерпретация проиллюстрирована.

Рис. 1. На рисунке проиллюстрирована интерпретация обучаемых представлений. Между игроками

a и b происходит поединок. Видно, что клинок игрока a ближе к груди игрока b, чем клинок игрока
b к груди игрока a, следовательно игрок a имеет более высокие шансы на победу.

Функция M(xi , xj ) в этой модели записывается как

M(xi , xj ) = kxblade
j − xchest
i k2 − kxblade
i − xchest
j k2 .
 6

Также можно записать функцию M(xi , xj ) альтернативным способом, исполь-

зуя скалярное произведение:

M(xi , xj ) = hxblade
i , xchest
j i − hxblade
j , xchest
i i.
В предыдущей модели мы использовали линейную комбинацию признаков для
оценки силы игрока. Тот же подход мы можем использовать для оценки искомых
представлений. Кроме того, помимо линейной комбинации признаков игроков, можно
также использовать любую дифференцируемую функцию для оценки этих векторов.
В общем виде можем записать:

xblade
i = fblade (Bxi )
xblade
j = fblade (Bxj )
xchest
i = fchest (Cxi )
xchest
j = fchest (Cxj ).

Получение данных представлений можно рассматривать как полносвязный

слой нейросети с нелинейностью. Без ограничений общности мы можем использо-
вать любые архитектуры нейросетей для обучения данных представлений.
В данной модели мы можем учесть признаки игры zk одним из двух способов:

1. Первый способ заключается в добавлении признаков игры к признаковому опи-

санию каждого игрока:

  
x
xblade
i =fblade B i ,
zk
  
x
xchest
i =fchest C i .
zk

2. Второй способ заключается в поэлементном домножении векторов представ-

лений на векторы представлений матча, полученные из признакового описания
матча аналогично векторам xblade , xchest , то есть:

xblade
i = fblade (Bxi ) · fmatch (B ′ zk ),
xchest
i = fchest (Cxi ) · fmatch (C ′ zk ).