인공지능 과목 요약 게시물입니다
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
인공지능이라는 과목은 뭔가 새로운 발명품을 공부해서 대단한 일을 해내는 것이 아니다
인공지능 과목에서는 문제 해결을 위한 툴을 공부한다고 생각하면된다
요새 알파고, 딥러닝, 머신러닝, 빅데이터 등이 화두가 되어 인공지능이 떠올랐지만 관련 알고리즘은 이미 30년 전, 최근 기술도 5년 전에 개발이 되었다
단지 갑자기 인공지능이 떠오른 이유는 하드웨어의 발전으로 예전에 풀 수 없었던 문제들이 이제 참을만한 시간 안에 해결이 되기 때문이다
np time / np-hard problem을 시행가능한 시간 안에 풀기 위해 near solution을 찾아내는데
이 과정에서 Knwoledge(Experience)를 이용한다
그리고 Knowledge를 만드는 것이 인공지능에서 하는 일이다.
Knowledge를 축적하기 위해서 딥러닝을 시행하는데 그에 필요한 방대한 데이터가 빅데이터이다
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
□ 인공지능의 문제 해결 방법
Trial And Error => Universal Problem Solver : Finding Path from starting point to goal
□ Search => Brute-force search / Heuristic search
Brute-force search : Depth-First Search / Breath-First Search / Iterative Deepening Search
Heuristic search : For efficiency, Prediction by experience
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
□ DFS , BFS, Interative Deepnening Search
□ General Search Algorithm
DFS와 BFS는 Node들의 관계가 트리라는 가정 하에 이루어진 탐색과정이다.
그래서 Node들의 관계가 그래프가 된다면 DFS와 BFS는 infinite loop를 만들게 된다
따라서 Visited Node를 기록함으로써 infinite loop 문제를 해결하여 보편적인 Search 알고리즘을 구성한다
■ Heuristic Search
지금까지 Optimal Solution을 찾으려고 할 때 BFS를 이용해서 가장 적은 Depth(=Movement)의 Solution을 찾았는데 TSP같은 문제에서는
각 Movement의 Cost가 일정하지 않기 때문에 쓸 수 없다.
그래서 BFS 는 Uniform-Cost Search, A* 로 확장하고
DFS 는 Iterative Deepening A*로 확장한다
□ Uniform-Cost Search
Uniform-Cost Search는 Depth 대신 Cost로 단계를 만들어서 BFS를 수행한다고 생각하면 된다.
스켈레톤도 OPEN list에 큐 대신 우선순위 큐를 넣으면 된다.
다익스트라 최단거리 알고리즘과 동일하다
□ A* Search
Uniform-Cost Search로 Optimal Solution을 찾을 수 있게 되었지만 그래도 Exponential 한 time 과 space가 필요하다
그래서 기존의 Uniform-Cost Search에서 Root부터 계산했던 Cost를 Node마다 각각 미리 계산해서 가장 적은 Cost 순서대로 Search를 해나가는
A* Search를 사용하게 된다. Special Case에 대해 해결하고자 Modification이 추가되어 A*가 된다.
A* Search의 노드 v를 지나는 goal까지의 Cost는 다음과 같이 표현된다.
총 예상비용 = 노드v까지 비용 + goal으로 이동 예상비용
heuristic search의 핵심은 얼마나 효율적인 estimation을 하는가 인 것 같다.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
□ True A* Search
위에서 언급한대로 Cost 값만 바꿔서는 A* Search 알고리즘이 아니다. ①Search 알고리즘에 수정을 하거나 ② Monotonic 한 Heuristic을 만들어야 한다.
□ A* Search ( Final Version )
GeneralGraphSearch( v )
Prepare two empty lists: OPEN, CLOSED
Insert v with Coste(v) into OPEN
While forever
If OPEN is empty, return failure
while forever
v = the node with the lowest cost in OPEN
remove v from OPEN
if v is not in CLOSED // v is not visited
break
else if the new cost is cheaper than the cost of v in CLOSED
remove v in CLOSED
break
end if
end while
If v is a goal, return success
Insert v into CLOSED
Expand v
Insert all children of v with their costs into OPEN
end while
End
□ Constistency Condition
위 조건이 만족하다면 consistent heuristic , monotonic heuristic 이다.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
댓글