Previous  Up  Next

Module Circuit

module Circuit: sig .. end
The Circuit module provides an interface for working with arithmetic circuits, so that learning and inference algorithms can be built on top of this data structure/inference representation.

Node 

type ndetails = Node.ndetails =
| TimesNode (*Represents products in the circuits*)
| PlusNode (*Represents sums in the circuits*)
| VarNode of int * int (*Indicator variable for (var,value) pair*)
| ConstNode of float (*Represents parameters (log-space)*)
| NullNode (*Represents dummy nodes*)
Different types of nodes in arithmetic circuits
type node = Node.node = {
   hashid : int; (*Unique auto-increment id*)
   mutable id : int; (*Shows the index of node in the citcuit.nodes.*)
   mutable parents : node list; (*List of parent nodes in the circuit graph.*)
   mutable children : node list; (*List of children nodes in the circuit graph.*)
   mutable details : ndetails; (*Type of the node.*)
}
Each element in an arithmetic circuit is a node (including parameters, plus, times, and indicators), which has a unique hashid. Node maintains a list of its parent and its children nodes in the circuit graph.

Node operations 

val null_node : node
Creates a node with type NullNode, and its parent and children lists are empty.
val create_node : ndetails -> node list -> node
Creates a node with the given node specification and children.
val ncopy : node -> node
Copy constructor.
val create_var : int -> int -> node
Creates an indicator node.
val create_const : float -> node
Creates a constant node (parameter node).
val create_times : node list -> node
Creates a times (product) node.
val create_plus : node list -> node
Creates a plus (sum) node.
val is_times : node -> bool
Checks whether the node is a times (product) node.
val is_plus : node -> bool
Checks whether the node is a plus (sum) node.
val is_var : node -> bool
Checks whether the node is an indicator node.
val is_const : node -> bool
Checks whether the node is a constant (parameter) node.
val is_null : node -> bool
Checks whether the node is a null node.
val const_value : node -> float
Gets the parameter value stored in the constant node
val var_details : node -> int * int
var_details node returns the variable-value pair if node is an indicator variable node
val var_var : node -> int
var_var node returns the variable if node is a variable node
val var_value : node -> int
var_value node returns the value if node is a variable node
val is_var_product : node -> bool
is_var_product node returns true if node is a product of a constant and an indicator variable.
val is_sot_dist : node -> bool
is_sot_dist node returns true if node is a sum of variable products (constants times indicator variables). Nodes with this structure are used to represent marginal distributions over individual variables.
val set_const : node -> float -> unit
set_const node wt sets the value of const node node to wt.
val add_child : node -> node -> unit
add_child parent child appends child to the children of parent and updates the parent of child accordingly.
val remove_child : node -> node -> unit
remove_child parent child removes child from the children of parent and updates child accordingly.
val remove_all_children : node -> unit
remove_all_children parent removes all children of parent.
val remove_all_parents : node -> unit
remove_all_parents child removes all parents of child.
val unlink : node -> unit
unlink node removes all parents and children of node.
val id : node -> int
id node returns the id of node.
val parents : node -> node list
parents node returns the parents of node.
val children : node -> node list
children node returns the children of node.
val num_children : node -> int
num_children node returns the number of children of node.

Printing and debugging operations

val node_name : node -> string
node_name returns the name of node node, e.g., "n5".
val string_of_node : node -> string
string_of_node node returns a string representation of node node.
val output_node : Pervasives.out_channel -> node -> unit
output_node out node writes node node to the output channel out.
val output_root : Pervasives.out_channel -> int array -> node -> unit
output_root out schema root recursively writes circuit to output channel out, starting at the root.
val print_node : node -> unit
Prints a single node to stdout.
val print_node_endline : node -> unit
Prints a single node to stdout, including a newline at the end.

Arithmetic circuits

exception Unknown_child of string * string
Parse error: Node references a child that has not yet been defined.
exception NonConstantFeatureWeight of int
Parse error: Node used for feature weight is not a const node.
exception UnsupportedNodeType
Type error: Given node type is not supported by this function.

Auxilary types

type evidence_t = float array array
Evidence data structure that specifies value of each indicator variable.
type schema_t = Data.schema_t
Data types from Data module.
type example_t = Data.example_t

Circuit type

type circuit = {
   schema : schema_t; (*Data schema specifies the range of each variable.*)
   vnodes : node array array; (*Array of arrays of indicator nodes. vnodes.(i).(j) is the indicator variable node for state j of variable i.*)
   vnodes_l : node list array; (*Array of lists of indicator nodes. Redundant with vnodes, but maintained for convenience.*)
   flat_vnodes : node array; (*Array of all indictator variables. Redundant with vnodes, but maintained for convenience.*)
   mutable nodes : node array; (*All nodes in the circuit.*)
   mutable root : node; (*The circuit root node.*)
   mutable size : int; (*The number of nodes in the circuit.*)
}
Data structure for arithmetic circuits. Fields are mutable so that the circuit can be updated in place.

Circuit operations

val load : Pervasives.in_channel -> circuit
Reads an arithmetic circuit from a file description.
val output : Pervasives.out_channel -> circuit -> unit
Stores an arithmetic circuit in the regular plain text format.
val output_js : Pervasives.out_channel -> circuit -> unit
Stores an arithmetic circuit in the javascript format for visualizing using Digraph.
val output_dot : Pervasives.out_channel -> circuit -> unit
Stores an arithmetic circuit in the dot format (for visualizing).
val print : circuit -> unit
Prints an arithmetic circuit to stdout.
val schema : circuit -> schema_t
Returns the schema of an arithmetic circuit.
val numvars : circuit -> int
Returns the number of variables in an arithmetic circuit.
val node : circuit -> int -> node
Returns the node at a specific index.
val all_var_dists : circuit -> node list
all_var_dists circ returns all plus nodes in the circuit circ that represent distributions.
val dist_var : node -> int
dist_var n returns the index of the random variable being modeled given the node n representing a multinomial distribution.
val all_vars : circuit -> node array array
Returns all indicator nodes (variable nodes).
val sibling_vars : circuit -> node -> node list
sibling_vars circ n returns a list of all indicator nodes for all values of the same variable given the indicator node n for a particular variable/value combination. For example, given the indicator node for x_5=1, it returns indicators for x_5=0, x_5=1, ..., x_5=k.
val var : circuit -> int -> node array
var circ i returns the array of indicator nodes for the given random variable index i and the circuit circ.
val flat_vars : circuit -> node array
Returns a flat array of all indicator nodes for all random variables.
val order : circuit -> unit
Puts all nodes in the circuit into a topological partial order.
val make_vnodes : schema_t -> node array array
Creates an indicator variable for each state of every variable based on the given schema
val rebuild : circuit -> unit
Rebuilds the circuit data structure from the root node. Fixes inconsistent parent/child relationships and removes orphaned nodes, leading to a compact and consistent node array.
val of_graph : schema_t ->
       node array array ->
       node list array -> node -> circuit
of_graph schema vn vnl root constructs a new circuit from schema and root node and places it in topological order. vn is node
val depth : circuit -> int
Returns the depth of an arithmetic circuit
val update_parents : circuit -> unit
Update parent references for all nodes to be consistent.
val num_edges : circuit -> int
Return the number of edges in an arithmetic circuit.
val num_params : circuit -> int
Return the number of parameters in an arithmetic circuit.

Create, set evidence

val create_evidence_s : schema_t -> evidence_t
create_evidence schema creates an matrix of ones as the values of indicator variables. Each column corresponds to a variable in the schema.
val create_evidence : circuit -> evidence_t
Returns create_evidence_s of the circuit.schema.
val ev_true : evidence_t -> int -> int -> unit
val ev_false : evidence_t -> int -> int -> unit
val set_evidence : 'a array -> circuit -> 'a array array -> unit

Other evidence related operations

val example_to_ev : schema_t -> example_t -> evidence_t
val ev_intersect : evidence_t -> evidence_t -> bool
ev_intersect e1 e2 returns true when evidence e1 and e2 are not mutually exclusive.
val ev_subset : evidence_t -> evidence_t -> bool
ev_subset e1 e2 returns true if evidence e1 is subset of evidence e2 (i.e. pr(e1|e2) = 1.0 )
val ev_intersect2 : evidence_t -> evidence_t -> bool
val ev_union : circuit ->
       evidence_t -> evidence_t -> evidence_t
ev_union circuit ev1 ev2 creates another evidence e such that e is the union of ev1 and ev2. ev_union suppose that ev1 and ev2 are not mutualy exclusive.
val print_ev : evidence_t -> unit
Print evidence data structure to stdout.

Arithmetic circuits for Markov networks

type condition = bool * int * int
condition represents a variable value combination in features. For example, (true,5,1) means that variable 5 has state 1, and (false, 5, 1) means that variable 5 does not have state 1.
type feature = {
   acnode : node; (*Node containing the feature weight*)
   mutable weight : float; (*The feature weight*)
   cond : condition list; (*The set of conditions that creates a feature, e.g. +v3_1 +v4_2 +v6_0*)
   ev : evidence_t;
}
Represents feature and its weight in the coresponding log-linear model of the arithmetic circuit.
val feature_node : feature -> node
feature_node f returns the acnode related to the feature f.
val feature_value : feature -> float
feature_value f returns the value of feature f when its condition is satisfied.
val set_feature_value : feature -> float -> unit
set_feature_value f wt sets the value of feature f to wt, modifying the associated constant node.
val feature_contains_var : feature -> node -> bool
feature_contains_var f v returns true if feature f has a condition of variable v.
val prune_for_evidence : circuit -> example_t -> unit
Prunes a circuit conditioned on evidence. May leave the parent references for some nodes in an inconsistent state - use update_parents to fix.
val c_satisfied : example_t -> condition -> bool
c_satisfied x cond returns true if x satisfies cond.
val f_satisfied : example_t -> feature -> bool
f_satisfied x f returns true if an instance x satisfies all conditions of feature f.
val prune_features : feature list -> example_t -> feature list
Prunes features by removing empty, redundant, and contradictory circuit features. Returns shortened list of simplified features.
val conditions_to_ev : schema_t -> condition array -> evidence_t
Converts a condition to evidence.
val cond_intersect : schema_t ->
       condition array -> condition array -> bool
Returns true when two given conditions are not mutually exclusive.

Read/Write features

val string_of_feature : feature -> string
Converts the given feature to a string
val output_feature : Pervasives.out_channel -> feature -> unit
output_feature out f writes feature f to the output channel out.
val output_with_features : Pervasives.out_channel -> circuit -> feature list -> unit
Stores the given arithmetic circuit and feature list in .ac format.
val output_root_with_features : Pervasives.out_channel ->
       schema_t -> node -> feature list -> unit
Stores the given arithmetic circuit and feature list in .ac format, given the circuit schema, root node, and feature list.
val output_features : Pervasives.out_channel -> node -> feature list -> unit
Stores the feature list given the circuit root.
val load_with_features : Pervasives.in_channel -> circuit * feature list
Reads an arithmetic circuits and log-linear features from .ac file. Used for arithmetic circuts that represent log-linear models.

Circuit derivatives 

type deriv_scratch = {
   dr : float array; (*Derivative of root with respect to each node.*)
   vr : float array; (*Log value of each node.*)
   vr_nz : float array;
   bit1 : bool array;
   bit2 : bool array;
   cids : int array array;
}
Data structure for computing the derivatives of circuits with respect to features.
val create_deriv_scratch : circuit -> deriv_scratch
Initializes the data structure for computing the derivatives. Reusing this data structure is much more efficient than creating it for every single query.
val get_derivatives_raw : circuit -> deriv_scratch -> evidence_t -> unit
Computes derivatives of an arithmetic circuit with respect to all features conditioned on evidence. Updates the deriv_scratch data structure in place.

Inference using arithmetic circuits

type scratch_t = float array * int array array
Helper data structure for circuit inference. Caches node values and child ids for each node. Reusing it over multiple queries is much faster than recreating it each time.
val create_scratch : circuit -> scratch_t
Create helper data structure.
val logvalues : scratch_t -> circuit -> float array
Maps Circuit.circuit.nodes to their logvalues after the evaluation of the circuit.
val logprob_ev : scratch_t -> circuit -> evidence_t -> float
logprob_ev scratch circ ev returns the log probability of evidence structure ev in circuit circ. For arithmetic circuits that represent Bayesian networks the log probability is normalized, but for circuits representing Markov networks it is unnormalized. scratch can be constructed using Circuit.create_scratch.
val logprob_x : scratch_t -> circuit -> example_t -> float
logprob_x scratch circ x returns the log probability of example x in circuit circ. For arithmetic circuits that represent Bayesian networks the log probability is normalized, but for circuits representing Markov networks it is unnormalized. scratch can be created using Circuit.create_scratch.
val get_logmarginals : circuit ->
       deriv_scratch -> example_t -> float array array
get_logmarginals circ ds ev returns the log-marginals of all variables in circuit circ given evidence ev. ds can be created using Circuit.create_deriv_scratch.
val get_marginals : circuit ->
       deriv_scratch -> example_t -> float array array
get_marginals circ ds ev return the marginals of all variables in circuit circ given evidence ev. ds can be created using Circuit.create_deriv_scratch.
val compute_z : scratch_t -> circuit -> float
Returns the log partition function.
val get_mpe : circuit -> deriv_scratch -> example_t -> int array
get_mpe circ ds e computes the MPE state of variables given the circuit circ, its empty derivative data structure ds, and the evidence ev.

Map and Set modules for Node (based on Hashtbl)

module NSet: sig .. end
module NMap: sig .. end
val node_iter : (node -> 'a) -> node -> unit
node_iter f root applies function f to every node in the circuit rooted at root.
val node_map : (node -> 'a) -> node -> 'a list
node_map f root applies function f to every node in the circuit rooted at root and creates a list of the results.
val root_to_list : node -> node list
root_to_list root generates a list of all nodes reachable from root.
val relatedl_a : int -> (node -> node list) -> node list -> bool array
relatedl_a size rel nl returns an array in which the ith element is true if the node with id i is reachable from some node in nl through relation rel. Useful for generating lists of ancestor or descendant nodes, represented as bit vectors.
val a_mem : 'a array -> node -> 'a
a_mem a n returns the ith element of array a, where i is the id of node n. Similar to NMap.find but faster.