Homework #4 - solution

2009. 2학기. 인공지능

 

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

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. Information gain을 사용하여 decision tree 학습을 수행하는 과정을 보이고, 학습 결과에 따라

유권자 A=(M, 35, 2000)의 성향을 + 또는 -로 분류하시오. 각 attribute의 값은 다음과 같이

변환하여 사용하시오.

age: Old(40이상) 또는 Young(40미만),

income: High(2500이상) 또는 Low(2500미만)

 

T = {+(1, 3, 5, 7, 8), -(2, 4, 6, 9)}

E(T) = -(5/9)*log2(5/9) (4/9)*log2(4/9) = 0.99

 

1) p = sex,

T1(M) = {+(1, 7), -(4, 6, 9)} E(T1) = -(2/5)*log2(2/5) (3/5)*log2(3/5) = 0.56

T2(F) = {+(3, 5, 8), -(2)} E(T2) = -(3/4)*log2(3/4) (1/4)*log2(1/4) = 0.44

Gain(sex) = E(T) - ((5/9)*E(T1) + (4/9)*E(T2))

= 0.99 - ((5/9)*0.56 + (4/9)*0.44) = 0.091

2) p = age,

T1(Old) = {+(1, 3, 7), -()} E(T1) = -(3/3)*log2(3/3) (0/3)*log2(0/3) = 0

T2(Young) = {+(5, 8), -(2, 4, 6, 9)} E(T2) = -(2/6)*log2(2/6) (4/6)*log2(4/6) = 0.92

Gain(age) = E(T) - ((3/9)*E(T1) + (6/9)*E(T2))

= 0.99 - ((3/9)*0 + (6/9)*0.92) = 0.379

3) p = income,

T1(High) = {+(1, 3), -(4, 6)} E(T1) = -(2/4)*log2(2/4) (2/4)*log2(2/4) = 1

T2(Low) = {+(5, 7, 8), -(2, 9)} E(T2) = -(3/5)*log2(3/5) (2/5)*log2(2/5) = 0.97

Gain(income) = E(T) - ((4/9)*E(T1) + (5/9)*E(T2))

= 0.99 ((4/9)*1 + (5/9)*0.97) = 0.007

 

∴ SELECT 'age'

 

T(age == 'Old') = {+(1, 3, 7), -()} leaf with '+'

 

T(age == 'Young') = {+(5, 8), -(2, 4, 6, 9)}

E(T) = -(2/6)*log2(2/6) (4/6)*log2(4/6) = 0.92

 

1) p = sex,

T1(M) = {+(), -(4, 6, 9)} E(T1) = -(0/3)*log2(0/3) (3/3)*log2(3/3) = 0

T2(F) = {+(5, 8), -(2)} E(T2) = -(2/3)*log2(2/3) (1/3)*log2(1/3) = 0.92

Gain(sex) = E(T) - ((3/6)*E(T1) + (3/6)*E(T2))

= 0.92 ((3/6)*0 + (3/6)*0.92) = 0.459

2) p = income,

T1(High) = {+(), -(4, 6)} E(T1) = -(0/2)*log2(0/2) (2/2)*log2(2/2) = 0

T2(Low) = {+(5, 8), -(2, 9)} E(T2) = -(2/4)*log2(2/4) (2/4)*log2(2/4) = 1

Gain(age) = E(T) - ((2/6)*E(T1) + (4/6)*E(T2))

= 0.92 ((2/6)*0 + (4/6)*1) = 0.252

 

∴ SELECT 'sex'

 

T((age == 'Young') and (sex == 'M')) = {+(), -(4, 6, 9)} leaf with '-'

 

T((age == 'Young') and (sex == 'F'))의 경우, 모든 경우에 대해서 income = Low이고,

T = {+(5, 8), -(2)}가 되어, 더 이상 class의 구분이 불가능하다.

이 경우 majority를 leaf로 한다 '+'

 

 

∴ A=<M, Young, Low>는 야당성향(-)이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Example 1, 2, 3을 이용하여 multi-layer neural network에서의 backpropagation learning을

한번 수행하는 과정을 보이고, 그 결과에 따라 유권자 A=(M, 35, 2000)의 성향을 + 또는 -로

분류하시오. Neural network의 구조는 다음 그림과 같이 하고, 각 unit의 output function은

sigmoid이며, w1 = 1, w2 = -1, 나머지 weight는 모두 0.0으로 하시오. Learning rate는 10.0,

각 attribute의 값은 다음과 같이 [-1, 1]로 normalize 하여 사용하시오.

sex: Male=1.0, Female=-1.0

age: (age - 40.0) / 20

income: (income - 2500) / 2500

 

 

 

 

 

 

 

 

Initial weight:

W3, W4, W5, W6, W7, W8, W9, W10, W11 = 0

W1 = -1, W2 = 1, c = 10

 

example 1 : (1, 0.7, 0.4) d = 1

H1 = 1/(1+e-s) = 0.5, (s = sex * W5 + age * W6 + income * W7 + W4 = 0)

H2 = 1/(1+e-s) = 0.5, (s = sex * W8 + age * W9 + income * W10 + W11 = 0)

O = 1/(1+e-s) = 0.5, (s = H1* W1 + H2 * W2 + W3 = 0)

 

deltaO = (d-O) * O * (1-O) = 0.1250

deltaH1 = deltaO * W1 * H1 * (1-H1) = -0.03125

deltaH2 = deltaO * W2 * H2 * (1-H2) = 0.03125

 

W1 = W1 + c * deltaO * H1 = -0.3750

W2 = W2 + c * deltaO * H2 = 1.625

W3 = W3 + c * deltaO * 1 = 1.250

W4 = W4 + c * deltaH1 * 1 = -0.3125

W5 = W5 + c * deltaH1 * sex = -0.3125

W6 = W6 + c * deltaH1 * age = -0.2188

W7 = W7 + c * deltaH1 * income = -0.1250

W8 = W8 + c * deltaH2 * sex = 0.3125

W9 = W9 + c * deltaH2 * age = 0.2188

W10 = W10 + c * deltaH2 * income = 0.1250

W11 = W11 + c * deltaH2 * 1 = 0.3125

 

example 2 : (-1, -1, -0.52) d = 0

H1 = 1/(1+e-s) = 0.2806, (s = sex * W5 + age * W6 + income * W7 + W4)

H2 = 1/(1+e-s) = 0.4296, (s = sex * W8 + age * W9 + income * W10 + W11)

O = 1/(1+e-s) = 0.8499, (s = H1 * W1 + H2 * W2 + W3)

 

deltaO = (d-O) * O * (1-O) = -0.1084

deltaH1 = deltaO * W1 * H1 * (1-H1) = 0.005289

deltaH2 = deltaO * W2 * H2 * (1-H2) = 0.06417

 

W1 = W1 + c * deltaO * H1 = -0.9934

W2 = W2 + c * deltaO * H2 = 1.159

W3 = W3 + c * deltaO = 0.1659

W4 = W4 + c * deltaH1 * 1= -0.2129

W5 = W5 + c * deltaH1 * sex = -0.41219

W6 = W6 + c * deltaH1 * age = -0.3184

W7 = W7 + c * deltaH1 * income = -0.1768

W8 = W8 + c * deltaH2 * sex = 0.7442

W9 = W9 + c * deltaH2 * age = 0.6504

W10 = W10 + c * deltaH2 * income = 0.3495

W11 = W11 + c * deltaH2 * 1= -0.1192

 

example 3 : (-1, 0.25, 0.68) d = 1

H1 = 1/(1+e-s) = 0.4999, (s = sex * W5 + age * W6 + income * W7 + W4)

H2 = 1/(1+e-s) = 0.3863, (s = sex * W8 + age * W9 + income * W10 + W11)

O = 1/(1+e-s) = 0.5293, (s = H1* W1 + H2 * W2 + W3)

 

deltaO = (d-O) * O * (1-O) = 0.1173

deltaH1 = deltaO * W1 * H1 * (1-H1) = -0.02913

deltaH2 = deltaO * W2 * H2 * (1-H2) = 0.03223

 

W1 = W1 + c * deltaO * H1 = -0.4071

W2 = W2 + c * deltaO * H2 = 1.612

W3 = W3 + c * deltaO = 1.339

W4 = W4 + c * deltaH1 * 1= -0.5041

W5 = W5 + c * deltaH1 * sex = -0.1208

W6 = W6 + c * deltaH1 * age = -0.3912

W7 = W7 + c * deltaH1 * income = -0.3749

W8 = W8 + c * deltaH2 * sex = 0.4218

W9 = W9 + c * deltaH2 * age = 0.7310

W10 = W10 + c * deltaH2 * income = 0.5687

W11 = W11 + c * deltaH2 * 1 = 0.2032

 

A: (1, -0.25, 0.2) 에 대한 neural network의 output O = 0.8926 > 0.5

∴ A=<M, Young, Low>는 여당성향(+)이다.

 

 

 

 

 

 

 

 

 

3. (WEKA) 위 1, 2번에 사용된 데이터로 다음을 수행하시오.

 

1) ARFF 파일을 작성하시오. neural network의 경우 세가지 attribute의 타입은

모두 real로 하시오.

 

Decision tree:

 

@relation hw4

 

@attribute sex {M, F}

@attribute age {Y, O}

@attribute income {H, L}

@attribute class {+, -}

 

@data

M, O, H, +

F, Y, L, -

F, O, H, +

M, Y, H, -

F, Y, L, +

M, Y, H, -

M, O, L, +

F, Y, L, +

M, Y, L, -

 

Neural network:

 

@relation hw4

 

@attribute sex real

@attribute age real

@attribute income real

@attribute class {+, -}

 

@data

1, 0.7, 0.4, +

-1, -1.0, -0.52, -

-1, 0.25, 0.68, +

1, -0.1, -0.68, -

-1, -0.75, -1.0, +

1, -0.5, 0.52, -

1, 0.4, -0.12, +

-1, -0.4, -0.2, +

1, -0.55, -0.08, -

2) WEKA를 사용하여 decision tree (J48), neural network (multilayerPerceptron)으로

학습을 수행하여 학습결과 얻어진 모델(함수)을 보이고 모델의 정확도를 보이시오.

정확도는 9-fold cross validation을 수행하여 구하시오.

 

Decision tree:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Correctly Classified Instances 6 66.6667 %

Incorrectly Classified Instances 3 33.3333 %

 

 

Neural network:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Sigmoid Node 0

Inputs Weights

Threshold -1.2877454144815335

Node 2 6.336370508429555

Node 3 -3.175366852826983

Sigmoid Node 1

Inputs Weights

Threshold 1.2882612886859117

Node 2 -6.334008973456787

Node 3 3.172332454644374

Sigmoid Node 2

Inputs Weights

Threshold 0.8712521397068584

Attrib sex -3.806121360872016

Attrib age 6.859539556488592

Attrib income -1.4862723057131864

Sigmoid Node 3

Inputs Weights

Threshold -0.3446589785401386

Attrib sex 1.8621658757094555

Attrib age -3.3434289883065005

Attrib income 0.5784976831594199

 

Correctly Classified Instances 6 66.6667 %

Incorrectly Classified Instances 3 33.3333 %

 

 

3) 얻어진 모델에 따라 (M, 35, 2000) 의 +/- 값을 판단하시오.

(속성값이 (M, 35, 2000), 클래스 값이 ?인 데이터 하나가 있는 ARFF 파일을 만든뒤

Test options에서 supplied test set을 선택하여 만든 파일를 지정하고,

More ooptions에서 output predictions를 체크하고 실행하면 결과를 확인할 수 있음)

 

Decision tree:

 

@relation hw4-test

 

@attribute sex {M, F}

@attribute age {Y, O}

@attribute income {H, L}

@attribute class {+, -}

 

@data

M, Y, L, ?

 

-->

 

=== Predictions on test set ===

 

inst#, actual, predicted, error, probability distribution

1 ? 2:- + 0 *1

 

Neural network:

 

@relation hw4-test

 

@attribute sex real

@attribute age real

@attribute income real

@attribute class {+, -}

 

@data

1, -0.25, 0.2, ?

 

-->

 

=== Predictions on test set ===

 

inst#, actual, predicted, error, probability distribution

1 ? 2:- + 0.017 *0.983

 

4. (WEKA) letter.arff 데이터는 인쇄된 숫자 이미지로부터 pixel들의 분포에 대한 16가지의 속성을 추출하고 그 속성값들을 바탕으로 A ~ Z 26개 문자 중 하나를 인식하는 문제에 대한 example들이다. 이 데이터로 decision tree (J48)와 neural network (multilayer Perceptron) 학습을 수행하여 다음의 결과를 보이시오.

 

1) letter-test.arff 파일의 5개 데이터가 각각 무슨 문자인지 판단하시오.

(Test options에서 supplied test set을 선택하여 letter-test.arff를 지정하고,

More ooptions에서 output predictions를 체크하고 실행하면 결과를 확인할 수 있음)

 

=== Predictions on test set ===

 

inst#, actual, predicted, error, probability distribution

1 ? 8:H + 0

2 ? 1:A + *0.994

3 ? 16:P + 0

4 ? 16:P + 0

5 ? 25:Y + 0

 

∴ H, A, P, P, Y

 

2) Test options에서 percentage split을 선택하고 %값을 작은 수에서부터 변화시키면서

정확도를 확인하여 decision tree와 neural network 알고리즘의 학습 곡선을

각각 그려보시오.

 

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

 

Homework #2

2009. 2학기. 인공지능

 

 

1. 다음 상태공간에서 시작상태는 A이고 목표상태(두개의 겹치는 원)는 F와 J이다(둘 중 어느쪽에 도달해도 목표가 달성되는 것이다). 각각의 노드에는 목표상태까지의 추정값인 heuristic 값 h가 있다. 목표상태에 도달할 수 없는 노드는 h=∞ 값을 가진다. 각각의 노드에서 다음 노드까지의 실제 값은 간선에 표시되어 있다. 아래의 각 탐색 알고리즘에 대하여 노드가 확장되는(선택되는) 순서와 탐색 결과를 구하시오. 동일한 조건의 노드들 중 하나를 선택할 때는 알파벳 순서로 선택한다고 가정하시오. BFS와 DFS에서는 간선 값 및 h 값은 고려되지 않는다. 탐색은 목표상태가 생성되었을 때가 아니라 목표상태가 선택되었을 때 종료됨에 주의하시오.

 

(a) Breadth-first search

(b) Depth-first search

(c) A*

 

(a) BFS: 탐색 순서: A, B, C, D, E, F

탐색 결과: A --> B --> F

(b) DFS: 탐색 순서: A, B, D, E, H, I, F

탐색 결과: A --> B --> F

(c) A*: 탐색 순서: A(0+3), C(2+2), B(3+2), G(5+1), J(6+0)

탐색 결과: A --> C --> G --> J

 

2. 다음은 어떤 공장에서 자동차를 생산하는 단계를 나타낸다. 생산 과정은 A, B, C, D, E 다섯 개의 process로 구성되며, 첫 번째 process는 A이고, 마지막 process는 E이다. XYZ는 X 다음 Y 다음 Z 까지 수행된 상태를 나타내며, ABCDE, ACDBE, ... 등이 완성된 상태로서 goal state에 해당된다. c(S1, S2)는 S1에서 S2 상태까지 진행하는 비용을 나타내며, h(S1)은 S1 상태에서부터 자동차가 완성될 때까지 비용의 추정값이다. 명시되지 않은 비용은 진행할 수 없는 경우로서 ∞이고, *는 임의의 process를 의미한다. 탐색을 이용하여 최소 비용으로 자동차를 완성하는 순서를 찾고자 한다.

 

c(A,AB)=3, c(A,AC)=4, c(A,AD)=2,

c(AB,ABC)=5, c(AB,ABD)=2, c(AC,ACB)=4, c(AD,ADB)=4, c(AD,ADC)=5,

c(ABD,ABDC)=4, c(ADB, ADBC)=5, c(ADC, ADCB)=3, c(****,****E)=1

h(A)=9, h(AB)=9, h(AC)=10, h(AD)=7,

h(ABC)=5, h(ABD)=4, h(ACB)=5, h(ADB)=6, h(ADC)=2, h(****)=1

 

a. f(n) = n 까지의 비용 + h(n) 을 평가함수로 하여 best-first search를 수행하는 과정을 graph로 나타내고, 단계별로 OPEN list가 어떻게 변하는지 쓰시오. 각 state에는 f 값을 명시하시오. 탐색이 끝난뒤 방문한 노드의 순서와 solution path를 쓰시오.

state	open
	A(9)
A	AD(9) AB(12) AC(14)
AD	ADC(9) AB(12) ADB(12)
ADC	ADCB(11) AB(12) ADB(12)
ADCB	ADCBE(11) AB(12) ADB(12)
ADCBE

Solution path : A --> AD --> ADC --> ADCB --> ADCBE

 

b. 위의 search는 최소 비용 생산 순서를 찾지 못한다. 그 이유는 무엇인지 설명하시오.

Admissible heuristic은 0 ≤ h(n) ≤h*(n)이어야 함

h(AB) = 9 > h*(AB) = 7이므로 조건을 만족하지 못함

 

c. 최소 비용 생산 순서를 찾을 수 있도록 h 값을 하나만 바꾸고 a번을 다시 수행하시오.

 

state	open
	A(9)
A	AD(9) AB(10) AC(14)
AD	ADC(9) AB(10) ADB(12) AC(14)
ADC	AB(10) ADCB(11) ADB(12) AC(14)
AB	ABD(9) ADCB(11) ADB(12) AC(14)
ABD	ABDC(10) ADCB(11) ADB(12) AC(14)
ABDC	ABDCE(10) ADCB(11) ADB(12) AC(14)
ABDCE

 

Solution path : A --> AB --> ABD --> ABDC --> ABDCE

 

3. 아래의 그림은 어느 지역의 도로망을 나타낸다. 는 고속도로, 는 국도, 는 일반도로이다. S,A,B,C,D,G 는 각각 도로의 교차 지점이고, 교차 지점 사이의 숫자는 각 지점 사이를 이동하는데 걸리는 운전 시간이다. 즉, S 지점에서 B 지점까지는 5시간이 소요된다. 각 지점의 좌표는 다음과 같다: S(0,0), A(1,0), B(0,1), C(1,1), D(0,2), G(1,2). 고속도로는 가장 빠른 도로로서, 이러한 좌표를 기준으로 거리 1을 이동하는데 1시간이 걸리는 도로이다. S 지점에서 G 지점까지 최소 시간 경로를 A* 알고리즘으로 탐색하려고 할 때 다음에 답하시오.

 

 

a. 각 지점을 state로 하여 탐색 공간을 state space로 나타내시오.

b. 휴리스틱 함수 h(X)는 “X 지점에서 G 지점까지 고속도로가 직선으로 연결되어 있다고 가정했을 때의 소요시간”으로 정의한다. 예를 들어 h(S) = (S~G 사이의 거리) x (1 시간) = 시간이다. 이러한 휴리스틱 함수는 admissible 한가? 설명하시오.

 

답: 각 state에서부터 Goal까지의 실제 걸리는 시간을 h*(s)이라고 했을 때, 고속도로가 가장

빠른 길이고, 직선거리보다 더 짧은 이동거리는 없으므로, h(s) ≤ h*(s)를 만족하며,

이 heuristic 함수는 admissible하다.

즉, 직선고속도로로 이동하는 것을 가정한 소요시간 ≤ 실제 소요시간 이 된다.

STATE	목적지까지 최단소요시간	h(n)
S	8	()
A	7	()
B	3	()
C	5	()
D	1	()

 

 

c. 위의 휴리스틱으로 A*를 진행하면서 단계별로 OPEN list가 어떻게 변하는지 쓰고, 찾아지는 solution path를 쓰시오. OPEN의 각 state는 state(parent, g, h)로 표시하시오.

 

stateOPENCLOSED

S(∅, 0, 2.2)

S(∅) ... S(∅)

 

 

Current	Open List	Close List
S	A(S, 1+2), B(S, 5+)	S
A	C(A, 3+1), B(S, 5+)	S, A
C	B(C, 4+), GOAL(C, 8+0)	S, A, C
B	D(B, 6+1), GOAL(C, 8+0)	S, A, C, B
D	GOAL(D, 7+0)	S, A, C, B, D
Goal	END	END

∴ Solution path = G ← D ← B ← C ← A ← S

 

4. (Programming) 8-puzzle 문제를 DFS, BFS, A* 알고리즘으로 탐색하여 solution을 구하는 프로그램을 작성하고, 아래의 시작상태와 목표상태가 주어졌을 때 각 알고리즘을 사용하는 경우의 방문 state 수와 solution path를 비교하시오. 프로그램은 시작 상태와 목표 상태를 입력 받아 탐색을 수행하고 solution path를 출력한다. 주어진 sample C code를 사용하거나, 새로운 프로그램을 작성할 수 있다.

extra credit) A* 알고리즘에서 두 가지 이상의 heuristic을 사용하여 그 결과를 비교하시오.

 

Start: 1 2 3 Goal: 7 8 1

8 x 46 x 2

7 6 55 4 3

 

 

h1: 제자리에 있지 않은 숫자들의 개수

h2: 제자리에 있지 않은 숫자들의 제자리로부터 거리의 합 이라 할 떄,

 

Solution path 길이: A* with h2 = A* with h1 = BFS =< DFS

방문 state 수: A* with h2 < A* with h1 =< BFS/DFS (경우에 따라 다를 수 있음)