Artificial Intelligence Exam 1

Chapter 1 - 4

popular definition of AI

involves using methods based on the intelligent behavior of humans and other animals to solve complex problems

strong AI

* if given sufficient processing power and enough intelligence
* it can literally think and is conscious about the behavior it is performing

weak AI

* intelligent behavior can be modeled and followed by computers to solve complex problems
* just because a computer behaves intelligently, it doesn’t mean that it’s actually intelligent like a human

weak methods

* uses logic, automated, and other general structures of systems
* can be applied to wide range of problems
* does not necessarily have any real knowledge about the problem domain
* focus on inferencing

Newell and Simon’s General Problem Solver (GPS)

an attempt to use weak methods to solve a wide range of general problems

* failed but led to realization that problem solving needed more
* knowledge was key ingredient

strong methods

* depend on a system being given a great deal of domain knowledge
* focus on knowledge representation
* depend on the weak methods

weak method, strong method

Production systems use __________ expert system shells to perform inference but use _________ rules to encode their knowledge.

syllogism

a disclosure in which certain things having been
stated, something else follows of necessity from
their being so

Aristotle

The propositional and predicate logic for logical reasoning are based on the logic invented by _________________

Dialectica

* a treatise on logic
* the first real study of logic written by Peter Abelard in the 12th century

Gottfried Leibniz

* German mathematician and philosopher who thought of developing a formal mathematical language for reasoning
* allowed us to express problems to go about solving them

Boolean algebra

developed by English mathematician George Bool

* for expressing concepts such as A is true and A is true \n but B is false

Analytic Engine

* the world’s first computer invented by Charles Babbage
* his logical design was used to build working digital \n computers around 1950s

Alan Turing

* worked on the possibility of building a computer that could think
* published a paper in 1950, “Computing Machinery and Intelligence,” one of the first papers on this subject

Turing test

* an interrogator is given access to two individuals
* a human and a computer
* the interrogator can ask two individual questions but can not see them
* questions are entered into a computer via a keyboard and the responses appear on the computer screen
* the human is intended to help the interrogator
* if the computer is smart enough, it should be able to fool the interrogator
* to be uncertain about which is the computer and which is the human

John McCarthy

first to use the term “Artificial Intelligence” at a conference in Dartmouth College, New Hampshire 1956

General Problem Solver (GPS)

* invented to solve almost any logical problem
* works well on simple problems, but could not be applied in a general way

LISP

a programming language invented by McCarthy which is still widely used today in AI research

algorithm

claimed by Socrates that it could be defined to describe the behavior of humans and determine whether a person’s behavior was good or bad

dualism

* Rene Descartes was a strong believer in this
* the universe consists of two entirely separate things
* mind and matter
* the mind was entirely separate from the physical body and not constrained by it in any way

Syntactic Structures

* theory proposed by Noam Chomsky
* a formal theory of the structure of human language

cognitive psychology

based on the idea that the human brain can solve problems, make decisions, draw conclusions, and carry out other intelligent acts

electronic neurons

* made by McCulloch and Pitt
* used today to build neural networks
* based on the function of human brain neurons

a) Linguistics, b) Biology, c) Philosophy, d) Psychology

What areas of study had a great deal of influence and vital roles in the development of AI?

a) Linguistics

b) Biology

c) Philosophy

d) Psychology

e) Chemistry

PROLOG, LISP

two programming languages that have features particularly useful for AI projects

PROLOG (PROgramming in LOGic)

* designed to enable programmers to build databases of facts and rules


* have the system answer questions by process of logical deduction using the databases’ facts and rules

LISP (LISt Programming)

* a language more similar to C++ and Pascal
* uses list to represent both data and programs
* a program can be treated as data
* writing self-modifying programs is possible

B :- A

“if A is true, then B is true” or “A implies B”

“if cheese is made from milk and milk contains calcium, then cheese contains calcium”

What is this example of a rule in PROLOG written in human language?

contains(cheese, calcium) :- made_from(cheese, milk), contains(milk, calcium)

Chinese Room

\n Designed by the American philosopher Jon Searle to argue against the proponents of strong AI

Chinese Room experiment components

* an English-speaking human placed inside a room
* the human can speak only English and has no ability to read, speak, or understand Chinese
* inside the room with the human are
* a set of cards showing printed Chinese symbols
* a set of instructions written in English

Chinese Room experiment

* a story in Chinese is fed into the room through a slot along with a set of questions about the story
* by following the cards and instructions the human has to answer these questions
* pass the answers back to the questioner through the slot
* if the system were set up properly
* would be able to make an observer believe that the room or person inside truly understood the story, the questions, and the answers it gave

after the Chinese Room experiment

* the man in the room does not understand Chinese
* the pieces of cards do not understand Chinese
* the room itself does not understand Chinese
* in other words
* a computer program that behaves in an intelligent way does not necessarily produce understanding, consciousness, or real intelligence

fuzzy logic

widely used in washing machines, cars, and elevator control mechanisms

intelligent agents

widely used to

* solve problems while using our computers
* search the Internet for documents that might be of interest

robots

are widely used

* as the physical embodiment of agents
* to explore the oceans and other worlds
* to travel in environments inhospitable to humans

expert systems

are used by doctors to prescribed treatment in cases where even human experts have difficulty

a) the variables it uses, c) the operators applied to those variables

The way a computer represents a problem involves

a) the variables it uses

b) the problem definition

c) the operators applied to those variables

d) the variable created for the computer

b) search of solutions

There are a wide range of representations used in AI. A good representation is vital for the

a) research development

b) search of solutions

c) creation of software systems

d) solution modeling

semantic nets

a graph consisting of nodes that are connected by edges (links)

* nodes represent objects
* links between nodes represent relationships between those objects
* the links are usually labeled to indicate the nature of the relationship

represent knowledge

Semantic nets provide a very intuitive way to ___________________ about objects and their relationships.

true

(T/F) The links in a semantic net are directional.

false

(T/F) The links in a semantic net are not directional.

true

(T/F) The data in semantic nets can be reasoned about, such as the ability to represent negations.

instances

Objects are referred to as ___________ of a particular class.

frames

an object-oriented representation that can be used to build expert systems

* each of this describes either an instance or a class

\

slots, slot values

Each frame has one or more ____________ that are assigned ________________.

true

(T/F) An instance could be a physical object, a property, a place, a situation, or a feeling.

relationship

Each ______________ is expressed by a value being placed in a slot.

generalization

using the is-a relationship to express membership of classes

true

(T/F) In frame-based systems, all information about a particular object is stored in one place.

why frames are useful

in frame-based systems

* all information about a particular object is stored in one place

in a rule-based system

* information about an object might be stored in a number of unrelated rules
* if the object changes, or a deduction needs to be made about the object
* time may be wasted examining irrelevant rules and facts

inheritance

a relation that can be particularly useful in AI

* can define a subclass which inherits the properties of its super class

exceptions

Inheritance needs to express __________ in some cases.

true

(T/F) In some cases of inheritance, the default value in the super class is overridden in the subclass.

false

(T/F) In the cases of inheritance, the default value in the super class is always overridden in the subclass.

true

(T/F) It is possible to express a range of values that a slot can take.

false

(T/F) It is not possible to express a range of values that a slot can take.

multiple inheritance

* an object can be an instance of more than one class
* a frame can inherit properties from more than one other frame

contradictory information

Multiple inheritance might lead to ____________________ about a frame.

procedures

a set of instructions associated with a frame that can be executed on request

WHEN-NEEDED procedures

procedures that are called when needed

demon

a particular type of procedure

* run automatically whenever a particular value changes or when a particular event occurs

WHEN-READ demon

are called automatically when a slot value is read

* can calculate the value to be returned to the user

WHEN-CHANGED demon

are run automatically when a slot value is changed

* also known as WHEN-WRITTEN demon
* can be used to ensure that values assigned to a slot meet the constrains

search space

consist of a set of states, connected by paths that represent actions

* many search problems can be represented by this

goal states

one or more states of the desired results

aim of search procedures

* to identify one or more goals and then find the paths to those goals
* usually interested in the shortest path, or the path with least cost

state transitions

For a robot that lives in an environment with three rooms (room A, B, C) and a block that can be moved from room to room.

The arrows between states represent

search tree

a kind of search space with the following properties

* one node has no predecessors called the root node
* each node (except for root node) has exactly ne predecessor (parent) and one or more successors (children)
* some nodes have no successors called leaf nodes
* one or more leaf nodes are called goal nodes that represent a state where the search has succeeded

root node

a node in a search tree that has no predecessors

leaf nodes

nodes in a search tree that have no successors

goal nodes

one or more leaf nodes that represent a state where the search has succeeded

ancestor

A ___________ of a node is a node further up the tree in some path.

descendent

A _______________ comes after a node in a path in the tree.

complete path

a path that leads from the root node to a goal node

partial path

a path that leads from the root node to a leaf node that is not a goal node

branching factor

If a node has n successors, that node has a ________________ of n

true

(T/F) A tree that has branching factor of n means the average branching factor of all the nodes is n.

false

(T/F) A tree that has branching factor of n means the average branching factor of all the nodes is n/2.

cycles are allowed in any path, construct the tree in a top-down and right-left manner, after reaching the first goal state the construction is stopped

Select which of the following are NOT guidelines to constructing a search tree

* cycles are allowed in any path
* start from the root (initial state)
* the shortest path from the root to a goal state is the best solution
* construct the tree in a top-down and right-left manner
* no repeated state in the tree
* after reaching the first goal state the construction is stopped

problem solving as search

a set of actions that can be taken to lead from the initial state to the goal state

* during the search
* keep checking if the current state has reached the desired result or not

data-driven search

* start from an initial state and use actions to move forward until a goal is reached
* a top-down approach
* also known as forward chaining

goal-driven search

* start at the goal state and work back toward an initial state
* a bottom-up approach
* also known as backward chaining

when the goal can be clearly specified

When is the goal-driven search particularly useful?

when the initial data is provided but its not clear what the goal is

When is the data-driven search particularly useful?

succeeded, moves on to the next node

Generate each node in the search space and test it to see if it is a goal node

* If yes, the search has _____________
* If no, the procedure ____________________________

generate and test

* is the simplest form of brute-force search
* also known as exhaustive search or blind search
* assume no additional knowledge other than
* how to traverse the search tree and how to identify leaf nodes and goal nodes

depth-first search

* follow each path to its greatest depth before moving on the next path
* start from the left side and work toward the right
* work all the way down the left-most path in the tree until a leaf node is reached
* if it is a goal node, the search is successfully completed
* if not, search backtracks up to the next highest node that has an unexplored path

chronological backtracking

Depth-first search uses a method called ____________________ to move back up the search tree.

breadth-first search

* start by examining all nodes one level down from the root node
* if a goal state is reached, success is reported
* otherwise, continue to search all the nodes in the current level then go down to the next level

when the tree has very deep paths, when the goal node is in a shallower part of the tree

When is breadth-first search good to use?

a) when the branching factor is extremely high

b) when the tree has very deep paths

c) when the goal node is in a shallower part of the tree

d) when there is more than one goal node

a) when the branching factor is extremely high

When is breadth-first search NOT good to use?

a) when the branching factor is extremely high

b) when the tree has very deep paths

c) when the goal node is in a shallower part of the tree

d) when there is more than one goal node

less memory

Depth-first search requires ____________ than breadth-first search

current path, all paths that reach the current depth

* Depth-first search needs to store info about the _________________
* Breadth-first search needs to store info about _______________________

depth threshold

The problem of infinite paths can be avoided by applying ________________________

* some goals might be missed but all branches will be explored within reasonable time

properties of search methods

* complexity
* completeness
* optimality
* admissibility
* irrevocability
* monotonicity

complexity

to describe how efficient is the method

* by using big-O notation

time complexity

related to the length of time that the method would take to find a goal state

space complexity

related to the amount of memory that the method needs to use