pwc-archive/papers-with-abstracts huggingface dataset:
Make Up Your Mind: The Price of Online Queries in Differential Privacy
Authors: Mark Bun, Thomas Steinke, Jonathan Ullman
Date: 2016-04-15 00:00:00

We consider the problem of answering queries about a sensitive dataset
subject to differential privacy. The queries may be chosen adversarially from a
larger set Q of allowable queries in one of three ways, which we list in order
from easiest to hardest to answer:
  Offline: The queries are chosen all at once and the differentially private
mechanism answers the queries in a single batch.
  Online: The queries are chosen all at once, but the mechanism only receives
the queries in a streaming fashion and must answer each query before seeing the
next query.
  Adaptive: The queries are chosen one at a time and the mechanism must answer
each query before the next query is chosen. In particular, each query may
depend on the answers given to previous queries.
  Many differentially private mechanisms are just as efficient in the adaptive
model as they are in the offline model. Meanwhile, most lower bounds for
differential privacy hold in the offline setting. This suggests that the three
models may be equivalent.
  We prove that these models are all, in fact, distinct. Specifically, we show
that there is a family of statistical queries such that exponentially more
queries from this family can be answered in the offline model than in the
online model. We also exhibit a family of search queries such that
exponentially more queries from this family can be answered in the online model
than in the adaptive model. We also investigate whether such separations might
hold for simple queries like threshold queries over the real line.
On deterministic conditions for subspace clustering under missing data
Authors: Wenqi Wang, Shuchin Aeron, Vaneet Aggarwal
Date: 2016-04-15 00:00:00
Tasks: Clustering

In this paper we present deterministic analysis of sufficient conditions for
sparse subspace clustering under missing data, when data is assumed to come
from a Union of Subspaces (UoS) model. In this context we consider two cases,
namely Case I when all the points are sampled at the same co-ordinates, and
Case II when points are sampled at different locations. We show that results
for Case I directly follow from several existing results in the literature,
while results for Case II are not as straightforward and we provide a set of
dual conditions under which, perfect clustering holds true. We provide
extensive set of simulation results for clustering as well as completion of
data under missing entries, under the UoS model. Our experimental results
indicate that in contrast to the full data case, accurate clustering does not
imply accurate subspace identification and completion, indicating the natural
order of relative hardness of these problems.
Similarity of symbol frequency distributions with heavy tails
Authors: Martin Gerlach, Francesc Font-Clos, Eduardo G. Altmann
Date: 2015-10-01 00:00:00
Tasks: valid

Quantifying the similarity between symbolic sequences is a traditional
problem in Information Theory which requires comparing the frequencies of
symbols in different sequences. In numerous modern applications, ranging from
DNA over music to texts, the distribution of symbol frequencies is
characterized by heavy-tailed distributions (e.g., Zipf's law). The large
number of low-frequency symbols in these distributions poses major difficulties
to the estimation of the similarity between sequences, e.g., they hinder an
accurate finite-size estimation of entropies. Here we show analytically how the
systematic (bias) and statistical (fluctuations) errors in these estimations
depend on the sample size~$N$ and on the exponent~$\gamma$ of the heavy-tailed
distribution. Our results are valid for the Shannon entropy $(\alpha=1)$, its
corresponding similarity measures (e.g., the Jensen-Shanon divergence), and
also for measures based on the generalized entropy of order $\alpha$. For small
$\alpha$'s, including $\alpha=1$, the errors decay slower than the $1/N$-decay
observed in short-tailed distributions. For $\alpha$ larger than a critical
value $\alpha^* = 1+1/\gamma \leq 2$, the $1/N$-decay is recovered. We show the
practical significance of our results by quantifying the evolution of the
English language over the last two centuries using a complete $\alpha$-spectrum
of measures. We find that frequent words change more slowly than less frequent
words and that $\alpha=2$ provides the most robust measure to quantify language
change.
Estimation of low rank density matrices: bounds in Schatten norms and other distances
Authors: Dong Xia, Vladimir Koltchinskii
Date: 2016-04-15 00:00:00

Let ${\mathcal S}_m$ be the set of all $m\times m$ density matrices
(Hermitian positively semi-definite matrices of unit trace). Consider a problem
of estimation of an unknown density matrix $\rho\in {\mathcal S}_m$ based on
outcomes of $n$ measurements of observables $X_1,\dots, X_n\in {\mathbb H}_m$
(${\mathbb H}_m$ being the space of $m\times m$ Hermitian matrices) for a
quantum system identically prepared $n$ times in state $\rho.$ Outcomes
$Y_1,\dots, Y_n$ of such measurements could be described by a trace regression
model in which ${\mathbb E}_{\rho}(Y_j|X_j)={\rm tr}(\rho X_j), j=1,\dots, n.$
The design variables $X_1,\dots, X_n$ are often sampled at random from the
uniform distribution in an orthonormal basis $\{E_1,\dots, E_{m^2}\}$ of
${\mathbb H}_m$ (such as Pauli basis). The goal is to estimate the unknown
density matrix $\rho$ based on the data $(X_1,Y_1), \dots, (X_n,Y_n).$ Let $$
\hat Z:=\frac{m^2}{n}\sum_{j=1}^n Y_j X_j $$ and let $\check \rho$ be the
projection of $\hat Z$ onto the convex set ${\mathcal S}_m$ of density
matrices. It is shown that for estimator $\check \rho$ the minimax lower bounds
in classes of low rank density matrices (established earlier) are attained up
logarithmic factors for all Schatten $p$-norm distances, $p\in [1,\infty]$ and
for Bures version of quantum Hellinger distance. Moreover, for a slightly
modified version of estimator $\check \rho$ the same property holds also for
quantum relative entropy (Kullback-Leibler) distance between density matrices.
Learning Temporal Regularity in Video Sequences
Authors: Mahmudul Hasan, Jonghyun Choi, Jan Neumann, Amit K. Roy-Chowdhury, Larry S. Davis
Date: 2016-04-15 00:00:00
Proceeding: CVPR 2016 6
Tasks: Abnormal Event Detection In Video, Anomaly Detection, Semi-supervised Anomaly Detection, Video Anomaly Detection

Perceiving meaningful activities in a long video sequence is a challenging
problem due to ambiguous definition of 'meaningfulness' as well as clutters in
the scene. We approach this problem by learning a generative model for regular
motion patterns, termed as regularity, using multiple sources with very limited
supervision. Specifically, we propose two methods that are built upon the
autoencoders for their ability to work with little to no supervision. We first
leverage the conventional handcrafted spatio-temporal local features and learn
a fully connected autoencoder on them. Second, we build a fully convolutional
feed-forward autoencoder to learn both the local features and the classifiers
as an end-to-end learning framework. Our model can capture the regularities
from multiple datasets. We evaluate our methods in both qualitative and
quantitative ways - showing the learned regularity of videos in various aspects
and demonstrating competitive performance on anomaly detection datasets as an
application.
CNN-RNN: A Unified Framework for Multi-label Image Classification
Authors: Jiang Wang, Yi Yang, Junhua Mao, Zhiheng Huang, Chang Huang, Wei Xu
Date: 2016-04-15 00:00:00
Proceeding: CVPR 2016 6
Tasks: Classification, General Classification, image-classification, Image Classification, Multi-Label Classification, MUlTI-LABEL-ClASSIFICATION, Multi-Label Image Classification

While deep convolutional neural networks (CNNs) have shown a great success in
single-label image classification, it is important to note that real world
images generally contain multiple labels, which could correspond to different
objects, scenes, actions and attributes in an image. Traditional approaches to
multi-label image classification learn independent classifiers for each
category and employ ranking or thresholding on the classification results.
These techniques, although working well, fail to explicitly exploit the label
dependencies in an image. In this paper, we utilize recurrent neural networks
(RNNs) to address this problem. Combined with CNNs, the proposed CNN-RNN
framework learns a joint image-label embedding to characterize the semantic
label dependency as well as the image-label relevance, and it can be trained
end-to-end from scratch to integrate both information in a unified framework.
Experimental results on public benchmark datasets demonstrate that the proposed
architecture achieves better performance than the state-of-the-art multi-label
classification model
Accessing accurate documents by mining auxiliary document information
Authors: Jinju Joby, Jyothi Korra
Date: 2016-04-15 00:00:00
Tasks: Clustering

Earlier techniques of text mining included algorithms like k-means, Naive
Bayes, SVM which classify and cluster the text document for mining relevant
information about the documents. The need for improving the mining techniques
has us searching for techniques using the available algorithms. This paper
proposes one technique which uses the auxiliary information that is present
inside the text documents to improve the mining. This auxiliary information can
be a description to the content. This information can be either useful or
completely useless for mining. The user should assess the worth of the
auxiliary information before considering this technique for text mining. In
this paper, a combination of classical clustering algorithms is used to mine
the datasets. The algorithm runs in two stages which carry out mining at
different levels of abstraction. The clustered documents would then be
classified based on the necessary groups. The proposed technique is aimed at
improved results of document clustering.
Tracking Human-like Natural Motion Using Deep Recurrent Neural Networks
Authors: Youngbin Park, Sungphill Moon, Il Hong Suh
Date: 2016-04-15 00:00:00
Tasks: Sensor Fusion

Kinect skeleton tracker is able to achieve considerable human body tracking
performance in convenient and a low-cost manner. However, The tracker often
captures unnatural human poses such as discontinuous and vibrated motions when
self-occlusions occur. A majority of approaches tackle this problem by using
multiple Kinect sensors in a workspace. Combination of the measurements from
different sensors is then conducted in Kalman filter framework or optimization
problem is formulated for sensor fusion. However, these methods usually require
heuristics to measure reliability of measurements observed from each Kinect
sensor. In this paper, we developed a method to improve Kinect skeleton using
single Kinect sensor, in which supervised learning technique was employed to
correct unnatural tracking motions. Specifically, deep recurrent neural
networks were used for improving joint positions and velocities of Kinect
skeleton, and three methods were proposed to integrate the refined positions
and velocities for further enhancement. Moreover, we suggested a novel measure
to evaluate naturalness of captured motions. We evaluated the proposed approach
by comparison with the ground truth obtained using a commercial optical
maker-based motion capture system.
Discriminative Predicate Path Mining for Fact Checking in Knowledge Graphs
Authors: Baoxu Shi, Tim Weninger
Date: 2015-10-20 00:00:00
Tasks: Fact Checking, Knowledge Graphs, Link Prediction

Traditional fact checking by experts and analysts cannot keep pace with the
volume of newly created information. It is important and necessary, therefore,
to enhance our ability to computationally determine whether some statement of
fact is true or false. We view this problem as a link-prediction task in a
knowledge graph, and present a discriminative path-based method for fact
checking in knowledge graphs that incorporates connectivity, type information,
and predicate interactions. Given a statement S of the form (subject,
predicate, object), for example, (Chicago, capitalOf, Illinois), our approach
mines discriminative paths that alternatively define the generalized statement
(U.S. city, predicate, U.S. state) and uses the mined rules to evaluate the
veracity of statement S. We evaluate our approach by examining thousands of
claims related to history, geography, biology, and politics using a public,
million node knowledge graph extracted from Wikipedia and PubMedDB. Not only
does our approach significantly outperform related models, we also find that
the discriminative predicate path model is easily interpretable and provides
sensible reasons for the final determination.
Using Deep Learning for Image-Based Plant Disease Detection
Authors: Sharada Prasanna Mohanty, David Hughes, Marcel Salathe
Date: 2016-04-11 00:00:00
Tasks: Deep Learning

Crop diseases are a major threat to food security, but their rapid
identification remains difficult in many parts of the world due to the lack of
the necessary infrastructure. The combination of increasing global smartphone
penetration and recent advances in computer vision made possible by deep
learning has paved the way for smartphone-assisted disease diagnosis. Using a
public dataset of 54,306 images of diseased and healthy plant leaves collected
under controlled conditions, we train a deep convolutional neural network to
identify 14 crop species and 26 diseases (or absence thereof). The trained
model achieves an accuracy of 99.35% on a held-out test set, demonstrating the
feasibility of this approach. When testing the model on a set of images
collected from trusted online sources - i.e. taken under conditions different
from the images used for training - the model still achieves an accuracy of
31.4%. While this accuracy is much higher than the one based on random
selection (2.6%), a more diverse set of training data is needed to improve the
general accuracy. Overall, the approach of training deep learning models on
increasingly large and publicly available image datasets presents a clear path
towards smartphone-assisted crop disease diagnosis on a massive global scale.
Integrating Know-How into the Linked Data Cloud
Authors: Paolo Pareti, Benoit Testu, Ryutaro Ichise, Ewan Klein, Adam Barker
Date: 2016-04-15 00:00:00

This paper presents the first framework for integrating procedural knowledge,
or "know-how", into the Linked Data Cloud. Know-how available on the Web, such
as step-by-step instructions, is largely unstructured and isolated from other
sources of online knowledge. To overcome these limitations, we propose
extending to procedural knowledge the benefits that Linked Data has already
brought to representing, retrieving and reusing declarative knowledge. We
describe a framework for representing generic know-how as Linked Data and for
automatically acquiring this representation from existing resources on the Web.
This system also allows the automatic generation of links between different
know-how resources, and between those resources and other online knowledge
bases, such as DBpedia. We discuss the results of applying this framework to a
real-world scenario and we show how it outperforms existing manual
community-driven integration efforts.
A short note on extension theorems and their connection to universal consistency in machine learning
Authors: Andreas Christmann, Florian Dumpert, Dao-Hong Xiang
Date: 2016-04-15 00:00:00
Tasks: BIG-bench Machine Learning

Statistical machine learning plays an important role in modern statistics and
computer science. One main goal of statistical machine learning is to provide
universally consistent algorithms, i.e., the estimator converges in probability
or in some stronger sense to the Bayes risk or to the Bayes decision function.
Kernel methods based on minimizing the regularized risk over a reproducing
kernel Hilbert space (RKHS) belong to these statistical machine learning
methods. It is in general unknown which kernel yields optimal results for a
particular data set or for the unknown probability measure. Hence various
kernel learning methods were proposed to choose the kernel and therefore also
its RKHS in a data adaptive manner. Nevertheless, many practitioners often use
the classical Gaussian RBF kernel or certain Sobolev kernels with good success.
The goal of this short note is to offer one possible theoretical explanation
for this empirical fact.
Probing the Intra-Component Correlations within Fisher Vector for Material Classification
Authors: Xiaopeng Hong, Xianbiao Qi, Guoying Zhao, Matti Pietikäinen
Date: 2016-04-15 00:00:00
Tasks: General Classification, Material Classification

Fisher vector (FV) has become a popular image representation. One notable
underlying assumption of the FV framework is that local descriptors are well
decorrelated within each cluster so that the covariance matrix for each
Gaussian can be simplified to be diagonal. Though the FV usually relies on the
Principal Component Analysis (PCA) to decorrelate local features, the PCA is
applied to the entire training data and hence it only diagonalizes the
\textit{universal} covariance matrix, rather than those w.r.t. the local
components. As a result, the local decorrelation assumption is usually not
supported in practice.
  To relax this assumption, this paper proposes a completed model of the Fisher
vector, which is termed as the Completed Fisher vector (CFV). The CFV is a more
general framework of the FV, since it encodes not only the variances but also
the correlations of the whitened local descriptors. The CFV thus leads to
improved discriminative power. We take the task of material categorization as
an example and experimentally show that: 1) the CFV outperforms the FV under
all parameter settings; 2) the CFV is robust to the changes in the number of
components in the mixture; 3) even with a relatively small visual vocabulary
the CFV still works well on two challenging datasets.
Bayesian linear regression with Student-t assumptions
Authors: Chaobing Song, Shu-Tao Xia
Date: 2016-04-15 00:00:00
Tasks: regression

As an automatic method of determining model complexity using the training
data alone, Bayesian linear regression provides us a principled way to select
hyperparameters. But one often needs approximation inference if distribution
assumption is beyond Gaussian distribution. In this paper, we propose a
Bayesian linear regression model with Student-t assumptions (BLRS), which can
be inferred exactly. In this framework, both conjugate prior and expectation
maximization (EM) algorithm are generalized. Meanwhile, we prove that the
maximum likelihood solution is equivalent to the standard Bayesian linear
regression with Gaussian assumptions (BLRG). The $q$-EM algorithm for BLRS is
nearly identical to the EM algorithm for BLRG. It is showed that $q$-EM for
BLRS can converge faster than EM for BLRG for the task of predicting online
news popularity.
Co-Localization of Audio Sources in Images Using Binaural Features and Locally-Linear Regression
Authors: Antoine Deleforge, Radu Horaud, Yoav Schechner, Laurent Girin
Date: 2014-08-12 00:00:00
Tasks: regression

This paper addresses the problem of localizing audio sources using binaural
measurements. We propose a supervised formulation that simultaneously localizes
multiple sources at different locations. The approach is intrinsically
efficient because, contrary to prior work, it relies neither on source
separation, nor on monaural segregation. The method starts with a training
stage that establishes a locally-linear Gaussian regression model between the
directional coordinates of all the sources and the auditory features extracted
from binaural measurements. While fixed-length wide-spectrum sounds (white
noise) are used for training to reliably estimate the model parameters, we show
that the testing (localization) can be extended to variable-length
sparse-spectrum sounds (such as speech), thus enabling a wide range of
realistic applications. Indeed, we demonstrate that the method can be used for
audio-visual fusion, namely to map speech signals onto images and hence to
spatially align the audio and visual modalities, thus enabling to discriminate
between speaking and non-speaking faces. We release a novel corpus of real-room
recordings that allow quantitative evaluation of the co-localization method in
the presence of one or two sound sources. Experiments demonstrate increased
accuracy and speed relative to several state-of-the-art methods.
Automatically Proving Mathematical Theorems with Evolutionary Algorithms and Proof Assistants
Authors: Li-An Yang, Jui-Pin Liu, Chao-Hong Chen, Ying-ping Chen
Date: 2016-02-24 00:00:00
Tasks: Evolutionary Algorithms, Sentence

Mathematical theorems are human knowledge able to be accumulated in the form
of symbolic representation, and proving theorems has been considered
intelligent behavior. Based on the BHK interpretation and the Curry-Howard
isomorphism, proof assistants, software capable of interacting with human for
constructing formal proofs, have been developed in the past several decades.
Since proofs can be considered and expressed as programs, proof assistants
simplify and verify a proof by computationally evaluating the program
corresponding to the proof. Thanks to the transformation from logic to
computation, it is now possible to generate or search for formal proofs
directly in the realm of computation. Evolutionary algorithms, known to be
flexible and versatile, have been successfully applied to handle a variety of
scientific and engineering problems in numerous disciplines for also several
decades. Examining the feasibility of establishing the link between
evolutionary algorithms, as the program generator, and proof assistants, as the
proof verifier, in order to automatically find formal proofs to a given logic
sentence is the primary goal of this study. In the article, we describe in
detail our first, ad-hoc attempt to fully automatically prove theorems as well
as the preliminary results. Ten simple theorems from various branches of
mathematics were proven, and most of these theorems cannot be proven by using
the tactic auto alone in Coq, the adopted proof assistant. The implication and
potential influence of this study are discussed, and the developed source code
with the obtained experimental results are released as open source.
Preference Elicitation For Single Crossing Domain
Authors: Palash Dey, Neeldhara Misra
Date: 2016-04-15 00:00:00

Eliciting the preferences of a set of agents over a set of alternatives is a
problem of fundamental importance in social choice theory. Prior work on this
problem has studied the query complexity of preference elicitation for the
unrestricted domain and for the domain of single peaked preferences. In this
paper, we consider the domain of single crossing preference profiles and study
the query complexity of preference elicitation under various settings. We
consider two distinct situations: when an ordering of the voters with respect
to which the profile is single crossing is known versus when it is unknown. We
also consider different access models: when the votes can be accessed at
random, as opposed to when they are coming in a pre-defined sequence. In the
sequential access model, we distinguish two cases when the ordering is known:
the first is that sequence in which the votes appear is also a single-crossing
order, versus when it is not.
  The main contribution of our work is to provide polynomial time algorithms
with low query complexity for preference elicitation in all the above six
cases. Further, we show that the query complexities of our algorithms are
optimal up to constant factors for all but one of the above six cases. We then
present preference elicitation algorithms for profiles which are close to being
single crossing under various notions of closeness, for example, single
crossing width, minimum number of candidates | voters whose deletion makes a
profile single crossing.