[DeepLearningBook] Chapter 5 : Machine Learning Basics

이 책 내용을 정리한 포스트입니다.

https://www.deeplearningbook.org/,

Ian Goodfellow and Yoshua Bengio and Aaron Courville, An MIT Press book

책 전체 목차

contents



딥러닝은 머신러닝의 일종으로, 딥러닝을 잘 이해하기 위해서는 머신러닝의 기본적인 원리를 이해하는 것이 좋다. 또한 이번 챕터에서는 후에 책에서 다루는 내용들에 기본적으로 적용되는 원리를 다루기도 한다.

아래는 이 장의 내용을 요약한 것이다.
우선 학습 알고리즘의 정의와 예시를 본다. Linear regression algorithm을 예시로 살펴보고, training data의 패턴에 fitting하는 함수를 만드는 것과 새로운 데이터의 에 학습된 패턴을 적용하는 것에 대해 알아본다. 대부분 머신러닝 알고리즘은 hyperparameter을 갖고있다. 하이퍼파라미터는 학습을 통해 정해지는 파라미터가 아닌, 사용자가 알고리즘 밖에서 지정해주는 값이다. 이를 어떻게 설정해야 하는지도 다룰 것이다.

머신러닝은 일종의 응용통계다. 따라서 통계학에서 사용되는 두가지 중요한 관점으로 다룬다. 하나는 frequentist estimator이고, 하나는 Bayesian inference다.
또한 머신러닝 알고리즘을 지도학습 supervised learning 과 비지도학습 unsupervised learning으로 구분해서 다룰 것이다. 그리고 stochastic gradient descent라고 불리는 최적화 알고리즘을 다루고, cost function, model, dataset 등의 요소들에 대해 다룬다. 마지막으로 머신러닝이 극복해야 할 점들을 서술함으로써 이 장을 마무리한다.

Learning Algorithms

머신러닝 알고리즘은 데이터로부터 학습하는 알고리즘이다. 그렇다면 학습이란 무엇인가?

“A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.”

Mitchell (1997)의 정의에 따르면, 프로그램이 학습을 한다는 것은, 경험 E로부터 학습을 하는데, task T라는 일을 하게 되고, 그것의 성능지표 P를 향상시키는 방향으로 발전한다는 것이다. 다음 섹션에서는 이 T, P, E 에 대해 좀더 직관적인 서술을 할 것이다.

The Task, T

머신러닝이 해결해야 할 문제를 의미한다. task 라는 용어 자체가 학습을 의미하는 것은 아니다. 예를 들면, 로봇이 걷게 만들때, 걷기라는 작업이 task가 된다. 이 task를 위해 학습을 시킬 수도 있고, 일일이 모터를 수동으로 제어하면서 걷게 만들 수도 있는 것이다. 머신러닝에서는 example이라고 불리는 feature들의 집합을 처리하여 task를 수행한다. task의 종류는 여러가지가 있다. 아래에서 몇가지를 살펴보자.

  • Classification: feature을 입력받아 해당 feature들이 어떤 카테고리(클래스, 종류, 레이블)에 속하는지 예측하는 task다. 입력 feature가 $\boldsymbol{x} \in \mathbb{R}^n$일때, 머신러닝 알고리즘은 $f: \mathbb{R} \rightarrow { 1,…,k}$ 함수를 찾는 과정이 된다. 즉 입력 feature $\boldsymbol{x}$를 카테고리 $y$에 맵핑시키는 $y = f(\boldsymbol{x})$를 하는 task다. 예를 들면, 이미지(feature $\boldsymbol{x}$)를 입력으로 받아 개,고양이,사람 등의 종류($y$)를 예측하는 문제가 classification에 해당된다.
  • Classification with missing inputs: Classification task인데, 입력 feature중 몇몇이 누락되어 있는 경우다. 입력 feature가 누락되어 있지 않으면 feature와 label사이에 하나의 함수만 찾아내면 되지만, 입력 feature가 누락되어 있다면 불완전한 feature에 대응하는 여러개의 함수를 찾아내야 한다. 이런 경우는 의료 데이터를 다룰 때 많이 발생한다. 많은 종류의 의료검진이 비싸거나 침습적이기 때문에, 모든 환자들이 같은 종류의 검사를 동일하게 진행하기 힘들다. 여러개의 함수를 효율적으로 정의하는 방법중 하나는 변수들 전체에 대해 확률분포를 학습하는 것이다. 그리고 누락된 입력은 무시하고 classification을 하는 것이다. 입력이 $n$개라면, $2^n$개의 classification 함수가 필요하지만, joint probability distribution을 이용하면 하나의 함수로 가능하다.
  • Regression: 입력 feature에 대해 수치를 예측하는 task다. 학습 알고리즘은 $f : \mathbb{R}^n \rightarrow \mathbb{R}$ 함수를 만들어낸다. class를 내뱉는 classification과는 달리, 수치 값을 내뱉는다. 예를 들면, 다른 feature들을 보고 집의 가격을 예측하거나, 사람의 키를 예측하는 등의 task다.
  • Transcription: 상대적으로 구조화되지 않은 데이터를 보고 textual form을 내뱉는 task다. 예를 들면, 이미지 속의 글자를 인식하여 텍스트로 출력하는 OCR (Optical Character Recognition)이나, 음향신호로부터 언어를 출력하는 음성인식 등이다.
  • Machine translation: 기계 번역이다. 어떤 언어의 시퀀스를 입력으로 받고, 다른 언어의 시퀀스로 내뱉는 task다.
  • Structured output: 출력이 벡터나 여러 값을 포함하는 자료구조인 task를 말한다. 일례로는 parsing 파싱이 있다. 자연어 문장을 입력으로 받아 tagging node와 함께 문법적인 구조의 트리에 맵핑하는 task다. 또 다른 예시로는 image segnmentation이 있다. 각각의 픽셀이 어떤 카테고리에 속하는지를 출력으로 내뱉는 task다.
  • Anomaly detection: 비정상적인 입력을 탐지해내는 task다. 예를 들면, 평소 사용내역과 다른 신용카드 내역을 잡아내어 사기를 방지하는 일에 쓰일 수 있다. Chandola et al. (2009) 논문에 anomaly detection 방법에 대한 서베이가 있다.
  • Synthesis and sampling: 학습 데이터와 유사한 새로운 데이터를 생성해내는 task다. 예를 들면 그럴듯한 이미지를 생성하여 지루하고 비용이 많이 드는 일을 대체하는 것이다. 또는 원하는 텍스트와 음성신호를 넣으면, 해당 음성으로 내가 원하는 텍스트를 읽어주는 신호를 만들어 낼 수 있다. Output은 하나로 정해져있는 것이 아니라, 그럴듯한 여러가지 output이 나올 수 있다.
  • Imputation of missing values: 입력 feature중에 누락된 값을 예측하는 task다.

  • Denoising: 입력으로 노이즈가 섞인 corrupted example $\boldsymbol{\tilde{x}} \in \mathbb{R}^n$를 받고, 노이즈가 제거된 clean example $\boldsymbol{x} \in \mathbb{R}^n$을 내뱉는 task다. 즉, 조건부 확률분포 $p(\boldsymbol{x} \vert \boldsymbol{\tilde{x}})$를 예측하는 것이다.

  • Density estimation or probability mass function estimation: Density estimation은 $p_{\text{model}} : \mathbb{R}^n \rightarrow \mathbb{R}$ 을 학습하여 데이터가 존재하는 공간에서의 probability density function(데이터가 연속) 또는 probability mass function(데이터가 불연속)를 나타낸다. 이 task를 잘 하기 위해서는 모델이 데이터가 존재하는 분포와 구조를 잘 파악해야 한다. 이렇게 학습된 모델은 다른 task를 위해서 사용될 수 있다. 예를 들면, feature $x_{i}$ 가 누락된 입력 $\boldsymbol{x}_{-i}$ 이 들어온 imputation of missing values의 경우, 누락된 값을 데이터 분포 로부터 찾을 수 있다. 실제로는 각각의 $i$에 대해 모든 분포를 다 찾기 힘들기 때문에 항상 유용한 것은 아니다.

이 외에도 많은 머신러닝 task가 존재한다.

The Performance Measure, P

머신러닝 알고리즘의 성능을 정량적으로 평가한다. 보통 각각의 성능 평가 $P$는 task $T$에 따라 정해진다.
classification, classification with missing inputs, transcription같은 task에 대해서는 accuracy라는 성능지표를 측정한다. Accuracy는 입력에 맞는 label, category, target 등등으로 불리우는 출력 정답을 얼마나 맞추는지에 대한 비율이다. 같은 성능을 error rate으로도 측정할 수 있다. 이는 얼마나 틀리는지에 대한 지표다. 정확히 분류하면 0, 틀리면 1을 부과하는 0-1 loss를 사용하기도 한다.
Density estimation 같은 task에서는, accuracy나 error rate같은 성능지표가 적절치 않다. 각각의 예시가 맞고 틀리고 처럼 0 또는 1로 나누어지는 것이 아니라, 연속된 값을 성능지표로 가져야 한다. 보통 log-probability를 사용한다.
이러한 성능을 측정할 때는, test set을 따로 지정하는데, 모델이 학습할 때는 주어지지 않은 데이터를 통해 성능을 측정해야 한다. task의 성능을 제대로 측정할 수 있는 성능지표를 선택하는 것도 때로는 어려울 수 있다. 특히 자연어처리 같은 경우, 각기 다른 특성의 다양한 성능지표가 있는데 모델마다 잘 나오는 성능지표가 다른 경우도 있다.

The Experience, E

머신러닝 알고리즘은 unsupervised 또는 supervised로 나뉠 수 있다. 나뉘는 기준은 학습과정동안 모델에게 주어지는 전체 dataset(data points)에서의 experience $E$의 종류다.

  • Unsupervised learning algorithms: dataset의 구조로부터 유용한 속성을 학습한다. 이를테면 데이터를 생성하거나 density estimation을 위한 데이터 전체의 확률분포를 학습한다던지, 유사한 데이터끼리 묶어주는 데이터 clustering을 수행한다.

  • Supervised learning algorithms: dataset에 feature들과 그에 해당되는 label, target, category(정답)가 있다. 모델은 feature을 입력으로 받아 각각의 정답을 내뱉는다. 이때 정답은 하나의 값일 수도, 여러개 값일수도 있고, 시퀀스 일 수도 있다.

Unsupervised learning은 데이터 $\boldsymbol{x}$를 받아 이들의 확률분포 $p(\boldsymbol{x})$를 학습하고, supervised learning은 $\boldsymbol{x}$에 해당되는 정답 $\boldsymbol{y}$를 맞추는 조건부 확률분포 $p(\boldsymbol{y}\mid\boldsymbol{x})$ 를 학습한다. $\boldsymbol{y}$가 일종의 instructor역할을 하기 때문에 supervised learning이라 한다.

그러나 unsupervised learning 과 supervised learning의 경계는 사실 엄밀하게 정의되어있지는 않다. 많은 머신러닝 기법이 두 task를 모두 수행할 수 있다.

예를 들면, $\boldsymbol{x} \in \mathbb{R}^n$ 에 대해 joint distribution은 위와 같이 decomposed될 수 있다. 여기서 좌변을 학습하는 unsupervised learning은 우변처럼 $n$개의 supervised learning으로 나누어서 해석될 수 있다.

반대로, 좌변의 supervised learning은 우변처럼 joint distribution $p(\boldsymbol{x},y)$를 학습하는 unsupervised learning으로 풀 수 있다.

이처럼 unsupervised learning과 supervised learning은 그 경계가 수식적으로 엄밀히 구분되어있지는 않지만, 직관적이고 대략적으로 머신러닝의 종류를 구분짓는 기준이 된다. 일반적으로 사람들은 regression, classification, structured output 문제를 supervised learning으로 구분하고, density estimation 같은 문제를 unsupervised learning으로 여긴다.

또 다른 종류도 있다. semi-supervised learning은 데이터-정답 쌍이 완전하지 않은 경우다. 즉, 어떤 데이터는 label이 있지만, 어떤 데이터에는 누락된 경우다. multi-instance learning은 데이터 뭉탱이(bag)에 포함되는 class들을 분류하지만, 뭉탱이속 각각의 데이터에는 정답 label이 없다.

Reinforcement learning은 고정된 dataset을 가지고 학습하지 않는다. 환경과 상호작용하면서, 반복되는 경험과 피드백을 통해 학습한다.

Example: Linear Regression

머신러닝 알고리즘이 돌아가는 것을 좀더 파악하기 위해 linear regression을 예시로 살펴본다. 이름에서 알 수 있듯, regression문제를 푸는 알고리즘이다. 입력으로 벡터 $\boldsymbol{x} \in \mathbb{R}^n$을 받아, 스칼라 $y \in \mathbb{R}$ 를 내뱉는다. linear regression의 출력은 입력의 linear function이며, 아래와같이 나타낼 수 있다.

$\boldsymbol{w} \in \mathbb{R}^n$ 는 모델의 파라미터다. 파라미터는 시스템의 행동을 조절한다. 이 경우에 $w_i$는 입력 $x_i$에 대한 계수로써 작용한다. 만약에 $w_i$가 작다면 출력에 대한 $x_i$의 영향은 적어질 것이고, $w_i$가 크다면 $x_i$의 영향은 커질 것이다. $w_i$가 0이라면 $x_i$는 영향을 전혀 미치지 못할 것이다.
위 task $T$를 정의하자면, $\boldsymbol{x}$를 입력으로 받아 출력 $\hat{y} = \boldsymbol{w}^\top\boldsymbol{x}$을 내뱉는 모델을 통해 $y$를 예측하는 것이다. 이제 성능을 측정할 $P$가 필요하다. 성능지표중 하나는 mean square error이고, 아래의 수식으로 정의된다.

MSE는 예측값과 정답의 Euclidean distance에 따라 증가한다. 이 성능지표를 향상시키기 위해 train 학습 데이터에서의 $\text{MSE}_\text{train}$값을 줄여야 한다. gradient descent방법을 사용한다.

마지막 수식은 normal equation으로 알려져있다. Gradient descent를 여러번 하지 않고 한번에 해를 구할 수 있는 반면, 역행렬을 구하는 연산에 따라 연산속도가 달라진다. 여기에 intercept $b$를 추가하면 아래와 같은 수식이 된다. $b$는 bias를 의미한다. 이때 bias는 통계적 편향을 의미하는 것이 아니라, 근사 함수에서의 y 절편, 상수항 정도로 생각하면 된다.

이때 bias $b$를 저렇게 둘 수도 있지만, $\boldsymbol{x}$ 에 1이라는 상수의 feature을 추가해주면 affine transformation의 형태로 나타낼 수 있다.

DBL-05-01

Capacity, Overfitting and Underfitting

이렇게 학습된 모델은 학습때 보지 못한 데이터에 대해서도 잘 적중해야 하는데, 이를 generalization이라 한다. 모델을 학습할 때, 학습 데이터에 대해 발생하는 에러를 training error라고 하고, 이를 줄여나가는 것이 학습이다. 학습 데이터에 포함되지 않은, 테스트 데이터에서 발생하는 에러를 generalization error, test error라고 한다.
위의 linear regression에서 사용했던 mean square error을 이용해서 training error을 표현하면, $\frac{1}{m^{(train)}} \Vert \boldsymbol{X}^{(train)}\boldsymbol{x} - \boldsymbol{y}^{(test)}\Vert_2^2$ 이고, test error는 $\frac{1}{m^{(test)}} \Vert \boldsymbol{X}^{(test)}\boldsymbol{x} - \boldsymbol{y}^{(test)}\Vert_2^2$으로 표현된다.

그렇다면 테스트 셋을 보지않고, 학습 데이터만 보고도 어떻게 테스트 셋에서의 성능을 향상 시킬 수 있을까? 그 답은 statistical learning theory에 있다. 데이터 셋들이 어떠한 확률분포를 갖는 data-generating process에 의해 생성 된다면, 데이터가 생성되고 수집되는 과정에 i.i.d. (independent identically distributed) assumptions을 한다. 즉, 수집된 각각의 데이터셋들은 매번 같은 분포로 생성되며, 서로의 생성에 영향을 미치지 않는다는 가정이다. test set과 train set이 같은 data-generating distribution $p_{data}$를 따른다는 것이다. 고정된 파라미터와 데이터 분포에서는 train error와 test error가 같을 것으로 예측된다.
그러나 학습할 때는 학습 파라미터와 데이터 분포가 고정이 아니기 때문에, test error은 대개 train error 보다 크거나 같다. 머신러닝 알고리즘이 잘 작동하게 하려면 두가지를 잘하면 된다.

  1. training error을 작게 만든다.
  2. test error와 training error의 차이를 작게 만든다.

위 두가지 이슈에 대해 underfittingoverfitting이라는 문제점이 발생할 수 있다. underfitting은 training error를 줄이지 못한 경우고, overfitting은 training error은 줄였으나 그에 비해 test error가 너무 큰 경우다. 이를 모델 capacity로도 설명할 수 있다. 모델 용량이 너무 작은 경우는 train data의 패턴에 근사하지 못해 underfitting이 일어나고, 모델 용량이 너무 큰 경우엔 train data의 속성을 기억해서 test data에는 제대로 작동하지 않는 overfitting이 일어난다. 모델의 capacity를 제어하는 방법중 하나는 hypothesis space를 선택하는 것이다. 예를 들면, linear regression 알고리즘은 모든 input에 대한 각각의 linear function들의 집합으로 이루어져 있으며, 각각의 가설공간을 갖는다. 우리는 이를 linear function에서 polynomial로 확장함으로써 모델의 용량을 늘릴 수 있다.
1차 polynomial은 이미 많이 다루어온 식으로, 아래와 같다.

$x^2$항을 추가함으로써 모델은 $x$에 대한 quadratic function으로 근사한다.

$x$에 대해서는 모델이 quadratic으로 작동하지만, parameter관점에서는 여전히 linear function이므로, 위에서 다룬 normal equation을 사용할 수 있다. 원하는 차수까지 넣어가며 capacity를 조절할 수 있다. 예를 들면 9차항까지 추가된 수식은 아래와 같다.

머신러닝은 모델의 capacity가 해당 task의 complecxity에 적절할 때 성능이 가장 좋다. 위에서 말한 것처럼 너무 과하면 overfitting, 부족하면 underfitting이 발생한다. 아래 그림에 각각의 상황이 묘사되어있다.

DBL-05-02

위에서 모델 capacity를 조절하는 한가지 방법을 다루었다. feature 차수를 늘리고(줄이고), 그에 해당하는 parameter를 추가하는(빼는) 방법이었다. 이렇게 모델을 선택하는 방법 외에도, 모델 capacity를 조절하는 방법이 있는데, 그 중 하나가 모델에서 사용하는 함수를 변경해서 representational capacity를 조절하는 방법이다. 그러나 실제로는 최적의 함수를 찾는 것은 매우 힘들고, 여러 함수 중 효과적인 하나를 찾아서 적용한다.

머신러닝의 generalization 성능을 향상시키고자 할 때, 주요한 원칙 중 하나는 Occam’s razor이다. 여러 복잡한 가정과 제한을 두는 것보다, 다른 것들을 커버하는 (data를 잘 설명하는) 가장 단순한 하나의 가정이나 제한을 선택하라는 원칙이다. Statistical learning theory에는 모델의 capacity를 정량화하는 여러가지 방법이 있는데, 그 중 잘 알려진 것이 Vapnik-Chervonenkis dimension (VC dimension)이다. VC dimension은 binary classifier의 capacity를 측정한다. 이를 좀더 설명하기 위해서는 dichotomyshattering이란 개념에 대해 먼저 다루어야 한다. Dichotomy란 어떤 집합을 두가지 label로 나누는 것을 의미한다. 즉, {a,b,c,d} 이렇게 네개의 데이터 포인트가 있다면, {a}{b,c,d} 또는 {a,c}{b,d} 이런식으로 나누는 것을 의미한다. 물론 {}{a,b,c,d} 나 {a,b,c,d}{}으로 나누는 것도 포함된다. 가능한 경우의 수는 총 $2^4 = 16$가지다. Shattering은 이렇게 나누어진 데이터 포인트들을 binary classification을 할 수 있는 지에 대한 것이다. VC dimension은 모델이 shattering 할 수 있는 차원이다. 다시말해, 모델에 의해 shattered 될 수 있는 데이터 포인트의 최대 갯수가 VC dimension이다. 일반적으로 N차원의 hyperplane의 VC dimension은 N+1이라고 알려져있지만, margin을 허용하는 SVM같은 모델은 shattering할 data point를 줄여 VC dimension을 낮추는 효과를 가져온다. 이처럼 capacity의 정량화는 모델에 대한 여러 해석을 가능케 하지만, 딥러닝 알고리즘에 대해서는 대체로 사용하기 힘들다. 왜냐하면 아직까지는 딥러닝같은 general nonconvex optimization에 대한 이론적인 이해가 부족하기 때문이다.
Occam’s razor에서 다루었듯이, training error과 test error간의 차이(generalization gap)를 줄이기 위해서 가급적이면 단순한 모델을 사용해야 하지만, 일반적으로는 training error를 줄이는 방향으로 모델을 만들기 때문에, 모델 capacity가 증가한다. 그에 따라서 generalization gap 또한 증가한다. 아래 그림에 이에 대한 내용이 있다.

DBL-05-03

지금까지 다룬 linear regression같은 내용들은 parametric model이었다. parametric model이란 관측되는 데이터에 의해 결정되는, 유한한 갯수의 파라미터들을 학습하여 함수를 근사하는 모델이다. 그러나 극단적으로 높은 capacity의 모델을 다루기 위해 nonparametric model의 개념을 소개한다. 가끔 nonparametric model은 현실적으로 구현 불가능한, 이론적인 모델로 여겨진다. 예를 들면, 가능한 모든 확률분포를 모두 계산하여 탐색하는 알고리즘처럼 말이다. 그러나 우리는 복잡도를 training set 크기의 함수로 만듦으로써, 현실적인 nonparametric model을 만들 수 있다. 그중 하나의 예가 nearest neighbor regression이다. 고정된 길이의 학습 파라미터 벡터를 가진 linear regression과는 달리, nearest neighbor regression 모델은 그저 training set으로부터 $\boldsymbol{X}$와 $\boldsymbol{y}$를 저장해둔다. 그리고 test data point $\boldsymbol{x}$가 들어오면, 저장해둔 training set중 가장 유사한 케이스를 내뱉는다. 이때 유사하다는 것은 $L^2$ norm이나 다른 distance metric을 사용할 수 있다. 가장 유사한 training data point의 $y$값을 내뱉어도 되지만, 꽤 유사한 data들의 $y$ 값들을 평균내어 내뱉음으로써 오차를 줄일 수도 있다.

이상적인 모델은 데이터가 생성되는 진짜 확률 분포를 알고 있는 오라클이라고 볼 수 있다. 그러나 많은 경우, 여전히 확률분포에 노이즈가 있을 수 있다. supervised learning의 경우에, 데이터 $\boldsymbol{x}$에 label $y$가 항상 매칭될 수도(deteministic), 아닐 수도(stochastic) 있다. 이처럼 true distribution $p(\boldsymbol{x},y)$에서도 발생하는 에러를 Bayes error라고 한다. training error와 generalization error는 trianing set의 크기에 따라 변한다. 학습 데이터를 많이 모을 수록 generalization error는 줄어들 수 있다. optimal capacity에 못미치는 parametric model은 Bayes error에 못미친다. optimal capacity라고 하더라도, 여전히 training error와 generalization error사이에는 차이가 존재한다. 이런 상황에서는 학습데이터를 더 모아서 차이를 줄여야 한다.

The No Free Lunch Theorem

일명 공짜 점심은 없다로 불리우는 이론은 비단 머신러닝에서만 있는 것은 아니다. 여러 분야에서 비용 또는 대가에 대한 내용으로 많이 다루어진다. 머신러닝에서는, 한정적인 데이터를 학습해서는 잘 할 수 있지만, 모든 데이터 distribution에 대해서 universally 잘 하는 머신러닝 모델은 없다는 것을 의미한다. 즉, 만능 AI는 없다 정도로 이해할 수 있다. 그러나 우리가 원하는 specific task에 특화된 (제한된) 모델을 만드는 것은 가능하므로, 이에 초점을 맞추어 개발해야 한다.

Regularization

공짜 점심은 없다의 내용대로, 만능 AI보다는 특정 task에 특화된 모델을 개발하는 것이 좋다. 여태까지 모델을 수정하는 방법으로 다루었던 것은, 입력 feature 차수를 조절하거나 함수를 더하고 빼서 capacity를 조절하는 방법이었다. 그러나 알고리즘에 강하게 영향을 끼치는 것은 함수들이 얼마나 많이 적용되느냐가 아니라, 함수 그 자체의 속성이다. 우리가 위에서 보았던 linear regression은 각각의 입력에 대해 선형함수를 적용하여 출력을 뽑아내는 방식이었는데, 이는 nonlinear 영역에서는 잘 작동하지 않는다. 예를 들면, linear regression 알고리즘을 이용하여 $\boldsymbol{x}$로부터 $\sin (\boldsymbol{x})$를 예측하는 것은 힘들다. 따라서 우리는 함수의 갯수 뿐만 아니라 종류도 적절히 선택하여 함수의 가설공간을 제어할 수 있다.
예를 들어, 기존의 가설공간에 또다른 종류의 솔루션을 더하여 제어할 수 있다. 두가지 모두 적용되지만, 상황에 따라 둘 중 하나가 강하게 영향을 미친다. linear regression에서 사용하던 기존의 trianing criterion MSE에 새로운 솔루션 weight decay를 더하면 우리가 최소화 해야 하는 함수는 아래와 같다.

기존의 MSE와 모델의 parameter weight의 $L^2$ norm을 둘다 줄이게 된다. 만약 $\lambda$가 0이면 아무런 영향도 없지만, $\lambda$가 커질수록 weight의 크기는 작아진다. $J(\boldsymbol{w})$를 최소화 하는 것은 weight의 크기를 작게 하거나 training error를 줄이는 것이다. weight decay를 이용해서 모델의 underfit, overfit 경향을 조절할 수 있다. 아래 그림은 차수 9인 linear regression의 모델을 weight decay의 $\lambda$를 조절하여 마치 복잡도를 제어하는 것 같은 효과를 나타낸다. weight가 작을 수록 모델은 단순해진다.

DBL-05-04

이처럼 모델에 regularizer를 추가하여 제어할 수 있다. 위의 예시에서는 regularizer가 $\boldsymbol{\Omega} (\boldsymbol{w}) = \boldsymbol{w}^\top \boldsymbol{w}$ 로 정의되어있다. 이처럼 weight를 explicit하게 제어할 수도 있고, 다른 방법으로는 implicit하게도 제어할 수도 있다. Chapter 7에서는 더 많은 종류의 regularizer를 살펴본다. Regularization은 흔히 training error보다는 generalization error를 줄이려는 목적으로 쓰인다. 위의 공짜 점심은 없다에서 보았던 것 처럼 모델을 좀더 제한적으로 만들어서 원하는 task에서는 성능을 높이는 역할을 한다.

Hyperparameters and Validation Sets

대부분의 머신러닝 알고리즘은 하이퍼파라미터를 갖고 있다. 모델이 학습하는 파라미터가 아닌, 사용자가 설정해주는 값들이다. 그림 5.2에서 보았던 polynomial regression에서는 입력 feature의 차수가 하이퍼파라미터였고, weight decay에서는 $\lambda$가 하이퍼파라미터였다. 최근에는 하이퍼 파라미터들을 최적으로 셋팅해주는 모델도 나오고 있긴 하지만, 하이퍼파라미터의 종류가 복잡해지고 많아지면 적절한 값을 선택하는 것은 아직 어려운 문제일 때가 많다. 이럴땐 하이퍼파라미터를 조절해가면서 테스트해보는데, test set이 아닌 training set의 일부를 validation set으로 놓고 사용한다. validation set은 학습때 사용하지 않는다. 일반적으로 training set의 80%를 모델 학습에 사용하고, 20%를 validation set으로 사용한다.
현실적으로는 학계에서 흔히 쓰이는 dataset들도 오랜시간 쓰이다 보면, test set에 과적합되어 실제 필드의 데이터에는 적합하지 않을 수 있다. 다행히도 벤치마킹할 새로운 데이터셋들이 계속 나오고 있다.

Cross-Validation

전체 데이터를 (validataion set 포함) training set, test set으로 나누어 알고리즘을 평가하는데, test set의 크기가 충분치 않은 경우는 통계적인 불확실성 때문에 모델을 평가하기엔 부족하다. 즉, 작은 데이터셋으로는 이 모델, 알고리즘이 비슷한 데이터에서 잘 작동한다고 말하기 어려운 것이다. 그래서 dataset을 랜덤하게 뭉탱이로 여러번 나누어 알고리즘을 반복 평가한다. 그 중 흔히 쓰이는 방법은 $k$-fold cross-validation이다. dataset을 서로 겹치지 않게 $k$개의 뭉탱이로 나누고, 총 $k$번의 평가를 하는데, 각각 첫번째부터 $k$번째까지의 뭉탱이를 돌아가며 test set으로 사용한다.

Monte-Carlo Cross Validation

Monte-Carlo Cross Validation는 training set 중 일정 비율로 validation set을 랜덤하게 뽑아 테스트한다. 이를 여러번 반복하여 수행하는데, 같은 데이터가 여러번 validation set에 등장할 수 있다는 것이 $k$-fold cross validation과의 가장 큰 차이점이다.

Estimators, Bias and Variance

통계학으로부터 머신러닝을 위한 많은 도구를 갖다 쓸 수 있다. trainig 뿐만 아니라, generalization을 위한 해석이나 제어를 하기 위한 parameter estimation, bias, variance같은 개념들이 있다.

Point Estimation

Point estimation은 단 하나의 “best” 예측을 뽑기 위한 방법이다. 대상은 하나의 파라미터일 수도 있고, linear regression 예시처럼 벡터 파라미터일 수도 있다. 예측과 참값을 구분하기 위해서 예측은 $\boldsymbol{\hat{\theta}}$로 표기하고, 참값은 $\boldsymbol{\theta}$로 표기한다. i.i.d를 따르는 데이터 에 대한 point estimator는 이에 대한 함수로 볼 수 있다. 즉, 아래와 같이 정의된다.

$\boldsymbol{\hat{\theta}}$가 true $\boldsymbol{\theta}$에 가까울 수록 좋은 estimator이다. 입력과 target variable간의 관계를 추정하는 point estimation을 function estimaton이라고 부른다.

Function Estimation

입력 벡터 $\boldsymbol{x}$에 대한 변수 $\boldsymbol{y}$를 예측하는 경우가 있다. 이 때, $\boldsymbol{y}$와 $\boldsymbol{x}$간의 관계를 나타내는 $f(\boldsymbol{x})$를 찾는 것이 function estimation이다. 예를 들면, $\boldsymbol{y} = f(\boldsymbol{x}) + \boldsymbol{\epsilon}$ 같은 수식으로 관계를 근사할 수 있다. 이 때 $\boldsymbol{\epsilon}$은 $\boldsymbol{x}$로부터 예측할 수 없는 값이다. 함수 $f$를 근사한 $\hat{f}$를 얻는다. function estimation은 함수공간에서의 point estimation과 같다. 또한 파라미터 $\boldsymbol{\theta}$를 찾는 것과도 같다. 위의 linear regression에서 $\boldsymbol{w}$를 구한 것과 polynomial regression을 했던 것도 function estimation이다.

Bias

Estimator의 bias는 아래와같이 정의된다.

data들로부터 추정한 의 기댓값과 true 와의 차이다. bias가 0이면 unbiased 되어있다고 하고, 을 의미한다. data의 갯수가 무한대로 많아질때 unbiased하다면 asymptotically unbiased하다고 표현하고, 를 의미한다.

Example: Bernoulli Distribution

데이터 샘플 이 i.i.d. 조건의 평균 $\theta$ 베르누이 분포를 따른다고 가정하자.

일반적인 $\theta$ parameter estimator는 데이터들을 평균 내는 것이다.

biased 되어있는지 아닌지 보려면, 위에서 보았던 bias에 관한 수식에 대입해보면 된다.

$\text{bias}(\hat{\theta}) =0$이므로, 평균을 사용한 esimator $\hat{\theta}$는 unbiased 되어있다.

Example: Gaussian Distribution Estimator of the Mean

데이터 샘플 이 i.i.d. 조건의 가우시안 분포 $\mathcal{N}(x^{(i)};\mu,\sigma^2)$ 를 따른다고 가정하자.

가우시안 mean parameter을 구하는 일반적인 estimator은 sample mean이다.

이를 이용해 수식을 전개하면 아래와 같다.

sample mean을 이용한 Gaussian mean paremeter estimator 또한 unbiased되어 있음을 알 수 있다.

Example: Estimators of the Variance of a Gaussian Distribution

이번에는 가우시안 분포에서 variance parameter $\sigma^2$의 estimator 두가지를 bias측면에서 비교해본다.

첫번째 estimator는 sample variance다.

여기서 $\hat{\mu}_m$는 위에서 봤던 sample mean이다.

따라서 sample variance estimator는 biased 되어있다.

Unbiased variance estimator는 아래와 같다.

이를 이용해 bias 식을 전개하면 아래와 같다.

따라서 $\tilde{\sigma}_m^2 = \frac{1}{m-1} \underset{i=1}{\overset{m}{\sum}} (x^{(i)}-\hat{\mu}_m)^2$ 는 unbiased variance estimator이다.

이렇게 두가지 종류의 variance estimator를 봤는데, 하나는 biased estimator $\hat{\sigma}^2$ 이고, 다른 하나는 unbiased estimator $\tilde{\sigma}^2$ 이었다. unbiased estimator가 true parameter를 나타내기 때문에 깔끔하지만, 항상 최고의 estimator인것은 아니다. 간혹 biased estimator가 갖는 주요한 속성때문에 사용되는 경우도 있다.

Variance and Standard Error

Estimator의 또다른 특성은 variance다. 우리가 추산하는 값이 데이터 샘플마다 얼마나 크게 달라지는지에 대한 지표다. 위에서 bias를 계산한것 처럼 variance를 계산할 수 있다. 우선 estimator의 variance는 아래와 같이 표기한다.

그리고 variance 의 square root를 standard error라고 부르며, $\text{SE}(\hat{\theta})$ 로 표기한다. 낮은 bias와 낮은 variance를 가지는 estimator가 대체로 우리가 원하는 estimator다. 유한한 데이터로 통계적인 수치를 계산할 때는, 항상 불확실성을 내포하고 있다. 즉, 같은 distribution을 통해 얻은 데이터들이라고 할지라도, 그들의 통계치는 달라질 수 있다는 뜻이다. 그 달라지는 정도를 계산하여 정량화 하는 것이다. 평균의 standard error는 아래의 수식으로 정의된다.

$\sigma^2$는 $x^i$ 들의 variance다. standard error는 보통 $\sigma$를 이용해서도 계산된다. 그러나 위에서 보았던 biased 된 sample variance $\hat{\sigma}^2$와 unbiased variance $\tilde{\sigma}^2$ 둘중 어떤걸 이용해도 unbiased 된 standard deviation estimate를 얻을 수 없다. 두가지 모두 standard deviation을 underestimate 하게 만들긴 하지만, 실제적으로는 여전히 사용되고 있다. 그나마 unbiased variance $\tilde{\sigma}^2$ 는 좀 덜하다. 데이터 수 $m$이 커질수록 근사가 합당해진다.

머신러닝에서는 평균의 standard error가 유용하게 사용된다. 주로 generalization error를 추정할 때 test set에서 error의 sample mean을 계산한다. 평균이 normal distribution 으로 근사한다는 중심극한정리에 따라, 우리는 standard error를 이용하여 true expectation이 신뢰구간에 떨어질 확률을 구할 수 있다. 예를 들어, 평균 $\hat{\mu}_m$의 95퍼센트 신뢰구간은 아래와 같다.

머신러닝 실험에서, 알고리즘 A의 error에 대한 95퍼센트 신뢰구간의 upper bound가 알고리즘 B의 error에 대한 95퍼센트 신뢰구간의 lower bound보다 작다면 알고리즘 A가 더 낫다고 할 수 있다.

Example: Bernoulli Distribution

Bias를 계산했을 때 처럼, 데이터 샘플 이 i.i.d. 조건의 평균 $\theta$ 베르누이 분포를 따른다고 가정하자.

일반적인 $\theta$ parameter estimator는 데이터들을 평균 내는 것이다.

이번엔 이 $\hat{\theta}_m$ 의 variance를 계산해보자.

데이터 수 $m$ 이 증가할수록 estimator의 variance는 작아진다.

Trading off Bias and Variance to Minimize Mean Squared Error

Bias와 variance는 estimator error의 서로 다른 원인이다. Bias는 함수나 파라미터의 참 값에서 예상되는 편차를 측정한다. 반면 variance는, 데이터 샘플링으로 인해 발생할 가능성이 있는 예측치 값과의 편차를 나타낸다.

보통 bias 와 variance는 아래 그림처럼 trade-off 관계에 있다. 이 때 적절한 모델을 선택하는 방법은 cross-validation을 이용하여 bias와 variance의 변화를 보는 것이다. 실험적으로 cross-validation은 실제 테스크에서 매우 성공적으로 사용되어왔다. 또한, mean square error(MSE)를 비교하여 사용할 수도 있다.

MSE는 estimator와 true parameter $\theta$ 간의 전체적인 편차를 측정한다. bias와 variance의 관계는 머신러닝의 capacity, underfitting, overfitting 의 개념과도 매우 밀접한 연관이 있다. MSE로 측정한 generalization error를 보면, 모델의 capacity가 증가하면 bias는 줄어들고 variance는 증가한다. 아래 그림에서도 확인할 수 있다.

DBL-05-05

Consistency

지금까지는 고정된 크기의 training set에 대한 다양한 estimator의 특성에 대해 다루었다. 일반적으로 training set이 증가하면, 우리의 point estimates도 참값에 수렴할 것으로 기대한다. 수식적으로는 아래와 같이 나타낸다.

$m \rightarrow \infty$에 따라 모든 $\epsilon >0$에 대해, $P(\vert \hat{\theta}_m - \theta \vert > \epsilon ) \rightarrow 0 $임을 의미한다. 이러한 조건을 consistency라고 한다. 이는 weak consistency로 분류되기도 하는데, strong consistency는 alomost sure convergence다. alomost sure convergence는 sequence random variables $\boldsymbol{\text{x}^{(1)},\text{x}^{(2)},}…$와 target value $\boldsymbol{x}$에 대해 $p(\lim _{m\to\infty}\boldsymbol{\text{x}^{(m)}} = \boldsymbol{x}) = 1$ 임을 의미한다.

Consistency는 데이터 수가 증가하면, estimator의 bias가 줄어든다는 것을 보장해준다. 그러나 역은 항상 성립하는 것은 아니다. 즉, estimator의 bias가 줄어든다고 해서 consistency가 성립하는 것은 아니다. 예를 들어, dataset 에서의 normal distribution $\mathcal{N}(x;\mu,\sigma^2)$의 평균 $\mu$의 추정을 생각해보자. 우리는 첫번째 sample $x^{(1)}$ 을 unbiased estimator로 사용할 수 있다: $\hat{\theta}=x^{(1)}$. 이 경우엔 $\mathbb{E}(\hat{\theta}_m) = \theta$ 이고, 데이터들을 얼마나 보느냐에 상관 없이 estimator가 unbiased 되어있다. 이런 경우는 $m \to \infty$에 따른 $\hat{\theta}_m\to\theta$가 아니기 때문에 consistency가 성립하는 것은 아니다.

Maximum Likelihood Estimation

위에서는 일반적인 estimator의 정의와 특성들에 대해 살펴보았다. 그러나 estimator는 어디서 오는가? estimator를 bias와 variance를 통해 분석하는 대신, 우리는 이제 각기 다른 모델을 위해서 좋은 estimator를 위한 특정 function을 뽑아내는 원리에 대해 다룰 것이다.

가장 일반적인 원리는 maximum likelihood 원리다. data set 이 독립적으로 unknown data-generating distribution $p_{data}(\boldsymbol{\text{x}}$로부터 생성되었다고 하자. $p_{model}(\boldsymbol{\text{x}};\boldsymbol{\theta})$는 $\boldsymbol{\theta}$ 공간상의 확률분포다. 즉, $p_{model}(\boldsymbol{\text{x}};\boldsymbol{\theta})$는 $\boldsymbol{x}$를 $p_{data}(\boldsymbol{x})$로 맵핑하는 것이다.

$\boldsymbol{\theta}$의 maximum likelihood estimator는 아래와같이 정의된다.

이렇게 여러 텀의 곱으로 나타내는 것은 underflow등 여러 이유로 불편할 수 있다. 따라서 로그를 취함으로써 최적화하는 대상은 유지하되, argmax 결과에 영향을 주지 않으면서 곱을 합으로 바꾼다.

argmax 는 cost function을 rescaling하더라도 결과가 같다. 이를 이용하여 위 식을 $m$으로 나누어주면, 데이터 샘플링된 empirical distribution $\hat{p}_{data}$ 를 따르는 expectation의 식으로 바뀐다.

DBL-05-06

data-generating process에 의한 distribution 와 empirical distribution 에 대해 좀더 이야기해보자. 위에서 그려진 Gaussian distribution을 data-generating process에 의한 distribution $p_{data}$ 라고 가정하고, x축에 그려진 빨간 점들을 training data points 라고 보자. $p_{data}$는 실제 상황에서는 unknown이다. 그렇기 때문에 data(빨간 점)들로부터 distribution을 뽑아내어 empirical distirbution 를 만드는 것이다. (이때 class가 여러개라면 Gaussian 분포가 여러개인 것이고, 입력 feature가 여러개라면 가 스칼라가 아닌 벡터로 표현될 것이다.) 따라서 위에서 maximum likelihood를 $\frac{1}{m}$으로 rescale하는 것은 data sampling을 할 때 data generating process만을 따른다는 가정이 있는 것이다. 즉, 샘플링 과정에서 무언가 data generating process를 따르지 않는 편중은 고려하지 않는다. 그러나 현실 data에서는 데이터 편중이 있으므로, 이에 대한 보정이 필요하다.
예시를 들어 설명하면, 흑백 펭귄 사진에서 펭귄의 색(픽셀들의 평균값)을 $\boldsymbol{x}$라고 두고, 황제펭귄의 깃털색이 위의 가우시안 분포 $p_{data}$ 를 따르는 것이다. training data images 에서 황제펭귄들의 평균 깃털색은 빨간 점들로 표현된다. 황제펭귄들은 유독 검정색일수도, 하얀색일수도 있지만 대체로 를 따를 것으로 가정하기 때문에 empirical distribution 를 사용하는 것이다. 그러나 만약 data sampling 과정에서 유독 까만 펭귄만 많이 얻는다면 그에 의한 empirical distribution 의 편중이 생길 것이다. 수식을 전개할 때는 이에 대한 편중을 고려하지 않지만, 실제로 데이터를 얻을 때는 다양한 이유에서 편중이 생길 수 있다.

DBL-05-07 귀여운 펭귄

maximum likelihood estimation을 사용하는 방법중 하나는 model이 training set으로부터 학습한 distribution을 empirical distribution와 유사하도록 만드는 것이다. 두 확률분포간 dissimilarity를 측정하는 지표중 하나는 KL divergence다. KL divergence는 아래와 같이 주어진다.

우변의 좌항은 모델에 의존적인 것이 아니라 data-generating process에 따라 달라지는 것이니, 결국 모델에서 최소화 해야 할 텀은 아래와 같다. 그리고 이는 maximum likelihood 를 최대화 하는 것과 같다.

KL divergence를 최소화 하는 것은 정확히 두 distribution간의 cross-entropy를 최소화 하는 것과 같다. 많은 저자들이 “cross-entropy” 라는 용어를 Bernoulli의 negative log-likelihood 나 softmax distribution으로 사용하지만, 이는 잘못된 용어사용이다. NLL로 구성된 모든 loss는 model이 내뱉는 distribution과 training set을 통해 정의되는 empirical distribution간의 cross-entropy다. 예를 들면, mean square error 또한 empirical distribution과 Gaussian model의 distribution간의 cross-entropy다. Maximum likelihood를 model의 distribution을 empirical distribution $\hat{p}_{data}$ 에 맞춰가는 과정으로도 볼 수 있다.

Conditional Log-Likelihood and Mean Squared Error

Maximum likelihood estimator를 일반화하면 conditional probability $P(\boldsymbol{\text{y}}\mid \boldsymbol{\text{x}};\boldsymbol{\theta})$의 추정으로도 볼 수 있다. 이 때, $\boldsymbol{\text{y}}$는 $\boldsymbol{\text{x}}$의 target 값이다.

위에서와 마찬가지로 i.i.d. 조건으로 본다면 아래와같이 decomposition된다.

Example: Linear Regression as Maximum Likelihood

Linear regression 또한 maximum likelihood로 정의될 수 있다. 모델의 distribution을 conditional distribution $p(y\mid \boldsymbol{x})$ 로 본다. 이 때 무한한 데이터들 중 우리가 볼 수 있는것은 한정된 데이터 셋이다. 그러므로 같은 $x$값에 여러 $y$가 맵핑되는 데이터에 대해 어떻게 처리할지가 관건이다. 이전에 봤던 linear regression과 같게끔 만들기 위해 $p(y\mid \boldsymbol{x}) = \mathcal{N}(y;\hat{y}(\boldsymbol{x};\boldsymbol{w}),\sigma^2)$ 으로 정의한다. 함수 $\hat{y}(\boldsymbol{x};\boldsymbol{w})$는 가우시안의 평균을 예측하는 것을 의미한다. 이 예시에서 $\sigma^2$는 사용자가 정해주는 고정값이다. $\boldsymbol{w}$가 결국 모델의 파라미터로써, 모델이 가우시안의 평균을 예측하게끔 만드는 것이다. 수식을 전개하면 아래와 같다.

위 식에서 $m$과 $\sigma$는 모델 파라미터와 무관하고, 결국 $\boldsymbol{w}$를 최적화 하는 텀은 이전에 봤던 MSE의 loss와 같다.

MSE와 MLE 두개의 값은 다르지만 결국 최적화하고자 하는 모델 파라미터의 위치는 같다.

Properties of Maximum Likelihood

Maximum likelihood 의 가장 주요한 특징은 데이터의 수 $m$이 늘어나면 늘어날수록, best estimator에 가까워진다는 것이다. MLE의 특성을 좀 더 나누어 설명하자면 consistency와 efficiency 다.

  • Consistency : 학습 데이터의 수가 무한대로 늘어나면, MLE는 true parameter 값에 수렴한다. 어떤 것이 data-generating process에 의한 true $\boldsymbol{\theta}$인지는 모르지만, MLE가 추정하는 $\boldsymbol{\theta}$ 중에 true parameter가 있다.
  • Statistical efficiency : MLE 이외에도 consistent한 방법들이 있다. 그러나 다른 방법들과는 달리 MLE는 statistical efficient하다. Statistical efficiency란, 한정된 데이터에서 더 낮은 generalization error를 갖는 것을 의미한다. 즉, 더 작은 데이터로도 동일한 테스트 성능을 낼 수 있다는 말과도 같다. Cramér-Rao lower bound (Rao, 1945; Cramér, 1946)에서, MLE보다 낮은 MSE를 갖는 consistent estimator는 없다고 밝혔다.

위 두가지 이유로 머신러닝에서 MLE는 자주 사용된다. 데이터 수가 작을때는 overfitting등의 위험이 있으므로 weight decay같은 regularization 을 사용하여 biased된 (variance가 적은) MLE를 얻는다.

Bayesian Statistics

지금까지는 frequentist statistics관점을 다루었다. 하나의 $\boldsymbol{\theta}$ 에서 가능한 모든 prediction을 뽑는 것이었다. 이제는 Bayesian statistics 관점에 대해 살펴볼 것이다. 가능한 모든 $\boldsymbol{\theta}$에서 하나의 prediction을 뽑는 것이다.
5.4.1에서 살펴보았듯이 frequentist 관점에서 보면 true parameter $\boldsymbol{\theta}$는 고정되어있지만 모르는 값이고, 데이터의 함수인 random variable $\hat{\boldsymbol{\theta}}$로 추정하는 것이다.
Bayesian 관점은 좀 다르다. Bayesian은 probability를 일종의 certainty로 해석한다. true parameter $\boldsymbol{\theta}$는 uncertain, unknown한 값이고, 따라서 이를 random variable로 놓는다. (frequentist 관점에서는 $\boldsymbol{\theta}$가 fixed, unknown값이었다.)
데이터를 관측하기 이전에, 도메인에 대한 사전지식을 반영할 수 있다. 사전지식은 prior probability distribution (사전확률분포, the prior) $p(\boldsymbol{\theta})$로써 표현한다. 데이터 가 있을때 data likelihood $p(x^{(1)},…,x^{(m)})$ 와 prior를 Bayes’ rule을 이용해 합쳐서 $\boldsymbol{\theta}$ 에 대한 확실성을 표현하면 아래와 같다.

Bayesian estimation을 사용할때는 주로 prior를 높은 엔트로피(불확실성)를 갖는 uniform 이나 Gaussian distribution을 이용한다. 그리고 데이터에 의한 posterior는 엔트로피를 낮추고 그럴듯한 parameter 근처의 값을 갖도록 만드는 역할을 한다. Bayesian estimation은 MLE와는 다른 두개의 중요한 차이점이 있다.
첫째로, $\boldsymbol{\theta}$ 를 point estimate하는 MLE와는 달리, $\boldsymbol{\theta}$에 대한 모든 분포를 사용하여 prediction을 한다. 예를 들어 $m$개의 데이터를 얻고 나서, 다음 데이터 $x^{(m+1)}$의 분포를 예측해보면 아래와 같다.

양의 확률분포를 갖는 $\boldsymbol{\theta}$의 값은 각각의 확실성의 크기 $p(\boldsymbol{\theta}\mid x^{(1)},…,x^{(m)})$ 만큼 prediction에 영향을 미친다. 즉, 확실성을 가중치로 한 weighted sum인 셈이다.
5.4 절에서 frequentist 관점을 다룰 때, $\boldsymbol{\theta}$ 에 대한 point estimation의 불확실성은 variance로 표현하였다. variance는 샘플링된 데이터에 따라 estimator의 추정값이 얼마나 바뀌는지에 대한 지표였다. Bayesian은 이를 그저 단순하게 다 합하는 방법으로 해결하였다.

두번째로 MLE와 Bayesian이 다른 중요한 점은, prior distribution이다. 사전확률분포 prior는 parameter가 존재하는 space를 prior에 맞게 옮기도록 한다. 예를 들면, 아주 약간 일그러진 주사위를 굴릴 때, 일그러졌기 때문에 각각의 눈이 나올 확률은 정확하게 1/6은 아닐 것이다. 실제로는, 4라는 눈이 더 자주(1/5확률로) 나온다고 가정하자. 주사위를 5번 던진 결과 4라는 눈이 2번 나왔다. 이때, 관측된 데이터로만 (사후확률분포) 확률을 구하면 2/5 이다. 그러나 우리의 prior로는 기본적으로는 1/6 확률이되, 관측된 결과값을 반영하여 수정하는 것이 좀더 타당할 것이다. 따라서 prior를 적용하면 관측값 2/5와 prior 1/6 사이의 어떠한 확률값이 나올 것이다. 이것이 prior가 probability mass density를 움직이는 것, 즉 확률분포의 베이스를 prior로 잡아주는 것이다. 따라서 Bayesian에는 인간의 직관,판단에 의존한 prediction이라는 비판이 존재한다. 그러나 수식적으로, 관측데이터 수가 매우 많아진다면 prior는 큰 영향을 끼치지 못하고 관측데이터에 의존적인 확률분포를 따른긴 한다.
Bayesian은 데이터가 적을 때 generalize하는 성능이 더 낫지만, 데이터 수가 많을 때는 연산비용이 많이 든다는 단점이 있다.

Example: Bayesian Linear Regression

이번에는 Bayesian 으로 linear regression을 해보자. linear regression은 스칼라 $y \in \mathbb{R}$ 이 입력벡터 $\boldsymbol{x} \in \mathbb{R}^n$ 와 선형적으로 맵핑되는 것이다. prediction은 아래와같이 벡터 $\boldsymbol{w} \in \mathbb{R}^n$으로 parametrized된다.

이를 데이터셋들과 가우시안 조건부 확률로 나타내면 아래와 같다.

$y$에 대한 Gaussian variance을 가정했던 MSE 식을 통해 전개하였다. 데이터와 label(target) 쌍은 이제 $(\boldsymbol{X},\boldsymbol{y})$ 로 표기한다.
model parameter $\boldsymbol{w}$에 대한 posterior distribution을 정하기 앞서, prior distribution을 먼저 정해야 한다. 흔히 사용되는 Gaussian distribution을 prior로 사용한다.

$\boldsymbol{\mu}_0$ 와 $\boldsymbol{\Lambda}_0$는 각각 평균벡터와 covariance matrix다. prior가 정해졌으니, model parameter의 posterior distribution을 구해보자.

$\boldsymbol{\Lambda}_m = (\boldsymbol{X}^\top \boldsymbol{X}+ \boldsymbol{\Lambda}_0^{-1})^{-1}$ 으로 정의하고, $\boldsymbol{\mu}_m = \boldsymbol{\Lambda}_m(\boldsymbol{X}^\top \boldsymbol{y}+\boldsymbol{\Lambda}_0^{-1}\boldsymbol{\mu}_0)$으로 정의하자. 이를 이용해 위 식을 다시 전개하면 아래와 같다.

parameter $\boldsymbol{w}$가 포함되지 않은 항은 모두 없앴다. 확률분포의 합이 1이 되도록 normalized 되어있음을 의미한다. 3장의 3.23식을 보면 다변수 가우시안 분포를 normalize하는 방법이 나와있다.
posterior distribution에서 보통 $\boldsymbol{\mu}_0$를 0으로 둔다. $\boldsymbol{\Lambda}_0 = \frac{1}{\alpha}\boldsymbol{I}$로 두면, $\mu_m$는 $\alpha \boldsymbol{w}^\top \boldsymbol{w}$의 weight decay penalty가 있는 frequentist linear regression과 같다. (차이가 있다면, Bayesian은 $\alpha$가 0인 경우에서는 정의되지 않는다. $\boldsymbol{w}$에 대해 무한히 넓은 prior가 가정되기 때문이다.) 더 중요한 차이점은 Bayesian 에서는 covariance matrix를 사용한다는 점이다.

Maximum a Posteriori (MAP) Estimation

$\boldsymbol{\theta}$에 대해 모든 Bayesian posterior distribution 을 사용하여 prediction을 하는 것이 좋아보이지만, 단 하나의 estimation을 구하는게 더 바람직 할 때가 있다. 그 이유는 모든 posterior distribution 을 사용하는 것은 연산비용이 많이 들고 까다롭기 때문이다. 그래서 parameter에 대해 single estimation을 하는 MLE가 더 다루기 쉬울 때가 있다. 대신, Byesian에서 사용했던 prior는 그대로 반영할 수 있는데, 이를 maximum a posteriori (MAP) estimation이라고 한다. MAP는 단 하나의 maximal posterior probability를 구한다.

log-likelihood 방법을 이용해서 prior 를 $\log p(\boldsymbol{\theta})$로 나타낸다. 예를 들어,weight $\boldsymbol{w}$에 Gaussian을 prior로 가진 linear regression 모델을 생각해보자. prior가 $\mathcal{N}(\boldsymbol{w};0,\frac{1}{\lambda}\boldsymbol{I}^2)$ 로 주어지고 log-prior 항은 $\lambda \boldsymbol{w}\top \boldsymbol{w}$에 대한 weight decay 패널티와 $\boldsymbol{w}$의 학습과 무관한 항의 합으로 볼 수 있다. 이처럼 MAP Bayesian inference는 학습데이터에서는 찾을 수 없었던 prior의 정보를 활용할 수 있다는 장점이 있다. 이는 MLE에 비해서 variance는 줄여주지만, bias를 증가시킨다. 위에서 본 weight decay가 주어진 MLE처럼, 많은 regularized estimation들이 MAP로 해석될 수 있다. regularization이 일종의 prior $\log p(\boldsymbol{\theta})$ 로 해석되는 것이다. 그렇다고해서 꼭 모두 그런 것은 아니다. log probability distribution에 적용되는 것이 아니라 데이터에 의존적인 regularization도 있다.

Supervised Learning Algorithms

5.1.3 절에서 보았듯, 학습 알고리즘은 입력과 출력간의 어떠한 관계를 학습하는 것을 의미한다. 원래는 입력과 ‘superviser’ 사람에 의해 수집된 정답(레이블, 타겟) 간의 관계를 학습하는 것을 supervised learning이라 하지만, 폭넓게는 자동적으로 수집된 데이터도 정답 레이블이 있다면 supervised learning이라 한다.

Probabilistic Supervised Learning

대부분의 supervised learning은 $p(y\mid \boldsymbol{x})$ 을 추정한다. 우리는 이를 best parameter $\boldsymbol{\theta}$ 를 찾기위한 maximum likelihood 로 볼 수 있다. 이전에 linear regression 문제에서 다루었던 $p(u\mid \boldsymbol{x};\boldsymbol{\theta}) = \mathcal{N}(y;\boldsymbol{\theta}^\top \boldsymbol{x},\boldsymbol{I})$ 처럼, classification 또한 아래와 같이 나타낼 수 있다.

linear regression에서는 평균을 예측하는 의미로 normal distribution을 사용하였지만, classification에서는 해당 class에 속할 $(y=1)$ 확률로, 0에서 1사이의 확률값을 내뱉어야 한다. 따라서 logistic sigmoid function $\sigma$ 를 사용한다. 이러한 접근을 logistic regression이라 한다.

linear regression에서는 normal equation을 이용해 optimal weight를 한번에 구했지만, logistic regression에서는 이러한 방법을 사용할 수 없다. (optimal weight를 위한 closed-form solution이 없다.) 따라서 gradient descent를 이용해 negative log likelihood를 최소화 하는 방법으로 이 문제를 해결한다.

Support Vector Machines

Support vector machine (SVM)은 정말 많이 쓰이는 supervised learning방법 중 하나다. linear function $\boldsymbol{w}^\top\boldsymbol{x}+b$로부터 유도되는 logistic regression방 법이다. 위에서 본 logistic regression과는 달리, 확률값을 내뱉는 것이 아니라 class identity를 내뱉는다. positive class에 속하면 $\boldsymbol{w}^\top\boldsymbol{x}+b$가 양의 값을 갖고, negative class 에 속하면 $\boldsymbol{w}^\top\boldsymbol{x}+b$가 음의 값을 갖는다.

여기에 kernel trick이라는 핵심적인 방법이 더해져 아래와 같은 수식으로 사용된다.

$\boldsymbol{x}^{(i)}$는 학습 데이터고, $\alpha_i$는 계수다. 위 수식은 $\boldsymbol{x}$와 학습 데이터간의 dot product의 형태로 학습 알고리즘을 바꾸어준다. 이 수식을 좀더 일반화 해서 써보면, $\boldsymbol{x}$ 대신 $\boldsymbol{x}$의 feature인 $\phi(\boldsymbol{x})$로 쓰고, dot product대신 kernel을 나타내는 $k(\boldsymbol{x},\boldsymbol{x}^{(i)})$로 쓴다. 그럼 아래의 일반화 된 수식으로 prediction function을 나타낼 수 있다.

이 함수는 $\boldsymbol{x}$에 대해서는 nonlinear하다. 그러나 $\phi(\boldsymbol{x})$와 $\boldsymbol{\alpha}$에 대해서는 linear하다. 즉, kernel-based function은 각각의 데이터에 $\phi(\boldsymbol{x})$를 적용하여 전처리를 하는 것과 같다. 전처리 한 후의 transformed space와 선형관계를 학습함으로써, $\boldsymbol{x}$와는 nonlinear한 관계를 학습하는 것이다. 이는 두가지 장점이 있는데, $\boldsymbol{x}$와는 nonlinear 하기 때문에 convex optimization 기술을 이용해 효율적으로 수렴하는 것을 보장할 수 있다. 두번째로는 kernel function $k$ 는 dot product보다는 굉장히 효율 좋은 연산으로 구현할 수 있다는 것이다.

흔히 쓰이는 kernel은 Gaussian kernel이다. (또는 radial basis function, RBF)

RBF라고 불리우는 이유는 $\boldsymbol{v}$가 $\boldsymbol{u}$로부터 멀어질수록(radiating) 이 함수의 결과값이 작아지기 때문이다. 이는 또한 일종의 template matching으로도 볼 수 있는데, 학습 데이터 $\boldsymbol{x}$에 해당하는 학습 레이블 $y$가 있을 때, $\boldsymbol{x}$가 class $y$에 대한 template으로 사용되기 때문이다. 만약 test point $\boldsymbol{x}’$가 $\boldsymbol{x}$와의 Euclidean distance가 작다면, 가우시안 커널은 큰 값을 내뱉을 것이고, model은 training label $y$에 대한 weihgt를 크게 가져갈 것이다.

이렇게 SVM 처럼 kernel trick을 사용하는 방법들을 kernel method, kernel machine이라고 한다. kernel machine들의 가장 큰 단점은 항 때문에 학습데이터의 수에 따라 연산 cost가 크게 증가한다는 것이다. SVM은 대부분이 0인 $\boldsymbol{\alpha}$ 를 학습함으로써 이를 완화한다. nonzero인 $\alpha_i$에 대해서만 수행하면 되는 것이다. 이러한 학습 데이터들을 support vector라고 부른다.

현대의 딥러닝 방법들은 kernel machine들의 단점을 극복하도록 설계되었고, Hinton et al.(2006) 에서 뉴럴넷이 RBF kernel SVM을 MNIST 벤치마크에서 뛰어넘는 것이 밝혀지면서 딥러닝의 시대가 시작되었다.

Other Simple Supervised Learning Algorithms

  • k-nearest neighbor (KNN) : 이전에 간략하게 다룬 nonprobabilistic supervised learning 알고리즘이 있는데, nearest neighbor regression이다. 일반적으로 $k$-nearest neighbor 이라고 불린다. nonparametric learning 알고리즘처럼, $k$-nearest neighbor 알고리즘은 고정된 갯수의 파라미터를 갖지 않는다. 흔히 $k$-nearest neighbor는 어떠한 파라미터도 갖지 않고, 단순히 학습 데이터들의 함수로만 이루어진다고 여겨지지만, 사실은 학습과정조차 없다. 대신 테스트 단계에서, 새로운 데이터 $\boldsymbol{x}$가 들어왔을 때, 기존 데이터들간의 거리를 측정해서 이웃하는 데이터들의 평균 label을 내뱉는다. 학습 모델을 따로 만들지 않기 때문에 Lazy model, Instance-based learning으로도 불리운다. KNN은 두가지 하이퍼 파라미터를 갖는다.
    • 탐색할 이웃 수 k : 학습 데이터가 무한히 많을 때, test point $\boldsymbol{x}$ 와의 distance가 0인 train data 또한 무수히 많을 것이다. 이 중에서 랜덤하게 몇개를 선택해서 볼 지에 대한 하이퍼 파라미터다. $k$ 가 작다면, 적은 수의 data에 overfitting되는 경우가 있고, 지나치게 크다면 제대로된 추정이 불가능한 underfitting의 위험이 있다. 따라서 naive하게는 모든 $k$에 대해 탐색해야 하며, 이를 좀더 효율적으로 찾기 위한 발전된 방법론들이 있다.
    • 거리측정방법 : test data와 train data간의 거리를 측정하는 방법(수식)에 따라 KNN의 성능이 달라진다. Euclidean distance, Manhattan distance, Correlation distance, Rank correlation distance, Mahalanobis distance 등 다양한 방법들이 있다. 이 중에 단순히 직선 거리를 측정하는 Euclidean 보다, 데이터 변수들의 공분산 등을 고려한 Mahalanobis distance가 흔히 사용된다.
  • decision tree : decision tree는 파라미터들을 각 영역에 따라 분리하는 알고리즘이다. 아래 그림처럼 입력 변수들을 특정 기준으로 하위 분류기준으로 나눈다. 최하위 노드들이 각각의 입력 영역에 일대일 대응이 되게끔 서로 겹치지 않게 나뉜다. Decision tree는 이 책의 뒷부분에서 다시 다룬다. 트리의 크기를 제한하지 않으면 nonparametric 으로 여겨지지만, 일반적으로는 사이즈를 지정하기 때문에 parametric model로 사용된다. DBL-05-10

Unsupervised Learning Algorithms

5.1.3에서 언급한 것 처럼, unsupervised learning은 supervision signal(label, target)이 아닌 오직 feature에 대한 것이다. 그러나 이어서 언급했다시피, supervised learning 과 unsupervised learning이 수식적으로 엄밀하게 구분되어있는 것은 아니다. 대강 말하자면, unsupervised learning은 distribution으로부터 뽑아내는 정보가 사람이 매겨준 annotation, target, label이 필요치 않은 것을 말한다. 예를 들면, density estimation이나 distribution으로 sample들을 만들어내는 것, distribution으로부터 data denoising 을 학습하는 것, data가 존재하는 manifold공간을 찾아내는것, 비슷한 data끼리 묶어서 clustering하는 것이 unsupervised learning이다. 가장 고전적인 unsupervised learning task는 데이터의 “best” representation을 찾는 것이다. “best” representation을 찾는다는 것은 원본 feature $\boldsymbol{x}$ 에 대한 정보를 잃지 않으면서 원본보다 더 단순하거나 이용하기 쉽게 만드는 representation을 찾는다는 것이다.
단순한 representation으로 바꿔주는 방법에는 주로 세가지가 쓰인다. 첫번째로 Low-dimensional representations은 원본보다 더 작은 차원으로 압축하여 데이터를 표현하는 것이다. 두번째로 Sparse representations (Barlow, 1989; Olshausen and Field, 1996; Hinton and Ghahramani, 1997)은 dataset을 input의 대부분을 0으로 만드는 representation으로 바꾼다. 이렇게 바꾸려면, 원본보다 차원을 늘려줘야 정보를 잃지 않으면서 sparse한 reapresentation을 만들 수 있다. 이는 data를 각각의 representation axes로 뿌려주는 효과가 있다. 세번째로 Independent representations은 통계적으로 독립적인 데이터 소스를 각각의 차원으로 분리해낸다.
물론 이 세가지가 서로 겹치는 부분이 없는 것은 아니다. Low-dimensional representations는 원본의 데이터에서 redundancy를 줄여서 차원을 줄일 수 있다. 그렇기 때문에 각각의 차원이 고차원 데이터보다 independent하게 표현될 수 있다.
Representation의 개념은 딥러닝에서 매우 중요하고, 따라서 이 책에서도 중요하게 다뤄질 것이다. 이 section에서 몇가지 간단한 representation learning 예시들을 살펴볼 것이고, 나머지 챕터에서도 더 많은 방법들을 소개할 것이다.

Principal Components Analysis

2장의 2.12절에서 우리는 principal components analysis (주성분 분석, PCA)를 데이터 압축의 관점에서 보았다. 우리는 이를 data representation을 학습하는 unsupervised learning의 측면에서도 볼 수 있다. PCA는 simple representation을 위해 두가지 criteria 에 기반하여 representation을 만든다. 첫번째로, 원래 데이터의 차원보다 적은 차원으로 만들어야 한다. 두번째로는 representation의 element들이 서로 linear correlation이 없어야 한다. full independence를 위해서 learning 알고리즘은 variable간의 비선형 관계를 모두 제거해야 한다.
아래 그림에서 나와있듯이, PCA는 input data $\boldsymbol{x}$를 orthogonal, linear transform하여 representation $\boldsymbol{z}$로 사영(projection)한다. 2장의 2.12절에서 원본데이터를 가장 잘 복원(MSE로)할 수 있는 1차원 representation을 학습할 수 있다는 것을 확인했다. 그리고 이 1차원 representation은 사실 데이터의 첫번째 주성분과도 같다. 그러므로 우리는 PCA를 단순하고 효과적인 (원래의 정보를 가능한 많이 보존하는) 차원축소 방법으로 사용할 수 있다. 이제 PCA가 어떻게 원본데이터 $\boldsymbol{X}$를 변형하는지 알아보자.

DBL-05-08

원본데이터 $\boldsymbol{X}$가 $m \times n$ matrix라고 하자. 이때 평균은 0에 맞춰져있다 ($\mathbb{E}(\boldsymbol{x})=0$). 평균을 0에 맞추는것은 전체 데이터에서 원본의 평균을 뺌으로써 쉽게 맞춰줄 수 있다. unbiased sample covariance matrix는 아래와 같이 주어진다.

PCA는 linear transform을 통해 representation $\boldsymbol{z} = \boldsymbol{W}^\top\boldsymbol{x}$를 찾는 것이다. 이때 $\text{Var}[\boldsymbol{z}]$는 diagonal하다. 즉, 서로 다른 variable끼리는 correlation이 없다. 2장 2.12절에서 $\boldsymbol{X}$의 principal component(주성분)는 $\boldsymbol{X}^\top\boldsymbol{X}$의 eigenvector임을 확인했다.

이번 섹션에서는 principal component의 다른 유도를 이용한다. 주성분은 singular value decomposition (SVD)을 이용해서도 얻을 수 있다. 특히, $\boldsymbol{X}$의 right singular vector을 쓴다. $\boldsymbol{X} = \boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{W}^\top$ 에서 $\boldsymbol{W}$를 right singular vector로 사용하면 원래의 eigenvector 수식을 아래와 같이 전개할 수 있다.

DBL-05-09

$\boldsymbol{X}$의 SVD를 이용하여 variance를 다시 전개할 수 있다.

$\boldsymbol{U}$ 는 SVD에서 orthogonal 로 정의된 행렬이기 때문에 $\boldsymbol{U}^\top \boldsymbol{U} = \boldsymbol{I}$이다. $\boldsymbol{z}$의 covariance는 아래와같이 전개된다.

$\boldsymbol{W}$ 또한 SVD에서 orthogonal로 정의된 matrix 이므로 $\boldsymbol{W}^\top\boldsymbol{W} = \boldsymbol{I}$이다.

이렇게 전개된 수식들에 따르면, data $\boldsymbol{x}$를 선형변환 $\boldsymbol{W}$를 통해 $\boldsymbol{z}$로 사영시킬 때 diagonal covariance matrix $\boldsymbol{\Sigma}^2$를 따르고 $\boldsymbol{z}$들의 각 요소들은 서로 uncorrelated 하다.

k-means Clustering

또 다른 representation learning은 $k$-means clustering이다. $k$-means clustering은 데이터들을 유사한 것들끼리 묶어서 $k$개의 cluster로 표현하는 것이다. 데이터를 $k$차원의 one-hot 벡터로 나타내는 것으로도 볼 수 있다. 유사한 데이터들을 하나의 클러스터 원핫으로 표현하는 것은 정보의 손실이 있긴 하지만, 많은 데이터들을 하나의 정수로 표현가능하다는 장점이 있다.
$k$-means clustering은 $k$개의 각기다른 centroid 들 을 초기화하는 것으로 시작된다. 그 다음 아래 두 단계를 수렴할때까지 반복한다.

  1. 각각의 학습데이터를 가장 가까운 cluster $\mu^{(i)}$ 에 할당한다.
  2. 각각의 cluster centroid를 할당된 데이터 포인트들의 평균으로 이동시킨다.

intra-cluster와 inter-cluster의 Euclidean 거리를 비교해서 얼마나 클러스터링이 잘 되어있는지는 알 수 있지만, 이것이 현실세계에서 데이터의 특성을 얼마나 잘 반영하는지 알려주는 것은 아니다. 예를 들어 빨간 승용차, 빨간 트럭, 회색 승용차, 회색 트럭의 이미지들이 있을 때, 두개의 클러스터로 이미지들을 분류해보자. [빨간 탈것 / 회색 탈것] 이렇게 두가지로 구분할 수 도 있고, [승용차 / 트럭] 이렇게 두가지로 분류할 수도 있다. 네가지 클러스터로 분류한다면 [빨간 승용차 / 빨간 트럭 / 회색 승용차 / 회색 트럭] 이렇게 분류할 수도 있지만, 이러한 분류는 클러스터간 얼마나 유사하고 얼마나 다른지에 대해서는 알 수 없다.

이러한 이슈들 때문에 distributed representation 이 one-hot representation 보다 선호되는 것이다. distributed representation은 색깔과 차의 유형을 모두 나타낼 수 있다. 따라서 각각의 object들의 유사도를 나타낼 수 있는 것이다.

Stochastic Gradient Descent

최근 대부분의 딥러닝 알고리즘은 stochastic gradient descent(SGD)에 기반한다. SGD는 이전에 4장의 4.3절에서 다루었던 gradient descent의 확장된 버젼이다. 많은 학습 데이터들에 대해 각각 gradient descent를 수행하는 것은 연산시간이 많이 들기 때문에 $m$개의 데이터들에서 cost를 구하고 평균내어 한번에 gradient descent를 한다. gradient의 expectation을 사용하는 것이다. 예를 들어, negative conditional log-likelihood 에서는 아래와 같이 사용된다.

$L$은 각각의 데이터별로 loss를 산출하는 함수로, $L(\boldsymbol{x},y,\boldsymbol{\theta}) = -\log p(y\mid \boldsymbol{x;\theta})$이다. 이 cost (loss)를 따라서 gradient descent는 아래와 같다.

computational cost는 $O(m)$이다. expectation은 데이터들의 small set으로도 근사될 수 있다. 우리는 작은 데이터 뭉탱이를 minibatch 라고 부른다. 전체 데이터가 몇개든 minibatch size $m’$개의 데이터만큼씩만 gradient descent를 한다.

이 gradient와 learning rate $\epsilon$을 이용해 모델 파라미터를 업데이트 한다.

SGD의 cost는 전체 학습 data size $m$에 상관없이 $m’$에 의존적이다. 학습데이터가 무한히 큰 경우에, 모든 데이터를 다 학습하기도 전에 test error를 최적성능으로 수렴시킬 수 있다는 장점도 있다. kernel을 사용하는 많은 머신러닝 알고리즘들은 computational cost가 $O(m^2)$ 다. 데이터셋들간의 kernel matrix $G_{i,j} = k(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(j)})$를 모두 계산해야 하기 때문이다. 그러나 SGD는 $m$과 상관없이 매 스텝이 $O(1)$이라고 볼 수 있다. SGD에 대해서는 8장에서 더 다룬다.

Building a Machine Learning Algorithm

머신러닝 알고리즘을 만드는 방법은 상당히 단순하다. 데이터셋과 cost function을 연결시켜주고, optimization 종류와 모델을 결정한다.

예를 들어 linear regression에서는 데이터셋($\boldsymbol{X},\boldsymbol{y}$)과 cost function 을 아래와 같이 엮어준다.

model은 $p_{model}(y\mid\boldsymbol{x}) = \mathcal{N}(y;\boldsymbol{x}^\top\boldsymbol{w}+b,1)$ 이고, 대부분의 경우엔 normal equation을 이용해서 cost의 gradient가 0인 지점으로 최적화 한다.

위의 예시에서 설명한 각각의 요소들을 다른 것으로 대체함으로써 많은 알고리즘을 설명할 수 있다. cost function을 negative log likelihood 처럼 통계적인 추정을 할 수 있는 항을 포함하게끔 바꿀 수도 있다. 또는 regularization 을 위한 항을 추가할 수도 있다. 예를 들어 weight decay 를 linear regression에 추가하면 아래와 같다.

위 식에서는 여전히 closed form optimization 이지만, 모델이 non linear로 바뀌게 되면 cost function은 더이상 closed form 으로 최적화 되지 않는다. 따라서 gradient descent 같은 반복적인 과정으로 최적화 해야한다.

이처럼 model, cost, optimization 을 엮어서 학습 알고리즘을 만드는 것은 supervised learning과 unsupervised learning에 모두 사용할 수 있다. unsupervised learning은 정답 레이블 $y$가 없으므로 오로지 데이터 $X$와 적절한 unsupervised cost로 정의된다. 예를 들어, 첫번째 PCA 벡터는 아래와 같은 cost function으로 얻을 수 있다.

이때 $r$은 reconstruction function $r(\boldsymbol{x}) = \boldsymbol{w}^\top\boldsymbol{xw}$ 이다. 즉, PCA로 데이터를 저차원으로 임베딩 했다가 $r$ 함수로 다시 복원했을 때, 원본 데이터의 정보 손실을 최소화 하는 것이다.

많은 머신러닝 알고리즘들이 이런 방식으로 만들어진다. 그러나 가끔은 특별한 optimizer를 사용해야 할 때도 있다. 예를 들면 decision tree나 $k$-means 같은 경우는 cost function이 flat하기 때문에 gradient based optimization은 적합하지 않다.

Challenges Motivating Deep Learning

AI 시스템을 개발하는데 있어서 어려운 점들을 살펴보자.

The Curse of Dimensionality

많은 머신러닝 알고리즘들이 직면한 문제가 바로 데이터의 차원에 대한 문제다. 이를 curse of dimensionality (차원의 저주) 라고 한다. 데이터의 차원이 증가할 때마다 차원공간속의 데이터분포를 설명할 데이터의 양이 지수적으로 증가한다는 것이다. 아래 그림에 잘 설명되어있다.

DBL-05-11

각각의 길이를 10이라 했을 때, 1차원인 데이터 공간에서, 서로 다른 8개의 데이터를 갖고있다면 공간의 8/10 에 해당하는 데이터를 갖고 있는 것이다. 그러나 차원이 2차원으로 늘어나면, 내가 갖고 있는 데이터는 데이터 공간의 8/100이다. 3차원이면 8/1000 이다. 많은 머신러닝 테스크가 공간속에 존재하는 데이터 분포를 이용하는데, 차원이 증가하면 그 분포를 설명하는 데이터의 수도 급증해야 한다는 의미다.

Local Constancy and Smoothness Regularization

머신러닝 알고리즘은 선택하고 학습하는 함수들의 prior belief에 의해서 특성이 달라진다. 가장 흔하게 사용되는 prior은 smoothness, local canstancy다. 이 prior는 sample들이 살짝씩 달라지더라도 학습결과는 크게 변하지 않는다는 것을 의미한다. 이것이 지켜지지 않으면, 고차원의 데이터 공간을 우리가 가진 데이터들의 분포로 잘 설명하지 못하고, 따라서 분포를 사용하는 어떠한 테스크도 최적화 하기 어렵다.

약간의 $\epsilon$의 차이가 있어도, 결과는 $\boldsymbol{x}$와 유사해야 한다는 prior다. 이러한 prior를 표현하는 implicit하거나 explicit한 방법은 많이 있다. local conatancy의 극단적인 예시는 $k$-nearest neighbor이다. $k$-nearest neighbor에서 test data $(\boldsymbol{x})$는 $k$개의 근처 학습데이터 ($\boldsymbol{x}+\epsilon$)들과 같은 클래스로 구분된다($f^\ast(\boldsymbol{x}) \approx f^\ast(\boldsymbol{x}+\epsilon)$). kernel machine에서는 test data와 근처 학습데이터를 interpolate (보간)한다. local kernel $k(\boldsymbol{u,v})$는 두 벡터의 거리가 가까울 수록 커지고 벡터의 거리가 멀수록 작아진다. local kernel은 템플릿 매칭을 하는 similarity function으로도 볼 수 있다. Decision tree는 파라미터를 기준으로 branch 들을 나누어가기 때문에 근처의 데이터들도 전혀 다른 leaf로 구분되기도 한다.

Manifold Learning

Manifold는 머신러닝에서 중요한 개념 중 하나다. 정말 중요하다. Manifold란, 국소적으로는 Euclidean space와 위상학적으로 같은 연속된 점들의 집합이다. 우리는 일상적으로 평면위에서 생활하지만, 지구는 사실상 굴곡진 3D라는 것과 직관적으로는 비슷한 개념이라고 보면 된다. 수학적으로 이를 설명하는 방법이 있지만, 머신러닝에서는 대강 고차원 공간 상에서, 저차원으로 임베딩 된 연속된 점들의 집합공간 정도로 여겨진다.

DBL-05-12

위 그림에 2차원 공간 상에서 1차원으로 존재하는 점들의 집합공간 manifold 가 묘사되어있다. 머신러닝에서는 monifold의 차원은 유동적이다. 예를 들어, 파란 선들의 교차점에서는 2차원 manifold로도 볼 수 있는 것이다.
Manifold hypothesis는 image, text, sound등의 데이터들의 분포가 특정 영역(manifold)에 분포되어있다는 가설이다. 만약 이미지의 데이터분포가 특정 영역에 몰려있지 않다면 uniform random을 통해 데이터를 뽑았을 때 그럴듯한 이미지가 나와야 한다. 하지만 실제로는 아래와같이 노이즈가 잔뜩 낀 이미지만 나올 뿐이다.

DBL-05-13

이러한 data probability distribution 을 학습하여 이용하는 머신러닝 딥러닝 연구들은 매우 많이 나와있다. 이전부터 익히 사용되던 오토인코더를 비롯하여 최근에는 이미지에서 여러가지 특성의 manifold를 분리해내는 disentangled reperesentation learning 또한 활발하게 연구중이다.