finalfusion embeddings in Rust

edit: Copied the list from the other comment to get an indicator for the list ticks.

Going through the API:

• [x] prelude.rs: #105

1. prelude re-exports SimpleVocab and SubwordVocab but not the aliases for FinalfusionSubwordVocab etc. I think it makes more sense to re-export the aliases and leave SubwordVocab in chunks::vocab.
2. MMapQuantizedArray is the only storage not re-exported.
3. NdNorms is the only public chunk not being re-exported.

• [x] chunks::storage::mod.rs:

• [x] chunks::storage::array.rs: #93

1. NdArray derives Debug but not MmapArray.
2. NdArray should derive Clone

• [x] chunks::storage::wrappers.rs:

1. StorageViewWrap implies that it wraps a view while it actually wraps a viewable storage. Think about renaming?

• [x] chunks::mod.rs:

1. Might be nice to explain the concept, right now the module docs state finalfusion chunks

• [x] chunks::io.rs: #92 Nothing public but from maintainers perspective:

1. typeid_impl is lacking docs, choices 1 for u8 and 10 for f32 seem arbitrary - iirc in order to leave room for other int and float types. Could still use some docs to make that clear once this is forgotten.

• [x] chunks::metadata.rs: #91

1. Encapsulate the inner Value.
2. Alternatives to lock in toml as our choice? Upside of toml is that we get easy serialization and heterogeneous collections. Downside is that we always need Values to construct.

• [x] chunks::norms.rs: #90

1. Encapsulate NdNorms' inner array
2. ~~impl Index for NdNorms since Norms seems to be just that but without the [ ]-indexing~~ Index::index returns references. I'd still like to make norm a method directly on NdNorms since NdNorms is entirely useless without importing Norms otherwise.

• [x] chunks::vocab.rs: #89

1. Rename vocabtypes as discussed
2. Think about reorganizing in separate modules, i.e. vocab::mod.rs, vocab::subword.rs, vocab::simple.rs.
3. [x] Remove Clone from Vocab's requirements and the other places where it pops up because of this requirement. (e.g. Indexer bounds)

• [x] compat::fasttext

• [x] compat::{text.rs, word2vec.rs}

• [x] embeddings.rs

1. Go through trait-bounds.

• [x] io.rs

• [x] lib.rs

• [x] similarity.rs

1. Could be nicer to read if put into module with similarity::analogy.rs and similarity::similarity.rs

• [x] subword.rs

1. Indexers could live in their own indexer.rs

• [x] util.rs

What needs to be done until then?

• Probably clean up chunks::Vocab::{NgramIndices, SubwordIndices}, consolidate into one trait?. Related to that, bracketing words per default forces us to collect the indices in both methods and return them as Vec.

I spent a fair amount of time to implement this properly (everything gated through a special AlignedArray type, which has constructors guaranteeing alignment).

On CI enabled tests using 32-byte alignment. Recent glibc versions allocate on 16-byte boundaries, so tests would never fail on my machone, even when the code was wrong. But even with 32-byte boundaries there is some non-determinism, since there is a small chance that memory that is not explicitly aligned ended up on a boundary by chance.

Advantages:

• We have explicit control over alignment.
• By using feature gating, we can use default (f32) alignment as before.
• We can give other libraries (Eigen, Tensorflow) the alignment that they need.

Disadvantages:

• As discussed, reading text files without dimensions, no requires two passes over the file.
• We have to be very careful with new code to use Vec::with_capacity_aligned if an embedding matrix is initialized from a Vec.
• Apart from non-determinism, we might miss cases where alignment is not enforced, when the code path is not covered by a unit test (I just did a grep for vec! and Vec::with_capacity).

Add support for reading and using Floret embeddings. Floret combines subword embeddings with Bloom embeddings:

https://github.com/explosion/floret#how-floret-works

This allows Floret embedding matrices to be compact like Bloom embeddings, while also using subword units.

Supporting Floret embeddings requires some architectural changes to finalfusion:

1. ngrams -> index mappings are many-to-many

   finalfusion assumed that each n-gram maps to a single index. In Floret embeddings, an n-gram can map to multiple embeddings. finalfusion is extended in this change to support returning multiple indices for an n-gram.

2. Floret also hashes the word itself, not just the subwords. This change adds a boolean flag. If it is enabled, the word itself is also hashed, and its index is returned.

3. Floret permits different begin/end-of-word markers. These are made configurable for subword vocabs.

Does what it says on the tin: memory-maps the quantized embeddings matrix and norms (if present).

This change does not implement WriteChunk for this data type, which will be added through a separate PR.

There is still a build error, because tempfile depends on some crate that does not build with Rust 1.31.0. This 'only support/check against the latest Rust stable' in the Rust ecosystem is becoming quite maddening.

We could get a lot of additional pretrained embeddings for 'free' if we convert fastText embeddings from:

https://fasttext.cc/docs/en/crawl-vectors.html

Any opinions?

This chunk stores the norms of in-vocabulary words. If an Embedding data structure stores NdNorms, the vector norms can be queried with the embedding_with_norm method.

When converting from word2vec/text in ff-convert, always normalize embeddings and store norms.

Some random points:

• I still need to add some more unit tests.
• The norms chunk is currently not a generic type of Embedding. This is to keep the type signature simple while we still can. This may change later. It will definitely be necessary when we want to make it memory mappable.
• The norms chunk is optional, for compatibility with existing finalfusion embeddings. Since we can assume the (known) word embeddings to be normalized, the norm 1 is returned when the chunk is absent.
• ff-convert from word2vec and text now always normalizes the embeddings and creates a norms chunk.
• I am considering to multiply the unit vectors by their norms when converting to word2vec or text embeddings, to restore the raw, unnormalized embeddings. However, this is currently not done.
• I tried to make the norms mandatory (normalizing the embeddings and computing norms when the chunk is not present). However, this poses problems, because mmaped and quantized embeddings cannot be updated.
• The traits for reading word2vec/text embeddings still have an argument for normalization. These are still needed for roundtrip unit tests. I might make a crate-private trait for unnormalized reading and call this from the public trait that always normalizes. This would allow us to keep the roundtrip unit tests, while always normalizing in the public interface. (Done now for ReadWord2Vec)

Add a method to query for the most similar words given a query vector.

Thought, this could be nice to have since analogy queries are essentially doing the same.

Add conversion from BucketVocab to ExplicitSubwordVocab. This requires storage of indices on disk, read and write methods now store indices, too.

Depends on #89, implements option 2 described in https://github.com/finalfusion/finalfusion-rust/issues/87#issuecomment-543739524

• Merge the Error and ErrorKind enums.
• Move the Error enum to the error module.
• Derive trait implementations using the thiserror crate.
• Make the Error enum non-exhaustive
• Replace the ChunkIdentifier::try_from method by an implementation of the TryFrom crate.

I think that for downstream users it would be great if we had a first release. Due to semver, once we release 1.0.0, we cannot break APIs anymore in 1.x.y. Basically, once someone puts

finalfusion = "1"

in their Cargo.toml, it should always work for 1.x.y. Of course, we can extend the API.

This issue is for discussing what still needs to be done before 1.0.0. What sore thumbs are sticking out. Also, we should probably look if there are any public APIs that need to be private or crate-private.

finalfusion-rust is currently licensed under the following licenses (user's choice):

• Apache License Version 2.0
• Blue Oak Model License Version 1.0.0

We are trying to relicense the finalfusion ecosystem to something that is more canonical for the Rust ecosystem, namely (user's choice):

• Apache License Version 2.0
• MIT License

I, @sebpuetz, and SfS ISCL have agreed with relicensing all finalfusion projects in this way. However, finalfusion-rust has two additional contributors:

• @RealNicolasBourbaki
• @djc

If you are ok with this relicensing, could you please reply to this issue confirming this? Thanks a lot!

While reimplementing finalfusion-inspector in Rust, I bumped into a small annoyance. The analogy method takes an array of &str:

query: [&str; 3]

However, oftentimes you have a [String; 3]. We should relax this type to:

query: [impl AsRef<str>; 3]

This should not break the API, since it allows a superset of types of the original signature.

I think it would be nice to have a small utility data structure to fetch pretrained embeddings. I don't think this needs to be part of the finalfusion crate, since it is not really core functionality. The basic idea is:

• We'd have a repository finalfusion-fetcher with some metadata file (probably JSON), mapping embedding file identifiers to URLs. E.g. fasttext.wiki.nl.fifu could map to http://www.sfs.uni-tuebingen.de/a3-public-data/finalfusion-fasttext/wiki/wiki.nl.fifu

• A small crate (possibly in the same repo), would provide a datastructure Fetcher With a constructor that retrieves the metadata and gives a fetcher:

  let fetcher = Fetcher::fetch_metadata().unwrap();
  

  A user could then open embeddings:

  let dutch_embeddings = fetcher.open("fasttext.wiki.nl.fifu").unwrap();
  

  This method would check if the embeddings are already available. If not, fetch them, store them in a standard XDG location. Then it would open the embeddings stored in this location.

  Similarly, Fetcher::mmap could be used to memory-map an embedding after downloading.

After this is implemented, the functionality could also be exposed in finalfusion-python.

Add support for pruning embeddings, where N embeddings are retained. Words for which embeddings are removed are mapped to their nearest neighbor.

This should provide more or less the same functionality as pruning in spaCy:

https://spacy.io/api/vocab#prune_vectors

I encourage some investigation here. Some ideas:

1. The most basic version could simply retain the embeddings of the N most frequent words and map all the remaining words to the nearest neighbor in the N embeddings that are retained.

2. Select vectors such that the similarities to the pruned vectors is maximized. The challenge here is making it tractable.

3. An approach similar to quantization, where k-means clustering is performed with N clusters. The embedding matrix is then replaced by the cluster centroid matrix. Each word maps to the cluster it is in. (This could reuse the KMeans stuff from reductive, which is already a dependency of finalfusion).

I would focus on (1) and (3) first.

Benefits:

• Compresses the embedding matrix.
• Faster than quantized embedding matrices, because simple lookups are used.
• Could later be applied to @sebpuetz 's non-hashed subword n-grams as well.
• Could perhaps be combined with quantization for even better compression.