맨위로가기

파티클 필터

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

파티클 필터는 통계 및 확률 분야에서 널리 사용되는 알고리즘으로, 시스템에 임의로 생성된 입력을 여러 번 가하여 시스템의 정보를 추측하는 방식으로 작동한다. 1990년대에 수학적 기초가 정립되었으며, 신호 처리, 베이즈 추론, 로봇 공학, 금융 수학 등 다양한 분야에 응용된다. 파티클 필터는 몬테카를로 방법, 평균장 입자 시뮬레이션, 순차 중요도 재표본추출(SIR) 알고리즘 등 여러 변형이 존재하며, 잡음이 있는 관측이나 강한 비선형성을 다루는 데 효과적이다.

더 읽어볼만한 페이지

  • 로봇 제어 - 칼만 필터
    칼만 필터는 잡음이 있는 측정값들을 이용하여 선형 동적 시스템의 상태를 추정하는 재귀 필터로, 예측과 보정 단계를 반복하며 항법 시스템, 레이더 추적, 컴퓨터 비전 등 다양한 분야에 응용된다.
  • 로봇 제어 - 유도, 항법 및 제어
    유도, 항법 및 제어(GNC)는 현대 무기 체계와 자율 시스템의 핵심으로, 항법, 유도, 제어 기능을 통해 위치 파악, 목표 설정, 비행 조정을 수행하며, 다양한 항법 기술을 활용하여 정확성과 신뢰성을 높이지만, 인공지능 도입에 따른 윤리적 문제와 사회적 논의가 필요한 분야이다.
  • 비선형 필터 - 칼만 필터
    칼만 필터는 잡음이 있는 측정값들을 이용하여 선형 동적 시스템의 상태를 추정하는 재귀 필터로, 예측과 보정 단계를 반복하며 항법 시스템, 레이더 추적, 컴퓨터 비전 등 다양한 분야에 응용된다.
  • 비선형 필터 - 전변동 잡음제거
    전변동 잡음 제거는 신호의 전변동을 최소화하여 잡음을 제거하는 신호 처리 기법이며, 1D 신호는 인접 신호 값의 차이 합으로, 2D 신호는 전변동 노름으로 정의하고, 정규화 매개변수를 통해 잡음 제거 정도를 조절하며 루딘-오셔-파테미 모델이 이미지 잡음 제거에 활용된다.
  • 계산통계학 - 인공 신경망
  • 계산통계학 - 랜덤 포레스트
    랜덤 포레스트는 결정 트리들을 앙상블하여 분류, 회귀, 검출 등에 활용되며, 랜덤화 기술로 일반화 성능을 향상시키는 기계 학습 알고리즘이다.
파티클 필터
개요
유형몬테카를로 방법
분야신호 처리, 베이즈 추론
상세 정보
다른 이름순차적 몬테카를로 (Sequential Monte Carlo, SMC) 방법
개발자니얼 고든, 데이비드 살몬드, 에이드리언 F. M. 스미스
개발일1993년
관련 항목확장 칼만 필터
몬테카를로 지역화
로젠블루스 알고리즘
활용
활용 분야컴퓨터 비전
로봇 공학
유전자 서열 분석
온라인 추정
숨겨진 마르코프 모델
재무 모델링
레이더 추적
기상 예측
GPS
단일 세포 궤적 분류
운영 위험 관리

2. 역사

파티클 필터의 역사는 1950년대 몬테카를로 방법에 대한 초기 연구에서 시작되었다. 1954년 해머슬리 등은 '가난한 사람의 몬테카를로'[23]를 제안했는데, 이는 오늘날 사용되는 유전자형 파티클 필터링 방법의 힌트를 담고 있었다. 1963년 닐스 올 바리첼리는 개인이 간단한 게임을 할 수 있는 능력을 모방하기 위해 유전자형 알고리즘을 시뮬레이션했다.[24]

1957년 호주의 유전학자 알렉스 프레이저는 유기체의 인공 선택에 대한 유전자형 시뮬레이션에 관한 일련의 논문을 발표했다.[26] 1948년 엔리코 페르미와 로버트 리히트마이어는 중성자 연쇄 반응의 평균장 파티클 해석을 개발했고,[32] 1984년 잭 H. 헤더링턴은 양자 시스템의 바닥 상태 에너지를 추정하기 위한 최초의 휴리스틱형 및 유전자형 파티클 알고리즘을 개발했다.[29] 1951년 테오도어 E. 해리스와 허먼 칸은 입자 전달 에너지를 추정하기 위해 평균장이지만 휴리스틱형 유전자 방법을 사용했다.[33]

신호 처리 및 베이즈 추론에서 유전자 파티클 알고리즘을 사용한 것은 비교적 최근의 일이다. 1993년 1월, 키타가와 겐시로는 "몬테카를로 필터"[34]를 개발했고, 같은 해 4월, 고든 등은 베이즈 통계적 추론에 유전자형 알고리즘을 적용한 "부트스트랩 필터"를 발표했다.[36] 1990년대 중반 피에르 델 모랄[2]과 히밀콘 카르발류, 피에르 델 모랄, 앙드레 모닌, 제라르 살루가 파티클 필터에 대한 연구를 발표했다.

1996년 피에르 델 모랄은 파티클 필터 알고리즘의 수학적 기초와 무편향 속성을 증명했다.[2][4] 1990년대 말, 댄 크리산, 제시카 게인스, 테리 라이온스,[44][45][46] 그리고 피에르 델 모랄과 테리 라이온스는 다양한 모집단 크기를 가진 분기형 입자 기법을 개발했다.

1999년 피에르 델 모랄과 앨리스 기오네는 최초의 중심 극한 정리를 증명했으며,[48] 2000년 피에르 델 모랄과 로랑 미클로는 이를 증명했다.[8] 2000년과 2004년에는 페인만-카츠 입자 방법론 및 관련 입자 필터 알고리즘에 대한 이론이 책으로 발간되었다.[8][5]

2. 1. 휴리스틱 알고리즘

통계적 방법론에서 파티클 필터의 초기 흔적은 1950년대 중반으로 거슬러 올라간다. 1954년 해머슬리 등은 '가난한 사람의 몬테카를로'[23]를 제안했는데, 이는 오늘날 사용되는 유전자형 파티클 필터링 방법의 힌트를 담고 있었다. 1963년, 닐스 올 바리첼리는 개인이 간단한 게임을 할 수 있는 능력을 모방하기 위해 유전자형 알고리즘을 시뮬레이션했다.[24] 진화 컴퓨팅 문헌에서, 유전자형 변이-선택 알고리즘은 1970년대 초 존 홀랜드의 획기적인 연구, 특히 1975년에 출판된 그의 저서[25]를 통해 인기를 얻었다.

생물학 및 유전학에서, 호주의 유전학자 알렉스 프레이저는 1957년에 유기체의 인공 선택에 대한 유전자형 시뮬레이션에 관한 일련의 논문을 발표했다.[26] 프레이저의 시뮬레이션은 현대 변이-선택 유전자형 파티클 알고리즘의 모든 필수 요소를 포함했다.

양자 몬테카를로 방법의 기원은 1948년에 중성자 연쇄 반응의 평균장 파티클 해석을 개발한 엔리코 페르미와 로버트 리히트마이어에게 기인하는데,[32] 양자 시스템의 바닥 상태 에너지를 추정하기 위한 최초의 휴리스틱형 및 유전자형 파티클 알고리즘은 1984년 잭 H. 헤더링턴이 개발했다.[29] 1951년에 발표된 테오도어 E. 해리스와 허먼 칸의 연구는 입자 전달 에너지를 추정하기 위해 평균장이지만 휴리스틱형 유전자 방법을 사용했다.[33] 1955년 마셜 N. 로젠블루스와 아리아나 W. 로젠블루스는 분자 화학에서 유전자 휴리스틱 입자 방법론을 사용했다.[11]

유전자 파티클 알고리즘의 고급 신호 처리 및 베이즈 추론에서의 사용은 더 최근의 일이다. 1993년 1월, 키타가와 겐시로는 "몬테카를로 필터"[34]를 개발했고, 이 논문의 약간 수정된 버전이 1996년에 발표되었다.[35] 1993년 4월, 고든 등은 베이즈 통계적 추론에 유전자형 알고리즘을 적용한 "부트스트랩 필터"를 발표했다.[36] 1990년대 중반에 피에르 델 모랄[2]과 히밀콘 카르발류, 피에르 델 모랄, 앙드레 모닌, 제라르 살루가 파티클 필터에 대한 연구를 발표했다.

2. 2. 수학적 기초

1996년 피에르 델 모랄(Pierre Del Moral)은 파티클 필터 알고리즘의 수학적 기초와 무편향 속성을 증명했다.[2][4] 이 논문에는 우도 함수 및 정규화되지 않은 조건부 확률 측도의 입자 근사치의 무편향 속성에 대한 증명도 포함되어 있으며, 여기서 제시된 우도 함수의 무편향 입자 추정기는 오늘날 베이지안 통계적 추론에 사용된다.

1990년대 말, 댄 크리산(Dan Crisan), 제시카 게인스(Jessica Gaines), 테리 라이온스(Terry Lyons),[44][45][46] 그리고 피에르 델 모랄과 테리 라이온스는 다양한 모집단 크기를 가진 분기형 입자 기법을 개발했다. 2000년에는 P. 델 모랄, A. 기오네(A. Guionnet), L. 미클로(L. Miclo)가 이 주제에 대한 추가적인 발전을 이루었다.[8][49][50]

1999년 피에르 델 모랄과 앨리스 기오네는 최초의 중심 극한 정리를 증명했으며,[48] 2000년 피에르 델 모랄과 로랑 미클로는 이를 증명했다.[8] 1990년대 말 피에르 델 모랄과 앨리스 기오네는 시간 매개변수와 관련된 최초의 균일 수렴 결과를 개발했다.[49][50] 2001년 P. 델 모랄과 L. 미클로는 계보 트리 기반 입자 필터 스무더에 대한 최초의 엄격한 분석을 수행했다.[51]

2000년과 2004년에는 페인만-카츠 입자 방법론 및 관련 입자 필터 알고리즘에 대한 이론이 책으로 발간되었다.[8][5]

3. 원리

파티클 필터는 시스템에 확률분포를 따르는 임의의 입력을 여러 개 생성하고, 이를 종합하여 시스템의 정보를 추정하는 방식으로 작동한다.[91][92]

3. 1. 필터링 문제

파티클 필터는 관측 변수를 기반으로 상태 변수의 사후 확률 밀도를 추정한다. 이는 은닉 마르코프 모델을 사용하여 순차적으로 숨겨진 상태 값을 추정하는 필터링 문제이다. 사후 밀도에서 파생된 베이지안 추정은 경험적 측정을 통해 근사치를 제공한다.

일반적으로 파티클 필터는 아래와 같은 상태 공간에서 숨겨진 상태의 사후 분포를 추정한다.

:\begin{array}{cccccccccc}

X_0&\to &X_1&\to &X_2&\to&X_3&\to &\cdots&\text{신호}\\

\downarrow&&\downarrow&&\downarrow&&\downarrow&&\cdots&\\

Y_0&&Y_1&&Y_2&&Y_3&&\cdots&\text{관측}

\end{array}

필터링 문제는 주어진 시간 단계 ''k''에서 관측 과정 Y_0,\cdots,Y_k의 값을 바탕으로 숨겨진 상태 X_k의 값을 순차적으로 추정하는 것이다.

X_k의 모든 베이지안 추정은 사후 밀도 p(x_k|y_0,y_1,...,y_k)에서 파생된다. 파티클 필터는 유전형 입자 알고리즘과 관련된 경험적 측정을 사용하여 이러한 조건부 확률의 근사치를 제공한다. 반면, 마르코프 체인 몬테카를로 또는 중요도 샘플링 접근 방식은 전체 사후 확률 p(x_0,x_1,...,x_k|y_0,y_1,...,y_k)를 모델링한다.

파티클 필터에서 관측 불가능한 상태 x_k와 관측값 y_k는 다음과 같이 표현될 수 있다.

관측 불가능한 상태 열 x_0, x_1, \ldots은 1계 마르코프 과정을 만족한다. 즉, x_k는 x_{k-1}에 의해 결정되며, 초기값 x_0의 확률 분포 p(x_0)를 갖는다.

:x_k|x_{k-1} \sim p_{x_k|x_{k-1}}(x|x_{k-1})

관측 데이터 열 y_0, y_1, \ldots는 x_0, x_1, \ldots가 알려져 있다는 조건 하에 독립적이다. 즉, y_k는 x_k에만 종속된다.

:y_k|x_k \sim p_{y|x}(y|x_k)

이는 상태 방정식을 따르는 상태 공간 모델로 표현될 수 있다.[91][92]

:x_k = f_k(x_{k-1}, v_k) \,

:y_k = h_k(x_k, w_k) \,

여기서 v_k와 w_k는 서로 다른 k에 대해 서로 독립적이며, 확률 분포를 따르는 노이즈이다. v_k는 시스템 노이즈, w_k는 관측 노이즈라고 부른다. f_k(\cdot)와 h_k(\cdot)는 알려진 함수이다.

칼만 필터는 상태 공간 모델의 일종으로, 선형 함수와 다변량 정규 분포를 따르는 노이즈를 가정하면 다음과 같이 표현할 수 있다.

:

\begin{align}

x_k &= F_k x_{k-1} + G_k v_k \\

y_k &= H_k x_k + w_k

\end{align}



이 경우 칼만 필터는 베이즈 추정과 정확히 일치하는 해를 제공한다. 그러나 선형이 아닌 경우 칼만 필터는 1차 근사에 불과하다. 파티클 필터는 몬테카를로 방법을 이용한 근사 방법이지만, 충분한 수의 입자를 사용하면 높은 정밀도를 얻을 수 있다.

3. 2. 신호-관측 모델

파티클 필터는 관측값을 바탕으로 숨겨진 상태 변수의 확률 분포를 추정하는 데 사용된다. 일반적으로 상태 변수와 관측 변수는 은닉 마르코프 모델을 따르며, 다음과 같은 신호-관측 모델을 가정한다.

:\begin{array}{cccccccccc}

X_0&\to &X_1&\to &X_2&\to&X_3&\to &\cdots&\text{신호}\\

\downarrow&&\downarrow&&\downarrow&&\downarrow&&\cdots&\\

Y_0&&Y_1&&Y_2&&Y_3&&\cdots&\text{관측}

\end{array}

여기서,

  • X_k는 시간 ''k''에서의 숨겨진 상태 변수를 나타내며, 마르코프 과정을 따른다. 즉, X_k는 이전 상태 X_{k-1}에만 의존하며, 전이 확률 밀도 p(x_k|x_{k-1})에 따라 변화한다. 초기 상태 X_0는 확률 밀도 p(x_0)를 가진다.
  • Y_k는 시간 ''k''에서의 관측 변수를 나타내며, 숨겨진 상태 X_k에만 의존한다. 즉, Y_k는 X_0, X_1, \cdots가 주어졌을 때 조건부 독립이며, 조건부 확률 밀도 p(y_k|x_k)를 따른다.


이러한 가정 하에, 파티클 필터는 관측값 Y_0, \cdots, Y_k가 주어졌을 때 숨겨진 상태 X_k의 값을 순차적으로 추정한다. 이는 사후 밀도 p(x_k|y_0, y_1, \ldots, y_k)를 추정하는 문제로, 파티클 필터는 경험적 측정을 통해 이 조건부 확률의 근사치를 제공한다.

간단한 예로, 다음과 같은 상태 공간 모델을 생각할 수 있다.

:X_k = g(X_{k-1}) + W_{k-1}

:Y_k = h(X_k) + V_k

여기서 W_k와 V_k는 서로 독립적인 확률 밀도 함수를 따르는 잡음이고, ''g''와 ''h''는 알려진 함수이다.

만약 ''g''와 ''h''가 선형 함수이고 W_k와 V_k가 가우시안 분포를 따르면, 칼만 필터를 사용하여 정확한 베이즈 필터링 분포를 찾을 수 있다. 그러나 함수가 비선형이거나 잡음이 비가우시안 분포를 따르는 경우, 파티클 필터는 EKF나 UKF와 같은 근사 방법보다 더 정확한 추정을 제공할 수 있다.

파티클 필터는 아래의 상태 공간 모델을 가정한다.[91][92]

:x_k = f_k(x_{k-1}, v_k) \,

:y_k = h_k(x_k, w_k) \,

여기서,

  • v_k는 시스템 잡음, w_k는 관측 잡음을 나타내며, 서로 다른 k에 대해 독립적이고 어떤 확률 분포를 따른다.
  • f_k(\cdot)와 h_k(\cdot)는 알려진 함수이다.


칼만 필터는 이 상태 공간 모델의 특수한 경우로, f_k(\cdot)와 h_k(\cdot)가 선형이고, v_k와 w_k가 다변량 정규 분포를 따를 때 다음과 같이 표현된다.

:

\begin{align}

x_k &= F_k x_{k-1} + G_k v_k \\

y_k &= H_k x_k + w_k

\end{align}



이 경우, 칼만 필터는 베이즈 추정과 정확히 일치하는 해를 제공한다. 하지만, 비선형 시스템이나 비가우시안 잡음의 경우에는 파티클 필터가 더 높은 정밀도를 제공할 수 있다.

3. 3. 근사 베이즈 계산 모델

어떤 문제에서는 신호의 무작위 상태가 주어졌을 때 관측값의 조건부 분포가 밀도를 갖지 못하거나, 밀도를 계산하는 것이 불가능하거나 너무 복잡할 수 있다.[17] 이 경우 추가적인 근사가 필요하다. 한 가지 방법은 신호 X_k를 마르코프 체인 \mathcal X_k=\left(X_k,Y_k\right)로 대체하고 가상 관측값을 도입하는 것이다.

:\mathcal Y_k=Y_k+\epsilon \mathcal V_k\quad\mbox{일부 매개변수에 대해}\quad\epsilon\in [0,1]

여기서 \mathcal V_k는 알려진 확률 밀도 함수를 가진 독립적인 무작위 변수들이다. 핵심 아이디어는 다음을 이용하는 것이다.

:\text{Law}\left(X_k|\mathcal Y_0=y_0,\cdots, \mathcal Y_k=y_k\right)\approx_{\epsilon\downarrow 0} \text{Law}\left(X_k|Y_0=y_0,\cdots, Y_k=y_k\right)

부분 관측 \mathcal Y_0=y_0,\cdots, \mathcal Y_k=y_k가 주어졌을 때 마르코프 과정 \mathcal X_k=\left(X_k,Y_k\right)와 관련된 입자 필터는 p(\mathcal Y_k|\mathcal X_k)로 주어진 가능도 함수를 사용하여 \mathbb R^{d_x+d_y}에서 진화하는 입자의 관점에서 정의된다. 이러한 확률적 기법은 근사 베이즈 계산(ABC)과 밀접하게 관련되어 있다. 이러한 ABC 입자 필터링 기법은 1998년 P. Del Moral, J. Jacod 및 P. Protter에 의해 도입되었다.[65] 이들은 P. Del Moral, A. Doucet 및 A. Jasra에 의해 추가적으로 개발되었다.[66][67]

입자 필터에서는 관측 불가능한 상태 x_k 와 관측값 y_k 를 다음과 같이 나타낼 수 있다고 가정한다.

관측 불가능한 상태 열 x_0, x_1, \ldots 은 1계 마르코프 과정을 만족한다. 즉, x_k 는 x_{k-1} 에 의해 결정되며, 초기값 x_0 의 확률 분포 p(x_0) 를 갖는다. 두 단계 전의 상태 x_{k-2} 를 사용할 수 없다는 의미가 아니라, 필요하다면 두 단계 전의 상태도 x_{k-1} 에 포함하여 사용한다는 의미이다.

:x_k|x_{k-1} \sim p_{x_k|x_{k-1}}(x|x_{k-1})

관측 데이터 열 y_0, y_1, \ldots 는 x_0, x_1, \ldots 가 알려져 있다는 조건 하에서 독립적이다. 즉, y_k 는 x_k 에만 종속된다.

:y_k|x_k \sim p_{y|x}(y|x_k)

상태 방정식은 다음과 같이 표현되는 상태 공간 모델이다.[91][92]

:x_k = f_k(x_{k-1}, v_k) \,

:y_k = h_k(x_k, w_k) \,

여기서 v_k 와 w_k 는 서로 다른 k 에 대해 서로 독립적이며, 어떤 확률 분포를 따르는 노이즈이다. v_k 를 시스템 노이즈, w_k 를 관측 노이즈라고 부른다. 또한, f_k(\cdot) 와 h_k(\cdot) 는 알려진 함수이다.

칼만 필터의 상태 방정식은 상태 공간 모델의 일종이며, x_k 와 y_k 가 실수 열 벡터이고, 함수 f_k(\cdot) 와 h_k(\cdot) 가 선형이며, v_k 와 w_k 가 다변량 정규 분포를 따른다고 가정하면 다음과 같이 표현할 수 있다.

:

\begin{align}

x_k &= F_k x_{k-1} + G_k v_k \\

y_k &= H_k x_k + w_k

\end{align}



x_k 의 확률 분포는 다변량 정규 분포가 되며, 칼만 필터에 의해 베이즈 추정과 정확히 일치하는 해를 얻을 수 있다. 선형이 아닌 경우 등, 칼만 필터는 1차 근사에 불과하다. 입자 필터도 몬테카를로 방법에 의한 근사이지만, 충분한 수의 입자가 있다면 높은 정밀도를 얻을 수 있다.

3. 4. 비선형 필터링 방정식

조건부 확률에 대한 베이즈 정리는 다음과 같이 표현된다.

:p(x_0, \cdots, x_k|y_0,\cdots,y_k) =\frac{p(y_0,\cdots,y_k|x_0, \cdots, x_k) p(x_0,\cdots,x_k)}{p(y_0,\cdots,y_k)}

여기서

:\begin{align}

p(y_0,\cdots,y_k) &=\int p(y_0,\cdots,y_k|x_0,\cdots, x_k) p(x_0,\cdots,x_k) dx_0\cdots dx_k \\

p(y_0,\cdots, y_k|x_0,\cdots ,x_k) &=\prod_{l=0}^{k} p(y_l|x_l) \\

p(x_0,\cdots, x_k) &=p_0(x_0)\prod_{l=1}^{k} p(x_l|x_{l-1})

\end{align}

입자 필터는 근사적인 방법이지만, 충분한 입자를 사용하면 매우 정확한 결과를 얻을 수 있다.[2][4][5][49][50] 비선형 필터링 방정식은 다음과 같은 재귀적인 형태로 주어진다.

:\begin{align}

p(x_k|y_0,\cdots,y_{k-1}) &\stackrel{\text{updating}}{\longrightarrow} p(x_k|y_0,\cdots,y_k)=\frac{p(y_k|x_k)p(x_k|y_0,\cdots,y_{k-1})}{\int p(y_k|x'_k)p(x'_k|y_0,\cdots,y_{k-1})dx'_k} \\

&\stackrel{\text{prediction}}{\longrightarrow}p(x_{k+1}|y_0,\cdots,y_k)=\int p(x_{k+1}|x_k) p(x_k|y_0,\cdots,y_k) dx_k

\end{align}

''k'' = 0일 때, p(x_0|y_0,\cdots,y_{k-1})=p(x_0)으로 정의한다. 비선형 필터링 문제는 이러한 조건부 분포를 순차적으로 계산하는 것이다.

3. 5. 페인만-카츠 공식

시간 범위 ''n''과 관측 시퀀스 Y_0=y_0,\cdots,Y_n=y_n을 고정하고, 각 ''k'' = 0, ..., ''n''에 대해 G_k(x_k)=p(y_k|x_k)로 설정한다.

이 표기법에서, 원점 ''k'' = 0부터 시간 ''k'' = ''n''까지 X_k의 궤적 집합에 대한 모든 유계 함수 ''F''에 대해 페인만-카츠 공식은 다음과 같다.

:\begin{align}

\int F(x_0,\cdots,x_n) p(x_0,\cdots,x_n|y_0,\cdots,y_n) dx_0\cdots dx_n &= \frac{\int F(x_0,\cdots,x_n) \left\{\prod\limits_{k=0}^{n} p(y_k|x_k)\right\}p(x_0,\cdots,x_n) dx_0\cdots dx_n}{\int \left\{\prod\limits_{k=0}^{n} p(y_k|x_k)\right\}p(x_0,\cdots,x_n) dx_0\cdots dx_n}\\

&=\frac{E\left(F(X_0,\cdots,X_n)\prod\limits_{k=0}^{n} G_k(X_k)\right)}{E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)}

\end{align}

페인만-카츠 경로 적분 모델은 계산 물리학, 생물학, 정보 이론 및 컴퓨터 과학을 포함한 다양한 과학 분야에서 응용된다.[8][53][5] 그 해석은 응용 분야에 따라 달라진다. 예를 들어, 상태 공간의 일부 하위 집합의 지표 함수 G_n(x_n)=1_A(x_n)을 선택하면, 주어진 튜브 내에 머무르는 경우 마르코프 체인의 조건부 분포를 나타낸다. 즉, 다음과 같다.

:E\left(F(X_0,\cdots,X_n) | X_0\in A, \cdots, X_n\in A\right) =\frac{E\left(F(X_0,\cdots,X_n)\prod\limits_{k=0}^{n} G_k(X_k)\right)}{E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)}

그리고

:P\left(X_0\in A,\cdots, X_n\in A\right)=E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)

정규화 상수가 엄격하게 양수인 경우에 한해서이다.

4. 파티클 필터 알고리즘

파티클 필터는 시스템에 제안된 확률분포를 바탕으로 임의로 생성된 입력을 여러 개 가하여 종합함으로써 시스템의 정보를 추정하는 방식으로 동작한다.

입자 필터는 관측 변수가 주어졌을 때 상태 변수의 사후 밀도를 추정하는 것을 목표로 하며, 은닉 마르코프 모델과 함께 사용된다. 관측 가능한 변수는 알려진 함수를 통해 숨겨진 변수에 연결된다. 일반적인 입자 필터는 관측 측정 프로세스를 사용하여 숨겨진 상태의 사후 분포를 추정한다. 필터링 문제는 임의의 시간 단계 ''k''에서 관측 과정의 값을 고려하여 숨겨진 상태의 값을 순차적으로 추정하는 것이다.

X_k의 모든 베이지안 추정은 사후 밀도 p(x_k|y_0,y_1,...,y_k)에서 파생된다. 입자 필터 방법론은 유전형 입자 알고리즘과 관련된 경험적 측정을 사용하여 이러한 조건부 확률의 근사치를 제공한다.

입자 필터에서 관측 불가능한 상태 x_k와 관측값 y_k는 다음을 만족하는 1계 마르코프 과정으로 표현된다.

:x_k|x_{k-1} \sim p_{x_k|x_{k-1}}(x|x_{k-1})

:y_k|x_k \sim p_{y|x}(y|x_k)

이는 상태 방정식으로 표현될 수 있으며, 칼만 필터는 이러한 상태 방정식의 특수한 경우이다. 칼만 필터는 선형성과 정규성 가정을 통해 정확한 해를 제공하지만, 입자 필터는 몬테카를로 방법을 통해 비선형 또는 비정규 분포 문제에서도 높은 정밀도를 얻을 수 있다.

'''Sampling Importance Resampling (SIR)''' 알고리즘[89][90]은 널리 사용되는 입자 필터 알고리즘으로, 필터링 확률 분포를 가중치를 가진 입자들로 근사한다. SIR은 중요도 샘플링의 순차적 버전이며, 가중 평균을 통해 함수 추정값을 근사한다.

:\int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx \sum_{L=1}^P w^{(L)} f(x_k^{(L)})

최적의 제안 분포는 \pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1},y_{k}) 이지만, 사전 전이 확률 p(x_k|x_{k-1})을 제안 분포로 사용하는 경우가 많다. SIR 필터는 재샘플링을 통해 알고리즘의 축퇴를 방지하며, 층화 추출법이 분산 측면에서 최적이다.[89]

SIR 방법의 단계는 다음과 같다.

1. 제안 분포에서 입자 샘플링: x^{(L)}_k \sim \pi(x_k|x^{(L)}_{0:k-1},y_{0:k})

2. 가중치 업데이트 및 정규화: \hat{w}^{(L)}_k = w^{(L)}_{k-1} \frac{p(y_k|x^{(L)}_k) p(x^{(L)}_k|x^{(L)}_{k-1})} {\pi(x_k^{(L)}|x^{(L)}_{0:k-1},y_{0:k})}

3. 정규화된 가중치 계산: w^{(L)}_k = \frac{\hat{w}^{(L)}_k}{\sum_{J=1}^P \hat{w}^{(J)}_k}

4. 유효 입자 수 추정: \hat{N}_\mathit{eff} = \frac{1}{\sum_{L=1}^P\left(w^{(L)}_k\right)^2}

5. 유효 입자 수가 임계값보다 적으면 재샘플링 실행

'''직접법'''은 다른 입자 필터에 비해 간단하며, 합성 및 기각 샘플링을 이용한다. k번째 샘플을 생성하기 위한 절차는 다음과 같다.

1. n = 1로 초기화

2. 이산 균등 분포에서 L 생성

3. 확률 분포 p_{x_k|x_{k-1}}(x|x_{k-1|k-1}^{(L)})에서 테스트 입자 \hat{x} 생성

4. \hat{x}를 사용하여 p_{y|x}(y_k|\hat{x})에서 \hat{y}의 확률 생성

5. 균등 분포에서 u 생성

6. u와 \hat{y} 비교 후 기각/수용 결정

7. n > P이면 종료

입자 필터의 수렴성 분석은 1996년 피에르 델 모랄(Pierre Del Moral)에 의해 시작되었으며,[2][4] 1990년대 말 피에르 델 모랄과 앨리스 기오네(Alice Guionnet)는 시간 매개변수와 관련된 최초의 균일 수렴 결과를 개발했다.[49][50]

4. 1. 유전자형 입자 알고리즘

파티클 필터는 관측 변수가 주어졌을 때 상태 변수의 사후 밀도를 추정하는 데 사용되는 방법이다. 이 방법은 유전자 알고리즘의 원리를 활용하며, 선택-업데이트 단계와 돌연변이-예측 단계를 거친다.
선택-업데이트 단계: 조건부 분포를 따르는 N개의 독립적인 확률 변수를 샘플링한다. 이 단계는 다음 식으로 표현된다.

:\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{j=1}^Np(y_k|\xi^j_k)} \delta_{\xi^i_k}(dx_k)

여기서 \delta_a는 주어진 상태 a에서의 디랙 델타 척도를 나타낸다.
돌연변이-예측 단계: 각 선택된 입자에서 독립적으로 전이를 샘플링한다. 이 단계는 다음 식으로 표현된다.

:\widehat{\xi}^i_k \longrightarrow\xi^i_{k+1} \sim p(x_{k+1}|\widehat{\xi}^i_k), \qquad i=1,\cdots,N.

위의 식에서 p(y_k|\xi^i_k)는 x_k=\xi^i_k에서 평가된 우도 함수 x_k\mapsto p(y_k|x_k)를 나타내고, p(x_{k+1}|\widehat{\xi}^i_k)는 x_k=\widehat{\xi}^i_k에서 평가된 조건부 밀도 p(x_{k+1}|x_k)를 나타낸다.

각 시간 ''k''에서 입자 근사는 다음과 같다.

:\widehat{p}(dx_k|y_0,\cdots,y_k):=\frac{1}{N} \sum_{i=1}^N \delta_{\widehat{\xi}^i_k} (dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_k) \approx_{N\uparrow\infty}

\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{i=1}^N p(y_k|\xi^j_k)} \delta_{\xi^i_k}(dx_k)

:\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1})

이러한 입자 근사는 유전자 알고리즘 및 진화 컴퓨팅에서 비례 선택을 가진 유전자 알고리즘으로 해석될 수 있다.[5][44][47]

4. 2. 몬테카를로 방법

파티클 필터는 마르코프 연쇄 몬테카를로와 같이, 필터링 밀도를 근사하는 일련의 표본을 생성한다.[53][5]

:p(x_k|y_0, \cdots, y_k).

예를 들어, X_k의 근사 사후 분포에서 위첨자로 표시된 ''N''개의 표본이 있을 수 있다.

:\widehat{\xi}_k^1, \cdots, \widehat{\xi}_k^{N}.

그러면, 필터링 분포에 대한 기대값은 다음과 같이 근사된다.

:\int f(x_k)p(x_k|y_0,\cdots,y_k) \, dx_k\approx_{N\uparrow\infty}\frac{1}{N} \sum_{i=1}^Nf\left(\widehat{\xi}_k^{i}\right)=\int f(x_k) \widehat{p}(dx_k|y_0,\cdots,y_k)

여기서

:\widehat{p}(dx_k|y_0,\cdots,y_k)=\frac{1}{N}\sum_{i=1}^N \delta_{\widehat{\xi}^i_k}(dx_k)

\delta_a는 주어진 상태 a에서 '''디랙 측도'''를 나타낸다. 몬테카를로 방법과 마찬가지로 함수 ''f''는 일부 근사 오차까지 분포의 모든 모멘트 등을 제공할 수 있다.

:p(dx_k|y_0,\cdots,y_k):=p(x_k|y_0,\cdots,y_k) dx_k \approx_{N\uparrow\infty} \widehat{p}(dx_k|y_0,\cdots,y_k)=\frac{1}{N}\sum_{i=1}^N \delta_{\widehat{\xi}^{i}_k}(dx_k)

파티클 필터는 다른 샘플링 방법과 마찬가지로 필터링 확률 분포 p(x_k|y_0,\dots,y_k)를 근사하는 점열을 생성한다. 따라서 P개의 샘플 점이 있다면, 필터링 확률 분포에 따른 기대값은

:\int f(x_k)p(x_k|y_0,\dots,y_k)dx_k\approx\frac1P\sum_{L=1}^Pf(x_k^{(L)})

에 의해 근사된다. 그리고 일반적인 몬테카를로 방법과 마찬가지로 f(\cdot)를 적절히 조정함으로써, 근사 정도에 따른 차수까지의 모멘트를 얻을 수 있다.

4. 3. 평균장 입자 시뮬레이션

비선형 필터링 진화는 확률 측도 집합에서의 동적 시스템으로 해석될 수 있다. 평균장 입자 방법은 이러한 확률 측도를 근사하는 가장 간단한 방법 중 하나이다.

입자 필터는 여러 가지 방법으로 해석될 수 있는데, 확률론적 관점에서는 비선형 필터링 방정식의 평균장 입자 해석과 일치한다. 최적 필터 진화의 업데이트-예측 전이는 개체의 고전적인 유전형 선택-돌연변이 전이로 해석될 수도 있다. 순차 중요도 재표본 추출 기술은 중요도 표본 추출과 부트스트랩 재표본 추출 단계를 결합하여 필터링 전이에 대한 또 다른 해석을 제공한다. 마지막으로, 입자 필터는 재활용 메커니즘을 갖춘 수락-거부 방법론으로 볼 수 있다.[53][5]

4. 4. 수렴 결과

입자 필터의 수렴성 분석은 1996년 피에르 델 모랄(Pierre Del Moral)에 의해 시작되었으며,[2][4] 필터링 방정식이 안정적일 때 입자 추정치의 편향과 분산은 비점근적 균일 추정치에 의해 제어된다. 1990년대 말 피에르 델 모랄과 앨리스 기오네(Alice Guionnet)는 시간 매개변수와 관련된 최초의 균일 수렴 결과를 개발했다.[49][50]

:\sup_{k\geqslant 0}\left\vert E\left(\widehat{I}_k(f)\right)-I_k(f)\right\vert\leqslant \frac{c_1}{N}

:\sup_{k\geqslant 0}E\left(\left[\widehat{I}_k(f)-I_k(f)\right]^2\right)\leqslant \frac{c_2}{N}

이는 1로 제한된 모든 함수 ''f''와 유한 상수 c_1,c_2에 대해 성립한다. 또한, 모든 x\geqslant 0에 대해 다음이 성립한다.

:\mathbf{P} \left ( \left| \widehat{I}_k(f)-I_k(f)\right|\leqslant c_1 \frac{x}{N}+c_2 \sqrt{\frac{x}{N}}\land \sup_{0\leqslant k\leqslant n}\left| \widehat{I}_k(f)-I_k(f)\right|\leqslant c \sqrt{\frac{x\log(n)}{N}} \right ) > 1-e^{-x}

위 식에서 c_1, c_2는 입자 추정치의 점근적 편향 및 분산과 관련된 유한 상수이고, ''c''는 유한 상수이다.

5. 계보 트리 및 무편향성

1990년대 말, 피에르 델 모랄과 앨리스 기오네는 시간 매개변수와 관련된 최초의 균일 수렴 결과를 개발했다.[49][50] 2001년에는 P. 델 모랄과 L. 미클로가 계보 트리 기반 입자 필터 스무더에 대한 최초의 엄격한 분석을 수행했다.[51]

조상 계보를 시간 순으로 추적하면 각 시간 단계에서 입자 근사값을 얻을 수 있으며, 이는 신호 궤적의 사후 밀도와 관련된 진화 방정식의 평균장 입자 해석과 일치한다.[54]

또한, 1996년 피에르 델 모랄의 논문[2]에는 우도 함수 및 정규화되지 않은 조건부 확률 측도의 입자 근사치의 무편향 속성에 대한 증명이 포함되어 있다.

5. 1. 계보 트리 기반 입자 스무딩

P. 델 모랄과 L. 미클로는 2001년에 계보 트리 기반 입자 필터 스무더에 대한 최초의 엄격한 분석을 수행했다.[51]

조상 계보를 시간 순으로 추적하면 각 시간 단계 ''k''에서 입자 근사도를 얻을 수 있다.

신호의 무작위 궤적에 대한 경계 함수 ''F''에 대해, 조상 계보의 진화는 신호 궤적의 사후 밀도와 관련된 진화 방정식의 평균장 입자 해석과 일치한다.[54]

5. 2. 우도 함수의 무편향 입자 추정

Likelihood function영어에 대한 편향되지 않은 입자 근사는 다음 곱셈 공식을 사용하여 설계할 수 있다.[2] 개선된 분산 추정치는 관련 연구에서 찾을 수 있다.[5][53]

:p(y_0,\cdots,y_n)=\prod_{k=0}^n p(y_k|y_0,\cdots,y_{k-1})

여기서

:p(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) p(dx_k|y_0,\cdots,y_{k-1})

이고, ''k'' = 0일 때, p(y_0|y_0,\cdots,y_{-1})=p(y_0)와 p(x_0|y_0,\cdots,y_{-1})=p(x_0)이다. 위 수식에서 p(x_k|y_0,\cdots,y_{k-1})dx_k를 경험적 근사

:\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1})

로 대체하면, 다음과 같은 우도 함수에 대한 편향되지 않은 입자 근사를 설계할 수 있다.

:p(y_0,\cdots,y_n) \approx_{N\uparrow\infty} \widehat{p}(y_0,\cdots,y_n)=\prod_{k=0}^n \widehat{p}(y_k|y_0,\cdots,y_{k-1})

여기서

:\widehat{p}(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) \widehat{p}(dx_k|y_0,\cdots,y_{k-1})=\frac{1}{N}\sum_{i=1}^N p(y_k|\xi^i_k)

이며, p(y_k|\xi^i_k)는 x_k=\xi^i_k에서 평가된 밀도 p(y_k|x_k)를 나타낸다.

5. 3. 후방 입자 스무더

Bayes영어 규칙을 사용하여 후방 입자 근사를 얻을 수 있으며, 이는 시간 역순으로 실행되는 마르코프 연쇄의 임의 경로 확률과 관련된다.[54]

시간 순으로 조상 계보를 추적하면 각 시간 단계 ''k''에서 다음과 같은 입자 근사값을 얻는다.[5]

:\begin{align}

\widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) &:=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\widehat{\xi}^i_{0,k},\cdots,\widehat{\xi}^i_{0,k}\right)}(d(x_0,\cdots,x_k)) \\

&\approx_{N\uparrow\infty} p(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) \\

&\approx_{N\uparrow\infty} \sum_{i=1}^N \frac{p(y_k|\xi^i_{k,k})}{\sum_{j=1}^Np(y_k|\xi^j_{k,k})} \delta_{\left(\xi^i_{0,k},\cdots,\xi^i_{0,k}\right)}(d(x_0,\cdots,x_k))

\end{align}

:\begin{align}

\widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) &:=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\xi^i_{0,k},\cdots,\xi^i_{k,k}\right)}(d(x_0,\cdots,x_k)) \\

&\approx_{N\uparrow\infty} p(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\

&:=p(x_0,\cdots,x_k|y_0,\cdots,y_{k-1}) dx_0,\cdots,dx_k

\end{align}

이러한 경험적 근사는 입자 적분 근사와 동일하다.

신호의 무작위 궤적에 대한 경계 함수 ''F''에 대해, 조상 계보의 진화는 신호 궤적의 사후 밀도와 관련된 진화 방정식의 평균장 입자 해석과 일치한다.[54][5][53]

Bayes영어 규칙을 사용하면 다음 공식을 얻는다.

:p(x_0,\cdots,x_n|y_0,\cdots,y_{n-1}) = p(x_n | y_0,\cdots,y_{n-1}) p(x_{n-1}|x_n, y_0,\cdots,y_{n-1} ) \cdots p(x_1|x_2,y_0,y_1) p(x_0|x_1,y_0)

여기서 다음이 성립한다.

: \begin{align}

p(x_{k-1}|x_{k},(y_0,\cdots,y_{k-1})) &\propto p(x_{k}|x_{k-1})p(x_{k-1}|(y_0,\cdots,y_{k-1})) \\

p(x_{k-1}|(y_0,\cdots,y_{k-1}) &\propto p(y_{k-1}|x_{k-1})p(x_{k-1}|(y_0,\cdots,y_{k-2})

\end{align}

이는 다음을 의미한다.

:p(x_{k-1}|x_k, (y_0,\cdots,y_{k-1}))=\frac{p(y_{k-1}|x_{k-1})p(x_{k}|x_{k-1})p(x_{k-1}|y_0,\cdots,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})p(x_{k}|x'_{k-1})p(x'_{k-1}|y_0,\cdots,y_{k-2}) dx'_{k-1}}

단일 단계 최적 예측기 p(x_{k-1}|(y_0,\cdots,y_{k-2}))dx_{k-1}을 입자 경험적 측도로 대체하면 다음과 같다.

:\begin{align}

p(dx_{k-1}| x_{k},(y_0,\cdots,y_{k-1})) &\approx_{N\uparrow\infty} \widehat{p}(dx_{k-1}|x_{k},(y_0,\cdots,y_{k-1})) \\

&:= \frac{p(y_{k-1}|x_{k-1}) p(x_{k}|x_{k-1}) \widehat{p}(dx_{k-1}|y_0,\cdots,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})~p(x_{k}| x'_{k-1}) \widehat{p}(dx'_{k-1}|y_0,\cdots,y_{k-2})}\\

&= \sum_{i=1}^{N} \frac{p(y_{k-1}|\xi^i_{k-1}) p(x_{k}|\xi^i_{k-1})}{\sum_{j=1}^{N} p(y_{k-1}|\xi^j_{k-1}) p(x_{k}|\xi^j_{k-1})} \delta_{\xi^i_{k-1}}(dx_{k-1})

\end{align}

결론적으로 후방 입자 근사값은 다음과 같다.

:\begin{align}

\widehat{p}_{backward} (d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1})) = \widehat{p}(dx_n|(y_0,\cdots,y_{n-1})) \widehat{p}(dx_{n-1}|x_n,(y_0,\cdots,y_{n-1})) \cdots \widehat{p}(dx_1|x_2,(y_0,y_1)) \widehat{p}(dx_0|x_1,y_0)

\end{align}

확률 측도 \widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))는 시간 k=n에서 시간 k=0으로 거꾸로 실행되고 각 시간 단계 k에서 입자 모집단 \xi^i_k, i=1,\cdots,N.와 관련된 상태 공간에서 진화하는 마르코프 연쇄 \left(\mathbb X^{\flat}_{k,n}\right)_{0\leqslant k\leqslant n}의 임의 경로 확률이다.

  • 처음에는 (시간 k=n에서) 연쇄 \mathbb X^{\flat}_{n,n}은 다음 분포로 상태를 무작위로 선택한다.


:\widehat{p}(dx_{n}|(y_0,\cdots,y_{n-1}))=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_{n}}(dx_{n})

  • 시간 k에서 시간 (k-1)까지, 시간 k에서 \mathbb X^{\flat}_{k,n}=\xi^i_k 상태에서 시작하는 체인은 시간 (k-1)에 가중 확률로 선택된 무작위 상태 \mathbb{X}^{\flat}_{k-1,n}으로 이동한다.


:\widehat{p}(dx_{k-1}|\xi^i_{k},(y_0,\cdots,y_{k-1}))= \sum_{j=1}^N\frac{p(y_{k-1}|\xi^j_{k-1}) p(\xi^i_{k}|\xi^j_{k-1})}{\sum_{l=1}^Np(y_{k-1}|\xi^l_{k-1}) p(\xi^i_{k}|\xi^l_{k-1})}~\delta_{\xi^j_{k-1}}(dx_{k-1})

위의 공식에서 \widehat{p}(dx_{k-1}|\xi^i_{k},(y_0,\cdots,y_{k-1}))는 x_k=\xi^i_{k}에서 평가된 조건부 분포 \widehat{p}(dx_{k-1}|x_k, (y_0,\cdots,y_{k-1}))를 나타낸다. p(y_{k-1}|\xi^j_{k-1}) 및 p(\xi^i_k|\xi^j_{k-1})은 x_k=\xi^i_{k} 및 x_{k-1}=\xi^j_{k-1}에서 평가된 조건부 밀도 p(y_{k-1}|x_{k-1}) 및 p(x_k|x_{k-1})를 나타낸다.

이러한 모델을 사용하면, 마르코프 전이와 관련된 행렬 연산을 통해 밀도 p((x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))에 대한 적분을 계산할 수 있다.[55]

5. 4. 수렴 결과

페이만-칵(Feynman-Kac) 입자 방법론 및 관련 입자 필터 알고리즘에 대한 이론은 2000년과 2004년에 책으로 개발되었다.[8][5] 이러한 추상적인 확률적 모델은 유전자형 알고리즘, 입자 및 부트스트랩 필터, 상호작용하는 칼만 필터(일명 라오-블랙웰화(Rao-Blackwellized) 입자 필터[52]), 중요도 샘플링 및 재샘플링 스타일 입자 필터 기법(필터링 및 스무딩 문제를 해결하기 위한 계보 트리 기반 및 입자 역방향 방법론 포함)을 포괄한다.

필터링 방정식이 안정적일 때, 우도 함수에 대한 입자 근사는 편향되지 않으며 상대적인 분산은 제어된다. 계보 트리의 조상 경로에 기반한 입자 추정치의 편향과 분산은 비점근적 균일 추정치에 의해 제어된다.

다음과 같은 곱셈 공식을 사용한다.

:p(y_0,\cdots,y_n)=\prod_{k=0}^n p(y_k|y_0,\cdots,y_{k-1})

여기서

:p(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) p(dx_k|y_0,\cdots,y_{k-1})

그리고 ''k'' = 0일 때, p(y_0|y_0,\cdots,y_{-1})=p(y_0)와 p(x_0|y_0,\cdots,y_{-1})=p(x_0)을 사용한다. 위 수식에서 p(x_k|y_0,\cdots,y_{k-1})dx_k를 경험적 근사

:\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1})

로 대체하면, 다음과 같은 우도 함수에 대한 편향되지 않은 입자 근사를 설계할 수 있다.

:p(y_0,\cdots,y_n) \approx_{N\uparrow\infty} \widehat{p}(y_0,\cdots,y_n)=\prod_{k=0}^n \widehat{p}(y_k|y_0,\cdots,y_{k-1})

여기서

:\widehat{p}(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) \widehat{p}(dx_k|y_0,\cdots,y_{k-1})=\frac{1}{N}\sum_{i=1}^N p(y_k|\xi^i_k)

이며, p(y_k|\xi^i_k)는 x_k=\xi^i_k에서 평가된 밀도 p(y_k|x_k)를 나타낸다. 이 입자 추정치의 설계 및 편향되지 않음 속성은 1996년 논문에서 증명되었다.[2]

6. 순차 중요도 재표본추출 (SIR)

순차 중요도 재표본추출(Sequential Importance Resampling, SIR)은 가중치가 부여된 N개의 샘플 집합을 사용하여 필터링 확률 밀도를 근사하는 알고리즘이다. SIR은 널리 사용되는 입자 필터 알고리즘 중 하나이며, 키타가와 겐시로가 제안한 몬테카를로 필터 및 부트스트랩 필터를 기반으로 한다.[89][90]

SIR 알고리즘에 대한 더 자세한 설명은 몬테카를로 필터 및 부트스트랩 필터 하위 섹션을 참조하라.

6. 1. 몬테카를로 필터 및 부트스트랩 필터

Sampling Importance Resampling영어 (SIR) 알고리즘은 몬테카를로 필터 (키타가와 겐시로 1993[89]) 및 부트스트랩 필터 (Gordon et al. 1993[90])를 기반으로 하는 입자 필터이며, 널리 사용된다. 필터링 확률 분포 p(x_k|y_0,\ldots,y_k)는 P개의 가중치를 가진 입자를 사용하여 근사한다.

:\{(w^{(L)}_k,x^{(L)}_k)~:~L=1,\ldots,P\}.

가중치 w^{(L)}_k는 \sum_{L=1}^P w^{(L)}_k = 1을 만족하며, 입자의 상대적 사후 분포(밀도)의 근사치이다.

SIR은 중요도 샘플링의 순차적 버전(재귀적)이라고 할 수 있다. 중요도 샘플링과 마찬가지로, 함수 f(\cdot)의 추정값은 가중 평균으로 근사할 수 있다.

: \int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx \sum_{L=1}^P w^{(L)} f(x_k^{(L)})

입자 수가 유한하면 알고리즘의 성능은 제안 분포 \pi(x_k|x_{0:k-1},y_{0:k})의 선택에 달려 있다. 최적의 제안 분포는 목표 분포이다.

: \pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1},y_{k})

그러나 사전 전이 확률을 제안 분포로 사용하는 경우가 많다.

: \pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1})

이는 입자를 쉽게 샘플링하고 가중치를 계산할 수 있기 때문이다. 사전 전이 확률을 제안 분포로 사용하는 SIR 필터는 부트스트랩 필터 또는 컨덴세이션 알고리즘으로도 알려져 있다.

알고리즘의 퇴화(하나를 제외한 모든 가중치가 0에 가까워지는 현상)를 방지하기 위해 재표본추출이 수행된다. 알고리즘의 성능은 재표본추출 방식에 따라서도 달라진다. 키타가와 겐시로 (1993[89])가 제안한 층화 추출법은 분산 측면에서 최적이다.

SIR 방법의 단계는 다음과 같다.

:1) L=1,\ldots,P에 대해, 제안 분포에서 입자를 샘플링한다.

::

x^{(L)}_k \sim \pi(x_k|x^{(L)}_{0:k-1},y_{0:k})



:2) L=1,\ldots,P에 대해, 가중치를 업데이트하고 정규화 상수를 구한다.

::

\hat{w}^{(L)}_k = w^{(L)}_{k-1} \frac{p(y_k|x^{(L)}_k) p(x^{(L)}_k|x^{(L)}_{k-1})} {\pi(x_k^{(L)}|x^{(L)}_{0:k-1},y_{0:k})}



이때 \pi(x_k^{(L)}|x^{(L)}_{0:k-1},y_{0:k}) = p(x^{(L)}_k|x^{(L)}_{k-1})이면 업데이트 식은 다음과 같이 간단해진다.

::

\hat{w}^{(L)}_k = w^{(L)}_{k-1} p(y_k|x^{(L)}_k)



:3) L=1,\ldots,P에 대해, 정규화된 가중치를 계산한다.

::

w^{(L)}_k = \frac{\hat{w}^{(L)}_k}{\sum_{J=1}^P \hat{w}^{(J)}_k}



:4) 유효 입자 수의 추정량을 계산한다.

::

\hat{N}_\mathit{eff} = \frac{1}{\sum_{L=1}^P\left(w^{(L)}_k\right)^2}



:5) 유효 입자 수가 주어진 임계값보다 적으면 (\hat{N}_\mathit{eff} < N_{thr}) 재표본추출을 실행한다.

::a) 현재 입자 집합에서 가중치에 비례하는 확률로 P개의 입자를 추출하고, 현재 입자 집합을 새로운 입자 집합으로 대체한다.

::b) L=1,\ldots,P에 대해, w^{(L)}_k = 1/P로 설정한다.

''Sequential Importance Resampling''은 SIR 필터를 지칭하는 용어로 사용될 수 있다.

6. 2. 순차 중요도 샘플링 (SIS)

순차 중요도 샘플링(Sequential Importance Sampling, SIS)은 SIR 알고리즘에서 재표본 추출(resampling) 단계를 제외한 것이다.[53]

6. 3. "직접 버전" 알고리즘

"직접 버전" 알고리즘은 구성과 기각 샘플링을 사용하여 구현할 수 있다. 이 방법은 다른 입자 필터에 비해 비교적 간단하다.

k번째 단계에서 하나의 샘플 x를 p_{x_k|y_{1:k}}(x|y_{1:k})에서 생성하기 위해 다음과 같은 절차를 따른다.

1) n = 1로 설정한다.

2) \{1,..., P\} 집합에서 이산 균등 분포를 사용하여 L을 생성한다.

3) 확률 분포 p_{x_k|x_{k-1}}(x|x_{k-1|k-1}^{(L)})에서 테스트 입자 \hat{x}를 생성한다.

4) \hat{x}를 사용하여 p_{y|x}(y_k|\hat{x})에서 \hat{y}의 확률을 생성한다. 여기서 y_k는 관측값이다.

5) [0, m_k] 구간에서 균등 분포를 사용하여 또 다른 수 u를 생성한다. 여기서 m_k = \sup_x p_{y|x}(y_k|x) 이다.

6) u와 \hat{y}를 비교한다.

6a) u가 더 크면 2단계부터 다시 반복한다.

6b) u가 더 작으면 \hat{x}를 x_{k|k}^{(p)}로 저장하고 n을 1 증가시킨다.

7) n > P이면 알고리즘을 종료한다.

이 알고리즘의 목표는 k-1번째 단계에서 P개의 입자를 생성하여 k번째 단계에서 P개의 입자를 만드는 것이다. 이를 위해 마르코프 방정식을 통해 x_{k-1}에서 x_k를 생성할 수 있어야 한다. 알고리즘은 k-1번째 단계의 P개 입자를 사용하여 k번째 단계의 입자를 생성하고, k번째 단계에서 P개의 입자가 생성될 때까지 2~6단계를 반복한다.

이 과정을 x를 2차원 배열로 생각하면 더 쉽게 이해할 수 있다. 한 차원은 k (시간 단계)이고, 다른 차원은 입자 번호 L이다. 예를 들어, x(k,L)은 k번째 단계에서 L번째 입자를 나타내며, x_k^{(L)}로도 표기할 수 있다. 3단계에서는 k-1번째 단계에서 임의로 선택된 입자 x_{k-1}^{(L)}로부터 "잠재적인" x_k를 생성하고, 6단계에서 수용/기각 결정이 내려진다. 즉, x_k의 값은 이전에 생성된 x_{k-1}을 기반으로 생성된다.

7. 응용 분야

입자 필터와 파인만-카츠 입자 방법론은 잡음이 있는 관측이나 강한 비선형성을 다루는 효과적인 수단으로서 여러 분야에서 응용된다.


  • 베이즈 추론, 기계 학습, 위험 분석 및 희귀 사건 샘플링
  • 생물 정보학
  • 계산 과학
  • 경제학, 금융 수학 및 수리 금융: 입자 필터는 거시 경제학의 동적 확률 일반 균형 모델 및 옵션 가격 결정과 관련된 고차원 및/또는 복잡한 적분을 계산하는 데 필요한 시뮬레이션을 수행할 수 있다.
  • 공학
  • 감염성 질환 역학에서는 계절성 인플루엔자 유행 예측과 같은 여러 유행 예측 문제에 적용되었다.
  • 고장 감지 및 격리: 관찰자 기반 체계에서 입자 필터는 예상 센서 출력을 예측하여 고장 격리를 가능하게 할 수 있다.
  • 분자 화학 및 계산 물리학
  • 약동학
  • 계통 발생학
  • 로봇 공학, 인공 지능: 몬테카를로 위치 추정은 이동 로봇 위치 추정의 사실상 표준이다.
  • 신호 및 이미지 처리: 시각적 위치 추정, 추적, 특징 인식

8. 기타 파티클 필터


  • 보조 파티클 필터[82]
  • 비용 기준 파티클 필터
  • 지수 자연 파티클 필터[83]
  • 파인만-카츠 및 평균장 파티클 방법론[2][53][5]
  • 가우시안 파티클 필터
  • 가우스-에르미트 파티클 필터
  • 계층적/확장 가능한 파티클 필터[84]
  • 너지드 파티클 필터[85]
  • 입자 마르코프 연쇄 몬테카를로 (예: 의사-마지널 메트로폴리스-헤이스팅스 알고리즘)
  • 라오-블랙웰화 파티클 필터[52]
  • 정규화된 보조 파티클 필터[86]
  • 기각-샘플링 기반 최적 파티클 필터[87][88]
  • 언센티드 파티클 필터

참조

[1] 논문 Sequential Monte Carlo: A Unified Review 2023-05-03
[2] 논문 Non Linear Filtering: Interacting Particle Solution. http://people.bordea[...] 1996
[3] 논문 Sequential Monte Carlo Methods for Dynamic Systems 1998-09-01
[4] 논문 Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems http://projecteuclid[...] 1998
[5] 서적 Feynman-Kac formulae. Genealogical and interacting particle approximations. https://www.springer[...] Springer. Series: Probability and Applications
[6] 논문 On Adaptive Resampling Procedures for Sequential Monte Carlo Methods http://hal.inria.fr/[...] 2012
[7] 서적 Feynman-Kac formulae. Genealogical and interacting particle approximations https://www.springer[...] Springer
[8] 서적 Séminaire de Probabilités XXXIV http://archive.numda[...] 2000
[9] 논문 A Moran particle system approximation of Feynman-Kac formulae. 2000
[10] 논문 Particle methods: An introduction with applications
[11] 논문 Monte-Carlo calculations of the average extension of macromolecular chains 1955
[12] 논문 Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups http://journals.camb[...] 2003
[13] 논문 Diffusion Monte Carlo Methods with a fixed number of walkers http://qmcchem.ups-t[...] 2000
[14] 논문 Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms 1993
[15] 논문 Asymptotic stability of beneš filters 1999-01-01
[16] 논문 Des resultats de non existence de filtre de dimension finie 1984-01-01
[17] 논문 Scalable optimal Bayesian classification of single-cell trajectories under regulatory model uncertainty
[18] 서적 Fundamental Aspects of Operational Risk and Insurance Analytics: A Handbook of Operational Risk https://onlinelibrar[...] Wiley 2015-02-27
[19] 서적 Advances in Heavy Tailed Risk Modeling: A Handbook of Operational Risk https://onlinelibrar[...] Wiley 2015-02-20
[20] 논문 Computing machinery and intelligence 1950-10
[21] 논문 Esempi numerici di processi di evoluzione
[22] 논문 Symbiogenetic evolution processes realized by artificial methods
[23] 논문 Poor Man's Monte Carlo
[24] 논문 Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life
[25] 웹사이트 Adaptation in Natural and Artificial Systems {{!}} The MIT Press https://mitpress.mit[...] 2015-06-06
[26] 논문 Simulation of genetic systems by automatic digital computers. I. Introduction
[27] 서적 Computer Models in Genetics McGraw-Hill
[28] 서적 Computer Simulation in Genetics John Wiley & Sons
[29] 논문 Observations on the statistical iteration of matrices 1984
[30] 논문 Diffusion Monte Carlo Methods with a fixed number of walkers http://qmcchem.ups-t[...] 2000
[31] 논문 Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms 1993
[32] 논문 Note on census-taking in Monte Carlo calculations http://scienze-como.[...] 1948
[33] 논문 Estimation of particle transmission by random sampling https://dornsifecms.[...] 1951
[34] 논문 A Monte Carlo Filtering and Smoothing Method for Non-Gaussian Nonlinear State Space Models https://www.ism.ac.j[...] 1993-01
[35] 논문 Monte carlo filter and smoother for non-Gaussian nonlinear state space models
[36] 논문 Novel approach to nonlinear/non-Gaussian Bayesian state estimation 1993-04
[37] 논문 Optimal Non-linear Filtering in GPS/INS Integration. http://homepages.laa[...] 2015-06-01
[38] 간행물 Estimation and nonlinear optimal control : An unified framework for particle solutions LAAS-CNRS, Toulouse 1991-04
[39] 간행물 Nonlinear and non-Gaussian particle filters applied to inertial platform repositioning. LAAS-CNRS, Toulouse 1991-09
[40] 간행물 Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Experimental results. null 1992-01
[41] 간행물 Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Theoretical results null 1992-10
[42] 간행물 Particle filters in radar signal processing : detection, estimation and air targets recognition. LAAS-CNRS, Toulouse 1992-12
[43] 간행물 Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. null 1993-01
[44] 논문 Convergence of a branching particle method to the solution of the Zakai 1998
[45] 논문 Nonlinear filtering and measure-valued processes 1997
[46] 논문 A particle approximation of the solution of the Kushner–Stratonovitch equation 1999
[47] 논문 Discrete filtering using branching and interacting particle systems http://web.maths.uns[...] 1999
[48] 논문 Central limit theorem for nonlinear filtering and interacting particle systems 1999
[49] 논문 On the stability of Measure Valued Processes with Applications to filtering 1999
[50] 논문 On the stability of interacting processes with applications to filtering and genetic algorithms http://web.maths.uns[...] 2001
[51] 논문 Genealogies and Increasing Propagation of Chaos For Feynman-Kac and Genetic Models 2001
[52] conference Rao–Blackwellised particle filtering for dynamic Bayesian networks
[53] 서적 Mean field simulation for Monte Carlo integration http://www.crcpress.[...] Chapman & Hall/CRC Press
[54] 논문 Genealogies and Increasing Propagations of Chaos for Feynman-Kac and Genetic Models http://web.maths.uns[...] 2001
[55] 논문 A Backward Particle Interpretation of Feynman-Kac Formulae http://hal.inria.fr/[...] 2010
[56] 논문 On parallel implementation of Sequential Monte Carlo methods: the island particle model 2013
[57] arXiv SMC^2: an efficient algorithm for sequential analysis of state-space models
[58] 논문 Particle Markov chain Monte Carlo methods 2010
[59] arXiv On Feynman-Kac and particle Markov chain Monte Carlo models 2014
[60] 논문 Sequential Monte Carlo Samplers https://www.jstor.or[...] 2006
[61] 논문 Topics in Sequential Monte Carlo Samplers https://www.ssrn.com[...] 2005
[62] 논문 Sequential Monte Carlo Samplers CUED Technical Report https://www.ssrn.com[...] 2004
[63] 서적 Handbook of approximate Bayesian computation CRC Press, Taylor and Francis Group 2019
[64] 논문 Chain ladder method: Bayesian bootstrap versus classical bootstrap https://www.scienced[...] 2010-08-01
[65] 논문 The Monte-Carlo method for filtering with discrete-time observations 2001-07-01
[66] 논문 An adaptive sequential Monte Carlo method for approximate Bayesian computation 2011
[67] 논문 Approximate Bayesian Computation for Smoothing 2014-05-04
[68] 논문 Concentration inequalities for mean field particle models 2011
[69] 서적 On the Concentration Properties of Interacting Particle Processes http://dl.acm.org/ci[...] Now Publishers Inc. 2012
[70] 논문 Adaptive memory-based single distribution resampling for particle filter 2017-10-18
[71] 서적 Bayesian Data Analysis, Third Edition Chapman and Hall/CRC
[72] 논문 A Survey of Sequential Monte Carlo Methods for Economics and Finance https://research.vu.[...]
[73] 논문 Forecasting influenza outbreak dynamics in Melbourne from Internet search query surveillance data
[74] 논문 Intelligent Particle Filter and Its Application to Fault Detection of Nonlinear System
[75] 논문 A Particle Filtering Approach for Fault Detection and Isolation of UAV IMU Sensors: Design, Implementation and Sensitivity Analysis
[76] 논문 Particle filtering-based fault detection in non-linear stochastic systems
[77] 간행물 Pharmacokinetic-Pharmacodynamic Modeling and Simulation Springer
[78] 웹사이트 Monte Carlo Localization: Efficient Position Estimation for Mobile Robots http://www.cs.washin[...] Proc. of the Sixteenth National Conference on Artificial Intelligence John Wiley & Sons Ltd
[79] 서적 Probabilistic Robotics http://www.probabili[...] MIT Press
[80] 논문 Robust monte carlo localization for mobile robots http://robots.stanfo[...]
[81] 논문 A Robust and Accurate Particle Filter-Based Pupil Detection Method for Big Datasets of Eye Video https://link.springe[...]
[82] 논문 Filtering Via Simulation: Auxiliary Particle Filters https://www.questia.[...] 2008-05-06
[83] arXiv Exponential Natural Particle Filter
[84] 논문 Human Motion Capture Using Scalable Body Models
[85] 논문 Nudging the particle filter 2020-03-01
[86] 논문 A Regularized Auxiliary Particle Filtering Approach for System State Estimation and Battery Life Prediction https://escholarship[...]
[87] conference An Optimal Filtering Algorithm for Non-Parametric Observation Models in Robot Localization
[88] 논문 Optimal Filtering for Non-Parametric Observation Models: Applications to Localization and SLAM
[89] 논문 A Monte Carlo filtering and smoothing method for non-Gaussian nonlinear state space models https://www.ism.ac.j[...] 1993-01
[90] 논문 Novel approach to nonlinear/non-Gaussian Bayesian state estimation 1993-04
[91] 서적 時系列解析入門 岩波書店
[92] 서적 予測にいかす統計モデリングの基礎―ベイズ統計入門から応用まで 講談社
[93] 문서 값 또는 가능한 값의 분포라 생각 수도 있다.


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com