Preferences and Nonmonotonic Reasoning
Brewka, Gerhard, Niemelä, Ilkka, Truszczynski, Miroslaw, AI Magazine
We give an overview of the multifaceted relationship between nonmonotonic logics and preferences. We discuss how the nonmonotonicity of reasoning itself is closely tied to preferences reasoners have on models of the world or, as we often say here, possible belief sets. Selecting extended logic programming with answer-set semantics as a generic nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. We discuss how such conflicts can be resolved based on implicit specificity or on explicit rankings of defaults. Finally, we comment on formalisms that explicitly represent preferences on properties of belief sets. Such formalisms either build preference information directly into rules and modify the semantics of the logic appropriately or specify preferences on belief sets independently of the mechanism to define them.
(ProQuest: ... denotes formulae omitted.)
One of the fundamental challenges of knowledge representation originates from a simple observation that information available to us more often than not is incomplete. Humans turn out to be quite effective at making decisions and taking actions when faced with incomplete knowledge. The key seems to be the skill of commonsense reasoning, based on our inherent preference to assume that things, given what we know, are normal or as expected. This assumption allows us to form preferred belief sets, base our reasoning exclusively upon them, and ignore all other belief sets that are consistent with our incomplete knowledge but represent situations that are abnormal or rare.1 In this way, commonsense reasoning provides a handle on the complexity of the world around us by eliminating unlikely alternatives. The challenge for knowledge representation research has been to automate commonsense reasoning by finding formal ways to represent incomplete information and to specify preferred belief sets.
Even a simple example shows that the problem is real. Let us consider the task of representing different jobs at a university, relations among them, and their duties. For instance, being a professor is one type of a university job, and we want to model the fact that professors teach. Right away we face a difficulty. Professors teach, but there are exceptions to that rule. A more accurate statement is that professors normally teach. How to model such normative statements and how to reason about them is not at all obvious.
Classical logic, be it first-order or modal, is not the right solution. Given a base theory, a formal description of our knowledge as a set of formulas in the logic, there are no means to distinguish between its models. In other words, a base theory, if expressed and interpreted in classical logic, provides no information on which belief sets, the theories of models, might be preferred for reasoning-all must receive an equal consideration (see figure 1). This aspect of classical logic has several far-reaching consequences. First, there are no concise ways to represent lack of knowledge. Second, classical logic is monotonic: while new information may add to what we know, it does not sanction retractions of conclusions reached earlier. Or, to put it differently, new information may eliminate some models (belief sets) but never leads to new ones. Yet the ability to retract or revise previous conclusions is one of the essential features of commonsense reasoning. Thus, a different breed of logics is needed to formalize it. Such logics, called nonmonotonic, started to emerge in the late 1970s and early 1980s (Reiter 1978, McCarthy 1980, Reiter 1980) and have been studied extensively ever since (Marek and Truszczynìski 1993, Antoniou 1997).
The single common thread running through nonmonotonic logics is that they distinguish among belief sets and use only the preferred ones in reasoning. …