Thesis Proposals

Label ranking is a specific type of preference learning problem, namely the problem of learning a model that maps instances to rankings over a finite set of predefined (choice) alternatives [1]. These alternatives are identified by their name or label while not being characterized in terms of any properties or attributes that could be potentially useful for learning. The dyad ranking problem is a generalization of the label ranking problem, where the instances and additionally also the alternatives are represented in terms of attributes. Here, the key notion of a dyad refers to a combination of an instance and an alternative attribute. In [2] a dyad ranking learner, called BilinPL, is proposed by (i) representing dyads in terms of a Kronecker product of the instance and label attributes and (ii) maximizing the likelihood-function of a bilinear Plackett-Luce model by means of the majorization-maximization algorithm. The bilinear Plackett-Luce is an extension of a statistical model used for label ranking taking the additional information of the alternatives into account. In a subsequent work [3] the bilinear Plackett-Luce model was combined with neural networks (feed-forward multi-layer perceptrons) in order to learn joint-feature representations for the dyads. This method, called PLNet, allows for learning a (highly nonlinear) joint feature representation of the dyads and shows promising empirical results.

While the original papers provide an implementation of the two approaches in Java and Matlab, there is only a rudimentary implementation available in Python. However, this is somewhat unsatisfactory since Python has now become a standard programming language in the field of machine learning, especially due to its popular scikit-learn package for machine learning applications [4]. Accordingly, it would be highly desirable to have both methods available in Python in a welldocumented package that is compatible with the scikit-learn API. Another goal would be to reproduce the results of the experimental studies in the original papers. Finally, in [3] a method for the visualization of dyad rankings is proposed, which is based on the technique of multidimensional unfolding [5]. Therefore, another goal of the thesis would be to implement this visualization method in the Python package as well. more

Label ranking is a specific type of preference learning problem, namely the problem of learning a model that maps instances to rankings over a finite set of predefined (choice) alternatives [1]. These alternatives are identified by their name or label while not being characterized in terms of any properties or attributes that could be potentially useful for learning. The dyad ranking problem is a generalization of the label ranking problem, where the instances and additionally also the alternatives are represented in terms of attributes [2]. Here, the key notion of a dyad refers to a combination of an instance and an alternative attribute. In [2] it was suggested to represent dyads in terms of a Kronecker product of the instance and label attributes and use these in the bilinear Plackett-Luce, which is an extension of a statistical model used for label ranking taking the additional information of the alternatives into account. In a subsequent work [3] the bilinear Plackett-Luce model was combined with neural networks in order to learn joint-feature representations for the dyads. This method, called PLNet, allows for learning a (highly nonlinear) joint feature representation of the dyads and shows promising empirical results. However, the considered neural network is based on a simple feed-forward multi-layer perceptron architecture, while for some applications, especially for image data, it would be more desirable to use more sophisticated network architectures such as deep convolutional networks (CNN) for learning the joint feature representation of the dyads. Accordingly, the goal of this thesis would be to endow the PLNet approach with such architectures and evaluate the performance of these extensions in empirical studies. more

The notion of single-peaked preferences refers to a rather simple (and restricted) type of utility function. Roughly speaking, preferences are single-peaked if a set of choice alternatives can be sorted in a single dimension “from left to right”, so that one of these alternatives is assigned the highest degree of utility, and the utility for the other alternatives decreases with increasing distance from that alternative in both directions [1].

The goal of the thesis is to apply models of that kind to a data set comprising voters’ opinions in the form of pairwise comparisons between political parties (in Germany). The main question behind is whether political orientation is sufficiently “one-dimensional”, or maybe more complex, so that additional dimensions are needed to characterize the orientation of voters and provide an adequate picture of the political landscape. To this end, algorithms must be implemented for fitting single-peaked preference functions to the data, as well as goodnessof-fit tests to determine the quality of these preference models.

The thesis is planned as a cooperation with the Chair of Empirical Political Research and
Policy Analysis (Prof. P. Thurner). more

Information retrieval (IR) is one of the most important tasks in the field of information science. The goal of IR is to extract useful information from a potentially large and unstructured database. One relevant form of IR is similarity search, where one seeks to find similar objects within the unstructured database. To this end, the underlying data need to admit a sensible measure of similarity, first to design reasonable algorithmic solutions for similarity search, and second to assess the quality of the latter. Given such a measure of similarity, one could use the k-Nearest-Neighbors (kNN) combined with an efficient index structure such as an M-Tree, R-Tree, or K-D Tree to perform similarity search. However, this approach is known to be computationally costly, especially for high-dimensional data.

An alternative approach is locality-sensitive hashing (LSH), which is a hash-based indexing technique for similarity search yielding satisfactory empirical results if instantiated with suitable hash-functions [1]. Although there are by now a variety of LSH approaches for various types of complex data available, data in the form of preferences or rankings have received very little attention so far. The only work in this regard is [2]. This is somewhat surprising, as preference/ranking data have recently gained importance for practical applications, especially for the improvement of search engines and recommendation systems [3].
The goal of the thesis is to design and implement an LSH approach for ranking data based on an iterative process using the concept of (w-)shingling to extract meaningful multisets of pairwise preferences from the rankings. Based on this, one idea is to adopt the weighted MinHash algorithm using the generalized Jaccard similarity to define a suitable distance measure [4]. more

In an increasing number of machine learning applications involving human activities, such as opinion polls, sports competition, or recommender systems, the available data is partially or entirely not of a quantitative, but rather of a qualitative nature, such as partial resp. total rankings or even incomplete rankings of the involved entities [1]. Such type of data is typically referred to as preference data and has given rise to the growing subfield of preference learning [2]. Unlike the classical machine learning problem, where the data is real-valued and methods can leverage the appealing properties of the Euclidean space, preference data is mathematically more difficult to handle, as the space of rankings (permutations) is lacking a vectorial structure. Nevertheless, the field of preference-based learning has evolved quite rapidly over the past decades, bringing up numerous problem frameworks ranging from variants of batch learning scenarios to online and reinforcement learning.

One key modeling approach, which has indisputable lead to significant progress in preference-based learning, is the usage of a Statistical Rank Model, providing a sound and convenient probabilistic model for the underlying preference data, which in turn can give rise to reasonable as well as practically powerful learning algorithms. Valuable insights into the numerical performance of preference-based learning algorithms can be gained by conducting experiments with synthetic preference data generated by statistical rank models. For this purpose, researchers can benefit from existing software packages in their favorite programming language, which provide convenient and versatile functions for dealing with preference data.

Although software packages for statistical rank models exist for some programming languages which are prevalent in machine learning research, such as R [3], there is (somewhat surprisingly) no software package available for Python [4], despite its increasing usage in machine learning research. more

Ridge regression is a standard approach for estimating the coefficients of a linear model when the features are highly correlated [1]. Especially in several online learning settings, it has been used quite intensively as it comes with a closed-form solution for the coefficient estimates, which in turn allows efficient coefficient updates once new data is available. One practically relevant example of an online learning setting is the online algorithm selection (OAS) problem, in which instances of an algorithmic problem class are presented to an algorithm selector one after another, and the algorithm selector has to quickly select a presumably best algorithm from a fixed set of candidate algorithms [2]. In many online prediction tasks, such as OAS, one usually observes the feature for which a prediction of the label(s) is to be made before the prediction is made. This has motivated to adapt ridge regression, which only takes the previously seen features into account, such that the current feature is considered for the prediction as well. One such adaptation is the forward regression [3,4], for which recent work has shown theoretically that it might be advantageous over ridge regression in specific online learning settings [5]. These theoretical results were corroborated by a simulation study on synthetic data sets. The goal of the thesis is to investigate whether the forward regression leads to superior results over ridge regression in OAS problems. To this end, the ridge regression underlying the various algorithm selectors proposed in [6] will be replaced by the forward algorithm, and the resulting algorithm selectors will be evaluated using the ASlib benchmark. more

xAI algorithms are a set of approaches toward understanding black-box models. However, in recent years, xAI algorithms became themselves questionable as many failed to explain basic transparent models. Moreover, given the huge number of known evaluation metrics for xAI (Fidelity, Fragility, Stability, etc.), it became difficult for data scientists to accurately evaluate each xAI and to remain up to date on its evolution. This issue yields a clearly visible symptom known as the illusion of explanatory depth in interpreting xAI results [1], and it is now a known fact that data scientists are prone to misuse interpretability tools [2].

The goal of the thesis is to define an evaluation method for a specific type of xAI of your choice (Feature importance, Feature interaction, counterfactual, etc.) and learn common limitations and misuse of existing algorithms. A solution to mitigate common issues could be elaborated in the second part of the thesis. more

In [1] and [2], the authors have demonstrated that a hierarchical decomposition of a multi-label classification problem is beneficial in terms of both efficiency and predictive accuracy. The decomposition in both works is mainly based on relatively simple heuristics. Furthermore, in [3], an approach for optimizing hierarchical structures was proposed. The aim of this thesis is to extend the approach of [3] to cope with the relevant structures in [1] and [2]. Other approaches are also conceivable. Furthermore, the thesis should be centered around the following research questions: more

The notion of fuzzy pattern tree (FPT) refers to a class of hierarchical models, in which basic properties of data objects are represented in the form of fuzzy sets and successively combined into more complex properties by means of generalized aggregation functions [1]. Different machine learning algorithms have been proposed for constructing such models in a data-driven way, either using a top-down or a bottom-up strategy [3]. FPTs can be used for both classification and regression tasks and have a number of appealing properties, especially compared to traditional “flat” fuzzy models [4].

The goal of this thesis is to revisit FPTs from the perspective of deep learning, i.e., to view pattern trees as a specific type of deep model. In particular, there is an interest in understanding how the depth of an FPT influences important properties such as predictive accuracy. To this end, existing learning algorithms for FPTs and their implementation [2] must be extended, and suitable experimental studies must be conducted. These studies should also include a comparison with deep neural networks. PREREQUISITES: Good background in machine learning, especially supervised learning (e.g., classification, regression), deep learning, and empirical performance studies; algorithm design; programming skills; basic knowledge in fuzzy logic (advantageous but not a prerequisite). more

The problem of learning predictive models from imprecise data modelled in the form of sets has recently attracted increasing attention in machine learning, and various methods to tackle this problem have been proposed. This includes a method based on the idea of minimizing a generalized loss function (called optimistic superset loss of infimum loss), which compares a (precise) prediction with a set of potential target values in an “optimistic” way. While this method is well-motivated and exhibits interesting theoretical properties [2], an overly extreme optimism may sometimes incorporate a bias in the learning process. Therefore, an adjusted version of the latter has recently been proposed in [1]. The goal of the thesis is to implement this proposal for specific types of machine learning problems and to evaluate it on real data. more

A fuzzy pattern tree (FPT) is a specific type of hierarchical fuzzy model [1]. More specifically, the structure of an FPT is that of a binary tree, whose inner nodes are marked with generalized (fuzzy) logical and arithmetic operators, while the leaf nodes are associated with (unary) fuzzy predicates on a given set of input attributes. Fuzzy pattern trees can be useful for a variety of machine learning applications. They can be used as regression or classification models with some interesting properties in terms of interpretability and the ability to incorporate expert knowledge into the modeling and learning process.

Fuzzy pattern trees share a common property with modern neural network architectures [2]: both model classes can be referred to as deep in the sense that raw values given by input attributes are successively combined (aggregated) with each other, building a feature-hierarchy layer by layer, eventually ending up with a final score in the output layer or root node, respectively. However, while fuzzy pattern trees so far have only be considered as binary trees, neural networks usually encompass a huge variety of more general (often fully connected) network structures.

Of special interest for many applications are the so-called autoencoder [2] architectures. These are frequently used to pre-train a compressed general purpose representation of the raw input features for later use in more specialized networks solving a concrete learning task. The idea of this thesis is to design a new deep aggregation autoencoder architecture that uses fuzzy logical operators and predicates like an FPT does while consisting of potentially fully connected layers compressing the input in a similar way as autoencoders. To accomplish this task, a new learning algorithm has to be designed. more

In the literature on preference learning, the problem of "learning to rank" (LTA) has arguably received the most attention so far. Broadly speaking, LTA deals with the task of leveraging suitable training data to learn a “ranker” in the sense of a function that produces predictions in the form of rankings (typically total orders) of query items. Depending on the concrete setting, different types of ranking problems can be distinguished, such as instance, object, and label ranking [1]. Moreover, depending on the type of training data used and the type of loss function minimised by the learner, a distinction between pointwise, pairwise, and listwise learning to rank has been made.

In the listwise approach [2], the learner seeks to leverage complete rankings (lists) as training information, instead of reducing such information to pairwise comparisons or preference information about individual items. Indeed, such reductions may come with a certain loss of information, which is avoided by the listwise approach. On the other side, listwise learning is challenging and often necessitates various approximations, which may in turn compromise its usefulness. The goal of the thesis is to provide a systematic overview of existing work on listwise learning to rank, along with a critical discussion of its advantages and disadvantages. more

The contextual dyad ranking framework is a generalization of the label ranking problem, where the instances and additionally also the alternatives are represented in terms of attributes. In [1] a dyad ranking learner is proposed by maximizing the likelihood-function of a bilinear Plackett-Luce model, which is an extension of a statistical model used for label ranking taking the additional information of the attributes into account. Recently, there have been some works on mixtures of Plackett-Luce models, which have shown to give a better fit to the data [2]. However, a mixture of bilinear Plackett-Luce models was not considered so far.

The goal of the thesis is to introduce a mixture model of bilinear Plackett-Luce models and investigate the identifiability of the model parameters. As a next step, an adaptation of the famous Expectation-Maximization (EM) algorithm, which is a popular framework for fitting the parameters of parametric mixture models, should be investigated. more

Many (binary and multi-class) classification methods in machine learning produce predictions in the form of scores, which provide an indication of the classifier’s confidence in a certain class assignment. Yet, the interpretation of such scores in terms of probabilities is normally not legitimate, although probabilities would be desirable in many applications. Therefore, so-called calibration methods have been developed [1, 2, 3, 4]. Roughly speaking, calibration methods learn mappings from scores to probabilities. Calibration can be used as a post-processing step, and most calibration methods can be combined with any scoring classifier.

The goal of this thesis is a comparative study of existing calibration methods. This includes a survey, in which each of these methods is described, a systematic comparison according to suitable criteria, an implementation of the methods, and an empirical study, in which their performance on real data sets is evaluated. more

Rank aggregation is aimed at finding a joint or consensus ranking among a set of preferences given over a set of alternatives. Considering the preference data as “noisy” ob- servations of this consensus, one approach to tackle rank aggregation is via estimation of an underlying probabilistic model. In [1], a Generalized Method of Moments (GMM) is proposed for one of the most commonly used probabilistic models called Plackett-Luce (PL) model.

The goal of the thesis is to elaborate on extensions of this method, in particular the following ones: (i) Although most aggregation problems include incomplete rankings, the authors only consider the case of complete rankings (except for top-k and bottom-k observations, which correspond to special cases of incomplete rankings). (ii) The method is compared experimentally to the well-known Minorization-Maximization algorithm [2].

However, since the empirical study is quite limited in scope, this comparison should be expanded, especially through the use of real-world data sets [3]. more

Conformal Prediction (CP) is a statistical approach to predictive modeling that allows for producing "reliable" predictions in the form of sets, which cover the true outcome with high probability [1]. One of its appealing properties is its aptitude for online learning settings, in which outcomes are predicted one by one. For this purpose, CP uses past experience (training examples) to obtain precise levels of confidence for new predictions.

By now, the CP framework has mainly been studied for "classical" scenarios, such as classification, regression, and clustering. The goal of the thesis is to investigate how the learning-to-rank problem can be tackled by means of the CP paradigm. For this purpose, a suitable nonconformity measure has to be defined, which is at the core of CP-related methods. As a nonconformity measure requires a notion of distance on the underlying data space, it seems to be more reasonable to focus on top-k-distances of the symmetric group to avoid high computational costs. The other ingredient of the nonconformity measure is a suitable point predictor, i.e., a rank aggregation procedure for the training data, for which several manifestations are conceivable [2, 3]. more

Label ranking is a specific problem in the realm of preference learning [1]. It can be seen as a generalization of multi-class classification, in which the problem is to learn a mapping from instances to rankings (permutations) over a finite number of alternatives (class labels). Ranking by pairwise comparison (RPC) is a state-of-the-art approach to label ranking [2]. RPC constructs one binary classifier for each pair of labels, and trains it to decide which of the two is preferred to the other one; thus, RPC effectively reduces a label ranking problem to a set of binary classification problems. At prediction time, a ranking is assembled from the predictions of the binary classifiers.

RPC can be seen as a special case of learning with error-correcting output codes (ECOC) [3]. Al- though the number of binary models is relatively small in comparison to the size of the output space, i.e., the set of permutations of the class labels, the predictions in principle suffice to recon- struct the correct ranking thanks to the special structure of that space. Yet, reconstruction gets difficult as soon as one of the classifiers makes a mistake. In particular, due to a lack of redundancy, mistakes of that kind cannot be compensated.

The goal of the thesis, therefore, is to develop an ECOC-approach for label ranking. Important questions to be addressed in this regard include the design of the coding matrix (e.g., the binary problems should be balanced), the question of how to handle incomplete observations (partial rankings) in the training data, and how to realize the decoding step efficiently. more

Probabilistic circuits represent uncertainty through probability distributions in a way that is both expressive and still computationally tractable by imposing specific structural properties [1]. More specifically, the probability distribution is modelled as a computational graph specified via recursive mixtures (sum units) and factorizations (product units) of simpler distributions (input unit), e.g., parametric distributions such as Bernoullis or Gaussians. While this modelling approach is already well suited for learning scenarios where the target probability distribution (i.e., the distribution to be modelled) is numerical in nature and has been studied intensively, not much has yet been done for probability distributions on domains with a complex structure. An important example is distributions over the symmetric group modelling preference relations over specific objects in a probabilistic way [2].

The goal of this thesis is to investigate the potential of probabilistic circuits for modelling probability distributions over preferences. In particular, the advantages of such preference-based probabilistic circuits over classical parametric preference probability distributions for real data in terms of goodness of fit are to be investigated. Another goal of the thesis is to check whether some of the common statistical preference probability distributions can be specified via a (preference-based) probabilistic circuit. more

Rank correlation measures, which originated in applied statistics, are nowadays used is many fields of application, such as information retrieval or sports analytics. Roughly speaking, a rank correlation measure can be seen as a measure of similarity (or, subsequent to a suitable transformation, a measure of distance) between two rankings. Henzgen and Hüllermeier [1] introduce a novel class of weighted rank correlation measures, which allows for assigning weights to positions. Thanks to this extension, deviations between two rankings may influence the similarity to a different extent, depending on which positions are involved. For example, when comparing the lists of websites returned by two search engines (queried with the same key words), one is typically more interested in the top of the ranking than in the bottom.

The aforementioned weights can be considered as parameters of the rank correlation measure. Thus, given a specific application, the performance of the measure as a similarity or distance can be optimized by tuning the weights in a proper way. This idea is closely connected to metric learning[2], that is, learning or adapting a distance measure for a specific purpose in a data-driven way. In metric learning, different types of training information are conceivable. For example, the data observed may suggest that the distance between rankings A and B should be smaller than the distance between A and C.

Taking existing methods in the field of metric learning as a point of departure, the goal of the thesis is to develop methods for the data-driven adaptation of weights in weighted rank correlation. more