pwc-archive/papers-with-abstracts huggingface dataset:
Robust Gaussian Graphical Modeling with the Trimmed Graphical Lasso
Authors: Eunho Yang, Aurélie C. Lozano
Date: 2015-10-28 00:00:00
Proceeding: NeurIPS 2015 12
Tasks: regression

Gaussian Graphical Models (GGMs) are popular tools for studying network
structures. However, many modern applications such as gene network discovery
and social interactions analysis often involve high-dimensional noisy data with
outliers or heavier tails than the Gaussian distribution. In this paper, we
propose the Trimmed Graphical Lasso for robust estimation of sparse GGMs. Our
method guards against outliers by an implicit trimming mechanism akin to the
popular Least Trimmed Squares method used for linear regression. We provide a
rigorous statistical analysis of our estimator in the high-dimensional setting.
In contrast, existing approaches for robust sparse GGMs estimation lack
statistical guarantees. Our theoretical results are complemented by experiments
on simulated and real gene expression data which further demonstrate the value
of our approach.
Emoticons vs. Emojis on Twitter: A Causal Inference Approach
Authors: Umashanthi Pavalanathan, Jacob Eisenstein
Date: 2015-10-28 00:00:00
Tasks: Causal Inference

Online writing lacks the non-verbal cues present in face-to-face
communication, which provide additional contextual information about the
utterance, such as the speaker's intention or affective state. To fill this
void, a number of orthographic features, such as emoticons, expressive
lengthening, and non-standard punctuation, have become popular in social media
services including Twitter and Instagram. Recently, emojis have been introduced
to social media, and are increasingly popular. This raises the question of
whether these predefined pictographic characters will come to replace earlier
orthographic methods of paralinguistic communication. In this abstract, we
attempt to shed light on this question, using a matching approach from causal
inference to test whether the adoption of emojis causes individual users to
employ fewer emoticons in their text on Twitter.
Toward Long Distance, Sub-diffraction Imaging Using Coherent Camera Arrays
Authors: Jason Holloway, M. Salman Asif, Manoj Kumar Sharma, Nathan Matsuda, Roarke Horstmeyer, Oliver Cossairt, Ashok Veeraraghavan
Date: 2015-10-28 00:00:00
Tasks: Retrieval, Translation

In this work, we propose using camera arrays coupled with coherent
illumination as an effective method of improving spatial resolution in long
distance images by a factor of ten and beyond. Recent advances in ptychography
have demonstrated that one can image beyond the diffraction limit of the
objective lens in a microscope. We demonstrate a similar imaging system to
image beyond the diffraction limit in long range imaging. We emulate a camera
array with a single camera attached to an X-Y translation stage. We show that
an appropriate phase retrieval based reconstruction algorithm can be used to
effectively recover the lost high resolution details from the multiple low
resolution acquired images. We analyze the effects of noise, required degree of
image overlap, and the effect of increasing synthetic aperture size on the
reconstructed image quality. We show that coherent camera arrays have the
potential to greatly improve imaging performance. Our simulations show
resolution gains of 10x and more are achievable. Furthermore, experimental
results from our proof-of-concept systems show resolution gains of 4x-7x for
real scenes. Finally, we introduce and analyze in simulation a new strategy to
capture macroscopic Fourier Ptychography images in a single snapshot, albeit
using a camera array.
Fast k-best Sentence Compression
Authors: Katja Filippova, Enrique Alfonseca
Date: 2015-10-28 00:00:00
Tasks: Sentence, Sentence Compression

A popular approach to sentence compression is to formulate the task as a
constrained optimization problem and solve it with integer linear programming
(ILP) tools. Unfortunately, dependence on ILP may make the compressor
prohibitively slow, and thus approximation techniques have been proposed which
are often complex and offer a moderate gain in speed. As an alternative
solution, we introduce a novel compression algorithm which generates k-best
compressions relying on local deletion decisions. Our algorithm is two orders
of magnitude faster than a recent ILP-based method while producing better
compressions. Moreover, an extensive evaluation demonstrates that the quality
of compressions does not degrade much as we move from single best to top-five
results.
Communication Complexity of Distributed Convex Learning and Optimization
Authors: Yossi Arjevani, Ohad Shamir
Date: 2015-06-05 00:00:00
Proceeding: NeurIPS 2015 12

We study the fundamental limits to communication-efficient distributed
methods for convex learning and optimization, under different assumptions on
the information available to individual machines, and the types of functions
considered. We identify cases where existing algorithms are already worst-case
optimal, as well as cases where room for further improvement is still possible.
Among other things, our results indicate that without similarity between the
local objective functions (due to statistical data similarity or otherwise)
many communication rounds may be required, even if the machines have unbounded
computational power.
Fast Landmark Subspace Clustering
Authors: Xu Wang, Gilad Lerman
Date: 2015-10-28 00:00:00
Tasks: Clustering

Kernel methods obtain superb performance in terms of accuracy for various
machine learning tasks since they can effectively extract nonlinear relations.
However, their time complexity can be rather large especially for clustering
tasks. In this paper we define a general class of kernels that can be easily
approximated by randomization. These kernels appear in various applications, in
particular, traditional spectral clustering, landmark-based spectral clustering
and landmark-based subspace clustering. We show that for $n$ data points from
$K$ clusters with $D$ landmarks, the randomization procedure results in an
algorithm of complexity $O(KnD)$. Furthermore, we bound the error between the
original clustering scheme and its randomization. To illustrate the power of
this framework, we propose a new fast landmark subspace (FLS) clustering
algorithm. Experiments over synthetic and real datasets demonstrate the
superior performance of FLS in accelerating subspace clustering with marginal
sacrifice of accuracy.
Efficient refinement of GPS-based localization in urban areas using visual information and sensor parameter
Authors: Mahdi Salarian, Rashid Ansari
Date: 2015-02-01 00:00:00
Tasks: Image Retrieval, Retrieval

An efficient method is proposed for refining GPS-acquired location
coordinates in urban areas using camera images, Google Street View (GSV) and
sensor parameters. The main goal is to compensate for GPS location imprecision
in dense area of cities due to proximity to walls and buildings. Avail-able
methods for better localization often use visual information by using query
images acquired with camera-equipped mobile devices and applying image
retrieval techniques to find the closest match in a GPS-referenced image data
set. The search areas required for reliable search are about 1-2 sq. Km and the
accuracy is typically 25-100 meters. Here we describe a method based on image
retrieval where a reliable search can be confined to areas of 0.01 sq. Km and
the accuracy in our experiments is less than 10 meters. To test our procedure
we created a database by acquiring all Google Street View images close to what
is seen by a pedestrian in a large region of downtown Chicago and saved all
coordinates and orientation data to be used for confining our search region.
Prior knowledge from approximate position of query image is leveraged to
address complexity and accuracy issues of our search in a large scale
geo-tagged data set. One key aspect that differentiates our work is that it
utilizes the sensor information of GPS SOS and the camera orientation in
improving localization. Finally we demonstrate retrieval-based technique are
less accurate in sparse open areas compared with purely GPS measurement. The
effectiveness of our approach is discussed in detail and experimental results
show improved performance when compared with regular approaches.
Universal Dependency Analysis
Authors: Hoang-Vu Nguyen, Jilles Vreeken
Date: 2015-10-28 00:00:00

Most data is multi-dimensional. Discovering whether any subset of dimensions,
or subspaces, of such data is significantly correlated is a core task in data
mining. To do so, we require a measure that quantifies how correlated a
subspace is. For practical use, such a measure should be universal in the sense
that it captures correlation in subspaces of any dimensionality and allows to
meaningfully compare correlation scores across different subspaces, regardless
how many dimensions they have and what specific statistical properties their
dimensions possess. Further, it would be nice if the measure can
non-parametrically and efficiently capture both linear and non-linear
correlations.
  In this paper, we propose UDS, a multivariate correlation measure that
fulfills all of these desiderata. In short, we define \uds based on cumulative
entropy and propose a principled normalization scheme to bring its scores
across different subspaces to the same domain, enabling universal correlation
assessment. UDS is purely non-parametric as we make no assumption on data
distributions nor types of correlation. To compute it on empirical data, we
introduce an efficient and non-parametric method. Extensive experiments show
that UDS outperforms state of the art.
Linear-time Detection of Non-linear Changes in Massively High Dimensional Time Series
Authors: Hoang-Vu Nguyen, Jilles Vreeken
Date: 2015-10-28 00:00:00
Tasks: Change Detection, Time Series, Time Series Analysis

Change detection in multivariate time series has applications in many
domains, including health care and network monitoring. A common approach to
detect changes is to compare the divergence between the distributions of a
reference window and a test window. When the number of dimensions is very
large, however, the naive approach has both quality and efficiency issues: to
ensure robustness the window size needs to be large, which not only leads to
missed alarms but also increases runtime.
  To this end, we propose LIGHT, a linear-time algorithm for robustly detecting
non-linear changes in massively high dimensional time series. Importantly,
LIGHT provides high flexibility in choosing the window size, allowing the
domain expert to fit the level of details required. To do such, we 1) perform
scalable PCA to reduce dimensionality, 2) perform scalable factorization of the
joint distribution, and 3) scalably compute divergences between these lower
dimensional distributions. Extensive empirical evaluation on both synthetic and
real-world data show that LIGHT outperforms state of the art with up to 100%
improvement in both quality and efficiency.
Flexibly Mining Better Subgroups
Authors: Hoang-Vu Nguyen, Jilles Vreeken
Date: 2015-10-28 00:00:00
Tasks: Attribute, Subgroup Discovery

In subgroup discovery, also known as supervised pattern mining, discovering
high quality one-dimensional subgroups and refinements of these is a crucial
task. For nominal attributes, this is relatively straightforward, as we can
consider individual attribute values as binary features. For numerical
attributes, the task is more challenging as individual numeric values are not
reliable statistics. Instead, we can consider combinations of adjacent values,
i.e. bins. Existing binning strategies, however, are not tailored for subgroup
discovery. That is, they do not directly optimize for the quality of subgroups,
therewith potentially degrading the mining result.
  To address this issue, we propose FLEXI. In short, with FLEXI we propose to
use optimal binning to find high quality binary features for both numeric and
ordinal attributes. We instantiate FLEXI with various quality measures and show
how to achieve efficiency accordingly. Experiments on both synthetic and
real-world data sets show that FLEXI outperforms state of the art with up to 25
times improvement in subgroup quality.
Canonical Divergence Analysis
Authors: Hoang-Vu Nguyen, Jilles Vreeken
Date: 2015-10-28 00:00:00

We aim to analyze the relation between two random vectors that may
potentially have both different number of attributes as well as realizations,
and which may even not have a joint distribution. This problem arises in many
practical domains, including biology and architecture. Existing techniques
assume the vectors to have the same domain or to be jointly distributed, and
hence are not applicable. To address this, we propose Canonical Divergence
Analysis (CDA). We introduce three instantiations, each of which permits
practical implementation. Extensive empirical evaluation shows the potential of
our method.
A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
Authors: Kejun Huang, Nicholas D. Sidiropoulos, Athanasios P. Liavas
Date: 2015-06-13 00:00:00
Tasks: Dictionary Learning

We propose a general algorithmic framework for constrained matrix and tensor
factorization, which is widely used in signal processing and machine learning.
The new framework is a hybrid between alternating optimization (AO) and the
alternating direction method of multipliers (ADMM): each matrix factor is
updated in turn, using ADMM, hence the name AO-ADMM. This combination can
naturally accommodate a great variety of constraints on the factor matrices,
and almost all possible loss measures for the fitting. Computation caching and
warm start strategies are used to ensure that each update is evaluated
efficiently, while the outer AO framework exploits recent developments in block
coordinate descent (BCD)-type methods which help ensure that every limit point
is a stationary point, as well as faster and more robust convergence in
practice. Three special cases are studied in detail: non-negative matrix/tensor
factorization, constrained matrix/tensor completion, and dictionary learning.
Extensive simulations and experiments with real data are used to showcase the
effectiveness and broad applicability of the proposed framework.
Extreme Compressive Sampling for Covariance Estimation
Authors: Martin Azizyan, Akshay Krishnamurthy, Aarti Singh
Date: 2015-06-02 00:00:00

This paper studies the problem of estimating the covariance of a collection
of vectors using only highly compressed measurements of each vector. An
estimator based on back-projections of these compressive samples is proposed
and analyzed. A distribution-free analysis shows that by observing just a
single linear measurement of each vector, one can consistently estimate the
covariance matrix, in both infinity and spectral norm, and this same analysis
leads to precise rates of convergence in both norms. Via information-theoretic
techniques, lower bounds showing that this estimator is minimax-optimal for
both infinity and spectral norm estimation problems are established. These
results are also specialized to give matching upper and lower bounds for
estimating the population covariance of a collection of Gaussian vectors, again
in the compressive measurement model. The analysis conducted in this paper
shows that the effective sample complexity for this problem is scaled by a
factor of $m^2/d^2$ where $m$ is the compression dimension and $d$ is the
ambient dimension. Applications to subspace learning (Principal Components
Analysis) and learning over distributed sensor networks are also discussed.
CBAS: context based arabic stemmer
Authors: Mahmoud El-Defrawy, Yasser El-Sonbaty, Nahla A. Belal
Date: 2015-10-28 00:00:00

Arabic morphology encapsulates many valuable features such as word root.
Arabic roots are being utilized for many tasks; the process of extracting a
word root is referred to as stemming. Stemming is an essential part of most
Natural Language Processing tasks, especially for derivative languages such as
Arabic. However, stemming is faced with the problem of ambiguity, where two or
more roots could be extracted from the same word. On the other hand,
distributional semantics is a powerful co-occurrence model. It captures the
meaning of a word based on its context. In this paper, a distributional
semantics model utilizing Smoothed Pointwise Mutual Information (SPMI) is
constructed to investigate its effectiveness on the stemming analysis task. It
showed an accuracy of 81.5%, with a at least 9.4% improvement over other
stemmers.
Evaluating accuracy of community detection using the relative normalized mutual information
Authors: Pan Zhang
Date: 2015-01-15 00:00:00
Tasks: Community Detection

The Normalized Mutual Information (NMI) has been widely used to evaluate the
accuracy of community detection algorithms. However in this article we show
that the NMI is seriously affected by systematic errors due to finite size of
networks, and may give a wrong estimate of performance of algorithms in some
cases. We give a simple theory to the finite-size effect of NMI and test our
theory numerically. Then we propose a new metric for the accuracy of community
detection, namely the relative Normalized Mutual Information (rNMI), which
considers statistical significance of the NMI by comparing it with the expected
NMI of random partitions. Our numerical experiments show that the rNMI
overcomes the finite-size effect of the NMI.
Qualitative Projection Using Deep Neural Networks
Authors: Andrew J. R. Simpson
Date: 2015-10-19 00:00:00

Deep neural networks (DNN) abstract by demodulating the output of linear
filters. In this article, we refine this definition of abstraction to show that
the inputs of a DNN are abstracted with respect to the filters. Or, to restate,
the abstraction is qualified by the filters. This leads us to introduce the
notion of qualitative projection. We use qualitative projection to abstract
MNIST hand-written digits with respect to the various dogs, horses, planes and
cars of the CIFAR dataset. We then classify the MNIST digits according to the
magnitude of their dogness, horseness, planeness and carness qualities,
illustrating the generality of qualitative projection.
Fully adaptive density-based clustering
Authors: Ingo Steinwart
Date: 2014-09-30 00:00:00
Tasks: Clustering

The clusters of a distribution are often defined by the connected components
of a density level set. However, this definition depends on the user-specified
level. We address this issue by proposing a simple, generic algorithm, which
uses an almost arbitrary level set estimator to estimate the smallest level at
which there are more than one connected components. In the case where this
algorithm is fed with histogram-based level set estimates, we provide a finite
sample analysis, which is then used to show that the algorithm consistently
estimates both the smallest level and the corresponding connected components.
We further establish rates of convergence for the two estimation problems, and
last but not least, we present a simple, yet adaptive strategy for determining
the width-parameter of the involved density estimator in a data-depending way.
Beyond Convexity: Stochastic Quasi-Convex Optimization
Authors: Elad Hazan, Kfir. Y. Levy, Shai Shalev-Shwartz
Date: 2015-07-08 00:00:00
Proceeding: NeurIPS 2015 12

Stochastic convex optimization is a basic and well studied primitive in
machine learning. It is well known that convex and Lipschitz functions can be
minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized
Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which
updates according to the direction of the gradients, rather than the gradients
themselves. In this paper we analyze a stochastic version of NGD and prove its
convergence to a global minimum for a wider class of functions: we require the
functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens
the con- cept of unimodality to multidimensions and allows for certain types of
saddle points, which are a known hurdle for first-order optimization methods
such as gradient descent. Locally-Lipschitz functions are only required to be
Lipschitz in a small region around the optimum. This assumption circumvents
gradient explosion, which is another known hurdle for gradient descent
variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic
normalized gradient descent algorithm provably requires a minimal minibatch
size.
Generalized Categorization Axioms
Authors: Jian Yu
Date: 2015-03-31 00:00:00
Tasks: BIG-bench Machine Learning, Clustering, Density Estimation, Dimensionality Reduction

Categorization axioms have been proposed to axiomatizing clustering results,
which offers a hint of bridging the difference between human recognition system
and machine learning through an intuitive observation: an object should be
assigned to its most similar category. However, categorization axioms cannot be
generalized into a general machine learning system as categorization axioms
become trivial when the number of categories becomes one. In order to
generalize categorization axioms into general cases, categorization input and
categorization output are reinterpreted by inner and outer category
representation. According to the categorization reinterpretation, two category
representation axioms are presented. Category representation axioms and
categorization axioms can be combined into a generalized categorization
axiomatic framework, which accurately delimit the theoretical categorization
constraints and overcome the shortcoming of categorization axioms. The proposed
axiomatic framework not only discuses categorization test issue but also
reinterprets many results in machine learning in a unified way, such as
dimensionality reduction,density estimation, regression, clustering and
classification.
Fast and Scalable Structural SVM with Slack Rescaling
Authors: Heejin Choi, Ofer Meshi, Nathan Srebro
Date: 2015-10-20 00:00:00

We present an efficient method for training slack-rescaled structural SVM.
Although finding the most violating label in a margin-rescaled formulation is
often easy since the target function decomposes with respect to the structure,
this is not the case for a slack-rescaled formulation, and finding the most
violated label might be very difficult. Our core contribution is an efficient
method for finding the most-violating-label in a slack-rescaled formulation,
given an oracle that returns the most-violating-label in a (slightly modified)
margin-rescaled formulation. We show that our method enables accurate and
scalable training for slack-rescaled SVMs, reducing runtime by an order of
magnitude compared to previous approaches to slack-rescaled SVMs.
Spectral Convergence Rate of Graph Laplacian
Authors: Xu Wang
Date: 2015-10-27 00:00:00
Tasks: Clustering, Denoising

Laplacian Eigenvectors of the graph constructed from a data set are used in
many spectral manifold learning algorithms such as diffusion maps and spectral
clustering. Given a graph constructed from a random sample of a $d$-dimensional
compact submanifold $M$ in $\mathbb{R}^D$, we establish the spectral
convergence rate of the graph Laplacian. It implies the consistency of the
spectral clustering algorithm via a standard perturbation argument. A simple
numerical study indicates the necessity of a denoising step before applying
spectral algorithms.