Roadmap to version 1.0, please participate

[Mec-iS]

Hello people,

Considering the path set by Volodymyr in #108, I have been trying to work his ideas to make the library fitter to current developments in the Rust ecosystem (in particular what has been done in num-traits). To do so I had to go through some digging in the current state of the library and I noted some drifting and tried to address it:

1. as it is now we have redundant code for the basic skeleton: i.e. different implementations of BaseVector, and other base structures that have been implemented for specific purposes are present. this makes the library very hard to understand and develop for, we cannot allow to have a specific implementation of general functionalities for every new module/feature.
2. Some features have become not so relevant to me (but maybe they are for others), for example the ndarray and nalgebra bindings, there are better ways to achieve the same objectives now and those make only the library clunkier (see below about refactoring).
3. we have focused too much on side (even if very useful) features before having a stable set of functionalities: for example the Wasm target and all the serialization work that has been done recently; these are both my priorities as well but I suggest to focus on implementing the skeleton structure and algorithms first.

So for me a tentative roadmap should look like this:

• ver 0.5 to ver 0.8: a stable skeleton (see below) with as much stable algorithms we can work with basic defaults as present in sklearn
• ver 1.0:
  • everything that points to extending the targets (Wasm: as it is now we don't have a strategy to handle parallelism in Wasm, so we should decide if we want to go for using rayon for example or to support Wasm; both it is not possible at the moment I think given the current maturity of Wasm. There is always time later to provide Wasm-only features once the library is stable). For now I would suggest to forget about Wasm and parallelism to reach stability; once we are at some point around ver 0.9 we can put these back on the table;
  • everything that points to improve accessibility and ergonomicity (serialization, ... , and more exhaustive method signatures; I mean giving more configuration options to users as now we mostly run on default parameters most of the time; plus anything else you want to suggest).

According to this, I have started reworking the skeleton to adhere to what Volodymyr set down; this meant a quite de-structuring process to clean up things and reach the cleanest possible initial implementation. I have reached a good starting point, with a basic skeleton for these functionalities (mostly implemented as traits): Number, RealNumber, BaseMatrix, Matrix, DenseMatrix and all the matrix-related traits ("decomposable" traits). I have reused as much code as I could for the sake of building a new base skeleton; obviously there is still a lot to add but I think if we stick to this convention we can rebuild the whole library easily in this order:

1. Base-traits: numbers, base vector, base matrix, ... (DONE)
2. what is currently is src/linalg (DONE. All existing tests passing, new tests welcome)
3. what is in src/math/distance
4. what is in src/metrics
5. what is in src/linear
6. what is in src/svm
7. what is in src/tree
8. improve DenseMatrix and add ArrayViews (I still don't have a precise idea how to reach/improve on zero-copy)
9. ... all the rest little-by-little

If you want to access the current state of the reworking, please drop a message here and I will add you to the temporary private repo I created until the state of the refactoring is presentable -> https://github.com/Mec-iS/smartcore-numbers (just take a look and you will tell me if it is worth to have a completely new history or if you can manage to merge the new changes to the existing history).
This way we can reuse the code and rebuild the library on a more solid foundations. This is the only option I see viable as the current state of the basic structures is so entangled with the implementation that smaller fixes have resulted in a waste of time (I have spent a lot of hours trying to disentangle the current modules while instead it took half-a-day to rebuild the skeleton reusing existing modules).

Please reply or give feedback here and I will invite you to the temporary refactoring repo. This is also a good way for growing the community as anybody that is going to the participate to the refactoring I propose to be added as a code owner to the current team of maintainers if he/she is interested.

Cheers!

[montanalow]

This is a nice summary of the status quo. I'd love to follow along with your progress to understand the issues more deeply. I think it would be great to reference this issue in your private repo as well so updates are tracked.

[morenol]

Thanks for leading this effort!

@Mec-iS happy to be included and participate in that repo. On the other hand I think that we should not invest time right now in parallelism with WASM. So, I am ok with using rayon but I also think that we always could use feature_flags to at least have a subset of the library that can be used with WASM

[Mec-iS]

Thanks for the feedback. Please see the temporary repo smartcore_numbers https://github.com/Mec-iS/smartcore-numbers

We have now a workable version of DenseMatrix (in the new design using the new Numbers), arrays and array views as designed by Volodymyr. Please take a look, run tests and help porting the missing tests (there are flagged as TODO in the code) and also help remove the warnings.

Current improvements

• Base-traits: numbers, base vector, base matrix, ... (DONE)
• what is currently is src/linalg (DONE. All existing tests passing, new tests welcome)
• ported all the decomposable traits (defined with the _n subfix in PR First draft of the new n-dimensional arrays + NB use case #108)
• make the new decomposable traits to work with the new DenseMatrix that is defined as an Array2
• Removed the old naive implementations (goodbye clucky matrices)
• Ported bg_solver.rs to the new implementation
• important: try to keep the documentation up to date.

Next:

• ~try to fix src/linalg/traits/stats.rs, it looks like svd and mean are not computed correctly with the new ArrayView2; ~
• try to port the src/linear module. If you want to try yourself:
  1. just copy the entire linear module in the new repository,
  2. wire the imports and methods to the new implementation: getter and setter may be working differently as we try to use views as much as possible; for example Array2 use type T but also S = (usize, usize) so self.get( (i, j) ) (note the tuple instead of the two values),
  3. try to build and tests

The new implementation is very powerful but it takes a little time to get in the mechanics, for example there are some traits that need explicit import (see documentation examples).

I think that once linear is ported we have a working first module with basic functionalities and we can think about keep adding or brake the other modules into subpackages. My idea is to provide smartcore_numbers as base package with basic inference capabilities, then allow importing the other packages as "add-ons" as suggested by some of you.

The thing I am trying to understand is what is the functional difference in having a RealNumber and a FloatNumber, I was tempted to completely remove the former. Any hints?
Also: what is the difference between Array and Array1? Why define both and not just one? Just the convenience of keeping Array as abstract method?

[Mec-iS]

I managed to implement the new numbers for #108:

• Remove legacy DenseMatrix and BaseMatrix implementation. Port the new…
  885180f
• Fix imports in src/linear
  644bf2e
• Port src/math/distance
  68c3e36
• Port src/metrics/distance
  2f36438
• Port src/metrics
  00ceb43
• Port src/algorithm
  45f580b
• Port src/dataset src.linear src/optimization
  e2c6f2c

I am finding quite challenging porting the remaining modules, for now they have been excluded:

• cluster
• decomposition
• ensemble
• algorithm`
• model_selection
• naive_bayes
• ... everything commented out in lib.rs

The ported modules build successfully.

test result: FAILED. 136 passed; 5 failed; 5 ignored; 0 measured; 0 filtered out; finished in 0.31s

[Mec-iS]

Work is on the way. But I start thinking I have to completely rewrite the metrics module. I just noted that the API for cross_validate cannot handle the new traits system.

let results = cross_validate(
    BiasedEstimator::fit, &x, &y, 
    NoParameters {},
    cv,
    &accuracy
).unwrap();

In particular accuracy is now a function that makes hard to define the number type handled. This probably requires a rewrite of the metrics/mod.rs to move all the metrics from functions to traits/structs.

PS. Rust Foundation is awarding grants https://app.smarterselect.com/programs/80957-Rust-Foundation

Recap of the new skeleton

Basics

numbers

The library is founded on basic traits provided by num-traits. Basic traits are in src/numbers. These traits are used to define all the procedures in the library to make everything safer and provide constraints to what implementations can handle.

linalg

numbers are made at use in linear algebra structures in the src/linalg/basic module. These sub-modules define the traits used all over the code base.

• arrays: In particular data structures like Array, Array1 (1-dimensional), Array2 (matrix, 2-D); plus their "views" traits. Views are used to provide no-footprint access to data, they have composed traits to allow writing (mutable traits: MutArray, ArrayViewMut, ...).
• matrix: This provides the main entrypoint to matrices operations and currently the only structure provided in the shape of struct DenseMatrix. A matrix can be instantiated and automatically make available all the traits in "arrays" (sparse matrices implementation will be provided).
• vector: Convenience traits are implemented for std::Vec to allow extensive reuse.

linalg/traits

The traits in src/linalg/traits are closely linked to Linear Algebra's theoretical framework. These traits are used to specify characteristics and constraints for types accepted by various algorithms. For example these allow to define if a matrix is QRDecomposable and/or SVDDecomposable. See docstring for referencese to theoretical framework.

metrics

Implementations for metrics (classification, regression, cluster, ...) and distance measure (Euclidean, Hamming, Manhattan, ...). For example: Accuracy, F1, AUC, Precision, R2. As everything else in the code base, these implementations reuse numbers and linalg traits and structures.

[montanalow]

The current metrics implementations for classification are not particularly efficient as well. F1 depends on Precision and Recall, which each (re)compute the confusion matrix independently, along with accuracy. If you're reimplementing metrics, it'd be better to compute the underlying confusion matrix once, and then compute the higher level metrics from the simple comparisons on the confusion matrix.

[Mec-iS]

cool, we have to reimplement everything.
Probably then we need a ConfusionMatrix in the footstep of the new crate::linalg::basic::matrix::DenseMatrix? If we need sparse matrix for that or other, we can use sprs

For example, now I am reimplementing all the metrics to be typed accordingly to the new numbers traits:

/// A trait to be implemented by all metrics
pub trait Metrics<T> {
    /// instantiate a new Metrics trait-object
    /// https://doc.rust-lang.org/error-index.html#E0038
    fn new() -> Self where Self: Sized;
    /// compute score realated to this metric
    fn get_score(&self,
        y_true: &dyn ArrayView1<T>,
        y_pred: &dyn ArrayView1<T>
    ) -> T; 
}

pub struct Accuracy<T> {
    _phantom: PhantomData<T>
}


impl<T: RealNumber + Number> Metrics<T> for Accuracy<T> {
...

I hope I am going the right way to implement trait-objects according to E0038

[Mec-iS]

@montanalow src/metrics are now rewritten with the new traits system. Please familiarize with the new implementation so we can see how to improve the implementation 👍🏼

fc78e97

AUC needs complete rewriting as we need a way to do argsort. Excluded for now

[Mec-iS]

New branch v0.5-wip and new PR ---> #187

[Mec-iS]

you can try the new implementation branch using Jupyter Notebooks ---> https://github.com/smartcorelib/smartcore-jupyter (if you don't have access ping me).

You can add all the notebooks you want, I would aim to have an introductory walkthrough for the new traits; also it would be useful to port smartcore-examples into notebooks.

[Mec-iS]

it would be nice to organize a brief talk (30 minutes) about the current status and future planning, please provide availability via poll: https://doodle.com/meeting/participate/id/aMQMWnBa

[Mec-iS]

@montanalow @VolodymyrOrlov @Steboss (and whoever wants to join) meeting organized for tomorrow (Friday 21st) https://doodle.com/meeting/organize/id/aMQMWnBa
thanks for the availability

EDIT:
meeting link -> meet.google.com/xym-nnzp-wwo

[Mec-iS]

Thanks everybody for the meeting. These are the alternatives for Arrays in Rust as listed in ndarray documentation:

• nalgebra provides 1-D and 2-D column-major vector and matrix types for linear algebra. Vectors and matrices can have constant or dynamic shapes, and nalgebra uses the type system to provide compile-time checking of shapes, not just the number of dimensions. nalgebra provides convenient functionality for geometry (e.g. coordinate transformations) and linear algebra.
• cgmath provides 1-D and 2-D column-major types of shape 4×4 or smaller. It’s primarily designed for computer graphics and provides convenient functionality for geometry (e.g. coordinate transformations). Similar to nalgebra, cgmath uses the type system to provide compile-time checking of shapes.
• rulinalg provides 1-D and 2-D row-major vector and matrix types with dynamic shapes. Similar to ndarray, rulinalg provides compile-time checking of the number of dimensions, but not shapes. rulinalg provides pure-Rust implementations of linear algebra operations.

rulinalg was part of rusty-machine. README states:

Currently the library does not make use of any external dependencies - though hopefully we will have BLAS/LAPACK bindings soon.

Aso the other questions seems to be:

• focus on big data (large framework like pyTorch) or edge/in-browser computations on relatively small datasets?
• what we can keep of the current codebase (considering that we will leverage another library for arrays and decomposition)?

[morenol]

It also looks like rulinalg is no longer maintained

[Mec-iS]

oh thanks. didn't notice the 6yo commit. there is some opportunity in forking it and move it into Rust 2021 maybe?

[Mec-iS]

Some more links about options we may have:

• BLAS Rust bindings https://github.com/mikkyang/rust-blas
• this looks new: https://crates.io/crates/slas

A linear algebra system with a focus on performance, static allocation, statically shaped data
and copy-on-write (aka cow) behavior. Safe and fast bindings for
blas/blis are also provided out of the box.

• this looks like the right option for OpenBLAS: https://crates.io/crates/blas-src
• all BLAS crates https://crates.io/search?q=blas
• This provide LAPACK traits https://crates.io/crates/lapack-traits
• Stainless Steel https://github.com/stainless-steel
• ArrayFire, supports GPU also https://github.com/arrayfire/arrayfire-rust

[Mec-iS]

nice overview about floating point arithmetic: https://0.30000000000000004.com/

[montanalow]

ndarray depends on BLAS under the hood as well. Linfa went through the effort of removing all of their direct usage of blas in favor of higher level reliance on ndarray only which is another option to consider.

[Mec-iS]

Anybody interested in writing Rust bindings for https://github.com/openai/triton to be used in Smartcore? ---> #207
If you like challenge and you have plenty of time, maybe also rewriting Triton in Rust

[Mec-iS]

Looks like with the next two PRs we will have finished the porting and will start the process to release v0.4, please give a try to the code in development!

[Mec-iS]

@morenol @Steboss89 and anybody interested, I will be available Tomorrow Friday the 4th at 5 to 7pm GMT for a conference-call about recent developments and discussion on implementations.

Link ---> meet.google.com/aqh-tznc-pit

[Mec-iS]

Tag for release v0.3.0 ready -> https://github.com/smartcorelib/smartcore/releases/tag/v0.3.0
Release on crates.io in the next days

[Mec-iS]

https://crates.io/crates/smartcore