분류 전체보기354

• 

  Admissible Heuristics from Subproblems, Pattern Databases Admissible Heuristics from Subproblems - 8-puzzle 문제의 subproblem 이다. - 1~8까지 모두 고려하는 게 아니라, 1~4까지만 고려하면 되는 문제로 원래 문제의 subproblem 이다. - 기존의 h1, h2 는 계산이 쉬웠다. 그러나 Subproblem 은 그에 비해 바로 찾는 것이 어렵다. - Subproblem 의 optimal solution 비용은 항상 original problem 보다 작으므로, admissible heuristic 하다. Pattern Databases - 모든 가능한 subproblem 의 state 에 대한 cost 를 저장해두는 방식이다. Goal state 에서부터 무작위로 start 하여, 만나는 node들의 co.. 인공지능 2021. 10. 18.

• 

  A* Search for N-puzzle Problem, Relaxed Problem The 8-Puzzle Problem - 8-퍼즐을 푸는데 평균적으로 22 step 이 걸리며, branching factor 은 평균 3이다. tree search 의 경우 3^22 개의 노드를 방문할 것이다 -> 3.1 x 10^10 node 에 달하는 큰 수 graph search 의 경우 1700000개의 노드를 방문할 것이며, 15-puzzle 의 경우 10^13 에 달할 것이다 A* Serach for the n-Puzzle Problem - 두 개의 Admissible heuristics 을 사용할 수 있다. - 즉, 절대 goal 까지 가는데 걸리는 step 을 넘지 않는 heuristic 함수를 필요로 한다. h1 : 잘못 위치된 타일의 수 h2 : 잘못 위치된 타일과 goal 위치와의 .. 인공지능 2021. 10. 18.

• 

  Informed search, Greedy Best-first Search, A* Search Informed Search - 지금까지의 Uninforemd 와는 달리, 문제 정의 이외의 정보를 더 활용하여 효율적으로 검색을 하는 방법이다. - Best-First Search : 트리 내 evaluation function f(n) 에 의해 cost가 가장 적은 노드를 판별하여 먼저 탐색한다. f(n) 은 heuristic function h(n) 을 포함하고 있다. h(n) 이란 n에서부터 goal 까지의 최소 비용을 예측하는 함수이다 예를 들어, Romania 문제에서 원래는 도시간의 비용이 지도에 주어졌지만, h(n)을 사용한다면 도시 n에서부터 goal 까지의 직선거리를 사용할 수 있다. (직선거리 = straight line distance -> SLD) Greedy Best-First .. 인공지능 2021. 10. 17.

• 

  Iterative Deepening Depth-First Search, Bidirectional Search Iterative Deepening Depth-First Search - Depth limit 를 점진적으로 늘려가나는 DLS 방식으로, goal state 를 찾을 때까지 반복해나간다. - Space complexity : Depth-first search 와 같이 O(bd) 이다. - Completeness & Optimal : Yes, Breadth-first search 처럼 branching factor b가 유한하다면 complete 하고, path cost 화 depth 가 비례하다면 optimal 하다. - 예시 - Goal 을 찾을 때까지 depth limit 를 늘려가는 과정이다. Efficiency of IDS - 같은 노드가 여러번 생성되어 성능이 좋지 않을 것으로 보이지만, 대부분.. 인공지능 2021. 10. 17.

• 

  Depth-First Search, Depth-Limited Search Depth-First Search - 항상 가장 깊은 노드부터 expand 하는 기법이다. - Graph search 의 frontier 를 LIFO 로 구현한 방식이다. Performance of Depth-First Search - Completeness : Graph search version : Yes, 단 state space 가 유한한 크기일 때 Tree search version : No, 방문했던 노드를 재방문 가능하므로 cycle 이 생길 수 있다. -> graph 버전은 explored set 으로 노드의 중복을 막고, tree 버전은 루프가 생길 수 있다. - Optimality : No, 항상 최적은 아니다. 최적의 답보다 더 깊이 있는 노드를 먼저 찾을 수 있기 때문 - Time .. 인공지능 2021. 10. 17.

• 

  Uniformed Search, BFS, UCS Uninformed Search -문제의 정의 외에는 다른 정보가 주어지지 않는 검색 알고리즘이다. - blind search 라고 불리기도 한다. - 이 알고리즘은 현재 상태에서 목표 상태까지의 path cost 를 모른다. - 따라서 오직 다음 후임자(successor) 를 expand 하고, 목표 상태인지 목표 상태가 아닌지를 구분만이 가능하다. - 후임자(successor) 들을 expand한 순서는 매우 중요한 key 가 될 것이다. - Uninformed Search 종류 Breadth-First Search (너비 우선 탐색) Uniform-Cost Search (일정량 탐색) Depth-First Search (깊이 우선 탐색) Depth-Limited Search (깊이 제한 탐색) It.. 인공지능 2021. 10. 17.

• 

  Search Tree, Tree search, Graph search A Search Tree - 문제를 형식화 한 뒤, 문제를 풀어야 한다. - 이때, solution 은 하나의 action sequence인데, 이 동작열을 찾기 위해 검색 알고리즘을 사용한다. - 검색 알고리즘은 가능한 여러 sequence 들을 살펴본다. - Initial state -> root - actions -> branches - states -> nodes Tree Search - initial state을 현재 state 로 설정한다. - Iterate 현재 state 가 Goal 인가? 그렇다면, 지금까지 찾은 solution (action sequence) 를 리턴 아니라면 가능한 action 들을 고려한 뒤 EXPAND 액션 선택 선택한 action 으로 파생된 state 를 현재 .. 인공지능 2021. 10. 17.

• 

  Problem-solving agent, search algorithm Problem-Solving Agents - Atomic 표현법을 사용한다. - task environments : 문제의 solution 은 Sequence of actions 이다. - 즉, 미래의 percept 에 대해서는 고려하지 않는다. - 검색 알고리즘이 solution 을 찾을 때 사용된다. - search algorithm 종류 Uninformed search : 문제에 대한 정의 외에 정보는 X Informed search : 문제에 대한 정의 + 추가적인 정보를 가짐 - From Romania to Home : 루마니아에서 집까지 찾아가는 문제 Goal Formulation - Goal : 이 세상의 일부 상태의 집합 - 지도를 가지고 있다고 가정하자 (=informed search) .. 인공지능 2021. 10. 17.

• 

  Agent Program Agent Programs - Agent = architecture (computing device) + program(구현 - data, algorithm) - Agent function vs agent program : 이론적인 vs 현실적인 - A simple agent program 입력값은 percept 이고, 리턴값은 action 이다. percepts 은 입력들을 나열한 percept sequence, percept history 이다 table 은 state sequence 에 대한 action 이 명시되어 있는 agent function 이다. 위 프로그램은 매우 큰 메모리를 필요로 하게 된다. ( 진공청소기 agent, 자율주행 택시) 왜냐하면 table 이 모든 state 의 조합에 .. 인공지능 2021. 10. 16.

• 

  Agent Agents -AI 의 정의는 Acting rationally 에 부합하는 이성적으로 행동하는 인공지능이다 - Sensor 를 통해 AI 가 처한 환경을 인식하고, Actuator(동작 기관) 을 통해 주어진 환경에서 행동한다. - Agent 의 예 : 사람, 로봇, 온도조절기(냉난방기), 소프트봇 등등 - Percept : 특정한 시각 (순간) 에서의 지각 - Percept sequence : 그러한 지각들의 연속 - Agent function : percept sequence 를 입력으로 받아 action 을 리턴함 - Agent program : Agent function 을 실제로 구현한 것 A Vacuum-Cleaner World 진공 청소기 세상을 정의하는 방법은 다음과 같다. Percept .. 인공지능 2021. 10. 16.

• 인공지능 역사 1952-1969 초기의 열광과 기대 Newell and Simon - "Thinking humanly" 접근법으로 General Problem Solver 을 만들었다. (LT 는 Thinking rationally 접근법) - Physical Symbol System hypothesis (물리적인 기호 시스템 가정) Arthur Samuel at IBM - 체커를 할 수 있는 컴퓨터 프로그램을 만들었다. John McCarthy at MIT - 프로그래밍 언어 LISP 를 만들었다. - Time-sharing 기법을 사용하였다. - Advice Taker (지식을 사용하여 추론하는 접근 프로그램) John McCarthy MIT -> Stanford - J.A. Robinson, resolution .. 인공지능 2021. 10. 16.

• 

  인공지능 연구 분야 Mathematics -What are the formal rules to draw valid conclusions? -> Logic -What can be computed? -> computation - How do we reason with uncertain information? -> probability -logic 의 수학적 발전은 George Boole에 의해 시작되었으며, 그는 Boolen logic 을 발견한 사람이다. -Incompleteness theorem (Kurt Goedel) 불완전성 정리 어떠한 공식이든지, 참이지만 증명이 불가능한 문장이 존재한다. 즉, 어떤 함수의 정수들은 알고리즘으로 표현할 수 없다 -> 계산할 수 없다. - Church-Turing thesis Turin.. 인공지능 2021. 10. 16.