9 Log

Informed(Heuristic) Search 문제에 추가적으로 주어진 휴리스틱   정보(Heuristic information) 를  활용하여 각 노드의 평가함수(Evaluation function) 를 만들고 그에 따라 확장 에 우선순위 를 두는 Tree Search 전략이다. 휴리스틱(Heuristic) 불충분한 시간, 정보로 인해 합리적인 판단이 불가능 할때, 과거의 경험이나 사회적 통념 등을 활용한 직관적 인 판단 을 하는 간편 추론법.  이때, 즉각적인 판단 기준이 되는 정보가 휴리스틱 정보(Heuristic Information) 휴리스틱 함수(Heuristic function), f(n) 휴리스틱 정보를 이용해 노드 n부터 목표노드까지의 최소경로비용의 예상치를 정의한 함수. 평가함수(Evaluation function), f(n) 출발노드로부터 노드 n을 거쳐서 목표노드까지 가는 최소경로비용에 대한 예측치를 정의한 함수. 대표적인 Informed Search 전략들 Greedy best-first search A* search Greedy best-first search 어떤 프린지 노드가 목표노드까지 가장 최소경로비용을 가질까? 평가함수 : f(n) = h(n) 장점 : 해를 가장 빠르게 구할수 있다. 단점 : Optimality를 보장 못한다. -> 두가지 이유가 있다. 1.  휴리스틱 함수값과 실제 최소경로비용과의 차이 휴리스틱이 알려주는 예상값의 우선순위가 실제 경로비용값 우선순위와 다르다면 최적해를 찾아가기는 더욱 힘들어진다. 2.  평가함수에 해당 노드까지의 경로비용이 무시되어있다. 서로다른 프린지 노드까지의 경로비용의 차이가 휴리스틱으로 무시 못 할만큼 크다면 휴리스틱으로 만든 우선순의는 의미가 없어진다. ->  그렇다면 어떤 조건에서 Optimality를 보장할까? 1.  휴리스틱 함수의 예측값 = 실제값. 우선, 적어도 휴리스틱 함수값이 실제 최소경로비용과 일치시켜야 겠다. 자, 모든 노드의 휴리스틱 함수값이 실제

문제 해결 ( Problem Solving ) 대표적으로 루마니아 문제 비행기를 타기위해 Arad에서 공항이있는 Bucharest로 가는 가장 최적의 경로 구하기. 문제 해결을 위한 핵심 2가지 요소 State : Agent의 상태 예제에서는 경유지. Action : Agent가 어떤 상태에서 어떤 상태로 이동하기 위한 행동. 예제에선 경유지간 이동하는 행위. 좀더 세밀한 4가지 요소 Initial State : 초기 상태를 정의.  Arad Possible actions : 가능한 Action들을 정의. Successor function, f(state) = {(action, successor state), ...} 를 정의. (action, successor) 쌍으로 만드는 이유 : 문제에 따라 서로 다른 action이 같은 state와 successor state를 가질수도 있다. S(Arad) = {(Arad->Zerind, Zerind), (Arad->Timisoara, Timisoara), (Arad->Sibiu, Sibiu)} Goal test : 목표(Goal State)를 정의하고 각 State별로 Goal State임을 검사하는 방법을 정의 Goal state : Bucharest, Goal test : state = Bucharest 채스처럼 Goal State가 많은 경우. 조건함수를 사용해 implicit하게 정의. Goal test : Checkmate(state) Path cost : 어떤 path를 통틀어 각 action이 발생시키는 cost(Step cost)를 더한 값.  각 action별로 0이상의 Step cost, Sc(state, action, successor state)>=0 를 정의 사실상  Sc (action.state, action, action.successor) 즉 ,Sc(action)과 같다. 이때 음수의 cost를 정의하면 루프를 돌면서 cost를 무한으로 낮추는등의 여러가지

인공지능 소개 1주차 학습노트 * 인공지능 이란? 대개는 지식과 기술을 습득하고 적용하는 능력 이라 한다. *인공지능의 4가지 정의  Thinking humanly, Acting Humanly, Thinking Rationally, Acting Rationally   - Humanly vs Nationally : 문제를 사람처럼 해결 vs 문제를 최고 성능으로 해결. Humanly : 사회적인 행동, 상식적(명시적이지 않은 조건), 전문지식(지식기반), 문제해결 능력(새롭게 주어진 문제를 빠르게 푸는 능력인듯). 가끔은 비이성적. Rationally : 오직 이성적 판단, 명시적 조건 필요, 지식무관. 비사회적.   - Acting vs Thinking  Acting이 Thinking 보다 쉽다. 결과만 사람처럼(이성적으로) 보이면 되기 때문.   *Turing Test  Acting humanly 를 검사. (얼마나 사람처럼 보이느냐...)  통과 위해선, 지식 표현, 자동 추론능력, 학습, 언어-이미지 이해 필요. *Main topics of AI <분야별 Topics> Sensing : 컴퓨터 비전, 음성 인식, 자연어 이해 Thinking : 지식 표현, 문제 해결, Planning, 학습 Acting : 로보틱스, 음성 발화 지식 표현과 추론 : 지식을 어떤 간결한 형태로 컴퓨터와 사람이 동시에 이해할수 있게 한다. 실세계 지식들의 모호성 속에서도 정확한 표현을 가능하게 하며 하여 지식구조를 결합해 추론한다. Planning  : 주어진 World에서 목표를 주어주고 일련의 action들을 통해 성취하는 과정을 설계. 불확실성 : Bayesian networks, graphical models, markov decision processes등 사용.  학습 : 강화학습, 군집화, 회귀분석 등 agent based and multi agent system  ex) 주식시장 예측. 즉, 다양한 시장 참여자가 있는 상태. 게임이론적 관점으로 예측