Dlaczego uczenie maszynowe może nie rozpoznawać liczb pierwszych?

13

Powiedzmy, że mamy reprezentację wektorową dowolnej liczby całkowitej o wartości n, V_n

Ten wektor stanowi dane wejściowe do algorytmu uczenia maszynowego.

Pierwsze pytanie: dla jakiego rodzaju reprezentacji można nauczyć się pierwotności / złożoności n za pomocą sieci neuronowej lub innego mapowania ML wektor-bit. Jest to czysto teoretyczne - rozmiar sieci neuronowej może być nieograniczony.

Zignorujmy reprezentacje, które są już powiązane z testowaniem pierwotności, takie jak: null oddzielona lista czynników n lub istnienie świadka złożoności, takiego jak w Miller Rabin. Zamiast tego skupmy się na reprezentacjach w różnych radach lub reprezentacjach jako wektorach współczynników wielomianów (być może wielowymiarowych). Lub inne egzotyczne, jak się zakłada.

Drugie pytanie: dla jakiego, jeśli w ogóle, rodzaju algorytmu ML nauczenie się tego będzie niemożliwe bez względu na specyfikę wektora reprezentacji? Ponownie pomińmy reprezentacje „zakazane przez trywialność”, których przykłady podano powyżej.

Dane wyjściowe algorytmu uczenia maszynowego to jeden bit, 0 dla liczb pierwszych, 1 dla kompozytu.

Tytuł tego pytania odzwierciedla moją ocenę, że konsensus dla pytania 1 jest „nieznany”, a konsensus dla pytania 2 to „prawdopodobnie większość algorytmów ML”. Pytam o to, ponieważ nie wiem nic więcej i mam nadzieję, że ktoś wskaże drogę.

Główną motywacją, jeśli istnieje, jest pytanie: czy istnieje „teoretyczna informacja” ograniczenie struktury zbioru liczb pierwszych, które można uchwycić w sieci neuronowej określonego rozmiaru? Ponieważ nie jestem ekspertem w tego rodzaju terminologii, pozwól mi kilka razy przeformułować ten pomysł i sprawdź, czy dostanę przybliżenie Monte-Carlo do pojęcia: jaka jest złożoność algorytmiczna zbioru liczb pierwszych? Czy fakt, że liczby pierwsze są diofantyną wyliczalną rekurencyjnie (i mogą spełniać szczególne duże równanie diofantyny ), może być wykorzystany do uchwycenia tej samej struktury w sieci neuronowej z wejściami i wyjściami opisanymi powyżej.

Cris Stringfellow
źródło
12
Z perspektywy teorii twój problem nie jest dobrze zdefiniowany. Jakie są dane wejściowe do algorytmu uczenia maszynowego? Jak są generowane? Co algorytm wie przed swoim zadaniem uczenia się?
Lew Reyzin
3
Nie sądzę, aby w obecnej formie było to dobre pytanie dotyczące tej witryny.
Kaveh
4
To może. Ale w uczeniu maszynowym chcemy zminimalizować błąd podczas testowania zestawu danych. Teraz, jeśli trenujesz na możesz skończyć naukę f ( n ) = n 2 - n + 41, co działa idealnie dla liczb mniejszych niż 41 . Ale potem jego wydajność nie jest dobra. Ludzie próbowali tego (ręcznie :-)) i jak dotąd bez większego sukcesu . W ML staramy się znaleźć wzory, ale co jeśli nie ma żadnego wzoru? [1,20]f(n)=n2n+4141
Pratik Deoghare
1
Wydaje się, że pytasz, czy istnieje algorytm, który otrzymał funkcję od skończonych sekwencji liczb naturalnych do predykatów liczb naturalnych, może poprawnie wyprowadzić predykat pierwotności przy danej sekwencji liczb pierwszych, z zastrzeżeniem dodatkowych ograniczeń algorytmu. Dalsze formułowanie ograniczenia nie jest trywialne, jeśli w ogóle możliwe. Jeśli spróbujesz to sprecyzować, możesz to zobaczyć.
Vijay D
1
Sff(n)nnS

Odpowiedzi:

-8

jest to stare pytanie / problem z wieloma, wieloma powiązaniami głęboko związanymi z teorią liczb, matematyką, TCS, aw szczególności z automatycznym dowodzeniem twierdzeń. [5]

stare, prawie starożytne pytanie brzmi: „czy istnieje wzór na obliczanie liczb pierwszych”

odpowiedź brzmi: tak, w pewnym sensie istnieją różne algorytmy do jej obliczenia.

funkcję zeta Riemanna można przeorientować jako „algorytm” do znajdowania liczb pierwszych.

wydaje mi się możliwe, że metoda GA, algorytm genetyczny może pewnego dnia odnieść sukces w tym problemie dzięki pomysłowej konfiguracji, tj. GA są najbliższą znaną technologią, która ma największe szanse na sukces. [6] [7] jego problemem jest znalezienie algorytmu ze skończonego zestawu przykładów, tj. uczenia maszynowego, który jest bardzo podobny do indukcji matematycznej. wydaje się jednak, że do tej pory nie przeprowadzono wielu badań nad zastosowaniem GA w teorii liczb.

najbliższym tego w istniejącej literaturze wydaje się być np. [8], który omawia opracowywanie hipotezy podwójnej liczby pierwszej w sposób zautomatyzowany, tj. „automatyczne tworzenie hipotez”.

innym podejściem jest program, który ma duży zestaw tabel standardowych funkcji, wraz z zaawansowaną logiką konwersji, do rozpoznawania standardowych sekwencji całkowitych. jest to nowa funkcja wbudowana w Mathematica o nazwie findsequence[3]

jest również związany ze stosunkowo nową dziedziną zwaną „matematyką eksperymentalną” [9,10] lub tak zwaną „badaniem empirycznym” w TCS.

kolejną podstawową kwestią, o której należy tutaj wspomnieć, jest to, że sekwencja liczb pierwszych nie jest „gładka”, wysoce nieregularna, chaotyczna, fraktalna, a standardowe algorytmy uczenia maszynowego są historycznie oparte na optymalizacji numerycznej i minimalizowaniu błędów (np. opadanie gradientu) i nie robią tego dobrze po znalezieniu dokładnych odpowiedzi na dyskretne problemy. ale ponownie GA mogą odnieść sukces i wykazano, że odnoszą sukcesy w tym obszarze / systemie.

[1] Czy istnieje równanie matematyczne dla n-tej liczby pierwszej, matematyka

[2] wzór na liczby pierwsze , wikipedia

[3] funkcja szukania wolframa

[4] funkcja riemann zeta

[5] największe sukcesy automatycznego dowodzenia twierdzeń

[6] zastosowania algorytmów genetycznych w świecie rzeczywistym

[7] zastosowanie algorytmów genetycznych do zautomatyzowanego udowadniania przez Wanga

[8] Zautomatyzowane tworzenie hipotez w teorii liczb przy użyciu HR, wydry i dwukropka klonu

[9] Czy istnieją zastosowania matematyki eksperymentalnej w TCS?

[10] Czytelnicza lista algorytmiki eksperymentalnej

vzn
źródło
1
to świetna odpowiedź. Nie jestem pewien, czy strona się zgodzi, ale tego właśnie szukałem. Kilka nowych wskazówek do odkrywania i starzenia starych połączeń. Dzięki, naprawdę to doceniam. Szczególnie GA. Ponadto czytasz między wierszami i uogólniasz od uczenia maszynowego do „formular for primes”. To bardzo pomocne dzięki.
Cris Stringfellow
11
@Cris, w tej odpowiedzi nie ma prawie nic, co dotyczy uczenia maszynowego. Z twojego komentarza do odpowiedzi Aryeha wydaje mi się, że nie znasz się na uczeniu maszynowym (czy mogę zapytać, gdzie widziałeś maszynę uczącą się algorytmu takiego jak testowanie pierwotności z listy przykładów?)
Kaveh
6
GA może „nauczyć się” algorytmu testowania pierwotności w tym samym sensie, w jakim przysłowiowa nieskończona małpa pewnego dnia napisze pełne dzieła Szekspira
Sasho Nikolov
@ sasho, nie zostało to jeszcze zademonstrowane, ale (tak, imho) prawdopodobnie nie jest to spowodowane ograniczeniami technologii, ale raczej brakiem próby. koza zademonstrował złożone algorytmy GA "rozwiązywania / uczenia się" dla gier wideo, np. pacman (poprzez drzewa seplenów prymitywów), a także konstruowanie obwodów przy użyciu podskładników. czy to nie jest tak trudne, jak znalezienie liczb pierwszych? prawdziwe pytanie brzmi: jakie rodzaje prymitywów miałby system i jak prymitywne mogą być i wciąż znajdują rozwiązanie?
vzn
19

Moim zdaniem pytanie jest dość niejasne i wiąże się z pewnym nieporozumieniem, więc ta odpowiedź ma na celu jedynie zapewnienie właściwego słownictwa i wskazanie właściwego kierunku.

Istnieją dwie dziedziny informatyki, które bezpośrednio badają takie problemy. Wnioskowanie indukcyjne i obliczeniowa teoria uczenia się . Te dwie dziedziny są ze sobą ściśle powiązane, a rozróżnienie ma charakter społeczny i estetyczny, a nie formalny.

AP(A)AAFP(A)

f:NA

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

Tak więc prezentacja pozytywnych danych jest wyliczeniem koncepcji celu, często z wprowadzonymi dodatkowymi warunkami uczciwości. Możesz również poprosić o prezentację, która opisuje słowa w zależności od tego, czy są w języku, czy nie. Ponownie możesz dodać dodatkowe warunki, aby zapewnić uczciwość i pokrycie wszystkich słów.

RepMRepL(M)

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

Chciałbym podkreślić, że jest to tylko jedna konkretna formalizacja jednego konkretnego modelu uczenia się. Ale jest to krok zerowy, zanim zaczniesz zadawać i studiować pytania, które Cię interesują. Model uczenia się można wzbogacić, umożliwiając interakcję między uczniem a nauczycielem. Zamiast arbitralnych rodzin języków, możemy rozważyć bardzo konkretne języki, a nawet określone reprezentacje (takie jak monotoniczne funkcje boolowskie). Istnieje różnica między tym, czego można się nauczyć w każdym modelu, a złożonością uczenia się. Oto jeden przykład fundamentalnego wyniku niemożliwości.

Złoto [1967] Żadna rodzina języków, która nie zawiera wszystkich języków skończonych i przynajmniej jeden język super-skończony nie jest pasywnie poznawana na podstawie samych pozytywnych danych.

Należy bardzo ostrożnie interpretować ten wynik. Na przykład Dana Angluin wykazała to w latach 80

k

k

Angluin [1987] Zwykłych języków można nauczyć się od nauczyciela, który odpowiada na pytania dotyczące równoważności i zapewnia kontrprzykłady. Algorytm jest wielomianowy w zestawie stanów minimalnego DFA i długości maksymalnego kontrprzykładu.

Jest to dość silny i pozytywny wynik, który niedawno znalazł kilka zastosowań. Jednak, jak zawsze, szczegóły są ważne, jak sugeruje już tytuł poniższej pracy.

Minimalny spójny problem DFA nie może być aproksymowany w obrębie wielomianu , Pitt i Warmuth, 1989.

Teraz możesz się zastanawiać, w jaki sposób ma to związek z twoim pytaniem? Na moją odpowiedź jest to, że przestrzeń projektowania matematycznej definicji twojego problemu jest bardzo duża, a konkretny punkt, który wybierzesz w tej przestrzeni, wpłynie na rodzaj otrzymanych odpowiedzi. Powyższe nie stanowi kompleksowej ankiety dotyczącej sposobu sformalizowania problemu uczenia się. Ma on jedynie na celu wskazanie kierunku, który możesz chcieć zbadać. Wszystkie cytowane przeze mnie referencje i wyniki są niezwykle datowane, a od tego czasu pole wiele zrobiło. Istnieją podstawowe podręczniki, z którymi można się zapoznać, aby uzyskać wystarczające tło do precyzyjnego sformułowania pytania i ustalenia, czy szukana odpowiedź już istnieje.

Vijay D.
źródło
To świetnie, @Vijay D, dziękuję za to.
Cris Stringfellow
To źle sformułowane pytanie. Moja odpowiedź (i komentarze) poniżej pokazują, dlaczego. ML rozpoznaje liczby pierwsze, ale nie w praktycznym sensie, zajęłoby to zbyt długo. Taka jest natura tej konkretnej bestii.
Dominic Cerisano
12

Sukces algorytmu uczenia się zależy krytycznie od reprezentacji. Jak prezentujesz dane wejściowe algorytmowi? W skrajnym przypadku załóżmy, że prezentujesz liczby jako sekwencje czynników pierwszych - w tym przypadku nauka jest dość trywialna. W innej skrajności rozważ reprezentowanie liczb jako ciągów binarnych. Wszystkie standardowe algorytmy uczenia, które znam, zawiodłyby tutaj. Oto jeden, który by działał: znajdź najmniejszą maszynę Turinga, która akceptuje wszystkie pozytywne przykłady i odrzuca wszystkie negatywne. [Ćwiczenie: udowodnij, że jest to uniwersalny uczeń.] Jednym z problemów jest to, że zadanie nie jest obliczalne według Turinga. Patrząc z perspektywy, czy możesz nauczyć się rozpoznawać prymat oparty tylko na reprezentacji binarnej?

Aryeh
źródło
Mogę nauczyć się rozpoznawać pierwszeństwo na podstawie powtórzeń binarnych, jeśli „nauczę się”, powiedzmy, algorytmu Millera Rabina. Ale chcę wyjść poza takie rzeczy i sprawdzić, czy jest coś jeszcze. Dlaczego wspomniane zadanie nie jest obliczalne według Turinga?
Cris Stringfellow
6
Nie rozumiem, jak można tu mówić o problemach z uczeniem się, nie odnosząc się na przykład do docelowej klasy funkcji.
Lev Reyzin
1
Lew ma oczywiście rację - ale myślałem, że dyskusja na temat klas funkcji byłaby poza zakresem pytania ... :)
Aryeh
-1

Ten problem jest częścią współczesnych badań: przy danych wejściowych i wyjściowych znajdź najprostszy algorytm, który wytwarza dane wyjściowe. Sieci RNN są kompletne Turinga, więc teoretycznie przez niekończące się SGD możesz skończyć w RNN, co jest równoważne z tym kodem:

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);
    }
}

w tym zestawie danych: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... itd.

Problem polega na tym, że nie mamy praktycznie wiarygodnej teorii konwergencji SGD ani żadnych szacunków czasu potrzebnych na konwergencję lub głębokość sieci neuronowej. Jednak najnowsze badania pokazują, że podobne problemy można rozwiązać:

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

https://www.microsoft.com/en-us/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

użyj wyszukiwarki google, aby wyszukać słowa kluczowe ...

Stepan Jakowenko
źródło
-3

Uczenie maszynowe podlega prawom złożoności obliczeniowej.

Problem faktoryzacji pierwotnej dotyczy klasy złożoności NP, być może nawet NP-twardej (nie udowodniono).

Dlatego wykrywanie liczb pierwszych jest jednym z najtrudniejszych problemów w uczeniu maszynowym i przy takim podejściu może nie być w ogóle możliwe.

Komputery kwantowe (QC) mogą to robić w czasie wielomianowym, ale Shor to determinizm brutalnej siły, a nie uczenie maszynowe.

Być może algorytm uczenia się QC oparty na Shorze jest podejściem. Naprawdę po prostu zbijam skały, sugerując to.

Dominic Cerisano
źródło
1
PRIMES jest w P, więc nie powiedziałbym, że „wykrywanie liczb pierwszych” jest jednym z najtrudniejszych problemów w ML - lub w jakiejkolwiek innej dziedzinie informatyki. „Wszystko sprowadza się do reprezentacji” trafia znacznie bliżej domu - jak wyjaśniono w mojej odpowiedzi i komentarzach poniżej.
Aryeh
Przepraszam, P ≠ NP! PRIMES jest ko-NP, a jego rozwiązanie w P wymagałoby obecnie algorytmu galaktycznego całkowicie nieodpowiedniego w żadnym paradygmacie obliczeniowym - szczególnie uczenia maszynowego, bez względu na to, jak go reprezentujesz. W każdym praktycznym sensie jest to NP, a być może NP-trudne, dziękuję.
Dominic Cerisano
1
@Birkensocks wygląda na to, że łączyłeś testowanie pierwotności z faktoringiem. „PRIMES is in P” to tak naprawdę nazwa artykułu, który jako pierwszy podał algorytm czasu wielomianowego do sprawdzania pierwotności, en.wikipedia.org/wiki/AKS_primality_test . Zauważ też, że faktoring jest w NP i co-NP, więc jest bardzo mało prawdopodobne, aby był NP-trudny, patrz np. Blog.computationalcomplexity.org/2002/09/...
Rahul Savani
Tak, chyba już to powiedziałem ...
Dominic Cerisano,