Meta methods for model sharing in personal information systems

ABSTRACT

This article introduces a methodology for automatically organizing document collections into thematic categories for Personal Information Management (PIM) through collaborative sharing of machine learning models in an efficient and privacy-preserving way. Our objective is to combine multiple independently learned models from several users to construct an advanced ensemble-based decision model by taking the knowledge of multiple users into account in a decentralized manner, for example, in a peer-to-peer overlay network. High accuracy of the corresponding supervised (classification) and unsupervised (clustering) methods is achieved by restrictively leaving out uncertain documents rather than assigning them to inappropriate topics or clusters with low confidence. We introduce a formal probabilistic model for the resulting ensemble based meta methods and explain how it can be used for constructing estimators and for goal-oriented tuning. Comprehensive evaluation results on different reference data sets illustrate the viability of our approach.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001 [doi>10.1162/15324430152733133]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Matthias Bender , Sebastian Michel , Peter Triantafillou , Gerhard Weikum , Christian Zimmer, Improving collection selection with overlap awareness in P2P search engines, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076049]
• 4: Bender, M., Michel, S., Triantafillou, P., Weikum, G., and Zimmer, C. 2006. P2P content search: Give the Web back to the people. In Proceedings of the 5th International Workshop on Peer-to-Peer Systems (IPTPS).
• 5: Bender, M., Michel, S., Weikum, G., and Zimmer, C. 2004. Bookmark-driven query routing in peer-to-peer Web search. In Proceedings of the SIGIR Workshop on P2P Information Retrieval.
• 6: Henk Ernst Blok , Djoerd Hiemstra , Sunil Choenni , Franciska de Jong , Henk M. Blanken , Peter M.G. Apers, Predicting the cost-quality trade-off for information retrieval queries: facilitating database design and query optimization, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502621]
• 7: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 8: Richard Boardman , M. Angela Sasse, "Stuff goes into the computer and doesn't come out": a cross-tool study of personal information management, Proceedings of the SIGCHI conference on Human factors in computing systems, p.583-590, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985766]
• 9: Brank, J., Grobelnik, M., Milic-Frayling, N., and Mladenic, D. 2003. Training text classifiers with SVM on very few positive examples. Tech. rep. MSR-TR-2003-34, Microsoft Corp.
• 10: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 11: Brinker, K. and Hüllermeier, E. 2006. Case-based label ranking. In Machine Learning: Proceedings of the 17th European Conference on Machine Learning (ECML'06), J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, Eds. Lecture Notes in Computer Science. Springer, 566--573.
• 12: Klaus Brinker , Eyke Hüllermeier, Label Ranking in Case-Based Reasoning, Proceedings of the 7th international conference on Case-Based Reasoning: Case-Based Reasoning Research and Development, August 13-16, 2007, Belfast, Northern Ireland, UK [doi>10.1007/978-3-540-74141-1_6]
• 13: Jake D. Brutlag , Christopher Meek, Challenges of the Email Domain for Text Classification, Proceedings of the Seventeenth International Conference on Machine Learning, p.103-110, June 29-July 02, 2000
• 14: Buckland, M. K. 1992. Emmanuel Goldberg, electronic document retrieval, and Vannevar Bush's memex. J. Amer. Soc. Inform. Sci. 43, 4, 284--294.
• 15: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 16: Bush, V. 1945. As we may think. Atlantic Monthly 176, 1, 101--108.
• 17: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 18: Philip Kin-Wah Chan , Salvatore J. Stolfo, An extensible meta-learning approach for scalable and accurate inductive learning, Columbia University, New York, NY, 1996
• 19: Namyoun Choi , Il-Yeol Song , Hyoil Han, A survey on ontology mapping, ACM SIGMOD Record, v.35 n.3, p.34-41, September 2006 [doi>10.1145/1168092.1168097]
• 20: Cormack, G. V. 2006. Trec 2006 spam evaluation track overview. In Proceedings of the 15th Text Retrieval Conference (TREC'06).
• 21: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 22: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564429]
• 23: Edward Cutrell , Daniel Robbins , Susan Dumais , Raman Sarin, Fast, flexible filtering with phlat, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124812]
• 24: Rajesh N. Dave, Characterization and detection of noise in clustering, Pattern Recognition Letters, v.12 n.11, p.657-664, Nov. 1991 [doi>10.1016/0167-8655(91)90002-4]
• 25: Inderjit S. Dhillon , Dharmendra S. Modha, A Data-Clustering Algorithm on Distributed Memory Multiprocessors, Revised Papers from Large-Scale Parallel Data Mining, Workshop on Large-Scale Parallel KDD Systems, SIGKDD, p.245-260, August 15, 1999
• 26: Evgenia Dimitriadou , Andreas Weingessel , Kurt Hornik, A Combination Scheme for Fuzzy Clustering, Proceedings of the 2002 AFSS International Conference on Fuzzy Systems. Calcutta: Advances in Soft Computing, p.332-338, February 03-06, 2002
• 27: Dong, X. and Halevy, A. 2005. A platform for personal information management and integration. In Proceedings of the 2nd Conference on Innovative Systems Research (CIDR). 119--130.
• 28: Anton N. Dragunov , Thomas G. Dietterich , Kevin Johnsrude , Matthew McLaughlin , Lida Li , Jonathan L. Herlocker, TaskTracer: a desktop environment to support multi-tasking knowledge workers, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040855]
• 29: Susan Dumais , Edward Cutrell , JJ Cadiz , Gavin Jancke , Raman Sarin , Daniel C. Robbins, Stuff I've seen: a system for personal information retrieval and re-use, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860451]
• 30: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 31: Ester, M., Kriegel, H.-P., and Sander, J. 2001. Knowledge Discovery in Databases. Springer.
• 32: Xiaoli Zhang Fern , Carla E. Brodley, Solving cluster ensemble problems by bipartite graph partitioning, Proceedings of the twenty-first international conference on Machine learning, p.36, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015414]
• 33: Data Clustering Using Evidence Accumulation, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 4, p.40276, August 11-15, 2002
• 34: Yoav Freund, An adaptive version of the boost by majority algorithm, Proceedings of the twelfth annual conference on Computational learning theory, p.102-113, July 07-09, 1999, Santa Cruz, California, United States [doi>10.1145/307400.307419]
• 35: Giorgio Fumera , Ignazio Pillai , Fabio Roli, Classification with Reject Option in Text Categorisation Systems, Proceedings of the 12th International Conference on Image Analysis and Processing, p.582, September 17-19, 2003
• 36: Jim Gemmell , Gordon Bell , Roger Lueder, MyLifeBits: a personal database for everything, Communications of the ACM, v.49 n.1, p.88-95, January 2006 [doi>10.1145/1107458.1107460]
• 37: Jim Gemmell , Gordon Bell , Roger Lueder , Steven Drucker , Curtis Wong, MyLifeBits: fulfilling the Memex vision, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France [doi>10.1145/641007.641053]
• 38: Goerlitz, O., Sizov, S., and Staab, S. 2008. PINTS: Peer-to-Peer infrastructure for tagging systems. In Proceedings of the 7th International Workshop on Peer-to-Peer Systems (IPTPS).
• 39: Groza, T., Handschuh, S., Moeller, K., Grimnes, G., Sauermann, L., Minack, E., Mesnage, C., Jazayeri, M., Reif, G., and Gudjonsdottir, R. 2007. The NEPOMUK Project—On the way to the social semantic desktop. In Proceedings of the International Conference on Semantic Technologies (I-Semantics). 201--211.
• 40: Stephen Haag , Maeve Cummings , Amy Phillips, Management Information Systems for the Information Age, McGraw-Hill Irwin, 2007
• 41: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 42: Hartigan, J. and Wong, M. 1979. A k-Means clustering algorithm. Appl. Stat. 28, 100--108.
• 43: imdb. Internet movie database. http://www.imdb.com.
• 44: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 45: Hillol Kargupta , Weiyun Huang , Krishnamoorthy Sivakumar , Erik Johnson, Distributed clustering using collective principal component analysis, Knowledge and Information Systems, v.3 n.4, p.422-448, November 2001 [doi>10.1007/PL00011677]
• 46: Klimt, B. and Yang, Y. 2004. The enron corpus: A new dataset for email classification research. In Proceedings of the 15th European Conference on Machine Learning (ECML'04). Lecture Notes in Computer Science, Springer, 217--226.
• 47: S. L. Kogan , M. J. Muller, Ethnographic study of collaborative knowledge work, IBM Systems Journal, v.45 n.4, p.759-771, October 2006
• 48: Kuhn, H. 1955. The Hungarian method for the assignment problem. Naval Resear. Logistics Quart. 2, 83--97.
• 49: Ludmila I. Kuncheva, Combining Pattern Classifiers: Methods and Algorithms, Wiley-Interscience, 2004
• 50: Thomas C. W. Landgrebe , David M. J. Tax , Pavel Paclík , Robert P. W. Duin, The interaction between classification and reject performance for distance-based reject-option classifiers, Pattern Recognition Letters, v.27 n.8, p.908-917, June 2006 [doi>10.1016/j.patrec.2005.10.015]
• 51: David D. Lewis, Evaluating text categorization, Proceedings of the workshop on Speech and Natural Language, p.312-318, February 19-22, 1991, Pacific Grove, California [doi>10.3115/112405.112471]
• 52: Tao Li , Sheng Ma , Mitsunori Ogihara, Document clustering via adaptive subspace iteration, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009031]
• 53: Tao Li , Shenghuo Zhu , Mitsunori Ogihara, Algorithms for clustering high dimensional and distributed data, Intelligent Data Analysis, v.7 n.4, p.305-326, September 2003
• 54: N. Littlestone , M. K. Warmuth, The weighted majority algorithm, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.256-261, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63487]
• 55: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 56: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 57: Masulli, F. and Valentini, G. 2000. Comparing decomposition methods for classification. In Proceedings of the International Conference on Knowledge-Based Intelligent Engineering Systems and Applied Technologies (KES). 788--792.
• 58: Srujana Merugu , Joydeep Ghosh, Privacy-preserving Distributed Clustering using Generative Models, Proceedings of the Third IEEE International Conference on Data Mining, p.211, November 19-22, 2003
• 59: Millen, D., Yeng, M., Whittaker, S., and Feinberg, J. 2007. Social bookmarking and exploratory search. In Proceedings of the European Conference on Computer Supported Cooperative Work.
• 60: David R. Millen , Jonathan Feinberg , Bernard Kerr, Dogear: Social bookmarking in the enterprise, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124792]
• 61: Pierskalla, W. 1968. The multi-dimensional assignment problem. Operations Res. 16, 422--431.
• 62: Platt, J. 1999. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In Advances in Large Margin Classifiers, MIT Press, 61--74.
• 63: M. F. Porter, An algorithm for suffix stripping, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 64: Quan, D., Huynh, D., and Karger, D. 2003. Haystack: A platform for authoring end user semantic web applications. In Proceedings of the International Semantic Web Conference. 738--753.
• 65: R. Rivest, The MD5 Message-Digest Algorithm, RFC Editor, 1992
• 66: Andrew I. Schein , Alexandrin Popescul , Lyle H. Ungar , David M. Pennock, Methods and metrics for cold-start recommendations, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564421]
• 67: Richard B. Segal , Jeffrey O. Kephart, MailCat: an intelligent assistant for organizing e-mail, Proceedings of the third annual conference on Autonomous Agents, p.276-282, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301209]
• 68: Shvaiko, P. and Euzenat, J. 2005. A survey of schema-based matching approaches. Lecture Notes in Computer Science, vol. 3730, Springer, 146--171.
• 69: Siersdorfer, S. and Sizov, S. 2003. Construction of Feature Spaces and Meta Methods for Classification of Web Documents. In Proceedings of the 10th Conference Datenbanksysteme fuer Business, Technologie und Web (BTW). 197--206.
• 70: Stefan Siersdorfer , Sergej Sizov, Restrictive clustering and metaclustering for self-organizing document collections, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009032]
• 71: Siersdorfer, S. and Sizov, S. 2006. Automatic document organization in a p2p environment. In Proceedings of the 28th European Conference on IR Research (ECIR). 265--276.
• 72: Siersdorfer, S. and Sizov, S. 2007. Restrictive methods and meta methods for thematically focused web search. In Handbook of Research on Web Information Systems Quality, Idea Group.
• 73: Stefan Siersdorfer , Sergej Sizov , Gerhard Weikum, Goal-oriented methods and meta methods for document classification and their parameter tuning, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031184]
• 74: Siersdorfer, S. and Weikum, G. 2005. Using restrictive classification and meta classification for junk elimination. In Proceedings of the 27th European Conference on Information Retrieval (ECIR'05), D. Losada and J. M. F. Luna, Eds. Lecture Notes in Computer Science, vol. 3408. Springer, 287--299.
• 75: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 76: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003 [doi>10.1162/153244303321897735]
• 77: Surendran, A. C., Platt, J. C., and Renshaw, E. 2005. Automatic discovery of personal topics to organize email. In Proceedings of the 2nd Conference on Email and Anti-Spam.
• 78: Jaime Teevan , Christine Alvarado , Mark S. Ackerman , David R. Karger, The perfect search engine is not enough: a study of orienteering behavior in directed search, Proceedings of the SIGCHI conference on Human factors in computing systems, p.415-422, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985745]
• 79: Alexander Topchy , Anil K. Jain , William Punch, Combining Multiple Weak Clusterings, Proceedings of the Third IEEE International Conference on Data Mining, p.331, November 19-22, 2003
• 80: Vaidya, J. and Clifton, C. 2004. Privacy preserving naive bayes classifier for vertically partitioned data. In Proceedings of the SIAM International Conference on Data Mining.
• 81: Vailaya, A. and Jain, A. K. 2000. Reject option for vq-based bayesian classification. In Proceedings of the International Conference on Pattern Recognition (ICPR'00). 2048--2051.
• 82: Van Rijsbergen, C. 1977. A theoretical basis for the use of co-occurence data in information retrieval. J. Document. 33, 2, 106--119.
• 83: Gang Wang , Frederick H. Lochovsky, Feature selection with conditional mutual information maximin in text categorization, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031241]
• 84: Haixun Wang , Wei Fan , Philip S. Yu , Jiawei Han, Mining concept-drifting data streams using ensemble classifiers, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956778]
• 85: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]
• 86: Hwanjo Yu , Kevin Chen-Chuan Chang , Jiawei Han, Heterogeneous Learner for Web Page Classification, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.538, December 09-12, 2002
• 87: Zhang, R. and Metaxas, D. 2006. Ro-svm: Support vector machine with reject option for image categorization. In Proceedings of the British Machine Vision Conference (BMNC'06). vol. 3, 1209--1218.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Classification, clustering, meta methods, peer-to-peer, personal information management, restrictive methods