Run loopy belief to estimate overall marginal probabilities of all node states. More...

#include <mmn_lbp_solver.h>

Inheritance diagram for mmn_lbp_solver:

Public Types
enum	msg_update_t { eALL_PARALLEL, eRANDOM_SERIAL }
	Message update mode type (all in parallel, or randomised node order with immediate effect}. More...
Public Member Functions
	mmn_lbp_solver ()
	Default constructor.
	mmn_lbp_solver (unsigned num_nodes, const vcl_vector< mmn_arc > &arcs)
	Construct with arcs.
virtual void	set_arcs (unsigned num_nodes, const vcl_vector< mmn_arc > &arcs)
	Input the arcs that define the graph.
double	operator() (const vcl_vector< vnl_vector< double > > &node_cost, const vcl_vector< vnl_matrix< double > > &arc_cost, vcl_vector< unsigned > &x)
	Find values for each node with minimise the total cost.
virtual double	solve (const vcl_vector< vnl_vector< double > > &node_cost, const vcl_vector< vnl_matrix< double > > &pair_cost, vcl_vector< unsigned > &x)
	return the beliefs, i.e. the marginal probabilities of each node's states.
const vcl_vector< vnl_vector < double > > &	belief () const
unsigned	count () const
	final iteration count.
void	set_smooth_on_cycling (bool bOn)
	Set true if want to alpha smooth message updates when cycling detected.
void	set_max_cycle_detection_count_ (unsigned max_cycle_detection_count)
void	set_verbose (bool verbose)
void	set_msg_upd_mode (msg_update_t msg_upd_mode)
	Set message update mode (parallel or randomised serial}.
virtual bool	set_from_stream (vcl_istream &is)
	Initialise from a text stream.
short	version_no () const
	Version number for I/O.
virtual vcl_string	is_a () const
	Name of the class.
virtual mmn_solver *	clone () const
	Create a copy on the heap and return base class pointer.
virtual void	print_summary (vcl_ostream &os) const
	Print class to os.
virtual void	b_write (vsl_b_ostream &bfs) const
	Save class to binary file stream.
virtual void	b_read (vsl_b_istream &bfs)
	Load class from binary file stream.
Static Public Member Functions
static vcl_auto_ptr< mmn_solver >	create_from_stream (vcl_istream &is)
	Create a concrete region_model-derived object, from a text specification.
Private Types
typedef vcl_map< unsigned, vnl_vector< double > >	message_set_t
	in below the map is indexed by the neighbour's node id.
typedef vcl_map< unsigned, vnl_matrix< double > >	neigh_arc_cost_t
	Matrix referenced by [source node state ID][target node state ID].
Private Member Functions
bool	continue_propagation (vcl_vector< unsigned > &x)
	Check if we carry on.
void	update_messages_to_neighbours (unsigned inode, const vnl_vector< double > &node_cost)
	Update all messages from input node to its neighbours.
void	renormalise_log (vnl_vector< double > &logMessageVec)
	Renormalise messages (assume they represent log probabilities) so SUM(exp) over target states is 1.
void	init ()
	Reset iteration counters.
double	solution_cost (vcl_vector< unsigned > &x)
	Calculate final sum of node and arc values.
double	best_solution_cost_in_history (vcl_vector< unsigned > &x)
void	calculate_beliefs (vcl_vector< unsigned > &x)
	update beliefs and calculate changes therein.
Private Attributes
mmn_graph_rep1	graph_
	Store in graph form (so each node's neighbours are conveniently to hand).
vcl_vector< mmn_arc >	arcs_
	The arcs from which the graph was generated.
unsigned	nnodes_
	Total number of nodes.
vcl_vector< neigh_arc_cost_t >	arc_costs_
	Workspace for costs of each arc.
vcl_vector< message_set_t >	messages_
	All the messages at previous iteration (vector index is source node).
vcl_vector< message_set_t >	messages_upd_
	Update messages calculated during this iteration (vector index is source node).
vcl_vector< vnl_vector< double > >	node_costs_
	Node costs (outer vector is node ID, inner vnl_vector is by state value).
vcl_vector< vnl_vector< double > >	belief_
	belief prob for each state of each node.
vcl_deque< vcl_vector< unsigned > >	soln_history_
	previous N solutions (used to trap cycling).
vcl_deque< double >	max_delta_history_
	previous max_delta values(used to check still descending).
unsigned	count_
	Current iteration count.
double	max_delta_
	Max change in any message value over this iteration.
unsigned	max_iterations_
	max number of iterations allowed.
unsigned	min_simple_iterations_
	min number of iterations before checking for solution looping (cycling).
double	epsilon_
	Convergence criterion on max_delta_.
unsigned	nrevisits_
	count of number of times a solution in history is revisited.
bool	isCycling_
	cycle condition detected.
unsigned	cycle_detection_count_
	Number of times cycling has been detected.
double	alpha_
	message update smoothing constant (used if cycling detected).
bool	smooth_on_cycling_
	should message update be smoothed during cycling.
unsigned	max_cycle_detection_count_
double	zbest_on_cycle_detection_
	solution value when cycling first detected.
bool	verbose_
	verbose debug output.
msg_update_t	msg_upd_mode_
Static Private Attributes
static const unsigned	NHISTORY_ = 5
	Magic numbers for cycle detection.
static const unsigned	NCYCLE_DETECT_ = 7

Detailed Description

Run loopy belief to estimate overall marginal probabilities of all node states.

Then use converged LBP messages to also estimate overall most likely configuration

Can use this for non-tree graphs, but convergence to optimum is not absolutely guaranteed Should converge if there is at most one loop in the graph The input graph is converted to form mmn_graph_rep1 from the input arcs

Definition at line 25 of file mmn_lbp_solver.h.

Member Typedef Documentation

typedef vcl_map<unsigned,vnl_vector<double > > mmn_lbp_solver::message_set_t [private]

in below the map is indexed by the neighbour's node id.

Inner vector indexed by target node state ID.

Definition at line 34 of file mmn_lbp_solver.h.

typedef vcl_map<unsigned, vnl_matrix<double > > mmn_lbp_solver::neigh_arc_cost_t [private]

Matrix referenced by [source node state ID][target node state ID].

Map ID is target node ID

Definition at line 38 of file mmn_lbp_solver.h.

Member Enumeration Documentation

enum mmn_lbp_solver::msg_update_t

Message update mode type (all in parallel, or randomised node order with immediate effect}.

Enumerator:

eALL_PARALLEL
eRANDOM_SERIAL

Definition at line 29 of file mmn_lbp_solver.h.

Constructor & Destructor Documentation

mmn_lbp_solver::mmn_lbp_solver ( )

Default constructor.

Definition at line 20 of file mmn_lbp_solver.cxx.

mmn_lbp_solver::mmn_lbp_solver	(	unsigned	num_nodes,
		const vcl_vector< mmn_arc > &	arcs
	)

Construct with arcs.

Definition at line 30 of file mmn_lbp_solver.cxx.

Member Function Documentation

void mmn_lbp_solver::b_read ( vsl_b_istream & bfs ) [virtual]

Load class from binary file stream.

Implements mmn_solver.

Definition at line 565 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::b_write ( vsl_b_ostream & bfs ) const [virtual]

Save class to binary file stream.

Implements mmn_solver.

Definition at line 556 of file mmn_lbp_solver.cxx.

const vcl_vector<vnl_vector<double> >& mmn_lbp_solver::belief ( ) const [inline]

Definition at line 173 of file mmn_lbp_solver.h.

double mmn_lbp_solver::best_solution_cost_in_history ( vcl_vector< unsigned > & x ) [private]

Definition at line 299 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::calculate_beliefs ( vcl_vector< unsigned > & x ) [private]

update beliefs and calculate changes therein.

Definition at line 232 of file mmn_lbp_solver.cxx.

mmn_solver * mmn_lbp_solver::clone ( ) const [virtual]

Create a copy on the heap and return base class pointer.

Implements mmn_solver.

Definition at line 538 of file mmn_lbp_solver.cxx.

bool mmn_lbp_solver::continue_propagation ( vcl_vector< unsigned > & x ) [private]

Check if we carry on.

Definition at line 423 of file mmn_lbp_solver.cxx.

unsigned mmn_lbp_solver::count ( ) const [inline]

final iteration count.

Definition at line 176 of file mmn_lbp_solver.h.

vcl_auto_ptr< mmn_solver > mmn_solver::create_from_stream ( vcl_istream & is ) [static, inherited]

Create a concrete region_model-derived object, from a text specification.

Definition at line 76 of file mmn_solver.cxx.

void mmn_lbp_solver::init ( ) [private]

Reset iteration counters.

Definition at line 40 of file mmn_lbp_solver.cxx.

vcl_string mmn_lbp_solver::is_a ( ) const [virtual]

Name of the class.

Reimplemented from mmn_solver.

Definition at line 532 of file mmn_lbp_solver.cxx.

double mmn_lbp_solver::operator()	(	const vcl_vector< vnl_vector< double > > &	node_cost,
		const vcl_vector< vnl_matrix< double > > &	arc_cost,
		vcl_vector< unsigned > &	x
	)

Find values for each node with minimise the total cost.

Run the algorithm.

Parameters:

node_cost,:	node_cost[i][j] is cost of selecting value j for node i
pair_cost,:	pair_cost[a](i,j) is cost of selecting values (i,j) for nodes at end of arc a.
x,:	On exit, x[i] gives choice for node i NOTE: If arc a connects nodes v1,v2, the associated pair_cost is ordered with the node with the lowest index being the first parameter. Thus if v1 has value i1, v2 has value i2, then the cost of this choice is (v1<v2?pair_cost(i1,i2):pair_cost(i2,i1))

Returns the minimum cost. Note that internally we deal with a maximisation after negating the input costs, which are assumed to represent -log probabilities If the states of a node in node_cost are not well normalised as a probability the algorithm should still work in some sense but the meaning of the belief_ objects is not really then well-defined. As it is marginal "belief" that is maximised, inputting non-normalised data may not give quite the expected answer - there may be some biases, in effect implicit weightings to particular nodes

Negate costs to convert to log prob (i.e. internally we do maximisation).

Definition at line 88 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::print_summary ( vcl_ostream & os ) const [virtual]

Print class to os.

Implements mmn_solver.

Definition at line 547 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::renormalise_log ( vnl_vector< double > & logMessageVec ) [private]

Renormalise messages (assume they represent log probabilities) so SUM(exp) over target states is 1.

Definition at line 403 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::set_arcs	(	unsigned	num_nodes,
		const vcl_vector< mmn_arc > &	arcs
	)		`[virtual]`

Input the arcs that define the graph.

Pass in the arcs, which are then used to build the graph object.

Implements mmn_solver.

Definition at line 53 of file mmn_lbp_solver.cxx.

bool mmn_lbp_solver::set_from_stream ( vcl_istream & is ) [virtual]

Initialise from a text stream.

Initialise from a string stream.

Reimplemented from mmn_solver.

Definition at line 503 of file mmn_lbp_solver.cxx.

void mmn_lbp_solver::set_max_cycle_detection_count_ ( unsigned max_cycle_detection_count ) [inline]

Definition at line 182 of file mmn_lbp_solver.h.

void mmn_lbp_solver::set_msg_upd_mode ( msg_update_t msg_upd_mode ) [inline]

Set message update mode (parallel or randomised serial}.

Definition at line 187 of file mmn_lbp_solver.h.

void mmn_lbp_solver::set_smooth_on_cycling ( bool bOn ) [inline]

Set true if want to alpha smooth message updates when cycling detected.

This may break the cycling condition

Definition at line 180 of file mmn_lbp_solver.h.

void mmn_lbp_solver::set_verbose ( bool verbose ) [inline]

Definition at line 184 of file mmn_lbp_solver.h.

double mmn_lbp_solver::solution_cost ( vcl_vector< unsigned > & x ) [private]

Calculate final sum of node and arc values.

Calculate best (max log prob) of solution x.

Definition at line 269 of file mmn_lbp_solver.cxx.

double mmn_lbp_solver::solve	(	const vcl_vector< vnl_vector< double > > &	node_cost,
		const vcl_vector< vnl_matrix< double > > &	pair_cost,
		vcl_vector< unsigned > &	x
	)		`[virtual]`