FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR > Class Template Reference

Implements Branch and Bound with Partial Prediction (BBPP) method, i.e., with predicted node ordering. More...

#include <search_branch_and_bound_partial_prediction.hpp>

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

[legend]

Collaboration diagram for FST::Search_Branch_And_Bound_Partial_Prediction< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >:

[legend]

List of all members.

Public Types
typedef Search_Branch_And_Bound < RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
typedef parent::PCriterion	PCriterion
typedef parent::PSubset	PSubset
typedef parent::PNode	PNode
typedef parent::Node	Node
typedef parent::NodeType	NodeType
Public Member Functions
virtual std::ostream &	print (std::ostream &os) const
Protected Member Functions
virtual void	initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit)
	called before search - enables set-up of additional structures in descendants
virtual void	process_leafs ()
	can be overridden to implement prediction information learning, threading etc.
virtual void	pre_evaluate_availables ()
	assign values to each feature in availables - to be used for node ordering
virtual void	post_process_tree_level ()
	enables to substitute missing COMPUTED values in nodes just after level creation, if needed
virtual bool	cut_possible ()
	tests current node for the possibility to cut its sub-branch
Protected Attributes
PREDICTOR	_predictor

---

Detailed Description

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

Implements Branch and Bound with Partial Prediction (BBPP) method, i.e., with predicted node ordering.

BBPP is generally slower than FBB but faster than IBB. Its principle is identical to that of Improved Branch & Bound (IBB), but it replaces large amount of criterion evaluations needed for ordering nodes in tree levels by quickly predicted values. The optimality of final result is not jeopardized but considerable amount of time is saved. See FBB for a more radical but still optimality preserving use of value prediction.

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:

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.

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.

Examples:

demo42.cpp.

---

The documentation for this class was generated from the following file:

• search_branch_and_bound_partial_prediction.hpp