We describe Information Forests, an approach to classification that
generalizes Random Forests by replacing the splitting criterion of non-leaf
nodes from a discriminative one -- based on the entropy of the label
distribution -- to a generative one -- based on maximizing the information
divergence between the class-conditional distributions in the resulting
partitions. The basic idea consists of deferring classification until a measure
of "classification confidence" is sufficiently high, and instead breaking down
the data so as to maximize this measure.

In this paper, we derive Hybrid, Bayesian and Marginalized Cramer Rao Lower
Bounds (HCRB, BCRB and MCRB) for the single measurement vector and multiple
measurement vector Sparse Bayesian Learning (SBL) problem of estimating
compressible vectors and their prior distribution parameters. We assume the
unknown vector to be drawn from a compressible Student-t prior distribution. We
derive CRBs that encompass the deterministic or random nature of the unknown
parameters of the prior distribution and the regression noise variance.

Most machine learning algorithms, such as classification or regression, treat
the individual data point as the object of interest. Here we consider extending
machine learning algorithms to operate on groups of data points. We suggest
treating a group of data points as a set of i.i.d. samples from an underlying
feature distribution for the group. Our approach is to generalize kernel
machines from vectorial inputs to i.i.d. sample sets of vectors.

For a large multi-hop wireless network, nodes are preferable to make
distributed and localized link-scheduling decisions with only interactions
among a small number of neighbors. However, for a slowly decaying channel and
densely populated interferers, a small size neighborhood often results in
nontrivial link outages and is thus insufficient for making optimal scheduling
decisions. A question arises how to deal with the information outside a
neighborhood in distributed link-scheduling. In this work, we develop joint
approximation of information and distributed link scheduling.

We introduce a class of learning problems where the agent is presented with a
series of tasks. Intuitively, if there is relation among those tasks, then the
information gained during execution of one task has value for the execution of
another task. Consequently, the agent is intrinsically motivated to explore its
environment beyond the degree necessary to solve the current task it has at
hand. We develop a decision theoretic setting that generalises standard
reinforcement learning tasks and captures this intuition.

Feature selection methods such as wrappers may produce high-quality feature
subsets, however they often require building multiple models and are
time-consuming. Motivated by a fresh perspective on the relationship between an
information-based forward feature selection criterion and decision trees, in
this paper we propose a tree regularization framework, in which only a single
model needs to be built. The framework enables many tree models to perform
feature selection. The key idea of the regularization framework is to penalize
using a new feature for splitting when its gain (e.g.

Latent Dirichlet allocation (LDA) is an important class of hierarchical
Bayesian models for probabilistic topic modeling, which attracts worldwide
interests and touches on many important applications in text mining, computer
vision and computational biology. This paper introduces a topic modeling
toolbox (TMBP) based on the belief propagation (BP) algorithms. This toolbox is
implemented by MEX C++/MATLAB platform for either Windows or Linux.

We provide the first algorithm for online bandit linear optimization whose
regret after T rounds is of order sqrt{Td ln N} on any finite class X of N
actions in d dimensions, and of order d*sqrt{T} (up to log factors) when X is
infinite. These bounds are not improvable in general. The basic idea utilizes
tools from convex geometry to construct what is essentially an optimal
exploration basis. We also present an application to a model of linear bandits
with expert advice.

Unsupervised aggregation of independently built univariate predictors is
explored as an alternative regularization approach for noisy, sparse datasets.
Bipartite ranking algorithm Smooth Rank implementing this approach is
introduced. The advantages of this algorithm are demonstrated on two types of
problems. First, Smooth Rank is applied to two-class problems from bio-medical
field, where ranking is often preferable to classification. In comparison
against SVMs with radial and linear kernels, Smooth Rank had the best
performance on 8 out of 12 benchmark benchmarks.

We consider the problem of learning a linear factor model with an unknown
number of factors. We propose a regularized form of principal component
analysis (PCA) and demonstrate through experiments with synthetic and real data
the superiority of resulting estimates to those produced by pre-existing factor
analysis approaches. We also establish theoretical results that elucidate the
manner in which our algorithm corrects biases induced by conventional PCA.

The multi-armed bandit problem is a popular model for studying
exploration/exploitation trade-off in sequential decision problems. Many
algorithms are now available for this well-studied problem. One of the earliest
algorithms, given by W. R. Thompson, dates back to 1933. This algorithm,
referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic
idea is to choose an arm to play according to its probability of being the best
arm. Thompson Sampling algorithm has experimentally been shown to be close to
optimal.

We propose a new online learning model for learning with preference feedback.
The model is especially suited for applications like web search and recommender
systems, where preference data is readily available from implicit user feedback
(e.g. clicks). In particular, at each time step a potentially structured object
(e.g. a ranking) is presented to the user in response to a context (e.g.
query), providing him or her with some unobserved amount of utility. As
feedback the algorithm receives an improved object that would have provided
higher utility.

Latent Dirichlet Allocation models discrete data as a mixture of discrete
distributions, using Dirichlet beliefs over the mixture weights. We study a
variation of this concept, in which the documents' mixture weight beliefs are
replaced with squashed Gaussian distributions. This allows documents to be
associated with elements of a Hilbert space, admitting kernel topic models
(KTM), modelling temporal, spatial, hierarchical, social and other structure
between documents. The main challenge is efficient approximate inference on the
latent Gaussian.

We consider the problem of identifying patterns in a data set that exhibit
anomalous behavior, often referred to as anomaly detection. In most anomaly
detection algorithms, the dissimilarity between data samples is calculated by a
single criterion. When dissimilarities are calculated by multiple criteria, one
might perform anomaly detection using a linear combination of the multiple
dissimilarities.

We consider unsupervised crowdsourcing performance based on the model wherein
the responses of end-users are essentially rated according to how their
responses correlate with the majority of other responses to the same
subtasks/questions. In one setting, we consider an independent sequence of
identically distributed crowdsourcing assignments (meta-tasks), while in the
other we consider a single assignment with a large number of component
subtasks. Both problems yield intuitive results in which the overall
reliability of the crowd is a factor.

The most basic assumption used in statistical learning theory is that
training data and test data are drawn from the same underlying distribution.
Unfortunately, in many applications, the "in-domain" test data is drawn from a
distribution that is related, but not identical, to the "out-of-domain"
distribution of the training data. We consider the common case in which labeled
out-of-domain data is plentiful, but labeled in-domain data is scarce.

In this paper we explore the problem of noise tolerant learning of
classifiers. We formulate the problem as follows. We assume that there is an
${\bf unobservable}$ training set which is noise-free. The actual training set
given to the learning algorithm is obtained from this ideal data set by
corrupting the class label of each example where the probability that the class
label on an example is corrupted is a function of the feature vector of the
example. This would account for almost all kinds of noisy data one may
encounter in practice.

This paper examines the problem of ranking a collection of objects using
pairwise comparisons (rankings of two objects). In general, the ranking of $n$
objects can be identified by standard sorting methods using $n log_2 n$
pairwise comparisons. We are interested in natural situations in which
relationships among the objects may allow for ranking using far fewer pairwise
comparisons. Specifically, we assume that the objects can be embedded into a
$d$-dimensional Euclidean space and that the rankings reflect their relative
distances from a common reference point in $R^d$.

In this paper, we consider the problem of preserving privacy in the online
learning setting. We study the problem in the online convex programming (OCP)
framework---a popular online learning setting with several interesting
theoretical and practical implications---while using differential privacy as
the formal privacy measure.

We consider the problem of optimizing the sum of a smooth convex function and
a non-smooth convex function using proximal-gradient methods, where an error is
present in the calculation of the gradient of the smooth term or in the
proximity operator with respect to the non-smooth term.

In this paper, we present a new multiple instance learning (MIL) method,
called MIS-Boost, which learns discriminative instance prototypes by explicit
instance selection in a boosting framework. Unlike previous instance selection
based MIL methods, we do not restrict the prototypes to a discrete set of
training instances but allow them to take arbitrary values in the instance
feature space. We also do not restrict the total number of prototypes and the
number of selected-instances per bag; these quantities are completely
data-driven.

In this paper, we consider Markov Decision Processes (MDPs) with error
states. Error states are those states entering which is undesirable or
dangerous. We define the risk with respect to a policy as the probability of
entering such a state when the policy is pursued. We consider the problem of
finding good policies whose risk is smaller than some user-specified threshold,
and formalize it as a constrained MDP with two criteria. The first criterion
corresponds to the value function originally given.

In this paper we investigate clustering in the weighted setting, in which
every data point is assigned a real valued weight. We conduct a theoretical
analysis on the influence of weighted data on standard clustering algorithms in
each of the partitional and hierarchical settings, characterising the precise
conditions under which such algorithms react to weights, and classifying
clustering methods into three broad categories: weight-responsive,
weight-considering, and weight-robust.

Volterra and polynomial regression models play a major role in nonlinear
system identification and inference tasks. Exciting applications ranging from
neuroscience to genome-wide association analysis build on these models with the
additional requirement of parsimony. This requirement has high interpretative
value, but unfortunately cannot be met by least-squares based or kernel
regression methods. To this end, compressed sampling (CS) approaches, already
successful in linear regression settings, can offer a viable alternative.

Multiclass prediction is the problem of classifying an object into a relevant
target class. We consider the problem of learning a multiclass predictor that
uses only few features, and in particular, the number of used features should
increase sub-linearly with the number of possible classes. This implies that
features should be shared by several classes. We describe and analyze the
ShareBoost algorithm for learning a multiclass predictor that uses few shared
features.

We present a data dependent generalization bound for a large class of
regularized algorithms which implement structured sparsity constraints. The
bound can be applied to standard squared-norm regularization, the lasso, the
group lasso, some versions of the group lasso with overlapping groups, multiple
kernel learning and other regularization schemes. In all these cases
competitive results are obtained.

Stability is a general notion that quantifies the sensitivity of a learning
algorithm's output to small change in the training dataset (e.g. deletion or
replacement of a single training sample). Such conditions have recently been
shown to be more powerful to characterize learnability in the general learning
setting under i.i.d. samples where uniform convergence is not necessary for
learnability, but where stability is both sufficient and necessary for
learnability. We here show that similar stability conditions are also
sufficient for online learnability, i.e.

This work deals with the problem of classifying uncertain data. With this aim
the Uncertain Nearest Neighbor (UNN) rule is here introduced, which represents
the generalization of the deterministic nearest neighbor rule to the case in
which uncertain objects are available. The UNN rule relies on the concept of
nearest neighbor class, rather than on that of nearest neighbor object. The
nearest neighbor class of a test object is the class that maximizes the
probability of providing its nearest neighbor.

This paper gives specific divergence examples of value-iteration for several
major Reinforcement Learning and Adaptive Dynamic Programming algorithms, when
using a function approximator for the value function. These divergence examples
differ from previous divergence examples in the literature, in that they are
applicable for a greedy policy, i.e. in a "value iteration" scenario. Perhaps
surprisingly, with a greedy policy, it is also possible to get divergence for
the algorithms TD(1) and Sarsa(1).

In this paper we propose a new algorithm for learning polyhedral classifiers
which we call as Polyceptron. It is a Perception like algorithm which updates
the parameters only when the current classifier misclassifies any training
data. We give both batch and online version of Polyceptron algorithm. Finally
we give experimental results to show the effectiveness of our approach.

We consider the problem of high-dimensional Gaussian graphical model
selection. We identify a set of graphs for which an efficient estimation
algorithm exists, and this algorithm is based on thresholding of empirical
conditional covariances. Under a set of transparent conditions, we establish
structural consistency (or sparsistency) for the proposed algorithm, when the
number of samples n=omega(J_{min}^{-2} log p), where p is the number of
variables and J_{min} is the minimum (absolute) edge potential of the graphical
model.

Sparse linear regression -- finding an unknown vector from linear
measurements -- is now known to be possible with fewer samples than variables,
via methods like the LASSO. We consider the multiple sparse linear regression
problem, where several related vectors -- with partially shared support sets --
have to be recovered. A natural question in this setting is whether one can use
the sharing to further decrease the overall number of samples required.

Motivated by the amount of code that goes unidentified on the web, we
introduce a practical method for algorithmically identifying the programming
language of source code. Our work is based on supervised learning and
intelligent statistical features. We also explored, but abandoned, a
grammatical approach. In testing, our implementation greatly outperforms that
of an existing tool that relies on a Bayesian classifier.

Signal Sequence Labeling consists in predicting a sequence of labels given an
observed sequence of samples. A naive way is to filter the signal in order to
reduce the noise and to apply a classification algorithm on the filtered
samples. We propose in this paper to jointly learn the filter with the
classifier leading to a large margin filtering for classification. This method
allows to learn the optimal cutoff frequency and phase of the filter that may
be different from zero. Two methods are proposed and tested on a toy dataset
and on a real life BCI dataset from BCI Competition III.

Estimator algorithms in learning automata are useful tools for adaptive,
real-time optimization in computer science and engineering applications. This
paper investigates theoretical convergence properties for a special case of
estimator algorithms---the pursuit learning algorithm. We identify a gap in
existing proofs of probabilistic convergence for pursuit learning and present a
more refined analysis to fill this gap.

Observational data usually comes with a multimodal nature, which means that
it can be naturally represented by a multi-layer graph whose layers share the
same set of vertices (users) with different edges (pairwise relationships). In
this paper, we address the problem of combining different layers of the
multi-layer graph for improved clustering of the vertices compared to using
layers independently.

We address the problem of learning in an online setting where the learner
repeatedly observes features, selects among a set of actions, and receives
reward for the action taken. We provide the first efficient algorithm with an
optimal regret. Our algorithm uses a cost sensitive classification learner as
an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number
of classification rules among which the oracle might choose. This is
exponentially faster than all previous algorithms that achieve optimal regret
in this setting.

We address the problem of minimizing a convex function over the space of
large matrices with low rank. While this optimization problem is hard in
general, we propose an efficient greedy algorithm and derive its formal
approximation guarantees. Each iteration of the algorithm involves
(approximately) finding the left and right singular vectors corresponding to
the largest singular value of a certain matrix, which can be calculated in
linear time.

We show that all non-negative submodular functions have high {\em
noise-stability}. As a consequence, we obtain a polynomial-time learning
algorithm for this class with respect to any product distribution on
$\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$). Our algorithm
also succeeds in the agnostic setting. Previous work on learning submodular
functions required either query access or strong assumptions about the types of
submodular functions to be learned (and did not hold in the agnostic setting).

We begin this report by describing the Probably Approximately Correct (PAC)
model for learning a concept class, consisting of subsets of a domain, and a
function class, consisting of functions from the domain to the unit interval.
Two combinatorial parameters, the Vapnik-Chervonenkis (VC) dimension and its
generalization, the Fat Shattering dimension of scale e, are explained and a
few examples of their calculations are given with proofs.

In this paper, we propose to (seamlessly) integrate b-bit minwise hashing
with linear SVM to substantially improve the training (and testing) efficiency
using much smaller memory, with essentially no loss of accuracy. Theoretically,
we prove that the resemblance matrix, the minwise hashing matrix, and the b-bit
minwise hashing matrix are all positive definite matrices (kernels).
Interestingly, our proof for the positive definiteness of the b-bit minwise
hashing kernel naturally suggests a simple strategy to integrate b-bit hashing
with linear SVM.

Feature selection is an important pre-processing step for many pattern
classification tasks. Traditionally, feature selection methods are designed to
obtain a feature subset that can lead to high classification accuracy. However,
classification accuracy has recently been shown to be an inappropriate
performance metric of classification systems in many cases. Instead, the Area
Under the receiver operating characteristic Curve (AUC) and its multi-class
extension, MAUC, have been proved to be better alternatives.

We present two alternative ways to apply PAC-Bayesian analysis to sequences
of dependent random variables. The first is based on a new lemma that enables
to bound expectations of convex functions of certain dependent random variables
by expectations of the same functions of independent Bernoulli random
variables. This lemma provides an alternative tool to Hoeffding-Azuma
inequality to bound concentration of martingale values.

In many physical, statistical, biological and other investigations it is
desirable to approximate a system of points by objects of lower dimension
and/or complexity. For this purpose, Karl Pearson invented principal component
analysis in 1901 and found 'lines and planes of closest fit to system of
points'. The famous k-means algorithm solves the approximation problem too, but
by finite sets instead of lines and planes. This chapter gives a brief
practical introduction into the methods of construction of general principal
objects, i.e.

We investigate unsupervised pre-training of deep architectures as feature
generators for "shallow" classifiers. Stacked Denoising Autoencoders (SdA),
when used as feature pre-processing tools for SVM classification, can lead to
significant improvements in accuracy - however, at the price of a substantial
increase in computational cost. In this paper we create a simple algorithm
which mimics the layer by layer training of SdAs. However, in contrast to SdAs,
our algorithm requires no training through gradient descent as the parameters
can be computed in closed-form.

This paper considers the problem of clustering a partially observed
unweighted graph -- i.e. one where for some node pairs we know there is an edge
between them, for some others we know there is no edge, and for the remaining
we do not know whether or not there is an edge. We want to organize the nodes
into disjoint clusters so that there is relatively dense (observed)
connectivity within clusters, and sparse across clusters.

In many practical applications of clustering, the objects to be clustered
evolve over time, and a clustering result is desired at each time step. In such
applications, evolutionary clustering typically outperforms ordinary static
clustering by producing clustering results that reflect long-term trends while
being robust to short-term variations. Several evolutionary clustering
algorithms have recently been proposed, often by adding a temporal smoothness
penalty to the cost function of a static clustering method.

We introduce new online and batch algorithms that are robust to data with
missing features, a situation that arises in many practical applications. In
the online setup, we allow for the comparison hypothesis to change as a
function of the subset of features that is observed on any given round,
extending the standard setting where the comparison hypothesis is fixed
throughout. In the batch setup, we present a convex relation of a non-convex
problem to jointly estimate an imputation function, used to fill in the values
of missing features, along with the classification hypothesis.

We consider a collection of prediction experiments, which are clustered in
the sense that groups of experiments ex- hibit similar relationship between the
predictor and response variables. The experiment clusters as well as the
regres- sion relationships are unknown. The regression relation- ships define
the experiment clusters, and in general, the predictor and response variables
may not exhibit any clus- tering. We call this prediction problem clustered
regres- sion with unknown clusters (CRUC) and in this paper we focus on linear
regression.

In this work we study parallelization of online learning, a core primitive in
machine learning. In a parallel environment all known approaches for parallel
online learning lead to delayed updates, where the model is updated using
out-of-date information.

The collection of massive volumes of data requires machine learning
algorithms that can be applied to distributed data. We describe COMET (Cloud of
Massive Ensemble Trees), a recipe for distributed supervised learning
consisting of three components: (1) Map-Reduce is used to parallelize the
learning and evaluation tasks and collect the results, (2) an IVoting Random
Forest is used for the learning task on each local data partition, and (3) the
results of all local ensembles are combined into one massive ensemble and lazy
evaluation is used to dynamically subsample it.

In multi-label learning, each sample is associated with several labels.
Existing works indicate that exploring correlations between labels improve the
prediction performance. However, embedding the label correlations into the
training process significantly increases the problem size. Moreover, the
mapping of the label structure in the feature space is not clear. In this
paper, we propose a novel multi-label learning method "Structured Decomposition
+ Group Sparsity (SDGS)".

This encyclopedic article gives a mini-introduction into the theory of
universal learning, founded by Ray Solomonoff in the 1960s and significantly
developed and extended in the last decade. It explains the spirit of universal
learning, but necessarily glosses over technical subtleties.

Recent research in multi-robot exploration and mapping has focused on
sampling environmental fields, which are typically modeled using the Gaussian
process (GP). Existing information-theoretic exploration strategies for
learning GP-based environmental field maps adopt the non-Markovian problem
structure and consequently scale poorly with the length of history of
observations. Hence, it becomes computationally impractical to use these
strategies for in situ, real-time active sampling.

In this paper, we propose a two-timescale delay-optimal dynamic clustering
and power allocation design for downlink network MIMO systems. The dynamic
clustering control is adaptive to the global queue state information (GQSI)
only and computed at the base station controller (BSC) over a longer time
scale. On the other hand, the power allocations of all the BSs in one cluster
are adaptive to both intra-cluster channel state information (CCSI) and
intra-cluster queue state information (CQSI), and computed at the cluster
manager (CM) over a shorter time scale.

We obtain a tight distribution-specific characterization of the sample
complexity of large-margin classification with L_2 regularization: We introduce
the \gamma-adapted-dimension, which is a simple function of the spectrum of a
distribution's covariance matrix, and show distribution-specific upper and
lower bounds on the sample complexity, both governed by the
\gamma-adapted-dimension of the source distribution. We conclude that this new
quantity tightly characterizes the true sample complexity of large-margin
classification.

We consider the celebrated Blackwell Approachability Theorem for two-player
games with vector payoffs. We show that Blackwell's result is equivalent, via
efficient reductions, to the existence of "no-regret" algorithms for Online
Linear Optimization. Indeed, we show that any algorithm for one such problem
can be efficiently converted into an algorithm for the other. We provide a
useful application of this reduction: the first efficient algorithm for
calibrated forecasting.

Nesterov's accelerated gradient methods (AGM) have been successfully applied
in many machine learning areas. However, their empirical performance on
training max-margin models has been inferior to existing specialized solvers.
In this paper, we first extend AGM to strongly convex and composite objective
functions with Bregman style prox-functions. Our unifying framework covers both
the $\infty$-memory and 1-memory styles of AGM, tunes the Lipschiz constant
adaptively, and bounds the duality gap.

Gaussian graphical models are of great interest in statistical learning.
Because the conditional independencies between different nodes correspond to
zero entries in the inverse covariance matrix of the Gaussian distribution, one
can learn the structure of the graph by estimating a sparse inverse covariance
matrix from sample data, by solving a convex maximum likelihood problem with an
$\ell_1$-regularization term.

A general framework based on Gaussian models and a MAP-EM algorithm is
introduced in this paper for solving matrix/table completion problems. The
numerical experiments with the standard and challenging movie ratings data show
that the proposed approach, based on probably one of the simplest probabilistic
models, leads to the results in the same ballpark as the state-of-the-art, at a
lower computational cost.

Hardness results for maximum agreement problems have close connections to
hardness results for proper learning in computational learning theory. In this
paper we prove two hardness results for the problem of finding a low degree
polynomial threshold function (PTF) which has the maximum possible agreement
with a given set of labeled examples in $\R^n \times \{-1,1\}.$ We prove that
for any constants $d\geq 1, \eps > 0$,

{itemize}

In this paper, we consider a queue-aware distributive resource control
algorithm for two-hop MIMO cooperative systems. We shall illustrate that relay
buffering is an effective way to reduce the intrinsic half-duplex penalty in
cooperative systems. The complex interactions of the queues at the source node
and the relays are modeled as an average-cost infinite horizon Markov Decision
Process (MDP). The traditional approach solving this MDP problem involves
centralized control with huge complexity.

We consider the problem of energy-efficient point-to-point transmission of
delay-sensitive data (e.g. multimedia data) over a fading channel.

Speech recognition and speaker identification are important for
authentication and verification in security purpose, but they are difficult to
achieve. Speaker identification methods can be divided into text-independent
and text-dependent. This paper presents a technique of text-dependent speaker
identification using MFCC-domain support vector machine (SVM).

Sparse learning has recently received increasing attention in many areas
including machine learning, statistics, and applied mathematics. The mixed-norm
regularization based on the L1/Lq norm with q > 1 is attractive in many
applications of regression and classification in that it facilitates group
sparsity in the model. The resulting optimization problem is, however,
challenging to solve due to the structure of the L1/Lq -regularization.
Existing work deals with special cases including q = 2,infinity, and they
cannot be easily extended to the general case.

Sparse methods for supervised learning aim at finding good linear predictors
from as few variables as possible, i.e., with small cardinality of their
supports. This combinatorial selection problem is often turned into a convex
optimization problem by replacing the cardinality function by its convex
envelope (tightest convex lower bound), in this case the L1-norm.

We propose a novel reformulation of the stochastic optimal control problem as
an approximate inference problem, demonstrating, that such a interpretation
leads to new practical methods for the original problem. In particular we
characterise a novel class of iterative solutions to the stochastic optimal
control problem based on a natural relaxation of the exact dual formulation.
These theoretical insights are applied to the Reinforcement Learning problem
where they lead to new model free, off policy methods for discrete and
continuous problems.

We study two families of online convex optimization algorithms: mirror
descent and follow-the-regularized-leader. We prove that many mirror descent
algorithms (such as online gradient descent) are actually instances of a more
general follow-the-leader algorithm which uses proximal regularization
(additional strong convexity centered at the current feasible point). Further,
under certain step-size assumptions, other mirror-descent algorithms are
equivalent to follow-the-leader algorithms with origin-centered regularization
(such as dual averaging).

The group Lasso is an extension of the Lasso for feature selection on
(predefined) non-overlapping groups of features. The non-overlapping group
structure limits its applicability in practice. There have been several recent
attempts to study a more general formulation, where groups of features are
given, potentially with overlaps between the groups. The resulting optimization
is, however, much more challenging to solve due to the group overlaps. In this
paper, we consider the efficient optimization of the overlapping group Lasso
penalized problem.

We propose a novel feature selection strategy to discover
language-independent acoustic features that tend to be responsible for emotions
regardless of languages, linguistics and other factors. Experimental results
suggest that the language-independent feature subset discovered yields the
performance comparable to the full feature set on various emotional speech
corpora.

In this paper, we study two general classes of optimization algorithms for
kernel methods with convex loss function and quadratic norm regularization, and
analyze their convergence. The first approach, based on fixed-point iterations,
is simple to implement and analyze, and can be easily parallelized. The second,
based on coordinate descent, exploits the structure of additively separable
loss functions to compute solutions of line searches in closed form.

In prediction with expert advice the goal is to design online prediction
algorithms that achieve small regret (additional loss on the whole data)
compared to a reference scheme. In the simplest such scheme one compares to the
loss of the best expert in hindsight. A more ambitious goal is to split the
data into segments and compare to the best expert on each segment. This is
appropriate if the nature of the data changes between segments. The standard
fixed-share algorithm is fast and achieves small regret compared to this
scheme.

Recently, applying the novel data mining techniques for evaluating enterprise
financial distress has received much research alternation. Support Vector
Machine (SVM) and back propagation neural (BPN) network has been applied
successfully in many areas with excellent generalization results, such as rule
extraction, classification and evaluation. In this paper, a model based on SVM
with Gaussian RBF kernel is proposed here for enterprise financial distress
evaluation.

It is difficult to find the optimal sparse solution of a manifold learning
based dimensionality reduction algorithm. The lasso or the elastic net
penalized manifold learning based dimensionality reduction is not directly a
lasso penalized least square problem and thus the least angle regression (LARS)
(Efron et al. \cite{LARS}), one of the most popular algorithms in sparse
learning, cannot be applied. Therefore, most current approaches take indirect
ways or have strict settings, which can be inconvenient for applications.

This paper introduces a principled approach for the design of a scalable
general reinforcement learning agent. This approach is based on a direct
approximation of AIXI, a Bayesian optimality notion for general reinforcement
learning agents. Previously, it has been unclear whether the theory of AIXI
could motivate the design of practical algorithms. We answer this hitherto open
question in the affirmative, by providing the first computationally feasible
approximation to the AIXI agent.

We show that the learning sample complexity of a sigmoidal neural network
constructed by Sontag (1992) required to achieve a given misclassification
error under a fixed purely atomic distribution can grow arbitrarily fast: for
any prescribed rate of growth there is an input distribution having this rate
as the sample complexity, and the bound is asymptotically tight. The rate can
be superexponential, a non-recursive function, etc. We further observe that
Sontag's ANN is not Glivenko-Cantelli under any input distribution having a
non-atomic part.

We address in this paper the problem of multi-channel signal sequence
labeling. In particular, we consider the problem where the signals are
contaminated by noise or may present some dephasing with respect to their
labels. For that, we propose to jointly learn a SVM sample classifier with a
temporal filtering of the channels. This will lead to a large margin filtering
that is adapted to the specificity of each channel (noise and time-lag). We
derive algorithms to solve the optimization problem and we discuss different
filter regularizations for automated scaling or selection of channels.

Music Sight Reading is a complex process that when it is occurred in the
brain, some learning attributes would be emerged. Besides giving a model based
on actor-critic method in the Reinforcement Learning, the agent is considered
to have a neural network structure. We studied on where the sight reading
process is happened and also a serious problem which is how the synaptic
weights would be adjusted through the learning process. The model we offer here
is a computational model on which an updated weights equation to fixing the
weights is accompanied too.

In response to a 1997 problem of M. Vidyasagar, we state a necessary and
sufficient condition for distribution-free PAC learnability of a concept class
$\mathscr C$ under the family of all non-atomic (diffuse) measures on the
domain $\Omega$. Clearly, finiteness of the classical Vapnik-Chervonenkis
dimension of $\mathscr C$ is a sufficient, but no longer necessary, condition.
Besides, learnability of $\mathscr C$ under non-atomic measures does not imply
the uniform Glivenko-Cantelli property with regard to non-atomic measures.

Abc-boost is a new line of boosting algorithms for multi-class
classification, by utilizing the commonly used sum-to-zero constraint. To
implement abc-boost, a base class must be identified at each boosting step.
Prior studies used a very expensive procedure based on exhaustive search for
determining the base class at each boosting step. Good testing performances of
abc-boost (implemented as abc-mart and abc-logitboost) on a variety of datasets
were reported.

Exchangeable random variables form an important and well-studied
generalization of i.i.d. variables, however simple examples show that no
nontrivial concept or function classes are PAC learnable under general
exchangeable data inputs $X_1,X_2,\ldots$. Inspired by the work of Berti and
Rigo on a Glivenko--Cantelli theorem for exchangeable inputs, we propose a new
paradigm, adequate for learning from exchangeable data: predictive PAC
learnability.

We study learnability in the online learning model. We define several
complexity measures which capture the difficulty of learning in a sequential
manner. Among these measures are analogues of Rademacher complexity, covering
numbers and fat shattering dimension from statistical learning theory.
Relationship among these complexity measures, their connection to online
learning, and tools for bounding them are provided. In the setting of
supervised learning, finiteness of the introduced scale-sensitive parameters is
shown to be equivalent to learnability.

A sequence $x_1,...,x_n,...$ of discrete-valued observations is generated
according to some unknown probabilistic law (measure) $\mu$. After observing
each outcome, it is required to give the conditional probabilities of the next
observation. The realizable case is when the measure $\mu$ belongs to an
arbitrary but known class $C$ of process measures. The non-realizable case is
when $\mu$ is completely arbitrary, but the prediction performance is measured
with respect to a given set $C$ of process measures.

This paper provides a theoretical explanation on the clustering aspect of
nonnegative matrix factorization (NMF). We prove that even without imposing
orthogonality or sparsity constraint on the basis and/or coefficient matrix,
NMF still can give clustering results, thus providing a theoretical support for
the works of Xu et al. [1] and Kim et al. [2], where the authors showed the
superiority of the standard NMF as a clustering method.

Rapid identification of object from radar cross section (RCS) signals is
important for many space and military applications. This identification is a
problem in pattern recognition which either neural networks or support vector
machines should prove to be high-speed. Bayesian networks would also provide
value but require significant preprocessing of the signals. In this paper, we
describe the use of a support vector machine for object identification from
synthesized RCS data.

We study prediction with expert advice in the setting where the losses are
accumulated with some discounting---the impact of old losses may gradually
vanish. We generalize the Aggregating Algorithm and the Aggregating Algorithm
for Regression to this case, propose a suitable new variant of exponential
weights algorithm, and prove respective loss bounds.

Although the real reproducing kernels are used in an increasing number of
machine learning problems, complex kernels have not, yet, been used, in spite
of their potential interest in applications such as communications. In this
work, we focus our attention on the complex gaussian kernel and its possible
application in the complex Kernel LMS algorithm. In order to derive the
gradients needed to develop the complex kernel LMS (CKLMS), we employ the
powerful tool of Wirtinger's Calculus, which has recently attracted much
attention in the signal processing community.

The problem of clustering is considered, for the case when each data point is
a sample generated by a stationary ergodic process. We propose a very natural
asymptotic notion of consistency, and show that simple consistent algorithms
exist, under most general non-parametric assumptions. The notion of consistency
is as follows: two samples should be put into the same cluster if and only if
they were generated by the same distribution. With this notion of consistency,
clustering generalizes such classical statistical problems as homogeneity
testing and process classification.

This paper presents a method for automated healing as part of off-line
automated troubleshooting. The method combines statistical learning with
constraint optimization. The automated healing aims at locally optimizing radio
resource management (RRM) or system parameters of cells with poor performance
in an iterative manner. The statistical learning processes the data using
Logistic Regression (LR) to extract closed form (functional) relations between
Key Performance Indicators (KPIs) and Radio Resource Management (RRM)
parameters.

We introduce two kernels that extend the mean map, which embeds probability
measures in Hilbert spaces. The generative mean map kernel (GMMK) is a smooth
similarity measure between probabilistic models. The latent mean map kernel
(LMMK) generalizes the non-iid formulation of Hilbert space embeddings of
empirical distributions in order to incorporate latent variable models. When
comparing certain classes of distributions, the GMMK exhibits beneficial
regularization and generalization properties not shown for previous generative
kernels.

We consider model-based reinforcement learning in finite Markov Decision
Processes (MDPs), focussing on so-called optimistic strategies. Optimism is
usually implemented by carrying out extended value iterations, under a
constraint of consistency with the estimated model transition probabilities. In
this paper, we strongly argue in favor of using the Kullback-Leibler (KL)
divergence for this purpose. By study- ing the linear maximization problem
under KL constraints, we provide an efficient algorithm for solving
KL-optimistic extended value iteration.

We describe and analyze efficient algorithms for learning a linear predictor
from examples when the learner can only view a few attributes of each training
example. This is the case, for instance, in medical research, where each
patient participating in the experiment is only willing to go through a small
number of tests. Our analysis bounds the number of additional examples
sufficient to compensate for the lack of full information on each training
example.

We present a solution to the problem of understanding a system that produces
a sequence of temporally ordered observations. Our solution is based on
generating and interpreting a set of temporal decision rules. A temporal
decision rule is a decision rule that can be used to predict or retrodict the
value of a decision attribute, using condition attributes that are observed at
times other than the decision attribute's time of observation.

In this paper, we consider the problem of planning and learning in the
infinite-horizon discounted-reward Markov decision problems. We propose a novel
iterative direct policy-search approach, called dynamic policy programming
(DPP). DPP is, to the best of our knowledge, the first convergent direct
policy-search method that uses a Bellman-like iteration technique and at the
same time is compatible with function approximation. For the tabular case, we
prove that DPP converges asymptotically to the optimal policy.

Clustering is an unsupervised learning method that constitutes a cornerstone
of an intelligent data analysis process. It is used for the exploration of
inter-relationships among a collection of patterns, by organizing them into
homogeneous clusters. Clustering has been dynamically applied to a variety of
tasks in the field of Information Retrieval (IR). Clustering has become one of
the most active area of research and the development.

This paper discusses the knowledge integration of clinical information
extracted from distributed medical ontology in order to ameliorate a machine
learning-based multi-label coding assignment system. The proposed approach is
implemented using a decision tree based cascade hierarchical technique on the
university hospital data for patients with Coronary Heart Disease (CHD). The
preliminary results obtained show a satisfactory finding.

The main function of IDS (Intrusion Detection System) is to protect the
system, analyze and predict the behaviors of users. Then these behaviors will
be considered an attack or a normal behavior. Though IDS has been developed for
many years, the large number of return alert messages makes managers maintain
system inefficiently. In this paper, we use RST (Rough Set Theory) and SVM
(Support Vector Machine) to detect intrusions. First, RST is used to preprocess
the data and reduce the dimensions. Next, the features were selected by RST
will be sent to SVM model to learn and test respectively.

Thanks to the Eslo1 ("Enqu\^ete sociolinguistique d'Orl\'eans", i.e.
"Sociolinguistic Inquiery of Orl\'eans") campain, a large oral corpus has been
gathered and transcribed in a textual format. The purpose of the work presented
here is to associate a morpho-syntactic label to each unit of this corpus. To
this aim, we have first studied the specificities of the necessary labels, and
their various possible levels of description. This study has led to a new
original hierarchical structuration of labels.

With the arrival of digital era and Internet, the lack of information control
provides an incentive for people to freely use any content available to them.
Plagiarism occurs when users fail to credit the original owner for the content
referred to, and such behavior leads to violation of intellectual property. Two
main approaches to plagiarism detection are fingerprinting and term occurrence;
however, one common weakness shared by both approaches, especially
fingerprinting, is the incapability to detect modified text plagiarism.

Given a set of data, biclustering aims at finding simultaneous partitions in
biclusters of its samples and of the features which are used for representing
the samples. Consistent biclusterings allow to obtain correct classifications
of the samples from the known classification of the features, and vice versa,
and they are very useful for performing supervised classifications.

Classifiers are often used to detect miscreant activities. We study how an
adversary can efficiently query a classifier to elicit information that allows
the adversary to evade detection at near-minimal cost. We generalize results of
Lowd and Meek (2005) to convex-inducing classifiers. We present algorithms that
construct undetected instances of near-minimal cost using only polynomially
many queries in the dimension of the space and without reverse engineering the
decision boundary.

We apply the method of defensive forecasting, based on the use of
game-theoretic supermartingales, to prediction with expert advice. In the
traditional setting of a countable number of experts and a finite number of
outcomes, the Defensive Forecasting Algorithm is very close to the well-known
Aggregating Algorithm. Not only the performance guarantees but also the
predictions are the same for these two methods of fundamentally different
nature. We discuss also a new setting where the experts can give advice
conditional on the learner's future decision.

Maximum likelihood estimators are often of limited practical use due to the
intensive computation they require. We propose a family of alternative
estimators that maximize a stochastic variation of the composite likelihood
function. Each of the estimators resolve the computation-accuracy tradeoff
differently, and taken together they span a continuous spectrum of
computation-accuracy tradeoff resolutions. We prove the consistency of the
estimators, provide formulas for their asymptotic variance, statistical
robustness, and computational complexity.

In this paper, we propose a unified algorithmic framework for solving many
known variants of \mds. Our algorithm is a simple iterative scheme with
guaranteed convergence, and is \emph{modular}; by changing the internals of a
single subroutine in the algorithm, we can switch cost functions and target
spaces easily. In addition to the formal guarantees of convergence, our
algorithms are accurate; in most cases, they converge to better quality
solutions than existing methods, in comparable time.

Semisupervised learning has emerged as a popular framework for improving
modeling accuracy while controlling labeling cost. Based on an extension of
stochastic composite likelihood we quantify the asymptotic accuracy of
generative semi-supervised learning. In doing so, we complement
distribution-free analysis by providing an alternative framework to measure the
value associated with different labeling policies and resolve the fundamental
question of how much data to label and in what manner.

We provide a sound and consistent foundation for the use of \emph{nonrandom}
exploration data in "contextual bandit" or "partially labeled" settings where
only the value of a chosen action is learned.

In a variety of disciplines such as social sciences, psychology, medicine and
economics, the recorded data are considered to be noisy measurements of latent
variables connected by some causal structure. This corresponds to a family of
graphical models known as the structural equation model with latent variables.
While linear non-Gaussian variants have been well-studied, inference in
nonparametric structural equation models is still underdeveloped.

We consider bandit problems involving a large (possibly infinite) collection
of arms, in which the expected reward of each arm is a linear function of an
$r$-dimensional random vector $\mathbf{Z} \in \mathbb{R}^r$, where $r \geq 2$.
The objective is to minimize the cumulative regret and Bayes risk.

India is a multi-lingual country where Roman script is often used alongside
different Indic scripts in a text document. To develop a script specific
handwritten Optical Character Recognition (OCR) system, it is therefore
necessary to identify the scripts of handwritten text correctly.

Learning problems form an important category of computational tasks that
generalizes many of the computations researchers apply to large real-life data
sets. We ask: what concept classes can be learned privately, namely, by an
algorithm whose output does not depend too heavily on any one input or specific
training example? More precisely, we investigate learning algorithms that
satisfy differential privacy, a notion that provides strong confidentiality
guarantees in contexts where aggregate information is released about a database
containing sensitive information about individuals.

The ability to monitor the progress of students academic performance is a
critical issue to the academic community of higher learning. A system for
analyzing students results based on cluster analysis and uses standard
statistical algorithms to arrange their scores data according to the level of
their performance is described. In this paper, we also implemented k mean
clustering algorithm for analyzing students result data.

A key problem in sensor networks is to decide which sensors to query when, in
order to obtain the most useful information (e.g., for performing accurate
prediction), subject to constraints (e.g., on power and bandwidth). In many
applications the utility function is not known a priori, must be learned from
data, and can even change over time. Furthermore for large sensor networks
solving a centralized optimization problem to select sensors is not feasible,
and thus we seek a fully distributed solution.

The paper deals with on-line regression settings with signals belonging to a
Banach lattice. Our algorithms work in a semi-online setting where all the
inputs are known in advance and outcomes are unknown and given step by step. We
apply the Aggregating Algorithm to construct a prediction method whose
cumulative loss over all the input vectors is comparable with the cumulative
loss of any linear functional on the Banach lattice. As a by-product we get an
algorithm that takes signals from an arbitrary domain.

Associative Classifier is a novel technique which is the integration of
Association Rule Mining and Classification. The difficult task in building
Associative Classifier model is the selection of relevant rules from a large
number of class association rules (CARs). A very popular method of ordering
rules for selection is based on confidence, support and antecedent size (CSA).
Other methods are based on hybrid orderings in which CSA method is combined
with other measures.

We study the tracking problem, namely, estimating the hidden state of an
object over time, from unreliable and noisy measurements. The standard
framework for the tracking problem is the generative framework, which is the
basis of solutions such as the Bayesian algorithm and its approximation, the
particle filters. However, the problem with these solutions is that they are
very sensitive to model mismatches. In this paper, motivated by online
learning, we introduce a new framework -- an {\em explanatory} framework -- for
tracking.

This empirical study is mainly devoted to comparing four tree-based boosting
algorithms: mart, abc-mart, robust logitboost, and abc-logitboost, for
multi-class classification on a variety of publicly available datasets. Some of
those datasets have been thoroughly tested in prior studies using a broad range
of classification algorithms including SVM, neural nets, and deep learning.

In terms of the empirical classification errors, our experiment results
demonstrate:

Multi-class classification is one of the most important tasks in machine
learning. In this paper we consider two online multi-class classification
problems: classification by a linear model and by a kernelized model. The
quality of predictions is measured by the Brier loss function. We suggest two
computationally efficient algorithms to work with these problems and prove
theoretical guarantees on their losses. We kernelize one of the algorithms and
prove theoretical guarantees on its loss. We perform experiments and compare
our algorithms with logistic regression.

While statistics focusses on hypothesis testing and on estimating (properties
of) the true sampling distribution, in machine learning the performance of
learning algorithms on future data is the primary issue. In this paper we
bridge the gap with a general principle (PHI) that identifies hypotheses with
best predictive performance. This includes predictive point and interval
estimation, simple and composite hypothesis testing, (mixture) model selection,
and others as special cases. For concrete instantiations we will recover
well-known methods, variations thereof, and new ones.

We consider the problem of optimizing an unknown, noisy function that is
expensive to evaluate. We cast this problem as a multiarmed bandit problem
where the payoff function is sampled from a Gaussian Process. We resolve an
important open problem on deriving regret bounds for this setting. In
particular, we analyze an upper confidence algorithm and bound its cumulative
regret in terms of the maximal information gain due to sampling, thus
connecting Gaussian Process bandits and optimal experimental design.