<commit_before>---
layout: post
title: Neural Networks F#, XOR classifier and TSP Hopfield solver
date: '2015-03-19T01:37:00.000-07:00'
author: <NAME>
tags:
- Machine Learning
- FSharp
modified_time: '2015-03-20T07:02:18.930-07:00'
thumbnail: http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s72-c/perceptron.PNG
blogger_id: tag:blogger.com,1999:blog-1710034134179566048.post-286840343880955613
blogger_orig_url: http://hoonzis.blogspot.com/2015/03/neural-networks-f-xor-classifier-and.html
---
It seems that recently thanks to the buzz around Deep Learning, Neural
Networks are getting back the attention that they once had. This post
contains just a very short introduction to Neural Networks, just enough
to understand the F\# code which follows. The aim for me is to learn F\#
and see how easy it can be to write Machine Learning code in F\#.

I present here two examples of NN in F\#:

-   XOR classifier - sort of Hello World of NN. A simple composition of
    2 input nodes, 2 hidden nodes and 1 output node which learns the
    XOR function.
-   Solution to TSP using Hopfield NN. More complex network which
    evolves over time in it's configuration space to it's local minima,
    which shall correspond to optimal TSP tour.

Both working examples are [available at my
GitHub](https://github.com/hoonzis/MachineLearning)

Neural Networks
---------------

Artificial neural networks are computational models with particular
properties such as the ability to adapt or learn, to generalise or to
cluster and organise data. These models are inspired by the way that the
human brain works. The building blocks of Neural Networks are inspired
by Neurons - the building blocks of our brain. Neural Network can be
seen as interconnected graph of nodes, where each node takes a role of a
neuron. Each neuron can receive multiple signals, modify it and send it
to other neurons to which it is connected. In this graph some vertexes
are used to set the input, some of them are used to perform the
computation and other onces will hold the output values.

Nodes are connected by edges which have different weights. The weight of
the edge specifies how the signals is modified when passing from one
node to another.

### Perceptron

Perceptron is a basic block of linear neural networks. It is composed of
multiple input nodes and a decision node. Perceptron is a single layer
network. Input values are linked directly to the output node, connected
by edges with certain weights.



[![](http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s320/perceptron.PNG)](http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s1600/perceptron.PNG)



The ouput node takes the incomming values, sums them and based on the
result returns an output. The output could be binary or continous value.
For instance a threashold can be used to say whether the output is 1 or
0.

In practice, very often the Sigmoid or also called logistic function is
used to output value within the interval \[0,1\].

### Linear separability

Single layer perceptrons can only learn linerearly separable data.

Imagine we want to separate a set of datapoints into multiple clusters.
We visualize the data in 2-dimensional euclidian space. If we can
separate the cluster by drawing direct line between the data points, the
data is linearly seperable. The same can be applied on multi-dimensional
data



[![](http://4.bp.blogspot.com/-Tgaknx4kIHg/VQmuFgc67JI/AAAAAAAAEPA/kaqHsNBCuBE/s320/separable_data.PNG)](http://4.bp.blogspot.com/-Tgaknx4kIHg/VQmuFgc67JI/AAAAAAAAEPA/kaqHsNBCuBE/s1600/separable_data.PNG)



In a world of logical functions (we are building XOR classifier), this
limitation means that a single layer perceptron is able to learn AND or
OR function but it won't be able to learn XOR function.

One can easily imagine a line that separates all OR positive results
from the negatives once. On the other hand there is no streight line
that separates the positive XOR results (\[0,1\] and \[1,0\]) from the
negatives (\[0,0\] and \[1,1\])

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  [![](http://1.bp.blogspot.com/-b-Xq2GIIKys/VQmuFkN4K9I/AAAAAAAAEPE/Ctj9PiGYGQI/s320/or_data.PNG)](http://1.bp.blogspot.com/-b-Xq2GIIKys/VQmuFkN4K9I/AAAAAAAAEPE/Ctj9PiGYGQI/s1600/or_data.PNG)   [![](http://3.bp.blogspot.com/-b0rzcCZmOD0/VQmuOlXpDRI/AAAAAAAAEP8/oEwEPTO8JK8/s320/xor_data.PNG)](http://3.bp.blogspot.com/-b0rzcCZmOD0/VQmuOlXpDRI/AAAAAAAAEP8/oEwEPTO8JK8/s1600/xor_data.PNG)
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

### Feed forward multilayer networks

Feed forward network can be thought as composition of perceptrons. Such
network has one input layer, multiple hidden layers and one output
layer. The feed forward network does not contain cycles, unlike the
Hopfield network in the next examples (which is recurrent neural
network).

Unlike single layer perceptron, multilayer feed forward network is
capable of learning linerably non-separable data such as the results of
XOR function.

XOR classifier
--------------

This is the first example. This network is called clasifier because it
learns the XOR function. It can then "classify" the 2 values in the
input into single value on the output.

Here is how the network looks like:



[![](http://1.bp.blogspot.com/-UVM3imr3fyU/VQmuOtKeUtI/AAAAAAAAEQA/QUD43O87Z7E/s320/xor.PNG)](http://1.bp.blogspot.com/-UVM3imr3fyU/VQmuOtKeUtI/AAAAAAAAEQA/QUD43O87Z7E/s1600/xor.PNG)



The NN diagram was drawn in latex, using the tkz-berge package. [Look
here if you want to know
how](http://hoonzis.blogspot.fr/2012/03/graph-theory-in-latex.html).

The network starts with random weights and continously updates the
weights so that the result in the output node corresponds to the XOR of
input values. In order to update the weights Backpropagation (Backwards
propagation of errors) technique is used.

The value of the output is compared to the real value (which is known).
The error is determined as the differences between the output and the
real value. Then the weights of the edges has to be updated to
minimalize the error as shown later.

### Implementation

Each layer can be represented as one dimensional array, the weights are
stored using 2-dimensional array (\[0,1\] is the weight between nodes 0
and 1). Here is the function which calculates the sum of values
incomming to a single node and passes the value to the activation
function. The activation function here can be any function, as it is
passed as parameter but here Sigmoid is used.

``` 
let pass (input:float[]) (weights:float[,]) activation =
let length = weights |> Array2D.length2
seq {
    for i in 0 .. length-1 do
        let sum = (Array.zip weights.[*,i] input) |> Array.sumBy (fun (v,w) -> v * w)
        yield activation sum
} |> Array.ofSeq
```

By applying the **pass** multiple times, the whole network can be
composed as sequence of **pass** functions.

### The training procedure

The following function is the main loop of the XOR network and we
iterate over until we obtain good results and the network is adapted.

``` 
let train network rate input target =
    let n1 = completepass input network
    let delta = deltaOutput n1.output target
    let deltaHidden = passDelta n1.hidden delta n1.hiddenToOutput
    let updatedHiddenToOut = updateWeights n1.hidden delta n1.hiddenToOutput rate
    let updatedInToHidden = updateWeights n1.input deltaHidden n1.inputToHidden rate
```

**Completepass** just calls 2 times the pass function value and gets the
input values trough the hidden layer to the output. The output is then
compared to desired result and error is estimated. From this error an
array of "delta" values per each output node is determined which is then
used to update the weights.

In the case of XOR network, there is only one output, so the delta will
one dimensional array.

The delta has to be propagated lower so that we can also update the
weights between the input and hidden layer.

### Backpropagating the error<commit_msg>fixing the readmore of nn post<commit_after>---
layout: post
title: Neural Networks F#, XOR classifier and TSP Hopfield solver
date: '2015-03-19T01:37:00.000-07:00'
author: <NAME>
tags:
- Machine Learning
- FSharp
modified_time: '2015-03-20T07:02:18.930-07:00'
thumbnail: http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s72-c/perceptron.PNG
blogger_id: tag:blogger.com,1999:blog-1710034134179566048.post-286840343880955613
blogger_orig_url: http://hoonzis.blogspot.com/2015/03/neural-networks-f-xor-classifier-and.html
---
It seems that recently thanks to the buzz around Deep Learning, Neural
Networks are getting back the attention that they once had. This post
contains just a very short introduction to Neural Networks, just enough
to understand the F\# code which follows. The aim for me is to learn F\#
and see how easy it can be to write Machine Learning code in F\#.

I present here two examples of NN in F\#:

* XOR classifier - sort of Hello World of NN. A simple composition of 2 input nodes, 2 hidden nodes and 1 output node which learns the XOR function.
* Solution to TSP using Hopfield NN. More complex network which evolves over time in it's configuration space to it's local minima, which shall correspond to optimal TSP tour.

Both working examples are [at GitHub](https://github.com/hoonzis/MachineLearning)

Neural Networks
===============

Artificial neural networks are computational models with particular
properties such as the ability to adapt or learn, to generalise or to
cluster and organise data. These models are inspired by the way that the
human brain works. The building blocks of Neural Networks are inspired
by Neurons - the building blocks of our brain. Neural Network can be
seen as interconnected graph of nodes, where each node takes a role of a
neuron. Each neuron can receive multiple signals, modify it and send it
to other neurons to which it is connected. In this graph some vertexes
are used to set the input, some of them are used to perform the
computation and other onces will hold the output values.

Nodes are connected by edges which have different weights. The weight of
the edge specifies how the signals is modified when passing from one
node to another.

### Perceptron

Perceptron is a basic block of linear neural networks. It is composed of
multiple input nodes and a decision node. Perceptron is a single layer
network. Input values are linked directly to the output node, connected
by edges with certain weights.

[![](http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s320/perceptron.PNG)](http://3.bp.blogspot.com/-VReCg6iqrF0/VQmuBdLVLvI/AAAAAAAAEOw/-wxaOWzU26U/s1600/perceptron.PNG)

The ouput node takes the incomming values, sums them and based on the
result returns an output. The output could be binary or continous value.
For instance a threashold can be used to say whether the output is 1 or
0.

In practice, very often the Sigmoid or also called logistic function is
used to output value within the interval \[0,1\].

### Linear separability

Single layer perceptrons can only learn linerearly separable data.

Imagine we want to separate a set of datapoints into multiple clusters.
We visualize the data in 2-dimensional euclidian space. If we can
separate the cluster by drawing direct line between the data points, the
data is linearly seperable. The same can be applied on multi-dimensional
data

[![](http://4.bp.blogspot.com/-Tgaknx4kIHg/VQmuFgc67JI/AAAAAAAAEPA/kaqHsNBCuBE/s320/separable_data.PNG)](http://4.bp.blogspot.com/-Tgaknx4kIHg/VQmuFgc67JI/AAAAAAAAEPA/kaqHsNBCuBE/s1600/separable_data.PNG)

In a world of logical functions (we are building XOR classifier), this
limitation means that a single layer perceptron is able to learn AND or
OR function but it won't be able to learn XOR function.

One can easily imagine a line that separates all OR positive results
from the negatives once. On the other hand there is no streight line
that separates the positive XOR results (\[0,1\] and \[1,0\]) from the
negatives (\[0,0\] and \[1,1\])

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
  [![](http://1.bp.blogspot.com/-b-Xq2GIIKys/VQmuFkN4K9I/AAAAAAAAEPE/Ctj9PiGYGQI/s320/or_data.PNG)](http://1.bp.blogspot.com/-b-Xq2GIIKys/VQmuFkN4K9I/AAAAAAAAEPE/Ctj9PiGYGQI/s1600/or_data.PNG)   [![](http://3.bp.blogspot.com/-b0rzcCZmOD0/VQmuOlXpDRI/AAAAAAAAEP8/oEwEPTO8JK8/s320/xor_data.PNG)](http://3.bp.blogspot.com/-b0rzcCZmOD0/VQmuOlXpDRI/AAAAAAAAEP8/oEwEPTO8JK8/s1600/xor_data.PNG)
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

### Feed forward multilayer networks

Feed forward network can be thought as composition of perceptrons. Such
network has one input layer, multiple hidden layers and one output
layer. The feed forward network does not contain cycles, unlike the
Hopfield network in the next examples (which is recurrent neural
network).

Unlike single layer perceptron, multilayer feed forward network is
capable of learning linerably non-separable data such as the results of
XOR function.

XOR classifier
--------------

This is the first example. This network is called clasifier because it
learns the XOR function. It can then "classify" the 2 values in the
input into single value on the output.

Here is how the network looks like:



[![](http://1.bp.blogspot.com/-UVM3imr3fyU/VQmuOtKeUtI/AAAAAAAAEQA/QUD43O87Z7E/s320/xor.PNG)](http://1.bp.blogspot.com/-UVM3imr3fyU/VQmuOtKeUtI/AAAAAAAAEQA/QUD43O87Z7E/s1600/xor.PNG)



The NN diagram was drawn in latex, using the tkz-berge package. [Look
here if you want to know
how](http://hoonzis.blogspot.fr/2012/03/graph-theory-in-latex.html).

The network starts with random weights and continously updates the
weights so that the result in the output node corresponds to the XOR of
input values. In order to update the weights Backpropagation (Backwards
propagation of errors) technique is used.

The value of the output is compared to the real value (which is known).
The error is determined as the differences between the output and the
real value. Then the weights of the edges has to be updated to
minimalize the error as shown later.

### Implementation

Each layer can be represented as one dimensional array, the weights are
stored using 2-dimensional array (\[0,1\] is the weight between nodes 0
and 1). Here is the function which calculates the sum of values
incomming to a single node and passes the value to the activation
function. The activation function here can be any function, as it is
passed as parameter but here Sigmoid is used.

```fsharp
let pass (input:float[]) (weights:float[,]) activation =
let length = weights |> Array2D.length2
seq {
    for i in 0 .. length-1 do
        let sum = (Array.zip weights.[*,i] input) |> Array.sumBy (fun (v,w) -> v * w)
        yield activation sum
} |> Array.ofSeq
```

By applying the **pass** multiple times, the whole network can be
composed as sequence of **pass** functions.

### The training procedure

The following function is the main loop of the XOR network and we
iterate over until we obtain good results and the network is adapted.

```fsharp
let train network rate input target =
    let n1 = completepass input network
    let delta = deltaOutput n1.output target
    let deltaHidden = passDelta n1.hidden delta n1.hiddenToOutput
    let updatedHiddenToOut = updateWeights n1.hidden delta n1.hiddenToOutput rate
    let updatedInToHidden = updateWeights n1.input deltaHidden n1.inputToHidden rate
```

**Completepass** just calls 2 times the pass function value and gets the
input values trough the hidden layer to the output. The output is then
compared to desired result and error is estimated. From this error an
array of "delta" values per each output node is determined which is then
used to update the weights.

In the case of XOR network, there is only one output, so the delta will
one dimensional array.

The delta has to be propagated lower so that we can also update the
weights between the input and hidden layer.

### Backpropagating the error
{'fraction_non_alphanumeric': 0.1537313432835821, 'fraction_numerical': 0.026176808266360506, 'mean_word_length': 2.824588364434687, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 13, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 22, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6537940', 'n_tokens_mistral': 5184, 'n_tokens_neox': 4644, 'n_words': 2096}