인공지능

01 Intro

The Turing test is a test, developed by Alan Turing in 1950, of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human.

• Unintelligent human behavior - 기대값이 -임에도 불구하고 복권을 사는 행위
• AI는 어떻게 보면 moving target이다 - OS가 AI로 불리던 시절도 있다.
• lisp: programming language
• 여러 technology의 collaboration 결과가 바로 deep learning이라고 할 수 있다 - 소프트웨어, 하드웨어..
• Modeling -> Algorithms의 두 단계로 real-world task를 tackle한다.
• 무엇을 풀지 정하고, 어떻게 풀지 정한다. 그 과정에선 어느 정도의 abstraction이 필요함.
• reflex-based model < state-based model < variable-based model < logic-based model 등 여러가지 모델이 있다 (low-level -> high-level 순)
• 각 모델마다 풀 수 있는/풀기 쉬운 문제의 종류가 다름
• what을 정할 때 computing이 가능할 지 안할지 고려해야 함. 따라서 how보다는 what이 대개 더 어려운 문제이다
• Learning algorithm내에서 example을 학습하고 generalization을 해야 의미가 있다. 그냥 예시만 학습(단순 암기)하면 머신러닝이 아님. 의미가없다.
• 31쪽 그림에서 node 하나하나를 각각의 state라고 한다
• 하나의 state에서 다음 state로 가는 순서가 중요한 경우에 state-based model을 사용한다. sudoku의 경우에는 그렇지 않음. 그래서 variable 측면에서 문제를 해결하는 것이 바람직함.
• 37쪽 hard constraints의 의미: 반드시 만족해야 하는 것으로 하나라도 만족하지 않으면 solve된 것이 아님.
• 반면 Bayesian network에서 soft dependencies의 의미: H1을 1분마다 차의 위치라고 하면, 여기서 위치는 반드시 만족하는 것이 아닌 단지 확률의 문제일 뿐이다
• 40쪽: 해당 문제를 variable-based 모델로 해결하려면 student를 하나하나를 variable로 표현해야하기 때문에 비효율적이다.
• 모델끼리 concept을 합쳐서 구현하는 경우도 있다

02 Reflex

• feature를 어떻게 설계하느냐에 따라 전체 설계의 성능이 달라진다. 가장 중요한 부분
• raw data보다 feature를 더 크게 사용하는 경우는 없다 왜냐하면 raw data가 주어진 데이터의 총량이기 때문
• production system: production rules로 이루어진 시스템.
• if-then으로 이루어져있다

03 Search

• 숫자판 문제에서 가능한 9!개의 상태를 하나의 노드로 생각 하면 9!개의 노드를 가진 그래프라고 생각해서 풀면 됨 - 스테이트 마다 각각 연결할 수 있기 때문 - 하지만 여기서 문제는 3*3, 4*4는 가능하지만 5*5는 불가능하다. 너무 크기 때문에
• 숫자가 움직이느냐/blank가 움직이느냐 의 차이: 32개의 액션/ 4개의 액션
• 9!개 노드가 있는 그래프를 스태틱하게 계속 가지고 있으면 비효율적임. 다이내믹하게 그때그때 필요한 부분만 빌드해서 쓰는게 중요하다 -> implicit representation
• start state는 주어질 수도 아닐수도 있다. 따라서 알고리즘 내에서 start state를 정의할 수 있어야 함
• state를 expand한다: 하나의 상태에서 다음 상태로 가능한 상태들을 계산하는 것
• 15쪽의 수도코드는 expand만 하고 지우는게 없음. 
• 20쪽의 수도코드는 좀 더 refined된 버전
• fringe: expand되지 않았지만 expand되기 위해 대기하고 있는 노드들의 집합
• goal인지 아닌지는 fringe에 들어갈 때가 아닌 dequeue 될 때(해당 노드를 expand 할 때) 판단한다
• state와 node를 혼용해서 쓰는 경우가 많다. 
• “node는 어떤 state를 나타내기 위한 것”
• search stretegy의 평가 기준
• time complexity: 만들어지는 노드의 총 수
• space complexity: 어느 한 “순간”에 메모리에 있는 최대 노드의 수. 전체 프로세스에서 만드는 총 노드의 수가 아님
• 두가지 complexity는 b,d,D의 세가지 변수로 계산할 수 있다
• b는 트리의 차수
• 23~ 26쪽 fringe의 queue (breadth-first search)
• A
• BC
• CDE
• DEFG
• 같은 레벨의 노드들(successor)간의 순서는 상관 없다
• 28쪽 
• time?: b(b^d-1) 은 트리의 d레벨의 마지막노드가 goal일 경우이다.
• 그럼 goal test를 fringe에 들어갈 때 하면 안되냐? 된다. 더 효율적임 breadth-first search에서만. 일반적인 경우에는 fringe에서 dequeue될 때 goal test를 해야 편하다 => exponential
• space?: 각 레벨에서의 노드들만 저장하고 있으면 된다. 부모 노드들(goal test가 끝난 노드들)은 잊어도 됨 => exponential
• optimal?: 가장 shallow한 노드에 대해 goal test를 먼저하기 때문에 yes.
• 29~40쪽 fringe의 stack (depth-first search)
• A
• BC
• DEC
• HIEC
• IEC
• EC
• JKC
• KC
• C
• so on
• 같은 레벨 노드 순서 역시 상관 없다
• 레벨을 계속 내려가다가 더 이상 갈 곳이 없으면 다음꺼… 반복
• 그림상에는 모든 노드가 있지만 까만색으로 색칠된 노드들은 스택에서 빠져나갔기 때문에 실제 메모리상에는 존재하지 않는다.
• 41쪽
• complete?: infinite loop에 빠질 가능성 존재
• time?: 최적의 경우 한번에 찾을수도 있지만 최악의 경우 모든 노드를 찾아봐야 할수도 => exponential
• space?: 최악의 경우 - 하나의 경로(D) * 나의 sibling(b-1) (가장 깊은 레벨의 첫번째 노드에서) => linear
• depth-first의 장점(메모리)을 살리며 단점(optimality)을 보완하는 방법: depth-limited search
• 42쪽
• limit l을 optimal depth로 정하는 것이 가장 좋다
• 하지만 optimal depth는 항상 알려진 것이 아니기 때문에 그런 경우에는 l을 작게 해보고 점점 늘려나가면 찾을 수 있다 -> iterative deepening
• limited search를 할 때 l의 범위 내에서 찾지 못하면 맨 위의 노드부터 (맨 처음부터) 다시 한다. overhead가 발생할 수도 있지만 overhead를 방지하기 위해 그 레벨의 노드를 모두 저장하면 결국 depth-first의 장점인 linear 메모리의 의미가 없어짐
• 43쪽 
• 이 그림에도 역시 스택에서 빠져나간 노드들이 그려져 있음. 실제 메모리에는 없다!
• backtracking: 하는것 처럼 보이지만, 실제 메모리는 그렇지 않음
• 44쪽
• chronological backtracking: 완전히 expand되지 않았지만 시간상 가장 최근에 만들어진(스택에 들어간) 노드로 backtrack하는 것

• 50쪽 Nids = O(b^(d+1))
• time에서 11%의 오버헤드가 발생하지만 그만큼 메모리라는 장점을 안고간다는 것에 의미를 둔다

• 51쪽 expand할 때 goal test를 해야하는 이유. link마다 cost가 있으면 더 깊은 node가 optimal goal일 수 있기 때문
• complete?: step cost가 양수나 0인 이유는 0인 루프가 있으면 infinite loop가 생길 수 있기 때문이다
• time?: C*/e 인 이유는 link 그대로 따지지 않고 step cost로 나누어서 단위 단계로 생각. (5면 1+1+1+1+1 이런식)

• 54쪽 기존 알고리즘과 다른 점은 closed에 기존 노드들을 저장. 이전 알고리즘들에선 지나간 노드들은 기억할 필요가 없었음

04 Heuristic Search

• heuristic function: 내가 얼마나 빨리 goal에 도달할 수 있는지 나타내는 함수. cost가 얼마나 남았는지. 지나온 길은 생각하지 않음. 
• 넓은 의미의 heuristic function은 evaluation function이라고 할 수 있다. 
• 숫자판 예시에서의 heuristic은 단지 추정값이고 정확하게 실제 “앞으로 얼마 남았는지”는 알 수 없다. 실제로 보면 7쪽에서 보면 5에서 6으로 간다. 따라서 그걸 따라가서 반드시 goal을 찾는다는 보장은 없다.
• 8쪽에서의 fringe는 min heap라고 생각하면 됨
• 9쪽 Greedy best-first search
• goal에 가장 가까운것 같은 node를 따라감
• Not complete라는 말 무시. 뒤에 보면 complete하다고 나와있음!
• 여태까지 본것중에 가장 비효율적인 알고리즘 같아 보인다. time과 cost를 보면
• A* search
• gb-f search가 왜 비효율적이냐면 여태 온거에 대해서는 다 까먹기 때문. 따라서 그것도 계산에 포함하면 꽤 효율적인 알고리즘을 찾을 수 있을것이다 그게 바로 a*: f = g + h
• h를 0으로 잡으면 UFS와 동일 => heuristic search라고 안한다
• 11쪽 마지막 조건: h*는 실제거리. 이 조건을 만족하는 그래프를 admissible heuristic이라고 한다
• 9쪽의 그래프에서 오른쪽애(h=4) 때문에 a* search를 쓸 수 없음
• 19쪽 앞의 핖티와 같은 알고리즘인데 expand부분이 좀 더 복잡
• successor가 처음 만드는 애면 값을 그대로 저장
• 이미 있으면 새로 계산해서 minimum한 것을 저장
• goal state의 h*값은 항상 0
• 21쪽 G는 9+0이고 C는 8+3=11이므로 둘을 비교함. G를 먼저 expand하려고 하던 중 goal test를 했는데 goal이니까 C는 expand 안하고 끝남
• h*는 우리가 아는 값. h는 정확히 알지 못하고 단지 추정하는 값일 뿐이다
• g는 expand하면서 구하는것이다. 처음부터 알려진게 아님
• 23쪽은 gbf서치를 이용하여 optimal path를 찾지 못한 예이다
• 24쪽은  a*를 이용하여 optimal path를 찾음
• 25쪽의 OPEN은 fringe임
• 둘째줄에서 h가 admissible(h* >= h)하다고 f* >= f라고 할 수 없음.
• 저렇게 말할 수 있는 이유는 f가 단조증가 하기 때문 
• admissible하면 단조증가한다(삼각형 공식)
• 어떤 노드든 expand할 때(fringe에서 뽑힐 때)에는 그 노드의 g가 optimal하다. 
• 28쪽 IDA*는 cutoff(limit)을 f로 한다
• A*는 좋아보이는데로 가면서 다 펼쳐본다면 RBFS는 가다가 아닌것같으면 backtrack해서 그 경로에 대한 정보를 기록함
• RBFS는 IDA*보다 시간을 조금 더 많이 쓰는 대신 메모리를 적게 쓴다
• SMA*: simple memory bounded a* 
• 내가 사용할 수 있는 메모리를 다 ㅏ사용함. 단 그 이상이 되면 RBFS처럼 backtrack함(가장 메모리를 많이 차지하는것을)

05 Local Search

• 그럭저럭 괜찮은 알고리즘
• 3쪽에서 hill의 가장 높은 곳(evaluation 값이 큰 곳)으로 올라가는 것이 목표 
• 지금보다 낮은 곳으로는 가지 않고, 경사가 가장 높은 곳으로 감
• 따라서 내 주변에 낮은 곳만 있을 때 종료됨 -> local optimal은 찾을 수 있지만 global optimal은 못찾을 수도 있음.
• random restart: 한번 search가 끝나면 random한 위치에서 다시 search를 진행함 (존재할 수도 있는 global optimal를 찾기 위해)
• 7쪽 simulated annealing search
• hill climbing search처럼 낮은 곳은 아예 제외하는게 아니라 확률적으로 낮은 곳으로 갈 수도 있음
• T = f(t)
• T는 temperature, t는 time, f(x)는 정하는 것
• next 위치를 랜덤으로 설정하여 현재보다 높으면 가고, 낮으면 확률을 따져서 가거나 가지 않음 
• 확률 공식을 보면 온도가 낮을수록 optimal에서 멀어질 확률이 적게 설계되어있음. 그리고 e에 대해 exponential하니까 처음에는 많이 헤메고 확 떨어져서 오랫동안 조금씩 헤매게 함 (꼭 나와있는 공식대로 쓸 필요는 없음. design issue!)
• 온도를 천천히 낮추면 global optimal을 찾을 확률이 높음
• 이론상 온도를 무한히 천천히 낮추면 global optimal을 찾을 수 있다
• 너무 복잡한 문제가 있을 때 어려운 솔루션을 찾는 대신 지푸라기 잡는 심정으로 아주 단순한 위의 알고리즘을 이용할 수 있다
• propositional satisfiability: 주어진 논리식에 0 또는 1을 대입하여 결과가 1이 나올수 있게 할 수 있는지 여부 -> SAT solver를 이용해서 해결할 수 있음 

06 Game

• 앞에서 배운것들과 달리 예측 불가능한 요소가 존재한다: 상대의 움직임, chance
• ply: 플레이어 하나의 차례. 2 ply = 1 move. move가 하나의 의미있는 단위임
• utility: 하나의 terminal state마다의 효용성(승리/패배 혹은 얻은 돈/잃은 돈)
• 보통 첫 플레이어를 max라고 함. utility를 max의 입장에 따라 정하기 때문
• Minimax: min과 max 모두 best play를 한다고 가정. 즉 max의 입장에서 상대인 min은 가장 불리한 play를 함
• dfs
• b: branching factor/m: maximum depth
• ab pruning
• 18쪽 doubles solvable depth의 의미: depth는 m, branching factor를 루트b로 줄어듬. 그냥 minimax와 같은 시간(b^m)으로 계산 한다면 depth를 2m만큼 search할 수 있다.
• random ordering은 같은 시간 안에 (4/3)m만큼 search할 수 있다
• heuristics: 같은 depth의 node들에 대해서 해당 레벨에서의 max/min한 해를 기억하고 있다
• DFID할 때 이전 iteration에서의 max/min값을 기억하고 있음
• 19쪽: quiescence search - eval값이 dynamic하게 변하는 상황 말고 잠잠한 상황에서 cut off를 한다. (병사 잡히고 다음에서 말을 먹을 수 있는 상황/병사를 먹고 다음에서 말을 잡히는 상황)
• 정확한 값일 필요 없음
• Expectiminimax
• 정확한 값이 필요
• TDGammon은 알파고같은 백개먼 게임 프로그램임. 두 수 앞을 내다본다
• Games of imperfect information
• 카드게임처럼 상대의 패를 모르는 경우에는 모든 가능성에 대한 확률을 구할 수 있다. 

07 CSP

• CSP가 아닌 constraint가 없는 일반적인 dfs에서는 pruning을 하지 않음
• CSP는 dfs의 중간 단계에서 constraint를 만족하는지 여부를 통해 pruning이 가능하다는 점이 기존의 일반적인 dfs와 비교해서 하나의 장점이 될 수 있다
• expand하지 않고 constraint를 만족하는 애들만 자식으로 삼는다
• optimization을 할 때 주로 local search를 쓴다
• 10쪽에서 root노드에 4개의 자식을 다 하지 않는 이유: symmetric하기 때문에 두개만 해보면 된다
• 밑의 예시에서는 땅이 variable, color가 value
• Minimum remaining values
• 앞에서 배운 heuristic처럼 value를 선택하는 것이 아니라 MRV를 가진 “variable”을 선택함
• 가장 남은 값이 적은 variable을 선택
• Most constraining variable
• 다른 variable에 대해 가장 많은 영향을 미치는 애를 우선적으로 선택
• 13쪽의 예에서는 다른 면과 가장 많이 맞닿아 있는 애
• Least constraining value
• 남은 variable이 최대한 다양한 value를 가질 수 있게 하는 값을 가진 애
• variable은 failure를 빨리 찾는 방향(까다롭게), value는 constraint를 만족하는 방향으로 이동
• Backtracking 효율적으로 하기 위한 것들
• Forward checking
• 남은 variable이 가질 수 있는 value들을 기록함 -> 어느 하나라도 공집합이 되면 backtrack함(가장 최근에 한 assignment를 undo)
• Constraint propagation: 공집합이 되지는 않았지만 인접한 두개가 같은 색(파랑)이 남았으므로 failure를 detect하게 함
• Arc consistency: 모든 vi에 대해 어떤 vj가 constraint를 만족한다면  vi->vj는 consistent하다고 한다
• preprocessor이나 postprocessor로 이용될 수 있음
• 따라서 assignment가 발생하면 나를 쳐다보는 unassigned된 애들이 constraint를 만족하는지 모두 살펴봐서 아니면 안되는 value를 지워서 consistent하게 만들어야한다. 
• time complexity: O(n^2 * d^3) -> 최대 n^2개의 edge가 있을 수 있음 * edge는 queue에 최대 d번 들어감 * value하나에 대해 constraint를 만족하는지 확인하는 횟수(RM-Inconsistent-Values)는 d^2
• SAT는 가장 대표적인 CSP문제이다: variable이 가질 수 있는 value는 0또는 1, constraint는 식의 결과가 1이어야 한다는 것
• 경로문제에서 어떤 경로에 대해 consistent하다는 것(path consistency)은 보장할 수 없음. pair-wise로 계산하기 때문에.
• map coloring의 경우에는 preprocessor의 의미가 없음: 맨 처음에 아무것도 색칠되지 않은 상태에서는 inconsistent한 값이 없으니까
• chronological backtracking: 가장 최근에 했던 것을 undo하는 방식
• 26쪽: local search와 비슷해 보이지만 backtracking을 하면 heuristic repair이고 현 상태만 가지고 있으면 local search임
• CSP로 풀 수 있는건 대부분 local search로 풀 수 있음

//중간고사 CSP까지

1. TF

2. A* 수도코드 잘못된 것

3. 확률 Minimax

4. NQueens forward checking + Arc consistency

5. Forward Checking + Arc Consistency

08 Learning Intro & Decision Tree

• 예전의 번역기: 어떤 언어를 하나의 언어로 바꾼후 그것을 목표 언어로 바꿈
• 현재의 번역기: 목표 언어로 바로 바꿈
• 어떤 독립적인 기능을 수행하는 단위를 agent라고 한다. 사람일수도 로봇일수도
• 3쪽
• Performance Standard는 고정하는것이 일반적.
• Problem generator: 실제 문제가 아닌 자기가 스스로 문제를 만들어보고 풀기위한 노력을 함. 여기서는 무시
• 4쪽
• representation: 어떤 알고리즘을 이용하여 학습할 것인가의 문제
• 피드백의 종류 세가지: supervised - 각각의 예제에 대해 정답이 주어짐, unsupervised - 예제에 대한 답이 없음, reinforcement - 예제에 대해 상과 벌을 줌 occasionally

• supervised learning은 대부분 inducted learning이다
• data의 pair(입력과 출력)을 보고 f에 최대한 근접하는 함수(h)을 알아내는 것이 목표
• f를 정확히 알아내려면 모든 x에 대해서 y가 일치해야 하는데 실제 상황에서 x가 유한하지 않기 때문에 모든 x에 대해서 확인할 수 없음
• training set에 없는 x에 대해서도 결과를 내는것 -> generalization
• 뭐가 중요하다고 생각하느냐(outlier가 있다고 생각하느냐 없다고 생각하느냐 등)에 따라 8쪽의 세가지 그래프 중 어떤식으로 하는게 바람직한지 달라질 수 있다. 파란색이 100% 다 맞췄다고 무조건 좋다고 할 수 없음

Decision Trees

• 테스트데이터와 디시젼트리 간에는 논리적인 비약이 존재한다
• 18쪽: 표현력과 space간에 balance가 중요
• 19쪽: default값 -> 만약 어느것에도 해당하지 않으면 설정
• DTL은 greedy(hill climbing)과 같이 행동한다
• backtracking 안함
• 현재 상태에서 Gain이 가장 큰 애를 선택
• 하나의 state를 partial decision tree로 나타냄
• 24쪽: 트리에 없는 attribute의 domain에 대해서는 don’t care로 놓은것임
• Performance Measurement(h가 f에 얼마나 가까운지)
• test set을 이용하여 검증(training set과 달라야함)
• nonrealizable -> training set이 너무 작을 경우/애트리뷰트가 없을 경우
• redundant -> 쓸데없는 애트리뷰트가 너무 많을 경우. overfitting

09 Linear Predictors

• linear predictor에 대해 배움 -> neural network
• 10쪽에서 0일경우에는 +1/-1 중 하나로 붙이면 된다
• 2차원: 직선, 3차원: 평면, n차원: hyperplane

Loss minimization

• optimization
• margin = (w*phi)*y
• 똑같이 positive라도 0.5와 1의 confidence는 다르다고 생각한다.
• 음수값이면 틀림, 양수값이면 맞음. 절대값이 클수록 얼마나 맞았고 얼마나 틀렸는지 알 수 있음
• 16쪽: 1[어쩌구]는 어쩌구가 맞으면 0, 틀리면 1을 리턴하는 함수
• residual: 실제값과 예측값과의 차이
• square loss: residual 제곱
• classification할때랑 regression할 때 무엇을 중심으로 error를 정할지 달라짐(margin/residual)
• 22쪽에서 squared loss를 사용하면 y가 최소가 되는 w값은 0, 2, 1000의 평균이고 absolute deviation을 사용하면 y가 최소가 되는 w값은 2(0, 2, 1000의 median)

Stochastic gradient descent

• squared loss를 사용할 경우 w가 하나일때는 미분해서 0되는값 찾으면 됨. 여러개일때는 변수 하나당 편미분해서 0되는값 찾음
• gradient: 기울기
• gradient descent: continuous space에서 하는 경우가 많음.
• initialize의 의미: 다 0으로 하라는게 아니라 랜덤값 넣으라는말
• hill climbing과 다른점은 모든 방향을 고려하는게 아니라 training data가 알려주는 방향으로 감
• step size가 크면 클수록 학습을 얼마나 과감하게 진행하느냐가 달라짐 -> learning rate라고 부르기도 함
• 27쪽 공식에서 변수는 w뿐이다(x, y는 주어지는것) 따라서 objective function을 w에대해 미분한 것이 gradient임
• gradient descent의 문제점: data가 엄청 많으면 한 iteration을 할 때 data를 한번 스캔해야하는데 엄청 오래걸린다. 따라서 모두 계산한 뒤에 iteration을 하지 않고 tuple하나하나 볼 때마다 iteration을 함(결과가 똑같지는 않음) -> stochastic gradient descent
• decreasing step size: simulated annealing에서 temperature과 비슷한 개념
• zero-one loss
• gradient가 항상 0이기 때문에 SGD를 이용할 수 없음. optimization은 loss에 비례해서 진행되니까
• 위의 문제를 해결하기 위해 hinge loss function을 이용
• hinge loss는 zero-one loss의 upper bound이므로 zero-one과 추구하는 방향은 같음
• 0<x<1 구간에서도 학습이 발생함
• loss가 클수록 loss를 줄이려는 노력을 더 많이함. zero one의 경우에는 줄이려는 노력이 같음 항상 1이니까
• logistic regression
• 모든 구간에서 미분 가능함
• 항상 upper bound는 아니지만 전체적으로 문제는 없음
• margin이 1을 넘어도 학습을 진행함
• SGD의 terminal condition
• 고정된 iteration 횟수를 넘길 경우
• weight update가 멈출 경우(미미할 경우)

10 Neural Network

• 여러가지 linear predictor를 합쳐서 하나의 predictor를 만드는 것. 단 합친 것이 nonlinear할 수 있게 하는 요소를 추가
• 2쪽에서 한단계로 학습하던 것(x -> y)을 3쪽에서는 두단계로 학습함(x -> h1 + h2 -> y)
• >=가 바로 NN을 nonlinear하게 만드는 요소(thresholding)
• NN에서만 할 수 있는 일이 있음. XOR은 단일 linear classification으로 학습할 수 없다
• sigmoid함수: zero-one함수를 모든 점에서 미분가능하게 흉내낸 것
• 8쪽: 1.5, -0.5, 0.5는 threshold value를 나타낸다. 1, -1은 weight.
• NN에서는 gradient descent를 backpropagation method라고 부른다
• d: desire (원하는 값)
• s: weighted sum
• f: sigmoid 함수
• ε: error
• error가 원하는값과 실제값의 차의 제곱이라고 하면 error를 s에 대해 미분한 것은 -2(d-f)
• 결과적으로 gradient만큼의 error를 고침
• 10쪽: layer간의 connection은 모두 complete bipartite하다
• k-layer feedforward network라고 함(feedback 되지 않음)
• 회색부분은 hidden layer이다
• j번째 레이어의 i번째 unit을 나타내려면 j를 위에 i를 밑에 쓴다
• threshold함수를 정하기 위해 dimension을 하나 추가하여 1로 둠 -> 11쪽에서 m(j-1)+1에서 플러스 1이 되는 이유. 1을 위해 unit이 따로 만들어주는건 아님
• 14: j+1번째 레이어의 unit들의 델타를 이용하여 j번째 레이어의 i번째 unit의 델타를 구함
• 뒤에서부터 앞으로 가면서 델타값을 결정 => backpropagation
• 15: 0인 이유는 같은 레이어의 unit들은 서로에게 영향을 끼치지 않기 때문
• train instance 하나에 대해서 각 unit별로 결과를 계산 -> backpropagation으로 weight를 업데이트
• generalization: 유한한 train set을 통해 나온 네트워크로 무한한 경우에 대한 추정값을 구할 수 있다
• 18: 일곱개의 점에 대해 함수를 구한다고 가정
• 무조건 에러가 적은 경우(high-degree)가 좋은가?
• 아님. noise가 존재할 수 있고, train data는 일부에 불과하기 때문. 따라서 train set으로 함수의 accuracy를 측정하는 것은 잘못된것.
• 그럼 전체를 모르는 상황에서 어떤 함수가 바람직한지 알수 있는가?
• 주어진 training set을 두개로 나눔: training set과 validation set -> cross validation
• k-fold cross validation: 적어도 몇번 이상을 해야 의미가 있다. 한번 하는건 의미 없음
• overfitting: 비슷한 에러를 낸다면 낮은 차수의 함수(2차원보다는 1차원 함수)를 이용하여야 방지할 수 있다
• underfitting: 데이터의 복잡도를 충분히 보장하지 않아 너무 낮은 차수의 함수로 나타내려고 하는것
• 21: validation set error 감소하는 부분은 언더피팅에서 정상으로 가는 부분, 증가하는 부분은 정상에서 오버피팅으로 가는 부분
• 앞의 모델(NN, decision tree, linear predictor…)은 parametric model(데이터에 알맞은 파라미터를 찾는 학습).
• nearest neighbor은 non-parametric
• regression이 아닌 classification에 사용
• 그냥 내가 가진 train set중 가장 가까운 애의 class를 리턴
• generalization을 한다기 보다는 storage의 문제

//과제

sigmoid함수가 1이상 -1이하일경우 그래디언트 값이 작기 때문에 convergence가 잘 이루어지지 않는다. 이것을 고치기. (= thresholding 함수바꾸기) 바꾸면 값이 제대로 안나올텐데 어떤 파라미터를 어떻게 바꾸면 잘될것이다 왜일까 생각해보기……………..

11 Supervised Learning

• binary classification을 이용하여 multi-classification을 할 수 있다
• 1인것을 classify할 때는 1인것과 1이 아닌것으로 classify하는식으로
• 5쪽에서 a의 세개 모델은 경향이 비슷, c는 세개의 경향이 모두 다르다. 경향이 다를수록 variance가 크다고 한다
• variance는 averaging하면 사라짐. bias는 averaging해도 사라지지 않음
• averaging해도 variance가 낮아지지 않으면 underfitting하고 있다고 생각할 수 있다 -> 차수를 높여서 해본다
• 모델이 덜 complex하면 bias가 있고 더 complex하면 variance가 있음 -> bias-variance간 tradeoff가 존재
• Ensemble method
• 트레이닝 데이터에 따라 디시젼 트리의 variance가 크게 달라지는것을 없애기 위해 여러가지 트리를 averaging함 (하지만 bias 감소효과는 미미)
• 트리는 트레이닝 데이터에 따라 트리가 많이 달라짐
• 하지만 다른 모델(뉴럴네트워크 등)에도 ensemble을 사용할 수 있음
• Bagging과 Boosting이 있음
• bagging은 literally sum의 의미가 아님.. 그냥 여러가지 모델의 결과를 종합하여 사용한다는 의미
• 12: I{~}의 의미 - ~가 참이면 1 거짓이면 0
• 엡실론과 알파는 반비례
• z는 normalize 하기 위한 상수
• 엡실론이 0.5보다 작을때만 이 알고리즘이 제대로 돌아감. 그래야 틀린게 많이 뽑히고 맞은게 적게 뽑힘

12 Genetic Algorithm

• genotype: 유전자 자체의 collection
• phenotype: genotype이 발현되어 나타나는것의 collection
• mutation: 유전자와 유전자가 재조합되어 발생하는 변이
• fitness: 생물이 얼마나 생존에 적합한지
• 제네틱 알고리즘: 랜덤 솔루션의 셋을 만들고 테스트 -> 비교적 안좋은 솔루션을 없애고 좋은 솔루션에 조금 변화를 주어 새로운 셋을 만들고 테스트. 베스트 솔루션이 충분히 좋을때까지 반복한다
• 19: program, fitness, crossover, mutation을 정해주어야함
• 어떻게 정하느냐의 자유도가 큼
• 8: IF(x,y,z) => x?y:z
• 9: 가장 바람직한 wall following program
• 10: 부모가 될 개체를 고르는 방법 두가지(같은 개체가 여러번 뽑힐 수도 있다)
• tournament
• proportional
• crossover rate: 몇개를 그대로 복사할 것인지 몇개를 부모에서 물려받을 것인지 비율
• crossover: 한 부모의 랜덤한 subtree를 골라 다른 부모의 랜덤한 subtree로 바꾸는것
• 고르는(바꾸는) subtree가 한개면 1-point, 여러개면 n-point
• 적절한 crossover operation은 부모의 fitness를 적절히 물려받게 해서 자식도 fitness가 좋게 나오게 하는것. 물려받아서 fitness가 다 흐트러지면 의미가 없다
• mutation: 부모의 랜덤한 subtree를 골라 “새로운” 랜덤 subtree로 바꾸는 것
• 18: 해당 세대에서 가장 fit한 개체의 fitness를 나타낸 그래프
• 장점: 어떤 문제에서도 응용 가능하다. development cost가 낮다. 결과가 interpretable하다(뉴럴네트워크와 달리)
• 단점: 느리다. optimal이 나온다는 보장이 없음

//중간2 genetic algorithm까지

13 Logic

• knowledge base: database로부터 얻어진 좀 더 high level의 정보(정보의 수준이 더 높음)
• inference engine은 domain independent하게 사용할 수 있다 - 데이터의 종류/얻어야 할 결과에 따라 다르게 만들 필요가 없다. 
• ex) watson(처음에는 퀴즈푸는애로 만들었지만 knowledge base를 바꿔서 암진단하는애로도 이용)
• knowledge base만 바꿔 끼우면 된다
• wumpus world
• 게임의 규칙과 fact(돌아다니면서 얻는 정보)의 조합이 knowledge base
• 추론(logic)이 inference engine (일반적인 과정)
• logic
• syntax: sentence의 validity를 구분하는 것
• semantics: sentence의 meaning을 정의하는 것
• x+2>y는 세살짜리 아이에게는 단순한 symbol 5개의 나열일 뿐임. symbol 각각의 의미를 알려주는것
• 어떤 world가 주어질 때 sentence가 참인지 거짓인지 판단하기 더 쉬움. 따라서 항상 world중심으로 문장을 해석한다
• entailment
• KB⊨α = “KB entails alpha” = “alpha follows from KB”
• KB가 참인 world에서 알파가 반드시 참이다라는 의미
• 이런 관계를 만족하는 알파를 찾는것이 목적임
• inference
• entailment를 계산하는 방법
• KB ⊢i α = i에 의해 알파가 KB에서 계산될 수 있다
• model
• = 참거짓을 판단할 수 있는 formally structured world
• 좁은의미: m에서 알파가 참일 경우 -> m을 알파의 모델이라고 한다
• entailment <-(sound) inference
• entailment ->(complete) inference
• 37: 여러가지 inference rule
• Modus Ponens: A과 B가 있을 때 A->B이면 B를 출력으로 내도 된다는 의미
• resolution은 거의 complete한 rule이다(resolution만 가지고 계산할 수 있는 rule이 아주 많음)
• literal = propositional variable or its negation
• 39: KB와 KB in CNF는 동치임
• *수정*: New KB: [¬P∨Q , ¬Q∨R , ¬Q∨S , ¬P∨R , ¬P∨S] 
• 41: 3번에서 negation을 가장 안쪽의 괄호까지 집어넣음
• KB⊨α이면 KB’는 inconsistent하다 -> KB’가 inconsistent하면 KB⊨α이다
• {P}, {P’}가 함께 있으면 inconsistency를 증명할 수 있다. 둘에 resolution을 적용하면 공집합이기 때문

14 Prop. Logic II

• 2쪽: 세가지 KB의 양은 똑같다. 왜냐하면 그 안에서 찾을 수 있는 것들만 추가되었기 때문
• 3쪽: modus ponens로 모든 knowledge를 얻어낼 수 없기 때문에 incomplete한 것임. complete하게 하려면
• 다음장에 나오는 것처럼 rule을 resolution으로 바꾸면 됨. 
• 만약 modus ponens를 사용한다면 horn clause를 이용하여 forward chaining을 하면 됨
• horn clause = definite clauses or goal clause
• a^b^c -> d같은 모양
• forward chaining = forward checking
• CSP문제로 생각한다면 변수 -> propositional logic, 변수가 가질 수 있는 값 -> t/f, constraint -> clause
• 기말고사에 CSP와 이걸 관련시켜서 문제가 나올 수 있다
• backward chaining
• q가 참이려면 무엇이 참이어야하는가? p. p가 참이려면? m과 l. 이것을 반복
• forward backward 모두 linear 시간 안에 가능 
• a->b = !a v b
• disjunction을 사용하면 모두 negation이 붙고 하나만 positive인 형태로 나옴
• resolution은 refutation-complete하다. 그냥 complete 하지는 않음
• 38쪽처럼 풀수도 있고 39쪽처럼 구구절절 할수도 있다..39쪽은 bfs하고 있는거임. 4번까지 이용해서 11번까지 구하고, 또 11번까지 이용해서 그 다음을 구하고. 결과적으로 search를 어떻게 하느냐의 문제임
• elimination strategies
• contradiction을 하는 데 도움이 안되는 것을 지움 
• 똑같은 문장들
• 하나의 literal로만 이루어진 것들(p만 있고 not p가 없는 경우 또는 그 반대)
• 늘 참이 되는 문장(positive와 negative가 disjunction되는 경우)
• “{p,q} 이면 {p,q,r}”에서 {p,q,r}이 없어도 됨
• restriction strategies
• 문장의 pair를 고를 때
• Unit Restriction: 둘 중 하나는 literal이 하나여야 함
• unit resolution은 일반적으로 complete 하지 않다. 하지만 빠르기 때문에 사용.
• Input Restriction: 둘 중 하나는 원래의 KB에 있어야 함
• Linear Restriction: 원래의 KB에 있거나 다른 문장의 ancestor
• Set of Support Restriction: 알아서공부하여라
• tell operation, ask operation
• 어떤 알파에 대해 확인 할 때 satisfiability를 알파에 대해 한번, not 알파에 대해 한번 총 두번 확인하면 된다
• 문제 자체가 complex하기 때문에 무슨 알고리즘을 써도 linear하게 할 수 없음
• satisfiability를 확인하는 것은 결국 해당 조건을 만족하는 모델이 있느냐의 문제이기 때문에 model checking이라고도 한다

DPLL

• 54쪽: 어떤 clause가 생기면 그 clause에 관련된 모든 clause를 확인해본다
• empty clause가 나오면 backtrack해야함
• KB의 모든 clause가 assignment를 통해 없어지면 남은 변수는 아무렇게나 assign해도됨
• KB에 하나의 literal만 남으면 1로 assign한다
• 57쪽 *수정*: DPLL(F U { (c) }, assigned) || DPLL(F U { (¬ c) }, assigned); 
• 주석: pure literal/unit clause를 제거하는 부분을 추가해도 된다는 뜻
• 61: horn clause에서 forward/backward chaining 은 linear. any clause는 NP-complete하기 때문에 exponential
• 𝑆(𝑥, y) → ¬𝐶lear(y) 이런건 propositional logic이 아님