Grands algorithmes, apprentissage automatique et aucune algèbre linéaire

30

J'enseigne un cours d'algorithmes avancés et j'aimerais inclure quelques sujets liés à l'apprentissage automatique qui intéresseront mes étudiants. En conséquence, j'aimerais entendre l'opinion des gens sur les résultats algorithmiques actuellement les plus intéressants / les plus importants en apprentissage automatique. La contrainte potentiellement délicate est que les élèves n'auront aucune connaissance préalable particulière de l'algèbre linéaire ou des autres sujets principaux de l'apprentissage automatique.

C'est vraiment pour les exciter sur le sujet et pour leur faire savoir que le ML est un domaine de recherche potentiellement passionnant pour les experts en algorithmes.

EDIT: Il s'agit d'un cours de premier cycle de dernière année (car nous n'avons pas de cours d'études supérieures au Royaume-Uni dans l'ensemble). Ils auront suivi au moins un cours d'algorithmes de base au préalable et auront vraisemblablement bien réussi en ayant choisi le cours de suivi avancé. Le programme actuel du cours avancé comprend des sujets tels que le hachage parfait, les filtres Bloom, les arbres van Emde Boas, le prog linéaire, env. algorithmes pour les problèmes NP-difficiles, etc. Je n'ai pas l'intention de passer plus d'une conférence exclusivement sur le ML, mais si quelque chose est vraiment pertinent à la fois pour un cours d'algorithmes et pour un cours de ML, alors bien sûr, cela pourrait aussi être inclus.

Raphael
la source
1
Veuillez clarifier deux choses: 1) S'agit-il d'un cours de premier cycle ou d'un cours d'études supérieures? Quels cours connexes (le cas échéant) ont-ils réussis? 2) Combien de temps souhaitez-vous consacrer au ML?
MS Dousti
3
hmmm je pense que l'algèbre linéaire est un must et un cours de base important, au moins en ce qui concerne l'apprentissage automatique. et je pense que le modèle linéaire est une très bonne introduction aux algorithmes d'apprentissage automatique. vous pouvez penser à d'autres algorithmes de niveau de base comme le K-plus proche voisin ou les algorithmes de régression logistique. cela pourrait-il vous aider en.wikipedia.org/wiki/List_of_machine_learning_algorithms
Deyaa
1
Peut-être quelques idées de la façon dont Hal Daume enseigne l'apprentissage automatique - nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html
Yaroslav Bulatov
3
Cher Raphael, Avrim Blum conclut généralement son cours d'algorithmes de niveau supérieur avec l'apprentissage automatique et quelques sujets connexes; une itération récente se trouve au lien suivant cs.cmu.edu/~avrim/451f09/index.html , et vous pouvez obtenir plus d'informations sur sa page Web. Ayant à la fois TA'd et pris ce cours, je peux dire qu'il (et son matériel de conclusion) sont très chaleureusement accueillis par les étudiants.
matus
1
voir par exemple les algorithmes génétiques ou aussi le deep learning
vzn

Réponses:

29

Vous pouvez couvrir le boosting . Il est très intelligent, facile à mettre en œuvre, est largement utilisé dans la pratique et ne nécessite pas beaucoup de connaissances préalables pour être compris.

Lev Reyzin
la source
5
J'ai présenté certaines parties de l'enquête d'Arora et al. ( cs.princeton.edu/~arora/pubs/MWsurvey.pdf ) dans la classe de théorie des diplômés il y a quelques années. Les gens semblaient l'aimer et je pense que vous n'avez presque pas besoin de connaissances pour comprendre ce matériel.
Danu
9

Si vous voulez simplement aiguiser leur appétit en une seule conférence, il pourrait être très excitant de présenter une application puissante. Par exemple, les machines à vecteurs de support et d'autres algorithmes d'apprentissage automatique sont utilisés en chimio-informatique pour la découverte de médicaments.

Le problème d'apprentissage est essentiellement: étant donné un comportement que nous voulons qu'un produit chimique expose, concevoir une structure qui présente ce comportement en le déduisant d'une base de données de structures connues qui présentent des comportements similaires (ou différents). Le problème d'apprentissage a une ride supplémentaire: le nouveau médicament doit être "éloigné" dans sa structure mondiale des médicaments précédemment connus, afin de fonder un domaine de brevet.

Une source est les méthodes de clustering et leurs utilisations en chimie computationnelle .

Aaron Sterling
la source
1
Merci pour la référence. Je pensais peut-être enseigner les SVM comme une application d'optimisation convexe. Cela relierait bien la partie algorithmes à la partie ML.
Raphael du
2
comment couvrez-vous les SVM sans algèbre linéaire?
Lev Reyzin
J'espérais leur enseigner les pré-requis minimum pour cela dans mon cours. C'était peut-être trop optimiste :-)
Raphael
Existe-t-il encore des exemples importants où les machines à vecteurs de support sont le meilleur choix? Je remarque que sur les compétitions de kaggle, par exemple, elles ne sont jamais la partie principale d'une participation gagnante. Du moins pas du tout que j'ai vu récemment. (Je me corrige bien sûr.)
Lembik
7

Les K-Means et KNN sont très puissants et ne nécessitent aucune algèbre linéaire sauf le calcul des distances de points.


la source
K-Means en particulier est un algorithme très puissant. Il est incroyablement efficace malgré le fait qu'il n'a pas fait ses preuves sur les performances de sa fonction objective, à un point tel que c'est presque comme la complexité polynomiale efficace de l'algorithme Simplex (malgré une réelle complexité exponentielle). Sa version en ligne est également utile dans les applications de données à grande échelle.
Elliot JJ
5

La deuxième partie de "Neural Networks and Machine Learning" de Christopher Bishop (au MSR) porte sur les algorithmes en ML. Les manuels de Bishop sont couramment utilisés pour les manuels des cycles supérieurs (et plus tard du premier cycle) et sont extrêmement bien écrits.

Christina Boucher
la source
4

Cet algorithme utilise des coupes minimales de graphe pour classer une grande quantité d'échantillons non étiquetés en utilisant seulement une petite quantité d'échantillons étiquetés.

Son amical de premier cycle. J'ai expliqué cela à quelques étudiants de premier cycle choisis au hasard et ils l'ont compris.

Réf: Blum, A., et Chawla, S. (2001). Apprendre à partir de données étiquetées et non étiquetées à l'aide de raccourcis graphiques.

Auto promotion Visualisation de l'algorithme sur youtube .

Pratik Deoghare
la source
1

Les algorithmes d'apprentissage par renforcement (en particulier Q-Learning et SARSA) sont assez simples à comprendre et très puissants pour résoudre certains problèmes d'apprentissage. Ils ne nécessitent aucune connaissance avancée en algèbre linéaire, à l'exception de la preuve de convergence et du taux de convergence.

Vous pouvez utiliser l'enquête bien connue de Littman et al.: Http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html

Lamine
la source
1

Vous pouvez couvrir certains algorithmes classiques ou avec une bonne intuition.

Par exemple, C4.5 et CART, qui sont des algorithmes d'arbre de décision classiques.

Vous pouvez également couvrir certaines méthodes d'ensemble (par exemple, AdaBoost (Boosting), Bagging), qui ont de très bonnes performances dans des applications du monde réel.

En outre, l'apprentissage en profondeur est également un bon sujet, car il fait très chaud.

jet
la source
0

Bayes natifs et réseau bayésien, les algorithmes d'arbre de décision sont assez faciles à visualiser que de démarrer avec un réseau neutre ou svm

Prabu
la source
0

La programmation génétique est vraiment cool. Il utilise l'inspiration de la biologie et peut être appliqué à un grand nombre de problèmes (par exemple, problème des n-reines et TSP).

Il ne nécessite pas de compétences mathématiques approfondies.

EDIT: Il suffit d'un moyen d'estimer la qualité d'une solution potentielle. Il peut être utilisé, par exemple, pour deviner la règle derrière une série de nombres, trouver des minima / maxima pour résoudre des problèmes à plusieurs variables et rechercher des espaces de paramètres énormes. Il convient lorsque vous n'êtes pas intéressé par la solution optimale, mais lorsqu'une solution suffisamment bonne fera l'affaire. Je crois que cela a été utilisé pour trouver de bonnes stratégies pour les jeux (construire des ordres dans Starcraft 2 et un jeu optimal dans Mario).

Per Alexandersson
la source
Y a-t-il un problème important pour lequel c'est la meilleure méthode? Je veux dire que ce n'est certainement pas pour TSP par exemple.
Lembik