Grandes algoritmos, aprendizaje automático y sin álgebra lineal

30

Enseño un curso de algoritmos avanzados y me gustaría incluir algunos temas relacionados con el aprendizaje automático que serán de interés para mis alumnos. Como resultado, me gustaría escuchar las opiniones de las personas sobre los resultados algorítmicos más interesantes / mejores actualmente en el aprendizaje automático. La restricción potencialmente complicada es que los estudiantes no tendrán ningún conocimiento previo particular de álgebra lineal u otros temas principales en el aprendizaje automático.

Esto es realmente para entusiasmarlos con el tema y para hacerles saber que ML es un área de investigación potencialmente emocionante para expertos en algoritmos.

EDITAR: Este es un curso de pregrado de último año (ya que no tenemos cursos de posgrado en el Reino Unido en general). Habrán realizado al menos un curso de algoritmos básicos de antemano y probablemente lo hayan hecho bien al haber elegido el curso de seguimiento avanzado. El programa de estudios actual del curso avanzado tiene temas como hashing perfecto, filtros Bloom, árboles de Van Emde Boas, programa lineal, aprox. algoritmos para problemas NP-difíciles, etc. No tengo la intención de gastar más de una conferencia exclusivamente en ML, pero si algo es realmente relevante tanto para un curso de algoritmos como para un ML, por supuesto, también podría incluirse.

Rafael
fuente
1
Por favor aclare dos cosas: 1) ¿Es un curso de pregrado o un curso de posgrado? ¿Qué cursos relacionados (si los hay) han aprobado? 2) ¿Cuánto tiempo quieres dedicar a ML?
MS Dousti
3
hmmm Creo que el álgebra lineal es imprescindible y un curso básico importante, al menos en el lado del aprendizaje automático. y creo que el modelo lineal es una muy buena introducción a los algoritmos de aprendizaje automático. Puede pensar en otros algoritmos de nivel básico como el vecino K más cercano o algoritmos de regresión logística. podría esto ayudarlo en.wikipedia.org/wiki/List_of_machine_learning_algorithms
Deyaa
1
Tal vez algunas ideas de cómo Hal Daume enseña Machine Learning - nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html
Yaroslav Bulatov
3
Estimado Raphael, Avrim Blum generalmente concluye su clase de algoritmos de nivel superior con aprendizaje automático y algunos temas relacionados; una iteración reciente se encuentra en el siguiente enlace cs.cmu.edu/~avrim/451f09/index.html , y puede obtener más información de su página web. Después de haber recibido asistencia técnica y haber tomado esta clase, puedo decir que (y su material final) son recibidos muy calurosamente por los estudiantes.
matus
1
ver, por ejemplo, algoritmos genéticos o también aprendizaje profundo
vzn

Respuestas:

29

Puedes cubrir el impulso . Es muy inteligente, fácil de implementar, se usa ampliamente en la práctica y no requiere mucho conocimiento previo para entenderlo.

Lev Reyzin
fuente
55
He presentado algunas partes de la encuesta de Arora et al. ( cs.princeton.edu/~arora/pubs/MWsurvey.pdf ) en la clase de teoría de posgrado hace unos años. A la gente parecía gustarle y creo que casi no se necesitan antecedentes para comprender este material.
Danu
9

Si solo quiere abrir su apetito en una sola conferencia, puede ser más emocionante presentar una aplicación poderosa. Por ejemplo, las máquinas de vectores de soporte y otros algoritmos de aprendizaje automático se utilizan en quimioinformática para el descubrimiento de fármacos.

El problema de aprendizaje es esencialmente: dado un comportamiento que queremos que exhiba un químico, diseñe una estructura que exhiba ese comportamiento deduciéndolo de una base de datos de estructuras conocidas que exhiben comportamientos similares (o diferentes). El problema de aprendizaje tiene una arruga adicional: el nuevo medicamento debe estar "distante" en la estructura global de los medicamentos previamente conocidos, para poder fundar un patrimonio de patentes.

Una fuente son los métodos de agrupamiento y sus usos en química computacional .

Aaron Sterling
fuente
1
Gracias por la referencia Estaba pensando en tal vez enseñar SVM como una aplicación de optimización convexa. Eso relacionaría muy bien la parte de algoritmos con la parte de ML.
Raphael el
2
¿Cómo cubre SVMs sin álgebra lineal?
Lev Reyzin
Tenía la esperanza de enseñarles los requisitos mínimos para ello en mi curso. Tal vez eso fue demasiado optimista :-)
Raphael
¿Todavía hay ejemplos importantes donde las máquinas de vectores de soporte son la mejor opción? Noto que en las competiciones de kaggle, por ejemplo, nunca son la parte principal de una entrada ganadora. Al menos no ninguno que haya visto recientemente. (Por supuesto, me corrigen).
Lembik
7

K-Means y KNN son muy potentes y no requieren ningún álgebra lineal, excepto el cálculo de distancias de puntos.


fuente
K-Means en particular es un algoritmo muy potente. Es increíblemente efectivo a pesar de no tener límites probados en el rendimiento de su función objetivo, hasta tal punto que es casi como la complejidad polinómica efectiva del algoritmo Simplex (a pesar de la complejidad exponencial real). Su versión en línea también es útil en aplicaciones de datos a gran escala.
Elliot JJ
5

La segunda parte de "Redes neuronales y aprendizaje automático" de Christopher Bishop (en MSR) es sobre algoritmos en ML. Los libros de texto de Bishop se usan comúnmente para libros de texto de posgrado (y luego de pregrado) y están extremadamente bien escritos.

Christina Boucher
fuente
4

Este algoritmo utiliza cortes mínimos de gráficos para clasificar una gran cantidad de muestras sin etiquetar utilizando solo una pequeña cantidad de muestras etiquetadas.

Es estudiante de pregrado amigable. Le expliqué esto a unos pocos estudiantes elegidos al azar y lo entendieron.

Ref: Blum, A. y Chawla, S. (2001). Aprendiendo de datos etiquetados y no etiquetados usando mincuts de gráficos.

Auto promoción Visualización del algoritmo en youtube .

Pratik Deoghare
fuente
1

Los algoritmos de refuerzo de aprendizaje (especialmente Q-Learning y SARSA) son bastante simples de entender y muy potentes para resolver algunos problemas de aprendizaje. No requieren ningún conocimiento avanzado en álgebra lineal, a excepción de la prueba de convergencia y la tasa de convergencia.

Puede usar la conocida encuesta de Littman y otros: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html

Lamina
fuente
1

Puede cubrir algunos algoritmos que son clásicos o con buena intuición.

Por ejemplo, C4.5 y CART, que son algoritmos clásicos de árbol de decisión.

También puede cubrir algunos métodos de conjunto (por ejemplo, AdaBoost (Boosting), Bagging), que tienen un muy buen rendimiento en aplicaciones del mundo real.

Además, el aprendizaje profundo también es un buen tema, porque es muy candente.

chorro
fuente
0

Bayes nativas y red bayesiana, los algoritmos de árbol de decisión son bastante fáciles de visualizar que comenzar con una red neutral o svm

Prabu
fuente
0

La programación genética es realmente genial. Utiliza la inspiración de la biología y puede aplicarse a una gran cantidad de problemas (por ejemplo, problema de n-reinas y TSP).

No requiere habilidades matemáticas profundas.

EDITAR: solo requiere una forma de estimar qué tan buena es una solución potencial. Se puede usar, por ejemplo, para adivinar la regla detrás de una serie de números, encontrar problemas de mínimos / máximos a múltiples variaciones y buscar espacios de parámetros enormes. Es adecuado cuando no está interesado en la solución óptima, pero cuando lo hará una solución lo suficientemente buena. Creo que esto se ha utilizado para encontrar buenas estrategias para los juegos (órdenes de construcción en Starcraft 2 y juego óptimo en Mario).

Por Alexandersson
fuente
¿Hay algún problema importante para el cual es el mejor método? Quiero decir que ciertamente no es para TSP, por ejemplo.
Lembik