지난 글에서는 convex의 성질에 대해서 간단히 살펴보았습니다.
또 마지막에 convex의 특징에 대해서 설명드렸습니다. 하지만 일일히 convex의 특징을 찾기엔 비용적으로 어려운 부분이 있으니
Hessian이라는 매트릭스를 이용하여 convex인지 아닌지를 더욱 쉽게 판별할 수 있다고 말씀드리면서 마쳤습니다.
그 방법을 알기전에 convex와 concave를 구분짓는 방법부터 살펴보겠습니다.
(기타 예제 및 그림은 KMOOC의 수업자료를 참조하였습니다.)
Convex , Concave?
미분에 대한 이해가 필요합니다. 자세한 설명은 거의 생략하였습니다.
위의 그림은 Hessian matrix, 2차편미분행렬입니다. 이 행렬은 미분을 통해 함수의 방향성을 나타낼 수 있다고 말할 수 있습니다.
예를 들면 다음 그림과 같습니다.
오른쪽에 보이는 것은 아시는 것과 같이 등고선입니다. 또 여러분은 Gradient가 함수의 이동방향이라고 이해하실 수 있습니다.
그렇다면 이 함수가 가지는 값이 결국 방향을 나타낼 수 있다고 말할 수 있다는 것입니다.
이러한 방향성을 담고 있는 것이 Hessian matrix라고 이해하시면 쉽습니다.
먼저 용어부터 알고 가시겠습니다. 다변수 함수 f(x)를 가질 때,
f(x) is strictly convex over X
-> if its Hessian matrix is positive definite for any x in X
f(x) is convex over X
-> if its Hessian matrix is positive semi-definite for any x in X
f(x) is strictly concave over X
-> if its Hessian matrix is negative definite for any x in X
f(x) is concave over X
-> if its Hessian matrix is negative semi-definite for any x in X
구분은 다음 식의 조건에 따라 달라집니다.
이 식이 (h(x)라고 두겟습니다)
1. if h(x)>0, positive definite
2. if h(x) >= 0, positive semi-definite
3. if h(x) <0, negative definite
4. if h(x) <= 0, negative semi-definite
를 만족하게끔 할 것입니다.
(단일 변수의 경우, α 의 조건으로 결정하게 됩니다. H를 α 로 보시면 됩니다 ^.^)
다변수에서는 예를 들어보도록 하겠습니다. y = [y1, y2]라고 두었을 때,
첫번째 식과 두번째 식은 대입해보면 convex라는 사실을 알 수 있습니다. 하지만 3번쨰는 그렇지 않습니다.
convex와 concave를 결정할 때, 위의 방법과 같이 결정하게 됩니다. 하지만 이 방법은 문제가 있습니다.
일일히 수를 생각해줘야 하므로 비용이 많이 든다는 점입니다. 즉, 모든 y에 대해 전부 검사하기는 상당히 어려운 일입니다.
따라서 우리는 k-th principle minor 방법을 생각해 볼 수 있습니다.
Principal Minor
정의는 이렇습니다.
요약하자면 k번째 소 주행렬이란, 매트릭스 H에서 (n-k)만큼의 행과 열을 제거하고 남는 수의 결정자라고 하네요.
예를 보겠습니다.
소 주행렬(principal minor)을 구하는 것은, (n-k)개의 행과 열을 삭제하는 것에서부터 시작됩니다.
>> matrix H에서 대각행렬은 1st principal minor이 됩니다. (이 때 k 는 2)
>> 행렬 [[1,3], [7,9]](2X2 행렬) 는 2nd principal minor중 하나가 될 것입니다. (k = 1)
>> 전체 행렬은 3번째 소 주행렬이 됩니다.
다음은 선도 주행렬(leading principal minor)에 대해 살펴보겠습니다.
matrix H 가 n by n 이라는 것을 감안하면, 다음 그림과 같이 n개의 선도 주행렬을 가지게 됩니다.
바로 예를 보겠습니다.
행렬
에서
>> Leading principal minors : D1 = a, D2 = ac - b^2 (여기서 D는 determinant)
>> Principal minors : dev1 = a, dev1 = d, dev2 = ac-b^2
(여기서 선도 행렬과 소 주행렬의 차이를 볼 수 있습니다. 선도는 a만 고려하지만 소 주행렬은 a와 c 둘 다 고려하게 됩니다.)
이 됩니다. 거의 마지막에 다왔습니다.
선도 및 소 주행렬식을 구하면 다음과 같은 조건으로 convex와 concave를 구별하게 됩니다.
(여기서 k는 위의 k와 같은 의미를 가집니다)
• 𝑯 is positive definite if and only if 𝐷 > 0 for all leading principal minors (선도 주행렬 판단)
• 𝑯 is positive semi-definite if and only if 𝛥𝑘 ≥ 0 for all principal minors (소 주행렬 판단)
• 𝑯 is negative definite if and only if (−1) 𝑘𝐷 > 0 for all leading principal minors (선도 주행렬 판단)
• 𝑯 is negative semi-definite if and only if (−1) 𝑘𝛥𝑘 ≥ 0 for all principal minors (소 주행렬 판단)
바로 예제를 살펴보고 글을 마치도록 하겠습니다.
(다른 예제는 KMOOC의 수업자료를 참고하시길 바랍니다. 글 길이가 너무 길어져 올리지 않았습니다.)
이 예제에서 함수가 convex인 부분을 원한다면 선도행렬들이 양의 값이 되어야 하겠죠??
따라서 12x1 - 36 >=0 이 되는 x값부터가 convex한 부분이라고 할 수 있겠습니다.
이상으로 convex가 무엇인지 간단하게 살펴보았는데요.
정말 쉽게 생각한다면 위의 선도 주행렬이니 소 주행렬이니 생각하지 마시고,
convex하면 경사(기울기)를 이용한 문제를 풀기 쉽다.
또한, 밥그릇 모양을 생각하시면 됩니다 :)
Reference
KMOOC
