Wednesday, 11 April 2018

Chess and Machine Learning?

Machine learning is a new, exciting and growing area of computer science that looks at if and how computers can learn without explicitly being taught.  Within the last few weeks, machine learning programs have learned games such as Go and Chess, and become very capable players: Google's AlphaZero beat the well-known Chess engine Stockfish after just 24 hours of learning how to play; just over a year ago, AlphaGo beat the world's strongest human player Ke Jie at Go.

AlphaZero is different from all previous Chess engines, in that it learns by playing.  Having been programmed with the rules of Chess (aims of the game; how the pieces move), it played 1000 games against itself, learning as it went.  The Google Alpha Zero team have published a paper of their research, and it makes for interesting reading.

From a Chess perspective, the data is very interesting as it shows how Alpha Zero discovered some key well-known openings (the English; the Sicilian; the Ruy Lopez) and how it used them in games, and then discarded them as it found 'better' alternatives.  Table 2 on page 6 shows how the frequency of each opening varied against training time.  There are some interesting highlights in the data:

The English Opening (1. c4 e5 2. g3 d5 3. cxd5 Nf6 4. Bg2 Nxd5 5. Nf3) was a clear favourite with Alpha Zero from very early on, and grew in popularity.


The Queen's Gambit (1. d4 d5 2. c4 c6 Nc3 Nf6 Nf3 a6 g3 c4 a4) also became a preferred opening.


Interestingly, the Sicilian Defence (1. ... c5) was not favoured, instead the preferred line against 1. e4 was the Ruy Lopez (1 ... e5).

It's worth remembering that Alpha Zero deduced these well-known and long-played openings and variations by itself in 24 hours - compared to the decades (and centuries) of human play that has gone into developing these openings.

Apart from the purely academic exercises of building machines that can learn to play games, there are the financially lucrative applications of machine learning: product recommendations.  Amazon and Netflix make extensive use of recommenders, where machines make forecasts about a user, based on users who showed similar behaviour ("people who liked what you like also like this...").  Splitting out and segmenting all users to find users with similar properties is a key part of the machine learning process for this application.

In conclusion:  
"It's an exciting time for Machine Learning.  There is ample work to be done at all levels: from the theory end to the framework end, much can be improved.  It's almost as exciting as the creation of the internet."  Ryan Dahl, inventor of Node.js

Monday, 5 March 2018

Why are manhole lids circular?

I remember reading this question - and its answer - in a maths puzzle book in my mid teens. It's a very simple solution - and very easy to start investigating further.  The short answer: manhole lids are circular so that they don't fall down the hole (risking losing the lid, and landing on a worker who is in the hole).  Technically, the lid has a constant maximum diameter irrespective of which angle you use to measure it. 

The same cannot be said of most other polygons - let's take some quick examples.
Squares: the sides are shorter than the diagonals, so a small rotation will enable the lid to fall down the hole.
Pentagons: the ratio of side to diameter is smaller, but it's still possible to drop the lid down the hole.
Equilateral triangles are an exception; and in fact you do sometimes see manhole lids that are equilateral triangles (sometimes hinged along one side).

The same principle applies to coins. In order to function correctly,  a vending machine has to be able to identify and distinguish different coins, based on their diameter and irrespective of how they fall through the slot.  The coins which are not circular are based on Reuleaux polygons, such as the Reuleaux triangle, where the shape has a constant diameter - the key requirement for coins, and manhole covers!

Wednesday, 14 February 2018

Film Review: Star Wars The Last Jedi

I loved it.

My first impressions from the first few minutes was that this was a retread of Empire Strikes Back.  The First Order have tracked down the resistance base on a remote planet, and the resistance are trying to evacuate before the First Order land troops and... oh, wait a minute, there is no shield, no cannon and the base is going to be obliterated from space.  And things seem to go well for the resistance, as they are able to stall long enough to get almost everybody safely aboard their cruiser and off to safety.  But not before Poe Dameron (X-Wing ace turned hot-headed insubordinate comedian pilot) decides to sacrifice the entire bomber fleet just to destroy a Dreadnaught.  Let's here it for Pyrrhic victories!

Worse still, the First Order have developed a way to track the Resistance through hyperspace: running away is not a way to escape, and hyperspace fuel is in limited supply.

At the end of the previous film, Rey had successfully tracked down Luke Skywalker, and much of this film covers her efforts to persuade him to join the Resistance.  So, we have space battles interspersed with the story of a Jedi master and a young Jedi-wannabe/trainee on a remote, green, damp planet.  Like I said, I kept recalling Empire Strikes Back throughout this film. I haven't looked online to see if anybody has listed all the parallels between The Last Jedi and The Empire Strikes back, but I saw a few (and I'm only a casual movie-goer).  Luke Skywalker has traded his youthful naivety and enthusiasm for jaded cynicism.  The way he casually lobs his lightsabre over his shoulder is both funny and tragic at the same time.

My only niggle with the film is the amount of time spent on the story with Rey and Luke.  The other storylines were far more exciting and just downright interesting; Luke and Rey - less so.  Luke goes for a walk.  Luke catches a fish.  Luke wanders around his island.  Yawn.

The plot makes a lot of sense, and there's a direct causal link between the Admiral and her tight-lipped need-to-know authoritarian attitude, conflicting with Poe Dameron's "we have a right to know what's going on" and the subsequent demise of the resistance fleet.  If she'd told Poe what her plan was, he wouldn't have sent Finn off to find the code breaker, who wouldn't have subsequently told the First Order about the resistance's plans and their cloaking frequency (or whatever it was).  If they'd all stayed home, sat tight and waited it out, they might all have survived.  I'm not blaming him or her, but it seems like the two characters managed to deliberately out-hard-head each other - aiming to be the most stubborn character and the one who wins, until neither of them do.

Some of my favourite aspects of the film is how the script addresses some of the criticisms that were levelled at the first of the new films (The Force Awakens).

"Finn should have had that fight with Captain Phasma, not with some random stormtrooper with a cool elbow mounted weapon."  Cue large-scale, violent, hand-to-hand fight between Finn and Phasma.


"Snoke is too much like the Emperor and there's no real explanation for him."  Kill him off - now who saw that coming?

"More Poe Dameron!" - definitely fixed in this episode.  He kicks off the action at the start; we see more of his character throughout this film (borderline arrogant, but still funny) and he commits mutiny.  This is not a replacement for Han Solo; this is a whole new character who has his own ideas, opinions and history.


"Do something different!"  - I saw most of the parallels between The Force Awakens and A New Hope.  In fact, it felt like a rehash of the story with new faces. As I mentioned earlier, The Last Jedi has elements of The Empire Strikes Back in it, but those elements have been rearranged to produce a fresh story (and no, I didn't for one second think "It's salt!", I knew full well it was meant to be snow).

All-in-all, I'm excited for the next installment; I'm looking forwards to the Han Solo movie and I feel even more optimistic for the future of the Star Wars saga.

Monday, 12 February 2018

Mathematically Explaining Confidence and Levels of Significance

Level of Significance: a more mathematical discussion

In mathematical terms, and according to "A Dictionary of Statistical Terms, by E H C Marriott, published for the International Statistical Institute by Longman Scientific and Technical":


"Many statistical tests of hypotheses depend on the use of the probability distributions of a statistic t chosen for the purpose of the particular test. When the hypothesis is true this distribution has a known form, at least approximately, and the probability Pr(t≥ti) or Pr(t≥t0), and Pr(t ≤ ti) and Pr(t ≤ t0) are called levels of significance and are usually expressed as percentages, e.g. 5 per cent.  The actual values are, of course, arbitrary, but popular values are 5, 1 and 0.1 per cent."






In English: we assume that the probability of a particular event happening (e.g. a particular recipe persuading a customer to convert and complete a purchase) can be modelled using the Normal Distribution.  We assume that the average conversion rate (e.g. 15%) represents the recipe's typical conversion rate, and the chances of the recipe driving a higher conversion rate can be calculated using some complex but manageable maths.  

More data, more traffic and more orders gives us the ability to state our average conversion rate with greater probability.  As we obtain more data, our overall data set is less prone to skewing (being affected by one or two anomalous data points).  The 'spread' of our curve - the degree of variability - decreases; in mathematical terms, the standard deviation of our data decreases.  The standard deviation is a measure of how spread out our data is, and this takes into account how many data points we have, and how much they vary from the average.  More data generally means a lower standard deviation (and that's why we like to have more traffic to achieve confidence).


When we run a test between two recipes, we are comparing their average conversion rate (and other metrics), and how likely it is that one conversion rate is actually better than the other.  In order to achieve this, we want to look at where the two conversion rates compare on their normal distribution curves.


In the diagram above, the conversion rate for Recipe B (green) is over one standard deviation from the mean - it's closer to two standard deviations.  We can use spreadsheets or data tables (remember those?) to translate the number of standard deviations into a probability:  how likely is it that the conversion rate for Recipe B is going to be consistently higher than Recipe A.  This will give us a confidence level.  It depends on the difference between the two (Y% compared to X%) and how many standard deviations this is (how much spread there is in the two data sets, which is dependent on how many orders and visitors we've received.

Most optimisation tools will carry out the calculation on number of orders and visitors, and comparision between the two recipes as part of their in-built capabilities (it's possible to do it with a spreadsheet, but it's a bit laborious).

The fundamentals are:


- we model the performance (conversion rate) of each recipe using the normal distribution (this tells us how likely it is that the actual performance for the recipe will vary around the reported average).
- we calculate the distance between conversion rates for two recipes, and how many standard deviations there are between the two.

- we translate the number of standard deviations into a percentage probability, which is the confidence level that one recipe is actually outperforming the other.

Revisiting our original definition:
Many statistical tests of hypotheses depend on the use of the probability distributions of a statistic t chosen for the purpose of the particular test

...and we typically use the Normal Distribution When the hypothesis is true this distribution has a known form, at least approximately, and the probability Pr(t≥ti) or Pr(t≥t0), and Pr(t ≤ ti) and Pr(t ≤ t0) are called levels of significance and are usually expressed as percentages, e.g. 5 per cent.

In our example, the probabilities ti and t0 are the probabilities that the test recipe outperforms the control recipe.  It equates to the proportion of the total curve which is shaded:




You can see here that almost 95% of the area under the Recipe A curve has been shaded, there is only the small amount between t1 and t0 which is not shaded (approx 5%).  Hence we can say with confidence that Recipe B is better than Recipe A.

Thus, for example, the expression "t falls above the 5 per cent level of significance" means that the observed value of t is greater than t1 where the probability of all values greater than t1 is 0.05; t1 is called the upper 5 per cent significance point, and similarly for the lower significance point t0."

As I said, most of the heavy maths lifting can be done either by the testing tool or a spreadsheet, but I hope this article has helped to clarify what confidence means mathematically, and (importantly) how it depends on the sample size (since this improves the accuracy of the overall data and reduces the standard deviation, which, in turn, enables to us to quote smaller differences with higher confidence).

Tuesday, 6 February 2018

New Year's Resolution - Don't moan, complain.

One of my New Year's Resolution's for 2018 is this: don't moan, complain.

What's the difference?

We're very good, as a society, at moaning. Social media has made it even easier to bend our friends' ears about the latest irritation that we've had to suffer: long queues; poor service; sub-standard goods; cold food; inept staff; rude checkout assistants... the list goes on. And we think that sharing our dreadful experience with our friends will avenge us on the service provider - we "warn" our friends against giving their money to the same company and encourage them to support their competitors instead.

That is not complaining; that's moaning.

Moaning
: telling everyone about a terrible experience - except the people who (1) caused your inconvenience and/or (2) are in a position to fix your situation or provide redress.  


Complaining: approaching the person who provided the poor service; the lousy product; the long wait or the cold food, and asking them to please fix it.

I don't tend to complain - I think it's rude; I don't want to cause a scene; I don't want to be an inconvenience; I think should just tolerate it and make it a character-building opportunity.

However, I think it's time to make a change, and - when necessary  - to complain instead of biting my tongue (I'd like to think I don't moan much, but the principle is the same). Some stores, cinemas and so on ask for feedback - some shops will enter you for a prize draw if you do - which is a good place to start, but how about this: if you think you're going to go home and then tomorrow tell your friends how bad this place/shop/meal was today, why not tell the staff today? Or at least contact their complaints department so that they can actually do something about it. Make a difference, so that they can make a difference too.

Tuesday, 23 January 2018

Explaining Statistical Significance and Confidence in A/B tests

If you've been presenting or listening to A/B test results (from online or offline tests) for a while, you'll probably have been asked to explain what 'confidence' or 'statistical significance' is.

A simple way of describing the measure of confidence is:

The probability (or likelihood) that this result (win or lose) will continue.


100% means this result is certain to continue, 50% means it's 50-50 on if it will win or lose. Please note that this is just a SIMPLE way of describing confidence, it's not mathematically rigorous.

Statistical significance
(or just 'significance') is achieved when the results reach a certain pre-agreed level, typically 75%, 80% or 90%.


It's worth mentioning that confidence doesn't give us the likelihood that the magnitude of the win will remain the same.  You can't say that a particular recipe will continue to win at +5.3% revenue per visitor (it might rise to 5.5%, or fall to 4.1%), but you can say that it will continue to outperform control.  As the sample size increases, the magnitude of the win will also start to settle down to a particular figure, and if you reach 100% confidence then you can also expect the level of the win to settle down to a specific figure too.

A note: noise and anomalous results in the early part of the test may lead you to see large wins with high confidence.  You need to consider the volume of orders (or successes) and traffic in your results, and observe the daily results for your test, until you can see that the effects of these early anomalies have been reduced.


Online testers frequently ask how long a test should run for - what measures should we look at, and when are we safe to assume that our test is complete (and the data is reliable).  I would say that looking at confidence and at daily trends should give you a good idea.


It's infuriating, but there are occasions when more time means less conclusive results: a test can start with a clear winner, but after time the result starts to flatten out (i.e. the winning lift decreases and confidence falls).  If you see this trend, then it's definitely time to switch the test off.

Conversely, you hope that you'll see flattish results initially, and then a clear winner begin to develop, with one recipe consistently outperforming the other(s).  Feeding more time, more traffic and more orders into the test gives you an increasingly clear picture of the test winner; the lifts will start to stabilise and the confidence will also start to grow.  So the question isn't "How long do I keep my test running?" but "How many days of consistent uplift do you look for?  And what level of confidence do I require to call a recipe a winner?"

What level of confidence do I need to call a test a winner?


Note that you may have different criteria for calling a winner compared to calling a loser.  I'm sure the mathematical purists will cry foul, and say that this sounds like cooking the books, or fiddling the results, but consider this:  if you're looking for a winner that you're going to implement through additional coding (and which may require an investment of time and money) then you'll probably want to be sure that you've got a definite winner that will provide a return on your money, so perhaps the win criteria would be 85% confidence with at least five days of consistent positive trending.

On the other hand, if your test is losing, then every day that you keep it running is going to cost you money (after all, you're funneling a fraction of your traffic through a sub-optimal experience).  So perhaps you'll call a loser with just 75% confidence and five days of consistent under-performing.  Here, the question becomes "How much is it going to cost me in immediate revenue to keep it running for another day?" and the answer is probably "Too much! Switch it off!!"  This is not a mathematical pursuit, along the lines of "How much money do we need to lose to achieve our agreed confidence levels?", this is real life profit-and-loss.

In a future blog post, I'll provide a more mathematical treatment of confidence, explaining how it's calculate from a statistical standpoint, so that you have a clear understanding of the foundations behind the final figures.



Thursday, 18 January 2018

Geometry: Changing the steepness of a hill by zig-zagging

Even if a hill or a road is too steep to climb, there is still a way to make progress, and that's by zig-zagging.  Instead of going directly up the hill in the shortest route, it's possible to take an angled approach up the slope, increasing the path length, but making the climb angle less steep.

It is easier to outline this in a simplified diagram:



This triangular prism represents the face of a hill.
The angle directly up the hill is α and is shown in the pink triangle.
The angle of approach (i.e. the degree of zigzag, the deviation from the straight-up route) is ß, and is shown by the red and pink triangles combined.
The resultant angle (i.e. the actual angle of ascent) is δ and is shown by the blue triangle.

Each of the triangles is right-angled, so standard trigonometry functions can be applied (I haven't shown all the right angles in the diagram, but it is a regular triangular prism).

Considering each of these three angles in turn:  the way to get to a simplified expression for δ is to express the three angles in the fewest numbers of lines.  It's possible to express α, ß and δ in terms of the external dimensions of the prism (let's call them x, y and z) but this just leads to incompatible expressions that can't be simplified or combined.

α
  



ß


δ



The strategy here is to substitute for y and p in the expression for δ, and then to simplify.

Firstly, rearrange the expressions for α and ß to make y and p the subjects of those equations.



A very simple and elegant equation:  the angle of ascent depends on how steep the hill is, and the amount by which you zigzag, and is completely independent of the size of the hill (i.e. none of the lengths are relevant in the calculation).

A few sanity checks:

If ß is zero, or close to zero, then δ approaches α - i.e. if you don't zigzag, then you approach the hill at its actual angle.

If ß approaches 90 degrees, then  δ approaches zero - you hardly climb at all, but you'll need to travel much further to climb the hill.  In fact, as ß tends towards 90 degrees, path length p tends to infinity.


If α increases, then δ increases for constant ß (something that was worth checking).

An interesting note:

At first glance, you may think that a path (or zigzag) angle of 45 degrees would reduce the angle of ascent by half (e.g. from 60 degrees to 30 degrees), simply because 45 is half of 90.  However, this isn't the case.  In order to get a reduction of a half, cos ß needs to equal 0.5.  If cos ß = 0.5, then ß = 60 degrees.  A much larger deviation from the straight-up angle is needed.


In conclusion

This question was first put to me when I was in high school (a few years ago now) and it's been nagging at me ever since.  I'm pleased to have been able to solve it, and I'm pleased with how surprisingly simple the final expression is (previously, my 3-D geometry and logic weren't quite up to scratch, and I ended up going round in circles!).