Introduction to Artificial Intelligence 2073

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.

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.

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:

Natural language processing is a technology which involves converting spoken or written human language into a form which can be processed by computers, and vice versa. NLP is composed of two parts: NLU and NLG.

Issues involved in the natural language processing are given below:

1. The same expression means different things in different context.

·         Where’s the water? ( Chemistry lab? Must be pure)

·         Where’s the water? ( Thirsty? Must be drinking water)

·         Where’s the water? ( Leaky roof? It can be dirty)

2. No natural language program can be complete because of new words, expression, and meaning can be generated quite freely.

·         I’ll fax it to you

3.  There are lots of ways to say the same thing.

·         Ram was born on October 11.

·         Ram’s birthday is October 11.

4.  Sentence and phrases might have hidden meanings

•      “Out of sight, out of mind”-> “ invisible idiot”

•      “The spirit was willing but the flesh was weak” - > “ the vodka was good, but the meat was bad”

5.  Problem due to syntax and semantics

6.  Problem due to extensive use of pronouns. (semantic issue)

•      Eg. Ravi went to the supermarket. He found his favorite brand of coffee in rack. He paid for it and left.

•      It denotes??

7.  Use of grammatically incorrect sentence

•      He rice eats. (syntax issue)

8.  Use of conjunctions to avoid repetition of phrases cause problem in NLP

•      Eg. Ram and Hari went to restaurant. While Ram had a cup of coffee, Hari had tea.

•      Hari had a cup of tea.

Inference: Inference is a process by which new sentences are derived from existing sentences in KB. E.g. Modus tollens is a rule of inference which derives new knowledge.

Reasoning: Reasoning is the act of deriving a conclusion from certain premise using given methodology.

 Probabilistic reasoning is using logic and probability to handle uncertain situations. The aim of probabilistic reasoning is to combine the capacity of probability theory to handle uncertainity with the capacity of deductive logic to exploit structure of formal argument.

Probabilistic reasoning is used in AI:

• When we are unsure of the predicates
• When the possibilities of predicates become too large to list down
• When it is known that an error occurs during an experiment

One has to apply probabilistic reasoning in deciding about the next card to play in a game of cards or in diagnosing the illness from the symptoms.

Bayesian networks are a type of probabilistic graphical model that uses Bayesian inference for probability computations.

• Bayesian Network is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph.
• Nodes in the graph represent the random variables and the directed edges between nodes represent conditional dependencies.
• The edge exists between nodes if there exists conditional probability i.e. a link from X to Y means Y is dependent of X.
• Each nodes are labelled with probability.

E.g.

P(x) = 0.5

P(y/x) = 0.7

P(z) = 0.8

P(u/y) = 0.47

Inference with Bayesian Network:

        Using a Bayesian network to compute probabilities is called inference in Bayesian network.

The first task is to compute the posterior probability distribution for the query variable X, given some assignment of values e to the set of evidence variable E = E₁,......., E_n and the hidden variables are Y = Y₁,.....Y_n. From the full joint probability distribution we can answer the query P(X/e) by computing

        P(x/e) = αP(X, e) = αΣ_Y(X, e, Y)

A Bayesian network gives a complete representation of the full joint distribution, specifically, the terms P(X, e, Y) can be written as products of conditional probabilities from the network.

        Therefore, a query can be answered using a Bayesian network by computing sums of products of conditional probabilities from the network.

The predicate in given KB are:

Conceptual graph is a graph representation for logic based on the semantic networks and the existential graphs of Charles sanders Peirce. 

A conceptual graph consists of concept nodes and relation nodes.

• The concept node represents entities, attributes, states and events.
• The relation node show how the concepts are interrelated.

Conceptual graph for given sentence:

Model Based System

• A model-based system is based on a model of the structure and behavior of the device that the system is designed to simulate.
• It is used for well structured problems. E.g. Engineering problems: Diagnosing hardware or  a machine, Automobile diagnostics
• It is based on written document.
• Observed behavior (what the device is actually doing) is compared with predicted behavior (what the device should do).

Case Based System

• A case-based system is a collection of a set of cases. It stores a case in the Case Base.
• It is based on human information processing (HIP) model in some problem areas: Thinking about how human processes information, Try to remember previous case/recall similar cases & modify to fit a new situation.
• E.g. Law, diagnosis, strategic planning
• It retrieves cases relevant to the present problem situation from the case base and decides on the solution to the current problem on the basis of the outcomes from the previous cases.

a. Electronic Circuit Testing --> Model based system is suitable.

b. Legal Reasoning --> Case based system is suitable.