log in  |  register  |  feedback?  |  help  |  web accessibility
Reasoning about Incomplete and Uncertain Preferences with Order-based Markov Models
Wednesday, January 24, 2018, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Reasoning about an entity's preferences (be it a user of an application, an individual targeted for marketing, or a group of people whose choices are of interest) has a long history in different areas of study. In this talk, we adopt the point of view that grows out of the intersection of databases and knowledge representation, where preferences are usually represented as strict partial orders over the set of tuples in a database or the consequences of a knowledge base. We introduce order-based Markov models (OMMs), which flexibly combine such preferences with probabilistic uncertainty. Their applications are clear in domains such as the Social Semantic Web, where users often express preferences in an incomplete manner and through different means, often in contradiction with each other. We show that the basic problems associated with reasoning with OMMs (computing the probability of a possible world or a given query) are #P-complete, and then explore ways to make these computations tractable by: (i) leveraging results from Order Theory to obtain a fully polynomial-time randomized approximation scheme (FPRAS); (ii) studying a fragment of the language of OMMs for which exact computations can be performed in fixed-parameter polynomial time; and (iii) variable elimination methods for other fragments, along with an empirical evaluation of their tractability.
The work presented in this talk has been carried out in conjunction with Maria Vanina Martinez (UNS Bahia Blanca and CONICET, Argentina), Thomas Lukasiewicz (University of Oxford, UK), and David Poole (University of British Columbia, Canada).

Gerardo Simari is an assistant professor at Universidad Nacional del Sur in Bahía Blanca, and an adjunct researcher at CONICET, Argentina. His research focuses on topics within AI and Databases, and reasoning under uncertainty. He received a PhD in computer science from University of Maryland College Park in 2010; after obtaining his doctoral degree, he obtained a postdoctoral researcher position in the Department of Computer Science, University of Oxford (UK), and one year later secured a position as Senior Researcher in the same department. Simari was recently selected as one of IEEE Intelligent Systems "AI's Ten to Watch" for 2016, was awarded the Best Paper prize at the 9th International Web Rule Symposium (RuleML 2015), and the Best Student Paper prize at the 2009 International Conference on Logic Programming (ICLP), and also received an honorable mention for the International Journal of Approximate Reasoning's Young Researcher Award 2011 for ongoing research in Probabilistic Logic. He currently serves on the editorial board of Journal of Artificial Intelligence Research (JAIR), and is a former Fulford Junior Research Fellow of Somerville College, University of Oxford.

This talk is organized by John P Dickerson