쉽게 알아보는 공학이야기 15 – 최적화

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

 

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

쉽게 알아보는 공학이야기 15 – 최적화

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

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

 

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

쉽게 알아보는 공학이야기 15 – 최적화

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

쉽게 알아보는 공학이야기 15 – 최적화▲ 영화 굿 윌 헌팅’ 중 문제를 푸는 주인공의 모습 (출처네이버 영화)

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

 

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

쉽게 알아보는 공학이야기 15 – 최적화

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

쉽게 알아보는 공학이야기 15 – 최적화

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

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

 

최저점 찾기 알고리즘

쉽게 알아보는 공학이야기 15 – 최적화

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

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

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

 

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

쉽게 알아보는 공학이야기 15 – 최적화

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

쉽게 알아보는 공학이야기 15 – 최적화

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

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

쉽게 알아보는 공학이야기 15 – 최적화

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