칼만 필터
칼만 필터()는 잡음이 포함되어 있는 선형 역학계의 상태를 추적하는 재귀 필터로, 루돌프 칼만이 개발하였다. 칼만 필터는 컴퓨터 비전, 로봇 공학, 레이다 등의 여러 분야에 사용되며, 많은 경우에 매우 효율적인
이 알고리즘은 시간에 따라 진행한 측정을 기반으로 한다. 해당 순간에만 측정한 결과만 사용한 것보다는 좀 더 정확한 결과를 기대할 수 있다. 잡음까지 포함된 입력 데이터를 재귀적으로 처리하는 필터로서, 현재 상태에 대한 최적의 통계적 예측을 진행할 수 있다.
알고리즘 전체는 예측과 업데이트의 두 가지로 나눌 수 있다. 예측은 현재 상태의 예측을 말하며, 업데이트는 현재 상태에서 관측된 측정까지 포함한 값을 통해서 더 정확한 예측을 할 수 있는 것을 말한다.
확장 칼만 필터는 비선형 시스템을 기반으로 동작한다.
칼만 필터는 물체의 측정값에 확률적인 오차가 포함되고, 또한 물체의 특정 시점에서의 상태는 이전 시점의 상태와 선형적인 관계를 가지고 있는 경우 적용이 가능하다. 예를 들어, 레이다 추적의 경우 특정 물체의 위치, 속도, 가속도 등을 측정할 수 있지만 이 측정값에 오차가 포함되어 있을 수 있다. 이 경우, 연속적으로 측정하는 값들을 칼만 필터를 이용해서 해당 물체의 위치를 추정할 수 있다.
칼만 필터는 이산 시간 선형 동적 시스템을 기반으로 동작하며, 각 시간에서의 상태 벡터는 이전 시간의 벡터들에 대해서만 관계된다는 마르코프 연쇄를 가정하고 있다.
특정 시간 formula_1에서의 상태 벡터를 formula_2라고 정의하고, 또한 그 시간에서의 사용자 입력을 formula_3라고 정의할 때, 칼만 필터에서는 다음과 같은 관계식을 가정하고 있다.
여기에서 formula_5는 해당 시간에서 이전 상태에 기반한 상태 전이 행렬, formula_6사용자 입력에 의한 상태 전이 행렬, 그리고 formula_7는 공분산행렬 formula_8을 가지는 다변수 정규 분포 formula_9 잡음 변수이다.
또한, 상태 벡터 formula_2와 그 벡터를 측정했을 때 실제로 얻어진 벡터 formula_11는 다음과 같은 관계식을 가지고 있다.
여기에서 formula_13는 해당 시간에서 측정에 관계되는 행렬이고, formula_14는 공분산행렬 formula_15을 가지는 다변수 정규 분포 formula_16 잡음 변수이다.
또한, 초기 상태와 각 잡음 변수 formula_17는 모두 상호 독립이라는 가정이 필요하다.
많은 경우, 실제 동적 시스템이 이 모델에 정확히 부합하지는 않는다. 특히, 선형성이나 상호 독립과 같은 중요한 가정이 맞지 않는 시스템의 경우, 칼만 필터의 성능을 심각하게 떨어뜨릴 수도 있고, 값을 발산하게 만드는 경우도 있다.
칼만 필터는 재귀적으로 동작한다. 즉, 칼만 필터는 바로 이전 시간에 추정한 값을 토대로 해서 현재의 값을 추정하며, 또한 바로 이전 시간 외의 측정값이나 추정값은 사용되지 않는다.
각 추정 계산은 두 단계로 이루어지며, 먼저 이전 시간에 추정된 상태에 대해, 그 상태에서 사용자 입력을 가했을 때 예상되는 상태를 계산한다. 이 단계는 예측(prediction) 단계라고 부른다. 그 다음, 앞서 계산된 예측 상태와 실제로 측정된 상태를 토대로 정확한 상태를 계산한다. 이 단계는 보정(update) 단계라고 부른다.
- 시스템에 따라서 보정단계가 가끔씩 일어날 수도 있다. 이때에는 예측단계가 여러번 수행되다가 한번씩 보정단계가 수행된다.
각 시간의 추정 상태는 평균과 분산의 두 개의 변수로 표현된다. 정확하게는,
여기에서 아랫첨자로 쓰인 formula_20은 m 시점에서의 측정값을 토대로 한 n 시점의 상태 추정을 의미한다.
예측 단계의 계산은 다음과 같이 이루어진다.보정 단계에서는 앞단계의 예측 값과 실제 측정값간의 오차를 이용해, 이전에 얻은 값을 귀납적으로 수정한다.모델이 정확하고, formula_28와 formula_29의 값이 정확하게 초기 상태 값의 몫을 반영한다면, 다음 불변량은 보존된다.
여기서 formula_32은 formula_33의 기대값이고, 공분산 매트릭스는 정확하게 추정의 공분산을 반영한다.
어떤 트럭이 마찰력이 없는 x축 공간에 있다. 이 트럭은 처음에는 원점 위치에 정지하고 있지만, 이후 임의의 가속도를 받으면서 움직인다. 관찰자는 formula_37 시간 간격으로 트럭의 위치를 측정하지만, 이 측정값은 정확하지 않고 실제 트럭의 위치와는 어느 정도 차이가 있을 수 있다. 이 때, 관찰자는 칼만 필터를 이용해서 부정확한 측정값을 기반으로 트럭의 실제 위치를 추정할 수 있다.
우선, 트럭의 움직임에 대한 관계식 formula_4을 알맞게 이끌어내야 한다. 트럭의 상태를 나타내는 벡터 formula_39는 그 트럭의 위치와 속도로 나타내면 적당하다. 즉, 해당 벡터를 다음과 같이 정의할 수 있다.
여기에서 formula_41는 시점 k에서의 위치, formula_42는 시점 k에서의 속도를 의미한다. 또한, 트럭에 임의로 가해지는 가속도를 formula_43로 정의한다.
뉴턴의 운동 법칙에 의해, formula_39와 formula_45 사이에는 다음과 같은 관계식이 (근사적으로) 성립한다.
이것을 formula_48로 표현하면 다음과 같다.
이 모델의 경우 formula_5, formula_6 등의 값이 시간 k에 관계없이 일정하다. 이러한 상수의 경우 첨자를 생략하여 표기하였다.
여기에서 formula_43가 평균이 0이고 표준편차가 formula_56인 정규 분포를 따른다고 가정하면, 잡음 변수 formula_57는 평균이 0이고 공분산이
라는 것을 구할 수 있다. 이렇게 해서 트럭의 움직임에 대한 관계식을 유도했다.
그 다음에는 측정에 대한 관계식을 유도한다. 측정 잡음 formula_60가 평균이 0이고 표준편차가 formula_61인 정규 분포를 따른다고 가정하면,
가 얻어진다.
트럭의 초기 위치와 속도는 0이라고 가정했으므로, 초기 변수를 다음과 같이 놓을 수 있다.
만약에 트럭의 초기 상태를 알지 못한다면, 불확실성을 의미하는 공분산행렬 formula_29는 적당히 큰 값으로 두어야 할 필요성이 있다. 적당히 큰 수 formula_68에 대해, 다음과 같이 초기화하면 된다.
후부 추정 공분산(posterior estimate covariance)
위의 불변 값인 에러 공분산 P에서 시작한다.
formula_71의 정의를 대체한다.
그리고 formula_73를 대체한다.
그리고 formula_75
그리고 우리가 얻은 에러 벡터를 수집함에 의해
측정 에러 v는 다른 항과 관련되지 않으므로, 이것은 다음과 같이 된다.
벡터 공분산의 속성에 의하여, 이것은 다음과 같이 된다.
이것은, 불변 값 P을 사용하여 R의 정의는 다음과 같이 된다.
이 공식(때때로 공분산 업데이트 방정식의 "Joseph form"이라 불린다)은 K의 값이 무엇이든 관계없이 가능하다. 이것은 만약 K가 최적의 칼만 이득이라면 이것을 아래 보이는 것처럼 더욱 단순화 할 수 있도록 한다.
칼만 필터는 최소 제곱 오차(minimum mean-square error, MMSE) 추정이다. 후부 상태 추정에서 에러는 다음 식과 같다.
우리는 이 벡터의 크기의 자승의 기댓값을 최소화하는 것을 찾는다, formula_82. 이것은 후부 추정 공분산 매트릭스 formula_83의 트레이스(대각 요소들의 합)를 최소화하는 것과 같다. 위 방정식에서 그 항을 확대하고 수집하여, 우리는 다음을 얻는다.
그 트레이스는 매트릭스 유도체(매트릭스 미분(calculus))가 0일 때 최소화 된다.
칼만 이득 K를 산출하기 위해 이것을 푼다.
"최적의 칼만 이득"이라 불리는, 이 이득은 MMSE 추정을 사용했을 때 산출되는 값이다.
후부 에러 공분산(posterior error covariance)
칼만 이득이 위에서 이끌어 낸 최적의 값과 같을 때 후부 에러 공분산을 단순화할 수 있도록 계산하기 위해 공식을 사용한다. SK을 칼만 게인 수식의 양쪽 모두에 곱하면, 다음과 같다.
후부 에러 공분산을 위한 확장된 공식을 다시 검토하면,
맨 뒤의 두 항이 없어지는 것을 알 수 있고, 따라서
이 공식은 계산 량이 적고 거의 항상 실제에 사용되지만, 최적의 이득에서 옳을 뿐이다. 만약 수치 정밀도가 수치안정에 문제를 야기하는 것에 대한 영향이 적지만은 않다면, 최적이 아닌 칼만 이득이 고의로 사용된다면, 이 단순화 과정은 지원될 수 없다. 위에서 이끌어낸 후부 에러 공분산 공식을 사용해야만 한다.
최적의 Fixed-lag smoother는 formula_90에서 formula_75까지의 측정값을 이용하여 주어진 fixed-lag N을 통해 최적의 formula_92 추정을 제공한다. 이것은 규정된 상태를 통하여 앞선 이론을 이용해 전달할 수 있고, 필터의 주요 방정식은 다음과 같다.
formula_93
여기서:
1) formula_94은 표준 칼만 필터를 통하여 추정된다;
2) formula_95은 표준 칼만 필터의 추정을 고려함으로써 생성된 혁신이다.
3) 변수 formula_96 (formula_97) 는 새로운 변수이다, i.e. 이것은 표준 칼만 필터에서는 나타나지 않는다;
4) 이득은 다음의 개요에 따라 계산된다:
formula_98
그리고
formula_99
여기서 formula_100 와 formula_101 은 표준 칼만 필터의 예측 에러 공분산과 이득이다.
만약 추정 에러 공분산을 정의한다면 다음과 같다.
formula_102
이경우 다음에 주어진 formula_103로 추정이 개선된다:
formula_104
칼만 필터에서는 기본적으로 모델의 선형성을 가정하고 있지만, 실제적으로는 많은 모델이 비선형 구조를 가지고 있다. 이런 경우 칼만 필터를 그대로 근사화해서 적용하면 그리 좋지 않은 결과를 얻는 경우가 많다. 이러한 경우, 칼만 필터를 수정해 비선형에도 사용할 수 있도록 한 필터가 사용된다.
확장 칼만 필터(Extended Kalman Filter, EKF)에서는 칼만 필터에서의 선형성 가정을 완화시켜, 더 일반적인 시스템에 대해서도 사용이 가능하도록 확장했다. 이 필터는 내비게이션이나 GPS와 같은 비선형 상태 추정에 주로 사용되고 있다.
확장 칼만 필터에서는 모델의 선형성 가정 대신, 상태 변화 함수의 미분가능성을 가정한다.
여기에서 formula_107, formula_108는 미분가능한 함수여야 한다.
여기서 상태 변이와 관측 매트릭스는 자코비안에 따라 정의 되었다.
선형의 것과는 다르게, 일반적인 확장 칼만 필터는 최적의 추정이 아니다(물론 만약 측정과 상태 천이 모델이 둘 다 선형이라면 최적이다. 그 경우엔 확장 칼만 필터는 보통의 것과 같다.). 덧붙여 말해서, 만약 상태의 초기 추정이 틀리거나 프로세스가 옳지 않게 설계됐다면, 필터는 필터의 선형성으로 인해 금방 발산할 수도 있다. 확장 칼만 필터의 다른 문제는 추정된 공분산 매트릭스가 실제 공분산 매트릭스를 경시하도록 의도되었고, 결론적으로 "안정적인 노이즈"의 추가됨이 없는 통계적 의미에 모순되는 위험을 감수한다.
이러한 단점에도 불구하고, 확장 칼만 필터는 적당한 수행을 할 수 있고, 내비게이션이나 GPS에서 거의 사실상 표준이다.
상태 천이와 관찰 모델(예측과 업데이트 함수 formula_107와 formula_108)이 매우 비선형일 경우, 확장 칼만 필터는 일부 형편없는 성능을 나타낼 수 있다. 이것은 평균과 공분산이 비선형 모델의 선형화로 인해 전달되었기 때문이다. 무향 칼만 필터(The unscented Kalman filter, UKF)는 평균 주변에 (시그마 점(sigma point)으로 불리는) 샘플 포인트의 최소 집합을 얻기 위해,무향 변환으로 알려져 있는 결정론적인 샘플링 기술을 사용한다. 이 시그마 점들은 비선형 함수를 통해 전달되고, 변환된 점들에 대해 평균과 공분산을 구하는 형태를 가진다. 결과는 더 정확하게 평균과 공분산을 잡아내는 필터이다.(이것은 몬테 카를로 샘플링(Monte Carlo sampling)이나 예측 통계의 테일러 시리즈 확장을 통해 수정 될 수 있다.) 덧붙여 말해서, 이 기술은 명시적인 자코비안 계산을 요구하지 않는다. 이것은 복잡한 함수를 위한 것이라면 더 어려운 임무일 수 있다. (i.e., 복잡하게 유도된 요구는 분석적 하게 되거나 수치적으로 비용이 많이 드는 컴퓨터 계산이 된다.)
예측
EKF와 같이, UKF 예측은 UKF 업데이트(선형 또는 EKF 업데이트의 조합)와 독립적으로 사용될 수 있고, 그 반대도 가능하다.
추정된 상태와 공분산은 프로세스 잡음의 평균과 공분산으로 증대된다.
2"L"+1 시그마 포인트의 집합은 증대되는 상태와 공분산으로부터 전달된다. 여기서 "L"은 증대되는 상태의 차원이다.
여기서,
은 다음 식의 매트릭스 스퀘어 루트의 "i"번째 행이다.
정의를 사용 : 매트릭스 B의 스퀘어루트 A를 푼다.
매트릭스 스퀘어 루트는 수치적으로 효율적인 계산이어야 하고, 초레스키 분해(the Cholesky decomposition)와 같이 안정적인 메서드이어야 한다.
시그마 포인트는 전달함수 "f"를 통해 전달된다.
웨이티드 시그마 포인트는 예측된 상태와 공분산을 생산하기 위해 재결합 된다.
여기서 상태와 공분산을 위한 웨이트는 다음과 같이 주어진다:
formula_122, formula_123, formula_124를 위한 대표적인 수로는 각각 formula_125, 2, 0 이다.(이들의 값은 최대한 목적을 만족시켜야 한다)
업데이트
예측된 상태와 공분산은 전보다 증대되었다. 다만 노이즈 측정의 평균과 공분산은 제외된다.
예전과 같이, 2"L"+1 시그마 포인트의 집합은 증대된 상태와 공분산으로부터 전달된다. 여기서 L은 증대된 상태의 차원이다.
이에 대한 대안으로, UKF 예측은 시그마 포인트를 사용하여 다음과 같이 증대될 수 있다.
여기서,
시그마 포인트는 관측 함수 "h"를 통하여 설계된다.
웨이티드 시그마 포인트는 예측된 측정과 예측된 측정 공분산을 생성하기위해 재구성된다.
상태 측정 크로스-공분산 매트릭스,
는 UKF 칼만 필터 이득을 계산하기위해 사용된다.
칼만필터로서, 업데이트된 상태는 예측된 상태에, 칼만 필터에 의해서 웨이티드된 혁신 값을 더한다.
그리고 업데이트된 공분산은 예측된 공분산에, 칼만 이득에 의해 웨이티드된 예측된 측정 공분산 값을 빼준다.
칼만-부시 필터(The Kalman–Bucy filter)는 칼만 필터의 연속 시간 버전이다.
이것은 상태 공간 모델을 기반으로 한다.
여기서 노이즈 항인 formula_139와 formula_140의 공분산은 각각 formula_141와 formula_142로 주어진다.
두 미분 방정식의 필터 상수, 상태 추정과 공분산:
여기서 칼만 이득은 다음과 같이 주어진다.
formula_146의 표현에서 노이즈 측정의 공분산 formula_142는 예측된 에러(혹은 혁신)formula_148의 공분산과 같은 시간에 표현된다. 이 공분산은 오직 연속시간의 경우이다.
이산 시간 칼만 필터링의 예측과 업데이트 단계 사이의 구별은 연속시간에서는 존재하지 않는다.
(공분산을 위한 )두 번째 미분 방정식은, Riccati equation의 예이다.
필터 이름은 루돌프 칼만( Rudolf E. Kalman) 개발자의 이름에서 따온 것이다.
실제로는 Thorvald Nicolai Thiele Peter Swerling가 유사한 알고리즘을 더 일찍 개발하였다.
Stanley F. Schmidt는 일반적으로 사용할 수 있는 첫 번째의 칼만 필터를 구현하였다. 칼만이 미 항공 우주센터를 방문 중에 그의 아이디어가 아폴로 프로젝트의 궤적 추정 문제에 사용이 가능함을 알고 아폴로 항법 컴퓨터에 적용하도록 인도하였다. 필터는 Swerling (1958), Kalman (1960), Kalman and Bucy (1961)가 계속해서 연구 개발하였다.
필터는 때로는 Stratonovich-Kalman-Bucy 필터라고도 하는데 그 이유는 Ruslan L. Stratonovich 가 더 일반적인 비선형 필터의 특별한 경우를 이전에 개발하였기 때문이다.
사실 특별한 경우 방정식은 선형 필터에서 나타나는데 Stratonovich가 작성한 1960년대 논문에 나타나는데 그 때가 Rudolf E. Kalman가 Ruslan L. Stratonovich를 모스크바의 컨퍼런스에서 만났던 때이다.
제어 이론에서 칼만 필터는 가장 유용한 것으로 linear quadratic estimation (LQE)으로 알려져 있다.
칼만 필터의 다양성은 계속 지금까지 개발되고 있는데 칼만의 원래 공식은 이제 단순 칼만 필터라고 부르고, 쉬미츠의 확장 필터, 그외 Bierman, Thornton에 의한 "information" 필터와 "square-root"필터가 있다. 아마도 가장 흔하게 사용되는 칼만 필터 형태는 phase-locked loop으로서 현재 유비쿼터스의 라디오, 컴퓨터 그리고 대부분의 통신 및 비디오 장비에 사용된다.