pwc-archive/papers-with-abstracts huggingface dataset:
Sequential Sensing with Model Mismatch
Authors: Ruiyang Song, Yao Xie, Sebastian Pokutta
Date: 2015-01-26 00:00:00
Tasks: model

We characterize the performance of sequential information guided sensing,
Info-Greedy Sensing, when there is a mismatch between the true signal model and
the assumed model, which may be a sample estimate. In particular, we consider a
setup where the signal is low-rank Gaussian and the measurements are taken in
the directions of eigenvectors of the covariance matrix in a decreasing order
of eigenvalues. We establish a set of performance bounds when a mismatched
covariance matrix is used, in terms of the gap of signal posterior entropy, as
well as the additional amount of power required to achieve the same signal
recovery precision. Based on this, we further study how to choose an
initialization for Info-Greedy Sensing using the sample covariance matrix, or
using an efficient covariance sketching scheme.
GeomRDF: A Geodata Converter with a Fine-Grained Structured Representation of Geometry in the Web
Authors: Fayçal Hamdi, Nathalie Abadie, Bénédicte Bucher, Abdelfettah Feliachi
Date: 2015-03-16 00:00:00

In recent years, with the advent of the web of data, a growing number of
national mapping agencies tend to publish their geospatial data as Linked Data.
However, differences between traditional GIS data models and Linked Data model
can make the publication process more complicated. Besides, it may require, to
be done, the setting of several parameters and some expertise in the semantic
web technologies. In addition, the use of standards like GeoSPARQL (or ad hoc
predicates) is mandatory to perform spatial queries on published geospatial
data. In this paper, we present GeomRDF, a tool that helps users to convert
spatial data from traditional GIS formats to RDF model easily. It generates
geometries represented as GeoSPARQL WKT literal but also as structured
geometries that can be exploited by using only the RDF query language, SPARQL.
GeomRDF was implemented as a module in the RDF publication platform Datalift. A
validation of GeomRDF has been realized against the French administrative units
dataset (provided by IGN France).
A distributed block coordinate descent method for training $l_1$ regularized linear classifiers
Authors: Dhruv Mahajan, S. Sathiya Keerthi, S. Sundararajan
Date: 2014-05-18 00:00:00

Distributed training of $l_1$ regularized classifiers has received great
attention recently. Most existing methods approach this problem by taking steps
obtained from approximating the objective by a quadratic approximation that is
decoupled at the individual variable level. These methods are designed for
multicore and MPI platforms where communication costs are low. They are
inefficient on systems such as Hadoop running on a cluster of commodity
machines where communication costs are substantial. In this paper we design a
distributed algorithm for $l_1$ regularization that is much better suited for
such systems than existing algorithms. A careful cost analysis is used to
support these points and motivate our method. The main idea of our algorithm is
to do block optimization of many variables on the actual objective function
within each computing node; this increases the computational cost per step that
is matched with the communication cost, and decreases the number of outer
iterations, thus yielding a faster overall method. Distributed Gauss-Seidel and
Gauss-Southwell greedy schemes are used for choosing variables to update in
each step. We establish global convergence theory for our algorithm, including
Q-linear rate of convergence. Experiments on two benchmark problems show our
method to be much faster than existing methods.
Visual Chunking: A List Prediction Framework for Region-Based Object Detection
Authors: Nicholas Rhinehart, Jiaji Zhou, Martial Hebert, J. Andrew Bagnell
Date: 2014-10-27 00:00:00
Tasks: Chunking, object-detection, Object Detection, Superpixels

We consider detecting objects in an image by iteratively selecting from a set
of arbitrarily shaped candidate regions. Our generic approach, which we term
visual chunking, reasons about the locations of multiple object instances in an
image while expressively describing object boundaries. We design an
optimization criterion for measuring the performance of a list of such
detections as a natural extension to a common per-instance metric. We present
an efficient algorithm with provable performance for building a high-quality
list of detections from any candidate set of region-based proposals. We also
develop a simple class-specific algorithm to generate a candidate region
instance in near-linear time in the number of low-level superpixels that
outperforms other region generating methods. In order to make predictions on
novel images at testing time without access to ground truth, we develop
learning approaches to emulate these algorithms' behaviors. We demonstrate that
our new approach outperforms sophisticated baselines on benchmark datasets.
An efficient distributed learning algorithm based on effective local functional approximations
Authors: Dhruv Mahajan, Nikunj Agrawal, S. Sathiya Keerthi, S. Sundararajan, Leon Bottou
Date: 2013-10-31 00:00:00
Tasks: L2 Regularization

Scalable machine learning over big data is an important problem that is
receiving a lot of attention in recent years. On popular distributed
environments such as Hadoop running on a cluster of commodity machines,
communication costs are substantial and algorithms need to be designed suitably
considering those costs. In this paper we give a novel approach to the
distributed training of linear classifiers (involving smooth losses and L2
regularization) that is designed to reduce the total communication costs. At
each iteration, the nodes minimize locally formed approximate objective
functions; then the resulting minimizers are combined to form a descent
direction to move. Our approach gives a lot of freedom in the formation of the
approximate objective function as well as in the choice of methods to solve
them. The method is shown to have $O(log(1/\epsilon))$ time convergence. The
method can be viewed as an iterative parameter mixing method. A special
instantiation yields a parallel stochastic gradient descent method with strong
convergence. When communication times between nodes are large, our method is
much faster than the Terascale method (Agarwal et al., 2011), which is a state
of the art distributed solver based on the statistical query model (Chuet al.,
2006) that computes function and gradient values in a distributed fashion. We
also evaluate against other recent distributed methods and demonstrate superior
performance of our method.
All Who Wander: On the Prevalence and Characteristics of Multi-community Engagement
Authors: Chenhao Tan, Lillian Lee
Date: 2015-03-04 00:00:00
Tasks: All

Although analyzing user behavior within individual communities is an active
and rich research domain, people usually interact with multiple communities
both on- and off-line. How do users act in such multi-community environments?
Although there are a host of intriguing aspects to this question, it has
received much less attention in the research community in comparison to the
intra-community case. In this paper, we examine three aspects of
multi-community engagement: the sequence of communities that users post to, the
language that users employ in those communities, and the feedback that users
receive, using longitudinal posting behavior on Reddit as our main data source,
and DBLP for auxiliary experiments. We also demonstrate the effectiveness of
features drawn from these aspects in predicting users' future level of
activity.
  One might expect that a user's trajectory mimics the "settling-down" process
in real life: an initial exploration of sub-communities before settling down
into a few niches. However, we find that the users in our data continually post
in new communities; moreover, as time goes on, they post increasingly evenly
among a more diverse set of smaller communities. Interestingly, it seems that
users that eventually leave the community are "destined" to do so from the very
beginning, in the sense of showing significantly different "wandering" patterns
very early on in their trajectories; this finding has potentially important
design implications for community maintainers. Our multi-community perspective
also allows us to investigate the "situation vs. personality" debate from
language usage across different communities.
Phase and TV Based Convex Sets for Blind Deconvolution of Microscopic Images
Authors: Mohammad Tofighi, Onur Yorulmaz, A. Enis Cetin
Date: 2015-03-16 00:00:00
Tasks: Image Reconstruction

In this article, two closed and convex sets for blind deconvolution problem
are proposed. Most blurring functions in microscopy are symmetric with respect
to the origin. Therefore, they do not modify the phase of the Fourier transform
(FT) of the original image. As a result blurred image and the original image
have the same FT phase. Therefore, the set of images with a prescribed FT phase
can be used as a constraint set in blind deconvolution problems. Another convex
set that can be used during the image reconstruction process is the epigraph
set of Total Variation (TV) function. This set does not need a prescribed upper
bound on the total variation of the image. The upper bound is automatically
adjusted according to the current image of the restoration process. Both of
these two closed and convex sets can be used as a part of any blind
deconvolution algorithm. Simulation examples are presented.
Skilled Impostor Attacks Against Fingerprint Verification Systems And Its Remedy
Authors: Carsten Gottschlich
Date: 2015-03-16 00:00:00
Tasks: fingerprint verification, Speaker Recognition

Fingerprint verification systems are becoming ubiquitous in everyday life.
This trend is propelled especially by the proliferation of mobile devices with
fingerprint sensors such as smartphones and tablet computers, and fingerprint
verification is increasingly applied for authenticating financial transactions.
In this study we describe a novel attack vector against fingerprint
verification systems which we coin skilled impostor attack. We show that
existing protocols for performance evaluation of fingerprint verification
systems are flawed and as a consequence of this, the system's real
vulnerability is systematically underestimated. We examine a scenario in which
a fingerprint verification system is tuned to operate at false acceptance rate
of 0.1% using the traditional verification protocols with random impostors
(zero-effort attacks). We demonstrate that an active and intelligent attacker
can achieve a chance of success in the area of 89% or more against this system
by performing skilled impostor attacks. We describe a new protocol for
evaluating fingerprint verification performance in order to improve the
assessment of potential and limitations of fingerprint recognition systems.
This new evaluation protocol enables a more informed decision concerning the
operating threshold in practical applications and the respective trade-off
between security (low false acceptance rates) and usability (low false
rejection rates). The skilled impostor attack is a general attack concept which
is independent of specific databases or comparison algorithms. The proposed
protocol relying on skilled impostor attacks can directly be applied for
evaluating the verification performance of other biometric modalities such as
e.g. iris, face, ear, finger vein, gait or speaker recognition.
Deep Feelings: A Massive Cross-Lingual Study on the Relation between Emotions and Virality
Authors: Marco Guerini, Jacopo Staiano
Date: 2015-03-16 00:00:00
Tasks: Articles, Relation

This article provides a comprehensive investigation on the relations between
virality of news articles and the emotions they are found to evoke. Virality,
in our view, is a phenomenon with many facets, i.e. under this generic term
several different effects of persuasive communication are comprised. By
exploiting a high-coverage and bilingual corpus of documents containing metrics
of their spread on social networks as well as a massive affective annotation
provided by readers, we present a thorough analysis of the interplay between
evoked emotions and viral facets. We highlight and discuss our findings in
light of a cross-lingual approach: while we discover differences in evoked
emotions and corresponding viral effects, we provide preliminary evidence of a
generalized explanatory model rooted in the deep structure of emotions: the
Valence-Arousal-Dominance (VAD) circumplex. We find that viral facets appear to
be consistently affected by particular VAD configurations, and these
configurations indicate a clear connection with distinct phenomena underlying
persuasive communication.
A Memcomputing Pascaline
Authors: Y. V. Pershin, L. K. Castelano, F. Hartmann, V. Lopez-Richard, M. Di Ventra
Date: 2015-03-16 00:00:00

The original Pascaline was a mechanical calculator able to sum and subtract
integers. It encodes information in the angles of mechanical wheels and through
a set of gears, and aided by gravity, could perform the calculations. Here, we
show that such a concept can be realized in electronics using memory elements
such as memristive systems. By using memristive emulators we have demonstrated
experimentally the memcomputing version of the mechanical Pascaline, capable of
processing and storing the numerical results in the multiple levels of each
memristive element. Our result is the first experimental demonstration of
multidigit arithmetics with multi-level memory devices that further emphasizes
the versatility and potential of memristive systems for future
massively-parallel high-density computing architectures.
Simple, Accurate, and Robust Nonparametric Blind Super-Resolution
Authors: Wen-Ze Shao, Michael Elad
Date: 2015-03-11 00:00:00
Tasks: Blind Super-Resolution, Super-Resolution

This paper proposes a simple, accurate, and robust approach to single image
nonparametric blind Super-Resolution (SR). This task is formulated as a
functional to be minimized with respect to both an intermediate super-resolved
image and a nonparametric blur-kernel. The proposed approach includes a
convolution consistency constraint which uses a non-blind learning-based SR
result to better guide the estimation process. Another key component is the
unnatural bi-l0-l2-norm regularization imposed on the super-resolved, sharp
image and the blur-kernel, which is shown to be quite beneficial for estimating
the blur-kernel accurately. The numerical optimization is implemented by
coupling the splitting augmented Lagrangian and the conjugate gradient (CG).
Using the pre-estimated blur-kernel, we finally reconstruct the SR image by a
very simple non-blind SR method that uses a natural image prior. The proposed
approach is demonstrated to achieve better performance than the recent method
by Michaeli and Irani [2] in both terms of the kernel estimation accuracy and
image SR quality.
Convex Color Image Segmentation with Optimal Transport Distances
Authors: Julien Rabin, Nicolas Papadakis
Date: 2015-03-06 00:00:00
Tasks: Image Segmentation, Semantic Segmentation

This work is about the use of regularized optimal-transport distances for
convex, histogram-based image segmentation. In the considered framework, fixed
exemplar histograms define a prior on the statistical features of the two
regions in competition. In this paper, we investigate the use of various
transport-based cost functions as discrepancy measures and rely on a
primal-dual algorithm to solve the obtained convex optimization problem.
Inexact Alternating Direction Method Based on Newton descent algorithm with Application to Poisson Image Deblurring
Authors: Dai-Qiang Chen
Date: 2014-12-15 00:00:00
Tasks: Deblurring, Image Deblurring, Image Restoration

The recovery of images from the observations that are degraded by a linear
operator and further corrupted by Poisson noise is an important task in modern
imaging applications such as astronomical and biomedical ones. Gradient-based
regularizers involve the popular total variation semi-norm have become standard
techniques for Poisson image restoration due to its edge-preserving ability.
Various efficient algorithms have been developed for solving the corresponding
minimization problem with non-smooth regularization terms. In this paper,
motivated by the idea of the alternating direction minimization algorithm and
the Newton's method with upper convergent rate, we further propose inexact
alternating direction methods utilizing the proximal Hessian matrix information
of the objective function, in a way reminiscent of Newton descent methods.
Besides, we also investigate the global convergence of the proposed algorithms
under certain conditions. Finally, we illustrate that the proposed algorithms
outperform the current state-of-the-art algorithms through numerical
experiments on Poisson image deblurring.
Simulation of Genetic Algorithm: Traffic Light Efficiency
Authors: Eric Lienert
Date: 2015-03-15 00:00:00
Tasks: Scheduling

Traffic is a problem in many urban areas worldwide. Traffic flow is dictated
by certain devices such as traffic lights. The traffic lights signal when each
lane is able to pass through the intersection. Often, static schedules
interfere with ideal traffic flow. The purpose of this project was to find a
way to make intersections controlled with traffic lights more efficient. This
goal was accomplished through the creation of a genetic algorithm, which
enhances an input algorithm through genetic principles to produce the fittest
algorithm. The program was comprised of two major elements: coding in Java and
coding in Simulation of Urban Mobility (SUMO), which is an environment that
simulates real traffic. The Java code called upon the SUMO simulation via a
command prompt which ran the simulation, received the output, altered the
algorithm, and looped. The SUMO component initialized a simulation in which a 1
x 1 street layout was created, each intersection with its own traffic light.
Each loop enhanced the input algorithm by altering the scheduling string
(dictates the light changes). After the looped simulations were executed, the
data was then analyzed. This was accomplished by creating an algorithm based
upon regular practice, timed traffic lights, and comparing the output which was
comprised of the total time it took for all vehicles to exit the system and the
average time it took each individual vehicle to exit the system. These
different variables: the time it took the average vehicle to exit the system
and total time for all vehicles to exit the system, where then graphed together
to provide a visual aid. The genetic algorithm did improve traffic light and
traffic flow efficiency in comparison to traditional scheduling methods.
apsis - Framework for Automated Optimization of Machine Learning Hyper Parameters
Authors: Frederik Diehl, Andreas Jauch
Date: 2015-03-10 00:00:00
Tasks: BIG-bench Machine Learning, Hyperparameter Optimization

The apsis toolkit presented in this paper provides a flexible framework for
hyperparameter optimization and includes both random search and a bayesian
optimizer. It is implemented in Python and its architecture features
adaptability to any desired machine learning code. It can easily be used with
common Python ML frameworks such as scikit-learn. Published under the MIT
License other researchers are heavily encouraged to check out the code,
contribute or raise any suggestions. The code can be found at
github.com/FrederikDiehl/apsis.
Separable and non-separable data representation for pattern discrimination
Authors: Jarosław Adam Miszczak
Date: 2015-03-15 00:00:00
Tasks: General Classification

We provide a complete work-flow, based on the language of quantum information
theory, suitable for processing data for the purpose of pattern recognition.
The main advantage of the introduced scheme is that it can be easily
implemented and applied to process real-world data using modest computation
resources. At the same time it can be used to investigate the difference in the
pattern recognition resulting from the utilization of the tensor product
structure of the space of quantum states. We illustrate this difference by
providing a simple example based on the classification of 2D data.
The placement of the head that minimizes online memory: a complex systems approach
Authors: Ramon Ferrer-i-Cancho
Date: 2013-09-08 00:00:00

It is well known that the length of a syntactic dependency determines its
online memory cost. Thus, the problem of the placement of a head and its
dependents (complements or modifiers) that minimizes online memory is
equivalent to the problem of the minimum linear arrangement of a star tree.
However, how that length is translated into cognitive cost is not known. This
study shows that the online memory cost is minimized when the head is placed at
the center, regardless of the function that transforms length into cost,
provided only that this function is strictly monotonically increasing. Online
memory defines a quasi-convex adaptive landscape with a single central minimum
if the number of elements is odd and two central minima if that number is even.
We discuss various aspects of the dynamics of word order of subject (S), verb
(V) and object (O) from a complex systems perspective and suggest that word
orders tend to evolve by swapping adjacent constituents from an initial or
early SOV configuration that is attracted towards a central word order by
online memory minimization. We also suggest that the stability of SVO is due to
at least two factors, the quasi-convex shape of the adaptive landscape in the
online memory dimension and online memory adaptations that avoid regression to
SOV. Although OVS is also optimal for placing the verb at the center, its low
frequency is explained by its long distance to the seminal SOV in the
permutation space.
Reply to the commentary "Be careful when assuming the obvious", by P. Alday
Authors: Ramon Ferrer-i-Cancho
Date: 2014-12-22 00:00:00

Here we respond to some comments by Alday concerning headedness in linguistic
theory and the validity of the assumptions of a mathematical model for word
order. For brevity, we focus only on two assumptions: the unit of measurement
of dependency length and the monotonicity of the cost of a dependency as a
function of its length. We also revise the implicit psychological bias in
Alday's comments. Notwithstanding, Alday is indicating the path for linguistic
research with his unusual concerns about parsimony from multiple dimensions.
Calculating Ultra-Strong and Extended Solutions for Nine Men's Morris, Morabaraba, and Lasker
Authors: Gábor E. Gévay, Gábor Danner
Date: 2014-07-31 00:00:00

The strong solutions of Nine Men's Morris and its variant, Lasker Morris are
well-known results (the starting positions are draws). We re-examined both of
these games, and calculated extended strong solutions for them. By this we mean
the game-theoretic values of all possible game states that could be reached
from certain starting positions where the number of stones to be placed by the
players is different from the standard rules. These were also calculated for a
previously unsolved third variant, Morabaraba, with interesting results: most
of the starting positions where the players can place an equal number of stones
(including the standard starting position) are wins for the first player (as
opposed to the above games, where these are usually draws).
  We also developed a multi-valued retrograde analysis, and used it as a basis
for an algorithm for solving these games ultra-strongly. This means that when
our program is playing against a fallible opponent, it has a greater chance of
achieving a better result than the game-theoretic value, compared to randomly
selecting between "just strongly" optimal moves. Previous attempts on
ultra-strong solutions used local heuristics or learning during games, but we
incorporated our algorithm into the retrograde analysis.