규칙 기반(Rule-Based) Machine Learning 기초

in Data on Machine-Learning


카이스트 문일철 교수님의 인공지능 및 기계학습 개론1 2주차 강의를 보고 정리한 포스팅입니다!

Machine Learning

  • 경험(experience)에 의해 학습(learning)
  • Task에 대해 점점 더 잘 실행되도록!
  • 많은 경험이 있다면 더욱 잘 될 것입니다(=데이터가 많아지면!)

Example Task

  • EnjoySPT를 예측하는 Task
SkyTempHumidWindWaterForestEnjoySPT
SunnyWarmNormalStrongWarmSameYes
RainyColdHighStrongWarmChangeNo

가정

  • 우리는 Perfect World에 살고 있습니다
    • 관측의 error는 없고, 일관적이지 않은 관측도 없습니다(=일관적이다)
    • random effect가 없습니다
    • 해당 factor로 상황을 완벽히 설명할 수 있습니다

Function Approximation

  • Task를 잘 소화할 수 있는 함수를 만들어야 합니다!
  • Instance, X
    • Feature(Input) : Sunny, Warm, Normal, Strong, Warm, Same
    • Label(Y) : Yes
  • Training Dataset, D : 인스턴스의 관측값 모음들
  • Hypothesis, H
    • \(h_{i}\) : <sunny, warm, ?, ?, ?, Same> -> Yes!
    • < >의 조건이면 Y다!
    • 가정의 개수는 64+@(don’t care)
  • Target Function, C : 알지 못하지만 목표로 하는 함수(데이터를 보고 알아내야 합니다)

다음과 같은 가설 \(h_{1}, h_{2}, h_{3}\) 3개와 관측값 \(x_{1}, x_{2}, x_{3}\)이 있습니다

\(h_{1}\) : <Sunny, ?, ?, ?, Warm, ?>
\(h_{2}\) : <Sunny, ?, ?, ?, Warm, Same>
\(h_{3}\) : <Sunny, ?, ?, Strong, Warm, ?>

\(x_{1}\) : <Sunny, Warm, Normal, Strong, Warm, Same>
\(x_{2}\) : <Sunny, Warm, Normal, Light, Warm, Same>
\(x_{3}\) : <Sunny, Warm, Normal, Strong, Warm, Change>

\(x_{1}\)은 가설 \(h_{1}, h_{2}, h_{3}\)에 모두 맞지만, \(x_{2}\)는 가설 \(h_{3}\)에 맞지 않습니다. \(h_{1}\)는 널널한 가설이며 \(h_{3}\)는 까다로운 가설입니다

이것은 Generalization vs Specialization 문제와 연결됩니다

Find S 알고리즘

간단한 Find S 알고리즘을 다음과 같이 정의하겠습니다

For instance x in D
  if x is positive
    for feature f in O
      if f_{i} in h == f_{i} in x
        Do nothing
      Else
        f_{i} in h = f_{i} in h U f_{i} in x
return h

조금 더 쉽게 설명하면, 첫 가설은 Null Hypotheses로 만듭니다.
\(h_{0}= <\phi, \phi, \phi, \phi, \phi, \phi>\)
\(x_{1}\) : <Sunny, Warm, Normal, Strong, Warm, Same> 가 들어오면, Else문으로 가게 되서 아래와 같이 가설이 변경됩니다
\(h_{1}\) : <Sunny, Warm, Normal, Strong, Warm, Same>
\(x_{2}\) : <Sunny, Warm, Normal, Light, Warm, Same>가 들어오면 새로운 경험을 받습니다. Strong해도 나가 노는구나! Strong U Light => ?로 변환됩니다
\(h_{2}\) : <Sunny, Warm, Normal, ?, Warm, Same>

이런 방법으로 가능한 범위(Version Space)를 찾아갑니다! General Boundary와 Specific Boundary 이 사이에 있는 공간을 찾습니다

Candidate Elimination Algorithm

  • Version Space를 구하기 위해 위 알고리즘을 적용합니다
  • 가장 maximally specific, 가장 general한 가설 사이에서 점점 좁혀가는 알고리즘입니다
For instance x in D
  If y of x is positive
    Generalize S as much as needed to cover o in x
    Remove any h in G, for which h(o)!=y
  If y of x is negative
    Specialize G as much as needed to exclude o in x
    Remove any h in S, for which h(o)=y
  • 위와 같은 방법은 Perfect World에선 사용 가능하지만, 현실에선 사용하기 어렵습니다
    • noise가 존재
    • decision factor가 존재 가능
  • 룰베이스 기반으론 현실을 반영하기 어렵습니다
  • 위 사항을 해결하기 위해 나온 것 중 하나가 의사결정 나무(Decision Tree)입니다!

Entropy

  • Entropy를 이해해야 Decision Tree를 더 잘 이해할 수 있습니다
  • Entropy
    • 어떤 attribute를 더 잘 check 할 수 있을지 알려주는 지표
    • 불확실성(uncertainty)를 줄여야 합니다!(=높은 entropy)
  • 주어진 상황을 특정 분포로 만들어진 random variable로 판단할 수 있습니다
\[H[X] = -\sum_{x}P(X=x) \log_{b} P(X=x)\]

Conditional Entropy

  • 특정 feature variable이 주어졌을 때의 Entropy
  • 주어진 x에 대해 y의 entropy를 구하는 형태
\[H(Y\mid X) = -\sum_{x}P(X=x)H(Y\mid X=x)\] \[= -\sum_{x}P(X=x)\{-\sum_{y}P(Y=y\mid X=x)log_{b}P(Y=y\mid X=x)\}\]

Information Gain

<-A1
(307+, 383-)		-><-A9
(307+, 393-)		->
a
(98+, 112-)		b
(206+, 262-)		?
(3+,9-)		 t
(284+,77-)		f
(23+, 306-)
\[H(Y) = -\sum_{y\in\{+,-\}}P(Y=y) \log_{2} P(Y=y)\] \[P(Y=t) =\frac{307}{307+383}\] \[H(Y\mid A1) = \sum_{X\in\{a,b,?\}}\sum_{Y\in\{+,-\}}P(A1 = x, Y=y)\log_{2}\frac{P(A9=X)}{P(A9=X, Y=Y)}\] \[IG(Y,A_{i}) = H(Y) - H(Y\mid A_{i})\]
  • 특정 condition \(A_{i}\) 조건이 주어졌을 때의 정보 이득의 양
  • 앞의 사례에선 A9가 IG이 높습니다
    • 따라서 A9를 root로 만들고 분리된 케이스에서 또 IG를 구하는 방시긍로 트리를 확장합니다

Decision Tree를 만드는 Algorithm

  • ID3, C4.5, CART 등 다양하게 있는데, 여기선 ID3만 설명하겠습니다
    • initial open node 생성
    • 채울 open node 선택
    • IG를 활용해 best variable 선택(T 또는 F)
    • 인스턴스를 정렬해 브런치에 넣어줌
    • class와 label이 동일할 경우 종료

Problem of Decision Tree

  • 디테일한 트리를 만들 경우엔 현재 데이터는 100% 맞을 수 있지만, 새로운 데이터는 예측을 못할 수 있습니다
  • 앞에서도 말했듯이 현실은 noise, inconsistencies를 가지고 있기 때문에 앞으로 올 데이터는 못 맞출 수 있습니다

Linear Regression

  • 이번엔 통계적 기반의 방식을 사용해보겠습니다
  • housing dataset
    • 13 numerical independent values
    • 1 numerical dependent value
  • linear한 function으로 approximation 하는 것이 머신러닝에서 바라본 linear regression
  • hypothesis를 function의 형태로 정의해보겠습니다
\[h:\hat f(x; \theta) = \theta_{0} + \sum_{i=1}^{n}\theta_{i}x_{i} = \sum_{i=0}^{n}\theta_{i}x_{i}\]
  • \(n\) = feature values의 개수
  • linear는 건들지 말고, \(\theta\)를 잘 정의해보는 것이 목표!
\[\hat f = X\theta\]

\(X = \begin{bmatrix} 1 & \cdots & x_{n}^{1} \\ \vdots & \ddots & \vdots \\ 1 & \cdots & x_{n}^{D} \end{bmatrix}\), \(\theta = \begin{bmatrix} \theta_0 \\ \theta_1 \\ \cdots \\ \theta_n \end{bmatrix}\)

현실의 noise를 반영하면, \[f(x; \theta) = \sum_{i=0}^{n}\theta_{i}x_{i}+e = y \to f=X\theta+e=Y\]

이제 \(\theta\)를 추정하기 위해 식을 작성해보겠습니다 \[\hat\theta=argmin_{\theta}(f-\hat f)^{2} = argmin_{\theta}(Y-X\theta)^2\] \[argmin_{\theta}(Y-X\theta)^{T}(Y-X\theta) = argmin_{\theta}(Y-X\theta)^{T}(Y-X\theta)\] \[argmin_{\theta}(\theta^{T}X^{T}X\theta-2\theta^{T}X^{T}Y+Y^{T}Y) = argmin_{\theta}(\theta^{T}X^{T}X\theta-2\theta^{T}X^{T}Y)\] \[\triangledown_{\theta}(\theta^{T}X^{T}X\theta-2\theta^{T}X^{T}Y) = 0\] \[2X^{T}X\theta-2X^{T}Y=0\] \[\theta = (X^{T}X)^{-1}X^{T}Y\]

현재 함수는 linear하기 때문에, 데이터의 끝 부분을 제대로 표현하지 못하고 있습니다. 이를 위해 x를 \(\phi\)라는 함수를 거쳐 새로운 벡터를 만든 후, 이 벡터를 사용해 \(\theta\)를 구해볼 것입니다.

\(x^2\), \(x^3\), \(x^4\)를 계속 추가해서 만들면 non-linear한 형태가 나타납니다. 하지만 이렇게 끝 부분이 잘 맞는 것이 옳은 것일까요? 관측치가 1개뿐인데 이것을 맞추는 것이 옳을까? 나중에 이에 대한 답을 고민해 볼 예정입니다

Reference


카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)

Buy me a coffeeBuy me a coffee



© 2017. by Seongyun Byeon

Powered by zzsza