pwc-archive/papers-with-abstracts huggingface dataset:
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel
Authors: Colin Wei, Jason D. Lee, Qiang Liu, Tengyu Ma
Date: 2018-10-12 00:00:00
Proceeding: NeurIPS 2019 12

Recent works have shown that on sufficiently over-parametrized neural nets, gradient descent with relatively large initialization optimizes a prediction function in the RKHS of the Neural Tangent Kernel (NTK). This analysis leads to global convergence results but does not work when there is a standard $\ell_2$ regularizer, which is useful to have in practice. We show that sample efficiency can indeed depend on the presence of the regularizer: we construct a simple distribution in d dimensions which the optimal regularized neural net learns with $O(d)$ samples but the NTK requires $\Omega(d^2)$ samples to learn. To prove this, we establish two analysis tools: i) for multi-layer feedforward ReLU nets, we show that the global minimizer of a weakly-regularized cross-entropy loss is the max normalized margin solution among all neural nets, which generalizes well; ii) we develop a new technique for proving lower bounds for kernel methods, which relies on showing that the kernel cannot focus on informative features. Motivated by our generalization results, we study whether the regularized global optimum is attainable. We prove that for infinite-width two-layer nets, noisy gradient descent optimizes the regularized neural net loss to a global minimum in polynomial iterations.
FPGA-based Acceleration System for Visual Tracking
Authors: Ke Song, Chun Yuan, Peng Gao, Yunxu Sun
Date: 2018-10-12 00:00:00
Tasks: Real-Time Visual Tracking, Visual Tracking

Visual tracking is one of the most important application areas of computer
vision. At present, most algorithms are mainly implemented on PCs, and it is
difficult to ensure real-time performance when applied in the real scenario. In
order to improve the tracking speed and reduce the overall power consumption of
visual tracking, this paper proposes a real-time visual tracking algorithm
based on DSST(Discriminative Scale Space Tracking) approach. We implement a
hardware system on Xilinx XC7K325T FPGA platform based on our proposed visual
tracking algorithm. Our hardware system can run at more than 153 frames per
second. In order to reduce the resource occupation, our system adopts the batch
processing method in the feature extraction module. In the filter processing
module, the FFT IP core is time-division multiplexed. Therefore, our hardware
system utilizes LUTs and storage blocks of 33% and 40%, respectively. Test
results show that the proposed visual tracking hardware system has excellent
performance.
Unsupervised Facial Geometry Learning for Sketch to Photo Synthesis
Authors: Hadi Kazemi, Fariborz Taherkhani, Nasser M. Nasrabadi
Date: 2018-10-12 00:00:00
Tasks: Image-to-Image Translation, Translation, Unsupervised Image-To-Image Translation

Face sketch-photo synthesis is a critical application in law enforcement and
digital entertainment industry where the goal is to learn the mapping between a
face sketch image and its corresponding photo-realistic image. However, the
limited number of paired sketch-photo training data usually prevents the
current frameworks to learn a robust mapping between the geometry of sketches
and their matching photo-realistic images. Consequently, in this work, we
present an approach for learning to synthesize a photo-realistic image from a
face sketch in an unsupervised fashion. In contrast to current unsupervised
image-to-image translation techniques, our framework leverages a novel
perceptual discriminator to learn the geometry of human face. Learning facial
prior information empowers the network to remove the geometrical artifacts in
the face sketch. We demonstrate that a simultaneous optimization of the face
photo generator network, employing the proposed perceptual discriminator in
combination with a texture-wise discriminator, results in a significant
improvement in quality and recognition rate of the synthesized photos. We
evaluate the proposed network by conducting extensive experiments on multiple
baseline sketch-photo datasets.
Efficient architecture for deep neural networks with heterogeneous sensitivity
Authors: Hyunjoong Cho, Jinhyeok Jang, Chanhyeok Lee, Seungjoon Yang
Date: 2018-10-12 00:00:00
Tasks: Facial Expression Recognition, Facial Expression Recognition (FER), object-detection, Object Detection, Object Recognition, Sensitivity

This work presents a neural network that consists of nodes with heterogeneous sensitivity. Each node in a network is assigned a variable that determines the sensitivity with which it learns to perform a given task. The network is trained by a constrained optimization that maximizes the sparsity of the sensitivity variables while ensuring the network's performance. As a result, the network learns to perform a given task using only a small number of sensitive nodes. Insensitive nodes, the nodes with zero sensitivity, can be removed from a trained network to obtain a computationally efficient network. Removing zero-sensitivity nodes has no effect on the network's performance because the network has already been trained to perform the task without them. The regularization parameter used to solve the optimization problem is found simultaneously during the training of networks. To validate our approach, we design networks with computationally efficient architectures for various tasks such as autoregression, object recognition, facial expression recognition, and object detection using various datasets. In our experiments, the networks designed by the proposed method provide the same or higher performance but with far less computational complexity.
On The Equivalence of Tries and Dendrograms - Efficient Hierarchical Clustering of Traffic Data
Authors: Chia-Tung Kuo, Ian Davidson
Date: 2018-10-12 00:00:00
Tasks: Clustering

The widespread use of GPS-enabled devices generates voluminous and continuous
amounts of traffic data but analyzing such data for interpretable and
actionable insights poses challenges. A hierarchical clustering of the trips
has many uses such as discovering shortest paths, common routes and often
traversed areas. However, hierarchical clustering typically has time complexity
of $O(n^2 \log n)$ where $n$ is the number of instances, and is difficult to
scale to large data sets associated with GPS data. Furthermore, incremental
hierarchical clustering is still a developing area. Prefix trees (also called
tries) can be efficiently constructed and updated in linear time (in $n$). We
show how a specially constructed trie can compactly store the trips and further
show this trie is equivalent to a dendrogram that would have been built by
classic agglomerative hierarchical algorithms using a specific distance metric.
This allows creating hierarchical clusterings of GPS trip data and updating
this hierarchy in linear time. %we can extract a meaningful kernel and can also
interpret the structure as clusterings of differing granularity as one
progresses down the tree. We demonstrate the usefulness of our proposed
approach on a real world data set of half a million taxis' GPS traces, well
beyond the capabilities of agglomerative clustering methods. Our work is not
limited to trip data and can be used with other data with a string
representation.
Optimal Hierarchical Learning Path Design with Reinforcement Learning
Authors: Xiao Li, Hanchen Xu, Jinming Zhang, Hua-hua Chang
Date: 2018-10-12 00:00:00
Tasks: cognitive diagnosis, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

E-learning systems are capable of providing more adaptive and efficient
learning experiences for students than the traditional classroom setting. A key
component of such systems is the learning strategy, the algorithm that designs
the learning paths for students based on information such as the students'
current progresses, their skills, learning materials, and etc. In this paper,
we address the problem of finding the optimal learning strategy for an
E-learning system. To this end, we first develop a model for students'
hierarchical skills in the E-learning system. Based on the hierarchical skill
model and the classical cognitive diagnosis model, we further develop a
framework to model various proficiency levels of hierarchical skills. The
optimal learning strategy on top of the hierarchical structure is found by
applying a model-free reinforcement learning method, which does not require
information on students' learning transition process. The effectiveness of the
proposed framework is demonstrated via numerical experiments.
4D Human Body Correspondences from Panoramic Depth Maps
Authors: Zhong Li, Minye Wu, Wangyiteng Zhou, Jingyi Yu
Date: 2018-10-12 00:00:00
Proceeding: CVPR 2018 6

The availability of affordable 3D full body reconstruction systems has given
rise to free-viewpoint video (FVV) of human shapes. Most existing solutions
produce temporally uncorrelated point clouds or meshes with unknown
point/vertex correspondences. Individually compressing each frame is
ineffective and still yields to ultra-large data sizes. We present an
end-to-end deep learning scheme to establish dense shape correspondences and
subsequently compress the data. Our approach uses sparse set of "panoramic"
depth maps or PDMs, each emulating an inward-viewing concentric mosaics. We
then develop a learning-based technique to learn pixel-wise feature descriptors
on PDMs. The results are fed into an autoencoder-based network for compression.
Comprehensive experiments demonstrate our solution is robust and effective on
both public and our newly captured datasets.
IndoSum: A New Benchmark Dataset for Indonesian Text Summarization
Authors: Kemal Kurniawan, Samuel Louvan
Date: 2018-10-12 00:00:00
Tasks: Articles, Extractive Summarization, Text Summarization

Automatic text summarization is generally considered as a challenging task in
the NLP community. One of the challenges is the publicly available and large
dataset that is relatively rare and difficult to construct. The problem is even
worse for low-resource languages such as Indonesian. In this paper, we present
IndoSum, a new benchmark dataset for Indonesian text summarization. The dataset
consists of news articles and manually constructed summaries. Notably, the
dataset is almost 200x larger than the previous Indonesian summarization
dataset of the same domain. We evaluated various extractive summarization
approaches and obtained encouraging results which demonstrate the usefulness of
the dataset and provide baselines for future research. The code and the dataset
are available online under permissive licenses.
Dynamic Channel Pruning: Feature Boosting and Suppression
Authors: Xitong Gao, Yiren Zhao, Łukasz Dudziak, Robert Mullins, Cheng-Zhong Xu
Date: 2018-10-12 00:00:00
Proceeding: ICLR 2019 5
Tasks: Model Compression, Network Pruning

Making deep convolutional neural networks more accurate typically comes at
the cost of increased computational and memory resources. In this paper, we
reduce this cost by exploiting the fact that the importance of features
computed by convolutional layers is highly input-dependent, and propose feature
boosting and suppression (FBS), a new method to predictively amplify salient
convolutional channels and skip unimportant ones at run-time. FBS introduces
small auxiliary connections to existing convolutional layers. In contrast to
channel pruning methods which permanently remove channels, it preserves the
full network structures and accelerates convolution by dynamically skipping
unimportant input and output channels. FBS-augmented networks are trained with
conventional stochastic gradient descent, making it readily available for many
state-of-the-art CNNs. We compare FBS to a range of existing channel pruning
and dynamic execution schemes and demonstrate large improvements on ImageNet
classification. Experiments show that FBS can respectively provide $5\times$
and $2\times$ savings in compute on VGG-16 and ResNet-18, both with less than
$0.6\%$ top-5 accuracy loss.
Important Attribute Identification in Knowledge Graph
Authors: Shengjie Sun, Dong Yang, Hongchun Zhang, Yanxu Chen, Chao Wei, Xiaonan Meng, Yi Hu
Date: 2018-10-12 00:00:00
Tasks: Attribute, Information Retrieval, Retrieval, Text Generation

The knowledge graph(KG) composed of entities with their descriptions and
attributes, and relationship between entities, is finding more and more
application scenarios in various natural language processing tasks. In a
typical knowledge graph like Wikidata, entities usually have a large number of
attributes, but it is difficult to know which ones are important. The
importance of attributes can be a valuable piece of information in various
applications spanning from information retrieval to natural language
generation. In this paper, we propose a general method of using external user
generated text data to evaluate the relative importance of an entity's
attributes. To be more specific, we use the word/sub-word embedding techniques
to match the external textual data back to entities' attribute name and values
and rank the attributes by their matching cohesiveness. To our best knowledge,
this is the first work of applying vector based semantic matching to important
attribute identification, and our method outperforms the previous traditional
methods. We also apply the outcome of the detected important attributes to a
language generation task; compared with previous generated text, the new method
generates much more customized and informative messages.
Learning to Reason
Authors: Brian Groenke
Date: 2018-10-12 00:00:00
Tasks: Automated Theorem Proving, Q-Learning

Automated theorem proving has long been a key task of artificial
intelligence. Proofs form the bedrock of rigorous scientific inquiry. Many
tools for both partially and fully automating their derivations have been
developed over the last half a century. Some examples of state-of-the-art
provers are E (Schulz, 2013), VAMPIRE (Kov\'acs & Voronkov, 2013), and Prover9
(McCune, 2005-2010). Newer theorem provers, such as E, use superposition
calculus in place of more traditional resolution and tableau based methods.
There have also been a number of past attempts to apply machine learning
methods to guiding proof search. Suttner & Ertel proposed a
multilayer-perceptron based method using hand-engineered features as far back
as 1990; Urban et al (2011) apply machine learning to tableau calculus; and
Loos et al (2017) recently proposed a method for guiding the E theorem prover
using deep nerual networks. All of this prior work, however, has one common
limitation: they all rely on the axioms of classical first-order logic. Very
little attention has been paid to automated theorem proving for non-classical
logics. One of the only recent examples is McLaughlin & Pfenning (2008) who
applied the polarized inverse method to intuitionistic propositional logic. The
literature is otherwise mostly silent. This is truly unfortunate, as there are
many reasons to desire non-classical proofs over classical.
Constructive/intuitionistic proofs should be of particular interest to computer
scientists thanks to the well-known Curry-Howard correspondence (Howard, 1980)
which tells us that all terminating programs correspond to a proof in
intuitionistic logic and vice versa. This work explores using Q-learning
(Watkins, 1989) to inform proof search for a specific system called
non-classical logic called Core Logic (Tennant, 2017).
Block Stability for MAP Inference
Authors: Hunter Lang, David Sontag, Aravindan Vijayaraghavan
Date: 2018-10-12 00:00:00

To understand the empirical success of approximate MAP inference, recent work (Lang et al., 2018) has shown that some popular approximation algorithms perform very well when the input instance is stable. The simplest stability condition assumes that the MAP solution does not change at all when some of the pairwise potentials are (adversarially) perturbed. Unfortunately, this strong condition does not seem to be satisfied in practice. In this paper, we introduce a significantly more relaxed condition that only requires blocks (portions) of an input instance to be stable. Under this block stability condition, we prove that the pairwise LP relaxation is persistent on the stable blocks. We complement our theoretical results with an empirical evaluation of real-world MAP inference instances from computer vision. We design an algorithm to find stable blocks, and find that these real instances have large stable regions. Our work gives a theoretical explanation for the widespread empirical phenomenon of persistency for this LP relaxation.
signSGD with Majority Vote is Communication Efficient And Fault Tolerant
Authors: Jeremy Bernstein, Jia-Wei Zhao, Kamyar Azizzadenesheli, Anima Anandkumar
Date: 2018-10-11 00:00:00
Proceeding: ICLR 2019 5
Tasks: Benchmarking

Training neural networks on large datasets can be accelerated by distributing
the workload over a network of machines. As datasets grow ever larger, networks
of hundreds or thousands of machines become economically viable. The time cost
of communicating gradients limits the effectiveness of using such large machine
counts, as may the increased chance of network faults. We explore a
particularly simple algorithm for robust, communication-efficient
learning---signSGD. Workers transmit only the sign of their gradient vector to
a server, and the overall update is decided by a majority vote. This algorithm
uses $32\times$ less communication per iteration than full-precision,
distributed SGD. Under natural conditions verified by experiment, we prove that
signSGD converges in the large and mini-batch settings, establishing
convergence for a parameter regime of Adam as a byproduct. Aggregating sign
gradients by majority vote means that no individual worker has too much power.
We prove that unlike SGD, majority vote is robust when up to 50% of workers
behave adversarially. The class of adversaries we consider includes as special
cases those that invert or randomise their gradient estimate. On the practical
side, we built our distributed training system in Pytorch. Benchmarking against
the state of the art collective communications library (NCCL), our
framework---with the parameter server housed entirely on one machine---led to a
25% reduction in time for training resnet50 on Imagenet when using 15 AWS
p3.2xlarge machines.
Online Multiclass Boosting with Bandit Feedback
Authors: Daniel T. Zhang, Young Hun Jung, Ambuj Tewari
Date: 2018-10-11 00:00:00
Tasks: General Classification

We present online boosting algorithms for multiclass classification with
bandit feedback, where the learner only receives feedback about the correctness
of its prediction. We propose an unbiased estimate of the loss using a
randomized prediction, allowing the model to update its weak learners with
limited information. Using the unbiased estimate, we extend two full
information boosting algorithms (Jung et al., 2017) to the bandit setting. We
prove that the asymptotic error bounds of the bandit algorithms exactly match
their full information counterparts. The cost of restricted feedback is
reflected in the larger sample complexity. Experimental results also support
our theoretical findings, and performance of the proposed models is comparable
to that of an existing bandit boosting algorithm, which is limited to use
binary weak learners.
IOHprofiler: A Benchmarking and Profiling Tool for Iterative Optimization Heuristics
Authors: Carola Doerr, Hao Wang, Furong Ye, Sander van Rijn, Thomas Bäck
Date: 2018-10-11 00:00:00
Tasks: Benchmarking

IOHprofiler is a new tool for analyzing and comparing iterative optimization
heuristics. Given as input algorithms and problems written in C or Python, it
provides as output a statistical evaluation of the algorithms' performance by
means of the distribution on the fixed-target running time and the fixed-budget
function values. In addition, IOHprofiler also allows to track the evolution of
algorithm parameters, making our tool particularly useful for the analysis,
comparison, and design of (self-)adaptive algorithms.
  IOHprofiler is a ready-to-use software. It consists of two parts: an
experimental part, which generates the running time data, and a post-processing
part, which produces the summarizing comparisons and statistical evaluations.
The experimental part is build on the COCO software, which has been adjusted to
cope with optimization problems that are formulated as functions
$f:\mathcal{S}^n \to \R$ with $\mathcal{S}$ being a discrete alphabet of
integers. The post-processing part is our own work. It can be used as a
stand-alone tool for the evaluation of running time data of arbitrary benchmark
problems. It accepts as input files not only the output files of IOHprofiler,
but also original COCO data files. The post-processing tool is designed for an
interactive evaluation, allowing the user to chose the ranges and the precision
of the displayed data according to his/her needs.
  IOHprofiler is available on GitHub at \url{https://github.com/IOHprofiler}.
Rethinking the Value of Network Pruning
Authors: Zhuang Liu, Ming-Jie Sun, Tinghui Zhou, Gao Huang, Trevor Darrell
Date: 2018-10-11 00:00:00
Proceeding: ICLR 2019 5
Tasks: Network Pruning, Neural Architecture Search

Network pruning is widely used for reducing the heavy inference cost of deep
models in low-resource settings. A typical pruning algorithm is a three-stage
pipeline, i.e., training (a large model), pruning and fine-tuning. During
pruning, according to a certain criterion, redundant weights are pruned and
important weights are kept to best preserve the accuracy. In this work, we make
several surprising observations which contradict common beliefs. For all
state-of-the-art structured pruning algorithms we examined, fine-tuning a
pruned model only gives comparable or worse performance than training that
model with randomly initialized weights. For pruning algorithms which assume a
predefined target network architecture, one can get rid of the full pipeline
and directly train the target network from scratch. Our observations are
consistent for multiple network architectures, datasets, and tasks, which imply
that: 1) training a large, over-parameterized model is often not necessary to
obtain an efficient final model, 2) learned "important" weights of the large
model are typically not useful for the small pruned model, 3) the pruned
architecture itself, rather than a set of inherited "important" weights, is
more crucial to the efficiency in the final model, which suggests that in some
cases pruning can be useful as an architecture search paradigm. Our results
suggest the need for more careful baseline evaluations in future research on
structured pruning methods. We also compare with the "Lottery Ticket
Hypothesis" (Frankle & Carbin 2019), and find that with optimal learning rate,
the "winning ticket" initialization as used in Frankle & Carbin (2019) does not
bring improvement over random initialization.