Artificial Intelligence - Unit Wise Questions

Artificial Intelligence (AI) is the part of computer science concerned with designing intelligence computer systems i.e. systems that exihibit the characteristics we associate with intelligence in human behaviour.

The behaviours of AI are as follows:

1. Learn from experience and apply knowledge acquired from experience

2. Handle Complex Situations

3. Solve problems with important information is missing: Decision must be made even when we lack information or have inaccurate information.

4. Determine what is important

5. React quickly and correctly to a new situation

6. Understand visual images

7. Process and manipulate symbols

8. Be creative and imaginative

9. Use heuristics

Turing Test

The Turing test, proposed by Alan Turing  was designed to convince the people that whether a particular machine can think or not. The test involves an interrogator who interacts with one human and one machine. Within a given time the interrogator has to find out which of the two the human is, and which one the machine.

To pass a Turing test, a computer must have following capabilities:

• Natural Language Processing: To communicate easily.
• Knowledge Representation: To store facts and rules.
• Automated Reasoning: To draw conclusion from stored knowledge.
• Machine Learning: To adopt new circumstances and detect pattern.

Additional requirements for the “total Turing test”: computer vision, speech recognition, speech synthesis, robotics.

Thinking humanly and Thinking rationally are concerned with thought process and reasoning.

Thinking Humanly

Defⁿ: The exciting new effort to make computers think machines with minds, in the full and literal sense.

If we are going to say that a given program thinks like a human, we must have some way of determining how humans think. We need to get inside the actual workings of human minds. There are two ways to do this: through introspection--trying to catch our own thoughts as they go by--or through psychological experiments. Once we have a sufficiently precise theory of the mind, it becomes possible to express the theory as a computer program. If the program's input/output and timing behavior matches human behavior, that is evidence that some of the program's mechanisms may also be operating in humans. 

Thinking Rationally

Defⁿ: The study of mental faculties through the use of computational models.

The laws of thought are supposed to implement operation of the mind and their study initiated the field called logic. It provides precise notations to express facts of the real world.

It also includes reasoning and "right thinking" that is irrefutable thinking process. Also computer program based on those logic notations were developed to create intelligent system.

The Turing test, proposed by Alan Turing  was designed to convince the people that whether a particular machine can think or not. The test involves an interrogator who interacts with one human and one machine. Within a given time the interrogator has to find out which of the two the human is, and which one the machine.

To pass a Turing test, a computer must have following capabilities:

• Natural Language Processing: To communicate easily.
• Knowledge Representation: To store facts and rules.
• Automated Reasoning: To draw conclusion from stored knowledge.
• Machine Learning: To adopt new circumstances and detect pattern.

Additional requirements for the “total Turing test”: computer vision, speech recognition, speech synthesis, robotics.

Critics of Turing test:

• Test is not reproducible, amenable or constructive to mathematical analysis as it is more important to study the underlined principles of intelligence than to duplicate example.

• Trying to evaluate machine intelligence in terms of human intelligence is fundamental mistake. It focuses too much on the behavior of conversation.

The Turing test, proposed by Alan Turing  was designed to convince the people that whether a particular machine can think or not. The test involves an interrogator who interacts with one human and one machine. Within a given time the interrogator has to find out which of the two the human is, and which one the machine.

To pass a Turing test, a computer must have following capabilities:

• Natural Language Processing: To communicate easily.
• Knowledge Representation: To store facts and rules.
• Automated Reasoning: To draw conclusion from stored knowledge.
• Machine Learning: To adopt new circumstances and detect pattern.

Additional requirements for the “total Turing test”: computer vision, speech recognition, speech synthesis, robotics.

Critics of Turing test:

• Test is not reproducible, amenable or constructive to mathematical analysis as it is more important to study the underlined principles of intelligence than to duplicate example.

• Trying to evaluate machine intelligence in terms of human intelligence is fundamental mistake. It focuses too much on the behavior of conversation.

Artificial intelligence is about designing systems that are as intelligent as humans. It involves trying to understand human thought and an effort to build machines that emulate the human thought process.

System that think like humans

Defⁿ: The exciting new effort to make computers think machines with minds, in the full and literal sense.

E.g. a program that think like humans, i.e. a cognitive modeling approach in which once we have sufficiently precise theory of mind , it become possible to express the theory as computer program.

System that act like humans

Defⁿ:  ”The art of creating machines that perform functions that require when performed by people” .
E.g. Turing Test approach: Which is based on the indistinguishability from undeniably intelligent entities.
           You enter a room which has a computer terminal. You have a fixed period of time to type what you want into the terminal, and study the replies. At the other end of the line is either a human being or a computer system.                   
           If it is a computer system, and at the end of the period you cannot reliably determine whether it is a system or a human, then the system is deemed to be intelligent.

 “System that think rationally” and “System that act rationally”  measure an ideal concept of intelligence, which is called rationality.

System that think rationally

Defⁿ: The study of mental faculties through the use of computational models.

The laws of thought are supposed to implement operation of the mind and their study initiated the field called logic. It provides precise notations to express facts of the real world.

It also includes reasoning and "right thinking" that is irrefutable thinking process. Also computer program based on those logic notations were developed to create intelligent system.

System that act rationally

Defⁿ: “Computational Intelligence is the study of design of intelligent agents”
E.g. ”Rational agent approach” , agent is the one who decide what to do and then perform action by receiving percepts from the environment.

A rational agent is an agent which has clear preferences and models uncertainity via expected value. It always performs right action, right action  means the action that causes the agent to be most successful in the given percept sequence.

Rational agent is capable of taking best possible action in any situation.

For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

The agents rational behavior depends upon:

• Performance measures
• Prior environment knowledge
• Actions
• Percept sequence upto now

a. Medical Diagnosis System: Utility Based Agent

b. Satellite image analysis system: Goal Based Agent

c. Part-picking robot: Goal Based Agent

d. Refinery Controller: Utility Based Agent

a. Medical Diagnosis System: Utility Based Agent

b. Satellite image analysis system: Goal Based Agent

c. Part-picking robot: Goal Based Agent

d. Refinery Controller: Utility Based Agent

A rational agent is an agent which has clear preferences and models uncertainity via expected value. It always performs right action, right action  means the action that causes the agent to be most successful in the given percept sequence.

Rational agent is capable of taking best possible action in any situation.

For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Episodic task environment vs Sequential task environment

In Episodic environment, the agent's experience is divided into atomic 'episodes' (each episode consists of the agent perceiving then performing a single action i.e. agent's single pair of perception & action) and every episode is independent of each other. The subsequent episodes do not depend on actions occured in previous episodes. For e.g. an agent sorting defective part in an assembly line, pick and place robot agent.

In Sequential environment, current actions may affect all future decisions. In sequential environment, an agent requires memory of past action to determine the next best action. For e.g. a taxi driving agent or Chess playing.

PEAS Framework for:

Soccer Playing Agent

Performance Measure (P): To Play, Make Goal & Win the Game.

Environment (E): Soccer, Team Members, Opponents, Referee, Audience and Soccer Field.

Actuators (A): Navigator, Legs of Robot, View Detector for Robot.

Sensors (S): Camera, Communicators and Orientation & Touch Sensors.

Internet Shopping Assistant

Performance measure: price, quality, appropriateness, efficiency

Environment: current and future WWW sites, vendors, shippers

Actuators: display to user, follow URL, fill in form

Sensors: HTML pages (text, graphics, scripts)

When we have a decision and based on the decision if we fetch the initial dat that supports goal then the process is called as backward chaining. Backward chaining starts with a goal and then searches back through inference rules to find the facts that support the goal.

E.g. "If it is raining then we will take umbrella". Here we have our possible conclusion "we will take umbrella". If we are taking umbrella then it can be stated that " it is raining". Here based on conclusion we guessed that the data can be "it is raining". This process is called backward chaining.

• The system that uses backward chaining tries to set goals in order which they arrive in the knowledge base.
• While searching, the backward chaining considers those parts of knowledge base which are directly related to the considered problem or backward chaining never performs unnecessary inferences.
• Backward chaining is an excellent tool for specific type of problem such as diagnosing & debugging.

Here, when search reaches at node C it stucks in loop. So we can't reach at goal node. Therefore, Greedy Best First Search is not complete for the given state space.

When we have some data and we make a decision based on this data then the process is called as forward chaining. Forward chaining starts with the available data and uses inference rules to extract more data until a goal is reached.

Forward chaining has the capability of providing a lot of data from the available few initial data or facts.

Forward chaining is a very popular technique for implementation to expert system, and system using production rules in the knowledge base. For expert system that needs interruption, control, monitoring and planning, the forward chaining is the best.

Examples:

1. While diagnosing a patient the doctor first check the symptoms and medical condition of the body such as temperature, blood, pressure, pulse, blood etc. After that, the patient symptoms are analysed and compared against the predetermined symptoms. Then the doctor is able to provide the medicine according to the symptoms of the patient.

2. "if it is raining then we will take umbrella". Here "it is raining" is data and "we will take umbrella" is a decision. It was alrready known that it is raining that is why we are going to take umbrella. This is forward chaining.

Uninformed (Blind) Search does not use any domain knowledge. This means it does not any information to judge where the solution is likely to lie. Uninformed search methods use only the information available in the problem definition.

For E.g.

Breadth First Search

It expands the shallowest unexpanded node first. Starting from the root node (initial state) explores all children of the root node, left to right. If no solution is found, expands the first (leftmost) child of the root node, then expands the second node at depth 1 and so on …until a solution is found.

E.g.

In goal formulation, we decide which aspects we are interested in and which aspects can be ignored. In the goal formulation process, the goal is to be set and we should assess those states in which the goal is satisfied. In problem formulation, we decide how to manipulate the important aspects, and ignore the others. So, without doing goal formulation, if we do the problem formulation, we would not know what to include in our problem and what to leave, and what should be achieved. So problem formulation must follow goal formulation. That means problem formulation must be done only after the goal formation is done.

In the state space representation of a problem, nodes of a graph correspond to partial problem solution states and arcs represent steps in a problem- solving process. An initial state, corresponding to the given information in a problem instance, forms the root of the graph. The graph also defines a goal condition, which is the solution to a problem instance. State space search characterizes problem solving as the process of finding a solution path from the start state to a goal state. Arcs of the state space correspond to steps in a solution process and path through the space represent solutions in varying stages of completion. Paths are searched, beginning at the start state and continuing through the graph until either the goal description is satisfied or they are abandoned.

E.g.

State Space representation of Vacuum World Problem:

States: two locations with or without dirt: = 8 states.

Initial state:  Any state can be initial

Actions:  {Left, Right, Suck}

Goal test: Check whether squares are clean.

Path cost:  Number of actions to reach goal.

a. BFS finds the solution as DFS and iterative deepening enter the infinite loop due to no repeated state checking.

b. Using BFS: A --> C

The state space is commonly defined as a directed graph in which each node is a state and each arc represents the application of an operator transforming a state to a successor state. A solution is a path from the initial state to a goal state.

State Space representation of Vacuum World Problem:

States: two locations with or without dirt: = 8 states.

Initial state:  Any state can be initial

Actions:  {Left, Right, Suck}

Goal test: Check whether squares are clean.

Path cost:  Number of actions to reach goal.

 Representing the root finding problem having four cities in to state representation:

The above problem can be formulate as:

States: All four cities. {Oradea, Zerind, Sibiu, Arad}

Initial State:  Current city where we are. For e.g. Oradea

Actions: Drive between cities or choose next city.

Goal test: Check whether the agent is in Arad and 4 cities have been visited.

Path Cost: Sum of distances.

    A solution is a sequence of actions leading from the initial state to a goal state

AI problems can be readily modeled as state spaces, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space. Using different searching algorithms we can find the best possible solution. So searching is important in AI.

Breadth First Search

It expands the shallowest unexpanded node first. Starting from the root node (initial state) explores all children of the root node, left to right. If no solution is found, expands the first (leftmost) child of the root node, then expands the second node at depth 1 and so on …until a solution is found.

E.g.

Depth First Search

It expands the deepest unexpanded node first.

It expands the root node, then the leftmost child of the root node, then the left most child of that node and so on. Only when the search hits dead end does the search backtrack.

E.g.

The information which is used to search the space more efficiently is called heuristic information.

Ways of using heuristic information:

• Deciding which node to expand next, instead of doing the expansion in a strictly breadth-first or depth-first order;

• In the course of expanding a node, deciding which successor or successors to generate, instead of blindly generating all possible successors at one time;

• Deciding that certain nodes should be discarded, or pruned, from the search space.

The function g(n) gives the cost of the path from initial state to the node n. Using h(n) = -g(n) for the heuristic function in a greedy search, then, will cause the algorithm to always select the node with the highest path cost so far (the largest g(n)) to expand next, since this will give us the smallest h(n) (i.e. the most negative value). If all operations have the same cost value associated with them, then the largest g(n) will always correspond to the longest path in the search tree and the greedy search will emulate depth-first search.

If we set h(n) = g(n) we get breadth first search.

Uniform cost searching algorithm is used for weighted state space. In this algorithm,

• Priority queue for storing nodes in state space is maintained, where least cost paths are given higher priority.
• Node at head of the queue is expanded first.
• The queue is updated at each expansion of nodes (deletion of node visited & insertion of node to be visited).

Given state space:

A heuristic function is said to be admissible if it is no more than the lowest-cost path to the goal. In other words, a heuristic is admissible if it never overestimates the cost of reaching the goal.

In greedy search, the evaluation function is defined by    f(n) = h(n)

               Where, h(n) is an estimate of cost from node n to goal node.

But in A* search, the evaluation function is defined by  f(n) = g(n) + h(n) 

            Where, g(n) is sum of actual costs incurred while travelling from root node (start node) to node n.

                         h(n) is an estimate of cost from node n to goal node

                         f(n) is estimated total cost of path through n to goal.

A* search gives us optimal solution if the heuristic function is admissible.

Proof:

AI problems can be readily modeled as state spaces, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space. Using different searching algorithms we can find the best possible solution. So searching is important in AI.

Breadth First Search

It expands the shallowest unexpanded node first. Starting from the root node (initial state) explores all children of the root node, left to right. If no solution is found, expands the first (leftmost) child of the root node, then expands the second node at depth 1 and so on …until a solution is found.

E.g.

Depth First Search

It expands the deepest unexpanded node first.

It expands the root node, then the leftmost child of the root node, then the left most child of that node and so on. Only when the search hits dead end does the search backtrack.

E.g.

AI problems can be readily modeled as state spaces, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space. Using different searching algorithms we can find the best possible solution. So searching is important in AI.

Informed search uses domain-dependent (heuristic) information in order to search the space more efficiently. It uses the heuristic function h(n) that estimates how close we are to a goal. The function is used to estimate the cost from  a state n to the closest goal.

Types of Informed Search:

• Greedy Best-first Search
• A* Search

In above given search, nodes are expanded based on the value of evaluation function. Nodes having minimal value of evaluation function are expanded first.

Greedy Best-first Search

• It expands the node that appears to be closest to the goal.
• The evaluation function is defined by    f(n) = h(n)

                Where, h(n) is an estimate of cost from node n to goal node

                            h(n) = 0 for goal node.

A* Search

The evaluation function is defined by    f(n) = g(n) + h(n) 

            Where, g(n) is sum of actual costs incurred while travelling from root node (start node) to node n.

                         h(n) is an estimate of cost from node n to goal node

                         f(n) is estimated total cost of path through n to goal.

AI problems can be readily modeled as state spaces, where we want to find the best possible solution, that successfully solves a particular task, among all the available candidate solutions in the solution space. Using different searching algorithms we can find the best possible solution. So searching is important in AI.

Blind Search does not use any domain knowledge. This means it does not any information to judge where the solution is likely to lie. E.g. Breadth first search, Depth first search, Uniform cost search etc.

Breadth First Search

It expands the shallowest unexpanded node first. Starting from the root node (initial state) explores all children of the root node, left to right. If no solution is found, expands the first (leftmost) child of the root node, then expands the second node at depth 1 and so on …until a solution is found.

E.g.

Depth First Search

It expands the deepest unexpanded node first.

It expands the root node, then the leftmost child of the root node, then the left most child of that node and so on. Only when the search hits dead end does the search backtrack.

E.g.

Blind search is extended to informed search by using domain-dependent (heuristic) information in order to search the space more efficiently. It uses the heuristic function h(n) that estimates how close we are to a goal. 

Alpha Beta pruning is needed to eliminate unnecessary nodes from state space. It has two values alpha and beta.

Alpha is the best (i.e. maximum) value found so far at any choice point along the path for MAX.

Beta is the best (i.e. minimum) value found so far at any choice point along the path for MIN.