칼만필터 알고리즘은 제어 시스템에서 시작되었습니다. 제어시스템에서 칼만필터의 역할은 State equation에 Noise가 발생했을 때, Noise를 제거하고 State를 예측합니다. (State equation에 대한 내용은 여기를 참조 해주세요.)
노이즈는 데이터가 튀게 만드는 성질이 있습니다. 즉, 칼만필터는 튀는 데이터를 제거하는 역할을 한다고 할 수 있습니다.이러한 성질을 응용하여 칼만필터가 Learning Equation에 응용됩니다.
:max_bytes(150000):strip_icc():format(webp)/EMA-5c535d5a46e0fb000181fa56.png)
Data가 정상적으로 들어오다가 갑자기 튀는 Noise들을 생각해볼 수 있습니다. 이러한 Noise의 영향을 최소화 하기 위해서 근처에 10개의 Data만 가지고 평균 값 계산한다고 하면 다음과 같이 써줄 수 있을 것입니다.
\mu_k=\sum_{i=1+k}^{k+10} \frac{x_i}{10}incremental mean을 이용해서 풀어주게 되면, 머신러닝에서 쓰이는 간단한 형태의 식으로 표현이 가능해집니다.
\mu_k = \mu_{k-1} +\frac{1}{n}(x_k-x_{k-n})모든 데이터에 동일한 가중치가 부여된다고 볼 수 있습니다. 여기서, 최신에 들어오는 데이터에 가중치를 더 주게되면 최신 데이터 위주로 평균 값이 나타나게 될 것입니다. 이를 Exponential Weighted Filter라고 불러주기도 합니다.
\begin {aligned}\mu_k &=\mu_{k-1}*\alpha +(1-\alpha)x_k \\\mu_{k-1} &=\mu_{k-2}*\alpha +(1-\alpha)x_{k-1} \\ \mu_k &= \alpha^k\mu_0 +(1-\alpha)x_k+\alpha (1-\alpha)x_k+ \cdots \\\therefore \mu_k &= \alpha^k\mu_0 + \sum_{n=0}^{k-1} \alpha^n(1-\alpha)x_{k-n} \sim \sum_{n=0}^{k-1} \alpha^n(1-\alpha)x_{k-n} \\ &=\frac{1-\alpha^n}{\sum_{ n=0}^{k-1} \alpha^n}\sum_{n=0}^{k-1} \alpha^n(1-\alpha^n)x_{k-n} \sim \frac{1}{\sum_{ n=0}^{k-1} \alpha^n}\sum_{n=0}^{k-1} \alpha^n(1-\alpha^n)x_{k-n} \tag{1}\end {aligned}(1)의 식을 보게되면, 최종적으로 가중치가 Exponential하게 부여 된 것을 알 수 있고, 화학공학에서는 Discount rate로 생각해 볼 수 있습니다.
결국 시간이 지남에 따라 초기에 부여되었던 값은 0으로 수렴하게 되고, 최근에 값에는 Weight가 가장 크게 부여가 된 형태가 되는 것을 확인할 수 있습니다.
Moving average에서 Exponential 하게 감소시키는 것을 확인할 수 있었습니다. 이 경우에는 \alpha 가 이미 정해져 있어서, 시간에 따라 변화 되지는 않은 형태 였습니다. 하지만, 갑자기 튀는 데이터가 발생한다면?Moving average도 큰 변화가 발생할 것입니다.
이에 Weighting 되는 정도도 시간에 따라 가변 (Adaptive)시키면서 조절해나가는 것이 칼만필터라고 말할 수 있습니다.
먼저, 시스템에 대하여 다음과 같이 주어졌다고 보겠습니다.
x_k \in \mathbb{R}^n , y_k \in \mathbb{R}, A\in \mathbb{R}^{n \times n},w_k\in \mathbb{R}^{n},y\in \mathbb{R} \\\begin {aligned}x_{k+1} &=A x_k +w_k \\y_k &=Hx_k+v_k\end {aligned}w_k, v_k 는 x_k, y_k 에 대한 White noise 입니다. 각 Noise는 아래의 확률 분포를 따른 다고 가정합니다.
w_k \sim N(0,Q), v_k \sim N(0,R)
칼만필터의 알고리즘은 공분산을 Predict 하고 Correct하는 과정입니다. 이러한 공분산에 대한 물리적 의미는 가우시안 프로세스에서 다뤘습니다.
Predict하는 공분산 값을 A prior estimate(Prediction), Correct한 공분산 값을 Posteriori estimate(Correction)라고 MIT와 같은 1류 학교에서는 말한다고 합니다. 이는 베이지안 추론이 나오게 되면서 칼만필터는 다시 베이지안 추론이론을 이용하여 재해석이 되면서 위와 같은 명칭이 사용됩니다.
\begin {align}\hat{x_k}^{-} & = A\hat{x_{k-1}} \tag {2} \\P_k^{-} & = AP_{k-1}A^T +Q \\\end {align}\begin {align}K_k &=P_k^-H^T(HP_kH^T+R)^{-1} \\ \tag{3}\hat{x_k} &=\hat{x_k}^-+K_k(z_k-H\hat{x_k}^-) \\P_k &= (I-K_kH)P_k^- \end {align}
-는 Predict 된 것을 말하며 우리는 P라는 공분산 Matrix를 추정하는 것을 목표로 하고 있습니다. 각 Update에 대한 rule은 (2)번에서 대략적인 추정을 하고, (3)번에서 추정된 Matrix를 Correct하는 과정을 거쳐 P^{-} \rightarrow P 로 update해가는 과정입니다.
먼저 A priori와 Posteriori는 각각 다음과 같이 정의 해줄 수 있습니다. P_k^{-} =cov(x_k - \hat{x_k}^-), P_k=cov(x_k-\hat{x_k} (모델 값과, 관측 값)
\begin {align}P_k & = cov(x_k-\hat{x_k}) \tag {4} \\\hat {x_k} & = \hat {x_k} ^-+K_k(y_k-Hx_k^-) = \hat {x_k} ^-+K_k(Hx_k+v_k-Hx_k^-) \because y_k=Hx_k+v_j \\P_k &=cov(x_k-(\hat {x_k} ^- +K_k(Hx_k+v_k-Hx_k^-) ) \\& =cov((I-K_kH_k)(x_k-\hat {x_k} ^-)+K_kv_k ) \text { cov-> linear function} \\& = cov(I-K_kH_k)(x_k-\hat {x_k} ^-)+cov(K_kv_k ) \\\end {align}\begin{align}P_k = (I-K_kH_k)cov (x_k-\hat{x_k}^-)(I-K_kH_k)^T + K_kcov(v_k)K_k^T \tag {5}\end{align}(4)에서 (5)번식으로 넘어갈 때, Covariance를 안쪽으로 풀어주게 됩니다. 이는 Expectation 값이 Linear하고, K_k H_k 가 Symmetric하기 때문에 가능한 성질입니다. (5)에서 (6)으로 넘어갈 때는 식의 정의를 이용하면 쉽게 이해할 수 있습니다.
\begin{align}P_k &= (I-K_kH_k)P_k^-(I-K_kH_k)^T + K_kR_kK_k^T \tag{6} \\ & =P_k^- -K_kH_kP_k^--P_kH_k^TK_k^T+K_k(H_kP_k^-H_k^T+R_k)K_k^T \\ & =P_k^- -K_kH_kP_k^--P_kH_k^TK_k^T+K_k(S_k)K_k^T \\\because S_k & =H_kP_k^-H_k^T+R_k\end{align}Covariance matrix는 Symmetric하며, 전체를 최소화 시켜줘야 합니다. Matrix를 최소화 시킨 다는 것은 스칼라형태로 만들어 준 다음 해석을 해줘야합니다. Matrix의 스칼라화는 임의의 Vector를 이용해 줄 수 있습니다.
|| v||=1 , v \in R^n, v^T A v \rightarrow matrix크기
또한, Symmetric한 경우 Matrix는 Vector 연산으로 간단하게 표현해줄 수 있는데, 이는 Matrix 크기와 관련이 있게 됩니다.
P_k =XX^T \\||P|| = tr(XX^T)=X^TX \\\therefore \frac{\partial tr (P_k)}{\partial K_k}=0 \rightarrow \text{ Covariance를 최소화 하는 조건} \\\frac{\partial tr (P_k)}{\partial K_k}=-2(H_kP_k^-)^T+2K_kS_k=0 \\P_k=(I-K_kH_k)P_k^- \\<맨 마지막식 추가 예정>
\begin{align}P_k^- &= cov(x_k-\hat{x_k}^-) =cov(Ax_{k-1}+w_k-A\hat{x_{k-1}}^- )\\& =A cov(x_{k-1}-\hat{x_{k-1}})A^T+cov(w_k) \\&= AP_{k-1}^-A^T+Q\end {align}여기 까지 각 Kaman filter에 대한 Update 방식에 대하여 알아보았습니다.
댓글
댓글 쓰기