Neural Networks Master’s Thesis by Prateeti Raj Thesis Supervisor Prof. Ashay Dharwadker 15th April 2004 Abstract This thesis is a survey of the field of Neural Networks. Various types of neural networks and learning algorithms are explained and demonstrated. In particular, the Perceptron, Hamming and Hopfield networks and their applications are described, and a detailed historical background is provided. The mathematical model of a Threshold Logic Unit and the problem of finding a linearly separable function that agrees with the desired training set is explored. Consequently, a calculus argument in the weight space allows us to derive the famous Widrow-Hoff delta rule using the zero-one step function and the Werbos generalized delta rule using the sigmoid function. We have implemented all of these neural networks and learning algorithms in C++ and provide the source code of the software under the GNU public license for noncommercial use on the accompanying CD. Contents 1. The Human Brain 2. History of Neural Networks 3. What is a Neural Network? 4. Learning in a Neural Network 5. A Simple Example of a Neural Network 6. Problem Statement 7. Perceptron 8. Pattern Recognition Problem 9. Programs 10. Hamming Network 11. Program on Hamming Network 12. Hopfield Networks 13. Widrow-Hoff Algorithm 14. Program using Widrow-Hoff Algorithm 15. Werbos Algorithm 16. Summary of Presentations Given 17. Applications of Neural Networks 18. References

Prof. Ashay Dharwadker's Courses (3):

Course	Semester	Grade	Add New Course
MS Project	Fall 2003	View	Update Course
Database Systems	Fall 2003	View	Update Course
Computer Networks	Spring 2004	View	Update Course

Projects (2)

The three sensors are then input to a neural network. The neural network will then decide which fruit is on the conveyer belt so that it can be directed to the correct storage bin. There are two kinds of fruits: apples & oranges.

Reference: What is a Neural Network?

I am stating the sql syntax used to create our relational database for Cricket Plus!

mysql>create database cricketplus;
mysql>use database cricketplus;
mysql>create table countries(country_name char(40) not null, uniform_color char(40), cricket_board char(40), famous_playgrounds char(40), world_cups_won integer);
mysql>create table cricket_players(player_id integer not null, player_name char(40), highest_score integer, average integer, no_of_centuries integer, no_of half_centuries integer, bowling_average integer, wickets_taken integer);
mysql>create table country_players(player_id char(40) not null, country_name char(40) not null, name char(40) not null, primary key(player_id, country_name), foreign key (country_name) references countries);

Seminars (2)

I also talked about my project and explained how the neural network will sort the apple & oranges. The exciting part of the seminar was that we found out that Turing Machines are actually Recurrent Neural Networks. I also talked about the various applications in which neural networks are used.

Research Notes (10)

• Feedforward Networks (perceptron)
• Competitive Networks (Hamming Network)
• Recurrent Associative Networks (Hopfield Network)

I have developed a program for the perceptron network and am trying to develop similar programs for the Hamming & Hopfield Networks.

LIKE 'pattern'
The pattern can contain wild card characters - % (percentage) and (underscore).

The % is used to denote any number of unknown characters and _ denotes one unknown character.

To denote more than one unknown character using _, the number of _ must be equal to the number of unknown characters.

• To retreive rows where the state name begins with K and followed by any other character. Example, KARNATAKA, KERALA
  

  SELECT FIRST_NAME, LAST_NAME, STATE
  FROM CUSTOMER WHERE STATE LIKE 'K%';
  

• To retreive rows where the first name contains the word RAJ embedded in it.
  Example, RAJESH, DEVRAJ, RAJESHWARI.

  SELECT FIRST_NAME, LAST_NAME, STATE
  FROM CUSTOMER WHERE FIRST_NAME LIKE '%RAJ%';

• To retreive rows where the ADD2 contains the word TEXAS or TEXIS in which the 3rd character may be anything. This is done using the underscore.

  SELECT FIRST_NAME, LAST_NAME, ADD2, STATE
  FROM CUSTOMER WHERE ADD2 LIKE 'TEX_S';
  

• ABS(data): Returns the absolute value of data (i.e. positive value).
  

  SQL>SELECT ABS(-5000) FROM DUAL;
  =5000
  

• CEIL(data): Returns the smallest integer greater than or equal to data.

  SQL>SELECT CEIL(123.55) FROM DUAL;
  =124
  

• FLOOR(data): Returns the largest integer less than or equal to data.

  SQL>SELECT FLOOR(123.55) FROM DUAL;
  =123
  

• LN(data): Returns the natural algorithm of data.
• LOG(b,data): Returns the base 'b' logarithm of data.
• MOD(data,Y): Returns the modulus of dividing data by Y.

  SQL>SELECT MOD(101,2) FROM DUAL;
  =1
  

• POWER(data,Y): Returns the data raised to the POWER of Y.

  SQL>SELECT POWER(2,4) FROM DUAL;
  =16
  

• ROUND(data,n): Where n is the number of decimal places to which the data is rounded.

  SQL>SELECT ROUND(123.55), ROUND(123.55,1)
  FROM DUAL;
  124                          123.6
  

• SQRT(data): Returns the square root of data.

  SQL>SELECT SQRT(64) FROM DUAL;
  =8
  

• TRUNC(data,n): Where n is the number of decimal places for truncation.

  SQL>SELECT TRUNC(123.55,0), TRUNC(123.55,1)
  FROM DUAL;
  123                 123.5
  

Views are logical tables of data extracted from existing tables. It can be queried just like a table, but does not require disk space. It can be thought of as either a virtual table or a stored query. Also the data accessible through a view is not stored in the database as a distinct object. What is stored in the database is a SELECT statement. The result set of the SELECT statement forms the virtual table returned by the view.

• It can be used to hide sensitive columns. To do this the owner of the view must grant the SELECT privilege on the view and revoke the privileges on the underlying tables.
• It can be used to hide complex queries involving multiple tables. Users need not concern with the syntax of complex queries.
• Views are created with a Check option, prevents the updating of other rows and columns.

Syntax: CREATE or REPLACE VIEW view-name AS query;
Example: CREATE VIEW EMP_VIEW AS
               SELECT emp_no, emp_name from emp;

Syntax:   SELECT * FROM VIEW_NAME;
Example: SELECT * FROM EMP_VIEW;

Syntax:    DESC VIEW_NAME;
Example:  DESC EMP_VIEW;

Syntax:    DROP VIEW VIEW-NAME;
Example: DROP VIEW EMP_VIEW;

• joins
• set operators (UNION, INTERSECT, MINUS)
• GROUP functions
• Group by Clause
• DISTINCT

CREATE OR REPLACE VIEW EMP AS
SELECT * FROM CUSTOMER
WHERE CITY = 'BANGALORE' WITH CHECK OPTION;

SQL>SELECT * FROM USER_VIEWS;

• Perceptron
  • Feedforward Network
  • Linear Decsion Boundary
  • One Neuron for Each Decision
• Hamming Network
• Competitive Network
• First Layer: Pattern Matching (Inner Product)
• Second Layer: Competition (Winner-Take-All) #Neuron=#Prototype Patterns
• Hopfield Network
• Dynamic Associative Memory Network
• Network Output Converges to a Prototype Pattern
• #Neurons=#Elements in each Prototype Pattern

I have developed the program for Hamming network and am studying Hopfield Networks currently.

I am also studying the research paper given by Ashay Sir which is very interesting.

f(x)=w1x1+w2x2+……………….+wnxn.

This function is a linearly separable function. For machines with only two actions 0,1 TLU’s suffice. For more complex actions 0,1,2 need a network of TLU’s which is called a Neural Network.

Example:

Inputs			Desired Output
X1=(x1+x2+……….+xn)	d1	
X2=(x1’+x2’+………..+xn’)	d2
.
.
.
.
Xk=(x1k+x2k+………..+xnk)	dk	

To find function “f” such that f(Xi)=di for i=0,1,2,3…….,k. Experimental evidence suggests that if the training set is “typical” then f will generate approximately correct response for all x. Frank Rosenblatt, Widrow and Hoff gave the following in 1962.

Weights W = (W1, W2,…….,WN)
Threshold theta (Assume theta =0)
X.W=X.W1+X2.W2+……..XN.WN
Input X = (x1,x2,…..,xn) 
Output  =   {1   if  X.W> theta
               0   if X.W<= theta

Start with arbitrary 		
W=(W1,W2….,WN)
(X=X1 In the training set)
Define error € = (f(x)-d)2
Define gradient d€/dw = (d€/dw1, d€/dw2,…..d€/dwn)
Define S=X.W
= ds/dw = x

     d€/dw = d€/ds.ds/dw => d€/ds.x
     But d€/ds = (f(x) – d) .df/ds
     So d€/dw = 2(f(x)-d)df/ds . x 

If f(x) = 1 =d => x.w=1
If f(x) = 0 = d => x.w = -1
Then f=s


€ = (f – d)2 => df/ds = 1

Step 1: Start with arbitrary w
Step 2: Replace w by w = (f-d)x Where c = learning rate parameter Repeat step 2 until w converges This is Widrow Hoff Algorithm

X=(1,1,0)
W=(0,0,0)
F(x)=1
w1.1+w2.1+w3.0 = 1
0.5(1) + 0.5 (1)+(0 or 1) 0 = 0.5+0.5+0=1

The output of the values will converge to 0.5 with the iterations from 0 to 0.5.

Generalized Delta Rule

Here Wi+1 = Wi + c(d-f).f(1-f)x Where f = 1/1+e-s(e to the power -s)

Alan Turing was the founder of computer science, mathematician, philosopher, code breaker and a visionary. He was born in 1912 (23 June) at Paddington, London. He studied at the Sherborne School, during 1926-31. He was then an undergraduate student at King’s College, Cambridge University during 1931-34. In 1935 he was elected Fellow of King’s College, Cambridge for his work in Quantum mechanics, probability and logic during 1932-35. Before the advent of the digital computer i.e. in the 1930's several mathematicians began to think about what it means to be able to compute a function. Turing's definitive contribution was the relation between logical instructions, the action of the mind, and a machine which could in principle be embodied in a practical physical form. Thus, in 1936, he contributed ‘The Turing machine, computability, universal machine’. At the same time American logician, Alonzo Church had also been working on the same and came with a parallel conclusion. It was seen, however that Turing's approach was original and different; Church relied upon an assumption internal to mathematics, rather than appealing to operations that could actually be done by real things or people in the physical world. Alonzo Church and Alan Turing independently arrived at equivalent conclusions. As we might phrase their common definition now:

What is a Turing Machine
Logically a Turing machine has all the power of any digital computer. Conceptually a Turing machine processes an infinite tape which is divided into squares, any square of which may contain a symbol from a finite alphabet, with the restriction that there can be only finitely many non-blank squares on the tape. At any time, the Turing machine has a read/write head positioned at some square on the tape. Furthermore, at any time, the Turing machine is in any one of a finite number of internal states. The Turing machine is further specified by a set of instructions of the following form:

Turing expanded this idea to show that there exists a "universal" Turing machine, a machine which can calculate any number and function, given the appropriate instructions. The set of instructions can be thought of as a program for the Turing machine. Turing’s Paper, On Computable Numbers was published near the end of 1936.This paper generated a lot of attention for him and the idea came to mathematician John Von Neumann. Turing obtained his Ph.D thesis through work that extended his original ideas i.e. during 1936-38 Turing also completed his Ph.D. in Logic, algebra, number theory at Princeton University.

It is found that Recurrent Neural Networks are actually equivalent to Turing Machines i.e. they can compute any algebraically computable function. Heikki Hyötyniemi of Helsinki University of Technology, Control Engineering Laboratory, Otakaari 5A, FIN-02150 Espoo, Finland has published a paper stating the same i.e. ‘Turing Machines are Recurrent Neural Networks’.

The class P informally is the class of decision problems that can be solved by some algorithms within a number of steps bounded by some fixed polynomial in the length of the input. We can get an exact solution to those problems within some reasonable amount of time. Such problems fall in class P where P stands for polynomial time complexity. Problems for which there is a polynomial time algorithm are called tractable. To define the problem in a precise way it is necessary to give a formal model of a computer. The Turing machine is the standard computer model in computability theory which was introduced by Alan Turing in 1936. The model was introduced before physical computers were built; but it still continues to be accepted as the proper computer model for the purpose of defining computable function.

NP Complete are the hardest problems in the class NP. Such problems are singled out because if at any point we find a deterministic polynomial time algorithm for one of them, all of the problems in NP must have deterministic polynomial time algorithms. Use of Neural Networks to solve P, NP, NP Hard and NP Complete problems

The Turing Machines can be used in computing P and NP problems. So the Recurrent Neural Networks can also be used for the same. However, both Hopfield and Recurrent Neural Networks are used for solving problems that deal with P and NP complexities.

The maximum clique problem (MCP) is a classic graph optimization problem with many real-world applications. This problem is NP-complete and computationally intractable even to approximate with certain absolute performance bounds. New discrete competitive Hopfield neural network for finding near-optimum solutions for the MCP are used. More information related to this topic can be obtained at the following address:
h ttp://portal.acm.org/citation.cfm?id=775532&dl=ACM&coll=GUIDE

Thus, Recurrent Neural Networks can be used for Universal Computation and Universal Approximation that is all places here Turing Machines can be used.

Universal Approximation: It means having the ability to approximate any function to an arbitrary degree of accuracy.
Universal Computation: It means the ability of computing anything that can be computed in principle, that is equivalent in computing power to a Turing machine, the lambda calculus, or a Post production system.