Redes neurais podem ser usadas para criar algoritmos?

Após os sucessos mais recentes e mais recentes das redes neurais nos jogos de tabuleiro, parece que o próximo objetivo que estabelecemos poderia ser algo mais útil do que derrotar humanos em Starcraft. Mais precisamente, eu me perguntava se

As redes neurais podem ser treinadas para resolver problemas algorítmicos clássicos?

Aqui quero dizer que, por exemplo, a rede teria um grafo de entrada com bordas ponderada, e dois vértices s e t especificado, e pedimos-lo para encontrar um mais curto s t caminho o mais rápido possível. Acho que a rede neural descobriria e se treinaria para usar o Dijkstra ou algo semelhante.$G$$s$$t$$st$

$TC^0$$TC^0$$NP\not\subset TC^0$

Obviamente, extrair o algoritmo é uma questão totalmente diferente. Suspeito que os especialistas saibam como fazer isso, mas discuti-lo não é o tópico desta pergunta.

Adicionado dois dias depois: Depois de ver as respostas, deixe-me especificar que, se você responder negativamente, gostaria de saber

Por que jogar xadrez é mais fácil do que Dijkstra ou Graphisomorphism?

De acordo com este blog Por Reza Zadeh , o treinamento de uma rede neural para produzir resultados corretos, mesmo para apenas dois terços dos exemplos de treinamento, é computacionalmente difícil:

De fato, em 1988, J. Stephen Judd mostra que o seguinte problema é difícil para o NP:

Dada uma rede neural geral e um conjunto de exemplos de treinamento, existe um conjunto de pesos de borda para a rede, para que a rede produza a saída correta para todos os exemplos de treinamento?

Judd também mostra que o problema permanece difícil para o NP, mesmo que exija apenas uma rede para produzir a saída correta para apenas dois terços dos exemplos de treinamento, o que implica que mesmo o treinamento aproximado de uma rede neural é intrinsecamente difícil no pior dos casos. Em 1993, Blum e Rivest pioram as notícias: mesmo uma rede simples com apenas duas camadas e três nós é difícil de treinar com NP!

Esta não é uma resposta completa e não tenho muita experiência em redes neurais, mas talvez seja útil.

NNs recebem essencialmente uma entrada e produzem uma resposta. Eles são treinados, através da prática, para produzir respostas semelhantes em entradas "semelhantes" no domínio, por exemplo, o mesmo rótulo para imagens do mesmo animal, ou altas classificações para "boas" posições de xadrez, onde bom significa altas chances de vitória.

Então, como eu comentei, as redes neurais são um modelo não uniforme de computação que funciona de uma maneira totalmente diferente dos algoritmos passo a passo executados nas Máquinas de Turing. Em vez disso, pense neles como circuitos "suaves" que usam matemática contínua em vez de booleana e podem ser aprimorados ou treinados e podem errar.

Por que jogar xadrez é mais fácil do que Dijkstra ou Graphisomorphism?

Parcialmente, é a diferença entre pedir a alguém que responda a uma pergunta da melhor maneira possível e pedir a resposta correta, juntamente com uma prova de que ela está correta. Parcialmente, é a diferença entre resolver um problema de tamanho fixo e resolver simultaneamente o problema para todos os tamanhos de entrada possíveis.

Cada vez Dijkstra é executado em uma instância, que pode ser de qualquer tamanho, ele implicitamente prova de que sua saída é a única resposta verdadeira e nenhum outro. No xadrez e no reconhecimento de imagens, dá-se a melhor resposta possível e erros são tolerados. Além disso, apenas treinamos redes para resolver esses problemas de um tamanho por vez. Acho que ainda não sabemos como generalizar uma solução de rede neural para, por exemplo, instâncias de problemas de tamanhos e formas totalmente diferentes.

Acho que não devemos supor que as redes neurais não possam resolver caminhos mais curtos ou problemas algorítmicos semelhantes, mas resolvem problemas de uma maneira fundamentalmente diferente de um algoritmo passo a passo que está sempre correto.

Voltando à semelhança entre redes neurais e circuitos, observe que os circuitos são estudados há décadas, mas, a julgar pela falta de respostas a (5) da minha pergunta anterior , sabemos quase nada sobre como construir circuitos totalmente corretos para um dado problema, exceto através da transformação de um algoritmo uniforme (Turing Machine) em um circuito.

Eu não sou especialista de forma alguma, mas ainda não vejo por que não.

As redes neurais executam fundamentalmente a otimização de acordo com algum tipo de "modelo de custo / benefício" que já é conhecido com antecedência. Além disso, o espaço de pesquisa é bem definido, com movimentos válidos e inválidos conhecidos e "variações" fáceis de definir. Mesmo para AlphaZero e AlphaGo, as funções de custo provavelmente se baseiam na taxa de ganhos e na distribuição resultante das taxas de ganhos para todos os movimentos possíveis depois de fazer um movimento, ou algum tipo de heurística para isso.

Para a criação de algoritmos, você está essencialmente pedindo ao programa que aprenda como gerar uma sequência correta (com uma função implícita de codificação e custo já conhecida) que corresponde a um programa que "executa um algoritmo". No entanto, existem infinitos algoritmos para os quais você implementa um programa. Então, talvez você deseje definir as métricas "adequadas" corretas.

No entanto, mesmo para certos programas, as métricas de "condicionamento físico" podem ser um pouco difíceis de definir. Tempo? Uso de espaço? Quantificação de "efeitos colaterais?" Idealmente, você gerará "o programa mais curto" que faz apenas o que você deseja que ele faça.

Suponho que, se você encontrar as métricas de adequação e os algoritmos de ajuste corretos, poderá fazer isso.

"redes neurais" transformam um vetor de um espaço dimensional para outro espaço dimensional. portanto, nada mais são do que aproximadores de funções altamente não altamente lineares. até redes neurais usam algoritmos de aproximação para minimizar as perdas. no entanto, o treinamento de redes neurais para a criação de novos algoritmos está fora de questão. tomas mikolov fez algum trabalho nesta área com rede neural recorrente aumentada por pilha, e também ouvi falar de "máquinas neurais de turing" para esse domínio. no entanto, encontrar estratégias ideais tem sido a causa fundamental do estudo da aprendizagem por reforço, que está um pouco relacionada à sua pergunta. mas o uso de redes neurais para a criação de novos algoritmos não é possível, pelo menos no futuro próximo.

Sou engenheiro de automação de controle de qualidade, portanto, não reivindique experiência em redes neurais, mas, tautologicamente, sim, o NN pode criar algoritmos. Os próprios seres humanos são NN em algum nível, e criamos algoritmos; portanto, é lógico que os sistemas NN artificiais que criamos podem criar algoritmos.