pwc-archive/papers-with-abstracts huggingface dataset:
Dimensionality Reduction of Affine Variational Inequalities Using Random Projections
Authors: Bharat Prabhakar, Ankur A. Kulkarni
Date: 2014-08-20 00:00:00
Tasks: Dimensionality Reduction, LEMMA

We present a method for dimensionality reduction of an affine variational
inequality (AVI) defined over a compact feasible region. Centered around the
Johnson Lindenstrauss lemma, our method is a randomized algorithm that produces
with high probability an approximate solution for the given AVI by solving a
lower-dimensional AVI. The algorithm allows the lower dimension to be chosen
based on the quality of approximation desired. The algorithm can also be used
as a subroutine in an exact algorithm for generating an initial point close to
the solution. The lower-dimensional AVI is obtained by appropriately projecting
the original AVI on a randomly chosen subspace. The lower-dimensional AVI is
solved using standard solvers and from this solution an approximate solution to
the original AVI is recovered through an inexpensive process. Our numerical
experiments corroborate the theoretical results and validate that the algorithm
provides a good approximation at low dimensions and substantial savings in time
for an exact solution.
Parallax Effect Free Mosaicing of Underwater Video Sequence Based on Texture Features
Authors: Nagaraja S., Prabhakar C. J., Praveen Kumar P. U
Date: 2014-11-08 00:00:00

In this paper, we present feature-based technique for construction of mosaic
image from underwater video sequence, which suffers from parallax distortion
due to propagation properties of light in the underwater environment. The most
of the available mosaic tools and underwater image mosaicing techniques yields
final result with some artifacts such as blurring, ghosting and seam due to
presence of parallax in the input images. The removal of parallax from input
images may not reduce its effects instead it must be corrected in successive
steps of mosaicing. Thus, our approach minimizes the parallax effects by
adopting an efficient local alignment technique after global registration. We
extract texture features using Centre Symmetric Local Binary Pattern (CS-LBP)
descriptor in order to find feature correspondences, which are used further for
estimation of homography through RANSAC. In order to increase the accuracy of
global registration, we perform preprocessing such as colour alignment between
two selected frames based on colour distribution adjustment. Because of
existence of 100% overlap in consecutive frames of underwater video, we select
frames with minimum overlap based on mutual offset in order to reduce the
computation cost during mosaicing. Our approach minimizes the parallax effects
considerably in final mosaic constructed using our own underwater video
sequences.
On Communication Cost of Distributed Statistical Estimation and Dimensionality
Authors: Ankit Garg, Tengyu Ma, Huy L. Nguyen
Date: 2014-05-07 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: parameter estimation

We explore the connection between dimensionality and communication cost in
distributed learning problems. Specifically we study the problem of estimating
the mean $\vec{\theta}$ of an unknown $d$ dimensional gaussian distribution in
the distributed setting. In this problem, the samples from the unknown
distribution are distributed among $m$ different machines. The goal is to
estimate the mean $\vec{\theta}$ at the optimal minimax rate while
communicating as few bits as possible. We show that in this setting, the
communication cost scales linearly in the number of dimensions i.e. one needs
to deal with different dimensions individually. Applying this result to
previous lower bounds for one dimension in the interactive setting
\cite{ZDJW13} and to our improved bounds for the simultaneous setting, we prove
new lower bounds of $\Omega(md/\log(m))$ and $\Omega(md)$ for the bits of
communication needed to achieve the minimax squared loss, in the interactive
and simultaneous settings respectively. To complement, we also demonstrate an
interactive protocol achieving the minimax squared loss with $O(md)$ bits of
communication, which improves upon the simple simultaneous protocol by a
logarithmic factor. Given the strong lower bounds in the general setting, we
initiate the study of the distributed parameter estimation problems with
structured parameters. Specifically, when the parameter is promised to be
$s$-sparse, we show a simple thresholding based protocol that achieves the same
squared loss while saving a $d/s$ factor of communication. We conjecture that
the tradeoff between communication and squared loss demonstrated by this
protocol is essentially optimal up to logarithmic factor.
A Novel Approach to Develop a New Hybrid Technique for Trademark Image Retrieval
Authors: Saurabh Agarwal, Punit Kumar Johari
Date: 2014-11-08 00:00:00
Tasks: Image Retrieval, Retrieval

Trademark Image Retrieval is playing a vital role as a part of CBIR System.
Trademark is of great significance because it carries the status value of any
company. To retrieve such a fake or copied trademark we design a retrieval
system which is based on hybrid techniques. It contains a mixture of two
different feature vector which combined together to give a suitable retrieval
system. In the proposed system we extract the corner feature which is applied
on an edge pixel image. This feature is used to extract the relevant image and
to more purify the result we apply other feature which is the invariant moment
feature. From the experimental result we conclude that the system is 85 percent
efficient.
Online Collaborative-Filtering on Graphs
Authors: Siddhartha Banerjee, Sujay Sanghavi, Sanjay Shakkottai
Date: 2014-11-07 00:00:00
Tasks: Collaborative Filtering, Recommendation Systems

A common phenomena in modern recommendation systems is the use of feedback
from one user to infer the `value' of an item to other users. This results in
an exploration vs. exploitation trade-off, in which items of possibly low value
have to be presented to users in order to ascertain their value. Existing
approaches to solving this problem focus on the case where the number of items
are small, or admit some underlying structure -- it is unclear, however, if
good recommendation is possible when dealing with content-rich settings with
unstructured content.
  We consider this problem under a simple natural model, wherein the number of
items and the number of item-views are of the same order, and an `access-graph'
constrains which user is allowed to see which item. Our main insight is that
the presence of the access-graph in fact makes good recommendation possible --
however this requires the exploration policy to be designed to take advantage
of the access-graph. Our results demonstrate the importance of `serendipity' in
exploration, and how higher graph-expansion translates to a higher quality of
recommendations; it also suggests a reason why in some settings, simple
policies like Twitter's `Latest-First' policy achieve a good performance.
  From a technical perspective, our model presents a way to study
exploration-exploitation tradeoffs in settings where the number of `trials' and
`strategies' are large (potentially infinite), and more importantly, of the
same order. Our algorithms admit competitive-ratio guarantees which hold for
the worst-case user, under both finite-population and infinite-horizon
settings, and are parametrized in terms of properties of the underlying graph.
Conversely, we also demonstrate that improperly-designed policies can be highly
sub-optimal, and that in many settings, our results are order-wise optimal.
Multivariate f-Divergence Estimation With Confidence
Authors: Kevin R. Moon, Alfred O. Hero III
Date: 2014-11-07 00:00:00
Tasks: General Classification

The problem of f-divergence estimation is important in the fields of machine
learning, information theory, and statistics. While several nonparametric
divergence estimators exist, relatively few have known convergence properties.
In particular, even for those estimators whose MSE convergence rates are known,
the asymptotic distributions are unknown. We establish the asymptotic normality
of a recently proposed ensemble estimator of f-divergence between two
distributions from a finite number of samples. This estimator has MSE
convergence rate of O(1/T), is simple to implement, and performs well in high
dimensions. This theory enables us to perform divergence-based inference tasks
such as testing equality of pairs of distributions based on empirical samples.
We experimentally validate our theoretical results and, as an illustration, use
them to empirically bound the best achievable classification error.
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
Authors: Boaz Barak, Jonathan A. Kelner, David Steurer
Date: 2014-07-06 00:00:00
Tasks: Dictionary Learning, Tensor Decomposition

We give a new approach to the dictionary learning (also known as "sparse
coding") problem of recovering an unknown $n\times m$ matrix $A$ (for $m \geq
n$) from examples of the form \[ y = Ax + e, \] where $x$ is a random vector in
$\mathbb R^m$ with at most $\tau m$ nonzero coordinates, and $e$ is a random
noise vector in $\mathbb R^n$ with bounded magnitude. For the case $m=O(n)$,
our algorithm recovers every column of $A$ within arbitrarily good constant
accuracy in time $m^{O(\log m/\log(\tau^{-1}))}$, in particular achieving
polynomial time if $\tau = m^{-\delta}$ for any $\delta>0$, and time $m^{O(\log
m)}$ if $\tau$ is (a sufficiently small) constant. Prior algorithms with
comparable assumptions on the distribution required the vector $x$ to be much
sparser---at most $\sqrt{n}$ nonzero coordinates---and there were intrinsic
barriers preventing these algorithms from applying for denser $x$.
  We achieve this by designing an algorithm for noisy tensor decomposition that
can recover, under quite general conditions, an approximate rank-one
decomposition of a tensor $T$, given access to a tensor $T'$ that is
$\tau$-close to $T$ in the spectral norm (when considered as a matrix). To our
knowledge, this is the first algorithm for tensor decomposition that works in
the constant spectral-norm noise regime, where there is no guarantee that the
local optima of $T$ and $T'$ have similar structures.
  Our algorithm is based on a novel approach to using and analyzing the Sum of
Squares semidefinite programming hierarchy (Parrilo 2000, Lasserre 2001), and
it can be viewed as an indication of the utility of this very general and
powerful tool for unsupervised learning problems.
Scalable Variational Gaussian Process Classification
Authors: James Hensman, Alex Matthews, Zoubin Ghahramani
Date: 2014-11-07 00:00:00
Tasks: Classification, General Classification

Gaussian process classification is a popular method with a number of
appealing properties. We show how to scale the model within a variational
inducing point framework, outperforming the state of the art on benchmark
datasets. Importantly, the variational formulation can be exploited to allow
classification in problems with millions of data points, as we demonstrate in
experiments.
Azhary: An Arabic Lexical Ontology
Authors: Hossam Ishkewy, Hany Harb, Hassan Farahat
Date: 2014-11-07 00:00:00

Arabic language is the most spoken languages in the Semitic languages group,
and one of the most common languages in the world spoken by more than 422
million. It is also of paramount importance to Muslims, it is a sacred language
of the Islamic Holly Book (Quran) and prayer (and other acts of worship) in
Islam is performed only by mastering some of Arabic words. Arabic is also a
major ritual language of a number of Christian churches in the Arab world and
it is also used in writing several intellectual and religious Jewish books in
the Middle Ages. Despite this, there is no semantic Arabic lexicon which
researchers can depend on. In this paper we introduce Azhary as a lexical
ontology for the Arabic language. It groups Arabic words into sets of synonyms
called synsets, and records a number of relationships between words such as
synonym, antonym, hypernym, hyponym, meronym, holonym and association
relations. The ontology contains 26,195 words organized in 13,328 synsets. It
has been developed and contrasted against AWN which is the most common
available Arabic lexical ontology.
Differential gene co-expression networks via Bayesian biclustering models
Authors: Chuan Gao, Shiwen Zhao, Ian C. McDowell, Christopher D. Brown, Barbara E. Engelhardt
Date: 2014-11-07 00:00:00

Identifying latent structure in large data matrices is essential for
exploring biological processes. Here, we consider recovering gene co-expression
networks from gene expression data, where each network encodes relationships
between genes that are locally co-regulated by shared biological mechanisms. To
do this, we develop a Bayesian statistical model for biclustering to infer
subsets of co-regulated genes whose covariation may be observed in only a
subset of the samples. Our biclustering method, BicMix, has desirable
properties, including allowing overcomplete representations of the data,
computational tractability, and jointly modeling unknown confounders and
biological signals. Compared with related biclustering methods, BicMix recovers
latent structure with higher precision across diverse simulation scenarios.
Further, we develop a method to recover gene co-expression networks from the
estimated sparse biclustering matrices. We apply BicMix to breast cancer gene
expression data and recover a gene co-expression network that is differential
across ER+ and ER- samples.
Hardware and Software manual for Evolution of Oil Droplets in a Chemo-Robotic Platform
Authors: Juan Manuel Parrilla Gutierrez, Trevor Hinkley, James Taylor, Kliment Yanev, Leroy Cronin
Date: 2014-11-07 00:00:00

This manual outlines a fully automated liquid handling robot to enable
physically-embodied evolution within a chemical oil-droplet system. The robot
is based upon the REPRAP3D printer system and makes the droplets by mixing
chemicals and then placing them in a petri dish after which they are recorded
using a camera and the behaviour of the droplets analysed using image
recognition software. This manual accompanies the open access publication
published in Nature Communications DOI: 10.1038/ncomms6571.
Data-driven HRF estimation for encoding and decoding models
Authors: Fabian Pedregosa, Michael Eickenberg, Philippe Ciuciu, Bertrand Thirion, Alexandre Gramfort
Date: 2014-02-27 00:00:00
Tasks: Computational Efficiency

Despite the common usage of a canonical, data-independent, hemodynamic
response function (HRF), it is known that the shape of the HRF varies across
brain regions and subjects. This suggests that a data-driven estimation of this
function could lead to more statistical power when modeling BOLD fMRI data.
However, unconstrained estimation of the HRF can yield highly unstable results
when the number of free parameters is large. We develop a method for the joint
estimation of activation and HRF using a rank constraint causing the estimated
HRF to be equal across events/conditions, yet permitting it to be different
across voxels. Model estimation leads to an optimization problem that we
propose to solve with an efficient quasi-Newton method exploiting fast gradient
computations. This model, called GLM with Rank-1 constraint (R1-GLM), can be
extended to the setting of GLM with separate designs which has been shown to
improve decoding accuracy in brain activity decoding experiments. We compare 10
different HRF modeling methods in terms of encoding and decoding score in two
different datasets. Our results show that the R1-GLM model significantly
outperforms competing methods in both encoding and decoding settings,
positioning it as an attractive method both from the points of view of accuracy
and computational efficiency.
Marginal AMP Chain Graphs
Authors: Jose M. Peña
Date: 2013-05-03 00:00:00
Tasks: Selection bias

We present a new family of models that is based on graphs that may have
undirected, directed and bidirected edges. We name these new models marginal
AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP
chain graph under marginalization of some of its nodes. However, MAMP chain
graphs do not only subsume AMP chain graphs but also multivariate regression
chain graphs. We describe global and pairwise Markov properties for MAMP chain
graphs and prove their equivalence for compositional graphoids. We also
characterize when two MAMP chain graphs are Markov equivalent.
  For Gaussian probability distributions, we also show that every MAMP chain
graph is Markov equivalent to some directed and acyclic graph with
deterministic nodes under marginalization and conditioning on some of its
nodes. This is important because it implies that the independence model
represented by a MAMP chain graph can be accounted for by some data generating
process that is partially observed and has selection bias. Finally, we modify
MAMP chain graphs so that they are closed under marginalization for Gaussian
probability distributions. This is a desirable feature because it guarantees
parsimonious models under marginalization.
Large-Margin Determinantal Point Processes
Authors: Boqing Gong, Wei-Lun Chao, Kristen Grauman, Fei Sha
Date: 2014-11-06 00:00:00
Tasks: Diversity, parameter estimation, Point Processes, Video Summarization

Determinantal point processes (DPPs) offer a powerful approach to modeling
diversity in many applications where the goal is to select a diverse subset. We
study the problem of learning the parameters (the kernel matrix) of a DPP from
labeled training data. We make two contributions. First, we show how to
reparameterize a DPP's kernel matrix with multiple kernel functions, thus
enhancing modeling flexibility. Second, we propose a novel parameter estimation
technique based on the principle of large margin separation. In contrast to the
state-of-the-art method of maximum likelihood estimation, our large-margin loss
function explicitly models errors in selecting the target subsets, and it can
be customized to trade off different types of errors (precision vs. recall).
Extensive empirical studies validate our contributions, including applications
on challenging document and video summarization, where flexibility in modeling
the kernel matrix and balancing different errors is indispensable.
Sparse Polynomial Learning and Graph Sketching
Authors: Murat Kocaoglu, Karthikeyan Shanmugam, Alexandros G. Dimakis, Adam Klivans
Date: 2014-02-17 00:00:00
Proceeding: NeurIPS 2014 12

Let $f:\{-1,1\}^n$ be a polynomial with at most $s$ non-zero real
coefficients. We give an algorithm for exactly reconstructing f given random
examples from the uniform distribution on $\{-1,1\}^n$ that runs in time
polynomial in $n$ and $2s$ and succeeds if the function satisfies the unique
sign property: there is one output value which corresponds to a unique set of
values of the participating parities. This sufficient condition is satisfied
when every coefficient of f is perturbed by a small random noise, or satisfied
with high probability when s parity functions are chosen randomly or when all
the coefficients are positive. Learning sparse polynomials over the Boolean
domain in time polynomial in $n$ and $2s$ is considered notoriously hard in the
worst-case. Our result shows that the problem is tractable for almost all
sparse polynomials. Then, we show an application of this result to hypergraph
sketching which is the problem of learning a sparse (both in the number of
hyperedges and the size of the hyperedges) hypergraph from uniformly drawn
random cuts. We also provide experimental results on a real world dataset.
How transferable are features in deep neural networks?
Authors: Jason Yosinski, Jeff Clune, Yoshua Bengio, Hod Lipson
Date: 2014-11-06 00:00:00
Proceeding: NeurIPS 2014 12
Tasks: Specificity

Many deep neural networks trained on natural images exhibit a curious
phenomenon in common: on the first layer they learn features similar to Gabor
filters and color blobs. Such first-layer features appear not to be specific to
a particular dataset or task, but general in that they are applicable to many
datasets and tasks. Features must eventually transition from general to
specific by the last layer of the network, but this transition has not been
studied extensively. In this paper we experimentally quantify the generality
versus specificity of neurons in each layer of a deep convolutional neural
network and report a few surprising results. Transferability is negatively
affected by two distinct issues: (1) the specialization of higher layer neurons
to their original task at the expense of performance on the target task, which
was expected, and (2) optimization difficulties related to splitting networks
between co-adapted neurons, which was not expected. In an example network
trained on ImageNet, we demonstrate that either of these two issues may
dominate, depending on whether features are transferred from the bottom,
middle, or top of the network. We also document that the transferability of
features decreases as the distance between the base task and target task
increases, but that transferring features even from distant tasks can be better
than using random features. A final surprising result is that initializing a
network with transferred features from almost any number of layers can produce
a boost to generalization that lingers even after fine-tuning to the target
dataset.
Computer vision-based recognition of liquid surfaces and phase boundaries in transparent vessels, with emphasis on chemistry applications
Authors: Sagi Eppel, Tal Kachman
Date: 2014-04-28 00:00:00

The ability to recognize the liquid surface and the liquid level in
transparent containers is perhaps the most commonly used evaluation method when
dealing with fluids. Such recognition is essential in determining the liquid
volume, fill level, phase boundaries and phase separation in various fluid
systems. The recognition of liquid surfaces is particularly important in
solution chemistry, where it is essential to many laboratory techniques (e.g.,
extraction, distillation, titration). A general method for the recognition of
interfaces between liquid and air or between phase-separating liquids could
have a wide range of applications and contribute to the understanding of the
visual properties of such interfaces. This work examines a computer vision
method for the recognition of liquid surfaces and liquid levels in various
transparent containers. The method can be applied to recognition of both
liquid-air and liquid-liquid surfaces. No prior knowledge of the number of
phases is required. The method receives the image of the liquid container and
the boundaries of the container in the image and scans all possible curves that
could correspond to the outlines of liquid surfaces in the image. The method
then compares each curve to the image to rate its correspondence with the
outline of the real liquid surface by examining various image properties in the
area surrounding each point of the curve. The image properties that were found
to give the best indication of the liquid surface are the relative intensity
change, the edge density change and the gradient direction relative to the
curve normal.
Conditional Generative Adversarial Nets
Authors: Mehdi Mirza, Simon Osindero
Date: 2014-11-06 00:00:00
Tasks: Descriptive, Human action generation

Generative Adversarial Nets [8] were recently introduced as a novel way to train generative models. In this work we introduce the conditional version of generative adversarial nets, which can be constructed by simply feeding the data, y, we wish to condition on to both the generator and discriminator. We show that this model can generate MNIST digits conditioned on class labels. We also illustrate how this model could be used to learn a multi-modal model, and provide preliminary examples of an application to image tagging in which we demonstrate how this approach can generate descriptive tags which are not part of training labels.