[AI class w7d3] Linear Model for Regression 선형회귀 TIL

오늘 내용은 PRML 3장의 내용이다.

 

선형 기저 함수 모델

가장 단순한 형태의 선형모델

 

$$ y(x, w) = w_0 + w_1x_1 + \dots + w_Dx_D $$

 

이 모델의 파라미터는 $\textbf w=(w_0,\dots,w_D)^T$ 벡터이다. 위 함수는 파라미터 $\textbf w$에 대해 선형일 뿐만 아니라 입력데이터 $\textbf x$에 대해서도 선형이다.

$\textbf x$에 대해 비선형인 함수를 만들고 싶다면?

 

$$ y(x, w) = w_0 + \sum_{j=1}^{M-1}w_j\phi{_j}(x) $$

$$ y(x, w) = \sum_{j=0}^{M-1}w_j\phi{_j}(x) = w^T\phi(x) $$

 

 

$\textbf x$에 대해 비선형인 함수 $\phi_j(\textbf x)$를 기저함수(basis function)이라고 부른다.

앞에서 몇 가지 기저함수를 이미 사용한 적이 있다.

• 다항식(polynomial) 기저함수
•  
• 
• 가우시안 기저함수
•  
• 
• 시그모이드(sigmoid) 기저함수
• 

최대우도와 최소제곱법 (Maximum Likelihood and Least Squares)

에러함수가 가우시안 노이즈를 가정할 때 최대우도로부터 유도될 수 있다는 것을 살펴본 적이 있다.

$t = y (\textbf{x,w}) + \epsilon$

 

• $y(\textbf x, \textbf w)$는 결정론적 함수(deterministic)
• $\epsilon$는 가우시안 분포 $\textbf N(\epsilon|0,\beta^{-1})$를 따르는 노이즈 확률변수

따라서 $t$의 분포는 다음과 같다.

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

 

제곱합이 손실함수로 쓰이는 경우(squared loss function), 새로운 $\textbf x$가 주어졌을 때 $t$의 최적의 예측값(optimal prediction)은 $t$의 조건부 기댓값임을 앞 강의에서 알아보았다.

$t$가 위의 분포를 따르는 경우 조건부 기댓값은 다음과 같다.

이제 파라미터인 $\textbf w$를 찾기 위해 최대우도추정법을 사용해보자.

• 입력값 $\textbf X=\textbf x_1, \dots, \textbf x_N$
• 출력값은 $\textbf t=t_1, \dots,t_N$

우도 함수는 (지도학습에서는 타겟값에 대해서 계산을 해야한다, 문맥상 명확할 경우에는 조건부의 X를 생략하기도)

 

$$p(t|\textbf{x, w}, \beta) = \prod_{n=1}^N\aleph(t_n|\textbf{w}^{T}\boldsymbol{\phi}({x}_{n}), \beta^{-1}) $$

 

로그 우도함수는

$$\ln{p}(t|\textbf{x}, \beta) = \sum_{n=1}^N\ln\aleph(t_n|\textbf{w}^{T}\boldsymbol{\phi}({x}_{n}), \beta^{-1}) $$

$$=\frac{N}{2}\ln\beta - \frac{N}{2}\ln(2\pi) -\beta{E}_D(\textbf{w})$$

 

$$E_D(\textbf{w}) = \frac{1}{2}\sum_{n=1}^N\{ t_n - \textbf{w}^{T}\boldsymbol{\phi}({x}_{n}) \}^2$$

 

->

로그 우도함수를 최대화시키는 $\textbf w$값은 $E_D(\textbf w)$로 주어진 제곱합 에러함수를 최소화시키는 값과 동일하다는 것을 알 수 있다.

우도를 최대화 시키는 $\textbf{w}$를 찾기 위해서는 우도를  $\textbf{w}$에 대해서 미분하고, 그것을 0으로 놓고 $\textbf{w}$에 대해서 풀면 된다.

 

$\textbf w$에 대한 기울기벡터(gradient vector)는

$$\nabla\ln{p({\bf t}|{\bf w}, \beta)} =\beta\sum_{n=1}^{N}\{t_n-{\bf w}^T\phi(x_n)\}\phi(x_n)^T$$

 

따라서 $\textbf w$의 최적값은

$${\bf w}_{ML} = (\Phi^T\Phi)^{-1}\Phi^T{\bf t}$$

위 식을 normal equations라고 부른다.

(선형대수 시간에 본 적 있는 normal equation)

 

* Normal equations 유도하기

 

 

* 하지만 모든 경우에 $\phi$의 역행렬이 존재하는 것은 아님!

• 하나의 조건을 만족하면 됨 : $\phi$ 의 모든 열들이 선형독립이면 역행렬이 존재한다.
• 항상 성립하는 것은 아니지만 많은 경우에 성립하며, 성립하지 않는 경우 데이터를 조절할 수 있다.

 

$$\Phi=\begin{pmatrix} \phi_0(x_1) & \phi_1(x_1) & \cdots & \phi_{M-1}(x_1)\\ \phi_0(x_2) & \phi_1(x_2) & \cdots & \phi_{M-1}(x_2)\\ \vdots & \vdots & \ddots & \vdots\\ \phi_0(x_N) & \phi_1(x_N) & \cdots & \phi_{M-1}(x_N)\\ \end{pmatrix}  $$

 

 

- 각각의 행은 하나의 데이터 포인트 (N개의 데이터 포인트가 있는 것)

- N개의 기저함수

->이 때 사용되는 Φ 는 N×M 크기의 행렬로 디자인 행렬(design matrix) 이라고 한다

 

Moore-Penrose pseudo-inverse

$$\Phi^{\dagger}\equiv(\Phi^T\Phi)^{-1}\Phi^T $$

 

 $w_0$를 명시적으로 구분을 해놓고  $w_0$에 대한 최대우도해를 구하게 되면

 

편향 파라미터 (bias parameter) $w_0$

 

$$E_D(\textbf{w}) = \frac{1}{2}\sum_{n=1}^{N}\{t_n - w_0 - \sum {j=1}{M-1} w_j\phi_j(\textbf{x}_{n})\}^2 $$

$$w_0 = \overline{t} - \sum_{j=1}^{M-1}w_j\overline{\phi}_j$$

 

$$\overline{t}= \frac{1}{N}\sum_{n=1}^{N}t_n$$

$$\overline{\phi}_j = \frac{1}{N}\sum_{n=1}^{N}\phi_j(\textbf{x}_{n})$$

 

 

$\beta$의 최적값은

$$\frac{1}{\beta_{ML}}=\dfrac{1}{N}\sum_{n=1}^{N}\{t_n-{\bf w_{ML}^T\phi(x_n)}\}^2$$

 

 

최대우도해의 기하학적 의미 (선형대수 복습)

• 벡터의 집합 (${\textbf x_1, \textbf x_2, \dots, \textbf x_n}$)에 대한 생성(span)

$$\text{span}({\textbf x_1, \textbf x_2, \dots, \textbf x_n})=\Bigg\lbrace\textbf v : \textbf v=\sum_{i=1}^{n}a_i\textbf x_i,a_i\in\mathbb{R}\Bigg\rbrace
$$

• 행렬의 치역(range)

행렬 $\textbf A\in\mathbb{R}^{m\times n}$의 치역 $\textbf R(\textbf A)$는 $\textbf A$의 모든 열들에 대한 생성(span)이다.

$$\textbf R(\textbf A)=\lbrace\textbf v\in\mathbb{R}^m:v=\textbf A\textbf x,\textbf x\in\mathbb{R}^n\rbrace
$$

• 벡터의 사영(projection)

벡터 $\textbf t \in\mathbb{R}^m$의 $\text{span}({\textbf x_1, \textbf x_2, \dots, \textbf x_n})(\textbf x_i\in\mathbb{R}^m)$으로의 사영(projection)은 $\text{span}({\textbf x_1, \textbf x_2, \dots, \textbf x_n})$에 속한 벡터 중 $\textbf t$에 가장 가까운 벡터로 정의된다.

$$\text{Proj}(\textbf t; {\textbf x_1, \textbf x_2, \dots, \textbf x_n})=\text{argmin}_{\textbf v\in\text{span}({\textbf x_1, \textbf x_2, \dots, \textbf x_n})}||\textbf{t-v}||_2
$$

$\text{Proj}(\textbf t; \textbf A)$은 행렬 $\textbf A$의 치역으로의 사영이다. $A$의 열들이 선형독립이면,

$\text{Proj}(\textbf t; \textbf A)=$ $\text{argmin}_{\textbf v\in R(A)}||\textbf{t-v}||_2$

$= A(A^TA)^{-1}A^T{t}$

($w_{ML}과 같은 형태$)

온라인 학습 (Sequential Learning)

배치학습 vs 온라인학습

데이터가 너무 큰 경우 계산이 힘들어짐 → 여러가지 대안 중 온라인 학습이 있음

가지고 있는 전체 데이터를 한꺼번에 사용하는 것이 아니라 조금씩 나누어서 업데이트 진행

-> 온라인 학습을 이용하면 데이터가 아무리 크더라도 학습을 진행할 수 있다.

Stochastic gradient decent

온라인 학습 방법 중 가장 많이 쓰이는 방법

에러함수가 $E=\sum_n E_n$ 이라고 하자.

 

$w^{\tau+1}=w^{(\tau)}-{\eta}{\nabla}E_n$

 

제곱합 에러함수인 경우

 

$w^{\tau+1}=w^{(\tau)}-{\eta}(t_n-{\bf w}^{(\tau)T}\phi_n)\phi_n$

 

 

$\phi_n=\phi(\textbf x_n)$

 

(실습) Stochastic gradient decent 이용하여 대규모의 선형회귀

import matplotlib.pyplot as plt
import seaborn as sns; sns.set()
import numpy as np

from sklearn.linear_model import LinearRegression
model = LinearRegression(fit_intercept=True)

N = 1000
M = 3
rng = np.random.RandomState(1)
rng.rand(N, M).shape
X = 10 * rng.rand(N, M)
np.dot(X, [1.5, -2., 1.]).shape
# (1000,)

rng = np.random.RandomState(1)
X = 10 * rng.rand(N, M)
y = 0.5 + np.dot(X, [1.5, -2., 1.])

model.fit(X, y)
print(model.intercept_)
print(model.coef_)
# 0.4999999999999689
# [ 1.5 -2.   1. ]

Normal Equations

import numpy.linalg as LA
normal_equation_solution = LA.inv(X.T@X)@X.T@y
normal_equation_solution
# array([ 1.52825484, -1.96886193,  1.03058857])

Small Memory Normal Equations (Online)

A = np.zeros([M, M])
b = np.zeros([M, 1])

for i in range(N):
    A = A + X[i, np.newaxis].T@X[i, np.newaxis]
    b = b + X[i, np.newaxis].T*y[i]
solution = LA.inv(A)@b
solution
# array([[ 1.52825484],
#        [-1.96886193],
#        [ 1.03058857]])

장점 : 메모리를 적게 사용

 

SGD(Stochastic Gradient Decent)

w = np.zeros([M, 1])
eta = 0.001
n_iter = 500

for i in range(n_iter):
    i = i % N
    neg_gradient = (y[i] - w.T@X[i, np.newaxis].T) * X[i, np.newaxis].T
    w = w + eta * neg_gradient
w
# array([[ 1.51033015],
#        [-1.93792375],
#        [ 1.0123695 ]])

 

규제화된 최소제곱법(Regularized Least Squares)

에러 함수의 정의

 

$$E({\bf w})=E_D({\bf w})+{\lambda}E_{W}({\bf w})$$

 

$lambda$ 는 regularization coefficient로서 $E_D({\bf w})$ 와 $E_{W}({\bf w})$ 사이의 가중치를 조절하게 된다.

 

두 부분으로 나누어져 있다고 볼 수 있는데,

이 식을 정리하면, 가장 단순한 형태는

 

$$E_W({\bf w})=\dfrac{1}{2}{\bf w^Tw}$$

 

$$E_D({\bf w})=\dfrac{1}{2}\sum_{n=1}^{N}\{t_n-{\bf w}^T\phi({\bf x}_n)\}^2$$

 

최종적인 에러함수는

 

$$E({\bf w})=\dfrac{1}{2}\sum_{n=1}^{N}\{t_n-{\bf w}^T\phi({\bf x}_n)\}^2+\dfrac{1}{2}{\bf w^Tw}$$

 

 

$\textbf w$의 최적값은

 

$${\bf w}=({\lambda}I+\Phi^T\Phi)^{-1}\Phi^T{\bf t}$$

 

 

일반화된 규제화 ($L^q$ norm)

 

$$E({\bf w})=\dfrac{1}{2}\sum_{n=1}^{N}\{t_n-{\bf w}^T\phi({\bf x}_n)\}^2+\dfrac{1}{2}{\sum_{j=1}^{M}|w_j|^{\;q}}$$

 

$\dfrac{1}{2}{\sum_{j=1}^{M}|w_j|^{\;q}}$ 부분을 라그랑지안이라고 생각을 하면, 이 부분을

 

$\sum_{j=1}^{M}{|w_j|^q}\le{\eta}$ 이 부등식을 만족시키는 제약 조건이라고 생각할 수 있다.

 

이 제약조건을 만족하면서 이 제약이 없는 앞부분 $\dfrac{1}{2}\sum_{n=1}^{N}\{t_n-{\bf w}^T\phi({\bf x}_n)\}^2$ 을 최소화시키는 해를 찾는 문제로 전환해서 생각할 수 있다.

 

 

• Constrained minimization 문제로 나타낼 수 있다. 

 

• 
• 파란 선 : 파란 선 위에 있는 w의 점들은 동일한 에러 함수 값들을 가짐을 표현 규제화가 없는 앞부분의 값 (contour)중간으로 갈 수록 에러 함수 값이 줄어드는 상황이라고 생각할 수 있음
• 제약 조건이 없다면 최적의 해는 가운데 점
• 왼쪽이 L2 norm, 오른쪽이 L1 norm
• 노란색 도형은 제약조건을 나타냄
• 제약 조건을 만족시키면서 에러 함수를 최소화 시키는 값은 $W^{*}$ 
• 꼭지점: $w$ 값이 0인 지점
• $q = 1$ 인 L1 norm을 규제화로 사용하는 경우 sparse model을 얻게 됨 (sparse하다 : parameter 중 여러 개의 값이 0)

 

편향-분산 분해 (Bias-Variance Decomposition)

모델이 과적합되는 현상에 대한 이론적인 분석

제곱합 손실함수가 주어졌을 떄의 최적 예측값

$$h(x)=\mathbb{E}[t|x]=\int{tp(t|x)\;dt}$$

 

손실함수의 기댓값

$$\mathbb{E}[L]=\int{\{y(x)-h(x)\}^2p(x)\;dx}+\iint{\{h(x)-t\}^2p(x,t)}\;dx\;dt$$

 

뒷부분은 우리가 어찌할 수 없는 부분 $\iint{\{h(x)-t\}^2p(x,t)}\;dx\;dt$

앞부분을 잘 조절해서 최소화 하려고 함

 

제한된 데이터셋 $D$만 주어져 있기 때문에 $h(\textbf x)$를 정확히 알 수는 없다.

대신 파라미터화 된 함수 $y(\textbf x, \textbf w)$를 사용하여 최대한 손실함수의 기댓값을 최소화하고자 한다.

 

제한된 데이터로 인해 발생하는 모델의 불확실성(uncertainty)를 어떻게든 표현해야 한다. 어떻게?

• 베이시안 방법: 모델 파라미터 $\textbf w$의 사후확률분포를 계산한다.
• 빈도주의 방법: 모델 파라미터 $\textbf w$의 점추정값을 구하고 여러 개의 데이터셋을 가정했을 때 발생하는 평균적인 손실을 계산하는 "가상의 실험"을 통해 점추정값의 불확실성을 해석한다.

특정 데이터셋 $D$에 대한 손실 $L(D)$을

$$L(D) = \{y(x;D)-h(x)\}^2$$

 

손실함수의 기댓값은 ($;D$ 는 데이터셋 $D$에 대한 dependency를 의미함

 

두 개의 알고리즘 중에서 어떤 것이 더 좋은 모델인가 판단하고자 한다면?

데이터 $D_1$부터 $D_L$이 주어졌을 때 이 값들의 평균을 생각해 본다.

 

$$\frac{1}{L}\sum_{l=1}^{L} [ \int\{y(x;D^(l))-h(\textbf x)\}^2p(x)d\textbf x + \text noise]$$

 $$= \int \mathbb {E}_D[\lbrace y(\textbf x; D)-h(\textbf x)\rbrace^2]p(x)\text{d}\textbf x+\text{noise}
$$

 

괄호 안 부분만 떼와서 전개

 

$$\{y(x;D)-E_D[y(x;D)]+E_D[y(x;D)]-h(x)\}^2\\=\{y(x;D)-E_D[y(x;D)]\}^2+\{E_D[y(x;D)-h(x)]\}^2\\\\+2\{y(x;D)-E_D[y(x;D)]\}\{E_D(x;D)-h(x)\}$$

 

 

 

정리하면

$${Expected}\;{loss} = (bias)^2 + variance + noise$$

 

$$(bias)^2=\int{\{E_D[y(x;D)]-h(x)\}^2p(x)\;dx}$$

 

$E_D[y(x;D)]$: 평균 예측값 이것이 얼마나 x로 부터 떨어져 있는가

 

$$variance = \int{E_D[\{y(x;D)-E_D[y(x;D)]\}^2]p(x)\;dx}$$

평균 예측값이 각각의 D가 주어져 있을 때의 예측값과 얼마나 떨어져 있는가?

 

• 모델의 자유도가 높을 수록 편향 값이 낮게 나오는 경향이 있음 (자유도 높음: 복잡도 높음)

-> 분산 부분은 커짐

• 편향과 분산은 서로 trade-off 하는 성질

$$noise=\iint{\{h(x)-t\}^2p(x,t)\;dx\;dt}$$

 

(예제)

$h(x)=sin(2\pi x)$

$$\overline{y}(x) =\frac{1}{L}\sum_{l=1}^{L}y^{(l)}(x)$$

$$(bias)^2 = \frac{1}{N}\sum_{n=1}^{N}\{\bar{y}(x_n)-h(x_n)\}^2$$

$$variance = \frac{1}{N}\sum_{n=1}^{N}\frac{1}{L}\sum_{l=1}^{L}\{y^{(l)}(x_n)-\bar{y}(x_n)\}^2$$

 

• 아래의 그림은 바이어스와 분산 사이의 trade-off 관계를 잘 나타내는 그림이다.
  • 하나의 샘플은 25개의 데이터로 구성된다. (일정 위치로부터 샘플 데이터를 추출하였다.)
  • 이러한 샘플 집합은 총 L=100 개로 구성된다. 각각의 학습 결과는 왼쪽 그림의 붉은 색 선이 된다.
  • 오른쪽 그림의 붉은 색 그래프는 왼쪽 샘플 집합 결과의 평균 값이다.
  • 오른쪽 그림의 녹색 선은 우리가 예측해야 할 sin⁡2π 곡선이다.
  • λ 값을 변화시켜 가면서 결과를 확인하였다.

• 왼쪽은 여러 데이터 학습 결과
• 오른쪽에서 빨간선은 $\bar y$, 초록선은 $h(x)$
• ln⁡λ 값이 큰 경우 높은 바이어스와 낮은 분산 값을 가진다.
  • 따라서 각각의 샘플 집합들 사이의 분산도가 작은 것을 알 수 있다.
  • 대신 실제 예측할 수 있는 값의 범위가 제한적이어서 최종 결과가 잘못 도출될 수도 있다.
  • 샘플 수를 충분히 확보하지 못하는 경우에는 가급적 이러한 안정된 모델을 선호하기도 한다.
• ln⁡λ 값이 작은 경우에는 낮은 바이어스와 높은 분산 값을 가진다.
  • 따라서 최종 결과로 사용된 예측 값(평균값)은 실제 결과와 매우 유사한 것을 확인할 수 있다.
  • 하지만 개별 샘플 집합의 결과를 보면 분산도가 매우 큰 것을 알 수 있다.
  • 따라서 샘플 수가 충분하지 못한 경우 실제 결과와 매우 큰 편차를 보이는 잘못된 결과를 얻을 수 있다.
  • 샘플 수가 충분하기만 하다면 이런 방식이 좋다.

->

$\lambda$ 값이 작아질수록 규제화가 적어져 모델의 자유도가 증가함

별개의 테스트 데이터 셋에 대한 결과

->

• 값이 작아질수록(왼쪽으로 갈수록) 편향은 줄어들고, 분산값은 늘어난다.
• 그리고 이 두개를 합한 값은 적절한 $\lambda$ 값에서 최소값을 가지게 된다 → 테스트 에러에 대해서 동일한 지점에서 최소값을 가진다.

* 적절한 모델의 자유도를 가질수 있게(적절한 $\lambda$값을 선택) 해야 새로운 데이터에 과적합되지 않는 좋은 모델을 만들 수 있다.

 

 

베이시안 선형회귀 (Bayesian Linear Regression)

빈도주의 방법으로 접근하게되면
모델의 불확실성을 나타내기 힘들다 (부자연스럽고 깔끔하지 못하다)

베이시안 방법을 이용하면 좀 더 깔끔하게 나타낼 수 있다.

• 파라미터 $\textbf w$의 사전확률을 다음과 같은 가우시안 분포라고 하자.

 

* 복습 (가우시안 분포를 위한 베이즈 정리)

$p(\textbf x)$와 $p(\textbf y|\textbf x)$가 다음과 같이 주어진다고 하자.

조건부 확률 $p(\textbf x|\textbf y)$의 평균과 공분산은 다음과 같다.

• 우도

다음과 같은 사전확률을 사용하면 식이 단순화된다.

이 경우에 사후확률은

사후확률의 로그값은 다음과 같다.

-> 사후확률을 최대화시키는 $\textbf w$ 의 값은 규제화가 포함되었을 때 에러를 최소화시키는 값과 같다.

* 베이시안 방법이 빈도주의 방법보다 일반적이고 강력한 방법론이다.

예측분포 (Predictive Distribution)

새로운 입력 $\textbf x$가 주어졌을 때 $\textbf t$를 예측