Μόλις ανακαλύφθηκε ένας νέος τρόπος να μετράμε
Η επιστήμη είναι αυτή που επιτρέπει την καινοτομία και τη βελτίωση της ζωής μας. Ελάχιστοι όμως θα περίμεναν ότι θα μπορούσαμε να βελτιώσουμε μια απλή πτυχή της καθημερινότητάς μας, όπως το μέτρημα. Και όμως, μια ομάδα επιστημόνων το έκαναν. Βρήκαν δηλαδή έναν τρόπο να λύσουν ένα πρόβλημα δεκαετιών που θέτει το απλό, εκ πρώτης όψεως, ερώτημα. Πόσα διαφορετικά πράγματα υπάρχουν μπροστά μας.
Ο Ευκλείδης στέλνει τις πρώτες εντυπωσιακές εικόνες του σκοτεινού σύμπαντος που καθηλώνουν!
Οι υπολογιστές είναι πολύ έξυπνοι, ωστόσο έχουν πολλά προβλήματα. Το πιο χαρακτηριστικό παράδειγμα, η πρόσφατη έκρηξη των AI chatbots, είναι απίστευτα έξυπνα, σου λύνουν πλήθος προβλημάτων και ερωτήσεων, αλλά πολλές φορές προτρέπουν σε άκρως επικίνδυνα πράγματα.
Και κάποιες φορές είναι τα πράγματα που μοιάζουν ιδιαίτερα απλά στον άνθρωπο που προκαλούν τη μεγαλύτερη όμως αναστάτωση. Για παράδειγμα, το μέτρημα, ή καλύτερα το μέτρημα των διακριτών αντικειμένων. Για εμάς του ανθρώπους είναι απλό. Κοιτάζουμε τη συλλογή των αντικειμένων και ο εγκέφαλός μας αυτόματα τα τοποθετεί σε ομάδες. Απίστευτα απλό.
Για τους υπολογιστές όμως αποτελεί ένα θεμελιώδες πρόβλημα, δεκαετιών. Και είναι κάτι που πρέπει να απαντηθεί. καθώς η εφαρμογή του στον κόσμο μας έχει πολλές πρακτικές χρήσεις, από την ανάλυση του traffic των δικτύων, για παράδειγμα σκέψου το Facebook ή το Twitter για την εξακρίβωση των πόσων ανθρώπων έχουν συνδεθεί σε κάποια χρονική στιγμή, ως και την ανίχνευση απάτης, ανάλυση κειμένου κ.α.
Πως λειτουργεί η νέα μέθοδος
Η νέα μέθοδος, που έλαβε την ονομασία αλγόριθμος CVM, μειώνει δραστικά τις απαιτήσεις μνήμης κάτι πολύ σημαντικό στη σύγχρονη εποχή των big data. Και αυτό το κάνει χρησιμοποιώντας ένα trick της θεωρίας των πιθανοτήτων. Για να κατανοήσουμε πως δουλεύει καλό είναι να διαβάσουμε το παρακάτω παράδειγμα που ακολουθεί καθώς και ένα πρόσφατο άρθρο του Quanta Magazine.
Φαντάσου ότι μετράς των αριθμό των μοναδικών λέξεων στο θεατρικό έργο Hamlet του Shakespeare, αλλά έχεις αρκετή μνήμη για να αποθηκεύσεις μόνο 100 λέξεις την φορά. Αρχικά, όπως εξηγεί το lflscience κάνεις το προφανές. Καταγράφεις τις πρώτες 100 μοναδικές λέξεις με τις οποίες ήρθες σε επαφή. Ο χώρος όμως τελειώνει, επομένως παίρνεις ένα νόμισμα και το ρίχνεις για κάθε λέξη. Κορώνα, μένει, γράμματα την ξεχνάς.
Στο τέλος της εν λόγω διαδικασίας θα έχεις περίπου 50 μοναδικές λέξεις στη λίστα. Ξεκινάς ξανά τη διαδικασία από πριν, αλλά αυτή τη φορά, αν έλθεις αντιμέτωπος μια λέξη που βρίσκεται ήδη στη λίστα, γυρνάς το νόμισμα πάλι για να δεις αν θα την διαγράψεις ή όχι. Μόλις φθάσεις τις 100 λέξεις, ανατρέχεις ξανά τη λίστα, γυρνώντας το νόμισμα για κάθε λέξη και τη διαγράφεις ή την κρατάς.
Στον δεύτερο γύρο, τα πράγματα γίνονται λίγο πιο περίπλοκα. Αντί για μια κορώνα για να κρατήσεις τη λέξη στη λίστα, θα χρειαστείς δυο στη σειρά, σε διαφορετική περίπτωση τη σβήνεις. Στον τρίτο γύρο θα χρειαστείς τρεις κορώνες στη σειρά για να μείνει, στον τέταρτο γύρο τέσσερις κορώνες στη σειρά μέχρι να φθάσεις στο τέλος του θεατρικού έργου.
Αν ανατρέξεις δηλαδή το κείμενο με αυτόν τον τρόπο, έχεις διασφαλίσει ότι κάθε λέξη στη λίστα σου έχει την ίδια πιθανότητα να βρίσκεται εκεί, 1/2k
όπου κ είναι ο αριθμός των φορών που ανατρέχεις στη λίστα. Επομένως, αν θεωρήσουμε ότι χρειάστηκαν έξι γύροι για να φθάσεις στο τέλος του έργο, μένεις με μια λίστα 61 διακριτών λέξεων. Στη συνέχεια πολλαπλασιάζεις το 61 x 26
για να πάρεις ένα κατά προσέγγιση αριθμό των λέξεων. Το αποτέλεσμα της πράξης είναι 3.904, που ο αριθμός είναι πολύ κοντά στον πραγματικό αριθμό λέξεων, που είναι 3.967 του θεατρικού έργου. Και ναι κάθισαν και τις μέτρησαν.
Οι επιστήμονες σχολίασαν ότι είναι ένας εξαιρετικός αλγόριθμος και είναι περίεργο που δεν ανακαλύφθηκε νωρίτερα.
Η αναλυτική έρευνα είναι ανεβασμένη στο arxiv του Πανεπιστημίου Cornell.
