create selected_index using feature selection

[smassung]

Create an index wrapper that uses the feature selection algorithms to determine whether or not to return certain terms from the index back to the user/application.

[skystrife]

Based on the way meta-classify now works, I think this is a ctor for learn::dataset that takes an index and a feature selector and selectively loads in only the active features into memory.

[skystrife]

So I set about starting to do this and realized that there's sort of a big choice to make.

First, the easy way to do this: just take an existing labeled_dataset and feature_selector. Iterate through the dataset and filter each feature_vector to only contain features that are marked selected via selector.selected(feat_id). This will work, but will result in classification models that can end up being way larger than they need to be due to containing weights for lots of now unused feature ids.

An alternative is to somehow "condense" the feature id space by performing a relabeling by pretending all non-selected feature_ids don't exist. As a simple example, if we had feature ids [0, 1, 2, 3, 4, 5] but only selected [2, 4, 5], we would relabel as 2 -> 0, 4 -> 1, and 5 -> 2.

The problem now is that the feature_ids no longer correspond to term_ids from the original forward_index, so you can't go look up the meaning of weights as easily (or at all) anymore. So we'd likely need to also produce a backward mapping from new id -> old id.

Fortunately, I think we can do these efficiently using stuff from the meta-succinct library (in particular, the sarray). Using sarray_select, we can answer questions like "give me the index of the i-th one in a bit vector". In our case, the "bit vector" is the selected features, where 0 indicates unselected and 1 indicates selected, and the query select(new_id) would return old_id. Using sarray_rank, we can answer questions like "how many ones are before the i-th position in a bit vector". In our case, rank(old_id) (where old_id is indeed a selected feature) would return new_id.

Perhaps unfortunately, all of the stuff in succinct is currently designed around keeping storage in memory-mapped files (so they can be easily persisted to disk). That would be totally unnecessary here, and it'd be confusing to have to give a folder prefix to create a new feature-selected dataset. So in order to actually do this, I'd need to do a (probably beneficial anyway) refactoring of meta-succinct to support non-persisted storage.

(...sorry, this is turning into a stream-of-consciousness note.)

An alternative would be to store this mapping inside the feature_selector itself, since it requires a prefix in order to store its pre-computed scores anyway. selector.select(k) or selector.select_percent(p) could simply construct the corresponding sarray for us automatically, and we could expose both new_id -> old_id and old_id -> new_id mappings as member functions.

...and actually, I think this ends up being really neat. Constructing an sarray simply requires a list of the positions of all of the ones in a bit vector (assumed to be sparse, hence sarray) which is exactly what we're generating in selector.select()/selector.select_percent. Additionally, I think we can eliminate the entire util::dist_vector<bool> for marking which features are selected! (but my logic would need double-checked.)

If we have the sarray already constructed, determining if old_id has been selected amounts to checking whether rank(old_id) < rank(old_id + 1). If the rank of old_id + 1 is greater than the rank of old_id, that means that there is one more one before old_id + 1 than there is before old_id, meaning old_id itself was the position of that one. If the ranks are the same, then old_id could not have been a one and is thus unselected.

So basically, in summary:

bool feature_selector::selected(term_id tid) const
{
    return s_rank.rank(tid) < s_rank.rank(tid + 1);
}

feature_id feature_selector::new_id(term_id tid) const
{
    return s_rank.rank(tid);
}

term_id feature_selector::old_id(feature_id fid) const
{
    return s_select.select(fid);
}

@smassung, what do you think?

[smassung]

Looks great, we discussed in person. Moving discussion to PR.

[skystrife]

Added in afa62a9.