Prediction Competition

Date:

2002-11-13

Group:

David Öggesjö <it1ogda@ituniv.se>

Henric Thisell <it2thhe@ituniv.se>

Sebastian Edman <it2edse@ituniv.se>

Source Code and Binary:

source (predict.tar.gz)

linux binary (predict.gz)

Table of Contents

The Predict Program

Basic Algorithm

Main Program

Interface

Bugs

Compile

High Scores

Score Board

The Predict Program

First let me quote a comment at the prediction competition, "This guy doesn't have a life".

Basic Algorithm

The algorithm used, is by us referred to as 'the adaptive tree algorithm'. I have no idea if that is the proper name, but it actually describes it pretty well. It is a very simple approach.

It consists of a tree, where each node has two branches, one and zero. At the bottom of the tree structure there is a value (leaf) at each end. The last N values in the input is used to traverse from the top to the bottom of the tree. When reaching the leaf, the value is used to predict the result and simultaneously the next input value from the user is added to the current leaf value. This makes the program do the following.

1. Use the last input value to train the previous leaf (the leaf which is saved at point 2). If the last user input is one, one is added to the leafs value and if it zero one is subtracted from the previous value.

2. Traverse through the tree structure to a specific leaf (using the last sequence of the user input) and save a pointer to the leaf for the updating in point 1.

3. Use the leafs value to output a zero or one. If the leafs value is positive it generates a one, and if it is negative it generates zero. If it is zero a random output will be generated.

Main Program

The main program was just an infinite loop. Where the prediction of a variable was done first, then a value was input, after this the statistics are updated and everything is presented to the user.

The prediction is actually done 6 times with different depths of the adaptive tree. Depths of 2 to 7 are used. Then the best prediction over the last 50 inputs is chosen. (This can be viewed by pressing F6, the word presented is telling which prediction it is using).

Interface

Escape exits, 'q' clears the statistics. F6 through F8 selects what to view, '0', 'o' and 'O' generate a zero and all other keystrokes generates a one.

Bugs

When the competition started we were told have the predicted value visible. This of course was added very quick, too quick. It's buggy and does not present the right predicted value, I apologize humbly to the first groups that were only presented this 'faulty' number.

Also, one word is misspelled ;)

Compile

The program is compiled with a simple 'make' in the source directory. It is compileable under Linux.

High Scores

The third and fourth best performers was two of the groups at the prediction competition, with 54.0% correct each. The second place goes to an art & tech student with a result of 53.4% and the first place goes to the staff with a whooping 49.8%. The first place is a bit debated but, the number was input by hand (took over an hour, but hey!) and not generated by a computer algorithm or similar.

The programmers best result is 55%...

Score Board