Algorithms: Literature Review

By pdarche On February 2, 2012 · Leave a Comment

As mentioned in the previous Algorithms post, over the last few months I’ve gathered a large (and growing) amount of data about various aspects of my life and I’m interested in analyzing it to gain knowledge about what affects my behavior, and what I can change to live better. A while back (I’m not sure when) I began learning about how this kind of analysis could be automated using algorithms studied by those in the field of machine learning. In this review I hope to accomplish three things: 1) define machine learning (and differentiate it from related fields, such as Data Mining and Knowledge Discovery in Databases), 2) describe the types of problems ML algorithms are used to solve, and 3) enumerate the algorithms used to solve those problems and describe how they do it.

Machine learning is a sub-field of Artificial Intelligence concerned with developing computer algorithms which ‘learn’ through exposure to data. What does it mean for an algorithm to learn? Mitchell, in his Machine Learning, defines learning thusly: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P , if its performance at tasks T, as measured by P, improves with experience E.” For example, an algorithm tasked with playing chess (T), would be said to learn if, through the experience of playing practice games against itself (E), it increased the percentage of games it won against opponents (P); or an algorithm tasked with classifying handwritten words in images (T) would be said to learn if it increased the percent of words correctly classified (P) given exposure to a database of handwritten words with given classifications.

Both of the previous algorithms, however, are examples of just one of the three major classes of algorithms studied by Machine Learning. Both use labeled training data to improve their performance, and are therefore instances of ‘supervised‘ learning algorithms. These algorithms are called ‘supervised’ because the information they use to generate their prediction or classification functions are known instances of what they are trying to predict. This contrasts with unsupervised learning algorithms, which use unlabeled or uncategorized data tho achieve their goals (ie looking to see if any groups or patterns can be found). The third major category of leanring algorithm is reinforcement learning, which uses reward and punishment to train algorithms to improve on learning tasks. Reinforcement learning is analogous to classical psychological conditioning, in that actions a trainer wants to see more of are positively reinforced with rewards, and actions he or she wants to see less of are negatively reinforced with (some form of) punishment.

An example that makes the distinction between supervised and unsupervised clearest to me involves the following computer vision problem. Imagine you were tasked with creating a machine that uses imaging to categorizes fruit. Given a random piece of fruit, the machine would be tasked with accurately labeling it as similar to it’s own kind and different from all other kinds. One way to solve this problem would be to ‘train’ the computer by giving it lots and lots of examples of each kind of fruit. After enough exposure to each kind of fruit, the computer would be able to classify any arbitrary new piece of fruit because it would be more like its own kind than the others. This is a paradigmatic example of supervised learning because it used a lot of examples of each particular kind of fruit to classify future cases.

Another way we could do this categorization would be to have all the fruit in one big pile and get the computer to group the fruits based on similarity in, say, size, shape, and color. It doesn’t know which fruit are which, but it does know that many are more similar along these dimensions to each other than others are, and it could separate them into distinct boxes based on these differences. This is a paradigmatic example of a clustering unsupervised learning algorithm; it’s not given labeled examples to use to make predictions, but it can find patterns in the data.

labeled and unlabeled classification are just two of the multiple problem classes addressed by supervised and unsupervised machine learning algorithms. Below is a list of problem classes and the circumstances in which they arise.

Problem Classes

Supervised Learning

regression : Very frequently, people are interested in predicting continuous quantities. Prices, temperatures, weights, etc. are some of the many values that vary continuously. If one is interested in how that quantity varies as a function of some other set of attributes, one is facing a regression problem. The form of this function may be linear or non-linear, and there are different algorithms to match each regression type.
classification – Equally frequently, people are interested in learning about categorical or discrete data. Yes/no questions, thresholds, and categories all fall into the category of classification problems. A typical example would be a medical diagnosis. It is of tremendous concern to doctors and patients whether or not a tumor is malignant. Classification algorithms can use data about past malignant tumors (size, density, etc.) to predict whether or not a given tumor is cancerous.
equations – If one is interested in modeling a real-world phenomena they are often interested in the set of equations that describe the behavior of the phenomena. Mathematical models can be inferred from data, and if this is what one is trying to do, then one is facing an equation problem.

unsupervised learning

associations -
clustering – If one has a large amount of data and doesn’t have a target variable in mind (or label for different categories of data), and one is facing a clustering problem. In these cases only a set of attributes without

Algorithms

Classification

Decision trees
Bayesian classifiers – classification through calculation conditional probabilities
Nearest neighbors -
Discriminant functions
Support Vector machines -
Neural networks
Hybrid Algorithms

Regression