오늘 소개할 논문은 새로운 momentum (타성) 방법을 제시한다. 우선 momentum에 간략하게 설명한 후 aggregated momentum (집계된 타성)을 소개하겠다. 지금까지도 machine learning models을 training하는데 gradient descent with momentum을 널리 사용한다. 이유는 momentum이 낮은 곡률 방향 (low curvature direction)을 minimize하는데 도움을 주기 때문이다. 가장 많이 사용되는 momentum 방법은 다음과 같다. 우선 함수 $f: \mathbb{R}^d \to \mathbb{R}$ 를 parameter $\boldsymbol{\theta}$ 에 관하여 minimize한다고 가정하겠다. 고전적인 momentum처음 parameter를 $\boldsymbol{\theta}_0$ 라 표기하였을때, update step은 다음과 같다.$\begin{align}\mathbf{v}_t &= \beta \mathbf{v}_{t-1} – \nabla_{\boldsymbol{\theta}} f (\boldsymbol{\theta}_{t-1}), \\\boldsymbol{\theta}_t &= …
Blog Posts
지금까지 machine learning이 발전하고, 유용히 쓰이는데 역전파 (backpropagation) 알고리즘은 큰 역활을 했다. Data의 error를 통해 neural network의 neuron을 간편하게, 빠르게, 그리고 유동성 있게 업데이트하며 network를 train하는데 도음을 준다. 하지만 backpropagation의 문제점은 두뇌에서 일어나는 학습과 일치하지 않는 점이다. 물론, practice에서 backpropagation이 잘 작동하는걸 이미 수차레 관찰했지만, 두뇌에서 일어나는 learning과 다르다는 점에서 더 좋은 옵션이 존재할까라는 의문점을 생기게한다. 특히, Backpropagation은 error를 propagate하는데 있어 위 neuron의 weight를 알아야한다 (이 문제는 웨이트 운송 문제라고 부른다). 다르게 말해서, 밑에 뉴런들이 위 뉴런들의 정보를 정확히 알아야한다는것이다. …
Let $f: \mathbb{R}^n \to \mathbb{R}$ be continously differentiable and let $p_k$ be the descent direction at $x_k$. Assuming $f$ is bounded below along the ray $\{x_k + \alpha p_k | \alpha >0 \}$. Then, if $0 < c_1 < c_2 < 1$, there exists a step length $\alpha$ that satisfies wolfe conditions and strong wolfe conditions. 증명은 비교적 간단하다. $\phi(\alpha) = f(x_k + \alpha p_k)$, $\alpha >0$ 는 당연히 bounded below이다. 추가로 $0 < c_1 < 1$ 이기 때문에 $l(\alpha) …
주로 line search 방법에서는 descent direction $p_k$ 가 정해졌을때 다음과 같은 update를 한다.$$x_{k+1} = x_k + \alpha p_k$$여기서 $a_k$ 는 양의 실수이며 step length라고 부른다. 이 글에서는 step length를 정하는 방법을 알아보겠다. Step length를 정할때 보통 trade-off가 존재한다. 예를 들어, step length가 너무 작으면, optimum point를 도달하는데 시간이 너무 걸리고, step length가 크면 diverge할 가능성이 있다. 최선의 방법은 다음과 같은 univariate 함수에서 제일 작은 $\alpha$를 찾는 것이다:$$\phi(\alpha) = f(x_k + \alpha p_k)$$하지만 위에 식을 찾는데에는 시간이 오래걸리기 때문에, 보통 위 …
3 패스 전략 첫번째 (5분):– Title, abstract, introduction을 명확하게 읽기 (따라쓰기).– Section과 sub-section은 읽기.– 수식들을 빠르게 보기.– Conclusion 읽기.– Reference를 보고 읽었던 논문을 tick 하기. 첫번째 패스 후 다음을 알 수 있다:1. Category: 이것은 무슨 논문인가.2. Context: 어떤 문제를 풀 수 있는가.3. Correctness: Assumptions들은 맞는가.4. Contributions: 이 논문은 무엇을 contribute 하는가.5. Clarity: 읽기 편한가. 두번째 (1 시간):– Detail (e.g. 증명)을 제외한 부분을 읽기.– Comment를 달면서 논문을 읽기.– “Dominik Grusemann: note down terms you didn’t understand, or questions you may want …
Stochastic variance reduction, SVR, 은 다음과 같은 objective를 최적화하는데 도움을 줄 수 있다.$$\begin{align}f(w) = \frac{1}{n} \sum_{i=1}^{N} f_i (w)\end{align}$$여기서 $f_i$ 는 한 데이터 포인트의 loss이다. SVRG의 대표적인 방법은 SVRG, SAGA, 그리고 그 변형들이 있다. 보통 SVR은 variance를 control variate을 통하여 줄인다. 여기서 control variate은 전통적으로 MC에서 variance를 줄이는 용도로 많이 사용되어 왔다. Random variable $X$ 가 있다고 가정해보자. 평균 $\mathbb{E}[X] = \bar{X}$ 을 통해서 $X$ 를 측정할수도 있지만, control variate을 사용할수도 있다. 만약에 $Y$ 는 $X$ 와 correlated 한 variable이면, 즉 …
우선, 코시 수열의 정의에 따라서 수열 $x_k$ 는 다음을 만족한다.$$ \begin{align} \forall \epsilon > 0, \exists N > 0 s.t. n, m > N \Rightarrow |x_n – x_m| < \epsilon \end{align} $$따라서, $\epsilon_1 := 2^{-1}$ 일 때 다음을 만족하는 $N_1 > 0$ 이 존재한다: $ \forall n,m > 0 $$$\begin{align} n, m > N_1 \Rightarrow |x_n – x_m| < \epsilon_1 \end{align} $$비슷하게 $\epsilon_2 := 2^{-2}$ 로 두면 다음을 만족하는 $N_2 > 0$ 이 존재한다: $ \forall n,m > 0 $ …