Semantic Nets

• Graphical structure for representing knowledge in terms of a network of nodes and arcs

• nodes usually represents objects, concepts or situations in the domain, and the arcs represent the relation between them.

Example: All robins are birds

adding (1) Clyde is a robin
(2) birds have wings

• deduction can be made by tracing the is-a arcs 0 inheritance hierarchies.

• e.g. in the above net, we can deduce Clyde is a bird and so has wings (property inheritance).

• Clyde is an instance of robin.

Clyde owns a nest:

A semantic net is a representation

in which

• lexically, there are nodes, links and application-specific link labels

• structurally, each link connects a tailnode to a head node.

• semantically, the nodes and links denote application-specific entities.

with constructors that

• construct a node

• construct a link, given a link label and two nodes to be connected

with readers that

• produce a list of all links departing from a given node

• produce a list of all links arriving at a given node

• produce a tail node, given a link

• produce a head node, given a link

• produce a link label, given a link

More Examples

Representation of an n-place predicate

• only binary relation can be encoded in semantic net.
  e.g. Clyde owned nest-1 from spring until fall
  cannot be represented. Need a 4-place predicate.
  own(Clyde, nest-1, spring, fall)

• Case frame: represent situations and actions in nodes, as well as objects and sets of objects

• each situation node (n-place predicate name) can have a set of out-going arcs, called a case frame which specifies the various arguments to the situation predicates.

  

• Allows instance nodes, like own-1, to inherit expectations about,and even default values for certain of their attributes (cf. frame structures)

Reasoning with Semantic Nets

• no formal semantics 0 no agreed-upon notion of what a given representational structure means (as in logic)

• meaning is assigned to network structure only by the nature of the procedures that manipulate the network.

• Matching network structure: A network fragment is constructed, representing a sought-for object or a query, and then matched against the network database to see if such an object exists.

Example: What does Clyde own?

• the matcher can make inferences during the matching process to create network structure that is not explicitly present in the network.

Example: Is there a bird who owns a nest?

Example: (Geometric Analogy Net)

To establishes analogies between relations of geometric objects.

Problems of Semantic Nets

1. No distinction in network formalism between an individual and a class of individuals.

   1. Clyde is a robin

   2. robins are birds (referring to all members of the class)

   3. robins are endangered species (referring to the class itself)

   4. birds have wings

   5. naturalists study endangered species

   
   Clyde has wings?
   Clyde is studied by Naturalist?
   
   
   

2. The size of network database associated with non-trivial amount of knowledge representation may cause computational problem.

3. Not formalized. No common principles applied to all networks. Link structures varied among networks

4. Problems with semantics of network structures

   • what does a node really mean?

   • Is there a unique way to represent an idea?

   • How is the passage of time to be represented (temporal reasoning)

   • How does one represent things that are not facts about the world but rather ideas or beliefs

   • what are rules about inheritance of properties in networks?

Advantage of Semantic Nets

• node-and-link captures something essential about symbols and pointers in symbolic computation (e.g. in LISP).

• captures something essential about association in the psychology of memory.

Semantic Nets in LISP

• every node is a symbol in LISP.

• every out-going arc is a property of the symbol.

(setf (get 'clyde 'is-a) 'robin)

(setf (get 'robin 'is-a) 'bird)

(setf (get 'own-1 'is-a) 'ownership)

(setf (get 'own-1 'owner) 'clyde)

(setf (get 'own-1 'start-time) 'spring)

(setf (get 'own-1 'end-time) 'fall)

(setf (get 'own-1 'ownee) 'nest-1)

(setf (get 'nest-1 'is-a) 'nest)

(setf (get 'spring 'is-a) 'time)

(setf (get 'fall 'is-a) 'time)

(setf (get 'ownership 'is-a) 'situation)

(setf (get 'bird 'has-part) 'wings)

property inheritance

(defun getprop (symbol prop)
(cond ((get symbol prop))
(t (getprop (get symbol 'is-a)

prop)))) ;trace is-a link

>(getprop 'clyde 'has-part)
wings

Semantic Primitives

• knowledge representation formalism: ways of expressing the kind of things we know.

• vocabulary used within that formalism?
  what predicates are to be used? (in logic system)
  what node and link type should be provided? (semantic nets)

Conceptual Dependency Theory (R. Schank)

• provide a representation of all actions using a smaller number of primitives.

• task independence.

Requirements:

1. Representation is unambiguous, even though the input may contain certain ambiguity (both syntactic or semantic ambiguity)
   e.g. I saw the Grand Canyon flying to New York.
   The old man's glasses were filled with sherry.
   The speaker of an ambiguous sentence usually intends an unambiguous meaning.
   Representation is expected to reflect only the most likely version.

2. Representation is unique 0 distinct sentence with the same conceptual content should have the same representation.
   e.g. I want a book.
   I want to get a book.
   I want to have a book.
   are represented the same way.

There are 11 primitive ACTS (Schank & Abelson) to obtain unique, unambiguous representation of meanings.

1. Physical Acts

• PROPEL apply a force to a physical object

• MOVE move a body part

• INGEST take something to the inside of an animate object

• EXPEL force something out from inside an animate object

• GRASP grasp an object physically
  
  
  

2. Acts characterized by resulting state changes

• PTRANS change the location of a physical object

• ATRANS change an abstract relationship, such as
  possession or ownership, with respect to an object
  
  
  

3. Acts used mainly as instruments for other Acts

• SPEAK produce a sound

• ATTEND direct a sense organ towards a stimulus.
  
  
  

4. Mental Acts

• MTRANS transfer information

• MBUILD construct new information from old ones.

There are several other categories, or concept types, besides the primitive ACTS in the representational system.

1. Picture Producer (PP)

• physical objects

• special cases: winds, human memory

2. Picture Aiders (PAs)

• attributes of objects

3. Times

4. Locations

5. Action Aiders (Aas)

• attributes of ACTS

Conceptualizations

• rules for combining the above categories into representation of meaning

• 2 basic kinds:

  • an actor (PP) doing a primitive ACT.
    e.g. John eats

  • an object (PP) and a description of its state (a picture aider PA)
    e.g. John is hungry

Remarks:

1. The primitive elements that occur in conceptualizations are not words, e.g. eat, but concepts, e.g. ingest.

2. They reflect a level of thought underlying language, rather than the language itself.

3. Representation in CD is thus said to be language-free.

Example1 (Schank)

Example2 (Schank)

Each primitive ACT entails its own set of inferences.

e.g. X PTRANSed Y from W to Z

inference:

Y is now located at Z

Y is no longer at location W

IF Z=X, or Z is human and requested the PTRANS, then Z will probably do whatever one ordinarily does with Y. Moreover, Z probably will become pleased by doing this.

CD Diagram

CD diagram is a semantic network that utilizes primitives proposed by Schank to represent meaning in a sentence.

Rule 1 describes the relationship between an actor and the event he or she causes. This is a two-way dependency, since neither actor nor event can be considered primary. The letter p above the dependency link indicates past tense.

Rule 2 describes the relationship between a PP and a PA that is being asserted to describe it. Many state descriptions, such as height are represented in CD as numeric scales.

Rule 3 describes the relationship between 2 PP's, one of which belongs to the set defined by the other.

Rule 4 describes the relationship between a PP and an attribute that has already been predicated of it. The direction of the arrow is toward the PP being described.

Rule 5 describes the relationship between 2 PP's, one of which provides a particular kind of information about the other. The three most common types of information to be provided in this way are possession (shown as POSS-BY), location (shown as LOC), and physical containment (shown as CONT). The direction of the arrow is again toward the concept being described.

Rule 6 describes the relationship between an ACT and the PP that is the object of that ACT. The direction of the arrow is toward the ACT since the context of the specific ACT determines the meaning of the object relation.

Rule 7 describes the relationship between an ACT and the source and the recipient of the ACT.

Rule 8 describes the relationship between an ACT and the instrument with which it is performed. The instrument must always be a full conceptualization (i.e. it must contain an ACT), not just a single physical source and destination.

Rule 9 describes the change of location of the PP that is the object of the ACT.

Rule 10 represents the relationship between a PP and a state in which it started and another in which it ended.



Rule 11 describes the relationship between one conceptualization and another that causes it. Notice that the arrow indicate dependency of one conceptualization on another and so point in the opposite direction of implication arrows. The 2 forms of the rule describe the cause of an action and the cause of a state change.

Rule 12 describes the relationship between a conceptualization and the time at which the event if describes occurred.

The set of conceptual tenses

Example:

Conceptual Graphs

J F Sowa.

No labeled arcs, use conceptual relation nodes instead.

2 kinds of nodes:

Concept nodes (boxes)

concrete object, e.g. cat, telephone etc.

abstract object, e.g. love, beauty etc.

Relation nodes (ellipse)

relation involving one or more concepts.

Every concept is a unique individual of a particular type.

Each concept box is labeled with a type label.
e.g. a node labeled dog represent some individual of that type.
type dog is a subtype of carnivore, which is a subtype of mammal

the type label & individual label is separated by ":"

use marker (a unique token, start with '#') to separate an individual from its name.

Example:

Her name was McGill and she called herself Lil, but everyone knew her as Nancy.

Example:
The dog scratches its ear with its paw.

Type Hierarchy

A partial ordering on the set of types

t < s, t a subtype of s
s a supertype of s

If hierarchy is a lattice, common subtype and common supertype by finding the greatest lower bound (glb) and least upper bound (lub) of the lattice elements.

A universal type T and an absurd type ^.

Generalization and Specialization

form new graphs from existing ones (either specializing or generalizing an existing graph)

4 rules:

Copy 0 form a new graph g, that is an exact copy of g₁.

Restrict 0 concept nodes in a graph to be replaced by a node representing their specialization.

a concept labeled with a generic marker may be replaced by an individual marker

a type label may be replaced by one of its subtype.

Join 0 combine two graphs into a single graph (by combining identical nodes in the 2 graphs)

Simplify 0 delete duplicate relation (as a result of join).

NB. These rules are not rules of inference, i.e. they does not guarantee true graphs will be derived from true graphs.

Generalization and Specialization allow property inheritance.

Proposition Nodes

can define relation between propositions
e.g. Tom believes that Jane likes pizza

use a concept type "proposition"
(take a set of conceptual graphs as its referent)

indicated as a box containing the set of graphs.

has a special "experiencer" link.

easy to represent conjunctive concepts by combining the propositions. Even unary operator: