Τα περισσότερα προβλήματα στην επιστήμη των υπολογιστών μπορούν να μειωθούν σε κάποιο μέρος σε ένα από μερικές εκατοντάδες περίπου κλασικά προβλήματα. Υπάρχουν οι Φιλόσοφοι της Τραπεζαρίας, το Κινέζικο Εστιατόριο, ο Ταξιδεύοντας Πωλητής, οι Βυζαντινοί Στρατηγοί και ούτω καθεξής. Την περασμένη εβδομάδα συνάντησα ένα διασκεδαστικό που δεν είχα δει εδώ και καιρό - το Σταθερό Πρόβλημα του Γάμου - οπότε σκέφτηκα να γράψω λίγα γι' αυτό.

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

Ρύθμιση προβλήματος: Φανταστείτε ότι είστε πολυάσχολος δικηγόρος..

Στέλνεις στους ανθρώπους συμβόλαια 40 σελίδων όλη μέρα. Συνήθως στέλνουν αυτά τα συμβόλαια πίσω υπογεγραμμένα και αμετάβλητα, αλλά μερικές φορές κάποιος διαγράφει μια γραμμή ή προσθέτει μια σημείωση περιθωρίου πριν υπογράψει. Το συμβόλαιο που υπέγραψαν είναι πλέον διαφορετικό από αυτό που τους στείλατε! Για να το εντοπίσετε, έχετε κολλήσει να ξαναδιαβάζετε το 100% των εισερχόμενων συμβολαίων για να δείτε ποιες έχουν αλλαγές και ποιες όχι.

Σας αρέσει το ποσοστό χρέωσής σας, αλλά δεν θέλετε να περάσετε έτσι τον χρόνο σας. Έτσι, γράφετε ένα πρόγραμμα υπολογιστή για να αναλύετε αυτόματα ζεύγη σελίδων, <outgoing_page, incoming_page>, για να εντοπίσετε τυχόν υπογραφές και σημάδια στυλό που έχουν γίνει στην εισερχόμενη σελίδα.

Εκτελείτε το πρόγραμμα. Λειτουργεί υπέροχα! Αλλά αποτυγχάνει και καταστροφικά μερικές φορές, με παράξενα αποτελέσματα. Επιθεωρώντας αυτά τα σφάλματα, συνειδητοποιείτε ότι ορισμένες από αυτές τις συμβάσεις δεν έχουν απλώς επισημανθεί με στυλό, αλλά έχουν επίσης ανακατευτεί και έχουν χαθεί σελίδες. Τα σφάλματα προκύπτουν από τον αλγόριθμό σας που προσπαθεί να συγκρίνει το outgoing_page 2 με κάποια κακώς αντιστοιχισμένα incoming_page 4.

Τρόποι με τους οποίους ένα έγγραφο μπορεί να είναι "εκτός λειτουργίας"

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

  • A, η απερχόμενη σύμβαση, και
  • B, το εισερχόμενο συμβόλαιο

Το έγγραφο A έχει σελίδες a_1, a_2, ... a_n και το έγγραφο B έχει σελίδες b_1, b_2, ... b_m. Γνωρίζουμε ότι τα A και B είναι τα ίδια έγγραφα, αλλά το b_1 .. b_m αποκλίνει από το A με μερικούς άβολους τρόπους:

  • Οι σελίδες έχουν αφαιρεθεί
  • Προστέθηκαν σελίδες
  • Οι σελίδες έχουν αναδιαταχθεί

Αυτό που θα θέλαμε να βρούμε είναι μια αντιστοιχία μεταξύ A και B. Ταίριασμα είναι ένα σύνολο ζευγαρωμάτων μεταξύ των στοιχείων A και B, όπως αυτό: [ <a_1,b_1>, <a_2,b_2> … <a_n,b_n> ] . Συγκεκριμένα, θέλουμε το ματς που έχει ως αποτέλεσμα <a_i, b_j> ζευγάρια που μοιάζουν περισσότερο μεταξύ τους.

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

Σταθερή αντιστοίχιση γάμου

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

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

No element in a match will have a better viable option.

Αυτή είναι η πρόταση που εκφράζεται ως τεστ που μπορείτε να εφαρμόσετε σε κάποια αντιστοίχιση (a, b) για να δείτε αν είναι σταθερή:

for all mates (a,b):
  if a would rather be with c than b:
    if c would rather be with a than c's current match:
      (a,b) is unstable! (a,c) deserve each other!
  same rule for b

Η αντίθετη παρατήρηση εδώ είναι ότι το ταίριασμα (a, b) θεωρείται σταθερό ακόμα και αν το a και το b προτιμούν άλλους συντρόφους…όπως όσο αυτές οι μυστικές συντριβές δεν συντρίβονται πίσω. Τα στοιχεία a και bείναι ο καλύτερος βιώσιμος συμβιβασμός μεταξύ τους όταν λαμβάνονται υπόψη οι προτιμήσεις όλων των άλλων. Αυτή η στρατηγική έχει επίσης ως αποτέλεσμα την εγγύηση ότι εάν υπάρχουν κάποιοι ερωτευμένοι Ρωμαίος και Ιουλιέτα, θα ταιριάξουν μαζί.

Το άλλο σπουδαίο μέρος του Stable Marriage Matching είναι ότι η λύση είναι απλή και καλά κατανοητή — απλώς αναζητήστε τον αλγόριθμο Gale-Shapley. Μπορείτε να το εφαρμόσετε σε μια ώρα και να είστε στο δρόμο σας.

ΕΝΤΑΞΕΙ. Ας υποθέσουμε λοιπόν ότι έχουμε τώρα κάποια συνάρτηση ταιριάζουνπου παράγει την ακόλουθη έξοδο:

match(A, B) -> { matches: [<a,b>], additions: [b], deletions: [a] }

Η συνάρτηση αντιστοίχισης παίρνει ένα εξερχόμενο έγγραφο A και ένα εισερχόμενο έγγραφο B και παράγει ένα σύνολο αντιστοιχίσεων από σελίδα σε σελίδα, μαζί με μια λίστα με προστιθέμενες και διαγραμμένες σελίδες. Εάν |B| > |A| θα ονομάσουμε τυχόν μη ταίριασμα b που προστέθηκε και εάν |A| > |B| θα ονομάσουμε οποιοδήποτε μη αντιστοιχισμένο a έχει διαγραφεί. Αυτή δεν είναι η στρατηγική προσθήκης/διαγραφής δεν είναι τέλεια — υπάρχουν καλύτερες στρατηγικές που περιλαμβάνουν ισχύ αντιστοίχισης — αλλά θα τα πάει καλά σε πολλές περιπτώσεις.

Το μόνο που απομένει είναι να ορίσουμε κάποιο μέτρο έλξης που μας βοηθά να αποφασίσουμε ποιες σελίδες a παντρεύονται με ποιες σελίδες b.

Το "Chunky Jaccard" ως μέτρο έλξης εγγράφων

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

Γενικά, μπορείτε να ορίσετε ένα φάσμα μέτρων ομοιότητας κειμένου που πηγαίνουν από χονδροειδή (Jaccard) σε αυστηρά (με την ένδειξη "Εξτρεμιστής" παρακάτω). Στο παρακάτω σχήμα, τα A και B είναι τα σύνολα των διακριτικών σε δύο σελίδες, και τα a_i και b_i είναι τα i^ο διακριτικά αυτών των σελίδων.

  • Η Ομοιότητα Jaccard είναι ένα χονδροειδές μέτρο ομοιότητας εγγράφων. Εξετάζει δύο έγγραφα ως σάκους λέξεων και επιστρέφει το μέτρο του πόσες λέξεις ήταν ίδιες διαιρεμένες με το πόσες υπήρχαν συνολικά. Εάν τα έγγραφα είναι απολύτως ίσα, J(A,B) = 1.0 και αν είναι τελείως ασύνδετα, J(A,B) = 0.0
  • Αυτό που ονόμασα ως Εξτρεμιστικόθα ήταν να ακολουθήσω την αντίθετη προσέγγιση από το "σακούλι με λέξεις" και να συγκρίνω την 1η λέξη κάθε εγγράφου μεταξύ τους. Από τη μια πλευρά, καταλαβαίνω τον εξτρεμισμό - σε τελική ανάλυση, τα έγγραφα δεν είναι σακούλες με λόγια. Η σειρά των λέξεων έχει σημασία! Αλλά από την άλλη πλευρά, αυτό είναι εξαιρετικά εύθραυστο παρουσία σφαλμάτων. Τι θα συμβεί αν το OCR ενός εγγράφου εισήγαγε μια επιπλέον λέξη; Αυτή η μεμονωμένη μετατόπιση του δείκτη θα προκαλούσε πτώση της βαθμολογίας ομοιότητας κατά 0,5 κατά μέσο όρο.
  • Η Ομοιότητα "Χονδροειδής" Jaccard αντιπροσωπεύει μια ισορροπία μεταξύ του μοντέλου με τις λέξεις και της εξτρεμιστικής παραλλαγής. Παίρνουμε περίπου chunk_size, το οποίο εκφράζεται ως ποσοστό, και μετά χαράζουμε το έγγραφο σε N τμήματα, κάθε ένα chunk_size τοις εκατό του εγγράφου. Όταν το chunk_size πλησιάζει το μηδέν, ο Chunky Jaccard είναι το ίδιο με το εξτρεμιστικό μέτρο. Όταν chunk_size = 1, η Chunky Jaccard είναι ίδια με την έκδοση του bag of words.

Άρα αυτό είναι πραγματικά. Επιλέξτε μία από τις δύο παραλλαγές Jaccard, εφαρμόστε την και χρησιμοποιήστε την ως μέτρο έλξης στον αλγόριθμο Gale-Shapley.

Η αντιστοίχιση έγινε απλή

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

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

Τα δυνατά γραφικά κάνουν τα πράγματα να θυμάστε εύκολα

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

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

Επομένως, μην απορρίπτετε τις ιστορίες πίσω από αυτούς τους αλγόριθμους ως κατάχρηση μεταφοράς. Ζαμπόν τους! Οραματιστείτε τις γελοίες αναπαραστάσεις τους στο μυαλό σας, ώστε να είναι πιο εύκολο να τις ανακαλέσετε όταν τις χρειάζεστε περισσότερο.

ΥΓ: Ελάτε να λύσετε ενδιαφέροντα προβλήματα στο Instabase

Εάν η επίλυση προβλημάτων μεγάλου αντίκτυπου με δεδομένα πραγματικού κόσμου ακούγεται σαν ένας καλός τρόπος για να περάσετε τη μέρα σας, πλώστε το χέρι και πείτε γεια. Το Instabase προσλαμβάνει ισχυρούς γενικούς CS, καθώς και ειδικούς σε συστήματα, μηχανική μάθηση, NLP και web front-end.