인공지능30

• 

  Resolution Inference Rule, Conversion to CNF, Resolution Algorithm Properties of Search-Based Theorem Proving Algorithms - Sound? Yes. 적용하는 inference rule 들이 sound 하기 때문이다. - Complete? inference rule 들이 매우 많은데 어떤 것을 사용할 지 알 수 없기 때문에 증명하기가 어렵다. - 따라서 연구자들은 inference rule 을 하나만 사용하는 알고리즘을 고안했다. 그리고 그 알고리즘이 complete 한 것을 증명하였다. -> resolution (하나의 inference rule) The Resolution Inference Rule - Unit resolution rule dnl1...lk 는 unit literal 이고, m은 단위 literal 일 때, l1.. 인공지능 2021. 12. 19.

• 

  Model Checking, Logical Inference, Theorem Proving A Simple Inference Example - [1,2] 를 안전하게 방문할 수 있을까? -> [1,2] 에는 함정이 없을까? (간단한 예제이므로 괴물은 배제하고 생각함) - In propositional logic Is ㄱP1,2 true? (1,2 에는 함정이 없나?) KB |= ㄱP1,2? (KB 에 의해 ㄱP1,2 가 entail 될 수 있나?) - KB - KB 는 다섯개의 sentence 의 집합이거나, 다섯개의 conjuncts를 가지고 있는 하나의 sentence 로 생각할 수 있다. Inference by Model Checking - M(KB) 는 M(ㄱP1,2) 에 포함되는지를 확인하는 것이 Model checking 이다. - M(KB) 와 ㄱP1,2 에는 7개의 proposi.. 인공지능 2021. 12. 18.

• 

  Logical Inference, Syntax of Propositional Logic, Semantics of Propositional Logic Logical Inference - logical entailment between sentence KB |= a 는 KB가 참이면 a가 참임을 의미한다. - KB 가 논리적으로 a를 entail 하는지를 결정하는 알고리즘이 필요하다. (Logical) inference algorithms - model checking algorithm M(a) 가 M(B) 의 부분집합인지 확인한다. - 알고리즘 i의 결과는 KB가 a를 entail 할 수도 있고, entail 하지 않을 수도 있다. Properties of (Logical) Inference Algorithms - Soundness entail 된 sentence 만 유도한다. -> KB |= a 는 KB 에서 a가 유도된다라고 말할 수 있다. 실제로.. 인공지능 2021. 12. 18.

• 

  Knowledge, The Wumpus World, Logical Reasoning Knowledge - 3,4 장에서 사용한 지식은 domain-specific 이라는 한계를 가지고 있었다. (n-puzzle문제 등) - 7장부터는, Logic 을 지식을 표현하는 방법으로 사용할 것이다. Knowledge-Based Agents - Knowldege base (KB) 지식표현언어로 구성된 sentence 들의 집합 - Inference 어떤 문장들로부터 새로운 문장을 추론해낸다. tell과 ask 는 다양한 문제에서 공통으로 구현되는 함수이다. - declarative approach TELL, ASK 는 공통으로 구현된 것을 사용할 수 있다. LISP, PASCAL 에서 사용된다. 이와 상반되는 접근법을 procedural approach 라고 하며, C, JAVA 등에서 사용된다... 인공지능 2021. 12. 17.

• 

  Local Search for CSPs, Independent Subproblems, Tree-Structured CSPs Local Search for CSPs - Complete state formulation (처음엔 initial state 에 무작위로 queen 을 다 배치한다.) - constraint 를 위반하는 변수를 랜덤으로 선택한다. - 선택한 변수의 값을 변경해준다. (여기서는 퀸의 위치를 변경한다.) - min-conflicts 에 해당하는 값으로 변경한다. - 다음으로 선택한 퀸을 최소제약 즉 0의 위치로 옮기게 되면 solution 을 찾게된다. - solution Independent Subproblems 위 문제에서 T는 위의 6개의 node 들과 독립적이기 때문에, 독립적인 두 개의 문제를 별도로 푸는 것과 같다. -> 같이 풀 때는 ()^7 이던 시간복잡도가 따로 풀게 된다면 ()^6 + ().. 인공지능 2021. 12. 17.

• 

  Path Consistency, K-Consistency, Global Constraints, Backtracking Search for CSPs Path Consistency - arc consistency 의 문제점 Map coloring using two colors -> 해결책이 없다. 그러나 AC-3 알고리즘은 솔루션이 없음에도 이를 탐지하면 못한다. 왜냐하면 모든 변수가 이미 arc consistent 하기 때문이다. - 두 개의 변수 집합 {Xi, Xj} 가 제 3의 변수 Xm에 대해서 consistent 하다는 것은 , Xi 와 Xj 의 모든 할당 상태에 대해서 {Xi, Xm} 그리고 {Xm,Xj} 사이에 모든 constraint 를 만족하는 값을 할당하는 것이 가능할 때 consistent 하다고 정의한다. WA가 red, SA 가 green 이면 둘 사이에 path consistent 는 성립한다. 이때 WA와도 path cons.. 인공지능 2021. 12. 17.

• 

  Constraint Propagation in CSPs, Local Consistency, Node consistency, Arc consistency Constraint Propagation in CSPs - CSP 를 푸는 두 가지 방법 Search Constraint propagation - 추론의 특정한 종류 변수가 취할 수 있는 값들이 줄어들게 된다. -> search space (탐색 공간) 이 줄어들게 된다. -> 효율성이 높아진다. - 전처리 단계에 constraint propagation 이 일어나거나, search 중간에 일어날 수도 있음 Local Consistency - Node consistency CSP 를 구성하는 한 변수가 가질 수 있는 모든 변수, 즉 domain 이 변수의 unary constraint 를 모두 만족시킨다면 node-consistent 하다. 예) unary constraint : SA 노드는 green .. 인공지능 2021. 11. 23.

• 

  Constraint satisfaction problems (CSPs) - 이전 챕터까지는 atomic representation 사용 -> 6장 부터는 Factored representation 사용 (state 를 표현하는 여러개의 variable 이 존재한다.) - Constraint satisfaction problems (CSPs) : variable value 가 제약조건을 만족해야한다. - CSP search 알고리즘은 general-purpose(범용) heuristic 이다. 반대로 이전까지 배운 search 알고리즘은 구체적인 문제의 heuristic 으로만 사용이 되었다. Defining CSPs - 세 가지 구성요소 X : 변수 {X1, ... , Xn} D : 도메인 {D1, ... , Dn} C : 제약조건 - i 번째 제약조건인 Ci : 의 쌍으로.. 인공지능 2021. 11. 23.

• 

  Evaluation Functions Imperfect Real-Time Decisions - 실시간으로 결정을 할 때에는 결함이 존재한다. - Alpha-beta search 는 terminal state 까지 계산을 하는데 시간이 오래 걸린다. (실제로 바둑, 체스를 alpha beta 로 구현을 할 수 없음) -> 실용적이지 않다. - Heuristic minimax - terminal state 까지 검사를 하지 않아도 된다. - terminal state 인지 테스트하는 대신 CUTOFF-TEST 를 사용한다. 원래는 utility(s) 로, s는 terminal state 였다. 그러나 EVAL(s) 에서는 depth-limit 와 유사하게, 제한을 둔 d까지만 탐색을 한다. cutoff 에 도달을 하였다면, EVAL(s) 로 m.. 인공지능 2021. 11. 23.

• 

  A Pruning, Alpha-Beta Pruning, Mover Ordering The Problem with Minimax Search - 재귀적으로 구현된 minimax search 는 depth search 와 비슷하고, 이는 O(b^m) 의 시간복잡도를 가지기 때문에 실용적이지 않다. - 그러나 어떤 경우에는 모든 노드에 대해 검사를 하지 않더라도 정확한 minimax value 를 알 수 있게 된다. A Pruning Example (a) 에서 [-무한, +무한] 은 A가 가질 수 있는 utility value 의 범위를 뜻한다. B를 방문하더라도 아직 알려진 것이 없기 때문에 B의 utility 범위도 [-무한, +무한] 이 된다. 이때 3을 방문하게 되면, B에서는 utility value 의 최댓값을 3으로 보장할 수 있게 되는 것이다. 다른 노드들을 방문해서 3보다 .. 인공지능 2021. 11. 23.

• 

  A Game Search Problem, A Two-Ply (One Move Deep) Game Tree, The Optimal Strategy in a Game Tree Games - Multiagent (competitive) environments : 상대방 agent 의 action 을 예측할 수 없기 때문에 Contingency 가 존재한다. (상대방의 action 이 ~라면 if , else 로 나눠서 결정) - 대부분의 게임은 deterministic, turn-taking (돌아가면서 진행), two-player , zero-sum game(한 명이 무조건 이기는 게임), perfect information(full observation, 게임에 필요한 모든 정보가 주어짐, 바둑, 체스) - 탐색 공간이 매우 크다 : chess 의 경우 branching factor 가 35에 가깝고, 각 플레이어는 50번 정도를 움직인다. search tree 는 35^1.. 인공지능 2021. 11. 22.

• 

  Transitions in a Pratially Observable World, Maintaining One's Belief State Many Sensorless Problems are Difficult to Solve - belief state 의 개수가 너무 많아지기 때문에 실제로 구현하기 어렵다. - 10 x 10 vacuum world 의 initial belieft state 는 100 x 2^100 = 10^32 의 physical states 를 가질 수 있다. - Solution : Incremental belieft-state search : {1,2,3,4,5,6,7,8} 의 physical state 가 존재할 때 1번 physical state 부터 시작해서 solution 을 탐색하고, 그 solution 을 2번 ,,, 8번 state 에 적용해본다. 그러나 8-puzzle 와 같은 경우에는 sensing 없이.. 인공지능 2021. 11. 22.