인공지능의 기초 - 휴리스틱 탐색

Informed(Heuristic) Search

문제에 추가적으로 주어진 휴리스틱 정보(Heuristic information)를 활용하여

각 노드의 평가함수(Evaluation function)를 만들고 그에 따라 확장에 우선순위를 두는 Tree Search 전략이다.

휴리스틱(Heuristic)

불충분한 시간, 정보로 인해 합리적인 판단이 불가능 할때, 과거의 경험이나 사회적 통념 등을 활용한 직관적인 판단을 하는 간편 추론법. 이때, 즉각적인 판단 기준이 되는 정보가 휴리스틱 정보(Heuristic Information)

휴리스틱 함수(Heuristic function), f(n)

휴리스틱 정보를 이용해 노드 n부터 목표노드까지의 최소경로비용의 예상치를 정의한 함수.

평가함수(Evaluation function), f(n)

출발노드로부터 노드 n을 거쳐서 목표노드까지 가는 최소경로비용에 대한 예측치를 정의한 함수.

대표적인 Informed Search 전략들

• Greedy best-first search
• A* search

Greedy best-first search

어떤 프린지 노드가 목표노드까지 가장 최소경로비용을 가질까?

평가함수 : f(n) = h(n)

장점 : 해를 가장 빠르게 구할수 있다.

단점 : Optimality를 보장 못한다.

-> 두가지 이유가 있다.

1. 휴리스틱 함수값과 실제 최소경로비용과의 차이

휴리스틱이 알려주는 예상값의 우선순위가 실제 경로비용값 우선순위와 다르다면 최적해를 찾아가기는 더욱 힘들어진다.

2. 평가함수에 해당 노드까지의 경로비용이 무시되어있다.

서로다른 프린지 노드까지의 경로비용의 차이가 휴리스틱으로 무시 못 할만큼 크다면 휴리스틱으로 만든 우선순의는 의미가 없어진다.

-> 그렇다면 어떤 조건에서 Optimality를 보장할까?

1. 휴리스틱 함수의 예측값 = 실제값.

우선, 적어도 휴리스틱 함수값이 실제 최소경로비용과 일치시켜야 겠다.

자, 모든 노드의 휴리스틱 함수값이 실제 최소경로비용과 같은 문제에서 어느 시점에 프린지 노드 n이 확장되어졌다 하자.

⇒ 노드 n은 1개 이상의 다른 프린지노드 q와 f(q) ≧ f(n)를 만족하거나, 유일한 프린지 노드이다.

⇒ n부터 f(n)을 지불해 목표노드에 도달가능함.

(∵ n으로 부터 도달 가능하지 않다면, 목표노드까지의 경로조차 없는데 실제 최소경로비용이 존재한다는 모순이 생긴다.)

⇒ n은 목표노드이거나 1개 이상의 자식노드 m 생성할것이다.

⇒ Step cost는 0이상 이므로, f(n) ≧ f(m) 이다.

⇒ q가 존재한다면, f(q) ≧ f(n) ≧ f(m) ⇒ f(q) ≧ f(m)이다.

⇒ q가 존재하면 f(q) ≧ f(m)이므로 다음에 m이 확장되고, 존재하지 않는다면 프린지 큐에 m밖에 없으므로 m 중 하나가 확장되게 된다.

∴  확장된 각 노드는 자신의 자식노드로만 확장하게된다.

귀납적으로, 휴리스틱 함수값이 실제값과 같을때, 확장은 시작노드부터 목표노드까지 자신의 자식노드로만 이루어지게 되어서, 목표노드까지 도달할때까지 오로지 보다 깊은 레벨로만 확장해나가게 된다.

2. step cost가 모두 일치.

휴리스틱 함수값이 실제값과 같아도 올바른 판단을 할 수 없는것은 그 노드까지의 경로비용을 고려하지 않아서인데, 이제는 형제노드끼리만 비교하면 된다. 즉, step cost의 차이를 반영 안해도 판단오류가 없게만 하면 된다.

 

이제, 어떤 문제에서 휴리스틱 함수값이 실제값과 같고, 실제 최소비용경로상의 2개이상의 자식노드를 가진 노드 n이 있다고 하자.

그렇다면, n의 자식노드중 임의의 서로다른 노드인 m과 k에대해 다음이 성립한다.

1. { R(m) ≦ R(k) } ⇔ { f(m) + S(m) + f(n) ≦ f(k) + S(k) + f(n) }

(R(x)는 출발노드부터 노드 x를 거쳐서 목표노드까지 가는데 드는 실제 최소경로비용, S(x)은 노드 x로 뻗어있는 에지의 step cost)

2. { S(m) - S(k) ≦  f(k) -  f(m)  }  ⇒ { R(m) ≦ R(k) }, from 1.

3. ¬{ R(m) ≦ R(k) } ⇔ ¬{ f(m) + S(m) + f(n) ≦ f(k) + S(k) + f(n) }, from 1.

4. { R(m) > R(k) } ⇔ { f(m) + S(m) + f(n) > f(k) + S(k) + f(n) }, from 3

5. { S(m) - S(k) > f(k) -  f(m) }  ⇒ { R(m) > R(k) }, from 4.

∴  S(m) - S(k)와 f(k) - f(m)의 대소관계가 R(m)과 R(k)의 대소관계와 같다.

그렇다면, 휴리스틱 함수값이 실제값과 같을때 부모노드가 최소비용경로상에 있고 형제노드가 하나이상 있는 어떤 노드 A가 있다고 하면, A가 다음을 만족할때 최소비용경로를 벗어나게 된다.

[ ∀B, { f(A) ≦ f(B) }] ⋀ [ ∃B, { S(A) - S(B) > f(B) - f(A) } ]

(B는 A의 형제노드)

반면, 다음을 만족할때는 최소비용경로로 진행하게 한다.

[ ∀B, { f(A) ≦ f(B) }] ⋀ [ ∀B, { S(A) - S(B) ≦ f(B) - f(A) } ]

( ∵ [ ∀B, { S(A) - S(B) ≦ f(A) - f(B) } ] ⇒ [ ∀B, { R(A) ≦ R(B) } ])

이때, 모든 step cost가 같아져버리면,

1. ∀B, { S(B) - S(A) = 0 }

2. [ ∀B, { f(A) ≦ f(B) }] ⇒ [ ∀B, { f(A) - f(B) ≦ 0 }]

3. [ ∀B, { f(A) ≦ f(B) }] ⇒ [ ∀B, { f(A) - f(B) ≦ S(B) - S(A) }], from 1,2

4. [ ∀B, { f(A) ≦ f(B) }] ⇒ [ ∀B, { S(A) - S(B) ≦ f(B) - f(A) }], from 3

5. [ ∀B, { f(A) ≦ f(B) }] ⇒ [ ∀B, { f(A) ≦ f(B) }] ⋀ [ ∀B, { S(A) - S(B) ≦ f(B) - f(A) } ]

∴  모든 step cost가 같아지면, ∀B, { f(A) ≦ f(B) }를 만족하는 A에 대해, [ ∀B, { f(A) ≦ f(B) }] ⋀ [ ∀B, { S(A) - S(B) ≦ f(A) - f(B) } ]는 항상 참

따라서, 휴리스틱함수값이 실제값이고 step cost가 모두 같으면, 알고리즘은 최소비용경로로만 진행하게 된다.

A* Search

출발노드부터 어떤 프린지 노드를 통하는 경로가 목표노드까지 가장 최소경로비용을 가질까?

평가함수 : f(n) = g(n) + h(n)

g(n) : 출발노드로부터 노드 n까지의 실제 최소경로비용. 노드를 생성할 때마다 갱신해 나간다.

장점 : 대체로 Optimal한 해를 구한다.

-> 허용적 휴리스틱을 사용하는 경우, Optimality를 보장.

단점 : 그리디 알고리즘보다 느리고 자원 소모가 조금 더 있을수 있다.

-> g(n)을 유지하기위한 오버헤드가 발생.

허용적 휴리스틱(Admissible Heuristics)

항상 실제 최소경로비용이하의 예측치를 가지는 휴리스틱 함수.

왜 Admissible Heuristics을 사용하면 Optimality가 보장될까?

임의의 최적해가 아닌 목표노드 G₀이 막 Enqueue된 상황에서 다음이 성립하게 된다.

h(G₀)=0 , f(G₀) = g(G₀)

이때, 최적해인 G₁으로가는 프린지노드 N도 존재할거고 다음이 성립한다.

f(G₀) = g(G₀) > g(G₁) = f(G₁) ≧ f(N), ∵ g(G₁) - g(N) ≧ h(N)

따라서, 무조건 다음에는 노드 N이 확장되어진다.

결국, 최적해가 아닌 목표노드로는 확장할 수가 없어 결국 최적해를 구하게 된다.