-
Article
Author Correction: Learnability can be undecidable
In the version of this Article originally published, the following text was missing from the Acknowledgements: ‘Part of the research was done while S.M. was at the Institute for Advanced Study in Princeton and...
-
Article
Learnability can be undecidable
The mathematical foundations of machine learning play a key role in the development of the field. They improve our understanding and provide tools for designing new learning paradigms. The advantages of mathem...
-
Chapter and Conference Paper
On Version Space Compression
We study compressing labeled data samples so as to maintain version space information. While classic compression schemes [11] only ask for recovery of a samples’ labels, many applications, such as distributed lea...
-
Chapter and Conference Paper
Finding Meaningful Cluster Structure Amidst Background Noise
We consider efficient clustering algorithm under data clusterability assumptions with added noise. In contrast with most literature on this topic that considers either the adversarial noise setting or some noi...
-
Chapter and Conference Paper
Multi-task and Lifelong Learning of Kernels
We consider a problem of learning kernels for use in SVM classification in the multi-task and lifelong scenarios and provide generalization bounds on the error of a large margin classifier. Our results show th...
-
Chapter and Conference Paper
Information Preserving Dimensionality Reduction
Dimensionality reduction is a very common preprocessing approach in many machine learning tasks. The goal is to design data representations that on one hand reduce the dimension of the data (therefore allowing...
-
Article
Domain adaptation–can quantity compensate for quality?
The Domain Adaptation problem in machine learning occurs when the distribution generating the test data differs from the one that generates the training data. A common approach to this issue is to train a stan...
-
Chapter and Conference Paper
On the Hardness of Domain Adaptation and the Utility of Unlabeled Target Samples
The Domain Adaptation problem in machine learning occurs when the test and training data generating distributions differ. We consider the covariate shift setting, where the labeling function is the same in bot...
-
Chapter and Conference Paper
Learning a Classifier when the Labeling Is Known
We introduce a new model of learning, Known-Labeling-Classifier-Learning (KLCL). The goal of such learning is to find a low-error classifier from some given target-class of predictors, when the correct labeling i...
-
Article
Open AccessA theory of learning from different domains
Discriminative learning methods for classification perform well when training and test data are drawn from the same distribution. Often, however, we have plentiful labeled training data from a source domain but w...
-
Chapter and Conference Paper
Theory-Practice Interplay in Machine Learning – Emerging Theoretical Challenges
Theoretical analysis has played a major role in some of the most prominent practical successes of statistical machine learning. However, mainstream machine learning theory assumes some strong simplifying assum...
-
Article
A notion of task relatedness yielding provable multiple-task learning guarantees
The approach of learning multiple “related” tasks simultaneously has proven quite successful in practice; however, theoretical justification for this success has remained elusive. The starting point for previ...
-
Article
A framework for statistical clustering with constant time approximation algorithms for K-median and K-means clustering
We consider a framework of sample-based clustering. In this setting, the input to a clustering algorithm is a sample generated i.i.d by some unknown arbitrary distribution. Based on such a sample, the algorithm h...
-
Chapter and Conference Paper
Stability of k-Means Clustering
We consider the stability of k-means clustering problems. Clustering stability is a common heuristics used to determine the number of clusters in a wide variety of clustering applications. We continue the theoret...
-
Chapter and Conference Paper
Alternative Measures of Computational Complexity with Applications to Agnostic Learning
We address a fundamental problem of complexity theory – the inadequacy of worst-case complexity for the task of evaluating the computational resources required for real life problems. While being the best know...
-
Chapter and Conference Paper
A Sober Look at Clustering Stability
Stability is a common tool to verify the validity of sample based algorithms. In clustering it is widely used to tune the parameters of the algorithm, such as the number k of clusters. In spite of the popularity ...
-
Chapter and Conference Paper
Learning Bounds for Support Vector Machines with Learned Kernels
Consider the problem of learning a kernel for use in SVM classification. We bound the estimation error of a large margin classifier when the kernel, relative to which this margin is defined, is chosen from a f...
-
Chapter and Conference Paper
A Framework for Statistical Clustering with a Constant Time Approximation Algorithms for K-Median Clustering
We consider a framework in which the clustering algorithm gets as input a sample generated i.i.d by some unknown arbitrary distribution, and has to output a clustering of the full domain set, that is evaluated...
-
Chapter and Conference Paper
Exploiting Task Relatedness for Multiple Task Learning
The approach of learning of multiple “related” tasks simultaneously has proven quite successful in practice; however, theoretical justification for this success has remained elusive. The starting point for pre...
-
Chapter and Conference Paper
Agnostic Boosting
We extend the boosting paradigm to the realistic setting of agnostic learning, that is, to a setting where the training sample is generated by an arbitrary (unknown) probability distribution over examples and ...
