30
$\begingroup$

I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of the currently most interesting/greatest algorithmic results in machine learning. The potentially tricky constraint is that the students will not have any particular previous knowledge of linear algebra or the other main topics in machine learning.

This is really to excite them about the topic and to let them know that ML is a potentially exciting research area for algorithms experts.

EDIT: This is a final year undergraduate course (as we don't have graduate courses in the UK in the main). They will have done at least one basic algorithms course beforehand and presumably done well in it to have chosen the advanced follow up course. The current syllabus of the advanced course has topics such as perfect hashing, Bloom filters, van Emde Boas trees, linear prog., approx. algorithms for NP-hard problems etc. I don't intend to spend more than one lecture exclusively on ML but if something is really relevant to both an algorithms course and an ML one then of course it could also be included.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Please clear out two things: 1) Is it an undergraduate course or a graduate course? What related courses (if any) have they passed? 2) How much time do you want to devote to ML? $\endgroup$
    – Sadeq Dousti
    Commented Nov 15, 2010 at 13:53
  • 3
    $\begingroup$ hmmm I think linear algebra is a must and an important foundation course, at least in machine learning side. and I think linear model is a very good introductory to machine learning algorithms. you may think of other basic level algorithms like K-nearest neighbor or logistic regression algorithms. might this help you en.wikipedia.org/wiki/List_of_machine_learning_algorithms $\endgroup$
    – Deyaa
    Commented Nov 15, 2010 at 14:37
  • 1
    $\begingroup$ Perhaps some ideas from how Hal Daume teaches Machine Learning -- nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html $\endgroup$
    – Yaroslav Bulatov
    Commented Nov 16, 2010 at 3:37
  • 3
    $\begingroup$ Dear Raphael, Avrim Blum typically concludes his senior-level algorithms class with machine learning and a few related topics; a recent iteration is at the following link cs.cmu.edu/~avrim/451f09/index.html , and you can get more info from his webpage. Having both TA'd and taken this class, I can say that it (and its concluding material) are very warmly received by the students. $\endgroup$
    – matus
    Commented Nov 16, 2010 at 3:59
  • 1
    $\begingroup$ see eg genetic algorithms or also deep learning $\endgroup$
    – vzn
    Commented May 9, 2014 at 22:36

10 Answers 10

Reset to default
29
$\begingroup$

You can cover boosting. It's very clever, easy to implement, is widely used in practice, and doesn't require much prerequisite knowledge to understand.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ I've presented some parts of the survey by Arora et al. (cs.princeton.edu/~arora/pubs/MWsurvey.pdf) in the grad theory class a few years back. People seemed to like it and I think you need almost no background to understand this material. $\endgroup$
    – Danu
    Commented Nov 15, 2010 at 20:39
9
$\begingroup$

If you just want to whet their appetite in a single lecture, it might be most exciting to present a powerful application. For example, support vector machines, and other machine learning algorithms, are used in chemoinformatics for drug discovery.

The learning problem essentially is: given a behavior we want a chemical to exhibit, devise a structure that exhibits that behavior by deducing it from a database of known structures that exhibit similar (or dissimilar) behaviors. The learning problem has an extra wrinkle: the new drug needs to be "distant" in global structure from previously known drugs, in order to found a patent estate.

One source is Clustering Methods and Their Uses in Computational Chemistry .

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the reference. I was thinking of perhaps teaching SVMs as an application of convex optimisation. That would relate the algorithms part with the ML part nicely. $\endgroup$
    – Simd
    Commented Nov 15, 2010 at 16:00
  • 2
    $\begingroup$ how do you cover SVMs without linear algebra? $\endgroup$
    – Lev Reyzin ♦
    Commented Nov 15, 2010 at 16:26
  • $\begingroup$ I was hoping to teach them the minimum prerequisites for it in my course. Maybe that was too optimistic :-) $\endgroup$
    – Simd
    Commented Nov 15, 2010 at 17:00
  • $\begingroup$ Are there still important examples where support vector machines are the best choice? I notice that on kaggle competitions, for example, they are never the main part of a winning entry. At least not any that I have seen recently. (I stand to be corrected of course.) $\endgroup$
    – Simd
    Commented May 9, 2014 at 18:34
7
$\begingroup$

K-Means and KNN are very powerful and do not require any Linear Algebra except the computation of distances of points.

Improve this answer
$\endgroup$
1
  • $\begingroup$ K-Means in particular is a very potent algorithm. It is incredibly effective despite not having proven bounds on its objective function performance, to such a spooky extent that it's almost like the Simplex algorithm's effective polynomial complexity (despite real exponential complexity). Its online version is also useful in large-scale data applications. $\endgroup$
    – Elliot JJ
    Commented May 26, 2011 at 1:56
5
$\begingroup$

The second part of "Neural Networks and Machine Learning" by Christopher Bishop (at MSR) is on algorithms in ML. Bishop's textbooks are commonly used for graduate (and later undergraduate) textbooks and are extremely well-written.

Improve this answer
$\endgroup$
4
$\begingroup$

This algorithm uses graph minimum cuts to classify large amount of unlabeled samples using only small amount of labelled samples.

Its undergrad friendly. I have explained this to a few randomly chosen undergrads and they understood it.

Ref: Blum, A., & Chawla, S. (2001). Learning from labeled and unlabeled data using graph mincuts.

Self promotion Visualization of the algorithm on youtube.

Improve this answer
$\endgroup$
3
$\begingroup$

I see that Expectation Maximization (EM) has not been mentioned, and it's certainly "up there" in the top 10: http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf .

Improve this answer
$\endgroup$
1
$\begingroup$

Reinforcement Learning algorithms (especially Q-Learning and SARSA) are quite simple to understand and very powerful to resolve some learning problems. They don't require any advanced knowledge in linear algebra, except for convergence proof and convergence rate.

You can use the well known survey of Littman and al.: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html

Improve this answer
$\endgroup$
1
$\begingroup$

You can cover some algorithms which are classic or with good intuition.

For example, C4.5 and CART, which are classic decision tree algorithms.

You also can cover some ensemble methods(e.g., AdaBoost(Boosting), Bagging), which have a very good performance in real world applications.

Furthermore, deep learning is also a good topic, because it is very hot.

Improve this answer
$\endgroup$
1
0
$\begingroup$

Native bayes and Bayesian network, decision tree algorithms are quite easy to visualize than starting with a neutral network or svm

Improve this answer
$\endgroup$
0
$\begingroup$

Genetic programming is really cool. It uses inspiration from biology, and can be applied to a vast number of problems (for example, n-queens problem, and TSP).

It does not require deep mathematical skills.

EDIT: It only requires a way to estimate how good a potential solution is. It can be used for example to guess the rule behind a series of numbers, finding minima/maxima to multi-variate problems, and search huge parameter spaces. It is suited when you are not interested in the optimal solution, but when a good enough solution will do. I believe this has been used to find good strategies for games (build orders in Starcraft 2, and optimal play in Mario).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there any important problem for which it is the best method? I mean it certainly isn't for TSP for example. $\endgroup$
    – Simd
    Commented May 9, 2014 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.