Grandes algoritmos, aprendizado de máquina e nenhuma álgebra linear

30

Dou aulas de algoritmos avançados e gostaria de incluir alguns tópicos relacionados ao aprendizado de máquina que serão do interesse dos meus alunos. Como resultado, eu gostaria de ouvir as opiniões das pessoas sobre os resultados algorítmicos atualmente mais interessantes / maiores no aprendizado de máquina. A restrição potencialmente complicada é que os alunos não terão nenhum conhecimento prévio específico de álgebra linear ou outros tópicos principais no aprendizado de máquina.

Isso realmente os excita sobre o assunto e informa que o ML é uma área de pesquisa potencialmente interessante para especialistas em algoritmos.

EDIT: Este é um curso de graduação do último ano (já que não temos cursos de pós-graduação no Reino Unido). Eles terão realizado pelo menos um curso básico de algoritmos e presumivelmente se saíram bem ao escolher o curso avançado de acompanhamento. O currículo atual do curso avançado inclui tópicos como hash perfeito, filtros Bloom, árvores van Emde Boas, programa linear, aprox. algoritmos para problemas difíceis de NP etc. Não pretendo passar mais de uma palestra exclusivamente em ML, mas se algo for realmente relevante tanto para um curso de algoritmos quanto para um de ML, é claro que também poderia ser incluído.

Rafael
fonte
11
Esclareça duas coisas: 1) É um curso de graduação ou de pós-graduação? Quais cursos relacionados (se houver) foram aprovados? 2) Quanto tempo você quer dedicar ao ML?
MSDousti
3
hmmm, acho que a álgebra linear é uma obrigação e um curso básico importante, pelo menos no lado do aprendizado de máquina. e acho que o modelo linear é uma introdução muito boa aos algoritmos de aprendizado de máquina. você pode pensar em outros algoritmos de nível básico, como o vizinho mais próximo K ou algoritmos de regressão logística. pode esta ajuda você en.wikipedia.org/wiki/List_of_machine_learning_algorithms
Deyaa
11
Talvez algumas idéias de como Hal Daume ensina Machine Learning - nlpers.blogspot.com/2010/04/how-i-teach-machine-learning.html
Yaroslav Bulatov
3
Caro Raphael, Avrim Blum normalmente conclui sua classe de algoritmos de nível sênior com aprendizado de máquina e alguns tópicos relacionados; uma iteração recente está no seguinte link cs.cmu.edu/~avrim/451f09/index.html , e você pode obter mais informações em sua página da web. Tendo ambos assistido e assistido a esta aula, posso dizer que (e seu material final) são muito calorosamente recebidos pelos alunos.
matus
11
ver por exemplo, algoritmos genéticos ou também o aprendizado profundo
vzn

Respostas:

29

Você pode cobrir o aumento . É muito inteligente, fácil de implementar, é amplamente utilizado na prática e não requer muito conhecimento prévio para entender.

Lev Reyzin
fonte
5
Apresentei algumas partes da pesquisa de Arora et al. ( cs.princeton.edu/~arora/pubs/MWsurvey.pdf ) na aula de teoria dos graduados alguns anos atrás. As pessoas pareciam gostar e acho que você quase não precisa de experiência para entender esse material.
Danu
9

Se você deseja apenas estimular o apetite em uma única palestra, pode ser mais emocionante apresentar uma aplicação poderosa. Por exemplo, máquinas de vetores de suporte e outros algoritmos de aprendizado de máquina são usados ​​na quimioinformática para descoberta de medicamentos.

O problema de aprendizagem é essencialmente: dado um comportamento que queremos que um produto químico exiba, crie uma estrutura que exiba esse comportamento deduzindo-o de um banco de dados de estruturas conhecidas que exibem comportamentos semelhantes (ou diferentes). O problema do aprendizado tem uma ruga extra: o novo medicamento precisa estar "distante" na estrutura global dos medicamentos anteriormente conhecidos, a fim de fundar uma patente.

Uma fonte é Métodos de agrupamento e seus usos na química computacional .

Aaron Sterling
fonte
11
Obrigado pela referência. Eu estava pensando em talvez ensinar SVMs como uma aplicação de otimização convexa. Isso relacionaria bem a parte dos algoritmos com a parte ML.
Raphael
2
como você cobre SVMs sem álgebra linear?
Lev Reyzin
Eu esperava ensinar a eles os pré-requisitos mínimos para isso no meu curso. Talvez tenha sido muito otimista :-)
Raphael
Ainda existem exemplos importantes em que as máquinas de vetores de suporte são a melhor escolha? Percebo que nas competições de kaggle, por exemplo, elas nunca são a parte principal de uma participação vencedora. Pelo menos, nenhum que eu tenha visto recentemente. (Estou a ser corrigido é claro.)
Lembik
7

K-Means e KNN são muito poderosos e não requerem Álgebra Linear, exceto o cálculo das distâncias dos pontos.


fonte
K-Means, em particular, é um algoritmo muito potente. É incrivelmente eficaz, apesar de não ter limites comprovados no desempenho da função objetivo, em uma extensão tão assustadora que é quase como a complexidade polinomial efetiva do algoritmo Simplex (apesar da complexidade exponencial real). Sua versão online também é útil em aplicativos de dados em larga escala.
Elliot JJ
5

A segunda parte de "Redes Neurais e Aprendizado de Máquina", de Christopher Bishop (na MSR), trata de algoritmos em ML. Os livros didáticos de Bishop são comumente usados ​​para livros de pós-graduação (e mais tarde na graduação) e são extremamente bem escritos.

Christina Boucher
fonte
4

Esse algoritmo usa cortes mínimos de gráfico para classificar grande quantidade de amostras não rotuladas usando apenas uma pequena quantidade de amostras rotuladas.

Sua graduação amigável. Eu expliquei isso para alguns graduandos escolhidos aleatoriamente e eles entenderam.

Ref: Blum, A., & Chawla, S. (2001). Aprendendo com dados rotulados e não rotulados usando atalhos de gráfico.

Auto-promoção Visualização do algoritmo no youtube .

Pratik Deoghare
fonte
1

Os algoritmos de aprendizado por reforço (especialmente Q-Learning e SARSA) são bastante simples de entender e muito poderosos para resolver alguns problemas de aprendizado. Eles não exigem nenhum conhecimento avançado em álgebra linear, exceto prova de convergência e taxa de convergência.

Você pode usar a bem conhecida pesquisa de Littman e outros: http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/kaelbling96a-html/rl-survey.html

Lamine
fonte
1

Você pode cobrir alguns algoritmos clássicos ou com boa intuição.

Por exemplo, C4.5 e CART, que são algoritmos clássicos de árvore de decisão.

Você também pode abordar alguns métodos de ensemble (por exemplo, AdaBoost (Boosting), Bagging), que têm um desempenho muito bom em aplicativos do mundo real.

Além disso, o aprendizado profundo também é um bom tópico, porque é muito quente.

jato
fonte
0

Bayes nativos e rede bayesiana, algoritmos de árvore de decisão são bastante fáceis de visualizar do que começar com uma rede neutra ou svm

Prabu
fonte
0

A programação genética é muito legal. Ele se inspira na biologia e pode ser aplicado a um grande número de problemas (por exemplo, problema das n rainhas e TSP).

Não requer habilidades matemáticas profundas.

EDIT: Requer apenas uma maneira de estimar quão boa é uma solução em potencial. Pode ser usado, por exemplo, para adivinhar a regra por trás de uma série de números, localizando mínimos / máximos para problemas com diversas variáveis ​​e pesquisando espaços de parâmetros enormes. É adequado quando você não está interessado na solução ideal, mas quando uma solução boa o suficiente serve. Acredito que isso tenha sido usado para encontrar boas estratégias para jogos (ordens de construção em Starcraft 2 e jogabilidade ideal em Mario).

Per Alexandersson
fonte
Existe algum problema importante para o qual é o melhor método? Quero dizer, certamente não é para TSP, por exemplo.
Lembik