ML Study(1) - Kernel, Variational Inference, Tree methods

Kernel Method (Gyumin-Lee 23.8.6) Chapter 17 (Nonparametric Method)

17.1 Mercer Kernels (positive definite kerenl a.k.a pd)

$\sum\sum K(x_i, x_j) c_i c_j \geq 0, \; c_i, c_j \in \mathbb{R}$

Kernel can be converted into gram matrix, whose elements are represented by inner products.

Matrix positive definite = Kernel pd 한거와 동일

 

Example  $ K(x,x')=exp(-\dfrac{||x-x'|^2}{2h^2})$ h is a bandwidth(가중치가 들어가는 범위)

ARD Kernel $ K(r) = \sigma^2 exp(-\dfrac{1}{2} r^T \Sigma^{-1}r)$

Matern Kernel 조금 더 제너럴한 표현(함수적 데이터분석에 자주 사용됨)

 

Q. 인풋 두개를 받아서 하나가 기준이 되는지?

A. 하나의 기준을 잡고 나머지 하나의 웨이트를 부여하는게 맞다. (lowess 처럼)

 

Gram Matrix가 Positive Defiinite다.

하나가 다른 하나일때

 

Kernel: $ \chi \times \chi $

Q. Gram Matrix와 Kernel 관계?

 

17.2 Gaussian Process

$ f = (f(x_1), ..., f(x_n)) \sim N(\mu, \Sigma) $

데이터를 함수에 넣었을 때 그 값의 분포를 예측해서, 다른 데이터를 함수에 넣었을 경우를 예측

$ f = (f(x_1), ..., f(x_n)) $

$ f \sim N(\mu, \Sigma) \; \Sigma_{ij}=K(x_i, x_j) $

*가 새로 등장한 경우: 원래 데이터 끼리의 커널, 원래 데이터와 새로운 데이터의 커널

$ p(f_x | x_*, \tilde{D}) \sim N(f_* | mean(X_*)+0^T0^_{-1))$

Covariance가 커널로 나오는 게 차이

noise free observation - 트레인이 x_n, y_n. y_n = f(x_n)

noise가 있을 수 있는데 노이즈가 있는거는 $y_n = f(x_n) + \varepsilon_n, \; \varepsilon_n \sim N(0, \sigma^2_y$

 

Kernel Regression과 동일하게 생각할 수 있는데

$E(y|x) = \Sigma w_n y_n $

 

Random Features for Large-Scale kernel Machines

$k(x,y) = <\phi(x), \phi(y)> $ Merce's theorem  

데이터만의 내적을 다 계산해야하기 때문에 $O(n^3)$

커널의 컴퓨테이션 문제를 랜덤피쳐로 근사시킨다 $z(x)^Tz(y)$로 근사시킴 (z는 linear한 random feature)

$e^{-1/(2\sigma^2) ||x-x^*||^2}$ 이 친구의 furier transformation이 본인과 동일

적분으로 바꾼 후 적분에 있는 값을 sampling해서 transposing값으로 근사한다 라는 내용.

 

17.3~4 SVM

 

23.8.15

 

 

 

Variational Inference

 VI tries to find variational distributions that serve as good proxies for the exact solution (true posterior)

Reference: https://zhiyzuo.github.io/VI/

Variational Inference

 

23.8.7

Tree Methods

Ch18. $T(x;\Theta) = \sum^J_{j=1} r_j I(x\in R_j), \; \Theta=\{ R_j, r_n\}^J_1$

Split input space into j spaces.

 

By minimizing loss, the parameters are updated. 

$ \hat{\Theta} = argmin_\Theta \sum_j \sum_{i \in R_j} L(y_j, r_j)$

각 노드에서의 예측값은 $r_j$. 하지만 위 로스는 이산이라 미분불가능.

 

대안을 다음으로 사용

1) $R_j$ is given. $\hat{r}_j$ 찾기 -> $\bar{y}$ in regression, $\mode(y)$ in classfication.

2) find $R_j$ -> feature space 분할의 기준점 찾기 -> greedy algorithm for all data points

ㄴ 데이터 포인트 기준 -> sorting 후 n개 뽑아서 사용하여 영역 구분

ㄴ sorting 시간복잡도 문제가 있어서 별로

 

What is the Best split?

• Regression: 각 영역의 mse를 줄이도록
• Classification: 각 영역에 비슷한 클래스가 모이도록 (How similar? measured by impurity)
  • impurity index: gini index, entropy

 

Tree size up -> overfitting 

pruning with regularization $\sum \sum L( \;\; )+ \alpha |T| $ T = 마지막 leaf node 개수 

$\alpha$ determines cost complexity

Tree: Variance is so high (데이터 기준으로 split을 찾기에 일부 데이터 바뀌어도 var 크게 바뀜)

 

remedy: Bagging 

Bootstrap + Aggregating

$z=\{(x_1,y_1) ,,, (x_N,y_N)\}, \;\; z^*: B.S.$

$\hat{f}(x) = \dfrac{1}{B} \sum^B_{b=1} \hat{f}^{*b}(x)$

B개의 Bootstrap 평균에서 적합된 친구들의 평균

 

Bagging은 꼭 tree에서만 쓸 수 있진 않고, Bagging의 소스로 사용되는건 뭐든 상관없음. Tree는 nonlinear모형이기 때문에 Bagging에 적합.(근데 linear모형에서는 B가 커지면 사실 부트스트랩 의미 없음)

 

Boosting(허접한 모형을 여러개 모아서 강력한 모형 만들기)

AdaBoost M1(최초)

ㄴ Task: Binary Classification. $y \in \{-1,1\}$

ㄴ Idea: weak classifiers => powerful classifier

 

$ z $ ->  G_1(x) $ Adaboost에서는 $G_1(x)$가 stump tree (weak)

얘가 엄청 틀릴텐데. 틀린 데이터에 대해 웨이트를 조절하여 다음과 같이 피팅

$ z'(weighted) $ -> $G_2(x)$

$ z''(weighted) $ -> $G_3(x)$

$G(x) = sign[\sum^M_{m=1} x_m G_m(x)]$

 

 

$ f(x) = \sum \beta_m T(x; \gamma_m)$

Adaboost도 basis expansion 형태이기 때문에 최적해를 구해야하는데 구하기가 쉽지 않음.

한번에 최적해 구하기 힘들어서 subproblem을 푸는 방식으로 최적화. 

$ f(x)=0$ -> $f(x)=0+\hat{T}_1$ -> $f(x)=0+\hat{T}_1+\hat{T}_2$

forward stagewise modeling

 

23.8.15

AdaBoost  M1

오답포인트들에 대한 가중치 부여

 

 

새로운 모형이 설명못하는 부분을 타겟으로 설정

 

Gradient Boosting

$$f^* = argmin_f L(y,f), \; f = [f(x_1) \cdots f(x_N)]^T$$

$$ f_n = f_{n-1} - \rho_m\nabla L(f_{n-1}) $$

$$ f_1 = f_0 - \rho_1 \nabla L(f_0)$$

$$ f_2 = f_1 - \rho_2 \nabla L(f_1) = f_0 - f_1 \nabla L(f_0) - \rho_2 \nabla L(f_1) $$

$$ f_n = f_0 - \rho_1\nabla L(f_0) - \cdots -\rho_n \nabla L(f_{n-1})$$

 

위의 Adaboost형태( $G(x) = G_0(x) + \alpha G_1(x) + \cdots + \alpha_n G_n(x)$ 와 비슷

negative gradient로 알파 학습시키면 되는거 아닌가? 라는것

즉, $argmin_{G_n} L(G_n, -\rho_1 \nabla L(f_n))$으로 

rgb, lgbm