Artificial Neural Networks
In the human brain, nerve cells are connected to other nerve cells via strands of fiber (neurons and axons, respectively). Modeled after the human brain, artificial neural networks (ANNs) incorporates attempts to incorporate a similar system to developing solutions. Analogous to the synapse (the connection between a dendrite and an axon) in the brain where the brain alters the strength of the synaptic connection between neurons, ANNs reduces this process to changing the weights of the input nodes; this is called a perceptron.
In the simplest case, a perceptron consists of:
- Multiple input nodes, for the sources of stimuli
- A single output node to represent the model output
- A weighted link, which models the aforementioned synaptic connection
The output node essentially takes the weighted sum of all the inputs, reduced by a bias term. The final output will depending on the sign of the result (referred to as the activation function).
Figure 1. A simple perceptron, where Σ is the weighted sum, _Γ is the bias term and T is the activation function.
A simple algorithm for getting the perceptron to learn is provided only for completeness:
Perceptron Learning Algorithm:
1. Let D = {(xi , yi) | i = 1, … N} the training set
2. Initialize weight vector w/ random values
3. For each set of x,y in training set,
a. Find predicted output ŷk
b. For each weight wj
i. Use weight formula
4. Stop when condition met
As is to be expected, this neural network can be made extremely complicated. One or multiple hidden layers can be placed between the input and output nodes. If the nodes in any given layer are only connected to nodes in the next layer, this neural network is considered to be a feed-forward neural network.
The following code is an implementation of a neural network with the larger focus on begin able to distinguish spam based on the content of an email.
# Python Implementation of ANN
from math import tanh
from pysqlite2 import dbapi2 as sqlite
def dtanh(y):
return 1.0-y*y
class searchnet:
def __init__(self,dbname):
self.con=sqlite.connect(dbname)
def __del__(self):
self.con.close()
def maketables(self):
self.con.execute('create table hiddennode(create_key)')
self.con.execute('create table wordhidden(fromid,toid,strength)')
self.con.execute('create table hiddenurl(fromid,toid,strength)')
self.con.commit()
# Calculates current strength of connection
# since new connections only created when necessary, method most return default value if no connections made
# negative values used as default so extra words have slightly negative effect on acitvation level
def getstrength(self,fromid,toid,layer):
if layer==0:
table='wordhidden'
else:
table='hiddenurl'
res=self.con.execute(
'select strength from %s where fromid=%d and toid=%d' %
(table,fromid,toid)).fetchone()
if res==None:
if layer==0: return -0.2
if layer==1: return 0
return res[0]
# determine if connection already exists & to update/create connection w/ new strength
# trains network
def setstrength(self,fromid,toid,layer,strength):
if layer==0:
table='wordhidden'
else:
table='hiddenurl'
res=self.con.execute('select rowid from %s where fromid=%d and toid=%d' %
(table,fromid,toid)).fetchone()
if res==None:
self.con.execute('insert into %s (fromid,toid,strength) values (%d,%d,%f)' %
(table,fromid,toid,strength))
else:
rowid=res[0]
self.con.execute('update %s set strength=%f where rowid=%d' %
(table,strength,rowid))
# creates new node in hidden layer every time it's passed a combo of words not seen together previously
# default-weighted link b/w words & hidden node & b/w query node & url results
def generatehiddennode(self,wordids,urls):
if len(wordids)>3:
return None
# Check if we already created a node for this set of words
createkey='_'.join(sorted([str(wi) for wi in wordids]))
res=self.con.execute("select rowid from hiddennode where create_key='%s'" %
createkey).fetchone()
# If not, create it
if res==None:
cur=self.con.execute("insert into hiddennode (create_key) values ('%s')" %
createkey)
hiddenid = cur.lastrowid
# Put in some default weights
for wordid in wordids:
self.setstrength(wordid, hiddenid, 0, 1.0/len(wordids))
for urlid in urls:
self.setstrength(hiddenid,urlid,1,0.1)
self.con.commit()
# find all nodes form hidden layer relevant to specifc query (must be connected to 1 of words in query or to 1 of url in results)
# since other nodes not used to determine an outcome or train network, don't include
def getallhiddenids(self,wordids,urlids):
l1={}
for wordid in wordids:
cur=self.con.execute('select toid from wordhidden where fromid=%d' % wordid)
for row in cur:
l1[row[0]] = 1
for urlid in urlids:
cur=self.con.execute('select fromid from hiddenurl where toid=%d' % urlid)
for row in cur:
l1[row[0]]=1
return l1.keys()
# sets instance variables for class - list of words, query nodes, urls, output level per node & weights of link b/w nodes
def setupnetwork(self,wordids,urlids):
# value lists
self.wordids=wordids
self.hiddenids=self.getallhiddenids(wordids,urlids)
self.urlids=urlids
# node outputs
self.ai = [1.0]*len(self.wordids)
self.ah = [1.0]*len(self.hiddenids)
self.ao = [1.0]*len(self.urlids)
# create weights matrix
self.wi = [[self.getstrength(wordid,hiddenid,0) for hiddenid in self.hiddenids]
for wordid in self.wordids]
self.wo = [[self.getstrength(hiddenid,urlid,1) for urlid in self.urlids]
for hiddenid in self.hiddenids]
# takes list of inputs, push through network, & return output of all nodes in outputl layer
def feedforward(self):
# the only inputs are the query words
for i in range(len(self.wordids)):
self.ai[i] = 1.0
# hidden activations
for j in range(len(self.hiddenids)):
sum = 0.0
for i in range(len(self.wordids)):
sum = sum + self.ai[i] * self.wi[i][j]
self.ah[j] = tanh(sum)
# output activations
for k in range(len(self.urlids)):
sum = 0.0
for j in range(len(self.hiddenids)):
sum = sum + self.ah[j] * self.wo[j][k]
self.ao[k] = tanh(sum)
return self.ao[:]
# get output for a set of words & urls
def getresult(self,wordids,urlids):
self.setupnetwork(wordids,urlids)
return self.feedforward()
# backprop alg:
# 1. calc diff b/w node's current output & what it should be
# 2. use dtanh to find how much the node's total input has to change
# 3. change strength of every incoming link in proportion to link's current strengh
#
# for each node in hidden layer
# 1. change output of node by sum of strength of each output link * how much its target node has to change
# 2,3 see above
def backPropagate(self, targets, N=0.5):
# step 1
# calculate errors for output
output_deltas = [0.0] * len(self.urlids)
for k in range(len(self.urlids)):
error = targets[k]-self.ao[k]
# step 2
output_deltas[k] = dtanh(self.ao[k]) * error
# step 1 for nodes in hidden layer
# calculate errors for hidden layer
hidden_deltas = [0.0] * len(self.hiddenids)
for j in range(len(self.hiddenids)):
error = 0.0
for k in range(len(self.urlids)):
error = error + output_deltas[k]*self.wo[j][k]
# step 2 for nodes in hidden layer
hidden_deltas[j] = dtanh(self.ah[j]) * error
# step 3
# update output weights
for j in range(len(self.hiddenids)):
for k in range(len(self.urlids)):
change = output_deltas[k]*self.ah[j]
self.wo[j][k] = self.wo[j][k] + N*change
# update input weights
for i in range(len(self.wordids)):
for j in range(len(self.hiddenids)):
change = hidden_deltas[j]*self.ai[i]
self.wi[i][j] = self.wi[i][j] + N*change
# setup network, run feedforward & backpropogation
def trainquery(self,wordids,urlids,selectedurl):
# generate a hidden node if necessary
self.generatehiddennode(wordids,urlids)
self.setupnetwork(wordids,urlids)
self.feedforward()
targets=[0.0]*len(urlids)
targets[urlids.index(selectedurl)]=1.0
error = self.backPropagate(targets)
self.updatedatabase()
# save results via updating database w/ new weights (wi.wo)
def updatedatabase(self):
# set them to database values
# for input weights...
for i in range(len(self.wordids)):
for j in range(len(self.hiddenids)):
self.setstrength(self.wordids[i],self. hiddenids[j],0,self.wi[i][j])
# for output weights...(
for j in range(len(self.hiddenids)):
for k in range(len(self.urlids)):
self.setstrength(self.hiddenids[j],self.urlids[k],1,self.wo[j][k])
self.con.commit()
References
The previous content is based on Chapter 4 of the following book:Segaran, Toby. Programming Collective Intelligence: Building Smart Web 2.0 Applications. Sebastopol, CA: O'Reilly Media, 2007.