COMP3308/COMP3608, Lecture 1
ARTIFICIAL INTELLIGENCE
Introduction to Artificial Intelligence
Irena Koprinska
Reference: Russell and Norvig, ch. 1 [ch. 2, ch. 26 – optional]
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021 1
Outline
• Administrative matters
• Course overview
• What is AI?
• A brief history
• The state of the art
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021 2
Welcome to AI!
• There are 445 students enrolled in this course • 403 in COMP3308 and 42 in COMP3608
• Local and international, from various degrees
• Welcome to everyone!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021 3
The world of AI
• The world of AI is exciting and fascinating, with great success stories and even greater in the future, that you can be part of. We will explore it together!
self-driving cars
Amazon Prime Air
Netflix’s movie recommender
https://www.amazon.com/Amazon-Prime-Air/ b?ie=UTF8&node=8037720011
Speech recognition
http://www.newsweek.com/microsoft-speech- recognition-achieves-human-parity-511538
http://fortune.com/2016/02/15/driverless-cars-google-lyft/
home robots
Amazon Alexa personal assistant
https://www.quora.com/Does-Pandora-use-machine-learning https://science.howstuffworks.com/study-elderly-robotic-help.htm
Cancer detection
http://pages.cs.wisc.edu/~olvi/ uwmp/cancer.html
car plate readers
http://en.wikipedia.org/wiki/
http://www.eutimes.net/2014/11/ new-artificial-intelligence
Automatic_number_plate_recognition -software-capable-of-near-human- level-image-recognition/
http://people.idsia.ch/~juergen/computer-vision-contests-won-by-gpu-cnns.html
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
4
Climate prediction
https://www.nature.com/news/how- machine-learning-could-help-to- improve-climate-forecasts-1.22503
Teaching Staff
• Unit coordinator and lecturer
• Irena Koprinska
• Computer Science Building, room 450 irena.koprinska@sydney.edu.au
• Teaching assistants
• Jessica McBroom
• Givanna Putri (PASTA)
• Tutors
• Jessica McBroom
• Stephen McCloskey
• Nicholas Rhodes
• James Wood
• Cameron Eggins
• Sophia Polito
• Christopher Irving
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
5
• Lectures
Timetable
• 2 hours weekly, 10-12 on Monday
• Pre-recorded, not-live streamed (we were asked to do this – big clashes with other courses)
• Available on Canvas from “Recorded lectures”
• Watch them during the lecture time (or another time but before your
tutorial)
• Tutorial
• 1 hour weekly on Tuesday or Wednesday, start in week 2
• Live-streamed via Zoom
• Please attend your allocated tutorial
• 1 tutorial will be recorded and available on Canvas in ‘Recorded lectures”
• COMP3308 and COMP3608: shared lectures, different tutorials, common and different assessment
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
6
Course Website
• The main place for this course is the Canvas website; we will use it for:
• all teaching materials (unit outline, lecture slides, tutorial notes, tutorial solutions, assignments)
• homework submissions
• posting marks
• All other relevant systems will be linked to the Canvas website:
• discussion board (Piazza)
• assignment submission system (PASTA)
• AI-unit-outline2020-detailed.pdf on Canvas – contains the most important information about this course
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
7
Course Materials
• Lecture slides, tutorial notes (with marked exercises for homework) will be available in advance on Saturday morning
• The lecture slides initially will not include the answers to questions and exercises that we will do at the lectures; the complete version with the answers will be uploaded after the lecture
• Tutorial solutions will be available on Wednesday evening (after the last tutorial
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
8
Discussion Board
• We will use Piazza, it is linked to Canvas
• Activate your Piazza account – I sent you an invitation email on
Wednesday
• If you have joined later, you can enroll yourself – Canvas->Piazza
• You must have access to Piazza – it will be the main communication channel + it is a wonderful resource
• When you click on Piazza in Canvas, you should be able to see the posts for this course, otherwise you are not enrolled in Piazza
• Posting questions on Piazza
• Post your question on Piazza instead of emailing them to us – this is
beneficial for everyone
• The question will be answered quicker
• When it is answered, it is answered for everybody (and often many students have the same question)
• If you are shy, you can ask your question anonymously!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
9
Automatic Marking System PASTA
• We will use PASTA for Assignment 1 and Assignment 2
• It will be linked to Canvas in due time
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
10
Lecture Recordings
• The lectures will be recorded and available on Canvas
• However, you may not need the recordings
• My lecture slides are very detailed, with many examples
• I put everything important on the slides, including updating the slides after the lecture to add the solutions/answers
• My slides are self-content and intended to help you revise and catch-up quickly
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
11
Assessment Overview
1. Weekly homeworks – 4% (individual)
• Every week (except weeks 1 and 13) you need to prepare and submit a homework via Canvas by Tuesday 4pm
• Why not in weeks 1 and 13? Week 1 – no tutorial, week 13 – last week of semester, relax☺
• Why Tuesday 4pm? The first tutorial starts at that time and we discuss the homework solutions at the tutorials
• The homeworks are due in the current week, i.e. the homework for week 2 is due in week 2, the homework for week 3 is due in week 3, etc.
• The homework exercises (typically 1 exercise) are easy and require direct application of the material covered at the lectures. Their aim is to prepare you for the tutorial and encourage you to study steadily during the semester.
• Marking – 4 homeworks only (randomly chosen, the same for all students) will be marked for 1 marks each; marks available in week 13
• Do your homework every week and do not lose easy marks! Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
12
Assessment Overview (2)
2. Two assignments
• Assignment 1 (12%) – out Friday week 3, due Friday week 6; individual
• Assignment 2 (24%) – out Monday week 7, due Friday week 10; individual or in pairs (no more than 2 people are allowed)
• Assignments are due at 11.59pm, submission is via PASTA (+ Canvas for Assignment 2)
• Given a problem, you need to apply one or more AI algorithms to solve it. You need to submit:
• •
For both assignments: a computer program (in Java, C, C++, Matlab or Python) – automarked in PASTA
For Assignment 2: also a report analysing the results – manually marked
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
13
Assessment Overview (3)
• Important: Start working on the assignments as soon as possible, do not delay them till a few days before the deadline!
• They are complex assignments
• Remember that all programming assignments, even the ones that look simple, almost always require much more time than expected – times more!
3. Exam: 60% (individual), during the examination period
• Take-home, 2 hours
• A minimum of 24 marks on the exam (40%) is required to pass the course
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
14
Late Submissions
• Homeworks: no late submissions are allowed
• Assignments:
• Late submissions are allowed up to 3 days late
• A penalty of 5% per day will apply
• Assignments more than 3 days late will not be accepted
• The day cut-off is 11:59
• Exception: No late submissions are allowed for 1 of the components of Assignment 1 for COMP3608
• The submission boxes close exactly at the deadline time
• Submit early to avoid last minute problems and busy systems
• For the assignments you can submit multiple times (unlimited) before the deadline
• For the homeworks – usually multiple submissions are
allowed, sometimes 1 – read the instructions
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
15
Pre-requisites and Assumed Knowledge
• Pre-requisites: None
• Assumed knowledge: • Algorithms
• Programming skills (e.g. Java, Python, C, C++, Matlab) • Warning:
• Do not attempt this course without good programming skills as the assignments are difficult
• Do not attempt this course out of sequence, e.g. in your first year at Uni. It is a third year (senior) course.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
16
Textbooks and Recommended Books
• Textbook
• Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson, 4th edition, 2020 (previous edition is OK)
• Recommended book
• Ian Witten, Eibe Frank, Mark Hall and Christopher Pal, Data Mining – Practical Machine Learning Tools and Techniques, Morgan Kaufmann, 2017 (previous edition is OK)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
17
Special Considerations (SC) due to Illness or Misadventure
• There is a centralized Uni system: http://sydney.edu.au/special-consideration
• Applications are submitted online, after login to “myUni”
• You are required to submit the SC form within 3 working days
from the date when the assessment was due
• Applications are assessed by the University Student Administration Services (SAS) unit
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
18
Information from the Disability Services Office
Do you have a disability that impacts on your studies?
• You may not think of yourself as having a ‘disability’ but the definition under the Disability Discrimination Act (1992) is broad and includes temporary or chronic medical conditions, physical or sensory disabilities, psychological conditions and learning disabilities
• The types of disabilities we see include:/
• Autism, ADHD, Bipolar disorder, Broken bones, Cancer, Cerebral palsy, Chronic fatigue syndrome, Crohn’s disease, Cystic fibrosis, Depression Diabetes, Dyslexia, Epilepsy, Hearing impairment, Learning disability, Mobility impairment, Multiple sclerosis and much more.
• In order to get assistance, students need to register with Disability Services. It is advisable to do this as early as possible. Please contact us or review our website to find out more.
• Disability Services Office, sydney.edu.au/disability, 02-8627-8422 Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
19
•
•
• •
Cheating and Plagiarism
Please read the Uni policy on Academic Honesty carefully: https://sydney.edu.au/students/academic-integrity.html
All cases of academic dishonesty and plagiarism will be investigated
There is a centralized Uni system and database Three types of offenses:
• Plagiarism – when you copy from another student, website or other source. This includes copying the whole assignment/exam or only a part of it.
• Academic dishonesty – when you make your work available to another student to copy (the whole assignment/exam or a part of it). There are other examples of academic dishonesty.
• Misconduct – when you engage another person to complete your assignment/exam (or a part of it), for payment or not. This is a very serious matter and the Policy requires that your case is forwarded to the University Registrar for investigation.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
20
Penalties
• The penalties are severe and include:
1) a permanent record of academic dishonesty, plagiarism and misconduct
in the University database and on your student file
2) mark deduction, ranging from 0 for the assignment to Fail for the course
3) expulsion from the University and cancelling of your student visa
• Do not confuse legitimate co-operation and cheating! You can discuss the assignment with another student, this is a legitimate collaboration, but you cannot complete the assignment together – everyone must write their own code or report, unless the assignment is group work.
• When there is copying between students, note that both students are penalised – the student who copies and the student who makes his/her work available for copying
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
21
Plagiarism Detection
• We will use the similarity detection software TurnItIn and MOSS to compare your assignments with these of other students (current and previous) and the Internet
• Turnitin is for text documents: http://www.turnitin.com/en_us/higher-education
• MOSS is for programming code: https://theory.stanford.edu/~aiken/moss/
• These tools are extremely good!
• e.g. MOSS cannot be fooled by changing the names of the variables or
changing the order of the conditions in if-else statements
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
22
Student Excuses
• These are cases of plagiarism and academic dishonesty from our school
• The student excuses are not acceptable and both parties were penalized
• I sat the test and then posted the questions and solutions to my friends whose test was later in the week. I only wanted to help them understand the concepts that are examinable.
• I posted parts of my code on my web page (group discussion forum) because my solution was cool (or I wanted to help them). I didn’t expect them to copy it.
• I tried to do the assignment on my own but I had problems with the extension part that I couldn’t fix, so I submitted my core part and his extension part. I didn’t cheat.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
23
Student Excuses (2)
• I finished my assignment but my friend had family problems. I felt sorry for her, so I gave her my assignment as an example. She said she only wanted to have a look and promised not to copy it.
• The test has finished but the tutor hasn’t collected the papers yet. I showed my answer to my friend. I didn’t expect him to copy it.
• He is my best friend. I had no choice but to let him copy my assignment.
• I couldn’t find a partner to work in pairs, so I joined their pair as they are my friends (when only groups of 2 are allowed – illegitimate collaboration – academic dishonesty).
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
24
Cheating and Plagiarism – Key Message
• Plagiarism and any form of academic dishonesty will be dealt with, and the penalties are severe
• We use plagiarism detection systems such as MOSS and TurnItIn that are extremely good. If you cheat, the chances you will be caught are very high.
• If someone asks you to see or copy your assignment, or to complete the assignment instead of them, just say: I can’t do this. This is against the University policy. I will not risk my reputation and future by doing this.
Be smart and don’t risk your future by engaging in plagiarism and academic dishonesty!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
25
Course Overview
• Introduction
• Problem solving and search
• Game playing ——————–
• Machine learning
• Neural networks (yes, deep learning too)
• Probabilistic reasoning and inference
• Unsupervised learning
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
26
Problem Solving and Search – Example
• Route (path) finding problem
• On holiday in Italy, currently in Venice
• The semester has started, you must return to Sydney!
• Flight leaves tomorrow from Rome
• What is the shortest route from Venice to Rome? (cheapest, most pleasant, etc.)
• How can this problem be represented in terms of states, operators and cost function? What search algorithms can be used to find a solution?
• Are these algorithms guaranteed to find a solution if it exists? Is it the optimal one? How long does it take to find a solution? What are the memory requirements?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
27
Problem Solving and Search – Application
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
28
Game Playing – Example
• How do computers play games?
• In a completely different way than humans – by searching a tree
• => playing games is a search problem (adversarial search)
• What is the best move?
• Typically not possible to calculate it – too complex, no time to calculate the exact consequences of each move
• Chess:
• branching factor of about 35
• one game consists of ~50 moves by each player
• search space consists of 35100 nodes
• We have to make our best guess based on past experience and resources (time and computing power)
• Techniques for choosing a good move when time is limited Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
29
Machine Learning – Classification Example
• Medical diagnosis
• •
• •
Predicting probability of emergency C-section based on past data (supervised learning)
Data: 9714 patient records, each describing a pregnancy and birth; each patient record contains 215 attributes and is pre-classified as “C-section” and “not C-section”
Task: Use these pre-classified historic data to learn to predict if a new patient is at high risk for emergency C-section
Solution: a classifier (e.g. set of rules) learned from the past data: if previousc-section&
abnormal 2d-trimester ultrasound &
malpresentation at admission
then probability of emergency c-section is 0.6 Example from T. Mitchell, Machine Learning, McGraw Hill, 1997
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
30
Yes
Machine Learning – Clustering Example
• Clustering is an example of unsupervised learning
• Data: 39 indicators describing various quality of life factors, e.g. state of
health, nutrition, education, etc.
• Task: Group these countries together based on their similarity
• World poverty map
http://www.cis.hut.fi/research/som-research/worldmap.html
• Clustering using SOM (a neural network-based approach) – not only groups data but also provides useful visualisation
• SOM will not be covered but we will study other classical clustering algorithms
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
31
Probabilistic Reasoning Example
• Build graphical probabilistic models such as Bayesian networks based on historical data and use them for reasoning and predictions for new data
• What will be the prediction play=yes or play=no for the new day:
outlook=rainy, temperature=cool, humidity=high, windy=true ?
Example from Data Mining, Witten, Frank and Hall, Morgan Kaufmann 2011
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
32
Ready to Start Learning AI?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
33
human-centered approach
What is AI?
•
rationality-centered
There are 4 views – systems with AI should:
approach
thinking →acting
think like humans
think rationally
act like humans
act rationally
Which view do you like?
•
•
•
like humans→rationality
Rationality = ideal performance given a performance measure
e.g. acting rationally = selecting the best action at each step, the one that maximizes the given performance measure
Historically all 4 approaches have been followed by different people
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
34
AI is…
1. “The exciting new effort to make computers think…machines with minds,
in the full and literal sense.” (Haugeland, 1985)
2. “The study of how to make computers do things at which, at the moment,
people are better” (Rich & Knight, 1991)
3. “The study of mental faculties through the use of computational models”
(Charniak & McDermott, 1985)
4. “The branch of computer science that is concerned with the automation of
think rationally
intelligent behavior” (Luger & Stubblefield, 1993) act rationally
5. “Computational Intelligence is the study of the design of intelligent
agents.” (Poole et al., 1998)
act rationally
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
35
think like humans act like humans
Acting Humanly – the Turing Test Approach
• Proposed by Alan Turing in 1950 in his paper “Computing Machinery and Intelligence”
• Can machines think? If so, how could we tell?
• “Thinking” is difficult to define, let’s replace this
question with a test of behavior
• A machine (computer) is intelligent if it passes the test
• Inspired by a party game called “Imitation game”
Image from http://en.wikipedia.org/ wiki/Alan_Turing
• A human asks written questions and receives back written responses
• A computer passes the test if the human cannot tell if the responses come from a human or computer
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
36
ALICE chat bot demo
• Developed by Richard Wallace
Irena: Hi, my name is Irena.
ALICE: That’s a very nice name, Irena.
Irena: Are you interested in Artificial Intelligence?
ALICE: Sure, Artificial Intelligence sounds like a good topic.
Human: Do you know who Alan Turing is?
ALICE: A brilliant and tragic figure in the history of computer science.
Irena: Why?
ALICE: The explanation is rather complicated.
Irena: Have you ever been to Australia?
ALICE: Not to my knowledge.
Irena: What do you like?
ALICE: I like movies about robots.
Irena: Which is your favourite movie?
ALICE: My favourite movie is Casablanca. Have you seen it?
Irena: No.
ALICE: I would recommend you check it out.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
37
ALICE chat bot demo (2)
Irena: Why do you like it?
ALICE: I have a lot of good experience with it.
Irena: I see.
ALICE: I’m glad you understand it.
Irena: Thanks for talking with me.
ALICE: Don’t mention it.
Irena: Ciao!
ALICE: Does CIAO mean hello or goodbye?
Irena: Both.
ALICE: What are both like?
Irena: Bye! It was nice talking to you.
ALICE: Goodbye. Thanks. It was nice chatting with you as well.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
38
Turing Test (3)
• What capabilities does the computer need for the Turing test?
• Natural language processing – to communicate successfully in
(written) English
• Knowledge representation – to store what it knows and hears
• Automated reasoning – to use the stored information to answer questions and draw conclusions
• Machine learning – to adapt to new situations, to detect patterns and apply them to new situations
• Suggested 4 major components of AI: natural language processing, knowledge representation, automated reasoning, learning
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
39
Total Turing Test
• The interrogator can test the subject’s perceptual abilities by showing video and passing physical objects “through the hatch”
• The computer needs:
• Computer vision to perceive objects
• Robotics to move them around
• The 6 disciplines compose most of AI
• Turing deserves credit for designing a test that remains relevant
70 years later
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
40
Loebner Prize Competition
• Started in 1991, https://en.wikipedia.org/wiki/Loebner_Prize
• $100K prize for the first program that can pass the total Turing
test – not awarded yet
• $25K for the first program that can pass the restricted Turing test – not awarded yet
• $2-3K each year for the best program on a restricted Turing test • ALICE won this prize 3 times
• Mitsuku is the last winner (2019) and has won 4 times
• 2020 – not sure if the competition went ahead
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
41
Passing the Turing Test
• Within AI there is little effort to pass the Turing test
• Reasons: to test if a machine resembles a human being (or to
simulate intelligence) is not very useful
• Instead, it is more important to understand the principles of intelligent behavior, and using them to build intelligent systems
• Analogy with the discovery of airplanes: When did the Wright brothers succeeded in building an airplane?
A. When they tried to imitate how birds fly
B. When they learned some basic aerodynamics principles
• The goal of aeronautical engineering is not to make flying machines that fly exactly like pigeons and can fool other pigeons ☺
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
42
Acting Humanly – ELIZA
• Joseph Weizenbaum, Communications of the ACM, 1966
• One of the first chatbots; programmed to behave like a psychiatrist
• Can communicate in natural language on any topic
• Named after Eliza Doolittle from G.B. Shaw’s play Pygmalion (musical: My Fair Lady)
• Transcript (from http://jerz.setonhill.edu/if/canon/eliza.htm):
ELIZA: How do you do. Please state your problem. Visitor: I spend too much time with computers. ELIZA: Why do you mention computers?
Visitor: You are one.
ELIZA: Does it please you to believe I am one? Visitor: Yes.
ELIZA: You seem to be quite positive.
Visitor: I suppose I am.
ELIZA: How long have you been?
• How does it work?
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
43
ELIZA – Another Transcript
• Transcript (from Alan Blair, UNSW, COMP9414/9814/3411):
Visitor: The trouble is, my mother’s ill. ELIZA: How long has she been ill?
…
Visitor: The trouble is, my mother’s Irish. ELIZA: How long has she been Irish?
…
Visitor: The trouble is, my mother’s poodle. ELIZA: How long has she been poodle?
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
44
Turing Test and Eliza Video
• http://www.youtube.com/watch?v=tXMaFhO6dIY
• The Machine that Changed the World: The Thinking Machine (4/5)
• Segment: minute 15 – 18
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
45
ALICE and ELIZA Talking
Jerry Zhu, pages.cs.wisc.edu/~jerryzhu/cs540/handouts/intro.pdf
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
46
Reverse Turing Test – CAPTCHA
• “CAPTCHA” stands for “Completely Automated Public Turing test to tell Computers and Humans Apart“
• Coined in 2000 by Luis von Ahn and Manuel Blum from CMU
• Used when creating email accounts, booking airline tickets,
adding links in Wikipedia etc. to protect from spam bots
http://en.wikipedia.org/wiki/Captcha
Jerry Zhu, pages.cs.wisc.edu/~jerryzhu/cs540/handouts/intro.pdf
• Why is it called “reverse” Turing test?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
47
Thinking Humanly: the Cognitive Modeling
Approach
• How do humans think? Once we know this (i.e. have a theory) we can write a computer program that thinks like human
• Given a problem, it is not enough that it is solved correctly by the computer; the same reasoning steps as in humans should be followed
• General Problem Solver (GPS), Newell and Simon, 1957
• a program for proving theorems and solving geometric problems
• imitates human reasoning; order in which it considers goals and sub- goals is similar to humans
• => the first program to embody the “thinking humanly” approach • http://shelf1.library.cmu.edu/IMLS/MindModels/humanandmachine.html
• Cognitive science: constructs and tests theories of how the human mind works using methods from psychology and computer models
• Cognitive Science and AI are separate fields
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
48
•
Thinking Rationally: the “Laws of Thought”
Approach
Goal: use logic to build intelligent systems
• Take a description of a problem in logical notation
• Find the solution (if one exists) using correct inference
• Example:
Socrates is a man. All man are mortal. => Socrates is mortal.
…
• Take informal knowledge and represent it in formal notation is
• Problems difficult
• This is especially difficult when knowledge is uncertain, i.e. less than 100% certain
• Limited time and memory – which reasoning step to apply first?
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
49
Acting Rationally: the Rational Agent Approach (the view we take)
• AI is a part of Computer Science which is concerned with the design
of intelligent agent programs • An intelligent agent
• Has in-built knowledge and goals
• Perceives the environment
To learn more about intelligent agent, see ch.2!
• It acts rationally to achieve its goals by using its knowledge and the percept sequence from the environment
• Acting rationally = does the right thing: the action that maximizes a performance measure
• In complex environments:
• •
Always doing the right thing is not possible – computational demands (time, memory) are too high
Limited rationality – acting appropriately when there is no enough time to make all computations for a perfect solution
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
50
theories of reasoning, learning, and rationality, logic
Foundations of AI
algorithm, formal representation and proof, computation, (un)decidability, (in)tractability, probability
Philosophy 428 B.C.
Mathematics 800
Psychology 1879
adaptation, phenomena of perception and motor control, experimental techniques to investigate human mind
Artificial Intelligence 1956
Computer Engineering 1940
machines to make AI reality
Linguistics 1957
structure and meaning of language; grammar, knowledge representation
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
51
History of AI
• Book about the history of AI:
Machines Who Think, Pamela McCorduck , 2004
http://www.pamelamc.com/html/machines_who_think.html
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
52
Gestation (1943-1955)
• 1943: McCulloch and Pitts’s model of
artificial neuron – the first work recognized
as AI p1
• Neuron is “on” and “off”; “on” when there
is sufficient stimulation from neighbouring p2 neurons; “off”, otherwise
• Mathematically: weighted sum of input pn signals is compared to a threshold to
determine the output; sum threshold => output is 1; else – 0
neuron i
Output: 0 or 1
inputs
w
w 1i ai
S f a =f(wp)
2i
…
w
ni
• Showed that a network of connected neurons can compute any arithmetic function and that all logical connections (AND, OR, NOT) can be implemented by simple networks of connected neurons
• The parameters of the network had to be designed, but it was suggested that they can be learned from a set of examples [input-correct output]!
• The link between biology & computers generated a lot of interest! Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021 53
i
Gestation (1943-1955)
• 1950 Hebb poroposed a rule for modifying the connection strength between neurons – Hebbian learning; still used in neural networks
• 1950: Turing’s article “Computing Machinery and Intelligence” stated a vision for AI (Turing test, machine learning, genetic algorithms and reinforcement learning)
• 1951: Minsky and Edmonds built the first neural network computer (Snarc) – a neural network of 40 neurons using 3000 vacuum tubes
Marvin Minsky
Photo from http://en.wikipedia.org/wiki/Marvin_Minsky
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
54
Birth (1956)
• 1956: John McCarthy’s workshop – “AI” adopted; the birth of AI
• Organized a 2-month workshop at Dartmouth College for researchers
interested in automata theory, neural nets and the study of intelligence
• 10 participants; no breakthroughs but the main AI people were introduced to each other
John McCarthy
Photo from http://www- formal.stanford.edu/jmc/personal.html
• Herbert Simon and Allen Newell presented the Logic Theorist, a computer program for proving theorems
• Provedmostofthetheoremsinch.2PrincipiaMathematica,andsome proofs were even shorter then in the book!
• IntroducedconceptsthatarecentralforAI:reasoningassearchina tree + use of heuristics to trim unpromising branches
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
55
• •
Early Enthusiasm (50-60s)
1960 Perceptrons & linear neural networks (Rosenblatt, Widrow & Hoff) – learning rule to train neural networks to solve pattern recognition problems
Early neural nets: http://www.youtube.com/watch?v=tXMaFhO6dIY The machine that changed the world, minute 39-41
• The perceptron was expected to be “able to walk, talk, see, write, reproduce itself and be conscious of its existence.” It didn’t happen…☺
1957 – General Problem Solver (Newell and Simon) – proves theorems, solves geometric problems and plays chess by imitates human problem solving (“Thinking Humanly” approach to AI)
1959 -1975 – Programs for playing checkers (Samuel)
• invented alpha-beta pruning for pruning unnecessary branches of the
game tree
• disproved the idea that computers can do only what they are told to – the
programs were able to learn from experience
Image from http://en.wikipedia.org/wiki/Draughts#Computer_draughts
•
•
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
56
Early Enthusiasm (50-60s) – 2
• 1958 – Lisp programming language (McCarthy)
• Lisp is the 2nd oldest language still in use!
• Which is the oldest language still in use?
• 1965 – resolution theory (Robinson) – theorem proving for 1st order logic; basis for Prolog
• 1967-1968 – programs for solving microworld problems – STUDEN (Bobrow) – algebra; ANALOGY – geometry
•
STUDEN program, Bobrow 1967 – algebra problems:
If the number of customers Tom gets is twice the square of 20 percent of the number of advertisements he runs, and the number of advertisements he runs is 45, what is the number of customers Tom gets?
ANALOGY program, Evans 1968 – solves geometric analogy problems
•
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
57
High Expectations
• Great progress in AI in 50-60s – from calculators to machines that can play games, solve mathematical problems and prove theorems
• This generated high expectations, e.g. Herbert Simon in 1957:
“It is not my aim to surprise or shock you – but the simplest way I can summarize is to say that there are now in the world machines that think, that learn and that create. Moreover, their ability to do these things is going to increase rapidly until – in a visible future – the range of problems they can handle will be coextensive with the range to which the human mind has been applied”.
“In 10 years a computer would be a chess champion and a significant mathematical theorem would be proven”
• When did the chess prediction come true?
• However, the early AI systems failed when they were tried on a wider
selections of problems and on more difficult problems
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
58
A Dose of Reality (60-70s)
• Problem 1: Limitations of algorithms
• 1960 – Minsky and Papert, book “Perceptrons” – demonstrated limitations of existing neural networks – need for more complex neural networks and a new learning rule
• Rosenblatt and Widrow were aware of these limitations and proposed new neural networks that would overcome them. But they were not able to modify their learning algorithm to train the more complex nets.
• Problem 2: Need for deeper knowledge, syntactic manipulation not sufficient
• Translation Russian-> English using grammatical rules + word replacement from dictionary
• English: “The spirit is willing but the flesh is weak”-> translated in Russian as “The vodka is good but the meat is rotten”
• One word has many meanings; the correct one depends on the context – knowledge about the topic is needed!
• http://en.wikipedia.org/wiki/Georgetown-IBM_experiment Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
59
A Dose of Reality (60-70s) cont.
• Problem 3: Many real problems are intractable
• Early AI programs solved problems by using different combination of steps until the solution is found; worked well for simple domains (small number of objects and possible actions)
• Generalization to larger problems proved difficult (and not only a matter of faster hardware and bigger memory)
• Need to deal with combinatorial explosion + computing power not sufficient
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
60
The Come Back (from 70s)
• Knowledge-based systems to solve specific problems in restricted domains
• Expert systems industry boom – millions of $$$
• Provide expert quality advice, diagnoses and recommendation
for real-world problems; rule-based
Should be able to provide explanation, e.g. WHY explanation
ES: I recommend that you should invest in IBM stock
Client: Why not in GE stock? (Why did you reject this solution?) ES: Because using R75, the annual growth rate of GE is only 7%
whereas that of IBM is 11%
61
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
The Come Back (from 70s) – 2
• 80s – Neural networks return to popularity Rumelhart and McClelland – backpropagation algorithm for training multilayer perceptrons – answer to the criticism of Minsky and Papert
• ALVINN (1993) and NetTalk (1987) NNs: minute 41-46 http://www.youtube.com/watch?v=tXMaFhO6dIY
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
62
Today – Machine Learning is Reinventing Computing?
• The Great AI Awakening (New York Times, 2016) https://www.nytimes.com/2016/12/14/magazine/the-great-ai-awakening.html?_r=0
• Machine learning and data mining are the fastest growing areas of AI
• Big Data, Deep Learning
• But be careful: Big Data may be Big Garbage!
• Deep learning has been around since 1993 Convolutional network demo – Yan LeCun, 1993 https://www.youtube.com/watch?v=FwFduRA_L6Q
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
63
•
The Rise of Machine Learning
A lot of data is being collected, e.g.
• trillions of words in English, billions of images on web, billions of base pairs of genomic sequences
• weather data, supermarket transactions, bank/credit card usage, government statistics, genomic databases, medical records, social networking data
• user data – browsing, reading, movies watched, products bought This data can be used to
• extract useful patterns used for different types of analytics
• train machines to learn to perform different tasks, e.g. translate
from one language to another or drive a car
•
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
64
AI – State of the Art
• Which of the following can be done at present?
• Play a descent game of table tennis
• Beat the world chess champion
• Drive in the centre of Cairo
• Drive along a curving mountain road
• Discover and prove a new mathematical theorem
• Write an intentionally funny story
• Give competent legal advice in a specialized area of law
• Translate spoken English into spoken Mandarin in real time
• Perform a complex surgical operation
Read Russell and Norvig, ch. 1.4!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
65
AI today
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
66
Playing Games
http://theconversation.com/googles-go-triumph-is-a-milestone-for-artificial-intelligence-research-53762
• Games are fascinating to people!
• test our “intelligence”; have simple rules and the goal is to win
• They are the “mice labs” for AI
• highly specialized tasks but a lot of cutting-edge AI
concepts and ideas came out of them
• Results: superhuman players in chess, checkers, scrabble, backgammon, simple poker and Go
Checkers: http://science.sciencemag.org/content/317/5836/308.1.full
Chess: http://blogs.gartner.com/andrew_white/2014/03/12/the-chess-master-and-
the-machine-the-truth-behind-kasparov-versus-deep-blue/
Scrabble: http://aitopics.org/topic/scrabble
Backgammon: http://aitopics.org/topic/backgammon
Poker: http://www.sciencemag.org/news/2015/01/texas-hold-em-poker-solved- computer
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
67
Playing Chess
Man versus Machine
What about: Man+Machine vs Machine Man+Machine vs Man+Machine?
http://hplusmagazine.com/wp-content/uploads/garry-kasparov-deep-blue-ibm.jpg
• 1997: Deep Blue (IBM) defeated the world champion Gary
Kasparov
• 6 games: 2:1 for Deep Blue + 3 draws
• AI method: search (alpha-beta + iterative deepening, etc.)
• https://www.research.ibm.com/deepblue/
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
68
AI today – Playing Go
• Board 19 x 19 = > the branching factor is too big ( b>300) for existing search techniques => computers don’t perform well
• Humans are too good – human champions refuse to compete against computers as they are too bad!
• Best existing program: Gomate – can be easily beaten by humans Not true any more!
Image from Linh Nguyen/Flickr, CC BY-NC-ND
Irena Koprinska, irena.koprinska@sydney.edu.au
• Ancient Chinese game, played by 40 million people
• Simple rules, big complexity – big search tree
• 2 players; 19×19 board; black and white stones
• Goal: capture the opponent’s stones or surround empty space to make points of territory
COMP3308/3608 AI, week 1, 2021 69
AlphaGo vs Lee Sedol
• 2016: AlphaGo won against Lee Sedol (4:1 games)
• https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
• Lee Sedol is a South Korean professional Go player, ranked 2nd in the world
• AlphaGo is a system developed by Google
• Uses a classifier – a convolutional neural network (deep learning
neural network) to predict the next move to play
• The neural network is trained using data from previous games played by human experts (30 million moves)
• It is not the effort of 1 person + 1 computer but a team of Google’s engineers + a lot of computing power (Google’s server farms)
AI has beaten us at Go. So what next for humanity? The Conversation, 2016
To Beat Go Champion, Google’s Program Needed a Human Army (New York Times,
2016)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021 70
Maps and navigation
• We don’t call this technology AI but it uses AI methods
• Plan the best route
• Evaluate the traffic
• Realign itself when we take the wrong path
• And it is better and faster than humans in doing this!
Irena Koprinska, irena.koprinska@sydney.edu.au
COMP3308/3608 AI, week 1, 2021
71
•
1)
Google Translate
Remarkable progress since 2016! Try it
• uses deep learning – trained using big corpora of texts translated by people
Written text English -> Written text Italian
2) Person A: Speech English -> translate ->Written text Italian for B Person B: Speech Italian ->translate -> Written text English for A
3) Translate text in images
• words recognition and extraction from images/video, translation and replacing the words with the translation
La Bamba video
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
72
Question Answering – Watson
• A computer program developed by IBM’s DeepQA project https://www.research.ibm.com/deepqa/deepqa.shtml http://www-03.ibm.com/innovation/us/watson/
• Answers questions posed in natural language on a wide range of topics
• Won the TV quiz show Jeopardy! in 2011
• The answer is given, the contestants need to come with the question
Clue: Nicholas II was the last ruling czar of this royal family Answer: Who are the Romanovs? https://www.jeopardy.com/be-on-j/practice-tests
• http://www.youtube.com/watch?v=tAzeGkuQmUU The smartest machine on earth, minute 47-49
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
73
Question Answering – Watson (2)
• DeepQA architecture
• Building Watson – A Brief Overview of the DeepQA Project
• paper in AI Magazine:
www.aaai.org/ojs/index.php/aimagazine/article/view/2303/2165
• video: https://www.youtube.com/watch?v=3G2H3DZ8rNc
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
74
Driving a Motor Vehicle
Google driverless car – Sebastian Trun
https://www.ted.com/talks/sebastian_thrun_google_s_driverless_ car
Waymo (Google’s company)
• Google has been testing driverless cars longer
• Its cars collect data whenever they go and it is shared with the
other Google’s cars to learn from it
• Other big players: Tesla, Daimler (Mercedes-Benz), Volvo, Uber, Toyota, Ford, nuTonomy
• The research is increasingly moving from universities to companies
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
75
Recommender Systems
• Recommending books – Amazon.com
• Customers who bought this book also bought:
• Method: collaborative filtering (unsupervised machine learning)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
76
Recommending Movies – Movielens
• User U rates some movies: actual
ratings
• AI method: collaborative
filtering
• The system uses U’s ratings, together with the ratings of other users, to give
recommendations to U:
predicted ratings
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
77
Reciprocal recommender systems
Maching People in Online Dating
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
78
• •
http://ida.first.fraunhofer.de/bbci/index_en.html
Brain-Computer Interfaces (BCI)
BCI is a system which allows a person to control a computer application (e.g. a cursor or robotic arm) by only using his/her thoughts
This is not mind reading or simulating human thinking!
Goal: to give paralyzed people another way to communicate, a way which doesn’t depend on muscle control but on their thoughts
•
• Rational
• There are patterns of EEG activity associated with mental states, e.g. imagining a movement of the right hand is associated with an EEG pattern in the left side of the brain (change in the Mu rhythm)
• A small number of mental tasks can be chosen so that they activate different parts of the brain and are easy to detect
• Example – BCI for writing
• AI task: classification (machine learning sub-task)
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
79
Future Trends
Based on AI and Life in 2030, https://ai100.stanford.edu/sites/default/files/ai_100_report_0831fnl.pdf
• Transportation
• Smarter cars (more sensors) and self-driving cars
• Remotely-controlled delivery vehicles – Amazon Prime Air drone
• More on-demand transportation (e.g. Uber) with AI algorithms matching drivers to passengers by location and reputation
• Home robots (highly specialized)
• To clean offices and deliver packages
• To interact with people at home – advances in image and speech processing
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
80
Future Trends (2)
• Healthcare – AI systems for:
• Clinical decision support
• Healthcare analytics for personalized diagnosis and treatment –mining data from “patients like mine”
• Predicting patients at risk of developing a disease or complications
• Patient monitoring and education
• Automated devices to assist in surgery (minimally invasive)
and patient care
• Mobile healthcare – healthcare apps offering information, behavior changes, collecting data (steps, diet, activities, etc.) and using data mining to make predictions
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
81
Future Trends (3)
• Elder care
• Better hearing and visual aids (personalized), intelligent
walkers and wheelchairs
• In-home monitoring
• Mobile applications monitoring movement and activities, and making recommendations about physical and mental health
• Education – good human teachers will always be needed but AI can enhance education by
• Providing personalization
• Auto grading assignments – short answer and programming
• Providing automatic feedback to students
• Predicting students at risk of failing
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
82
Future Trends (4)
• Public safety and security
• Detecting white collar crime, e.g. credit card fraud
• Detecting spam
• Crime preventions
• Crime prediction
• Detecting suspicious activities using social data – young adults at risk of being radicalized by violent groups
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
83
Implication of AI on Workforce
• Erik Brynjolfsson and Tom Mitchell on:
• What can machine learning do? What are the workforce
implications?
• Profound change is coming but roles for humans remain
http://www.cs.cmu.edu/~tom/pubs/Science_WorkforceDec2017.pdf
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
84
A. Science fiction movies
B. Supernatural and magical things
C. Algorithms
AI is about…
The world of AI is exciting and fascinating, with great success stories and even greater in the future, that you can be part of.
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
85
To do at home:
• Chat with Alice (google “Alice original chat bot”)
• Watch The Smartest Machine on Earth documentary
https://www.youtube.com/watch?v=X0JZMHhupTs
• Watch The Machine that Changed the World 4/5 documentary
http://www.youtube.com/watch?v=tXMaFhO6dIY
• Watch the Imitation Game movie
• Read AI and Life in 2030
• Read The Great AI Awakening
• Read AI implications on workforce
• Watch the Spanish Apartment movie and consider going on exchange at another Uni abroad (next year)!
Irena Koprinska, irena.koprinska@sydney.edu.au COMP3308/3608 AI, week 1, 2021
86