입자 필터(particle filter)는 순차 몬테카를로 방법(sequential Monte Carlo methods)으로도 알려져 있으며, 비선형 상태-공간 시스템에 대한 필터링 문제의 근사 해를 찾는 데 사용되는 알고리즘 집합이다. 이러한 기법은 신호 처리 및 베이지안 통계적 추론과 같은 분야에 적용된다. 필터링 문제는 부분적인 관측만 가능하고 센서와 시스템 자체 모두에 무작위 섭동이 영향을 미칠 때 동적 시스템의 내부 상태를 추정하는 것을 포함한다. 핵심 목표는 잡음이 있고 부분적인 관측이 주어졌을 때 마르코프 과정 상태의 사후 분포를 계산하는 것이다.
"입자 필터"라는 용어는 1996년 피에르 델 모랄(Pierre Del Moral)이 처음 만들어냈으며, 1960년대 초부터 유체 역학에서 사용된 평균장 상호작용 입자 방법을 지칭한다. "순차 몬테카를로"라는 용어는 1998년 준 S. 리우(Jun S. Liu)와 롱 첸(Rong Chen)이 별도로 만들어냈다. 입자 필터링은 입자 또는 표본 집합을 사용하여 확률 과정의 사후 분포를 나타낸다. 상태-공간 모델은 비선형일 수 있으며, 초기 상태 및 잡음 분포는 필요한 모든 형태를 취할 수 있다. 이 접근 방식은 모델이나 상태 분포에 대한 제한적인 가정 없이 목표 분포에서 표본을 생성하는 잘 확립된 방법론을 제공한다.
핵심 방법론
입자 필터는 근사적이고 통계적인 방식으로 예측을 업데이트한다. 각 입자는 시스템 상태의 기저 확률 밀도 함수에서 추출될 확률을 나타내는 우도 가중치를 지닌다. 일반적인 문제는 소수의 입자가 분포를 지배하는 가중치 붕괴(weight collapse)이다. 이 문제는 무시할 수 있는 가중치를 가진 입자를 더 높은 가중치를 가진 입자 근처의 새 입자로 대체하는 재표본화(resampling) 단계로 완화되며, 종종 가중치 분산이나 상대 엔트로피와 같은 적응 기준에 의해 촉발된다.
입자 필터의 수학적 기초는 필터링 문제를 페인만-카츠 경로 적분 모델로 해석하는 데 있다. 이러한 기법은 분자 화학 및 계산 물리학에서 개발되었으며, 시어도어 E. 해리스(Theodore E. Harris), 마셜 N. 로젠블루스(Marshall N. Rosenbluth), 아리아나 W. 로젠블루스(Arianna W. Rosenbluth)의 초기 기여가 있었다. 계산 물리학에서 이러한 방법은 양자 몬테카를로, 특히 확산 몬테카를로 방법에도 사용된다. 페인만-카츠 상호작용 입자 방법은 진화 계산에 사용되는 유전 알고리즘과 강하게 관련이 있다.
배경 및 동기
필터링 문제는 관측이 부분적이고 센서와 시스템 역학 모두에서 잡음에 의해 손상될 때 동적 시스템의 내부 상태를 추정하는 것을 포함한다. 목표는 관측이 주어졌을 때 상태의 사후 분포를 계산하는 것이며, 이는 재귀적 베이지안 추정을 요구한다. 선형 및 가우시안 모델의 경우 칼만 필터가 정확한 해를 제공한다. 그러나 많은 실제 시스템에서 역학 및 관측 모델은 비선형이거나 비가우시안이다.
1984년 미레이유 샬레야-모렐(Mireille Chaleyat-Maurel)과 도미니크 미셸(Dominique Michel)은 선형-가우시안 모델이나 특정 더 넓은 계열과 같은 특정 클래스를 제외하고는 사후 분포의 시퀀스가 유한 차원 재귀를 허용하지 않음을 증명했다. 이 결과는 정확한 해가 일반적으로 불가능하며 근사 수치 방법이 필요함을 의미한다. 그리드 근사, 마르코프 체인 몬테카를로, 확장 칼만 필터 또는 선형화 모델을 포함한 전통적인 접근 방식은 대규모 시스템, 불안정한 과정 또는 강한 비선형 역학에서 종종 어려움을 겪는다.
알고리즘 및 재표본화
입자 필터는 각각 가능한 상태를 나타내는 입자 집합과 관측이 주어졌을 때 해당 상태의 우도에 비례하는 가중치를 유지한다. 알고리즘은 반복적으로 진행된다: 예측 단계에서 입자는 시스템 역학에 따라 진화하고, 업데이트 단계에서 가중치는 새 관측에 따라 조정되며, 재표본화 단계에서 저가중치 입자를 고가중치 입자의 복사본으로 대체하여 가중치 붕괴를 방지한다.
가중치 붕괴는 소수의 입자가 대부분의 확률 질량을 축적하여 퇴화된 표현을 초래할 때 발생한다. 이를 완화하기 위해 가중치 분산이나 가중치 분포의 상대 엔트로피가 임계값을 초과할 때 재표본화가 수행된다. 재표본화 중에는 무시할 수 있는 가중치를 가진 입자가 폐기되고 더 높은 가중치를 가진 입자 주변에서 새 입자가 생성된다 $[$Machine learning$]$ 방법. 이 단계는 약간의 근사를 도입하지만 시간이 지남에 따라 다양성과 정확성을 유지하는 데 필수적이다.
이론적 기초
통계적 관점에서 입자 필터는 페인만-카츠 확률 측도의 평균장 입자 해석으로 해석될 수 있다. 이러한 기법은 분자 화학 및 물리학에서 시작되었다. 초기 기여에는 1951년 시어도어 E. 해리스와 허먼 칸(Herman Kahn)의 연구와 1955년 로젠블루스 부부의 연구가 포함되며, 이들은 양자 몬테카를로 시뮬레이션에서 이러한 방법을 사용했다. 1948년 엔리코 페르미(Enrico Fermi)와 로버트 릭트마이어(Robert Richtmyer)는 이러한 방법과 관련된 평균장 입자 해석을 개발했다. 관련 유전형 알고리즘은 1950년과 1954년 앨런 튜링(Alan Turing)과 1950년대 초 프린스턴 고등연구소의 닐스 알 바리첼리(Nils Aall Barricelli)에 의해 탐구되었다. 1954년 존 해머슬리(John Hammersley)가 제안한 "가난한 사람의 몬테카를로" 방법도 현대 입자 필터 아이디어의 선구자를 포함했다.
응용 및 방법
입자 필터는 Artificial intelligence, 신호 처리 및 베이지안 통계적 추론과 같은 분야에서 널리 사용된다. 특히 기저 역학과 잡음 분포가 비가우시안인 숨은 마르코프 모델에서 상태 추정에 적합하다. 일반적인 응용에는 표적 추적, 로봇 위치 추정 및 금융 위험 분석이 포함된다. Machine learning에서 입자 방법은 순차 데이터 분석 및 희귀 사건 표본 추출에 나타난다.
계산 물리학 및 분자 화학에서 이러한 기법은 양자 몬테카를로 및 관련 문제에 적용된다. 생물학에서는 개체군 역학과 유전적 진화를 모델링한다. 이 방법은 계통 발생학, 약동학 및 정량적 위험 평가에서도 사용된다.
다른 방법과의 관계
입자 필터는 비선형 역학을 선형화하는 확장 칼만 필터나 시그마 포인트를 통해 분포를 근사하는 무향 칼만 필터와 같은 전통적인 기법과 다르다. 이러한 방법은 가우시안 가정에 의존하지만 입자 필터는 그러한 제한을 두지 않는다. 그러나 매우 고차원 시스템에서는 필요한 입자 수가 차원에 따라 기하급수적으로 증가하여 차원의 저주라고 불리는 현상이 발생하므로 성능이 저하된다. 보조 입자 필터 및 무향 입자 필터와 같은 변형은 특정 응용에서 비효율성을 해결하기 위해 개발되었다.
응용
입자 필터의 다양성은 많은 분야에서 채택으로 이어졌다. 신호 및 이미지 처리, 로봇 공학 및 자율 항법, 표적 추적 및 컴퓨터 비전에 사용된다. 기계 학습 및 Artificial intelligence에서는 시간적 모델에서 근사 추론을 위한 도구로 사용된다. 또한 생물정보학, 계통 발생학, 경제학, 희귀 사건 표본 추출 및 약동학에서도 응용을 찾았다. Waymo 및 Tesla과 같은 회사는 자율 주행 시스템의 차량 상태 추정을 위해 입자 필터 기법을 탐구했지만, 현대 구현은 종종 이를 Deep learning 접근 방식과 결합한다.
발전 및 한계
입자 필터의 이론적 기초는 1950년대 물리학 및 화학에서 개발된 평균장 상호작용 입자 방법으로 거슬러 올라가며, 유전형 학습 기계에 대한 앨런 튜링의 초기 연구와 닐스 알 바리첼리의 기여를 포함한다. 1954년 존 해머슬리와 동료들이 제안한 '가난한 사람의 몬테카를로' 방법은 현대 유전형 입자 필터의 요소를 포함했다. 계산 물리학에서 1948년 엔리코 페르미와 로버트 릭트마이어의 연구에서 개발된 양자 몬테카를로 및 확산 몬테카를로 방법도 페인만-카츠 경로 적분의 상호작용 입자 근사에 의존한다.
진화 계산 연구자, 특히 1970년대 초 존 홀랜드(John Holland)는 유사한 유전 알고리즘을 휴리스틱 도구로 독립적으로 개발했다. 통계학에서 첫 번째 공식 입자 필터는 1993년 닐 고든(Neil Gordon), 데이비드 살몬드(David Salmond), 아드리안 스미스(Adrian Smith)에 의해 부트스트랩 필터로 도입되었다. 이후 1999년 마이클 피트(Michael Pitt)와 닐 셰퍼드(Neil Shephard)의 보조 입자 필터와 일부 상태 변수를 주변화하여 효율성을 개선하는 라오-블랙웰화 입자 필터를 포함한 중요한 개선이 이어졌다. 이러한 방법은 현대 순차 베이지안 추론의 초석으로 남아 있다.
응용
입자 필터는 다양한 분야에서 널리 적용된다. 신호 처리 및 이미지 분석에서는 객체 추적 및 컴퓨터 비전에 사용된다. 로봇 공학에서는 Tesla 및 Cruise와 같은 시스템에서 동시적 위치 추정 및 지도 작성(SLAM)을 가능하게 한다. 경제학 및 금융에서는 위험 분석 및 희귀 사건 표본 추출을 지원한다. 생물정보학에서는 계통 발생학에 적용되고, 약동학에서는 약물 흡수 및 분포 모델링을 돕는다. 또한 계산 생물학, 희귀 사건 시뮬레이션 및 정량적 위험 평가에도 나타난다.
이 방법은 Artificial intelligence에서 위치 및 환경의 정확한 추적이 중요한 Waymo 및 기타 자율 주행 차량 시스템과 같은 상태 추정 작업에 특히 가치가 있다. 또한 시퀀스 모델링을 위한 신경망에 사용되는 기법과도 관련이 있다.
한계 및 확장
입자 필터의 주요 한계는 고차원 상태 공간에서의 성능이다. 필요한 입자 수는 상태 차원에 따라 기하급수적으로 증가하여 실용적 제약을 초래한다. 이 문제는 입자 방법과 Deep learning 또는 무향 변환을 결합한 하이브리드 접근 방식에 대한 연구를 촉발했다. Robotics에서 입자 필터는 몬테카를로 위치 추정에 널리 사용되며, 금융에서는 위험 분석 및 희귀 사건 시뮬레이션을 지원한다. 이 방법론은 생물정보학, 계통 발생학 및 경제학에도 적용되었다.
관련 방법 및 변형
여러 변형이 특정 단점을 해결한다. 순차 중요도 재표본화는 각 반복에서 재표본화 단계를 포함하는 일반적인 구현이다. 보조 입자 필터는 제안 분포를 개선하고, 라오-블랙웰화 입자 필터는 선형 하위 구조를 주변화하여 분산을 줄인다. 앙상블 칼만 필터는 가우시안 근사에 대한 특수한 경우로 볼 수 있다. Deep learning 접근 방식과의 비교가 때때로 이루어지지만, 입자 필터는 확률적 공식화와 이론적 보장에서 여전히 구별된다.
응용
이 방법론은 다양한 분야에서 응용을 찾는다. 신호 및 이미지 처리에서 입자 필터는 비디오 시퀀스의 객체를 추적한다. 공학 및 로봇 공학에서는 자율 주행 차량과 같은 시스템의 동시적 위치 추정 및 지도 작성(SLAM)을 지원한다. 생물정보학에서는 계통 발생 추론 및 유전자 발현 분석에 적용된다. 경제학 및 금융은 확률적 변동성 모델의 상태 추정에 이를 사용한다. 정량적 위험 평가 및 희귀 사건 표본 추출도 이러한 기법의 혜택을 받는다. 고차원 문제는 여전히 어려운 과제이지만, 입자 필터는 비선형, 비가우시안 상태 추정을 위한 유연하고 널리 사용되는 도구로 계속되고 있다.
같이 보기
- 학습 알고리즘의 더 넓은 맥락을 위한 Machine learning
- 관련 응용을 위한 Artificial intelligence
참고 문헌
주요 출처에는 평균장 입자 방법에 대한 피에르 델 모랄의 연구와 1984년 샬레야-모렐 및 미셸이 확립한 수학적 기초가 포함된다. 실용적인 개요는 통계 계산 문헌에서 확인할 수 있다.