2

I have a solid user-item matrix, with which I have build a collaborative filtering recommender system. I also have for each item a number of high quality features.

If a new user comes to the website (online store), I quickly want to find out his taste. Currently I do this by asking 20 questions, in which I ask him to select his most preferred product out of 4 options.

How can you use the item features and the information in the user-item matrix (and it derivaties: product popularities and latent features) to set up an efficient questionnaire to get to know the user his taste?

For example, you want to find out if the user likes popular products. So in each question with 4 options, you want to make sure there is one popular product in it, and one non popular product. But there are many features, and I am looking for a method that makes sure there is as much variation as possible in all the questions, so you learn as fast as possible.

My question is inspired by the implementation of the game 20 questions, http://www.20q.com, where you also want to ask the question that eliminates to most of the potential concepts that the user can have in mind.

Can you guide me towards some concepts or solutions?

Zhubarb
  • 8,269
Kasper
  • 3,399

2 Answers2

2

You are interested in adaptive testing. In adaptive testing scenario after answering each item from the test, the next item to be presented is choosen based on the ability of examinee as estimated based on previous items. As you can see, this is a educational/testing scenario, but the main ideas probably can be adapted to other settings as well. This kind of testing needs pretty complicated statistical methods based on Item Response Theory, so you would need to read more about those methods (disclaimer: I never worked with adaptive testing data myself). Since IRT models are very flexible by design, you can possibly easily adapt them to different scenarios.

Tim
  • 138,066
  • 1
    Unfortunately, it would be way to heavy on the back end to optimize the next question given the previous answers. I pre-calculate a set of 20 questions beforehand, so that the website stays super fast. – Kasper Nov 08 '17 at 14:01
  • 1
    @Kasper I didn't say you need to go one question at a time. – Tim Nov 08 '17 at 14:05
2

You can make use of popular algorithms in two steps:

  1. Partition the space of user tastes into mutually exclusive classes. You can do it fully authomatically (e.g. do k-means clustering on the latent features), or first split the users into large meaningful classes by hand and then divide each one into subclasters by an algorithm.
  2. Train a decision tree on raw like/dislike data to predict these classes. Most of this data, however, would be missing. But you can use a matrix factorization algorithm (or any other appropriate model) to infer the unknown values from the known ones before building the tree. There would be some users who rated/used too few items, so this inference would be poor for them. But you may just exclude such users from this model, because they add no information anyway.

Voila! You have the perfect questioning strategy! By design, it discriminates different tastes as fast as possible. For a new user, you just go down the decision tree asking questions "how do you like item X?", where X is the feauture used in the current node in the tree.

If the number of latent features is not too large, you can do even simpler: just train your decision tree regressor to predict all these latent features simultaneously, in a multi-output mode (scikit-learn trees certainly can do this). In this case, you don't even have to puzzle over clustering strategy, because you predict the latent features themselves instead of clusters.

David Dale
  • 2,301
  • Do I understand you correctly:
    1. First we use the latent features of the previous users to cluster users
    2. We build a decision tree model to see if we can predict the cluster the user belongs to based on his feedback on the items

    Here I see a first problem, not every user gave feedback on every item. So the decision tree model has to deal with missing values

    But then I don't understand how you get a questioning strategy from this decision tree model.

    And the last paragraph I also don't understand. Can you elaborate a bit further?

    Thank you

     – Kasper Nov 08 '17 at 14:14
  • @Kasper, yes, you understood me correctly. As for missing values and the last paragraph, I have clarified it in the answer. – David Dale Nov 08 '17 at 14:45
  • Ok thanks. But I am not seeing your Voila! step :) – Kasper Nov 08 '17 at 14:56
  • Voila is not a step :) It's just the fact that the tree is ready to use and, in some sense, optimal. – David Dale Nov 08 '17 at 15:28
  • I don't see how I can use that tree to set up a questionnaire strategy. I see that the tree allows me to predict to which class a user belongs given his feedback on the names. But how do I turn this around so that I can select which items to put in each question? – Kasper Nov 08 '17 at 15:36
  • The tree itself consists of questions. Each node of the tree is already a question "do you like the item i?" (actually, it's a feature on which the tree has been trained). You need only to extract these questions by traversing the tree. Different users will get different questions, but all sequences of questions are already coded into the tree, so you can built them into your site efficiently. And the total number of the questions asked to a single user equals the depth of this tree - 20, in your case. – David Dale Jan 04 '20 at 17:24