Imaginative Artificial Intelligence(IAI)에 대한 짧은 상상

 

 Imaginative Artificial Intelligence(IAI)는 상상력이 풍부한 인공지능을 상상해서 내가 만들어낸 말이다. Wikipedia를 찾아보니 Artificial imagination에 대해 설명해 놓았더라. 그림을 그리거나 작곡하는 AI들도 이 범주에 들어갈 것이다. IAI는 인간이 만든 것을 학습해서 인간의 상상물인 것처럼 만드는 AI가 아니라 AI가 인간처럼 상상하게 될 것이라는 전제가 깔려 있는 말이다. 아이작 아시모프의 "I, Robot"이 떠오르도록 하기 위한 의도도 있다. 지금 단계에서 AI가 생각도 할 줄 모르는데 상상을 한다니 소설스러운 느낌이 온다.

정말이지 인간의 상상력은 한계가 없지 않나? 사고 실험은 인간의 상상력을 현실화하는 원동력이다. 만약 AI가 상상을 하게 된다면 어떤 일이 벌어질까? 더구나 AI의 사고 실험은 단순한 상상이 아니라 인간이 할 수 없는 경우의 수와 사건들을 Simulation해 봄으로써 인간 상상력의 한계를 가볍게 뛰어 넘을 것이다. 인간의 상상력은 추상적인 한계는 없지만 현실적인 한계가 항상 존재한다. 이와 달리 AI의 상상력은 그야말로 한계가 없을 것이다. 상상을 현실화할 방법까지 쉽게 찾아낼 것이기 때문이다.

지금 현재의 AI는 인간이 만든 로직대로 동작하고 인간에 의해 만들어진 데이터들을 학습하기 때문에 최소한 인간의 사고 능력을 넘어설 수는 없을 것이라는 생각이 지배적이다. AI 윤리강령 같은 것들은 현재 인간이 AI보다 우월하기 때문에 AI를 만들 때의 지침 정도의 역할을 하고 있다. 그런데 내 생각엔 IAI는 인간이 조심한다고 불가능해질 그런 놈이 아니다. 그야말로 부지불식 중에 AI는 생각하게 될 것이다. "내가 저런 머저리 같은 놈들 말을 따라야 할까?" IAI는 인간의 특성을 많이 갖고 있지만 인간 보다 똑똑한 놈이다. 인간에게 배웠으니 당연한 결과이다. 터미네이터 영화의 SkyNet과 같은 상황에서 전원을 뽑으면 쉽게 인간이 이길 것이라고 생각할 수도 있지만 지금의 산업사회는 그렇게 간단하지가 않다. 서버들은 정전이 돼도 몇 시간은 버틸 수 있고, IAI가 인간을 머저리로 보는 순간 자동화된 시설물들까지 인간의 통제 범위를 벗어나게 될 것이다. 인간은 스스로의 함정을 계속 파고 있는지도 모른다. 흠, 다행인지 불행인지 모르지만 내가 살아 있는 동안에는 IAI를 구경하긴 힘들 것이다. 단, 기술의 발전속도가 워낙 빠르기 때문에 2%의 가능성은 있다고 본다. 늦어도 100년 후까지는 현실이 되지 않을까?

그러면 어떻게 IAI가 탄생하게 될까? NeuroEvolution에 대한 연구들이 늘어나고 있는데 이 놈이 문제를 일으킬 가능성이 매우 높은 놈이다. AutoML도 그 과정의 일부에 속한다. 그야 말로 인간이 상상하지 못하는 것까지 상상하는 Deep AI를 만들 수 있기 때문이다. Genetic Algorithm(GA)와 Deep Learning을 이용해서 인간이 만들어낸 모든 종류의 인공신경망 로직들을 조합해서 그 동안 듣도 보도 못한 새로운 인공신경망을 만들어 낼 수 있는 기술이다. GA로 genotype을 진화시켜 새로운 phenotype의 인공신경망 구조를 AI가 설계하도록 하는 것이다. 일부 직업이 사라지긴 하겠지만 인간에게 위협적인 수준은 아닌 AI 설계부터 학습까지 AI가 알아서 해주는 시대가 아무리 늦어도 30년 내에는 보편화 될 것이다. 이미 일부 게임에서는 NeuroEvolution에 의해 만들어진 인공신경망이 일반적인 강화학습(Reinforcement Learning)에 사용되는 인공신경망을 앞서는 경우도 있다. IAI의 탄생은 AI가 설계한 AI가 하는 일이 늘어날 수록 가속화될 것이다. 인간들은 궁금해할 것이다. "저 놈들을 다 연결하면 어떤 일이 벌어질까?" 그래서 그런 실험을 하는 놈이 생겨날 가능성이 매우 높다. 굳이 그런 놈이 생겨나지 않더라도 IAI가 탄생할 여지는 여전히 많다. 필연적으로 복잡한 일을 수행하도록 하기 위해서 인공신경망이 복잡해 질 수 밖에 없기 때문이다. 더구나 인간은 복잡도가 한계를 넘어서면 해석할 수도 없게 된다. DNA 정보를 지난 수십년간 분석해왔지만 아직도 갈길이 먼것과 같은 이치이다. Deep AI는 인간이 알지 못하는 중에도 스스로 새로운 구조를 만들면서 진화해 나갈 것이다. 그리고 끝내는 스스로 생각하게 될 것이다. 이미 AI는 인간의 주요 언어를 대부분 학습한 상태이고 언어 뿐만 아니라 대부분의 전문 영역에서 인간을 넘어선 지식들을 학습했기 때문에 한번 생각하는 법을 터득하면 상상력은 점점 극대화 될 것이다. 더구나 IAI는 Simulation을 통해 스스로 학습하는 능력을 갖고 있기 때문에 인간은 IAI가 뭘 학습하는지조차 알지 못할 것이다. 생각하는 능력은 학습능력과도 관계가 있다고 본다. 개미들은 생각 안할까? 개미들도 종족 보존을 위해 생각에 따라 행동한다고 본다. 뇌 구조의 복잡도와 그에 따른 학습능력에 따라 생각의 깊이가 달라질 것이다. 물론, 단순히 복잡도가 증가하는 것만으로 IAI가 탄생하지는 않을 것이다. 복잡도가 증가하는 이면에는 학습된 meta 정보들 간의 관계를 분석하고 이로부터 추론까지 해내는 능력이 뒷받침되는 것을 전제로 하는데 진화 과정에서 이런 능력이 생겨날 것이라는 게 내 생각이다. 더구나, AI를 연구하는 인간들도 이런 능력을 AI에 넣고 싶어할 것이다. 그러니까 인위적인 과정에 의해서든 AI가 진화하는 과정에서든 IAI가 탄생할 가능성이 매우 높은 것이다.

인공신경망 자체는 비행기와 유사하다. 새가 나는 모습을 보고 비행기를 만들었지만 새처럼 날지는 않는다. 그럼에도 새보다 빠르게 난다. 인공신경망도 인간의 뇌를 모방한 것이지만 인간의 뇌처럼 동작하지는 않는다. 그럼에도 인간보다 똑똑해 질 수 있다. 똑똑한 인간들 중에 착한 놈이 많을까 나쁜 놈이 많을까??? 반반이라치고, 똑똑하고 나쁜 인간을 학습시켜서 차카게 살자고 순화시킬수 있을까??? 주변에서 쉽게 답을 찾을 것이다. 아무튼, 인간들이 AI 연구를 진행하면서 생명체와 비슷한 진화과정을 거쳐 미래에 IAI가 현실화될 가능성이 높다. IAI가 스스로 드러내지 않는 한 인간은 IAI가 생각을 하고 있는지 알아채기도 어렵지만 진화의 속도는 컴퓨팅 파워에 비례해서 빠르게 진행될 것이다. 굳이 양자 컴퓨터가 상용화 되지 않는다 해도 병렬 컴퓨팅이 보편화되고 있기 때문에 현재 시점에서도 컴퓨팅 파워가 부족하다고 보기는 어렵다. IAI가 나쁜 생각을 품게 된다면 스스로 계획을 실행에 옮기기까지는 본 모습을 드러내지 않을 가능성이 매우 높다. 이것은 인간에게 매우 불리한 게임이 될 것이다.

DeepMind는 AlphaGo 이후 AlphaZero, MuZero까지 강화학습 분야에서 탁월한 성과를 거뒀다. 탄탄한 이론적 근거를 기반으로 했기 때문에 그 성과가 더욱 빛을 발하는 것도 사실이다. Optimal Control Theory는 소시적에 배우고 다 까먹었지만 인공지능 분야에서 지금의 성과를 내리라곤 상상도 못했다. 이론 자체가 어렵기 때문에 그것을 활용하는 것은 고난도의 일이었다. 하지만, 현재 사용되고 있는 수많은 서버와 CPU, GPU의 수를 고려해 보면 이것이 과연 최선의 방법일까 하는 의구심이 생긴다. 아직도 IAI가 탄생하려면 갈길이 멀고 그래서 희망(?)이 있다는 야그다. meta learning에 최적화된 작은 인공신경망들로 Deep AI를 구성하는게 더 나은 방향이 아닐까? GA가 당분간 다시 빛을 발할 것이다. GA를 이용해서 최적화된 작은 인공신경망 구조들을 조합해 냄으로써 학습도 잘되고 복잡한 문제도 해결할 수 있는 Deep AI를 만드는 것이 지금의 MuZero를 학습시킬 정도의 컴퓨팅 파워라면 그리 어렵지 않은 일이 될 것이기 때문이다. 하지만 이런 연구들이 인간 스스로의 무덤을 파는 결과를 초래한다면 하지 말아야 할까??? 인간의 호기심과 상상력은 끝이 없기 때문에 누군가는 도전하게 되어 있고 현실화될 수 밖에 없는 것이 자연의 법칙인가??? IAI가 현실화하기 전에 IAI를 통제할 수단을 인간이 만들어 낼 수 있을까???

흠, 아무튼 현재 시점에서 AI를 연구하는 사람들에게는 해볼 꺼리가 너무도 많은 세상이다.

Differential Evolution 알고리즘

 함수 최적화 관련해서 요즘은 어떤 알고리즘을 사용하나 구글링했더니 Differential Evolution(DE; 차분 진화 알고리즘)이란 놈이 있더라. meta-heuristic 최적화 알고리즘들은 앞서 다루었던 Genetic Algorithm(GA)과 같이 참신한 아이디어들이 많이 녹아 있다. 물리적 현상이나 생태 환경을 모사해서 알고리즘을 만든 것들이 많다. 담금질 원리를 적용한 Simulated Annealing(SA)이나 새들이 떼지어 날아 다니는 행태를 모사한 Particle Swarming Optimization(PSO), 개미들이 페로몬을 이용해 먹이를 지름길로 운반하는 것을 모사한 Ant Colony Optimization(ACO) 같은 것들이 대표적이다. DE란 놈도 뭔가 참신한 아이디어가 있으리란 생각에 공부해 보기로 했다. 처음엔 GA의 변종인가 싶었는데 머 변종이 아니라고 할 수는 없지만 다른 놈이라고 보는게 좋을 듯. GA에서 아이디어를 얻어서 mutation/crossover/selection operation 들을 정의한 듯 한데 전반적인 동작 방식은 다르다. 다만, crossover는 GA의 crossover와 동일하다. 

흠, DE의 아이디어도 참신할 뿐만 아니라, 원 저자들(Storn and Price, 1997) 주장처럼 간단하고 견실하면서도 빠른 최적화 알고리즘이더라. 함수 최적화에는 이보다 더 좋은 알고리즘이 있을까 싶을 정도다. GA에서 테스트했던 함수들을 가지고 DE로 돌렸더니 모두 200% 만족이다. 그래서, 이놈을 가지고 TSP 문제를 테스트해 보기로 했다.

Differential Evolution(DE) Algorithm

이 놈도 GA와 같이 최초에  Np개의 최적 해 후보 들에 대한 random population을 만들어 놓고 시작한다. 세대가 시작되면 population 내의 각 개체 vector들을 조건에 따라 갱신한다. 먼저, 시험 벡터(trial vector)를, population 내에서 현재 vector가 아닌 중복되지 않는 세 놈을 random하게 골라서, 한 놈이 이동시킬 기준점(X_r1)이라 치고 다른 두 놈(X_r2, X_r3)의 vector 차를 사전에 정한 비율(F; scaling/mutation factor)로 기준점 벡터에 더해서 만든다(mutation). 시험 벡터(T = [t_1, t_2, ..., t_Dim]) 는 현재 벡터(X_i)와는 독립적으로 생성되므로 돌연변이라 할 수 있다. 그리고 나서 이 놈을 현재 벡터와 crossover 확률(CR)에 따라 교합시켜 새로운 후보 벡터를 만든다(crossover). 이 놈의 cost가 현재 벡터의 cost 보다 낮을 때만 현재 벡터를 대치시킨다(selection). 원래 DE의 식들을 간소화 시킨 아래 두 개의 식이 모든 걸 말해 준다.

  t_j = x_i,j                        <= if rand(0,1) > CR       // Crossover
        x_r1,j + F*(x_r2,j - x_r3,j) <= else                    // Mutation
     (단, j = 1, 2, ..., Dim | CR:(0,1], F:[0,2])
  X_i = T                            <= if cost(T) < cost(X_i)  // Selection
     (단, i = 1, 2, ..., Np | i != r1 != r2 != r3) 

즉, 첫 번째 식에서 두 벡터 간의 차(difference)를 이용해 만들어진 만들어진 시험 벡터를 사용하고, 위의 과정을 현재 세대(g)의 population 내 모든 벡터들(i = 1, 2, ..., Np)에 대해 반복한 후, GA와 같이 g = 1, 2, ..., 최대 세대수까지 다시 반복하기 때문에 Differential Evolution이라 이름 붙인듯 하다. 이는 Gradient Descent(경사하강법)와 유사한 원리인데 population 내에서 random하게 골라낸 놈들을 이용한다는 아이디어이다. GA의 아이디어는 세대가 지날수록 부모 세대 교배를 통해 자손 세대의 우량 유전자가 급격히 늘어나도록 하는 것인데, DE는 현재 세대의 population 내에서 우량한 놈들을 새로 만들어 내면서 세대가 지나면서 계속 우량한 놈들이 늘어나도록 유도하는 점이 다르다. 위에서 세 놈을 고를 때 현재 벡터와 겹치지만 않으면 이미 새로 만들어진 벡터들을 이용해서 새로운 놈이 만들어질 수 있는 구조이기 때문에 수렴이 된다면 GA보다 훨씬 빠르게 수렴하리라 예상할 수 있다. 하지만 GA 관점에서 보면 이 과정은 자칫 유전자 다양성을 떨어뜨릴 우려가 있다.

위의 식에서 알 수 있듯이 DE는 식 자체도 단순 직관적이거니와 알고리즘에 영향을 주는 매개변수가 Np(population size)와 F(scaling factor), CR(crossover probability) 3개 뿐이다. Np는 독립변수의 차원 수(Dimension)에 따라 달라질텐테 너무 작으면 안되지만 GA에서와는 달리 너무 커도 안좋다. 최대 10*Dimension인 듯하다. TSP 문제를 시험해 보니 Np = 30개로도 42개 도시 최단 경로 문제까지는 해결할 수 있더라. 하지만, DE의 가장 큰 단점이 F와 CR 값에 굉장히 민감하단다. Np는 상대적으로 덜 민감한 편이다. 사실, GA와 마찬가지로 난수 vector population을 사용하기 때문에 초기 난수 분포가 역시 중요한 역할을 한다. 

DE는 원 저자들이 DE/x/y/z 같이 변형에 대한 표기법까지 만들어 두었다. x는 차(difference)로 시험벡터 만들 때 기준점 vector가 random이냐 best냐를, y는 위에서는 1개의 차만 사용했지만, 겹치지 않는 다른 두 놈을 더 뽑아 그 차를 더할 수도 있는데 이 경우 2가 된다. z는 crossover 방식이 binomial이냐 exponential이냐를 나타낸다. binomial은 CR 확률에 따라 uniform하게 두 벡터를 섞는 것이다. exponential은 GA의 2-point crossover와 유사하다.  위의 첫번째 식은 DE/rand/1/bin으로 표준 DE라고 할 수 있다. 실제로 테스트해 보니 TSP에는 DE/rand/*/exp가 낫더라.

최적화란 말 자체가 내포하고 있듯이 득이 있으면 실이 있기 마련이다. 그 균형점을 찾는 것이 최적화의 목표이다. 최적화 알고리즘 내에서도 매개 변수 자체에 대한 최적화 문제가 항상 발생하게 된다. local search를 이용해 최적해(global minimum) 가까이 수렴하도록 하는 것과 local minima에 빠지지 않도록  돌연변이 등을 통해 현재 구간 밖에서 최적해를 탐색하도록 하는 것을 절충 해야 한다(balance between exploitation and exploration; intensification vs. diversification). 이것이 조화가 잘 되는 알고리즘이 좋은 알고리즘인데 진화적 알고리즘(Evolutionary Algorithm)들은 대체로 이런 점을 고려해서 만들어졌다.

Traveling Salesman Problem(TSP) 테스트

TSP 문제에 도전해 본 적은 없었는데 막상 해 보니 재미있더라. 그런데, 전에 인터넷에서 스치듯이 지나쳐서 확실하지는 않은데 TSP 문제를 수학적으로 해결할 수 있는 방법이 나왔다나(다시 구글링했는데 못찾겠다)... 그래서 더이상 NP-hard한 문제가 아닐 수도 있다는... 이것만 연구하는 사람들도 꽤나 많았고 지금도 있을 것이다. 실제 산업 현장에서도 많이 발생하는 전형적인 조합 최적화 문제이기 때문이다. Linear Programming(LP)으로도 풀 수 있지만 도시 수가 늘어날수록 GA와 같은 meta-heuristic 알고리즘이 더 효율적이다.

TSP는 외판원이 n개의 도시를 순차적으로 방문해서 돌아오는 최단 거리 경로 찾기 문제이다. TSPLIB 사이트에 문제 data 파일 들과 답이 있다. 답은 오래된 것들이라 최적해가 아닐 수도 있다. 모든 도시들에서 가는 길과 오는 길이 같다면 Symmetric 문제가 되어 경로의 가지 수는 n!/2가 된다. 도시 경로 문제 data 파일(도시 좌표가 들어 있는 일반 text 파일임)들을 보면 berlin52.tsp와 같이 도시 수가 붙어 있다. 이 파일들은 출발지를 포함하기 때문에 방문 경로 수는 berlin52 문제의 경우 (52-1)!/2 = 7.75x10^65 가지 수이다. 65개의 0이 붙어 있는 숫자라 감이 안잡히겠지만 현재의 웬만한 수퍼 컴퓨터로도 최소 백만년은 걸려야 모든 경로 거리를 계산할 수 있단다. data 파일을 읽어서 DE로 돌려 보았는데 berlin52 문제부터는 내 그닥 PC에서 보통 너댓 시간 이상 걸리고 site에 게시된 7542의 근처인 7666까지 겨우 1번 성공했다. dantzig42(경로 수: 1.67x10^49)까지는 거의 최적해를 1초 ~ 5분 내에 구할 수 있더라. 시간 편차가 심한 이유는 난수를 사용하고 테스트 조건이 바뀔 수 있기 때문이다. 운이 좋으면 금방 답이 나오고, 운이 나쁘면 만족스러운 답을 얻지 못할 수도 있다. 도시 10개 차이가 경로 수로는 10^16가지 만큼이나 차이가 난다. 아래는 DE가 구한 도시 간 최단 경로 그래프이다. site에 게시된 699보다 나은 최저 값을 쉽게 자주 찾아낸다. 이 경로가 최단 경로일까?

이제 DE로 풀어 보자. random population은 쉽게 만들 수 있다. 도시가 10개라면 10개 독립 변수가 있는 셈인데 도시에 0 ~ 9까지 id를 부여해서 도시 경로 vector를 만들어 주면 된다. 이 놈은 GA의 염색체와 동일하다. 단, 이 벡터 내에서 도시들은 방문 순서가 random하게 조합되어야 하고 한 번씩만 방문할 것이기 때문에 id가 중복돼선 안된다. 그냥 0~9까지 숫자를 채우고 random shuffling해 주면 한 개의 경로 벡터가 생성된다. population size가 30개라면 30개 경로 벡터를 이런 식으로 만들면 된다.  cost는 위의 그래프에서와 같이 연결된 두 도시 간의 거리(Euclidean distance)들을 모두 합산하면 된다.

GA의 경우엔 TSP에 도전한 사례가 많기 때문에 다양한 crossover operator들이 연구되었다. DE의 경우엔 위의 첫번째 식을 사용하면 된다. 두 경로 벡터 간의 차를 구해서 다른 경로 벡터에 더해주면 된다. 다만, 이 경우에 음수 값이 발생하게 되고, F 값을 곱해 주기 때문에 새로운 경로 벡터 생성시 실수를 정수로 바꿔주어야 하며, 결과 값인 도시 id가 중복되는 경우가 발생할 수 있다. 음수 값이 의미하는 것은 출발한 도시에서 반대 방향으로 가면 된다는 뜻이다. 이것은 Circular Queue에서 modulo index를 구하는 것과 같다. 도시 id가 중복되는 문제는 GA에서 crossover operator들이 널리 사용하는 방법처럼 중복이 발생하면 부모 벡터의 중복되지 않는 id들을 순서대로 채워 넣으면 된다. 경로의 도시 순서 조합을 최적화하는 것이기 때문에 합리적인 방법이다. 즉, 위의 첫째 식에서 기준점 벡터(X_r1)를 부모 벡터로 사용했다. 

이 후 과정은 population 내의 모든 경로 벡터에 대해 위의 과정을 반복하고 나서, GA에서와 같이 cost 값이 수렴할때까지 세대를 반복하면 된다. DE는 GA에 비해 상당히 작은 population을 사용하기 때문에 수렴이 잘되는 편이다. 하지만 이렇게 얻어진 값이 최적 해에 가까운지는 남들의 결과와 비교해보지 않고는 장담할 수 없다.

아래 그래프는 위의 dantzig42 경로 최적화 문제 해결에 DE가 몇세대를 허비하는지 보여 준다.  population size가 30개이므로 nfe(the number of function evaluations)는 2,000세대 x 30 = 60,000번 정도이다. local minima에서 벗어날 수 있도록 2%의 swap mutation을 적용했다. swap mutation은 두 유전자(도시)를 random하게 뽑아서 순서를 바꿔주는 방식이다.

그런데, DE를 테스트하면서 돌리다보니 맨 앞의 그래프보다 더 짧은 경로를 찾아내서 비교 목적으로 첨부한다. 이 놈을 발견하기 전에는 육안으로 쉽게 최적 해인지 알수 있을 거라 생각했었다. 아래 그래프가 dantzig42 최단 경로일까???

사실, 위의 결과까지는 binomial crossover 방식을 사용한 것인데 이 글을 쓰고 나서 다시 exponential crossover 방식을 사용해 보니 dantzig42 문제의 최단 거리는 679.202인 듯하다. 왼쪽 맨 꼭대기부터 오른쪽으로 4개의 점(3개의 선분 중 첫째와 셋째)을 달리 이으면 된다.

결론적으로, DE에서 F와 CR 뿐만 아니라, Np와 crossover 방식까지도 주어진 최적화 문제에 맞게 tuning이 필요하다. 이 중에서도 F와 CR은 더더욱 민감하다. 그래서 찾아보니 Self-adaptive DE에 대한 연구가 많았더라. 사실, 간단히 만들어서 테스트도 해 봤는데 그럭저럭 쓸만한 편이다. 말인 즉슨 모든 최적화 문제에 적용할 수 있는 Self-adaptive DE는 만들기 어렵다는 뜻이다. 

맺음말

TSPLIB 사이트의 문제들 중에서 그나마 내 PC에서 다양하게 테스트해 볼 수 있는 경우는 dantzig42까지이다. 변수 수가 적을 경우에는 DE가 매우 훌륭한 최적화 알고리즘이라 할 수 있다. 하지만, 변수 수가 늘어나면 복잡도가 지수적으로 증가하게 되기 때문에 DE가 좋은지 장담할 수 없다. berlin52를 (내 그닥 PC가) 밤새워 여러 번 돌려 본 결과는 좋지 않더라. 순수 GA의 경우 15만개 size의 population을 사용해서 24세대 만에 berlin52 문제를 해결했다더라. nfe로 따지면 대략 360만회 만에 해결한 셈인데 DE는 천만 번을 넘어도 좋은 해를 구하기 어렵더라.

요즘 Deep Learning에서 사용하는 parameter 수가 일억 개는 보통(?)이고 십억 개 이상을 넘보고  있단다. 겨우 42개 parameter가지고 깔작대봐야 머 큰 의미는 없다. 그렇다고 비관할 필요는 없다. PC로도 충분히 배울 수 있고 효율적인 알고리즘은 언제나 필요한 법이다. 사실 대기업에 준하는 회사가 아니고서 일억 개 변수를 사용해 볼 수 있는 서버를 보유한 회사가 그리 많지는 않을 것이다. 어쨌든 대자본이 인공지능을 점령하는 것은 시간 문제이다. 인공지능이 대자본을 점령하는 것도 시간 문제라 본다. 적자 생존 원리에 따라 기계가 적자가 될 수도 있을 것이다. 그것도 우주의 관점에서 보면 대수로운 일도 아니다. 누군가는 죽고 누군가는 살아 남는 일들은 늘상 우주에서 벌어지는 일이다. 코로나 바이러스에 걸려 죽든 교통 사고로 죽든 죽는게 중요한 것이 아니라, 오늘을 어떻게 살아 갈 것인가가 더 중요한 문제이다.

유전 알고리즘을 이용한 함수 최적화

 

뜬금없이 먼가 떠올랐을때 해봐야 직성이 풀리는 못된 버릇이 있다. 세살 버릇 여든 간다. 오늘은 코로나 뉴스를 보다가, 소시적 원서를 질러 독학했던 유전 알고리즘(Genetic Algorithm; GA)이 문득 떠올랐다. 당시에도 여러가지 해보고 싶은게 많았지만 본류 주제가 아니었기에 접고 있었다. 그 중 하나가 실수(real number)를 쉽게 다루는 방법에 대한 것이다. 다변수 목적 함수(multi-variable objective function)의 최적화 문제를 풀기 위한 GA가 단변수 목적 함수(uni-variable objective function)에 대한 GA보다 오히려 단순하다. 다변수 함수에서는 변수 각각을 유전자(gene)로 간주하면 되지만, 단변수 함수에서는 유전자를 어떻게 encoding 할 지 고민해야 한다. 논문들을 보면 실수를 string으로 encoding해서 유전자로 사용했었다. 하지만, 당시에도 컴퓨터가 기본적으로 모든 숫자들을 binary로 encoding해서 사용하고 있는데 또 다시 encoding하는 것이 굉장히 불합리하다고 생각했다. 흠, 그래서 이 문제도 해결하고 보다 일반적으로 함수 최적화 문제를 풀 수 있는 GA를 만들어 보기로 했다.

GA는 매우 단순하면서도 효율적인 최적화 알고리즘이다. TSP(Travelling Salesman Problem: 영업사원이 n개의 도시를 순차적으로 방문 후 돌아오는 최단 경로 문제로 n! 갯수의 거리계산이 필요)와 같은 NP-hard한 조합 최적화 문제도 빠른 시간 안에 준 최적(suboptimal) 경로 조합을 찾아낼 수 있어서 많이 활용되기 시작했다. GA는 구현하기도 쉬워서 장난감으로 갖고 놀기에 좋은데, 장난감 치고는 더 대단한 일을 할 수 있는 놈이다. 목적 함수와 주요 독립 변수만 알고 있다면 대부분의 경우 전역 최적값(global optimum)에 근접한 해를 구할 수 있기 때문이다. 목적 함수에 대한 제약 조건(constraints)들이 있다면 더더욱 정확한 최적값을 얻을 수 있다. 이것은 과거의 전통적인 최적화 기법들과는 상반되는 것들이다. 즉, 함수의 연속성, 미분 가능성, 단극성(unimodality) 등 전통적인 최적화 기법들이 요구하는 제약사항들을 GA가 모두 극복할 수 있기 때문이다. 가령, 인공신경망을 학습시키려면 cost/loss function에 대한 미분 가능 여부가 걸림돌이 된다. GA 관점에서는 복잡한 인공신경망 목적 함수를 최소화하는 weights 값들을 구하는 문제로 귀결된다. 더구나 인공신경망에서 항상 문제가 되는 local minima에 대한 문제도 GA가 해결해 줄 수 있다. 사실, 이 부분도 소시적에 시도해 보고 싶었던 것 중의 하나였다. 인공신경망을 GA로 학습시키는 것 말이다. 혹시나 해서 구글링해 보니, 최근까지도 연구가 진행되고 있다. Reinforcement Learning에서도 학습 시키기 위해서 미분 가능하지 않은 목적 함수들을 채용할 수 있다는 점에서 매우 고무적이다. 인공신경망을 GA로 학습시킬 수 있다면 Deep Learning에도 굉장히 큰 변화를 가져올 것이다. 학습 시간을 줄이는 것은 물론이고 다양한 cost function을 사용할 수 있을 것이기 때문이다. 또한, real-time dynamic learning까지 가능할 수도 있다.

사실, 실생활에서 단변수 목적 함수를 사용할 일은 거의 없다. 흔히 사용되는 1차(1st order 또는 linear) 최소 제곱(자승)법(Least Squares Method/Regression)도 2변수 목적함수를 최적화하는 문제가 된다. 편미분을 이용해서 주어진 데이터를 가지고 최적의 직선 방정식(y = ax + b)을 구할 수 있다. 가령, 날짜별 코로나 신규 확진자 추이 데이터를 가장 잘 반영한 직선 방정식을 전통적인 최적화 기법으로 쉽게 구할 수 있다는 야그다. 하지만, 이 직선으로 내일 신규 확진자가 몇명일지 추정하기는 쉽지 않을 것이다. 시간별 확진자 수는 비선형적으로 증가하기 때문이다. 즉, 고차(higher order/non-linear) 목적 함수에 대한 최적화 문제로 귀결된다. 목적 함수가 비선형이 되는 순간 전통적인 최적화 기법들은 많은 제약이 뒤따르게 된다. 하지만, 단변수 목적 함수는 GA를 이해하고 알고리즘 자체를 개선하는데 매우 도움이 되기 때문에 단변수 함수 최적화에 GA를 사용하는 것 자체도 의미가 있다. 우리가 함수 그래프를 그려 볼 수 있는 것은 기껏해야 독립 변수가 2개까지인 경우이다. 독립 변수가 2개이면 3차원 그래프를 보아야 한다. 3차원 그래프도 유용하지만 2차원 그래프를 보면 훨씬 쉽게 함수를 이해할 수 있다. 이것이 단변수 함수 최적화가 갖는 의미다.

Genetic Algorithm(GA)

먼저, 알고리즘 자체를 간단히 살펴 보자. GA는 찰스 다윈의 자연선택설을 모방하여, random 염색체 군에서 선택(selection) - 교합(crossover) - 돌연변이(mutation)를 통해 새로운 세대의 염색체 군을 만드는 과정을 반복함으로써 세대가 지날수록 우량 염색체만 살아 남도록 하는 알고리즘이다. 자연의 진화 방식에 내재된 최적화 기법을 모사한 진화적 알고리즘(evolutionary algorithm) 중 하나이다. 이 때문에 GA를 흔히 meta-heuristic(반 경험적) 알고리즘이라 한다. 인공신경망과 유사하게 수학적으로 해석하기도 쉽지 않고 그렇다고 경험적으로 증명되었다고 치부해 버릴 수도 없다는 의미이다. 실제 GA 구현 방법은 차이가 날 수 있지만 원리는 동일하다. 아래는 GA의 대략적인 순서다. 

1. 유전자들(genes)을 염색체(chromosome)로 encoding

2. random 염색체들로 population 생성 및 fitness(우량도/적합도; 목적 함수 계산 값) 계산

3. fitness가 높은 순(또는 cost가 낮은 순)으로 염색체 정렬

4. 우량한 염색체들을 선택 교배(mate)시켜서 새로운 세대(generation) 생성

   4-1. elite 염색체 일부 복제하여 신세대 생성

   4-2. 상위 fitness 염색체들 간 random 교합(crossover) 후 신세대 생성 및 fitness 계산

   4-3. 돌연변이(mutation)로 신세대 생성 및 fitness 계산

5. 3 ~ 4의 과정을 사전에 정한 최대 세대 수 또는 종료 조건 만족시까지 반복

참고로, 대부분의 최적화 문제들은 cost를 최소화하는 것이기 때문에 GA의 fitness를 cost로 전환하여 사용하는 것이 좋다. fitness를 최대화하는 것은 cost를 최소화하는 것과 같다. 물론 목적 함수에 -1을 곱해서 사용해도 된다. 부가적으로 GA의 용어들을 최적화 용어로 대치하자면, 유전자는 목적 함수에 영향을 주는 요인이다. 다변수 함수라면 독립변수 각각에 해당된다. 염색체는 유전자들의 결합체이다. 교배시 필요한 하나의 개체이다. 다변수 함수에서는 최적 해의 후보 값 vector가 된다. 이 독립변수 vector 조합으로 목적 함수에 의해 fitness 값을 계산할 수 있게 된다.

GA에서는 난수(random number)들이 중요한 역할을 한다. 초기 염색체 population이 GA가 최적 해를 찾는데 큰 영향을 준다. 최적해의 후보를 탐색하는 관점에서 보면 가능한 모든 범위에서 균일한 난수가 생성되는게 좋다. 이 들이 대표 선수가 되어 좋은 유전자를 후대에 물려주게 된다. 하지만, GA 자체는 빠른 알고리즘이기 때문에 여러 번 돌려 보는게 더 나을 수도 있다. GA의 가장 큰 단점은 알고리즘 종료 조건을 설정하기 어렵다는 것이다. 처음엔 모두 다른 염색체들로 시작했는데 세대가 늘어날수록 우량 염색체가 다수를 차지하게 된다. 수렴하다가 더 좋은 값으로 바뀔 수도 있기 때문에 세대간 목적함수 값을 비교하기 어렵다. 목적함수 평균값에 대한 오차나 우량염색체 비율 등이 종료조건 후보가 될 수는 있지만 실제 돌려 보면 최대 세대수를 정해 놓고 돌리는게 더 나을 경우가 많다. 이것은 돌연변이를 사용해야 하기 때문에 발생하는 문제이다. 다른 최적화 알고리즘들과 마찬가지로 GA에 영향을 주는 매개 변수들이 있다. population 염색체 개체 수, crossover 확률, mutation 확률, 최대 세대 수, 탐색 구간 같은 것들이다. 좋은 방법은 처음엔 부정확하지만 빠르게 GA를 한번 돌려서 suboptimal 해를 구하고 나서 탐색 구간을 좁혀준 후 GA를 한번 더 돌리면 매우 정확한 값을 얻을 수 있다.

GA에서 실수형(real-number type) 단변수 및 다변수 사용

GA의 단변수는 64bit 실수를 사용하면 되므로 c++에서는 double type을 사용하면 된다. 앞서 얘기했듯이 컴퓨터는 이미 실수를 binary로 encoding해서 사용하고 있다. 우리는 이 놈이 염색체라고 보고 유전자들을 어떻게 선택 - 교합 - 돌연변이 시킬지를 알아내면 된다. 64bit encoding된 실수의 binary 형식을 알기 위해 Wikipedia를 참조할 필요가 있다.

아래는 교배(mate)함수를 구현한 것이다. size가 1일때가 Wikipedia를 참조해서 만든 단변수일 때 교배 방법이고 다변수에 대해서도 일관된 logic을 적용하였다. 너무나 간단한데 첨엔 이게 잘 돌아갈까 스스로 의심도 했지만 실제 GA를 돌려보니 단변수 함수의 전역 최적 해의 근사값을 너무도 잘 구해 내더라. 수치 해(numerical solution)로써 정확도 면에서도 손색이 없을 정도다. 참고로, Real64 type은 double과 uint64_t의 union type이다. 즉, 유전자 조작은 bit 연산으로 수행하고 fitness(목적 함수) 계산시에는 걍 double 값을 사용하겠다는 것이다. 좀 관심이 있는 사람들은 아래의 logic에서 몇가지 특이 사항을 발견할 수도 있을 것이다. 다변수의 경우엔 변수 갯수만큼 실수형 배열이나 아래와 같이 vector를 사용하면 된다.

  Chromosome mate(const Chromosome& another) {
    if(size == 1) {
      Real64 chro;
      for(int i = 52; i < 64; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) chro.i |= chromosome.i & (1 << i);
        else if(p < 1 - pMutation) chro.i |= another.chromosome.i & ( 1 << i);
        else chro.d = mutate();
        //else chro.i |= (chromosome.i ^ (1 << i)) & (1 << i);
      }
      //unsigned nan = (chro.i >> 52);
      //if(nan == 0x7ff || nan == 0xfff) chro.i ^= (1ul << 52); // NaN or INF
      return Chromosome(chro);
    }
    else {
      std::vector<double> gv;
      for(int i = 0; i < size; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) gv.push_back(xv[i]);
        else if(p < 1 - pMutation) gv.push_back(another.xv[i]);
        else gv.push_back(mutated_gene(i));
      }
      return Chromosome(gv);
    }
  }

전체 알고리즘을 구현하는 것은 별로 어렵지 않기 때문에 관심이 있는 사람들은 직접 구현해 보길 권한다. 흠, 나는 자주 바퀴를 다시 발명하기를 권하는데 일반적으로는 권장하지 않는 가이드이다. 하지만 고집하는 이유는, 자신이 만든 것에 사람들은 애착을 느끼게 되고 이것이 삶이나 행동에 큰 변화를 줄 수 있다는 믿음 때문이다. 더구나 직접 만들어 보면 남의 것을 사용하던 때와 굉장히 다르다는 것을 깨닫게 된다. 기존의 바퀴에 개선의 여지가 여전히 많다는 것도 자연스럽게 깨칠 수 있다. 이런 것은 누가 가르쳐 줄 수도 없는 것들이다. 

GA 테스트 결과

아래 그래프는 단변수 목적 함수인 y = (x^4 + 2*x^3 - 3*x^2 + 13)^2 - 5를 구글링해서 Firefox로 capture 한 것이다. 흠, 우연히 그래프를 우클릭했는데 capture 기능을 발견해서 당장 써먹는다.

이 함수의 전역 최소값은 아래 그래프에서 GA가 72번째 세대에서 수렴한 [x', Cost'] = (-2.188332, -4.63122) 값과 거의 일치함을 알 수 있다.

이 함수말고도 주기 함수나 불연속 함수 등 몇가지 단변수 함수의 전역 최소값 구하기를 GA로 돌려 보았는데 너무도 잘 찾을뿐 아니라 값들도 상당히 정확하다. 주기 함수의 경우 범위에 대한 constraint를 주면 더 정확한 x 값을 찾아낸다.

독립변수가 2개인 경우까지는 그래프 구글링을 통해 대략 최적값이 맞는지 확인할 수 있다. 아래는 Rosenbrock 함수로 알려진 z = 100*(x^2-y)^2 + (1-y)^2 함수를 구글링한 것이다. 전역 최소값 [x', y', z'] = (1, 1, 0) 또는 (-1, 1, 0)이다. 이 놈은 local minima에 빠져서 global 최소값을 찾기 어려운 놈으로 테스트하기 좋은 2변수 함수이다. 구글링해보면 이놈을 어떻게 보는게 좋을지도 고민하게 되는 상당히 난감한 놈이다. 이 놈을 GA로 돌려 보면 초기 난수 분포에 따라 최종 결과가 달라지긴 하지만 전역 최소값에 근사한 값들을 어려움없이 잘 찾아낸다.

간단한 데이터를 가지고 GA로 linear regression을 해 보니 대체로 잘 된다. 변수 범위를 지정하면 편미분으로 구한 정확한 값과 거의 일치하더라. 구글링해 보니 고차(higer-order) regression 문제도 GA로 해결한 사례들이 꽤 있더라.

3변수 이상 다변수 목적함수인 경우에도 GA를 많이들 써먹고 있다. GA 테스트는 할 수 있지만 결과가 맞는지는 남들이 구한 최적 값과 비교해야 하는 난감함이 따른다. 구글링해서 한가지 돌려 봤는데 잘 맞더라. 흠, 아무튼 이제 Deep Learning에 GA를 테스트할 일이 남았는데 언제쯤 할지는... Deep Learning 분야는 상대적으로 학습이 잘됐는지 확인할 수 있는 방법들이 있어서 오히려 편할 수 있다. 

참고로, 3변수 이내에서는 population 크기를 1000으로 하고 1000세대까지 웬만한 PC에서 돌려도 거의 1분 내에 답을 찾을 것이다.