1. Basic Mathematics of RL

1. 강화학습 수학

리스트업 된 내용을 가볍게 살펴보고 잘 모르는 내용은 깊게 이해하기

한 번씩 살펴본 후 pdf 자료 참고하여 복습

01, 02 알고리즘을 이해하기 위한 수학 내용

1. 확률과 랜덤 변수

확률: 어떤 사건이 일어날 가능성

랜덤 변수: 확률 적인 사건의 결과를 수치로 표현한 변수

• 이산 랜덤 변수(Discrete Random Variable)

  $$\begin{gathered} P(X=x) \\ E(X)=\sum _{x}x\cdot P(X=x) \\ V(X)=E\{(X-E(X){)}^2\} \end{gathered}$$

• 연속 랜덤 변수(Continuous Random Variable)

  $$\begin{gathered} f(x) \\ E(X)={\int }_{-\infty }^{\infty }x\cdot f(x)dx \\ V(X)={\int }_{-\infty }^{\infty }(x-E(X){)}^2\cdot f(x)dx \end{gathered}$$

2. 기댓값과 분산

기댓값(Expectation): 랜덤 변수의 평균적인 값

분산(Variance): 랜덤 변수가 기댓값으로부터 얼마나 떨어져 있는지 측정하는 지표

3. 랜덤 벡터

랜덤 벡터: 여러 개의 랜덤 변수를 벡터 형태로 표현한 것

$$\text{X}=[X_1,X_2,...,X_n]$$

4. 가우시안 분포

가우시안 분포: 평균과 표준편차로 정의할 수 있는 연속 확률 분표(정규 분포)

5. 랜덤 시퀀스

랜덤 시퀀스: 시간에 따라 변하는 랜덤 변수의 순열

$$\{X_t{\}}_{t=1}^{\infty }$$

6. 선형 확률 차분방정식(Linear Stochastic Differential Equation)

$$d{X}_t=a(X_t,t)dt+b(X_t,t)W_t$$

시스템이 평균적으로 어떻게 움직이는 지 나타내는 Drift Term $a(X_t,t)$ 과 시스템의 랜덤성을 나타내는 Diffusion Term $b(X_t,t)$, Wiener Process $d{W}_t$ 를 통해 시스템의 동적인 행동을 모델링 함.

• Wiener Process(or Brownian motion)

  확률 과정의 한 종류

  • $W_o=0$ 으로 초기값은 0이다.
  • 독립 증분: 시간 간격이 다르면 증분들이 독립적이다.
  • Stationarity: 증분의 분포는 시간에 따라 변하지 않는다.
  • 연속성: 모든 시간 $t$ 에 대해 $W_t$ 가 연속이다.

• 미소 증분(Infinitesimal Increment)

  따라서 미소 증분 $d{W}_t$ 는 평균이 0이고, 분산이 $dt$ 이다.

이 둘의 곱은 시스템의 랜덤성을 의미한다.

7. 중요 샘플링

$$E_p(f(X))\approx \frac{1}{N}\sum _{i=1}^N\frac{p(x_i)}{q(x_i)}f(x_i)$$

샘플링이 어려운 분포 $p(x)$ 대신 비교적 샘플링이 쉬운 $q(x)$ 를 통해 $p(x)$ 의 기댓값을 추정하는 방법

8. 엔트로피: 정보의 불확실성을 측정하는 척도. 높은 엔트로피는 높은 불확실성을 의미한다.

9. KL 발산(Kullback-Leibler Divergence)

$$\begin{gathered} D_{KL}(P\Vert Q)=\sum _{x\in X}P(x)\log \frac{P(x)}{Q(x)} \\ {D}_{KL}(P\Vert Q)={\int }_{-\infty }^{\infty }p(x)\log \frac{p(x)}{q(x)}dx \end{gathered}$$

두 확률 분포 P와 Q 사이의 차이를 측정하는 척도이다. 예를 들어 데이터의 확률 분포와와 모델이 예측한 확률 분포 간의 거리를 측정할 때 사용될 수 있다.

이 값이 작을 수록 두 분포가 유사하다고 할 수 있다.

10. 경사하강법(Gradient Descent)

목적 함수를 최소화하는 $\theta$ 를 찾는 알고리즘 중 하나

11. 손실함수의 확률론적 해석

Loss Function은 모델의 파라미터를 추정하는 Maximum Likelihood Estimation(MLE)의 일환

---

수학으로 풀어보는 강화학습 원리와 알고리즘 1장

1.1.5 조건부 확률함수

$$P\{A|B\}=P\{A,B\}/P\{B\}$$

A와 B의 곱사건 확률과 B만 발생할 확률의 비

전체 표본공간 S의 확률은 1이므로 $P\{A|S\}=P\{A\}$ 이다. 그러므로 전체 표본공간이 사건 B로 축소된 것으로 생각할 수 도 있다.

랜덤 변수 Y가 y로 주어진 X의 조건부 확률밀도함수(conditional probability density function) $p_{X|Y}(x|y)$ 는 아래와 같이 표현된다.

$$P\{X\le x|Y=y\}={\int }_{-\infty }^x{p}_{X|Y}(u|y)du$$

이때 $Y=y$를 $Y$가 미소구간 $(y,y+dy]$에 속한다고 해석한다.

그러면 chain rule을 유도할 수 있다.

• 누적 확률 밀도함수(cdf; cumulative probability density function)

주로 F(x)와 같은 기호로 표현한다. 이때 변수 x는 범위의 끝을 뜻하며 범위의 시작은 $-\infty$ 을 의미한다.

$F(x)=P(X<x)$ 인 것이다.

• 확률 밀도함수(probability density function)

이러한 누적 확률 밀도함수를 미분한 도함수가 확률 밀도함수 이다. 누적 확률 밀도함수는 구간 마다의 확률을 알기 힘들기 때문에 어떤 값이 더 자주나온다 등의 정보를 위해 확률 밀도함수를 사용한다.

주로 f(x)의 기호를 사용한다.

$f(x)=\frac{dF(x)}{dx}$ 또는 $F(x)={\int }_{-\infty }^{x}f(u)du$ 와 같다.

Reference: 확률분포함수와 확률밀도함수의 의미

1.1.8 Bayes’ theorem

전확률(total probability) 정리를 확률밀도함수로 표현하면 아래와 같다.

$$p_x(x)={\int }_{-\infty }^{\infty }{p}_{XY}(x,y)dy={\int }_{-\infty }^{\infty }{p}_{X|Y}(x|y)p_Y(y)dy$$

이 때, $P(X,Y)=0$ 이다. dy에 대하여 모든 범위를 적분하면 X와 Y의 교집합인 사건의 확률은 0이므로 X의 확률이 된다.

조건부 확률을 전확률 정리에 대입하면 아래와 같다.

$$P\{B_i|A\}=\frac{P\{A|B_i\}P\{B_i\}}{\sum _{j=1}^{n}P\{A|B_i\}P\{B_i\}}$$

분모 $\sum _{j=1}^{n}P\{A|B_i\}P\{B_i\}$ 는 $P\{A\}$ 와 같다.

위 식을 베이즈 정리(Bayes’ theorem)이라고 한다.

1.1.9 샘플링

각 샘플이 어떤 확률적 특성을 갖는 모집단에서 독립적이고 공평하게 추출된 경우 추출된 샘플을 독립동일분포(iid, independent and identically distributed) 샘플이라고 한다.

1.5 랜덤 시퀀스

랜덤 변수 $X\equiv X(e)$ 는 확률 실험의 결과에 실숫값을 대응시키는 함수로 정의했다.

discrete-time random process or random sequence는 확률 실험의 결과에 시간 함수를 대응시키는 함수로 정의한다. ⇒ $X_t\equiv X_t(e)$

랜덤 시퀀스는 시간에 따라 변하는 확률 실험을 모델링하는데 이용된다.(e.g. 주식 가격, 센서의 노이즈 등)

샘플 함수 ${\text{x}}_t$ 는 time step t에서의 state를 의미하며, deterministic & ensemble 하다.

continuous time에서는 random process라고 한다.

$$X(t)\equiv X(t,e)=[X_1(t,e),...,X_n(t,e){]}^T$$

1.5.3 Markov sequence(or process)

현재의 확률 정보가 주어진 조건 하에서, 미래와 과거는 무관한(혹은 조건부 독립인) 랜덤 시퀀스(또는 프로세스)

$$p_{x_t}(x_{t+1}|x_t,x_{t-1},...,x_0)=p_{x_t}(x_{t+1}|x_t)$$

즉, 과거의 모든 확률 정보는 현재의 확률 정보에 포함되어 있다는 의미이다.

1.10 Kullback-Leibler divergence

상대 엔트로피(relative entropy)라고도 한다.

거리의 척도 특성 4가지 중 3가지 만을 만족하고, 대칭성을 만족하지 못해 semi distance metric이라고 한다.

$$\begin{array}{rl}KL(p\Vert q)& =H(p,q)-H(p)\\ & \ne H(q,p)-H(q)=KL(q\Vert p)\\ KL(p\Vert q)& \ne KL(q\Vert p)\end{array}$$

이 때 $H(p,q)$ 는 교차 엔트로피(cross entropy)라고 하며 확률밀도함수 q(x)의 정보량을 p(x)의 관점에서 기댓값으로 표현한 것이다.

$$\begin{gathered} H(p,q)={\text{E}}_{x\sim p(x)}[-\log q(x)] \\ =-{\int }_{x}p(x)\log q(x)dx \end{gathered}$$

Reference: KL-divergence

1.12 벡터와 행렬의 미분

$\text{x}=[x_1,x_2,\dots x_n{]}^T\in R^n$ 인 벡터이고, A는 $\in R^{m\times n}$ 인 행렬이고 스칼라 함수 $f(x)=x^{T}Ax$ 로 주어졌을 때

$${▽}_{\text{x}}f(\text{x})={▽}_{\text{x}}{\text{x}}^{T}A\text{x}=(A+A^T)\text{x}$$

벡터 함수 $g(x)=Ax$ 일 때 미분하면 ${▽}_{\text{x}}A\text{x}=A^T$ 이다.

${▽}_{\text{x}}^{2}f(\text{x})$ 를 Hessian matrix라고 한다. (symmetric)

1.14 경사하강법

$${\theta }^{\ast }=\arg \underset{\theta }{\min }L(\theta )$$

학습 데이터를 한 번에 일괄적으로 처리해 경사하강법을 적용하는 방법을 batch gradient descent라고 한다.

이러한 방식은 학습 데이터가 많은 경우 연산량이 매우 크므로, 이를 개선하기 위해 SGD(Stochastic Gradient Descent)가 고안되었다.

무작위로 추출된 학습 데이터 한 개를 이용해 $\theta$ 를 업데이트 한다.

업데이트 속도가 매우 빠른 대신 노이즈가 심하다.

mini-batch는 위 2개의 방법의 절충안으로 b개의 학습 데이터를 무작위로 추출해 업데이트 한다.

1.15 경사하강법의 개선

Gradient descent의 단점은 step size $\alpha$ 를 적절히 정해야 하고, global optimum이 보장될 수 없다.(saddle point)

이를 개선하기 위해 GD w/ momentum, RMSprop, Adam 등이 있다.

• 모멘텀

파라미터를 바로 이동시키지 않고, 기존에 이동하던 방향으로의 움직임을 일정 부분 유지하면서(momentum) 그래디언트가 가리키는 방향의 반대 방향을 적당히 혼합해 이동하는 것이다.

$$\begin{array}{rl}\text{while}\{& \\ v& \leftarrow \beta v+{▽}_{\theta }L(\theta )\\ \theta & \leftarrow \theta -\alpha v\\ \}& \end{array}$$

이 때의 $\beta$ 를 모멘텀 계수라고 한다. 그래디언트의 이동 구간을 일부 취해 사용하므로, 관성 방향은 그래디언트를 일정 시간동안 누적시킨 평균으로 해석할 수 있다.

• RMSprop

각 파라미터 $\theta$ 의 구성 요소마다 스텝 사이즈 $\alpha$를 다르게 주는 것이다. 크게 변화한 $\theta$ 는 $\alpha$ 를 작게 하고, 그렇지 않으면 크게 하여 최소점으로 빠르게 이동시키겠다는 것이다.

많이 변화했는 지의 판단 기준은 그래디언트 제곱 크기의 이동 구간 평균값으로 판단한다.

$$\begin{array}{rl}\text{while}\{& \\ S_j& \leftarrow \beta S_j+(1-\beta )({▽}_{\theta }L(\theta ){)}^2\\ {\theta }_j& \leftarrow {\theta }_j-\frac{\alpha }{\sqrt{S_j+ϵ}}{▽}_{{\theta }_j}L({\theta }_j)\\ \}& \end{array}$$

• Adam (Adaptive moment estimation)

Adam은 모멘텀과 RMSprop을 합친 방법이다.

각 timestep k에 대해 그래디언트의 이동 구간 평균을 구해 $v_k$ 를 업데이트 하고, RMSprop 처럼 파라미터의 요소별 그래디언트 제곱 크기의 이동 구간 평균을 구해 $S_k$ 를 업데이트 한다.

그리고 $k=0$ 일때의 편향을 보정하여 ${\theta }_{k+1}$ 를 업데이트 한다.

Original Link : 연세드론 4기 RL 스터디