Pointers to work on ApproximateReasoning here.
A useful early paper outlining the basic concepts of anytime algorithms
- Using Anytime Algorithms in Intelligent Systems Shlomo Zilberstein, AI Magazine 1996
A recent event where object/meta-reasoning was brought back to the
- attention of the AI community (after absence of many years): AAAI Workshop on Metareasoning: Thinking about Thinking
From this event, Zilberstein's paper on meta-reasoning is very relevant:
- "Metareasoning and Bounded Rationality",
A paper defining a semantic distance measure between interpretations.
- This paper is about ontology revision, in itself an interesting topic, but my main interest is in def's 1 and 2 of the paper. There the authors define a distance measure between interpretations (roughly: the size of the symmetric difference between the interpretations, still quite straightforward), but (more interestingly), they then define a distance measure between an interpretation and an ontology, namely: the distance of an interpretation to an ontology is the minimal distance from that interpretation to a ontology-satisfying interpretation. This is an interesting general device to measure how "close" an intepretation is to being a satisfying interpretation (instead of just a binary divide between satisfying and non-satisfying interpretations). I would think that this is quite a general device, and might be useful for other work, such as approximate reasoning strategies. (and I hadn't seen it defined before).
This is an as yet unpublished draft, I cannot expose it on the Wiki.
- This paper is about ontology revision, in itself an interesting topic, but my main interest is in def's 1 and 2 of the paper. There the authors define a distance measure between interpretations (roughly: the size of the symmetric difference between the interpretations, still quite straightforward), but (more interestingly), they then define a distance measure between an interpretation and an ontology, namely: the distance of an interpretation to an ontology is the minimal distance from that interpretation to a ontology-satisfying interpretation. This is an interesting general device to measure how "close" an intepretation is to being a satisfying interpretation (instead of just a binary divide between satisfying and non-satisfying interpretations). I would think that this is quite a general device, and might be useful for other work, such as approximate reasoning strategies. (and I hadn't seen it defined before).
- The PAC (probably approximately correct) framework has been a very useful
framework for Machine Learning. Here's a good intro/overview paper: PAC learning.pdf
Could one develop a framework for PAC Reasoning? - An entire special issue on how the Database community tries to deal with
probabilistic data:
- either the data is uncertain, or
- returning probablistic answers to queries (based on probability distributions of the data) the probability
- probabilistic relations models
and closely related: a paper about probabilistic RDF probabilistic-RDF.pdf
using SAT-solving for RDF querying (by translation RDF to prop. logic). RetrievingMatchingRDFGraphsSolvingSATProblem.pdf.
By itself this paper is not so relevant to LarKC, but at the VU we are using this as the basis for approx. reasoning by using approx. SAT-solving instead.One would expect the notion of similarity to play an important part in approximate reasoning. Here's a paper looking what has been done and what still must be done on the topic of concept-similarity in DL's. (by Borgida, so it must be good) similarity in DL.pdf
Activation Spreading over RDF graphs is one of the ideas to be explored for selecting appropriate subgraphs.
Here is the original presentation at the kick-off meeting
and a paper of people who have the same idea: spreading-semantics-Scheir.pdfA short but very good paper on statistical reasoning for the Semantic Web. The following could have come straight out of the LarKC proposal! : "we argue that statistical reasoning ('reasoning with uncertainty') need not be a substitute for traditional Description Logic (DL) / First-Order Logic (FOL) reasoning, instead statistical methods can serve as a complement to logicbased reasoning systems in two ways: (i) Offer a meta-reasoning (or audit) mechanism to validate logical reasoning, and (ii) Act as a “filler” where Ontological information either does not exist, or is insufficient to reason conclusively.". statistical-reasoning-MIT.pdf