Given a data matrix, unsupervised column subset selection refers to the problem of identifying a subset of columns that can be used to linearly approximate the original data matrix. This problem has many applications, such as feature selection and representative selection, but solving it optimally is known to be NP-hard. We consider multi-view unsupervised column subset selection, which extends the concept of (single-view) column subset selection to data represented in multiple views or modalities. We introduce a combinatorial search algorithm for this generalized problem. One variant of the algorithm is guaranteed to compute an optimal solution in a setting similar to the classical A* algorithm. Other suboptimal variants, in a setting similar to the weighted A* algorithm, are much faster and provide a solution along with a bound on its quality.

Spectral clustering is a powerful clustering technique. It leverages the spectral properties of graphs to partition data points into meaningful clusters. The most common criterion for evaluating multi-way spectral clustering is NCut. Column Subset Selection is an important optimization technique in the domain of feature selection and dimension reduction which aims to identify a subset of columns of a given data matrix that can be used to approximate the entire matrix. We show that column subset selection can be used to compute spectral clustering and use this to obtain new graph clustering algorithms.

The common criteria for evaluating spectral clustering are NCut and RatioCut. The seemingly unrelated column subset selection (CSS) problem aims to compute a column subset that linearly approximates the entire matrix. A common criterion is the approximation error in the Frobenius norm (ApproxErr). We show that any algorithm for CSS can be viewed as a clustering algorithm that minimizes NCut by applying it to a matrix formed from graph edges. Conversely, any clustering algorithm can be seen as identifying a column subset from that matrix. In both cases, ApproxErr and NCut have the same value. Analogous results hold for RatioCut with a slightly different matrix. Therefore, established results for CSS can be mapped to spectral clustering. We use this to obtain new clustering algorithms, including an optimal one that is similar to A*. This is the first nontrivial clustering algorithm with such an optimality guarantee. A variant of the weighted A* runs much faster and provides bounds on the accuracy. Finally, we use the results from spectral clustering to prove the NP-hardness of CSS from sparse matrices.

Graph spectral clustering is a fundamental technique in data analysis, which utilizes eigenpairs of the Laplacian matrix to partition graph vertices into clusters. However, classical spectral clustering algorithms require eigendecomposition of the Laplacian matrix, which has cubic time complexity. In this work, we describe pass-efficient spectral clustering algorithms that leverage recent advances in randomized eigendecomposition and the structure of the graph vertex-edge matrix. Furthermore, we derive formulas for their efficient implementation. The resulting algorithms have a linear time complexity with respect to the number of vertices and edges and pass over the graph constant times, making them suitable for processing large graphs stored on slow memory. Experiments validate the accuracy and efficiency of the algorithms.

Electrophysiological Source Imaging (ESI) refers to reconstructing the underlying brain source activation from non-invasive Electroencephalography (EEG) and Magnetoencephalography (MEG) measurements on the scalp. Estimating the source locations and their extents is a fundamental tool in clinical and neuroscience applications. However, the estimation is challenging because of the ill-posedness and high coherence in the leadfield matrix as well as the noise in the EEG/MEG data. In this work, we proposed a combinatorial search framework to address the ESI problem with a provable optimality guarantee. Specifically, by exploiting the graph neighborhood information in the brain source space, we converted the ESI problem into a graph search problem and designed a combinatorial search algorithm under the framework of A* to solve it. The proposed algorithm is guaranteed to give an optimal solution to the ESI problem. Experimental results on both synthetic data and real epilepsy EEG data demonstrated that the proposed algorithm could faithfully reconstruct the source activation in the brain.

Outliers negatively affect the accuracy of data analysis. In this paper we are concerned with their influence on the accuracy of Principal Component Analysis (PCA). Algorithms that attempt to detect outliers and remove them from the data prior to applying PCA are sometimes called Robust PCA, or Robust Subspace Recovery algorithms. We propose a new algorithm for outlier detection that combines two ideas. The first is "chunk recursive elimination" that was used effectively to accelerate feature selection, and the second is combinatorial search, in a setting similar to A*. Our main result is showing how to combine these two ideas. One variant of our algorithm is guaranteed to compute an optimal solution according to some natural criteria, but its running time makes it impractical for large datasets. Other variants are much faster and come with provable bounds on sub-optimality. Experimental results show the effectiveness of the proposed approach.

A common task in data analysis is to compute an approximate embedding of the data in a low dimensional subspace. This is used, for example, for dimensionality reduction. Robust Subspace Recovery computes the embedding by ignoring a fraction of the data considered as outliers. Its performance can be evaluated by how accurate the inliers (non-outliers) are represented. We propose a new algorithm that outperforms the current state of the art when the data is dominated by outliers. The main idea is to rank each point by evaluating the change in the global PCA error when that point is considered as an outlier. We show that this lookahead procedure can be implemented efficiently by centered rank-one modifications.

We present a novel edge sparsification approach for semi-supervised learning on undirected and attributed graphs. The main challenge is to retain few edges while minimizing the loss of node classification accuracy. The task can be mathematically formulated as a bi-level optimization problem. We propose to use meta-gradients, which have traditionally been used in meta-learning, to solve the optimization problem, specifically, treating the graph adjacency matrix as hyperparameters to optimize. Experimental results show the effectiveness of the proposed approach. Remarkably, with the resulting sparse and light graph, in many cases the classification accuracy is significantly improved.

A common task in the analysis of data is to compute an approximate embedding of the data in a low-dimensional subspace. The standard algorithm for computing this subspace is the well-known Principal Component Analysis (PCA). PCA can be extended to the case where some data points are viewed as “outliers” that can be ignored, allowing the remaining data points (inliers”) to be more tightly embedded. We develop a new algorithm that detects outliers so that they can be removed prior to applying PCA. The main idea is to rank each point by looking ahead and evaluating the change in the global PCA error if that point is considered as an outlier. Our technical contribution is showing that this lookahead procedure can be implemented efficiently, producing an accurate algorithm with running time not much above the running time of standard PCA algorithms.

We study the approximation of a target matrix in terms of several selected columns of another matrix, sometimes called "a dictionary". This approximation problem arises in various domains, such as signal processing, computer vision, and machine learning. An optimal column selection algorithm for the special case where the target matrix has only one column is known since the 1970's, but most previously proposed column selection algorithms for the general case are greedy. We propose the first nontrivial optimal algorithm for the general case, using a heuristic search setting similar to the classical A* algorithm. We also propose practical sub-optimal algorithms in a setting similar to the classical Weighted A* algorithm. Experimental results show that our sub-optimal algorithms compare favorably with the current state-of-the-art greedy algorithms. They also provide bounds on how close their solutions are to the optimal solution.

Outlier based Robust Principal Component Analysis (RPCA) requires centering of the non-outliers. We show a “bias trick” that automatically centers these non-outliers. Using this bias trick we obtain the first RPCA algorithm that is optimal with respect to centering.

We consider popular dimension reduction techniques that project data on a low dimensional subspace. They include Principal Component Analysis, Column Subset Selection, and Johnson-Lindenstrauss projections. These techniques have been classically used to efficiently compute various approximations. We propose the following three-step procedure for enhancing the accuracy of such approximations: 1. Unknown quantities in the approximation are replaced with random variables. 2. The Maximum Entropy method is applied to infer the most likely probability distribution. 3. Expected values of the random variables are used to compute the enhanced estimates. Our use of the Maximum Entropy method requires knowledge of vector norms that can be easily computed during the dimension reduction. We demonstrate significant enhancements in average accuracy for Euclidean distance and Mahalanobis distance, and improvements in evaluating k-nearest neighbors and k-furthest neighbors by using the enhanced Euclidean distance formula.

The following are two classical approaches to dimensionality reduction: 1. Approximating the data with a small number of features that exist in the data (feature selection). 2. Approximating the data with a small number of arbitrary features (feature extraction). We study a generalization that approximates the data with both selected and extracted features. We show that an optimal solution to this hybrid problem involves a combinatorial search, and cannot be trivially obtained even if one can solve optimally the separate problems of selection and extraction. Our approach that gives optimal and approximate solutions uses a “best first” heuristic search. The algorithm comes with both an a priori and an a posteriori optimality guarantee similar to those that can be obtained for the classical weighted A* algorithm. Experimental results show the effectiveness of the proposed approach.

Classical Principal Component Analysis (PCA) approximates data in terms of projections on a small number of orthogonal vectors. There are simple procedures to efficiently compute various functions of the data from the PCA approximation. The most important function is arguably the Euclidean distance between data items. This can be used, for example, to solve the approximate nearest neighbor problem. We use random variables to model the inherent uncertainty in such approximations, and apply the Maximum Entropy Method to infer the underlying probability distribution. We propose using the expected values of distances between these random variables as improved estimates of the distance. We show experimentally that in most cases results obtained by our method are more accurate than what is obtained by the classical approach. This improves the accuracy of a classical technique that have been used with little change for over 100 years.

We address the problem of approximating a matrix by the linear combination of a column sparse matrix and a low rank matrix. Two variants of a heuristic search algorithm are described. The first produces an optimal solution but may be slow, as these problems are believed to be NP-hard. The second is much faster, but only guarantees a suboptimal solution. The quality of the approximation and the optimality criterion can be specified in terms of unitarily invariant norms.

In standard machine learning and regression setting feature values are used to predict some desired information. The privacy challenge considered here is to prevent an adversary from using available feature values to predict confidential information that one wishes to keep secret. We show that this can sometimes be achieved with almost no effect on the qual- ity of predicting desired information. We describe two algorithms aimed at providing such privacy when the predictors have a linear operator in the first stage. The desired effect can be achieved by zeroing out feature components in the approximate null space of the linear operator.

Principal Component Analysis (PCA) is a classical dimensionality reduction technique that computes a low rank representation of the data. Recent studies have shown how to compute this low rank representation from most of the data, excluding a small amount of outlier data. We describe an algorithm that solves this problem by applying a variant of the A* algorithm to search for the outliers. The results obtained by our algorithm are optimal, and more accurate than the current state of the art. This comes at the cost of running time, which is typically slower than the current state of the art. We also describe a related variant of the A* algorithm that runs much faster and produces a solution that is guaranteed to be near the optimal.

A common technique for reducing the running time of feature selection is to perform it in two stages. In the first stage a fast and simple filter is applied to select good candidates. The number of candidates is further reduced in the second stage by an accurate algorithm that may run significantly slower. It is common to distinguish between supervised and unsupervised feature selection. In the supervised case features are selected for predicting a set of labels. Such label information is not used in the unsupervised case. We describe a general framework that can use an arbitrary off-the-shelf unsupervised algorithm for the second stage. The algorithm is applied to the selection obtained in the first stage weighted appropriately. Our main technical result is the computation of these weights. We show that the weights can be found as the solution to a quadratic optimization problem. The solution is deterministic, and improves on previously published studies that use probabilistic ideas to compute the weights. To the best of our knowledge our approach is the first technique for converting a supervised feature selection problem into an unsupervised problem. Complexity analysis shows that the proposed technique is very fast, can be implemented in a single pass over the data, and can take advantage of data sparsity. Experimental results show its accuracy to be comparable to that of much slower techniques.

Identifying a small number of features that can represent the data is a known problem that comes up in areas such as machine learning, knowledge representation, data mining, and numerical linear algebra. Computing an optimal solution is believed to be NP-hard, and there is extensive work on approximation algorithms. Classic approaches exploit the algebraic structure of the underlying matrix, while more recent approaches use randomization. An entirely different approach that uses the A* heuristic search algorithm to find an optimal solution was recently proposed. Not surprisingly it is limited to effectively selecting only a small number of features. We propose a similar approach related to the Weighted A* algorithm. This gives algorithms that are not guaranteed to find an optimal solution but run much faster than the A* approach, enabling effective selection of many features from large datasets. We demonstrate experimentally that these new algorithms are more accurate than the current state-of-the-art while still being practical. Furthermore, they come with an adjustable guarantee on how different their error may be from the smallest possible (optimal) error. Their accuracy can always be increased at the expense of a longer running time.

Identifying a small number of features that can represent the data is believed to be NP-hard. Previous approaches exploit algebraic structure and use randomization. We propose an algorithm based on ideas similar to the Weighted A* algorithm in heuristic search. Our experiments show this new algorithm to be more accurate than the current state of the art.

Approximating a matrix by a small subset of its columns is a known problem in numerical linear algebra. Algorithms that address this problem have been used in areas which include, among others, sparse approximation, unsupervised feature selection, data mining, and knowledge representation. Such algorithms were investigated since the 1960's, with recent results that use randomization. The problem is believed to be NP-Hard, and to the best of our knowledge there are no previously published algorithms aimed at computing optimal solutions. We show how to model the problem as a graph search, and propose a heuristic based on eigenvalues of related matrices. Applying the A* search strategy with this heuristic is guaranteed to find the optimal solution. Experimental results on common datasets show that the proposed algorithm can effectively select columns from moderate size matrices, typically improving by orders of magnitude the run time of exhaustive search. We also show how to combine the proposed algorithm with other non-optimal (but much faster) algorithms in a ``two stage'' framework, which is guaranteed to improve the accuracy of the other algorithms.

We consider simultaneously approximating all the columns of a data matrix in terms of few selected columns of another matrix that is sometimes called “the dictionary”. The challenge is to determine a small subset of the dictionary columns that can be used to obtain an accurate prediction of the entire data matrix. Previously proposed greedy algorithms for this task compare each data column with all dictionary columns, resulting in algorithms that may be too slow when both the data matrix and the dictionary matrix are large. A recent approach for accelerating the run time requires large amounts of memory to keep temporary values during the run of the algorithm. We propose two new algorithms that can be used even when both the data matrix and the dictionary matrix are large. The first algorithm is exact, with output identical to some previously proposed greedy algorithms. It takes significantly less memory when compared to the current state-of-the-art, and runs much faster when the dictionary matrix is sparse. The second algorithm uses a low rank approximation to the data matrix to further improve the run time. The algorithms use new recursive formulas for computing the greedy selection criterion. The formulas enable decoupling most of the computations related to the data matrix from the computations related to the dictionary matrix.

The goal of unsupervised feature selection is to identify a small number of important features that can represent the data. We propose a new algorithm, a modification of the classical pivoted QR algorithm of Businger and Golub, that requires a small number of passes over the data. The improvements are based on two ideas: keeping track of multiple features in each pass, and skipping calculations that can be shown not to affect the final selection. Our algorithm selects the exact same features as the classical pivoted QR algorithm, and has the same favorable numerical stability. We describe experiments on real-world datasets which sometimes show improvements of {\em several orders of magnitude} over the classical algorithm. These results appear to be competitive with recently proposed randomized algorithms in terms of pass efficiency and run time. On the other hand, the randomized algorithms may produce better features, at the cost of small probability of failure.

Recently proposed fast template matching techniques employ rejection schemes derived from lower bounds on the match measure. This paper generalizes that idea and shows that in addition to lower bounds, upper bounds on the match measure can be used to accelerate the search. An algorithm is proposed that utilizes both lower and upper bounds to detect the k best matches in an image. The performance of this dual-bound algorithm is guaranteed; it always detects the k best matches. Theoretical analysis and experimental results show that its runtime compares favorably with previously proposed real-time exact template-matching schemes.

We describe a fast algorithm that searches for the k most likely locations of a template in an image according to the standard normalized correlations criterion. The algorithm is exact; it always finds the best matches. Its speed is achieved by utilizing an acceptance-rejection pruning scheme, applied to easily computed bounds on the normalized correlation values. Previously proposed rejection schemes require a rejection threshold that has to be provided or estimated from the data. Our algorithm does not use such thresholds explicitly, but performs as well as if the perfect rejection threshold is known.

The problem of finding a match for an image (`template') within a larger image is known as template matching. It is key to a variety of computer vision applications. Currently known template matching algorithms run in fixed time, or are guaranteed to find the best match. We present a novel algorithm which in many cases can guarantee that the best match is found. In other cases it finds a good approximation to the best match. This algorithm runs in fixed time (a.k.a. hard real time). It finds an optimal match very quickly when a good match exists.

Content based indexing is computed from input that consists of matching values between images and templates. The key idea is to embed both images and templates in a low-dimensional Euclidean space so that matching between embedded images and embedded templates approximates the given input. It is shown that such embedding can be computed by means of a singular value decomposition of the input matrix. Classic principal component analysis is shown to be a special case of the proposed technique, corresponding to the case where the templates and the images are the same.

Large collections of images cam be indexed by projections on a few "eigenfeatures" the dominant eigenvectors of the images covariance matrix. A preliminary step of registering the images is common practice. A quantitative analysis is being gained by registration was not performed in previous work, and heuristics were used to determine on what to register the images. We show that the registration improves the accuracy of indexing and optimal improvement is obtained when the images are registered on their eigenfeatures subspace. Similarly, if multiple images are to be registered on a subspace, the optimal subspace is the one spanned by the dominant eigenfeatures of the registered images. An algorithm that simultaneously registers the images and computes their eigenfeatures is proposed. The key idea is to iterate the following two steps: 1. Eigenfeatures are computed from the images. 2. New images are computed by registering the images on the subspace of these eigenfeatures. In the next iteration, Step 1 is applied to the set of images that were most recently computed in Step 2. It is demonstrated that the algorithm produces improved eigenfeatures and registers multiple images.

Measures of scatter are used in statistical pattern recognition to identify and select important features, computed as linear combinations of the given features. Examples include principal components and linear discriminants. The classic computational procedures require eigenvector decomposition of large matrices, and in the case of images they are only practical for identifying a low dimensional feature subspace. We investigate the case in which the selected features are required to be a subset of the given features. It is shown that the same scatter measures used in the general case can also be used in this discrete selection case, but the computational procedure no longer involves matrix eigenvector decomposition. Instead, the selection of pixels that optimize scatter measures can be accomplished by a very simple and efficient discrete optimization technique that runs in linear time regardless of the subspace size. Applications to clustering and content based indexing are discussed.

In inductive reasoning one uses a small set of examined instances to infer global relations. The standard approach is to search for relations that can be verified in all the examined instances, and hypothesize that they hold globally. Relations that hold only for a subset of the examined instances were previously used only for statistical inference. In this paper it is shown that this statistical information can also be used to infer relations that hold for all instances. The main result is an algorithm that uses statistics to infer Boolean predicates. The analysis includes an investigation of what statistics are relevant for such inference, and what predicates can be inferred.

Ritz vectors approximate eigenvectors that are a common choice for primary images in content based indexing. They can be computed efficiently even when the images are accessed through slow communication such as the Internet. We develop an algorithm that computes Ritz vectors in one pass through the images. When iterated, the algorithm can recover the exact eigenvectors. In applications to image indexing and learning it may be necessary to compute primary images for indexing many sub-categories of the image set. The proposed algorithm can compute these age data. Similar computation by other algorithms is much more costly even when access to the images is inexpensive.

An unsupervised algorithm for arranging an image database as a binary tree is described. Tree nodes are associated with image subsets, maintaining the property that the similarity among the images associated with the children of a node is higher than the similarity among the images associated with the parent node. Experiments with datasets of hundreds and thousands of images show that shallow trees can produce clustering into "meaningful" classes. Visual-content search trees can be used to automate image retrieval by content, or help a human to interactively search for images.

Shapes such as triangles or rectangles can be defined in terms of geometric properties invariant under a group of transformations. Complex shapes can be described by logic formulas with simpler shapes as the atoms. A standard technique for computing invariant properties of simple shapes is the method of moment invariants, known since the early 1960s. We generalize this technique to shapes described by arbitrary monotone formulas (formulas in propositional logic without negation). Our technique produces a reduced Gröbner basisfor approximate shape descriptions. We show how to use this representation to solve decision problems related to shapes. Examples include determining if a figure has a particular shape, if one description of a shape is more general than another, and whether a specific geometric property is really necessary for specifying a shape. Unlike geometry theorem proving, our approach does not require the shapes to be explicitly defined. Instead, logic formulas combined with measurements performed on actual shape instances are used to compute well‐characterized least squares approximations to the shapes. Our results provide a proof that decision problems stated in terms of these approximations can be solved in a finite number of steps.

Reliable object recognition is an essential part of most visual systems. Model-based approaches to object recognition use a database (a library) of modeled objects; for a given set of sensed data, the problem of model-based recognition is to identify and locate the objects from the library that are present in the data. We show that the complexity of model-based recognition depends very heavily on the number of object models in the library even if each object is modeled by a small number of discrete features. Specifically, deciding whether a discrete set of sensed data can be interpreted as transformed object models from a given library is NP-complete if the transformation is any combination of translation, rotation, scaling, and perspective projection. This suggests that efficient algorithms for model-based recognition must use additional structure to avoid the inherent computational difficulties. © 1998 John Wiley & Sons, Inc.

Image motion induced by camera or object motion can be approximated locally by an affine coordinate transformation. We extract 3D information directly from the affine parameters, without camera calibration. The derivation relies on the following assumptions: the object is rigid locally planar, and its local 3D motion is translation. These assumptions enable complete recovery of 3D structure, whereas it is impossible to compute the direction (and magnitude) of the motion. Still, it is possible to distinguish between objects moving differently. Explicit expressions for the structure and the motion indicators are given in terms of the 6 affine parameters, computed for each image patch. Results of experiments on data with known ground truth are described.

The standard approach to computing motion relies on pixel correspondence. Computational schemes impose additional constraints, such as smoothness and continuity of the motion vector even though these are not directly related to pixel correspondence. This paper proposes an alternative to the multiple constraints approach. By drawing analogy with machine learning, motion is computed as a function that accurately predicts frames. The Occam-Razor principle suggests that among all functions that accurately predict the second frame from the first frame, the best predictor is the "simplest," and simplicity can be rigorously defined in terms of encoding length. An implementation of a practical algorithm is described. Experiments with real video sequences verify the algorithm assumptions by showing that motion in typical sequences can be accurately described in terms of a few parameters. Our particular choice of predictors produces results that compare very favorably with other image flow algorithms in terms of accuracy and compactness. It may, however, be too constrained to enable accurate recovery of 3D motion and structure.>

Correspondence between pixels in two perspective views can be obtained from correspondence between surface patches. Establishing surface correspondence is formulated as a global minimization problem.>

By drawing an analogy with machine learning, the author proposes to define visual motion as a predictor that can accurately predict future frames. Under this new definition, visual motion can be specified by a collection of image patches, each moving in a simple motion. An implementation with rectangular patches determined recursively by a binary decision tree is described. Experimental results on real video sequences verify the algorithm assumptions and show that motion in typical sequences can be accurately described in terms of a few parameters.>

When given partial data, a model based approach requires that pictures consistent with the model are chosen as plausible interpretations of the data. The author presents a computational theory that relates degrees of freedom in such models to the number of pixels that carry useful information. It is shown that in models with a finite number of degrees of freedom it is always possible to find a consistent interpretation from a finite number of pixels.>

A method for determining local surface orientation from the autocorrelation function of statistically isotropic textures is introduced. It relies on the foreshortening that occurs in the image of an oriented surface, and the analogous foreshortening produced in the texture-autocorrelation function. This method assumes textural isotropy, but does not require the texture to be composed of texels or assume other texture regularities. The technique was applied to natural images of planar-textured surfaces and found to give good results. The simplicity of the method and its use of information from all parts of the image are emphasized.>

Valiant's theory of the learnable is applied to visual concepts in digital pictures. Several visual concepts that are easily perceived by humans are shown to be learnable from positive examples. These concepts include a certain type of inaccurate copies of line drawings, identifying a subset of objects at specific locations, and pictures of lines in a fixed slope. Several characterizations of visual concepts by templates are shown to be nonlearnable (in the sense of Valiant) from positive-only examples. The importance of representations is demonstrated by showing that even though one can easily learn to identify pictures with at least one of two objects, identifying the objects is sometimes much harder (computationally infeasible).>

A method for determining local surface orientation from the autocorrelation function of statistically isotropic textures is introduced. It relies on the foreshortening that occurs in the image of an oriented surface, and the analogous foreshortening produced in the texture autocorrelation function. This method assumes textural isotropy, but does not require the texture to be composed of texels or assume texture regularities such as equal-area texels or equal spacing between texels. This technique is applied to natural images of planar textured surfaces and found to give good results in many instances. The simplicity of the method and its use of information from all parts of the image are emphasized.>

A novel technique is described that can be applied to a sequence of pictures to detect moving objects and segment them from the stationary background. It does not require the pictures to be in-register, and is suitable for cases where the camera moves while the pictures are taken. Its greatest advantage is the simplicity and efficiency in which it can be implemented. By the use of fast Fourier transforms, the detection of moving objects in a pair of pictures takes about the same computation time as a simple convolution between two pictures of the same size (three Fourier transforms).>

Valiant’s theory of the learnable is applied to visual concepts in digital pictures. Several visual concepts that are easily perceived by humans are shown to be learnable from examples by a simple algorithm. These include inaccurate copies of a picture, multiple objects, and lines in a fixed slope. However, there are simple characterizations of visual concepts which are apparently non-learnable from examples. It is shown that templates for template matching cannot be learned from a feasible number of positive examples.