pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Algorithms for Adversarial Contextual Learning
Authors: Vasilis Syrgkanis, Akshay Krishnamurthy, Robert E. Schapire
Date: 2016-02-08 00:00:00
Tasks: Combinatorial Optimization

We provide the first oracle efficient sublinear regret algorithms for
adversarial versions of the contextual bandit problem. In this problem, the
learner repeatedly makes an action on the basis of a context and receives
reward for the chosen action, with the goal of achieving reward competitive
with a large class of policies. We analyze two settings: i) in the transductive
setting the learner knows the set of contexts a priori, ii) in the small
separator setting, there exists a small set of contexts such that any two
policies behave differently in one of the contexts in the set. Our algorithms
fall into the follow the perturbed leader family \cite{Kalai2005} and achieve
regret $O(T^{3/4}\sqrt{K\log(N)})$ in the transductive setting and $O(T^{2/3}
d^{3/4} K\sqrt{\log(N)})$ in the separator setting, where $K$ is the number of
actions, $N$ is the number of baseline policies, and $d$ is the size of the
separator. We actually solve the more general adversarial contextual
semi-bandit linear optimization problem, whilst in the full information setting
we address the even more general contextual combinatorial optimization. We
provide several extensions and implications of our algorithms, such as
switching regret and efficient learning with predictable sequences.
Feature Representation for ICU Mortality
Authors: Harini Suresh
Date: 2015-12-16 00:00:00
Tasks: ICU Mortality, L2 Regularization

Good predictors of ICU Mortality have the potential to identify high-risk
patients earlier, improve ICU resource allocation, or create more accurate
population-level risk models. Machine learning practitioners typically make
choices about how to represent features in a particular model, but these
choices are seldom evaluated quantitatively. This study compares the
performance of different representations of clinical event data from MIMIC II
in a logistic regression model to predict 36-hour ICU mortality. The most
common representations are linear (normalized counts) and binary (yes/no).
These, along with a new representation termed "hill", are compared using both
L1 and L2 regularization. Results indicate that the introduced "hill"
representation outperforms both the binary and linear representations, the hill
representation thus has the potential to improve existing models of ICU
mortality.
Training CNNs with Low-Rank Filters for Efficient Image Classification
Authors: Yani Ioannou, Duncan Robertson, Jamie Shotton, Roberto Cipolla, Antonio Criminisi
Date: 2015-11-20 00:00:00
Tasks: Classification, General Classification, image-classification, Image Classification

We propose a new method for creating computationally efficient convolutional
neural networks (CNNs) by using low-rank representations of convolutional
filters. Rather than approximating filters in previously-trained networks with
more efficient versions, we learn a set of small basis filters from scratch;
during training, the network learns to combine these basis filters into more
complex filters that are discriminative for image classification. To train such
networks, a novel weight initialization scheme is used. This allows effective
initialization of connection weights in convolutional layers composed of groups
of differently-shaped filters. We validate our approach by applying it to
several existing CNN architectures and training these networks from scratch
using the CIFAR, ILSVRC and MIT Places datasets. Our results show similar or
higher accuracy than conventional CNNs with much less compute. Applying our
method to an improved version of VGG-11 network using global max-pooling, we
achieve comparable validation accuracy using 41% less compute and only 24% of
the original VGG-11 model parameters; another variant of our method gives a 1
percentage point increase in accuracy over our improved VGG-11 model, giving a
top-5 center-crop validation accuracy of 89.7% while reducing computation by
16% relative to the original VGG-11 model. Applying our method to the GoogLeNet
architecture for ILSVRC, we achieved comparable accuracy with 26% less compute
and 41% fewer model parameters. Applying our method to a near state-of-the-art
network for CIFAR, we achieved comparable accuracy with 46% less compute and
55% fewer parameters.
Early Inference in Energy-Based Models Approximates Back-Propagation
Authors: Yoshua Bengio, Asja Fischer
Date: 2015-10-09 00:00:00

We show that Langevin MCMC inference in an energy-based model with latent
variables has the property that the early steps of inference, starting from a
stationary point, correspond to propagating error gradients into internal
layers, similarly to back-propagation. The error that is back-propagated is
with respect to visible units that have received an outside driving force
pushing them away from the stationary point. Back-propagated error gradients
correspond to temporal derivatives of the activation of hidden units. This
observation could be an element of a theory for explaining how brains perform
credit assignment in deep hierarchies as efficiently as back-propagation does.
In this theory, the continuous-valued latent variables correspond to averaged
voltage potential (across time, spikes, and possibly neurons in the same
minicolumn), and neural computation corresponds to approximate inference and
error back-propagation at the same time.
Interpretable Selection and Visualization of Features and Interactions Using Bayesian Forests
Authors: Viktoriya Krakovna, Jiong Du, Jun S. Liu
Date: 2015-06-08 00:00:00
Tasks: feature selection, General Classification

It is becoming increasingly important for machine learning methods to make
predictions that are interpretable as well as accurate. In many practical
applications, it is of interest which features and feature interactions are
relevant to the prediction task. We present a novel method, Selective Bayesian
Forest Classifier, that strikes a balance between predictive power and
interpretability by simultaneously performing classification, feature
selection, feature interaction detection and visualization. It builds
parsimonious yet flexible models using tree-structured Bayesian networks, and
samples an ensemble of such models using Markov chain Monte Carlo. We build in
feature selection by dividing the trees into two groups according to their
relevance to the outcome of interest. Our method performs competitively on
classification and feature selection benchmarks in low and high dimensions, and
includes a visualization tool that provides insight into relevant features and
interactions.
Localization for Wireless Sensor Networks: A Neural Network Approach
Authors: Shiu Kumar, Ronesh Sharma, Edwin Vans
Date: 2016-02-07 00:00:00

As Wireless Sensor Networks are penetrating into the industrial domain, many
research opportunities are emerging. One such essential and challenging
application is that of node localization. A feed-forward neural network based
methodology is adopted in this paper. The Received Signal Strength Indicator
(RSSI) values of the anchor node beacons are used. The number of anchor nodes
and their configurations has an impact on the accuracy of the localization
system, which is also addressed in this paper. Five different training
algorithms are evaluated to find the training algorithm that gives the best
result. The multi-layer Perceptron (MLP) neural network model was trained using
Matlab. In order to evaluate the performance of the proposed method in real
time, the model obtained was then implemented on the Arduino microcontroller.
With four anchor nodes, an average 2D localization error of 0.2953 m has been
achieved with a 12-12-2 neural network structure. The proposed method can also
be implemented on any other embedded microcontroller system.
Train faster, generalize better: Stability of stochastic gradient descent
Authors: Moritz Hardt, Benjamin Recht, Yoram Singer
Date: 2015-09-03 00:00:00

We show that parametric models trained by a stochastic gradient method (SGM)
with few iterations have vanishing generalization error. We prove our results
by arguing that SGM is algorithmically stable in the sense of Bousquet and
Elisseeff. Our analysis only employs elementary tools from convex and
continuous optimization. We derive stability bounds for both convex and
non-convex optimization under standard Lipschitz and smoothness assumptions.
  Applying our results to the convex case, we provide new insights for why
multiple epochs of stochastic gradient methods generalize well in practice. In
the non-convex case, we give a new interpretation of common practices in neural
networks, and formally show that popular techniques for training large deep
models are indeed stability-promoting. Our findings conceptually underscore the
importance of reducing training time beyond its obvious benefit.
The Optimal Sample Complexity of PAC Learning
Authors: Steve Hanneke
Date: 2015-07-02 00:00:00
Tasks: PAC learning

This work establishes a new upper bound on the number of samples sufficient
for PAC learning in the realizable case. The bound matches known lower bounds
up to numerical constant factors. This solves a long-standing open problem on
the sample complexity of PAC learning. The technique and analysis build on a
recent breakthrough by Hans Simon.
Nonparametric Canonical Correlation Analysis
Authors: Tomer Michaeli, Weiran Wang, Karen Livescu
Date: 2015-11-16 00:00:00
Tasks: Representation Learning

Canonical correlation analysis (CCA) is a classical representation learning
technique for finding correlated variables in multi-view data. Several
nonlinear extensions of the original linear CCA have been proposed, including
kernel and deep neural network methods. These approaches seek maximally
correlated projections among families of functions, which the user specifies
(by choosing a kernel or neural network structure), and are computationally
demanding. Interestingly, the theory of nonlinear CCA, without functional
restrictions, had been studied in the population setting by Lancaster already
in the 1950s, but these results have not inspired practical algorithms. We
revisit Lancaster's theory to devise a practical algorithm for nonparametric
CCA (NCCA). Specifically, we show that the solution can be expressed in terms
of the singular value decomposition of a certain operator associated with the
joint density of the views. Thus, by estimating the population density from
data, NCCA reduces to solving an eigenvalue system, superficially like kernel
CCA but, importantly, without requiring the inversion of any kernel matrix. We
also derive a partially linear CCA (PLCCA) variant in which one of the views
undergoes a linear projection while the other is nonparametric. Using a kernel
density estimate based on a small number of nearest neighbors, our NCCA and
PLCCA algorithms are memory-efficient, often run much faster, and perform
better than kernel CCA and comparable to deep CCA.
Network Inference by Learned Node-Specific Degree Prior
Authors: Qingming Tang, Lifu Tu, Weiran Wang, Jinbo Xu
Date: 2016-02-07 00:00:00
Tasks: Matrix Completion

We propose a novel method for network inference from partially observed edges
using a node-specific degree prior. The degree prior is derived from observed
edges in the network to be inferred, and its hyper-parameters are determined by
cross validation. Then we formulate network inference as a matrix completion
problem regularized by our degree prior. Our theoretical analysis indicates
that this prior favors a network following the learned degree distribution, and
may lead to improved network recovery error bound than previous work.
Experimental results on both simulated and real biological networks demonstrate
the superior performance of our method in various settings.
Disentangled Representations in Neural Models
Authors: William Whitney
Date: 2016-02-07 00:00:00
Tasks: Representation Learning

Representation learning is the foundation for the recent success of neural
network models. However, the distributed representations generated by neural
networks are far from ideal. Due to their highly entangled nature, they are di
cult to reuse and interpret, and they do a poor job of capturing the sparsity
which is present in real- world transformations. In this paper, I describe
methods for learning disentangled representations in the two domains of
graphics and computation. These methods allow neural methods to learn
representations which are easy to interpret and reuse, yet they incur little or
no penalty to performance. In the Graphics section, I demonstrate the ability
of these methods to infer the generating parameters of images and rerender
those images under novel conditions. In the Computation section, I describe a
model which is able to factorize a multitask learning problem into subtasks and
which experiences no catastrophic forgetting. Together these techniques provide
the tools to design a wide range of models that learn disentangled
representations and better model the factors of variation in the real world.
Find an Optimal Path in Static System and Dynamical System within Polynomial Runtime
Authors: Yong Tan
Date: 2016-02-07 00:00:00

We study an ancient problem that in a static or dynamical system, sought an
optimal path, which the context always means within an extremal condition. In
fact, through those discussions about this theme, we established a universal
essential calculated model to serve for these complex systems. Meanwhile we
utilize the sample space to character the system. These contents in this paper
would involve in several major areas including the geometry, probability, graph
algorithms and some prior approaches, which stands the ultimately subtle linear
algorithm to solve this class problem. Along with our progress, our discussion
would demonstrate more general meaning and robust character, which provides
clear ideas or notion to support our concrete applications, who work in a more
popular complex system.
Learning Contextual Dependencies with Convolutional Hierarchical Recurrent Neural Networks
Authors: Zhen Zuo, Bing Shuai, Gang Wang, Xiao Liu, Xingxing Wang, Bing Wang
Date: 2015-09-13 00:00:00
Tasks: General Classification, image-classification, Image Classification

Existing deep convolutional neural networks (CNNs) have shown their great
success on image classification. CNNs mainly consist of convolutional and
pooling layers, both of which are performed on local image areas without
considering the dependencies among different image regions. However, such
dependencies are very important for generating explicit image representation.
In contrast, recurrent neural networks (RNNs) are well known for their ability
of encoding contextual information among sequential data, and they only require
a limited number of network parameters. General RNNs can hardly be directly
applied on non-sequential data. Thus, we proposed the hierarchical RNNs
(HRNNs). In HRNNs, each RNN layer focuses on modeling spatial dependencies
among image regions from the same scale but different locations. While the
cross RNN scale connections target on modeling scale dependencies among regions
from the same location but different scales. Specifically, we propose two
recurrent neural network models: 1) hierarchical simple recurrent network
(HSRN), which is fast and has low computational cost; and 2) hierarchical
long-short term memory recurrent network (HLSTM), which performs better than
HSRN with the price of more computational cost.
  In this manuscript, we integrate CNNs with HRNNs, and develop end-to-end
convolutional hierarchical recurrent neural networks (C-HRNNs). C-HRNNs not
only make use of the representation power of CNNs, but also efficiently encodes
spatial and scale dependencies among different image regions. On four of the
most challenging object/scene image classification benchmarks, our C-HRNNs
achieve state-of-the-art results on Places 205, SUN 397, MIT indoor, and
competitive results on ILSVRC 2012.
The IMP game: Learnability, approximability and adversarial learning beyond $Σ^0_1$
Authors: Michael Brand, David L. Dowe
Date: 2016-02-07 00:00:00

We introduce a problem set-up we call the Iterated Matching Pennies (IMP)
game and show that it is a powerful framework for the study of three problems:
adversarial learnability, conventional (i.e., non-adversarial) learnability and
approximability. Using it, we are able to derive the following theorems. (1) It
is possible to learn by example all of $\Sigma^0_1 \cup \Pi^0_1$ as well as
some supersets; (2) in adversarial learning (which we describe as a
pursuit-evasion game), the pursuer has a winning strategy (in other words,
$\Sigma^0_1$ can be learned adversarially, but $\Pi^0_1$ not); (3) some
languages in $\Pi^0_1$ cannot be approximated by any language in $\Sigma^0_1$.
  We show corresponding results also for $\Sigma^0_i$ and $\Pi^0_i$ for
arbitrary $i$.
Scalable Text Mining with Sparse Generative Models
Authors: Antti Puurula
Date: 2016-02-07 00:00:00
Tasks: General Classification, Retrieval, text-classification, Text Classification

The information age has brought a deluge of data. Much of this is in text
form, insurmountable in scope for humans and incomprehensible in structure for
computers. Text mining is an expanding field of research that seeks to utilize
the information contained in vast document collections. General data mining
methods based on machine learning face challenges with the scale of text data,
posing a need for scalable text mining methods.
  This thesis proposes a solution to scalable text mining: generative models
combined with sparse computation. A unifying formalization for generative text
models is defined, bringing together research traditions that have used
formally equivalent models, but ignored parallel developments. This framework
allows the use of methods developed in different processing tasks such as
retrieval and classification, yielding effective solutions across different
text mining tasks. Sparse computation using inverted indices is proposed for
inference on probabilistic models. This reduces the computational complexity of
the common text mining operations according to sparsity, yielding probabilistic
models with the scalability of modern search engines.
  The proposed combination provides sparse generative models: a solution for
text mining that is general, effective, and scalable. Extensive experimentation
on text classification and ranked retrieval datasets are conducted, showing
that the proposed solution matches or outperforms the leading task-specific
methods in effectiveness, with a order of magnitude decrease in classification
times for Wikipedia article categorization with a million classes. The
developed methods were further applied in two 2014 Kaggle data mining prize
competitions with over a hundred competing teams, earning first and second
places.
Winning Arguments: Interaction Dynamics and Persuasion Strategies in Good-faith Online Discussions
Authors: Chenhao Tan, Vlad Niculae, Cristian Danescu-Niculescu-Mizil, Lillian Lee
Date: 2016-02-02 00:00:00
Tasks: Persuasion Strategies, Persuasiveness

Changing someone's opinion is arguably one of the most important challenges
of social interaction. The underlying process proves difficult to study: it is
hard to know how someone's opinions are formed and whether and how someone's
views shift. Fortunately, ChangeMyView, an active community on Reddit, provides
a platform where users present their own opinions and reasoning, invite others
to contest them, and acknowledge when the ensuing discussions change their
original views. In this work, we study these interactions to understand the
mechanisms behind persuasion.
  We find that persuasive arguments are characterized by interesting patterns
of interaction dynamics, such as participant entry-order and degree of
back-and-forth exchange. Furthermore, by comparing similar counterarguments to
the same opinion, we show that language factors play an essential role. In
particular, the interplay between the language of the opinion holder and that
of the counterargument provides highly predictive cues of persuasiveness.
Finally, since even in this favorable setting people may not be persuaded, we
investigate the problem of determining whether someone's opinion is susceptible
to being changed at all. For this more difficult task, we show that stylistic
choices in how the opinion is expressed carry predictive power.
MPBART - Multinomial Probit Bayesian Additive Regression Trees
Authors: Bereket P. Kindo, Hao Wang, Edsel A. Peña
Date: 2013-09-30 00:00:00
Tasks: General Classification, regression

This article proposes Multinomial Probit Bayesian Additive Regression Trees
(MPBART) as a multinomial probit extension of BART - Bayesian Additive
Regression Trees (Chipman et al (2010)). MPBART is flexible to allow inclusion
of predictors that describe the observed units as well as the available choice
alternatives. Through two simulation studies and four real data examples, we
show that MPBART exhibits very good predictive performance in comparison to
other discrete choice and multiclass classification methods. To implement
MPBART, we have developed an R package mpbart available freely from CRAN
repositories.
A Deep Learning Approach to Unsupervised Ensemble Learning
Authors: Uri Shaham, Xiuyuan Cheng, Omer Dror, Ariel Jaffe, Boaz Nadler, Joseph Chang, Yuval Kluger
Date: 2016-02-06 00:00:00
Tasks: Deep Learning, Ensemble Learning

We show how deep learning methods can be applied in the context of
crowdsourcing and unsupervised ensemble learning. First, we prove that the
popular model of Dawid and Skene, which assumes that all classifiers are
conditionally independent, is {\em equivalent} to a Restricted Boltzmann
Machine (RBM) with a single hidden node. Hence, under this model, the posterior
probabilities of the true labels can be instead estimated via a trained RBM.
Next, to address the more general case, where classifiers may strongly violate
the conditional independence assumption, we propose to apply RBM-based Deep
Neural Net (DNN). Experimental results on various simulated and real-world
datasets demonstrate that our proposed DNN approach outperforms other
state-of-the-art methods, in particular when the data violates the conditional
independence assumption.
Importance Sampling for Minibatches
Authors: Dominik Csiba, Peter Richtárik
Date: 2016-02-06 00:00:00

Minibatching is a very well studied and highly popular technique in
supervised learning, used by practitioners due to its ability to accelerate
training through better utilization of parallel processing power and reduction
of stochastic variance. Another popular technique is importance sampling -- a
strategy for preferential sampling of more important examples also capable of
accelerating the training process. However, despite considerable effort by the
community in these areas, and due to the inherent technical difficulty of the
problem, there is no existing work combining the power of importance sampling
with the strength of minibatching. In this paper we propose the first {\em
importance sampling for minibatches} and give simple and rigorous complexity
analysis of its performance. We illustrate on synthetic problems that for
training data of certain properties, our sampling can lead to several orders of
magnitude improvement in training time. We then test the new sampling on
several popular datasets, and show that the improvement can reach an order of
magnitude.