Least Square Method

Least Square Method

개요

• 최소자승법(최소제곱법, Least Square Method)은 관측된 데이터가 있을 때, 이 데이터를 가장 잘 설명하는 모델(직선/곡선/다항식/파라미터) 을 찾는 방법.
• 예측값과 실제값의 차이(오차/잔차 제곱합)가 최소가 되도록 모델 파라미터를 찾는 방법.
• RANSAC과 다르게 모든 데이터를 사용하여 에러를 최소화 하므로, 노이즈는 있지만 outlier가 거의 없는 데이터에 용이하다.

---

Linear Least Square

• 선형 회귀(Linear Regression)에서 최소자승법은 주어진 데이터 $\{(x_1,y_2),(x_2,y_2),\dots ,(x_n,y_n)\}$에 가장 잘 맞는 선형 모델을 찾는 것을 목표로 한다.

선형 모델 및 목적 함수 정의

선형 모델

• 선형 모델(직선)은 아래와 같이 정의할 수 있다.

$$y_i^{\prime }=a{x}_i+b$$

• $a$ : 직선의 기울기 (Slope)
• $b$ : $y$ 절편 (Intercept)
• $y_i^{\prime }$ : $x_i$ 에 대한 모델의 예측값

오차

• 실제 데이터 값 $y_i$와 예측값 $y_i^{\prime }$ 사이의 오차(잔차, Residual)를 다음과 같이 정의한다.

$$e_i=y_i-y_i^{\prime }$$ $$e_i=y_i-(a{x}_i+b)$$

목적 함수

• 최소자승법은 오차들의 제곱합을 최소화하는 $a$와 $b$를 찾는 것을 목표로 한다.
• 오차 제곱의 총 합을 목적함수 $S$로 두어 아래와 같이 정의한다.

$$S(a,b)=\sum _{i=1}^n{e}_i^2$$ $$S(a,b)=\sum _{i=1}^n(y_i-a{x}_i-b{)}^2$$

최소화를 위한 미분 정리

• 목적 함수 $S(a,b)$가 최소가 되기 위해서는 각각의 미지수 $a$와 $b$에 대해 편미분한 값이 0이 되도록 해야 한다.

$$\frac{\partial S}{\partial a}=0,\frac{\partial S}{\partial b}=0$$

$a$에 대한 편미분

• 목적함수 $S$의 $\sum$ 내부의 항을 $u=y_i-a{x}_i-b$ 라고 할 때, 합성함수의 체인 룰(Cahin rule)에 의해 다음과 같이 분리된다.

$$\frac{\partial (u^2)}{\partial a}=\frac{\partial (u^2)}{\partial u}\cdot \frac{\partial u}{\partial a}$$ $$\frac{\partial (u^2)}{\partial u}=2u$$ $$\frac{\partial u}{\partial a}=-x_i$$

• 분리된 두 항을 곱하여 최종 $a$에 대한 편미분은 다음과 같다.

$$\frac{\partial (u^2)}{\partial a}=2u\cdot -x_i=-2x_i(y_i-a{x}_i-b)$$

• $\sum$ 를 적용하여 정리하면 다음과 같다.

$$\frac{\partial S}{\partial a}=\sum _{i=1}^n[-2x_i(y_i-a{x}_i-b)]=0$$

• 양변을 $-2$로 나누고, $x_i$를 전개한다.

$$\sum _{i=1}^n(x_i{y}_i-a{x}_i^2-b{x}_i)=0$$ $$\sum _{i=1}^n{x}_i{y}_i-a\sum _{i=1}^n{x}_i^2-b\sum _{i=1}^n{x}_i=0$$

$b$에 대한 편미분

• $a$에 대한 편미분과 마찬가지로 $b$에 대한 편미분은 다음과 같이 계산할 수 있다.

$$\frac{\partial (u^2)}{\partial b}=\frac{\partial (u^2)}{\partial u}\cdot \frac{\partial u}{\partial b}$$ $$\frac{\partial (u^2)}{\partial b}=2u\cdot -1=-2(y_i-a{x}_i-b)$$

• $\sum$ 를 적용하여 정리하면 다음과 같다.

$$\frac{\partial S}{\partial b}=\sum _{i=1}^n\left[-2(y_i-a{x}_i-b)\right]=0$$

• 양변을 $-2$로 나누고, $\sum$를 각 항으로 분배한다.

$$\sum _{i=1}^n(y_i-a{x}_i-b)=0$$ $$\sum _{i=1}^n{y}_i-a\sum _{i=1}^n{x}_i-\sum _{i=1}^{n}b=0$$ $$\sum _{i=1}^n{y}_i-a\sum _{i=1}^n{x}_i-nb=0$$

• $nb$를 우변으로 이항하고, 양변을 데이터 개수 $n$으로 나눈다.

$$nb=\sum _{i=1}^n{y}_i-a\sum _{i=1}^n{x}_i$$ $$b=\frac{1}{n}\sum _{i=1}^n{y}_i-a\left(\frac{1}{n}\sum _{i=1}^n{x}_i\right)$$

• 여기서, 첫번 째 항과 두번 째 항은 각각 $y$와 $x$에 대한 평균 $\bar{y},\bar{x}$이므로 최종 식은 아래와 같다.

$$b=\bar{y}-a\bar{x}$$

연립방정식 정리

• $a$에 대한 편미분 식에 $b$에 대한 편미분 식을 대입하면 아래와 같다.

$$\sum _{i=1}^n{x}_i{y}_i-a\sum _{i=1}^n{x}_i^2-b\sum _{i=1}^n{x}_i=0$$ $$\sum _{i=1}^n{x}_i{y}_i-a\sum _{i=1}^n{x}_i^2-(\bar{y}-a\bar{x})n\bar{x}=0$$ $$\sum _{i=1}^n{x}_i{y}_i-a\sum _{i=1}^n{x}_i^2-n\bar{x}\bar{y}-an{\bar{x}}^2=0$$ $$\sum _{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}=a\sum _{i=1}^n{x}_i^2-an{\bar{x}}^2$$ $$\sum _{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}=a\left(\sum _{i=1}^n{x}_i^2-n{\bar{x}}^2\right)$$

• 이것을 $a$ 에 대해 정리하면 다음과 같다.

$$a=\frac{{\sum }_{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}}{{\sum }_{i=1}^n{x}_i^2-n{\bar{x}}^2}$$

공분산과 분산을 이용한 표현

• 연립방정식을 통해 정리한 $a$ 에 대한 식에서 수학적 성질에 의해 분모를 분산(Variance), 분자를 공분산(Covariance)로 나타낼 수 있다.
• $x$의 분산(편차 제곱의 합)은 다음과 같이 표현할 수 있다.

$$\text{Var}(x)=\sum _{i=1}^n(x_i-\bar{x}{)}^2=\sum _{i=1}^n{x}_i^2-n{\bar{x}}^2$$

• $x,y$ 의 공분산(두 변수 간의 관계)은 다음과 같이 표현할 수 있다.

$$\text{Cov}(x,y)=\sum _{i=1}^n(x_i-\bar{x})(y_i-\bar{y})=\sum _{i=1}^n{x}_i{y}_i-n\bar{x}\bar{y}$$

• 따라서, 최종 $a$와 $b$ 는 다음과 같이 나타낼 수 있다.

$$a=\frac{\text{Cov}(x,y)}{\text{Var}(x)}$$ $$b=\bar{y}-a\bar{x}$$

---

정규 방정식을 이용한 정리

• 정규 방정식(Normal Equation)은 최소자승법의 해를 직접 계산하기 위한 대수적 방법이다.

행렬 표현

• 데이터 집합을 행렬로 표현하여 다음과 같이 나타낼 수 있다.

$$X=\left[\begin{array}{cc}{x}_1& 1\\ x_2& 1\\ ⋮& ⋮\\ x_n& 1\end{array}\right],\theta =\left[\begin{array}{c}a\\ b\end{array}\right],y=\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$$

• 이것을 선형대수학의 행렬 곱셉 $y=X\theta$로 나타내면 다음과 같다.

$$y=X\theta$$ $$\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]=\left[\begin{array}{cc}{x}_1& 1\\ x_2& 1\\ ⋮& ⋮\\ x_n& 1\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]$$

• $X\theta =y$ 를 정확히 만족하는 해는 존재하지 않으므로, $X\theta \approx y$가 되도록하는 최적해를 찾아야 한다.

최소자승 문제 정의

• 오차 벡터를 다음과 같이 정의한다.

$$e=y-X\theta$$

• 최소자승법은 $||e|{|}^2$를 최소화 하므로 비용함수 $J(\theta )$를 다음과 같이 나타낼 수 있다.

$$J(\theta )=||y-X\theta |{|}^2$$ $$J(\theta )=(y-X\theta {)}^T(y-X\theta )$$

• 비용함수를 전개하면 다음과 같다.

$$J=y^{T}y-2{\theta }^T{X}^{T}y+{\theta }^T{X}^{T}X\theta$$

최소점 조건

• 최소점에서는 기울기가 0이므로 $\theta$ 에 대한 편미분을 아래와 같이 할 수 있다.

$$\frac{\partial J}{\partial \theta }=0$$ $$-2X^{T}y+2X^{T}X\theta =0$$

• 정리하면 아래의 정규방정식 형태가 나온다.

$$X^{T}X\theta =X^{T}y$$

최종 해 구하기

• 만약 $X^{T}X$의 역행렬이 존재한다면(Full Rank인 경우) 양변에 $(X^{T}X{)}^{-1}$를 곱하여 최소자승의 해를 구할 수 있다.
• 정규방정식을 이용하면 입력 데이터의 차원이 늘어나도 대수적 표현에 의해 간결하게 해를 구할 수 있다.

$$\theta =(X^{T}X{)}^{-1}{X}^{T}y$$

기하학적 의미

• 정규방정식은 직교 투영(Otrhogonal Projection)의 관점으로 해석할 수 있다.
• 열공간(Column Space) - Column Space는 모든 열 벡터의 선형결합으로 만들 수 있는 벡터들의 집합.
• $X\theta$에서 $X$는 열벡터들의 집합이고 $\theta$는 $X$에 곱해지는 계수이므로, $X\theta$는 $X$의 열벡터들의 선형결합이므로 항상 $X$의 열공간 안에 존재한다.
• 하지만 $y=X\theta$ 가 모든 데이터에 만족하는 해를 가진다면 $y$ 역시 $X$의 열공간 안에 존재해야 겠지만 일반적으로 $y$는 $X$의 열공간과 잔차(Residual)만큼 떨어져 있을 것이다.
• 따라서 잔차만큼 떨어진 $y$와 가장 가까운 점 $X\theta$를 $X$의 열공간 안에서 찾는다. 이때, 잔차 $r=y-X\theta$ 는 $X$의 열공간과 직교한다.
• 즉, $y$를 $X$ 열공간에 직교 투영 했을 때 만나는 $X$ 열공간 내부의 점이 잔차를 최소화하는 $X\theta$가 되고, 이때의 $\theta$가 해가 된다.

기하학적 의미 - 예시

• 예를 들어 $X$가 다음과 같으면 $X$의 열공간은 2차원(평면)을 나타낼 수 있다.

$$X=\left[\begin{array}{cc}1& 0\\ 0& 1\\ 1& 1\end{array}\right],\theta =\left[\begin{array}{c}{\theta }_1\\ {\theta }_2\end{array}\right]$$

• 즉 $X\theta$로 2차원 평면 위의 모든 점을 표현할 수 있다.
• $y$가 다음과 같이 구성되어 평면 밖에 있다고 할 때,

$$y=\left[\begin{array}{c}2\\ 1\\ 5\end{array}\right]$$

• 잔차 $r$ 벡터는 다음과 같이 정의되며, $X$의 열공간과 직교한다.

$$r=y-X\theta$$

• 벡터 내적의 성질에 의해 서로 직교하는 벡터의 내적 값은 0이 나온다.

$$X^{T}r=0$$

• 이 식을 정리하면 정규 방정식과 같게 된다.

$$X^T(y-X\theta )=0$$ $$X^{T}X\theta =X^{T}y$$