CSCE 420 Lecture 15

« previous | Thursday, March 7, 2013 | next »

Begin Exam 2 content

WalkSAT

function WalkSAT(clauses, p, max-flips) returns a satisfying model or failure
  inputs: clauses   - a set of clauses in propositional logic
          p         - the probability of choosing to do a "random walk" move
          max-flips - number of flips allowed before giving up
  model := a random assignment of true/false to the symbols in clauses
  for i from 1 to max-flips do
    if model satisfies clauses then return model
    clauses := a randomly selected clause from clauses that is false in model
    if RandFloat() < p then flip the value in model of a randomly selected symbol from clause
    else flip whichever symbol in clause maximizes number of satisfied clauses
  end for
  return failure
end function

Ruby Pseudo-Implementation

def walk-sat clauses, p, max_flips
  model = clauses.symbols.reduce({}) {|h,s| h[s] = [true, false].sample}
  max_flips.times do
    return model if clauses.all? {|c| c.eval(model)}
    clause = clauses.select {|c| not c.eval(model)}.sample
    if rand < p
      model[clause.symbols.sample] = not clause.symbols.sample
    else
      symb = clause.symbols.max_by {|s| clauses.count {|c| c.eval(model + {symb => not model[symb]} }}
      model[symb] = not model[symb]
    end
  end
end

In general, hardness spikes around 4.3 clauses per symbol

First Order Logic

Expressive, unambiguous use for Knowledge bases, expert systems, and knowledge base agents

• Syntax
• Semantics
• Inference
• …
• Uncertainty

Syntax

Propositional logic + variables + quantifiers

<sentence> ::= <atomic> | <complex>

<atomic> ::= <predicate>

(* predicates are like propositions with arguments *)
<predicate> ::= <predname> '(' {<term>} ')'

<term> ::= <constant> | <variable> | <functions>

<constant> ::= /\w+/

<variable> ::= ['?'] /\w+/

<function> ::= <funcname> '(' {<term>} ')'

<complex> ::= '(' <sentence> ')'
            | '¬' <sentence>
            | <sentence> <connective> <sentence>
            | <quantifier> <variable> <sent>

<connective> ::= '∧' | '∨' | '⊕' | '→' | '↔'

<quantifier> ::= '∀' | '∃'

Example sentence: $\forall p\quad have(p,BSdegree)\implies graduate(p)$

More about predicates:

• value can be either true or false
• can be used to assert relations among objects
• can be used to represent concepts
• Unary predicates are properties
• Special infix predicate: equality

"All mammals are animals, have fur, and give birth to live young "

$\forall x\quad mammal(x)\iff animal(x)\wedge has\_fur(x)\wedge viviparous(x)$

Knowledge engineering (Ontology): Choosing basis concepts (predicates) and writing axioms to define other concepts

Peano Axioms

Define Natural numbers:

• $num(0)$
• $\forall n\quad num(n)\implies num(succ(n))$
• $\forall n,m\quad num(n)\wedge num(m)\wedge n\neq m\implies succ(n)\neq succ(m)$
• $\forall n\quad succ(n)\neq 0$
• $\forall n\quad plus(0,n)=n$
• $\forall n,m\quad plus(succ(n),succ(m))=plus(n,succ(succ(m)))$