<p>If you just want to whet their appetite in a single lecture, it might be most exciting to present a powerful application.  For example, <a href="http://en.wikipedia.org/wiki/Support_vector_machine" rel="nofollow">support vector machines</a>, and other machine learning algorithms, are used in chemoinformatics for drug discovery.</p>

<p>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.</p>

<p>One source is <a href="http://onlinelibrary.wiley.com/doi/10.1002/0471433519.ch1/summary" rel="nofollow">Clustering Methods and Their Uses in Computational Chemistry </a>.</p>

CC BY-SA 2.5
2010-11-15T16:00:50.160Z
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.
Simd
CC BY-SA 2.5
2010-11-15T16:26:51.997Z
how do you cover SVMs without linear algebra?
Lev Reyzin
CC BY-SA 2.5
2010-11-15T17:00:11.250Z
I was hoping to teach them the minimum prerequisites for it in my course. Maybe that was too optimistic :-)
Simd
CC BY-SA 3.0
2014-05-09T18:34:00.517Z
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.)
Simd
CC BY-SA 3.0
2010-11-15T15:32:53.430Z
2016-06-01T13:32:12.310Z
2016-06-01T13:32:12.310Z
Aaron Sterling
<p>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. </p>

CC BY-SA 2.5
2010-11-15T15:55:32.063Z
2010-11-15T15:55:32.063Z
Christina Boucher
<p><a href="http://repository.cmu.edu/cgi/viewcontent.cgi?article=1175&amp;context=compsci" rel="nofollow">This algorithm</a> uses graph minimum cuts to classify large amount of unlabeled samples using only small amount of labelled samples. </p>

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

<p><strong>Ref:</strong>
Blum, A., &amp; Chawla, S. (2001). Learning from labeled and unlabeled data using graph mincuts.</p>

<p><em>Self promotion</em> Visualization of the algorithm on <a href="https://www.youtube.com/watch?v=gmcV4-sxlSw" rel="nofollow">youtube</a>.</p>

CC BY-SA 3.0
2014-05-08T06:44:53.137Z
2014-05-09T20:18:56.943Z
2014-05-09T20:18:56.943Z
Pratik Deoghare
<p>I see that Expectation Maximization (EM) has not been mentioned, and it's certainly "up there" in the top 10:
<a href="http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf" rel="nofollow noreferrer">http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf</a> .</p>

CC BY-SA 4.0
2016-05-24T15:49:50.133Z
2019-04-25T08:53:28.627Z
2019-04-25T08:53:28.627Z
Aryeh
<p>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.</p>

<p>You can use the well known survey of Littman and al.: <a href="http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html" rel="nofollow">http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html</a></p>

CC BY-SA 2.5
2011-01-31T10:49:15.403Z
2011-01-31T10:49:15.403Z
Lamine
<p>You can cover some algorithms which are classic or with good intuition.</p>

<p>For example, C4.5 and CART, which are classic decision tree algorithms.</p>

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

<p>Furthermore, deep learning is also a good topic, because it is very hot.</p>

CC BY-SA 3.0
2014-05-08T15:20:38.877Z
[deep learning web survey/links](http://vzn1.wordpress.com/2013/10/28/deep-learning-ai-artificialreal-brain-research-leadscompendiumcritical-masssingularity/)
vzn
CC BY-SA 3.0
2014-05-08T13:57:33.807Z
2014-05-09T10:56:49.947Z
2014-05-09T10:56:49.947Z
jet
<p>Native bayes and Bayesian network, decision tree algorithms are quite easy to visualize than starting with a neutral network or svm </p>

CC BY-SA 2.5
2010-11-17T05:28:45.250Z
2010-11-17T05:28:45.250Z
Prabu 
<p>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).</p>

<p>It does not require deep mathematical skills.</p>

<p>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).</p>

CC BY-SA 3.0
2014-05-09T18:32:01.253Z
Is there any important problem for which it is the best method? I mean it certainly isn't for TSP for example.
Simd
CC BY-SA 3.0
2014-05-09T15:19:32.933Z
2014-05-09T19:55:36.257Z
2014-05-09T19:55:36.257Z
Per Alexandersson
<p>You can cover <a href="http://cseweb.ucsd.edu/~yfreund/papers/IntroToBoosting.pdf" rel="nofollow">boosting</a>.  It's very clever, easy to implement, is widely used in practice, and doesn't require much prerequisite knowledge to understand.</p>

CC BY-SA 2.5
2010-11-15T20:39:48.293Z
I've presented some parts of the survey by Arora et al.  (http://www.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.
Dan
CC BY-SA 3.0
2010-11-15T16:28:45.863Z
2016-06-01T13:35:26.077Z
2016-06-01T13:35:26.077Z
Lev Reyzin
<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-15T13:53:50.253Z
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?
Sadeq Dousti
CC BY-SA 2.5
2010-11-15T14:37:18.603Z
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 http://en.wikipedia.org/wiki/List_of_machine_learning_algorithms
Deyaa
CC BY-SA 2.5
2010-11-16T03:37:12.227Z
Perhaps some ideas from how Hal Daume teaches Machine Learning -- http://nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-16T03:59:49.727Z
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 http://www.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.
matus
CC BY-SA 3.0
2014-05-09T22:36:15.963Z
see eg [genetic algorithms](http://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms) or also [deep learning](http://vzn1.wordpress.com/2013/10/28/deep-learning-ai-artificialreal-brain-research-leadscompendiumcritical-masssingularity/)
vzn
CC BY-SA 4.0
2019-04-26T01:52:05.847Z
I'm not leaving this as an answer because it's not strictly speaking ML, but Fast Fourier Transform and Discrete Fourier Transform are extremely important algorithms that are used in AI.
Stella Biderman
<ds.algorithms><machine-learning><teaching>
Great algorithms, machine learning and no linear algebra
Simd
# Great algorithms, machine learning and no linear algebra

(Asked by: username_0 on 2010-11-15)

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.

**Tags:** ds.algorithms, machine-learning, teaching
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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 http://en.wikipedia.org/wiki/List_of_machine_learning_algorithms  
> **username_3**: Perhaps some ideas from how Hal Daume teaches Machine Learning -- http://nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html  
> **username_4**: 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 http://www.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.  
> **username_5**: see eg [genetic algorithms](http://cstheory.stackexchange.com/questions/427/what-are-some-real-world-applications-for-genetic-algorithms) or also [deep learning](http://vzn1.wordpress.com/2013/10/28/deep-learning-ai-artificialreal-brain-research-leadscompendiumcritical-masssingularity/)  
> **username_6**: I'm not leaving this as an answer because it's not strictly speaking ML, but Fast Fourier Transform and Discrete Fourier Transform are extremely important algorithms that are used in AI.  

---

## 9 answers

### Answer by username_8 on 2010-11-15. Score: 29 | Accepted answer

You can cover [boosting](http://cseweb.ucsd.edu/~yfreund/papers/IntroToBoosting.pdf). It's very clever, easy to implement, is widely used in practice, and doesn't require much prerequisite knowledge to understand.

> **Comments:**
> **username_16**: I've presented some parts of the survey by Arora et al.  (http://www.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.  

---

### Answer by username_7 on 2010-11-15. Score: 9

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](http://en.wikipedia.org/wiki/Support_vector_machine), 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](http://onlinelibrary.wiley.com/doi/10.1002/0471433519.ch1/summary) .

> **Comments:**
> **username_0**: 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.  
> **username_8**: how do you cover SVMs without linear algebra?  
> **username_0**: I was hoping to teach them the minimum prerequisites for it in my course. Maybe that was too optimistic :-)  
> **username_0**: 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.)  

---

### Answer by username_9 on 2010-11-15. Score: 5

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.


---

### Answer by username_10 on 2014-05-08. Score: 4

[This algorithm](http://repository.cmu.edu/cgi/viewcontent.cgi?article=1175&context=compsci) 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](https://www.youtube.com/watch?v=gmcV4-sxlSw).


---

### Answer by username_11 on 2016-05-24. Score: 3

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> .


---

### Answer by username_12 on 2011-01-31. Score: 1

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>


---

### Answer by username_13 on 2014-05-08. Score: 1

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.

> **Comments:**
> **username_5**: [deep learning web survey/links](http://vzn1.wordpress.com/2013/10/28/deep-learning-ai-artificialreal-brain-research-leadscompendiumcritical-masssingularity/)  

---

### Answer by username_14 on 2010-11-17. Score: 0

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


---

### Answer by username_15 on 2014-05-09. Score: 0

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).

> **Comments:**
> **username_0**: Is there any important problem for which it is the best method? I mean it certainly isn't for TSP for example.  

---

