Convexity(2)

지난 글에서는 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