Por que estudar otimização convexa para aprendizado de máquina teórico?

27

Estou trabalhando no aprendizado de máquina teórico - no aprendizado de transferência, para ser específico - para meu doutorado.

  • Por curiosidade, por que devo fazer um curso sobre otimização convexa?

  • Que conclusões da otimização convexa posso usar em minha pesquisa sobre aprendizado teórico de máquinas?

Upendra Pratap Singh
fonte
2
Não está claro se você está se opondo à parte convexa, à parte de otimização ou a ambas.
Mehrdad 26/01
Observe que a resposta que você aceitou está claramente errada. Talvez você possa dar uma olhada nesta pergunta novamente e escolher uma resposta que faça muito mais sentido.
Xj7
A otimização convexa e a otimização matemática são uma ferramenta para construir modelos - essas técnicas são usadas para construir modelos / controlar / encontrar parâmetros de fenômenos compreensíveis até uma certa incerteza.
Bruziuz
O Machine Learning trata da construção de aproximação de funções, como métodos de contagem, e, até onde você conhece uma das funções de seleção de conceito, que minimiza aproximadamente a perda (que é não convexa ou até pior inclui variáveis ​​indicadoras), para que o ML funcione bem com a otimização não convexa.
Bruziuz
FYI "A otimização convexa não pode ser usada para aprendizado profundo - S.Boyd" - youtu.be/uF3htLwUHn0?t=2810
bruziuz

Respostas:

59

Os algoritmos de aprendizado de máquina usam otimização o tempo todo. Minimizamos a perda, o erro ou maximizamos algum tipo de função de pontuação. A descida de gradiente é o algoritmo de otimização "olá mundo", coberto provavelmente em qualquer curso de aprendizado de máquina. É óbvio no caso de modelos de regressão ou classificação, mas mesmo com tarefas como clustering, estamos procurando uma solução que se encaixe perfeitamente aos nossos dados (por exemplo, k-means minimiza a soma dos quadrados dentro do cluster). Portanto, se você quiser entender como os algoritmos de aprendizado de máquina funcionam, aprender mais sobre otimização ajuda. Além disso, se você precisar fazer coisas como ajuste de hiperparâmetro, também estará usando diretamente a otimização.

Alguém poderia argumentar que a otimização convexa não deve ser tão interessante para o aprendizado de máquina, pois, em vez de lidar com funções convexas , geralmente encontramos superfícies de perda como a abaixo, que estão longe de ser convexas .

Exemplo de cenário de perda não convexa da vida real.

(fonte: https://www.cs.umd.edu/~tomg/projects/landscapes/ e arXiv: 1712.09913 )

No entanto, como mencionado em outras respostas, a otimização convexa é mais rápida, mais simples e menos intensiva em termos computacionais; portanto, é mais fácil "convexar" um problema (torne a otimização convexa amigável) e use a otimização não convexa. Por exemplo, algoritmos de descida de gradiente e similares são comumente usados ​​no aprendizado de máquina, especialmente para redes neurais, porque "trabalham", escalam e são amplamente implementados em diferentes softwares; no entanto, eles não são os melhores que podemos obter e ter suas armadilhas. , conforme discutido pela palestra de Ali Rahimi no NIPS 2017 .

Por outro lado, algoritmos de otimização não convexos, como algoritmos evolutivos, parecem estar ganhando cada vez mais reconhecimento na comunidade de ML, por exemplo, o treinamento de redes neurais por neuroevolução parece ser um tópico de pesquisa recente (consulte também arXiv: 1712.07897 ).

Tim
fonte
5
esta resposta parece não abordar "convexo"
Haitao Du
@ hxd1011 eu comentei sobre isso.
Tim
Ótima resposta! Realmente aborda o quanto a otimização é crítica para o ML e como o ML simplifica usando aproximações convexas que funcionam com descida de gradiente.
ChuckCottrill 28/01
Essa deve ser a resposta aceita.
Jan KUKACKA
11

Eu acho que há duas perguntas aqui.

  • Por que estudar otimização
  • Por que otimização convexa

Eu acho que o @Tim tem uma boa resposta sobre o porquê da otimização. Concordo plenamente e recomendaria qualquer pessoa interessada em aprendizado de máquina para dominar a otimização contínua. Porque o processo de otimização / encontrar a melhor solução ao longo do tempo, é o processo de aprendizado para um computador.

Quero falar mais sobre por que estamos interessados ​​em funções convexas. O motivo é simples: otimizações convexas são "mais fáceis de resolver" e temos muito algoritmo confiável para resolver.

Mas o mundo é convexo? Não. Por que obcecado com a convexidade? Verifique esta metáfora

Um policial vê um homem bêbado procurando algo sob a luz da rua e pergunta o que o bêbado perdeu. Ele diz que perdeu as chaves e os dois olham juntos sob a luz da rua. Depois de alguns minutos, o policial pergunta se tem certeza de que os perdeu aqui, e o bêbado responde que não, e que os perdeu no parque. O policial pergunta por que ele está pesquisando aqui, e o bêbado responde: "é aqui que a luz está".

Haitao Du
fonte
2
Mas metaforicamente, é por isso que você recebe uma lanterna. É difícil impossível procurar as chaves no escuro; portanto, você adapta o problema a um que sabe resolver. Se você trabalha com um problema com algoritmos não convexos e apresenta uma solução que custará 3 milhões de dólares, e eu trabalho com um problema semelhante com otimização convexa, aceite minha resposta e encontre uma solução para o problema não convexo que custa 2 milhões de dólares, encontrei uma resposta melhor.
prosfilaes 27/01
Esta resposta é falha em muitos níveis. Comparar a análise convexa com o efeito da luz da rua está errado . Aconselho você a consultar o livro introdutório Otimização Convexa de Boyd e Vandenberghe para aprender mais sobre o assunto.
Digio
2

O ponto mais importante é que o aprendizado de máquina é aplicado a problemas em que não há uma solução ideal disponível. O melhor que você pode fazer é encontrar uma boa aproximação.

Por outro lado, quando você tem um problema de otimização, existe uma solução ideal, mas geralmente ela não pode ser encontrada em tempo razoável ou com poder de processamento razoável.

As ferramentas e algoritmos que você usa são fundamentalmente diferentes. Portanto, embora eu diria que não há benefício imediato em ter uma aula de otimização, é sempre bom saber um pouco sobre os campos relacionados. Se você conseguir reconhecer um problema de otimização, saberá que não deve enfrentá-lo com algoritmos de aprendizado de máquina, mas sim com algoritmos de otimização. Só isso vale muito, eu diria.

Toby
fonte
33
Sim, no aprendizado de máquina, estamos procurando as melhores aproximações. Mas você está errado ao dizer que as duas coisas são "fundamentalmente diferentes". Os algoritmos de ML usam otimização para minimizar as funções de perda e encontrar os parâmetros ideais, dados os objetivos e os dados. Quando você está ajustando seus hiperparâmetros, está procurando a combinação ideal deles. Em cada um dos casos, você está maximizando ou minimizando algo para atingir seu objetivo, e está usando algum tipo de otimização.
Tim
@ Tim: É verdade, eu deveria ter formulado isso de maneira diferente.
Toby
17
se você concorda, provavelmente deve reformulá-lo.
Tim
19
Esta resposta está evidentemente errada. Um número significativo de problemas de aprendizado de máquina se resume a problemas de otimização.
Reintegrar Monica
2
A alegação de que em "problemas de otimização a solução ideal geralmente não pode ser encontrada" está incorreta. Especialmente no contexto da otimização convexa (que é o que o OP está perguntando), a solução ideal pode ser facilmente encontrada (por exemplo, a descida do gradiente com a taxa de aprendizado decadente é garantida para convergir para o ideal de uma função convexa). O grande problema é que muitos problemas no aprendizado de máquina não são convexos .
Jan KUKACKA
2

Como disse hxd1011, os problemas convexos são mais fáceis de resolver, tanto teoricamente quanto (normalmente) na prática. Portanto, mesmo para problemas não convexos, muitos algoritmos de otimização começam com a "etapa 1. reduza o problema a um convexo" (possivelmente dentro de um loop while).

O mesmo ocorre com a busca de raiz não linear. Normalmente, a solução (por exemplo, com o método de Newton) vai "passo 1. Reduza para um problema linear, porque sabemos como resolvê-los".

Federico Poloni
fonte
1

Se seus interesses estão na otimização (convexa) aplicada ao aprendizado profundo (você menciona o aprendizado de transferência, que é amplamente usado na prática com redes neurais), recomendo fortemente que você considere a leitura do capítulo 8 (otimização para o treinamento de redes neurais profundas) de http : //www.deeplearningbook.org/

Há uma discussão sobre otimização convexa e por que ela ainda não teve tanto sucesso quando aplicada redes neurais profundas. Claro, talvez você possa fazer pesquisas nessa área que mudarão o consenso atual!

FXQuantTrader
fonte
0

Como ouvi de Jerome H. Friedman, os métodos desenvolvidos no Machine Learning não são, de fato, pertencentes à comunidade do Machine Learning.

Do meu ponto de vista, o Machine Learning é mais como uma coleção de vários métodos de outros campos.

Do ponto de vista do aprendizado estatístico, as três principais questões para regressão e classificação são:

  1. Qual é a família de funções da qual você puxa o aproximador

  2. O que é um critério como você puxa uma função

  3. O que é um método para encontrar a melhor função


Para operar de alguma maneira construtiva em (1) - não é tão óbvio como o uso da otimização matemática pode ajudar

Para operar de alguma maneira construtiva em (2) - é óbvio que objetivo é o objetivo. E a otimização da matemática pode ajudar nisso.

Para operar de alguma maneira construtiva em (3) - você precisa de otimização matemática.


Existem várias partes da otimização matemática:

  1. Otimização convexa / Análise convexa - área muito legal da matemática. A não diferenciabilidade não é um problema. E há 50 generalizações de funções convexas, das quais mais duas úteis em termos de aplicação são quasiconvexas e log-côncavas.

Também existem maneiras de lidar com a "estocástica" de alguma forma, mesmo "Ninguém sabe como resolver a otimização estocástica convexa"

  1. Otimização não-convexa - geralmente as pessoas com isso significam algo que é objetivo contínuo, mas a curvatura pode variar. As pessoas neste planeta não sabem como resolvê-lo com precisão. E, de fato, todos os métodos me alavancam (1)

  2. Otimização combinatória - é ainda mais selvagem do que (2), agora para parâmetros que você acha que não pode aplicar menos operador. Um exemplo é "regiões" nas Árvores de Decisão. Portanto, existem duas maneiras de lidar com isso: a) Convexifique o problema e use os métodos de (1) b) Faça força bruta. Não funciona para um grande número de parâmetros. c) Faça força bruta, mas com alguns passos gananciosos. É algo que a CART faz.


Então, pelo menos, acho que convido você a:

I) A otimização convexa é essencial para a maioria dos problemas de otimização.

II) "01:15 A otimização é, na verdade, um assunto mais grande que o ML ou AI, mas é um assunto maior, de fato." ( https://www.youtube.com/watch?v=uF3htLwUHn0&t=992s )

bruziuz
fonte
Isso é um pouco breve para os padrões deste site, como resposta - você acha que poderia expandi-lo? Caso contrário, pode ser mais adequado como um comentário.
Silverfish
Está bem. Vou expandir, mas, na verdade, é possível escrever um artigo sobre a conexão com vários campos. Na verdade, eu perguntei a Stephen P. Boyd sobre uma pergunta relativa à qual as pessoas pensavam anteriormente e quando - youtu.be/XV1E-Jnc4SU?t=242 . Ele disse que o mundo de hoje está quebrado.
Bruziuz
11
@ Silverfish eu atualizei, agora é um texto longo em vez de uma frase.
Bruziuz