DeepMind melancarkan algoritma pengisihan yang mengejutkan, dan perpustakaan C++ sedang sibuk mengemas kini!

Klik untuk mengambil bahagian dalam soal selidik tinjauan kandungan laman web 51CTO

Disusun | Wang Ruiping, Yan Zheng

AlphaGo mempunyai seorang lagi "adik lelaki" yang menyertai!

Google DeepMind "melancarkan" siri Alpha ke dalam algoritma pengisihan dan melancarkan AlphaDev.

Ia seperti "kaedah rahsia pembangunan". Dengan menggunakan AI pembelajaran pengukuhan untuk menemui algoritma pengisihan dan algoritma pencincangan, ia secara paksa mempercepatkan algoritma yang direka oleh pengaturcara manusia sebanyak kira-kira 70% dan 30% masing-masing.

Sebaik sahaja hasil penyelidikan dikeluarkan, mereka serta-merta menyalakan bulatan perisian! Tiba-tiba, kelajuan berjalan berjuta-juta perisian di seluruh dunia melonjak, secara langsung mengatasi pencapaian saintis dan jurutera selama beberapa dekad, dan perpustakaan C++ standard LLVM yang tidak dikemas kini dalam sepuluh tahun telah dikemas kini.

(Sumber: Nature)

Ini juga merupakan teknologi mengganggu yang dilancarkan selepas penggabungan dua jabatan AI Google. Kertas kerja itu diterbitkan dalam Nature di bawah tajuk "Algoritma pengisihan lebih pantas ditemui menggunakan pembelajaran pengukuhan mendalam". Pengarang pertama kertas itu ialah Daniel Mankowitz, seorang saintis komputer di DeepMind.

1. Evolusi: Asal-usul algoritma pengisihan

Isih ialah kaedah menyusun banyak item dalam susunan tertentu, contohnya, tiga huruf dalam susunan abjad, daripada terbesar hingga terkecil Jujukan lima nombor atau mengisih pangkalan data yang mengandungi berjuta-juta rekod.

Kaedah pesanan boleh dikesan kembali ke abad kedua hingga ketiga dan masih berkembang. Pada mulanya, para ulama menyusun secara manual beribu-ribu buku di rak Perpustakaan Iskandariah mengikut susunan abjad.

Selepas Revolusi Perindustrian, mesin pengisih sendiri—mesin penjadual yang menyimpan maklumat pada kad tebuk—dicipta untuk mengumpul hasil Banci A.S. 1890.

Pada tahun 1950-an, komputer komersial mula meningkat, dan algoritma pengisihan segera dihasilkan. Masukkan beberapa nombor yang tidak diisih ke dalam algoritma pengisihan dan ia akan menghasilkan urutan nombor yang diisih.

Banyak teknik dan algoritma pengisihan yang berbeza masih digunakan dalam pangkalan kod di mana-mana untuk memproses sejumlah besar data.        

Selepas berdekad-dekad penyelidikan dan pembangunan, kecekapan algoritma pengisihan ini telah terus dipertingkatkan dan diiktiraf oleh saintis komputer dan pengaturcara. Walau bagaimanapun, cabaran besar kekal untuk penambahbaikan selanjutnya.

2. Sorotan: Bagaimana untuk menggunakan AlphaDev untuk menjana algoritma pengisihan baharu?

Para penyelidik pada asalnya menggunakan AlphaDev untuk menjana algoritma baharu dengan matlamat untuk menyelesaikan tugasan yang diberikan dengan cekap.

AlphaDev telah membina algoritma baharu sepenuhnya dan tidak dibangunkan berdasarkan algoritma sebelumnya, jadi ia boleh dianggap sebagai asal. Dalam proses itu, ia menggunakan bahasa perantaraan kod pemasangan. AlphaDev menjadikannya lebih mudah untuk mencipta algoritma yang cekap kerana bahasa itu lebih dekat dengan arahan binari komputer.

Khususnya, AlphaDev menjana arahan setiap kali dan kemudian menguji sama ada output adalah betul Ia juga menetapkan keperluan dalam model untuk menjana algoritma terpendek.

Apabila diminta untuk mereka bentuk semula algoritma pengisihan, AlphaDev secara rawak menjana algoritma pengisihan baharu yang 70% lebih pantas daripada algoritma sedia ada dan boleh mengisih lima data pada masa yang sama. Ia juga 1.7% lebih pantas daripada algoritma terbaik apabila mengisih 250,000 data.

Inovasi ini akan memberi impak yang besar pada algoritma global, kerana algoritma pengisihan digunakan secara meluas oleh pelbagai perisian biasa. DeepMind telah membuka sumbernya dan menyepadukannya ke dalam perpustakaan standard Libc++.

Menurut penyelidik DeepMind: “Disebabkan bilangan kombinasi arahan yang banyak, proses penyelidikan yang kelihatan mudah adalah amat sukar.”

3 >

Tambahan pula, AlphaDev ialah model yang lebih maju yang direka bentuk berdasarkan struktur AlphaZero. AlphaZero sebelum ini merupakan model pembelajaran pengukuhan DeepMind dan telah mengalahkan juara dunia dalam Go, catur dan permainan catur lain.

Melalui percubaan ini, model baharu AlphaDev menggunakan kelebihan uniknya dalam beralih daripada bermain permainan kepada menyelesaikan masalah saintifik, dan daripada simulasi percubaan kepada aplikasi dunia sebenar.

Penyelidik mensimulasikan pengisihan sebagai "permainan pemasangan" pemain tunggal untuk melatih AlphaDev menemui algoritma baharu. Semasa setiap giliran permainan, AlphaDev memerhati algoritma yang dijana dan maklumat yang terkandung dalam CPU, dan kemudian memilih arahan untuk ditambahkan pada algoritma untuk membuat setiap langkah.

Makalah tersebut menyebut bahawa permainan pemasangan adalah sangat sukar kerana AlphaDev mesti berupaya mencari dengan cekap melalui sejumlah besar kombinasi arahan yang mungkin untuk mendapatkan algoritma yang boleh diisih.

Bilangan kombinasi arahan adalah serupa dengan bilangan zarah dalam alam semesta atau bilangan kemungkinan gabungan pergerakan dalam catur (10120 permainan) dan Go (10700 permainan akan membatalkan keseluruhan algoritma).

Model kemudian mengeluarkan algoritma dan membandingkannya dengan output yang dijangkakan, memberi ganjaran kepada ejen berdasarkan ketepatan dan kependaman algoritma.

Apabila membina algoritma, setiap kali arahan dimasukkan, AlphaDev menyemak ketepatan dengan membandingkan algoritma keluaran dengan hasil yang dijangkakan (untuk algoritma pengisihan, ini bermakna selepas memasukkan nombor tidak tertib, ia boleh mengeluarkan disusun dengan betul nombor).

Model memberi ganjaran kepada AlphaDev kerana mengisih nombor dengan betul dan cekap. Akhirnya AlphaDev memenangi pertandingan dengan menemui program yang lebih tepat dan lebih pantas.

4. Inovasi algoritma: swap move dan salin urutan arahan

AlphaDev bukan sahaja menjana algoritma yang lebih pantas, tetapi juga menginovasi dua urutan arahan.

Secara khusus, algoritma pengisihan yang dihasilkannya termasuk dua urutan arahan baharu: swap move dan copy move, dan satu arahan akan disimpan setiap kali ia digunakan. Para penyelidik memanggilnya "pergerakan pertukaran dan penyalinan AlphaDev."

Kaedah novel ini mengingatkan kepada "Langkah 37" AlphaGo - permainan catur "counter-intuitif" yang mengejutkan penonton dan mencipta kegagalan Tangan pemain catur legenda.

Dengan menukar langkah dan menyalin urutan arahan pergerakan, AlphaDev melangkau satu langkah, melengkapkan matlamat dengan cara yang kelihatan seperti kesilapan tetapi sebenarnya adalah jalan pintas. Ini bermakna AlphaDev mempunyai keupayaan untuk menemui penyelesaian awal dan cuba memperbaik algoritma sains komputer.

5 Ujian: Promosikan dan perbaiki algoritma pencincangan

Selepas menemui algoritma pengisihan yang lebih pantas, penyelidik cuba menerapkannya pada algoritma sains komputer yang lain - promosi dan penambahbaikan algoritma pencincangan.

Algoritma cincang ialah algoritma asas dalam pengkomputeran dan digunakan untuk mendapatkan semula, menyimpan dan memampatkan data. Sama seperti pustakawan menggunakan sistem klasifikasi untuk mencari buku tertentu, algoritma pencincangan membantu pengguna mengetahui perkara yang mereka cari dan tempat untuk mencarinya.

Algoritma ini dapat mengambil data untuk kunci tertentu (cth., nama pengguna "Jane Doe") dan mengisih cincang - menukar data mentah kepada rentetan unik (cth., 1234ghty).

Komputer menggunakan cincang ini untuk mendapatkan semula data yang berkaitan dengan kunci dengan cepat, dan bukannya mencari semua data.

Penyelidik menggunakan AlphaDev pada salah satu algoritma pencincangan yang paling biasa digunakan dalam struktur data dalam usaha untuk menemui algoritma yang lebih pantas. Apabila digunakan pada julat 9-16 bait fungsi cincang, AlphaDev menghasilkan algoritma yang 30% lebih pantas.

Awal tahun ini, algoritma pencincangan baharu yang dihasilkan oleh AlphaDev telah dikeluarkan ke dalam pustaka Abseil sumber terbuka, menjadikannya tersedia kepada berjuta-juta pembangun di seluruh dunia Dianggarkan ia kini digunakan oleh berpuluh-puluh ribu setiap orang hari.

6. Momentum pengumpulan: mengambil langkah pertama dalam membangunkan AGI

Dengan mengoptimumkan "algoritma pengisihan dan pencincang", AlphaDev telah menunjukkan keupayaan untuk menjana algoritma baharu praktikal yang berbeza.

Ini juga merupakan langkah pertama AlphaDev ke arah membangunkan alatan kecerdasan buatan umum (AGI) yang serupa juga boleh membantu mengoptimumkan keseluruhan ekosistem pengkomputeran dan menyelesaikan masalah lain yang memberi manfaat kepada masyarakat.

Walaupun mengoptimumkan algoritma dalam ruang arahan pemasangan peringkat rendah sangat berkuasa, ia juga mempunyai had. Pada masa ini, pasukan sedang mengkaji keupayaan AlphaDev untuk mengoptimumkan algoritma dalam bahasa peringkat tinggi (seperti C++), yang akan lebih bermanfaat kepada pembangun.

Ringkasnya, penemuan baharu ini diharapkan dapat memberi inspirasi kepada pembangun untuk mencipta teknologi dan kaedah baharu, seterusnya mengoptimumkan algoritma asas dan mencipta ekosistem pengkomputeran yang lebih kukuh dan mampan.

7. Sumber terbuka: satu kejayaan penting dalam kod pengoptimuman AI

Sebelum ini, algoritma pengisihan telah digunakan bertrilion kali setiap hari. Dengan pertumbuhan keperluan pengkomputeran, orang ramai mempunyai keperluan prestasi yang lebih tinggi dan lebih tinggi untuk algoritma. Walaupun jurutera manusia telah menemui algoritma pengisihan yang berbeza, selepas beberapa dekad pengoptimuman, adalah sukar untuk membuat penemuan dan tidak dapat memenuhi permintaan yang semakin meningkat.

Hari ini, AlphaDev telah menemui algoritma pengisihan yang lebih pantas untuk mengisih data.

Algoritma kedudukan baharu boleh digunakan untuk menentukan kedudukan hasil carian dalam talian dan siaran sosial, serta memproses data pada komputer dan telefon mudah alih.

Adalah wajar diraikan bahawa algoritma pengisihan baharu telah bersumberkan terbuka dalam pustaka C++ utama. Ia kini digunakan oleh berjuta-juta pembangun dan syarikat di seluruh dunia untuk pengkomputeran awan, beli-belah dalam talian, pengurusan rantaian bekalan dan banyak lagi.

Ringkasnya, menggunakan alat kecerdasan buatan untuk mengoptimumkan algoritma akan mengubah sepenuhnya cara pengaturcaraan tradisional. Ini adalah kali pertama dalam lebih daripada sepuluh tahun perpustakaan pengisihan telah diubah, dan kali pertama algoritma yang direka bentuk oleh model pembelajaran pengukuhan telah ditambahkan pada perpustakaan pengisihan Oleh itu, ia telah menjadi kejayaan penting dalam menggunakan kecerdasan buatan untuk mengoptimumkan kod.

8. Pengguna: Mungkin ini hanya gimik

Pengguna mempunyai pendapat yang bercampur-campur tentang hasil penyelidikan Kebanyakan suara di Twitter memuji:

Ketahui asas Tugasan penjujukan ialah salah satu kemahiran yang dikuasai oleh pengaturcara awal, dan kemahiran ini meningkatkan kelajuan sebanyak 70%. Sangat mengujakan untuk melihat memanfaatkan AI untuk menyampaikan pecutan yang ketara dalam algoritma dan perpustakaan yang kita semua harapkan". , mula mengoptimumkan dari peringkat pemasangan”

Namun, sesetengah pengaturcara menganggap ini hanyalah gimik, dan DeepMind membesar-besarkan fungsi algoritma

Pertama sekali, dari sudut kecekapan , Ia hanya mengira kependaman algoritma, dan bukannya mengubah kerumitan masa

Selain itu, ia sebenarnya tidak mengubah susunan, yang biasa dalam pelbagai pustaka kod lain:

1.https://www.nature.com/articles/s41586-023-06004-9

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

3.https://www.deepmind.com/blog/optimising-computer-systems-with-more-generalised-ai-tools

4 .https://twitter.com /demishassabis

Atas ialah kandungan terperinci DeepMind melancarkan algoritma pengisihan yang mengejutkan, dan perpustakaan C++ sedang sibuk mengemas kini!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!