The objective of Extreme Multi-Label Completion (XMLCo) is to predict missing document labels drawn from a very large collection. Together with Extreme Multi-Label Classification (XMLC), XMLCo is arguably one of the most challenging document classification tasks, as the number of potential labels is generally very large compared to the number of labeled documents. The collection of labels is often structured in a taxonomy that encodes relationships between labels, and many methods have been proposed to leverage this hierarchy to improve XMLCo algorithms. In this paper, we propose a new approach to this problem: TAMLEC (Taxonomy-Aware Multi-task Learning for Extreme multi-label Completion). TAMLEC divides the problem into several Taxonomy-Aware Tasks, i.e. into specific subsets of the labels drawn from paths in the taxonomy, and trains on these tasks using a dynamic Parallel Feature sharing approach where parts of the model are shared between tasks while others are task-specific. Then, at inference time, TAMLEC uses the labels available in a document to predict missing labels, using the Weak-Semilattice structure that is naturally induced by the tasks. Our empirical evaluation on real-world datasets shows that TAMLEC substantially outperforms the state-of-the-art in XMLCo. Furthermore, additional experiments show that TAMLEC is particularly suited for few-shot settings, where new tasks or labels are introduced with only few examples after initial training.

Extreme Multi Label (XML) problems, and in particular XML completion -- the task of prediction the missing labels of an entity -- have attracted significant attention in the past few years. Most XML completion problems can organically leverage a label hierarchy, which can be represented as a tree that encodes the relations between the different labels.

The quantification of human perception through the study of psychometric functions Ψ is one of the pillars of experimental psychophysics. In particular, the evaluation of the threshold is at the heart of many neuroscience and cognitive psychology studies, and a wide range of adaptive procedures has been developed to improve its estimation. However, these procedures are often implicitly based on different mathematical assumptions on the psychometric function, and unfortunately, these assumptions cannot always be validated prior to data collection. This raises questions about the accuracy of the estimator produced using the different procedures. In the study we examine in this letter, we compare five adaptive procedures commonly used in psychophysics to estimate the threshold: Dichotomous Optimistic Search (DOS), Staircase, PsiMethod, Gaussian Processes, and QuestPlus. These procedures range from model-based methods, such as the PsiMethod, which relies on strong assumptions regarding the shape of Ψ, to model-free methods, such as DOS, for which assumptions are minimal. The comparisons are performed using simulations of multiple experiments, with psychometric functions of various complexity. The results show that while model-based methods perform well when Ψ is an ideal psychometric function, model-free methods rapidly outshine them when Ψ deviates from this model, as, for instance, when Ψ is a beta cumulative distribution function. Our results highlight the importance of carefully choosing the most appropriate method depending on the context.

In this paper we address a variant of the continuous multi-armed bandits problem, called the threshold estimation problem, which is at the heart of many psychometric experiments. Here, the objective is to estimate the sensitivity threshold for an unknown psychometric function Psi, which is assumed to be non decreasing and continuous. Our algorithm, Dichotomous Optimistic Search (DOS), efficiently solves this task by taking inspiration from hierarchical multi-armed bandits and Black-box optimization. Compared to previous approaches, DOS is model free and only makes minimal assumption on Psi smoothness, while having strong theoretical guarantees that compares favorably to recent methods from both Psychophysics and Global Optimization. We also empirically evaluate DOS and show that it significantly outperforms these methods, both in experiments that mimics the conduct of a psychometric experiment, and in tests with large pulls budgets that illustrate the faster convergence rate.

Wikidata is rapidly emerging as a key resource for a multitude of online tasks such as Speech Recognition, Entity Linking, Question Answering, or Semantic Search. The value of Wikidata is directly linked to the rich information associated with each entity – that is, the properties describing each entity as well as the relationships to other entities. Despite the tremendous manual and automatic efforts the community invested in the Wikidata project, the growing number of entities (now more than 100 million) presents multiple challenges in terms of knowledge gaps in the graph that are hard to track. To help guide the community in filling the gaps in Wikidata, we propose to identify and rank the properties that an entity might be missing. In this work, we focus on entities with a dedicated Wikipedia page in any language to make predictions directly based on textual content. We show that this problem can be formulated as a multi-label classification problem where every property defined in Wikidata is a potential label. Our main contribution, Wiki2Prop, solves this problem using a multimodal Deep Learning method to predict which properties should be attached to a given entity, using its Wikipedia page embeddings. Moreover, Wiki2Prop is able to incorporate additional features in the form of multilingual embeddings and multimodal data such as images whenever available. We empirically evaluate our approach against the state of the art and show how Wiki2Prop significantly outperforms its competitors for the task of property prediction in Wikidata, and how the use of multilingual and multimodal data improves the results further. Finally, we make Wiki2Prop available as a property recommender system that can be activated and used directly in the context of a Wikidata entity page.

In this article, we propose to extend the classical Convolutional Sparse Coding model (CSC) to multivariate data by introducing a new tensor CSC model that enforces sparsity and low-rank constraint on the activations. The advantages of this model are threefold. First, by using tensor algebra, this model takes into account the underlying structure of the data. Second, this model allows for complex atoms but enforces fewer activations to decompose the data, resulting in an improved summary (dictionary) and a better reconstruction of the original multivariate signal. Third, the number of parameters to be estimated are greatly reduced by the low-rank constraint. We exhibit the associated optimization problem and propose a framework based on alternating optimization to solve it. Finally, we evaluate it on both synthetic and real data.

We address the problem of tuning word embeddings for specific use cases and domains. We propose a new method that automatically combines multiple domain-specific embeddings, selected from a wide range of pre-trained domain-specific embeddings, to improve their combined expressive power. Our approach relies on two key components: 1) a ranking function, based on a new embedding similarity measure, that selects the most relevant embeddings to use given a domain and 2) a dimensionality reduction method that combines the selected embeddings to produce a more compact and efficient encoding that preserves the expressiveness. We empirically show that our method produces effective domain-specific embeddings that consistently improve the performance of state-of-the-art machine learning algorithms on multiple tasks, compared to generic embeddings trained on large text corpora.

As falls prevalence increases with the aging of the population, early detection of balance degradation is of great importance for efficient prevention and treatment. This work addresses the problem of quantifiying static balance with fully interpretable learning algorithms. Our approach relies on a heuristic based variant of the aggregation of weak classifiers constrained with a new model-space regularization combined with a family of interpretable features. In our experiments, these models outperforms their regular alternative, opening promising new research directions.

Regularization is used to find a solution that both fits the data and is sufficiently smooth, and thereby is very effective for designing and refining learning algorithms. But the influence of its exponent remains poorly understood. In particular, it is unclear how the exponent of the reproducing kernel Hilbert space (RKHS) regularization term affects the accuracy and the efficiency of kernel-based learning algorithms. Here we consider regularized least squares regression (RLSR) with an RKHS regularization raised to the power of m, where m is a variable real exponent. We design an efficient algorithm for solving the associated minimization problem, we provide a theoretical analysis of its stability, and we compare it with respect to computational complexity and prediction accuracy to the classical kernel ridge regression algorithm where the regularization exponent m is fixed at 2. Our results show that the m-power RLSR problem can be solved efficiently, and support the suggestion that one can use a regularization term that grows significantly slower than the standard quadratic growth in the RKHS norm.

We address the problem of dueling bandits defined on partially ordered sets, or posets. In this setting, arms may not be comparable, and there may be several (incomparable) optimal arms. We propose an algorithm, UnchainedBandits, that efficiently finds the set of optimal arms, or Pareto front, of any poset even when pairs of comparable arms cannot be a priori distinguished from pairs of incomparable arms, with a set of minimal assumptions. This means that UnchainedBandits does not require information about comparability and can be used with limited knowledge of the poset. To achieve this, the algorithm relies on the concept of decoys, which stems from social psychology. We also provide theoretical guarantees on both the regret incurred and the number of comparison required by UnchainedBandits, and we report compelling empirical results.

In this paper (This is a combined and expanded version of previous conference papers Kadri et al., 2010, 2011c) we consider the problems of supervised classification and regression in the case where attributes and labels are functions: a data is represented by a set of functions, and the label is also a function. We focus on the use of reproducing kernel Hilbert space theory to learn from such functional data. Basic concepts and properties of kernel-based learning are extended to include the estimation of function-valued functions. In this setting, the representer theorem is restated, a set of rigorously defined infinite-dimensional operator-valued kernels that can be valuably applied when the data are functions is described, and a learning algorithm for nonlinear functional data analysis is introduced. The methodology is illustrated through speech and audio signal processing experiments.

We study the restless bandit problem where arms are associated with stationary $\varphi$-mixing processes and where rewards are therefore dependent: the question that arises from this setting is that of carefully recovering some independence by `ignoring' the values of some rewards. As we shall see, the bandit problem we tackle requires us to address the exploration/exploitation/independence trade-off, which we do by considering the idea of a {\em waiting arm} in the new Remix-UCB algorithm, a generalization of Improved-UCB for the problem at hand, that we introduce. We provide a regret analysis for this bandit strategy; two noticeable features of Remix-UCB are that i) it reduces to the regular Improved-UCB when the $\varphi$-mixing coefficients are all $0$, i.e. when the i.i.d scenario is recovered, and ii) when $\varphi(n)=O(n^{-\alpha})$, it is able to ensure a controlled regret of order $\Ot\left( \Delta_*^{(\alpha- 2)/\alpha} \log^{1/\alpha} T\right),$ where $\Delta_*$ encodes the distance between the best arm and the best suboptimal arm, even in the case when $\alpha<1$, i.e. the case when the $\varphi$-mixing coefficients {\em are not} summable.

We study the stability properties of nonlinear multi-task regression in reproducing Hilbert spaces with operator-valued kernels. Such kernels, a.k.a. multi-task kernels, are appropriate for learning problems with nonscalar outputs like multi-task learning and structured output prediction. We show that multi-task kernel regression algorithms are uniformly stable in the general case of infinite-dimensional output spaces. We then derive under mild assumption on the kernel generalization bounds of such algorithms, and we show their consistency even with non Hilbert-Schmidt operator-valued kernels. We demonstrate how to apply the results to various multi-task kernel regression methods such as vector-valued SVR and functional ridge regression.