pwc-archive/papers-with-abstracts huggingface dataset:
Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction
Authors: Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi
Date: 2018-12-30 00:00:00

Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels $\mathcal{W}$, which can be instantiated to capture both the communication- and privacy-constrained settings and beyond. The referee uses the messages from players to solve an inference problem for the unknown distribution that generated the samples. We derive lower bounds for sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distances between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.
ORIGAMI: A Heterogeneous Split Architecture for In-Memory Acceleration of Learning
Authors: Hajar Falahati, Pejman Lotfi-Kamran, Mohammad Sadrosadati, Hamid Sarbazi-Azad
Date: 2018-12-30 00:00:00
Tasks: GPU

Memory bandwidth bottleneck is a major challenges in processing machine
learning (ML) algorithms. In-memory acceleration has potential to address this
problem; however, it needs to address two challenges. First, in-memory
accelerator should be general enough to support a large set of different ML
algorithms. Second, it should be efficient enough to utilize bandwidth while
meeting limited power and area budgets of logic layer of a 3D-stacked memory.
We observe that previous work fails to simultaneously address both challenges.
We propose ORIGAMI, a heterogeneous set of in-memory accelerators, to support
compute demands of different ML algorithms, and also uses an off-the-shelf
compute platform (e.g.,FPGA,GPU,TPU,etc.) to utilize bandwidth without
violating strict area and power budgets. ORIGAMI offers a pattern-matching
technique to identify similar computation patterns of ML algorithms and
extracts a compute engine for each pattern. These compute engines constitute
heterogeneous accelerators integrated on logic layer of a 3D-stacked memory.
Combination of these compute engines can execute any type of ML algorithms. To
utilize available bandwidth without violating area and power budgets of logic
layer, ORIGAMI comes with a computation-splitting compiler that divides an ML
algorithm between in-memory accelerators and an out-of-the-memory platform in a
balanced way and with minimum inter-communications. Combination of pattern
matching and split execution offers a new design point for acceleration of ML
algorithms. Evaluation results across 12 popular ML algorithms show that
ORIGAMI outperforms state-of-the-art accelerator with 3D-stacked memory in
terms of performance and energy-delay product (EDP) by 1.5x and 29x (up to 1.6x
and 31x), respectively. Furthermore, results are within a 1% margin of an ideal
system that has unlimited compute resources on logic layer of a 3D-stacked
memory.
ATHENA: Automated Tuning of Genomic Error Correction Algorithms using Language Models
Authors: Mustafa Abdallah, Ashraf Mahgoub, Saurabh Bagchi, Somali Chaterji
Date: 2018-12-30 00:00:00
Tasks: Language Modeling, Language Modelling

The performance of most error-correction algorithms that operate on genomic
sequencer reads is dependent on the proper choice of its configuration
parameters, such as the value of k in k-mer based techniques. In this work, we
target the problem of finding the best values of these configuration parameters
to optimize error correction. We perform this in a data-driven manner, due to
the observation that different configuration parameters are optimal for
different datasets, i.e., from different instruments and organisms. We use
language modeling techniques from the Natural Language Processing (NLP) domain
in our algorithmic suite, Athena, to automatically tune the
performance-sensitive configuration parameters. Through the use of N-Gram and
Recurrent Neural Network (RNN) language modeling, we validate the intuition
that the EC performance can be computed quantitatively and efficiently using
the perplexity metric, prevalent in NLP. After training the language model, we
show that the perplexity metric calculated for runtime data has a strong
negative correlation with the correction of the erroneous NGS reads. Therefore,
we use the perplexity metric to guide a hill climbing-based search, converging
toward the best $k$-value. Our approach is suitable for both de novo and
comparative sequencing (resequencing), eliminating the need for a reference
genome to serve as the ground truth. This is important because the use of a
reference genome often carries forward the biases along the stages of the
pipeline.
Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis
Authors: Salar Fattahi, Somayeh Sojoudi
Date: 2018-12-30 00:00:00

This work is concerned with the non-negative rank-1 robust principal component analysis (RPCA), where the goal is to recover the dominant non-negative principal components of a data matrix precisely, where a number of measurements could be grossly corrupted with sparse and arbitrary large noise. Most of the known techniques for solving the RPCA rely on convex relaxation methods by lifting the problem to a higher dimension, which significantly increase the number of variables. As an alternative, the well-known Burer-Monteiro approach can be used to cast the RPCA as a non-convex and non-smooth $\ell_1$ optimization problem with a significantly smaller number of variables. In this work, we show that the low-dimensional formulation of the symmetric and asymmetric positive rank-1 RPCA based on the Burer-Monteiro approach has benign landscape, i.e., 1) it does not have any spurious local solution, 2) has a unique global solution, and 3) its unique global solution coincides with the true components. An implication of this result is that simple local search algorithms are guaranteed to achieve a zero global optimality gap when directly applied to the low-dimensional formulation. Furthermore, we provide strong deterministic and probabilistic guarantees for the exact recovery of the true principal components. In particular, it is shown that a constant fraction of the measurements could be grossly corrupted and yet they would not create any spurious local solution.
A neural joint model for Vietnamese word segmentation, POS tagging and dependency parsing
Authors: Dat Quoc Nguyen
Date: 2018-12-30 00:00:00
Proceeding: ALTA 2019 4
Tasks: Dependency Parsing, Multi-Task Learning, Part-Of-Speech Tagging, POS, POS Tagging, Segmentation, Vietnamese Word Segmentation

We propose the first multi-task learning model for joint Vietnamese word segmentation, part-of-speech (POS) tagging and dependency parsing. In particular, our model extends the BIST graph-based dependency parser (Kiperwasser and Goldberg, 2016) with BiLSTM-CRF-based neural layers (Huang et al., 2015) for word segmentation and POS tagging. On Vietnamese benchmark datasets, experimental results show that our joint model obtains state-of-the-art or competitive performances.
Removing Malicious Nodes from Networks
Authors: Sixie Yu, Yevgeniy Vorobeychik
Date: 2018-12-30 00:00:00

A fundamental challenge in networked systems is detection and removal of suspected malicious nodes. In reality, detection is always imperfect, and the decision about which potentially malicious nodes to remove must trade off false positives (erroneously removing benign nodes) and false negatives (mistakenly failing to remove malicious nodes). However, in network settings this conventional tradeoff must now account for node connectivity. In particular, malicious nodes may exert malicious influence, so that mistakenly leaving some of these in the network may cause damage to spread. On the other hand, removing benign nodes causes direct harm to these, and indirect harm to their benign neighbors who would wish to communicate with them. We formalize the problem of removing potentially malicious nodes from a network under uncertainty through an objective that takes connectivity into account. We show that optimally solving the resulting problem is NP-Hard. We then propose a tractable solution approach based on a convex relaxation of the objective. Finally, we experimentally demonstrate that our approach significantly outperforms both a simple baseline that ignores network structure, as well as a state-of-the-art approach for a related problem, on both synthetic and real-world datasets.
Greedy Layerwise Learning Can Scale to ImageNet
Authors: Eugene Belilovsky, Michael Eickenberg, Edouard Oyallon
Date: 2018-12-29 00:00:00
Tasks: image-classification, Image Classification

Shallow supervised 1-hidden layer neural networks have a number of favorable
properties that make them easier to interpret, analyze, and optimize than their
deep counterparts, but lack their representational power. Here we use 1-hidden
layer learning problems to sequentially build deep networks layer by layer,
which can inherit properties from shallow networks. Contrary to previous
approaches using shallow networks, we focus on problems where deep learning is
reported as critical for success. We thus study CNNs on image classification
tasks using the large-scale ImageNet dataset and the CIFAR-10 dataset. Using a
simple set of ideas for architecture and training we find that solving
sequential 1-hidden-layer auxiliary problems lead to a CNN that exceeds AlexNet
performance on ImageNet. Extending this training methodology to construct
individual layers by solving 2-and-3-hidden layer auxiliary problems, we obtain
an 11-layer network that exceeds several members of the VGG model family on
ImageNet, and can train a VGG-11 model to the same accuracy as end-to-end
learning. To our knowledge, this is the first competitive alternative to
end-to-end training of CNNs that can scale to ImageNet. We illustrate several
interesting properties of these models theoretically and conduct a range of
experiments to study the properties this training induces on the intermediate
layers.
Multivariate Arrival Times with Recurrent Neural Networks for Personalized Demand Forecasting
Authors: Tianle Chen, Brian Keng, Javier Moreno
Date: 2018-12-29 00:00:00
Tasks: Demand Forecasting, Marketing, Survival Analysis

Access to a large variety of data across a massive population has made it
possible to predict customer purchase patterns and responses to marketing
campaigns. In particular, accurate demand forecasts for popular products with
frequent repeat purchases are essential since these products are one of the
main drivers of profits. However, buyer purchase patterns are extremely diverse
and sparse on a per-product level due to population heterogeneity as well as
dependence in purchase patterns across product categories. Traditional methods
in survival analysis have proven effective in dealing with censored data by
assuming parametric distributions on inter-arrival times. Distributional
parameters are then fitted, typically in a regression framework. On the other
hand, neural-network based models take a non-parametric approach to learn
relations from a larger functional class. However, the lack of distributional
assumptions make it difficult to model partially observed data. In this paper,
we model directly the inter-arrival times as well as the partially observed
information at each time step in a survival-based approach using Recurrent
Neural Networks (RNN) to model purchase times jointly over several products.
Instead of predicting a point estimate for inter-arrival times, the RNN outputs
parameters that define a distributional estimate. The loss function is the
negative log-likelihood of these parameters given partially observed data. This
approach allows one to leverage both fully observed data as well as partial
information. By externalizing the censoring problem through a log-likelihood
loss function, we show that substantial improvements over state-of-the-art
machine learning methods can be achieved. We present experimental results based
on two open datasets as well as a study on a real dataset from a large
retailer.
Brain MRI super-resolution using 3D generative adversarial networks
Authors: Irina Sanchez, Veronica Vilaplana
Date: 2018-12-29 00:00:00
Tasks: Super-Resolution

In this work we propose an adversarial learning approach to generate high
resolution MRI scans from low resolution images. The architecture, based on the
SRGAN model, adopts 3D convolutions to exploit volumetric information. For the
discriminator, the adversarial loss uses least squares in order to stabilize
the training. For the generator, the loss function is a combination of a least
squares adversarial loss and a content term based on mean square error and
image gradients in order to improve the quality of the generated images. We
explore different solutions for the upsampling phase. We present promising
results that improve classical interpolation, showing the potential of the
approach for 3D medical imaging super-resolution. Source code available at
https://github.com/imatge-upc/3D-GAN-superresolution
Training dynamically balanced excitatory-inhibitory networks
Authors: Alessandro Ingrosso, L. F. Abbott
Date: 2018-12-29 00:00:00

The construction of biologically plausible models of neural circuits is
crucial for understanding the computational properties of the nervous system.
Constructing functional networks composed of separate excitatory and inhibitory
neurons obeying Dale's law presents a number of challenges. We show how a
target-based approach, when combined with a fast online constrained
optimization technique, is capable of building functional models of rate and
spiking recurrent neural networks in which excitation and inhibition are
balanced. Balanced networks can be trained to produce complicated temporal
patterns and to solve input-output tasks while retaining biologically desirable
features such as Dale's law and response variability.
Loss Aversion in Recommender Systems: Utilizing Negative User Preference to Improve Recommendation Quality
Authors: Bibek Paudel, Sandro Luck, Abraham Bernstein
Date: 2018-12-29 00:00:00
Tasks: Link Prediction, Recommendation Systems

Negative user preference is an important context that is not sufficiently
utilized by many existing recommender systems. This context is especially
useful in scenarios where the cost of negative items is high for the users. In
this work, we describe a new recommender algorithm that explicitly models
negative user preferences in order to recommend more positive items at the top
of recommendation-lists. We build upon existing machine-learning model to
incorporate the contextual information provided by negative user preference.
With experimental evaluations on two openly available datasets, we show that
our method is able to improve recommendation quality: by improving accuracy and
at the same time reducing the number of negative items at the top of
recommendation-lists. Our work demonstrates the value of the contextual
information provided by negative feedback, and can also be extended to signed
social networks and link prediction in other networks.
Imputation and low-rank estimation with Missing Not At Random data
Authors: Aude Sportisse, Claire Boyer, Julie Josse
Date: 2018-12-29 00:00:00
Tasks: Imputation, Matrix Completion, Missing Values

Missing values challenge data analysis because many supervised and unsupervised learning methods cannot be applied directly to incomplete data. Matrix completion based on low-rank assumptions are very powerful solution for dealing with missing values. However, existing methods do not consider the case of informative missing values which are widely encountered in practice. This paper proposes matrix completion methods to recover Missing Not At Random (MNAR) data. Our first contribution is to suggest a model-based estimation strategy by modelling the missing mechanism distribution. An EM algorithm is then implemented, involving a Fast Iterative Soft-Thresholding Algorithm (FISTA). Our second contribution is to suggest a computationally efficient surrogate estimation by implicitly taking into account the joint distribution of the data and the missing mechanism: the data matrix is concatenated with the mask coding for the missing values; a low-rank structure for exponential family is assumed on this new matrix, in order to encode links between variables and missing mechanisms. The methodology that has the great advantage of handling different missing value mechanisms is robust to model specification errors.The performances of our methods are assessed on the real data collected from a trauma registry (TraumaBase ) containing clinical information about over twenty thousand severely traumatized patients in France. The aim is then to predict if the doctors should administrate tranexomic acid to patients with traumatic brain injury, that would limit excessive bleeding.
SLIM LSTMs
Authors: Fathi M. Salem
Date: 2018-12-29 00:00:00

Long Short-Term Memory (LSTM) Recurrent Neural networks (RNNs) rely on gating
signals, each driven by a function of a weighted sum of at least 3 components:
(i) one of an adaptive weight matrix multiplied by the incoming external input
vector sequence, (ii) one adaptive weight matrix multiplied by the previous
memory/state vector, and (iii) one adaptive bias vector. In effect, they
augment the simple Recurrent Neural Networks (sRNNs) structure with the
addition of a "memory cell" and the incorporation of at most 3 gating signals.
  The standard LSTM structure and components encompass redundancy and overly
increased parameterization. In this paper, we systemically introduce variants
of the LSTM RNNs, referred to as SLIM LSTMs. These variants express
aggressively reduced parameterizations to achieve computational saving and/or
speedup in (training) performance---while necessarily retaining (validation
accuracy) performance comparable to the standard LSTM RNN.
Feature Preserving and Uniformity-controllable Point Cloud Simplification on Graph
Authors: Junkun Qi, Wei Hu, Zongming Guo
Date: 2018-12-29 00:00:00
Tasks: Autonomous Driving, Point Cloud Registration

With the development of 3D sensing technologies, point clouds have attracted
increasing attention in a variety of applications for 3D object representation,
such as autonomous driving, 3D immersive tele-presence and heritage
reconstruction. However, it is challenging to process large-scale point clouds
in terms of both computation time and storage due to the tremendous amounts of
data. Hence, we propose a point cloud simplification algorithm, aiming to
strike a balance between preserving sharp features and keeping uniform density
during resampling. In particular, leveraging on graph spectral processing, we
represent irregular point clouds naturally on graphs, and propose concise
formulations of feature preservation and density uniformity based on graph
filters. The problem of point cloud simplification is finally formulated as a
trade-off between the two factors and efficiently solved by our proposed
algorithm. Experimental results demonstrate the superiority of our method, as
well as its efficient application in point cloud registration.
Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
Authors: Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, Tong Zhang
Date: 2018-12-29 00:00:00
Tasks: Adversarial Attack

Zeroth-order optimization is an important research topic in machine learning.
In recent years, it has become a key tool in black-box adversarial attack to
neural network based image classifiers. However, existing zeroth-order
optimization algorithms rarely extract second-order information of the model
function. In this paper, we utilize the second-order information of the
objective function and propose a novel \textit{Hessian-aware zeroth-order
algorithm} called \texttt{ZO-HessAware}. Our theoretical result shows that
\texttt{ZO-HessAware} has an improved zeroth-order convergence rate and query
complexity under structured Hessian approximation, where we propose a few
approximation methods for estimating Hessian. Our empirical studies on the
black-box adversarial attack problem validate that our algorithm can achieve
improved success rates with a lower query complexity.
StarAlgo: A Squad Movement Planning Library for StarCraft using Monte Carlo Tree Search and Negamax
Authors: Mykyta Viazovskyi, Michal Certicky
Date: 2018-12-29 00:00:00
Tasks: Real-Time Strategy Games, Starcraft

Real-Time Strategy (RTS) games have recently become a popular testbed for
artificial intelligence research. They represent a complex adversarial domain
providing a number of interesting AI challenges. There exists a wide variety of
research-supporting software tools, libraries and frameworks for one RTS game
in particular -- StarCraft: Brood War. These tools are designed to address
various specific sub-problems, such as resource allocation or opponent
modelling so that researchers can focus exclusively on the tasks relevant to
them. We present one such tool -- a library called StarAlgo that produces plans
for the coordinated movement of squads (groups of combat units) within the game
world. StarAlgo library can solve the squad movement planning problem using one
of two algorithms: Monte Carlo Tree Search Considering Durations (MCTSCD) and a
slightly modified version of Negamax. We evaluate both the algorithms, compare
them, and demonstrate their usage. The library is implemented as a static C++
library that can be easily plugged into most StarCraft AI bots.
EANet: Enhancing Alignment for Cross-Domain Person Re-identification
Authors: Houjing Huang, Wenjie Yang, Xiaotang Chen, Xin Zhao, Kaiqi Huang, Jinbin Lin, Guan Huang, Dalong Du
Date: 2018-12-29 00:00:00
Tasks: Domain Adaptation, Person Re-Identification

Person re-identification (ReID) has achieved significant improvement under
the single-domain setting. However, directly exploiting a model to new domains
is always faced with huge performance drop, and adapting the model to new
domains without target-domain identity labels is still challenging. In this
paper, we address cross-domain ReID and make contributions for both model
generalization and adaptation. First, we propose Part Aligned Pooling (PAP)
that brings significant improvement for cross-domain testing. Second, we design
a Part Segmentation (PS) constraint over ReID feature to enhance alignment and
improve model generalization. Finally, we show that applying our PS constraint
to unlabeled target domain images serves as effective domain adaptation. We
conduct extensive experiments between three large datasets, Market1501, CUHK03
and DukeMTMC-reID. Our model achieves state-of-the-art performance under both
source-domain and cross-domain settings. For completeness, we also demonstrate
the complementarity of our model to existing domain adaptation methods. The
code is available at https://github.com/huanghoujing/EANet.