논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

Gaussian Processes for Signal Strength-Based Location Estimation

1. Introduction

무선 장치나 로봇의 위치를 파악하기 위한 한 방법으로 무선 신호의 세기 정보를 이용하는 방법이 있습니다. 이 방법은 실내 환경의 영향으로 인하여 무선 신호의 전달을 예측하기가 힘들다는 점에 그 어려움이 있습니다. 따라서 적은 수의 샘플만으로 전체 영역의 신호 세기를 알기 위한 모델을 개발하는 것이 중요한 주제입니다.

기존의 signal strength localization은 두가지 부류로 나뉩니다. 첫번째는 미리 AP를 위치를 알고 있다는 가정 하에, 신호가 AP와의 거리에 따라 어떻게 퍼지는지를 모델링하는 것입니다. 하지만 이는 벽이나 가구 등에 영향을 받기 때문에 부정확할 수밖에 없습니다. 두번째 방법은 특정 위치에서의 샘플을 채취하여 캘리브레이션 데이터로 활용, measurement likelihood를 계산하는 방법입니다. 샘플을 채취하였기 때문에 해당 위치의 주변부에서는 정확도가 높을 것이지만, 샘플이 없는 부분에서의 추측은 어떤 모델을 사용하느냐에 따라 그 성능이 좌우됩니다.

이 논문에서는 이를 위하여 Gaussian processes (GP)를 이용합니다. GP는 non-prametric 모델로서 트레이닝 데이터를 기반으로 만들어진 함수 위에서 Gaussian distribution을 추정해낼 것입니다. GP가 이 문제에 적당한 이유를 몇가지 들어보자면,

  • Continuous locations : 데이터의 위치를 표현하는데 이산적(discrete)으로 표현할 필요가 없습니다. 이는 트레이닝 데이터도 마찬가지로 적용됩니다.
  • Arbitrary likelihood models : GP는 non-parametric regression 모델이기 때문에 비선형의 특징을 갖는 신호 확산에 대해서 넓은 영역에 걸쳐 근사화하는 것이 가능합니다.
  • Correct uncertainty handling : GP는 또한 추정한 위치에서의 불확실성 또한 제공합니다.
  • Consistent parameter estimation : GP의 파라미터는 트레이닝 데이터로부터 학습이 가능합니다.

사실 GP를 이용한 연구는 Schwaighofer에 의해서 먼저 이루어졌지만 이 논문에서는 위치를 추정하는데 Bayesian filter를 사용하여 확장하였습니다. 물론 이 연구에서 AP의 위치는 사용되지 않습니다.

2. Gaussian Processes for Modeling Signal Strength Measurements

Bayes filter에서 중요한 점은 관측 모델(observation model)입니다. 이것은 위치에서의 관측 값을 만들어내는 likelihood 모델을 의미합니다. 먼저 어떻게 GP를 이용하여 관측 모델을 생성하는지 알아보도록 합시다.

A. Preliminaries

먼저 트레이닝 샘플을 $ D = { (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) } $ 이라고 하여봅시다. 이 것은 노이즈를 포함한 샘플링 과정 $ y_i = f(x_i) + \epsilon $ 에서 채취된 것입니다. $ x_i \in R^d $ 는 입력 샘플이고 $ y_i $는 그에 해당하는 목표 값 혹은 관측 값입니다. $ \epsilon \sim N(0, \sigma_n^2) $ 인 노이즈입니다. 표현을 쉽게 하기 위하여 n개의 입력 벡터 $x_n$을 모아서 d * n 크기의 $ X $, $y_i$를 모아서 벡터 $ y $ 라고 표현합니다.

GP는 함수 트레이닝 데이터 D로부터 생성된 함수 f로부터 사후 분포(posterior distribution)을 추정합니다. 이 분포는 트레이닝 데이터를 이용하여 파라미터 없이 표현됩니다. GP의 아이디어는, 여러 위치에서의 함수 값은 서로 연관이 있으며(correlated), 이 연관성은 특정 covariance function, 혹은 커널 함수 $ k(x_p, x_q) $에 기반하고 있다는 가정에 있습니다. 커널 함수를 어떤 것으로 사용할 것인지는 사람마다 다르지만 보통 가우시안 커널을 사용합니다.

$$k(x_p, x_q) = \sigma_f^2 \exp ( - \frac{1}{2 l^2} |x_p - x_q|^2)$$

여기서 $ \sigma_f^2 $는 신호의 분산을, $ l $ 은 지점 사이에 얼마나 강한 연광성이 있는지를 정해주는 길이 값입니다. 두 개 모두 GP가 얼마나 부드럽게 추정할지를 결정하는 파라미터입니다.

우리는 완벽한 함수 값을 알 수가 없고, 노이즈가 섞인 관측 값만을 알기 때문에 여기에 노이즈에 관한 항을 추가합니다. 결과적으로 covariance는 다음과 같이 됩니다.

$$cov(y_p, y_q) = k(x_p, x_q) + \sigma_n^2 \delta_{pq}$$

델타 함수를 이용하여 $ p = q $일 때만 노이즈가 추가하도록 하였습니다. 이는 함수 형태로 다음과 같이 나타내기도 합니다.

$$cov(y) = K + \sigma_n^2 I$$

결국 이 식은 사전 분포(prior distribution)을 나타냅니다. 즉, 커널 함수에 의하여 각 입력값 $ X $에 대하여 $ K $를 생성할 수 있고, 그에 해당하는 $ y $ 또한 위의 식으로 covariance로 갖습니다. 따라서 $ y \sim N(0, K + \sigma_n^2 I) $ 입니다.

하지만 우리가 원하는 것은 $ X, y $가 주어졌을 때의 사후 분포입니다. 이는 $ X $의 평균과 분산값 $ \mu_x, \sigma_x^2 $를 이용하여 다음과 같이 계산됩니다.

$$p(f(x_*) | x_*, X, y) = N(f(x_*) ; \mu_{x_*}, \sigma^2_{x_*}), \text{where} \\
\mu_{x_*} = k_*^T (K + \sigma_n^2 I)^{-1} y \\
\sigma_{x_*}^2 = k(x_*, x_*) - k_*^T(K + \sigma_n^2I)^{-1} k_*$$

여기서 $ k_* $$ x_* $ 와 트레이닝 데이터 $ X $ 사이의 covariance 벡터이고, $ K $$ X $ 끼리의 covariance 행렬입니다.

B. Application to Signal Strength Modeling

논문의 주제로 돌아온다면 $ X $는 위치를, $ y $는 그 위치에서의 신호 세기를 나타내게 됩니다. GP의 posterior는 트레이닝 데이터로부터 신호 세기와 그 위치까지 추정하게 됩니다. 위의 식에 따라서 모든 위치에 대하여 신호세기와 그 분산을 추정할 수가 있는데, 데이터 포인트가 적게 분포된 곳일 수록 추정된 분산이 커지게 됩니다.

논문에서는 수식의 하이퍼파라미터의 값으로 $ l = 17.8, \sigma_f^2 = 8.2, sigma_n^2 = 4.0 $을 사용한 예를 들고 있습니다. 이들 파라미터의 값을 정하는 것은 매우 중요한 문제입니다.

C. Hyperparameter Estimation

이들 하이퍼파라미터 $ \theta = (\sigma_n^2, l, \sigma_f^2) $는 트레이닝 데이터를 이용한 Maximum log-likelihood 방법으로 결정할 수 있습니다. 수식은 다음과 같습니다.

$$\log p(y | X, \theta) = - \frac{1}{2} y ^T (K + \sigma_n^2I)^{-1}y - \frac{1}{2} \log | K + \sigma_n^2 I | - \frac{n}{2} \log 2 \pi$$

그리고 이 식을 conjugate gradient descent (LBFGS)를 이용하여 최대화시키는 파라미터를 찾습니다. 그 과정에서 사용되는 파라미터의 각 편미분 식은 다음과 같습니다.

$$\frac{ \partial } {\partial \theta_j} \log p(y | X, \theta ) = \frac{1}{2} \text{tr}((K^{-1}y)(K^{-1}y^T \frac{\partial K}{\partial \theta_j}))$$

$$\frac{\partial K}{\partial \sigma_f^2} = 2 \sigma_f \exp (- \frac{1}{2} (\frac{d}{l})^2)$$

$$\frac{\partial K}{\partial l} = \sigma_f \exp (- \frac{1}{2} (\frac{d}{l})^2) \frac{d^2}{l^3}$$

$$\frac{\partial K}{\partial \sigma_n^2} = 2 \sigma_n \delta_{pq}$$

$$\text{where } d= x_p - x_q$$

D. Zero Mean Offset

Gaussian process는 기본적으로 평균이 0인 프로세스입니다. 트레이닝 데이터를 적용하지 않았을 때 모든 지점에서 그 평균은 0 입니다. 하지만 트레이닝 데이터를 적용하게 될 때에는, 데이터의 평균이 0이 아닐 수도 있습니다. 따라서 이를 감안하기 위해 간단하게는 트레이닝 데이터에서 평균을 뺀 값을 사용하는 방법을 사용합니다.

마찬가지로 이 WiFi 신호 세기 문제에는 신호의 확산을 반영해줄 필요가 있습니다. AP에서 멀리 떨어진 지점에서는 신호세기가 0이 되는 것이 정상이지만, 어느정도 신호 세기가 높을 만한 지점인데도 트레이닝 데이터가 없어 zero-mean 문제로 0에 가깝게 추정하게 됩니다. 이를 간단한 확산 모델을 적용하여 방지하도록 합니다.

$$ss = m || x - x_{AP} || + b$$

$ x$ 는 현재 위치를, $ x_{AP} $는 AP의 위치입니다. $ m $ 는 확산의 정도를, $ b $ 는 AP에서 측정된 신호세기를 나타냅니다. 마지막으로 $ss $$x $위치에서의 신호 세기입니다.

그리고 트레이닝 데이터로써 실제로 측정한 값들을 $x$$ss$로 이용하여 $m, b, x_{AP}$를 계산합니다. 이 때에도 역시 conjugate gradient descent 방법을 사용합니다.

3. Bayesian Filtering on Mixed Graph / Free Space Representations

Bayes filter를 이용하여 현재 위치를 찾는 문제는 지금까지 측정된 신호세기들 $ z_{1:t} $를 이용하여 현재 위치 $ x_t $를 찾는 문제입니다. 이를 식으로 표현하면 아래와 같습니다.

$$p(x_t | z_{1:t}) \propto p(z_t|x_t) \int p(x_t | x_{t-1}) p(x_{t-1} | z_{1:t-1}) dx_{t-1}$$

여기서 $p(x_t | x_{t-1})$는 위치 이동에 관한 모델이고, $p(z_t | x_t)$는 관찰된 값에 대한 likelihood 모델입니다. 이 likelihood 모델에 Guassian process를 사용할 것입니다. 여기서는 $ n$개의 각 AP마다 GP를 따로 생성한 다음에 이들을 조합하여 부드러운 likelihood 모델을 생성합니다.

$$p(z_{t[1:n]}|x_t) = (\prod_{t=1}^n p(z_{t[i]} | x_t))^\gamma$$

여기서 $ \gamma \in [0:1] $가 smoothing coefficient으로 실험에서는 $1/n$을 사용하였습니다.

A. Mixed Graph / Free Sparse Representation

위치를 나타내는 모델은 기존 Liao의 Voronoi motion graph에 기초한 방법을 사용합니다. Liao는 실내 환경을 보로노이 그래프를 이용하여 표현하였는데, 이를 통해 사람의 위치와 그 이동을 그래프의 에지로 제한하여 성능 향상을 보였습니다.

이 논문에서는 이를 확장한 Mixed graph와 free space representation을 소개합니다. 이 방법은 환경을 그래프 $ G = (E, R, V) $로 표현합니다. E는 방향성이 없는 에지 $ e_i $의 집합이며 이 에지는 복도, 계단, 엘리베이터 등에 해당됩니다. R는 다각형 영역 $ r_i $의 집합이며 방 같은 공간을 나타냅니다. V는 정점 $ v_i $ 의 집합으로 에지와 영역을 이어주는 부분입니다.

B. Particle Filter-Based Tracking

위의 모델을 particle filter에 적용하여 Bayesian filtering을 구현할 것입니다. Posterior는 가중치가 적용된 샘플들 $ S_t = \{ < x_t^{(i)}, w^(i)_t > | i = 1, \dots, n \} $ 를 사용하여 계산하게 됩니다. 각 샘플 $ x_t^{(i)} $은 사람이 위치할만한 위치로 각각의 가중치 $ w_t^{(i)} $를 갖습니다. Particle filter는 각 시각마다 다음의 샘플링 과정을 거쳐 Bayes filter를 갱신합니다.

  1. Resampling : t-1 시각의 할당되었던 가중치를 참고하여 랜덤 샘플 $ x_{t-1}^{(i)} $ 를 솎아냅니다.
  2. Sampling : 움직임 모델 $ p(x_t^{(j)} | x_{t-1}^{(i)}) $으로부터 새로운 파티클 $ x_t^{(i)} $을 생성
  3. Importance sampling : 관측 likelihood $ p(z_t | x_t^{(j)}) $으로부터 샘플들의 가중치를 결정

언급했던 것 처럼 $x_t$는 사람의 위치를 나타내는 것으로, likelihood model에는 앞서 설명한 Gaussian process를 사용합니다. 여기에 $ x_t$가 가진 위치 정보 이외에 몇가지 정보를 더 추가합니다.

현재 위치가 에지일 경우, $ x_t = < e_t, d_t, m_t > $.
현재 위치가 영역에 있을 경우, $ x_t = < r_t, x_t, y_t, \alpha_t, m_t > $ 입니다.

여기서 $ e_t $는 어느 에지인지를 의미하고, $ d_t $는 에지의 시작지점으로부터의 거리, $m_t \in \{ \text{stopped, moving} \} $ 는 현재 움직임 상태를 나타냅니다. $r_t$는 현재 어느 영역인지를 나타내고, $x_t, y_t, \alpha_t $는 사람의 위치와 영역 내에서 바라보는 방향을 나타냅니다. 움직임 모델 $ p(x_t^{(j)} | x_{t-1}^{(i)}) $을 그래프에 적용하기 위하여 다음 것들을 이용하여야 합니다.

Motion state transitions $ p(m_t | m_{t-1}) $ : 움직임이 stopped나 moving에서 다른 상태로 바뀔 확률을 나타냅니다. 2 * 2로 행렬로 나타낼 수 있는데, 이 것은 움직임의 급격한 변화를 방지하도록 하여야 합니다. 여기서는 에지, 영역에 있을 때 다른 transition matrix를 사용합니다.

Edge transition $p(e_t | e_{t-1}) $ : 그래프 구조에 따라 각 에지에 할당되는 확률입니다.

Free space motion : 영역 내에서 할당되는 확률로, moving 상태에서는 현재 향하고 있는 방향을 선호하도록 하고 stopped 상태에서는 어느 방향이든 가능하도록 하였습니다. 만약 영역의 벽에 닿았을 경우 영역 안에 들어가도록 강제하고 그 방향은 반대로 향하도록 수정하여줍니다. 영역을 들어오고 나가는 유일한 방법은 영역과 에지를 연결하는 정점을 통하는 것입니다. 정점으로 이동할 확률은 정점까지의 거리에 반비례 합니다.

이러한 점을 반영한 움직임 모델에서 샘플링을 다음과 같이 수행합니다.

만약 $ x_{t-1}^{(i)} = < e_{t-1}, d_{t-1}, m_{t-1} > $가 에지에 있을 경우 Liao의 방법과 비슷하게 진행합니다. 먼저 상태 $m_t$$p(m_t | m_{t-1})$에 의하여 샘플링합니다. 그리고 상태가 stopped면, $ x_t = x_{t-1}$로 고정시킵니다. 만약 moving이라면 Gaussian velocity distribution에 의하여 움직인 거리 d를 임의로 정합니다. 이 d의 거리에 따라서 에지에 끝을 넘어가는지를 판단해보아야 합니다. 만약 에지에 끝에 닿지 않는다면 $ e_t = e_{t-1}, d_t = d_{t-1} + d $로 에지를 유지하고 위치만 변경하여 줍니다. 만약 에지의 끝을 넘어가버리면 $d_t = d_{t-1} + d - |e_{t-1}| $ 그리고 $e_t$$p(e_t | e_{t-1})$로부터 샘플링합니다. 만약 마지막 끝 정점이 영역과 연결되어있다면, 다음 상태 $ \alpha_t, x_t, y_t $를 입구 위치의 정점을 mean으로 하는 Gaussian으로부터 데이터를 얻어 초기화합니다.

만약 이전 상태 $ x_{t-1}^{(i)} = < r_{t-1}, x_{t-1}, y_{t-1}, \alpha_{t-1}, m_{t-1} > $가 영역 내에 있다면 먼저 파티클이 영역을 나갈 것인지 아닐 것인지를 샘플링합니다. 이것은 직전 위치로부터 출구 정점까지의 거리에 반비례하는 확률을 가집니다. 만약 샘플이 영역을 나가면 위치는 에지의 정점과 연결되는 시작위치로 초기화됩니다. 그렇지 않으면 움직임 상태 $ m_t $와 거리 $ d $를 샘플링하고, 직전 상태의 방향에서 d만큼 이동한 새로운 위치를 할당합니다. 만약 상태가 moving이라면 새로운 방향 $\alpha_t$를 직전 방향을 평균으로 하는 Gaussian으로부터 새로이 정하고, 움직이지 않는 상태라면 $[0 : 2 \pi]$로부터 균등하게 샘플링합니다.

4. Related works

생략합니다.

5. Experimental Results

신호 세기를 이용한 위치를 찾기 위해 WiFi, GSM 접속 데이터를 Gaussian process에 적용하였습니다.

A. Steup of Indoor Exper

사용한 기기와 실내 환경, 어떤 방식으로 신호를 측정했는지에 대한 설명을 하고 있습니다.

먼저 각 AP로부터 300개의 랜덤 샘플을 뽑은 다음 앞에서 설명한 식을 이용하여 모든 AP에 대하여 negative loglikelihood를 최소로 하는 하이퍼 파라미터를 계산합니다.

다음 이 하이퍼 파라미터를 이용하여 GP 모델을 생성합니다. 700개의 샘플을 뽑아 식에서 사용할 $ ( K + \sigma_n^2 I) ^{-1} $를 계산합니다.

위치를 계산하기 위해서는 200개의 파티클을 사용하였습니다. 파티클 필터의 매 업데이트마다 likelihood은 그 파티클 위치의 GP로부터 추정된 값을 사용합니다.

B. Indoor WiFi Localization Accuracy

정확도는 매 반복마다 가장 중요도가 높게 계산된 파티클의 위치를 실제 위치와 비교합니다. 그 결과는 논문을 참고하시기 바랍니다.

C. Dealing with Sparse Data

Sparse한 데이트에 대해서도 잘 작동하는지 알아보기 위하여 54개의 방 중, 25개의 방의 데이터를 제거하고 테스트를 진행하였습니다.

D. GSM Localization

WiFi 대신 GSM을 이용하여 실험을 진행하였습니다.

5. Conclusions

결론적으로 GP 모델을 likelihood로 사용하여 Bayesian filter를 구성하였습니다. Bayesian filter를 구현하는데에는 파티클 필터를 사용하였습니다.


Add a Comment Trackback