기계학습 강좌 week 2 - 1 from Youtube

Weekly Objectives

•Learn the most classical methods of machine learning
  - Rule based approach
  - Classical statistics approach
  - Information theory appraoch
•Rule based machine learning
  - How to find the specialized and the generalized rules
  - Why the rules are easily broken
•Decision Tree
  - How to create a decision tree given a training dataset
  - Why the tree becomes a weak learner with a new dataset
•Linear Regression
  - How to infer a parameter set from a training dataset
  - Why the feature engineering has its limit

1. RULE BASED MACHINE LEARNING

1) A Perfect World for Rule Based Learning

A perfect world with

• No observation errors, No inconsistent observations

• No stochastic elements in the system we observe

• Full information in the observations to regenerate the system

Sky, Temp, Humid, Wind, Water, Forecast -> EnjoySport

완벽하게 일관적인 관찰과 행동을 하는 위와 같은 3가지에 의해 perfect world를 가정한다.

2) Function Approximation

1번에서 가정한 세계에서 

Instance : X

  Features: O:

  Label: Y:

Training Dataset : D (X를 여러 개 모아둔 것)

Hypotheses : H

  hi: -> Y : Yes

Target Function c

  알지 못하지만 h를 통해 점점 c로 가까워져야 한다.

3) Graphical Representation of Function Approximation

x1:

x2:

x3:

h1:

h2:

h3:

?들은 Y에 영향을 주지 않는다고 가정하는 것이다.

h1은 Instances들을 많이 포함하므로 일반적인 가정이고

h2,h3는 Instances들을 적게 포함하므로 구체적인 가정이다.

4) Find-S Algorithm

•Find-S Algorithm

Initialize h to the most specific in H

For instance x in D

  if x is positive

    For feature f in O

      If fiin h == fiin x

        Do nothing

      Else

        fi in h = fi in h ∪ fi in x

Return h

Instances

x1:

x2:

x4:

Hypotheses

h0=<∅,∅,∅,∅,∅,∅>

h1=

h1,2=

h1,2,4=

Instances x1,x2,x3들을 받아 가설 h를 세우는 s-알고리즘을 설명한 것이다.

h0 부터 h1,2,4 로 가면 갈 수록 가설은 구체적으로 된다.

5) Etropy

엔트로피는 ‘정보’의 단위라고 할 수 있다. 어떤 distibution p(x)에서 generate되는 discrete random variable x가 있다고 해보자. 이 random variable x가 전달할 수 있는 정보량은 어떻게 계산할 수 있을까. 여기에서 ‘정보’란 얼만큼의 bit가 있어야 x에 대한 정보를 완벽하게 얻을 수 있는가로 정의해보자. 

예를 들어서 fair한 동전 던지기의 정보량은 1이다. 한 비트만 있으면 반드시 그 동전 던지기의 distribution을 서술할 수 있다. 그러나 만약 fair coin이 아니라면 한 면이 나올 확률이 다른 면이 나올 확률보다 상대적으로 더 크기 때문에 한 비트보다도 더 적은 정보를 사용해 값을 맞추는 것이 가능해진다. 

이런 정보의 양을 Entropy라는 것으로 정의하게 되는데, 간단하게 생각하면 열역학2법칙의 그 엔트로피와 동일하다. 즉, 엔트로피가 커질수록 불확실성이 높아지고 정보량은 더 많아진다. Entropy H(p) 는 아래와 같은 공식으로 유도 가능하다.



Conditional Entropy



(출처 : http://sanghyukchun.github.io/62/)

6) Information Gain

특징은 문서에서의 출현 빈도뿐만 아니라 출현하지 않은 빈도까지 고려해서 각 범주에서의 용어 정보량을 계산한다는것이다.범주를 ( c1, c2, …, cm )라고 할 때 용어 t의 정보 획득량은 다음과 같은 식으로 구해진다.

위의 엔트로피 공식 두 개를 이용해 IG를 구할 수 있다.

7) Problem of Decision Tree

의사결정트리는 데이터 셋에는 충실하지만

real world 에서는 노이즈와 inconsistencies 때문에 잘 사용하지 않는 추세이다.