Artificial Intelligence Exam 1

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

• if given sufficient processing power and enough intelligence

• it can literally think and is conscious about the behavior it is performing

• 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

• 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

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

• depend on a system being given a great deal of domain knowledge

• focus on knowledge representation

• depend on the weak methods

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

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

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

• a treatise on logic

• the first real study of logic written by Peter Abelard in the 12th century

• German mathematician and philosopher who thought of developing a formal mathematical language for reasoning

• allowed us to express problems to go about solving them

developed by English mathematician George Bool

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

• the world’s first computer invented by Charles Babbage

• his logical design was used to build working digital \n computers around 1950s

• 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

• 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

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

• invented to solve almost any logical problem

• works well on simple problems, but could not be applied in a general way

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

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

• 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

• theory proposed by Noam Chomsky

• a formal theory of the structure of human language

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

• made by McCulloch and Pitt

• used today to build neural networks

• based on the function of human brain neurons

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

two programming languages that have features particularly useful for AI projects

• 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

• 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

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

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

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

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

• 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

• 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

• 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

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

widely used to

• solve problems while using our computers

• search the Internet for documents that might be of interest

are widely used

• as the physical embodiment of agents

• to explore the oceans and other worlds

• to travel in environments inhospitable to humans

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

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

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

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

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

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

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

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

Objects are referred to as ___________ of a particular class.

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

• each of this describes either an instance or a class

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

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

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

using the is-a relationship to express membership of classes

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

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

a relation that can be particularly useful in AI

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

Inheritance needs to express __________ in some cases.

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

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

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

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

• an object can be an instance of more than one class

• a frame can inherit properties from more than one other frame

Multiple inheritance might lead to ____________________ about a frame.

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

procedures that are called when needed

a particular type of procedure

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

are called automatically when a slot value is read

• can calculate the value to be returned to the user

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

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

• many search problems can be represented by this

one or more states of the desired results

• 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

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

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

a node in a search tree that has no predecessors

nodes in a search tree that have no successors

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

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

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

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

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

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

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

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

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

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

• 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

• start at the goal state and work back toward an initial state

• a bottom-up approach

• also known as backward chaining

When is the goal-driven search particularly useful?

When is the data-driven search particularly useful?

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 ____________________________

• 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

• 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

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

• 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 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

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

Depth-first search requires ____________ than breadth-first search

• Depth-first search needs to store info about the _________________

• Breadth-first search needs to store info about _______________________

The problem of infinite paths can be avoided by applying ________________________

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

• complexity

• completeness

• optimality

• admissibility

• irrevocability

• monotonicity

to describe how efficient is the method

• by using big-O notation

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

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