pwc-archive/papers-with-abstracts huggingface dataset:
Forming A Random Field via Stochastic Cliques: From Random Graphs to Fully Connected Random Fields
Authors: Mohammad Javad Shafiee, Alexander Wong, Paul Fieguth
Date: 2015-06-30 00:00:00
Tasks: Image Segmentation, Semantic Segmentation

Random fields have remained a topic of great interest over past decades for
the purpose of structured inference, especially for problems such as image
segmentation. The local nodal interactions commonly used in such models often
suffer the short-boundary bias problem, which are tackled primarily through the
incorporation of long-range nodal interactions. However, the issue of
computational tractability becomes a significant issue when incorporating such
long-range nodal interactions, particularly when a large number of long-range
nodal interactions (e.g., fully-connected random fields) are modeled.
  In this work, we introduce a generalized random field framework based around
the concept of stochastic cliques, which addresses the issue of computational
tractability when using fully-connected random fields by stochastically forming
a sparse representation of the random field. The proposed framework allows for
efficient structured inference using fully-connected random fields without any
restrictions on the potential functions that can be utilized. Several
realizations of the proposed framework using graph cuts are presented and
evaluated, and experimental results demonstrate that the proposed framework can
provide competitive performance for the purpose of image segmentation when
compared to existing fully-connected and principled deep random field
frameworks.
Divide-and-Conquer with Sequential Monte Carlo
Authors: Fredrik Lindsten, Adam M. Johansen, Christian A. Naesseth, Bonnie Kirkpatrick, Thomas B. Schön, John Aston, Alexandre Bouchard-Côté
Date: 2014-06-19 00:00:00

We propose a novel class of Sequential Monte Carlo (SMC) algorithms,
appropriate for inference in probabilistic graphical models. This class of
algorithms adopts a divide-and-conquer approach based upon an auxiliary
tree-structured decomposition of the model of interest, turning the overall
inferential task into a collection of recursively solved sub-problems. The
proposed method is applicable to a broad class of probabilistic graphical
models, including models with loops. Unlike a standard SMC sampler, the
proposed Divide-and-Conquer SMC employs multiple independent populations of
weighted particles, which are resampled, merged, and propagated as the method
progresses. We illustrate empirically that this approach can outperform
standard methods in terms of the accuracy of the posterior expectation and
marginal likelihood approximations. Divide-and-Conquer SMC also opens up novel
parallel implementation options and the possibility of concentrating the
computational effort on the most challenging sub-problems. We demonstrate its
performance on a Markov random field and on a hierarchical logistic regression
problem.
Artificial Catalytic Reactions in 2D for Combinatorial Optimization
Authors: Jaderick P. Pabico
Date: 2015-06-30 00:00:00
Tasks: Combinatorial Optimization

Presented in this paper is a derivation of a 2D catalytic reaction-based
model to solve combinatorial optimization problems (COPs). The simulated
catalytic reactions, a computational metaphor, occurs in an artificial chemical
reactor that finds near-optimal solutions to COPs. The artificial environment
is governed by catalytic reactions that can alter the structure of artificial
molecular elements. Altering the molecular structure means finding new
solutions to the COP. The molecular mass of the elements was considered as a
measure of goodness of fit of the solutions. Several data structures and
matrices were used to record the directions and locations of the molecules.
These provided the model the 2D topology. The Traveling Salesperson Problem
(TSP) was used as a working example. The performance of the model in finding a
solution for the TSP was compared to the performance of a topology-less model.
Experimental results show that the 2D model performs better than the
topology-less one.
Fast ADMM Algorithm for Distributed Optimization with Adaptive Penalty
Authors: Changkyu Song, Sejong Yoon, Vladimir Pavlovic
Date: 2015-06-30 00:00:00
Tasks: Distributed Optimization

We propose new methods to speed up convergence of the Alternating Direction
Method of Multipliers (ADMM), a common optimization tool in the context of
large scale and distributed learning. The proposed method accelerates the speed
of convergence by automatically deciding the constraint penalty needed for
parameter consensus in each iteration. In addition, we also propose an
extension of the method that adaptively determines the maximum number of
iterations to update the penalty. We show that this approach effectively leads
to an adaptive, dynamic network topology underlying the distributed
optimization. The utility of the new penalty update schemes is demonstrated on
both synthetic and real data, including a computer vision application of
distributed structure from motion.
Characterization of Logic Program Revision as an Extension of Propositional Revision
Authors: Nicolas Schwind, Katsumi Inoue
Date: 2015-06-30 00:00:00

We address the problem of belief revision of logic programs, i.e., how to
incorporate to a logic program P a new logic program Q. Based on the structure
of SE interpretations, Delgrande et al. adapted the well-known AGM framework to
logic program (LP) revision. They identified the rational behavior of LP
revision and introduced some specific operators. In this paper, a constructive
characterization of all rational LP revision operators is given in terms of
orderings over propositional interpretations with some further conditions
specific to SE interpretations. It provides an intuitive, complete procedure
for the construction of all rational LP revision operators and makes easier the
comprehension of their semantic and computational properties. We give a
particular consideration to logic programs of very general form, i.e., the
generalized logic programs (GLPs). We show that every rational GLP revision
operator is derived from a propositional revision operator satisfying the
original AGM postulates. Interestingly, the further conditions specific to GLP
revision are independent from the propositional revision operator on which a
GLP revision operator is based. Taking advantage of our characterization
result, we embed the GLP revision operators into structures of Boolean
lattices, that allow us to bring to light some potential weaknesses in the
adapted AGM postulates. To illustrate our claim, we introduce and characterize
axiomatically two specific classes of (rational) GLP revision operators which
arguably have a drastic behavior. We additionally consider two more restricted
forms of logic programs, i.e., the disjunctive logic programs (DLPs) and the
normal logic programs (NLPs) and adapt our characterization result to DLP and
NLP revision operators.
Learning Single Index Models in High Dimensions
Authors: Ravi Ganti, Nikhil Rao, Rebecca M. Willett, Robert Nowak
Date: 2015-06-30 00:00:00
Tasks: General Classification, Vocal Bursts Intensity Prediction

Single Index Models (SIMs) are simple yet flexible semi-parametric models for
classification and regression. Response variables are modeled as a nonlinear,
monotonic function of a linear combination of features. Estimation in this
context requires learning both the feature weights, and the nonlinear function.
While methods have been described to learn SIMs in the low dimensional regime,
a method that can efficiently learn SIMs in high dimensions has not been
forthcoming. We propose three variants of a computationally and statistically
efficient algorithm for SIM inference in high dimensions. We establish excess
risk bounds for the proposed algorithms and experimentally validate the
advantages that our SIM learning methods provide relative to Generalized Linear
Model (GLM) and low dimensional SIM based learning methods.
An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
Authors: Paul Kirchner, Pierre-Alain Fouque
Date: 2015-06-08 00:00:00
Tasks: Quantization

In this paper, we study the Learning With Errors problem and its binary
variant, where secrets and errors are binary or taken in a small interval. We
introduce a new variant of the Blum, Kalai and Wasserman algorithm, relying on
a quantization step that generalizes and fine-tunes modulus switching. In
general this new technique yields a significant gain in the constant in front
of the exponent in the overall complexity. We illustrate this by solving p
within half a day a LWE instance with dimension n = 128, modulus $q = n^2$,
Gaussian noise $\alpha = 1/(\sqrt{n/\pi} \log^2 n)$ and binary secret, using
$2^{28}$ samples, while the previous best result based on BKW claims a time
complexity of $2^{74}$ with $2^{60}$ samples for the same parameters. We then
introduce variants of BDD, GapSVP and UniqueSVP, where the target point is
required to lie in the fundamental parallelepiped, and show how the previous
algorithm is able to solve these variants in subexponential time. Moreover, we
also show how the previous algorithm can be used to solve the BinaryLWE problem
with n samples in subexponential time $2^{(\ln 2/2+o(1))n/\log \log n}$. This
analysis does not require any heuristic assumption, contrary to other algebraic
approaches; instead, it uses a variant of an idea by Lyubashevsky to generate
many samples from a small number of samples. This makes it possible to
asymptotically and heuristically break the NTRU cryptosystem in subexponential
time (without contradicting its security assumption). We are also able to solve
subset sum problems in subexponential time for density $o(1)$, which is of
independent interest: for such density, the previous best algorithm requires
exponential time. As a direct application, we can solve in subexponential time
the parameters of a cryptosystem based on this problem proposed at TCC 2010.
Machine learning for many-body physics: efficient solution of dynamical mean-field theory
Authors: Louis-François Arsenault, O. Anatole von Lilienfeld, Andrew J. Millis
Date: 2015-06-29 00:00:00
Tasks: BIG-bench Machine Learning

Machine learning methods for solving the equations of dynamical mean-field
theory are developed. The method is demonstrated on the three dimensional
Hubbard model. The key technical issues are defining a mapping of an input
function to an output function, and distinguishing metallic from insulating
solutions. Both metallic and Mott insulator solutions can be predicted. The
validity of the machine learning scheme is assessed by comparing predictions of
full correlation functions, of quasi-particle weight and particle density to
values directly computed. The results indicate that with modest further
development, machine learning approach may be an attractive computational
efficient option for real materials predictions for strongly correlated
systems.
Requirement Tracing using Term Extraction
Authors: Najla Al-Saati, Raghda Abdul-Jaleel
Date: 2015-06-29 00:00:00
Tasks: Term Extraction

Requirements traceability is an essential step in ensuring the quality of
software during the early stages of its development life cycle. Requirements
tracing usually consists of document parsing, candidate link generation and
evaluation and traceability analysis. This paper demonstrates the applicability
of Statistical Term Extraction metrics to generate candidate links. It is
applied and validated using two data sets and four types of filters two for
each data set, 0.2 and 0.25 for MODIS, 0 and 0.05 for CM1. This method
generates requirements traceability matrices between textual requirements
artifacts (such as high-level requirements traced to low-level requirements).
The proposed method includes ten word frequency metrics divided into three main
groups for calculating the frequency of terms. The results show that the
proposed method gives better result when compared with the traditional TF-IDF
method.
Spectral Motion Synchronization in SE(3)
Authors: Federica Arrigoni, Andrea Fusiello, Beatrice Rossi
Date: 2015-06-29 00:00:00
Tasks: Form, Translation

This paper addresses the problem of motion synchronization (or averaging) and
describes a simple, closed-form solution based on a spectral decomposition,
which does not consider rotation and translation separately but works straight
in SE(3), the manifold of rigid motions. Besides its theoretical interest,
being the first closed form solution in SE(3), experimental results show that
it compares favourably with the state of the art both in terms of precision and
speed.
S2: An Efficient Graph Based Active Learning Algorithm with Application to Nonparametric Classification
Authors: Gautam Dasarathy, Robert Nowak, Xiaojin Zhu
Date: 2015-06-29 00:00:00
Tasks: Active Learning, General Classification

This paper investigates the problem of active learning for binary label
prediction on a graph. We introduce a simple and label-efficient algorithm
called S2 for this task. At each step, S2 selects the vertex to be labeled
based on the structure of the graph and all previously gathered labels.
Specifically, S2 queries for the label of the vertex that bisects the *shortest
shortest* path between any pair of oppositely labeled vertices. We present a
theoretical estimate of the number of queries S2 needs in terms of a novel
parametrization of the complexity of binary functions on graphs. We also
present experimental results demonstrating the performance of S2 on both real
and synthetic data. While other graph-based active learning algorithms have
shown promise in practice, our algorithm is the first with both good
performance and theoretical guarantees. Finally, we demonstrate the
implications of the S2 algorithm to the theory of nonparametric active
learning. In particular, we show that S2 achieves near minimax optimal excess
risk for an important class of nonparametric classification problems.
An automatic and efficient foreground object extraction scheme
Authors: Subhajit Adhikari, Joydeep Kar, Jayati Ghosh Dastidar
Date: 2015-06-29 00:00:00
Tasks: Object

This paper presents a method to differentiate the foreground objects from the
background of a color image. Firstly a color image of any size is input for
processing. The algorithm converts it to a grayscale image. Next we apply canny
edge detector to find the boundary of the foreground object. We concentrate to
find the maximum distance between each boundary pixel column wise and row wise
and we fill the region that is bound by the edges. Thus we are able to extract
the grayscale values of pixels that are in the bounded region and convert the
grayscale image back to original color image containing only the foreground
object.
Tracking Direction of Human Movement - An Efficient Implementation using Skeleton
Authors: Merina Kundu, Dhriti Sengupta, Jayati Ghosh Dastidar
Date: 2015-06-29 00:00:00

Sometimes a simple and fast algorithm is required to detect human presence
and movement with a low error rate in a controlled environment for security
purposes. Here a light weight algorithm has been presented that generates alert
on detection of human presence and its movement towards a certain direction.
The algorithm uses fixed angle CCTV camera images taken over time and relies
upon skeleton transformation of successive images and calculation of difference
in their coordinates.
Portfolio optimization using local linear regression ensembles in RapidMiner
Authors: Gabor Nagy, Gergo Barta, Tamas Henk
Date: 2015-06-29 00:00:00
Tasks: Portfolio Optimization, regression

In this paper we implement a Local Linear Regression Ensemble Committee
(LOLREC) to predict 1-day-ahead returns of 453 assets form the S&P500. The
estimates and the historical returns of the committees are used to compute the
weights of the portfolio from the 453 stock. The proposed method outperforms
benchmark portfolio selection strategies that optimize the growth rate of the
capital. We investigate the effect of algorithm parameter m: the number of
selected stocks on achieved average annual yields. Results suggest the
algorithm's practical usefulness in everyday trading.
Human Shape Variation - An Efficient Implementation using Skeleton
Authors: Dhriti Sengupta, Merina Kundu, Jayati Ghosh Dastidar
Date: 2015-06-29 00:00:00
Tasks: Object

It is at times important to detect human presence automatically in secure
environments. This needs a shape recognition algorithm that is robust, fast and
has low error rates. The algorithm needs to process camera images quickly to
detect any human in the range of vision, and generate alerts, especially if the
object under scrutiny is moving in certain directions. We present here a
simple, efficient and fast algorithm using skeletons of the images, and simple
features like posture and length of the object.
Automatic Channel Network Extraction from Remotely Sensed Images by Singularity Analysis
Authors: F. Isikdogan, A. C. Bovik, P. Passalacqua
Date: 2015-06-29 00:00:00
Tasks: General Classification

Quantitative analysis of channel networks plays an important role in river
studies. To provide a quantitative representation of channel networks, we
propose a new method that extracts channels from remotely sensed images and
estimates their widths. Our fully automated method is based on a recently
proposed Multiscale Singularity Index that responds strongly to curvilinear
structures but weakly to edges. The algorithm produces a channel map, using a
single image where water and non-water pixels have contrast, such as a Landsat
near-infrared band image or a water index defined on multiple bands. The
proposed method provides a robust alternative to the procedures that are used
in remote sensing of fluvial geomorphology and makes classification and
analysis of channel networks easier. The source code of the algorithm is
available at: http://live.ece.utexas.edu/research/cne/.
A review of landmark articles in the field of co-evolutionary computing
Authors: Noe Casas
Date: 2015-06-10 00:00:00
Tasks: Articles, Evolutionary Algorithms

Coevolution is a powerful tool in evolutionary computing that mitigates some
of its endemic problems, namely stagnation in local optima and lack of
convergence in high dimensionality problems. Since its inception in 1990, there
are multiple articles that have contributed greatly to the development and
improvement of the coevolutionary techniques. In this report we review some of
those landmark articles dwelving in the techniques they propose and how they
fit to conform robust evolutionary algorithms
Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
Authors: Junpei Komiyama, Junya Honda, Hisashi Kashima, Hiroshi Nakagawa
Date: 2015-06-08 00:00:00

We study the $K$-armed dueling bandit problem, a variation of the standard
stochastic bandit problem where the feedback is limited to relative comparisons
of a pair of arms. We introduce a tight asymptotic regret lower bound that is
based on the information divergence. An algorithm that is inspired by the
Deterministic Minimum Empirical Divergence algorithm (Honda and Takemura, 2010)
is proposed, and its regret is analyzed. The proposed algorithm is found to be
the first one with a regret upper bound that matches the lower bound.
Experimental comparisons of dueling bandit algorithms show that the proposed
algorithm significantly outperforms existing ones.
Is Intelligence Artificial?
Authors: Kieran Greer
Date: 2014-03-05 00:00:00

Our understanding of intelligence is directed primarily at the human level. This paper attempts to give a more unifying definition that can be applied to the natural world in general and then Artificial Intelligence. The definition would be used more to qualify than quantify it and might help when making judgements on the matter. While correct behaviour is the preferred definition, a metric that is grounded in Kolmogorov's Complexity Theory is suggested, which leads to a measurement about entropy. A version of an accepted AI test is then put forward as the 'acid test' and might be what a free-thinking program would try to achieve. Recent work by the author has been more from a direction of mechanical processes, or ones that might operate automatically. This paper agrees that intelligence is a pro-active event, but also notes a second aspect to it that is in the background and mechanical. The paper suggests looking at intelligence and the conscious as being slightly different, where the conscious is this more mechanical aspect. In fact, a surprising conclusion can be a passive but intelligent brain being invoked by active and less intelligent senses.
Variational Inference for Background Subtraction in Infrared Imagery
Authors: Konstantinos Makantasis, Anastasios Doulamis, Nikolaos Doulamis
Date: 2015-06-29 00:00:00
Tasks: Variational Inference

We propose a Gaussian mixture model for background subtraction in infrared
imagery. Following a Bayesian approach, our method automatically estimates the
number of Gaussian components as well as their parameters, while simultaneously
it avoids over/under fitting. The equations for estimating model parameters are
analytically derived and thus our method does not require any sampling
algorithm that is computationally and memory inefficient. The pixel density
estimate is followed by an efficient and highly accurate updating mechanism,
which permits our system to be automatically adapted to dynamically changing
operation conditions. Experimental results and comparisons with other methods
show that our method outperforms, in terms of precision and recall, while at
the same time it keeps computational cost suitable for real-time applications.
Tell and Predict: Kernel Classifier Prediction for Unseen Visual Classes from Unstructured Text Descriptions
Authors: Mohamed Elhoseiny, Ahmed Elgammal, Babak Saleh
Date: 2015-06-29 00:00:00
Tasks: Zero-Shot Learning

In this paper we propose a framework for predicting kernelized classifiers in
the visual domain for categories with no training images where the knowledge
comes from textual description about these categories. Through our optimization
framework, the proposed approach is capable of embedding the class-level
knowledge from the text domain as kernel classifiers in the visual domain. We
also proposed a distributional semantic kernel between text descriptions which
is shown to be effective in our setting. The proposed framework is not
restricted to textual descriptions, and can also be applied to other forms
knowledge representations. Our approach was applied for the challenging task of
zero-shot learning of fine-grained categories from text descriptions of these
categories.