|
UNIT
– 1 |
|||||||||
|
Unit-01/Lecture-01 |
|||||||||
|
Soft
Computing: Soft computing is a term applied to a field within computer
science which is characterized by the use of inexact solutions to
computationally hard tasks such as the solution of NP-complete
problems, for which there is no known algorithm that can compute an exact
solution in polynomial time. Soft computing differs from
conventional (hard) computing in that, unlike hard computing, it is tolerant
of imprecision, uncertainty, partial truth, and approximation. In effect, the
role model for soft computing is the human mind. Fig 1: Soft
computing represents that area of computing adapted from the physical
sciences The Soft Computing – development history The following two schemes show
development history of Soft Computing in brief.
Importance of Soft Computing The complementarity of FL, NC, GC, and PR has an
important consequence: in many cases a problem can be solved most effectively
by using FL, NC, GC and PR in combination rather than exclusively. A striking
example of a particularly effective combination is what has come to be known
as "neurofuzzy systems." Such systems are becoming increasingly
visible as consumer products ranging from air conditioners and washing
machines to photocopiers and camcorders. Less visible but perhaps even more
important are neuro fuzzy systems in industrial applications. What is
particularly significant is that in both consumer products and industrial
systems, the employment of soft computing techniques leads to systems which
have high MIQ (Machine Intelligence Quotient). In large measure, it is the
high MIQ of SC-based systems that accounts for the rapid growth in the number
and variety of applications of soft computing Hard computing: Hard computing based on binary logic, crisp systems, numerical
analysis and crisp software but soft
computing based on fuzzy logic, neural nets and probabilistic
reasoning Soft Computing
vs Hard Computing :-(Jun 2014) (1)
Soft Computing is tolerant of
imprecision, uncertainty, partial truth and approximation whereas
Hard Computing requires a
precisely state analytic model. (2)
Soft Computing is based on fuzzy logic, neural sets,
and probabilistic reasoning whereas Hard Computing is based on
binary logic, crisp system, numerical analysis and crisp software. (3)
Soft computing has the
characteristics of approximation and dispositionality whereas Hard
computing has the characteristics of precision and categoricity. (4)
Soft computing can evolve its
own programs whereas Hard computing requires programs to be
written. (5)
Soft computing can use
multivalued or fuzzy logic whereas Hard computing uses two-valued
logic. (6)
Soft computing incorporates
stochasticity whereas Hard computing is deterministic. (7)
Soft computing can deal with
ambiguous and noisy data whereas Hard computing requires exact
input data. (8)
Soft computing allows parallel
computations whereas Hard computing is strictly sequential. (9)
Soft computing can yield
approximate answers whereas Hard computing produces precise
answers.
|
|
Unit-01/Lecture-02 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
various types of soft computing
techniques: (Jun 2013) (i)
Neural Network (ii)
Fuzzy Logic (iii)
Genetic Algorithm Applications of soft computing: (1)
Actuarial
Science Actuarial science is the discipline
that applies mathematical and statistical methods to evaluate risk in the
insurance and finance industries. Actuarial science includes a number of
interrelating subjects, including probability, mathematics, statistics,
finance, economics, financial economics, and computer programming.
Historically, actuarial science used deterministic models in the construction
of tables and premiums. (2) Agricultural Engineering
Agricultural engineering is the
engineering discipline that applies engineering science and technology to
agricultural production and processing. Agricultural engineering combines the
disciplines of animal biology, plant biology, and mechanical, civil,
electrical and chemical engineering principles with knowledge of agricultural
principles. (3)
Biomedical
Application Biomedical application is a design
concept to medicine and biology. This field seeks to close the gap between
engineering and medicine: It combines the design and problem solving skills
of engineering with medical and biological sciences to advance healthcare
treatment, including diagnosis, monitoring, treatment and therapy. (4)
Civil
Engineering Civil engineering is a professional
engineering discipline that deals with the design, construction, and
maintenance of the physical and naturally built environment, including works
like roads, bridges, canals, dams, and buildings. Civil engineering takes
place on all levels: in the public sector from municipal through to national
governments, and in the private sector from individual homeowners through to
international companies. (5)
Computer
Engineering Computer engineering is a discipline
that integrates several fields of electrical engineering and computer science
required to develop computer systems. Computer engineers usually have
training in electronic engineering, software design, and hardware-software
integration instead of only software engineering or electronic engineering.
Computer engineers are involved in many hardware and software aspects of computing,
from the design of individual microprocessors, personal computers, and
supercomputers, to circuit design. This field of engineering not only focuses
on how computer systems themselves work, but also how they integrate into the
larger picture. (6)
Crime
Forecasting Crime forecast is a planning tool
that helps to manage crime in our society in different way. Crime is the
breaking of rules or laws for which some governing authority can ultimately
prescribe a conviction. Crimes may also result in cautions, rehabilitation or
be unenforced. By the help of crime forecast we can reduce crime in our
societies. (7) Data Mining Data mining
is a subfield of computer science whichis the computational process of
discovering patterns in large data sets involving methods at theintersection
of artificial intelligence, machine learning, statistics, and database
systems. The overall goal of the data mining process is to extract
information from a data set and transform it into an understandable structure
for further use. (8) Environmental
Engineering Environmental
engineering is the integration of science and engineering principles to
improve the natural environment like air, water, and/or land resources, to
provide healthy water, air, and land for human habitation like house or home
and for other organisms, and to remediate pollution sites. (9) Image
Processing In imaging
science, image processing is any form of signal processing for which the
input is an image, such as a photograph or video frame; the out put of image
processing may be either an image or a set of characteristics or parameters
related to the image. Most image-processing techniques involve treating the
image as a two-dimensional signal and applying standard signal-processing
techniques to it. (10)Mechanical
Engineering Mechanical
engineering is a discipline of engineering that applies the principles of
physics and materials science for analysis, design, manufacturi ng, and
maintenance of mechanical systems. It is the branch of engineering that
involves the production and usage of heat and mechanical power for the
design, production, and operation of machines and tools. (11) Medical diagnosis Medical
diagnosis refers both to the process of attempting to determine or identify a
possible disease and to the opinion reached by this process.From the point of
view of statistics the diagnostic procedure involves classification tests. (12) Nano Technology Nanotechnology
is the manipulation of matter on an atomic and molecular scale. Generally, nanotechnology
works with materials, devices, and other structures with at least one
dimension sized from 1 to 100 nanometers. Nanotechnology entails the
application of fields of science as diverse as surface science, organic
chemistry, molecular biology, semiconductor physics, micro fabrication, etc. (13) Pattern
Recognition Pattern
recognition generally aim to provide a reasonable answer for all possible
inputs and to perform "most likely" matching of the inputs, taking
into account their statistical variation. Pattern recognition is studied in
many fields, including psychology, psychiatry, and ethology, cognitive
science, and traffic flow and computer science. (14) Signal
Processing Signal
processing is an area of systems engineering, electrical engineering and
applied mathematics that deals with operations on or analysis of signals, or
measurements of time-varying or spatially varying physical quantities. Types
of signals are sound, images, and sensor data, for example biological data
such as electrocardiograms,control system signals, telecommunication
transmission signals, and many others. Artificial Intelligence (Jun 2014) Artificial intelligence (AI) is the intelligence exhibited by
machines or software, and the branch of computer science
that develops machines and software with intelligence. Major AI researchers
and textbooks define the field as "the study and design of intelligent
agents", where an intelligent agent is a system that perceives
its environment and takes actions that maximize its chances of success. John McCarthy, who
coined the term in 1955, defines it as "the science and engineering of
making intelligent machines". Natural Intelligence (Jun 2014) Human
intelligence is something natural, no artificiality is involved in it. In all
fields, intelligence is something differently perceived and differently
acquired. More specifically, human intelligence is something related to the
adaption of various other cognitive process in order to have specific environment.
In human intelligence, the word ”intelligence”
plays a vital role because intelligence is with them all it’s need to
cogitate and make a step by step plan for performing certain task. Differentiate between Natural
Intelligence and the Artificial Intelligence:
|
|
Unit-01/Lecture-03 |
||||||||
|
Production system (Jun 2012) A production system
consists of rules and factors. Knowledge is encoded in a declarative from
which comprises of a set of rules of the form A production system is a system
based on IF ... THEN ... rules and consisting of 3 parts : 1. The set of production
rules 2. Working memory 3. The recognize – act
cycle The goal
database is the central data structure used by an AI production system. The
production system. The production rules operate on the global database. Each
rule has a precondition that is either satisfied or not by the database. If
the precondition is satisfied, the rule can be applied. Application of the
rule changes the database. The control system chooses which applicable rule
should be applied and ceases computation when a termination condition on the
database is satisfied. If several rules are to fire at the same time, the
control system resolves the conflicts. Four classes of
production systems:- 1. A
monotonic production system 2. A non
monotonic production system 3. A
partially commutative production system 4. A
commutative production system. Advantages of
production systems:- 1.
Production systems provide an excellent tool for structuring AI programs. 2.
Production Systems are highly modular because the individual rules can be
added, removed or modified independently. 3. The
production rules are expressed in a natural form, so the statements contained
in the knowledge base should the a recording of an expert thinking out loud. Disadvantages of
Production Systems:- One
important disadvantage is the fact that it may be very difficult analyse the
flow of control within a production system because the individual rules don’t
call each other. Production
systems describe the operations that can be performed in a search for a
solution to the problem. They can be classified as follows. Monotonic
production system :- A system in which the application of a rule never
prevents the later application of another rule, that could have also been
applied at the time the first rule was selected. Partially
commutative production system:- A
production system in which the application of a particular sequence of rules
transforms state X into state Y, then any permutation of those rules that is
allowable also transforms state x into state Y. Theorem
proving falls under monotonic partially communicative system. Blocks world
and 8 puzzle problems like chemical analysis and synthesis come under
monotonic, not partially commutative systems. Playing the game of bridge
comes under non monotonic , not partially commutative system. For any
problem, several production systems exist. Some will be efficient than
others. Though it may seem that there is no relationship between kinds of
problems and kinds of production systems, in practice there is a definite
relationship. Partially
commutative , monotonic production systems are useful for solving ignorable
problems. These systems are important for man implementation standpoint
because they can be implemented without the ability to backtrack to previous
states, when it is discovered that an incorrect path was followed. Such
systems increase the efficiency since it is not necessary to keep track of
the changes made in the search process. Monotonic
partially commutative systems are useful for problems in which changes occur
but can be reversed and in which the order of operation is not critical (ex:
8 puzzle problem). Production
systems that are not partially commutative are useful for many problems in
which irreversible changes occur, such as chemical analysis. When dealing
with such systems, the order in which operations are performed is very
important and hence correct decisions have to be made at the first time
itself. .
|
|
Unit-01/Lecture-04 |
||||||||
|
Search techniques Search
techniques are general problem-solving methods. When there is a formulated
search problem, a set of states, a set of operators, an initial state, and a
goal criterion we can use search techniques to solve the problem. Breadth-First-Search (BFS) (Jun 2012) (i)
Place the
starting node ‘s’ on the queue (ii)
If the queue
is empty,failure and stop. (iii)
If the first
element on the queue is a goal node ‘g’,return success and stop.Otherwise. (iv)
Remove and
expand first element from the queu and Placed all the children at the end of
the queue at any order. (v)
Return to
step 2.
Depthth-First-Search (DFS) (Jun 2012) (i)
Place the starting
node ‘s’ on the queue (ii) If the queue is empty,failure and stop. (iii) If the first element on the queue is a goal node ‘g’,return
success and stop. Otherwise. (iv)
Remove and expand
first element from the queu and Placed all the children at the front of the
queue at any order. (v) Return to step
|
||||||||
|
|
|
Unit-01/Lecture-05 |
||||||||
|
hill-climbing search(Jun 2013) hill-climbing search simply evaluates
the objective function for all states that are neighbors to the current
state, and takes the neighbor state with the best objective function value as
the new current state. If there are more than one next best states, one is
picked randomly.
Hill-climbing search is sometimes called
greedy search, because a step
is taken after only considering the immediate neighbors. No time is spent
considering possible future states. Hill
Climbing - Algorithm 1
Pick a random point in the search space 2
Consider all the neighbors of the current state 3
Choose the neighbor with the best quality and move to that state 4
Repeat 2 thru 4 until all the neighboring states are of lower quality 5
Return the current state as the solution state Hill-climbing is easy to formulate
and implement and often finds pretty good states quickly. But, it has the
following problems: (i) it
gets stuck on local optima (hills for maximizing searches, valleys for
minimizing searches, (ii) it
may get stuck on a ridge, if no single action can advance the search along
the ridge, (iii) it
may get stuck wandering on a plateau for which all neighboring states have
equal value. Common variations include (i) allow
sideways moves (when on a plateau) (ii) stochastic
hill-climbing: choose next state with probability related to increase in
value of objective function (iii) first-choice
hill-climbing: generate neighbors by random choice of available actions and
keep first state that has better value, (iv) random-restart
hill climbing: conduct multiple hill-climbing searches from multiple,
randomly generated, initial states. All states will be tried as starting
states so the goal, or best state, will eventually be found.
|
|
Unit-01/Lecture-06 |
|
Best first search 1
Expand current node. (i) New nodes are called successor
nodes 2
Move current node to CLOSE
list 3
Calculate f(n) for successor
nodes 4
Add new nodes to OPEN
list (frontier) 5
Sorted by f(n); lowest cost
node is first 6
Current node = first node in
open list 7
Repeat (i)
Until current node = goal (ii)
Or open list is empty (fail)
|
|
Unit-01/Lecture-07 |
||||||||
|
A* ALGORITHM ( Jun 2013) A
Star algorithm is a best first graph search algorithm that finds a
least cost path from a given initial node to one goal node. Basic
Terminologies Used: Problem Space:The set of all
possible configurations is the space of problem states or the problem space. Keywords used: Functions used in the algorithm: Evaluation Function f(n):At any
node n,it estimates the sum of the
cost of the minimal cost path from the start node s to node n plus the cost
of a minimal cost path from node n to a goal node.
f(n)=g(n)+h(n) Where g(n)=cost of the path in the
search tree from s to n; h(n)=cost of the path in the
search tree from n to a goal node; Function f*(n): At any node n,it
is the actual cost of an optimal path from node s to node n plus the cost of an
optimal path from node n to a goal
node. f*(n)=g*(n)+h*(n) Where g*(n)=cost of the optimal path in the
search tree from s to n; h*(n)=cost of the optimal path
in the search tree from n to a goal node; h*(n):It is the cost of the minimal cost path from n
to a goal node and any path from node n to a goal node that acheives h*(n) is an optimal path from n to a goal. h is an estimate of h*. h(n) is calculated on
the heuristic information from the problem domain. A* ALGORITHM 1.
Create a search graph G, consisting solely of the
start node, no. Put no on a list called OPEN. 2.
Create a list called CLOSED that is initially empty. 3.
If OPEN is empty, exit with failure. 4.
Select the first node on OPEN, remove it from OPEN,
and put it on CLOSED. Called this node n. 5.
If n is a goal node, exit successfully with the
solution obtained by tracing a path along the pointers from n to no
in G. (The pointers define a search tree and are established in Step 7.) 6.
Expand node n, generating the set M, of its
successors that are not already ancestors of n in G. Install these members of
M as successors of n in G. 7.
Establish a pointer to n from each of those members
of M that were not already in G (i.e., not already on either OPEN or CLOSED).
Add these members of M to OPEN. For each member, m, of M that was already on
OPEN or CLOSED, redirect its pointer to n if the best path to m found so far
is through n. For each member of M already on CLOSED, redirect the pointers
of each of its descendants in G so that they point backward along the best
paths found so far to these descendants. 8.
Reorder the list OPEN in order of increasing f
values. (Ties among minimal f values are resolved in favor of the deepest
node in the search tree.) 9.
Go to Step 3.
|
|
Unit-01/Lecture-08 |
|
AO* ALGORITHM:
Compute h' (INIT). Until INIT is labeled
SOLVED or hi (INIT) becomes greater than FUTILITY, repeat the following
procedure. (I)
Trace the marked arcs from INIT and select an unbounded node NODE. (II)
Generate the successors of NODE . if there are no successors then
assign FUTILITY as h' (NODE). This
means that NODE is not solvable. If there are successors then for each
one called SUCCESSOR, that is not also an ancestor of NODE do the
following
(b) if successor is not a terminal node,
mark it solved and assign zero to its h ' value. (c) If successor is
not a terminal node, compute it h' value. (III) propagate the newly discovered information up the graph by doing
the following .let S be a set of nodes that have been marked SOLVED.
Initialize S to NODE. Until S is empty repeat the
following procedure; (a) select a node from S call
if CURRENT and remove it from S. (b) compute h' of each of the
arcs emerging from CURRENT , Assign
minimum h' to CURRENT. (c) Mark the minimum cost path
a s the best out of CURRENT. (d) Mark CURRENT SOLVED if all
of the nodes connected to it through
the new marked are have been labeled SOLVED. (e) If CURRENT has been marked SOLVED or its h '
has just changed, its new status must be propagate backwards up the graph . hence
all the ancestors of CURRENT are added to S. |
|
Unit-01/Lecture-09 |
||||||||
|
Knowledge
representation issues (Dec 2012) Knowledge is a progression that starts with data
which is of limited utility. By organizing or analyzing the data, we
understand what the data means, and this becomes information (i) The interpretation or evaluation of information
yield knowledge (ii) An understanding of the principles embodied within
the knowledge is wisdom Knowledge Progression
Fig. Knowledge progression Different types of knowledge require different kinds
of representation. The Knowledge Representation models/mechanisms are often based on v Logic v Rules v Frames v Semantic Net Different types of knowledge require
different kinds of reasoning Prepositional logic Logic is used to represent
properties of objects in the world about which we are going to reason. When
we say Miss Piggy is plump we are talking about the object Miss Piggy and a property
plump. Similarly when we say Kermit's voice is high-pitched then the object
is Kermit's voice and the property is high-pitched. predicate logic Predicate logic uses the
same connectives as propositional
logic but allows you to refer to
different elements of the universe. It also introduces quantifiers. Two
common quantifiers are the existential ∃ ("there
exists") and universal ∀ ("for all")
quantifiers. The variables could be elements in the universe under discussion, or perhaps
relations or functions over that universe
|
|
Unit-01/Lecture-10 |
||||||||||||
|
Monotonic Logic (Dec 2012) Formal logic is a set of rules for making deductions
that seem self evident. A Mathematical logic formalizes such deductions with
rules precise enough to program a
computer to decide if an argument is valid,representing objects and
relationships symbolically. Examples Predicate logic and the inferences we
perform on it. All humans are mortal. Socrates is a human.
Therefore Socrates is mortal. In monotonic reasoning if we enlarge at set of
axioms we cannot retract any existing assertions or axioms. (i) Most
formal logics have a monotonic
consequence relation, meaning
that adding a formula to a theory never produces a reduction of its
set of consequences. In other words, a
logic is monotonic if the truth of a proposition does not change when new
information (axioms) are added. The
traditional logic is monotonic. (ii) In mid
1970s, Marvin Minsky and John McCarthy pointed out that pure classical logic is not adequate to
represent the commonsense nature of
human reasoning. The reason is, the human reasoning is non-monotonic in nature. This means, we reach to conclusions from certain
premises that we would not reach if certain other sentences are included in
our premises. (iii) The
non-monotonic human reasoning is caused by the fact that our knowledge about the world is always
incomplete and therefore we are forced to reason in the absence of complete
information. Therefore we often revise our conclusions, when new information
becomes available. (iv) Thus,
the need for non-monotonic reasoning in AI was recognized, and several formalizations of non-monotonic
reasoning. Non-Monotonic
Logic (Dec 2012) Inadequacy of monotonic logic for reasoning is said
in the previous slide. A monotonic logic cannot handle : Reasoning by
default : because
consequences may be derived only because
of lack of evidence of the contrary. Abductive
reasoning : because consequences
are only deduced as most likely explanations. Belief
revision : because new
knowledge may contradict old beliefs. A non-monotonic logic is a formal logic whose
consequence relation is not monotonic. A logic is non-monotonic if the truth
of a proposition may change when new information (axioms) are added. (i) Allows a statement to be retracted. (ii) Used to formalize plausible (believable) reasoning. Example 1 : Birds typically fly. Tweety is a bird. -------------------------- Tweety (presumably) flies. (iii) Conclusion of non-monotonic argument may not be
correct. Example-2 : (Ref. Example-1) If Tweety is a penguin, it is incorrect to conclude
that Tweety flies. (Incorrect because, in example-1,default rules were
applied when case-specific information was not available.) (i) All non-monotonic reasoning are concerned with
consistency. Inconsistency is resolved, by removing the relevant
conclusion(s) derived by default rules, as shown in the example
below. Example -3 : The truth value (true or false), of propositions
such as "Tweety is a bird" accepts default that is normally true,
such as "Birds typically fly". Conclusions derived was "Tweety
flies". When an inconsistency is recognized, only the truth value of the
last type is changed
|
|
|
||||||||
|
Unit-01/Lecture-11 |
||||||||
|
Forward chaining Forward chaining is one of the two main methods of reasoning when
using an inference engine and can be described logically
as repeated application of modus ponens.
Forward chaining is a popular implementation strategy for expert systems,
business and production rule systems. The opposite of
forward chaining is backward chaining. Backward reasoning Backward chaining (or backward
reasoning) is an inference method that can be described (in lay terms) as
working backward from the goal(s). It is used in automated theorem provers, inference
engines, proof assistants and other artificial intelligence applications
Natural language processing Natural language
processing (NLP) is the ability of a computer program to understand human
speech as it is spoken. NLP is a component of artificial intelligence.Natural
language processing (NLP) is a field of computer science,
artificial intelligence, and linguistics
concerned with the interactions between computers
and human (natural) languages. As such, NLP is
related to the area of human–computer interaction. Many
challenges in NLP involve natural language understanding -- that
is, enabling computers to derive meaning from human or natural language
input. There are
three major aspects of any natural language understanding theory: Syntax The syntax
describes the form of the language. It is usually specified by a grammar.
Natural language is much more complicated than the formal languages used for
the artificial languages of logics and computer programs. Semantics The
semantics provides the meaning of the utterances or sentences of the
language. Although general semantic theories exist, when we build a natural
language understanding system for a particular application, we try to use the
simplest representation we can. For example, in the development that follows,
there is a fixed mapping between words and concepts in the knowledge base,
which is inappropriate for many domains but simplifies development. Pragmatics The pragmatic
component explains how the utterances relate to the world. To understand
language, an agent should consider more than the sentence; it has to take
into account the context of the sentence, the state of the world, the goals
of the speaker and the listener, special conventions, and the like. To
understand the difference among these aspects, consider the following
sentences, which might appear at the start of an AI textbook:
The first
sentence would be quite appropriate at the start of such a book; it is
syntactically, semantically, and pragmatically well formed. The second
sentence is syntactically and semantically well formed, but it would appear
very strange at the start of an AI book; it is thus not pragmatically well
formed for that context. The last two sentences are attributed to linguist
Noam Chomsky (1957).
The third sentence is syntactically well formed, but it is semantically non-sensical.
The fourth sentence is syntactically ill formed; it does not make any sense -
syntactically, semantically, or pragmatically. |
||||||||