Intelligent search -General Problem Solving Approaches -• Heuristic Search o Heuristic Search for OR Graphs

Introduction

Intelligent search

Problem solving requires two prime considerations: first representation of the problem by an appropriately organized state space and then testing the existence of a well-defined goal state in that space. Identification of the goal state and determination of the optimal path, leading to the goal through one or more transitions from a given starting state, will be addressed in this chapter in sufficient details. The chapter, thus, starts with some well-known search algorithms, such as the depth first and the breadth first search, with special emphasis on their results of time and space complexity. It then gradually explores the 'heuristic search' algorithms, where the order of visiting the states in a search space is supported by thumb rules, called heuristics, and demonstrates their applications in complex problem solving. It also discusses some intelligent search algorithms for game playing.
Common experience reveals that a search problem is associated with two important issues: first 'what to search' and secondly 'where to search'. The first one is generally referred to as 'the key', while the second one is termed 'search space'. In AI the search space is generally referred to as a collection of states and is thus called state space. Unlike common search space, the state space in most of the problems in AI is not completely known, prior to solving the problem. So, solving a problem in AI calls for two phases: the generation of the space of states and the searching of the desired problem state in that space. Further, since the whole state space for a problem is quite large, generation of the whole space prior to search may cause a significant blockage of storage, leaving a little for the search part. To overcome this problem, the state space is expanded in steps and the desired state, called "the goal", is searched after each incremental expansion of the state space.
Depending on the methodology of expansion of the state space and consequently the order of visiting the states, search problems are differently named in AI. For example, consider the state space of a problem that takes the form of a tree. Now, if we search the goal along each breadth of the tree, starting from the root and continuing up to the largest depth, we call it breadth first search. On the other hand, we may sometimes search the goal along the largest depth of the tree, and move up only when further traversal along the depth is not possible. We then attempt to find alternative offspring of the parent of the node (state) last visited. If we visit the nodes of a tree using the above principles to search the goal, the traversal made is called depth first traversal and consequently the search strategy is called depth first search. We will shortly explore the above schemes of traversal in a search space. One important issue, however, needs mention at this stage. We may note that the order of traversal and hence search by breadth first or depth first manner is generally fixed by their algorithms. Thus once the search space, here the tree, is given, we know the order of traversal in the tree. Such types of traversal are generally called 'deterministic'. On the other hand, there exists an alternative type of search, where we cannot definitely say which node will be traversed next without computing the details in the algorithm. Further, we may have transition to one of many possible states with equal likelihood at an instance of the execution of the search algorithm. Such a type of search, where the order of traversal in the tree is not definite, is generally termed 'nondeterministic'. Most of the search problems in AI are non-deterministic.

General Problem Solving Approaches

There exist quite a large number of problem solving techniques in AI that rely on search. The simplest among them is the generate and test method. The algorithm for the generate and test method can be formally stated as follows:

• Procedure Generate & Test
• Begin
• Repeat
• Generate a new state and call it current-state;
• Until current-state = Goal;
• End.

It is clear from the above algorithm that the algorithm continues the possibility of exploring a new state in each iteration of the repeat-until loop and exits only when the current state is equal to the goal. Most important part in the algorithm is to generate a new state. This is not an easy task. If generation of new states is not feasible, the algorithm should be terminated. In our simple algorithm, we, however, did not include this intentionally to keep it simplified.
But how does one generate the states of a problem? To formalize this, we define a four tuple, called state space, denoted by
{ nodes, arc, goal, current },
where nodes represent the set of existing states in the search space; an arc denotes an operator applied to an existing state to cause transition to another state; goal denotes the desired state to be identified in the nodes; and current represents the state, now generated for matching with the goal.
We will now present two typical algorithms for generating the state
space for search. These are depth first search and breadth first search.

Breadth First Search

The breadth first search algorithm visits the nodes of the tree along its
breadth, starting from the level with depth 0 to the maximum depth. It can be
easily realized with a queue. For instance, consider the tree, given in figure.
Here, the nodes in the tree are traversed following their ascending ordered labels.

The order of traversal in a tree of depth 3 by breadth first manner. The algorithm for traversal in a tree by depth first manner can be presented with a queue as follows:

Procedure Breadth-first-search

Begin
• i) Place the starting node in a queue;
• ii) Repeat
• Delete queue to get the front element;
• If the front element of the queue = goal,
• return success and stop;
• Else do
• Begin
• insert the children of the front element,
• if exist, in any order at the rear end of
• the queue;
• End
• Until the queue is empty;
• End.

The breadth first search algorithm, presented above, rests on a simple principle. If the current node is not the goal add the offspring of the current in any order to the rear end of the queue and redefine the front element of the queue as the current. The algorithm terminates, when the goal is found.

First few steps of breadth first search on the tree of fig. Time Complexity
For the sake of analysis, we consider a tree of equal branching factor from each node = b and largest depth = d. Since the goal is not located within depth (d-1), the number of false search is given by

Further, the first state within the fringe nodes could be the goal. On the other hand, the goal could be the last visited node in the tree. Thus, on an average, the number of fringe nodes visited is given by

Consequently, the total number of nodes visited in an average case becomes

Since the time complexity is proportional to the number of nodes visited, therefore, the above expression gives a measure of time complexity.
Space Complexity
The maximum number of nodes will be placed in the queue, when the leftmost node at depth d is inspected for comparison with the goal. The queue length under this case becomes bd. The space complexity of the algorithm that depends on the queue length, in the worst case, thus, is of the order of bd. In order to reduce the space requirement, the generate and test algorithm is realized in an alternative manner, as presented below.

Depth First Search

The depth first search generates nodes and compares them with the goal along the largest depth of the tree and moves up to the parent of the last visited node, only when no further node can be generated below the last visited node. After moving up to the parent, the algorithm attempts to generate a new offspring of the parent node. The above principle is employed recursively to each node of a tree in a depth first search. One simple way to realize the recursion in the depth first search algorithm is to employ a stack. A stackbased realization of the depth first search algorithm is presented below.

Procedure Depth first search

Begin
• Push the starting node at the stack,
• pointed to by the stack-top;
• While stack is not empty do
• Begin
• Pop stack to get stack-top element;
• If stack-top element = goal, return
• success and stop
• Else push the children of the stack-top
• element in any order into the stack;
• End.
• End while;
• End.

Fig. A:Depth first search on a tree, where the node numbers denote the order of visiting that node.
In the above algorithm, a starting node is placed in the stack, the top of which is pointed to by the stack-top. For examining the node, it is popped out from the stack. If it is the goal, the algorithm terminates, else its children are pushed into the stack in any order. The process is continued until the stack is empty. The ascending order of nodes in fig. A represents its traversal on the tree by depth first manner. The contents of the stack at the first few iterations are illustrated below in fig. B. The arrowhead in the figure denotes the position of the stack-top.

Fig. B: A snapshot of the stack at the first few iterations.
Space Complexity
Maximum memory in depth first search is required, when we reach the largest depth at the first time. Assuming that each node has a branching factor b, when a node at depth d is examined, the number of nodes saved in memory are all the unexpanded nodes up to depth d plus the node being examined. Since at each level there are (b-1) unexpanded nodes, the total number of memory required = d (b -1) +1. Thus the space complexity of depth first search is a linear function of b, unlike breadth first search, where it is an exponential function of b. This, in fact, is the most useful aspect of the depth first search.
Time Complexity
If we find the goal at the leftmost position at depth d, then the number of nodes examined = (d +1). On the other hand, if we find the goal at the extreme right at depth d, then the number of nodes examined include all the nodes in the tree, which is

So, the total number of nodes examined in an average case

This is the average case time complexity of the depth first search algorithm. Since for large depth d, the depth first search requires quite a large runtime, an alternative way to solve the problem is by controlling the depth of the search tree. Such an algorithm, where the user mentions the initial depth cut-off at each iteration, is called an Iterative Deepening Depth First Search or simply an Iterative deepening search.

Iterative Deepening Search

When the initial depth cut-off is one, it generates only the root node and examines it. If the root node is not the goal, then depth cut-off is set to two and the tree up to depth 2 is generated using typical depth first search. Similarly, when the depth cut-off is set to m, the tree is constructed up to depth m by depth first search. One may thus wonder that in an iterative deepening search, one has to regenerate all the nodes excluding the fringe nodes at the current depth cut-off. Since the number of nodes generated by depth first search up to depth h is

the total number of nodes expanded in failing searches by an iterative deepening search will be

The last pass in the algorithm results in a successful node at depth d, the average time complexity of which by typical depth first search is given by

Thus the total average time complexity is given by

Consequently, the ratio of average time complexity of the iterative deepening search to depth first search is given by

The iterative deepening search thus does not take much extra time, when compared to the typical depth first search. The unnecessary expansion of the entire tree by depth first search, thus, can be avoided by iterative deepening. A formal algorithm of iterative deepening is presented below.

Procedure Iterative-deepening

• Begin
• 1. Set current depth cutoff =1;
• 2. Put the initial node into a stack, pointed to by stack-top;
• 3. While the stack is not empty and the depth is within the
• given depth cut-off do
• Begin
• Pop stack to get the stack-top element;
• if stack-top element = goal, return it and stop
• else push the children of the stack-top in any order
• into the stack;
• End.
• End While;
• 4. Increment the depth cut-off by 1 and repeat
• through step 2;
• End.

The breadth first, depth first and the iterative deepening search can be equally used for Generate and Test type algorithms. However, while the breadth first search requires an exponential amount of memory, the depth first search calls for memory proportional to the largest depth of the tree. The iterative deepening, on the other hand, has the advantage of searching in a depth first manner in an environment of controlled depth of the tree.

Hill Climbing

The 'generate and test' type of search algorithms presented above only expands the search space and examines the existence of the goal in that space. An alternative approach to solve the search problems is to employ a function f(x) that would give an estimate of the measure of distance of the goal from node x. After f(x) is evaluated at the possible initial nodes x, the nodes are sorted in ascending order of their functional values and pushed into a stack in the ascending order of their 'f' values. So, the stack-top element has the least f value. It is now popped out and compared with the goal. If the stack-top element is not the goal, then it is expanded and f is measured for each of its children. They are now sorted according to their ascending order of the functional values and then pushed into the stack. If the stack-top element is the goal, the algorithm exits; otherwise the process is continued until the stack becomes empty. Pushing the sorted nodes into the stack adds a depth first flavor to the present algorithm. The hill climbing algorithm is formally presented below.

Procedure Hill-Climbing

• Begin
• 1. Identify possible starting states and measure the distance (f) of their closeness with the goal node; Push them in a stack according to the ascending order of their f ;
• 2. Repeat
• Pop stack to get the stack-top element;
• If the stack-top element is the goal, announce it and exit
• Else push its children into the stack in the ascending order of their f values;
• Until the stack is empty;
• End.

Moving along a ridge in two steps (by two successive operators) in hill climbing.
The hill climbing algorithm too is not free from shortcomings. One common problem is trapping at local maxima at a foothill. When trapped at local maxima, the measure of f at all possible next legal states yield less promising values than the current state. A second drawback of the hill climbing is reaching a plateau. Once a state on a plateau is reached, all legal next states will also lie on this surface, making the search ineffective. A new algorithm, called simulated annealing, discussed below could easily solve the first two problems. Besides the above, another problem that too gives us trouble is the traversal along the ridge. A ridge (vide figure above) on many occasions leads to a local maxima. However, moving along the ridge is not possible by a single step due to non-availability of appropriate operators. A multiple step of movement is required to solve this problem.

Simulated Annealing

"Annealing" is a process of metal casting, where the metal is first melted at a high temperature beyond its melting point and then is allowed to cool down, until it returns to the solid form. Thus in the physical process of annealing, the hot material gradually loses energy and finally at one point of time reaches a state of minimum energy. A common observation reveals that most physical processes have transitions from higher to lower energy states, but there still remains a small probability that it may cross the valley of energy states [2] and move up to a energy state, higher than the energy state of the valley. The concept can be verified with a rolling ball. For instance, consider a rolling ball that falls from a higher (potential) energy state to a valley and then moves up to a little higher energy state (vide figure below). The probability of such

A rolling ball passes through a valley to a higher energy state.
transition to a higher energy state, however, is very small and is given by

where p is the probability of transition from a lower to a higher energy state, ΔE denotes a positive change in energy, K is the Boltzman constant and T is the temperature at the current thermal state. For small ΔE, p is higher than the value of p, for large ΔE. This follows intuitively, as w.r.t the example of ball movement, the probability of transition to a slightly higher state is more than the probability of transition to a very high state. An obvious question naturally arises: how to realize annealing in search? Readers, at this stage, would remember that the need for simulated annealing is to identify the direction of search, when the function f yields no better next states than the current state. Under this circumstance, ΔE is computed for all possible legal next states and p' is also evaluated for each such next state by the following formula:

A random number in the closed interval of [0,1] is then computed and p' is compared with the value of the random number. If p' is more, then it is selected for the next transition. The parameter T, also called temperature, is gradually decreased in the search program. The logic behind this is that as T decreases, p' too decreases, thereby allowing the algorithm to terminate at a stable state. The algorithm for simulated annealing is formally presented below.

Procedure Simulated Annealing

• Begin
• 1. Identify possible starting states and measure the distance (f) of their closeness with the goal; Push them in a stack according to the ascending order of their f ;
• 2. Repeat
• Pop stack to get stack-top element;
• If the stack-top element is the goal,
announce it and exit;
• Else do
• Begin
• a) generate children of the stack-top element N and compute f for each of them;
• b) If measure of f for at least one child of N is improving
• Then push those children into stack in ascending order of their f;
• c) If none of the children of N is better in f
• Then do
• Begin
• a) select any one of them randomly, compute its p' and test whether p' exceeds a randomly generated number in the interval [0,1]; If yes, select that state as the next state; If no, generate another alternative legal next state and test in this way until one move can be selected; Replace stack-top element by the selected move (state);
• b) Reduce T slightly; If the reduced value is negative, set it to zero;
• End;
• End.
• Until the stack is empty;
• End.

The algorithm is similar to hill climbing, if there always exists at least one better next state than the state, pointed to by the stack-top. If it fails, then the last begin-end bracketed part of the algorithm is invoked. This part corresponds to simulated annealing. It examines each legal next state one by one, whether the probability of occurrence of the state is higher than the random value in [0,1]. If the answer is yes, the state is selected, else the next possible state is examined. Hopefully, at least one state will be found whose probability of occurrence is larger than the randomly generated probability.
Another important point that we did not include in the algorithm is the process of computation of ΔE. It is computed by taking the difference of the value of f of the next state and that of the current (stack-top) state.
The third point to note is that T should be decreased once a new state with less promising value is selected. T is always kept non-negative. When T becomes zero, p' will be zero and thus the probability of transition to any other state will be zero.

Heuristic Search

This section is devoted to solve the search problem by a new technique, called heuristic search. The term "heuristics" stands for " thumb rules", i.e., rules which work successfully in many cases but its success is not guaranteed.
In fact, we would expand nodes by judiciously selecting the more promising nodes, where these nodes are identified by measuring their strength compared to their competitive counterparts with the help of specialized intuitive functions, called heuristic functions.
Heuristic search is generally employed for two distinct types of problems:
i) forward reasoning and
ii) backward reasoning.
We have already discussed that in a forward reasoning problem we move towards the goal state from a pre-defined starting state, while in a backward reasoning problem, we move towards the starting state from the given goal. The former class of search algorithms, when realized with heuristic functions, is generally called heuristic Search for OR-graphs or the Best First search Algorithms. It may be noted that the best first search is a class of algorithms, and depending on the variation of the performance measuring function it is differently named. One typical member of this class is the algorithm A*. On the other hand, the heuristic backward reasoning algorithms are generally called AND-OR graph search algorithms and one ideal member of this class of algorithms is the AO* algorithm. We will start this section with the best first search algorithm.

Heuristic Search for OR Graphs

Most of the forward reasoning problems can be represented by an OR-graph, where a node in the graph denotes a problem state and an arc represents an application of a rule to a current state to cause transition of states. When a number of rules are applicable to a current state, we could select a better state among the children as the next state. We remember that in hill climbing, we ordered the promising initial states in a sequence and examined the state occupying the beginning of the list. If it was a goal, the algorithm was terminated. But, if it was not the goal, it was replaced by its offsprings in any order at the beginning of the list. The hill climbing algorithm thus is not free from depth first flavor. In the best first search algorithm to be devised shortly, we start with a promising state and generate all its offsprings. The performance (fitness) of each of the nodes is then examined and the most promising node, based on its fitness, is selected for expansion. The most promising node is then expanded and the fitness of all the newborn children is measured. Now, instead of selecting only from the generated children, all the nodes having no children are examined and the most promising of these fringe nodes is selected for expansion. Thus unlike hill climbing, the best first search provides a scope of corrections, in case a wrong step has been selected earlier. This is the prime advantage of the best first search algorithm over hill climbing. The best first search algorithm is formally presented below.

Procedure Best-First-Search

• Begin
• 1. Identify possible starting states and measure the distance (f) of their closeness with the goal; Put them in a list L;
• 2. While L is not empty do
• Begin
• a) Identify the node n from L that has the minimum f; If there exist more than one node with minimum f, select any one of them (say, n) arbitrarily;
• b) If n is the goal Then return n along with the path from the starting node, and exit; Else remove n from L and add all the children of n to the list L, with their labeled paths from the starting node;
• End.
• End While;
• End.

As already pointed out, the best first search algorithm is a generic algorithm and requires many more extra features for its efficient realization. For instance, how we can define f is not explicitly mentioned in the algorithm. Further, what happens if an offspring of the current node is not a fringe node. The A* algorithm to be discussed shortly is a complete realization of the best first algorithm that takes into account these issues in detail. The following definitions, however, are required for presenting the A* algorithm. These are in order.
Definition: A node is called open if the node has been generated and the h' (x) has been applied over it but it has not been expanded yet.
Definition: A node is called closed if it has been expanded for generating offsprings.
In order to measure the goodness of a node in A* algorithm, we require two cost functions: i) heuristic cost and ii) generation cost. The heuristic cost measures the distance of the current node x with respect to the goal and is denoted by h(x). The cost of generating a node x, denoted by g(x), on the other hand measures the distance of node x with respect to the starting node in the graph. The total cost function at node x, denoted by f(x), is the sum of g(x) plus h(x).
The generation cost g(x) can be measured easily as we generate node x through a few state transitions. For instance, if node x was generated from the starting node through m state transitions, the cost g(x) will be proportional to m (or simply m). But how does one evaluate the h(x)? It may be recollected that h(x) is the cost yet to be spent to reach the goal from the current node x. Obviously, any cost we assign as h(x) is through prediction.
The predicted cost for h(x) is generally denoted by h’(x). Consequently, the predicted total cost is denoted by f’(x), where
f ’(x) = g(x) + h’ (x).
Now, we shall present the A* algorithm formally.

Procedure A*

• Begin
• 1. Put a new node n to the set of open nodes (hereafter open); Measure its f'(n) = g(n) + h' (n); Presume the set of closed nodes to be a null set initially;
• 2. While open is not empty do
• Begin
• If n is the goal, stop and return n and the path of n from the beginning node to n through back pointers;
• Else do
• Begin
• a) remove n from open and put it under closed;
• b) generate the children of n;
• c) If all of them are new (i.e., do not exist in the graph before generating them Then add them to open and label their f' and the path from the root node through back pointers;
• d) If one or more children of n already existed as open nodes in the graph before their generation Then those children must have multiple parents; Under this circumstance compute their f' through current path and compare it through their old paths, and keep them connected only through the shortest path from the starting node and label the back pointer from the children of n to their parent, if such pointers do not exist;
• e) If one or more children of n already existed as closed nodes before generation of them, then they too must have multiple parents; Under this circumstance, find the shortest path from the starting node, i.e., the path (may be current or old) through which f' of n is minimum; If the current path is selected, then the nodes in the sub-tree rooted at the corresponding child of n should have revised f' as the g' for many of the nodes in that sub-tree changed; Label the back pointer from the children of n to their parent, if such pointers do not exist;
• End.
• End.
• End While;
• End.

To illustrate the computation of f' (x) at the nodes of a given tree or graph, let us consider a forward reasoning problem, say the water-jug problem, discussed in chapter 3. The state-space for such problems is often referred to as OR graphs / trees. The production rules we would use here are identical with those in chapter 3, considered for the above problem.
Example: Let us consider the following heuristic function, where X and Y denote the content of 4-liter and 3-liter jugs respectively and x denotes an arbitrary node in the search space.
h’ (x) = 2, when 0 < X < 4 AND 0 < Y < 3,
= 4, when 0 < X < 4 OR 0 < Y < 3,
=10, when i) X = 0 AND Y = 0
OR ii) X = 4 AND Y = 3
= 8, when i) X = 0 AND Y = 3
OR ii) X =4 AND Y = 0
Assume that g(x) at the root node = 0 and g(x) at a node x with
minimum distance n, measured by counting the parent nodes of each node
starting from x till the root node, is estimated to be g(x) = n. Now let us
illustrate the strategy of the best first search in an informal manner using the
water-jug problem, vide figure.

Fig.: Expanding the state-space by the A* algorithm.
Another important issue that needs to be discussed is how to select a path,when an offspring of a currently expanded node is an already existing node. Under this circumstance, the parent that yields a lower value of g+h' for the offspring node is chosen and the other parent is ignored, sometimes by de-linking the corresponding arc from that parent to the offspring node.

Multi-layer feed-forward networks, Delta Rule, Understanding backpropagation

Multi-layer feed-forward networks, Delta Rule, Understanding backpropagation

Introduction

A single-layer network has severe restrictions: the class of tasks that can be accomplished is very limited. In this chapter we will focus on feed-forward networks with layers of processing units. Minsky and Papert (Minsky & Papert, 1969) showed in 1969 that a two layer feed-forward network can overcome many restrictions, but did not present a solution to the problem of how to adjust the weights from input to hidden units. An answer to this question was presented by Rumelhart, Hinton and Williams in 1986 (Rumelhart, Hinton, & Williams, 1986), and similar solutions appeared to have been published earlier (Werbos, 1974; Parker, 1985; Cun, 1985). The central idea behind this solution is that the errors for the units of the hidden layer are determined by back-propagating the errors of the units of the output layer. For this reason the method is often called the back-propagation learning rule. Back-propagation can also be considered as a generalisation of the delta rule for non-linear activation functions1 and multilayer networks.

Multi-layer feed-forward networks

A feed-forward network has a layered structure. Each layer consists of units which receive their input from units from a layer directly below and send their output to units in a layer directly above the unit. There are no connections within a layer. The Ni inputs are fed into the
first layer of Nh;1 hidden units. The input units are merely 'fan-out' units; no processing takes place in these units. The activation of a hidden unit is a function Fi of the weighted inputs plus a bias, as given in in eq

The output of the hidden units is distributed over the next layer of Nh;2 hidden units, until the last layer of hidden units, of which the outputs are fed into a layer of No output units .

Although backpropagation can be applied to networks with any number of layers, just as for networks with binary units it has been shown (Hornik, Stinchcombe, & White, 1989; Funahashi, 1989; Cybenko, 1989; Hartman, Keeler, & Kowalski, 1990) that only one layer of hidden units su
ces to approximate any function with finitely many discontinuities to arbitrary precision, provided the activation functions of the hidden units are non-linear (the universal approximation theorem). In most applications a feed-forward network with a single layer of hidden units is used with a sigmoid activation function for the units.

Delta Rule

Since we are now using units with nonlinear activation functions, we have to generalise the delta rule:
The activation is a differentiable function of the total input, given by
in whichTo get the correct generalisation of the delta rule as presented in the previous chapter, we must set
The error measure Ep is defined as the total quadratic error for pattern p at the output units:
where dpo is the desired output for unit o when pattern p is clamped. We further set as the summed squared error. We can write
By equation we see that the second factor is When we define we will get an update rule which is equivalent to the delta rule as described in the previous chapter, resulting in a gradient descent on the error surface if we make the weight changes according to:The trick is to figure out what δp k should be for each unit k in the network. The interesting result, which we now derive, is that there is a simple recursive computation of these δ's which can be implemented by propagating error signals backward through the network.
To compute δp k we apply the chain rule to write this partial derivative as the product of two factors, one factor reflecting the change in error as a function of the output of the unit and one re ecting the change in the output as a function of changes in the input. Thus, we have

Let us compute the second factor. By equation we see that which is the same result as we obtained with the standard delta rule. Substituting this and equation in equation , we get
for any output unit o. Secondly, if k is not an output unit but a hidden unit k = h, we do not readily know the contribution of the unit to the output error of the network. However, the error measure can be written as a function of the net inputs from hidden to output layer; Ep = Ep(sp 1,sp 2,....... sp j.....) and we use the chain rule to write

Substituting this in equation yields
Equations and give a recursive procedure for computing the δ's for all units in
the network, which are then used to compute the weight changes according to equation.
This procedure constitutes the generalised delta rule for a feed-forward network of non-linear
units.

Understanding backpropagation

The equations derived in the previous section may be mathematically correct, but what do they actually mean? Is there a way of understanding back-propagation other than reciting the necessary equations? The answer is, of course, yes. In fact, the whole back-propagation process is intuitively very clear. What happens in the above equations is the following. When a learning pattern is clamped, the activation values are propagated to the output units, and the actual network output is compared with the desired output values, we usually end up with an error in each of the output units. Let's call this error eo for a particular output unit o. We have to bring eo to zero The simplest method to do this is the greedy method: we strive to change the connections in the neural network in such a way that, next time around, the error eo will be zero for this particular pattern. We know from the delta rule that, in order to reduce an error, we have to adapt its incoming weights according to.

That's step one. But it alone is not enough: when we only apply this rule, the weights from input to hidden units are never changed, and we do not have the full representational power of the feed-forward network as promised by the universal approximation theorem. In order to adapt the weights from input to hidden units, we again want to apply the delta rule. In this case, however, we do not have a value for δ for the hidden units. This is solved by the chain rule which does the following: distribute the error of an output unit o to all the hidden units that is it connected to, weighted by this connection. Differently put, a hidden unit h receives a delta from each output unit o equal to the delta of that output unit weighted with (= multiplied by) the weight of the connection between those units.

Working with back-propagation

The application of the generalised delta rule thus involves two phases: During the first phase the input x is presented and propagated forward through the network to compute the output values yp o for each output unit. This output is compared with its desired value do, resulting in an error signal δp o for each output unit. The second phase involves a backward pass through the network during which the error signal is passed to each unit in the network and appropriate weight changes are calculated.
Weight adjustments with sigmoid activation function.

• The weight of a connection is adjusted by an amount proportional to the product of an error signal δ, on the unit k receiving the input and the output of the unit j sending this signal along the connection:
• If the unit is an output unit, the error signal is given by Take as the activation function F the 'sigmoid' function as definedIn this case the derivative is equal to

such that the error signal for an output unit can be written as:

• The error signal for a hidden unit is determined recursively in terms of error signals of the
  units to which it directly connects and the weights of those connections. For the sigmoid
  activation function:

Learning rate and momentum
The learning procedure requires that the change in weight is proportional to True gradient descent requires that in
nitesimal steps are taken. The
constant of proportionality is the learning rate . For practical purposes we choose a learning rate that is as large as possible without leading to oscillation. One way to avoid oscillation at large , is to make the change in weight dependent of the past weight change by adding a momentum term:
where t indexes the presentation number and F is a constant which determines the efect of the previous weight change.
Although, theoretically, the back-propagation algorithm performs gradient descent on the total error only if the weights are adjusted after the full set of learning patterns has been presented, more often than not the learning rule is applied to each pattern separately, i.e., a pattern p is applied, Ep is calculated, and the weights are adapted (p = 1, 2,..... P). There exists empirical indication that this results in faster convergence. Care has to be taken, however, with the order in which the patterns are taught. For example, when using the same sequence over and over again the network may become focused on the
rst few patterns. This problem can be overcome by using a permuted training method.

Introduction to Genetic Aalgorithms

Introduction

Professor John Holland in 1975 proposed an attractive class of computational models, called Genetic Algorithms (GA), that mimic the biological evolution process for solving problems in a wide domain. The mechanisms under GA have been analyzed and explained later by Goldberg, De Jong, Davis, Muehlenbein, Chakraborti, Fogel, Vose and many others. Genetic Aalgorithms has three major applications, namely, intelligent search, optimization and machine learning. Currently, Genetic Algorithms is used along with neural networks and fuzzy logic for solving more complex problems. Because of their joint usage in many problems, these together are often referred to by a generic name: “;soft-computing”. A Genetic Algorithms operates through a simple cycle of stages:

• i) Creation of a “;population” of strings,
• ii) Evaluation of each string,
• iii) Selection of best strings and
• iv) Genetic manipulation to create new population of strings.

The cycle of a Genetic Algorithms is presented below

Each cycle in Genetic Algorithms produces a new generation of possible solutions for a given problem. In the first phase, an initial population, describing representatives of the potential solution, is created to initiate the search process. The elements of the population are encoded into bit-strings, called chromosomes. The performance of the strings, often called fitness, is then evaluated with the help of some functions, representing the constraints of the problem. Depending on the fitness of the chromosomes, they are selected for a subsequent genetic manipulation process. It should be noted that the selection process is mainly responsible for assuring survival of the best-fit individuals. After selection of the population strings is over, the genetic manipulation process consisting of two steps is carried out. In the first step, the crossover operation that recombines the bits (genes) of each two selected strings (chromosomes) is executed. Various types of crossover operators are found in the literature. The single point and two points crossover operations are illustrated
. The crossover points of any two chromosomes are selected randomly. The second step in the genetic manipulation process is termed mutation, where the bits at one or more randomly selected positions of the chromosomes are altered. The mutation process helps to overcome trapping at local maxima. The offsprings produced by the genetic manipulation process are the next population to be evaluated.

Fig.: Mutation of a chromosome at the 5th bit position.

Example: The Genetic Algorithms cycle is illustrated in this example for maximizing a function f(x) = x2 in the interval 0 = x = 31. In this example the fitness function is f (x) itself. The larger is the functional value, the better is the fitness of the string. In this example, we start with 4 initial strings. The fitness value of the strings and the percentage fitness of the total are estimated in Table A. Since fitness of the second string is large, we select 2 copies of the second string and one each for the first and fourth string in the mating pool. The selection of the partners in the mating pool is also done randomly. Here in table B, we selected partner of string 1 to be the 2-nd string and partner of 4-th string to be the 2nd string. The crossover points for the first-second and second-fourth strings have been selected after o-th and 2-nd bit positions respectively in table B. The second generation of the population without mutation in the first generation is presented in table C.
Table A:
Table B:

Table C:

A Schema (or schemata in plural form) / hyperplane or similarity template is a genetic pattern with fixed values of 1 or 0 at some designated bit positions. For example, S = 01?1??1 is a 7-bit schema with fixed values at 4-bits and don't care values, represented by ?, at the remaining 3 positions. Since 4 positions matter for this schema, we say that the schema contains 4 genes.

Fuzzy Logic

A fuzzy logic system is unique, because is able to simultaneously handle numerical data and linguistic knowledge. It is a non linear mapping of an input data vector into a scalar output i.e. it maps' numbers into numbers.

Fuzzy Logic Definition

Fuzzy logic means inexact reasoning, data granulation, computing with words and so on.
Haziness is always present in any realistic process. This vagueness may come up from the analysis of the data inputs and in the directives used to describe the relationships between the informative attributes. Fuzzy logic grants an inference structure that allows the human reasoning capacities to be applied to artificial knowledge-based structures. Fuzzy logic gives a means for adapting linguistic strategy into control actions and thus offers a high-level computation.
A definition of fuzzy logic systems set mathematical determination to the emulation of certain perceptual and lingual attributes related with human cognition, where the science of neural networks provides a new computing tool with learning and adaptation capabilities. The theory of fuzzy logic gives an inference method under cognitive uncertainty, computational neural networks, fuzzy logic offer exciting benefits such as learning, adaptation, fault tolerance, parallelism, and generalization.
In the literary texts sources, we can find different kinds of explanation for fuzzy systems theory. Human knowledge these days becomes more and more important – we increase it from living through the world after only which we live and use our capability to reason to create an order in the mass of information (i.e., to formulate human knowledge in a organized manner). As we are all limited in our ability to perceive the world and to deep reasoning, we find ourselves everywhere faced by uncertainty that is a result of lack of information, in particular, miscalculation of measurements.
The other restriction factor in our request for precision is a natural language used for describing/sharing knowledge, communication, etc. We understand core meanings of word and are able to communicate without error to an adequate degree, but generally we cannot precisely agree among ourselves on the singular word or terms of communal sense meaning. In other words, ordinary languages are unclear.
Our impression of the real world is pervaded by concepts, which do not have severely defined boundaries – for example, many, tall, much larger than,young, etc. are true only to some degree, and they are false to some extent as well. These concepts can be called fuzzy or vague concepts – a human brain works with them, while computers may not do it (they reason with strings of 0s and 1s). Natural languages, which are much higher in level than programming languages, are fuzzy, while programming languages are not. The door to the development of fuzzy computers was opened in 1985 by the design of the first logic chip by Masaki Togai and Hiroyuki Watanabe at Bell Telephone Laboratories. In the years to come fuzzy computers will employ both fuzzy hardware and fuzzy software, and they will be much closer in structure to the human brain than the present-day computers are.
The Fuzzy Logic tool was introduced in 1965 by Lotfi Zadeh. It is a mathematical tool for dealing with uncertainty. It offers to a software computing system the important concept of computing with words’. It grants a technique to deal with vagueness and information granularity. The fuzzy theory provides a mechanism for representing linguistic constructs such as “many,” “low,” “medium,” “often,” “few.”
Basically, the fuzzy logic provides an inference organization that enables proper human reasoning capabilities that machines do not have. In the other hand, the traditional binary set theory describes crisp events, events that have two options: one or zero. It uses probability theory to explain whether an event is about to happen, measuring the chance with which a given event is expected to come about. The premise of fuzzy logic is based leading the concept of relative graded connection and so are the functions of awareness and cognitive processes.
It is important to keep in mind that there is a close connection between Fuzziness and Complexity. As the complexity of a task, or of a system for performing that task, exceeds a certain limit, the system must unavoidably become fuzzy in nature. Zadeh, initially an engineer and systems scientist, was concerned with the fast turn down in information afforded by common mathematical models as the complexity of the target system increased.
As he stressed, with the increasing of complexity our skill to make accurate and yet major statements about its behavior diminishes. Real world problems are too complex, and the difficulty involves thedegree of vagueness – as uncertainty increases, so does the involvedness of the problem. Habitual system modeling and analysis techniques are too precise for such problems, and in order to make complexity less daunting we set up appropriate simplifications, assumptions, etc. to accomplish a reasonable compromise between the information we have and the amount of uncertainty we are willing to accept. In this aspect, fuzzy systems theory is similar to other engineering theories, because almost all of them describe the real world in an approximate manner.
Engineers define fuzzy logic as a useful tool with diverse applications; especially on solving problems that linear computing is not able to do. A good example of this functionality is the capability for image recognition, since human brain is capable to distinguish an object from an image even if is blur, meanwhile linear computing is able to read just pixels as set of colors. There is an analog factor: vagueness, images may have fuzzy maps.
Fuzzy sets grants means to model the ambiguity associated with vagueness, imprecision, and lack of information concerning a dilemma or a plant, etc. Consider the significance of a “short person.” For an entity X, the short person may be one whose height is below 4.20. For another individual Y, the short person may be one whose height is beneath or equal to 3.9. This “short” is called as a linguistic descriptor. The term “short” informs the same meaning to the individuals X and Y, but it is establish that they both do not supply a unique definition. The term “short” would be conveyed successfully, only when a computer compares the given height value with the pre-assigned value of “short.” This variable “short” is called as linguistic variable, which represents the elusiveness existing in the system.

What is Digital Signal Processing?

What is Digital Signal Processing?

Digital signal processing is the newest technology in the tech world. It is not as new as the iPod but enough for being a young discipline in different areas such as electronics and computing. Digital Signal Processing a.k.a. (DSP) is widely used in the world as many technologies depend of their algorithms.
Digital signal processing has many applications being the core goals measuring, filtering and compressing real analog signals. These kinds of algorithms depend widely on other systems such as ADC (analog to digital converter) and DAC (digital to analog converter).
Common fields in DSP include audio analysis,speech recognition, sonar, radar processing, spectral estimation, digital image processing, signal processing for communications, control of systems and much more.
DSP algorithms are time consuming for common processors. Therefore, they are widely used on special hardware commonly named as digital signal processors. These are application-specific integrated circuits specifically designed to carry out tasks with improved timing. Nowadays, we can find even more technologies, which are used in the field signal processing including more powerful microprocessors, field-programmable gate arrays (FPGAs), digital signal controllers or commonly know has micro controllers and others.

Learning Digital Signal Processing algorithms

In the field of DSP, it is studied digital signals intodifferent ways: signals in time domain or known as one-dimensional signals, spatial domain (signals with several layers, frequency domain, autocorrelation domain and wavelet domain. It is common to transform each signal to another domain. For example, the most common transformation made in DSP is from the time domain to frequency. This can be done using the Fourier transform and the Fast Fourier transforms.

Implementing DSP Algorithms

As a mentioned before, DSP is often implemented in specialized hardware, which greatly improves fixed-point arithmetic and floating point arithmetic being the last a lot more powerful. For faster applications, it used the FPGA. During the beginning of 2007, multicore implementations of DSPs have emerged. These new features allow even more tasks thus allowing more complex technologies.
I have to mention that DSP is not only limited to specialized hardware. It is also widely used on software applications. For example, Adobe Photoshop uses this technology for their image processing functions. DAW systems or digital audio stations use DSP algorithms as well for all related to audio processing.

Relationship with AI and neural networks

DSP and artificial neural networks are widely related. Both algorithms and implementations can be used for signal processing. Furthermore, these new technologies help each other for proper functioning. For example, it is common to “clean” the input of a neural network with DSP algorithms.