%---------------------------------------------------------------------------- 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.) %---------------------------------------------------------------------------- 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 %---------------------------------------------------------------------------- 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 %---------------------------------------------------------------------------- SCRIPTS (Schank and Abelson, 1977) Frame-like sequences for representing sequences of events. Scheme for organization of knowledge and expectations Key idea: Pre-stored situation-specific causal chain. Advantages: Functional justification: Inference control Cognitive justification: Psychologically plausible Example: Jack went to a restaurant. He ordered a hamburger. He paid and left. What did John eat? Too many inferences involved -- how do we control them? The basic idea -- we KNOW what happens in restaurants. Why not use this knowledge? $RESTAURANT -- The restaurant script. o --> inside(&REST.) Go in. &PATRON <=> PTRANS <-- &PATRON -| ^ --< |c Jack went to a restaurant. Sit down. &PATRON <=> PTRANS Look at the menu. ^-c- MTRANS Decide what to order. ^-c- MBUILD Order your meal. ^-c- MTRANS He ordered a hamburger. (Wait.) Waiter brings food. ^-c- PTRANS Eat. ^-c- INGEST Pay. ^-c- ATRANS He paid... Tip waiter. ^-c- ATRANS Leave. ^-c- PTRANS ...and left. Roles, Header (entry conditions, etc.), Body (default path + variations), Scenes. ^-c- represents a "causal link", a causal connection between the SCENES of the script. Script-based understanding: How do we use this to understand stories? Script suggestion: Find possibly active scripts based on input Script selection: Select appropriate script Script instantiation: Match input to script; instantiate roles and scenes Script application: Match subsequent inputs to script scenes; instantiate missing concepts When the story about the scripted activity comes in, we match inputs against the script, trying to find which script element it matches. When we find a match, we update role bindings (e.g., who is the patron, what is the food), and infer actions and states left implicit (i.e., fill in the gaps in the causal chain). Problems: The script selection problem -- how do we find the right script at the right time? Examples: John wanted a hamburger. He opened the refrigerator. John went to the restaurant. The salad bar looked good. He left $5 on the table. John went into McDonalds. He asked the cashier if he could break a twenty dollar bill. More on this when we talk about natural language processing and conceptual information processing. %----------------------------------------------------------------------------