[인공지능 : AI, Artificial Intelligence] Lecture 6 : Search 3부

Lecture 6

문제를 tree로 표현, state와 action으로 구성되어있으며, 이를 이용해서 Search를 한다.

근본적으로는 다 똑같다고 한다만...

best first search의 흐름은 똑같지만, 각 node의 값은 g, h, g+h에 따라서 UCS, GBFS, A*인지 구분된다.

A*의 completeness와 optimality

A* search는 completeness와 optimality를 보장하는 조건이 있다.

A* is optimal if h(n)is admissible, while the graph-search version of A* is consistent

admissible heuristic is that never overestimates the cost to reach the goal.

h*(추정값) = h(실제값 g랑 같은 수준. 두 state간의 g값 차이)

h* <= h이면, admissible하고, 따라서 optimal하다

우리가 본 대부분은 보장된다.

8 puzzle에서의 admissibile

real h = 실제로 원위치 시키는 데에 필요한 단계의 수
h1 = 잘못 배치된 숫자의 개수
무조건 h1 < real h이므로, admissible하다.

마찬가지로,
h2 = 각 숫자의 goal postion까지의 거리의 총합
무조건 h2 < real h이므로, admissible하다.

admissible에 대한 약간의 증명

Goal state인 G1과 G2가 있다고 하자.
Best first search이므로, G1을 향해서 가게 될 것이다.
그 중간의 node n에서는, f = h* + g를 조건으로 갖추게 되는데,
여기에서 h* <= h, 즉, 실제 cost인 g보다 무조건 h*가 더 작으므로,
G2로 나아가지 않고 n이 있던 방향으로 그대로 진행하게 된다.

즉, Best first Search면 무조건 왼쪽으로 돌입하게 된다.

이 때, Best-First Search 중, heuristic function을 사용하면서 admissibility condition을 만족하면 A* 알고리즘이다.

전체 흐름은 Best-first search로 not hill climbin로 진행하므로, h*<=h이기만 하면 completeness, optimality 보장.

a,b,c모두 맞다. 놀랇게도 b가 맞다!

4장

Local Search

좋은 heuristic을 스스로 만들게 한다.

3장에서는 solution is a sequence of actions

local search에서는 state space와 initial state에서의 gola까지의 path를 찾는 것이 아니라, solution state를 찾는 것이 중요하다.
simulated annealing, genetic algorithm

3장 : initial state와 goal state가 주어지고, state space에서 path를 찾는다.

4장 : initial state와 goal state같은 것 없다. 각 node의 utility값이 주어진다. 평가값.

주어진 시간동안 가장 최선의 노드를 찾고자 한다. good enough 일 수도 있다.

space가 너무 커서 sequential하게 찾는 것이 불가능할 때 도입한다.

주어진 시간동안 제일 좋은 근사해를 내놓는 것

---

노트

best goal이 불분명, path 안중요 등등...

예시

goal state로의 path를 찾는 것과 state with higher value를 찾는 것을 비교하자.

열자리의 password를 찾아보자.

약 60가지의 글자가 있는데, 총 경우의 수는 60^10

이런 문제에서는 각 state를 tree로 표현할 수 없다. path를 찾는 것이 아니기 때문이다.

그래서 candidate solution의 obj function을 각각 확인한다.

정답과 얼마나 가까운지는 알수 있다. goal에 얼마나 가까운지에 관한 점수, utility가 있다. obj function라고도 한다.

나를 중심으로 local에서 가장 좋은쪽으로 이동하는 것을 반복. 이런 알고리즘이 greedy hill climbing.

그럼 어떤 전략을 쓰면 더 좋은 쪽으로 갈까???

• greedy hill climbing
• local bean
• sim area
• genetic algorithm

Hill Climbing = Greedy

global maxima를 찾는 것이 목표이다.

local maxima를 피해야한다.

random으로 위치를 시작하고, 더 좋은쪽으로만 계속 옮겨가는 알고리즘이다.
local maxima를 벗어날 수 없다.

Greedy 전략...

시작을 여러곳에서 여러번 해본다. random하게 = random restart.
이런식으로 global maxima를 얻는다.

hill climbing
random restart
parallel climbing

그외에는
local beam search
simulated annealing
genetic algorithm

exploitation : 실행(더 좋은 쪽으로 가보겠다.) hill climbing은 100% 이것만한다.
exploration : 탐험(더 좋은 곳은 아니지만, 더 멀리에 더 좋은 보상이 있을 것이라 기대하고 하는 것)

이 둘을 어떻게 더 잘 조합할 것인가가 중요하다.

신경망에 대해서 대입해서 본다면,
각 weight값의 조합을 state, 그리고 목표와의 차이를 obj function = loss라고 둔다.

강의노트 보충

Admissible Heuristic

admissible heuristic은 true cost to reach the goal을 overestimate하지 않는다.
즉,

$$
h^*(n) \leq h(n)
$$

여기서 $h^*(n)$는 추정치이고, $h(n)$는 true cost이다.

A* Optimality

만약 h(n)이 admissible하다면, A*는 optimal하다.
아래는 그 증명이다.

so A* will never select Gs during the search and hence A* is optimal.

아래 세 이미지 모두 같은 내용을 설명하는 것이다.

아래 사진은 UCS와 A*를 비교하는 내용이다.

A*의 criteria

• Complete : Yes
• Time : exponential
• Space : Keeps every node in memory
• Optimal : Yes

A*는 goal을 향해서 bias 되어있다. 따라서 적은 수의 node를 거친다.
더 좋은 heuristic을 사용할수록 더 적은 영역을 explore한다.

Dominance

모든 n에 대해서 h2(n) >= h1(n)라면, h2는 h1을 dominate한다.
그리고 search에 있어서 더 좋은 성능을 보인다.
예를 들면...

admissible heuristics ha, hb가 있다고 하자. 이 때,

$$
h(n) = max(ha(n),hb(n))
$$

은 admissible하며, ha, hb를 dominate한다.

아래는 실제로 node의 생성 수나, 유의미한 branching에 대한 factor를 계산한 것이다.

다음은 각 Heuristic에 따른 Search의 결과를 나타낸다.

여기서 consistent(일관성)하다는 말은 다음과 같다.

휴리스틱 함수 h(n)이 일관성이 있다는 말은, 모든 n노드와 그의 어떤 행위를 통해서 생성된 자식노드(Successor) n'에 대해서,
노드 n에서 Goal에 도달하는 추정 비용은 노드n에서 노드n'까지 가는 실제 비용과 노드 에서 Goal에 도달하는 추정 비용을 합한 것보다 작다와 같다. 이 어려운(?) 말을 수식으로 표현하면 아래와 같은 식으로 표현된다.

$$
h(n) \leq c(n,a,n') + h(n)
$$
단, $c(n,a,n')$는 n노드에서 n'노드까지 드는 실제 경로 비용

모든 Consistent Heuristic 또한 Admissible 하기 때문에 Consistency가 Admissible 보다 좀더 엄격한 요구조건이 따른 다는 것을 알 수 있다.

Summary

We can organize the algorithms into pairs where the first proceeds by layers, and the other proceeds by subtrees.

(1) Iterate on Node Depth:

• BFS searches layers of increasing node depth.
• IDS searches subtrees of increasing node depth.
  (2) Iterate on Path Cost + Heuristic Function:
• A* searches layers of increasing path + heuristic function.
• IDA* searches subtrees of increasing path cost + heuristic function.

Which cost function?

• UCS searches layers of increasing path cost.
• Greedy best first search searches layers of increasing heuristic function.
• A* search searches layers of increasing path cost + heuristic function.

Local Search