JointBackwardSampling.java

Go to the documentation of this file.

package edu.tum.cs.bayesnets.inference;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Vector;

import edu.ksu.cis.bnj.ver3.core.BeliefNode;
import edu.ksu.cis.bnj.ver3.core.CPF;
import edu.ksu.cis.bnj.ver3.core.Discrete;
import edu.tum.cs.bayesnets.core.BeliefNetworkEx;
import edu.tum.cs.util.Stopwatch;
import edu.tum.cs.util.StringTool;

public class JointBackwardSampling extends Sampler {

        Vector<BeliefNode> backwardSampledNodes;
        Vector<BeliefNode> forwardSampledNodes;
        HashSet<BeliefNode> outsideSamplingOrder;
        int[] evidenceDomainIndices;
        
        protected static class BackSamplingDistribution {
                public Vector<Double> distribution;
                public Vector<int[]> states;
                double Z;
                protected Sampler sampler;
                
                public BackSamplingDistribution(Sampler sampler) {
                        Z = 0.0;
                        distribution = new Vector<Double>();
                        states = new Vector<int[]>();
                        this.sampler = sampler;
                }
                
                public void addValue(double p, int[] state) {
                        distribution.add(p);
                        states.add(state);
                        Z += p;
                }
                
                public void applyWeight(WeightedSample s, int sampledValue) {
                        s.weight *= Z;
                }
                
                public void construct(BeliefNode node, int[] nodeDomainIndices) {
                        CPF cpf = node.getCPF();
                        BeliefNode[] domProd = cpf.getDomainProduct();
                        int[] addr = new int[domProd.length];
                        addr[0] = nodeDomainIndices[sampler.nodeIndices.get(node)];
                        construct(1, addr, cpf, nodeDomainIndices);
                }
                
                protected void construct(int i, int[] addr, CPF cpf, int[] nodeDomainIndices) {
                        if(i == addr.length) {
                                double p = cpf.getDouble(addr);
                                if(p != 0)
                                        addValue(p, addr.clone());
                                return;
                        }
                        BeliefNode[] domProd = cpf.getDomainProduct();
                        int nodeIdx = sampler.nodeIndices.get(domProd[i]);
                        if(nodeDomainIndices[nodeIdx] >= 0) {
                                addr[i] = nodeDomainIndices[nodeIdx];
                                construct(i+1, addr, cpf, nodeDomainIndices);
                        }
                        else {
                                Discrete dom = (Discrete)domProd[i].getDomain();                
                                for(int j = 0; j < dom.getOrder(); j++) {
                                        addr[i] = j;
                                        construct(i+1, addr, cpf, nodeDomainIndices);
                                }
                        }
                }
        }
        
        public JointBackwardSampling(BeliefNetworkEx bn) throws Exception {
                super(bn);
        }
        
        protected void getOrdering(int[] evidenceDomainIndices) {
                HashSet<BeliefNode> uninstantiatedNodes = new HashSet<BeliefNode>(Arrays.asList(nodes));
                backwardSampledNodes = new Vector<BeliefNode>();
                forwardSampledNodes = new Vector<BeliefNode>();
                outsideSamplingOrder = new HashSet<BeliefNode>();
                LinkedList<BeliefNode> backSamplingCandidates = new LinkedList<BeliefNode>();

                // check which nodes have evidence; ones that are are candidates for backward sampling and are instantiated
                for(int i = 0; i < evidenceDomainIndices.length; i++) {
                        if(evidenceDomainIndices[i] >= 0) { 
                                backSamplingCandidates.add(nodes[i]);
                                uninstantiatedNodes.remove(nodes[i]);
                        }
                }
                
                // check all backward sampling candidates
                while(!backSamplingCandidates.isEmpty()) {
                        BeliefNode node = backSamplingCandidates.removeFirst();
                        // check if there are any uninstantiated parents
                        BeliefNode[] domProd = node.getCPF().getDomainProduct();
                        boolean doBackSampling = false;
                        for(int j = 1; j < domProd.length; j++) {
                                BeliefNode parent = domProd[j];
                                // if there are uninstantiated parents, we do backward sampling on the child node
                                if(uninstantiatedNodes.remove(parent)) { 
                                        doBackSampling = true;
                                        backSamplingCandidates.add(parent);
                                }                                       
                        }
                        if(doBackSampling)
                                backwardSampledNodes.add(node);
                        // if there are no uninstantiated parents, the node is not backward sampled but is instantiated,
                        // i.e. it is not in the sampling order
                        else
                                outsideSamplingOrder.add(node);
                }
                
                // schedule all uninstantiated node for forward sampling in the topological order
                int[] topOrder = bn.getTopologicalOrder();
                for(int i : topOrder) {
                        if(uninstantiatedNodes.contains(nodes[i]))
                                forwardSampledNodes.add(nodes[i]);
                }
        }
        
        protected boolean sampleBackward(BeliefNode node, WeightedSample s) {           
                //System.out.println("backward sampling from " + node);
                // get the distribution from which to sample            
                BackSamplingDistribution d = getBackSamplingDistribution(node, s);
                // sample
                int idx = sample(d.distribution, generator);    
                if(idx == -1)
                        return false;
                int[] state = d.states.get(idx);
                // apply weight
                d.applyWeight(s, idx);
                if(s.weight == 0.0)
                        return false;
                // apply sampled parent setting
                BeliefNode[] domProd = node.getCPF().getDomainProduct();
                for(int i = 1; i < state.length; i++) {
                        int nodeIdx = this.nodeIndices.get(domProd[i]);
                        s.nodeDomainIndices[nodeIdx] = state[i];
                        //System.out.println("  sampled node " + domProd[i]);
                }
                return true;
        }
        
        protected BackSamplingDistribution getBackSamplingDistribution(BeliefNode node, WeightedSample s) {
                BackSamplingDistribution d = new BackSamplingDistribution(this);
                d.construct(node, s.nodeDomainIndices);
                return d;
        }
        
        protected void prepareInference(int[] evidenceDomainIndices) {
                this.evidenceDomainIndices = evidenceDomainIndices;
                getOrdering(evidenceDomainIndices);
                if(true) {
                        System.out.println("sampling backward: " + this.backwardSampledNodes);
                        System.out.println("sampling forward: " + this.forwardSampledNodes);
                        System.out.println("not in order: " + this.outsideSamplingOrder);
                }
        }
        
        @Override
        public SampledDistribution _infer() throws Exception {          
                Stopwatch sw = new Stopwatch();
                sw.start();
                
                this.prepareInference(evidenceDomainIndices);
                
                this.createDistribution();
                System.out.println("sampling...");
                WeightedSample s = new WeightedSample(this.bn, evidenceDomainIndices.clone(), 1.0, null, 0);
                for(int i = 1; i <= this.numSamples; i++) {     
                        if(i % infoInterval == 0)
                                System.out.println("  step " + i);
                        getSample(s);
                        this.addSample(s);
                }
                
                sw.stop();
                System.out.println(String.format("time taken: %.2fs (%.4fs per sample, %.1f trials/step)\n", sw.getElapsedTimeSecs(), sw.getElapsedTimeSecs()/numSamples, dist.getTrialsPerStep()));
                return this.dist;
        }
        
        public void getSample(WeightedSample s) {
                int MAX_TRIALS = 5000;  
                boolean debug = true;
loop1:  for(int t = 1; t <= MAX_TRIALS; t++) {
                        // init sample
                        s.nodeDomainIndices = evidenceDomainIndices.clone();
                        s.weight = 1.0;
                        // backward sampling
                        for(BeliefNode node : backwardSampledNodes) {
                                if(!sampleBackward(node, s)) {
                                        if(debug) System.out.println("!!! backward sampling failed at " + node);
                                        continue loop1;
                                }                               
                        }
                        //System.out.println("after backward: weight = " + s.weight);
                        // forward sampling
                        for(BeliefNode node : forwardSampledNodes) {
                                if(!sampleForward(node, s)) {
                                        if(debug) System.out.println("!!! forward sampling failed at " + node);
                                        continue loop1;
                                }
                        }
                        //System.out.println("after forward: weight = " + s.weight);
                        // nodes outside the sampling order: adjust weight
                        for(BeliefNode node : outsideSamplingOrder) {
                                s.weight *= this.getCPTProbability(node, s.nodeDomainIndices);
                                if(s.weight == 0.0) {
                                        // error diagnosis                                      
                                        if(debug) System.out.println("!!! weight became zero at unordered node " + node);
                                        continue loop1;
                                }
                        }
                        s.trials = t;
                        return;
                }
                throw new RuntimeException("Maximum number of trials exceeded.");
        }
        
        protected boolean sampleForward(BeliefNode node, WeightedSample s) {
                int idx = super.sampleForward(node, s.nodeDomainIndices);
                if(idx == -1)
                        return false;
                s.nodeDomainIndices[this.nodeIndices.get(node)] = idx;
                return true;
        }
}

---

srldb
Author(s): Dominik Jain, Stefan Waldherr, Moritz Tenorth
autogenerated on Fri Jan 11 09:58:29 2013