Author name cluster

Joel Ratsaby

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

I&C Journal 2023 Journal Article

Learning half-spaces on general infinite spaces equipped with a distance function

Joel Ratsaby

For a general infinite distance space X, with no assumptions about the distance function, which need not satisfy the metric axioms, it is not clear what the VC-dimension of the class H of half-spaces in X may be and if there are generalization error bounds for learning H. We define a combinatorial dimension of X to be the independence number of the class of balls in X. We compute it for Euclidean space and for several non-metric distance spaces. Using this dimension, we are able to provide a generalization error bound for learning H over any infinite distance space X.

Details DOI

TCS Journal 2018 Journal Article

Large width nearest prototype classification on general distance spaces

Martin Anthony
Joel Ratsaby

In this paper we consider the problem of learning nearest-prototype classifiers in any finite distance space; that is, in any finite set equipped with a distance function. An important advantage of a distance space over a metric space is that the triangle inequality need not be satisfied, which makes our results potentially very useful in practice. We consider a family of binary classifiers for learning nearest-prototype classification on distance spaces, building on the concept of large-width learning which we introduced and studied in earlier works. Nearest-prototype is a more general version of the ubiquitous nearest-neighbor classifier: a prototype may or may not be a sample point. One advantage in the approach taken in this paper is that the error bounds depend on a ‘width’ parameter, which can be sample-dependent and thereby yield a tighter bound.

Details DOI

I&C Journal 2017 Journal Article

Classification based on prototypes with spheres of influence

Martin Anthony
Joel Ratsaby

We present a family of binary classifiers and analyse their performance. Each classifier is determined by a set of ‘prototypes’, with given labels. The classification of a given point is determined through the sign of a discriminant function. For each prototype, its sphere of influence is the largest sphere centred on it that contains no prototypes of opposite label, and, given a point to be classified, there is a contribution to the discriminant function at that point from precisely those prototypes whose spheres of influence contain the point. This contribution is positive from positive prototypes and negative from negative prototypes. These contributions are larger in absolute value the closer the point is (relative to the sphere's radius) to the prototype. We quantify the generalization error of such classifiers in a standard probabilistic learning model which involves the values of the discriminant function on the points of a random training sample.

Details DOI

TCS Journal 2015 Journal Article

A probabilistic approach to case-based inference

Martin Anthony
Joel Ratsaby

The central problem in case based reasoning (CBR) is to infer a solution for a new problem-instance by using a collection of existing problem–solution cases. The basic heuristic guiding CBR is the hypothesis that similar problems have similar solutions. Recently, some attempts at formalizing CBR in a theoretical framework have been made, including work by Hüllermeier who established a link between CBR and the probably approximately correct (PAC) theoretical model of learning in his ‘case-based inference’ (CBI) formulation. In this paper we develop further such probabilistic modelling, framing CBI it as a multi-category classification problem. We use a recently-developed notion of geometric margin of classification to obtain generalization error bounds.

Details DOI

TCS Journal 2014 Journal Article

Learning bounds via sample width for classifiers on finite metric spaces

Martin Anthony
Joel Ratsaby

In a recent paper [M. Anthony, J. Ratsaby, Maximal width learning of binary functions, Theoretical Computer Science 411 (2010) 138–147] the notion of sample width for binary classifiers mapping from the real line was introduced, and it was shown that the performance of such classifiers could be quantified in terms of this quantity. This paper considers how to generalize the notion of sample width so that we can apply it where the classifiers map from some finite metric space. By relating the learning problem to one involving the domination numbers of certain graphs, we obtain generalization error bounds that depend on the sample width and on certain measures of ‘density’ of the underlying metric space. We also discuss how to employ a greedy set-covering heuristic to bound generalization error.

Details DOI

TCS Journal 2010 Journal Article

Maximal width learning of binary functions

Martin Anthony
Joel Ratsaby

This paper concerns learning binary-valued functions defined on R, and investigates how a particular type of ‘regularity’ of hypotheses can be used to obtain better generalization error bounds. We derive error bounds that depend on the sample width (a notion analogous to that of sample margin for real-valued functions). This motivates learning algorithms that seek to maximize sample width.

Details DOI

TCS Journal 2006 Journal Article

Complexity of hyperconcepts

Joel Ratsaby

In machine-learning, maximizing the sample margin can reduce the learning generalization error. Samples on which the target function has a large margin ( γ ) convey more information since they yield more accurate hypotheses. Let X be a finite domain and S denote the set of all samples S ⊆ X of fixed cardinality m. Let H be a class of hypotheses h on X. A hyperconcept h ′ is defined as an indicator function for a set A ⊆ S of all samples on which the corresponding hypothesis h has a margin of at least γ. An estimate on the complexity of the class H ′ of hyperconcepts h ′ is obtained with explicit dependence on γ, the pseudo-dimension of H and m.

Details DOI

I&C Journal 2003 Journal Article

On learning multicategory classification with sample queries

Joel Ratsaby

Consider the pattern recognition problem of learning multicategory classification from a labeled sample, for instance, the problem of learning character recognition where a category corresponds to an alphanumeric letter. The classical theory of pattern recognition assumes labeled examples appear according to the unknown underlying pattern-class conditional probability distributions where the pattern classes are picked randomly according to their a priori probabilities. In this paper we pose the following question: Can the learning accuracy be improved if labeled examples are independently randomly drawn according to the underlying class conditional probability distributions but the pattern classes are chosen not necessarily according to their a priori probabilities? We answer this in the affirmative by showing that there exists a tuning of the sub-sample proportions which minimizes a loss criterion. The tuning is relative to the intrinsic complexity of the Bayes-classifier. As this complexity depends on the underlying probability distributions which are assumed to be unknown, we provide an algorithm which learns the proportions in an on-line manner utilizing sample querying which asymptotically minimizes the criterion. In practice, this algorithm may be used to boost the performance of existing learning classification algorithms by apportioning better sub-sample proportions.

Details DOI

NeurIPS Conference 1997 Conference Paper

An Incremental Nearest Neighbor Algorithm with Queries

Joel Ratsaby

We consider the general problem of learning multi-category classifi(cid: 173) cation from labeled examples. We present experimental results for a nearest neighbor algorithm which actively selects samples from different pattern classes according to a querying rule instead of the a priori class probabilities. The amount of improvement of this query-based approach over the passive batch approach depends on the complexity of the Bayes rule. The principle on which this al(cid: 173) gorithm is based is general enough to be used in any learning algo(cid: 173) rithm which permits a model-selection criterion and for which the error rate of the classifier is calculable in terms of the complexity of the model.

PDF Details