Monotone Classification by Function Decomposition

  • Viara Popova
  • Jan C. Bioch
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3735)


The paper focuses on the problem of classification by function decomposition within the frame of monotone classification. We propose a decomposition method for discrete functions which can be applied to monotone problems in order to generate a monotone classifier based on the extracted concept hierarchy. We formulate and prove a criterion for the existence of a positive extension of the scheme f=g(S 0,h(S 1)) in the context of discrete functions. We also propose a method for finding an assignment for the intermediate concept with a minimal number of values.


Boolean Function Discrete Function Decomposition Tree Default Rule Constraint Graph 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bioch, J.C., Popova, V.: Monotone Decision Trees and Noisy Data. In: Blockeel, H., Denecker, M. (eds.) Proceedings of the 14th Belgium-Dutch Conference on Artificial Intelligence (BNAIC 2002), Leuven, pp. 19–26 (2002)Google Scholar
  2. 2.
    Bioch, J.C., Potharst, R.: Decision Trees for Monotone Classification. In: van Marcke, K., Daelmans, W. (eds.) Proceedings of the Dutch Artificial Conference on Artificial Intelligence (NAIC 1997), pp. 361–369 (1997)Google Scholar
  3. 3.
    Blake, C.L., Mertz, C.J.: UCI Repository of machine learning databases. University of California. Department of Information and Computer Science, Irvine (1998),
  4. 4.
    Bohanec, M., Rajkovič, V.: DEX: An expert system shell for decision support. Sistemica 1, 145–157 (1990)Google Scholar
  5. 5.
    Boros, E., Gurvich, V., Hammer, P.L., Ibaraki, T., Kogan, A.: Decomposability of partially defined Boolean functions. Discrete Applied Mathematics 62, 51–75 (1995)CrossRefMathSciNetzbMATHGoogle Scholar
  6. 6.
    Popova, V.: Knowledge Discovery and Monotonicity, PhD Thesis, Erasmus University Rotterdam, The Netherlands (2004)Google Scholar
  7. 7.
    Potharst, R., Bioch, J.C.: Decision Trees for Ordinal Classification. Intelligent Data Analysis 4, 1–15 (2000)Google Scholar
  8. 8.
    Samuel, A.L.: Some studies in machine learning using the game of checkers. IBM Journal of Research and Development 3, 221–229 (1959)CrossRefGoogle Scholar
  9. 9.
    Shapiro, A.D.: Structured induction in expert systems. Turing Institute Press in association with Addison-Wesley, Wokingham, UK (1987)Google Scholar
  10. 10.
    Zupan, B.: Machine learning by function decomposition. PhD Thesis, University of Ljubljana (1997)Google Scholar
  11. 11.
    Zupan, B., Bohanec, M., Demsar, J., Bratko, I.: Learning by Discovering Concept Hierarchies. Artificial Intelligence 109, 211–242 (1999)CrossRefMathSciNetzbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Viara Popova
    • 1
  • Jan C. Bioch
    • 2
  1. 1.Department of Artificial IntelligenceVrije UniversiteitAmsterdamThe Netherlands
  2. 2.Econometric InstituteErasmus University RotterdamRotterdamThe Netherlands

Personalised recommendations