Handling missing values

[maxstrobel]

Hi,

at first thanks for this great library. It works great.

My question refers to missing values in feature vectors. Say, we have used a set of N d-dimensional vectors to create the classifier.
Is it possible to query neighbours if our query vector has less than d dimension, e.g. a missing values in one or more dimensions?

Thanks in advance & Best,
Max

[yurymalkov]

Hi @maxstrobel,
Thank you for the kind words!

Yes, you can do that using the inner product distance (which just seem to be natural for classification). If you zero all dimensions in the query that are missing (or unknown), they effectively will not be used during the search.

But if you zero too many dimensions of the query, the seach accuracy/speed ratio of the search may degarde (since the index was built using a different metric than it was searched), so do not forgot to increase the ef parameter.

[maxstrobel]

Hi @yurymalkov,

sorry I was a little bit inprecise. I am currently using the 'Squared L2' distance. Is there some workaround to handle missing values here?

I tried your suggestion and used the inner product as distance metric, but sadly the accuracy of my application drops to a fraction opposed to using the L2 distance.

Thanks,
Max

[searchivarius]

@maxstrobel I doubt. This IMHO requires keeping an inverse of a missing value mask together with each vector. Then, when comparing two vectors you would have to mask-out (zero-out) all the differences where a dimension in x or y is missing.

[yurymalkov]

@maxstrobel This can be done only using C++ interface. As @searchivarius has mentioned, you would need to use query-specific masks(there are several ways to do that, e.g. change distance function before every query, or modify the distance to contain masks).

[maxstrobel]

@yurymalkov @searchivarius Thanks for your kind replies!

@yurymalkov I thought about your second advice to modify the distance to contain a mask.
If I would add a mask to the distance function via an diagonal matrix, e.g.:

Distance	parameter	Equation
Squared L2	'l2'	d = sum((Ai-Bi)^2) = (Ai-Bi)^T * W * (Ai-Bi) with W=I
Weighted Squared L2	'Wl2'	d = sum((Ai-Bi)^2) = (Ai-Bi)^T * W * (Ai-Bi) with arbitrary diagonal W

I could mask a missing features by setting the diagonal matrix W=I (I := unity matrix) and zero out those elements that are missing.

Do you have an estimate how this would affect the performance of queries? I would index all samples without missing features, but at test time there would sometimes occur queries with missing features.
In general, is this a valid approach at all or would this procedure fail?

[yurymalkov]

@maxstrobel as to my experience, this is a valid approach.
Although i wouldn't use matricies(which have quadratic compleixty), but just multiply Ai and Bi by the binary mask before computing the distance.

[maxstrobel]

@yurymalkov Nice to hear that this procedure may work.

If I find time during next week I will give it a try.
I would use hnswlib/space_l2.h as a boilerplate and follow those steps:

1. Adopt distance functions (L2Sqr, L2SqrSIMD16Ext, L2SqrSIMD4Ext, L2SqrI)
2. Adjust the space classes (L2Space, L2SpaceI) to use the new weighted versions
3. Extend hnswlib.h to make the new distance available
4. Extend python_bindings to support the new distance

Would that be sufficient or am I missing some steps?

[yurymalkov]

@maxstrobel Yes, this should be sufficient.

[maxstrobel]

@yurymalkov @searchivarius
It seems that handling missing features via weighting of features works. I have implemented only a very basic prototype version (only copy&paste - no clean code...) to check the general behaviour.

Summing up:

1. Added a new distance function to the space interface: get_weighted_dist_func
2. Implemented the weighted distance functions (not the CPU optimized ones...)
3. Added new search methods to hnswalg (i.e. just a copy using the weighted distance) : searchWeightedKnn and searchBaseLayerSTWeighted
4. Added weighted_knn_query in python bindings

I made also some small benchmarks to check the behaviour. As benchmark I used sklearns exact kNN and fitted on the subset of available features. The adapted hnswlib kNN is fitted only once with the whole dataset (i.e. all features).
Then I increased the number of (random) missing features and compared the queries of the exact kNN and the hnswlib kNN with weights to disable those missing features. (As a baseline I included also standard hnswlib and imputed zeros formissing features).
I used three toy datasets and got the following results:

dataset: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

dataset: https://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_breast_cancer.html

dataset: human postures from http://users.eecs.northwestern.edu/~jwa368/my_data.html

As you can see your algorithm works really well with the feature weighting as extension to handle missing features (I hope I made no silly mistakes and the results are correct...). Maybe it would make sense to incorporate this in the master branch? What do you think?

Feel free to ask questions if something is unclear.

[searchivarius]

Wow @maxstrobel looks like this warrants an implementation of a special space.

[yurymalkov]

Hi @maxstrobel,
Sure, this can be added to the library, but it has to be clean code.
Also, can you explain what is the accuracy on the plots?

[maxstrobel]

@yurymalkov I try to code it in a clean way in the next days.

The accuracy in the plots is calculated as followed:

0. Fit HNSW on training data with full feature set
1. Iterate from zero to number of features. At each iteration, I eliminate one more feature. The current set of features is randomly sampled at each iteration. Then during each iteration:
   1. Fit an exact KNN and query from a test set with the current set of features.
   2. Use the current set of features to build a weight vector ('1' for every available feature; '0' for missing features)
   3. Use the weight vector and the modified HNSW to query from the test set with the current set of features.
   4. As comparison: Impute zeros in all missing features and query with HNSW from 'imputed original space'
   5. Accuracy is built via an overlap (order of elements counts) of the exact query and the approximate query using the weights (and the imputed zeros)

I hope you can follow my explanations.

TL;DR It might be usefull to look at the code snippet. From here it should be clear, what I did.

# Approx kNN - fitted with whole feature space
approx_knn = hnswlib.Index(space='l2', dim=dim)
approx_knn.init_index(max_elements=len(X_train), ef_construction=ef, M=M)
approx_knn.add_items(X_train, num_threads=-1)
approx_knn.set_ef(ef)

accuracy_weighting, accuracy_no_weighting = [], []
for d in range(dim):    
    # Disable randomly features
    missing_features = np.random.permutation(dim)[:d]
    available_features = np.setdiff1d(np.arange(dim), missing_features)
    
    ###########
    # Exact kNN - fitted & queried with the current subset of feature
    exact_knn = KNeighborsClassifier(n_neighbors=k).fit(X_train[:, available_features], y_train)
    exact_query = exact_knn.kneighbors(X_test[:, available_features])[1]
    
    ###########
    # HNSWLIB
    weights = np.ones(dim)
    weights[missing_features] = 0  # disable features via 0-weighting
    # Manipulate test data in order to use it with default HNSWLIB & no weighting
    X_test_ = X_test.copy()
    X_test_[:, missing_features] = 0
    # Query data with imputed values (only zeros...) or disabled features
    approx_query = approx_knn.knn_query(X_test_, k=k)[0]
    approx_query_weight = approx_knn.weighted_knn_query(X_test_, weights, k=k)[0]

    accuracy_no_weighting.append(np.mean(exact_query == approx_query))
    accuracy_weighting.append(np.mean(exact_query == approx_query_weight))

[yurymalkov]

@maxstrobel Thank you for a comprehensive explanation!
Looking forward to get a pool request.

[maxstrobel]

@yurymalkov

It turned out that the inclusion of a weighted distance is a little bit tricky.
The problem is that a weigthed distance needs one more parameter for the weights.
The standard distance is defined as:

   template<typename MTYPE>
   using DISTFUNC = MTYPE(*)(const void *, const void *, const void *);

a weighted distance would require:

    template<typename MTYPE>
    using WDISTFUNC = MTYPE(*)(const void *, const void *, const void *, const void *);

Do you have any proposal how this can be integrated in a clean fashion?
In the first run I implemented a parallel branch for the Weighted distances. This means a copy of:

// Standard distance
std::priority_queue<std::pair<dist_t, labeltype >> searchKnn(const void *query_data, size_t k)

// Weighted distance
std::priority_queue<std::pair<dist_t, labeltype >> searchWeightedKnn(const void *query_data, const void *weights, size_t k)


// Standard distance
std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
searchBaseLayerST(tableint ep_id, const void *data_point, size_t ef)

// Weighted distance
std::priority_queue<std::pair<dist_t, tableint>, std::vector<std::pair<dist_t, tableint>>, CompareByFirst>
searchBaseLayerSTWeighted(tableint ep_id, const void *data_point, const void *weights, size_t ef)

This means a lot of replicated code... Spliting up the functions in distance-independent and distance dependent parts seems to be a bad idea, too.

Maybe you have a look at maxstrobel@307b676 to imagine what I have done so far.

I tought too complicated, now I have got a simple solution... Pull request with some first code for reviewing comes soon. It seems to work now and the code looks good. Now I have to touch the processor dependent code.

[maxstrobel]

@yurymalkov @searchivarius
I pushed the first part of the pull request: maxstrobel@f1a95a4 (For which branch should I do a pull request? master?)

The build passes and the python test are also sucessful.
Currently I implemented only the weighted versions of the L2 square. When the code passes your review I would implement also InnerSpace.
btw: Are there some performance issues regarding the duplicated code inside the while-loops inside the CPU optimized functions in the space_l2.h?

I hope the code is acceptable. Feel free to ask if you have some questions.