Παρουσιάζοντας ένα από τα καλύτερα χάσματα στη μηχανική μάθηση: το τέχνασμα Hashing

Το 2018 χαιρετίστηκε από διάφορα καταστήματα ως το έτος κατά το οποίο το spam θα αρχίσει να πεθαίνει επειδή οι αλγόριθμοι μηχανικής μάθησης θα γίνουν σχεδόν τέλειοι στο να υπολογίσουμε τι είναι πραγματικό ταχυδρομείο και τι όχι. Δεν είμαι πεπεισμένος ότι θα συμβεί ποτέ (η πρόοδος στη μηχανική μάθηση κόπηκε και στους δύο τρόπους), αλλά θα ήθελα να μοιραστώ κάποιες γενικές σκέψεις σχετικά με το πώς κατασκευάζονται οι απλοί ταξινομητές spam με βάση το ML και πώς να ξεπεραστεί ένα σημαντικό πρόβλημα, χρησιμοποιώντας ένα από τα καλύτερα hacks στη μηχανική μάθηση: το τέχνασμα κατακερματισμού. Είναι επίσης χρήσιμη η ανίχνευση ανεπιθύμητης αλληλογραφίας.

Δημιουργία ενός απλού ταξινομητή spam

Για τις εργασίες ταξινόμησης εγγράφων, συμπεριλαμβανομένης της κατάταξης με ανεπιθύμητα μηνύματα (spam classification), αρχίζει κανείς να κατασκευάζει αυτό που είναι γνωστό ως αναπαράσταση τσαγιού (BOW). Με δεδομένο ένα σύνολο γνωστών ηλεκτρονικών μηνυμάτων ανεπιθύμητης αλληλογραφίας και ανεπιθύμητης αλληλογραφίας, κάθε μοναδική λέξη προστίθεται σε ένα λεξιλόγιο και έχει εκχωρηθεί ένα μοναδικό ευρετήριο, συνήθως ξεκινώντας από το 0. Ας υποθέσουμε, για λόγους συντομίας, ότι έχουμε ένα σύνολο δύο παραδειγμάτων σύντομων κειμένων, το οποίο είναι spam και ένα άλλο που είναι νόμιμο:

κάνω δέκα χιλιάδες δολάρια την εβδομάδα μόνο σερφάρει στο διαδίκτυο! (ανεπιθυμητη αλληλογραφια)
Είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; (όχι spam)

Εάν σαρώσουμε το σύνολο δεδομένων και αρχίσουμε να φτιάχνουμε το λεξιλόγιό μας, ίσως καταλήξουμε σε κάτι τέτοιο:

i: 0
κάνετε: 1
δέκα: 2
χιλιάδες: 3
δολάρια: 4
ανά: 5
εβδομάδα: 6
μόλις: 7
surfing: 8
το: 9
web: 10
είναι: 11
εσείς: 12
δωρεάν: 13
για: 14
α: 15
συνάντηση: 16
νωρίς: 17
επόμενο: 18

Υπάρχουν συνολικά 19 μοναδικές λέξεις και κάθε ένα έχει ένα μοναδικό ευρετήριο (σημειώστε ότι η εβδομάδα λέξεων εμφανίζεται και στα δύο παραδείγματα). Το επόμενο βήμα είναι να δημιουργήσουμε διανύσματα χαρακτηριστικών για το μοντέλο μηχανικής μάθησης. Ξεκινάμε δημιουργώντας ένα διάνυσμα μηδενικής στήλης για κάθε παράδειγμα, με τον ίδιο αριθμό στοιχείων όπως υπάρχουν λέξεις στο λεξιλόγιό μας (19):

κάνω δέκα χιλιάδες δολάρια την εβδομάδα μόνο σερφάρει στο διαδίκτυο! (ανεπιθυμητη αλληλογραφια)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
Είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; (όχι spam)
-> [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Στη συνέχεια, για κάθε λέξη σε κάθε παράδειγμα, εκτελούμε μια αναζήτηση λεξιλογίου για να πάρουμε το ευρετήριο και να αυξήσουμε την τιμή σε αυτόν τον δείκτη κατά ένα:

κάνω δέκα χιλιάδες δολάρια την εβδομάδα μόνο σερφάρει στο διαδίκτυο! (ανεπιθυμητη αλληλογραφια)
-> [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
Είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; (όχι spam)
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Οι διανυσματικοί χαρακτήρες που προκύπτουν είναι αναπαραστάσεις σακουλών-λέξεων. Οι αναφορές BOW τυπικά πετάνε πληροφορίες σχετικά με τη στίξη και τη σειρά λέξεων, αλλά για πολλά προβλήματα, αυτό δεν είναι ένα θέμα. Οι πιο εξελιγμένες αναπαραστάσεις BOW χρησιμοποιούν τα βάρη TF-IDF και / ή τα n-grams αντί για τις πρώτες λέξεις, αλλά η βασική ιδέα είναι η ίδια.

Αφού έχουμε τους διανύσματα χαρακτηριστικών BOW, μπορούμε να εκπαιδεύσουμε έναν δυαδικό ταξινομητή για να δημιουργήσουμε ένα φίλτρο ανεπιθύμητης αλληλογραφίας. Υπάρχουν πολλές επιλογές σχετικά με αλγορίθμους μάθησης, αλλά οι πιο συνηθισμένοι ύποπτοι είναι Naïve Bayes, τυχαία δάση, διοικητική παλινδρόμηση και, όλο και περισσότερο, νευρωνικά δίκτυα. Δεδομένου ενός εκπαιδευμένου μοντέλου, μπορούμε να χρησιμοποιήσουμε το λεξιλόγιο για να τροφοδοτήσουμε ένα νέο μήνυμα ηλεκτρονικού ταχυδρομείου ως φορέα BOW και να προβλέψουμε αν το παράδειγμα είναι spam ή όχι. Σημειώστε ότι για συμπεράσματα σε πραγματικό χρόνο, πρέπει να διατηρήσουμε το λεξιλόγιο στη μνήμη RAM να είναι όσο το δυνατόν γρηγορότερα.

Το ζήτημα: καταστρατήγηση φίλτρου

Οι spammers είναι λαϊκοί. Ένας δημοφιλής τρόπος για να βεβαιωθείτε ότι το spam δεν παίρνει φιλτραρισμένο είναι να αναμειγνύεται με λέξεις όχι στο λεξιλόγιο που χρησιμοποιείται για να μάθει τον ταξινομητή. Εξετάστε, για παράδειγμα, την ακόλουθη, ελαφρώς κατασκευασμένη πρόταση:

Ίσως να είστε ελεύθεροι για surf1ing τη συνάντηση webz στις αρχές της επόμενης εβδομάδας

Είναι σαφές ότι αυτό δεν είναι κάτι που κάποιος θα θεωρούσε νόμιμο μήνυμα ηλεκτρονικού ταχυδρομείου. Αλλά τι συμβαίνει εάν χρησιμοποιήσουμε το λεξιλόγιό μας για να χτίσουμε ένα διάνυσμα BOW για αυτό το παράδειγμα; Οι πρώτες οκτώ λέξεις δεν υπάρχουν καθόλου στο λεξιλόγιό μας και δεν θα το κάνουν. Τα υπόλοιπα είναι, οδηγώντας στον ακόλουθο φορέα:

Ίσως να είστε ελεύθεροι για surf1ing τη συνάντηση webz στις αρχές της επόμενης εβδομάδας
-> [0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1]

Αυτό το διάνυσμα είναι το ίδιο με αυτό για το νόμιμο παράδειγμα είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; . Οποιοσδήποτε ταξινομητής εκπαιδευτεί στα παραδείγματα μας θα πιστεύει πιθανώς ότι αυτό το spam είναι νόμιμο. Αυτό είναι ένα σημαντικό πρόβλημα, και όχι τόσο εύκολο να το λύσουμε όσο θα μπορούσαμε να σκεφτούμε. Θα μπορούσαμε να προσθέσουμε τις νέες λέξεις στο λεξιλόγιό μας, αλλά αυτό θα σήμαινε ότι το μέγεθος των διανυσματικών μεγεθών θα αλλάξει, όπως και το ίδιο το λεξιλόγιο. Τα μοντέλα μηχανικής μάθησης τυπικά μαθαίνουν σε παραδείγματα εκπαίδευσης σταθερού μεγέθους, οπότε θα χρειαστεί να επανεκπαιδεύσουμε το μοντέλο μας από την αρχή. Αυτό απαιτεί χρόνο και ενώ το κάνουμε αυτό, ο παλιός ταξινομητής θα συνεχίσει να δέχεται τα ανεπιθύμητα μηνύματα. Χρειαζόμαστε μια λύση που α) μπορεί να χειριστεί λέξεις εκτός λεξιλογίου, β) δεν απαιτεί από εμάς να επανεκπαιδεύουμε τα μοντέλα μας από το μηδέν κάθε φορά που συναντάμε μια νέα λέξη ή ορθογραφικά λάθη και γ) είναι όσο το δυνατόν ακριβέστερη. Αν μπορούσαμε να ξεφύγουμε χωρίς να κρατάμε ένα τεράστιο λεξιλόγιο στη μνήμη RAM, ακόμα καλύτερα.

Παρουσιάζοντας το τέχνασμα κατακερματισμού

Οι λειτουργίες Hash είναι θεμελιώδεις για την επιστήμη των υπολογιστών Υπάρχουν πολλοί διαφορετικοί τύποι λειτουργιών κατακερματισμού, αλλά όλοι κάνουν το ίδιο πράγμα: χάρτης δεδομένων αυθαίρετων μεγεθών σε δεδομένα σταθερού μεγέθους. Συνήθως, φτύνουν έναν αριθμό (γνωστός ως hash):

"John Doe" -> λειτουργία κατακερματισμού -> 34
"Jane Doe" -> λειτουργία κατακερματισμού -> 48

Η λογική με την οποία υπολογίζεται ένας κατακερματισμός εξαρτάται από την ίδια τη συνάρτηση κατακερματισμού, αλλά όλες οι λειτουργίες κατακερματισμού έχουν τα ίδια κοινά χαρακτηριστικά:

  • Αν τροφοδοτούμε την ίδια είσοδο σε μια λειτουργία κατακερματισμού, θα δίνει πάντα την ίδια έξοδο.
  • Η επιλογή της συνάρτησης κατακερματισμού καθορίζει το εύρος των πιθανών εξόδων, δηλαδή το εύρος είναι πάντα σταθερό (π.χ. αριθμοί από 0 έως 1024).
  • Οι λειτουργίες Hash είναι μονόδρομες: με ένα hash, δεν μπορούμε να κάνουμε αντίστροφη αναζήτηση για να καθορίσουμε ποια ήταν η είσοδος.
  • Οι λειτουργίες Hash μπορεί να εκπέμπουν την ίδια τιμή για διαφορετικές εισόδους (σύγκρουση).

Οι λειτουργίες Hash είναι απίστευτα χρήσιμες σχεδόν σε κάθε τομέα της επιστήμης των υπολογιστών, αλλά πώς μπορούν να χρησιμοποιηθούν για να διορθώσουν το ζήτημα εκτός λεξιλογίου του ταξινομητή spam μας; Η απάντηση δεν είναι αμέσως προφανής, αλλά το πρώτο βήμα είναι να απαλλαγούμε από το λεξιλόγιό μας εντελώς. Αντ 'αυτού, κατά την κατασκευή των παραστάσεων BOW, θα ξεκινήσουμε κάνοντας ένα διάνυσμα μηδενικής στήλης με ένα τεράστιο αριθμό (για παράδειγμα, 2².8) στοιχείων για κάθε ένα από τα παραδείγματα εκπαίδευσης:

κάνω δέκα χιλιάδες δολάρια την εβδομάδα μόνο σερφάρει στο διαδίκτυο! (ανεπιθυμητη αλληλογραφια)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 στοιχεία)
Είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; (όχι spam)
-> [0 0 0 0 ... 0 0 0 0] (2 ^ 28 στοιχεία)

Στη συνέχεια, θα επιλέξουμε μια συνάρτηση κατακερματισμού f που τρώει χορδές και εξάγει τιμές στην περιοχή [0, 2²,8). Με άλλα λόγια, διασφαλίζουμε ότι η συνάρτηση κατακερματισμού μας δεν θα αντιμετωπίσει ποτέ ένα ευρετήριο εκτός των διαστάσεων των διανυσμάτων μας.

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

κάνω δέκα χιλιάδες δολάρια την εβδομάδα μόνο σερφάρει στο διαδίκτυο! (ανεπιθυμητη αλληλογραφια)
-> [0 ... 0 1 1 1 0 1 1 0 ... 0 1 1 1 1 0 1 1 0] (2 ^ 28 στοιχεία)
Είστε ελεύθεροι για μια συνάντηση στις αρχές της επόμενης εβδομάδας; (όχι spam)
-> [0 1 0 1 0 ... 0 1 0 ... 0 1 0 ... 0 1 1 0 1 1 0 1] (2 ^ 28 στοιχεία)

Αυτή η διαδικασία είναι γνωστή ως το τέχνασμα κατακερματισμού.

Τώρα έχουμε την παράσταση BOW και μπορούμε να εκπαιδεύσουμε έναν ταξινομητή στα δεδομένα όπως πριν. Απλό, όχι; Έχουμε ξεχάσει τη χρήση ενός ξεχωριστού λεξιλογίου, πράγμα που σημαίνει ότι δεν χρειάζεται να κρατήσουμε μια δυνητικά μεγάλη λίστα λέξεων στη μνήμη RAM. Αλλά αυτό είναι απλώς μια ωραία παρενέργεια - το πραγματικό ζήτημα που θέλουμε να αντιμετωπίσουμε είναι η καταστρατήγηση του φίλτρου χρησιμοποιώντας λέξεις εκτός λεξιλογίου. Πως βοηθάει, λοιπόν, το τέχνασμα κατακερματισμού;

Ας υποθέσουμε ότι έχουμε έναν ταξινομητή ανεπιθύμητων μηνυμάτων που εκπαιδεύεται σε μια δέσμη των διανυσματικών διανυσματικών χαρακτηριστικών 2².8 BOW. Λαμβάνοντας ένα νέο κομμάτι αλληλογραφίας, το κάνουμε όπως πριν, αρχικοποιώντας ένα διάνυσμα 2 2 8 και περνώντας κάθε λέξη μέσω της συνάρτησης hash. Σε αντίθεση με το παρελθόν, κάθε λέξη καταλήγει αυξάνοντας κάποια αξία χαρακτηριστικών. Δεδομένου του διάνυσμα BOW, κάθε λέξη - ακόμα και νέες - λαμβάνεται υπόψη κατά το χρόνο πρόβλεψης. Νέες λέξεις εξακολουθούν να επιδεινώνουν την ακρίβεια του ταξινομητή μας, αλλά δεν είναι πλέον δυνατό να καταστραφεί εξ ολοκλήρου το φίλτρο ανεπιθύμητης αλληλογραφίας, δημιουργώντας νέες λέξεις. Δεδομένου ότι οι φορείς BOW διατηρούν το ίδιο μέγεθος, μπορούμε να εφαρμόσουμε σταδιακά το πρότυπό μας με νέα παραδείγματα ανεπιθύμητης αλληλογραφίας / spam, χωρίς να επαναπροσδιορίσουμε το όλο θέμα από την αρχή. Είναι μια μορφή ηλεκτρονικής μάθησης: όταν ένας χρήστης σηματοδοτεί ένα μήνυμα ηλεκτρονικού ταχυδρομείου ως ανεπιθύμητο, το μοντέλο μπορεί να μάθει από αυτό προοδευτικά, χωρίς να ξαναρχίσει ολόκληρη τη διαδικασία. Για μια πρακτική εφαρμογή όπως το φιλτράρισμα ανεπιθύμητων μηνυμάτων, αυτό είναι ένα σαφές όφελος από το hashing χαρακτηριστικών: μπορούμε να αντιδράσουμε γρήγορα στις επιθέσεις κάνοντας μάθηση μόλις εισέλθουν νέα παραδείγματα spam / μη spam.

Αλλά τι γίνεται με τις συγκρούσεις, ακούω να ρωτάς; Δεν είναι δυνατόν κάποια σκόπιμη ορθογραφία να καταλήξει να αυξάνει τον ίδιο ευρετήριο με κάποια νόμιμη λέξη καθώς περνάει από τη λειτουργία κατακερματισμού; Ναι, μπορεί να συμβεί, αλλά εάν επιλέξετε το μέγεθος του φορέα σας (το κάνετε όσο το δυνατόν μεγαλύτερο) και η συνάρτηση κατακερματισμού προσεκτικά, οι πιθανότητες αυτού του συμβάντος είναι αμελητέες και ακόμα και αν αυτό συμβαίνει, συνήθως δεν επηρεάζει την εκμάθηση ) τόσο πολύ. Η τεκμηρίωση για τυποποιημένες λειτουργίες κατακερματισμού συνήθως περιλαμβάνει πιθανότητες σύγκρουσης, οπότε βεβαιωθείτε ότι θα δείτε αυτούς όταν κάνετε τη δική σας λύση εξαπατήσεως.

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

Κάποιες τελικές σκέψεις

Το τέχνασμα κατακερματισμού είναι ένα από αυτά τα κομψά κόλπα στη μηχανική μάθηση που δεν έχει σχεδόν την ίδια αγάπη που αξίζει. Το μόνο πραγματικό μειονέκτημα είναι το γεγονός ότι οι αντίστροφες αναζητήσεις (output to input) δεν είναι δυνατές, αλλά για πολλά προβλήματα, αυτό δεν είναι απαίτηση. Με πιο γενικό τρόπο, το τέχνασμα κατακερματισμού σας επιτρέπει να χρησιμοποιείτε διανύσματα μεταβλητού μεγέθους με τυπικούς αλγορίθμους μάθησης (παλινδρόμηση, τυχαία δάση, νευρωνικά δίκτυα τροφοδοσίας, SVM, συντεταγμένη μήτρας κλπ.). Αυτό θα πρέπει να είναι αρκετό για να κάνει τους περισσότερους επαγγελματίες της εκμάθησης μηχανών τουλάχιστον ενθουσιασμένοι.