pwc-archive/papers-with-abstracts huggingface dataset:
Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching
Authors: Yunsheng Bai, Hao Ding, Yizhou Sun, Wei Wang
Date: 2018-09-10 00:00:00
Tasks: Clustering, Combinatorial Optimization, Graph Classification, Graph Clustering, Graph Matching, Graph Similarity, set matching

Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a trade-off between accuracy and speed. Recently, several data-driven approaches based on neural networks have been proposed, most of which model the graph-graph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixed-dimensional embedding per graph may fail to fully capture graphs in varying sizes and link structures, a limitation that is especially problematic for the task of graph similarity computation, where the goal is to find the fine-grained difference between two graphs. In this paper, we address the problem of graph similarity computation from another perspective, by directly matching two sets of node embeddings without the need to use fixed-dimensional vectors to represent whole graphs for their similarity computation. The model, GraphSim, achieves the state-of-the-art performance on four real-world graph datasets under six out of eight settings (here we count a specific dataset and metric combination as one setting), compared to existing popular methods for approximate Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) computation.
Estimate the Warfarin Dose by Ensemble of Machine Learning Algorithms
Authors: Zhiyuan Ma, Ping Wang, Zehui Gao, Ruobing Wang, Koroush Khalighi
Date: 2018-09-10 00:00:00
Tasks: BIG-bench Machine Learning

Warfarin dosing remains challenging due to narrow therapeutic index and
highly individual variability. Incorrect warfarin dosing is associated with
devastating adverse events. Remarkable efforts have been made to develop the
machine learning based warfarin dosing algorithms incorporating clinical
factors and genetic variants such as polymorphisms in CYP2C9 and VKORC1. The
most widely validated pharmacogenetic algorithm is the IWPC algorithm based on
multivariate linear regression (MLR). However, with only a single algorithm,
the prediction performance may reach an upper limit even with optimal
parameters. Here, we present novel algorithms using stacked generalization
frameworks to estimate the warfarin dose, within which different types of
machine learning algorithms function together through a meta-machine learning
model to maximize the prediction accuracy. Compared to the IWPC-derived MLR
algorithm, Stack 1 and 2 based on stacked generalization frameworks performed
significantly better overall. Subgroup analysis revealed that the mean of the
percentage of patients whose predicted dose of warfarin within 20% of the
actual stable therapeutic dose (mean percentage within 20%) for Stack 1 was
improved by 12.7% (from 42.47% to 47.86%) in Asians and by 13.5% (from 22.08%
to 25.05%) in the low-dose group compared to that for MLR, respectively. These
data suggest that our algorithms would especially benefit patients required low
warfarin maintenance dose, as subtle changes in warfarin dose could lead to
adverse clinical events (thrombosis or bleeding) in patients with low dose. Our
study offers novel pharmacogenetic algorithms for clinical trials and practice.
Addressing the Fundamental Tension of PCGML with Discriminative Learning
Authors: Isaac Karth, Adam M. Smith
Date: 2018-09-10 00:00:00
Tasks: BIG-bench Machine Learning, valid

Procedural content generation via machine learning (PCGML) is typically
framed as the task of fitting a generative model to full-scale examples of a
desired content distribution. This approach presents a fundamental tension: the
more design effort expended to produce detailed training examples for shaping a
generator, the lower the return on investment from applying PCGML in the first
place. In response, we propose the use of discriminative models (which capture
the validity of a design rather the distribution of the content) trained on
positive and negative examples. Through a modest modification of
WaveFunctionCollapse, a commercially-adopted PCG approach that we characterize
as using elementary machine learning, we demonstrate a new mode of control for
learning-based generators. We demonstrate how an artist might craft a focused
set of additional positive and negative examples by critique of the generator's
previous outputs. This interaction mode bridges PCGML with mixed-initiative
design assistance tools by working with a machine to define a space of valid
designs rather than just one new design.
Unsupervised Controllable Text Formalization
Authors: Parag Jain, Abhijit Mishra, Amar Prakash Azad, Karthik Sankaranarayanan
Date: 2018-09-10 00:00:00
Tasks: Decoder

We propose a novel framework for controllable natural language
transformation. Realizing that the requirement of parallel corpus is
practically unsustainable for controllable generation tasks, an unsupervised
training scheme is introduced. The crux of the framework is a deep neural
encoder-decoder that is reinforced with text-transformation knowledge through
auxiliary modules (called scorers). The scorers, based on off-the-shelf
language processing tools, decide the learning scheme of the encoder-decoder
based on its actions. We apply this framework for the text-transformation task
of formalizing an input text by improving its readability grade; the degree of
required formalization can be controlled by the user at run-time. Experiments
on public datasets demonstrate the efficacy of our model towards: (a)
transforming a given text to a more formal style, and (b) introducing
appropriate amount of formalness in the output text pertaining to the input
control. Our code and datasets are released for academic use.
On-the-fly Historical Handwritten Text Annotation
Authors: Ekta Vats, Anders Hast
Date: 2017-09-06 00:00:00
Tasks: Information Retrieval, Retrieval, text annotation

The performance of information retrieval algorithms depends upon the
availability of ground truth labels annotated by experts. This is an important
prerequisite, and difficulties arise when the annotated ground truth labels are
incorrect or incomplete due to high levels of degradation. To address this
problem, this paper presents a simple method to perform on-the-fly annotation
of degraded historical handwritten text in ancient manuscripts. The proposed
method aims at quick generation of ground truth and correction of inaccurate
annotations such that the bounding box perfectly encapsulates the word, and
contains no added noise from the background or surroundings. This method will
potentially be of help to historians and researchers in generating and
correcting word labels in a document dynamically. The effectiveness of the
annotation method is empirically evaluated on an archival manuscript collection
from well-known publicly available datasets.
A Less Biased Evaluation of Out-of-distribution Sample Detectors
Authors: Alireza Shafaei, Mark Schmidt, James J. Little
Date: 2018-09-13 00:00:00
Tasks: image-classification, Image Classification

In the real world, a learning system could receive an input that is unlike anything it has seen during training. Unfortunately, out-of-distribution samples can lead to unpredictable behaviour. We need to know whether any given input belongs to the population distribution of the training/evaluation data to prevent unpredictable behaviour in deployed systems. A recent surge of interest in this problem has led to the development of sophisticated techniques in the deep learning literature. However, due to the absence of a standard problem definition or an exhaustive evaluation, it is not evident if we can rely on these methods. What makes this problem different from a typical supervised learning setting is that the distribution of outliers used in training may not be the same as the distribution of outliers encountered in the application. Classical approaches that learn inliers vs. outliers with only two datasets can yield optimistic results. We introduce OD-test, a three-dataset evaluation scheme as a more reliable strategy to assess progress on this problem. We present an exhaustive evaluation of a broad set of methods from related areas on image classification tasks. Contrary to the existing results, we show that for realistic applications of high-dimensional images the previous techniques have low accuracy and are not reliable in practice.
MSc Dissertation: Exclusive Row Biclustering for Gene Expression Using a Combinatorial Auction Approach
Authors: Amichai Painsky
Date: 2018-09-13 00:00:00
Tasks: Clustering

The availability of large microarray data has led to a growing interest in
biclustering methods in the past decade. Several algorithms have been proposed
to identify subsets of genes and conditions according to different similarity
measures and under varying constraints. In this paper we focus on the exclusive
row biclustering problem for gene expression data sets, in which each row can
only be a member of a single bicluster while columns can participate in
multiple ones. This type of biclustering may be adequate, for example, for
clustering groups of cancer patients where each patient (row) is expected to be
carrying only a single type of cancer, while each cancer type is associated
with multiple (and possibly overlapping) genes (columns). We present a novel
method to identify these exclusive row biclusters through a combination of
existing biclustering algorithms and combinatorial auction techniques. We
devise an approach for tuning the threshold for our algorithm based on
comparison to a null model in the spirit of the Gap statistic approach. We
demonstrate our approach on both synthetic and real-world gene expression data
and show its power in identifying large span non-overlapping rows sub matrices,
while considering their unique nature. The Gap statistic approach succeeds in
identifying appropriate thresholds in all our examples.
Computer Vision-aided Atom Tracking in STEM Imaging
Authors: Yawei Hui, Yaohua Liu
Date: 2018-09-13 00:00:00
Tasks: All

To address the SMC'17 data challenge -- "Data mining atomically resolved
images for material properties", we first used the classic "blob detection"
algorithms developed in computer vision to identify all atom centers in each
STEM image frame. With the help of nearest neighbor analysis, we then found and
labeled every atom center common to all the STEM frames and tracked their
movements through the given time interval for both Molybdenum or Selenium
atoms.
Derivative-free online learning of inverse dynamics models
Authors: Diego Romeres, Mattia Zorzi, Raffaello Camoriano, Silvio Traversaro, Alessandro Chiuso
Date: 2018-09-13 00:00:00

This paper discusses online algorithms for inverse dynamics modelling in
robotics. Several model classes including rigid body dynamics (RBD) models,
data-driven models and semiparametric models (which are a combination of the
previous two classes) are placed in a common framework. While model classes
used in the literature typically exploit joint velocities and accelerations,
which need to be approximated resorting to numerical differentiation schemes,
in this paper a new `derivative-free' framework is proposed that does not
require this preprocessing step. An extensive experimental study with real data
from the right arm of the iCub robot is presented, comparing different model
classes and estimation procedures, showing that the proposed `derivative-free'
methods outperform existing methodologies.
Physical Primitive Decomposition
Authors: Zhijian Liu, William T. Freeman, Joshua B. Tenenbaum, Jiajun Wu
Date: 2018-09-13 00:00:00
Proceeding: ECCV 2018 9
Tasks: Object

Objects are made of parts, each with distinct geometry, physics,
functionality, and affordances. Developing such a distributed, physical,
interpretable representation of objects will facilitate intelligent agents to
better explore and interact with the world. In this paper, we study physical
primitive decomposition---understanding an object through its components, each
with physical and geometric attributes. As annotated data for object parts and
physics are rare, we propose a novel formulation that learns physical
primitives by explaining both an object's appearance and its behaviors in
physical events. Our model performs well on block towers and tools in both
synthetic and real scenarios; we also demonstrate that visual and physical
observations often provide complementary signals. We further present ablation
and behavioral studies to better understand our model and contrast it with
human performance.
Learning Shape Priors for Single-View 3D Completion and Reconstruction
Authors: Jiajun Wu, Chengkai Zhang, Xiuming Zhang, Zhoutong Zhang, William T. Freeman, Joshua B. Tenenbaum
Date: 2018-09-13 00:00:00
Proceeding: ECCV 2018 9

The problem of single-view 3D shape completion or reconstruction is
challenging, because among the many possible shapes that explain an
observation, most are implausible and do not correspond to natural objects.
Recent research in the field has tackled this problem by exploiting the
expressiveness of deep convolutional networks. In fact, there is another level
of ambiguity that is often overlooked: among plausible shapes, there are still
multiple shapes that fit the 2D image equally well; i.e., the ground truth
shape is non-deterministic given a single-view input. Existing fully supervised
approaches fail to address this issue, and often produce blurry mean shapes
with smooth surfaces but no fine details.
  In this paper, we propose ShapeHD, pushing the limit of single-view shape
completion and reconstruction by integrating deep generative models with
adversarially learned shape priors. The learned priors serve as a regularizer,
penalizing the model only if its output is unrealistic, not if it deviates from
the ground truth. Our design thus overcomes both levels of ambiguity
aforementioned. Experiments demonstrate that ShapeHD outperforms state of the
art by a large margin in both shape completion and shape reconstruction on
multiple real datasets.
Seeing Tree Structure from Vibration
Authors: Tianfan Xue, Jiajun Wu, Zhoutong Zhang, Chengkai Zhang, Joshua B. Tenenbaum, William T. Freeman
Date: 2018-09-13 00:00:00
Proceeding: ECCV 2018 9
Tasks: Bayesian Inference, Object

Humans recognize object structure from both their appearance and motion;
often, motion helps to resolve ambiguities in object structure that arise when
we observe object appearance only. There are particular scenarios, however,
where neither appearance nor spatial-temporal motion signals are informative:
occluding twigs may look connected and have almost identical movements, though
they belong to different, possibly disconnected branches. We propose to tackle
this problem through spectrum analysis of motion signals, because vibrations of
disconnected branches, though visually similar, often have distinctive natural
frequencies. We propose a novel formulation of tree structure based on a
physics-based link model, and validate its effectiveness by theoretical
analysis, numerical simulation, and empirical experiments. With this
formulation, we use nonparametric Bayesian inference to reconstruct tree
structure from both spectral vibration signals and appearance cues. Our model
performs well in recognizing hierarchical tree structure from real-world videos
of trees and vessels.
IncSQL: Training Incremental Text-to-SQL Parsers with Non-Deterministic Oracles
Authors: Tianze Shi, Kedar Tatwawadi, Kaushik Chakrabarti, Yi Mao, Oleksandr Polozov, Weizhu Chen
Date: 2018-09-13 00:00:00
Tasks: Action Parsing, Text to SQL, Text-To-SQL

We present a sequence-to-action parsing approach for the natural language to
SQL task that incrementally fills the slots of a SQL query with feasible
actions from a pre-defined inventory. To account for the fact that typically
there are multiple correct SQL queries with the same or very similar semantics,
we draw inspiration from syntactic parsing techniques and propose to train our
sequence-to-action models with non-deterministic oracles. We evaluate our
models on the WikiSQL dataset and achieve an execution accuracy of 83.7% on the
test set, a 2.1% absolute improvement over the models trained with traditional
static oracles assuming a single correct target SQL query. When further
combined with the execution-guided decoding strategy, our model sets a new
state-of-the-art performance at an execution accuracy of 87.1%.
XNLI: Evaluating Cross-lingual Sentence Representations
Authors: Alexis Conneau, Guillaume Lample, Ruty Rinott, Adina Williams, Samuel R. Bowman, Holger Schwenk, Veselin Stoyanov
Date: 2018-09-13 00:00:00
Proceeding: EMNLP 2018 10
Tasks: Cross-Lingual Natural Language Inference, Machine Translation, Natural Language Inference, Sentence, Translation

State-of-the-art natural language processing systems rely on supervision in
the form of annotated data to learn competent models. These models are
generally trained on data in a single language (usually English), and cannot be
directly used beyond that language. Since collecting data in every language is
not realistic, there has been a growing interest in cross-lingual language
understanding (XLU) and low-resource cross-language transfer. In this work, we
construct an evaluation set for XLU by extending the development and test sets
of the Multi-Genre Natural Language Inference Corpus (MultiNLI) to 15
languages, including low-resource languages such as Swahili and Urdu. We hope
that our dataset, dubbed XNLI, will catalyze research in cross-lingual sentence
understanding by providing an informative standard evaluation task. In
addition, we provide several baselines for multilingual sentence understanding,
including two based on machine translation systems, and two that use parallel
data to train aligned multilingual bag-of-words and LSTM encoders. We find that
XNLI represents a practical and challenging evaluation suite, and that directly
translating the test data yields the best performance among available
baselines.
Learning to Group and Label Fine-Grained Shape Components
Authors: Xiaogang Wang, Bin Zhou, Haiyue Fang, Xiaowu Chen, Qinping Zhao, Kai Xu
Date: 2018-09-13 00:00:00
Tasks: Segmentation

A majority of stock 3D models in modern shape repositories are assembled with
many fine-grained components. The main cause of such data form is the
component-wise modeling process widely practiced by human modelers. These
modeling components thus inherently reflect some function-based shape
decomposition the artist had in mind during modeling. On the other hand,
modeling components represent an over-segmentation since a functional part is
usually modeled as a multi-component assembly. Based on these observations, we
advocate that labeled segmentation of stock 3D models should not overlook the
modeling components and propose a learning solution to grouping and labeling of
the fine-grained components. However, directly characterizing the shape of
individual components for the purpose of labeling is unreliable, since they can
be arbitrarily tiny and semantically meaningless. We propose to generate part
hypotheses from the components based on a hierarchical grouping strategy, and
perform labeling on those part groups instead of directly on the components.
Part hypotheses are mid-level elements which are more probable to carry
semantic information. A multiscale 3D convolutional neural network is trained
to extract context-aware features for the hypotheses. To accomplish a labeled
segmentation of the whole shape, we formulate higher-order conditional random
fields (CRFs) to infer an optimal label assignment for all components.
Extensive experiments demonstrate that our method achieves significantly robust
labeling results on raw 3D models from public shape repositories. Our work also
contributes the first benchmark for component-wise labeling.
PhD Dissertation: Generalized Independent Components Analysis Over Finite Alphabets
Authors: Amichai Painsky
Date: 2018-09-13 00:00:00

Independent component analysis (ICA) is a statistical method for transforming
an observable multi-dimensional random vector into components that are as
statistically independent as possible from each other. Usually the ICA
framework assumes a model according to which the observations are generated
(such as a linear transformation with additive noise). ICA over finite fields
is a special case of ICA in which both the observations and the independent
components are over a finite alphabet. In this thesis we consider a formulation
of the finite-field case in which an observation vector is decomposed to its
independent components (as much as possible) with no prior assumption on the
way it was generated. This generalization is also known as Barlow's minimal
redundancy representation and is considered an open problem. We propose several
theorems and show that this hard problem can be accurately solved with a branch
and bound search tree algorithm, or tightly approximated with a series of
linear problems. Moreover, we show that there exists a simple transformation
(namely, order permutation) which provides a greedy yet very effective
approximation of the optimal solution. We further show that while not every
random vector can be efficiently decomposed into independent components, the
vast majority of vectors do decompose very well (that is, within a small
constant cost), as the dimension increases. In addition, we show that we may
practically achieve this favorable constant cost with a complexity that is
asymptotically linear in the alphabet size. Our contribution provides the first
efficient set of solutions to Barlow's problem with theoretical and
computational guarantees. Finally, we demonstrate our suggested framework in
multiple source coding applications.
Hamiltonian Descent Methods
Authors: Chris J. Maddison, Daniel Paulin, Yee Whye Teh, Brendan O'Donoghue, Arnaud Doucet
Date: 2018-09-13 00:00:00

We propose a family of optimization methods that achieve linear convergence
using first-order gradient information and constant step sizes on a class of
convex functions much larger than the smooth and strongly convex ones. This
larger class includes functions whose second derivatives may be singular or
unbounded at their minima. Our methods are discretizations of conformal
Hamiltonian dynamics, which generalize the classical momentum method to model
the motion of a particle with non-standard kinetic energy exposed to a
dissipative force and the gradient field of the function of interest. They are
first-order in the sense that they require only gradient computation. Yet,
crucially the kinetic gradient map can be designed to incorporate information
about the convex conjugate in a fashion that allows for linear convergence on
convex functions that may be non-smooth or non-strongly convex. We study in
detail one implicit and two explicit methods. For one explicit method, we
provide conditions under which it converges to stationary points of non-convex
functions. For all, we provide conditions on the convex function and kinetic
energy pair that guarantee linear convergence, and show that these conditions
can be satisfied by functions with power growth. In sum, these methods expand
the class of convex functions on which linear convergence is possible with
first-order computation.