방송대 컴퓨터과학과 인공지능 기말평가

목차

1. 몬테카를로 트리 탐색의 개념과 탐색 과정을 구성하는 단계들에 대하여 A4용지 1매 정도로 정리하여 설명하라. (20점)
2. k-평균 군집화에 대한 다음 질문에 답하라. (20점)
3. 신경회로망 및 심층학습(딥러닝)에 대한 다음 질문에 답하라. (가)~(다) 각각 A4용지 1매 정도로 정리하여 작성한다. (30점)

본문내용

1. 몬테카를로 트리 탐색의 개념과 탐색 과정을 구성하는 단계들에 대하여 A4용지 1매 정도로 정리하여 설명하라. (20점)

게임트리 탐색에서는 어떤 노드가 얼마나 유리한 상태인지를 판단하기 위해 평가함수를 사용하여 그 값을 정확하게 계산할 수 있지만 방대한 경우의 수가 있는 경우 평가함수를 만드는 것이 매우 어렵다. 몬테카를로 트리 탐색은 게임트리 탐색과는 달리, 어떠한 노드의 가치를 추정할 때 경험적 평가함수를 사용하는 방식이 아닌 무작위 방식으로 탐색하기 때문에 문제에 대한 지식이 많지 않아도 되는 장점이 있다. 이 방식은 게임과 같이 승리하는 가장 유망한 방법을 분석하면서 검색 공간에서 무작위 추출에 기초한 탐색 트리를 확장하는 데 중점을 둔다. 트리 탐색의 절차는 루트노드에서 시작하여 적절한 자식노드를 선택하는 과정을 반복하여 트리를 확장해 나간다. 이 때 생성되는 자식노드의 가치를 알아내기 위해 시뮬레이션을 수행한다. 이 시뮬레이션은 탐색공간을 무작위 방식으로 스스로 게임을 진행하는 '플레이아웃'(playout)에 기초한다. 이 과정은 미리 정의된 예산(시간, 메모리, 반복 횟수 등의 제약)에 도달할 때까지 반복한다. 이 시점에 도달하면 탐색을 중단하고 가장 우수한 행동을 선택한다. 최종 시뮬레이션 결과는 루트노드까지 선택 경로를 따라 역으로 전파되어 업데이트된다.

[몬테카를로 트리 탐색 알고리즘의 4단계]
① 선택(selection): 루트노드에서 시작하여 선택전략에 따라 자식노드를 선택하는 과정을 깊이방향으로 반복한다. 선택전략은 탐사(충분히 검사해 보지 않은 영역을 선택)와 활용(유망한 것으로 보이는 영역을 선택)의 균형을 이루도록 하는 것이다.
② 확장(expansion): 선택된 노드에서 승패를 내지 못하면 하나 또는 그 이상의 자식 노드를 생성(확장)하고 그 중 하나의 노드를 선택한다.

참고 자료

https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%ED%8A%B8%EB%A6%AC_%ED%83%90%EC%83%89
https://blog.naver.com/igenius21c/221694917606
http://sherrytowers.com/2013/10/24/k-means-clustering/
https://it-study-jh.tistory.com/7