15. Ejercicio de las redes Bayesianicas
Una red de Bayes (RB) es un modelo gráfico probabilístico que usa inferencia de Bayes y está basado en el concepto de independencia condicional. Una red de Bayes tiene un grafo acíclico dirigido donde los vertices pueden ser literales de una lógica proposicional.
Aquí incluimos una clase de Python para representar literales. Esta clase será necesaria para la implementación de nuestra RB.
import re
class Literal:
def __init__(self,input=None,variable=None,value=None):
if input:
self.parse(input)
else:
self.variable = variable
self.value = value
def parse(self,input):
c = re.match("([~]?)\s*(\w+)",input)
if c is None:
raise Exception("cannot parse a literal from the input: "+ input)
self.variable = c.group(2)
self.value = not c.group(1)
def __str__(self):
return self.variable if self.value else "~"+self.variable
def __repr__(self):
return self.__str__()
def __hash__(self):
return hash(self.__str__())
def __eq__(self,l):
return l.variable == self.variable and l.value == self.value
def __ne__(self,other):
return not self.__eq__(other)
def __lt__(self,other):
if self.variable == other.variable:
return self.value < other.value
return self.variable < other.variable
Vamos a crear una literal l=¬A
l = Literal(variable='A',value=False)
print(l)
~A
La tilde (~) se utiliza como símbolo de la negación.
Tabla de Probabilidad Condicional
En una RB los vertices tienen asociados parámetros numéricos que representan probabilidades condicionales. Hemos definido una clase de Python que representa una tabla de parámetros. En el constructor indicamos la variable proposicional a la que se asocia la tabla y la tabla se especifica como una lista de tuplas. Cada tupla tiene dos valores, el primero es una cadena que contiene las literales de un renglón de la tabla separadas por coma. El segundo valor es la probabilidad correspondiente.
from itertools import product as cartesian
from functools import reduce
# Conditional probability table
class CPT:
# initializes the condional probability table for the given variable
# table, a list of pairs (v,p)
# where v is a string with a comma separated list of literals
# and p the corresponding probability
# for example:
# [("~A,~B",0.5),("~A,B",0.8),("A,~B",0.3),("A,B",0.9)]
def __init__(self,variable,table):
self.variable = variable
#parse variables from first row of table
self.parents = CPT.parseVariables(table[0][0])
self.fillDictionary(table)
# parses the variables from the first row of the table
@staticmethod
def parseVariables(s):
return set([l.variable for l in CPT.stringToLiteralList(s)])
# obtains all variations of the given variables
@staticmethod
def computeKeys(variables):
entries = []
if len(variables) == 1:
(v,)= variables
keys = [CPT.formatLiteral(Literal(variable=v,value=False)),\
CPT.formatLiteral(Literal(variable=v,value=True))]
else:
for e in [CPT.flatten(i,[]) \
for i in list(reduce(lambda x,y:cartesian(x,y), \
[cartesian([v],[False,True]) for v in sorted(variables)]))]:
entries.append([Literal(variable=a[0],value=a[1]) for a in e])
keys = [reduce(lambda x,y: \
CPT.formatLiteral(x)+','+CPT.formatLiteral(y),e) for e in entries]
return keys
@staticmethod
def formatLiteral(l):
return str(l).rjust(len(str(l))+1) \
if l.value else str(l).rjust(len(str(l)))
# fills the conditional probability table
def fillDictionary(self,table):
self.table = {self.hashString(row[0]):row[1] for row in table}
# converts the string to a list of literals
@staticmethod
def stringToLiteralList(s):
l=[]
# there are parents
if s:
l = [Literal(l) for l in s.split(",")]
return l
# hashes the provided string (list of literals)
def hashString(self,s):
return hash(frozenset(self.stringToLiteralList(s)))
# allows indexing of the table
def __getitem__(self,s):
return self.table[self.hashString(s)]
# allows changing probabilities in the table
def __setitem__(self,s,p):
self.table[self.hashString(s)] = p
def __repr__(self):
return self.__str__()
# pretty printing of the conditional probability table
def __str__(self):
s = "CPT for variable "+self.variable+"\n"
if self.parents:
for key in CPT.computeKeys(self.parents):
s += "P("+self.variable+"|"+key+") = "\
+str("%.4f" % self[key]) + "\n"
else:
s += "P("+self.variable+ ") = " + str("%.4f" % self['']) + "\n"
return s
# flattens a nested tuple
@staticmethod
def flatten(x,l=[]):
if not isinstance(x[0],tuple):
l.extend([x])
else:
for i in x:
CPT.flatten(i,l)
return l
En el siguiente ejemplo creamos una tabla de probabilidad condicional para la variable B. En este ejemplo tenemos:
| P(B∣A)= | 0.30 |
|---|---|
| P(B∣¬A)= | 0.15 |
tabla = CPT(
'B',[('A',0.3),('~A',0.15)])
print(tabla)
CPT for variable B P(B|~A) = 0.1500 P(B| A) = 0.3000
Red bayesiana
La siguiente es una implementación en Python de la RB. Hemos dejado indicado donde debes agregar tu código para la tarea de programación.
class BayesianNetwork:
#Initializes the Bayesian network
# cpts a dictionary with the conditional probability tables
# the dictionary is indexed by the vertex variable
def __init__(self,cpts=None):
if cpts is not None:
self.cpts = cpts
self.variables = set(cpts.keys())
else:
self.cpts = {}
self.variables = set()
def setTable(self,table):
self.cpts[table.variable]=table
self.variables.add(table.variable)
# computes the probability expressed in the given query
def query(self,q):
if "|" in q:
s = q.split("|")
p = self.query(s[0]+","+s[1])/self.query(s[1])
else:
#obtains all variables in the query
mentioned = CPT.parseVariables(q)
#obtains the missing variables
missing = set(self.variables).difference(mentioned)
if not missing:
p = self.atomic(q)
else:
p = self.nonatomic(q,missing)
return p
# computes the probability of an atomic event
def atomic(self,q):
p = 1
q_literals = CPT.stringToLiteralList(q)
for v in q_literals:
s = ",".join(\
map(lambda x:str(x), filter(lambda x:x.variable \
in self.cpts[v.variable].parents,q_literals)))
p *= self.cpts[v.variable][s] \
if v.value else 1-self.cpts[v.variable][s]
return p
# debes modificar este método para calcular la probabilidad
# de un evento no atómico
def nonatomic(self,q,missing):
p = 0
for key in CPT.computeKeys(missing):
# inserta tu código aquí, borra la palabra pass
# debes actualizar el valor de p aquí
pass
return p
def __str__(self):
s = ''
for v in self.variables:
s += str(self.cpts[v])+"\n"
return s
El método computeKeys de la tabla de probabilidad condicional recibe un conjunto de variables y te regresa todas las variaciones de literales posibles para las variables.
#ejemplo del uso del método computeKeys
tabla.computeKeys({'A','B'})
['~A,~B', '~A, B', ' A,~B', ' A, B']
En tu tarea hemos puesto un ciclo for que itera sobre estas posibilidades. Nota que ya te hemos dado un método para calcular la probabilidad de un evento atómico.
relatedInteligencia Artificial