optimization22 Optimization 심화 : Random process (4, Stochastic process) 모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다. 앞으로 Random process에서 가장 중요하고 유명한 두 개념인 'Martingale process'와 'Markov process'를 다루고자 한다. 오늘은 기본적인 정의와 개념에 대해서 살펴보도록 하자. 같은 Probability space $(\Omega, \mathcal{F}, \mathbb{P})$와 Borel $\sigma$-algebra를 장착한 Topological space $(S, \mathcal{B})$ 에서 정의된 Random variable들의 집합 Stochastic process $\{X_t : t \in T \}$를 고려해보자. 이때 Index set인 $T$가 discrete.. 2023. 12. 31. Optimization 심화 : Random process (3, Stochastic process) 모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다. 오늘은 수리통계학적인 개념들에 대해 복습하고자 한다. 이는 앞으로 다양한 Random process에 대해 다뤄보는 데 있어 기본적인 밑바탕이 될 것이다. 수리통계학을 충분히 학습한 사람은 이 내용이 크게 어렵지 않으리라 생각한다. 먼저 확률수렴에 대한 정의이다. Random variable sequence $\{X_n\}$이 모든 $\epsilon > 0$에 대해 다음과 같으면 $X$에 'converge in probability'라 한다. $\lim_{n \rightarrow \infty} \mathbb{P}[|X_n - X| \ge \epsilon] = 0$ 다음은 'weak version' 의 Law o.. 2023. 12. 23. Optimization 심화 : Noise에 대하여 (1) 모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다. 오늘부턴 stochastic gradient의 중요한 특징 중 하나인 'Noise'에 대해서 살펴보고자 한다. 'Deterministic' gradient descent는 모든 data를 활용해서 계산된 loss와 gradient이기 때문에 우리는 이를 효율적으로 대체하기 위해 매 iteration마다 data의 일부를 (random) sampling해서 'mini-batch'를 활용하여 gradient를 계산한다. 당연히 이는 가장 가파른 하강방향 (Deterministic 'Negative' gradient)과 차이가 있을 수밖에 없고 이 차이를 만드는 요소가 noise이다. noise는 다음과 같은 ter.. 2023. 11. 21. Optimization 심화: Iterative Complexity 모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다. 지난 번 글에서는 convergence type 3가지를 소개하였다. 첫 번째는 in-Expectation bound, 두 번째는 with a probability bound, 세 번째는 Almost sure bound이다. 각각 의미가 있지만, 이들 사이에는 중요한 차이점이 존재한다. with a probability bound는 구체적으로 low probability와 high probability로 나뉘어져 있고, in-Expectation bound는 concentration inequality (e.g. Markov inequality) 를 사용하면 low probability bound로 쉽게 바꿀 .. 2023. 11. 13. Deep dive into Optimization : Types of Convergence 모바일 앱 환경에서는 latex 수식이 깨져 나타나므로 가급적 웹 환경에서 봐주시길 바랍니다. 다음과 같이 최적화 문제를 정의하자. $\min_x f(x)$ Stochastic gradient를 쓰는 First-order optimization algorithms를 생각해보자. 그러면 우리는 자연스레 다음과 같은 질문을 던지게 될 것이다. 이 알고리즘들을 매 step (iteration)마다 반복적으로 (=iterative) 사용하여 $f(x)$를 최소화하면, 우리는 정말로 위의 최적화 문제를 풀 수 있는가? 즉, $f(x)$의 global minima를 찾을 수 있는가? 그리고 두 번째로 궁금한 것은 과연 그렇다면 얼마만큼의 비용이 필요한가? 여기서의 비용 (cost)란 대다수의 경우에 gradient.. 2023. 11. 5. 이전 1 2 3 4 5 다음
