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

Implements voting ensemble selection step in sequential search type of methods to possibly improve robustness and stability of feature selection result. More...

#include <seq_step_ensemble.hpp>

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

Classes
class	SubsetCandidate
	Nested class to hold feature/subset candidate info in the course of the ensemble voting process. More...

Public Types
typedef Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the single criterion passed into evaluate_candidates() and used to (re-)score the winning subset – distinct from the ensemble member criteria
typedef std::shared_ptr< Criterion< RETURNTYPE, SUBSET > >	PAbstractCriterion
	shared pointer to one ensemble member, held via the abstract Criterion base so unrelated (filter/wrapper) criterion types can be mixed in one ensemble
typedef std::vector< PAbstractCriterion >	PAbstractCriteria
	the ordered collection of ensemble member criteria
typedef std::shared_ptr< PAbstractCriteria >	PEnsembleCriteria
	shared pointer to the ensemble member collection, as supplied to the constructor
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a feature subset
typedef Candidate_Evaluator< RETURNTYPE, DIMTYPE, SUBSET, Criterion< RETURNTYPE, SUBSET > >	EVALUATORENGINE
	typed on the abstract Criterion (the ensemble members' type)
typedef std::shared_ptr< EVALUATORENGINE >	PEvaluatorEngine
	shared pointer to the candidate-evaluation engine (see candidate_evaluator.hpp)
Public Types inherited from FST::Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion this step evaluates candidates against
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()

Public Member Functions
	Sequential_Step_Ensemble (const PEnsembleCriteria ensemble, PEvaluatorEngine engine=PEvaluatorEngine())
	Constructs the ensemble step over the given member criteria.
bool	evaluate_candidates (RETURNTYPE &result, const PSubset sub, const PCriterion crit, const DIMTYPE _generalization_level=1, std::ostream &os=std::cout) override
	chooses among subsets offered by sub->get*CandidateSubset()
virtual std::ostream &	print (std::ostream &os) const override
	Writes a human-readable identification of the step, incl. the engine's thread count (if threaded) and any attached result tracker.
Public Member Functions inherited from FST::Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >
void	enable_result_tracking (PResultTracker tracker)
	assigns a result tracker to this step, i.e., enables logging of all evaluated candidate 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

Protected Types
typedef std::shared_ptr< SubsetCandidate >	PSubsetCandidate
	shared pointer to a SubsetCandidate
typedef std::list< SubsetCandidate >	CANDIDATELIST
	one ensemble member's candidates, kept sorted best (highest _value) first by order_candidates()
typedef std::shared_ptr< CANDIDATELIST >	PCANDIDATELIST
	shared pointer to a CANDIDATELIST
typedef std::vector< PCANDIDATELIST >	CANDIDATELISTS
	one CANDIDATELIST per ensemble member, indexed the same as _ensemble
typedef std::map< DIMTYPE, PSubsetCandidate >	FINALVALUES
	maps each candidate feature to its tallied ensemble vote (see SubsetCandidate::_value); iteration order is thus ascending feature index

Protected Member Functions
bool	order_candidates (const PSubset sub)
	Builds, for each ensemble member, the ordered (best-first) list of candidate subsets in _lists, and seeds _final with one zero-valued entry per candidate feature.

Protected Attributes
PEvaluatorEngine	_engine
	candidate-evaluation engine driving the per-member candidate batches
PEnsembleCriteria	_ensemble
	the ensemble member criteria, as supplied to the constructor
CANDIDATELISTS	_lists
	per-member ordered candidate lists, rebuilt by order_candidates() on every evaluate_candidates() call
FINALVALUES	_final
	the per-feature vote tally built by evaluate_candidates() from _lists; the entry with the lowest (best) vote determines the step's chosen subset
CANDIDATELISTS::iterator	oiter
	iterates _lists, i.e. over ensemble members
CANDIDATELIST::iterator	iter
	iterates one member's ordered candidate list (an element of _lists)
FINALVALUES::iterator	fiter
	iterates _final, i.e. over candidate features and their tallied votes
Protected Attributes inherited from FST::Sequential_Step< 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()

Private Attributes
std::unique_ptr< SUBSET >	tmp_step_sub
	holds the winning candidate subset while evaluate_candidates() assembles it, before it is copied into the caller's sub (lazily allocated/grown to sub's feature count)
bool	track
	cached parent::result_tracker_active() for the duration of the current evaluate_candidates() call

Detailed Description

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

Implements voting ensemble selection step in sequential search type of methods to possibly improve robustness and stability of feature selection result.

Criteria ensembles may improve generalization and stability properties of the selected feature subset, see "P. Somol, J. Grim, and P. Pudil. Criteria Ensembles in Feature Selection. In Proc. MCS, LNCS 5519, pages 304–313. Springer, 2009." The idea is to reduce possible over-training, i.e., excessive result adjustment to particular criterion properties. By employing more different criteria the result is likely to be more robust in different contexts. Criteria ensembles as implemented here are based on voting about feature preferences. In sequential algorithm step, feature candidates are ordered separately according to each considered criterion. The various orderings are then joined (the position indices of a feature are summed over the criteria, which ranks the features the same way as averaging them would) to produce the final feature ordering. The best feature is then selected for addition to the current working subset. Note that this mechanism allows to use completely unrelated criteria, as the various criterion values are never combined - the only information that is combined is position index in ordered feature lists. This is advantageous as it enables combinations of filter and wrapper criteria (that yield values from different intervals) etc. Note, however, that the value obtained as result of ensemble evaluation is not usable for assessing the whole feature subset - it can be used only within the selection step to identify one feature (can be extended to feature c-tuple) for next inclusion/removal. For this reason it is also necessary to employ one single criterion to be used by selection algorithm for evaluating current subsets (and thus directing next search steps). This single criterion is used in the same way as in other FST4 Sequential_Step implementations, i.e. it must be passed in evaluate_candidates call. The criteria that form the ensemble are to be passed to Sequential_Step_Ensemble constructor.

Note

Single feature ordering implementation only. Support for generalized search (evaluation of candidate c-tuples instead of single features) may be implemented in future, but so far is not: evaluate_candidates() THROWS fst_error for any generalization level other than 1.

Like Sequential_Step_Straight this class serves both the sequential and the threaded execution model: the per-candidate evaluations of each ensemble member run through the injected Candidate_Evaluator, one batch per member criterion (default: sequential in-line evaluation; inject Candidate_Evaluator_Threaded for thread-pooled batches). The engine is typed on the abstract Criterion because that is how the ensemble members are held. Results are identical to sequential for any thread count: per-result callbacks fire in candidate order on the master, so the per-member ordered lists — and therefore the vote combination — come out the same whichever engine runs the batches (member criteria are deterministic and stateless across evaluate() calls, so evaluating member-by-member instead of candidate-by-candidate yields the same values).

One instance keeps a single set of iteration cursors and scratch lists, so a Sequential_Step_Ensemble object must not be used by two searches at the same time. Give each concurrent search its own instance.

Constructor & Destructor Documentation

Sequential_Step_Ensemble()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

FST::Sequential_Step_Ensemble< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::Sequential_Step_Ensemble ( const PEnsembleCriteria ensemble, PEvaluatorEngine engine = PEvaluatorEngine() )

inline

Constructs the ensemble step over the given member criteria.

Parameters

ensemble	the (non-null) collection of member criteria whose votes are combined each step; each member is expected to be already initialize()d before use, like crit passed to evaluate_candidates()
engine	the candidate-evaluation engine used to run each member's per-candidate batch; if null (the default), a Candidate_Evaluator_Sequential is constructed, i.e. sequential in-line evaluation

Member Function Documentation

evaluate_candidates()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

bool FST::Sequential_Step_Ensemble< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::evaluate_candidates ( RETURNTYPE & result, const PSubset sub, const PCriterion crit, const DIMTYPE _generalization_level = 1, std::ostream & os = std::cout )

inlineoverridevirtual

chooses among subsets offered by sub->get*CandidateSubset()

Implements FST::Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

order_candidates()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

bool FST::Sequential_Step_Ensemble< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::order_candidates ( const PSubset sub )

inlineprotected

Builds, for each ensemble member, the ordered (best-first) list of candidate subsets in _lists, and seeds _final with one zero-valued entry per candidate feature.

Two passes: first the master enumerates sub's candidate subsets once (single-feature add/remove, i.e. generalization level 1) to register every candidate's temporary feature in _final and count the candidates. Then, for each ensemble member in turn, the candidates are re-enumerated and evaluated as one batch through _engine; the per-result callback performs a descending-value sorted insertion into that member's list in _lists, so the list is ordered from the member's most to least preferred candidate regardless of evaluation/callback order (results fire on the master in candidate order for any thread count).

Parameters

sub	the subset whose candidate subsets are ordered

Returns

false if no candidate subsets exist, or if candidate enumeration or any member's evaluation fails

print()

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION>

virtual std::ostream & FST::Sequential_Step_Ensemble< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::print ( std::ostream & os ) const

inlineoverridevirtual

Writes a human-readable identification of the step, incl. the engine's thread count (if threaded) and any attached result tracker.

Reimplemented from FST::Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

---

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

• /Users/psms/dev/devtest1/_src_search/seq_step_ensemble.hpp