pwc-archive/papers-with-abstracts huggingface dataset:
Temporal Description Logic for Ontology-Based Data Access (Extended Version)
Authors: Alessandro Artale, Roman Kontchakov, Frank Wolter, Michael Zakharyaschev
Date: 2013-04-18 00:00:00

Our aim is to investigate ontology-based data access over temporal data with
validity time and ontologies capable of temporal conceptual modelling. To this
end, we design a temporal description logic, TQL, that extends the standard
ontology language OWL 2 QL, provides basic means for temporal conceptual
modelling and ensures first-order rewritability of conjunctive queries for
suitably defined data instances with validity time.
Fractal-Based Detection of Microcalcification Clusters in Digital Mammograms
Authors: P. Shanmugavadivu, V. Sivakumar
Date: 2013-04-30 00:00:00
Tasks: Edge Detection

In this paper, a novel method for edge detection of microcalcification
clusters in mammogram images is presented using the concept of Fractal
Dimension and Hurst co-efficient that enables to locate the microcalcifications
in the mammograms. This technique detects the edges accurately than the ones
obtained by the conventional Sobel method. Generally, Sobel method detects the
edges of the regions/objects in an image using the Fudge factor that assumes
its value as 0.5, by default. In this proposed technique, the Fudge factor is
suitably replaced with Hurst Co-efficient, which is computed as the difference
of Fractal dimension and the topological dimension of a given input image.
These two dimensions are image-dependent, and hence the respective Hurst
co-efficient too varies with respect to images. Hence, the image-dependent
Hurst co-efficient based Sobel method is proved to produce better results than
the Fudge factor based Sobel method. The results of the proposed method
substantiate the merit of the proposed technique.
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability
Authors: Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
Date: 2013-04-30 00:00:00
Tasks: Topic Models

We give a robust version of the celebrated result of Kruskal on the
uniqueness of tensor decompositions: we prove that given a tensor whose
decomposition satisfies a robust form of Kruskal's rank condition, it is
possible to approximately recover the decomposition if the tensor is known up
to a sufficiently small (inverse polynomial) error.
  Kruskal's theorem has found many applications in proving the identifiability
of parameters for various latent variable models and mixture models such as
Hidden Markov models, topic models etc. Our robust version immediately implies
identifiability using only polynomially many samples in many of these settings.
This polynomial identifiability is an essential first step towards efficient
learning algorithms for these models.
  Recently, algorithms based on tensor decompositions have been used to
estimate the parameters of various hidden variable models efficiently in
special cases as long as they satisfy certain "non-degeneracy" properties. Our
methods give a way to go beyond this non-degeneracy barrier, and establish
polynomial identifiability of the parameters under much milder conditions.
Given the importance of Kruskal's theorem in the tensor literature, we expect
that this robust version will have several applications beyond the settings we
explore in this work.
Digenes: genetic algorithms to discover conjectures about directed and undirected graphs
Authors: Romain Absil, Hadrien Mélot
Date: 2013-04-30 00:00:00
Tasks: Math

We present Digenes, a new discovery system that aims to help researchers in
graph theory. While its main task is to find extremal graphs for a given
(function of) invariants, it also provides some basic support in proof
conception. This has already been proved to be very useful to find new
conjectures since the AutoGraphiX system of Caporossi and Hansen (Discrete
Math. 212-2000). However, unlike existing systems, Digenes can be used both
with directed or undirected graphs. In this paper, we present the principles
and functionality of Digenes, describe the genetic algorithms that have been
designed to achieve them, and give some computational results and open
questions. This do arise some interesting questions regarding genetic
algorithms design particular to this field, such as crossover definition.
RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational Models
Authors: Jan Noessner, Mathias Niepert, Heiner Stuckenschmidt
Date: 2013-04-16 00:00:00

RockIt is a maximum a-posteriori (MAP) query engine for statistical
relational models. MAP inference in graphical models is an optimization problem
which can be compiled to integer linear programs (ILPs). We describe several
advances in translating MAP queries to ILP instances and present the novel
meta-algorithm cutting plane aggregation (CPA). CPA exploits local
context-specific symmetries and bundles up sets of linear constraints. The
resulting counting constraints lead to more compact ILPs and make the symmetry
of the ground model more explicit to state-of-the-art ILP solvers. Moreover,
RockIt parallelizes most parts of the MAP inference pipeline taking advantage
of ubiquitous shared-memory multi-core architectures.
  We report on extensive experiments with Markov logic network (MLN) benchmarks
showing that RockIt outperforms the state-of-the-art systems Alchemy, Markov
TheBeast, and Tuffy both in terms of efficiency and quality of results.
ManTIME: Temporal expression identification and normalization in the TempEval-3 challenge
Authors: Michele Filannino, Gavin Brown, Goran Nenadic
Date: 2013-04-30 00:00:00
Proceeding: SEMEVAL 2013 6
Tasks: Attribute

This paper describes a temporal expression identification and normalization
system, ManTIME, developed for the TempEval-3 challenge. The identification
phase combines the use of conditional random fields along with a
post-processing identification pipeline, whereas the normalization phase is
carried out using NorMA, an open-source rule-based temporal normalizer. We
investigate the performance variation with respect to different feature types.
Specifically, we show that the use of WordNet-based features in the
identification task negatively affects the overall performance, and that there
is no statistically significant difference in using gazetteers, shallow parsing
and propositional noun phrases labels on top of the morphological features. On
the test data, the best run achieved 0.95 (P), 0.85 (R) and 0.90 (F1) in the
identification phase. Normalization accuracies are 0.84 (type attribute) and
0.77 (value attribute). Surprisingly, the use of the silver data (alone or in
addition to the gold annotated ones) does not improve the performance.
Clustering processes
Authors: Daniil Ryabko
Date: 2010-05-05 00:00:00
Tasks: Clustering

The problem of clustering is considered, for the case when each data point is
a sample generated by a stationary ergodic process. We propose a very natural
asymptotic notion of consistency, and show that simple consistent algorithms
exist, under most general non-parametric assumptions. The notion of consistency
is as follows: two samples should be put into the same cluster if and only if
they were generated by the same distribution. With this notion of consistency,
clustering generalizes such classical statistical problems as homogeneity
testing and process classification. We show that, for the case of a known
number of clusters, consistency can be achieved under the only assumption that
the joint distribution of the data is stationary ergodic (no parametric or
Markovian assumptions, no assumptions of independence, neither between nor
within the samples). If the number of clusters is unknown, consistency can be
achieved under appropriate assumptions on the mixing rates of the processes.
(again, no parametric or independence assumptions). In both cases we give
examples of simple (at most quadratic in each argument) algorithms which are
consistent.
From Ordinary Differential Equations to Structural Causal Models: the deterministic case
Authors: Joris M. Mooij, Dominik Janzing, Bernhard Schölkopf
Date: 2013-04-30 00:00:00

We show how, and under which conditions, the equilibrium states of a
first-order Ordinary Differential Equation (ODE) system can be described with a
deterministic Structural Causal Model (SCM). Our exposition sheds more light on
the concept of causality as expressed within the framework of Structural Causal
Models, especially for cyclic models.
Enhancements to ACL2 in Versions 5.0, 6.0, and 6.1
Authors: Matt Kaufmann, J Strother Moore
Date: 2013-04-30 00:00:00

We report on highlights of the ACL2 enhancements introduced in ACL2 releases
since the 2011 ACL2 Workshop. Although many enhancements are critical for
soundness or robustness, we focus in this paper on those improvements that
could benefit users who are aware of them, but that might not be discovered in
everyday practice.
A Hybrid Rule Based Fuzzy-Neural Expert System For Passive Network Monitoring
Authors: Azruddin Ahmad, Gobithasan Rudrusamy, Rahmat Budiarto, Azman Samsudin, Sureswaran Ramadass
Date: 2013-04-30 00:00:00

An enhanced approach for network monitoring is to create a network monitoring
tool that has artificial intelligence characteristics. There are a number of
approaches available. One such approach is by the use of a combination of rule
based, fuzzy logic and neural networks to create a hybrid ANFIS system. Such
system will have a dual knowledge database approach. One containing membership
function values to compare to and do deductive reasoning and another database
with rules deductively formulated by an expert (a network administrator). The
knowledge database will be updated continuously with newly acquired patterns.
In short, the system will be composed of 2 parts, learning from data sets and
fine-tuning the knowledge-base using neural network and the use of fuzzy logic
in making decision based on the rules and membership functions inside the
knowledge base. This paper will discuss the idea, steps and issues involved in
creating such a system.
Learning Densities Conditional on Many Interacting Features
Authors: David C. Kessler, Jack Taylor, David B. Dunson
Date: 2013-04-26 00:00:00
Tasks: Dimensionality Reduction, feature selection

Learning a distribution conditional on a set of discrete-valued features is a
commonly encountered task. This becomes more challenging with a
high-dimensional feature set when there is the possibility of interaction
between the features. In addition, many frequently applied techniques consider
only prediction of the mean, but the complete conditional density is needed to
answer more complex questions. We demonstrate a novel nonparametric Bayes
method based upon a tensor factorization of feature-dependent weights for
Gaussian kernels. The method makes use of multistage feature selection for
dimension reduction. The resulting conditional density morphs flexibly with the
selected features.
Proximal Newton-type methods for minimizing composite functions
Authors: Jason D. Lee, Yuekai Sun, Michael A. Saunders
Date: 2012-06-07 00:00:00
Tasks: Vocal Bursts Type Prediction

We generalize Newton-type methods for minimizing smooth functions to handle a
sum of two convex functions: a smooth function and a nonsmooth function with a
simple proximal mapping. We show that the resulting proximal Newton-type
methods inherit the desirable convergence behavior of Newton-type methods for
minimizing smooth functions, even when search directions are computed
inexactly. Many popular methods tailored to problems arising in bioinformatics,
signal processing, and statistical learning are special cases of proximal
Newton-type methods, and our analysis yields new convergence results for some
of these methods.
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
Authors: Ohad Shamir
Date: 2012-09-11 00:00:00

The problem of stochastic convex optimization with bandit feedback (in the
learning community) or without knowledge of gradients (in the optimization
community) has received much attention in recent years, in the form of
algorithms and performance upper bounds. However, much less is known about the
inherent complexity of these problems, and there are few lower bounds in the
literature, especially for nonlinear functions. In this paper, we investigate
the attainable error/regret in the bandit and derivative-free settings, as a
function of the dimension d and the available number of queries T. We provide a
precise characterization of the attainable performance for strongly-convex and
smooth functions, which also imply a non-trivial lower bound for more general
problems. Moreover, we prove that in both the bandit and derivative-free
setting, the required number of queries must scale at least quadratically with
the dimension. Finally, we show that on the natural class of quadratic
functions, it is possible to obtain a "fast" O(1/T) error rate in terms of T,
under mild assumptions, even without having access to gradients. To the best of
our knowledge, this is the first such rate in a derivative-free stochastic
setting, and holds despite previous results which seem to imply the contrary.
Machine Translation Systems in India
Authors: Sugata Sanyal, Rajdeep Borgohain
Date: 2013-04-29 00:00:00
Tasks: Machine Translation, Translation

Machine Translation is the translation of one natural language into another
using automated and computerized means. For a multilingual country like India,
with the huge amount of information exchanged between various regions and in
different languages in digitized format, it has become necessary to find an
automated process from one language to another. In this paper, we take a look
at the various Machine Translation System in India which is specifically built
for the purpose of translation between the Indian languages. We discuss the
various approaches taken for building the machine translation system and then
discuss some of the Machine Translation Systems in India along with their
features.
A Logic Programming Approach to Activity Recognition
Authors: A. Artikis, M. Sergot, G. Paliouras
Date: 2009-05-28 00:00:00
Tasks: Activity Recognition

We have been developing a system for recognising human activity given a
symbolic representation of video content. The input of our system is a set of
time-stamped short-term activities detected on video frames. The output of our
system is a set of recognised long-term activities, which are pre-defined
temporal combinations of short-term activities. The constraints on the
short-term activities that, if satisfied, lead to the recognition of a
long-term activity, are expressed using a dialect of the Event Calculus. We
illustrate the expressiveness of the dialect by showing the representation of
several typical complex activities. Furthermore, we present a detailed
evaluation of the system through experimentation on a benchmark dataset of
surveillance videos.
Markovian models for one dimensional structure estimation on heavily noisy imagery
Authors: Ana Georgina Flesia, Javier Gimenez, Elena Rufeil Fiori
Date: 2013-04-29 00:00:00
Tasks: Two-sample testing

Radar (SAR) images often exhibit profound appearance variations due to a
variety of factors including clutter noise produced by the coherent nature of
the illumination. Ultrasound images and infrared images have similar cluttered
appearance, that make 1 dimensional structures, as edges and object boundaries
difficult to locate. Structure information is usually extracted in two steps:
first, building and edge strength mask classifying pixels as edge points by
hypothesis testing, and secondly estimating from that mask, pixel wide
connected edges. With constant false alarm rate (CFAR) edge strength detectors
for speckle clutter, the image needs to be scanned by a sliding window composed
of several differently oriented splitting sub-windows. The accuracy of edge
location for these ratio detectors depends strongly on the orientation of the
sub-windows. In this work we propose to transform the edge strength detection
problem into a binary segmentation problem in the undecimated wavelet domain,
solvable using parallel 1d Hidden Markov Models. For general dependency models,
exact estimation of the state map becomes computationally complex, but in our
model, exact MAP is feasible. The effectiveness of our approach is demonstrated
on simulated noisy real-life natural images with available ground truth, while
the strength of our output edge map is measured with Pratt's, Baddeley an Kappa
proficiency measures. Finally, analysis and experiments on three different
types of SAR images, with different polarizations, resolutions and textures,
illustrate that the proposed method can detect structure on SAR images
effectively, providing a very good start point for active contour methods.
Learning Geo-Temporal Non-Stationary Failure and Recovery of Power Distribution
Authors: Yun Wei, Chuanyi Ji, Floyd Galvan, Stephen Couvillon, George Orellana, James Momoh
Date: 2013-04-29 00:00:00

Smart energy grid is an emerging area for new applications of machine
learning in a non-stationary environment. Such a non-stationary environment
emerges when large-scale failures occur at power distribution networks due to
external disturbances such as hurricanes and severe storms. Power distribution
networks lie at the edge of the grid, and are especially vulnerable to external
disruptions. Quantifiable approaches are lacking and needed to learn
non-stationary behaviors of large-scale failure and recovery of power
distribution. This work studies such non-stationary behaviors in three aspects.
First, a novel formulation is derived for an entire life cycle of large-scale
failure and recovery of power distribution. Second, spatial-temporal models of
failure and recovery of power distribution are developed as geo-location based
multivariate non-stationary GI(t)/G(t)/Infinity queues. Third, the
non-stationary spatial-temporal models identify a small number of parameters to
be learned. Learning is applied to two real-life examples of large-scale
disruptions. One is from Hurricane Ike, where data from an operational network
is exact on failures and recoveries. The other is from Hurricane Sandy, where
aggregated data is used for inferring failure and recovery processes at one of
the impacted areas. Model parameters are learned using real data. Two findings
emerge as results of learning: (a) Failure rates behave similarly at the two
different provider networks for two different hurricanes but differently at the
geographical regions. (b) Both rapid- and slow-recovery are present for
Hurricane Ike but only slow recovery is shown for a regional distribution
network from Hurricane Sandy.
A Probabilistic Logic Programming Event Calculus
Authors: Anastasios Skarlatidis, Alexander Artikis, Jason Filippou, Georgios Paliouras
Date: 2012-04-09 00:00:00
Tasks: Activity Recognition, Human Activity Recognition

We present a system for recognising human activity given a symbolic
representation of video content. The input of our system is a set of
time-stamped short-term activities (STA) detected on video frames. The output
is a set of recognised long-term activities (LTA), which are pre-defined
temporal combinations of STA. The constraints on the STA that, if satisfied,
lead to the recognition of a LTA, have been expressed using a dialect of the
Event Calculus. In order to handle the uncertainty that naturally occurs in
human activity recognition, we adapted this dialect to a state-of-the-art
probabilistic logic programming framework. We present a detailed evaluation and
comparison of the crisp and probabilistic approaches through experimentation on
a benchmark dataset of human surveillance videos.
On the convergence of the IRLS algorithm in Non-Local Patch Regression
Authors: Kunal. N. Chaudhury
Date: 2013-03-02 00:00:00
Tasks: Denoising, Image Denoising, regression

Recently, it was demonstrated in [CS2012,CS2013] that the robustness of the
classical Non-Local Means (NLM) algorithm [BCM2005] can be improved by
incorporating $\ell^p (0 < p \leq 2)$ regression into the NLM framework. This
general optimization framework, called Non-Local Patch Regression (NLPR),
contains NLM as a special case. Denoising results on synthetic and natural
images show that NLPR consistently performs better than NLM beyond a moderate
noise level, and significantly so when $p$ is close to zero. An iteratively
reweighted least-squares (IRLS) algorithm was proposed for solving the
regression problem in NLPR, where the NLM output was used to initialize the
iterations. Based on exhaustive numerical experiments, we observe that the IRLS
algorithm is globally convergent (for arbitrary initialization) in the convex
regime $1 \leq p \leq 2$, and locally convergent (fails very rarely using NLM
initialization) in the non-convex regime $0 < p < 1$. In this letter, we adapt
the "majorize-minimize" framework introduced in [Voss1980] to explain these
observations.
  [CS2012] Chaudhury et al. (2012), "Non-local Euclidean medians," IEEE Signal
Processing Letters.
  [CS2013] Chaudhury et al. (2013), "Non-local patch regression: Robust image
denoising in patch space," IEEE ICASSP.
  [BCM2005] Buades et al. (2005), "A review of image denoising algorithms, with
a new one," Multiscale Modeling and Simulation.
  [Voss1980] Voss et al. (1980), "Linear convergence of generalized Weiszfeld's
method," Computing.
Simulated Car Racing Championship: Competition Software Manual
Authors: Daniele Loiacono, Luigi Cardamone, Pier Luca Lanzi
Date: 2013-04-05 00:00:00
Tasks: Car Racing

This manual describes the competition software for the Simulated Car Racing
Championship, an international competition held at major conferences in the
field of Evolutionary Computation and in the field of Computational
Intelligence and Games. It provides an overview of the architecture, the
instructions to install the software and to run the simple drivers provided in
the package, the description of the sensors and the actuators.
A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem
Authors: Xiaolin Tang, Chunhua Yang, Xiaojun Zhou, Weihua Gui
Date: 2013-04-29 00:00:00
Tasks: Combinatorial Optimization, Traveling Salesman Problem

Generalized traveling salesman problem (GTSP) is an extension of classical
traveling salesman problem (TSP), which is a combinatorial optimization problem
and an NP-hard problem. In this paper, an efficient discrete state transition
algorithm (DSTA) for GTSP is proposed, where a new local search operator named
\textit{K-circle}, directed by neighborhood information in space, has been
introduced to DSTA to shrink search space and strengthen search ability. A
novel robust update mechanism, restore in probability and risk in probability
(Double R-Probability), is used in our work to escape from local minima. The
proposed algorithm is tested on a set of GTSP instances. Compared with other
heuristics, experimental results have demonstrated the effectiveness and strong
adaptability of DSTA and also show that DSTA has better search ability than its
competitors.
Optimal amortized regret in every interval
Authors: Rina Panigrahy, Preyas Popat
Date: 2013-04-29 00:00:00

Consider the classical problem of predicting the next bit in a sequence of
bits. A standard performance measure is {\em regret} (loss in payoff) with
respect to a set of experts. For example if we measure performance with respect
to two constant experts one that always predicts 0's and another that always
predicts 1's it is well known that one can get regret $O(\sqrt T)$ with respect
to the best expert by using, say, the weighted majority algorithm. But this
algorithm does not provide performance guarantee in any interval. There are
other algorithms that ensure regret $O(\sqrt {x \log T})$ in any interval of
length $x$. In this paper we show a randomized algorithm that in an amortized
sense gets a regret of $O(\sqrt x)$ for any interval when the sequence is
partitioned into intervals arbitrarily. We empirically estimated the constant
in the $O()$ for $T$ upto 2000 and found it to be small -- around 2.1. We also
experimentally evaluate the efficacy of this algorithm in predicting high
frequency stock data.