Many AI inference problems arising in a wide variety of fields such as machine learning, semantic web, network communication, computer vision, and robotics can be solved using message-passing algorithms that operate on factor graphs. Often, however, we are facing inference problems with symmetries not reflected in the graph structure and, hence, not exploitable by efficient message-passing algorithms. Recently, several lifting approaches have been proposed that exploit such additional symmetries. Starting from a given factor graph, they essentially first construct a lifted factor graph of supernodes and superfactors, corresponding to sets of nodes and factors that send and receive the same messages, i.e., that are indistinguishable given the evidence. Then, they run a modified message-passing algorithm on the often smaller lifted factor gaph. In this talk, I will demonstrate that another important AI technique is lifteable too: linear programs (LPs). Intuitively, we employ a lifted variant of Gaussian belief propagation (GaBP) to solve the systems of linear equations arising when running an interior-point solver based on a Newton method. Then, we show that running lifted GaBP is not required at all. Instead we can read off a lifted but equivalent LP from it that can be solved using any off-the-shelf LP solver. This contribution significantly pushes the boundaries of lifted inference as it directly paves the way to novel sometimes even first lifted approaches for MAP inference, solving MDPs, and flow problems, among others.

This talk is based on joint works with Babak Ahmadi, Yussef El Massaoudi, Fabian Hadiji, Michael Haimes, Leslie Kaelbling, Brian Milch, Martin Mladenov, Sriraam Natarajan, Scott Sanner, and Luke Zettlemoyer.

Kristian Kersting is the head of the "statisitcal relational activity mining" (STREAM) group at Fraunhofer IAIS, Bonn, Germany, and a research fellow of the University of Bonn, Germany. He received his Ph.D. from the University of Freiburg, Germany, in 2006. After a PostDoc at the MIT, USA, he joined Fraunhofer IAIS in 2008 to build up the STREAM research group using an ATTRACT Fellowship. His main research interests are statistical relational artificial intelligence, machine learning, and data mining. He has published over 70 peer-reviewed papers, has received the ECML Best Student Paper Award in 2006 and the ECCAI Dissertation Award 2006 for the best European dissertation in the field of AI, and is an ERCIM Cor Baayen Award 2009 finalist for the "Most Promising Young Researcher In Europe in Computer Science and Applied Mathematics". He gave several tutorials at top conferences (AAAI, ECML-PKDD, ICAPS, ICML, IJCAI, ...) and (will) co-chair(ed) MLG-07, SRL-09, MLG-11, CoLISD-11, STAIRS-12, and the first workshop on Statistical Relational AI (StarAI-10). In 2013, he will co-chair the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). He (will) serve(d) as area chair for ECML (06,07), ICML (10,11,12) as Senior PC member at IJCAI-11 and AAAI-12, and on the PCs of several top conference (AAAI, ECAI, ECML PKDD, ICAPS, ICML, IJCAI, KDD, RSS, PODS, ...). He was a guest co-editor for special issues of the Annals of Mathematics and AI (AMAI), the Journal of Machine Learning Research (JMLR), and the Machine Learning Journal (MLJ). Currently, he serves as an action editor for MLJ and the Data Mining and Knowledge Discovery (DAMI) Journal as well as an associate editor for the Journal of Artifical Intelligence Research (JAIR).

The position paper provides a brief summary of log-linear description logics and their applications. We compile a list of ve requirements that we believe a probabilistic description logic should have to be useful in practice. We demonstrate the ways in which log-linear description logics answer to these requirements.

This position paper proposes an interactive approach for developing information extractors based on the ontology definition process with knowledge about possible (in)correctness of annotations. We discuss the problem of managing and manipulating probabilistic dependencies.

Predicting potential links between nodes in a network is a problem of great practical interest. Link prediction is mostly based on graph-based features and, recently, on approaches that consider the semantics of the domain. However, there is uncertainty in these predictions; by modeling it, one can improve prediction results. In this paper, we propose an algorithm for link prediction that uses a probabilistic ontology described through the probabilistic description logic crALC. We use an academic domain in order to evaluate this proposal.

We present DISPONTE, a semantics for probabilistic ontologies that is based on the distribution semantics for probabilistic logic programs. In DISPONTE each axiom of a probabilistic ontology is annotated with a probability. The probabilistic theory denes thus a distribution over normal theories (called worlds) obtained by including an axiom in a world with a probability given by the annotation. The probability of a query is computed from this distribution with marginalization. We also present the system BUNDLE for reasoning over probabilistic OWL DL ontologies according to the DISPONTE semantics. BUNDLE is based on Pellet and uses its capability of returning explanations for a query. The explanations are encoded in a Binary Decision Diagram from which the probability of the query is computed.

This paper deals with the problem of building a common knowledge body for a set of domain ontologies in order to enable their sharing and integration in a collaborative framework. We propose a novel hierarchical algorithm for concept fuzzy set representation mediated by a reference ontology. In contrast to the original concept representations based on instances, this enables the application of methods of fuzzy logical reasoning in order to characterize and measure the degree of the relationships holding between concepts from dierent ontologies. We present an application of the approach in the multimedia domain.

We consider the fuzzy logic ALCI with semantics based on a finite residuated lattice. We show that the problems of satisability and subsumption of concepts in this logic are ExpTime-complete w.r.t. general TBoxes and PSpace-complete w.r.t. acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp ALCI.

Standard semantic technologies propose powerful means for knowledge representation as well as enhanced reasoning capabilities to modern applications. However, the question of dealing with uncertainty, which is ubiquitous and inherent to real world domain, is still considered as a major deficiency. We need to adapt those technologies to the context of uncertain representation of the world. Here, this issue is examined through the evidential theory, in order to model and reason about uncertainty in the assertional knowledge of the ontology. The evidential theory, also known as the DempsterShafer theory, is an extension of probabilities and proposes to assign masses on specific sets of hypotheses. Further on, thanks to the semantics (hierarchical structure, constraint axioms and properties defined in the ontology) associated to hypotheses, a consistent frame of this theory is automatically created to apply the classical combinations of information and decision process offered by this mathematical theory.

Web data often manifest high levels of uncertainty. We focus on categorical Web data and we represent these uncertainty levels as first or second order uncertainty. By means of concrete examples, we show how to quantify and handle these uncertainties using the BetaBinomial and the Dirichlet-Multinomial models, as well as how take into account possibly unseen categories in our samples by using the Dirichlet Process.

Knowledge available through Semantic Web standards can easily be missing, generally because of the adoption of the Open World Assumption (i.e. the truth value of an assertion is not necessarily known). However, the rich relational structure that characterizes ontologies can be exploited for handling such missing knowledge in an explicit way. We present a Statistical Relational Learning system designed for learning terminological na¨ıve Bayesian classifiers, which estimate the probability that a generic individual belongs to the target concept given its membership to a set of Description Logic concepts. During the learning process, we consistently handle the lack of knowledge that may be introduced by the adoption of the Open World Assumption, depending on the varying nature of the missing knowledge itself.

In this paper we outline a shared knowledge representation based on RDF. It can be used in a distributed multi-tenant environment to store design knowledge. These RDF-graphs incorporate all necessary information to instantiate Bayesian network representations of certain problem solving cases, which are used to support the conceptual design tasks carried out by a salesperson during lead qualication.

To be defined.