This paper presents a novel manifold learning algorithm for high-dimensional data sets. The scope of the application focuses on the problem of motion tracking in video sequences. The framework presented is twofold. First, it is assumed that the samples are time ordered, providing valuable information that is not presented in the current methodologies. Second, the manifold topology comprises multiple charts, which contrasts to the most current methods that assume one single chart, being overly restrictive. The proposed algorithm, Gaussian process multiple local models (GP-MLM), can deal with arbitrary manifold topology by decomposing the manifold into multiple local models that are probabilistic combined using Gaussian process regression. In addition, the paper presents a multiple filter architecture where standard filtering techniques are integrated within the GP-MLM. The proposed approach exhibits comparable performance of state-of-the-art trackers, namely multiple model data association and deep belief networks, and compares favorably with Gaussian process latent variable models. Extensive experiments are presented using real video data, including a publicly available database of lip sequences and left ventricle ultrasound images, in which the GP-MLM achieves state of the art results.

The problem of learning a data-adaptive dictionary for a very large collection of signals is addressed. This paper proposes a statistical model and associated variational Bayesian (VB) inference for simultaneously learning the dictionary and performing sparse coding of the signals. The model builds upon beta process factor analysis (BPFA), with the number of factors automatically inferred, and posterior distributions are estimated for both the dictionary and the signals. Crucially, an online learning procedure is employed, allowing scalability to very large datasets which would be beyond the capabilities of existing batch methods. State-of-the-art performance is demonstrated by experiments with large natural images containing tens of millions of pixels.

The problem of large-scale online matrix completion is addressed via a Bayesian approach. The proposed method learns a factor analysis (FA) model for large matrices, based on a small number of observed matrix elements, and leverages the statistical model to actively select which new matrix entries/observations would be most informative if they could be acquired, to improve the model; the model inference and active learning are performed in an online setting. In the context of online learning, a greedy, fast and provably near-optimal algorithm is employed to sequentially maximize the mutual information between past and future observations, taking advantage of submodularity properties. Additionally, a simpler procedure, which directly uses the posterior parameters learned by the Bayesian approach, is shown to achieve slightly lower estimation quality, with far less computational effort. Inference is performed using a computationally efficient online variational Bayes (VB) procedure. Competitive results are obtained in a very large collaborative filtering problem, namely the Yahoo! Music ratings dataset.

This paper describes a methodology for detecting anomalies from sequentially observed and potentially noisy data. The proposed approach consists of two main elements: 1) filtering, or assigning a belief or likelihood to each successive measurement based upon our ability to predict it from previous noisy observations and 2) hedging, or flagging potential anomalies by comparing the current belief against a time-varying and data-adaptive threshold. The threshold is adjusted based on the available feedback from an end user. Our algorithms, which combine universal prediction with recent work on online convex programming, do not require computing posterior distributions given all current observations and involve simple primal-dual parameter updates. At the heart of the proposed approach lie exponential-family models which can be used in a wide variety of contexts and applications, and which yield methods that achieve sublinear per-round regret against both static and slowly varying product distributions with marginals drawn from the same exponential family. Moreover, the regret against static distributions coincides with the minimax value of the corresponding online strongly convex game. We also prove bounds on the number of mistakes made during the hedging step relative to the best offline choice of the threshold with access to all estimated beliefs and feedback signals. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality, as well as on the Enron email dataset.

A statistical framework for modeling and prediction of binary matrices is presented. The method is applied to social network analysis, specifically the database of US Supreme Court rulings. It is shown that the ruling behavior of Supreme Court judges can be accurately modeled by using a small number of latent features whose values evolve with time. The learned model facilitates the discovery of inter-relationships between judges and of the gradual evolution of their stances over time. In addition, the analysis in this paper extends previous results by considering automatic estimation of the number of latent features and other model parameters, based on a nonparametric-Bayesian approach. Inference is efficiently performed using Gibbs sampling.

We consider problems for which one has incomplete binary matrices that evolve with time (e.g., the votes of legislators on particular legislation, with each year characterized by a different such matrix). An objective of such analysis is to infer structure and inter-relationships underlying the matrices, here defined by latent features associated with each axis of the matrix. In addition, it is assumed that documents are available for the entities associated with at least one of the matrix axes. By jointly analyzing the matrices and documents, one may be used to inform the other within the analysis, and the model offers the opportunity to predict matrix values (e.g., votes) based only on an associated document (e.g., legislation). The research presented here merges two areas of machine-learning that have previously been investigated separately: incomplete-matrix analysis and topic modeling. The analysis is performed from a Bayesian perspective, with efficient inference constituted via Gibbs sampling. The framework is demonstrated by considering all voting data and available documents (legislation) during the 220-year lifetime of the United States Senate and House of Representatives.

This paper considers the problem of sequential assignment of probabilities (likelihoods) to elements of an individual sequence using an exponential family of probability distributions. We draw upon recent work on online convex programming to devise an algorithm that does not require computing posterior distributions given all current observations, involves simple primal-dual parameter updates, and achieves minimax per-round regret against slowly varying product distributions with marginals drawn from the same exponential family. We validate the theory on synthetic data drawn from a time-varying distribution over binary vectors of high dimensionality.

This paper addresses the problem of detecting anomalous multivariate co-occurrences using a limited number of unlabeled training observations. A novel method based on using a hypergraph representation of the data is proposed to deal with this very high-dimensional problem. Hypergraphs constitute an important extension of graphs which allow edges to connect more than two vertices simultaneously. A variational Expectation-Maximization algorithm for detecting anomalies directly on the hypergraph domain without any feature selection or dimensionality reduction is presented. The resulting estimate can be used to calculate a measure of anomalousness based on the False Discovery Rate. The algorithm has O(np) computational complexity, where n is the number of training observations and p is the number of potential participants in each co-occurrence event. This efficiency makes the method ideally suited for very high-dimensional settings, and requires no tuning, bandwidth or regularization parameters. The proposed approach is validated on both high-dimensional synthetic data and the Enron email database, where p > 75,000, and it is shown that it can outperform other state-of-the-art methods.

This paper describes a recursive estimation procedure for multivariate binary densities using orthogonal expansions. For $d$ covariates, there are $2^d$ basis coefficients to estimate, which renders conventional approaches computationally prohibitive when $d$ is large. However, for a wide class of densities that satisfy a certain sparsity condition, our estimator runs in probabilistic polynomial time and adapts to the unknown sparsity of the underlying density in two key ways: (1) it attains near-minimax mean-squared error, and (2) the computational complexity is lower for sparser densities. Our method also allows for flexible control of the trade-off between mean-squared error and computational complexity.

This paper discusses a collaborative framework for the legal certification of toll enforcement on motorways operated by Brisa Auto-Estradas de Portugal, based on the Advanced License Plate Recognition (ALPR) system/service. The developed ALPR service produces a composite JPEG picture documenting an irregular situation. An enforcement transaction is generated at Brisa’s toll infrastructure and later delivered to the toll clearing company Via Verde Portugal (VVP). This company processes the generated composite picture, matching it with the client data base and, if necessaty, pursuing legal action. The enforcement picture might also be delivered to other organizations, such as the official entity for car registration management, in Portugal the General Direction of Traffic (DGV). Certification is based on Public Key Infrastructure (PKI) and legal digital certificates. Its purpose is to guarantee the validation of an ALPR generated picture as genuine, at a court of law; any change will be detected by a validation service. The paper discusses the adopted strategy, considering not only technical but also organizational issues, since the trust required for the management of enforcement pictures along the involved networked organizations requires a set of procedures to be followed in order to ensure the required legal confidence (trust). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The problem of non-linear dimension reduction is relevant to many different areas of knowledge. While the linear case can be solved by variations of PCA, the non-linear case is more complex. Recent advances incorporate geometrical information by estimating a manifold that approximates the data. The paper follows that trend and tackles some limitations of existing approaches -arbitrary topology and curvature of the manifold, unknown intrinsic dimension and, for mixture models, unknown number of mixture components. An algorithm, designated TBA (tangent bundle approximation), is presented that addresses the enumerated difficulties and is faster than existing methods, in datasets of a few thousand points. The motivation behind TBA is to perform motion tracking in video sequences, but the algorithm can be applied in a wide class of problems. The paper starts with a brief review of related work and then describes the TBA approach in detail. The algorithm is then subjected to comparative evaluation.

There has been a surge of interest in learning non-linear manifold models to approximate high-dimensional data. Both for computational complexity reasons and for generalization capability, sparsity is a desired feature in such models. This usually means dimensionality reduction, which naturally implies estimating the intrinsic dimension, but it can also mean selecting a subset of the data to use as landmarks, which is especially important because many existing algorithms have quadratic complexity in the number of observations. This paper presents an algorithm for selecting landmarks, based on LASSO regression, which is well known to favor sparse approximations because it uses regularization with an l1 norm. As an added benefit, a continuous manifold parameterization, based on the landmarks, is also found. Experimental results with synthetic and real data illustrate the algorithm.