ABSTRACT
The task of preference
elicitation is characterized by the conflicting goals of eliciting a model as
accurately as possible and asking as few questions of the user as
possible. To reduce the complexity of
elicitation, traditional approaches involve making independence assumptions and
then performing elicitation within the constraints of those assumptions. Inaccurate assumptions can result in
inaccurate elicitation. Ideally, we
would like to make assumptions that approximately apply to a large segment of
the population and correct for inaccuracies in those assumptions when we
encounter an individual to whom they do not apply. We present an approach to encoding of soft assumptions using the
KBANN technique. We show how to encode
assumptions concerning preferential independence and monotonicity as Horn-clauses and how to encode these in a KBANN
network. We empirically compare the
KBANN network with an unbiased ANN in terms of learning rate and accuracy for
preference structures consistent and inconsistent with the domain theory.
Finally, we demonstrate how we can learn a fine-grained preference structure
from simple binary classification data.
Keywords
User
modeling, Product brokering, Neural networks, Decision theory
1. Introduction
Intelligent user interfaces
increasingly require accurate representation of user interests and
preferences. Applications range from
adaptable software and operating systems to Internet-based product brokering. But accurately eliciting a preference model
can be highly time consuming. Thus we
are faced with the conflicting goals of eliciting a preference model as
accurately as possible and asking as few questions of the user as possible.
Representation and
elicitation of preferences have long been studied in Decision Theory. In
Multi-Attribute Utility Theory (Keeyney
& Raiffa 1976) a set of items is typically described in terms of a
set of attributes with an item being a complete assignment of values to all the
attributes. In domains containing no
uncertainty, user preferences over a set of items can be represented by a value
function that assigns a real number to each item, resulting in a total ordering
over the items. Given a set of items
described in terms of a set of attributes {X1, …, Xn} a
function v, which associates a real
number v(x) with each point xÎ X, is said to be a value function representing the decision maker’s preferences
provided that:
(x1’,x2’,..,xn’) ~
(x1’’,x2’’,…,xn’’) Û v(x1’,x2’,..,xn’) =
v(x1’’,x2’’,…,xn’’)
and (x1’,x2’,..,xn’) p (x1’’,x2’’,…,xn’’) Û v(x1’,x2’,..,xn’)
< v(x1’’,x2’’,…,xn’’),
where x' ~ x'' means that the
decision maker is indifferent between two outcomes x’ and x'' and x' p x'' means that the decision maker prefers outcome x'' to outcome x' . When the number of
items is large, eliciting a high-dimensional value function can be impractical,
so practitioners attempt to identify assumptions that permit a value function
to be represented in terms of a combination of lower-dimensional sub-value
functions. The most common assumption is preferential independence. Given a set of attributes {X1, …, Xn} a
subset of attributes Y is preferentially
independent of its complement set Z if and only if the conditional
preferences in the y space given a fixed value z¢ for the attribute set Z does not depend on z¢. The
attributes X1, …, Xn are mutually
preferentially independent if every subset Y is preferentially independent
of its complementary set of attributes. Given a set of attributes {X1, …, Xn}, n³3, an additive
value function v(x1, …, xn) = l1v1(x1) + … + lnvn(xn) exists if and only if the attributes
are mutually preferentially independent.
Elicitation of an additive value function typically proceeds by
determining the sub-value functions vi
and then the scaling constants li. The scaling constants can be interpreted as
representing the tradeoffs between levels of the different attributes, e.g.
cost vs time. In cases of continuous
attributes, a user will often have monotonic preferences over the values of the
attributes, making the sub-value function easy to define. But determining the tradeoff coefficients
can require significant introspection.
As a running example, we will
use the domain of airline flight selection.
Suppose we have a user who wishes to find a flight from Milwaukee to the
San Francisco. We might describe
flights by three attributes: time (T), cost (C), and whether or not there is a
layover involved (L). Time and cost are
continuous, while layover is binary. We
can assume that the user prefers shorter flights, cheaper flights, and flights
without layovers. Thus we need only
assess the tradeoff coefficients that indicate how much the decision making is
willing to trade off the level of one attribute for a more desirable level of
another. A resulting value function
might be v(t,c,l) = 100t + c + 50l.
As we have
outlined the traditional approach to preference elicitation, the decision
analyst (or agent) makes a set of assumptions concerning a decision maker’s
preferences and then performs the elicitation within the constraints of those
assumptions. If the assumptions are
incorrect, the elicited model will be inaccurate. While such assumptions are clearly useful, it would be helpful to
be able to detect and correct errors in our assumptions. In particular, when designing product
brokering systems, we may wish to make assumptions that at least approximately
apply to a large segment of the user population and then correct for
inaccuracies in those assumptions when we encounter an individual to whom they
do not apply. The problem of starting
with an approximately correct domain theory and then correcting and refining it
in the light of data has been studied in the area of theory refinement. In this paper we examine use of one
technique for theory refinement called Knowledge-Based Artificial Neural
Networks (KBANN) (Shavlik & Towell 1989).
We show how assumptions concerning independence and monotonicity of
preferences can be encoded as a KBANN domain theory and how examples of user
preferences can then be used to refine the theory. We empirically compare
elicitation speed and accuracy of a KBANN network containing this domain theory
with a neural network containing no domain theory. We use Ha and Haddawy’s similarity measure on preference
structures (Ha & Haddawy 1998) to define a measure of the degree to which a
preference structure violates the domain theory. We use this to evaluate how well the KBANN network performs as
the preference structure from which the training examples are drawn
increasingly violates the domain theory.
Our results show rather robust and somewhat surprising behavior. Finally, we demonstrate how we can learn a
fine-grained preference structure from simple binary classification data.
2. KBANN
The KBANN technique (Shavlik
& Towell 1989) permits a domain theory expressed as an acyclic set of
propositional Horn-clauses to be encoded in a back-propagation neural
network. The propositions become nodes
and the logical relations between them become links. By training the network on data an incomplete domain theory can
be supplemented and an inaccurate domain theory can be corrected. Given an approximately correct domain
theory, KBANN has been shown to be require fewer examples to correctly classify
a test set than an unbiased network (Towel 90). When using an unbiased network, the weights are initialized
randomly, so that the network starts out in a randomly chosen point in function
space. In contrast, initializing the
network with an approximately correct domain theory starts it at a point that
is close to the target function.
3. Representing Preferences
In deciding how to represent
user preferenes, several alternatives present themselves: discrete numeric
ratings, a simple binary classification into interesting/uninteresting, a value
function, or pairwise preferences among items. We will evaluate these from the standpoint of representational
adequacy, ease of gathering training examples, and ease of expressing and encoding
assumptions concerning preference. Numeric
ratings are the predominant representation used in building recommender
systems. Note that the simple binary
classification is a degenerate case of a numeric rating scheme. Use of numeric ratings requires training
instances to consist of individual items with an associated rating. But notice that numeric ratings have the
disadvantage of fixed granularity.
Either we choose a coarse granularity and cannot make fine distinctions
in preference or we choose a fine granularity and are faced with deciding
exactly what rating to assign to an item.
For example, a rating scheme with only five values can easily have a the
top rating filled with items among which we have strong distinctions of
preference. On the other hand, if we
use, say, 100 rating values then we may very well end assigning ratings that
have little meaning to us, e.g. a 47 vs 48.
The direct use of a value function to represent preference has this
latter problem of deciding exactly what value to assign to an item as
well.
Training examples consisting
of items with numeric scores would require a neural network architecture in
which we have the attributes for one instance as the input nodes and a single
output node that provides the score.
This would the dictate that the assumptions encoded in the form of a
domain theory say something about the relation of the score to the item
attributes. Notice how difficult it
would be to come up with principled statements of that form.
The alternative is to represent a user’s
preferences in terms of pairwise preferences among items. Training instances consist of pairs of items
and an indication of whether the first is preferred to the second. So using pairwise preferences would require
the network to have input nodes for the attributes of two items and a binary
output node that indicated preference or no preference. If two items are input to the network in one
order and then the other and the output indicates no preference for both cases,
then the user is considered to be indifferent between the two items. Notice that with this representation the
domain theory can simply be written to state under what conditions the user
would prefer one item to another.
4.
Encoding the Assumptions and Network Architecture
We can conveniently encode
assumptions concerning preferential independence and monotonicity of preference
through statements of dominance.
Consider our flight domain. It
is plausible that the user prefer cheaper flights to more expensive flights,
shorter flights to longer flights, and flights without layover to those
with. These assumptions can be encoded
with the following set of Horn-clauses:
C1<C2 Ù T1£T2 Ù L1£L2 ® F1fF2
C1£C2 Ù T1<T2 Ù L1£L2 ® F1fF2
C1£C2 Ù T1£T2 Ù L1<L2 ® F1fF2,
where Ci and Ti are the
cost and time of flight i, respectively.
Li is 0 if no layover and 1 otherwise. F1fF2 indicates that flight 1 is preferred to
flight 2. Notice that each of these
sentences indicates that the attribute over which it is expressing
directionality of preference is also preferentially independent of the other
attributes.
To accommodate this domain theory we have
include an extra hidden layer that contains the logic for our comparison
operators. This layer is coded for the
following operators: <,>,<=,>=,=,¹. The layer is
located between the input layer and the initial hidden layer. The tails of the Horn-clauses in the domain
theory are represented in the hidden layer and the heads are represented by the
output node. Figure 1 shows the general
network architecture. While every node at
each layer is connected to every node at the next with low randomly chosen
weights, the Horn-clauses are encoded by setting some weights to high
values. The figure shows the links that
encode the first Horn-clause in the domain theory above. While it would be possible to compute the
comparisons outside the network and include them as separate inputs,
representing them as nodes in the network allows for the possibility that they
can be modified during training. For
example, it might be the case that the user only has preference among two
different costs when they differ by at least some minimal amount. Training could modify the weights to capture
this.
