Redes neurais podem ser usadas para criar algoritmos?

9

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.Gstst

TC0TC0NPTC0

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?

domotorp
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Lev Reyzin

Respostas:

2

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!

Mohammad Al-Turkistany
fonte
11
Realmente não vejo como isso responde à minha pergunta.
Domotorp 11/11
Antes de editar a postagem, sua primeira pergunta é sobre o treinamento de NN. Desde que você adicionou a tag CC, minha resposta mostra que é difícil treinar NN, independentemente de o seu problema algorítmico estar em P ou NPC
Mohammad Al-Turkistany
Me desculpe se eu era vago.
Domotorp 11/12
0

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.

usul
fonte
Eu não acho que ter uma resposta faça a diferença - dois jogadores podem jogar o Dijkstra competindo e encontrar um caminho mais curto. A escalabilidade pode ser um problema mais sério - você acha que os NNs podem aprender a jogar NIM?
Domotorp 11/11
@domotorp, acho que há uma enorme diferença conceitual e prática entre algoritmos corretos e heurísticas incorretas, mas aproximadas. Você não perguntou por que o xadrez é mais difícil do que os caminhos mais curtos, mas por que o xadrez é mais difícil que o Dijkstra, que é comprovadamente correto 100% do tempo em todos os tamanhos de entrada. Re: nim, nenhuma idéia; você precisa de uma arquitetura NN que aceite entradas arbitrariamente grandes para começar ...
usul
0

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.

CinchBlue
fonte
-3

"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.

riemann77
fonte
Penso que uma estratégia ideal para um jogo adequado é a mesma que um algoritmo ideal para o problema correspondente.
domotorp
@domotorp "estratégia" é mais uma heurística do que um algoritmo
riemann77
-6

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.

Francis H Erdman III
fonte