Logic & Probability

CSCI 4511/6511

Joe Goldfrank

Announcements

  • Homework 2 is due on today February at 11:55 PM
    • Grace days
  • Homework 3 is released
    • Working with one partner is optionally permitted
  • Midterm Exam on 7 Mar

Midterm Exam on 7 Mar

  • In lecture
    • COR 103, 12:45 PM
  • 100 minutes
  • Open note:
    • Ten sides1 of handwritten notes permitted

CSPs

States, Variables, Domains

  • State variables: \(X_1, X_2, ... , X_n\)
  • State variable domains: \(D_1, D_2, ..., D_n\)
    • The domain specifies which values are permitted for the state variable
    • Domain: set of allowable variables (or permissible range for continuous variables)1
    • Some constraints \(C_1, C_2, ..., C_m\) restrict allowable values

Assignments

  • Assignments must be to values in each variable’s domain
  • Assignment violates constraints?
    • Consistency
  • All variables assigned?
    • Complete

Logic

Yugoslav Logic

\(R_{HK} \Rightarrow \neg R_{SI}\)
\(G_{HK} \Rightarrow \neg G_{SI}\)
\(B_{HK} \Rightarrow \neg B_{SI}\)
\(R_{HK} \lor G_{HK} \lor B_{HK}\)

Goal: find assignment of variables that satisfies conditions

Is It Possible To Know Things?



Yes.


😌

How Even Do We Know Things?

  • What color is an apple?
    • Red?
    • Green?
    • Blue?
  • Are you sure?

Symbols

  • Propositional symbols
    • Similar to boolean variables
    • Either True or False

The Unambiguous Truth

  • It is a nice day.
    • It is difficult to discern an unambiguous truth value.
  • It is warm outside.
    • This has some truth value, but it is ambiguous.
  • The temperature is at least 78°F outside.
    • This has an unambiguous truth value.1

What Matters, Matters

  • Non-ambiguity required
  • Abitrary detail is not
  • The temperature is exactly 78°F outside.
    • We don’t necessarily need any other “related” symbols
  • What is the problem?
  • What do we care about?

Sentences

  • What is a linguistic sentence?
    • Subject(s)
    • Verb(s)
    • Object(s)
    • Relationships
  • What is a logical sentence?
    • Symbols
    • Relationships

Familiar Logical Operators

  • \(\neg\)
    • “Not” operator, same as CS (!, not, etc.)
  • \(\land\)
    • “And” operator, same as CS (&&, and, etc.)
    • This is sometimes called a conjunction.
  • \(\lor\)
    • “Inclusive Or” operator, same as CS.
    • This is sometimes called a disjunction.

Unfamiliar Logical Operators

  • \(\Rightarrow\)
    • Logical implication.
    • If \(X_0 \Rightarrow X_1\), \(X_1\) is always True when \(X_0\) is True.
    • If \(X_0\) is False, the value of \(X_1\) is not constrained.
  • \(\iff\)
    • “If and only If.”
    • If \(X_0 \iff X_1\), \(X_0\) and \(X_1\) are either both True or both False.
    • Also called a biconditional.

Equivalent Statements

  • \(X_0 \Rightarrow X_1\) alternatively:
    • \((X_0 \land X_1) \lor \neg X_0\)
  • \(X_0 \iff X_1\) alternatively:
    • \((X_0 \land X_1) \lor (\neg X_0 \land \neg X_1)\)

 

  • Can we make an XOR?

Knowledge Base & Queries

  • We encode everything that we ‘know’
    • Statements that are true
  • We query the knowledge base
    • Statement that we’d like to know about
  • Logic:
    • Is statement consistent with KB?

Models

  • Mathematical abstraction of problem
    • Allows us to solve it
  • Logic:
    • Set of truth values for all sentences
    • …sentences comprised of symbols…
    • Set of truth values for all symbols
    • New sentences, symbols over time

Entailment

  • \(KB \models A\)
    • “Knowledge Base entails A”
    • For every model in which \(KB\) is True, \(A\) is also True
    • One-way relationship: \(A\) can be True for models where \(KB\) is not True.
  • Vocabulary: \(A\) is the query

Knowing Things

Falsehood:

  • \(KB \models \neg A\)
    • No model exists where \(KB\) is True and \(A\) is True

It is possible to not know things:1

  • \(KB \nvdash A\)
  • \(KB \nvdash \neg A\)

It Is Possible To Not Know Things 😔

Lexicon

  • Valid
    • \(A \lor \neg A\)
  • Satisfiable
    • True for some models
  • Unsatisfiable
    • \(A \land \neg A\)

Inference

  • \(KB\) models real world
    • Truth values unambiguous
    • \(KB\) coded correctly
  • \(KB \models A\)
    • \(A\) is true in the real world

Inference - How?

  • Model checking
    • Enumerate possible models
    • We can do better
    • NP-complete 😣
  • Theorem proving
    • Prove \(KB \models A\)

Satisfiability

  • Commonly abbreviated “SAT”
    • Not the Scholastic Assessment Test
    • Much more difficult
    • First NP-complete problem
  • The

Deliberate typographical error!

Satisfiability

  • Commonly abbreviated “SAT”

  • \((X_0 \land X_1) \lor X_2\)

    • Satisfied by \(X_0 = \text{True}, X_1 = \text{False}, X_2 = \text{True}\)
    • Satisfied for any \(X_0\) and \(X_1\) if \(X_2 = \text{True}\)

  • \(X_0 \land \neg X_0 \land X_1\)

    • Cannot be satisfied by any values of \(X_0\) and \(X_1\)

Satisfaction

  • SAT reminiscent of Constraint Satisfaction Problems
  • CSPs reduce to SAT
    • Solving SAT \(\rightarrow\) solving CSPs
    • Restricted to specific operators
    • CSP global constraints \(\rightarrow\) refactor as binary
  • Still NP-Complete

Why Do I Keep On Doing This To You



This is the entire point of the course.


Theory and practice are the same, in theory, but in practice they differ.

CSP Solution Methods

  • They all work
  • Backtracking search
  • Hill-climbing
  • Ordering (?)

SAT Solvers

  • Heuristics
  • PicoSAT
    • Python bindings: pycosat
    • (Solver written in C) (it’s fast)
  • You don’t have to know anything about the problem
    • This is not actually true
  • Conjunctive Normal Form

Conjunctive Normal Form

  • Literals — symbols or negated symbols
    • \(X_0\) is a literal
    • \(\neg X_0\) is a literal
  • Clauses — combine literals and disjunction using disjunctions (\(\lor\))
    • \(X_0 \lor \neg X_1\) is a valid disjunction
    • \((X_0 \lor \neg X_1) \lor X_2\) is a valid disjunction

Conjunctive Normal Form

  • Conjunctions (\(\land\)) combine clauses (and literals)
    • \(X_1 \land (X_0 \lor \neg X_2)\)
  • Disjunctions cannot contain conjunctions:
  • \(X_0 \lor (X_1 \land X_2)\) not in CNF
    • Can be rewritten in CNF: \((X_0 \lor X_1) \land (X_0 \lor X_2)\)

Converting to CNF

  • \(X_0 \iff X_1\)
    • \((X_0 \Rightarrow X_1) \land (X_1 \Rightarrow X_0)\)
  • \(X_0 \Rightarrow X_1\)
    • \(\neg X_0 \lor X_1\)
  • \(\neg (X_0 \land X_1)\)
    • \(\neg X_0 \lor \neg X_1\)
  • \(\neg (X_0 \lor X_1)\)
    • \(\neg X_0 \land \neg X_1\)

Limitations

  • Consider: No cat is a vegetarian
  • Express in propositional symbols?
  • \(\neg\) First cat is a vegetarian
  • \(\neg\) Second cat is a vegetarian
  • \(\neg\) Third cat is a vegetarian …

Solutions

First-Order Logic:

  • \(\forall\) (“for all”)
  • \(\exists\) (“there exists at least one”)

Loops 🙂 :

for cat in cats:
  t = Expr(f"{cat} is not a vegetarian")
  Exprs.push(t)

Goal: find assignment of variables that satisifies conditions

Probability

Randomness and Uncertainty

  • We don’t know things about future events
    • Someone else might know
  • Example: expectimax!
    • Ghost could behave randomly
    • Ghost could behave according to some plan
    • We model behavior as random

The Random Variable

  • Uncertain future event: random variable
  • Probability:

\[P(x) = \lim_{n \to \infty} \frac{n_x}{n}\]

  • Probabilities constrained \(0 \leq P(x) \leq 1\) for any \(x\)

The Random Variable

  • In ensemble of events, what fraction represent event \(x\) ?
    • What’s troubling about this?
  • How do we quantify probability based on observations?
  • How do we quantify probability without direct observations?

Plausibility of Statements

  • “A is more plausible than B”
    • \(P(A) > P(B)\)
  • “A is as plausible as B”
    • \(P(A) = P(B)\)
  • “A is impossible”
    • \(P(A) = 0\)
  • “A is certain”
    • \(P(A) = 1\)

Probability Distribution

  • Enumerate possible outcomes1
  • Assign probabilities to outcomes
  • Distribution: ensemble of outcomes mapped to probabilities
  • Works for discrete and continuous cases

Combinatorics

  • Enumerating outcomes is a counting problem
    • We know how to solve counting problems
  • Permutations:
    • Ordering \(n\) items: \(n!\)
    • Ordering \(n\) items, \(k\) of which are alike: \(\frac{n!}{k!}\)
    • … \(k_1\), \(k_2\) of which are alike: \(\frac{n!}{k_1!k_2!}\)

I Am Extremely Sorry




…if you thought this course was going to be about LLMs

Combinatorics

  • How many possible outcomes are there?
  • How many possible outcomes are there of interest?
  • Assume all outcomes have equal probability
    • Or don’t
  • Divide
    • Weight if necessary

Choice

  • \(n\) events
  • \(k\) are of interest
    • \(n-k\) are not of interest

Possible combinations:

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

Bernoulli Trials

  • “Single event” that occurs with probability \(\theta\)
  • \(P(E) = \theta\)
  • \(P(\neg E) = 1 - \theta\)
  • Alternate notations:1
    • \(P(E^C) = 1 - \theta\)
    • \(P(\bar{E}) = 1 - \theta\)
  • Examples?

Math Notation

  • \(P(E)\)
    • Probability of some event \(E\) occuring
  • \(P\{X=a\}\)
    • Probability of random variable \(X\) taking value \(a\)
  • \(p(a)\)
    • Probability of random variable taking value \(a\)

Bernoulli Random Variable

  • Bernoulli trial:
    • Variable, takes one of two values
    • Coin toss: \(H\) or \(T\)
    • \(P\{X = H\} = \theta\)
    • \(P\{X = T\} = 1 - \theta\)

Expected Value

  • Variable’s values can be numeric values:
    • Coin toss \(H = 8\) and \(T2\)
    • \(P\{X = 8\} = \theta\)
    • \(P\{X = 2\} = 1 - \theta\)
  • Expected value:
    • \(E[X] = H \cdot \theta + T \cdot (1-\theta)\)
    • \(E[X] = 8 \cdot \theta + 2 \cdot (1-\theta)\)

Expected Value

Of a variable: \[E[X] = \sum_{i=0}^n x_i \cdot p(x_i)\]

Of a function of a variable:

\[E[g(x)] = \sum_{i=0}^n g(x_i) \cdot p(x_i) \neq g(E[X])\]

Variance

  • How much do values vary from the expected value?

\[\text{Var}(X) = E[(X - E[X])^2]\]

  • \(E[X]\) represents mean, or \(\mu\)
  • We’re really interested in \(E[|X-\mu|]\)
    • Absolute values are mathematically troublesome
  • Standard deviation: \(\sigma\) = \(\sqrt{\text{Var}}\)

Variance

\[\begin{align}\text{Var}(X) & = E[(E[X]-\mu)^2]\\ & = \sum_x (x-\mu)^2 p(x) \\ & = \sum_x (x^2 - 2 x \mu + \mu^2) p(x) \\ & = \sum_x x^2 p(x) - 2 \mu \sum_x x p(x) + \mu^2 \sum_x p(x) \\ & = E[X^2] - 2 \mu \mu + \mu^2 \\ & = E[X^2] - E[X]^2 \end{align}\]

How To Lie With Statistics

References

  • Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. 4th Edition, 2020.

  • Mykal Kochenderfer, Tim Wheeler, and Kyle Wray. Algorithms for Decision Making. 1st Edition, 2022.

  • Stanford CS231

  • Stanford CS228

  • UC Berkeley CS188