ÚTIA — Institute of Information Theory and Automation, Czech Academy of Sciences
Find the features that matter — reproducibly, on any platform, at any dimensionality. A standalone C++ library and a single-binary command-line tool for choosing, out of everything you measured, the subset your model should actually use.
--threads--seed ⇒ same result on every OS./fst4 --data data/wdbc_30.trn \
--criterion wrapper-knn --knn-k 3 \
--splitter 5050 --splitter2 cv \
--search sffs \
--validate sameOne command, four decisions: what to optimize (3-NN accuracy), how to estimate it honestly (inner cross-validation on one half, the other half walled off), how to explore (floating search), and the final honesty check (the untouched holdout). Load a dataset, run the search on the selection half, and report the chosen subset with its holdout validation — the complete textbook protocol.
01 · The problem
Most datasets measure far more variables than the signal needs. Feature selection picks the subset worth keeping — and unlike projection methods (PCA and friends), the selected variables remain the original, interpretable measurements. Nothing is mixed, rotated, or renamed. Three reasons to care, in decreasing order of frequency:
With limited samples, models fit noise in irrelevant variables. Removing them is regularization you can inspect — and explain.
Features can be expensive to acquire: sensors, lab tests, compute. A model that needs 10 of 500 inputs is a different product from one that needs all 500.
Which variables carry the signal is often the actual research question. The subset is the answer, not a preprocessing step.
The catch: subsets live in a space of 2D candidates, every candidate must be scored, and every score is only an estimate made from finite data. Feature selection is therefore three problems wearing one coat — a search problem, a scoring problem, and a statistical-honesty problem. FST4 treats all three as first-class.
02 · The design
FST4 is built around one organizing idea: feature selection is a search over subsets, scored by a criterion, estimated on data splits, with results collected by trackers. The four axes compose freely — any search runs any criterion on any splitting protocol — and the command line mirrors them one flag each.
--validate.Everything runs from one binary with no mandatory external dependencies. ./fst4 --list prints
the full component registry with validity notes; every misuse produces an actionable error, not a silent
fallback. The same components are equally usable as a C++ template library — the CLI is a thin composition
layer over public seams.
03 · The choice that matters most
Newcomers to feature selection agonize over search algorithms. The evidence says: agonize over the criterion instead. Search algorithms differ in how hard they push the objective; criteria differ in what is being pushed. A perfect search of the wrong objective returns a confidently wrong subset.
FST4 makes this concrete. Take one dataset, one search (floating), one classifier (3-NN) — and change
only the optimized metric from plain accuracy to balanced accuracy. The two runs select almost disjoint
subsets: cross-scenario similarity IATI ≈ 0.14 on the diagnostic data of
demos/demo14.cfg. Same everything, different question, different answer. Choose the question
first.
Filter criteria score subsets from data statistics alone — no classifier is trained, evaluations cost microseconds, and there is no classifier to overfit. All five are cardinality-monotonic, which is exactly what the optimal searches of section 05 need:
| criterion | model | notes |
|---|---|---|
bhattacharyya | Gaussian | two-class; the recommended default filter |
divergence | Gaussian | two-class; can breach monotonicity numerically on some data — prefer Bhattacharyya |
gmahalanobis | Gaussian | two-class generalized Mahalanobis distance |
multinom-bhattacharyya | multinomial | count/text data, any class count |
multinom-mi | multinomial | mutual information for count/text data |
Wrapper criteria train and test an actual predictor on every candidate subset — slower, but they measure the thing you ultimately ship. FST4 carries a full model zoo, implemented from scratch in the library and deterministic by design:
| criterion | model | notes |
|---|---|---|
wrapper-knn | k-nearest neighbours | --knn-k, L1/L2/Lp distances |
wrapper-bayes | Gaussian Bayes | per-class covariances, any class count |
wrapper-lda | linear discriminant | pooled covariance, closed form, parameterless |
wrapper-logreg | multinomial logistic regression | deterministic Newton training, RNG-free |
wrapper-linsvm | linear SVM | dual coordinate descent, RNG-free, one-vs-rest |
wrapper-rbfsvm | RBF-kernel SVM | native, deterministic; built-in C/γ tuning (--rbfsvm-optimize) |
wrapper-svm | kernel SVM (poly/sigmoid too) | via the optional LibSVM drop-in |
wrapper-rf | Random Forest | CART/Gini + bagging; deterministic by construction |
wrapper-multinom | multinomial naive Bayes | count/text data |
wrapper-regressor | weighted-neighbours regression | regression pipeline |
wrapper-ridge | ridge regression | closed form; criterion defaults to R² |
wrapper-extern | your own model | any language, persistent-process protocol — section 06 |
Every wrapper optimizes plain accuracy by default, but imbalanced problems deserve better.
--wrapper-metric switches the optimized quantity to balanced-accuracy,
f1, f1-macro, or exact-rank auc (binary exact; multiclass as
one-vs-rest macro AUC) for classification, and r2, neg-rmse, neg-mae
for regression. --class-weights 1,5 injects asymmetric error costs — a missed positive can cost
five times a false alarm, and selection will pick features accordingly.
--validate is given — via --report detailed, so you see where
your own d★ sits instead of guessing.Honest guidance — filter or wrapper?
Filters are orders of magnitude faster and immune to classifier overfitting, but they optimize a proxy.
Wrappers optimize deployed performance — and can over-optimize it when samples are few and
features many. When samples are scarce, prefer filters or regularized criteria, and distrust any criterion
value not confirmed on a holdout. The nested-split protocol and --validate exist exactly for
this.
04 · Exploring 2ᴰ subsets
With the criterion chosen, the search question has a surprisingly crisp answer.
If your criterion is monotonic — a subset never scores above its supersets, true for all
five built-in filters — and the dimensionality is moderate, FST4's four Branch & Bound
variants (bb-basic, bb-improved, bb-fast, bb-bbpp)
return the provably optimal subset of a given size at a fraction of exhaustive cost, and
exhaustive search settles anything smaller. Where optimal search is affordable, it ends the
discussion:
./fst4 --data data/wdbc_30.trn --criterion bhattacharyya \
--search bb-fast --target-d 7 --validate knnFST4 is honest about the fine print: supply a criterion that does not declare monotonicity and Branch & Bound warns you that its optimality guarantee is off. Wrappers are not monotonic — for them, “optimal” search is exhaustive search, and exhaustive search is 2ᴰ.
Two reasons, one practical and one statistical. Practically, cost explodes: the last one or two percent of criterion value can cost orders of magnitude more evaluations. Statistically — and this is the part that is easy to miss — the criterion is an estimate. Optimizing an estimate beyond its own noise floor buys false precision: the “optimal” subset of the sample is not the optimal subset of the problem. Past a point, extra search effort optimizes noise.
Greedy forward selection (sfs) is cheap but suffers from nesting — an early pick can never be
reconsidered. Floating search (sffs, backward sbfs) fixes exactly
that: after every forward step it backtracks as long as removing a feature improves the criterion.
The result is near-optimal subsets at polynomial cost, plus the entire best-subset-per-size curve in one run
— no target size needs to be fixed in advance. If you do know the target size, the oscillating searches
(os, dos) refine around it; sfrs/sbrs retreat more
aggressively; montecarlo samples subsets at random — a baseline, and the probe generator for
DAF ranking below.
Searches also compose with step evaluators: --evaluator hybrid pre-sorts
each step's candidates with a cheap filter so the expensive wrapper only sees the promising ones;
--evaluator ensemble lets several classifiers vote; and --threads N fans candidate
evaluations out to a thread pool — with results, by design, identical to sequential execution.
05 · The big gun
At D ≈ 10 000, classic sequential search dies of arithmetic: every floating-search step sweeps all D candidates, so a single step costs thousands of criterion evaluations — with a wrapper criterion, that is the end of the story. The usual retreat is to give up on search altogether and rank features individually. FST4 offers a stronger option.
The budgeted stochastic sequential search (--evaluator sampled) replaces
each step's full sweep with a fixed-size, adaptively informed sample: online per-feature statistics —
collected free of charge from every criterion evaluation the search already pays for — feed a softmax
proposal distribution (with a guaranteed exploration floor) that nominates --step-cap
candidates per forward step and --step-cap-backward per backward step. Step cost is set by the
budget, not by D. A frontier bound (--sffs-delta) keeps the floating expansion near
the target size instead of wandering toward full dimensionality. The method and its evaluation are
described in Somol and Grim, Stochastic Sequential Search in Very-High-Dimensional Feature
Selection, arXiv:2608.01502 (2026).
# 10,105-feature text data, target d=500, 8 threads — minutes, not days:
./fst4 --config demos/demo37t.cfg
# the campaign protocol behind it, spelled out:
./fst4 --data data/reuters_apte.arff --criterion multinom-bhattacharyya \
--search sffs --target-d 500 --sffs-delta 20 \
--evaluator sampled --step-cap 100 --step-cap-backward 50 \
--threads 8 --validate multinomTwo shipped protocols mark the scale: 5 000-feature handwriting data searched to d = 300
(demos/demo36.cfg), and 10 105-feature text categorization searched to d = 500 in minutes on
8 threads (demos/demo37t.cfg) — threaded runs bit-identical to sequential at the same
--seed, for any thread count.
FST4's other high-dimensional instrument is DAF (Dependency-Aware Feature ranking):
run montecarlo probes with the feature-stats tracker, and every feature is ranked
by its average contribution across thousands of random subsets (--daf-rank, pairwise statistics
via --daf-pairs). Unlike per-feature ranking, DAF sees features in company, yet it
stays blunt enough to be extremely robust. The two methods form a genuine duality:
The stronger optimizer. Actively constructs a subset; with budget it decisively out-scores rankings on the criterion. The choice when you can validate and want the best subset the data can support.
The robust one. Averages over thousands of probes; stable across data resamples and seeds, hard to overfit, cheap. The safer default when samples are scarce relative to dimensionality.
--evaluator sampled)
DAF ranking (montecarlo + feature-stats)
BIF (individual ranking)
--validate, and let DAF's robustness arbitrate ties. FST4 makes the comparison a one-liner
(--compare-config, section 07).06 · Open the loop
Everything so far used FST4's built-in models. But the most consequential capability is the generic one: FST4 will optimize a criterion it has never heard of. Your model, your metric, your cost function — in Python, R, awk, or a compiled binary — plugs into every search, splitter, tracker and thread of the toolbox through a persistent-process line protocol on stdin/stdout. Three escalating layers:
# your classifier in the loop (reference tool: a nearest-centroid model in awk):
./fst4 --data data/wdbc_30.trn --criterion wrapper-extern \
--extern-cmd "awk -f tests/extern_centroid.awk" \
--splitter 5050 --splitter2 cv --search sfs --target-d 3 --validate same
# your criterion in the loop — and, asserted monotonic, under PROVABLY OPTIMAL search:
./fst4 --data data/wdbc_30.trn --criterion extern-value \
--extern-cmd "awk -f tests/extern_value_meandiff.awk" \
--extern-monotonic --search bb-improved --target-d 3That second command deserves a double take: --extern-monotonic asserts that your criterion
is cardinality-monotonic, which admits the Branch & Bound family — guaranteed-optimal subsets of a
criterion FST4 cannot even inspect. The guarantee then rests entirely on your assertion; without the
flag, the optimal searches refuse and tell you why. Reference implementations of all three protocol layers
ship in tests/ as one-page awk scripts — the protocol is small enough to implement over
coffee.
Loud caveats — by design
--extern-cmd is user-supplied code execution through the shell: run only commands you
trust. FST4's reproducibility guarantees end at the protocol boundary — beyond it, determinism belongs to
your tool. The label-only classifier protocol cannot provide scores, so AUC is unavailable there
(confusion-based metrics work).
07 · Trust, but verify
Feature selection is uniquely exposed to self-deception: the same data that chooses the subset praises it. FST4's estimation machinery is built to keep the praise and the choice apart.
The splitter axis (5050, cv, holdout, resub,
leave1out, randrand/randfix) defines the estimation protocol, and
splitters nest: with --splitter 5050 --splitter2 cv, the criterion runs on
inner cross-validation folds of the outer training half while the outer holdout stays untouched for
--validate — selection never sees the data it is judged on. Scaling
(--scaler to01|white) normalizes from training-part statistics only when you ask for it with
--scaler-fit train; the default fits the transform on the whole dataset before splitting, the
FST3 convention.
--validate knn,bayes,lda then reports holdout performance under classifiers that took no part
in selection — the cheapest honesty check there is.
Trackers observe every evaluated subset. The default keeps the best-k distinct subsets;
regularizer prefers a smaller or cheaper subset within a criterion margin of the best — a
direct antidote to overfitting-by-greed; stabileval measures selection stability
across repeated splits (--repeat-over-splits): if ten resamples of your data select ten
disjoint subsets, no single run should be trusted, and now you know. --compare-config runs a
second scenario and quantifies the similarity of two whole selection processes (IATI/ICW/IANHI) —
the instrument behind the metric-flip experiment of section 03.
08 · The contract
Randomized feature selection has a credibility problem: rerun someone's experiment and you get a different subset. FST4 treats determinism as a contract with a test suite:
--seed yields the same splits, the same
sampled candidates, the same subsets, on every platform. An unseeded run equals --seed 1:
even the default is reproducible.--threads 8 is free of scientific cost.The single deliberate exception is the external bridge — beyond the protocol line, determinism is your tool's job.
09 · From experiment to pipeline
--report detailed upgrades any run into a small research report: the best-per-size
criterion curve with holdout re-validation of every subset (the overfitting curve of section 03), tabular
ROC and precision–recall curves of the validating classifier, confusion matrices, and any hyperparameters
the run tuned. --curves-svg renders those curves as a self-contained picture — no plotting
library, nothing fetched from anywhere — and keeps the criterion and the holdout on separate axes, so the
overfitting panel cannot be misread as one quantity. --dump-scores writes the per-sample
holdout predictions and class scores, for error analysis or an ROC variant of your own. For automation,
the CLI is pipe-clean by design in both directions: with --output json or
csv, all prose goes to stderr and stdout carries only the result —
./fst4 … --output json | jq just works — while --data - takes the dataset from
standard input, so fst4 sits in the middle of a pipeline like any other filter:
zcat data.trn.gz | ./fst4 --data - --format trn … | jq. --progress json emits one
JSON line per improved solution for live dashboards, config files capture whole scenarios
(--config demos/demo10.cfg), and --seed makes every pipeline rerun byte-comparable
to the last.
10 · See for yourself
Every capability on this page ships as a ready-to-run config — ./fst4 --config demos/demoNN.cfg
from the repository root; the demo datasets are included in data/ (see
data/readme.txt). A guided selection:
| config | what it shows |
|---|---|
demo10.cfg | filter selection + independent validation — the basic protocol |
demo14.cfg | balanced vs. plain accuracy changing what gets selected (IATI ≈ 0.14) |
demo15.cfg / demo16.cfg | AUC-driven selection / cost-sensitive selection (--class-weights) |
demo17.cfg / demo19.cfg | regression selection by R² — neighbours / ridge |
demo18.cfg / demo38.cfg | Random Forest vs. linear-SVM wrappers on spam data |
demo29.cfg | RBF-SVM wrapper with built-in C/γ tuning |
demo41.cfg | optimal Branch & Bound |
demo34.cfg | DAF ranking at high dimensionality |
demo36.cfg / demo37t.cfg | budgeted stochastic search at 5 000 and 10 105 features |
demo54.cfg / demo55.cfg | selection stability / process-similarity comparison |
demo64.cfg | your-own-model selection via the external bridge |
11 · Ninety seconds
# build (CMake ≥ 3.x, any C++17 compiler; no external libraries needed):
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel --target fst4
# first result:
build/bin/fst4 --config demos/demo10.cfg
# what else is in the box:
build/bin/fst4 --list
build/bin/fst4 --helpFrom there: doc/FST4_CLI.md is the complete flag reference,
the ready-to-run configs in demos/ map protocols to command lines, and the C++ API is documented in the
source headers (Doxygen configuration in doc/). The library itself is header-only — C++
consumers include and go; the demo sources in demos/ show the idiom.
12 · The fine print, honestly
fst4 command-line tool additionally uses CLI11 for argument parsing — vendored
in-tree (BSD-3-licensed), so there is nothing to fetch, and library-only consumers carry no CLI11
obligations. Exactly two optional external libraries exist — LibSVM (enables the
wrapper-svm kernel zoo; drop-in, auto-detected) and Eigen (optional swap-in for the
internal matrix kernels, used to cross-verify the built-in solvers — which it matches at print
precision). Everything else,
Random Forest to ridge to both native SVMs, is implemented in the library itself, keeping the licensing
story a one-liner.LICENSE): anyone, including commercial
users, may use, modify and redistribute it, provided that modified versions they distribute or serve over
a network stay under the AGPL with complete source. Organizations that want FST4 in closed-source products
without those obligations need a commercial license from ÚTIA. LICENSING.md explains
both options and the contributor license agreement. In case of interest in a commercial license, or with
any licensing question, write to utia@utia.cas.cz; technical
questions and pull requests: somol@utia.cas.cz, with "FST" in the
subject line.