DOC PREVIEW
CMU CS 15780 - Lecture

This preview shows page 1-2-3-4-5-6-44-45-46-47-48-49-50-89-90-91-92-93-94 out of 94 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 94 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

15-780: Graduate AILecture 4. Logic, SAT, and CSPs Geoff Gordon (this lecture)Ziv Bar-Joseph TAs Michael Benisch, Yang GuAdmin15-780 and 16-731 are the same course, cross listed in CS and RoboticsIf your email address is not [email protected], please contact the TAs to make sure you’re on the mailing listLast episode, on Grad AIWhat you should knowIDA* definitionPropositional logicsyntax, truth tablesmodels, satisfiability, validity, entailment, etc.equivalence rules (e.g., De Morgan)inference rules (e.g., resolution)What you should knowNormal forms (e.g., CNF)SAT problemits search graphreductions (e.g., 3-coloring to SAT)Structure of a theorem proverproof trees, knowledge basescompare/contrast search graph w/ SATDirection of reductionIf A reduces to B thenif we can solve B, we can solve Aso B must be at least as hard as AE.g., could take an easy problem and reduce it to a hard oneNot-so-useful reductionPath planning reduces to SATVariables: is edge e in path?Constraints:exactly 1 path-edge touches startexactly 1 path-edge touches goaleither 0 or 2 touch each other nodeReduction to 3SATWe saw that search problems can be reduced to SATis CNF formula satisfiable?Can reduce even further, to 3SATis 3CNF formula satisfiable?Useful if reducing SAT/3SAT to another problem (to show other problem hard)Reduction to 3SATMust get rid of long clausesE.g., (a ∨ ¬b ∨ c ∨ d ∨ e ∨ ¬f)Replace with(a ∨ ¬b ∨ x) ∧ (¬x ∨ c ∨ y) ∧ (¬y ∨ d ∨ z) ∧ (¬z ∨ e ∨ ¬f)A note on reductionsMay be many reductions from problem A to problem BMay have wildly different propertiese.g., search on transformed instance may take seconds vs. daysExample will show up when we get to Planning topicCitation“Using Inaccurate Models in Reinforcement Learning.” Pieter Abbeel, Morgan Quigley, Andrew Y. Nghttp://www.icml2006.org/icml_documents/camera-ready/001_Using_Inaccurate_Mod.pdfComparing representationsAll search algorithms presented so far use a discrete representation of the worldIf world is continuous, they divide it into blocksThis works great for some domains, terribly for othersReal vs. discreteDiscrete works well, e.g., for deciding which way to go around an obstacleBut it would be really bad to discretize to the level required for precision position servoingPosition servoingE.g., if state is (x(t) - xtgt(t)), discretization will allow bang-bang control (or, slightly better, control with k fixed levels of effort)If state is (x(t), xtgt(t)), axis-parallel splits won’t even allow accurate bang-bang control without very fine discretizationSmooth controlCouldn’t implement a smooth controller like PID without a really fine gridProbably so fine as to make it infeasible to search for control recommended by logical formulaTheorem proversSoundness and completenessAn inference procedure is sound if it can only conclude things entailed by KBcommon sense; we already required itA set of rules is complete if it can conclude everything entailed by KBModus ponens by itself is incompleteCompleteness of resolutionInference procedure: put KB in CNF, add ¬B to KB, apply resolution untilwe get a False as a consequence (and conclude KB ⊨ B), orwe run out of inferences (and conclude KB ⊭ B)This inference procedure is completeVariationsHorn clause inference (faster)Ways of handling uncertainty (slower)CSPs (sometimes more convenient)Quantifiers / first-order logic (say more about this later)Horn clausesHorn clause: (a ∧ b ∧ c ⇒ d)Equivalently, (¬a ∨ ¬b ∨ ¬c ∨ d)Disjunction of literals, at most one of which is positivePositive literal = head, rest = bodyUse of Horn clausesPeople find it easy to write Horn clauses (listing out conditions under which we can conclude head)happy(John) ∧ happy(Mary) ⇒ happy(Sue)No negative literals in above formula; again, easier to think aboutWhy are Horn clauses importantInference in a KB of propositional Horn clauses is linearForward chaining or backward chaining (see RN reading, or discussion of unit resolution below)Handling uncertaintyFuzzy logic / certainty factorssimple, but don’t scaleNonmonotonic logicalso doesn’t scaleProbabilitiesmay or may not scale—more in Part IIDempster-Shafer theoryCertainty factorsInstead of just T/F, a model assigns a certainty factor in [0, 1] to each propositionAnd, KB assigns a certainty to each ruleInterpret as “degree of belief”Certainty factorsLogical connectives are interpreted as arithmetic operations, e.g., ∧ as min, ∨ as max, and ¬ as (1-x)E.g., if KB has (¬rains ∨ pours) @ 0.8 and rains @ 0.7, concludemax(0.3, pours) ≥ 0.8pours ≥ 0.8Problems w/ certainty factorsHard to separate a large KB into mostly-independent chunks that interact only through a well-defined interfaceCertainty factors are not probabilities (i.e., do not obey Bayes’ Rule)Nonmonotonic logicSuppose we believe all birds can flyMight add a set of sentences to KBbird(Polly) ⇒ flies(Polly) bird(Tweety) ⇒ flies(Tweety)bird(Tux) ⇒ flies(Tux)bird(John) ⇒ flies(John)…Nonmonotonic logicFails if there are penguins in the KBFix: instead, addbird(Polly) ∧ ¬ab(Polly) ⇒ flies(Polly) bird(Tux) ∧ ¬ab(Tux) ⇒ flies(Tux)…ab(Tux) is an “abnormality predicate”Need separate abi(x) for each type of ruleNonmonotonic logicNow set as few abnormality predicates as possibleCan prove flies(Polly) or flies(Tux) with no ab(x) assumptionsIf we assert ¬flies(Tux), must now assume ab(Tux) to maintain consistencyCan’t prove flies(Tux) any more, but can still prove flies(Polly)Nonmonotonic logicWorks well as long as we don’t have to choose between big sets of abnormalitiesis it better to have 3 flightless birds or 5 professors that don’t wear jackets with elbow-patches?even worse with nested abnormalities: birds fly, but penguins don’t, but superhero penguins do, but …Dempster-ShaferAllows additional worst-case uncertainty beyond probabilitiesMaintains lower, upper bounds on probabilities; assumes world is adversarial within those boundsLike probabilities, inference is guaranteed correctMay be overly conservativeCSPsConstraint satisfactionRecall 3-coloringTurned map into graph (same size) then into SAT problem (constant factor blowup)Did we have to do that?=CSP definitionNo: represent as CSP insteadCSP = (variables, domains, constraints)Variable: aDomain: (R, G, B)Constraint: a, b ∈ (RG, RB, GR, GB, BR, BG)Constraints usually represented compactlySearchObviously a search problemLet’s try DFS—top to


View Full Document

CMU CS 15780 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?