pwc-archive/papers-with-abstracts huggingface dataset:
On Proportions of Fit Individuals in Population of Evolutionary Algorithm with Tournament Selection
Authors: Anton Eremeev
Date: 2015-07-29 00:00:00

In this paper, we consider a fitness-level model of a non-elitist
mutation-only evolutionary algorithm (EA) with tournament selection. The model
provides upper and lower bounds for the expected proportion of the individuals
with fitness above given thresholds. In the case of so-called monotone
mutation, the obtained bounds imply that increasing the tournament size
improves the EA performance. As corollaries, we obtain an exponentially
vanishing tail bound for the Randomized Local Search on unimodal functions and
polynomial upper bounds on the runtime of EAs on 2-SAT problem and on a family
of Set Cover problems proposed by E. Balas.
A Meta-Analysis of the Anomaly Detection Problem
Authors: Andrew Emmott, Shubhomoy Das, Thomas Dietterich, Alan Fern, Weng-Keen Wong
Date: 2015-03-03 00:00:00
Tasks: Anomaly Detection, Benchmarking, Experimental Design, Two-sample testing

This article provides a thorough meta-analysis of the anomaly detection
problem. To accomplish this we first identify approaches to benchmarking
anomaly detection algorithms across the literature and produce a large corpus
of anomaly detection benchmarks that vary in their construction across several
dimensions we deem important to real-world applications: (a) point difficulty,
(b) relative frequency of anomalies, (c) clusteredness of anomalies, and (d)
relevance of features. We apply a representative set of anomaly detection
algorithms to this corpus, yielding a very large collection of experimental
results. We analyze these results to understand many phenomena observed in
previous work. First we observe the effects of experimental design on
experimental results. Second, results are evaluated with two metrics, ROC Area
Under the Curve and Average Precision. We employ statistical hypothesis testing
to demonstrate the value (or lack thereof) of our benchmarks. We then offer
several approaches to summarizing our experimental results, drawing several
conclusions about the impact of our methodology as well as the strengths and
weaknesses of some algorithms. Last, we compare results against a trivial
solution as an alternate means of normalizing the reported performance of
algorithms. The intended contributions of this article are many; in addition to
providing a large publicly-available corpus of anomaly detection benchmarks, we
provide an ontology for describing anomaly detection contexts, a methodology
for controlling various aspects of benchmark creation, guidelines for future
experimental design and a discussion of the many potential pitfalls of trying
to measure success in this field.
A Novel Approach to Multimedia Ontology Engineering for Automated Reasoning over Audiovisual LOD Datasets
Authors: Leslie F. Sikos
Date: 2016-08-26 00:00:00

Multimedia reasoning, which is suitable for, among others, multimedia content
analysis and high-level video scene interpretation, relies on the formal and
comprehensive conceptualization of the represented knowledge domain. However,
most multimedia ontologies are not exhaustive in terms of role definitions, and
do not incorporate complex role inclusions and role interdependencies. In fact,
most multimedia ontologies do not have a role box at all, and implement only a
basic subset of the available logical constructors. Consequently, their
application in multimedia reasoning is limited. To address the above issues,
VidOnt, the very first multimedia ontology with SROIQ(D) expressivity and a
DL-safe ruleset has been introduced for next-generation multimedia reasoning.
In contrast to the common practice, the formal grounding has been set in one of
the most expressive description logics, and the ontology validated with
industry-leading reasoners, namely HermiT and FaCT++. This paper also presents
best practices for developing multimedia ontologies, based on my ontology
engineering approach.
Scalable Compression of Deep Neural Networks
Authors: Xing Wang, Jie Liang
Date: 2016-08-26 00:00:00

Deep neural networks generally involve some layers with mil- lions of
parameters, making them difficult to be deployed and updated on devices with
limited resources such as mobile phones and other smart embedded systems. In
this paper, we propose a scalable representation of the network parameters, so
that different applications can select the most suitable bit rate of the
network based on their own storage constraints. Moreover, when a device needs
to upgrade to a high-rate network, the existing low-rate network can be reused,
and only some incremental data are needed to be downloaded. We first
hierarchically quantize the weights of a pre-trained deep neural network to
enforce weight sharing. Next, we adaptively select the bits assigned to each
layer given the total bit budget. After that, we retrain the network to
fine-tune the quantized centroids. Experimental results show that our method
can achieve scalable compression with graceful degradation in the performance.
Hyperspectral Image Recovery via Hybrid Regularization
Authors: Reza Arablouei, Frank de Hoog
Date: 2015-11-09 00:00:00
Tasks: Denoising

Natural images tend to mostly consist of smooth regions with individual
pixels having highly correlated spectra. This information can be exploited to
recover hyperspectral images of natural scenes from their incomplete and noisy
measurements. To perform the recovery while taking full advantage of the prior
knowledge, we formulate a composite cost function containing a square-error
data-fitting term and two distinct regularization terms pertaining to spatial
and spectral domains. The regularization for the spatial domain is the sum of
total-variation of the image frames corresponding to all spectral bands. The
regularization for the spectral domain is the l1-norm of the coefficient matrix
obtained by applying a suitable sparsifying transform to the spectra of the
pixels. We use an accelerated proximal-subgradient method to minimize the
formulated cost function. We analyze the performance of the proposed algorithm
and prove its convergence. Numerical simulations using real hyperspectral
images exhibit that the proposed algorithm offers an excellent recovery
performance with a number of measurements that is only a small fraction of the
hyperspectral image data size. Simulation results also show that the proposed
algorithm significantly outperforms an accelerated proximal-gradient algorithm
that solves the classical basis-pursuit denoising problem to recover the
hyperspectral image.
Online Learning Schemes for Power Allocation in Energy Harvesting Communications
Authors: Pranav Sakulkar, Bhaskar Krishnamachari
Date: 2016-07-08 00:00:00
Tasks: Scheduling

We consider the problem of power allocation over a time-varying channel with
unknown distribution in energy harvesting communication systems. In this
problem, the transmitter has to choose the transmit power based on the amount
of stored energy in its battery with the goal of maximizing the average rate
obtained over time. We model this problem as a Markov decision process (MDP)
with the transmitter as the agent, the battery status as the state, the
transmit power as the action and the rate obtained as the reward. The average
reward maximization problem over the MDP can be solved by a linear program (LP)
that uses the transition probabilities for the state-action pairs and their
reward values to choose a power allocation policy. Since the rewards associated
the state-action pairs are unknown, we propose two online learning algorithms:
UCLP and Epoch-UCLP that learn these rewards and adapt their policies along the
way. The UCLP algorithm solves the LP at each step to decide its current policy
using the upper confidence bounds on the rewards, while the Epoch-UCLP
algorithm divides the time into epochs, solves the LP only at the beginning of
the epochs and follows the obtained policy in that epoch. We prove that the
reward losses or regrets incurred by both these algorithms are upper bounded by
constants. Epoch-UCLP incurs a higher regret compared to UCLP, but reduces the
computational requirements substantially. We also show that the presented
algorithms work for online learning in cost minimization problems like the
packet scheduling with power-delay tradeoff with minor changes.
Community Detection and Classification in Hierarchical Stochastic Blockmodels
Authors: Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, Carey E. Priebe
Date: 2015-03-07 00:00:00
Tasks: Classification, Community Detection, General Classification

We propose a robust, scalable, integrated methodology for community detection
and community comparison in graphs. In our procedure, we first embed a graph
into an appropriate Euclidean space to obtain a low-dimensional representation,
and then cluster the vertices into communities. We next employ nonparametric
graph inference techniques to identify structural similarity among these
communities. These two steps are then applied recursively on the communities,
allowing us to detect more fine-grained structure. We describe a hierarchical
stochastic blockmodel---namely, a stochastic blockmodel with a natural
hierarchical structure---and establish conditions under which our algorithm
yields consistent estimates of model parameters and motifs, which we define to
be stochastically similar groups of subgraphs. Finally, we demonstrate the
effectiveness of our algorithm in both simulated and real data. Specifically,
we address the problem of locating similar subcommunities in a partially
reconstructed Drosophila connectome and in the social network Friendster.
Fast Trajectory Simplification Algorithm for Natural User Interfaces in Robot Programming by Demonstration
Authors: Daniel L. Marino, Milos Manic
Date: 2016-08-25 00:00:00

Trajectory simplification is a problem encountered in areas like Robot
programming by demonstration, CAD/CAM, computer vision, and in GPS-based
applications like traffic analysis. This problem entails reduction of the
points in a given trajectory while keeping the relevant points which preserve
important information. The benefits include storage reduction, computational
expense, while making data more manageable. Common techniques formulate a
minimization problem to be solved, where the solution is found iteratively
under some error metric, which causes the algorithms to work in super-linear
time. We present an algorithm called FastSTray, which selects the relevant
points in the trajectory in linear time by following an open loop heuristic
approach. While most current trajectory simplification algorithms are tailored
for GPS trajectories, our approach focuses on smooth trajectories for robot
programming by demonstration recorded using motion capture systems.Two
variations of the algorithm are presented: 1. aims to preserve shape and
temporal information; 2. preserves only shape information. Using the points in
the simplified trajectory we use cubic splines to interpolate between these
points and recreate the original trajectory. The presented algorithm was tested
on trajectories recorded from a hand-tracking system. It was able to eliminate
about 90% of the points in the original trajectories while maintaining errors
between 0.78-2cm which corresponds to 1%-2.4% relative error with respect to
the bounding box of the trajectories.
Feedback-Controlled Sequential Lasso Screening
Authors: Yun Wang, Xu Chen, Peter J. Ramadge
Date: 2016-08-21 00:00:00
Tasks: Model Selection

One way to solve lasso problems when the dictionary does not fit into
available memory is to first screen the dictionary to remove unneeded features.
Prior research has shown that sequential screening methods offer the greatest
promise in this endeavor. Most existing work on sequential screening targets
the context of tuning parameter selection, where one screens and solves a
sequence of $N$ lasso problems with a fixed grid of geometrically spaced
regularization parameters. In contrast, we focus on the scenario where a target
regularization parameter has already been chosen via cross-validated model
selection, and we then need to solve many lasso instances using this fixed
value. In this context, we propose and explore a feedback controlled sequential
screening scheme. Feedback is used at each iteration to select the next problem
to be solved. This allows the sequence of problems to be adapted to the
instance presented and the number of intermediate problems to be automatically
selected. We demonstrate our feedback scheme using several datasets including a
dictionary of approximate size 100,000 by 300,000.
Fundamental Limits of Budget-Fidelity Trade-off in Label Crowdsourcing
Authors: Farshad Lahouti, Babak Hassibi
Date: 2016-08-25 00:00:00
Proceeding: NeurIPS 2016 12

Digital crowdsourcing (CS) is a modern approach to perform certain large
projects using small contributions of a large crowd. In CS, a taskmaster
typically breaks down the project into small batches of tasks and assigns them
to so-called workers with imperfect skill levels. The crowdsourcer then
collects and analyzes the results for inference and serving the purpose of the
project. In this work, the CS problem, as a human-in-the-loop computation
problem, is modeled and analyzed in an information theoretic rate-distortion
framework. The purpose is to identify the ultimate fidelity that one can
achieve by any form of query from the crowd and any decoding (inference)
algorithm with a given budget. The results are established by a joint source
channel (de)coding scheme, which represent the query scheme and inference, over
parallel noisy channels, which model workers with imperfect skill levels. We
also present and analyze a query scheme dubbed $k$-ary incidence coding and
study optimized query pricing in this setting.
The Symmetry of a Simple Optimization Problem in Lasso Screening
Authors: Yun Wang, Peter J. Ramadge
Date: 2016-08-21 00:00:00
Tasks: Computational Efficiency

Recently dictionary screening has been proposed as an effective way to
improve the computational efficiency of solving the lasso problem, which is one
of the most commonly used method for learning sparse representations. To
address today's ever increasing large dataset, effective screening relies on a
tight region bound on the solution to the dual lasso. Typical region bounds are
in the form of an intersection of a sphere and multiple half spaces. One way to
tighten the region bound is using more half spaces, which however, adds to the
overhead of solving the high dimensional optimization problem in lasso
screening. This paper reveals the interesting property that the optimization
problem only depends on the projection of features onto the subspace spanned by
the normals of the half spaces. This property converts an optimization problem
in high dimension to much lower dimension, and thus sheds light on reducing the
computation overhead of lasso screening based on tighter region bounds.
Prioritised Default Logic as Argumentation with Partial Order Default Priorities
Authors: Anthony P. Young, Sanjay Modgil, Odinaldo Rodrigues
Date: 2016-08-25 00:00:00

We express Brewka's prioritised default logic (PDL) as argumentation using
ASPIC+. By representing PDL as argumentation and designing an argument
preference relation that takes the argument structure into account, we prove
that the conclusions of the justified arguments correspond to the PDL
extensions. We will first assume that the default priority is total, and then
generalise to the case where it is a partial order. This provides a
characterisation of non-monotonic inference in PDL as an exchange of argument
and counter-argument, providing a basis for distributed non-monotonic reasoning
in the form of dialogue.
Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
Authors: Cem Aksoylar, George Atia, Venkatesh Saligrama
Date: 2013-04-02 00:00:00
Tasks: regression

We derive fundamental sample complexity bounds for recovering sparse and
structured signals for linear and nonlinear observation models including sparse
regression, group testing, multivariate regression and problems with missing
features. In general, sparse signal processing problems can be characterized in
terms of the following Markovian property. We are given a set of $N$ variables
$X_1,X_2,\ldots,X_N$, and there is an unknown subset of variables $S \subset
\{1,\ldots,N\}$ that are relevant for predicting outcomes $Y$. More
specifically, when $Y$ is conditioned on $\{X_n\}_{n\in S}$ it is conditionally
independent of the other variables, $\{X_n\}_{n \not \in S}$. Our goal is to
identify the set $S$ from samples of the variables $X$ and the associated
outcomes $Y$. We characterize this problem as a version of the noisy channel
coding problem. Using asymptotic information theoretic analyses, we establish
mutual information formulas that provide sufficient and necessary conditions on
the number of samples required to successfully recover the salient variables.
These mutual information expressions unify conditions for both linear and
nonlinear observations. We then compute sample complexity bounds for the
aforementioned models, based on the mutual information expressions in order to
demonstrate the applicability and flexibility of our results in general sparse
signal processing models.
A globally-applicable disease ontology for biosurveillance; Anthology of Biosurveillance Diseases (ABD)
Authors: A. R. Daughton, R. Priedhorsky, G. Fairchild, N. Generous, A. Hengartner, E. Abeyta, N. Velappan, A. Lillo, K. Stark, A. Deshpande
Date: 2016-08-25 00:00:00

Biosurveillance, a relatively young field, has recently increased in
importance because of its relevance to national security and global health.
Databases and tools describing particular subsets of disease are becoming
increasingly common in the field. However, a common method to describe those
diseases is lacking. Here, we present the Anthology of Biosurveillance Diseases
(ABD), an ontology of infectious diseases of biosurveillance relevance.
Learning Latent Vector Spaces for Product Search
Authors: Christophe Van Gysel, Maarten de Rijke, Evangelos Kanoulas
Date: 2016-08-25 00:00:00
Tasks: Learning-To-Rank, parameter estimation

We introduce a novel latent vector space model that jointly learns the latent
representations of words, e-commerce products and a mapping between the two
without the need for explicit annotations. The power of the model lies in its
ability to directly model the discriminative relation between products and a
particular word. We compare our method to existing latent vector space models
(LSI, LDA and word2vec) and evaluate it as a feature in a learning to rank
setting. Our latent vector space model achieves its enhanced performance as it
learns better product representations. Furthermore, the mapping from words to
products and the representations of words benefit directly from the errors
propagated back from the product representations during parameter estimation.
We provide an in-depth analysis of the performance of our model and analyze the
structure of the learned representations.
Modeling and Propagating CNNs in a Tree Structure for Visual Tracking
Authors: Hyeonseob Nam, Mooyeol Baek, Bohyung Han
Date: 2016-08-25 00:00:00
Tasks: Object Tracking, Visual Object Tracking, Visual Tracking

We present an online visual tracking algorithm by managing multiple target
appearance models in a tree structure. The proposed algorithm employs
Convolutional Neural Networks (CNNs) to represent target appearances, where
multiple CNNs collaborate to estimate target states and determine the desirable
paths for online model updates in the tree. By maintaining multiple CNNs in
diverse branches of tree structure, it is convenient to deal with
multi-modality in target appearances and preserve model reliability through
smooth updates along tree paths. Since multiple CNNs share all parameters in
convolutional layers, it takes advantage of multiple models with little extra
cost by saving memory space and avoiding redundant network evaluations. The
final target state is estimated by sampling target candidates around the state
in the previous frame and identifying the best sample in terms of a weighted
average score from a set of active CNNs. Our algorithm illustrates outstanding
performance compared to the state-of-the-art techniques in challenging datasets
such as online tracking benchmark and visual object tracking challenge.
Formal Concept Analysis of Rodent Carriers of Zoonotic Disease
Authors: Roman Ilin, Barbara A. Han
Date: 2016-08-25 00:00:00

The technique of Formal Concept Analysis is applied to a dataset describing
the traits of rodents, with the goal of identifying zoonotic disease
carriers,or those species carrying infections that can spillover to cause human
disease. The concepts identified among these species together provide
rules-of-thumb about the intrinsic biological features of rodents that carry
zoonotic diseases, and offer utility for better targeting field surveillance
efforts in the search for novel disease carriers in the wild.
Sentiment/Subjectivity Analysis Survey for Languages other than English
Authors: Mohammed Korayem, Khalifeh Aljadda, David Crandall
Date: 2016-01-01 00:00:00
Tasks: Arabic Sentiment Analysis, Sentiment Analysis, Subjectivity Analysis, Survey

Subjective and sentiment analysis have gained considerable attention
recently. Most of the resources and systems built so far are done for English.
The need for designing systems for other languages is increasing. This paper
surveys different ways used for building systems for subjective and sentiment
analysis for languages other than English. There are three different types of
systems used for building these systems. The first (and the best) one is the
language specific systems. The second type of systems involves reusing or
transferring sentiment resources from English to the target language. The third
type of methods is based on using language independent methods. The paper
presents a separate section devoted to Arabic sentiment analysis.
Social and Business Intelligence Analysis Using PSO
Authors: Jyoti Chaturvedi, Anubha Parashar, Amrita A Manjrekar, Vinay S Bhaskar
Date: 2014-07-23 00:00:00
Tasks: Decision Making, Descriptive, Management

The goal of this paper is to elaborate swarm intelligence for business
intelligence decision making and the business rules management improvement.
.The swarm optimization, which is highly influenced by the behavior of
creature, performs in group. The Spatial data is defined as data that is
represented by 2D or 3D images. SQL Server supports only 2D images till now. As
we know that location is an essential part of any organizational data as well
as business data enterprises maintain customer address lists, own property,
ship goods from and to warehouses, manage transport flows among their
workforce, and perform many other activities. By means to say a lot of spatial
data is used and processed by enterprises, organizations and other bodies in
order to make the things more visible and self descriptive. From the
experiments, we found that PSO is can facilitate the intelligence in social and
business behavior.
Minimizing Quadratic Functions in Constant Time
Authors: Kohei Hayashi, Yuichi Yoshida
Date: 2016-08-25 00:00:00
Proceeding: NeurIPS 2016 12

A sampling-based optimization method for quadratic functions is proposed. Our
method approximately solves the following $n$-dimensional quadratic
minimization problem in constant time, which is independent of $n$:
$z^*=\min_{\mathbf{v} \in \mathbb{R}^n}\langle\mathbf{v}, A \mathbf{v}\rangle +
n\langle\mathbf{v}, \mathrm{diag}(\mathbf{d})\mathbf{v}\rangle +
n\langle\mathbf{b}, \mathbf{v}\rangle$, where $A \in \mathbb{R}^{n \times n}$
is a matrix and $\mathbf{d},\mathbf{b} \in \mathbb{R}^n$ are vectors. Our
theoretical analysis specifies the number of samples $k(\delta, \epsilon)$ such
that the approximated solution $z$ satisfies $|z - z^*| = O(\epsilon n^2)$ with
probability $1-\delta$. The empirical performance (accuracy and runtime) is
positively confirmed by numerical experiments.