pwc-archive/papers-with-abstracts huggingface dataset:
A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
Authors: Ohad Shamir
Date: 2014-09-09 00:00:00

We describe and analyze a simple algorithm for principal component analysis
and singular value decomposition, VR-PCA, which uses computationally cheap
stochastic iterations, yet converges exponentially fast to the optimal
solution. In contrast, existing algorithms suffer either from slow convergence,
or computationally intensive iterations whose runtime scales with the data
size. The algorithm builds on a recent variance-reduced stochastic gradient
technique, which was previously analyzed for strongly convex optimization,
whereas here we apply it to an inherently non-convex problem, using a very
different analysis.
A Sinc Wavelet Describes the Receptive Fields of Neurons in the Motion Cortex
Authors: Stephen G. Odaibo
Date: 2015-07-31 00:00:00

Visual perception results from a systematic transformation of the information
flowing through the visual system. In the neuronal hierarchy, the response
properties of single neurons are determined by neurons located one level below,
and in turn, determine the responses of neurons located one level above.
Therefore in modeling receptive fields, it is essential to ensure that the
response properties of neurons in a given level can be generated by combining
the response models of neurons in its input levels. However, existing response
models of neurons in the motion cortex do not inherently yield the temporal
frequency filtering gradient (TFFG) property that is known to emerge along the
primary visual cortex (V1) to middle temporal (MT) motion processing stream.
TFFG is the change from predominantly lowpass to predominantly bandpass
temporal frequency filtering character along the V1 to MT pathway (Foster et al
1985; DeAngelis et al 1993; Hawken et al 1996). We devised a new model, the
sinc wavelet model (Odaibo, 2014), which logically and efficiently generates
the TFFG. The model replaces the Gabor function's sine wave carrier with a sinc
(sin(x)/x) function, and has the same or fewer number of parameters as existing
models. Because of its logical consistency with the emergent network property
of TFFG, we conclude that the sinc wavelet is a better model for the receptive
fields of motion cortex neurons. This model will provide new physiological
insights into how the brain represents visual information.
Systematic Verification of the Modal Logic Cube in Isabelle/HOL
Authors: Christoph Benzmüller, Maximilian Claus, Nik Sultana
Date: 2015-07-31 00:00:00

We present an automated verification of the well-known modal logic cube in
Isabelle/HOL, in which we prove the inclusion relations between the cube's
logics using automated reasoning tools. Prior work addresses this problem but
without restriction to the modal logic cube, and using encodings in first-order
logic in combination with first-order automated theorem provers. In contrast,
our solution is more elegant, transparent and effective. It employs an
embedding of quantified modal logic in classical higher-order logic. Automated
reasoning tools, such as Sledgehammer with LEO-II, Satallax and CVC4, Metis and
Nitpick, are employed to achieve full automation. Though successful, the
experiments also motivate some technical improvements in the Isabelle/HOL tool.
Beyond Gauss: Image-Set Matching on the Riemannian Manifold of PDFs
Authors: Mehrtash Harandi, Mathieu Salzmann, Mahsa Baktashmotlagh
Date: 2015-07-31 00:00:00
Proceeding: ICCV 2015 12
Tasks: Dimensionality Reduction, Face Recognition, General Classification, set matching, Supervised dimensionality reduction, Texture Classification, valid

State-of-the-art image-set matching techniques typically implicitly model
each image-set with a Gaussian distribution. Here, we propose to go beyond
these representations and model image-sets as probability distribution
functions (PDFs) using kernel density estimators. To compare and match
image-sets, we exploit Csiszar f-divergences, which bear strong connections to
the geodesic distance defined on the space of PDFs, i.e., the statistical
manifold. Furthermore, we introduce valid positive definite kernels on the
statistical manifolds, which let us make use of more powerful classification
schemes to match image-sets. Finally, we introduce a supervised dimensionality
reduction technique that learns a latent space where f-divergences reflect the
class labels of the data. Our experiments on diverse problems, such as
video-based face recognition and dynamic texture classification, evidence the
benefits of our approach over the state-of-the-art image-set matching methods.
Finding One Community in a Sparse Graph
Authors: Andrea Montanari
Date: 2015-02-19 00:00:00

We consider a random sparse graph with bounded average degree, in which a
subset of vertices has higher connectivity than the background. In particular,
the average degree inside this subset of vertices is larger than outside (but
still bounded). Given a realization of such graph, we aim at identifying the
hidden subset of vertices. This can be regarded as a model for the problem of
finding a tightly knitted community in a social network, or a cluster in a
relational dataset.
  In this paper we present two sets of contributions: $(i)$ We use the cavity
method from spin glass theory to derive an exact phase diagram for the
reconstruction problem. In particular, as the difference in edge probability
increases, the problem undergoes two phase transitions, a static phase
transition and a dynamic one. $(ii)$ We establish rigorous bounds on the
dynamic phase transition and prove that, above a certain threshold, a local
algorithm (belief propagation) correctly identify most of the hidden set. Below
the same threshold \emph{no local algorithm} can achieve this goal. However, in
this regime the subset can be identified by exhaustive search.
  For small hidden sets and large average degree, the phase transition for
local algorithms takes an intriguingly simple form. Local algorithms succeed
with high probability for ${\rm deg}_{\rm in} - {\rm deg}_{\rm out} >
\sqrt{{\rm deg}_{\rm out}/e}$ and fail for ${\rm deg}_{\rm in} - {\rm deg}_{\rm
out} < \sqrt{{\rm deg}_{\rm out}/e}$ (with ${\rm deg}_{\rm in}$, ${\rm
deg}_{\rm out}$ the average degrees inside and outside the community). We argue
that spectral algorithms are also ineffective in the latter regime.
  It is an open problem whether any polynomial time algorithms might succeed
for ${\rm deg}_{\rm in} - {\rm deg}_{\rm out} < \sqrt{{\rm deg}_{\rm out}/e}$.
Computational Implications of Reducing Data to Sufficient Statistics
Authors: Andrea Montanari
Date: 2014-09-12 00:00:00

Given a large dataset and an estimation task, it is common to pre-process the
data by reducing them to a set of sufficient statistics. This step is often
regarded as straightforward and advantageous (in that it simplifies statistical
analysis). I show that -on the contrary- reducing data to sufficient statistics
can change a computationally tractable estimation problem into an intractable
one. I discuss connections with recent work in theoretical computer science,
and implications for some techniques to estimate graphical models.
CRISNER: A Practically Efficient Reasoner for Qualitative Preferences
Authors: Ganesh Ram Santhanam, Samik Basu, Vasant Honavar
Date: 2015-07-30 00:00:00

We present CRISNER (Conditional & Relative Importance Statement Network
PrEference Reasoner), a tool that provides practically efficient as well as
exact reasoning about qualitative preferences in popular ceteris paribus
preference languages such as CP-nets, TCP-nets, CP-theories, etc. The tool uses
a model checking engine to translate preference specifications and queries into
appropriate Kripke models and verifiable properties over them respectively. The
distinguishing features of the tool are: (1) exact and provably correct query
answering for testing dominance, consistency with respect to a preference
specification, and testing equivalence and subsumption of two sets of
preferences; (2) automatic generation of proofs evidencing the correctness of
answer produced by CRISNER to any of the above queries; (3) XML inputs and
outputs that make it portable and pluggable into other applications. We also
describe the extensible architecture of CRISNER, which can be extended to new
reference formalisms based on ceteris paribus semantics that may be developed
in the future.
Multilayer Network of Language: a Unified Framework for Structural Analysis of Linguistic Subsystems
Authors: Domagoj Margan, Ana Meštrović, Sanda Martinčić-Ipšić
Date: 2015-07-30 00:00:00

Recently, the focus of complex networks research has shifted from the
analysis of isolated properties of a system toward a more realistic modeling of
multiple phenomena - multilayer networks. Motivated by the prosperity of
multilayer approach in social, transport or trade systems, we propose the
introduction of multilayer networks for language. The multilayer network of
language is a unified framework for modeling linguistic subsystems and their
structural properties enabling the exploration of their mutual interactions.
Various aspects of natural language systems can be represented as complex
networks, whose vertices depict linguistic units, while links model their
relations. The multilayer network of language is defined by three aspects: the
network construction principle, the linguistic subsystem and the language of
interest. More precisely, we construct a word-level (syntax, co-occurrence and
its shuffled counterpart) and a subword level (syllables and graphemes) network
layers, from five variations of original text (in the modeled language). The
obtained results suggest that there are substantial differences between the
networks structures of different language subsystems, which are hidden during
the exploration of an isolated layer. The word-level layers share structural
properties regardless of the language (e.g. Croatian or English), while the
syllabic subword level expresses more language dependent structural properties.
The preserved weighted overlap quantifies the similarity of word-level layers
in weighted and directed networks. Moreover, the analysis of motifs reveals a
close topological structure of the syntactic and syllabic layers for both
languages. The findings corroborate that the multilayer network framework is a
powerful, consistent and systematic approach to model several linguistic
subsystems simultaneously and hence to provide a more unified view on language.
Framework for learning agents in quantum environments
Authors: Vedran Dunjko, Jacob M. Taylor, Hans J. Briegel
Date: 2015-07-30 00:00:00

In this paper we provide a broad framework for describing learning agents in
general quantum environments. We analyze the types of classically specified
environments which allow for quantum enhancements in learning, by contrasting
environments to quantum oracles. We show that whether or not quantum
improvements are at all possible depends on the internal structure of the
quantum environment. If the environments are constructed and the internal
structure is appropriately chosen, or if the agent has limited capacities to
influence the internal states of the environment, we show that improvements in
learning times are possible in a broad range of scenarios. Such scenarios we
call luck-favoring settings. The case of constructed environments is
particularly relevant for the class of model-based learning agents, where our
results imply a near-generic improvement.
People Counting in High Density Crowds from Still Images
Authors: Ankan Bansal, K. S. Venkatesh
Date: 2015-07-30 00:00:00
Tasks: Crowd Counting, Vocal Bursts Intensity Prediction

We present a method of estimating the number of people in high density crowds
from still images. The method estimates counts by fusing information from
multiple sources. Most of the existing work on crowd counting deals with very
small crowds (tens of individuals) and use temporal information from videos.
Our method uses only still images to estimate the counts in high density images
(hundreds to thousands of individuals). At this scale, we cannot rely on only
one set of features for count estimation. We, therefore, use multiple sources,
viz. interest points (SIFT), Fourier analysis, wavelet decomposition, GLCM
features and low confidence head detections, to estimate the counts. Each of
these sources gives a separate estimate of the count along with confidences and
other statistical measures which are then combined to obtain the final
estimate. We test our method on an existing dataset of fifty images containing
over 64000 individuals. Further, we added another fifty annotated images of
crowds and tested on the complete dataset of hundred images containing over
87000 individuals. The counts per image range from 81 to 4633. We report the
performance in terms of mean absolute error, which is a measure of accuracy of
the method, and mean normalised absolute error, which is a measure of the
robustness.
Multilinear Map Layer: Prediction Regularization by Structural Constraint
Authors: Shuchang Zhou, Yuxin Wu
Date: 2015-07-30 00:00:00
Tasks: Prediction

In this paper we propose and study a technique to impose structural
constraints on the output of a neural network, which can reduce amount of
computation and number of parameters besides improving prediction accuracy when
the output is known to approximately conform to the low-rankness prior. The
technique proceeds by replacing the output layer of neural network with the
so-called MLM layers, which forces the output to be the result of some
Multilinear Map, like a hybrid-Kronecker-dot product or Kronecker Tensor
Product. In particular, given an "autoencoder" model trained on SVHN dataset,
we can construct a new model with MLM layer achieving 62\% reduction in total
number of parameters and reduction of $\ell_2$ reconstruction error from 0.088
to 0.004. Further experiments on other autoencoder model variants trained on
SVHN datasets also demonstrate the efficacy of MLM layers.
The RatioLog Project: Rational Extensions of Logical Reasoning
Authors: Ulrich Furbach, Claudia Schon, Frieder Stolzenburg, Karl-Heinz Weis, Claus-Peter Wirth
Date: 2015-03-20 00:00:00
Tasks: BIG-bench Machine Learning, Common Sense Reasoning, Information Retrieval, Logical Reasoning, Question Answering, Retrieval, Specificity

Higher-level cognition includes logical reasoning and the ability of question
answering with common sense. The RatioLog project addresses the problem of
rational reasoning in deep question answering by methods from automated
deduction and cognitive computing. In a first phase, we combine techniques from
information retrieval and machine learning to find appropriate answer
candidates from the huge amount of text in the German version of the free
encyclopedia "Wikipedia". In a second phase, an automated theorem prover tries
to verify the answer candidates on the basis of their logical representations.
In a third phase - because the knowledge may be incomplete and inconsistent -,
we consider extensions of logical reasoning to improve the results. In this
context, we work toward the application of techniques from human reasoning: We
employ defeasible reasoning to compare the answers w.r.t. specificity, deontic
logic, normative reasoning, and model construction. Moreover, we use integrated
case-based reasoning and machine learning techniques on the basis of the
semantic structure of the questions and answer candidates to learn giving the
right answers.
Tag-Weighted Topic Model For Large-scale Semi-Structured Documents
Authors: Shuangyin Li, Jiefei Li, Guan Huang, Ruiyang Tan, Rong Pan
Date: 2015-07-30 00:00:00
Tasks: Distributed Computing, TAG, text-classification, Text Classification, Variational Inference

To date, there have been massive Semi-Structured Documents (SSDs) during the
evolution of the Internet. These SSDs contain both unstructured features (e.g.,
plain text) and metadata (e.g., tags). Most previous works focused on modeling
the unstructured text, and recently, some other methods have been proposed to
model the unstructured text with specific tags. To build a general model for
SSDs remains an important problem in terms of both model fitness and
efficiency. We propose a novel method to model the SSDs by a so-called
Tag-Weighted Topic Model (TWTM). TWTM is a framework that leverages both the
tags and words information, not only to learn the document-topic and topic-word
distributions, but also to infer the tag-topic distributions for text mining
tasks. We present an efficient variational inference method with an EM
algorithm for estimating the model parameters. Meanwhile, we propose three
large-scale solutions for our model under the MapReduce distributed computing
platform for modeling large-scale SSDs. The experimental results show the
effectiveness, efficiency and the robustness by comparing our model with the
state-of-the-art methods in document modeling, tags prediction and text
classification. We also show the performance of the three distributed solutions
in terms of time and accuracy on document modeling.
Multiple-Path Selection for new Highway Alignments using Discrete Algorithms
Authors: Yasha Pushak, Warren Hare, Yves Lucet
Date: 2015-07-30 00:00:00
Tasks: Decision Making

This paper addresses the problem of finding multiple near-optimal,
spatially-dissimilar paths that can be considered as alternatives in the
decision making process, for finding optimal corridors in which to construct a
new road. We further consider combinations of techniques for reducing the costs
associated with the computation and increasing the accuracy of the cost
formulation. Numerical results for five algorithms to solve the dissimilar
multipath problem show that a "bidirectional approach" yields the fastest
running times and the most robust algorithm. Further modifications of the
algorithms to reduce the running time were tested and it is shown that running
time can be reduced by an average of 56 percent without compromising the
quality of the results.
VMF-SNE: Embedding for Spherical Data
Authors: Mian Wang, Dong Wang
Date: 2015-07-30 00:00:00
Tasks: Data Visualization

T-SNE is a well-known approach to embedding high-dimensional data and has
been widely used in data visualization. The basic assumption of t-SNE is that
the data are non-constrained in the Euclidean space and the local proximity can
be modelled by Gaussian distributions. This assumption does not hold for a wide
range of data types in practical applications, for instance spherical data for
which the local proximity is better modelled by the von Mises-Fisher (vMF)
distribution instead of the Gaussian. This paper presents a vMF-SNE embedding
algorithm to embed spherical data. An iterative process is derived to produce
an efficient embedding. The results on a simulation data set demonstrated that
vMF-SNE produces better embeddings than t-SNE for spherical data.
When VLAD met Hilbert
Authors: Mehrtash Harandi, Mathieu Salzmann, Fatih Porikli
Date: 2015-07-30 00:00:00
Proceeding: CVPR 2016 6
Tasks: General Classification

Vectors of Locally Aggregated Descriptors (VLAD) have emerged as powerful
image/video representations that compete with or even outperform
state-of-the-art approaches on many challenging visual recognition tasks. In
this paper, we address two fundamental limitations of VLAD: its requirement for
the local descriptors to have vector form and its restriction to linear
classifiers due to its high-dimensionality. To this end, we introduce a
kernelized version of VLAD. This not only lets us inherently exploit more
sophisticated classification schemes, but also enables us to efficiently
aggregate non-vector descriptors (e.g., tensors) in the VLAD framework.
Furthermore, we propose three approximate formulations that allow us to
accelerate the coding process while still benefiting from the properties of
kernel VLAD. Our experiments demonstrate the effectiveness of our approach at
handling manifold-valued data, such as covariance descriptors, on several
classification tasks. Our results also evidence the benefits of our nonlinear
VLAD descriptors against the linear ones in Euclidean space using several
standard benchmark datasets.
Information-theoretical analysis of the statistical dependencies among three variables: Applications to written language
Authors: Damián G. Hernández, Damián H. Zanette, Inés Samengo
Date: 2015-07-30 00:00:00

We develop the information-theoretical concepts required to study the
statistical dependencies among three variables. Some of such dependencies are
pure triple interactions, in the sense that they cannot be explained in terms
of a combination of pairwise correlations. We derive bounds for triple
dependencies, and characterize the shape of the joint probability distribution
of three binary variables with high triple interaction. The analysis also
allows us to quantify the amount of redundancy in the mutual information
between pairs of variables, and to assess whether the information between two
variables is or is not mediated by a third variable. These concepts are applied
to the analysis of written texts. We find that the probability that a given
word is found in a particular location within the text is not only modulated by
the presence or absence of other nearby words, but also, on the presence or
absence of nearby pairs of words. We identify the words enclosing the key
semantic concepts of the text, the triplets of words with high pairwise and
triple interactions, and the words that mediate the pairwise interactions
between other words.
Action recognition in still images by latent superpixel classification
Authors: Shaukat Abidi, Massimo Piccardi, Mary-Anne Williams
Date: 2015-07-30 00:00:00
Tasks: Action Recognition, Action Recognition In Still Images, Classification, General Classification, Superpixels, Temporal Action Localization

Action recognition from still images is an important task of computer vision
applications such as image annotation, robotic navigation, video surveillance
and several others. Existing approaches mainly rely on either bag-of-feature
representations or articulated body-part models. However, the relationship
between the action and the image segments is still substantially unexplored.
For this reason, in this paper we propose to approach action recognition by
leveraging an intermediate layer of "superpixels" whose latent classes can act
as attributes of the action. In the proposed approach, the action class is
predicted by a structural model(learnt by Latent Structural SVM) based on
measurements from the image superpixels and their latent classes. Experimental
results over the challenging Stanford 40 Actions dataset report a significant
average accuracy of 74.06% for the positive class and 88.50% for the negative
class, giving evidence to the performance of the proposed approach.
Distributed Mini-Batch SDCA
Authors: Martin Takáč, Peter Richtárik, Nathan Srebro
Date: 2015-07-29 00:00:00

We present an improved analysis of mini-batched stochastic dual coordinate
ascent for regularized empirical loss minimization (i.e. SVM and SVM-type
objectives). Our analysis allows for flexible sampling schemes, including where
data is distribute across machines, and combines a dependence on the smoothness
of the loss and/or the data spread (measured through the spectral norm).