Implements Fast Branch and Bound, i.e., B&B with full utilization of prediction mechanism. More...

#include <search_branch_and_bound_fast.hpp>

Inheritance diagram for FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >:

Public Types
typedef Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef parent::PCriterion	PCriterion
	shared pointer to the criterion the search optimizes
typedef parent::PSubset	PSubset
	shared pointer to a feature subset
typedef parent::PNode	PNode
	pointer to a search-tree Node, see Search_Branch_And_Bound
typedef parent::Node	Node
	search-tree node record (feature, value, type, valid), see Search_Branch_And_Bound
typedef parent::NodeType	NodeType
	UNKNOWN/RANDOM/PREDICTED/COMPUTED node-value provenance, see Search_Branch_And_Bound.
typedef parent::PEvaluatorEngine	PEvaluatorEngine
	shared pointer to the injected evaluation-strategy engine
Public Types inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class: the abstract Search interface (search(), progress reporting, result tracker)
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion under optimization
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef Candidate_Evaluator< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	EVALUATORENGINE
	the injected candidate-evaluation strategy type (sequential-inline or thread-pooled); process_leafs(), and descendants' pre_evaluate_availables()/post_process_tree_level() overrides, batch candidate evaluations through it
typedef std::shared_ptr< EVALUATORENGINE >	PEvaluatorEngine
	shared pointer to an EVALUATORENGINE, as accepted by the constructor and returned by get_engine()
Public Types inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion the search optimizes
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef std::shared_ptr< Result_Tracker< RETURNTYPE, SUBSET > >	PResultTracker
	shared pointer to the result tracker enabled via enable_result_tracking()
typedef Search_Observer< RETURNTYPE, SUBSET >	OBSERVER
	the observer interface type this search reports through (see Search_Observer)
typedef std::shared_ptr< OBSERVER >	PObserver
	shared pointer to an OBSERVER, as set via set_observer()

Public Member Functions
	Search_Branch_And_Bound_Fast (PEvaluatorEngine engine=PEvaluatorEngine())
	`engine` forwarded to Search_Branch_And_Bound; defaults to sequential in-line evaluation if not supplied
void	set_gamma (const RETURNTYPE gamma=1.0)
	forwards to the PREDICTOR's set_gamma() (in Branch_And_Bound_Predictor_Averaging the scaling factor applied to a prediction); the PREDICTOR type must provide that method
void	set_delta (const unsigned int delta=1)
	forwards to the PREDICTOR's set_delta() (in Branch_And_Bound_Predictor_Averaging the number of samples a feature needs before it is predicted at all); the PREDICTOR type must provide that method
virtual std::ostream &	print (std::ostream &os) const override
	writes the method's name, the predictor's own print() and, with a threaded engine, the number of worker threads
Public Member Functions inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
	Search_Branch_And_Bound (PEvaluatorEngine engine=PEvaluatorEngine())
	Constructs the search, optionally injecting a candidate-evaluation engine.
virtual bool	search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout) override
	returns the found subset of exactly target_d features + its criterion value; target_d must be nonzero (Branch & Bound searches one fixed cardinality, it does not optimize it)
Public Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	enable_result_tracking (PResultTracker tracker)
	assigns a result tracker to the search process, i.e., enables logging of all evaluated subsets for future reuse (re-evaluation, etc.)
void	disable_result_tracking ()
	detaches any result tracker (result_tracker_active() then returns false)
bool	result_tracker_active () const
	true if a result tracker was assigned via enable_result_tracking() and not since disabled
void	set_output_detail (OutputDetail detail)
	sets the amount of information that is logged to output stream throughout the course of search
OutputDetail	get_output_detail () const
	the currently configured output detail level
bool	output_normal () const
	true unless output detail is SILENT
bool	output_detailed () const
	true only at the DETAILED output level
void	set_observer (PObserver observer)
	redirects search progress reporting away from the default syncout text output to `observer`

Protected Member Functions
virtual void	initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit) override
	resets the predictor's per-feature statistics before each search - nothing is carried over from a previous one
virtual void	leaf_result (const DIMTYPE feature, const RETURNTYPE value) override
	feeds one more observed criterion-value drop to the predictor; fired per leaf, in candidate order, by the base class
virtual void	pre_evaluate_availables () override
	orders the available features for the next tree level: each feature's value is predicted where the predictor has enough samples for it, and computed by the criterion otherwise
virtual void	post_process_tree_level () override
	nothing to do: a PREDICTED node value is what makes FBB fast, and the values are turned into computed ones only where a cut decision needs them (see cut_possible())
virtual bool	cut_possible () override
	decides whether the sub-branch below the current node can be cut: a value above the bound rejects the cut right away (a predicted value is enough for that), while an actual cut is always decided on a computed value, which is evaluated here if missing
Protected Member Functions inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
PCriterion const &	get_criterion () const
	accessor for _criterion, for use by descendant B&B variants' hooks
PEvaluatorEngine const &	get_engine () const
	accessor for the injected evaluation strategy (sequential-inline or thread-pooled), for use by descendant B&B variants' hooks
RETURNTYPE	get_bound_value () const
	the current best (bound) criterion value; meaningful only once is_bound_valid()
bool	is_bound_valid () const
	true once a valid bound has been established, see _boundvalid
int	get_k () const
	the tree depth/level currently being processed (root is 0; the deepest stored level is n-d-1, and level n-d is the leaf level, evaluated but never stored). The return type is int, while the member k is DIMTYPE
DIMTYPE	get_n () const
	total number of features, see n
DIMTYPE	get_d () const
	target subset cardinality, see d
bool	getFirstNode (PNode &nod)
	begins forward iteration (ascending by value, from _tree[k].begin()) over the current level's not-yet-decided nodes into nod; returns false if the level is empty
bool	getNextNode (PNode &nod)
	advances the getFirstNode() iteration; returns false once the level's end is reached
bool	getFirstAvailable (PNode &avail)
	begins iteration over _available in feature-index order, skipping withdrawn (invalid) entries, into avail; returns false if none are available
bool	getNextAvailable (PNode &avail)
	advances the getFirstAvailable() iteration, again skipping invalid entries; returns false once exhausted
bool	getAvailable (DIMTYPE idx, PNode &avail)
	direct lookup of _available[idx] by feature index, regardless of its valid flag; returns false if idx is out of range
PSubset &	get_currentset ()
	mutable accessor for _currentset, for use by descendant B&B variants' hooks
Node &	get_parent_node ()
	the node one level up (_tree[k-1].back()) whose feature removal defines the branch currently being followed; valid at the leaf level too (k==n-d==_tree.size(), the unstored leaf level whose parent is the last stored one), which is where FBB/BBPP's leaf hooks call it
Node &	get_current_node ()
	the node at the current level k presently being visited (_tree[k].back()), i.e. about to be tested for cutting or descended into
void	setup_default_structures (const DIMTYPE d, const DIMTYPE n)
	Allocates and resets everything one search() run needs: the n-d stored tree levels (all emptied), the _available pool (all n features valid), _currentset (all features selected, i.e. the root), the _tempset scratch subset and the _boundset holder (bound marked invalid).
void	update_bound (const RETURNTYPE val, const PSubset &sub)
	Registers one fully-evaluated candidate subset of target cardinality d against the running bound. Updates _boundset/_boundvalue/_boundvalid whenever val improves on (or is the first) bound and, at NORMAL output or above, reports the improvement as a new solution; unconditionally feeds (val,sub) to the result tracker if one is active. Called from process_rightmost_path() and from process_leafs()'s per-leaf engine callback.
void	make_tree_level ()
	Builds the k-th tree level (_tree[k]), keeping exactly n-d-k+1 candidates in reserve for the levels still to come. Calls pre_evaluate_availables() to obtain each still-available feature's ordering value, sorts the best (levelsize = get_available_size()-(n-d-k+1)) of them ascending by value into _tree[k] (withdrawing the chosen features from _available via available_remove()), then calls post_process_tree_level() so a descendant can substitute exact values for any node whose ordering value was only an estimate.
void	process_rightmost_path ()
	Evaluates and registers the "rightmost" leaf reachable from the current branch by removing every feature still in _available at once. Copies _currentset into _tempset, deselects every remaining available feature, evaluates the criterion on the result and passes it to update_bound() - this seeds/tightens the bound as soon as each new tree level is built, before further descent, so later cuts can trigger sooner.
virtual void	process_leafs ()
	engine-routed leaf evaluation; descendants hook per-leaf work via leaf_result() instead of overriding this
Protected Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	report (std::ostream &os, const msgbuf &m) const
	delivers one pre-formatted progress message: to the observer if attached, otherwise as syncout text to os
void	report_solution (std::ostream &os, const RETURNTYPE value, const SUBSET &sub, const msgbuf &m) const
	like report(), for sites announcing a new (sub-)solution; fires on_solution instead

Protected Attributes
PREDICTOR	_predictor
	the prediction mechanism instance (PREDICTOR type parameter, e.g. Branch_And_Bound_Predictor_Averaging); learns per-feature criterion-value drops from computed leaf/cut evaluations and predicts them for unevaluated nodes, letting FBB skip most criterion evaluations while still guaranteeing the optimal result
Protected Attributes inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
std::ostream *	shared_os
	to enable sharing the same stream across the methods below
std::shared_ptr< StopWatch >	swatch
	stopwatch for the running search, (re)created at the start of search() and reported alongside progress/solution messages
Protected Attributes inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
PResultTracker	_tracker
	the assigned result tracker, or null (see enable_result_tracking()/result_tracker_active())
OutputDetail	_detail
	the output detail level set via set_output_detail(); read by output_normal()/output_detailed()
PObserver	_observer
	the attached progress observer, or null (see set_observer(), report(), report_solution())

Additional Inherited Members
Protected Types inherited from FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
enum	NodeType { UNKNOWN , RANDOM , PREDICTED , COMPUTED }
	Marks how a Node's value was obtained: UNKNOWN = not yet assigned; RANDOM = reserved but currently unused by any B&B variant in this file; PREDICTED = filled from a PREDICTOR estimate pending confirmation (FBB/BBPP node ordering); COMPUTED = an exact criterion value.
typedef Node *	PNode
	pointer to a Node, as used by the getFirst.../getNext... accessors below
typedef std::list< Node >	ListNode
	one tree level's not-yet-decided candidate nodes, kept sorted ascending by value; the main search loop visits/pops from the back (highest value = most promising) via get_current_node()
typedef std::vector< ListNode >	VectorListNode
	the search tree: one ListNode per level, indexed by tree depth k (see _tree)
typedef ListNode::iterator	ListNodeIter
	iterator into a single tree level's ListNode, as used by _nodeiter/getFirstNode()/getNextNode()
typedef std::vector< ListNode >::iterator	TreeLevelIter
	iterator over tree levels (used only to clear _tree in setup_default_structures())
typedef std::vector< Node >	VectorNode
	type of _available: one Node per original feature, indexed by feature id

Detailed Description

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class PREDICTOR>
class FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >

Implements Fast Branch and Bound, i.e., B&B with full utilization of prediction mechanism.

FBB is in most feature selection tasks the fastest of all Branch & Bound algorithms and as such should be the method of first choice whenever optimal feature selection is required and possible (see the warning below). Nevertheless, the FBB's prediction mechanism can theoretically fail and slow the search down (an analogy is perhaps the Quick Sort which is known as the best sorting algorithm for the general case but no guarantee is given about its actual speed). If you prefer more conservative option, try BBPP or the even slower but more predictable IBB or BBB.

Note: All Branch & Bound algorithms by definition yield the solution with the same maximum criterion value, therefore the main concern regarding particular Branch & Bound algorithm is only its search speed.

Warning: All Branch & Bound feature selection algorithms require the used CRITERION to be monotonic with respect to cardinality. More precisely, it must hold that removing a feature from a set MUST NOT increase criterion value. Otherwise there is no guarantee as of the optimality of obtained results with respect to the used criterion.

Note: Due to possibly high number of subsets to be tested expect excessive computational time.; Result tracking in case of Branch & Bound algorithms records only results of target cardinality.