Abstract

Preference-based decision problems often involve choosing one among a large set of options, making common tasks like buying a car or a domestic appliance very challenging for a customer to handle on her own. This is especially true when buying online, where the amount of available options is humongous, and expert advice is yet limited. Recommender systems have become essential computational tools for aiding users in this endeavor. Recommender systems represent one of the most successful applications of artificial intelligence. In the last decades, several recommendation approaches have been proposed for different types of applications, from assisted browsing of product catalogs to personalization of results in search engines. Depending on the application, the job of the recommender system may be to recommend a satisfying option for the given context, as in finding the next best song to play, as opposed to helping the user in finding an optimal instance, e.g. when looking for an apartment. The former is generally handled by data-driven approaches, such as collaborative filtering and contextual bandits, while in the latter case data is usually scarce, making it necessary to employ specialized algorithms for preference elicitation. Preference elicitation algorithms interactively build a utility model of the user preferences and then recommend the instances with the highest utility. Preference elicitation is especially effective when recommending infrequently purchased items, such as professional work tools, electronic devices and other products that can be explicitly stored e.g. in the database of an e-commerce website. Standard preference elicitation algorithms, however, struggle when the options are so numerous that cannot even be explicitly enumerated, and instead need to be represented implicitly as a collection of variables and constraints. Indeed, when a customer wants to configure a product by putting several components together, e.g. for a custom personal computer, the option space is combinatorial and grows exponentially with the number of components, making it impractical to store every single feasible combination explicitly. This is an example of constructive decision problem, in which an object has to be synthesized on the basis of the preferences of the customer and the constraints over the configuration domain. Constructive problems such as product configuration have traditionally been addressed by specialized configurator systems, which guide the user through the configuration process component by component and check whether the user choices are consistent with the set of feasibility constraints. Over the years, however, the limitations of product configurators for mass customization have become apparent. With the growing scale of configuration problems, product configurators have become more difficult for non-experts to use and ultimately do not provide relief against the "mass confusion" caused by the sheer amount of choice. Research in this field has progressively been integrating recommendation technologies into configuration systems, in order to make them more flexible and easy to use. Preference elicitation in product configuration has been attempted as well but still remains a challenge. We propose a generic framework for preference elicitation in constructive domains, that is able to scale to large combinatorial problems better than existing techniques. Our constructive preference elicitation framework is based on online structured prediction, a machine learning technique that deals with sequential decision problems over structured objects. By combining online structured prediction and state-of-the-art constraint solvers we can efficiently learn user utility models and make increasingly better recommendations for complex preference-based constructive problems such as product configuration. In particular, we favor the use of coactive learning, an online structured prediction framework for preference learning. Coactive learning is particularly well suited for constructive preference elicitation as it may be seen as a cooperation between the user and the system. The user and the systems interact through "coactive" feedback: after each recommendation, the user provides a modification that makes it slightly better for her preferences. This type of feedback is very flexible and can be acquired both explicitly and implicitly from the user actions. Coactive learning also comes with theoretical convergence guarantees and a set of ready-made extensions for many related problems such as learning in a multi-user setting and learning with approximate constraint solvers. In this thesis we detail our coactive learning approach to constructive preference elicitation, and propose extensions for scaling up to very large constructive problems and personalizing the utility model. We also applied our framework to two important classes of constructive preference elicitation problems, namely layout synthesis and product bundling. The former is a design process for arranging objects into a given space, while the latter is a kind of product configuration problem in which the object to configure is a package of different products and services. Within the product bundling application, we also performed an extensive validation involving real participants, which highlights the practical benefits of our approach.