Newton-Raphson method 대신 사용하는 방식으로, 주어진 함수들에 대한 로컬 maxima 또는 minima 를 찾는 방법이다.
뉴튼 방법에서 사용하는 Jacobian matrix 이나 Hessian 을 계산하는게 불가능하거나 너무 비용이 많이 드는 경우 사용한다.
1 min read
Newton-Raphson method 대신 사용하는 방식으로, 주어진 함수들에 대한 로컬 maxima 또는 minima 를 찾는 방법이다.
뉴튼 방법에서 사용하는 Jacobian matrix 이나 Hessian 을 계산하는게 불가능하거나 너무 비용이 많이 드는 경우 사용한다.
여기서 H⁻¹ 를 구하는 것이 계산 비용 상승의 주된 원인인데, 이를 근사하는 방향으로 계산 비용을 줄인다. 즉, quasi-Newton method 방식을 적용하여 low-rank update 를 통해 matrix Mt 에 대한 inverse 를 approximate 한다.
Newton’s method 라고 불리기도 하며, 실수 함수의 approximate 한 해를 빠르게 찾는 방법이다.
BFGS 알고리즘은 Newton-Raphson method 의 장점을 취하면서 계산 비용을 줄인 방법이다. 이런 관점에서 BFGS 는 conjugate gradients 방식과 비슷하다. 뉴턴 방법의 업데이트는 아래와 같다.
Suppose f:\mathbb{R}^{n}\rightarrow\mathbb{R} is a function taking as input a vector \mathbf{x}\in\mathbb{R}^{n} and outputting a scalar f(\mathbf{x})\in\mathbb{R}.
tight lowerbound LL(\boldsymbol{\theta}) , Q\left(\boldsymbol{\theta},\boldsymbol{\theta}^{t}\right)\leq LL(\boldsymbol{\theta})...
최적화 문제 (Optimization problems) 란 여러개의 선택가능한 후보 중에서 최적의 해 (Optimal value) 또는 최적의 해에 근접한 값을 찾는 문제를 일컫는다.
Method of finding a local maximum subject to constraints.
Convex ? Concave f(x) is convex, iff f^{\prime\prime}(x)\geqslant0,\forall\mathrm{x}\in R f(x) is strictly convex, iff f^{\prime\prime}(x)>0,\forall\mathrm{x}\in R f(x) is...
variational inference 와 동일한 아이디어를 채택한 방식이다.
Jensen’s Inequality For a random variable x, if f(x) is convec (refer. convex function), then E[f(x)]>=f(E[x]).
ADMM 은 원래의 convex 최적화 문제보다 최적화가 쉬운 부분문제로 분할하고 이를 취합함으로써 복잡한 원 문제를 해결하는 방식의 근사알고리즘이다.