“Meet a GERAD researcher!” seminar

Title: How does the web know our preferences ?

Speaker: Alain Hertz – Professeur titulaire, Département de mathématiques et de génie industriel, Polytechnique Montréal, Canada

We have all experimented recommender systems on the web, whether it’s for choosing a movie, a book, a restaurant, or a holiday destination. Roughly speaking, a recommender system is a platform that seeks to predict the rating or preference that a user would give to an item.

More formally, consider a set I of items and a set A of Boolean attributes. A Boolean vector with |A| components can be associated with every item so that the j-th component equals 1 if and only if the j-th attribute in A is true for that item. For example, if I is a set of restaurants and the first attribute is “vegetarian”, then the first component of the vector associated with a given restaurant equals 1 if and only if  it offers vegetarian food.

Consider now a set U of users. A Boolean vector with |A| components can also be associated with every user so that the j-th component equals 1 if and only if the user has interest for the j-th attribute. In our example, the first component of the vector associated with a user equals 1 if and only if the considered user has interest for vegetarian food. While these vectors associated to users are not known, we aim to predict them, which then makes it possible to recommend to each user all items which correspond to his interests.

A subset W of vertices in a graph is called a resolving set if every vertex in the graph is uniquely determined by its distances to the vertices of W. We show in this talk that resolving sets in the hypercube of dimension |A| make it possible to differentiate between any two users with distinct preferences. Moreover, we describe a procedure that generates resolving sets of small size. For example, for 20 attributes (which allows the classification of the items in more than one million categories), we have produced resolving sets with 12 items, and it is therefore sufficient to know 12 specific ratings of a user to predict his preferences  among more than  one million item types.

---

Coffee and biscuits will be offered at the beginning of the seminar.
Welcome to everyone!