Εβδομάδα 1: Εισαγωγή και επίλυση προβλημάτων

Σημειώσεις μελέτης βασισμένες στη Διάλεξη 1 του μαθήματος. Οι διαφάνειες της διάλεξης βρίσκονται στο Moodle.

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

Τι είναι η Τεχνητή Νοημοσύνη

Δεν υπάρχει ένας μοναδικός ορισμός της νοημοσύνης. Οι περισσότεροι ορισμοί συμφωνούν ότι περιλαμβάνει την ικανότητα να μαθαίνεις, να καταλαβαίνεις μια κατάσταση, να προσαρμόζεσαι σε κάτι νέο και να λύνεις προβλήματα. Πολλές από αυτές τις ικανότητες στηρίζονται στην κοινή λογική: γνώσεις που ένας άνθρωπος αποκτά εύκολα, αλλά είναι πολύ δύσκολο να τις «πεις» σε ένα πρόγραμμα.

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

Οι ορισμοί της ΤΝ διαφέρουν ως προς τον στόχο. Θέλουμε συστήματα που:

Το τεστ Turing

Το 1950 ο Alan Turing πρότεινε ένα πρακτικό κριτήριο: ένας άνθρωπος συνομιλεί γραπτά με κάποιον που δεν βλέπει. Αν δεν μπορεί να καταλάβει αν απέναντι είναι άνθρωπος ή μηχανή, η μηχανή «περνά» το τεστ.

Για να περάσει ένα πρόγραμμα το τεστ χρειάζεται πολλές περιοχές της ΤΝ μαζί: επεξεργασία φυσικής γλώσσας, αναπαράσταση γνώσης, αυτοματοποιημένη συλλογιστική και μηχανική μάθηση. Το πλήρες τεστ Turing ζητά επιπλέον να αναγνωρίζει εικόνες και αντικείμενα, άρα χρειάζεται και μηχανική όραση και ρομποτική.

Δύο μεγάλες προσεγγίσεις

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

Σήμερα η ΤΝ είναι παντού: από τη μηχανική μάθηση και τα μεγάλα γλωσσικά μοντέλα μέχρι την επιχειρηματική ευφυΐα (Business Intelligence), όπου τα δεδομένα μιας επιχείρησης αναλύονται για να παρθούν καλύτερες αποφάσεις.

Επίλυση προβλημάτων

Το κεντρικό θέμα του μαθήματος συνοψίζεται σε μία φράση:

Τεχνητή Νοημοσύνη = αναπαράσταση του προβλήματος + αναζήτηση της λύσης

Η επίλυση ενός προβλήματος έχει τρία στάδια:

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

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

Κατηγορίες προβλημάτων

Τα προβλήματα διαφέρουν ως προς το τι ξέρουμε από πριν και τι ψάχνουμε:

• Σχεδιασμός ενεργειών (planning): ξέρουμε ακριβώς την τελική κατάσταση και ψάχνουμε τη σειρά ενεργειών που οδηγεί εκεί. Π.χ. πλοήγηση ενός ρομπότ.
• Ικανοποίηση περιορισμών: ξέρουμε μόνο κάποιες ιδιότητες της λύσης και ψάχνουμε μια πλήρη λύση που τις τηρεί. Π.χ. ένα ωρολόγιο πρόγραμμα ή ένα σταυρόλεξο.
• Διαμόρφωση (configuration): ξέρουμε κάποιες ιδιότητες της λύσης και ψάχνουμε και τη λύση και τη σειρά κινήσεων που οδηγεί σε αυτή. Π.χ. μια διάταξη κύβων.
• Βελτιστοποίηση: λύσεις βρίσκονται εύκολα, αλλά ψάχνουμε την καλύτερη. Π.χ. η συντομότερη διαδρομή του πλανόδιου πωλητή.

Στη θεωρία χρησιμοποιούμε συχνά απλά προβλήματα (toy problems), όπως το 8-puzzle, η τρίλιζα, ο λαβύρινθος, οι πύργοι του Ανόι ή οι κανίβαλοι και οι ιεραπόστολοι. Είναι εύκολο να τα περιγράψεις, αλλά δείχνουν τις ίδιες δυσκολίες με τα πραγματικά προβλήματα, όπως το σκάκι ή τον πλανόδιο πωλητή.

Περιγραφή με χώρο καταστάσεων

Μια κατάσταση είναι ένα «στιγμιότυπο» του κόσμου του προβλήματος: τι ισχύει σε μια δεδομένη στιγμή. Ο χώρος καταστάσεων είναι το σύνολο όλων των έγκυρων καταστάσεων.

Τυπικά, ένα πρόβλημα γράφεται ως τετράδα P = (I, G, T, S):

• S: ο χώρος καταστάσεων.
• I: η αρχική κατάσταση (ανήκει στο S).
• G: το σύνολο των τελικών καταστάσεων, δηλαδή όσων πετυχαίνουν τον στόχο.
• T: οι τελεστές μετάβασης, δηλαδή οι επιτρεπτές ενέργειες. Κάθε τελεστής έχει προϋποθέσεις (πότε μπορεί να εφαρμοστεί) και πρέπει να οδηγεί σε έγκυρη κατάσταση.

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

Παράδειγμα: τα δύο ποτήρια

Έχουμε ένα ποτήρι των 70 ml και ένα των 50 ml, μια βρύση και έναν νεροχύτη. Ένα ποτήρι γεμίζει μέχρι το χείλος μόνο όταν είναι άδειο. Μπορούμε επίσης να αδειάσουμε ένα ποτήρι στον νεροχύτη ή να ρίξουμε νερό από το ένα στο άλλο. Ο στόχος είναι να έχουμε ακριβώς 40 ml σε ένα από τα δύο.

Γράφουμε μια κατάσταση ως ζεύγος (x, y): x ml στο ποτήρι των 70 και y ml στο ποτήρι των 50.

• Αρχική κατάσταση: (0, 0)
• Τελικές καταστάσεις: κάθε (x, y) με x = 40 ή y = 40
• Τελεστές: γέμισε ένα άδειο ποτήρι, άδειασε ένα ποτήρι, ρίξε από το ένα ποτήρι στο άλλο (μέχρι να αδειάσει το πρώτο ή να γεμίσει το δεύτερο)

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

Στο τέλος το ποτήρι των 70 έχει 40 ml. Αν σχεδιάσεις όλες τις καταστάσεις και τις κινήσεις ανάμεσά τους, παίρνεις έναν γράφο, και η λύση είναι ένα μονοπάτι σε αυτόν.

Περιγραφή με αναγωγή

Ένας δεύτερος τρόπος είναι να σπάσεις το πρόβλημα σε μικρότερα υποπροβλήματα, μέχρι να φτάσεις σε τόσο απλά που λύνονται αμέσως (τα «αρχέγονα» προβλήματα).

Κλασικό παράδειγμα είναι οι πύργοι του Ανόι. Για να μεταφέρεις n δίσκους από τον στύλο i στον στύλο k:

1. μετάφερε τους n−1 πάνω δίσκους στον βοηθητικό στύλο j,
2. μετάφερε τον μεγαλύτερο δίσκο στον στύλο k,
3. μετάφερε ξανά τους n−1 δίσκους από τον j στον k.

Κάθε βήμα με n−1 δίσκους σπάει με τον ίδιο τρόπο, μέχρι να μείνει ένας δίσκος, που μετακινείται με μία κίνηση.

Αλγόριθμοι αναζήτησης

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

Χώρος αναζήτησης και δένδρο αναζήτησης

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

Συνήθως τον σχεδιάζουμε ως δένδρο αναζήτησης:

Ευριστικές συναρτήσεις: μια πρώτη ματιά

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

Σε έναν λαβύρινθο (ή χάρτη πλέγματος) δύο συνηθισμένες εκτιμήσεις για την απόσταση από ένα σημείο S σε έναν στόχο F είναι:

Ευκλείδεια απόσταση:  d(S, F)  = √((xS − xF)² + (yS − yF)²)
Απόσταση Manhattan:   Md(S, F) = |xS − xF| + |yS − yF|

Παράδειγμα: από το S = (1, 1) στο F = (4, 5) η ευκλείδεια απόσταση είναι √(3² + 4²) = 5, ενώ η Manhattan είναι 3 + 4 = 7. Η Manhattan ταιριάζει όταν κινείσαι μόνο οριζόντια και κάθετα, όπως στους διαδρόμους ενός λαβυρίνθου.

Στο 8-puzzle δύο απλές ευριστικές είναι:

• πόσα πλακίδια είναι εκτός θέσης·
• το άθροισμα των αποστάσεων Manhattan κάθε πλακιδίου από τη σωστή του θέση.

Αρχική κατάσταση      Τελική κατάσταση
 2  8  3               1  2  3
 1  6  4               8  ·  4
 7  ·  5               7  6  5

Εδώ είναι εκτός θέσης τα πλακίδια 1, 2, 6 και 8, άρα η πρώτη ευριστική δίνει 4. Για τη δεύτερη: τα 1, 2 και 6 απέχουν από μία θέση και το 8 δύο θέσεις, άρα το άθροισμα είναι 5. Η δεύτερη ευριστική είναι πιο «ενημερωμένη», γιατί μετρά και πόσο μακριά είναι κάθε πλακίδιο, όχι μόνο αν είναι στη θέση του.

Μια σύντομη εισαγωγή στα νευρωνικά δίκτυα

Τα νευρωνικά δίκτυα είναι μοντέλα εμπνευσμένα από τους νευρώνες του εγκεφάλου. Δεν τα προγραμματίζεις με κανόνες· τα εκπαιδεύεις με παραδείγματα, αλλάζοντας τα βάρη των συνδέσεων ανάμεσα στους νευρώνες. Ένα καλά εκπαιδευμένο δίκτυο γενικεύει: απαντά σωστά και σε παραδείγματα που δεν έχει δει. Είναι ιδιαίτερα χρήσιμα όταν δεν υπάρχει απλός τύπος που να περιγράφει το πρόβλημα.

• Μάθηση με επίβλεψη (supervised): κατά την εκπαίδευση ξέρουμε τη σωστή απάντηση για κάθε παράδειγμα και το δίκτυο προσαρμόζεται ώστε να την πλησιάζει. Χρησιμοποιείται για ταξινόμηση (π.χ. «είναι αυτό γάτα ή σκύλος;») και πρόβλεψη (π.χ. την αυριανή τιμή μιας μετοχής).
• Μάθηση χωρίς επίβλεψη (unsupervised): δεν υπάρχουν σωστές απαντήσεις. Το δίκτυο ομαδοποιεί τα δεδομένα με βάση τις ομοιότητές τους (clustering) και εμείς ερμηνεύουμε τις ομάδες. Παράδειγμα είναι οι χάρτες αυτο-οργάνωσης (SOM), που τοποθετούν κοντά μεταξύ τους παρόμοια δεδομένα.

Θα επιστρέψουμε στη μηχανική μάθηση στο τέλος του εξαμήνου.

Σύνοψη

• ΤΝ = αναπαράσταση του προβλήματος + αναζήτηση της λύσης.
• Ένα πρόβλημα περιγράφεται ως P = (I, G, T, S): αρχική κατάσταση, τελικές καταστάσεις, τελεστές μετάβασης και χώρος καταστάσεων.
• Λύση είναι μια σειρά τελεστών από την αρχική σε μια τελική κατάσταση.
• Εναλλακτικά, ένα πρόβλημα περιγράφεται με αναγωγή σε απλούστερα υποπροβλήματα.
• Οι αλγόριθμοι αναζήτησης χωρίζονται σε τυφλούς, ευριστικούς και αλγορίθμους παιχνιδιών.
• Οι ευριστικές συναρτήσεις εκτιμούν την απόσταση από τον στόχο, π.χ. με την απόσταση Manhattan.

Ερωτήσεις αυτοαξιολόγησης

1. Ποια είναι τα τέσσερα στοιχεία της περιγραφής P = (I, G, T, S);

Ο χώρος καταστάσεων S, η αρχική κατάσταση I, το σύνολο τελικών καταστάσεων G και οι τελεστές μετάβασης T.

2. Βρες τρεις διαφορετικές τελικές καταστάσεις στο πρόβλημα των ποτηριών.

Τελική είναι κάθε κατάσταση με 40 ml σε ένα από τα δύο ποτήρια, π.χ. (40, 50), (40, 0) και (0, 40). Από το (40, 50) της λύσης παραπάνω, αν αδειάσεις το ποτήρι των 50 φτάνεις στο (40, 0). Αν μετά ρίξεις το νερό στο ποτήρι των 50, φτάνεις στο (0, 40).

3. Σε ένα πλέγμα, ποια απόσταση είναι πάντα μεγαλύτερη ή ίση: η ευκλείδεια ή η Manhattan;

Η Manhattan. Μετρά τη διαδρομή μόνο με οριζόντιες και κάθετες κινήσεις, ενώ η ευκλείδεια μετρά την ευθεία γραμμή, που είναι πάντα η συντομότερη.

4. Ποια είναι η βασική διαφορά μάθησης με και χωρίς επίβλεψη;

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

---

Πηγές: Διάλεξη 1 του μαθήματος· Ι. Βλαχάβας, Π. Κεφαλάς, Ν. Βασιλειάδης, Φ. Κόκκορας, Η. Σακελλαρίου, Τεχνητή Νοημοσύνη (4η έκδοση).