Abstract
Signed network analysis has attracted increasing attention in
recent years. This is in part because research on signed network
analysis suggests that negative links have added value
in the analytical process. A major impediment in their effective
use is that most social media sites do not enable users
to specify them explicitly. In other words, a gap exists between
the importance of negative links and their availability
in real data sets. Therefore, it is natural to explore whether
one can predict negative links automatically from the commonly
available social network data. In this paper, we in-
vestigate the novel problem of negative link prediction with
only positive links and content-centric interactions in social
media. We make a number of important observations about
negative links, and propose a principled framework NeLP,
which can exploit positive links and content-centric interactions
to predict negative links. Our experimental results on
real-world social networks demonstrate that the proposed
NeLP framework can accurately predict negative links with
positive links and content-centric interactions. Our detailed
experiments also illustrate the relative importance of various
factors to the effectiveness of the proposed framework.
|
Abstract
Partially observable Markov decision processes
(POMDPs) provide a principled mathematical framework for
motion planning of autonomous robots in uncertain and dynamic
environments. They have been successfully applied to
various robotic tasks, but a major challenge is to scale up
POMDP algorithms for more complex robotic systems. Robotic
systems often have mixed observability: even when a robot’s
state is not fully observable, some components of the state
may still be fully observable. Exploiting this, we use a factored
model to represent separately the fully and partially observable
components of a robot’s state and derive a compact lowerdimensional
representation of its belief space. We then use this
factored representation in conjunction with a point-based algorithm
to compute approximate POMDP solutions. Separating
fully and partially observable state components using a factored
model opens up several opportunities to improve the efficiency
of point-based POMDP algorithms. Experiments show that on
standard test problems, our new algorithm is many times faster
than a leading point-based POMDP algorithm.
|