Project Title: Unstructuring User Preferences: Efficient Non-Parametric Utility Revelation

Researchers: Alex Cheng, Thorsten Joachims (Advisor)

Overview:

• A decision support system that allows user to input preference statements returns a set of results from the database in a ranking that is consistent with the input.
• Base on research by Carmel Domshlak (IIT) and Thorsten Joachim (Cornell)

Motivation:

• Existing methods of utilizing user preference statements for creating a ranking imposes a structure on the type of preference statements allowed. They only works if the preference statements fits a certain structure and under certain conditions (example, CP-net)

Approach:

• Combines mixture of techniques from knowledge representation (boolean vectors to represent user preferences) and machine learning (Support Vector Machine)
• Approach is semantically sound and computational efficient in its theoretical analysis and small initial experiments
• Goal of this project is implement a scalable experimental system that will enable us to conduct further research

System Architecture:

Running Example:

We can represent each car by a Boolean vector. An entry is 1 if that attribute is present in the car and 0 otherwise. The vector of attributes is [Auto, Manual, Blue, Red, Green, SUV, Convertible: x = [

Users can input two types of preferences statements:

1. Complete Alternatives (I prefer CarA to CarB)
2. Partial Alternatives (I prefer Blue Convertibles over Red cars) [note: preferences do not have to be specifically applied to any car in the database]

We will use preference statement two as our example:

I prefer Blue Convertibles over Red cars:

Let be the proposition: Blue Convertibles and be the proposition: Red

Then is a preference statement which states that the user prefer over

Given a set of n preference statements, one way we can represent and interpret the information about the user’s preference is with the use of an ordinal utility function where X is the domain of the attribute vectors.

╞

Intuitively, the ordinal utility function will return a higher value for x than x’ if the user prefer x over x’.

• We convert the user preference into a boolean vectors, and map into a higher dimension by combining features.
• We can create a mapping in such a way that is semantically appealing for representing preference statements

The vector presentation for the preference statement : I prefer Blue Convertibles over Red cars would be:

: [?,?,1,0,0,0,1] and : [?,?,0,1,0,?,?] where the ? indicates the attribute that we do not concern with.

Let be the valuation of , that is and

We want to create a mapping where F is the power set of

So for example,

and similarly for

This representation is appealing because it captures the combinations of all the attributes, and thus, the next step would be to assign weights to each element in F.

We then define the our utility function as follows:

and we want to find the weights w such that

╞

is satisfied.

Which means, we want

Problem: solving the set of equations for find w will take exponential time:

Solution: We can use Support Vector Machines which can learn w, given the set of preferences as rankings and can solve the problem in quadratic time.

After we find w we can use U to find a numeric value associate with each car and re-rank the database based on the preference statements.

Future work:

• Active Learning: system asking user preference questions.
• Implementing support for all logical operators (in propositional logic) for inputting user preference.
• The effect of dimensionality on accuracy.

Reference:

Carmel Domshlak, Thorsten Joachims Unstructuring User Preferences: Efficient Non-Parametric Utility Revelation, 2005 (To be published)