Rule learning with monotonicity constraints

ABSTRACT

In classification with monotonicity constraints, it is assumed that the class label should increase with increasing values on the attributes. In this paper we aim at formalizing the approach to learning with monotonicity constraints from statistical point of view. Motivated by the statistical analysis, we present an algorithm for learning rule ensembles. The algorithm first "monotonizes" the data using a nonparametric classification procedure and then generates a rule ensemble consistent with the training set. The procedure is justified by a theoretical analysis and verified in a computational experiment.

REFERENCES

• 1: Anglin, P., & Gencay, R. (1996). Semiparametric estimation of a hedonic price function. Journal of Applied Econometrics, 11, 633--648.
• 2: Asuncion, A., & Newman, D. (2007). UCI machine learning repository. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 3: Nicola Barile , Ad Feelders, Nonparametric Monotone Classification with MOCA, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.731-736, December 15-19, 2008 [doi>10.1109/ICDM.2008.54]
• 4: Arie Ben-David, Monotonicity Maintenance in Information-Theoretic Machine Learning Algorithms, Machine Learning, v.19 n.1, p.29-43, April 1995 [doi>10.1023/A:1022655006810]
• 5: A. Ben-David , L. Sterling , Y.-H. Pao, Learning and classification of monotonic ordinal concepts, Computational Intelligence, v.5 n.1, p.45-49, February 1989 [doi>10.1111/j.1467-8640.1989.tb00314.x]
• 6: Cao-Van, K., & De Baets, B. (2004). An instance-based algorithm for learning rankings. Proceedings of Benelearn (pp. 15--21).
• 7: R. Chandrasekaran , Young U. Ryu , Varghese S. Jacob , Sungchul Hong, Isotonic Separation, INFORMS Journal on Computing, v.17 n.4, p.462-474, October 2005 [doi>10.1287/ijoc.1030.0061]
• 8: Daniels, H., & Kamp, B. (1999). Applications of MLP networks to bond rating and house pricing. Neural Computation and Applications, 8, 226--234.
• 9: Dembczyński, K., Greco, S., Kotłowski, W., & Słłowiński, R. (2008). Ensemble of decision rules for ordinal classification with monotonicity constraints. LNAI, 5009, 260--267.
• 10: Ayhan Demiriz , Kristin P. Bennett , John Shawe-Taylor, Linear Programming Boosting via Column Generation, Machine Learning, v.46 n.1-3, p.225-254, 2002 [doi>10.1023/A:1012470815092]
• 11: Devroye, L., Györfi, L., & Lugosi, G. (1996). A probabilistic theory of pattern recognition. Springer.
• 12: Dykstra, R., Hewett, J., & Robertson, T. (1999). Non-parametric, isotonic discriminant procedures. Biometrica, 86, 429--438.
• 13: Eibe Frank , Mark Hall, A Simple Approach to Ordinal Classification, Proceedings of the 12th European Conference on Machine Learning, p.145-156, September 05-07, 2001
• 14: David Gamarnik, Efficient learning of monotone concepts via quadratic optimization, Proceedings of the eleventh annual conference on Computational learning theory, p.134-143, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279971]
• 15: Greco, S., Matarazzo, B., & Słłowiński, R. (2001). Rough sets theory for multicriteria decision analysis. European J. of Operational Research, 129, 1--47.
• 16: Greco, S., Matarazzo, B., & Słłowiński, R. (2007). Customer satisfaction analysis based on rough set approach. Zeitschrift für Betriebswirtschaft, 16, 325--339.
• 17: Herbrich, R., Graepel, T., & Obermayer, K. (1999). Regression models for ordinal data: A machine learning approach (Technical Report). Technical University of Berlin.
• 18: Koltchinskii, V., & Panchenko, D. (2002). Empirical margin distributions and bounding the generalization error of combined classifiers. Annals of Statistics, 30, 1--50.
• 19: Wojciech Kotłowski , Krzysztof Dembczyński , Salvatore Greco , Roman Słowiński, Stochastic dominance-based rough set model for ordinal classification, Information Sciences: an International Journal, v.178 n.21, p.4019-4037, November, 2008 [doi>10.1016/j.ins.2008.06.013]
• 20: Kotłowski, W., & Słłowiński, R. (2008). Statistical approach to ordinal classification with monotonicity constraints. Preference Learning ECML/PKDD 2008 Workshop.
• 21: Lin, H.-T., & Li, L. (2007). Ordinal regression by extended binary classifications. Advances in Neural Information Processing Systems, 19, 865--872.
• 22: Claude Nadeau , Yoshua Bengio, Inference for the Generalization Error, Machine Learning, v.52 n.3, p.239-281, September 2003 [doi>10.1023/A:1024068626366]
• 23: R. Potharst , A. J. Feelders, Classification trees for problems with monotonicity constraints, ACM SIGKDD Explorations Newsletter, v.4 n.1, June 2002 [doi>10.1145/568574.568577]
• 24: Schapire, R. E., Freund, Y., Bartlett, P., & Lee, W. S. (1998). Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 26, 1651--1686.
• 25: Joseph Sill, Monotonic networks, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.661-667, July 1998, Denver, Colorado, United States
• 26: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization
  G.3 PROBABILITY AND STATISTICS
      Subjects: Nonparametric statistics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Deduction (e.g., natural, rule-based)
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory