How General is Your Algorithm?

One of the research issues that has been tackled for at least 50 years is attempting to develop algorithms that are better than other algorithms on a certain type of problem (for example, vehicle routing, traveling salesman problem etc.). And it is easy to judge if you have a better algorithm. You run it on a benchmark problem from the literature and if yours is better you write a paper claiming as much. Of course, you should also show statistical significance, robustness of your approach, provide some discussion etc.

There has been some recent work where the goal is to develop an algorithm that works well on many different problem domains. This is a challenging objective as even small changes to a problem instance can make an algorithm that used to perform well, now perform poorly. See a previous blog where I gave a simple example.

So, if we have an algorithm that works well on a particular problem instance, but a small change to the problem renders it useless (or at least worse than it was) then imagine the challenge in trying to get an algorithm to work on a totally different domain without any changes being made to the algorithm. To make it clearer what we are trying to achieve, let's say you have an algorithm that works well on a Vehicle Routing Problem. Is it possible, without any changes to that algorithm, to get it to work well on a (say) a staff rostering problem?

This is one (if not THE) goal of hyper-heuristics. In a future blog, I'll give some more concrete examples, but the challenge of developing more general search algorithms is an area that is attracting quite a lot of interest at the moment.

Horse Race Prediction with Neural Networks

I was sorting through some old papers recently and I came across my undergraduate final year dissertation. I recall that it started as a project about genetic algorithms but quickly turned into a project that used neural networks to predict the outcome of horse races.

I trained a back propagation network and used the final network to predict the outcome of (selected) races that the network had not been trained on. One of the biggest challenges was finding suitable data. I was lucky enough that a couple of companies (Timeform and Raceform - thank you) sent me their databases which made the data collection side of things a lot easier than it might have been.

One item that was missing from both datasets were the starting prices. Due to this I could not really judge if the predictions would result in a profit. However I did a few calculations and assumed that the average odds were either 2/1 (3.00), evens (2.00) or 1/2 (1.50) (see note, for a description of the odds calculation). I also made an assumption that the odds would also capture any tax that had to be paid.
Using these figures it was possible to make a profit even when the average odds were as low as 1/2 (1.50).

I wonder if it really is possible to develop a prediction system that can make a profit from backing horses? Although my undergraduate dissertation suggested that it is, it would need a lot more development, testing and analysis.
I would also like to investigate other methodologies, in addition to neural networks - but that needs a little more thinking about.

Of course, it's not possible to predict the result of every race but you only need to predict enough races, at good enough odds, to show a profit.

One of the issues when betting is the amount of tax you have to pay but with new methods of betting (such as spread betting and betting exchanges) becoming ever more popular, perhaps this might not be so much of an issue.
I know that betting exchanges (such as betfair) still charge a tax but at least you are betting against other punters and are not limited by the odds being offered by the bookmakers.

I'll keep this one of the back burner for a while, but I think there is some potential in exploring it further.

Note on odds: I have shown the odds in two ways. The UK way of expressing odds is (for example) 2/1 which means you have to place a stake of 1 unit to win 2 units. You also receive back your stake. So if you bet 1 unit at odds of 2/1, and the horse wins you receive 3 units back (the 2 units you won + your 1 unit stake = 3 units; less any tax - but let's ignore that for the purpose of this discussion).
Another way of expressing odds is the decimal format (which I have shown in brackets). This is used, for example, on betfair. This says how much you will receive for 1 unit, including getting your stake back. So if you bet 1 unit at odds of 3.00, and the horse wins, you get 3 units back.
So the two ways are just the same way of expressing the same thing, but you might be more used to seeing one system over another, depending on where you live/bet.