One of the most widely used techniques for data clustering is agglomerative clustering. Such algorithms have been long used across any different fields ranging from computational biology to social sciences to computer vision in part because they are simple and their output is easy to interpret. However, many of these algorithms lack any performance guarantees when the data is noisy, incomplete or has outliers, which is the case for most real world data. It is well known that standard linkage algorithms perform extremely poorly in presence of noise. In this work we propose two new robust algorithms for bottom-up agglomerative clustering and give formal theoretical guarantees for their robustness. We show that our algorithms can be used to cluster accurately in cases where the data satisfies a number of natural properties and where the traditional agglomerative algorithms fail. We also extend our algorithms to an inductive setting with similar guarantees, in which we randomly choose a small subset of points from a much larger instance space and generate a hierarchy over this sample and then insert the rest of the points to it to generate a hierarchy over the entire instance space. We then do a systematic experimental analysis of various linkage algorithms and compare their performance on a variety of real world data sets and show that our algorithms do much better at handling various forms of noise as compared to other hierarchical algorithms in the presence of noise.

Η Υπολογιστική Γεωμετρία έχει υιοθετήσει το μοντέλο της ακριβής αριθμητικής σε πραγματικούς αριθμούς. Αυτή η προσέγγιση όμως έχει μειονεκτήματα κατά την επίλυση των αλγορίθμων στις υπολογιστικές μηχανές μιας και αυτές λειτουργούν με πεπερασμένη ακρίβεια, κάτι που επηρεάζει όχι μόνο τα αποτελέσματα των αλγορίθμων αλλά την ορθότητα του προβλήματος, εξαιτίας των στρογγυλοποιήσεων που πραγματοποιούνται κατά τη διάρκεια εκτέλεσης του αλγορίθμου. Το πρόβλημα της επίλυσης γεωμετρικών αλγορίθμων με μοντέλο real-RAM αποτυγχάνει επειδή δεν μπορούν να γίνουν με ακρίβεια ή έστω μέσα σε συγκεκριμένο σφάλμα όλοι οι υπολογισμοί. Προσπαθώντας να επιλυθεί το πρόβλημα αυτό έχει εισαχθεί η έννοια των εύρωστων γεωμετρικών αλγόριθμων, δηλαδή αλγορίθμων οι οποίοι δίνουν αποδεκτά αποτελέσματα για όλες τις νόμιμες εισόδους του προβλήματος. Προκειμένου να επιλυθεί το πρόβλημα που ανακύπτει κατά την μεταφορά του αλγορίθμου σε μια υπολογιστική μηχανή, έχουν προταθεί δύο διαφορετικές προσεγγίσεις η καθεμία από τις οποίες ακολουθεί διαφορετική μεθοδολογία. Η μία ομάδα τεχνικών ονομάζεται perturbing και περιλαμβάνει μεθόδους οι οποίες μετατρέπουν το πρόβλημα έτσι ώστε να αποφευχθούν οι ασάφειες και τα λάθη. Η άλλη ομάδα ονομάζεται non perturbing και περιλαμβάνει μεθόδους που αντιμετωπίζουν το πρόβλημα με ακριβή αριθμητική. / The problem of resolution of geometric algorithms with a real - RAM model fails because it cannot have precision or a concrete fault for all the calculations. There exist two different approaches that give solution in this problem each one following a different methodology. A team of techniques is named perturbing and it includes methods what they change the problem so as the ambiguities and the errors are avoided. The other team is named non perturbing and it includes methods that face the problem with precise arithmetic.

Over the past few years, speech recognition technology performance on tasks ranging from isolated digit recognition to conversational speech has dramatically improved. Performance on limited recognition tasks in noiseree environments is comparable to that achieved by human transcribers. This advancement in automatic speech recognition technology along with an increase in the compute power of mobile devices, standardization of communication protocols, and the explosion in the popularity of the mobile devices, has created an interest in flexible voice interfaces for mobile devices. However, speech recognition performance degrades dramatically in mobile environments which are inherently noisy. In the recent past, a great amount of effort has been spent on the development of front ends based on advanced noise robust approaches. The primary objective of this thesis was to analyze the performance of two advanced front ends, referred to as the QIO and MFA front ends, on a speech recognition task based on the Wall Street Journal database. Though the advanced front ends are shown to achieve a significant improvement over an industry-standard baseline front end, this improvement is not operationally significant. Further, we show that the results of this evaluation were not significantly impacted by suboptimal recognition system parameter settings. Without any front end-specific tuning, the MFA front end outperforms the QIO front end by 9.6% relative. With tuning, the relative performance gap increases to 15.8%. Finally, we also show that mismatched microphone and additive noise evaluation conditions resulted in a significant degradation in performance for both front ends.

[pt] O objetivo deste trabalho é projetar e implementar um algoritmo eficiente, confiável e preciso para a interseção de superfícies triangulares que representam modelos geológicos complexos. A grandeza das coordenadas espaciais desses modelos, em contraste com o relativamente pequeno tamanho médio de seus elementos, levam a problemas numéricos que podem gerar modelos ruins ou a erros graves do modelador geométrico. Além disso, um alto nível de precisão é desejável para se evitar erros de modelagem que possam gerar acidentes no campo de exploração. Neste trabalho, é proposta uma solução para reduzir os problemas numéricos com o uso de algumas estratégias geométricas e da Aritmética Exata. Exemplos demonstram estes problemas de robustez e validam o algoritmo proposto. / [en] The goal of this work is to design and to develop an efficient, reliable, and accurate algorithm for the intersection of triangular surfaces that represent complex geological models. The wide range of these models coordinates in contrast with the relatively small average size of its elements lead up to numerical instability problems, which may generate bad models or crash the geometric modeler. Additionally, a high degree of precision is desired in the model to avoid accidents in the field of oil exploration. In this work, it is proposed a solution to reduce the numerical issues by the use of some geometrical strategies and the Exact Arithmetic. Examples are used to demonstrate these robustness problems and to validate the proposed algorithm.