pwc-archive/papers-with-abstracts huggingface dataset:
Decentralized Online Big Data Classification - a Bandit Framework
Authors: Cem Tekin, Mihaela van der Schaar
Date: 2013-08-21 00:00:00
Tasks: Classification, General Classification

Distributed, online data mining systems have emerged as a result of
applications requiring analysis of large amounts of correlated and
high-dimensional data produced by multiple distributed data sources. We propose
a distributed online data classification framework where data is gathered by
distributed data sources and processed by a heterogeneous set of distributed
learners which learn online, at run-time, how to classify the different data
streams either by using their locally available classification functions or by
helping each other by classifying each other's data. Importantly, since the
data is gathered at different locations, sending the data to another learner to
process incurs additional costs such as delays, and hence this will be only
beneficial if the benefits obtained from a better classification will exceed
the costs. We assume that the classification functions available to each
processing element are fixed, but their prediction accuracy for various types
of incoming data are unknown and can change dynamically over time, and thus
they need to be learned online. We model the problem of joint classification by
the distributed and heterogeneous learners from multiple data sources as a
distributed contextual bandit problem where each data is characterized by a
specific context. We develop distributed online learning algorithms for which
we can prove that they have sublinear regret. Compared to prior work in
distributed online data mining, our work is the first to provide analytic
regret results characterizing the performance of the proposed algorithms.
A Decomposition of the Max-min Fair Curriculum-based Course Timetabling Problem
Authors: Moritz Mühlenthaler, Rolf Wanka
Date: 2013-06-24 00:00:00
Tasks: Fairness

We propose a decomposition of the max-min fair curriculum-based course
timetabling (MMF-CB-CTT) problem. The decomposition models the room assignment
subproblem as a generalized lexicographic bottleneck optimization problem
(LBOP). We show that the generalized LBOP can be solved efficiently if the
corresponding sum optimization problem can be solved efficiently. As a
consequence, the room assignment subproblem of the MMF-CB-CTT problem can be
solved efficiently. We use this insight to improve a previously proposed
heuristic algorithm for the MMF-CB-CTT problem. Our experimental results
indicate that using the new decomposition improves the performance of the
algorithm on most of the 21 ITC2007 test instances with respect to the quality
of the best solution found. Furthermore, we introduce a measure of the quality
of a solution to a max-min fair optimization problem. This measure helps to
overcome some limitations imposed by the qualitative nature of max-min fairness
and aids the statistical evaluation of the performance of randomized algorithms
for such problems. We use this measure to show that using the new decomposition
the algorithm outperforms the original one on most instances with respect to
the average solution quality.
Dynamic Reasoning Systems
Authors: Daniel G. Schwartz
Date: 2013-08-25 00:00:00

A {\it dynamic reasoning system} (DRS) is an adaptation of a conventional
formal logical system that explicitly portrays reasoning as a temporal
activity, with each extralogical input to the system and each inference rule
application being viewed as occurring at a distinct time step. Every DRS
incorporates some well-defined logic together with a controller that serves to
guide the reasoning process in response to user inputs. Logics are generic,
whereas controllers are application-specific. Every controller does,
nonetheless, provide an algorithm for nonmonotonic belief revision. The general
notion of a DRS comprises a framework within which one can formulate the logic
and algorithms for a given application and prove that the algorithms are
correct, i.e., that they serve to (i) derive all salient information and (ii)
preserve the consistency of the belief set. This paper illustrates the idea
with ordinary first-order predicate calculus, suitably modified for the present
purpose, and two examples. The latter example revisits some classic
nonmonotonic reasoning puzzles (Opus the Penguin, Nixon Diamond) and shows how
these can be resolved in the context of a DRS, using an expanded version of
first-order logic that incorporates typed predicate symbols. All concepts are
rigorously defined and effectively computable, thereby providing the foundation
for a future software implementation.
A stochastic hybrid model of a biological filter
Authors: Andrea Ocone, Guido Sanguinetti
Date: 2013-08-24 00:00:00

We present a hybrid model of a biological filter, a genetic circuit which
removes fast fluctuations in the cell's internal representation of the extra
cellular environment. The model takes the classic feed-forward loop (FFL) motif
and represents it as a network of continuous protein concentrations and binary,
unobserved gene promoter states. We address the problem of statistical
inference and parameter learning for this class of models from partial,
discrete time observations. We show that the hybrid representation leads to an
efficient algorithm for approximate statistical inference in this circuit, and
show its effectiveness on a simulated data set.
An Integrated Framework for Diagnosis and Prognosis of Hybrid Systems
Authors: Elodie Chanthery, Pauline Ribot
Date: 2013-08-24 00:00:00
Tasks: Prognosis

Complex systems are naturally hybrid: their dynamic behavior is both
continuous and discrete. For these systems, maintenance and repair are an
increasing part of the total cost of final product. Efficient diagnosis and
prognosis techniques have to be adopted to detect, isolate and anticipate
faults. This paper presents an original integrated theoretical framework for
diagnosis and prognosis of hybrid systems. The formalism used for hybrid
diagnosis is enriched in order to be able to follow the evolution of an aging
law for each fault of the system. The paper presents a methodology for
interleaving diagnosis and prognosis in a hybrid framework.
Monitoring with uncertainty
Authors: Ezio Bartocci, Radu Grosu
Date: 2013-08-24 00:00:00

We discuss the problem of runtime verification of an instrumented program
that misses to emit and to monitor some events. These gaps can occur when a
monitoring overhead control mechanism is introduced to disable the monitor of
an application with real-time constraints. We show how to use statistical
models to learn the application behavior and to "fill in" the introduced gaps.
Finally, we present and discuss some techniques developed in the last three
years to estimate the probability that a property of interest is violated in
the presence of an incomplete trace.
Evolution Theory of Self-Evolving Autonomous Problem Solving Systems
Authors: Seppo Ilari Tirri
Date: 2013-08-24 00:00:00

The present study gives a mathematical framework for self-evolution within
autonomous problem solving systems. Special attention is set on universal
abstraction, thereof generation by net block homomorphism, consequently
multiple order solving systems and the overall decidability of the set of the
solutions. By overlapping presentation of nets new abstraction relation among
nets is formulated alongside with consequent alphabetical net block renetting
system proportional to normal forms of renetting systems regarding the
operational power. A new structure in self-evolving problem solving is
established via saturation by groups of equivalence relations and iterative
closures of generated quotient transducer algebras over the whole evolution.
Edge-detection applied to moving sand dunes on Mars
Authors: Amelia Carolina Sparavigna
Date: 2013-08-24 00:00:00
Tasks: Edge Detection, Sand

Here we discuss the application of an edge detection filter, the Sobel filter
of GIMP, to the recently discovered motion of some sand dunes on Mars. The
filter allows a good comparison of an image HiRISE of 2007 and an image of 1999
recorded by the Mars Global Surveyor of the dunes in the Nili Patera caldera,
measuring therefore the motion of the dunes on a longer period of time than
that previously investigated.
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Authors: Rishabh Iyer, Jeff Bilmes
Date: 2012-07-03 00:00:00
Tasks: feature selection

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions
representable as a difference between submodular functions. Similar to [30],
our new algorithms are guaranteed to monotonically reduce the objective
function at every step. We empirically and theoretically show that the
per-iteration cost of our algorithms is much less than [30], and our algorithms
can be used to efficiently minimize a difference between submodular functions
under various combinatorial constraints, a problem not previously addressed. We
provide computational bounds and a hardness result on the mul- tiplicative
inapproximability of minimizing the difference between submodular functions. We
show, however, that it is possible to give worst-case additive bounds by
providing a polynomial time computable lower-bound on the minima. Finally we
show how a number of machine learning problems can be modeled as minimizing the
difference between submodular functions. We experimentally show the validity of
our algorithms by testing them on the problem of feature selection with
submodular cost features.
Ensemble of Distributed Learners for Online Classification of Dynamic Data Streams
Authors: Luca Canzian, Yu Zhang, Mihaela van der Schaar
Date: 2013-08-24 00:00:00
Tasks: Ensemble Learning, General Classification

We present an efficient distributed online learning scheme to classify data
captured from distributed, heterogeneous, and dynamic data sources. Our scheme
consists of multiple distributed local learners, that analyze different streams
of data that are correlated to a common event that needs to be classified. Each
learner uses a local classifier to make a local prediction. The local
predictions are then collected by each learner and combined using a weighted
majority rule to output the final prediction. We propose a novel online
ensemble learning algorithm to update the aggregation rule in order to adapt to
the underlying data dynamics. We rigorously determine a bound for the worst
case misclassification probability of our algorithm which depends on the
misclassification probabilities of the best static aggregation rule, and of the
best local classifier. Importantly, the worst case misclassification
probability of our algorithm tends asymptotically to 0 if the misclassification
probability of the best static aggregation rule or the misclassification
probability of the best local classifier tend to 0. Then we extend our
algorithm to address challenges specific to the distributed implementation and
we prove new bounds that apply to these settings. Finally, we test our scheme
by performing an evaluation study on several data sets. When applied to data
sets widely used by the literature dealing with dynamic data streams and
concept drift, our scheme exhibits performance gains ranging from 34% to 71%
with respect to state of the art solutions.
The Lovasz-Bregman Divergence and connections to rank aggregation, clustering, and web ranking
Authors: Rishabh Iyer, Jeff Bilmes
Date: 2013-08-24 00:00:00
Tasks: Clustering, Information Retrieval, Learning-To-Rank, Retrieval

We extend the recently introduced theory of Lovasz-Bregman (LB) divergences
(Iyer & Bilmes, 2012) in several ways. We show that they represent a distortion
between a 'score' and an 'ordering', thus providing a new view of rank
aggregation and order based clustering with interesting connections to web
ranking. We show how the LB divergences have a number of properties akin to
many permutation based metrics, and in fact have as special cases forms very
similar to the Kendall-$\tau$ metric. We also show how the LB divergences
subsume a number of commonly used ranking measures in information retrieval,
like the NDCG and AUC. Unlike the traditional permutation based metrics,
however, the LB divergence naturally captures a notion of "confidence" in the
orderings, thus providing a new representation to applications involving
aggregating scores as opposed to just orderings. We show how a number of
recently used web ranking models are forms of Lovasz-Bregman rank aggregation
and also observe that a natural form of Mallow's model using the LB divergence
has been used as conditional ranking models for the 'Learning to Rank' problem.
Understanding the Predictive Power of Computational Mechanics and Echo State Networks in Social Media
Authors: David Darmon, Jared Sylvester, Michelle Girvan, William Rand
Date: 2013-06-26 00:00:00

There is a large amount of interest in understanding users of social media in
order to predict their behavior in this space. Despite this interest, user
predictability in social media is not well-understood. To examine this
question, we consider a network of fifteen thousand users on Twitter over a
seven week period. We apply two contrasting modeling paradigms: computational
mechanics and echo state networks. Both methods attempt to model the behavior
of users on the basis of their past behavior. We demonstrate that the behavior
of users on Twitter can be well-modeled as processes with self-feedback. We
find that the two modeling approaches perform very similarly for most users,
but that they differ in performance on a small subset of the users. By
exploring the properties of these performance-differentiated users, we
highlight the challenges faced in applying predictive models to dynamic social
data.
Geodesic-based Salient Object Detection
Authors: Richard M Jiang
Date: 2013-02-26 00:00:00
Tasks: Object, object-detection, Object Detection, RGB Salient Object Detection, Saliency Detection, Saliency Prediction, Salient Object Detection

Saliency detection has been an intuitive way to provide useful cues for
object detection and segmentation, as desired for many vision and graphics
applications. In this paper, we provided a robust method for salient object
detection and segmentation. Other than using various pixel-level contrast
definitions, we exploited global image structures and proposed a new geodesic
method dedicated for salient object detection. In the proposed approach, a new
geodesic scheme, namely geodesic tunneling is proposed to tackle with textures
and local chaotic structures. With our new geodesic approach, a geodesic
saliency map is estimated in correspondence to spatial structures in an image.
Experimental evaluation on a salient object benchmark dataset validated that
our algorithm consistently outperformed a number of the state-of-art saliency
methods, yielding higher precision and better recall rates. With the robust
saliency estimation, we also present an unsupervised hierarchical salient
object cut scheme simply using adaptive saliency thresholding, which attained
the highest score in our F-measure test. We also applied our geodesic cut
scheme to a number of image editing tasks as demonstrated in additional
experiments.
Manopt, a Matlab toolbox for optimization on manifolds
Authors: Nicolas Boumal, Bamdev Mishra, P. -A. Absil, Rodolphe Sepulchre
Date: 2013-08-23 00:00:00
Tasks: Dimensionality Reduction, Low-Rank Matrix Completion, Matrix Completion, Metric Learning, Riemannian optimization

Optimization on manifolds is a rapidly developing branch of nonlinear
optimization. Its focus is on problems where the smooth geometry of the search
space can be leveraged to design efficient numerical algorithms. In particular,
optimization on manifolds is well-suited to deal with rank and orthogonality
constraints. Such structured constraints appear pervasively in machine learning
applications, including low-rank matrix completion, sensor network
localization, camera network registration, independent component analysis,
metric learning, dimensionality reduction and so on. The Manopt toolbox,
available at www.manopt.org, is a user-friendly, documented piece of software
dedicated to simplify experimenting with state of the art Riemannian
optimization algorithms. We aim particularly at reaching practitioners outside
our field.
Spectral redemption: clustering sparse networks
Authors: Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhang
Date: 2013-06-24 00:00:00
Tasks: Clustering, Community Detection, Stochastic Block Model

Spectral algorithms are classic approaches to clustering and community
detection in networks. However, for sparse networks the standard versions of
these algorithms are suboptimal, in some cases completely failing to detect
communities even when other algorithms such as belief propagation can do so.
Here we introduce a new class of spectral algorithms based on a
non-backtracking walk on the directed edges of the graph. The spectrum of this
operator is much better-behaved than that of the adjacency matrix or other
commonly used matrices, maintaining a strong separation between the bulk
eigenvalues and the eigenvalues relevant to community structure even in the
sparse case. We show that our algorithm is optimal for graphs generated by the
stochastic block model, detecting communities all the way down to the
theoretical limit. We also show the spectrum of the non-backtracking operator
for some real-world networks, illustrating its advantages over traditional
spectral clustering.
Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors
Authors: Patrick Breheny, Jian Huang
Date: 2012-09-10 00:00:00
Tasks: regression, Variable Selection

Penalized regression is an attractive framework for variable selection
problems. Often, variables possess a grouping structure, and the relevant
selection problem is that of selecting groups, not individual variables. The
group lasso has been proposed as a way of extending the ideas of the lasso to
the problem of group selection. Nonconvex penalties such as SCAD and MCP have
been proposed and shown to have several advantages over the lasso; these
penalties may also be extended to the group selection problem, giving rise to
group SCAD and group MCP methods. Here, we describe algorithms for fitting
these models stably and efficiently. In addition, we present simulation results
and real data examples comparing and contrasting the statistical properties of
these methods.
Artificial Immune Systems (INTROS 2)
Authors: Uwe Aickelin, Dipankar Dasgupta, Feng Gu
Date: 2013-08-23 00:00:00

The biological immune system is a robust, complex, adaptive system that
defends the body from foreign pathogens. It is able to categorize all cells (or
molecules) within the body as self or non-self substances. It does this with
the help of a distributed task force that has the intelligence to take action
from a local and also a global perspective using its network of chemical
messengers for communication. There are two major branches of the immune
system. The innate immune system is an unchanging mechanism that detects and
destroys certain invading organisms, whilst the adaptive immune system responds
to previously unknown foreign cells and builds a response to them that can
remain in the body over a long period of time. This remarkable information
processing biological system has caught the attention of computer science in
recent years.
  A novel computational intelligence technique, inspired by immunology, has
emerged, called Artificial Immune Systems. Several concepts from the immune
system have been extracted and applied for solution to real world science and
engineering problems. In this tutorial, we briefly describe the immune system
metaphors that are relevant to existing Artificial Immune Systems methods. We
will then show illustrative real-world problems suitable for Artificial Immune
Systems and give a step-by-step algorithm walkthrough for one such problem. A
comparison of the Artificial Immune Systems to other well-known algorithms,
areas for future work, tips & tricks and a list of resources will round this
tutorial off. It should be noted that as Artificial Immune Systems is still a
young and evolving field, there is not yet a fixed algorithm template and hence
actual implementations might differ somewhat from time to time and from those
examples given here.
Measuring the Directional Distance Between Fuzzy Sets
Authors: Josie McCulloch, Christian Wagner, Uwe Aickelin
Date: 2013-08-23 00:00:00

The measure of distance between two fuzzy sets is a fundamental tool within
fuzzy set theory. However, current distance measures within the literature do
not account for the direction of change between fuzzy sets; a useful concept in
a variety of applications, such as Computing With Words. In this paper, we
highlight this utility and introduce a distance measure which takes the
direction between sets into account. We provide details of its application for
normal and non-normal, as well as convex and non-convex fuzzy sets. We
demonstrate the new distance measure using real data from the MovieLens dataset
and establish the benefits of measuring the direction between fuzzy sets.
Extending Similarity Measures of Interval Type-2 Fuzzy Sets to General Type-2 Fuzzy Sets
Authors: Josie McCulloch, Christian Wagner, Uwe Aickelin
Date: 2013-08-23 00:00:00
Tasks: Vocal Bursts Type Prediction

Similarity measures provide one of the core tools that enable reasoning about
fuzzy sets. While many types of similarity measures exist for type-1 and
interval type-2 fuzzy sets, there are very few similarity measures that enable
the comparison of general type-2 fuzzy sets. In this paper, we introduce a
general method for extending existing interval type-2 similarity measures to
similarity measures for general type-2 fuzzy sets. Specifically, we show how
similarity measures for interval type-2 fuzzy sets can be employed in
conjunction with the zSlices based general type-2 representation for fuzzy sets
to provide measures of similarity which preserve all the common properties
(i.e. reflexivity, symmetry, transitivity and overlapping) of the original
interval type-2 similarity measure. We demonstrate examples of such extended
fuzzy measures and provide comparisons between (different types of) interval
and general type-2 fuzzy measures.
Coupled Neural Associative Memories
Authors: Amin Karbasi, Amir Hesam Salavati, Amin Shokrollahi
Date: 2013-01-08 00:00:00
Tasks: Retrieval

We propose a novel architecture to design a neural associative memory that is
capable of learning a large number of patterns and recalling them later in
presence of noise. It is based on dividing the neurons into local clusters and
parallel plains, very similar to the architecture of the visual cortex of
macaque brain. The common features of our proposed architecture with those of
spatially-coupled codes enable us to show that the performance of such networks
in eliminating noise is drastically better than the previous approaches while
maintaining the ability of learning an exponentially large number of patterns.
Previous work either failed in providing good performance during the recall
phase or in offering large pattern retrieval (storage) capacities. We also
present computational experiments that lend additional support to the
theoretical analysis.