Approximate Inferencing Task
An Approximate Inferencing Task is a reasoning task/inferencing task that is a Approximation Task.
- Context:
- output: Approximate Inference.
- It can be solved by a Approximate Inference System (that implements an approximate inference algorithm).
- …
- Counter-Example(s):
- See: Bayesian Reasoning, Bayesian Inference, Inference Argument, Non-Monotonic Reasoning, Reasoning Under Uncertainty.
References
2008
- (Rudolph et al., 2008) ⇒ Sebastian Rudolph, Tuvshintur Tserendorj, and Pascal Hitzler. 2008). “What Is Approximate Reasoning?.” In: The Second International Conference on Web Reasoning and Rule System (RR 2008).
- Approximate reasoning for the Semantic Web is based on the idea of sacrificing soundness or completeness for a significant speedup of reasoning. This is to be done in such a way that the number of introduced mistakes is at least outweighed by the obtained speed-up. When pursuing such approximate reasoning approaches, however, it is important to be critical not only about appropriate application domains, but also about the quality of the resulting approximate reasoning procedures. With different approximate reasoning algorithms discussed and developed in the literature, it needs to be clarified how these approaches can be compared, i.e. what it means that one approximate reasoning approach is better than some other. In this paper, we will formally define such a foundation for approximate reasoning research. We will clarify – by means of notions from statistics – how different approximate algorithms can be compared, and ground the most fundamental notions in the field formally.We will also exemplify what a corresponding statistical comparison of algorithms would look like.
2006
- (Bishop, 2006) ⇒ Christopher M. Bishop. (2006). “Pattern Recognition and Machine Learning. Springer, Information Science and Statistics.
2001
- Giangiacomo Gerla. (2001). “FUZZY LOGIC: Mathematical Tools for Approximate Reasoning.” Springer. ISBN:079236941
- Book overview: The theme of this book is fuzzy logic in a narrow sense, a promising new chapter of fuzzy logic. The basic ideas of formal logic were formulated by Lotfi Zadeh in 1975. The aim of this logic is to investigate the wonderful human capacity of reasoning with vague notions by attempting to formalize the `approximate reasoning' we use in everyday life. A peculiarity of this book is to propose a general framework based on three mathematical tools: the theory of fuzzy closure operators, an extension principle for crisp logics and the theory of recursively enumerable fuzzy subsets. This book is unique in that it treats fuzzy logics which are not truth-functional in nature (as an example, the logic of the necessities, probabilistic logics and similarity-based logics).
- Google keywords: fuzzy logic, ultraproducts, inference rule, complete lattice, algebraic closure, triangular norm, tautology, order-preserving, propositional calculus, logical axioms, Boolean algebra, fuzzy subalgebra, order-reversing, interior operator, Galois connection, characteristic function, greatest element, one-one reducible, maximal element, fuzzy system
1996
- (Roth, 1996) ⇒ Dan Roth. (1996). “On the Hardness of Approximate Reasoning.” In: Artificial Intelligence, 82(1-2). doi:10.1016/0004-3702(94)00092-1
- QUOTE: Many AI problems, when formalized, reduce to evaluating the probability that a propositional expression is true. In this paper we show that this problem is computationally intractable even in surprisingly restricted cases and even if we settle for an approximation to this probability.
We consider various methods used in approximate reasoning such as computing degree of belief and Bayesian belief networks, as well as reasoning techniques such as constraint satisfaction and knowledge compilation, that use approximation to avoid computational difficulties, and reduce them to model-counting problems over a propositional domain.
We prove that counting satisfying assignments of propositional languages is intractable even for Horn and monotone formulae, and even when the size of clauses and number of occurrences of the variables are extremely limited. This should be contrasted with the case of deductive reasoning, where Horn theories and theories with binary clauses are distinguished by the existence of linear time satisfiability algorithms. What is even more surprising is that, as we show, even approximating the number of satisfying assignments (i.e., “approximating” approximate reasoning), is intractable for most of these restricted theories.
We also identify some restricted classes of propositional formulae for which efficient algorithms for counting satisfying assignments can be given.
- QUOTE: Many AI problems, when formalized, reduce to evaluating the probability that a propositional expression is true. In this paper we show that this problem is computationally intractable even in surprisingly restricted cases and even if we settle for an approximation to this probability.