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, 0 insertions, 365 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 deleted file mode 100644 index 3dd9aead0..000000000 --- a/ml/dlib/dlib/optimization/find_max_factor_graph_nmplp_abstract.h +++ /dev/null @@ -1,365 +0,0 @@ -// 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_ - - |