Machine Learning - Introduction

Machine Learning - Introduction

After my latest blog on "Why Robots are the way of the future" I realized I have not really written about one of my greater passions...Machine Learning/Artificial Intelligence.

Machine Learning and Artificial Intelligence are not quite the same thing. Usually Machine Learning falls under the category of Computational Science, Mathematics, Computer Science and Statistics. Artificial Intelligence usually belongs to the Computer Science, Cognitive Science, Psychology and perhaps Mathematical Philosophy departments.

Machine Learning is generally the field of study related to the question: How can we teach a machine to perform a certain task as well as it can be performed?

However, Artificial Intelligence is generally an answer to the question: How can we simulate (or reproduce) the cognitive functions of humans/animals/intelligent beings? A lot of Artificial Intelligence seeks to model the human mind, which doesn't always do things optimally.

Both fields of study are important for developing algorithms and systems that are able to interact, aid, and enhance our lives. For instance, Machine Learning was used to create software to control a refinery. Up until the 1980's most refineries and their myriad pipes, valves, and gauges were controlled by humans. Any potential catastrophes had to be averted by alert workers. However, ML systems were developed that could optimally monitor and control refineries...even better than humans can! Furthermore, as conditions in the refinery change over time the software adapts and retrains itself without having to be reprogrammed over and over.

Interestingly, many of the Machine Learning algorithms are fairly simple in their approach. For instance, a basic classification algorithm is as follows:

Given a set of descriptions x and their associated objects/predictions y which are part of a set of classification categories {y_1, y_2, ... , y_n},

Build a model (a brain)

- For each unique classification y:

-take mean(x) for all x associated with the classification categories y_n

Make Predictions

- take an unclassified description x and evaluate the distances to each of the category means

- the unclassified description x will be classified according to the closest mean

Enhance the model with new examples

-given additional information x and y, recalculate the mean(x)'s with the new information...the model is now enhanced.

For example: Bobby stands by the road and for every vehicle that passes by quickly measures the length of the vehicle. Bobby also writes down whether the vehicle was an "18-wheeler" or "other". Using the above algorithm he calculates the mean "18-wheeler" length to be 20.4 feet, and the mean "other" vehicle length to be 10.9 feet. A blind girl named Jane comes along and says that she has just measured a vehicle that is 16.9 feet long, but can't tell if it's an "18-wheeler" or not. Bobby says that since the unobserved vehicle is closer in length to an "18-wheeler" it must be one!

This may not seem like a very intelligent algorithm (and it's not) but it does demonstrate one key feature of an intelligent algorithm, the ability to form it's internal computing algorithm via external data.

In the next few articles on Machine Learning I'd like to discuss some other more intelligent algorithms such as Support Vector Machines, Neural Networks and Random Forests...all three of which are some of the coolest and most effective AI/ML algorithms. Until then, see if you can think up your own intelligent algorithm...or use for an algorithm. I'd love to hear about it!

But How Can I be Sure my Widget is Actually Working?

But How Can I be Sure my Widget is Actually Working?

Welcome to the world of statistics, where we try to convince ourselves and our employers/clients/friends/wives that the projects we have spent hours and hours on are actually worthwhile! We will see by the end of this article just how you can too can demonstrate with reasonable certainty that your very own predictor/estimator/widget is having a positive (or negative effect) on the process it is being applied to.

Yes, we're talking about hypothesis testing!

What hypothesis?

The hypothesis that results from the question about whether our widget has a positive (or negative) effect on the process, of course ! If we want to know whether the widget has a positive or negative effect then we must hypothesize the opposite (that there is no effect, or that the widget and the normal process are the same) and try to prove it wrong! This may sound counter-intuitive but one limiting factor about statistics is that you can't prove a statement true, you can only use it to reject a statement (though your're not disproving it).

For example, for my stock market predicting widget, I want to know how I can be 95% confident in my belief that my estimated prediction accuracy of 57% is not just random chance (luck). If you've ever studied the stock market you've probably heard the cliche about how someone let monkeys pick stocks, or threw darts at a dartboard and the resulting random selection of stocks did better than "such and such" a famous money manager. Well, I don't want to end up being the money manager that gets beat by a monkey, that's for sure!

First, in statistics, we are always estimating parameters. In this case we are only estimating the ability of my stock predictor to make correct stock predictions. Because I can't, or wont, test the predictor on every stock ever I can't know it's true 100% ability to make predictions. But this is where the beauty of mathematical statistics comes in...we don't have to! I can estimate the stock's accuracy on a relatively small number of days within the stock's history and then use the principals of confidence intervals to establish a level of confidence or belief that my predictor is better or at least not eqaul to a random predictor.

Secondly, we want to know something about how we expect the process to function without the help of our widget. For my stock widget, I want to know if my predictor is significantly different than a random predictor, i.e. a monkey throwing a dart at a dart board filled with stock predictions (if monkeys could do that).

So how do we know what our process will do without our widget? Easy! We simply sample the output! Sometimes we can do this theoretically, as in the case of my stock market predictor.

My stock predictor only makes predictions on whether the stock should be bought or sold. I can say that the accuracy of my stock predictor, which comes in the form n correct predictions out of N attempts, looks a lot like a Binomial distribution! Actually, Binomial distributions look a lot like Normal/Gaussian distributions ...otherwise known as the Bell curve. A Binomial distribution can be produced with the following 4 steps:

1.) flip a coin 100 times and write down how many times you got heads - we'll call this a "coin flip trial" with a heads population of "p-heads".

2.) we do 1000 "coin flip trials" - yes it will take a while

3.) after the "coin flip trials" are finished we make a chart and plot each unique value of "p-heads", and the number of times we got each one of the "p-heads".

4.) We stand back and marvel at our new representation of the Binomial Distribution - it should look this.

This is what would happen if I randomly chose whether the stock would go up or down. It would achieve 50% accuracy on average.

If you get an evenly balanced coin you will notice that your most popular choice for "p-head" is 50. You will also notice that most of the values fall within the range 45 and 55.

Now, let's say that the evenly balanced coin is a random stock predictor. It will only predict half of all possible stock moves correctly... i.e. you lose as much as you make over time. But when I run my stock predictor on a random sample of the market it tells me that I got 57% of the predictions correct!. Since this estimated accuracy is only on a small random portion of the market, how do I know that I didn't just get lucky? How do I know I'm not a monkey (this may be an altogether different question :-)?

Going back to my hypothesis, I need to evaluate the claim that (Accuracy_random = Accuracy_mystockwidget). But this is the same as evaluating (0 = Accruacy_mystockwidget - Accuracy_random) Now, we know that the accuracy of the random predictor will be distributed according to the picture above. Incredibly, my stock predictor should actually follow the same pattern, only shifted over to the right slightly. But here's the even more incredible thing, if we subtract the two variables, and plot the results the associated relative frequencies, it will also look like the above!

If the resulting distribution contains 0 in a centered 95% selection of it's values about its mean, then we will be forced to make the satement, "We fail to reject the hypothesis that Theo's stock widget is equal to a random monkey predictor." However, if 0 is not found about this center 95% of the distribution, then I can proudly say that I reject the claim that they are equal in favor of the claim that my predictor is different from a coin-flippining monkey (and I will later go on to say that of course it is much better!). So what do the numbers say? Let's take a look at another sweet chart!

And so we see that from a statistical standpoint, my stock predicting widget is significantly different from a coin-flipping-dart-throwing monkey predictor!

Isn't statistics cool?

note: I haven't yet acheived 57% accuracy yet, so hold your horses and your money until I do :-)

An estimate of the Probability of getting a 4 Letter Acronym Formed by Blog Subtitles

Kent at The Digression blog asks: What is the probability of a blog's subtitle's first letter of each word producing a meaningful acronym?

Apparently the subtitle for my blog makes the acronym MPEG. MPEG is the acronym for a file format that contains movies or motion pictures.

Well be careful what you ask for, cause here's my answer! :-)

First, let's simplify this by asking, what is the probability of producing a meaningful 4 letter acronym given that the blog has a 4 word subtitle.

The probability of getting a meaningful 4 letter acronym given that the blog has a 4 word subtitle is: P(4 letter meaningful Acronym blog has 4 word subtitle).

Using Bayes rule of conditional probability, we can say that P(4A blog4subtitle) = P(blog4subtitle 4A) x P(4A) / P(blog4subtitle).

The P(4A) = #meaningful 4 letter Acronyms / #of Possible 4 letter Acronyms

The P(blog4subtitle) = #of blogs with 4 word subtitles / #of blogs, the probability that out of all blogs, the chosen blog has a 4 word subtitle.

The conditional probability P(blog4subtitle 4A) = Probability of getting a blog with 4 words in the subtitle given that it has a 4 letter meaningful acronym) = 1

So then P(4A blog4subtitle) = 1xP(4A) / P(blog4subtitle).

Let's proceed shall we?

A rough estimation of the #of meaningful 4 letter acronyms is... well that's kind of hard. Ok so here's where we can get all statistical.

On Wikipedia we can find a list of all acronyms known to wikipedia . Sampling the population of A acronyms I can count that for each section of the A page (26 sections, the acronyms are broken down into the AA, AB, AC...AZ sections) there are about 10 4-letter acronyms. Let's assume that the actual number per section is distributed according to a normal distribution ~ N(10, 2)...i.e. The number of 4 letter acronyms per section is 10+-about 2 per section. We can do this because for large n, the binomial distribution is approximated by a normal distribution. There are 26 sections per page...and 26 pages...thus 676 sections. Taking this into account, we can say that the number of 4 letter acronyms in existence has a sampled distribution of ~N(676*10, 676*2) which means that there will be on average an estimated 6760 4 letter acronyms based on our small sample distribution of 1 section of the A acronyms on wikipedia.

On the other hand computing the number of possible 4 letter acronyms is easy.... 26X26X26X26 = 456976.

Estimating the number of blogs with 4 letter subtitles is also difficult. But again, let's say that the number words in the subtitle of a blog is distributed according to a binomial distribution with mean 6. Assuming that the max number of words in the subtitle is 20, the probability of getting a 4 word subtitle can be approximated by 20!/[4! x 16!] x .3^4 x (.7)^16 = .13 This means that obtaining a blog with 4 letters would be the probability of obtaining a 4 letter blog times the number of blogs available.

The available #of blogs is 66 million...according to BlogHerald .

So(P(blog4subtitle) = .13 x 66million/66million = .13

Thus our final estimation of the probability of getting a meaningful acronym given a four word subtitle is distributed according to a N(6760/456976/.113, 1352/456976/.113) distribution. (It is a distribution because I had to estimate the number of 4 letter acronyms in order not to have to count them.) Thus I can't be 100% sure what the real probability is. However the mean probability from my estimation is about 11.3% with a variation of 2%. And I can say with 99% confidence that the true probability of obtaining a 4 letter meaningful acronym given my 4 word subtitle lies between 6% and 16%.

That was fun wasn't it? With statistics anything is possible to estimate!