Backpropagation, which uses the chain rule, is the de-facto standard algorithm for optimizing neural networks nowadays. Recently, Hinton (2022) proposed the forward-forward algorithm, a promising alternative that optimizes neural nets layer-by-layer, without propagating gradients throughout the network. Although such an approach has several advantages over back-propagation and shows promising results, the fact that each layer is being trained independently limits the optimization process. Specifically, it prevents the network's layers from collaborating to learn complex and rich features. In this work, we study layer collaboration in the forward-forward algorithm. We show that the current version of the forward-forward algorithm is suboptimal when considering information flow in the network, resulting in a lack of collaboration between layers of the network. We propose an improved version that supports layer collaboration to better utilize the network structure, while not requiring any additional assumptions or computations. We empirically demonstrate the efficacy of the proposed version when considering both information flow and objective metrics. Additionally, we provide a theoretical motivation for the proposed method, inspired by functional entropy theory.

Learning to match discrete objects has been a central task in machine learning, often facilitated by a continuous relaxation of the matching structure. However, practical problems entail partial matchings due to missing correspondences, which pose difficulties to the one-to-one matching learning techniques that dominate the state-of-the-art. This paper introduces Gumbel-IPF networks for learning latent partial matchings. At the core of our method is the differentiable Iterative Proportional Fitting (IPF) procedure that biproportionally projects onto the transportation polytope of target marginals. Our theoretical framework also allows drawing samples from the temperature-dependent partial matching distribution. We investigate the properties of common-practice relaxations through the lens of biproportional fitting and introduce a new metric, the empirical prediction shift. Our method’s advantages are demonstrated in experimental results on the semantic keypoints partial matching task on the Pascal VOC, IMC-PT-SparseGM, and CUB2001 datasets.

Multi-graph matching is a prominent structured prediction task, in which the predicted label is constrained to the space of cycle-consistent matchings. While direct loss minimization is an effective method for learning predictors over structured label spaces, it cannot be applied efficiently to the problem at hand, since executing a specialized solver across sets of matching predictions is computationally prohibitive. Moreover, there’s no supervision on the ground-truth matchings over cycle-consistent prediction sets. Our key insight is to strictly enforce the matching constraints in pairwise matching predictions and softly enforce the cycle-consistency constraints by casting them as weighted loss terms, such that the severity of inconsistency with global predictions is tuned by a penalty parameter. Inspired by the classic penalty method, we prove that our method theoretically recovers the optimal multi-graph matching constrained solution. Our method’s advantages are brought to light in experimental results on the popular keypoint matching task on the Pascal VOC and the Willow ObjectClass datasets.

The success of deep neural nets heavily relies on their ability to encode complex relations between their input and their output. While this property serves to fit the training data well, it also obscures the mechanism that drives prediction. This study aims to reveal hidden concepts by employing an intervention mechanism that shifts the predicted class based on discrete variational autoencoders. An explanatory model then visualizes the encoded information from any hidden layer and its corresponding intervened representation. By the assessment of differences between the original representation and the intervened representation, one can determine the concepts that can alter the class, hence providing interpretability. We demonstrate the effectiveness of our approach on CelebA, where we show various visualizations for bias in the data and suggest different interventions to reveal and change bias.

Contemporary predictive models are hard to interpret as their deep nets exploit numerous complex relations between input elements. This work suggests a theoretical framework for model interpretability by measuring the contribution of relevant features to the functional entropy of the network with respect to the input. We rely on the log-Sobolev inequality that bounds the functional entropy by the functional Fisher information with respect to the covariance of the data. This provides a principled way to measure the amount of information contribution of a subset of features to the decision function. Through extensive experiments, we show that our method surpasses existing interpretability sampling-based methods on various data signals such as image, text, and audio.

A key concern in integrating machine learning models in medicine is the ability to interpret their reasoning. Popular explainability methods have demonstrated satisfactory results in natural image recognition, yet in medical image analysis, many of these approaches provide partial and noisy explanations. Recently, attention mechanisms have shown compelling results both in their predictive performance and in their interpretable qualities. A fundamental trait of attention is that it leverages salient parts of the input which contribute to the model’s prediction. To this end, our work focuses on the explanatory value of attention weight distributions. We propose a multi-layer attention mechanism that enforces consistent interpretations between attended convolutional layers using convex optimization. We apply duality to decompose the consistency constraints between the layers by reparameterizing their attention probability distributions. We further suggest learning the dual witness by optimizing with respect to our objective; thus, our implementation uses standard back-propagation, hence it is highly efficient. While preserving predictive performance, our proposed method leverages weakly annotated medical imaging data and provides complete and faithful explanations to the model’s prediction.

Generalization bounds which assess the difference between the true risk and the empirical risk have been studied extensively. However, to obtain bounds, current techniques use strict assumptions such as a uniformly bounded or a Lipschitz loss function. To avoid these assumptions, in this paper, we follow an alternative approach: we relax uniform bounds assumptions by using on-average bounded loss and on-average bounded gradient norm assumptions. Following this relaxation, we propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. These inequalities add an additional loss-gradient norm term to the generalization bound, which is intuitively a surrogate of the model complexity. We apply the proposed bound on Bayesian deep nets and empirically analyze the effect of this new loss-gradient norm term on different neural architectures.

We present a method for matching a text sentence from a given corpus to a given video clip and vice versa. Traditionally video and text matching is done by learning a shared embedding space and the encoding of one modality is independent of the other. In this work, we encode the dataset data in a way that takes into account the query’s relevant information. The power of the method is demonstrated to arise from pooling the interaction data between words and frames. Since the encoding of the video clip depends on the sentence compared to it, the representation needs to be recomputed for each potential match. To this end, we propose an efficient shallow neural network. Its training employs a hierarchical triplet loss that is extendable to paragraph/video matching. The method is simple, provides explainability, and achieves state-of-the-art results for both sentence-clip and video-text by a sizable margin across five different datasets: ActivityNet, DiDeMo, YouCook2, MSR-VTT, and LSMDC. We also show that our conditioned representation can be transferred to video-guided machine translation, where we improved the current results on VATEX. Source code is available at https://github.com/AmeenAli/VideoMatch.

This work focuses on object goal visual navigation, aiming at finding the location of an object from a given class, where in each step the agent is provided with an egocentric RGB image of the scene. We propose to learn the agent’s policy using a reinforcement learning algorithm. Our key contribution is a novel attention probability model for visual navigation tasks. This attention encodes semantic information about observed objects, as well as spatial information about their place. This combination of the "what" and the "where" allows the agent to navigate toward the sought-after object effectively. The attention model is shown to improve the agent’s policy and to achieve state-of-the-art results on commonly-used datasets.

Direct loss minimization is a popular approach for learning predictors over structured label spaces. This approach is computationally appealing as it replaces integration with optimization and allows to propagate gradients in a deep net using loss-perturbed prediction. Recently, this technique was extended to generative models, by introducing a randomized predictor that samples a structure from a randomly perturbed score function. In this work, we interpolate between these techniques by learning the variance of randomized structured predictors as well as their mean, in order to balance between the learned score function and the randomized noise. We demonstrate empirically the effectiveness of learning this balance in structured discrete spaces.

To perform counterfactual reasoning in Structural Causal Models (SCMs), one needs to know the causal mechanisms, which provide factorizations of conditional distributions into noise sources and deterministic functions mapping realizations of noise to samples. Unfortunately, the causal mechanism is not uniquely identified by data that can be gathered by observing and interacting with the world, so there remains the question of how to choose causal mechanisms. In recent work, Oberst & Sontag (2019) propose Gumbel-max SCMs, which use Gumbel-max reparameterizations as the causal mechanism due to an appealing counterfactual stability property. However, the justification requires appealing to intuition. In this work, we instead argue for choosing a causal mechanism that is best under a quantitative criteria such as minimizing variance when estimating counterfactual treatment effects. We propose a parameterized family of causal mechanisms that generalize Gumbel-max. We show that they can be trained to minimize counterfactual effect variance and other losses on a distribution of queries of interest, yielding lower variance estimates of counterfactual treatment effect than fixed alternatives, also generalizing to queries not seen at training time.

Many recent datasets contain a variety of different data modalities, for instance, image, question, and answer data in visual question answering (VQA). When training deep net classifiers on those multi-modal datasets, the modalities get exploited at different scales, i.e., some modalities can more easily contribute to the classification results than others. This is suboptimal because the classifier is inherently biased towards a subset of the modalities. To alleviate this shortcoming, we propose a novel regularization term based on the functional entropy. Intuitively, this term encourages to balance the contribution of each modality to the classification result. However, regularization with the functional entropy is challenging. To address this, we develop a method based on the log-Sobolev inequality, which bounds the functional entropy with the functional-Fisher-information. Intuitively, this maximizes the amount of information that the modalities contribute. On the two challenging multi-modal datasets VQA-CPv2, and SocialIQ, we obtain state-of-the-art results while more uniformly exploiting the modalities. In addition, we demonstrate the efficacy of our method on Colored MNIST.

Direct optimization (McAllester et al., 2010; Song et al., 2016) is an appealing framework that replaces integration with optimization of a random objective for approximating gradients in models with discrete random variables (Lorberbom et al., 2018). A* sampling (Maddison et al., 2014) is a framework for optimizing such random objectives over large spaces. We show how to combine these techniques to yield a reinforcement learning algorithm that approximates a policy gradient by finding trajectories that optimize a random objective. We call the resulting algorithms \emph{direct policy gradient} (DirPG) algorithms. A main benefit of DirPG algorithms is that they allow the insertion of domain knowledge in the form of upper bounds on return-to-go at training time, like is used in heuristic search, while still directly computing a policy gradient. We further analyze their properties, showing there are cases where DirPG has an exponentially larger probability of sampling informative gradients compared to REINFORCE. We also show that there is a built-in variance reduction technique and that a parameter that was previously viewed as a numerical approximation can be interpreted as controlling risk sensitivity. Empirically, we evaluate the effect of key degrees of freedom and show that the algorithm performs well in illustrative domains compared to baselines.

We regard explanations as a blending of the input sample and the model's output and offer a few definitions that capture various desired properties of the function that generates these explanations. We study the links between these properties and between explanation-generating functions and intermediate representations of learned models and are able to show, for example, that if the activations of a given layer are consistent with an explanation, then so do all other subsequent layers. In addition, we study the intersection and union of explanations as a way to construct new explanations.

The recently proposed audio-visual scene-aware dialog task paves the way to a more data-driven way of learning virtual assistants, smart speakers and car navigation systems. However, very little is known to date about how to effectively extract meaningful information from a plethora of sensors that pound the computational engine of those devices. Therefore, in this paper, we provide and carefully analyze a simple baseline for audio-visual scene-aware dialog which is trained end-to-end. Our method differentiates in a data-driven manner useful signals from distracting ones using an attention mechanism. We evaluate the proposed approach on the recently introduced and challenging audio-visual scene-aware dataset, and demonstrate the key features that permit to outperform the current state-of-the-art by more than 20% on CIDEr.

Dialog is an effective way to exchange information, but subtle details and nuances are extremely important. While significant progress has paved a path to address visual dialog with algorithms, details and nuances remain a challenge. Attention mechanisms have demonstrated compelling results to extract details in visual question answering and also provide a convincing framework for visual dialog due to their interpretability and effectiveness. However, the many data utilities that accompany visual dialog challenge existing attention techniques. We address this issue and develop a general attention mechanism for visual dialog which operates on any number of data utilities. To this end, we design a factor graph based attention mechanism which combines any number of utility representations. We illustrate the applicability of the proposed approach on the challenging and recently introduced VisDial datasets, outperforming recent state-of-the-art methods by 1.1% for VisDial0.9 and by 2% for VisDial1.0 on MRR. Our ensemble model improved the MRR score on VisDial1.0 by more than 6%.

Reparameterization of variational auto-encoders with continuous random variables is an effective method for reducing the variance of their gradient estimates. In the discrete case, one can perform reparametrization using the Gumbel-Max trick, but the resulting objective relies on an $\arg \max$ operation and is non-differentiable. In contrast to previous works which resort to \emph{softmax}-based relaxations, we propose to optimize it directly by applying the \emph{direct loss minimization} approach. Our proposal extends naturally to structured discrete latent variable models when evaluating the $\arg \max$ operation is tractable. We demonstrate empirically the effectiveness of the direct loss minimization technique in variational autoencoders with both unstructured and structured discrete latent variables.

The best solution of structured prediction models in NLP is often inaccurate because of limited expressive power of the model or to non-exact parameter estimation. One way to mitigate this problem is sampling candidate solutions from the model’s solution space, reasoning that effective exploration of this space should yield high-quality solutions. Unfortunately, sampling is often computationally hard and many works hence back-off to sub-optimal strategies, such as extraction of the best scoring solutions of the model, which are not as diverse as sampled solutions. In this paper we propose a perturbation-based approach where sampling from a probabilistic model is computationally efficient. We present a learning algorithm for the variance of the perturbations, and empirically demonstrate its importance. Moreover, while finding the argmax in our model is intractable, we propose an efficient and effective approximation. We apply our framework to cross-lingual dependency parsing across 72 corpora from 42 languages and to lightly supervised dependency parsing across 13 corpora from 12 languages, and demonstrate strong results in terms of both the quality of the entire solution list and of the final solution.1

This paper presents a new approach, called perturb-max, for high-dimensional statistical inference in graphical models that is based on applying random perturbations followed by optimization. This framework injects randomness into maximum a-posteriori (MAP) predictors by randomly perturbing the potential function for the input. A classic result from extreme value statistics asserts that perturb-max operations generate unbiased samples from the Gibbs distribution using high-dimensional perturbations. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. However, when the perturbations are of low dimension, sampling the perturb-max prediction is as efficient as MAP optimization. This paper shows that the expected value of perturb-max inference with low dimensional perturbations can be used sequentially to generate unbiased samples from the Gibbs distribution. Furthermore the expected value of the maximal perturbations is a natural bound on the entropy of such perturb-max models. A measure concentration result for perturb-max values shows that the deviation of their sampled average from its expectation decays exponentially in the number of samples, allowing effective approximation of the expectation.

One of the common ways to perform indoor localization for pedestrians is to employ the smartphone's inertial sensors, in a process known as pedestrian dead reckoning (PDR). Estimation of the pedestrian's heading is a crucial step in PDR algorithms, since it is a key factor in the positioning accuracy. In this paper, rather than assuming the smartphone to be fixed in a certain orientation on the pedestrian, we focus on estimating the vertical direction within the sensor frame of an unconstrained device. To that end, we establish a framework for gravity direction estimation and highlight the important role it has for solving the heading in the horizontal plane. By employing only accelerometers and gyroscopes, we derive, present and compare different approaches both for estimating the gravity direction and for computing the heading angle. The results are demonstrated and analyzed using data recorded from field experiments.

In this work we consider non-linear classifiers that comprise intersections of hyperplanes. We learn these classifiers by minimizing the “minimax” bound over the negative training examples and the hinge type loss of the positive training examples. These classifiers fit typical real-life datasets that consist of a small number of positive data points and a large number of negative data points. Such an approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, which is used in a single constraint on the empirical risk, as opposed to SVM, in which the number of variables is equal to the size of the training set. We first focus on intersection of $K$ hyperplanes, for which we provide empirical risk bounds. We show that these bounds are dimensionally independent and decay as $K/\sqrt{m}$ for $m$ samples. We then extend the K-hyperplane mixed risk to the latent mixed risk for training a union of $C$ $K$-hyperplane models, which can form an arbitrary complex, piecewise linear boundaries. We propose efficient algorithms for training the proposed models. Finally, we show how to combine hinge-minimax training with deep architectures and extend it to multi-class settings using transfer learning. The empirical evaluation of the proposed models shows their advantage over the existing methods in a small training labeled data regime.

We introduce a synergetic approach incorporating psychological theories and data science in service of predicting human behavior. Our method harnesses psychological theories to extract rigorous features to a data science algorithm. We demonstrate that this approach can be extremely powerful in a fundamental human choice setting. In particular, a random forest algorithm that makes use of psychological features that we derive, dubbed psychological forest, leads to prediction that significantly outperforms best practices in a choice prediction competition. Our results also suggest that this integrative approach is vital for data science tools to perform reasonably well on the data. Finally, we discuss how social scientists can learn from using this approach and conclude that integrating social and data science practices is a highly fruitful path for future research of human behavior.

We revisit the study of optimal regret rates in bandit combinatorial optimization—a fundamental framework for sequential decision making under uncertainty that abstracts numerous combinatorial prediction problems. We prove that the attainable regret in this setting grows as $\widetildeΘ(k^3/2\sqrt{d}T)$ where $d$ is the dimension of the problem and $k$ is a bound over the maximal instantaneous loss, disproving a conjecture of Audibert, Bubeck, and Lugosi (2013) who argued that the optimal rate should be of the form $\widetildeΘ(k\sqrt{d}T)$. Our bounds apply to several important instances of the framework, and in particular, imply a tight bound for the well-studied bandit shortest path problem. By that, we also resolve an open problem posed by Cesa-Bianchi and Lugosi (2012).

The quest for algorithms that enable cognitive abilities is an important part of machine learning. A common trait in many recently investigated cognitive-like tasks is that they take into account different data modalities, such as visual and textual input. In this paper we propose a novel and generally applicable form of attention mechanism that learns high-order correlations between various data modalities. We show that high-order correlations effectively direct the appropriate attention to the relevant elements in the different data modalities that are required to solve the joint task. We demonstrate the effectiveness of our high-order attention mechanism on the task of visual question answering (VQA), where we achieve state-of-the-art performance on the standard VQA dataset.

We study an online learning framework introduced by Mannor and Shamir (2011) in which the feedback is specified by a graph, in a setting where the graph may vary from round to round and is \emphnever fully revealed to the learner. We show a large gap between the adversarial and the stochastic cases. In the adversarial case, we prove that even for dense feedback graphs, the learner cannot improve upon a trivial regret bound obtained by ignoring any additional feedback besides her own loss. In contrast, in the stochastic case we give an algorithm that achieves \widetildeΘ(\sqrtαT) regret over T rounds, provided that the independence numbers of the hidden feedback graphs are at most α. We also extend our results to a more general feedback model, in which the learner does not necessarily observe her own loss, and show that, even in simple cases, concealing the feedback graphs might render the problem unlearnable.

Inference in Markov random fields subject to consistency structure is a fundamental problem that arises in many real-life applications. In order to enforce consistency, classical approaches utilize consistency potentials or encode constraints over feasible instances. Unfortunately this comes at the price of a serious computational bottleneck. In this paper we suggest to tackle consistency by incorporating constraints on beliefs. This permits derivation of a closed-form message-passing algorithm which we refer to as the Constraints Based Convex Belief Propagation (CBCBP). Experiments show that CBCBP outperforms the standard approach while being at least an order of magnitude faster.

Conditional random fields maximize the log-likelihood of training labels given the training data, e.g., objects given images. In many cases the training labels are structures that consist of a set of variables and the computational complexity for estimating their likelihood is exponential in the number of the variables. Learning algorithms relax this computational burden using approximate inference that is nested as a sub- procedure. In this paper we describe the objective function for nested learning and inference in conditional random fields. The devised objective maximizes the log-beliefs --- probability distributions over subsets of training variables that agree on their marginal probabilities. This objective is concave and consists of two types of variables that are related to the learning and inference tasks respectively. Importantly, we afterwards show how to blend the learning and inference procedure and effectively get to the identical optimum much faster. The proposed algorithm currently achieves the state-of- the-art in various computer vision applications.

Structured output prediction is a powerful framework for jointly predicting interdependent output labels. Learning the parameters of structured predictors is a central task in machine learning applications. However, training the model from data often becomes computationally expensive. Several methods have been proposed to exploit the model structure, or decomposition, in order to obtain efficient training algorithms. In particular, methods based on linear programming relaxation, or dual decomposition, decompose the prediction task into multiple simpler prediction tasks and enforce agreement between overlapping predictions. In this work we observe that relaxing these agreement constraints and replacing them with soft constraints yields a much easier optimization problem. Based on this insight we propose an alternative training objective, analyze its theoretical properties, and derive an algorithm for its optimization. Our method, based on the Frank-Wolfe algorithm, achieves significant speedups over existing state-of-the-art methods without hurting prediction accuracy.

We investigate a new Follow the Perturbed Leader (FTPL) algorithm for online structured prediction problems. We show a regret bound which is comparable to the state of the art of FTPL algorithms and is comparable with the best possible regret in some cases. To better understand FTPL algorithms for online structured learning, we present a lower bound on the regret for a large and natural class of FTPL algorithms that use logconcave perturbations. We complete our investigation with an online shortest path experiment and empirically show that our algorithm is both statistically and computationally efficient.

We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition.

Perturbation models are families of distributions induced from perturbations. They combine randomization of the parameters with maximization to draw unbiased samples. Unlike Gibbs’ distributions, a perturbation model defined on the basis of low order statistics still gives rise to high order dependencies. In this paper, we analyze, extend and seek to estimate such dependencies from data. In particular, we shift the modelling focus from the parameters of the Gibbs’ distribution used as a base model to the space of perturbations. We estimate dependent perturbations over the parameters using a hard-EM approach, cast in the form of inverse convex programs. Each inverse program confines the randomization to the parameter polytope responsible for generating the observed answer. We illustrate the method on several computer vision problems.

Computational education offers an important add-on to conventional teaching. To provide optimal learning conditions, accurate representation of students’ current skills and adaptation to newly acquired knowledge are essential. To obtain sufficient representational power we investigate suitability of general graphical models and discuss adaptation by learning parameters of a log-linear distribution. For interpretability we propose to constrain the parameter space a-priori by leveraging domain knowledge. We show the benefits of general graphical models and of regularizing the parameter space by evaluation of our models on data collected from a computational education software for children having difficulties in learning mathematics.

We address the problem of efficiently annotating labels of objects when they are structured. Often the distribution over labels can be described using a joint potential function over the labels for which sampling is provably hard but efficient maximum a-posteriori (MAP) solvers exist. In this setting we develop novel entropy bounds that are based on the expected amount of perturbation to the potential function that is needed to change MAP decisions. By reasoning about the entropy reduction and cost tradeoff, our algorithm actively selects the next annotation task. As an example of our framework we propose a boundary refinement task which can used to obtain pixel-accurate image boundaries much faster than traditional tools by focussing on parts of the image for refinement in a multi-scale manner.

We present a tool for re-ranking the results of a specific query by considering the (n+1) × (n+1) matrix of pairwise similarities among the elements of the set of n retrieved results and the query itself. The re-ranking thus makes use of the similarities between the various results and does not employ additional sources of information. The tool is based on graphical Bayesian models, which reinforce retrieved items strongly linked to other retrievals, and on repeated clustering to measure the stability of the obtained associations. The utility of the tool is demonstrated within the context of visual search of documents from the Cairo Genizah and for retrieval of paintings by the same artist and in the same style.

The maximum a-posteriori (MAP) perturbation framework has emerged as a useful approach for inference and learning in high dimensional complex models. By maximizing a randomly perturbed potential function, MAP perturbations generate unbiased samples from the Gibbs distribution. Unfortunately, the computational cost of generating so many high-dimensional random variables can be prohibitive. More efficient algorithms use sequential sampling strategies based on the expected value of low dimensional MAP perturbations. This paper develops new measure concentration inequalities that bound the number of samples needed to estimate such expected values. Applying the general result to MAP perturbations can yield a more efficient algorithm to approximate sampling from the Gibbs distribution. The measure concentration result is of general interest and may be applicable to other areas involving Monte Carlo estimation of expectations.

While MAP inference is typically intractable for many real-world applications, linear programming relaxations have been proven very effective. Dual block-coordinate descent methods are among the most efficient solvers, however, they are prone to get stuck in sub-optimal points. Although subgradient approaches achieve global convergence, they are typically slower in practice. To improve convergence speed, algorithms which compute the steepest ε-descent direction by solving a quadratic program have been proposed. In this paper we suggest to decouple the quadratic program based on the Frank-Wolfe approach. This allows us to obtain an efficient and easy to parallelize algorithm while retaining the global convergence properties. Our method proves superior when compared to existing algorithms on a set of spin-glass models and protein design tasks.

In this paper we describe how MAP inference can be used to sample efficiently from Gibbs distributions. Specifically, we provide means for drawing either approximate or unbiased samples from Gibbs' distributions by introducing low dimensional perturbations and solving the corresponding MAP assignments. Our approach also leads to new ways to derive lower bounds on partition functions. We demonstrate empirically that our method excels in the typical high signal - high coupling'' regime. The setting results in ragged energy landscapes that are challenging for alternative approaches to sampling and/or lower bounds. "

In this work we develop efficient methods for learning random MAP predictors for structured label problems. In particular, we construct posterior distributions over perturbations that can be adjusted via stochastic gradient methods. We show that every smooth posterior distribution would suffice to define a smooth PAC-Bayesian risk bound suitable for gradient methods. In addition, we relate the posterior distributions to computational properties of the MAP predictors. We suggest multiplicative posteriors to learn super-modular potential functions that accompany specialized MAP predictors such as graph-cuts. We also describe label-augmented posterior models that can use efficient MAP approximations, such as those arising from linear program relaxations.

Existing approaches to indoor scene understanding formulate the problem as a structured prediction task focusing on estimating the 3D bounding box which best describes the scene layout. Unfortunately, these approaches utilize high order potentials which are computationally intractable and rely on ad-hoc approximations for both learning and inference. In this paper we show that the potentials commonly used in the literature can be decomposed into pair-wise potentials by extending the concept of integral images to geometry. As a consequence no heuristic reduction of the search space is required. In practice, this results in large improvements in performance over the state-of-the-art, while being orders of magnitude faster.

While finding the exact solution for the MAP inference problem is intractable for many real-world tasks, MAP LP relaxations have been shown to be very effective in practice. However, the most efficient methods that perform block coordinate descent can get stuck in sub-optimal points as they are not globally convergent. In this work we propose to augment these algorithms with an $\epsilon$-descent approach and present a method to efficiently optimize for a descent direction in the subdifferential using a margin-based extension of the Fenchel-Young duality theorem. Furthermore, the presented approach provides a methodology to construct a primal optimal solution from its dual optimal counterpart. We demonstrate the efficiency of the presented approach on spin glass models and protein interactions problems and show that our approach outperforms state-of-the-art solvers.

In this paper we propose a distributed message-passing algorithm for inference in large scale graphical models. Our method can handle large problems efficiently by distributing and parallelizing the computation and memory requirements. The convergence and optimality guarantees of recently developed message-passing algorithms are preserved by introducing new types of consistency messages, sent between the distributed computers. We demonstrate the effectiveness of our approach in the task of stereo reconstruction from high-resolution imagery, and show that inference is possible with more than 200 labels in images larger than 10 MPixels.

We describe a new approach for phoneme recognition which aims at minimizing the phoneme error rate. Building on structured prediction techniques, we formulate the phoneme recognizer as a linear combination of feature functions. We state a PAC-Bayesian generalization bound, which gives an upper-bound on the expected phoneme error rate in terms of the empirical phoneme error rate. Our algorithm is derived by finding the gradient of the PAC-Bayesian bound and minimizing it by stochastic gradient descent. The resulting algorithm is iterative and easy to implement. Experiments on the TIMIT corpus show that our method achieves the lowest phoneme error rate compared to other discriminative and generative models with the same expressive power.

In this paper we propose an approximated learning framework for large scale graphical models and derive message passing algorithms for learning their parameters efficiently. We first relate CRFs and structured SVMs and show that in the CRF's primal a variant of the log-partition function, known as soft-max, smoothly approximates the hinge loss function of structured SVMs. We then propose an intuitive approximation for structured prediction problems using Fenchel duality based on a local entropy approximation that computes the exact gradients of the approximated problem and is guaranteed to converge. Unlike existing approaches, this allow us to learn graphical models with cycles and very large number of parameters efficiently. We demonstrate the effectiveness of our approach in an image denoising task. This task was previously solved by sharing parameters across cliques. In contrast, our algorithm is able to efficiently learn large number of parameters resulting in orders of magnitude better prediction.

In discriminative machine learning one is interested in training a system to optimize a certain desired measure of performance, or loss. In binary classification one typically tries to minimizes the error rate. But in structured prediction each task often has its own measure of performance such as the BLEU score in machine translation or the intersection-over-union score in PASCAL segmentation. The most common approaches to structured prediction, structural SVMs and CRFs, do not minimize the task loss: the former minimizes a surrogate loss with no guarantees for task loss and the latter minimizes log loss independent of task loss. The main contribution of this paper is a theorem stating that a certain perceptron-like learning rule, involving features vectors derived from loss-adjusted inference, directly corresponds to the gradient of task loss. We give empirical results on phonetic alignment of a standard test set from the TIMIT corpus, which surpasses all previously reported results on this problem.

Inference problems in graphical models can be represented as a constrained optimization of a free-energy function. In this paper, we treat both forms of probabilistic inference, estimating marginal probabilities of the joint distribution and finding the most probable assignment, through a unified message-passing algorithm architecture. In particular we generalize the belief propagation (BP) algorithms of sum-product and max-product and tree-reweighted (TRW) sum and max product algorithms (TRBP) and introduce a new set of convergent algorithms based on “convex-free-energy” and linear-programming (LP) relaxation as a zero-temperature of a convex-free-energy. The main idea of this work arises from taking a general perspective on the existing BP and TRBP algorithms while observing that they all are reductions from the basic optimization formula off+Σihiwhere the functionfis an extended-valued, strictly convex but nonsmooth and the functionshiare extended-valued functions (not necessarily convex). We use tools from convex duality to present the “primal-dual ascent” algorithm which is an extension of the Bregman successive projection scheme and is designed to handle optimization of the general typef+ Σihi. We then map the fractional-free-energy variational principle for approximate inference onto the optimization formula above and introduce the “norm-product” message-passing algorithm. Special cases of the norm-product include sum-product and max-product (BP algorithms), TRBP and NMPLP algorithms. When the fractional-free-energy is set to be convex (convex-free-energy) the norm-product is globally convergent for the estimation of marginal probabilities and for approximating the LP-relaxation. We also introduce another branch of the norm-product which arises as the “zero-temperature” of the convex-free-energy which we refer to as the “convex-max-product”. The convex-max-product is convergent (unlike max-product) and aims at solving the LP- relaxation.

We introduce a distributed algorithm for solving large scale support vector machines (SVM) problems. The algorithm divides the training set into a number of processing nodes each running independently an SVM sub-problem associated with its subset of training data. The algorithm is a parallel (Jacobi) block-update scheme derived from the convex conjugate (Fenchel duality) form of the original SVM problem. Each update step consists of a modified SVM solver running in parallel over the sub-problems followed by a simple global update. We derive bounds on the number of updates showing that the number of iterations (independent SVM applications on sub-problems) required to obtain a solution of accuracy isin is O(log(1/isin)). We demonstrate the efficiency and applicability of our algorithms by running on large scale experiments on standardized datasets while comparing the results to the state-of-the-art SVM solvers.

Several authors have noticed that the common representation of images as vectors is sub-optimal. The process of vectorization eliminates spatial relations between some of the nearby image measurements and produces a vector of a dimension which is the product of the measurements' dimensions. It seems that images may be better represented when taking into account their structure as a 2D (or multi-D) array. Our work bears similarities to recent work such as 2DPCA or Coupled Subspace Analysis in that we treat images as 2D arrays. The main difference, however, is that unlike previous work which separated representation from the discriminative learning stage, we achieve both by the same method. Our framework, "low-rank separators ", studies the use of a separating hyperplane which are constrained to have the structure of low-rank matrices. We first prove that the low-rank constraint provides preferable generalization properties. We then define two "low-rank SVM problems" and propose algorithms to solve these. Finally, we provide supporting experimental evidence for the framework.

We introduce the Tsallis divergence error measure in the context of pLSA matrix and tensor decompositions showing much improved performance in the presence of noise. The focus of our approach is on one hand to provide an optimization framework which extends (in the sense of a one parameter family) the Maximum Likelihood framework and on the other hand is theoretically guaranteed to provide robustness under clutter, noise and outliers in the measurement matrix under certain conditions. Specifically, the conditions under which our approach excels is when the measurement array (co-occurrences) is sparse — which happens in the application domain of "bag of visual words".

We introduce an algorithm for a non-negative 3D tensor factorization for the purpose of establishing a local parts feature decomposition from an object class of images. In the past, such a decomposition was obtained using non-negative matrix factorization (NMF) where images were vectorized before being factored by NMF. A tensor factorization (NTF) on the other hand preserves the 2D representations of images and provides a unique factorization (unlike NMF which is not unique). The resulting "factors" from the NTF factorization are both sparse (like with NMF) but also separable allowing efficient convolution with the test image. Results show a superior decomposition to what an NMF can provide on all fronts - degree of sparsity, lack of ghost residue due to invariant parts and efficiency of coding of around an order of magnitude better. Experiments on using the local parts decomposition for face detection using SVM and Adaboost classifiers demonstrate that the recovered features are discriminatory and highly effective for classification.

We derive algorithms for finding a non-negative n-dimensional tensor factorization (n-NTF) which includes the non-negative matrix factorization (NMF) as a particular case when n = 2. We motivate the use of n-NTF in three areas of data analysis: (i) connection to latent class models in statistics, (ii) sparse image coding in computer vision, and (iii) model selection problems. We derive a "direct" positive-preserving gradient descent algorithm and an alternating scheme based on repeated multiple rank-1 problems.

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) =< 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) =< (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 , < x1 x2, y >= ( )( ). 1 y2 x1 y1 x2 y2 The inner-product < A, B > over all p.s.d. matrices S has the form: < A, B > = < aijei ej, ( Gr Fr) bltel et > i,j r l,t = aijblt < ei ej, Grel Fret > 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 < A, B > 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: < A, B >= 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 < A, B >= 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, < A, B > 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 < A, B > of eqn. (1) and lifting operations on A, B. 3 Lifting Matrices onto Higher Dimensions The family of sim(A, B) =< 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) =< (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: < Ad, Bd >= trace (A ^ GrB)d ^ Fr . r By taking linear combinations of < Al, Bl >, 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 < ... < id n form a basis of the alternating d - f old tensor product of Rn, denoted as dRn. If A Rnk is a linear map on Rn sending points to Rk, then Ad is a linear map on dRn sending x1 ... xd to Ax1 ... Axd, i.e., sending points in dRn to points in dRk. The matrix representation of Ad is called the "d'th compound matrix" Cd(A) whose (i1, ..., id|j1, ..., jd) entry has the value det(A[i1, ..., id : j1, ..., jd]) where the determinant is of the d d block constructed by choosing the rows i1, ..., id and the columns j1, ..., jd of A. In other words, Cd(A) has n rows and k columns d d (instead of nd kd necessary for Ad) whose entries are equal to the d d minors of A. When k = d, Ck(A) is a vector known as the Grasmanian of A, and when n = k = d then Cd(A) = det(A). Finally, the identity (Ad) Bd = (A B)d specializes to (Ad) Bd = (A B)d which translates to the identity Cd(A) Cd(B) = Cd(A B) known as the Binet-Cauchy theorem [1]. Taken together, the "d-fold alternating kernel" d(A, B) is defined by: d(A, B) =< Ad, Bd >=< Cd(A), Cd(B) >= 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) =< Ad, Bd >=< Rd(A), Rd(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 < A, B > (eqn. 1) and non-linear versions l(A, B), Syml(A, B) (eqns. 2,3) which are group projections of the general kernel < Ad, Bd >. 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 < A, B > 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.