Bayesian Classifiers

Bayesian Classifier

Conditional Probability를 이용해서 Classifier를 구현 하는 방법이다.

이번 장에서는 Theorem에 대해서 주로 다루고 실제 구현은 R을 통해서 수행한다.

구현 부분이 궁금하다면 Naive Bayes Classification with R을 보자.

Conditional Probability 계산법

$$P\left( { C }|{ A } \right) =\frac { P(A\cap C) }{ P(A) } $$

이라면, A일때 C의 확률을 구하는 조건부 확률 문제이다.

하지만, A 조건이 결합 확률로써 여러 조건들이 연속적으로 발생 할때의 확률이라면 계산하기는 쉽지 않다.

이때 Bayes Theorem을 적용하면 쉽게 계산을 할 수 있게 된다.

이 알고리즘은

P를 정확히 계산할 수 있다는 전제 하에 가장 성능이 좋은 알고리즘으로 알려져 있다.

하지만 이것은 이론상 그런것일 뿐 실제로는 P를 정확히 계산하기 어렵기 떄문에 그렇지는 않다.

Bayes Theorem의 기초 문제

---

팀 0은 65% 승리, 이중 30%만이 팀1의 Home 장소에서 이긴것이다.

팀1의 경우 35%의 승리가 있고 그중 75%가 자신의 홈에서 승리한 것이다.

이러한 상황에서 

팀 1이 팀0의 홈에서 경기를 한다면 확률상 어느 팀이 승리할 것인가?

해설

X는 홈이 되는 팀을 나타낸다.

Y는 경기에서 승리한 팀을 나타낸다.

이럴때, X와 Y는 각각 {0,1}사이의 값을 가질 수 있다.

P(Y=0) = 0.65

P(Y=1) = 0,35

P(X=1 | Y=1) = 0.75

P(X+1 | Y=0) = 0.3

이것을 예측하기 위해서는 다음과 같다.

P(Y=1|X=1)와 P(Y=0|X=1) 이 둘의 확률을 계산해서 더 큰 쪽으로 Prediction 하면 된다.

계산 방법은 아래와 같다.

Bayesian Classifier

---

Bayes Theorem을 이용해서 모든 class에 대한

posterior probability를 계산하여 classifier를 만드는 것이다.

그런다음, 각각의 Class에 대한 확률 값 P중에서 최대가 되는 것을 선택해서 예측 하게 된다.

Bayes theorem을 쓰면, 원래 수식 보다는 조건부가 더 간단해져서 계산하기 쉽지만, 

그래도 여전히 아래와 같이 Joint Probability 이므로 계산하기 쉽지 않다. 

Naive Bayes Classifier 

---

주어킨 class에 대해서 모든 각각의 Attribute들이 독립적이라고 가정 하면, 

Joint Probability 문제가 간단해 진다.

그렇다면, 어떻게 Data로 부터 Probability를 얻어내는가?

Traning set으로 부터 counting하여 P를 얻어낸다.

결국 discrete attribute에 대해서는 아래와 같은 식이 성립 한다.

□ Example of Naive Bayes Classifier (1) 

아래와 같이 트레이닝 데이터가 주어졌다고 했을때,

x = (Refund = no, Martial Status= Married, Income = 120K)의 Record에 대해서 prediction을 수행 해라.

Taxable Income에 대해서는 Normal Distribution을 따른 다고 가정한다.

sample mean = 110 

sample variance = 2975

문제를 풀기 위해서 주어진 record에 대해서 class = Yes 일때와 No일때의 확률을 구하는 수식은 아래와 같다.

위를 계산하면,

P(X|yes) = 0 이고 P(X|no) = 0.0024 이다.

따라서 Class는 No로 Prediction 된다.

□ Example of Naive Bayes Classifier (2)

독립이라는 가정하에 각각의 Class의 확률을아래와 같이 분리 할 수 있다.

결국 분모는 P(X)로 같으므로, 분자만 비교하면 P(mammals|x) > P(non-mammals|x) 이므로

test record x는 mammals로 prediction 된다.

Probabilistic Learning - Classification using Naive Bayes

---

과거의 데이터를 분포를 가지고 확률에 기반에서 미래를 예측 하는 기술이다.

18세기 수학자 Thomas Bayes에 의해서 고안된 기초적인 수학 원칙인 Bayesian method에 기반한다.

Bayesian classifier는 

Text classification, such as junk email (spam) filtering, author identification, or topic categorization

Intrusion detection or anomaly detection in computer networks

Diagnosing medical conditions, when given a set of observed symptom

기본적으로 Basian classifier는 정보가 다양한 속성으로 부터 동시에 고려되져야 한다면, 그것을 통해서 확률적인 결과를 예측 해야 한다면

그러한 상황에서 적용할때 최적의 방법으로 알려져 있다.

많은 알고리즘은들은 weak effect를 가지는 feature 들을 무시하는 방법을 택하지만 Bayesian 방법은 모든 미묘한 변화와 가능성을 고려하는 방법을 택한다.

스팸의 경우 스팸이 20% 이면 스팸이 아닌것은 80%인 둘은 항상 총합이 100%가 되는,

Mutually exclusive 하며 exhaustive한 관계를 가지고 있다.

The Laplace estimator

spam filter를 하기위해서 몇가지를 더 고려한다고 가정해보자.

money, groceries, 그리고 unsubscribe 이 세개를 Viagra와 함께 추가로 고려 한다.

이럴때, Naive baytes algorithm을 적용하기전에 spam일 때의 likelihood를 계산해 보면,

$$(4/20)\times (10/20) \times (0/20) \times (12/20) \times (20/100) = 0$$

이렇게 계산 했을 때, ham의 경우

$$(1/80) * (14/80) * (8/80) * (23/80) * (80/100) = 0.00005$$

따라서 spam 일때의 확률은

$$0 / (0 + 0.0099) = 0$$

ham 일때의 확률은

$$0.00005 / (0 + 0. 0.00005) = 1$$

이 된다.

하지만, 이러한 0% 와 100%의 spam과 ham의 예측은 타당하지 않다.

가끔은 viagra도 합당한 e-mail에도 쓰일 수 있다. 그래서 절대적으로 spam이라고 단정 할 수는 없는 것이다.

이러한 문제는 과거에 해당 이벤트가 한번도 해당 클래스 레벨에서 관측 되지 않았다면 매번 발생 하는 문제이다.

Groceries라는 단어가 과거의 spam에서 발견되지 않았다면,

P(spam|groceries) = 0%이고 따라서 절대적으로 spam이 아닌 결과를 도출 하게 된다.

데이터를 관측하지 못해서 정확도가 올라가는 현상은 매번 심각히 고려야할 문제로 다뤄 왔다.

이것을 해결하는 하나의 방법으로 Laplace estimator를 사용하는 방법이 있다.

프랑수 수학자 pierre-simon laplace에 의해서 고안된 것이다.

이것은 zero feature를 막기 위해서 최소한 1의 count 값을 모든 feature에 추가하는 방식을 말한다.

1을 각각 추가해서 이전의 식을 재수행하면 아래와 같다.

$$(5/24) * (11/24) * (1/24) * (13/24) * (20/100) = 0.0004$$

각각의 feature에 1을 추가하면 전체에 총 4를 추가한다. 모두 각각 4개의 feature가 기록 되었기 때문이다.

ham의 값은

$$(2/84) * (15/84) * (9/84) * (24/84) * (80/100) = 0.0001$$

이것을 이용해서 각각의 확률 계산해 보면,

Using numeric features with naive Bayes 

naive bayes를 적용하기 위해서는 빈도 테이블이 있어야 한다. 따라서 각각의 feature들은 카테고리컬 해야하며 메트릭으로 구성 되어야 한다.

해결방법은 discretization을 수행 하는 것이다.

이렇게 할려면 각각의 bin 설정을 위한 cut point를 설정 해야 한다. 따라서 이러한 discretization 기법을 binning이라고도 부른다.

여기서는 시간을 이용해서 cut point를 설정 했다.

아래의 histogram을 보면 자연적으로 4개의 구분으로 나눠지는 것을 알 수 있다.

이렇게 나눠진 numeric data들은 각각의 구획에 따라서 nominal feature들로 변환 되어서 naive bayes에 적용된다.

만약 discretization을 하기가 명확하지 않다면, 하나의 선택적 방법은

분위수를 수행 하는 것이다.

하지만 이러한 discretizing은 언제나 정보 손실을 가져온다는 것을 유념해야 하며,

따라서 balance를 유지하기 위해서 노력 해야 한다.

너무 적은 bin은 중요한 경향을 놓치게하며, 너무 많은 bin은 naive bayes에 적용하기에는 부족한 빈도 table을 생성하는 경향을 보이기 때문이다.

Bayesian Network  

---

기존의 Naive Bayesian의 경우 모든 Attribute가 독립 적이라는 가정을 하고 Classification을 수행하기 때문에 문제가 발생한다.

어느정도 의존성을 고려해서 처리하고 싶을때 지금 소개하는 Bayesian Network을 사용 한다.

아래 보여지는 Network은 기존의 Naive Bayes Classifier를 Network으로 나타낸것이다. 보이는 봐와 같이 Class 정보인 play에만 의존성이 있고 각각의 Attribute에 대해서는 모두 의존성이 없는 모습을 가진다.

그럼 이제 어느정도 의존성이 있는 Network을 가지고 Prediction을 수행해 보자.

아래와 같은 데이터에 대해서 Play는 무엇으로 Prediction 되어 질 수 있는가?

위의 주어진 레코드를 x로 두면

P(Play = Y |X), P(play = N |X) 둘 중에서 더 큰 확률 값을 가지는 것으로 prediction하는 문제가 된다.

이때 모든 Joint Probability를 고려 하면,

이중에서 network을 고려해서 실제 의존성이 있는 것들만 남기면 다음과 같다.

각각의 확률 값들은 표에 나온 미리 계산된 확률값을 그대로 이용 한다.

Play=no에 대해서도 계산하면 다음과 같다.

최종적으로 계산하면 아래와 같다.

결국 두개의 확률을 비교 하면 Play=YES가 더 크기 때문에 해당 값으로 prediction 된다.