Το Deep Mind AlphaTensor θα ανακαλύψει νέους αλγόριθμους

Η Deep Mind έχει επεκτείνει το AlphaZero στα μαθηματικά για να ξεκλειδώσει νέες δυνατότητες για αλγόριθμους έρευνας.

Το AlphaTensor, βασίζεται στο AlphaZero, έναν πράκτορα που έχει δείξει υπεράνθρωπες επιδόσεις σε επιτραπέζια παιχνίδια, όπως το σκάκι, το Go και το shogi, και αυτό το έργο δείχνει το ταξίδι του AlphaZero από το να παίζει παιχνίδια μέχρι την αντιμετώπιση άλυτων μαθηματικών προβλημάτων για πρώτη φορά.

Οι αρχαίοι Αιγύπτιοι δημιούργησαν έναν αλγόριθμο για τον πολλαπλασιασμό δύο αριθμών χωρίς να απαιτείται πίνακας πολλαπλασιασμού και ο Έλληνας μαθηματικός Ευκλείδης περιέγραψε έναν αλγόριθμο για τον υπολογισμό του μεγαλύτερου κοινού διαιρέτη, ο οποίος χρησιμοποιείται ακόμα και σήμερα.

Κατά την Ισλαμική Χρυσή Εποχή, ο Πέρσης μαθηματικός Muhammad ibn Musa al-Khwarizmi σχεδίασε νέους αλγόριθμους για την επίλυση γραμμικών και τετραγωνικών εξισώσεων. Στην πραγματικότητα, το όνομα του al-Khwarizmi, μεταφρασμένο στα λατινικά ως Algoritmi, οδήγησε στον όρο αλγόριθμος. Όμως, παρά την εξοικείωση με τους αλγόριθμους σήμερα –που χρησιμοποιούνται σε όλη την κοινωνία από την άλγεβρα στην τάξη μέχρι την επιστημονική έρευνα αιχμής– η διαδικασία ανακάλυψης νέων αλγορίθμων είναι απίστευτα δύσκολη και αποτελεί παράδειγμα των εκπληκτικών συλλογιστικών ικανοτήτων του ανθρώπινου μυαλού.

Δημοσίευσαν στο Nature. Το AlphaTensor είναι το πρώτο σύστημα τεχνητής νοημοσύνης (AI) για την ανακάλυψη νέων, αποτελεσματικών και αποδεδειγμένα σωστών αλγορίθμων για θεμελιώδεις εργασίες όπως ο πολλαπλασιασμός πινάκων. Αυτό ρίχνει φως σε μια ανοιχτή ερώτηση 50 ετών στα μαθηματικά σχετικά με την εύρεση του ταχύτερου τρόπου πολλαπλασιασμού δύο πινάκων.

Εκπαιδευμένο από την αρχή, το AlphaTensor ανακαλύπτει αλγόριθμους πολλαπλασιασμού μητρών που είναι πιο αποτελεσματικοί από τους υπάρχοντες αλγόριθμους που έχουν σχεδιαστεί από ανθρώπους και υπολογιστή. Παρά τη βελτίωση σε σχέση με τους γνωστούς αλγόριθμους, σημειώνουν ότι ένας περιορισμός του AlphaTensor είναι η ανάγκη προκαθορισμού ενός συνόλου πιθανών καταχωρήσεων παραγόντων F, που διακριτοποιεί τον χώρο αναζήτησης, αλλά μπορεί ενδεχομένως να οδηγήσει σε απώλεια αποτελεσματικών αλγορίθμων. Μια ενδιαφέρουσα κατεύθυνση για μελλοντική έρευνα είναι η προσαρμογή του AlphaTensor στην αναζήτηση του F. Ένα σημαντικό πλεονέκτημα του AlphaTensor είναι η ευελιξία του να υποστηρίζει σύνθετες στοχαστικές και μη διαφοροποιήσιμες ανταμοιβές (από την κατάταξη του τανυστήρα έως την πρακτική αποτελεσματικότητα σε συγκεκριμένο υλικό), εκτός από την εύρεση αλγορίθμων για προσαρμοσμένες λειτουργίες σε μεγάλη ποικιλία χώρων (όπως πεπερασμένα πεδία). Πιστεύουν ότι αυτό θα ωθήσει τις εφαρμογές του AlphaTensor προς το σχεδιασμό αλγορίθμων που βελτιστοποιούν μετρήσεις που δεν λάβαμε υπόψη εδώ, όπως η αριθμητική σταθερότητα ή η χρήση ενέργειας.

Η ανακάλυψη αλγορίθμων πολλαπλασιασμού πινάκων έχει εκτεταμένες επιπτώσεις, καθώς ο πολλαπλασιασμός πινάκων βρίσκεται στον πυρήνα πολλών υπολογιστικών εργασιών, όπως η αντιστροφή πίνακα, ο υπολογισμός της ορίζουσας και η επίλυση γραμμικών συστημάτων.

Η διαδικασία και η πρόοδος της αυτοματοποίησης αλγοριθμικής ανακάλυψης
Πρώτον, μετέτρεψαν το πρόβλημα της εύρεσης αποτελεσματικών αλγορίθμων για πολλαπλασιασμό μήτρας σε ένα παιχνίδι ενός παίκτη. Σε αυτό το παιχνίδι, ο πίνακας είναι ένας τρισδιάστατος τανυστής (πίνακας αριθμών), ο οποίος καταγράφει πόσο μακριά είναι ο τρέχων αλγόριθμος από τον σωστό. Μέσω ενός συνόλου επιτρεπόμενων κινήσεων, που αντιστοιχούν σε οδηγίες αλγορίθμου, ο παίκτης προσπαθεί να τροποποιήσει τον τανυστή και να μηδενίσει τις καταχωρίσεις του. Όταν ο παίκτης το καταφέρει, αυτό έχει ως αποτέλεσμα έναν αποδεδειγμένα σωστό αλγόριθμο πολλαπλασιασμού πινάκων για οποιοδήποτε ζεύγος πινάκων και η αποτελεσματικότητά του αποτυπώνεται από τον αριθμό των βημάτων που γίνονται για να μηδενιστεί ο τανυστής.

Αυτό το παιχνίδι είναι απίστευτα προκλητικό – ο αριθμός των πιθανών αλγορίθμων που πρέπει να ληφθούν υπόψη είναι πολύ μεγαλύτερος από τον αριθμό των ατόμων στο σύμπαν, ακόμη και για μικρές περιπτώσεις πολλαπλασιασμού μήτρας. Σε σύγκριση με το παιχνίδι Go, το οποίο παρέμεινε πρόκληση για την τεχνητή νοημοσύνη για δεκαετίες, ο αριθμός των πιθανών κινήσεων σε κάθε βήμα του παιχνιδιού τους είναι 30 τάξεις μεγέθους μεγαλύτερος (πάνω από 10^33 για μία από τις ρυθμίσεις που εξετάζουν).

Ουσιαστικά, για να παίξει κανείς καλά αυτό το παιχνίδι, πρέπει να εντοπίσει τις πιο μικροσκοπικές βελόνες σε μια τεράστια στοίβα άρων. Για να αντιμετωπίσουμε τις προκλήσεις αυτού του τομέα, ο οποίος αποκλίνει σημαντικά από τα παραδοσιακά παιχνίδια, αναπτύξαμε πολλά κρίσιμα στοιχεία, συμπεριλαμβανομένης μιας νέας αρχιτεκτονικής νευρωνικών δικτύων που ενσωματώνει επαγωγικές μεροληψίες ειδικά για το πρόβλημα, μια διαδικασία δημιουργίας χρήσιμων συνθετικών δεδομένων και μια συνταγή για την αξιοποίηση συμμετριών του πρόβλημα.

Στη συνέχεια εκπαίδευσαν έναν πράκτορα AlphaTensor χρησιμοποιώντας ενισχυτική εκμάθηση για να παίξει το παιχνίδι, ξεκινώντας χωρίς καμία γνώση σχετικά με τους υπάρχοντες αλγόριθμους πολλαπλασιασμού πινάκων. Μέσω της μάθησης, το AlphaTensor βελτιώνεται σταδιακά με την πάροδο του χρόνου, ανακαλύπτοντας ξανά ιστορικούς αλγόριθμους πολλαπλασιασμού γρήγορης μήτρας, όπως αυτός του Strassen, ξεπερνώντας τελικά το βασίλειο της ανθρώπινης διαίσθησης και ανακαλύπτοντας αλγόριθμους πιο γρήγορα από ό,τι ήταν γνωστό στο παρελθόν.

Διερεύνηση του αντίκτυπου σε μελλοντικές έρευνες και εφαρμογές
Από μαθηματική άποψη, τα αποτελέσματά τους μπορούν να καθοδηγήσουν περαιτέρω έρευνα στη θεωρία πολυπλοκότητας, η οποία στοχεύει στον προσδιορισμό των ταχύτερων αλγορίθμων για την επίλυση υπολογιστικών προβλημάτων. Εξερευνώντας το χώρο των πιθανών αλγορίθμων με πιο αποτελεσματικό τρόπο από τις προηγούμενες προσεγγίσεις, το AlphaTensor συμβάλλει στην προώθηση της κατανόησης του πλούτου των αλγορίθμων πολλαπλασιασμού πινάκων. Η κατανόηση αυτού του χώρου μπορεί να ξεκλειδώσει νέα αποτελέσματα για να βοηθήσει στον προσδιορισμό της ασυμπτωτικής πολυπλοκότητας του πολλαπλασιασμού πινάκων, ενός από τα πιο θεμελιώδη ανοιχτά προβλήματα στην επιστήμη των υπολογιστών.

Επειδή ο πολλαπλασιασμός πινάκων είναι ένα βασικό συστατικό σε πολλές υπολογιστικές εργασίες, που εκτείνονται σε γραφικά υπολογιστών, ψηφιακές επικοινωνίες, εκπαίδευση νευρωνικών δικτύων και επιστημονικούς υπολογισμούς, οι αλγόριθμοι που ανακαλύφθηκαν από το AlphaTensor θα μπορούσαν να κάνουν τους υπολογισμούς σε αυτά τα πεδία σημαντικά πιο αποτελεσματικούς. Η ευελιξία του AlphaTensor να εξετάζει κάθε είδους στόχο θα μπορούσε επίσης να δώσει ώθηση σε νέες εφαρμογές για το σχεδιασμό αλγορίθμων που βελτιστοποιούν μετρήσεις όπως η κατανάλωση ενέργειας και η αριθμητική σταθερότητα, βοηθώντας στην αποφυγή μικρών σφαλμάτων στρογγυλοποίησης από χιονοστιβάδες καθώς λειτουργεί ένας αλγόριθμος.

Ενώ εστίασαν εδώ στο συγκεκριμένο πρόβλημα του πολλαπλασιασμού πινάκων, ελπίζουμε ότι η εργασία μας θα εμπνεύσει άλλους να χρησιμοποιήσουν την τεχνητή νοημοσύνη για να καθοδηγήσουν την αλγοριθμική ανακάλυψη για άλλες θεμελιώδεις υπολογιστικές εργασίες. Η έρευνά τους δείχνει επίσης ότι ο AlphaZero είναι ένας ισχυρός αλγόριθμος που μπορεί να επεκταθεί πολύ πέρα ​​από τον τομέα των παραδοσιακών παιχνιδιών για να βοηθήσει στην επίλυση ανοιχτών προβλημάτων στα μαθηματικά. Βασιζόμενοι στην έρευνά μας, ελπίζουν να προωθήσουν μεγαλύτερο όγκο εργασίας – εφαρμόζοντας τεχνητή νοημοσύνη για να βοηθήσουν την κοινωνία να λύσει μερικές από τις πιο σημαντικές προκλήσεις στα μαθηματικά και στις επιστήμες.

Nature – Ανακαλύπτοντας ταχύτερους αλγόριθμους πολλαπλασιασμού πινάκων με ενισχυτική μάθηση

Περίληψη
Η βελτίωση της αποτελεσματικότητας των αλγορίθμων για θεμελιώδεις υπολογισμούς μπορεί να έχει εκτεταμένο αντίκτυπο, καθώς μπορεί να επηρεάσει τη συνολική ταχύτητα μεγάλου όγκου υπολογισμών. Ο πολλαπλασιασμός μήτρας είναι μια τέτοια πρωτόγονη εργασία, που εμφανίζεται σε πολλά συστήματα—από τα νευρωνικά δίκτυα μέχρι τις επιστημονικές υπολογιστικές ρουτίνες. Η αυτόματη ανακάλυψη αλγορίθμων που χρησιμοποιούν μηχανική μάθηση προσφέρει την προοπτική να ξεπεράσουμε την ανθρώπινη διαίσθηση και να ξεπεράσουμε τους τρέχοντες καλύτερους αλγορίθμους που έχουν σχεδιαστεί από τον άνθρωπο. Ωστόσο, η αυτοματοποίηση της διαδικασίας ανακάλυψης αλγορίθμων είναι περίπλοκη, καθώς ο χώρος των πιθανών αλγορίθμων είναι τεράστιος. Εδώ αναφέρουμε μια προσέγγιση εκμάθησης βαθιάς ενίσχυσης που βασίζεται στο AlphaZero1 για την ανακάλυψη αποτελεσματικών και αποδεδειγμένα σωστών αλγορίθμων για τον πολλαπλασιασμό αυθαίρετων πινάκων. Ο πράκτορας μας, ο AlphaTensor, έχει εκπαιδευτεί να παίζει ένα παιχνίδι για έναν παίκτη όπου ο στόχος είναι η εύρεση αποσυνθέσεων τανυστών μέσα σε ένα χώρο πεπερασμένου παράγοντα. Η AlphaTensor ανακάλυψε αλγόριθμους που ξεπερνούν την πολυπλοκότητα τελευταίας τεχνολογίας για πολλά μεγέθη μήτρας. Ιδιαίτερα σημαντική είναι η περίπτωση των πινάκων 4 × 4 σε ένα πεπερασμένο πεδίο, όπου ο αλγόριθμος του AlphaTensor βελτιώνει τον αλγόριθμο δύο επιπέδων του Strassen για πρώτη φορά, εξ όσων γνωρίζουμε, από την ανακάλυψή του πριν από 50 χρόνια2. Επιδεικνύουμε περαιτέρω την ευελιξία του AlphaTensor μέσω διαφορετικών περιπτώσεων χρήσης: αλγόριθμοι με πολυπλοκότητα τελευταίας τεχνολογίας για πολλαπλασιασμό δομημένου πίνακα και βελτιωμένη πρακτική αποτελεσματικότητα βελτιστοποιώντας τον πολλαπλασιασμό μητρών για χρόνο εκτέλεσης σε συγκεκριμένο υλικό. Τα αποτελέσματά μας υπογραμμίζουν την ικανότητα του AlphaTensor να επιταχύνει τη διαδικασία αλγοριθμικής ανακάλυψης σε μια σειρά προβλημάτων και να βελτιστοποιεί για διαφορετικά κριτήρια.