Se as técnicas de aprendizado de máquina continuarem melhorando, qual é o papel da algorítmica no futuro?

23

Vamos olhar para o futuro daqui a 30 anos. Vamos ser otimistas e assumir que as áreas relacionadas ao aprendizado de máquina continuam se desenvolvendo tão rapidamente quanto o que vimos nos últimos 10 anos. Isso seria ótimo, mas qual seria o papel da algorítmica tradicional em um futuro tão próximo?

Aqui, por "algoritmos tradicionais", refiro-me ao processo usual que seguimos no TCS: formalizar um problema computacional bem definido , projetar algoritmos para resolver o problema e provar garantias formais de desempenho .

Agora, quais são as áreas de aplicação nas quais devemos usar o design e a análise tradicionais de algoritmos também no futuro, e é altamente improvável que quaisquer avanços no aprendizado de máquina tornem a algorítmica tradicional principalmente irrelevante?

No começo, isso pode parecer uma pergunta boba: é claro que precisaremos ser capazes de ordenar, pesquisar, indexar etc. também no futuro! É claro que precisamos fazer transformações de Fourier com eficiência, multiplicar matrizes grandes, encontrar caminhos mais curtos, resolver problemas de otimização linear!

Mas, novamente, uma vez que você começa a analisar mais profundamente os aplicativos em que tradicionalmente usamos os algoritmos que projetamos, não está claro que o design e a análise tradicionais de algoritmos sejam a resposta certa para esses problemas: em aplicativos relacionados à pesquisa , geralmente estamos interessados ​​em encontrar algo que seja parecido com o ser humano em algum sentido vago e mal definido (por exemplo, semelhança semântica), e não algo que seja ideal em algum sentido matemático (por exemplo, distância mínima de edição). Em aplicativos relacionados ao planejamento de rotas, geralmente estamos interessados ​​em encontrar rotas que sejam boas com base em exemplos (por exemplo, outras pessoas o preferem), e não em rotas que sejam ótimas em algum sentido matemático (por exemplo, distância mais curta ou preço mais barato). E uma vez que você tenha algum componente humano vago e mal definido, talvez seja melhor tentarmos ensinar o computador a produzir boas respostas com base em exemplos, em vez de tentar permitir que um pesquisador da TCS apareça com um problema computacional formal que podemos resolver por meio do design e análise tradicionais de algoritmos.

Então, quais são as áreas de aplicação (de preferência aplicações industriais reais e diretas) nas quais é absolutamente claro que o que temos feito em algoritmos no passado também será o caminho certo (e o único caminho possível) para progredir no futuro?

Os algoritmos usados ​​como sub-rotinas nas técnicas de aprendizado de máquina parecem um candidato óbvio à prova do futuro, mas isso depende muito da técnica de aprendizado de máquina que usamos e, como vimos nos últimos dez anos, isso pode mudar rapidamente .

ds.algorithms soft-question machine-learning Jukka Suomela
fonte
2
Isso parece depender se o problema corresponde naturalmente a um problema limpo que pode ser aproximado em DTIME ( ) para alguns que não é muito grande nem muito pequeno, mas não se acredita que seja aproximado em DTIME ( ). Se a tarefa é bastante "fácil" do ponto de vista de algoritmos, mas exige garantias em tempo real ou é difícil, mas não está claro como abstrair a dureza para resolvê-la por métodos disponíveis no mercado, o modelo do O processo subjacente oferecido pelo aprendizado de máquina (e outras técnicas estatísticas) pode ser apenas a abordagem mais prática. nccnc-ε
András Salamon
4
Sou cético em relação à visão de que as abordagens são exclusivas. Temos motivos para pensar que não será possível definir formalmente os problemas que os algoritmos de aprendizado de máquina resolvem e criar bons modelos teóricos que analisam seu desempenho? Isso pode exigir modelos melhores para algoritmos controlados por dados (que eu considero algoritmos com alta complexidade descritiva), mas isso é um obstáculo que não pode ser superado?
Neal Young

Respostas:

6

Esta é uma pergunta que me assombra recentemente, por isso estou feliz que você fez.
No entanto, estou menos interessado em classificar as áreas de aplicação para as quais o aprendizado de máquina dominará a abordagem computacional do que no impacto no avanço no campo dos algoritmos (tradicionais). Em que tipo de pesquisa em "algoritmos criados por humanos" ainda estaremos interessados ​​em 30 anos? É certo que essa é a pergunta mais difícil de responder em geral, porque é o aplicativo que determina qual qualidade de resultado é necessária.

Eu acho que os algoritmos de enumeração serão numerados entre os sobreviventes. Continuará sendo necessário testar todas as entradas em um chip ou realizar uma pesquisa exaustiva. A atenção específica ao objeto, o design aperfeiçoado necessário para gerar cada instância do objeto exatamente (ou pelo menos) uma vez; e a amplificação em tempo de execução de qualquer esforço desperdiçado (pode haver um número exponencial de instâncias, em função da descrição do objeto) - esses fatores me deixam cético quanto ao fato de que um processo de aprendizado automatizado de uso geral possa corresponder a um inteligente, solução projetada especificamente para essa área.

Gara Pruesse
fonte
4

O problema das soluções de aprendizado de máquina é que não há como saber se elas realmente computaram o que você queria.

Eu esperaria que eles assumissem o controle em todos os domínios em que um resultado errado não é catastrófico (ou seja, em todos os lugares onde atualmente usamos heurísticas) ou o resultado pode ser facilmente verificado (problemas de pesquisa para os quais você sabe que existe uma solução (porque marque "lá não há solução "pode ​​ser difícil)).

Para os domínios restantes, eu esperaria que os algoritmos fossem provados formalmente (por exemplo, usando Coq / Gallina) com frequência excessiva. Felizmente, o aprendizado de máquina acabará tornando as provas em tais sistemas tão fáceis quanto no papel (ou até mais fácil). Pode até chegar ao ponto em que os humanos escrevem apenas a especificação, o algoritmo e sua prova de correção são encontrados usando o aprendizado de máquina. (Observe que o próprio algoritmo não usa aprendizado de máquina, mas ele e suas provas de correção foram encontradas no aprendizado de máquina)

Assim, podemos nos encontrar escrevendo apenas assistentes de prova, especificações de programas e algoritmos de aprendizado de máquina.

xavierm02
fonte