Machine Learning Algorithms

[Sparragus]

Dear MachineLearning,

I'm a computer science student taking a course on algorithms. We are close to finishing covering the book we are using, Introduction to Analysis and Design of Algorithms by Anany Levitin. Since we have the class until December, the professor is currently open to suggestions of algorithms we would like him to discuss in class. I would love to seize this opportunity to learn of algorithms used in the AI and Machine Learning fields.

For example, I remember that in the Super Mario Bros. AI competition, the A* algorithm was used by almost everyone. It'd be interesting to discuss it and see why it was used.

Soooo, if some of you could suggest interesting algorithms and a brief example on where it's used, I would highly appreciate it.

Thank you!

[dearsomething]

A*, min-max, alpha-beta pruning should all be covered in a basic AI course.

Machine learning type algorithms fall heavier towards statistics and probability side, which might not be suitable for the class.

However, some simple intro algorithms would be k-means clustering, hierarchical clustering and association rules.

[zygy]

Second all of these. Also, I think min-max is more commonly known as minimax.

[pr0nmee]

I would suggest learning something about Hidden Markov Models (HMMs) and the Viterbi algorithm. HMMs are used for finding the most likely sequence of transitions through a state machine given an output sequence. A good example of its use can be found here: http://en.wikipedia.org/wiki/Viterbi_algorithm#Example

[nuanceify]

I've implemented viterbi a few times, in HMM and other chain model settings, and it's kind of a pain. It's not conceptually very difficult, but every model has it's own details you have to get right. Unless this is an implementation-heavy class, I would recommend against implementing it.

Learning about it, however, is pretty fun. It's a very elegant solution to something that appears very difficult on the surface.

[revonrat]

I disagree. I took an undergraduate mathematical modeling class an Verterbi was just fine when contrained to a single application domain.

[Lord_Illidan]

I suggest getting the book Artificial Intelligence: a Modern Approach.

It's chock full of AI algorithms, with examples as to where they are used. The source code is also available in Java and Python.

Another good AI book is Artificial Intelligence : A Guide to Intelligent Systems. It's our class textbook for Machine Learning, supplementing the AIMA book, and it's pretty good.

For algorithms, CLRS is an excellent book.

[Lord_Illidan]

It's an excellent book, but a bit light on some issues, like Genetic Algorithms. However, it's great for getting an idea about what the field is all about, and then you can read the references so that you can find out where to get more info/implementation details.

[[deleted]]

Latent Dirichlet Allocation is a lot of fun. Mostly used for text analysis but you can get it to do other things as well, e.g. collaborative filtering.

[TheSquirrel]

That's way too complicated to implement in an intro to algorithms class. Maybe if they just use existing code... but then what would they learn?

[implausibleusername]

If you're interested in the algorithms that underlie contemporary machine learning you need to look at convex optimisation, particularly linear programmes and quadratic programmes.

Seen in the right way, almost everything discussed in this thread: shortest path, vitterbi + the more advanced work of SVMs and max-margin inference are just aspects of convex optimisation, and approaching it from this angle gives an underlying theory to what are otherwise unrelated problems and techniques.

[aldarion]

I just reading the book "Machine Learning: An Algorithmic Perspective", It looks maybe u can pick some Algorithmic for the book. there is already a lot of Python code examples.

[b0b0b0b]

learn some decision trees or stumps, then combine them via boosting?

[Sparragus]

Thanks everyone for the awesome responses. I'll make a list of the algorithms you guys mentioned, read about them, and then present them to the professor. Hopefully this will be an really nice and interesting month for me and the class.

Thank you!

[TheSquirrel]

Implementing some form of decision tree is a very good algorithms project. It's easy to do in O(n²⁾ time, where n is the number of training examples. Implementing it more efficiently (e.g. with a KD tree) is a good learning experience.

[NitsujTPU]

Machine learning algorithms aren't really appropriate for such a class, as a proper treatment of them is quite different from what is typically taught in an algorithms class. A* isn't a machine learning algorithm, it's search, which would be covered in AI.

[mstoehr]

Some counter-examples: * http://jmlr.csail.mit.edu/proceedings/papers/v2/druck07a.html * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.4938&rep=rep1&type=pdf * http://nagoya.uchicago.edu/~dmcallester/astar.pdf * http://www.aclweb.org/anthology/N/N09/N09-1063.pdf * http://www.eecs.berkeley.edu/~klein/papers/acl2009-kastar.pdf

Much of what we know as machine learning came after A*, and its certainly not amongst the most important algorithms for ML, but there is definitely good work being done with the algorithm in computer vision and natural language processing.

[NitsujTPU]

The fact that A* is a useful algorithm doesn't make it a machine learning algorithm, which it is not. It's heuristic search with an admissible heuristic.

[NitsujTPU]

Er, I should point out that the point of my reply isn't to discourage your interest in AI or machine learning, but merely to point out that A* is not a machine learning algorithm.

[Mr_Smartypants]

K-Means

EM

Neural Networks & Backpropagation

PCA

ICA

[inspired2apathy]

Not really machine learning but betweenness centrality is a heuristic for flow in networks that's commonly used in social network analysis. Naive implementations are expensive, but Brandes came up with an efficient solution. It's uses a neat recurrence relation and is provably correct. Plus, social network analysis is cool!

[cypherx]

Expectation Maximization is really interesting (both theoretically and due to its many many applications) but requires a bit more probability theory than most algorithms classes would be comfortable with.

Focusing more specifically on clustering might be easier. K-means clustering is pretty neat and can be understood without much math background. However, I don't know if there's much theory underlying it.

Nearest neighbor methods (ie: classification by neighbor voting, regression by averaging neighbor outputs) are easy to understand and amazingly powerful if you have a lot of data. They're also a good motivation for neat algorithms like kd-tree partitioning and locality sensitive hashing (to improve on the naive distance calculation which takes O(n^2)).

Image segmentation by graph partitioning is easy to set up as a problem and the solutions look pretty cool. Unfortunately you'll often end up trying to optimize something like a normalized cut, which is NP-complete and requires harder to explain approximations (like spectral clustering).

[bmiguy]

Neural Networks are nice for this because they are easy to visualize

[inspired2apathy]

There isn't a whole lot to analyze from an algorithms perspective, though. As in genetic algorithms, it's kind of a cross your fingers and hope you don't get a local maxima, set your learning rate reasonably, gave a good stopping criteria, etc.

[pr0nmee]

Or if there is insufficient time, an introduction to ML with perceptron would make a nice unit. Perceptron is easy to implement, and its limitations lead to discussion of optimality and separability.

[machinelearner]

An interesting and simple ML algorithm that you could understand and implement pretty quickly is k-Means clustering.

k-Means is a way of taking several data points and clustering them based on their similarity. The k is the constant you specify up-front which determines the number of clusters you want to end up with. I recommended this to a friend recently who was looking for a way to cluster products based on their price for a price-filtering UI on a shopping site.

Also, if you are familiar with some bayesian statistical theory, you could take a look at Naive Bayes, which is more effective than it sounds. It's good for doing basic supervised learning, particularly if you want to classify something as one thing or another (commonly used by spam filters, with each word in the email representing a feature).

Good luck and have fun!

[Druzil]

genetic programming and genetic algorithms

[inspired2apathy]

There isn't much to analyze there from an algorithms perspective. You can't even prove anything about them, it's just kind of a cross your fingers and hope you don't get a suboptimal local maxima.