pwc-archive/papers-with-abstracts huggingface dataset:
A unifying representer theorem for inverse problems and machine learning
Authors: Michael Unser
Date: 2019-03-02 00:00:00
Tasks: BIG-bench Machine Learning

The standard approach for dealing with the ill-posedness of the training problem in machine learning and/or the reconstruction of a signal from a limited number of measurements is regularization. The method is applicable whenever the problem is formulated as an optimization task. The standard strategy consists in augmenting the original cost functional by an energy that penalizes solutions with undesirable behavior. The effect of regularization is very well understood when the penalty involves a Hilbertian norm. Another popular configuration is the use of an $\ell_1$-norm (or some variant thereof) that favors sparse solutions. In this paper, we propose a higher-level formulation of regularization within the context of Banach spaces. We present a general representer theorem that characterizes the solutions of a remarkably broad class of optimization problems. We then use our theorem to retrieve a number of known results in the literature---e.g., the celebrated representer theorem of machine leaning for RKHS, Tikhonov regularization, representer theorems for sparsity promoting functionals, the recovery of spikes---as well as a few new ones.
DimDraw -- A novel tool for drawing concept lattices
Authors: Dominik Dürrschnabel, Tom Hanika, Gerd Stumme
Date: 2019-03-02 00:00:00

Concept lattice drawings are an important tool to visualize complex relations
in data in a simple manner to human readers. Many attempts were made to
transfer classical graph drawing approaches to order diagrams. Although those
methods are satisfying for some lattices they unfortunately perform poorly in
general. In this work we present a novel tool to draw concept lattices that is
purely motivated by the order structure.
OmniDRL: Robust Pedestrian Detection using Deep Reinforcement Learning on Omnidirectional Cameras
Authors: G. Dias Pais, Tiago J. Dias, Jacinto C. Nascimento, Pedro Miraldo
Date: 2019-03-02 00:00:00
Tasks: Deep Reinforcement Learning, Pedestrian Detection, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Pedestrian detection is one of the most explored topics in computer vision
and robotics. The use of deep learning methods allowed the development of new
and highly competitive algorithms. Deep Reinforcement Learning has proved to be
within the state-of-the-art in terms of both detection in perspective cameras
and robotics applications. However, for detection in omnidirectional cameras,
the literature is still scarce, mostly because of their high levels of
distortion. This paper presents a novel and efficient technique for robust
pedestrian detection in omnidirectional images. The proposed method uses deep
Reinforcement Learning that takes advantage of the distortion in the image. By
considering the 3D bounding boxes and their distorted projections into the
image, our method is able to provide the pedestrian's position in the world, in
contrast to the image positions provided by most state-of-the-art methods for
perspective cameras. Our method avoids the need of pre-processing steps to
remove the distortion, which is computationally expensive. Beyond the novel
solution, our method compares favorably with the state-of-the-art methodologies
that do not consider the underlying distortion for the detection task.
Leveraging Low-Rank Relations Between Surrogate Tasks in Structured Prediction
Authors: Giulia Luise, Dimitris Stamos, Massimiliano Pontil, Carlo Ciliberto
Date: 2019-03-02 00:00:00
Tasks: Structured Prediction

We study the interplay between surrogate methods for structured prediction
and techniques from multitask learning designed to leverage relationships
between surrogate outputs. We propose an efficient algorithm based on trace
norm regularization which, differently from previous methods, does not require
explicit knowledge of the coding/decoding functions of the surrogate framework.
As a result, our algorithm can be applied to the broad class of problems in
which the surrogate space is large or even infinite dimensional. We study
excess risk bounds for trace norm regularized structured prediction, implying
the consistency and learning rates for our estimator. We also identify relevant
regimes in which our approach can enjoy better generalization performance than
previous methods. Numerical experiments on ranking problems indicate that
enforcing low-rank relations among surrogate outputs may indeed provide a
significant advantage in practice.
Towards NLP with Deep Learning: Convolutional Neural Networks and Recurrent Neural Networks for Offensive Language Identification in Social Media
Authors: Andrei-Bogdan Puiu, Andrei-Octavian Brabete
Date: 2019-03-02 00:00:00
Tasks: General Classification, Language Identification

This short paper presents the design decisions taken and challenges
encountered in completing SemEval Task 6, which poses the problem of
identifying and categorizing offensive language in tweets. Our proposed
solutions explore Deep Learning techniques, Linear Support Vector
classification and Random Forests to identify offensive tweets, to classify
offenses as targeted or untargeted and eventually to identify the target
subject type.
Quaternion Convolutional Neural Networks
Authors: Xuanyu Zhu, Yi Xu, Hongteng Xu, Changjian Chen
Date: 2019-03-02 00:00:00
Proceeding: ECCV 2018 9
Tasks: Denoising, image-classification, Image Classification

Neural networks in the real domain have been studied for a long time and
achieved promising results in many vision tasks for recent years. However, the
extensions of the neural network models in other number fields and their
potential applications are not fully-investigated yet. Focusing on color
images, which can be naturally represented as quaternion matrices, we propose a
quaternion convolutional neural network (QCNN) model to obtain more
representative features. In particular, we redesign the basic modules like
convolution layer and fully-connected layer in the quaternion domain, which can
be used to establish fully-quaternion convolutional neural networks. Moreover,
these modules are compatible with almost all deep learning techniques and can
be plugged into traditional CNNs easily. We test our QCNN models in both color
image classification and denoising tasks. Experimental results show that they
outperform the real-valued CNNs with same structures.
One-Pass Incomplete Multi-view Clustering
Authors: Menglei Hu, Songcan Chen
Date: 2019-03-02 00:00:00
Tasks: Clustering, Incomplete multi-view clustering

Real data are often with multiple modalities or from multiple heterogeneous
sources, thus forming so-called multi-view data, which receives more and more
attentions in machine learning. Multi-view clustering (MVC) becomes its
important paradigm. In real-world applications, some views often suffer from
instances missing. Clustering on such multi-view datasets is called incomplete
multi-view clustering (IMC) and quite challenging. To date, though many
approaches have been developed, most of them are offline and have high
computational and memory costs especially for large scale datasets. To address
this problem, in this paper, we propose an One-Pass Incomplete Multi-view
Clustering framework (OPIMC). With the help of regularized matrix factorization
and weighted matrix factorization, OPIMC can relatively easily deal with such
problem. Different from the existing and sole online IMC method, OPIMC can
directly get clustering results and effectively determine the termination of
iteration process by introducing two global statistics. Finally, extensive
experiments conducted on four real datasets demonstrate the efficiency and
effectiveness of the proposed OPIMC method.
Unsupervised Traffic Accident Detection in First-Person Videos
Authors: Yu Yao, Mingze Xu, Yuchen Wang, David J. Crandall, Ella M. Atkins
Date: 2019-03-02 00:00:00
Tasks: Anomaly Detection, Autonomous Driving, Object Localization, One-Class Classification, Traffic Accident Detection, Trajectory Prediction, Video Anomaly Detection

Recognizing abnormal events such as traffic violations and accidents in natural driving scenes is essential for successful autonomous driving and advanced driver assistance systems. However, most work on video anomaly detection suffers from two crucial drawbacks. First, they assume cameras are fixed and videos have static backgrounds, which is reasonable for surveillance applications but not for vehicle-mounted cameras. Second, they pose the problem as one-class classification, relying on arduously hand-labeled training datasets that limit recognition to anomaly categories that have been explicitly trained. This paper proposes an unsupervised approach for traffic accident detection in first-person (dashboard-mounted camera) videos. Our major novelty is to detect anomalies by predicting the future locations of traffic participants and then monitoring the prediction accuracy and consistency metrics with three different strategies. We evaluate our approach using a new dataset of diverse traffic accidents, AnAn Accident Detection (A3D), as well as another publicly-available dataset. Experimental results show that our approach outperforms the state-of-the-art.
Approximation Properties of Variational Bayes for Vector Autoregressions
Authors: Reza Hajargasht
Date: 2019-03-02 00:00:00
Tasks: Bayesian Inference, regression

Variational Bayes (VB) is a recent approximate method for Bayesian inference.
It has the merit of being a fast and scalable alternative to Markov Chain Monte
Carlo (MCMC) but its approximation error is often unknown. In this paper, we
derive the approximation error of VB in terms of mean, mode, variance,
predictive density and KL divergence for the linear Gaussian multi-equation
regression. Our results indicate that VB approximates the posterior mean
perfectly. Factors affecting the magnitude of underestimation in posterior
variance and mode are revealed. Importantly, We demonstrate that VB estimates
predictive densities accurately.
GAP: Generalizable Approximate Graph Partitioning Framework
Authors: Azade Nazi, Will Hang, Anna Goldie, Sujith Ravi, Azalia Mirhoseini
Date: 2019-03-02 00:00:00
Tasks: Clustering, graph partitioning

Graph partitioning is the problem of dividing the nodes of a graph into
balanced partitions while minimizing the edge cut across the partitions. Due to
its combinatorial nature, many approximate solutions have been developed,
including variants of multi-level methods and spectral clustering. We propose
GAP, a Generalizable Approximate Partitioning framework that takes a deep
learning approach to graph partitioning. We define a differentiable loss
function that represents the partitioning objective and use backpropagation to
optimize the network parameters. Unlike baselines that redo the optimization
per graph, GAP is capable of generalization, allowing us to train models that
produce performant partitions at inference time, even on unseen graphs.
Furthermore, because we learn the representation of the graph while jointly
optimizing for the partitioning loss function, GAP can be easily tuned for a
variety of graph structures. We evaluate the performance of GAP on graphs of
varying sizes and structures, including graphs of widely used machine learning
models (e.g., ResNet, VGG, and Inception-V3), scale-free graphs, and random
graphs. We show that GAP achieves competitive partitions while being up to 100
times faster than the baseline and generalizes to unseen graphs.
Discovering Options for Exploration by Minimizing Cover Time
Authors: Yuu Jinnai, Jee Won Park, David Abel, George Konidaris
Date: 2019-03-02 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

One of the main challenges in reinforcement learning is solving tasks with
sparse reward. We show that the difficulty of discovering a distant rewarding
state in an MDP is bounded by the expected cover time of a random walk over the
graph induced by the MDP's transition dynamics. We therefore propose to
accelerate exploration by constructing options that minimize cover time. The
proposed algorithm finds an option which provably diminishes the expected
number of steps to visit every state in the state space by a uniform random
walk. We show empirically that the proposed algorithm improves the learning
time in several domains with sparse rewards.
Block-Coordinate Minimization for Large SDPs with Block-Diagonal Constraints
Authors: Yulun Tian, Kasra Khosoussi, Jonathan P. How
Date: 2019-03-02 00:00:00
Tasks: Riemannian optimization

The so-called Burer-Monteiro method is a well-studied technique for solving large-scale semidefinite programs (SDPs) via low-rank factorization. The main idea is to solve rank-restricted, albeit non-convex, surrogates instead of the SDP. Recent works have shown that, in an important class of SDPs with elegant geometric structure, one can find globally optimal solutions to the SDP by finding rank-deficient second-order critical points of an unconstrained Riemannian optimization problem. Hence, in such problems, the Burer-Monteiro approach can provide a scalable and reliable alternative to interior-point methods that scale poorly. Among various Riemannian optimization methods proposed, block-coordinate minimization (BCM) is of particular interest due to its simplicity. Erdogdu et al. in their recent work proposed BCM for problems over the Cartesian product of unit spheres and provided global convergence rate estimates for the algorithm. This report extends the BCM algorithm and the global convergence rate analysis of Erdogdu et al. from problems over the Cartesian product of unit spheres to the Cartesian product of Stiefel manifolds. The latter more general setting has important applications such as synchronization over the special orthogonal (SO) and special Euclidean (SE) groups.
Straight to the point: reinforcement learning for user guidance in ultrasound
Authors: Fausto Milletari, Vighnesh Birodkar, Michal Sofka
Date: 2019-03-02 00:00:00
Tasks: Anatomy, Diagnostic, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Point of care ultrasound (POCUS) consists in the use of ultrasound imaging in
critical or emergency situations to support clinical decisions by healthcare
professionals and first responders. In this setting it is essential to be able
to provide means to obtain diagnostic data to potentially inexperienced users
who did not receive an extensive medical training. Interpretation and
acquisition of ultrasound images is not trivial. First, the user needs to find
a suitable sound window which can be used to get a clear image, and then he
needs to correctly interpret it to perform a diagnosis. Although many recent
approaches focus on developing smart ultrasound devices that add interpretation
capabilities to existing systems, our goal in this paper is to present a
reinforcement learning (RL) strategy which is capable to guide novice users to
the correct sonic window and enable them to obtain clinically relevant pictures
of the anatomy of interest. We apply our approach to cardiac images acquired
from the parasternal long axis (PLAx) view of the left ventricle of the heart.
PuVAE: A Variational Autoencoder to Purify Adversarial Examples
Authors: Uiwon Hwang, Jaewoo Park, Hyemi Jang, Sungroh Yoon, Nam Ik Cho
Date: 2019-03-02 00:00:00
Tasks: Adversarial Defense, Adversarial Defense against FGSM Attack

Deep neural networks are widely used and exhibit excellent performance in
many areas. However, they are vulnerable to adversarial attacks that compromise
the network at the inference time by applying elaborately designed perturbation
to input data. Although several defense methods have been proposed to address
specific attacks, other attack methods can circumvent these defense mechanisms.
Therefore, we propose Purifying Variational Autoencoder (PuVAE), a method to
purify adversarial examples. The proposed method eliminates an adversarial
perturbation by projecting an adversarial example on the manifold of each
class, and determines the closest projection as a purified sample. We
experimentally illustrate the robustness of PuVAE against various attack
methods without any prior knowledge. In our experiments, the proposed method
exhibits performances competitive with state-of-the-art defense methods, and
the inference time is approximately 130 times faster than that of Defense-GAN
that is the state-of-the art purifier model.
GRP Model for Sensorimotor Learning
Authors: Tianyu Li, Bolun Dai
Date: 2019-03-01 00:00:00
Tasks: Imitation Learning, model

Learning from complex demonstrations is challenging, especially when the
demonstration consists of different strategies. A popular approach is to use a
deep neural network to perform imitation learning. However, the structure of
that deep neural network has to be ``deep" enough to capture all possible
scenarios. Besides the machine learning issue, how humans learn in the sense of
physiology has rarely been addressed and relevant works on spinal cord learning
are rarer. In this work, we develop a novel modular learning architecture, the
Generator and Responsibility Predictor (GRP) model, which automatically learns
the sub-task policies from an unsegmented controller demonstration and learns
to switch between the policies. We also introduce a more physiological based
neural network architecture. We implemented our GRP model and our proposed
neural network to form a model the transfers the swing leg control from the
brain to the spinal cord. Our result suggests that by using the GRP model the
brain can successfully transfer the target swing leg control to the spinal cord
and the resulting model can switch between sub-control policies automatically.
Improved Deep Embeddings for Inferencing with Multi-Layered Networks
Authors: Huan Song, Jayaraman J. Thiagarajan
Date: 2018-09-20 00:00:00
Tasks: Community Detection, Link Prediction, Network Embedding, Node Classification

Inferencing with network data necessitates the mapping of its nodes into a
vector space, where the relationships are preserved. However, with
multi-layered networks, where multiple types of relationships exist for the
same set of nodes, it is crucial to exploit the information shared between
layers, in addition to the distinct aspects of each layer. In this paper, we
propose a novel approach that first obtains node embeddings in all layers
jointly via DeepWalk on a \textit{supra} graph, which allows interactions
between layers, and then fine-tunes the embeddings to encourage cohesive
structure in the latent space. With empirical studies in node classification,
link prediction and multi-layered community detection, we show that the
proposed approach outperforms existing single- and multi-layered network
embedding algorithms on several benchmarks. In addition to effectively scaling
to a large number of layers (tested up to $37$), our approach consistently
produces highly modular community structure, even when compared to methods that
directly optimize for the modularity function.
JIM: Joint Influence Modeling for Collective Search Behavior
Authors: Shubhra Kanti Karmaker Santu, Liangda Li, Yi Chang, ChengXiang Zhai
Date: 2019-03-01 00:00:00

Previous work has shown that popular trending events are important external
factors which pose significant influence on user search behavior and also
provided a way to computationally model this influence. However, their problem
formulation was based on the strong assumption that each event poses its
influence independently. This assumption is unrealistic as there are many
correlated events in the real world which influence each other and thus, would
pose a joint influence on the user search behavior rather than posing influence
independently. In this paper, we study this novel problem of Modeling the Joint
Influences posed by multiple correlated events on user search behavior. We
propose a Joint Influence Model based on the Multivariate Hawkes Process which
captures the inter-dependency among multiple events in terms of their influence
upon user search behavior. We evaluate the proposed Joint Influence Model using
two months query-log data from https://search.yahoo.com/. Experimental results
show that the model can indeed capture the temporal dynamics of the joint
influence over time and also achieves superior performance over different
baseline methods when applied to solve various interesting prediction problems
as well as real-word application scenarios, e.g., query auto-completion.
From PAC to Instance-Optimal Sample Complexity in the Plackett-Luce Model
Authors: Aadirupa Saha, Aditya Gopalan
Date: 2019-03-01 00:00:00
Proceeding: ICML 2020 1
Tasks: PAC learning

We consider PAC-learning a good item from $k$-subsetwise feedback information sampled from a Plackett-Luce probability model, with instance-dependent sample complexity performance. In the setting where subsets of a fixed size can be tested and top-ranked feedback is made available to the learner, we give an algorithm with optimal instance-dependent sample complexity, for PAC best arm identification, of $O\bigg(\frac{\theta_{[k]}}{k}\sum_{i = 2}^n\max\Big(1,\frac{1}{\Delta_i^2}\Big) \ln\frac{k}{\delta}\Big(\ln \frac{1}{\Delta_i}\Big)\bigg)$, $\Delta_i$ being the Plackett-Luce parameter gap between the best and the $i^{th}$ best item, and $\theta_{[k]}$ is the sum of the \pl\, parameters for the top-$k$ items. The algorithm is based on a wrapper around a PAC winner-finding algorithm with weaker performance guarantees to adapt to the hardness of the input instance. The sample complexity is also shown to be multiplicatively better depending on the length of rank-ordered feedback available in each subset-wise play. We show optimality of our algorithms with matching sample complexity lower bounds. We next address the winner-finding problem in Plackett-Luce models in the fixed-budget setting with instance dependent upper and lower bounds on the misidentification probability, of $\Omega\left(\exp(-2 \tilde \Delta Q) \right)$ for a given budget $Q$, where $\tilde \Delta$ is an explicit instance-dependent problem complexity parameter. Numerical performance results are also reported.
A Nonlinear Model for Time Synchronization
Authors: Frank Wang, Danjue Li
Date: 2019-03-01 00:00:00
Tasks: model

The current algorithms are based on linear model, for example, Precision Time
Protocol (PTP) which requires frequent synchronization in order to handle the
effects of clock frequency drift. This paper introduces a nonlinear approach to
clock time synchronize. This approach can accurately model the frequency shift.
Therefore, the required time interval to synchronize clocks can be longer.
Meanwhile, it also offers better performance and relaxes the synchronization
process. The idea of the nonlinear algorithm and some numerical examples will
be presented in this paper in detail.
Combinatorial Bandits with Relative Feedback
Authors: Aadirupa Saha, Aditya Gopalan
Date: 2019-03-01 00:00:00
Proceeding: NeurIPS 2019 12

We consider combinatorial online learning with subset choices when only relative feedback information from subsets is available, instead of bandit or semi-bandit feedback which is absolute. Specifically, we study two regret minimisation problems over subsets of a finite ground set $[n]$, with subset-wise relative preference information feedback according to the Multinomial logit choice model. In the first setting, the learner can play subsets of size bounded by a maximum size and receives top-$m$ rank-ordered feedback, while in the second setting the learner can play subsets of a fixed size $k$ with a full subset ranking observed as feedback. For both settings, we devise instance-dependent and order-optimal regret algorithms with regret $O(\frac{n}{m} \ln T)$ and $O(\frac{n}{k} \ln T)$, respectively. We derive fundamental limits on the regret performance of online learning with subset-wise preferences, proving the tightness of our regret guarantees. Our results also show the value of eliciting more general top-$m$ rank-ordered feedback over single winner feedback ($m=1$). Our theoretical results are corroborated with empirical evaluations.