HEBBIAN LEARNING::::::THE TEACHER OF A NEURON:::::::

HEBBIAN BREEZE::::

The development of various methodologies to train a neuron have a significant place in the history of learning algorithms used by  neurons to produce good neuron citizens for the artificial intelligence community. Hebbian learning is one of the most primitive form of learning. It is widely accepted as a supervised learning and also a small community included it in the unsupervised learning..

My first encounter to hebbian learning methodologies ended in a mischap of all of its basic concepts. But timely intervention of good friends and Lecturers made me clear to a good extent about the concept of training a neuron, what learning is etc...

For instance of hebbian learning adaptation we can use iris data set. In the case of iris data set it we have 3 groups. They are Iris-virginica, Iris-versicolor, Iris-setosa. As human beings if we had given all the parts of each group of flower we will naturally starts learning to identify the parts of each flower. We will keep an eye on certain parts of the flower especially the inflorescence or petal colour etc. At last as the time period over we will be put into a test, in which we have to select a flower of right group with all kinds of combination tests. Either we have to identify flower group from  petal colour or group the given flower into the right group etc.

The whole phenomenon was copied and abstracted on  a single neuron. Here we have to become a neuron. As we all know all the sense organs of an abstract neuron are the inputs that got from external environment in the form of numbers(normalised values). We have to look certain inputs with at most affection(weights). We have to be trained with the data set of each group for estimating the final weights of required group(updating the weights with hebbian equation). Thus we learned to identify the 'flowers' (can group successfully into matched group).

The whole process of hebbian learning is a systematic one that each data set have to be trained seaparately and store final updated  weights for reference. This final updated weights are the keypoints in identifying the missing properties to some extent. ie with desired output and weights we are able to get the missing input value. It will be closed to some values predefined as inputs. Thats how we say that a neuron is learned to identify the group to some extent by performing a comparison with the desired output. 

ARTIFICIAL INTELLIGENCE::AWSOME ABSTRACTION OF HUMAN BRAIN

Artificial intelligence is one of the most reforming branches of computer science. When man starts thinking about how his own brain works, how can he adopt the features of brain to solve most complicated problems, artificial intelligence emerges. In-fact many eminent researchers with their outstanding inventions, found out numerous models of human thought process. 

Computational intelligence, Artificial neural networks, Design of neurons, ganglia etc are the most challenging tasks that happening at the  back-end of all these research.

Most of the neural network studies starts with the study of biological neurons, which are the major component of human brain where amazing mind blogging mysteries are happening. We have to wonder and with wide open eyes to believe that these neurons are cells which carry more than gigabytes of informations about various learning process  right from a human beings' birth. It is the place where all information exchanges are happening. If neuron has this much importance in our life, its better to fold our hands and give a worshipful respect to the creator of all these structures at this moment..

Most classification algorithms with neurons include perceptron model, alpha-LMS, steepest descent, Back-propagation etc. The perceptron model includes the training of a neuron with the inputs from external environment with a specialized weights given to each of these inputs. Clearly when we remap perceptron to our daily routine, it can be visualized as a process when we starts learning a new environment.

In this process of learning we will naturally give more importance to certain inputs and we will constantly observing these inputs in course of our learning. Similar thing happens in the training of perceptron training. In each iteration we will update the importance of certain inputs by improving their weights also give unimportance to certain weights by the process of weight updation. There are different systematic ways to do this critical process. It can be alpha-LMS approach, Back-propagation, Steepest descent etc. Each of these methods have their own merits and demerits. These demerits are the pointers to further research in this area. 

One simple classification problem using perceptron is described below. The matlab  simulation code also included which contains weight updation process done with perceptron approach as well as alpha-LMS.

The problem is that we have to design a neuron using perceptron approach and also with alpha-LMS which can distinguish between two triangles located on either side of a line. The output is the final weights that we will give to each input pattern and inputs are the various points of training. It is assumed that the expected output if 1 if the point is above the line and the expected output is 0 when the point is below the line. The image of the problem specification is shown above.


The matlab code for perceptron learning and alpha-LMS is shown below. If we execute the code we will be getting weights at which the neuron is to be ready to classify the points whether it is above or below the line.

The perceptron code:
 
p = [1 2 2
    1 2 .75
    1 2.25 .75
    1 2.75 .75
    1 2.125 .75
    1 3 .75
    1 3.25 .75
    1 3.5 .75
    1 4 .75
    1 2.25 .5
    1 2.5 .25
    1 2.75 0
    1 3 -.25
    1 3.25 -.25
    1 4 .25
    1 1 1
    1 1.125 1
    1 1.25 1
    1 1.25 1
    1 1.5 1
    1 2 1
    1 2.25 1
    1 2.5 1
    1 2.75 1
    1 3 1
    1 1.25 1.25
    1 1.5 .5
    1 1.75 1.75
    1 2 2
    1 2.25 1.75
    1 2.5 1.5
    1 2.75 .5
    1 3 1
    1 2.125 1.75];
d = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];
w = [0 0 0];
eta = 1;
update = 1;
while update == 1
    for i=1:34
        y = p(i,:)*w';
        if y>=0 & d(i) == 0
            w = w-eta*p(i,:);
            up(i) = 1;
        elseif y<=0 & d(i) ==1
            w = w + eta*p(i,:);
            up(i) = 1;
        else
            up(i) = 0;
        end
    end
    numberofupdates = up * up' ;
    if numberofupdates > 0
        update = 1;
    else
        update = 0;
    end
end

The alpha-LMS code :

p = [1 2 2
    1 2 .75
    1 2.25 .75
    1 2.75 .75
    1 2.125 .75
    1 3 .75
    1 3.25 .75
    1 3.5 .75
    1 4 .75
    1 2.25 .5
    1 2.5 .25
    1 2.75 0
    1 3 -.25
    1 3.25 -.25
    1 4 .25
    1 1 1
    1 1.125 1
    1 1.25 1
    1 1.25 1
    1 1.5 1
    1 2 1
    1 2.25 1
    1 2.5 1
    1 2.75 1
    1 3 1
    1 1.25 1.25
    1 1.5 .5
    1 1.75 1.75
    1 2 2
    1 2.25 1.75
    1 2.5 1.5
    1 2.75 .5
    1 3 1
    1 2.125 1.75];
d = [0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1];
w = [0 0 0];
eta = 1;
update = 1;
 while update == 1
     for i=1:34
         y = p(i,:)*w';
         ek = d(i) - y;
         pi = p(i,:);
         pi = pi/(norm(pi)^2)
         w = w + 1*ek*pi;
         if y>=0 & d(i) == 0
%             w = w-eta*p(i,:);
             up(i) = 1;
        elseif y<=0 & d(i) ==1
%             w = w + eta*p(i,:);
             up(i) = 1;
        else
             up(i) = 0;
        end
     end
     numberofupdates = up * up' ;
     if numberofupdates > 0
         update = 1;
     else
         update = 0;
     end
 end
The above views are according to the descriptions from the book of neural networks by Dr. sathish Kumar and subject to change in-case, any error in the conepts and the pointers to errors are most welcome.

ACKERMANN RECURSION MYSTERY

RECURSION   is one of the beautiful techniques of programming. Instead of repeating the whole code, several programmers are using this technique in their programs. But using recursion is not a good programming methods, since it will consume memory space and other resources. There are large number of problems in computer science which depends upon the recursion for their result. Some of them are Fibanocci numbers, Factorial, Towers of Hanoi problem, N-queens problem, DFS,BFS, most of the tree and graph related problems etc.

ACKERMANN function is a problem which works using the principles of recursion, especially tail recursion. The peculiarity of the function is that the output will be obtained for the small values very rapidly and if the input values exceed one particular number then the function behaves like an algorithm which never comes up with the answer. The tracing of the function for small values can be done with ease effort. The function is described as follows

                                              A(m,n) =   n + 1 ,                         if    m=0;
                                                            =   A(m-1,1),                  if    n=0;
                                                            =   A(m-1, A(m, n-1))   otherwise;


The values m and n must be greater than or equal to zero. If we execute this program with the values A(3,2) we will get 29. similarly if A(3,3) we will get 61. If we go beyond 4 or 5 it will take large amount of time, Sometimes years!!!!!!!!!!!!!. In that condition the complexity of the program as explained in some books looks like


                                                               .....
                                                             .... 
                                                           2
                                                         2
                                                       2


A slope of 2's arranged one above the other..

Ackermanns function is a typical example of tail recursion.. Some people may say as a joke that running complex recursive algorithms are worth enough  for giving training to the processors...

UNROLLING "DFS" :: THE SLOWEST APPROACH

DFS: Depth First Search is the most familiar graph traversal method which is used in large number of searching application. A graph traversal is a systematic procedure of visiting all the nodes. The basic data structure for the DFS is stack. And we implement the procedures using the basic elements of programming.

Beyond all these implementation details, these methods convey various other concepts. Some of them are described below.
1. E-Node.
2. L-Node.
3. D-Node.
4. Discovery time.
5. Departure time.

Sometimes while programming we didn't pay attention to these stuffs. But they can provide a great information, when we extend the algorithms for solving the network related issues.

E-NODE ( Expanding or Exploring)

Node which is currently being explored or whose children is being generated is E-Node. There can be only one E-Node at a time during the traversal.

L-NODE (Live Node)

The node which has not been fully explored or all of the two children has not been generated is live node. There can be many number of live nodes during the traversal.

D-NODE(Dead Node)

The node which is not explored or all of its children has been generated is Dead Node.

TWO TIME CONCEPTS:

DISCOVERY TIME:

It is the time when we discover a particular node.

DEPARTURE TIME:

It is the time when we leave a node after exploring all the children

We usually say DFS as multiple DFS, because E-Node can be started from any node.

The unrolling of DFS can be visualised by the following graph


 The working of the DFS algorithm based on the concepts of the nodes and times is as follows. Starting from the node 1. At time 1 we discovered the node numbered 1. At present the E-NODE is node 1. From the first node we have two possibilities. Either we can go for the 2nd or 3rd. For the time being we are going to discover the node numbered 2. At the moment we reach the node 2, node 1 will become the live node and node 2 will becomes the E node. Similarly the discovery time of the node 2 is 2. From 2nd node we can go to either 4 or 5. We are going to the 4th node correspondingly the node 2 will becomes the LIVE-NODE and node 4 will becomes the E-NODE. The discovery time is 3. Similarly we are going to other nodes in the sequence from the 4th node is as follows  4--8--7--3--6---. The corresponding discovery times is in the sequence 3--4--5--6--7. And the nodes except the 6th node will become the live node. The sixth node will becomes the E-NODE. The sixth node is devoid of any children which is unexplored. So the first departure takes place at the sixth node. The departure time is 8. we will return form the sixth node to the previous node. and it will become dead. On reaching the node 3 , there also no children remained unexplored. So returns to node number 7. and the node 3 will becomes dead. The departing time from the node 3 is 9. On reaching the node 7 the same process will happens. The departing time is 10. On reaching the node 8, Checks for any unexplored child. Here node 5 is unexplored. So the discovery time of the node 5 is 11...and the process is continues...The Whole process will come to an end when all the nodes of the graph becomes dead nodes..

The data structure view of these process shows the usage of stack for tracking the path. When a node becomes a live node, that node will be pushed in to the stack. When ever a node becomes a dead node, It will be popped from the stack. The whole process will comes to an end when the stack is empty.

There is another method called DFT. We usually DFS and DFT unknowingly at different places. There is a crucial difference between these two. DFT( Depth First Traversal) is  used on a FOREST. It is used for traversing when the graph is disjointed or disconnected. DFS using the strategy of backtracking, it is used to know whether a graph is connected or not , Verifying whether a node is reachable and finding the articulation points in the graph, which is very essential in solving network related problems..

Thats all the story of DFS..............................................................................................

The emergence of P and NP

P :   " This is the set of all decision problems solvable by deterministic algorithms in polynomial time "
NP: " This is the set of all decision problems solvable by non- deterministic algorithms in polynomial time "

Since Deterministic algorithms are special case of Non deterministic ones, We conclude that P C NP.

COOKS THEOREM:

Cooks  theorem is better known as cooks question. Is there any single problem in NP such that if it is showed to be in P then it would imply that P=NP ?  also


Satisfiability is in P iff P=NP
 

Maximum Clique -----"MAX --CLIQUE" Problem

This problem is one of the most familiar problem in computer science. The maximal complete subgraph of a graph G is a clique. The size of the clique is  the number of vertices in it. The max-clique problem is that finding the largest possible clique in the graph.

There is another definition for the clique. A clique is a set of vertices from the original graph G in which every vertex in the set have an edge with any other vertex in the set.

This is an optimisation problem. But it can be viewed in the angles of decision problem in the following way.

Does the graph can have a clique of size 6 ---NO
Does the graph can have a clique of size 5 ---NO
Does the graph can have a clique of size 4 ---yes

Thus the maximum clique has the size of 4.

Similarly satisfiablity problem, Node cover problem
etc are viewed in this way.

The mirage of NP, P and Co-NP conepts in computer science

The concepts of NP, P, and Co-NP problems were always confusing. Even during the engineering studies, after referring the most famous "fat" book "Design and Analysis of Algorithms" amble times the idea will not be impregnated in the mind. While reading the book, at one point of the peak all the concepts will clash at last we will have the condition that Co-NP is P? or will NP become P? etc. When I went to the ACE engineering academy eminent professors made me clear what exactly is happening between the P, NP, Co-NP.  The ideas are sharing here.

Before thinking of the NP, P, Co-NP we must be aware of the basic facts about the deterministic and non deterministic algorithms, Decision problems, Optimization problems, Reducibility, Polynomial-Equivalence properties etc.

The great division  of problems 

Basically computer science problems are broadly classified into two categories.

• Decidable problems

• Undecidable problems  

Decidable problems are the problems having algorithms. They are also divided into two categories. Deterministic and Non-deterministic algorithms. The basic differentiation in this way is based on the acceptance of the problems by a Deterministic Turing machine and Non - deterministic Turing machine.
Deterministic algorithms are again divided into polynomial time and exponential time algorithms.Polynomial time algorithms are the ones that can be solved in polynomial time complexity(O(n), O(n^2) etc). Exponential time algorithms are the ones that can be solved in exponential time complexity.(2^n, 3^n etc).

Non-deterministic algorithms are also divided in the same fashion as that of deterministic algorithms.

Why the problems are categorised into NP, NP-Hard, NP-complete, P?

The basic essence in the classification of the problems is that to show that the various problems in Computer Science are related. So in future if any scientist or researcher found out that a particular problem belong to any of these categories he can also prove that the other related problems are also belongs to the same category.

Non deterministic algorithms : First tool for the Analysis.

Every decidable problems have a non-deterministic algorithms. Determinism reveals that output is distinct. Non determinism shows that there can be more than one output for the input. Non deterministic algorithm  have basically two steps. Success and failure. Success signal is generated when the algorithm is successfully completed. Its complexity is O(1). Similarly failure is the signal generated when the algorithm fails. The interesting fact of these nondeterministic algorithms is that they are theoretical.

An example for the non-deterministic algorithm for searching.

 procedure nd_search(A[], n, x)
    {
       j = choice(i,n);
       if(A[j]==x)
         {
            write[j];
             success();
          }
        else
             failure(); 
     }

The above algorithm is a search algorithm which uses only  O(1)  time for its execution and it will returns the index of the searched element in the array of size n. The explanation is like this:  The above algorithm has a function called choice(1,n). The main job of this function is that it will returns the index of the searched element with O(1) complexity.!!! Naturally we may rise the question, How this is possible, even the fastest searching deterministic algorithm will takes at least log n  complexity? The answer to this question is very interesting. If a system have to return the index of the searched element atonce, that element have to be compared with every other element in the array at once. It can be done by using sufficient number of processors which compares the searched element with consecutive elements in the array parallely. If this can be done then it is possible to return the index of the searched element in O(1) time complexity. But this method is not practical. To arrange as much as processors as that of the array size is tedious and immaterial. So it is not possible. But our focus is on the nondeterministic algorithm. Thus every decidable problems have a nondeterministic algorithm. And it will be much faster than the deterministic one.
                                                
Decision Vs Optimization problems in computer science.

Any problem which has an output either YES (TRUE)or NO(FALSE)  is known as decision problem. Finding an optimal value for the criteria described in the problem ( It can be either minimum or maximum) belongs to the Optimisation problems. Every decision and optimization problems are interchangeable. Some of the examples of decision problems are N-Queens, Hamiltonian Cycle problem (Does there exists a cycle connecting all the vertices's exactly once) etc. The examples of Optimization problems include 0/1 Knapsack problem(minimum weight and maximum profit), Travelling sales man problem, Graph colouring problem ( minimum number of colours needed to mark all the vertices's differently.) etc. Interesting fact about these type of problems is that they can be converted to either of each other. The examples include the conversion of 0/1 knapsack optimisation problem into 0/1 knapsack decision problem by looking the problem in another way. Is it possible to get filled up the knapsack to get  maximum profit? the answer will be yes or no. Similarly, Is it possible to color a graph say with four adjacent vertices with two colours? NO, with three colours? NO, with four colours? YES. In computer science there are many standard problems that can be interchangeable between these two extremities. Some of them are max- clique, Satisfiability problem, Node cover problem  etc.