drwnMapInference.h

/*****************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnMapInference.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**
*****************************************************************************/

#pragma once

#include <vector>
#include <set>
#include <map>
#include <list>

#include "drwnBase.h"
#include "drwnVarUniverse.h"
#include "drwnVarAssignment.h"
#include "drwnFactorGraph.h"
#include "drwnTableFactorOps.h"

// drwnMAPInference class --------------------------------------------------

class drwnMAPInference {
 protected:
    const drwnFactorGraph& _graph; 

 public:
    drwnMAPInference(const drwnFactorGraph& graph);
    drwnMAPInference(const drwnMAPInference& inf);
    virtual ~drwnMAPInference();

    virtual void clear() { /* do nothing */ };
    virtual std::pair<double, double> inference(drwnFullAssignment& mapAssignment) = 0;
};

// drwnICMInference class --------------------------------------------------

class drwnICMInference : public drwnMAPInference {
 public:
    drwnICMInference(const drwnFactorGraph& graph);
    ~drwnICMInference();

    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);
};

// drwnMessagePassingMAPInference class -------------------------------------

class drwnMessagePassingMAPInference : public drwnMAPInference
{
 public:
    static unsigned MAX_ITERATIONS; 
    static double DAMPING_FACTOR;   

 protected:
    // forward and backward messages during each iteration
    std::vector<drwnTableFactor *> _forwardMessages;
    std::vector<drwnTableFactor *> _backwardMessages;
    std::vector<drwnTableFactor *> _oldForwardMessages;
    std::vector<drwnTableFactor *> _oldBackwardMessages;

    // computation tree: intermediate factors, and (atomic) factor operations
    std::vector<drwnTableFactor *> _intermediateFactors;
    std::vector<drwnFactorOperation *> _computations;

    // shared storage for intermediate factors
    std::vector<drwnTableFactorStorage *> _sharedStorage;

 public:
    drwnMessagePassingMAPInference(const drwnFactorGraph& graph);
    //drwnMessagePassingMAPInference(const drwnMessagePassingMAPInference& inf);
    virtual ~drwnMessagePassingMAPInference();

    void clear();
    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);

 protected:
    virtual void initializeMessages();
    virtual void buildComputationGraph() = 0;
    virtual void decodeBeliefs(drwnFullAssignment& mapAssignment);
};

// drwnMaxProductInference class --------------------------------------------

class drwnMaxProdInference : public drwnMessagePassingMAPInference {
 public:
    drwnMaxProdInference(const drwnFactorGraph& graph);
    ~drwnMaxProdInference();

 protected:
    void buildComputationGraph();
    void decodeBeliefs(drwnFullAssignment& mapAssignment);
};

// drwnAsyncMaxProductInference class ---------------------------------------

class drwnAsyncMaxProdInference : public drwnMessagePassingMAPInference {
 public:
    drwnAsyncMaxProdInference(const drwnFactorGraph& graph);
    ~drwnAsyncMaxProdInference();

 protected:
    void buildComputationGraph();
    void decodeBeliefs(drwnFullAssignment& mapAssignment);
};

// drwnJunctionTreeInference class ------------------------------------------

class drwnJunctionTreeInference : public drwnMAPInference {
 public:
    drwnJunctionTreeInference(const drwnFactorGraph& graph);
    ~drwnJunctionTreeInference();

    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);
};

// drwnGEMPLPInference class ------------------------------------------------

class drwnGEMPLPInference : public drwnMessagePassingMAPInference {
 protected:
    std::vector<drwnClique> _separators;      // list of all separators, S
    std::vector<drwnEdge> _edges;             // list of edges (c,s)
    std::vector<std::set<int> > _cliqueEdges; // mapping from c to _edges
    std::vector<std::set<int> > _separatorEdges; // mapping from s to _edges
    double _lastDualObjective;                // previous dual objecive value
    unsigned _maxIterations;                  // maximum number of iterations

 public:
    drwnGEMPLPInference(const drwnFactorGraph& graph);
    ~drwnGEMPLPInference();

    void clear();
    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);

 protected:
    void initializeMessages();
    void buildComputationGraph();
    void decodeBeliefs(drwnFullAssignment& mapAssignment);

    // helper functions for building clique-to-separator mapping
    int findSeparatorIndex(const drwnClique& cliqueA, const drwnClique& cliqueB);

    // computations for messages from clique \p cliqueId
    void addMessageUpdate(int cliqueId, const drwnClique& cliqueVars,
        const drwnTableFactor* psi = NULL);
};

// drwnSontag08Inference class ----------------------------------------------

class drwnSontag08Inference : public drwnGEMPLPInference {
 public:
    static unsigned WARMSTART_ITERATIONS; 
    static unsigned MAX_CLIQUES_TO_ADD;   

 protected:
    std::vector<drwnClique> _additionalCliques;

 public:
    drwnSontag08Inference(const drwnFactorGraph& graph);
    ~drwnSontag08Inference();

    void clear();
    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);

 protected:
    void buildComputationGraph();

    virtual void findCliqueCandidates(std::map<drwnClique, std::vector<int> >& cliqueCandidateSet);
};

// drwnDualDecompositionInference class ------------------------------------

class drwnDualDecompositionInference : public drwnMAPInference {
 public:
    static double INITIAL_ALPHA; 
    static bool USE_MIN_MARGINALS; 

 public:
    drwnDualDecompositionInference(const drwnFactorGraph& graph);
    ~drwnDualDecompositionInference();

    std::pair<double, double> inference(drwnFullAssignment& mapAssignment);
};