과학에는 하나의 정답이 존재하지만, 공학에는 다수의 해결 방안이 가능합니다. 여러 가지 해결 방안 중 가장 적합한 것을 찾아가는 과정을 최적화(optimization)라 합니다. 최적화 이론은 최대나 최소가 되는 조건을 찾기 위해 시작되었으며, 전통적인 공학을 비롯한 경영, 행정 등 여러 산업 분야에서 널리 활용되고 있습니다. 최근에는 인공지능 분야에서 많은 양의 데이터를 빠른 속도로 처리하기 위한 최적화 알고리즘이 핵심적인 기술로 떠오르고 있습니다.

실생활에서도 자연스럽게 사용하는 최적화

물건을 구입할 때 우리는 가성비를 따집니다. 또 공학 문제에서는 너무 크지도 않으면서 그렇다고 너무 작지도 않은 가장 적당한 조건을 찾습니다. 예를 들어, 단열재를 두껍게 하면 열 손실은 줄지만, 설치비용이 늘어납니다. 따라서 총비용을 최소화하기 위한 적당한 단열재 두께를 찾아야 합니다.

최적화 문제에서 대상이 되는 함수를 목적함수(objective function)라 하고, 이때 주어지는 특정 조건이나 변수의 범위를 제한조건(constraint)이라고 합니다. 목적함수가 성능이나 이윤인 경우는 최댓값 문제가 되고, 목적함수가 소요 시간이나 비용인 경우는 최솟값 문제가 됩니다. 최소화나 최대화는 수학적으로 동일한 최적화 과정입니다.

효율적인 배분을 위한, 선형계획법

목적함수나 제한조건이 모두 단순한 선형 관계로 주어지는 경우는 선형계획법(linear programming)이 활용됩니다. 선형계획법은 한정된 자원을 효율적으로 배분하는 방법을 찾기 위해 개발되었습니다. 예를 들어, 주어진 재료를 가지고 초코빵과 밀빵을 만들 때 이익을 극대화하려면 각각 몇 개씩 만들어야 하는가를 고민해야합니다. 밀빵은 이윤은 적지만 밀가루만 있으면 되고, 초코빵은 초콜릿이 필요하지만, 이윤이 높습니다. 가지고 있는 밀가루와 초콜릿 양은 제한조건으로 주어져 있으며, 이윤은 판매 개수에 비례해서 선형적으로 증가합니다.

▲ 영화 ‘굿 윌 헌팅’ 중 문제를 푸는 주인공의 모습 (출처: 네이버 영화)

선형계획법은 2차 세계대전 당시 효율적으로 군수물자를 수송하고 보급하는 문제에 적용되면서 크게 발전하였습니다. 특히 선형계획법의 하나인 심플렉스(SIMPLEX) 방법은 여러 학문 분야로 확산되었습니다. 영화 <굿 윌 헌팅>을 본 사람이면 기억하겠지만, 대학에서 청소부로 일하던 주인공이 복도 칠판에 적혀 있는 난해한 문제를 보고 흥미를 느끼면서 낙서처럼 풀이를 적는 장면이 나옵니다. 다음 날 아침 출근한 교수는 칠판에 적혀 있는 것을 보고 깜짝 놀랍니다. 그때까지 아무도 풀지 못한 선형계획에 관한 수학 난제를 해결한 것이었습니다.

최대도 최소도 아닌 특이한 안장점

선형 관계로 주어지지 않는 대부분의 최적화 문제는 목적함수가 위로 볼록하거나 아래로 오목하여 미분값이 영이 되는 지점을 찾으면 됩니다. 변수가 두 개인 경우, 산봉우리나 분지에서 x-방향과 y-방향으로 모두 기울기가 영이 됩니다. 하지만 특이하게도, 양방향 기울기가 모두 영인데도 불구하고 최대나 최소가 되지 않는 경우가 있습니다. 공교롭게도 한쪽으로는 최대가 되고, 다른 쪽으로는 최소가 되는 경우입니다. 이러한 점을 안장점(saddle point)이라 합니다. 마치 말의 안정처럼 생겼다고 해서 붙여진 이름입니다.

▲ 쌍곡 포물 곡면을 보이고 있는 감자칩 모형

이러한 안장점은 소청봉에서 내려와 대청봉을 올라가는 능선의 중간 지점에서 찾아볼 수 있습니다. 또 프링글스라는 유명한 감자칩도 대표적인 말안장 형상으로 수학적으로 쌍곡 포물 곡면(hyperbolic parabloid)으로 되어 있습니다. 안장점은 한쪽으로는 최대인데 다른 방향으로는 최소가 되는 특이한 특성을 갖기 때문에 최고점이나 최저점을 찾는 최적화 과정을 어렵게 만듭니다.

최저점 찾기 알고리즘

목적함수가 수식으로 주어지면 기울기가 영인 지점을 찾으면 되지만, 데이터값으로 주어지는 경우에는 최저점을 찾기 위한 수치해석 알고리즘이 필요합니다. 변수가 한 개일 때 알고리즘은 비교적 간단합니다. 함수가 감소하는 방향으로 계속 진행하면 됩니다. 하지만, 변수가 여러 개일 때는 방향 잡기가 쉽지 않습니다.

이해를 돕기 위해 눈을 가리고 산에서 내려오는 방법을 생각해 봅시다. 산의 높이 f(x, y)는 두 개의 변수에 따라 데이터 값이 매겨집니다. 일단 변수가 한 개일 때처럼 현재 위치에서 임의의 방향으로 이동하면서 가장 낮은 점을 찾습니다. 그렇다고 거기가 최저점은 아니고 경로 직선상 최저점일 뿐입니다. 그리고 다른 방향으로 틀어서 새로운 직선 경로에서 다시 최저점을 찾아야 합니다. 계속 방향을 바꾸면서 이 과정을 반복하면 결국은 산 아래로 내려올 수 있습니다.

하지만 좀 더 빨리 내려오려면, 임의의 방향으로 방향을 바꾸는 것보다 기울기가 가장 급한 방향 즉 그래디언트 방향(물이 흘러내리는 방향 또는 등고선에 수직방향)으로 움직이는 것이 좋습니다. 그래디언트 방향으로 한 걸음 이동하여 멈춰서고, 다시 제자리에서 새로운 그래디언트 방향을 찾아서 그리로 또 한 걸음 이동합니다. 이를 반복하면 가장 빠르게 최저점에 도달할 수 있습니다. 이러한 방법을 경사하강법(gradient descent method) 또는 최급강하법(steepest descent method)이라 합니다.

빠른 속도를 자랑하는 확률적 경사하강법

인공신경망을 활용해 음성인식이나 영상처리를 하는 경우, 예측한 결과는 실제 결과와 크고 작은 차이가 발생하는데, 이를 손실함수(loss function)라 합니다. 앞에서 설명한 경사하강법을 써서 손실함수를 최소화하려면 각 점에서 손실함수의 그래디언트를 계산해야 합니다. 하지만 데이터양이 많을 경우 계산 시간은 크기 때문에 무작위로 선정된 몇 개의 데이터를 써서 확률적으로 손실함수의 그래디언트를 추정합니다.

▲ 확률경사하강법 (Stochastic Gradient Descent)

정확하지는 않지만, 신속히 그래디언트를 추정할 수 있으므로 다음 지점으로 빠르게 이동할 수 있습니다. 그래디언트 방향이 부정확해서 우왕좌왕할 수는 있더라도, 전체적으로 보면 빨리 최저점을 찾아갈 수 있습니다. 이를 확률경사하강법(stochastic gradient descent)이라 합니다. 이외에도 모멘텀(momentum)법, 내그(NAG)법, 아담(Adam)법 등 더욱 빠르고 효율적인 최적화 알고리즘이 개발되고 있습니다. 이러한 알고리즘에서 중요한 것은 안장점과 같은 특이점에 갇히지 않고 빠르게 탈출할 수 있는 특성을 갖도록 하는 것입니다. 

최적화 기법은 전통적인 공학 분야에서 최적 설계를 위한 방법으로 널리 활용되어 왔으나, 이제는 빅데이터를 대상으로 하여 인식, 비교, 분류, 탐색, 추론 등 인공지능 알고리즘의 핵심적인 기술로 자리 잡고 있습니다. 실시간으로 정보가 오가는 5G 시대에, 다양한 인공지능 기술이 활용되기 위해서는 더욱 효율적인 최적화 알고리즘이 요구될 것으로 보입니다.