Knowledge Representation & Reasoning Lecture #1Explicit Knowledge RepresentationKnowledge in Different FormsKnowledge Representation and Reasoning (KR&R)Slide 5Reasoning TasksExampleExample Details 1Example Details 2Example Details 3Example Use of Reasoning 1Example Use of Reasoning 2Slide 13Slide 14Tractability of ReasoningSummary: Why, When, How KR&RIn This Course: RepresentationIn This Course: ReasoningCourse RequirementsCourse Requirements #2Project SelectionCheating PolicyMore AdministrativiaNextPropositional LogicRepresenting KnowledgeSlide 27Knowledge EngineeringSlide 29Slide 30Slide 31Slide 32More NotationsSlide 34SummaryHomeworkKnowledge Representation & ReasoningLecture #1UIUC CS 498: Section EAProfessor: Eyal AmirFall Semester 2004Explicit Knowledge Representation•What is knowledge?•What applications do you know of knowledge?•Where do we not need knowledge?•How do we use knowledge?Knowledge in Different Forms•CYC, OpenMind, SUMO – Commonsense•Ontologies – frame-based, semantic web•Medical knowledge•Diseases/symptoms networks•Dynamic systems•Specific applications: NLP, DatabasesKnowledge Representation and Reasoning (KR&R)•Advice taker: a paradigm for KR&R–Represent knowledge (with statements)–Add statements when you want to give advice (control knowledge = statements)–World vs Reasoner (Decision Maker)Reasoner+KnowledgeWorldSensoryinformationActions/DecisionsKnowledge Representation and Reasoning (KR&R)•Advice taker: a paradigm for KR&R•Examples:–A robot moving and manipulating the world–An internet agent booking flights for us–A virtual agent in a computer gameReasoner+KnowledgeWorldSensoryinformationActions/DecisionsReasoning Tasks•A robot moving and manipulating the world–Track the environment and its body (actions)–Update its knowledge with new information (sensors & communications)–Make timely decisions–Safe decisions–Take uncertainty into account–Learning and generalizing from knowledgeExample•A robot moving and manipulating the worldReasoner+KnowledgeWorldSensoryinformationActions/DecisionsReasoningAlgorithmKBSymbols toSensorsTasksMngrExample Details 1•A robot moving and manipulating the worldReasoningAlgorithmKBSymbols toSensorsTasksMngrReasoningAlgorithmKBSymbols toSensorsTasksMngrTask: Decide on actionCall reasoning algorithmwith query. Examples:- next_action(move_fwd)- next_action(look_door)Example Details 2•A robot moving and manipulating the worldReasoningAlgorithmKBSymbols toSensorsTasksMngrTask: Is the action safe?Call reasoning algorithmwith query. Examples:- safe_action(move_fwd)- safe_action(look_door,s)Example Details 3•A robot moving and manipulating the worldReasoningAlgorithmKBSymbols toSensorsTasksMngrTask: Track the worldUse reasoning to updateknowledge. Examples:get_KB(result(move_fwd))get_KB(result(arm(10),s))Example Use of Reasoning 1•Task: select an action to perform•Logical KB: (a) Prove that KB entails move_fwd (e.g.,FOL)(b) Find a model of KB that satisfies move_fwd (e.g., propositional logic)•Probabilistic KB:–Find the probability of move_fwd (e.g., BNs)–Find an action that gives best utility (MDPs)Example Use of Reasoning 2•Task: find cause of error Err•Logical KB: Abduction: Find an explanation Exp such that KB Exp logically entails Err•Probabilistic KB:–Find the set of variable assignments that has maximum posterior probability given ErrKnowledge Representation and Reasoning (KR&R)•Two agents interacting–Sales and purchase agent–Collaboration to achieve a task–Information agent and user agentReasoning Agent 1+Knowledge Base 1Agent 2+Knowledge Base 2ResponseRequestKnowledge Representation and Reasoning (KR&R)•Query answering:–Formal verification of digital circuits–Temporal verification of programs–Prediction and explanationHuman / SoftwareReasoning withA Knowledge BaseAnswerQueryTractability of Reasoning•More expressive languages require more time to reason withExpressivity – Tractability tradeoff•Compact representations not always more efficient for reasoning•Reasoning with a complete model many times easier than reasoning with general knowledge in the same languageSummary: Why, When, How KR&R•Reasoning with knowledge is good when we are not sure about knowledge or query.•The language of KB is determined by the application:–Need for expressive language–Need for fast/accurate response•Knowledge is entered by hand or learned•Tasks for reasoning algorithms varyIn This Course: Representation•Knowledge Representation Languages–Logic: propositional, First-Order Logic, Description Logics [, defaults, linear logic]–Probabilities: graphical models (e.g., BNs), relational-probabilistic models [, causality]•Specific cases:–Dynamic worlds: logical, probabilistic–Space/Shape: logical, probabilistic–Knowledge about knowledgeIn This Course: Reasoning•Exact inference:–Fundamental principles–Structure: treewidth [, context-based]•Approximate inference:–Sampling, variational, lower/upper bounds,…•Special tasks: –Dynamic worlds: filtering, smoothing,…–Space/Shape: logical, probabilistic–EqualityCourse Requirements•First-order logic (e.g., Models, signature, formulae, literal): [R&N ’03] ch. 8 (lec. #3)•Probability & Statistics (e.g., Normal distr., Bayes rule): [R&N ’03] ch. 13 (lecture #6)•Computational complexity (level of CS373)Course Requirements #2•Mathematical maturity: proofs, understanding•Independence: follow beyond your presentation reading to gain depth•Independence: project will require readings that are not specified•Independence: search for information instead of thinking it will come to youProject Selection•Select from list or suggest your own•Projects for one or two people•12th lec. (Oct 7): Project proposals (~1 pg) •18th lec. (Oct 28): Extended proposals (~3-pages)•24th lec. (Nov 18): Review of progress (~1 page)•Final Exam (Dec 16): Projects dueCheating Policy•First offense:–Exam: zero on exam–Project/homework: zero + loss of full letter grade•Second offense:–In same course: failure–In different course: expulsionMore Administrativia•Late HW submission policy: 7 days•Date/time for midterm ?•Course grading•NewsgroupNext•Example of (non-traditional) reasoning with first-order logic in a robotics setting•Reminder of Propositional Logic notation and conceptsPropositional Logic•Language includes–Prop.
View Full Document
Unlocking...