문제 정의

Doing The Right Thing

지난 포스팅에서 가장 중요한 말이다. 인공지능을 통해 문제를 Perfermence measure(성능 측정치)가 최대가 되게 끔 푸는 것을 찾는 것이다.

그렇다면 우리는 문제를 어떻게 정해야하고 어떻게 풀어야할까?

Problem Solving

How to achieve the goal state through the complex state space form the initial state?

시작 상태에서 복잡한 상태들을 거쳐 목표로 가는 방법이 Problem Solving의 정의이다.

문제를 푸는 순서는 [ 문제 -> 모델링 -> 솔루션(알고리즘) ] 이다. 여기서 솔루션(solution)이란 answer와 다르다.

answer는 그저 말그대로 답만 있는 것이고 솔루션은 풀이과정까지 있는 것이다. CS에서는 이러한 Step by Step 과정을 알고리즘이라고 부른다. 즉, 알고리즘은 initial state에서 goal state로 가는 과정과 같다.

문제를 간단하게는 Input, Output, Solution, Perfermance measure로 나눌 수 있을 것이다.  좀 더 정확하게 구분해보자.

Problem Formulation VS. Problem modeling

여기서 Problem modeling이 Formulation보다 더 중요하지만 학부생의 범주를 넘어가기 때문에 다음 기회에 ㅜㅜ... 물론 Formulation도 중요하다!

Problem Formulation

Initial State / Successor Function / Goal test / Path cost

위와 같이 나눌 수 있다. Initial State는 시작 상태이고 Successor function은 행동들을 이야기한다. Goal test는 목표를 달성하는지, Path case는 해결한 답을 이야기한다.

그렇다면 문제를 어떻게 푸는가? A Tree Search Alg in CS!

왜 문제를 푸는 것이 Tree Search와 같은건지 의아할 것이다.

init state부터 가능한 state들을 탐색하여 말단 노드(goal)까지 가는 과정들이 Tree와 동일하기 때문이다!

즉, init state(root node)부터 가능한 state들을 child로 가지는 tree이며 탐색을 통해 goal인 터미널까지 갔을 때 문제를 푼 것이다!

또한 탐색 방법을 평가하는 데 기준이 있다.

Complete / Time complexity / Space Complexity / Optimal

Complete는 답에 도달할 수 있는 지 여부이다. Optimal은 구한 답이 Optimal 한지 체크하는 것이다.

BFS와 DFS 같은 경은 경우는 어떨까?

누가 더 빨리 Tree에서 답을 찾고 효율적으로 Tree를 확장하는 가를 따지는 것이 중요하다.

BFS는 Complete 하며 Optimal하다. 그러나 DFS는 Complete 하지 않으며 Optimal 하지 않다. 왜 일까?

BFS는 Optimal한 값을 놓칠 일이 없다. 그러나 DFS는 만약 왼쪽 child를 계속 타고 가다 보면 무한루프에 빠질 수 있으며 오른쪽으로 온다는 보장이 없다. 즉, 답을 못 찾는 경우가 생긴다.

BFS와 DFS의 중간인 IDS 기법도 있지만 성능 때문에 잘 사용하지 않는다.

위의 Tree serach말고 다른 Search를 찾아보자

Informed Search

Best-first Search / Greedy Search / A* Search / Branch & Bound Search

Informed Search에서 중요한 것은 evaluation function을 잘 정의하는 것이다! heuristic function이라고도 부른다. h(n)

Greedy Search

매순간 최적의 선택을 하는 알고리즘이다. 이를 판단할 때 적절한 제약조건이 있다면 좀 더 합리적인 선택이 가능해진다. 물론 구해진 값이 Optimal 한지 증명하는 것은 어려우며 애초에 Optimal을 보장하는 것이 아니다!

Branch & Bound Search

알고리즘 시간에 배웠지만 간단히 이야기하면 BFS방식으로 탐색하는 데 evaluation function을 정의하여 가장 기대값이 좋은 쪽으로 확장을 한다.

A* Search

대표적인 예로 Best-first Branch and Bound가 있다.

f(n) = g(n) + h(n) | h(n) <= h*(n) [admissible heuristic], When Minimize

f(n)은 노드가 가진 값이고 g(n)은 실제 가지고 있는 값, h(n)은 앞으로 가질 수 있을거라 기대되는 추정치이다!

h*(n)은 실제 구해야하는 Optimal이고 우리가 추정하는 값이 실제 구해야하는 Optimal보다 작다는 것이다. (Minimize 문제의 경우)

왜냐하면 우리가 추정하는 값이 Optimal보다 크면 Optimal을 구할 수 없기 때문이다. 우리는 가장 작은 값을 찾아야하는 데 기댓값이 크면 아무리 해도 클 수 밖에 없기 때문이다.

예를 들어 8-puzzle 문제를 푼다고 하자. 이때 우리는 h(n)을 세워서 Optimal한 Minimize된 값을 얻을 수 있을 것이다.

 실제 이동가능 여부와 관계 없이 가야하는 위치로 이동하는 횟수를 다 더한 것을 h(n)으로 나타낼 수 있다. 그 값은 무조건 Optimal한 값보다 작기 때문이다. 하지만 이뿐만 아니라 다른 h(n)이 존재할 수 있다. 바로 아직 정확한 위치에 오지 않은 타일 수를 세는 것이다.

 이렇듯 h(n)은 여러가지 나올 수 있다. 그래서 더 정확한 h(n)을 찾는 것이 중요하다. minimize한 문제에서는 0<h1<h2<h*(n) 중 h2가 더 좋다. 즉, Optimal보다는 작지만 작은 것들 중에서는 가장 큰게 제일 좋다.

 h(n)을 구하는 쉬운 방법에는 문제를 relexed시키는 것이다. 문제를 좀 더 쉬운 문제로 변형하여 푸는 것인데 이에 대한 해답은 무조건 원본 문제보다 간단할 수 밖에 없다.

 물론 A*는 뛰어난 search 방법이지만 실제로 성능이 좋지 않기 때문에 이 마저도 사용하지 않는 다고 한다...흠쓰...

Local Search : A TSP Solution

hp-hard 문제를 풀 때 자주 사용된다.

Search space : data, size / constraints : hard VS. soft / Evaluation function / Environment : time ...

자연계의 문제를 푸는 것은 굉장히 어렵다. 많은 변수와 제약조건들이 존재하기 때문이다.

 위에서 문제 -> 모델 -> 솔루션 이라고 언급한 적이 있을 것이다. 이 때 model과 solution을 각각 A,P 또는 P,A로 지정할 수 있는 데 A는 근사, P는 정확도를 뜻한다. 즉, 모델을 근사하면 솔루션은 정확해야하고 모델이 정확하다면 솔루션이 근사해도 어느정도 쓸모있다고 생각하는 것이다.

 Feasible Solution은 제약조건을 만족하는 것을 말한다. 우리는 수학적으로 풀 수 없는 것을 이 같은 Search 방법으로 풀어야하는 데 Search Space에서 Feasible Solution을 찾는 것이 Optimization이다.

자세한 설명은 다음번에 하겠다.