머신러닝에는 cost function의 최솟값(최댓값)을 찾기 위한 다양한 알고리즘들이 존재한다.
그중에서도 Zero-order optimization은 미분을 사용하지 않고 원하는 값을 찾아가는 알고리즘들을 말한다.
이번 포스팅에서는 그 중에서도 Coordinate Search라는 방법을 사용해볼 것이다.
임의의 한 점에서 최솟값을 찾기 위한 다음 점으로 나아간다고 생각해보자.
cost function(이하 g라고 하겠다)의 입력값이 2차원만 돼도 한 점에서 다음 점으로 나아갈 수 있는 방향은 360도로 무수히 많다. 이 경우에는 연산 횟수가 매우 많아지기 때문에 입력값의 차원의 영향을 크게 받는다.
그렇기 때문에 생각한 것이 한 점에서 다음 방향으로의 축방향만 고려하는 것이다.
입력값이 2차원(예를 들어 x, y)인 경우라면 ± x, ± y축 4방향만 고려하면 되기 때문에 한 점마다 연산값이 4회로 이전과는 다르게 크게 줄어든다.
축을 따라서 고려해주기 때문에 이를 Coordinate Search라 한다.
아래의 식이 Coordinate Search의 식이다.
w: 현재 위치의 점을 나타냄
alpha: Learning rate라고 불리며 steplength를 조절하는 parameter
e_n: n-D input space에서 n번째 표준기저벡터, 즉 축의 방향 중 하나를 의미함
주어진 cost function에 대해 축방향을 고려하여 g가 가장 작아지는 위치를 찾아 그 방향으로 이동하며 최솟값을 찾는다.
이와 비슷하지만 조금 다른 방법이 있는데 이를 Coordinate Descent라 한다.
Coordinate Search와 결정적인 차이는 각 점마다 번갈아가면서 하나의 축방향만 고려한다는 것이다.
k번째 step에서 x축에 대한 방향을 고려해주었다면, k+1번째 step에서는 y축의 방향을 고려하고 이를 반복하는 것이다. (지금 설명은 2차원에 대해서만 예를 드는 것이고 n차원에 대해서는 n개의 축방향을 번갈아가면서 고려해야 한다. 헷갈리지 말자!)
작은 차이이지만 상황에 따라 효율적인 방법이 다르다.
위의 식에서 alpha를 고정하느냐 조절하느냐에 따라서 '고정형'과 '조절형'이 있다.
고정형은 말그대로 alpha값을 하나로 고정하여 최솟값을 구하는 방식이다.
조절형은 여러가지가 있는데 이중에서 강화학습에 많이 쓰이는 감쇄형을 알아보자. 감쇄형은 k번째 step에서 alpha를 1/k로 하여 최솟값을 구하는 방식이다. 조절형은 시작점과 최솟값과의 거리가 너무 멀다면 컴퓨터의 연산범위를 넘어가거나 오래 걸릴 수 있다는 단점이 있지만 가까운 경우에는 고정형에 비해 훨씬 효율적이다.
지금까지 Coordinate Search와 Coordinate Descent, 고정형과 감쇄형에 대해 설명했다.
이제 이에 대한 코드를 python으로 구현해보자.
나는 Coordinate Descent를 먼저 구현한 후에 이를 기반으로 Coordinate Search를 구현했다.
# 고정형(알파와 시작점은 임의로) - Coordinate Descent
def g(w1, w2): # 주어진 cost function
a = w1**2 + w2**2
b = w1*w2
value = 0.26 * a - 0.48 * b
return value
def candidate(g): # gvalue 변화분포 - g / step, 좌표 변화 - x / y좌표
wx0 = int(input())
wy0 = int(input())
alpha = 1/10
g0 = g(wx0, wy0)
gvalue = [g0]
N = 0
wx = [wx0]
wy = [wy0]
bool_ = True
while bool_:
# x
positive_x = wx0 + alpha
negative_x = wx0 - alpha
positive_gx, negative_gx = g(positive_x, wy0), g(negative_x, wy0)
if (g0 > positive_gx) & (positive_gx < negative_gx):
g0 = positive_gx
wx0 = positive_x
N += 1
gvalue.append(g0)
wx.append(positive_x)
elif (g0 > negative_gx) & (positive_gx >= negative_gx):
g0 = negative_gx
wx0 = negative_x
N += 1
gvalue.append(g0)
wx.append(negative_x)
elif (g0 == positive_gx) or (g0 == negative_gx):
break
# y
positive_y = wy0 + alpha
negative_y = wy0 - alpha
positive_gy, negative_gy = g(wx0, positive_y), g(wx0, negative_y)
if (g0 > positive_gy) & (positive_gy < negative_gy):
g0 = positive_gy
wy0 = positive_y
N += 1
gvalue.append(g0)
wy.append(positive_y)
elif (g0 > negative_gy) & (positive_gy >= negative_gy):
g0 = negative_gy
wy0 = negative_y
N += 1
gvalue.append(g0)
wy.append(negative_y)
elif (g0 == positive_gy) or (g0 == negative_gy):
break
else:
break
return gvalue, N, wx, wy
gvalue, N, wx, wy = candidate(g)
while문 속에서 x방향을 먼저 고려하고 y방향을 고려하게 하였다. 이를 하나의 loop로 설정하여 y의 if문에서 else 혹은 cost function이 더이상 내려가지 않는 경우에 break를 통해 코드를 멈췄다.
x축에 대하여 else를 통해 break를 따로 설정하지 않은 이유: x의 변화가 더이상 유효한 결과를 얻지 못한다고 해서 코드를 종료시키면 더 나은 y를 찾을 수 있는 가능성을 배제하게 되기 때문이다.
또한 y값의 변화에 따라 x가 다시 유효한 변화를 만들 수 있는 가능성을 배제하지 않기 위해서 계속해서 반복문에서 작동하도록 남겨두었다. - 다만 여러 번 시작점을 바꿔본 결과 이 코드에서는 그렇지 않은 것 같다.
import matplotlib.pyplot as plt
n = [i for i in range(N+1)]
nx = [i for i in range(len(wx))]
ny = [i for i in range(len(wy))]
plt.subplot(1,2,1)
plt.plot(n, gvalue, label='g')
plt.subplot(1,2,2)
plt.scatter(nx, wx, label='wx', c='r', alpha=0.3)
plt.scatter(ny, wy, label='wy', c='orange', alpha=0.3)
plt.legend()
cost function과 x,y 좌표 모두 최솟값 부근으로 줄어드는 것을 확인할 수 있다.
위의 그래프는 시작점을 (13, 48)로 설정했을 때의 결과이다.
이번에는 감쇄형으로 구현해봤다.
고정형과 비교했을 때 코드의 큰 차이는 없다.
# 감쇄형(알파와 시작점은 임의로) - Coordinate Descent
def g(w1, w2):
a = w1**2 + w2**2
b = w1*w2
value = 0.26 * a - 0.48 * b
return value
def candidate(g): # gvalue 변화분포 - g / step, 좌표 변화 - x / y좌표
wx0 = int(input())
wy0 = int(input())
N = 1
g0 = g(wx0, wy0)
gvalue = [g0]
wx = [wx0]
wy = [wy0]
bool_ = True
while bool_:
# x
alpha = 1/N
positive_x = wx0 + alpha
negative_x = wx0 - alpha
positive_gx, negative_gx = g(positive_x, wy0), g(negative_x, wy0)
if (g0 > positive_gx) & (positive_gx < negative_gx):
g0 = positive_gx
wx0 = positive_x
N += 1
gvalue.append(g0)
wx.append(positive_x)
elif (g0 > negative_gx) & (positive_gx >= negative_gx):
g0 = negative_gx
wx0 = negative_x
N += 1
gvalue.append(g0)
wx.append(negative_x)
elif (g0 == positive_gx) & (g0 == negative_gx):
break
# y
alpha = 1/N
positive_y = wy0 + alpha
negative_y = wy0 - alpha
positive_gy, negative_gy = g(wx0, positive_y), g(wx0, negative_y)
if (g0 > positive_gy) & (positive_gy < negative_gy):
g0 = positive_gy
wy0 = positive_y
N += 1
gvalue.append(g0)
wy.append(positive_y)
elif (g0 > negative_gy) & (positive_gy >= negative_gy):
g0 = negative_gy
wy0 = negative_y
N += 1
gvalue.append(g0)
wy.append(negative_y)
elif (g0 == positive_gy) & (g0 == negative_gy):
break
else:
break
return gvalue, N, wx, wy
gvalue, N, wx, wy = candidate(g)극소점 근처에서는 함수가 잘 동작하지만 조금만 거리가 멀어지면 알파값이 너무 작아져 연산이 잘 되지 않는 것 같다. 시작점이 (3,5)만 돼도 벌써 12000번 돌아간다.
아래는 시작점을 (3,5)로 했을 때 결과이다.
고정형에 비해 더 빠르게 최솟값 부근에 도달하지만 최솟값 부근에서 연산의 양이 상당하다는 장단점을 그래프를 통해 확인할 수 있다.
nx = [i for i in range(len(wx))]
ny = [i for i in range(len(wy))]
n = [i for i in range(N)]
plt.subplot(1,2,1)
plt.plot(n, gvalue, label='g')
plt.subplot(1,2,2)
plt.scatter(nx, wx, label='wx', c='r', alpha=0.3)
plt.scatter(ny, wy, label='wy', c='orange', alpha=0.3)
plt.legend()
이제 coordinate Descent에서 Coordinate Search로 변환하기 위해 다음과 같은 사항을 고려하였다.
< Coordinate Descent => Coordinate Search>
1. x에 대해서만 더 좋은 값 찾기
1-1) g0가 아닌 새로운 변수 gx0를 설정하여 값 할당.
1-2) wx0가 아닌 새로운 변수 better_wx를 설정하여 값 할당.
2. y에 대해서만 더 좋은 값 찾기
2-1) g0가 아닌 새로운 변수 gy0를 설정하여 값 할당.
2-2) wy0가 아닌 새로운 변수 better_wy를 설정하여 값 할당.
3. 좋은 x, y에 대하여 둘을 다시 비교
3-1) g0에 값 할당
3-2) if문으로 wx0 or wy0에 새로운 값 할당
3-3) if문 내에서 wx0 or wy0를 wx or wy에 append
3-4) gvalue에 g0를 append
3-5) N += 1
이를 토대로 구현한 코드는 다음과 같다.
# 고정형(알파와 시작점은 임의로) - Coordinate Search
def g(w1, w2):
a = w1**2 + w2**2
b = w1*w2
value = 0.26 * a - 0.48 * b
return value
def candidate(g): # gvalue 변화분포 - g / step, 좌표 변화 - x / y좌표
wx0 = int(input())
wy0 = int(input())
alpha = 1/10
g0 = g(wx0, wy0)
gvalue = [g0]
N = 0
wx = [wx0]
wy = [wy0]
bool_ = True
while bool_:
# x
positive_x = wx0 + alpha
negative_x = wx0 - alpha
positive_gx, negative_gx = g(positive_x, wy0), g(negative_x, wy0)
if (g0 > positive_gx) & (positive_gx < negative_gx):
gx0 = positive_gx
better_wx = positive_x
elif (g0 > negative_gx) & (positive_gx >= negative_gx):
gx0 = negative_gx
better_wx = negative_x
else:
gx0 = g(wx[-1], wy[-1])
better_wx = gx0
# y
positive_y = wy0 + alpha
negative_y = wy0 - alpha
positive_gy, negative_gy = g(wx0, positive_y), g(wx0, negative_y)
if (g0 > positive_gy) & (positive_gy < negative_gy):
gy0 = positive_gy
better_wy = positive_y
if gx0 < gy0:
g0 = gx0
wx0 = better_wx
N += 1
gvalue.append(g0)
wx.append(wx0)
else:
g0 = gy0
wy0 = better_wy
N += 1
gvalue.append(g0)
wy.append(wy0)
elif (g0 > negative_gy) & (positive_gy >= negative_gy):
gy0 = negative_gy
better_wy = negative_y
if gx0 < gy0:
g0 = gx0
wx0 = better_wx
N += 1
gvalue.append(g0)
wx.append(wx0)
else:
g0 = gy0
wy0 = better_wy
N += 1
gvalue.append(g0)
wy.append(wy0)
elif ((g0 == positive_gx) or (g0 == negative_gx)) & ((g0 == positive_gy) or (g0 == negative_gy)):
break
else:
break
return gvalue, N, wx, wy
gvalue, N, wx, wy = candidate(g)
위와 마찬가지로 고정형의 시작점은 (13,48)로 하였다.
import matplotlib.pyplot as plt
n = [i for i in range(N+1)]
nx = [i for i in range(len(wx))]
ny = [i for i in range(len(wy))]
plt.subplot(1,2,1)
plt.plot(n, gvalue, label='g')
plt.subplot(1,2,2)
plt.scatter(nx, wx, label='wx', c='r', alpha=0.3)
plt.scatter(ny, wy, label='wy', c='orange', alpha=0.3)
plt.legend()
Coordinate Descent에 비하여 step의 수가 조금 더 적다는 것을 알 수 있다.
또한 Coordinate Descent에서는 x가 커지다가 줄어들었는데 여기서는 x가 계속해서 줄어드는 것을 확인할 수 있다.
약간이지만 더 효율적인 결과를 얻을 수 있었다.
마지막으로 감쇄형이다.
# 감쇄형(알파와 시작점은 임의로) - Coordinate Search
def g(w1, w2):
a = w1**2 + w2**2
b = w1*w2
value = 0.26 * a - 0.48 * b
return value
def candidate(g): # gvalue 변화분포 - g / step, 좌표 변화 - x / y좌표
wx0 = int(input())
wy0 = int(input())
g0 = g(wx0, wy0)
gvalue = [g0]
N = 1
wx = [wx0]
wy = [wy0]
bool_ = True
while bool_:
# x
alpha = 1/N
positive_x = wx0 + alpha
negative_x = wx0 - alpha
positive_gx, negative_gx = g(positive_x, wy0), g(negative_x, wy0)
if (g0 > positive_gx) & (positive_gx < negative_gx):
gx0 = positive_gx
better_wx = positive_x
elif (g0 > negative_gx) & (positive_gx >= negative_gx):
gx0 = negative_gx
better_wx = negative_x
else:
gx0 = g(wx[-1], wy[-1])
better_wx = gx0
# y
positive_y = wy0 + alpha
negative_y = wy0 - alpha
positive_gy, negative_gy = g(wx0, positive_y), g(wx0, negative_y)
if (g0 > positive_gy) & (positive_gy < negative_gy):
gy0 = positive_gy
better_wy = positive_y
if gx0 < gy0:
g0 = gx0
wx0 = better_wx
N += 1
gvalue.append(g0)
wx.append(wx0)
else:
g0 = gy0
wy0 = better_wy
N += 1
gvalue.append(g0)
wy.append(wy0)
elif (g0 > negative_gy) & (positive_gy >= negative_gy):
gy0 = negative_gy
better_wy = negative_y
if gx0 < gy0:
g0 = gx0
wx0 = better_wx
N += 1
gvalue.append(g0)
wx.append(wx0)
else:
g0 = gy0
wy0 = better_wy
N += 1
gvalue.append(g0)
wy.append(wy0)
elif ((g0 == positive_gx) or (g0 == negative_gx)) & ((g0 == positive_gy) or (g0 == negative_gy)):
break
else:
break
return gvalue, N, wx, wy
gvalue, N, wx, wy = candidate(g)위와 마찬가지로 감쇄형의 시작점은 (3,5)로 하였다.
import matplotlib.pyplot as plt
n = [i for i in range(N)]
nx = [i for i in range(len(wx))]
ny = [i for i in range(len(wy))]
plt.subplot(1,2,1)
plt.plot(n, gvalue, label='g')
plt.subplot(1,2,2)
plt.scatter(nx, wx, label='wx', c='r', alpha=0.3)
plt.scatter(ny, wy, label='wy', c='orange', alpha=0.3)
plt.legend()
감쇄형의 경우에는 Coordinate Descent에 비해 현저히 적은 step으로 원하는 결과를 얻을 수 있었다.
하지만 이것이 두 코드의 성능의 차이를 말해주는 것 같지는 않다.
이는 오직 한 경우에서만 보여지는 것이고 시작점에 따라, cost function에 따라 다른 효율을 보인다. 따라서 상황에 따라 올바른 방법을 선택하는 것이 중요해보인다.
* 나의 코드에서는 while문 자체에 따로 조건을 걸지 않았다. 이렇게 코드를 짜보고 싶어서 그렇게 하였다. 하지만 적절한 값을 정해놓고 그 값보다 움직이는 범위가 적다면 코드가 멈추는 형식으로 코드를 짠다면 나의 코드보다 더 나은 코드가 될 것이다.
'딥러닝' 카테고리의 다른 글
| [Incarnate the Algorithm] Linear Classification (2) | 2023.04.11 |
|---|---|
| [Incarnate the Algorithm] Linear Regression (0) | 2023.04.07 |
| [Incarnate the Algorithm] Gradient Descent (0) | 2023.04.07 |
| [Deep Learning from scratch] 3. 신경망 (0) | 2023.03.05 |
| [Deep Learning from scratch] 2. 퍼셉트론 (0) | 2023.03.05 |