[인공지능 튜링 테스트에서 딥러닝까지] 탐색

안녕하세요. jiogenes입니다.

저번시간에 현재의 인공지능은 특정 문제를 해결하기 위한 도구로 활용된다고 살펴보았습니다. 특정 문제라는 것은 산업에서 일어나는 거창한 문제들도 있지만 우리가 일상에서 맞딱뜨리는 상황들도 모두 문제로 볼 수 있습니다. 가령 갑자기 지도교수님과 미팅을 해야되는 문제가 있을 수 있지요. 또 제안서를 쓰면서 직접비와 간접비 그리고 인건비와 재료비 등을 계산할 때 각각의 항목들을 총액에서 얼마나 분배할지 정하는 문제도 있습니다. 지도교수님과의 미팅 문제는 미팅 주제에 대한 부분을 잘 정리하고 설명할 수 있는 방법을 찾는 탐색으로 해결할 수 있습니다. 과제비 계산 문제는 제약조건을 만족하는 최적화 방법으로 해결할 수 있습니다. 그렇다면 인공지능에서 특정 문제를 어떻게 정의하며 문제를 풀기위한 방법은 무엇이 있을까요? 이번 시간에는 인공지능에서 문제 정의와 풀이 방법으로서 탐색과 최적화에 대해 알아보겠습니다.

상태 공간 탐색

상태 공간 탐색은 문제의 해가 될 수 있는 상태들의 집합을 상태 공간으로 간주하고 최적해를 찾기 위해 상태 공간을 찾아보는 방법을 의미합니다. 여기서 상태(state)는 특정 시점에 문제가 처해있는 모습이고 상태 공간(state space)는 초기 상태로부터 도달할 수 있는 모든 상태들의 집합을 의미합니다. 상태 공간은 문제의 해가 될 가능성이 있는 모든 상태들의 집합입니다. 그리고 이러한 상태 공간을 상태를 노드(node), 노드 사이에 간선(edge)를 추가하여 상태 공간 그래프를 그릴 수 있습니다.

탐색의 대표적인 문제는 강건너기 문제, Tic-Tac-Toe, 8-Puzzle, 8-Queen, Traveling Salesperson Problem(TSP) 등이 있습니다. 이러한 문제들을 푸는 여러가지 방법들에 대해 알아보겠습니다.

맹목적 탐색

맹목적 탐색(Blind Search)이란 상태 공간 정보를 이용하지 않고 항상 정해진 순서에 따라 상태 공간 그래프를 생성해 가면서 해를 탐색하는 방법을 말합니다. 가장 단순 무식한 방법이지만 가장 직관적으로 떠올릴 수 있고 컴퓨터가 가장 하기 쉬워하는 방법이라 할 수 있습니다. 맹목적 탐색에는 깊이 우선 탐색, 너비 우선 탐색, 반복적 깊이 심화 탐색, 양방향 탐색 등이 있습니다.

깊이 우선 탐색

깊이 우선 탐색(Depth First Search, DFS)은 초기 노드에서 시작하여 깊이 방향으로 계속해서 탐색 합니다. 목표 상태의 노드를 찾다가 더 이상 깊이 들어갈 수 없으면 이전 노드로 돌아와 자식 노드를 확장하고 확장한 자식 노드를 다시 깊이 방향으로 탐색을 진행합니다. 이렇게 뒤로 돌아오는 방법을 백트레킹(backtracking)이라고 합니다. 한 번 방문한 노드는 재방문 하지 않으며 목표 노드를 찾을 때 까지 반복합니다. DFS는 목표 노드가 없는 경로는 메모리에 올려놓을 필요가 없으므로 메모리 공간에 대한 비용이 상대적으로 적다는 장점이 있습니다.

깊이 우선 탐색 : 탐색 순서대로 번호가 적혀있습니다. [출처:위키]

너비 우선 탐색

너비 우선 탐색(Breadth First Search, BFS)은 자식 노드를 확장하여 목표 노드를 찾고 목표 노드가 없으면 또다른 자식 노드를 확장하여 목표 노드를 탐색합니다. 자식 노드를 전부 확장한 후에도 목표노드를 찾지 못했다면 단말 노드에서 자식 노드를 확장하는것을 반복합니다. BFS는 DFS와 달리 확장한 노드를 계속 기억하고 있어야 더 깊이 확장할 수 있기 때문에 메모리 공간에 대한 비용이 큽니다. 하지만 목표 노드를 찾게 된다면 목표 상태에 도달하는 최단 경로를 찾을 수 있다는 장점이 있습니다.

너비 우선 탐색 : 탐색 순서대로 번호가 적혀있습니다. [출처:위키]

반복적 깊이심화 탐색

DFS는 메모리 비용이 적지만 최단 경로를 찾는다는 보장이 없고, BFS는 메모리 비용이 크지만 최단 경로를 찾을 수 있다는 것을 보장합니다. 반복적 깊이심화 탐색(Iterative Deepening Depth First Search, IDDFS)은 앞선 두 개의 탐색 방법의 장점을 같이 활용할 수 있습니다. IDDFS는 기본적으로 DFS를 하지만 탐색 깊이 한계를 1씩 증가시켜 가면서 DFS를 실행합니다. 따라서 실제 BFS 보다 약간 더 많은 (약 11%) 노드를 생성하지만 메모리 비용을 줄이면서 최단 경로를 찾을 수 있습니다. IDDFS는 맹목적 탐색 방법중에 가장 먼저 고려해보는 방법 중 하나입니다.

반복적 깊이심화 탐색 : 깊이 별로 DFS를 진행하고 해당 깊이에서 찾지 못하면 깊이를 늘려서 다시 DFS를 진행합니다. 약간의 비효율성이 있지만 메모리 효율성이 더 높으므로 좋은 성능을 보입니다. [출처:저서]

정보이용 탐색

맹목적 탐색은 전체 상태 공간이 한정적이고 계산 가능한 영역에 있을때 사용 가능합니다. 알고리즘 문제로 나오기 적합하지만 실생활에 적용하기는 힘듭니다. 체스나 바둑과 같은 상태공간이 큰 문제로 가버리면 컴퓨터 메모리에 다 담을 수 없을만큼 상태 공간이 커지기 때문입니다. 그래서 상태공간에 대한 정보를 이용해서 탐색 효율을 높이는 방법을 사용하는데 이를 정보이용 탐색(Informed Search)이라 합니다. 정보이용 탐색은 대부분 휴리스틱을 사용하기 때문에 휴리스틱 탐색이라고도 합니다.

휴리스틱

휴리스틱(heuristic)은 라틴어의 “heuristicus” 와 그리스어 “heuriskein” 에서 파생되어 “찾아내다(find out)” 그리고 “발견하다(discover)” 라는 의미를 가집니다. 인공지능에서 휴리스틱이란 시간과 정보가 불충분해서 합리적인 판단을 할 수 없거나 굳이 합리적인 판단이 필요 없는 경우에 신속하게 판단하기 위한 어림짐작을 뜻합니다.

탐색의 목표는 어떤 노드를 확장해야 목표 노드로 빨리 도달할 수 있는지 판단하는 것입니다. 그래서 일반적으로 탐색에서 휴리스틱이란 현재 상태에서 목표 상태까지의 거리를 어림짐작으로 계산하는 것을 의미합니다. 휴리스틱 방법은 항상 최적해를 찾는다는 보장하지 않습니다. 하지만 상태 공간이 큰 실생활 문제에 최적해를 항상 찾을 수 있는 맹목적 탐색 방법을 사용하는 것은 거의 불가능 하기 때문에 휴리스틱 방법을 주로 사용합니다. 휴리스틱 방법도 맹목적 탐색과 같이 어떤 휴리스틱을 사용하는가에 따라 성능차이가 크게 나타날 수 있습니다.

언덕 오르기 방법

언덕 오르기 방법(Hill Climbing Method)은 휴리스틱에 의한 평가값이 가장 좋은 상태 하나만 선택해서 확장해 나가는 방식입니다. 이 방법은 현재 상태에서 도달 가능한 이웃 상태만 고려하기 때문에 지역 탐색이라고도 부릅니다. 휴리스틱을 사용하기 때문에 휴리스틱 탐색(Heuristic Seach)이라고도 불리고 가장 좋은 것만 선택하기 때문에 탐욕 알고리즘(Greedy Search)이라고 부르기도 합니다. 언덕 오르기 방법은 국소 최적해(local optimal solution)에 갇혀서 전역 최적해(global optimal solution)를 찾지 못하는 경우가 생깁니다. 초기 상태가 정해져 있지 않다면 초기 상태를 바꾸어 가면서 언덕 오르기 방법을 여러번 적용해서 전역 최적해를 찾을 수 있습니다.

언덕 오르기 방법 : A부분에서 언덕 오르기 방법을 사용하면 국소 최적해에 갇히고 B부분에서 언덕 오르기 방법을 사용하면 전역 최적해를 찾을 수 있습니다. [출처:저서]

최상 우선 탐색

최상 우선 탐색(Best First Search)은 확장된 노드 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 방법입니다. 이 때, 남은 거리를 측정하는 방법을 정확히 알 수 없으므로 휴리스틱을 사용합니다. 이 방법은 확장 중인 노드와 목표 노드간의 거리를 얼마나 잘 짐작할 수 있는가에 따라 효율이 결정됩니다.

최상 우선 탐색 : 목표 상태까지의 거리가 제자리에 있지 않은 타일의 갯수일 때 자식 노드 중에서 가장 거리가 짧은 노드를 선택하여 확장합니다. [출처:저서]

빔 탐색

최상 우선 탐색을 하는 경우 깊이가 깊어짐에 따라 확장한 노드의 수가 기하급수적으로 많아질 수 있기 때문에 메모리 관리 비용이 큽니다. 빔 탐색(Beam Search)은 평가값이 가장 좋은 일정한 갯수의 노드만 기억하면서 최상 우선 탐색을 진행합니다. 따라서 최상 우선 탐색에 비해 메모리 비용을 아낄 수 있습니다.

빔 탐색의 빔은 광선을 뜻하는데 어두컴컴한 밤에 광선을 비추면 그 부분만 빛나는 것 처럼 탐색 시 우수한 특정 갯수의 노드만 기억한다는 의미입니다.

빔 탐색 : 가장 좋은 2개의 노드만 기억하는 빔 탐색의 예시 [출처:geeksforgeeks]

A* 알고리즘

이때까지 살펴본 문제들은 특정 상태에 도달하기 위한 문제들이었습니다. 하지만 어떤 문제는 목표 상태를 찾아가는 것 뿐만 아니라 소요되는 비용이 가장 적은 경로를 찾는 문제일 수도 있습니다. 이러한 문제는 어떤 노드 $n$을 경유하는 전체 경로에 대한 비용 $f(n)$을 초기 노드부터 현재 노드 $n$까지의 이미 투입한 비용 $g(n)$과 현재 노드 $n$에서 목표 노드까지의 남은 비용 $h(n)$의 합으로 나타낼 수 있습니다.

\[f(n) = g(n) + h(n)\]

A* 알고리즘은 전체 비용이 최소인 노드를 확장해 가면서 탐색하는 방법입니다. 그런데 이 때, 남은 비용 $h(n)$을 정확히 계산할 수 없으므로 휴리스틱을 사용합니다. 남은 비용 $h(n)$을 대신하여 휴리스틱 함수 $\hat{h}(n)$을 사용하여 전체 비용 추정함수 $\hat{f}(n)$을 정의합니다.

\[\hat{f}(n) = g(n) + \hat{h}(n)\]

A* 알고리즘에서 사용하는 휴리스틱 함수 $\hat{h}(n)$이 항상 실제 남은 비용 $h(n)$ 보다 작거나 같으면 $\hat{h}(n)$이 허용성을 갖는다고 할 수 있습니다. 허용성을 갖는 휴리스틱을 사용하는 A* 알고리즘은 항상 최적해를 찾는다는 것이 증명되어 있습니다. [링크] 하지만 실제 남은 비용에 대한 휴리스틱 함수는 사람이 직접 생각해 내야 하고 이것이 A* 알고리즘의 성능을 결정하기 때문에 허용적 휴리스틱을 발견하기란 쉽지 않습니다.

8-퍼즐 문제에 A* 알고리즘 적용 : 각 노드의 왼쪽편에 있는 수식의 왼쪽 항이 $g(n)$, 오른쪽 항이 $h(n)$. 자식노드 중 $f(n)$이 가장 작은 노드를 선택합니다. [출처:저서]

게임 탐색

인간의 활동은 모든것이 게임이라고 봐도 무방합니다. 이전의 경제학자 및 수학자들은 게임이론을 통해서 인간 행동을 예상할 수 있을거라 생각했습니다. 세계와 상태를 규칙을 통해 한정짓는 게임은 컴퓨터 공학에서도 컴퓨터가 인간을 능가할 수 있는 문제로 여겼으며 탐색 방법을 통해 이를 해결하고자 많은 노력이 있었습니다.

mini-max 게임 트리

체스, 장기, 바둑과 같이 차례(turn)가 있는 게임은 서로 번갈아 가면서 진행합니다. 이런 게임을 잘 하는 사람들은 상대방의 수와 나의 수를 가능한 많이 생각한 후 최적의 해를 찾아 수를 놓습니다. 게임에서 이렇게 수를 앞서 보는 것을 탐색의 트리 형태로 표현할 수 있고 깊이에 따라 서로의 차례가 정해집니다. 이러한 트리를 게임 트리라 부릅니다.

승패가 갈리는 시점까지 수를 본다면 자신이 이겼을 때 +1점, 자신이 졌을 때 -1점, 비겼을 때 0점을 줘서 상태 노드들에 값을 부여할 수 있습니다. 모든 단말 노드에 값이 부여된다면 부모 노드로 올라가서 부모 노드의 차례가 자신의 차례라면 가장 높은 값을 가지는 노드를 선택할 것이고 상대방의 차례라면 가장 낮은 값을 선택할 것입니다. 이 과정을 루트 노드까지 반복해서 진행하면 루트 노드에서 자신이 선택할 수를 결정할 수 있습니다. 이 때, 해당 깊이의 노드가 자기 자신이라면 항상 최대값을 선택하기 때문에 MAX 노드라고 하고 상대방이라면 항상 최소값을 선택하기 때문에 MIN 노드라고 합니다.

하지만 일반적으로 승패가 결정되는 시점까지 수를 보기 어렵기 때문에 특정 깊이까지 수를 본 뒤에 유리한 정도를 판단하는 휴리스틱을 사용합니다. 특정 깊이까지 수를 본 후 휴리스틱으로 현재 착수 상태를 평가한 다음 역으로 올라가면서 각 노드들이 자신의 차례에 따라 최대값과 최소값을 선택합니다. 마지막으로 루트노드(자기 자신)에서 최대값을 가지는 노드를 선택합니다. 이러한 알고리즘을 mini-max 알고리즘이라 합니다.

mini-max : 말단 노드에서 휴리스틱 값이 정해지면 각 차례에 맞게 min, max를 정하고 루트 노드에서 가장 자식 노드(-7)를 선택합니다. [출처:위키]

$\alpha - \beta$ 가지치기

mini-max 알고리즘은 깊이가 제한된 BFS처럼 모든 단말노드에 대한 게임트리 전체를 기억하고 있어야 합니다. 때문에 메모리 관리 비용이 크고 불필요한 부분을 탐색하느라 메모리를 낭비할 수 있습니다. 이 문제점을 보완한 알고리즘이 $\alpha - \beta$ 가지치기 알고리즘 입니다. 이 알고리즘은 처음에는 mini-max 알고리즘과 같이 특정 깊이까지 DFS를 진행하고 해당 깊이에 도달하면 휴리스틱을 통해 단말 노드들의 평가값을 계산합니다. DFS 탐색 과정 후 백트레킹을 통해 MIN 노드로 돌아갈 경우 자식 노드 중 최소값을, MAX 노드로 돌아갈 경우 자식 노드 중 최대값을 선택하여 노드값을 업데이트 합니다.

그런데 만약 MIN 노드의 현재 값이 부모 노드(MAX 노드)가 가진 값보다 작거나 같다면 MIN 노드의 자식 노드들을 더 이상 탐색할 필요가 없습니다. 왜냐하면 MIN노드는 항상 최소값만 선택하기 때문에 자식 노드를 더 확장하여 탐색하더라도 지금보다 더 큰 값을 가질 수 없기 때문입니다. 이렇게 MIN 노드에서 탐색을 중지하는 것을 $\alpha-$자르기 라고 합니다.

마찬가지로 MAX 노드의 현재 값이 부모 노드(MIN 노드)가 가진 값보다 크거나 같다면 더 이상 부모 노드의 값을 줄일 수 없으므로 탐색을 중지합니다. 이를 $\beta-$자르기 라고 합니다. 이와같이 $\alpha - \beta$ 가지치기 알고리즘은 DFS 방식으로 게임트리를 생성하여 메모리 공간도 줄이고 $\alpha-$자르기와 $\beta-$자르기를 통해 탐색 공간도 줄일 수 있습니다.

$\alpha - \beta$ 가지치기 : 맨 왼쪽 가지치기에서 4를 가진 MIN 노드는 뒤에 아무리 많은 자식 노드가 있더라도 4를 넘을 수 없으며, 부모 노드는 이미 5를 가지고 있기 때문에 뒤의 자식들을 더 볼 필요가 없습니다. [출처:위키]

몬테카를로 트리 탐색

mini-max 알고리즘과 $\alpha - \beta$ 가지치기 알고리즘은 단말 노드를 평가하기 위해 휴리스틱을 사용하는데 이러한 평가값을 어림짐작으로 계산하는 것은 매우 어려운 일입니다. 체스와 바둑의 현재 착수 상태를 보고 판단할 수 있는 공식이 있었다면 신의 한수와 같은 드라마틱한 일은 거의 일어나지 않을 것입니다. 이러한 휴리스틱 함수를 사용하는 대신에 무작위 시뮬레이션으로 직접 결과값을 보고 상태를 결정하는 알고리즘이 몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)입니다. 평가하고 싶은 단말 노드의 형세가 유리하다면 무작위 시뮬레이션을 돌렸을 때 이기는 횟수가 많을 것이고, 불리하다면 무작위 시뮬레이션을 돌렸을 때 지는 횟수가 많을 것입니다. 즉, MCTS는 무작위 시뮬레이션의 결과값을 단말 노드의 평가값으로 사용하고자 하는 방법입니다.

MCTS는 선택, 확장, 시뮬레이션, 역전파 과정을 반복하여 게임 트리를 구성합니다.

선택 단계에서는 어떤 자식 노드를 확장할지 선택합니다. 자식 노드는 현재까지의 승률(이긴 횟수/총 방문 횟수)이 높은 것과 지금까지 방문 횟수가 적은 것을 우선하여 선택합니다. 우선순위를 정하는 식은 UCB(Upper Confidence Bound)라는 식을 사용합니다.

\[UCB = \frac{Q(n_i)}{N(n_i)} + C \sqrt{\frac{2log N}{N(n_i)}}\]

위 식에서 $N(n_i)$는 자식 노드 $n_i$를 경유한 전체 게임 수, $Q(n_i)$는 $n_i$를 경유한 게임 중에서 이긴 횟수입니다. 따라서 $\frac{Q(n_i)}{N(n_i)}$는 $n_i$를 경유한 게임의 승률이라고 할 수 있습니다. 그리고 $N$은 전체 게임 횟수를 나타내고, 따라서 $\sqrt{\frac{2log N}{N(n_i)}}$는 $n_i$를 적게 방문할수록 커집니다. 상수 $C$는 승률과 방문횟수를 얼마나 반영할지 정하는 역할을 합니다.

선택 단계에서는 UCB 함수를 통해 루트 노드로 부터 값이 가장 큰 수에 해당하는 노드로 계속 내려갑니다. UCB 값이 가장 큰 노드가 아직 만들어져 있지 않으면 해당 노드에서 확장 단계로 진행한다.

확장 단계에서는 선택 단계에서 마지막에 도달한 노드에 새로운 노드를 추가할 수 있습니다. 확장 단계로 진입한 해당 노드가 특정 조건(일정 방문 횟수 이상 방문 등)을 만족한다면 이 노드를 트리에 추가합니다. 조건을 만족하지 않아도 해당 노드에서 시뮬레이션 단계로 넘어갑니다.

시뮬레이션 단계는 노드의 형세를 평가하기 위해 승패가 결정될 때까지 무작위로 게임을 진행합니다. 시뮬레이션을 진행할 때 최적의 수를 계산하는 것은 시간과 비용이 너무 많이 들기 때문에 게임 규칙에 맞는 수를 무작위로 돌리거나 휴리스틱 방법을 이용해 빠르게 계산하는 방법으로 진행합니다.

역전파 단계는 시뮬레이션의 결과로 나온 승패 정보를 현재 노드부터 루트 노드까지 경로 상의 모든 노드들의 승패 정보를 업데이트 합니다.

MCTS 방법은 게임에서 이기기 위한 다음수를 결정하기 위한 방법으로 루트 노드의 자식 노드들에 대한 평가값을 결정하고 평가값이 좋은 다음 노드를 선택하는 것입니다. 평가값은 승률 뿐만 아니라 방문 횟수, 방문 횟수와 승률 모두를 사용할 수도 있습니다. MCTS는 컴퓨팅 자원이 충분하면 휴리스틱 없이도 높은 성능을 기대할 수 있습니다. 또한 조건을 만족하는 부분만 트리로 구성하고 나머지는 시뮬레이션으로 대체하기 때문에 메모리 요구량도 높지 않다는 장점이 있습니다. 또한, 이미 구성된 트리를 다음 착수때 활용할 수 있다는 것도 MCTS의 장점 중 하나입니다.

몬테카를로 방법(Monte Carlo method) 반복된 무작위 추출(repeated random sampling)을 이용하여 함수의 값을 근사하는 알고리즘을 부르는 용어이다. 몬테카를로(Monte Carlo)라는 용어는 맨해튼 계획에 참여하고 있던 니콜라스 메트로폴리스가 맨해튼 계획이 끝나가던 1947년에 제안한 이름이다. 맨해튼 계획 당시 그의 동료였던 폴란드 출신 수학자 스타니스와프 울람에게는 삼촌이 있었는데, 그는 모나코의 유명한 도박의 도시 몬테카를로에서 도박을 하기 위해 친척들의 돈을 종종 빌려갔다. 몬테카를로 방법 또한 무작위성이 있으므로 이로부터 이름이 유래된 것이 지금까지 이어져 내려왔다. - Wiki

MCTS : 선택, 확장, 시뮬레이션, 역전파 과정을 보여줍니다. [출처:저서]

제약조건 만족 문제

제약조건 만족 문제는 주어진 제약조건을 만족하는 해를 찾는 방법입니다. 탐색의 관점에서 제약조건 만족 문제를 바라볼 때 목표 상태는 모든 제약조건을 만족하는 상태를 뜻합니다. 제약조건을 만족하는 상태를 찾는 탐색 방법으로는 백트레킹 탐색 방법과 제약조건 전파 방법이 있습니다.

백트레킹 탐색 방법

백트레킹 탐색 방법(backtracking seach)은 DFS처럼 변수에 허용되는 값을 차례대로 대입해 보는 방법입니다. 대입한 후 제약조건을 만족하지 않는다면 뒤로 돌아가서 다음 허용되는 값을 대입하고 이것을 목표 상태를 찾을 때 까지 반복합니다.

4-퀸 문제에서 백트레킹 탐색 방법 : 초록색 선은 제약조건을 만족할때, 빨간색 선은 제약조건을 만족하지 않을때 사용됩니다. 모든 자식 노드가 제약조건을 만족하지 않으면 백트레킹을 수행합니다. [출처:저서]

제약조건 전파 방법

제약조건 전파 방법(constraint propagation)은 인접 변수간의 제약조건에 따라 각 변수에서 제약조건을 만족하지 않는 변수들을 제거하는 방법입니다.

4-퀸 문제에서 제약조건 전파 방법 : 위 그림의 위쪽 상태의 경우 제약조건을 만족하지 않는 변수를 없애면 C열에 가능한 변수가 없습니다. 아래쪽 상태의 경우 모든 제약조건을 만족합니다.[출처:저서]

이상으로 탐색 방법에 대해 전반적으로 살펴보았습니다. 쓰다보니 너무 길어져서 최적화 방법은 다음 시간에 살펴보도록 하겠습니다. 여기서 나온 문제 해결 방법들을 하나씩 찾아보고 더 깊게 음미해보는 시간을 가져보시길 바랍니다. 감사합니다.