pwc-archive/papers-with-abstracts huggingface dataset:
Dynamic stochastic blockmodels: Statistical models for time-evolving networks
Authors: Kevin S. Xu, Alfred O. Hero III
Date: 2013-04-22 00:00:00

Significant efforts have gone into the development of statistical models for
analyzing data in the form of networks, such as social networks. Most existing
work has focused on modeling static networks, which represent either a single
time snapshot or an aggregate view over time. There has been recent interest in
statistical modeling of dynamic networks, which are observed at multiple points
in time and offer a richer representation of many complex phenomena. In this
paper, we propose a state-space model for dynamic networks that extends the
well-known stochastic blockmodel for static networks to the dynamic setting. We
then propose a procedure to fit the model using a modification of the extended
Kalman filter augmented with a local search. We apply the procedure to analyze
a dynamic social network of email communication.
Three Generalizations of the FOCUS Constraint
Authors: Nina Narodytska, Thierry Petit, Mohamed Siala, Toby Walsh
Date: 2013-04-22 00:00:00

The FOCUS constraint expresses the notion that solutions are concentrated. In
practice, this constraint suffers from the rigidity of its semantics. To tackle
this issue, we propose three generalizations of the FOCUS constraint. We
provide for each one a complete filtering algorithm as well as discussing
decompositions.
Backdoors to Abduction
Authors: Andreas Pfandler, Stefan Rümmele, Stefan Szeider
Date: 2013-04-22 00:00:00
Tasks: Fault Diagnosis

Abductive reasoning (or Abduction, for short) is among the most fundamental
AI reasoning methods, with a broad range of applications, including fault
diagnosis, belief revision, and automated planning. Unfortunately, Abduction is
of high computational complexity; even propositional Abduction is
\Sigma_2^P-complete and thus harder than NP and coNP. This complexity barrier
rules out the existence of a polynomial transformation to propositional
satisfiability (SAT). In this work we use structural properties of the
Abduction instance to break this complexity barrier. We utilize the problem
structure in terms of small backdoor sets. We present fixed-parameter tractable
transformations from Abduction to SAT, which make the power of today's SAT
solvers available to Abduction.
Learning loopy graphical models with latent variables: Efficient methods and guarantees
Authors: Animashree Anandkumar, Ragupathyraj Valluvan
Date: 2012-03-17 00:00:00

The problem of structure estimation in graphical models with latent variables
is considered. We characterize conditions for tractable graph estimation and
develop efficient methods with provable guarantees. We consider models where
the underlying Markov graph is locally tree-like, and the model is in the
regime of correlation decay. For the special case of the Ising model, the
number of samples $n$ required for structural consistency of our method scales
as $n=\Omega(\theta_{\min}^{-\delta\eta(\eta+1)-2}\log p)$, where p is the
number of variables, $\theta_{\min}$ is the minimum edge potential, $\delta$ is
the depth (i.e., distance from a hidden node to the nearest observed nodes),
and $\eta$ is a parameter which depends on the bounds on node and edge
potentials in the Ising model. Necessary conditions for structural consistency
under any algorithm are derived and our method nearly matches the lower bound
on sample requirements. Further, the proposed method is practical to implement
and provides flexibility to control the number of latent variables and the
cycle lengths in the output graph.
A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction
Authors: Tobias Buer, Herbert Kopfer
Date: 2012-01-20 00:00:00

The bi-objective winner determination problem (2WDP-SC) of a combinatorial
procurement auction for transport contracts is characterized by a set B of
bundle bids, with each bundle bid b in B consisting of a bidding carrier c_b, a
bid price p_b, and a set tau_b transport contracts which is a subset of the set
T of tendered transport contracts. Additionally, the transport quality
q_{t,c_b} is given which is expected to be realized when a transport contract t
is executed by a carrier c_b. The task of the auctioneer is to find a set X of
winning bids (X subset B), such that each transport contract is part of at
least one winning bid, the total procurement costs are minimized, and the total
transport quality is maximized. This article presents a metaheuristic approach
for the 2WDP-SC which integrates the greedy randomized adaptive search
procedure with a two-stage candidate component selection procedure, large
neighborhood search, and self-adaptive parameter setting in order to find a
competitive set of non-dominated solutions. The heuristic outperforms all
existing approaches. For seven small benchmark instances, the heuristic is the
sole approach that finds all Pareto-optimal solutions. For 28 out of 30 large
instances, none of the existing approaches is able to compute a solution that
dominates a solution found by the proposed heuristic.
Towards an Extension of the 2-tuple Linguistic Model to Deal With Unbalanced Linguistic Term sets
Authors: Mohammed-Amine Abchir, Isis Truck
Date: 2013-04-22 00:00:00
Tasks: Decision Making

In the domain of Computing with words (CW), fuzzy linguistic approaches are
known to be relevant in many decision-making problems. Indeed, they allow us to
model the human reasoning in replacing words, assessments, preferences,
choices, wishes... by ad hoc variables, such as fuzzy sets or more
sophisticated variables.
  This paper focuses on a particular model: Herrera & Martinez' 2-tuple
linguistic model and their approach to deal with unbalanced linguistic term
sets. It is interesting since the computations are accomplished without loss of
information while the results of the decision-making processes always refer to
the initial linguistic term set. They propose a fuzzy partition which
distributes data on the axis by using linguistic hierarchies to manage the
non-uniformity. However, the required input (especially the density around the
terms) taken by their fuzzy partition algorithm may be considered as too much
demanding in a real-world application, since density is not always easy to
determine. Moreover, in some limit cases (especially when two terms are very
closed semantically to each other), the partition doesn't comply with the data
themselves, it isn't close to the reality. Therefore we propose to modify the
required input, in order to offer a simpler and more faithful partition. We
have added an extension to the package jFuzzyLogic and to the corresponding
script language FCL. This extension supports both 2-tuple models: Herrera &
Martinez' and ours. In addition to the partition algorithm, we present two
aggregation algorithms: the arithmetic means and the addition. We also discuss
these kinds of 2-tuple models.
Distributed User Profiling via Spectral Methods
Authors: Dan-Cristian Tomozei, Laurent Massoulié
Date: 2011-09-15 00:00:00

User profiling is a useful primitive for constructing personalised services,
such as content recommendation. In the present paper we investigate the
feasibility of user profiling in a distributed setting, with no central
authority and only local information exchanges between users. We compute a
profile vector for each user (i.e., a low-dimensional vector that characterises
her taste) via spectral transformation of observed user-produced ratings for
items. Our two main contributions follow: i) We consider a low-rank
probabilistic model of user taste. More specifically, we consider that users
and items are partitioned in a constant number of classes, such that users and
items within the same class are statistically identical. We prove that without
prior knowledge of the compositions of the classes, based solely on few random
observed ratings (namely $O(N\log N)$ such ratings for $N$ users), we can
predict user preference with high probability for unrated items by running a
local vote among users with similar profile vectors. In addition, we provide
empirical evaluations characterising the way in which spectral profiling
performance depends on the dimension of the profile space. Such evaluations are
performed on a data set of real user ratings provided by Netflix. ii) We
develop distributed algorithms which provably achieve an embedding of users
into a low-dimensional space, based on spectral transformation. These involve
simple message passing among users, and provably converge to the desired
embedding. Our method essentially relies on a novel combination of gossiping
and the algorithm proposed by Oja and Karhunen.
Dealing with natural language interfaces in a geolocation context
Authors: M. -A. Abchir, Isis Truck, Anna Pappa
Date: 2013-04-22 00:00:00

In the geolocation field where high-level programs and low-level devices
coexist, it is often difficult to find a friendly user inter- face to configure
all the parameters. The challenge addressed in this paper is to propose
intuitive and simple, thus natural lan- guage interfaces to interact with
low-level devices. Such inter- faces contain natural language processing and
fuzzy represen- tations of words that facilitate the elicitation of
business-level objectives in our context.
Asymptotic Generalization Bound of Fisher's Linear Discriminant Analysis
Authors: Wei Bian, DaCheng Tao
Date: 2012-08-15 00:00:00
Tasks: Binary Classification, Dimensionality Reduction

Fisher's linear discriminant analysis (FLDA) is an important dimension
reduction method in statistical pattern recognition. It has been shown that
FLDA is asymptotically Bayes optimal under the homoscedastic Gaussian
assumption. However, this classical result has the following two major
limitations: 1) it holds only for a fixed dimensionality $D$, and thus does not
apply when $D$ and the training sample size $N$ are proportionally large; 2) it
does not provide a quantitative description on how the generalization ability
of FLDA is affected by $D$ and $N$. In this paper, we present an asymptotic
generalization analysis of FLDA based on random matrix theory, in a setting
where both $D$ and $N$ increase and $D/N\longrightarrow\gamma\in[0,1)$. The
obtained lower bound of the generalization discrimination power overcomes both
limitations of the classical result, i.e., it is applicable when $D$ and $N$
are proportionally large and provides a quantitative description of the
generalization ability of FLDA in terms of the ratio $\gamma=D/N$ and the
population discrimination power. Besides, the discrimination power bound also
leads to an upper bound on the generalization error of binary-classification
with FLDA.
Bargaining for Revenue Shares on Tree Trading Networks
Authors: Arpita Ghosh, Satyen Kale, Kevin Lang, Benjamin Moseley
Date: 2013-04-22 00:00:00

We study trade networks with a tree structure, where a seller with a single
indivisible good is connected to buyers, each with some value for the good, via
a unique path of intermediaries. Agents in the tree make multiplicative revenue
share offers to their parent nodes, who choose the best offer and offer part of
it to their parent, and so on; the winning path is determined by who finally
makes the highest offer to the seller. In this paper, we investigate how these
revenue shares might be set via a natural bargaining process between agents on
the tree, specifically, egalitarian bargaining between endpoints of each edge
in the tree. We investigate the fixed point of this system of bargaining
equations and prove various desirable for this solution concept, including (i)
existence, (ii) uniqueness, (iii) efficiency, (iv) membership in the core, (v)
strict monotonicity, (vi) polynomial-time computability to any given accuracy.
Finally, we present numerical evidence that asynchronous dynamics with randomly
ordered updates always converges to the fixed point, indicating that the fixed
point shares might arise from decentralized bargaining amongst agents on the
trade network.
Infinitely imbalanced binomial regression and deformed exponential families
Authors: Tomonari Sei
Date: 2013-03-29 00:00:00
Tasks: regression

The logistic regression model is known to converge to a Poisson point process
model if the binary response tends to infinitely imbalanced. In this paper, it
is shown that this phenomenon is universal in a wide class of link functions on
binomial regression. The proof relies on the extreme value theory. For the
logit, probit and complementary log-log link functions, the intensity measure
of the point process becomes an exponential family. For some other link
functions, deformed exponential families appear. A penalized maximum likelihood
estimator for the Poisson point process model is suggested.
A novice looks at emotional cognition
Authors: Rajendra K. Bera
Date: 2013-04-21 00:00:00

Modeling emotional-cognition is in a nascent stage and therefore wide-open
for new ideas and discussions. In this paper the author looks at the modeling
problem by bringing in ideas from axiomatic mathematics, information theory,
computer science, molecular biology, non-linear dynamical systems and quantum
computing and explains how ideas from these disciplines may have applications
in modeling emotional-cognition.
Multiple graph regularized protein domain ranking
Authors: Jim Jing-Yan Wang, Halima Bensmail, Xin Gao
Date: 2012-08-18 00:00:00

Background Protein domain ranking is a fundamental task in structural
biology. Most protein domain ranking methods rely on the pairwise comparison of
protein domains while neglecting the global manifold structure of the protein
domain database. Recently, graph regularized ranking that exploits the global
structure of the graph defined by the pairwise similarities has been proposed.
However, the existing graph regularized ranking methods are very sensitive to
the choice of the graph model and parameters, and this remains a difficult
problem for most of the protein domain ranking methods.
  Results To tackle this problem, we have developed the Multiple Graph
regularized Ranking algorithm, MultiG- Rank. Instead of using a single graph to
regularize the ranking scores, MultiG-Rank approximates the intrinsic manifold
of protein domain distribution by combining multiple initial graphs for the
regularization. Graph weights are learned with ranking scores jointly and
automatically, by alternately minimizing an ob- jective function in an
iterative algorithm. Experimental results on a subset of the ASTRAL SCOP
protein domain database demonstrate that MultiG-Rank achieves a better ranking
performance than single graph regularized ranking methods and pairwise
similarity based ranking methods.
  Conclusion The problem of graph model and parameter selection in graph
regularized protein domain ranking can be solved effectively by combining
multiple graphs. This aspect of generalization introduces a new frontier in
applying multiple graphs to solving protein domain ranking applications.
Analytic Feature Selection for Support Vector Machines
Authors: Carly Stambaugh, Hui Yang, Felix Breuer
Date: 2013-04-20 00:00:00
Tasks: feature selection

Support vector machines (SVMs) rely on the inherent geometry of a data set to
classify training data. Because of this, we believe SVMs are an excellent
candidate to guide the development of an analytic feature selection algorithm,
as opposed to the more commonly used heuristic methods. We propose a
filter-based feature selection algorithm based on the inherent geometry of a
feature set. Through observation, we identified six geometric properties that
differ between optimal and suboptimal feature sets, and have statistically
significant correlations to classifier performance. Our algorithm is based on
logistic and linear regression models using these six geometric properties as
predictor variables. The proposed algorithm achieves excellent results on high
dimensional text data sets, with features that can be organized into a handful
of feature types; for example, unigrams, bigrams or semantic structural
features. We believe this algorithm is a novel and effective approach to
solving the feature selection problem for linear SVMs.
Graph Estimation From Multi-attribute Data
Authors: Mladen Kolar, Han Liu, Eric P. Xing
Date: 2012-10-29 00:00:00
Tasks: Attribute

Many real world network problems often concern multivariate nodal attributes
such as image, textual, and multi-view feature vectors on nodes, rather than
simple univariate nodal attributes. The existing graph estimation methods built
on Gaussian graphical models and covariance selection algorithms can not handle
such data, neither can the theories developed around such methods be directly
applied. In this paper, we propose a new principled framework for estimating
graphs from multi-attribute data. Instead of estimating the partial correlation
as in current literature, our method estimates the partial canonical
correlations that naturally accommodate complex nodal features.
Computationally, we provide an efficient algorithm which utilizes the
multi-attribute structure. Theoretically, we provide sufficient conditions
which guarantee consistent graph recovery. Extensive simulation studies
demonstrate performance of our method under various conditions. Furthermore, we
provide illustrative applications to uncovering gene regulatory networks from
gene and protein profiles, and uncovering brain connectivity graph from
functional magnetic resonance imaging data.
A Survey on Multi-view Learning
Authors: Chang Xu, DaCheng Tao, Chao Xu
Date: 2013-04-20 00:00:00
Tasks: MULTI-VIEW LEARNING, Survey

In recent years, a great many methods of learning from multi-view data by
considering the diversity of different views have been proposed. These views
may be obtained from multiple sources or different feature subsets. In trying
to organize and highlight similarities and differences between the variety of
multi-view learning approaches, we review a number of representative multi-view
learning algorithms in different areas and classify them into three groups: 1)
co-training, 2) multiple kernel learning, and 3) subspace learning. Notably,
co-training style algorithms train alternately to maximize the mutual agreement
on two distinct views of the data; multiple kernel learning algorithms exploit
kernels that naturally correspond to different views and combine kernels either
linearly or non-linearly to improve learning performance; and subspace learning
algorithms aim to obtain a latent subspace shared by multiple views by assuming
that the input views are generated from this latent subspace. Though there is
significant variance in the approaches to integrating multiple views to improve
learning performance, they mainly exploit either the consensus principle or the
complementary principle to ensure the success of multi-view learning. Since
accessing multiple views is the fundament of multi-view learning, with the
exception of study on learning a model from multiple views, it is also valuable
to study how to construct multiple views and how to evaluate these views.
Overall, by exploring the consistency and complementary properties of different
views, multi-view learning is rendered more effective, more promising, and has
better generalization ability than single-view learning.
Computational Capabilities of Random Automata Networks for Reservoir Computing
Authors: David Snyder, Alireza Goudarzi, Christof Teuscher
Date: 2012-12-08 00:00:00

This paper underscores the conjecture that intrinsic computation is maximal
in systems at the "edge of chaos." We study the relationship between dynamics
and computational capability in Random Boolean Networks (RBN) for Reservoir
Computing (RC). RC is a computational paradigm in which a trained readout layer
interprets the dynamics of an excitable component (called the reservoir) that
is perturbed by external input. The reservoir is often implemented as a
homogeneous recurrent neural network, but there has been little investigation
into the properties of reservoirs that are discrete and heterogeneous. Random
Boolean networks are generic and heterogeneous dynamical systems and here we
use them as the reservoir. An RBN is typically a closed system; to use it as a
reservoir we extend it with an input layer. As a consequence of perturbation,
the RBN does not necessarily fall into an attractor. Computational capability
in RC arises from a trade-off between separability and fading memory of inputs.
We find the balance of these properties predictive of classification power and
optimal at critical connectivity. These results are relevant to the
construction of devices which exploit the intrinsic dynamics of complex
heterogeneous systems, such as biomolecular substrates.
Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies
Authors: Boris Lesner, Bruno Scherrer
Date: 2013-04-20 00:00:00

We consider approximate dynamic programming for the infinite-horizon
stationary $\gamma$-discounted optimal control problem formalized by Markov
Decision Processes. While in the exact case it is known that there always
exists an optimal policy that is stationary, we show that when using value
function approximation, looking for a non-stationary policy may lead to a
better performance guarantee. We define a non-stationary variant of MPI that
unifies a broad family of approximate DP algorithms of the literature. For this
algorithm we provide an error propagation analysis in the form of a performance
bound of the resulting policies that can improve the usual performance bound by
a factor $O(1-\gamma)$, which is significant when the discount factor $\gamma$
is close to 1. Doing so, our approach unifies recent results for Value and
Policy Iteration. Furthermore, we show, by constructing a specific
deterministic MDP, that our performance guarantee is tight.
A Markov Model for Ontology Alignment
Authors: Michael E. Cotterell, Terrance Medina
Date: 2013-04-20 00:00:00
Tasks: Data Integration, model

The explosion of available data along with the need to integrate and utilize
that data has led to a pressing interest in data integration techniques. In
terms of Semantic Web technologies, Ontology Alignment is a key step in the
process of integrating heterogeneous knowledge bases. In this paper, we present
the Edge Confidence technique, a modification and improvement over the popular
Similarity Flooding technique for Ontology Alignment.
Automating the Dispute Resolution in Task Dependency Network
Authors: Ioan Alfred Letia, Adrian Groza
Date: 2013-04-19 00:00:00

When perturbation or unexpected events do occur, agents need protocols for
repairing or reforming the supply chain. Unfortunate contingency could increase
too much the cost of performance, while breaching the current contract may be
more efficient. In our framework the principles of contract law are applied to
set penalties: expectation damages, opportunity cost, reliance damages, and
party design remedies, and they are introduced in the task dependency model
Enacting Social Argumentative Machines in Semantic Wikipedia
Authors: Adrian Groza, Sergiu Indrie
Date: 2013-04-19 00:00:00

This research advocates the idea of combining argumentation theory with the
social web technology, aiming to enact large scale or mass argumentation. The
proposed framework allows mass-collaborative editing of structured arguments in
the style of semantic wikipedia. The long term goal is to apply the abstract
machinery of argumentation theory to more practical applications based on human
generated arguments, such as deliberative democracy, business negotiation, or
self-care. The ARGNET system was developed based on ther Semantic MediaWiki
framework and on the Argument Interchange Format (AIF) ontology.