We assume i.i.d. data sampled from a mixture distribution with K components
along fixed d-dimensional linear subspaces and an additional outlier component.
For p>0, we study the simultaneous recovery of the K fixed subspaces by
minimizing the l_p-averaged distances of the sampled data points from any K
subspaces. Under some conditions, we show that if $0<p\leq1$, then all
underlying subspaces can be precisely recovered by l_p minimization with
overwhelming probability.

We consider the problem of using a factor model we call {\em spike-and-slab
sparse coding} (S3C) to learn features for a classification task. The S3C model
resembles both the spike-and-slab RBM and sparse coding. Since exact inference
in this model is intractable, we derive a structured variational inference
procedure and employ a variational EM training algorithm. Prior work on
approximate inference for this model has not prioritized the ability to exploit
parallel architectures and scale to enormous problem sizes.

An empirical investigation of the interaction of sample size and
discretization - in this case the entropy-based method CAIM (Class-Attribute
Interdependence Maximization) - was undertaken to evaluate the impact and
potential bias introduced into data mining performance metrics due to variation
in sample size as it impacts the discretization process. Of particular interest
was the effect of discretizing within cross-validation folds averse to outside
discretization folds.

Information theoretic active learning has been widely studied for
probabilistic models. For simple regression an optimal myopic policy is easily
tractable. However, for other tasks and with more complex models, such as
classification with nonparametric models, the optimal solution is harder to
compute. Current approaches make approximations to achieve tractability. We
propose an approach that expresses information gain in terms of predictive
entropies, and apply this method to the Gaussian Process Classifier (GPC).

We formulate a convex minimization to robustly recover a subspace from a
contaminated data set, partially sampled around it, and propose a fast
iterative algorithm to achieve the corresponding minimum. We establish exact
recovery by this minimizer, quantify the effect of noise and regularization,
explain how to take advantage of a known intrinsic dimension and establish
linear convergence of the iterative algorithm.

A beta-negative binomial (BNB) process is proposed, leading to a
beta-gamma-Poisson process, which may be viewed as a "multi-scoop"
generalization of the beta-Bernoulli process. The BNB process is augmented into
a beta-gamma-gamma-Poisson hierarchical structure, and applied as a
nonparametric Bayesian prior for an infinite Poisson factor analysis model. A
finite approximation for the beta process Levy random measure is constructed
for convenient implementation. Efficient MCMC computations are performed with
data augmentation and marginalization techniques.

We describe a simple and efficient procedure for approximating the L\'evy
measure of a $\text{Gamma}(\alpha,1)$ random variable. We use this
approximation to derive a finite sum-representation that converges almost
surely to Ferguson's representation of the Dirichlet process based on arrivals
of a homogeneous Poisson process. We compare the efficiency of our
approximation to several other well known approximations of the Dirichlet
process and demonstrate a substantial improvement.

Exact inference in the linear regression model with spike and slab priors is
often intractable. Expectation propagation (EP) can be used for approximate
inference. However, the regular sequential form of EP (R-EP) may fail to
converge in this model when the size of the training set is very small. As an
alternative, we propose a provably convergent EP algorithm (PC-EP).

Unbalanced data arises in many learning tasks such as clustering of
multi-class data, hierarchical divisive clustering and semisupervised learning.
Graph-based approaches are popular tools for these problems. Graph construction
is an important aspect of graph-based learning. We show that graph-based
algorithms can fail for unbalanced data for many popular graphs such as k-NN,
\epsilon-neighborhood and full-RBF graphs. We propose a novel graph
construction technique that encodes global statistical information into node
degrees through a ranking scheme.

Contemporary global optimization algorithms are based on local measures of
utility, rather than a probability measure over location and value of the
optimum. They thus attempt to collect low function values, not to learn about
the optimum. The reason for the absence of probabilistic global optimizers is
that the corresponding inference problem is intractable in several ways.

This work concerns the way that statistical models are used to make
decisions. In particular, we aim to merge the way estimation algorithms are
designed with how they are used for a subsequent task. Our methodology
considers the operational cost of carrying out a policy, based on a predictive
model. The operational cost becomes a regularization term in the learning
algorithm's objective function, allowing either an \textit{optimistic} or
\textit{pessimistic} view of possible costs.

We develop mask iterative hard thresholding algorithms (mask IHT and mask
DORE) for sparse image reconstruction of objects with known contour. The
measurements follow a noisy underdetermined linear model common in the
compressive sampling literature. Assuming that the contour of the object that
we wish to reconstruct is known and that the signal outside the contour is
zero, we formulate a constrained residual squared error minimization problem
that incorporates both the geometric information (i.e. the knowledge of the
object's contour) and the signal sparsity constraint.

Probabilistic graphical models combine the graph theory and probability
theory to give a multivariate statistical modeling. They provide a unified
description of uncertainty using probability and complexity using the graphical
model. Especially, graphical models provide the following several useful
properties:

- Graphical models provide a simple and intuitive interpretation of the
structures of probabilistic models. On the other hand, they can be used to
design and motivate new models.

While Gaussian probability densities are omnipresent in applied mathematics,
Gaussian cumulative probabilities are hard to calculate in any but the
univariate case. We offer here an empirical study of the utility of Expectation
Propagation (EP) as an approximate integration method for this problem. For
rectangular integration regions, the approximation is highly accurate. We also
extend the derivations to the more general case of polyhedral integration
regions. However, we find that in this polyhedral case, EP's answer, though
often accurate, can be almost arbitrarily wrong.

The Ward error sum of squares hierarchical clustering method has been very
widely used since its first description by Ward in a 1963 publication. It has
also been generalized in various ways. However there are different
interpretations in the literature and there are different implementations of
the Ward agglomerative algorithm in commonly used software systems, including
differing expressions of the agglomerative criterion. Our survey work and case
studies will be useful for all those involved in developing software for data
analysis using Ward's hierarchical clustering method.

Gaussian process models -also called Kriging models- are often used as
mathematical approximations of expensive experiments. However, the number of
observation required for building an emulator becomes unrealistic when using
classical covariance kernels when the dimension of input increases. In oder to
get round the curse of dimensionality, a popular approach is to consider
simplified models such as additive models.

This paper addresses the problem of estimating the latent dimensionality in
nonnegative matrix factorization (NMF). The estimation is done via automatic
relevance determination (ARD). Uncovering the model order is important as it is
necessary to strike the right balance between data fidelity and overfitting. We
propose a Bayesian model for NMF and two families of algorithms known as l1-ARD
and l2-ARD, each assuming different priors on the basis elements and the
activation coefficients.

Iterative information processing, either based on heuristics or analytical
frameworks, has been shown to be a very powerful tool for the design of
efficient, yet feasible, wireless receiver architectures. Within this context,
algorithms performing message-passing on a probabilistic graph, such as the
sum-product (SP) and variational message passing (VMP) algorithms, have become
increasingly popular.

The graphical lasso [Banerjee et al., 2008, Friedman et al., 2007b] is a
popular approach for learning the structure in an undirected Gaussian graphical
model, using $\ell_1$ regularization to control the number of zeros in the
precision matrix ?${\B\Theta}={\B\Sigma}^{-1}$. The R package glasso is
popular, fast, and allows one to efficiently build a path of models for
different values of the tuning parameter. Convergence of GLASSO can be tricky;
the converged precision matrix might not be the inverse of the estimated
covariance, and occasionally it fails to converge with warm starts.

In this paper, we give a new generalization error bound of Multiple Kernel
Learning (MKL) for a general class of regularizations, and discuss what kind of
regularization gives a favorable predictive accuracy. Our main target in this
paper is dense type regularizations including \ellp-MKL. According to the
recent numerical experiments, the sparse regularization does not necessarily
show a good performance compared with dense type regularizations.

Vapnik-Chervonenkis (VC) dimension is a fundamental measure of the
generalization capacity of learning algorithms. However, apart from a few
special cases, it is hard or impossible to calculate analytically. Vapnik et
al. [10] proposed a technique for estimating the VC dimension empirically.
While their approach behaves well in simulations, it could not be used to bound
the generalization risk of classifiers, because there were no bounds for the
estimation error of the VC dimension itself.

The popular cubic smoothing spline estimate of a regression function arises
as the minimizer of the penalized sum of squares $\sum_j(Y_j - {\mu}(t_j))^2 +
{\lambda}\int_a^b [{\mu}"(t)]^2 dt$, where the data are $t_j,Y_j$, $j=1,...,
n$. The minimization is taken over an infinite-dimensional function space, the
space of all functions with square integrable second derivatives. But the
calculations can be carried out in a finite-dimensional space.

Principal component analysis (PCA) is widely used for dimensionality
reduction, with well-documented merits in various applications involving
high-dimensional data, including computer vision, preference measurement, and
bioinformatics. In this context, the fresh look advocated here permeates
benefits from variable selection and compressive sampling, to robustify PCA
against outliers.

Linear and Quadratic Discriminant analysis (LDA/QDA) are common tools for
classification problems. For these methods we assume observations are normally
distributed within group. We estimate a mean and covariance matrix for each
group and classify using Bayes theorem. With LDA, we estimate a single, pooled
covariance matrix, while for QDA we estimate a separate covariance matrix for
each group. Rarely do we believe in a homogeneous covariance structure between
groups, but often there is insufficient data to separately estimate covariance
matrices.

We propose a novel method of introducing structure into existing machine
learning techniques by developing structure-based similarity and distance
measures. To learn structural information, low-dimensional structure of the
data is captured by solving a non-linear, low-rank representation problem. We
show that this low-rank representation can be kernelized, has a closed-form
solution, allows for separation of independent manifolds, and is robust to
noise.

We propose a scalable, efficient and statistically motivated computational
framework for Graphical Lasso (Friedman et al., 2007b) - a covariance
regularization framework that has received significant attention in the
statistics community over the past few years. Existing algorithms have trouble
in scaling to dimensions larger than a thousand. Our proposal significantly
enhances the state-of-the-art for such moderate sized problems and gracefully
scales to larger problems where other algorithms become practically infeasible.
This requires a few key new ideas.

We describe the first sub-quadratic sampling algorithm for the Multiplicative
Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close
connection between MAGM and the Kronecker Product Graph Model (KPGM) of
Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices
to sample small number of KPGM graphs and \emph{quilt} them together. Under
mild technical conditions our algorithm runs in $O((\log_2(n))^3 |E|)$ time,
where $n$ is the number of nodes and $|E|$ is the number of edges in the
sampled graph.

We introduce a new regression framework, Gaussian process regression networks
(GPRN), which combines the structural properties of Bayesian neural networks
with the non-parametric flexibility of Gaussian processes. This model
accommodates input dependent signal and noise correlations between multiple
response variables, input dependent length-scales and amplitudes, and
heavy-tailed predictive distributions. We derive both efficient Markov chain
Monte Carlo and variational Bayes inference procedures for this model.

We consider the problem of covariance matrix estimation in the presence of
latent variables. Under suitable conditions, it is possible to learn the
marginal covariance matrix of the observed variables via a tractable convex
program, where the concentration matrix of the observed variables is decomposed
into a sparse matrix (representing the graphical structure of the observed
variables) and a low rank matrix (representing the marginalization effect of
latent variables). We present an efficient first-order method based on split
Bregman to solve the convex problem.

We study the generalization performance of arbitrary online learning
algorithms trained on samples coming from a dependent source of data. We show
that the generalization error of any stable online algorithm concentrates
around its regret--an easily computable statistic of the online performance of
the algorithm--when the underlying ergodic process is $\beta$- or
$\phi$-mixing.

We consider the problem of learning the structure of Ising models (pairwise
binary Markov random fields) from i.i.d. samples. While several methods have
been proposed to accomplish this task, their relative merits and limitations
remain somewhat obscure. By analyzing a number of concrete examples, we show
that low-complexity algorithms often fail when the Markov random field develops
long-range correlations. More precisely, this phenomenon appears to be related
to the Ising model phase transition (although it does not coincide with it).

We present the discrete infinite logistic normal distribution (DILN), a
Bayesian nonparametric prior for mixed membership models. DILN is a
generalization of the hierarchical Dirichlet process (HDP) that models
correlation structure between the weights of the atoms at the group level. We
derive a representation of DILN as a normalized collection of gamma-distributed
random variables, and study its statistical properties. We consider
applications to topic modeling and derive a variational inference algorithm for
approximate posterior inference.

In this paper, we extend Meek's conjecture (Meek 1997) from directed and
acyclic graphs to chain graphs, and prove that the extended conjecture is true.
Specifically, we prove that if a chain graph H is an independence map of the
independence model induced by another chain graph G, then (i) G can be
transformed into H by a sequence of directed and undirected edge additions and
feasible splits and mergings, and (ii) after each operation in the sequence H
remains an independence map of the independence model induced by G.

We present a probabilistic model for natural images which is based on
Gaussian scale mixtures and a simple multiscale representation. In contrast to
the dominant approach to modeling whole images focusing on Markov random
fields, we formulate our model in terms of a directed graphical model. We show
that it is able to generate images with interesting higher-order correlations
when trained on natural images or samples from an occlusion based model.

We propose a non-parametric link prediction algorithm for a sequence of graph
snapshots over time. The model predicts links based on the features of its
endpoints, as well as those of the local neighborhood around the endpoints.
This allows for different types of neighborhoods in a graph, each with its own
dynamics (e.g, growing or shrinking communities). We prove the consistency of
our estimator, and give a fast implementation based on locality-sensitive
hashing.

Ensemble methods for supervised machine learning have become popular due to
their ability to accurately predict class labels with groups of simple,
lightweight "base learners." While ensembles offer computationally efficient
models that have good predictive capability they tend to be large and offer
little insight into the patterns or structure in a dataset. We consider an
ensemble technique that returns a model of ranked rules. The model accurately
predicts class labels and has the advantage of indicating which parameter
constraints are most useful for predicting those labels.

This article addresses the problem of classification method based on both
labeled and unlabeled data, where we assume that a density function for labeled
data is different from that for unlabeled data. We propose a semi-supervised
logistic regression model for classification problem along with the technique
of covariate shift adaptation. Unknown parameters involved in proposed models
are estimated by regularization with EM algorithm. A crucial issue in modeling
process is the choices of tuning parameters in our semi-supervised logistic
models.

Monte Carlo (MC) techniques are often used to estimate integrals of a
multivariate function using randomly generated samples of the function. In
light of the increasing interest in uncertainty quantification and robust
design applications in aerospace engineering, the calculation of expected
values of such functions (e.g. performance measures) becomes important.
However, MC techniques often suffer from high variance and slow convergence as
the number of samples increases.

The optimal selection of experimental conditions is essential to maximizing
the value of data for inference and prediction, particularly in situations
where experiments are time-consuming and expensive to conduct. We propose a
general mathematical framework and an algorithmic approach for optimal
experimental design with nonlinear simulation-based models; in particular, we
focus on finding sets of experiments that provide the most information about
targeted sets of parameters.

In this work we introduce a mixture of GPs to address the data association
problem, i.e. to label a group of observations according to the sources that
generated them. Unlike several previously proposed GP mixtures, the novel
mixture has the distinct characteristic of using no gating function to
determine the association of samples and mixture components. Instead, all the
GPs in the mixture are global and samples are clustered following
"trajectories" across input space.

We present a method to estimate block membership of nodes in a random graph
generated by a stochastic blockmodel. We use an embedding procedure motivated
by the random dot product graph model, a particular example of the latent
position model. The embedded vectors are clustered through minimization of a
mean square error/criteria. We prove that this method is consistent for
assigning nodes to blocks, as only a negligible number of nodes will be
mis-assigned. We prove consistency of the method for directed and undirected
graphs.

In many data mining applications collection of sufficiently large datasets is
the most time consuming and expensive. On the other hand, industrial methods of
data collection create huge databases, and make difficult direct applications
of the advanced machine learning algorithms. To address the above problems, we
consider active learning (AL), which may be very efficient either for the
experimental design or for the data filtering.

We investigate multi-task learning from an output space regularization
perspective. Most multi-task approaches tie together related tasks by
constraining them to share input spaces and function classes. In contrast to
this, we propose a multi-task paradigm which we call output space
regularization, in which the only constraint is that the output spaces of the
multiple tasks are related. We focus on a specific instance of output space
regularization, multi-task averaging, that is both widely applicable and
amenable to analysis.

Graphical models compactly capture stochastic dependencies amongst a
collection of random variables using a graph. Inference over graphical models
corresponds to finding marginal probability distributions given joint
probability distributions. Several inference algorithms rely on iterative
message passing between nodes. Although these algorithms can be generalized so
that the message passing occurs between clusters of nodes, there are limited
frameworks for finding such clusters. Moreover, current frameworks rely on
finding clusters that are overlapping.

In many scientific disciplines structures in high-dimensional data have to be
found, e.g., in stellar spectra, in genome data, or for face recognition tasks.
In this work we present a novel approach to non-linear dimensionality
reduction. It is based on fitting K-nearest neighbor regression to the
unsupervised regression framework for learning of low-dimensional manifolds.
Similar to related approaches that are mostly based on kernel methods,
unsupervised K-nearest neighbor (UKNN) regression optimizes latent variables
w.r.t.

Purely data driven approaches for machine learning present difficulties when
data is scarce relative to the complexity of the model or when the model is
forced to extrapolate. On the other hand, purely mechanistic approaches need to
identify and specify all the interactions in the problem at hand (which may not
be feasible) and still leave the issue of how to parameterize the system. In
this paper, we present a hybrid approach using Gaussian processes and
differential equations to combine data driven modelling with a physical model
of the system.

We consider the problem of training probabilistic conditional random fields
(CRFs) in the context of a task where performance is measured using a specific
loss function. While maximum likelihood is the most common approach to training
CRFs, it ignores the inherent structure of the task's loss function.

Kernel methods are among the most popular techniques in machine learning.
From a frequentist/discriminative perspective they play a central role in
regularization theory as they provide a natural choice for the hypotheses space
and the regularization functional through the notion of reproducing kernel
Hilbert spaces. From a Bayesian/generative perspective they are the key in the
context of Gaussian processes, where the kernel function is also known as the
covariance function.

Divergence estimators based on direct approximation of density-ratios without
going through separate approximation of numerator and denominator densities
have been successfully applied to machine learning tasks that involve
distribution comparison such as outlier detection, transfer learning, and
two-sample homogeneity test. However, since density-ratio functions often
possess high fluctuation, divergence estimation is still a challenging task in
practice.

This paper considers the robust and efficient implementation of Gaussian
process regression with a Student-t observation model. The challenge with the
Student-t model is the analytically intractable inference which is why several
approximative methods have been proposed. The expectation propagation (EP) has
been found to be a very accurate method in many empirical studies but the
convergence of the EP is known to be problematic with models containing
non-log-concave site functions such as the Student-t distribution.

Probabilistic principal component analysis (PPCA) seeks a low dimensional
representation of a data set in the presence of independent spherical Gaussian
noise, Sigma = (sigma^2)*I. The maximum likelihood solution for the model is an
eigenvalue problem on the sample covariance matrix. In this paper we consider
the situation where the data variance is already partially explained by other
factors, e.g. covariates of interest, or temporal correlations leaving some
residual variance.

A key problem in statistical modeling is model selection, how to choose a
model at an appropriate level of complexity. This problem appears in many
settings, most prominently in choosing the number ofclusters in mixture models
or the number of factors in factor analysis. In this tutorial we describe
Bayesian nonparametric methods, a class of methods that side-steps this issue
by allowing the data to determine the complexity of the model. This tutorial is
a high-level introduction to Bayesian nonparametric methods and contains
several examples of their application.

Due to space limitations, our submission "Source Separation and Clustering of
Phase-Locked Subspaces", accepted for publication on the IEEE Transactions on
Neural Networks in 2011, presented some results without proof. Those proofs are
provided in this paper.

It is of increasing importance to develop learning methods for ranking. In
contrast to many learning objectives, however, the ranking problem presents
difficulties due to the fact that the space of permutations is not smooth. In
this paper, we examine the class of rank-linear objective functions, which
includes popular metrics such as precision and discounted cumulative gain. In
particular, we observe that expectations of these gains are completely
characterized by the marginals of the corresponding distribution over
permutation matrices.

The exploration-exploitation tradeoff is among the central challenges of
reinforcement learning. A hypothetical exact Bayesian learner would provide the
optimal solution, but is intractable in general. I show that, however, in the
specific case of Gaussian process inference, it is possible to make analytic
statements about optimal learning of both rewards and transition dynamics, for
nonlinear, time-varying systems in continuous time and space, subject to a
relatively weak restriction on the dynamics. The solution is described by an
infinite-dimensional differential equation.

This paper addresses the problem of inferring sparse causal networks modeled
by multivariate auto-regressive (MAR) processes. Conditions are derived under
which the Group Lasso (gLasso) procedure consistently estimates sparse network
structure. The key condition involves a "false connection score." In
particular, we show that consistent recovery is possible even when the number
of observations of the network is far less than the number of parameters
describing the network, provided that the false connection score is less than
one.

Multidimensional scaling (MDS) is a class of projective algorithms
traditionally used to produce two- or three-dimensional visualizations of
datasets consisting of multidimensional objects or interobject distances.
Recently, metric MDS has been applied to the problems of graph embedding for
the purpose of approximate encoding of edge or path costs using node
coordinates in metric space. Several authors have also pointed out that for
data with an inherent hierarchical structure, hyperbolic target space may be a
more suitable choice for accurate embedding than Euclidean space.

In data sets with many more features than observations, independent screening
based on all univariate regression models leads to a computationally convenient
variable selection method. Recent efforts have shown that in the case of
generalized linear models, independent screening may suffice to capture all
relevant features with high probability, even in ultra-high dimension. It is
unclear whether this formal sure screening property is attainable when the
response is a right-censored survival time.

We define and discuss the first sparse coding algorithm based on closed-form
EM updates and continuous latent variables. The underlying generative model
consists of a flexibly parameterized `spike-and-slab' prior and a standard
Gaussian noise model. Closed-form solutions for E- and M-step equations are
derived by generalizing probabilistic PCA. The resulting EM algorithm infers
all model parameters including the level of sparsity, and it takes all modes of
a potentially multi-modal posterior into account.

We present a novel factor analysis method that can be applied to the
discovery of common factors shared among trajectories in multivariate time
series data. These factors satisfy a precedence-ordering property: certain
factors are recruited only after some other factors are activated.
Precedence-ordering arise in applications where variables are activated in a
specific order, which is unknown. The proposed method is based on a linear
model that accounts for each factor's inherent delays and relative order.

Nearest neighbor (k-NN) graphs are widely used in machine learning and data
mining applications, and our aim is to better understand what they reveal about
the cluster structure of the unknown underlying distribution of points.
Moreover, is it possible to identify spurious structures that might arise due
to sampling variability?

We consider the problem of learning a distance metric from a limited amount
of pairwise information as effectively as possible. The proposed SERAPH
(SEmi-supervised metRic leArning Paradigm with Hyper sparsity) is a direct and
substantially more natural approach for semi-supervised metric learning, since
the supervised and unsupervised parts are based on a unified information
theoretic framework.

Learning theory has largely focused on two main learning scenarios. The first
is the classical statistical setting where instances are drawn i.i.d. from a
fixed distribution and the second scenario is the online learning, completely
adversarial scenario where adversary at every time step picks the worst
instance to provide the learner with. It can be argued that in the real world
neither of these assumptions are reasonable. It is therefore important to study
problems with a range of assumptions on data.

Modern data acquisition routinely produces massive amounts of network data.
Though many methods and models have been proposed to analyze such data, the
research of network data is largely disconnected with the classical theory of
statistical learning and signal processing. In this paper, we present a new
framework for modeling network data, which connects two seemingly different
areas: network data analysis and compressed sensing. From a nonparametric
perspective, we model an observed network using a large dictionary.

Notwithstanding the popularity of conventional clustering algorithms such as
K-means and probabilistic clustering, their clustering results are sensitive to
the presence of outliers in the data. Even a few outliers can compromise the
ability of these algorithms to identify meaningful hidden structures rendering
their outcome unreliable. This paper develops robust clustering algorithms that
not only aim to cluster the data, but also to identify the outliers.

Many real-world problems encountered in several disciplines deal with the
modeling of time-series containing different underlying dynamical regimes, for
which probabilistic approaches are very often employed. In this paper we
describe several such approaches in the common framework of graphical models.
We give a unified overview of models previously introduced in the literature,
which is simpler and more comprehensive than previous descriptions and enables
us to highlight commonalities and differences among models that were not
observed in the past.

Graphical models, and in particular Bayesian networks, have been widely used
to investigate data in the biological and healthcare domains. This can be
attributed to the recent explosion of high-throughput data across these domains
and the importance of understanding the causal relationships between the
variables of interest. However, classic model validation techniques for
identifying significant edges rely on the choice of an ad-hoc threshold, which
is non-trivial and can have a pronounced impact on the conclusions of the
analysis.

The discovery of non-linear causal relationship under additive non-Gaussian
noise models has attracted considerable attention recently because of their
high flexibility. In this paper, we propose a novel causal inference algorithm
called least-squares independence regression (LSIR). LSIR learns the additive
noise model through the minimization of an estimator of the squared-loss mutual
information between inputs and residuals.

We theoretically investigate the convergence rate and support consistency
(i.e., correctly identifying the subset of non-zero coefficients in the large
sample limit) of multiple kernel learning (MKL). We focus on MKL with block-l1
regularization (inducing sparse kernel combination), block-l2 regularization
(inducing uniform kernel combination), and elastic-net regularization
(including both block-l1 and block-l2 regularization).

We present two sets of theoretical results on the grouped lasso with overlap
of Jacob, Obozinski and Vert (2009) in the linear regression setting. This
method allows for joint selection of predictors in sparse regression, allowing
for complex structured sparsity over the predictors encoded as a set of groups.
This flexible framework suggests that arbitrarily complex structures can be
encoded with an intricate set of groups. Our results show that this strategy
results in unexpected theoretical consequences for the procedure.

In this work I propose a frequency domain adaptation of the Expectation
Maximization (EM) algorithm to separate a family of sequential observations in
classes of similar dynamic structure, which can either mean non-stationary
signals of similar shape, or stationary signals with similar auto-covariance
function. It does this by viewing the magnitude of the discrete Fourier
transform (DFT) of the signals (or power spectrum) as a probability
density/mass function (pdf/pmf) on the unit circle: signals with similar
dynamics have similar pdfs; distinct patterns have distinct pdfs.

Kernel methods have become increasingly popular in a variety of machine
learning applications due to their flexibility and appealing algorithmic
properties. In the context of Bayesian inference, the kernel trick can be used
to construct nonparametric Bayesian methods directly from parametric models.
For example, Gaussian process regression can be derived from kernelising
Bayesian linear regression. Despite the success of the Gaussian process
framework, the kernel trick is rarely explicitly considered in the Bayesian
literature.

We derive generalization error bounds for stationary univariate
autoregressive (AR) models. We show that the stationarity assumption alone lets
us treat the estimation of AR models as a regularized kernel regression without
the need to further regularize the model arbitrarily. We thereby bound the
Rademacher complexity of AR models and apply existing Rademacher complexity
results to characterize the predictive risk of AR models. We demonstrate our
methods by predicting interest rate movements.

We present a probabilistic viewpoint to multiple kernel learning unifying
well-known regularised risk approaches and recent advances in approximate
Bayesian inference relaxations. The framework proposes a general objective
function suitable for regression, robust regression and classification that is
lower bound of the marginal likelihood and contains many regularised risk
approaches as special cases. Furthermore, we derive an efficient and provably
convergent optimisation algorithm.

We investigate the learning rate of multiple kernel leaning (MKL) with
elastic-net regularization, which consists of an $\ell_1$-regularizer for
inducing the sparsity and an $\ell_2$-regularizer for controlling the
smoothness. We focus on a sparse setting where the total number of kernels is
large but the number of non-zero components of the ground truth is relatively
small, and prove that elastic-net MKL achieves the minimax learning rate on the
$\ell_2$-mixed-norm ball.

We analyze a class of estimators based on convex relaxation for solving
high-dimensional matrix decomposition problems. The observations are the noisy
realizations of the sum of an (appproximately) low rank matrix $\Theta^\star$
with a second matrix $\Gamma^\star$ endowed with a complementary form of
low-dimensional structure. We derive a general theorem that gives upper bounds
on the Frobenius norm error for an estimate of the pair $(\Theta^\star,
\Gamma^\star)$ obtained by solving a convex optimization problem that combines
the nuclear norm with a general decomposable regularizer.

Research in a number of fields now requires the analysis of "multi-block"
data, in which multiple high-dimensional, and fundamentally disparate,
datatypes are available for a common set of objects. In this paper we introduce
Joint and Individual Variation Explained (JIVE), a general method for the
integrated analysis of multi-block data. The method decomposes a multi-block
dataset into a sum of three terms: a low-rank approximation capturing joint
variation across datatypes, low-rank approximations for structured variation
individual to each datatype, and residual noise.

We address the sparse signal recovery problem in the context of multiple
measurement vectors (MMV) when elements in each nonzero row of the solution
matrix are temporally correlated. Existing algorithms do not consider such
temporal correlations and thus their performance degrades significantly with
the correlations. In this work, we propose a block sparse Bayesian learning
framework which models the temporal correlations.

We study the scenario of graph-based clustering algorithms such as spectral
clustering. Given a set of data points, one first has to construct a graph on
the data points and then apply a graph clustering algorithm to find a suitable
partition of the graph. Our main question is if and how the construction of the
graph (choice of the graph, choice of parameters, choice of weights) influences
the outcome of the final clustering result.

Unsupervised discovery of latent representations, in addition to being useful
for density modeling, visualisation and exploratory data analysis, is also
increasingly important for learning features relevant to discriminative tasks.
Autoencoders, in particular, have proven to be an effective way to learn latent
codes that reflect meaningful variations in data. A continuing challenge,
however, is guiding an autoencoder toward representations that are useful for
particular discriminative tasks.

A collaborative convex framework for factoring a data matrix $X$ into a
non-negative product $AS$, with a sparse coefficient matrix $S$, is proposed.
We restrict the columns of the dictionary matrix $A$ to coincide with certain
columns of the data matrix $X$, thereby guaranteeing a physically meaningful
dictionary and dimensionality reduction. We use $l_{1,\infty}$ regularization
to select the dictionary from the data and show this leads to an exact convex
relaxation of $l_0$ in the case of distinct noise free data.

Existing approaches to analyzing the asymptotics of graph Laplacians
typically assume a well-behaved kernel function with smoothness assumptions. We
remove the smoothness assumption and generalize the analysis of graph
Laplacians to include previously unstudied graphs including kNN graphs. We also
introduce a kernel-free framework to analyze graph constructions with shrinking
neighborhoods in general and apply it to analyze locally linear embedding
(LLE).

A typical approach in estimating the learning rate of a regularized learning
scheme is to bound the approximation error by the sum of the sampling error,
the hypothesis error and the regularization error. Using a reproducing kernel
space that satisfies the linear representer theorem brings the advantage of
discarding the hypothesis error from the sum automatically. Following this
direction, we illustrate how reproducing kernel Banach spaces with the l1 norm
can be applied to improve the learning rate estimate of l1-regularization in
machine learning.

Efficient global optimization is the problem of minimizing an unknown
function f, using as few evaluations f(x) as possible. It can be considered as
a continuum-armed bandit problem, with noiseless data and simple regret.
Expected improvement is perhaps the most popular method for solving this
problem; the algorithm performs well in experiments, but little is known about
its theoretical properties. Implementing expected improvement requires a choice
of Gaussian process prior, which determines an associated space of functions,
its reproducing-kernel Hilbert space (RKHS).

Structural equation models and Bayesian networks have been widely used to
analyze causal relations between continuous variables. In such frameworks,
linear acyclic models are typically used to model the data-generating process
of variables. Recently, it was shown that use of non-Gaussianity identifies the
full structure of a linear acyclic model, i.e., a causal ordering of variables
and their connection strengths, without using any prior knowledge on the
network structure, which is not the case with conventional methods.

We consider the problem of online linear regression on arbitrary
deterministic sequences when the ambient dimension $d$ can be much larger than
the number of time rounds $T$. In this framework we prove deterministic online
counterparts of the so-called sparsity oracle inequalities introduced in the
stochastic setting in the past decade. They indicate that the task consisting
in predicting almost as well as an unknown high-dimensional target vector is
still statistically feasible if this target vector has only few non-zero
coordinates.

We study the problem of estimating a temporally varying coefficient and
varying structure (VCVS) graphical model underlying nonstationary time series
data, such as social states of interacting individuals or microarray expression
profiles of gene networks, as opposed to i.i.d. data from an invariant model
widely considered in current literature of structural estimation. In
particular, we consider the scenario in which the model evolves in a piece-wise
constant fashion.

We propose a novel algorithm to solve the expectation propagation relaxation
of Bayesian inference for continuous-variable graphical models. In contrast to
most previous algorithms, our method is provably convergent. By marrying
convergent EP ideas from (Opper&Winther 05) with covariance decoupling
techniques (Wipf&Nagarajan 08, Nickisch&Seeger 09), it runs at least an order
of magnitude faster than the most commonly used EP solver.

The goal of cross-domain object matching (CDOM) is to find correspondence
between two sets of objects in different domains in an unsupervised way. Photo
album summarization is a typical application of CDOM, where photos are
automatically aligned into a designed frame expressed in the Cartesian
coordinate system. CDOM is usually formulated as finding a mapping from objects
in one domain (photos) to objects in the other domain (frame) so that the
pairwise dependency is maximized.

For high-dimensional classification, it is well known that naively performing
the Fisher discriminant rule leads to poor results due to diverging spectra and
noise accumulation. Therefore, researchers proposed independence rules to
circumvent the diverse spectra, and sparse independence rules to mitigate the
issue of noise accumulation. However, in biological applications, there are
often a group of correlated genes responsible for clinical outcomes, and the
use of the covariance information can significantly reduce misclassification
rates.

We introduce block-tree graphs as a framework for deriving efficient
algorithms on graphical models. We define block-tree graphs as a
tree-structured graph where each node is a cluster of nodes such that the
clusters in the graph are disjoint. This differs from junction-trees, where two
clusters connected by an edge always have at least one common node.

Multiple kernel learning (MKL) has received considerable attention recently.
In this paper, we show how different MKL algorithms can be understood as
applications of different types of regularization on the kernel weights. Within
the regularization view we consider in this paper, the
Tikhonov-regularization-based formulation of MKL allows us to consider a
generative probabilistic model behind MKL. Based on this model, we propose
learning algorithms for the kernel weights through the maximization of
marginalized likelihood.

High density clusters can be characterized by the connected components of a
level set $L(\lambda) = \{x:\ p(x)>\lambda\}$ of the underlying probability
density function $p$ generating the data, at some appropriate level
$\lambda\geq 0$. The complete hierarchical clustering can be characterized by a
cluster tree ${\cal T}= \bigcup_{\lambda} L(\lambda)$. In this paper, we study
the behavior of a density level set estimate $\widehat L(\lambda)$ and cluster
tree estimate $\widehat{\cal{T}}$ based on a kernel density estimator with
kernel bandwidth $h$.

The performance of the Lasso is well understood under the assumptions of the
standard linear model with homoscedastic noise. However, in several
applications, the standard model does not describe the important features of
the data. This paper examines how the Lasso performs on a non-standard model
that is motivated by medical imaging applications. In these applications, the
variance of the noise scales linearly with the expectation of the observation.
Like all heteroscedastic models, the noise terms in this Poisson-like model are
\textit{not} independent of the design matrix.

One of the key challenges in sensor networks is the extraction of information
by fusing data from a multitude of distinct, but possibly unreliable sensors.
Recovering information from the maximum number of dependable sensors while
specifying the unreliable ones is critical for robust sensing. This sensing
task is formulated here as that of finding the maximum number of feasible
subsystems of linear equations, and proved to be NP-hard. Useful links are
established with compressive sampling, which aims at recovering vectors that
are sparse.

A density ratio is defined by the ratio of two probability densities. We
study the inference problem of density ratios and apply a semi-parametric
density-ratio estimator to the two-sample homogeneity test. In the proposed
test procedure, the f-divergence between two probability densities is estimated
using a density-ratio estimator. The f-divergence estimator is then exploited
for the two-sample homogeneity test.

We have developed an efficient algorithm for the maximum likelihood joint
tracking and association problem in a strong clutter for GMTI data. By using an
iterative procedure of the dynamic logic process "from vague-to-crisp," the new
tracker overcomes combinatorial complexity of tracking in highly-cluttered
scenarios and results in a significant improvement in signal-to-clutter ratio.

The group lasso is a penalized regression method, used in regression problems
where the covariates are partitioned into groups to promote sparsity at the
group level. Existing methods for finding the group lasso estimator either use
gradient projection methods to update the entire coefficient vector
simultaneously at each step, or update one group of coefficients at a time
using an inexact line search to approximate the optimal value for the group of
coefficients when all other groups' coefficients are fixed.

Actors in realistic social networks play not one but a number of diverse
roles depending on whom they interact with, and a large number of such
role-specific interactions collectively determine social communities and their
organizations. Methods for analyzing social networks should capture these
multi-faceted role-specific interactions, and, more interestingly, discover the
latent organization or hierarchy of social communities.

We consider the problem of learning a binary classifier from a training set
of positive and unlabeled examples, both in the inductive and in the
transductive setting. This problem, often referred to as \emph{PU learning},
differs from the standard supervised classification problem by the lack of
negative examples in the training set.

We study the problem of learning a sparse linear regression vector under
additional conditions on the structure of its sparsity pattern. This problem is
relevant in machine learning, statistics and signal processing. It is well
known that a linear regression can benefit from the knowledge that the
underlying regression vector is sparse. The combinatorial problem of selecting
the nonzero components of this vector can be ``relaxed'' by regularizing the
squared error with a convex penalty function like the $\ell_1$ norm.

A kernel method is proposed for realizing Bayes' rule, based on
representations of probability distributions in reproducing kernel Hilbert
spaces (RKHS). The empirical RKHS embeddings of the conditional probabilities
and prior are expressed as feature mappings of samples, and an RKHS embedding
of the posterior distribution is computed, again based on a feature mapping of
a sample. This kernel Bayes' rule can be applied to a wide variety of
nonparametric Bayesian inference problems. As an example, the approach is used
in filtering with a nonparametric state-space model.

We study the problem of learning a latent tree graphical model where samples
are available only from a subset of variables. We propose two consistent and
computationally efficient algorithms for learning minimal latent trees, that
is, trees without any redundant hidden nodes. Unlike many existing methods, the
observed nodes (or variables) are not constrained to be leaf nodes. Our first
algorithm, recursive grouping, builds the latent tree recursively by
identifying sibling groups using so-called information distances.

Identifying overlapping communities in networks is a challenging task. In
this work we present a novel approach to community detection that utilises the
Bayesian non-negative matrix factorisation (NMF) model to produce a
probabilistic output for node memberships. The scheme has the advantage of
computational efficiency, soft community membership and an intuitive
foundation. We present the performance of the method against a variety of
benchmark problems and compare and contrast it to several other algorithms for
community detection.

Inspired by the hierarchical hidden Markov models (HHMM), we present the
hierarchical semi-Markov conditional random field (HSCRF), a generalisation of
embedded undirectedMarkov chains tomodel complex hierarchical, nestedMarkov
processes. It is parameterised in a discriminative framework and has polynomial
time algorithms for learning and inference. Importantly, we consider
partiallysupervised learning and propose algorithms for generalised
partially-supervised learning and constrained inference.

Low-rank matrix approximations are often used to help scale standard machine
learning algorithms to large-scale problems. Recently, matrix coherence has
been used to characterize the ability to extract global information from a
subset of matrix entries in the context of these low-rank approximations and
other sampling-based algorithms, e.g., matrix com- pletion, robust PCA.

Undirected graphs are often used to describe high dimensional distributions.
Under sparsity conditions, the graph can be estimated using
{\ell}1-penalization methods. We propose and study the following method. We
combine a multiple regression approach with ideas of thresholding and
refitting: first we infer a sparse undirected graphical model structure via
thresholding of each among many {\ell}1-norm penalized regression functions; we
then estimate the covariance matrix and its inverse using the maximum
likelihood estimator.

We sharply characterize the performance of different penalization schemes for
the problem of selecting the relevant variables in the multi-task setting.
Previous work focuses on the regression problem where conditions on the design
matrix complicate the analysis. A clearer and simpler picture emerges by
studying the Normal means model. This model, often used in the field of
statistics, is a simplified model that provides a laboratory for studying
complex procedures.

Since learning is typically very slow in Boltzmann machines, there is a need
to restrict connections within hidden layers. However, the resulting states of
hidden units exhibit statistical dependencies. Based on this observation, we
propose using $l_1/l_2$ regularization upon the activation possibilities of
hidden units in restricted Boltzmann machines to capture the loacal
dependencies among hidden units.

Kernel Induced Random Survival Forests (KIRSF) is a statistical learning
algorithm which aims to improve prediction accuracy for survival data. As in
Random Survival Forests (RSF), Cumulative Hazard Function is predicted for each
individual in the test set. Prediction error is estimated using Harrell's
concordance index (C index) [Harrell et al. (1982)]. The C-index can be
interpreted as a misclassification probability and does not depend on a single
fixed time for evaluation. The C-index also specifically accounts for
censoring.

In the last few years, many different performance measures have been
introduced to overcome the weakness of the most natural metric, the Accuracy.
Among them, Matthews Correlation Coefficient has recently gained popularity
among researchers not only in machine learning but also in several application
fields such as bioinformatics. Nonetheless, further novel functions are being
proposed in literature.

Many problems of low-level computer vision and image processing, such as
denoising, deconvolution, tomographic reconstruction or super-resolution, can
be addressed by maximizing the posterior distribution of a sparse linear model
(SLM). We show how higher-order Bayesian decision-making problems, such as
optimizing image acquisition in magnetic resonance scanners, can be addressed
by querying the SLM posterior covariance, unrelated to the density's mode.

This paper proposes a nonparametric Bayesian method for exploratory data
analysis and feature construction in continuous time series. Our method focuses
on understanding shared features in a set of time series that exhibit
significant individual variability. Our method builds on the framework of
latent Diricihlet allocation (LDA) and its extension to hierarchical Dirichlet
processes, which allows us to characterize each series as switching between
latent ``topics'', where each topic is characterized as a distribution over
``words'' that specify the series dynamics.

Support vector machines (SVMs) are special kernel based methods and belong to
the most successful learning methods since more than a decade. SVMs can
informally be described as a kind of regularized M-estimators for functions and
have demonstrated their usefulness in many complicated real-life problems.
During the last years a great part of the statistical research on SVMs has
concentrated on the question how to design SVMs such that they are universally
consistent and statistically robust for nonparametric classification or
nonparametric regression purposes.

Distributions over permutations arise in applications ranging from
multi-object tracking to ranking of instances. The difficulty of dealing with
these distributions is caused by the size of their domain, which is factorial
in the number of considered entities ($n!$). It makes the direct definition of
a multinomial distribution over permutation space impractical for all but a
very small $n$. In this work we propose an embedding of all $n!$ permutations
for a given $n$ in a surface of a hypersphere defined in
$\mathbbm{R}^{(n-1)^2}$.

We define a class of Euclidean distances on weighted graphs, enabling to
perform thermodynamic soft graph clustering. The class can be constructed form
the "raw coordinates" encountered in spectral clustering, and can be extended
by means of higher-dimensional embeddings (Schoenberg transformations).
Geographical flow data, properly conditioned, illustrate the procedure as well
as visualization aspects.

We find the minimax rate of convergence in Hausdorff distance for estimating
a manifold M of dimension d embedded in R^D given a noisy sample from the
manifold. We assume that the manifold satisfies a smoothness condition and that
the noise distribution has compact support. We show that the optimal rate of
convergence is n^{-2/(2+d)}. Thus, the minimax rate depends only on the
dimension of the manifold, not on the dimension of the space in which M is
embedded.