pwc-archive/papers-with-abstracts huggingface dataset:
Self Organizing Maps Whose Topologies Can Be Learned With Adaptive Binary Search Trees Using Conditional Rotations
Authors: César A. Astudillo, B. John Oommen
Date: 2015-06-09 00:00:00

Numerous variants of Self-Organizing Maps (SOMs) have been proposed in the
literature, including those which also possess an underlying structure, and in
some cases, this structure itself can be defined by the user Although the
concepts of growing the SOM and updating it have been studied, the whole issue
of using a self-organizing Adaptive Data Structure (ADS) to further enhance the
properties of the underlying SOM, has been unexplored. In an earlier work, we
impose an arbitrary, user-defined, tree-like topology onto the codebooks, which
consequently enforced a neighborhood phenomenon and the so-called tree-based
Bubble of Activity. In this paper, we consider how the underlying tree itself
can be rendered dynamic and adaptively transformed. To do this, we present
methods by which a SOM with an underlying Binary Search Tree (BST) structure
can be adaptively re-structured using Conditional Rotations (CONROT). These
rotations on the nodes of the tree are local, can be done in constant time, and
performed so as to decrease the Weighted Path Length (WPL) of the entire tree.
In doing this, we introduce the pioneering concept referred to as Neural
Promotion, where neurons gain prominence in the Neural Network (NN) as their
significance increases. We are not aware of any research which deals with the
issue of Neural Promotion. The advantages of such a scheme is that the user
need not be aware of any of the topological peculiarities of the stochastic
data distribution. Rather, the algorithm, referred to as the TTOSOM with
Conditional Rotations (TTOCONROT), converges in such a manner that the neurons
are ultimately placed in the input space so as to represent its stochastic
distribution, and additionally, the neighborhood properties of the neurons suit
the best BST that represents the data. These properties have been confirmed by
our experimental results on a variety of data sets.
Empirical Studies on Symbolic Aggregation Approximation Under Statistical Perspectives for Knowledge Discovery in Time Series
Authors: Wei Song, Zhiguang Wang, Yangdong Ye, Ming Fan
Date: 2015-06-08 00:00:00
Tasks: Time Series, Time Series Analysis

Symbolic Aggregation approXimation (SAX) has been the de facto standard
representation methods for knowledge discovery in time series on a number of
tasks and applications. So far, very little work has been done in empirically
investigating the intrinsic properties and statistical mechanics in SAX words.
In this paper, we applied several statistical measurements and proposed a new
statistical measurement, i.e. information embedding cost (IEC) to analyze the
statistical behaviors of the symbolic dynamics. Our experiments on the
benchmark datasets and the clinical signals demonstrate that SAX can always
reduce the complexity while preserving the core information embedded in the
original time series with significant embedding efficiency. Our proposed IEC
score provide a priori to determine if SAX is adequate for specific dataset,
which can be generalized to evaluate other symbolic representations. Our work
provides an analytical framework with several statistical tools to analyze,
evaluate and further improve the symbolic dynamics for knowledge discovery in
time series.
Non-parametric Revenue Optimization for Generalized Second Price Auctions
Authors: Mehryar Mohri, Andres Munoz Medina
Date: 2015-06-08 00:00:00
Tasks: Density Estimation

We present an extensive analysis of the key problem of learning optimal
reserve prices for generalized second price auctions. We describe two
algorithms for this task: one based on density estimation, and a novel
algorithm benefiting from solid theoretical guarantees and with a very
favorable running-time complexity of $O(n S \log (n S))$, where $n$ is the
sample size and $S$ the number of slots. Our theoretical guarantees are more
favorable than those previously presented in the literature. Additionally, we
show that even if bidders do not play at an equilibrium, our second algorithm
is still well defined and minimizes a quantity of interest. To our knowledge,
this is the first attempt to apply learning algorithms to the problem of
reserve price optimization in GSP auctions. Finally, we present the first
convergence analysis of empirical equilibrium bidding functions to the unique
symmetric Bayesian-Nash equilibrium of a GSP.
Population Empirical Bayes
Authors: Alp Kucukelbir, David M. Blei
Date: 2014-11-02 00:00:00
Tasks: Bayesian Inference, regression, Variational Inference

Bayesian predictive inference analyzes a dataset to make predictions about
new observations. When a model does not match the data, predictive accuracy
suffers. We develop population empirical Bayes (POP-EB), a hierarchical
framework that explicitly models the empirical population distribution as part
of Bayesian analysis. We introduce a new concept, the latent dataset, as a
hierarchical variable and set the empirical population as its prior. This leads
to a new predictive density that mitigates model mismatch. We efficiently apply
this method to complex models by proposing a stochastic variational inference
algorithm, called bumping variational inference (BUMP-VI). We demonstrate
improved predictive accuracy over classical Bayesian inference in three models:
a linear regression model of health data, a Bayesian mixture model of natural
images, and a latent Dirichlet allocation topic model of scientific documents.
A CMOS Spiking Neuron for Dense Memristor-Synapse Connectivity for Brain-Inspired Computing
Authors: Xinyu Wu, Vishal Saxena, Kehan Zhu
Date: 2015-06-02 00:00:00

Neuromorphic systems that densely integrate CMOS spiking neurons and
nano-scale memristor synapses open a new avenue of brain-inspired computing.
Existing silicon neurons have molded neural biophysical dynamics but are
incompatible with memristor synapses, or used extra training circuitry thus
eliminating much of the density advantages gained by using memristors, or were
energy inefficient. Here we describe a novel CMOS spiking leaky
integrate-and-fire neuron circuit. Building on a reconfigurable architecture
with a single opamp, the described neuron accommodates a large number of
memristor synapses, and enables online spike timing dependent plasticity (STDP)
learning with optimized power consumption. Simulation results of an 180nm CMOS
design showed 97% power efficiency metric when realizing STDP learning in
10,000 memristor synapses with a nominal 1M{\Omega} memristance, and only
13{\mu}A current consumption when integrating input spikes. Therefore, the
described CMOS neuron contributes a generalized building block for large-scale
brain-inspired neuromorphic systems.
Homogeneous Spiking Neuromorphic System for Real-World Pattern Recognition
Authors: Xinyu Wu, Vishal Saxena, Kehan Zhu
Date: 2015-06-02 00:00:00

A neuromorphic chip that combines CMOS analog spiking neurons and memristive
synapses offers a promising solution to brain-inspired computing, as it can
provide massive neural network parallelism and density. Previous hybrid analog
CMOS-memristor approaches required extensive CMOS circuitry for training, and
thus eliminated most of the density advantages gained by the adoption of
memristor synapses. Further, they used different waveforms for pre and
post-synaptic spikes that added undesirable circuit overhead. Here we describe
a hardware architecture that can feature a large number of memristor synapses
to learn real-world patterns. We present a versatile CMOS neuron that combines
integrate-and-fire behavior, drives passive memristors and implements
competitive learning in a compact circuit module, and enables in-situ
plasticity in the memristor synapses. We demonstrate handwritten-digits
recognition using the proposed architecture using transistor-level circuit
simulations. As the described neuromorphic architecture is homogeneous, it
realizes a fundamental building block for large-scale energy-efficient
brain-inspired silicon chips that could lead to next-generation cognitive
computing.
Encoding Markov Logic Networks in Possibilistic Logic
Authors: Ondrej Kuzelka, Jesse Davis, Steven Schockaert
Date: 2015-06-03 00:00:00

Markov logic uses weighted formulas to compactly encode a probability
distribution over possible worlds. Despite the use of logical formulas, Markov
logic networks (MLNs) can be difficult to interpret, due to the often
counter-intuitive meaning of their weights. To address this issue, we propose a
method to construct a possibilistic logic theory that exactly captures what can
be derived from a given MLN using maximum a posteriori (MAP) inference.
Unfortunately, the size of this theory is exponential in general. We therefore
also propose two methods which can derive compact theories that still capture
MAP inference, but only for specific types of evidence. These theories can be
used, among others, to make explicit the hidden assumptions underlying an MLN
or to explain the predictions it makes.
A Topological Approach to Spectral Clustering
Authors: Antonio Rieser
Date: 2015-06-08 00:00:00
Tasks: Clustering

We propose two related unsupervised clustering algorithms which, for input, take data assumed to be sampled from a uniform distribution supported on a metric space $X$, and output a clustering of the data based on the selection of a topological model for the connected components of $X$. Both algorithms work by selecting a graph on the samples from a natural one-parameter family of graphs, using a geometric criterion in the first case and an information theoretic criterion in the second. The estimated connected components of $X$ are identified with the kernel of the associated graph Laplacian, which allows the algorithm to work without requiring the number of expected clusters or other auxiliary data as input.
On Symmetric and Asymmetric LSHs for Inner Product Search
Authors: Behnam Neyshabur, Nathan Srebro
Date: 2014-10-21 00:00:00

We consider the problem of designing locality sensitive hashes (LSH) for
inner product similarity, and of the power of asymmetric hashes in this
context. Shrivastava and Li argue that there is no symmetric LSH for the
problem and propose an asymmetric LSH based on different mappings for query and
database points. However, we show there does exist a simple symmetric LSH that
enjoys stronger guarantees and better empirical performance than the asymmetric
LSH they suggest. We also show a variant of the settings where asymmetry is
in-fact needed, but there a different asymmetric LSH is required.
An Information-Theoretic Analysis of Thompson Sampling
Authors: Daniel Russo, Benjamin Van Roy
Date: 2014-03-21 00:00:00
Tasks: Thompson Sampling

We provide an information-theoretic analysis of Thompson sampling that
applies across a broad range of online optimization problems in which a
decision-maker must learn from partial feedback. This analysis inherits the
simplicity and elegance of information theory and leads to regret bounds that
scale with the entropy of the optimal-action distribution. This strengthens
preexisting results and yields new insight into how information improves
performance.
Path-SGD: Path-Normalized Optimization in Deep Neural Networks
Authors: Behnam Neyshabur, Ruslan Salakhutdinov, Nathan Srebro
Date: 2015-06-08 00:00:00
Proceeding: NeurIPS 2015 12

We revisit the choice of SGD for training deep neural networks by
reconsidering the appropriate geometry in which to optimize the weights. We
argue for a geometry invariant to rescaling of weights that does not affect the
output of the network, and suggest Path-SGD, which is an approximate steepest
descent method with respect to a path-wise regularizer related to max-norm
regularization. Path-SGD is easy and efficient to implement and leads to
empirical gains over SGD and AdaGrad.
Optimal Sparse Kernel Learning for Hyperspectral Anomaly Detection
Authors: Zhimin Peng, Prudhvi Gurram, Heesung Kwon, Wotao Yin
Date: 2015-06-08 00:00:00
Tasks: Anomaly Detection, feature selection

In this paper, a novel framework of sparse kernel learning for Support Vector
Data Description (SVDD) based anomaly detection is presented. In this work,
optimal sparse feature selection for anomaly detection is first modeled as a
Mixed Integer Programming (MIP) problem. Due to the prohibitively high
computational complexity of the MIP, it is relaxed into a Quadratically
Constrained Linear Programming (QCLP) problem. The QCLP problem can then be
practically solved by using an iterative optimization method, in which multiple
subsets of features are iteratively found as opposed to a single subset. The
QCLP-based iterative optimization problem is solved in a finite space called
the \emph{Empirical Kernel Feature Space} (EKFS) instead of in the input space
or \emph{Reproducing Kernel Hilbert Space} (RKHS). This is possible because of
the fact that the geometrical properties of the EKFS and the corresponding RKHS
remain the same. Now, an explicit nonlinear exploitation of the data in a
finite EKFS is achievable, which results in optimal feature ranking.
Experimental results based on a hyperspectral image show that the proposed
method can provide improved performance over the current state-of-the-art
techniques.
On SAT Models Enumeration in Itemset Mining
Authors: Said Jabbour, Lakhdar Sais, Yakoub Salhi
Date: 2015-06-08 00:00:00

Frequent itemset mining is an essential part of data analysis and data
mining. Recent works propose interesting SAT-based encodings for the problem of
discovering frequent itemsets. Our aim in this work is to define strategies for
adapting SAT solvers to such encodings in order to improve models enumeration.
In this context, we deeply study the effects of restart, branching heuristics
and clauses learning. We then conduct an experimental evaluation on SAT-Based
itemset mining instances to show how SAT solvers can be adapted to obtain an
efficient SAT model enumerator.
License Plate Recognition System Based on Color Coding Of License Plates
Authors: Jani Biju Babjan
Date: 2015-06-08 00:00:00
Tasks: License Plate Recognition, Optical Character Recognition, Optical Character Recognition (OCR)

License Plate Recognition Systems are used to determine the license plate
number of a vehicle. The current system mainly uses Optical Character
Recognition to recognize the number plate. There are several problems to this
system. Some of them include interchanging of several letters or numbers
(letter O with digit 0), difficulty in localizing the license plate, high error
rate, use of different fonts in license plates etc. So a new system to
recognize the license plate number using color coding of license plates is
proposed in this paper. Easier localization of license plate can be done by
searching for the start or stop patters of license plates. An eight segment
display system along with traditional numbering with the first and last
segments left for start or stop patterns is proposed in this paper. Practical
applications include several areas under Internet of Things (IoT).
Faster SGD Using Sketched Conditioning
Authors: Alon Gonen, Shai Shalev-Shwartz
Date: 2015-06-08 00:00:00
Tasks: Stochastic Optimization

We propose a novel method for speeding up stochastic optimization algorithms
via sketching methods, which recently became a powerful tool for accelerating
algorithms for numerical linear algebra. We revisit the method of conditioning
for accelerating first-order methods and suggest the use of sketching methods
for constructing a cheap conditioner that attains a significant speedup with
respect to the Stochastic Gradient Descent (SGD) algorithm. While our
theoretical guarantees assume convexity, we discuss the applicability of our
method to deep neural networks, and experimentally demonstrate its merits.
Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
Authors: Chenxin Ma, Rachael Tappenden, Martin Takáč
Date: 2015-06-08 00:00:00

In this paper we generalize the framework of the feasible descent method
(FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent
method (RC-FDM) framework. We show that the famous SDCA algorithm for
optimizing the SVM dual problem, or the stochastic coordinate descent method
for the LASSO problem, fits into the framework of RC-FDM. We prove linear
convergence for both R-FDM and RC-FDM under the weak strong convexity
assumption. Moreover, we show that the duality gap converges linearly for
RC-FDM, which implies that the duality gap also converges linearly for SDCA
applied to the SVM dual problem.
Convex recovery of tensors using nuclear norm penalization
Authors: Stephane Chretien, Tianwen Wei
Date: 2015-06-08 00:00:00

The subdifferential of convex functions of the singular spectrum of real
matrices has been widely studied in matrix analysis, optimization and automatic
control theory. Convex analysis and optimization over spaces of tensors is now
gaining much interest due to its potential applications to signal processing,
statistics and engineering. The goal of this paper is to present an
applications to the problem of low rank tensor recovery based on linear random
measurement by extending the results of Tropp to the tensors setting.
Learning Mixtures of Ising Models using Pseudolikelihood
Authors: Onur Dikmen
Date: 2015-06-08 00:00:00

Maximum pseudolikelihood method has been among the most important methods for
learning parameters of statistical physics models, such as Ising models. In
this paper, we study how pseudolikelihood can be derived for learning
parameters of a mixture of Ising models. The performance of the proposed
approach is demonstrated for Ising and Potts models on both synthetic and real
data.
SVM and ELM: Who Wins? Object Recognition with Deep Convolutional Features from ImageNet
Authors: Lei Zhang, David Zhang
Date: 2015-06-08 00:00:00
Tasks: General Classification, image-classification, Image Classification, Object Recognition

Deep learning with a convolutional neural network (CNN) has been proved to be
very effective in feature extraction and representation of images. For image
classification problems, this work aim at finding which classifier is more
competitive based on high-level deep features of images. In this report, we
have discussed the nearest neighbor, support vector machines and extreme
learning machines for image classification under deep convolutional activation
feature representation. Specifically, we adopt the benchmark object recognition
dataset from multiple sources with domain bias for evaluating different
classifiers. The deep features of the object dataset are obtained by a
well-trained CNN with five convolutional layers and three fully-connected
layers on the challenging ImageNet. Experiments demonstrate that the ELMs
outperform SVMs in cross-domain recognition tasks. In particular,
state-of-the-art results are obtained by kernel ELM which outperforms SVMs with
about 4% of the average accuracy. The features and codes are available in
http://www.escience.cn/people/lei/index.html
Gaussian Process Optimization with Mutual Information
Authors: Emile Contal, Vianney Perchet, Nicolas Vayatis
Date: 2013-11-19 00:00:00
Tasks: Gaussian Processes, global-optimization

In this paper, we analyze a generic algorithm scheme for sequential global
optimization using Gaussian processes. The upper bounds we derive on the
cumulative regret for this generic algorithm improve by an exponential factor
the previously known bounds for algorithms like GP-UCB. We also introduce the
novel Gaussian Process Mutual Information algorithm (GP-MI), which
significantly improves further these upper bounds for the cumulative regret. We
confirm the efficiency of this algorithm on synthetic and real tasks against
the natural competitor, GP-UCB, and also the Expected Improvement heuristic.
NP-hardness of sortedness constraints
Authors: Irena Rusu
Date: 2015-06-08 00:00:00

In Constraint Programming, global constraints allow to model and solve many
combinatorial problems. Among these constraints, several sortedness constraints
have been defined, for which propagation algorithms are available, but for
which the tractability is not settled. We show that the sort(U,V) constraint
(Older et. al, 1995) is intractable for integer variables whose domains are not
limited to intervals. As a consequence, the similar result holds for the
sort(U,V, P) constraint (Zhou, 1996). Moreover, the intractability holds even
under the stability condition present in the recently introduced
keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014), and requiring that
the order of the variables with the same value in the list U be preserved in
the list V. Therefore, keysorting(U,V,Keys,P) is intractable as well.
Reflection Invariance: an important consideration of image orientation
Authors: Craig Henderson, Ebroul Izquierdo
Date: 2015-06-08 00:00:00
Tasks: General Classification, object-detection, Object Detection, Position, Scene Classification

In this position paper, we consider the state of computer vision research
with respect to invariance to the horizontal orientation of an image -- what we
term reflection invariance. We describe why we consider reflection invariance
to be an important property and provide evidence where the absence of this
invariance produces surprising inconsistencies in state-of-the-art systems. We
demonstrate inconsistencies in methods of object detection and scene
classification when they are presented with images and the horizontal mirror of
those images. Finally, we examine where some of the invariance is exhibited in
feature detection and descriptors, and make a case for future consideration of
reflection invariance as a measure of quality in computer vision algorithms.
Robust Regression via Hard Thresholding
Authors: Kush Bhatia, Prateek Jain, Purushottam Kar
Date: 2015-06-08 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: regression

We study the problem of Robust Least Squares Regression (RLSR) where several
response variables can be adversarially corrupted. More specifically, for a
data matrix X \in R^{p x n} and an underlying model w*, the response vector is
generated as y = X'w* + b where b \in R^n is the corruption vector supported
over at most C.n coordinates. Existing exact recovery results for RLSR focus
solely on L1-penalty based convex formulations and impose relatively strict
model assumptions such as requiring the corruptions b to be selected
independently of X.
  In this work, we study a simple hard-thresholding algorithm called TORRENT
which, under mild conditions on X, can recover w* exactly even if b corrupts
the response variables in an adversarial manner, i.e. both the support and
entries of b are selected adversarially after observing X and w*. Our results
hold under deterministic assumptions which are satisfied if X is sampled from
any sub-Gaussian distribution. Finally unlike existing results that apply only
to a fixed w*, generated independently of X, our results are universal and hold
for any w* \in R^p.
  Next, we propose gradient descent-based extensions of TORRENT that can scale
efficiently to large scale problems, such as high dimensional sparse recovery
and prove similar recovery guarantees for these extensions. Empirically we find
TORRENT, and more so its extensions, offering significantly faster recovery
than the state-of-the-art L1 solvers. For instance, even on moderate-sized
datasets (with p = 50K) with around 40% corrupted responses, a variant of our
proposed method called TORRENT-HYB is more than 20x faster than the best L1
solver.