칼만 필터

'''칼만 필터'''(Kalman filter)는 잡음이 포함되어 있는 측정치를 바탕으로 선형 역학계의 상태를 추정하는 재귀 필터로, 루돌프 칼만이 개발하였다. 칼만 필터는 컴퓨터 비전, 로봇 공학, 레이다 등의 여러 분야에 사용된다. 칼만 필터는 과거에 수행한 측정값을 바탕으로 현재의 상태 변수의 결합분포를 추정한다.
알고리즘은 예측과 업데이트의 두 단계로 이루어진다. 예측 단계에서는 현재 상태 변수의 값과 정확도를 예측한다. 현재 상태 변수의 값이 실제로 측정된 이후, 업데이트 단계에서는 이전에 추정한 상태 변수를 기반으로 예측한 측정치와 실제 측정치의 차이를 반영해 현재의 상태 변수를 업데이트한다.
확장 칼만 필터는 비선형 시스템을 기반으로 동작한다.
칼만 필터는 물체의 측정값에 확률적인 오차가 포함되고, 또한 물체의 특정 시점에서의 상태가 이전 시점의 상태와 선형적인 관계를 가지고 있는 경우 적용이 가능하다. 예를 들어, 레이다 추적의 경우 특정 물체의 위치, 속도, 가속도 등을 측정할 수 있지만 이 측정값에 오차가 포함되어 있을 수 있다. 이 경우, 연속적으로 측정하는 값들을 칼만 필터를 이용해서 해당 물체의 위치를 추정할 수 있다.
칼만 필터는 이산 시간 선형 동적 시스템을 기반으로 동작하며, 각 시간에서의 상태 벡터는 이전 시간의 상태 벡터를 통해서 결정된다는 마르코프 연쇄를 가정하고 있다.
파일:칼만필터.jpg|오른쪽|섬네일|631px|칼만 필터 모델. 사각형은 행렬을 나타낸다. 타원은 (행렬 내부의 평균과 공분산을 포함한) 다변량의 정규 분포를 나타낸다. 내부 변수의 값은 벡터이다.
특정 시간 에서의 상태 벡터를 라고 정의하고, 또한 그 시간에서의 사용자 입력을 라고 정의할 때, 칼만 필터에서는 다음과 같은 관계식을 가정하고 있다.
:
여기에서 는 해당 시간에서 이전 상태에 기반한 상태 전이 행렬, 는 사용자 입력에 의한 상태 전이 행렬, 그리고 는 공분산행렬 을 가지는 다변량 정규분포  잡음 변수이다.
또한, 상태 벡터 와 그 벡터를 측정했을 때 실제로 얻어진 벡터 는 다음과 같은 관계식을 가지고 있다.
:
여기에서 는 해당 시간의 상태에서 측정값을 도출하는 행렬이고, 는 공분산행렬 을 가지는 다변량 정규분포  잡음 변수이다.
초기 상태와 각 잡음 변수 는 모두 상호 독립이라는 가정이 필요하다.
많은 경우 실제 동적 시스템이 이 모델에 정확히 부합하지는 않는다. 특히, 선형성이나 상호 독립과 같은 중요한 가정이 맞지 않는 시스템의 경우, 칼만 필터의 성능을 심각하게 떨어뜨릴 수도 있고, 예측값이 발산하는 경우도 있다.
칼만 필터는 재귀적으로 동작한다. 즉, 칼만 필터는 바로 이전 시간에 추정한 값을 토대로 해서 현재의 값을 추정하며, 바로 이전 시간 외의 측정값이나 추정값은 사용하지 않는다.
각 추정 계산은 두 단계로 이루어진다. 첫 단계에서는 이전 시간에 추정된 상태에 대해, 그 상태에서 사용자 입력을 가했을 때 예상되는 측정값을 계산한다. 이 단계는 '''예측'''(prediction) 단계라고 부른다. 그 다음 단계에서는, 앞서 예측된 측정값과 실제 측정값을 토대로 현재의 상태를 추정한다. 이 단계는 '''보정'''(update) 단계라고 부른다.
시스템에 따라서 보정단계가 가끔씩 일어날 수도 있다. 이때에는 예측단계가 여러번 수행되다가 한번씩 보정단계가 수행된다.
각 시간의 추정 상태는 평균과 분산의 두 개의 변수로 표현된다. 정확하게는,
* : m 시점의 측정값을 토대로 한 n 시점의 상태 추정값
* : m 시점의 측정값을 토대로 한 n 시점의 상태 공분산행렬
여기에서 아랫첨자로 쓰인 은 m 시점에서의 측정값을 토대로 한 n 시점의 상태 추정을 의미한다.
=== 예측 단계 ===
예측 단계의 계산은 다음과 같이 이루어진다.
 연역적 상태 예측: 
  
 연역적 공분산 예측:
 
=== 보정 단계 ===
보정 단계에서는 앞단계의 예측 값과 실제 측정값간의 오차를 이용해, 이전에 얻은 값을 귀납적으로 수정한다.
 예측 단계와 실제 측정간의 잔차:
 
 잔차의 공분산: 
 
 최적 '''칼만 이득'''(Kalman gain): 
 
 귀납적 상태 보정: 
 
 귀납적 상태 공분산 보정: 
 
=== 불변량 ===
모델이 정확하고, 와 의 값이 정확하게 초기 상태 값의 몫을 반영한다면, 다음 불변량은 보존된다.
* 
* 
여기서 은 의 기대값이고, 공분산 행렬은 정확하게 추정의 공분산을 반영한다.
* 
* 
* 
어떤 트럭이 마찰력이 없는 x축 공간에 있다. 이 트럭은 처음에는 원점 위치에 정지하고 있지만, 이후 임의로 가해지는 미지의 가속도를 받으면서 움직인다. 관찰자는  시간 간격으로 트럭의 위치를 측정하지만, 이 측정값은 정확하지 않고 실제 트럭의 위치와는 어느 정도 차이가 있을 수 있다. 이 때, 관찰자는 칼만 필터를 이용해서 부정확한 측정값을 기반으로 트럭의 실제 위치를 추정할 수 있다.
우선, 트럭의 움직임에 대한 관계식 을 알맞게 이끌어내야 한다. 트럭의 상태를 나타내는 벡터 는 그 트럭의 위치와 속도로 나타내면 적당하다. 즉, 해당 벡터를 다음과 같이 정의할 수 있다.
:
여기에서 는 시점 k에서의 위치, 는 시점 k에서의 속도를 의미한다. 는 트럭에 임의로 가해지는 미지의 가속도를 표시한다.
뉴턴의 운동 법칙에 의해, 와  사이에는 다음과 같은 관계식이 근사적으로 성립한다.
:
:
이것을 로 표현하면 다음과 같다.
:
:
:
:
이 모델의 경우 ,  등의 값이 시간 k에 관계없이 일정하다. 이러한 상수의 경우 첨자를 생략하여 표기하였다.
여기에서 가 평균이 0이고 표준편차가 인 정규 분포를 따른다고 가정하면, 잡음 변수 는 평균이 0이고 공분산이
: (가 상수이므로 성립한다)
라는 것을 구할 수 있다. 이렇게 해서 트럭의 움직임에 대한 관계식을 유도했다.
그 다음에는 측정에 대한 관계식을 유도한다. 측정 잡음 가 평균이 0이고 표준편차가 인 정규 분포를 따른다고 가정하면,
:
:
:
가 얻어진다.
트럭의 초기 위치와 속도는 0이라고 가정했으므로, 초기 변수를 다음과 같이 놓을 수 있다.
:
:
만약에 트럭의 초기 상태를 알지 못한다면, 불확실성을 의미하는 공분산행렬 는 다음과 같이 적당히 큰 값으로 초기화하면 된다.
:
=== 후부 추정 공분산 행렬 유도 ===
불변 값인 잔차 공분산 '''P'''''k''|''k''에서 시작한다.
:
의 정의를 대입하면,
:
를 대입하면,
:
를 대입하면,
:
잔차 벡터를 묶어내면,
:
측정 에러 '''v'''''k''는 다른 항과 독립이므로,
:
벡터 공분산의 속성에 따라,
:
이것은, 불변 값 와 '''R'''''k''의 정의를 이용하면,
:
이 공식은 때로는 공분산 업데이트 방정식의 "'''조셉 형식(Joseph form)'''"이라 불리는데 '''K'''''k''의 값이 최적 칼만이득인지 여부에 관계없이 성립한다. 만약 '''K'''''k''가 최적 칼만이득이라면 이것을 아래처럼 더욱 단순화 할 수 있다.
=== 칼만 이득 유도 ===
칼만 필터는 최소 제곱 오차(minimum mean-square error, MMSE) 추정이다. 후부 상태 추정에서 잔차는 다음 식과 같다.
:
이 벡터의 크기의 제곱의 기댓값 을 최소화하는 를 찾는 것이 목적이다. 이것은 후부 추정 공분산 행렬 의 대각합을 최소화하는 것과 같다. 위 방정식에서 를 전개하여 묶어내면
:
 
 
 
이 행렬의 대각합이 최소가 되는 조건은
:
최적의 칼만 이득 를 산출하면
:
:
''최적의 칼만 이득''이라 불리는 이 이득은 MMSE 추정을 사용했을 때 산출되는 값이다.
=== 후부 잔차 공분산 식의 간이화 ===
칼만 이득이 위에서 이끌어 낸 최적의 값과 같을 때 후부 잔차 공분산을 단순화할 수 있도록 계산하기 위해 공식을 사용한다. '''S'''''k'''''K'''''k''''T''을 칼만 이득 수식의 양쪽 모두에 곱하면,
:
후부 잔차 공분산을 위한 확장된 공식을 다시 검토하면,
:
맨 뒤의 두 항이 없어지는 것을 알 수 있고, 따라서
:
이 공식은 간단하고 거의 항상 실제에 사용되지만, 최적의 이득일 때만 성립한다. 만약 수치 정밀도가 낮거나 최적이 아닌 칼만 이득을 사용할 경우 이 단순화는 성립하지 않는다. 그런 경우에는 위에서 유도한 후부 잔차 공분산 공식을 사용해야만 한다.
최적의 고정 지연 스무더는 에서 까지의 측정값을 이용하여 주어진 고정된 지연값 N을 통해 최적의  추정을 제공한다. 이것은 위의 이론에서 상태 벡터를 확장 정의해 아래와 같이 유도할 수 있다.
여기서:
1) 은 표준 칼만 필터를 통하여 추정된다;
2) 은 표준 칼만 필터의 추정을 고려함으로써 생성된 혁신(잔차)이다.
3) 변수  ()는 새로운 변수이다. 즉 이것은 표준 칼만 필터에서는 나타나지 않는다;
4) 이득은 다음의 개요에 따라 계산된다:
그리고
여기서  와  은 표준 칼만 필터의 예측 오차 공분산과 이득이다.
만약 추정 오차 공분산을 정의한다면 다음과 같다.
이경우 다음에 주어진 로 추정이 개선된다:
칼만 필터에서는 기본적으로 모델의 선형성을 가정하고 있지만, 실제적으로는 많은 모델이 비선형 구조를 가지고 있다. 이런 경우 칼만 필터를 그대로 근사화해서 적용하면 그리 좋지 않은 결과를 얻는 경우가 많다. 이러한 경우, 칼만 필터를 수정해 비선형에도 사용할 수 있도록 한 필터가 사용된다.
=== 확장 칼만 필터 ===
'''확장 칼만 필터'''(Extended Kalman Filter, '''EKF''')에서는 칼만 필터에서의 선형성 가정을 완화시켜, 더 일반적인 시스템에 대해서도 사용이 가능하도록 확장했다. 이 필터는 내비게이션이나 GPS와 같은 비선형 상태 추정에 주로 사용되고 있다.
==== 구조 ====
확장 칼만 필터에서는 모델의 선형성 가정 대신, 상태 변화 함수의 미분가능성을 가정한다.
:
:
여기에서 , 는 미분가능한 함수여야 한다.
==== 예측과 업데이트 방정식 ====
 '''예측''' 
 예측된 상태 
예측된 추정 공분산
 '''업데이트''' 
 혁신 혹은 추정 나머지 
 혁신(혹은 나머지) 공분산 
 ''최적의'' 칼만 이득 
 업데이트된 상태 추정 
 업데이트된 추정 공분산 
여기서 상태 변이와 관측 매트릭스는 자코비안에 따라 정의 되었다.
:
:
==== 확장 칼만 필터의 단점 ====
선형의 것과는 다르게, 일반적인 확장 칼만 필터는 최적의 추정이 아니다(물론 만약 측정과 상태 천이 모델이 둘 다 선형이라면 최적이다. 그 경우엔 확장 칼만 필터는 보통의 것과 같다.). 덧붙여 말해서, 만약 상태의 초기 추정이 틀리거나 프로세스가 옳지 않게 설계됐다면, 필터는 필터의 선형성으로 인해 금방 발산할 수도 있다. 확장 칼만 필터의 다른 문제는 추정된 공분산 매트릭스가 실제 공분산 매트릭스를 경시하도록 의도되었고, 결론적으로 "안정적인 노이즈"의 추가됨이 없는 통계적 의미에 모순되는 위험을 감수한다.
이러한 단점에도 불구하고, 확장 칼만 필터는 적당한 수행을 할 수 있고, 내비게이션이나 GPS에서 거의 사실상 표준이다.
=== 무향 칼만 필터 ===
상태 전이와 관찰 모델(예측과 업데이트 함수 와 )이 매우 비선형일 경우, 확장 칼만 필터는 일부 형편없는 성능을 나타낼 수 있다. 이것은 평균과 공분산이 비선형 모델의 선형화로 인해 전달되었기 때문이다. 무향 칼만 필터(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''를 통해 전달된다.
:
웨이티드 시그마 포인트는 예측된 상태와 공분산을 생산하기 위해 재결합 된다.
:
:
여기서 상태와 공분산을 위한 웨이트는 다음과 같이 주어진다:
:
:
:
:
, , 를 위한 대표적인 수로는 각각 , 2, 0이다.(이들의 값은 최대한 목적을 만족시켜야 한다)
'''업데이트'''
예측된 상태와 공분산은 전보다 증대되었다. 다만 노이즈 측정의 평균과 공분산은 제외된다.
:
:
예전과 같이, 2''L''+1 시그마 포인트의 집합은 증대된 상태와 공분산으로부터 전달된다. 여기서 L은 증대된 상태의 차원이다.
:
이에 대한 대안으로, UKF 예측은 시그마 포인트를 사용하여 다음과 같이 증대될 수 있다.
:
여기서,
:
시그마 포인트는 관측 함수 ''h''를 통하여 설계된다.
:
웨이티드 시그마 포인트는 예측된 측정과 예측된 측정 공분산을 생성하기 위해 재구성된다.
:
:
상태 측정 크로스-공분산 매트릭스,
:
는 UKF 칼만 필터 이득을 계산하기 위해 사용된다.
:
칼만필터로서, 업데이트된 상태는 예측된 상태에, 칼만 필터에 의해서 웨이티드된 혁신 값을 더한다.
:
그리고 업데이트된 공분산은 예측된 공분산에, 칼만 이득에 의해 웨이티드된 예측된 측정 공분산 값을 빼준다.
:
칼만-부시 필터(The Kalman–Bucy filter)는 칼만 필터의 연속 시간 버전이다.
이것은 상태 공간 모델을 기반으로 한다.
:
:
여기서 노이즈 항인 와 의 공분산은 각각 와 로 주어진다.
두 미분 방정식의 필터 상수, 상태 추정과 공분산:
:
:
여기서 칼만 이득은 다음과 같이 주어진다.
:
의 표현에서 노이즈 측정의 공분산 는 예측된 에러(혹은 혁신)의 공분산과 같은 시간에 표현된다. 이 공분산은 오직 연속시간의 경우이다.
이산 시간 칼만 필터링의 예측과 업데이트 단계 사이의 구별은 연속시간에서는 존재하지 않는다.
.
(공분산을 위한 )두 번째 미분 방정식은, 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으로서 현재 유비쿼터스의 라디오, 컴퓨터 그리고 대부분의 통신 및 비디오 장비에 사용된다.
분류:제어이론
분류:선형 필터
분류:비선형 필터
분류:마르코프 모형
분류:로봇 제어
분류:신호 추정
분류:확률미분방정식
분류:헝가리의 발명품