6.871 - Lecture 21Tell It What to KnowReview of Search6.871 - Lecture 26.871 - Lecture 2 2A Reminder Checkbook balancing vs. getting out of the supermarket Character of task Character of solution Go past image to technical ideas and concepts6.871 - Lecture 2 3Purposes of This Lecture Explain the mindset of knowledge engineering Change your mind about what a program is– From a buncha bits to …– From code to … Change your mind about how to create them– Don’t tell it what to do– Build it incrementally Change your mind about what to use a computer for – Many things…6.871 - Lecture 2 4Punchlines The issue is style and pragmatics, not theory A program can be much more than just code.It can be a repository of knowledge, an environment for the development of knowledge Embody the reasoning, not (just) the calculation Don’t tell it what to do, tell it what to know, and how to use what it knows (often many different ways)– Task changes from writing a program to specifying the knowledge.– Task becomes debugging knowledge, not code.6.871 - Lecture 2 5Punchlines One payoff: multiple uses of the same knowledge. Performance is only the beginningSolving the problem is only (a small) part of the job– Explanation– Learning–Tutoring Suppressing detail helps Build a custom language6.871 - Lecture 2 6Punchlines Nothing is ever right the first time– Nature of the task– Nature of the knowledge– Evolutionary development» Build a little» Test a little» Redesign a little6.871 - Lecture 226.871 - Lecture 2 8What’s a Good Representation? Consider: 1996 vs. MCMXCVI Which would you rather use in arithmetic? Why?6.871 - Lecture 2 10What’s a Good Representation? Consider: 1996 vs. 11111001100 Which would the computer rather use in arithmetic? Why?6.871 - Lecture 2 11The Power of A Good Representation6.871 - Lecture 2 12The proportional ownership of the first party shall be equal to a ratio, the numerator of which is: a ratio, the numerator of which is the holding period of the first party multiplied by the capital contributed by the first party, and the denominator of which is a sum, the first term of which is the holding period of the first party and the second term of which is the holding period of the second party; and a denominator which is the sum of two terms; the first term of which is a ratio, the numerator of which is the holding period of the first party multiplied by the capital contributed by the first party, and the denominator of which is a sum, the first term of which is the holding period of the first party, the second term of which is the holding period of the second party; and the second term of which is a ratio, the numerator of which is the holding period of the second party multiplied by the capital contributed by the second party, and the denominator of which is a sum, the first term of which is the holding period of the first party and the second term of which is the holding period of the second party.6.871 - Lecture 2 15DO 14 I = 1,NDO 14 J = 1,N14 V(I,J) = (I/J)*(J/I)What’s a Program?The Minimal Number of Bits View6.871 - Lecture 2 16Task: Symbolic Mathematics345732xxx+++9852xx++How can we take a derivative ofto get6.871 - Lecture 236.871 - Lecture 2 25Observations about the knowledge It’s organized around the operators. It’s organized around nested sub-expressions Top-down tree descent is the natural approach The representation should reflect that. The representation should facilitate that.6.871 - Lecture 2 26Use a Natural Representation Conventional mathematical notation(* (* 2 y) sqrt(+ (^ x 3) (* x y (+ z a)))) Use the pattern appropriate for the leading operator)(23azxyxy ++6.871 - Lecture 2 27A Small Language  In effect we’ve built a language with the right abstractions:– Expression tree– Dispatching on leading operator– Recursive descent through the expression tree Operators are independent, modular chunks of “mathematical knowledge” Operators can be added incrementally There is an indexing mechanism for finding relevant operators given the structure of the current representational focus6.871 - Lecture 2 29Catchphrases and Punchlines The issue is style and pragmatics, not theory A program can be much more that just code.It can be a repository for knowledge, an environment for the development of knowledge Embody the reasoning, not (just) the calculation. Don’t tell it what to do, tell it what to know.– Task changes from writing a program to specifying the knowledge.– Task becomes debugging knowledge, not code.6.871 - Lecture 2 30Catchphrases and Punchlines One payoff: multiple uses of the same knowledge. Performance is only the beginningSolving the problem is only (a small) part of the job– Explanation– Learning–Tutoring6.871 - Lecture 2 31Task: Balancing Your CheckbookRead StatementBalanceAdjBalance = StatementBalanceuntil done do {read OutstandingCheckAdjBalance=- OutstandingCheck}until done do {read OutstandingDepositsAdjBalance=+ OutstandingDeposits}until done do {read FeeAdjBalance=- Fee}until done do {read InterestAdjBalance=+ Interest}if AdjBalance = CheckBookBalance{print (“It balances!”); return}else if AdjBalance > CheckbookBalance{print “Hey, good news.”; return}else {print “We’re scrod.”; return}6.871 - Lecture 246.871 - Lecture 2 32A Spreadsheet is Almost Right The right mindset: focus on the knowledge6.871 - Lecture 2 33The Checkbook ExampleCleared Cleared Uncleared UnclearedDeposits Checks Deposits ChecksBank Balance $1234.56 $100.00 $213.40 $250.00 $12.34$250.00 $874.30 $95.00 $19.99Total uncleared $75.00 $19.00 $180.00 $25.00deposits 725.00 $90.00 $22.00 $200.00 $72.54$15.00 $105.00$14.00Total uncleared checks $24.00$248.87New Balance$1,710.696.871 - Lecture 2 34A Spreadsheet is Almost Right The right mindset: focus on the knowledgeBut:– They are numeric and we want more– They have only one inference engine KBS as “conceptual spreadsheets”6.871 - Lecture 2 35Search Basics Lecture 2, Part 2.6.871 - Lecture 2 36The Fundamental Problem:Search in a Problem Space B = branching factor D = depthNodeOperatorBDSize = Bd6.871 - Lecture 2 37Search Spaces Grow ExponentiallyThe marginal cost of slight improvement is prohibitive6.871 - Lecture 256.871 - Lecture 2