×

Qualitative knowledge discovery. (English) Zbl 1165.68415

Schewe, Klaus-Dieter (ed.) et al., Semantics in data and knowledge bases. Third international workshop, SDKB 2008, Nantes, France, March 29, 2008. Revised selected papers. Berlin: Springer (ISBN 978-3-540-88593-1/pbk). Lecture Notes in Computer Science 4925, 77-102 (2008).
Summary: Knowledge discovery and data mining deal with the task of finding useful information and especially rules in unstructured data. Most knowledge discovery approaches associate conditional probabilities to discovered rules in order to specify their strength. In this paper, we propose a qualitative approach to knowledge discovery. We do so by abstracting from actual probabilities to qualitative information and in particular, by developing a method for the computation of an ordinal conditional function from a possibly noisy probability distribution. The link between structural and numerical knowledge is established by a powerful algebraic theory of conditionals. By applying this theory, we develop an algorithm that computes sets of default rules from the qualitative abstraction of the input distribution. In particular, we show how sparse information can be dealt with appropriately in our framework. By making use of the duality between inductive reasoning and knowledge discovery within the algebraic theory of conditionals, we can ensure that the discovered rules can be considered as being most informative in a strict, formal sense.
For the entire collection see [Zbl 1154.68026].

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

TETRAD
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artificial Intelligence (1996) · doi:10.1016/0004-3702(95)00090-9
[2] Benferhat, S., Dubois, D., Prade, H.: Nonmonotonic reasoning, conditional objects and possibility theory. Artificial Intelligence (92), 259–276 (1997) · Zbl 1017.68539
[3] Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence 44, 167–207 (1990) · Zbl 0782.03012 · doi:10.1016/0004-3702(90)90101-5
[4] Kern-Isberner, G.: Solving the inverse representation problem. In: Proceedings 14th European Conference on Artificial Intelligence, ECAI 2000, Berlin, pp. 581–585. IOS Press, Amsterdam (2000)
[5] Kern-Isberner, G., Fisseler, J.: Knowledge discovery by reversing inductive knowledge representation. In: Proceedings of the Ninth International Conference on the Principles of Knowledge Representation and Reasoning, KR 2004, pp. 34–44. AAAI Press, Menlo Park (2004)
[6] Adams, E.: Probability and the logic of conditionals. In: Hintikka, J., Suppes, P. (eds.) Aspects of inductive logic, pp. 265–316. North-Holland, Amsterdam (1966) · doi:10.1016/S0049-237X(08)71673-2
[7] Spohn, W.: Ordinal conditional functions: a dynamic theory of epistemic states. In: Harper, W., Skyrms, B. (eds.) Causation in Decision, Belief Change, and Statistics, vol. 2, pp. 105–134. Kluwer Academic Publishers, Dordrecht (1988) · doi:10.1007/978-94-009-2865-7_6
[8] Benferhat, S., Dubois, D., Lagrue, S., Prade, H.: A big-stepped probability approach for discovering default rules. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems (IJUFKS) 11, 1–14 (2003) · Zbl 1072.68616 · doi:10.1142/S0218488503002235
[9] Paris, J.: The uncertain reasoner’s companion – A mathematical perspective. Cambridge University Press, Cambridge (1994) · Zbl 0838.68104
[10] Kern-Isberner, G.: Characterizing the principle of minimum cross-entropy within a conditional-logical framework. Artificial Intelligence 98, 169–208 (1998) · Zbl 0903.68181 · doi:10.1016/S0004-3702(97)00068-4
[11] Kern-Isberner, G.: Conditionals in Nonmonotonic Reasoning and Belief Revision. LNCS (LNAI), vol. 2087. Springer, Heidelberg (2001) · Zbl 0978.03014 · doi:10.1007/3-540-44600-1
[12] Jain, A., Murty, M., Flynn, P.: Data clustering: A review. ACM Computing Surveys 31(3) (1999) · doi:10.1145/331499.331504
[13] Cooper, G., Herskovits, E.: A bayesian method for the induction of probabilistic networks from data. Machine Learning 9, 309–347 (1992) · Zbl 0766.68109
[14] Spirtes, P., Glymour, C., Scheines, R.: Causation, Prediction and Search. Lecture Notes in Statistics, vol. 81. Springer, Heidelberg (1993) · Zbl 0806.62001 · doi:10.1007/978-1-4612-2748-9
[15] Heckerman, D.: Bayesian networks for knowledge discovery. In: Fayyad, U., Piatsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in knowledge discovery and data mining. MIT Press, Cambridge (1996)
[16] Buntine, W.: A guide to the literature on learning probabilistic networks from data. IEEE Transactions on Knowledge and Data Engineering 8(2), 195–210 (1996) · Zbl 05109019 · doi:10.1109/69.494161
[17] Herskovits, E., Cooper, G.: Kutató: An entropy-driven system for construction of probabilistic expert systems from databases. Technical Report KSL-90-22, Knowledge Systems Laboratory (1990)
[18] Geiger, D.: An entropy-based learning algorithm of bayesian conditional trees. In: Proceedings of the Eighth Conference on Uncertainty in Artificial Intelligence, pp. 92–97 (1992) · doi:10.1016/B978-1-4832-8287-9.50017-7
[19] Kern-Isberner, G.: Following conditional structures of knowledge. In: Burgard, W., Christaller, T., Cremers, A.B. (eds.) KI 1999. LNCS (LNAI), vol. 1701, pp. 125–136. Springer, Heidelberg (1999) · Zbl 0961.03018 · doi:10.1007/3-540-48238-5_10
[20] Kern-Isberner, G.: Handling conditionals adequately in uncertain reasoning. In: Benferhat, S., Besnard, P. (eds.) ECSQARU 2001. LNCS (LNAI), vol. 2143, pp. 604–615. Springer, Heidelberg (2001) · Zbl 1001.68144 · doi:10.1007/3-540-44652-4_53
[21] DeFinetti, B.: Theory of Probability, vol. 1,2. John Wiley and Sons, New York (1974)
[22] Calabrese, P.: Deduction and inference using conditional logic and probability. In: Goodman, I., Gupta, M., Nguyen, H., Rogers, G. (eds.) Conditional Logic in Expert Systems, pp. 71–100. Elsevier, North Holland (1991)
[23] Kern-Isberner, G.: A thorough axiomatization of a principle of conditional preservation in belief revision. Annals of Mathematics and Artificial Intelligence 40(1-2), 127–164 (2004) · Zbl 1067.68141 · doi:10.1023/A:1026110129951
[24] Beierle, C., Kern-Isberner, G.: Modelling conditional knowledge discovery and belief revision by abstract state machines. In: Börger, E., Gargantini, A., Riccobene, E. (eds.) ASM 2003. LNCS, vol. 2589, pp. 186–203. Springer, Heidelberg (2003) · Zbl 1021.68529 · doi:10.1007/3-540-36498-6_10
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.