CS 171: Introduction to AI

Compilation of material from CS 171 (Introduction to AI course) at UC Irvine taught by Professor Koeing. Foucses on understanding how systems act and make decisions rationally. Main concept focuses on the theoretical transition point from high level percepts (sensor, cv, etc) into high level actions (commands).

Introduction

Artificial agents are referenced from human agents which operate based on a cycle of making sense of an environemnt (investigation) and acting on it.

• Cognitive Science approach: computationally model and REPLICATE human cognition (emotions, biology, intention) as closely as possible.
• Engineering approach: algorithmically optimize a given tasks by borrowing human reasoning systems
  

Turing test: Cog Sci will say an intelligent AI must "think" like a human in order to pass the test, while the Engineering approach says AI should "act" like a human

There are three elements of AI: knowledge representation -> learning -> search/filtering

Knowledge Representation and Reasoning

First order knowledge representation

Knowledge (english sentences) is uses propositional logic to represent it as a first-order reasoning structure.

Syntax is the representation of a well-formed sentence that follows the precedence rules of propositional logic. An example of the precedence order is shown below.

• usually the machine needs the interpretation (input) to form an output
• topologies (always true) and contradictions (always false) do not require interpretations

These are the components of a logic statement:

• predicate
  $P(A)$: a declared statement that takes a variable as a parameter and returns a truth value (ex: isCat)
• function: takes in multiple variables (obj) and returns another obj

Example:

$$\forall x(isCat(x)\to isMammal(x))$$

Exisential quantifier ("there exists an object…"):

$$\exists x P(x)\equiv P(a)\vee P(b)\vee P(c)$$

Universal instantiation ("All objects are…"):

$$\forall x P(x)\equiv P(a)\wedge P(b)\wedge P(c)$$

Computer representation

The computer needs the definition of a predicate, function, and input variables. Here is the naive approach:

• predicate: set of
  $(input,output)$ where inputs∈numbers and ouput∈T/F.
  • In first order logic, all sets are infinite which makes it challenging for the computer to parse completely
• function: table of objs

A computer interprets a tautology/contradiction based on the Abstract Predicate (P(A)) where it must be true no matter the value of A or P(). In other words, it must be true for every interpretation. An example of this is:

$$\forall xP(A)\to \neg \neg P(A)$$

Reasoning

You can reject a proposition by creating a truth table, given that the predicate set is finite. Note that this cannot be used for first-order logic because the sets are infinite.

Conjunctive Normal Form (CNF) is a way to constrain a search space by setting specific rules that the system must follow

$$(A\vee B)\wedge (\neg C\vee D)$$
Disjunctive Normal Form (DNF) selects the next best option if one of the conditions is satisfied. Used for building structures.

$$(A\wedge B)\vee (\neg C\wedge D)$$

Equilvalence(A≡B) indicates that variable A is equal to varibale B

Semantic Entailation (A⊨B) indicates that variable A always leads to varibale B, but not vice versa. This is what humans understand.

Syntatic Entailment (A⊢B) is used to prove entailment. This is what the computer understands

Resolution is the process of proving entailment and first order logic. This is syntactically easier for the computer to compute through string manipulation. The general form is:

$$KB\models S$$

• KB = Knowledge Base
• S = Sentence

KB and S are identical. Thus

$KB\wedge \neg S$ is always false becasue it's a contradiction thus the following are the same:

$$KB\wedge \neg S\equiv FALSE$$

$$KB\wedge \neg S\models FALSE$$

example:

# given
(S ∨ Q) ∧ (¬Q ∨ R) 

# output
# 1. identify that there is a clause with a symbol (Q) and its negation (¬Q) exists
# 2. if so, change the divider between two clauses (in this case, ∧) and turn to opposite
# 3. return final output with ⊢ (synatactic "entails")
(S ∨ Q) ∧ (¬Q ∨ R) ⊢ S ∨ R

Additional readings

• cognitive science approach to ai
• primary textbook