Convexity(1)

이 글은 convexity에 대해 정리한 글입니다.

함수가 convex하다. 여러분이 ML을 공부하다 보면 경사하강법을 많이 사용하시게 되는데요. 이때, 함수가 convex하다라고 표현이 가능하면 해의 최적값을 좀 더 빠르고 정확하게 찾을 수 있다는 것을 아실 것입니다.

실제로 유명한 GAN에서도 함수를 conex라고 가정하고 풀고 있죠. 하지만 실제로 convex한지는 증명되진 않았습니다.

여기서 나오는 convex에 대해 정리해보겟습니다.

Convex Set

다음과 같은 그림을 보시길 바랍니다.

집합 X에서 점과 점을 잡고 어떤 선을 그엇을 때, 그 선이 포함하는 점조차도 집합 X에 포함된다.

위의 말이 성립되면 그 집합은 convex하다 라고 표현할 수 있습니다. 

따라서, 위 그림에서는 첫번 째, 두번 째 그림만이 convex하다고 표현할 수 있겟네요.

Convex Set은 다음과 같은 성격을 가집니다.

정리하자면,' convex할 때 상수를 더하거나 곱해도 convex하고, 어떤 convex집합 X, Y가 만났을 때, 그 교집합도 convex하다' 라는 의미입니다.

좀 더 수식적으로 풀어보면 이렇습니다.

첫번째 그림은 두번째 그림으로 설명하겠습니다.

먼저, 빨간선을 할선(secant line)이라고 부릅니다.

 어떤 함수 f(x)에서 점 (x1, x2) 를 선택하여 할선을 그렷을 때, 실제 함수 f가 할선의 선분아래에 있으며, 임의로 다른 점 (x1, x2)을 선택했을 때도 선분 아래에 있다면 convex정의가 성립됩니다.

convex와 strictly convex의 차이는 등호(=)의 차이입니다. 

예를 들어, 두번 째 그림의 경우, 파란색 점 (x1, x2)를 선분으로 그린다고 생각해 봅시다. 그럴경우엔 실제 함수 f와 완벽히 일치하게 됩니다. 이때, convex의 정의인 <=는 성립하지만, <는 성립하지 않게됩니다. 완벽하게 동일하니까요. 그래서 밑 함수는 convex이지만 strictly convex는 아닙니다.

위 그림에서 Linear함수는 완벽히 convex하다고 할 수 있습니다.

다음은 convex의 몇 가지 특징입니다.

함수 -f(x)가 convex하다면 실제함수 f(x)는 concave(오목함수)하다고 표현합니다.

두번째는, 실제함수 f가 convex할 경우, αf(x) 또한 convex이며 α >= 0입니다.

1.  convex하다면 접선 위에 있어야 한다는 것입니다. 다변수의 경우 빨간색으로 표시된 변수처럼 기울기로 표시하면 되겠습니다.

2. 실제 함수 f(x)의 2차미분값이 0보다 크거나 같아야 convex하다는 것입니다. 이를 positive semi-definite라고 표현합니다.(뒤에서 설명)

어떤 Model에서 함수가 convex하다는 것을 증명하는 것은 정말 중요합니다. 그만큼 계산이 쉬워지고 해도 찾기가 상당히 쉬워집니다. 하지만 실제로 convex를 찾으려면 실험도 많이 해봐야하고, 값도 일일히 찾아봐야하는데는 비용이 너무 많이 들겁니다. 

그래서 이용하는 것이 Hessian에서 2차미분 값을 이용하는 방법이 있습니다. -> 다음 글에서 이어나가도록 하겟습니다.

감사합니다

Reference

KMOOC