인공지능 과제3

Posted by Patchman
2010.02.15 16:30 Univ Study/인공지능


 

Homework #3 - solution

2009. 2학기. 인공지능

 

1. 어떤 정당에서는 과거 유권자의 투표 성향 자료를 기초로 미래의 새로운 유권자들에 대한 투표 성향을 예측하려고 한다. 아래의 자료는 9명의 유권자들이 과거 여당(+) 또는 야당(-)에 투표한 기록이다. 각 유권자에 대하여 각각 성별(sex), 나이(age), 수입(income)에 대한 데이터가 있다.

example no.

sex

age

income

vote

1

M

54

3500

+

2

F

20

1200

-

3

F

45

4200

+

4

M

38

4800

-

5

F

25

0

+

6

M

30

3800

-

7

M

48

2200

+

8

F

32

2000

+

9

M

29

2300

-

 

 

 

 

 

 

 

 

 

1) 새로운 유권자 (sex=M, age=24, income=2500)의 투표 성향을 3-Nearest Neighbor 방법으로 예측해보시오. M=1, F=0 으로 하여 Distance(A, B) = (sex 차이 / 2) + (age 차이 / 40) + (income 차이 / 5000)으로 정의하시오.

새로운 사용자의 정보: (sex=M, age=24, income = 2500)

Distance(A, B) = (Sex의 차이 / 2)+(Age의 차이 / 40)+(Income의 차이 / 5000)

 

새로운 유권자 x와 기존 유권자 사이의 거리:

D(1, x) = 30/40 + 1000/5000 = 0.75 + 0.2 = 0.95

D(2, x) = 1/2 + 4/40 + 1300/5000 = 0.5+0.1+0.26 = 0.86

D(3, x) = 1/2 + 21/40 + 1700/5000 = 0.5+0.525 +0.34 = 1.36

D(4, x) = 16/40 + 2300/5000 = 0.4 + 0.46 = 0.86

D(5, x) = 1/2+1/40+2500/5000=0.5+0.025+0.5=1.03

D(6, x) = 6/4+1300/5000=0.15+0.26=0.41

D(7, x) = 24/40+300/5000=0.6+0.06=0.66

D(8, x) = 1/2+8/40+500/5000=0.5+0.2+0.1=0.8

D(9, x) = 5/40+200/5000=0.125+0.04=0.16

 

가장 거리가 가까운 6, 7, 9를 선택하고 여당을 +1, 야당을 -1로 선정하면,

(-1/0.41)+(1/0.66)+(-1/0.16) = -7.17

 

∴ 야당

 

 

2) 위의 데이터에서 age 40 이상은 Old, 40 미만은 Young, income 3000 이상은 High, 3000 미만은 Low로 표현하기로 하자. 새로운 유권자 (sex=M, age=24, income=2500)은 (sex=M, age=Young, income=Low)가 된다. Naive Bayesian classifier를 이용하여 이 유권자의 투표 성향을 예측해보시오.

 

새로운 사용자의 정보 = (sex=M, age=24, income = 2500)

= (sex=M, age=Y, income = L)

 

- P(+) = 5/9 P(-) = 4/9

- P(M|+) = 2/5 P(M|-) = 3/4

- P(Y|+) = 2/5 P(Y|-) = 4/4 = 1

- P(L|+) = 3/5 P(L|-) = 2/4

 

∴ P(+|M, Y, L) = ․P(M|+)․P(Y|+)․P(L|+)․P(+)

= ․(4/9)․(2/5)․(3/5)․(5/9)

= 0.0585

P(-|M, Y, L) = ․P(M|-)․P(Y|-)․P(L|-)․P(-)

= ․(3/4)․(4/4)․(2/4)․(4/9)

= 0.168

- Normalize

P(+|M, Y, L) = 0.258, P(-|M, Y, L) =0.742

∴ 야당 (약 75%)

 

2. 어떤 과학 분야 문서들을 Physics, Biology, Chemistry 등 세 가지 카테고리로 분류한다고 하자. 다음의 확률은 Yahoo 로부터 수집되어 전문가에 의해 미리 분류된 웹페이지들의 전자 코퍼스(corpus)를 분석하여 추정되었다. 예를 들어 Physics에 해당하는 문서에서 ‘atom'이라는 단어가 나타날 확률은 0.1 이었다.

Category (c)

Physics

Biology

Chemistry

P(c)

0.35

0.40

0.25

P(atom | c)

0.1

0.01

0.2

P(carbon | c)

0.005

0.03

0.05

P(proton | c)

0.05

0.001

0.05

P(life | c)

0.001

0.1

0.008

P(earth | c)

0.005

0.006

0.003

P(force | c)

0.05

0.005

0.008

 

 

 

 

 

 

 

 

문서의 카테고리가 주어졌을 때 각각의 단어의 확률은 독립적이라고 가정하고 (conditional independence), 다음의 각 문장들이 각 카테고리에 속할 확률을 계산하시오. 단어들은 모두 기본형으로 변환하여 처리한다고 가정하고 (예: atoms → atom, forces → force), 위의 표 안에 있지 않은 단어들(The, is 등)은 무시하시오.

 

a) The carbon atom is the foundation of life on earth.

P(P | carbon, atom, life, earth)

= ⍺P(carbon | P)∙P(atom | P)∙P(life | P)∙P(earth | P)*P(P)

= ⍺*0.005*0.1*0.001*0.005*0.35

= 8.75*10-10

 

P(B | carbon, atom, life, earth)

= ⍺P(carbon | B)∙P(atom | B)∙P(life | B)∙P(earth | B)*P(B)

= ⍺*0.03*0.01*0.1*0.006*0.4

= 720*10-10

 

P(C | carbon, atom, life, earth)

= ⍺P(carbon | C)∙P(atom | C)∙P(life | C)∙P(earth | C)*P(C)

= ⍺*0.05*0.2*0.008*0.008*0.25

= 1600*10-10

==> Normalize

Physics일 확률 = 0.004

Biology일 확률 = 0.309

Chemistry일 확률 = 0.687

b) The carbon atom contains 12 protons.

P(P | carbon, atom, proton)

= ⍺P(carbon | P)∙P(atom | P)∙P(proton | P)*P(P)

= ⍺*0.005*0.1*0.05*0.35

= 875*10-8

 

P(B | carbon, atom, proton)

= ⍺P(carbon | B)∙P(atom | B)∙P(proton | B)*P(B)

= ⍺*0.03*0.01*0.001*0.4

= 12*10-8

 

P(C | carbon, atom, proton)

= ⍺P(carbon | C)∙P(atom | C)∙P(proton | C)*P(C)

= ⍺*0.05*0.2*0.05*0.25

= 12500*10-8

==> Normalize

Physics일 확률 = 0.065

Biology일 확률 = 0.001

Chemistry일 확률 = 0.934

c) String theory attempts to unify all of the forces on earth.

P(P | force, earth)

= ⍺P(force | P)∙P(earth | P)*P(P)

= ⍺*0.05*0.005*0.35

= 875*10-7

 

P(B | force, earth)

= ⍺P(force | B)∙P(earth | B)*P(B)

= ⍺*0.005*0.006*0.4

= 120*10-7

 

P(C | force, earth)

= ⍺P(force | C)∙P(earth | C)*P(C)

= ⍺*0.008*0.003*0.25

= 60*10-7

==> Normalize

Physics일 확률 = 0.829

Biology일 확률 = 0.114

Chemistry일 확률 = 0.057

 

 

 

 

3. 다음 그림은 자동차가 시동이 걸리기 위한 여러 요소들의 관계를 Bayesian network 으로 나타낸 것이다.

 

 

 

1) Start = no, Light = off 일 경우 Plug = bad 의 확률을 구하시오.

P(Plug = bad)

 

B=Good

Sp=Yes

G=Full

B=Good

Sp=No

G=No

B=Bad

Sp=Yes

G=Full

B=Bad

Sp=No

G=No

B=Good

Sp=Yes

G=Full

B=Good

Sp=No

G=No

B=Bad

Sp=Yes

G=Full

B=Bad

Sp=No

G=No

P=Good

0.00504

0

0.0063

0.0567

0.01728

0

0.0216

0.027

P=Bad

0.000112

0.004032

0.00014

0.01134

0.000384

0.00192

0.00048

0.0054

- sum

P=Good

0.13392

P=Bad

0.023808

- Normalization

P=Good

0.8491

P=Bad

0.1509

∴ 0.1509

2) Start = no, Light = off 일 경우 Battery = bad 의 확률을 구하시오.

P(Battery = bad)

 

Sp=Yes

G=Full

Sp=Yes

Sp=No

G=No

Sp=No

Sp=Yes

G=Full

Sp=Yes

Sp=No

G=No

Sp=No

Sp=Yes

G=Full

Sp=Yes

Sp=No

G=No

Sp=No

Sp=Yes

G=Full

Sp=Yes

Sp=No

G=No

Sp=No

B=Good

0.00504

0

0.000112

0.004032

0.1728

0

0.000384

0.00192

B=Bad

0.00063

0.0567

0.00014

0.01134

0.0216

0.027

0.00048

0.0054

- sum

B=Good

0.028768

B=Bad

0.12896

- Normalization

B=Good

0.1824

B=Bad

0.8176

∴ 0.8176

 

4. 어떤 지하 연구실의 청소 로봇은 외부 날씨(FINE, RAIN, SNOW)에 확률적으로 반응하는 크리스탈을 가지고 있다. 크리스탈은 3가지 색(RED, GREEN, BLUE) 중 하나의 색깔로 변한다. 날씨의 변화는 first-order markov process라고 가정하고, 날씨의 transition probability와 크리스탈 색의 output probability가 아래와 같이 주어진다.

 

 

FINE

RAIN

SNOW

FINE

0.7

0.2

0.1

RAIN

0.3

0.5

0.2

SNOW

0.3

0.2

0.5

 

RED

GREEN

BLUE

FINE

0.7

0.1

0.2

RAIN

0.3

0.5

0.2

SNOW

0.1

0.3

0.6

 

1) 오늘 날씨가 RAIN일 때 다음 이틀이 연속 SNOW일 확률은 얼마인가?

P(R, S, S) = P(R) * P(S | R) * P(S | S)

= 1 * 0.2 * 0.5

= 0.1

2) 어느 2일간 크리스탈의 색이 (BLUE → GREEN)으로 변하는 것이 관측되었다면,

그 2일간 가장 가능성이 높은 실제 날씨는 무엇이었겠는가? 사전 정보가 없을 때,

P(FINE)=0.5, P(RAIN)=0.3, P(SNOW)=0.2 이다.

P(F, F | B, G) = P(B | F) * P(G | F) * P(F | ⌀) * P(F | F)

= ⍺* 0.2 * 0.1 * 0.5 * 0.7

= 70β

(β = 0.0001)

P(F, R | B, G) = P(B | F) * P(G | R) * P(F | ⌀) * P(R | F)

= ⍺* 0.2 * 0.5 * 0.5 * 0.2

= 100β

P(F, S | B, G) = P(B | F) * P(G | S) * P(F | ⌀) * P(S | F)

= ⍺* 0.2 * 0.3 * 0.5 * 0.1

= 30β

P(R, F | B, G) = P(B | R) * P(G | F) * P(R | ⌀) * P(F | R)

= ⍺* 0.2 * 0.1 * 0.3 * 0.3

= 18β

P(R, R | B, G) = P(B | R) * P(G | R) * P(R | ⌀) * P(R | R)

= ⍺* 0.2 * 0.5 * 0.3 * 0.5

= 150β

P(R, S | B, G) = P(B | R) * P(G | S) * P(R | ⌀) * P(S | R)

= ⍺* 0.2 * 0.3 * 0.3 * 0.2

= 36β

P(S, F | B, G) = P(B | S) * P(G | F) * P(S | ⌀) * P(F | S)

= ⍺* 0.6 * 0.1 * 0.2 * 0.3

= 36β

P(S, R | B, G) = P(B | S) * P(G | R) * P(S | ⌀) * P(R | S)

= ⍺* 0.6 * 0.5 * 0.2 * 0.2

= 120β

P(S, S | B, G) = P(B | S) * P(G | S) * P(S | ⌀) * P(S | S)

= ⍺* 0.6 * 0.3 * 0.2 * 0.5

= 180β

∴ snow, snow


'Univ Study > 인공지능' 카테고리의 다른 글

인공지능 과제4  (0) 2010.02.15
인공지능 과제3  (0) 2010.02.15
인공지능 과제2  (2) 2010.02.15
인공지능 과제1  (0) 2010.02.15
인공지능 프로로그(Prolog) 설치파일  (0) 2010.02.15