• 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note8을 정리하였음을 밝힙니다.
• 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다

Particle Filtering

베이즈 넷의 결합 확률 분포를 얻을 때 정확한 분포를 찾으려면 연산 비용이 너무 크기 때문에 일반적으로 샘플링 기법을 활용한다. HMM 또한 베이즈 넷의 샘플링 기법과 같이 정확한 확률 분포를 얻어내기 위한 연산 비용이 너무 과도해질 때 대안으로 사용하는 방법이 존재한다. 파티클 필터링(particle filtering)이라는 알고리즘이다.

파티클 필터링은 파티클, 즉 입자들의 집합이 상태 그래프 상에서 어떻게 시뮬레이션되는지 보여준다. 랜덤 변수의 빌리프 확률 분포를 근사할 수 있다.

$n$개의 파티클을 통해 확률 분포를 나타내보자. 파티클 하나는 타임 스탬프 t에 따라 나타나는 랜덤 변수 도메인 값 중 하나다. 도메인이 될 수 있는 개수를 $d$라고 하자. 일반적으로 파티클 개수는 도메인 개수보다 작게 설정하자. 그렇다면 파티클이라는 이 입자가 어떻게 표현되는지가 확률 분포와 어떻게 연관될까? 특정 상태 특정 타임 스탬프의 파티클은 전적으로 동일한 시뮬레이션 상의 파티클 개수에 의존적이라고 할 수 있다.

$i$ 날 온도 $T$도가 나올 빌리프 확률 분포를 시뮬레이션해보자. 온도를 10도에서 20도까지로 한정하고 파티클 개수 역시 10개로 뽑는다고 가정한다. 파티클이 가질 값은 대략 이렇다.

$[15,12,12,10,18,14,12,11,11,10]$ 파티클 개수 10으로 해당 수가 나올 확률을 근사해보자.

$T_i$	10	11	12	13	14	15	16	17	18	19	20
$B(T_i)$	0.2	0.2	0.3	0	0.1	0.1	0	0	0.1	0	0

이 파티클 리스트에서 빌리프 확률 분포를 복구해보자.

Particle Filtering Simulation

위처럼 파티클 리스트 초깃값을 구하는 방법은 다양하다. 파티클을 랜덤하게, 균등하게, 특정 초기 분포에 따라 뽑아도 된다. 초깃값을 만든 뒤 총 두 번의 업데이트를 통해 빌리프 확률 분포를 구하는데, 그 방법은 포워드 알고리즘의 작동 방식과 정확히 일치한다. 타임 스탬프 $t$ 값이 추가될 때 한 번 업데이트하고, 각 타임 스탬프에서 관측값을 얻으면 그 값으로 다시 한 번 업데이트한다.

• Time Elapse Update: 트랜지션 모델에 따라 파티클 값을 업데이트한다. 상태 $t_i$의 파티클에 대해서 $Pr(T_{i+1}|t_i)$ 분포에 따라 업데이트되는 값을 샘플링한다.

• Observation Update: 관측값을 업데이트할 때 센서 모델 $Pr(F_i|T_i)$을 통해 관측된 에디번스와 각 파티클의 상태를 통해 파티클 값의 가중치를 구할 수 있다. 상태 $t_i$의 파티클을 센서 $f_i$가 읽으면 $Pr(f_i|t_i)$ 가중치를 준다. (조건부 확률을 참고)

관측값 업데이트는 다음과 같은 순서다.
1. 모든 파티클 가중치를 계산한다.
2. 각 상태의 총 가중치를 계산한다.
3. 모든 상태의 가중치 총합이 0이면 모든 파티클을 한 번 더 초기화한다.
4. 0이 아니라면 모든 상태에 대해 가중치 총합을 정규화하고 파티클 리스트를 확률 분포에서 다시 샘플링한다.

이 알고리즘을 통해 구한 확률이 과연 참값과 어느 정도로 일치하는지 알아보자.

15에 근접한 수로 바뀔 확률이 $80$%, 균등한 수로 바뀔 확률이 $20$%라고 하자. 파티클 리스트는 $[15,12,12,10,18,14,12,11,11,10]$다. 처음 상태가 $15$라면 $0.8$과 나머지 $0.2$를 분배한 확률이 곧 분포다.

$T_i$	14	15	16
$B(T_i)$	0.1	0.8	0.1

전체 도메인 $r$의 크기를 1이라고 할 때 이 분포에 따르자면 $T_{i+1}=14:\, 0\leq r<0.1$, $T_{i+1}=15:\, 0.1\leq r<0.9$, $T_{i+1}=16:\, 0.9\leq r<1$이다.

랜덤 함수를 통해 0 이상 1 미만 값을 추출한 뒤 각 값의 트랜지션 모델 $T_{i+1}$로 사용하자. $[15,12,12,10,18,14,12,11,11,10]$과 매칭되는 $r$ 값은 $[0.467,0.452,0.583,0.604,0.748,0.932,0.609,0.372,0.402,0.026]$이라고 하자. 따라서 $[15,13,13,11,17,15,13,12,12,10]$가 나온다. $r$ 값의 범위에 따라 현재 수를 유지할지, 1씩 가감할지 정하는 데 주의하자.

이렇게 time elapse update가 끝난 뒤 파티클 리스트를 통해 빌리프 확률 분포 $B(T_{i+1})$을 구해보자.

$T_i$	10	11	12	13	14	15	16	17	18	19	20
$B(T_i+1)$	0.1	0.1	0.2	0.3	0	0.2	0	0.1	0	0	0

두 번째 업데이트, 즉 관측값 기반 업데이트를 해보자. 센서 모델 $Pr(F_i|T_i)$는 예측이 맞는다면 $0.8$, 다른 경우 $0.02$로 균등한 확률 분포라 가정하자.

$Particle$	p_1	p_2	p_3	p_4	p_5	p_6	p_7	p_8	p_9	p_10
$State$	15	13	13	11	17	15	13	12	12	10
$Weight$	0.02	0.8	0.8	0.02	0.02	0.02	0.8	0.02	0.02	0.02

값이 같은 상태별로 가중치 합을 구하자.

$State$	10	11	12	13	15	17
$Weight$	0.02	0.02	0.04	2.4	0.04	0.02

가중치 총합이 $2.54$다. 각 상태별 가중치를 총합으로 나누는 정규화를 실행하자.

$State$	10	11	12	13	15	17
$Weight$	0.02	0.02	0.04	2.4	0.04	0.02
$Normalized\,\,\,\,Weight$	0.0079	0.0079	0.0157	0.9449	0.0157	0.0079

이 가중치를 통해 다시 한 번 샘플링에 사용할 0 이상 1 미만 $r$ 값을 추출하자. $[0.315,0.829,0.304,0.368,0.459,0.891,0.282,0.980,0.898,0.341]$라 한다면, $[13,13,13,13,13,13,13,15,13,13]$이 뜬다. $13$이 9번 $15$가 1번 나왔기 때문에 각 확률 분포는 $0.9$, $0.1$이다. $B(T_{i+1})$ 센서 모델의 정확도가 높아졌다.

MMs, HMMs 각 모델에서 사용한 포워드 알고리즘 기법의 연산 비용을 낮추기 위해 샘플링 기법을 사용한다. 이러한 방법은 딥러닝 훈련 횟수를 학습률을 통해 제한하거나 에포크 등을 통해 조절하는 의도와 닿아 있다. 정확한 근사가 거의 불가능 또한 불가능에 가까울만큼 연산 비용이 크기 때문에 확률적으로 거의 비슷한 값을 근사하는 샘플링을 통해 연산 비용을 현저히 감소시킬 수 있다.