Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/bnt/inference/static/@jtree_inf_engine/jtree_inf_engine.m @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
wolffd@0 1 function engine = jtree_inf_engine(bnet, varargin)
wolffd@0 2 % JTREE_INF_ENGINE Junction tree inference engine
wolffd@0 3 % engine = jtree_inf_engine(bnet, ...)
wolffd@0 4 %
wolffd@0 5 % The following optional arguments can be specified in the form of name/value pairs:
wolffd@0 6 % [default value in brackets]
wolffd@0 7 %
wolffd@0 8 % clusters - a cell array of sets of nodes we want to ensure are in the same clique (in addition to families) [ {} ]
wolffd@0 9 % root - the root of the junction tree will be a clique that contains this set of nodes [N]
wolffd@0 10 % stages - stages{t} is a set of nodes we want to eliminate before stages{t+1}, ... [ {1:N} ]
wolffd@0 11 %
wolffd@0 12 % e.g., engine = jtree_inf_engine(bnet, 'maximize', 1);
wolffd@0 13 %
wolffd@0 14 % For more details on the junction tree algorithm, see
wolffd@0 15 % - "Probabilistic networks and expert systems", Cowell, Dawid, Lauritzen and Spiegelhalter, Springer, 1999
wolffd@0 16 % - "Inference in Belief Networks: A procedural guide", C. Huang and A. Darwiche,
wolffd@0 17 % Intl. J. Approximate Reasoning, 15(3):225-263, 1996.
wolffd@0 18
wolffd@0 19
wolffd@0 20 % set default params
wolffd@0 21 N = length(bnet.dag);
wolffd@0 22 clusters = {};
wolffd@0 23 root = N;
wolffd@0 24 stages = { 1:N };
wolffd@0 25 maximize = 0;
wolffd@0 26
wolffd@0 27 if nargin >= 2
wolffd@0 28 args = varargin;
wolffd@0 29 nargs = length(args);
wolffd@0 30 if ~isstr(args{1})
wolffd@0 31 error('the interface to jtree has changed; now, onodes is not allowed and all optional params must be passed by name')
wolffd@0 32 end
wolffd@0 33 for i=1:2:nargs
wolffd@0 34 switch args{i},
wolffd@0 35 case 'clusters', clusters = args{i+1};
wolffd@0 36 case 'root', root = args{i+1};
wolffd@0 37 case 'stages', stages = args{i+1};
wolffd@0 38 case 'maximize', maximize = args{i+1};
wolffd@0 39 otherwise,
wolffd@0 40 error(['invalid argument name ' args{i}]);
wolffd@0 41 end
wolffd@0 42 end
wolffd@0 43 end
wolffd@0 44
wolffd@0 45 engine = init_fields;
wolffd@0 46 engine = class(engine, 'jtree_inf_engine', inf_engine(bnet));
wolffd@0 47
wolffd@0 48 engine.maximize = maximize;
wolffd@0 49
wolffd@0 50 onodes = bnet.observed;
wolffd@0 51
wolffd@0 52 %[engine.jtree, dummy, engine.cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ...
wolffd@0 53 % dag_to_jtree(bnet, onodes, stages, clusters);
wolffd@0 54
wolffd@0 55 porder = determine_elim_constraints(bnet, onodes);
wolffd@0 56 strong = ~isempty(porder);
wolffd@0 57 ns = bnet.node_sizes(:);
wolffd@0 58 ns(onodes) = 1; % observed nodes have only 1 possible value
wolffd@0 59 [engine.jtree, root2, engine.cliques, B, w] = ...
wolffd@0 60 graph_to_jtree(moralize(bnet.dag), ns, porder, stages, clusters);
wolffd@0 61
wolffd@0 62
wolffd@0 63 engine.cliques_bitv = B;
wolffd@0 64 engine.clique_weight = w;
wolffd@0 65 C = length(engine.cliques);
wolffd@0 66 engine.clpot = cell(1,C);
wolffd@0 67
wolffd@0 68 % Compute the separators between connected cliques.
wolffd@0 69 [is,js] = find(engine.jtree > 0);
wolffd@0 70 engine.separator = cell(C,C);
wolffd@0 71 for k=1:length(is)
wolffd@0 72 i = is(k); j = js(k);
wolffd@0 73 engine.separator{i,j} = find(B(i,:) & B(j,:)); % intersect(cliques{i}, cliques{j});
wolffd@0 74 end
wolffd@0 75
wolffd@0 76 % A node can be a member of many cliques, but is assigned to exactly one, to avoid
wolffd@0 77 % double-counting its CPD. We assign node i to clique c if c is the "lightest" clique that
wolffd@0 78 % contains i's family, so it can accomodate its CPD.
wolffd@0 79
wolffd@0 80 engine.clq_ass_to_node = zeros(1, N);
wolffd@0 81 for i=1:N
wolffd@0 82 %c = clq_containing_nodes(engine, family(bnet.dag, i));
wolffd@0 83 clqs_containing_family = find(all(B(:,family(bnet.dag, i)), 2)); % all selected columns must be 1
wolffd@0 84 c = clqs_containing_family(argmin(w(clqs_containing_family)));
wolffd@0 85 engine.clq_ass_to_node(i) = c;
wolffd@0 86 end
wolffd@0 87
wolffd@0 88 % Make the jtree rooted, so there is a fixed message passing order.
wolffd@0 89 if strong
wolffd@0 90 % the last clique is guaranteed to be a strong root
wolffd@0 91 % engine.root_clq = length(engine.cliques);
wolffd@0 92
wolffd@0 93 % --- 4/17/2010, by Wei Sun (George Mason University):
wolffd@0 94 % It has been proved that the last clique is not necessary to be the
wolffd@0 95 % strong root, instead, a clique called interface clique, that contains
wolffd@0 96 % all discrete parents and at least one continuous node from a connected
wolffd@0 97 % continuous component in a CLG, is guaranteed to be a strong root.
wolffd@0 98 engine.root_clq = findroot(bnet, engine.cliques) ;
wolffd@0 99 else
wolffd@0 100 % jtree_dbn_inf_engine requires the root to contain the interface.
wolffd@0 101 % This may conflict with the strong root requirement! *********** BUG *************
wolffd@0 102 engine.root_clq = clq_containing_nodes(engine, root);
wolffd@0 103 if engine.root_clq <= 0
wolffd@0 104 error(['no clique contains ' num2str(root)]);
wolffd@0 105 end
wolffd@0 106 end
wolffd@0 107
wolffd@0 108 [engine.jtree, engine.preorder, engine.postorder] = mk_rooted_tree(engine.jtree, engine.root_clq);
wolffd@0 109
wolffd@0 110 % collect
wolffd@0 111 engine.postorder_parents = cell(1,length(engine.postorder));
wolffd@0 112 for n=engine.postorder(:)'
wolffd@0 113 engine.postorder_parents{n} = parents(engine.jtree, n);
wolffd@0 114 end
wolffd@0 115 % distribute
wolffd@0 116 engine.preorder_children = cell(1,length(engine.preorder));
wolffd@0 117 for n=engine.preorder(:)'
wolffd@0 118 engine.preorder_children{n} = children(engine.jtree, n);
wolffd@0 119 end
wolffd@0 120
wolffd@0 121
wolffd@0 122
wolffd@0 123 %%%%%%%%
wolffd@0 124
wolffd@0 125 function engine = init_fields()
wolffd@0 126
wolffd@0 127 engine.jtree = [];
wolffd@0 128 engine.cliques = [];
wolffd@0 129 engine.separator = [];
wolffd@0 130 engine.cliques_bitv = [];
wolffd@0 131 engine.clique_weight = [];
wolffd@0 132 engine.clpot = [];
wolffd@0 133 engine.clq_ass_to_node = [];
wolffd@0 134 engine.root_clq = [];
wolffd@0 135 engine.preorder = [];
wolffd@0 136 engine.postorder = [];
wolffd@0 137 engine.preorder_children = [];
wolffd@0 138 engine.postorder_parents = [];
wolffd@0 139 engine.maximize = [];
wolffd@0 140 engine.evidence = [];
wolffd@0 141