Summarization of Multi-Document Topic Hierarchies using Submodular Mixtures

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 553–563, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Summarization of Multi-Document Topic Hierarchies using Submodular Mixtures Ramakrishna B Bairi IITB-Monash Research Academy IIT Bombay Mumbai, 40076, India bairi@cse.iitb.ac.in Rishabh Iyer University of Washington Seattle, WA-98175, USA rkiyer@u.washington.edu Ganesh Ramakrishnan IIT Bombay Mumbai, 40076, India ganesh@cse.iitb.ac.in Jeff Bilmes University of Washington Seattle, WA-98175, USA bilmes@uw.edu Abstract We study the problem of summarizing DAG-structured topic hierarchies over a given set of documents. Example appli- cations include automatically generating Wikipedia disambiguation pages for a set of articles, and generating candidate multi-labels for preparing machine learn- ing datasets (e.g., for text classification, functional genomics, and image classi- fication). Unlike previous work, which focuses on clustering the set of documents using the topic hierarchy as features, we directly pose the problem as a submodular optimization problem on a topic hierarchy using the documents as features. Desirable properties of the chosen topics include document coverage, specificity, topic diversity, and topic homogeneity, each of which, we show, is naturally modeled by a submodular function. Other information, provided say by unsupervised approaches such as LDA and its variants, can also be utilized by defining a submodular function that expresses coherence between the chosen topics and this information. We use a large-margin framework to learn convex mixtures over the set of submodular components. We empirically evaluate our method on the problem of automatically generating Wikipedia disambiguation pages using human generated clusterings as ground truth. We find that our frame- work improves upon several baselines according to a variety of standard evalua- tion metrics including the Jaccard Index, F1 score and NMI, and moreover, can be scaled to extremely large scale problems. 1 Introduction Several real world machine learning applications involve hierarchy based categorization of topics for a set of objects. Objects could be, e.g., a set of documents for text classification, a set of genes in functional genomics, or a set of images in computer vision. One can often define a natural topic hierarchy to categorize these objects. For example, in text and image classification problems, each document or image is assigned a hierarchy of labels — a baseball page is assigned the labels “baseball” and “sports.” Moreover, many of these applications, naturally have an existing topic hierarchy generated on the entire set of objects (Rousu et al., 2006; Barutcuoglu et al., 2006; ling Zhang and hua Zhou, 2007; Silla and Freitas, 2011; Tsoumakas et al., 2010). Given a DAG-structured topic hierarchy and a subset of objects, we investigate the problem of finding a subset of DAG-structured topics that are induced by that subset (of objects). This problem arises naturally in several real world applications. For example, consider the problem of identifying appropriate label sets for a collection of articles. Several existing text collection datasets such as 20 Newsgroup1, Reuters-215782 work with a prede- fined set of topics. We observe that these topic …

Content truncated to 500 words