Recommendation systems are emerging as an important business application as the demand for personalized services in E-commerce increases. Collaborative filtering techniques are widely used for predicting a user's preference or generating a list of items to be recommended. In this thesis, we develop several new approaches for collaborative filtering based on model combination and kernel smoothing. Specifically, we start with an experimental study that compares a wide variety of CF methods under different conditions. Based on this study, we formulate a combination model similar to boosting but where the combination coefficients are functions rather than constant. In another contribution we formulate and analyze a local variation of matrix factorization. This formulation constructs multiple local matrix factorization models and then combines them into a global model. This formulation is based on the local low-rank assumption, a slightly different but more plausible assumption about the rating matrix. We apply this assumption to both rating prediction and ranking problems, with both empirical validations and theoretical analysis. We contribute with this thesis in four aspects. First, the local approaches we present significantly improve the accuracy of recommendations both in rating prediction and ranking problems. Second, with the more realistic local low-rank assumption, we fundamentally change the underlying assumption for matrix factorization-based recommendation systems. Third, we present highly efficient and scalable algorithms which take advantage of parallelism, suited for recent large scale datasets. Lastly, we provide an open source software implementing the local approaches in this thesis as well as many other recent recommendation algorithms, which can be used both in research and production.

Η διαρκώς αυξανόμενη διαθεσιμότητα ηλεκτρονικών πηγών πληροφόρησης έχει δημιουργήσει νέα δεδομένα και απαιτήσεις στην περιοχή της Ανάκτησης Πληροφορίας. Υπάρχει αδιάκοπη ανάγκη για βελτίωση των υπαρχόντων και σχεδίαση νέων αλγορίθμων, που να επιτυγχάνουν υψηλή απόδοση και αξιοπιστία. Ένα επιπλέον ζητούμενο είναι η κατασκευή λογισμικού περιβάλλοντος που θα διευκολύνει τη χρήση υπαρχόντων αλγορίθμων, την εισαγωγή νέων, το συνδυασμό τους και τη συγκριτική αξιολόγησή τους. Στην παρούσα διδακτορική διατριβή, εστιάζουμε σε μεθόδους ανάκτησης πληροφορίας (με έμφαση στην ανάκτηση κειμένου), που έχουν στον πυρήνα τους τεχνολογίες Γραμμικής Άλγεβρας και πιο συγκεκριμένα σε τεχνικές που αξιοποιούν τα φασματικά χαρακτηριστικά των μητρώων όρων-κειμένων. Υπενθυμίζουμε ότι περίοπτη θέση στην περιοχή της Ανάκτησης Πληροφορίας, όσον αφορά τις τεχνικές της γραμμικής άλγεβρας, κατέχουν οι ιδιάζουσες τιμές και τα ιδιάζοντα διανύσματα των μητρώων. Περιγράφουμε επίσης το σχεδιασμό και την κατασκευή ενός ολοκληρωμένου περιβάλλοντος που διευκολύνει τους χρήστες στην ανάπτυξη, χρήση και αξιολόγηση των αλγορίθμων που στηρίζεται στο εξαιρετικά διαδεδομένο περιβάλλον της MATLAB. Αρχικά, εξετάζουμε τα βασικά προβλήματα στην Ανάκτηση Πληροφορίας, που είναι η ομαδοποίηση, η εξαγωγή σχετικών κειμένων και η κατηγοριοποίηση. Στην πρώτη κατηγορία προβλημάτων, στόχος μας είναι η βελτίωση παραδοσιακών αλγορίθμων όπως οι k-means και PDDP. Στο πλαίσιο αυτό προτείνουμε ένα σύνολο υβριδικών τεχνικών που βασίζονται στους δύο αυτούς αλγορίθμους και αντιμετωπίζουν προβλήματα που σχετίζονται με αυτούς. Ειδικότερα, πετυχαίνουν τη βελτίωση της απόδοσής τους ως προς την ποιότητα των παρεχόμενων αποτελεσμάτων ή ως προς την ταχύτητά τους. Σε σύγκριση με τον k-means, επιτυγχάνουν την αφαίρεση του στοιχείου της τυχαιότητας που τον χαρακτηρίζει, λόγω της γνωστής ευαισθησίας του στις αρχικές συνθήκες. Επιπλέον, προτείνουμε ένα ενιαίο σύνολο αποδοτικών "μεθόδων πυρήνα" (kernel methods) που μπορούν να χρησιμοποιηθούν στην περίπτωση που τα δεδομένα του προβλήματος έχουν μη γραμμικά χαρακτηριστικά. Οι παραπάνω υβριδικές μέθοδοι εφαρμόζονται και στο πρόβλημα της μπλοκ διαγωνιοποίησης στοχαστικών μητρώων που μοντελοποιούν για παράδειγμα χημικές διεργασίες, μέσω μαρκοβιανών αλυσίδων. Τα αρχικά αποτελέσματα που έχουμε, υποδεικνύουν ότι η προσέγγιση αυτή μπορεί να βελτιώσει σημαντικά υπάρχουσες μεθόδους, παρέχοντας ταυτόχρονα προσεγγίσεις του πλήθους των μπλοκ που αντιστοιχούν σε σταθερές καταστάσεις της μαρκοβιανής αλυσίδας. Τέλος, προτείνουμε μια διαφορετική προσέγγιση με τον αλγόριθμο ομαδοποίησης Oriented k-windows ο οποίος, όπως και ο PDDP, χρησιμοποιεί ιδιάζοντα διανύσματα (ισοδύναμα, κύριους άξονες - PCA) με σκοπό την εξαγωγή πληροφορίας αναφορικά με τον κυρίαρχο προσανατολισμό των ομάδων στον Ευκλείδειο χώρο. Στη συνέχεια, παρουσιάζουμε αλγορίθμους ανάκτησης σχετικών κειμένων και αλγορίθμους κατηγοριοποίησης που βασίζονται στη "Λανθάνουσα Σημασιολογική Δεικτοδότηση" (LSI). Πιο συγκεκριμένα, παρουσιάζουμε ένα αλγοριθμικό πλαίσιο που στηρίζεται σε μια "μεθοδολογία αντιπροσώπων", με την οποία προσπαθούμε να προσεγγίσουμε σημασιολογικά μια συλλογή, εξάγοντας υποχώρους του χώρου στηλών του μητρώου όρων-κειμένων που προσεγγίζουν τον βέλτιστο υποχώρο της διάσπασης ιδιαζουσών τιμών. Η μεθοδολογία μας χρησιμοποιεί αλγορίθμους ομαδοποίησης, όπως οι υβριδικές μέθοδοι που αναφέραμε, με σκοπό τη διάσπαση του προβλήματος σε ένα σύνολο όσο γίνεται περισσότερο ανεξάρτητων προβλημάτων που μπορούν να λυθούν περισσότερο αποδοτικά. Μέσα από μια εκτεταμένη πειραματική μελέτη, δείχνουμε ότι η συγκεκριμένη μεθοδολογία μπορεί να βελτιώσει άλλες διαδεδομένες προσεγγίσεις (LSI, LLSF κ.λπ.). Επίσης, επεκτείνουμε και εφαρμόζουμε τη "μεθοδολογία αντιπροσώπων" σε μεθόδους πυρήνα, καθώς επίσης και στο πρόβλημα υπολογισμού μη αρνητικών παραγοντοποίησεων μητρώων (NMF). Δείχνουμε ότι η χρήση της μεθοδολογίας επιφέρει σημαντική μείωση του κόστους σε μνήμη και υπολογισμούς των μεθόδων πυρήνα και βελτίωση της ποιότητας των αποτελεσμάτων της NMF. Η διατριβή στάθηκε αφορμή για την ανάπτυξη ενός ολοκληρωμένου λογισμικού περιβάλλοντος. Πιο συγκεκριμένα, οι νέες μέθοδοι που αναφέραμε, καθώς και άλλες διαδεδομένες τεχνικές έχουν υλοποιηθεί και ενταχθεί στο περιβάλλον Text to Matrix Generator (TMG). Το TMG στηρίζεται κατά κύριο λόγο στη MATLAB ενώ μικρότερα τμήματά του έχουν γραφτεί σε Perl. Το TMG αποτελείται από έξι τμήματα, ενώ είναι εύκολα επεκτάσιμο. Τα τμήματα αυτά παρέχουν μια ευρεία συλλογή μεθόδων ανάκτησης πληροφορίας που αποτελείται από μεθόδους (i) κατασκευής και ανανέωσης μητρώων όρων-κειμένων, (ii) υπολογισμού προσεγγίσεων μειωμένης διάστασης και (iii) μη αρνητικών παραγοντοποιήσεων, (iv) ανάκτησης σχετικών κειμένων, (v) ομαδοποίησης και (vi) κατηγοριοποίησης. Για όλα τα παραπάνω, το εργαλείο παρέχει κατάλληλα προσαρμοσμένες γραφικές διεπαφές που διευκολύνουν το χρήστη. Εναλλακτικά, οι λειτουργίες του μπορούν να κληθούν απευθείας από τη γραμμή εντολών. Το TMG διευκολύνει την ταχεία προτοτυποποίηση αλγορίθμων και διατίθεται ελεύθερα μέσω ιστοσελίδας (http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/). Από αναζητήσεις τεκμηριώνεται ότι έχει υποστηρίξει πολλούς επιστήμονες παγκοσμίως τόσο σε ερευνητικό όσο και σε εκπαιδευτικό επίπεδο. Περιγράφουμε επίσης τις πρόσφατες εργασίες μας για την ανάδειξη του TMG ως υπηρεσίας στον Παγκόσμιο Ιστό. Ειδικότερα, αναπτύσσεται λογισμικό για την απομακρυσμένη χρήση του TMG μέσω ειδικού API και τίθενται οι βάσεις για μελλοντική έρευνα που θα αφορά στην βελτιωμένη επίδοση και στην αποδοτική χρήση του συστήματος. / The amount of digital data is rapidly growing and continuously motivates research innovation in Information Retrieval. Much of the data is text, so there is an ever present need to push the field of Text Mining forward by designing and implementing novel, effective algorithms that attain high performance and reliability. It is also desirable to develop software environments that facilitate not only access to existing methods, but also enable the rapid prototyping, performance evaluation and incorporation of new algorithms for Text Mining. In this research we focus on algorithms that use Linear Algebra and Matrix Analysis tools as computational kernels. We use the term spectral to highlight the fact that our methods rely on the spectral characteristics of the underlying term-document matrices that encode the texts under study. We consolidate our new and existing algorithms in a software environment, called TMG, that we built on top of MATLAB and Perl. First, we consider the basic text mining tasks, namely clustering, ad-hoc retrieval and text classication. In clustering, we focus on a well-known spectral method, called PDDP (Principal Direction Divisive Partitioning) and investigate hybrid methods that combine PDDP and standard workhorses such as k-means. In particular, the proposed methods improve the performance of the aforementioned algorithms, regarding the quality of the attained clustering and/or their speed. Compared with k-means, our algorithms eliminate the non-determinism originating from k-means' initialization phase. We also propose a framework for kernel methods, that can be used in case the data exhibit non-linearities. Our spectral clustering algorithms are applied in sparse matrix reordering, specifically in the block diagonalization of row stochastic matrices. In addition to helping in the intepretation of a recent method for identifying metastable states of Markov chains, they also provide the means to improve their performance. Initial results, demonstrate that the proposed methodology can improve significantly over existing techniques, deriving approximations of the number of blocks corresponding to dinstict stable states of the underlying Markov chain. We also show how to use spectral methods to improve the performance of a density-based clustering approach, called Oriented k-windows. In particular, the algorithm uses information derived from the Principal Component Analysis (PCA), in order to guide a windowing technique, namely k-windows, that could give insights about the data orientation. The next part of the thesis deals with ad-hoc retrieval and classification methods, based on Latent Semantic Indexing (LSI). We propose an algorithmic framework based on a "representatives methodology", in order to approximate a collection semantically, by extracting subspaces of the column space of the term-document matrix, that approximate the optimal subspace derived by the SVD. Our methodology uses clustering techniques, like the aforementioned hybrid methods, in a preprocessing stage. Our objective is to split the problem into a set of independent subproblems that could be solved more efficiently. Results from extensive experimentation indicate that our methodology can improve a state-of-the-art method like LSI. We also apply the representatives methodology to kernel methods and Nonnegative Matrix Factorization (NMF). Extensive numerical experiments indicate that this methodology improves the computational cost and memory requirements of kernel methods and also increases the quality of the nonnegative approximations. We have incorporated all the proposed methods in a software environment, called Text to Matrix Generator (TMG). The first release of TMG was before this Ph.D. was even started. but has since undergone several upgrades and rewrites. TMG currently consists of six easily extensible modules. These modules provide methods for (i) constructing and updating term-document matrices, (ii) computing low rank approximations and (iii) non negative factorizations, and (iv) ad-hoc retrieval, (v) clustering and (vi) classification. TMG is accessible in two primary modes, graphical and command line and is freely downloadable from its webpage (http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/). As our usage logs indicate, TMG is being used worldwide for research and educational uses. We also describe a brief overview of open problems and ongoing work. We describe our first version of "remote TMG", that views TMG as a Web resource and provides remote access mode to it by means of a special API.

Multivariate linear regression methods are widely used statistical tools in data analysis, and were developed when some response variables are studied simultaneously, in which our aim is to study the relationship between predictor variables and response variables through the regression coefficient matrix. The rapid improvements of information technology have brought us a large number of large-scale data, but also brought us great challenges in data processing. When dealing with high dimensional data, the classical least squares estimation is not applicable in multivariate linear regression analysis. In recent years, some approaches have been developed to deal with high-dimensional data problems, among which dimension reduction is one of the main approaches. In some literature, random projection methods were used to reduce dimension in large datasets. In Chapter 2, a new random projection method, with low-rank matrix approximation, is proposed to reduce the dimension of the parameter space in high-dimensional multivariate linear regression model. Some statistical properties of the proposed method are studied and explicit expressions are then derived for the accuracy loss of the method with Gaussian random projection and orthogonal random projection. These expressions are precise rather than being bounds up to constants. In multivariate regression analysis, reduced rank regression is also a dimension reduction method, which has become an important tool for achieving dimension reduction goals due to its simplicity, computational efficiency and good predictive performance. In practical situations, however, the performance of the reduced rank estimator is not satisfactory when the predictor variables are highly correlated or the ratio of signal to noise is small. To overcome this problem, in Chapter 3, we incorporate matrix projections into reduced rank regression method, and then develop reduced rank regression estimators based on random projection and orthogonal projection in high-dimensional multivariate linear regression models. We also propose a consistent estimator of the rank of the coefficient matrix and achieve prediction performance bounds for the proposed estimators based on mean squared errors. Envelope technology is also a popular method in recent years to reduce estimative and predictive variations in multivariate regression, including a class of methods to improve the efficiency without changing the traditional objectives. Variable selection is the process of selecting a subset of relevant features variables for use in model construction. The purpose of using this technology is to avoid the curse of dimensionality, simplify models to make them easier to interpret, shorten training time and reduce overfitting. In Chapter 4, we combine envelope models and a group variable selection method to propose an envelope-based sparse reduced rank regression estimator in high-dimensional multivariate linear regression models, and then establish its consistency, asymptotic normality and oracle property. Tensor data are in frequent use today in a variety of fields in science and engineering. Processing tensor data is a practical but challenging problem. Recently, the prevalence of tensor data has resulted in several envelope tensor versions. In Chapter 5, we incorporate envelope technique into tensor regression analysis and propose a partial tensor envelope model, which leads to a parsimonious version for tensor response regression when some predictors are of special interest, and then consistency and asymptotic normality of the coefficient estimators are proved. The proposed method achieves significant gains in efficiency compared to the standard tensor response regression model in terms of the estimation of the coefficients for the selected predictors. Finally, in Chapter 6, we summarize the work carried out in the thesis, and then suggest some problems of further research interest. / Dissertation / Doctor of Philosophy (PhD)

In dieser Dissertation werden das Anregungsspektrum und das Phasendiagramm wechselwirkender Fermi- und Bosegase untersucht. Zu diesem Zweck wird eine neuartige renormierte Kadanoff-Martin-Näherung vorgestellt, die Selbstwechselwirkung von Teilchen vermeidet und somit eine einheitliche Beschreibung sowohl der normalen als auch der kondensierten Phase ermöglicht. Für Fermionen findet man den BCS-Zustand, benannt nach Bardeen, Cooper und Schrieffer, welcher entscheidend ist für das Phänomen der Supraleitung. Charakteristisch für diesen Zustand ist eine Energielücke im Anregungsspektrum an der Fermi-Energie. Weiterhin tritt für Bosonen eine Bose-Einstein-Kondensation (BEC) auf, bei der das Anregungsspektrum für kleine Impulse linear ist. Letzteres führt zum Phänomen der Suprafluidität. Über die bereits bekannten Phänomene hinaus findet man eine dem BCS-Zustand ähnliche Kondensation von Zweiteilchenbindungszuständen, sowohl für Fermionen als auch für Bosonen. Für Fermionen tritt ein Übergang zwischen der Kondensation von Bindungszuständen und dem BCS-Zustand auf, der sogenannte BEC-BCS-Übergang. Die Untersuchung der Zustandsgleichung zeigt, dass im Gegensatz zu Fermi-Gasen und Bose-Gasen mit abstoßender Wechselwirkung Bose-Gase mit anziehender Wechselwirkung zu einer Flüssigkeit kondensieren oder sich verfestigen, bevor es zur Kondensation von Bindungszuständen oder zur Bose-Einstein-Kondensation kommt. Daher können diese Phänomene voraussichtlich nicht in der Gasphase beobachtet werden. Zusammenfassend lässt sich sagen, dass das vorgestellte Näherungsverfahren sehr gut geeignet ist, die erwähnten Phänomene im Zusammenhang mit der Bose-Einstein-Kondensation zu beschreiben.

In dieser Dissertation werden das Anregungsspektrum und das Phasendiagramm wechselwirkender Fermi- und Bosegase untersucht. Zu diesem Zweck wird eine neuartige renormierte Kadanoff-Martin-Näherung vorgestellt, die Selbstwechselwirkung von Teilchen vermeidet und somit eine einheitliche Beschreibung sowohl der normalen als auch der kondensierten Phase ermöglicht. Für Fermionen findet man den BCS-Zustand, benannt nach Bardeen, Cooper und Schrieffer, welcher entscheidend ist für das Phänomen der Supraleitung. Charakteristisch für diesen Zustand ist eine Energielücke im Anregungsspektrum an der Fermi-Energie. Weiterhin tritt für Bosonen eine Bose-Einstein-Kondensation (BEC) auf, bei der das Anregungsspektrum für kleine Impulse linear ist. Letzteres führt zum Phänomen der Suprafluidität. Über die bereits bekannten Phänomene hinaus findet man eine dem BCS-Zustand ähnliche Kondensation von Zweiteilchenbindungszuständen, sowohl für Fermionen als auch für Bosonen. Für Fermionen tritt ein Übergang zwischen der Kondensation von Bindungszuständen und dem BCS-Zustand auf, der sogenannte BEC-BCS-Übergang. Die Untersuchung der Zustandsgleichung zeigt, dass im Gegensatz zu Fermi-Gasen und Bose-Gasen mit abstoßender Wechselwirkung Bose-Gase mit anziehender Wechselwirkung zu einer Flüssigkeit kondensieren oder sich verfestigen, bevor es zur Kondensation von Bindungszuständen oder zur Bose-Einstein-Kondensation kommt. Daher können diese Phänomene voraussichtlich nicht in der Gasphase beobachtet werden. Zusammenfassend lässt sich sagen, dass das vorgestellte Näherungsverfahren sehr gut geeignet ist, die erwähnten Phänomene im Zusammenhang mit der Bose-Einstein-Kondensation zu beschreiben.