[ML] Robbins-Monro algorithm

Pattern Recognition and Machine Learning의 2.3.5 Sequential estimation 부분참조.

데이터가 순차적으로 주어지는 경우 ML을 통해 \theta값을 추정할 때 사용된다; 

N-1번째 주어진 데이터로 모델 \theta를 추정했는데 새로운 데이터 N번째 data 포인트가 들어와서 새로운 \theta를 추정하는 알고리즘. 

여기서 z는 새로운 N번째 데이터 포인트 때문에 변화하는 \theta값을 의미하고 a_{N-1}은 learning rate를 가르키게 된다. 

그리고 a_n은 다음 세가지 조건을 만족해야 한다. 

Convergence를 위한 조건인듯 보인다. 

사실 위의 식은 gradient descent model의 수식과 같다. 

a_N은 Learning rate가 되고 새로운 데이터 포인트가 들어올 수록 배우는 것은 수렴해야 하는데 전체 배우는 양은 유한해야 함으로 위의 조건이 붙게 되는것이다.