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

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.

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

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.

$A$$\mathcal{P}(A^*)$$A$$A$$\mathcal{F} \subseteq \mathcal{P}(A^*)$

$f: \mathbb{N} \to A^*$

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.

$Rep$$M$$Rep$$L(M)$

$p: \mathbb{N} \to Rep$$L(p(i))$$f(j)$$j \le i$$k$$j \ge k$$L(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.

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?

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

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.