06 Knowledge Representation Flashcards
General ontology
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
Ogdens trekant
Fenomen i UoD - Begrep - Representasjon
Ontological engineering
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)
Elements of a general ontology
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
Ontology: Categories
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
Ontology: Objects
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
Ontology: Composite objects
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.
Ontology: Measurements
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.
Events: Event calculus
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
Mental events and mental objects
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)”)
Semantic networks
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
Description logic (DL)
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
Default and non-monotonic logic
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
Circumscription
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
Truth maintenance systems (TMS)
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)
