정리 블로그

1. Data Mining
 - 목표는 방대한 양의 데이터 속에서 의미있는 지식을 찾아내는 것

2. Metadata
 - 데이터에 대한 데이터, 특정 데이터가 어떤 것의 데이터 인지 정의한 data

3. Supervised Learning
 - 사람이 지도하는 방식
 - Data Mining 방법 중 하나로 주된 방법으로 classification이 있다.
 - classification은 특정 데이터의 카테고리를 찾는 방법이다.
 - KNN 알고리즘 : 특정 데이터를 뽑았을 때 가까운 데이터를 범위 k만큼 골라내는 방식으로 카테고리를 나눌 수 있다

4. Unsupervised Learning
 - 사람이 개입하지 않는 방식
 - label data 없이 가장 그 data를 잘 설명할 수 있는 cluster를 찾는 문제이다.
 - K-means : 특정 cluster 내에서 자신을 제외한 다른 data와 차이가 가장 작은 값을 가지는 데이터를 뽑아내는 알고리즘

5. Machine Learning
 - explicit programming(사람이 개입해 개발)의 제한으로 나타남
 - data mining 처럼 supervised와 unsupervised, reinforcement 이렇게 3가지 방법이 있다.
 - Data로 새로운 rule을 생성하는 방식
 - 실제 데이터 값과 rule의 값을 비교해서 그 비교 값의 제곱을 비교해 그 값이 가장 적은 rule을 채택한다.

1. Agent System
 - Agent : 특정 사람의 일을 대신할 수 있는 전문성을 지닌 사람을 의미
 - Agent System은 이런 Agent의 기능을 수행하는 컴퓨터 시스템을 의미

2. Conversational Animated Agents
 - 대화가 가능한 가상의 대리인을 의미

3. Joseph Wiezenbaum
 - 자주 쓰이는 대화 문장을 정리해 사용자가 입력한 문장에 대한 대답을 할 수 있도록 rule을 만든 사람
 - Eliza : rule을 이용해 만든 대화형 에이전트
 - 동작 방식 : 문장을 받아들여 키워드를 체크하고, 문장의 형태를 분석한다.
                  질의의 주어와 목적어를 바꾸는 방식으로 대답
                  전의 문장의 내용을 기억하는 부분이 없기 때문에 전의 대화 내용과는 상관없는 대답이 나올 수 있다.
                  특정 문장 형식에도 대답하는 문장 형식을 여러개 만들어 랜덤으로 다양하게 출력할 수 있다.

1. Semantic Web
 - '의미론적 웹'이란 뜻으로 인터넷에 있는 정보를 컴퓨터가 이해할 수 있도록 Ontology형태로 표현하고 이를 처리하도록 하는 프레임워크이자 기술.

2. Resouce Description Framework(RDF)
 - Ontology 형태로 표현하는 규격 중의 하나이다.
 - triple 속성을 가지며 subject, predicate, object를 가진다
 - 각각 관계 주체, 관계, 관계 대상을 나타내며, 해당 테이블을 이용해 Directed Graph를 만들 수 있다.
 - 해당 정보들을 여러 군데서 받아 하나의 graph를 생성할 수도 있다.

3. RDFS(Resource Description Framework Schema)
 - RDF Schema Language로써, RDF의 스키마를 정의

4. Ontology
 - RDF 등 semantic web에서 컴퓨터가 파악할 수 있는 자료를 표현하는 것

5. DBPedia
 - WikiPedia의 Box 정보를 가져 올 수 있는 저장소

1. Propositional logic
 - 명제 논리
 - 서술문으로서 그 내용에 대해 참이나 거짓을 담고 있는 문장

2. Predicate logic
 - 술어 논리
 - 명제 논리를 기반으로 기호화시켜 관계를 나타낼 수 있고, 기호를 통해 수량도 나타낼 수 있게 한 것

3. Quantifier
 - 정량자, 전체 정량자(∀), 존재 정량자(∃) 두가지가 있다.
 - ∀ : 전체 정량자, '모든'
 - ∃ : 존재 정량자, '일부'

4. First-order logic
 - 일차 술어 계산
 - 술어 계산에서 정량자가 변수에만 적용되고, 술어나 함수에 대해서는 적용되지 않는 경우

5. Conversion to clause form
 1) implication 제거
  ex) p -> q = ￢p ∨ q
 2) 부정의 범위를 줄임
  ex) ￢(∃x)P(x) <=> (∀ㅌ)(￢P(x))
 3) 변수의 변환
  ex) (∀x)[P(x) -> (∃x)Q(x)] <=> (∀x)[P(x) -> (∃y)Q(y)]
 4) 정량자를 제거
  ex) (∀x)[(∃y)P(x, y)] <=> (∀x)P(x,F(x))
 5) prenex form 변환
  ex) (∀x)[P(x) -> (∀y)Q(y)] <=> (∀x)(∀y)[P(x)->Q(y)]
 6) global 정량자 제거
 7) ∧ 제거
 8) 변수 이름 재정의

6. Resolution in Propositional logic
 Given Axioms         Conversion to clause Form
   P                         P
   (P∧Q)->R              ￢P ∨ ￢Q ∨ R
   (S∨T)->Q              ￢S ∨ Q 
   T                         ￢T ∨ Q  
                              T

  To Prove R,
  ￢P ∨ ￢Q ∨ R                   ￢R
            └─────────┘
                      ￢P ∨ ￢Q                      P
                            └─────────┘
                                         ￢Q                     ￢T ∨ Q  
                                           └─────────┘
                                                        ￢T                          T
                                                          └─────────┘ 
                                                                       □        -------------> R 증명 완료

7. The Most General Unifier
 - 술어 논리에서 variable의 value를 최대한 정해주는 집합
 - UNIFY 함수를 호출하면 반환해준다.

8. Procedural Knowledge
 - 사람이 instruction의 순서를 정해준다.

9. Declarative Knowledge
 - 사람이 순서를 정해주지 않아도 컴퓨터가 스스로 순서를 정해서 수행한다.
 - 모든 가짓수를 계산해 맞는 답을 찾음
 - 사람이 instruction의 순서를 정해주는 것은 cost가 크므로 Declarative 방식이 유리할 때가 있다.

10. Closed World Assumption
 - 닫힌 세계이므로 현재 명시된 명제로 추론이 불가능하면 그 명제는 거짓이 된다.

11. Open World Assumption
 - 열린 세계이므로 현재 명시된 명제로 추론이 불가능 하다면 그 명제는 알 수 없는 명제가 된다.

1. Constraint Satisfaction Problem
 - Variable과 Domain 사이의 제약조건을 통해 미리 Variable에 대한 Domain을 제한하여 수행 속도를 올리는 방법

2. Map-Coloring Problem

 - 위처럼 나눠져 있는 지도에서 3개의 색으로 인접한 구역의 색과 겹치지 않도록 칠하는 방법이 있는지를 구하는 문제
 - Constraint graph를 통해 인접하는 구역을 표현할 수 있고, 해당 그래프를 이용해 색칠 하는 것이 가능

3. Varieties of Constraints
 - Variable의 수에 따라 분류 가능
 - Unary constraints : 하나의 변수를 특정 도메인으로 제약하는 Constraint
 - Binary constraints : 두개의 변수로 제약하는 Constraint
 - higher-order constraints : 3개 이상의 변수로 제약하는 Constraint

4. Cryptarithmetic

       T W O
    + T W O
    -----------
     F O U R
 - 같은 문자의 경우 같은 숫자이며 해당 연산 결과와 맞는 경우가 있는지 찾는 문제
 - Constraint를 정의하여 문제 풀이 가능

5. Real-world CSPs
 - Assignment Problems : 누가 어떤 과목을 강의 할지
 - Timetabling problems : 어떤 class를 언제 어디서 강의 할지
 - Transportation scheduling : 배송을 효율적으로 하는 방법

6. Backtracking search
 - 가능한 경우의 수를 모두 해보는 방식으로 graph에서 dfs방식으로 탐색.
 - 모든 경우의 수를 탐색하므로 정확한 결과를 얻을 수 있지만 필요 없는 계산이 너무 많음.(Cost가 높다)

7. Most constrained variable
 - 가장 단순한 방법으로 가능한 경우의 수 중 가장 빠른 것 부터 적용하는 방법

8. Most constraining variable
 - 가장 많은 연관성(제약)을 가진 곳부터 Domain을 할당하는 방식

9. Least constraining value
 - Domain 중 영향을 가장 적게 주는 value를 선택하는 방식.

10. Forward checking
 - 특정 variable의 value를 정해주고 난 뒤, constraint에 의해 value가 선택되지 않은 variable의 domain이 바뀌게 되는데,
   바뀔 때 마다 Domain을 바꿔 주어서 연산을 줄이는 방식

11. Arc consistency
 - 특정 Variable의 value가 정해졌을 때, constraint에 의해 value가 선택되지 않았을 경우 variable의 domain이 바뀌게 되고,
   해당 Domain의 남은 수가 1개일 경우 해당 value만 가능하므로 이 value를 선택했을 경우를 가정해 다시 Domain을 계속 줄여나가는 방식
 - AC-3 알고리즘이라고 불린다.

1. Game Playing

 - Game Playing은 AI research의 좋은 문제이다. 

 - 결과가 간단하고, 평가하기 쉽다.

 - 특정 시간 안에 decision making을 해야 한다.

2. Game Playing as Searching

 - 두 명이서 하는 턴제보드게임일 때

 - states          : 보드의 상태

 - operators     : 규칙에 맞게 움직이는 경우들

 - initial state    : 현재의 보드 상태 

 - goal state     : 최종적으로 이기거나 지는 상태

3. Minimax Algorithm

 - 현재  상태에서 수행 가능한 operator로 진행했을 때, AI 턴일 때는 점수가 가장 높은 쪽으로, 상대방 턴일 때는 점수가 가장 낮은 쪽으로 가도록 한다.

1) 0 번위치가 현재 보드 상태라고 가정하고, depth는 4까지 탐색한다.

    (네모는 AI의 선택으로 움직일 수 있는 상태들, 동그라미는 상대의 선택으로 움직일 수 있는 상태들이다.)

    (각 네모, 동그라미 속 숫자는 클수록 AI에게 유리하다.)

 2) 왼쪽으로 계속 내려가서 4의 가장 왼쪽 노드까지 내려간다. 10과 무한대를 비교

 3) 3에서 4로 갈때는 상대의 선택이므로 AI에게 가장 불리한 선택을 한다고 가정하고 10을 선택한다.

 4) 그 뒤, 오른쪽을 탐색하고 5라는 결과를 불러온다.

 5) 2에서 3은 AI의 선택이므로 5와 10 중 더 큰 값을 가져온다.

 6) 위 과정을 계속 반복하면 -7이 가장 크므로 -7 쪽으로 움직인다.

4. Alpha-Beta Pruning

 - Minimax algorithm을 기반으로 더 빠르게 노드들을 탐색하기 위한 알고리즘

 1) Alpha Cutoff

   a) 처음 D와 E를 비교했을 때, D가 더 작으므로 B는 5가 된다. ( alpha = 5 )

   b) 그 다음 오른쪽으로 내려가서 F를 탐색한다.

   c) C는 F와 G 중에서 작은 수를 가져온다. F가 4라면 G가 어떤 수라도 C가 4보다 클 수 없다.

   d) 이미 alpha값이 5이므로 C는 4를 가져오고 G를 보지 않는다.

 2) Beta Cutoff 

   a) 처음 H와 I를 비교했을 때, I가 더 크므로 D는 5가 된다. ( beta = 5 )

   b) 그 다음 오른쪽으로 내려가서 J를 탐색한다.

   c) E는 J와 K 중에서 큰 수를 가져온다. J가 10라면 K가 어떤 수라도 E가 10보다 작을 수 없다.

   d) 이미 beta값이 5이므로 E는 10를 가져오고 K를 보지 않는다.

Genetic Algorithm

1. n-Queen Problem

 1) 문제 정의 : N x N 크기의 체스판이 주어질 떄, N개의 퀸이 서로 공격이 불가능하도록 놓는 경우를 구하는 문제

 2) ex : N = 4

2. Genetic Algorithm

 1) Fitness function으로 Fitness 검사 : 어느 정도 해에 가까운지 수치값으로 나타내는 함수로 수치값을 계산

 2) 검사된 결과 중 가장 높은 값은 두 개, 다음 높은 순으로 두 개를 뽑아 서로 형질을 바꾼다.(유전)

 3) 거기에 랜덤(자리, 번호 둘다)으로 형질을 바꿔준다.(돌연변이)

   ex) ①( 3 3 4 2 )   4  4/7      ①( 3 3 | 4 2 )           ( 3 3 | 1 2 )          ( 3 ① 1 2 )

        ②( 1 2 1 2 )   1  1/7      ②( 1 2 | 1 2 )           ( 1 2 | 4 2 )          ( 1 2 4 2 )

        ③( 1 2 3 4 )   0  0/7      ①( 3 | 3 4 2 )           ( 1 | 3 4 2 )          ( 1 3 4 ④ )

        ④( 1 1 1 3 )   2  2/7      ④( 1 | 1 1 3 )           ( 3 | 1 1 3 )          ( 3 1 ③ 3 )

               ⓐ                                ⓑ                       ⓒ                      ⓓ

   ⓐ         : Fitness 검사 : 두개씩 퀸을 페어로 봤을 때 서로 공격이 불가능 한 페어의 개수를 센 값이 클수록 Fitness가 높다.

   ⓑ ~ ⓒ  : 유전 나누는 구간을 랜덤으로 정해 서로 바꾼다(위 예제에선 ①이랑 ②, ③ 이랑 ④를 바꿨다)

   ⓓ         : ⓒ가 끝난 뒤, 특정 지점의 번호를 바꿔준다.(돌연변이)

3. 장단점

 1) 장점

   ① 거의 최적에 가까운 해(near optimal)를 빠르게 찾아낼 수 있다.

   ② parallel 작업이 가능하다

 2) 단점

   ① 어떤 방식으로 최적을 구했는지 재현이 거의 불가능하다.

1. Generate-and-Test

 - 단순히 풀이법을 만들어 실험해보는 방식

 1) 해결 가능한 Solution을 생성한다. 

 2) Solution이 맞는지 Test한다.

 3) 해결되면 그만두고, 실패하면 다시 1번으로 돌아간다

2. Hill Climbing

 - 현재 노드에서 가장 evaluation function 결과가 좋은 노드로 이동해 나가다가 더이상 좋은 노드가 없거나 goal state에 도착시 멈춤.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 그 중 가장 높은 evaluation 값을 가진 노드로 이동

    만약 가장 높은 evaluation도 현재 evaluation보다 작다면 움직이지 않는다.

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

3. Steepest-Ascent Hill Climbing

 - 현재 노드에서 가장 가파르게 evaluation 값이 상승하는 노드로 이동한다.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 그 중 가장 많이 증가한 evaluation 값을 가진 노드로 이동

    만약 가장 많이 증가한 evaluation도 현재 evaluation보다 작다면 움직이지 않는다.

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

4. Best-first search

 - 현재 펼쳐진 노드( evaluation을 평가했던 노드 )들 중에서 가장 큰 노드로 이동한다.

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 한다.

 2) 현재 펼쳐진 노드 중 evaluation 값이 가장 높은 노드로 이동

    evaluation 값이 가장 높은 노드가 없다면 움직이지 않음

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로

5. A* Search

 - 현재 펼쳐진 노드 중 evaluation 값과 start state에서 현재 노드까지 이동하는데 필요한 비용을 더한 값이 가장 작은 노드로 이동한다.
    f(n) = g(n) + h(n)   (f(n) : 총 값, g(n) : 현재 노드까지 이동하는데 소요된 비용, h(n) : goal state 까지 소모된다고 예측되는 비용)

 1) 현재 노드에서 갈 수 있는 노드들을 evaluation 하고, 현재 노드까지 소요된 비용을 더한다.

 2) 현재 펼쳐진 노드 중 계산된 값이 가장 높은 노드로 이동

    계산된 값이 가장 높은 노드가 없다면 움직이지 않음

 3) 현재 노드가 goal state인지 확인, goal state 라면 끝, 아니면 다시 1로 

6. Heuristic function estimate

 - Heuristic function을 overestimate 하지 않는 이상 admissible하다고 본다.

 - 만약 underestimate 하다면 optimal하지만 시간이 오래걸린다.

- AI 수업 내용 정리

1. Intelligent Software Agent

 1) 용어 정리

   - Agent : 특정 할 일을 대신 해주는 대행자

   - Intelligent Software Agent : 인공지능 소프트웨어가 할 일을 대신해 주는 것

 2) Intelligent Software Agent란?

   - Environment에서 다양한 Sensor를 통해 들어온 정보를 percept 한다.

   - percept된 정보를 토대로 정의된 State를 찾는다.

   - State에서 가능한 Action 중 Goal에 가까워 질 수 있는 Action을 Actuators로 실행.

   - Goal 도달!!

 3) 예시

   - 의료 진단 시스템( 암 진단 등... )

   - 웹 쇼핑 프로그램( 필요한 상품 추천 등... )

2. Particular Problem

 1) 문제를 정확히 정의한다

 2) 문제를 분석한다

 3) 문제를 풀기 위해 필요한 정보를 분리해낸다.

 4) 최적의 풀이기법을 정한뒤 Particular Problem에 적용시킨다

3. State space Search로 Problem을 정의하는 법

 - state를 정의

 - 가능한 모든 state set(state space)을 정의

 - 시작 state와 목표 state 정의

 - state의 전이 정의

4. water jug problem

 1) 문제 정의

   - 2개의 눈금 없는 주전자가 있고, 하나의 주전자는 4gallon, 하나의 주전자는 3gallon을 담을 수 있다.
     이 떄, 한 주전자에 4gallon 주전자에 2gallon의 물을 담을 방법은?

 2) State 정의

   - S(x, y)

   - x = 0, 1, 2, 3, 4 (4 gallon 주전자)

   - y = 0, 1, 2, 3    (3 gallon 주전자)

   - start state : S(0, 0)

   - goal state : S(2, y)

 3) production Rule

   - (x, y) if x < 4 then (4, y) : fill the 4-gallon jug

   - (x, y) if x < 3 then (x, 3) : fill the 3-gallon jug

   - .... etc 이런식으로 정의

   - 상태 전이의 룰을 정의, 순서가 없다

5. MC problem

 1) 문제 정의

   - 3명의 식인종과 3명의 선교사가 강변에 있다. 모두 다 배를 타고 반대편 강변에 도착해야한다.
     하지만, 배의 승선 가능 인수는 2명이고, 만약 식인종이 선교사보다 수가 많다면 선교사는 죽임을 당할 수 있다. 
     이 경우, 모두 다 살아서 강을 건너는  방법은?

 2) State 정의

   - S(Can_Left, Miss_Left, BoatPos, Can_Right, Miss_Right)

   - Can_Left = 0, 1, 2, 3 ( 왼쪽 강변의 식인종 수 )

   - Miss_Left = 0, 1, 2, 3 ( 왼쪽 강변의 선교사 수)

   - Boat_Pos = Left, Right ( 현재 배 위치 )

   - Can_Right = 0, 1, 2, 3 ( 오른쪽 강변의 식인종 수)

   - Miss_Right = 0, 1, 2, 3 ( 오른쪽 강변의 선교사 수)

 3) Production Rule

   - (Can_Left, Miss_Left, Left, Can_Right, Miss_Right)
     : if Can_Left > 0 && Miss_Left > 0 then (Can_Left-1, Miss_Left-1, Right, Can_Right+1, Miss_Right+1) - Move-1m1c-lr

   - (Can_Left, Miss_Left, Right, Can_Right, Miss_Right)
     : if Can_Right > 0 && Miss_Right > 0 then (Can_Left-1, Miss_Left-1, Left, Can_Right-1, Miss_Right-1) - Move-1m1c-rl

6. Production systems

 1) 정의해야 할 것들

   - global databases 정의 = state space를 정의한다.

   - production rule을 정의

   - control strategy를 정의( 탐색 방법을 정한다 )

 2) control strategy

   - 가장 첫번쨰를 적용한다

   - 랜덤으로 룰을 적용한다

   - dfs를 이용한다

   - bfs를 이용한다

  3) heuristic search

   - 효율적으로 search를 하게 해주는 방법 ( 탐색을 줄여준다 )

   - heuristic evaluation function을 이용해 탐색의 조건을 추가해준다.

https://github.com/open-korean-text/open-korean-text

트위터에서 개발한 한국어 분석기!

이건 또 메이븐 프로젝트이다...

1. https://maven.apache.org/download.cgi

메이븐 다운로드를 해주자.

2. 메이븐을 설치하고픈 폴더에 설치 후 환경설정 값 저장하기

3. cmd에서 확인하기

mvn --version

이라고 명령어를 넣어서 아래처럼 뜬다면 설치 성공

4. 이젠 IntelliJ 설치

https://www.jetbrains.com/idea/#chooseYourEdition

가난한 학생이므로 Community를 받자.

next의 연속.jpg

5. https://github.com/open-korean-text/open-korean-text

여기서 프로젝트를 다운받자.

6. IntelliJ에 임포트!

7. pom.xml 파일을 선택해주면 알아서 maven 프로젝트라 인식한다.

8. Next...

9. reimport!

10. mvn test

입력하기

11. 결과 출력이 됨

Test라고 된 부분에 출력이 된 것을 볼 수 있다.

소스 분석은 이후에...