Introduction to AI - Week 4

Neural Networks

• They are inspired by nature. The human mental capabilities are generated by the brain, which can be viewed as a large set of neurons (10¹⁰ to 10¹¹ many), each connected to around 10³ to 10⁴ many others.
• Unlike to expert systems or decision trees neural nets do not make use of an explicit symbolic representation.
• Each individual neuron behaves in a very simple way.

A Neuron

A Neuron (Cont'd)

• A neuron receives inputs from other neurons, x₁,x₂,... ,x_n, which are weighted by weights w₁,w₂,... ,w_n.
• In the simplest model, a neuron takes its weighted inputs and sums them up
  S=sum_iⁿw_i* x_i.
• Then it checks whether the sum is above a given threshold
  S>= Threshold.
• If yes, it sends out the value 1 (excitatory).
• If not, it sends out the value -1 (inhibitory).

Building a Neural Net

• a set of input neurons, a set of output neurons, and a set of hidden neurons,
• a set of directed links which connect two neurons each,
• a set of weights (for each link one).

In the simple case, which we will consider in the following, the set of input neurons, the set of output neurons, and the set of hidden neurons are given. Furthermore the topology is given, that is, the programmer has fixed initially which neuron is connected to which others.

The weights have to be learned.

A Perceptron

• If the desired output and the actual output values are equal, do nothing.
• If the actual output is -1, but should be 1, increase the weights, that is, w_i -> w_i+delta w_i with delta w_i = lambda* (d_i-O_i)x_i.
• If the actual output is 1, but should be -1, decrease the weights, that is, w_i -> w_i+delta w_i with delta w_i = lambda* (d_i-O_i)x_i.

Example - Perceptron

Example - Perceptron (Cont'd)

Example - Perceptron (Cont'd)

1. Assume initial (guessed) weights as [0.75,0.5,-0.6].
2. With the first value we get:
   f(net)¹=f(0.75* 1.0 + 0.5* 1.0- 0.6* 1) = 1, hence no correction
3. f(net)²=f(0.75* 9.4 + 0.5* 6.4- 0.6* 1) = 1, however the result should be -1, so we have to apply the learning rule, i.e., w_i-> w_i+lambda*(d-sign(w_i* x_i))x_i, that is, w₁-> 0.75 +0.2*(-1-1)* 9.4=-3.01, likewise w₂=-2.06 and w₃=-1.00.
4. This will be repeated for all input values and we will get the final weights satisfying 1.3* x₁ +1.1* x₂-10.9=0 See [Luger, p. 424ff].

Properties of a Perceptron

• The choice of the learning rate lambda should not be too big (you will miss the true value), or too small (learning will be very slow). It is usual to decrease the learning rate slowly over time.

• All that can be learned is a straight line to separate positive from negative examples. But what, if the positive and negative examples cannot be separated by a straight line?

• Use more sophisticated threshold functions.
  

  hard limiting and bipolar threshold	sigmoidal and unipolar threshold

Sigmoidal Thresholds

• First the weighted inputs are summed up: net=sum_i=1ⁿw_i* x_i.
• Second the threshold function is applied:
  output=sigma(net)=1/ 1+ e^{-lambda* net}

Why Sigmoidal Thresholds?

• Nice theoretical properties (differentiable)
• Can approximate hard-limiting threshold function well for large lambda.

For learning (training) a network, use backpropagation. Try to minimise the squared error Error = ½sum_i(d_i-O_i)²

Multi Layered Neural Networks

• The perceptron can be viewed as a network of two layers, the input layer and the output layer.
• Any node, which is neither an input nor an output node, is called a hidden node.
• It is possible to create networks with many hidden nodes.
• A standard approach is to have a layered approach, in which all nodes are partitioned in layers and each layer n feeds in the next layer n+1 only.

Three Layered Neural Networks

Three Layered Neural Networks (Cont'd)

• All input nodes are connected with all nodes in the hidden layer.
• All nodes in the hidden layer are connected with the output layer.
• No further nodes are connected.

Backpropagation

• T is the set of training examples (given in form of an input list and an output list).
• d desired output
• O actual output

Backpropagation Approach

1. Initialise the weights randomly with small numbers (e.g. between -0.05 and 0.05.)
2. Until termination condition reached, repeat for each training example x:
   1. Take a training example x and compute the corresponding outputs.
   2. For each output node k calculate its error term
      delta_k=lambda* O_k* (1-O_k) * (d_k-O_k)
   3. For each hidden node h calculate its error term
      delta_h=O_h* (1-O_h) * sum_{k in Outputs} w_k,hdelta_k
   4. Update weights w_j,i -> w_j,i+delta w_j,i with
      delta w_j,i = delta_j* x_j,i

Intuitive Explanation for the Updates

• [(b)] delta_k=lambda* O_k* (1-O_k) * (d_k-O_k)
  The change of weights to the output nodes should be proportional to the difference between desired and actual output d_k-O_k, multiplied with the derivative of the sigmoid function.
  Note, with sigma(x)=1/ 1+ e^{-lambda* x} you get sigma'(x)=--lambda e^{-lambda* x} / (1+e^{-lambda * x})², that is, sigma'(x) = lambda...igma(x)* (1-sigma(x))
• [(c)] delta_h=O_h* (1-O_h) * sum_{k in Outputs} w_k,hdelta_k
  The value for a hidden node is updated similarly. However, since there is no error value which directly tells how to update it, the weighted average of its contribution to the errors is taken, where w_k,h is the weight between the hidden node h and the output node k.

Naive Bayes Approach

Naive Bayes Approach (Cont'd)

1. Approach: Estimate probabilities of P(v_j) and P(a_i|v_j) from the frequencies in the training set.
2. Naively assume that the probabilities are all independent, i.e., we can compute P(a₁,a₂,... ,a_n| v_j) as the product P(a₁|v_j)* P(a₂|v_j)*...* P(a_n|v_j).
3. The classifier is the most probable target value, that is, choose v_j so that given the attribute values [a₁,a₂,... ,a_n], take v_max=argmax_{vj in V}P(v_j|a1,a₂,... ,a_n)
4. With Bayes' theorem we get
   v_max= argmax_{vj in V}P(a₁,a₂,... ,a_n|v_j)P(v_j)/ P(a₁,a₂,... ,a_n)= argmax_{vj in V}P(a₁,a₂,... ,a_n|v_j)P(v_j)
5. With the assumption in (2) we get
   v_max= argmax_{vj in V} P(v_j)* P(a₁|v_j)* P(a₂|v_j)*...* P(a_n|v_j)

Naive Bayes Approach (Cont'd)

Assumed we see a new instance

Day	Outlook	Temperature	Humidity	Wind	PlayTennis
--------	-------------	-------------
new	Sunny	Cool	High	Strong	???

We compute:

P(Yes)* P(Sunny|Yes)* P(Cool|Yes)* P(High|Yes)* P(Strong|Yes)= 0.0053
P(No)* P(Sunny|No)* P(Cool|No)* P(High|No)* P(Strong|No)= 0.0206
Thus Naive Bayes chooses the attribute with the higher probability, i.e., No in this case.

Example - Text Analysis

• Assume we want to learn the target concept C, e.g. C= "www page that discuss the topic `Artificial Intelligence'."
• Assume we have k examples, e.g., pages of which we know for each whether it is relevant or not.
• We collect all n different words in all pages, e.g., n=1,000,000 words, w₁,w₂,... ,w_n and estimate their probabilities (from the training data): P(AIRelevant = Yes), P(AIRelevant = No), P(w_i = Yes | AIRelevant = Yes), P(w_i = No | AIRelevant = Yes), P(w_i = Yes | AIRelevant = No), P(w_i = No | AIRelevant = No), ... .

  Any unseen article will be classified according to
  P(Yes)* P(w₁=val₁|Yes)... P(w_n=val_n|Yes)          (relevant)
  P(No)* P(w₁=val₁|No)... P(w_n=val_n|No)          (irrelevant)
  Classify according to greater probability.

Summary

• Neural Networks and the Naive Bayes approach can be used in areas in which humans have no good intuition and do not know any causal relationship.

• The methods do not give any explanation for their answers.
• In some domains Naive Bayes has a comparable performance to decision tree learning and neural nets.

• Applied in many areas such as recognition of pictures

Further Reading    

• George F. Luger. Artificial Intelligence - Structures and Strategies for Complex Problem Solving. 4th Edition, Addison Wesley, 2002, Chapter 10.

• Tom M. Mitchell. Machine Learning. McGraw-Hill, 1997, Chapters 4 and 6.

• S. Russell, P. Norvig. Artificial Intelligence - A Modern Approach. 2nd Edition, Pearson Education, 2003. Chapter 20.

• Many more general AI texts and specialised books and articles.
• Specialised lecture on Neural Nets.