머신러닝 수업 6주차 - Multivariate Methods

10/17

Multivariate Methods

오늘은 챕터 5를 다룰 것이며, 주제는 Multivariate methods이다.  Univariate와 같은 컨셉을 이용할 것인데 variable의 개수가 늘어난 multidimensional case를 다룰 것이다. 그리고 나서 챕터 8의 non-parametric method로 넘어갈 것이다. (중간고사는 non-parametric method까지 포함할 것이다)

이 챕터에서 여전히 parametric approach를 사용할 것인데, multivariate case (multivariate dimension)를 볼 것이다. input이 more than 2 variable인 경우이다. see how such function can be learned from a labeled multivariate samples and how the complexity of the learner can be fine-tuned to the data at hand. 많은 application에서 univariate variable보다는 more than 2 random variable을 가지고 있다. (ex. brain image)

capital X는 matrix이고, composed of N number of observation으로 이루어져 있다. 각 observation X는 d dimension이다. 각 sample의 element를 의미한다. 각 data의 1 observation 이 1 variable이다. N X d matrix 라고 표시할 것이다. loan application 예시에 대해 이야기할 때는, age 등의 변수들이 observation vector로 동시에 고려될 수 있다. 예를 들어, customer age가 10살이면 marital stage가 아닐 것이다. 그래서 변수들 끼리 어떤 관계가 있을 텐데, 이런 correlation 관계가 없다면 multivariate analysis를 할 필요가 없다. 그냥 univariate case를 multiple time하면 된다. variable 사이의 inexplicit 관계를 고려해야한다. 

jumping하기 전에 basic definition of mean, variance, covariance, correlation을 다룰 것이다. mean vector는 단순히 1st order expectation of random variable이다. mean은 이미 친숙할 것이다. variance 개념은 how much random variables variate를 나타내는 것이다. 이것은 2nd order expectation으로 정의될 수 있다. covariance 는 relation between different random variables를 나타낸다. random variable들을 subtracted by their own mean을 한 다음에 그들의 관계를 care하는 것이다. 한 variable이 조금 변했을 때 다른 variable은 얼만큼 변하는 가 하는 것이다. correlation은 normalized covariance이다. variance나 standard deviation을 가지고 normalize를 한다. 

이거에 대해 알고 gaussian distibution으로 넘어갈 것이다. 이전에 이미 univariate gaussian에 대해 다뤘다. parametric approach에서 only parameter는 mean과 variance (or standard deviation)이었다. mean과 variance는 데이터로부터 얻는다. 이것을 (그림의 아래 패널) Multivariate case로 확장한다. 식을 보면 normalizing factor가 있고, 주된 차이는 오른쪽 부분에서 나온다. univariate일 때 square term이었던 부분이 dot product로 바뀌었다. 그리고 그 안에 covariance가 있다. covariance는 variance as scale factor의 역할을 하고 있다. 그래서 여기에 나오는 parameter는 mu와 covariance인데, 이것은 데이터로부터 얻을 수 있다. 이걸 알면 분포를 특정할 수 있기 때문에 sufficient statistics이다.

주로 Gaussian을 이야기하는 이유는 central limit theorem 때문이다. set of random variable 은 데이터가 증가함에 따라 점차 Gaussian 형태가 된다. 

데이터로부터 가능한 6 outputs가 있다. 실험을 여러번 반복하면 at some point에서 Gaussian 분포를 따르게 된다. 이게 central limit theorem의 내용이고, nature에 기반했기 때문에 Gaussian을 쓰는 것이다. 

여기 이 슬라이드는 가우시안과 관련이 있다. 공식을 어떻게 이해하는지에 대한 insight를 주기 위한 것이다. 공식의 왼쪽 아래는 normalizing factor니까 무시한다. 오른쪽 부분이 왜 bell shape를 만들어내는지 볼 것이다. x-mu는 distance from the mean을 의미한다. mu와 variance는 somehow fixed된 값이다. mu와 sigma square는 우리에게 주어진 값이고 알고 있다고 가정한다. 이 경우에 mu는 0이고, x는 value of x를 의미한다. mu로부터 멀어질수록의 distance는 yellow line으로 표시되어 있다. positive way나 negative way로 얼만큼 distance를 가지고 있는지 보이는데, distance를 보여줘야 하므로 absolute value를 표현하였다. 그래서 |x-mu|가 노란 선이다. 근데 여기서 square를 취하면 여기 파란 선이 된다. absolute 대신에 이 function은 quadratic이 되는 것이다. mu로부터 멀어질수록 higher distance를 보이게 된다. distance가 quadratically 커진다. 여기에 -를 취하면 blue line을 convex에서 concave로 만들어준다. 그러면 그림 상으로 flip된다. 2 sigma square을 scale factor로 사용하면 green line을 갖게 된다. 그 다음 exponential을 취하면 위로 올라가고 non-linear form이 된다. 그리고 마지막으로 constant로 나눠주면 red line이 된다. 이 shape를 설명하는 이유는 가우시안 공식이 복잡해보임에도 불구하고 하나씩 보면 how the function looks like를 알 수 있다.

Multivariate case의 경우 variance 대신 covariance를 가지고 있는 것이고 role of covariance는 정확히 똑같은 일을 한다. distance from mean을 가지고 나눠주는 역할을 해서 normalizing factor가 되고 분포가 probability axiom을 따르도록 해준다. 

x-mu는 distance from mu를 multidimensional case로 구하는 것 뿐이다. x가 mu로부터 얼마나 떨어져있는지가 Univariate case와 Multivariate case에서 의미가 동일하다. 공식은 |x-mu|^2 에서 (/x-mu)^2을 (/x-mu)T(/x-mu)로 써준 것 뿐이다. Univariate case에서는 단순히 how far from distance를 나타내므로 이건 유클리디안 거리다. 그런데 sigma ^2 대신 대문자 Σ 로 나눠줘서 normalizing을 해준다. how much value are varied를 보여주는 값인데, variance는 매트릭스 중간에 diagonal로 들어있고, 나머지 칸에는 relation between random variables가 들어있다. xi와 xj가 highly correlated라면 그걸 더 고려해줘야 한다. 그러면 유클리디안 디스턴스에서 개념이 변해서 마할라노비스 디스턴스가 된다. distance among the random variables를 더 고려해주게 된다. (변수들이 완전히 독립적이어서 관계가 없을 때 유클리디안 디스턴스가 됨) 

Covariance matrix에 대해서 생각해볼 것이다. 우리는 이미 Covariance matrix가 symmetric하다는 것을 안다. symmetric이라는 것은 upper triangular part가 lower triangular part와 완전히 똑같은 것이다. 또한 covariance matrix는 square matrix이기 때문에 D x D 형태이다. D는 number of variable을 뜻한다.

그리고 이건 positive definite이다. (=모든 eigen value가 non-negative, or positive 인 것을 의미한다.) 

covariance matrix인 Σ은 어떤 경우에 decomposition에서 eigen vector가 되고, eigen value가 있을 것이다. (eigen vector는 unit length를 갖도록 transform하는 역할을 한다. by normalizing with the norm of eigen vector로 - 첫 번째 시간에 소개한 linear algebra를 참조할 것) eigen vector는 independent하고 perpendicular하다. ui는 transpose하고 ui랑 곱하면 1이 된다.

(covariance matrix는 full rank이다.) 정의에 따르면 ui T와 ui의 곱이 I이기 때문에, inverse of matrix를 해주면 위와 같이 식이 변형된다. cubic time complexity (시간 복잡도) 에 따르면 D가 number of matrix일 때 O (D^3) 이런 식으로 표현하고, computer science 분야에서 inverse of matrix를 하는 것은 굉장히 expensive한 작업이다 (글쓴이 - 시간 복잡도가 크면 계산이 오래 걸림). 하지만, eigen vector와 eigen value를 알고 있으면 inverse하는 게 매우 쉽다.

이제 아까 정의한 마할라노비스 거리에 대해 생각해볼 것이다. inverse of covariance를 아까 구한 식으로 적어준다. scalar는 앞으로 이동할 수 있어서 식이 두번째줄과 같이 변형된다. 그리고 transpose property를 사용한다. (U| T) T = U| (글쓴이 - U|는 /x처럼 줄을 하나 더 그은 것을 표현한 것이다) transpose를 두 번 하면 자기 자신이 된다. 그러면 세번째 줄은 vector들의 dot product로 간단하게 생각해볼 수 있다. 이전에 얘기한 것처럼 두 vector의 곱은 similarity measure이다. 혹은 projection one vector to the other vector를 의미한다. {}을 보면 x-mu라는 vector를 eigen vector로 projection한다고 생각할 수도 있다. 혹은 new basis에서의 distance를 측정하는 것이다. covariance matrix를 decomposing 했을 때 2 dimensional space에서 2개의 eigen vector를 찾을 수 있고, 이 둘이 perpendicular하다는 것을 알고 있다. 그리고 unit length를 갖도록 transform 되어있다. u1과 u2는 magnitude나 length가 1인 eigen vector이다.

가운데 mu vector로부터 distanc를 구할 수 있다. mu와 x사이 거리 또한 다른 vector가 된다. (=x-mu) 어떤 vector든 이걸로 project를 할 수 있다. eigen vector들로 new coordinate system이 define된다. 이 부분을 이해하기 위해서는 linear algebra에서 linear system을 언급한 부분을 기억해야 한다. 일반적으로 우리가 아는 x1과 x2로 이루어진 친숙한 coordinate system이 있다. basis function은 (1,2) point가 있다고 한다면 이것을 1 x x1 + 2 x x2 로 표시할 수 있다. (글쓴이 - [1,2] 와 [x1; x2]의 곱)

basis를 변형해서 [1,0]과 [0,1]이었던 축을 [1,2] [-1,1/2]로 표현하면 이제 [1,2]가 [1,0]이 된다. 

1 x [1]  + 0 [-1]

1 x [2]  + 0 [1/2]

로 표현된다.

이렇게 축을 이동하거나 회전시킬 수 있다. x-mu는 모든 x vector들을 origin으로 옮겨주는 것이다. 위 슬라이드의 그림을 보면 circle은 x1과 x2 사이의 어떤 relation을 보여준다. 이것을 새 축으로 projection하면 세로축으로 small variance를 갖게 된다. 

covariance matrix의 대각선 부분은 각각의 random variable의 variance를 나타낸다. sigma 1 ^2와 sigma 2 ^2는 x1 dimension에서 x1이 얼마나 varies한지와 x2 dimension에서 x2가 얼마나 variable한지를 나타낸다. sigma 12 ^2와 sigma 21 ^2는 x1와 x2의 관계를 나타낸다. 원이 오른쪽 위로 rotate되어있으면 x1과 x1가 positively correlated되어있고, negatively correlate 된 관계라면 다른 방향으로 rotate되어있을 것이다. 그것을 이 covariance value가 보여준다. 

eigen vector를 구하면 highest variance 방향을 찾을 수 있다. 똑같은 개념이 PCA에서도 사용될 것이기 때문에 이 부분을 자세히 설명하고 있다. dimension reduction에 사용할 수 있다. 가장 큰 eigen vector가 가장 큰 variance를 보이는 축이 된다. 그 다음으로 크고 수직인 eigen vector가 second largest variance를 나타낸다. 만약 3 dimensional space를 가지고 있다면 eigen vector를 3rd largest variance direction까지 얻을 수 있을 것이다. highest variance와 second highest variance를 고려하는 이유는 중요한 정보가 있기 때문이다. 엄청나게 많은 sample을 얻었다고 가정해본다. 그런데 만약 sample이 ............ 이런 식으로 수평으로 distributed 되어있다. 가로 세로에 same scale이 적용된 상태이다. 그러면 x2는 정보를 전혀 주지 않고 모두 x2에 대해서 같은 값을 가지고 있다는 것을 알아차릴 것이다. 하지만 x1 direction이나 dimension으로 본다면 value가 크게 변한다. 이 direction이 가장 많은 정보를 가진 방향이다. 

만약 샘플이 우상향하는 모양을 가지고 있다면, 원래 coordinate system으로는 x1과 x2에 모두 정보가 있지만, 이것을 아까처럼 새로운 coordinate system으로 고려한다면 아까와 똑같은 일이 일어난다. 한 방향으로의 variation이 아예 없어진 것이다. 한 dimension만 필요한 것이다. 이게 PCA의 기본 개념이다. (무엇이 principle component인지를 찾는 것)

2 포인트 사이 거리를 계산할 때 variance를 고려한 거리를 계산할 수 있다. (글쓴이 - variance가 엄청 클 때 긴 거리와 variance가 작을 때 작은 거리가 이렇게 계산하면 같은 distance일 수 있다.) 그게 마할라노비스 거리의 개념이다.

그리고 covariance matrix에 따라 gaussian의 형태가 달라진다. 위의 그림들은 off diagonal term이나 diagonal term을 변화시켰을 때 나오는 결과들이다. (how distribution changes) center가 mean을 의미한다. covariance는 타원의 형태를 결정한다. x나 o는 sample을 denote한다. 더 색이 빨갈 수록 higher probability를 의미한다. off diagonal term에 들어있는 것이 positive나 negative 형태를 결정한다. 

샘플을 가지고 analysis를 할 때, 먼저 covariance에 집중해야 한다. 머신러닝도 decision을 위해서 먼저 샘플 사이 covariance를 utilize한다. covariance에 따라 decision boundary가 결정된다. 0 off diagonal value를 가지고 있는 (4)가 가장 simple한 경우이다. 두 그룹이 correlation이 없고, x와 y에 대해 equal covariance를 가지고 있다. 그러면 feature space를 partition하는 single line을 얻게 된다. 이 선을 기준으로 넘으면 모두 빨강으로 분류되고, 왼쪽에 있는 것은 모두 파란색으로 분류된다. 그런데 diagonal covariance를 가지고 있다면 (3), 각 dimension 별로 다른 covariance를 가지고 있다면, 그림 상에서 x가 y에 비해 작은 variance를 가지고 있다. 두 class는 여전히 same form of covariance를 가지고 있다. 이 경우에도 샘플을 separate하는 line이 존재한다. 

그리고 그 다음 correlation value가 있는데 (2), 이제 그림이 rotate하기 시작한다. 하지만 여전히 line function으로 분류할 수 있다. 그런데 class마다 다른 covariance를 가지고 있을 때 (1), 나누기 복잡해진다. 선으로 나눴을 때와 달리 아랫부분이 다시 빨간 class일 확률이 높아지기 때문이다. Multivariate case를 위한 다양한 likelihood function을 사용하다보면 class별로 다른 covariance를 갖게 되고, 그러면 이렇게 복잡한 decision boundary를 나타낼 수도 있다. decision boundary는 prior에 의해서도 영향을 받는데, 지난 시간에 배운 것처럼 prior가 변하면 decision boundary가 shift하게 된다. 여기에 covariance는 decision boundary의 form을 결정한다.

다른 알고리즘들을 이해하기 위해서는 다른 characteristic of function을 이해해야 한다. (글쓴이 - 가우시안 function 안의 covariance에 대해 이렇게 자세하게 이해함으로써 알고리즘이 어떻게 작동하는지 더 잘 이해할 수 있게 된다)

covariance에 대해 더 살펴볼 것이다. determinant of covariance 값이 매우 작다면 (size, volume이 작음) 모든 sample들이 mean 근처에 close together하다는 것을 의미한다. determinant가 크다면 high variation을 가지고 있다는 것을 의미한다. 그리고 covariance matrix는 symmetric 하고 positive definite라고 가정하는 것을 아까 보았다. 

univariate case에서 variance는 sample variance로부터 계산하였다. mu와 covariance도 unknown 값이기 때문에 데이터로부터 추정해야했다. mu는 sample mean이고, covariance도 sample covariance로부터 나온다. mu는 이전에 봤듯이 unbiased값이지만, variance는 somehow biased 되어있다. 그래서 bias를 피하기 위해서 1/N 대신 1/ N-1을 해줘야 했다. 특히 샘플 수가 적으면 high bias된다. 

covariance matrix가 symmetric하고 positive definite하다는 것은 eigen vector들이 모두 non negative하다는 것이다. 하지만 sample covariance를 계산했을 때 때때로 0 eigen value를 얻는 경우가 있다. 이것을 overcome하는 방법은 dimension을 축소하는 것이다. 이것도 dimension reduction idea이다. linear dependent 관계가 있다는 것인데, 이것은 다른 dimension들의 combination으로 얻을 수 있다는 뜻이다. 그러면 그 dimension은 필요가 없다는 뜻이고, 그것을 없앨 수 있다. 또는 0 variance 가진 dimension 없앤다. + determinant는 product of eigen values로 얻어진다. 

이 내용들은 MLE와 관련이 있다. 지난 시간에 mu와 variance를 보았는데, 그것과 똑같은 내용이 multivariate의 경우에도 적용이 된다. MLE를 계산하기 위한 mu가 sample mean으로부터 나오고 covariance는 sample covariance로부터 나온다. 그리고 sample covariance가 positive definite인지 확인해야 determinant를 구할 수 있다. determinant가 0이 나오면 뭔가 문제가 있는 것이다. inverse of covariance를 얻을 수 없기 때문이다. inverse of covariance를 얻으려면 matrix가 반드시 full rank여야 한다. 이 문제를 해결하기 위해 add some values를 하는 것이 가능하다. 혹은 dimension을 줄이는 방법이 있다. practically 중요한 부분이다.

그리고 Gaussian distribution의 nice property 하나를 더 고려할 것이다. 다른 모델들은 distribution에 대한 다른 property를 갖고 있다. dimension이 D인 x를 가지고 있고, distribution은 mu와 sigma로 정의되어 있다. 다른 vector w, weight coefficient도 고려한다. linear method로 observation에 기반한 product로 나온 output value를 계산해보면 linear regression과 다를 게 없다. 이 경우에 x가 random variable이고 gaussian distributed 이며 mu는 fixed value라는 것을 알고 있다. guassian distributed 된 것의 combination 또한 gaussian distributed이다. x는 random variable이고, w는 이미 결정된 값이다. 위와 같이 계산이 되고, 이것을 variance 계산에도 적용 가능하다. 마지막 점에 있는대로 D dimensional normal vector를 w vector에 projection한다면 univariate normal값을 얻게 된다. 

이것을 일반화할 수 있다. single vector대신 multiple vector를 고려한다. D dimensional x를 K dimensional space로 확대한다. 그리고 아까처럼 linear transformation을 해준다. linear transformation 이후에 another gaussian distribution을 얻을 수 있다. 그래서 이번엔 초록 글씨로 D dimensional normal distribution을 K dimension으로 Projection하면, K dimensional normal 결과를 얻게 된다.

어떤 경우에 D dimensional space인 샘플을 가지고 있는데, gaussian function을 likelihood로 쓰고 싶은데, limited number of sample을 가지고 있다면, D dimensional vector를 lower dimension of vector로 바꿔주는 것을 고려해볼 수 있다. 2 dimensional space에서 single vector로 projection 해줌으로써 sample이 1 dimension으로 projected된 값을 얻을 수 있다. 그리고 샘플이 original space에서 gaussian 분포를 따른다면, K dimension에서도 여전히 gaussian 분포를 따를 것이다.

classification을 위해서 straight forward하다. 필요한 내용은 다 학습하였다. 계산을 간단하게 하기 위해서 log를 취하였다. 그러면 분자와 분모가 분리되어서 class별로 share되는 evidence part를 따로 볼 수 있다.

p(ci | /x) = p(/x | ci) P(ci)   / p(/x)

P(/x | ci)는 multivariate case를 고려할 것이다. class 별로 P(ci) 값은 다르지만 P(/x)는 모두 공유한다. 그래서 P(/x)는 decision boundary를 만드는데 아무런 영향도 주지 않는다. 여기에 로그를 취하면 다음과 같다.

log(p(ci | /x)) = log(p /x | ci)+log(p(ci))

ci는 class 마다의 index로 하나씩 1 distribution for each class를 의미한다. ci (i th)class일 때, likelihood of your observation x를 의미한다. mu와 covariance를 구하기 위해서는 training sample belongs to that specific class를 이용해야 한다.

- Examples of most classes can be seen as mildly changed versions of a single prototype

- Covariance matrix, sigma i, denotes the amount of noise in each variable and the correlations of these noise sources.

- While real data may not often be exactly multivariate normal, it is a useful approximation

그런데, x가 가우시안 분포를 따르지 않는다면? 하는 질문이 생길 것이다. 다른 방식으로 분포가 되어있다면 당연히 위 내용은 not gonna work할 것이다. 그런데 분포가 무슨 form인지 잘 모른다면, underlying distribution을 approximation 하기 위해 gaussian 방식을 사용해도 된다. 

예를 들어 샘플이 왼쪽으로 skewed 되어 있다면 이것은 exactly gaussian 분포는 아닐 것이다. 가우시안이 되기 위해서는 mean 근처에서 symmetric해야 한다. 이 분포를 추정하기 위한 nice form of density function이 없다면 gaussian 분포를 사용해서 approximation을 할 수 있다. 물론 차이는 있을 것이다. 이게 idea of Laplace approximation이다. 가우시안 분포는 머신 러닝에서 매우 common한 분포이다. 이것은 likelihood estimation 뿐만 아니라 approximation of distribution에도 사용된다. 그리고 같은 내용을 variational approximation에도 적용할 수 있다. Laplace와 variational 방법이 있는데, 후자가 좀 더 general한 방법이다. advance paper를 보면 Laplace를 많이 사용하였다. 그리고 approximation하는 다른 방법으로 Sampling based 방식이 있다. 이 방법들이 가장 흔한 방법들이다.

class별로 function g(x)를 따로 구한다. covariance는 sample로부터 얻어질 것이다. 위 식을 reorganize하면 아래부분처럼 간단한 term으로 변형할 수 있다. 중요한 부분은 input x가 어디있는지 하는 것이다. 그 외의 나머지는 모두 constant이다. smaple이라서 bold x로 표시되어야하는데, 슬라이드가 잘못되었다! 정리를 하면 quadratic form을 얻게 된다. S inverse는 Wi로 denote해준다. S inverse와 m의 곱을 w로 써주고 나머지 모든 constant 값을 wi0로 정리한다. 그러면 결과적으로 quadratic function이 나오기 때문에 different values of covariance를 가지고 있다면 decision boundary는 non-linear하게 된다. class들이 same sample covariance를 가지고 있다면, class들이 모두 공유하기 때문에 이 부분을 ignore할 수 있다.

S-1 _ i = S -1 _ 1 = S -1 _2....S-1 _k

sample covariance가 위와 같이 모두 동일하다면, decision에 impact를 주지 못할 것이다. 이 부분을 무시할 수 있고, 그러면 discriminant function은 linear function이 된다. 그러면 classification이나 regression에서 distribution이 똑같기 때문에 이 부분을 고려하지 않게 된다.

물론 limitation도 존재한다. high dimension이라서 많은 수의 random variable이 있으면, higher number of parameters가 필요한다. class 별로 필요한 parameter의 수는 슬라이드에 나와 있다. 이 숫자들이 어디서 나오는 걸까? D는 mu로부터 나온다. D x (D+1) /2는 covariance로부터 나온다. covariance는 diagonal term과 off diagonal term이 있다. 이 값에 해당한다. 대각선과 대각선 아닌 값의 합인 D + D x (D+1)/2 가 슬라이드의 값이 되는 것이다. D가 1000이라면 million number of parameters가 필요하게 될 것이다. 그런데 샘플 수가 그거 보다 적다면 mu와 covariance 값을 underestimate하게 될 것이다. 특히 covariance는 high change of bias가 있다. 이를 피하기 위해서 아까 말했듯이 dimension을 줄이거나, dimension을 그대로 유지하고 싶다면 diagonal term에 constant random value를 합하는 방법이 있다. dimension이 서로 dependent한 관계를 갖지 못하게 만드는 것이다. 

다음 슬라이드가 그런 내용들을 설명하고 있다. variance for each dimension만 고려하거나, 더 간단하게 1 variance among dimensions만 고려하는 것이다. 

naive bayes classifier에 기반하면 off diagonal term이 0이다. 각 dimension의 variance만 고려하게 된다. naive bayes는 can be represented as product of univariate gaussian distribution으로 표현된다. off diagonal term이 0이라는 것은 매우 strong assumption이다. practically 매우 잘 사용되는 방법이다. recommendation system이나 spam filtering에 효과적이다.

model selection 관점에서 우리는 limited number of sample을 가지고 있다. sample 수가 적으면 parameter 수가 적게 필요한 간단한 모델을 사용해야 한다. 복잡한 모델을 쓰게 되면 overfitting이 일어나고 일반화가 안 될 것이다.

RDA

알파와 베타 수 크기 조정에 따라 trade off가 일어난다. alpha 0 beta 1이면 1 single covariance over all classes를 의미한다. alpha와 beta는 hyper parameter이다.

여기까지가 chapter 5의 내용이었다. multivariate modeling with gaussian distribution에서 마할라노비스 distance를 소개하였다. 거기서 covariance를 어떻게 구하고 어떤 의미인지를 보았다. off diagonal term이 0이라는 very strong assumption으로 (random variable이 independent each other하게 하면) naive bayes classifier를 derive할 수 있다. different assumption에 따라 different form of model을 derive할 수 있다 (without changing the whole way). bayes rule에서 posterior 구하는 기본 공식으로 다 이어져왔다. 다음 챕터인 non parametric 챕터도 여전히 이 프레임을 따를 것이다. 단 가우시안을 사용하는 대신 distribution을 data로부터 얻는다는 점이 다르다. 

Q. Mutivariate analysis와 GLM이랑 뭐가 다른가? Linear model은 representing the data하는 방식이다. 그리고 Multivariate 는 variable을 여러개 가지고 있다는 것을 의미한다. 

수업 자료

MultivariateMethods_2P.pdf

Nonparametric Methods

이 챕터에서는 Non parametric method를 다룰 것이다. form of distribution에 대해 assumption (inductive bias) 을 하지 않는 것을 의미한다. binary인 베르누이부터 multinomial 까지 gaussian 분포를 고려했었는데, 이 챕터는 그런 분포를 고려하지 않는다. 이전에 말한 것처럼 classification이든, regression이든 여전히 베이즈 framework 내에서 고려할 것이고, 차이점은 오직 how to define the likelihood function으로부터 나온다. 여기 parametric 과 non parametric method를 간단히 비교해두었다. Q. Bayes hierarchical inference에 대해 잘 알고 있는 사람? Bayesian에서는 non-parametric을 다른 의미로 사용하기 때문에 이 부분이 헷갈릴 수도 있다. 

P와 non P 방식의 main difference는 form of distribution을 하는지 안하는지로부터 나온다. parametric은 single global model이다. 가우시안 form에 대해 정의하면 parameter를 조정하면 whole form of distribution도 변한다. mean은 shift가 일어나고, variance는 넓거나 좁아지게 form이 변한다. 

하지만 Non parametric에서는 value나 observation of your sample을 바꾼다고 해서 locally 변하기만 할 뿐 globally 변하지는 않는다. 그리고 in terms of parameter에서는 P는 mean과 covariance만 구하면 되었지만 non P 방식은 그런 parameter가 없다. 그리고 P는 베르누이, 가우시안 등 strong assumption을 가지고 있다. 하지만 non P는 그런게 없다. main paradigm의 차이는 non P는 let data speak for itself한다는 것이다. 

non parametric은 기본적으로  2 step을 따른다. 첫 번째로 small number of similar training instances를 찾아야 한다. similarity를 고려해야 한다. 어떤 new data가 주어지든, 이 distribution에서의 likelihood를 구해야 한다. parametric에서는 distribution을 알았지만, 지금은 그렇지 않기 때문에 먼저 비슷한 샘플들을 찾아야 한다. distance를 구하는 것인데, 마할라노비스 distance도 한 가지 방법이 될 수 있다. 

small number of similar samples instances를 찾은 후에는 base on those samples로 output of probability for your observation을 구한다. bunch of data sample을 가지고 있을 때 new data가 주어지면 원래 데이터로부터 estimate probability given my data by training set를 구하는 것이다.

이 probability, likelihood를 계산하기 위해서는 첫 번째로 observation과 비슷한 set of instances를 찾아야 한다. 내 샘플과 비슷한 j개의 x를 찾으면, 이 sample을 기반으로 estimation을 구한다.

(1) X = {/xi} N_i=1

(2) p(x'|X)

{/xj}j ∈ N(/x)

parametric 방식이 mu, sigma form data를 구한다면, non parametric은 given new test data와 비슷한 set of sample을 찾는다. 그리고 그것을 기반으로 probability를 계산한다. 이것을 이해한다면 이 두 단계 내에는 learning step이 없다는 것을 이해할 것이다. 이런 종류를 lazy learning이라고 부르거나 memory base라고 부른다. 나중에 test data가 주어질 때까지 all denoted sample을 다 memorize하는 것이다. testing sample이 주어지면 similar sample을 찾아야 한다. 그래서 memory based나 case based라고 부르는 것이다.

training step이 없어서 complexity of training은 0이지만, practically testing 동안 모든 계산이 끝나기 때문에 computation이 더 어렵다. (expensive) 

기본적으로 생각할 것은 classification을 할 것인지, regression을 할 것인지다. 그런데 그 전에 베이즈 프레임워크에서 density probability를 compute / estimate 해야한다. 이게 density distribution부터 시작하는 이유이다. non parametric approach의 density estimation을 위해서 수업 초반에 배웠던 probability distribution function 정의를 활용할 것이다. 이 equation을 기억해야하는데, continuous일 때, density distribution function은 위와 같이 정의된다. (random variable x가 smaller or equal to a) continuous일 때 single specific value일 확률은 항상 0이다. 그래서 interval을 고려한다. 이것이 pdf의 개념이고, non parametric에서도 이것과 같은 개념을 사용한다.

그래서 이제 define compute /estimate density 하기 위해서 2 part를 고려할 것이다. density function 정의로부터 F(x)를 구할 수 있다. 다른 non parametric approach마다 F(x)를 구하는 방법이 다르다. F(x)를 알게 되면 distance로 결정되기 때문에 이제 number of sample만 고려하면 된다. number of sample을 total number of sample로 나눠준다. bin interval은 h로 결정된다. 한 bin에 들어가는 x에 size of interval과 total number of sample을 고려한다. 이 definition을 기억하고 다른 method들을 이해해야 한다. 

마지막 문장대로, interval 안에 있는 xn들은 similarity나 distance가 가까운 것들이다. x1과 x2의 interval이 여기에 들어가는가 아닌가를 알기 위해 distance나 how close each other을 측정할 방법이 필요하다. 

이제 가장 간단한 방법을 소개할 것이다. Histogram estimator이다. 사람이 들어있는 image를 processing한다고 하면 (gray scale이라고 가정한다.) 0~255까지의 값을 가지고 있다. 그러면 배경은 다 0이니까 히스토그램을 그려보면 0 부분이 엄청 높은 값으로 나올 것이다. 똑같은 컨셉이 density estimation에 적용된다. 그런데 여기에 bin size가 추가된 것이다. 이미지는 density가 discrete라서 더 쉬운 경우다. 

수평선의 왼쪽에 -2h, h를 써주고 오른쪽에 h, 2h, 4h를 써주면 이게 내 bin이 된다. 그리고 양수나 음수의 m은 h를 쪼갠다. 그리고 bin 안에 속하는 sample 이 몇 개 있는지 센다. 간단하게 하기 위해 h가 1이라고 둔다.

예를 들어, (글쓴이 - 1.2, 1.3, 1.4 등...) 0과 1 사이의 값은 없다. 1과 2 사이에 3개가 있다. 2와 3 사이에 4개를 가지고 있다. 이게 히스토그램의 개념이다. 그 case에 속하는 sample 수를 단순히 세는 것이다.

그림은 다른 h에 따른 차이를 보여준다. h가 2, 1, 0.5개인 경우이다. large bin size를 가지고 있으면 더 많은 sample이 그 안으로 들어가게 된다. small bin size를 가지고 있으면 more picky distribution을 갖게 된다.

그리고 estimate가 0인, no instance가 fall 한 경우가 생기면 discontinuous boundary를 보이게 된다. 그래서 위 그림에서 그림이 끊겨보이는 것이다. 

Naive bayes는 origin을 설정하는 것으로부터 자유롭다. 미리 bin의 position을 설정해놓고, 그 안에 들어가는 샘플 수를 계산한다. training data set 중 하나인 xn을 center로 삼는다. 그리고 왼쪽과 오른쪽은 half of the h로 정한다. 그리고 이 sample around에 얼마나 많은 sample이 있는지를 센다. 그게 Naive estimator이다. free from approximating origin한 것이다. 모든 샘플 중 얼마나 많은 샘플이 이 샘플 주변에 있는지를 계산한다. 그리고 그것을 weight로 사용할 수 있다. training sample 근처에 있으면 1이 되고 아니면 모두 0이 된다. 

매우 straight forward하다.

다음은 kernel estimator이다. Parzen window based approach라고도 한다. 이건 field에서 commonly used된다. 이 function의 form을 보면, naive estimator와 형태는 같다. 차이는 weight function에서 나온다. 이전 슬라이드에서 weight function이 1또는 0이었는데, 이것은 step function이 아닌 더 smooth한 function이다. K, kernel function 중 commonly used되는 것은 normal gaussian distribution이다. 이 function은 activation function으로도 많이 사용된다. 똑같은 테크닉이 SVM의 커널 메소드에도 사용된다. 

K를 u로 바꾸면 얼마나 많은 sample이 xn 주변에 있는지를 세는 것으로 바뀐다. 그것을 variance가 1이 되도록 normalize한 것이다.

똑같은 데이터를 가지고 있을 때, 이렇게 nice continuous한 형태를 갖게 된다. 내가 8개 sample을 가지고 있다고 가정한다. simply put 8개의 gaussian distribution을 취한다. mean은 points of each sample로 지정한다. 거기마다 한 gaussian을 입히고, 다른 곳에 다른 gaussian을 입히고 한다. 총 8개. 8개 sample을 가지고 있기 때문이다. 파란선은 sum of the outputs from 8 gaussians이다. 3개의 gaussian이 샘플 근처에 있다면 그 부근에 high value를 얻게 될 것이다. 

다음은 k-nearest neighbor estimator이다. 이 방식은 very simple algorithm for the classification이다. 어떤 sample이 주어지든 k near sample이면 먼저 K number of sample similar close to the testing sample을 찾는다. 그리고 majority에 따라 decision하는 것이다. 일반적으로 K는 홀수이다.

density에 따라 bin size가 달라진다.

naive estimator와 비교하면, fixed size of interval을 사용한다. 그리고 K-nearest neighbor estimator의 문제는 매우 picky distribution을 보인다는 것이다. 속하는 sample이 없더라도 항상 K nearest neighbor을 고려해야 한다. 그래서 항상 0이 아닌 positive 값을 보이게 된다. 

Kernel function을 여기에 결합시킬 수도 있다.

여기까지 3개의 다른 method를 소개해줬는데, commonly used하는 것들이다. 특히 팔즌 윈도우와 KNN은 매우 잘 쓰인다. 

그리고 지금까지 univariate case를 봤는데, multivariate case에 적용하는 것도 straight forward하다. what kind of distance measure를 사용할지도 고려해야 한다. 그리고 이것은 kernel density estimator for gaussian의 예시이다. covariance나 correlation of values는 고려하지 않는다. 

* Matlab demonstration

사람들이 non parametric을 쓰지 않고 parametric을 쓰는 이유가 있다. 대부분은 Curse of dimensionality 때문이다. 8 dimensional space가 있을 때, 8 bins for each dimension이 있으면 엄청나게 큰 수가 만들어진다. robust estimate를 위해서는 엄청나게 많은 sample이 필요하다. high dimensional space라면 non parametric method를 할 때 be careful 해야한다.

Discrete Inputs의 경우 distance measure를 위해 Hamming distance를 사용할 수 있다. 

estimate는 bayes framework로부터 구하는데, kernel로 likelihood function을 이렇게 define한다. label이 똑같은 sample (Ci에 속한 sample) 만 고려하는데, 그것이 Ni 개이다. 

그러면 discriminant function을 define하기 위한 likelihood와 prior를 얻었다. Normalization 부분은 ignore할 수 있다. 

여기 knn classifier가 있다. knn estimator는 이런 식으로 define된다. (글쓴이 - 전체 k 개 중 i 에 속한 것의 개수) K 가까운 것들 중 Ci 라고 label 된 것이 몇 개인지 센다. (14) 식을 보면 왼쪽은 bayes framework이고, 오른쪽은 simple equation으로 변형된 걸 볼 수 있다. sample 중 k number of sample이나 instance를 찾아야 한다. 그리고 그냥 out of k 중 얼마나 많은 sample이 i로 label되었는지 찾는다. k 가 5개면 5개 중 얼마나 많은 sample이 i로 label 됐는지를 찾는 것이다. 다수결로 결정하는 매우 simple한 방법이다.

여기까지 classification이었고, regression problem을 볼 것이다. training set의 input and output value가 xn, rn으로 주어졌다. rn은 underling function과 noise가 합해진 것으로 본다. parametric에서는 g(x)를 미리 정해서 구한다. 하지만 non parametric에서는 close x가 close g(x)를 가지고 있다는 가정만 한다. neighbor x의 average를 사용한다. classification의 majority 대신 weighted average of the other values를 사용하는 것이다. 

origin과 bin을 선택한 후 average를 취한다. bin size를 3으로 하고 output value를 average한다. 그 안의 3개로 항상 output value를 얻는다. 

결과

또 다른 intuitive way는 average를 하는 대신 각 bin마다 line function을 fit하는 것이다. 

마지막은 kernel 을 이용하여 smoother to estimate하는 방법이다.

마지막 파트는 model selection과 관련이 있다. how to set value of h 에 대한 것이다. predefined interval을 찾는 것이었다. 혹은 knn에서의 k였다. 그런데 조심해야할 것은 너무 큰 value를 설정하면 over smoothing이 일어난다. 너무 작은 value를 설정해도 문제가 된다. validation set을 사용해서 해결한다. 

이 챕터는 non parametric estimation을 보았다. density function estimation을 설명하고 3 different method를 보았다. 이 방법들의 variation은 오른쪽의 simple definition으로부터 나왔다. interval을 어떻게 define하고 어떻게 adaptively change하는지에 차이가 있었다.

* 시험범위는 123458 챕터를 다룰 것이다.

수업 자료

NonparametricMethods_2P.pdf