pwc-archive/papers-with-abstracts huggingface dataset:
Augmentative Message Passing for Traveling Salesman Problem and Graph Partitioning
Authors: Siamak Ravanbakhsh, Reihaneh Rabbany, Russell Greiner
Date: 2014-06-04 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: graph partitioning, Traveling Salesman Problem

The cutting plane method is an augmentative constrained optimization
procedure that is often used with continuous-domain optimization techniques
such as linear and convex programs. We investigate the viability of a similar
idea within message passing -- which produces integral solutions -- in the
context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP),
we propose a factor-graph based on Held-Karp formulation, with an exponential
number of constraint factors, each of which has an exponential but sparse
tabular form. 2) For graph-partitioning (a.k.a., community mining) using
modularity optimization, we introduce a binary variable model with a large
number of constraints that enforce formation of cliques. In both cases we are
able to derive surprisingly simple message updates that lead to competitive
solutions on benchmark instances. In particular for TSP we are able to find
near-optimal solutions in the time that empirically grows with N^3,
demonstrating that augmentation is practical and efficient.
ACO Implementation for Sequence Alignment with Genetic Algorithms
Authors: Aaron Lee, Livia King
Date: 2014-06-04 00:00:00

In this paper, we implement Ant Colony Optimization (ACO) for sequence
alignment. ACO is a meta-heuristic recently developed for nearest neighbor
approximations in large, NP-hard search spaces. Here we use a genetic algorithm
approach to evolve the best parameters for an ACO designed to align two
sequences. We then used the best parameters found to interpolate approximate
optimal parameters for a given string length within a range. The basis of our
comparison is the alignment given by the Needleman-Wunsch algorithm. We found
that ACO can indeed be applied to sequence alignment. While it is
computationally expensive compared to other equivalent algorithms, it is a
promising algorithm that can be readily applied to a variety of other
biological problems.
Improvement Tracking Dynamic Programming using Replication Function for Continuous Sign Language Recognition
Authors: S. Ildarabadi, M. Ebrahimi, H. R. Pourreza
Date: 2014-06-04 00:00:00
Tasks: Sign Language Recognition

In this paper we used a Replication Function (R. F.)for improvement tracking
with dynamic programming. The R. F. transforms values of gray level [0 255] to
[0 1]. The resulting images of R. F. are more striking and visible in skin
regions. The R. F. improves Dynamic Programming (D. P.) in overlapping hand and
face. Results show that Tracking Error Rate 11% and Average Tracked Distance 7%
reduced
Query Answering over Contextualized RDF/OWL Knowledge with Forall-Existential Bridge Rules: Attaining Decidability using Acyclicity (full version)
Authors: Mathew Joseph, Gabriel Kuper, Luciano Serafini
Date: 2014-06-03 00:00:00

The recent outburst of context-dependent knowledge on the Semantic Web (SW)
has led to the realization of the importance of the quads in the SW community.
Quads, which extend a standard RDF triple, by adding a new parameter of the
`context' of an RDF triple, thus informs a reasoner to distinguish between the
knowledge in various contexts. Although this distinction separates the triples
in an RDF graph into various contexts, and allows the reasoning to be decoupled
across various contexts, bridge rules need to be provided for inter-operating
the knowledge across these contexts. We call a set of quads together with the
bridge rules, a quad-system. In this paper, we discuss the problem of query
answering over quad-systems with expressive forall-existential bridge rules. It
turns out the query answering over quad-systems is undecidable, in general. We
derive a decidable class of quad-systems, namely context-acyclic quad-systems,
for which query answering can be done using forward chaining. Tight bounds for
data and combined complexity of query entailment has been established for the
derived class.
Supervised classification-based stock prediction and portfolio optimization
Authors: Sercan Arik, Sukru Burc Eryilmaz, Adam Goldberg
Date: 2014-06-03 00:00:00
Tasks: Classification, General Classification, Portfolio Optimization, Prediction, Stock Prediction, Time Series, Time Series Analysis

As the number of publicly traded companies as well as the amount of their
financial data grows rapidly, it is highly desired to have tracking, analysis,
and eventually stock selections automated. There have been few works focusing
on estimating the stock prices of individual companies. However, many of those
have worked with very small number of financial parameters. In this work, we
apply machine learning techniques to address automated stock picking, while
using a larger number of financial parameters for individual companies than the
previous studies. Our approaches are based on the supervision of prediction
parameters using company fundamentals, time-series properties, and correlation
information between different stocks. We examine a variety of supervised
learning techniques and found that using stock fundamentals is a useful
approach for the classification problem, when combined with the high
dimensional data handling capabilities of support vector machine. The portfolio
our system suggests by predicting the behavior of stocks results in a 3% larger
growth on average than the overall market within a 3-month time period, as the
out-of-sample test suggests.
Learning Latent Block Structure in Weighted Networks
Authors: Christopher Aicher, Abigail Z. Jacobs, Aaron Clauset
Date: 2014-04-02 00:00:00
Tasks: Community Detection, Stochastic Block Model

Community detection is an important task in network analysis, in which we aim
to learn a network partition that groups together vertices with similar
community-level connectivity patterns. By finding such groups of vertices with
similar structural roles, we extract a compact representation of the network's
large-scale structure, which can facilitate its scientific interpretation and
the prediction of unknown or future interactions. Popular approaches, including
the stochastic block model, assume edges are unweighted, which limits their
utility by throwing away potentially useful information. We introduce the
`weighted stochastic block model' (WSBM), which generalizes the stochastic
block model to networks with edge weights drawn from any exponential family
distribution. This model learns from both the presence and weight of edges,
allowing it to discover structure that would otherwise be hidden when weights
are discarded or thresholded. We describe a Bayesian variational algorithm for
efficiently approximating this model's posterior distribution over latent block
structures. We then evaluate the WSBM's performance on both edge-existence and
edge-weight prediction tasks for a set of real-world weighted networks. In all
cases, the WSBM performs as well or better than the best alternatives on these
tasks.
The Design of the Fifth Answer Set Programming Competition
Authors: Francesco Calimeri, Martin Gebser, Marco Maratea, Francesco Ricca
Date: 2014-05-14 00:00:00
Tasks: Scheduling

Answer Set Programming (ASP) is a well-established paradigm of declarative
programming that has been developed in the field of logic programming and
nonmonotonic reasoning. Advances in ASP solving technology are customarily
assessed in competition events, as it happens for other closely-related
problem-solving technologies like SAT/SMT, QBF, Planning and Scheduling. ASP
Competitions are (usually) biennial events; however, the Fifth ASP Competition
departs from tradition, in order to join the FLoC Olympic Games at the Vienna
Summer of Logic 2014, which is expected to be the largest event in the history
of logic. This edition of the ASP Competition series is jointly organized by
the University of Calabria (Italy), the Aalto University (Finland), and the
University of Genova (Italy), and is affiliated with the 30th International
Conference on Logic Programming (ICLP 2014). It features a completely
re-designed setup, with novelties involving the design of tracks, the scoring
schema, and the adherence to a fixed modeling language in order to push the
adoption of the ASP-Core-2 standard. Benchmark domains are taken from past
editions, and best system packages submitted in 2013 are compared with new
versions and solvers.
  To appear in Theory and Practice of Logic Programming (TPLP).
Changing the Environment Based on Empowerment as Intrinsic Motivation
Authors: Christoph Salge, Cornelius Glackin, Daniel Polani
Date: 2014-06-03 00:00:00
Tasks: Decision Making, Minecraft

One aspect of intelligence is the ability to restructure your own environment
so that the world you live in becomes more beneficial to you. In this paper we
investigate how the information-theoretic measure of agent empowerment can
provide a task-independent, intrinsic motivation to restructure the world. We
show how changes in embodiment and in the environment change the resulting
behaviour of the agent and the artefacts left in the world. For this purpose,
we introduce an approximation of the established empowerment formalism based on
sparse sampling, which is simpler and significantly faster to compute for
deterministic dynamics. Sparse sampling also introduces a degree of randomness
into the decision making process, which turns out to beneficial for some cases.
We then utilize the measure to generate agent behaviour for different agent
embodiments in a Minecraft-inspired three dimensional block world. The
paradigmatic results demonstrate that empowerment can be used as a suitable
generic intrinsic motivation to not only generate actions in given static
environments, as shown in the past, but also to modify existing environmental
conditions. In doing so, the emerging strategies to modify an agent's
environment turn out to be meaningful to the specific agent capabilities, i.e.,
de facto to its embodiment.
Visual Reranking with Improved Image Graph
Authors: Ziqiong Liu, Shengjin Wang, Liang Zheng, Qi Tian
Date: 2014-06-03 00:00:00
Tasks: Image Retrieval, Reranking

This paper introduces an improved reranking method for the Bag-of-Words (BoW)
based image search. Built on [1], a directed image graph robust to outlier
distraction is proposed. In our approach, the relevance among images is encoded
in the image graph, based on which the initial rank list is refined. Moreover,
we show that the rank-level feature fusion can be adopted in this reranking
method as well. Taking advantage of the complementary nature of various
features, the reranking performance is further enhanced. Particularly, we
exploit the reranking method combining the BoW and color information.
Experiments on two benchmark datasets demonstrate that ourmethod yields
significant improvements and the reranking results are competitive to the
state-of-the-art methods.
An Ordered Lasso and Sparse Time-Lagged Regression
Authors: Xiaotong Suo, Robert Tibshirani
Date: 2014-05-26 00:00:00
Tasks: regression, Time Series, Time Series Analysis

We consider regression scenarios where it is natural to impose an order
constraint on the coefficients. We propose an order-constrained version of
L1-regularized regression for this problem, and show how to solve it
efficiently using the well-known Pool Adjacent Violators Algorithm as its
proximal operator. The main application of this idea is time-lagged regression,
where we predict an outcome at time t from features at the previous K time
points. In this setting it is natural to assume that the coefficients decay as
we move farther away from t, and hence the order constraint is reasonable.
Potential applications include financial time series and prediction of dynamic
patient out- comes based on clinical measurements. We illustrate this idea on
real and simulated data.
Experimental Demonstration of Array-level Learning with Phase Change Synaptic Devices
Authors: S. Burc Eryilmaz, Duygu Kuzum, Rakesh G. D. Jeyasingh, Sang-Bum Kim, Matthew BrightSky, Chung Lam, H. -S. Philip Wong
Date: 2014-05-29 00:00:00

The computational performance of the biological brain has long attracted
significant interest and has led to inspirations in operating principles,
algorithms, and architectures for computing and signal processing. In this
work, we focus on hardware implementation of brain-like learning in a
brain-inspired architecture. We demonstrate, in hardware, that 2-D crossbar
arrays of phase change synaptic devices can achieve associative learning and
perform pattern recognition. Device and array-level studies using an
experimental 10x10 array of phase change synaptic devices have shown that
pattern recognition is robust against synaptic resistance variations and large
variations can be tolerated by increasing the number of training iterations.
Our measurements show that increase in initial variation from 9 % to 60 %
causes required training iterations to increase from 1 to 11.
Provable Deterministic Leverage Score Sampling
Authors: Dimitris Papailiopoulos, Anastasios Kyrillidis, Christos Boutsidis
Date: 2014-04-06 00:00:00

We explain theoretically a curious empirical phenomenon: "Approximating a
matrix by deterministically selecting a subset of its columns with the
corresponding largest leverage scores results in a good low-rank matrix
surrogate". To obtain provable guarantees, previous work requires randomized
sampling of the columns with probabilities proportional to their leverage
scores.
  In this work, we provide a novel theoretical analysis of deterministic
leverage score sampling. We show that such deterministic sampling can be
provably as accurate as its randomized counterparts, if the leverage scores
follow a moderately steep power-law decay. We support this power-law assumption
by providing empirical evidence that such decay laws are abundant in real-world
data sets. We then demonstrate empirically the performance of deterministic
leverage score sampling, which many times matches or outperforms the
state-of-the-art techniques.
Universal Convexification via Risk-Aversion
Authors: Krishnamurthy Dvijotham, Maryam Fazel, Emanuel Todorov
Date: 2014-06-03 00:00:00
Tasks: Stochastic Optimization

We develop a framework for convexifying a fairly general class of
optimization problems. Under additional assumptions, we analyze the
suboptimality of the solution to the convexified problem relative to the
original nonconvex problem and prove additive approximation guarantees. We then
develop algorithms based on stochastic gradient methods to solve the resulting
optimization problems and show bounds on convergence rates. %We show a simple
application of this framework to supervised learning, where one can perform
integration explicitly and can use standard (non-stochastic) optimization
algorithms with better convergence guarantees. We then extend this framework to
apply to a general class of discrete-time dynamical systems. In this context,
our convexification approach falls under the well-studied paradigm of
risk-sensitive Markov Decision Processes. We derive the first known model-based
and model-free policy gradient optimization algorithms with guaranteed
convergence to the optimal solution. Finally, we present numerical results
validating our formulation in different applications.
Neutrosophic soft sets with applications in decision making
Authors: Faruk Karaaslan
Date: 2014-05-30 00:00:00
Tasks: Decision Making

We firstly present definitions and properties in study of Maji
\cite{maji-2013} on neutrosophic soft sets. We then give a few notes on his
study. Next, based on \c{C}a\u{g}man \cite{cagman-2014}, we redefine the notion
of neutrosophic soft set and neutrosophic soft set operations to make more
functional. By using these new definitions we construct a decision making
method and a group decision making method which selects a set of optimum
elements from the alternatives. We finally present examples which shows that
the methods can be successfully applied to many problems that contain
uncertainties.
More Bang For Your Buck: Quorum-Sensing Capabilities Improve the Efficacy of Suicidal Altruism
Authors: Anya Elaine Johnson, Eli Strauss, Rodney Pickett, Christoph Adami, Ian Dworkin, Heather J. Goldsby
Date: 2014-06-02 00:00:00

Within the context of evolution, an altruistic act that benefits the
receiving individual at the expense of the acting individual is a puzzling
phenomenon. An extreme form of altruism can be found in colicinogenic E. coli.
These suicidal altruists explode, releasing colicins that kill unrelated
individuals, which are not colicin resistant. By committing suicide, the
altruist makes it more likely that its kin will have less competition. The
benefits of this strategy rely on the number of competitors and kin nearby. If
the organism explodes at an inopportune time, the suicidal act may not harm any
competitors. Communication could enable organisms to act altruistically when
environmental conditions suggest that that strategy would be most beneficial.
Quorum sensing is a form of communication in which bacteria produce a protein
and gauge the amount of that protein around them. Quorum sensing is one means
by which bacteria sense the biotic factors around them and determine when to
produce products, such as antibiotics, that influence competition. Suicidal
altruists could use quorum sensing to determine when exploding is most
beneficial, but it is challenging to study the selective forces at work in
microbes. To address these challenges, we use digital evolution (a form of
experimental evolution that uses self-replicating computer programs as
organisms) to investigate the effects of enabling altruistic organisms to
communicate via quorum sensing. We found that quorum-sensing altruists killed a
greater number of competitors per explosion, winning competitions against
non-communicative altruists. These findings indicate that quorum sensing could
increase the beneficial effect of altruism and the suite of conditions under
which it will evolve.
Linear Algorithm for Digital Euclidean Connected Skeleton
Authors: Aurélie Leborgne, Julien Mille, Laure Tougne
Date: 2013-10-09 00:00:00

The skeleton is an essential shape characteristic providing a compact
representation of the studied shape. Its computation on the image grid raises
many issues. Due to the effects of discretization, the required properties of
the skeleton - thinness, homotopy to the shape, reversibility, connectivity -
may become incompatible. However, as regards practical use, the choice of a
specific skeletonization algorithm depends on the application. This allows to
classify the desired properties by order of importance, and tend towards the
most critical ones. Our goal is to make a skeleton dedicated to shape matching
for recognition. So, the discrete skeleton has to be thin - so that it can be
represented by a graph -, robust to noise, reversible - so that the initial
shape can be fully reconstructed - and homotopic to the shape. We propose a
linear-time skeletonization algorithm based on the squared Euclidean distance
map from which we extract the maximal balls and ridges. After a thinning and
pruning process, we obtain the skeleton. The proposed method is finally
compared to fairly recent methods.
An Algebraic Hardness Criterion for Surjective Constraint Satisfaction
Authors: Hubie Chen
Date: 2014-05-19 00:00:00

The constraint satisfaction problem (CSP) on a relational structure B is to
decide, given a set of constraints on variables where the relations come from
B, whether or not there is a assignment to the variables satisfying all of the
constraints; the surjective CSP is the variant where one decides the existence
of a surjective satisfying assignment onto the universe of B. We present an
algebraic condition on the polymorphism clone of B and prove that it is
sufficient for the hardness of the surjective CSP on a finite structure B, in
the sense that this problem admits a reduction from a certain fixed-structure
CSP. To our knowledge, this is the first result that allows one to use
algebraic information from a relational structure B to infer information on the
complexity hardness of surjective constraint satisfaction on B. A corollary of
our result is that, on any finite non-trivial structure having only essentially
unary polymorphisms, surjective constraint satisfaction is NP-complete.
Generalized Max Pooling
Authors: Naila Murray, Florent Perronnin
Date: 2014-06-02 00:00:00
Proceeding: CVPR 2014 6
Tasks: image-classification, Image Classification

State-of-the-art patch-based image representations involve a pooling
operation that aggregates statistics computed from local descriptors. Standard
pooling operations include sum- and max-pooling. Sum-pooling lacks
discriminability because the resulting representation is strongly influenced by
frequent yet often uninformative descriptors, but only weakly influenced by
rare yet potentially highly-informative ones. Max-pooling equalizes the
influence of frequent and rare descriptors but is only applicable to
representations that rely on count statistics, such as the bag-of-visual-words
(BOV) and its soft- and sparse-coding extensions. We propose a novel pooling
mechanism that achieves the same effect as max-pooling but is applicable beyond
the BOV and especially to the state-of-the-art Fisher Vector -- hence the name
Generalized Max Pooling (GMP). It involves equalizing the similarity between
each patch and the pooled representation, which is shown to be equivalent to
re-weighting the per-patch statistics. We show on five public image
classification benchmarks that the proposed GMP can lead to significant
performance gains with respect to heuristic alternatives.
Transductive Learning for Multi-Task Copula Processes
Authors: Markus Schneider, Fabio Ramos
Date: 2014-06-02 00:00:00
Tasks: Gaussian Processes, Multi-Task Learning, Prediction, Transductive Learning

We tackle the problem of multi-task learning with copula process.
Multivariable prediction in spatial and spatial-temporal processes such as
natural resource estimation and pollution monitoring have been typically
addressed using techniques based on Gaussian processes and co-Kriging. While
the Gaussian prior assumption is convenient from analytical and computational
perspectives, nature is dominated by non-Gaussian likelihoods. Copula processes
are an elegant and flexible solution to handle various non-Gaussian likelihoods
by capturing the dependence structure of random variables with cumulative
distribution functions rather than their marginals. We show how multi-task
learning for copula processes can be used to improve multivariable prediction
for problems where the simple Gaussianity prior assumption does not hold. Then,
we present a transductive approximation for multi-task learning and derive
analytical expressions for the copula process model. The approach is evaluated
and compared to other techniques in one artificial dataset and two publicly
available datasets for natural resource estimation and concrete slump
prediction.
The constitution of visual perceptual units in the functional architecture of V1
Authors: Alessandro Sarti, Giovanna Citti
Date: 2014-06-02 00:00:00
Tasks: Clustering, Dimensionality Reduction, Hallucination

Scope of this paper is to consider a mean field neural model which takes into
account the functional neurogeometry of the visual cortex modelled as a group
of rotations and translations. The model generalizes well known results of
Bressloff and Cowan which, in absence of input, accounts for hallucination
patterns. The main result of our study consists in showing that in presence of
a visual input, the eigenmodes of the linearized operator which become stable
represent perceptual units present in the image. The result is strictly related
to dimensionality reduction and clustering problems.