AI 졸업고사 단순정리

1. AI를 engineering과 science의 관점에서 비교?
  - 사고과정 + 추론을 통한 지능적 행동(intelligence behavior)에 관련된 연구를 하는 학문
  - 기계가 사람처럼 사고하고 행동할 수 있는가? 
    혹은 이성적으로 판단하고 행동할 수 있는 가를 연구함
  - engineering 분야 : 실제 지능적으로 사고, 행동할 수 있는 intelligence machine을 
    만들기 위해 요구되는 개념이나 이론, 실습 등에 관련된 연구 분야
  - science 분야 : 사람이나 동물이 자연생태에서 사고하고 행동하는 일련의 과정들을 
    탐구하고 분석하여 관련된 개념이나 원리를 연구하는 분야 (예-인지과학)

2. Turing test
  - 기계가 생각하고 있는가를 판정하는 시험 (Alan Turing)
  - 현재의 인공지능 분야에서는 어떤 기계가 지능적이냐, 그렇지 않느냐를
    구분하는 기준에 대한 논의보다는 지능 자체의 행동양식, 
    즉 어떻게 해서 지능적인 판단과 행동을 할 수 있는가가 주요 연구 대상임
  - 만약 인간과 대화가 가능한 기게를 만든다면, 인간이 그것이 기계임을 구분하지 못하는
    것이 중요한 것이 아니라 인간이 하는 말과 행동에 반응하고 이를 바탕으로
    새로운 사실을 추론하는 등, 인간에게 유용하게 사용할 수 있어야 함

3. Forward Reasoning과 Backward reasoning
  - 일반적인 추론이란? 기존 명제를 이용하여 새로운 명제를 유도하는 과정으로
    전제와 결과간의 논리적 관계를 다룸
  - forward reasoning : 정보기반 추론과정으로 bottom-up reasoning임
    이용 가능한 여러 정보들로부터 출발하여 적절한 결론을 찾는 추론 방식
    장점 : 간단하고 주어진 문제에 대해 모든 해를 찾는 것이 가능함
    단점 : 문제와 직접 관련 없는 규칙들이 자주 실행되며,
             불필요한 새로운 명제가 많이 생성될 수 있기 때문에 비효율적임
  - backward reasoning : 목표기반 추론과정으로 top-down임
    목표상태의 증명을 위해 이를 뒷받침하는 명제를 찾고,
    또다시 이를 뒷받침하는 명제를 찾는 과정을 반복
    장점 : 현재 목표와 관련이 없는 규칙들은 찾지 않기 때문에 효율적이고
             특정 목표의 참, 거짓을 판단할 수 있음
    단점 : 목표나 가정의 구성이 어렵고, 초기상태에 모든 데이터가 주어져야 추론이 가능함

4. Genetic algorithm과 CSP
  - Genetic algorithm : 자연계 생물의 유전과 진화의 메카니즘을 공학적으로 모델화하는 
    일종의 확률 탐색방법으로, 생물의 유전자 모양으로 탐색을 진행하며, search,
    optimization, machine learning의 도구로서 많이 사용됨.
    근접한 최적 해를 찾기 쉽고 병렬적 탐색이 가능하며 local maximum에 빠지지 않음.
    그러나 만약 탐색이 해의 사이로 진행되는 경우 결과를 찾지 못할 가능성이 있으며, 
    해를 찾는다 하더라도 찾는 과정을 알 수 없음
  - CSP (Constrain Satisfaction problem) : 주어진 제약조건을 만족시켜야 하는 문제를
    말하는데, 이러한 제약조건을 만족시킨 상태가 CSP의 목적상태임.
    제약조건을 만족하지 않는 상태는 탐색의 범위에서 제외되기 때문에 탐색공간을 줄여
    주는 체계적인 방법이며, 합리적인 시간 안에 해를 찾기 위해 heuristic function을 사용함.
    어떤 문제든 제약조건만 알맞게 변경하면 적용할 수 있으므로 도메인 독립적이며,
    해를 찾는 과정을 trace해야 하는 경우 genetic algorithm에 비해 유리함

5. Intelligent Agent의 4가지 특징
  - 자율성 (autonomy)
    사람 혹은 다른 에이전트의 간섭이나 조정 없이 자율적으로 작업을 수행할 수 있음.
    자신의 행위와 내부 상태에 대한 control를 갖음
  - 사회적 능력 (social ability)
    agent간의 상호작용 능력, 다른 agent에게 서비스를 요청하거나,
    자신의 KB에 존재하지 않는 정보를 다른 에이전트에게 요청할 수 있음.
    이러한 에이전트 간의 상호 메시지 교환에 KQML과 같은 공통의 언어가 사용됨
  - 반응성 (reactivity)
    주변상황, 사람이나 다른 에이전트의 행동 등의 변화를 인식하고 이에 적시에
    적절한 대응을 할 수 있음
  - 선행성 (proactiveness)
    환경에 대한 반응 뿐 아니라
    주어진 어떤 목적에 따라 정보를 수집하고 작업을 수행할 수 있음

6. KQML
  - 에이전트가 다른 에이전트에게 서비스를 요청할 경우, 즉 자신의 KB안에 저장되어 있지
    않는 정보요구, 협상이나 스케줄링 등 에이전트간의 정보교환의 필요가 있을 때,
    정해진 공통의 언어 규약에 따라 요구사항을 메시지화 하여 전달함.
    메시지를 받은 에이전트는 이를 분석하여 자신의 내부처리형태로 변화하여
    서비스 처리 후 결과를 다시 메시지화 하여 요청한 에이전트에게 전달함.
    이러한 과정에서 필요한 system independent(시스템 독립적)한 공통의 통신언어를
    KQML이라고 함

7. CSP
  - domain value : domain variable에 assign될 수 있는 값들의 집합
    ex) {1,2,3}, {4,5,6}, {6,9,8,3}
  - domain variable : state값이 저장되어 있는 변수로, 각 변수 사이에는 constraint가 존재함
    ex) a, b, c
  - constraint : variable 간에 존재하는 제약조건, 문제 해결을 위한 제약조건임
    ex) a>b, a+c=b, b=c
  - 예로들어 CSP로 N-Queue problem를 solve할 때
    N-Queen? N*N size의 체스판에 N개의 queen을 서로 공격할 수 없도록 올려놓는 문제
    Q가 놓여질 수 있는 모든 경우를 node로 하는 tree를 구성해보면, 정해진 제약조건,
    즉, 같은 row와 column, 대각선에는 퀸이 놓일 수 없다는 제약조건을 만족하지 않는
    arc를 제외함.
    때문에 탐색하는 범위가 줄어들어 문제 해결 시간을 단축시킴.
    CSP는 사전에 구성된 constraints newwork에 의해 domain를 여과시켜 탐색공간을
    축소하고, 축소된 공간에서 최적해를 찾아냄

8. CSP와 Best-first search (BFS - Graph search algorithm)
  - CSP는 어떤 문제에 대한 제약조건만 바꿔주면 문제를 해결할 수 있으므로
    도메인 독립적이임.
    제약조건에 만족하지 않는 경우를 제거함으로서 탐색공간을 줄일 수 있기 때문에
    비교적 빠른 시간 안에 최적 해를 찾을 수 있음
    또한 모든 상태가 제약조건에 어긋나는 경우 탐색을 중지하는 예측적성격도 가지고 있음
    BFS는 heuristic search 방법으로 얼마나 좋은 heuricstic fuction를 사용하느냐에 따라
    문제해결의 속도가 달라짐. 각 문제에 따른 평가함수를 설계해야 하기 때문에
    도메인 종속적임

9. Simple hill climbing과 Steepest hill climbing (쉬운 언덕 등반과 가파른 언덕 등반)
  - hill climbing 기법은 DFS (depth-first search)를 기초로 하여 heuristic을 적용한
    탐색 기법으로 현재 상태와 자식 노드와의 거리(혹은 비용)에 따라 sort한 후
    각 step의 선택이 이전 step의 상태보다 나은지를 평가함
  - foothill (작은 언덕) : 작은 언적에서 시작할 경우 시간을 소모 할 수 있음
  - plateaus (평지) ; 평지가 계속될 경우 비교대상을 찾지 못함
  - ridge (산등성이) : 산등성이인 경우 최적해로 알 수도 있음(local solution)
  - silple hill climbing은 탐색 시 현재 노드를 자식 노드와 비교하여 목적 상태와 
    가장 가까운 노드를 선택할 때, 가장 먼저 찾은 노드를 선택함
    최적 해를 찾지 못할 수도 있음(local solution에 빠짐)
  - steepest hill climbing은 모든 자식 노드를 평가한 값을 비교해서 최선의 경로를 찾음

10. A* algorithm이 f' = g + h' 일 때, 최적 해를 찾는다고 어떻게 보장할 수 있은가?
  - A* algorithm은 BFS (Breadth-First search)의 한 예로, 가장 좋은 경로 추정을 위해
    각 노드의 랭킹을 부여하는 heuristic을 사용하고 그 순서대로 경로를 방문함
  - f' : goal 까지의 현재 추정 비용, 목표상태가 가까워질수록 추정이 쉬움
  - g : 현재 경로까지 확정 비용
  - h' : 현재부터 goal 까지 추정비용
  - h = h' 인 경우, 문제없이 최적 해를 찾음
  - h' < h 인 경우, 시간이 소비되기는 하지만 결국 적은 비용이 드는 경로로 가기 때문에
               goal을 찾을 수 있음
  - h' > h : 해를 찾지 못하며, BFS의 정의에 어긋남
  ※ 참고 search method에서
    DFS는 stack base, BFS는 queue base, Blind search는 Random.
  ※ A*와 BFS의 different
    현재 Node에서 다음 이동 가능 Node 후보를 선정시에 (f' = g + h' 일 때)
    A*는 모든 후보 중 f'가 가장 유리한 값을 선택하고
    BFS는 모든 후보 중 h'가 가장 유리한 값을 선택함

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

11. α-β pruning (알파-베타 가지치기)
  - 2명이 참여하는 게임을 위한 최소최대(Mini-max) 암고리즘에 의해 평가되는 노드들의
    수를 감소시키기 위한 기술임
    즉, 게임에서 상대방은 절대 도달하지 못하도록 나에게만 유리하게 탐색트리의
    일부분을 잘라내는 것임.
    Alpha-Beta pruning을 가진 Mini-Max는 pruning을 하지 않은 Mini-Max와 같은 결과를
    보이지만 훨씬 더 효율적임
    - 최소값에 의한 pruning은 Alpha pruning, 최대값에 의한 pruning은 Beta pruning

※ 이런 자료를 정리해 주신 애띠 누님께 심심한 감사를 드립니다 ^^

- 20090327 추가
12. Semantic Web and Web 2.0
  - Semantic Web : 컴퓨터가 사람을 대신하여 정보를 읽고 이해하고 가공하여 새로운
    정보를 만들어 낼 수 있도록, 이해하기 쉬운 의미를 가진 차세대 지능형 웹
    시맨틱 웹을 구성하는 핵심 기술로는 자원 기술 개념(RDF)과 같은 웹 자원(Resource)을
    서술하기 위한 자원 서술 기술, 온톨로지(ontology)를 통한 지식 서술 기술, 통합적으로
    운영하기 위한 에이전트(agent) 기술 등을 들 수 있다
  - Web 2.0 : 개방형 서비스 구조를 기반으로 사용자의 참여를 통해 핵심가치를 창출하는
    인터넷 서비스. 기존의 웹이 사용자들이 데이터와 서비스를 수동적으로 받는 일방적인
    정보제공의 개념이라면 웹2.0은 참여와 개방을 바탕으로 사용자들이 자유롭게 정보와
    네트워크를 활용하는 개념이다.