빨간당무 마을

- 제약 만족 문제(Constraint Satisfaction Problem; CSP) - 주어진 제약 조건을 만족시키는 해를 찾는 탐색 방법으로, 이 제약 조건을 만족시킨 상태가 CSP의 목적 상태이다. - 제약 조건을 만족시키지 않으면 탐색 범위에서 제외되기 때문에 탐색 공간을 줄일 수 있고, 모든 상태가 제약 조건을 만족시키지 않을 경우, 해가 없음을 미리 알 수 있는 예측적 성격을 갖는다. - 어느 도메인에서든 제약 조건만 변경하면 적용할 수 있으므로, 도메인 독립적이다. - 해를 찾는 과정을 추적(trace)할 수 있다. - 각각의 변수가 가지는 도메인 내에서 문제에 주어진 모든 제약 조건을 만족하는 해를 찾는 문제로 정의 - 구성 요소 domain variable : 상태값이 저장되어 있는 변..

- 유전 알고리즘이란 자연계에 있어서 생물의 유전(Genetics)과 진화(Evolution)의 메카니즘을 공학적으로 모델화하는 것에 의해 생물이 갖는 환경에서의 적응 능력을 취급하는 것 - 1975년에 John Holland가 저서 "Adaptation on Natural and Artificial System'에 처음 소개한 자연도태의 원리를 기초로 한 최적화(Optimization) 방법 - 유전 알고리즘 - 자연계 생물의 유전과 진화의 메카니즘을 공학적으로 모델화 하는 일종의 확률 탐색 방법으로, 생물의 유전자 모양으로 탐색을 진행하며, 탐색(search), 최적화(optimization), 기계학습(machine learning)의 도구로서 많이 사용됨 - 근접한 최적 해를 찾기 쉽고 병렬적 탐..

- Local beam search - Beam Search의 일종 (Path-based algorithm) - Best-First search 에서 기억 노드의 수를 제한 하는 방법 - 기억 공간이 축소되지만 너무 빠른 가지치기를 초래 - BFS search로 다음 상태의 해집합을 구함 - 해집합을 Goal에 가가운 순으로 정렬 - 사전 설정된 수만큼의 해집합만을 유지하고 나머지는 잘라냄

- Best first search - 휴리스틱에 따라 목표까지 가장 좋은 경로 상에 있다고 판단되는 노드를 우선 방문하도록 진행 Evaluation Function에 따라 다음에 확장 할 노드를 선택 (같은 값이면 무작위 선택) 다음에 확장할 노드가 Goal이면, 탐색 종료 - 한 노드로 부터 목표 노드까지 도달하기 위한 비용을 평가 함수로 함 출발노드에서 시작하여 목표노드까지 도달하는 최적의 경로를 탐색하는 것은 보장 되지 않음 - 방안 : A* algorithm - A* algorithm - 출발 노드부터 목표 노드까지의 최적경로를 탐색 - f(n) = g(n) + h(n) -> 출발 노드에서 시작하여 노드 n을 거쳐서 목표 노드까지 도달하는 비용 g(n) : 출발 노드로 부터 노드 n까지의 경로비..

- Systematic search 절차적인 탐색 최적해(optimal solution)을 찾을 수 있음 최적해임을 보장할 수 있음 오버헤드가 큼 해를 찾는 과정을 알 수 있음 Exact search 최적해를 찾을 수도 있지만 못 찾을 수도 있음 CSP(Constraint Satisfaction Problem) - Stochastic search 확률적인 탐색 빠른 시간에 해를 찾을 수 있음 최적해를 보장할 수 없음 해를 찾는 과정을 알 수 없음 Heuristic search 최적해를 보장할 수 없음(Near-optimal) Genetic algorithm

- hill climbing 기법은 DFS(depth-first search)를 기초로 하여 heuristic을 적용한 탐색 기법으로 현재 상태와 자식 노드와의 거리(혹은 비용)에 따라 정렬(sort)한 후 각 단계(step)의 선택이 이전 단계의 상태보다 나은지를 평가함 - 작은언덕(foothilll) : 작은 언덕에서 시작할 경우 시간을 소모 할 수 있음 - 고원(plateaus) : 고원이 계속될 경우 비교대상을 찾지 못함 - 산등성이(ridge) : 산등성이인 경우 최적해로 알 수도 있음(local solution) Fig. 1. (ref. Artificial Intelligence A Modern Approach Third Edition)Fig. 2. (ref. http://www.cs.iusb..

- 예상되는 최대의 손실(maximum loss)를 최소화(minimize) 시키기 위해 사용되는 의사 결정 이론(decision theory)의 한 방법임 - 해당 문제에서 탐색이 끝나면 탐색트리로 부터 최상이라고 추정되는 행동을 찾기 우해 탐색트리의 단말(leaf) 노드에 정적 평가 함수(static evaluation function)로 추정값을 얻고 그 단말노드의 가치를 통해 최상의 행동을 찾음 - 예를 들어, 체스에서 유용한 특징들은 상대적인 말의 이점, 중심의 제어권, 킹에 의한 중심제어 여부 등이 있는데, 게임트리를 분석할 때 max에 유리한 상태에서는 평가함수 값이 양수, min에 유리한 상태에서는 평가 함수 값이 음수, 그리고 max나 min 어느 편에 특별히 유리하지 않은 상태에서는 0..

Alpha-Beta pruning 이란? 두명이 참여하는 게임을 위한 최소최대(Mini-max) 알고리즘에 의해 평가되는 노드들의 수를 감소시키기 위한 기술이다. 즉, 게임에서 상대방은 절대 도달하지 못하도록 나에게만 유리하게 탐색트리의 일부분을 잘라내는 것이다. Alpha-beta pruning을 가진 minimax는 가지치기를 하지 않는 minimax와 같은 결과를 보이지만 훨씬 더 효율적이다. 보통 효율적인 분기 요소(branching factor)를 square root 까지 감소시키고, 같은 시간내에 탐색할 수 있는 가지(ply)의 수를 두배로 만든다. 두 값 앞파와 베타는, maximizing player가 보장하는 (assured of) 최소 점수이며 마찬가지로 minimizing playe..

■ 바인딩(Binding)을 설명하고 바인딩시간(Binding time)의 종류 ([1] pp.221) - 바인딩(Binding) 일반적인 의미에서, 속성과 개체 사이 또는 연산과 기호 사이와 같은 연관(Association)이다. 바인딩이 일어나는 시간을 바인딩 시간이라고 부른다. 바인딩과 바인딩 시간은 프로그래밍 언어 의미론에서 매우 중요한 개념이다. 바인딩은 언어 설계 시간, 언어 구현시간, 컴파일 시간, 링크 시간, 적재 시간, 또는 실행 시간에 일어날 수 있다. 다음 C 배정문을 생각해 보자 int count; count = count + 5; 위 배정문에 대해서 고려할 수 있는 바인딩과 바인딩 시간은 다음과 같다. - count에 대한 가능한 타입의 집합은 언어 설계 시간에 바인딩 된다. 예)..

Turing Test 란? 앨런 튜링이 1950년에 제안 기계가 인간과 얼마나 비슷하게 대화할 수 있는지를 기준으로 기계에 지능이 있는지를 판별하고자 하는 테스트 서로 상대를 볼 수 없는 폐쇄된 공간에서 실험자가 대화하는 대상이 사람인지 기계인지를 구분 할 수 없는 경우 이 기계를 지능적인 컴퓨터라고 말할 수 있음 (단, 예/아니오 로만 대답이 가능함) 문제점으로는 누가, 얼마나 오랜 시간 대화하여 판단하였는가에 따라 그 기준이 모호함 Eliza 란? 정신병 환자를 치료하기 위한 심리 치료 프로그램 특정 단어에 따라 질문을 하게 만들어 졌고, 인칭과 시제를 대화에 맞게 바꾸는 정도의 극도로 단순한 프로그램 (http://www.manifestation.com/neurotoys/eliza.php3) Tur..