SGD / EKF / PF algorithm

● SGD(Stochastic gradient descent)

• 배치 사이즈가 1(즉, 하나의 예)인 미니배치에서 gradient를 계산하는 것
• gradient를 평가하기 위해 무작위로 선택된 샘플을 사용
• 반복이 충분하면 SGD는 효과 있지만 noise가 심함

• first-order gradient 정보만 이용

•  second-order gradient 기반 기술보다 수렴이 느리고 조건이 좋지 않은 문제에서 성능이 저하된다

• 이를 완화시키기 위해 second-order gradient를 고려한다

• 수렴률(convergence rate)이 빠르고 conditioned problem에 대해 더 강력하다

• Hessian Matrix라는 2차 편미분 행렬을 계산한 후 역행렬을 구해야 한다.

• SGD algorithm 기반의 online update 

•  ‘RTRL algorithm’ in the neural network iterature

 

 

● PF(Particle Filter)

• 보통 베이즈 모델을 추정하기 위해 사용된다
• 시뮬레이션에 기반을 둔 예측기술의 하나로 계속적인 몬테카를로 방법이라고 한다. 
  • 몬테카를로 방법: 난수를 이용하여 함수의 값을 확률적으로 계산하는 알고리즘
• PF의 목적은 Gaussian이 아닌 임의의 분포를 다루기 위한 접근 방식
• http://jinyongjeong.github.io/2017/02/22/lec11_Particle_filter/
• 필터링은 어떤 특정 시간에 잠재변수의 분포를 결정하되, 관측 값은 그 시간 까지만 주어진다
• 목적: 연속적으로 들어오는 정보를 오차가 존재하는 관측값만을 가지고 정보를 예측하는 데에 있다.
• 원리
  • 시스템에 적절하게 제안된 확률분포로 임의로 생성된 입력을 여럿 가하여보고 그것들을 종합하여 시스템의 정보를 추측
• 작동 과정
  1. Random sample 생성: 맵의 군데 군데 입자들을 뿌린다. (입자들의 정보 - 좌표 값) 
  2. Sampling 과정: 시스템 모델에 random sample들을 통과 시켜 새로운 위치로 입자들을 이동 시킨다
  3. Importance sampling 과정: 각 입자들의 가중치는 측정 값의 확률에 비례한다. gloabl localization문제에서 측정한다는 의미는 Sonar sensor이나 Laser sensor를 이용하여 공간의 형태를 측정하는 것이다. 이런 공간의 형태가 전체 맵에서 존재할 확률이 가장 높은 곳에 weight을 더 주게 된다.
  4. 입자의 위치와 그 위치에서의 가중치(입자의 가중치)를 알게 되었다
  5. Resampling 과정: 이렇게 가중치가 생긴 sample들을 이제 다시 가중치가 일정한 입자들로 바꾸기 위해서 resampling 과정을 거친다. 
  6. 반복
• Resampling:
  • 가중치가 큰 입자들은 근처에서 잘게 쪼개어 근처에 입자들이 많이 분포되도록 하고, 가중치가 작은 입자들은 제거한다.
• Global localization:
  • 초기 위치를 알고 그 근처의 정보만으로 위치를 추적

 

● KF(Kalman Filter)

• noise가 포함되어 있는 측정치를 바탕으로 선형 역학계의 상태를 추정하는 재귀 필터이다.
• 과거에 수행한 측정값을 바탕으로 현재의 상태 변수의 결합분포를 추정한다.
• 알고리즘
  • 예측과 업데이트 두 단계로 이루어진다.
  • 예측 단계 - 현재 상태 변수의 값과 정확도를 예측 
  • 업데이트 단계 - (현재 상태 변수의 값이 실제로 측정된 이후) 이전에 추정한 상태 변수를 기반으로 예측한 측정치와 실제 측정치의 차이를 반영해 현재의 상태 변수를 업데이트한다.
• 적용 분야
  • 물체의 측정값에 확률적인 오차가 포함되고, 또한 물체의 특정 시점에서의 상태가 이전 시점의 상태와 선형적인 관계를 가지고 있는 경우 적용 가능하다.
• 동적 시스템 모델
  • 이산 시간 선형 동적 시스템을 기반으로 동작하며, 각 시간에서의 상태 벡터는 이전 시간의 상태 벡터를 통해서 결정된다는 '마르코프 연쇄'를 가정
  •  

 

 

 

● EKF(Extended Kalman Filter)

- 비선형 시스템을 기반으로 동작

- 선형성 가정을 완화시켜, 더 일반적인 시스템에 대해서도 사용이 가능하도록 확장했다.

- 비선형 상태 추정에 주로 사용되고 있다

$x_{k}$: 상태 백터, $u_{k}$: 사용자 입력, $w_{k}$: 공분산행렬$Q_{k}$을 가지는 다변수 정규분포 noise 변수, $w_{k}$: 분산행렬$R_{k}$을 가지는 다변수 정규분포 noise 변수

 

 

참고 자료:

http://jinyongjeong.github.io/2017/02/14/lec03_kalman_filter_and_EKF/

 

칼만 필터 위키 백과 설명(한국어) - https://ko.wikipedia.org/wiki/%EC%B9%BC%EB%A7%8C_%ED%95%84%ED%84%B0

PF - https://m.blog.naver.com/PostView.nhn?blogId=sw4r&logNo=110148331165&proxyReferer=https%3A%2F%2Fwww.google.com%2F