Laurea in Computer Science Laurea in Computer Science MAGISTRALE MAGISTRALE

1

Multistrategy Reasoning / 2 Multistrategy Reasoning / 2

Abstraction – Abduction – Argumentation – Analogy Abstraction – Abduction – Argumentation – Analogy

Laurea in Computer Science Laurea in Computer Science

MAGISTRALE MAGISTRALE

Corso di

ARTIFICIAL INTELLIGENCE Stefano Ferilli

Questi lucidi sono stati preparati per uso didattico. Essi contengono materiale originale di proprietà dell'Università degli Studi di Bari e/o figure di proprietà di altri autori, società e organizzazioni di cui e' riportato il riferimento. Tutto o parte del materiale può essere fotocopiato per uso personale o didattico ma non può essere distribuito per uso commerciale. Qualunque altro uso richiede una specifica autorizzazione da parte dell'Università degli Studi di Bari e degli altri autori coinvolti.

Abstraction

●

Features

●

Aimed at removing unimportant details

– Fundamental for improving efficiency

●

Pervasive in human reasoning

– Handling complexity

●

Subjective

– Depends on the goal

●

Delicate

– Too much: problem solution impossible

– Too few: problem solution too complex

Abstraction

●

Concrete objects (the “real things”) reside in the world (W)

●

Underlying any source of experience, but

●

Not really known

●

We only have a mediated access to it, through our perception

– [Alfred Korzybski, “Science and Sanity”, 1933]

●

In the following, we consider only static situations

●

The world does not change in time

●

Usual situation addressed in Machine Learning

Abstraction

●

Concept representation deals with entities belonging to 3 different levels

– What is important, for an observer, is not the world per se, but his perception P(W) of it

●The percepts “exist” only for the observer and only during their being perceived. Their reality consists in the “physical” stimuli produced on the observer

– To become available over time, the stimuli must be memorized into an organized structure S

●An extensional representation of the perceived world, in which mutually related stimuli are stored together into tables

–Relational database, on which relational algebra operators can be applied

– In order to reason about the perceived world, and to communicate with other agents, a language L is needed

●Allows to describe intensionally the perceived world. At the language level we can operate through inference rules

Reasoning Context

●

Levels used to reason about the world W

●

In P(W) there are perceptions of objects and their matter-of-fact links

●

S is a set of tables, grouping sets of objects sharing some property

●

L is a formal language, whose semantics is evaluated on S’s tables

– T is a theory, embedding properties of the world and general knowledge

●

Reasoning Context

●

R = (P(W), S, L)

Abstraction

●

Among the 3 levels there may be complex links and interplay

●

Investigation of these links pertains to philosophy or psychology

●

Levels are generated upwards

●

P(W) is the primary source of information

●

S tries to record P(W)

●

L verbally describes P(W)

Abstraction

●

The world does not change

●

Only our perception of it may change

●

Several reasons:

– Used tool

– Purposely ignore details

●Not considered relevant for current goal – ...

●

In Machine Learning,

definition of P(W) ~ feature selection

Abstraction

●

Early approaches

●

Abstraction = mapping between two languages

●

Structures implicitly considered as sets of models

●

Saitta & Zucker

●

Abstraction = mapping at the level of the perceived world

– Modifications of the structure and of the language must be introduced only to describe the differences occurred in the perception of the world

Definitions

●

Given a world W, let P(W) be a perception system consisting of a set of sensors, each

●

Devoted to the reception of a particular signal

●

Has a resolution threshold that establishes the minimum difference between two signals in order to consider them as distinct

●

Signal pattern or Configuration: A set of values provided by the sensors in P

●

Recognizing configurations is important for the observer

– Actions may be associated to configurations

●

 : the set of all possible configurations detectable by P(W)

Perception Systems

●

Let P

₁

(W), P

2

(W) be two perception systems for a world W, with configuration sets 

₁

, 

₂

.

P

2

(W) is simpler than P

1

(W) iff

– There is a function f : 

1  

2 that

●Starting from any configuration g₁  ₁ uniquely determines a configuration g₂  ₂

– The inverse function f^–1 does not exist

●There is at least some configuration g₁ that cannot be uniquely reconstructed from g₂, without additional information

Perception Systems

●

Intuitively, “simpler” means that some information, apparent in P

1

, is hidden in P

2

●

We say that P'(W) is "simpler" than P(W), because it offers to the observer less information to manipulate

– Lower cognitive burden (computational load, for an artificial system) paid by a decrease in the information about the world

– This lack of information can be good or bad

●If the correct action to be performed in response to the recognition of the state of W has to be very fine-tuned, this lack of information may result in the wrong action

●If this is not the case, there is no point is handling more information than is needed, because a part of the observer's cognitive effort can be freed for attending another task

Definition

●

Abstraction

●

Given a world W, let R

_g

= (P

_g

(W), S

_g

, L

_g

) and R

_a

= (P

_a

(W), S

_a

, L

_a

) be two reasoning contexts

–

‘ground’ and ‘abstract’

●

An Abstraction is a functional mapping : P Α: P

_g

(W)

→ P

_a

(W) between a perception P

_g

(W) and a simpler perception P

_a

(W) of the same world W

●

Function A allows any abstract configuration to

be uniquely determined from a ground one, but

not vice versa, without additional information

Perception

●

A world may be, in principle, infinitely rich in information. It contains various kinds of objects

●

Compound (composed by several components), or

●

Atomic

each kind with specific properties

●

Thus, P(W) can be informally defined as a 4- tuple P(W) = <OBJ, ATT, FUNC, REL>, where

●

OBJ is a set of perceived objects

●

ATT is a set of object attributes

●

FUNC is a set of functional links

●

REL is a set of relations

Example

●

Perceived world W

●

OBJ contains 7 objects

●

ATT contains attributes "color",

"owner", "type"

●

FUNC contains

a function that gives the distance between two planes and a function that returns the country of an owner

●

Possible relations in REL are spatial ones, such that a plane is "close" to another one and that three planes are in priority conflict for landing

Structure

●

For memorization purposes, the implicit information available in P(W) is organized as a set of tables, forming a relational database (the structure S)

●

S extensively identifies attribute values, functions and relations. To each physical object a unique identifier is associated

– Denoted by an integer or roman number in the ground and abstract world, respectively

●

While S describes the world extensionally, an intensional description is also needed, in order to facilitate reasoning and communication. Then a logical language L is introduced. The truth of a formula of L is evaluated on the structure S

Example

●

Possible structure S

g

for the perceived world W

Example

●

Possible language L

g

for the perceived world W

Scheme of the Abstraction Process

●

Symbols w, s, and l denote abstraction

operators acting at the 3 considered levels,

respectively

Abstraction Operators

●

Corresponding operators at different levels

●

Perception level P(W)

–

W = {w

_ind

, w

_ta

, w

_hide

, w

_eq-val

, w

_red-arg

,

w prop}

●

Structure level

–

S = {s

_ind

, s

_ta

, s

_hide

, s

_eq-val

, s

_red-arg

, s

_prop

}

●

Language level

–

L = {l

_ind

, l

_ta

, l

_hide

, l

_eq-val

, l

_red-arg

, l

_prop}

●

The above set can be reduced or extended with domain-specific abstraction types

Abstraction Operators

●

Perception level 1/3

●

w

_ind

grouping of indistinguishable objects

– Arguments: OBJ

●the objects that shall be considered the same

– Corresponds to Imielinski’s domain abstraction, which groups objects into equivalence classes

●

w

_ta

grouping of a set of ground objects to form a new compound object

– Arguments: OBJ

– The primitive objects disappear from the abstract world

– Most promising for limiting the complexity of learning in a first order logic setting, because it simplifies the matching process between hypotheses and examples

Abstraction Operators

●

Perception level 2/3

●

w

_hide

the specified arguments can be ignored in the abstract world, where they disappear

– Arguments : subsets of OBJ, ATT, FUNC or REL

●

w

_eq-val

for an attribute or a function, specifies what subset of its values can be merged, because they are considered indistinguishable

– Arguments : subsets of ATT, FUNC or REL

– If the values belong to a function range, then the operator can be seen as an approximation of the function

Abstraction Operators

●

Perception level 3/3

●

w

_red-arg

specifies a function/relation and a subset of its arguments to be dropped

– Arguments : subsets of either FUNC or REL, whose elements’ arity is not less than 2

– Obtains a function/relation with reduced arity

●

w

_prop

eliminates all arguments of a function/relation

– Arguments : subsets of either FUNC or REL, whose elements’ arity is not less than 2

– Extreme applicaton of

w

_red-arg.

– Moves from a predicate logic to a propositional logic setting. Corresponds to the propositional abstraction, proposed by Plaisted (1981) at the language level

Example

●

Application of some abstraction operators at the perception level

Abstraction Operators

●

Structure Level

●

Each operator s in S is defined on S by means of relational algebra’s operators

– Projection, selection, join and product

●

Examples

– if r is a binary relation and

w

_red-arg(r(x,y), y) 

W

, then

s

_red-arg(r*(x,y), y) is a projection on x of the table r*

associated to r

–

s

_ind, applied to objects, is a selection operation

Example

●

Effect of abstraction on the structure level

Abstraction Operators

●

Language Level

●

Predicate and function symbols associated to tables in S

– Abstractions of atomic predicates different from abstractions of formulas

●l_ta can only be applied to formulas

●The others can be applied to atomic predicates, to functions and to formulas

●

l

_eq-val

corresponds to

– predicate mapping, when applied to atomic predicates

– climbing a taxonomy, when applied to an attribute values

●

l

red-arg

and l

prop

proposed by Plaisted (1981)

Example

– Operator l_ind to merge the planes from Japan and USA

●Inference rule:

–l_ind (JAPANESE-PLANE, AMERICAN-PLANE | FOREIGN- PLANE) ≡

–∀x [JAPANESE-PLANE(x) AMERICAN-PLANE(x) => → ∨ AMERICAN-PLANE(x) => → FOREIGN-PLANE(x)]

– Operator _ta combining a “hull” and a “sail” to form a yacht

●In the world, w_ta corresponds to actually building up a yacht

●In S, s_ta corresponds to defining a new table

–f_yacht(x,y), with 3 columns; each row <hull_j, sail_j, yacht_j>

asserts that hull

j is combined with sail

j to form yacht

j. Only the yacht column is to be exported to the abstract world

●Corresponding operator l_ta at the language level:

–l_ta(hull, sail | yacht)  "x,y,z [type(x,hull) type(y,sail) ∧ type(y,sail) ∧ ∧ type(y,sail) ∧ close(y,x) => type(z,yacht)]

where z = f_yacht(x,y)

Abstractions and Concept Learning

●

Characterizing Abstractions for Concept Learning

●

Abstraction defined as a true semantic mapping

– Mapping between two perceived worlds P

g(W) and P

a(W)

●Not anymore defined starting from a syntactic mapping – The modifications of the structure and of the language

necessary to describe what happened at the level of the perceived world are, in some sense, side-effects

Abstraction and Concept Learning

●

Approach useful for characterizing abstractions in concept learning

●

Consider

– a reasoning context R_g = (P_g(W), S_g, L_g) and

– an abstraction from P_g(W) to P_a(W).

●

If the operators in W are known,

one can generate both the abstract structure S

_a

– using the corresponding operators in S

and the language L

_a

– using the operators in L

Abstraction and Machine Learning

●

Main question

– If concepts and examples are defined at a “ground” level P_g(W), what are the features of an abstraction mapping that make the corresponding abstract concepts learnable

●or more “easily” learnable in the abstract space using L

a?

●

Concept learning as search

– Definition (a “hypothesis”) of an unknown concept “c”

searched in a space defined by the language L_g

– Most important element to structure L_g :

“generality” relation among hypotheses

●Given two hypotheses h

1 and h

2,

h₁ more general than h₂ if any model for h₂ is also a model for h₁ – Abstractions useful for ML should preserve it

Abstraction in Machine Learning

●

Generality-preserving Language Abstraction Mapping (GLAM)

●

A language level abstraction mapping , between L

_g

and L

_a

, compatible with an abstraction mapping M between P

_g

(W) and P

_a

(W), is a GLAM if the generality relation existing between hypotheses in L

_g

is preserved between the corresponding hypotheses in L

_a

, and vice-versa

– Generality relations evaluated on S_g and S_a, respectively

●

No restriction on the GLAMs, except that the abstracted structure S

a

be used for evaluating the truth of the abstracted hypotheses

Abstraction in Machine Learning

●

Open questions

●

How can a concept definition learnt in L

_a

be mapped back into L

_g

?

●

Identification of the operators which are GLAM and of the set of operators that preserve the GLAM property by composition

Abduction

“Elementary, my dear Watson!”

Sherlock Holmes

Abduction

●

Features

●

Aimed at reasoning from effects to causes

– Hypothesizing sensible but unknown information that can explain given observations

– Fundamental for restarting stuck reasoning

●

Pervasive in diagnosis

– Handling missing information

●

Falsity preserving

– Many explanations possible

●

Potentially complex

– Need to satisfy many constraints

Abduction

●

Definitions

●

“the inference process of forming a hypothesis that explains given observed phenomena”

– [C.S. Pierce (1839-1914)]

●

Broadly : any form of “inference to the best explanation”

– “best” : the generated hypothesis is subject to some optimality criterion

– covers a wide range of different phenomena involving some form of hypothetical reasoning

●

Studies of “abduction” range from philosophical discussions of human scientific discovery to formal and computational approaches in different formal logics

Abduction in Formal Logics

●

Given

– a logical theory T representing the expert knowledge and

– a formula Q representing an observation on the problem domain,

●

abductive inference = Find

– an explanation formula E such that:

●E is satisfiable w.r.t. T and

–If E contains free variables, (E) should be satisfiable w.r.t. T∃(E) should be satisfiable w.r.t. T

●T |= E  Q

–Or, more general, if Q and E contain free variables:

T |= (E ∀  Q)

– In general, E will be subject to further restrictions

●minimality criteria

●criteria restricting the form of the explanation formula (e.g. by restricting the predicates that may appear in it)

●...

Abduction in Formal Logics

●

Abductive explanation of an observation =

●

a formula which logically entails the observation

●

a cause for the observation

– More natural view

●Example

●Disease paresis is caused by a latent untreated form of syphilis.

The probability that latent untreated syphilis leads to paresis is only 25%

–Note: in this context, the direction of entailment and causality are opposite: syphilis is the cause of paresis but does not entail it, while paresis entails syphilis but does not cause it –Yet a doctor can explain paresis by the hypothesis of syphilis

while paresis cannot account for an explanation for syphilis

●

In practice, causation and entailment almost always correspond

Abduction in Formal Logics

●

In many applications of abduction in AI, the theory T describes explicit causality information

●

E.g., model-based diagnosis and temporal reasoning, where theories describe effects of actions

●

By restricting the explanation formulas to the predicates describing primitive causes in the domain, an explanation formula which entails an observation gives a cause for the

observation

●

Hence, for this class of theories, the logical entailment view implements the causality view on abductive inference

Abduction vs Induction

●

Goals

●

In most applications of abduction:

inferring extentional knowledge

– Specific to the particular state or scenario of the world

●

In applications of induction:

inferring intentional knowledge

– Universally holds in many different states of affairs and not only in the current state of the world

●

Example

– Problem : my car won’t start this morning

●an abductive solution is the explanation that its battery is empty –Extentional explanation

●an inductive inference is to derive from a set of examples the rule that if the battery is empty then the car will not start

–Intentional knowledge

Abduction vs Induction

●

Consequence of this distinction

●

Very different format of inductive

– Mostly general rules not referred to a particular scenario

and abductive answers

– Usually simpler formulas, often sets of ground atoms, that describe the causes of the observation in the current scenario according to a given general theory describing the problem domain

●

Induces strong differences in the underlying inference procedures

Abduction & Deduction

●

Deduction

●

Reasoning paradigm to determine whether a statement is true in all possible states of affairs

●

Abduction

●

Returns an explanation formula corresponding to a (non-empty) collection of possible states of affairs in which the observation would be true or would be caused

– Strictly related to model generation and satisfiability checking

– By definition, the existence of an abductive answer proves the satisfiability of the observation

●But abduction returns more informative answers, which describe the properties of a class of possible states of affairs in which the observation is valid

Abduction

●

A form of inference of extentional hypotheses explaining observed phenomena

●

A versatile and informative way of reasoning on

– Incomplete knowledge

●Does not entirely fix the state of affairs of the domain of discourse

–Abductive inference can be used for default reasoning – Uncertain knowledge

●Is defeasible

(its truth in the domain of discourse is not entirely certain)

●

Can be seen as a refinement of these forms of

reasoning

Abduction & Declarative Knowledge Representation

●

An important role of logic in AI is to provide a framework for declarative problem solving

●

A human expert specifies his knowledge of the problem domain by a descriptive logic theory and uses logical inference systems to solve

computational tasks arising in this domain

– Early days of logic-based AI : deduction considered as the only fundamental problem solving paradigm of declarative logic

– Current state of the art : deduction not the central inferential paradigm of logic in AI

●A declarative problem solving methodology will often lead to abductive problems

Abduction & Declarative Knowledge Representation

●

Trade-off

●

(1) Natural representation

– The choice of an alphabet corresponding to the concepts and relations in the mind of the human expert

●Prerequisite to obtain a compact, elegant and readable specification

– Consequence: tight link to the computational task of problem solving

●Declarative Knowledge Representation comes hand in hand with abduction

●Abduction then emerges as an important computational paradigm that would be needed for certain problem solving tasks within a declarative representation of the problem domain

Abduction & Declarative Knowledge Representation

●

Trade-off

●

(2) Computational effectiveness

– Although the use of a more complex ontology may seriously reduce the elegance of the representation, it may be necessary to be able to use a specific system for solving a problem

– In some cases the pure declarative problem

representation needs to be augmented with procedural, heuristic and strategic information on how to solve effectively the computational problem

●

Current research studies how more intelligent search and inference methods in abductive systems can push this trade-off as far as possible in the direction of more declarative representations

Abductive Logic Programming (ALP)

●

ALP theory : a triple (P, A, IC)

●

P a logic program

●

A a set of ground abducible atoms (abducibles)

– In practice, specified by their predicate names

– No p  A can occur in the head of a rule in P

●

IC a set of classical logic formulas (integrity constraints)

– Usually, Logic Programming goals

●

In ALP, the definition of abduction is usually specialized as follows:

Views on IC

●

Need to define how integrity constraints IC constrain the abductive solutions

●

Consistency view

– Any extension of the given theory P with an abductive solution D is required to be consistent with the integrity constraints IC: P IC D is consistent∪ IC ∪ D is consistent ∪ IC ∪ D is consistent

●Adopted by early work on abduction in the context of classical logic

●

Entailment view

– The abductive solution D together with P should entail the constraints

●Taken in most versions of ALP

●Stronger than the consistency view

–Solutions according to the entailment view are solutions according to the consistency view but not vice versa

Views on IC

●

The difference can be subtle but

in practice the two views usually coincide

●

E.g. often P ∪ IC ∪ D is consistent D has a single model, in which case both views are equivalent

●

Many ALP systems use the entailment view

●

Can be easily implemented without the need for any

extra specialized procedures for the satisfaction of

the integrity constraints since this semantics treats

the constraints in the same way as the query

Abductive Explanation

●

Given an abductive logic theory (P, A, IC), an abductive explanation for a query Q is a set D A of ground abducible atoms such that: ⊆ A of ground abducible atoms such that:

●

P ∪ IC ∪ D is consistent D |= Q

●

P ∪ IC ∪ D is consistent D |= IC

●

P ∪ IC ∪ D is consistent D is consistent

– D aims to represent a nonempty collection of states of affairs in which the explanandum Q would hold

●

Defines abductive solution for a query

Abductive Explanation

●

Does not define abductive logic programming as a logic in its own right

●

Pair (syntax, semantics)

●

Generic definition in terms of

●

Syntax

– Often, normal logic programs with negation as failure

●Investigations on extended logic programming or constraint logic programming

●

Semantics

– each standard logic programming semantics defines its own entailment relation |=, its own notion of consistent logic programs and hence its own notion of what an abductive solution is

●In practice, the three main semantics of logic programming – completion, stable and well-founded semantics – have been used to define different abductive logic frameworks

Models & Entailment

●

A notion of generalized model can be defined

●

M is a model of an abductive logic framework (P, A, IC) iff there exists a set D A such that ⊆ A of ground abducible atoms such that:

– M is a model of P D (acco∪ IC ∪ D is consistent rding to some LP-semantics) and

– M is a classical model of IC, i.e. M |= IC

●

Entailment between abductive logic frameworks and classical logic formulas

●

(P, A, IC) |= F iff M |= F for each model M of (P, A, IC)

Models & Entailment

●

Observations on entailment definition

●

Standard

●

Generic in the choice of the LP semantics

– stable, well-founded, partial stable model semantics

– Completion semantics of an abductive logic framework (P, A, IC) defined by mapping it to its completion

●Completion: the first order logic theory consisting of : –U N , the set of unique names axioms, or Clark’s equality

theory –IC

–comp(P, A), the set of completed definitions for all non- abducible predicates

ID-logic

●

Extension of classical logic with inductive definitions

– Each consists of a set of rules defining a specific subset of predicates under the well-founded semantics

●

Proposed as appropriate for ALP

– Attempt to clarify the representational and epistemological aspects

– Gives an epistemological view on ALP

●P defines the non-abducible predicates

–~ human expert’s strong definitional knowledge

●A are the undefined predicates

●IC are simply classical logic assertions

–~ human expert’s weaker assertional knowledge – ALP seen as a sort of description logic

●Program = TBOX consisting of one simultaneous definition of the non-abducible predicates

●Assertions = ABOX

Abductive Inference

●

2 procedures

●

Abductive derivation

– Standard Logic Programming derivation, but

– When an abducible is needed

●If not already abduced (nor its negation already abduced) –Abduce it if Consistency Derivation succeeds

●

Consistency derivation

– Checks if all ICs involving it can be satisfied

– Must ensure the truth or falsity of atoms in the Ics

●Exploits the Abductive Derivation for this

Abductive Inference

●

Abductive derivation [Kakas & Mancarella]

Abductive Inference

●

Consistency check [Kakas & Mancarella]

Abductive Inference

●

Example

●

Abductive Theory

– P = {father(X,Y) :- parent(X,Y), male(X). parent(a,b).}

– A = {male/1}

– IC = {:- male(X),female(X).}

●Implicit: :- male(X), male(X).

●

?- father(a,b).

●SLD resolution up to male(a), missing -> consistency check

●Can be abduced provided that female(a) -> SLD resolution

●[NAF tries to prove female(a), missing -> consistency check

●Can be abduced because alone it satisfies the constraint – D = {male(a), female(a)}

Expressive ALP

●

Additional types of constraints

– Associated to logistic operators

●nand([l

1,...,l

n]) : at least one among literals l

1,...,l

n must be false –The classical denials considered in ALP

●xor([l₁,...,l_n]) : exactly one among literals l₁,...,l_n must be true

●or([l₁,...,l_n]) : at least one among literals l₁,...,l_n must be true

●if([l’₁,...,l’_n],[l’’₁,...,l’’_m]) : if all literals l₁,...,l_n are true, then all literals l’’₁,...,l’’_m must also be true (modus ponens); alternatively, if at least one literal l

1,...,l

n is false, then at least one literal l’’

1,...,l’’

m

must also be false (modus tollens)

●iff([l’₁,...,l’_n],[l’’₁,...,l’’_m]) : either all literals l₁,...,l_n and l’’₁,...,l’’_m are true, or at least one literal in l₁,...,l_n and at least one literal in l’’₁,...,l’’_m is false

●and([l₁,...,l_n]) : all literals l₁,...,l_n must be true

●nor([l₁,...,l_n]) : all literals l₁,...,l_n must be false

Expressive ALP

●

Example

Expressive ALP

●

Relationships among constraints

Expressive ALP

●

(Extended) Consistency Derivation

●

AND constraints

– satisfied when the list of literals becomes empty after all of its members have been proven to be true

– fail as soon as one literal cannot be proved to be true.

●

NOR constraints

– satisfied when the list of literals becomes empty after all of its members have been proven to be false

– fail as soon as one literal cannot be proved to be false

●

XOR constraints

– satisfied when, after proving one literal to be true, the list of all remaining literals is proved to be false (i.e., a NAND constraint holds on it)

– fail when the list of literals becomes empty after all of its members have been proven to be false

Expressive ALP

●

(Extended) Consistency Derivation

●

IFF constraints checked as follows

– Check the AND of the premise

●if it succeeds,

enqueue the AND of the consequence for checking

●otherwise, as soon as the premise fails,

enqueue the NAND of the consequence for checking

●

IF constraints

checked based on the X  Y  X  Y equivalence

– Check the NAND of the premise

●if it succeeds,

do nothing (the constraint is satised)

●otherwise, as soon as the NAND fails (i.e., the AND of the premise is satisfied),

enqueue the AND of the consequence for checking

Expressive ALP

●

(Extended) Consistency Derivation

●

OR constraints

– satisfied as soon as one literal is proven to be true

– fail when the list of literals becomes empty after proving all of its members to be false

●

NAND constraints

– satisfied as soon as one literal is proven to be false

– fail when the list of literals becomes empty after proving all of its members to be true

Probabilistic Expressive ALP

●

Definition (Probabilistic Expressive Abductive Logic Program)

●

4-tuple <P,A,I,p>

– P is a (standard or probabilistic) logic program

– A (abducible predicates) is a set of atoms (or predicates)

– I (integrity consstraints) is a set of typed (‘extended’) integrity constraints

– p : P  ground(A)  I  [0,1] is a function associating a probability to each element in P, in I

●strength of a constraint

and in the set ground(A) of ground literals built on predicates in A

●For the sake of compactness, in the following all items for which p(.) is not specified will be assumed to have probability 1.0

Probabilistic Expressive ALP

●

Probabilistic approach based on the notion of possible worlds, as usual in the literature

●

Given a goal G and a PEALP T = <P,A,I,p>, a (probabilistic) abductive explanation of (or possible world for) G in T is a triple E = (L, D,C)

– L is the set of facts in P

– D is the abductive explanation

●The set of ground literals abduced

– C is the set of instances of (probabilistic) integrity constraints in I, involved in an abductive proof of G in T

●C  C denotes the instances of constraints that are satisfied by D

●C  C denotes the instances of constraints that are violated by D

●WG the set of all possible consistent worlds associated to G in T

Probabilistic Expressive ALP

●

Likelihood score of an abductive explanation

●

Most likely explanation

Argumentation

●

Studies the processes and activities involved in the production and exchange of arguments

●

Goals: identify, analyze and evaluate arguments

●

Captures diverse kinds of reasoning and dialogue activities in a formal but still intuitive way

●

Provides procedures for making and explaining decisions

●

In AI

●

Giving reasons to support claims that are open to doubt

●

Defending these claims against attack

Argumentation

●

Argument

– In Computational Linguistics, Logics, NLP, Philosophy:

●is a set of propositions from which a conclusion can be drawn

●invoked by a linguistic action (in either monologue or dialogue)

●results from an appropriate speaker/writer intention

●may be subsequently evaluated

●may leave material implication implicit

●may have various types of internal structures – In AI, Knowledge Representation, Nonmonotonic

Reasoning:

●An attempt to persuade someone by giving reasons for accepting a conclusion as evident

●Defeasible Reasoning: the validity of its conclusions can be disputed by other arguments

Argumentation

●

Arguing

– something people do

●rather than something that propositions do – typically involves two or more people

●Dialogue (vs monologue)

– typically involves two or more points of view

●Dialectical (vs monolectical) – concerns advancing arguments

●

Arguers

– Those who put forward arguments and engage in arguing

– Their stance and expertise may affect their arguments

Argumentation

●

Structured Argumentation

●

Arguments = trees of statements

– (including an underlying logic language + a notion of logical consequence)

●

closer to the linguistic form of argument

●

supports a range of

formal logics for characterizing inference

●

claims obtained via strict and defeasible rules

●

different notions of conflict

– rebuttal, undercut, undermine, etc.

●

Focus: defining a notion of attack and defeat between arguments

●

Intermediate step to abstract frameworks

Abstract Argumentation

●

Arguments encapsulated as nodes in a digraph connected through an attack relationship

– abstracts from the specific content of arguments, only considers the relation between them

●allows to compare several KR formalisms on a conceptual level

●

Solution of conflicts between the arguments:

defines a calculus of opposition for determining what is acceptable (justified)

●

Different semantics allowed

– Select subsets of arguments satisfying certain criteria

●

Main properties

– Separation between logical (forming arguments) and nonmonotonic reasoning (Argumentation Frameworks)

– Simple, yet powerful, formalism

– Most active research area in the field of Argumentation

Abstract Argumentation vs Structured Argumentation

●

Example

Argumentation Pipeline

●

Argument Mining

– Analyzing argumentation structures in the discourse

●

Abstract Argumentation

– A framework for practical and uncertain reasoning able to cope with partial and inconsistent knowledge

Abstract Argumentation

●

Argumentation Framework (AF) [Dung]

●

A pair F = <A, R>

– A finite set of arguments, R A × A⊆ A of ground abducible atoms such that:

●

Semantics

●

A way to identify sets of arguments (extensions)

“surviving the conflict together”

●

Given an AF F = <A, R>, S A ⊆ A of ground abducible atoms such that:

Argumentation Framework

●

(Some) Semantics Properties

– Conflict-freeness

●An attacking and an attacked argument can not stay together – Defense

●to survive the conflict you should be able to defend yourself, by replying to every attack with a counterattack

– Admissibility

●a conflict-free extension should be able to defend itself – Strong-Admissibility

●no self-defeating arguments – Reinstatement

●if you defend some argument you should take it on board – I-Maximality

●no extension is a proper subset of another one – Directionality

●a (set of) argument(s) is affected only by its ancestors in the attack relation

Abstract Argumentation

●

Conflict-free set

●

Given an AF F = <A, R>

●

S A ⊆ A of ground abducible atoms such that: is conflict-free if a, b  S s.t. aRb.

–  conflict-free by definition

●

Example

– cf(F) = { , {a}, {b}, {c}, {d}, {a,c}, {a,d}, {b,d} }

Abstract Argumentation

●

Admissible set

●

Given an AF F = <A, R>

●

S A is admissible if S is conflict-free and S ⊆ A of ground abducible atoms such that:

defends itself

●

"a  S, "b  A : bRa  c  S s.t. cRb

–  admissible by definition

●

Example

– adm(F) = { , {a}, {b}, {c}, {d}, {a,c}, {a,d}, {b,d} }

Extension-based Semantics

●

(Extension-based) Semantics

– Naive

●Maximum conflict-free sets – Complete

●Conflict-free set s.t. each defended argument is included – Grounded

●Minimum complete extension – Preferred

●Maximum complete extensions – Stable

●Complete extensions attacking all the arguments outside – Semi-Stable

●Preferred extensions with maximum range

–union of non-attacked arguments and attacked ones – Stage

●Conflict-free sets with maximum range

Extension-based Semantics

●

(Extension-based) Semantics

– Ideal

●Maximal subset of each preferred extension – Eager

●Maximal semi-stable extension – cf2

●Maximal consistent set of arguments based on SCCs of naive sets

– stage2

●Maximal consistent set of arguments based on SCCs of stage extensions

– Resolution-based Grounded

●Grounded sets including solutions with nodes involved in odd- length cycles

– Prudent

●Extensions without indirect conflicts

Extension-based Semantics

●

Naive Extension

●

S conflict-free and T  cf(F) s.t. S  T

●Example: adm(F) = { , {a}, {b}, {c}, {d}, {a,c}, {a,d}, {b,d} }

●

Complete Extension

●

S admissible and "x  A : x defended by S  x  S

– Any argument in A defended by S is in S

–  complete only if there are no unattacked arguments

●Example: comp(F) = { , {a}, {c}, {d}, {a,c}, {a,d} }

Extension-based Semantics

●

Grounded extension

●

S complete and T  comp(F) s.t. T  S

●Example: grd(F) = { {a}, {a,c}, {a,d} }

●

Preferred extension

●

S admissible and T  adm(F) s.t. S  T

●Example: pref(F) = { , {a}, {c}, {d}, {a,c}, {a,d} }

●

Stable extension

●

S conflict-free and "a  A : a  S  b  S s.t. bRa

●Example: stb(F) = { , {a}, {b}, {c}, {d}, {a,c}, {a,d}, {b,d} }

Extension-based Semantics

● S⁺ = S  { a  A | b  S s.t. bRa } range of S

●Example: {a,d}⁺ = A

●

Semi-stable Extension

●

S admissible and T  adm(F) s.t. S

⁺

 T

⁺

●Example: sem(F) = { , {a}, {c}, {d}, {a,c}, {a,d} }

●

Stage Extension

●

S conflict-free and T  cf(F) s.t. S

⁺

 T

⁺

●Example: stage(F) = { , {a}, {b}, {c}, {d}, {a,c}, {a,d}, {b,d} }

Extension-based Semantics

●

Ideal Extension

●

S admissible and "T  pref(F) : S  T

●

Example

– pref(F) = { {a,d}, {b,d} }

– ideal(F) = { {d} }

– grd(F) = {  }

●

Ideal Extension

●

S admissible and

"T  pref(F) : S  T

●Example:

pref(F) = { {a,d}, {b,d} } ideal(F) = { {d} } grd(F) = {  }

Extension-based Semantics

●

Eager Extension

●

"T  sem(F) : S  T

●Example:

sem(F) = { {b,c,f}, {b,d,f} } eager(F) = { {b,f} } grd(F) = {  }

Extension-based Semantics

●

Taxonomy

Ranking-based Semantics

●

Extension-based

– Arguments either accepted or rejected

– Defeated arguments are killed

●Automatically excluded – Number of successful

attacks against an argument is irrelevant

– Absolute status of arguments (accepted, rejected, undecided)

●Makes sense without comparing them – Same level of

acceptability for all accepted arguments

●

Ranking-based

– Gradual levels of acceptability

– Arguments cannot be killed

●Just weakened to an extreme extent – The more attacks

against an argument, the less acceptable

– Relative degrees of acceptability

●Make sense only when compared to each other – Arbitrarily large

number of degrees of acceptability

Ranking-based Semantics

●

Rank arguments from the most to the least acceptable

●

(Some) properties:

– Abstraction (Abs)

●The ranking on arguments should be defined only on the basis of the attacks between arguments

– Independence (In)

●The ranking between two arguments a and b should be independent of any argument that is neither connected to a nor to b

– Void Precedence (VP)

●A non-attacked argument is ranked strictly higher than any attacked argument

– Self-Contradiction (SC)

●A self-attacking argument is ranked lower than any non self- attacking argument

Ranking-based Semantics

●

(Some) properties:

– Cardinality Precedence (CP)

●The greater the number of direct attackers for an argument, the weaker the level of acceptability of this argument

– Quality Precedence (QP)

●The greater the acceptability of one direct attacker for an argument, the weaker the level of acceptability of this argument – Counter-Transitivity (CT)

●If the direct attackers of b are at least as numerous and acceptable as those of a, then a is at least as acceptable as b – Strict Counter-Transitivity (SCT)

●If CT is satisfied and either the direct attackers of b are strictly more numerous or acceptable than those of a, then a is strictly more acceptable than b

Ranking-based Semantics

●

(Some) properties:

– Defense Precedence (DP)

●For two arguments with the same number of direct attackers, a defended argument is ranked higher than a non-defended argument

– Addition of Attack Branch (AAB)

●Adding an attack branch to any argument degrades its ranking – Total (Tot)

●All pairs of arguments can be compared – Non-attacked Equivalence (NaE)

●All the non-attacked argument have the same rank – Attack vs Full Defense (AvsFD)

●An argument without any attack branch is ranked higher than an argument only attacked by one non-attacked argument

Ranking-based Semantics

●

Categorizer

●

Given an AF F = <A,R>, Cat : A  [0,1]

Argumentation Framework

●

Limitations of Dung’s Argumentation Framework

●

Allows only a symbolic representation of knowledge using propositions and the attack relation

●

Acceptability of arguments only based on the logical relations between arguments

●

Neglects social relations between arguers, preferences between arguments, or different strength of attacks

●

Admits many alternate solutions (with no hint for a choice) or the only solution may be the empty set

●

Supports can only be represented implicitly via defended arguments

Argumentation Framework

●

Generalizations

●

Bipolar AF

– Support relation

●

Weighted AF

– Weights on attacks

●

Extended AF

– Preferences on attacks

●

PAF/VAF

– Preferences over arguments

●

ADF

– Explicit acceptability conditions per argument

Bipolar

Argumentation Framework

●

Bipolar AF (BAF)

● 2

possible kinds of interactions

– Attack

– Support

●

Advantages

– Combined interactions: complex attack relations

●support + attack = supported attack

●attack + support = indirect attack

– Extension-based semantics include supported arguments

●

Disadvantages

– Hidden assumption: conflict is stronger than support

– No gradual valuation

●Existing semantics still declare all justified arguments as equally accepted

Weighted

Argumentation Framework

●

Weighted AF (WAF)

●

Weight on attack = measure of inconsistency

●

Advantages

– Removing some attacks up to a certain degree of tolerated incoherence

●Sum of weights of attacks does not exceed an Inconsistency Budget > 0β > 0

– Selecting some extensions among Dung’s ones (when there are too many extensions)

●

Disadvantages

– Extension-based semantics do not fully exploit the weight of relations

– Non-conflict-free extensions

Bipolar Weighted Argumentation Framework

●

Weights in [-1,0[  ]0,1]

●

0 = no relationship

●

[-1,0[  Attack

●

]0,1]  Support

●

Indirect relationships

●

Sign rule

– + x + = + + x – = – – x + = – – x – = +

Bipolar Weighted Argumentation Framework

●

Extension-based Semantics

●

BAF-like: weights {-1,1}

– Multiplication defines bw-defense and bw-admissibility

●

WAF-like: extended inconsistency budget

– Threshold to neglect attacks

●

Ranking-based Semantics

●

Strength Propagation strategies

– How the weights of attacks and supports propagate along the paths in the graph to determine the overall attack or support to an argument

Trusted Bipolar Weighted Argumentation Framework

●

Weights also on arguments

●

Experience of the arguer about the topic

– Arguments labeled with topics

●

Subjective certainty of the arguer about the argument

●

Trust of the community for the arguer on the topic

– Graph of trust for each topic

●Wide literature in the Social Network community

●Representation and computation of trust may be the same as for arguments

a 0.7 b

0.8

Abstract Argumentation

●

Sample application

●

On-line debates

– Example: Reddit thread

Analogy

●

Transfer of knowledge across domains

●

Motivations

– Important in the study of learning, for the transfer of knowledge and inferences across different concepts, situations, or domains

– Often used in problem solving and reasoning

– Can serve as mental models to understand new domains

– Important in creativity

●Frequent mode of thought in the history of science for such great scientists as Faraday, Maxwell, and Kepler

– Used in communication and persuasion

– Together with its ‘sibling’, similarity, underlies many other cognitive process

Analogy

●

Phases

●

Retrieval, finding the better base domain that can be useful to solve the task in the target domain;

●

Mapping, searching for a mapping between base and target domains;

●

Evaluation, providing some criteria to evaluate the candidate mapping;

●

Pattern, shifting the representation of both domains to their roles schema, converging to the same analogical pattern;

●

Re-representation, adapting of one or more piece of the representation to improve the match.

Analogy

●

Assumptions

●

In human reasoning common sense shares the formalism

●

All descriptions expresseded at the same abstraction level

●

Formalization of the goal is not subject of study

●

Open issues

●

Application of Reasoning by Analogy is not direct

●

Lack of several steps are lacking, e.g.:

– An approach to select only the knowledge of interest

– An approach to abstraction in order to make possible the matching of different experiences

Analogy

●

ROM mapping

a(n1,1,n1,8) a(n2,1,n2,8) a(n1,1,n1,2) a(n2,1,n1,2)

Analogy

●

ROM mapping

c(n^1,3,n1,2) c(n^2,3,n1,2) c(n^1,6,n^1,7)

a(n1,1,n1,8) a(n2,1,n2,8) a(n^1,1,n^1,2) a(n^2,1,n^1,2)

Analogy

●

ROM mapping

e(n1,5,n1,1) m(n2,5,n2,1) b(n1,1,n1,6) n(n2,1,n2,6) g(n1,6,n1,8) o(n2,6,n2,8) d(n1,1,n^1,4) h(n2,1,n^2,4)

Analogy

●

Inference

Analogy

●

Inference

Analogy

●

Qualitative Evaluation

A fortress was located in the center of the country. Many roads radiated out from the fortress. A general wanted to capture the fortress with his army. The general wanted to prevent mines ...

conquer(fortress) :- located(fortress,center), partof(center,country), radiated(oneroad,fortress), radiated(roads,fortress), partof(oneroad,roads), capture(general,fortress), use(general,army), ...

heal(tumor) :-

located(tumor,interior), partof(interior,body), defeat(doc,tumor), use(doc,rays), ...

A tumor was located in the interior of a patient’s body. A doctor wanted to destroy the tumor with rays. The doctor wanted to prevent ...

Analogy

●

Qualitative evaluation

After filtering out one-to-one correspondences,

the procedure seeks base knowledge that could be novel in the target domain.

heal(tumor) :-

located(tumor, interior), partof(interior, body),

defeat(doc, tumor), use(doc, rays), prevent(doc, healthytissue), located(healthytissue, oneslit), located(healthytissue, slits), aredestroyed(healthytissue, rays), couldnotuse(rays, oneslit), defeat(rays, tumor), couldnotuse(ray, oneslit),

radiated(oneslit, tumor), radiated(slits, tumor), partof(oneslit, slits), splittable(rays, ray),

partof(ray, subrays), partof(subrays, rays), notenough(ray),

aredestroyed(healthytissue, ray), aredestroyed(healthytissue, subrays).

defeat(subrays, tumor) splittable(rays, subrays) distribute(subrays, slits) converge(subrays, tumor)

aredestroyed(healthytissue, villages)

Analogy & Argumentation

●

Analogy to solve mapping conflicts

●

Argument = candidate mapping

– Each considered as starting point for the ROM mapping procedure

●

Complete extensions

– Conflict-free sets = consistent sets of statements

– Restrict the possible associations

– Maximal general mapping = Union of mappings of the biggest complete extension

●

Use of argumentation to solve conflicts

●

Conflict-free sets = consistent sets of statements

– Restrict the possible associations

a

k

Analogy & Argumentation

●

Wrong analogy

●

Correct analogy

●

Structural mapping...

Analogy & Generalization

●

Patterns

– If the fox cannot reach the grapes it says they are not ripe.

– John cannot have Carla. He spreads a bad opinion about her.

pattern(proverb(wolf,grape), situation(john,carla)) :- wants/loves(wolf/john, grape/carla),

cannot_take/cannot_have(wolf/john, grape/carla,

wolf_does_not_reach_grape/john_cannot_have_carla), says(wolf/john, grape_is_ugly/carla_is_bad),

is(grape/carla, ugly/bad, grape_is_ugly/carla_is_bad).