인공지능 정리

인공지능

강한 인공지능 (strong AI)
-사람과 같은 지능
-마음을 가지고 사람처럼 느끼면서 지능적으로 행동하는 기계
-튜링 테스트
-지능의 조작적 정의 (operational definition)
-조작적 정의: 측정할 수 있는 조건으로 어떤 속성을 기술
-흉내 게임(imitation game)
약한 인공지능 (weak AI, narrow AI)
-특정 문제를 해결하는 지능적 행동
-사람의 지능적 행동을 흉내 낼 수 있는 수준
-중국인 방 사고실험(The Chinese Room Thought Experiment)
-존 설(John Searle,1980) 제시
-문 밑으로 중국어로 쓴 질문지를 전달
-방 안에서 중국어를 모르는 사람이 글자모양에 따른 중국어 단어 조합 방법
-매뉴얼을 참조하여 답변에 대한 단어 조합
-조합된 단어들을 문 밖으로 내보냄
-문 밖 사람은 중국어를 이해하는 사람이 방 안에 있다고 생각
-단지 흉내만 내고 이해하는 것은 아님
-이해하지 못하고 흉내 낼 수 있어도 지능적(intelligent) 행동.

세 차례의 붐

수단-목표 분석(means-ends analysis)
-해결해야 하는 문제를 상태(state)로 정의
-현재 상태와 목적 상태(goal state) 간의 차이 계산
-목적 상태로 도달하기 위한 조작자(operator, 연산자) 선택 적용하는 과정 반복
탐색과 최적화

탐색
-문제의 해가 될수 있는 것들의 집합을 공간으로 간주하고,
 문제에 대한 최적의 해를 찾기 위해 공간을 체계적으로 찾아 보는것
-해(solution)정의 : 일련의 동작으로 구성되거나 하나의 상태로 구성
-상태(state)정의 : 특정 시점에 문제의 세계가 처해 있는 모습
-세계(world)정의 : 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭

-상태 공간과 탐색
-상태 공간(state space)
-문제 해결과정에서 초기 상태로부터 도달할 수 있는 모든 상태들의 집합
-문제의 해가 될 가능성이 있는 모든 상태들의 집합
-초기 상태: 문제가 주어진 시점의 시작 상태
-목표 상태: 문제에서 원하는 최종 상태
-탐색문제의 예
-선교사-식인종 강건너기 문제
-8퍼즐 문제
-tic-tac-toe
-상태 공간 그래프(state space graph)
-상태공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프
-노드 : 상태
-링크 : 행동
-해 : 초기상태에서 목표 상태로의 경로
-문제점 : 일반적인 문제에서는 상태 공간이 매우 큼
-미리 상태 공간 그래프를 만들기 어려움

-맹목적 탐색(Blind search)
-정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 탐색하는 방법

-깊이 우선 탐색(depth-first search, DFS)
-초기 노드에서 시작하여
 깊이 방향으로 탐색
-목표 노드에 도달하면 종료
-더 이상 진행할 수 없으면,
 백트랙킹(backtracking, 되짚어가기)
-방문한 노드는 재방문하지 않음
-메모리 적게 소모
-최단 거리를 보장 하지 않음

-너비 우선 탐색(breadth-first search, BFS)
-초기 노드에서 시작하여
 모든 자식 노드를 확장하여 생성
-목표 노드가 없으면 단말노드에서
 다시 자식 노드 확장
-전체 트리를 메모리에서
 관리, 메모리 부담 큼
-최단 거리를 보장해 줌


-반복적 깊이심화 탐색(iterative-deepening search)
-깊이/너비 우선 탐색의 장점만 활용(메모리, 최단거리)
-반복적인 깊이 우선 탐색에 따른 비효율성
–실제 비용이 크게 늘지 않음
–각 노드가 10개의 자식노드를 가질 때,
 너비 우선 탐색 대비 약 11%정도 추가 노드 생성
-맹목적 탐색 적용시 우선 고려 대상











-양방향 탐색(bidirectional search)
-초기 노드와 목적 노드에서동시에 너비 우선 탐색을 진행
-중간에 만나도록 하여 초기 노드에서
 목표 노드로의 최단 경로를 찾는 방법

-정보 이용 탐색(informed search)
-휴리스틱(heuristic)
-그리스어 Εὑρίσκω (Eurisko, 찾다, 발견하다, 유레카)
-시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나,
 굳이 체계적이고 합리적인 판단을 할필요가
 없는 상황에서 신속하게 어림짐작하는 것
-최적해를 보장 할수 없음
-예 : 최단 경로 문제에서 목적지까지 남은 거리
 현재 위치에서 목적지(목표 상태)까지
 지도상의 직선 거리, 직선이라는 직관을 이용

-언덕 오르기 방법(hill climbing method)
-지역 탐색(local search),
 휴리스틱 탐색(heuristic search)
-현재 노드에서 휴리스틱에
 의한 평가값이 가장 좋은
 이웃 노드(주변을 보면서) 하나를
 확장해 가는 탐색 방법
-활용 정보 : 이웃 노드의 높이
-단점: 국소 최적해(local optimal solution)에 빠질 가능성 있음

-최상 우선 탐색(best-first search)
-확장 중인 노드들 중에서 목표 노드까지
 남은 거리가 가장 짧은 노드를 확장하여 탐색
-활용 정보 : 목표노드 상태와 다른 것
-남은 거리를 정확히 알 수 없으므로 휴리스틱 사용
-Best인거 하나만 활용

-빔 탐색(beam search)
-휴리스틱에 의한 평가값이 우수한 일정 개수의 확장
 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용
-'최상 우선 탐색'과 비슷하나 Best인거
 하나가 아닌 Good 여러개를 같이 선택
-A* 알고리즘(A-star 알고리즘)
-추정한 전체 비용 F(n)을 최소로 하는 노드를 확장해 가는 방법
-f(n): 노드 n을 경유하는 전체 비용
-현재 노드 n까지 이미 투입한 비용 g(n)과
-목표 노드까지의 남은 비용 h(n)의 합 / f(n) = g(n) + h(n)
-문제점 : 남은 비용 h(n)의 정확한 예측 불가
-해결책 : h(n)에 대응하는 휴리스틱 함수 H(n)사용 / F(n) = g(n) + H(n)
-게임에서의 탐색
-게임 트리(game tree)
-상대가 있는 게임에서 자신과 상대방의
 가능한 게임 상태를 나타낸 트리
-ex: 보드게임 = 틱-택-톡, 바둑, 장기, 체스 등
-게임의 결과는 마지막에 결정
-많은 수(lookahead)를 볼 수록 유리




-mini-max 알고리즘(mini-max algorithm)
-MAX 노드: 자신에 해당하는 노드로
 자기에게 유리한 최대값 선택
-MIN 노드:상대방에 해당하는 노드로
 최소값 선택
-단말 노드부터 위로 올라가면서
 최소(minimum)-최대(maximum) 연산을
 반복하여 자신이 선택할 수 있는
 방법 중 가장 좋은 것은 값을 결정

-α-β 가지치기 (prunning)
-검토해 볼 필요가 없는 부분을
 탐색하지 않도록 하는 기법
-깊이 우선 탐색으로 제한 깊이까지 탐색을 하면서,
 MAX 노드와 MIN 노 드의 값 결정
-a-자르기(cut-off) : MIN 노드의 현재값이 부모
 노드의 현재 값보다 같거나 작으면,
 나머지 자식 노드 탐색 중지
-b-자르기 : MAX 노드의 현재값이 부모노드의
 현재값보다 같거나 크면,
 나머지 자식 노드 탐색 중지
 

-몬테카를로 시뮬레이션 (Monte Carlo Simulation)
-특정 확률 분포로 부터 무작위 표본(random sample)을 생성하고, 이 표본에 따라 행동을 하는 과정을
 반복하여 결과를 확인하고, 이러한 결과확인 과정을 반복하여 최종 결정을 하는 것
-모든 경우를 수행 하면서 특정 수에서 이길 확률 정리하고 이를 이용하여 정리

-몬테카를로 트리 탐색(Monte Carlo Tree Search, MCTS)
-탐색 공간(search space)을 무작위 표본추출(random sampling)을 하면서,
 탐색트리를 확장하여 가장 좋아 보이는 것을 선택하는 휴리스틱 탐색 방법
-4개 단계를 반복하여 시간이 허용하는 동안 트리 확장 및 시뮬레이션
-선택(selection) : 트리 정책(tree policy) 적용
-루트노드에서 시작
-정책에 따라 자식 노드를 선택하여 단말노드까지 내려 감
-승률과 노드 방문횟수 고려하여 선택
-UCB(Upper Confidence Bound) 정책 : UCB가 큰 것 선택
-확장(expansion)
-단말노드에서 트리 정책에 따라 노드 추가
-일정 횟수이상 시도된 수(move)가 있으면 해당 수에 대한 노드 추가
-시뮬레이션(simulation)
-기본 정책(default policy)에 의한 몬테카를로 시뮬레이션 적용
-무작위 선택(random moves) 또는 약간 똑똑한 방법으로 게임 끝날 때까지 진행
-역전파(backpropagation)
-단말 노드에서 루트 노드까지 올라가면서 승점 반영


-특징
-판의 형세판단을 위해 휴리스틱을 사용하는 대신,
 가능한 많은 수의 몬테카를로 시뮬레이션 수행
-일정 조건을 만족하는 부분은 트리로 구성하고,나머지 부분은 몬테카를로 시뮬레이션
-가능성이 높은 수(move)들에 대해서 노드를 생성하여 트리의 탐색 폭을 줄이고,
 트리 깊이를 늘리지 않기 위해 몬테카를로 시뮬레이션을 적용
-탐색 공간 축소

-제약조건 만족 문제(constraint satisfaction problem)
-주어진 제약조건을 만족하는 조합 해(combinatorial solution)를 찾는 문제

-백트랙킹 탐색(backtracking search)
-깊이 우선 탐색을 하는 것처럼 변수에 허용되는 값을 하나씩 대입
-모든 가능한 값을 대입해서 만족하는 것이 없으면 이전 단계로 돌아가서 이전 단계의 변수에 다른 값을 대입

-제약조건 전파(constraint propagation)
-인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식
최적화(optimization)
-여러 가지 허용되는 값들 중에서 주어진 기준(=목적함수)을 가장 잘 만족하는 것을 선택하는 것

-목적함수(objective function)
-기준을 나타내는 함수, 최소 또는 최대가 되도록 만들려는 함수

-조합 최적화 (combinatorial optimization)
-순회 판매자 문제(TSP)와 같이 주어진 항목들의
 조합으로 해가 표현되는 최적화 문제
목적함수 : 경로의 길이




-유전 알고리즘(genetic algorithm, GA)
-생물의 진화를 모방한 집단 기반의 확률적 탐색 기법(John Holland, 1975)
-대표적인 진화 연산(evolutionary computation)의 하나
-유전 알고리즘, 유전자 프로그래밍(genetic programming), 진화 전략(evolutionary strategy)
-최적해 보장은
-[생물의 진화]
-염색체(chromosome)의 유전자(gene)들이 개체 정보 코딩
-적자생존(fittest survival)/자연선택(natural selection)
-환경에 적합도가 높은 개체의 높은 생존 및 후손 번성 가능성
-우수 개체들의 높은 자손 증식 기회
-열등 개체들도 작지만 증식 기회
-집단(population)의 진화
-세대(generation) 집단의 변화
-형질 유전과 변이
-부모 유전자들의 교차(crossover) 상속
-돌연변이(mutation)에 의한 변이
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
생물 진화와 문제 해결의 관계
-개체 = 후보 해(candidate solution)
-환경 = 문제(problem)
-적합도 = 해의 품질(quality)

[초기 모집단 생성]
후보해(candidate solution) 표현
염색체(chromosome) 표현

모집단(population) : 동시에 존재하는 염색체들의 집합

[적합도 함수, fitness function]
후보해가 문제의 해(solution)로서 적합한 정도를 평가하는 함수

[부모 개체 선택(selection)]
높은 적합도의 개체가 새로운 개체를 생성할 확률이 높도록 함
적합도에 비례하는 선택확률
예. 개체 1의 적합도: 10, 개체 2의 적합도: 5, 개체 3의 적합도: 15

[유전 연산자, genetic operator]
새로운 개체 생성
[세대(generation) 교체]
엘리트주의(elitism)우수한 개체를 다음 세대에 유지

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

-메타 휴리스틱
-최적해(optimal solution)을 보장하지는 않지만
 준최적해(suboptimal solution)을 빠르게 찾는 알고리즘
-종류
-유전 알고리즘
-모방 알고리즘(memetic algorithm)
-입자 군집 최적화(particle swarm optimization, PSO)
-개미 집단(ant colony) 알고리즘
-타부 탐색(Tabu search) : 이미 했던건 다시 안함
-담금질 기법(simulated annealing)
-하모니 탐색(Harmonic search)


-함수 최적화(function optimization)
-어떤 목적 함수가 있을 때, 이 함수를 최대로 하거나
   최소로 하는 변수 값를 찾는 최적화 문제




-제약조건 최적화(constrained optimization)
-제약조건(constraints)을 만족시키면서 목적함수를 최적화시키는 변수값들을 찾는 문제

-최적화 순서
-Lagrange함수(제약조건 + 목적 함수 결함)정의로 시작

-기존 제약 조건 + 목적함수에 임의의 라그랑주 승수 결합

최적화 예시

-회귀(regression) 문제의 최적 함수
-주어진 데이터를 가장 잘 근사하는 함수
-최소 평균제곱법(least mean square method)
-오차 함수 또는 에너지 함수를 최소로 하는 함수를 찾는 방법



-최대 경사법(gradient descent method, 경사 하강법)
-함수의 최소값 위치를 찾는 문제에서 오차 함수의
 그레디언트(gradient) 반대 방향으로 조금씩 움직여 가며 최적의 파라미터를 찾으려는 방법
-그레디언트: 각 파라미터에 대해 편미분한 벡터 $$
-데이터의 입력과 출력을 이용하여 각 파라미터에 대한
 그레디언트를 계산하여 파라미터를 반복적으로 조금씩 조정

-활용 : 회귀모델, 신경망 등의 기본 학습 방법
-단점 : 국소해(local minima)에 빠질 위험
-해결책 : 개선된 형태의 방법 존재(conjugate gradient method 등)

지식 표현 및 추론

지식 표현
-데이터 피라미드
-데이터 (data)
-특정 분야에서 관측된 아직 가공되는 않은 것
-사실인 것처럼 관측되지만 오류나 잡음을 포함 가능
-정보 (information)
-데이터를 가공하여 어떤 목적이나 의미를 갖도록 한 것
-지식 (knowledge)
-정보를 취합하고 분석하여 얻은 대상에 대해 사람이 이해한 것
-지혜 (wisdom)
-경험과 학습을 통해서 얻은 지식보다 높은 수준의 통찰


-지식(知識, knowledge)
-경험이나 교육을 통해 얻어진 전문적인 이해(understanding)와 체계화된 문제 해결 능력
-어떤 주제나 분야에 대한 이론적 또는 실제적인 이해, 또는 현재 알려진 사실과 정보의 모음
-암묵지(暗黙知, tacit knowledge)
-형식을 갖추어 표현하기 어려운, 학습과 경험을 통해 쌓은 지식
-형식지(形式知, explicit knowledge)
-비교적 쉽게 형식을 갖추어 표현될 수 있는 지식(수학같은거)
-절차적 지식(procedural knowledge)
-문제해결의 절차 기술
-선언적 지식(declarative knowledge)
-어떤 대상의 성질, 특성이나 관계 서술(나그거알아!하는것)
-컴퓨터를 통한 지식 표현 및 처리
-프로그램이 쉽게 처리할 수 있도록 정형화된 형태로 표현

-규칙
-조건부의 지식을 표현하는 if-then형태
-직관적, 이해하기 쉬움
-신호등이 녹색일 때는 건널목을 안전하게 건널 수 있고, 빨간색일 때는 길을 건너지 말아야 한다
-대상(신호등), 속성(녹색, 빨간색), 행동(건넌다, 멈춘다) 또는 판단의 정보 추출
-표현
-IF 신호등이 녹색이다 THEN 행동은 건넌다
-IF 신호등이 빨간색이다 THEN 행동은 멈춘다
-IF trafficLight = green THEN action = cross
-IF trafficLight= red THEN action = stop
-IF 부분
-주어진 정보나 사실에 대응될 조건
-조건부(conditional part, antecedent)
-둘 이상의 조건을 AND 또는 OR로 결합하여 구성 가능
-THEN 부분
-조건부가 만족될 때의 판단이나 행동
-결론부(conclusion, consequent)
-여러 개의 판단 또는 행동 포함 가능
-인과관계
-원인을 조건부에 결과는 결론부에 표현(IF 연료통이 빈다/THEN 차가 멈춘다)
-추천
-상황을 조건부에 기술하고 이에 따른 추천 내용을 결론부에 표현
 (IF여름철이다 AND 날이 흐리다/THEN 우산을 가지고 가라)
-지시
-상황을 조건부에 기술하고 이에 따른 지시 내용을 결론부에 표현
 (IF 차가 멈추었다 AND 연료통이 비었다/THEN 주유를 한다)
-프레임
-특정 객체 또는 개념에 대한 전형적인 지식을 슬롯(slot/객체의 속성)의 집합으로 표현하는 것
 
 -패싯 (facet)
-속성에 대한 부가적인 정보를 지정하기 위해 사용


-데몬(demon)
-지정된 조건을 만족할 때 실행할 절차적 지식을 기술
-슬롯 값으로 데몬 실행조건과 데몬 이름의 쌍
-프레임의 종류
-클래스(class) 프레임
-부류(class)에 대한 정보 표현
-인스턴스(instance) 프레임
-특정 객체에 대한 정보 표현

-논리
-말로 표현된 문장들에 대한 타당한 추론을 위해, 기호를 사용하여
 문장들을 표현하고 기호의 조작을 통해 문장들의 참 또는 거짓을 판정하는 분야
-명제(Propositional logic) 논리
-참, 거짓을 분명하게 판정할 수 있는 문장
-명제를 P, Q등과 같은 기호로 표현
-정형식(well-formed formula, wff)
-논리에서 문법에 맞는 논리식
-추론(推論, inference)
-귀납적 추론(inductive inference)
-관측된 복수의 사실들을 일반화(generalization)하여 일반적인 패턴 또는 명제를 도출하는 것
-연역적 추론(deductive inference)
-참인 사실들 또는 명제들로 부터 새로운 참인 사실 또는 명제를 도출 하는 것
-긍정 논법 (modus ponens)
-부정 논법 (modus tollens)
-삼단 논법 (syllogism)
-논리 융합 (resolution)
-일반화된 추론규칙
-긍정 논법, 부정 논법, 삼단 논법의 규칙을 포함한 추론 규칙
-두 개의 논리합절이 같은 기호의 긍정과 부정의 리터럴을 서로 포함
 하고 있을 때, 해당 리터럴들을 제외한 나머지 리터럴들의 논리합절을 만들어 내는 것
-술어(predicate logic) 논리
-명제의 내용을 다루기 위해 변수, 함수 등을 도입하고 이들의 값에 따라 참, 거짓이 결정되도록 명제 논리를 확장한 논리
-존재 한정사(existential quantifier)“∃”와 전칭 한정사(universal quantifier)"∀“ 사용

-의미망(Semantic network)
-지식을 이항 관계(binary relation)의 집합으로 표현
-노드와 방향성 간선으로 구성되는 그래프를 사용해 지식 표현


-온톨로지
-시맨틱 웹(semantic web)
-웹의 데이터를 소프트웨어 에이전트가 이해하여 지능적으로 활용할 수있도록 하는 것
-의미있는 태그(tag)를 정의하여 문서를 기술하기 위해 XML 사용
-태그 및 데이터의 의미 해석을 위해 RDF 사용
-자원에 대한 메타데이터(metadata, 데이터에 대한 데이터)를 기술하는 명세(specification)
-온톨로지 구축을 통해 태그 및 메타 데이터의 의미 해석
-그림을 벡터데이터로 표현
-불확실한 지식 표현
-함수 기반의 지식 표현
-비기호적 지식표현
-기호 대신 수치값과 수치값을 계산하는 함수를 사용하여 지식을 표현
-신경망과 딥러닝
-퍼셉트론(Perceptron) : 함수식 계산 출력 생성
-다층 퍼셉트론
-서포트 벡터 머신(SVM)
-회귀(regression) 모델 등
-불확실성의 원인
-약한 관련성의 지식
-약한 인과성(weak implication)이나 애매한 연관관계(vague association)인 지식의 표현
-확신도(certainty degree) 사용 표현
-베이즈 정리(Bayesian theorem) 사용 표현
-부정확한 언어 사용
-자연어(natural language)는 본질적으로 모호하고(vague) 부정확(imprecise)
-퍼지이론(fuzzy theory) 사용 표현
-불완전하거나(incomplete) 결손된(missing) 데이터에 기반한 지식
-‘알려지지 않은 것(unknown)’으로 간주하고, 근사적인 추론(approximate reasoning) 진행
-상충되는 지식의 통합
-모순된 견해(contradictory opinion)와 상충된 지식(conflicting knowledge)의 통합
-지식 소스 별로 가중치 부여
-확신도(certainty factor)
-규칙(rule)과 사실(fact)의 신뢰정도를 [- 1,1] 구간의 값으로 표현
-1 (단정적 신뢰), -1 (단정적 불신)
-AND 작은값 OR 큰값 선택



-확률 (probability)
-조건부 확률(conditional probability)
-P(A|B): B가 주어질 때 A가 일어날 확률


독립<->종속
⇵
배반<->교


-퍼지 이론
-원소가 모임(collection)에 어느 정도 속한다는 것
-명제는 참 또는 거짓이 아니라 어느 정도는 부분적으로 참(이거나 부분적으로 거짓)
-소속정도(membership degree)는 [0,1] 범위의 실수값으로 표현