Χωρίς αμφιβολία, όποιος έχει σπουδάσει βασική επιστήμη των υπολογιστών έχει αφιερώσει χρόνο επινοώντας έναν αλγόριθμο ταξινόμησης – κώδικα που λαμβάνει μια μη ταξινομημένη λίστα στοιχείων και τα βάζει σε αύξουσα ή φθίνουσα σειρά. Είναι μια ενδιαφέρουσα πρόκληση επειδή υπάρχουν τόσοι πολλοί τρόποι για να γίνει αυτό και επειδή οι άνθρωποι έχουν αφιερώσει πολύ χρόνο για να βρουν πώς να κάνουν αυτήν την ταξινόμηση όσο το δυνατόν πιο αποτελεσματικά.
Η ταξινόμηση είναι τόσο βασική που οι αλγόριθμοι είναι ενσωματωμένοι στις περισσότερες τυπικές βιβλιοθήκες γλωσσών προγραμματισμού. Και στην περίπτωση της βιβλιοθήκης C++ που χρησιμοποιείται με τον μεταγλωττιστή LLVM, ο κώδικας δεν έχει αγγιχτεί εδώ και μια δεκαετία.
Αλλά η ομάδα DeepMind AI της Google έχει πλέον αναπτύξει ένα εργαλείο ενίσχυσης εκμάθησης που μπορεί να αναπτύξει άκρως βελτιστοποιημένους αλγόριθμους χωρίς πρώτα να έχει εκπαιδευτεί σε παραδείγματα ανθρώπινου κώδικα. Το κόλπο ήταν να τον προετοιμάσει να αντιμετωπίσει τον προγραμματισμό ως παιχνίδι.
Όλα είναι ένα παιχνίδι
Το DeepMind, μεταξύ άλλων, είναι γνωστό για την ανάπτυξη λογισμικού που διδάσκει τον εαυτό του πώς να παίζει παιχνίδια. Αυτή η προσέγγιση έχει αποδειχθεί εξαιρετικά αποτελεσματική, κατακτώντας παιχνίδια τόσο διαφορετικά όσο το σκάκι, ΠαειΚαι StarCraft. Ενώ οι λεπτομέρειες ποικίλλουν ανάλογα με το παιχνίδι με το οποίο ασχολείται, το πρόγραμμα μαθαίνει παίζοντας μόνο του και ανακαλύπτει επιλογές που του επιτρέπουν να μεγιστοποιήσει το σκορ.
Επειδή δεν έχει εκπαιδευτεί σε παιχνίδια που παίζονται από ανθρώπους, το σύστημα DeepMind μπορεί να βρει τρόπους να παίζει παιχνίδια που οι άνθρωποι δεν έχουν σκεφτεί. Φυσικά, δεδομένου ότι παίζει πάντα ενάντια στον εαυτό του, υπάρχουν περιπτώσεις που έχει αναπτύξει τυφλά σημεία που οι άνθρωποι μπορούν να εκμεταλλευτούν.
Αυτή η προσέγγιση σχετίζεται στενά με τον προγραμματισμό. Τα σπουδαία γλωσσικά παραδείγματα γράφουν αποτελεσματικό κώδικα επειδή έχουν δει πολλά ανθρώπινα παραδείγματα. Αλλά εξαιτίας αυτού, είναι πολύ απίθανο να αναπτύξουν κάτι που οι άνθρωποι δεν έχουν κάνει πριν. Εάν επιδιώκουμε να βελτιώσουμε καλά κατανοητούς αλγόριθμους, όπως συναρτήσεις ταξινόμησης, βασίζοντας κάτι στον υπάρχοντα ανθρώπινο κώδικα, στην καλύτερη περίπτωση, θα έχετε ισοδύναμη απόδοση. Αλλά πώς μπορείτε να κάνετε ένα AI να επιλέξει πραγματικά μια νέα προσέγγιση;
Οι άνθρωποι στο DeepMind έχουν υιοθετήσει την ίδια προσέγγιση που έκαναν με το σκάκι και Παει: Μετέτρεψαν τη βελτιστοποίηση κώδικα σε παιχνίδι. Το σύστημα AlphaDev ανέπτυξε αλγόριθμους μεταγλώττισης x86 που αντιμετώπιζαν τον λανθάνοντα κώδικα ως επιτυχία και προσπάθησε να ελαχιστοποιήσει αυτό το χτύπημα διασφαλίζοντας παράλληλα ότι ο κώδικας ολοκληρώθηκε χωρίς σφάλματα. Μέσω της ενισχυτικής μάθησης, το AlphaDev αναπτύσσει σταδιακά την ικανότητα να γράφει εξαιρετικά αποδοτικό και ισχυρό κώδικα.
Μέσα στο AlphaDev
Το να λέμε ότι το σύστημα βελτιώνει τον λανθάνοντα χρόνο είναι πολύ άλλο θέμα από το να εξηγήσουμε πώς λειτουργεί. Όπως τα περισσότερα άλλα πολύπλοκα συστήματα τεχνητής νοημοσύνης, το AlphaDev αποτελείται από πολλά διακριτά στοιχεία. Η μία είναι η λειτουργία αναπαράστασης, η οποία παρακολουθεί τη συνολική απόδοση του κώδικα καθώς αναπτύσσεται. Αυτό περιλαμβάνει τη συνολική δομή του αλγορίθμου, καθώς και τη χρήση καταχωρητών x86 και μνήμης.
Το σύστημα προσθέτει οδηγίες συναρμολόγησης ξεχωριστά, που επιλέγονται από α Βρείτε το δέντρο του Μόντε Κάρλο– πάλι, μια προσέγγιση δανεισμένη από συστήματα τυχερών παιχνιδιών. Η πτυχή “δέντρο” αυτής της προσέγγισης επιτρέπει στο σύστημα να περιορίζεται γρήγορα σε μια περιορισμένη περιοχή από ένα μεγάλο εύρος πιθανών εντολών, ενώ το Monte Carlo προσθέτει έναν βαθμό τυχαίας στις ακριβείς οδηγίες που επιλέγονται από αυτόν τον κλάδο. (Σημειώστε ότι η “βοήθεια” σε αυτό το πλαίσιο περιλαμβάνει πράγματα όπως οι συγκεκριμένες εγγραφές που επιλέχθηκαν για τη δημιουργία μιας έγκυρης, ολοκληρωμένης συναρμολόγησης.)
Στη συνέχεια, το σύστημα αξιολογεί την κατάσταση του κωδικού συναρμολόγησης ως προς την καθυστέρηση και την εγκυρότητα και του εκχωρεί μια βαθμολογία και τη συγκρίνει με τη βαθμολογία της προηγούμενης βαθμολογίας. Και μέσω της ενισχυτικής μάθησης, συσχετίζει πληροφορίες σχετικά με τον τρόπο λειτουργίας των διαφορετικών κλάδων του δέντρου, δεδομένης της κατάστασης του προγράμματος. Με την πάροδο του χρόνου, «μαθαίνεις» πώς να επιτυγχάνεις μια συνθήκη νικηφόρου παιχνιδιού – ολοκληρώθηκε η ταξινόμηση – με μέγιστο σκορ, που σημαίνει ελάχιστο λανθάνον χρόνο.
Το κύριο πλεονέκτημα αυτού του συστήματος είναι ότι η εκπαίδευσή του δεν χρειάζεται να περιλαμβάνει παραδείγματα κώδικα. Αντίθετα, το σύστημα δημιουργεί τα δικά του παραδείγματα κώδικα και στη συνέχεια τα αξιολογεί. Στη διαδικασία, κλείνεται από πληροφορίες σχετικά με το ποια σύνολα εντολών είναι αποτελεσματικά στην ταξινόμηση.
Χρήσιμος κώδικας
Η ταξινόμηση σε πολύπλοκα προγράμματα μπορεί να χειριστεί μεγάλες, αυθαίρετες ομάδες στοιχείων. Αλλά στο επίπεδο των τυπικών βιβλιοθηκών, δημιουργούνται από ένα μεγάλο σύνολο πολύ συγκεκριμένων λειτουργιών που χειρίζονται μόνο μία κατάσταση ή λίγες περιπτώσεις. Για παράδειγμα, υπάρχουν ξεχωριστοί αλγόριθμοι για την ταξινόμηση τριών στοιχείων, τεσσάρων στοιχείων και πέντε στοιχείων. Και υπάρχει ένα άλλο σύνολο συναρτήσεων που μπορούν να χειριστούν έναν αυθαίρετο αριθμό στοιχείων έως το μέγιστο – που σημαίνει ότι μπορείτε να καλέσετε ένα που ταξινομεί έως τέσσερα στοιχεία, αλλά όχι περισσότερα.
Το DeepMind έχει ρυθμίσει το AlphaDev σε καθεμία από αυτές τις λειτουργίες, αλλά λειτουργούν πολύ διαφορετικά. Για συναρτήσεις που χειρίζονται έναν καθορισμένο αριθμό στοιχείων, είναι δυνατή η εγγραφή κώδικα χωρίς διακλαδώσεις όπου εκτελεί διαφορετικό κώδικα με βάση την κατάσταση της μεταβλητής. Ως αποτέλεσμα, η απόδοση αυτού του κωδικού είναι γενικά ανάλογη με τον αριθμό των απαιτούμενων εντολών. Το AlphaDev μπόρεσε να ξυρίσει όλες τις οδηγίες Ταξινόμησης-3, Ταξινόμησης-5 και Ταξινόμησης-8 και ακόμη περισσότερες οδηγίες Ταξινόμησης-6 και Ταξινόμησης-7. Υπήρχε μόνο ένας (τάξις 4) όπου δεν μπορούσε να βρει τρόπο να βελτιώσει τον ανθρώπινο κώδικα. Η επανειλημμένη εκτέλεση του κώδικα σε πραγματικά συστήματα έδειξε ότι λιγότερες οδηγίες είχαν ως αποτέλεσμα καλύτερη απόδοση.
Η ταξινόμηση ενός μεταβλητού αριθμού καταχωρήσεων περιλαμβάνει διακλάδωση στον κώδικα και διαφορετικοί επεξεργαστές έχουν διαφορετικές ποσότητες υλικού αφιερωμένου στο χειρισμό αυτών των διακλαδώσεων. Επομένως, ο κώδικας αξιολογήθηκε με βάση την απόδοσή του σε 100 διαφορετικές συσκευές. Και εδώ, η AlphaDev βρήκε τρόπους για να συμπιέζει την επιπλέον απόδοση και θα ρίξουμε μια ματιά στο πώς να το κάνουμε σε μία περίπτωση: μια συνάρτηση που ταξινομεί έως και τέσσερα στοιχεία.
Στην τρέχουσα υλοποίηση στη βιβλιοθήκη C++, ο κώδικας εκτελεί μια σειρά δοκιμών για να δει πόσα στοιχεία χρειάζεται να ταξινομήσει και καλεί τη συνάρτηση προσαρμοσμένης ταξινόμησης για αυτόν τον αριθμό στοιχείων. Ο αναθεωρημένος κώδικας κάνει κάτι ακόμα πιο περίεργο. Ελέγχει εάν υπάρχουν δύο στοιχεία και καλεί μια ξεχωριστή συνάρτηση για να τα ταξινομήσει εάν είναι απαραίτητο. Εάν το πλήθος είναι μεγαλύτερο από δύο, ο κωδικός καλεί να ταξινομηθούν τα τρία πρώτα. Εάν υπάρχουν τρία στοιχεία, τα αποτελέσματα αυτού του είδους θα επιστραφούν.
Ωστόσο, εάν υπάρχουν τέσσερα στοιχεία για ταξινόμηση, εκτελεί εξειδικευμένο κώδικα που είναι πολύ αποτελεσματικός στην εισαγωγή ενός τέταρτου στοιχείου στην κατάλληλη θέση μέσα σε μια σειρά τριών ταξινομημένων στοιχείων. Αυτό φαίνεται σαν μια περίεργη προσέγγιση, αλλά έχει σταθερά καλύτερες επιδόσεις από τον υπάρχοντα κώδικα μου.
σε παραγωγή
Επειδή το AlphaDev παρήγαγε πιο αποτελεσματικό κώδικα, η ομάδα ήθελε να τον ενσωματώσει ξανά στην τυπική βιβλιοθήκη LLVM C++. Το πρόβλημα εδώ είναι ότι ο κώδικας ήταν στη συναρμολόγηση και όχι στη C++. Έτσι, έπρεπε να δουλέψουν ανάποδα και να καταλάβουν ποιος κώδικας C++ θα παρήγαγε το ίδιο συγκρότημα. Μόλις έγινε αυτό, ο κώδικας συγχωνεύτηκε στην αλυσίδα εργαλείων LLVM – η πρώτη φορά που ορισμένοι από τον κώδικα τροποποιήθηκαν σε πάνω από μια δεκαετία.
Ως αποτέλεσμα, οι ερευνητές έχουν υπολογίσει ότι ο κώδικας AlphaDev εκτελείται τώρα τρισεκατομμύρια φορές την ημέρα.
Nature, 2023. DOI: 10.1038 / s41586-023-06004-9 (σχετικά με τα DOI).
“Τηλεοπτικός γκουρού. Υποστηρικτής της ζόμπι. Οπαδός του διαδικτύου. Πιστοποιημένος μπύρας. Υπερήφανος αναγνώστης. Φανταστικός αλκοόλ. Βραβευμένος επιχειρηματίας.”