Wolfgang Pauli Institute (WPI) Vienna

Home WPI in a nutshell Practical Information Events People WPI Projects
Login Thematic Programs Pauli Fellows Talks Research Groups

Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Organizers: Thomas Eiter TU Wien), Monika Henzinger (WPI, U. Wien), Georg Gottlob (WPI, TU Wien & U. Oxford), Helmut Veith (TU Wien), PF Antoniou Grigoris (Univ. Greece)

Talks


Chakraborty Sourav Vienna University of Technology, 1040 Vienna, Gußhausstr. 25-29, "Kontaktraum", 6th floor Mon, 1. Jan 01, 0:00
"Property Testing: Sublinear Algorithms for Promise Problems"
Deciding weather a graph is $k$-colorable is an NP-complete problem and hence solving this problem is expected to be hard. But if we are given a promise that the graph is either $k$-colorable of "far from being $k$-coloarble", can we make some intelligent deductions "quickly"? Property testing deals with these kind of questions, where the goal is to solve some promise problems. The efficiency of an algorihtm is measured by the number of input bits that are read. In many cases there are algorithms that can correctly answer with high probability by looking at a tiny fraction (sometimes even constant) of the input bits. In the past two decades this area has been at the forefront of research in theoretical computer science - we will take at look at it.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Antoniou Grigoris/Bikakis Antonis Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom von Neumann, ground floor, access through the courtyard Tue, 12. Apr 11, 17:00
Distributed Reasoning about Context
Interest in formalizations of contextual information and inter-contextual information flow has steadily increased over the past few years. Intuitively, a multi-context system describes the information available in a number of contexts (such as people, agents, databases, modules) and specifies the information flow between those contexts through mapping rules associating concepts used by different contexts. The imperfect nature of context in key application areas, such as ambient intelligence, mobile and social computing, and the special characteristics of the entities that possess and share the available context information in such systems, render contextual reasoning a very challenging task. In the main part of this talk, we propose a solution by extending multi-context systems with simple rule-ased non-monotonic feature: local defeasible theories, defeasible mappings, and a preference relation on the system contexts. We present this novel representation model, describe an algorithm for distributed query evaluation, give a number of formal properties, and present an argumentation semantics. We also describe specific application scenarios in ambient intelligence and social computing and outline their implementation and evaluation.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Verheij Bart Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard Tue, 31. May 11, 14:00
The logic of argumentation: what next?
Argumentation is a process in which arguments and counterarguments are put forward, thereby supporting and attacking positions on the basis of premises. In recent years, the study of the logic of argumentation has flourished, resulting in good understanding of the formal and computational properties of the proposed logical models. Moreover, the logic of argumentation has found applications in medicine, law, critical thinking, software design and artificial intelligence. In this talk, I will give a personal perspective of the developments in the interdisciplinary study of argumentation, and explain what I believe to be important next steps.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Koivisto Mikko Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard Tue, 14. Jun 11, 14:00
Exponential-time algorithms for Bayesian networks
Bayesian networks, also called belief networks, is an extensively studied formalism for representing multivariate probability distributions. A Bayesian network consists of a directed acyclic graph, DAG for short, and local functions that specify the probability distribution of a variable given its parent variables in the DAG. Besides statistical dependencies, Bayesian networks are often used for representing causal relationships among a set of variables. I will talk about two hard computational problems associated with Bayesian networks: inference and structure learning. The inference problem is that of computing a marginal distribution by summing over most of the variables in a given Bayesian network; the fastest known exact algorithms run in time exponential in the treewidth of the underlying graph. In the structure learning problem the task is to find a DAG that maximizes the fit to a given set of data records on the variables, formalized by a decomposable objective function; the acyclicity constraint renders the learning problem NP_hard. The fastest known algorithms resemble the dynamic programming treatment of the traveling salesman problem.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Liedloff Mathieu Vienna University of Technology, Institute for Information Systems, Favoritenstrasse 9, Seminarroom Goedel, ground floor, access through the courtyard Tue, 14. Jun 11, 15:00
A Fast Exact Algorithm for L(2,1)-Labeling of Graphs
In this talk I will present an exponential time algorithm to solve the L(2,1)-labeling problem in graphs. Given a graph, an L(2,1)-labeling is a mapping from its vertex set into the nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices at distance 2 are different. The aim is to minimize the span of the labeling, i.e. the maximum label used by the labeling.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Gatterbauer Wolfgang TU Wien, Institut für Informationssysteme, Meetingroom Menger, Favoritenstraße 9-11, Stg. 3. 3. Stock, 1040 Wien Fri, 9. Mar 12, 14:30
Rules of Thumb for Information Acquisition Rules of Thumb for Information Acquisition from Large and Redundant Data
We develop an abstract model of information acquisition from redundant data. We assume a random sampling process from data which contain information with bias and are interested in the fraction of information we expect to learn as function of (i) the sampled fraction (recall) and (ii) varying bias of information (redundancy distributions). We develop two rules of thumb with varying robustness. We first show that, when information bias follows a Zipf distribution, the 80-20 rule or Pareto principle does surprisingly not hold, and we rather expect to learn less than 40% of the information when randomly sampling 20% of the overall data. We then analytically prove that for large data sets, randomized sampling from power-law distributions leads to “truncated distributions” with the same power-law exponent. This second rule is very robust and also holds for distributions that deviate substantially from a strict power law. We further give one particular family of powerlaw functions that remain completely invariant under sampling. Finally, we validate our model with two large Web data sets: link distributions to web domains and tag distributions on delicious.com.
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

James Delgrande Seminarroom Gödel (Favoritenstrasse 9-11, ground floor, access through courtyard Mon, 5. Nov 12, 16:00
Revising Horn Theories
This talk addresses belief revision where the underlying logic is that governing Horn clauses. It proves to be the case that classical (AGM) belief revision doesn't immediately generalise to the Horn case. In particular, a standard construction based on a total preorder over possible worlds may violate the accepted (AGM) postulates. Conversely, Horn revision functions in the obvious extension to the AGM approach are not captured by total preorders over possible worlds. We address these difficulties by first restricting the semantic construction to ``well behaved'' orderings; and second, by augmenting the revision postulates by an additional postulate. This additional postulate is redundant in the AGM approach but not in the Horn case. In a representation result we show that these two approaches coincide. Arguably this work is interesting for several reasons. It extends AGM revision to inferentially-weaker Horn theories; hence it sheds light on the theoretical underpinnings of belief change, as well as generalising the AGM paradigm. Thus, this work is relevant to revision in areas that employ Horn clauses, such as deductive databases and logic programming, as well as areas in which inference is weaker than classical logic, such as in description logic.
  • Thematic program: Databases and Ontologies in Advanced Information Systems (2010, Prolongation from 2009)
  • Thematic program: Logic based reasoning and data mining on the web (2011, Prolongation from 2010)

Impressum webmaster [Printable version]