김영진

Greedy Best First Search

• Heuristic function의 평가 값이 제일 좋은 Node 부터 탐색한다. 

$A^*$ 알고리즘

• $f(n) = g(n) + h(n)$
  • $g(n)$은 현재 노드까지 오는데 사용한 비용
  • $h(n)$은 Heuristic Function의 평가값 
• admissable
  • 휴리스틱 함수가 실제 Cost보다 언제나 작거나 같게 예측을 하는것 
• Admissable한 Heuristic Function을 쓰는 $A^*$알고리즘은 언제나 최선의 솔루션을 구한다. 

• Thinking $ \longleftrightarrow $ Acting
  • 사람의 생각을 구현하느냐, 사람의 행동을 모사하느냐 
• Humanly $ \longleftrightarrow $ Rationally
  • 사람처럼 행동하느냐, 합리적으로 행동하느냐 

• 인공지능의 영역
  • Sensing : 음성 인식, Vision 등 감지에 관한 영역
  • Thinking: Knowledge Represenation 등
  • Acting : Speech, Robotics 등 행동에 관한 영역

• 약 인공지능 : 사람이 어떤 task를 정해놓고, 어떤 행동을 해야할지 프로그래밍 하는 인공지능 ex) 알파고
• 강 인공지능 : 사람의 지능에 준하는 혹은 그 이상의 인공지능. 자유의지 , 자각등을 갖춰야함 

• Diagonalization Problem 
  • $ A = N*N , P =N*N, D $는 대각행렬일때 $A = P*D*P^{-1}$을 만족하는 $A$가 존재하는가
    • 대각행렬이란 대각선에만 숫자가 있는 행렬
    • 모든 $A$가 가능한 것은 아니다. 
    • Lineary Independent한 N개의 Eigen Vecotor가 존재하는 $A$만 성립한다.
    • $ P= \begin{bmatrix}X^{1} & X^{2}&  \cdots  & X^N \end{bmatrix} $
      • $X^i$는 1*N 벡터이다 
    • $ D= \begin{bmatrix} \lambda^{1} & 0&0&0 \\ 0&\lambda^{2}&0&0\\0&0& \ddots &0 \\ 0&0&0 & \lambda^N \end{bmatrix} $
      • 각각의 \lambda 는 Eigen Value를 의미한다.
• Transpose Matrix 
  • $ A^T : A $의 행과 열을 바꾼 것 
• Symmetric matrix
  • $A = A^T$ 를 만족하는 행렬 
  • A의 모든 수가 실수이면 A의 Eigen Value는 모두 실수
  • 반드시 N개의 서로다른 Eigen value를 가지고 있다.
• Unit Norm
  • $ \| X  \|  = 1$ 을 만족하는 X
  •   $X = \begin{bmatrix} x_1 \\x_2 \\  \vdots \\x_n \end{bmatrix} $ 일때 $\| X  \|  =  \sqrt{{x_1}^2 + {x_2}^2 +\cdots+{x_n}^2 } $
• $A$가 Diagnoalised Matrix 이면 $A^M$ 을 쉽게 구할 수 있다. 
  • Deep Learning에서는 연산을 여러번 반복하기 때문에 행렬곱을 빠르게 구할 수 있는 것이 좋다. 
  • $A^M = PD^MP^{-1}$ 
  • $ D = \begin{bmatrix}a & &  \\ & b & \\ & & c \end{bmatrix}$ 이면 $
    D^M = \begin{bmatrix}a^M & &  \\ & b^M & \\ & & c^M \end{bmatrix} $ 이다. 

• 1X1 행렬에서 Determinant
  • $A =  \alpha $ 이면 $det(A) =  \alpha $
• NXN 행렬에서 Determinant 일반식
  • $det(A) =   \sum_{j=1}^N  (-1)^{I+j}  *a_{Ij} *det( A_{IJ}) $
  • $A_{IJ}$ 는 A에서 I 행과 J 열을 지운 행렬 
• Row Operation을 수행한 두 행렬 사이의 determination은 다음과 같은 관계를 가진다. 
  • $ R_{i}  \rightarrow R_{j}$
    • $det(B) = -det(A)$
  • $ R_{i}  \rightarrow  \alpha  R_{i} +  \beta R_{j}$
    • $det(B) = \alpha * det(A)$
• $det(AB) = det(A) * det(B)$

• Eigen Value Problem
  • $A = N * N , X = N*1 $ 행렬일때 $A*X = \lambda *X $를 만족하는 실수 혹은 복소수 $\lambda$ 를 찾는 문제
  • $ A*X = \lambda * I * X $ 이므로 $(A-\lambda*I)X = 0 $ 으로 바꿀 수 있다. 
  • $det(A-\lambda*I) =0 $ 을 만족하는 $\lambda$ 를 찾는 문제