pwc-archive/papers-with-abstracts huggingface dataset:
Fractal structures in Adversarial Prediction
Authors: Rina Panigrahy, Preyas Popat
Date: 2013-04-29 00:00:00
Tasks: Prediction, Time Series, Time Series Analysis

Fractals are self-similar recursive structures that have been used in
modeling several real world processes. In this work we study how "fractal-like"
processes arise in a prediction game where an adversary is generating a
sequence of bits and an algorithm is trying to predict them. We will see that
under a certain formalization of the predictive payoff for the algorithm it is
most optimal for the adversary to produce a fractal-like sequence to minimize
the algorithm's ability to predict. Indeed it has been suggested before that
financial markets exhibit a fractal-like behavior. We prove that a fractal-like
distribution arises naturally out of an optimization from the adversary's
perspective.
  In addition, we give optimal trade-offs between predictability and expected
deviation (i.e. sum of bits) for our formalization of predictive payoff. This
result is motivated by the observation that several time series data exhibit
higher deviations than expected for a completely random walk.
Modeling in OWL 2 without Restrictions
Authors: Michael Schneider, Sebastian Rudolph, Geoff Sutcliffe
Date: 2012-12-12 00:00:00
Tasks: Automated Theorem Proving

The Semantic Web ontology language OWL 2 DL comes with a variety of language
features that enable sophisticated and practically useful modeling. However,
the use of these features has been severely restricted in order to retain
decidability of the language. For example, OWL 2 DL does not allow a property
to be both transitive and asymmetric, which would be desirable, e.g., for
representing an ancestor relation. In this paper, we argue that the so-called
global restrictions of OWL 2 DL preclude many useful forms of modeling, by
providing a catalog of basic modeling patterns that would be available in OWL 2
DL if the global restrictions were discarded. We then report on the results of
evaluating several state-of-the-art OWL 2 DL reasoners on problems that use
combinations of features in a way that the global restrictions are violated.
The systems turn out to rely heavily on the global restrictions and are thus
largely incapable of coping with the modeling patterns. Next we show how
off-the-shelf first-order logic theorem proving technology can be used to
perform reasoning in the OWL 2 direct semantics, the semantics that underlies
OWL 2 DL, but without requiring the global restrictions. Applying a naive
proof-of-concept implementation of this approach to the test problems was
successful in all cases. Based on our observations, we make suggestions for
future lines of research on expressive description logic-style OWL reasoning.
Semi-supervised Eigenvectors for Large-scale Locally-biased Learning
Authors: Toke J. Hansen, Michael W. Mahoney
Date: 2013-04-28 00:00:00
Tasks: BIG-bench Machine Learning, Clustering

In many applications, one has side information, e.g., labels that are
provided in a semi-supervised manner, about a specific target region of a large
data set, and one wants to perform machine learning and data analysis tasks
"nearby" that prespecified target region. For example, one might be interested
in the clustering structure of a data graph near a prespecified "seed set" of
nodes, or one might be interested in finding partitions in an image that are
near a prespecified "ground truth" set of pixels. Locally-biased problems of
this sort are particularly challenging for popular eigenvector-based machine
learning and data analysis tools. At root, the reason is that eigenvectors are
inherently global quantities, thus limiting the applicability of
eigenvector-based methods in situations where one is interested in very local
properties of the data.
  In this paper, we address this issue by providing a methodology to construct
semi-supervised eigenvectors of a graph Laplacian, and we illustrate how these
locally-biased eigenvectors can be used to perform locally-biased machine
learning. These semi-supervised eigenvectors capture
successively-orthogonalized directions of maximum variance, conditioned on
being well-correlated with an input seed set of nodes that is assumed to be
provided in a semi-supervised manner. We show that these semi-supervised
eigenvectors can be computed quickly as the solution to a system of linear
equations; and we also describe several variants of our basic method that have
improved scaling properties. We provide several empirical examples
demonstrating how these semi-supervised eigenvectors can be used to perform
locally-biased learning; and we discuss the relationship between our results
and recent machine learning algorithms that use global eigenvectors of the
graph Laplacian.
Towards a Formal Distributional Semantics: Simulating Logical Calculi with Tensors
Authors: Edward Grefenstette
Date: 2013-04-22 00:00:00
Proceeding: SEMEVAL 2013 6
Tasks: Relation

The development of compositional distributional models of semantics
reconciling the empirical aspects of distributional semantics with the
compositional aspects of formal semantics is a popular topic in the
contemporary literature. This paper seeks to bring this reconciliation one step
further by showing how the mathematical constructs commonly used in
compositional distributional models, such as tensors and matrices, can be used
to simulate different aspects of predicate logic.
  This paper discusses how the canonical isomorphism between tensors and
multilinear maps can be exploited to simulate a full-blown quantifier-free
predicate calculus using tensors. It provides tensor interpretations of the set
of logical connectives required to model propositional calculi. It suggests a
variant of these tensor calculi capable of modelling quantifiers, using few
non-linear operations. It finally discusses the relation between these
variants, and how this relation should constitute the subject of future work.
Measuring Cultural Relativity of Emotional Valence and Arousal using Semantic Clustering and Twitter
Authors: Eugene Yuta Bann, Joanna J. Bryson
Date: 2013-04-28 00:00:00
Tasks: Clustering, Cultural Vocal Bursts Intensity Prediction

Researchers since at least Darwin have debated whether and to what extent
emotions are universal or culture-dependent. However, previous studies have
primarily focused on facial expressions and on a limited set of emotions. Given
that emotions have a substantial impact on human lives, evidence for cultural
emotional relativity might be derived by applying distributional semantics
techniques to a text corpus of self-reported behaviour. Here, we explore this
idea by measuring the valence and arousal of the twelve most popular emotion
keywords expressed on the micro-blogging site Twitter. We do this in three
geographical regions: Europe, Asia and North America. We demonstrate that in
our sample, the valence and arousal levels of the same emotion keywords differ
significantly with respect to these geographical regions --- Europeans are, or
at least present themselves as more positive and aroused, North Americans are
more negative and Asians appear to be more positive but less aroused when
compared to global valence and arousal levels of the same emotion keywords. Our
work is the first in kind to programatically map large text corpora to a
dimensional model of affect.
Deterministic Initialization of the K-Means Algorithm Using Hierarchical Clustering
Authors: M. Emre Celebi, Hassan A. Kingravi
Date: 2013-04-28 00:00:00
Tasks: Clustering

K-means is undoubtedly the most widely used partitional clustering algorithm.
Unfortunately, due to its gradient descent nature, this algorithm is highly
sensitive to the initial placement of the cluster centers. Numerous
initialization methods have been proposed to address this problem. Many of
these methods, however, have superlinear complexity in the number of data
points, making them impractical for large data sets. On the other hand, linear
methods are often random and/or order-sensitive, which renders their results
unrepeatable. Recently, Su and Dy proposed two highly successful hierarchical
initialization methods named Var-Part and PCA-Part that are not only linear,
but also deterministic (non-random) and order-invariant. In this paper, we
propose a discriminant analysis based approach that addresses a common
deficiency of these two methods. Experiments on a large and diverse collection
of data sets from the UCI Machine Learning Repository demonstrate that Var-Part
and PCA-Part are highly competitive with one of the best random initialization
methods to date, i.e., k-means++, and that the proposed approach significantly
improves the performance of both hierarchical methods.
Storing cycles in Hopfield-type networks with pseudoinverse learning rule: admissibility and network topology
Authors: Chuan Zhang, Gerhard Dangelmayr, Iuliana Oprea
Date: 2012-11-19 00:00:00

Cyclic patterns of neuronal activity are ubiquitous in animal nervous
systems, and partially responsible for generating and controlling rhythmic
movements such as locomotion, respiration, swallowing and so on. Clarifying the
role of the network connectivities for generating cyclic patterns is
fundamental for understanding the generation of rhythmic movements. In this
paper, the storage of binary cycles in neural networks is investigated. We call
a cycle $\Sigma$ admissible if a connectivity matrix satisfying the cycle's
transition conditions exists, and construct it using the pseudoinverse learning
rule. Our main focus is on the structural features of admissible cycles and
corresponding network topology. We show that $\Sigma$ is admissible if and only
if its discrete Fourier transform contains exactly $r={rank}(\Sigma)$ nonzero
columns. Based on the decomposition of the rows of $\Sigma$ into loops, where a
loop is the set of all cyclic permutations of a row, cycles are classified as
simple cycles, separable or inseparable composite cycles. Simple cycles contain
rows from one loop only, and the network topology is a feedforward chain with
feedback to one neuron if the loop-vectors in $\Sigma$ are cyclic permutations
of each other. Composite cycles contain rows from at least two disjoint loops,
and the neurons corresponding to the rows in $\Sigma$ from the same loop are
identified with a cluster. Networks constructed from separable composite cycles
decompose into completely isolated clusters. For inseparable composite cycles
at least two clusters are connected, and the cluster-connectivity is related to
the intersections of the spaces spanned by the loop-vectors of the clusters.
Simulations showing successfully retrieved cycles in continuous-time
Hopfield-type networks and in networks of spiking neurons are presented.
On Integrating Fuzzy Knowledge Using a Novel Evolutionary Algorithm
Authors: Nafisa Afrin Chowdhury, Murshida Khatun, M. M. A. Hashem
Date: 2013-04-28 00:00:00
Tasks: General Classification

Fuzzy systems may be considered as knowledge-based systems that incorporates
human knowledge into their knowledge base through fuzzy rules and fuzzy
membership functions. The intent of this study is to present a fuzzy knowledge
integration framework using a Novel Evolutionary Strategy (NES), which can
simultaneously integrate multiple fuzzy rule sets and their membership function
sets. The proposed approach consists of two phases: fuzzy knowledge encoding
and fuzzy knowledge integration. Four application domains, the hepatitis
diagnosis, the sugarcane breeding prediction, Iris plants classification, and
Tic-tac-toe endgame were used to show the performance ofthe proposed knowledge
approach. Results show that the fuzzy knowledge base derived using our approach
performs better than Genetic Algorithm based approach.
Bingham Procrustean Alignment for Object Detection in Clutter
Authors: Jared Glover, Sanja Popovic
Date: 2013-04-27 00:00:00
Tasks: Object, object-detection, Object Detection, Position

A new system for object detection in cluttered RGB-D images is presented. Our
main contribution is a new method called Bingham Procrustean Alignment (BPA) to
align models with the scene. BPA uses point correspondences between oriented
features to derive a probability distribution over possible model poses. The
orientation component of this distribution, conditioned on the position, is
shown to be a Bingham distribution. This result also applies to the classic
problem of least-squares alignment of point sets, when point features are
orientation-less, and gives a principled, probabilistic way to measure pose
uncertainty in the rigid alignment problem. Our detection system leverages BPA
to achieve more reliable object detections in clutter.
TimeML-strict: clarifying temporal annotation
Authors: Leon Derczynski, Hector Llorens, Naushad UzZaman
Date: 2013-04-26 00:00:00
Tasks: valid

TimeML is an XML-based schema for annotating temporal information over
discourse. The standard has been used to annotate a variety of resources and is
followed by a number of tools, the creation of which constitute hundreds of
thousands of man-hours of research work. However, the current state of
resources is such that many are not valid, or do not produce valid output, or
contain ambiguous or custom additions and removals. Difficulties arising from
these variances were highlighted in the TempEval-3 exercise, which included its
own extra stipulations over conventional TimeML as a response.
  To unify the state of current resources, and to make progress toward easy
adoption of its current incarnation ISO-TimeML, this paper introduces
TimeML-strict: a valid, unambiguous, and easy-to-process subset of TimeML. We
also introduce three resources -- a schema for TimeML-strict; a validator tool
for TimeML-strict, so that one may ensure documents are in the correct form;
and a repair tool that corrects common invalidating errors and adds
disambiguating markup in order to convert documents from the laxer TimeML
standard to TimeML-strict.
Active and passive learning of linear separators under log-concave distributions
Authors: Maria Florina Balcan, Philip M. Long
Date: 2012-11-06 00:00:00
Tasks: Active Learning, Open-Ended Question Answering

We provide new results concerning label efficient, polynomial time, passive
and active learning of linear separators. We prove that active learning
provides an exponential improvement over PAC (passive) learning of homogeneous
linear separators under nearly log-concave distributions. Building on this, we
provide a computationally efficient PAC algorithm with optimal (up to a
constant factor) sample complexity for such problems. This resolves an open
question concerning the sample complexity of efficient PAC algorithms under the
uniform distribution in the unit ball. Moreover, it provides the first bound
for a polynomial-time PAC algorithm that is tight for an interesting infinite
class of hypothesis functions under a general and natural class of
data-distributions, providing significant progress towards a longstanding open
question.
  We also provide new bounds for active and passive learning in the case that
the data might not be linearly separable, both in the agnostic case and and
under the Tsybakov low-noise condition. To derive our results, we provide new
structural results for (nearly) log-concave distributions, which might be of
independent interest as well.
Solution of System of Linear Equations - A Neuro-Fuzzy Approach
Authors: Arindam Chaudhuri, Kajal De, Dipak Chatterjee
Date: 2013-04-26 00:00:00
Tasks: Decision Making, Management

Neuro-Fuzzy Modeling has been applied in a wide variety of fields such as
Decision Making, Engineering and Management Sciences etc. In particular,
applications of this Modeling technique in Decision Making by involving complex
Systems of Linear Algebraic Equations have remarkable significance. In this
Paper, we present Polak-Ribiere Conjugate Gradient based Neural Network with
Fuzzy rules to solve System of Simultaneous Linear Algebraic Equations. This is
achieved using Fuzzy Backpropagation Learning Rule. The implementation results
show that the proposed Neuro-Fuzzy Network yields effective solutions for
exactly determined, underdetermined and over-determined Systems of Linear
Equations. This fact is demonstrated by the Computational Complexity analysis
of the Neuro-Fuzzy Algorithm. The proposed Algorithm is simulated effectively
using MATLAB software. To the best of our knowledge this is the first work of
the Systems of Linear Algebraic Equations using Neuro-Fuzzy Modeling.
Solution of the Decision Making Problems using Fuzzy Soft Relations
Authors: Arindam Chaudhuri, Kajal De, Dipak Chatterjee
Date: 2013-04-26 00:00:00
Tasks: Decision Making, Management, Relation

The Fuzzy Modeling has been applied in a wide variety of fields such as
Engineering and Management Sciences and Social Sciences to solve a number
Decision Making Problems which involve impreciseness, uncertainty and vagueness
in data. In particular, applications of this Modeling technique in Decision
Making Problems have remarkable significance. These problems have been tackled
using various theories such as Probability theory, Fuzzy Set Theory, Rough Set
Theory, Vague Set Theory, Approximate Reasoning Theory etc. which lack in
parameterization of the tools due to which they could not be applied
successfully to such problems. The concept of Soft Set has a promising
potential for giving an optimal solution for these problems. With the
motivation of this new concept, in this paper we define the concepts of Soft
Relation and Fuzzy Soft Relation and then apply them to solve a number of
Decision Making Problems. The advantages of Fuzzy Soft Relation compared to
other paradigms are discussed. To the best of our knowledge this is the first
work on the application of Fuzzy Soft Relation to the Decision Making Problems.
In the sight of my wearable camera: Classifying my visual experience
Authors: Alessandro Perina, Nebojsa Jojic
Date: 2013-04-26 00:00:00

We introduce and we analyze a new dataset which resembles the input to
biological vision systems much more than most previously published ones. Our
analysis leaded to several important conclusions. First, it is possible to
disambiguate over dozens of visual scenes (locations) encountered over the
course of several weeks of a human life with accuracy of over 80%, and this
opens up possibility for numerous novel vision applications, from early
detection of dementia to everyday use of wearable camera streams for automatic
reminders, and visual stream exchange. Second, our experimental results
indicate that, generative models such as Latent Dirichlet Allocation or
Counting Grids, are more suitable to such types of data, as they are more
robust to overtraining and comfortable with images at low resolution, blurred
and characterized by relatively random clutter and a mix of objects.
Runtime Optimizations for Prediction with Tree-Based Models
Authors: Nima Asadi, Jimmy Lin, Arjen P. de Vries
Date: 2012-12-11 00:00:00
Tasks: Prediction

Tree-based models have proven to be an effective solution for web ranking as
well as other problems in diverse domains. This paper focuses on optimizing the
runtime performance of applying such models to make predictions, given an
already-trained model. Although exceedingly simple conceptually, most
implementations of tree-based models do not efficiently utilize modern
superscalar processor architectures. By laying out data structures in memory in
a more cache-conscious fashion, removing branches from the execution flow using
a technique called predication, and micro-batching predictions using a
technique called vectorization, we are able to better exploit modern processor
architectures and significantly improve the speed of tree-based models over
hard-coded if-else blocks. Our work contributes to the exploration of
architecture-conscious runtime implementations of machine learning algorithms.
Algorithmic Optimisations for Iterative Deconvolution Methods
Authors: Martin Welk, Martin Erler
Date: 2013-04-26 00:00:00
Tasks: Image Deconvolution

We investigate possibilities to speed up iterative algorithms for non-blind
image deconvolution. We focus on algorithms in which convolution with the
point-spread function to be deconvolved is used in each iteration, and aim at
accelerating these convolution operations as they are typically the most
expensive part of the computation. We follow two approaches: First, for some
practically important specific point-spread functions, algorithmically
efficient sliding window or list processing techniques can be used. In some
constellations this allows faster computation than via the Fourier domain.
Second, as iterations progress, computation of convolutions can be restricted
to subsets of pixels. For moderate thinning rates this can be done with almost
no impact on the reconstruction quality. Both approaches are demonstrated in
the context of Richardson-Lucy deconvolution but are not restricted to this
method.
Computational Lower Bounds for Sparse PCA
Authors: Quentin Berthet, Philippe Rigollet
Date: 2013-04-03 00:00:00
Tasks: Computational Efficiency

In the context of sparse principal component detection, we bring evidence
towards the existence of a statistical price to pay for computational
efficiency. We measure the performance of a test by the smallest signal
strength that it can detect and we propose a computationally efficient method
based on semidefinite programming. We also prove that the statistical
performance of this test cannot be strictly improved by any computationally
efficient method. Our results can be viewed as complexity theoretic lower
bounds conditionally on the assumptions that some instances of the planted
clique problem cannot be solved in randomized polynomial time.
Reading Ancient Coin Legends: Object Recognition vs. OCR
Authors: Albert Kavelar, Sebastian Zambanini, Martin Kampel
Date: 2013-04-26 00:00:00
Tasks: Object, Object Recognition, Optical Character Recognition (OCR), Scene Text Recognition

Standard OCR is a well-researched topic of computer vision and can be
considered solved for machine-printed text. However, when applied to
unconstrained images, the recognition rates drop drastically. Therefore, the
employment of object recognition-based techniques has become state of the art
in scene text recognition applications. This paper presents a scene text
recognition method tailored to ancient coin legends and compares the results
achieved in character and word recognition experiments to a standard OCR
engine. The conducted experiments show that the proposed method outperforms the
standard OCR engine on a set of 180 cropped coin legend words.
Non Deterministic Logic Programs
Authors: Emad Saad
Date: 2013-04-26 00:00:00
Tasks: Negation, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL), Stochastic Optimization

Non deterministic applications arise in many domains, including, stochastic
optimization, multi-objectives optimization, stochastic planning, contingent
stochastic planning, reinforcement learning, reinforcement learning in
partially observable Markov decision processes, and conditional planning. We
present a logic programming framework called non deterministic logic programs,
along with a declarative semantics and fixpoint semantics, to allow
representing and reasoning about inherently non deterministic real-world
applications. The language of non deterministic logic programs framework is
extended with non-monotonic negation, and two alternative semantics are
defined: the stable non deterministic model semantics and the well-founded non
deterministic model semantics as well as their relationship is studied. These
semantics subsume the deterministic stable model semantics and the
deterministic well-founded semantics of deterministic normal logic programs,
and they reduce to the semantics of deterministic definite logic programs
without negation. We show the application of the non deterministic logic
programs framework to a conditional planning problem.