Cost-sensitive learning with conditional Markov networks

ABSTRACT

There has been a recent, growing interest in classification and link prediction in structured domains. Methods such as CRFs (Lafferty et al., 2001) and RMNs (Taskar et al., 2002) support flexible mechanisms for modeling correlations due to the link structure. In addition, in many structured domains, there is an interesting structure in the risk or cost function associated with different misclassifications. There is a rich tradition of cost-sensitive learning applied to unstructured (IID) data. Here we propose a general framework which can capture correlations in the link structure and handle structured cost functions. We present a novel cost-sensitive structured classifier based on Maximum Entropy principles that directly determines the cost-sensitive classification. We contrast this with an approach which employs a standard 0/1 loss structured classifier followed by minimization of the expected cost of misclassification. We demonstrate the utility of our proposed classifier with experiments on both synthetic and real-world data.

REFERENCES

• 1: Bodik, P., Hong, W., Guestrin, C., Madden, S., Paskin, M., & Thibaux, R. (2004). Intel lab dataset. http://berkeley.intel-research.net/labdata/.
• 2: Béla Bollobás , Christian Borgs , Jennifer Chayes , Oliver Riordan, Directed scale-free graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: Brefeld, U., Geibel, P., & Wysotzki, F. (2003). Support vector machines with example dependent costs. Proceedings of the European Conference on Machine Learning.
• 4: Amol Deshpande , Carlos Guestrin , Wei Hong , Samuel Madden, Exploiting Correlated Attributes in Acquisitional Query Processing, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.143-154, April 05-08, 2005 [doi>10.1109/ICDE.2005.63]
• 5: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 6: Elkan, C. (2001). The foundations of cost-sensitive learning. Proceedings of the International Conference on Artificial Intelligence.
• 7: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 8: Vipul Singhvi , Andreas Krause , Carlos Guestrin , James H. Garrett, Jr. , H. Scott Matthews, Intelligent light control using sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098942]
• 9: Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence.
• 10: Taskar, B., Guestrin, C., & Koller, D. (2003). Max-margin markov networks. Advances in Neural Information Processing Systems.
• 11: Ioannis Tsochantaridis , Thomas Hofmann , Thorsten Joachims , Yasemin Altun, Support vector machine learning for interdependent and structured output spaces, Proceedings of the twenty-first international conference on Machine learning, p.104, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015341]
• 12: Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2000). Generalized belief propagation. Advances in Neural Information Processing Systems.
• 13: Yedidia, J. S., Freeman, W. T., & Weiss, Y. (2005). Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory.
• 14: Bianca Zadrozny , Charles Elkan, Learning and making decisions when costs and probabilities are both unknown, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.204-213, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502540]
• 15: Zhang, T., & Oles, F. (2001). Text categorization based on regularized linear classification methods. IEEE Transactions on Pattern Analysis and Machine Intelligence.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms