Amnon Shashua

ICLR Conference 2024 Conference Paper

Align With Purpose: Optimize Desired Properties in CTC Models with a General Plug-and-Play Framework

• Eliya Segev
• Maya Alroy
• Ronen Katsir
• Noam Wies
• Ayana Shenhav
• Yael Ben-Oren
• David Zar
• Oren Tadmor

Connectionist Temporal Classification (CTC) is a widely used criterion for training supervised sequence-to-sequence (seq2seq) models. It learns the alignments between the input and output sequences by marginalizing over the perfect alignments (that yield the ground truth), at the expense of the imperfect ones. This dichotomy, and in particular the equal treatment of all perfect alignments, results in a lack of controllability over the predicted alignments. This controllability is essential for capturing properties that hold significance in real-world applications. Here we propose Align With Purpose (AWP), a general Plug-and-Play framework for enhancing a desired property in models trained with the CTC criterion. We do that by complementing the CTC loss with an additional loss term that prioritizes alignments according to a desired property. AWP does not require any intervention in the CTC loss function, and allows to differentiate between both perfect and imperfect alignments for a variety of properties. We apply our framework in the domain of Automatic Speech Recognition (ASR) and show its generality in terms of property selection, architectural choice, and scale of the training dataset (up to 280,000 hours). To demonstrate the effectiveness of our framework, we apply it to two unrelated properties: token emission time for latency optimization and word error rate (WER). For the former, we report an improvement of up to 590ms in latency optimization with a minor reduction in WER, and for the latter, we report a relative improvement of 4.5% in WER over the baseline models. To the best of our knowledge, these applications have never been demonstrated to work on this scale of data. Notably, our method can be easily implemented using only a few lines of code and can be extended to other alignment-free loss functions and to domains other than ASR.

ICML Conference 2024 Conference Paper

Fundamental Limitations of Alignment in Large Language Models

• Yotam Wolf
• Noam Wies
• Oshri Avnery
• Yoav Levine
• Amnon Shashua

An important aspect in developing language models that interact with humans is aligning their behavior to be useful and unharmful for their human users. This is usually achieved by tuning the model in a way that enhances desired behaviors and inhibits undesired ones, a process referred to as alignment. In this paper, we propose a theoretical approach called Behavior Expectation Bounds (BEB) which allows us to formally investigate several inherent characteristics and limitations of alignment in large language models. Importantly, we prove that within the limits of this framework, for any behavior that has a finite probability of being exhibited by the model, there exist prompts that can trigger the model into outputting this behavior, with probability that increases with the length of the prompt. This implies that any alignment process that attenuates an undesired behavior but does not remove it altogether, is not safe against adversarial prompting attacks. Furthermore, our framework hints at the mechanism by which leading alignment approaches such as reinforcement learning from human feedback make the LLM prone to being prompted into the undesired behaviors. This theoretical result is being experimentally demonstrated in large scale by the so called contemporary "chatGPT jailbreaks", where adversarial users trick the LLM into breaking its alignment guardrails by triggering it into acting as a malicious persona. Our results expose fundamental limitations in alignment of LLMs and bring to the forefront the need to devise reliable mechanisms for ensuring AI safety.

ICLR Conference 2023 Conference Paper

Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks

• Noam Wies
• Yoav Levine
• Amnon Shashua

The field of Natural Language Processing (NLP) has experienced a dramatic leap in capabilities with the recent introduction of huge Language Models (LMs). Despite this success, natural language problems that involve several compounded steps are still practically unlearnable, even by the largest LMs. This complies with experimental failures for end-to-end learning of composite problems that were demonstrated in a variety of domains. An effective mitigation is to introduce intermediate supervision for solving sub-tasks of the compounded problem. Recently, several works have demonstrated high gains by taking a straightforward approach for incorporating intermediate supervision in compounded natural language problems: the sequence-to-sequence LM is fed with an augmented input, in which the decomposed tasks' labels are simply concatenated to the original input. In this paper, we prove a positive learning result that motivates these recent efforts. We show that when concatenating intermediate supervision to the input and training a sequence-to-sequence model on this modified input, unlearnable composite problems can become learnable. We show that this is true for any family of tasks which on the one hand, are unlearnable, and on the other hand, can be decomposed into a polynomial number of simple sub-tasks, each of which depends only on $O(1)$ previous sub-task results. Beyond motivating contemporary empirical efforts for incorporating intermediate supervision in sequence-to-sequence language models, our positive theoretical result is the first of its kind in the landscape of results on the benefits of intermediate supervision for neural-network learning: Until now, all theoretical results on the subject are negative, i.e., show cases where learning is impossible without intermediate supervision, while our result is positive, showing that learning is facilitated in the presence of intermediate supervision.

NeurIPS Conference 2023 Conference Paper

The Learnability of In-Context Learning

• Noam Wies
• Yoav Levine
• Amnon Shashua

In-context learning is a surprising and important phenomenon that emerged when modern language models were scaled to billions of learned parameters. Without modifying a large language model's weights, it can be tuned to perform various downstream natural language tasks simply by including concatenated training examples of these tasks in its input. Though disruptive for many practical applications of large language models, this emergent learning paradigm is not well understood from a theoretical perspective. In this paper, we propose a first-of-its-kind PAC based framework for in-context learnability, and use it to provide the first finite sample complexity results for the in-context learning setup. Our framework includes an initial pretraining phase, which fits a function to the pretraining distribution, and then a second in-context learning phase, which keeps this function constant and concatenates training examples of the downstream task in its input. We use our framework in order to prove that, under mild assumptions, when the pretraining distribution is a mixture of latent tasks (a model often considered for natural language pretraining), these tasks can be efficiently learned via in-context learning, even though the model's weights are unchanged and the input significantly diverges from the pretraining distribution. Our theoretical analysis reveals that in this setting, in-context learning is more about identifying the task than about learning it, a result which is in line with a series of recent empirical findings. We hope that the in-context learnability framework presented in this paper will facilitate future progress towards a deeper understanding of this important new learning paradigm.

ICLR Conference 2022 Conference Paper

The Inductive Bias of In-Context Learning: Rethinking Pretraining Example Design

• Yoav Levine
• Noam Wies
• Daniel Jannai
• Dan Navon
• Yedid Hoshen
• Amnon Shashua

Pretraining Neural Language Models (NLMs) over a large corpus involves chunking the text into training examples, which are contiguous text segments of sizes processable by the neural architecture. We highlight a bias introduced by this common practice: we prove that the pretrained NLM can model much stronger dependencies between text segments that appeared in the same training example, than it can between text segments that appeared in different training examples. This intuitive result has a twofold role. First, it formalizes the motivation behind a broad line of recent successful NLM training heuristics, proposed for the pretraining and fine-tuning stages, which do not necessarily appear related at first glance. Second, our result clearly indicates further improvements to be made in NLM pretraining for the benefit of Natural Language Understanding tasks. As an example, we propose ``kNN-Pretraining": we show that including semantically related non-neighboring sentences in the same pretraining example yields improved sentence representations and open domain question answering abilities. This theoretically motivated degree of freedom for pretraining example design indicates new training schemes for self-improving representations.

ICML Conference 2021 Conference Paper

Which transformer architecture fits my data? A vocabulary bottleneck in self-attention

• Noam Wies
• Yoav Levine
• Daniel Jannai
• Amnon Shashua

After their successful debut in natural language processing, Transformer architectures are now becoming the de-facto standard in many domains. An obstacle for their deployment over new modalities is the architectural configuration: the optimal depth-to-width ratio has been shown to dramatically vary across data types (i. e. , 10x larger over images than over language). We theoretically predict the existence of an embedding rank bottleneck that limits the contribution of self-attention width to the Transformer expressivity. We thus directly tie the input vocabulary size and rank to the optimal depth-to-width ratio, since a small vocabulary size or rank dictates an added advantage of depth over width. We empirically demonstrate the existence of this bottleneck and its implications on the depth-to-width interplay of Transformer architectures, linking the architecture variability across domains to the often glossed-over usage of different vocabulary sizes or embedding ranks in different domains. As an additional benefit, our rank bottlenecking framework allows us to identify size redundancies of 25%-50% in leading NLP models such as ALBERT and T5.

NeurIPS Conference 2020 Conference Paper

Limits to Depth Efficiencies of Self-Attention

• Yoav Levine
• Noam Wies
• Or Sharir
• Hofit Bata
• Amnon Shashua

Self-attention architectures, which are rapidly pushing the frontier in natural language processing, demonstrate a surprising depth-inefficient behavior: Empirical signals indicate that increasing the internal representation (network width) is just as useful as increasing the number of self-attention layers (network depth). In this paper, we theoretically study the interplay between depth and width in self-attention. We shed light on the root of the above phenomenon, and establish two distinct parameter regimes of depth efficiency and inefficiency in self-attention. We invalidate the seemingly plausible hypothesis by which widening is as effective as deepening for self-attention, and show that in fact stacking self-attention layers is so effective that it quickly saturates a capacity of the network width. Specifically, we pinpoint a ``depth threshold" that is logarithmic in the network width: for networks of depth that is below the threshold, we establish a double-exponential depth-efficiency of the self-attention operation, while for depths over the threshold we show that depth-inefficiency kicks in. Our predictions accord with existing empirical ablations, and we further demonstrate the two depth-(in)efficiency regimes experimentally for common network depths of 6, 12, and 24. By identifying network width as a limiting factor, our analysis indicates that solutions for dramatically increasing the width can facilitate the next leap in self-attention expressivity.

ICLR Conference 2018 Conference Paper

Boosting Dilated Convolutional Networks with Mixed Tensor Decompositions

• Nadav Cohen 0001
• Ronen Tamari
• Amnon Shashua

The driving force behind deep networks is their ability to compactly represent rich classes of functions. The primary notion for formally reasoning about this phenomenon is expressive efficiency, which refers to a situation where one network must grow unfeasibly large in order to replicate functions of another. To date, expressive efficiency analyses focused on the architectural feature of depth, showing that deep networks are representationally superior to shallow ones. In this paper we study the expressive efficiency brought forth by connectivity, motivated by the observation that modern networks interconnect their layers in elaborate ways. We focus on dilated convolutional networks, a family of deep models delivering state of the art performance in sequence processing tasks. By introducing and analyzing the concept of mixed tensor decompositions, we prove that interconnecting dilated convolutional networks can lead to expressive efficiency. In particular, we show that even a single connection between intermediate layers can already lead to an almost quadratic gap, which in large-scale settings typically makes the difference between a model that is practical and one that is not. Empirical evaluation demonstrates how the expressive efficiency of connectivity, similarly to that of depth, translates into gains in accuracy. This leads us to believe that expressive efficiency may serve a key role in developing new tools for deep network design.

ICML Conference 2016 Conference Paper

Convolutional Rectifier Networks as Generalized Tensor Decompositions

• Nadav Cohen 0001
• Amnon Shashua

Convolutional rectifier networks, i. e. convolutional neural networks with rectified linear activation and max or average pooling, are the cornerstone of modern deep learning. However, despite their wide use and success, our theoretical understanding of the expressive properties that drive these networks is partial at best. On the other hand, we have a much firmer grasp of these issues in the world of arithmetic circuits. Specifically, it is known that convolutional arithmetic circuits possess the property of "complete depth efficiency", meaning that besides a negligible set, all functions realizable by a deep network of polynomial size, require exponential size in order to be realized (or approximated) by a shallow network. In this paper we describe a construction based on generalized tensor decompositions, that transforms convolutional arithmetic circuits into convolutional rectifier networks. We then use mathematical tools available from the world of arithmetic circuits to prove new results. First, we show that convolutional rectifier networks are universal with max pooling but not with average pooling. Second, and more importantly, we show that depth efficiency is weaker with convolutional rectifier networks than it is with convolutional arithmetic circuits. This leads us to believe that developing effective methods for training convolutional arithmetic circuits, thereby fulfilling their expressive potential, may give rise to a deep learning architecture that is provably superior to convolutional rectifier networks but has so far been overlooked by practitioners.

NeurIPS Conference 2016 Conference Paper

Learning a Metric Embedding for Face Recognition using the Multibatch Method

• Oren Tadmor
• Tal Rosenwein
• Shai Shalev-Shwartz
• Yonatan Wexler
• Amnon Shashua

This work is motivated by the engineering task of achieving a near state-of-the-art face recognition on a minimal computing budget running on an embedded system. Our main technical contribution centers around a novel training method, called Multibatch, for similarity learning, i. e. , for the task of generating an invariant ``face signature'' through training pairs of ``same'' and ``not-same'' face images. The Multibatch method first generates signatures for a mini-batch of $k$ face images and then constructs an unbiased estimate of the full gradient by relying on all $k^2-k$ pairs from the mini-batch. We prove that the variance of the Multibatch estimator is bounded by $O(1/k^2)$, under some mild conditions. In contrast, the standard gradient estimator that relies on random $k/2$ pairs has a variance of order $1/k$. The smaller variance of the Multibatch estimator significantly speeds up the convergence rate of stochastic gradient descent. Using the Multibatch method we train a deep convolutional neural network that achieves an accuracy of $98. 2\%$ on the LFW benchmark, while its prediction runtime takes only $30$msec on a single ARM Cortex A9 core. Furthermore, the entire training process took only 12 hours on a single Titan X GPU.

UAI Conference 2012 Conference Paper

Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs

• Tamir Hazan
• Jian Peng 0001
• Amnon Shashua

In this paper we present a new approach for tightening upper bounds on the partition function. Our upper bounds are based on fractional covering bounds on the entropy function, and result in a concave program to compute these bounds and a convex program to tighten them. To solve these programs effectively for general region graphs we utilize the entropy barrier method, thus decomposing the original programs by their dual programs and solve them with dual block optimization scheme. The entropy barrier method provides an elegant framework to generalize the message-passing scheme to high-order region graph, as well as to solve the block dual steps in closed-form. This is a key for computational relevancy for large problems with thousands of regions.

NeurIPS Conference 2011 Conference Paper

ShareBoost: Efficient multiclass learning with feature sharing

• Shai Shalev-Shwartz
• Yonatan Wexler
• Amnon Shashua

Multiclass prediction is the problem of classifying an object into a relevant target class. We consider the problem of learning a multiclass predictor that uses only few features, and in particular, the number of used features should increase sub-linearly with the number of possible classes. This implies that features should be shared by several classes. We describe and analyze the ShareBoost algorithm for learning a multiclass predictor that uses few shared features. We prove that ShareBoost efficiently finds a predictor that uses few shared features (if such a predictor exists) and that it has a small generalization error. We also describe how to use ShareBoost for learning a non-linear predictor that has a fast evaluation time. In a series of experiments with natural data sets we demonstrate the benefits of ShareBoost and evaluate its success relatively to other state-of-the-art approaches.

UAI Conference 2008 Conference Paper

Convergent Message-Passing Algorithms for Inference over General Graphs with Convex Free Energies

• Tamir Hazan
• Amnon Shashua

Inference problems in graphical models can be represented as a constrained optimization of a free energy function. It is known that when the Bethe free energy is used, the fixedpoints of the belief propagation (BP) algorithm correspond to the local minima of the free energy. However BP fails to converge in many cases of interest. Moreover, the Bethe free energy is non-convex for graphical models with cycles thus introducing great difficulty in deriving efficient algorithms for finding local minima of the free energy for general graphs. In this paper we introduce two efficient BP-like algorithms, one sequential and the other parallel, that are guaranteed to converge to the global minimum, for any graph, over the class of energies known as ”convex free energies”. In addition, we propose an efficient heuristic for setting the parameters of the convex free energy based on the structure of the graph.

NeurIPS Conference 2006 Conference Paper

Doubly Stochastic Normalization for Spectral Clustering

• Ron Zass
• Amnon Shashua

In this paper we focus on the issue of normalization of the affinity matrix in spectral clustering. We show that the difference between N-cuts and Ratio-cuts is in the error measure being used (relative-entropy versus L1 norm) in finding the closest doubly-stochastic matrix to the input affinity matrix. We then develop a scheme for finding the optimal, under Frobenius norm, doubly-stochastic approximation using Von-Neumann's successive projections lemma. The new normalization scheme is simple and efficient and provides superior clustering performance over many of the standardized tests.

NeurIPS Conference 2006 Conference Paper

Nonnegative Sparse PCA

• Ron Zass
• Amnon Shashua

We describe a nonnegative variant of the "Sparse PCA" problem. The goal is to create a low dimensional representation from a collection of points which on the one hand maximizes the variance of the projected points and on the other uses only parts of the original coordinates, and thereby creating a sparse representation. What distinguishes our problem from other Sparse PCA formulations is that the projection involves only nonnegative weights of the original coordinates -- a desired quality in various fields, including economics, bioinformatics and computer vision. Adding nonnegativity contributes to sparseness, where it enforces a partitioning of the original coordinates among the new axes. We describe a simple yet efficient iterative coordinate-descent type of scheme which converges to a local optimum of our optimization criteria, giving good results on large real world datasets.

JMLR Journal 2005 Journal Article

Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach

• Lior Wolf
• Amnon Shashua

The problem of selecting a subset of relevant features in a potentially overwhelming quantity of data is classic and found in many branches of science. Examples in computer vision, text processing and more recently bio-informatics are abundant. In text classification tasks, for example, it is not uncommon to have 10 4 to 10 7 features of the size of the vocabulary containing word frequency counts, with the expectation that only a small fraction of them are relevant. Typical examples include the automatic sorting of URLs into a web directory and the detection of spam email. In this work we present a definition of "relevancy" based on spectral properties of the Laplacian of the features' measurement matrix. The feature selection process is then based on a continuous ranking of the features defined by a least-squares optimization process. A remarkable property of the feature relevance function is that sparse solutions for the ranking values naturally emerge as a result of a "biased non-negativity" of a key matrix in the process. As a result, a simple least-squares optimization process converges onto a sparse solution, i.e., a selection of a subset of features which form a local maximum over the relevance function. The feature selection algorithm can be embedded in both unsupervised and supervised inference problems and empirical evidence show that the feature selections typically achieve high accuracy even when only a small fraction of the features are relevant. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

ICML Conference 2005 Conference Paper

Non-negative tensor factorization with applications to statistics and computer vision

• Amnon Shashua
• Tamir Hazan

NeurIPS Conference 2004 Conference Paper

Algebraic Set Kernels with Application to Inference Over Local Image Representations

• Amnon Shashua
• Tamir Hazan

This paper presents a general family of algebraic positive definite simi- larity functions over spaces of matrices with varying column rank. The columns can represent local regions in an image (whereby images have varying number of local parts), images of an image sequence, motion tra- jectories in a multibody motion, and so forth. The family of set kernels we derive is based on a group invariant tensor product lifting with param- eters that can be naturally tuned to provide a cook-book of sorts covering the possible "wish lists" from similarity measures over sets of varying cardinality. We highlight the strengths of our approach by demonstrat- ing the set kernels for visual recognition of pedestrians using local parts representations. 1 Introduction In the area of learning from observations there are two main paths that are often mutually exclusive: (i) the design of learning algorithms, and (ii) the design of data representations. The algorithm designers take pride in the fact that their algorithm can generalize well given straightforward data representations (most notable example is SVM [11]), whereas those who work on data representations demonstrate often remarkable results with sophisticated data representations using only straightforward learning algorithms (e. g. [5, 10, 6]). This dichotomy is probably most emphasized in the area of computer vision, where image under- standing from observations involve data instances of images or image sequences containing huge amounts of data. A straightforward representation treating all the measurements as a single vector, such as the raw pixel data, or a transformed raw-pixel data, places un- reasonable demands on the learning algorithm. The "holistic" representations suffer also from sensitivity to occlusions, invariance to local and global transformations, non-rigidity of local parts of the object, and so forth. Practitioners in the area of data representations have long noticed that a collection of local representations (part-based representations) can be most effective to ameliorate changes of appearance [5, 10, 6]. The local data representations vary in their sophistication, but share the same principle where an image corresponds to a collection of points each in a relatively small dimensional space -- instead of a single point in high-dimensional space induced by holistic representations. In general, the number of points (local parts) per image may vary and the dimension of each point may vary as well. The local representations tend School of Engineering and Computer Science, Hebrew University of Jerusalem, Jerusalem 91904, Israel to be robust against occlusions, local and global transformations and preserve the original resolution of the image (the higher the resolution the more parts are generated per image). The key for unifying local and holistic representations for inference engines is to design positive definite similarity functions (a. k. a. kernels) over sets (of vectors) of varying cardi- nalities. A Support Vector Machine (SVM) [11] can then handle sets of vectors as a single instance via application of those "set kernels". A set kernel would be useful also to other types of inference engines such as kernel versions of PCA, LDA, CCA, ridge regression and any algorithm which can be mapped onto inner-products between pairs of data instances (see [8] for details on kernel methods). Formally, we consider an instance being represented by a collection of vectors, which for the sake of convenience, form the columns of a matrix. We would like to find an algebraic family of similarity functions sim(A, B) over matrices A, B which satisfy the following requirements: (i) sim(A, B) is an inner product, i. e. , sim(A, B) = (A) (B) for some mapping () from matrices to vectors, (ii) sim(A, B) is built over local kernel functions k(ai, bj) over columns ai and bj of A, B respectively, (iii) The column cardinality (rank of column space) of A and B need not be the same (number of local parts may differ from image to image), and (iv) the parameters of sim(A, B) should induce the properties of in- variance to order (alignement) of parts, part occlusions, and degree of interactions between local parts. In a nutshell, our work provides a cook-book of sorts which fundamentally covers the possible algebraic kernels over collections of local representations built on top of local kernels by combining (linearly and non-linearly) local kernels to form a family of global kernels over local representations. The design of a kernel over sets of vectors has been recently attracting much attention in the computer vision and machine learning literature. A possible approach is to fit a distribution to the set of vectors and define the kernel as a distribution matching measure [9, 12, 4]. This has the advantage that the number of local parts can vary but at the expense of fitting a distribution to the variation over parts. The variation could be quite complex at times, unlikely to fit into a known family of distributions in many situations of interest, and in practice the sample size (number of columns of A) is not sufficiently large to reliably fit a distribution. The alternative, which is the approach taken in this paper, is to create a kernel over sets of vectors in a direct manner. When the column cardinality is equal it is possible to model the similarity measure as a function over the principal angles between the two column spaces ([14] and references therein) while for varying column cardinality only heuristic similarity measures (which are not positive definite) have so far been introduced [13]. It is important to note that although we chose SVM over local representations as the appli- cation to demonstrate the use of set kernels, the need for adequately working with instances made out of sets of various cardinalities spans many other application domains. For exam- ple, an image sequence may be represented by a set (ordered or unordered) of vectors, where each vector stands for an image, the pixels in an image can be represented as a tuple consisting of position, intensity and other attributes, motion trajectories of multiply mov- ing bodies can be represented as a collection of vectors, and so on. Therefore, the problem addressed in this paper is fundamental both theoretically and from a practical perspective as well. 2 The General Family of Inner-Products over Matrices We wish to derive the general family of positive definite similarity measures sim(A, B) over matrices A, B which have the same number of rows but possibly different column rank (in particular, different number of columns). Let A be of dimensions n k and B of dimension n q where n is fixed and k, q can vary at will over the application of sim(, ) on pairs of matrices. Let m = max{n, k, q} be the upper bound over all values of k, q encountered by the data. Let ai, bj be the column vectors of matrices A, B and let k(ai, bj) be the local kernel function. For example, in the context where the column vectors represent local parts of an image, then the matching function k(, ) between pairs of local parts provides the building blocks of the overall similarity function. The local kernel is some positive definite function k(x, y) = (x) (y) which is the inner-product between the "feature"-mapped vectors x, y for some feature map (). For example, if () is the polynomial map of degree up to d, then k(x, y) = (1 + x y)d. The local kernels can be combined in a linear or non-linear manner. When the combination is linear the similarity becomes the analogue of the inner-product between vectors extended to matrices. We will refer to the linear family as sim(A, B) = and that will be the focus of this section. In the next section we will derive the general (algebraic) non- linear family which is based on "lifting" the input matrices A, B onto higher dimensional spaces and feeding the result onto the machinery developed in this section, i. e. , sim(A, B) =. We will start by embedding A, B onto m m matrices by zero padding as follows. Let ei denote the i'th standard basis vector (0, .. , 0, 1, 0, .. , 0) of Rm. The the embedding is represented by linear combinations of tensor products: n k n q A aijei ej, B bltel et. i=1 j=1 l=1 t=1 Note that A, B are the upper-left blocks of the zero-padded matrices. Let S be a positive semi definite m2 m2 matrix represented by S = p G r=1 r Fr where Gr, Fr are m m matrices1. Let ^ Fr be the q k upper-left sub-matrix of Fr, and let ^ Gr be the n n upper-left sub-matrix of Gr. We will be using the following three identities: Gx1 F x2 = (G F )(x1 x2), (G F )(G F ) = GG F F, = ( )( ). 1 y2 x1 y1 x2 y2 The inner-product over all p. s. d. matrices S has the form: = i, j r l, t = aijblt r i, j, l, t = aijblt(e G F i r el)(ej r et) r i, j, l, t = aijblt(Gr)il(Fr)jt r i, j, l, t = (A ^ GrB)jt(Fr)jt r lt = trace (A ^ GrB) ^ Fr r We have represented the inner product using the choice of m m matrices Gr, Fr instead of the choice of a single m2 m2 p. s. d. matrix S. The matrices Gr, Fr 1Any S can be represented as a sum over tensor products: given column-wise ordering, the matrix G F is composed of n n blocks of the form fij G. Therefore, take Gr to be the n n blocks of S and Fr to be the elemental matrices which have "1" in coordinate r = (i, j) and zero everywhere else. must be selected such that p G r=1 r Fr is positive semi definite. The problem of decid- ing on the the necessary conditions on Fr and Gr such that the sum over tensor products is p. s. d is difficult. Even deciding whether a given S has a separable decomposition is known to be NP-hard [3]. The sufficient conditions are easy -- choosing Gr, Fr to be positive semi definite would make p G r=1 r Fr positive semi definite as well. In this context (of separable S) we need one more constraint in order to work with non-linear local ker- nels k(x, y) = (x) (y): the matrices ^ G ~ r = ~ M M r r must "distribute with the kernel", namely there exist Mr such that k(M ~ r x, Mr y) = (Mr x) (Mry) = (x) ~ M M r r (y) = (x) ^ Gr(y). To summarize the results so far, the most general, but seperable, analogue of the inner- product over vectors to the inner-product of matrices of varying column cardinality has the form: = trace(H ^ r Fr ) (1) r Where the entries of Hr consists of k(Mrai, Mrbj) over the columns of A, B after possibly undergoing global coordinate changes by Mr (the role of ^ Gr), and ^ Fr are the q k upper- left sub-matrix of positive definite m m matrices Fr. The role of the matrices ^ Gr is to perform global coordinate changes of Rn before applica- tion of the kernel k() on the columns of A, B. These global transformations include pro- jections (say onto prototypical "parts") that may be given or "learned" from a training set. The matrices ^ Fr determine the range of interaction between columns of A and columns of B. For example, when ^ Gr = I then = trace(A B ^ F ) where ^ F is the upper-left submatrix with the appropriate dimension of some fixed m m p. s. d matrix F = F r r. Note that entries of A B are k(ai, bj). In other words, when Gr = I, boils down to a simple linear super-position of the local kernels, k(a ij i, bj )fij where the en- tries fij are part of the upper-left block of a fixed positive definite matrix F where the block dimensions are commensurate with the number of columns of A and those of B. The various choices of F determine the type of invariances one could obtain from the simi- larity measure. For example, when F = I the similarity is simply the sum (average) of the local kernels k(ai, bi) thereby assuming we have a strict alignment between the local parts represented by A and the local parts represented by B. On the other end of the in- variance spectrum, when F = 11 (all entries are "1") the similarity measure averages over all interactions of local parts k(ai, bj) thereby achieving an invariance to the order of the parts. A decaying weighted interaction such as fij = -|i-j| would provide a middle ground between the assumption of strict alignment and the assumption of complete lack of alignment. In the section below we will derive the non-linear version of sim(A, B) based on the basic machinery of of eqn. (1) and lifting operations on A, B. 3 Lifting Matrices onto Higher Dimensions The family of sim(A, B) = forms a weighted linear superposition of the local kernel k(ai, bj). Non-linear combinations of local kernels emerge using map- pings (A) from the input matrices onto other higher-dimensional matrices, thus forming sim(A, B) =. Additional invariance properties and parameters control- ling the perfromance of sim(A, B) emerge with the introduction of non-linear combina- tions of local kernels, and those will be discussed later on in this section. Consider the general d-fold lifting (A) = Ad which can be viewed as a nd kd matrix. Let Fr be a p. s. d. matrix of dimension md md and ^ Fr be the upper-left qd kd block of Fr. Let Gr = ( ^ Gr)d be a p. s. d matrix of dimension nd nd where ^ Gr is p. s. d. n n matrix. Using the identity (Ad) Bd = (A B)d we obtain the inner-product in the lifted space: = trace (A ^ GrB)d ^ Fr. r By taking linear combinations of, l = 1, .. ., d, we get the general non- homogenous d-fold inner-product simd(A, B). A this point the formulation is general but somewhat unwieldy computational-wise. The key for computational simplification lay in the fact that choices of Fr determine not only local interactions (as in the linear case) but also group invariances. The group invariances are a result of applying symmetric operators on the tensor product space -- we will consider two of those operators here, known as the the d-fold alternating tensor Ad = A. .. . A and the d-fold symmetric tensor Ad = A. .. A. These lifting operations introduce the determinant and permanent operations on submatrices of A ^ GrB, as described below. The alternating tensor is a multilinear map of Rn, (A. .. . A)(x1. .. xd) = Ax1. .. Axd, where 1 x1. .. xd = sign()x d! (1). .. . x(d), Sd where Sd is the symmetric group over d letters and Sd are the permutations of the group. If x1, .. ., xn form a basis of Rn, then the n elements x. .. x, where 1 d i1 id i1 = = trace Cd(A ^ GrB) ^ Fr, (2) r where ^ Fr is the q k upper-left submatrix of the p. s. d m m matrix F d d d d r. Note that the local kernel plugs in as the entries of (A ^ GrB)ij = k(Mrai, Mrbj) where ^ Gr = M M r r. Another symmetric operator on the tensor product space is via the d-fold symmetric tensor space SymdRn whose points are: 1 x1 xd = x d! (1). .. . x(d). Sd The analogue of Cd(A) is the "d'th power matrix" Rd(A) whose (i1, .. ., id|j1, .. ., jd) entry has the value perm(A[i1, .. ., id: j1, .. ., jd]) and which stands for the map Ad (A A)(x1 xd) = Ax1 Axd. In other words, Rd(A) has n+d-1 rows and k+d-1 columns whose entries are equal to d d the dd permanents of A. The analogue of the Binet-Cauchy theorem is Rd(A) Rd(B) = Rd(A B). The ensuing kernel similarity function, referred to as the "d-fold symmetric kernel" is: Symd(A, B) = = = trace Rd(A ^ GrB) ^ Fr (3) r where ^ Fr is the q+d-1 k+d-1 upper-left submatrix of the positive definite m+d-1 d d d n+d-1 matrix F d r. Due to lack of space we will stop here and spend the remainder of this section in describing in laymen terms what are the properties of these similarity measures, how they can be constructed in practice and in a computationally efficient manner (despite the combinatorial element in their definition). 3. 1 Practical Considerations To recap, the family of similarity functions sim(A, B) comprise of the linear version (eqn. 1) and non-linear versions l(A, B), Syml(A, B) (eqns. 2, 3) which are group projections of the general kernel. These different similarity func- tions are controlled by the choice of three items: Gr, Fr and the parameter d representing the degree of the tensor product operator. Specifically, we will focus on the case Gr = I and on d(A, B) as a representative of the non-linear family. The role of ^ Gr is fairly in- teresting as it can be viewed as a projection operator from "parts" to prototypical parts that can be learned from a training set but we leave this to the full length article that will appear later. Practically, to compute d(A, B) one needs to run over all d d blocks of the k q ma- trix A B (whose entries are k(ai, bj)) and for each block compute the determinant. The similarity function is a weighted sum of all those determinants weighted by fij. By appro- priate selection of F one can control both the complexity (avoid running over all possible d d blocks) of the computation and the degree of interaction between the determinants. These determinants have an interesting geometric interpretation if those are computed over unitary matrices -- as described next. Let A = QARA and B = QBRB be the QR factorization of the matrices, i. e. , QA has orthonormal columns which span the column space of A, then it has been recently shown [14] that R-1 can be computed from A using only operations over k(a A i, aj ). Therefore, the product Q Q A BR-1, can be computed using only local A B, which is equal to R-T A B kernel applications. In other words, for each A compute R-1 (can be done using only A inner-products over columns of A), then when it comes to compute A B compute in- stead R-T A BR-1 which is equivalent to computing Q Q A B A B. Thus effectively we have replaced every A with QA (unitary matrix). Now, d(QA, QB) for unitary matrices is the sum over the product of the cosine principal angles between d-dim subspaces spanned by columns of A and B. The value of each determinant of the d d blocks of Q Q A B is equal to the product of the cosine principal angles between the respective d-dim subspaces determined by corresponding selection of d columns from A and d columns from B. For example, the case k = q = d produces d(QA, QB) = det(Q Q Q A B ) which is the product of the eigenvalues of the matrix QA B. Those eigenvalues are the cosine of the principal angles between the column space of A and the column space of B [2]. Therefore, det(Q Q A B ) measures the "angle" between the two subspaces spanned by the respective columns of the input matrices -- in particular is invariant to the order of the columns. For smaller values of d we obtain the sum over such products between subspaces spanned by subsets of d columns between A and B. The advantage of smaller values of d is two fold: first it enables to compute the similarity when k = q and second breaks down the similarity between subspaces into smaller pieces. The entries of the matrix F determine which subspaces are being considered and the inter- action between subspaces in A and B. A diagonal F compares corresponding subspaces (a) (b) Figure 1: (a) The configuration of the nine sub-regions is displayed over the gradient image. (b) some of the positive examples -- note the large variation in appearance, pose and articulation. between A and B whereas off-diagonal entries would enable comparisons between differ- ent choices of subspaces in A and in B. For example, we may want to consider choices of d columns arranged in a "sliding" fashion, i. e. , column sets {1, .. , d}, {2, .. ., d + 1}, .. . and so forth, instead of the combinatorial number of all possible choices. This selection is associated with a sparse diagonal F where the non-vanishing entries along the diagonal have the value of "1" and correspond to the sliding window selections. To conclude, in the linear version the role of F is to determine the range of interaction between columns of A and columns of B, whereas with the non-linear version it is the interaction between d-dim subspaces rather than individual columns. We could select all possible interactions (exponential number) or any reduced interaction set such as the sliding window rule (linear number of choices) as described above.

JMLR Journal 2003 Journal Article

Learning over Sets using Kernel Principal Angles (Kernel Machines Section)

• Lior Wolf
• Amnon Shashua

We consider the problem of learning with instances defined over a space of sets of vectors. We derive a new positive definite kernel f ( A, B ) defined over pairs of matrices A, B based on the concept of principal angles between two linear subspaces. We show that the principal angles can be recovered using only inner-products between pairs of column vectors of the input matrices thereby allowing the original column vectors of A, B to be mapped onto arbitrarily high-dimensional feature spaces. We demonstrate the usage of the matrix-based kernel function f ( A, B ) with experiments on two visual tasks. The first task is the discrimination of "irregular" motion trajectory of an individual or a group of individuals in a video sequence. We use the SVM approach using f ( A, B ) where an input matrix represents the motion trajectory of a group of individuals over a certain (fixed) time frame. We show that the classification (irregular versus regular) greatly outperforms the conventional representation where all the trajectories form a single vector. The second application is the visual recognition of faces from input video sequences representing head motion and facial expressions where f ( A, B ) is used to compare two image sequences. [abs] [ pdf ][ ps.gz ][ ps ]

NeurIPS Conference 2002 Conference Paper

Ranking with Large Margin Principle: Two Approaches

• Amnon Shashua
• Anat Levin

We discuss the problem of ranking k instances with the use of a "large margin" principle. We introduce two main approaches: the first is the "fixed margin" policy in which the margin of the closest neighboring classes is being maximized - which turns out to be a direct generaliza(cid: 173) tion of SVM to ranking learning. The second approach allows for k - 1 different margins where the sum of margins is maximized. This approach is shown to reduce to lI-SVM when the number of classes k = 2. Both approaches are optimal in size of 21 where I is the total number of training examples. Experiments performed on visual classification and "collab(cid: 173) orative filtering" show that both approaches outperform existing ordinal regression algorithms applied for ranking and multi-class SVM applied to general multi-class classification.

NeurIPS Conference 1991 Conference Paper

Illumination and View Position in 3D Visual Recognition

• Amnon Shashua

It is shown that both changes in viewing position and illumination con(cid: 173) ditions can be compensated for, prior to recognition, using combinations of images taken from different viewing positions and different illumina(cid: 173) tion conditions. It is also shown that, in agreement with psychophysical findings, the computation requires at least a sign-bit image as input - contours alone are not sufficient.

NeurIPS Conference 1990 Conference Paper

Grouping Contours by Iterated Pairing Network

• Amnon Shashua
• Shimon Ullman

Shimon Ullman We describe in this paper a network that performs grouping of image con(cid: 173) tours. The input to the net are fragments of image contours, and the output is the partitioning of the fragments into groups, together with a saliency measure for each group. The grouping is based on a measure of overall length and curvature. The network decomposes the overall opti(cid: 173) mization problem into independent optimal pairing problems performed at each node. The resulting computation maps into a uniform locally connected network of simple computing elements. 1 The Problenl: Contour Grouping A problem that often arises in visual information processing is the linking of con(cid: 173) tour fragments into optimal groups. For example, certain subsets of contours spon(cid: 173) taneously form perceptual groups, as illustrated in Fig. 1, and are often detected immediately without scanning the image in a systematic manner. Grouping process of this type are likely to play an important role in object recognition by segmenting the image and selecting image structures that are likely to correspond to objects of interest in the scene. 'Ve propose that some form of autonomous grouping is performed at an early stage based on geometrical characteristics, that are independent of the identity of objects to be selected. The grouping process is governed by the notion of saliency in a way that priority is given to forming salient groups at the expense of potentially less salient ones. This general notion can again be illustrated by Fig. 1; it appears that certain groups spontaneously emerge, while grouping decisions concerning the less salient parts of the image may remain unresolved. As we shall see, the computation below exhibits a similar behavior. We define a grouping of the image contours as the formation of a set of disjoint