[인공지능] 1.인공지능 기초 용어 정리

인공지능 수업에서 자주 나오게 될 단어들의 정의에 대해서 알아봅시다.

 

Heuristic(휴리스틱)

단어는 어려워보이지만 대충 말해서 '어림 짐작하기' 입니다. 다시 말해 합리적인 판단을 할 수 없는 상황이거나 그럴 필요가 없는 상황에서 빠르게 '어림짐작의 기술' 을 사용하는 겁니다. 경험과 체험을 사용하는 시행 착오적인 방법을 사용하여 구하는 겁니다. 인공지능에서 'Heuristic'은 이미 '경험'이 있기 때문에 답에 도달하기 쉬운 상태를 의미합니다. 그 어떠한 문제에 대해서 informed 한 겁니다.

 예를 들어 GPS 시스템을 생각해보겠습니다. 만약 GPS 시스템이 목적지까지 모든 경우의 수를 구해준다면 이 시스템은 제대로 된 시스템일까요? 아닙니다. 100가지 경우의 수를 내주게 된다면 시간도 너무 오래걸리고 필요하지도 않기 때문입니다. 이렇게 소모적인 방식은 'Blind Search 방법' 이라고 합니다. 

  반면 Heuristic Search는 항상 옳고 최적화된 답을 제공하는 게 아니라 대부분 경험에 의한 규칙을 이용하는 경우가 되는 겁니다. 그래프로써 표현된 문제에 대한 특별한 정보를 이용하여 Search 를 최대한 빠르게 진행합니다. 예를 들어 GPS 시스템으로 다시 설명을 들면 현재 위치와 목표 위치를 지정하고 그 거리를 계산하고 갈 수 있는 방식을 제공합니다. 가끔 GPS 시스템이 갈 수 없는 길로 안내해주는 경험을 하신 적이 있으신가요?(저는 있는데요.) 보통은 알맞게 안내를 해주고 내가 이동할 때마다 다시 탐색 하게 하는 경험적 방법을 통해 방향성을 제공하는 겁니다. 

 

 

FIFO(선입선출)

 선입(먼저 들어간 게) 선출( 먼저 나간다) 

자료구조에서 Queue 의 개념입니다. 

은행에서 줄을 서든 먼저 서면 먼저 서비스를 받을 수 있는 개념입니다. 

 

 

LIFO(후입선출)

 후입(늦게 들어간 게) 선출(먼저 나간다)

자료구조에서 Stack 의 개념입니다. 

옷을 갤  때, 접시를 씻을 때와 같은 상황입니다. 먼저 개서 놔둔게 가장 바닥으로 가서 꺼낼 때는 가장 마지막에 쓰게 된다는 개념입니다. 

 

 

Breath-First Search(너비-우선 탐색)

 BFS 는 FIFO 큐를 사용하여 탐색합니다. 큐 앞의 첫번째 노드를 꺼내서 그 노드의 자식 노드를 큐에 삽입합니다. 이렇게 탐색을 진행합니다. 생각해보면 결과적으로 너비 기준으로 탐색 합니다. 

 

 

Depth-First Search(깊이-우선 탐색)

 깊이 우선 탐색은 이름처럼 한 노드 방향으로 쭉 내려가게 되는 탐색입니다. Stack 을 사용합니다.

 

 

Fringe

 expand 하기 원하는 노드의 집합입니다. 흔히 큐처럼 나타내집니다. 

 

 

Depth 

 Search 할 때 만들어지는 Searching tree 깊이입니다. 루트 노드 와의 거리라고도 생각할 수 있겠습니다. 

 

 

Uniform-Cost Search

 Depth의 수치보다 Cost 의 수치를 우선적으로 현재 상황에서 가장 짧은 거리에(cost 가 낮은) 있는 노드로 Expand 합니다.

 

 

Depth-limited Search

 Depth-first 에 제한을 둡니다. limit = 1이면 한 번 까지만 파고 들고 뒤로가야합니다.

 

 

Iterative Deepening Search

 순차적으로 Depth-Limit의 Limit 을 증가시킵니다.

 

 

Bidirectional Search

 Start와 Goal 에서 동시에 노드를 Expand 합니다. 'Bi' 는 양 쪽 이라는 의미죠. 가장 먼저 만나는게 솔루션이 됩니다. 즉 시작 노드와 목적지 노드 양방향에서 Search 를 진행하는 겁니다. 

 

 

F(n)

 평가함수입니다. 매개변수 n은 노드를 의미합니다. F(n) = Distance through n to the goal 

(컴퓨터에서 거리와 비용은 동일한 말입니다.) 

즉 F(n)은 n부터 Goal 까지의 비용(=거리)를 뜻하는 겁니다. 

 

- F(n) = H(n) 이면 휴리스틱 함수로만 평가를 한다는 겁니다. 

- F(n) = G(n) 이면 이는 Uniform-Cost Search 를 의미합니다. 

 

Uniform-Cost Search 에서 G(n) 도 고려하지 않으면 깊이 우선 탐색이 됩니다. 

F(n)은 문제 해결의 척도이기 때문에 굉장히 중요합니다. 

 

 

H(n)

 평가 함수의 구성 요소 중 하나입니다. 

H(n)은 노드 n에서 Goal 노드 까지 가장 짧은 거리를 추측해보는 겁니다. 

 

 

G(n)

 평가 함수의 구성 요소 중 하나입니다. 시작노드부터 노드 n까지의 Path Cost 입니다. 

 

 

Greedy Best-Fit Search

 평가함수가 오직 H(n)인 검색 방법, 최적화가 아닐 수도 있고 끝나지 않을 수도 있습니다. 

 

 

Admissible Heuristic

 H(n)을 측정할 때 H(n)이 실제보다 큰 값으로 측정되지 않는 경우의 휴리스틱 

 

 

A* Search

 F(n) = g(n)  + h(n) 

솔루션 Cost 를 최소로 에측하는 탐색입니다. 

Greedy Best-Fit Search( h(n) 만 ) 와 Uniform-Cost Search( g(n) 만 ) 를 조합한 것이죠. 

H(n)이 실제보다 큰 값으로 측정되지 않으면 Optimal 합니다. 

A* 는 어떠한 휴리스틱에서도 Optimal 하는 게 효율적입니다. 

A* 보다 적게 Expand 하는 Optimal 알고리즘은 없습니다. 

 

 

Tree Search Based 와 Graph Search Based 

이 둘의 가장 중요한 차이는 Explored Set(방문한 노드의 집합) 의 유무입니다. 

Graph Search Based 는 Explored Set 을 통해서 redundant path(중복된 경로)를 제거하는 스텝이 추가됩니다.

트리기반 슈도코드

그래프기반 수도코드

 

궁금증, 트리노드는 explored set이 없는데 어떻게 왔던 길을 되돌아갈까? 이는 Node 자체의 정보 덕분입니다. 

위의 그림과 같이 노드는 부모 정보를 기억하고 있습니다.

 

 

 

Redundant Path(불필요한 경로)

동일한 시작 node 에서 동일한 Goal node 로 가는 경로가 여러 개 일 때입니다.

 

Loopy Path 

이상한 경로, Redundant Path 의 특수한 경우입니다. 

Loopy Path는 주로 Repeated State 를 발생시키고 무한 루프도 발생시깁니다.