Optimization (최적화) in Statistics

Optimization (최적화)

• Optimization은 어떠한 함수의 특정한 정의역 범위 내에서 최대값 (Maximum)과 최소값 (Minimum)을 찾는 문제를 말한다.
• 수학의 한 세부 분야에 속하며, 통계학 (Statistics), 기계학습 (Machine learning), 컴퓨터 공학 (Computer Science), 공학 (Engineering) 등 다양한 분야에서 폭넓게 활용된다.
• 최대값 (Maximum)과 최소값 (Minimum)을 얼마나 정확하게, 얼마나 효율적으로 (빠르게) 찾아낼 수 있는가에 대한 문제로서 일반적으로 수치를 iterative하게 계산해나가는 방식을 취한다.
• 통계에서도 대표적으로 Maximum likelihood estimation (MLE)이 최적화 문제에 해당된다.
  • 특히 generalized linear model, 예를 들어 logistic linear regression의 경우 MLE를 구하기 위해 iterative한 방법으로 최적화 문제를 풀어야한다.

Graph of a given by \(z = f(x, y) = −(x^2 + y^2) + 4\). The global maximum at \((x, y, z) = (0, 0, 4)\) is indicated by a blue dot.

---

Section 1. Optimization Problem

1.1 Optimization Problem의 수학적 정의.

• Optimization problem은 다음과 같이 수학적으로 정의할 수 있다 :
  • 어떠한 set \(A\)에서 정의되며 실수 값을 가지는 함수 \(f: A \rightarrow \mathbb{R}\)에 대하여
    1. (Minimization) 모든 \(\mathbf{x} \in A\)에 대해서 \(f(\mathbf{x}_0) \le f(\mathbf{x})\)가 성립하는 \(f(\mathbf{x}_0) \in A\)를 찾는 것.
    2. (Maximization) 모든 \(\mathbf{x} \in A\)에 대해서 \(f(\mathbf{x}_0) \ge f(\mathbf{x})\)가 성립하는 \(f(\mathbf{x}_0) \in A\)를 찾는 것.
• Minimization 하나만 고려해도 무방하다. 일반적으로 Optimization problem을 다룰 때는 minimization을 기준으로 서술함.
  • 왜냐하면 \(f(\mathbf{x})\)대신에 \(-f(\mathbf{x})\)를 고려하게 되면
  • \(f(\mathbf{x})\)를 maximization 시키는 것과 \(-f(\mathbf{x})\)를 minimization하는 것은 동일하기 때문
  • \(f(\mathbf{x}_0) \ge f(\mathbf{x})\) 과 \(-f(\mathbf{x}_0) \le -f(\mathbf{x})\) 은 동일일
• (예시 1)
  • (예시 1)에서는 \(f: A \rightarrow \mathbb{R}\)가 \[ f(\mathbf{x}) = -(x_1^2 + x_2^2) + 4 \] 의 형태이고,
  • \(A\)는 \(\mathbb{R}^2\), 즉 \((X_1,X_2)\)의 공간 전체가 된다.

constraint

• 가끔식 \(A\)에 어떠한 constraint, 즉 제한이 들어가는 경우가 생긴다.
  • 다시 말해서 어떠한 \(f\)의 minimization을 하는 솔루션 \(\mathbf{x}\)에 대해서 어떠한 제약 (constraint)를 부여하는 것.
• (예시 1)에서는 \(A=\mathbb{R}^2\)에 어떠한 제한이 들어가 있는 상황이 아니지만 다음과 같이 constraint를 넣을 수 있다.
• (예시 2) \[f(\mathbf{x}) = -(x_1^2 + x_2^2) + 4 \]에 대해서 \(x_1 \ge 1\)이고 \(x_2=1\)인 조건을 만족하는 \((x_1,x_2)\) 중에서 \(f: A \rightarrow \mathbb{R}\)를 maximization하는 \((x_1,x_2)\)를 찾는것, 즉 \[ \text{maximize} -(x_1^2 + x_2^2) + 4 \ \text{ subject to } \ x_1 \ge 1 \text{ and } x_2=1 \]
  • (예시 2)에서는 \(A\)가 \(\mathbb{R}^2\)가 아닌 \(\mathbb{R}^2\) 상에서 \(X_1 \ge 1\)이고 \(X_2=1\)인 직선이 된다.

plot(-100,100, xlim=c(-5,5), ylim=c(-5,5), xlab="X1", ylab="X2", main="A")
segments(x0=1, y0=1, x1=10, y1=1, lwd=2, col=2)

1.2 Minimum and Maximum

• Minimum과 Maximum은 문자 그대로, 어떠한 함수의 가장 큰 값과 가장 작은 값을 가리킨다.
• 그 중에서 global minimum (maximum)과 local minimum (maximum)의 두 개념에 대해서 설명하고자 한다.

Graph of \(cos(3\pi x)/x\) for \(0.1 \le x \le 1.1\)

Global minimum (maximum)

• 개념적으로 global 이라는 문자가 의미하는 것처럼, 함수 \(f\)가 정의된 \(A\) 전체를 통틀어서 가장 작은 값이 global minimum이 되는 것이다.
• 어떠한 set \(A\)에서 정의되며 실수 값을 가지는 함수 \(f: A \rightarrow \mathbb{R}\)에 대하여 Global minimum은 다음과 같이 정의된다 :
  • \(A\)에 포함된 모든 \(\mathbf{x}\)에 대하여 \(f(\mathbf{x}^*) \le f(\mathbf{x})\)가 성립하게 되면, 함수 \(f\)는 \(\mathbf{x}^*\)에서 global minimum을 가진다고 말한다.
    • 이 때, \(f(\mathbf{x}^*)\), 즉, \(\mathbf{x}^*\)에서의 함수 값을 global minimum value라고 말하고
    • \(\mathbf{x}^*\)은 global minimum point라고 말한다.
  • 혹은 이렇게도 표현한다 : \[ \mathbf{x}^* \in A \text{ is a global minimum point of function } f: A \rightarrow \mathbb{R}, \text{ if } f(\mathbf{x}^*) \le f(\mathbf{x}) \text{ for any } \mathbf{x} \in A\]

local minimum (maximum)

• 개념적으로 local 이라는 문자가 의미하는 것처럼, 함수 \(f\)의 근처 영역에서 가장 큰 값을 가지게 되면 local minimum이 되는 것이다.
• 어떠한 set \(A\)에서 정의되며 실수 값을 가지는 함수 \(f: A \rightarrow \mathbb{R}\)에 대하여 local minimum은 다음과 같이 정의된다 :
  • 어떠한 \(\epsilon > 0\)이 존재해서, \(\mathbf{x}^*\)와 \(\epsilon\) 거리 안에 있는 모든 \(\mathbf{x}\)에 대하여 \(f(\mathbf{x}^*) \le f(\mathbf{x})\)가 성립하게 되면, 함수 \(f\)는 \(\mathbf{x}^*\)에서 local minimum을 가진다고 말한다.
    • 이 때, \(f(\mathbf{x}^*)\), 즉, \(\mathbf{x}^*\)에서의 함수 값을 local minimum value라고 말하고
    • \(\mathbf{x}^*\)은 local minimum point라고 말한다.
  • 혹은 이렇게도 표현한다 : \[ \mathbf{x}^* \in A \text{ is a local minimum point of function } f: A \rightarrow \mathbb{R}, \text{ if there exists } \epsilon > 0 \text{ such that } f(\mathbf{x}^*) \le f(\mathbf{x}) \text{ for any } \mathbf{x} \text{ satisfying } d(\mathbf{x},\mathbf{x}^*) < \epsilon\]

Notation

• \(\text{min}\)는 global minimum value를,

• \(\text{argmin}\)는 local minimum value를 찾는 것을 뜻한다.

• (예시 1)

  • \[ \text{max}_{x \in \mathbf{R}^2}{\left[ -(x_1^2 + x_2^2) + 4 \right]} \] 는 \(f(-(x_1^2 + x_2^2) + 4)\)의 global maximum value를 뜻하며, 4가 된다.
  • \[ \text{argmax}_{x \in \mathbf{R}^2}{\left[ -(x_1^2 + x_2^2) + 4 \right]} \] 는 \(f(-(x_1^2 + x_2^2) + 4)\)의 global maximum point를 뜻하며, \((0,0)\)이 된다.

1.3 Other Deifinitions

Continuous

• (Limit) \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\) 함수에 대해서 다음 조건을 만족하면 \(\displaystyle{\lim_{\mathbf{x} \to \mathbf{a}}}f(\mathbf{x}) = L\) 라고 표현한다. : 임의의 \(\epsilon > 0\)에 대해서 항상 \(\delta > 0\)이 존재해서 \(||\mathbf{x} - \mathbf{a}||<\delta\)를 만족하는 \(\mathbf{x} \in A\)에 대해서 \(||f(\mathbf{x}) - f(\mathbf{a})||<\epsilon\) 가 성립한다.

• (Continuous) \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\) 함수에 대해서 다음 조건을 만족하면 \(f\)는 continuous하다고 한다 : 모든 \(\mathbf{a} \in A\)에 대해서 \(\displaystyle{\lim_{\mathbf{x} \to \mathbf{a}}}f(\mathbf{x}) = f(\mathbf{a})\)가 성립한다.

Differentiable

• (partial derivative) \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\)의 \(x_j\)에 대한 partial derivative \({\partial f \over \partial x_j}\)는 다음과 같이 정의된다 : \({\partial f \over \partial x_j} = \displaystyle{\lim_{h \to 0}}{ f(x_1,\dots,x_{j-1},x_{j}+h,x_{j+1},\dots,x_p) - f(x_1,\dots,x_{j-1},x_{j},x_{j+1},\dots,x_p) \over h}\)
• (Differentiable) \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\) 함수에 대해서 다음 조건을 만족하면 \(f\)는 \(\mathbf{a}\)에서 differentiable하다고 한다. : \(\mathbf{a}\)에서 모든 partial derivative가 존재하고, \(\displaystyle{\lim_{\mathbf{x} \to \mathbf{a}}}{ ||f(\mathbf{x}) - [f(\mathbf{a}) + \nabla f(\mathbf{a})(\mathbf{x} - \mathbf{a})]|| \over ||\mathbf{x}-\mathbf{a}||}\)가 성립한다.
  • 이 때, \(\nabla f(\mathbf{x}) = \begin{bmatrix} {\partial f \over \partial x_1} (\mathbf{x}) \\ \vdots \\ {\partial f \over \partial x_p} (\mathbf{x}) \\ \end{bmatrix}\)

open & closed & boundary

• (open) \(A \subset \mathbb{R}^p\)에 대해서 다음 조건이 성립하면 \(A\)는 open이라고 한다 : \(A\)에 포함되는 각 \(\mathbf{x} \in A\)에 대해서, \(\mathbf{x}\)를 중심으로 한 어떠한 open ball이 존재해서 open ball의 모든 point가 \(A\)에 속한다. 다시 말해서 \(||\mathbf{x} - \mathbf{y}|| < r\)이 성립하는 모든 \(\mathbf{y}\)가 \(A\)에 속하게 하는 \(r\)이 존재한다.

• (boundary) \(A \subset \mathbb{R}^p\)에 대해서 다음 조건이 성립하면 \(\mathbf{x}\)는 \(A\)의 boundary라고 한다 : \(\mathbf{x}\)를 중심으로 한 모든 open ball에 대해서 항상 일부 point는 \(A\)에 속하고 일부는 \(A\)에 속하지 않는다.

• (closed) \(A \subset \mathbb{R}^p\)에 대해서 다음 조건이 성립하면 \(A\)는 closed라고 한다 : \(A\)의 모든 boundary를 \(A\)가 포함한다.

bounded

• \(A \subset \mathbb{R}^p\)에 대해서 다음 조건이 성립하면 \(A\)는 bounded라고 정의한다. : 어떠한 \(M>0\)이 존재해서 모든 \(\mathbf{x} \in A\)에 대해서 \(||\mathbf{x}|| < M\)이 성립한다.

compact

• \(A \subset \mathbb{R}^p\)에 대해서 \(A\)가 closed이고 bounded이면 compact하다고 정의한다.
  • 실수 공간, 즉 \(\mathbb{R}^p\)가 아니면 compact의 정의가 조금 달라진다.

Gradient

• \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\)에 대해서 \(\mathbf{x} \in A\)에서의 \(f\)의 gradient는 다음과 같이 정의된다 \[ \nabla f(\mathbf{x}) = \begin{bmatrix} {\partial f \over \partial x_1} (\mathbf{x}) \\ \vdots \\ {\partial f \over \partial x_p} (\mathbf{x}) \\ \end{bmatrix} \]

• 개념적으로 \(\nabla f(\mathbf{x})\)는 \(\mathbf{x}\)에서 \(f\)가 가장 급격하게 증가하는 방향과 정도를 가리킨다.

  • 즉, \(\nabla f(\mathbf{x})\) 벡터의 방향이 \(f\)가 가장 급격하게 증가하는 방향을 가리키고
  • \(\nabla f(\mathbf{x})\) 벡터의 크기가 \(f\)가 증가하는 정도라고 생각할 수 있다.

The gradient of the function \(f(x,y) = −(cos^2x + cos^2y)^2\)

Critical point

• \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\)에 대해서, \(\mathbf{x} \in A\)에서 \(f\)가 미분이 불가능하거나 \(\nabla f(\mathbf{x}) = \mathbf{0}\)이면 \(\mathbf{x}\)를 Critical point라고 부름

Saddle point

• \(f: A \subset \mathbb{R}^p \rightarrow \mathbb{R}\)에 대해서, \(\nabla f(\mathbf{x}) = \mathbf{0}\)이지만 \(f(\mathbf{x})\)가 local maximum도 local minimum도 아닌 경우, \(\mathbf{x}\)를 Saddle point라고 부름

A saddle point (in red) on the graph of \(z = x^2 − y^2\)

• (예시)
  • 이 때, \((0,0)\)은 saddle point이며, \(x=0\)기준으로는 local maximum, \(y=0\) 기준으로는 local minimum이 되지만 전체 \((x,y)\)에서는 local maximum도, local minimum도 아님을 확인할 수 있다.
  • 이에 따라 saddle point를 다르게 가리키는 말로 minimax point 라고도 한다.

1.4 Global minimum 계산 방법

Property

• global minimum은 local minimum이다.

• (Theorem) \(A \in \mathbb{R}^p\)가 open이고 \(f: A \rightarrow \mathbb{R}\)가 differentiable이라고 하자. 이 때 \(f\)가 \(\mathbf{x}^*\)에서 local minimum을 가진다면, \(\nabla f(\mathbf{x}^*) = \mathbf{0}\)이 성립한다.

  • 따라서 미분이 가능할 경우, local minimum이면 \(\nabla f(\mathbf{x}^*) = \mathbf{0}\)이 성립하게 되는데
  • 반대로 \(\nabla f(\mathbf{x}^*) = \mathbf{0}\)이 성립한다고 해서 local minimum이 아님을 주의하라.

• (Theorem) \(A \in \mathbb{R}^p\)가 compact이고 \(f: A \rightarrow \mathbb{R}\)가 continuous이면, \(f\)는 \(A\)에서 global minimum과 global maximum을 가진다. (존재성)

• Global minimum (혹은 maximum)을 찾는 방법 : compact한 공간 \(A\)에서 정의되는 \(f: A \rightarrow \mathbb{R}\)에 대해서

  1. \(A\) 안에서 모든 critical point를 찾고 그에 대한 함수값을 계산한다.
  2. \(A\)의 boundary, 즉 경계선에서의 minimum 혹은 maximum 값을 계산한다.
  3. 1과 2에서의 minimum과 maximum이 global minimum이 된다.

• (예시 3) \[ \text{max}_{x_1^2 + x_2^2 \le 1}{\left[ -(x_1^2 + x_2^2) + 4 \right]} \]

  • \[ \nabla f(\mathbf{x}) = \begin{bmatrix} {\partial f \over \partial x_1} (\mathbf{x}) \\ {\partial f \over \partial x_2} (\mathbf{x}) \\ \end{bmatrix} = \begin{bmatrix} -2x_1 \\ -2x_2 \\ \end{bmatrix} \] 이기 때문에 \((0,0)\)이 유일한 critical point이며 이 때 함수값은 4이다.
  • 정의역이 \(x_1^2 + x_2^2 \le 1\)이고 boundary에서 \(f\)의 함수값은 3이다.
  • 따라서 maximum은 \((0,0)\)에서 4가 되며, minimum은 \(x_1^2 + x_2^2 = 1\)에서 3을 가진다.

• (예시 4) \(f(x_1,x_2) = x_1^2 + 4 x_2^2 - 2x_1^2 x_2 + 4\)의 \(-1 \le x_1 \le 1\) & \(-1 \le x_2 \le 1\)에서의 global minimum과 global maximum을 구하라.

  • boundary는 다음과 같고
    1. \(x_1=1\), \(-1 \le x_2 \le 1\)
    2. \(x_1=-1\), \(-1 \le x_2 \le 1\)
    3. \(-1 \le x_1 \le 1\), \(x_2=1\)
    4. \(-1 \le x_1 \le 1\), \(x_2=-1\)
  • gradient \(\nabla f\)는 다음과 같음
    • \({\partial f \over \partial x_1} = 2x_1 - 4x_1x_2\)
    • \({\partial f \over \partial x_2} = 8x_2 - 2x_1^2\)
  • critical point는
    • \(2x_1 - 4x_1x_2=0\)
      • 밑의 식을 그대로 대입하면, \(x_1(2-x_1^2) = 0\)
    • \(8x_2 - 2x_1^2=0\)
      • we have \(x_2={x_1^2 \over 4}\)
    • 따라서 critical point의 \(x_1\) 값은 \(0, \pm \sqrt{2}\)이 된다.
    • 이 중, \(-1 \le x_1 \le 1\) & \(-1 \le x_2 \le 1\)를 만족하는 것은 \(x_1=0\) 뿐이므로
    • 해당 region에서 critical point는 \((0,0)\)이고, \(f(0,0)=4\)이다.
  • boundary의 경우
    1. \(f(1,x_2)=g(x_2) = 5+ 4x_2^2 - 2x_2 = 4(x_2^2-{1\over2}x_2)+5 = 4(x_2-{1\over 4})^2 + {19 \over 4}\)
       • \(g(1/4)=19/4\)
       • \(g(-1)=11\)
       • \(g(1)=7\)
    2. \(f(-1,x_2)=g(x_2) = 5+ 4x_2^2 - 2x_2 = 4(x_2^2-{1\over2}x_2)+5 = 4(x_2-{1\over 4})^2 + {19 \over 4}\)
       • \(g(1/4)=19/4\)
       • \(g(-1)=11\)
       • \(g(1)=7\)
    3. \(f(x_1,1)=h(x_1) = 8 - x_1^2\)
       • \(h(-1) = 7\)
       • \(h(1) = 7\)
       • \(h(0) = 8\)
    4. \(f(x_1,-1)=h(x_1) = 8 + 3x_1^2\)
       • \(h(-1) = 11\)
       • \(h(1) = 11\)
       • \(h(0) = 8\)
  • 따라서 다음 중
    • \(f(0,0)=4\)
    • \(f(1,1/4)=f(-1,1/4)=19/4\)
    • \(f(1,-1)=f(-1,-1)=11\)
    • \(f(1,1)=f(-1,1)=7\)
    • \(f(0,1) = 8\)
    • \(f(0,-1) = 8\)
  • global minimum은 \(f(0,0)=4\) 이고 global maximum은 \(f(1,-1)=f(-1,-1)=11\)이다.

• 그러나 이러한 방법으로는 \(f\)가 복잡할때는 global minimum을 찾기가 어려워진다.

  • 따라서 일반적으로는 최적화 문제를 풀 때 계산적인 방법을 사용한다.
  • 가령 다음과 같이 \(f\)의 여러 \(x\)값의 grid에 대해서 \(f(x)\) 함수값을 계산한 이후, 가장 큰 작은 값을 global minimum으로 계산하는 것이다.
  • 그러나 이러한 방법의 경우, 계산량이 매우 많이 필요하기 때문에 (특히 차원이 클수록) 보다 효율적으로 최적화 문제를 풀기 위하여 iterative한 방법을 사용한다. (Convex optimization 참조)

1.5 Convex optimization

• Convex opitmization은 formal하게 다음과 같은 형태로 정의할 수 있다. : \[\begin{align*} \begin{split} \text{minimize}_{\mathbf{x}} & \quad f(\mathbf{x}) \\ \text{subject to } & \quad g_j(\mathbf{x}) = c_j, \ j=1,\dots , m \\ & \quad h_l(\mathbf{x}) \ge d_j, l=1,\dots ,p \end{split} \end{align*}\]

  • 이 때, \(f\)와 \(g_j\)들은 convex function이고
  • \(h_i\)들은 affine transformation이다.

• Convex optimization의 가장 큰 특징은 local minimum이 global minimum과 동일하다는 것이다.

• 또한 local minimum은 iterative한 방법들로 비교적 쉽고 빠르게 계산이 가능하다.

• 따라서 Convex optimization의 경우 local minimum을 찾는 iterative한 방법을 사용하여 쉽고 빠르게 최적화 문제를 풀 수 있다.

• 그러나 convex optimization이 아닌 경우, 즉 non-convex optimization은 local minimum과 global minimum이 다르기 때문에 local minimum을 찾는 방법을 적용할 수 없다.

  • 따라서 여러 \(x\)값의 grid에 대해서 \(f(x)\) 함수값을 계산하는 방식으로 global minimum을 찾아야 하기 때문에 난제이다.
  • Machine learning 분야에서는 이를 위해 local minimum을 찾는 iteratvie한 방법을 개선한 방법들을 사용하지만 (ADAM 알고리즘 등), 이러한 방법들이이 global minimum을 찾는 것을 보장하지는 않는다.

Section 2. Optimization의 계산 테크닉

2.1 Gradient descent

• Gradient descent는 미분가능한 함수 \(f\)에 대해서 local minimum을 찾는 iterative 방법 중에 하나이다.
• Gradient descent 방법은 다음과 같이 작동한다 :
  1. initial point \(\mathbf{x}_0\) 지정
  2. \[ \mathbf{x}_{k} = \mathbf{x}_{k-1} - \gamma \nabla f(\mathbf{x}_{k-1}) \]
  3. \(\mathbf{x}_k\)가 \(k\)가 증가함에 따라 생기는 변화가 미미할 때까지 (즉 수렴할 때 까지) 2를 계속 반복.
• (Recall) 개념적으로 \(\nabla f(\mathbf{x})\)는 \(\mathbf{x}\)에서 \(f\)가 가장 급격하게 증가하는 방향과 정도를 가리킨다.
  • 따라서 \(-\nabla f(\mathbf{x}_{k-1})\)는 \(-f\)가 가장 급격하게 증가하는 방향과 정도를 가르키므로
  • \(f\)가 가장 급격하게 감소하는 방향과 정도를 가르키는 것으로 이해할 수 있다.
  • 따라서 \(f\)의 local minimum을 찾기 위하여 현재 위치 \(\mathbf{x}_{k-1}\)에서 \(f\)가 가장 급격하게 감소하는 방향인 \(\nabla f(\mathbf{x}_{k-1})\)으로 \(\mathbf{x}\)을 iterative하게 업데이트 해나가는 방식으로 이해할 수 있다.

• 이 때 \(\gamma\)는 learning rate라고 부르는데, iterative한 방법을 통해 local minimum을 찾는 과정에서 매 iteration마다 local minimum으로 다가가는 속도를 조절한다.
  • 보다 정확한 local minimum을 찾기 위해서 0.01이나 0.001 같이 적당히 작은 값으로 지정한다.

2.2 Newton’s method

• Newton’s method (혹은 Newton-Raphson method)는 기본적으로 root-finding algorithm에 속한다.

  • root-finding algorithm이란 어떠한 함수 \(f\)에 대하여 \(f(\mathbf{x})=0\)이 되는 \(\mathbf{x}\)를 찾는 알고리즘을 뜻한다.

• 이를 local minimum을 찾는 문제로 바꾸어서 특히 통계학에서 많이 활용한다.

• Newton’s method는 다음과 같이 진행된다 :

  • 어떠한 함수 \(f\)에 대하여 \(f(\mathbf{x})=0\)이 되는 \(\mathbf{x}\)를 찾기 위해
    1. initial point \(\mathbf{x}_0\) 지정
    2. \[ \mathbf{x}_{k} = \mathbf{x}_{k-1} - {f(x_{k-1}) \over f'(x_{k-1})} \]
    3. \(\mathbf{x}_k\)가 \(k\)가 증가함에 따라 생기는 변화가 미미할 때까지 (즉 수렴할 때 까지) 2를 계속 반복.

• 2처럼 update를 하는 논리는 다음 그림과 같다.

  • \((x_n,f(x_n))\)에서 접선 (빨간 선)을 그었을 때, 이 접선의 기울기는 \(f'(x_n)\)이 된다.
  • 그리고 이 접선이 \(y=0\)과 만나는 \(x\)의 값을 그 다음 step의 \(x_{n+1}\)로 놓을 것이다.
  • 이 때 기울기 \(f'(x_n)\)는 \[ f'(x_n) = {f(x_n) - 0 \over x_n - x_{n+1}} \] 이 성립하기 때문에
  • \(\mathbf{x}_{n+1} = \mathbf{x}_{n} - {f(x_{n}) \over f'(x_{n})}\)이 된다.

• Newton’s method를 optimization에서 활용하는 것은 다음과 같이 활용한다.
  • 어떠한 함수 \(f\)에 대하여 local minimum을 찾기 위해
    1. initial point \(\mathbf{x}_0\) 지정
    2. \[ \mathbf{x}_{k} = \mathbf{x}_{k-1} - {f'(x_{k-1}) \over f''(x_{k-1})} \]
    3. \(\mathbf{x}_k\)가 \(k\)가 증가함에 따라 생기는 변화가 미미할 때까지 (즉 수렴할 때 까지) 2를 계속 반복.
• Newton’s method를 optimization에서 활용하는 것은
  1. local minimum에 대해서 \(f'(\mathbf{x})=0\)인 것을 활용하여 Newton’s method를 적용하는 것으로 생각할 수도 있고
  2. 또는 다음과 같이 taylor expansion을 활용하여 생각할수도 있다.
     • \(\mathbf{x}_k\)에서 다음 iteration으로 update를 생각할 때 \(\mathbf{x}_k + t\)의 함수값 \(f(\mathbf{x}_k + t)\)를 다음과 같이 taylor exapnsion을 통해 나타낼 수 있다 : \[ f(\mathbf{x}_k + t) \approx f(\mathbf{x}_k) + f'(\mathbf{x}_k)t + {1\over 2} f''(\mathbf{x}_k)t^2 \]
     • 이는 \(t\)에 대한 2차 함수이기 때문에 미분해서 0으로 놓음으로써 minimum 값에 해당하는 \(t\)를 계산할 수 있다 : \[ {d\over dt}\left( f(\mathbf{x}_k) + f'(\mathbf{x}_k)t + {1\over 2} f''(\mathbf{x}_k)t^2 \right) = f'(\mathbf{x}_k) + f''(\mathbf{x}_k)t = 0 \]
     • 따라서 \(t=-{f'(\mathbf{x}_k)\over f''(\mathbf{x}_k)}\)이 성립하므로 \[ \mathbf{x}_{k+1} = \mathbf{x}_{k} - {f'(x_{k}) \over f''(x_{k})} \]
• Newton’s method를 직관적으로 해석하면 다음과 같다.
  • Newton’s method를 \(f=0\)이 되는 root를 찾는 알고리즘으로 생각할 때는 0이 되는 \(\mathbf{x}\)를 찾기 위해 \(f\)를 linear한 1차 함수로 Taylor expansion을 통해 근사한 이후 근사한 1차 함수에 대해서 root를 찾아나가는 것으로 해석할 수 있고
  • Newton’s method를 optimization을 위한 알고리즘으로 생각할 때는 \(f\)의 local minimum이 되는 \(\mathbf{x}\)를 찾기 위해 \(f\)를 quadratic한 2차 함수로 Taylor expansion을 통해 근사한 이후 근사한 2차 함수에 대해서 minimum을 찾아나가는 것으로 해석할 수 있다.
• Newton’s method vs Gradient descent
  • Gradient descent는 수렴속도가 느린편이다. 왜냐하면 local minimum 근처에서는 gradient가 0에 가까워지기 때문에 속도가 느려지기 때문이다. 다만 \(f'\)만 계산하면 되기 때문에 계산하기에 편리하다
  • Newton’s method는 수렴속도는 빠른편이다. Gradient descent와 같은 문제가 발생하지 않으나, 다만 \(f''\)까지 계산해야하기 때문에, \(f''\)을 계산하기 힘든 경우에, 즉 \(f\)가 복잡한 경우에는 사용하기가 힘들다.

2.3 Lagrange multiplier

• Lagrange multiplier는 equality constraint가 있는 상태에서 어떠한 함수 \(f\)의 local minimum을 찾는 방법이다.
  • 이는 다음과 같이 formal하게 표현할 수 있다. \[\begin{align*} \begin{split} \text{minimize}_{\mathbf{x}} & \quad f(\mathbf{x}) \\ \text{subject to } & \quad g_j(\mathbf{x}) = 0, \ j=1,\dots , m \\ \end{split} \end{align*}\]

• 이를 풀기위해서는 다음과 같이 Lagrangian function을 정의하고 \[ L(\mathbf{x}, \lambda_1, \dots , \lambda_m) = f(\mathbf{x}) + \sum_{j=1}^{m}{\lambda_j g_j(\mathbf{x})} \]
  • \(\nabla L = 0\)의 식을 풀어서 local minimum point인 \(\mathbf{x}^*\)를 찾는 방식으로 이루어진다.
• (예제) \(x^2 + y^2 = 1\)의 constraint 아래에서 \(f(x^2 + y^2)=x+y\)를 최대화하는 \(x\)와 \(y\)를 찾아라
  • \(L(x,y,\lambda) = x+y + \lambda (x^2 + y^2 - 1)\)에 대해서 gradient를 계산하고 0으로 놓게되면 되면
  • \(\nabla L(x,y,\lambda) = [1+2\lambda x, 1+2\lambda y, x^2 + y^2 - 1]^t = 0\) 와 같은 식을 얻게 된다.
  • 따라서 다음과 같은 \(x\), \(y\), \(\lambda\)간의 관계식을 얻게 된다 : \[ X(m,n)= \begin{cases} 1+2\lambda x = 0\\ 1+2\lambda y = 0\\ x^2 + y^2 - 1 = 0 \end{cases} \]
  • 이에 따라 \[ x=y=-{1\over 2\lambda} \] 를 위 두식으로부터 얻을 수 있고 이를 세번째 식에 대입하면
  • \(\lambda = \pm {1 \over \sqrt{2}}\)을 얻게된다.
  • \(f({1 \over \sqrt{2}},{1 \over \sqrt{2}})=\sqrt{2}\) 와 \(f(-{1 \over \sqrt{2}},-{1 \over \sqrt{2}})=-\sqrt{2}\) 이기 때문에
  • constrained maximum은 \(\sqrt{2}\)이고 constrained minimum은 \(-\sqrt{2}\)이다.

2.4 Machine learning에서의 optimization 테크닉

• 기본적으로 위에서 다룬 알고리즘들은 local minimum을 찾는 알고리즘이다.
• 그러나 non-convex optimization의 경우 local minimum과 global minimum이 다르기 때문에 위에서 다룬 local minimum을 찾는 알고리즘을 적용할 수 없다.
  • 다음 그림과 같이 initial point를 잘못 잡을 경우 global minimum이 아닌 local minimum을 찾게 될 것이기 때문이다.
• 특히 Machine learning에서 모형을 learning하기 위해서는 통계학과는 다르게 (통계학에서는 보통 convex optimizaton을 다룸) non-convex optimization을 수행해야한다.
• Machine learning에서는 non-convex optimization을 수행하기 위해 위에서 다룬 iterative한 방법들을 변화시켜서 사용한다.
  • 대표적으로 Stocastic Gradient descent가 있으며 이는 local minimum에 빠지는 문제를 어느정도 보완한다.
  • 다만 이러한 방법들이 global minimum으로 수렴하는 것을 보장하지는 않는다.
• Stochastic Gradient descent (SGD) :
  • 일반적으로 통계의 모형을 fitting하는 과정은 loss function을 최소화 하는 문제로 표현이 가능하다.
  • 예를 들어 linear regression의 경우 \[y_i = \beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip} + \epsilon_i\]
  • 이에 대해서 MLE를 사용하여 추정하는 것은 다음과 같은 loss function을 최소화하는 것으로 표현이 가능하다 : \[ R(\boldsymbol{\beta}) = \sum_{i=1}^{n}{ (y_i - \beta_0 - \beta_1 x_{i1} - \dots - \beta_p x_{ip})^2 }\]
  • 이는 각 관측치 \(i\)에 대한 loss function의 합의 형태로 표현이 가능하다. \[ R(\boldsymbol{\beta}) = \sum_{i=1}^{n}{R_i(\boldsymbol{\beta})} \]
    • 이 때, \(R_i(\boldsymbol{\beta}) = (y_i - \beta_0 - \beta_1 x_{i1} - \dots - \beta_p x_{ip})^2\)
  • 일반적인 Gradient descent은 \[\nabla R(\boldsymbol{\beta}) = \sum_{i=1}^{n}{\nabla R_i(\boldsymbol{\beta})}\]를 활용하게 된다.
  • 이 때, Stochastic Gradient descent는 모든 \(i=1,\dots,n\)을 사용한 gradient를 계산하는 것이 아닌 일부의 \(i\)를 랜덤하게 골라서 그에 해당하는 gradient만 사용해서 iterative하게 업데이트 해나가는 최적화 방법이 된다.
  • 이렇게 하면 모든 \(i\)에 대해서 gradient를 계산하지 않아도 되어서 계산속도가 빨라질 수 있기도 하고, 그 외에 \(\nabla R(\boldsymbol{\beta})\)를 사용하지 않기 때문에 \(R(\boldsymbol{\beta})\)의 local minimum에 빠지지 않을 수 있는 장점 또한 가지고 있다.
• SGD 외에도 수렴속도가 더 빠른 더 발전된 형태의 최적화 방법들이 있다
  • SGD momentum, ADAM등의 방법 등이 이에 속하며, 최신 Machine learning 방법론에서도 ADAM 등의 발전된 최적화 방법을 사용한다.

Section 3. 통계학 분야에서의 Optimization Problem의 활용.

• Optimization은 통계학에서도 활발히 활용된다.
  • 통계학에서 모형을 fitting하는 과정을 optimization으로 나타낼 수 있기 때문이다.

3.1 Linear regression

• (데이터) 반응변수 \(Y\)와 설명변수 \(X=(X_1, \dots X_p)\)에 대해서 관측한 데이터가 \(y_i\) & \(\mathbf{x}_i = (x_{i1}, \dots , x_{ip})\) for \(i=1,\dots , n\)이라고 할 때,
• (모형) 다음과 같은 linear regression 모형을 적용하면 \(Y = \beta_0 + \beta_1 X_1 + \dots + \beta_p X_p + \epsilon, \ \epsilon \sim N(0,\sigma^2)\)
• 여기서 parameter인 \(\boldsymbol{\beta} = (\beta_0, \dots , \beta_p)^t\)를 추정하기 위해 Maximum lieklihood estimation (MLE) 혹은 Least square estimation (LSE)를 사용한다.
  1. MLE : Likelihood 혹은 log-Liklihood를 최대화 하는 방식으로 fitting \[ \text{Maximize}_{\boldsymbol{\beta}} L(\boldsymbol{\beta}) = \prod_{i=1}^{n}{ N(y_i,\beta_0 + \beta_1 x_{i1} + \dots + \beta_p, \sigma^2) } \]
     • 이 때, \(N(y_i,\beta_0 + \beta_1 x_{i1} + \dots + \beta_p, \sigma^2)\)은 Normal distribution의 pdf로 \[ N(x,\mu, \sigma^2) = {1\over \sqrt{2\pi \sigma^2}}\exp{\left( -{(x-\mu)^2\over 2\sigma^2} \right)} \]
     • log 함수는 strictly incresing이기 때문에 보통 log를 씌워서 최소화 하는 문제로 바꿔서 푼다 : \[ \text{Maximize}_{\boldsymbol{\beta}} { l(\boldsymbol{\beta})} = \text{Maximize}_{\boldsymbol{\beta}} { \log L(\boldsymbol{\beta})} = -{1 \over 2}\sum_{i=1}^{n}{ \left( y_i - (\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip}) \right)^2 } + Const \]
  2. LSE : Residual sum of squares (RSS)를 최소화 하는 방식으로 fitting \[\text{Minimize}_{\boldsymbol{\beta}} \ \sum_{i=1}^{n}{\left( y_i - (\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip}) \right)^2} \]
• 따라서 Linear regression 모형에서 MSE와 LSE는 동일한 방법임을 알 수 있다.
• 일반적으로 Linear regression 뿐만 아니라, MLE를 계산할 때 estimating equation을 사용한다 :
  • 어떠한 parameter \(\theta\)에 대해서 \[ {\partial l(\theta) \over \partial \theta} = 0 \] 을 계산함으로써 critical point \(\hat{\theta}\)를 확인하고
  • \(\hat{\theta}\)가 global maximum임을 확인하는 과정을 거쳐서 MLE를 계산하게 된다.
• 주의해야할 점은 단순히 \({\partial l \over \partial \theta}(\hat{\theta}) = 0\)이라고 해서 \(\hat{\theta}\)가 MLE임을 보장하는 것이 아니라는 것이다.
  • estimating equation으로부터 알 수 있는 것은 \(\hat{\theta}\)가 critical point일 뿐, 이것이 global maximum인 것까지 확인하는 과정이 필요하다.
  • 다만, 통계학에서 활용하는 분포는 대부분의 경우 좋은 성질을 가지고 있기 때문에 (exponential family는 logarithmically concave하다), 보통 이 critical point가 local maximum이면서 global maximum이기까지 하기 때문에
  • estimating equation \({\partial l \over \partial \theta}(\hat{\theta}) = 0\)만 계산하여 MLE를 구하는 것으로 서술을 끝내는 경우가 많은 것일 뿐이다.
  • 원칙적으로 이 critical point가 global maximum인 것까지 확인해야 한다.
• (예시) Exponential distribution : \(X_1, \dots , X_n \sim Exp(\theta)\). 이 때,pdf는 \(f(x|\theta) = {1 \over \theta}\exp{(-x/\theta)}\)
  • 이 때 log likelihood는 \[ l(\theta) = -n \log \theta - {\sum_{i=1}^{n}{x_i} \over \theta } \]
  • 따라서 \[ {\partial l (\theta) \over \partial \theta } = -{n \over \theta} + {\sum_{i=1}^{n}{x_i} \over \theta^2} = n{ \bar{x}-\theta \over \theta^2} \]
  • \(\theta = \bar{x}\)에서 \({\partial l (\theta) \over \partial \theta }=0\)이고
  • \(\theta > \bar{x}\)에서 \({\partial l (\theta) \over \partial \theta }<0\)이므로 감소하고
  • \(\theta < \bar{x}\)에서 \({\partial l (\theta) \over \partial \theta }>0\)이므로 증가하기 때문에
  • MLE는 \(\hat{\theta} = \bar{x}\) 임을 알 수 있다.
• (예시) Multiple linear regression \(y_i = \beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip} + \epsilon_i \ \epsilon_i \sim N(0,\sigma^2)\)
  • 보통 matrix 버전으로 표현하는 것이 다루기 편하다 : \[ \mathbf{y} = \mathbf{X}\boldsymbol{\beta} + \boldsymbol{\epsilon}, \ \boldsymbol{\epsilon} \sim N_n(0,\sigma^2 I)\]
    • 이 때, \(N_n(0,\sigma^2 I)\)은 \(n\)차원의 multivariate normal distribution으로, pdf는 \[ {1 \over \sqrt{ (2\pi)^{n} |\Sigma| }}\exp{ \left( -{1 \over 2}(\mathbf{y}-\boldsymbol{\mu})^t \Sigma^{-1} (\mathbf{y}-\boldsymbol{\mu}) \right) } \]
  • 이 경우 vector인 \(\boldsymbol{\beta}\)에 대하여 estimating equation \[ {\partial l \over \partial \boldsymbol{\beta}} = {\partial \over \partial \boldsymbol{\beta}} \left( -{1\over 2\sigma^2} (\mathbf{y}-\mathbf{X}\boldsymbol{\beta})^t (\mathbf{y}-\mathbf{X}\boldsymbol{\beta}) \right) = {1 \over \sigma^2}(\mathbf{X}^t \mathbf{y} - \mathbf{X}^t\mathbf{X} \boldsymbol{\beta}) = 0 \] 으로 부터
    • \(\hat{\boldsymbol{\beta}} = (\mathbf{X}^t\mathbf{X})^{-1}\mathbf{X}^t \mathbf{y}\)로 구할 수 있다.
    • 그러나 이 경우는 이 critical point가 global maximum임을 확인하기가 어렵기 때문에 다음의 방법을 고려할 수 있다.
  • log-likelihood는 다음과 같이 표현가능하다 : \[\begin{equation} \begin{split} l(\boldsymbol{\beta}) & = -{1\over 2\sigma^2} (\mathbf{y}-\mathbf{X}\boldsymbol{\beta})^t (\mathbf{y}-\mathbf{X}\boldsymbol{\beta}) + Const \\ & = -{1\over 2\sigma^2} (\mathbf{y}^t \mathbf{y} - 2 \boldsymbol{\beta}^t \mathbf{X}^t \mathbf{y} - \boldsymbol{\beta}^t \mathbf{X}^t \mathbf{X} \boldsymbol{\beta}) + Const \\ & = -{1\over 2\sigma^2} (\boldsymbol{\beta} - (\mathbf{X}^t\mathbf{X})^{-1}\mathbf{X}^t \mathbf{y})^t \mathbf{X}^t\mathbf{X} (\boldsymbol{\beta} - (\mathbf{X}^t\mathbf{X})^{-1}\mathbf{X}^t \mathbf{y}) + Const \end{split} \end{equation}\]
  • 따라서 \(\hat{\boldsymbol{\beta}} = (\mathbf{X}^t\mathbf{X})^{-1}\mathbf{X}^t \mathbf{y}\)에서 최대값을 가짐을 알 수 있으므로 MLE를 구할 수 있다.
• 확인할 수 있듯이, linear regression에서는 MLE를 얻기 위해 optimization problem을 푸는 과정을 수학적으로 유도해서 closed form으로 MLE를 구할 수 있다.
  • 허나, likelihood가 복잡한 경우는 closed form으로 얻기 힘든 경우가 대부분이다.
  • logistic regression과 같이 Generalized linear model이 이러한 경우에 해당되며, 이에 대해서 optimization problem을 풀기 위해서는 Section 2에서 소개한 iterative한 방법들을 사용해야한다. 이 때 일반적으로 Newton’s method를 활용하여 optimization 문제를 풀게 된다.

3.2 Generalized linear model

• binary logistic regression의 경우, 즉 \(Y\)가 0또는 1의 값을 가지는 binary일 때
  • \(P(y_i=1 |\mathbf{x}_i; \boldsymbol{\beta}) = {exp{(\beta_0 + \beta_1 X_1 + \dots + \beta_p X_p)} \over 1 + exp{(\beta_0 + \beta_1 X_1 + \dots + \beta_p X_p)} }\) 로 모델링을 하고
  • likelihood는 \[L(\boldsymbol{\beta}) = \prod_{i=1}^{n}{ P(y_i|\mathbf{x}_i; \boldsymbol{\beta}) }= \prod_{i=1}^{n}{ \left(P(y_i=1|\mathbf{x}_i; \boldsymbol{\beta})\right)^{y_i} \left(P(y_0=0|\mathbf{x}_i; \boldsymbol{\beta})\right)^{1-y_i} }\] 이므로
  • 다음의 log-likelihood를 minimization 시키는 최적화문제를 풂으로써 MLE를 계산해야한다. : \[ l(\boldsymbol{\beta}) = \sum_{i=1}^{n}{ \left[ y_i \log{ \left( P(y_i=1|\mathbf{x}_i; \boldsymbol{\beta}) \right) } + (1-y_i)\log{ \left( P(y_i=0|\mathbf{x}_i; \boldsymbol{\beta}) \right) } \right] } \]
  • 이는 linear regression과 달리 closed form으로 주어지지 않으므로 MLE를 계산하기 위하여 iterative한 방법들을 사용해야한다.
  • 일반적으로 Newton’s method를 활용한다.

3.3 Lasso and Ridge regression

• Lasso와 Ridge regression은 반응변수 \(Y\)와 설명변수 \(X=(X_1, \dots X_p)\)에 대해서 \(p\)가 굉장히 큰 고차원인 경우에 regression을 수행하고자 할 때 사용하는 방법이다. : Regularization 혹은 Shrinkage
  • 다음과 같이 linear regression을 적용하고자 할 때, \(Y = \beta_0 + \beta_1 X_1 + \dots + \beta_p X_p + \epsilon, \ \epsilon \sim N(0,\sigma^2)\)
  • 다음을 통해 Lasso 혹은 Ridge regression 을 수행한다. \[ \text{Minimize}_{\boldsymbol{\beta}} \ \sum_{i=1}^{n}{\left( y_i - (\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip}) \right)^2} + \lambda \cdot \text{Penalty} \]
    • Lasso : \(\text{Penalty} = \sum_{j=1}^{p}{|\beta_j|}\)
    • Ridge : \(\text{Penalty} = \sum_{j=1}^{p}{\beta_j^2}\)
  • 고차원의 데이터의 경우 linear regression을 수행하는데 필요한 parameter 개수가 많아지는 만큼 모형이 복잡해지고 차원의 저주로 인해 성능이 떨어질 수 있기 때문에
  • 데이터에 대해서 덜 fitting이 되더라도 overfitting을 방지하는데 활용하는 방법이다.
• Generalized linear model과 마찬가지로 closed form으로 minimum이 구해지지 않기 때문에, iterative한 방법을 활용하여 최적화 문제를 풀어야한다.
  • Convex optimization problem이기 때문에 local minimum과 global maximum이 같고 굉장히 효율적이고 빠르게 풀 수 있는 문제다.
  • LARS 등의 알고리즘을 통해 풀게 된다.

3.4 EM algorithm

• data에 missing이 있을 때 이에 대해서 maximum likelihood estimation을 하는 방법으로 EM algorithm이 있다.

• 대표적으로 mixture model에 많이 사용된다. : \[f(x|\theta) = \sum_{k=1}^{K}{\pi_k f_k(x|\theta)}\]

  • 이는 다음과 같다. \[\begin{equation} \begin{split} x|z=k,\theta & \sim f_k(x|\theta) \\ P(z=k) & = \pi_k \end{split} \end{equation}\]

• 이 때 \(z\)는 관측이 되지 않은 missing 값이기 때문에 EM algorithm을 통해 풀게 된다 :

• EM algorithm은 local maximum을 찾는 알고리즘이기 때문에 intial value에 따라 다른 값으로 수렴할 수 있기 때문에 주의해야한다.