05824077

b

05824077 Kaci, Souhila Working with preferences. Less is more. Cognitive Technologies. Berlin: Springer (ISBN 978-3-642-17279-3/hbk; 978-3-642-17280-9/ebook). xvi, 202~p. EUR~79.95/net; SFR~115.00; \sterling~72.00; \$~99.00 (2011). 2011 Berlin: Springer EN preferences comparative and quantitative statements propositional logic possibilistic logic penalty logic discrimin and lexicographic orderings strong semantics optimistic semantics pessimistic semantics opportunistic semantics ceteris paribus semantics bipolar preferences

doi:10.1007/978-3-642-17280-9

Preferences are expressed in the form of statements which can be comparative (e.g., ``I like London more than Paris''), quantitative (e.g., ``I like Berlin with weight .7''), or qualitative (e.g., ``I really like Amsterdam''). The book provides the reader with a comprehensive overview of the various frameworks that develop formal languages to express comparative and quantitative statements of this kind, and methods to rank the set of models of such statements, with models ranked higher being preferred to models ranked lower. After the introductory chapter, Chapter 2 provides the basic background on partial pre-order relations. Chapter 3 is the longest and richest chapter of the book. It discusses in particular many frameworks based on extensions of propositional logic. The first class of frameworks deals with quantitative statements. 1) Penalty logic. A weight $a$, that is, a nonnegative number, is assigned to a propositional formula $\phi$, such as $ {fish}\wedge {white}$, to express how important it is to satisfy $\phi$. A structure $\omega$, taken from a set $\Omega$ of propositional structures constrained in particular ways, for instance, to satisfy ${fish}\leftrightarrow\neg{meat}$ and ${white}\leftrightarrow\neg {red}$, receives no penalty (that is, a penalty of 0) if it makes $\phi$ true, and a penalty of $a$ otherwise. Given a set $X$ of weighted formulas, $\omega$ receives as overall penalty the sum of all penalties over the members of $X$, which determines a total pre-order on $\Omega$. A variant changes the penalty to take into account how far $\omega$ is to a structure that makes $\phi$ true; for instance, the structure that makes both ${fish}$ and ${white}$ false would incur a penalty of $2a$, whereas a structure that would make only one of ${fish}$ and ${white}$ false would incur a penalty of $a$. 2) Possibilistic logic. It is like penalty logic except that weights take values in $[0,1]$, the penalty of not satisfying $\phi$ is $1-a$, so a weight of 1 corresponds to no penalty, and the penalty associated with a set $X$ of formulas is the minimum of penalties over the members of $X$. 3) Discrimin and lexicographic orderings. With weights interpreted as in possibilistic logic, a structure $\omega$ is preferred to (is greater than) a structure $\omega'$ if there exists $\beta$ such that $\omega$ falsifies fewer formulas associated with a penalty of $\beta$ than $\omega'$, but as many formulas associated with a penalty of $\alpha$ for all $\alpha>\beta$, where ``fewer'' and ``as many'' are interpreted either in terms of set inclusion or in terms of set cardinality. 4) Guaranteed possibilistic logic. It is like possibilistic logic, except that the weights represent the degree of satisfaction to satisfy a formula, with larger values corresponding to larger satisfaction, and the degree of satisfaction associated with a set $X$ of formulas is the maximum of the degrees of satisfaction over the members of $X$. 5) Qualitative choice logic. The language is generalised with formulas of the form $\phi\widehat{\times}\psi$ to express that $\phi$ should be preferred but if it does not hold then $\psi$ should be preferred, together with a preference relation that generalises one of the former ones. The second class of frameworks deals with qualitative statements, represented as $p>q$ to express that $p$ is preferred to $q$. Given a preference relation, denoted $\preceq$, defined on $\Omega$, five semantics determine whether $p>q$: I. Strong semantics: Any $p\wedge\neg q$ model is $\preceq$-preferred to any $q\wedge\neg p$ model. II. Ceteris paribus semantics: Any $p\wedge\neg q$ model is $\preceq$-preferred to any $q\wedge\neg p$ model having the same valuation as the former on variables that occur neither in $p$ nor in $q$. III. Optimistic semantics: Any $\preceq$-best model of $p\wedge\neg q$ is $\preceq$-preferred to any $\preceq$-best model of $q\wedge\neg p$. IV. Pessimistic semantics: Any $\preceq$-worst model of $p\wedge\neg q$ is $\preceq$-preferred to any $\preceq$-worst model of $q\wedge\neg p$. V. Opportunistic semantics: Any $\preceq$-best model of $p\wedge\neg q$ is $\preceq$-preferred to any $\preceq$-worst model of $q\wedge\neg p$. Algorithmic procedures are described that produce for strong and ceteris paribus semantics a least and a most specific total pre-order on $\Omega$, respectively (a total pre-order $\preceq_1$ is less specific than a total pre-order $\preceq_2$ if every structure is ranked at least as high w.r.t.\ $\preceq_1$ as w.r.t.\ $\preceq_2$). Similarly, algorithmic procedures are described that produce for optimistic and pessimistic semantics a least and a most specific total pre-order on $\Omega$, respectively. Relationships between those semantics or combinations of those semantics (where relationships of the form $p>q$ are respective to one or the other of some of the previous semantics) are stated and other algorithmic procedures are given to complete particular orders on $\Omega$. Then the notions of ``mutual preferential independence'' and of ``generalised additive independence'' among (propositional) variables are reminded, allowing one to simplify the computation of the utility of a member of $\Omega$ from the utility of the values of single variables or the values of variables in specific sets called factors, respectively. Generalised additive independence networks are presented as graphical languages that capture the structure of generalised additive independent utility functions. Conditional independence networks are introduced based on a qualitative counterpart to generalised additive independence. Together with ceteris paribus semantics, they are associated with a unique partial order on $\Omega$. Variations on those networks are considered. The chapter ends with a discussion of bipolar preferences, where a user expresses both what she considers more or less unacceptable (negative preferences), along the lines of possibilistic logic, and what she considers to be more or less satisfactory (positive preferences), along the lines of guaranteed possibilistic logic. Chapter 4 introduces some bridges between some of the formalisms introduced in Chapter 3. The nontechnical Chapter 5 provides some insight on what psychology has to say about preferences. Chapter 6 adapts Dung's argumentation framework to take preferences into account. The 7th chapter looks at preferences from the point of view of database queries. Chapter 8 draws some relationships between preference representations and multiple criteria aggregation and temporal reasoning. Overall, the book will interest readers who want to have a fairly comprehensive presentation of the various frameworks that deal with expressing preferences. Every chapter ends with a good bibliography, which facilitates access to the literature. A concluding Chapter 9 also provides some links to the literature. Some frameworks are not described in as much detail as others, but the presentation is still reasonably consistent and usually detailed enough. One of the best features of the book is the large number of examples. Every definition and every algorithm is illustrated by a simple but well chosen example that usually captures well enough the notion or the algorithm, to the point where a reader who does not want to study the formal or algorithmic aspects in detail can still get a very good understanding on the basis of the examples alone. The typography is not perfect, especially for some figures, but not to the point where it substantially degrades the reading experience. The mistakes are not too many and almost all of them are very minor and will not confuse the reader. There are more notions than results. Most results are given without proof, but many of them are easy and readers will have no difficulty to establish their validity by themselves, would they want to. Readers who are not strongly motivated to learn about the field in depth are likely to gradually loose motivation from Chapter 4 onwards, as the number of frameworks keeps growing, having too often many points in common with already presented frameworks, which gives the impression that more of the same is being discussed with variations that are not obviously relevant, and with results meant to relate those frameworks together which are rather weak and shallow. The structure of the sequence of chapters and of the chapters themselves is loose. The author claims that the first part of the book is about representation languages, while the second part is about reasoning, but there is actually no study about reasoning about preferences in the true sense of the word ``reasoning''. As they make their way through the book, readers will get more and more the impression that they get exposed to large number of frameworks whose sequence does not tell a story. The author claims that the large number of frameworks is justified by the large number of applications which all have specific needs and rest on specific assumptions. Still, one can only feel that there are so many commonalities between the various settings that it should be possible to adopt a more abstract approach, unify the frameworks, get rid of irrelevant details, and provide a much tighter description of the field. But if that task is indeed possible, then readers interested in it should find this book to be an excellent resource to tackle it! \'Eric Martin (Sydney)