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

Implements the budgeted (sampled) sequential selection step: forward steps evaluate only a sampled batch of candidates, backward steps sweep in full unless a backward budget is set. More...

#include <seq_step_sampled.hpp>

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

Public Types
enum	SamplerMode { SAMPLER_SOFTMAX , SAMPLER_UNIFORM , SAMPLER_TOPK }
	Proposal-sampling policy for the forward/backward candidate batch (see the class docs above for the exact per-mode draw procedure). SAMPLER_SOFTMAX (default) draws without replacement with probability softmax(+-score/tau) plus an exploration floor; SAMPLER_UNIFORM draws uniformly without replacement from the whole pool (the Mirzasoleiman et al. 2015 stochastic-greedy baseline); SAMPLER_TOPK is a hard score cutoff with no exploration at all, which tends to keep re-proposing the same few features.
typedef Sequential_Step< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	parent
	base class alias
typedef std::shared_ptr< CRITERION >	PCriterion
	shared pointer to the criterion evaluated by this step
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to a candidate/working feature subset
typedef std::shared_ptr< WEIGHTER >	PWeighter
	shared pointer to the statistics engine (Result_Weighter_Sampled)
typedef Candidate_Evaluator< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >	EVALUATORENGINE
	candidate-evaluation engine type (sequential in-line or thread-pooled)
typedef std::shared_ptr< EVALUATORENGINE >	PEvaluatorEngine
	shared pointer to the evaluation engine
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_Sampled (PWeighter stats, const DIMTYPE cap=100, const double explore=0.2, const double tau=0.0, const SamplerMode sampler=SAMPLER_SOFTMAX, PEvaluatorEngine engine=PEvaluatorEngine())
	Constructs the step with its statistics engine, per-step evaluation budget, proposal sampler and (optional) evaluation engine.
void	set_cap_frac (const double frac)
	Switches the forward budget to a constant-PERCENTAGE schedule: when frac >0 the forward step cap becomes ceil(frac*pool) instead of the constant count cap, so per-step cost scales with the pool again — the very property the constant-count default removes. frac is clamped to [0,1]; 0 (default) disables the schedule. Applies to FORWARD steps only.
double	get_cap_frac () const
	current constant-percentage schedule fraction (0 = disabled, see set_cap_frac())
void	set_cap_backward (const DIMTYPE cap)
	Sets the backward-step budget y_b: 0 (default) = full backward sweeps, which keeps the floating correction exact; >0 = propose exactly y_b removal candidates, sampled ~ softmax(-score/tau) with the exploration floor taken over count_isnot.
DIMTYPE	get_cap_backward () const
	current backward-step budget y_b (0 = full sweeps, see set_cap_backward())
bool	evaluate_candidates (RETURNTYPE &result, const PSubset sub, const PCriterion crit, const DIMTYPE _generalization_level=1, std::ostream &os=std::cout) override
	Performs one selection step on sub: routes to the budgeted forward path, the budgeted backward path or the classic full sweep, depending on sub's current direction mode, the pool size and the configured budgets (see the class docs).
PWeighter	get_stats ()
	shared statistics engine (fst4 feeds warm-up probes through it)
virtual std::ostream &	print (std::ostream &os) const override
	Writes a human-readable identification of the step configuration (cap or the percentage schedule, cap_backward if set, explore, tau or "auto", sampler, the statistics engine's mode and horizon, and the thread count when the injected engine is threaded), followed by the active result tracker if one is attached.
virtual bool	print_summary (std::ostream &os=std::cout)
	Prints the statistics engine's diagnostic top-scored-feature listing (Result_Weighter_Sampled::print_stats()) to os.
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 Attributes
PWeighter	_stats
	shared online per-feature statistics engine driving proposal sampling (also reachable via get_stats(), e.g. for fst4's warm-up probes)
PEvaluatorEngine	_engine
	injected candidate-evaluation engine: sequential in-line (default) or thread-pooled
DIMTYPE	_cap
	forward per-step candidate budget (constant-count schedule; see set_cap_frac() for the percentage alternative)
DIMTYPE	_cap_backward =0
	>0 = budgeted backward steps; 0 = full backward sweeps (exact floating correction)
double	_cap_frac =0.0
	>0 = constant-percentage schedule overrides _cap (see set_cap_frac); forward only
double	_explore
	exploration-floor fraction of each proposal batch, clamped to [0,1] at construction (see class docs)
double	_tau
	softmax temperature as given at construction; <=0 triggers the per-step robust auto-scale (class docs)
SamplerMode	_sampler
	active proposal policy, see SamplerMode
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 Member Functions
bool	full_sweep (RETURNTYPE &result, const PSubset sub, const PCriterion crit, const DIMTYPE g, const DIMTYPE pool, std::ostream &os)
	Full candidate sweep (the Sequential_Step_Straight fallback): evaluates every candidate subset returned by sub's getFirstCandidateSubset()/getNextCandidateSubset() through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and copies the best-found candidate into sub. Used for small pools (pool<=cap), cap==0, generalized steps (g>1) and frozen-mode subsets.
bool	sampled_forward (RETURNTYPE &result, const PSubset sub, const PCriterion crit, const DIMTYPE pool, const DIMTYPE cap, std::ostream &os)
	Budgeted forward step: proposes exactly cap candidate features (see the class docs above for the sampler-mode and exploration-floor mechanics), evaluates the proposed batch through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and selects the best-scoring proposed feature into sub. All fst_rand() draws happen before any candidate is handed to the engine, so proposal sampling is unaffected by threaded evaluation (see the threading paragraph in the class docs).
bool	sampled_backward (RETURNTYPE &result, const PSubset sub, const PCriterion crit, const DIMTYPE pool, const DIMTYPE cap, std::ostream &os)
	Budgeted backward step, the removal mirror of sampled_forward (kept as a separate body on purpose — see the comment above its definition): proposes exactly cap removal candidates favoring low-scored members, evaluates them through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and removes the best-scoring proposed member from sub.
void	note_step (const bool forward, const DIMTYPE order, const DIMTYPE cnt, const DIMTYPE pool, std::ostream &os)
	Folds one completed step's outcome into the order-instrumentation running averages (order_forward/order_backward, count_forward/count_backward) and, at NORMAL verbosity, prints the "F order"/"B order" diagnostic line to os (see the class docs' Diagnostics paragraph).
double	frand ()
	uniform [0,1); fst_rand()-based per the --seed contract

Private Attributes
PSubset	tmp_cand
	sampled path: reusable candidate = S + {f} (lazy)
DIMTYPE	count_forward
	number of completed forward steps folded into order_forward so far (cumulative, never reset)
DIMTYPE	count_backward
	number of completed backward steps folded into order_backward so far (cumulative, never reset)
RETURNTYPE	order_forward
	running average of forward-step winner order, normalized to (0,1] (see note_step(); cumulative, never reset)
RETURNTYPE	order_backward
	running average of backward-step winner order, normalized to (0,1] (see note_step(); cumulative, never reset)
unsigned long long	all_evals
	criterion evaluations performed by this step object so far (cumulative, never reset; 64-bit because a long is 32-bit on LLP64)

Detailed Description

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

Implements the budgeted (sampled) sequential selection step: forward steps evaluate only a sampled batch of candidates, backward steps sweep in full unless a backward budget is set.

The point of the step is that the number of criterion evaluations it spends is bounded by a user-set candidate budget INDEPENDENT of the feature-space size n, which keeps sequential selection tractable where the classic full sweep (n-d evaluations per step) is not. Candidates are not drawn blindly: an online per-feature statistics engine (Result_Weighter_Sampled), fed by every criterion evaluation the search performs, scores each feature and the proposal sampler concentrates the budget on the promising ones while an exploration floor keeps the rest reachable. For the method and its evaluation see arXiv:2608.01502.

The class is a drop-in replacement for Sequential_Step_Straight in any search built on Sequential_Step (SFS/SFFS/SFRS, Oscillating and Dynamic Oscillating Search); the fst4 command-line tool selects it with --evaluator sampled.

Forward steps with a free-feature pool larger than the cap propose exactly cap candidates per step instead of sweeping the whole pool:

• a fraction explore of the batch is drawn uniformly (without replacement) from the least-evaluated features (exploration floor — solves cold start and keeps low-scoring features discoverable),
• the remainder is drawn without replacement with probabilities softmax(score/tau) over the statistics engine's current per-feature scores; tau<=0 selects a robust automatic scale (IQR of the current free-feature scores / 1.349, floored) so the policy is self-tuning. SAMPLER_UNIFORM (the stochastic-greedy baseline of Mirzasoleiman et al. 2015) and SAMPLER_TOPK (a hard top-cap cutoff, prone to collapsing onto the same few features) are the alternative proposal policies.

Backward steps are budgeted SYMMETRICALLY: when set_cap_backward(y_b>0) is active and the subset is larger than y_b, exactly y_b removal candidates are proposed — the exploration-floor fraction uniformly from the members whose ABSENCE is least observed (count_isnot), the remainder drawn without replacement ~ softmax(-score/tau) so LOW-scoring members are removed first. This matters because uncapped backward sweeps otherwise dominate the budget of a floating search at large d. The default y_b==0 lets backward steps sweep in full, which keeps the SFFS floating correction exact (the y_b -> |S| limit). CAUTION: weighting removal candidates by (1-w/sum(w)) over raw weights compresses to near-uniform and carries no signal; the softmax over z-contrast scores with the robust tau is the scale-aware alternative. Judge a configuration by the B-order diagnostic described below — avgorder must fall below ~0.5 for the proposals to carry signal at all.

Small pools (pool <= cap), cap==0, generalized steps (g>1), and frozen-mode subsets fall back to the classic full sweep over sub->get*CandidateSubset() — identical in semantics to Sequential_Step_Straight. EVERY evaluated candidate (all paths) is fed to the statistics engine; the batch is flushed at the end of each step (batches never mix cardinalities — see Result_Weighter_Sampled's caller contract).

All randomness is drawn via FST::fst_rand(), inheriting the process-wide seed contract (fst4 --seed; unseeded == --seed 1). Reruns with the same seed reproduce the same result.

The candidate-evaluation engine (Candidate_Evaluator) is injected through the constructor; the default is sequential in-line evaluation. With Candidate_Evaluator_Threaded injected, each step's proposal batch is evaluated in the thread pool while the proposal sampling itself stays on the caller's thread: every fst_rand() draw of a step happens BEFORE the first evaluation, criterion evaluate() never draws (fst_rand state is thread_local, so workers could not perturb the master stream even if it did), and the engine replays results to the statistics engine/tracker/ best-so-far in add-order (= proposal order) on the caller's thread when the batch completes. A threaded run therefore yields exactly the same result as a sequential one at the same seed, for any thread count (the weighter is never accessed concurrently and its batch semantics are unchanged).

Diagnostics (printed at NORMAL verbosity): "F order"/"B order" lines report at which position in the proposal order the step winner appeared, normalized to (0,1] — the direct measure of whether the online statistics front-load winners. A value near 1/cnt means the sampler proposes the winner first; values around 0.5 mean the proposals are no better than a random order of the pool.

Constructor & Destructor Documentation

Sequential_Step_Sampled()

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

FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::Sequential_Step_Sampled ( PWeighter stats, const DIMTYPE cap = 100, const double explore = 0.2, const double tau = 0.0, const SamplerMode sampler = SAMPLER_SOFTMAX, PEvaluatorEngine engine = PEvaluatorEngine() )

inline

Constructs the step with its statistics engine, per-step evaluation budget, proposal sampler and (optional) evaluation engine.

Parameters

stats	shared statistics engine (Result_Weighter_Sampled); a default-constructed instance is created when null
cap	forward per-step candidate budget (set_cap_frac() overrides it with a percentage-of-pool schedule); a pool not larger than cap falls back to a full sweep
explore	fraction of each proposal batch drawn from the exploration floor (least-evaluated free features, or least-observed-absent members on backward steps), clamped to [0,1]
tau	softmax temperature; <=0 selects the robust self-tuning scale (IQR/1.349 of the current free-feature/member scores) fresh on every step
sampler	proposal policy, see SamplerMode
engine	candidate-evaluation engine (Candidate_Evaluator); sequential in-line evaluation is used when null

Member Function Documentation

evaluate_candidates()

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

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

inlineoverridevirtual

Performs one selection step on sub: routes to the budgeted forward path, the budgeted backward path or the classic full sweep, depending on sub's current direction mode, the pool size and the configured budgets (see the class docs).

Parameters

result	set to the criterion value of the winning candidate on success
sub	the working subset; the winning feature is added (forward mode) or removed (backward mode) in place. Its direction (Subset::set_forward_mode()) selects the path.
crit	the criterion each candidate is evaluated against; it must already be initialize()d
_generalization_level	candidate subsets differ from sub by this many features; values >1 always take the full-sweep path
os	progress and diagnostic messages are written here

Returns

false when there is nothing to do (empty pool), when a candidate could not be evaluated, or when the statistics engine rejected an evaluation; true otherwise

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

full_sweep()

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

bool FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::full_sweep ( RETURNTYPE & result, const PSubset sub, const PCriterion crit, const DIMTYPE g, const DIMTYPE pool, std::ostream & os )

inlineprivate

Full candidate sweep (the Sequential_Step_Straight fallback): evaluates every candidate subset returned by sub's getFirstCandidateSubset()/getNextCandidateSubset() through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and copies the best-found candidate into sub. Used for small pools (pool<=cap), cap==0, generalized steps (g>1) and frozen-mode subsets.

Parameters

result	set to the best-found candidate's criterion value on success
sub	the working subset; updated in place to the best-found candidate
crit	the criterion each candidate is evaluated against
g	generalization level (candidate subsets differ from sub by g features)
pool	number of free (forward) or selected (backward) features available to propose from
os	progress/diagnostic messages are written here at NORMAL output detail or above

note_step()

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

void FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::note_step ( const bool forward, const DIMTYPE order, const DIMTYPE cnt, const DIMTYPE pool, std::ostream & os )

inlineprivate

Folds one completed step's outcome into the order-instrumentation running averages (order_forward/order_backward, count_forward/count_backward) and, at NORMAL verbosity, prints the "F order"/"B order" diagnostic line to os (see the class docs' Diagnostics paragraph).

Parameters

forward	true for a forward step, false for backward
order	1-based position of the step winner within the proposal (sampled path) or sweep (full path) order
cnt	number of candidates actually evaluated this step
pool	candidate pool size this step drew from
os	the diagnostic line, when printed, is written here

print()

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

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

inlineoverridevirtual

Writes a human-readable identification of the step configuration (cap or the percentage schedule, cap_backward if set, explore, tau or "auto", sampler, the statistics engine's mode and horizon, and the thread count when the injected engine is threaded), followed by the active result tracker if one is attached.

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

print_summary()

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

virtual bool FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::print_summary ( std::ostream & os = std::cout )

inlinevirtual

Prints the statistics engine's diagnostic top-scored-feature listing (Result_Weighter_Sampled::print_stats()) to os.

Returns

true (unconditionally; the statistics engine is asserted non-null)

sampled_backward()

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

bool FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::sampled_backward ( RETURNTYPE & result, const PSubset sub, const PCriterion crit, const DIMTYPE pool, const DIMTYPE cap, std::ostream & os )

inlineprivate

Budgeted backward step, the removal mirror of sampled_forward (kept as a separate body on purpose — see the comment above its definition): proposes exactly cap removal candidates favoring low-scored members, evaluates them through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and removes the best-scoring proposed member from sub.

Parameters

result	set to the winning candidate's criterion value on success
sub	the working subset; the winning feature is removed in place
crit	the criterion each proposed candidate is evaluated against
pool	number of currently selected features (subset size)
cap	number of removal candidates to propose (< pool)
os	progress/diagnostic messages are written here at NORMAL output detail or above

sampled_forward()

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

bool FST::Sequential_Step_Sampled< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, WEIGHTER >::sampled_forward ( RETURNTYPE & result, const PSubset sub, const PCriterion crit, const DIMTYPE pool, const DIMTYPE cap, std::ostream & os )

inlineprivate

Budgeted forward step: proposes exactly cap candidate features (see the class docs above for the sampler-mode and exploration-floor mechanics), evaluates the proposed batch through the injected engine, feeds every evaluation to the statistics engine and (if active) the result tracker, and selects the best-scoring proposed feature into sub. All fst_rand() draws happen before any candidate is handed to the engine, so proposal sampling is unaffected by threaded evaluation (see the threading paragraph in the class docs).

Parameters

result	set to the winning candidate's criterion value on success
sub	the working subset; the winning feature is added in place
crit	the criterion each proposed candidate is evaluated against
pool	number of free features available
cap	number of candidates to propose (< pool; the caller has already ruled out the full-sweep fallback)
os	progress/diagnostic messages are written here at NORMAL output detail or above

---

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

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