Collaborative classifier agents: studying the impact of learning in distributed document classification

ABSTRACT

We developed a multi-agent framework where agents had limited/distributed knowledge for document classification and collaborated with each other to overcome the knowledge distribution. Each agent was equipped with a certain learning algorithm for predicting potential collaborators, or helping agents. We conducted experimental research on a standard news corpus to examine the impact of two learning algorithms: Pursuit Learning and Nearest Centroid Learning. For a fundamental retrieval operation, namely classification, both algorithms achieved competitive classification effectiveness and efficiency. Subsequently, the impact of the learning exploration rate and the maximum collaboration range on classification effectiveness and efficiency were examined. Close investigation of agent learning dynamics revealed increasing and stabilizing patterns that were enhanced by the learning algorithms.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Katy Börner , Luca Dall'Asta , Weimao Ke , Alessandro Vespignani, Studying the emerging global brain: Analyzing and visualizing the impact of co-authorship teams: Research Articles, Complexity, v.10 n.4, p.57-67, March 2005 [doi>10.1002/cplx.v10:4]
• 3: Jamie Callan , Fabio Crestani , Mark Sanderson, SIGIR 2003 workshop on distributed information retrieval, ACM SIGIR Forum, v.37 n.2, Fall 2003 [doi>10.1145/959258.959263]
• 4: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636 ]
• 5: James R. Davis , Carl Lagoze, NCSTRL: design and deployment of a globally distributed digital library, Journal of the American Society for Information Science, v.51 n.3, p.273-280, Feb. 2000 [doi>10.1002/(SICI)1097-4571(2000)51:3<273::AID-ASI6>3.0.CO;2-6]
• 6: Naomi Dushay , James C. French , Carl Lagoze, Using query mediators for distributed searching in federated digital libraries, Proceedings of the fourth ACM conference on Digital libraries, p.171-178, August 11-14, 1999, Berkeley, California, United States [doi>10.1145/313238.313302]
• 7: Edward A. Fox , Gregory R. Crane , Stephen M. Griffin , Ronald L. Larsen , David M. Levy , David J. McArthur , Sugimoto Shigeo, Digital libraries settling the score: 10 years hence and 10 before, Proceedings of the 4th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2004, Tuscon, AZ, USA [doi>10.1145/996350.996439]
• 8: Yueyu Fu , Weimao Ke , Javed Mostafa, Automated text classification using a multi-agent framework, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA [doi>10.1145/1065385.1065420]
• 9: A. Helsinger, M. Thome, and T. Wright. Cougaar: A scalable, distributed multi-agent architecture. In Proceedings of IEEE Conference on Systems, Man and Cybernetics 2004, October 2004.
• 10: W. Ke, Y. Fu, and J. Mostafa. Advanced information retrieval web services for digital libraries. Library Collections, Acquisitions, and Technical Services, 29(2):220--224, 2005.
• 11: Kevin Knight, Mining online text, Communications of the ACM, v.42 n.11, p.58-61, Nov. 1999 [doi>10.1145/319382.319394]
• 12: Robert R. Korfhage, Information storage and retrieval, John Wiley & Sons, Inc., New York, NY, 1997
• 13: David D. Lewis, Text representation for intelligent text retrieval: a classification-oriented view, Text-based intelligent systems: current research and practice in information extraction and retrieval, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1992
• 14: David D. Lewis, Evaluating and optimizing autonomous text classification systems, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.246-254, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215366]
• 15: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 16: Filippo Menczer , Richard K. Belew, Adaptive information agents in distributed textual environments, Proceedings of the second international conference on Autonomous agents, p.157-164, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280794]
• 17: Pragnesh Jay Modi , Wei-Min Shen, Collaborative multiagent learning for classification tasks, Proceedings of the fifth international conference on Autonomous agents, p.37-38, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.375854]
• 18: J. Mostafa , W. Lam, Automatic classification using supervised learning in a medical document filtering application, Information Processing and Management: an International Journal, v.36 n.3, p.415-444, May 2000 [doi>10.1016/S0306-4573(99)00033-3 ]
• 19: S. Mukhopadhyay , S. Peng , R. Raje , J. Mostafa , M. Palakal, Distributed multi-agent information filtering—A comparative study: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.8, p.834-842, June 2005 [doi>10.1002/asi.v56:8]
• 20: Snehasis Mukhopadhyay , Shengquan Peng , Rajeev Raje , Mathew Palakal , Javed Mostafa, Multi-agent information classification using dynamic acquaintance lists, Journal of the American Society for Information Science and Technology, v.54 n.10, p.966-975, August 2003 [doi>10.1002/asi.10292]
• 21: S. Mukhopadhyay and M. Thathachar. Associative learning of boolean functions. IEEE Transactions on Systems, Man and Cybernetics, 19:1008--1015, 1989.
• 22: Andreas Paepcke , Chen-Chuan K. Chang , Terry Winograd , Héctor García-Molina, Interoperability for digital libraries worldwide, Communications of the ACM, v.41 n.4, p.33-42, April 1998 [doi>10.1145/273035.273044]
• 23: S. Peng , S. Mukhopadhyay , R. Raje , M. Palakal, A Comparison Between Single-agent and Multi-agent Classification of Documents, Proceedings of the 10th Heterogeneous Computing Workshop â"" HCW 2001 (Workshop 1), p.20090.2, April 23-27, 2001
• 24: Francisco B. Pereira , Ernesto Costa, The influence of learning in the behavior of information retrieval adaptive agents, Proceedings of the 2000 ACM symposium on Applied computing, p.452-457, March 2000, Como, Italy [doi>10.1145/335603.335906]
• 25: Vladimir G. Red'ko, Problem of the Global Brain and Multi-Agent Modeling, Proceedings of the 2002 IEEE International Conference on Artificial Intelligence Systems (ICAIS'02), p.279, September 05-10, 2002
• 26: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 27: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 28: R. W. House , O. E. Taulbee, Invited papers—1: classification in information storage and retrieval, Proceedings of the 1965 20th national conference, p.119-137, August 24-26, 1965, Cleveland, Ohio, United States [doi>10.1145/800197.806038]
• 29: Vladimir Gorodetsky , Oleg Karsaeyv , Vladimir Samoilov, Multi-agent Technology for Distributed Data Mining and Classification, Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology, p.438, October 13-17, 2003
• 30: M. Wimmer , R. Traunmuller, Trends in Electronic Government: Managing Distributed Knowledge, Proceedings of the 11th International Workshop on Database and Expert Systems Applications, p.340, September 06-08, 2000
• 31: 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
• 32: K. Yang. Combining Text-, Link-, and Classification-based Retrieval Methods to Enhance Information Discovery on the Web. PhD thesis, University of North Carolina at Chapel Hill, 2002.
• 33: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 34: Edmund S. Yu , Ping C. Koo , Elizabeth D. Liddy, Evolving intelligent text-based agents, Proceedings of the fourth international conference on Autonomous agents, p.388-395, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337550]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries
          Subjects: Systems issues

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering
      H.3.4 Systems and Software
          Subjects: Information networks; Distributed systems

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
collaboration, distributed classification, effectiveness, efficiency, information retrieval, learning, multi-agent system