pwc-archive/papers-with-abstracts huggingface dataset:
On the Expressive Power of Deep Neural Networks
Authors: Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, Jascha Sohl-Dickstein
Date: 2016-06-16 00:00:00
Proceeding: ICML 2017 8

We propose a new approach to the problem of neural network expressivity,
which seeks to characterize how structural properties of a neural network
family affect the functions it is able to compute. Our approach is based on an
interrelated set of measures of expressivity, unified by the novel notion of
trajectory length, which measures how the output of a network changes as the
input sweeps along a one-dimensional path. Our findings can be summarized as
follows:
  (1) The complexity of the computed function grows exponentially with depth.
  (2) All weights are not equal: trained networks are more sensitive to their
lower (initial) layer weights.
  (3) Regularizing on trajectory length (trajectory regularization) is a
simpler alternative to batch normalization, with the same performance.
Entropy, neutro-entropy and anti-entropy for neutrosophic information
Authors: Vasile Patrascu
Date: 2017-06-18 00:00:00

This approach presents a multi-valued representation of the neutrosophic
information. It highlights the link between the bifuzzy information and
neutrosophic one. The constructed deca-valued structure shows the neutrosophic
information complexity. This deca-valued structure led to construction of two
new concepts for the neutrosophic information: neutro-entropy and anti-entropy.
These two concepts are added to the two existing: entropy and non-entropy.
Thus, we obtained the following triad: entropy, neutro-entropy and
anti-entropy.
The impact of Entropy and Solution Density on selected SAT heuristics
Authors: Dor Cohen, Ofer Strichman
Date: 2017-06-18 00:00:00

In a recent article [Oh'15], Oh examined the impact of various key heuristics
(e.g., deletion strategy, restart policy, decay factor, database reduction) in
competitive SAT solvers. His key findings are that their expected success
depends on whether the input formula is satisfiable or not. To further
investigate these findings, we focused on two properties of satisfiable
formulas: the entropy of the formula, which approximates the freedom we have in
assigning the variables, and the solution density, which is the number of
solutions divided by the search space. We found that both predict better the
effect of these heuristics, and that satisfiable formulas with small entropy
`behave' similarly to unsatisfiable formulas.
Learning Similarity Functions for Pronunciation Variations
Authors: Einat Naaman, Yossi Adi, Joseph Keshet
Date: 2017-03-28 00:00:00
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), Binary Classification, speech-recognition, Speech Recognition

A significant source of errors in Automatic Speech Recognition (ASR) systems
is due to pronunciation variations which occur in spontaneous and
conversational speech. Usually ASR systems use a finite lexicon that provides
one or more pronunciations for each word. In this paper, we focus on learning a
similarity function between two pronunciations. The pronunciations can be the
canonical and the surface pronunciations of the same word or they can be two
surface pronunciations of different words. This task generalizes problems such
as lexical access (the problem of learning the mapping between words and their
possible pronunciations), and defining word neighborhoods. It can also be used
to dynamically increase the size of the pronunciation lexicon, or in predicting
ASR errors. We propose two methods, which are based on recurrent neural
networks, to learn the similarity function. The first is based on binary
classification, and the second is based on learning the ranking of the
pronunciations. We demonstrate the efficiency of our approach on the task of
lexical access using a subset of the Switchboard conversational speech corpus.
Results suggest that on this task our methods are superior to previous methods
which are based on graphical Bayesian methods.
Bayesian inference on random simple graphs with power law degree distributions
Authors: Juho Lee, Creighton Heaukulani, Zoubin Ghahramani, Lancelot F. James, Seungjin Choi
Date: 2017-02-27 00:00:00
Proceeding: ICML 2017 8
Tasks: Bayesian Inference

We present a model for random simple graphs with a degree distribution that
obeys a power law (i.e., is heavy-tailed). To attain this behavior, the edge
probabilities in the graph are constructed from Bertoin-Fujita-Roynette-Yor
(BFRY) random variables, which have been recently utilized in Bayesian
statistics for the construction of power law models in several applications.
Our construction readily extends to capture the structure of latent factors,
similarly to stochastic blockmodels, while maintaining its power law degree
distribution. The BFRY random variables are well approximated by gamma random
variables in a variational Bayesian inference routine, which we apply to
several network datasets for which power law degree distributions are a natural
assumption. By learning the parameters of the BFRY distribution via
probabilistic inference, we are able to automatically select the appropriate
power law behavior from the data. In order to further scale our inference
procedure, we adopt stochastic gradient ascent routines where the gradients are
computed on minibatches (i.e., subsets) of the edges in the graph.
Provably Optimal Algorithms for Generalized Linear Contextual Bandits
Authors: Lihong Li, Yu Lu, Dengyong Zhou
Date: 2017-02-28 00:00:00
Proceeding: ICML 2017 8
Tasks: Multi-Armed Bandits, News Recommendation

Contextual bandits are widely used in Internet services from news
recommendation to advertising, and to Web search. Generalized linear models
(logistical regression in particular) have demonstrated stronger performance
than linear models in many applications where rewards are binary. However, most
theoretical analyses on contextual bandits so far are on linear bandits. In
this work, we propose an upper confidence bound based algorithm for generalized
linear contextual bandits, which achieves an $\tilde{O}(\sqrt{dT})$ regret over
$T$ rounds with $d$ dimensional feature vectors. This regret matches the
minimax lower bound, up to logarithmic terms, and improves on the best previous
result by a $\sqrt{d}$ factor, assuming the number of arms is fixed. A key
component in our analysis is to establish a new, sharp finite-sample confidence
bound for maximum-likelihood estimates in generalized linear models, which may
be of independent interest. We also analyze a simpler upper confidence bound
algorithm, which is useful in practice, and prove it to have optimal regret for
certain cases.
On the Optimization Landscape of Tensor Decompositions
Authors: Rong Ge, Tengyu Ma
Date: 2017-06-18 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Tensor Decomposition

Non-convex optimization with local search heuristics has been widely used in
machine learning, achieving many state-of-art results. It becomes increasingly
important to understand why they can work for these NP-hard problems on typical
data. The landscape of many objective functions in learning has been
conjectured to have the geometric property that "all local optima are
(approximately) global optima", and thus they can be solved efficiently by
local search algorithms. However, establishing such property can be very
difficult.
  In this paper, we analyze the optimization landscape of the random
over-complete tensor decomposition problem, which has many applications in
unsupervised learning, especially in learning latent variable models. In
practice, it can be efficiently solved by gradient ascent on a non-convex
objective. We show that for any small constant $\epsilon > 0$, among the set of
points with function values $(1+\epsilon)$-factor larger than the expectation
of the function, all the local maxima are approximate global maxima.
Previously, the best-known result only characterizes the geometry in small
neighborhoods around the true components. Our result implies that even with an
initialization that is barely better than the random guess, the gradient ascent
algorithm is guaranteed to solve this problem.
  Our main technique uses Kac-Rice formula and random matrix theory. To our
best knowledge, this is the first time when Kac-Rice formula is successfully
applied to counting the number of local minima of a highly-structured random
polynomial with dependent coefficients.
Improved Variational Autoencoders for Text Modeling using Dilated Convolutions
Authors: Zichao Yang, Zhiting Hu, Ruslan Salakhutdinov, Taylor Berg-Kirkpatrick
Date: 2017-02-27 00:00:00
Proceeding: ICML 2017 8
Tasks: Decoder, Text Generation

Recent work on generative modeling of text has found that variational
auto-encoders (VAE) incorporating LSTM decoders perform worse than simpler LSTM
language models (Bowman et al., 2015). This negative result is so far poorly
understood, but has been attributed to the propensity of LSTM decoders to
ignore conditioning information from the encoder. In this paper, we experiment
with a new type of decoder for VAE: a dilated CNN. By changing the decoder's
dilation architecture, we control the effective context from previously
generated words. In experiments, we find that there is a trade off between the
contextual capacity of the decoder and the amount of encoding information used.
We show that with the right decoder, VAE can outperform LSTM language models.
We demonstrate perplexity gains on two datasets, representing the first
positive experimental result on the use VAE for generative modeling of text.
Further, we conduct an in-depth investigation of the use of VAE (with our new
decoding architecture) for semi-supervised and unsupervised labeling tasks,
demonstrating gains over several strong baselines.
Matching while Learning
Authors: Ramesh Johari, Vijay Kamble, Yash Kanoria
Date: 2016-03-15 00:00:00

We consider the problem faced by a service platform that needs to match limited supply with demand but also to learn the attributes of new users in order to match them better in the future. We introduce a benchmark model with heterogeneous "workers" (demand) and a limited supply of "jobs" that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The expected payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff. Though we use terminology inspired by labor markets, our framework applies more broadly to platforms where a limited supply of heterogeneous products is matched to users over time. Our main contribution is a complete characterization of the structure of the optimal policy in the limit that each worker performs many jobs. The platform faces a trade-off for each worker between myopically maximizing payoffs (exploitation) and learning the type of the worker (exploration). This creates a multitude of multi-armed bandit problems, one for each worker, coupled together by the constraint on availability of jobs of different types (capacity constraints). We find that the platform should estimate a shadow price for each job type, and use the payoffs adjusted by these prices, first, to determine its learning goals and then, for each worker, (i) to balance learning with payoffs during the "exploration phase," and (ii) to myopically match after it has achieved its learning goals during the "exploitation phase."
Predictive State Recurrent Neural Networks
Authors: Carlton Downey, Ahmed Hefny, Boyue Li, Byron Boots, Geoffrey Gordon
Date: 2017-05-25 00:00:00
Proceeding: NeurIPS 2017 12
Tasks: Tensor Decomposition

We present a new model, Predictive State Recurrent Neural Networks (PSRNNs),
for filtering and prediction in dynamical systems. PSRNNs draw on insights from
both Recurrent Neural Networks (RNNs) and Predictive State Representations
(PSRs), and inherit advantages from both types of models. Like many successful
RNN architectures, PSRNNs use (potentially deeply composed) bilinear transfer
functions to combine information from multiple sources. We show that such
bilinear functions arise naturally from state updates in Bayes filters like
PSRs, in which observations can be viewed as gating belief states. We also show
that PSRNNs can be learned effectively by combining Backpropogation Through
Time (BPTT) with an initialization derived from a statistically consistent
learning algorithm for PSRs called two-stage regression (2SR). Finally, we show
that PSRNNs can be factorized using tensor decomposition, reducing model size
and suggesting interesting connections to existing multiplicative architectures
such as LSTMs. We applied PSRNNs to 4 datasets, and showed that we outperform
several popular alternative approaches to modeling dynamical systems in all
cases.
Diving into the shallows: a computational perspective on large-scale shallow learning
Authors: Siyuan Ma, Mikhail Belkin
Date: 2017-03-30 00:00:00
Proceeding: NeurIPS 2017 12

In this paper we first identify a basic limitation in gradient descent-based
optimization methods when used in conjunctions with smooth kernels. An analysis
based on the spectral properties of the kernel demonstrates that only a
vanishingly small portion of the function space is reachable after a polynomial
number of gradient descent iterations. This lack of approximating power
drastically limits gradient descent for a fixed computational budget leading to
serious over-regularization/underfitting. The issue is purely algorithmic,
persisting even in the limit of infinite data.
  To address this shortcoming in practice, we introduce EigenPro iteration,
based on a preconditioning scheme using a small number of approximately
computed eigenvectors. It can also be viewed as learning a new kernel optimized
for gradient descent. It turns out that injecting this small (computationally
inexpensive and SGD-compatible) amount of approximate second-order information
leads to major improvements in convergence. For large data, this translates
into significant performance boost over the standard kernel methods. In
particular, we are able to consistently match or improve the state-of-the-art
results recently reported in the literature with a small fraction of their
computational budget.
  Finally, we feel that these results show a need for a broader computational
perspective on modern large-scale learning to complement more traditional
statistical and convergence analyses. In particular, many phenomena of
large-scale high-dimensional inference are best understood in terms of
optimization on infinite dimensional Hilbert spaces, where standard algorithms
can sometimes have properties at odds with finite-dimensional intuition. A
systematic analysis concentrating on the approximation power of such algorithms
within a budget of computation may lead to progress both in theory and
practice.
Neural Structural Correspondence Learning for Domain Adaptation
Authors: Yftah Ziser, Roi Reichart
Date: 2016-10-05 00:00:00
Proceeding: CONLL 2017 8
Tasks: Denoising, Domain Adaptation, Representation Learning, Sentiment Analysis, Sentiment Classification, Word Embeddings

Domain adaptation, adapting models from domains rich in labeled training data
to domains poor in such data, is a fundamental NLP challenge. We introduce a
neural network model that marries together ideas from two prominent strands of
research on domain adaptation through representation learning: structural
correspondence learning (SCL, (Blitzer et al., 2006)) and autoencoder neural
networks. Particularly, our model is a three-layer neural network that learns
to encode the nonpivot features of an input example into a low-dimensional
representation, so that the existence of pivot features (features that are
prominent in both domains and convey useful information for the NLP task) in
the example can be decoded from that representation. The low-dimensional
representation is then employed in a learning algorithm for the task. Moreover,
we show how to inject pre-trained word embeddings into our model in order to
improve generalization across examples with similar pivot features. On the task
of cross-domain product sentiment classification (Blitzer et al., 2007),
consisting of 12 domain pairs, our model outperforms both the SCL and the
marginalized stacked denoising autoencoder (MSDA, (Chen et al., 2012)) methods
by 3.77% and 2.17% respectively, on average across domain pairs.
Accelerating Innovation Through Analogy Mining
Authors: Tom Hope, Joel Chan, Aniket Kittur, Dafna Shahaf
Date: 2017-06-17 00:00:00
Tasks: Information Retrieval, Retrieval

The availability of large idea repositories (e.g., the U.S. patent database)
could significantly accelerate innovation and discovery by providing people
with inspiration from solutions to analogous problems. However, finding useful
analogies in these large, messy, real-world repositories remains a persistent
challenge for either human or automated methods. Previous approaches include
costly hand-created databases that have high relational structure (e.g.,
predicate calculus representations) but are very sparse. Simpler
machine-learning/information-retrieval similarity metrics can scale to large,
natural-language datasets, but struggle to account for structural similarity,
which is central to analogy. In this paper we explore the viability and value
of learning simpler structural representations, specifically, "problem
schemas", which specify the purpose of a product and the mechanisms by which it
achieves that purpose. Our approach combines crowdsourcing and recurrent neural
networks to extract purpose and mechanism vector representations from product
descriptions. We demonstrate that these learned vectors allow us to find
analogies with higher precision and recall than traditional
information-retrieval methods. In an ideation experiment, analogies retrieved
by our models significantly increased people's likelihood of generating
creative ideas compared to analogies retrieved by traditional methods. Our
results suggest a promising approach to enabling computational analogy at scale
is to learn and leverage weaker structural representations.
Group Scissor: Scaling Neuromorphic Computing Design to Large Neural Networks
Authors: Yandan Wang, Wei Wen, Beiye Liu, Donald Chiarulli, Hai Li
Date: 2017-02-11 00:00:00

Synapse crossbar is an elementary structure in Neuromorphic Computing Systems
(NCS). However, the limited size of crossbars and heavy routing congestion
impedes the NCS implementations of big neural networks. In this paper, we
propose a two-step framework (namely, group scissor) to scale NCS designs to
big neural networks. The first step is rank clipping, which integrates low-rank
approximation into the training to reduce total crossbar area. The second step
is group connection deletion, which structurally prunes connections to reduce
routing congestion between crossbars. Tested on convolutional neural networks
of LeNet on MNIST database and ConvNet on CIFAR-10 database, our experiments
show significant reduction of crossbar area and routing area in NCS designs.
Without accuracy loss, rank clipping reduces total crossbar area to 13.62\% and
51.81\% in the NCS designs of LeNet and ConvNet, respectively. Following rank
clipping, group connection deletion further reduces the routing area of LeNet
and ConvNet to 8.1\% and 52.06\%, respectively.
DeepBach: a Steerable Model for Bach Chorales Generation
Authors: Gaëtan Hadjeres, François Pachet, Frank Nielsen
Date: 2016-12-03 00:00:00
Proceeding: ICML 2017 8
Tasks: model

This paper introduces DeepBach, a graphical model aimed at modeling
polyphonic music and specifically hymn-like pieces. We claim that, after being
trained on the chorale harmonizations by Johann Sebastian Bach, our model is
capable of generating highly convincing chorales in the style of Bach.
DeepBach's strength comes from the use of pseudo-Gibbs sampling coupled with an
adapted representation of musical data. This is in contrast with many automatic
music composition approaches which tend to compose music sequentially. Our
model is also steerable in the sense that a user can constrain the generation
by imposing positional constraints such as notes, rhythms or cadences in the
generated score. We also provide a plugin on top of the MuseScore music editor
making the interaction with DeepBach easy to use.
Fatiguing STDP: Learning from Spike-Timing Codes in the Presence of Rate Codes
Authors: Timoleon Moraitis, Abu Sebastian, Irem Boybat, Manuel Le Gallo, Tomas Tuma, Evangelos Eleftheriou
Date: 2017-06-17 00:00:00

Spiking neural networks (SNNs) could play a key role in unsupervised machine
learning applications, by virtue of strengths related to learning from the fine
temporal structure of event-based signals. However, some spike-timing-related
strengths of SNNs are hindered by the sensitivity of spike-timing-dependent
plasticity (STDP) rules to input spike rates, as fine temporal correlations may
be obstructed by coarser correlations between firing rates. In this article, we
propose a spike-timing-dependent learning rule that allows a neuron to learn
from the temporally-coded information despite the presence of rate codes. Our
long-term plasticity rule makes use of short-term synaptic fatigue dynamics. We
show analytically that, in contrast to conventional STDP rules, our fatiguing
STDP (FSTDP) helps learn the temporal code, and we derive the necessary
conditions to optimize the learning process. We showcase the effectiveness of
FSTDP in learning spike-timing correlations among processes of different rates
in synthetic data. Finally, we use FSTDP to detect correlations in real-world
weather data from the United States in an experimental realization of the
algorithm that uses a neuromorphic hardware platform comprising phase-change
memristive devices. Taken together, our analyses and demonstrations suggest
that FSTDP paves the way for the exploitation of the spike-based strengths of
SNNs in real-world applications.
Coresets for Vector Summarization with Applications to Network Graphs
Authors: Dan Feldman, Sedat Ozer, Daniela Rus
Date: 2017-06-17 00:00:00
Proceeding: ICML 2017 8
Tasks: Data Summarization

We provide a deterministic data summarization algorithm that approximates the
mean $\bar{p}=\frac{1}{n}\sum_{p\in P} p$ of a set $P$ of $n$ vectors in
$\REAL^d$, by a weighted mean $\tilde{p}$ of a \emph{subset} of $O(1/\eps)$
vectors, i.e., independent of both $n$ and $d$. We prove that the squared
Euclidean distance between $\bar{p}$ and $\tilde{p}$ is at most $\eps$
multiplied by the variance of $P$. We use this algorithm to maintain an
approximated sum of vectors from an unbounded stream, using memory that is
independent of $d$, and logarithmic in the $n$ vectors seen so far. Our main
application is to extract and represent in a compact way friend groups and
activity summaries of users from underlying data exchanges. For example, in the
case of mobile networks, we can use GPS traces to identify meetings, in the
case of social networks, we can use information exchange to identify friend
groups. Our algorithm provably identifies the {\it Heavy Hitter} entries in a
proximity (adjacency) matrix. The Heavy Hitters can be used to extract and
represent in a compact way friend groups and activity summaries of users from
underlying data exchanges. We evaluate the algorithm on several large data
sets.