11.05M

Category: $mathematics$ mathematics

Методы классификации и регрессии

1)
:
https://docs.google.com/spreadsheets/d/1I595ZXYJJRRbGFpuLN0XGn7DzljadTXXvbFIiRfpW8/edit?usp=sharing
:
https://docs.google.com/spreadsheets/d/1df7pT164xMzcvrCfX3iC7kVFRaz1J3i
qzD2OK468Nrs/edit#gid=2109442725
1)
1)
:
:
https://docs.google.com/document/d/1LeOOz9jsPRm2fuYQEtjc_8gxIxOrCoEcDSlvlPqZYY/edit?usp=sharing
3

4.

Jonathan T. Barron (2019). A General and Adaptive Robust Loss Function. // https://arxiv.org/pdf/1701.03077.pdf.
Jaderberg, M. et. al (2016). Decoupled Neural Interfaces using Synthetic Gradients. // Arxiv.org
Diederik P. Kingma and Jimmy Ba (2014). Adam: A Method for Stochastic Optimization. // https://arxiv.org/abs/1412.6980.
Davis J., Goadrich M. (2006). The Relationship Between Precision-Recall and ROC Curves. // Proceedings of the 23rd
International Conference on Machine Learning, Pittsburgh, PA.
Mohri, M., Rostamizadeh, A., Talwalkar, A. Foundations of Machine Learning. // MIT Press, 2012
.
.
.
.
//
http://www.
recognition.mccme.ru/pub/RecognitionLab.html/slbook.pdf
Tai, Farbound and Lin, Hsuan-Tien. Multilabel Classification with Principal Label Space Transformation. // Neural
Comput., 24-9, 2012.
. .
. //
.
. .
. 2014.
Hastie T., Tibshirani R., Friedman J. (2009). The Elements of Statistical Learning.
Hastie, T., Tibshirani, R., Friedman, J. (2001). The Elements of Statistical Learning. // Springer, New York.
Domingos, Pedro (2000). A Unified Bias-Variance Decomposition and its Applications. // In Proc. 17th International Conf.
on Machine Learning.
Breiman, Leo (2001). Random Forests. // Machine Learning, 45(1), 5 32.
Friedman, Jerome H. (2001). Greedy Function Approximation: A Gradient Boosting Machine. // Annals of Statistics, 29(5),
p. 1189 1232.
Gulin,
A.,
Karpovich,
P.
(2009).
Greedy
function
optimization
in
learning
to
rank.
http://romip.ru/russir2009/slides/yandex/lecture.pdf
Tianqi Chen, Carlos Guestrin (2016). XGBoost: A Scalable Tree Boosting System. // http://arxiv.org/abs/1603.02754
4

5.

I.
II.
III.
IV.
V.
VI.
VII.
5

6.

.
:
,
.
.
:
,
.
.
6

7.

x,
.
X.
,
. .
Y.
: Y = R.
y.
7

8.

.
X = {(x1, y1), . . . , (x , y )},
,
x1, . . . , x
.
,
y1, . . . , y .
8

9.

.
x
-
.
:
(set-valued,
.
9

10.

:
1. Y = {0, 1}
.
.
2. Y = {1, . . . , K}
(multi-class)
.
3. Y = {0, 1}K
classification).
4.
. .).
(multi-label
.
(semi-supervised learning)
.
.
10

11.

:
1.
.
.
2.
.
.
11

12.

:
3.
.
4.
.
.
.
12

13.

-
X ∈ R ×d (
a:X
Y,
,
d
.
.
.
.
.
.
(mean
squared error, MSE):
L(y, z) = (y-z)2).
L : Y×Y
R+
.
13

14.

A,
.
a(x).
,
w0):
xi
i-
x.
14

15.

MSE:
xij
a(x)
.
j-
i-
.
w,
.
;
.
15

16.

.
:
.
.
-
-
.
-
.
.
,
.
,
.
16

17.

(overfitting)
:
: A = {a : X
Y}.
:
.
контроля сложности семейства алгоритмов
.
17

18.

:
1.
;
2.
;
3.
;
4.
;
5.
6.
;
;
7.
18

19.

20.

:
(bias).
wj .
w
:
w = (w1, . . . , wd)
.
(d+1)-
:
.
w0
20

21.

22.

-
.
1.
.
.
m
fj(x)
b1(x), . . . , bm(x),
:
one-hot
.
C = {c1, . . . , cm}.
.
22

23.

b1(x), . . . , bm(x)
f(x)),
:
:
c1
w1),
one-hot
.
23

24.

2.
(bag of words).
bj(x)
m
b1(x), . . . , bm(x),
cj
cj
: {c1, . . . , cm}.
.
:
wj .
24

25.

3.
xj
{t1, . . . , tm}.
t0 = -
tm+1 = + .
.
.
25

26.

27.

.
1.
MSE
y
,
L(y, a)
a
.
.
R2
:
MSE):
(mean squared error,
27

28.

.
(root mean squared error,
RMSE):
.
R2):
y¯ = 1 P i=1 yi
.
.
28

29.

2. MAE
:
(mean absolute error,
MAE):
.
.
29

30.

a2(x)
a1(x)
MAE
MSE.
30

31.

y1, . . . , y
MSE
:
.
31

32.

MAE:
:
.
32

33.

:
.
.
33

34.

3. Huber loss
.
δ
:
,
.
(a - y)
δ,
,
.
δ
δ
0
.
.
,
34

35.

4. Log-Cosh
:
.
log-cosh:
.
-Cosh
35

36.

5. MSLE
:
(mean
squared logarithmic error, MSLE).
.
.
,
36

37.

6. MAPE
SMAPE
:
1.
2.
:
-
-
.
.
:
absolute percentage error, MAPE).
(mean
37

38.

MAPE
.
:
y = 1
(a < y)
,
,
(a > y)
(symmetric mean absolute percentage error, SMAPE)
37 38

39.

7.
:
-
,
.
.
:
[0, 1]
τ
.
τ,
.
39

40.

p(y | x)
x∈X
.
:
может возникать в задаче предсказания кликов по рекламным баннерам: один и тот же
пользователь может много раз заходить на один и тот же сайт и видеть данный баннер. При этом
некоторые посещения закончатся кликом, а некоторые — нет.
1)
2)
: a(x)
: a(x)
median[p(y | x)].
a(x)
E[y | x];
,
40

41.

1.
2.
x
q,
1.
p(y | x).
:
:
1.
:
q
τ-
τρτ(z)
p(y | x).
.
a(x)
41

42.

43.

.
.
:
Существует некоторая одномерная выборка, значения единственного признака x в которой
генерируются равномерно на отрезке [0, 1], а значения целевой переменной выбираются по
формуле y = cos(1.5πx) + N (0, 0.01),
где N (µ, σ2) — нормальное распределение со средним µ и дисперсией σ2.
Возможно восстановить зависимость с помощью линейных моделей над тремя наборами
признаков: {x}, {x, x2, x3, x4} и {x, x2, . . . , x15}.
43

44.

.
.
44

45.

46.

.
1)
2)
!!!
-
-
.
;
:
.
. .
.
.
46

47.

:
.
:
1)
2)
3)
k
i;
k
a1(x), . . . , ak(x),
X1, . . . , Xk
i-
;
:
47

48.

Как получить финальную модель для дальнейшего использования?
1.
;
1.
a1(x), . . . , ak(x),
-
.
.
48

49.

50.

.
:
X
-
L2-
y
.
.
w
,
:
w,
50

51.

:
1)
;
1)
XT X
.
:
.
MSE
.
.
.
51

52.

51 52

53.

.
f : Rd
R
:
:
Известно, что градиент является направлением наискорейшего роста функции, а антиградиент
(т.е. -∇f) — направлением наискорейшего убывания.
,
.
53

54.

v ∈ Rd
x0 ∈ Rd
:
: ||v|| = 1.
.
x0
v
:
54

55.

:
:
v.
ϕ
,
,
180
,
.
.
55

56.

:
У градиента есть ещё одно свойство - он ортогонален линиям уровня.
x0
S(x0) = {x ∈ Rd | f(x) = f(x0)}
1.
.
x0:
x0 + ε ∈ S(x0).
f(x0 + ε) = f(x0)
-
:
||ε||:
1.
||ε||
1.
x 0.
.
ε/||ε||
.
56

57.

:
Основное свойство антиградиента — он указывает в сторону наискорейшего убывания функции в
данной точке.
w(0)
:
Q(w)
ηk
w.
.
: ηk = c.
:
57

58.

1)
2)
(||∇Q(w(k-1)|| < ε);
:
(||w(k) - w(k-1)|| < ε).
:
следить за ошибкой модели на отложенной выборке и останавливаться, если эта ошибка
перестала убывать.
-
:
если функция выпуклая и дифференцируемая, для её первой производной выполнено
условие Липшица, длина шага выбрана правильно, то градиентный спуск сойдётся к
минимуму функции;
также имеет место следующая оценка сходимости для градиентного спуска:
.
58

59.

Q(w)
:
:
.
.
59

60.

1.
:
ik
.
(stochastic gradient descent,
SGD).
.
,
:
.
60

61.

SGD
.
SGD
.
1),
-
:
:
61

62.

.
,
n
ikj
:
(j
1
n),
.
.
mini-batch gradient descent,
62

63.

2.
SAG
(stochastic average gradient)
.
1)
1)
w 0,
zi0,
k-
:
:
ik
63

64.

3)
:
4)
:
:
64

65.

SAG
.
.
:
i-
.
qi (〈w, xi〉)
65

66.

3.
-
-
-
u
:
∇wqi(w)
.
66

67.

68.

v,
w +αv
w
x
〈v, x〉 = 0.
.
точно такие же ответы
68

69.

,
:
.
αw0 L2
L1-
:
69

70.

L2-
.
:
.
:
L2
XTX
.
70

71.

72.

.
-
-
.
.
:
введение регуляризации мешает модели подгоняться под обучающие данные, и с точки
зрения среднеквадратичной ошибки выгодно всегда брать α = 0.
выборку, на которой настраиваются гиперпараметры, называют валидационной, и при этом
выделяют третий, тестовый набор данных, на которых оценивается качество итоговой
модели.
72

73.

74.

:
Модели, в которых некоторые веса равны нулю, называют разреженными, поскольку прогноз в них
зависит лишь от части признаков.
Пример:
1. Может быть заведомо известно, что релевантными являются не все признаки. Очевидно, что
признаки, которые не имеют отношения к задаче, надо исключать из данных, то есть
производить отбор признаков (L1-регуляризация);
1.
К модели могут выдвигаться ограничения по скорости построения предсказаний (L1регуляризация);
1.
В обучающей выборке объектов может быть существенно меньше, чем признаков (так
называемая «проблема N ≪ p») (L1-регуляризация).
74

75.

1.
Q(w) + α||w||1
Q(w)
C:
Q(w) -
||w||1
-
-
75

76.

2.
w = (1, ε),
.
L1-
ε
δ < ε:
L2-
:
2-
76

77.

3.
.
L1-
F(w) = ||Xw - y||2
:
η
,α
Sηα(w)
77

78.

79.

1.
:
:
:
-
log xj
-
exp(||x -
-
sin(xj/T )
2/σ)
79

80.

2.
-
.
1
f1(x) = ½*x21+ ½*x22
x(0) = (1, 1)
1)
2)
3)
η=1
:
2
1)
:
f2(x) = 50x21 + ½*x22
x(0) = (1, 1)
1)
:
(-100, -1)
.
80

81.

1)
1)
:
[0, 1]:
81

82.

83.

X = Rd
Y = {-1, +1}
X = {(xi, yi)} i=1
.
:
w ∈ Rd
w0 ∈ R
(bias)
xd+1 = 1.
w 0,
〈 w, x〉-
83

84.

1.
(accuracy):
:
-
⇒
84

85.

1.
.
Mi = yi 〈w, xi 〉,
:
〈w,
;
xi
(margin)
〉
85

86.

1.
.
L(M) = [M < 0],
x
M = y〈w, xi 〉.
1)
1)
.
.
86

87.

1.
.
1)
2)
= log (1 + e-M )
= (1 - M)+ = max(0, 1 - M)
1)
= (-M)+ = max(0, -M)
1)
2)
= e-M
= 2/(1 + eM)
-
.
87

88.

89.

.
a(x) = sign(b(x)-t) = 2[b(x) > t] - 1.
b(x) = 〈w, x 〉
t = 0.
1.
Пример: если в выборке 950 отрицательных и 50 положительных объектов, то при тривиальном
пороге t = maxi b(xi) мы получим долю правильных ответов 0.95.
Это означает, что доля положительных ответов сама по себе не несет никакой информации о
качестве работы алгоритма a(x), и вместе с ней следует анализировать соотношение классов в
выборке.
Важно: также полезно вместе с долей правильных ответов вычислять базовую долю — долю
правильных ответов алгоритма, всегда выдающего наиболее мощный класс.
89

90.

.
1.
a1
r1.
-
a2
a2
20%
50%
90%.
10%,
25%,
0.1%
.
0.01%,
r1
r2
:
r2 >
50%.
50%,
90

91.

.
2.
-
91

92.

.
2.
:
y=1
y = -1
.
.⇒
a(x) = sign(b(x) - t) = 2[b(x) > t] - 1.
a(x)
1.
t
:
92

93.

.
2.
F-
precision ≪ 1,
:
1/2,
.
recall = 1
93

94.

.
2.
F-
-
94

95.

.
2.
R-
(breakeven point).
:
t,
R.
95

96.

.
2.
b(x),
b(x).
t,
precision, AP):
y(k)
(average
k-
+
precision@k
k
.
96

97.

.
2.
:
1% ( + = 10.000).
10.000
9.000
1000.
( = 1.000.000),
TP = 9000, FN = 1000.
.
90%
90%,
FP =
(1 - 2.000/1.000.000) = 99.8%!
97

98.

.
2.
Lift -
:
.
98

99.

.
3.
Area Under Curve
.
{a(x) = sign(b(x) - t)
| t ∈ R}.
ROC-
Under ROC Curve, AUC-ROC):
FPR
TPR
b(x),
(Area
(False Positive Rate),
(True Positive Rate).
99

100.

.
3.
Area Under Curve
-
TPR = 0, FPR = 0.
ROC-
+ 1.
tmax = maxi b(xi)
tmin = mini b(xi) - ε
TPR = 1
(0, 0)
FPR = 1.
(1, 1),
b(x(1))- ε, b(x(1)), b(x(2)), . . . , b(x( )).
-
- AUC-ROC,
t
AUC-ROC
b(x)
0
1.
AUC-ROC
0.5.
a(x)
;
,
100

101.

.
3.
Area Under Curve
(Gini index) -
.
AUC-ROC
Gini = 2AUC - 1.
-
ROC:
(0, 0)
(1, 1).
AUC
101

102.

.
3.
Area Under Curve
.
1)
:
.
1.000.100
a(x),
1)
0.95
FPR = 0.05,
100
.
.
TPR
95
.
FPR
50.000
TPR =
:
если положительный класс существенно меньше по размеру, то AUC-ROC может давать
неадекватную оценку качества работы алгоритма, поскольку измеряет долю неверно принятых
объектов относительно общего числа отрицательных.
102