(note-02) Rademacher 1/57

(note-02) Rademacher 1/57

(x 1, y 1 ),..., (x n, y n ) X Y f : X Y Y = R f Y = {+1, 1}, {1, 2,..., G} f x y 1. (x 1, y 1 ),..., (x n, y n ) f(x i ) ( ) 2. x f(x) Y 2/57

(x, y) f(x) f(x) y (, loss) l(f(x), y) l(f(x), y) = (f(x) y) 2 L 1 f(x) y 0-1 l(f(x), y) = 1[f(x) y] f(x) = y loss = 0 f(x) y loss = 1 1, A, 1[ ] 1[A] = 0, A. 3/57

f : X Y (x 1, y 1 ),..., (x n, y n ) X Y L(f) = 1 n n l(f(x i ), y i ) X Y D L(f) = E[l(f(x), y)], (x, y) D 4/57

2 & 0-1 x R, y {1, 1}, P (x, y) = p(x y)p (y) L(f) 0.4 h(x) = 1 h(x) =1 = P (f(x) = 1, Y = +1) 0.3 + P (f(x) = +1, Y = 1) 0.2 0.1 p(x y = 1) p(x y = 1) = P (f(x) = 1 Y = 1) P (Y = 1) + P (f(x) = 1 Y = 1) P (Y = 1) 0.0-4 -2 0 2 4 = [ ] P (Y = 1) + [ ] P (Y = 1) 5/57

L(f) f D L(f) L(f) f i.i.d. f L(f) p L(f), n, = [ L(f) f ] [ L(f) f ] ( ) L(f) L(f) 6/57

Bayes rule f 0 L(f 0 ) = inf f L(f) inf f : f : X Y f 0 : Bayes error: L(f 0 ) ( ) Bayes rule 7/57

Theorem 1. Bayes rule : Bayes rule (x, y) p(x, y) = p(y x)p(x) f 0 (x) = arg min Bayes error : L(f 0 ) = f 0 f Y p(x) l(f, y)p(y x)dy ( min f Y ) l(f, y)p(y x)dy dx (Steinwart, Christmann, Support Vector Machines, Chap.3 ) 8/57

L(f) = = L(f(x), y)p(y x)p(x)dydx ( ) p(x) min L(f, y)p(y x)dy dx f Y p(x) L(f 0 (x), y)p(y x)dydx = L(f 0 ). 9/57

Y = R l(f, y) = (f y) 2 f 0 (x) = yp(y x)dx. (y f) 2 p(y x)dy = (y f 0 (x)) 2 p(y x)dy + (f 0 (x) f(x)) 2 10/57

l(f, y) = f y f 0 (x) p(y x) y note: y f p(y x)dy f = 0 global min. y f p(y x)dy = f (y f)p(y x)dy + f (f y)p(y x)dy = f yp(y x)dy fp (Y f x) + fp (Y f x) f yp(y x)dy. 11/57

f L(f x) = fp(f x) P (Y f x) fp(f x) + P (y f x) fp(f x) + fp(f x) = P (Y f x) + P (y f x) L(f x) = 0 P (Y f x) = P (y f x) f p(y x) 12/57

2 Y = {+1, 1} p(x, y) = p(y x)p(x) f 0 (x) = +1, p(+1 x) p( 1 x), 1, p( 1 x) > p(+1 x). L(f 0 ) = min{p(x, y)}dx. y 13/57

y=±1 1[f y]p(y x) = 1 p(f x) f = { p(+1 x) p( 1 x) f0 (x) = +1, p(+1 x) < p( 1 x) f 0 (x) = 1 L(f 0 ) = (1 max y=±1 p(y x))p(x)dx = min p(y x)p(x)dx y=±1 2 2 14/57

p(+1 x) x 1.0 0.8 p(y = 1 x) p(y =1 x) p(y x) 0.6 0.4 0.2 0.0-4 -2 0 2 4 6 x h 0 (x) 15/57

Y = {1, 2,..., K} p(x, y) = p(y x)p(x) Remark. L(f 0 ) = f 0 (x) = arg max p(y x) y (1 max y p(y x))p(x)dx p(y x)p(x) [Steinwart, A3.16] cf. Polish space. 16/57

( ) H (Empirical risk minimization, ERM): min f H L(f) f ERM (Regularized ERM) f 0 H 17/57

Example 1. H = {f 1, f 2 }, L(f1 ) = 2 8, L(f2 ) = 3 8 = f = f 1 h 1 h 2 18/57

(Y = R) ϕ : X R d H Lin = {f(x) = w T ϕ(x i ) + b w R d, b R} (2 ) H = {f(x) = sign(g(x)) g H Lin }, sign ( ) Y = {1, 2,..., K}. H = {f(x) = arg max{g 1 (x),..., g K (x)} g 1,..., g K H Lin } 19/57

(x 1, y 1 ),..., (x n, y n ) i.i.d. D f 0 (x) ERM, H f L( f) L(f 0 )?? 20/57

H Bayes rule f 0 f 0 H f := arg min L(f) f H f = arg min L(f) f H f 0 f. 2 (i) L(f 0 ) L( f) L( f), (ii) L( f) L( f) 21/57

L( f) L(f 0 ) L( f) L(f 0 ) = [ L( f) L( f) ] + [ L( f) L(f 0 ) ] ( 0) ( 0) H f 0 22/57

: P ( L( f) L( f) < ε ) 1 δ ε δ ε > 0, δ (0, 1) P ( ) i.i.d. (x 1, y 1 ),..., (x n, y n ) δ ε 23/57

Lemma 1. P ( L( f) L( f) ε ) P ( L( f) L( f) ε/2 ) + P ( L( f) L( f) ε/2 ) Proof. L( f) L( f) = (L( f) L( f)) + ( L( f) L( f)) + ( L( f) L( f)) (L( f) L( f)) + ( L( f) L( f)) L( f) L( f) ε (i) L( f) L( f) ε/2, (ii) L( f) L( f) ε/2. 24/57

Theorem 2 ( ). sup f,y l(f, y) inf f,y l(f, y) M H < 1 δ L( f) < L(f 0 ) + [ L( f) L(f 0 ) ] 2 H + 1 + M log n δ (1) Proof. Hoeffding Z i = l(f(x i ), y i ) E[ L( f)] = L( f) P ( L( f) L( f)) ε/2 ) e nε 2 /2M 2. 25/57

f P ( L( f) L( f) ε/2 ) P ( { ) L(f) L(f) ε/2} f H f H P ( L(f) L(f) ε/2 ) H e nε2 /2M 2. note: l(ĥ(x i), y i ), i = 1,..., n = H 26/57

P P ( ) L( f) L( f) ε ( ) L( f) L( f) ε/2 ( H + 1)e nε2 /2M 2 + P ( ) L( f) L( f) ε/2 δ = ( H + 1)e nε2 /2M 2 (1) Remark. Chebyshev s ineq P (4 H +1)M 2 4 M n H +1 δ. nε 2, 27/57

2, 0-1 loss (M = 1). X = (0, 1] p(y x)p(x), p(x) = 1, x (0, 1] 0, x a, p(+1 x) =, f 0 (x) = 1, x < a 1, x a, +1, x < a. L(f 0 ) = 0. F K f b,l b, l/k x 1, f b,l (x) = b, 0 < x < l/k, b = ±1, l = 1,..., K. 28/57

F K = 2K, f F K, L( f) 1/(2K) a (l/k, (l + 1)/K] f = f 0 f F K F K < 1 δ L( f) < 1 2K + 2 n log 2K + 1 δ 29/57

K = n, δ = 1/n 1 1/n L( f) < 1 2 n + 2 log n n log 3n3/2 4, (n 3). n 30/57

b H := min f H L(f) L(f 0) v H (n, δ) := M 2 n H + 1 log δ (1) n 1 δ L( f) < L(f 0 ) + b H + v H (n, δ). 31/57

H 1, H 2,..., H K H 1 H 2 H K b H1 b H2 b HK n δ v H1 (n, δ) v H2 (n, δ) v HK (n, δ) 32/57

L( f) L(f 0 ) + b H + v H (n, δ) min k=1,...,k b H k + v Hk (n, δ) H k prediction error 0.0 0.5 1.0 1.5 2.0 bias+varialce bias variance 1e+01 1e+03 1e+05 H 33/57

Rademacher H = 34/57

Definition 1 (( ) Rademacher ). H {f f : Z R} S = {z 1,..., z n } Z Rademacher : RS (H) = E σ [sup f H σ 1,..., σ n i.i.d. Ber(1/2), i.e., P (σ i = +1) = P (σ i = 1) = 1/2 1 n ] n σ i f(z i ), E σ [ ] σ 1,..., σ n Rademacher R n (H) = E S [ R S (H)], (z 1,..., z n i.i.d. P ). R n (H) 35/57

Rademacher σ 1,..., σ n {+1, 1} G 36/57

R n (H) Rademacher 1. H 1 H 2 = R S (H 1 ) R S (H 2 ) 2. c R R S (c H) = c R S (H) c H = {cg : g H} 3. ϕ : R R L R S (ϕ H) L R S (H). ϕ H = {z ϕ(g(z)) : g H} 37/57

Proof. 1. 2. c = 0 c 0 R S (ch) = E σ [ sup g H = c E σ [ 1 n sup g H n 1 n ] [ σ i cg(z i ) = c E σ n ] σ i g(z i ) sup g H 1 n n ] σ i sign(c)g(z i ) σ i σ i sign(c) 1/2 ±1 3 Foundations of Machine Learning, Lemma 4.2. 38/57

Rademacher Theorem 3 ( ). H {f : Z [a, b]} Z Z, Z 1,..., Z n i.i.d. P. 1 δ sup f H E[f(Z)] 1 n n f(z i ) log(2/δ) 2R n(h) + (b a). 2n Hoeffding s McDiarmid 39/57

{ Proof. A(z 1,..., z n ) = sup E[g(Z)] 1 g H n n } g(z i ) A(z 1,..., z n ) A(z 1,..., z n 1, z ) { = sup inf E[g(Z)] 1 n g(z i ) E[f(Z)] + 1 g H f H n n sup g H = sup g H { E[g(Z)] 1 n g(z ) g(z n ) n n g(z i ) E[g(Z)] + 1 n b a n. n 1 n 1 f(z i ) + 1 } n f(z ) g(z i ) + 1 } n g(z ) A(z 1,..., z n 1, z ) A(z 1,..., z n 1, z n ) (b a)/n 40/57

A(z 1,..., z n 1, z ) A(z 1,..., z n 1, z n ) b a n McDiarmid s inequality { P A(Z 1,..., Z n ) E[A] (b a) } log(1/δ) 2n 1 δ. (2) E[A] Z Z 1,..., Z n, Z 1,..., Z n 41/57

A(Z 1,..., Z n ) = sup g H { E Z 1,...,Z n Z i Z i E Z 1,...,Z n [ sup g H [ 1 n 1 n ] } n g(z i) 1 n g(z i ) n ] n (g(z i) g(z i )). = g(z i ) g(z i) g(z i ) g(z i ) σ 1,..., σ n i.i.d. Ber(1/2) σ i (g(z i ) g(z i)) g(z i ) g(z i) 42/57

E Z1,...,Z n [A(Z 1,..., Z n )] [ ] 1 n E Z,Z,σ σ i (g(z n i) g(z i )) E [ sup g H = 2R n (H) 1 n sup g H ] [ n σ i g(z i) + E sup g H 1 n ] n ( σ i )g(z i ) (2) O.K. 43/57

Example 2 ( ). H < f H f B (f(z 1 ),..., f(z n )) 2 B n Massart s ineq. R S (H) = E σ [max f H 1 n ] n σ i f(z i ) B n 2 log H n = B 2 log H n R n (H) 44/57

Example 3 ( (decision stump)). 1 (R d 2 ) x = (x 1,..., x d ) f(x; s, k, z) = s sign(x k z) {+1, 1}, : s = ±1, k {1,..., d}, z R. : H = { f(x; s, k, z) s = ±1, k = 1,..., d, z R }. 45/57

H A = {(f(x 1 ),..., f(x n )) f H} A n A 2nd Massart s ineq. R S (H) = 1 n E σ [ sup s,k,z n ] σ i f(x i ; s, k, z) 2 log(2nd) n 46/57

(R d 2 ) l H l ( H 2 ) A l := {(f(x 1 ),..., f(x n )) {±1} n f H l }, l 1 A l (2n k d) A l 1 = 2nd A l 1 (n k : k ) k=1 = A l (2nd) l 1. R n (H l ) 2(l 1) log(2nd) n 47/57

0-1 Rademacher G = {1[f(x) y] f H}, f : X {+1, 1}. For S = {(x 1, y 1 ),..., (x n, y n )}, R S (G) = E σ [sup = 1 2 E σ f H [ 1 n sup f H n 1 n ] 1 y i f(x i ) σ i 2 ] n ( y i σ i )f(x i ) = 1 2 R S (H) 48/57

H 2 0-1 ERM f 0 H 2, L(f 0 ) = 0 L( f) = 0 1 δ L( f) 2 log(2nd) n + log(2/δ) 2n 49/57

2 Rademacher y = f 0 (x) + ε, H {f : X [ B, B]}. l(f(x), y) = 1 (y f(x))2 2 (x, y) X [ M, M] (B + M)2 0 l(f(x), y). 2 l(f, y) f = f y B + M, = l(f 1 (x), y) l(f 2 (x), y) (B + M) f 1 (x) f 2 (x). 50/57

G = {(x, y) l(f(x), y) : f H} R n (G) (B + M)R n (H) 1 δ L( f) L( f) 2(B + M)R n (H) + (B + M)2 log(2/δ) 2 2n 51/57

RKHS Rademacher k RKHS H H B = {f H f B} sup k(x, x) a 2 x X f H B f ab, R m (H B ) ab m 52/57

Proof. f = sup x f, k(x, ) f sup x k(x, x) ab. R S (H B ) = E σ [ sup f B 1 m m ] σ i f(x i ) = B [ m E m σ σ i k(x i, ) ] B m = 1 m E σ = B ( [ ] ) 1/2 k(x i, x j )E σ σi σ j m = B m i,j ( m ) 1/2 k(x i, x i ) ab. m [ sup f B ( E σ [ m m f, σ i k(x i, ) ] σ i k(x i, ) 2 ] ) 1/2 53/57

(x 1, y 1 ),..., (x m, y m ) X [ M, M] RKHS H 2 l(f(x), y) = 1 2 (f(x) y)2 min f H 1 2m m (y i f(x i )) 2 + λ 2 f 2 f 54/57

λ 2 f 2 1 2m m = f M/ λ (y i f(x i )) 2 + λ 2 f 2 1 2m m y 2 i M 2 2 H M/ λ 2 B am/ λ, R m (H M/ λ ) am mλ 55/57

L( f) L( f) sup f H M/ λ L(f) L(f) ( 2 am/ ) am λ + M mλ + ( ) 1 O λ m (λ = o(1) ) ( am/ λ + M 2 ) 2 log(1/δ) 2m 56/57

f 0 H, λ = λ m λ m 0, λ m m = L( f) L(f0 ) (in prob.) Proof. λ m 0 m f 0 H M/ λm 0 L( f) L(f 0 ) L( f) L( f) + L( f) + λ m 2 f 2 L(f 0 ) λ m 2 f 0 2 0 + L(f 0 ) L(f 0 ) + λ m 2 f 0 2 2 sup f H M/ λ m L( f) L( f) + λ m 2 f 0 2 = O ( ) 1 + λ m λ m m λ m = O(m 1/4 ) 57/57