CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Here is a VE template for you to solve the burglary example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class VariableElimination:
@staticmethod
def inference(factorList, queryVariables,
orderedListOfHiddenVariables, evidenceList):
for ev in evidenceList:
# Your code here
for var in orderedListOfHiddenVariables:
# Your code here
print "RESULT:"
res = factorList[0]
for factor in factorList[1:]:
res = res.multiply(factor)
total = sum(res.cpt.values())
res.cpt = {k: v/total for k, v in res.cpt.items()}
res.printInf()
@staticmethod
def printFactors(factorList):
for factor in factorList:
factor.printInf()
class Util:
@staticmethod
def to_binary(num, len):
return format(num, '0' + str(len) + 'b')
class Node:
def __init__(self, name, var_list):
self.name = name
self.varList = var_list
self.cpt = {}
def setCpt(self, cpt):
self.cpt = cpt
def printInf(self):
print "Name = " + self.name
print " vars " + str(self.varList)
for key in self.cpt:
print " key: " + key + " val : " + str(self.cpt[key])
print ""
def multiply(self, factor):
"""function that multiplies with another factor"""
# Your code here
new_node = Node("f" + str(newList), newList)
new_node.setCpt(new_cpt)
return new_node
def sumout(self, variable):
"""function that sums out a variable given a factor"""
# Your code here
new_node = Node("f" + str(new_var_list), new_var_list)
new_node.setCpt(new_cpt)
return new_node
def restrict(self, variable, value):
"""function that restricts a variable to some value
in a given factor"""
# Your code here
new_node = Node("f" + str(new_var_list), new_var_list)
new_node.setCpt(new_cpt)
return new_node
# create nodes for Bayes Net
B = Node("B", ["B"])
E = Node("E", ["E"])
A = Node("A", ["A", "B", "E"])
J = Node("J", ["J", "A"])
M = Node("M", ["M", "A"])
# Generate cpt for each node
B.setCpt({'0': 0.999, '1': 0.001})
E.setCpt({'0': 0.998, '1': 0.002})
A.setCpt({'111': 0.95, '011': 0.05, '110': 0.94, '010': 0.06,
'101': 0.29, '001': 0.71, '100': 0.001, '000': 0.999})
J.setCpt({'11': 0.9, '01': 0.1, '10': 0.05, '00': 0.95})
M.setCpt({'11': 0.7, '01': 0.3, '10': 0.01, '00': 0.99})
print("P(A) **********************")
VariableElimination.inference([B, E, A, J, M], ['A'], ['B', 'E', 'J', 'M'], {})
print("P(B | J~M) **********************")
VariableElimination.inference([B, E, A, J, M], ['B'], [
'E', 'A'], {'J': 1, 'M': 0})
Task
You should implement 4 functions: inference, multiply, sumout and restrict.
Codes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
class VariableElimination:
@staticmethod
def inference(factorList, queryVariables,
orderedListOfHiddenVariables, evidenceList):
for ev in evidenceList:
# Your code here
for factor in factorList:
if ev in factor.varList:
if len(factor.varList) > 1:
factorList.append(
factor.restrict(ev, evidenceList[ev]))
factorList.remove(factor)
for var in orderedListOfHiddenVariables:
# Your code here
new_var_list = []
for e in factorList:
if var in e.varList:
new_var_list.append(e)
first = True
for e in new_var_list:
for i in factorList:
if i.name == e.name:
factorList.remove(i)
if first:
new_var = e
first = False
else:
new_var = new_var.multiply(e)
factorList.append(new_var.sumout(var))
print("RESULT:")
res = factorList[0]
for factor in factorList[1:]:
res = res.multiply(factor)
total = sum(res.cpt.values())
res.cpt = {k: v/total for k, v in res.cpt.items()}
res.printInf()
@staticmethod
def printFactors(factorList):
for factor in factorList:
factor.printInf()
class Util:
@staticmethod
def to_binary(num, len):
return format(num, '0' + str(len) + 'b')
class Node:
def __init__(self, name, var_list):
self.name = name
self.varList = var_list
self.cpt = {}
def setCpt(self, cpt):
self.cpt = cpt
def printInf(self):
print("Name = " + self.name)
print(" vars " + str(self.varList))
for key in self.cpt:
print(" key: " + key + " val : " + str(self.cpt[key]))
print()
def multiply(self, factor):
"""function that multiplies with another factor"""
# Your code here
new_cpt = {}
new_var_list = list(self.varList)
idx1 = []
idx2 = []
for var in factor.varList:
if var in new_var_list:
idx1.append(self.varList.index(var))
idx2.append(factor.varList.index(var))
else:
new_var_list.append(var)
for k1, v1 in self.cpt.items():
for k2, v2 in factor.cpt.items():
flag = True
for i in range(len(idx1)):
if k1[idx1[i]] != k2[idx2[i]]:
flag = False
break
if flag:
new_key = k1
for i in range(len(k2)):
if i not in idx2:
new_key += k2[i]
new_cpt[new_key] = v1 * v2
new_node = Node("f" + str(new_var_list), new_var_list)
new_node.setCpt(new_cpt)
return new_node
def sumout(self, variable):
"""function that sums out a variable given a factor"""
# Your code here
new_cpt = {}
new_var_list = list(self.varList)
new_var_list.remove(variable)
idx = self.varList.index(variable)
for k, v in self.cpt.items():
tmp = k[:idx] + k[idx+1:]
if tmp not in new_cpt.keys():
new_cpt[tmp] = v
else:
new_cpt[tmp] += v
new_node = Node("f" + str(new_var_list), new_var_list)
new_node.setCpt(new_cpt)
return new_node
def restrict(self, variable, value):
"""function that restricts a variable to some value
in a given factor"""
# Your code here
new_cpt = {}
new_var_list = list(self.varList)
new_var_list.remove(variable)
idx = self.varList.index(variable)
value = str(value)
for k, v in self.cpt.items():
if k[idx] == value:
new_cpt[k[:idx] + k[idx+1:]] = v
new_node = Node("f" + str(new_var_list), new_var_list)
new_node.setCpt(new_cpt)
return new_node
# create nodes for Bayes Net
B = Node("B", ["B"])
E = Node("E", ["E"])
A = Node("A", ["A", "B", "E"])
J = Node("J", ["J", "A"])
M = Node("M", ["M", "A"])
# Generate cpt for each node
B.setCpt({'0': 0.999, '1': 0.001})
E.setCpt({'0': 0.998, '1': 0.002})
A.setCpt({'111': 0.95, '011': 0.05, '110': 0.94, '010': 0.06,
'101': 0.29, '001': 0.71, '100': 0.001, '000': 0.999})
J.setCpt({'11': 0.9, '01': 0.1, '10': 0.05, '00': 0.95})
M.setCpt({'11': 0.7, '01': 0.3, '10': 0.01, '00': 0.99})
print("P(A) **********************")
VariableElimination.inference([B, E, A, J, M], ['A'], ['B', 'E', 'J', 'M'], {})
print("P(B | J~M) **********************")
VariableElimination.inference([B, E, A, J, M], ['B'], [
'E', 'A'], {'J': 1, 'M': 0})
Results
1
2
3
4
5
6
7
8
9
10
11
12
13
P(A) **********************
RESULT:
Name = f['A']
vars ['A']
key: 1 val : 0.0025164420000000002
key: 0 val : 0.997483558
P(B | J~M) **********************
RESULT:
Name = f['B']
vars ['B']
key: 0 val : 0.9948701418665987
key: 1 val : 0.0051298581334013015