[PRML] ch 1 Introduction

1. Introduction

Pattern Recognition:

• 주어진 데이터에서 특정한 패턴을 찾아내는 것. training set로부터 학습하여 test set을 예측

• 학습 시에는 전처리, 특성 추출, 차원 축소 등의 방법을 활용

• 예측 시 "일반화 generalization" 을 목표로 한다.

• 예측은 분류와 회귀 task로 나뉠 수 있고 지도학습, 비지도학습, 강화학습 등의 방법이 있다.

1.1 Example: Polynomial Curve Fitting

---

• 곡선 적합

  • input $\mathbf{x}=(x_1,...,x_N)^T$, target $\mathbf{t}=(t_1,...,t_N)^T$

  $$y(x,\mathbf{w})=w_0+w_1x+w_2x^2+...+w_Mx^M=\sum_{j=0}^{M}w_jx^j$$

  • linear model: 계수 $\mathbf{w}$에 대해 선형

• 오차함수 $E(\mathbf{w})=\frac{1}{2}\sum_{n=1}^{N}\{y(x_n,\mathbf{w})-t_n\}^2$를 최소화하는 $\mathbf{w}$를 선택

  • model selection: order M 결정 → 좋은 일반화 달성이 목표

    • M이 크면 overfitting 가능성 커지고 모델이 복잡, 유연해짐

    • M이 작으면 underfitting 가능성이 큼

  • 성능지표 $RMSE=\sqrt{2E(\mathbf{w}^*)/\mathbf{w}}$

  • Regularization(정규화): 오차함수에 패널티 항을 추가하여 과적합 방지

    $$E(\tilde{\mathbf{w}})=\frac{1}{2}\sum_{n=1}^{N}\{y(x_n,\mathbf{w})-t_n\}^2+\frac{\lambda}{2}\lVert \mathbf{w} \rVert ^2$$

    • tuning parameter $\lambda$ controls overfitting

  • 모델 복잡도: training set과 validation set으로 조절

1.2 Probability Theory

---

• 패턴 인식에서 "불확실성"을 다루기 위해 "확률론"이 필요

• sum rule, product rule

• marginal probability, conditional probability

• Bayes' theorem

  $$P(Y|X)=\frac{p(X|Y)p(Y)}{p(X)}$$

• prior probability, posterior probability

• independent

1.2.1 Probability densities

• probability density , probability mass

• cumulative distribution function

1.2.2 Expectations and covariances

• Expectations, conditional expectation

• variance, covariance

1.2.3 Bayesian probabilities

• classical(frequentist) or Bayesian

  • $$p(\mathbf{w}|\mathcal{D})=\frac{p(\mathcal{D}|\mathbf{w})p(\mathbf{w})}{p(\mathcal{D})}$$

  • $posterior \propto likelihood \times prior$

• 베이지안 방법론

  • 장점: 사전 지식을 추론 과정에 포함

  • 단점: 사전 확률의 선택에 따라 추론 과정에 주관이 포함됨

1.2.4 The Gaussian distribution

$$N(x|\mu, \sigma^2)=\frac{1}{(2\pi\sigma^2)^{1/2}} exp\{-\frac{1}{2\sigma^2}(x-\mu)^2\}$$

1.2.5 Curve fitting re-visited

• 확률분포

  • input $\mathbf{x}=(x_1,...,x_N)^T$와 target $\mathbf{t}=(t_1,...,t_N)^T$가 주어진 상황에서 새로운 input $x$가 주어졌을 때 그에 대한 타깃 변수 $t$ 예측

    $$p(t|x,\mathbf{w},\beta)=N(t|y(x,\mathbf{w}), \beta^{-1})$$

    • $\beta$는 정밀도(precision) parameter로, 분포의 표본의 역수

  • MLE를 통해 $\mathbf{w}$와 $\beta$를 구하면,

  $$\mathbf{w}_{ML}=\frac{1}{N}\sum{n=1}^{N}x_n, \beta^{-1}=\frac{1}{N}\sum_{n=1}^{N}\{y(x_n,\mathbf{w}_{ML})-t_n\}^2$$

• 예측분포(predictive distribution)

  $$p(t_{NEW}|x_{NEW},\mathbf{w}_{ML},\beta_{ML})=N(t_{NEW}|y(x_{NEW},\mathbf{w}_{ML}), \beta_{ML}^{-1})$$

  • 다항계수 $\mathbf{w}$에 대한 사전 분포 도입

    $$p(\mathbf{w}|\alpha)=N(\mathbf{w}|0,\alpha^{-1}\mathbf{I}=(\frac{\alpha}{2\pi})^{\frac{M+1}{2}}exp\{-\frac{\alpha}{2}\mathbf{w}^T\mathbf{w}\}$$

    • $\alpha$는 분포의 정밀도(precision)로 hyperparameter, $\mathbf{w}$는 $M$차원

    • $\mathbf{w}$의 사후 분포

      $$p(\mathbf{w}|\mathbf{x}, \mathbf{t}, \alpha, \beta) \propto p(\mathbf{t}|\mathbf{x}, \mathbf{w}, \beta)p(\mathbf{w}|\alpha)$$

  • MAP (Maximum A Posterior)

    • 주어진 데이터에 대해 가장 가능성 높은, 즉 사후분포를 최대화하는 $\mathbf{w}$ 찾기

    • 즉, $p(\mathbf{t}|\mathbf{x}, \mathbf{w}, \beta)p(\mathbf{w}|\alpha)$인 다음 식을 최대화한다.

    $$-\frac{\beta}{2}\sum_{n=1}^{N}\{y(x_n,\mathbf{w})-t_n\}^2-\frac{\alpha}{2}\mathbf{w}^T\mathbf{w}$$

    • 따라서, 사후분포를 최대화하는 것은 정규화 매개변수 $\lambda=\alpha/\beta$로 패널티항을 추가한 오차 함수(1.4)를 최소화하는 것과 동일하다.

1.2.6 Bayesian curve fitting

• '주변화' 시행

• 예측 분포 구하기 (3.3 참고)

  $$p(t|x,\mathbf{x},\mathbf{t})=\int{p(t|x,\mathbf{w})p(\mathbf{w}|\mathbf{x},\mathbf{t})d\mathbf{w}} = N(t|m(x), s^2(x))$$

  $$m(x)=\beta\phi(x)^T\mathbf{S}\sum_{n=1}^{N}\phi(x_n)t_n$$

  $$s^2(x)=\beta_{ML}^{-1}+\phi(x)^T\mathbf{S}\phi(x)$$

  $$\mathbf{S}^{-1}=\alpha\mathbf{I}+\beta\sum_{n=1}^{N}\phi(x_n)\phi(x_n)^T$$

  • $\phi(x)$는 각각의 원소가 $\phi_i(x)=x^i, i=0,...,M$

  • 각 평균, 분산이 $x$에 종속되어 있음.

  • $\beta_{ML}$ : 타깃 변수의 노이즈로 인한 예측치 $t$의 불확실성

  • $\phi(x)^T\mathbf{S}\phi(x)$ : $\mathbf{w}$의 불확실성

  • 증명: 2020/09/16 - [Machine Learning/PRML] - [PRML] Prove (1.69) - (1.72)

1.3 Model Selection

---

• parameter, hyperparameter 결정

• validation set 활용

  • cross validation (교차검증법)

    • 장점: 모든 데이터를 활용하여 성능을 추정

    • 단점: 모델 학습의 시행 횟수, 모델의 파라미터 수가 증가함에 따라 모델 훌련의 시행 횟수가 매우 증가한다.

  • leave-one-out

• information criteria

  • AIC(Akaike Information Criterition)

  • BIC(Bayesian Information Criterion)

1.4 The Curse of Dimensionality

---

• 예: 분류 문제: 데이터를 분류하기 위해 여러 칸으로 나누어 클래스로 지정할 수 있는데, 이를 고차원으로 확장하면 필요한 칸의 숫자가 기하급수적으로 늘어난다.

• 예: $D$차원의 input에 대한 3차 계수까지의 다항식

• $y(\mathbf{x}, \mathbf{w})=w_0+\sum_{i=1}^{D}w_ix_i+\sum_{i=1}^{D}\sum_{j=1}^{D}w_{ij}x_ix_j+\sum_{i=1}^{D}\sum{j=1}^{D}w_{ijk}x_ix_jx_k$

  • $D$가 증가할수록 독립적인 계수의 수는 $D^3$에 비례하여 증가한다.

  • $M$차 다항식의 경우 $D^M$에 비례하여 증가

• 예: D차원의 반지름 $r=1$인 구체

  • 구체의 부피는 $r^D$에 비례하여 증가

  • $V_D(r)=K_Dr^D$

  • $r=1-\epsilon$과 $r=1$ 사이에 존재하는 부피의 비율

  • $\frac{V_D(1)-V_D(1-\epsilon)}{V_D(1)}=1-(1-\epsilon)^D$

    • $D$값이 큰 경우 $\epsilon$이 작아도 비율이 1에 가깝다.

    • 고차원의 공간에서는 구체 부피의 대부분이 표면 근처의 얇은 껍질에 집중되어 있다.

• 고차원 공간에서의 가우시안 분포

  • 밀도함수: $p(r)$

    • 원점에서부터 반지름 $r$에 대한 함수

    • 데카르트 좌표에서 극좌표로 변환한 뒤 방향성 변수들을 적분시켜 없애 구함

  • 확률질량: $p(r)\delta r$

    • 반지름 $r$ 상에 $\delta r$의 두께에 해당하는 확률질량

  • 큰 $D$값에 대해서 가우시안 확률 질량이 얇은 겉껍질에 집중되어 있음

• 차원의 저주(curse of dimensionality) 문제를 풀기가 어려운 이유

  • 실제 세계의 고차원 데이터들 중 유의미한(타깃 변수에 변화를 주는) 차원의 수는 제한적

  • 실제 세계의 데이터는 보통 '매끈한' 특성을 지님. 따라서 input이 작게 변해도 target도 작게 변함.

  • 예: 제조업 컨베이어 벨트 이미지 분류

    • 각 이미지가 고차원 공간은 포인트, 공간의 차원수는 픽셀의 수

    • 각 물체는 이미지 안에 다른 위치와 다른 모양으로 나타날 수 있으므로 이미지들 사이에는 3 단계의 자유도가 존재 → 이미지 집합은 고차원 공간 내부에 포함된 삼차원의 매니폴드(manifold)상에 존재한다.

    • 물체의 위치, 모양, 픽셀의 강도 등은 서로 간에 복잡한 관계를 지니므로 매니폴드는 강한 비선형성을 가진다.

1.5 Decision Theory

---

• 추론(inference): 결합 확률분포 $p(\mathbf{x}, \mathbf{t})$를 찾는 것

• 결정(decision) : 최적의 결합 확률분포를 찾는 것

• 예: 환자 엑스레이 이미지로 암 판단 문제

  • 이미지가 주어졌을 때 각 클래스의 조건부 확률

  • $p(\mathcal{C}_k|\mathbf{x})=\frac{p(\mathbf{x}|\mathcal{C}_k)p(\mathcal{C}_k)}{p(\mathbf{x})}$

  • 클래스 $\mathcal{C}_k$에 포함될 사전 확률 $p(\mathcal{C}_k)$, 사후 확률 $p(\mathcal{C}_k|\mathbf{x})$

  • $p(\mathcal{C}_1)$: x-ray 이미지 확인 전에 알 수 있는 환자가 암에 걸렸을 확률

  • $p(\mathcal{C}_1|\mathbf{x})$: x-ray에 포함된 정보를 베이지안 정리를 이용해 포함시킨 후 알 수 있는 환자가 암에 걸렸을 확률

1.5.1 Minimizing the misclassification rate

• mistake의 수 줄이기

  • decision region $\mathcal{R}_k$로 각 $\mathbf{x}$를 가능한 클래스 중 하나로 포함

  • decision boundary(surface): 결정 구역들 사이의 경계

• 2진 분류의 경우 mistake가 발생할 확률

  $$p(mistake)=p(\mathbf{x} \in \mathcal{R}_1, \mathcal{C}_2)+p(\mathbf{x}\in\mathcal{R}_2,\mathcal{C}_1)$$

  $$=\int_{\mathcal{R}_1}p(\mathbf{x},\mathcal{C}2)d\mathbf{x}+\int{\mathcal{R}_2}p(\mathbf{x},\mathcal{C}_1)d\mathbf{x}$$

  • mistake를 최소화하기 위해 각 x를 더 작은 결합확률에 클래스에 포함시킨다.

  • 즉, $p(\mathbf{x},\mathcal{C}_1)>p(\mathbf{x},\mathcal{C}_2)$일 때 $\mathbf{x}$를 클래스 $\mathcal{C}_1$에 포함시켜야 한다.

  • 이는 가능도 함수와 사전확률의 곱으로 표현될 수 있는데 사전확률은 같으므로 사후확률 $p(\mathcal{C}_k|\mathbf{x})$가 최대가 되는 클래스에 포함시키면 된다.

• K개 클래스 분류

  $$p(correct)=\sum_{k=1}^{K}p(\mathbf{x}\in\mathcal{R}k,\mathcal{C}k)=\sum{k=1}^{K}\int{\mathcal{R}_k}p(\mathbf{x},\mathcal{C}_k)d\mathbf{x}$$

  • 각 $\mathbf{x}$가 $p(\mathbf{x},\mathcal{C}_k)$가 최대인 클래스로 분류되도록 $\mathcal{R}_k$를 선택하면 $p(correct)$ 최대화. 즉, 사후확률 $p(\mathcal{C}_k|\mathbf{x})$ 최대화.

1.5.2 Minimizing the expected loss

• 손실함수(loss function), 비용함수(cost function)

  • 전체 손실 최소화 목표

  • loss matrix $L_{kj}$

  • 최적의 해 : 손실함수를 최소화

    • 실제 클래스값에 대한 불확실성 $p(\mathbf{x}, \mathcal{C}_k)$

    • $E(L)=\sum_k \sum_j \int_{\mathcal{R}j}L{kj}p(\mathbf{x},\mathcal{C}_k)d\mathbf{x}$ 를 최소화하는 $\mathcal{R}_j$ 선택하는 문제

    • 즉, $\sum_kL_{kj}p(\mathcal{C}_k|\mathbf{x})$를 최소화하는 클래스 $j$에 할당

1.5.3 The reject option

• 거부 옵션: 오류 비율을 최소화하기 위해 결정을 내리기 힘든 지역에 대해서 결정 회피

• 임계값 $\theta$를 설정해서 사후 확률 $p(\mathcal{C}_k|\mathbf{x})$들 중 가장 큰 값이 \theta보다 작거나 같을 경우 해당 입력값 $\mathbf{x}$를 거부

• $\theta=1$로 설정하면 모든 예시가 거부되며 K클래스의 경우에는 $\theta < 1/K$로 설정하면 거부되지 않음

1.5.4 Inference and decision

• 분류 단계

  • inference: 훈련 집단을 활용하여 $p(\mathcal{C}_k|\mathbf{x})$에 대한 모델 학습

  • decision : 학습된 사후 확률들을 이용해 최적의 클래스 할당

  • discriminant function 활용: $\mathbf{x}$가 주어졌을 때 결정값을 돌려주는 함수 학습

• 결정 문제의 세 가지 접근법

  1. 생성 모델(generative model): 직간접적으로 입력값과 출력값의 분포를 모델링하는 방법

     • 순서

     • 결합 분포를 찾아야 하므로 손이 많이 간다.

  2. 판별 모델(discriminative model): 사후 확률 $p(\mathcal{C}_k|\mathbf{x})$를 계산하는 추론 문제를 훈 푸 결정 이론을 적용하여 각각의 입력 변수 $\mathbf{x}$에 대한 클래스를 구하는 방법

  3. ? : 각각의 입력값 $\mathbf{x}$를 클래스에 사상하는 판별 함수 $f(\mathbf{x})$를 찾는 방법. 확률론을 사용하지 않는다.

1.5.5 Loss functions for regression

1.6 Information Theory

---

• 정보량

  "한 변수가 특정 값을 가지고 있는 것을 확인했을 때 놀라움의 정도"라고 정의할 수 있겠다.

• Entropy

  확률변수의 상태를 결정짓는데 필요한 정보량의 평균

  $H(x) = -\sum_xp(x)log_2p(x)$

1.6.1 Relative entropy and mutual information