pwc-archive/papers-with-abstracts huggingface dataset:
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
Authors: Yudong Chen, Martin J. Wainwright
Date: 2015-09-10 00:00:00
Tasks: Clustering, Graph Clustering, Matrix Completion, regression

Optimization problems with rank constraints arise in many applications,
including matrix regression, structured PCA, matrix completion and matrix
decomposition problems. An attractive heuristic for solving such problems is to
factorize the low-rank matrix, and to run projected gradient descent on the
nonconvex factorized optimization problem. The goal of this problem is to
provide a general theoretical framework for understanding when such methods
work well, and to characterize the nature of the resulting fixed point. We
provide a simple set of conditions under which projected gradient descent, when
given a suitable initialization, converges geometrically to a statistically
useful solution. Our results are applicable even when the initial solution is
outside any region of local convexity, and even when the problem is globally
concave. Working in a non-asymptotic framework, we show that our conditions are
satisfied for a wide range of concrete models, including matrix regression,
structured PCA, matrix completion with real and quantized observations, matrix
decomposition, and graph clustering problems. Simulation results show excellent
agreement with the theoretical predictions.
Compatible Value Gradients for Reinforcement Learning of Continuous Deep Policies
Authors: David Balduzzi, Muhammad Ghifary
Date: 2015-09-10 00:00:00
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

This paper proposes GProp, a deep reinforcement learning algorithm for
continuous policies with compatible function approximation. The algorithm is
based on two innovations. Firstly, we present a temporal-difference based
method for learning the gradient of the value-function. Secondly, we present
the deviator-actor-critic (DAC) model, which comprises three neural networks
that estimate the value function, its gradient, and determine the actor's
policy respectively. We evaluate GProp on two challenging tasks: a contextual
bandit problem constructed from nonparametric regression datasets that is
designed to probe the ability of reinforcement learning algorithms to
accurately estimate gradients; and the octopus arm, a challenging reinforcement
learning benchmark. GProp is competitive with fully supervised methods on the
bandit task and achieves the best performance to date on the octopus arm.
Knowlege Graph Embedding by Flexible Translation
Authors: Jun Feng, Mantong Zhou, Yu Hao, Minlie Huang, Xiaoyan Zhu
Date: 2015-05-20 00:00:00
Tasks: General Classification, Graph Embedding, Knowledge Graph Embedding, Link Prediction, Relation, Translation, Triple Classification

Knowledge graph embedding refers to projecting entities and relations in
knowledge graph into continuous vector spaces. State-of-the-art methods, such
as TransE, TransH, and TransR build embeddings by treating relation as
translation from head entity to tail entity. However, previous models can not
deal with reflexive/one-to-many/many-to-one/many-to-many relations properly, or
lack of scalability and efficiency. Thus, we propose a novel method, flexible
translation, named TransF, to address the above issues. TransF regards relation
as translation between head entity vector and tail entity vector with flexible
magnitude. To evaluate the proposed model, we conduct link prediction and
triple classification on benchmark datasets. Experimental results show that our
method remarkably improve the performance compared with several
state-of-the-art baselines.
Planar Ultrametric Rounding for Image Segmentation
Authors: Julian Yarkony, Charless C. Fowlkes
Date: 2015-07-09 00:00:00
Tasks: Clustering, Image Segmentation, Segmentation, Semantic Segmentation

We study the problem of hierarchical clustering on planar graphs. We
formulate this in terms of an LP relaxation of ultrametric rounding. To solve
this LP efficiently we introduce a dual cutting plane scheme that uses minimum
cost perfect matching as a subroutine in order to efficiently explore the space
of planar partitions. We apply our algorithm to the problem of hierarchical
image segmentation.
Clustering Tree-structured Data on Manifold
Authors: Na Lu, Hongyu Miao
Date: 2015-07-20 00:00:00
Tasks: Attribute, Clustering, Tree Decomposition

Tree-structured data usually contain both topological and geometrical
information, and are necessarily considered on manifold instead of Euclidean
space for appropriate data parameterization and analysis. In this study, we
propose a novel tree-structured data parameterization, called
Topology-Attribute matrix (T-A matrix), so the data clustering task can be
conducted on matrix manifold. We incorporate the structure constraints embedded
in data into the negative matrix factorization method to determine meta-trees
from the T-A matrix, and the signature vector of each single tree can then be
extracted by meta-tree decomposition. The meta-tree space turns out to be a
cone space, in which we explore the distance metric and implement the
clustering algorithm based on the concepts like Fr\'echet mean. Finally, the
T-A matrix based clustering (TAMBAC) framework is evaluated and compared using
both simulated data and real retinal images to illustrate its efficiency and
accuracy.
Optimizing Static and Adaptive Probing Schedules for Rapid Event Detection
Authors: Ahmad Mahmoody, Evgenios M. Kornaropoulos, Eli Upfal
Date: 2015-09-08 00:00:00
Tasks: Event Detection

We formulate and study a fundamental search and detection problem, Schedule
Optimization, motivated by a variety of real-world applications, ranging from
monitoring content changes on the web, social networks, and user activities to
detecting failure on large systems with many individual machines.
  We consider a large system consists of many nodes, where each node has its
own rate of generating new events, or items. A monitoring application can probe
a small number of nodes at each step, and our goal is to compute a probing
schedule that minimizes the expected number of undiscovered items at the
system, or equivalently, minimizes the expected time to discover a new item in
the system.
  We study the Schedule Optimization problem both for deterministic and
randomized memoryless algorithms. We provide lower bounds on the cost of an
optimal schedule and construct close to optimal schedules with rigorous
mathematical guarantees. Finally, we present an adaptive algorithm that starts
with no prior information on the system and converges to the optimal memoryless
algorithms by adapting to observed data.
Proposal-free Network for Instance-level Object Segmentation
Authors: Xiaodan Liang, Yunchao Wei, Xiaohui Shen, Jianchao Yang, Liang Lin, Shuicheng Yan
Date: 2015-09-09 00:00:00
Tasks: Clustering, Object, Region Proposal, Segmentation, Semantic Segmentation

Instance-level object segmentation is an important yet under-explored task.
The few existing studies are almost all based on region proposal methods to
extract candidate segments and then utilize object classification to produce
final results. Nonetheless, generating accurate region proposals itself is
quite challenging. In this work, we propose a Proposal-Free Network (PFN ) to
address the instance-level object segmentation problem, which outputs the
instance numbers of different categories and the pixel-level information on 1)
the coordinates of the instance bounding box each pixel belongs to, and 2) the
confidences of different categories for each pixel, based on pixel-to-pixel
deep convolutional neural network. All the outputs together, by using any
off-the-shelf clustering method for simple post-processing, can naturally
generate the ultimate instance-level object segmentation results. The whole PFN
can be easily trained in an end-to-end way without the requirement of a
proposal generation stage. Extensive evaluations on the challenging PASCAL VOC
2012 semantic segmentation benchmark demonstrate that the proposed PFN solution
well beats the state-of-the-arts for instance-level object segmentation. In
particular, the $AP^r$ over 20 classes at 0.5 IoU reaches 58.7% by PFN,
significantly higher than 43.8% and 46.3% by the state-of-the-art algorithms,
SDS [9] and [16], respectively.
Dictionary Learning and Sparse Coding for Third-order Super-symmetric Tensors
Authors: Piotr Koniusz, Anoop Cherian
Date: 2015-09-09 00:00:00
Tasks: Dictionary Learning

Super-symmetric tensors - a higher-order extension of scatter matrices - are
becoming increasingly popular in machine learning and computer vision for
modelling data statistics, co-occurrences, or even as visual descriptors.
However, the size of these tensors are exponential in the data dimensionality,
which is a significant concern. In this paper, we study third-order
super-symmetric tensor descriptors in the context of dictionary learning and
sparse coding. Our goal is to approximate these tensors as sparse conic
combinations of atoms from a learned dictionary, where each atom is a symmetric
positive semi-definite matrix. Apart from the significant benefits to tensor
compression that this framework provides, our experiments demonstrate that the
sparse coefficients produced by the scheme lead to better aggregation of
high-dimensional data, and showcases superior performance on two common
computer vision tasks compared to the state-of-the-art.
Coarse-to-Fine Sequential Monte Carlo for Probabilistic Programs
Authors: Andreas Stuhlmüller, Robert X. D. Hawkins, N. Siddharth, Noah D. Goodman
Date: 2015-09-09 00:00:00

Many practical techniques for probabilistic inference require a sequence of
distributions that interpolate between a tractable distribution and an
intractable distribution of interest. Usually, the sequences used are simple,
e.g., based on geometric averages between distributions. When models are
expressed as probabilistic programs, the models themselves are highly
structured objects that can be used to derive annealing sequences that are more
sensitive to domain structure. We propose an algorithm for transforming
probabilistic programs to coarse-to-fine programs which have the same marginal
distribution as the original programs, but generate the data at increasing
levels of detail, from coarse to fine. We apply this algorithm to an Ising
model, its depth-from-disparity variation, and a factorial hidden Markov model.
We show preliminary evidence that the use of coarse-to-fine models can make
existing generic inference algorithms more efficient.
Sensor Selection by Linear Programming
Authors: Joseph Wang, Kirill Trapeznikov, Venkatesh Saligrama
Date: 2015-09-09 00:00:00
Tasks: Computational Efficiency

We learn sensor trees from training data to minimize sensor acquisition costs
during test time. Our system adaptively selects sensors at each stage if
necessary to make a confident classification. We pose the problem as empirical
risk minimization over the choice of trees and node decision rules. We
decompose the problem, which is known to be intractable, into combinatorial
(tree structures) and continuous parts (node decision rules) and propose to
solve them separately. Using training data we greedily solve for the
combinatorial tree structures and for the continuous part, which is a
non-convex multilinear objective function, we derive convex surrogate loss
functions that are piecewise linear. The resulting problem can be cast as a
linear program and has the advantage of guaranteed convergence, global
optimality, repeatability and computational efficiency. We show that our
proposed approach outperforms the state-of-art on a number of benchmark
datasets.
Sampling-based Approximations with Quantitative Performance for the Probabilistic Reach-Avoid Problem over General Markov Processes
Authors: Sofie Haesaert, Robert Babuska, Alessandro Abate
Date: 2014-09-01 00:00:00

This article deals with stochastic processes endowed with the Markov
(memoryless) property and evolving over general (uncountable) state spaces. The
models further depend on a non-deterministic quantity in the form of a control
input, which can be selected to affect the probabilistic dynamics. We address
the computation of maximal reach-avoid specifications, together with the
synthesis of the corresponding optimal controllers. The reach-avoid
specification deals with assessing the likelihood that any finite-horizon
trajectory of the model enters a given goal set, while avoiding a given set of
undesired states. This article newly provides an approximate computational
scheme for the reach-avoid specification based on the Fitted Value Iteration
algorithm, which hinges on random sample extractions, and gives a-priori
computable formal probabilistic bounds on the error made by the approximation
algorithm: as such, the output of the numerical scheme is quantitatively
assessed and thus meaningful for safety-critical applications. Furthermore, we
provide tighter probabilistic error bounds that are sample-based. The overall
computational scheme is put in relationship with alternative approximation
algorithms in the literature, and finally its performance is practically
assessed over a benchmark case study.
Sélection de variables par le GLM-Lasso pour la prédiction du risque palustre
Authors: Bienvenue Kouwayè, Noël Fonton, Fabrice Rossi
Date: 2015-09-09 00:00:00
Tasks: Epidemiology, Variable Selection

In this study, we propose an automatic learning method for variables
selection based on Lasso in epidemiology context. One of the aim of this
approach is to overcome the pretreatment of experts in medicine and
epidemiology on collected data. These pretreatment consist in recoding some
variables and to choose some interactions based on expertise. The approach
proposed uses all available explanatory variables without treatment and
generate automatically all interactions between them. This lead to high
dimension. We use Lasso, one of the robust methods of variable selection in
high dimension. To avoid over fitting a two levels cross-validation is used.
Because the target variable is account variable and the lasso estimators are
biased, variables selected by lasso are debiased by a GLM and used to predict
the distribution of the main vector of malaria which is Anopheles. Results show
that only few climatic and environmental variables are the mains factors
associated to the malaria risk exposure.
Transfer learning approach for financial applications
Authors: Cosmin Stamate, George D. Magoulas, Michael S. C. Thomas
Date: 2015-09-09 00:00:00
Tasks: Transfer Learning

Artificial neural networks learn how to solve new problems through a
computationally intense and time consuming process. One way to reduce the
amount of time required is to inject preexisting knowledge into the network. To
make use of past knowledge, we can take advantage of techniques that transfer
the knowledge learned from one task, and reuse it on another (sometimes
unrelated) task. In this paper we propose a novel selective breeding technique
that extends the transfer learning with behavioural genetics approach proposed
by Kohli, Magoulas and Thomas (2013), and evaluate its performance on financial
data. Numerical evidence demonstrates the credibility of the new approach. We
provide insights on the operation of transfer learning and highlight the
benefits of using behavioural principles and selective breeding when tackling a
set of diverse financial applications problems.
Finite Dictionary Variants of the Diffusion KLMS Algorithm
Authors: Rangeet Mitra, Vimal Bhatia
Date: 2015-09-09 00:00:00

The diffusion based distributed learning approaches have been found to be a
viable solution for learning over linearly separable datasets over a network.
However, approaches till date are suitable for linearly separable datasets and
need to be extended to scenarios in which we need to learn a non-linearity. In
such scenarios, the recently proposed diffusion kernel least mean squares
(KLMS) has been found to be performing better than diffusion least mean squares
(LMS). The drawback of diffusion KLMS is that it requires infinite storage for
observations (also called dictionary). This paper formulates the diffusion KLMS
in a fixed budget setting such that the storage requirement is curtailed while
maintaining appreciable performance in terms of convergence. Simulations have
been carried out to validate the two newly proposed algorithms named as
quantised diffusion KLMS (QDKLMS) and fixed budget diffusion KLMS (FBDKLMS)
against KLMS, which indicate that both the proposed algorithms deliver better
performance as compared to the KLMS while reducing the dictionary size storage
requirement.
Visual Understanding via Multi-Feature Shared Learning with Global Consistency
Authors: Lei Zhang, David Zhang
Date: 2015-05-20 00:00:00

Image/video data is usually represented with multiple visual features. Fusion
of multi-source information for establishing the attributes has been widely
recognized. Multi-feature visual recognition has recently received much
attention in multimedia applications. This paper studies visual understanding
via a newly proposed l_2-norm based multi-feature shared learning framework,
which can simultaneously learn a global label matrix and multiple
sub-classifiers with the labeled multi-feature data. Additionally, a group
graph manifold regularizer composed of the Laplacian and Hessian graph is
proposed for better preserving the manifold structure of each feature, such
that the label prediction power is much improved through the semi-supervised
learning with global label consistency. For convenience, we call the proposed
approach Global-Label-Consistent Classifier (GLCC). The merits of the proposed
method include: 1) the manifold structure information of each feature is
exploited in learning, resulting in a more faithful classification owing to the
global label consistency; 2) a group graph manifold regularizer based on the
Laplacian and Hessian regularization is constructed; 3) an efficient
alternative optimization method is introduced as a fast solver owing to the
convex sub-problems. Experiments on several benchmark visual datasets for
multimedia understanding, such as the 17-category Oxford Flower dataset, the
challenging 101-category Caltech dataset, the YouTube & Consumer Videos dataset
and the large-scale NUS-WIDE dataset, demonstrate that the proposed approach
compares favorably with the state-of-the-art algorithms. An extensive
experiment on the deep convolutional activation features also show the
effectiveness of the proposed approach. The code is available on
http://www.escience.cn/people/lei/index.html
Communication: Words and Conceptual Systems
Authors: Jian Yu
Date: 2015-07-29 00:00:00

Words (phrases or symbols) play a key role in human life. Word (phrase or
symbol) representation is the fundamental problem for knowledge representation
and understanding. A word (phrase or symbol) usually represents a name of a
category. However, it is always a challenge that how to represent a category
can make it easily understood. In this paper, a new representation for a
category is discussed, which can be considered a generalization of classic set.
In order to reduce representation complexity, the economy principle of category
representation is proposed. The proposed category representation provides a
powerful tool for analyzing conceptual systems, relations between words,
communication, knowledge, situations. More specifically, the conceptual system,
word relations and communication are mathematically defined and classified such
as ideal conceptual system, perfect communication and so on; relation between
words and sentences is also studied, which shows that knowledge are words.
Furthermore, how conceptual systems and words depend on situations is
presented, and how truth is defined is also discussed.
Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
Authors: Yuchen Zhang, Lin Xiao
Date: 2014-09-10 00:00:00

We consider a generic convex optimization problem associated with regularized
empirical risk minimization of linear predictors. The problem structure allows
us to reformulate it as a convex-concave saddle point problem. We propose a
stochastic primal-dual coordinate (SPDC) method, which alternates between
maximizing over a randomly chosen dual variable and minimizing over the primal
variable. An extrapolation step on the primal variable is performed to obtain
accelerated convergence rate. We also develop a mini-batch version of the SPDC
method which facilitates parallel computing, and an extension with weighted
sampling probabilities on the dual variables, which has a better complexity
than uniform sampling on unnormalized data. Both theoretically and empirically,
we show that the SPDC method has comparable or better performance than several
state-of-the-art optimization methods.
Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
Authors: Peng Wang, Chunhua Shen, Anton Van Den Hengel, Philip Torr
Date: 2014-04-20 00:00:00

We propose a Branch-and-Cut (B&C) method for solving general MAP-MRF
inference problems. The core of our method is a very efficient bounding
procedure, which combines scalable semidefinite programming (SDP) and a
cutting-plane method for seeking violated constraints. In order to further
speed up the computation, several strategies have been exploited, including
model reduction, warm start and removal of inactive constraints.
  We analyze the performance of the proposed method under different settings,
and demonstrate that our method either outperforms or performs on par with
state-of-the-art approaches. Especially when the connectivities are dense or
when the relative magnitudes of the unary costs are low, we achieve the best
reported results. Experiments show that the proposed algorithm achieves better
approximation than the state-of-the-art methods within a variety of time
budgets on challenging non-submodular MAP-MRF inference problems.
Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance
Authors: Tsung-Hui Chang, Wei-Cheng Liao, Mingyi Hong, Xiangfeng Wang
Date: 2015-09-09 00:00:00

The alternating direction method of multipliers (ADMM) has been recognized as
a versatile approach for solving modern large-scale machine learning and signal
processing problems efficiently. When the data size and/or the problem
dimension is large, a distributed version of ADMM can be used, which is capable
of distributing the computation load and the data set to a network of computing
nodes. Unfortunately, a direct synchronous implementation of such algorithm
does not scale well with the problem size, as the algorithm speed is limited by
the slowest computing nodes. To address this issue, in a companion paper, we
have proposed an asynchronous distributed ADMM (AD-ADMM) and studied its
worst-case convergence conditions. In this paper, we further the study by
characterizing the conditions under which the AD-ADMM achieves linear
convergence. Our conditions as well as the resulting linear rates reveal the
impact that various algorithm parameters, network delay and network size have
on the algorithm performance. To demonstrate the superior time efficiency of
the proposed AD-ADMM, we test the AD-ADMM on a high-performance computer
cluster by solving a large-scale logistic regression problem.
A nonlinear aggregation type classifier
Authors: Alejandro Cholaquidis, Ricardo Fraiman, Juan Kalemkerian, Pamela Llop
Date: 2015-09-04 00:00:00
Tasks: Vocal Bursts Type Prediction

We introduce a nonlinear aggregation type classifier for functional data
defined on a separable and complete metric space. The new rule is built up from
a collection of $M$ arbitrary training classifiers. If the classifiers are
consistent, then so is the aggregation rule. Moreover, asymptotically the
aggregation rule behaves as well as the best of the $M$ classifiers. The
results of a small simulation are reported both, for high dimensional and
functional data, and a real data example is analyzed.