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

Abstract

In the present thesis a new pattern recognition methodology, as well as a new method for coping with computation problems caused by the use of finite word length in contemporary computers are presented. The introduced methods can resolve really important problems in the fields of Archaeometry and Computer Architecture. A new method for the automatic classification of a set of documents according to their writer is initially presented. The comparison between the various symbols appearing in the documents at hand is achieved by means of a novel shape matching method based on a new mathematical entity called plane curvature. Moreover, the affine transformations of rotation and parallel translation are taken into account, so that the final matching of any two shapes becomes optimal. The aforementioned method was applied to a number of alphabet symbols appearing in important ancient and Byzantine documents. For each comparison of two instances of a certain alphabet symbol, a value of a similarity criterion was calculated that best expresses the similarity between these instances. Furthermore, a number of novel statistical criteria applied to the values of the aforementioned similarity criterion is introduced. By means of these statistical criteria, the determination of the number of different writers who wrote the given ensemble of documents, as well as the clustering of the set of given documents according to their writer is achieved. The aforementioned method attributed 46 ancient inscriptions to 10 individual writers/carvers and 25 Byzantine codices to 4 distinct writers. Prominent epigraphists and professors of Classical Studies fully agreed with the classification proposed by the method. On the second part of the thesis, a novel approach for studying the finite precision error generation and propagation in any multiplication process performed in a contemporary computing machine is presented. The need for this study occurred during the execution of the algorithms corresponding to the aforementioned writer identification method. This error may accumulate and render the results of an algorithm totally erroneous very fast, especially in cases where multiple successive multiplications take place during the execution of the algorithm. In the present thesis, a new, general methodology that allows for exact tracking of the finite precision error’s main sources, as well as calculation of the exact number of erroneous decimal digits appearing in any algorithm’s multiplication result at any given time is introduced. The corresponding methodology determines the exact theoretical and practical evaluation of the finite precision error’s modification caused by any multiplication process. For any modification eventuality, the corresponding exact probabilities for it to take place are given. These results are also extended in order to include the case of execution of successive multiplications. Moreover, extensive experiments that fully supported the theoretical analysis were carried out. Specifically, the theoretical conditions under which an algorithm that includes numerous successive multiplications may be finite precision error resistant or not were experimentally verified. Finally, specific algorithms that quickly fail to provide accurate results due to finite precision error accumulation, as well as others that are remarkably finite precision error resistant, even if they contain a large number of successive multiplications, were presented.

Στην παρούσα διατριβή αναπτύσσονται μεθοδολογίες αναγνώρισης προτύπων και μέθοδοι αντιμετώπισης υπολογιστικών προβλημάτων που οφείλονται στη χρήση πεπερασμένου μήκους λέξης στους σύγχρονους υπολογιστές. Οι μεθοδολογίες αυτές αντιμετωπίζουν πραγματικά, σημαντικά προβλήματα της Αρχαιομετρίας και της Αρχιτεκτονικής Υπολογιστών. Αρχικά παρουσιάζεται μία νέα μέθοδος για την αυτόματη κατάταξη ενός αριθμού κειμένων επί τη βάσει του γραφέα τους. Η σύγκριση των συμβόλων από τα οποία αποτελούνται τα κείμενα αυτά πραγματοποιείται με μία πρωτότυπη μέθοδο προσαρμογής σχημάτων, η οποία βασίζεται σε μία νέα μαθηματική οντότητα, την επίπεδη καμπυλότητα. Η προσαρμογή αυτή χρησιμοποιεί επιπλέον τους αφινικούς μετασχηματισμούς της στροφής και της παράλληλης μετατόπισης, ούτως ώστε να γίνει βέλτιστη. Η μέθοδος αυτή εφαρμόστηκε σε έναν αριθμό συμβόλων της αλφαβήτου που εμφανίζονται σε σημαντικά αρχαία και βυζαντινά κείμενα. Σε κάθε σχετική προσαρμογή υπολογίζεται η τιμή ενός κριτηρίου ομοιότητας που βέλτιστα εκφράζει το βαθμό ομοιότητας δύο υλοποιήσεων. Ακολούθως, εισάγονται κατάλληλα πρωτότυπα στατιστικά κριτήρια, τα οποία δρουν επί αυτών των τιμών του κριτηρίου ομοιότητας, διαχωρίζουν τους διαφορετικούς γραφείς που έγραψαν τα υπό μελέτη κείμενα και αποδίδουν σε κάθε γραφέα τα κείμενα που αυτός είχε γράψει. Η ανωτέρω μέθοδος κατέταξε 46 αρχαίες επιγραφές σε 10 γραφείς/λιθοξόους και 25 βυζαντινούς παπύρους σε 4 γραφείς. Με την κατάταξη αυτή συμφώνησαν πλήρως επιφανείς επιγραφολόγοι και καθηγητές Κλασικών Σπουδών. Σε επόμενο στάδιο, παρουσιάζεται μία νέα προσέγγιση για τη μελέτη παραγωγής και διάδοσης του λάθους πεπερασμένης ακρίβειας κατά την εκτέλεση της πράξης του πολλαπλασιασμού στους σύγχρονους υπολογιστές. Η ανάγκη αυτής της μελέτης προέκυψε και κατά την εκτέλεση των προαναφερθέντων, αρκετά περίπλοκων αλγορίθμων ταυτοποίησης γραφέα. Το συγκεκριμένο λάθος πεπερασμένης ακρίβειας, ειδικά σε περιπτώσεις εκτέλεσης πολλών διαδοχικών πολλαπλασιασμών, είναι δυνατόν να συσσωρεύεται, καθιστώντας τα αποτελέσματα του αντίστοιχου αλγορίθμου αναξιόπιστα ή/και εντελώς λανθασμένα. Στην παρούσα διατριβή εισάγεται μία νέα, γενική μεθοδολογία που επιτρέπει τον εντοπισμό των κυρίων πηγών γένεσης αριθμητικού λάθους κβαντισμού και τον επακριβή υπολογισμό του αριθμού των λανθασμένων ψηφίων που συσσωρεύονται στα γινόμενα που υπολογίζονται κατά την εκτέλεση του αλγορίθμου. Η σχετική μεθοδολογία οδηγεί στον ακριβή θεωρητικό και πρακτικό υπολογισμό της τροποποίησης του λάθους πεπερασμένης ακρίβειας που μπορεί να προκαλέσει ένας τυχών πολλαπλασιασμός. Για κάθε σχετικό ενδεχόμενο τροποποίησης, οι αντίστοιχες πιθανότητες αυτό να λάβει χώρα δίνονται επακριβώς. Τα ανωτέρω αποτελέσματα επεκτείνονται και στην περίπτωση εκτέλεσης διαδοχικών πολλαπλασιασμών. Επιπλέον, πραγματοποιήθηκαν εκτεταμένα πειράματα, τα οποία πλήρως επιβεβαίωσαν τις θεωρητικές προβλέψεις. Ειδικότερα, επιβεβαιώθηκαν οι θεωρητικά προβλεπόμενες συνθήκες, οι οποίες μπορούν να καταστήσουν έναν αλγόριθμο που περιλαμβάνει πολλούς πολλαπλασιασμούς ανθεκτικό ή όχι στη γένεση και συσσώρευση λάθους πεπερασμένης ακρίβειας. Τέλος, δόθηκαν συγκεκριμένοι αλγόριθμοι που αστοχούν πλήρως λόγω επανειλημμένων πολλαπλασιασμών, καθώς και άλλοι αλγόριθμοι που είναι πολύ ανθεκτικοί στο λάθος πεπερασμένης ακρίβειας, αν και περιλαμβάνουν μεγάλο πλήθος πολλαπλασιασμών.