Objective Function Designing Led by User

Preferences Acquisition
Patrick Taillandier and Julien Gaffuri

Abstract—Many real world problems can be defined as as well as its results. Section 5 concludes and presents the
optimisation problems in which the aim is to maximise an perspectives of this work.
objective function. The quality of obtained solution is
directly linked to the pertinence of the used objective II. CONTEXT
function. However, designing such function, which has to
translate the user needs, is usually fastidious. In this paper, A. Optimisation problem and objective function
a method to help user objective functions designing is Many real world problems can be expressed as optimisation
proposed. Our approach, which is highly interactive, is problems. Solving such a problem consists in finding, among all
based on man-machine dialogue and more particularly on possible solutions of the problems, the one that maximises an
the comparison of problem instance solutions by the user. objective function. This function characterises the quality of a
We propose an experiment in the domain of cartographic solution. Its definition is a key point of the resolution of
generalisation that shows promising results. optimisation problems [19]-[20]. Indeed, the goal of the
resolution of an optimisation problem is to find the solution that
Index Terms—user needs definition, objective function
maximises (or minimises) this function. Thus, if the objective
designing, man-machine dialogue, cartographic
function is not in adequacy with the real quality of a solution, the
generalisation.
solutions that will be found will never be good. Many works
I. INTRODUCTION were interested in the definition of such function for specific
problems [14]-[21] but few proposed general approach for
Artificial systems are more effective than humans to solve
helping the user of an optimisation system to define it.
many problems. One of the reasons is their computing capacity
that allows them to tests many possibilities in a short period of B. Related Works
time. However, in order to get good results, an artificial system The problem of objective function definition and more
has to know what it is searching, i.e. what type of solutions is generally of user need definition is a complex problem which
expected. Unfortunately, while human experts can easily give a was studied in various fields.
qualitative evaluation of the quality of a problem solution or A first approach to solve this problem is to use supervised
order several solutions in terms of quality, it is often far more machine learning techniques. These techniques consist in
difficult for them to express their expectations in a formal way inducing a general model from examples labeled by a
that can be used by artificial systems. This problem is user/expert. In this context, it is possible to learn an objective
particularly complex when numerous measures are used to function from examples evaluated by a user. This approach was
characterise a solution and when no simple links can be found used in several works. For example, [21] used this approach in
between these measures values and the solution quality. the domain of computer vision, [6], in the learning of cognitive
This paper deals with the problem of the formalisation of the radio.
user outcome expectation from the system, into a form usable by A second approach consists in establishing a man-machine
artificial systems. In this context, we propose an approach dialogue to converge toward a formalisation of the user needs.
aiming at translating the user needs into an objective function Reference [5] proposes to use such approach in order to help
thanks to dialogue between the user and the system. users to create original map legends. This work proposed to use
In Section 2, the general context of our work is introduced. map samples to establish a dialogue between the user and the
Section 3 is devoted to the presentation of our approach. Section system. This dialogue allows the system to retrieve the user
4 describes an application of our approach to cartographic preferences, and thus to design a suitable legend that respects
generalisation. We present a real case study that we carried out the user expectations as well as cartographic constraints (to
ensure the map readability). In the same way, [13] proposes to
P. Taillandier is with the UMI UMMISCO of IRD, 209, 32 avenue Henri use map samples to capture user needs in terms of geographic
Varagnat,93143 Bondy, France and with the UMI 209 of IFI, MSI, ngo 42 Ta information. Our work is taking place in the continuity of these
Quang Buu, Ha Noi, Viet Nam (e-mail: [Link]@[Link]).
two works. We propose to use the same approach based on a
J. Gaffuri is with the COGIT lab of IGN , 73 avenue De Paris, 94165
Saint-Mandé, France (e-mail: [Link]@[Link]). dialogue between the user and the system established through
the presentation of samples.

ICITA 2009 ISBN: 978-981-08-3029-8

 III. PROPOSED APPROACH C. Capture of the user preferences
The second step of our approach consists in capturing the
A. General approach
user preferences. Figure 2 presents our approach: at each
As stated in the introduction, if experts often have difficulties iteration, a comparison is selected between all available ones
to express in a formal way their needs from a system, it is far (the comparison set). Then, the user defines its preferences, i.e.
easier for them to compare different solutions of a problem and between the two solutions, the one that he finds better. The user
to point out their preferences. Thus, we propose to base our user can also define that the two solutions are as good or as bad. This
need definition approach on the presentation of comparisons sequence is reiterated until an ending criterion is checked. An
between solutions to the user. Each comparison is composed of example of ending criterion can be to stop the cycle when a
two solutions for a same problem instance. The user can give his specific number of comparisons have been presented to the user.
preferences toward these two solutions to the system, i.e. the
solution that he prefers if there is one. The system then
automatically build the evaluation function from the whole set
of preferences.
Our general approach, presented Figure 1, is composed of 3
steps: the first one consists in generating a set of pairs of
solutions to compare (called “comparisons set”); the second one
consists in capturing the user preferences by asking the user to
select its favourite solution for each comparison; the last step
consists in using these captured preferences to automatically
build the objective function that will represent the user
expectations toward the optimisation system.

Fig. 2. User preference capture approach

The main question of this step concerns the choice of a

comparison to propose to the user at each iteration. How to
choose that comparison? To guide this choice, we propose to
use comparison choice strategies: a comparison choice strategy
allows the choice of the next comparison among a set of
comparisons according to a specific strategy.

In this paper, we propose four different comparison choice

Fig. 1. General approach strategies:
• Measure consistency analysis: this strategy consists in
In the following sections, we described each of these three choosing a comparison where the two solutions are
steps. equivalent in terms of measure values. The goal is to
analyse the consistency of the measure set. If the user
B. Initialisation of the comparison set
prefers one of the two solutions whereas they are
The first step of our approach consists in generating a set of equivalent in terms of measure values, it means that the
comparisons that will be used to capture the user needs. We measure set is not pertinent and does not allow to
defined a comparison as a set of two solutions for a same well-characterised the solution quality.
problem instance. • Measure evolution analysis: this strategy consists in
The generation of the comparison set depends on the context choosing a comparison where the value of only one
of use of our approach. For example, in the case where a set of measure changes between the two solutions. The goal is
instances of the considered problem is available and where this to analyse how the quality of a solution evolves
set is too big to take into account all available instances, a according to the evolution of the value of this measure.
sampling method has to be used in order to select a subset of • Order of preference between two measures: this strategy
problem instances. The subset has to be representative of the consists in choosing a comparison where the values of
whole set in order to capture more pertinently the user only two measures change between the two solutions.
preferences in a generic objective function. The goal is to compare the relative importance of each
Each selected instance has to be solved in order to obtain at measure for the computation of the solution quality.
least two solutions for it. For each couple of solutions, a
• Random comparison: this strategy consists in choosing
comparison is created and is added to the comparison set.
randomly a comparison in the comparison set.
In order to define a global strategy of user preference capture,
we propose to chain different comparison choice strategies. allows to get a better result than the previous one, it is kept;
Indeed, in a first step, we propose to apply the measure otherwise, the system backtracks to the previous objective
consistency analysis strategy in order to check the pertinence of function and end the evaluation function building process. This
the measure set. If this one is not pertinent, the objective partitioning procedure is recursively repeated until the learnt
function obtained at the end of the user need definition process objective function allows to obtain the given user preferences or
will certainly not be perfect. Then, in a second step, we propose until no more improvement of the objective function is
to apply the measure evolution analysis strategy for each obtained.
measure. This step allows a better understanding of the link
existing between the evolution of a measure and the evolution of
the solution quality. The third step consists in applying the order
of preference between two measures strategy to compare by
couple the relative importance of each measure. In the last step,
we propose to apply he random comparison strategy.
D. Definition of the objective function
The last step of our approach consists in designing an
objective function from the user preferences.
We propose to formulate the objective function as a set of
regression rules. Each regression rule is associated to a
weighted means. The interest of such representation is to be
easily interpretable by domain experts and thus to facilitate the
objective function validation.
Let M be the set of measures, wi the weight associated to the
measure i and Vali(sol), the value of the measure i for the Fig. 3. Approach of evaluation function building
solution sol belonging to the whole possible solution set SOL.
We define the measures of M such as: 1) Search of the best weight assignment
∀sol ∈ SOL, ∀i ∈ M , VAL _ MIN ≤ vali (sol ) ≤ VAL _ MAX
We propose to formulate the problem of best weight
assignment as a minimisation problem. We define a global error
with VAL_MIN and VAL_MAX real.
function that represents the inadequacy between the evaluation
function (and thus the weight assignment) and the user
Each regression rule is defined as follows:
preferences. The goal of the best weight assignment search is to
1
if condition then quality ( sol ) = × ∑ wi × Val i ( sol ) find the weights that allow to minimise the global error function.
∑ wi i∈M
i∈M
Let fobj(sol) be the current objective function that evaluates
An Example of objective function is presented in Section
the quality of a solution sol.
IV.E.3.
Let csol1,sol2 be a comparison between two solutions, sol1 and
sol2.
Building an objective function consists in finding a set of
Let pc be the user preference for the comparison c. pc can be
regression rules (with, for each of them, a condition and the
either {sol1} (the user prefers the solution sol1), {sol2} (the user
weight values) from the preferences given by the users on the
prefers the solution sol2) or {sol1, sol2} (the two solutions have
samples. As presented Figure 3, to solve this problem, we
the same quality for the user).
propose to use an approach based on the search of the best
weights and eventually on the partitioning of the measures set
We define the function comp(c, fobj, pc) that determines for a
(which correspond to the addition of new regression rules).
comparison c if the user preference pc is compatible with the
At the initial stage, the objective function is composed of only
objective function fobj, i.e. if the preference formulated by the
one regression rule, such as the measure space is composed of
user is consistent with the quality order obtained by applying the
only one partition. At the first step, the system searches a weight
objective function on the solutions. If the user preference pc is
assignment that maximises the adequacy between the objective
compatible with the objective function fobj for the comparison c,
function and the user preferences. If this weight assignment is in
comp(c, fobj, pc) is equal to 0; otherwise it is equal to 1.
total adequacy with the user preferences, the process ends; the
  pc = {sol1 , sol2 } and f obj ( sol1 ) = f obj (sol2 )
objective function is composed of only one regression rule.  
Otherwise, new regression rules are introduced: the system 0 if  or pc = {sol1} and f obj ( sol1 ) > f obj (sol2 )
 or p = {sol } and f obj ( sol2 ) > f obj ( sol1 )
computes partitions of the measure set in order to detect the   c 2
comp(c, f obj , pc ) = 
parts of the measure set that are not compatible with the others. 1 otherwise
Then, a new weight assignment is searched again for all 

regression rules, by considering all partitions built at the same 
time. If the weight assignment obtained after the partitioning 
 We define the function error(c, fobj, pc) that returns the error
value for a comparison c. This function is defined as:
 0 if comp(c, f obj , pc ) = 0

error (c, f obj , pc ) = 
val
 error + f obj ( sol1 ) − f obj ( sol2 ) if comp(c, f obj , pc ) = 1

In this function, we integrated a parameter valerror that

represents the minimum importance of an error whatever the
values of the objective function for the two solutions are. The
higher the value of this parameter, the more important it will be
to minimise the number of incompatible comparisons.
Fig. 4. Partitioning method
Finally, the global error function proposed corresponds to the
Once the partitioning is carried out, the user need definition
mean error obtained with the objective function fobj on the
module performs a new search of the best weights assignment.
comparison sample Comp:
All partitions are considered at the same time for this search. If
1
Error ( f obj , Comp ) = × ∑ error (c, f obj , p c ) the weights assignment found is better (in terms of minimisation
Comp c∈Comp
of the global error value) than the assignment obtained before
The aims of the weight assignment step is to find a weight the partitioning, the new objective function is kept. Otherwise,
assignment that minimises Error(fobj, Comp). The size of the the module keeps the previously obtained objective function.
search space will be most of time too high to carry out a
complete search. Thus, it will be necessary to proceed by IV. APPLICATION TO CARTOGRAPHIC
incomplete search. In this context, we propose to use a GENERALISATION
metaheuristic to find the best weight assignment. In the
A. Automatic cartographic generalisation
literature, numerous metaheuristics were introduced
[8]-[11]-[15]. In this paper, we propose to use genetic We propose to test our objective function designing approach
algorithms [12] which are particularly effective when the search in the domain of cartographic generalisation. Cartographic
space is well-structured as it is in our search problem. generalisation is the process that aims at simplifying geographic
data to suit the scale and purpose of a map. The objective of this
2) Partitioning of the measure space process is to ensure the readability of the map while keeping the
For some user need definition problems, it will not be essential information of the initial data. Figure 5 gives an
possible to find a weight assignment compatible with all user example of cartographic generalisation.
preferences. Thus, we propose to partition the measure set space
and to define for each partition a regression rule with its own
weight assignment.
We propose to base our partitioning method on the utilisation
of supervised learning techniques. The goal is to search the parts
of the measure space that have a different behaviour in terms of
objective function. Thus, we search to detect the parts of the
measure space which contain solutions linked to an Fig. 5. Cartographic Generalisation
incompatible comparison.
We built an example set composed of solutions described by The automation of the generalisation process is an interesting
its measures values. The conclusion could be either industrial application context which is far from being solved.
“compatible” if the comparison which contains the solution is Moreover, it directly interests the mapping agencies that wish to
compatible with the objective function or “incompatible” if it is improve their map production lines. At last, the multiplication
not. Then, a supervised learning algorithm is used to partition of web sites allowing creating one’s own map increases the
the measure space. We remind that we proposed to express the needs of reliable and effective automatic generalisation
partition in the form of rules. Thus, it is necessary to use a processes.
supervised learning algorithm that allows to build a predictive One classical approach to automate the generalisation
model expressed by rules. Different algorithms could be used process is to use a local, step-by-step and knowledge-based
for this partitioning problem such as RIDOR [10] or C4.5 method [4]: each vector object of the database (representing a
algorithm [16]. In this paper, we propose to use the effective and building, a road segment, etc.) is transformed by application of a
well-established RIPPER algorithm [7]. sequence of generalisation algorithms realising atomic
Figure 4 presents an example of partitioning for a measure set transformations. The choice of the applied sequence algorithms
composed of two measures. is not predetermined but built on the fly for each object
according to heuristics and to its characteristics.
 B. The generalisation system D. Implementation of our approach for the AGENT model
The generalisation system that we use for our experiment is We experiment our approach on an implementation of our
based on the AGENT model [3]-[17]. The AGENT model has user need definition module in Java, using GéOxygene [2] for
been further described in [18]. geographical data transformation, and WEKA [22] for the
In this model, geographic objects (roads, buildings, etc) are partitioning part using RIPPER algorithm.
modelled as agents. Geographic agents manage their own Figure 7 presents our implemented interface. On the top
generalisation, choosing and applying generalisation operations panel, the initial state for a building is presented to the user,
to themselves. Each state of the agent represents the geometric with, under, the two possible solutions. The user gives its
state of the considered geographic objects. preference for this sample.
During its generalisation process, each agent is guided by a
set of constraints that represents the specifications of the desired
cartographic product. An example of constraint is, for a building
agent, to be big enough to be readable. Each constraint has a
satisfaction level between 0 (constraint not satisfy at all) and
100 (constraint perfectly satisfy). For each state, the agent
computes its own satisfaction according to the values of its
constraint satisfaction.
To satisfy its constraints as well as possible, a geographical
agent carries out a cycle of actions during which it tests different
actions in order to reach a perfect state (where all of its
constraints are perfectly satisfied) or at least the best possible
state. The action cycle results in an informed exploration of a
state tree. Each state represents the geometric state of the
considered geographic objects. Figure 6 gives an example of a Fig. 7. Implemented graphic interface
state tree obtained with the generalisation system.
E. Case study
1) Setting of the case study
We propose to apply our user need definition approach for
the learning of the satisfaction function of the generalisation of
building agents for 1:25000 scaled maps.

We defined six constraints for the building agents:

• Size constraint: the building shape should be big enough.
Let Ssz be the value of this constraint satisfaction.
• Granularity constraint: the building shape should not
contain too small details. Let Sgr be the value of this
Fig. 6. Example of a state tree for the generalisation of a
constraint satisfaction.
building
• Squareness constraint: the angles of the building that are
nearly square should be square. Let Ssq be the value of
C. Difficulties of the agent satisfaction function definition this constraint satisfaction.
The AGENT model has been the core of numerous research • Convexity constraint: the convexity of the building should
works and is used for map production in several mapping be preserved. Let Scv be the value of this constraint
agencies. However, the question of the evaluation of the state of satisfaction
an agent is still asked. The function usually used is a mean of the • Elongation constraint: the elongation of the building
constraint satisfaction weighted by their importance (which is should be preserved. Let Sel be the value of this
often an integer ranged between 1 and 10). The problem of this constraint satisfaction
function is to give satisfaction values too homogenous. More • Orientation constraint: the orientation of the building
over, it does not allow to take into account discontinuities in the should be preserved. Let Sor be the value of this
satisfaction function. At last, the definition of the importance constraint satisfaction
values is often complex and fastidious when more than five
constraints are in stake [2]. Thus, having an approach like the 2) Experiment protocol
one described in this paper allowing to design the agent 50 comparisons (the learning set) were presented to a
satisfaction function is particularly interesting in the context of generalisation expert to learn an objective function. Then, we
the AGENT model. tested the learnt objective function on 50 new comparisons (the
test set) which were selected in a new area and for which the
expert expressed its preferences. Concerning the exploration part as well as the partitioning
The value used for valerror (cf. Section III.D.1) is 40. This part, we just tested one search algorithm and one supervised
value is high enough to limit the number of incompatible learning algorithm. An interesting study could be to test others
comparisons and, at the same time, not too high in order to take algorithms and to compare the results with the ones obtained.
into account the difference of values of the objective function A last perspective could be to pass from an acquisition
value in case of errors. Thus, in our application context, the problem to a revision problem. Indeed, it could be interesting to
value of the global error is ranged between 0 and 140. take into account an initial objective function and to refine it
rather than learning a new one from scratch.
3) Results
The learnt objective function (with S, the satisfaction of the REFERENCES
building agent) is the following: [1] T. Badard and A. Braun, OXYGENE: An open framework for the
 1 deployment of geographic web services. Im proceedings of the 21st
if ( S cv < 83) ⇒ S = 28 (6 × S cv + 2 × S el + 9 × S sq + 2 × S gr + 2 × S or + 7 × S sz ) International Cartographic Conference (ACI/ICA), Durban, South Africa,
 1 August 10-16, 2003, pp 994-1004.
 if (83 ≤ Scv < 93) ⇒ S = (7 × Scv + 7 × Sel + 1 × S sq + 7 × S gr + 6 × S sz ) [2] S. Bard, Quality Assessment of Cartographic Generalisation,
 28
1 Transactions in GIS, 8, 2004, pp. 63-81.
 if ( S cv > 93) ⇒ S = (9 × S cv + 9 × S el + 3 × S sq + 2 × S gr + 7 × S sz )
 30 [3] M. Barrault, N. Regnauld, C. Duchêne, K. Haire, C. Baejis, Y.
Demazeau, P. Hardy, W. Mackaness, A. Ruas and R. Weibel, Integrating
multi-agent, object-oriented, and algorithmic techniques for improved
Table 1 presents the results obtained on the two comparison automated map generalization. In ICC, 2001.
sets. The learnt objective function allowed to get, for both [4] K. Brassel and R. Weibel, A review and conceptual framework of
automated map generalization. IJGIS, 1988.
comparison sets, a global error value lower than 5 and a number
[5] S. Christophe, Creative Cartography based on Dialogue, in 'In
of incompatible comparisons equals to 5. proceedings of AutoCarto', Shepherdstown, West Virginia, 2008.
[6] C. Clancy, J. Hecker, E. Stuntebeck, T. O'Shea, Applications of Machine
Nb of incompatible comparisons Global error Learning to Cognitive Radio Networks, Wireless Communications,
IEEE, vol. 14, no. 4, August 2007, pp. 47-52.
Learning set 5 4.25 [7] W. Cohen, Fast effective rule induction, in Proc. (ICML-95), 1995, pp.
Test set 5 4.63 115—123.
[8] M. Dorigo and T. Stützle, Ant Colony Optimization, MIT Press, 2004.
Table 1. Results of the learnt objective function on the learning [9] J. Gaffuri and J. Trévisan, Role of urban patterns for building
set and on the test set. generalisation: An application of AGENT, in 'Workshop on
Generalisation and Multiple representation', United Kingdom, 2004.
These results show that our approach allowed to learn a [10] B.R. Gaines and P. Compton, Induction of Ripple-Down Rules Applied
to Modeling Large Databases. Journal of Intelligent Information Systems
pertinent objective function. Indeed, the results obtained by the 5(3), 1995, pp. 211--228.
learnt function are both good on the learning set and on the test [11] F. Glover, Tabu search. Journal on Computing, 1989.
set. For both comparison sets, the global error value is very low [12] J.H. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor:
and only 5 of the 50 comparisons are incompatible. Among University of Michigan Press, 1975.
these incompatible comparisons, several can be explained by [13] F. Hubert and A. Ruas, A method based on samples to capture user needs
for generalisation, in 'fifth workshop on progress in automated map
the lack of pertinent measures used to describe the generalisation', Paris, 2003.
generalisation results. Indeed, the Measure consistency analysis [14] S. Kakade, Y. W. Teh, and S. Roweis. An alternative objective function
comparison choice strategy allowed us to detect that, for some for Markovian fields. In Proc. 19th ICML, 2002.
comparisons, two states can be identical in terms of constraint [15] S. Kirkpatrick, C. Gellatt, and M.P. Vecchi, 'Optimization by Simulated
Annealing', Science 220, 1983, pp.671--680.
satisfactions but different in terms of generalisation quality.
[16] J. Quinlan, C4.5: programs for machine learning, Morgan Kaufmann
Publishers Inc, 1993.
V. CONCLUSION [17] A. Ruas, Modèle de généralisation de données géographiques à base de
In this paper, we presented an approach dedicated to the contraintes et d’autonomie. Thèse de l’UMLV, 1999.
[18] A. Ruas, and C. Duchêne, A Prototype Generalisation System Based on
definition of user needs. Thus, we proposed an approach based the Multi-Agent Paradigm. Generalisation of Geographic Information:
on a man-machine dialogue aiming at defining an objective Cartographic Modelling and Applications, 2007.
function representing the user expectations toward an [19] S. Russel and P. Norvig, informed search and exploration, chapter 4 of
optimisation system. An experiment, carried out in the domain artificial intelligence, a modern approach, second edition, Pearson
education, 1995
of cartographic generalisation, showed that our approach can [20] P. Taillandier, C. Duchêne and A. Drogoul, Knowledge revision in
help users to formalise their needs and can allow to detect lacks systems based on an informed tree search strategy: application to
of pertinent measures. cartographic generalisation, in CSTST. 2008, pp. 273--278.
Our approach is based on the utilisation of comparison [21] M. Wimmer, F. Stulp, S. Pietzsch, and B. Radig. Learning local objective
functions for robust face model fitting. IEEE Transactions on Pattern
choosing strategies. In this paper, we defined four different Analysis andMachine Intelligence (PAMI), 30(8), 2008
strategies. Other strategies, more complex, could be proposed, [22] I.H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools
such as strategies that take more into account the preferences and Techniques (San Francisco, CA: Morgan Kaufmann), 2nd edition.
2005.
initially formalised by the user.