2022¶

Sublinear algorithms¶

Μιλήσαμε αρχικά για την ανάγκη να έχουμε προσεγγισιτικούς αλγορίθμους για τον υπολογισμό κάποιων ποσοτήτων σε υπογραμμικό (sublinear) χρόνο, χρόνο δηλ. που είναι λιγότερος κι από όσο παίρνει να διαβάσουμε το input (εδώ $n$ παριστάνει το μέγεθος του input). Η έμφαση εδώ είναι στην ταχύτητα και όχι στην ακρίβεια.
Παραδοσιακά έχουμε τέτοιους αλγορίθμους σε αρκετά προβλήματα στατιστικής. Όταν π.χ. κάνουμε μια δημοσκόπηση για να δούμε τι ποσοστό των Ελλήνων ψηφίζει το Α κόμμα δε μας ενδιαφέρει (έως κάποιο βαθμό) η ακρίβεια. Δε θέλουμε να υπολογίσουμε το ακριβές ποσοστό. Αυτό άλλωστε θα απαιτούσε να ερωτήσουμε όλους για την κομματική τους προτίμηση. Είμαστε ευχαριστημένοι, π.χ., να εκτιμήσουμε το ποσοστό μέχρι διαφοράς 1% (εκτός αν πρόκειται φυσικά για πολύ μικρό κόμμα, οπότε μια τέτοια διαφορά θα εμηδένιζε την όποια πληροφορία). Επίσης το κάνουμε αυτό ρωτώντας ένα πολύ μικρό αριθμό ατόμων σε σχέση με το σύνολο.
Αν π.χ. έχουμε μια λίστα από $n$ στοιχεία $y_1, \ldots, y_n$ κάθε ένα από τα οποία είναι 0 ή 1 (δεν ψηφίζω το Α κόμμα, ψηφίζω το Α κόμμα), $\epsilon$ είναι η παράμετρος ακρίβειας και $\delta$ η παράμετρος πεποίθησης, τότε μας ενδιαφέρει να κάνουμε μια δειγματοληψία $k$ ατόμων από τα $n$ με αποτελέσματα $Y_1, \ldots, Y_k$ έτσι ώστε ο δειγματικός μέσος $\tilde{\mu} = \frac{1}{k}(Y_1+\cdots+Y_k)$ που θα υπολογίσουμε να μην απέχει πολύ από τον πραγματικό μέσο $\mu = \frac{1}{n}(y_1+\cdots+y_n)$ με μεγάλη πιθανότητα: $$ \mathbb{P}(|\tilde\mu-\mu| > \epsilon\mu) < \delta. $$ Από την ανισότητα Chernoff παίρνουμε ότι η πιθανότητα παραπάνω φράσσεται από $$ 2 e^{-\epsilon^2 \mu k/3}, $$ άρα, αν υποθέσουμε ότι $\mu \ge 1\% n$ παίρνουμε ότι η πιθανότητα που μας ενδιαφέρει είναι $\le 2 e^{-\epsilon^2 10^{-2} k /3}$ και αν πάρουμε το $k$ τέτοιο ώστε αυτή η τελευταία ποσότητα να είναι $\le \delta$ έχουμε την ακρίβεια που θέλουμε ($\epsilon$) με την επιθυμητή μέγιστη πιθανότητα αποτυχίας της εκτίμhσης ($\delta$).
Το επόμενο παράδειγμα που είδαμε (που δε χρησιμοποιεί πιθανότητες) είναι μια προσέγγιση (μέχρι ένα παράγοντα του 2) της διαμέτρου ενός γραφήματος όπου οι ακμές $uv$ φέρουν βάρη (αποστάσεις) $d(u, v)$ που ικανοποιούν την τριγωνική ανισότητα $$ d(u, v) \le d(u, w) + d(w, v), $$ για κάθε τριάδα κορυφών $u, v, w$. Αν το γράφημα μας έχει $n$ κορυφές τότε το μέγεθος του προβλήματος (πόσο χώρο χρειάζεται για να αποθηκευτεί) είναι $N={n \choose 2} \sim n^2/2$ αφού τόσες ακμές υπάρχουν. Αν θέλουμε να υπολογίσουμε ακριβώς τη διάμετρο $$ D = \max\{d(u, v):\ \text{$u, v$ κορυφές του γραφήματος}\} $$ τότε πρέπει να διαβάσουμε όλες τις τιμές $d(u, v)$ και άρα χρειαζόμαστε χρόνο $\sim n^2$. Μπορούμε όμως να υπολογίσουμε μια προσέγγιση $\Delta$ του $D$ που ικανοποιεί την ανισότητα $$ D/2 \le \Delta \le D, $$ ως εξής: σταθεροποιούμε μια οποιαδήποτε κορυφή, ας την πούμε $a$, και ορίζουμε $$ \Delta = \max\{d(a, u):\ \text{$u$ κορυφή του γραφήματος}\}. $$ Η άνω ανισότητα $\Delta \le D$ είναι προφανής και η κάτω είναι συνέπεια της τριγωνικής ανισότητας. Αν η διάμετρος πιάνεται στις κορυφές $u, v$, δηλ. $D = d(u, v)$, τότε $$ D = d(u, v) \le d(a, u) + d(a, v) \le \Delta+\Delta = 2\Delta. $$ Το πλεονέκτημα είναι ότι ο υπολογισμός της $\Delta$ παίρνει χρόνο μόνο $O(n) = O(\sqrt{N})$ αντί για $O(N)$ που παίρνει ο ακριβής υπολογισμός.
Είδαμε έπειτα ένα πρόβλημα από την περιοχή του "property testing", όπου επιθυμούμε να αποφανθούμε αν ένα αντικείμενο έχει μια ιδιότητα ή όχι, αλλά δε μας πειράζει, αν κάνουμε λάθος και πούμε ότι το αντικείμενο έχει την ιδιότητα όταν δεν την έχει, αλλά είναι "κοντά" στα αντικείμενα που την έχουν.
Μια μικρή περιγραφή των ερωτημάτων αυτών (από O. Goldreich, lecture notes), § 1.1:
Property testing: distinguishing between objects having a predetermined property and objects that are “far” from having this property. In all cases, the algorithms sought are such of sub-linear complexity, and in particular they only inspect relatively small portions of the object. Typically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ.
Το πρόβλημα που κοιτάξαμε είναι το πώς ελέγχουμε αν μια λίστα $n$ αριθμών είναι ταξινομημένη σε αύξουσα σειρά. Δείτε μια λεπτομερή περιγραφή εδώ: https://people.csail.mit.edu/ronitt/COURSE/S19/Handouts/scribe11.pdf, § 2.