Class: BayesNet

Inherits:
DirectedAdjacencyGraph
  • Object
show all
Defined in:
lib/bn4r/bn_algorithms.rb,
lib/bn4r/bn.rb,
lib/bn4r/bn_export.rb,
lib/bn4r/bn_import.rb

Overview

Inference Algorithms for Bayesian Network Library for Ruby

Author: Sergio Espeja ( http://www.upf.edu/pdi/iula/sergio.espeja, sergio.espeja at gmail.com )

Developed in: IULA ( http://www.iula.upf.es ) and 
in bee.com.es ( http://bee.com.es )

== Current implemented algorithms
* enumeration_ask
* prior_sample
* rejection_sampling
* likelihood_weighting

Instance Method Summary collapse

Instance Method Details

#add_edge(parent, child, tag = nil) ⇒ Object

Adds a directed edge between parent and child BayesNetNodes labeled with tag ( if tag is included, othewise the label is nil ).



27
28
29
30
31
32
33
34
35
36
 
# File 'lib/bn4r/bn.rb', line 27

def add_edge(parent, child, tag=nil)
  raise "Nodes must be of the class BayesNetNodes" if parent.class != BayesNetNode or child.class != BayesNetNode
  raise "Self relations not allowed in BayesNet" if parent == child
  raise "Diferent BayesNetNodes with equal name: " + parent.name if parent.name == child.name
  
  edge = super(parent, child)
  child.parents << parent unless child.parents.include? parent
  child.relations << tag if !tag.nil?
  edge
end

#all_nodes_with_values? ⇒ Boolean

Returns true if all nodes have values.

Returns:

  • (Boolean) 


136
137
138
 
# File 'lib/bn4r/bn.rb', line 136

def all_nodes_with_values?
  vertices.select {|v| !v.value.nil? }.size == vertices.size
end

#childs(v) ⇒ Object

Returns an array with childs of given node ( or vertice )



56
57
58
59
60
61
62
 
# File 'lib/bn4r/bn.rb', line 56

def childs(v)
  begin
    self.adjacent_vertices(v)
  rescue RGL::NoVertexError
    []
  end
end

#clear_values! ⇒ Object

Clears the value of all BayesNetNodes in Bayes Net.



70
71
72
 
# File 'lib/bn4r/bn.rb', line 70

def clear_values!
    vertices.each { |v| v.clear_value }
end

#create_from_xmlbif(file, bn = self) ⇒ Object 



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
 
# File 'lib/bn4r/bn_import.rb', line 26

def create_from_xmlbif(file, bn=self)
    doc = Document.new File.open(file, "r")

    # first go through and add the variables
    doc.elements.each("BIF/NETWORK/VARIABLE") { |variable|

      name = variable.elements["NAME"]

      outcomes = []
      variable.elements.each("OUTCOME") { |outcome|
        outcomes << outcome.text
      }
      # transform from text to boolean
      if outcomes.size == 2 and outcomes.include?("true") and outcomes.include?("false")
        outcomes = outcomes.collect {|o| o == "true"}
      end
      node = BayesNetNode.new( name.text, outcomes )
      bn.add_vertex(node)
    }

    # for each variable we list, we will look up 
    # the conditional probability table for it.

    doc.elements.each("BIF/NETWORK/DEFINITION/") { |definition|
      node = get_variable( definition.elements["FOR"].text )
      givens_array = []
      definition.elements.each("GIVEN") { |given|
        givens_array << get_variable( given.text )
      }

      table = definition.elements["TABLE"].text.split

      givens_array.each { |g| bn.add_edge(g, node) }

      node.set_probability_table(givens_array, table)      
    }
    bn
end

#deep ⇒ Object

Returns de deep of the bayes net (larger path from a root node to a child node).



116
117
118
 
# File 'lib/bn4r/bn.rb', line 116

def deep
  vertices.collect {|root| root.deep }.max
end

#each_child(v) ⇒ Object

Iterates all the childs of given node ( or vertice )



65
66
67
 
# File 'lib/bn4r/bn.rb', line 65

def each_child(v)
  childs(v).each { |child| yield child }
end

#each_leaf ⇒ Object

Iterates all the leaf nodes ( or vertices )



91
92
93
 
# File 'lib/bn4r/bn.rb', line 91

def each_leaf
  leafs.each { |leaf| yield leaf }
end

#enumeration_ask(x, e, bn_vertices = vertices) ⇒ Object

ENUMERATION ASK algorithm

Implementation based on: S.Russell, P.Norving, “Artificial Intelligence, A Modern Approach”, 2nd Edition. pp 506

x –> query variable

e –> variables with observed values



29
30
31
32
33
34
35
36
37
38
 
# File 'lib/bn4r/bn_algorithms.rb', line 29

def enumeration_ask(x,e, bn_vertices = vertices)
  e << x
  q = []
  #p bn_vertices.collect { |v| v.name }
  x.outcomes.each {|outcome|
    x.set_value(outcome)
    q << enumerate_all(bn_vertices, e)
  }
  q
end

#get_variable(text) ⇒ Object

Gets the variable with given name.



75
76
77
78
 
# File 'lib/bn4r/bn.rb', line 75

def get_variable( text )
  vertices.each { |v| return v if v.name == text }
  return nil
end

#inference_by_enumeration ⇒ Object

Return the probability of a distribution in the bayes net all nodes in the Bayes Net must have a value, otherwise will raise a exception



122
123
124
125
126
 
# File 'lib/bn4r/bn.rb', line 122

def inference_by_enumeration
  prob = 1.0;
  vertices.each {|v| prob = prob * p_v_cond_parents(v)}
  prob
end

#leafs ⇒ Object

Returns the leaf nodes



86
87
88
 
# File 'lib/bn4r/bn.rb', line 86

def leafs
  vertices.select { |v| childs(v).size == 0 }
end

#likelihood_weighting(x, e, n, bn = self) ⇒ Object

Returns an estimation of P(X=x|e) = <P(X=x|e), 1 - P(X=x|e)> obtained.

Implementation based on: S.Russell, P.Norving, “Artificial Intelligence, A Modern Approach”, 2nd Edition. pp 515

x –> query variable

e –> variables with observed values, must be a copy of the nodes in bn ( Can’t be the BayesNetNodes instaces that are in bn ).

n –> Number of samples generated

WARNING: Clears the values of current bn!



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File 'lib/bn4r/bn_algorithms.rb', line 121

def likelihood_weighting( x, e, n, bn = self )

  retval = [0.0, 0.0]
  n.times {
    w_sample, w = weighted_sample(e) # ask for a weighted_sample with given evidences
    value = w_sample.select { |v| v.name == x.name }[0].value # select the value for the query variable

    if value == (x.value || true) # if no value for x, ask for true
      retval[1] += w
    else
      retval[0] += w
    end
  }

  # Normalize results
  norm = retval[1].to_f / (retval[0]+retval[1]).to_f

  return [norm, 1-norm]
end

#nodes_ordered_by_breath_first_search(nodes = roots, bn_ordered = Array.new) ⇒ Object

Returns nodes ordered by Breath First Search



152
153
154
155
156
157
158
159
160
 
# File 'lib/bn4r/bn.rb', line 152

def nodes_ordered_by_breath_first_search(nodes = roots, bn_ordered = Array.new)

  nodes.each { |v| 
    next if bn_ordered.include?(v)
    bn_ordered << v
    nodes_ordered_by_breath_first_search(childs(v), bn_ordered)
  }
  return bn_ordered.flatten
end

#nodes_ordered_by_dependencies(nodes = vertices, bn_ordered = Array.new) ⇒ Object

Returns nodes ordered by dependencies ( from those who haven’t ( roots ) to leaves ).



142
143
144
145
146
147
148
149
 
# File 'lib/bn4r/bn.rb', line 142

def nodes_ordered_by_dependencies(nodes = vertices, bn_ordered = Array.new)
  nodes.each { |v| 
    next if bn_ordered.include?(v)
    nodes_ordered_by_dependencies(v.parents, bn_ordered) if !v.root?
    bn_ordered << v 
   }
   return bn_ordered.flatten
end

#num_parents(v) ⇒ Object

Returns the number of parents of a node.



110
111
112
 
# File 'lib/bn4r/bn.rb', line 110

def num_parents(v)
  return v.parents.size
end

#p_v_cond_parents(v) ⇒ Object

Returns the probability of a node conditioned to his parents:

P(v|parents(v))



130
131
132
133
 
# File 'lib/bn4r/bn.rb', line 130

def p_v_cond_parents(v)
  givens_assignments = v.parents.collect {|parents| parents.value}
  v.get_probability(v.value, givens_assignments).to_f
end

#prior_sample(nodes_ordered = nodes_ordered_by_dependencies) ⇒ Object

Returns a sample from prior joint distribution specified by the network.

Implementation based on: S.Russell, P.Norving, “Artificial Intelligence, A Modern Approach”, 2nd Edition. pp 511-512

The input are the nodes of the bn ordered by dependencies see nodes_ordered_by_dependencies



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/bn4r/bn_algorithms.rb', line 46

def prior_sample(nodes_ordered = nodes_ordered_by_dependencies)
  sample = Array.new
  nodes_ordered.each { |v|
    value = nil
    prob = 0.0; r_prob = rand
    v.outcomes.each { |outcome| 
      prob += v.get_probability(outcome)
      value = outcome and break if r_prob < prob
    }
    v.set_value(value) 
    sample << v.copy
  }
  # leave the bn clear of values.
  nodes_ordered.each { |v| v.clear_value }

  return sample
end

#rejection_sampling(x, e, n, bn = self) ⇒ Object

Returns an estimation of P(X=x|e) = <P(X=x|e), 1 - P(X=x|e)> obtained. Generates samples from prior joint distribution specified by the network, rejects all those that do not match the evidence, and finally counts hoy often X = x occurs in remaining samples.

Caution, this algorthm is unusable for complex problems because rejects many samples!

Implementation based on: S.Russell, P.Norving, “Artificial Intelligence, A Modern Approach”, 2nd Edition. pp 513

x –> query variable

e –> variables with observed values

n –> Number of samples generated



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
 
# File 'lib/bn4r/bn_algorithms.rb', line 79

def rejection_sampling( x, e, n, bn = self )

    evidece_list = [e] if e.class != Array
    x_list = [x] if x.class != Array
         
    nodes_ordered = bn.nodes_ordered_by_dependencies
    evidence_vector = get_vector_value(evidece_list, nodes_ordered)
    x_vector = get_vector_value(x_list, nodes_ordered)
    
    total_valid = 0; total_correct = 0
    n.times do
      sample_vector  = bn.prior_sample(nodes_ordered).collect {|v| v.value}
      
      valid = true; correct = true
      for i in 0..(sample_vector.size-1) do
        correct = false if !x_vector[i].nil? and sample_vector[i] != x_vector[i]
        valid = false and break if !evidence_vector[i].nil? and sample_vector[i] != evidence_vector[i]
      end
      
      next if !valid
      total_valid += 1
      total_correct += 1 if correct  
    end
    
    p_true = total_correct.to_f/total_valid.to_f
    return [p_true, 1-p_true]
    #return [total_correct.to_f, total_valid.to_f]
end

#remove_vertex(v) ⇒ Object

Removes a vertex and its edges of the BayesNet, removing also its references from childs nodes.



40
41
42
43
 
# File 'lib/bn4r/bn.rb', line 40

def remove_vertex(v)
  self.each_child(v) {|c| c.parents.delete(v)}
  super(v)
end

#root?(v) ⇒ Boolean

Returns true/false if given Node is root.

Returns:

  • (Boolean) 


104
105
106
107
 
# File 'lib/bn4r/bn.rb', line 104

def root?(v)
  return true if num_parents(v) == 0
  false
end

#roots ⇒ Object

Returns the root nodes of the Bayes Net.



81
82
83
 
# File 'lib/bn4r/bn.rb', line 81

def roots
  vertices.select { |v| root?(v) }
end

#siblings(v) ⇒ Object 



95
96
97
98
99
100
 
# File 'lib/bn4r/bn.rb', line 95

def siblings(v)
  return roots if v.root?
  v.parents.map do |p|
    childs(p)
  end.flatten.uniq
end

#to_dot(bn = self) ⇒ Object 



20
21
22
23
24
 
# File 'lib/bn4r/bn_export.rb', line 20

def to_dot(bn = self)
  #TODO: label relations between nodes
  #TODO: print information about probabilities tables?
  bn.to_dot_graph.to_s
end

#to_xbn(bn = self) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/bn4r/bn_export.rb', line 26

def to_xbn(bn = self)
  #TODO beautify code using REXML
  xbn_str = "<?xml version=\"1.0\"?>\n"
  xbn_str += "<ANALYSISNOTEBOOK NAME=\"Notebook.bndefault\" ROOT=\"bndefault\">\n"
  xbn_str += "<BNMODEL NAME=\"bndefault\"><STATICPROPERTIES><FORMAT>MSR DTAS XML</FORMAT>\n"
  xbn_str += "      <VERSION>1.0</VERSION>\n"
  xbn_str += "        <CREATOR>Microsoft Research DTAS</CREATOR>\n"
  xbn_str += "        </STATICPROPERTIES>\n"
  xbn_str += "      <DYNAMICPROPERTIES><PROPERTYTYPE NAME=\"DTASDG_Notes\" TYPE=\"stringarray\"><COMMENT>Notes on the diagram</COMMENT>\n"
  xbn_str += "          </PROPERTYTYPE>\n"
  xbn_str += "        <PROPERTYTYPE NAME=\"MS_Addins\" TYPE=\"stringarray\"/>\n"
  xbn_str += "        </DYNAMICPROPERTIES>\n"

  xbn_str += xbn_variables(bn)
  xbn_str += xbn_structure(bn)
  xbn_str += xbn_distributions(bn)
  
  xbn_str += "  </BNMODEL>\n"
  xbn_str += "</ANALYSISNOTEBOOK>\n"
  
end