이제는 지역 탐색이라고 불리는 테크닉에 대해서 함께 알아보도록 하겠습니다. 지역 탐색은 영어로는 Local Search라고 하고요. 실제로는 Local Search 방법이 매우 많이 활용이 되고 있습니다.
여러분이 요즘 많이 듣고 있는 딥러닝이라는 기술도 딥러닝 모델을 학습하는 과정에서 Local Search 방법을 아주 적극적으로 활용을 하고 있고요.
그래서 실제로는 아주 많이 사용 방법이다. 이렇게 이해하시면 되겠고요. 그래서 Local Search를 언제 활용하느냐?
이런 경우를 한번 보시면 많은 경우에 목적까지의 path가 중요하지는 않고, 그냥 목적을 달성하는 그 자체가 중요한 경우가 매우 많습니다.
물론 지금까지 우리가 살펴본 루마니아의 예제에서는 최단거리로 가는 게 당연히 좋긴 하겠지만,
예를 들어서 여러분이 체스 게임을 탐색 문제로 한번 정의를 해본다고 하면 물론 체스도 마찬가지로 최단수를 둬서 상대방을 제압하는 게 좋긴 하겠지만,
많은 경우에는 이기는 것, 그러니까 상대방의 왕을 잡는 것. 그거 자체가 목적이 되겠죠.
그런 경우에는 path cost를 고려한다기보다는 goal에 도달하는 그것에 더 집중을 한 그런 문제라고 볼 수 있겠습니다.
그래서 저희가 이 예제에서는 다음 슬라이드에 이제 소개가 될 텐데, n-queens 문제라는 게 있습니다.
그래서 자세한 내용은 다음 슬라이드에서 더 자세히 말씀을 드리도록 하겠고요.
그래서 지금 말씀 드린 대로 goal 자체를 찾는 게 중요한 경우, 그 경우에는 지역 탐색 방법을 많이 활용을 한다는 거고요.
기본 아이디어는 이와 같습니다.
제가 현재 어떤 state에 있다고 할 때 내가 어떤 액션을 취해서 바로 갈 수 있는 인접한 state들 중에 지금 내 state보다 낮다고 판단되는 데가 있으면 그거를 그냥 취하겠다는 겁니다.
그러니까 여러분이 문제를 풀 때 goal까지의 거리, 아주 global한 reasoning을 통해서 문제를 해결하겠다는 게 아니라,
그냥 매 state에서 ‘지금 보다 더 나은 state로만 가 보자.’ 그런 식으로 하나하나씩 가는 방법이 Local Search Algorithms이라고 할 수 있겠습니다.
그렇게 함으로써 여러 가지 장점이 있는데 그중에 가장 대표적인 2개를 살펴보면, 일단은 메모리를 매우 적게 필요로 한다는 것이죠.
그러니까 현재 state만 기억을 하고 있고요. 그리고 현재 state에서 주변 state 정도로 탐색을 하면 되기 때문에 메모리가 훨씬 적습니다.
현재 state에서 2번 스텝을 갔을 때 어떻게 될 것이냐? 이런 것까지 고려하지 않고 그냥 바로 내가 갈 수 있는 인접한 노드들만 탐색을 해나가겠다. 그게 기본 아이디어라고 할 수 있고요.
그리고 실제로 저희 문제들 중에서 Search space 혹은 State space가 엄청나게 큰 문제들이 많이 있는데요.
그래서 그런 문제를 전역적으로 global하게 분석을 하기 위해서 정말 많은 시간 계산이 필요할 텐데,
그런 과정을 다 없앰에도 불구하고 많은 경우에 꽤 괜찮은 솔루션을 얻게 된다. 그런 실질적인 장점이 있다고 할 수 있겠습니다.
그래서 좀 전에 말씀드린 n-queens 문제에 대해서 좀 더 깊이 말씀드리도록 하겠습니다.
여러분이 체스의 룰을 아실 수 있고, 모르실 수도 있지만, 그중에 queen(왕비)라는 말은 가로 혹은 세로로 어디든지 이동할 수 있고요. 또 대각선으로도 움직일 수가 있습니다.
그래서 그런 queen이 n개가 있다고 가정을 해보시면 되겠고요. 그래서 현재 판은 n × n 보드가 있습니다. 이 example에서는 가로 넷, 세로 넷, 그래서 4 × 4 보드라고 할 수가 있겠죠.
4 × 4 보드 안에 queen, 그러니까 왕비 말을 4개를 놓습니다. n개를 놓는 거죠.
우리의 목적은 무엇이냐 하면 queen이 서로 공격하지 않는 마지막 goal을 도달해보자. 그게 n-queens 문제의 목적이라고 할 수 있겠습니다.
여기에서 보시면 첫 번째 example에서 보시면 이 queen과 이 queen은 서로 대각선에 있기 때문에 얘네들은 서로 공격을 하게 되죠.
이런 게 하나도 없는 상태로 말을 놓아 보자. 이게 n-queens 문제라고 정의할 수 있겠습니다.
그래서 만약에 이런 문제 같은 경우에 조금 전에 말씀드렸다시피 물론 최단거리로 이런 배열을 찾는 게 중요하다고 할 수 있지만,
많은 경우에는 배열을 찾는 것 자체가 되게 도전적이고, 그것을 도달하는 것 자체가 어렵기 때문에, 그거 자체가 목적인 경우가 매우 많다고 할 수 있습니다.
이 경우에는 Local Search, 지역탐색 방법을 활용해서 해를 구할 수가 있습니다. 그래서 첫 번째, 지역탐색 아이디어 중에서 Hill-Climbing Search라는 거를 말씀드리도록 하겠습니다.
그러니까 지역탐색 방법은 여러 가지가 있는데요. 그중에서 가장 간단한 Hill-Climbing Search라고 불리는 방법에 대해서 말씀을 드리도록 하겠습니다.
제목에서 알 수 있다시피 이거는 일종의 언덕을 올라가는 그런 과정을 모사를 해서 만들어진 탐색 방법이라고 할 수가 있겠고요.
첫 번째 문장은 Hill-Climbing Search의 아이디어를 비유와 함께 설명한 것입니다. 그러니까 여러분이 에베레스트 산을 올라가는 것입니다.
현재 매우 깊은 안개 안에 있는 것입니다. 그러니까 여러분이 멀리 볼 수는 없고요. 바로 주변, 발 앞에서 앞뒤로 1m 정도만 볼 수 있는 상황이죠.
그런 상황이고, local하게만 볼 수가 있고요. 여러분이 global하게는 볼 수 없는 상황을 얘기를 하고 있습니다.
그리고 또 하나 중요한 가정 중에 하나는 기억상실증에 걸린 거죠.
그러니까 여러분이 내가 이 위치를 기존에 왔었는지, 안 왔었는지는 모르고 제가 그 state에서 주변만 보고 그다음 state로 가고 그거를 반복한다는 것입니다.
그래서 만약에 재수가 없는 경우에는 제가 있었던 곳으로 다시 돌아오는 그런 경우도 있겠지만, 그거까지 고려를 하지 않는다는 것입니다.
그래서 지역탐색의 기본 철학 중 하나가 말씀드렸다시피 메모리를 최대한 적게 활용하자는 게 목적이었기 때문에
우리가 지금까지 온 모든 path에 대해서 다 기억을 하는 거는 그것조차도 어려운 문제가 꽤 많다는 것이죠.
그래서 여러분이 에베레스트 산을 완전히 시야가 확보되지 않은 상태에서 올라간다고 하면 그냥 여러분 주변에서 경사가 제일 높은 곳으로 한발, 한발씩 올라갈 수밖에 없겠죠.
그거와 같이 지역탐색을 수행하는 과정을 Hill-Climbing Search라고 얘기를 합니다.
여기에서는 또 다른 얘기로는 Steepest ascent라는 얘기를 합니다. 그러니까 가장 급한 쪽으로 올라가겠다. 그렇게 이해를 하시면 되겠고요.
여러분이 만약에 Optimization, 최적화 문제를 푸는데, 여러분이 최적화의 목적함수를 최대화하고 싶다. Maximization 하고 싶다.
그런 경우에는 여러분 주변에 있는 neighbor들 중에 그 목적함수 값이 가장 높은 노드로 가게 되겠죠. 그러니까 그와 같이 반복하는 방법을 Steepest ascent라고 합니다.
그리고 Greedy local search라고 불리는데, 여기에서 Greedy라는 얘기는 여러분이 문제를 길게 탐색하지 않고
바로 내가 지금 취할 수 있는 행동들 중에 가장 좋은 행동을 취하는 방법을 Greedy search라고 하는데,
여기 설명한대로 goal까지 어떻게 갈지, 그리고 내가 이 액션을 취하고 이후에 무슨 일이 벌어질지는 전혀 고려하지 않고 그냥 단순히 가장 좋은 이웃으로만 가겠다. 이와 같이 불리게 됩니다.
그래서 Hill-Climbing Search는 개념 자체는 매우 간단하지만, 한 가지 치명적인 단점이 있습니다. 우리가 만약에 Maximization 하는 문제를 푼다고 했을 때, local maxima에 빠질 수 있다는 것입니다.
여기에서 local maxima는 지역적으로 최댓값을 가지는 영역이라고 보시면 됩니다. 여기에 지금 우리의 목적함수에 대한 그림이 있는데요.
여기 global optimum, global maximum이라고 불리는 포인트가 어떻게 보면 우리 문제에서 최적의 솔루션이라고 할 수가 있죠.
예를 들어서 저희가 지금 보여진 현재 위치에서 Steepest ascent 혹은 Hill-Climbing 아이디어를 활용한다고 그러면
계속 왼쪽, 오른쪽을 봤을 때 값을 증가시키는 방향인 이쪽으로 계속 올라가다가 결국에는 Local Search에 머무르게 되겠죠.
그래서 많은 경우에 Hill-Climbing Search를 할 때는 여러분이 initial point를 어디로 잡느냐에 따라서 결과가 매우 달라집니다.
여러분이 만약에 이 포인트에서 initial point를 찾고 그다음에 Hill-Climbing을 한다고 하면 여러분이 global maximum에 도달할 수 있겠죠.
그 외에 shoulder라는 영역은 평평한 영역인데, 여기 왼쪽은 더 낮은 곳이고, 오른쪽은 더 높은 곳이고요.
flat local maximum이라고 불리는 부분은 local maximum이긴 한데, flat한, 평평한 영역을 얘기를 합니다.
그래서 Hill-Climbing Search는 되게 간단하고 많은 경우에 좋은 솔루션을 주긴 하지만 이런 local maximum, local optimum에 빠지는 문제가 생길 수도 있다고 이해하시면 되겠습니다.
그래서 Hill-Climbing Search를 n-queens 문제에 대해서 한번 적용해보도록 하죠. 그래서 여기에서는 더 어려운 8-queens Problem입니다. 그러니까 총 8 × 8의 그리드가 있고요.
그리고 총 8개의 여왕 말이 배열이 되어 있습니다.
그래서 저희의 목적은 뭐냐? 저희의 목적은 얘네들이 서로 공격하지 않는 그런 배열을 찾는 게 저희의 목적이고요. 그런 목적을 달성하기 위해서 우리가 h라는 변수를 정의하고요.
h는 여왕들 중에 서로 공격하는 여왕의 쌍을 보여주고 있습니다.
그래서 우리가 global minimum이다. global optimal point다. 그 영역은 목적을 만족하는, 그러니까 h가 0이 되는 상황이겠죠.
서로 공격하는 여왕 쌍이 하나도 없는 경우, 그게 우리가 원하는 global minimum이라고 할 수가 있겠습니다.
그런데 예를 들어서 우리가 처음에 문제 시작하기에 앞서서 이렇게 initial state로 queen이 random하게 배치가 되어서 이와 같이 주어졌다고 한번 가정을 해보죠.
이 상황에서는 h가 지금 17입니다. 그래서 이 한 쌍이 지금 서로 공격하고 있고요. 이 한 쌍이 공격하고 있고, 얘와 얘가 서로 공격하고 있고.
이런 식으로 여러분이 하나하나씩 세 나가다 보면 총 17개의 쌍이 서로 공격하고 있다. 이렇게 보실 수가 있습니다.
그래서 우리가 이 주어진 상황에서 서로 공격하는 쌍이 하나도 없는 상태까지 한번 탐색해보자. 이게 현재 문제라고 할 수가 있고요.
Hill-Climbing에서의 기본 아이디어는 지금 저희가 이렇게 8개의 말이 있는데, 이 8개의 말 중에 하나를 움직였을 때 h 값 가장 많이 떨어지는 그 말을 한번 찾아보자는 것입니다.
그러니까 여러분이 8개의 조합을 다 고려하는 게 아니라, 그냥 이 주어진 상황에서 내가 8개 중에 어떤 애를 어디로 옮겼을 때 가장 h값이 크게 줄어드느냐?
그런 식으로 하나하나씩 찾아가는 과정입니다.
그래서 여러분이 이 과정을 계속 반복을 하다 보면 아까 주어진 initial state에서는 최대로 도달할 수 있는 경우가 h가 1인 경우입니다.
그러니까 perfect solution, 그러니까 서로 공격하는 퀸이 하나도 없는 그 상황까지 도달할 수가 없고요.
여러분이 local search를 하다 보면 가장 최선으로 도달할 수 있는 상황이 이와 같은 상황입니다. 그래서 여기에서는 총 한 쌍의 서로 공격하는 queen이 있고요.
8개 중에 어떻게 움직이든 간에 h값을 줄일 수 있는 배열은 존재하지 않게 됩니다. 그래서 이게 장점과 단점을 같이 보여주는 예제라고 할 수 있습니다.
장점은 아주 간단하고요. 단점은 여러분이 어디에서 시작하는지에 따라서 최적의 솔루션에 도달하지 못하는 경우도 있다. 그렇게 이해를 하시면 되겠습니다.
이 단점을 해결하기 위해서 나온 local search 방법 하나가 Simulated Annealing Search입니다. 그러니까 Annealing이라는 거는 ‘담금질’이라고 해석이 되는데요.
많은 경우에 금속을 강도를 높이기 위해서 가열을 했다가 급격히 식혔다, 가열을 했다가 급격히 식혔다 이 과정을 반복하게 되는데,
거기에서부터 아이디어를 얻어서 제한된 방법이다. 이렇게 보시면 되겠습니다.
그래서 key idea는 뭐냐 하면, 우리가 Hill-Climbing 방법에서는 제가 각 스텝마다 움직일 수 있는 액션들 중에서 무조건 제 objective를 최대화하는 그런 모션을 했다고 한다면,
여기에서는 중간 중간 현재 상태보다 좋지는 않지만 안 좋은 move를 허락을 하는데,
그 안 좋은 move를 허락하는 빈도를 처음에는 크게 줬다가 가면 갈수록 그거를 줄여주는 그런 방식이라고 보시면 되겠습니다.
그래서 조금 전에도 살펴보셨다시피 Hill-Climbing Algorithms 같은 경우에는 결코 downhill을 하지 않죠. 얘는 항상 올라가기만 합니다.
그렇지만 Simulated Annealing에서는 가끔 내려가기도 한다는 것이죠. 그래서 이런 식으로 무조건 올라가기만 한다면 local maximum에 빠지는 문제가 있었고요.
그래서 Simulated Annealing의 기본 아이디어는 Hill-Climbing을 따르긴 하지만 동시에 random walk, 그러니까 가끔 더 좋은 솔루션이 아님에도 불구하고 무작위로 움직이겠다는 얘기입니다.
그래서 이런 식으로 무작위성을 넣는 게 많은 경우에 local maxima를 피할 수가 있다. 이렇게 이해하시면 되겠고요.
그래서 이거에 대한 Intuition을 말씀드리기 위해서 gradient descent, 그러니까 아까는 gradient ascent였죠.
가장 좋은 방향으로 올라가는 예제였는데, 여기에서는 우리 목적 함수가 최소화하는 경우입니다. 그래서 가장 급하게 내려가는 그런 예를 한번 보도록 하죠.
여러분이 위에서 볼을 떨어뜨렸는데, 면에 여러 가지 범프가 있어서 얘가 잴 수가 없으면 local minimum에 빠지게 되는 거죠.
지역적으로 움푹 들어간 곳에 빠지게 되는 것입니다. 그런 상황을 한번 가정해봤을 때 여러분이 random하게 전체 판을 이렇게 흔들 수 있다고 가정을 해보시죠.
그러면 local minimum에 빠져 있는 공이 튕겨져 나올 수가 있을 텐데요. 그런 상황을 유사하게 생각해보실 수가 있을 것입니다.
그래서 공을 떨어트리는데 우리가 판을 가끔 흔들 수가 있고요. 그런데 처음에는 많이 흔들다가 가면 갈수록 점점 흔드는 빈도를 줄여나가자. 그게 기본 아이디어라고 할 수가 있고요.
그래서 조금 전에 말씀드린 담금질 아이디어랑 유사성을 보자면 처음 시점은 온도가 높은 시점이고요. 시간이 많이 지난 시점은 온도가 낮은 시점으로 이렇게 가정을 합니다.
그래서 처음에는 온도가 높았다가, 그래서 온도가 높았을 때는 이런 randomness가 더 많이 들어가 있다가, 온도는 시간이 지나면 지날수록 저희가 계속 낮춰줍니다.
낮춰주면서 온도에 따라서 randomness가 결정이 되는 것이죠.
그래서 뒤에 아주 간단한 Algorithms이 주어져 있고요. 하나하나씩 보도록 하겠습니다.
여기에서의 기본 아이디어는 뭐냐 하면 가끔 best move를 선택하는 대신에 random move를 가끔 선택을 하게 되고요.
그리고 만약에 그 move가 현재 상황보다 낫다고 하면 그 move를 통해서 이동한 state를 받아들이고요.
만약에 그게 안 좋다고 그러면, randomness를 통해서 받아들이든지, 안 받아들이든지 그것을 결정하게 됩니다.
그래서 이 Algorithms을 하나씩 보시면 input으로서는 문제와 schedule이 주어져 있고요.
여기에서 보여드린 Algorithms은 pseudo code라고 해서 아주 엄밀하게 만든, 그러니까 Simulated Annealing을 구현하기 위해서 아주 엄밀하게 설계된 Algorithms이 아니라, 개념 위주로 보여드린 거다.
이렇게 보시면 되겠습니다. 그래서 문제가 주어졌고, scheduling 아이디어가 주어진 것입니다.
이 schedule이라는 건 제가 계속 iteration을 통해서 탐색을 해나갈 텐데, 그 iteration마다 온도를 어떻게 줄여나갈지 그거에 대한 함수다. 이렇게 보시면 되겠습니다.
그래서 local variables은 현재 노드, 다음 노드 그리고 온도를 나타내는 t가 주어져 있고요. t는 조금 전에도 말씀드렸다시피 시간이 가면, iteration이 진행되면 진행될수록 점점 낮아지는 값입니다.
그래서 결국에 중요한 for roop 안을 한 번 보도록 하죠. 여기에서 t라는 거는 iteration을 나타내는 값이고요. iteration을 계속 반복하게 됩니다.
그래서 조금 전에 말씀드린 대로 현재의 t값, 그러니까 온도 값을 어떻게 결정하느냐는 temperature의 schedule에 따라서 결정이 됩니다.
그래서 조금 전에도 말씀드렸다시피 schedule이라는 함수를 여러분이 input으로서 주어져야 되는데 그러니까 얼마나 급하게 온도를 낮춰갈지는 여러분이 결정해야 될 문제입니다.
그래서 만약에 t가 0까지 가면 이제 더 이상 탐색을 그만 하고 끝내는 것입니다. 그러니까 이 scheduling 과정에서 몇 번의 iteration을 돌고 탐색을 그만 둘지를 결정을 해야 된다는 것이고요.
그리고 현재 state에서 random하게 다음 state를 결정을 합니다. 그리고 그다음 state의 값과 현재 state의 값의 차이를 delta E라고 정의를 했습니다.
그래서 만약에 delta E가 0보다 크다. 그러면 무슨 뜻입니까? 제가 random으로 next state를 정했는데, 거기에서의 값이 현재의 값보다 더 크다는 거고, 그거는 더 좋다는 거죠.
그런 경우에는 무조건 accept를 합니다. 그러니까 delta E가 0보다 클 때는 제가 이런 식으로 random으로 선택한 다음 state를 현재 state로 만들어버린다.
그러니까 그쪽으로 이동하겠다. 그 얘기고요.
delta E가 0보다 작은 경우가 문제겠죠. 그러니까 delta E가 작다는 거는 현재보다 random으로 선택한 다음 state가 더 안 좋다는 겁니다.
그렇다고 해서 무조건 버리는 게 아니라, 특정 확률을 가지고 받아들일지, 안 받아들일지를 결정을 하겠다는 겁니다.
그래서 이런 exponential 함수를 통해서 정의를 하는데요. 이 경우에는 언제 더 받아들일 확률이 높아지느냐? 그래서 delta E가 클 경우에는 항상 받아들이는데, 중요한 거는 delta E가 작은 경우죠.
그러니까 제가 다음 next state로 옮겼을 때 목적함수의 값으로 떨어지는 경우입니다. 이 경우에는 주어진 확률 분포 값으로 선택을 하게 되는데요.
여기 보시면 exponential 함수 위에 delta E 나누기 t라는 식으로 정의가 되어 있습니다.
그런데 이 수식의 의미를 말씀을 드려 보면 이게 언제 받아들일 확률이 줄어드는지 하면 delta E의 절대 값이 클 경우, 혹은 temperature가 낮은 경우입니다.
delta E의 절대 값이 크다는 거는 무슨 얘기냐 하면, 지금 여기 else문에 들어왔다는 거는 delta E가 항상 마이너스라는 거죠.
마이너스인 상황에서 절대 값이 크다는 거는 내가 그다음 state로 갔을 때 value의 감소가 아주 크다는 겁니다.
그러니까 value의 감소가 크면 클수록 받아들일 확률을 줄여주겠다는 거고요. 또 하나 중요한 parameter는 온도 t인데요. t가 낮을수록 받아들일 확률이 적어집니다.
t가 낮아진다는 거는 iteration이 계속 진행이 돼서 점점 t가 낮아지는 상황이기 때문에, 이 수식을 통해서 처음에는 bad move임에도 받아들일 확률이 높다가,
가면 갈수록 bad move는 받아들일 확률이 떨어지는 그거를 이런 식으로 구현했다고 보실 수가 있겠습니다.
그래서 Simulated Annealing에 대해서 개략적인 Algorithms을 말씀을 드렸는데요. 이 기본 Algorithms을 통해서 다양한 변화들이 있습니다.
Algorithms마다 조금 조금씩 다르긴 하지만 전체 철학은 이대로 따라간다고 보시면 되겠고요.
Local Search, 지역탐색이라는 Algorithms은 어떻게 보면 하나의 큰 Algorithms 그룹을 말씀을 드리는 거고,
이번 시간에는 Hill-Climbing 방법과 Simulated Annealing 방법을 말씀드렸지만, 그 외에도 훨씬 다양한 Algorithms이 있습니다.
유전자 Algorithms이라든지, 그 외에 여러 Algorithms이 존재하게 되고요.
혹시 관심 있으신 분은 이것을 기반으로 해서 좀 더 찾아보시고 공부해보시면 더 유익한 인공지능 공부가 되지 않을까 이렇게 생각을 합니다. 그러면 오늘의 강연은 여기에서 마치도록 하겠습니다.