Artificial Intelligence

학기를 마무리 하며.. 기말고사 부분에 대한 간단한 정리.

• Sec 9

  • Markov Model

    • Markov assumption
      It is the presumption that the future behavior of a dynamical system only depends on it's recent history.
      
    • K-th order Makrov model
      The next state only depends on the k most receont states.
      (N gram = N-1 th order Markov model)
      

    Bigram의 Probability는 Count(Wn-1Wn)/Count(Wn-1)

    Chain rule → Markov Model에서 assuming하는 Dependencies

    Ex) P(X1,X2,X3,X4) = P(X1)P(X2|X1)P(X3|X1,X2)P(X4|X1,X2,X3)

    X3랑 X1 | X2, X4랑 X1,X2 | X3 랑 독립이라고 가정!
    

• Sec 10
  • MDP

    • MDP의 구성 요소
      1. A set of states s
      2. A set of actions a
      3. A transition function T(s, a, s')
      4. A reward function R(s, a, s')
      5. A start state
      6. Maybe a terminal state

      Transition과 Reward를 다 알고있으면 MDP의 optimal policy를 알 수 있나? → Minimax가 사실상 무한대기 때문에, 일반적인 Search Tree에서 그걸 계산하는건 불가능하다 이거지.

      그러면? → Time Limited Value를 사용해서 계산한다.

      V_0 일때는 모든 값이 0, 이후 계산 방법 = 일단 state를 쭉 적어두고, 바로 아래에 있는 stage에 있는 V-value에서 Q 값을 계산, 다시 next V value를 구함.

      Bellmane Equation

      V(s) = max_a(Q(s,a))

      Q(s,a) = sum(T(s,a,s')[R(s,a,s') + rV*(s') ])

      두개 합치면,

      V(s) =max_a(sum(T(s,a,s')[R(s,a,s') + rV*(s') ]))

  • Value Iteration
    • Time limited Value를 반복적으로 적용해서 MDP의 value를 구하는것. k=0부터 V값에 변화가 없을 때 까지 반복 실행.
  • Policy Iteration
    • Policy Evaluation
      • 정해진 action policy Pi에 대해서, 매 state마다 가능한 모든 action을 훑어 보는게 아니라, 정해진 Pi(s) action 을 취하면서 얻을 수 있는 값을 계산해서 V(s) 값으로 지정한다.
      • 매번 policy를 track하지 않음. implicit 하게 action을 계산
    • Policy Improvement
      • 매번 새로운 policy를 정함. 그게 better option
  • Reinforcement Learning MDP는 Transition과 Reward를 알고 있다(=Offline Planning).. 모르면..?(=Online Planning)
    • Exploration: 새로운거 시도
    • Exploitation: 이미 해본거 시도
    • Regret: 아~ 저기갈껄
    • Sampling: 반복적으로 시도
    • Difficulty: learning이 쉽지 않다.
  • Model-Based Learning
    • T와 R을 만들어보고, MDP를 풀듯이 해결
  • Model-Free Laarning
    • Passive Reinforcement Learning

      1. Direct Evaluation

         전체 결과 짬뽕해서 최종 결과 (V value) 구하기 → B의 Value를 구하려면, B에서 시작하고 끝나는 모든 최종 value의 average

         장점: 이해하기 쉬움, T,R 몰라도 됨, 아무튼 Correct average value는 구할 수 있음

         단점: 어떤 연속된 상황에 대한 V value가 반영되지 못함. 시간이 오래걸림

      2. Temporal Difference Learning

         각 action마다 결과를 평가함. Learning Rate a가 존재.

         V(s) = (1-a)V(s) + a[R(s,a,s') + rV(s')]

         장점: 연속된 상황에 대한 V-value가 반영됨.

         단점: V-value를 평가할 수 있을지언정, Q-value를 정할 수는 없음. 즉, 새로운 Policy를 도출하는 것은 불가능 함(Passive 특)

      3. Exponential Moving Average

         Decreasing Learning Rate → Converging Average

    • Active Reinforcement Learning

      1. Q-learning

         Q(s,a) = (1-a)Q(s,a) + a[R + rQ(s', a')]

         아오 근데 Q state유지하는게 여간 일이 아님.

      2. Approximate Q-learning

         w = w + a[difference]f(s,a)

         difference = real value - expected value

         Q-learning만큼 table유지 하지 않아도 되는 장점.

         전혀 다른 상태인데 state로만 과하게 일반화 하는 단점.

  • Sec 11
    • Linear Classifiers(= Perceptron) 3 components
      1. Feature values
      2. Weights
      3. Activation
    • Binary Decision Binary Decision을 하는 경우, 하나의 plane으로(separable 한 경우) 두 경우를 깔끔하게 나눔
      • Weight Update
        1. Starts with weights = 0
        2. Classify with current weights
        3. If correct → no change!
        4. If wrong → adjust the weight vector ( w = w + yf) y은 1 or -1
    • Multiclass Decision Rule 각각의 방향에 대한 weight vector가 있음. 즉, 3가지로 나눈다면 3가지 각각 weights를 가지고 있고, f*w 결과가 가장 큰 방향이라고 판단.
      • Weight Update
        1. Starts with weights = 0
        2. Predict with current weights (argmax y w_y*f)
        3. If correct → no change!
        4. If wrong → wy = wy - f(x)
           w = w + f(x)
    • Overfitting이 되는 경우, training set 에서의 accuracy는 증가할지언정, new-data에 대한 성능이 오히려 감소하는 경향을 보인다.
  • Sec 12

    • Case-Based Reasoning

      → Linear한 방법에서 발전되어서 Non-seperable case도 deal 할 수 있음

      • Nearest-neighbor classification (k-NN) → Non-parametic 한 방법임 1-NN: 가장 가까운 data point 따라감 k-NN: k-nearest neighbors를 따라감 K값이 크면, smooth한 function, k값이 작으면, relevent reighbor을 선택 Image에 대해서, 모든 training set이랑 digit 비교후, 가장 가까운거랑 동일하다고 classify하는 것.
        

    • Similarity Functions

      모든 similarity를 dot-product로 구할수는 없지 않느냐.

      NN이랑 Perceptron을 비교할 때

      NN은 fancy 하게 비교 가능하지만 explicit하게 learning 하는 과정은 아님

      Perceptrion은 오차를 줄이기 위해서 Learning하기는 하는데, Fancy 하게 못나눔
      

    • Kernelization
      feature 하나씩 뽑는 대신, Kernel function을 design해서 dimension의 변화를 통해 결정하는 그런 방법. 좋은데, overfitted 될 가능성도 있음

      Classification이 supervised learning이라면, Clustering은 Unsupervied learning에 해당함.

      자자. 지금까지는 supervised learning에 해당하는 classification을 봤음.

    • Clustering
      Clustering은 unsupervised learing에 해당하는데, 가장 기본적으로 K-mean 방법이 있음.

      • K-mean K-mean은 나누고 싶은 group 개수만큼 random하게 initial value를 잡고, 거기서부터 가까운거끼리 모으고, mean을 조정하는 식으로 반복해나감. converge하냐? ㅇㅇ 그게 optimal한 group이냐? ㄴㄴ hill climbing과 같이 initial value에 따라서 잘 나뉠수도, 아닐수도 있다는 점! Setting Cluster → Update Center 한무
      • agglomerative clustering Union-Find 처럼 처음에는 n개의 group이 있다고 가정할때, 가장 가까운 2개의 그룹끼리 합치는 방법. 어떤 기준으로 가까운지를 판단하냐? Min Max를 비교, Average비교, 각 element를 전부 비교하는등 다양한 방법에 따라서 이를 비교한다! → dendrogram을 만들 수 있고, 몇개로 나누고 싶은지에 따라서 dendrogram을 통해서 적당한 level에서 나누면 된다
        

    • Neural Network

      우리는 function을 계산해서 0보다 큰지, 아닌지 판단해서 적절한 result를 내보내는식으로 계산하면 된다는 것을 알았음. 근데 이걸 수학적으로 어떻게 표시할거냐?

      • Binary classifacation인 경우 sigmoid function을 써서 1/1+e^-z z가 0보다 크면 1 작으면 0이 되도록 구분

      • Multiclass classification인 경우 softmax function을 써서 제일 큰 값이 1이 되도록 함.

        NN은 여러 layer로 구성되어 있어서, 기존에 perceptron에서 어떤 feature를 잡아야할지 말지 이런 고민들을 안하고, 지가 적절한 feature를 뽑아서 계산함. 어떤 hidden layer에서 적절한 값을 뽑을 수도.

        이런 NN은 거의 모든 fuction을 만들 수 있기 때문에 XOR problem을 해결하는 또 다른 방법이며, 동시에 매우 Powerful하다. overfitting만 하지 않는다면.