FFSVM stands for "Really Fast Support Vector Machine"

Ralf Biedert

Last update: Nov 24, 2022

Related tags

Overview

In One Sentence

You trained a SVM using libSVM, now you want the highest possible performance during (real-time) classification, like games or VR.

Highlights

loads almost all libSVM types (C-SVC, ν-SVC, ε-SVR, ν-SVR) and kernels (linear, poly, RBF and sigmoid)
produces practically same classification results as libSVM
optimized for SIMD and can be mixed seamlessly with Rayon
written in 100% Rust
allocation-free during classification for dense SVMs
2.5x - 14x faster than libSVM for dense SVMs
extremely low classification times for small models (e.g., 128 SV, 16 dense attributes, linear ~ 500ns)
successfully used in Unity and VR projects (Windows & Android)

Note: Currently requires Rust nightly (March 2019 and later), because we depend on RFC 2366 (portable SIMD). Once that stabilizes we'll also go stable.

Usage

Train with libSVM (e.g., using the tool svm-train), then classify with ffsvm-rust.

From Rust:

// Replace `SAMPLE_MODEL` with a `&str` to your model.
let svm = DenseSVM::try_from(SAMPLE_MODEL)?;

let mut problem = Problem::from(&svm);
let features = problem.features();

features[0] = 0.55838;
features[1] = -0.157895;
features[2] = 0.581292;
features[3] = -0.221184;

svm.predict_value(&mut problem)?;

assert_eq!(problem.solution(), Solution::Label(42));

Status

June 7, 2019: Gave up on 'no unsafe', but gained runtime SIMD selection.
March 10, 2019: As soon as we can move away from nightly we'll go beta.
Aug 5, 2018: Still in alpha, but finally on crates.io.
May 27, 2018: We're in alpha. Successfully used internally on Windows, Mac, Android and Linux on various machines and devices. Once SIMD stabilizes and we can cross-compile to WASM we'll move to beta.
December 16, 2017: We're in pre-alpha. It will probably not even work on your machine.

Performance

Classification time vs. libSVM for dense models.

Performance milestones during development.

All performance numbers reported for the DenseSVM. We also have support for SparseSVMs, which are slower for "mostly dense" models, and faster for "mostly sparse" models (and generally on the performance level of libSVM).

See here for details.

Tips

For an x-fold performance increase, create a number of Problem structures, and process them with Rayon's par_iter.

FAQ

See here for details.

Comments

Suggestions for better results

Hi I am training regression svm using this library, and I get horrible results. I verified with libsvm and it provides the same results. What is a good approach to svm regression? Here is what I should get: Screen Shot 2019-03-20 at 1.17.59 AM.pdf Here is the predicted: Screen Shot 2019-03-20 at 1.18.35 AM.pdf I tried all possible kernels but I cannot get it to work. Screen Shot 2019-03-20 at 1.18.56 AM.pdf Screen Shot 2019-03-20 at 1.21.41 AM.pdf

I have 219k data points with 100 dimensions.
question

opened by karasjoh000 2

Lack of empty line in a model causes kernel panic

The model below causes a panic. Please note the lack of empty line at the end of the file.

kernel_type rbf
gamma 1
nr_class 2
total_sv 2
rho -0.109665
label 1 0
probA -4.83344
probB 0.590724
nr_sv 1 1
SV
0 0:0 1:0 2:0 3:0 4:0 5:0 6:0 7:0 8:0 9:0 10:0 11:0 12:0 13:0 14:0 15:0 16:0 17:0 18:0 19:0 20:0 21:0 22:0 23:0
1 0:0 1:0 2:0 3:0 4:0 5:0 6:0 7:0 8:0 9:0 10:0 11:0 12:0 13:0 14:0 15:0 16:0 17:0 18:0 19:0 20:0 21:0 22:0 23:0

opened by Hoodad 2

breaks on label with labels 1 -1

I have a model file with label 1 -1 however the parser only parses label 1 and therefore it breaks at this part:

            // Construct vector of classes
            let classes = match svm_type {
                // TODO: CLEAN THIS UP ... We can probably unify the logic
                SVMType::CSvc | SVMType::NuSvc => (0..num_classes)
                    .map(|c| {
                        let label = header.label[c];
                        let num_sv = nr_sv[c] as usize;
                        Class::<$m32>::with_parameters(num_classes, num_sv, num_attributes, label)
                    })
                    .collect::<Vec<Class<$m32>>>(),
                SVMType::ESvr | SVMType::NuSvr => vec![Class::<$m32>::with_parameters(
                    2,
                    num_total_sv,
                    num_attributes,
                    0,
                )],
            };

here is my file header:

svm_type c_svc
kernel_type rbf
gamma 0.076923076923076927
nr_class 2
total_sv 132
rho 0.42446205176771579
label 1 -1
nr_sv 64 68
SV

however the header gets parsed like this:

[src/svm/core/sparse.rs:41] header = Header {
    svm_type: "c_svc",
    kernel_type: "rbf",
    gamma: Some(
        0.07692308
    ),
    coef0: None,
    degree: None,
    nr_class: 2,
    total_sv: 132,
    rho: [
        0.4244620517677158
    ],
    label: [
        1
    ],
    prob_a: None,
    prob_b: None,
    nr_sv: [
        64,
        68
    ]
}

probably does not like the negative sign

opened by karasjoh000 1

Status Update
Various notes to self:

the crate is not really dead, the cross-platform SIMD situation has just been a bit ... frustrating

once something like packed SIMD ever stabilizes I want to move to that

I consider classification / regression mostly feature complete

IIRC there are one or two rarer kernels not implemented yet, PRs welcome

Training is missing too, probably won't implement it myself as I don't really need it, PRs also welcome #2

runtime SIMD selection should probably be removed again (came to generally prefer unsafe free over a few percent more performance)

once safe transmutes are a thing simd_aligned dependency should be removed

if meanwhile anyone feels repelled by fact last commit is 2+ years old and / or project would not compile in specific constellation I'm also happy to accept PRs and / or add co-maintainers
opened by ralfbiedert 0
Should support training
Blocked by

[ ] Need high-performance matrix library that abstracts away sparse and dense (SIMD) matrices.

[ ] In turn blocked by num-traits abstraction to handle scalar and packed types / math transparently.
opened by ralfbiedert 2