AI Algorithms  Introduction

CSCI 4511/6511

Joe Goldfrank

Good Afternoon

Course Mechanics

How To Succeed

• Pay Attention
• Start Early
• Do The Work
  • Yourself

Extremely Important Dates

Midterm Exam: 16 October

Final Exam: 4 Dec

Arrange to be present for both exams.

Grading

• 35% Homework average: weighted average of all homework
  • Lowest homework weighted 50%
• 15% Project:
  • One intermediate deliverable
• 50% Exam average: weighted average of two exams
  • Final replaces midterm if higher

Attendance

• Optional

• Recommended

• Assumed

• Office Hours

  • Why are there so many?

Office Hours

• Mon 1:00-3:00 PM
• Weds 12:30 PM - 3:00 PM
• Fri 3:00-6:00 PM
• Appointments are not necessary

The Syllabus

• Homework 0:
  • Syllabus acknowledgement
  • Python/autograder check
  • Must be completed before you get credit for anything
  • Write it yourself

Write It Yourself

• Copying code (from anywhere!) is generally prohibited, however:
  • Searching for errors, use of Stack Overflow, etc. is allowed
  • Use of code snippets from language documentation is allowed
  • Collaborating to understand the algorithms is always allowed
• Document what help you received when solving the problems

Your code will almost certainly show up on your exam.

Write It Yourself

• I check my email and respond
• Please do not use ChatGPT (etc.) to write emails to me
  • “I hope this email finds you well”
  • “I understand the importance of…”
  • “I appreciate your time and attention to this matter”
  • “I look forward to your response”

If nobody wrote it, why should anybody read it?

Textbook

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

Several copies will be on reserve at the GWU Library.

Mechanics

• One 2.5 hr meeting per week

• Exams in person

  • Periodic in-class practice

• Homework via submit server

• Programming assignments in Python

  • If you don’t know Python: you will.

• Rhythms

Introduction to the Subject

Do We Even Need to Introduce AI?

• You have undoubtedly used an LLM
  • You have almost certainly used speech-to-text
• You may have ridden in a self-driving car
• You probably unlock your telephone with your face
  • Consider how this sentence would have been received in 1995
• You trust software to give you street directions
• You have probably flown on an airliner with autopilot
• You might have lost to a computer at chess

What Is Artificial Intelligence?

What is intelligence?

• Thought
• Reasoning
• Behavior

Do we need all three?
Does “AI” need all three?

Is It Intelligent?

Images: Speed Queen, Volvo

Rationality

• Decisions
• Outcomes
• Values

It is possible to make better decisions.

Rational agents make better decisions.

Which Decision?

• Pay $17 for this pizza, delivered
• Pay $21 for the same pizza, delivered

Basically The Same Problem

Image: Bloomberg

Expected Utility

Which would you prefer?

• Receive $10
• Flip a fair coin:
  • Heads - Pay $10
  • Tails - Receive $100

• Many outcomes aren’t directly expressed in dollars
• Rational agents maximize expected utility

Defining AI, Again

• Thought “vs.” Action

• Human “vs.” Rational

• What is necessary?

  • All four combinations have been asserted

Errors

• What happens when a human¹ crashes a bicycle?
• What happens when a self-driving car² crashes?
• Who is responsible when a self-driving car crashes?

How do “we” ensure AI values align with human values?

1. Human at fault

2. Software at fault

Alignment

Image: Meme; fair use.

Alignment

• Are universal human values defined?
• How are AI values defined?
• How are AI values validated?

This is an open area of investigation.¹

1. And of concern.

How We Got Here

• Neural Networks
  • Perceptron (McCulloch & Pitts, 1943)
  • “Computing Machinery and Intelligence” (Turing, 1950)
• Logic
  • Samuel’s checkers, MANIAC Chess (1950s)
  • Dartmouth “Artificial Intelligence” conference (1956)
  • Minsky & Papert assault perceptrons (1959)

How We Got Here

• Knowledge/Expert Systems
  • Expert systems boom (1980s)
  • Back propagation paper (Rumelhart et al., 1986)
  • Expert systems bust (1990s)
• Probabilistic methods
  • TD-Gammon (1992)
  • Deep Blue defeats Kasparov (1997)

How We Got Here

• Neural Networks
  • AlexNet computer vision (2012)
  • DeepMind Atari (2013)
  • AlphaGo defeats Sedol (2016)
  • Google Translate LSTM (2016)
  • AlphaFold (2018)
• Large Language Models
  • Attention Is All You Need (2017)
  • GPT-3.5 (2022)

Where Do We Go Now?

• Game-playing
  • Real-world tasks that look like games
• Statistical generation of text, images, video…
• Open-ended logical problems
  • Unsolved problems
• Problems with poorly-defined interfaces

Societal Implications

• Translation
• Text generation
• “Art” generation
• Decision-making
  • “Who is responsible for…”

What This Course Is Not About

• Translation
• Text generation
• “Art” generation

What This Course Is About

• The design of rational agents
• General AI techniques for problem solving
  • Recognizing when a new problem has an “existing” solution
• Solving problems approximately
  • Optimal solutions often intractable

The Rational Agent

• Has a utility function
  • Maximizes expected utility
• Sensors: perceives environment
• Actuators: influences environment

What is in between sensors and actuators?

The agent function.

Reflex Agent

• Very basic form of agent function
• Percept \(\rightarrow\) Action lookup table
• Good for simple games
  • Tic-tac-toe
  • Checkers?
• Needs entire state space in table

State Space Size

• Tic-tac-toe: \(10^3\)
• Checkers: \(10^{20}\)
• Chess: \(10^{44}\)
• Go: \(10^{170}\)
• Self-driving car: ?

Partially-Observable State

Partially-Observable State

• Most real-world problems
  • Sensor error
  • Model error
• Reflex agents fail¹
• Agent needs a belief state

1. Unless total number of partial observations is bounded

Backing Up

• The Environment
  • State Space
• Rational Agents:
  • Sensors
  • Actuators
• Sensors + State Space = Belief State

Features of the problem are pre-defined; we define the agent function.

High-Level Topics

• Search & Planning
• Multi-Agent Problems
• Probability & Inference
• Learning

Search & Planning

• World model
  • “Fully known”
• How do we accomplish a goal?

Multi-Agent Problems

• Other agents with different utility functions
• Agents react to our agent
• How do we maximize our own utility?

Probability & Inference

• Partially-observed states
• Stochastic actions
• How do we maintain a belief state?
• How do we maximize our utility?

Learning

• Initially-unknown problem structure
• Explore vs. exploit
  • Actions tell us more about the problem
  • Actions have some cost
• Can also learn from data

Big Picture

• Represent problems
  • States, actions
• Implement algorithms
• Train (if needed) using data

The Pac-Man

Note that Bandai Namco Entertainment Inc. owns the trademark to “PAC-MAN” for Coin and Non-Coin Operated Electronic Amusement Apparatus for Playing a Game on a Video Output Display, as well as for Entertainment, namely providing a computer game that may be accessed network-wide by network users via mobile phones and computers; providing computer games via network between communications networks and computers. Our use is educational.

Why Pac-Man?

• Real world AI problems are hard
  • This is a one-semester course
• Algorithms themselves are reasonably simple
  • Applying them to problems is “the” problem
• Pac-man is simple
• You don’t have to like games
  • Same algorithms apply to real world

The Real World

• Observable?
• Deterministic?
• Markov?
• Static?
• Discrete?

Examples…

References

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

• Stanford CS231

• UC Berkeley CS188