FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, max_threads > Class Template Reference
Implements threaded Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering.
More...
#include <search_branch_and_bound_improved_threaded.hpp>
List of all members.
Public Types |
typedef Search< RETURNTYPE,
DIMTYPE, SUBSET, CRITERION > | grandgrandparent |
typedef
Search_Branch_And_Bound
< RETURNTYPE, DIMTYPE, SUBSET,
CRITERION > | grandparent |
typedef grandparent::PCriterion | PCriterion |
typedef grandparent::PSubset | PSubset |
typedef grandparent::Node | Node |
typedef grandparent::NodeType | NodeType |
Public Member Functions |
virtual std::ostream & | print (std::ostream &os) const |
Protected Member Functions |
virtual void | process_leafs () |
| overridden to implement threading
|
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 | pre_evaluate_availables () |
| assign values to each feature in availables - to be used for node ordering
|
Protected Attributes |
Candidate_Evaluator_Threaded
< RETURNTYPE, DIMTYPE, SUBSET,
CRITERION, max_threads > | _evaluator |
Detailed Description
template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, unsigned int max_threads = 2>
class FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, max_threads >
Implements threaded Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering.
- 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.
-
Threading is implemented here wherever it was straightforward to do so. At various stages the algorithm thus switches beween sequential and threaded evaluation (e.g., node ordering is parallelized, evaluation of leafs at the end of paths is not). Taking better use of concurrency would require much more effort or conceptual changes in the algorithm itself. See specialized research resources for more information on this problem.
- Warning:
- This implementation unfortunately is not capable of accelerating feature selection process if any of the monotonous criteria implemented currently in the FST library are used; this is because the evaluation speed of any of the implemented monotonous criteria is too high when compared to threading overhead. Unless you need to run IBB with a computationally expensive monotonous criterion (if such is custom implemented), we strongly recommend to stay with the standard non-concurrent version of IBB.
- 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.
The documentation for this class was generated from the following file: