Feature Selection Toolbox FST4
UTIA · Czech Academy of Sciences
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION > Class Template Reference

DEPRECATED shim: threaded Improved Branch and Bound (IBB) method. More...

#include <search_branch_and_bound_improved_threaded.hpp>

Inheritance diagram for FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >:
FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION > FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION > FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >

Public Types

typedef Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION > parent
 base class: the merged Improved B&B search this shim configures with a threaded engine
typedef parent::PEvaluatorEngine PEvaluatorEngine
Public Types inherited from FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
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 >
 shared pointer to the criterion the search optimizes
 shared pointer to a feature subset
 shared pointer to the result tracker enabled via enable_result_tracking()
 the observer interface type this search reports through (see Search_Observer)
 shared pointer to an OBSERVER, as set via set_observer()

Public Member Functions

 Search_Branch_And_Bound_Improved_Threaded (const unsigned int max_threads=2)
 Constructs a Search_Branch_And_Bound_Improved configured with a Candidate_Evaluator_Threaded engine of max_threads workers.
Public Member Functions inherited from FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
 Search_Branch_And_Bound_Improved (PEvaluatorEngine engine=PEvaluatorEngine())
 engine forwarded to Search_Branch_And_Bound; defaults to sequential in-line evaluation if not supplied
virtual std::ostream & print (std::ostream &os) const override
 writes a human-readable identification of the search and its configuration; base default writes nothing
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 >
 assigns a result tracker to the search process, i.e., enables logging of all evaluated subsets for future reuse (re-evaluation, etc.)
 detaches any result tracker (result_tracker_active() then returns false)
 true if a result tracker was assigned via enable_result_tracking() and not since disabled
 sets the amount of information that is logged to output stream throughout the course of search
 the currently configured output detail level
 true unless output detail is SILENT
 true only at the DETAILED output level
 redirects search progress reporting away from the default syncout text output to observer

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
Protected Member Functions inherited from FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
virtual void initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit) override
 IBB keeps no structures of its own beyond the base class's tree, so there is nothing to set up.
virtual void pre_evaluate_availables () override
 evaluates the criterion for every available feature (one batch through the evaluation engine) so that the next tree level can be ordered by true criterion values - this is what IBB buys its cuts with
virtual void post_process_tree_level () override
 nothing to do: every node of the new level already carries a COMPUTED value from pre_evaluate_availables()
virtual bool cut_possible () override
 reports whether the current node's (always computed) value fails to exceed the bound, in which case the whole sub-branch below it can be cut
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
virtual void leaf_result (const DIMTYPE feature, const RETURNTYPE value)
Protected Member Functions inherited from FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
 delivers one pre-formatted progress message: to the observer if attached, otherwise as syncout text to os
 like report(), for sites announcing a new (sub-)solution; fires on_solution instead
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 >
 the assigned result tracker, or null (see enable_result_tracking()/result_tracker_active())
 the output detail level set via set_output_detail(); read by output_normal()/output_detailed()
 the attached progress observer, or null (see set_observer(), report(), report_solution())

Detailed Description

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

DEPRECATED shim: threaded Improved Branch and Bound (IBB) method.

Deprecated
Deprecated since FST4 4.0; scheduled for removal in the next major release — construct the merged class with a Candidate_Evaluator_Threaded engine instead.

Kept for source compatibility with earlier FST4 sources, written when the threaded and the sequential variant were separate classes. This class is now nothing but a Search_Branch_And_Bound_Improved constructed with a Candidate_Evaluator_Threaded engine (which threads node ordering and leaf evaluation); prefer constructing that directly in new code.

Warning
Threading cannot accelerate IBB with any of the fast monotonous criteria implemented in FST4 - criterion evaluation is too cheap compared to the threading overhead. Use only with computationally expensive custom monotonous criteria.

Member Typedef Documentation

◆ PEvaluatorEngine

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>
typedef parent::PEvaluatorEngine FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::PEvaluatorEngine

the candidate-evaluation engine type, inherited from parent

Constructor & Destructor Documentation

◆ Search_Branch_And_Bound_Improved_Threaded()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>
FST::Search_Branch_And_Bound_Improved_Threaded< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::Search_Branch_And_Bound_Improved_Threaded ( const unsigned int max_threads = 2)
inlineexplicit

Constructs a Search_Branch_And_Bound_Improved configured with a Candidate_Evaluator_Threaded engine of max_threads workers.

Parameters
max_threadspool capacity for the threaded engine (must be greater than zero, asserted); see the class
Warning
above about threading overhead vs. cheap criteria
The documentation for this class was generated from the following file:
Generated by doxygen 1.17.0
Copyright © 2000–present ÚTIA, Institute of Information Theory and Automation of the Czech Academy of Sciences · Contacts · This site sets no cookies and uses no analytics.