1,721,084 research outputs found
Improving the union bound: A distribution dependent approach
No full textStatistical Learning Theory deals with the problem of estimating the performance of a learning procedure. Any learning procedure implies making choices and this choices imply a risk. When the number of choices is finite, the state-of-the-art tool for evaluating the total risk of all the choice made is the Union Bound. The problem of the Union Bound is that it is very loose in practice if no a-priori information is available. In fact, the Union Bound considers all choices equally plausible while, as a matter of fact, a learning procedure targets just particular choices disregarding the others. In this work we will show that it is possible to improve the Union Bound based results using a distribution dependent weighting strategy of the true risks associated to each choice. Then we will prove that our proposal outperforms or, in the worst case, it degenerate in the Union Bound
Towards algorithms and models that we can trust: A theoretical perspective
No full textIn the last decade it became increasingly apparent the inability of technical metrics such as accuracy, sustainability, and non-regressiveness to well characterize the behavior of intelligent systems. In fact, they are nowadays requested to meet also ethical requirements such as explainability, fairness, robustness, and privacy increasing our trust in their use in the wild. Of course often technical and ethical metrics are in tension between each other but the final goal is to be able to develop a new generation of more responsible and trustworthy machine learning. In this paper, we focus our attention on machine learning algorithms and associated predictive models, questioning for the first time, from a theoretical perspective, if it is possible to simultaneously guarantee their performance in terms of both technical and ethical metrics towards machine learning algorithms that we can trust. In particular, we will investigate for the first time both theory and practice of deterministic and randomized algorithms and associated predictive models showing the advantages and disadvantages of the different approaches. For this purpose we will leverage the most recent advances coming from the statistical learning theory: Complexity-Based Methods, Distribution Stability, PAC-Bayes, and Differential Privacy. Results will show that it is possible to develop consistent algorithms which generate predictive models with guarantees on multiple trustworthiness metrics
Generalization performances of randomized classifiers and algorithms built on data dependent distributions
No full textIn this paper we prove that a randomized algorithm based on the data generating dependent prior and data dependent posterior Boltz- mann distributions of Catoni (2007) is Differentially Private (DP) and shows better generalization properties than the Gibbs (randomized) classi- fier associated to the same distributions. For this purpose, we will develop a tight DP-based generalization bound, which improve over the current state-of-the-art Hoefiding-type bound
Local Rademacher Complexity Machine
No full textSupport Vector Machines (SVMs) are a state-of-the-art and powerful learning algorithm that can effectively solve many real world problems. SVMs are the transposition of the Vapnik–Chervonenkis (VC) theory into a learning algorithm. In this paper, we present the Local Rademacher Complexity Machine (LRCM), a transposition of the Local Rademacher Complexity (LRC) theory, the state-of-the-art evolution of the VC theory, into a learning algorithm. Analogously to what has been done for the SVMs, we will present first the theoretical ideas behind the LRC theory, we will show how these ideas can be translated into a learning algorithm, the LRCM, and then how the LRCM can be made efficient and kernelizable. By exploiting a series of real world datasets, we will show the effectiveness of the LRCM against the SVMs
Local rademacher complexity machine
No full textIn this paper we present the Local Rademacher Complexity Machine, a transposition of the Local Rademacher Complexity Theory into a learning algorithm. By exploiting a series of real world small-sample datasets, we show the advantages of our proposal with respect to the Support Vector Machines, i.e. the transposition of the milestone results of V. N. Vapnik and A. Chervonenkis into a learning algorithm
Mining Big Data with Random Forests
No full textIn the current big data era, naive implementations of well-known learning algorithms cannot efficiently and effectively deal with large datasets. Random forests (RFs) are a popular ensemble-based method for classification. RFs have been shown to be effective in many different real-world classification problems and are commonly considered one of the best learning algorithms in this context. In this paper, we develop an RF implementation called ReForeSt, which, unlike the currently available solutions, can distribute data on available machines in two different ways to optimize the computational and memory requirements of RF with arbitrarily large datasets ranging from millions of samples to millions of features. A recently proposed improved RF formulation called random rotation ensembles can be used in conjunction with model selection to automatically tune the RF hyperparameters. We perform an extensive experimental evaluation on a wide range of large datasets and several environments with different numbers of machines and numbers of cores per machine. Results demonstrate that ReForeSt, in comparison to other state-of-the-art alternatives such as MLlib, is less computationally intensive, more memory efficient, and more effective
Fair Empirical Risk Minimization Revised
No full textArtificial Intelligence is nowadays ubiquitous, thanks to a continuous process of commodification, revolutionizing but also impacting society at large. In this paper, we address the problem of algorithmic fairness in Machine Learning: ensuring that sensitive information does not unfairly influence the outcome of a classifier. We extend the Fair Empirical Risk Minimization framework (10) where the fair risk minimizer is estimated via constrained empirical risk minimization. In particular, we first propose a new, more general, notion of fairness which translates into a fairness constraint. Then, we propose a new convex relaxation with stronger consistency properties deriving both risk and fairness bounds. By extending our approach to kernel methods, we will also show that the proposal empirically over-performs the state-of-the-art Fair Empirical Risk Minimization approach on several real-world datasets
Informed Machine Learning: Excess risk and generalization
No full textMachine Learning (ML) has transformed both research and industry by offering powerful models capable of capturing complex phenomena. However, these models often require large, high-quality datasets and may struggle to generalize beyond the distributions on which they are trained. Informed Machine Learning (IML) tackles these challenges by incorporating domain knowledge at various stages of the ML pipeline, thereby reducing data requirements and enhancing generalization. Building on statistical learning theory, we present some theoretical comparison and insights about ML and IML excess risk and generalization performance. We then illustrate how these theoretical insights can be leveraged in practice through some practical examples. Our findings shed some light on the mechanisms and conditions under which IML can outperform traditional ML, offering valuable guidance for effective implementation in real-world settings
- …
