Obsidian + 🪴 Quartz 4.0

AI - Lecture - Knowledge Engineering

16 min read

AI - Lecture - Knowledge Engineering

  • Chapter 10 from Artificial Intelligence Book

A knowledge based agent uses a knowledge base to reason and act. So the main question is “what knowledge should be represented and how?“.

In this lecture, we discuss how to organize knowledge so that an agent can:

  • Describe objects, events, and relations
  • Reason about categories and individuals
  • Infer new facts from existing knowledge
  • Choose appropriate actions

Ontological Engineering and Upper Ontology

An ontology is a formal specification of the concepts, relations, and properties used to describe a domain. Ontologies provide a shared, machine-readable vocabulary for representing and reasoning about domain knowledge. They are widely used in:

  • knowledge representation
  • semantic web technologies
  • information integration
  • intelligent systems

Ontological Engineering is the process of designing concepts and relations used in a domain.

An upper ontology is a domain-independent framework of very general concepts. It provides a shared high-level vocabulary for describing the most general kinds of entities.

It is called upper ontology because of the convention of drawing graphs with the general concepts at the top and the more specific concepts below them, as in figure:

The principal difficulty is that most generalizations have exceptions or hold only to a degree. For example, although “tomatoes are red” is a useful rule, some tomatoes are green, yellow, or orange.

We should say up front that the enterprise of general ontological engineering has so far had only limited success. None of the top AI applications make use of a general ontology—they all use special-purpose knowledge engineering and machine learning. Social/political considerations can make it difficult for competing parties to agree on an ontology.

For example, the Google Knowledge Graph uses semistructured content from Wikipedia, combining it with other content gathered from across the web under human curation. It contains over 70 billion facts and provides answers for about a third of Google searches.

Categories and Objects

graph TD
    Categories --> Objects
    Categories --> Predicates

The organization of objects into categories is a vital part of knowledge representation. Categories also serve to make predictions about objects once they are classified. One infers the presence of certain objects from perceptual input, infers category membership from the perceived properties of the objects, and then uses category information to make predictions about the objects.

For example, from its green and yellow mottled skin, one-foot diameter, ovoid shape, red flesh, black seeds, and presence in the fruit aisle, one can infer that an object is a watermelon; from this, one infers that it would be useful for fruit salad.

Another example:

There are two choices for representing categories in first-order logic:

  • predicates
  • objects

Reification of categories

For example consider the predicate Basketball(x) could also be expressed as Member(x,Basketballs).

The second representation is an example of reification: treating something abstract, such as category, relation, event or proposition, as an object in the domain.

By reifying a category, we can make statements about the category itself:

  • Member(, )
  • Subset()
  • Subset()

This allows the knowledge base reason not only about individual objects, but also about classes of objects and relations among classes.

Rationale: Reification lets us talk about concepts as things.

Inheritance and Taxonomies

Categories allow knowledge to be inherited.

then we can infer:

Subclass relations organize categories into a taxonomic hierarchy, or taxonomy.

Example:

So properties of more general categories can be inherited by more specific categories.

FOL and categories

First order logic (FOL) simplifies stating facts about categories by relating objects to them or quantifying over their members. Here are the examples provided:

  • An object is a member of a category.
  • A category is a subclass of another category. or
  • All members of a category have some properties.
  • Members of a category can be recognized by some properties.
  • A category as a whole has some properties.

Categories can be defined by giving necessary and sufficient conditions for membership.

For example: A bachelor is an unmarried adult, in FOL we would write that means:

  • if is a bachelor, then is unmarried, adult and male
  • If is unmarried, adult, and male, then is a bachelor.

Disjoint categories, exhaustive decomposition and partition

Categories may be related in ways other than subclass relations.

Disjoint categories are two categories that have no members in common Exhaustive decomposition: a set of subcategories is exhaustive if every member of the parent category belongs to at least one subcategory

Partition: a partition is both exhaustive and disjoint.

So every member of the parent category belongs to exactly one subcategory.

Here are some more examples of these three concepts:

(Note that the of is not a , because some people have dual citizenship.)

Formal definitions - the three predicates are defined as follows:

Categories can also be defined by providing necessary and sufficient conditions for membership. For example, a bachelor is an unmarried adult male:

Physical Composition

graph LR
PhysicalComposition --> |Part-whole relations| PartOf
PhysicalComposition --> CompositeObjects[Composite Objects]
CompositeObjects --> Bunch
CompositeObjects

The idea that one object can be part of another is a familiar one. One’s nose is part of one’s head, Romania is part of Europe, and this chapter is part of this book.

Objects can be related by part–whole relations. We use the general relation to say that one thing is part of another. Objects can be grouped into hierarchies, reminiscent of the hierarchy:

The relation is transitive and reflexive; that is,

Therefore, we can conclude .

Categories of composite objects are often characterized by structural relations among parts.

For example consider a biped, that is an object with exactly two legs attached to a body:

The notation for “exactly two” is a little awkward; we are forced to say that there are two legs, that they are not the same, and that if anyone proposes a third leg, it must be the same as one of the other two.

It is also useful to define composite objects with definite parts but no particular structure. For example, we might want to say “The apples in this bag weight two pounds.”

The temptation would be to ascribe this weight to the set of apples in the bag, but this would be a mistake because the set is an abstract mathematical concept that has elements but does not have weight. The solution is to add a new concept called a bunch.

For example, if the apples are , and then: denotes the composite object with the three apples as parts (not elements). We can then use the bunch as a normal, albeit unstructured, object.

We can define BunchOf in terms of the PartOf relation. Ofcourse each element of is part of BunchOf(s):

We can define BunchOf in terms of the PartOf relation.

Measurements

Objects often have measurable properties, such as: height, length, mass, cost, temperature.

The values assigned to these properties are called measures. A measure combines number + unit. For example: 1.5 inches and 3.81 centimeters can denote the same length. We can represent this using measure objects:

Here, 𝐼𝑛𝑐ℎ𝑒𝑠 and 𝐶𝑒𝑛𝑡𝑖𝑚𝑒𝑡𝑒𝑟𝑠 are unit functions that map numbers to measure objects.

Measures describe quantitative properties of objects. For example: .

Diameter is a function from objects to measure values, while Inches is a unit function. Unit functions maps numbers to measure objects.

Things and stuff

graph LR
Things[Things <br><small>Count Nouns</small>]
Stuff[Stuff <br><small>Mass Nouns</small>]
Things --> Properties
Stuff --> Properties
Properties --> Intrinsic
Properties --> Extrinsic

The real world can be seen as consisting of primitive objects (e.g., atomic particles) and composite objects built from them.

There is, however, a significant portion of reality that seems to defy any obvious individuation—division into distinct objects. We give this portion the generic name stuff. For example, suppose I have some butter and an aardvark in front of me. I can say there is one aardvark, but there is no obvious number of “butter-objects,” because any part of a butter-object is also a butter-object, at least until we get to very small parts indeed.

Things are described by count nouns: a cat, car two apples.

Stuff is described by mass nouns: water, butter, sand, energy.

Some properties are intrinsic. They are properties of the substance itself and are usually preserved when the substance is divided.

On the other hand, their extrinsic properties; weight, length, shape, and so on, are not retained under subdivision.

Events

graph TD
Root[Represent Change]
Root --> Events[Events <br><small>or actions</small>]
Root --> Fluents
Root --> TimePoints[Time Points <br><small>or intervals</small>]
TimePoints --> EventCalculus[Event Calculus]
Fluents --> EventCalculus
Events --> EventCalculus
EventCalculus -->SetOfPredicates[Set of Predicates]

An event is something that happens. An event may cause the world to change.

To represent change, we distinguish:

  • events/actions: things that happen
  • fluents: facts whose truth value may change over time
  • time points or intervals: when things happen or hold

Example fluent: meaning that Shankar is in Berkley.

Example: Event of Shankar flying from San Francisco to Washington D.C.:

Event Calculus

The event calculus is a formalism for representing events, change and time.

It uses objects such as: events, fluents and time points or intervals.

To say that a fluent is true over an interval, we use that is true through the interval from to .

  • Example:
  • meanining that Shankar is in berkley from time to

To say that an event occurs over an interval: .

A possible complete set of predicates for one version of the event calculus is:

  • Fluent is true for all times between and
  • Event starts at time and ends at
  • Event causes fluent to become true at time
  • Event causes fluent to cease to be true at time
  • Fluent become true at some point between and
  • Fluent cease to be true at some point between and
  • Time point occurs before time

We can describe the effects of a flying event:

We can assume a distinguished event, Start, that describes the initial state by saying which fluents are true (using Initiates) or false (using Terminated) at the start time.

Time

In the context of these events, we can deal directly with time.

Event calculus allows us to represent:

  • Time points
  • Time intervals
  • Events that occur udring intervals
  • Flutens that hold during intervals.

Two kinds of intervals are useful:

  • Moments: intervals with zero duration
  • Extended intervals: intervals with positive duration

We can define:

  • meanining an interval is either a moment or an extended interval, but not both.

A moment has zero duration:

We can also associate moments with points on a time scale. For example, choose an arbitrary reference point:

  • where is midnight GMT on January 1, 1900

For an interval :

  • is the earliest moment of
  • is the latest moment of

The function Time maps a moment to its position on the time scale.

Then the function Duration measures the length of an interval:

For every interval i:

Then:

Therefore duration is:

To make these numbers easier to read, we also introduce a function Date, which takes six arguments (hours, minutes, seconds, day, month, and year) and returns a time point:

Two intervals if the end time of the first equals the start time of the second. The complete set of interval relations (Allen, 1983) is shown below and in Figure 10.2:

These all have their intuitive meaning, with the exception of : we tend to think of overlap as symmetric (if overlaps then overlaps ), but in this definition, only is true if begins before . Experience has shown that this definition is more useful for writing axioms.

Mental States

So far our agents have represented facts about the external world. However, intelligent agents may also need to represent mental states:

  • What an agent believes
  • What an agent knows
  • What an agent want or intend to do

Mental states are internal states that help explain or predict an agent’s behaviour.

They are useful for:

  • modelling rational behaviour
  • planning and decision-making (see Planning)
  • reasoning about other agents (see adversarial games)
  • supporting communication and cooperation

Example: suppose you have a Robot, and the robot have the intention of entering a room. But the room is locked. If the Robot has the mental state that the room is locked it could start to look for a key. His mental state guides the behavior of a robot, because it knows the clock is lock and wants to enter the room.

In order to deal with mental states, we need to introduce the concept of mental objects. A mental object is the content of an agent’s mental state.

Examples of mental objects include:

  • beliefs
  • goals
  • desires
  • intentions
  • propositions
  • concepts and ideas

A propositional attitude relates an agent to a proposition.

Examples:

For example: from superman fiction, meaning Lois knows that Superman can fly.

Suppose also that

In ordinary FOL, substitutivity of identicals could allow: .

But this inference is not always valid. Why? Because Lois may not know that: .

So the system should not automatically substitute identical terms inside knowledge or belief contexts. This motivates modal logic and other logics for representing mental states.

graph TD
    MS(Mental States)

    MS --> IS("Internal States<br><small>Explain/predict agent behavior</small>")

    IS --> MentalObjects(Mental Objects)
    IS --> PropAtt("Propositional Attitude<br><small>Believes(agent, proposition)</small>")

    MentalObjects --> ModalLogic(Modal Logic)
    PropAtt --> ModalLogic

Modal logic includes special modal operators that take sentences (rather than terms) as arguments.

For example A know P is represented with where is the modal operator for knowledge.

So in the previous example:

  • means that Lois knows that Superman can fly

However, even if we should not automatically infer that

Unless we also know: this is because knowledge contexts are intentional: how an object is described can matter to the agent.

Modal logic allows us to define axioms for knowledge. Closure under known implication:

  • If agent knows , and knows that implies , then knows: )
  • This means that ideal logical agents can draw conclusions from what they know.

Furthermore, logical agents are able to introspect on their own knowledge. If they know something, then they know that they know it:

One problem of modal logic is that it assumes logical omniscience on the part of agents. That is, if an agent knows a set of axioms, then it knows all consequences of those axioms. This is on shaky ground even for the somewhat abstract notion of knowledge, but it seems even worse for belief, because belief has more connotation of referring to things that are physically represented in the agent, not just potentially derivable.

graph LR
    ModalLogic --> ModalOperator("Modal Operator<br><small>e.g., K_Lois(CanFly(Superman))</small>")
    ModalLogic --> Axioms(Axioms for Knowledge)
    ModalLogic --> Introspection(Introspection)
    ModalLogic --> ProblemML("Problem<br><small>Logical omniscience</small>")

Reasoning Systems for Categories

Categories are the primary building blocks of large-scale knowledge representation schemes.

Two important families of category-based reasoning systems are:

  • Semantic networks
  • Description logics

Semantic Networks

Semantic networks are graph-based representations of knowledge. They represent: objects, categories, properties and relations such as “is-a”, “part-of”, and “member-of”. They support inheritance reasoning.

This is an example:

and: - then mary inherits the property .

Say that has just one leg that he may be lost it so . We can express a specific property of an object.

In order to specify that every person has a mother that is a female is specified with this double box. It could be translated in FOL as:

A limitation of simple semantic networks is that links usually represent binary relations. For example: .

This is an n-ary relation because it involves more than two arguments:

  • the flyer
  • the origin
  • the destination
  • the time

To represent this in a semantic network, we reify the event. That is, we create an event object: and connect it to its roles.

Inheritance becomes complicated when an object can belong to more than one category or when a category can be a subset of more than one other category; this is called multiple inheritance. In such cases, the inheritance algorithm might find two or more conflicting values answering the query. For this reason, multiple inheritance is banned in some object-oriented programming (OOP) languages, such as Java, that use inheritance in a class hierarchy.

Description Logic

Description logics are notations that are designed to make it easier to describe definitions and properties of categories.

Description logic systems evolved from semantic networks in response to pressure to formalize what the networks mean while retaining the emphasis on taxonomic structure as an organizing principle.

Tractability of Inference:

  • Goal: to describe definitions and properties of categories with predictable, decidable reasoning times
  • The mechanism: problem instances are solved by formalizing definitions and evaluating subsumption.

The principal inference tasks for description logics are subsumption (checking if one category is a subset of another by comparing their definitions) and classification (checking whether an object belongs to a category). Some systems also include consistency of a category definition—whether the membership criteria are logically satisfiable.

Description logics are designed to support practical reasoning about categories. They do this by restricting the kinds of logical expression we can write.

Description logic vs First-Order Logic (FOL)

  • FOL Issues: Full FOL is semi-decidable; reasoning times can be unpredictable, requiring manual “knowledge engineering” to avoid infinite loops or exponential explosions
  • DL Advantage: deliberately restricts language constructs (e.g., limiting unconstrained negation/disjunction) to maintain decidability and analyse exact computational complexity boundaries
graph TD
RSFC[Reasoning Systems for Categories]
SemanticNetworks[Semantic Networks<br><small>'is a', 'part of','member of'</small>]
DLI[Description Logic Inference]
RSFC --> SemanticNetworks
RSFC --> DescriptionLogic
SemanticNetworks --> Inherithance
DescriptionLogic --> DLI
DLI --> Subsumption
DLI --> Classification

Graph View

Backlinks