CS 4710 Artificial Intelligence
Chen-Yu Wei
What is (Artificial) Intelligence?
Alan Turing’s Perspective
Let’s change the question from
“Can machines think?”
to
“Can machines win the
imitation game?”
Alan Turing
(1912-1954)
Turing Test (Imitation Game)
● C (human evaluator) interacts with A (machine)
and B (human) through natural languages.
● C tries to tell which one is the machine.
● If C cannot reliably tell, then the machine wins.
Different Goals of AI
Behave like human
Neural Art Speech synthesis Chatbot
Behave rationally
AutoTrader AlphaGo Healthcare
Different Goals of AI
Disciplines studying “how human thinks”:
● Psychology
● Neuroscience
So far, AI in computer science focuses more on machine’s behaviors
than human-like thinking.
● Similar behaviors could be achieved by different mechanisms.
● Currently, we know little about our brains.
A History of AI
(also an overview of the topics to be covered in the course)
References:
[Link] Percy Liang
[Link] Henry Kautz
[Link]
AI Summers and Winters
● First Summer (1950-1966)
● First Winter (1967-1977)
● Second Summer (1978-1987)
● Second Winter (1988-2011)
● Third Summer (2012-Present)
First AI Summer (1950-1966)
● Turing Machine (1936)
● Modern computer development during WWII
● Turing Test (1950)
● The Dartmouth workshop (1956) – a two-month workshop at Dartmouth College
● Initiated by John McCarthy
● Coined down the term “Artificial Intelligence”
The Dartmouth Workshop (1956)
Proposal (the beginning):
[Link]
[Link]
First AI Summer (1950-1966)
● Logic Theorist (Newell, Simon, Shaw, 1956)
● Proves math theorems
● Proves 38 out of 52 theorems in Principia Mathematica
● The First Computer Chess (Bernstein, 1957)
● Can defeat an inexperienced player based on search algorithms
● Symbolic Automatic INTegrator (Slagle, 1961)
● Calculates (symbolic) integration
● Solves 52 out of 54 problems in MIT’s freshman final
Alex Bernstein’s Chess Machine
● [Link]
ELIZA – The First Chatbot
● [Link]
First AI Winter (1967-1977) [Link]
● ALPAC report (1966)
● AI failed in machine translation between English and Russian.
● Lighthill report (1973)
● AI research failed to address combinatorial explosion in real-world problems.
● Funding agencies (Defense Advanced Research Projects Agency, National
Research Council) cutoff fundings for AI research.
Lessons from the First Wave of AI
● Tasks that seem easy for human may be difficult for machines.
● On the other hand, tasks that seem difficult for human might actually
accomplished with simple rules.
Second AI Summer (1978-1987): Expert Systems
Advice
Query
[Link]
Represent experts’ domain knowledge in
the from of rules:
If [premises] then [conclusion]
A Toy Expert System: Animal Identification
Knowledge Base
If has_hair, then mammal.
If mammal and has_hooves, then ungulate.
If has_feathers, then bird.
If mammal and carnivore and has_dark_spots, then cheetah.
Advice If mammal and carnivore and has_black_stripes, then tiger.
If bird and does_not_fly and has_long_neck, then ostrich.
……
Query
User Interface
Animal’s attributes
Related topics:
Logic and Knowledge Representation
Second AI Summer (1978-1987): Expert Systems
● DENDRAL (1968)
● Predict molecular structure based on spectrographic data
● MYCIN (1975)
● Diagnose blood infections
● Better than junior doctor
● XCON (1978)
● Select computer system components based on customer’s need
● Save ~$25M a year
● Many companies built expert systems and software/hardware specialized for
their purpose.
Second AI Winter (1988-)
● Difficult to build and maintain expert systems for complex domains
● Uncertainty
● Could not learn from data
● Companies fell as they failed to meet their extravagant promises
Symbolic vs. Subsymbolic AI
Symbols encoded as numerical vectors,
Symbols e.g., (1, 0.2, 0.1, -0.5)
has_hair
If has_hair, then mammal.
Multiplying some weight matrices
Symbols usually directly correspond to real- Using numerical / distributed representations for
world concepts or relationships. concepts and relationships.
Symbolic AI Subsymbolic AI
Subsymbolic AI
● The “rules” (e.g., the weights in neural networks) are usually learned from
data rather than assigned by human.
● Less interpretable
● But can represent more complex rules, e.g., natural languages rules
● Better in dealing with uncertainty
● It hard / complex for human to write rules with uncertainty
● Learning from data → Statistical Learning
Statistical Learning
● Learning from data
● Methods
● Linear regression (Galton, 1894)
● Hidden Markov Model (Baum, 1960s)
Modeling uncertainty
● Bayesian Network (Pearl, 1985)
● Support Vector Machine (Cortes & Vapnik, 1995)
● SVM is a dominant approach in 2000-2010 for many tasks:
● Image classification
● Speech recognition (combined with HMM)
● Text categorization
● …
Artificial Neural Networks (NN)
● Perceptron (McCullough & Pitts, 1943)
● Inspired by biological neuron
● Can simulate logic gates
● Perceptron algorithm (Rosenblatt, 1958) Perceptron
● Learning single-layer NN
● Backpropagation (Linnainmaa, 1970; Rumelhart et al., 1986)
● Learning multi-layer NN
● Convolutional Neural Network (Fukushima, 1980; LeCun et al., 1989)
● Handwritten digit recognition for USPS
Third AI Summer (2012-Present): Deep Learning
● ImageNet (Fei-Fei Li et al., 2009)
● Large-scale image dataset: 14 million images, ~20000 classes
● Annual image recognition contest (ILSVRC) since 2010
● AlexNet (Krizhevsky, Sutskever, and Hinton, 2012)
● Won ILSVRC by >10% margin
● Revolutionize computer vision and spark the use of deep learning in many domains
● AlphaGo (Deepmind, 2016)
● Won Lee Sedol (world champion of Go) 4 out of 5 games
● Transformer (Google, 2017)
● Revolutionize natural language processing and other domains
● Generative Pre-trained Transformer (GPT)
Topics Covered in the Course
Topics
● Search
● Logic and Knowledge Representation
● Statistical Learning
● Probabilistic models (Bayesian Network, HMM)
● Linear/kernel models (SVM)
● Deep learning
● Reinforcement Learning
● Generative AI
● Safety in AI, Ethics in AI
Related UG Courses in UVA
● CS 4774 Machine Learning
● CS 4501 Special Topics – Reinforcement Learning
● CS 4501 Special Topics – Natural Language Processing
● CS 4501 Special Topics – Machine Learning in Image Analysis
● CS 4501 Special Topics – Autonomous Vehicles: Perception, Planning & Control
● David Evans’s “Risks and Benefits of Generative AI and LLMs” in Fall 2023.
Prerequisite
● Data Structure and Algorithms 2
● Calculus, Probability
● Python
Grading
● Homework: 40%
● Midterm Exam: 25%
● Final Exam: 35%
Homework (40%)
● 6 assignments
● Multiple choices questions
● Programming tasks
● Late policy
● 5 free late days distributed as desired
● Every additional late day costs 10% in the semester’s homework grade
● Collaboration policy
● May discuss the ideas, but should work on the problems/coding individually
● Acknowledge the collaborators in the homework
Exam
● Midterm and final exams
● Open notes
● No books or electronic devices
Communications
● Course website: slides, recommended reading
● Piazza: discussions
● Gradescope: homework submissions
● Office Hours
● See the course website
Online Resource
• Introduction to Artificial Intelligence at UC Berkeley
• Artificial Intelligence: Principles and Techniques at Stanford University
• Artificial Intelligence at MIT
Books (Optional)
● Artificial Intelligence: A Modern Approach, 4th Edition
● by Stuart Russell and Peter Norvig
Next Lecture
● Search