pwc-archive/papers-with-abstracts huggingface dataset:
Parent Oriented Teacher Selection Causes Language Diversity
Authors: Ibrahim Cimentepe, Haluk O. Bingol
Date: 2017-02-20 00:00:00
Tasks: Diversity

An evolutionary model for emergence of diversity in language is developed. We
investigated the effects of two real life observations, namely, people prefer
people that they communicate with well, and people interact with people that
are physically close to each other. Clearly these groups are relatively small
compared to the entire population. We restrict selection of the teachers from
such small groups, called imitation sets, around parents. Then the child learns
language from a teacher selected within the imitation set of her parent. As a
result, there are subcommunities with their own languages developed. Within
subcommunity comprehension is found to be high. The number of languages is
related to the relative size of imitation set by a power law.
Replicator Equation: Applications Revisited
Authors: Tinsae G. Dulecha
Date: 2017-04-16 00:00:00
Tasks: BIG-bench Machine Learning

The replicator equation is a simple model of evolution that leads to stable
form of Nash Equilibrium, Evolutionary Stable Strategy (ESS). It has been
studied in connection with Evolutionary Game Theory and was originally
developed for symmetric games. Beyond its first emphasis in biological use,
evolutionary game theory has been expanded well beyond in social studies for
behavioral analysis, in machine learning, computer vision and others. Its
several applications in the fields of machine learning and computer vision has
drawn my attention which is the reason to write this extended abstract
Critical Contours: An Invariant Linking Image Flow with Salient Surface Organization
Authors: Benjamin S. Kunsberg, Steven W. Zucker
Date: 2017-05-20 00:00:00

We exploit a key result from visual psychophysics---that individuals perceive
shape qualitatively---to develop the use of a geometrical/topological
"invariant'' (the Morse--Smale complex) relating image structure with surface
structure. Differences across individuals are minimal near certain
configurations such as ridges and boundaries, and it is these configurations
that are often represented in line drawings. In particular, we introduce a
method for inferring a qualitative three-dimensional shape from shading
patterns that link the shape-from-shading inference with shape-from-contour
inference. For a given shape, certain shading patches approach "line drawings''
in a well-defined limit. Under this limit, and invariably with respect to
rendering choices, these shading patterns provide a qualitative description of
the surface. We further show that, under this model, the contours partition the
surface into meaningful parts using the Morse--Smale complex. These critical
contours are the (perceptually) stable parts of this complex and are invariant
over a wide class of rendering models. Intuitively, our main result shows that
critical contours partition smooth surfaces into bumps and valleys, in effect
providing a scaffold on the image from which a full surface can be
interpolated.
Formalized Lambek Calculus in Higher Order Logic (HOL4)
Authors: Chun Tian
Date: 2017-05-20 00:00:00

In this project, a rather complete proof-theoretical formalization of Lambek
Calculus (non-associative with arbitrary extensions) has been ported from Coq
proof assistent to HOL4 theorem prover, with some improvements and new
theorems.
  Three deduction systems (Syntactic Calculus, Natural Deduction and Sequent
Calculus) of Lambek Calculus are defined with many related theorems proved. The
equivalance between these systems are formally proved. Finally, a formalization
of Sequent Calculus proofs (where Coq has built-in supports) has been designed
and implemented in HOL4. Some basic results including the sub-formula
properties of the so-called "cut-free" proofs are formally proved.
  This work can be considered as the preliminary work towards a language parser
based on category grammars which is not multimodal but still has ability to
support context-sensitive languages through customized extensions.
Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
Authors: Yi-Chen Chen, Mengdi Wang
Date: 2017-05-20 00:00:00

We study the computational complexity of the infinite-horizon
discounted-reward Markov Decision Problem (MDP) with a finite state space
$|\mathcal{S}|$ and a finite action space $|\mathcal{A}|$. We show that any
randomized algorithm needs a running time at least
$\Omega(|\mathcal{S}|^2|\mathcal{A}|)$ to compute an $\epsilon$-optimal policy
with high probability. We consider two variants of the MDP where the input is
given in specific data structures, including arrays of cumulative probabilities
and binary trees of transition probabilities. For these cases, we show that the
complexity lower bound reduces to $\Omega\left( \frac{|\mathcal{S}|
|\mathcal{A}|}{\epsilon} \right)$. These results reveal a surprising
observation that the computational complexity of the MDP depends on the data
structure of input.
Representation learning of drug and disease terms for drug repositioning
Authors: Sahil Manchanda, Ashish Anand
Date: 2017-05-15 00:00:00
Tasks: Articles, Matrix Completion, Representation Learning

Drug repositioning (DR) refers to identification of novel indications for the
approved drugs. The requirement of huge investment of time as well as money and
risk of failure in clinical trials have led to surge in interest in drug
repositioning. DR exploits two major aspects associated with drugs and
diseases: existence of similarity among drugs and among diseases due to their
shared involved genes or pathways or common biological effects. Existing
methods of identifying drug-disease association majorly rely on the information
available in the structured databases only. On the other hand, abundant
information available in form of free texts in biomedical research articles are
not being fully exploited. Word-embedding or obtaining vector representation of
words from a large corpora of free texts using neural network methods have been
shown to give significant performance for several natural language processing
tasks. In this work we propose a novel way of representation learning to obtain
features of drugs and diseases by combining complementary information available
in unstructured texts and structured datasets. Next we use matrix completion
approach on these feature vectors to learn projection matrix between drug and
disease vector spaces. The proposed method has shown competitive performance
with state-of-the-art methods. Further, the case studies on Alzheimer's and
Hypertension diseases have shown that the predicted associations are matching
with the existing knowledge.
Deep Sparse Coding Using Optimized Linear Expansion of Thresholds
Authors: Debabrata Mahapatra, Subhadip Mukherjee, Chandra Sekhar Seelamantula
Date: 2017-05-20 00:00:00
Tasks: Denoising, Image Denoising

We address the problem of reconstructing sparse signals from noisy and
compressive measurements using a feed-forward deep neural network (DNN) with an
architecture motivated by the iterative shrinkage-thresholding algorithm
(ISTA). We maintain the weights and biases of the network links as prescribed
by ISTA and model the nonlinear activation function using a linear expansion of
thresholds (LET), which has been very successful in image denoising and
deconvolution. The optimal set of coefficients of the parametrized activation
is learned over a training dataset containing measurement-sparse signal pairs,
corresponding to a fixed sensing matrix. For training, we develop an efficient
second-order algorithm, which requires only matrix-vector product computations
in every training epoch (Hessian-free optimization) and offers superior
convergence performance than gradient-descent optimization. Subsequently, we
derive an improved network architecture inspired by FISTA, a faster version of
ISTA, to achieve similar signal estimation performance with about 50% of the
number of layers. The resulting architecture turns out to be a deep residual
network, which has recently been shown to exhibit superior performance in
several visual recognition tasks. Numerical experiments demonstrate that the
proposed DNN architectures lead to 3 to 4 dB improvement in the reconstruction
signal-to-noise ratio (SNR), compared with the state-of-the-art sparse coding
algorithms.
Demystifying ResNet
Authors: Sihan Li, Jiantao Jiao, Yanjun Han, Tsachy Weissman
Date: 2016-11-03 00:00:00

The Residual Network (ResNet), proposed in He et al. (2015), utilized
shortcut connections to significantly reduce the difficulty of training, which
resulted in great performance boosts in terms of both training and
generalization error.
  It was empirically observed in He et al. (2015) that stacking more layers of
residual blocks with shortcut 2 results in smaller training error, while it is
not true for shortcut of length 1 or 3. We provide a theoretical explanation
for the uniqueness of shortcut 2.
  We show that with or without nonlinearities, by adding shortcuts that have
depth two, the condition number of the Hessian of the loss function at the zero
initial point is depth-invariant, which makes training very deep models no more
difficult than shallow ones. Shortcuts of higher depth result in an extremely
flat (high-order) stationary point initially, from which the optimization
algorithm is hard to escape. The shortcut 1, however, is essentially equivalent
to no shortcuts, which has a condition number exploding to infinity as the
number of layers grows. We further argue that as the number of layers tends to
infinity, it suffices to only look at the loss function at the zero initial
point.
  Extensive experiments are provided accompanying our theoretical results. We
show that initializing the network to small weights with shortcut 2 achieves
significantly better results than random Gaussian (Xavier) initialization,
orthogonal initialization, and shortcuts of deeper depth, from various
perspectives ranging from final loss, learning dynamics and stability, to the
behavior of the Hessian along the learning process.
Kernel-based Reconstruction of Space-time Functions on Dynamic Graphs
Authors: Daniel Romero, Vassilis N. Ioannidis, Georgios B. Giannakis
Date: 2016-12-12 00:00:00
Tasks: Sociology

Graph-based methods pervade the inference toolkits of numerous disciplines
including sociology, biology, neuroscience, physics, chemistry, and
engineering. A challenging problem encountered in this context pertains to
determining the attributes of a set of vertices given those of another subset
at possibly different time instants. Leveraging spatiotemporal dynamics can
drastically reduce the number of observed vertices, and hence the cost of
sampling. Alleviating the limited flexibility of existing approaches, the
present paper broadens the existing kernel-based graph function reconstruction
framework to accommodate time-evolving functions over possibly time-evolving
topologies. This approach inherits the versatility and generality of
kernel-based methods, for which no knowledge on distributions or second-order
statistics is required. Systematic guidelines are provided to construct two
families of space-time kernels with complementary strengths. The first
facilitates judicious control of regularization on a space-time frequency
plane, whereas the second can afford time-varying topologies. Batch and online
estimators are also put forth, and a novel kernel Kalman filter is developed to
obtain these estimates at affordable computational cost. Numerical tests with
real data sets corroborate the merits of the proposed methods relative to
competing alternatives.
Topic modeling of public repositories at scale using names in source code
Authors: Vadim Markovtsev, Eiso Kant
Date: 2017-04-01 00:00:00

Programming languages themselves have a limited number of reserved keywords
and character based tokens that define the language specification. However,
programmers have a rich use of natural language within their code through
comments, text literals and naming entities. The programmer defined names that
can be found in source code are a rich source of information to build a high
level understanding of the project. The goal of this paper is to apply topic
modeling to names used in over 13.6 million repositories and perceive the
inferred topics. One of the problems in such a study is the occurrence of
duplicate repositories not officially marked as forks (obscure forks). We show
how to address it using the same identifiers which are extracted for topic
modeling.
  We open with a discussion on naming in source code, we then elaborate on our
approach to remove exact duplicate and fuzzy duplicate repositories using
Locality Sensitive Hashing on the bag-of-words model and then discuss our work
on topic modeling; and finally present the results from our data analysis
together with open-access to the source code, tools and datasets.
Non-Linear Phase-Shifting of Haar Wavelets for Run-Time All-Frequency Lighting
Authors: Mais Alnasser, Hassan Foroosh
Date: 2017-05-20 00:00:00
Tasks: All

This paper focuses on real-time all-frequency image-based rendering using an
innovative solution for run-time computation of light transport. The approach
is based on new results derived for non-linear phase shifting in the Haar
wavelet domain. Although image-based methods for real-time rendering of dynamic
glossy objects have been proposed, they do not truly scale to all possible
frequencies and high sampling rates without trading storage, glossiness, or
computational time, while varying both lighting and viewpoint. This is due to
the fact that current approaches are limited to precomputed radiance transfer
(PRT), which is prohibitively expensive in terms of memory requirements and
real-time rendering when both varying light and viewpoint changes are required
together with high sampling rates for high frequency lighting of glossy
material. On the other hand, current methods cannot handle object rotation,
which is one of the paramount issues for all PRT methods using wavelets. This
latter problem arises because the precomputed data are defined in a global
coordinate system and encoded in the wavelet domain, while the object is
rotated in a local coordinate system. At the root of all the above problems is
the lack of efficient run-time solution to the nontrivial problem of rotating
wavelets (a non-linear phase-shift), which we solve in this paper.
Learning to Factor Policies and Action-Value Functions: Factored Action Space Representations for Deep Reinforcement learning
Authors: Sahil Sharma, Aravind Suresh, Rahul Ramesh, Balaraman Ravindran
Date: 2017-05-20 00:00:00
Tasks: Decision Making, Deep Reinforcement Learning, Q-Learning, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Deep Reinforcement Learning (DRL) methods have performed well in an
increasing numbering of high-dimensional visual decision making domains. Among
all such visual decision making problems, those with discrete action spaces
often tend to have underlying compositional structure in the said action space.
Such action spaces often contain actions such as go left, go up as well as go
diagonally up and left (which is a composition of the former two actions). The
representations of control policies in such domains have traditionally been
modeled without exploiting this inherent compositional structure in the action
spaces. We propose a new learning paradigm, Factored Action space
Representations (FAR) wherein we decompose a control policy learned using a
Deep Reinforcement Learning Algorithm into independent components, analogous to
decomposing a vector in terms of some orthogonal basis vectors. This
architectural modification of the control policy representation allows the
agent to learn about multiple actions simultaneously, while executing only one
of them. We demonstrate that FAR yields considerable improvements on top of two
DRL algorithms in Atari 2600: FARA3C outperforms A3C (Asynchronous Advantage
Actor Critic) in 9 out of 14 tasks and FARAQL outperforms AQL (Asynchronous
n-step Q-Learning) in 9 out of 13 tasks.
Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
Authors: Lam M. Nguyen, Jie Liu, Katya Scheinberg, Martin Takáč
Date: 2017-05-20 00:00:00

In this paper, we study and analyze the mini-batch version of StochAstic
Recursive grAdient algoritHm (SARAH), a method employing the stochastic
recursive gradient, for solving empirical loss minimization for the case of
nonconvex losses. We provide a sublinear convergence rate (to stationary
points) for general nonconvex functions and a linear convergence rate for
gradient dominated functions, both of which have some advantages compared to
other modern stochastic gradient algorithms for nonconvex losses.
Learning Feature Nonlinearities with Non-Convex Regularized Binned Regression
Authors: Samet Oymak, Mehrdad Mahdavi, Jiasi Chen
Date: 2017-05-20 00:00:00
Tasks: regression

For various applications, the relations between the dependent and independent
variables are highly nonlinear. Consequently, for large scale complex problems,
neural networks and regression trees are commonly preferred over linear models
such as Lasso. This work proposes learning the feature nonlinearities by
binning feature values and finding the best fit in each quantile using
non-convex regularized linear regression. The algorithm first captures the
dependence between neighboring quantiles by enforcing smoothness via
piecewise-constant/linear approximation and then selects a sparse subset of
good features. We prove that the proposed algorithm is statistically and
computationally efficient. In particular, it achieves linear rate of
convergence while requiring near-minimal number of samples. Evaluations on
synthetic and real datasets demonstrate that algorithm is competitive with
current state-of-the-art and accurately learns feature nonlinearities. Finally,
we explore an interesting connection between the binning stage of our algorithm
and sparse Johnson-Lindenstrauss matrices.
Divergent discourse between protests and counter-protests: #BlackLivesMatter and #AllLivesMatter
Authors: Ryan J. Gallagher, Andrew J. Reagan, Christopher M. Danforth, Peter Sheridan Dodds
Date: 2016-06-22 00:00:00

Since the shooting of Black teenager Michael Brown by White police officer
Darren Wilson in Ferguson, Missouri, the protest hashtag #BlackLivesMatter has
amplified critiques of extrajudicial killings of Black Americans. In response
to #BlackLivesMatter, other Twitter users have adopted #AllLivesMatter, a
counter-protest hashtag whose content argues that equal attention should be
given to all lives regardless of race. Through a multi-level analysis of over
860,000 tweets, we study how these protests and counter-protests diverge by
quantifying aspects of their discourse. We find that #AllLivesMatter
facilitates opposition between #BlackLivesMatter and hashtags such as
#PoliceLivesMatter and #BlueLivesMatter in such a way that historically echoes
the tension between Black protesters and law enforcement. In addition, we show
that a significant portion of #AllLivesMatter use stems from hijacking by
#BlackLivesMatter advocates. Beyond simply injecting #AllLivesMatter with
#BlackLivesMatter content, these hijackers use the hashtag to directly confront
the counter-protest notion of "All lives matter." Our findings suggest that
Black Lives Matter movement was able to grow, exhibit diverse conversations,
and avoid derailment on social media by making discussion of counter-protest
opinions a central topic of #AllLivesMatter, rather than the movement itself.
End-to-end Planning of Fixed Millimeter-Wave Networks
Authors: Tim Danford, Onur Filiz, Jing Huang, Brian Karrer, Manohar Paluri, Guan Pang, Vish Ponnampalam, Nicolas Stier-Moses, Birce Tezel
Date: 2017-05-20 00:00:00
Tasks: Combinatorial Optimization

This article discusses a framework to support the design and end-to-end
planning of fixed millimeter-wave networks. Compared to traditional techniques,
the framework allows an organization to quickly plan a deployment in a
cost-effective way. We start by using LiDAR data---basically, a 3D point cloud
captured from a city---to estimate potential sites to deploy antennas and
whether there is line-of-sight between them. With that data on hand, we use
combinatorial optimization techniques to determine the optimal set of locations
and how they should communicate with each other, to satisfy engineering (e.g.,
latency, polarity), design (e.g., reliability) and financial (e.g., total cost
of operation) constraints. The primary goal is to connect as many people as
possible to the network. Our methodology can be used for strategic planning
when an organization is in the process of deciding whether to adopt a
millimeter-wave technology or choosing between locations, or for operational
planning when conducting a detailed design of the actual network to be deployed
in a selected location.
An Investigation of Newton-Sketch and Subsampled Newton Methods
Authors: Albert S. Berahas, Raghu Bollapragada, Jorge Nocedal
Date: 2017-05-17 00:00:00
Tasks: Dimensionality Reduction

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.
RankPL: A Qualitative Probabilistic Programming Language
Authors: Tjitze Rienstra
Date: 2017-05-19 00:00:00
Tasks: Causal Inference, Probabilistic Programming

In this paper we introduce RankPL, a modeling language that can be thought of
as a qualitative variant of a probabilistic programming language with a
semantics based on Spohn's ranking theory. Broadly speaking, RankPL can be used
to represent and reason about processes that exhibit uncertainty expressible by
distinguishing "normal" from" surprising" events. RankPL allows (iterated)
revision of rankings over alternative program states and supports various types
of reasoning, including abduction and causal inference. We present the
language, its denotational semantics, and a number of practical examples. We
also discuss an implementation of RankPL that is available for download.