KNOWLEDGE REPRESENTATION AND REASONING UNIT 4.pptx

KNOWLEDGE REPRESENTATION AND REASONING UNIT 4 - PROCESSES Presented By Dr. SK. Karthika Assistant Professor Department of CSE QIS College of Engineering and Techn...

KNOWLEDGE REPRESENTATION AND REASONING UNIT 4 - PROCESSES Presented By Dr. SK. Karthika Assistant Professor Department of CSE QIS College of Engineering and Technology, Ongole TOPIC 1 – TIMES, EVENTS AND SITUATIONS Introduction to Process-Based Logic: Charles Sanders Peirce: First modern logician to distinguish processes and events as entities separate from the objects involved. Alfred North Whitehead (1929): Advanced the idea by making processes the primary entities in his ontology. Traditional Logic vs. Process-Based Logic: Traditional Logic: Elementary logic books prioritize stable objects over processes. Example: The sentence "Brutus stabbed Caesar" is typically translated to the formula stabbed(Brutus, Caesar). TOPIC 1 - Continued Limitations of Traditional Logic: 1.Tense Sensitivity: 1.Traditional formulas do not account for different tenses (present, past, future). 2.Details and Relations: 1.Cannot incorporate details such as adverbs (e.g., "violently") or prepositional phrases (e.g., "with a shiny knife"). 3.Cross-References: 1.Inadequate for supporting cross-references from other sentences (e.g., "The stabbing was violent"). Implications: The simplistic translation in traditional logic overlooks the complexity and detail inherent in natural language. TOPIC 1 - Continued Rediscovery Across Fields: 1.During the 1960s, the need to treat events as first-class entities was independently rediscovered in: 1.Linguistics 2.Philosophy 3.Artificial Intelligence Philosophy: 2. Donald Davidson (1967): 1. A key advocate for event semantics. 2. Campaigned for the inclusion of quantified variables to represent events in philosophical discourse. Linguistics: 3. Terence Parsons (1990): 1. Applied event variables to linguistics. 2. Example: Used event variables to represent sentences like "Brutus stabbed Caesar." TOPIC 1 - Continued Importance of Event Semantics: 1.Provides a more nuanced representation of actions and occurrences. 2.Enhances the ability to capture the complexity of natural language in logical and computational frameworks. TOPIC 1 - Continued Existence of Interval: There exists an interval I where I is before now. Existence of Time: There exists a time t, which is contained within I. Existence of Event: There exists a stabbing event e. The agent of e is Brutus. The patient of e is Caesar. e culminates at time t. Complexity vs. Simplicity: Parson's representation is more complex than the simple stabbed (Brutus,Caesar) stabbed (Brutus, Caesar) stabbed (Brutus,Caesar) relation. It captures more of the meaning in the English sentence through the use of predicates and variables. TOPIC 1 - Continued Situations and Events Historical Background: Silvio Ceccato (1961): First computational linguist to map nouns, verbs, and adjectives to nodes with equivalent status using correlational nets. Semantic Networks: Quillian (1966) and Schank & Tesler (1969) also used equivalent concept nodes to represent basic content words. Conceptual Graphs: Integration of Logic and Networks: Combines Peirce's logic with AI's semantic networks. Represents attributes and events with concept nodes similar to those used for concrete things. TOPIC 1 - Continued Example Sentence: Sentence: "Brutus stabbed Caesar violently with a shiny knife." Conceptual Graph Representation: Concept Nodes: Agent (Agnt): Brutus Patient (Ptnt): Caesar Instrument (Inst): Knife Attribute (Attr): Shiny Manner (Manr): Violently Thematic Roles: Links verbs and attributes using relations similar to thematic roles in linguistics. Situation and Tense: Surrounding concept: Situation Tense relation: Past TOPIC 1 - Continued TOPIC 1 - Continued TOPIC 1 - Continued Multiple Occurrences Past Relation in Conceptual Graphs: Situation Box: The Past relation attached to a Situation concept indicates that everything inside the box occurred in the past. Direct Attachment to Verb: Verb-Level Indication: The Past relation can be directly attached to the verb to indicate that the event expressed by the verb occurred in the past. Other Entities: This method does not explicitly specify the time of occurrence for other entities involved in the event. Temporal Flexibility: Explicit Timing: Allows for temporal information to be either broadly applied to the entire situation or specifically to the event described by the verb. TOPIC 1 - Continued TOPIC 1 - Continued TOPIC 1 - Continued TOPIC 1 - Continued ADVERBIAL MODIFIERS TOPIC 1 - Continued That syntactic distinction may signal a difference in the conceptual relation: Manner. Adverbs, which usually modify verbs, commonly express the manner of performance or happening of some occurrent. Attribute. Adjectives, which usually modify nouns, commonly express an attribute of some continuant. TOPIC 1 - Continued Describing the Same Activity with Different Verbs Verbs: Spending, outlining, and speaking describe the same activity. Speaking: Determines the form of the activity, recognizable even without understanding the language. Outlining: Refers to the results of the activity (Secondness). Spending time: Refers only to the duration of the activity, ignoring its nature (a different aspect of the result). In conceptual graphs, these verbs would be represented by three separate concepts with coreference links. The concept [Speak] represents the form. The concepts [Outline] and [SpendTime] refer to the same activity, emphasizing different effects. TOPIC 1 - Continued Describing Actions by Form, Effects, and Intentions Firstness (Form): Describes the observable form of an action. Example: A person may walk into a forest. Secondness (Effects): Describes the results or effects of an action. Example: A person disappears from view. Thirdness (Intentions): Describes the agent's intentions behind an action. Example: If the intention was to disappear, walking becomes an act of hiding. TOPIC 1 - Continued Examples of Action Descriptions Stabbing, Killing, and Murdering: Brutus stabbed Caesar: Describes the form of the action (Firstness). Recognized by objective criteria at the instant it happens. Brutus killed Caesar: Describes the result of the action (Secondness). Requires a second event of dying to occur. Brutus murdered Caesar: Depends on the motives of the agent (Thirdness). Interpretation may require a judge, jury, and a lengthy trial. TOPIC 1 - Continued Conceptual Graphs and Action Descriptions In conceptual graphs, different verbs for the same action are represented by separate concepts. Coreference links are drawn between these concepts to show their relationship. Example: [Speak]: Represents the form. [Outline]: Refers to the same activity with emphasis on the results. [SpendTime]: Refers to the same activity with emphasis on its duration. The classification of actions by Firstness, Secondness, and Thirdness helps in understanding different perspectives of the same activity. Visual Elements: Include diagrams showing conceptual graphs with nodes and coreference links. Use color-coded nodes to represent different verbs and their relationships. Provide examples to illustrate the difference between Firstness, Secondness, and Thirdness in action descriptions.  TOPIC 2 – CLASSIFICATION OF PROCESSES Processes can be described by their starting and stopping points and by the kinds of changes that take place in between. TOPIC 2 - Continued In language, the features of tense arid aspect relate the event described by a verb to the type of process and to the reference times of one or more observers. The simple tenses - past, present, and future - relate the time of an event to the time of the speech. The compound tenses, such as past perfect or future perfect, involve an additional reference time in some real or hypothetical past or future. Aspect describes the initiation, continuation, or completion of some action with respect to the reference times. As in the example of Farmer Brown, whether an action is continuing or completed may depend on some agent's intentions. The definitions of many verbs depend on the intentions of their agents, and the same physical process described by different verbs can be classified in very different ways. Different classifications, in turn, have different implications: depending 'on the verb that is applied, Brown may be praised for a success or TOPIC 2 - Continued FLUENTS. Isaac Newton used the word fluent for a time- dependent physical quantity, such as position, pressure, or temperature. Leibniz developed the more general notion of a function, whose values could depend on an argument of any type, including time. Newton's fluents can be considered special cases of Leibniz’s functions. They can also be considered indexicals whose referents depend on the current context. TOPIC 2 - Continued TOPIC 2 - Continued In AI, the term fluent has been generalized beyond Newton's physical quantities and beyond time-dependent functions to any kind of state or situation-dependent property. Even the property of being president can be considered a fluent, as in the following example: TOPIC 2 - Continued BASIC DISTINCTIONS In his book Features and Fluents, Erik Sandewall presented a comprehensive analysis of fluents, their representation in logic, and the techniques for reasoning about them. For knowledge representation, the interactions of fluents with time, change, sequencing, and context are· major concerns. TOPIC 2 - Continued Sandewall presented a list of distinctions for classifying processes according to the complexity of their interactions with fluents: 1. Discrete or Continuous 2. Linear or Branching 3. Independent or Ramified 4. Immediate or Delayed 5. Sequential or Concurrent 6. Predictable or suprising TOPIC 2 - Continued 7. Normal or Equinormal 8. Flat or Hierarchical 9. Timeless or Time bound 10. Forgetful or Memory bound  TOPIC 3 - Procedures, Processes, and Histories Discrete processes can be simulated by digital computers, but continuous processes are more naturally simulated by analog computers. Yet if the time step is small enough, the granularity of a digital simulation might not be noticeable. Movies and television, for example, represent continuous motion by a sequence -if discrete frames. State-transition diagrams, which represent states by circles and events by arrows that connect the circles, are a common representation for discrete processes. Finite-state machines are the simplest and most widely used version of state-transition diagrams. Petri nets, designed by Carl Adam Petri (1962), are a generalization of state-transition diagrams for representing concurrent processes. TOPIC 3 - Continued For object-oriented design, Petri nets have been adopted as the basis for activity diagrams in the Unified Modeling Language (UML). For programming the original von Neumann machine, Herman Goldstine and John von Neumann (1947) designed flow charts, which are complementary to finite state machines. In a flow chart, boxes.represent computational events, and diamonds represent decisions where the flow of control can take an alternate path. In a finite state machine, circles represent states, and arcs mark the transitions from one state to the next. TOPIC 3 - Continued TOPIC 3 - Continued TOPIC 3 - Continued TOPIC 3 - Continued To distinguish processes, procedures, and histories, some further distinctions must be observed: A process is an evolving sequence of states and events, in which one of the states or events is marked current at a context- dependent time called #now. A procedure is a pattern or script that determines the types of states and events that may occur in an entire family of processes. Each process in the family is called an activation of the procedure. A history is a record of the sequence of states and events that existed in the evolution of some process. Each state and event of a history may be marked with a time stamp that records its point in time or duration. TOPIC 3 - Continued TOPIC 3 - Continued Branches and Loops Branches. When the flow of control takes a branch, the states and events on the path not taken never occur, and the concepts that represent them should not have existential quantifiers. Loops. When the flow of control loops back to a place that was previously visited, a new instance of that type of state occurs. In CGs, a separate concept box is needed to distinguish the new instance from the previous instance. TOPIC 3 - Continued TOPIC 3 - Continued TOPIC 3 - Continued TOPIC 3 - Continued PROCEDURAL OR DECLARATIVE. Conventional programming languages are usually called procedural, and logic is the epitome of nonprocedural or declarative languages. Yet the examples show that logic can represent the same kinds of procedures as a programming language. The primary difference is that logic requires explicit relations or predicates to express the sequence, while procedural languages depend on the implicit sequence of the program listing. Ideally, programmers should use whatever notation they find easiest to read and write, and compilers should translate that notation to different code for different purposes: a logic-based language for program analysis, or machine-oriented code for high-speed execution. TOPIC 4 - Concurrent Processes TOPIC 4 - Continued FLOW OF TOKENS The flow of tokens through a Petri net is governed by three rules: Enabled. Whenever a transition has one or more tokens in each of its input; places, it is said to be enabled. Active. An enabled transition may become active by removing one token from each input place. Finished. An active transition finishes by adding one token to each output place. The event from activation to finish is called a firing of the transition TOPIC 4 - Continued TOPIC 4 - Continued TOPIC 4 - Continued TOPIC 4 - Continued Synchronizing Processes TOPIC 4 - Continued TOPIC 4 - Continued  TOPIC 5 - COMPUTATION As purely declarative notations, logic and mathematics have no inherent directionality. A computation, however, always has a purpose. It must thread its way through a tangle of relationships to find the answer to some question. F =ma. TOPIC 5 - Continued The relationships stated in logic and mathematics are like a road map: they affect every possible route, but they don't determine any particular direction a driver should take. The directionality of a computation, like the route the driver chooses, depends primarily on the starting point and the desired goal. A road map is a statement of constraints the driver must observe to find a route with the best balance of speed, economy, convenience, and scenery. The constraints stated in a road map or a logical formula determine the options; the driver's goals determine the direction. TOPIC 5 - Continued DATAFLOW DIAGRAMS. Functions are relations that behave like one-way streets in guiding a computation. In graphic form, they correspond to dataflow diagrams, which have a preferred directionality. By definition, a function is a relation that has one argument called the output, which has a single value for each combination of values of the other arguments, called the inputs. In conceptual graphs, the output concept of a function is attached to its last arc, whose arrow points away from the circle. TOPIC 5 - Continued TOPIC 5 - Continued TOPIC 5 - Continued TOPIC 5 - Continued COMPUTING WITH PETRI NETS If concurrent processes have interacting side effects, dataflow diagrams can be supplemented with general Petri nets. Kurt Jensen (1992) took advantage of that distinction in his system for compiling colored Petri nets to executable code. He used the functional language ML (Stansifer 1992) to specify the basic computation within a transition and developed graphic tools to simulate the interactions between transitions. This distinction enables the different kinds of computations to be specified, tested, and debugged in a modular fashion. After the testing and debugging, the complete Petri nets are compiled to C for efficiency and portability. TOPIC 5 - Continued Petri nets are especially useful for event-driven programs that respond to unpredictable surprises from outside the computer system. Some large applications were implemented with Jensen's tools: a radar simulation System,· electronic money transfer between banks, and communication protocols for a digital telephone network. Since the activity diagrams in UML are based on Petri nets, such tools can be used to simulate UML models and compile them to executable code. TOPIC 5 - Continued MESSAGE PASSING. Surprises in event-driven systems are commonly represented by passing messages from one process to another. The kinds of systems can be distinguished by the way the sending process communicates with the receiving process: Synchronous or asynchronous. Addressed or Associative TOPIC 5 - Continued Combinations of these two distinctions lead to four kinds of communication by message passing: 1. Synchronous addressed communication corresponds to a function or subroutine call, in which the calling program is suspended until the called program returns a result. 2. Asynchronous addressed communication supports parallel processing for input/output devices and muti-threaded operating systems. 3. Synchronous associative communication is based on an ag~ for ordering or prioritizing tasks in forward-chaining languages such as CLIPS. 4. Asynchronous associative communication resembles the New York Stock Exchange, with a pandemonium of brokers making trades for buyers and sellers who never know each other's identity. It is used in distributed processing, triggers in database systems, and data sharing among independent Java programs that communicate via the InfoBus. TOPIC 5 - Continued LINDA. The language Linda, designed by David Gdernter (1985), has a simple but powerful set of rules for asynchronous associative communication. In Linda, messages are passed via BB as n-tuples or lists of n data items. There are three kinds of tuples: (1) Data (2) Patterns (3) Executables TOPIC 5 - Continued TOPIC 6 – Constraint Satisfaction A computation follows a method to achieve a goal that satisfies certain constraints. In procedural languages, the programmer states the method in detail and leaves the goal unstated, except perhaps in the comments and documentation. In nonprocedural languages, the programmer states the goal and lets the computer system select an appropriate method. In either kind of language, the constraints must always be specified. The SQL database language is a typical nonprocedural language: the programmer specifies a goal in the select clause of a query and the logical constraints in the where clause; then the database system determines an' appropriate method for satisfying the constraints. TOPIC 6 - Continued By itself, a constraint is a proposition stated in some logic-based language. What makes a constraint different from an ordinary statement is the ulterior purpose behind it: some agent has declared that the constraint must be true. Computationally, some goal triggers a search for a combination of values that make the constraint true. The method of searching depends on both the goal and the constraints. In SQL, for example, very different search methods would be generated by different select options with the same where clause. TOPIC 6 - Continued GENERATE AND TEST. For his system of rotating disks, Ramon Lull discovered a general method for solving constraint-satisfaction problems: generate and test. The generate-and-test algorithm has one important property: it is general enough to solve all constraint satisfaction problems. For realistic problems, however, it is impossibly slow, since its execution time increases exponentially with the number of variables. Its saving grace is that many of the most useful programs can be converted to highly optimized ones just by changing the order of generating values and testing constraints. The general method of reordering, which is used in relational database systems and many AI systems for planning and problem solving, is called constraint propagation. TOPIC 6 - Continued TOPIC 6 - Continued CRYPTARITHMETIC PROBLEM. To illustrate the effects of constraint propagation, consider the puzzle SEND+MORE=MONEY, which is an example of a cryptarithmetic problem. The goal is to replace the letters with digits that make the equation true; each letter represents a single digit, no digit is repeated, and the initial digits Sand M must not be zero. In their studies of human problem solving, Allen Newell and Herbert Simon (1972) studied how people solve such puzzles in the hope of finding heuristics for making AI programs more natural. Yet a conscious imitation of human techniques is unnecessary. An optimal solution that is remarkably similar to the best human approaches can be derived directly from an analysis of the logical constraints. An optimizing compiler could use such an analysis to determine an efficient sequence of execution. TOPIC 6 - Continued TOPIC 6 - Continued TOPIC 6 - Continued OPTIMIZATION. By constraint propagation, the unoptimized program can be improved by interleaving the operations of generating values and testing constraints. Following are two meta-leved principles that determine which constraints to move: When values have been generated for all variables in a constraint, test that constraint before new values are generated for other variables. If all remaining constraints depend on variables that have not yet been as signed a value, generate values for the constraint that has the smallest choice space. TOPIC 6 - Continued TOPIC 6 - Continued TOPIC 6 - Continued TOPIC 6 - Continued TOPIC 6 - Continued OBSERVATIONS ON THE METHOD TOPIC 6 - Continued METALEVEL HEURISTICS. Generate and test is an exhaustive search for the best possible solution. Constraint propagation is a metalevel technique that reorganizes the search to improve performance, but it still finds the best solution if one exists. Heuristics are also metalevel techniques for guiding the search, manipulating constraints, or evaluating different solutions at the object level. Unlike generate and test or constraint propagation, most heuristics cannot guarantee that a solution they find is the best possible. There are many such techniques, including genetic algorithms, which simulate an evolutionary search for gradually improved methods. TOPIC 6 - Continued Peirce emphasized three ways of using logic: deduction, induction, and abduction.. His third method, abduction, uses heuristics to guess a solution, followed by deduction to verify its correctness. As a universal language for representing declarative information, logic is equally suitable for deductive algorithms that determine the best solution and metalevel heuristics that search for acceptable solutions.  TOPIC 7 – CHANGE CONTEXTS SYNTAX OF CONTEXTS The word context has been used with a variety of conflicting meanings in linguistics, philosophy, and artificial intelligence. Some of the confusion results from an ambiguity in the English word Dictionaries list two major senses of the word context: The basic meaning is a section of linguistic text or discourse that surrounds some word or phrase of interest. The derived meaning is a nonlinguistic situation, environment, domain, setting, background, or milieu that includes some entity, subject, or topic of interest. TOPIC 7 - Continued The word context may refer to the text, to the information ·contained in the text, to the thing that the information is about, or to the possible uses of the text, the information, or the thing itself. The ambiguity about contexts results from which of these aspects happens to be the central focus. These informal senses of the word suggest criteria for distinguishing the formal functions: (1) Syntax (2) Semantics (3) Pragmatics TOPIC 7 - Continued PEIRCE’S CONTEXTS. In 1883, C. S. Peirce invented the algebraic notation for predicate calculus. A dozen years later,. he developed a graphical notation that more dearly distinguished contexts. TOPIC 7 - Continued By combining negation with the existential-conjunctive subset of logic, Peirce developed existential graphs (EGs), which are based on three primitives: TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued DISCOURSE REPRESENTATION THEORY. The logician Hans Kamp once spent a summer translating English sentences from a scientific article to predicate calculus. During the course of his work, he was troubled by the same kinds of irregularities that puzzled the Scholastics. In order to simplify the mapping from language to logic, Kamp (198la,b) developed discourse representation structures (DRSs) with an explicit notation for contexts. In terms of those structures, Kamp defined the rules of discourse representation theory for mapping quantifiers, determiners, and pronouns from language to logic (Kamp & Reyle 1993). TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued RESOLVING INDEXICALS TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued CONVERSATIONAL IMPUCATURES. Sometimes no suitable referent for an indexical can be found. In such a case, the person who hears or reads the sentence must make further assumptions about implicit referents. The philosopher Paul Grice (1975) observed that such assumptions, called conversational implicatures, are often necessary to make sense out of the sentences in ordinary language. They are justified by the charitable assumption that the speaker or writer is trying to make a meaningful statement but, for the sake of brevity, may leave some background information unspoken. TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued TOPIC 7 - Continued  TOPIC 8 – SEMANTICS OF CONTEXTS A context is a package of information about one of those separated chunks of the world. Semantics determines how those packages relate to those chunks. SITUATIONS AND PROPOSITIONS TOPIC 8 - Continued TOPIC 8 - Continued TOPIC 8 - Continued Mc Carthy’s Contexts TOPIC 8 - Continued Meaningful Situations TOPIC 8 - Continued Meaning Preserving Translations Four criteria for formal languages (i) Invertible (ii) Proof preserving (iii)Vocabulary preserving (iv)Structure preserving TOPIC 8 - Continued Meaning in Natural Languages TOPIC 8 - Continued Tinctured Existential Graphs TOPIC 8 - Continued Classifying Contexts TOPIC 8 - Continued TOPIC 8 - Continued  TOPIC 9 – FIRST ORDER REASONING IN CONTEXTS Syntactically, contexts are enclosures for propositions. Semantically, some agent asserts, believes, or assumes that the propositions they enclose describe some situation. Pragmatically, the contexts separate an agent's statements about a situation from metalevel statements about the agent's intentions or attitudes toward those statements. TOPIC 9 - Continued TOPIC 9 - Continued IMPORT and EXPORT RULES Semantics depends on the things that are described by the three kinds of contexts: (i) Actual (ii) Modal (iii) Intentional TOPIC 9 - Continued PIERCE’s RULE OF INFERENCE TOPIC 9 - Continued TOPIC 9 - Continued PROOF IN ALGEBRAIC NOTATION TOPIC 10 – MODAL REASONING IN CONTEXTS Leibniz introduced possible worlds as the foundation for modal semantics: a proposition p is necessarily true in the real world if it is true in every possible world, and p is possible in the real world if there is some accessible world in which it happens to be true. KRIPKE’s WORLDS TOPIC 10 - Continued CRITICISM OF POSSIBLE WORLDS TOPIC 10 - Continued HINTIKKA’s MODEL SETS. Instead of assuming possible worlds, Jaakko Hintikka (1961, 1963) independently developed an equivalent semantics for modal logic based on collections of propositions, which he called model_ sets. He also assumed an alternativity relation between model sets, which serves the same purpose as Kripke's accessibility relation between worlds. As collections of propositions, Hintikka's model sets describe Kripke's possible worlds in the same way that McCarthy's contexts describe Barwise and Perry's situations. TOPIC 10 - Continued DUNN's LAWS AND FACTS Michael Dunn (1973) introduced pairs ,, where M, is a Hintikka-style model set called the facts of a possible world and L is a subset of M, called the laws of that world. Finally, Dunn showed how the accessibility relation from one pair to another is defined by constraints on which propositions are chosen as laws. As a result, the accessibility relation is no longer primitive, and the modal semantics does not depend on imaginary worlds. The ultimate source of modality is some agent, called the lawgiver, who chooses the laws. TOPIC 10 - Continued COMPLETING THE PUSHOUT The branch of mathematics called category theory has methods of completing such diagrams by deriving the other mappings. Given the two arrows at the left and the top, the technique called a pushout defines the two arrows on the bottom and the right. SITUATIONS AS PULLBACKS The inverse of a pushout, called a pullback, is an operation of category theory that "pulls" some structure or family of structures backward along an arrow of a commutative diagram. LEGISLATING MODALITIES EXPORTING MODAL !NFORMATION TOPIC 11 – ENCAPSULATING OBJECTS IN CONTEXTS TOPIC 11 - Continued TOPIC 11 - Continued OBJECT INSTANCE TOPIC 11 - Continued OBJECT METHODS TOPIC 11 - Continued PASSING MESSAGES TOPIC 11 - Continued EXECUTING A PROCEDURE TOPIC 11 - Continued RESULTING STATE