Intelligent Systems (AI2) Computer Science cpsc422, Lecture 21 Oct, 23, 2019 Slide credit: some slides adapted from Stuart Russell (Berkeley), some from Prof. Carla P. Gomes (Cornell) CPSC 422, Lecture 21 Slide 1 David Buchman and Professor David Poole are the recipients of the UAI 2017 Best Student Paper Award, Why Rules are Complex: RealValued Probabilistic Logic Programs are not Fully Expressive. This paper proves some surprising results about what can and what cannot be represented by a popular method that combines logic and probability. Such models are important as they let us go beyond features in machine learning to reason about objects and relationships with uncertainty.

CPSC 422, Lecture 21 Slide 2 Lecture Overview Finish Resolution in Propositional logics Satisfiability problems WalkSAT Start Encoding Example CPSC 422, Lecture 21 3

KB | Proof by resolution KB | equivalent to : KB unsatifiable Key ideas equivalent to : KB unsatifiable KB | equivalent to : KB unsatifiable Simple Representation for KB Simple Rule of Derivation

CPSC 322, Lecture 19 Conjunctive Normal Form (CNF) RewriteKB into conjunction of disjunctions literals (A B) (B C D) Clause Clause Any KB can be converted into CNF ! CPSC 322, Lecture 19 5

Example: Conversion to CNF A (B C) 1. Eliminate , replacing with ( )( ). (A (B C)) ((B C) A) 2. Eliminate , replacing with . (A B C) ((B C) A) 3. Using de Morgan's rule replace ( ) with ( ) : (A B C) ( ( B C) A) 4. Apply distributive law ( over ) and flatten: (A B C) (B A) (C A) CPSC 322, Lecture 19 Example: Conversion to CNF

A (B C) 5. KB is the conjunction of all of its sentences (all are true), so write each clause (disjunct) as a sentence in KB: (A B C) (B A) (C A) CPSC 322, Lecture 19 Full Propositional Logics DEFs.

Literal: an atom or a negation of an atom Clause: is a disjunction of literals Conjunctive Normal Form (CNF): a conjunction of clauses INFERENCE: Convert all formulas in KB and CNF Apply Resolution Procedure CPSC 422, Lecture 21 in 8 Resolution Deduction step

Resolution: inference rule for CNF: sound and * (A complete! B C) ( A ) If A or B or C is true, but not A, then B or C must be true. (B C ) (A B C ) ( A D E ) If A is false then B or C must be true, or if A is true then D or E must be true, hence since A is either true or false, B or C or D or E must be true.

(B C D E ) (A B ) ( A B ) (B B ) B Simplification CPSC 322, Lecture 19 Resolution Algorithm The resolution algorithm tries to prove: KB is converted in CNF Resolution is applied to each pair of clauses with complementary literals Resulting clauses are added to the set (if not already there) Process continues until one of two things can happen:

1. Two clauses resolve in the empty clause. i.e. query is entailed 2. No new clauses can be added: We find no contradiction, there is a model that satisfies the sentence and hence we cannot entail the query. CPSC 422, Lecture 21 10 Resolution example KB = (A (B C)) A = B KB True! False in all worlds

CPSC 422, Lecture 21 Slide 11 CPSC 422, Lecture 21 Slide 12 Lecture Overview Finish Resolution in Propositional logics Satisfiability problems WalkSAT

Hardness of SAT Start Encoding Example CPSC 422, Lecture 21 13 Satisfiability problems Consider a CNF sentence, e.g., (D B C) (B A C) (C B E) (E D B) (B E C) Is there an interpretation in which this sentence is true (i.e., that is a model of this sentence )? Many combinatorial problems can be reduced to checking the satisfiability of propositional sentences (example later) and returning the model

CPSC 422, Lecture 21 Slide 14 How can we solve a SAT problem? Consider a CNF sentence, e.g., (D B C) (A C) (C B E) (E D B) (B E C) Each clause can be seen as a constraint that reduces the number of interpretations that can be models Eg (A C) eliminates interpretations in which A=F and C=F So SAT is a Constraint Satisfaction Problem: Find a possible world that is satisfying all the constraints (here all the clauses)

CPSC 422, Lecture 21 Slide 15 WalkSAT algorithm (Stochastic) Local Search Algorithms can be used for this task! Evaluation Function: number of unsatisfied clauses WalkSat: One of the simplest and most effective algorithms: Start from a randomly generated interpretation Pick randomly an unsatisfied clause Pick a proposition/atom to flip (randomly 1 or 2) 1. Randomly 2. To minimize # of unsatisfied clauses

CPSC 422, Lecture 21 16 WalkSAT: Example (D B C) (A C) (C B ) (E D B) (B C ) Look at algo on previous slide CPSC 422, Lecture 21 Slide 17 Because by flipping B we are left with only 1 unsatisfied

clause, while by flipping E with 3 and by flipping D Pseudocode for WalkSAT pw pw pw pw 1 pw 2

pw = possible world / interpretation CPSC 422, Lecture 21 Slide 18 The WalkSAT algorithm If it returns failure after it tries max-flips times, what can we say? A. The sentence is unsatisfiable B. Nothing C. The sentence is satisfiable Typically most useful when we expect a solution to exist CPSC 422, Lecture 21 Slide 19

Hard satisfiability problems Consider random 3-CNF sentences. e.g., (D B C) (B A C) (C B E) (E D B) (B E C) m = number of clauses (5) n = number of symbols (5) Under constrained problems: Relatively few clauses constraining the variables Tend to be easy E.g. For the above problem16 of 32 possible assignments are solutions (so 2 random guesses will work on average) CPSC 422, Lecture 21 Slide 20

Hard satisfiability problems What makes a problem hard? Increase the number of clauses while keeping the number of symbols fixed Problem is more constrained, fewer solutions You can investigate this experimentally. CPSC 422, Lecture 21 Slide 21 P(satisfiable) for random 3-CNF sentences, n = 50 m = number of

clauses n = number of symbols Hard problems seem to cluster near m/n = 4.3 (critical point) CPSC 422, Lecture 21 Slide 22 Lecture Overview Finish Resolution in Propositional logics

Satisfiability problems WalkSAT Start Encoding Example CPSC 422, Lecture 21 23 Encoding the Latin Square Problem in Propositional Logic In combinatorics and in experimental design, a Latin square is an n n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Here is an example: Here is another one:

A B C C A B B C A

Encoding Latin Square in Propositional Logic: Propositions Variables must be binary! (They must be propositions) Each variables represents a color assigned to a cell. Assume colors are encoded as integers x {0,1} ijk Assuming colors are encoded as follows (black, 1) (red, 2) (blue, 3) (green, 4) (purple, 5) x 233 True or false, ie. 1 or 0 with respect to the interpretation represented by the picture?

How many vars/propositions overall? Encoding Latin Square in Propositional Logic: Clauses Some color must be assigned to each cell (clause of length n); (x x x ) ij ij1 ij2 ijn (x x x ) ik i1k i2k ink No color is repeated in the same row (sets of negative binary clauses); ( x x ) ( x x ) ( x x )( x x ) ik i1k i2k i1k i3k

i1k ink ink i(n 1)k How many clauses? Logics in AI: Similar slide to the one for planning Propositional Definite Clause Logics Propositional Logics Description Logics Ontologies

Semantic Web Information Extraction Semantics and Proof Theory First-Order Logics Satisfiability Testing (SAT) Production Systems Hardware Verification

Product Configuration Cognitive Architectures Video Games Summarizatio n Tutoring Systems CPSC 422, Lecture 21 Slide 27 Relationships between different Logics (better with colors)

CPSC 422, Lecture 21 Slide 28 Learning Goals for todays class You can: Specify, Trace and Debug the resolution proof procedure for propositional logics Specify, Trace and Debug WalkSat Encode the Latin square problem in propositional logics (basic ideas) CPSC 422, Lecture 21 Slide 29 Next class Mon Finish SAT example

First Order Logic Extensions of FOL Assignment-3 will be posted on Wed! CPSC 422, Lecture 21 30 Midterm, Fri, Oct 25, we will start at 4pm sharp How to prepare

Go to Office Hours (I am offering one more Thur 9-10) Learning Goals (look at the end of the slides for each lecture complete list has been posted) Revise all the clicker questions and practice exercises Practice material has been posted Check questions and answers on Piazza CPSC 422, 422, Lecture CPSC Lecture 19 18 Slide 3131