Por que o aprendizado de máquina não pode reconhecer números primos?

13

Digamos que temos uma representação vetorial de qualquer número inteiro de magnitude n, V_n

Esse vetor é a entrada para um algoritmo de aprendizado de máquina.

Primeira pergunta: para que tipo de representações é possível aprender a primalidade / composição de n usando uma rede neural ou algum outro mapeamento ML de vetor para bit. Isso é puramente teórico - a rede neural pode ter tamanho ilimitado.

Vamos ignorar representações que já estão relacionadas ao teste de primalidade, como: a lista separada nula de fatores de n ou a existência de uma testemunha de composição como em Miller Rabin. Em vez disso, vamos nos concentrar nas representações em diferentes radias ou representações como vetores coeficientes de polinômios (possivelmente multivariados). Ou outros exóticos como são postados.

Segunda pergunta: para quais tipos de algoritmo ML, se houver algum, o aprendizado será impossível, independentemente das especificidades do vetor de representação? Novamente, vamos deixar de fora as representações "proibidas pela trivialidade", cujos exemplos são dados acima.

A saída do algoritmo de aprendizado de máquina é um bit único, 0 para prime, 1 para composto.

O título desta pergunta reflete minha avaliação de que o consenso para a pergunta 1 é 'desconhecido' e o consenso para a pergunta 2 é 'provavelmente a maioria dos algoritmos de ML'. Estou perguntando isso, porque não sei mais do que isso e espero que alguém possa apontar o caminho.

A principal motivação, se houver uma, dessa pergunta é: existe um limite "teórico da informação" para a estrutura do conjunto de primos que pode ser capturado em uma rede neural de um tamanho específico? Como não sou especialista nesse tipo de terminologia, reformule essa idéia algumas vezes e veja se entendo uma aproximação de Monte-Carlo ao conceito: qual é a complexidade algorítmica do conjunto de números primos? O fato de que os primos são diofantinos recursivamente enumeráveis ​​(e podem satisfazer uma determinada equação diofantina grande ) pode ser usado para capturar a mesma estrutura em uma rede neural com as entradas e saídas descritas acima.

Cris Stringfellow
fonte
12
Da perspectiva da teoria, seu problema não está bem definido. Quais são as entradas para o algoritmo de aprendizado de máquina? Como eles são gerados? O que o algoritmo sabe antes de sua tarefa de aprendizado?
Lev Reyzin
3
Não acho que seja uma boa pergunta em sua forma atual para este site.
Kaveh
4
Pode. Mas no aprendizado de máquina, queremos minimizar o erro no teste do conjunto de dados. Agora, se você treinar em pode acabar aprendendo e que funciona perfeitamente para números menores que . Mas depois disso, seu desempenho não é bom. As pessoas tentaram isso (manualmente :-)) e até agora sem muito sucesso . No ML, tentamos encontrar padrões, mas e se não houver nenhum padrão? f ( n ) = n 2 - n + 41 41[1,20]f(n)=n2n+4141
Pratik Deoghare 11/01
1
Parece que você está se perguntando se existe um algoritmo que, dado uma função de seqüências finitas de números naturais a predicados nos números naturais, possa gerar corretamente um predicado de primalidade, dada uma sequência de números primos, sujeito a restrições adicionais no algoritmo. Articular ainda mais sua restrição não é trivial, se possível. Se você tentar torná-lo preciso, poderá ver.
precisa
1
Uma resposta simples, porque é difícil aproximar o espaço de pesquisa da função do número primo f que você está procurando (ou seja, f ( n ) retorna 1 se n for primo e 0 caso contrário, para cada n ). Em relação ao comentário @PratikDeoghare, é difícil encontrar um padrão em S . Sff(n)nnS
precisa saber é

Respostas:

-8

essa é uma pergunta / problema antigo, com muitas, muitas conexões profundas na teoria dos números, na matemática, no TCS e, em particular, na Prova automatizada de teoremas. [5]

a pergunta antiga e quase antiga é "existe uma fórmula para calcular números primos"

a resposta é sim, em certo sentido, existem vários algoritmos para calculá-lo.

a função Riemann zeta pode ser reorientada como um "algoritmo" para encontrar números primos.

Parece-me possível que uma abordagem de algoritmo genético da GA possa ter sucesso nesse problema algum dia com uma configuração engenhosa, ou seja, as GAs são a tecnologia conhecida mais próxima que tem mais chances de sucesso. [6] [7] é o problema de encontrar um algoritmo a partir de um conjunto finito de exemplos, isto é, aprendizado de máquina, que é muito semelhante à indução matemática. no entanto, parece não haver muita pesquisa sobre a aplicação de AGs na teoria dos números até o momento.

o mais próximo disso na literatura existente parece ser, por exemplo, [8] que discute o desenvolvimento da conjectura de gêmeos primos de maneira automatizada, ou seja, "criação automatizada de conjecturas".

outra abordagem é um programa que possui um grande conjunto de tabelas de funções padrão, juntamente com alguma lógica sofisticada de conversão, para reconhecer seqüências inteiras padrão. esta é uma nova função incorporada ao Mathematica chamada findsequence[3]

também está conectado a um campo relativamente novo chamado "matemática experimental" [9,10] ou ao que também é chamado de pesquisa "empírica" ​​no TCS.

Outro ponto básico a ser destacado aqui é que a sequência de números primos não é "suave", algoritmos de aprendizado de máquina altamente irregulares, caóticos, fractais e padrão são historicamente baseados em otimização numérica e minimização de erros (por exemplo, descida de gradiente), e não o fazem bem em encontrar respostas exatas para problemas discretos. mas, novamente, as AGs podem ter sucesso e demonstraram ter sucesso nessa área / regime.

[1] existe um eqn matemático para o enésimo nono primo, math.se

[2] fórmula para números primos , wikipedia

[3] função de sequência de wolfram

[4] função riemann zeta

[5] principais sucessos da prova automatizada de teoremas

[6] aplicações de algoritmos genéticos no mundo real

[7] aplicando algoritmos genéticos à prova automatizada de thm por Wang

[8] Confecção automatizada de conjecturas em teoria dos números usando HR, Otter e Maple colton

[9] Existem aplicações de matemática experimental no TCS?

[10] Uma lista de leitura sobre algoritmos experimentais

vzn
fonte
1
Esta é uma ótima resposta. Não tenho certeza se o site vai concordar, mas era o que eu estava procurando. Um monte de novas direções para explorar e envelhecer conexões antigas. Obrigado, realmente aprecio isso. Particularmente GAs. Além disso, você lê nas entrelinhas e generaliza do aprendizado de máquina a 'formular para primos'. Isso é muito útil, obrigado.
precisa saber é o seguinte
11
@ Cris, não há quase nada nesta resposta que seja sobre aprendizado de máquina. Do seu comentário sobre a resposta de Aryeh parece-me que você não está familiarizado com a aprendizagem de máquina (posso perguntar onde já se viu uma máquina de aprender um algoritmo como teste de primalidade de uma lista de exemplos?)
Kaveh
6
GA pode "aprender" um algoritmo de teste de primalidade no mesmo sentido em que o macaco infinito proverbial um dia vai escrever as obras completas de Shakespeare
Sasho Nikolov
@ Sasho, ainda não foi demonstrado, mas (sim, imho) provavelmente não é devido a limitações na tecnologia, mas sim à falta de tentativa. O koza demonstrou os GAs "resolvendo / aprendendo" algoritmos complexos para videogames, por exemplo, pacman (via lisp trees of primitives), e também construindo circuitos usando subcomponentes. não é tão difícil quanto encontrar números primos? a verdadeira questão é: que tipos de primitivas o sistema teria e qual a sua primitividade e ainda encontrar a solução?
vzn
19

A pergunta é, na minha opinião, bastante vaga e envolve algum mal-entendido; portanto, essa resposta tenta apenas fornecer o vocabulário correto e direcioná-lo na direção certa.

Existem dois campos da ciência da computação que estudam diretamente esses problemas. Inferência indutiva e teoria da aprendizagem computacional . Os dois campos estão intimamente relacionados e a distinção é social e estética, e não formal.

AP(A)AAFP(A)

f:NA

iNf(i)=T, for some T in F.

Portanto, uma apresentação de dados positivos é uma enumeração do conceito de destino, geralmente com algumas condições adicionais de equidade. Você também pode solicitar uma apresentação que rotule as palavras, dependendo se elas estão no idioma ou não. Novamente, você pode adicionar condições adicionais para garantir justiça e cobertura de todas as palavras.

RepMRepL(M)

p:NRepL(p(i))f(j)jikjkL(p(j))=L(p(j+1))

Permitam-me enfatizar que esta é apenas uma formalização específica de um modelo de aprendizado específico. Mas este é o passo zero antes que você possa começar a fazer e estudar as perguntas que lhe interessam. O modelo de aprendizado pode ser enriquecido ao permitir a interação entre o aluno e o professor. Em vez de famílias arbitrárias de idiomas, podemos considerar idiomas muito específicos ou mesmo representações específicas (como funções booleanas monótonas). Há uma diferença entre o que você pode aprender em cada modelo e a complexidade do aprendizado. Aqui está um exemplo de um resultado de impossibilidade fundamental.

Gold [1967] Nenhuma família de idiomas que contém todos os idiomas finitos e pelo menos um idioma super finito é passivamente aprendida apenas com dados positivos.

Deve-se ter muito cuidado ao interpretar esse resultado. Por exemplo, Dana Angluin mostrou nos anos 80 que

k

k

Angluin [1987] As línguas regulares são aprendidas por um professor que responde a consultas de equivalência e fornece contra-exemplos. O algoritmo é polinomial no conjunto de estados do DFA mínimo e no comprimento do contra-exemplo máximo.

Este é um resultado bastante forte e positivo e recentemente encontrou várias aplicações. No entanto, como sempre, os detalhes são importantes, como o título do artigo abaixo já sugere.

O problema mínimo consistente de DFA não pode ser aproximado e polinomial , Pitt e Warmuth, 1989.

Agora você pode estar se perguntando, como isso é relevante para sua pergunta? A minha resposta é que o espaço de design para uma definição matemática do seu problema é muito grande e o ponto específico escolhido nesse espaço afetará o tipo de resposta que você obterá. O exposto acima não pretende ser uma pesquisa abrangente de como formalizar o problema de aprendizagem. Ele serve apenas para demonstrar a direção que você pode querer investigar. Todas as referências e resultados que cito são extremamente antigos, e o campo fez muito desde então. Existem manuais básicos que você pode consultar para obter os antecedentes suficientes para formular sua pergunta de maneira precisa e determinar se a resposta que você procura já existe.

Vijay D
fonte
Isso é ótimo @Vijay D, obrigado por isso.
precisa saber é o seguinte
É uma pergunta mal formada. Minha resposta (e comentários) abaixo mostram o porquê. O ML pode reconhecer números primos, mas não em sentido prático, levaria muito tempo. Essa é a natureza desse animal em particular.
Dominic Cerisano 15/01
12

O sucesso de um algoritmo de aprendizado depende criticamente da representação. Como você apresenta a entrada para o algoritmo? Em um caso extremo, suponha que você apresente os números como seqüências de fatores primos - nesse caso, o aprendizado é bastante trivial. Em outro extremo, considere representar os números como cadeias binárias. Todos os algoritmos de aprendizado padrão que conheço falhariam aqui. Aqui está uma que funcionaria: encontre a menor máquina de Turing que aceite todos os exemplos positivos e rejeite todos os negativos. [Exercício: prove que este é um aprendiz universal.] Um problema disso é que a tarefa não é computável em Turing. Para colocar as coisas em perspectiva, você pode aprender a reconhecer a primalidade com base apenas na representação binária?

Aryeh
fonte
Posso aprender a reconhecer a primalidade com base no representante binário se 'aprender', digamos, o algoritmo de Miller Rabin. Mas quero ir além de coisas assim e ver se há algo mais. Por que a tarefa que você mencionou não é computável em Turing?
precisa saber é o seguinte
6
Não entendo como se pode falar sobre um problema de aprendizagem aqui sem se referir, por exemplo, à classe-alvo de funções.
Lev Reyzin
1
Lev é certo, é claro - mas eu pensei que uma discussão de aulas de função estaria além do alcance da questão ... :)
Aryeh
-1

Esse problema faz parte da pesquisa moderna: dados dados de entrada e saída, encontre o algoritmo mais simples que produza saída a partir da entrada. As redes RNN são completas em Turing; portanto, teoricamente, por um infinito SGD, você pode acabar na RNN, que é equivalente a este código:

bool isPrime(int n, int d) {
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

neste conjunto de dados: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... etc

O problema é que não temos uma teoria praticamente confiável sobre convergência SGD nem estimativas de tempo necessárias para convergência ou profundidade da rede neural. Porém, pesquisas mais recentes mostram que problemas semelhantes podem ser resolvidos:

https://en.wikipedia.org/wiki/Neural_Turing_machine

https://www.microsoft.com/pt-br/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf

use o google scholar para pesquisar palavras-chave ...

Stepan Yakovenko
fonte
-3

O aprendizado de máquina está sujeito às leis da complexidade da computação.

O principal problema de fatoração está na classe de complexidade NP, possivelmente até NP-difícil (não comprovada).

É por isso que detectar números primos está entre os problemas mais difíceis do aprendizado de máquina e pode não ser possível com essa abordagem.

Os computadores quânticos (QC) podem fazê-lo em tempo polinomial, mas o Shor é o determinismo da força bruta, não o aprendizado de máquina.

Possivelmente, um algoritmo de aprendizado de CQ baseado no Shor é uma abordagem. Estou realmente apenas batendo as pedras sugerindo isso.

Dominic Cerisano
fonte
1
PRIMES está em P, então eu não diria que "detectar números primos" está entre os problemas mais difíceis da ML - ou de qualquer outro ramo da ciência da computação. "É tudo sobre representação" chega muito mais perto de casa - como explicado na minha resposta e nos comentários abaixo.
Aryeh 15/01
Com licença, P ≠ NP! PRIMES é co-NP, e para resolvê-lo em P atualmente seria necessário um algoritmo galáctico totalmente inadequado para qualquer paradigma de computação - especialmente aprendizado de máquina, não importa como você o represente. Em qualquer sentido prático, é NP, e possivelmente NP-difícil, obrigado.
Dominic Cerisano 15/01
1
@ Birkensocks, você parece ter conflitado o teste de primazia com o Factoring. "PRIMES is in P" é realmente o nome do artigo que primeiro forneceu um algoritmo de tempo polinomial para verificar a primalidade, en.wikipedia.org/wiki/AKS_primality_test . Observe também que o Factoring está em NP e co-NP, e é muito improvável que seja NP-difícil, veja, por exemplo, blog.computationalcomplexity.org/2002/09/…
Rahul Savani
Sim, acho que já disse isso ...
Dominic Cerisano