CSCI 360

An introduction to artificial intelligence.

Course logistics

Grades are not curved
The textbook is recommended, but strong retention of the slides is believed to be sufficient.
Projects are assigned on Friday, and are due 2-3 Fridays later.

Designing rational agents

An agent is an entity that perceives and acts. A rational agent selects actions that maximize its (expected) utility. Characteristics of the percepts, environment, and action space dictate techniques for selecting rational actions

Propositional logic

This class has so far covered a lot of propositional logic. A useful resource to reference for terms and formulae is the propositional calculus article on Wikipedia.

The conventional variable names used for propositional variables are $p$, $q$, $r$, etc.

The unary operator negation, denoted $\neg$, is used to negate a propositional variable. Negation is sometimes referred to as the "complement" of a propositional variable.

Two or more propositional variables are linked together by a logical operators known as a connective. The two primary connectives are the conjunction "$\land$" and disjunction "$\lor$".

conjunction: Let $p$ and $q$ be propositions. The conjunction of $p$ and $q$, denoted by "$p \land q$", pronounced "$p$ and $q$", is true when both $p$ and $q$ are true and is false otherwise.
disjunction: Let $p$ and $q$ be propositions. The disjunction of $p$ and $q$, denoted by "$p \lor q$", pronounced "$p$ or $q$", is false when both $p$ and $q$ are false, and is true otherwise.

The input to a truth function consists of one or more propositional variables, each of which is either true or false.

De Morgan's laws

Negation of Conjunction:
- $\neg (p \land q) \equiv (\neg p \lor \neg q)$
Negation of Disjunction:
- $\neg (p \lor q) \equiv (\neg p \land \neg q)$

Conditional statements

Given a antecedent $p$ and a consequent $q$, the implication $p \implies q$, read as "$p$ implies $q$", or "if $p$, then $q$" is only false when both $p$ is true and $q$ is false, otherwise it is true.

Implication is also referred to as a conditional statement

Note: When the antecedent $p$ is false, $p \implies q$ is true regardless $q$. In this situation,the implication $p \implies q$ is referred to as a vacuous truth.

In formal logical notation:

$$ p \implies q \equiv \neg p \lor q $$

From this, we can also derive the equivalence

$$ \neg (p \implies q) \equiv (p \land \neg q) $$

The biconditional $p \iff q$, pronounced "$p$ if and only if $q$", is a connective that is true when $p$ and $q$ are both true and false when $p$ and $q$ are both false.

Module 0 Reading: "Artificial Intelligence and Automation"

Optimization is the process of determining which inputs can be provided to a function so as to minimize the function's output.
The continuous function minimization problem under constraints is typically solved using a strategy known as gradient descent.
Gradient descent is a local search which bases each of its subsequent iterations on the result of the previous iteration, choosing values for its inputs that result in the greatest decrease in the value of the output.
The discrete function minimization problem is the discrete analog of the continuous function minimization problem under constraints, and is typically solved using a strategy known as hill climbing.
Hill climbing is a local search which determines its subsequent iterations by choosing the neighbor of the current set of parameters that results in the highest positive increase in value.
The agent is exploring when it chooses a neighbor with an output with a lesser level of optimization.
The agent is exploiting when it chooses a neighbor with an output with a greater level of optimization.
The field of knowledge representation and reasoning concerns itself with representing information about the world in a form that a computer system can utilize to solve complex tasks.

Note: At the rate I was going, there was no way I was going to be able to finish Module 0 in a reasonable amount of time, so I began skimming through the remaining pages of the handout.

Logical Entailment

A set of antecedents $P_1, P_2, \dots, P_n$ are said to entail the consequent if and only if every truth assignment that satisfies the antecedents also satisfies the consequent.

Conjunctive Normal Form

In boolean arithmetic, the conversion of $(A \land B) \lor (C \land D)$ into conjunctive normal form can be done as shown below:

$$ (A \land B) \lor (C \land D) \newline \dots \newline (A \lor (C \land D)) \land (B \lor (C \land D)) \newline \dots \newline (A \lor C) \land (A \lor D) \land (B \lor C) \land (B \lor D) $$

Note: This is, by no coincidence, very familiar. Recall how performing the F.O.I.L. operations works, which we learned back in Algebra I for $(a + b) * (c + d)$

$$ (a + b) * (c + d) \newline \dots \newline a(c + d) + b(c + d) \newline \dots \newline ac + ad + bc + bd $$

Module 2

Rule-Based Expert Systems

Taxonomic knowledge states relationships such as "All X are Y" and "All Y are Z".

Representing this as a knowledge base in first order logic is possible but it is difficult and slow to interpret by humans and computers alike.

An alternative to first order logic is rule-based expert systems, which store knowledge in a form that can be manipulated by a computer.

Resolution is an inference mechanism used in propositional logic, in which the goal is to determine if "the knowledge base entails the query."

Rule-Based Expert Systems

are easier for humans to understand and modify than the equivalent representation of the rules as a complex web of resolutions using first order logic
can perform more powerful reasoning tasks than resolution using first order logic
are less powerful than resolution using first order logic in terms of its inference capabilities
are easier to implement and runs more efficiently than resolution using first order logic

Modus Ponens

First-Order Logic: $P \land P \to Q \vDash Q$

Propositional Logic: $\forall A[P(A) \land \forall x [P(x) \to Q(x)] \vDash Q(A)]$

Forward Chaining

Good for determing everything we can know from a given set of facts.

Backward Chaining

Backward chaining is a query-driven form of reasoning, driven by a hypothesis.

Good for verifying a hypothesis that we surmised from a particular situation.

Ontology

Ontology is the branch of philosophy that studies concepts such as existence, being, becoming, and reality. Ontologists often try to determine what the categories or highest kinds are and how they form a system of categories that provides an encompassing classification of all entities.

Question: What is the difference between ontology and taxonomy?

Semantic Networks

Semantic Networks use a special purpose reasoning procedure called pointer following to make it easier to determine relationships between properties through the inheritance of properties by inheriting entities.

First order logic is monotonic, meaning that if a statement is true, then it is true for all possible values of its variables. Edge cases like "I saw a bird, so it can fly, since birds fly", are better suited for semantic networks, which allow for generalizations, in spite of edge cases such as "penguins are birds, but penguins cannot fly."

Properties of Semantic Networks

Properties (some versus first-order logic) Knowledge base (appears) easy to understand by humans but its semantics is often not well defined in practice

Problems with multiple inheritance of incompatible properties
More expressive than first-order logic, for example, allows for default reasoning
Less expressive (or more complicated) than first-order logic with regard to some logical operators such as negation and disjunction
Some reasoning is easy to implement and efficient but limited in capability due to special-purpose reasoning procedures

Heuristic Search:

Date: 2021-10-28

A* doesn't necessarily terminate when it first finds the vertex of the terminus

Date: 2021-10-26

Example Problems Covered:

Map Coloring with Two Colors
N-Queens (Backtracing)

Uninformed Search

Date: 2021-10-21

Breadth-First Search
Depth-First Search
Uniform-Cost Search

SAT-Based Planning

Date: 2021-10-19

The planning problem is defined at the start of the problem statement
There is a start state and a goal state
There are operator schemata which contain preconditions and effects

A planning problem is transformed into a Boolean satisfiability problem in the form of a propositional sentence.

The interpretation that makes the proposition true is the solution to the satisfiability problem, which in turn is the solution to the planning problem.

$$Q_t \pi = u$$

Today marks the final in-person lecture of the semester.

Types of intelligent agents:

Rational
- An agent designed to be intelligent as it pertains to solving a particular task or job
Believable
- An agent that behaves like a human
Cognitive
- An agent that thinks like a human

Core areas of artificial intelligence:

Knowledge representation and reasoning
Machine learning
Planning
Multi agent coordination
Interfaces
- Vision
- Robotics
- Natural language processing

hello world