Introduction to Artificial Intelligence 2072

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.

 “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 sentence that is expressed as a conjunction of disjunction of literals is said to be in conjunctive normal form (CNF). E.g. (P∨Q)∧(P∨R)

CNF conversion steps

1. Eliminate ↔ rewriting P↔Q as (P→Q)∧(Q→P)

2. Eliminate → rewriting P→Q as ¬P∨Q

3. Use De Morgan‘s laws to push ¬ inwards:

        - rewrite ¬(P∧Q) as ¬P∨¬Q

        - rewrite ¬(P∨Q) as ¬P∧¬Q

4. Eliminate double negations: rewrite ¬¬P as P

5. Use the distributive laws to get CNF:

        - rewrite P∨(Q∧R) as(P∨Q)∧(P∨R)

6. Use:

        - (P∧Q) ∧ R as P∧Q ∧ R

        - (P∨Q)∨R as P∨Q∨R

E.g. Converting to CNF

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. 

Belief network / 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 Belief / 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.

Mathematical model of neural Network

Type of Neural Network: Feed-forward Neural Network

Feed-forward ANNs allow signals to travel one way only; from input to output. There is no feedback (loops) i.e. the output of any layer does not affect that same layer. Feed-forward ANNs tend to be straight forward networks that associate inputs with outputs. They are extensively used in pattern recognition.

An expert system is a set of program that manipulate encoded knowledge to solve problem in a specialized domain that normally requires human expertise.

An expert system's knowledge is obtained from expert sources and code in a form suitable for the system to use in its inference process.

We require expert system due to the following reasons:

• It provides consistent answer for repetitive decisions, processes and tasks.
• It holds and maintain levels of information.
• It can tackle very complex problems that are difficult for human expert to solve.
• It can discover new knowledge.
• It can work steadily without getting emotional, tensed or fatigued.
• It provides quick and efficient solutions to problem in narrow area of specialization.

Architecture of expert system

Knowledge Base (KB): The component of an expert system that contains the system’s knowledge is called its knowledge base. It contains the rules of in IF-THEN rule. The KB contains the knowledge necessary for understanding, formulating & solving problems. The KB of an expert system contains both declarative knowledge and procedural knowledge.

Inference Engine: It carries out the reasoning by interplaying the information or facts obtained from the user with the knowledge stored in knowledge base whereby the expert system reaches a solution.

Working memory: It is a data structure which stores information about a specific problem.

User Interface: The component of an expert system that communicates with the user is known as the user interface. The communication performed by a user interface is bidirectional. At the simplest level, we must be able to describe our problem to the expert system, and the system must be able to respond with its recommendations. 

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 part: NLU (Natural Language Understanding) and NLG (Natural Language generation).

Steps of Natural Language Processing (NLP)

Input/Source

• The input of a NLP system can be written text or speech.

• Quality of input decides the possible errors in language processing that is high quality input leads to correct language understanding.

Segmentation

• The text inputs are divided in segments (Chunks) and the segments are analyzed. Each such chunk is called frames.

Syntactic Analysis

• Syntactic analysis takes an input sentence and produces a representation of its grammatical structure.
• A grammar describes the valid parts of speech of a language and how to combine them into phrases.
• The grammar of English is nearly context free.

Grammar: A computer grammar specifies which sentences are in a language and their parse trees. A parse tree is a hierarchical structure that shows how the grammar applies to the input. Each level of the tree corresponds to the application of one grammar rule.

Parse Tree:

Semantic Analysis

• Semantic analysis is a process of converting the syntactic representations into a meaning representation.
• This involves the following tasks:

                    - Word sense determination

                    -  Sentence level analysis

Word sense: Words have different meanings in different contexts.

Example:Mary had a bat in her office.

        bat = ``a baseball thing’

        bat = ``a flying mammal’

Sentence Level Meaning:

Once the words are understood, the sentence must be assigned some meaning

Examples:

• She saw her duck.
• I saw a man with a telescope.

Non-examples: Colorless green ideas sleep furiously - >This would be rejected semantically as colorless green would make no sense.

Pragmatic Analysis

• Pragmatics comprises aspects of meaning that depend upon the context or upon facts about real world.
• These aspects include:

                - Pronouns and referring expressions.

                - Logical inferences, that can be drawn from the meanings of a set of propositions.

                - Discourse structure: the meaning of a collection of sentences taken together.

Examples:

Jack fell. Jill brought him a band-aid.

        Jack got hurt and Jill wanted to help.

We got seven letters today

        We got only seven letters (and not eight).