1. Informed Search Strategies
큐속의 노드의 순서를 결정하기 위해서 evaluation function을 적용.
- frontier node의 순서는 우선순위 큐로 유지.
evaluation function
1) Greedy Best-first Search
goal에 가장 가까운 노드를 Expand.
예) 경로 탐색 문제
(tree search) 평가
- finite에서 optimal, complete하지 않다. (Infinite loop가 생길수있음.)
- m이 miaximum depth of the search space라면, O(b^m)
- 좋은 heuristic function은 space와 time 복잡도를 줄일 수 있다.
Greedy best-first graph search는 finite space에서 complete하다.
Greedy Best-first Search와 Uniform-cost search의 차이?
#1 Uniform-cost search
- 위와 같은 방식으로, initial으로부터 path cost가 가장 적은 노드를 택하여 expand.
- frontier list에 중복되는 state는 path cost를 비교해서 가장 낮은 state를 남긴다.
- 이미 방문한 노드를 explored set에 넣음. (그래프 서치)
#2 Greedy Best-first Search
- 위와 같은 방식으로, heuristic function의 결과가 가장 적은 노드를 택하여 expand.
(지금까지 어떻게 왔는지 상관X)
2) A* Search
greedy best-first search와 uniform-cost search의 결합형태.
- A* tree Search
- A* graph Search
-> tree보다 graph가 노드가 적으므로, time이라던지가 적게 걸린다!
complete하긴한데, optimal인가?
#1 tree-search version of A*
h(n)이 admissible하다면, A*는 optimal을 찾을 수 있다.
(admissible의 뜻은 h(n)의 값이 goal까지의 실제 cost보다 넘지않는 형태.)
증명
- admissible하기때문에, h(G2) = 0. (게다가, goal에 도달했으니, 0이어야 한다.)
- f(G2)는 suboptimal이기 때문에, f(G2) > C*가 성립.
- f(n) = g(n) + h(n) <= C* (addimissible하기 때문에, 둘의 합은 optimal보다 작거나 같다.)
-> suboptimal인 G2를 선택하지 않는다. ( h(n)이 admissible하다면, A*는 optimal을 찾을 수 있다.)
#2 graph-search version of A*
- h(n)이 consistency해야 한다.
(consistency란, h(n) <= c(n, a, n') + h(n')인 경우.)
증명
- f(n)은 점점 증가하거나 같다.
- expand될수록 f(n)은 갈수록 커질것임.
-> 위 2사항은 h(n)이 consistent하기 때문에.
- n'을 선택하게 된다면, f(n') <= f(n). (f(n)은 점점 증가하거나 같으므로.)
- 따라서, goal node는 optimal이다!
평가
- A*는 optimal, complete하다.
- 특정한 C*라는 threshold value를 써서, 이보다 f(n)이 크면 잘라내서, 효율성을 높인다.
(C*가 minimum이 이거보다는 더 낮다.는 필요없는 부분을 줄임.)
현실
- 그렇게 줄인다고 해도 여전히 exponential!
- 좋은 heuristic을 사용하면 더 효율적이다.
2. Local Search Algorithms
모든 problem이 path로 표현할 수 있는것은 아님. (goal node가 없는 문제가 있다.)
-> 예) 8-queens problem, TSP, time table
임의의 solution을 결정한다음에, 약간씩 변화를 주면서 푼다.
매번 objective function으로 평가를 하게된다.
- attack하는 queens의 pair갯수가 function이 되고, 이를 줄여가면서 0이 되면 optimal.
1) Hill-climbing Search
"안개에서 에베레스트를 올라가는 것과 같다"
-> 전체를 못보고, 눈앞의 정도에서 찾아가는 것.
gradient ascent/descent search라고도 함.
Example) 8-queens problem
각 column당 하나씩 queen을 둔다.
Successor function에 의해서 generate되는 56개 중에서 가장 나은 state로.
(서로 어택하는 퀸의 갯수를 줄여가는 방향으로.)
Hill-climbing Search의 문제점?
- Local maximum에 갇힐 우려가 있음.
해결 방법
#1 Stochastic hill climbing
올라가는 방향으로 가는데, 제일 가파르다고 거기만 가는게 아니라, 돌아서가는게 global일 확률도 있으니,
그쪽에도 chance를 준다.
-> 가장 좋은 방법 말고도, 덜 좋은 방법까지도 선택!
#2 First-choice (simple) hill climbing
전체에 대해서 판단하는게 아니라, successor를 랜덤하게 해보는것.
-> 56개중에 하나를 선택을 하고, 그게 현재보다 낫다면 그쪽으로 감.
-> 랜덤하게 찍어서 하니까, 빠름. (해가 빨리 수렴한다고는 볼순없다. best로 가는게 아니기 때문에)
-> evaluate가 빠르다!
#3 Random-restart hill climbing
hill climbing을 여러번 하는것. 그러고 그중에서 나은것 선택.
복잡도
state-space의 shape에 달려있음.
NP-hard problems -> local maxima에 빠질 갯수가 exponential하기때문에.
restart를 사용하면, 어느정도 좋은 local maximam을 찾을수있다.
2) Simulated Annealing Search
아이디어
Efficiency of valley-desceding + completeness of random walk
"bad" moves를 허락해서, local minima를 피할 수 있도록한다.
- First-choice (simple) hill climbing와의 차이가 마지막 줄!
- T는 회를 거듭할수록 커지고, bad move로 가는 확률이 작아진다!
bad move를 느리게 할수록, conversion(알고리즘을 끝내는데까지는, 루프를 끝내는데까지는)
오래 걸리겠지만, 실제로 minimum이나 maximum을 찾을 가능성은 높아진다.
3) Genetic Algorithms
#1 Chromosome design
#2 Initialization & #3 Fitness evaluation
#4 Selection
#5 Crossover
#6 Mutation
#7 Update Generation
Overview
individual을 여러개를 생성해서 시작.
-> 각각 individual들은 alphabet이나 0과 1의 string으로 구성.
각각 individual은 fitness function에 의해서 rate된다.
-> fitness score가 높을수록 select가 될 확률이 높음.
select된 pair들은 crossover된다.
-> 처음에는 large step으로하다가, 나중에, individual이 similar갈수록 (conversion에 다다를때)
smaller step으로 전환.
그리고, mutation.
- 조금만 더가면 global찾는데, mutation이나, crossover가 나올수있으니, 그래서 조금 느림.
-> 가다가, hill-climbing같은 local search 적용하면, 조금더 빠르게 찾을수 있음.
'4학년 1학기 수업 > 머신러닝 및 응용' 카테고리의 다른 글
| [머신러닝 및 응용] CH.1 Solving Problems by Searching (0) | 2020.05.02 |
|---|
