pwc-archive/papers-with-abstracts huggingface dataset:
Spectral Analysis of Symmetric and Anti-Symmetric Pairwise Kernels
Authors: Tapio Pahikkala, Markus Viljanen, Antti Airola, Willem Waegeman
Date: 2015-06-19 00:00:00
Tasks: regression

We consider the problem of learning regression functions from pairwise data
when there exists prior knowledge that the relation to be learned is symmetric
or anti-symmetric. Such prior knowledge is commonly enforced by symmetrizing or
anti-symmetrizing pairwise kernel functions. Through spectral analysis, we show
that these transformations reduce the kernel's effective dimension. Further, we
provide an analysis of the approximation properties of the resulting kernels,
and bound the regularization bias of the kernels in terms of the corresponding
bias of the original kernel.
A Tight Runtime Analysis of the $(1+(λ, λ))$ Genetic Algorithm on OneMax
Authors: Benjamin Doerr, Carola Doerr
Date: 2015-06-19 00:00:00

Understanding how crossover works is still one of the big challenges in
evolutionary computation research, and making our understanding precise and
proven by mathematical means might be an even bigger one. As one of few
examples where crossover provably is useful, the $(1+(\lambda, \lambda))$
Genetic Algorithm (GA) was proposed recently in [Doerr, Doerr, Ebel: TCS 2015].
Using the fitness level method, the expected optimization time on general
OneMax functions was analyzed and a $O(\max\{n\log(n)/\lambda, \lambda n\})$
bound was proven for any offspring population size $\lambda \in [1..n]$.
  We improve this work in several ways, leading to sharper bounds and a better
understanding of how the use of crossover speeds up the runtime in this
algorithm. We first improve the upper bound on the runtime to
$O(\max\{n\log(n)/\lambda, n\lambda \log\log(\lambda)/\log(\lambda)\})$. This
improvement is made possible from observing that in the parallel generation of
$\lambda$ offspring via crossover (but not mutation), the best of these often
is better than the expected value, and hence several fitness levels can be
gained in one iteration.
  We then present the first lower bound for this problem. It matches our upper
bound for all values of $\lambda$. This allows to determine the asymptotically
optimal value for the population size. It is $\lambda =
\Theta(\sqrt{\log(n)\log\log(n)/\log\log\log(n)})$, which gives an optimization
time of $\Theta(n \sqrt{\log(n)\log\log\log(n)/\log\log(n)})$. Hence the
improved runtime analysis gives a better runtime guarantee along with a better
suggestion for the parameter $\lambda$.
  We finally give a tail bound for the upper tail of the runtime distribution,
which shows that the actual runtime exceeds our runtime guarantee by a factor
of $(1+\delta)$ with probability $O((n/\lambda^2)^{-\delta})$ only.
Sampling constrained probability distributions using Spherical Augmentation
Authors: Shiwei Lan, Babak Shahbaba
Date: 2015-06-19 00:00:00
Tasks: Bayesian Inference, regression

Statistical models with constrained probability distributions are abundant in
machine learning. Some examples include regression models with norm constraints
(e.g., Lasso), probit, many copula models, and latent Dirichlet allocation
(LDA). Bayesian inference involving probability distributions confined to
constrained domains could be quite challenging for commonly used sampling
algorithms. In this paper, we propose a novel augmentation technique that
handles a wide range of constraints by mapping the constrained domain to a
sphere in the augmented space. By moving freely on the surface of this sphere,
sampling algorithms handle constraints implicitly and generate proposals that
remain within boundaries when mapped back to the original space. Our proposed
method, called {Spherical Augmentation}, provides a mathematically natural and
computationally efficient framework for sampling from constrained probability
distributions. We show the advantages of our method over state-of-the-art
sampling algorithms, such as exact Hamiltonian Monte Carlo, using several
examples including truncated Gaussian distributions, Bayesian Lasso, Bayesian
bridge regression, reconstruction of quantized stationary Gaussian process, and
LDA for topic modeling.
Expectation Particle Belief Propagation
Authors: Thibaut Lienart, Yee Whye Teh, Arnaud Doucet
Date: 2015-06-19 00:00:00
Proceeding: NeurIPS 2015 12

We propose an original particle-based implementation of the Loopy Belief
Propagation (LPB) algorithm for pairwise Markov Random Fields (MRF) on a
continuous state space. The algorithm constructs adaptively efficient proposal
distributions approximating the local beliefs at each note of the MRF. This is
achieved by considering proposal distributions in the exponential family whose
parameters are updated iterately in an Expectation Propagation (EP) framework.
The proposed particle scheme provides consistent estimation of the LBP
marginals as the number of particles increases. We demonstrate that it provides
more accurate results than the Particle Belief Propagation (PBP) algorithm of
Ihler and McAllester (2009) at a fraction of the computational cost and is
additionally more robust empirically. The computational complexity of our
algorithm at each iteration is quadratic in the number of particles. We also
propose an accelerated implementation with sub-quadratic computational
complexity which still provides consistent estimates of the loopy BP marginal
distributions and performs almost as well as the original procedure.
Exploring the influence of scale on artist attribution
Authors: Nanne van Noord, Eric Postma
Date: 2015-06-19 00:00:00

Previous work has shown that the artist of an artwork can be identified by
use of computational methods that analyse digital images. However, the
digitised artworks are often investigated at a coarse scale discarding many of
the important details that may define an artist's style. In recent years high
resolution images of artworks have become available, which, combined with
increased processing power and new computational techniques, allow us to
analyse digital images of artworks at a very fine scale. In this work we train
and evaluate a Convolutional Neural Network (CNN) on the task of artist
attribution using artwork images of varying resolutions. To this end, we
combine two existing methods to enable the application of high resolution
images to CNNs. By comparing the attribution performances obtained at different
scales, we find that in most cases finer scales are beneficial to the
attribution performance, whereas for a minority of the artists, coarser scales
appear to be preferable. We conclude that artist attribution would benefit from
a multi-scale CNN approach which vastly expands the possibilities for
computational art forensics.
New Descriptor for Glomerulus Detection in Kidney Microscopy Image
Authors: Tsuyoshi Kato, Raissa Relator, Hayliang Ngouv, Yoshihiro Hirohashi, Tetsuhiro Kakimoto, Kinya Okada
Date: 2015-06-19 00:00:00
Tasks: object-detection, Object Detection

Glomerulus detection is a key step in histopathological evaluation of
microscopy images of kidneys. However, the task of automatic detection of
glomeruli poses challenges due to the disparity in sizes and shapes of
glomeruli in renal sections. Moreover, extensive variations of their
intensities due to heterogeneity in immunohistochemistry staining are also
encountered. Despite being widely recognized as a powerful descriptor for
general object detection, the rectangular histogram of oriented gradients
(Rectangular HOG) suffers from many false positives due to the aforementioned
difficulties in the context of glomerulus detection.
  A new descriptor referred to as Segmental HOG is developed to perform a
comprehensive detection of hundreds of glomeruli in images of whole kidney
sections. The new descriptor possesses flexible blocks that can be adaptively
fitted to input images to acquire robustness to deformations of glomeruli.
Moreover, the novel segmentation technique employed herewith generates high
quality segmentation outputs and the algorithm is assured to converge to an
optimal solution. Consequently, experiments using real world image data reveal
that Segmental HOG achieves significant improvements in detection performance
compared to Rectangular HOG.
  The proposed descriptor and method for glomeruli detection present promising
results and is expected to be useful in pathological evaluation.
Solving Problems with Unknown Solution Length at (Almost) No Extra Cost
Authors: Benjamin Doerr, Carola Doerr, Timo Kötzing
Date: 2015-06-19 00:00:00

Most research in the theory of evolutionary computation assumes that the
problem at hand has a fixed problem size. This assumption does not always apply
to real-world optimization challenges, where the length of an optimal solution
may be unknown a priori.
  Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we
analyze variants of the (1+1) evolutionary algorithm for problems with unknown
solution length. For their setting, in which the solution length is sampled
from a geometric distribution, we provide mutation rates that yield an expected
optimization time that is of the same order as that of the (1+1) EA knowing the
solution length.
  We then show that almost the same run times can be achieved even if \emph{no}
a priori information on the solution length is available.
  Finally, we provide mutation rates suitable for settings in which neither the
solution length nor the positions of the relevant bits are known. Again we
obtain almost optimal run times for the \textsc{OneMax} and
\textsc{LeadingOnes} test functions, thus solving an open problem from
Cathabard et al.
Deep Knowledge Tracing
Authors: Chris Piech, Jonathan Spencer, Jonathan Huang, Surya Ganguli, Mehran Sahami, Leonidas Guibas, Jascha Sohl-Dickstein
Date: 2015-06-19 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: Knowledge Tracing

Knowledge tracing---where a machine models the knowledge of a student as they
interact with coursework---is a well established problem in computer supported
education. Though effectively modeling student knowledge would have high
educational impact, the task has many inherent challenges. In this paper we
explore the utility of using Recurrent Neural Networks (RNNs) to model student
learning. The RNN family of models have important advantages over previous
methods in that they do not require the explicit encoding of human domain
knowledge, and can capture more complex representations of student knowledge.
Using neural networks results in substantial improvements in prediction
performance on a range of knowledge tracing datasets. Moreover the learned
model can be used for intelligent curriculum design and allows straightforward
interpretation and discovery of structure in student tasks. These results
suggest a promising new line of research for knowledge tracing and an exemplary
application task for RNNs.
Representation Learning for Clustering: A Statistical Framework
Authors: Hassan Ashtiani, Shai Ben-David
Date: 2015-06-19 00:00:00
Tasks: Clustering, Representation Learning

We address the problem of communicating domain knowledge from a user to the
designer of a clustering algorithm. We propose a protocol in which the user
provides a clustering of a relatively small random sample of a data set. The
algorithm designer then uses that sample to come up with a data representation
under which $k$-means clustering results in a clustering (of the full data set)
that is aligned with the user's clustering. We provide a formal statistical
model for analyzing the sample complexity of learning a clustering
representation with this paradigm. We then introduce a notion of capacity of a
class of possible representations, in the spirit of the VC-dimension, showing
that classes of representations that have finite such dimension can be
successfully learned with sample size error bounds, and end our discussion with
an analysis of that dimension for classes of representations induced by linear
embeddings.
Novel Bernstein-like Concentration Inequalities for the Missing Mass
Authors: Bahman Yari Saeed Khanloo, Gholamreza Haffari
Date: 2015-03-10 00:00:00
Tasks: Learning Theory

We are concerned with obtaining novel concentration inequalities for the
missing mass, i.e. the total probability mass of the outcomes not observed in
the sample. We not only derive - for the first time - distribution-free
Bernstein-like deviation bounds with sublinear exponents in deviation size for
missing mass, but also improve the results of McAllester and Ortiz (2003)
andBerend and Kontorovich (2013, 2012) for small deviations which is the most
interesting case in learning theory. It is known that the majority of standard
inequalities cannot be directly used to analyze heterogeneous sums i.e. sums
whose terms have large difference in magnitude. Our generic and intuitive
approach shows that the heterogeneity issue introduced in McAllester and Ortiz
(2003) is resolvable at least in the case of missing mass via regulating the
terms using our novel thresholding technique.
Strongly Adaptive Online Learning
Authors: Amit Daniely, Alon Gonen, Shai Shalev-Shwartz
Date: 2015-02-25 00:00:00

Strongly adaptive algorithms are algorithms whose performance on every time
interval is close to optimal. We present a reduction that can transform
standard low-regret algorithms to strongly adaptive. As a consequence, we
derive simple, yet efficient, strongly adaptive algorithms for a handful of
problems.
To Know Where We Are: Vision-Based Positioning in Outdoor Environments
Authors: Kuan-Wen Chen, Chun-Hsin Wang, Xiao Wei, Qiao Liang, Ming-Hsuan Yang, Chu-Song Chen, Yi-Ping Hung
Date: 2015-06-19 00:00:00
Tasks: Image Registration, Model Compression

Augmented reality (AR) displays become more and more popular recently,
because of its high intuitiveness for humans and high-quality head-mounted
display have rapidly developed. To achieve such displays with augmented
information, highly accurate image registration or ego-positioning are
required, but little attention have been paid for out-door environments. This
paper presents a method for ego-positioning in outdoor environments with low
cost monocular cameras. To reduce the computational and memory requirements as
well as the communication overheads, we formulate the model compression
algorithm as a weighted k-cover problem for better preserving model structures.
Specifically for real-world vision-based positioning applications, we consider
the issues with large scene change and propose a model update algorithm to
tackle these problems. A long- term positioning dataset with more than one
month, 106 sessions, and 14,275 images is constructed. Based on both local and
up-to-date models constructed in our approach, extensive experimental results
show that high positioning accuracy (mean ~ 30.9cm, stdev. ~ 15.4cm) can be
achieved, which outperforms existing vision-based algorithms.
Stay on path: PCA along graph paths
Authors: Megasthenis Asteris, Anastasios Kyrillidis, Alexandros G. Dimakis, Han-Gyol Yi and, Bharath Chandrasekaran
Date: 2015-06-08 00:00:00

We introduce a variant of (sparse) PCA in which the set of feasible support
sets is determined by a graph. In particular, we consider the following
setting: given a directed acyclic graph $G$ on $p$ vertices corresponding to
variables, the non-zero entries of the extracted principal component must
coincide with vertices lying along a path in $G$.
  From a statistical perspective, information on the underlying network may
potentially reduce the number of observations required to recover the
population principal component. We consider the canonical estimator which
optimally exploits the prior knowledge by solving a non-convex quadratic
maximization on the empirical covariance. We introduce a simple network and
analyze the estimator under the spiked covariance model. We show that side
information potentially improves the statistical complexity.
  We propose two algorithms to approximate the solution of the constrained
quadratic maximization, and recover a component with the desired properties. We
empirically evaluate our schemes on synthetic and real datasets.
A simple application of FIC to model selection
Authors: Paul A. Wiggins
Date: 2015-06-19 00:00:00
Tasks: Model Selection

We have recently proposed a new information-based approach to model
selection, the Frequentist Information Criterion (FIC), that reconciles
information-based and frequentist inference. The purpose of this current paper
is to provide a simple example of the application of this criterion and a
demonstration of the natural emergence of model complexities with both AIC-like
($N^0$) and BIC-like ($\log N$) scaling with observation number $N$. The
application developed is deliberately simplified to make the analysis
analytically tractable.
Smart Pacing for Effective Online Ad Campaign Optimization
Authors: Jian Xu, Kuang-Chih Lee, Wentong Li, Hang Qi, Quan Lu
Date: 2015-06-18 00:00:00

In targeted online advertising, advertisers look for maximizing campaign
performance under delivery constraint within budget schedule. Most of the
advertisers typically prefer to impose the delivery constraint to spend budget
smoothly over the time in order to reach a wider range of audiences and have a
sustainable impact. Since lots of impressions are traded through public
auctions for online advertising today, the liquidity makes price elasticity and
bid landscape between demand and supply change quite dynamically. Therefore, it
is challenging to perform smooth pacing control and maximize campaign
performance simultaneously. In this paper, we propose a smart pacing approach
in which the delivery pace of each campaign is learned from both offline and
online data to achieve smooth delivery and optimal performance goals. The
implementation of the proposed approach in a real DSP system is also presented.
Experimental evaluations on both real online ad campaigns and offline
simulations show that our approach can effectively improve campaign performance
and achieve delivery goals.
An Iterative Convolutional Neural Network Algorithm Improves Electron Microscopy Image Segmentation
Authors: Xundong Wu
Date: 2015-06-18 00:00:00
Tasks: BIG-bench Machine Learning, Electron Microscopy Image Segmentation, Image Segmentation, Segmentation, Semantic Segmentation

To build the connectomics map of the brain, we developed a new algorithm that
can automatically refine the Membrane Detection Probability Maps (MDPM)
generated to perform automatic segmentation of electron microscopy (EM) images.
To achieve this, we executed supervised training of a convolutional neural
network to recover the removed center pixel label of patches sampled from a
MDPM. MDPM can be generated from other machine learning based algorithms
recognizing whether a pixel in an image corresponds to the cell membrane. By
iteratively applying this network over MDPM for multiple rounds, we were able
to significantly improve membrane segmentation results.
Automated Assignment of Backbone NMR Data using Artificial Intelligence
Authors: John Emmons, Steven Johnson, Timothy Urness, Adina Kilpatrick
Date: 2015-06-18 00:00:00

Nuclear magnetic resonance (NMR) spectroscopy is a powerful method for the
investigation of three-dimensional structures of biological molecules such as
proteins. Determining a protein structure is essential for understanding its
function and alterations in function which lead to disease. One of the major
challenges of the post-genomic era is to obtain structural and functional
information on the many unknown proteins encoded by thousands of newly
identified genes. The goal of this research is to design an algorithm capable
of automating the analysis of backbone protein NMR data by implementing AI
strategies such as greedy and A* search.
Dependent Multinomial Models Made Easy: Stick Breaking with the Pólya-Gamma Augmentation
Authors: Scott W. Linderman, Matthew J. Johnson, Ryan P. Adams
Date: 2015-06-18 00:00:00
Tasks: Bayesian Inference, Position

Many practical modeling problems involve discrete data that are best
represented as draws from multinomial or categorical distributions. For
example, nucleotides in a DNA sequence, children's names in a given state and
year, and text documents are all commonly modeled with multinomial
distributions. In all of these cases, we expect some form of dependency between
the draws: the nucleotide at one position in the DNA strand may depend on the
preceding nucleotides, children's names are highly correlated from year to
year, and topics in text may be correlated and dynamic. These dependencies are
not naturally captured by the typical Dirichlet-multinomial formulation. Here,
we leverage a logistic stick-breaking representation and recent innovations in
P\'olya-gamma augmentation to reformulate the multinomial distribution in terms
of latent variables with jointly Gaussian likelihoods, enabling us to take
advantage of a host of Bayesian inference techniques for Gaussian models with
minimal overhead.
Cheap Bandits
Authors: Manjesh Kumar Hanawal, Venkatesh Saligrama, Michal Valko, R\' emi Munos
Date: 2015-06-15 00:00:00

We consider stochastic sequential learning problems where the learner can
observe the \textit{average reward of several actions}. Such a setting is
interesting in many applications involving monitoring and surveillance, where
the set of the actions to observe represent some (geographical) area. The
importance of this setting is that in these applications, it is actually
\textit{cheaper} to observe average reward of a group of actions rather than
the reward of a single action. We show that when the reward is \textit{smooth}
over a given graph representing the neighboring actions, we can maximize the
cumulative reward of learning while \textit{minimizing the sensing cost}. In
this paper we propose CheapUCB, an algorithm that matches the regret guarantees
of the known algorithms for this setting and at the same time guarantees a
linear cost again over them. As a by-product of our analysis, we establish a
$\Omega(\sqrt{dT})$ lower bound on the cumulative regret of spectral bandits
for a class of graphs with effective dimension $d$.
Optimal model-free prediction from multivariate time series
Authors: Jakob Runge, Reik V. Donner, Jürgen Kurths
Date: 2015-06-18 00:00:00
Tasks: Prediction, Time Series, Time Series Analysis

Forecasting a time series from multivariate predictors constitutes a
challenging problem, especially using model-free approaches. Most techniques,
such as nearest-neighbor prediction, quickly suffer from the curse of
dimensionality and overfitting for more than a few predictors which has limited
their application mostly to the univariate case. Therefore, selection
strategies are needed that harness the available information as efficiently as
possible. Since often the right combination of predictors matters, ideally all
subsets of possible predictors should be tested for their predictive power, but
the exponentially growing number of combinations makes such an approach
computationally prohibitive. Here a prediction scheme that overcomes this
strong limitation is introduced utilizing a causal pre-selection step which
drastically reduces the number of possible predictors to the most predictive
set of causal drivers making a globally optimal search scheme tractable. The
information-theoretic optimality is derived and practical selection criteria
are discussed. As demonstrated for multivariate nonlinear stochastic delay
processes, the optimal scheme can even be less computationally expensive than
commonly used sub-optimal schemes like forward selection. The method suggests a
general framework to apply the optimal model-free approach to select variables
and subsequently fit a model to further improve a prediction or learn
statistical dependencies. The performance of this framework is illustrated on a
climatological index of El Ni\~no Southern Oscillation.