Tomaso Poggio

NeurIPS Conference 2025 Conference Paper

Training the Untrainable: Introducing Inductive Bias via Representational Alignment

• Vighnesh Subramaniam
• David Mayo
• Colin Conwell
• Tomaso Poggio
• Boris Katz
• Brian Cheung
• Andrei Barbu

We demonstrate that architectures which traditionally are considered to be ill-suited for a task can be trained using inductive biases from another architecture. We call a network untrainable when it overfits, underfits, or converges to poor results even when tuning their hyperparameters. For example, fully connected networks overfit on object recognition while deep convolutional networks without residual connections underfit. The traditional answer is to change the architecture to impose some inductive bias, although the nature of that bias is unknown. We introduce guidance, where a guide network steers a target network using a neural distance function. The target minimizes its task loss plus a layerwise representational similarity against the frozen guide. If the guide is trained, this transfers over the architectural prior and knowledge of the guide to the target. If the guide is untrained, this transfers over only part of the architectural prior of the guide. We show that guidance prevents FCN overfitting on ImageNet, narrows the vanilla RNN–Transformer gap, boosts plain CNNs toward ResNet accuracy, and aids Transformers on RNN-favored tasks. We further identify that guidance-driven initialization alone can mitigate FCN overfitting. Our method provides a mathematical tool to investigate priors and architectures, and in the long term, could automate architecture design.

NeurIPS Conference 2024 Conference Paper

On the Power of Decision Trees in Auto-Regressive Language Modeling

• Yulu Gan
• Tomer Galanti
• Tomaso Poggio
• Eran Malach

Originally proposed for handling time series data, Auto-regressive Decision Trees (ARDTs) have not yet been explored for language modeling. This paper delves into both the theoretical and practical applications of ARDTs in this new context. We theoretically demonstrate that ARDTs can compute complex functions, such as simulating automata, Turing machines, and sparse circuits, by leveraging "chain-of-thought" computations. Our analysis provides bounds on the size, depth, and computational efficiency of ARDTs, highlighting their surprising computational power. Empirically, we train ARDTs on simple language generation tasks, showing that they can learn to generate coherent and grammatically correct text on par with a smaller Transformer model. Additionally, we show that ARDTs can be used on top of transformer representations to solve complex reasoning tasks. This research reveals the unique computational abilities of ARDTs, aiming to broaden the architectural diversity in language model development.

NeurIPS Conference 2023 Conference Paper

Norm-based Generalization Bounds for Sparse Neural Networks

• Tomer Galanti
• Mengjia Xu
• Liane Galanti
• Tomaso Poggio

In this paper, we derive norm-based generalization bounds for sparse ReLU neural networks, including convolutional neural networks. These bounds differ from previous ones because they consider the sparse structure of the neural network architecture and the norms of the convolutional filters, rather than the norms of the (Toeplitz) matrices associated with the convolutional layers. Theoretically, we demonstrate that these bounds are significantly tighter than standard norm-based generalization bounds. Empirically, they offer relatively tight estimations of generalization for various simple classification problems. Collectively, these findings suggest that the sparsity of the underlying target function and the model's architecture plays a crucial role in the success of deep learning.

NeurIPS Conference 2020 Conference Paper

Biologically Inspired Mechanisms for Adversarial Robustness

• Manish Reddy Vuyyuru
• Andrzej Banburski
• Nishka Pant
• Tomaso Poggio

A convolutional neural network strongly robust to adversarial perturbations at reasonable computational and performance cost has not yet been demonstrated. The primate visual ventral stream seems to be robust to small perturbations in visual stimuli but the underlying mechanisms that give rise to this robust perception are not understood. In this work, we investigate the role of two biologically plausible mechanisms in adversarial robustness. We demonstrate that the non-uniform sampling performed by the primate retina and the presence of multiple receptive fields with a range of receptive field sizes at each eccentricity improve the robustness of neural networks to small adversarial perturbations. We verify that these two mechanisms do not suffer from gradient obfuscation and study their contribution to adversarial robustness through ablation studies.

NeurIPS Conference 2017 Conference Paper

Do Deep Neural Networks Suffer from Crowding?

• Anna Volokitin
• Gemma Roig
• Tomaso Poggio

Crowding is a visual effect suffered by humans, in which an object that can be recognized in isolation can no longer be recognized when other objects, called flankers, are placed close to it. In this work, we study the effect of crowding in artificial Deep Neural Networks (DNNs) for object recognition. We analyze both deep convolutional neural networks (DCNNs) as well as an extension of DCNNs that are multi-scale and that change the receptive field size of the convolution filters with their position in the image. The latter networks, that we call eccentricity-dependent, have been proposed for modeling the feedforward path of the primate visual cortex. Our results reveal that the eccentricity-dependent model, trained on target objects in isolation, can recognize such targets in the presence of flankers, if the targets are near the center of the image, whereas DCNNs cannot. Also, for all tested networks, when trained on targets in isolation, we find that recognition accuracy of the networks decreases the closer the flankers are to the target and the more flankers there are. We find that visual similarity between the target and flankers also plays a role and that pooling in early layers of the network leads to more crowding. Additionally, we show that incorporating flankers into the images of the training set for learning the DNNs does not lead to robustness against configurations not seen at training.

AAAI Conference 2017 Conference Paper

When and Why Are Deep Networks Better Than Shallow Ones?

• Hrushikesh Mhaskar
• Qianli Liao
• Tomaso Poggio

While the universal approximation property holds both for hierarchical and shallow networks, deep networks can approximate the class of compositional functions as well as shallow networks but with exponentially lower number of training parameters and sample complexity. Compositional functions are obtained as a hierarchy of local constituent functions, where “local functions” are functions with low dimensionality. This theorem proves an old conjecture by Bengio on the role of depth in networks, characterizing precisely the conditions under which it holds. It also suggests possible answers to the the puzzle of why high-dimensional deep networks trained on large training sets often do not seem to show overfit.

AAAI Conference 2016 Conference Paper

Holographic Embeddings of Knowledge Graphs

• Maximilian Nickel
• Lorenzo Rosasco
• Tomaso Poggio

Learning embeddings of entities and relations is an efficient and versatile method to perform machine learning on relational data such as knowledge graphs. In this work, we propose holographic embeddings (HOLE) to learn compositional vector space representations of entire knowledge graphs. The proposed method is related to holographic models of associative memory in that it employs circular correlation to create compositional representations. By using correlation as the compositional operator, HOLE can capture rich interactions but simultaneously remains efficient to compute, easy to train, and scalable to very large datasets. Experimentally, we show that holographic embeddings are able to outperform state-ofthe-art methods for link prediction on knowledge graphs and relational learning benchmark datasets.

AAAI Conference 2016 Conference Paper

How Important Is Weight Symmetry in Backpropagation?

• Qianli Liao
• Joel Leibo
• Tomaso Poggio

Gradient backpropagation (BP) requires symmetric feedforward and feedback connections—the same weights must be used for forward and backward passes. This “weight transport problem” (Grossberg 1987) is thought to be one of the main reasons to doubt BP’s biologically plausibility. Using 15 different classification datasets, we systematically investigate to what extent BP really depends on weight symmetry. In a study that turned out to be surprisingly similar in spirit to Lillicrap et al. ’s demonstration (Lillicrap et al. 2014) but orthogonal in its results, our experiments indicate that: (1) the magnitudes of feedback weights do not matter to performance (2) the signs of feedback weights do matter—the more concordant signs between feedforward and their corresponding feedback connections, the better (3) with feedback weights having random magnitudes and 100% concordant signs, we were able to achieve the same or even better performance than SGD. (4) some normalizations/stabilizations are indispensable for such asymmetric BP to work, namely Batch Normalization (BN) (Ioffe and Szegedy 2015) and/or a “Batch Manhattan” (BM) update rule.

TCS Journal 2016 Journal Article

Unsupervised learning of invariant representations

• Fabio Anselmi
• Joel Z. Leibo
• Lorenzo Rosasco
• Jim Mutch
• Andrea Tacchetti
• Tomaso Poggio

The present phase of Machine Learning is characterized by supervised learning algorithms relying on large sets of labeled examples ( n → ∞ ). The next phase is likely to focus on algorithms capable of learning from very few labeled examples ( n → 1 ), like humans seem able to do. We propose an approach to this problem and describe the underlying theory, based on the unsupervised, automatic learning of a “good” representation for supervised learning, characterized by small sample complexity. We consider the case of visual object recognition, though the theory also applies to other domains like speech. The starting point is the conjecture, proved in specific cases, that image representations which are invariant to translation, scaling and other transformations can considerably reduce the sample complexity of learning. We prove that an invariant and selective signature can be computed for each image or image patch: the invariance can be exact in the case of group transformations and approximate under non-group transformations. A module performing filtering and pooling, like the simple and complex cells described by Hubel and Wiesel, can compute such signature. The theory offers novel unsupervised learning algorithms for “deep” architectures for image and speech recognition. We conjecture that the main computational goal of the ventral stream of visual cortex is to provide a hierarchical representation of new objects/images which is invariant to transformations, stable, and selective for recognition—and show how this representation may be continuously learned in an unsupervised way during development and visual experience.

NeurIPS Conference 2015 Conference Paper

Learning with a Wasserstein Loss

• Charlie Frogner
• Chiyuan Zhang
• Hossein Mobahi
• Mauricio Araya
• Tomaso Poggio

Learning to predict multi-label outputs is challenging, but in many problems there is a natural metric on the outputs that can be used to improve predictions. In this paper we develop a loss function for multi-label learning, based on the Wasserstein distance. The Wasserstein distance provides a natural notion of dissimilarity for probability measures. Although optimizing with respect to the exact Wasserstein distance is costly, recent work has described a regularized approximation that is efficiently computed. We describe an efficient learning algorithm based on this regularization, as well as a novel extension of the Wasserstein distance from probability measures to unnormalized measures. We also describe a statistical learning bound for the loss. The Wasserstein loss can encourage smoothness of the predictions with respect to a chosen metric on the output space. We demonstrate this property on a real-data tag prediction problem, using the Yahoo Flickr Creative Commons dataset, outperforming a baseline that doesn't use the metric.

NeurIPS Conference 2015 Conference Paper

Learning with Group Invariant Features: A Kernel Perspective.

• Youssef Mroueh
• Stephen Voinea
• Tomaso Poggio

We analyze in this paper a random feature map based on a theory of invariance (\emph{I-theory}) introduced in \cite{AnselmiLRMTP13}. More specifically, a group invariant signal signature is obtained through cumulative distributions of group-transformed random projections. Our analysis bridges invariant feature learning with kernel methods, as we show that this feature map defines an expected Haar-integration kernel that is invariant to the specified group action. We show how this non-linear random feature map approximates this group invariant kernel uniformly on a set of $N$ points. Moreover, we show that it defines a function space that is dense in the equivalent Invariant Reproducing Kernel Hilbert Space. Finally, we quantify error rates of the convergence of the empirical risk minimization, as well as the reduction in the sample complexity of a learning algorithm using such an invariant representation for signal classification, in a classical supervised learning setting

NeurIPS Conference 2013 Conference Paper

Learning invariant representations and applications to face verification

• Qianli Liao
• Joel Leibo
• Tomaso Poggio

One approach to computer object recognition and modeling the brain's ventral stream involves unsupervised learning of representations that are invariant to common transformations. However, applications of these ideas have usually been limited to 2D affine transformations, e. g. , translation and scaling, since they are easiest to solve via convolution. In accord with a recent theory of transformation-invariance, we propose a model that, while capturing other common convolutional networks as special cases, can also be used with arbitrary identity-preserving transformations. The model's wiring can be learned from videos of transforming objects---or any other grouping of images into sets by their depicted object. Through a series of successively more complex empirical tests, we study the invariance/discriminability properties of this model with respect to different transformations. First, we empirically confirm theoretical predictions for the case of 2D affine transformations. Next, we apply the model to non-affine transformations: as expected, it performs well on face verification tasks requiring invariance to the relatively smooth transformations of 3D rotation-in-depth and changes in illumination direction. Surprisingly, it can also tolerate clutter transformations'' which map an image of a face on one background to an image of the same face on a different background. Motivated by these empirical findings, we tested the same model on face verification benchmark tasks from the computer vision literature: Labeled Faces in the Wild, PubFig and a new dataset we gathered---achieving strong performance in these highly unconstrained cases as well. "

NeurIPS Conference 2013 Conference Paper

Neural representation of action sequences: how far can a simple snippet-matching model take us?

• Cheston Tan
• Jedediah Singer
• Thomas Serre
• David Sheinberg
• Tomaso Poggio

The macaque Superior Temporal Sulcus (STS) is a brain area that receives and integrates inputs from both the ventral and dorsal visual processing streams (thought to specialize in form and motion processing respectively). For the processing of articulated actions, prior work has shown that even a small population of STS neurons contains sufficient information for the decoding of actor invariant to action, action invariant to actor, as well as the specific conjunction of actor and action. This paper addresses two questions. First, what are the invariance properties of individual neural representations (rather than the population representation) in STS? Second, what are the neural encoding mechanisms that can produce such individual neural representations from streams of pixel images? We find that a baseline model, one that simply computes a linear weighted sum of ventral and dorsal responses to short action “snippets”, produces surprisingly good fits to the neural data. Interestingly, even using inputs from a single stream, both actor-invariance and action-invariance can be produced simply by having different linear weights.

NeurIPS Conference 2012 Conference Paper

Learning Manifolds with K-Means and K-Flats

• Guillermo Canas
• Tomaso Poggio
• Lorenzo Rosasco

We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-flats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-flats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-flats, both the results and the mathematical tools are new.

NeurIPS Conference 2012 Conference Paper

Multiclass Learning with Simplex Coding

• Youssef Mroueh
• Tomaso Poggio
• Lorenzo Rosasco
• Jean-jeacques Slotine

In this paper we dicuss a novel framework for multiclass learning, defined by a suitable coding/decoding strategy, namely the simplex coding, that allows to generalize to multiple classes a relaxation approach commonly used in binary classification. In this framework a relaxation error analysis can be developed avoiding constraints on the considered hypotheses class. Moreover, we show that in this setting it is possible to derive the first provably consistent regularized methods with training/tuning complexity which is {\em independent} to the number of classes. Tools from convex analysis are introduced that can be used beyond the scope of this paper.

NeurIPS Conference 2011 Conference Paper

Why The Brain Separates Face Recognition From Object Recognition

• Joel Leibo
• Jim Mutch
• Tomaso Poggio

Many studies have uncovered evidence that visual cortex contains specialized regions involved in processing faces but not other object classes. Recent electrophysiology studies of cells in several of these specialized regions revealed that at least some of these regions are organized in a hierarchical manner with viewpoint-specific cells projecting to downstream viewpoint-invariant identity-specific cells (Freiwald and Tsao 2010). A separate computational line of reasoning leads to the claim that some transformations of visual inputs that preserve viewed object identity are class-specific. In particular, the 2D images evoked by a face undergoing a 3D rotation are not produced by the same image transformation (2D) that would produce the images evoked by an object of another class undergoing the same 3D rotation. However, within the class of faces, knowledge of the image transformation evoked by 3D rotation can be reliably transferred from previously viewed faces to help identify a novel face at a new viewpoint. We show, through computational simulations, that an architecture which applies this method of gaining invariance to class-specific transformations is effective when restricted to faces and fails spectacularly when applied across object classes. We argue here that in order to accomplish viewpoint-invariant face identification from a single example view, visual cortex must separate the circuitry involved in discounting 3D rotations of faces from the generic circuitry involved in processing other objects. The resulting model of the ventral stream of visual cortex is consistent with the recent physiology results showing the hierarchical organization of the face processing network.

NeurIPS Conference 2009 Conference Paper

On Invariance in Hierarchical Models

• Jake Bouvrie
• Lorenzo Rosasco
• Tomaso Poggio

A goal of central importance in the study of hierarchical models for object recognition -- and indeed the visual cortex -- is that of understanding quantitatively the trade-off between invariance and selectivity, and how invariance and discrimination properties contribute towards providing an improved representation useful for learning from data. In this work we provide a general group-theoretic framework for characterizing and understanding invariance in a family of hierarchical models. We show that by taking an algebraic perspective, one can provide a concise set of conditions which must be met to establish invariance, as well as a constructive prescription for meeting those conditions. Analyses in specific cases of particular relevance to computer vision and text processing are given, yielding insight into how and when invariance can be achieved. We find that the minimal sets of transformations intrinsic to the hierarchical model needed to support a particular invariance can be clearly described, thereby encouraging efficient computational implementations.

JMLR Journal 2003 Journal Article

Introduction to the Special Issue on Machine Learning Methods for Text and Images

• Jaz Kandola
• Thomas Hofmann
• Tomaso Poggio
• John Shawe-Taylor

NeurIPS Conference 2001 Conference Paper

Categorization by Learning and Combining Object Parts

• Bernd Heisele
• Thomas Serre
• Massimiliano Pontil
• Thomas Vetter
• Tomaso Poggio

We describe an algorithm for automatically learning discriminative com- ponents of objects with SVM classifiers. It is based on growing image parts by minimizing theoretical bounds on the error probability of an SVM. Component-based face classifiers are then combined in a second stage to yield a hierarchical SVM classifier. Experimental results in face classification show considerable robustness against rotations in depth and suggest performance at significantly better level than other face detection systems. Novel aspects of our approach are: a) an algorithm to learn component-based classification experts and their combination, b) the use of 3-D morphable models for training, and c) a maximum operation on the output of each component classifier which may be relevant for bio- logical models of visual recognition.

NeurIPS Conference 2000 Conference Paper

Feature Selection for SVMs

• Jason Weston
• Sayan Mukherjee
• Olivier Chapelle
• Massimiliano Pontil
• Tomaso Poggio
• Vladimir Vapnik

We introduce a method of feature selection for Support Vector Machines. The method is based upon finding those features which minimize bounds on the leave-one-out error. This search can be efficiently performed via gradient descent. The resulting algorithms are shown to be superior to some standard feature selection algorithms on both toy data and real-life problems of face recognition, pedestrian detection and analyzing DNA micro array data.

NeurIPS Conference 2000 Conference Paper

Incremental and Decremental Support Vector Machine Learning

• Gert Cauwenberghs
• Tomaso Poggio

An on-line recursive algorithm for training support vector machines, one vector at a time, is presented. Adiabatic increments retain the Kuhn(cid: 173) Tucker conditions on all previously seen training data, in a number of steps each computed analytically. The incremental procedure is re(cid: 173) versible, and decremental "unlearning" offers an efficient method to ex(cid: 173) actly evaluate leave-one-out generalization performance. Interpretation of decremental unlearning in feature space sheds light on the relationship between generalization and geometry of the data.

NeurIPS Conference 1997 Conference Paper

Just One View: Invariances in Inferotemporal Cell Tuning

• Maximilian Riesenhuber
• Tomaso Poggio

In macaque inferotemporal cortex (IT), neurons have been found to re(cid: 173) spond selectively to complex shapes while showing broad tuning ("in(cid: 173) variance") with respect to stimulus transformations such as translation and scale changes and a limited tuning to rotation in depth. Training monkeys with novel, paperclip-like objects, Logothetis et al. 9 could in(cid: 173) vestigate whether these invariance properties are due to experience with exhaustively many transformed instances of an object or if there are mech(cid: 173) anisms that allow the cells to show response invariance also to previously unseen instances of that object. They found object-selective cells in an(cid: 173) terior IT which exhibited limited invariance to various transformations after training with single object views. While previous models accounted for the tuning of the cells for rotations in depth and for their selectiv(cid: 173) ity to a specific object relative to a population of distractor objects, 14, 1 the model described here attempts to explain in a biologically plausible way the additional properties of translation and size invariance. Using the same stimuli as in the experiment, we find that model IT neurons exhibit invariance properties which closely parallel those of real neurons. Simulations show that the model is capable of unsupervised learning of view-tuned neurons. We thank Peter Dayan, Marcus Dill, Shimon Edelman, Nikos Logothetis, Jonathan Mumick and Randy O'Reilly for useful discussions and comments. 216

NeurIPS Conference 1996 Conference Paper

3D Object Recognition: A Model of View-Tuned Neurons

• Emanuela Bricolo
• Tomaso Poggio
• Nikos Logothetis

In 1990 Poggio and Edelman proposed a view-based model of ob(cid: 173) ject recognition that accounts for several psychophysical properties of certain recognition tasks. The model predicted the existence of view-tuned and view-invariant units, that were later found by Lo(cid: 173) gothetis et al. (Logothetis et al. , 1995) in IT cortex of monkeys trained with views of specific paperclip objects. The model, how(cid: 173) ever, does not specify the inputs to the view-tuned units and their internal organization. In this paper we propose a model of these view-tuned units that is consistent with physiological data from single cell responses.

NeurIPS Conference 1990 Conference Paper

Extensions of a Theory of Networks for Approximation and Learning: Outliers and Negative Examples

• Federico Girosi
• Tomaso Poggio
• Bruno Caprile

Learning an input-output mapping from a set of examples can be regarded as synthesizing an approximation of a multi-dimensional function. From this point of view, this form of learning is closely related to regularization theory, and we have previously shown (Poggio and Girosi, 1990a, 1990b) the equivalence between reglilari~at. ioll and a. class of three-layer networks that we call regularization networks. In this note, we ext. end the theory by introducing ways of <lealing with t. wo aspect. s of learning: learning in presence of unreliable examples or outliel·s, an<llearning from positive and negative examples.

NeurIPS Conference 1988 Conference Paper

A Network for Image Segmentation Using Color

• Anya Hurlbert
• Tomaso Poggio

We propose a parallel network of simple processors to find color boundaries irrespective of spatial changes in illumi(cid: 173) nation, and to spread uniform colors within marked re-

IJCAI Conference 1987 Conference Paper

An Optimal Scale for Edge Detection

• Da vl Qelger
• Tomaso Poggio

NeurIPS Conference 1987 Conference Paper

Learning a Color Algorithm from Examples

• Tomaso Poggio
• Anya Hurlbert

A lightness algorithm that separates surface reflectance from illumination in a Mondrian world is synthesized automatically from a set of examples, pairs of input (image irradiance) and desired output (surface reflectance). The algorithm, which re(cid: 173) sembles a new lightness algorithm recently proposed by Land, is approximately equiva(cid: 173) lent to filtering the image through a center-surround receptive field in individual chro(cid: 173) matic channels. The synthesizing technique, optimal linear estimation, requires only one assumption, that the operator that transforms input into output is linear. This assumption is true for a certain class of early vision algorithms that may therefore be synthesized in a similar way from examples. Other methods of synthesizing algorithms from examples, or "learning", such as backpropagation, do not yield a significantly dif(cid: 173) ferent or better lightness algorithm in the Mondrian world. The linear estimation and backpropagation techniques both produce simultaneous brightness contrast effects. The problems that a visual system must solve in decoding two-dimensional images into three-dimensional scenes (inverse optics problems) are difficult: the information supplied by an image is not sufficient by itself to specify a unique scene. To reduce the number of possible interpretations of images, visual systems, whether artificial or biological, must make use of natural constraints, assumptions about the physical properties of surfaces and lights. Computational vision scientists have derived effective solutions for some inverse optics problems (such as computing depth from binocular disparity) by determining the appropriate natural constraints and embedding them in algorithms. How might a visual system discover and exploit natural constraints on its own? We address a simpler question: Given only a set of examples of input images and desired output solutions, can a visual system synthesize. or "learn", the algorithm that converts input to output? We find that an algorithm for computing color in a restricted world can be constructed from examples using standard techniques of optimal linear estimation. The computation of color is a prime example of the difficult problems of inverse optics. We do not merely discriminate betwN'n different wavelengths of light; we assign @ American Institute of Physics 1988 623 roughly constant colors to objects even though the light signals they send to our eyes change as the illumination varies across space and chromatic spectrum. The compu(cid: 173) tational goal underlying color constancy seems to be to extract the invariant surface spectral reflectance properties from the image irradiance, in which reflectance and iI-" lumination are mixed 1 • Lightness algorithms 2-8, pioneered by Land, assume that the color of an object can be specified by its lightness, or relative surface reflectance, in each of three inde(cid: 173) pendent chromatic channels, and that lightness is computed in the same way in each channel. Computing color is thereby reduced to extracting surface reflectance from the image irradiance in a single chromatic channel. The image irra. diance, s', is proportional to the product of the illumination inten(cid: 173) sity e' and the surface reflectance r' in that channel: (1 ) This form of the image intensity equation is true for a Lambertian reflectance model, in which the irradiance s' has no specular components, and for appropriately chosen color channels 9. Taking the logarithm of both sides converts it to a sum: s' (x, y) = r' (x, y )e' (x, y). s(x, y) = rex, y) + e(x, y), (2) where s = loges'), r = log(r') and e = log(e'). Given s(x, y) alone, the problem of solving Eq. 2 for r(x, y) is underconstrained. Lightness algorithms constrain the problem by restricting their domain to a world of Mondrians, two-dimensional surfaces covered with patches of random colors2 and by exploiting two constraints in that world: (i) r'(x, y) is unifonn within patches but has sharp discontinuities at edges between patches and (ii) e' (x, y) varies smoothly across the Mondrian. Under these constraints, lightness algorithms can recover a good approximation to r( x, y) and so can recover lightness triplets that label roughly constant colors 10. We ask whether it is possible to synthesize from examples an algorithm that ex· tracts reflectance from image irradiance. and whether the synthesized algorithm will re(cid: 173) semble existing lightness algorithms derived from an explicit analysis of the constraints. We make one assumption, that the operator that transforms irradiance into reflectance is linear. Under that assumption, motivated by considerations discussed later, we use optimal linear estimation techniques to synthesize an operator from examples. The examples are pairs of images: an input image of a Mondrian under illumination that varies smoothly across space and its desired output image that displays the reflectance of the Mondrian without the illumination. The technique finds the linear estimator that best maps input into desired output. in the least squares sense. For computational convenience we use one-dimensional "training vectors" that represent vertical scan lines across the ~londrian images (Fig. 1). We generate many