[ML] Linear Regression 1

KURTY·2023년 9월 17일
0

Machine Learning

목록 보기
1/15
post-thumbnail

Linear Regression

Linear regression → 연속적인 값을 추정

Normal equation → 선형대수학적으로 최적화된 해를 구함

Gradient descent → 값의 근사 (미분을 이용)

What is Linear Regression

input → model → output

(trainset) (prediction)

이때, cost를 최소화 하는 방향으로 학습을 시킴 → model에 대한 개선

Linear model

input (vector) → linear model (linear regression) → output (real number, scalar)

y^=θ0+θ1x1+θ2x2+...+θnxn=ΘTx\hat{y} = \theta_0 + \theta_1x_1 + \theta_2x_2 + ... + \theta_nx_n = \Theta^Tx
  • y^\hat{y}은 실제 yy에 대한 예측된 변수

  • nn은 feature의 수, nn차원, input에 들어있는 값의 수

  • xix_i의 경우 ii번째 feature 값

  • θj\theta_j의 경우 jj번째 model parameter, 각 feature에 대한 weight θ1,θ2,...,θn\theta_1, \theta_2, ..., \theta_n에 bias인 θ0\theta_0을 더한 값

  • Θ\Theta는 model의 parameter vector을 나타냄. model을 기술하는데 필요한 parameter

  • xx의 경우 feature vector이다. 이는 input이다. x0x_0의 경우 1이며, 이는 bias를 위한 값이다.

y^=θ0+θ1x1\hat{y} = \theta_0 + \theta_1x_1

  1. θ=[01]\theta = \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}
  2. θ=[12]\theta = \begin{bmatrix} -1 \\ 2 \\ \end{bmatrix}

이 때, bias θ\theta에 따라 직선의 기울기가 달라진다. parameter θ0\theta_0θ1\theta_1을 조정하여 주어진 data를 가장 잘 설명하는 parameter θ\theta를 구한다.

parameter θ\theta가 결정되는 순간 예측값은 하나의 직선으로 표현된다 → 우리의 prediction을 모든 영역에 대해 표현한다

실제값과 예측값의 차이를 error라고 할 때, error = yy^y - \hat{y}로 표현할 수 있다.

이때, error의 값은 거리값이므로 (yy^)2(y - \hat{y})^2로 제곱을 취하고, 이는 항상 양수값이다.

ii iierror(i)=(y(i)y^(i))2error^{(i)} = (y^{(i)} - \hat{y}^{(i)})^2로 표현할 수 있고, 각 sample에 대한 error을 정의할 수 있다.

i=15error(i)2=i=15(y(i)y^(i))2\sum_{i=1}^{5}error^{(i)2} = \sum_{i=1}^{5}(y^{(i)} - \hat{y}^{(i)})^2을 위의 1번 model과 2번 model에 대해 구할 수 있다.

1번 model의 error2error^2의 값을 20, 2번 model의 error2error^2의 값을 100이라 할 때, 주어진 data를 잘 설명하는 model은 1번 model이라고 할 수 있다.

Cost function

linear regression model에 대한 parameter은 어떻게 찾는가?

model을 training한다는 뜻은 적합한 주어진 training set에 가장 적합한 model을 찾아냄을 의미한다.

가장 먼저 현재 주어진 데이터에 대해 model이 얼마나 fit한지 판단해야 한다

regression problem에 사용되는 measure, error index, cost function은 다음과 같다

θ^=arg min RMSE(X,Θ)=arg min 1mi=1m(y(i)ΘTx(i))2=arg min MSE(X,Θ)=arg min 1mi=1m(y(i)ΘTx(i))2=arg min SSE(X,Θ)=arg mini=1m(y(i)ΘTx(i))2\hat{\theta} = arg \space min\space RMSE(X, \Theta) = arg\space min\space \sqrt{{1\over{m}}\sum_{i=1}^{m}(y^{(i)} - \Theta^Tx^{(i)})^2} \newline= arg \space min \space MSE(X, \Theta) = arg \space min\space {1\over{m}}\sum_{i=1}^{m}(y^{(i)} - \Theta^Tx^{(i)})^2 \newline = arg \space min\space SSE(X, \Theta) = arg \space min \sum_{i=1}^{m}(y^{(i)} - \Theta^Tx^{(i)})^2

여기서 ΘTx(i)=y^(i)\Theta^Tx^{(i)} = \hat{y}^{(i)}이다.

RMSE: Root Mean Of Squared error

MSE: Mean Of Squared error

SSE: Sum Of Squared error

RMSE, MSE, SSE를 최소로 만드는 argument의 해는 동일하다

Design matrix

  • regressor matrix, model matrix, data matrix
  • model은 y^=ΘTx\hat{y} = \Theta^Tx
  • training dataset은 (x(1),y(1)), (x(2),y(2)), (x(3), y(3)), ..., (x(m),y(m))(x^{(1)}, y^{(1)}), \space (x^{(2)}, y^{(2)}), \space (x^{(3)}, \space y^{(3)}), \space ..., \space (x^{(m)}, y^{(m)})
  • model prediction은 (y^(1)=ΘTx(1)), (y^(2)=ΘTx(2)), (y^(3)=ΘTx(3)), ... , (y^(m)=ΘTx(m)), (\hat{y}^{(1)} = \Theta^Tx^{(1)}), \space (\hat{y}^{(2)} = \Theta^Tx^{(2)}), \space(\hat{y}^{(3)} = \Theta^Tx^{(3)}), \space... \space , \space (\hat{y}^{(m)} = \Theta^Tx^{(m)}), \space
  • SSE는 (y(1)ΘTx(1))2+(y(2)ΘTx(2))2+(y(3)ΘTx(3))2+...+(y(m)ΘTx(m))2(y^{(1)} - \Theta^Tx^{(1)})^2 + (y^{(2)} - \Theta^Tx^{(2)})^2 + (y^{(3)} - \Theta^Tx^{(3)})^2 + ... + (y^{(m)} - \Theta^Tx^{(m)})^2

이를 input X=[x(1)Tx(2)Tx(m)T]X = \begin{bmatrix} x^{(1)T} \\ x^{(2)T} \\ \vdots \\ x^{(m)T} \\ \end{bmatrix}일 때, y^=[y^(1)y^(2)y^(m)]\hat{y} = \begin{bmatrix} \hat{y}^{(1)} \\ \hat{y}^{(2)} \\ \vdots \\ \hat{y}^{(m)} \\ \end{bmatrix} = XΘ=[x(1)Tx(2)Tx(m)T]ΘX \cdot \Theta = \begin{bmatrix} x^{(1)T} \\ x^{(2)T} \\ \vdots \\ x^{(m)T} \\ \end{bmatrix} \cdot \Theta로 표현할 수 있다.

SSE(Θ)=i=1m(y(i)ΘTx(i))2=yy^22=[y(1)y(2)y(m)][y^(1)y^(2)y^(m)]22=[y(1)y^(1)y(2)y^(2)y(m)y^(m)]22SSE(\Theta) = \sum_{i=1}^{m}(y^{(i)} - \Theta^Tx^{(i)})^2 \newline = \| y - \hat{y} \|^2_2 \newline = \| \begin{bmatrix} y^{(1)} \\ y^{(2)} \\ \vdots \\ y^{(m)} \\ \end{bmatrix} - \begin{bmatrix} \hat{y}^{(1)} \\ \hat{y}^{(2)} \\ \vdots \\ \hat{y}^{(m)} \\ \end{bmatrix} \|^2_2 \newline = \| \begin{bmatrix} y^{(1)} - \hat{y}^{(1)} \\ y^{(2)} - \hat{y}^{(2)} \\ \vdots \\ y^{(m)} - \hat{y}^{(m)} \\ \end{bmatrix} \|^2_2

Design matrix에 대해 training dataset이 mm개, feature vector xx의 차원이 nn일 때, mm개의 sample을 row vector로 한 design matrix XX로 표현할 수 있다.

Normal Equation

Geometric approach

Design matrix XX의 각 열을 xj\vec{x_j}라고 하면

y^=XΘ=[1x1...xn][θ0θ1,...θn]=θ01+θ1x1+θ2x2+...+θnxn\hat{y} = X\Theta = \begin{bmatrix} \rule{1pt}{5mm} & \rule{1pt}{\5mm} & & \rule{1pt}{5mm} \\ 1 & x_1 &...& x_n \\ \rule{1pt}{5mm} & \rule{1pt}{5mm} & & \rule{1pt}{5mm} \\ \end{bmatrix} \cdot \begin{bmatrix} \theta_0 \\ \theta_1,\\ ... \\ \theta_n \end{bmatrix} \newline = \theta_01 + \theta_1x_1 + \theta_2x_2 + ... + \theta_nx_n

즉, y^\hat{y}x1,x2,...,xnx_1, x_2, ..., x_n이 생성하는 hyperplane인 span{1,x1,...,xn}\{1, x_1, ... ,x_n\} 상에 존재한다

Residual(잔차) 또는 error의 크기 yy^\|y-\hat{y}\|을 최소화 하기 위해서는 위의 hyperplane과 erroryy^y - \hat{y}가 서로 수직이어야 한다

y^=XΘspan{x1,x2,...,xn}\hat{y} = X \cdot \Theta \in span\{ x_1, x_2, ..., x_n \}

y^\hat{y}spanspan이라는 평면 위에 존재해야 한다. 이 때, yyy^\hat{y}과의 거리가 가장 짧은 parameter θ\theta를 찾는다

이는 target인 yy와 prediction인 y^\hat{y}가 수직에 위치할 때 거리가 가장 짧다

즉, min yy^(yy^)span{x1,x2,...,xn}min \space \|y -\hat{y}\| \Leftrightarrow (y-\hat{y}) \perp span\{x_1, x_2, ..., x_n\}이다.

즉, 모든 column vector에 대해서 xjT(yy^)=0x^T_j \cdot (y-\hat{y})=0이 성립해야 한다. → (수직이므로 내적값은 0)

전체 mm의 sample에 대해 XT(yXθ)=0XTXθ=XTyX^T \cdot (y-X\theta) = 0 \Rightarrow X^TX\theta = X^Ty이고, θ^=(XTX)1XTy\hat{\theta} = (X^TX)^{-1}X^Ty이다

이는 θ^=(XTX)1XTyθ^=arg min SSE(θ)\hat{\theta} = (X^TX)^{-1}X^Ty \Leftrightarrow \hat{\theta} = arg \space min \space SSE(\theta)를 유도한 것이다.

Analytic approach

Sum of squared error (SSE)에 대해

SSE=i=1m(y(i)y^(i))2=yy^2=(yy^)T(yy^)SSE = \sum_{i=1}^{m}(y^{(i)}-\hat{y}^{(i)})^2 \newline = \|y - \hat{y} \|^2 = (y-\hat{y})^T(y-\hat{y})

y^=Xθ\hat{y} = X\theta를 사용하여

SSE(θ)=yTy2yTXθ+(Xθ)T(Xθ)=yTy2yTXθ+θTXTXθSSE(\theta) = y^Ty - 2y^TX\theta + (X\theta)^T(X\theta) = y^Ty - 2y^TX\theta + \theta^TX^TX\theta

SSE(θ)θ=2(XTXθXy)=0XTXθ=XTy\frac{\partial SSE(\theta)}{\partial \theta} = 2(X^TX\theta - Xy) = 0 \Rightarrow X^TX\theta = X^Ty

위 SSE를 미분하여 0이 나오는 값을 찾는다

따라서 우리는

θ^=(XTX)1XTy\hat{\theta} = (X^TX)^{-1}X^Ty

y^=X(XTX)1XTy\hat{y} = X(X^TX)^{-1}X^Ty

라는 normal equation을 얻을 수 있다.

Computational complexity

Normal equation의 계산

  • Normal equation에 의한 예측치 y^=X(XTX)1XTy\hat{y} = X(X^TX)^{-1}X^Ty
  • XRm×nX \in R^{m \times n}
  • XTXRn×nX^TX \in R^{n \times n}
  • (XTX)1(X^TX)^{-1}의 계산 복잡도 = O(n2.4)O(n^{2.4}) ~ O(n3)O(n^3)
  • Feature 수의 약 세제곱으로 계산 시간이 증가한다
profile
진짜 공부하자

0개의 댓글