커널 방법론

Size: px

Start display at page:

Download "커널 방법론"

승언 좌
5 years ago
Views:

1 커널방법론 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 커널방법론 1 / 31

2 학습내용 벌점화방법 재생커널힐버트공간 여러가지커널기계 박창이 ( 서울시립대학교통계학과 ) 커널방법론 2 / 31

3 커널방법론 회귀함수나베이즈분류함수가선형이라는가정은비현실적임최종모형의해석상의편리성또는과대적합문제를피하기위해선형모형을고려비선형모형의구축시적절한기저함수 (basis function) 을이용한일반화가법모형또는커널트릭을사용커널트릭 : 특성변환 (feature map) 라불리는비선형변환을통하여본래의입력공간에서새로운 ( 많은경우고차원 ) 특성공간 (feature space) 으로매핑시킨후에특성공간상에서선형방법을적용기계학습에서는커널트릭에기반한학습법을통칭하여커널기계 (kernel machine) 라고부름 박창이 ( 서울시립대학교통계학과 ) 커널방법론 3 / 31

4 커널 트릭 선형모형 f (x) = x T β의 비선형모형으로 확장 입력변수 x Rp 를 적절한 비선형 변환인 특성변환 Φ를 통하여 새로운 입력변수 Φ(x) 생성 f (x) = Φ(x)T β 고려 (예) 2차 다항회귀모형에서의 특성함수 Φ(x) = (1, x1,..., xp, x12,..., xp2, x1 x2,..., xp 1 xp ) 일반적으로 Φ는 매우 복잡하고 고차원의 변환이기 때문에 Φ의 선택은 어려움 아이디어: 특성공간에서 내적이 정의되어진 경우 회귀함수의 추정량은 Φ의 내적으로 주어지므로 Φ를 선택하는 대신 Φ의 내적을 선택 박창이 (서울시립대학교 통계학과) 커널 방법론 4 / 31

5 벌점화의필요성 I 입출력변수간의의존관계를결정하는모형의복잡도를어떻게조절할것인가? 모수적추론 (parametric inference) 특정함수형태를가지는모형을가정하고자료로부터모형에나타나는모수에대한추론함. 실제의존관계가단순한모수적형태로표현또는근사가능한경우에만의미를가짐고차원또는대용량자료에직접적용하기에는다중공선성등의현실적어려움이있음 박창이 ( 서울시립대학교통계학과 ) 커널방법론 5 / 31

6 벌점화의필요성 II 대안여러가지복잡도를가지는모형들로구성된모형집합에서훈련자료로부터최적의복잡도를갖는모형을선택하고이를이용하여추론특정함수형태를가정하지않는함수추정 (function estimation) 방법론을적용 p n 또는모수가무한차원의함수형태인모형의경우에는유한개의훈련자료로적합하는것은여러문제를유발 벌점화방법론 (method of penalization or regularization) 을고려 박창이 ( 서울시립대학교통계학과 ) 커널방법론 6 / 31

7 벌점화방법 : 통계적학습 훈련자료 {(x i, y i )} n i=1 로부터입력값 x X Rp 와출력값 y Y 의 함수적관계 f 를찾는다차원공간상의함수추정문제 손실함수 L(y, f (x)) 를이용하여예측력을평가 박창이 ( 서울시립대학교통계학과 ) 커널방법론 7 / 31

8 벌점화방법 : 경험위험최소화의문제점 평활스플라인 (smoothing spline) 에대한경험위험최소화 L(y, f (x)) = (y f (x)) 2 에대하여 1 n n i=1 L(f (x i), y i ) 을최소화하는 f 를찾음유한개의자료로무한차원의함수를추정하므로자료를과대적합하는해가무수히많음 박창이 ( 서울시립대학교통계학과 ) 커널방법론 8 / 31

9 벌점화방법 : Tikhnov 벌점화 I 함수추정문제의해가수학적으로잘정의되도록 ( 즉, 해가존재하고, 유일하고, 또한자료에연속적으로의존하도록 ) 하는방법 벌점항 J(f ) 가추가된벌점화된목적함수 를최적화 1 n n L(f (x i ), y i ) + λj(f ) (1) i=1 λ > 0: 훈련오차와모형의복잡도간의비중을조절 박창이 ( 서울시립대학교통계학과 ) 커널방법론 9 / 31

10 벌점화방법 : Tikhnov 벌점화 II 평활스플라인 : J(f ) = f (t) 2 dt <, 차수가 2인 Sobolev 공간 λ = 0: interpolation λ = : 선형회귀손실함수 L과벌점항 J(f ) 에따라회귀에서분류에이르기까지다양한형태의자료에적용이가능한일반적인방법론 박창이 ( 서울시립대학교통계학과 ) 커널방법론 10 / 31

11 벌점화방법 : 베이지안과의관계 I i(= 1,..., n) 에대하여 (x i, y i ) f 가서로독립적으로분산이 σ 2 인 정규분포를따른다고가정하면 ( D = {(x i, y i ) } n i=1 베이즈정리에의해 P(D f ) exp P(f D) exp ( 1 2σ 2 1 2σ 2 ) n (y i f (x i )) 2, i=1 ) n (y i f (x i )) 2 J(f ) i=1 박창이 ( 서울시립대학교통계학과 ) 커널방법론 11 / 31

12 벌점화방법 : 베이지안과의관계 II MAP(maximum a posteriori) 추정치 을최소화 1 n n i=1 Tikhonov 벌점화에서 λ = 2σ2 n (y i f (x i )) 2 + 2σ2 n J(f ) > 0인경우의해와동치 박창이 ( 서울시립대학교통계학과 ) 커널방법론 12 / 31

13 양정치커널 I Φ: 입력공간을도트곱공간 (dot product space) 인특성공간로매핑하는특성함수커널 (kernel) K : X X R x, x X, K(x, x ) = Φ(x), Φ(x ) ( 예 ) 차수 d = 2인다항커널 (polynomial kernel) x, x X R 2 에대하여 Φ(x) = (x1 2, x2 2, 2x 1 x 2, 2x 1, 2x 2, 1) T 이면 K(x, x ) = (x 1 x 1 + x 2 x 2 + 1) 2 = Φ(x), Φ(x ) 박창이 ( 서울시립대학교통계학과 ) 커널방법론 13 / 31

14 양정치커널 II 커널트릭 : 내적에만의존하는학습방법에서 x, x 을 K(x, x ) 으로대치하면 Φ에의한특성공간상에서학습을하게됨. 학습을위해서는변환 Φ의구체적형태는알필요는없음 K = (K(x i, x j )): K의 x 1,..., x n 에대한그램행렬 (Gram matrix) 또는커널행렬 (kernel matrix) 모든 n과 x i X 에대하여양정치그램행렬을생성하는커널 K : X X R는양정치커널 (positive definite kernel) 이라부름 x i 값이서로다를때그램행렬이순양정치행렬인경우에는 K를순양정치커널 (strictly positive definite kernel) 이라부름 박창이 ( 서울시립대학교통계학과 ) 커널방법론 14 / 31

15 재생커널힐버트공간 I F: 함수 f : R p R를원소로갖는함수공간 F상의내적 (inner product), : F F R f, g F, f, g = g, f f 1, f 2, g F, c 1, c 2 R, c 1 f 1 + c 2 f 2, g = c 1 f 1, g + c 2 f 2, g f F, f, f 0. 등호가성립할필요충분조건은 f = 0 F상의노음 (norm) : F R f F, f 0이고 f = 0일필요충분조건은 f = 0 f, g F, f + g f + g f F와 c R, cf = c f ( 예 ) F = R p x, y R p 에대하여 x, y = x T y이고 x = (x T x) 1/2 박창이 ( 서울시립대학교통계학과 ) 커널방법론 15 / 31

16 재생커널힐버트공간 II 힐버트공간 H: 내적이존재하는완비된 (complete) 선형공간내적으로부터유도되는노음 =, 을흔히고려 H는분리가능 (separable) 하다고, 즉, 가산무한개의정규직교기저 (countable orthonormal basis) 를가진다고, 가정통계학에서힐버트공간을고려하는이유완비된공간으로서알고리즘의수렴성을보장내적이존재함으로써직교성이나정사영 (projection) 을구할수도있음 박창이 ( 서울시립대학교통계학과 ) 커널방법론 16 / 31

17 재생커널힐버트공간 III C[a, b] 노음 : f = max x [a,b] f (x), 내적은존재하지않음 힐버트공간이아님 L 2 [a, b] 내적 : f, g = ( b ) a f (x)g(x)dx, 노음 : f = b 1/2 a f 2 (x)dx 힐버트공간 g(x) 를 x = k 에서만 f 와다르게정의하면 g L 2 [a, b] 이고 f g = 0 내적이임의의한점에서다른함수와구별하지못하는단점을가지고 있어서이함수공간을예측문제에서적용하기어려움 박창이 ( 서울시립대학교통계학과 ) 커널방법론 17 / 31

18 재생커널힐버트공간 IV 힐버트공간 H상의평가함수 (evaluation functional) F t : H R f H, F t [f ] = f (t) 평가함수가유계 (bounded) 인경우힐버트공간 H를재생커널힐버트공간이라부름 L 2 [a, b] 에서는두함수가제곱적분가능하지만유한개의점에서값이임의로다를수있음 재생커널힐버트공간이아님 박창이 ( 서울시립대학교통계학과 ) 커널방법론 18 / 31

19 재생커널힐버트공간 V H 가재생커널힐버트공간이면 t X 에대하여 t 의대표자 (representer) K t H 는재생성 (reproducing property) 을가짐, 즉, f H, F t [f ] = K t, f H = f (t). K(t, x) = K t (x): 재생커널 (reproducing kernel) 재생커널힐버트공간이주어지면대응되는유일한재생커널이존재함을의미반대로양정치커널 K가주어지면 K를재생커널로갖는유일한재생커널힐버트공간 H가존재 박창이 ( 서울시립대학교통계학과 ) 커널방법론 19 / 31

20 여러가지커널 I K 1, K 2 : X X 상의양정치커널 K: 양정치커널 K(x, x ) = K 1 (x, x ) + K 2 (x, x ). c > 0 에대하여 K(x, x ) = ck 1 (x, x ). c > 0 에대하여 K(x, x ) = K 1 (x, x ) + c. K(x, x ) = K 1 (x, x )K 2 (x, x ). 임의의함수 f : X R 에대하여 K(x, x ) = f (x)f (x ). 임의의 θ 1 > 0 와자연수 θ 2 에대하여 K(x, x ) = (K 1 (x, x ) + θ 1 ) θ2. 임의의 σ > 0 에대하여 K(x, x ) = exp(k 1 (x, x )/σ 2 ). 임의의 σ > 0 에대하여 K(x, x ) = K(x, x ) = exp( (K 1 (x, x) 2K 1 (x, x ) + K 1 (x, x ))/σ 2 ). K 1 (x, x ) K1 (x, x)k 1 (x, x ). 박창이 ( 서울시립대학교통계학과 ) 커널방법론 20 / 31

21 여러가지커널 II ( 예 ) K 1, K 2 : H 1 과 H 2 상의재생커널 직합 (direct sum) 공간 H 1 H 2 : K 1 (x, x ) + K 2 (x, x ) 텐서곱 (tensor product) 공간 H 1 H 2 : 과 K 1 (x, x ) K 2 (x, x ) 박창이 ( 서울시립대학교통계학과 ) 커널방법론 21 / 31

22 대표자정리 I 재생커널힐버트공간에서의벌점화 [ ] 1 n ˆf = arg min L(f (x i ), y i ) + λj(f ), (2) f H n i=1 K: 재생커널, H: K 에의해정의되는재생커널힐버트공간 재생커널에의해이론적인문제는해결 : 해는잘정의되고, 해의존재성과유일성은손실함수 L 과벌점항 J(f ) 에의존하며, J(f ) = f 2 이흔히사용됨 실제계산문제 H 는함수공간이므로무한차원임. 유한개의자료로부터무한차원의 해를구해야함 박창이 ( 서울시립대학교통계학과 ) 커널방법론 22 / 31

23 대표자정리 II Theorem ( 대표자정리 ) J(f ) 가 f 2 에대한단조증가함수이면 (2) 의해 ˆf 는적절한 c 1,..., c n R 에대하여 f (x) = 로표현된다. n c i K(x i, x) i=1 무한차원의힐버트공간상의최적화가유한차원 R n 상의최적화문제가 됨 박창이 ( 서울시립대학교통계학과 ) 커널방법론 23 / 31

24 대표자정리 III L: 볼록손실함수인경우 Tikhnov 벌점화 (1) 는 Ivanov 벌점화 Philips 벌점화 와동치 1 제약조건 J(f ) τ하에서 arg min f H n n L(f (x i ), y i ) i=1 제약조건 1 n n i=1 L(f (x i), y i ) κ 하에서 arg min f H J(f ) 박창이 ( 서울시립대학교통계학과 ) 커널방법론 24 / 31

25 벌점화최소제곱법 I 최소제곱서포트벡터기계 (least squares support vector machines) 라고도불림 (1) 에서손실함수로서제곱오차 L(y, ˆf (x)) = (y ˆf (x)) 2 를사용 Q λ (f ) = 1 n n (y i f (x i )) 2 + λ f 2 i=1 = 1 n y Kc 2 + λc T Kc = 1 n (y Kc)T (y Kc) + λc T Kc, K = (K(x i, x j )): c = (c 1,..., c n ) T 박창이 ( 서울시립대학교통계학과 ) 커널방법론 25 / 31

26 벌점화최소제곱법 II c 에대한일차및이차도함수 H = Q λ (f ) c = 2 n Ky + 2 n K2 c + 2λKc Q λ (f ) c l c m = 2 n (K2 ) lm + 2λ(K) lm. ( Qλ (f ) c l c m ): 헤시안 (Hessian) 행렬 K: 양정치 H: 양정치 해 ĉ = (K + λi) 1 y 박창이 ( 서울시립대학교통계학과 ) 커널방법론 26 / 31

27 커널로지스틱회귀 I Y = {0, 1} 모형 f (x) = log P(Y = 1 X = x) P(Y = 0 X = x) ef (x ) p(x) = P(Y = 1 X = x) = 1 + e f (x ) 박창이 ( 서울시립대학교통계학과 ) 커널방법론 27 / 31

28 커널로지스틱회귀 II 목적함수 Q λ (f ) = n [y i log p(x i ) + (1 y i ) log(1 p(x i ))] + λ 2 i=1 f 2 = y T Kc + 1 T log(1 + exp(kc)) + λ 2 ct Kc. 을최소화계수 c의추정 : 적절한초기치 c (0) 에대하여가중최소제곱법이용 c (k) = (K T WK + λk) 1 K T Wz, 여기서 z = Ka (k 1) + W 1 (y p), W = diag(p(x i )(1 p(x i ))) 박창이 ( 서울시립대학교통계학과 ) 커널방법론 28 / 31

29 커널 로지스틱 회귀 III 계산량이 많을수 있기 때문에 서포트 벡터 기계와 같이 전체 모형에 P 대하여 근사가 잘 되는 부분 모형 f (x) = i S ci K (x i, x)를 고려 S는 훈련 자료의 부분 집합을 나타내며 S상의 자료점을 임포트 벡터(import vector)라고 부름 박창이 (서울시립대학교 통계학과) 커널 방법론 29 / 31

비선형으로의 확장

비선형으로의 확장 비선형으로의확장 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 비선형으로의확장 1 / 30 개요 선형모형은해석과추론에장점이있는반면예측력은제한됨능형회귀, lasso, PCR 등의방법은선형모형을이용하는방법으로모형의복잡도를감소시켜추정치의분산을줄이는효과가있음해석력을유지하면서비선형으로확장다항회귀 (polynomial regression): ( 예 )