Optimization 심화 : Random process 1(Stochastic process)

 

 

모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다.

 

 

그동안 Optimization 주제로 다양한 글들을 올려오면서 stochastic optimization algorithm를 이야기할 때 다음과 같은 언급을 많이 하였다. 

"Parameter sequence $\{ x_t \}$가 Stochastic process이다." 

 

이번 글에서는 Stochastic process에 대해 기본적인 개념을 짚어보고자 한다.

이 분야는 Probability theory 중 매우 중요한 분야이며 쉽지 않은 분야 중 하나이다.

이번 시리즈의 글들은 위 분야를 약간 맛보기한다 라고 생각하면 된다.

 

"Stochastic process"는 Random variable sequence로 정의되는데 이때 index 역할을 하는 것이 일반적으로 time step이다.

 

우선 Random variable을 정의하기 위해 Probability space부터 먼저 이야기하고 가자.

Probability space는 $(\Omega, \mathcal{F}, \mathbb{P})$로 표현되며, $\Omega$는 Sample space, $\mathcal{F}$는 $\sigma$-algebra, $\mathbb{P}$는 probability measure이다.

 

Sample space는 모든 가능한 결과의 집합이다.

$\sigma$-algebra는 $\Omega$의 부분집합의 모음 (collection) 이자 관심 있는 사건 결과의 집합이며 다음의 조건을 만족한다.

1. 만약 $A \in \mathcal{F}$이면, $A^{c}$ \in \mathcal{F}$이다.

2. 'Countable' union에 대해서 닫혀있다. 즉, 모든 $i$에 대해 $A_i \in \mathcal{F}$이면, $\Cup_{i} A_i \in \mathcal{F}$이다.

$\mathbb{P}$는 $\mathcal{F} \rightarrow [0, 1]$로서 probability measure이다.

 

$(\Omega, \mathcal{F})$는 measurable space인데, 이 공간의 measure를 위한 도구로 우리는 확률을 사용한다.

measure ($\mu : \mathcal{F} \rightarrow \mathbb{R}$) 란 다음의 조건을 만족하는 'set function'을 의미한다.

1. $\mu(A) \ge \mu (\emptyset) = 0$ for all $A \in \mathcal{F}$.

2. 만약 $A_i \in \mathcal{F}$이 서로소 집합의 수열이라면, $\mu(\cup_{i} A_i) = \sum_i \mu(A_i)$이다.

2번 성질을 우리는 'countable additivity'라고 한다.

 

여기서 추가적으로 $\mu(\Omega) = 1$을 만족하면 우린 $\mu$를 Probability measure라고 부른다.

그리고 Probability measure는 주로 $\mathbb{P}$로 표기한다.

 

그러면 Random variable은 어떻게 정의될까?

(Informally) $\Omega$에서 $\mathbb{R}$로 mapping해주는 함수로 정의된다.

구체적인 예시를 들어본 다음에, 엄밀한 정의를 살펴보자.

 

(공평한) 동전을 2번 던지는 행위를 생각해보자. 이때 나올 수 있는 Sample space는 다음과 같다.

$\Omega = \{HH, HT, TH, TT \}$.

$w \in \Omega$에 대하여 $X(w)$를 H의 수라고 정의하자. 즉, 동전 앞면이 나온 횟수라고 정의하자. 그렇다면, 

$X(HH) = 2, X(HT) = X(TH) = 1, X(TT) = 0$으로 정의된다.

 

자, 어떤 도박꾼이 H가 나오면 2달러를 벌고, T가 나오면 2달러를 잃는 도박을 시행했다고 생각해보자.

그렇다면 그의 소득  $W$는 다음과 같이 정의된다.

$W(HH) = 4, W(HT) = W(TH) = 0, W(TT) = -2$.

 

동전이 던져지기 전까지는 우리는 이 결과에 불확실성을 가지고 있지만, 동전이 던져진 이후에는 결과를 알게 된다.
(결정된다.)

즉, Random variable $X$가 어떤 값을 갖는지 알게 되는 것이고 도박꾼이 얼마를 벌었는지 (또는 잃었는지) 알게된다.

확률과 관련된 다양한 영역에서 우리는 이 Random variable이 어떠한 분포를 갖는지 알고 싶고, 그것을 함수 $F(x)$라고 표현하자.

즉, $F(x) : \mathbb{R} \rightarrow \mathbb{R}$은 $X$가 $x$를 넘지 않을 확률이다.

엄밀하게 정의하면

$F(x) := \mathbb{P}(A(x))$이고 이때 $A(X) \subseteq \Omega$이며 $A(x) = \{ w \in \Omega : X(w) \le x \}$이다.

이때 $\mathbb{P}$는 앞서 정의한 Probability measure이며 이는 당연히 $A(x)$가 $\sigma$-algebra $\mathcal{F}$에 포함되어야만 'measurable'하다.

 

이제 Random variable에 대한 정의를 내리자.

 

Random variable은 함수 $X : \Omega \rightarrow \mathbb{R}$이며, 각각의 $x \in \mathbb{R}$에 대하여 $\{w \in \Omega : X(w) \le x\} \in \mathcal{F}$를 만족하는 함수이다.

그리고 이러한 함수를 우리는 '$\mathcal{F}$-measurable'하다고 표현한다.

 

여기서 한 단계 더 나아가 Random variable $X$에 대하여 $F(x) : \mathbb{R} \rightarrow [0, 1]  = \mathbb{P}(X \le x)$ 인 함수를 분포 함수 (Distribution function)이라고 정의한다.

 

이러한 Random variable의 sequence는 다음과 같이 표현된다.

 

$\{ X(t) : t \in T \}$

 

여기서 $t \in T$는 'index set'을 의미하며 대다수의 Random process 문제에서는 주로 Time step을 의미한다.

그리고 우리가 관심 있는 Stochastic optimization에서도 Time step을 의미한다.

 

마지막으로 'Filtration'에 대해서 정의하자.

Filtration은 $\sigma$-algebra의 집합으로서 $(\mathcal{F}_t)_{t \ge 0}$로 표기한다.

이것의 가장 중요한 특징은 'non-decrasing' set이라는 것인데 다음과 같은 성질을 만족한다.

$\mathcal{F}_s \subseteq \mathcal{F}_t$ for all $s \le t$.

이는 결국 시간이 지남에 따라, (일반적으로 index set $t$는 time step을 의미하므로) Random variable에 대한 정보가 더 증가함을 의미한다. (최소한 줄어들지는 않음을 의미한다)

 

Stochastic Process $\{ X(t) \}$가 'adapted to a filtration $(\mathcal{F}_t)$'하다는 표현이 자주 등장하는데 (또는, $X_t$가 $\mathcal{F}_t$-measurable하다') 이는 $X_t$의 값이 time step $t$까지의 정보가 주어져있으면 관찰 가능하다는 의미이다. 

 

자, 그러면 이제 다음 글부터 본격적으로 Stochastic Process의 중요한 개념들에 대해 짚어보도록 하자.