pwc-archive/papers-with-abstracts huggingface dataset:
High-Performance Distributed ML at Scale through Parameter Server Consistency Models
Authors: Wei Dai, Abhimanu Kumar, Jinliang Wei, Qirong Ho, Garth Gibson, Eric P. Xing
Date: 2014-10-29 00:00:00
Tasks: Vocal Bursts Intensity Prediction

As Machine Learning (ML) applications increase in data size and model
complexity, practitioners turn to distributed clusters to satisfy the increased
computational and memory demands. Unfortunately, effective use of clusters for
ML requires considerable expertise in writing distributed code, while
highly-abstracted frameworks like Hadoop have not, in practice, approached the
performance seen in specialized ML implementations. The recent Parameter Server
(PS) paradigm is a middle ground between these extremes, allowing easy
conversion of single-machine parallel ML applications into distributed ones,
while maintaining high throughput through relaxed "consistency models" that
allow inconsistent parameter reads. However, due to insufficient theoretical
study, it is not clear which of these consistency models can really ensure
correct ML algorithm output; at the same time, there remain many
theoretically-motivated but undiscovered opportunities to maximize
computational throughput. Motivated by this challenge, we study both the
theoretical guarantees and empirical behavior of iterative-convergent ML
algorithms in existing PS consistency models. We then use the gleaned insights
to improve a consistency model using an "eager" PS communication mechanism, and
implement it as a new PS system that enables ML algorithms to reach their
solution more quickly.
Latent Feature Based FM Model For Rating Prediction
Authors: Xudong Liu, Bin Zhang, Ting Zhang, Chang Liu
Date: 2014-10-29 00:00:00
Tasks: model, Prediction, Recommendation Systems

Rating Prediction is a basic problem in Recommender System, and one of the
most widely used method is Factorization Machines(FM). However, traditional
matrix factorization methods fail to utilize the benefit of implicit feedback,
which has been proved to be important in Rating Prediction problem. In this
work, we consider a specific situation, movie rating prediction, where we
assume that watching history has a big influence on his/her rating behavior on
an item. We introduce two models, Latent Dirichlet Allocation(LDA) and
word2vec, both of which perform state-of-the-art results in training latent
features. Based on that, we propose two feature based models. One is the
Topic-based FM Model which provides the implicit feedback to the matrix
factorization. The other is the Vector-based FM Model which expresses the order
info of watching history. Empirical results on three datasets demonstrate that
our method performs better than the baseline model and confirm that
Vector-based FM Model usually works better as it contains the order info.
A Semantic Web of Know-How: Linked Data for Community-Centric Tasks
Authors: Paolo Pareti, Ewan Klein, Adam Barker
Date: 2014-10-29 00:00:00

This paper proposes a novel framework for representing community know-how on
the Semantic Web. Procedural knowledge generated by web communities typically
takes the form of natural language instructions or videos and is largely
unstructured. The absence of semantic structure impedes the deployment of many
useful applications, in particular the ability to discover and integrate
know-how automatically. We discuss the characteristics of community know-how
and argue that existing knowledge representation frameworks fail to represent
it adequately. We present a novel framework for representing the semantic
structure of community know-how and demonstrate the feasibility of our approach
by providing a concrete implementation which includes a method for
automatically acquiring procedural knowledge for real-world tasks.
Reasoning for ALCQ extended with a flexible meta-modelling hierarchy
Authors: Regina Motz, Edelweis Rohrer, Paula Severi
Date: 2014-10-29 00:00:00

This works is motivated by a real-world case study where it is necessary to
integrate and relate existing ontologies through meta- modelling. For this, we
introduce the Description Logic ALCQM which is obtained from ALCQ by adding
statements that equate individuals to concepts in a knowledge base. In this new
extension, a concept can be an individual of another concept (called
meta-concept) which themselves can be individuals of yet another concept
(called meta meta-concept) and so on. We define a tableau algorithm for
checking consistency of an ontology in ALCQM and prove its correctness.
Using synchronous Boolean networks to model several phenomena of collective behavior
Authors: Stepan Kochemazov, Alexander Semenov
Date: 2014-10-29 00:00:00

In this paper, we propose an approach for modeling and analysis of a number
of phenomena of collective behavior. By collectives we mean multi-agent systems
that transition from one state to another at discrete moments of time. The
behavior of a member of a collective (agent) is called conforming if the
opinion of this agent at current time moment conforms to the opinion of some
other agents at the previous time moment. We presume that at each moment of
time every agent makes a decision by choosing from the set {0,1} (where
1-decision corresponds to action and 0-decision corresponds to inaction). In
our approach we model collective behavior with synchronous Boolean networks. We
presume that in a network there can be agents that act at every moment of time.
Such agents are called instigators. Also there can be agents that never act.
Such agents are called loyalists. Agents that are neither instigators nor
loyalists are called simple agents. We study two combinatorial problems. The
first problem is to find a disposition of instigators that in several time
moments transforms a network from a state where a majority of simple agents are
inactive to a state with a majority of active agents. The second problem is to
find a disposition of loyalists that returns the network to a state with a
majority of inactive agents. Similar problems are studied for networks in which
simple agents demonstrate the contrary to conforming behavior that we call
anticonforming. We obtained several theoretical results regarding the behavior
of collectives of agents with conforming or anticonforming behavior. In
computational experiments we solved the described problems for randomly
generated networks with several hundred vertices. We reduced corresponding
combinatorial problems to the Boolean satisfiability problem (SAT) and used
modern SAT solvers to solve the instances obtained.
Extended Dynamic Programming and Fast Multidimensional Search Algorithm for Energy Minization in Stereo and Motion
Authors: Mikhail G. Mozerov
Date: 2014-10-29 00:00:00
Tasks: GPU

This paper presents a novel extended dynamic programming approach for energy
minimization (EDP) to solve the correspondence problem for stereo and motion. A
significant speedup is achieved using a recursive minimum search strategy
(RMS). The mentioned speedup is particularly important if the disparity space
is 2D as well as 3D. The proposed RMS can also be applied in the well-known
dynamic programming (DP) approach for stereo and motion. In this case, the
general 2D problem of the global discrete energy minimization is reduced to
several mutually independent sub-problems of the one-dimensional minimization.
The EDP method is used when the approximation of the general 2D discrete energy
minimization problem is considered. Then the RMS algorithm is an essential part
of the EDP method. Using the EDP algorithm we obtain a lower energy bound than
the graph cuts (GC) expansion technique on stereo and motion problems. The
proposed calculation scheme possesses natural parallelism and can be realized
on graphics processing unit (GPU) platforms, and can be potentially restricted
further by the number of scanlines in the image plane. Furthermore, the RMS and
EDP methods can be used in any optimization problem where the objective
function meets specific conditions in the smoothness term.
Global Bandits with Holder Continuity
Authors: Onur Atan, Cem Tekin, Mihaela van der Schaar
Date: 2014-10-29 00:00:00
Tasks: Informativeness

Standard Multi-Armed Bandit (MAB) problems assume that the arms are
independent. However, in many application scenarios, the information obtained
by playing an arm provides information about the remainder of the arms. Hence,
in such applications, this informativeness can and should be exploited to
enable faster convergence to the optimal solution. In this paper, we introduce
and formalize the Global MAB (GMAB), in which arms are globally informative
through a global parameter, i.e., choosing an arm reveals information about all
the arms. We propose a greedy policy for the GMAB which always selects the arm
with the highest estimated expected reward, and prove that it achieves bounded
parameter-dependent regret. Hence, this policy selects suboptimal arms only
finitely many times, and after a finite number of initial time steps, the
optimal arm is selected in all of the remaining time steps with probability
one. In addition, we also study how the informativeness of the arms about each
other's rewards affects the speed of learning. Specifically, we prove that the
parameter-free (worst-case) regret is sublinear in time, and decreases with the
informativeness of the arms. We also prove a sublinear in time Bayesian risk
bound for the GMAB which reduces to the well-known Bayesian risk bound for
linearly parameterized bandits when the arms are fully informative. GMABs have
applications ranging from drug and treatment discovery to dynamic pricing.
Sub-threshold CMOS Spiking Neuron Circuit Design for Navigation Inspired by C. elegans Chemotaxis
Authors: Shibani Santurkar, Bipin Rajendran
Date: 2014-10-29 00:00:00

We demonstrate a spiking neural network for navigation motivated by the
chemotaxis network of Caenorhabditis elegans. Our network uses information
regarding temporal gradients in the tracking variable's concentration to make
navigational decisions. The gradient information is determined by mimicking the
underlying mechanisms of the ASE neurons of C. elegans. Simulations show that
our model is able to forage and track a target set-point in extremely noisy
environments. We develop a VLSI implementation for the main gradient detector
neurons, which could be integrated with standard comparator circuitry to
develop a robust circuit for navigation and contour tracking.
A neural circuit for navigation inspired by C. elegans Chemotaxis
Authors: Shibani Santurkar, Bipin Rajendran
Date: 2014-10-29 00:00:00

We develop an artificial neural circuit for contour tracking and navigation
inspired by the chemotaxis of the nematode Caenorhabditis elegans. In order to
harness the computational advantages spiking neural networks promise over their
non-spiking counterparts, we develop a network comprising 7-spiking neurons
with non-plastic synapses which we show is extremely robust in tracking a range
of concentrations. Our worm uses information regarding local temporal gradients
in sodium chloride concentration to decide the instantaneous path for foraging,
exploration and tracking. A key neuron pair in the C. elegans chemotaxis
network is the ASEL & ASER neuron pair, which capture the gradient of
concentration sensed by the worm in their graded membrane potentials. The
primary sensory neurons for our network are a pair of artificial spiking
neurons that function as gradient detectors whose design is adapted from a
computational model of the ASE neuron pair in C. elegans. Simulations show that
our worm is able to detect the set-point with approximately four times higher
probability than the optimal memoryless Levy foraging model. We also show that
our spiking neural network is much more efficient and noise-resilient while
navigating and tracking a contour, as compared to an equivalent non-spiking
network. We demonstrate that our model is extremely robust to noise and with
slight modifications can be used for other practical applications such as
obstacle avoidance. Our network model could also be extended for use in
three-dimensional contour tracking or obstacle avoidance.
Faster graphical model identification of tandem mass spectra using peptide word lattices
Authors: Shengjie Wang, John T. Halloran, Jeff A. Bilmes, William S. Noble
Date: 2014-10-29 00:00:00

Liquid chromatography coupled with tandem mass spectrometry, also known as
shotgun proteomics, is a widely-used high-throughput technology for identifying
proteins in complex biological samples. Analysis of the tens of thousands of
fragmentation spectra produced by a typical shotgun proteomics experiment
begins by assigning to each observed spectrum the peptide hypothesized to be
responsible for generating the spectrum, typically done by searching each
spectrum against a database of peptides. We have recently described a machine
learning method---Dynamic Bayesian Network for Rapid Identification of Peptides
(DRIP)---that not only achieves state-of-the-art spectrum identification
performance on a variety of datasets but also provides a trainable model
capable of returning valuable auxiliary information regarding specific
peptide-spectrum matches. In this work, we present two significant improvements
to DRIP. First, we describe how to use word lattices, which are widely used in
natural language processing, to significantly speed up DRIP's computations. To
our knowledge, all existing shotgun proteomics search engines compute
independent scores between a given observed spectrum and each possible
candidate peptide from the database. The key idea of the word lattice is to
represent the set of candidate peptides in a single data structure, thereby
allowing sharing of redundant computations among the different candidates. We
demonstrate that using lattices in conjunction with DRIP leads to speedups on
the order of tens across yeast and worm data sets. Second, we introduce a
variant of DRIP that uses a discriminative training framework, performing
maximum mutual entropy estimation rather than maximum likelihood estimation.
This modification improves DRIP's statistical power, enabling us to increase
the number of identified spectrum at a 1% false discovery rate on yeast and
worm data sets.
A Direct Estimation of High Dimensional Stationary Vector Autoregressions
Authors: Fang Han, Huanran Lu, Han Liu
Date: 2013-07-01 00:00:00
Tasks: parameter estimation, Time Series, Time Series Analysis, Vocal Bursts Intensity Prediction

The vector autoregressive (VAR) model is a powerful tool in modeling complex
time series and has been exploited in many fields. However, fitting high
dimensional VAR model poses some unique challenges: On one hand, the
dimensionality, caused by modeling a large number of time series and higher
order autoregressive processes, is usually much higher than the time series
length; On the other hand, the temporal dependence structure in the VAR model
gives rise to extra theoretical challenges. In high dimensions, one popular
approach is to assume the transition matrix is sparse and fit the VAR model
using the "least squares" method with a lasso-type penalty. In this manuscript,
we propose an alternative way in estimating the VAR model. The main idea is,
via exploiting the temporal dependence structure, to formulate the estimating
problem into a linear program. There is instant advantage for the proposed
approach over the lasso-type estimators: The estimation equation can be
decomposed into multiple sub-equations and accordingly can be efficiently
solved in a parallel fashion. In addition, our method brings new theoretical
insights into the VAR model analysis. So far the theoretical results developed
in high dimensions (e.g., Song and Bickel (2011) and Kock and Callot (2012))
mainly pose assumptions on the design matrix of the formulated regression
problems. Such conditions are indirect about the transition matrices and not
transparent. In contrast, our results show that the operator norm of the
transition matrices plays an important role in estimation accuracy. We provide
explicit rates of convergence for both estimation and prediction. In addition,
we provide thorough experiments on both synthetic and real-world equity data to
show that there are empirical advantages of our method over the lasso-type
estimators in both parameter estimation and forecasting.
A Markov Decision Process Analysis of the Cold Start Problem in Bayesian Information Filtering
Authors: Xiaoting Zhao, Peter I. Frazier
Date: 2014-10-29 00:00:00
Tasks: Articles

We consider the information filtering problem, in which we face a stream of
items, and must decide which ones to forward to a user to maximize the number
of relevant items shown, minus a penalty for each irrelevant item shown.
Forwarding decisions are made separately in a personalized way for each user.
We focus on the cold-start setting for this problem, in which we have limited
historical data on the user's preferences, and must rely on feedback from
forwarded articles to learn which the fraction of items relevant to the user in
each of several item categories. Performing well in this setting requires
trading exploration vs. exploitation, forwarding items that are likely to be
irrelevant, to allow learning that will improve later performance. In a
Bayesian setting, and using Markov decision processes, we show how the
Bayes-optimal forwarding algorithm can be computed efficiently when the user
will examine each forwarded article, and how an upper bound on the
Bayes-optimal procedure and a heuristic index policy can be obtained for the
setting when the user will examine only a limited number of forwarded items. We
present results from simulation experiments using parameters estimated using
historical data from arXiv.org.
Efficient optimisation of structures using tabu search
Authors: Andy M. Connor, Keith A. Seffen, Geoffrey T. Parks, P. John Clarkson
Date: 2014-10-29 00:00:00

This paper presents a novel approach to the optimisation of structures using
a Tabu search (TS) method. TS is a metaheuristic which is used to guide local
search methods towards a globally optimal solution by using flexible memory
cycles of differing time spans. Results are presented for the well established
ten bar truss problem and compared to results published in the literature. In
the first example a truss is optimised to minimise mass and the results
compared to results obtained using an alternative TS implementation. In the
second example, the problem has multiple objectives that are compounded into a
single objective function value using game theory. In general the results
demonstrate that the TS method is capable of solving structural optimisation
problems at least as efficiently as other numerical optimisation approaches.
A mutli-thread tabu search algorithm
Authors: A. M. Connor
Date: 2014-10-29 00:00:00

This paper describes a novel refinement to a Tabu search algorithm that has
been implemented in an attempt to improve the robustness of the search when
applied to particularly complex problems. In this approach, two Tabu searches
are carried out in parallel. Each search thread is characterised by it's own
short term memory which forces that point out of local optima. However, the two
search threads share an intermediate term memory so allowing a degree of
information to be passed between them. Results are presented for both
unconstrained and constrained numerical functions as well as a problem in the
field of hydraulic circuit optimization. Simulation of hydraulic circuit
performance is achieved by linking the optimization algorithm to the commercial
simulation package Bathfp.
Correcting Errors in Digital Lexicographic Resources Using a Dictionary Manipulation Language
Authors: David Zajic, Michael Maxwell, David Doermann, Paul Rodrigues, Michael Bloodgood
Date: 2014-10-28 00:00:00

We describe a paradigm for combining manual and automatic error correction of
noisy structured lexicographic data. Modifications to the structure and
underlying text of the lexicographic data are expressed in a simple,
interpreted programming language. Dictionary Manipulation Language (DML)
commands identify nodes by unique identifiers, and manipulations are performed
using simple commands such as create, move, set text, etc. Corrected lexicons
are produced by applying sequences of DML commands to the source version of the
lexicon. DML commands can be written manually to repair one-off errors or
generated automatically to correct recurring problems. We discuss advantages of
the paradigm for the task of editing digital bilingual dictionaries.
Graphical LASSO Based Model Selection for Time Series
Authors: Alexander Jung, Gabor Hannak, Norbert Görtz
Date: 2014-10-05 00:00:00
Tasks: Gaussian Processes, Model Selection, Time Series, Time Series Analysis

We propose a novel graphical model selection (GMS) scheme for
high-dimensional stationary time series or discrete time process. The method is
based on a natural generalization of the graphical LASSO (gLASSO), introduced
originally for GMS based on i.i.d. samples, and estimates the conditional
independence graph (CIG) of a time series from a finite length observation. The
gLASSO for time series is defined as the solution of an l1-regularized maximum
(approximate) likelihood problem. We solve this optimization problem using the
alternating direction method of multipliers (ADMM). Our approach is
nonparametric as we do not assume a finite dimensional (e.g., an
autoregressive) parametric model for the observed process. Instead, we require
the process to be sufficiently smooth in the spectral domain. For Gaussian
processes, we characterize the performance of our method theoretically by
deriving an upper bound on the probability that our algorithm fails to
correctly identify the CIG. Numerical experiments demonstrate the ability of
our method to recover the correct CIG from a limited amount of samples.
A hierarchical framework for object recognition
Authors: Reza Moazzezi
Date: 2014-10-28 00:00:00
Tasks: Object, Object Recognition

Object recognition in the presence of background clutter and distractors is a
central problem both in neuroscience and in machine learning. However, the
performance level of the models that are inspired by cortical mechanisms,
including deep networks such as convolutional neural networks and deep belief
networks, is shown to significantly decrease in the presence of noise and
background objects [19, 24]. Here we develop a computational framework that is
hierarchical, relies heavily on key properties of the visual cortex including
mid-level feature selectivity in visual area V4 and Inferotemporal cortex (IT)
[4, 9, 12, 18], high degrees of selectivity and invariance in IT [13, 17, 18]
and the prior knowledge that is built into cortical circuits (such as the
emergence of edge detector neurons in primary visual cortex before the onset of
the visual experience) [1, 21], and addresses the problem of object recognition
in the presence of background noise and distractors. Our approach is
specifically designed to address large deformations, allows flexible
communication between different layers of representation and learns highly
selective filters from a small number of training examples.
On the Computational Efficiency of Training Neural Networks
Authors: Roi Livni, Shai Shalev-Shwartz, Ohad Shamir
Date: 2014-10-05 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Computational Efficiency

It is well-known that neural networks are computationally hard to train. On
the other hand, in practice, modern day neural networks are trained efficiently
using SGD and a variety of tricks that include different activation functions
(e.g. ReLU), over-specification (i.e., train networks which are larger than
needed), and regularization. In this paper we revisit the computational
complexity of training neural networks from a modern perspective. We provide
both positive and negative results, some of them yield new provably efficient
and practical algorithms for training certain types of neural networks.