06 Knowledge Representation

Question 1

General ontology

Answer 1

An ontology is a “vocabulary” and a “theory” of a certain “part of reality”.

Special-purpose ontologies apply to restricted domains (e.g. electronic circuits).

General-purpose ontologies have wider applicability across domains, i.e.:
• Must include concepts that cover many subdomains
• Cannot use special “short-cuts” (such as ignoring time)
• Must allow unification of different types of knowledge

Genetic programming (GP) ontologies are useful in widening applicability of reasoning systems, e.g. by including time

Question 2

Ogdens trekant

Answer 2

Fenomen i UoD - Begrep - Representasjon

Question 3

Ontological engineering

Answer 3

Ontological engineering

Representing a general-purpose ontology is a difficult task called ontology engineering. Existing GP ontologies have been created in different ways:

• By team of trained ontologists
• By importing concepts from database(s)
• By extracting information from text documents
• By inviting anybody to enter commonsense knowledge

Ontological engineering has only been partially successful, and few large AI systems are based on GP ontologies (use special-purpose ontologies)

Question 4

Elements of a general ontology

Answer 4

Elements of a general ontology:

• Categories of objects
• Measures of quantities
• Composite objects
• Time, space, and change
• Events and processes
• Physical objects
• Substances
• Mental objects and beliefs

Question 5

Ontology: Categories

Answer 5

Categories are used to classify objects according to common properties or definitions

∀x x ∈ Tomatoes ⇒ Red(x) ∧ Round(x)

Categories can be represented by:
• Predicates: Tomato(x)
• Sets: The constant Tomatoes represents set of tomatoes (reification)

Roles of category representations

• Instance relations (is-a): x1 ∈ Tomatoes
• Taxonomical hierarchies (Subset): Tomatoes ⊆ Fruit
• Inheritance of properties
• (Exhaustive) decompositions

Question 6

Ontology: Objects

Answer 6

Need to distinguish between substance and discrete objects.

Substance (“stuff”)
• Mass nouns - not countable
• Intrinsic properties
• Part of a substance is (still) the same substance

• *Discrete objects (“things”)**
• Count nouns - countable
• Extrinsic properties
• Parts are (generally) not of same category

Question 7

Ontology: Composite objects

Answer 7

A composite object is an object that has other objects as parts. The PartOf relation defines the object containment, and is transitive and reflexive:
PartOf(x, y) ∧ PartOf(y, z) ⇒ PartOf(x, z)
PartOf(x, x)

Objects can be grouped in PartOf hierarchies, similar to Subset hierarchies. The structure of the composite object describes how the parts are related.

Question 8

Ontology: Measurements

Answer 8

Need to be able to represent properties like height, mass, cost, etc. Values for such properties are measures. Unit functions represent and convert measures:
Length(L1) = Inches(1.5) = Centimeters(3.81)
∀l Centimeters(2.53 * l) = Inches(l)

Measures can be used to describe objects:
Mass(Tomato1) = Kilograms(0.16)
∀d d ∈ Days ⇒ Duration(d) = Hours(24)

Non-numerical measures can also be represented, but normally there is an order (e.g. >). Used in qualitative physics.

Question 9

Events: Event calculus

Answer 9

Event calculus: How to deal with change based on representing points of time. Reifies fluents (“forløp”) and events (that is, fluents are functions and we introduce new predicates)

• A fluent: At(Shankar, Berkeley)
• The fluent is true at time t: T(At(Shankar, Berkeley), t)

Events are instances of event categories:
E1 ∈ Flyings ∧ Flyer(E1, Shankar) ∧ Origin(E1, SF) ∧ Destination(E1, LA)

Event E1 took place over interval i:
Happens(E1 , i)

Time intervals represented by (start, end) pairs:
i = (t1, t2)

Time intervals are partitioned into moments (zero duration) and extended intervals.

• *Predicates**
• *T**(f,t) - Fluent f is true at time t. Can be extended to:
• *T**(f, (t1,t2)) - Fluent f is true in interval (t1, t2)
• *Happens**(e, i) - Event e happens over interval i
• *Initiates**(e, f, t) - Event e causes fluent f to start at t
• *Terminates**(e, f, t) - Event e causes f to cease at t
• *Clipped**(f, i) - Fluent f ceases to be true in int. i
• *Restored**(f, i) - Fluent f becomes true in interval i

Question 10

Mental events and mental objects

Answer 10

Mental events and mental objects

Need to represent beliefs in self and other agents, e.g. for controlling reasoning, or for planning actions that involve others. How are beliefs represented?

• Beliefs are reified as mental objects
• Mental objects are represented as strings in a language
• Inference rules for this language can be defined

Rules for reasoning about logical agents’ use their beliefs:

∀a,p,q LogicalAgent(a) ^ Believes(a, p) ^ Believes(a, ”p ⇒ q”)) ⇒ Believes(a, q)
∀a,p LogicalAgent(a) ^ Believes(a, p) ⇒ Believes(a, ”Believes(Name(a), p)”)

Question 11

Semantic networks

Answer 11

Semantic networks
Graph representation of categories, objects, relations, etc. (i.e. essentially FOL). Natural representation of inheritance and default values. E.g. a Person has normally 2 legs, but the default is overridden for John with 1 leg

Question 12

Description logic (DL)

Answer 12

Description logic (DL)

FOL enables ascribing properties to objects, while DL allows formal specification of and reasoning about definitions and categories. DL inference tasks:
• Subsumption - Check if a category is a subset of another
• Classification - Check if object belongs to a category
• Consistency - Check if category definition is satisfiable

DL evolved from semantic networks as a more formalized approach, still based on taxonomies. DL in different versions is the logical foundation for the Semantic Web.

CLASSIC
CLASSIC is an early example of DL, in which definitions can be stated and reasoned about. Simple category definitions:
Single = And(Unmarried,Adult)
Bachelor = And(U nmarried, Adult, M ale)

CLASSIC can answer questions like:
• Is category Bachelor subsumed by category Single?
• Is the individual Adam of category Bachelor?

CLASSIC definitions can be translated to FOL, but inference in DL is more efficient

Question 13

Default and non-monotonic logic

Answer 13

Default and non-monotonic logic
Classical logic is monotonic: true statements remain true after new facts are added to KB: If KB |= a, then KB ^ B |= a

In the closed-world assumption (facts not mentioned assumed false), monotonicity is violated: If a is not mentioned in KB, then KB |= ¬a, but KB ^ a |= a

Non-monotonic reasoning is widespread in common-sense reasoning. We assume default in absence of other input, and are able to retract assumption if new evidence occurs. Non-monotonic logics support such reasoning

Question 14

Circumscription

Answer 14

Circumscription (Norwegian: “begrensning”) is a more powerful version of the closed-world assumption. The idea is to specify particular predicates “as false as possible”, i.e. false for every object except for those for which they are known to be true. E.g. for the default that birds can fly:
Bird(x) ^ ¬Abnormal(x) ⇒ Flies(x)

If Abnormal is circumscribed, a circumscriptive reasoner can:

• Assume ¬Abnormal(x) unless the opposite is known
• Infer Flies(Tweety) from Bird(Tweety)
• Retract the conclusion if Abnormal(T weety) is asserted

Question 15

Truth maintenance systems (TMS)

Answer 15

Many inferences in the KB may have default status, and may need to be retracted in a process called belief revision.

• E.g. KB contains statement P(adefault)
• New evidence that P is not true: TELL(KB, ¬P)
• To avoid contradiction: RETRACT (KB, P)
• Other statements may have been added by P, e.g. Q if the KB contains P ⇒ Q, and Q may also have to go
• However, Q may also be true if the KB contains R ⇒ Q, in which case Q need not be retracted after all.

Systems to handle such “book keeping” are called Truth Maintenance Systems (TMS)

Question 16

Shopping agent

Answer 16

PEAS specification of shopping agent
Performance goal: Recommend product(s) to match user’s description
Environment: All of the Web
Actions: Follow links, retrieve page contents
Sensors: Web pages: HTML, XML

Outline
Start at home page of known web store(s). Must have knowledge of relevant web addresses, such as www.amazon.com etc. Spread out from home page, following links to relevant pages containing product offers. Must be able to identify page relevance, using product category ontologies, as well as parse page contents to detect product offers. Having located one or more product offers, agent must compare and recommend product. Comparison range from simple price ranking to complex tradeoffs in several dimensions.