pwc-archive/papers-with-abstracts huggingface dataset:
Statistical inference on errorfully observed graphs
Authors: Carey E. Priebe, Daniel L. Sussman, Minh Tang, Joshua T. Vogelstein
Date: 2012-11-15 00:00:00

Statistical inference on graphs is a burgeoning field in the applied and
theoretical statistics communities, as well as throughout the wider world of
science, engineering, business, etc. In many applications, we are faced with
the reality of errorfully observed graphs. That is, the existence of an edge
between two vertices is based on some imperfect assessment. In this paper, we
consider a graph $G = (V,E)$. We wish to perform an inference task -- the
inference task considered here is "vertex classification". However, we do not
observe $G$; rather, for each potential edge $uv \in {{V}\choose{2}}$ we
observe an "edge-feature" which we use to classify $uv$ as edge/not-edge. Thus
we errorfully observe $G$ when we observe the graph $\widetilde{G} =
(V,\widetilde{E})$ as the edges in $\widetilde{E}$ arise from the
classifications of the "edge-features", and are expected to be errorful.
Moreover, we face a quantity/quality trade-off regarding the edge-features we
observe -- more informative edge-features are more expensive, and hence the
number of potential edges that can be assessed decreases with the quality of
the edge-features. We studied this problem by formulating a quantity/quality
tradeoff for a simple class of random graphs model, namely the stochastic
blockmodel. We then consider a simple but optimal vertex classifier for
classifying $v$ and we derive the optimal quantity/quality operating point for
subsequent graph inference in the face of this trade-off. The optimal operating
points for the quantity/quality trade-off are surprising and illustrate the
issue that methods for intermediate tasks should be chosen to maximize
performance for the ultimate inference task. Finally, we investigate the
quantity/quality tradeoff for errorful obesrvations of the {\it C.\ elegans}
connectome graph.
Completing Any Low-rank Matrix, Provably
Authors: Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, Rachel Ward
Date: 2013-06-12 00:00:00
Tasks: Matrix Completion

Matrix completion, i.e., the exact and provable recovery of a low-rank matrix
from a small subset of its elements, is currently only known to be possible if
the matrix satisfies a restrictive structural constraint---known as {\em
incoherence}---on its row and column spaces. In these cases, the subset of
elements is sampled uniformly at random.
  In this paper, we show that {\em any} rank-$ r $ $ n$-by-$ n $ matrix can be
exactly recovered from as few as $O(nr \log^2 n)$ randomly chosen elements,
provided this random choice is made according to a {\em specific biased
distribution}: the probability of any element being sampled should be
proportional to the sum of the leverage scores of the corresponding row, and
column. Perhaps equally important, we show that this specific form of sampling
is nearly necessary, in a natural precise sense; this implies that other
perhaps more intuitive sampling schemes fail.
  We further establish three ways to use the above result for the setting when
leverage scores are not known \textit{a priori}: (a) a sampling strategy for
the case when only one of the row or column spaces are incoherent, (b) a
two-phase sampling procedure for general matrices that first samples to
estimate leverage scores followed by sampling for exact recovery, and (c) an
analysis showing the advantages of weighted nuclear/trace-norm minimization
over the vanilla un-weighted formulation for the case of non-uniform sampling.
Are There Good Mistakes? A Theoretical Analysis of CEGIS
Authors: Susmit Jha, Sanjit A. Seshia
Date: 2014-07-21 00:00:00

Counterexample-guided inductive synthesis CEGIS is used to synthesize
programs from a candidate space of programs. The technique is guaranteed to
terminate and synthesize the correct program if the space of candidate programs
is finite. But the technique may or may not terminate with the correct program
if the candidate space of programs is infinite. In this paper, we perform a
theoretical analysis of counterexample-guided inductive synthesis technique. We
investigate whether the set of candidate spaces for which the correct program
can be synthesized using CEGIS depends on the counterexamples used in inductive
synthesis, that is, whether there are good mistakes which would increase the
synthesis power. We investigate whether the use of minimal counterexamples
instead of arbitrary counterexamples expands the set of candidate spaces of
programs for which inductive synthesis can successfully synthesize a correct
program. We consider two kinds of counterexamples: minimal counterexamples and
history bounded counterexamples. The history bounded counterexample used in any
iteration of CEGIS is bounded by the examples used in previous iterations of
inductive synthesis. We examine the relative change in power of inductive
synthesis in both cases. We show that the synthesis technique using minimal
counterexamples MinCEGIS has the same synthesis power as CEGIS but the
synthesis technique using history bounded counterexamples HCEGIS has different
power than that of CEGIS, but none dominates the other.
Representing and Reasoning about Game Strategies
Authors: Dongmo Zhang, Michael Thielsher
Date: 2014-07-21 00:00:00

As a contribution to the challenge of building game-playing AI systems, we
develop and analyse a formal language for representing and reasoning about
strategies. Our logical language builds on the existing general Game
Description Language (GDL) and extends it by a standard modality for linear
time along with two dual connectives to express preferences when combining
strategies. The semantics of the language is provided by a standard
state-transition model. As such, problems that require reasoning about games
can be solved by the standard methods for reasoning about actions and change.
We also endow the language with a specific semantics by which strategy formulas
are understood as move recommendations for a player. To illustrate how our
formalism supports automated reasoning about strategies, we demonstrate two
example methods of implementation\/: first, we formalise the semantic
interpretation of our language in conjunction with game rules and strategy
rules in the Situation Calculus; second, we show how the reasoning problem can
be solved with Answer Set Programming.
Impact of regularization on Spectral Clustering
Authors: Antony Joseph, Bin Yu
Date: 2013-12-05 00:00:00
Tasks: Clustering, Stochastic Block Model

The performance of spectral clustering can be considerably improved via
regularization, as demonstrated empirically in Amini et. al (2012). Here, we
provide an attempt at quantifying this improvement through theoretical
analysis. Under the stochastic block model (SBM), and its extensions, previous
results on spectral clustering relied on the minimum degree of the graph being
sufficiently large for its good performance. By examining the scenario where
the regularization parameter $\tau$ is large we show that the minimum degree
assumption can potentially be removed. As a special case, for an SBM with two
blocks, the results require the maximum degree to be large (grow faster than
$\log n$) as opposed to the minimum degree.
  More importantly, we show the usefulness of regularization in situations
where not all nodes belong to well-defined clusters. Our results rely on a
`bias-variance'-like trade-off that arises from understanding the concentration
of the sample Laplacian and the eigen gap as a function of the regularization
parameter. As a byproduct of our bounds, we propose a data-driven technique
\textit{DKest} (standing for estimated Davis-Kahan bounds) for choosing the
regularization parameter. This technique is shown to work well through
simulations and on a real data set.
Certifying the Existence of Epipolar Matrices
Authors: Sameer Agarwal, Hon-Leung Lee, Bernd Sturmfels, Rekha R. Thomas
Date: 2014-07-21 00:00:00
Tasks: Camera Calibration

Given a set of point correspondences in two images, the existence of a
fundamental matrix is a necessary condition for the points to be the images of
a 3-dimensional scene imaged with two pinhole cameras. If the camera
calibration is known then one requires the existence of an essential matrix.
  We present an efficient algorithm, using exact linear algebra, for testing
the existence of a fundamental matrix. The input is any number of point
correspondences. For essential matrices, we characterize the solvability of the
Demazure polynomials. In both scenarios, we determine which linear subspaces
intersect a fixed set defined by non-linear polynomials. The conditions we
derive are polynomials stated purely in terms of image coordinates. They
represent a new class of two-view invariants, free of fundamental
(resp.~essential)~matrices.
Practical Kernel-Based Reinforcement Learning
Authors: André M. S. Barreto, Doina Precup, Joelle Pineau
Date: 2014-07-21 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Kernel-based reinforcement learning (KBRL) stands out among reinforcement
learning algorithms for its strong theoretical guarantees. By casting the
learning problem as a local kernel approximation, KBRL provides a way of
computing a decision policy which is statistically consistent and converges to
a unique solution. Unfortunately, the model constructed by KBRL grows with the
number of sample transitions, resulting in a computational cost that precludes
its application to large-scale or on-line domains. In this paper we introduce
an algorithm that turns KBRL into a practical reinforcement learning tool.
Kernel-based stochastic factorization (KBSF) builds on a simple idea: when a
transition matrix is represented as the product of two stochastic matrices, one
can swap the factors of the multiplication to obtain another transition matrix,
potentially much smaller, which retains some fundamental properties of its
precursor. KBSF exploits such an insight to compress the information contained
in KBRL's model into an approximator of fixed size. This makes it possible to
build an approximation that takes into account both the difficulty of the
problem and the associated computational cost. KBSF's computational complexity
is linear in the number of sample transitions, which is the best one can do
without discarding data. Moreover, the algorithm's simple mechanics allow for a
fully incremental implementation that makes the amount of memory used
independent of the number of sample transitions. The result is a kernel-based
reinforcement learning algorithm that can be applied to large-scale problems in
both off-line and on-line regimes. We derive upper bounds for the distance
between the value functions computed by KBRL and KBSF using the same data. We
also illustrate the potential of our algorithm in an extensive empirical study
in which KBSF is applied to difficult tasks based on real-world data.
Robust Spectral Compressed Sensing via Structured Matrix Completion
Authors: Yuxin Chen, Yuejie Chi
Date: 2013-04-30 00:00:00
Tasks: compressed sensing, Matrix Completion, Super-Resolution

The paper explores the problem of \emph{spectral compressed sensing}, which
aims to recover a spectrally sparse signal from a small random subset of its
$n$ time domain samples. The signal of interest is assumed to be a
superposition of $r$ multi-dimensional complex sinusoids, while the underlying
frequencies can assume any \emph{continuous} values in the normalized frequency
domain. Conventional compressed sensing paradigms suffer from the basis
mismatch issue when imposing a discrete dictionary on the Fourier
representation. To address this issue, we develop a novel algorithm, called
\emph{Enhanced Matrix Completion (EMaC)}, based on structured matrix completion
that does not require prior knowledge of the model order. The algorithm starts
by arranging the data into a low-rank enhanced form exhibiting multi-fold
Hankel structure, and then attempts recovery via nuclear norm minimization.
Under mild incoherence conditions, EMaC allows perfect recovery as soon as the
number of samples exceeds the order of $r\log^{4}n$, and is stable against
bounded noise. Even if a constant portion of samples are corrupted with
arbitrary magnitude, EMaC still allows exact recovery, provided that the sample
complexity exceeds the order of $r^{2}\log^{3}n$. Along the way, our results
demonstrate the power of convex relaxation in completing a low-rank multi-fold
Hankel or Toeplitz matrix from minimal observed entries. The performance of our
algorithm and its applicability to super resolution are further validated by
numerical experiments.
Efficient Learning and Planning with Compressed Predictive States
Authors: William L. Hamilton, Mahdi Milani Fard, Joelle Pineau
Date: 2013-12-01 00:00:00
Tasks: compressed sensing, Dimensionality Reduction, Model-based Reinforcement Learning, Reinforcement Learning

Predictive state representations (PSRs) offer an expressive framework for
modelling partially observable systems. By compactly representing systems as
functions of observable quantities, the PSR learning approach avoids using
local-minima prone expectation-maximization and instead employs a globally
optimal moment-based algorithm. Moreover, since PSRs do not require a
predetermined latent state structure as an input, they offer an attractive
framework for model-based reinforcement learning when agents must plan without
a priori access to a system model. Unfortunately, the expressiveness of PSRs
comes with significant computational cost, and this cost is a major factor
inhibiting the use of PSRs in applications. In order to alleviate this
shortcoming, we introduce the notion of compressed PSRs (CPSRs). The CPSR
learning approach combines recent advancements in dimensionality reduction,
incremental matrix decomposition, and compressed sensing. We show how this
approach provides a principled avenue for learning accurate approximations of
PSRs, drastically reducing the computational costs associated with learning
while also providing effective regularization. Going further, we propose a
planning framework which exploits these learned models. And we show that this
approach facilitates model-learning and planning in large complex partially
observable domains, a task that is infeasible without the principled use of
compression.
A Comparative Analysis for Determining the Optimal Path using PSO and GA
Authors: Kavitha Sooda, T. R. Gopalakrishnan Nair
Date: 2014-07-20 00:00:00

Significant research has been carried out recently to find the optimal path
in network routing. Among them, the evolutionary algorithm approach is an area
where work is carried out extensively. We in this paper have used particle
swarm optimization (PSO) and genetic algorithm (GA) for finding the optimal
path and the concept of region based network is introduced along with the use
of indirect encoding. We demonstrate the advantage of fitness value and hop
count in both PSO and GA. A comparative study of PSO and genetic algorithm (GA)
is carried out, and it was found that PSO converged to arrive at the optimal
path much faster than GA.
Optimized Method for Iranian Road Signs Detection and recognition system
Authors: Reza Azad, Babak Azad, Iman Tavakoli Kazerooni
Date: 2014-07-20 00:00:00
Tasks: Edge Detection

Road sign recognition is one of the core technologies in Intelligent
Transport Systems. In the current study, a robust and real-time method is
presented to identify and detect the roads speed signs in road image in
different situations. In our proposed method, first, the connected components
are created in the main image using the edge detection and mathematical
morphology and the location of the road signs extracted by the geometric and
color data; then the letters are segmented and recognized by Multiclass Support
Vector Machine (SVMs) classifiers. Regarding that the geometric and color
features ate properly used in detection the location of the road signs, so it
is not sensitive to the distance and noise and has higher speed and efficiency.
In the result part, the proposed approach is applied on Iranian road speed sign
database and the detection and recognition accuracy rate achieved 98.66% and
100% respectively.
Object Proposal Generation using Two-Stage Cascade SVMs
Authors: Ziming Zhang, Philip H. S. Torr
Date: 2014-07-20 00:00:00
Tasks: Computational Efficiency, Object, Object Proposal Generation, Object Recognition, Quantization, Vocal Bursts Valence Prediction

Object proposal algorithms have shown great promise as a first step for
object recognition and detection. Good object proposal generation algorithms
require high object recall rate as well as low computational cost, because
generating object proposals is usually utilized as a preprocessing step. The
problem of how to accelerate the object proposal generation and evaluation
process without decreasing recall is thus of great interest. In this paper, we
propose a new object proposal generation method using two-stage cascade SVMs,
where in the first stage linear filters are learned for predefined quantized
scales/aspect-ratios independently, and in the second stage a global linear
classifier is learned across all the quantized scales/aspect-ratios for
calibration, so that all the proposals can be compared properly. The proposals
with highest scores are our final output. Specifically, we explain our
scale/aspect-ratio quantization scheme, and investigate the effects of
combinations of $\ell_1$ and $\ell_2$ regularizers in cascade SVMs with/without
ranking constraints in learning. Comprehensive experiments on VOC2007 dataset
are conducted, and our results achieve the state-of-the-art performance with
high object recall rate and high computational efficiency. Besides, our method
has been demonstrated to be suitable for not only class-specific but also
generic object proposal generation.
A fast and robust algorithm to count topologically persistent holes in noisy clouds
Authors: Vitaliy Kurlin
Date: 2013-12-05 00:00:00
Proceeding: CVPR 2014 6

Preprocessing a 2D image often produces a noisy cloud of interest points. We
study the problem of counting holes in unorganized clouds in the plane. The
holes in a given cloud are quantified by the topological persistence of their
boundary contours when the cloud is analyzed at all possible scales. We design
the algorithm to count holes that are most persistent in the filtration of
offsets (neighborhoods) around given points. The input is a cloud of $n$ points
in the plane without any user-defined parameters. The algorithm has $O(n\log
n)$ time and $O(n)$ space. The output is the array (number of holes, relative
persistence in the filtration). We prove theoretical guarantees when the
algorithm finds the correct number of holes (components in the complement) of
an unknown shape approximated by a cloud.
Context Aware Dynamic Traffic Signal Optimization
Authors: Kandarp Khandwala, Rudra Sharma, Snehal Rao
Date: 2014-07-19 00:00:00
Tasks: Fairness

Conventional urban traffic control systems have been based on historical
traffic data. Later advancements made use of detectors, which enabled the
gathering of real time traffic data, in order to reorganize and calibrate
traffic signalization programs. Further evolvement provided the ability to
forecast traffic conditions, in order to develop traffic signalization programs
and strategies precomputed and applied at the most appropriate time frame for
the optimal control of the current traffic conditions. We, propose the next
generation of traffic control systems based on principles of Artificial
Intelligence and Context Awareness. Most of the existing algorithms use average
waiting time or length of the queue to assess an algorithms performance.
However, a low average waiting time may come at the cost of delaying other
vehicles indefinitely. In our algorithm, besides the vehicle queue, we use
fairness also as an important performance metric to assess an algorithms
performance.
A machine-compiled macroevolutionary history of Phanerozoic life
Authors: Shanan E. Peters, Ce Zhang, Miron Livny, Christopher Ré
Date: 2014-06-11 00:00:00
Tasks: Data Integration, Reading Comprehension

Many aspects of macroevolutionary theory and our understanding of biotic
responses to global environmental change derive from literature-based
compilations of palaeontological data. Existing manually assembled databases
are, however, incomplete and difficult to assess and enhance. Here, we develop
and validate the quality of a machine reading system, PaleoDeepDive, that
automatically locates and extracts data from heterogeneous text, tables, and
figures in publications. PaleoDeepDive performs comparably to humans in complex
data extraction and inference tasks and generates congruent synthetic
macroevolutionary results. Unlike traditional databases, PaleoDeepDive produces
a probabilistic database that systematically improves as information is added.
We also show that the system can readily accommodate sophisticated data types,
such as morphological data in biological illustrations and associated textual
descriptions. Our machine reading approach to scientific data integration and
synthesis brings within reach many questions that are currently underdetermined
and does so in ways that may stimulate entirely new modes of inquiry.
Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
Authors: Mehrdad Mahdavi
Date: 2014-07-19 00:00:00
Tasks: Stochastic Optimization

In the last several years, the intimate connection between convex
optimization and learning problems, in both statistical and sequential
frameworks, has shifted the focus of algorithmic machine learning to examine
this interplay. In particular, on one hand, this intertwinement brings forward
new challenges in reassessment of the performance of learning algorithms
including generalization and regret bounds under the assumptions imposed by
convexity such as analytical properties of loss functions (e.g., Lipschitzness,
strong convexity, and smoothness). On the other hand, emergence of datasets of
an unprecedented size, demands the development of novel and more efficient
optimization algorithms to tackle large-scale learning problems.
  The overarching goal of this thesis is to reassess the smoothness of loss
functions in statistical learning, sequential prediction/online learning, and
stochastic optimization and explicate its consequences. In particular we
examine how smoothness of loss function could be beneficial or detrimental in
these settings in terms of sample complexity, statistical consistency, regret
analysis, and convergence rate, and investigate how smoothness can be leveraged
to devise more efficient learning algorithms.
On the minimal teaching sets of two-dimensional threshold functions
Authors: Max A. Alekseyev, Marina G. Basova, Nikolai Yu. Zolotykh
Date: 2013-07-03 00:00:00
Tasks: Vocal Bursts Valence Prediction

It is known that a minimal teaching set of any threshold function on the
twodimensional rectangular grid consists of 3 or 4 points. We derive exact
formulae for the numbers of functions corresponding to these values and further
refine them in the case of a minimal teaching set of size 3. We also prove that
the average cardinality of the minimal teaching sets of threshold functions is
asymptotically 7/2.
  We further present corollaries of these results concerning some special
arrangements of lines in the plane.