dient descent. Главной особенностью алгорит-ма LF+SGD являются два обучающих пара-метра в соответствии с числом факторных матриц.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
И
И
Е
Е
С
С
Т
Т
Н
Н
И
И
К
К


П
П
Е
Е
Р
Р
М
М
С
С
К
К
О
О
Г
Г
О
О


У
У
Н
Н
И
И
И
И
Е
Е
Р
Р
С
С
И
И
Т
Т
Е
Е
Т
Т
А
А


201
4




Математика. Меμаβика. Иβформатика




Иыμ.

3(26)

48






УДК

004.9

Два а
лгоритм
а

на основе техники
стохастического градиентного спуска


для рекомендательных систем


В. Н
.
Никулин
,

Т. Г
.
П
розорова

Вятский

государственный университет

Россия,

61
000
0,
Киров
, ул.
Московская, 36

vnikuin
.
uq
@
gi
.
co


Рекомендате
льная система


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

студе
н
тов,
состоящи
х

в
про
гнозе
,

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

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

неиз
вестна и требуе
т прогнозирования, хорошо себя зарекомендовали ст
о
хастические градиентные методы. В данной работе рассмотрена оптимизация

т
а
ких наибол
ее
значимых вариативных параметров, как количество
факторов
,
параметры
обу
чения

и регул
и
рования
, число гло
бальных итераций. Исследования

и эксперименты
базиру
ю
тся на данных
,
которые использовались при проведении

международных соревнований по анализу данных

Grockit
и hess

на пла
т
форме Kgge.


Ключевые слова:

матричная факторизация
;

коллаборативная фильтрация
;

рекоменд
а
тельная система
;

onine

обучение
;

шахматные рейтин
ги
;

попарные сравнения
;

обучение
без учителя
.



Введение



В последнее время модели на ос
нове н
е
зависимого компонентного анализа и нео
т
р
и
ц
а
тельной матричной факторизации (NMF
:
non

negtive

trix

fctoristion
) ста
ли

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

[1].

Следует о
т
м
е
тить, что факторные

переменные
не явл
я
ют
ся
явными

в том смысле, что не использ
у
ется
никаких предварительных знаний о п
е
реме
н
ных за исключением таких общих
к
а
честв
,



© Никулин В. Н., Прозорова Т. Г., 2014

как гауссовость, статистическая нез
а
вис
и
мость или неотриц
а
тельность.

Примерами методов успешных матри
ч
ных факторизаций являются синг
улярное ра
з
ложение и неотрицательное матричное ра
з
л
о
жение [2]. Кроме того, разработан новый
,

очень быстрый алгоритм матричной фактор
и
зации на основе
метода градиентного спуска

(GMF
:
grdient

sed

trix

fctoristion
), к
о
торый представлен
в
наших
предыдущ
их
статьях [3] и [4]
.


Основным предметом данной статьи
является более специализированная версия
алг
о
ритма GMF. Название

нового

алгоритма

L
FSG
:

ist

fctoriztion

pus

stochstic

gr

Два алгоритма на основе техники стохастического градиентного спуска


49
d
i
ent

descent
.
Главной особен
ностью
алгори
т
ма
L
FSG явля
ю
тся два обучаю
щих пар
а
метра в соответствии с числом факторных
матриц. По определению процесс обучения
включает р
е
гул
ирование

как неотъемлемый
компонент.

Заметим, что метод стохастического
градиентного спуска (
SG
) является

особе
н
но
эффективны
м

в

том случае, когда целева
я
функция представляет собой сумму большого
числа элементов со многими
переменными

параметрами. Другим примером применим
о
сти
стохастического градиентного спуска

служит

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

(
см
. раздел
3)
. Следует заметить, что основная
идея алгоритма
,

представленного
в разделе
3.1
,

опубликована в

р
а
бо
те

[5].


1.
Ф
акторизация
списков
на основе
техники стохастического

градиен
т
но
го спуска (
L
FSG)


В соответствии с [6] в этом разделе

и
с
пользуются следующи
е обозначения. Матр
и
ца
рейтингов обозначается как


J
I



1
,
0
, где
значение
1

ij
x

показывает, что
i

й ст
у
дент
правильно решил
j

ю задачу и
0

ij
x

в пр
о
тивном случае.
I

и
J



общее колич
ество ст
у
дентов и задач соответственно. Верхний и
н
декс крышка» обозначает прогнозируемое
значение заданной величины:
ˆ
x



прогноз
и
руемое значение
x
.

К
оличество студентов
I

обычно измер
я
ется сотнями тысяч, кол
ичество задач
J



т
ы
сячами. Данные представлены в матрице ре
й
тингов


размера
J
I

, которая является
разреженной в связи с
тем
, что
большинств
о

значений

неизвестно
.
Обозначим множество
известных пар (
i
,

j
)

матрицы


как

.
Н
а
шей целью является
нахождение небольшого
числа
факторов

или
метастуде
н
тов
)
,
in(
J
I
K

.
Затем исходная
мат
риц
а

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


в виде произведения двух
матриц

AB


,


(1)

где весовая матрица
A

имеет размеры
K
I

,
фа
кторная матрица
B



J
K

, ка
ж
дая из
K

строк представляет собой
прогноз того
,

как

мета
студент

справится с
соответствующей
м
е
та
з
а
дач
ей
.

Главной особенностью стохастического
градиентного спуска яв
ляется отсутствие тр
е
бования пре
д
ставления входных данных


в
матри
чной форме
. Фактически
приведенный

ниже алгоритм работает не с матрицей, а со
сп
и
ском данных.

Отметим, что ф
ормула (1) является не
точным, а приблизительным

соотношени
ем
,
где последовательные прогнозируемые вел
и
чины для
элементов

(
i
,

j
)

рейтинговой матр
и
цы


вычисляю
т
ся по формуле

)
exp(
1
1
ˆ
ij
ij
s
x



,


(2)

где



K
k
kj
ik
ij


s
1
.

Задача состоит
в
м
аксимиз
ации

следующ
ей

функци
и

потерь (бино
миальное отклон
е
ние):






)
,
(
2
1
#
1
)
,
,
,
(
j
i
ij
H
B
A
L


,


(3)

22
12
11
1
n(10)
KK
ijijikkj
kk
HE




, (4)

)
ˆ
1
n(
)
1
(
)
ˆ
n(
ij
ij
ij
ij
ij
x
x
x
x
E





, (5)

где
0

d

,
2
,
1

d



регулирующие

параме
т
ры
.

Приведем алгоритм
L
F

SG

с квадр
а
тичной регуляризацией.


Алгоритм
LF

SG
:

Исходные

данные и инициализация
:




ре
й
тинговая матрица, организованная в виде
сп
и
ска;
N



число глобальных итераций;
1

K



число факторов;
0

d

,
0

d

,
2
,
1

d



обучающие и регуляризационные
пар
а
метры
.

Глобальный цикл
: повторить
N

раз шаги 1

12.

Шаг

1 (в
нутренний цикл
)
.

Д
ля каждой пары


)
,
(
j
i

выполнить шаги 2

12
.

Шаг

2
.
Вычислить прогнозируемое зна
ч
ение:




K
k
kj
ik


S
1
,
)
exp(
1
1
S
pr



.

Шаг

3
. Вычислить погрешность прогноза:
pr
x
ij



.

В.
Н
. Никулин, Т. Г. Прозорова


50
Шаг

4

(внутренний цикл по факторам)
. Для
k

от 1 до
K

выполнить шаги 5

12
.

Шаг

5
.
kj
ik




.

Шаг

6
.
)
(
1
1
ik
kj
ik
ik











.

Шаг

7
.
kj
ik


S
S




,
)
exp(
1
1
S
pr



.

Шаг

8
.
pr
x
ij



.

Шаг

9
.
kj
ik




.

Шаг

10
.
)
(
2
2
kj
ik
kj
kj











.

Шаг

11
.
kj
ik


S
S




,
)
exp(
1
1
S
pr



.

Шаг

1
2
.
pr
x
ij



.

Результат
:
A

и
B



факторные
матрицы
.


Замечание 1
.

У
словия
регулирования
(4) являют
ся необходимыми. Цель регул
ир
о
вания



приостановк
а

неоправданного
роста

элемент
ов

факторных матриц

(по абсолю
т
ной
величине)
.

Отметим, что ц
ел
евая функция (3)
включает

)
(
J
I
K


регулирующих параме
т
ров и может быть
неустойчив
ой

в случае,
е
с
ли
проц
есс

её минимизации проводится без у
чёта
взаимной зависимости
между элеме
н
тами
матриц
A

и
B
.

В

соответствии с (2) формулу (5) можно
переписать следующим образом:

)).
exp(
1
n(
)
1
(
)))
exp(
1
n(
(
ij
ij
ij
ij
ij
ij
s
x
s
s
x
E









(6)

Производные функции
ij
E

имеют сл
е
дующий вид:

kj
ij
ij
ik
ij

x
x

E
)
ˆ
(





,


(7а)

ik
ij
ij
kj
ij

x
x

E
)
ˆ
(





.


(7б)

Замечание 2.

Шаги 6 и 10 прив
еде
н
ного

выше

алгоритма
L
F

SG

представляют
наиболее важные формулы

обновления
. Их
структура непосредственно следует из фо
р
мул
(4), (7а) и (7б), где регул
ирующи
е пар
а
метры


могут
быть различны

(
так

же как параме
т
ры обучения
)
.


2. Сор
евнование
Grockit


по анализу данных

Международное соревнование
Grockit

проводилось на платформе
Kgge
1

с 18 ноя
б
ря 2011 г
.

по 29 февраля 2012 г
.

(всего 103
дня).

Использованный нами

алгоритм
прод
е
монстрировал

15

й

результат

из 241
.

Опис
а
ние метода

победи
теля

пр
и
ведено в [7].

Grockit
2



это
компания социального
обучения, которая создает
инструменты на б
а
зе
И
нтернета
, помогающие
студентам

учит
ь
ся
друг

у друга
. Основной задачей
Grockit

явл
я
ется
обес
печение студентов ги
б
ким графиком
обучения. Успех
Grockit

не
п
о
средственно з
а
висит от успехов студе
н
тов.

Grockit



это мировой
быстро
разв
и
вающийся

сервис
onine

тестирования для
л
ю
дей
, стремящихся
улучшить свои результ
а
ты

как
на стандартных тестах
, так и на
тестах,
необходимых для поступления в ко
л
ледж.

Grockit



э
то
адаптивная, персонализ
и
рующая обучающая программа, известная
своими уникальными социальными особенн
о
стями, которые помогают людям
быстро
из
у
чать новые области и
достаточно

корректно
отвечать на вопросы. Обучение
доступно
o
n
ine

в любое время дня
, из люб
ого места
, где
имеется
И
нтер
нет
.
Grockit

предсказывает
оценку
студентов
на базе
их

ответов и ход
а

процесса обу
чения
. Персонализация и незав
и
симое обучение также
очень

важны. План
обучения
Grockit

предполагает практические
тесты, ориентиро
ванные на те облас
ти

знания
,

в которых
обучающиеся
довольно слабы
, а
хоро
шо спроектированный автоматический

реп
е
титор поможет
освоить необходимые зн
а
ния

гораздо быстрее.

Функция
Grockit
.
TV

используется для
демонстрации заслуженными преподавател
я
ми
методики

решения задач, к
оторые могут
быт
ь

применены в процессе обучения. Это как
в популярной компании
Fceook
,
но
только
для обучения. Комбинируя социальное вза
и
модействие с обучением,
Grockit

поощр
я
ет
академический успех через взаимодействие с
другими обучающ
и
мися.

Пос
тавив це
лью организовать занятия

студентов в различной форме, компания со
з
дала центр
onine

взаимодействия, где студе
н
ты могут помогать друг другу в выполнении
домашнего задания, развивая тем самым
,




1

URL:
http://

www.kgge.co

2

URL:
https://grockit.co

Два алгоритма на основе техники стохастического градиентного спуска


51
важные в
XXI

в
.

качества

кооперации
. В
ы
бранные для себя тесты

мож
но

выполнять
и
н
дивидуально или в составе команды
. Соци
а
лизированное обучение позволяет многим
студентам знач
и
тельно
улучшить знания.

Становление Grockit потребовало кап
и
тала.
К
омпания
привлекла

17 млн дол
л.

в к
а
честве инвестиций
на протяжении своего с
у
щест
вования. Венчурными инвесторами были

и являются в настоящее время

Benchrk
pit, Ats Ventures и Integr pit
Prtners и индивидуальные инвесторы Марк
Пинкус (Zyng EO) и Рид Хоффман, предс
е
датель LinkedIn's (LNK).

Частью пути развития Grockit б
ыло
включение в

процесс получения

знаний
ст
и
мулирующего
элемента развлечения
(
через с
е
тевое социальное взаимодействие
)

как очень
существенн
ого

элемент
а

обучения
. К
о
гда л
ю
ди работают над заданиями, они могут отпр
а
вить мгновенное сообщение другим л
ю
дям с
ц
е
л
ью получения совета или просто
вести
диалог

через панель в правой части о
к
на.
Э
т
о

общение

не произ
вод
и
т никакого зв
у
ка, п
о
этому не явля
е
тся слишком навяз
ч
и
вым
, но и
не позволя
е
т полностью
изолир
о
ваться

и ра
с
слабиться
.

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

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

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

Grockit использует модель подписки и
сейчас насчитывает сотни тысяч зарегистр
и
рованных пользователей. Главный директор
Grockit Рой Гилберт сказал, что Grockit растет
на одну среднюю американскую высшую
школу в день и продолжит агрессив
но расти
на протяжени
и лета 201
4

г. Grockit также
расширяется в направлении сервисов для по
д
готовки студентов к широкому кругу разли
ч
ных стандарт
ных

тестов и в направлении с
о
трудничества с такими организациями
,

как
KIPP
(
knowedge

is

power

progr
)
Acdey,
которые помогают ст
удентам из бедных с
е
мей
пост
у
пать в колледж.

К 2016

г.
, по мнению Гилберта, Grockit
должен стать
наиболее эффективным ресу
р
сом для

каждого человека, которому предст
о
ит

подготовка к стандарт
ному

тесту. Если
Grockit достигнет этой цели, то он
доб
ь
е
тся

успеха

и расположения

у
мно
жеств
а

клие
н
тов,

сотрудников и инвест
о
ров.

2
.1
.

Данные
Grockit

Данные соревнования
Grockit

содержат
4851475 тренировочных записей и 93100
те
с
товых
результатов, которые нужно предск
а
зать
, к
оличество студентов
I
179106, колич
е
ство задач
J
6046. Следовательно, известные
данные составляют около 0.45% теоретич
е
ской полной информации.
Структура да
н
ных
очень простая:

мы имеем

тр
и

столб
ц
а
: индекс
студента, индекс задачи и результат (1 в сл
у
чае верного решения и 0 ин
а
че).

2
.2
.

Эксперименты

Рис
.

1 показывает сходимость алгори
т
ма как функции
индекса
глобально
го

цикла
.
Вертикальная ось показывает
величину ф
у
н
к
ции потерь

L
(
A
,
B
,0,0), где 500000 н
а
блюдений
были
слу
чайно удал
ены

из тренировочной
выборки и ис
польз
овались

для
тестирования

(прово
ди
лось

30
испытаний со
случай
ны
ми
разбиениями
).



Рис. 1.

Сходимость алгоритма
L
FSG:
L
(
A
,
B
,0,0) как функция глобальной итер
а
ции (
относительн
о горизонтальной оси)


Для

этих экспериментов использ
ов
а
лись

следующие параметры:
5

K
,
022
.
0
1


,
016
.
0
2


,
006
.
0
1


,
0085
.
0
2


.

Замечание 3.

Приведённые выше

зн
а
чения регулирующих параметров
2
,
1
,

d
d


В.
Н
. Никулин, Т. Г. Прозорова


52
использовались только для трен
и
ровки.
Скользящий контроль

проводи
л
ся

по форм
у
ле
(3)
без ре
гул
ирования
, т.е.
2
,
1
,
0


d
d

.

В базе данных имеются

54.74% пр
а
вильных отве
тов

или меток.
В дополнение м
ы
сгенерировали

случайным образом
втори
ч
ный

вектор

целевой функции с аналогичной пр
о
порцией корректных отв
е
тов
.

Рис
.

2а и 2в показываю
т сходимость а
л
горитма в случае
оригинальных

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

сначала очень быстро
уменьшается, а затем
процесс убывания з
а
медляется
. По

видимому, поведение
фун
к
ции
потерь
в течение начального пери
о
да
следует
объяснить

некоторыми скрытыми зависим
о
стями
,

содержащи
мися

в

данных. Алгоритм
обнаруживает эти зависимости очень быстро.
В случае случайных
меток

о
шибка уменьш
а
ется достаточно гладко и может быть объя
с
нена переобучением: на каждом шаге к мод
е
ли
доб
авляется
I

J

новых параметров. Рис
.


наиболее интересен
:

он показывает разницу
между графиками на рис
.

2в и 2а.
Э
та разн
и
ца
увеличивается до
некоторого
максимал
ь
н
о
го значения, а затем уменьшается. Можно
пре
д
положить
, что это максимальное знач
е
ние
(на гор
изонтальной оси)
может быть и
с
пользов
а
но в качестве критерия для выбора
кол
и
чества факторов
K
. Эта гипотеза по
д
твержд
а
ется графиком на рис
.

2г. В соотве
т
ствии с рис
.

2б и 2д можно сказать, что опт
и
мальное колич
е
ство факт
о
ров
K

5.

Тепловая карта

(
hot

p
)
,
представле
н
ная на рис
.

3, показывает поведение ошибки
скользящего контроля

в зависимости от наб
о
ра параметров: а


1


по вертикали,
1


по г
о
ризонтали; б



1

,
2

; в



1

,
2

; г



2

,
2

.

Рис
.

3в иллюстрирует значимость регуляр
и
з
а
ции для преодоления
проблемы
переобуч
е
ния.
При проведении экспериментов и
спол
ь
зов
а
лись значения
5

K

и
24

N
.

Замечание 4.

Рис
.

3 показывает р
е
зультаты
скользящего контроля

ниже 0.249 в
случае
, когда
параметры
выбраны правил
ь
но.
Этот результат представляется весьма конк
у
рентоспособн
ым

с учетом результатов
,

пок
а
занных
дру
гими

уч
а
стни
ками
.


3. Соревнования по анализу данных
hess 2010 и hess 2011

Система рейтинг
ов

Эло была разраб
о
тана венге
р
ским физиком Арпад
о
м Э
ло в
1950

х

гг.

и адаптирована
В
семирной ша
х
матной федераци
ей

(ФИ
ДЕ) в 1970 г
. На пр
о
тяжении более
сорока

лет система Эло сл
у
ж
и
ла первичным критерием во всем мире для
оценки силы шахматных игроков. Рейтинг
ФИДЕ используется
при

отбор
е

игроков

для
участия в

шахмат
ны
х

турни
р
ах
, вклю
чая
ци
к
л
ы

чемпио
нат
ов

ми
ра

и присуждения т
а
ких тит
у
лов как мастер международного кла
с
са и гроссмейс
тер. Фактически рейтинг Эло
стал настолько популярен, что был
использ
о
ван

во

мног
их других област
ях
, где требуется
сра
в
нительный анализ силы игроков
. Однако,
н
е
смотря на популярность системы Эло, н
и
к
о
гда не было показано, что подход Эло пр
е
восходит другие
подходы по каким

либо те
х
ническим пар
а
метрам.



Два алгоритма на основе техники стохастического градиентного спуска


53
Рис. 2
.

Выбор количества факторов K (по
горизонтальной оси): а и в


тренирово
ч
ная ошибка в случае
исходных

и случайных
м
е
ток
; б


разница

между в и а; г



ошибка

скользящего контроля
, соответствующая
а с оп
тимальным выбором
K
5


Существует несколько альтернатив по
д
х
о
ду Эло.
Например
, п
рофессор Марк Гли
к
ман разработал системы Глико и Глико

2, к
о
торые расширяют систему Эло введен
и
ем д
о
полнительных параметров, которые о
т
ражают
ст
а
бильность

рейтинга игрока. Джеф

Сонас
(организатор обоих соревнований) ра
з
работал
hessetrics

для
оптимизации кач
е
ства пр
о
гноза
. Отметим также работы [9]
,
[10]

и
[11],
в которых представлено несколько
других
подходов
.



Рис. 3.

Выбор регуляризационных и об
у
чающих параметров


Большая ч
асть замечаний к системе Эло
является отражением её

простоты
:

она ид
е
ально подходит в ситуациях, когда вычисл
е
ние рейтинга является важной частью соре
в
нования, даже если список участников сост
о
ит из н
е
скольких сотен игроков. Формула Эло
бы
ла
обоснована

тео
ретически

во врем
ена, к
о
гда отсутс
т
вовали

мощно
ст
и

с
овременных

вычислитель
ных машин.

П
оявление

совр
е
менных компьютеров и боль
ш
их

баз

данных

стимулировало развитие методов и

подхо
д
ов
,
предсказательная сила которых применител
ь
но к шахматам значительно превос
ходит си
с
тему Эло. Такие исследования могут иметь
знач
и
тельное влияние на теорию и практику
методол
о
гии оценивани
я как в шахматах, так
и во все
х

ос
тальн
ых о
б
ластях знаний
.

Основной целью двух соревнований
hess

2010 и
hess

2011 было
выявление
пе
р
спективны
х

методов

для вычисления рейти
н
га

r

шахматных игроков.

Разработанные нами
методы и алгоритмы

показали следующие р
е
зультаты
в ходе

соревновани
й
:

10

й результат
из 252 в 2010
г.
и 4

й

из 181 в 2011

г.

Метод
победителя

в соревновании
hess

2010, осн
о
ванный на

методе стохастического градиен
т
ного спуска, представлен в работе [5]. Пр
о
должительность соревнования в 2010

г
.

сост
а
вила

106 дней
, а в 2011

г
.



86 дней.

Набор данных для
hess

2011 включал
реальные исторические данные, предоста
в
ленные

Международной шахма
тной федер
а
цией

ФИДЕ. Участники
использовали для
тренировки

свои
х

рейтин
говы
х

систем

на
б
о
р
ы

данных из 2327683 результатов игр с
уч
а
стием
85250 шахматных игроков за
11
п
о
следних лет.
Затем

участники использовали
свои методики оценивания для предсказ
а
ния
исх
одов будущих 427361 игр, которые
с
о
сто
я
лись

в следующие три мес
я
ца.


3
.1 Алгоритм вычисления шахматного
рейтинга с помощью стохастического

гр
а
диентного спуска (
R

SG
)

Алгоритм, представленный ниже, имеет
несколько
от
личий
по

сравнени
ю

с соответс
т
вующей ве
рсией из работы [5].
Во

первых
,
рассматр
ивается

биномиальное отклонение
,
а
не квадратичн
ая

ошибк
а
. Во

вторых,
пре
д
ставлены

все детали относительно очень с
у
щественного дополнения о среднем

рейтинге

В.
Н
. Никулин, Т. Г. Прозорова


54
сосед
а

(
см.
формул
у

(11)). К
роме того
, все
константы и пара
метры были вычислены з
а
ново с использованием специальн
ой
оптим
и
зационной
программы

на
языке

.

В соответствии с моделью Бредли



Терри
прогноз

вероятност
и
, что игрок
i

(
б
е
лы
е)

победит игрока
j

(
черны
е)

составляет

)
exp(
1
1
ˆ
1
i
j
ij
r
r
p




,


(8)

г
де гло
бальный параметр
1
0




отражает
меньшие шансы на победу
черных (все пар
а
метры


представлены

в табл
ице
).


Регулирующие параметры для
алг
о
ритма
R

SG

1


0.8848

2


0.7626

3


0.1488

4


90.0000

5


4.0438

6


1.5663

7


2.0317


Целевая функция состоит в

минимиз
а
ци
и

биномиального

отклонения с квадрати
ч
ной регуляр
и
зацией





L
,
(,)
#
ij
ijT
s
T




,


(9)

где

)
ˆ
1
n(
)
1
(
)
ˆ
n(
ij
ij
ij
ij
ij
p
p
p
p
s




, (10)






I
i
i
i
q
r
2
)
(

,





i
i
N
j
ij
N
j
j
ij
i
w
r
w
q
,
(11)

2
in
x
in
1
1














t
t
t
t
w
ij
ij
,

(12)

где
0



и
0





регулирующие
параме
т
ры,
i
N



список соседей или список
тех
игр
о
ков, которые играли с игроком
i
.

Этот список
включает: 1) результат; 2) цвет фигур; 3) м
е
сяц. Отметим, что каждой паре игроков м
о
жет соответствовать несколько игр. Следов
а
тельно, для у
прощения обозначений под
ij
t

(номер месяца) понимается неуникальное зн
а
чение
132
1
x
in




t
t
t
ij
.

Замечание 5.

Заметим, что
действ
и
тельные значения регулирующих параметров
α

и
μ

не являются существенными
(
поскольку
они
обобщаются па
раметрами
β
)
в (9), (10) и
(11), которые определяют структуру формул
(14а) и (14б).

В соответствии с формулами (8) и (10)
верны следующие соотношения:

ij
ij
i
ij
p
p
r
S




ˆ
,


(
13а
)

ij
ij
j
ij
p
p
r
S
ˆ




.


(
13
б)


Рис. 4.

Сходимость алгорит
ма
R

SG

как функции от глобальных итераций
:
а

обучение


монотонно убывает; б те
с
т
и
рование


убывает до точки
K
21
, а
з
а
тем растет


Используя формулы (13а) и (13б), мо
ж
но получить главные формулы для обновл
е
ния значений:
















7
6
3
)
ˆ
(




i
i
i
ij
ij
ij
k
i
i
s
q
r
p
p
w
r
r
,

(14а)

















7
6
3
)
ˆ
(




i
i
i
ij
ij
ij
k
j
j
s
q
r
p
p
w
r
r
,

(14б)

Два алгоритма на основе техники стохастического градиентного спуска


55
где
i
s



количество игр, сыгранных
i

м игр
о
ком за период в 132 месяца,

k



индекс гл
о
бальной итерации,
5
4
4
1















k
k
.

Рис
.

4 иллюстрирует сходимость алг
о
ритма
R

SG
.
Как и
следовало
ожид
ать
,
о
ш
ибка
обучения

(а)
монотонно

убывает.
Ошибка тестирования (б) убывает до знач
е
ния

n
21.

Отметим

сходство между график
а
ми,
приведенн
ы
ми на рис
.

1 и 4б.

Замечание 6.

Центроиды
i
q

являются
важ
ными

эле
ментами

алгоритма
R

SG
,
они долж
ны бы
ть пересчитаны с обновл
ё
н
н
ыми рейтингами после
каждой

глобальн
ой

итер
а
ци
и
.

Замечание 7.

Используя

описанный
выше
алгоритм

R

SG
, можно вычислить
рейти
н
ги шахматных игроков
в
соответствии
с информацией, имеющейся за предыдущие
130, 131 и 132 месяца. Эти ре
йтинги
будут

различны
ми

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

признаками

мы
мо
жем

сформировать

базу данных для
R
,
а з
а
тем использовать такие функции
,

как

GB
M

и
ли

r
n
doForest

для вычисления требуемых
вероятностей
для
резул
ь
татов игр.


Заключительные замечания

и в
ыв
о
ды


Фактичес
ки предложенные алгоритмы
L
F

SG

и
R

SG

представляют гибкие и
простые структуры, которые можно прим
е
нить и тестировать с разными ре
гулирующ
и
ми параметрами. Алгоритмы реализованы на
языке


и
работают
очень быстро. Как сле
д
ствие, можно провести много тестов в целях
оптимизации регулирующих параметров. В
случае
L
F

SG

выяснено, что
использование
двух различных параметров обучения

прив
о
д
ит к улучшению качества факторных разл
о
жений
.

Логично предположить
,

что

начальные
значения
парамет
р
ов обучения

являются

до
с
таточно большими. Затем они
должны быт
ь

уменьш
ены
, что является предметом дал
ь
нейших исследований. Регуляризация пре
д
ставляет
собой
н
еобходимую и очень важную
часть систем на основе
SG
.

Число факторов
не должн
о

быть очень большим, чтобы пр
е
дотвратить переобучение
. С другой стороны,
малое число факторов приводит к потере
важной информации.

В работе представлен
непараметрический критерий

для выбора п
а
раметра
K



число факторов
.
Структура
SG

является

идеальным подходом для обработки
больших списков данных (в случае раз
р
е
же
н
ных ма
т
риц).

Э
ффективность представленного мет
о
да
была подтверждена в ходе
трё
х

ме
ждун
а
ро
д
ных
соревнований по анализу

данных на
платформе
Kgge
.

Дальнейшие улучшения
могут быть достигнуты с применением одн
о
родного

ансамблирования

(при использов
а
нии так называемых паспортов скользящего
контроля)
,
которое
рас
см
о
тр
ено

в работе
[13].


Список литературы


1.


Oj E., Iin A., Lut
tinen J., Yng Z.

Liner
expnsions with noniner cost functions: o
d
e

ing, representtion, nd prtitioning // P
e
nry nd Invited Lectures, WI 2010, Edited
y Jon Arnd nd S
e
sti Xo
.

Brc
e
on, Spin
,

2010
.

P
.
105

123.

2.


Lee ., Seung

H.

Lerni
ng the prts of o

jects
y nonnegtive trix fctoriztion

//

Nture
401
.

1999
.

P
.
788

791.

3.


Nikuin V., McLchn G.J.

ssifiction of
i

nced rketing dt with nced r
n
do sets // JMLR: Workshop nd onfe
r
ence
Procee
d
ings. 2009
.
Vo
.

7.
P.

89

100.

4.


Nikuin V., Hung T.H.

Unsupervised die
n
sionity reduction vi grdient

sed trix
fctoriztion with two erning rtes nd their
utotic updtes // Journ of M

chine
Lerning Reserch, Workshop nd onfe
r
ence
Proceedings. 2012
.

Vo. 27. P
.
18
1

195.

5.


Sisnis Y.

How I won the hess rtings


Eo vs the Rest of the Word opetition

//
rXiv:1012.4571v1. 2010.

6.


Tkcs G., Piszy I., Neeth B., Tikk .

On
the Grvity Recoendtion Syste

//
K
up Workshop t SIGK 2007 Sn Jose, 
i
forni
,

US
A. 2007
.
Vo. 7.
P
.

22

30.

7.


Rende S.

Fctoriztion Mchines with iFM

//

AM Trnsctions on Inteigent Systes
nd Technoogy 3
.
2012
.
P
.

1

22.

В.
Н
. Никулин, Т. Г. Прозорова


56
8.


Gickn M.E.

Preter estition in rge
dynic pired coprison experients

//

App. St

tist. 1999
.
Vo
. 48(3) P
.

377

394.

9.


Furnkrnz J., Huereier E., heng W., Prk
S.H.

Preference

sed reinforceent erning:
 for frework nd  poicy itertion 

gorith

//
Mchine Lerning
.

2012
.
Vo.
89(1).P
.

123

156.

10.

Sun Q., Pfhringer B.

Pirwise et

rues f
or
etter et

erning

sed gorith rn
k
ing

//
Mchine Lerning
.

2013
.
Vo. 93(1) P
.

141

161.

11.

nguthier P., Herrich R., Mink T.,
Gr

epe T.

TrueSki Through Tie: Revisi
t
ing the History of hess

//

NIPS. 2007.

12.

Hung

T.K., Weng R., Lin .J.

Gener
ized
Brdey

Terry Modes nd Mu
ti

ss Pro


iity Estites //

Journ of Mchine Ler
n

ing Reserch
.

2006
.
Vo.

7
.
С
.

85

115.

13.

Nikuin V., Bkhri A., Hung T.H.
: On the
evution of the hoogeneous ensees with
V

pssports

//
PAK 2013, LNS Spr
i
n
ger, J. Li et.. (Eds.). 2013
.

Vo
.

7867.
P
.
181

195
.


Two Agoriths under Stochstic Grdient


e
scent Frework for Recoender Systes


V. N
.
Nikuin, T. G
.
Prozorov

Vytk

Stte University,
Russi,
61
000
0,
Kirov
,
Moscovsky

st.,
36

vnikuin
.
uq
@
g
i
.co


Recoender systes is  sufied of chine erning tht is in creting goriths to pr
e
dict user preferences sed on known user rtings or user ehvior in seecting or purchsing
ites. Such  sy
s
te hs gret iportnce in ppictions t
o sport, rketing nd eduction. In
the ter cse, we re i
n
terested to iprove stte of the rt in student evution y predicting
whether  st
u
dent wi nswer the next question correcty. This prediction wi hep student to get
right orienttion whi
ch erning re shoud to e given greter ttention. Note tht the vie
dt re given in the for of ist, ut not in the trdition for of trix. onsequenty, stndr
d
fctoristion technique is not ppice here. However, stochstic grdien
t ethods work we
with the ists of dt, where the ost of retions re issing, nd ye required to e predicted.

In this pper we sh consider optiistion of the ost iportnt regution p

reters, such s
nuers of fctors, erning nd regu
ristion rtes, nuers of go itertions. Our study is
sed on the Grockit
nd
hess dt, which were used onine during popur dt ining contests
on the ptfor K
g
ge.

Key

words
:

trix fctoriztion
;

coortive fitering
;

recoender syste

;

onine educ

tion
;

chess rtings
;

pirwise couping
;

unsupervised erning
.


Приложенные файлы

  • pdf 7805842
    Размер файла: 815 kB Загрузок: 0

Добавить комментарий