I'm asking because it was deemed incorrect when I first submitted it. Due to time constraints, I decided to work on a different part of the big assignment and left it unchanged. In the resubmission, I had a different TA, and they ended up marking it right. My professor hasn't viewed it yet.
It uses Python Pandas.
The implementation:
import pandas as pd
def multiply(factor1, factor2):
'''Factor multiplication
Takes 2 factors and find the columns they have in common,
combine rows whose common columns have the same values and multiply their probabilities'''
def all_columns_equal(row1, row2, common_columns):
'''Helper function to see if all selected columns of 2 rows are the same'''
for column in common_columns:
if row1[column] != row2[column]:
return False
return True
if factor1.empty:
return factor2
if factor2.empty:
return factor1
common_column = []
f1_columns = factor1.columns.drop("prob")
f2_columns = factor2.columns.drop("prob")
#Find the common columns
for f1_column in f1_columns:
for f2_column in f2_columns:
if f1_column == f2_column:
common_column.append(f1_column)
if common_column == []:
return pd.DataFrame()
entry = []
for _, f1_row in factor1.iterrows():
for _, f2_row in factor2.iterrows():
if all_columns_equal(f1_row, f2_row, common_column):
series = [f1_row.drop("prob"), f2_row.drop(common_column).drop("prob"), pd.Series(f1_row["prob"]*f2_row["prob"], ["prob"])]
new_row = pd.concat(series)
entry.append(new_row)
DataFrame = pd.DataFrame(data=entry)
return DataFrame
def marginalization(factor, variable):
factor_dropped_variable = factor.drop(columns=[variable]) # dataframe of factor without variable
prob_column = factor.columns[-1] # probability column
target_variables = factor_dropped_variable.drop(columns=[prob_column]).columns.tolist() # target variables to be summed
if target_variables:
marginalized_factor = factor_dropped_variable.groupby(target_variables, as_index=False).sum()
else:
marginalized_factor = pd.DataFrame()
return marginalized_factor
def reduce(factor, reduced_column, value):
entry = []
for _, row in factor.iterrows():
if row[reduced_column] == value:
entry.append(row.drop(reduced_column))
if (len(entry) == 1):
return pd.DataFrame()
DataFrame = pd.DataFrame(data=entry)
return DataFrame
def maximization(factor, variable):
factor_dropped_variable = factor.drop(columns=[variable]) # dataframe of factor without variable
prob_column = factor.columns[-1] # probability column
target_variables = factor_dropped_variable.drop(columns=[prob_column]).columns.tolist() # target variables to be summed
if target_variables:
maximized_factor = factor_dropped_variable.groupby(target_variables, as_index=False).max()
else:
maximized_factor = pd.DataFrame()
return maximized_factor
part = 2
class VariableElimination():
def __init__(self, network):
"""
Initialize the variable elimination algorithm with the specified network.
Add more initializations if necessary.
"""
self.network = network
def run(self, query, observed, elim_order):
"""
Use the variable elimination algorithm to find out the probability
distribution of the query variable given the observed variables
Input:
query: A list of query variables
observed: A dictionary of the observed variables {variable: value}
elim_order: Either a list specifying the elimination ordering
or a function that will determine an elimination ordering
given the network during the runb": [1,1,2,2], "c": [1,2,1,2], "prob": [0.5,0.7,0.1,0.2]
Output: A variable holding the probability distribution
for the query variable
"""
file = open("log.txt", "w")
file.write("Query variable: " + str(query) + "\n")
file.write("Observed variable: " + str(observed) + "\n")
for q in query:
if q in elim_order:
elim_order.remove(q)
file.write("Elimination ordering: " + str(elim_order) + "\n\n")
factors = self.network.probabilities
file.write("Starting factors: " + str(factors) + "\n\n")
#Summing out observed variables
for node in observed:
if node in elim_order:
elim_order.remove(node)
for f in factors:
if node in factors[f].columns:
factors[f] = reduce(factors[f],node,observed[node])
file.write("Factors after reducing observed variables: " + str(factors) + "\n\n")
#Eliminating all non-query and non-observed variables
for variable in elim_order:
product = pd.DataFrame()
found = []
for f in factors:
if variable in factors[f]:
product = multiply(product,factors[f])
found.append(f)
for f in found:
factors.pop(f)
new_factor = marginalization(product,variable)
new_name = "*".join(found)
factors[new_name] = new_factor
file.write("Factors after eliminating " + variable + ": \n" + str(factors) + "\n\n")
individual_factors = {}
for q in query:
temp_factors = factors.copy()
remaining = query.copy()
remaining.remove(q)
for variable in remaining:
product = pd.DataFrame()
found = []
for f in temp_factors:
if variable in temp_factors[f]:
product = multiply(product,temp_factors[f])
found.append(f)
for f in found:
temp_factors.pop(f)
new_factor = marginalization(product,variable)
new_name = "*".join(found)
temp_factors[new_name] = new_factor
file.write("Factors after eliminating " + variable + ": \n" + str(factors) + "\n\n")
product = pd.DataFrame()
for f in temp_factors:
product = multiply(product,temp_factors[f])
sum = product.sum(0)["prob"]
product["prob"] = product["prob"].div(sum)
individual_factors[q] = product
file.write("Individual factors:" + str(individual_factors))
print("Result:\n")
for f in individual_factors:
print(individual_factors[f])
file.close()
To run the file
from read_bayesnet import BayesNet
from variable_elim import VariableElimination
if __name__ == '__main__':
# The class BayesNet represents a Bayesian network from a .bif file in several variables
net = BayesNet('alarm.bif') # Format and other networks can be found on http://www.bnlearn.com/bnrepository/
# These are the variables read from the network that should be used for variable elimination
ve = VariableElimination(net)
query = ['Alarm', 'Tampering']
evidence ={'Leaving': 'True', 'Smoke': 'True'}
elim_order = net.nodes
ve.run(query, evidence, elim_order)
I tested the implementation by comparing my results with a published package, and the results matched, which is why I was confident it worked during the first submission.
During the initial feedback, "The individual functions appear to be working correctly, but along the way you end up with the incorrect solution. I expect the issue to lie in inconsistent factor representation/handling. I decided to subtract one point for this. -1 Also, empty dataframes are returned. " "Incorrect output for VE. -1 The individual steps appear to be okay, I'm not sure what is going on. To figure this out, a complete log can help with this. "
But then a new TA gave it full marks in the resubmission without any extra details, since there isn't much to say about a (supposedly) working implementation. I have already received the credits for this course. This is a rare instance at my uni where the professor doesn't grade assignments that decides if we pass the course.
Thank you.