pwc-archive/papers-with-abstracts huggingface dataset:
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
Authors: Bryon Aragam, Arash A. Amini, Qing Zhou
Date: 2015-11-29 00:00:00
Tasks: regression

We study a family of regularized score-based estimators for learning the
structure of a directed acyclic graph (DAG) for a multivariate normal
distribution from high-dimensional data with $p\gg n$. Our main results
establish support recovery guarantees and deviation bounds for a family of
penalized least-squares estimators under concave regularization without
assuming prior knowledge of a variable ordering. These results apply to a
variety of practical situations that allow for arbitrary nondegenerate
covariance structures as well as many popular regularizers including the MCP,
SCAD, $\ell_{0}$ and $\ell_{1}$. The proof relies on interpreting a DAG as a
recursive linear structural equation model, which reduces the estimation
problem to a series of neighbourhood regressions. We provide a novel
statistical analysis of these neighbourhood problems, establishing uniform
control over the superexponential family of neighbourhoods associated with a
Gaussian distribution. We then apply these results to study the statistical
properties of score-based DAG estimators, learning causal DAGs, and inferring
conditional independence relations via graphical models. Our results
yield---for the first time---finite-sample guarantees for structure learning of
Gaussian DAGs in high-dimensions via score-based estimation.
Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences
Authors: Kinjal Basu, Ankan Saha, Shaunak Chatterjee
Date: 2017-10-02 00:00:00
Proceeding: NeurIPS 2017 12

We consider the problem of solving a large-scale Quadratically Constrained
Quadratic Program. Such problems occur naturally in many scientific and web
applications. Although there are efficient methods which tackle this problem,
they are mostly not scalable. In this paper, we develop a method that
transforms the quadratic constraint into a linear form by sampling a set of
low-discrepancy points. The transformed problem can then be solved by applying
any state-of-the-art large-scale quadratic programming solvers. We show the
convergence of our approximate solution to the true solution as well as some
finite sample error bounds. Experimental results are also shown to prove
scalability as well as improved quality of approximation in practice.
Cooperative Automated Vehicles: a Review of Opportunities and Challenges in Socially Intelligent Vehicles Beyond Networking
Authors: Seng W. Loke
Date: 2017-10-02 00:00:00
Tasks: Autonomous Vehicles, Decision Making

The connected automated vehicle has been often touted as a technology that will become pervasive in society in the near future. One can view an automated vehicle as having Artificial Intelligence (AI) capabilities, being able to self-drive, sense its surroundings, recognise objects in its vicinity, and perform reasoning and decision-making. Rather than being stand alone, we examine the need for automated vehicles to cooperate and interact within their socio-cyber-physical environments, including the problems cooperation will solve, but also the issues and challenges. We review current work in cooperation for automated vehicles, based on selected examples from the literature. We conclude noting the need for the ability to behave cooperatively as a form of social-AI capability for automated vehicles, beyond sensing the immediate environment and beyond the underlying networking technology.
Deep Abstract Q-Networks
Authors: Melrose Roderick, Christopher Grimm, Stefanie Tellex
Date: 2017-10-02 00:00:00
Tasks: Deep Reinforcement Learning, Montezuma's Revenge, Reinforcement Learning

We examine the problem of learning and planning on high-dimensional domains
with long horizons and sparse rewards. Recent approaches have shown great
successes in many Atari 2600 domains. However, domains with long horizons and
sparse rewards, such as Montezuma's Revenge and Venture, remain challenging for
existing methods. Methods using abstraction (Dietterich 2000; Sutton, Precup,
and Singh 1999) have shown to be useful in tackling long-horizon problems. We
combine recent techniques of deep reinforcement learning with existing
model-based approaches using an expert-provided state abstraction. We construct
toy domains that elucidate the problem of long horizons, sparse rewards and
high-dimensional inputs, and show that our algorithm significantly outperforms
previous methods on these domains. Our abstraction-based approach outperforms
Deep Q-Networks (Mnih et al. 2015) on Montezuma's Revenge and Venture, and
exhibits backtracking behavior that is absent from previous methods.
Visual Reasoning with Natural Language
Authors: Stephanie Zhou, Alane Suhr, Yoav Artzi
Date: 2017-10-02 00:00:00
Tasks: Descriptive, Diversity, Visual Reasoning

Natural language provides a widely accessible and expressive interface for
robotic agents. To understand language in complex environments, agents must
reason about the full range of language inputs and their correspondence to the
world. Such reasoning over language and vision is an open problem that is
receiving increasing attention. While existing data sets focus on visual
diversity, they do not display the full range of natural language expressions,
such as counting, set reasoning, and comparisons.
  We propose a simple task for natural language visual reasoning, where images
are paired with descriptive statements. The task is to predict if a statement
is true for the given scene. This abstract describes our existing synthetic
images corpus and our current work on collecting real vision data.
Learning event representation: As sparse as possible, but not sparser
Authors: Tuan Do, James Pustejovsky
Date: 2017-10-02 00:00:00
Tasks: Classification, General Classification, Human-Object Interaction Detection, Spatial Reasoning

Selecting an optimal event representation is essential for event
classification in real world contexts. In this paper, we investigate the
application of qualitative spatial reasoning (QSR) frameworks for
classification of human-object interaction in three dimensional space, in
comparison with the use of quantitative feature extraction approaches for the
same purpose. In particular, we modify QSRLib, a library that allows
computation of Qualitative Spatial Relations and Calculi, and employ it for
feature extraction, before inputting features into our neural network models.
Using an experimental setup involving motion captures of human-object
interaction as three dimensional inputs, we observe that the use of qualitative
spatial features significantly improves the performance of our machine learning
algorithm against our baseline, while quantitative features of similar kinds
fail to deliver similar improvement. We also observe that sequential
representations of QSR features yield the best classification performance. A
result of our learning method is a simple approach to the qualitative
representation of 3D activities as compositions of 2D actions that can be
visualized and learned using 2-dimensional QSR.
Feature-based time-series analysis
Authors: Ben D. Fulcher
Date: 2017-09-23 00:00:00
Tasks: Time Series, Time Series Analysis

This work presents an introduction to feature-based time-series analysis. The
time series as a data type is first described, along with an overview of the
interdisciplinary time-series analysis literature. I then summarize the range
of feature-based representations for time series that have been developed to
aid interpretable insights into time-series structure. Particular emphasis is
given to emerging research that facilitates wide comparison of feature-based
representations that allow us to understand the properties of a time-series
dataset that make it suited to a particular feature-based representation or
analysis algorithm. The future of time-series analysis is likely to embrace
approaches that exploit machine learning methods to partially automate human
learning to aid understanding of the complex dynamical patterns in the time
series we measure from the world.
Numerical optimization for Artificial Retina Algorithm
Authors: Maxim Borisyak, Andrey Ustyuzhanin, Denis Derkach, Mikhail Belous
Date: 2017-09-25 00:00:00

High-energy physics experiments rely on reconstruction of the trajectories of
particles produced at the interaction point. This is a challenging task,
especially in the high track multiplicity environment generated by p-p
collisions at the LHC energies. A typical event includes hundreds of signal
examples (interesting decays) and a significant amount of noise (uninteresting
examples).
  This work describes a modification of the Artificial Retina algorithm for
fast track finding: numerical optimization methods were adopted for fast local
track search. This approach allows for considerable reduction of the total
computational time per event. Test results on simplified simulated model of
LHCb VELO (VErtex LOcator) detector are presented. Also this approach is
well-suited for implementation of paralleled computations as GPGPU which look
very attractive in the context of upcoming detector upgrades.
DeepTFP: Mobile Time Series Data Analytics based Traffic Flow Prediction
Authors: Yuanfang Chen, Falin Chen, Yizhi Ren, Ting Wu, Ye Yao
Date: 2017-10-01 00:00:00
Tasks: Prediction, Time Series, Time Series Analysis, Time Series Prediction

Traffic flow prediction is an important research issue to avoid traffic
congestion in transportation systems. Traffic congestion avoiding can be
achieved by knowing traffic flow and then conducting transportation planning.
Achieving traffic flow prediction is challenging as the prediction is affected
by many complex factors such as inter-region traffic, vehicles' relations, and
sudden events. However, as the mobile data of vehicles has been widely
collected by sensor-embedded devices in transportation systems, it is possible
to predict the traffic flow by analysing mobile data. This study proposes a
deep learning based prediction algorithm, DeepTFP, to collectively predict the
traffic flow on each and every traffic road of a city. This algorithm uses
three deep residual neural networks to model temporal closeness, period, and
trend properties of traffic flow. Each residual neural network consists of a
branch of residual convolutional units. DeepTFP aggregates the outputs of the
three residual neural networks to optimize the parameters of a time series
prediction model. Contrast experiments on mobile time series data from the
transportation system of England demonstrate that the proposed DeepTFP
outperforms the Long Short-Term Memory (LSTM) architecture based method in
prediction accuracy.
A Workflow for Visual Diagnostics of Binary Classifiers using Instance-Level Explanations
Authors: Josua Krause, Aritra Dasgupta, Jordan Swartz, Yindalon Aphinyanaphongs, Enrico Bertini
Date: 2017-05-04 00:00:00
Tasks: BIG-bench Machine Learning

Human-in-the-loop data analysis applications necessitate greater transparency
in machine learning models for experts to understand and trust their decisions.
To this end, we propose a visual analytics workflow to help data scientists and
domain experts explore, diagnose, and understand the decisions made by a binary
classifier. The approach leverages "instance-level explanations", measures of
local feature relevance that explain single instances, and uses them to build a
set of visual representations that guide the users in their investigation. The
workflow is based on three main visual representations and steps: one based on
aggregate statistics to see how data distributes across correct / incorrect
decisions; one based on explanations to understand which features are used to
make these decisions; and one based on raw data, to derive insights on
potential root causes for the observed patterns. The workflow is derived from a
long-term collaboration with a group of machine learning and healthcare
professionals who used our method to make sense of machine learning models they
developed. The case study from this collaboration demonstrates that the
proposed workflow helps experts derive useful knowledge about the model and the
phenomena it describes, thus experts can generate useful hypotheses on how a
model can be improved.
Policy Learning with Observational Data
Authors: Susan Athey, Stefan Wager
Date: 2017-02-09 00:00:00
Tasks: Fairness, Form

In many areas, practitioners seek to use observational data to learn a treatment assignment policy that satisfies application-specific constraints, such as budget, fairness, simplicity, or other functional form constraints. For example, policies may be restricted to take the form of decision trees based on a limited set of easily observable individual characteristics. We propose a new approach to this problem motivated by the theory of semiparametrically efficient estimation. Our method can be used to optimize either binary treatments or infinitesimal nudges to continuous treatments, and can leverage observational data where causal effects are identified using a variety of strategies, including selection on observables and instrumental variables. Given a doubly robust estimator of the causal effect of assigning everyone to treatment, we develop an algorithm for choosing whom to treat, and establish strong guarantees for the asymptotic utilitarian regret of the resulting policy.
On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
Authors: Mingrui Liu, Tianbao Yang
Date: 2017-09-25 00:00:00

The Hessian-vector product has been utilized to find a second-order
stationary solution with strong complexity guarantee (e.g., almost linear time
complexity in the problem's dimensionality). In this paper, we propose to
further reduce the number of Hessian-vector products for faster non-convex
optimization. Previous algorithms need to approximate the smallest eigen-value
with a sufficient precision (e.g., $\epsilon_2\ll 1$) in order to achieve a
sufficiently accurate second-order stationary solution (i.e.,
$\lambda_{\min}(\nabla^2 f(\x))\geq -\epsilon_2)$. In contrast, the proposed
algorithms only need to compute the smallest eigen-vector approximating the
corresponding eigen-value up to a small power of current gradient's norm. As a
result, it can dramatically reduce the number of Hessian-vector products during
the course of optimization before reaching first-order stationary points (e.g.,
saddle points). The key building block of the proposed algorithms is a novel
updating step named the NCG step, which lets a noisy negative curvature descent
compete with the gradient descent. We show that the worst-case time complexity
of the proposed algorithms with their favorable prescribed accuracy
requirements can match the best in literature for achieving a second-order
stationary point but with an arguably smaller per-iteration cost. We also show
that the proposed algorithms can benefit from inexact Hessian by developing
their variants accepting inexact Hessian under a mild condition for achieving
the same goal. Moreover, we develop a stochastic algorithm for a finite or
infinite sum non-convex optimization problem. To the best of our knowledge, the
proposed stochastic algorithm is the first one that converges to a second-order
stationary point in {\it high probability} with a time complexity independent
of the sample size and almost linear in dimensionality.
Estimating the Fundamental Limits is Easier than Achieving the Fundamental Limits
Authors: Jiantao Jiao, Yanjun Han, Irena Fischer-Hwang, Tsachy Weissman
Date: 2017-07-05 00:00:00
Tasks: Binary Classification, Data Compression, General Classification

We show through case studies that it is easier to estimate the fundamental
limits of data processing than to construct explicit algorithms to achieve
those limits. Focusing on binary classification, data compression, and
prediction under logarithmic loss, we show that in the finite space setting,
when it is possible to construct an estimator of the limits with vanishing
error with $n$ samples, it may require at least $n\ln n$ samples to construct
an explicit algorithm to achieve the limits.
Efficient Preconditioning for Noisy Separable NMFs by Successive Projection Based Low-Rank Approximations
Authors: Tomohiko Mizutani, Mirai Tanaka
Date: 2017-10-01 00:00:00
Tasks: Single Particle Analysis

The successive projection algorithm (SPA) can quickly solve a nonnegative
matrix factorization problem under a separability assumption. Even if noise is
added to the problem, SPA is robust as long as the perturbations caused by the
noise are small. In particular, robustness against noise should be high when
handling the problems arising from real applications. The preconditioner
proposed by Gillis and Vavasis (2015) makes it possible to enhance the noise
robustness of SPA. Meanwhile, an additional computational cost is required. The
construction of the preconditioner contains a step to compute the top-$k$
truncated singular value decomposition of an input matrix. It is known that the
decomposition provides the best rank-$k$ approximation to the input matrix; in
other words, a matrix with the smallest approximation error among all matrices
of rank less than $k$. This step is an obstacle to an efficient implementation
of the preconditioned SPA.
  To address the cost issue, we propose a modification of the algorithm for
constructing the preconditioner. Although the original algorithm uses the best
rank-$k$ approximation, instead of it, our modification uses an alternative.
Ideally, this alternative should have high approximation accuracy and low
computational cost. To ensure this, our modification employs a rank-$k$
approximation produced by an SPA based algorithm. We analyze the accuracy of
the approximation and evaluate the computational cost of the algorithm. We then
present an empirical study revealing the actual performance of the SPA based
rank-$k$ approximation algorithm and the modified preconditioned SPA.
Parallelizing Over Artificial Neural Network Training Runs with Multigrid
Authors: Jacob B. Schroder
Date: 2017-08-07 00:00:00
Tasks: Distributed Computing, GPU

Artificial neural networks are a popular and effective machine learning
technique. Great progress has been made parallelizing the expensive training
phase of an individual network, leading to highly specialized pieces of
hardware, many based on GPU-type architectures, and more concurrent algorithms
such as synthetic gradients. However, the training phase continues to be a
bottleneck, where the training data must be processed serially over thousands
of individual training runs. This work considers a multigrid reduction in time
(MGRIT) algorithm that is able to parallelize over the thousands of training
runs and converge to the exact same solution as traditional training would
provide. MGRIT was originally developed to provide parallelism for time
evolution problems that serially step through a finite number of time-steps.
This work recasts the training of a neural network similarly, treating neural
network training as an evolution equation that evolves the network weights from
one step to the next. Thus, this work concerns distributed computing approaches
for neural networks, but is distinct from other approaches which seek to
parallelize only over individual training runs. The work concludes with
supporting numerical results for two model problems.
libact: Pool-based Active Learning in Python
Authors: Yao-Yuan Yang, Shao-Chuan Lee, Yu-An Chung, Tung-En Wu, Si-An Chen, Hsuan-Tien Lin
Date: 2017-10-01 00:00:00
Tasks: Active Learning

libact is a Python package designed to make active learning easier for
general users. The package not only implements several popular active learning
strategies, but also features the active-learning-by-learning meta-algorithm
that assists the users to automatically select the best strategy on the fly.
Furthermore, the package provides a unified interface for implementing more
strategies, models and application-specific labelers. The package is
open-source on Github, and can be easily installed from Python Package Index
repository.
Mathematical foundations of matrix syntax
Authors: Roman Orus, Roger Martin, Juan Uriagereka
Date: 2017-10-01 00:00:00

Matrix syntax is a formal model of syntactic relations in language. The
purpose of this paper is to explain its mathematical foundations, for an
audience with some formal background. We make an axiomatic presentation,
motivating each axiom on linguistic and practical grounds. The resulting
mathematical structure resembles some aspects of quantum mechanics. Matrix
syntax allows us to describe a number of language phenomena that are otherwise
very difficult to explain, such as linguistic chains, and is arguably a more
economical theory of language than most of the theories proposed in the context
of the minimalist program in linguistics. In particular, sentences are
naturally modelled as vectors in a Hilbert space with a tensor product
structure, built from 2x2 matrices belonging to some specific group.
Beyond opening up the black box: Investigating the role of algorithmic systems in Wikipedian organizational culture
Authors: R. Stuart Geiger
Date: 2017-09-26 00:00:00
Tasks: Cultural Vocal Bursts Intensity Prediction, Fairness

Scholars and practitioners across domains are increasingly concerned with
algorithmic transparency and opacity, interrogating the values and assumptions
embedded in automated, black-boxed systems, particularly in user-generated
content platforms. I report from an ethnography of infrastructure in Wikipedia
to discuss an often understudied aspect of this topic: the local, contextual,
learned expertise involved in participating in a highly automated
social-technical environment. Today, the organizational culture of Wikipedia is
deeply intertwined with various data-driven algorithmic systems, which
Wikipedians rely on to help manage and govern the "anyone can edit"
encyclopedia at a massive scale. These bots, scripts, tools, plugins, and
dashboards make Wikipedia more efficient for those who know how to work with
them, but like all organizational culture, newcomers must learn them if they
want to fully participate. I illustrate how cultural and organizational
expertise is enacted around algorithmic agents by discussing two
autoethnographic vignettes, which relate my personal experience as a veteran in
Wikipedia. I present thick descriptions of how governance and gatekeeping
practices are articulated through and in alignment with these automated
infrastructures. Over the past 15 years, Wikipedian veterans and administrators
have made specific decisions to support administrative and editorial workflows
with automation in particular ways and not others. I use these cases of
Wikipedia's bot-supported bureaucracy to discuss several issues in the fields
of critical algorithms studies, critical data studies, and fairness,
accountability, and transparency in machine learning -- most principally
arguing that scholarship and practice must go beyond trying to "open up the
black box" of such systems and also examine sociocultural processes like
newcomer socialization.