Simultaneously modeling semantics and structure of threaded discussions: a sparse coding approach and its applications

ABSTRACT

The huge amount of knowledge in web communities has motivated the research interests in threaded discussions. The dynamic nature of threaded discussions poses lots of challenging problems for computer scientists. Although techniques such as semantic models and structural models have been shown to be useful in a number of areas, they are inefficient in understanding threaded discussions due to three reasons: (I) as most of users read existing messages before posting, posts in a discussion thread are temporally dependent on the previous ones; It causes the semantics and structure to be coupled with each other in threaded discussions; (II) in online discussion threads, there are a lot of junk posts which are useless and may disturb content analysis; and (III) it is very hard to judge the quality of a post. In this paper, we propose a sparse coding-based model named SMSS to Simultaneously Model Semantics and Structure of threaded discussions. The model projects each post into a topic space, and approximates each post by a linear combination of previous posts in the same discussion thread. Meanwhile, the model also imposes two sparse constraints to force a sparse post reconstruction in the topic space and a sparse post approximation from previous posts. The sparse properties effectively take into account the characteristics of threaded discussions. Towards the above three problems, we demonstrate the competency of our model in three applications: reconstructing reply structure of threaded discussions, identifying junk posts, and finding experts in a given board/sub-board in web communities. Experimental results show encouraging performance of the proposed SMSS model in all these applications.

REFERENCES

• 1: K. Balog, L. Azzopardi, and M. de Rijke. A language modeling framework for expert finding. Information Processing and Management, 06(003):1--12, 2008.
• 2: David M. Blei , John D. Lafferty, Dynamic topic models, Proceedings of the 23rd international conference on Machine learning, p.113-120, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143859]
• 3: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003
• 4: Wray Buntine , Aleks Jakulin, Applying discrete PCA in data analysis, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.59-66, July 07-11, 2004, Banff, Canada
• 5: C. Chemudugunta, P. Smyth, and M. Steyvers. Modeling general and specific aspects of documents with a probabilistic topic model. Advances in newral information processing systems, 41(6):391--407, 1990.
• 6: Gao Cong , Long Wang , Chin-Yew Lin , Young-In Song , Yueheng Sun, Finding question-answer pairs from online forums, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390415]
• 7: S. Ding, G. Cong, C.-Y. Lin, and X. Zhu. Using conditional random Éelds to extract contexts and answers of questions from online forums. In Proc. 11th ACL, pages 710--718, 2008.
• 8: Gu Xu , Wei-Ying Ma, Building implicit links from content for forum search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148224]
• 9: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 10: J. Huang, M. Zhou, and D. Yang. Extracting chatbot knowledge from online discussion forums. In Proc. 11th IJCAI, pages 423--428, 2006.
• 11: J.Scott. Social Network Analysis: A Handbook. Sage Publications, London, 2000.
• 12: Jong Wook Kim , K. Selçuk Candan , Mehmet E. Dönderler, Topic segmentation of message hierarchies for indexing and navigation support, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060795]
• 13: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 14: A. McCallum, A. Corrada-Emmanuel, and X. Wang. Topic and role discovery in social networks. In Proc. of IJCAI, pages 249--272, 2007.
• 15: G. Mishne, D. Carmel, and R. Lempel. Blocking blog spam with language model disagreement. In Proc. of AIRWeb, 2005.
• 16: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report. Stanford University, 1998.
• 17: Xuan-Hieu Phan , Le-Minh Nguyen , Susumu Horiguchi, Learning to classify short and sparse text & web with hidden topics from large-scale data collections, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367510]
• 18: Michal Rosen-Zvi , Thomas Griffiths , Mark Steyvers , Padhraic Smyth, The author-topic model for authors and documents, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.487-494, July 07-11, 2004, Banff, Canada
• 19: Dou Shen , Qiang Yang , Jian-Tao Sun , Zheng Chen, Thread detection in dynamic text message streams, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148180]
• 20: Xiaodan Song , Belle L. Tseng , Ching-Yung Lin , Ming-Ting Sun, Personalized recommendation driven by information flow, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148258]
• 21: C. Wang, D.M. Blei, and D. Heckerman. Continuous time dynamic topic models. In Proc. of UAI, 2008.
• 22: Jun Zhang , Mark S. Ackerman , Lada Adamic, Expertise networks in online communities: structure and algorithms, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242603]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation

Keywords:
expert finding, junk identification, reply reconstruction, sparse coding, threaded discussion