다운로드
작성자: admin 작성일시: 2016-05-17 22:56:05 조회수: 7268 다운로드: 393
카테고리: 기초 수학 태그목록:

최적화 기초

최적화 문제

최적화 문제는 함수 $f$의 값을 최대화 혹은 최소화하는 변수 $x$의 값 $x^{\ast}$를 찾는 것이다. 수식으로는 다음처럼 쓴다.

$$ x^{\ast} = \arg \max_x f(x) \;\;(\text{최대화의 경우}) $$$$ x^{\ast} = \arg \min_x f(x) \;\;(\text{최소화의 경우}) $$

이 값 $x^{\ast}$를 최적화 문제의 해(solution)라고 한다.

최대화 문제는 $f(x)$ 를 $-f(x)$ 로 바꾸면 풀 수 있으므로 보통 최소화의 경우만 고려한다.

이 때 최소화하고자 하는 함수 $f(x)$를 목적함수(objective function), 비용함수(cost function) 또는 손실함수(loss function) 등으로 부른다. 기호로는 각각 $J, C, L$로 표기하는 경우가 많다.

다음은 1차원 목적함수의 예이다. 그래프에서 이 목적함수 $f_1(x)$의 최저점은 $x^{\ast}=2$임을 알 수 있다.

In [1]:
def f1(x):
    return (x - 2) ** 2 + 2
In [2]:
xx = np.linspace(-1, 4, 100)
plt.plot(xx, f1(xx))
plt.plot(2, 2, 'ro', markersize=10)
plt.ylim(0, 10)
plt.xlabel("x")
plt.ylabel("$f_1(x)$")
plt.title("1차원 목적함수")
plt.show()

다음 함수 $f_2(x, y)$는 2차원 목적함수의 예로 2차원 Rosenbrock 함수라고 한다. 2차원 Rosenbrock 함수는 $x^{\ast}, y^{\ast} = (1, 1)$에서 최소값을 가진다.

$$ f(x, y) = (1 − x )^2 + 100(y − x^2)^2 $$
In [3]:
def f2(x, y):
    return (1 - x)**2 + 100.0 * (y - x**2)**2
In [4]:
xx = np.linspace(-4, 4, 800)
yy = np.linspace(-3, 3, 600)
X, Y = np.meshgrid(xx, yy)
Z = f2(X, Y)

levels=np.logspace(-1, 3, 10)
plt.contourf(X, Y, Z, alpha=0.2, levels=levels)
plt.contour(X, Y, Z, colors="gray",
            levels=[0.4, 3, 15, 50, 150, 500, 1500, 5000])
plt.plot(1, 1, 'ro', markersize=10)

plt.xlim(-4, 4)
plt.ylim(-3, 3)
plt.xticks(np.linspace(-4, 4, 9))
plt.yticks(np.linspace(-3, 3, 7))
plt.xlabel("$x$")
plt.ylabel("$y$")
plt.title("2차원  Rosenbrock 함수 $f(x,y)$")
plt.show()

그리드 서치와 수치적 최적화

목적함수의 값을 가장 작게 하는 $x$ 위치를 찾는 최적화 문제를 푸는 가장 간단한 방법은 가능한 $x$의 값을 여러개 넣어 보고 그 중 가장 작은 값을 선택하는 그리드 서치(grid search) 방법이다. 함수 $f_1(x)$의 그래프를 그려 최저점을 찾은 방법도 그리드 서치 방법의 일종이다. 그리드 서치는 가장 간단한 방법이지만 많은 $x$ 위치에 대해 목적함수 값을 계산해야 한다. 위에서 함수 $f_1(x)$의 최저점을 찾을 때는 사실 100번의 함수 계산을 하였다.

예측 모형을 만들 때 목적함수 값, 즉 예측 오차를 구하려면 모든 트레이닝 데이터 집합에 대해 예측 값과 타겟 값의 차이를 구해야 하므로 상당히 많은 계산량을 요구한다.따라서 그리드 서치보다 목적함수 계산을 적게 할 수 있는 방법이 필요하다.

반복적 시행 착오(trial and error)에 의해 최적화 필요조건을 만족하는 값 $x^{\ast}$를 찾는 방법을 수치적 최적화(numerical optimization)라고 한다. 수치적 최적화 방법은 함수 위치가 최적점이 될 때까지 가능한 한 적은 횟수만큼 $x$ 위치를 옮기는 방법을 말한다.

수치적 최적화 방법은 다음 두 가지 알고리즘을 요구한다.

  • 현재 위치 $x_k$가 최적점인지 판단하는 알고리즘
  • 어떤 위치 $x_k$를 시도한 뒤, 다음 번에 시도할 위치 $x_{k+1}$을 찾는 알고리즘

기울기 필요조건

우선 현재 시도하고 있는 위치 $x$가 최소점인지 아닌지 알아내는 알고리즘을 생각해 보자.

어떤 독립 변수 값 $x^{\ast}$ 가 최소점이 되기 위해서는 일단 다음과 같이 값 $x^{\ast}$에서 함수의 기울기(slope), 도함수 $\dfrac{df}{dx}$ 의 값이 0이라는 조건을 만족해야 한다. 이를 기울기 필요조건이라고 한다.

  • 단일 변수에 대한 함수인 경우, 미분값이 0
$$ \dfrac{df(x)}{dx} = 0 $$
  • 다변수 함수인 경우 모든 변수에 대한 편미분값이 0
$$ \dfrac{\partial f(x_1, x_2, \cdots , x_N)}{\partial x_1} = 0 $$$$ \dfrac{\partial f(x_1, x_2, \cdots , x_N)}{\partial x_2} = 0 $$$$ \vdots $$$$ \dfrac{\partial f(x_1, x_2, \cdots , x_N)}{\partial x_N} = 0 $$

$$ \nabla f = 0 $$

이 때 그레디언트(gradient) 벡터 $\nabla f$를 $g$라는 기호로 간단하게 나타내기도 한다.

$$ g = 0 $$

이 조건을 필요조건이라고 하는 이유는 기울기가 0이라고 반드시 최소점이 되지는 않지만, 모든 최소점은 기울기가 0이기 때문이다. 일반적인 수치적 최적화 알고리즘에서는 기울기 필요조건을 이용하여 최적점에 도달하였는지 판단한다.

기울기가 0이어도 최소점이 아니라 최고점일 수도 있다. 기울기가 0인 위치가 최소점임을 확인하기 위해서는 2차 도함수의 부호도 계산해야 한다. 기울기가 0이고 2차도함수가 양수이면 최소점이다. 반대로 기울기가 0이고 2차 도함수가 음수이면 최대점이 된다.

SGD 방법

SGD(Steepest Gradient Descent)방법은 최급강하법이라고도 하며 단순히 현재 시도하고 위치 $x_k$에서의 기울기 값 $g(x_k)$ 만을 이용하여 다음번에 시도할 위치 $x_{k+1}$를 결정하는 방법이다.

$$ x_{k+1} = x_{k} - \mu \nabla f(x_k) = x_{k} - \mu g(x_k) $$

만약 현재 위치 $x_k$에서 기울기가 음수이면 즉 곡면이 아래로 향하면 $g(x_k) < 0$이므로 앞으로 진행하고 현재 위치 $x_k$에서 기울기가 양수이면 $g(x_k) > 0$이므로 뒤로 진행하게 되어 점점 낮은 위치로 옮겨간다.

$x_k$가 일단 최적 점에 도달하였을 때는 $g(x_k) = 0$이 되므로 더 이상 위치를 옮기지 않는다.

이 때 위치를 옮기는 거리를 결정하는 비례상수 $\mu$를 스텝 사이즈(step size)라고 한다.

위에서 예로 든 1차원 목적함수를 이 방법으로 최적화하면 다음과 같다. 우선 사람이 직접 목적함수를 미분하여 도함수를 파이썬으로 구현해야 한다.

In [5]:
def f1d(x):
    """derivative of f1(x)"""
    return 2 * (x - 2.0)

$x=0$에서 시작하여 SGD로 최적점을 찾아나가는 과정은 다음과 같다.

In [6]:
xx = np.linspace(-1, 4, 100)

plt.plot(xx, f1(xx), 'k-')

# step size
mu = 0.4

# k = 0
x = 0
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x + 0.1, f1(x) + 0.1, "1차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("1차 시도: x_1 = {:.2f}, g_1 = {:.2f}".format(x, f1d(x)))

# k = 1
x = x - mu * f1d(x)
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x - 0.2, f1(x) + 0.4, "2차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("2차 시도: x_2 = {:.2f}, g_2 = {:.2f}".format(x, f1d(x)))

# k = 2
x = x - mu * f1d(x)
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x - 0.2, f1(x) - 0.7, "3차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("3차 시도: x_3 = {:.2f}, g_3 = {:.2f}".format(x, f1d(x)))

plt.xlabel("x")
plt.ylabel("$f_1(x)$")
plt.title("SGD를 사용한 1차함수의 최적화")
plt.ylim(0, 10)
plt.show()
1차 시도: x_1 = 0.00, g_1 = -4.00
2차 시도: x_2 = 1.60, g_2 = -0.80
3차 시도: x_3 = 1.92, g_3 = -0.16

SGD에서는 스텝사이즈의 크기를 적절히 조정하는 것이 중요하다. 보통 스텝사이즈를 사용자가 경험적으로 얻는 값으로 고정하거나 특정한 알고리즘에 따라 변화시킨다. 하지만 스텝 사이즈가 너무 작으면 최저점을 찾아가는데 시간이 너무 오래 걸리고 스텝사이즈가 너무 크면 다음 그림과 같이 오히려 최저점에서 멀어지는 현상이 발생할 수 있다.

In [7]:
xx = np.linspace(-3, 8, 100)

plt.plot(xx, f1(xx), 'k-')

# step size (너무 큰 값!)
mu = 1.1

# k = 0
x = 0
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x + 0.2, f1(x) + 0.1, "1차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("1차 시도: x_1 = {:.2f}, g_1 = {:.2f}".format(x, f1d(x)))

# k = 1
x = x - mu * f1d(x)
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x + 0.2, f1(x) + 0.4, "2차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("2차 시도: x_2 = {:.2f}, g_2 = {:.2f}".format(x, f1d(x)))

# k = 2
x = x - mu * f1d(x)
plt.plot(x, f1(x), 'go', markersize=10)
plt.text(x - 1.2, f1(x) - 0.7, "3차 시도")
plt.plot(xx, f1d(x) * (xx - x) + f1(x), 'b--')
print("3차 시도: x_3 = {:.2f}, g_3 = {:.2f}".format(x, f1d(x)))

plt.ylim(0, 15)
plt.xlabel("x")
plt.ylabel("$f_1(x)$")
plt.title("SGD를 사용한 1차함수의 최적화 (스텝사이즈가 너무 큰 경우)")
plt.show()
1차 시도: x_1 = 0.00, g_1 = -4.00
2차 시도: x_2 = 4.40, g_2 = 4.80
3차 시도: x_3 = -0.88, g_3 = -5.76

2차원 Rosenbrock 함수에 대해 SGD를 적용해보자. 목적함수를 미분하여 도함수를 구한 다음 그레디언트 벡터를 파이썬 함수로 구현한다.

In [8]:
def f2g(x, y):
    """gradient of f2(x, y)"""
    return np.array((2.0 * (x - 1) - 400.0 * x * (y - x**2), 200.0 * (y - x**2)))

다음 그림에 $x=-1, y-1$에서 시작하여 SGD로 최적점을 찾아나가는 과정을 그레디언트 벡터 화살표와 함께 보였다.

In [9]:
xx = np.linspace(-4, 4, 800)
yy = np.linspace(-3, 3, 600)
X, Y = np.meshgrid(xx, yy)
Z = f2(X, Y)

levels = np.logspace(-1, 3, 10)

plt.contourf(X, Y, Z, alpha=0.2, levels=levels)
plt.contour(X, Y, Z, colors="green", levels=levels, zorder=0)
plt.plot(1, 1, 'ro', markersize=10)

mu = 8e-4  # step size
s = 0.95  # for arrowhead drawing

x, y = -1, -1
for i in range(5):
    g = f2g(x, y)
    plt.arrow(x, y, -s * mu * g[0], -s * mu * g[1],
              head_width=0.04, head_length=0.04, fc='k', ec='k', lw=2)
    x = x - mu * g[0]
    y = y - mu * g[1]

plt.xlim(-3, 3)
plt.ylim(-2, 2)
plt.xticks(np.linspace(-3, 3, 7))
plt.yticks(np.linspace(-2, 2, 5))
plt.xlabel("x")
plt.ylabel("y")
plt.title("SGD를 사용한 2차함수의 최적화")
plt.show()