FUNCTIONS, GOALS, TASKS A FUNCTION is what a system (or an agent) does (or is supposed to do). Often defined as a: GOAL: specified by the state a system reaches (or is supposed to reach) from a given initial state. (Allen Newell) TASK: specified by the information that it takes as input and the information that it provides as output. (David Marr) The goal and the task views are equivalent and often they will be used interchangably. %---------------------------------------------------------------------------- Some AI Tasks (Smart and Langeland-Knudsen 1986): - INTERPRETATION (UNDERSTANDING): Forming high level conclusions or descriptions from collections of raw data. - PREDICTION: Projecting probable consequences of given situations. - DIAGNOSIS: Determining the cause of malfunctions in complex situations based on observable symptoms. - DESIGN: Determining a configuration of system componenents that meets certain performance goals while satisfying a set of constraints. - PLANNING: Devising a sequence of actions that will achieve a set of goals given certain starting conditions. - MONITORING: Comparing the observed behavior of a system to its expected behavior. - DEBUGGING and REPAIR: Prescribing and implementing remedies for malfunctions. - INSTRUCTION: Detecting and correcting deficiencies in students' understanding of a subject domain. - CONTROL: Governing the behavior of a complex environment. Also: - LEARNING: Extending abilities or improving performance. %---------------------------------------------------------------------------- METHOD A method is how a system (or an agent) achieves a given task. -------------- | | ---------->| Task |----------> Input | | Output -------------- ^^ || || || Method A method is characterized by the KNOWLEDGE it needs the PROCESSES (or algorithms) it uses %---------------------------------------------------------------------------- PROCESS Process is one major component of an AI method (knowledge being the other). A process is characterized by the SUBTASKS it sets up the CONTROL it exercises over the subtasks (i.e., how it orders and sequences the subtasks). %---------------------------------------------------------------------------- KNOWLEDGE, KNOWLEDGE REPRESENTATION Knowledge is the other major component of strong AI methods (process being the first one). Types of knowledge include: facts, heuristics, associations, procedures, plans, constraints, concepts, experiences, causal models, commonsense, etc. The study of knowledge is concerned with: (i) ONTOLOGY/CONTENT: what types of knowledge are possible, (ii) FORM/STRUCTURE: how the various types of knowledge are represented, (iii) PROCESS: how may knowledge be used to accomplish various functions, and (iv) LEARNING: how may knowledge be acquired. KNOWLEDGE REPRESENTATION is concerned with the first two questions. %---------------------------------------------------------------------------- KNOWLEDGE REPRESENTATION: CONTENT and FORM Consider Newton's Second Law of Motion: In English: ``The acceleration of a body at rest or in uniform motion is directly proportional to the net external force applied on it''. In the language of Algebra: ``F = ma'', where F stands for force, a for acceleration, m is a constant of proportionality (mass), and = stands for equality. In the language of Calculus: ``dp/dt = m dv/dt'' where p stands for linear momentum, v for linear velocity, t for time, m, again, is a constant of proportionality (mass), and = stands for equality. These different statements of my knowledge of Newton's law are different REPRESENTATIONS of the same piece of knowledge. They are representations in that each symbol in them "stands for" for an object or relation in the real world. In the algebriac representation, for example, F, a, and m, stand for objects in the world while = stands for a specific relation between them. The "piece of knowledge that does not change across the above representations is my knowledge of the CONTENT of Newton's law. Of course, the FORM of representation does change; the different representation LANGUAGES (e.g., English, Algebra, Calculus) use different vocabularies and grammars. These different languages are able to represent my knowledge of Newton's law to different degrees of precision. In sum: Each statement is a different REPRESENTATION of the same piece of knowledge Each SYMBOL in each representation stands for an object or relation in the real world The CONTENT of the knowledge in each case is the same The FORM of the knowledge changes with the language used to describe the knowledge Each REPRESENTATIONAL LANGUAGE has its own vocabulary and grammar Of course, my knowledge of Newton's law may be incorrect or incomplete; that is a different issue. The point is that the representation of knowledge requires: a CONTENT THEORY of what needs to be represented a REPRESENTATION LANGUAGE that can adequately express the content theory a FUNCTIONAL ACCOUNT of why the chosen representations are appropriate for the representational task at hand %---------------------------------------------------------------------------- TELEOLOGY OF INTELLIGENCE This analysis of intelligence in terms of functions and methods assumes a teleological (device-like) nature of intelligence, i.e, it ascribes purposes (functions) and mechanisms (methods) to intelligences. In other words, AI theories must be justified functionally (or teleologically) by relating the proposed mechanisms to the tasks that they support. Note that function, process and knowledge are inter-dependent; as any one of them changes, the others may changes as well. %---------------------------------------------------------------------------- WHY IS KNOWLEDGE (AND KNOWLEDGE REPRESENTATION) IMPORTANT? Let's take natural language processing as an example. GENERATION PARSING/ <- Processes UNDERSTANDING <- Ideas --> Language --> Ideas (Speaker) (Hearer) The purpose of language is to enable communication of IDEAS (or feelings, needs, etc.) The speaker has something on his mind which he wishes the hearer to know. The main issues are: REPRESENTATION and PROCESS How to represent the ideas? How to encode (generate) and decode (parse, understand) ideas in language? Teleology: Process and representation are interdependent: - Representations impose requirements on processes: the processes must take certain representations as input and produce the appropriate representations as output. - Processes impose requirements on representations: the representations must facilitate the processes that operate on them. (The same issues arise in perception, planning, problem-solving -- all cognitive functions.) %---------------------------------------------------------------------------- The problem of understanding language is the problem of understanding ideas. Understanding requires making inferences. John went to a store. He picked up some toothpaste and went to the check-out counter. He paid the cashier and left. Q: What did John buy? Language is: AMBIGUOUS: word sense ambiguity - "take". structural ambiguity - I saw the Grand Canyon flying to NY. VAGUE: I got a new TV at Macy's. ELLIPTIC: John thinks vanilla. (What flavor ice-cream does Mary like?) (McCowley) METAPHORICAL: There's a cancer in the White House. (John Dean) But we are able to communicate ideas because of SHARED WORLD KNOWLEDGE, and our ability to draw INFERENCES from what we are told and what we already know. Big issues: How do we represent all this knowledge in the machine? How can it be brought to bear at the right time in the right way? How can we get the machine to draw the necessary inferences? Although we used natural language as an example, similar teleological considerations come up in other areas as well. Conclusion: KNOWLEDGE REPRESENTATION is a central problem in AI. %---------------------------------------------------------------------------- We'll start with KNOWLEDGE REPRESENTATION, then move on to processing issues in SEARCH, PLANNING, PROBLEM-SOLVING, NATURAL LANGUAGE, ROBOTICS, VISION and LEARNING. While talking about the processing issues, we'll encounter knowledge representation issues repeatedly (since process and content are interdependent). %---------------------------------------------------------------------------- Similarly for other tasks. E.g., can derive characteristics of a good path planning representation by looking at the functions these representations must support. %---------------------------------------------------------------------------- REPRESENTATIONAL TERMINOLOGY Some other (domain-independent) representation schemes (such as logic or semantic nets) provide an underlying "language" for designing representations. These focus primarily on FORM, not CONTENT. WHAT IS A REPRESENTATION? A stylized version of (some part of) the world: A description of an object, event, relation, etc., in terms of a collection of SYMBOL STRUCTURES Composed of a pre-defined VOCABULARY of symbols standing for objects, relations, etc. according to well-defined RULES WHAT IS A REPRESENTATION SCHEME? A language for expressing representations: A collection of available symbol structures, comprising the VOCABULARY or ONTOLOGY A SEMANTIC MAPPING specifying which real-world objects and relations the symbols stand for A set of RULES for combining vocabulary items into representational structures Capable of expressing any relevant aspects of the CONTENT of the real world input (e.g., a sentence, a visual scene) and background knowledge WHAT IS A REPRESENTATIONAL THEORY? A theory of representation specifies: A CONTENT THEORY of what needs to be represented A REPRESENTATIONAL SCHEME that can adequately express the content theory A FUNCTIONAL ACCOUNT of why the chosen representations are appropriate for the representational task at hand %---------------------------------------------------------------------------- PROPERTIES OF A GOOD REPRESENTATION SCHEME (Elaine Rich) A representation for knowledge must: - capture generalizations - be understood by the people who provide the knowledge - be easily modified to correct errors and reflect changes - be usable even if it is not entirely accurate or complete - be used to overcome its bulk by helping to narrow the range of possibilities to be considered (Winston) Good representation characteristics: - Important features are explicit - Constraints are clear - Complete (for the problem at hand) - Concise (no unnecessary wordiness) - Transparent (easy for people to understand) - Efficient (computer time and memory) - Procedures exist to compute - Detail is hidden unless expressly requested (Winograd) Characteristics of primitives: - Finitude - Comprehensiveness - Completeness - Independence - Canonicality - Irreducibility Criteria: (compare with the ones we derived for our NL database example) - The ability to state significant generalizations - Criteria for selecting semantic entities - Coverage of relevant phenomena - Canonical form (and effects on memory and reasoning) - Dealing with extended meaning and metaphor %---------------------------------------------------------------------------- INFERENCE AND UNDERSTANDING The reason for investigating knowledge is that ``understanding'' appears to play a major role in cognition. What is understanding? "Understanding" may entail understanding the world, understanding oneself, understanding ones interactions with the world, etc. "Understanding" implies certain types of knowledge and the ability to make certain types of "inferences". What is an inference? An "inference" is the derivation of some knowledge from some other knowledge. Understanding involves deriving two kinds of inferences: Explanations (or abductions) Expectations (or predictions) %---------------------------------------------------------------------------- CAUSALITY Representation of the TYPES of causal connections or relationships. Example: John bought a car RESULT: What state results from this action? John owns the car. The seller has John's money. ENABLEMENT: What state enables this action? John owned the money. The seller owned the car. MOTIVATION: What was the reason for this action? John wanted the car. CD distinguishes four types of causation: Acts can RESULT in states or state changes. States can ENABLE actions. States or actions can INITIATE mental states. Mental states can be REASONS for actions. Examples: John killed Mary. John grew the plants with fertilizer. When John saw the new car, he wanted it. CD Representations: ACT STATE STATE STATE (or ACT) MENTAL-STATE ^ ^ ^ ^ ^ |r |E |dE |I |R STATE ACT ACT MENTAL-STATE ACT Abbreviations: rE: an ACT results in a STATE which enables an ACT IR: an ACT or STATE initiates a thought which is the reason for an ACT %---------------------------------------------------------------------------- COMMON REPRESENTATION SCHEMES Propositional logic, predicate calculus Procedural representations Semantic (associative) networks And/Or graphs Production systems, rules Direct (analogical) representation Semantic primitives Frames, scripts, schemas, MOPs, XPs ... %---------------------------------------------------------------------------- SEMANTIC PRIMITIVES Several perspectives: AI: Schank (1968), Schank and Abelson (1977), Wilks (1977) Psychology: Miller (1975), Johnson-Laird (1976), Norman and Rumelhart (1975) Linguistics: Jackendoff (1975) For a good analysis, see: Winograd (1978) E.g., Schank's CD ACTS - ptrans, atrans, mtrans, propel, ... STATES - location, hunger, happiness, ... CASES - actor, object, from, to, instrumental action, ... CAUSAL RELATIONS- results, enables, initiates, reason E.g., Wilks ENTITIES - man, stuff, part, ... ACTIONS - cause, be, flow, ... CASES - to (direction), in (containment), ... QUALIFIERS - good, much, ... TYPE INDICATORS - how, kind, ... %---------------------------------------------------------------------------- FRAMES, SCRIPTS, SCHEMAS Proposed by several people, including Minsky (1975), Schank & Abelson (1977); also Charniak, Brachman, Fahlman, Bobrow & Winograd. Basis for "frame systems" such as KRL (Bobrow & Winograd, 1977) and PARMENIDES (Shell & Carbonell, 1991) Origins in semantic networks and case frames Generalization of "case frame" idea: "Chunks" of knowledge Provide expectations (top-down) Group information into organized knowledge structures Minsky (1975): Frames as a representation for: visual perception natural language complex behaviors Key ideas: A FRAME is a structure with SLOTS (also called TERMINALS). FRAME TYPES specify abstract concepts. INSTANCES specify actual entities or instances of those concepts. Slot fillers may have CONSTRAINTS (also called MARKERS). Slot fillers may have DEFAULTS. Slot fillers may have INFERENTIAL ATTACHMENTS. Slots have FACETS (value, default, range, if-added, if-needed, ...). Values and ranges can be filled with other frames. If-added and if-needed provide inferential capability through procedural attachment. (They tell the system what inferences to make and how to make them by specifying the inference procedures associated with the slots.) Slots provide both DECLARATIVE and PROCEDURAL information. Frames are usually arranged in semantic net-like INHERITANCE HIERARCHIES Example: Generic DOG frame Isa: an ANIMAL, a PET Owner: a PERSON (if-needed: find a PERSON with Pet = Self) Name: a PROPER-NAME (default: ROVER) Breed: Computer representation: (def-frame DOG (:is-a ANIMAL) :owner (:constraint PERSON :if-needed ...) :name (:default ROVER :constraint PROPER-NAME) :breed ...) Procedures: The frame system can be thought of as providing a data abstraction (in the data structures sense) which allows you to define data objects and associated data operations. (F.isa frame) (F.frame-p frame) (F.set frame slot [facet] value) (F.get frame [facet] slot) (F.instantiate frame) (F.define frame (isa abstract-frame) [slot filler] [slot filler] ...) Inheritance (usually automatic) Procedural attachment Support for variable binding Matching and instantiation Skolemization %---------------------------------------------------------------------------- PRODUCTION SYSTEMS Computational model of Newell & Simon (1972), based on Post production systems (1943). Knowledge is a flat set of IF-THEN rules IF condition1 AND condition2 AND ... THEN action Advantages: Modular (in theory, each rule is independent) Uniformity Naturalness Disadvantages: Inefficiency Opaqueness Is human knowledge rule-based? %---------------------------------------------------------------------------- PROCEDURAL REPRESENTATIONS Examples: PLANNER (Hewitt 1972), ATNs det noun verb s1 --> s2 ----> s3 ----> ... (Finite state machine) / \ --- adj Advantages: Heuristics can be encoded Disadvantages: Non-modular Can't state facts without including control information (e.g., (THAND A B)) Can't use knowledge in ways other than initially intended Does not support learning %---------------------------------------------------------------------------- DIRECT OR ANALOGICAL REPRESENTATIONS Special purpose representations, such as bitmaps for vision Example: Mutilated chessboard %---------------------------------------------------------------------------- DIMENSIONS OF COMPARISON Generality: WEAK: General purpose, structure oriented (e.g., logic) vs. STRONG: Specific, content oriented (e.g., CD) CONTENT vs. STRUCTURE: How does logic compare with CD? It doesn't. Logic only talk about FORM, not CONTENT. You can represent CD using logic, semantic nets, anything you want. FORM is important too, but the hard issue is the CONTENT of the representations. (Both should follow from the functional constraints on the represenation.) Logic allows mechanized inference of logically correct formulas from pre-existing formulas. You can assert facts and rules about the world, and the computer will automatically make the correct inferences (may be inefficient). BUT: Logic does not tell you about how the predicates, constants, variables, functions, are to be selected. It tells you how to write down inference rules, not which ones to write down. CD, in contrast, contains a content theory of inferences; it tells us which inferences we want to make. However, it does not tell us how to implement the inference-making process unlike logic which gives us a principled and uniform (but possible inefficient) way to implement inferences. Structure: FLAT: Set of autonomous formulas (e.g., logic). vs. STRUCTURED: Interconnected formulas (e.g., frame systems, semantic nets). The latter represent the STRUCTURE of knowledge (RELATIONSHIPS between concepts) as well as its CONTENT (the concepts themselves). %---------------------------------------------------------------------------- Copyright (c) Ashwin Ram, 1990-93 Assistant Professor, College of Computing Georgia Institute of Technology, Atlanta, Georgia 30332-0280 E-mail: