스튜어드 러셀의 인공지능을 읽어보자(10) : 모의정련

https://startagainbornagain.tistory.com/92

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

모의 정련

값이 낮은(또는 비용이 높은) 상태로의 '내리막' 이동이 결코 없는 언덕 알고리즘은 극댓값에 머무를 수 있으므로 완결성을 보장하지 못합니다. 반면 순수한 무작위 보행(random walk), 즉 일단의 후행자들 중 하나를 균등분포 난수로 선택하는 방식은 완결적이지만 극도로 비효율적입니다.

 

모의 정련(simulated annealing)이 바로 그런한 시도에서 나온 알고리즘의 하나 입니다. 야금학에서 정련은 금속이나 유리를 높은 온도로 가열한 후 점차 식혀서 해당 물질이 저에너지 결정 상태에 도달하게 함으로써 단련하거나 강화하는 공정을 말합니다.

사진 출처 : https://www.canstockphoto.co.kr/%EA%B0%95%EC%B2%A0-%EC%A0%95%EB%A0%A8-%EA%B3%BC%EC%A0%95-3%EC%B0%A8%EC%9B%90-20384163.html

 

모의 정력을 설명하기 위해, 관하점을 언덕오르기에서 경사 하강(gradient descent)으로 바꾸면 세게 흔들다가 흔들기 강도가 점차 감소하는 결과가 나옵니다.(즉 점차 오차가 작아진다)

 

국소 다발 검색

메모리에 노드 하나만 유지한다는 것이 메모리 제약 문제에 대한 극단적인 반응으로 보일 수 있습니다.

국소 다발 검색(local beam search) 알고리즘은 하나가 아니라 k개의 상태를 추적합니다. 

국소다발 검색에서는 병력적인 검색 스레트들이 유용한 정보를 주고 받습니다. 비유하자면 최상의 후행자들을 생성한 상태들은 다른 상태들에게 '이리로 와, 이쪽으로 풀이 더 싱싱해' 라고 말해 줍니다.

 

가장 간단한 형태의 국소 다발 검색은 k개의 상태들 사이의 다양성 부족 때문에 문제를 겪을 수 잇습니다. k개의 상태들이 상태 공간의 작은 영역에 집중되기 쉬우며, 그러면 검색은 언덕 오르기의 비싼 버전보다 별로 나을 바가 없게 됩니다. 확률론적 언덕 오르기와 같은 취지로 만들어진 환률론적 다발 검색(stochastic beam search)이라는 변형을 사용하면 이 문제가 완화됩니다. 

https://www.slideshare.net/hemak15/lecture-26-local-beam-search-71648392

또 이 책에서는 연속 공간의 국소 검색에 대해 길게 설명합니다 더 궁금하시면 찾아 보시거나 책을 사셔서 읽는걸 추천 해드릴게요!

 

유전 알고리즘

유전 알고리즘(genetic algorithm)은 확률론적 다발 검색의 한 변형으로, 특징은 후행자 상태들이 한 상태의 수정에 의해서가 아니라 두 부모 상태의 결합에 의해 생성됩니다. 자연선택의 비유는 확률론적 다발 검색과 같되, 이제는 무성 생식이 아니라 유성 생식이 관여합니다.

다발 검색 알고리즘들처럼 유전 알고리즘은 무작위로 생성한 k개의 상태들로 시작합니다. 이 상태들의 집합을 군집(population)이라고 부릅니다. 군집의 각 상태, 즉 개체(individual)는 유한한 알파벳(문제 집합)의 한 문자열로 표현됩니다. 가장 흔히 쓰이는 방식은 들과 1들로 이루어진 문자열(비트열)을 사용하는 것 입니다.

https://data-newbie.tistory.com/685

오늘은 여기까지고요 다음에는 비결정론적 동작들을 수반한 검색에 대해 알아보도록 하겠습니다.