Uncertainty and Bayesian Theory

3.1 Overview of Structured Knowledge Representation Techniques

Following are various structured knowledge representation techniques. All of these techniques, in different ways, involve hierarchical representation of data.

Lists-Linked lists are used to represent hierarchical knowledge v Trees and Graphs-These are the techniques which represent hierarchical knowledge. LISP, the programming language of AI, was developed to process lists and trees. v Semantic networks-These structure have nodes and links stored as propositions. v Schemas-These are used to represent common sense or stereotyped knowledge. Ø Frames-Frames describe objects and consist of a cluster of nodes and links manipulated as a whole. Knowledge is organised in slots. Frames are hierarchically organised. Ø Scripts-Scripts describe event rather than objects. They consist of stereotypically ordered causal or temporal chain of events. v Rule-based representations-This technique is used in specific problem-solving contexts. It involves production rules containing if-then or situation-action pairs. v Logic-based representations-This may use deductive or inductive reasoning. It contains - Ø Facts and premises. Ø Set of rules of propositional logic (Boolean-dealing with complete statements) Ø Set of rules of predicate calculus (It allows use of additional information about objects in the proposition, use of variables and functions of variables.) Ø Measures of certainty-may involve Certainty Factors (eg. If symptom then (CF) diagnosis) which could be derived from expert estimation or from statistical data; Bayesian probability or Fuzzy logic (in which the concepts or information itself

has some associated certainty value).

3.2 Weak-Slot and Filler Structures

This data structure enables attribute values to be retrieved quickly. Properties of the relations are easy to describe in this data structures. It allows ease of consideration as it embraces aspects of object oriented programming.

A slot is an attribute value pair in its simplest form. A filler is a value that a slot can take which could be a numeric, string (or any data type) value or a pointer to another slot. A weak slot and filler structure does not consider the content of the representation.

We will study two types of weak slot and filler structures namely semantic nets and frames.

Knowledge Representation and Inferencing using Semantic Net

Semantic networks are an alternative to predicate logic as a form of knowledge representation. The idea is that we can store our knowledge in the form of a graph, with nodes representing objects in the world, and arcs representing relationships between those objects. The physical attributes of a person can be represented as in Fig. 3.1.

Fig. 3.1 A semantic network.

These values can also be represented in logic as: is a (person, mammal), instance (Yuvraj, person) team (Yuvraj, PWI). We have already seen how conventional predicates such as lecturer (Poonam) can be written as instance (Poonam, lecturer). Recall that isa and instance represent inheritance and are popular in many knowledge representation schemes. But we have a problem: how we can have more than 2 place predicates in semantic nets? For e.g. score (PWI, India, 20). Solution is that, create new nodes to represent new objects either contained or alluded to in the knowledge, game and fixture in the current example. Relate information to nodes and fill up slots.

Fig. 3.2 A semantic network for n-place predicate.

As a more complex example consider the sentence: Ram gave Shyam the book. Here we have several aspects of an event.

Fig. 3.3 A semantic network for a sentence.

Semantic Networks or Semantic Net

It provides graphical aids for visualizing a knowledgebase and efficient algorithms for inferring properties of an object on the basis of its category membership. v Semantic network is graph which has nodes representing objects and their categories and arc representing relationships between objects. v A typical graphical notation displays object or category names in oval or boxes and connects them with the labelled arcs. v Inheritance association (is a relationship) can be described using semantic network. It is useful for inferencing a query on the object. It can happen that a particular object is subset of more than one category (multiple inheritance association) then inferencing algorithm might find two or more conflicting values answering the query for that object. For example: whale is a mammal, Ram is a person.

Fig. 3.4 Semantic network.

Inverse links is one common inferencing technique used in semantic network. For example: ∀ P, B HasBrother (P, B) ⇔ BrotherOf (B,P) Here relationship is two way

Semantic network provide direct indexing for objects, categories and the links between them. v Semantic network can represent default values for categories. For example: If there is category WildAnimals with following descriptions, Category (WildAnimals) Then, we specify default value for legs of WildAnimals, ∀𝑥𝑥 ∈ WildAnimals ⇒ Legs (𝑥, 4) [It means that if any animal who is WildAnimals will have four legs. We need not specify again]. Tiger ∈ Wild Animals [It means that tiger has four legs].

The semantic network would like as shown in Fig. 3.5.

Fig. 3.5 Semantic network.

The major drawback of semantic network is, it represents binary relationships. Solution for this is, we need to convert n-ary associations into binary by reifying the propositions as events.

If some things are unable to expressed in semantic network then semantic network system provides procedural routines attached with the network of objects. Procedure attachment is a technique whereby a query about a certain relation result in a call to a

special procedure designed for that relation.

Inference in a Semantic Net

Basic inference mechanism: follow links between nodes. Two methods are there to do this:

Intersection search

One of the early ways that semantic nets were used was to find relation among objects by spreading activation out from each of the two nodes.

The notion that spreading activation out of two nodes and finding their intersection finds relationships among objects. This is achieved by assigning a special tag to each visited node. Many advantages are there including entity-based organisation and fast parallel implementation. However very structured questions need highly structured networks.

For e.g., in the Fig. 3.6 below intersections search can be used to answer the question like, "What is the connection between India and blue?". To answer more structural questions, the networks themselves must be highly structured.

Fig. 3.6 Intersection search in semantic network.

Representing non-binary predicates Semantic nets are used to represent relationship that appear as ground instances of binary predicates in predicate logic.

Arcs in the Fig. 3.7 can be represented in logic as: home_team (Cricket, India)

Instance (Cricket, game) Visiting_team (Cricket, India)

Fig. 3.7 Representing non-binary predicates in semantic network.

Representing some important distinctions There should be a difference between the link that defines a new entity and one that relates two existing entities:

Both nodes represent an object that exists independently of their relationships to each other. But suppose we want to represent the fact like "Anil" is taller than Raj".

The nodes H₁ and H₂ represent Anil's and Raj's height respectively. Sometimes it is useful to introduce the arc value to make the distinction clear. This is shown in the following Fig. 3.10.

The procedure that operates on nets such as this can be used to exploit the fact that some arcs such as height define new entities whereas some arcs like greater than and value merely describes the relationship among existing entities.

Fig. 3.8 Semantic network.

Fig. 3.9 Semantic network.

Fig. 3.10 Representation distinction in semantic network.

Inheritance

AI researchers have refined the notion of inheritance. It is called a specialized inferencing technique for representing properties of classes, exceptions to inherited properties, multiple super classes and structured concepts with specific relationships among the structural elements.

The isa and instance representation provide a mechanism to implement this. Inheritance also provides a means of dealing with default reasoning. Eg. we could represent:

Emus are birds. Typically birds fly and have wings. Emus run. in the following Semantic net:

Fig. 3.11 A semantic network for a default reasoning.

In making certain inferences we will also need to distinguish between the links that defines a new entity and holds its value and the other kind of link that relates two existing entities. Consider the example shown where the height of two people is depicted and we also wish to compare them.

Fig. 3.12 Two heights.

We need extra nodes for the concept as well as its value. Special procedures are needed to process these nodes, but without this distinction the analysis would be very limited.

Fig. 3.13 Comparison of two heights.

Extending Semantic Nets

Here we will consider some extensions to semantic nets that overcome a few problems or extend their expression of knowledge. Hendrix developed the partitioned semantic network. It was designed to represent the difference between the description of an individual object or process. It is also used to present description of a set of objects. These set of descriptions involves quantification.

Partitioned networks: Partitioned semantic networks allow for propositions to be made without commitment to truth and ! expressions to be quantified. Basic idea: Break network into spaces which consist of groups of nodes and arcs and regard each space as a node, Consider the following: Anil believes that the earth is flat. We can encode the proposition the earth is flat in a space and within it have nodes and arcs represent the fact (Fig. 3.14). We can have nodes and arcs to link this space and rest of the network to represent Anil's belief.

`

Fig. 3.14 Partitioned network.

Now consider the quantified expression: Every parent loves their child To represent this we: ! Create a general statement, GS, special class. ! Make node g an instance of GS. Every element will have at least 2 attributes: - a form that states which relation is being asserted. - one or more forall ( ) or exists () connections -- these represent universally quantifiable variables in such statements e.g. 𝑥, 𝑦 in parent( 𝑥 ) : child(y) loves (𝑥, 𝑦). Here we have to construct two spaces one for each 𝑥, 𝑦. Note that we can express variables as existentially qualified variables and express the event of love having an agent p and receiver 𝑏 for every parent 𝑝 which could simplify the network. Also If we change the sentence to every parent loves child then the node of the object being acted on (the child) lies outside the form of the general statement. Thus it is not viewed as an existentially qualified variable whose value may depend on the agent.

Fig. 3.15 Partitioning network.

So we could construct a partitioned network as in above figure.

In general, to represent

Create general statement GS. This is a special class.

Make node ' g ' an instance of GS.

Every element will have atleast 2 attributes -

a form that states which relations is being asserted.

for 'all ∀ ' and 'exists ∃ ' connections, that represent universally quatified variables and sentences.

Suppose now we consider statement, "Every dog has bitten a postman".

Fig. 3.16 (a) "Every dog has bitten a postman" - Partitioned semantic network.

Above partitioned semantic network has two partitions 𝑆₁ and SA. Node G is an instance of the special class of general statements about the world, comprising link statement form and one universal quantifier ∀.

Suppose we wish to make a specific statement, "The dog Tipya has bitten the postman Tukaram". Then following is the partitioned semantic net for the statement.

Fig. 3.16 (b) Partitioned semantic net.

The partitioning of semantic network makes the semantic network logically more adequate. Because of partitioning one can distinguish between individuals and sets of individuals.

Semantic network is used in building natural language front-ends for databases and for programs to deduct information from databases.

Parts of Semantic Network

Lexical: Symbols are allowed to represent vocabulary. v Structural: Symbols can be arranged in certain form. v Procedural: Edit, create, delete procedure can be applied. v Semantic: It is a way of associating meaning which semantic nets can depict.

Advantages of Semantic Nets

Semantic network can represent default values of different categories. v Semantic networks are simple and easy to understand. v Semantic networks are easy to translate in to prolog. v Semantic network arcs represent relationship between nodes. v In semantic networks the relationships are handled by pointers. v Semantic networks provide good visualization. Being diagrammatic representation they are easy to view.

Disadvantages of Semantic Networks

Semantic networks represent relationships between the objects which are only binary relations.

Nodes and arcs may not have perfect values always.

Limitations of Semantic Networks

Lack of link names standards, make it difficult to understand the net meaning. v Even the nodes naming is not standard. If a node is labelled "car" this may mean Ø The class of a car Ø A specific car Ø The concept of a car v Answering negative query like "is XYZ a car" takes a very long time. v Semantic nets are logically inadequate because they cannot define knowledge in a way logic can. v Semantic nets can be used better in representing binary relations, but not all types of relations. v Logic enhancements have been made and heuristic enhancements have been tried by attaching procedures to the nodes in the semantic nets. The procedures will be executed when the node is activated.

Knowledge Representation and Inferencing using Frames

Natural language understanding requires inference i.e., assumptions about what is typically true of the objects or situations under consideration. Such information can be coded in structures known as frames.

Frames can also be regarded as an extension to Semantic nets. Indeed it is not clear where the distinction between a semantic net and a frame ends. Semantic nets was initially used to represent labelled connections between objects. As tasks became more complex the representation needs to be more structured. The more structured the system it becomes more beneficial to use frames. A frame is a collection of attributes or slots and associated values that describe some real world entity.

Frames on their own are not particularly helpful but frame systems are a powerful way of encoding information to support reasoning. Set theory provides a good basis for understanding frame systems. Each frame represents: a class (set), or an instance (an element of a class).

Need of frames

Frame is a type of schema used in many AI applications including vision and natural language processing. Frames provide a convenient structure for representing objects that are typical to a stereotypical situations. The situations to represent may be visual scenes, structure of

complex physical objects, etc. Frames are also useful for representing common sense knowledge. As frames allow nodes to have structures they can be regarded as three-dimensional representations of knowledge.

A frame is similar to a record structure and corresponding to the fields and values are slots and slot fillers. Basically it is a group of slots and fillers that defines a stereotypical object. A single frame is not much useful. Frame systems usually have collection of frames connected to each other. Value of an attribute of one frame may be another frame.

A frame for a book is given below.

The above example is simple one but most of the frames are complex. Moreover with filler slots and inheritance provided by frames, powerful knowledge representation systems can be built.

Frames can represent either generic or frame. Following is the example for generic frame.

The fillers may have values such as computer in the name slot or a range of values as in types slot. The procedures attached to the slots are called procedural attachments. There are mainly three types of procedural attachments: if-needed, default and if-added. As the name implies if-needed types of procedures will be executed when a filler value is needed. Default value is taken if no other value exists. Defaults are used to represent common sense knowledge. Common sense is generally used when no more situation specific knowledge is available.

The if-added type is required if any value is to be added to a slot. In the above example, if a new type of computer is invented ADD_COMPUTER procedure should be executed to add

that information. An if-removed type is used to remove a value from the slot.

Frame knowledge representation

Consider the example

Fig. 3.17 A simple frame system.

Here the frames Person, Adult-Male, Cricket-Player and Cricket-Team are all classes and the frames Sachin-Mumbai and Cheteshwar-Gujarath are instances.

Distinction between Sets and Instances

It is important that this distinction is clearly understood. Cheteshwar-Gujrat can be thought of as a set of players or as an instance of a Cricket-Team. If Cheteshwar-Gujrat were a class then

Its instances would be players.

It could not be a subclass of Cricket-Team otherwise its elements would be members of Cricket-Team which we do not want. Instead we make it a subclass of Cricket-Player and this allows the players to inherit the correct properties enabling us to let the Cheteshwar-Gujrat to inherit information about teams. This means that Cheteshwar-Gujrat is an instance of Cricket-Team. BUT There is a problem here: v A class is a set and its elements have properties. v We wish to use inheritance to bestow values on its members. v But there are properties that the set or class itself has such as the manager of a team. This is why we need to view Cheteshwar-Gujrat as a subset of one class players and an instance of teams. Solution is to create MetaClasses. The basic metaclass is Class, and this allows us to define classes which are instances of other classes, and (thus) inherit properties from this class. Inheritance of default values occurs when one element or class is an instance of a class. Slots as objects How can we represent the following properties in frames? v Having attributes such as weight, age be attached and make sense. v Putting constraints on values such as age being less than a hundred. v Assigning default values v Defining rules for inheritance of values such as children inheriting parent's names. v Defining rules for computing values. v Having many values for a slot. A slot is a relation that maps from its domain of classes to its range of values. A relation is a set of ordered pairs so one relation is a subset of another. Since slot is a set, the set of all slots can be represented by a metaclass called Slot, say.

NOTE the following: (Features of frame)

Instances of SLOT are slots. v Associated with SLOT are attributes that each instance will inherit. v Each slot has a domain and range. v Range is split into two parts, one the class of the elements and the other is a constraint which is a logical expression, if it is absent it is taken to be true. v If there is a value for default then it must be passed on unless an instance has its own value. v The to-compute attribute involves a procedure to compute its value. E.g. in Position where we use the dot notation to assign values to the slot of a frame.

Transfers through the lists other slots from which values can be derived from inheritance.

Interpreting frames

A frame system interpreter must be capable of the following in order to exploit the frame slot representation: v Consistency checking-when a slot value is added to the frame relying on the domain attribute and that the value is legal using range and range constraints. v Propagation of definition values along isa and instance links. v Inheritance of default values along isa and instance links. v Computation of value of slot as needed. v Checking that only correct number of values are computed. Reasoning using frame

A frame can be attached to another frame, thereby resulting in a network of frames. v The main task of action frames is to provide facility for procedural attachment and help transforming from initial to goal state. It also helps in breaking the entire problem into sub-tasks which can be described as top-down methodology. v A task can be represented using these action frames. v Reasoning using frames is done by instantiation. Ø In instantiation process a given situation is matched with frames that are already in existence. Ø The reasoning process tries to match the frame with the situation and latter fills up slots for which values must be assigned. Ø A particular situation is depicted by assigning the values to the slots and by this, the reasoning process try to move toward a goal. v Generally, if a given slot characteristic is not present, the slot provides a default values for that characteristics. v But mostly situations are not static and there is a deviation in characteristics, in such cases the values of the corresponding slots are updated that reflect clear current situation. v Reasoning using frames allows one to move from one frame to another to match the current situation. The process builds up a wide network of frames, thereby faciliting one to build a knowledge base for representing knowledge about common-sense.

Converting: Semantic Network and Frames a) Semantic network

Fig. 3.18 Semantic network.

b) Frame

Access Procedure for Frames

Class constructor: Direct super-class v Instance constructor: Instance is connected to class by is-a slot. v Slot writer: Installs slot value.

Slot reader: Retrieves slot value.

Advantages of Frames

Frames are easy to understand. v It is easy to represent new properties and relations in frames. v Default information can be included. v Missing values can be detected in frames.

A frame collects information about an object ata single place in an organized fashion. v Frames provide a way of associating knowledge with objects. v By relating slots to other kinds of frames, a frame can represent typical structure involving an object; these can be very important for reasoning based on limited information. v Frames allow data that are stored, computed and to be treated in a uniform manner, (E,g., Age might be stored, or might be computed from BIRTHDAY.) v Frames are relatively efficient way of implementing A.I. applications.

Disadvantages of Frames

Frames are very general and do not have well-formed rule for construction and specification. v Frame building procedure takes long time. v Frames encourage baroque representations; little guide to good structuring of a domain. v Some things that can be represented in logic cannot be represented well in frames. v It is not possible to quantify over slots. For example, there is no way to represent "Some student made 100 in the exam". v Inheritance can cause trouble. v Slot fillers must be "real" data. For example, it is not possible to say that Shamu is a butcher or a baker, since there is no way to deal with a disjunction in a slot filler. v Inference tends to become complex and ill-structured. v It is necessary to repeat the same information to make it usable from different viewpoints, since methods are associated with slots or particular object types. (For example, it may be easy to answer "whom does Krishna love?" but hard to answer "who loves Radha?") v There is more than one way to break down the world into taxonomies. v Frames are good for representing static situations; they are not so good for representing fluents and things that change over time.

Declarative and Procedural Frames

A frame that just contains only description about objects is called a declarative type / factual / situation frame.

For example, a computer centre and each equipment of the centre that as shown below.

Fig. 3.19 A sample frame of a computer centre.

Fig. 3.20 Linking of sub frames.

Apart from the declarative part in a frame, it is possible to attach slots which explain how to perform things. Or it is possible to have procedural knowledge represented in a frame.

Such frames which have procedural knowledge embedded in it are called action procedure frames.

The action-frame has the following slot, **Actor slot -**Which holds information about who is performing the activity. **Object slot -**This frame has information about the item to be operated on.

**Source slot -**Source slot holds information from where the action has to begin.

Destination slot-Holds information about the place where the action has to end. **Task slot -**This generates the necessary sub-frames required to perform the operation.

For example, consider Fig. 3.21 showing a procedural frame, for cleaning the jet of a carburettor in a scooter.

Fig. 3.21 A procedural frame.

This frame merely describes that, the expert in order to clean the nozzle of the scooter has to merely perform, the following operations,

Removing the carburettor from the scooter.

Opening it up to expose all parts.

v Cleaning the nozzle.

v Refixing it in the scooter.

Since, entire operation is done on a scooter, the source and destination slots are the same viz. the scooter.

Fig. 3.22 shows that for each task slot, it is possible to have other frames (procedural) of how

to do it.

Fig. 3.22 Linking of procedure sub-frames.

3.3 Strong Slot and Filler Structures

To avoid the difficulties with Frames and Nets, Schank and Rieger offered network-like representations that would have implied uses and built-in semantics conceptual dependencies and scripts. These representations are termed as strong slot and filler structures.

Strong Slot and Filler Structures typically represent links between objects according to more rigid rules.

The specific notions of what types of object and relations between them, are provided in this structure.

These structures represent knowledge about common situations.

Knowledge Representation and Rule based Inferencing using Conceptual Dependency (CD)

A number of authors in AI have addressed the question of the 'concept'-based organization of knowledge. To know this idea, we will consider a verb-oriented organization of knowledge proposed by Schank which is Conceptual Dependency Grammar and then the Conceptual graphs.

Conceptual dependency Grammar is a powerful representation formalism, which has been used in a number of Virtual Reality (VR) Systems. In a VR system,

The end user of the system can interact with the system in a manner analogous to interacting with another human being at a 'physical' level. v A VR end user can 'bounce' a ball on a VR screen, and can catch a ball thrown by the system. v A VR end user can ride a bike. Conceptual dependency was originally developed to represent knowledge acquired from natural language input.

The goals of this theory are,

To be independent of the words used in the original input. It has been argued that the representation (CD) is independent of the language in which the sentences were originally stated. v To help in the drawing of inference from sentences. v That is to say: For any 2 (or more) sentences that are identical in meaning there should be only one representation of that meaning. Conceptual Dependency originally developed to represent knowledge acquired from natural language input. Conceptual dependency was derived as a form of semantic network that would have specific types of links to be used for representing specific pieces of information in English sentences, the action of the sentence, the objects affected by the action or that brought about the action and the modifiers of both actions and objects. CD has been used by many programs that portent to understand English (some programs are MARGIE, SAM, PAM). CD was developed by Schank et al..

CD provides

A structure into which nodes representing information can be placed a specific set of primitives at a given level of granularity. v The sentences are represented as a series of diagrams depicting actions using both abstract and real physical situations. v The agent and the objects are represented v The actions are built up from a set of primitive acts which can be modified by tense.

Primitives Acts in CDs

CD defined 11 primitive actions, called ACTs

Every possible action can be categorized as one of these 11 primitives.

An ACT would form the center of the CD, with links attaching the objects and modifiers.

Examples of Primitive Acts are,

ATRANS

Transfer of an abstract relationship. e.g. give. PTRANS

Transfer of the physical location of an object. e.g. go. PROPEL

Application of a physical force to an object. e.g. push. MTRANS

Transfer of mental information. e.g. tell. MBUILD

Construct new information from old. e.g. decide. SPEAK

Utter a sound. e.g. say. ATTEND

Focus a sense on a stimulus. e.g. listen, watch. MOVE

Movement of a body part by owner. e.g. punch, kick. GRASP

Actor grasping an object. e.g. clutch. INGEST

Actor ingesting an object. e.g. eat. EXPEL

Actor getting rid of an object from body. e.g. sweat, ????. Six primitive conceptual categories provide building blocks which are the set of allowable dependencies in the concepts in a sentence:

**PP -**Real world objects. **ACT -**Real world actions. **PA -**Attributes of objects. **AA -**Attributes of actions. **T -**Times. **LOC -**Locations.

Connecting all these things together,

Consider the example,

For example: Consider statement,

Bhavani gave shivaji a sword.

Following is CD representation of above statement.

Arrows indicate the direction of dependency. v Letters above indicate certain relationships which are as follows - Ø P-Indicates past tense. Ø O-Object. Ø R-Recipient-donor. v Double arrows ( ⇔) indicate two-way links between the actor (PP) and action (ACT). v The actions are built from the set of primitive acts (see above). Ø These can be modified by tense etc. v The use of tense and mood in describing events is extremely important and Schank introduced the following modifiers : v 𝐩 - past v f-future v t-transition Ø t_s- start transition Ø 𝑡_𝑓- finished transition v 𝐤 - continuing v? - interrogative Ø /-negative

delta-timeless v c-conditional the absence of any modifier implies the present tense. v I-instrument e.g. eat with a spoon. v D-destination e.g. going home. Example: So the present tense of above statement in example 1 becomes.

Bhawani gives Shivaji a sword and the CD representation is, v The ⇔ has an object (actor), PP and action, ACT. That is PP ⇔ ACT. v The triple arrow (⇔) is also a two link but between an object, PP and its attribute, PA. I.e. PP ⇔ PA. It represents is 𝑎 type dependencies. v e.g. Dave ⇔ lecturer, Dave is a lecturer. Rules used in CD

Primitive states are used to describe many state descriptions such as height, health, mental state, physical state. v You can also specify things like the time of occurrence in the relationship. v There are many more physical states than primitive actions. They use a numeric scale. v The rules that are used for representing the knowledge in conceptual dependency are shown in Fig. 3.23. v Here, the first column contains the rules, the second contains examples of their use; and the third contains an English version of each example.

The rules shown in Fig. 3.23 can be interpreted as follows -

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

Fig. 3.23 CD dependencies.

2. **Rule 2 -**This rule describes the relationship between PP and PA. Height are represented in CD as numeric scales. Here by showing that height of John is greater than average we indicate that "John is tall".
3. **Rule 3 -**This rule describes the relationship between two PPs. One or which belongs to the set defined by the other. Here, it is shown that John is a doctor.
4. **Rule 4 -**This rule shows a relationship between a PP and a PA, i.e., between a PP and an attribute that has already been predicated of it. The direction of arrow is toward the PP. Here, it is show that "boy is nice".
5. **Rule 5 -**This rule gives the relationship between two PPs, 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-BT). Again direction of arrow is towards PP i.e., dog as in example, it is shown "John's dog".
6. **Rule 6 -**This rule describes the relationship between ACT and PP i.e., the object of that ACT. The direction of the arrow is toward the ACT, since, the contest of the specific ACT determines the meaning of the object relation. It is shown here, "John pushed the cart".
7. **Rule 7 -**It describes the relationship between an ACT and the source and the recipient of the ACT. In the example, "John took the book from Mary". Mary is source, book is an object and John is recipient.
8. **Rule 8 -**This rule 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 object. Here, the example is "John ate ice cream with a spoon". i.e., John's action is eating and instrument used is spoon.
9. **Rule 9 -**This rule describes the relationship between an ACT and its physical source and destination. In the example, it is shown that the statement John fertilized the fields" Here, John is physical source, fertilize is an act and field is the destination.
10. **Rule 10 -**It represents live relationship between a PP and a state in which it started and another in which ended. As here, "The plants grow". One PP (object) is plant and there are its two states i.e., size = x and size > x i.e., showing that initially size of plant was 𝑥 but now in new state, its size is greater than 𝑥, so plants grow.

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

**Rule 12 -**It describes the relationship between a conceptualization and the time at which the event it describes occurred. For example "John ran yesterday" in which it is shown that John run, but past is shown by P so, John ran and day is indicated above arrow yesterday.

**Rule 13 -**Describes the relationship between one conceptualization and another that is the time of the first. The example, "While going home I saw a frog" shows how CD exploits a model of the human information processing system, see is represented as the transfer of information between the eyes and the conscious processor.

Rule 𝟏𝟒**-**This rule describes the relationship between a conceptualization and the place at which it occurred.

Examples

Ram ⇔ height( +10 ). Ram is the tallest. Ram ⇔ height(< average). Ram is short. Ravana ⇔ health( -10 ). Ravana is dead Monster. Ravana ⇔ mental_state(-10). Ravana is sad. Vase ⇔ physical_state(-10) The vase is broken

Following are some of the examples

1. PP ⇔ ACT Raj ⇔ PTRANS Raj walk
2. PP ⇔ PA Raj ⇔ Scientist Raj is a scientist
3. PP Boy ↑ ↑ A handsome boy PA handsome
4. PP parrot ⇑ ⇑ Raj's parrot. PP Raj

O

5. ACT ← PP P O Raj ⇔ PROPEL ← door Raj pulled the door.

6. Raj drunk coke with a straw.

7. Raj fertilized the field

8. The plants grow

9. X shot y

10. While going home she saw him

11. I heard tiger in the jungle CD can describes the relationship between a conceptualization and the place of which it occurred.

Now let us consider a more complex sentence:

Since smoking can kill you, I stopped. Let's look at how we represent the inference that smoking can kill:

Use the notion of one to apply the knowledge to. v Use the primitive act of INGESTing smoke from a cigarette to one. v Killing is a transition from being alive to dead. We use triple arrows to indicate a transition from one state to another. v Have a conditional, 𝑐 causality link. The triple arrow indicates dependency of one concept on another.

Fig. 3.24 “Since smoking can kill you, I stopped”.

To add the fact that I stopped smoking

Use similar rules to imply that I smoke cigarettes. v The qualification 𝑡_𝑓𝑝 attached to this dependency indicates that the instance INGESTing smoke has stopped. Advantages of CD

Using these primitives involves fewer inference rules. v Many inference rules are already represented in CD structure. v The holes in the initial structure help to focus on the points still to be established. v The ACT primitives help in representing wide knowledge in a succinct way. In CD representation the verbs that use to transfer mental information such as, see, hear, learn, inform, remember, all can be represented by a single ACT primitive MTRANS. v The main goal of CD representation is to make explicit of what is implicit. That is why every statement that is made has not only the actors and objects but also time and location, source and destination. v CD brought forward the notion of language independence because all ACTs are language-independent primitives. CD is a special purpose extension of semantic network in which specific primitives were used in building representations.

Disadvantages of CD

Knowledge must be decomposed into fairly low level primitives. v Impossible or difficult to find correct set of primitives. v A lot of inference may still be required. v Representations can be complex even for relatively simple actions. Consider : Dave bet Frank five pounds that Wales would win the Rugby World Cup. Complex representations require a lot of storage

Applications of CD

MARGIE (Meaning Analysis, Response Generation and Inference on English) - model natural language understanding.

SAM (Script Applier Mechanism) - Scripts to understand stories. See next topic.

PAM (Plan Applier Mechanism) - Scripts to understand stories.

Schank et al. developed all of the above.

Knowledge Representation and Interfacing using Scripts

The other structured representation developed by Schank (along with Abelson) is the script.

A script is a structure that prescribes a set of circumstances (stereotyped sequences) which could be expected to follow on from one another.

It is similar to a thought sequence or a chain of situations which could be anticipated. It could be considered to consist of a number of slots or frames but with more specialized roles.

Scripts are useful and handy because,

In general the events tend to occur in known runs or patterns. v Scripts represent existing causal relationships between events. v Scripts can represent entry conditions which exist and which allow an event to take place. v There are certain prerequisites exist upon events taking place. e.g. when a child progresses through a kindergarten scheme or when a girl purchases a dress.

The components of a script

Entry Conditions

These must be satisfied before events in the script can occur. Results

Conditions that will be true after events in script occur. Props

Slots representing objects involved in events. Roles

Persons involved in the events. Track

Variations on the script. Different tracks may share components of the same script.

Scenes v The sequence of events that occur. Events are represented in conceptual dependency form. Features of Scripts

For a particular script when applying it, it must be activated and the activation depends on its significance. v When certain topic is mentioned in passing, a pointer to that script could be held. v When the topic is important, then the script should be opened. v The negative aspect is that if too many active scripts exist then one might have too many windows open on the screen or too many recursive calls in a program. v Provided that events follow a known trail we can use scripts to represent the actions involved and use them to answer detailed questions. v Different trails may be allowed for different outcomes of Scripts (e.g. The bank robbery goes wrong). Advantages of Scripts

Scripts have ability to predict events. v Scripts provide an ability for default reasoning when information is not available that directly states that an action occurred. v In scripts a single coherent interpretation may be build up from a collection of

observations.

Disadvantages of Scripts

Scripts are less general than frames. v Scripts are might not be suitable to represent all kinds of knowledge.

Script Example

Construct a script for going to the movie from the viewpoint of movie goer.

3.4 CYC

The Concept

CYC is a big prospective attempt to form a very large knowledgebase aimed at capturing common sense reasoning. v The initial goal of CYC was to capture knowledge from a hundred randomly selected articles in the Encyclopaedia Britannica. v In CYC both Implicit and Explicit knowledge is encoded.

CYC puts emphasis on study of underlying information (assumed by the authors) but not needed to tell to the readers. Example: Suppose we read that Wellington learned of Napoleon's death. Then we (humans) can conclude Napoleon never knew that Wellington had died.

How do human do this?

Humans require special implicit knowledge or common sense such as,

We only die once. v You stay dead. v You cannot learn of anything when dead. v Time cannot go backwards.

Why build large knowledge bases?

Brittleness

The specialised knowledge bases are brittle. It is hard to encode new situations and non-graceful degradation in performance. Common sense based knowledge bases should have a firmer foundation. Form and Content

Such type of knowledge representation may not be suitable for AI. Common sense strategies could point out where difficulties in content may affect the form.

Shared Knowledge

There should be greater communication among systems with common bases and assumptions.

CYC Coding

CYC can be coded simply by hand. There are special CYCL language such as LISP which can be used for coding. Frame based coding, Multiple inheritance, Generalised inheritance (where any link is not just isa and instance), Slots which are fully fledged objects, can also be used for CYC coding.

For Example: Construct a script for going to the movie from the view point of movie goer.

3.5 Schema

The overall design of the knowledge database is called the knowledge base schema. Schema are changed infrequently, if at all. v A database schema corresponds to the programming language type definition. A variable of a given type has a particular value at given instance which corresponds to an instance of a database schema. v Knowledge-base systems have several schemas, partitioned according to the levels of abstraction. At the lowest level is the physical schema, at the intermediate level is the logical schema and at the highest level is a subschema. In general, knowledge-base system support one physical schema, one logical schema and several subschemas. v In order for a program to be able to participate intelligently in a dialogue it must be able to participate not only its own beliefs about the world, but also its knowledge of the other dialogue participant's belief about the world, that person's belief, about the computer's belief and so forth. v To make computational models of belief, it is useful to divide the issue into two parts-those beliefs that can be assumed to be shared among all the participants in a linguistic event and those that cannot. v Shared beliefs can be modeled without and explicit notion of belief in the knowledge base. All that we need to do is to represent the shared beliefs as facts and they will be accessed whenever knowledge about anyone's belief is needed. The representation technique used here to represent shared belief is known as schema.

Information-base contains a catalog having many schemas. The presence of multiple schemas allows different applications and different users to work independently. If

schema is not set explicitly, a default schema associated with the user identifier is used, so different users see their own schemas. v Another use of schemas is to allow multiple versions of an application-one a production version and other versions being tested to be used on the same knowledge-base.

3.6 Introduction to Handling Uncertainity

A agent working in real world environment almost never has access to whole truth about its environment. Therefore, agent needs to work under uncertainity.

Earlier agents make the epistemological commitment that either the facts (expressed as prepositions) are true, false or else they are unknown. When an agent knows enough facts about its environment, the logical approach enables it to derive plans, which are guaranteed to work.

But when agent works with uncertain knowledge then it might be impossible to construct a complete and correct description of how its actions will work. If a logical agent can’t conclude that any particular course of action achieves its goal, then it will be unable to act.

The right thing logical agent can do is, take a rational decision. The rational decision depends on following things,

The relative importance of various goals. v The likelihood and the degree to which, goals will be achieved.

Dealing with Uncertain Knowledge and Probability Theory

An agent would possess some early basic knowledge of the world (Assume that knowledge is represented in first order logic sentence). Using first order logic to handle real word problem domains fails for three main reasons as discussed below,

Laziness

It is too much work to list the complete set of antecedents or consequents needed to ensure an exception less rule and too hard to use such rules.

Theoretical ignorance

A particular problem may not have complete theory for the domain.

Practical ignorance

Even if all the rules are known, particular aspects of problem are not checked yet or some details are not considered at all (missing out the details).

The agent's knowledge can provide it with a degree of belief with relevant sentences. To this degree of belief probability theory is applied. Probability assigns a numerical degree of belief between 0 and 1 to each sentence.

Probability provides a way of summarizing the uncertainity that comes from our laziness and ignorance.

Assigning probability of 0 to a given sentence corresponds to an unequivocal belief saying that sentence is false. Assigning probability of 1 corresponds to an unequivocal belief saying that the sentence is true. Probabilities between 0 and 1 correspond to intermediate degree of belief in the truth of the sentence.

The beliefs completely depends on precepts of agent at particular time. These precepts constitute the evidence on which probability assertions are based. Assignment of probability to a proposition is analogous to saying that whether the given logical sentence (or its negation) is entailed by the knowledge base rather than whether it is true or not. When more sentences are added to knowledge base the entailment keeps on changing. Similarly the probability would also keep on changing with additional knowledge.

All probability statements must therefore, indicate the evidence with respect to which the probability is being assessed. As the agent receives new precepts, its probability assessments are updated to reflect the new evidence. Before the evidence is obtained, we talk about prior or unconditional probability; after the evidence is obtained, we talk about posterior or conditional probability. In most cases, an agent will have some evidence from its precepts and will be interested in computing the posterior probabilities of the outcomes it cares about.

Uncertainty and rational decisions