Πριν από το smartphone, μια μηχανή «άκουγε» τη μουσική
Το 2002, πριν από τα smartphones, τα app stores και το streaming, εμφανίστηκε στη Βρετανία μια υπηρεσία που έμοιαζε σχεδόν μαγική. Ο χρήστης καλούσε από ένα απλό κινητό τον σύντομο αριθμό 2580, κρατούσε το τηλέφωνο κοντά στη μουσική και άφηνε τη γραμμή να «ακούσει» για λίγα δευτερόλεπτα. Ύστερα από λίγο λάμβανε SMS με τον τίτλο και τον καλλιτέχνη. Δεν υπήρχε εφαρμογή, οθόνη αφής ή γρήγορο διαδίκτυο.
Η δυσκολία ήταν τεράστια. Το σύστημα δεν άκουγε καθαρά το αρχικό τραγούδι, αλλά μια κακή τηλεφωνική εκδοχή του: με θόρυβο από τον χώρο, περιορισμένες συχνότητες, συμπίεση και ένα μικρόφωνο χαμηλής ποιότητας. Έπρεπε, παρ’ όλα αυτά, να ξεχωρίσει το σωστό κομμάτι ανάμεσα σε εκατοντάδες χιλιάδες ηχογραφήσεις. Όταν άνοιξε το App Store το 2008, το Shazam έγινε μία από τις πρώτες εφαρμογές του και η ίδια βασική ιδέα πέρασε από την τηλεφωνική κλήση στο smartphone.
Το εντυπωσιακό δεν ήταν το SMS, αλλά η αναζήτηση που κρυβόταν πίσω του. Από ένα μικρό και βρόμικο δείγμα ήχου, το σύστημα έπρεπε να κατασκευάσει μια πολύ σύντομη «ταυτότητα» και να τη βρει γρήγορα μέσα σε μια τεράστια βιβλιοθήκη. Η βασική λογική μπορεί να περιγραφεί χωρίς τεχνική ορολογία: μετατρέπουμε τον ήχο σε χάρτη, κρατάμε τα πιο σταθερά σημεία του, φτιάχνουμε μικρούς κωδικούς από τις μεταξύ τους σχέσεις και αναζητούμε σε ποιο τραγούδι οι ίδιοι κωδικοί εμφανίζονται με την ίδια χρονική διάταξη. Οι επόμενες ενότητες εξηγούν ακριβώς πώς αυτή η απλή εικόνα μετατρέπεται σε μαθηματικό αλγόριθμο.
Η βασική ιδέα: όχι ολόκληρος ο ήχος, αλλά τα σταθερά σημεία του
Ο ήχος είναι αέρας που πάλλεται: άλλοτε πιέζει λίγο περισσότερο και άλλοτε λίγο λιγότερο. Το μικρόφωνο μετατρέπει αυτή την κίνηση σε ηλεκτρικό σήμα. Ο υπολογιστής, όμως, χρειάζεται αριθμούς. Γι’ αυτό μετρά το σήμα πάρα πολλές φορές κάθε δευτερόλεπτο, σαν να τραβά χιλιάδες πολύ γρήγορες φωτογραφίες του ήχου:
x[n] = x(nTₛ), όπου Tₛ = 1/fₛ.
Το x[n] είναι απλώς η τιμή της n-οστής μέτρησης. Το fₛ λέει πόσες μετρήσεις γίνονται σε ένα δευτερόλεπτο και το Tₛ πόσο χρόνο απέχουν δύο διαδοχικές μετρήσεις. Αν, για παράδειγμα, γίνουν 8.000 μετρήσεις σε ένα δευτερόλεπτο, τότε ο υπολογιστής αποκτά 8.000 αριθμούς που περιγράφουν πώς κινήθηκε το ηχητικό κύμα. Δεν γνωρίζει ακόμη αν ακούει κιθάρα ή φωνή· διαθέτει μόνο μια πολύ γρήγορη αριθμητική καταγραφή.
Ένα ολόκληρο τραγούδι αλλάζει συνεχώς, γι’ αυτό δεν αναλύεται ως ένα ενιαίο κομμάτι. Ο αλγόριθμος το κόβει σε πάρα πολύ μικρές φέτες χρόνου, οι οποίες επικαλύπτονται λίγο ώστε να μη χαθεί κάτι στα σύνορά τους. Σε κάθε φέτα εφαρμόζει τον βραχύχρονο μετασχηματισμό Fourier, γνωστό ως STFT:
X(m,k) = Σₙ x[n+mR] w[n] exp(−j2πkn/N).
Ο τύπος μοιάζει δύσκολος, αλλά επαναλαμβάνει μία πολύ απλή δοκιμή: «Υπάρχει εδώ αυτή η συχνότητα; Και πόσο δυνατά;». Είναι σαν να έχουμε μια σειρά από μικροσκοπικά κουρδιστήρια, ένα για κάθε νότα. Όποιο κουρδιστήρι ταιριάζει με τον ήχο “κουνιέται” πολύ και δίνει μεγάλη τιμή. Όσα δεν ταιριάζουν σχεδόν αλληλοαναιρούνται. Το m δείχνει ποια χρονική φέτα εξετάζουμε, το k ποια συχνότητα δοκιμάζουμε, το w[n] σβήνει ομαλά τα άκρα κάθε φέτας και το R λέει πόσο μετακινούμαστε μέχρι την επόμενη. Έτσι, αντί για μία κυματομορφή, αποκτούμε για κάθε στιγμή μια λίστα με τις συχνότητες που ακούγονται.
Από το μέγεθος |X(m,k)|² προκύπτει το φασματογράφημα, δηλαδή μια εικόνα του ήχου. Από αριστερά προς τα δεξιά περνά ο χρόνος. Από κάτω προς τα πάνω ανεβαίνουμε από τους χαμηλούς στους υψηλούς ήχους. Τα φωτεινότερα σημεία δείχνουν πού υπάρχει περισσότερη ενέργεια. Ένα χτύπημα τυμπάνου, μια φωνή και μια κιθάρα αφήνουν διαφορετικά ίχνη, όπως διαφορετικά αντικείμενα αφήνουν διαφορετικές σκιές.
Το Shazam δεν χρειάζεται όλο το φασματογράφημα. Αναζητεί τοπικά μέγιστα, δηλαδή σημεία ισχυρότερα από το κοντινό τους περιβάλλον στον χρόνο και στη συχνότητα. Μαθηματικά, ένα σημείο επιλέγεται όταν η ενέργειά του S(m,k)=|X(m,k)|² είναι μεγαλύτερη από τις γειτονικές τιμές:
S(m,k) > S(m+Δm, k+Δk) για όλα τα γειτονικά (Δm,Δk).
Το κριτήριο δεν κρατά κάθε δυνατό ήχο. Κρατά ένα σημείο μόνο όταν είναι πιο έντονο από όσα βρίσκονται ακριβώς γύρω του. Η αναλογία με έναν νυχτερινό ουρανό είναι χρήσιμη: δεν χρειάζεται να αποθηκεύσουμε όλο το σκοτεινό φόντο, αλλά μόνο τα αστέρια που ξεχωρίζουν. Κάθε κορυφή γράφεται ως pᵢ=(tᵢ,fᵢ), δηλαδή με δύο πληροφορίες: πότε εμφανίστηκε και σε ποια συχνότητα. Το πλάτος της δεν είναι τόσο χρήσιμο, επειδή αλλάζει όταν χαμηλώνουμε την ένταση ή απομακρύνουμε το κινητό από το ηχείο. Οι θέσεις των κορυφών είναι πιο σταθερές. Το σύνολό τους λέγεται constellation map, δηλαδή «χάρτης αστερισμού».
Από δύο κορυφές σε ένα ψηφιακό αποτύπωμα
Ένα αστέρι μόνο του δεν μπορεί να αναγνωρίσει έναν αστερισμό. Με τον ίδιο τρόπο, μία κορυφή —για παράδειγμα ένας ήχος στα 900 Hz— μπορεί να υπάρχει σε χιλιάδες τραγούδια. Το Shazam παίρνει λοιπόν ένα σημείο αναφοράς pₐ=(tₐ,fₐ) και το συνδέει με μερικά γειτονικά σημεία-στόχους pᵦ=(tᵦ,fᵦ). Για κάθε ζευγάρι κρατά την πρώτη συχνότητα, τη δεύτερη συχνότητα και τον χρόνο που τις χωρίζει:
Δt = tᵦ − tₐ , h = H(fₐ, fᵦ, Δt)
Το Δt είναι η χρονική απόσταση των δύο κορυφών. Η συνάρτηση H πακετάρει τις τρεις τιμές —fₐ, fᵦ και Δt— σε έναν μικρό κωδικό h, που ονομάζεται hash. Σκεφτείτε τον σαν ετικέτα: «900 Hz, μετά 1.400 Hz, ύστερα από 0,6 δευτερόλεπτα». Αν το ίδιο σημείο του τραγουδιού ηχογραφηθεί ξανά, η ετικέτα θα είναι περίπου η ίδια, ακόμη κι αν το δείγμα ξεκινά από διαφορετικό σημείο. Ο κωδικός δεν λέει τι όργανο παίζει ή τι σημαίνει το τραγούδι. Περιγράφει μόνο ένα μικρό και χαρακτηριστικό γεωμετρικό σχήμα στον χάρτη του ήχου.
Για κάθε κωδικό, η βάση αποθηκεύει την τριάδα (h, trackID, tₐ): τον κωδικό, το τραγούδι στο οποίο ανήκει και τη χρονική θέση του μέσα σε αυτό. Η οργάνωση θυμίζει το ευρετήριο ενός βιβλίου. Αν ψάχνουμε τη λέξη «πλανήτης», δεν διαβάζουμε όλες τις σελίδες από την αρχή· το ευρετήριο μάς στέλνει κατευθείαν στις σωστές. Έτσι και το Shazam χρησιμοποιεί κάθε hash ως κλειδί και παίρνει αμέσως μια μικρή λίστα με τα τραγούδια και τις θέσεις όπου έχει εμφανιστεί. Αυτή η δομή λέγεται αντεστραμμένο ευρετήριο και είναι ο βασικός λόγος που η αναζήτηση μπορεί να γίνει τόσο γρήγορα.
Πώς γίνεται πραγματικά το matching
Η διαδικασία μπορεί να ιδωθεί ως έξι διαδοχικά βήματα:
- Μετατροπή του ηχητικού δείγματος σε φασματογράφημα.
- Επιλογή των ισχυρότερων τοπικών κορυφών.
- Σύνδεση κορυφών σε ζεύγη και παραγωγή hashes.
- Αναζήτηση κάθε hash στο αντεστραμμένο ευρετήριο.
- Υπολογισμός της χρονικής μετατόπισης για κάθε πιθανή αντιστοίχιση.
- Συσσώρευση ψήφων και αποδοχή του τραγουδιού που σχηματίζει καθαρή κορυφή.
Το ηχητικό δείγμα του χρήστη περνά ακριβώς από την ίδια διαδικασία και παράγει τη δική του μικρή συλλογή από hashes. Κάθε hash αναζητείται στο ευρετήριο και επιστρέφει πιθανά τραγούδια. Όμως ένα κοινό hash δεν αρκεί για απόφαση. Δύο τραγούδια μπορεί τυχαία να έχουν ένα παρόμοιο ζευγάρι κορυφών, όπως δύο διαφορετικά βιβλία μπορεί να περιέχουν την ίδια λέξη. Χρειαζόμαστε πολλές συμπτώσεις και, κυρίως, πρέπει να βρίσκονται στη σωστή χρονική σειρά.
Αν ένα hash εμφανίζεται στο δείγμα στον χρόνο t_q και στο υποψήφιο τραγούδι στον χρόνο t_d, υπολογίζεται η μετατόπιση:
δ = t_d − t_q
Η ποσότητα δ λέει πόσο πρέπει να μετακινήσουμε το μικρό δείγμα προς τα δεξιά ώστε να πέσει πάνω στο πλήρες τραγούδι. Παράδειγμα: αν ένα χαρακτηριστικό βρίσκεται στο 1ο δευτερόλεπτο του δείγματος και στο 41ο δευτερόλεπτο του τραγουδιού, τότε δ=40 s. Αν ένα δεύτερο βρίσκεται στα 2 s και στα 42 s, δ=40 s ξανά. Όταν πολλές ανεξάρτητες αντιστοιχίσεις δίνουν την ίδια διαφορά, είναι σαν πολλά κομμάτια ενός διάφανου σχεδίου να κουμπώνουν ταυτόχρονα πάνω στο πρωτότυπο. Αυτή η κοινή μετατόπιση είναι πολύ ισχυρότερη από μια απλή ομοιότητα συχνοτήτων.
Πρακτικά, το σύστημα σχηματίζει ένα ιστόγραμμα ψήφων για κάθε υποψήφιο τραγούδι:
V(s,δ) = Σᵢ 1[sᵢ=s και δᵢ ανήκει στο ίδιο χρονικό bin].
Ο τύπος είναι απλώς μια καταμέτρηση ψήφων. Το σύμβολο 1[·] λειτουργεί σαν κουμπί: δίνει 1 όταν μια αντιστοίχιση ανήκει στο τραγούδι s και στην ίδια μικρή περιοχή μετατόπισης δ, διαφορετικά δίνει 0. Το «χρονικό bin» είναι ένα μικρό κουτάκι τιμών, για παράδειγμα από 39,95 έως 40,05 s, ώστε οι μικρές αποκλίσεις της ηχογράφησης να θεωρούνται ίδιες. Το V(s,δ) είναι το πλήθος των ψήφων μέσα σε κάθε κουτάκι. Το σωστό τραγούδι συνήθως δημιουργεί έναν ψηλό σωρό ψήφων σε μία θέση, ενώ οι τυχαίες συμπτώσεις σκορπίζονται.
Στο τέλος, το σύστημα συγκρίνει όλους αυτούς τους σωρούς. Επιλέγει το τραγούδι s και τη μετατόπιση δ που συγκέντρωσαν τις περισσότερες συνεπείς ψήφους:
(s*,δ*) = arg max₍s,δ₎ V(s,δ).
Με απλά λόγια, το Shazam δεν ρωτά μόνο «βρήκα τα ίδια αστεράκια;». Ρωτά «βρήκα πολλά ίδια ζευγάρια αστεριών και κουμπώνουν όλα όταν μετακινήσω το δείγμα κατά τον ίδιο χρόνο;». Η απαίτηση κοινής χρονικής μετατόπισης απορρίπτει τις περισσότερες τυχαίες συμπτώσεις και αποτελεί την καρδιά του matching.
Ένα μικρό νοητικό παράδειγμα
Ας πάρουμε ένα απλό παράδειγμα. Τέσσερα hashes εμφανίζονται στο δείγμα στα 1, 2, 3 και 4 s. Στο τραγούδι Α εμφανίζονται στα 41, 42, 43 και 44 s. Οι τέσσερις αφαιρέσεις δίνουν 40 s, άρα τέσσερις ψήφοι πέφτουν στο ίδιο κουτάκι. Στο τραγούδι Β ίσως βρεθούν οι ίδιοι κωδικοί στα 12, 57, 20 και 91 s. Οι διαφορές είναι διαφορετικές και οι ψήφοι σκορπίζουν. Το Α δημιουργεί καθαρή κορυφή· το Β μοιάζει με τυχαίο θόρυβο. Αυτός είναι ολόκληρος ο μηχανισμός αναγνώρισης σε μικρογραφία.
Γιατί αντέχει στον πραγματικό κόσμο
Η αντοχή στον θόρυβο δεν οφείλεται σε ένα μοναδικό τέχνασμα, αλλά σε πολλές απλές επιλογές που συνεργάζονται. Πρώτον, κρατιούνται μόνο κορυφές που ξεχωρίζουν από τη γειτονιά τους, άρα ένα μέρος του θορύβου αγνοείται. Δεύτερον, χρησιμοποιούνται χρόνος και συχνότητα και όχι η ακριβής ένταση, η οποία αλλάζει πολύ εύκολα. Τρίτον, παράγονται πολλά hashes: ακόμη κι αν ο θόρυβος καταστρέψει μερικά, αρκετά μπορούν να επιβιώσουν. Τέταρτον, η κοινή χρονική μετατόπιση απαιτεί από τις σωστές αντιστοιχίσεις να συμφωνούν μεταξύ τους. Τέλος, το ευρετήριο επιτρέπει άμεση αναζήτηση χωρίς σύγκριση με κάθε τραγούδι ξεχωριστά.
Το κλασικό audio fingerprinting αναγνωρίζει την ίδια ηχογράφηση ή μια αρκετά πιστή αναπαραγωγή της. Δεν «καταλαβαίνει» τη μελωδία όπως ένας άνθρωπος. Αν τραγουδήσουμε ή σφυρίξουμε ένα κομμάτι, αλλάζουν οι ακριβείς συχνότητες, ο ρυθμός, η ενορχήστρωση και οι χρονικές σχέσεις· τα hashes δεν συμπίπτουν. Η αναγνώριση διασκευών, μελωδικής ομοιότητας ή τραγουδιού από humming είναι συγγενικά, αλλά διαφορετικά προβλήματα, στα οποία σήμερα χρησιμοποιούνται συχνά τεχνικές μηχανικής μάθησης.
Από το 2580 στο σημερινό οικοσύστημα
Η εξέλιξη ήταν κυρίως εξέλιξη του περιβάλλοντος γύρω από τον αλγόριθμο. Το 2002 η αναγνώριση περνούσε από τηλεφωνική κλήση και SMS. Το 2008 μεταφέρθηκε στην εφαρμογή του iPhone. Σήμερα συνδέεται με streaming, ιστορικό αναζητήσεων και λειτουργίες του λειτουργικού συστήματος. Ο κατάλογος και η υπολογιστική υποδομή μεγάλωσαν θεαματικά, αλλά η ιδέα του συμπαγούς ακουστικού αποτυπώματος παραμένει το σημείο αναφοράς.
Οι ακριβείς σημερινές εσωτερικές υλοποιήσεις είναι ιδιοκτησιακές. Δεν υπάρχει ασφαλής τεκμηρίωση ότι ο βασικός μηχανισμός έχει αντικατασταθεί από ένα νευρωνικό δίκτυο. Αυτό που μπορούμε να πούμε είναι ότι η κλασική ιδέα του ακουστικού αποτυπώματος παραμένει θεμελιώδης, ενώ το σύστημα γύρω της απέκτησε πολύ μεγαλύτερη βάση, ισχύ, ταχύτητα και ενσωμάτωση.
Η διαφορά από πολλά σημερινά συστήματα τεχνητής νοημοσύνης είναι ουσιαστική. Ένα νευρωνικό μοντέλο μαθαίνει μόνο του πολύπλοκες αναπαραστάσεις από μεγάλο αριθμό παραδειγμάτων και μπορεί να αναγνωρίζει ευρύτερες ομοιότητες. Το κλασικό Shazam, αντίθετα, εκτελεί μια προσεκτικά σχεδιασμένη ακολουθία μαθηματικών βημάτων για ένα στενό πρόβλημα: να βρει την ίδια ηχογράφηση. Δεν επιχειρεί να ερμηνεύσει τη μουσική· μετατρέπει ένα ακατάστατο φυσικό σήμα σε ένα μικρό, σταθερό και αναζητήσιμο αποτύπωμα. Η εντυπωσιακή του αποτελεσματικότητα προέρχεται από αυτήν ακριβώς την εξειδίκευση.
Η κομψότητα της αφαίρεσης
Το Shazam πέτυχε επειδή πέταξε σχεδόν όλη την πληροφορία του ήχου και κράτησε μόνο ό,τι χρειαζόταν για την ταυτοποίηση. Ένα τραγούδι έγινε λίγα σταθερά σημεία. Τα σημεία έγιναν σχέσεις. Οι σχέσεις έγιναν hashes. Και τα hashes, όταν ευθυγραμμίστηκαν στον χρόνο, έδωσαν ένα όνομα.
Αυτό είναι ένα από τα βαθύτερα μαθήματα της υπολογιστικής επιστήμης: η λύση ενός δύσκολου προβλήματος δεν απαιτεί πάντοτε περισσότερα δεδομένα ή ένα μεγαλύτερο μοντέλο. Μερικές φορές απαιτεί να βρούμε τη μικρότερη αναπαράσταση που διατηρεί ακριβώς τη δομή που μας ενδιαφέρει.
Change is the only Constant
