본문 바로가기

AI 수학53

등식 제약조건에서의 뉴턴방법 (Newton’s Method) 뉴턴방법(Newton's method)은 제약조건이 없는 최적화 문제에서 최적해를 이터레이션(iteration)으로 구하는 방법이었다. 하지만 뉴턴방법은 등식 제약조건을 갖는 최적화 문제로도 확장 적용될 수 있다. 등식 제약조건(equality constraints)을 갖는 컨벡스 최적화 문제(convex optimization problem)는 다음과 같다. \[ \begin{align} & \min_{\mathbf{x}}⁡ f(\mathbf{x}) \tag{1} \\ \\ & \mbox{subject to : } \ \ A\mathbf{x}=\mathbf{b} \end{align} \] 여기서 \(\mathbf{x} \in \mathbb{R}^n\) 은 최적화 변수이고, \(f(\mathbf{x})\.. 2022. 4. 10.
뉴턴방법 (Newton’s Method) 경사하강법(gradient descent)이 어떤 함수의 최소값을 향한 방향을 계산하는데 1차 미분을 사용하는 반면 뉴턴방법(Newton's method)는 2차 미분을 사용한다. 따라서 뉴턴방법이 경사하강법보다는 성능이 훨씬 좋다. 제약조건이 없는 최적화 문제는 다음과 같다. \[ \min_{\mathbf{x}} f(\mathbf{x}) \tag{1} \] 여기서 \(\mathbf{x} \in \mathbb{R}^n\) 은 최적화 변수이고, \(f(\mathbf{x})\) 는 목적함수(objective function)이다. 목적함수는 두 번 미분가능하다고 가정한다. 뉴턴방법의 기본 개념은 최적화 변수의 시작값(starting point) \(\mathbf{x}\) 에서 목적함수 \(f(\mathbf{.. 2022. 4. 8.
내부점 방법 (Interior-Point Method)의 개념 다음 사진은 내부점 방법(interior-point method)에 대해서 1984년 11월 19일에 뉴욕 타임즈지에 실린 기사를 캡쳐한 것이다. 기사 제목은 'Breakthrough in Problem Solving'이다. 전문적인 수학 알고리즘에 대해서 과학 전문지도 아닌 일반 신문에 기사화되는 일은 매우 드문데, 그만큼 내부점 방법의 중요성을 말해주는 것 같다. 그럼 최적화 이론에서 혁명적인 방법으로 일컬어지는 내부점 방법에 대해서 알아보도록 하자. 내부점 방법은 기본적으로 KKT조건식의 해를 구하기 위한 방법이다. 하지만 KKT 조건식을 직접 푸는 대신 조금 수정한 식을 풀어서 점근적으로 최적해를 찾아가는 방법을 택했다. 제약조건이 있는 컨벡스(convex) 최적화 문제에 대해서 \[ \begin.. 2022. 4. 6.
프라이멀 문제와 듀얼 문제의 유도 제약조건을 갖는 최적화 문제는 지시함수(indicator function)를 이용하면 제약조건이 없는 최적화 문제로 바꿀 수 있다. 지시함수는 어떤 집합에 어떤 값이 속하는지를 표시하는 함수로서 어떤 집합 \(\mathcal{X}\) 의 지시함수 \(I_{\mathcal{X}}\) 는 다음과 같이 정의된다. \[ I_{\mathcal{X}} (\mathbf{x}) = \begin{cases} 0, & \mbox{if } \mathbf{x} \in \mathcal{X} \\ \infty, & \mbox{if } \mathbf{x} \notin \mathcal{X} \end{cases} \tag{1} \] 다음과 같은 제약조건을 갖는 최적화 문제가 있을 때, \[ \begin{align} & \min_{\m.. 2022. 4. 4.
역전파 (Backpropagation) 계산 선형 레이어(또는 fully-connected layer, 완전 연결 레이어)는 레이어의 모든 뉴런이 이전 레이어의 모든 뉴런과 연결된 레이어이다. 선형 레이어는 다음과 같이 선형 방정식으로 표현할 수 있다. \[ \mathbf{z}^{(l+1) }=W^{(l) } \mathbf{a}^{(l) }+\mathbf{b}^{(l) } \] 여기서 위첨자 \(l\)은 \(l\)번째 은닉(hidden) 레이어를 뜻하고 \(W^{(l) }\)은 가중치(weights), \(\mathbf{b}^{(l) }\)는 바이어스를 나타낸다. 레이어의 출력 \(\mathbf{z}^{(l+1) }\)은 활성함수(activation function) \(\sigma^{(l+1)}\)를 통과하여 \(\mathbf{a}^{(l+1)}.. 2021. 3. 31.
벡터 함수를 행렬로 미분하기 다변수 스칼라 함수를 벡터로 미분한 것을 그래디언트(gradient), 벡터 함수를 벡터로 미분한 것을 자코비안(Jacobian), 스칼라 함수를 벡터로 두 번 미분한 것을 헤시안(Hessian)이라고 한다. 이번에는 스칼라 함수를 행렬로 미분해 보자. \( X=\begin{bmatrix} x_{11} & \cdots & x_{1n} \\ \vdots & \ddots & \vdots \\ x_{m1} & \cdots & x_{mn} \end{bmatrix} \in \mathbb{R}^{m \times n}\) 가 행렬이고 스칼라 함수 \(f(X)\)가 주어졌을 때 \(f(X)\)에 대한 \(X\)의 미분은 다음과 같이 정의한다. \[ \frac{d f}{d X} = \begin{bmatrix} \frac.. 2021. 3. 27.
다변수 함수의 연쇄법칙 (Chain Rule) 연쇄법칙(chain rule)은 합성함수(composite function)의 도함수를 구할 때 유용하게 사용되는 법칙이다. 합성함수란 두개 이상의 함수를 연결하여 하나의 함수로 만드는 연산을 말한다. 연쇄법칙은 신경망을 학습시킬 때 사용되는 역전파(backpropagation) 알고리즘의 근간을 이룬다. 벡터 \(\mathbf{y}=[y_1 \ \ y_2 ]^T\)를 변수로 하는 다변수 스칼라 함수 \(f(\mathbf{y})\)의 미분 \(df\)는 다음과 같이 계산된다. \[ df= \frac{\partial f}{\partial y_1} dy_1 + \frac{\partial f}{\partial y_2} dy_2 \tag{1} \] 한편 \(y_1, \ y_2\)도 각각 \(\mathbf{x}=.. 2021. 3. 23.
행렬의 조건수 (Condition Number) 어떤 함수 \(y=f(x)\)의 조건수(condition number)는 함수의 입력인 \(x\)의 작은 변화울에 대해 함수의 출력인 \(y\)의 변화율이 얼마인지를 나타내는 수로서, 함수의 민감도를 측정하는 지표이다. 행렬의 조건수도 일반 함수의 조건수 정의를 이용하여 유도할 수 있다. 다음과 같이 행렬 \(A \in \mathbb{R}^{n \times n}\)와 어떤 벡터 \( \mathbf{b} \in \mathbb{R}^n\)에 관한 방정식이 있다고 하자. \[ A \mathbf{x}= \mathbf{b} \] 여기서 벡터 \(\mathbf{b}\)가 어떤 작은 오차로 인하여 \(\mathbf{b}+\Delta \mathbf{b}\)로 변화했다면 이 방정식의 해 \(\mathbf{x}\)도 \(.. 2021. 3. 2.
[KKT 조건 - 3] 프라이멀 문제와 듀얼 문제 최적화 문제는 두 가지 관점에서 문제를 표현할 수 있는데 프라이멀 문제(primal problem)와 듀얼 문제(dual problem)가 그것이다. 어떤 문제에서는 프라이멀 문제보다도 듀얼 문제로 바꾸어 푸는 것이 더욱 효과적일 수 있다. 먼저 프라이멀 문제는 등식과 부등식 제약조건이 있는 본래의 최적화 문제를 말한다. \[ \begin{align} & p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ \mbox{subject to: } \ \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,k \end{align} \] 이 문제에 대한 라그랑지안을 다음과 같이 .. 2021. 2. 17.
[KKT 조건 - 2] KKT 조건과 적용 예제 등식과 부등식 제약조건이 있는 일반적인 최적화 문제에 대해서 \[ \begin{align} & p^\star = \min_{\mathbf{x}} f(\mathbf{x}) \\ \\ \mbox{subject to : } \ & g_i (\mathbf{x}) \le 0, \ \ \ i=1,...,m \\ \\ \ & h_j (\mathbf{x}) = 0, \ \ \ j=1,...,k \end{align} \] KKT 조건(Karush-Kuhn-Tucker conditions)은 다음과 같다. \[ \begin{align} & \mbox{1. stationarity: } \ \nabla_{\mathbf{x}} f(\mathbf{x} ) + \sum_{i=1}^m \mu_i \nabla_{\mathbf{x}} .. 2021. 1. 18.