Google menggunakan AI untuk memecahkan meterai sepuluh tahun algoritma pengisihan Ia dilaksanakan bertrilion kali setiap hari, tetapi netizen mengatakan ia adalah penyelidikan yang paling tidak realistik?

Organisasi |. Nuka-Cola, Chu Xingjuan

Rakan yang telah mengambil kursus asas sains komputer mesti telah mereka sendiri algoritma pengisihan - iaitu, menggunakan kod untuk menyusun semula item dalam senarai tidak tertib dalam tertib menaik atau menurun. Ia adalah satu cabaran yang menarik, dan terdapat banyak cara yang mungkin untuk melakukannya. Banyak masa telah dilaburkan untuk memikirkan cara untuk menyelesaikan tugasan pengasingan dengan lebih cekap.

Sebagai operasi asas, algoritma pengisihan dibina ke dalam perpustakaan standard kebanyakan bahasa pengaturcaraan. Terdapat banyak teknik dan algoritma pengisihan berbeza yang digunakan dalam pangkalan kod di seluruh dunia untuk menyusun sejumlah besar data dalam talian, tetapi sekurang-kurangnya setakat perpustakaan C++ yang digunakan dengan pengkompil LLVM, kod pengisihan tidak berubah dalam lebih sedekad. .

Baru-baru ini, pasukan DeepMind AI Google kini telah membangunkan alat pembelajaran pengukuhan, AlphaDev, yang boleh membangunkan algoritma yang sangat dioptimumkan tanpa memerlukan pra-latihan dengan contoh kod manusia. Hari ini, algoritma ini telah disepadukan ke dalam perpustakaan pengisihan standard LLVM C++, menandakan kali pertama dalam lebih sedekad bahawa sebahagian daripada perpustakaan pengisihan telah berubah dan kali pertama algoritma yang direka bentuk dengan pembelajaran pengukuhan telah ditambahkan ke perpustakaan.

Fikirkan proses pengaturcaraan sebagai "permainan"

Sistem DeepMind selalunya dapat mencari penyelesaian kepada masalah yang tidak pernah difikirkan oleh manusia kerana ia tidak memerlukan pendedahan awal kepada strategi permainan manusia. DeepMind bergantung sepenuhnya pada konfrontasi diri apabila belajar daripada pengalaman, jadi kadangkala terdapat titik buta yang boleh dieksploitasi oleh manusia.

Kaedah ini sebenarnya hampir sama dengan pengaturcaraan. Model bahasa yang besar dapat menulis kod yang cekap kerana mereka telah melihat banyak contoh kod manusia. Tetapi kerana ini, sukar bagi model bahasa untuk menghasilkan perkara yang tidak pernah dilakukan oleh manusia sebelum ini. Jika kita ingin mengoptimumkan lagi algoritma sedia ada di mana-mana (seperti fungsi pengisihan), sukar untuk menembusi kekangan idea yang wujud dengan terus bergantung pada kod manusia sedia ada. Jadi bagaimana AI boleh mencari arah yang benar-benar baharu?

Penyelidik DeepMind menggunakan kaedah yang serupa dengan catur dan Pergi untuk mengoptimumkan tugasan kod, mengubahnya menjadi "teka-teki jigsaw" pemain tunggal. AlphaDev Systems telah membangunkan algoritma pemasangan x86 yang menganggap kelewatan berjalan kod sebagai pecahan, dan berusaha untuk meminimumkan pecahan sambil memastikan kod boleh berjalan dengan lancar. AlphaDev telah secara beransur-ansur menguasai seni menulis kod yang cekap dan ringkas, terima kasih kepada aplikasi pembelajaran pengukuhan.

AlphaDev adalah berdasarkan AlphaZero. DeepMind terkenal kerana membangunkan perisian AI yang boleh mempelajari peraturan permainan sendiri. Garis pemikiran ini telah terbukti sangat berkesan dan telah berjaya menyelesaikan banyak masalah permainan, seperti catur, Go dan "StarCraft". Walaupun butirannya berbeza-beza bergantung pada permainan yang anda mainkan, perisian DeepMind belajar melalui permainan berulang, terus meneroka cara untuk memaksimumkan skor anda.

Dua komponen teras AlphaDev ialah algoritma pembelajaran dan fungsi perwakilan.

Menggunakan gabungan DRL dan algoritma pengoptimuman carian rawak untuk memasang permainan ialah kaedah algoritma pembelajaran AlphaDev. Algoritma pembelajaran utama dalam AlphaDev ialah lanjutan daripada AlphaZero 33, algoritma DRL yang terkenal di mana rangkaian saraf dilatih untuk membimbing carian melalui permainan.

Fungsi ini digunakan untuk memantau prestasi keseluruhan pembangunan kod, meliputi struktur umum algoritma, serta penggunaan daftar dan memori x86. Sistem akan secara beransur-ansur memperkenalkan arahan pemasangan, ditambah secara bebas apabila membuat pilihan menggunakan kaedah carian pokok Monte Carlo yang dipinjam daripada sistem permainan. Struktur pokok membolehkan sistem menyempitkan carian dengan cepat ke kawasan terhad yang mengandungi sejumlah besar arahan berpotensi, manakala kaedah Monte Carlo memilih arahan khusus dari kawasan bercabang ini dengan tahap rawak. Ambil perhatian bahawa "arahan" yang dirujuk di sini adalah operasi seperti memilih daftar khusus untuk membuat perhimpunan yang sah dan lengkap. )

Sistem kemudiannya menilai kependaman dan status kesahihan kod pemasangan dan memberikan skor, yang dibandingkan dengan skor sebelumnya. Melalui pembelajaran pengukuhan, sistem ini dapat merekodkan maklumat kerja cabang yang berbeza dalam struktur pokok untuk keadaan program tertentu. Lama kelamaan, sistem menjadi biasa dengan cara memenangi permainan (berjaya menyelesaikan jenis itu) dengan skor tertinggi (mewakili kependaman terendah). Fungsi perwakilan utama AlphaDev adalah berdasarkan Transformers..

Untuk melatih AlphaDev menemui algoritma baharu, AlphaDev dalam setiap pusingan memerhati algoritma yang dijana dan maklumat yang terkandung dalam unit pemprosesan pusat (CPU), kemudian melengkapkan permainan dengan memilih arahan untuk ditambahkan pada algoritma. AlphaDev mesti cekap mencari sejumlah besar kombinasi arahan yang mungkin untuk mencari algoritma yang boleh disusun dan juga lebih pantas daripada algoritma terbaik semasa, manakala model ejen boleh diberi ganjaran berdasarkan ketepatan dan kependaman algoritma.

Gambar A: Permainan perhimpunan, Gambar B: Pengiraan ganjaran

Akhir sekali, AlphaDev menemui algoritma pengisihan baharu yang boleh meningkatkan pustaka pengisihan LLVM libc++: untuk urutan yang lebih pendek, pustaka pengisihan adalah 70% lebih pantas untuk jujukan melebihi 250,000 elemen, kelajuan dipertingkatkan Kira-kira 1.7%.

Secara khususnya, inovasi algoritma ini terutamanya terletak pada dua urutan arahan: AlphaDev Swap Move (swap move) dan AlphaDev Copy Move (copy move) Melalui kedua-dua arahan ini, AlphaDev melangkau satu langkah dan melakukan cara A untuk menyambungkan item itu mungkin kelihatan salah tetapi sebenarnya jalan pintas.

Kiri: Pelaksanaan sort3 asal dengan min(A,B,C). ‍

Gambar kanan: AlphaDev Swap Move - AlphaDev mendapati anda hanya memerlukan min(A,B).

Kiri: Pelaksanaan asal maks (B, min (A, C)) untuk algoritma pengisihan yang lebih besar yang mengisih lapan elemen.

‍ Kanan: AlphaDev mendapati bahawa hanya maks (B, min (A, C)) diperlukan apabila menggunakan pemindahan salinannya.

Kelebihan utama sistem ini ialah proses latihannya tidak memerlukan sebarang contoh kod. Sebaliknya, sistem secara autonomi menjana contoh kod dan kemudian menilai mereka. Dalam proses itu, ia secara beransur-ansur menguasai maklumat tentang penjujukan kombinasi arahan yang berkesan.

Daripada pengisihan kepada pencincangan

Selepas menemui algoritma pengisihan yang lebih pantas, DeepMind menguji sama ada AlphaDev boleh membuat generalisasi dan menambah baik pada algoritma sains komputer yang berbeza: pencincangan.

Hashing ialah algoritma asas yang digunakan dalam pengkomputeran untuk mendapatkan semula, menyimpan dan memampatkan data. Sama seperti pustakawan yang menggunakan sistem klasifikasi untuk mencari buku tertentu, algoritma pencincangan membantu pengguna mengetahui perkara yang mereka cari dan tempat untuk mencarinya. Algoritma ini mengambil data untuk kunci tertentu (cth. nama pengguna "Jane Doe") dan mencincangnya - proses yang menukar data mentah kepada rentetan unik (cth. 1234ghfty). Algoritma pencincangan ini digunakan untuk mendapatkan semula data yang berkaitan dengan kunci dengan cepat, mengelakkan keperluan untuk mencari seluruh data.

DeepMind menggunakan AlphaDev pada salah satu algoritma pencincangan yang paling biasa digunakan dalam struktur data dalam usaha untuk menemui algoritma yang lebih pantas. AlphaDev mendapati bahawa algoritma adalah 30% lebih pantas apabila fungsi cincang menggunakan data dalam julat 9-16 bait.

Tahun ini, algoritma pencincangan baharu AlphaDev telah dikeluarkan ke dalam perpustakaan Abseil sumber terbuka, tersedia kepada berjuta-juta pembangun di seluruh dunia, dan perpustakaan itu kini digunakan bertrilion kali setiap hari.

Kod kerja sebenar

Mekanisme pengisihan dalam program yang kompleks boleh mengendalikan koleksi besar item sewenang-wenangnya. Tetapi pada peringkat perpustakaan standard, keupayaan ini datang daripada satu siri fungsi khusus yang sangat terhad. Setiap fungsi ini hanya boleh mengendalikan satu atau beberapa situasi. Contohnya, sesetengah algoritma individu hanya boleh mengisih 3, 4 atau 5 entri. Kita boleh mengisih sebarang bilangan entri menggunakan satu set fungsi, tetapi kita hanya boleh mengisih sehingga 4 entri bagi setiap panggilan fungsi.

AlphaDev telah dilaksanakan oleh DeepMind pada setiap fungsi, tetapi kaedah operasi sebenar berbeza dengan ketara.. Ia adalah mungkin untuk menulis kod tanpa penyataan cawangan untuk mengendalikan fungsi yang mengendalikan bilangan entri tertentu, iaitu melaksanakan kod yang berbeza bergantung pada keadaan pembolehubah. Jadi prestasi kod cenderung berkadar songsang dengan bilangan arahan yang terlibat.

AlphaDev telah berjaya mengurangkan bilangan arahan dalam sort-3, sort-5 dan sort-8 dengan satu setiap satu, dan lebih banyak lagi dalam sort-6 dan sort-7. Tiada cara untuk menambah baik kod sedia ada boleh didapati hanya pada sort-4. Ujian berulang pada sistem sebenar menunjukkan bahawa lebih sedikit arahan meningkatkan prestasi.

Mengisih bilangan entri yang berubah-ubah memerlukan penyata cawangan dalam kod dan pemproses yang berbeza mempunyai bilangan komponen yang berbeza khusus untuk mengendalikan cawangan ini.

Para penyelidik menggunakan 100 peranti pengkomputeran yang berbeza semasa menilai keadaan ini. AlphaDev juga telah menemui cara untuk memerah lagi prestasi dalam senario jenis ini Mari kita ambil fungsi yang menyusun sehingga 4 item pada satu masa sebagai contoh untuk melihat cara ia beroperasi.

Dalam pelaksanaan semasa pustaka C++, kod tersebut perlu melakukan satu siri ujian untuk mengesahkan bilangan item yang perlu diisih, dan kemudian memanggil fungsi pengisihan yang sepadan berdasarkan bilangan item.

Kod AlphaDev yang diubah suai menggunakan idea yang lebih "ajaib": ia mula-mula menguji sama ada terdapat 2 item, dan jika ya, panggil fungsi yang sepadan untuk mengisih serta-merta. Jika nombor lebih besar daripada 2, kod akan mengisih 3 entri pertama dahulu. Dengan cara ini jika memang terdapat hanya 3 entri, hasil yang disusun dikembalikan. Memandangkan sebenarnya terdapat 4 item untuk diisih, AlphaDev akan menjalankan kod khusus untuk memasukkan item ke-4 ke kedudukan yang sesuai antara 3 item pertama yang telah diisih dengan cara yang sangat cekap.

Pendekatan ini kedengaran agak pelik, tetapi ternyata ia sentiasa berprestasi lebih baik daripada kod sedia ada.

Memandangkan AlphaDev menjana kod yang lebih cekap, pasukan penyelidik merancang untuk menggabungkan semula keputusan ini ke dalam perpustakaan C++ standard LLVM. Tetapi masalahnya ialah kod itu dalam format pemasangan, bukan C++. Oleh itu, mereka perlu bekerja ke belakang untuk mencari kod C++ yang menjana perhimpunan yang sama.

Versi tulisan semula ayat ini: Kod ini kini telah disepadukan ke dalam rantai alat LLVM dan dikemas kini buat kali pertama dalam hampir sedekad. Penyelidik menganggarkan bahawa kod baharu yang dijana oleh AlphaDev dilaksanakan bertrilion kali setiap hari.

Kesimpulan

Ini sangat hebat! Kami pengaturcara telah lama mempelajari tugas pengisihan asas ini, tetapi kini kami 70% lebih pantas. Terdapat sesuatu yang sangat menarik tentang AI dalam algoritma dan perpustakaan yang kita semua bergantung pada penyampaian kelajuan yang ketara. "Sesetengah pembangun menyatakan keterujaan tentang hasil Google DeepMind.

Tetapi sesetengah pembangun tidak membelinya: "Agak mengecewakan...1.7% peningkatan? 70% daripada urutan 5 elemen? Mungkin penyelidikan gunaan yang paling tidak popular dan paling tidak realistik..." Terdapat juga pemaju Kata pengarang : "Bukankah agak mengelirukan untuk mengatakan bahawa algoritma baharu telah ditemui? Ia kelihatan lebih seperti pengoptimuman algoritma. Lagipun, ia tetap keren."

Pautan rujukan:

https://arstechnica.com/science/2023/06/googles-deepmind-develops-a-system-that-writes-efficient-algorithms/

https://www.deepmind.com/blog/alphadev-discovers-faster-sorting-algorithm

Kedalaman: Mengapakah gergasi seperti Snowflake tidak muncul dalam medan pangkalan data China?

Keruntuhan paling pelik dalam tujuh belas tahun! Untuk menghalang OpenAI dan Google daripada mendapatkan data secara percuma, Reddit mengenakan bayaran API yang besar dan memfitnah pembangun, menyebabkan bantahan berskala besar dalam komuniti

Kod “Mencuri” untuk membina syarikat, memalsukan kelayakan akademik, memperoleh AS$100 juta dalam 6 hari tetapi tidak membayar gaji, Ketua Pegawai Eksekutif AI unicorn ini bertindak balas secara peribadi selepas disoal siasat berulang kali

Atas ialah kandungan terperinci Google menggunakan AI untuk memecahkan meterai sepuluh tahun algoritma pengisihan Ia dilaksanakan bertrilion kali setiap hari, tetapi netizen mengatakan ia adalah penyelidikan yang paling tidak realistik?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!