11.05M

Категория: $Математика$ Математика

Похожие презентации:

Математические методы прогноза и восстановления зависимостей

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

Ошибки классификации. Экспериментальная оценка качества алгоритмов классификации (лекция 03)

Статистические методы обработки данных

Метод наименьших квадратов

Применение метода опорных векторов для решения задачи прогнозирования и классификации

Парная линейная регрессия и метод наименьших квадратов

Эконометрика. Обобщенный метод наименьших квадратов

Статистические методы обработки данных

Методы обработки экспериментальных данных

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

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