Fungsi yang Tidak Dapat Dihitung Secara Efisien namun Dapat Dipelajari

Kita tahu bahwa (lihat, misalnya, Teorema 1 dan 3 dari [1]), secara kasar, dalam kondisi yang sesuai, fungsi yang dapat dihitung secara efisien oleh mesin Turing dalam waktu polinomial ("efisien yang dapat dihitung") dapat diekspresikan oleh jaringan saraf polinomial dengan ukuran yang wajar, dan dengan demikian dapat dipelajari dengan kompleksitas sampel polinomial ("dapat dipelajari") di bawah distribusi input apa pun.

Di sini "dapat dipelajari" hanya menyangkut kompleksitas sampel, terlepas dari kompleksitas komputasi.

Saya bertanya-tanya tentang masalah yang sangat terkait: apakah ada fungsi yang tidak dapat dihitung secara efisien oleh mesin Turing dalam waktu polinomial ("tidak dapat dihitung secara efisien"), tetapi sementara itu, dapat dipelajari dengan kompleksitas sampel polinomial ("dapat dipelajari") di bawah distribusi input apa pun?

• [1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, " Tentang Efisiensi Komputasi Pelatihan Jaringan Saraf Tiruan ", 2014

Saya akan memformalkan varian dari pertanyaan ini di mana "efisiensi" diganti oleh "komputabilitas".

Biarkan $C_n$ menjadi kelas konsep semua bahasa $L\subseteq\Sigma^*$ dikenali oleh mesin Turing pada $n$ status atau lebih sedikit. Secara umum, untuk $x\in\Sigma^*$ dan $f\in C_n$ , masalah mengevaluasi $f(x)$ tidak dapat dipastikan.

Namun, anggaplah kita memiliki akses ke oracle $A$ belajar PAC (tepat, dapat direalisasi) untuk $C_n$ . Yaitu, untuk $\epsilon,\delta>0$ , oracle meminta sampel berlabel ukuran $m_0(n,\epsilon,\delta)$ sedemikian sehingga, dengan asumsi sampel seperti itu diambil iid dari distribusi yang tidak diketahui $D$ , oracle $A$ menghasilkan hipotesis f ∈ C n yang, dengan probabilitas setidaknya 1 - δ , memiliki D$\hat f\in C_n$$1-\delta$$D$Kesalahan-generalisasi tidak lebih dari $\epsilon$ . Kami akan menunjukkan bahwa oracle ini tidak dapat dihitung oleh Turing.

Sebenarnya, kita akan menunjukkan bahwa masalah sederhana adalah diputuskan: Salah menentukan, diberi label sampel $S$ , apakah ada sebuah $f\in C_n$ konsisten dengan $S$ . Misalkan (untuk mendapatkan kontradiksi) bahwa $K$ adalah mesin Turing yang memutuskan masalah konsistensi.

Kami membuat konvensi notasi berikut. Identifikasi $\Sigma^*$ dengan $\mathbb{N}=\{0,1,2,\ldots\}$ melalui pemesanan leksikografis yang biasa. Untuk $x\in\{0,1\}^*$ , kita mengatakan bahwa TM $M$ "S-print" $x$ jika ia menerima semua string dalam $\Sigma^*$ sesuai dengan indeks $i$ st $x_i=1$ dan tidak menerima (mungkin dengan tidak halting) salah satu string yang sesuai dengan indeks $x_i=0$ . Sejak (dengan asumsi)$K$ adalah decidable, berikut bahwa fungsi$\tilde K:x\mapsto k$ , didefinisikan sebagai terkecil$k$ sehingga beberapa TM di$C_k$ S-cetakan$x$ , adalah Turing-dihitung. Lebih lanjut mengikuti bahwa fungsi $g:k\mapsto x$ , yang memetakan$k\in\mathbb{N}$ ke string paling sedikit (secara leksikografis)$x\in\{0,1\}^*$ sedemikian rupa sehingga$\tilde K(x)>k$ , juga dapat dihitung.

Sekarang mendefinisikan TM $M$ sebagai berikut: $M$ S-cetak $g(|\langle M\rangle|)$ , di mana $\langle M\rangle$ adalah pengkodean $M$ , $|x|$menunjukkan panjang string, dan teorema rekursi sedang dipanggil untuk menyatakan keberadaan $M$ seperti itu . Kemudian $M$ memiliki panjang penyandian, $\ell=|\langle M\rangle|$, dan S-mencetak beberapa string, $x_M\in\{0,1\}^*$. Dengan konstruksi, $\tilde K(x_M)>\ell$ , dan dengan demikian $x_M$ tidak dapat dicetak S oleh TM mana pun dengan panjang uraian $\ell$ atau lebih pendek. Namun itu didefinisikan sebagai output S-print dari TM dengan panjang deskripsi $\ell$ --- sebuah kontradiksi.