# 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). References [this](http://lib.ysu.am/disciplines_bk/efdd4d1d4c2087fe1cbe03d9ced67f34.pdf) textbook.

## Table of Contents
- Introduction to AI - history and models
- Knowledge representation and reasoning

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

- **Act human -- 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. Ex: using NLP to simulate the human language without copying neural mechanisms
- **Think like a human -- Cognitive Science approach**: computationally model and REPLICATE human cognition (emotions, biology, intention) as closely as possible. ML mechanics should match neural mechanics


- **Think rationally: Engineering approach:** algorithmically optimize a given tasks by borrowing human reasoning systems (symbolic ai)


- **Act rationally: Rational agent**: find the best action to get to a goal by forming a plan of actions.

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

AI systems adopt ethical policies proposed by schools of philosophy. - Dentological ethics proposes that decisions must be fundamnetally made under ethical principles (ex; don't tell a lie).
- Utilitatian philosophy argues that the expected gain of the output should outweigh the expected cost.

### History
**Inception** (1943 - 1956)
- Neurological motivation: perceptron model representing each neuron in a binary on/off state to simulate a single ouput with inputs
- **Hebian learning**: proposes that the strength of connections between neurons increased based on the neurons that activate together (unsupervised model)
- Turing Model formalized the process of computation: a machine that can manipulate symbols (i.e. inputs) based on a series of rules (i.e. policies and nodes)

**Enthusiasm** (1950 - 1969)
- **physical symbol system** proposed that intelligent systems must be able to manipulate symbolic structures. initially formalize from the gps system which is modeled after human cognition
- **Lisp** was a high level programming language for AI reasoning by extracting discrete representations of the world throough logical axioms
- **perceptron convergence theorm** demonstrated that perceptrons can self-adjust connection strengths and weights (i.e. learn) until it gets to the optimal output

**AI Winter 1966 - 1973**
- **machine evolution/genetic programming** attempted to show that machine programs can randomly mutuate and select the optimal option until it "evolves" into the optimal outoput result

**Expert systems** (1969 - 1986)
- Design of expert systems that optimize ai systems in niche domains

**Neural networks and probabilistic reasoning** (1986 - now)
- Introduction of symbolic systems
- Introduction of probability-based reasoning model instead of boolean logic and shared data repositories for data training

**Big data** (2001 - now)
- Proliferated by the creation of the World Wide Web
- data labeling problem. fix all the data that have wholes in them to get high quality data that models can train on

**Deep learning** (2011 - now)
- CNNs and multiple layers of neurons

---

## Knowledge Representation and Reasoning
Our goal is to answer the questions: "how can we represent knowledge in a way humans can understand?". Subfields include computational linguistics (i.e. natural language processing).
Naive logic is usually used to represent AI reasoning systems. This helps make reasoning processes structured and explainable since they can be deduced to "first principles" (hence, first order logic)

### Propositional logic representation
**Propositional logic** is the most naive form of reasoning that tells you if a statement is true or false. These are the building blocks of more complex reasoning (called first order logic). An anology is counting numbers or reading "ABCs" for humans.

Knowledge information can be represented in a truth table, which can show how different combinations of T/F values leads to different outcomes.

### First order knowledge (FOL) representation
FOL logic builds on top of **propositional logic** to form more complex thoughts and propositions about how objects related to each other. This represents information with **quantifiers** which represent how information relates to each other. This is closer to how humans think and reason.

**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:
$$
∀x (isCat(x) → isMammal(x))
$$

Exisential quantifier ("there exists an object..."):
$$
∃x P(x) ≡ P(a) ∨ P(b) ∨ P(c)
$$

Universal instantiation ("All objects are..."):
$$
∀x P(x) ≡ P(a) ∧ P(b) ∧ 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:
$$
∀x P(A) → ¬¬P(A)
$$

### Reasoning with FOL
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*.

**Common reasoning patterns**
- Conjunctive Normal Form (CNF) is a way to constrain a search space by setting specific rules that the system must follow
$$
(A ∨ B) ∧ (¬C ∨ D)
$$
- Disjunctive Normal Form (DNF) selects the next best option if one of the conditions is satisfied. Used for building structures.
$$
(A ∧ B) ∨ (¬C ∧ 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 an algorithm used to prove that a statement is true. This is primarily used by AI systems to reason about the truthworthiness of information. Logic is represented compositionally, similar to how humans reason about information:
- We break complex logic into pieces (clauses).
- We use contradictions in logic to reduce the problem space one step at a time
- Trees represent combinations of smaller results into bigger ones and vice versa.

More formally, it's proves that a conclusion "S" can be logically derived from "KB" (Knowledge base). It does this by *proving entailment using first order logic*. This is syntactically easier for the computer to compute through **string manipulation**.


The naive algorithm:
1. Formulate a knowledge base of information. All clauses must be *disjunctions*.
2. Assume the opposite of the conclusion.
3. Combine the clauses with *conjunction*. The final expression must be in CNF form
4. "Resolve" clauses (i.e. combine facts) until a contradiction (EMPTY state) is reached, at which point you can prove that the original statement is true. The same clauses can be repeated in the combination

*note that not all the clauses need to be used. Only a subset that is relevant to the contradiction is necessary.*

The goal is to reach an **empty clause** at the very end of resolution. This means that all clauses have been resolved to a point where ¬A and A clauses both exist, therefore creating a contradiction (⊥) after resolution. Thus proving that the original un-negated statement given KB is true.

The general form is:
$$
KB ⊨ S
(S ∨ Q) ∧ (¬Q ∨ R) ⊢ (S ∨ R)
$$
- KB = Knowledge Base
- S = Sentence

KB and S are identical. Thus $KB ∧ ¬S$ is always false becasue it's a contradiction thus the following are the same:
$$
KB ∧ ¬S ≡ FALSE
$$
$$
KB ∧ ¬S ⊨ 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

## Bayesian Learning
### Proabilities
### Bayesian Networks

## Perceptron Learning
### Single layer perceptrons
### Multilayer perceptrons

## Planning agents

---

## Decision Theory
### Constraint Satisfaction Problem

## Search Algorithms
Components:
1.
Algorithm:
1. Begin with a tree with only one node (start state)
2. Check if there are **fringe nodes** (organized as a list of unexplored nodes). If there are no unexpanded nodes, stop. Else, pick an unexpanded fringe node $n$ with state $s(n)$
3. Check if this is the goal state. Expand n by creating a child node of n for each of the successor states of s(n).
### Uniformed Search
### Heuristic Search
Heuristic search algorithm uses a heurstic search function which finds the locally optimal solution instead of exploring all solutions to find the globally optimal one.

It models human cognition by following three principles. Problem relaxation simplifies the problem to capture its essence. Admissibility allows for safe estimates that do not overestimate the total risk. Consistency ensures that changes in the prediction are gradual and reasonable without large oversteps:
- **Problem Relaxation** is the process of reducing rules and constraints to make it easier for the algorithm to find an optimal solution.
- **Admissibility** describes wether an algorithm overestimates the real cost. Heuristics are highly admissible because they never overestimate the true cost but only underestimate it.
- **Consistency** assumes that every step should reduce the estimated cost no more than the actual cost (i.e. we always underestimate):
$$
h(n) ≤ c(n, n') + h(n')
$$

## Additional readings
- [cognitive science approach to ai](https://uxmag.com/articles/how-cognitive-science-and-artificial-intelligence-are-intertwined)
- [primary textbook](http://lib.ysu.am/disciplines_bk/efdd4d1d4c2087fe1cbe03d9ced67f34.pdf)