More Web Proxy on the site http://driver.im/

research-article

Reflect and correct: A misclassification prediction approach to active inference

Authors:

Mustafa Bilgic,

Lise GetoorAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 3, Issue 4

Article No.: 20, Pages 1 - 32

https://doi.org/10.1145/1631162.1631168

Published: 04 December 2009 Publication History

Abstract

Information diffusion, viral marketing, graph-based semi-supervised learning, and collective classification all attempt to model and exploit the relationships among nodes in a network to improve the performance of node labeling algorithms. However, sometimes the advantage of exploiting the relationships can become a disadvantage. Simple models like label propagation and iterative classification can aggravate a misclassification by propagating mistakes in the network, while more complex models that define and optimize a global objective function, such as Markov random fields and graph mincuts, can misclassify a set of nodes jointly. This problem can be mitigated if the classification system is allowed to ask for the correct labels for a few of the nodes during inference. However, determining the optimal set of labels to acquire is intractable under relatively general assumptions, which forces us to resort to approximate and heuristic techniques. We describe three such techniques in this article. The first one is based on directly approximating the value of the objective function of label acquisition and greedily acquiring the label that provides the most improvement. The second technique is a simple technique based on the analogy we draw between viral marketing and label acquisition. Finally, we propose a method, which we refer to as reflect and correct, that can learn and predict when the classification system is likely to make mistakes and suggests acquisitions to correct those mistakes. We empirically show on a variety of synthetic and real-world datasets that the reflect and correct method significantly outperforms the other two techniques, as well as other approaches based on network structural measures such as node degree and network clustering.

References

[1]

Bilgic, M. and Getoor, L. 2007. VOILA: Efficient feature-value acquisition for classification. In Proceedings of the AAAI Conference on Artificial Intelligence. 1225--1230.

Digital Library

[2]

Bilgic, M. and Getoor, L. 2008. Effective label acquisition for collective classification. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 43--51.

Digital Library

[3]

Blum, A. and Chawla, S. 2001. Learning from labeled and unlabeled data using graph mincuts. In Proceedings of the International Conference on Machine Learning. 19--26.

Digital Library

[4]

Chakrabarti, S., Dom, B., and Indyk, P. 1998. Enhanced hypertext categorization using hyperlinks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York, 307--318.

Digital Library

[5]

Chapelle, O., Schölkopf, B., and Zien, A., Eds. 2006. Semi-Supervised Learning. MIT Press, Cambridge, MA.

[6]

Cohn, D., Atlas, L., and Ladner, R. 1994. Improving generalization with active learning. Mach. Learn. 15, 2, 201--221.

Digital Library

[7]

Cohn, D. A., Ghahramani, Z., and Jordan, M. I. 1996. Active learning with statistical models. J. Artif. Intell. Res. 4, 129--145.

[8]

Freund, Y., Seung, H. S., Shamir, E., and Tishby, N. 1997. Selective sampling using the query by committee algorithm. Mach. Learn. 28, 2, 133--168.

Digital Library

[9]

Getoor, L., Friedman, N., Koller, D., and Taskar, B. 2002. Learning probabilistic models of link structure. J. Mach. Learn. Res. 3, 679--707.

Digital Library

[10]

Getoor, L., Segal, E., Taskar, B., and Koller, D. 2001. Probabilistic models of text and link structure for hypertext classification. In Proceedings of the IJCAI Workshop on Text Learning: Beyond Supervision. ACM, New York, 24--29.

[11]

Giles, C. L., Bollacker, K. D., and Lawrence, S. 1998. CiteSeer: An automatic citation indexing system. In Proceedings of the ACM Conference on Digital Libraries. ACM, New York, 89--98.

Digital Library

[12]

Gilks, W. R., Richardson, S., and Spiegelhalter, D. J. 1996. Markov Chain Monte Carlo in Practice. Interdisciplinary Statistics. Chapman&Hall/CRC.

[13]

Howard, R. A. 1966. Information value theory. IEEE Trans. Syst. Sci. Cybernet. 2, 1, 22--26.

[14]

Jensen, D., Neville, J., and Gallagher, B. 2004. Why collective inference improves relational classification. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 593--598.

Digital Library

[15]

Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., and Saul, L. K. 1999. An introduction to variational methods for graphical models. Mach. Learn. 37, 2, 183--233.

Digital Library

[16]

Kempe, D., Kleinberg, J., and Tardos, E. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 137--146.

Digital Library

[17]

Krause, A. and Guestrin, C. 2005. Optimal nonmyopic value of information in graphical models—efficient algorithms and theoretical limits. In Proceedings of the International Joint Conference on Artificial Intelligence. 1339--1345.

Digital Library

[18]

Lafferty, J. D., McCallum, A., and Pereira, F. C. N. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning. 282--289.

Digital Library

[19]

Leskovec, J., Adamic, L. A., and Huberman, B. A. 2007. The dynamics of viral marketing. ACM Trans. Web 1, 1, 5.

Digital Library

[20]

Leskovec, J., Kleinberg, J., and Faloutsos, C. 2007. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 1, 177--187.

Digital Library

[21]

Lewis, D. D. and Gale, W. A. 1994. A sequential algorithm for training text classifiers. In Proceedings of the ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 3--12.

Digital Library

[22]

Lu, Q. and Getoor, L. 2003a. Link based classification. In Proceedings of the International Conference on Machine Learning. 496--503.

[23]

Lu, Q. and Getoor, L. 2003b. Link-based classification using labeled and unlabeled data. In Proceedings of the ICML Workshop on the Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining.

[24]

Macskassy, S. and Provost, F. 2003. A simple relational classifier. In Proceedings of the ACM Workshop on Multi-Relational Data Mining. ACM, New York.

[25]

Macskassy, S. and Provost, F. 2007. Classification in networked data: A toolkit and a univariate case study. J. Mach. Learn. Res. 8, 935--983.

Digital Library

[26]

McCallum, A. and Nigam, K. 1998. Employing EM and pool-based active learning for text classification. In Proceedings of the International Conference on Machine Learning. 350--358.

Digital Library

[27]

McCallum, A. K., Nigam, K., Rennie, J., and Seymore, K. 2000. Automating the construction of internet portals with machine learning. Inf. Retrieval 3, 2, 127--163.

Digital Library

[28]

McDowell, L., Gupta, K. M., and Aha, D. W. 2007. Cautious inference in collective classification. In Proceedings of the AAAI Conference on Artificial Intelligence. 596--601.

Digital Library

[29]

Melville, P. and Mooney, R. J. 2004. Diverse ensembles for active learning. In Proceedings of the International Conference on Machine Learning. 584--591.

Digital Library

[30]

Neville, J. and Jensen, D. 2000. Iterative classification in relational data. In Proceedings of the SRL Workshop in AAAI.

[31]

Newman, M. E. J. 2003. Mixing patterns in networks. Phys. Rev. E 67, 2, 026126.

[32]

Provost, F., Melville, P., and Saar-Tsechansky, M. 2007. Data acquisition and cost-effective predictive modeling: targeting offers for electronic commerce. In Proceedings of the ACM International Conference on Electronic Commerce. 389--398.

Digital Library

[33]

Rattigan, M., Maier, M., and Jensen, D. 2007. Exploiting network structure for active inference in collective classification. In Proceedings of the ICDM Workshop on Mining Graphs and Complex Structures. 429--434.

Digital Library

[34]

Richardson, M. and Domingos, P. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 61--70.

Digital Library

[35]

Richardson, M. and Domingos, P. 2006. Markov logic networks. Mach. Learn. 62, 1-2, 107--136.

Digital Library

[36]

Roy, N. and McCallum, A. 2001. Toward optimal active learning through sampling estimation of error reduction. In Proceedings of the International Conference on Machine Learning. 441--448.

Digital Library

[37]

Saar-Tsechansky, M. and Provost, F. 2004. Active sampling for class probability estimation and ranking. Mach. Learn. 54, 2, 153--178.

Digital Library

[38]

Sen, P., Namata, G. M., Bilgic, M., Getoor, L., Gallagher, B., and Eliassi-Rad, T. 2008. Collective classification in network data. AI Magazine 29, 3.

Digital Library

[39]

Seung, H. S., Opper, M., and Sompolinsky, H. 1992. Query by committee. In Proceedings of the ACM Annual Workshop on Computational Learning Theory. ACM, New York, 287--294.

Digital Library

[40]

Sheng, V. S. and Ling, C. X. 2006. Feature value acquisition in testing: a sequential batch test algorithm. In Proceedings of the International Conference on Machine Learning. 809--816.

Digital Library

[41]

Taskar, B., Abbeel, P., and Koller, D. 2002. Discriminative probabilistic models for relational data. In Proceedings of the Annual Conference on Uncertainty in Artificial Intelligence. 485--492.

Digital Library

[42]

Tong, S. and Koller, D. 2002. Support vector machine active learning with applications to text classification. J. Mach. Learn. Res. 2, 45--66.

Digital Library

[43]

Xiang, R. and Neville, J. 2008. Pseudolikelihood em for within-network relational learning. In Proceedings of the IEEE International Conference on Data Mining. IEEE Computer Society Press, Los Alamitos, CA, 1103--1108.

Digital Library

[44]

Yedidia, J., Freeman, W. T., and Weiss, Y. 2000. Generalized belief propagation. In Neural Information Processing Systems. 689--695.

[45]

Zadrozny, B. and Elkan, C. 2001. Learning and making decisions when costs and probabilities are both unknown. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 204--213.

Digital Library

[46]

Zhu, X. and Ghahramani, Z. 2002. Learning from labeled and unlabeled data with label propagation. Tech. Rep. CMU-CALD-02-107, Carnegie Mellon University.

[47]

Zhu, X., Ghahramani, Z., and Lafferty, J. D. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the International Conference on Machine Learning. 912--919.

Cited By

Xie RDeng SDeng WAllahverdyan A(2018)Active image restorationPhysical Review E10.1103/PhysRevE.98.05210898:5Online publication date: 8-Nov-2018
https://doi.org/10.1103/PhysRevE.98.052108
Ramirez-Loaiza MSharma MKumar GBilgic M(2017)Active learningData Mining and Knowledge Discovery10.1007/s10618-016-0469-731:2(287-313)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10618-016-0469-7
Komurlu CShao JAkar BBayrak EBrey ECinar ABilgic M(2017)Active inference for dynamic Bayesian networks with an application to tissue engineeringKnowledge and Information Systems10.1007/s10115-016-0963-750:3(917-943)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10115-016-0963-7
Show More Cited By

Index Terms

Reflect and correct: A misclassification prediction approach to active inference
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees

Recommendations

Effective label acquisition for collective classification
KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

Information diffusion, viral marketing, and collective classification all attempt to model and exploit the relationships in a network to make inferences about the labels of nodes. A variety of techniques have been introduced and methods that combine ...
NMFE-SSCC

Collective classification (CC) is a task to jointly classifying related instances of network data. Enabling CC usually improves the performance of predictive models on fully-labeled training networks with large amount of labeled data. However, acquiring ...
Multi-Label Regularized Generative Model for Semi-Supervised Collective Classification in Large-Scale Networks

The problem of collective classification (CC) for large-scale network data has received considerable attention in the last decade. Enabling CC usually increases accuracy when given a fully-labeled network with a large amount of labeled data. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 3, Issue 4

November 2009

196 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/1631162

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 December 2009

Accepted: 01 August 2009

Revised: 01 July 2009

Received: 01 March 2009

Published in TKDD Volume 3, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
457
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xie RDeng SDeng WAllahverdyan A(2018)Active image restorationPhysical Review E10.1103/PhysRevE.98.05210898:5Online publication date: 8-Nov-2018
https://doi.org/10.1103/PhysRevE.98.052108
Ramirez-Loaiza MSharma MKumar GBilgic M(2017)Active learningData Mining and Knowledge Discovery10.1007/s10618-016-0469-731:2(287-313)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10618-016-0469-7
Komurlu CShao JAkar BBayrak EBrey ECinar ABilgic M(2017)Active inference for dynamic Bayesian networks with an application to tissue engineeringKnowledge and Information Systems10.1007/s10115-016-0963-750:3(917-943)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s10115-016-0963-7
Komurlu C(2016)Active inference for dynamic Bayesian networksProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3061053.3061194(4008-4009)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3061053.3061194
Van Vlasselaer VEliassi-Rad TAkoglu LSnoeck MBaesens B(2015)AFRAIDProceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 201510.1145/2808797.2810058(659-666)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1145/2808797.2810058
Allahverdyan AGalstyan A(2015)Active Inference for Binary Symmetric Hidden Markov ModelsJournal of Statistical Physics10.1007/s10955-015-1321-y161:2(452-466)Online publication date: 9-Aug-2015
https://doi.org/10.1007/s10955-015-1321-y
Komurlu CShao JBilgic M(2014)Dynamic Bayesian network modeling of vascularization in engineered tissuesProceedings of the Eleventh UAI Conference on Bayesian Modeling Applications Workshop - Volume 121810.5555/3020299.3020309(89-98)Online publication date: 27-Jul-2014
https://dl.acm.org/doi/10.5555/3020299.3020309
Zhang PWang JFarhadi AHebert MParikh D(2014)Predicting Failures of Vision SystemsProceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition10.1109/CVPR.2014.456(3566-3573)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1109/CVPR.2014.456
Shi LZhao YTang J(2012)Batch Mode Active Learning for Networked DataACM Transactions on Intelligent Systems and Technology10.1145/2089094.20891093:2(1-25)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1145/2089094.2089109
Attenberg JProvost FApte CGhosh JSmyth P(2011)Online active inference and learningProceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2020408.2020443(186-194)Online publication date: 21-Aug-2011
https://dl.acm.org/doi/10.1145/2020408.2020443
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents