Backpropagation algorithm

Backpropagation is an algorithm used to teach feed forward artificial neural networks. It works by providing a set of input data and ideal output data to the network, calculating the actual outputs and backpropagating the calculated error (the difference between the ideal and actual outputs) using gradient descent. This is useful for learning specific patterns of input and output data in order to be able to reproduce them afterwards even from slightly different or incomplete input data. Neural networks are able to learn any function that applies to input data by doing a generalization of the patterns they are trained with.

In this post I will start by explaining what feed forward artificial neural networks are and afterwards I will explain the backpropagation algorithm used to teach them. In the end I will provide a sample implementation. This post expects some knowledge of math and computer programming from the reader.

Artificial neural networks

Artificial neural networks try to simulate the basic functioning of natural neural networks. The human brain has billions of neurons that work together as one big network. Each natural neuron has stronger or weaker connections with other neurons in the brain. It is believed that in these connections (especially how strong they are) is most of the information that the brain retains.

An artificial neural network retains this basic aspect of natural neural networks and uses a set of real value weights to remember how strong the connections between its neurons are. Each neuron has a number of input connections from other neurons, a number of output connections to other neurons and an activation function that is calculated on the sum of inputs and provides the output value of the neuron.

Feed forward neural networks don’t have any cycles in their neuron connections network. This implies that the outputs connections of a neuron are different from the input ones. In this kind of network the neurons are typically arranged in layers.

The feed forward neural network above has 6 neurons arranged in 3 layers. N₁, N₂ and N₃ are called input neurons as they receive data directly from the user, not other neurons. For input neurons the activation function is not used. N₄ and N₅ are part of what is called a hidden layer of neurons. They are hidden as the user can’t set them a value or get their value directly, they only communicate with other neurons. N₆ is an output neuron. From the output neurons the users get the result of the neural network processing. W_ij are the weights of the connections between the neurons (the value of how strong the connections are).

Hidden and output neurons apply an activation function to their sum of input data. The sum of input data is the sum of the products of the input neurons output values and the weights of the input connections from those neurons.

, where N_i are the input neurons to neuron N_j

For the activation function F(x) we have the output of the neuron N_j:

In order to be able to learn any pattern we need a non linear activation function. The most used activation function is the sigmoid function:

Because the sigmoid function takes values in the (0, 1) interval you will have to scale your output values to and from that interval.

In our example above we have:

N₁, N₂ and N₃ as input values.
N₄ = F(w₁₄*N₁ + w₂₄*N₂ + w₃₄*N₃)
N₅ = F(w₁₅*N₁ + w₂₅*N₂ + w₃₅*N₃)
Output = N₆ = F(w₄₆*N₄ + w₅₆*N₅)

Backpropagation

The purpose of learning is to determine the weights W_ij that allow us to reproduce the provided patterns of inputs and outputs (function of inputs). Once the network is trained we can use it to get the expected outputs with incomplete or slightly different data. Basically, it learns a function of arbitrary complexity from examples. The complexity of the function that can be learned depends on the number of hidden neurons.

A backpropagation step for a specific input pattern and ideal output starts by calculating the error at the output neurons. This error is the difference between the provided ideal output and the calculated actual output multiplied with the activation function derivate on that output point. For the sigmoid function the derivate is F^’(x) = F(x)*(1 – F(x).

OutputError_j = (IdealOutput_j – Output_j) * F^’(Output_j)

In our example, using the sigmoid as an activation function:

N₆_Error = (N₆_Ideal – N₆) * N₆ * (1-N₆)

After we have the error for the output layer we calculate an error for each neuron in the hidden layers, going backwards, layer by layer. The error for a neuron in a hidden layer is the sum of the products between the errors of the neurons in the next layer and the weights of the connections to those neurons, multiplied by the derivate of the activation function.

HiddenError_i = ∑(OutputError_j * w_ij) * F^’(HiddenOutput_i)

In our example:

N₄_Error = ( N₆_Error * w₄₆ ) * N₄ * (1 – N₄)
N₅_Error = ( N₆_Error * w₅₆ ) * N₅ * (1 – N₅)

We will use those errors to calculate the variation of the weights as a result of the current input pattern and ideal outputs. The variation (delta) of a weight is the product of the input neuron output value with the error of the output neuron for that connection. Please note that I use input neuron and output neuron for a connection as a separate term from the network input neurons and output neurons.

∆w_ij = Output_i * Error_j

In our example:

∆w₄₆ = N₄ * N₆_Error
∆w₅₆ = N₅ * N₆_Error

∆w₁₄ = N₁ * N₄_Error
∆w₂₄ = N₂ * N₄_Error
∆w₃₄ = N₃ * N₄_Error
∆w₁₅ = N₁ * N₅_Error
∆w₂₅ = N₂ * N₅_Error
∆w₃₅ = N₃ * N₅_Error

This process is repeated for all input patterns and the variations (deltas) are accumulated. At the end of a learning iteration we change the actual weights with the accumulated deltas for all the training patterns multiplied with a learning rate (a number typically between 0 and 1 which states how fast a network converges to a result). A neural network typically needs at least a few hundred iterations in order to learn a set of patterns.

∆w_ij_Final = ∑∆w_ij_Input_k
w_ij = w_ij + ( ∆w_ij_Final * LearningRate )

In our example, considering 2 input patterns and a learning rate of 0.3 we have for example:

∆w₄₆_Final = ∆w₄₆_Input1 + ∆w₄₆_Input2
New w₄₆ = w₄₆ + 0.3 * ∆w₄₆_Final

Resuming, in order to teach a network using backpropagation, we do the following steps:

- For a specified number of training iterations

1. For each input and ideal (expected) output pattern
   1. Calculate the actual output from the input
   2. Calculate output neurons error
   3. Calculate hidden neurons error
   4. Calculate weights variations (delta): ∆w_ij
   5. Add the weights variations to the accumulated delta
2. Learn by using the accumulated deltas and adding them to the weights

I’ve made a C# implementation of a feed forward neural network with just one hidden layer that uses backpropagation: NeuralNet.cs.

I also made an example project (using Visual C# Express Edition) where I test the neural network and backpropagation on simple digit recognition: nnet.zip

GSeptica card game

Just created a new game. It is the GTK implementation of a popular card game in Romania, called “Septica”. It has a simple and intuitive interface (mostly, just drag cards down on the deck area). The game itself is simple to play and you can find the game rules on the website or in the game help menu.

Take a look:  http://gseptica.sourceforge.net

Remote administration security issues

Any administrator that accesses his server from his home computer (or any not so safe computer for the matter) is easily vulnerable to giving access to the server to hackers. If the admin uses ssh an attacker could easily hijack the ssh command (or the graphical ssh menu entry) and present the admin with identical looking hacked version of ssh that remembers the server password and sends it to verybadguys.com.

Using /usr/bin/ssh might help if the source account in not root and root is really, really hard to get by an attacker (for root the hacker can simply replace your original ssh) but there probably are methods to hijack that even in a limited account (graphical ssh program with plugins? some kind of plugin like functionality for the console? are you sure you opened the right console?(do you really trust that menu entry?)). Even if the hacker does not know how to hijack your ssh he can use snapshots of your desktop to make an idea of how the server configuration looks like and use that information later when doing an attack (if he sees a config file password or cryptology key its obviously bad but sometimes even subtler information is decisive) .

This applies to many other remote administration taks (ftp included). If you do ftp from firefox a malicious firefox addon can simply remember your password.

Security issues with sudo

I posted the issue described bellow in a post on ubuntu forums. They closed my thread in a few hours so I am reposting it here so that you can comment on it. If I don’t get some reasonable feedback from the linux community until next week I will publish code and step by step instructions on how to use it.

1. The problem
In Ubuntu gksu and sudo can be hijacked by an attacker who already has access to the current non-administrative account. In order to do that you can simply create a bin directory in your home folder, add that directory to PATH and create in it the scripts: gksu and sudo. The scripts would silently run any application the attacker wants with root privileges and start the application you wanted to start in the first place so that you won’t notice a thing.
So, after the attacker application (got on a website with a firefox bug for example) gets access to your limited account all it has to do in order to get root access is the above and wait for you run something with administrative rights (like synaptic from the menu; at some point even the updater which runs automatically was calling gksu with a relative path). This largely defeats the purpose of having a limited account on a desktop version of Ubuntu. The code to do this is very simple and even a script kiddie can make it if he doesn’t find it somewhere on the internet.
I did test multiple times the things I said above.

2. The do it right solution
I don’t know how to fix sudo but for gksu I have an idea and I posted it on the gksu bug I submited a year and a half ago. Even if you set a description gksu should show the complete path of the application it is running. The presence of the description still leaves easy social engineering attacks (people don’t read all the text in a form or they don’t understand linux commands) but an advanced user has a chance to realize he is hacked. A more complete solution would require not being able to modify menu entries for administrative applications and, of course, having absolute paths in those menu entries.
Sudo solutions might go in the direction of modifying the most used terminal in order to treat sudo specially but I find that very problematic. The simple, working, correct solution is to also lock the screen and show what you are executing.
There might be a system wide solution for any administrative start commands in a way that the system (kernel and some base applications) treats differently the sudo/gksu type of commands. It would not use the path to search for sudo but only its predefined location and the path used for the applications sudo runs would be only changeable with root access. But I understand too little about linux as a whole in order to realize all the implications of this.
There also is the simple and very restrictive solution of not having local user paths, only paths that are modifiable by root access.
The use of unlock on some ubuntu applications (User settings) puzzles me. The password prompt you get there does not lock the screen and it seems that you don’t have a way to realize if it is the system asking you the password or an applications that looks just like “user settings” (it is very easy to create clones in open source). I haven’t looked deeper into unlock but superficially it doesn’t look like a solution for gksu problems.
Any solution without having an administrative (locked, grayed out, something that only a root application can do) screen where to enter the password and see exactly what you are running is prone to attacks where the random dialog appears and asks you for password (maybe it knows that you are running synaptic and somehow expect to be asked about password).

3. The sad solution
No gksu and sudo. Users log out and log in as root for administrative stuff. Of course they will end up using only root and here the limited account “protection” stops.

4. The “great new thing” solution
Get rid of the default limited user account on desktop installations. Even if that user account works properly in connection with doing administrative jobs its limitation don’t prevent an attacker to do damage where it mostly matters for you. For 99% of the users their documents and most other things they care about are accessible/modifiable with the limited user account. This includes those secret pictures you have with your new girlfriend. Browser settings can also be altered without administrative rights, and of course browsing history, cache and saved passwords are not locked behind the “root door”. There are things that the malware can’t do on limited accounts like sniffing, key logging, reading your credit card from firefox memory but attackers can find creative ways around these limitations (can’t they install addons without root access? don’t those addons get to the firefox internals?).  For me, the part of the system for which I need root access is the part I care less about. For instance I installed the version of Ubuntu (9.04) I am talking from 2h ago (45 min of my time I think). On my desktop system (doing usual stuff: internet, music, pictures) if an attacker gets from limited account to root access he mostly can hide better from me (rootkits). But I am not really searching for him so I won’t find him anyway.
As for limited access preventing users and applications to do stupid things. Users are not prevented too much to mess their system by root access (they need to type “sudo rm -fr /*” instead of “rm -fr /*”; saving a document in / by accident is not the biggest problem in the world; for deleting system files they could be prompted anyway). User applications are prevented to arbitrarily break the system but there is a long time since I’ve seen an application trying to break my system in any place other than the installer. Its true that default root access would allow applications to grow more ill behaved (like saving user settings in /usr) but we might find solutions for that without using a default limited account (at least not as limited as it is now; minimal set of restrictions, warnings, etc for properly behaving applications).
On Windows XP when I do not trust an application I get from the internet I do run it under a limited user account I created specifically for that purpose. That user account does not have access to my documents, my desktop, settings or anything else that matters for me. Things I save from that application go to that account documents and I copy them later from that location. People see me as an advanced user and, still, I have to admit that I don’t find the method easy to use. But if the operating system would create such a user account for me and offer me some really easy entry points to it when I might need it (like asking: do you want to run this internet application: yes, no, under limited account.) I would use it all the time. Firefox can also be run under a special limited account (you could still save files only in a predefined location), maybe each tab in its process like chrome with higher limitations if you go on some blurry web sites (enabled for private browsing?).
I have installed my Windows XP system 3 years ago, I use it a lot and I like to experiment new things but still I haven’t broken it. I did reinstall some linux systems in the mean time (it is related with understanding less linux (I did the “hard” windows experiments 12 years ago), going deeper into the system (I use sudo all the time), but mostly it is problematic updates (especially distribution upgrades)).

5. Linux security fundamentalists please read the above twice before posting .

What do you think about Georgia?

I saw on television the recent war on Georgia. I want to say my opinion on the matter. I think that the russians tried to make their actions look similar with the USA intervention in Kosovo. Its true there was no land invasion in Kosovo but the air attacks where far reaching inside Serbia. Just like the russian response was far reaching inside Georgia. The russians commented that they are fighting for the peace of the region. They said that they are providing humanitarian aid and fighting off the aggressor. And now they are recognizing the breakaway provinces South Osetia and Abhazia as independent states. Just like US did with Kosovo. Neither USA or Russia had UN support for their actions. Its true that US had a lot a of allies and UN support was denied by Russian intervention. But still, there was no legal international support in both cases. The Russians might say that they respected the will of the people in the two provinces. Just like US respected the will of the people in Kosovo. It seems to me that there are many similarities between the US intervention in Kosovo and the Russian intervention in South Osetia. What do you think? Should the Russian soldiers be heroes or negative characters?