New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Artificial Intelligence

by: Mrs. Carolyne Abbott

Artificial Intelligence CS 4710

Mrs. Carolyne Abbott
GPA 3.71

David Brogan

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

David Brogan
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 9 page Class Notes was uploaded by Mrs. Carolyne Abbott on Monday September 21, 2015. The Class Notes belongs to CS 4710 at University of Virginia taught by David Brogan in Fall. Since its upload, it has received 55 views. For similar materials see /class/209667/cs-4710-university-of-virginia in ComputerScienence at University of Virginia.


Reviews for Artificial Intelligence


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
CS 416 Artificial Intelligence Lecture 17 FirstOrder Logic Chapter 9 Guest Speaker Topics in Optimal Control Minimax Control and Game Theory March 28 2 pm OLS 005 Onesimo HernandezLenna CINVESTAVPN Mexico City This is a nontechnical introduction mainlythru examples to some minimax rcontrol aka quotworstcase controlquot or quotgames against naturequot p a wuuuueu L cooperative and noncooperative game equilibria etc Inference in firstorder logic Our goal is to prove that KB entails a fact a We use logical inference 7 Forward chaining r Backward chaining 7 Resolution All three logical inference systems rely on search to find a sequence of actions that derive the empty clause Search and forward chaining Start with KB full of firstorder definite clauses Disjunction of literals with exactly one positive Equivalent to implication with conjunction of positive literals on left antecedent body premise and one positive literal on right consequent head conclusion Propositional logic used Horn clauses which permit zero or one to be positive Look for rules with premises that are satis ed use substitution to make matches and add conclusions to KB Search and forward chaining mm Firsl A B D G H Which rules have premises A A E gt c that are satisfied modus BADgtE ponens AquotEgtC nope BquotDgtEyes EquotCquotGquotHgtlnope 7AAEC yes rEACAGAHAl riope oriemorerry yes EquotCquotGquotHgtl Search and forward chaining Would other search methods work Yes thistechnique falls in standard domain of all searches Page 1 Search and backward chaining Start with KB full of implications Find all implications with conclusion matching the query Add to fringe list the unknown premises Adding could be to front or rear of 39inge depth or breadth Search and backward chaining Are all the premises ofl satisfied No Uepll Frsl A B D G H For each C E G H are each oftheir A A E gt c premises satis ed 3 A D gt E C no put its premises on fringe CAEAGAHgt ForeachAandEaretheir premises satis ed yes E no add premises for each B and D B yes D yes E G H yes Search and backward chaining Are all the premises ofl satis ed No asantn i rsl For each C E G H are each oftheir 39 A39 B39 D39 G39 H premises satis ed 39 A A E gt c C no put its premises on fringe end B quot D gt E E no put Its premises on fringe end c A E A G A H gtl G H yes Are C39s premises A E satis ed A es E no add premises Are E39s premises B D satis ed Yes Backwardforward chaining on t explicitly tie search method to chaining direction Inference with resolution We put each firstorder sentence into conjunctive normal form We remove quanti ers We make each sentence a disjunction ofliterals each literal is universally quanti ed We show KB quot on is unsatisfiable by deriving the empty clause Resolution inference rule is our method 7 Keep resolving until the empty clause l5 reached Resolution Look for matching sentences Shared literal with opposite sign Substitution may be required Animal Fx V Loves Gx x and Loves uv V Kills u v Fx animal unloved by x Gx someone who loves x Page 2 Resolution Wnat does tnis rnean in Englisn7 e Anlrna XVLuvesGgtltygtlt FOO anlmal unluved bvx i c X sumeunewhuluvesx e Luves u v y Kllls u y For all people eitner a person doesn t loye an anirnal or someone loyes tne person Nobody loyes anybody or nobody kills anybody Resolution 7 Animal Fm y Loves cm x and Loves u v y lltills u y LEIVES and NLEIVES cancel Wl h Substitutlurl r ulGgtlt and VX e Resolyent clause Anlrnal Fgtlt vlltllls om gt0 Example tn iiiriii new i will inniinn interim liniiwin pinion itiini alliwl i i n i in nihiliiii Resolution example Inference with resolution What resolves with what for proof 7 Unit prererence Start vvlth singlerllteral sentences and resolye tnern vvlth rnore cumpllcated sentenees Eyery resolution reduees ne size ortne sentence by one 7 Cunsls12nl Wllh our ooaiioiind a sentence oi size n Resemblesfurvvard enaining Inference with resolution What resolves with what for proof 7 Set or suppo Build a special set or sentences Eyery resolution includes one sentence from set n e do set Resembles backward enaining it set or support initialized yyitn negated duery Theorem provers Logical inference is a powerful way to reason automatically Prover should be independent of KB syntax Prover should use control strategy that is fast Prover can support a human by Checking a proof by lling in 39d s Person can kill offsearch even if semidecidable Practical theorem provers BoyerMoor First rigorous proof of cooel incompleteness Theorem Solved several open questions in comoinatorial logic QP Solved F39 Roooins algebra a proof of aXlOmS required for Boolean algebra rubl m posed in was and solved in l997 arter eignt days or computation Practical theorem provers Veri cation and synthesis of hardsoft ware So ware Verify a program s output is correct for all inputs There eXlStS a program Pi tnat satisnes a specincation Hardware Verify tnat interactions between signals and circuits is robust 7 Nil CPU Elfle all cundltluns There eXlStS a circuit c tnat satisnes a specincation Statistical Learning Methods Chapter 20 Statistical learning Bayes maximum Ikelihood Hidden variables expectation maximization Markov models Instancebased Nearest neighbor Neural networks Rational agents Up until now Ma y rules were available and rationality was piecing rules together to accomplish a goal Inference and deduction Now Lots of data available causeeffect pairs and rationality is improving performance with data Model building generalization prediction How early will my son be born Logic from first principles I think he will be born tomorrow 20 literals corresponding to 20 dates Wellfed momx gt late x latex quot impa ientfatherx gt thisWeekend x latex quot impatientmotherx gt tomorrowx Page 4 CS 416 Artificial Intelligence Lecture 10 Logical Agents Chapter 7 Midterm Exam Midterm will be on Thursday March 13 h Itwill cover material up until Feb 27th Chess Article Garry Kasparov re ects on computerized chess IBM should have released the contents of Deep Blue to chess community to advance research of computation as it relates to chess Kudos to Deep Junior for putting information in public domain so state ofthe art can advance Dee Blue made one good move the surprised Kasparov though he thinks a person was in the loo Deep Junior made a fantastic sacri ce that re ects a new accomplishment for computerized chess httplmmopinionjournalcomextralid110003081 Logical Agents What are we talking about logical Aren t searchbased chess programs logical Yes but knowledge is used in a very speci c way rWlnthe ame 7 Not useful for extracting strategies or understanding otner aspects ess We want to develop more generalpurpos e knowledge systems that support a variety of logical analyses Why study knowledgebased agents Partially observable environments combine available information percepts with general knowledge to select actions Natural Language Language is too complex and ambiguous Problemsolving agents are impeded by high branching factor Flexibility Knowledge can be reused for novel tasks New knowledge can be added to improve future performance Components of knowledgebased agent Knowledge Base Store information knowledge representation language Add information Tell Retrieve information Ask Perform inferen e derive new sentences knowledge 39om existing sentences Page 1 The wumpus world But you have sensing and action A scary world indeed male in a cave rAWurnpus who will eat you 7 One arrow that can kill the Wurnpus Sensing each is either on or off a single bit rWurnpus emits a stehch ll l adiaceht squares e pits cause a breeze ll l adiaceht squares 7 gold causes glitteryou see when ll l the square rwalking ll ito waii causes a bump e Pits that cah ehtrao you out ho the wurhous rorrtrstooiarge to raii ll l 7 death orwurhous can be heard eYeernere ll l world 7 A neap or gold somewhere But you have sensing and action An example Action 7 You can turn left or hght 90 degrees 7 You can move rorward 7 You can shoot an arrow ll l yourfacing direction An example Our agent played well 7 Used rhrerehce to relate two drrrereht percepts observed from different locations rAgent is guaranteed to draw correct conclusions rr percepts are correct Page 2 Knowledge Representation Logical Reasoning lvlust oe syntactically and semantically correct EntaiIment yntax 7 one sentence follows logically from another 7 the formal specificatiun or how information is stored a I 3 m wpm a mfmfmama Wm the sentence a entails the sentence in a i eea max 7 aegtb it and only it Sernaritics every model in Wnien a istrue o is aise true 7 the meaning or the infurmatiun a o2c cmu helmurelhana An example Model Checking After one step in Wurnpus World The agent wishes to check all models ofthe n rmvvledge base is quot game in which a pit is in the three candidate rules mgam spots percents a breeze in 2 i H i H H e Askthe kair neieisaoitin Enumerate all model adiaeent squares Where three candidate I new i spots may have pits M e 3 pltS two conditions eacl ii 2i air u e23Eigntinodes 39t Checking entailment Checking entailment Can There is no pit in 1 2quot be true Can There is no pit in 2 2quot be true 7 is Obi true 7 is at true rForall models Where kt rForallmodelsWhere lStrLle a1 is true aiso lStrLle 061 is notalwag Kaeoq true also 7 kB does not entail a2 Page 3 Logical inference Entailment permitted logic 7 We infen ed neW knowledge from entailrnentS Model Checking e We enumerated all possibilities to ensure inference was corn plete Inference Algorithms Sound 7 only entailed sentences are inferred e inference algoritnrn can oeriye any sentence tnat is entailed r can inference algoritnrn become caugnt in infnite loop Propositional Boolean Logic Syntax of allowable sentences 7 atomic sentences lndlvlslblE syntactic elernents cine propositional syrnpcil Use uppercase letters as representa icin True and False are predefined proposition syrnpcils Complex sentences Formed from symbols using connectives e not tne negation M and tne conlunctlon e y or tne disiunction e gtirnplies tneirnplication e lt22 if and only if tne biconditional BackusNaur Form BN F iiiiiiin 7 iiiiiiuisniiiiiiii iiiiiiiiiii iiiiiini i new miniiii lQ Rl iiiiiiiiisiiiiiiii Tnl viiinlmi 7 r r iriiiiilirniniiiin eiiiii iiiiiiiiiii riuiiiii I l iiniiiiii l mini ioiuiiiiii xiiiiiiiiir Propositional Boolean Logic Semantics giyen a particularrnooel Situation wnat are tne rules tnat determine tne trutn of a sentence 7 use a trutn table to cornpute tne yalue of any sentence Witn respect to a model by recursiye evalua ion Page 4 mm 1 x mm Mth m a rlmvtlwntlquot u nttl rt Truth table r Ilv l39nu r m mlvlu WWW w n I lt lav lurdr m t at wt m m lethl u u Example from wumpus A square l5 breezy only lfa nelgnborlng square nas a plt EM F 12V A square l5 breezy lfa nelgnborlng square nas a plt PleP2 JgtEl Forrnerl5 more powerful and true to wurnpus rules Awump e lnltlal cundltluns n us knowledge base Inference P quotD MW H H M N M Does KB entail aKB gt 0 7 Rules ufElrEEZEs furafew r ls tnere a mt n l 21 P1 a exaRmpEle safest H M w w rconelderonlywnatwe need 39 2 u 2 2r jazwwwruvao EMEUPMPHPUPHF39M pmems w 4 17 t Z7permutatluns ufrnudelstu check Rt gall M rForeacln model see lfKB lstrue Weknsow k W W W W n 2113 arm n rForallKBflrueseelfalstrue 1 2 3 a 5 H Inference Concepts related to entailment Truthtable luglcalequlvalence e a and l are lugrcallyequwalent lltneyaretrue rntne same set qr wallle urtautulugy r a sentence that lsvalld m all mudels p w dedu mntnemem aentallsbltandanlvnalmpllesb satlsflablllty r a sentence that lStYLlE n some mudel e a entallsb a aquotb ls unsatrsnaule Page 5


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.