Czy sieć neuronowa może wykryć liczby pierwsze?


21

Nie szukam skutecznego sposobu na znalezienie liczb pierwszych (co oczywiście jest rozwiązanym problemem ). To jest raczej pytanie „co jeśli”.

Teoretycznie: czy możesz wytrenować sieć neuronową, aby przewidzieć, czy dana liczba n jest złożona, czy pierwsza? Jaka byłaby taka sieć?



2
Jeśli liczby pierwsze są zgodne ze schematem, a ktoś po prostu trenuje sieć neuronową z wystarczającą liczbą ukrytych węzłów, aby zdefiniować granicę klasyfikacji, przypuszczam, że to zadziałałoby. Jednak nie wiemy, czy ta klasyfikacja istnieje, a nawet gdyby tak było, musielibyśmy udowodnić, jaka jest granica, aby udowodnić, że sieć neuronowa rzeczywiście znalazła prawidłowy wzór.
kwintumnia

Odpowiedzi:


11

faloor(x)

02)n-1n

  1. Czy można to po prostu zapamiętać liczby pierwsze w zakresie liczb całkowitych?
  2. Czy można to zrobić, ucząc się uwzględniać i stosować definicję liczby pierwszej?
  3. Czy można to zrobić, ucząc się znanego algorytmu?
  4. Czy można to zrobić, opracowując własny algorytm podczas szkolenia?

Bezpośrednia odpowiedź brzmi „tak” i zostało to już zrobione zgodnie z 1. powyżej, ale zostało to zrobione przez nadmierne dopasowanie, a nie uczenie się metody wykrywania liczb pierwszych. Wiemy, że ludzki mózg zawiera sieć neuronową, która może osiągnąć 2., 3. i 4., więc jeśli sztuczne sieci zostaną rozwinięte w stopniu, w jakim większość z nich myśli, że tak, to dla nich odpowiedź brzmi „tak”. Nie ma kontrwywiadu, który mógłby wykluczyć którekolwiek z nich z zakresu możliwości w chwili pisania tej odpowiedzi.

Nic dziwnego, że poczyniono prace nad szkoleniem sztucznych sieci w zakresie testowania liczb pierwszych ze względu na znaczenie liczb pierwszych w dyskretnej matematyce, jej zastosowanie w kryptografii, a dokładniej w kryptoanalizie. Możemy zidentyfikować znaczenie cyfrowej detekcji liczb pierwszych w badaniach i rozwoju inteligentnego bezpieczeństwa cyfrowego w pracach takich jak Pierwsze badanie podejścia do sieci neuronowej w kryptosystemie RSA , Gc Meletius i in. al., 2002 . Wiązanie kryptografii z bezpieczeństwem naszych odpowiednich narodów jest również powodem, dla którego nie wszystkie obecne badania w tej dziedzinie będą publiczne. Ci z nas, którzy mogą mieć zezwolenie i ujawnienie, mogą mówić tylko o tym, co nie jest klasyfikowane.

Po stronie cywilnej, ciągłe prace nad tak zwanym wykrywaniem nowości są ważnym kierunkiem badań. Tacy jak Markos Markou i Sameer Singh zbliżają się do wykrycia nowości od strony przetwarzania sygnału , a dla tych, którzy rozumieją, że sztuczne sieci są zasadniczo cyfrowymi procesorami sygnałowymi, które mają możliwości samostrojenia wielopunktowego, można zobaczyć, jak ich praca odnosi się bezpośrednio do tego. pytanie. Markou i Singh piszą: „Istnieje wiele aplikacji, w których niezwykle ważne jest wykrywanie nowości, w tym przetwarzanie sygnałów, widzenie komputerowe, rozpoznawanie wzorców, eksploracja danych i robotyka”.

Jeśli chodzi o matematykę kognitywną, opracowanie matematyki zaskakującej, takiej jak Uczenie się z niespodzianką: teoria i zastosowania (teza), Mohammadjavad Faraji, 2016, może być kontynuacją tego, co rozpoczęli Ergi i Shultz.


1

Teoretycznie sieć neuronowa może odwzorować dowolną daną funkcję ( źródło ).

Jeśli jednak trenować sieć z numerami 0do N, nie można zagwarantować, że sieć będzie prawidłowo klasyfikować numery spoza tego zakresu ( n > N).

Taka sieć byłaby regularną siecią przesyłu danych ( MLP ), ponieważ rekurencja nic nie dodaje do klasyfikacji danych wejściowych. Ilość warstw i węzłów można znaleźć tylko metodą prób i błędów.


1
Twierdzenia uniwersalne dotyczą funkcji ciągłych na podzbiorach kompaktowych. Prime / not prime nie jest tego rodzaju funkcją.
pasaba por aqui

1
@pasabaporaqui: W tym przypadku funkcja pierwotności może być wystarczająco dobrze przybliżona przez funkcję ciągłą z pikami przy wartościach liczb pierwszych. Tak więc NN może generować 90% szansy na bycie liczbą pierwszą dla 6,93 - to oczywisty nonsens, ale jeśli dyskretyzujesz wejścia i wyjścia, tak naprawdę nie obchodzi cię, co NN przewidziałby dla liczb całkowitych. Myślę, że ta odpowiedź jest zasadniczo poprawna.
Neil Slater,

1

Jestem pracownikiem naukowym na uniwersytecie Prairie View A&M. Pomyślałem, że skomentuję, ponieważ spędziłem kilka tygodni na ulepszaniu modelu MLPRegressor, aby przewidzieć n-tą liczbę pierwszą. Niedawno wpadł w bardzo niskie minima, gdzie pierwsze 1000 ekstrapolacji poza danymi szkoleniowymi spowodowało błąd mniejszy niż 0,02 procent. Nawet przy 300 000 liczb pierwszych było to około 0,5 procent zniżki. Mój model był prosty: 10 ukrytych warstw, trenowanych na jednym procesorze przez mniej niż 2 godziny.

Dla mnie rodzi się pytanie: „Czy istnieje rozsądna funkcja, która daje n-tą liczbę pierwszą?” W tej chwili algorytmy stają się bardzo obciążające obliczeniowo dla ekstremalnych n. Sprawdź przerwy czasowe między najnowszymi największymi odkrytymi liczbami pierwszymi. Niektóre z nich dzieli lata. Wiem, że udowodniono, że jeśli taka funkcja istnieje, nie będzie wielomianowa.


Witamy w AI.SE! Pamiętaj, że w sekcji odpowiedzi zezwalamy tylko na odpowiedzi (w przeciwieństwie do komentarzy), dlatego dopracowałem twój post, aby skupić się na rozwiązaniu pytania. Wprowadzenie do naszej witryny można znaleźć w przewodniku .
Ben N

Cześć Cody, to nie było dawno temu. Ale chciałbym porozmawiać z tobą na temat testu, który zrobiłeś. Czy zechcesz porozmawiać na żywo o tym, co zrobiłeś i co postrzegałeś? Chciałbym sprawdzić, czy istnieje możliwość dalszego eksperymentowania z tym.
momomo

-1

tak, jest to wykonalne, ale weź pod uwagę fakt, że problem faktoryzacji liczb całkowitych jest problemem NP-coś i problemem BQP .

z tego powodu niemożliwe jest, aby sieć neuronowa oparta wyłącznie na klasycznych obliczeniach znalazła liczbę pierwszą ze 100% dokładnością, chyba że P = NP.


Jak wyjaśnia pytanie, sprawdź, czy liczba jest liczbą pierwszą, nie stanowi problemu NP.
pasaba por aqui
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.