Sort items in an autocomplete by estimated probability of selection

Question

I'm trying to sort places in an autocomplete by the probability that the user wants to select them, given their context, which mostly consists of their current location, time and history (previous selections). So the goal is to estimate the following probability:

$P(user\ wants\ to\ select\ this\ place\ |\ context,\ place)$

The autocomplete displays a list of places filtered by the entered text and sorted by the predicted probability. So if the user entered "ab", only places starting with "ab" are shown.

The main metric I'm trying to optimize is how many keystrokes are required (on average) until the desired place bubbles up to the first position in the list. Correctly predicting the above probability should be enough to maximize this.

The input dataset consists of 500,000 selections (or searches) and for each of them the context and the chosen place are known. There are 50,000 items in the autocomplete.

One approach is to use a logistic regression to predict whether a place was selected given the context. So for every search and every place, there would be a training example with features derived from the combination of the context and the place, such as:

• distance from current location to the place
• whether the place was used before

The training examples could have this form:

$[distance,\ used\ before] \to [0\ or\ 1]$

Unfortunately, the resulting dataset would be huge (25,000,000,000) and imbalanced (1:49,999). I tried using only one randomly selected negative example for every search, which shrinks and balances the dataset, but it didn't work very well. Taking more negative examples per search while using less searches improved the performance

Directly optimizing the metric (using a black-box optimization algorithm) works quite well but it's slow and I'm not confident it finds the best solution. Thousands or tens of thousands searches were enough for a good fit.

What are some other things I should try? Is the logistic regression approach theoretically ok?

Note: prediction must be very fast so I can't use methods such as k-NN.

Answer 1

For this particular task you might want to look into Bloom filters and work it out from there perhaps using an ensemble technique.

I believe this is the element that you are missing for efficiency.

Check out this page that has a demo, the math is here.