스튜어드 러셀의 인공지능을 읽어보자(9) : 고급 검색 기법

https://startagainbornagain.tistory.com/88

스튜어드 러셀의 인공지능을 읽어보자(8) : 해답 검색

 

고급 검색 기법

저번에는 관찰 가능, 결정론적, 기지, 환경을 가진, 그리고 해답이 하나의 동작 열인 단일한 범주의 문제들만 논의했었습니다. 이번 장에서는 그러한 가정들을 완하 하면 어떻게 되는지 살펴봅시다.  

 

상태 공간 안에서 초기 상태로부터의 경로들을 체계적으로 탐색하는 대신 현재 상태 한두 개를 평가하고 수정하는 데 주력하는 국소 검색(local search 또는 지역 검색)만 수행하는 알고리즘들을 다룹니다. 이런 알고리즘들은 해답 상태로 이어지는 경로 비용은 그리 중요하지 않고 해답 상태 자체만 중요한 문제에 적합합니다. 국소 검색 알고리즘에는 통계 물리학에서 영감을 얻은 알고리즘(모의 정련 등)과 진화 생물학에서 영감을 얻은 알고리즘(유전 알고리즘) 등 이 포함됩니다.

출처 : https://en.wikipedia.org/wiki/Local_search_(optimization)

결정론과 관찰 가능에 관한 가정들을 완화했을 때 생기는 일을 조사하고, 만일 에이전트가 자신이 받을 지각을 정확히 예측 할 수 없다면, 그 지각들에 의해 드러날 각각의 우발 사건(contingency; 또는 우발성)하면 에이전트는 자신이 처할 수 있는 상태들도 추적할 필요가 있습니다.

 

마지막으로 초기에는 알려지지 않아서 반드시 탐색할 필요가 있는 상태 공간을 만난 에이전트에게 유용한 온라인 검색(online search)을 탐구합니다.

 

국소 검색 알고리즘과 최적화 문제

국소 검색 알고리즘(local search) 알고리즘들은 현재 노드(current node)만 사용하며, 일반적으로  오직 그 노드의 이웃 노드로만 이동하는 식으로 작동합니다. 대부분의 경우 검색 공정이 밟아 온 경로들은 메모리에 유지되지 않습니다(자원 소모 x) 국소 검색 알고리즘은 체계적이지는 않지만, 2가지 장점이 있습니다. 

• 메모리를 아주 적게 소비 보통은 고정된 양의 메모리만 사용
• 체계적 알고리즘은 적합하지 않은 커다ㅏ란 또는 무한한 (연속) 상태 공간에서도 적당한 해답을 찾아내는 경우가 많음

국소 검색 알고리즘은 목표를 찾는 것 외에 순수한 최적화 문제(optimization problem)를 푸는 데에도 유용합니다. 최적화 문제는 목적 함수(objective function)를 기준으로 해서 가장 좋은 상태를 찾는 것입니다.

 

예를 들어 찰스 다윈에 진화론을 가져와 봅시다. 자연은 생식 적합성이라는 목적 함수를 제공합니다. 즉 다윈의 진화론은 일종의 최적화 문제를 풀려는 자연의 시도라 할 수 있습니다.

 

출처 : https://www.newstown.co.kr/news/articleView.html?idxno=290122

 

상태 공간 지형(state-space landscape)을 고려하면 국소 검색의 이해에 도움이 됩니다. 이 지형은 '장소(location; 상태에 의해 정의됨)'와 '고도(elevation; 발견법적 비용 함수나 목적 함수의 값에 의해 정의됨)'가 있습니다. 고도가 비용에 해당한다면 문제의 목적은 가장 낮은 계곡, 즉 전역 최솟값(global minimum; 또는 전역 최소점)을 찾는 것 입니다. 고도가 목적 함수에 해당한다면 목적은 가장 높은 봉우리, 즉 전역 최댓값(global maximum; 또는 전역 최대점)을 찾는 것입니다. 국소 검색 알고리즘들은 이러한 지형을 탐색합니다. 완결적인(complete) 국소 검색 알고리즘은 목표가 존재한다면 항상 목표를 찾아냅니다. 최적 알고리즘은 항상 전역 최솟값/최댓값을 말합니다.

 

언덕 오르기 검색

https://en.wikipedia.org/wiki/Hill_climbing

언덕 오르기(hill-climbing) 알고리즘이 위에 사진에 나와있습니다. 구체적으로 이 알고리즘은 언덕 오르기의 최고 경사 등반(steepest-ascent) 버전입니다. 언덕 오르기 알고리즘은 값이 증가하는 방향으로, 즉 오르막으로 계속해서 이동하는 루프로 이루어집니다.

루프는 주변에 더 큰 값이 없는 '정상(peak)'에 도달하면 종료됩니다. 알고리즘은 검색 트리를 유지하지 않으므로, 현재 노드를 위한 자료구조는 상태와 목적 함수의 값만 담으면 됩니다.

언덕 오르기는 현재 상태에 바로 이웃한 값들만 고려할 뿐, 그 밖의 값들은 미리 살펴보지 않습니다. 이는 기억상실증 환자가 짙은 안갯속에서 에베레스트 산의 정상에 오르려는 것과 비슷합니다

 

이 알고리즘의 특징은

• 완전 상태 형식화(complete-state formulation)를 사용
• 탐욕적 국소 검색(greedy local search) 

안타깝게도 언덕 오르기가 성능이 상승하지 않는 '곤경'에 처하는 몇가지 이유가 있습니다.

1. 극댓값(local maximum 또는 국소 극댓값): 극댓값은 이웃 상태들보다는 높지만 전역 최댓값보다는 낮은 정상입니다. 극댓값 근처에 도달한 언덕 오르기 알고리즘은 그 정상으로 올라가긴 하지만, 그때부터는 더 이상 오를 곳이 없게 됩니다
2. 능선(ridge) : 능선은 극댓값들이 연이어 있는 상황에 해당합니다. 탐욕적 알고리즘은 이런 상황을 통과하기가 아주 어렵습니다.
3. 대지(plateau) : 대지는 상태 공간 지형에서 평평한 영역을 말합니다. 대지는 오르막으로 가는 출구가 없는 평평한 극댓값이거나 진척이 가능한 어깨(shoulder)입니다 대지에서는 언덕 오르기 검색이 길을 잃을 수 있습니다.

 

오늘은 여기까지고요 다음에는 모의 정련에 대해 공부하도록 합시다.