ERATO PDF Free Download

ERATO September 13, 2010, DC2 1/25

1. 2 2. 2/25

3/25

2 3/25

1 1 0.5 0.5 0 0 0.5 1 0 0 0.5 1 4/25

1 1 0.5 0.5 0 0 0.5 1 (0, 0) 0 0 0.5 1 4/25

1 1 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 0 0 0.5 1 4/25

1 (1, 1) 1 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 0 0 0.5 1 4/25

1 (1, 1) (1, 1) 1 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 0 0 0.5 1 4/25

1 (1, 1) (1, 1) 1 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 4/10 + 4/10 = 0.8 0 0 0.5 1 4/25

1 (1, 1) (1, 1) 1 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 4/10 + 4/10 = 0.8 0 0 0.5 1 (00, 01) (01, 00) ( 10, 01) 4/25

1 (1, 1) (1, 1) (01, 10) 1 (1, 1) (1 1, 01) 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 4/10 + 4/10 = 0.8 0 0 0.5 1 (00, 01) (01, 00) ( 10, 01) 4/25

1 (1, 1) (1, 1) (01, 10) 1 (1, 1) (1 1, 01) 0.5 0.5 0 0 0.5 1 (0, 0) ( 1, 0) 4/10 + 4/10 = 0.8 0 0 0.5 1 (00, 01) (01, 00) ( 10, 01) 12/10 + 10/10 = 2.2 4/25

t [Johnson, 99] p 2 1 FPAI 5/25

6/25

7/25

A B 1 2 3 4 8/25

A B 1 2 3 4 1.239582... 0.6469... 0.426711... 0.2655... 1.111577... 0.4998... 1.801501... 0.7569... 8/25

A B A B 1 2 3 4 1.239582... 0.6469... 0.426711... 0.2655... 1.111577... 0.4998... 1.801501... 0.7569... 1.2 0.6 0.4 0.2 1.1 0.4 1.8 0.7 8/25

9/25

2 2 10 2 y = 3x 10/25

0, 1, 1 1000 1 [Tsuiki, 2002] 2 1 1 2 0.25 00111 01000 0 1000 11/25

5 3 2 Position 1 0 0 γ(1/4) 1/2 = 0 1000... γ((5/8, 7/8)) = (1 1 ω ) 1 12/25

(01 1 ω ) (1 1 ω ) 000 00 1 0 10 01 1 100 11 1 1 10 10 1 001 011 010 110 111 101 100 00 0 1 01 10 11 1 1 10 0 1 1 13/25

14/25

X Y I = [0, 1] [0, 1] R d X, Y γ(x), γ(y) R d γ γ(x) γ(y) 15/25

C(X, Y) { if X Y, D(X; Y) + D(Y; X) otherwise, D D(X; Y) 1 X X X R (P, Q) R P R Q = min { O O (γ(x), γ(y)) } 16/25

function MAIN(γ(X), γ(y)) LEARNING(γ(X), γ(y), 0, 0, X, Y, 0) function LEARNING(P, Q, D 1, D 2, m, n, k) V DISCRETIZE(P, k), W DISCRETIZE(Q, k) V sep {v V v W}, W sep {w W w V} D 1 D 1 + min V V v V v (V = {V V sep f P (V ) = f P (V sep )}) D 2 D 2 + min W W w W w (W = {W W sep f P (W ) = f P (W sep )}) output D 1 /m + D 2 /n P {p P p f P (V sep )}, Q {q Q q f Q (W sep )} if P = and Q = then halt else return LEARNING(P, Q, D 1, D 2, m, n, k + 1) function DISCRETIZE(P, k) return {w w = n, p (w ω ), p P} (n = (k + 1)d 1) f P (V) = {p P v V. p (v ω )}, P Σ ω,d, V Σ 17/25

: X : Y Level-1 0 1 D(X; Y) { 10, 11} D(Y; X) {0 1, 101} C(X, Y) = 18/25

: X : Y Level-2 1 0 1 Level-1 0 1 D(X; Y) { 10, 11} D(Y; X) {0 1, 101} C(X, Y) = 18/25

: X : Y Level-3 Level-2 0 1 10 1 1 00 01 10 11 1 0 1 Level-1 0 1 D(X; Y) { 10, 11} D(Y; X) {0 1, 101} C(X, Y) = 18/25

: X : Y Level-4 Level-3 Level-2 101 0 1 10 1 1 00 01 10 11 1 0 1 Level-1 0 1 D(X; Y) { 10, 11} D(Y; X) {0 1, 101} C(X, Y) = 4/5 + 5/5 = 1.8 18/25

19/25

X Y A B Z A B Z { A B if C(X, Z) > C(Y, Z), otherwise. 20/25

21/25

R 2.10.1 UCI abalon, sonar,... 10,000 sensitivity specificity accuracy n 2 X, T + Y, T X, Y T +, T min-max normalization T + T t pos t neg (t pos + t neg )/20000 accuracy 22/25

n = 10 0.52 abalon 0.65 sonar Accuracy 0.46 0.55 0.4 0.45 1 3 5 7 1 3 5 7 Number of attributes Number of attributes Gray-coding div. Binary-coding div. SVM (RBF) SVM (Polynomial) 1-nearest neighbor 5-nearest neighbor 23/25

n = 10 1.0 ecoli 1.0 glass Accuracy 0.75 0.85 0.6 0.7 1 3 5 7 1 3 5 7 Number of attributes Number of attributes Gray-coding div. Binary-coding div. SVM (RBF) SVM (Polynomial) 1-nearest neighbor 5-nearest neighbor 23/25

n = 10 1.0 segmentation 0.9 ionosphere Accuracy 0.9 0.7 0.8 0.55 1 3 5 7 1 3 5 7 Number of attributes Number of attributes Gray-coding div. Binary-coding div. SVM (RBF) SVM (Polynomial) 1-nearest neighbor 5-nearest neighbor 23/25

n = 10 0.5 madelon 0.7 magic Accuracy 0.6 0.44 0.5 0.38 1 3 5 7 1 3 5 7 Number of attributes Number of attributes Gray-coding div. Binary-coding div. SVM (RBF) SVM (Polynomial) 1-nearest neighbor 5-nearest neighbor 23/25

n = 10 0.55 yeast Accuracy 0.5 0.45 0.4 1 3 5 7 Number of attributes Gray-coding div. Binary-coding div. SVM (RBF) SVM (Polynomial) 1-nearest neighbor 5-nearest neighbor 23/25

24/25

Computable Analysis Computational Learning Theory 25/25

ERATO100913