여태까지는 이 책에서 density estimation이나 data clustering 등의 unsupervised learning 기법들을 많이 사용했지만, 이번 챕터부터는 linear regression부터 시작하여 supervised learning 기법에 대해 다룰 예정이라고 한다.
가장 간단한 형태의 linear regression은 input variable들의 linear combination을 취하는 것이지만, input variable을 nonlinear function을 통해 변형한 것들의 linear combination을 취하여도 (훨씬 더 강력한 표현력을 가지는 동시에) 여전히 linear regression의 유용한 성질들을 이용할 수 있게 된다. 이러한 nonlinear function을 basis function이라 부른다.
기본적으로 input variable과 corresponding target 이 주어지고, 새로운 데이터 의 target value를 추론하는 것을 목표로 한다. 확률적으로 생각해보면, training data를 통해 predictive distribution 를 얻어내는 것을 목표로 한다. 이렇게 도출된 를 통해 decision theory를 따라 적절히 선택된 loss(e.g. squared error)를 최소화하는 방향으로 추론값을 얻어낼 수 있다.
3.1. Linear Basis Function Models
가장 간단한 형태의 linear model은 앞서 언급했듯 다음과 같이 input variable의 linear combination을 취하는 것이다.
이러한 linear model의 핵심은 바로 모델이 parameter 에 대한 linear function이라는 것인데, 위와 같은 모델은 input variable에 대해서도 linear function이기 때문에 표현력에 큰 한계를 가진다. 따라서 아래와 같이 input variable의 fixed nonlinear function의 linear combination을 취하는 모델로 확장한다.
여기서 는 bias parameter라 불리는데, 흔히 과 같은 dummy basis function을 정의하여 다음과 같이 표현한다.
이로써 우리는 input variable에 대한 nonlinear한 관계를 표현할 수 있는 function을 얻는다. 하지만 linear model의 분석을 간소화하는 핵심 특성은 parameter 에 대한 linearity이므로, 이를 역시 linear model이라 부를 수 있다.
여기서 basis function으로는 이론상 어떠한 functional form이든 택할 수 있다. 가장 대표적인 선택은 아래와 같은 Gaussian basis function이다. 어차피 adjustable parameter 가 곱해질 것이므로 normalization term은 무의미하다.
또한 sigmoid function 를 이용하여 다음과 같은 sigmoidal basis function을 택할 수도 있다.
이 밖에도 function이나 Fourier basis를 택할 수도 있겠다. 하지만 이번 장에서는 basis function과는 독립적인, linear model의 general property를 다룰 예정이다.
3.1.1. Maximum likelihood and least squares
챕터 1에서 curve fitting을 위해 sum-of-squares error function을 최소화하는 polynomial function을 도출해 보았고, 이러한 sum-of-squares error가 Gaussian noise를 상정한 maximum likelihood solution임을 살펴보았다. 이번에 이러한 sum-of-squared approach와 maximum likelihood method에 대해 보다 자세히 다룬다.
이전과 동일하게 target variable 가 deterministic function 와 Gaussian noise 에 의해 결정된다고 하자. (이 때 .)
즉 다음과 같이 쓸 수 있다.
이제 데이터 가 위와 같은 분포로부터 i.i.d.로 도출되었다고 하자. 우선 다음과 같은 likelihood function을 얻을 수 있다.
와 같이 sum-of-squares loss를 정의하면 log of likelihood는 다음과 같이 쓸 수 있다.
이를 에 대해 미분하면 다음과 같은 식이 나오는데,
이러한 gradient를 0으로 설정함으로써 다음과 같은 일반해(normal equation)를 얻어낼 수 있다.
여기서 는 design matrix라 불리는 matrix인데, 번째 행이 번째 training data의 input variable을 나타낸다. 즉 .
이 때 는 의 pseudo-inverse matrix인데, 선형대수에서 다루었듯 만약 가 invertible이라면 이다.
또 에 대해 동일한 log likelihood를 최대화할 경우 다음을 얻는다. 즉 noise variance의 maximum likelihood estimator는 regression function에 대한 target value의 residual variance이다.
3.1.2. Geometry of least squares
Target value 를 축으로 이루어진 -dimensional space를 생각해보자. 각각의 basis function으로 이루어진 vector 역시 같은 공간의 vector로 볼 수 있는데, 이라면 은 linear subspace 를 span할 것이다. 여기서 regression 는 의 arbitrary linear function이므로 $S$의 어떤 멤버이든 될 수 있다.
이 때 sum-of-squares error는 regression 와 target 의 Euclidean distance임에 유의하자. 이에 따라 least-squares solution은 subspace 에서 에 가장 가까운 vector 의 선택이다. 즉 쉽게(?) 말하자면 의 에 대한 orthogonal projection인 것이다.
3.1.3. Sequential learning
One-batch learning은 컴퓨터의 메모리를 엄청 잡아먹을 것이기 때문에 현실적으로 어려운 경우가 많다. 이를 해소하기 위해 sequential learning 혹은 online learning framework이 필요한데, 여기서는 SGD(Stochastic Gradient Descent)를 소개한다. 잘 알고 있는 대로 다음과 같이 batch마다 parameter를 업데이트한다.
3.1.4. Regularized least squares
또 이전에 maximum likelihood estimator의 over-fitting 현상을 해소하기 위해 regularization term을 더하는 방식에 대해 배웠었다. 즉 다음과 같은 error를 최소화함으로써 over-fitting을 어느 정도 해소할 수 있었다. 여기서 당연히 이다.
여기서 흔히 로 sum-of-squares error를 택할 수 있다. 이러한 regularization term을 weight decay라고도 하는데, parameter value를 매 update마다 (data에 의해 support되지 않는 한) 조금씩 0을 향해 decay하기 때문이다.
또 이러한 weight decay는 다음과 같은 closed form 일반해를 제공한다.
다음과 같은 general regularizer를 생각할 수도 있다.
인 경우가 바로 여태 보았던 quadratic regularization(weight decay)이며, 인 경우를 lasso라 하는데, 이 경우에는 weight가 sparse해지는 특성을 갖는다.
3.1.5. Multiple outputs
지금까지 single output linear model을 살펴보았는데, 사실 multiple output으로의 확장은 trivial하다. 똑같이 likelihood 구하고 gradient를 0으로 설정하면 다음과 같은 일반해를 얻는데,
어차피 linear combination parameter는 독립적으로 도출되고, pseudo-inverse 는 한 번만 구하면 된다.
3.2. The Bias-Variance Decomposition
이번 장에서 Bayesian view에서의 model complexity를 다룰 예정이지만, 그 전에 먼저 model complexity issue에 대한 frequentist view인 bias-variance trade-off에 대해 간단히 다룬다.
섹션 1.5.5에서 loss function에 기반한 decision making을 다룬 적이 있는데, 대표적인 loss function의 선택이 바로 squared loss function으로 이를 통한 optimal prediction은 conditional expectation으로 도출되었었다고 한다.
여기서 우리는 decision theory로부터 도출된 squared loss function과 maximum likelihood estimation으로부터 도출된 sum-of-squares error function을 구분할 필요가 있다(?).
먼저 섹션 1.5.5에서 보았듯 expected squared loss는 다음과 같이 표현할 수 있는데,
두 번째 term은 와는 무관한, intrinsic noise로부터 발생하는 loss이며, 따라서 optimization을 통해 달성 가능한 최소한의 loss이다. 첫 번재 term이 바로 와 관련된 term이며, 이를 최소화하는 solution을 찾는 것이 목적이 되겠다.
만약 parametric function 를 통해 를 모델링하는 데 있어 Bayesian approach를 취한다면 그 uncertainty는 posterior distribution 를 통해 표현된다. 하지만 frequentist approach를 취한다면 기본적으로 point estimation이 이루어지며, uncertainty는 다음과 같은 사고실험을 통해 도출된다.
만약 우리가 많은 수의 크기 인 데이터셋들을 보유하고 있다고 하자. 그 중 어떠한 데이터셋 에 대해 prediction function 를 얻을 수 있는데, 어떠한 알고리즘의 성능을 이러한 각기 다른 데이터셋들에 대한 결과의 ensemble로써 평가한다.
위 expected loss의 first term의 integrand를 생각해보자. 이를 average ensemble하는 것이다.
Integrand에서 를 더하고 뺀 후 expectation을 취하면, 다음과 같은 식을 얻는다.
첫 번째 term은 squared bias라 부를 수 있으며, prediction의 평균이 desired regression function으로부터 얼마나 벗어나있는지를 나타낸다. 두 번째 term은 variance라 부를 수 있으며, 각각의 데이터셋에 대한 solution이 그들의 평균으로부터 얼마나 분산되어있는지를 나타낸다.
따라서 expected loss는 다음과 같이 decomposition이 가능한데,
이러한 expected loss를 최소화하는 데 bias와 variance 사이에서 trade-off가 발생한다. 즉, 충분히 flexible하여 bias가 낮은 모델에 대해서는 variance가 높게 나타나는 경향성이 존재하고, 반대로 robust한 모델에 대해서는 bias가 높게 나타나는 경향성이 존재한다는 것이다. 이는 교재의 실험과 그래프들을 통해 좀 더 명확히 확인할 수 있다.
하지만 이러한 bias-variance decomposition은 현실적인 유용성이 떨어지는데, 실제 프로젝트에서 bias-variance를 확인하기 위해 데이터셋을 여러 개로 쪼개는 멍청한 짓은 하지 않을 것이기 때문이다.
3.3. Bayesian Linear Regression
앞서 살펴본 maximum likelihood estimation은 잘 알다시피 over-fitting 문제에 취약하다. 이에 따라 over-fitting 문제를 피하면서도 training data를 통해 model complexity를 조절할 수 있는 Bayesian approach를 다룬다.
3.3.1. Parameter distribution
먼저 model parameter 에 대한 prior distribution을 소개함으로써 linear model에 대한 Bayesian treatment의 포문을 연다. 이 때 는 알려져있다고 가정하자. 위에서 살펴보았듯 likelihood function Gaussian이었기 때문에, 그 conjugate 역시 Gaussian이 된다.
이제 likelihood에 prior를 곱한 후 completing the square 과정을 거쳐 posterior를 구할 수 있는데, 2장에서 알아낸 결과를 통해 어렵지 않게 추론해낼 수 있다.
이 때 posterior는 Gaussian이기 때문에 mean과 mode가 일치하고, 따라서 이다.
이제 계산상의 편의를 위해 이번 장의 나머지에서는 다음과 같은 특별한 형태의 prior를 다룬다. Zero-mean isotropic Gaussian이라고 한다.
이에 대한 posterior를 구하면 다음과 같다.
이 때 log of posterior를 에 대한 function으로 정리하면, 다음과 같다.
따라서 MAP solution은 quadratic regularization term을 더한 sum-of-squares error를 최소화하는 것과 동치이다. (단, .)
이러한 Bayesian treatment의 과정이 교재에 그림과 함께 직관적으로 설명되어 있으니, 참고하면 좋다.
3.3.2. Predictive Distribution
사실 대부분의 상황에서 우리는 의 값 자체에는 큰 관심이 없고, 에 대한 prediction에 대해서만 관심을 가지는 편이다. (딥러닝에 대해서는 디버깅을 할 때 의 값에도 관심을 가지기는 한다.) 이는 다음과 같은 predictive distribution으로 나타낼 수 있다. 여기서 는 training set의 target vector이며, 는 편의상 생략되었다.
Target variable의 conditional distribution 는 다음과 같이 주어졌었고,
posterior weight distribution 는 다음과 같이 주어졌었다.
따라서 predictive distribution은 두 Gaussian의 convolution이므로, 2장에서 도출한 내용을 통해 다음을 알아낼 수 있다.
여기서 variance 는 다음과 같이 주어진다.
위 variance의 첫 번째 term은 data의 noise에 기인하며, 두 번째 term이 parameter 에 대한 uncertainty에 기인한다.
교재의 그림에서 보이듯, 이러한 predictive uncertainty는 관측된 데이터의 근처에서 가장 작으며, 더 많은 데이터가 관측될수록 전반적으로 작아진다.
또한 만약 Gaussian과 같은 localized basis function을 사용한다면, basis function center와 멀리 떨어진 공간에 대해서는 위 variance의 두 번째 term의 영향력이 적어지고, 이에 따라 extrapolating 시에 over-confident한 경향을 가지게 된다고 한다. 이는 후에 다룰 Gaussian process를 통해 해결할 수 있다.
또한 위의 결과들은 precision 가 상수라는 가정 하에 도출된 것들인데, 만약 가 모두 unknown이라면 prior는 Gaussian-gamma가 되고, posterior는 Student's t-distribution이 된다고 한다.
3.3.3. Equivalent kernel
위에서 살펴본 다음과 같은, linear basis function model에 대한 posterior mean solution은 kernel method와 Gaussian process에 대한 포문을 열어주는 흥미로운 성질을 가진다.
이를 에 대입하면 다음의 결과를 얻는다.
즉, 에서의 predictive distribution의 mean은 training set의 target 의 linear combination으로 이루어진다. 따라서 이를 kernel function 를 통해 다음과 같이 표현할 수 있는데, 이러한 kernel function을 smoother matrix 혹은 equivalent kernel이라 부른다.
이 때 kernel은 안의 의 값에 의존적인데, 점 근처에 localize되어 있음을 알 수 있다. 따라서 으로 표현되는 predictive distribution의 mean은, 에 가까울수록 더 높은 값을 부여하는 weight에 의한 training target value $t$의 weighted combination으로 해석될 수 있다.
이러한 equivalent kernel의 역할에 대한 인사이트는 와 의 covariance가 또 한 번 보여주는데,
위 식을 통해 가까운 점들 사이의 predictive mean은 correlation이 높고, 멀리 떨어진 점들 사이의 predictive mean은 correlation이 낮음을 알 수 있다.
이렇게 linear regression을 kernel function의 형태로 reformulation하는 것은 다음과 같은 regression에 대한 또 다른 접근 방식을 제시한다. Basis function의 set을 도입하기보다는, 그와 동일한 역할을 하는 localized kernel function을 도입함으로써 새로운 input vector 에 대한 prediction을 수행할 수 있다는 것이다. 이는 6장에서 다룰 Gaussian process라는 프레임워크와 밀접한 연관성을 가진다.
또 왜인지 잘 이해하지는 못했지만, 가중치의 역할을 하는 이러한 kernel의 합이 1임을 알 수 있다고 한다. 하지만 kernel function은 음의 값도 취할 수 있기 때문에, 언제나 prediction이 training target value의 convex combination은 아니다.
마지막으로 이와 같은 equivalent kernel은 kernel function과 함께 공유하는 중요한 성질을 지니는데, 바로 에 대한 nonlinear function 의 inner product로 표현될 수 있다는 것이다.
이 때 이다.
3.4. Bayesian Model Comparison
이번 섹션에서는 Bayesian view에서의 model selection의 일반적인 방법론에 대해 다룬다. 이어지는 섹션 3.5에서는 이러한 model selection 방법론을 통해 regularization coefficient를 결정하는 방법을 다룬다.
곧 보겠지만(?), maximum likelihood의 over-fitting 문제는 point estimation을 수행하는 대신 model parameter에 대한 marginalization을 수행함으로써 해소할 수 있다. 이로써 별도의 validation set 없이 모델들을 비교할 수 있다고 한다.
이제 $L$개의 모델들의 set 를 비교한다고 하자. 가 주어진 상태에서 에 대한 distribution을 나타내는 경우도 있을 것이고, 의 joint distribution을 나타내는 경우도 있을 것이다. 어쨌거나 주어진 데이터가 이 중 하나의 모델로부터 생성되었다고 가정한다. 그러면 모델에 대한 uncertainty를 나타내는 prior 과 함께 다음과 같은 posterior를 구하고자 할 것이다.
이 때 prior은 서로 다른 모델들 사이에서의 preference를 나타낼 수 있다. 여기서 서로 다른 모델에 대한 prior은 모두 같다고 가정한다. 또 는 model evidence라 불리는데, 데이터를 통해 나타난 서로 다른 모델에 대한 preference라고 볼 수 있겠다. 이러한 model evidence는 marginal likelihood라고도 불리는데, parameter가 marginalized out된 model space에서의 likelihood function이라고 볼 수 있기 때문이다. 두 모델의 evidence의 비율 는 Bayes factor이라고 불리기도 한다.
위와 같은 posterior가 주어진다면, predictive distribution은 다음과 같이 나타낼 수 있다.
이는 model evidence를 가중치로 각 모델의 predictive distribution을 평균한 것이라고 볼 수 있다. 이러한 model average의 간단한 approximation 중 하나는 그냥 가장 probable한 model을 선택해버리는 것인데, 이것이 바로 model selection이다.
Parameter 에 의해 정의되는 모델에 대해서, model evidence는 다음과 같이 주어진다.
표집론의 관점에서 보면, 위와 같은 marginal likelihood는 parameter가 prior로부터 random sampling된 모델이 주어진 데이터를 형성할 확률이라고 볼 수 있다고 한다.
또한 distribution의 형태에 대한 단순한 가정을 통해 integral over parameter 의 approximation을 구해봄으로써 model evidence에 대한 몇 가지 인사이트를 얻어낼 수 있다. 요는 가 데이터에 대한 fit term과 model complexity에 대한 penalty term으로 factorize될 수 있다는 것이다. 즉 모델을 복잡하게 구성할수록 데이터에 대한 fit은 높아지겠지만, 이와 함께 model complexity 역시 늘어나게 됨으로써 그 효과가 상쇄(?)된다.
단적으로, 간단한 모델은 데이터에 제대로 fit 할 수 없지만, 복잡한 모델은 그 predictive probability를 너무 넓은 범위에 흩뜨려 (정답이 되는 것을 포함하여) 그 어떤 데이터에도 높은 probability를 부여하지 않는다. 이로써 자연스럽게 그 사이의, 적절한 complexity를 가진 모델을 선호하게 되는 것이다.
Bayesian model comparison은 암묵적으로 model set 중에 true distribution이 포함되어있다고 가정하는데, 이러한 가정 하에서 Bayesian model comparison은 "평균적으로" true distribution을 선호하는 모습을 보여준다. 예컨대 진짜 distribution 과 가짜 distribution 가 주어졌다고 하면, Bayes factor를 data set들의 distribution에 대한 평균은 다음과 같은 형태를 가지는데,
위는 Kullback-Leibler divergence라고 불리며, 두 distribution이 같을 때에만 0의 값을, 그렇지 않은 경우에는 양의 값을 가짐이 알려져있다. Bayes factor의 log가 양의 값을 가진다는 것은 분자가 분모보다 크다는 것을 의미하므로, 위의 정리가 성립한다.
이렇게 Bayesian framework를 통해 training data만을 통해 over-fitting을 피할 수 있음을 보였다. 하지만 아무리 이러한 Bayesian view라도 model form에 대한 가정을 해야 하고, 이 가정이 invalid 하다면 모든 결과가 쓰레기통행이므로 현실적으로는 validation set을 따로 두고 모델을 평가하는 것이 현명하다.
3.5. The Evidence Approximation
Linear basis function의 fully Bayesian treatment에서는 prior distribution에 noise 와 parameter variance 와 같은 hyperparameter를 도입하며 이들을 parameter 와 함께 marginalize함으로써 추론을 수행한다. 하지만 에 대한, 혹은 hypereparameter에 대한 marginalization은 해석적으로 해낼 수 있지만, 이들을 함께 marginalization해 버리는 것은 해석적으로 불가능하다. 그렇기 때문에 여기서는 먼저 에 대해 marginalization함으로써 얻어낸 marginal likelihood function을 극대화하는 hyperparameter의 값을 구하고, 이들을 해당 값으로 고정하는 방법을 고려한다.
먼저 predictive distribution은 다음과 같이 표현될 수 있다.
이 때 와 는 이미 이전에 계산해본 바 있다. 이 때 hyperparameter에 대한 posterior 가 특정 값 에 몰려 있다면, 그냥 해당 값들로 hyperparameter를 고정해버려도 나름 괜찮을 것이다.
이러한 는 prior가 flat하다는 가정 하에 marginal likelihood 를 극대화함으로써 얻는다. 이를 통해 validation 없이 hyperparameter value를 찾아낼 수 있다.
3.5.1. Evaluation of the evidence function
Marginal likelihood function 는 에 대한 marginalization을 통해 얻을 수 있다.
이러한 integration은 섹션 2.1에서 배운 conditional Gaussian distribution과 completing the square 과정을 통해 해낼 수 있다. 계산은 너무 복잡하여 생략하고, 결과적으로 marginal likelihood의 log를 다음과 같이 쓸 수 있다. 은 의 dimensionality, 는 regularized sum-of-squares error이다.
3.5.2. Maximizing the evidence function
생략
3.5.3. Effective number of parameters
생략
3.6. Limitations of Fixed Basis Functions
여태까지 살펴보았듯 linear model은 closed-form solution을 가짐과 동시에 Bayesian treatment가 analytically tractable하다는 편리한 성질을 가진다.
하지만 이러한 linear model은 basis function이 데이터와 무관하게 고정되고, curse of dimensionality에 취약하다는 치명적인 결점을 가진다. 이러한 결점으로 인해 보다 복잡한 support vector machine이나 neural network 같은 모델에 의존하게 된다.
그렇지만 현실 세계에서는 다음과 같은 두 가지 특성이 위와 같은 치명적인 결점을 조금은 완화해준다. 첫 번째는 데이터가 주로 특정한 nonlinear manifold 근처에 분포하여 실질적인 dimensionality는 훨씬 작다는 것이며, 두 번째는 target variable이 data manifold의 극히 일부 direction에만 영향을 받는다는 것이다.
E.O.D.