/ INTERVIEW

면접 대비 - 인공지능, 기계학습 개념 복습

면접 대비를 위해서 정리한 내용을 간단히 써보고자 한다.

1. Machine Learning 정의

Well-posed learning problem by Tom Mitchell

경험(E)이 늘어남에 따라 특정 작업(T)를 수행하는 지표(P)의 개선이 이루어 질 때 기계가 학습한다고 정의할 수 있다.

2. 지도/비지도 학습, 강화학습

  • 지도 학습 - 정답과 오답이 주어져서 training set을 바탕으로 정확도 높은 함수를 학습하는 것이 목표이다. 연속적인 데이터를 바탕으로 예측하는 회귀 문제나 비연속적인 데이터를 분류하는 Classification 문제가 지도 학습의 예이다.
  • 비지도 학습 - 어떤 명시적인 정답이 주어지지 않고 데이터의 특성을 파악하는 과정이라고 할 수 있다. Clustering, Anomaly detection, association, autoencoder와 같은 문제가 해당된다.
  • 강화학습 - Agent가 가장 reward가 높은 policy를 학습하는 학습 방법이다. 이제부터 강화학습에 대해 좀 더 알아보자.

Search Problem

4가지 요소를 갖는다. - state space, successor function(action, cost), start sate/goal state
여기서 start state에서 goal state까지 도달하게 만드는 일련의 action을 solution이라고 한다.

어떤 그래프(State Space Graph) 또는 트리(Search Tree)를 탐색하는 문제에서 아무런 정보가 주어지지 않은 상태이다. DFS, BFS를 통해 완전탐색을 할 수 있다. 그래프는 각각의 상태가 한나의 노드로만 표현되기에 사이즈가 작다는 장점이 있고 트리는 상태가 여러번 등장하기도 하지만 goal state까지 하나의 고유한 path로 나타낼 수 있다는 장점이 있다.

  • Uniform Cost Search - 모든 옵션까지의 비용을 계산해서 가장 비용이 작은 노드를 확장한다.(Optimal, Complete, but Slow)
  • Gready Search - Heuristic function(goal에 가까운 정도를 예측하는 함수)에 따라 goal state에 가장 가깝다고 생각되는 node를 expand한다. Optimal한 solution을 보장하지 못한다.
  • A* Search(Best of both worlds - optimal & fast)
  • 조건: Admissible(Optimistic) Heuristic - goal까지의 true cost보다 높게(비관적인) 전망을 하지 않아야 한다.
    똑같은 node를 두번 탐색하지 않도록 Graph Search에서는 Consistency 조건이 필요하다. 하나의 arc(간선)의 비용 예측이 실제 비용보다 작아야한다. f = h + g goal에 더 가까운 지점 B보다 goal에서 먼 A가 더 먼저 fringe에 들어간다는 것을 보이는 것으로 optmiality를 증명할 수 있다.
  • Minimax는 deterministic & perfect information 게임에서 상대방이 optimal한 선택을 한다고 가정하고 상대가 나에게 가장 불리한 선택할 것을 가정한뒤 선택에 임한다. 내가 Max agent인 경우에는 상대가 선택한 최소 reward 중에서 가장 큰 것을 선택하게 되고 min agent는 그 반대로 행동할 것이다.

Pruning - 선택되지 않을 것들을 탐색에서 제외할 수 있다. 알파-베타 프루닝을 통해서 Max agent는 탐색과정에서 얻을 수 있는 최대 value(알파), Min agent는 탐색과정에서 얻을 수 있는 최소 value(베타)와 새로운 노드를 비교해서 탐색하게 되는 노드 수를 줄이는 과정을 거친다.
Minimizer: v > alpha => prune Maximizer: v < beta => prune

Expectimax는 상대방이 최적의 선택을 하지 않는다고 가정하고 확률을 도입해서 expected value가 가장 큰 노드를 선택한다.

4. Markov Decision Processes

다음 state는 오직 현재 state에 의해서만 영향을 받는다(Simplified version of the world). 즉, 미래와 과거가 독립이라는 것을 가정한다. 보상 R(s, a, s’) / Transition function T(s, a, s’) = P(s’|s, a)

  • Value Iteration Complexity - O(S^2A)

  • Bellman Equations: a Bellman equation is a recursion for expected rewards.

    Value Iteration의 문제점

    V function에는 optimal action이 포함되지 않음. 수렴하는데 오래 걸림. => Policy Iteration: action을 track하지 않아도 돼서 시간이 적게 걸림(Value iteration 둘다 one-step lookahead 개념 활용)
    Q value를 활용하면 action을 선택하기 쉬워짐

  • regret = u(possible action) - u(action taken) it converges to 0 if the strategy is good enough

MDP 아닌 경우(Model-free) 문제점

In reinforcement learning (RL), a model-free algorithm (as opposed to a model-based one) is an algorithm which does not use the transition probability distribution (and the reward function) associated with the Markov decision process (MDP)
R, T를 모름

해결책: Q-Learning

Q-values를 활용: action을 선택하고 그에 따른 reward에 맞춰서 Q-value를 업데이트 해줌.

Q-Learning의 문제점

비슷한 노드끼리 서로 다르게 보기 때문에 탐색과정을 일일이 거쳐야 한다는 단점. 따라서 feature를 이용해서 state를 일반화해주는 것이 가능하다. => Feature-Based Representation & Approximate Q-Learning

5. Naive Bayes 및 확률 기초 개념 정리

1) random variable - 확률적인 과정에 따라 값이 결정되는 변수(오메가 -> E로의 mapping)
2) 조건부 확률 - 주어진 사건이 일어났다는 가정 하에 다른 한 사건이 일어날 확률을 뜻한다.
3) Chain rule
4) Bayes Theorem
5) MLE
6) MAP
7) 조건부 독립 - p(a|b,c)=p(a|c), 즉 b, c가 있거나 없거나 a의 확률에 영향을 미치지 않는다. 8) Naive Bayes- 조건부 독립을 가정하면 c의 prior와 c와 다른 사건의 조건부 확률의 곱 또는 log합으로 나타낼 수 있다.
장점은 단순하고 빠르다는 것이 있으나 independent하지 않을 경우 bias 문제에 빠질 수 있으며 pattern을 모델링 할 수 없다는 문제가 있다. 따라서 정확도도 낮은 편이다.

6. 기계학습 정리

  • Overfitting 방지를 위한 regularization term 추가

  • Backpropagation

  • A support vector machine (SVM) is a supervised machine learning model that uses classification algorithms for two-group classification problems. After giving an SVM model sets of labeled training data for each category, they’re able to categorize new text.

  • Kernel Trick - Kernel function(similarity function)은 높은 차원의 내적을 의미한다. K(x_i,x_j)로 구성된 행렬은 positive semi-definite matrix여야 하며 대칭행렬(symetric matrix)이어야 합니다.

  • PCA - eigenvalue decomposition of covariance matrices

7. 딥러닝

  • CNN - In deep learning, a convolutional neural network (CNN, or ConvNet) is a class of deep neural networks, most commonly applied to analyzing visual imagery.

  • RNN - A recurrent neural network (RNN) is a class of artificial neural networks where connections between nodes form a directed graph along a temporal sequence.