Innovation과 NIS

칼만 필터에서 새로운 관측은 예측 상태를 보정하는 데 사용된다.
이때 관측과 예측의 차이를 innovation이라 하고, innovation이 현재 불확실성 모델에 비추어 얼마나 이례적인지를 나타내는 값으로 **NIS(Normalized Innovation Squared)**를 사용할 수 있다.

NIS의 핵심 형태는 다음과 같다.

$$\mathrm{NIS}_k=\mathbf{r}_k^\top\mathbf{S}_k^{-1}\mathbf{r}_k$$

이는 innovation에 대한 Mahalanobis distance squared와 같은 형태다.

Kalman filter의 관측 업데이트

선형 시스템을 다음과 같이 두자.

$$\mathbf{x}_k=\mathbf{F}_k \mathbf{x}_{k-1}+\mathbf{w}_k$$$$\mathbf{z}_k=\mathbf{H}_k \mathbf{x}_k+\mathbf{v}_k$$

여기서

  • \(\mathbf{x}_k\): 상태 벡터
  • \(\mathbf{z}_k\): 관측 벡터
  • \(\mathbf{F}_k\): 상태 전이 행렬
  • \(\mathbf{H}_k\): 관측 행렬
  • \(\mathbf{w}_k\): 프로세스 잡음
  • \(\mathbf{v}_k\): 관측 잡음

이다.

프로세스 잡음과 관측 잡음은 일반적으로 다음과 같이 둔다.

$$\mathbf{w}_k \sim \mathcal{N} \left( \mathbf{0}, \mathbf{Q}_k \right)$$$$\mathbf{v}_k \sim \mathcal{N} \left( \mathbf{0}, \mathbf{R}_k \right)$$

칼만 필터의 예측 상태와 예측 공분산은 다음과 같다.

$$\hat{\mathbf{x}}_{k|k-1}=\mathbf{F}_k\hat{\mathbf{x}}_{k-1|k-1}$$$$\mathbf{P}_{k|k-1}=\mathbf{F}_k\mathbf{P}_{k-1|k-1}\mathbf{F}_k^\top+\mathbf{Q}_k$$

새로운 관측 \(\mathbf{z}_k\)가 들어오면, 관측 업데이트에 앞서 예측된 관측과 실제 관측의 차이를 계산한다.

Innovation

예측 상태로부터 기대되는 관측은 다음과 같다.

$$\hat{\mathbf{z}}_k=\mathbf{H}_k\hat{\mathbf{x}}_{k|k-1}$$

실제 관측과 예측 관측의 차이를 innovation이라 한다.

$$\mathbf{r}_k=\mathbf{z}_k-\hat{\mathbf{z}}_k$$

따라서 선형 관측 모델에서는

$$\mathbf{r}_k=\mathbf{z}_k-\mathbf{H}_k\hat{\mathbf{x}}_{k|k-1}$$

이다.

Innovation은 다음 의미를 가진다.

$$\text{innovation}=\text{measurement}-\text{predicted measurement}$$

Innovation이 0에 가깝다면 관측과 예측이 잘 일치한다.
Innovation이 크다면 관측과 예측 사이의 차이가 크다는 뜻이다.

다만 innovation의 크기만으로 관측의 이상 여부를 판단하기는 어렵다.
같은 크기의 차이라도 현재 예측과 관측의 불확실성에 따라 의미가 달라지기 때문이다.

Innovation covariance

Innovation의 공분산은 다음과 같다.

$$\mathbf{S}_k=\mathbf{H}_k\mathbf{P}_{k|k-1}\mathbf{H}_k^\top+\mathbf{R}_k$$

여기서

  • \(\mathbf{P}_{k|k-1}\): 예측 상태 공분산
  • \(\mathbf{R}_k\): 관측 잡음 공분산
  • \(\mathbf{S}_k\): innovation covariance

이다.

예측 상태의 불확실성은 관측 공간으로 투영되어

$$\mathbf{H}_k \mathbf{P}_{k|k-1} \mathbf{H}_k^\top$$

로 나타난다.

여기에 관측 자체의 불확실성인 \(\mathbf{R}_k\)가 더해진다.

따라서 \(\mathbf{S}_k\)는 예측과 실제 관측 사이에서 어느 정도 차이가 발생할 수 있는지를 나타내는 공분산이다.

$$\text{innovation uncertainty}=\text{projected prediction uncertainty}+\text{measurement uncertainty}$$

Residual의 크기만으로는 부족한 이유

1차원 위치 추정을 생각해보자.

예측 위치가 \(10.0\,\mathrm{m}\), 관측 위치가 \(10.8\,\mathrm{m}\)라면 innovation은

$$r_k=10.8-10.0=0.8\,\mathrm{m}$$

이다.

그러나 \(0.8\,\mathrm{m}\)가 큰 오차인지는 불확실성에 따라 달라진다.

예측과 관측이 매우 정밀하여 innovation 표준편차가 \(0.3\,\mathrm{m}\)라면 \(0.8\,\mathrm{m}\)는 비교적 이례적이다.

반대로 innovation 표준편차가 \(2.0\,\mathrm{m}\)라면 동일한 \(0.8\,\mathrm{m}\)는 충분히 발생 가능한 차이다.

따라서 필요한 것은 innovation의 절대 크기가 아니라

$$\frac{\text{innovation}}{\text{expected innovation uncertainty}}$$

에 해당하는 값이다.

Mahalanobis distance

Mahalanobis distance는 벡터가 평균으로부터 얼마나 떨어져 있는지를 공분산을 고려하여 측정한다.

벡터 \(\mathbf{x}\), 평균 \(\boldsymbol{\mu}\), 공분산 \(\boldsymbol{\Sigma}\)에 대해 Mahalanobis distance squared는 다음과 같다.

$$d_M^2=\left(\mathbf{x}-\boldsymbol{\mu}\right)^\top\boldsymbol{\Sigma}^{-1}\left(\mathbf{x}-\boldsymbol{\mu}\right)$$

유클리드 거리는 모든 방향을 동일한 스케일로 다루지만, Mahalanobis distance는 방향별 분산과 변수 간 상관관계를 반영한다.

공분산이 큰 방향에서는 같은 차이도 상대적으로 가깝게 평가된다.
공분산이 작은 방향에서는 작은 차이도 상대적으로 멀게 평가된다.

Innovation의 기대 평균이 0이라고 보면

$$\boldsymbol{\mu}=\mathbf{0}$$

이며,

$$\mathbf{x}=\mathbf{r}_k$$$$\boldsymbol{\Sigma}=\mathbf{S}_k$$

로 둘 수 있다.

그러면 Mahalanobis distance squared는

$$d_M^2=\mathbf{r}_k^\top\mathbf{S}_k^{-1}\mathbf{r}_k$$

가 된다.

이 값이 NIS다.

NIS

NIS는 다음과 같이 정의된다.

$$\mathrm{NIS}_k=\mathbf{r}_k^\top\mathbf{S}_k^{-1}\mathbf{r}_k$$

따라서 NIS는 다음과 같이 해석할 수 있다.

NIS는 innovation이 평균 0으로부터 얼마나 떨어져 있는지를 innovation covariance 기준으로 측정한 Mahalanobis distance squared다.

NIS는 단순히 관측 오차가 큰지를 측정하지 않는다.

다음 항목을 함께 반영한다.

  • innovation의 크기
  • 예측 상태의 불확실성
  • 관측의 불확실성
  • 관측 성분 사이의 상관관계

즉,

$$\mathrm{NIS}=\text{innovation relative to its expected covariance}$$

에 해당한다.

1차원 형태

1차원에서는 NIS가 다음과 같이 단순해진다.

$$\mathrm{NIS}_k=\frac{r_k^2}{S_k}$$

Innovation variance를

$$S_k=\sigma_{r,k}^2$$

라고 하면

$$\mathrm{NIS}_k=\left(\frac{r_k}{\sigma_{r,k}}\right)^2$$

이다.

즉, innovation이 예상 표준편차의 몇 배인지를 계산한 뒤 제곱한 값이다.

1차원 예시

예측 위치를

$$\hat{x}_{k|k-1}=10.0,\mathrm{m}$$

관측 위치를

$$z_k=10.8,\mathrm{m}$$

라고 하자.

Innovation은

$$r_k=0.8,\mathrm{m}$$

이다.

작은 불확실성

예측 분산과 관측 분산이 각각 다음과 같다고 하자.

$$P_{k|k-1}=0.04$$$$R_k=0.05$$

관측 모델이 \(H_k=1\)이면 innovation variance는

$$S_k=P_{k|k-1}+R_k$$$$S_k=0.04+0.05=0.09$$

이다.

따라서 NIS는

$$\mathrm{NIS}_k=\frac{0.8^2}{0.09}\approx7.11$$

이다.

Innovation의 표준편차는

$$\sqrt{S_k}=0.3,\mathrm{m}$$

이므로 \(0.8\,\mathrm{m}\)의 innovation은 약 \(2.67\) 표준편차에 해당한다.

$$\frac{0.8}{0.3}\approx2.67$$

큰 불확실성

예측 분산이 더 크다고 하자.

$$P_{k|k-1}=1.0$$

관측 분산은 동일하게 둔다.

$$R_k=0.05$$

Innovation variance는

$$S_k=1.0+0.05=1.05$$

이다.

NIS는

$$\mathrm{NIS}_k=\frac{0.8^2}{1.05}\approx0.61$$

이다.

두 경우 모두 innovation은 \(0.8\,\mathrm{m}\)로 같지만 NIS는 다르다.

경우\(r_k\)\(S_k\)NIS
작은 불확실성\(0.8\)\(0.09\)\(7.11\)
큰 불확실성\(0.8\)\(1.05\)\(0.61\)

작은 공분산에서 \(0.8\,\mathrm{m}\)는 이례적인 차이가 된다.
큰 공분산에서는 동일한 차이가 자연스러운 범위에 포함된다.

다차원 예시

2차원 innovation을 다음과 같이 두자.

$$\mathbf{r}=\begin{bmatrix}0.5 \\0.2\end{bmatrix}$$

Innovation covariance는 다음과 같다.

$$\mathbf{S}=\begin{bmatrix}0.25 & 0 \\0 & 0.04\end{bmatrix}$$

역행렬은

$$\mathbf{S}^{-1}=\begin{bmatrix}4 & 0 \\0 & 25\end{bmatrix}$$

이다.

NIS는

$$\begin{aligned} \mathrm{NIS} &= \mathbf{r}^\top \mathbf{S}^{-1} \mathbf{r}\\&= 0.5^2 \times 4 + 0.2^2 \times 25\\&= 1+1\\&= 2 \end{aligned}$$

이다.

\(y\) 방향 innovation은 \(x\) 방향보다 작지만 \(y\) 방향 분산도 더 작다.
따라서 두 방향은 NIS에 동일하게 기여한다.

이는 단순한 유클리드 norm과 다른 점이다.

단순 norm은

$$\left\|\mathbf{r}\right\|^2=0.5^2 + 0.2^2=0.29$$

이지만, NIS는 각 방향의 불확실성을 반영하여 \(2\)가 된다.

카이제곱 분포

칼만 필터의 모델이 적절하고 innovation이 다음 정규분포를 따른다고 가정한다.

$$\mathbf{r}_k \sim \mathcal{N} \left( \mathbf{0}, \mathbf{S}_k \right) $$

이때 whitening된 innovation은

$$\mathbf{u}_k=\mathbf{S}_k^{-1/2} \mathbf{r}_k $$

이며,

$$\mathbf{u}_k \sim \mathcal{N} \left( \mathbf{0}, \mathbf{I} \right) $$

가 된다.

NIS는 whitening된 innovation의 제곱 norm으로 볼 수 있다.

$$\mathrm{NIS}_k=\mathbf{u}_k^\top \mathbf{u}_k $$$$\mathrm{NIS}_k=\left\|\mathbf{u}_k\right\|^2 $$

표준 정규분포를 따르는 \(m\)개 성분의 제곱합은 자유도 \(m\)인 카이제곱 분포를 따른다.

따라서 innovation의 차원이 \(m\)이면

$$\mathrm{NIS}_k \sim \chi_m^2 $$

이다.

NIS gating

카이제곱 분포를 이용하면 NIS에 대한 임계값을 설정할 수 있다.

신뢰수준을 \(1-\alpha\)라고 하면 threshold는 다음과 같다.

$$\tau_{\mathrm{NIS}}=\chi^2_{m,1-\alpha} $$

관측 acceptance 조건은

$$\mathrm{NIS}_k \le \tau_{\mathrm{NIS}} $$

이다.

반대로

$$\mathrm{NIS}_k>\tau_{\mathrm{NIS}}$$

이면 관측이 현재 예측 및 불확실성 모델과 일관되지 않는다고 판단할 수 있다.

예를 들어 1차원 innovation에 대한 95% threshold는

$$\chi^2_{1,0.95} \approx 3.84 $$

이다.

앞선 예시에서 작은 불확실성의 경우

$$7.11>3.84 $$

이므로 관측이 gate를 통과하지 못한다.

큰 불확실성의 경우

$$0.61 < 3.84 $$

이므로 관측을 받아들일 수 있다.

대표적인 threshold는 다음과 같다.

자유도 \(m\)95%99%
13.846.63
25.999.21
37.8111.34
612.5916.81

관측 차원 또는 residual 차원이 자유도가 된다.

관측 업데이트와의 관계

NIS gate를 통과한 관측은 일반적인 칼만 필터 업데이트에 사용할 수 있다.

Kalman gain은

$$\mathbf{K}_k=\mathbf{P}_{k|k-1} \mathbf{H}_k^\top \mathbf{S}_k^{-1} $$

이다.

상태 업데이트는

$$\hat{\mathbf{x}}_{k|k}=\hat{\mathbf{x}}_{k|k-1} + \mathbf{K}_k \mathbf{r}_k $$

이고, 공분산 업데이트는

$$\mathbf{P}_{k|k}=\left( \mathbf{I}-\mathbf{K}_k \mathbf{H}_k \right) \mathbf{P}_{k|k-1} $$

이다.

NIS는 이 업데이트를 수행하기 전에 해당 관측을 사용할지 판단하는 gate로 배치할 수 있다.

predict state and covariance

r = z - H x_pred
S = H P_pred H^T + R
NIS = r^T S^(-1) r

if NIS <= threshold:
    compute Kalman gain
    update state and covariance
else:
    reject or defer measurement

수치 계산

NIS를 계산할 때 \(\mathbf{S}^{-1}\)를 직접 구할 필요는 없다.

다음 선형 시스템을 푼다.

$$\mathbf{S}_k \mathbf{y}_k=\mathbf{r}_k $$

그다음

$$\mathrm{NIS}_k=\mathbf{r}_k^\top \mathbf{y}_k $$

로 계산할 수 있다.

공분산 행렬이 대칭 양의 정부호라면 Cholesky decomposition을 사용하는 방식이 일반적이다.

$$\mathbf{S}_k=\mathbf{L}_k \mathbf{L}_k^\top $$

이때

$$\mathbf{L}_k \mathbf{u}_k=\mathbf{r}_k $$

를 풀면

$$\mathrm{NIS}_k=\mathbf{u}_k^\top \mathbf{u}_k $$

로 계산할 수 있다.

이는 innovation whitening의 계산과도 연결된다.

비선형 관측 모델

EKF에서 관측 모델이

$$\mathbf{z}_k=h\left( \mathbf{x}_k \right) + \mathbf{v}_k $$

형태라면 innovation은

$$\mathbf{r}_k=\mathbf{z}_k-h\left(\hat{\mathbf{x}}_{k|k-1}\right)$$

이다.

Innovation covariance는 관측 Jacobian을 사용하여 계산한다.

$$\mathbf{H}_k=\left. \frac{\partial h} {\partial \mathbf{x}} \right|_{\hat{\mathbf{x}}_{k|k-1}} $$$$\mathbf{S}_k=\mathbf{H}_k \mathbf{P}_{k|k-1} \mathbf{H}_k^\top + \mathbf{R}_k $$

NIS의 형태는 선형 필터와 동일하다.

$$\mathrm{NIS}_k=\mathbf{r}_k^\top \mathbf{S}_k^{-1} \mathbf{r}_k $$

다만 비선형성이 강하면 innovation의 실제 분포가 정규분포에서 벗어날 수 있으므로 카이제곱 해석이 근사적인 성격을 갖는다.

자세와 manifold residual

회전이나 자세를 포함하는 상태에서는 상태 차이를 단순 벡터 뺄셈으로 표현하기 어려울 수 있다.

예를 들어 두 pose 사이의 residual을 Lie group에서 정의하면

$$\mathbf{r}_k=\operatorname{Log} \left( \widetilde{\mathbf{T}}_k^{-1} \hat{\mathbf{T}}_k \right) $$

와 같이 tangent space의 벡터로 변환할 수 있다.

그 후 residual covariance \(\mathbf{S}_k\)를 구성하여

$$\mathrm{NIS}_k=\mathbf{r}_k^\top\mathbf{S}_k^{-1}\mathbf{r}_k$$

를 계산할 수 있다.

이 경우에도 본질은 동일하다.

  • residual을 적절한 벡터 공간에 표현한다.
  • 그 residual의 공분산을 구성한다.
  • Mahalanobis distance squared를 계산한다.

NIS가 큰 경우

NIS가 크다는 것은 관측이 현재 예측과 불확실성 모델에 비추어 이례적이라는 뜻이다.

그러나 반드시 관측 센서만 잘못되었다는 의미는 아니다.

가능한 원인은 다음과 같다.

  • 관측 이상치
  • 잘못된 데이터 연관
  • 잘못된 정합
  • 상태 예측 오차
  • 부정확한 시스템 모델
  • 부정확한 관측 모델
  • 과소 추정된 예측 공분산
  • 과소 추정된 관측 공분산
  • 시간 동기화 오차
  • 좌표계 변환 오차
  • 선형화 오차

따라서 NIS는 관측 자체만을 평가하는 값이라기보다 다음 항목 사이의 일관성을 평가한다.

$$\text{prediction} + \text{measurement} + \text{uncertainty model} $$

공분산과 NIS

NIS는 공분산 설정에 직접적으로 영향을 받는다.

공분산이 작아지면

$$\mathbf{S}_k \downarrow \quad\Rightarrow\quad \mathrm{NIS}_k \uparrow $$

가 된다.

필터가 실제보다 지나치게 확신하면 정상적인 관측도 이상치로 판단될 수 있다.

반대로 공분산이 커지면

$$\mathbf{S}_k \uparrow \quad\Rightarrow\quad \mathrm{NIS}_k \downarrow $$

가 된다.

불확실성을 과도하게 크게 설정하면 실제 이상치도 gate를 통과할 수 있다.

따라서 NIS threshold를 설정하는 것만으로는 충분하지 않다.
예측 공분산과 관측 공분산이 실제 불확실성을 어느 정도 반영해야 한다.

단일 관측 gate와 필터 일관성

NIS는 두 가지 관점에서 사용할 수 있다.

단일 관측 gating

각 시점의 NIS를 계산하여 관측 acceptance를 판단한다.

$$\mathrm{NIS}_k \le \tau_{\mathrm{NIS}} $$

이면 관측을 사용하고, 그렇지 않으면 관측을 거부하거나 보류한다.

시간에 따른 일관성 검사

NIS를 여러 시점에 걸쳐 관찰하면 필터가 주장하는 공분산과 실제 innovation의 일관성을 점검할 수 있다.

NIS가 반복적으로 높다면 다음 가능성이 있다.

  • 공분산이 과소 추정됨
  • 모델링되지 않은 외란이 존재함
  • 관측 잡음이 과소 추정됨
  • 상태 추정이 실제 상태를 추적하지 못함

반대로 NIS가 지속적으로 지나치게 낮다면 공분산을 과도하게 크게 잡았을 가능성이 있다.

따라서 NIS는 이상치 gate이면서 동시에 필터 일관성 진단 지표다.

Hard gating 이외의 처리

NIS가 threshold를 넘는 경우 가장 단순한 처리는 관측을 거부하는 것이다.

$$\mathrm{NIS}_k>\tau_{\mathrm{NIS}} \quad\Rightarrow\quad \text{reject} $$

그러나 응용에 따라 다른 방식도 사용할 수 있다.

  • 관측 거부
  • 관측 업데이트 보류
  • 관측 공분산 \(\mathbf{R}_k\) 증가
  • 관측 가중치 감소
  • robust loss 적용
  • 추가 센서를 이용한 재검증
  • 연속된 NIS 패턴을 이용한 fault detection

연속적으로 높은 NIS가 발생하는 경우 관측을 계속 제거하는 것만으로는 필터가 회복되지 않을 수 있다. 이 경우 예측 모델, 초기화, 공분산 설정을 함께 점검할 필요가 있다.

Residual threshold와의 차이

단순 residual threshold는 다음과 같은 형태다.

$$\left\|\mathbf{r}_k\right\| \le \tau_r $$

이 방법은 residual의 절대 크기만 사용한다.

NIS gate는 다음과 같다.

$$\mathbf{r}_k^\top \mathbf{S}_k^{-1} \mathbf{r}_k \le \tau_{\mathrm{NIS}} $$

두 방법의 차이는 다음과 같다.

항목Residual thresholdNIS
기준절대 오차불확실성 대비 오차
예측 공분산반영하지 않음반영
관측 공분산반영하지 않음반영
변수 간 상관관계반영하지 않음반영
threshold물리 단위 의존무차원
통계적 해석제한적카이제곱 분포

NIS는 공분산을 통해 스케일이 정규화되므로 서로 다른 물리 단위가 포함된 다차원 residual에도 사용할 수 있다.

핵심 정리

Innovation은 실제 관측과 예측 관측의 차이다.

$$\mathbf{r}_k=\mathbf{z}_k-\mathbf{H}_k\hat{\mathbf{x}}_{k|k-1}$$

Innovation covariance는 예측 불확실성과 관측 불확실성을 합한 값이다.

$$\mathbf{S}_k=\mathbf{H}_k\mathbf{P}_{k|k-1}\mathbf{H}_k^\top+\mathbf{R}_k$$

NIS는 innovation을 covariance로 정규화한 값이다.

$$\mathrm{NIS}_k=\mathbf{r}_k^\top\mathbf{S}_k^{-1}\mathbf{r}_k$$

NIS는 형태상 innovation의 Mahalanobis distance squared다.

정규성 가정 아래 innovation 차원이 \(m\)이면

$$\mathrm{NIS}_k \sim \chi_m^2 $$

이므로 카이제곱 threshold를 이용해 관측 일관성을 검사할 수 있다.

핵심 해석은 다음과 같다.

NIS는 관측 오차의 절대적인 크기가 아니라, 현재 예측과 불확실성 모델에 비추어 해당 innovation이 얼마나 이례적인지를 나타낸다.