Daphna Weinshall

AAAI Conference 2025 Conference Paper

On Local Overfitting and Forgetting in Deep Neural Networks

• Uri Stern
• Tomer Yaacoby
• Daphna Weinshall

The infrequent occurrence of overfitting in deep neural networks is perplexing: contrary to theoretical expectations, increasing model size often enhances performance in practice. But what if overfitting does occur, though restricted to specific sub-regions of the data space? In this work, we propose a novel score that captures the forgetting rate of deep models on validation data. We posit that this score quantifies local overfitting: a decline in performance confined to certain regions of the data space. We then show empirically that local overfitting occurs regardless of the presence of traditional overfitting. Using the framework of deep over-parametrized linear models, we offer a certain theoretical characterization of forgotten knowledge, and show that it correlates with knowledge forgotten by real deep models. Finally, we devise a new ensemble method that aims to recover forgotten knowledge, relying solely on the training history of a single network. When combined with knowledge distillation, this method will enhance the performance of a trained model without adding inference costs. Extensive empirical evaluations demonstrate the efficacy of our method across multiple datasets, contemporary neural network architectures, and training protocols.

AAAI Conference 2024 Conference Paper

United We Stand: Using Epoch-Wise Agreement of Ensembles to Combat Overfit

• Uri Stern
• Daniel Shwartz
• Daphna Weinshall

Deep neural networks have become the method of choice for solving many classification tasks, largely because they can fit very complex functions defined over raw data. The downside of such powerful learners is the danger of overfit. In this paper, we introduce a novel ensemble classifier for deep networks that effectively overcomes overfitting by combining models generated at specific intermediate epochs during training. Our method allows for the incorporation of useful knowledge obtained by the models during the overfitting phase without deterioration of the general performance, which is usually missed when early stopping is used. To motivate this approach, we begin with the theoretical analysis of a regression model, whose prediction - that the variance among classifiers increases when overfit occurs - is demonstrated empirically in deep networks in common use. Guided by these results, we construct a new ensemble-based prediction method, where the prediction is determined by the class that attains the most consensual prediction throughout the training epochs. Using multiple image and text classification datasets, we show that when regular ensembles suffer from overfit, our method eliminates the harmful reduction in generalization due to overfit, and often even surpasses the performance obtained by early stopping. Our method is easy to implement and can be integrated with any training scheme and architecture, without additional prior knowledge beyond the training set. It is thus a practical and useful tool to overcome overfit.

NeurIPS Conference 2023 Conference Paper

How to Select Which Active Learning Strategy is Best Suited for Your Specific Problem and Budget

• Guy Hacohen
• Daphna Weinshall

In the domain of Active Learning (AL), a learner actively selects which unlabeled examples to seek labels from an oracle, while operating within predefined budget constraints. Importantly, it has been recently shown that distinct query strategies are better suited for different conditions and budgetary constraints. In practice, the determination of the most appropriate AL strategy for a given situation remains an open problem. To tackle this challenge, we propose a practical derivative-based method that dynamically identifies the best strategy for a given budget. Intuitive motivation for our approach is provided by the theoretical analysis of a simplified scenario. We then introduce a method to dynamically select an AL strategy, which takes into account the unique characteristics of the problem and the available budget. Empirical results showcase the effectiveness of our approach across diverse budgets and computer vision tasks.

ICML Conference 2022 Conference Paper

Active Learning on a Budget: Opposite Strategies Suit High and Low Budgets

• Guy Hacohen
• Avihu Dekel
• Daphna Weinshall

Investigating active learning, we focus on the relation between the number of labeled examples (budget size), and suitable querying strategies. Our theoretical analysis shows a behavior reminiscent of phase transition: typical examples are best queried when the budget is low, while unrepresentative examples are best queried when the budget is large. Combined evidence shows that a similar phenomenon occurs in common classification models. Accordingly, we propose TypiClust – a deep active learning strategy suited for low budgets. In a comparative empirical investigation of supervised learning, using a variety of architectures and image datasets, TypiClust outperforms all other active learning strategies in the low-budget regime. Using TypiClust in the semi-supervised framework, performance gets an even more significant boost. In particular, state-of-the-art semi-supervised methods trained on CIFAR-10 with 10 labeled examples selected by TypiClust, reach 93. 2% accuracy – an improvement of 39. 4% over random selection. Code is available at https: //github. com/avihu111/TypiClust.

NeurIPS Conference 2022 Conference Paper

Active Learning Through a Covering Lens

• Ofer Yehuda
• Avihu Dekel
• Guy Hacohen
• Daphna Weinshall

Deep active learning aims to reduce the annotation cost for the training of deep models, which is notoriously data-hungry. Until recently, deep active learning methods were ineffectual in the low-budget regime, where only a small number of examples are annotated. The situation has been alleviated by recent advances in representation and self-supervised learning, which impart the geometry of the data representation with rich information about the points. Taking advantage of this progress, we study the problem of subset selection for annotation through a “covering” lens, proposing ProbCover – a new active learning algorithm for the low budget regime, which seeks to maximize Probability Coverage. We then describe a dual way to view the proposed formulation, from which one can derive strategies suitable for the high budget regime of active learning, related to existing methods like Coreset. We conclude with extensive experiments, evaluating ProbCover in the low-budget regime. We show that our principled active learning strategy improves the state-of-the-art in the low-budget regime in several image recognition benchmarks. This method is especially beneficial in the semi-supervised setting, allowing state-of-the-art semi-supervised methods to match the performance of fully supervised methods, while using much fewer labels nonetheless. Code is available at https: //github. com/avihu111/TypiClust.

JMLR Journal 2022 Journal Article

Principal Components Bias in Over-parameterized Linear Models, and its Manifestation in Deep Neural Networks

• Guy Hacohen
• Daphna Weinshall

Recent work suggests that convolutional neural networks of different architectures learn to classify images in the same order. To understand this phenomenon, we revisit the over-parametrized deep linear network model. Our analysis reveals that, when the hidden layers are wide enough, the convergence rate of this model's parameters is exponentially faster along the directions of the larger principal components of the data, at a rate governed by the corresponding singular values. We term this convergence pattern the Principal Components bias (PC-bias). Empirically, we show how the PC-bias streamlines the order of learning of both linear and non-linear networks, more prominently at earlier stages of learning. We then compare our results to the simplicity bias, showing that both biases can be seen independently, and affect the order of learning in different ways. Finally, we discuss how the PC-bias may explain some benefits of early stopping and its connection to PCA, and why deep networks converge more slowly with random labels. [abs] [ pdf ][ bib ] &copy JMLR 2022. ( edit, beta )

ICML Conference 2020 Conference Paper

Let's Agree to Agree: Neural Networks Share Classification Order on Real Datasets

• Guy Hacohen
• Leshem Choshen
• Daphna Weinshall

We report a series of robust empirical observations, demonstrating that deep Neural Networks learn the examples in both the training and test sets in a similar order. This phenomenon is observed in all the commonly used benchmarks we evaluated, including many image classification benchmarks, and one text classification benchmark. While this phenomenon is strongest for models of the same architecture, it also crosses architectural boundaries – models of different architectures start by learning the same examples, after which the more powerful model may continue to learn additional examples. We further show that this pattern of results reflects the interplay between the way neural networks learn benchmark datasets. Specifically, when fixing the architecture, we describe synthetic datasets for which this pattern is no longer observed. When fixing the dataset, we show that other learning paradigms may learn the data in a different order. We hypothesize that our results reflect how neural networks discover structure in natural datasets.

JMLR Journal 2020 Journal Article

Theory of Curriculum Learning, with Convex Loss Functions

• Daphna Weinshall
• Dan Amir

Curriculum Learning is motivated by human cognition, where teaching often involves gradually exposing the learner to examples in a meaningful order, from easy to hard. Although methods based on this concept have been empirically shown to improve performance of several machine learning algorithms, no theoretical analysis has been provided even for simple cases. To address this shortfall, we start by formulating an ideal definition of difficulty score - the loss of the optimal hypothesis at a given datapoint. We analyze the possible contribution of curriculum learning based on this score in two convex problems - linear regression, and binary classification by hinge loss minimization. We show that in both cases, the convergence rate of SGD optimization decreases monotonically with the difficulty score, in accordance with earlier empirical results. We also prove that when the difficulty score is fixed, the convergence rate of SGD optimization is monotonically increasing with respect to the loss of the current hypothesis at each point. We discuss how these results settle some confusion in the literature where two apparently opposing heuristics are reported to improve performance: curriculum learning in which easier points are given priority, vs hard data mining where the more difficult points are sought out. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

ICML Conference 2019 Conference Paper

On The Power of Curriculum Learning in Training Deep Networks

• Guy Hacohen
• Daphna Weinshall

Training neural networks is traditionally done by providing a sequence of random mini-batches sampled uniformly from the entire training data. In this work, we analyze the effect of curriculum learning, which involves the non-uniform sampling of mini-batches, on the training of deep networks, and specifically CNNs trained for image recognition. To employ curriculum learning, the training algorithm must resolve 2 problems: (i) sort the training examples by difficulty; (ii) compute a series of mini-batches that exhibit an increasing level of difficulty. We address challenge (i) using two methods: transfer learning from some competitive “teacher" network, and bootstrapping. In our empirical evaluation, both methods show similar benefits in terms of increased learning speed and improved final performance on test data. We address challenge (ii) by investigating different pacing functions to guide the sampling. The empirical investigation includes a variety of network architectures, using images from CIFAR-10, CIFAR-100 and subsets of ImageNet. We conclude with a novel theoretical analysis of curriculum learning, where we show how it effectively modifies the optimization landscape. We then define the concept of an ideal curriculum, and show that under mild conditions it does not change the corresponding global minimum of the optimization function.

ICML Conference 2018 Conference Paper

Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networks

• Daphna Weinshall
• Gad Cohen
• Dan Amir

We provide theoretical investigation of curriculum learning in the context of stochastic gradient descent when optimizing the convex linear regression loss. We prove that the rate of convergence of an ideal curriculum learning method is monotonically increasing with the difficulty of the examples. Moreover, among all equally difficult points, convergence is faster when using points which incur higher loss with respect to the current hypothesis. We then analyze curriculum learning in the context of training a CNN. We describe a method which infers the curriculum by way of transfer learning from another network, pre-trained on a different task. While this approach can only approximate the ideal curriculum, we observe empirically similar behavior to the one predicted by the theory, namely, a significant boost in convergence speed at the beginning of training. When the task is made more difficult, improvement in generalization performance is also observed. Finally, curriculum learning exhibits robustness against unfavorable conditions such as excessive regularization.

ICML Conference 2013 Conference Paper

Hierarchical Regularization Cascade for Joint Learning

• Alon Zweig
• Daphna Weinshall

As the sheer volume of available benchmark datasets increases, the problem of joint learning of classifiers and knowledge-transfer between classifiers, becomes more and more relevant. We present a hierarchical approach which exploits information sharing among different classification tasks, in multi-task and multi-class settings. It engages a top-down iterative method, which begins by posing an optimization problem with an incentive for large scale sharing among all classes. This incentive to share is gradually decreased, until there is no sharing and all tasks are considered separately. The method therefore exploits different levels of sharing within a given group of related tasks, without having to make hard decisions about the grouping of tasks. In order to deal with large scale problems, with many tasks and many classes, we extend our batch approach to an online setting and provide regret analysis of the algorithm. We tested our approach extensively on synthetic and real datasets, showing significant improvement over baseline and state-of-the-art methods.

ICML Conference 2013 Conference Paper

LDA Topic Model with Soft Assignment of Descriptors to Words

• Daphna Weinshall
• Gal Levi
• Dmitri Hanukaev

The LDA topic model is being used to model corpora of documents that can be represented by bags of words. Here we extend the LDA model to deal with documents that are represented more naturally by bags of continuous descriptors. Given a finite dictionary of words which are generative models of descriptors, our extended LDA model allows for the soft assignment of descriptors to (many) dictionary words. We derive variational inference and parameter estimation procedures for the extended model, which closely resemble those obtained for the original model, with two important differences: First, the histogram of word counts is replaced by a histogram of pseudo word counts, or sums of responsibilities over all descriptors. Second, parameter estimation now depends on the average covariance matrix between these pseudo-counts, reflecting the fact that with soft assignment words are not independent. We use this approach to address novelty detection, where we seek to identify video events with low posterior probability. Video events are described by a generative dynamic texture model, from which we naturally derive a dictionary of generative words. Using a benchmark dataset for novelty detection, we show a very significant improvement in the detection of novel events when using our extended LDA model with soft assignment to words as against hard assignment (the original model), achieving state of the art novelty detection results.

ICML Conference 2013 Conference Paper

Modeling Musical Influence with Topic Models

• Uri Shalit
• Daphna Weinshall
• Gal Chechik

The role of musical influence has long been debated by scholars and critics in the humanities, but never in a data-driven way. In this work we approach the question of influence by applying topic-modeling tools (Blei & Lafferty, 2006; Gerrish & Blei, 2010) to a dataset of 24941 songs by 9222 artists, from the years 1922 to 2010. We find the models to be significantly correlated with a human-curated influence measure, and to clearly outperform a baseline method. Further using the learned model to study properties of influence, we find that musical influence and musical innovation are not monotonically correlated. However, we do find that the most influential songs were more innovative during two time periods: the early 1970’s and the mid 1990’s.

JMLR Journal 2012 Journal Article

Online Learning in the Embedded Manifold of Low-rank Matrices

• Uri Shalit
• Daphna Weinshall
• Gal Chechik

When learning models that are represented in matrix forms, enforcing a low-rank constraint can dramatically improve the memory and run time complexity, while providing a natural regularization of the model. However, naive approaches to minimizing functions over the set of low-rank matrices are either prohibitively time consuming (repeated singular value decomposition of the matrix) or numerically unstable (optimizing a factored representation of the low-rank matrix). We build on recent advances in optimization over manifolds, and describe an iterative online learning procedure, consisting of a gradient step, followed by a second-order retraction back to the manifold. While the ideal retraction is costly to compute, and so is the projection operator that approximates it, we describe another retraction that can be computed efficiently. It has run time and memory complexity of O ( (n+m)k ) for a rank- k matrix of dimension m X n, when using an online procedure with rank-one gradients. We use this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. LORETA improves the mean average precision over a passive-aggressive approach in a factorized model, and also improves over a full model trained on pre-selected features using the same memory requirements. We further adapt LORETA to learn positive semi-definite low-rank matrices, providing an online algorithm for low-rank metric learning. LORETA also shows consistent improvement over standard weakly supervised methods in a large (1600 classes and 1 million images, using ImageNet ) multi-label image classification task. [abs] [ pdf ][ bib ] &copy JMLR 2012. ( edit, beta )

YNIMG Journal 2010 Journal Article

Differential category learning processes: The neural basis of comparison-based learning and induction

• Rubi Hammer
• André Brechmann
• Frank Ohl
• Daphna Weinshall
• Shaul Hochstein

Findings from numerous studies suggest that multiple neural systems are involved in category learning. Specifically, it is often argued that acquiring a representation of different category structures (e. g. , rule-based vs. prototype-based representation) involves different computational challenges, which are resolved by different neural circuitries in the human brain. Here we present an alternative approach for studying neural mechanisms of category learning: We refer to the idea that any category learning task involves mapping common features shared by same-category members, distinctive features discriminating members of different categories, or both. We argue that since these processes are psychologically and computationally distinct, they differ in their usability for category learning. Our participants learned novel categories of complex visual stimuli by comparing either pairs of objects from the same novel category or pairs of objects from different categories. Object pairs were chosen so that the objective amount of information they contained was identical in the two category learning conditions, equally enabling learning the predefined objective category structure. We find that the neural circuitry involved in detecting important between-categories differences is associated mainly with the dorsal striatum (bilaterally) and the right hippocampus. On the other hand, mapping within-category similarities and differences is restricted to high-level visual brain areas. We suggest that multiple neural mechanisms are involved in category learning enabling us to face different computational challenges associated with different basic types of induction processes that differ in their usability for learning different category structures.

NeurIPS Conference 2010 Conference Paper

Online Learning in The Manifold of Low-Rank Matrices

• Uri Shalit
• Daphna Weinshall
• Gal Chechik

When learning models that are represented in matrix forms, enforcing a low-rank constraint can dramatically improve the memory and run time complexity, while providing a natural regularization of the model. However, naive approaches for minimizing functions over the set of low-rank matrices are either prohibitively time consuming (repeated singular value decomposition of the matrix) or numerically unstable (optimizing a factored representation of the low rank matrix). We build on recent advances in optimization over manifolds, and describe an iterative online learning procedure, consisting of a gradient step, followed by a second-order retraction back to the manifold. While the ideal retraction is hard to compute, and so is the projection operator that approximates it, we describe another second-order retraction that can be computed efficiently, with run time and memory complexity of O((n+m)k) for a rank-k matrix of dimension m x n, given rank one gradients. We use this algorithm, LORETA, to learn a matrix-form similarity measure over pairs of documents represented as high dimensional vectors. LORETA improves the mean average precision over a passive- aggressive approach in a factorized model, and also improves over a full model trained over pre-selected features using the same memory requirements. LORETA also showed consistent improvement over standard methods in a large (1600 classes) multi-label image classification task.

NeurIPS Conference 2008 Conference Paper

Beyond Novelty Detection: Incongruent Events, when General and Specific Classifiers Disagree

• Daphna Weinshall
• Hynek Hermansky
• Alon Zweig
• Jie Luo
• Holly Jimison
• Frank Ohl
• Misha Pavel

Unexpected stimuli are a challenge to any machine learning algorithm. Here we identify distinct types of unexpected events, focusing on 'incongruent events' - when 'general level' and 'specific level' classifiers give conflicting predictions. We define a formal framework for the representation and processing of incongruent events: starting from the notion of label hierarchy, we show how partial order on labels can be deduced from such hierarchies. For each event, we compute its probability in different ways, based on adjacent levels (according to the partial order) in the label hierarchy. An incongruent event is an event where the probability computed based on some more specific level (in accordance with the partial order) is much smaller than the probability computed based on some more general level, leading to conflicting predictions. We derive algorithms to detect incongruent events from different types of hierarchies, corresponding to class membership or part membership. Respectively, we show promising results with real data on two specific problems: Out Of Vocabulary words in speech recognition, and the identification of a new sub-class (e. g. , the face of a new individual) in audio-visual facial object recognition.

ICML Conference 2007 Conference Paper

Learning distance function by coding similarity

• Aharon Bar-Hillel
• Daphna Weinshall

ICML Conference 2006 Conference Paper

Learning a kernel function for classification with small training samples

• Tomer Hertz
• Aharon Bar-Hillel
• Daphna Weinshall

NeurIPS Conference 2006 Conference Paper

Subordinate class recognition using relational object models

• Aharon Hillel
• Daphna Weinshall

We address the problem of sub-ordinate class recognition, like the distinction between different types of motorcycles. Our approach is motivated by observations from cognitive psychology, which identify parts as the defining component of basic level categories (like motorcycles), while sub-ordinate categories are more often defined by part properties (like 'jagged wheels'). Accordingly, we suggest a two-stage algorithm: First, a relational part based object model is learnt using unsegmented object images from the inclusive class (e. g. , motorcycles in general). The model is then used to build a class-specific vector representation for images, where each entry corresponds to a model's part. In the second stage we train a standard discriminative classifier to classify subclass instances (e. g. , cross motorcycles) based on the class-specific vector representation. We describe extensive experimental results with several subclasses. The proposed algorithm typically gives better results than a competing one-step algorithm, or a two stage algorithm where classification is based on a model of the sub-ordinate class.

NeurIPS Conference 2005 Conference Paper

Analyzing Auditory Neurons by Learning Distance Functions

• Inna Weiner
• Tomer Hertz
• Israel Nelken
• Daphna Weinshall

We present a novel approach to the characterization of complex sensory neurons. One of the main goals of characterizing sensory neurons is to characterize dimensions in stimulus space to which the neurons are highly sensitive (causing large gradients in the neural responses) or al- ternatively dimensions in stimulus space to which the neuronal response are invariant (defining iso-response manifolds). We formulate this prob- lem as that of learning a geometry on stimulus space that is compatible with the neural responses: the distance between stimuli should be large when the responses they evoke are very different, and small when the re- sponses they evoke are similar. Here we show how to successfully train such distance functions using rather limited amount of information. The data consisted of the responses of neurons in primary auditory cortex (A1) of anesthetized cats to 32 stimuli derived from natural sounds. For each neuron, a subset of all pairs of stimuli was selected such that the responses of the two stimuli in a pair were either very similar or very dissimilar. The distance function was trained to fit these constraints. The resulting distance functions generalized to predict the distances between the responses of a test stimulus and the trained stimuli.

JMLR Journal 2005 Journal Article

Learning a Mahalanobis Metric from Equivalence Constraints

• Aharon Bar-Hillel
• Tomer Hertz
• Noam Shental
• Daphna Weinshall

Many learning algorithms use a metric defined over the input space as a principal tool, and their performance critically depends on the quality of this metric. We address the problem of learning metrics using side-information in the form of equivalence constraints. Unlike labels, we demonstrate that this type of side-information can sometimes be automatically obtained without the need of human intervention. We show how such side-information can be used to modify the representation of the data, leading to improved clustering and classification. Specifically, we present the Relevant Component Analysis (RCA) algorithm, which is a simple and efficient algorithm for learning a Mahalanobis metric. We show that RCA is the solution of an interesting optimization problem, founded on an information theoretic basis. If dimensionality reduction is allowed within RCA, we show that it is optimally accomplished by a version of Fisher's linear discriminant that uses constraints. Moreover, under certain Gaussian assumptions, RCA can be viewed as a Maximum Likelihood estimation of the within class covariance matrix. We conclude with extensive empirical evaluations of RCA, showing its advantage over alternative methods. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

ICML Conference 2004 Conference Paper

Boosting margin based distance functions for clustering

• Tomer Hertz
• Aharon Bar-Hillel
• Daphna Weinshall

NeurIPS Conference 2003 Conference Paper

Computing Gaussian Mixture Models with EM Using Equivalence Constraints

• Noam Shental
• Aharon Bar-Hillel
• Tomer Hertz
• Daphna Weinshall

Density estimation with Gaussian Mixture Models is a popular gener- ative technique used also for clustering. We develop a framework to incorporate side information in the form of equivalence constraints into the model estimation procedure. Equivalence constraints are defined on pairs of data points, indicating whether the points arise from the same source (positive constraints) or from different sources (negative con- straints). Such constraints can be gathered automatically in some learn- ing problems, and are a natural form of supervision in others. For the estimation of model parameters we present a closed form EM procedure which handles positive constraints, and a Generalized EM procedure us- ing a Markov net which handles negative constraints. Using publicly available data sets we demonstrate that such side information can lead to considerable improvement in clustering tasks, and that our algorithm is preferable to two other suggested methods using the same type of side information.

ICML Conference 2003 Conference Paper

Learning Distance Functions using Equivalence Relations

• Aharon Bar-Hillel
• Tomer Hertz
• Noam Shental
• Daphna Weinshall

NeurIPS Conference 1998 Conference Paper

A Randomized Algorithm for Pairwise Clustering

• Yoram Gdalyahu
• Daphna Weinshall
• Michael Werman

We present a stochastic clustering algorithm based on pairwise sim(cid: 173) ilarity of datapoints. Our method extends existing deterministic methods, including agglomerative algorithms, min-cut graph algo(cid: 173) rithms, and connected components. Thus it provides a common framework for all these methods. Our graph-based method differs from existing stochastic methods which are based on analogy to physical systems. The stochastic nature of our method makes it more robust against noise, including accidental edges and small spurious clusters. We demonstrate the superiority of our algorithm using an example with 3 spiraling bands and a lot of noise.

NeurIPS Conference 1998 Conference Paper

Classification in Non-Metric Spaces

• Daphna Weinshall
• David Jacobs
• Yoram Gdalyahu

A key question in vision is how to represent our knowledge of previously encountered objects to classify new ones. The answer depends on how we determine the similarity of two objects. Similarity tells us how relevant each previously seen object is in determining the category to which a new object belongs. Here a dichotomy emerges. Complex notions of similar(cid: 173) ity appear necessary for cognitive models and applications, while simple notions of similarity form a tractable basis for current computational ap(cid: 173) proaches to classification. We explore the nature of this dichotomy and why it calls for new approaches to well-studied problems in learning. We begin this process by demonstrating new computational methods for supervised learning that can handle complex notions of similarity. (1) We discuss how to implement parametric met. hods that represent a class by its mean when using non-metric similarity functions; and (2) We review non-parametric methods that we have developed using near(cid: 173) est neighbor classification in non-metric spaces. Point (2), and some of the background of our work have been described in more detail in [8]. 1 Supervised Learning and Non-Metric Distances How can one represent one 's knowledge of previously encountered objects in order to classify new objects? We study this question within the framework of supel vised learning: it is assumed that one is given a number of training objects, each labeled as belonging to a category; one wishes to use this experience to label new test instances of objects. This problem emerges both in the modeling of cognitive processes and in many practical applications. For example, one might want to identify risky applicants for credit based on past experience with clients who have proven to be good or bad credit risks. Our work is motivated by computer vision applications. Most current computational approaches to supervised learning suppose that objects can be thought of as vectors of numbers, or equivalently as points lying in an n(cid: 173) dimensional space. They further suppose that the similarity between objects can be determined from the Euclidean distance between these vectors, or from some other simple metric. This classic notion of similarity as Euclidean or metric distance leads Classification in Non-Metric Spaces 839 to considerable mathematical and computational simplification. However, work in cognitive psychology has challenged such simple notions of sim(cid: 173) ilarity as models of human judgment, while applications frequently employ non(cid: 173) Euclidean distances to measure object similarity. We consider the need for similar(cid: 173) ity measures that are not only non-Euclidean, but that are non-metric. We focus on proposed similarities that violate one requirement of a metric distance, the triangle inequality. This states that if we denote the distance between objects A and B by d(A, B), then: VA, B, C: d(A, B) + d(B, C) ~ d(A, C). Distances violating the triangle inequality must also be non-Euclidean. Data from cognitive psychology has demonstrated that similarity judgments may not be well modeled by Euclidean distances. Tversky [12] has demonstrated in(cid: 173) stances in which similarity judgments may violate the triangle inequality. For ex(cid: 173) ample, close similarity between Jamaica and Cuba and between Cuba and Russia does not imply close similarity between Jamaica and Russia (see also [10]). Non(cid: 173) metric similarity measures are frequently employed for practical reasons, too (cf. [5]). In part, work in robust statistics [7] has shown that methods that will survive the presence of outliers, which are extraneous pieces of information or information containing extreme errors, must employ non-Euclidean distances that in fact violate the triangle inequality; related insights have spurred the widespread use of robust methods in computer vision (reviewed in [5] and [9]). We are interested in handling a wide range of non-metric distance functions, includ(cid: 173) ing those that are so complex that they must be treated as a black box. However, to be concrete, we will focus here on two simple examples of such distances: median distance: This distance assumes that objects are representable as a set of features whose individual differences can be measured, so that the difference between two objects is representable as a vector: J = (d1, d2, .. . dn ). The median distance between the two objects is just the median value in this vector. Similarly, one can define a k-median distance by choosing the k'th lowest element in this list. k(cid: 173) median distances are often used in applications (cf. [9]), because they are unaffected by the exact values of the most extreme differences between the objects. Only these features that are most similar determine its value. The k-median distance can violate the triangle inequality to an arbitrary degree (i. e. , there are no constraints on the pairwise distances between three points). robust non-metric LP distances: Given a difference vector J, an LP distance has the form: (1) and is non-metric for p < 1. Figure 1 illustrates why these distances present significant new challenges in su(cid: 173) pervised learning. Suppose that given some datapoints (two in Fig. 1), we wish to classify each new point as coming from the same category as its nearest neighbor. Then we need to determine the Voronoi diagram generated by our data: a division of the plane into regions in which the points all have the same nearest neighbor. Fig. 1 shows how the Voronoi diagram changes with the function used to compute the distance between datapoints; the non-metric diagrams (rightmost three pictures in Fig. 1) are more complex and more likely to make non-intuitive predictions. In fact, very little is known about the computation of non-metric Voronoi diagrams. We now describe new parametric methods for supervised learning with non-metric 840 D. Weins hall, D. W Jacobs and Y. Gdalyahu Figure 1: The Voronoi diagram for two points using, from left to right, p-distances with p = 2 (Euclidean), p = 1 ( Manhattan, which is still metric), the non-metric distances arising from p = 0. 5, p = 0. 2, and the min (I-median) distance. The min distance in 2-D illustrates the behavior of the other median distances in higher dimensions. The region of the plane closer to one point is shown in black, and closer to the other in white. distances, and review non-parametric methods that we described in [8]. 2 Parametric methods: what should replace the mean Parametric methods typically represent objects as vectors in a high-dimensional space, and represent classes and the boundaries between them in this space us(cid: 173) ing geometric constructions or probability distributions with a limited number of parameters. One can attempt to extend these techniques to specific non-metric distances, such as the median distance, or non-metric LP distances. We discuss the example of the mean of a class below. One can also redefine geometric ob(cid: 173) jects such as linear separators, for specific non-metric distances. However, existing algorithms for finding such objects in Euclidean spaces will no longer be directly suitable, nor will theoretical results about such representations hold. Many prob(cid: 173) lems are therefore open in determining how to best apply parametric supervised learning techniques to specific non-metric distances. 1 We analyze k-means clustering where each class is represented by its average mem(cid: 173) ber; new elements are then classified according to which of these prototypical exam(cid: 173) ples is nearest. In Euclidean space, the mean is the point q whose sum of squared distances to all the class members {qdr=l - (2: ~1 d(ij, qi)2)2 - is minimized. Suppose now that our data come from a vector space where the correct distance is the LP distance from (1). Using the natural extension of the above definition, we should represent each class by the point ij whose sum of distances to all the class members - (2: ~=1 d(ij, qi)P) p - is minimal. It is now possible to show (proof is omitted) that for p < 1 (the non-metric cases), the exact value of every feature of the representative point ij must have already appeared in at least one element in the class. Moreover, the value of these features can be determined separately with complexity O(n 2 ), and total complexity of O(dn 2 ) given d features. ij is therefore determined by a mixture of up to d exemplars, where d is the dimension of the vector space. Thus there are efficient algorithms for finding the "mean" element of a class, even using certain non-metric distances. 1 We will illustrate these results with a concrete example using the corel database, a commercial database of images pre-labeled by categories (such as "lions"), where non-metric distance functions have proven effective in determining the similarity of images [1]. The corel database is very large, making the use of prototypes desirable. We represent each image using a vector of 11 numbers describing general image properties, such as color histograms, as described in [1]. We consider the Euclidean Classification in Non-Metric Spaces 841 and L0 5 distances, and their corresponding prototypes: the mean and the LO. 5_ prototype computed according to the result above. Given the first 45 classes, each containing 100 images, we found their corresponding prototypes; we then computed the percentage of images in each class that are closest to their own prototype, using either the Euclidean or the L 0. 5 distance and one of the two prototypes. The results are the following: mean d existing features

NeurIPS Conference 1998 Conference Paper

Mechanisms of Generalization in Perceptual Learning

• Zili Liu
• Daphna Weinshall

The learning of many visual perceptual tasks has been shown to be specific to practiced stimuli, while new stimuli require re-Iearning from scratch. Here we demonstrate generalization using a novel paradigm in motion discrimination where learning has been previ(cid: 173) ously shown to be specific. We trained subjects to discriminate the directions of moving dots, and verified the previous results that learning does not transfer from the trained direction to a new one. However, by tracking the subjects' performance across time in the new direction, we found that their rate of learning doubled. Therefore, learning generalized in a task previously considered too difficult for generalization. We also replicated, in the second ex(cid: 173) periment, transfer following training with "easy" stimuli. The specificity of perceptual learning and the dichotomy between learning of "easy" vs. "difficult" tasks were hypothesized to involve different learning processes, operating at different visual cortical areas. Here we show how to interpret these results in terms of signal detection theory. With the assumption of limited computational resources, we obtain the observed phenomena - direct transfer and change of learning rate - for increasing levels of task 'difficulty. It appears that human generalization concurs with the expected behavior of a generic discrimination system.

NeurIPS Conference 1990 Conference Paper

Qualitative structure from motion

• Daphna Weinshall

Exact structure from motion is an ill-posed computation and therefore very sensitive to noise. In this work I describe how a qualitative shape representation, based on the sign of the Gaussian curvature, can be com(cid: 173) puted directly from motion disparities, without the computation of an exact depth map or the directions of surface normals. I show that humans can judge the curvature sense of three points undergoing 3D motion from two, three and four views with success rate significantly above chance. A simple RBF net has been trained to perform the same task.

NeurIPS Conference 1989 Conference Paper

A self-organizing multiple-view representation of 3D objects

• Daphna Weinshall
• Shimon Edelman
• Heinrich Bülthoff

We demonstrate the ability of a two-layer network of thresholded summation units to support representation of 3D objects in which several distinct 2D views are stored for ea. ch object. Using unsu(cid: 173) pervised Hebbian relaxation, the network learned to recognize ten objects from different viewpoints. The training process led to the emergence of compact representations of the specific input views. When tested on novel views of the same objects, the network ex(cid: 173) hibited a substantial generalization capability. In simulated psy(cid: 173) chophysical experiments, the network's behavior was qualitatively similar to that of human subjects. 1 Background Model-based object recognition involves, by definition, a compa. rison between the input image and models of different objects that are internal to the recognition system. The form in which these models are best stored depends on the kind of information available in the input, and on the trade-off between the amount of memory allocated for the storage and the degree of sophistication required of the recognition process. In computer vision, a distinction can be made between representation schemes that use 3D object-centered coordinate systems and schemes that store viewpoint-specific information such as 2D views of objects. In principle, storing enough 2D views would A Self-Organizing Multiple-View Representation of 3D Objects 275 allow the system to use simple recognition techniques such as template matching. If only a few views of each object are remembered, the system must have the capa(cid: 173) bility to normalize the appearance of an input object, by carrying out appropriate geometrical transformations, before it can be directly compared to the stored rep(cid: 173) resen tat ions. What representation strategy is employed by the human visual system? The notion that objects are represented in viewpoint-dependent fashion is supported by the finding that commonplace objects are more readily recognized from certain so-called canonical vantage points than from other, random viewpoints (Palmer et al. 1981). Namely, canonical views are identified more quickly (and more accurately) than others, with response times decreasing monotonically with increasing subjective goodness. ! The monotonic increase in the recognition latency with misorientation of the object relative to a canonical view prompts the interpretation of the recognition process in terms of a mechanism related to mental rotation. In the classical mental rotation task (see Shepard & Cooper 1982), the subject is required to decide whether two simultaneously presented images are two views of the same 3D object. The average latency of correct response in this task is linearly dependent on the difference in the 3D attitude of the object in the two images. This dependence is commonly accounted for by postulating a process that attempts to rotate the 3D shapes per(cid: 173) ceived in the two images into congruence before making the identity decision. The rotation process is sometimes claimed to be analog, in the sense that the represen(cid: 173) tation of the object appears to pass through intermediate orientation stages as the rotation progresses (Shepard & Cooper 1982). Psychological findings seem to support the involvement of some kind of mental rotation in recognition by demonstrating the dependence of recognition latency for an unfamiliar view of an object on the distance to its closest familiar view. There is, however, an important qualification. Practice with specific objects appears to cause this strategy to be abandoned in favor of a more memory-intensive, less time(cid: 173) consuming direct comparison strategy. Under direct comparison, many views of the objects are stored and recognition proceeds in essentially constant time, provided that the presented views are sufficiently close to one of the stored views (Tarr & Pinker 1989, Edelman et al. 1989). From the preceding outline, it appears that a faithful model of object representa(cid: 173) tion in the human visual system should provide both for the ability to "rotate" 3D objects and for the fast direct-comparison strategy that supersedes mental ro(cid: 173) tation for highly familiar objects. Surprisingly, it turns out that mental rotation in recognition can be replicated by a self-organizing memory-intensive model based on direct comparison. The rest of the present paper describes such a model, called CLF (conjunctions of localized features; see Edelman & Weins hall 1989). 1 Canonical viewl of objects can be reliably identified in lubjective judgement al well as in recognition talb. For example, when alked to form a mental image of an object, people Ulually imagine it as leen &om a canonical perspective. 276 Weinshall, Edelman and Bulthoff INPUT (feature) LAYER