wolffd@0: function [mpe, ll] = calc_mpe(engine, evidence, break_ties)
wolffd@0: % CALC_MPE Computes the most probable explanation of the evidence
wolffd@0: % [mpe, ll] = calc_mpe_given_inf_engine(engine, evidence, break_ties)
wolffd@0: %
wolffd@0: % INPUT
wolffd@0: % engine must support max-propagation
wolffd@0: % evidence{i} is the observed value of node i, or [] if hidden
wolffd@0: % break_ties is optional. If 1, we will force ties to be broken consistently
wolffd@0: %  by calling enter_evidence N times.
wolffd@0: %
wolffd@0: % OUTPUT
wolffd@0: % mpe{i} is the most likely value of node i (cell array!)
wolffd@0: % ll is the log-likelihood of the globally best assignment
wolffd@0: %
wolffd@0: % This currently only works when all hidden nodes are discrete
wolffd@0: 
wolffd@0: if nargin < 3, break_ties = 0; end
wolffd@0: 
wolffd@0: 
wolffd@0: [engine, ll] = enter_evidence(engine, evidence, 'maximize', 1);
wolffd@0: 
wolffd@0: observed = ~isemptycell(evidence);
wolffd@0: 
wolffd@0: if 0 % fgraphs don't support bnet_from_engine
wolffd@0: onodes = find(observed);
wolffd@0: bnet = bnet_from_engine(engine);
wolffd@0: pot_type = determine_pot_type(bnet, onodes);
wolffd@0: assert(pot_type == 'd');
wolffd@0: end
wolffd@0: 
wolffd@0: scalar = 1;
wolffd@0: evidence = evidence(:); % hack to handle unrolled DBNs
wolffd@0: N = length(evidence);
wolffd@0: mpe = cell(1,N);
wolffd@0: for i=1:N
wolffd@0:   m = marginal_nodes(engine, i);
wolffd@0:   % observed nodes are all set to 1 inside the inference engine, so we must undo this
wolffd@0:   if observed(i)
wolffd@0:     mpe{i} = evidence{i};
wolffd@0:   else
wolffd@0:     mpe{i} = argmax(m.T);
wolffd@0:     % Bug fix by Ron Zohar, 8/15/01
wolffd@0:     % If there are ties, we must break them as follows (see Jensen96, p106)
wolffd@0:     if break_ties
wolffd@0:       evidence{i} = mpe{i};                             
wolffd@0:       [engine, ll] = enter_evidence(engine, evidence, 'maximize', 1);  
wolffd@0:     end
wolffd@0:   end
wolffd@0:   if length(mpe{i}) > 1, scalar = 0; end
wolffd@0: end
wolffd@0: 
wolffd@0: if nargout >= 2
wolffd@0:   bnet = bnet_from_engine(engine);
wolffd@0:   ll = log_lik_complete(bnet, mpe(:));
wolffd@0: end
wolffd@0: if 0 % scalar
wolffd@0:   mpe = cell2num(mpe);
wolffd@0: end