diff options
Diffstat (limited to 'ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h')
| -rw-r--r-- | ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h | 365 |
1 files changed, 365 insertions, 0 deletions
diff --git a/ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h b/ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h new file mode 100644 index 000000000..3dd9aead0 --- /dev/null +++ b/ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h @@ -0,0 +1,365 @@ +// Copyright (C) 2011 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_FIND_MAX_FACTOR_GRAPH_nMPLP_ABSTRACT_Hh_ +#ifdef DLIB_FIND_MAX_FACTOR_GRAPH_nMPLP_ABSTRACT_Hh_ + +#include <vector> + + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + class map_problem + { + /*! + WHAT THIS OBJECT REPRESENTS + This object represents a factor graph or graphical model. In + particular, this object defines the interface a MAP problem on + a factor graph must implement if it is to be solved using the + find_max_factor_graph_nmplp() routine defined at the bottom of this file. + + Note that there is no dlib::map_problem object. What you are + looking at here is simply the interface definition for a map problem. + You must implement your own version of this object for the problem + you wish to solve and then pass it to the find_max_factor_graph_nmplp() routine. + + + Note also that a factor graph should not have any nodes which are + neighbors with themselves. Additionally, the graph is undirected. This + mean that if A is a neighbor of B then B must be a neighbor of A for + the map problem to be valid. + + + Finally, note that the "neighbor" relationship between nodes means the + following: Two nodes are neighbors if and only if there is a potential + function (implemented by the factor_value() method) which operates on + the nodes. + !*/ + + public: + + class node_iterator + { + /*! + WHAT THIS OBJECT REPRESENTS + This is a simple forward iterator for iterating over + the nodes/variables in this factor graph. + + Note that you can't dereference the iterator and + obtain a value. That is, the iterator is opaque to + the user. It is used only as an argument to the other + methods defined in this interface. + !*/ + + public: + node_iterator( + ); + /*! + ensures + - constructs an iterator in an undefined state + !*/ + + node_iterator( + const node_iterator& item + ); + /*! + ensures + - #*this is a copy of item + !*/ + + node_iterator& operator= ( + const node_iterator& item + ); + /*! + ensures + - #*this is a copy of item + - returns #*this + !*/ + + bool operator== ( + const node_iterator& item + ) const; + /*! + ensures + - returns true if *this and item both reference + the same node in the factor graph and false + otherwise. + !*/ + + bool operator!= ( + const node_iterator& item + ) const; + /*! + ensures + - returns false if *this and item both reference + the same node in the factor graph and true + otherwise. + !*/ + + node_iterator& operator++( + ); + /*! + ensures + - advances *this to the next node in the factor graph. + - returns a reference to the updated *this + (i.e. this is the ++object form of the increment operator) + !*/ + }; + + class neighbor_iterator + { + /*! + WHAT THIS OBJECT REPRESENTS + This is a simple forward iterator for iterating over + the nodes/variables in this factor graph. This version + of the iterator is used for iterating over the neighbors + of another node in the graph. + !*/ + + public: + neighbor_iterator( + ); + /*! + ensures + - constructs an iterator in an undefined state + !*/ + + neighbor_iterator( + const neighbor_iterator& item + ); + /*! + ensures + - #*this is a copy of item + !*/ + + neighbor_iterator& operator= ( + const neighbor_iterator& item + ); + /*! + ensures + - #*this is a copy of item + - returns #*this + !*/ + + bool operator== ( + const neighbor_iterator& item + ) const; + /*! + ensures + - returns true if *this and item both reference + the same node in the factor graph and false + otherwise. + !*/ + + bool operator!= ( + const neighbor_iterator& item + ) const; + /*! + ensures + - returns false if *this and item both reference + the same node in the factor graph and true + otherwise. + !*/ + + neighbor_iterator& operator++( + ); + /*! + ensures + - advances *this to the next node in the factor graph. + - returns a reference to the updated *this + (i.e. this is the ++object form of the increment operator) + !*/ + }; + + unsigned long number_of_nodes ( + ) const; + /*! + ensures + - returns the number of nodes in the factor graph. Or in other words, + returns the number of variables in the MAP problem. + !*/ + + node_iterator begin( + ) const; + /*! + ensures + - returns an iterator to the first node in the graph. If no such + node exists then returns end(). + !*/ + + node_iterator end( + ) const; + /*! + ensures + - returns an iterator to one past the last node in the graph. + !*/ + + neighbor_iterator begin( + const node_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [begin(), end())) + ensures + - returns an iterator to the first neighboring node of the node + referenced by it. If no such node exists then returns end(it). + !*/ + + neighbor_iterator begin( + const neighbor_iterator& it + ) const; + /*! + requires + - it == a valid iterator. (i.e. it must be in the range + [begin(i), end(i)) where i is some valid iterator. ) + ensures + - returns an iterator to the first neighboring node of the node + referenced by it. If no such node exists then returns end(it). + !*/ + + neighbor_iterator end( + const node_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [begin(), end())) + ensures + - returns an iterator to one past the last neighboring node of the node + referenced by it. + !*/ + + neighbor_iterator end( + const neighbor_iterator& it + ) const; + /*! + requires + - it == a valid iterator. (i.e. it must be in the range + [begin(i), end(i)) where i is some valid iterator. ) + ensures + - returns an iterator to one past the last neighboring node of the node + referenced by it. + !*/ + + unsigned long node_id ( + const node_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [begin(), end())) + ensures + - returns a number ID such that: + - 0 <= ID < number_of_nodes() + - ID == a number which uniquely identifies the node pointed to by it. + !*/ + + unsigned long node_id ( + const neighbor_iterator& it + ) const; + /*! + requires + - it == a valid iterator. (i.e. it must be in the range + [begin(i), end(i)) where i is some valid iterator. ) + ensures + - returns a number ID such that: + - 0 <= ID < number_of_nodes() + - ID == a number which uniquely identifies the node pointed to by it. + !*/ + + unsigned long num_states ( + const node_iterator& it + ) const; + /*! + requires + - it == a valid iterator (i.e. it must be in the range [begin(), end())) + ensures + - returns the number of states attainable by the node/variable referenced by it. + !*/ + + unsigned long num_states ( + const neighbor_iterator& it + ) const; + /*! + requires + - it == a valid iterator. (i.e. it must be in the range + [begin(i), end(i)) where i is some valid iterator. ) + ensures + - returns the number of states attainable by the node/variable referenced by it. + !*/ + + // The next four functions all have the same contract. + double factor_value (const node_iterator& it1, const node_iterator& it2, unsigned long s1, unsigned long s2) const; + double factor_value (const neighbor_iterator& it1, const node_iterator& it2, unsigned long s1, unsigned long s2) const; + double factor_value (const node_iterator& it1, const neighbor_iterator& it2, unsigned long s1, unsigned long s2) const; + double factor_value (const neighbor_iterator& it1, const neighbor_iterator& it2, unsigned long s1, unsigned long s2) const; + /*! + requires + - it1 == a valid iterator + - it2 == a valid iterator + - 0 <= s1 < num_states(it1) + - 0 <= s2 < num_states(it2) + - it1 and it2 reference nodes which are neighbors in the factor graph + ensures + - returns the value of the factor/potential function for the given pair of + nodes, defined by it1 and it2, for the case where they take on the values + s1 and s2 respectively. + !*/ + + }; + +// ---------------------------------------------------------------------------------------- + + template < + typename map_problem + > + void find_max_factor_graph_nmplp ( + const map_problem& prob, + std::vector<unsigned long>& map_assignment, + unsigned long max_iter, + double eps + ); + /*! + requires + - for all valid i: prob.num_states(i) >= 2 + - map_problem == an object with an interface compatible with the map_problem + object defined at the top of this file. + - eps > 0 + ensures + - This function is a tool for approximately solving the given MAP problem in a graphical + model or factor graph with pairwise potential functions. That is, it attempts + to solve a certain kind of optimization problem which can be defined as follows: + maximize: f(X) + where X is a set of integer valued variables and f(X) can be written as the + sum of functions which each involve only two variables from X. In reference + to the prob object, the nodes in prob represent the variables in X and the + functions which are summed are represented by prob.factor_value(). + - #map_assignment == the result of the optimization. + - #map_assignment.size() == prob.number_of_nodes() + - for all valid i: + - #map_assignment[prob.node_id(i)] < prob.num_states(i) + - #map_assignment[prob.node_id(i)] == The approximate MAP assignment for node/variable i. + - eps controls the stopping condition, smaller values of eps lead to more accurate + solutions of the relaxed linear program but may take more iterations. Note that + the algorithm will never execute more than max_iter iterations regardless of + the setting of eps. + - If the graph is tree-structured then this routine always gives the exact solution + to the MAP problem. However, for graphs with cycles, the solution may be approximate. + + + - This function is an implementation of the NMPLP algorithm introduced in the + following papers: + Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations (2008) + by Amir Globerson and Tommi Jaakkola + + Introduction to dual decomposition for inference (2011) + by David Sontag, Amir Globerson, and Tommi Jaakkola + !*/ + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_FIND_MAX_FACTOR_GRAPH_nMPLP_ABSTRACT_Hh_ + + |