Weak & Strong Slot & filler structures, NLP.

 forward Reasoning, backward reasoning, 

monotonic and non monotonic reasoning,

Prepositional and predicate logic

Knowledge representation issues

 AO* Algorithms and various types of control strategies.

A* Algorithm

 A* algorithm,

A^* search is a combination of lowest-cost-first and best-first searches that considers both path cost and heuristic information in its selection of which path to expand. For each path on the frontier, A^* uses an estimate of the total path cost from a start node to a goal node constrained to start along that path. It uses cost(p), the cost of the path found, as well as the heuristic function h(p), the estimated path cost from the end of p to the goal.

For any path p on the frontier, define f(p)=cost(p)+h(p). This is an estimate of the total path cost to follow path p then go to a goal node.

n  Evaluation function f(n) = g(n) + h(n)

n  g(n) = cost so far to reach n

n  h(n) = estimated cost from n to goal

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

n  Best First search has f(n)=h(n)

n  Uniform Cost search has f(n)=g(n)

Example :: A* Algorithm 
Romania with step costs in km

Open List:

Arad

We start with our initial state Arad.  We make a node and add it to the open list.  Since it’s the only thing on the open list, we expand the node.

Think of the open list as a priority queue (or heap) that sorts the nodes inside of it according to their   g()+h()   score.

Open List: 

Sibiu

Timisoara

Zerind

We add the three nodes we found to the open list. 

We sort them according to the    g()+h()    calculation.

Open List:

Rimricu Vicea

Fagaras

Timisoara

Zerind

Arad                     (We’ve been to Arad before.  Don’t list it again on the open list.)

Oradea 

When we expand Sibiu, we run into Arad again.  But we’ve already expanded this node once; so, we don’t add it to the open list again.

Open List:

Rimricu Vicea

Fagaras

Timisoara

Zerind

Oradea

We see that Rimricu Vicea is at the top of the open list; so, it’s the next node we will expand.

Open List:

Fagaras

Pitesti

Timisoara

Zerind

Craiova

Sibiu

Oradea

When we expand Rimricu Vicea, we run into Sibiu again. 

But we’ve already expanded this node once; so, we don’t add it to the open list again.

Open List:

Fagaras

Pitesti

Timisoara

Zerind

Craiova

Oradea

Fagaras will be the next node we should expand – it’s at the top of the sorted open list.

Open List:

Pitesti

Timisoara

Zerind

Bucharest

Craiova

Sibiu

Oradea

When we expand Fagaras, we find Sibiu again.  We don’t add it to the open list.

We also find Bucharest, but we’re not done.  The algorithm doesn’t end until we “expand” the goal node – it has to be at the top of the open list.

Open List:

Pitesti

Timisoara

Zerind

Bucharest

Craiova

Oradea

It looks like Pitesti is the next node we should expand.

Open List:

Bucharest

Timisoara

Zerind

Craiova

Rimricu Vicea

Oradea

We just found a better value for Bucharest; so, it got moved higher in the list.  We also found a worse value for Craiova – we just ignore this.

And of course, we ran into Rimricu Vicea again.  Since it’s already been expanded once, we don’t re-add it to the Open List. 

Open List:

Bucharest

Timisoara

Zerind

Craiova

Oradea 

Now it looks like Bucharest is at the top of the open list…

Open List:

Bucharest

Timisoara

Zerind

Craiova

Oradea 

Now we “expand” the node for Bucharest. 

We’re done!   (And we know the path that we’ve found is optimal.)

Best First Search

Best first Search

Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.

Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function  which, in general, may depend on the description of n, the description of the goal, the information gathered by the search up to that point, and most important, on any extra knowledge about the problem domain.

Some authors have used "best-first search" to refer specifically to a search with a heuristic that attempts to predict how close the end of a path is to a solution, so that paths which are judged to be closer to a solution are extended first. This specific type of search is called greedy best-first search or pure heuristic search.

Efficient selection of the current best candidate for extension is typically implemented using a priority queue.

other Search Techniques like hill Climbing, 

Depth First Search Techniques

How do we search a graph?
At a particular vertices, where shall we go next?
Two common framework:  

• the depth-first search (DFS)
• the breadth-first search (BFS) and 

In DFS, go as far as possible along a single path until reach a dead end (a vertex with no edge out or no neighbor unexplored) then backtrack
In BFS, one explore a graph level by level away (explore all neighbors first and then move on)

Color Scheme

• Vertices initially colored white
• Then colored gray when discovered
• Then black when finished

Time Stamp

• Discover time d[u]:  when u is first discovered 
• Finish time f[u]: when backtrack from u
• d[u] < f[u]

Application 

• Topological Sort
• Strongly Connected Component

Breadth First Search

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

BFS was invented in the late 1950s by E. F. Moore, who used it to find the shortest path out of a maze, and discovered independently by C. 

• Search for all vertices  that are directly reachable from the root (called level 1 vertices)
• After mark all these vertices, visit all vertices that are directly reachable from any level 1 vertices (called level 2 vertices), and so on.
• In general, level k vertices are directly reachable from a level k – 1 vertices

1. White vertices have not been discovered ( All vertices start out white )
2. Grey vertices are discovered but not fully explored ( They may be adjacent to white vertices)
3. Black vertices are discovered and fully explored (They are adjacent only to black and gray vertices)
4. Explore vertices by scanning adjacency list of grey vertices

Applications:
Breadth-first search can be used to solve many problems in graph theory, for example:

• Copying garbage collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v (with path length measured by number of edges)
• Testing a graph for bipartiteness 
• (Reverse) Cuthill–McKee mesh numbering
• Ford–Fulkerson method for computing the maximum flow in a flow network
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• Construction of the failure function of the Aho-Corasick pattern matcher.

Characteristics of Production Systems

Production system:

Production system is useful to structure AI programs in a way that is facilitates describing and performing the search process.  Don’t confuse of the word production such as to describe is done in factories.

•            A production system is consist of a set of rules. Left side (a pattern) that determines the applicability of the rule and right side that describes the operation to be performed if the rule is applied.
•           One or more knowledge / data bases that contain whatever information is appropriate for the particular task. 
•       A control strategy that specifies the order in which the rules will be compared to the database and way of resolving the conflict that arise when several rules match at once.
•        A rule applier. 

1    Requirements of a good control strategy:
                 How to decide which rule is apply is next during the process of searching for a solution to a problem  

• The first requirement is that it can cause motion: Consider the water jug problem. Suppose we implemented the simple control strategy of starting each time at the top of the list of rules and choosing the first applicable one.
•  The second requirement is that it be systematic: The requirement that a control strategy be systematic corresponds to the need for global motion as well as for local motion.

Production System Characteristics:

We have argued that production systems are a good way to describe the operations that can be performed in a search for a solution to a problem.

•  Can production systems, like problems, be described by a set of characteristics that shed some light on how they can easily be implemented?
•  If  so,  what relationships are  there  between  problem  types and the types  of  production  system  best suited  to solving the problems?

Artificial Intelligence : Introduction , Various types of production systems

Introduction of Artificial Intelligence :

Artificial intelligence (AI) is the intelligence exhibited by machines or software. It is also the name of the academic field of study which studies how to create computers and computer software that are capable of intelligent behavior. Major AI researchers and textbooks define this field as "the study and design of intelligent agents", in which an intelligent agent is a system that perceives its environment and takes actions that maximize its chances of success.

Various types of production systems:

Various Types of Soft Computing Techniques and Application of Soft Computing

Various types of soft computing techniques: 
Soft computing consist several computing paradigms  mainly are :

• Neural Network
• Fuzzy Logic
• Genetic Algorithm    

Application of Soft Computing:

• A Fusion Approach of Multi spectral Images with SAR (Synthetic Aperture Radar).
• Optimization of traveling Salesman Problem using Genetic Algorithm Approach.
• Genetic algorithm base Internet search technique.
• Hybrid fuzzy Controllers based on Soft Computing.
• Rocket Engine control based on Soft Computing.
• Architectural design and development of new approaches combining fuzzy logic, neural networks, evolutionary computation, and other recent computational intelligence methods in the SC paradigm.
• Comparative theoretical and empirical studies on SC techniques, with validation through convincing computational experiments, performance measures, and convergence proof.
• Application of SC techniques (e.g., big data, smart systems, semantic web, sustainable development, cloud computing, dynamic processes, and other domains in science and engineering)

   

Soft Computing vs. Hard Computing

Soft Computing	Hard Computing
Soft Computing is tolerant of imprecision, uncertainty, partial truth and approximation	Hard Computing requires a precisely state analytic model
Soft Computing is based on fuzzy logic, neural sets, and probabilistic reasoning	Hard Computing is based on binary logic, crisp system, numerical analysis and crisp software.
Soft computing has the characteristics of approximation and disposition	Hard computing has the characteristics of precision and category
Soft computing can evolve its own programs	Hard computing requires programs to be written
Soft computing can use multi-valued or fuzzy logic	Hard computing uses two-valued logic
Soft computing incorporates stochasticity	Hard computing is deterministic
Soft computing can yield approximate answers	Hard computing produces precise answers
Soft computing allows parallel computations	Hard computing is strictly sequential
Soft computing can deal with ambiguous and noisy data	Hard computing requires exact input data
Soft computing can deal with Approximate Models like Approximate reasoning , Functional Approximation and randomized search	Hard computing requires precise models like Symbolic logic reasoning , Traditional numerical modeling and search

What is Soft Computing

What is Soft Computing : Introduction of soft computing

Definition of Soft Computing :: Lotfi. A. Zadeh 1992   " Soft computing is an emerging approach to computing which parallel the remarkable ability of the human mind to reason and learn in a environment of uncertainty and imprecision"

Aim of Soft computing :it is differs from conventional (hard) computing. Its aim is to exploit tolerant of imprecision, uncertainty, partial truth and approximation.

Imprecision:  Here the model feature are not the same as  the real ones but close to them. 
Partial Truth: Hear the model feature are near about real ones. 
Uncertainty : Hear we are not sure that the feature of model are the same as that of the entity.
Approximation : Hear the model feature are similar the real ones but not same.

Soft computing is to develop intelligent machine and provide solution of real world problem which is difficulty to model mathematically.
Soft Computing is not a combination or mixture rather soft computing  is a partnership in which each of the partners contributes or share a distinct methodology for addressing problem in its domain.

Soft computing = Evolutionary Computing + Neural Network  + Fuzzy Logic.

Evolutionary Computing = Genetic Programming + Genetic Algorithm + Evolutionary Programming + Evolution Strategy