[SLAM] Kalman filter and EKF(Extended Kalman Filter)

on SLAM

Kalman filter와 Extended Kalman filter에 대한 설명.

본 글은 University Freiburg의 Robot Mapping 강의를 바탕으로 이해하기 쉽도록 정리하려는 목적으로 작성되었습니다.

Kalman Filter & EKF (Extended Kalman Filter)

이번 글에서는 Kalman filter와 Kalman filter의 확장판인 EKF(Extended Kalman Filter)에 대해서 설명한다. 앞의 글에서 설명한 Bayes filter는 로봇의 상태(state)를 추정하기 위한 방법 중에 한가지 이며, 예측(prediction)단계와 보정(correction)단계의 두 단계로 나뉘어 진다.

\[\overline{bel}(x_t) = \int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\]\[bel(x_t) = \eta p(z_t \mid x_t)\overline{bel}(x_t)\]

Bayes filter에 대한 자세한 설명은 이전 글을 참고하기 바란다.

Gaussian 분포

\[p(x) = \frac{1}{\sqrt{2\sigma^2 \pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}\]\[p(\mathbf{x}) = \frac{1}{\sqrt{det(2\pi \Sigma)}}e^{-\frac{1}{2}(\mathbf{x}-\mu)^T\Sigma^{-1}(\mathbf{x}-\mu)}\]

Gaussian 분포는 single variable과 multi variable의 Gaussian 분포로 표현할 수 있으며, SLAM에서는 Vector를 이용하여 로봇의 상태(state), 센서 입력, 관찰 값 등을 표현하므로 multi variable의 Gaussian을 많이 사용한다. 따라서 Multi variable의 Gaussian 식은 숙지하는 것이 좋다.

선형 모델에서 Gaussian 분포의 변환

가장 기본적인 선형 모델은 다음과 같다. \[Y = AX+B\]

이 때, 확률변수 X가 Gaussian 분포를 갖고 있으며 다음과 같을 때, \[X \sim \mathcal{N}(\mu_x,\Sigma_x)\]

선형 변환 후의 확률변수인 Y의 분포는 다음과 같다. \[Y \sim \mathcal{N}(A \mu_x+B,A \Sigma_x A^T)\]

유도과정

X의 평균인 $\mu_x$ 는 선형 변환에 의해서 $A\mu_x+B$가 되는 것은 직관적으로 이해 할 수 있다. 그렇다면 covariance matrix은 어떻게 유도가 될까? 우선 covariance matrix의 정의로 부터 시작한다. \[\begin{aligned} \Sigma_y &= E((y-\mu_y)(y-\mu_y)^T)\\ &= E((y-(A\mu_x+B))(y-(A\mu_x+B))^T)\\ &= E(((AX+B)-(A\mu_x+B))((AX+B)-(A\mu_x+B))^T)\\ &= E([A(X-\mu_x)][A(X-\mu_x)]^T)\\ &= E(A(X-\mu_x)(X-\mu_x)^TA^T)\\ &= AE((X-\mu_x)(X-\mu_x)^T)A^T\\ &= A \Sigma_x A^T \end{aligned}\]

위의 유도처럼 Gaussian 분포의 선형변환에서의 covariance는 covariance의 정의로부터 $\Sigma_y = A \Sigma_x A^T$ 로 정의된다. 이 관계는 Kalman filter 뿐만 아니라 Gaussian을 사용하는 여러 분야에서 자주 사용되므로 기억해 두는것이 좋다.

Kalman Filter (KF)

\[\begin{aligned} x_t &= A_t x_{t-1} + B_t u_t + \epsilon_t\\ z_t &= C_t x_t + \delta_t \end{aligned}\]

여기서 구별해야 할 점은 $R_t$는 input의 noise가 아닌 process의 noise이다. $R_t$는 control input에서 들어오는 Gaussian noise가 한번의 선형 변환을 거친 전체 state인 $x_t$의 noise 이므로 process noise라고 부른다. 이때 control input인 $u_t$의 covariance는 $M_t$라고 표기한다.

위의 선형 모델을 이용한 motion model과 observation model은 다음과 같다.

\[p(x_t \mid u_t, x_{t-1}) = \frac{1}{\sqrt{det(2\pi R_t)}}e^{-\frac{1}{2}(x_t-A_t x_{t-1} - B_t u_t)^TR_t^{-1}(x_t-A_t x_{t-1} - B_t u_t)}\]\[p(z_t \mid x_t) = \frac{1}{\sqrt{det(2\pi Q_t)}}e^{-\frac{1}{2}(z_t-C_t x_{t})^T Q_t^{-1}(z_t-C_t x_{t})}\]

Motion model은 prediction step에서, observation model은 correction step에 적용된다.

\[\overline{bel}(x_t) = \int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\]\[bel(x_t) = \eta p(z_t \mid x_t)\overline{bel}(x_t)\]

t-1에서의 state의 확률은 motion model에 의해 t의 state의 확률이 결정되며(prediction step), prediction step에서 계산된 t에서의 state의 확률은 observation model에 의해서 보정된다. 이와같은 bayes filter식은 여러 확률 모델 분포를 모두 포함하고 있는 식이며, 그 중에서 모든 확률 분포를 Gaussian 확률 분포로 가정하는 모델이 Kalman filter이다. Gaussian으로 확률분포를 표현할 때, 간단히 평균(mean, $\mu$)와 분산(variance, $\Sigma$)으로 표현하기 때문에 두개의 파라미터만으로 분포를 표현할 수 있는 장점이 있다. Kalman filter 알고리즘은 다음과 같다. \[\begin{aligned} 1: & \text{Kalman filter}(\mu_{t-1}, \Sigma_{t-1}, u_t, z_t)\\ &[Prediction step]\\ 2: & \ \ \bar{\mu}_t = A_t \mu_{t-1} + B_t u_t\\ 3: &\ \ \bar{\Sigma_t} = A_t \Sigma_{t-1} A_t^T + R_t\\ &[Correction step]\\ 4: &\ \ K_t = \bar{\Sigma_t}C_t^T(C_t \bar{\Sigma_t}C_t^T + Q_t)^{-1}\\ 5: &\ \ \mu_t = \bar{\mu_t} + K_t(z_t - C_t \bar{\mu_t})\\ 6: &\ \ \Sigma_t = (I - K_t C_t)\bar{\Sigma_t}\\ 7: &\ \ \text{return} \ \ \mu_t, \Sigma_t\\ \end{aligned}\]

위 식은 Kalman filter algorithm을 보여주고 있다. Kalman filter는 bayes filter이기 때문에 prediction과 correction의 두 단계로 이루어 지며, 다소 복잡해 보이지만 한단계씩 이해하면 어렵지 않다.

첫번째 prediction 단계는 복잡하지 않다. 직관적으로 t-1의 평균은 motion model을 통해 t의 평균으로 계산되어 진다(2). 이때 $\mu, \Sigma$에 붙어있는 bar($\bar{\mu}, \bar{\Sigma}$)는 prediction step임을 의미한다. 그 다음으로 covariance는 위에서 설명한 Gaussian linear transformation의 의해 계산되어 진다(3). 이때 $R_t$는 process noise 이며, control input($u_t$)의 covariance가 $M_t$일 때 $R_t = B_t M_t B_t^T$이다. 일반적인 로봇시스템이나 자동차 시스템에서 control input은 wheel encoder로 부터 얻어지는 odometry 정보를 많이 이용하며, encoder 센서의 uncertainty가 $M_t$가 된다.

Correction 단계에서는 새로운 변수인 K(Kalman gain)이 추가된다. K는 현재 관측 데이터($z_t$)의 정확도에 따라 predicted state와 관측된 state(observation model을 이용하여 관측값으로부터 추정된 state)의 보정 비율을 결정하는 역활을 한다. 이때 $Q_t$가 observation의 covariance이다. 5번 식에서 ($z_t - C_t\bar{\mu_t}$)는 현재 실제로 관측된 데이터($z_t$)와 현재 위치로 예상되는 위치($\bar{\mu_t}$)에서 기대되는 관측값($C_t\bar{\mu_t}$)과의 차이를 Kalman gain(K)의 크기만큼 보정함으로써, 최종 Gaussian의 평균을 계산한다. 쉬운 이해를 돕기 위해 예를 들어보자. 우리의 로봇은 로봇의 위치에서 부터 주변 lanemark까지의 거리를 측정할 수 있는 로봇이라고 하자. 만약 encoder data와 motion model에 의해서 예상되는 로봇의 위치를 알고 있고, 주변의 lanemark의 위치를 이미 알고 있을 때, 예상되는 lanemark까지의 거리를 계산할 수 있다. 만약 이 예상되는 거리가 10m인데, 실제 lanemark까지의 거리가 9m로 측정이 된다면, 두 값이 오차인 1m는 odometry sensor로 부터 발생한 것일 수 도 있고, 거리를 측정하는 센서로 부터 발생한 것일 수도 있다. 이때 Kalman gain은 10m와 9m중 어느 데이터를 더 신뢰할지를 결정하는 파라미터로 볼 수 있다.

조금 더 쉽게 이해하기 위해 observation의 covariance인 $Q_t$가 무한대라고 해보자. covariance가 무한대라는 의미는 거리측정 센서로부터 얻어진 데이터는 전혀 신뢰 할 수 없다는 것을 의미한다. 이때 K는 0이 되며, $\mu_t = \bar{\mu_t}$가 된다. 즉, 관측된 센서 데이터는 신뢰할 수 없으므로, 예측된 로봇의 위치를 전적으로 신뢰하겠다는 것이다. 반대로 $Q_t$가 0라고 해보자. Covariance가 0이라는 의미는 센서 데이터를 100% 신뢰할 수 있음을 의미한다. 따라서 $Q_t$가 0이라면 $K = C_t^{-1}$이 되며, 5번식은 $\mu_t = C_t^{-1} z_t$가 된다. 즉 로봇의 거리 측정센서로 부터 얻어진 데이터($z_t$)를 전적으로 신뢰하여, 이로부터 로봇의 state를 추정하겠다는 의미이다. 6번식 covariace를 계산하는 부분도 이와 마찬가지로 $Q_t$가 무한대 일때는 최종 covariace는 prediction의 covariance를 그대로 사용하며, $Q_t$가 0일때는 관측데이터가 100%신뢰할 수 있음을 의미하므로 covariace는 0이 된다.

kalman fig

위 그림은 Kalman filter의 과정을 그림으로 표현하였다. 빨간색은 그래프는 prediction step에서 계산한 state의 Gaussian, 초록색은 observation으로 추정한 state의 Gaussian 분포이다. Kalman filter algorithm의 계산에 의해 두 Gaussian분포는 파란색의 최종 Gaussian 분포로 state가 결정된다. 이때 초록색 Gaussian의 variance가 빨간색보다 작기 때문에, 최종 결과는 measurement에 더욱 dominant하다.

Extended Kalman Filter (EKF)

Extended Kalman Filter는 아래와 같이 기존 KF의 선형 모델을 비선형 함수인 $g(u_t,x_{t-1})$와 $h(x_t)$로 바꿈으로써 비선형으로 확장한 모델이다. \[\begin{aligned} x_t &= g(u_t, x_{t-1}) + \epsilon_t &\leftarrow &x_t = A_t x_{t-1} + B_t u_t + \epsilon_t\\ z_t &= h(x_t) + \delta_t &\leftarrow &z_t = C_t x_t + \delta_t \end{aligned}\]

하지만 motion 모델과 observation 모델을 비선형으로 확장한 경우 문제가 발생한다. 다음 그림은 이러한 문제를 보여준다.

많은 문제에서 Gaussian 분포를 사용하는 이유는 평균(mean)과 분산(variance) 두개의 파라미터로 분포를 표현함과 동시에 데이터들의 분포를 정확히 반영할 수 있기 때문이다. 따라서 반복적인 계산을 통해 state를 추정하는 문제에서 입력이 Gaussian 분포일 때 출력 또한 Gaussian 분포이여야 한다. 왼쪽 그림은 선형 시스템에서의 입력과 출력을 보여준다. 선형 시스템이기 때문에 입력이 Gaussian 분포일 때 출력 또한 Gaussian 분포가 된다. 하지만 오른쪽 그림과 같이 비선형 시스템의 경우, 입력은 Gaussian 분포이지만 시스템의 비선형성에 의해 출력은 Gaussian 분포가 아니다. 따라서 이런 경우 출력을 평균과 분산으로 표현 할 수 없다. 이러한 문제를 풀기 위해서는 비선형함수를 선형화(Linearization) 시키는 과정이 필요하다.

선형화(Linearization)

EKF에서 비선형 함수를 선형화 시키기 위해서는 1차 Taylor 근사법(First order Talyer Expansion)을 사용한다. 선형 근사화된 model은 다음과 같다.

\[g(u_t, x_{t-1}) \approx g(u_t,\mu_{t-1}) + \frac{\partial g(u_t, \mu_{t-1})}{\partial x_{t-1}}(x_{t-1} - \mu_{t-1})\]\[h(x_t) \approx h(\bar{\mu_t}) + \frac{\partial h(\bar{\mu_t})}{\partial x_t} (x_t - \bar{\mu_t})\]

이떄 비선형 함수들을 state로 편미분하여 matrix를 생성하는데 이 matrix를 Jacobian 이라고 부르며, 두 matrix는 $G_t = \frac{\partial g(u_t, \mu_{t-1})}{\partial x_{t-1}}$, $H_t = \frac{\partial h(\bar{\mu_t})}{\partial x_t}$로 표기한다.

Jacobian Matrix

\[g(x) = \begin{bmatrix} g_1(x)\\ g_2(x)\\ \vdots\\ g_m(x) \end{bmatrix}\] \[G_x = \begin{bmatrix} \frac{\partial g_1}{\partial x_1} & \frac{\partial g_1}{\partial x_2} & \cdots & \frac{\partial g_1}{\partial x_n}\\ \frac{\partial g_2}{\partial x_1} & \frac{\partial g_2}{\partial x_2} & \cdots & \frac{\partial g_2}{\partial x_n}\\ \vdots & \vdots & & \vdots\\ \frac{\partial g_m}{\partial x_1} & \frac{\partial g_m}{\partial x_2} & \cdots & \frac{\partial g_m}{\partial x_n} \end{bmatrix}\]

아래 그림은 Talyer 근사화를 통해 선형화를 하였을 때의 특징을 보여준다.

외쪽 그림은 입력의 분산(variance)가 큰 경우를 보여주며, 오른쪽 그림은 분산이 작은 경우를 보여준다. 분산이 큰 경우 실제 비선형 함수 출력의 평균값과 선형화를 통해 계산된 평균값의 차이가 큰 것을 알 수 있다. 반면 분산이 작은 경우는 선형화를 통해 계산된 평균값이 실제 평균값과 유사함을 알 수 있다. 따라서 선형화 시 선형화 지점으로 부터 멀수록(분산이 클수록) 실제 함수를 반영하지 못한다.

EKF Algorithm

선형화된 motion 모델과 observation 모델을 이용한 bayes filter는 다음과 같다.

\[p(x_t \mid u_t, x_{t-1}) \approx \frac{1}{\sqrt{det(2\pi R_t)}}e^{-\frac{1}{2}(x_t-g(u_t, \mu_{t-1}) - G_t(x_{t-1} - \mu_{t-1}))^TR_t^{-1}(x_t-g(u_t, \mu_{t-1}) - G_t(x_{t-1} - \mu_{t-1}))}\]\[p(z_t \mid x_t) \approx \frac{1}{\sqrt{det(2\pi Q_t)}}e^{-\frac{1}{2}(z_t-h(\bar{\mu_t})-H_t (x_t-\bar{\mu_t}))^T Q_t^{-1}(z_t-h(\bar{\mu_t})-H_t (x_t-\bar{\mu_t}))}\]

KF와 마찬가지로 $R_t, Q_t$는 process noise와 measurement noise이다. EKF 알고리즘은 다음과 같다. \[\begin{aligned} 1: & \text{Extended Kalman filter}(\mu_{t-1}, \Sigma_{t-1}, u_t, z_t)\\ &[Prediction step]\\ 2: & \ \ \bar{\mu}_t = g(u_t, \mu_{t-1})\\ 3: &\ \ \bar{\Sigma_t} = G_t \Sigma_{t-1} G_t^T + R_t\\ &[Correction step]\\ 4: &\ \ K_t = \bar{\Sigma_t}H_t^T(H_t \bar{\Sigma_t}H_t^T + Q_t)^{-1}\\ 5: &\ \ \mu_t = \bar{\mu_t} + K_t(z_t - h(\bar{\mu_t}))\\ 6: &\ \ \Sigma_t = (I - K_t H_t)\bar{\Sigma_t}\\ 7: &\ \ \text{return} \ \ \mu_t, \Sigma_t\\ \end{aligned}\]

EKF 알고리즘과 KF 알고리즘의 차이는 KF에서 선형함수를 통해 평균($\mu$)를 구하는 2,5번 식에서 선형함수 대신 비선형 함수가 사용되었다. 그리고 3,4번 식에서 선형함수의 $A_t, C_t$ Matrix는 Jacobian matrix인 $G_t, H_t$로 수정되었다. 여기서 $R_t$는 process noise이며, control input의 covariance matrix가 $M_t$일 때 $R_t = V_t M_t V_t^T$이다. 여기서 $V_t$는 $g(u_t,\mu_{t-1})$를 control input인 $u_t$로 편미분한 Jacobian이다.

여기까지 EKF에 대한 설명을 마친다. 다음 글에서는 실제 robot의 모델을 통해 EKF를 이해해보자.

본 글을 참조하실 때에는 출처 명시 부탁드립니다.


[SLAM] Motion Model & Observation model

on SLAM

Motion model과 observation model 설명.

본 글은 University Freiburg의 Robot Mapping 강의를 바탕으로 이해하기 쉽도록 정리하려는 목적으로 작성되었습니다.

Motion Model & Observation Model

이번 글에서는 SLAM의 framework에서 중요한 Motion model과 Observation model에 대해서 설명한다. 이전 post(Bayes Filter)에서 설명한 것처럼 SLAM은 다음과 같이 recursive bayes filter의 식으로 표현할 수 있다. \[\begin{aligned} bel(x_t) &= p(x_t \mid z_{1:t},u_{1:t}) \\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\\ \end{aligned}\]

bayes filter식은 prediction step 과 correction step 으로 나눌 수 있다.

Prediction step

\[\overline{bel}(x_t) = \int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\]

$\overline{bel}(x_t)$ 는 prediction 단계의 state를 나타낸다. prediction step은 control input 데이터($u_t$)와 이전 step의 로봇의 state에 대한 데이터($x_{t-1}$)를 이용하여 현재의 로봇 state($x_t$)의 확률을 추정하는 과정이다. 이 과정에서 $p(x_t \mid x_{t-1}, u_{t})$ 는 입력($u_t$)에 의한 로봇의 움직임을 추정하여 현재의 state의 확률을 계산하는 model이기 때문에 Motion model 이라고 부른다.

Correction step

\[bel(x_t) = \eta p(z_t \mid x_t)\overline{bel}(x_t)\]

Correction step은 prediction step에서 예상한 로봇의 위치를 보정하는 단계이다. 즉, input data($u_t$)를 이용하여 현재의 로봇의 위치를 예측하고, 그 위치에서 얻어진 센서 데이터($z_t$)로 부터 예측된 로봇의 위치를 보정하는 단계이다.

이때 $p(z_t \mid x_t)$ 는 observation model 이라 하며, 현재 예측한 state($x_t$)에서 실제 얻어진 센서 데이터($z_t$)가 얻어질 확률을 의미한다.

Motion Model

\[p(x_t \mid x_{t-1}, u_{t})\]

Motion model은 control input($u_t$)이 이전 state($x_{t-1}$)을 현재 state($x_t$)로 변화시킬 사후확률(posterior probability)를 의미한다. 실제 로봇의 응용에서 motion model은 크게 2가지로 분류된다.

odometry model은 로봇 혹은 자동차의 바퀴에 달린 wheel encoder의 센서 데이터를 이용한 모델이며, velocity model은 imu와 같은 관성 센서를 이용한 model이다. velocity model은 wheel encoder와 같은 odometry model을 사용할 수 없을 때 주로 사용하며, odometry model이 velocity model보다 더 정확한 편이다.

odometry based

위의 그림은 motion model에 의한 state의 uncertainty를 나타낸다. 점이 많이 분포되거나, 어두운 부분일 수록 확률이 높은 부분이다. 로봇의 진행방향과 회전방향에 대한 uncertainty의 크기에 따라서 다른 확률 분포를 보인다. 맨 왼쪽의 그림은 고르게 분포되었을 경우이며, 가운데 그림은 진행방향의 uncertainty가 더 큰경우이며 마지막의 오른쪽 그림은 회전방향의 uncertainty가 진행방향보다 큰 경우를 보여주고 있다.

Observation Model

\[p(z_t \mid x_t)\]

observation model은 현재 state에서의 센서 데이터의 확률을 의미한다. 로봇 분야에서 많이 사용하는 Laser Scanner데이터를 이용하여 model을 표현하면 다음과 같다. \[\mathbf{z_t} = \{z_t^1,...,z_t^k\}\]

$\mathbf{z_t}$ 는 각 laser scan 데이터의 그룹을 나타내는 vector이며, $z_t^1$ ~ $z_t^k$는 t 시점에서의 각 scan 데이터를 의미한다. 따라서 최종 observation model은 다음과 같이 표현된다. \[p(z_t \mid x_t) = \prod_{i=1}^{k} p(z_t^i \mid x_t)\]

즉 observation은 현재 state에서의 각 센서 데이터들의 확률의 곱으로 표현된다.

자세한 Motion & Observation model에 대해서는 Freiburg 강의-bayes filter를 참조하기 바란다.


[SLAM] Bayes filter(베이즈 필터)

on SLAM

SLAM framework에서 Bayes filter에 대한 설명.

본 글은 University Freiburg의 Robot Mapping 강의를 바탕으로 이해하기 쉽도록 정리하려는 목적으로 작성되었습니다.

SLAM(Simultaneous Localization and Mapping)

SLAM은 simultaneous localization and mapping의 줄임말로 위치추정(localization)과 지도생성(mapping)을 동시에 하는 연구분야를 의미한다. 이는 닭이 먼저냐 달걀이 먼저냐의 문제와 비슷하다. 자기의 위치를 추정하기 위해서는 주변환경에 대한 정보가 필요하다. 반면에 로봇이 얻을 수 있는 데이터를 이용해서 지도를 만들기 위해서는 로봇이 자신의 위치가 어디에 있는지를 정확히 알아야 한다. 따라서 위치를 알 수 없으면 지도를 만들 수 없고, 반대로 지도가 없으면 위치를 알 수 없다. 이러한 문제를 풀기 위해서 지도의 생성과 위치 추정을 동시에 수행하는 것이 SLAM이다.

State Estimation

State estimation은 로봇에 주어지는 입력과, 로봇의 센서로부터 얻어지는 데이터로부터 현재의 로봇의 위치인 state와 주변환경에 대한 지도를 추정 방법이다. \[p(\mathbf{x}\mid \mathbf{z}, \mathbf{u})\]

위의 식은 기본적인 state estimation을 의미한다. $\mathbf{x}$ 는 로봇의 위치 및 지도(주변의 land mark들의 위치)를 의미하는 vector이며, $\mathbf{z}$는 로봇의 센서로부터 얻어지는 데이터로 observation이라고 부르며, $\mathbf{u}$ 는 센서의 움직임을 제어하는 입력으로 control input이라고 부른다. state estimation은 이러한 control input과 observation의 데이터를 통해 현재의 위치와 지도를 추정한다.

Bayes Theorem

베이즈 정리는 확률론과 통계학에서 두 확률변수의 사전확률(prior)과 사후확률(posterior) 사이의 관계를 나타내는 정리이다. \[P(A \mid B) = \frac{P(B \mid A)P(A)}{P(B)}\]

$P(A)$ 는 A의 prior로, 사건 B에 대한 어떠한 정보를 알지 못하는 것을 의미한다. $P(A \mid B)$ 는 B의 값이 주어진 경우 A의 posterior이다. $P(B \mid A)$ 는 A가 주어졌을 때 B의 조건부 확률이다.

bayes 정리의 자세한 내용은 wiki를 참고한다.

Recursive Bayes Filter

위에서 설명한 state estimation은 bayes filter의 과정으로 설명할 수 있으며, 각 step의 state를 반복적으로 계산함으로써 계산할 수 있기 때문에 recursive bayes filter로 부른다. 전체적인 recursive bayes filter의 식은 다음과 같다. \[\begin{aligned} bel(x_t) &= p(x_t \mid z_{1:t},u_{1:t}) \\ &= \eta p(z_t \mid x_t, z_{1:t-1}, u_{1:t})p(x_t \mid z_{1:t-1},u_{1:t}) \\ &= \eta p(z_t \mid x_t)p(x_t \mid z_{1:t-1},u_{1:t}) \\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, z_{1:t-1}, u_{1:t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t-1}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\\ \end{aligned}\]

위의 식은 recursive bayes filter를 유도하는 과정을 모두 표현하고 있기 때문에 다소 복잡해 보인다. 우선 전체적인 식을 이해하기 위해서 맨 처음과 맨 마지막 식만을 보면 다음과 같다. \[\begin{aligned} bel(x_t) &= p(x_t \mid z_{1:t},u_{1:t}) \\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\\ \end{aligned}\]

$bel(x_t)$ 는 처음부터 현재까지의 observation( $z$ )와 control input( $u$ )을 알고 있을 때 현재 state( $x_t$ )의 확률을 의미한다. 위의 식에서 $bel(x_t)$ 의 식은 $bel(x_{t-1})$ 의 integral로 표현되어 있기 때문에 만약 $p(z_t \mid x_t)$ 와 $p(x_t \mid x_{t-1}, u_t)$ 에 대한 정보를 알고 있다면 반복적인 계산을 통해 현재 state의 확률을 계산할 수 있음을 알 수 있다. 여기서 $p(z_t \mid x_t)$ 는 현재의 state에서 센서 데이터의 확률인 observation model이며, $p(x_t \mid x_{t-1}, u_t)$ 은 현재의 control input에 대해 이전 state에서 현재 state로의 update를 나타내는 motion model를 의미한다. 위의 식을 Recursive bayes filter라고 한다. Recursive bayes filter는 Kalman filter의 기본이 되는 식이다. 다음은 recursive bayes filter의 유도과정을 간단하게 살펴본다. 유도에 관심이 없고 전체적인 흐름만 보고자 한다면 다음 설명은 넘어가도 좋다.

Recursive Bayes Filter의 유도과정

\[\begin{aligned} bel(x_t) &= p(x_t \mid z_{1:t},u_{1:t}) \\ \end{aligned}\]

control input과 observation을 알고 있을 때 현재 state의 확률을 의미하는 belief의 정의 \[\begin{aligned} bel(x_t) &= p(x_t \mid z_{1:t},u_{1:t}) \\ &= \eta p(z_t \mid x_t, z_{1:t-1}, u_{1:t})p(x_t \mid z_{1:t-1},u_{1:t}) \\ \end{aligned}\]

기본적인 bayes rule이다. 현재 시점 t의 observation은 현재의 state에서 얻어진 data이므로 따로 분리하여 위와 같이 정의한다. $p(x_t \mid z_{1:t-1},u_{1:t})$ 는 t시점까지의 control input, 그리고 t-1시점 까지의 observation을 알고 있을 때의 현재 시점 t의 state, $p(z_t \mid x_t, z_{1:t-1}, u_{1:t})$ 는 현재 state에서 얻어진 observation의 확률이다. $\eta$ 는 normalize term이다. \[\begin{aligned} bel(x_t) &= \eta p(z_t \mid x_t, z_{1:t-1}, u_{1:t})p(x_t \mid z_{1:t-1},u_{1:t}) \\ &= \eta p(z_t \mid x_t)p(x_t \mid z_{1:t-1},u_{1:t}) \\ \end{aligned}\]

Markov Assumption은 현재의 state는 바로 이전 state에 의해서만 영향을 받는다는 것이다. 즉 이전 state를 결정하기 위한 데이터들은 알지 못해도 이전 state만 알고 있다면 현재 state를 결정할 수 있다는 것이다. Markov assumtion에 의해 $p(z_t \mid x_t, z_{1:t-1}, u_{1:t})$ 는 $p(z_t \mid x_t)$로 표현 할 수 있다. 왜냐하면 현재의 observation은 현재의 state인 $x_t$에만 영향을 받으며, $z_{1:t-1}$ 와 $u_{1:t}$는 현재 state $x_t$에만 영향을 미치기 때문이다. \[\begin{aligned} bel(x_t) &= \eta p(z_t \mid x_t)p(x_t \mid z_{1:t-1},u_{1:t}) \\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, z_{1:t-1}, u_{1:t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ \end{aligned}\]

다음 식은 total probability(전체확률) 법칙에 의해 위와같이 전개된다. 전체확률 법칙은 간단하게 표현하면 다음과 같다. \[P(A) = \int_B P(A \mid B)P(B) dB\]

즉 A는 $x_t$ 이며, B는 $x_{t-1}$ 이다. \[\begin{aligned} bel(x_t) &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, z_{1:t-1}, u_{1:t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ \end{aligned}\]

위 과정은 앞에서 설명한 Markov assumtion에 의해서 $x_t$ 에 영향을 미치는 $x_{t-1}$ 과 $u_t$만 남기고 정리된다. \[\begin{aligned} bel(x_t) &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t-1}) dx_{t-1}\\ \end{aligned}\]

이 과정 또한 Markov assumption으로 $p(x_{t-1} \mid z_{1:t-1}, u_{1:t})$ 에서 $u_t$는 t-1시점의 state인 $x_{t-1}$ 에 영향을 미치지 않기 때문에 제거 될 수 있다. \[\begin{aligned} bel(x_t) &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t})p(x_{t-1} \mid z_{1:t-1}, u_{1:t-1}) dx_{t-1}\\ &= \eta p(z_t \mid x_t)\int_{x_{t-1}}p(x_t \mid x_{t-1}, u_{t}) bel(x_{t-1}) dx_{t-1}\\ \end{aligned}\]

따라서 위와 같은 과정을 통해 최종적으로 식은 위와같이 정리되며, recursive bayes filter의 식으로 정리된다.


[Jekyll] github blog를 google에서 검색되도록 설정하기

on Jekyll

github io와 같은 개인 블로그를 google과 naver, 그리고 daum과 같은 포탈사이트에서 검색 가능하도록 만드는 방법

이 글은 다음 blog의 글을 참고하였습니다.

네이버 블로그와 같은 포탈의 블로그 서비스를 사용할 경우 자동으로 검색이 가능하지만, github와 같은 플렛폼을 사용할 경우에는 직접 각 포탈에 검색이 가능하도록 등록을 해 주어야 한다. 이 글에서는 블로그의 글이 google, daum, naver에서 검색 가능하도록 등록하는 방법에 대해서 설명한다.

1. Sitemap 생성

sitemap을 google에 등록해 두면 주기적으로 크롤링을 통해 url을 연결시킨다. 우선 sitemap을 생성하는 방법에 대해서 설명한다. ruby를 통해 jekyll 홈페이지를 만든 경우에는 sudo gem install jekyll-sitemap 의 명령어를 이용해 플러그인을 사용할 수 있다. 하지만 여기서는 플러그인을 사용하지 않는 방법을 설명한다.

블로그의 /root 경로에 /sitemap.xml 파일을 만들고 아래의 내용을 복사해 넣는다. 반드시 root 디렉토리에 넣어야 한다.


---
layout: null
---
<?xml version="1.0" encoding="UTF-8"?>
<urlset xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.sitemaps.org/schemas/sitemap/0.9 http://www.sitemaps.org/schemas/sitemap/0.9/sitemap.xsd" xmlns="http://www.sitemaps.org/schemas/sitemap/0.9">
  {% for post in site.posts %}
    <url>
      <loc>{{ site.url }}{{ post.url }}</loc>
      {% if post.lastmod == null %}
        <lastmod>{{ post.date | date_to_xmlschema }}</lastmod>
      {% else %}
        <lastmod>{{ post.lastmod | date_to_xmlschema }}</lastmod>
      {% endif %}

      {% if post.sitemap.changefreq == null %}
        <changefreq>weekly</changefreq>
      {% else %}
        <changefreq>{{ post.sitemap.changefreq }}</changefreq>
      {% endif %}

      {% if post.sitemap.priority == null %}
          <priority>0.5</priority>
      {% else %}
        <priority>{{ post.sitemap.priority }}</priority>
      {% endif %}

    </url>
  {% endfor %}
</urlset>

git과 commit으로 블로그를 업데이트 후 blog주소/sitemap.xml로 접속했을 때 아래와 같은 화면이 나와야 정상적으로 sitemap이 등록된 것이다.

sitemap

sitemap에는 각 해당 글의 lastmod, sitemap.changefreq, sitemap.prioritye 등의 정보가 설정되는데, 이것은 각 글의 맨 위에 다음과 같이 sitemap의 옵션을 추가해 줌으로써 추가적으로 설정 가능하다. 설정이 없을 때의 default 설정은 sitemap.xml에 정의되어 있다.


---
layout: post
title:  "제목"
date:   2016-03-14 12:00:00 
lastmod : 2016-03-15 12:00:00
sitemap :
  changefreq : daily
  priority : 1.0
---

changefreq를 너무 짧게 하면 빈번한 접속으로 안좋은 영향을 미칠 수도 있다고 하니 적당히 하루 혹은 일주일로 하면 좋을 것 같다. 추가적으로 blog주소/sitemap.xml을 실행했을 때 위와 같이 나오지 않는 경우는 아마 주소링크에 &와 같은 특수기호가 있는 경우가 있을 수 있다. 예를들어 파일의 이름이 URL의 링크 주소가 되는데, 만약 파일이름이 한글일 경우 url의 주소에 %의 기호가 들어가 있다. 이럴경우 xml이 정상적으로 해석하지 못한다. 따라서 최대한 URL의 링크가 되는 파일이름은 영문으로 만들고, 특수기호는 최대한 사용하지 않는 것이 좋다.

2. RSS Feed 생성

Rss feed는 naver와 daum에 등록하기 위함이다. sitemap.xml과 마찬가지로 root 디렉토리에 /feed.xml파일을 생성하고 아래의 코드를 복사한다.


---
layout: null
---
<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom">
  <channel>
    <title>{{ site.title | xml_escape }}</title>
    <description>{{ site.description | xml_escape }}</description>
    <link>{{ site.url }}{{ site.baseurl }}/</link>
    <atom:link href="{{ "/feed.xml" | prepend: site.baseurl | prepend: site.url }}" rel="self" type="application/rss+xml"/>
    <pubDate>{{ site.time | date_to_rfc822 }}</pubDate>
    <lastBuildDate>{{ site.time | date_to_rfc822 }}</lastBuildDate>
    <generator>Jekyll v{{ jekyll.version }}</generator>
    {% for post in site.posts limit:30 %}
      <item>
        <title>{{ post.title | xml_escape }}</title>
        <description>{{ post.content | xml_escape }}</description>
        <pubDate>{{ post.date | date_to_rfc822 }}</pubDate>
        <link>{{ post.url | prepend: site.baseurl | prepend: site.url }}</link>
        <guid isPermaLink="true">{{ post.url | prepend: site.baseurl | prepend: site.url }}</guid>
        {% for tag in post.tags %}
        <category>{{ tag | xml_escape }}</category>
        {% endfor %}
        {% for cat in post.categories %}
        <category>{{ cat | xml_escape }}</category>
        {% endfor %}
      </item>
    {% endfor %}
  </channel>
</rss>

3. robots.txt 생성

robots.txt파일에 sitemap.xml파일의 위치를 등록해 두면 검색엔진의 크롤러들이 홈페이지를 크롤링하는데 도움을 주게 된다고 한다. root 디렉토리에 /robots.txt 파일을 만들고 아래와 같이 입력한다.

User-agent: *
Allow: /

Sitemap: http://jinyongjeong.github.io/sitemap.xml

User-agent는 허용할 검색엔진 명을 넣게 된다. 따로 설정하지 않으면(*) 모든 검색엔진을 허용하게 된다. 자세한 내용은 http://dveamer.github.io/homepage/SubmitSitemap.html를 참고한다.

4. 사이트 등록

Google (google search console등록)

Google Search Console를 접속한다.

이 사이트에서 본인의 블로그를 등록해야 google에서 검색이 가능하다.

속성추가 버튼을 눌러 본인의 blog 주소를 입력하여 사이트를 등록한다.

크롤링 > sitemaps 메뉴를 열어 sitemap 추가 버튼을 눌러 만들어 두었던 sitemap.xml파일을 제출한다.

제출이 완료되면 sitemap.xml파일이 등록된 것을 확인할 수 있으며 색인이 접수 중임을 알 수 있다.

네이버 웹마스터 도구에 접속한다.

로그인하여 구글과 비슷하게 블로그 주소를 등록하는 과정을 거친다. 그 후 “사이트 소유 확인”이라는 과정을 거치게 되는데 HTML 파일을 다운받아 블로그의 root에 업로드 하여 확인하는 과정을 거치게 된다. 이 과정을 거치면 google의 analystics와 유사한 기능을 사용할 수 있는 것 같다. 그 다음에 RSS를 등록하는 과정이 필요하다. 왼쪽 메뉴에서 요청 > RSS제출 을 클릭해서 URL을 포함한 주소인 블로그URL/feed.xml을 입력한다.

추가적으로 요청 > 사이트맵제출로 들어가서 google과 마찬가지로 블로그URL/sitemap.xml을 입력해서 sitemap을 등록시켜 준다.

Daum

DAUM 검색등록에 접속 후 로그인한다.

등록 탭에서 블로그 RSS등록을 선택하고 블로그URL에 본인의 URL을 입력하고 확인버튼을 누른다.

이전 블로그에서 보면 feed.xml파일을 올리는 RSS 부분이 있었는데 지금 확인해보니 URL을 입력하는 창만 뜬다.

우선 URL만 등록해보도록 한다.

위의 과정을 거치고 최종으로 반영되기 까지 어느정도의 시간이 걸린다. 일주일정도 시간이 흐른뒤에 확인해보도록 하자.


[Ubuntu] Ubuntu Sublime text 설치하기

on Ubuntu,

Sublime text 설치 후 셋팅하는 방법을 설명한다.

SublimeText3

1. sublime text 설치하기

sublimetext 에서 다운로드 후 설치
ppa 이용한 설치 방법
sudo add-apt-repository ppa:webupd8team/sublime-text-3
sudo apt-get update
sudo apt-get install sublime-text-installer

2. Project 를 위한 패키지 구성

Package Control 설치

메뉴 View -> Show Consol (Ctrl+`) 실행후 console 창을 열어서 아래의 명령어 입력후 에디터 재시작 Sublime text 버전에 따라 다르게 입력

Sublime Text 2

import urllib2,os; pf='Package Control.sublime-package'; ipp = sublime.installed_packages_path(); os.makedirs( ipp ) if not os.path.exists(ipp) else None; urllib2.install_opener( urllib2.build_opener( urllib2.ProxyHandler( ))); open( os.path.join( ipp, pf), 'wb' ).write( urllib2.urlopen( 'http://sublime.wbond.net/' +pf.replace( ' ','%20' )).read()); print( 'Please restart Sublime Text to finish installation')

Sublime Text 3

import urllib.request,os; pf = 'Package Control.sublime-package'; ipp = sublime.installed_packages_path(); urllib.request.install_opener( urllib.request.build_opener( urllib.request.ProxyHandler()) ); open(os.path.join(ipp, pf), 'wb').write(urllib.request.urlopen( 'http://sublime.wbond.net/' + pf.replace(' ','%20')).read())

YcmdCompletion 패키지

1. YcmdCompletion 설치
2. Ycmd server 설치
git clone https://github.com/Valloric/ycmd.git
cd ycmd
git submodule update --init --recursive

./build.py --all
3. YcmdCompletion 설정
HMAC key 생성

Command Pallete (Ctrl+Shift+p) -> Ycmd: Create HMAC keys

Sublime Text의 Ycmd Completion 설정

Preferences -> Package Settings -> YcmdCompletion -> Settings - Default 클릭 후 YcmdCompletion.sublime-settings 파일의 주석 처리된 부분을 풀어서 다음과 같이 입력

{
    "ycmd_server": "http://127.0.0.1",
    "ycmd_port": 8080,
    "HMAC": "위에서 생성한 HMAC key",
    "use_auto_start_localserver": 1,
    "ycmd_path": "/home/USERNAME/ycmd/ycmd",
    "languages": ["cpp", "python"],
}
Sublime Text의 Syntax Specific 추가

Preferences -> Settings - More -> Syntax Specific - User 클릭 후 C++.sublime-settings에 다음 내용 추가(c++ 프로젝트 혹은 파일을 열었을 때 C++.sublime-settings을 열 수 있다.

{
    "auto_complete_selector": "source - (comment, string.quoted)",
    "auto_complete_triggers": [ 
        {"selector": "source.c++", "characters": "."},
        {"selector": "source.c++", "characters": "::"},
        {"selector": "source.c++", "characters": "->"} 
    ]
}
Sublime project 생성하기
cd build
cmake . -G "Sublime Text 2 - Unix Makefiles"

project의 root의 CMakeLists.txt에 다음 항목 추가

set(CMAKE_EXPORT_COMPILE_COMMANDS "ON")
set(CMAKE_GENERATOR "Unix Makefiles" CACHE INTERNAL "" FORCE)
set(CMAKE_EXTRA_GENERATOR "Sublime Text 2" CACHE INTERNAL "" FORCE)
Ycmd default_settings.json 파일 설정

위에서 복제한 ycmd server directory에서 default_settings.json 파일 내용 중 아래 부분 변경

  "global_ycm_extra_conf": "/home/ycmd/ycmd/.ycm_extra_conf.py",
  "confirm_extra_conf": 0,
  "hmac_secret": "위의 HMAC key 입력",
.ycm_extra_conf.py 파일 설정하기
compilation_database_folder = os.path.expanduser("~/projects/naver/build")
YCM-Generator 이용해서 .ycm_extra_conf.py 만들기

YCM-Generator를 github repository로부터 복제

git clone https://github.com/rdnetto/YCM-Generator.git

프로젝트 디렉토리에 .ycm_extra_conf.py 만들기

cd YCM-Generator
./config_gen.py 프로젝트디렉토리

위의 프로그램을 수행하면 프로젝트디렉토리의 root에 .ycm_extra_conf.py파일이 생성됨


Pagination