Course Overview and Introduction

CE417: Introduction to Artificial Intelligence

Sharif University of Technology
Spring 2016

Soleymani
Course Info
 Instructor: M. Soleymani
 Email: soleymani@[Link]

 Teacher Assistants:
 Seyed Mohammad Chavoshian
 Seyed Alireza Mir Mohammad Sadeghi
 Alireza Sahaf

 Lectures: Sun-Tue (15:00-16:30), Room 202

 Website: [Link]
2
Text Book
Artificial Intelligence: A Modern Approach
by Stuart Russell and Peter Norvig 3rd Edition, 2009

[Link]

3
Marking Scheme
 Mid Term Exam: 25%
 Final Exam: 35%
 Homeworks (written & programming): 20%
 Miniexams: 15%
 Quizes: 5%

4
Class Target
 Getting a feeling of Artificial Intelligence (AI), its aims,
fields, abilities, some applications and open problems

 Learning fundamentals of AI

 Learning some basic tools for AI and a little experience

with AI

5
Why AI?
 One of the newest fields in science (coined in 1956)
 However, the quest for AI begins with dreams thousands of years ago
 One of the most preferred fields
 Still has openings for several full time Einsteins
 Huge variety of subfields
 Can be useful to any intellectual task (universal field)

6
What is Artificial Intelligence?
 What is AI?
 What is intelligence?
 What are features that make humans (animals, animate
objects) intelligent?

7
Intelligence: Definitions
 The ability to carry out abstract thinking (Terman, 1921)

 The capacity for knowledge, and knowledge possessed (Henmon, 1921)

 The capacity to learn or to profit by experience (Dearborn, 1921)

 Intelligence is what is measured by intelligence tests (Boring, 1923)

 A global concept that involves an individual's ability to act purposefully, think

rationally, and deal effectively with the environment (Wechsler, 1958)

8 [Link]
Intelligence: Definitions
 A general factor that runs through all types of performance (Jensen)

 Intelligent activity consists of grasping the essentials in a given situation and

responding appropriately to them (Heim 1970)

 A person possesses intelligence insofar as he had learned, or can learn, to

adjust himself to his environment (Colvin 1982)

 Intelligence is adaptation to the environment (unknown)

 Intelligence is that faculty of mind by which order is perceived in a situation

previously considered disordered ([Link], 1999)

 Intelligence is the ability to use optimally limited resources - including time -

to achieve goals. (Kurzweil, 1999)

9 [Link]
Formal Definitions of Artificial Intelligence

Human intelligence Rational

Thinking Thinking humanly Thinking rationally

Behavior Acting humanly Acting rationally

10
Rationality
 Rationality: doing the right thing

 Mathematical characterizations of rationality have come

from diverse areas like:
 Logic
 Economics
 Utility theory: how best to act under uncertainty
 Game theory: how self-interested agents interact

11
Acting Humanly
 Turing Test (Turing, 1950): Operational test for intelligent
behavior:
 A human interrogator communicates (through a teletype) with a hidden
subject that is either a computer system or a human. If the human
interrogator cannot reliably decide whether or not the subject is a
computer, the computer is said to have passed the Turing test.
 5 minutes test, it passes by fooling the interrogator 30% of time

 Turing predicted that by 2000 a computer could pass the test.

 He was wrong.
12
Acting Humanly (Cont.)
 To pass the basic Turing test:
 Natural Language Processing (communication)
 Knowledge Representation (storing what it knows or hears)
 Automated Reasoning (using the stored info to draw new conclusions or answer
questions)
 Learning (adapting to new circumstances)

 To pass the total Turing test (in addition to above):

 Vision
 Robotics
 …

Anticipated most of AI major fields (60 years ago)

Problem: Turing test is not reproducible, constructive, or amenable to

mathematical analysis

13
Thinking humanly: cognitive modeling
 Needs some way of determining how humans thinks
 Brain imaging (observing brain in action)
 Introspection (catching our thoughts as they go)
 Psychological experiments (observing a person in action)

 Scientific theories of internal activities of the brain

 Experimental investigation of actual human or animal behavior (top-
down)
 Direct identification from neurological data (bottom-up)

 Cognitive Science and AI are now distinct sciences (while

continuing to fertilize each other)

 Precise theory of mind is not available and seems mysterious.

14
Thinking rationally: "laws of thought"
 Aristotle codified the right thinking and correct
arguments/inference processes
 “Socrates is a man, all men are mortal, therefore Socrates is
mortal”

 Direct line through mathematics and philosophy to

modern AI
 However, intelligent behaviors are not necessarily mediated by
logical deliberation

 Main obstacles:
 Not easy to convert informal knowledge to formal ones
 Reasoning usually needs high computational resource

15
Acting rationally: rational agent
 Rational agent does the right thing achieving the best outcome or
expected outcome (given what it knows)

 Thinking rationality is sometimes part of being a rational agent (it is

not all of rationality)
 Rational behavior doesn't necessarily involve thinking (e.g., blinking reflex)
 There may be no provable correct thing to do but something must be
done
 Acting rationally is more general than thinking rationally

 Compared to approaches based on human (behavior or thinking), it

can be more scientific
 Well-defined mathematically and completely general

16
Acting rationally: rational agent (cont.)
 Bounded rationality – design best agent for given resources
when not enough time available to do all computations
 Perfect rationality as a good starting point

 We’ll focus on acting rationally in this course.

17
Rational agents

 An agent is an entity that perceives and acts

 Abstractly, an agent is a function from percept histories to

actions:

[f: P*  A]

 For any given class of environments and tasks, we seek the

agent (or agents) with the best performance

18
AI definition evolution
 Agents acting rationally have been gradually more popular than
systems based on human intelligence (thinking or acting
humanly)

 Definition of AI has also been changed during the time.

 Despite successes, founders of AI including McCarthy & Minsky

have expressed discontent with the progress of AI
 AI should put less emphasis on creating ever-improved version of
applications that are good at a specific task
 AI should return to its roots “machines that think, that learn, and
create” (Human-level AI)

19
Human Level Intelligence: Samples
 Game playing: Chess, Backgammon, Othello, Poker, …
 Proving a mathematical theorem using a set of known axioms
 Planning to reach a set of goals
 Learning from previous experience to do a task better

20
Subareas of AI
 Problem solving
 Search (focus of our course)
 Planning (we talk also about it)

 Knowledge representation & reasoning (focus of our course)

 Knowledge representation & Reasoning: logical, probabilistic

 Learning

 Perception (Vision, Speech, …)

 Robotics (ability to move and manipulate objects)

 Natural Language Processing (communication)

21
Course Outline
 Intelligent agents (chapters 1-2)

 Search
 Heuristic Search (Chapter 3,4)
 Search spaces & heuristic guidance
 Game tree search (Chapter 5)
 Working against an opponent
 Backtracking Search (Chapter 6)
 Constraint Satisfaction Problems

 Reasoning and knowledge Representation (Chapter 7-9)

 Logical agents and First Order Logic for more general knowledge

 Planning (Chapter 10)

 Predicate representation of states, planning graphs, reachability heuristics

 Uncertainty (Chapter 13-14)

 Probabilistic reasoning, Bayesian networks

 Reinforcement learning
22