Never Abandon Minorities: Exhaustive Extraction of Bursty Phrases on Microblogs Using Set Cover Problem

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2358–2367 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Never Abandon Minorities: Exhaustive Extraction of Bursty Phrases on Microblogs Using Set Cover Problem Masumi Shirakawa†‡ and Takahiro Hara‡ and Takuya Maekawa‡ hapicom Inc., Japan† Graduate School of Information Science and Technology, Osaka University, Japan‡ shirakawa@hapicom.jp {hara, maekawa}@ist.osaka-u.ac.jp Abstract We propose a language-independent data- driven method to exhaustively extract bursty phrases of arbitrary forms (e.g., phrases other than simple noun phrases) from microblogs. The burst (i.e., the rapid increase of the occurrence) of a phrase causes the burst of overlapping N- grams including incomplete ones. In other words, bursty incomplete N-grams in- evitably overlap bursty phrases. Thus, the proposed method performs the extraction of bursty phrases as the set cover problem in which all bursty N-grams are covered by a minimum set of bursty phrases. Experi- mental results using Japanese Twitter data showed that the proposed method outper- formed word-based, noun phrase-based, and segmentation-based methods both in terms of accuracy and coverage. 1 Introduction Background and motivation. Trends on mi- croblogs reflect manifold real-world events includ- ing natural disaster, new product launch, televi- sion broadcasting, public speech, airplane acci- dent, scandal and national holiday. To catch real- world events, not a few researchers and practi- tioners have sought ways to detect trends on mi- croblogs. Trend detection often involves bursty phrase extraction, i.e., extracting phrases of which occurrence rate in microblog texts posted within a certain period of time (and from a certain location) is much higher than that of the normal state. Ex- tracted bursty phrases are directly used as trends as Twitter1 officially provides, or sent to higher-order processes such as clustering and event labeling. 1https://twitter.com/. Bursty phrases on microblogs are likely to be noun phrases, but sometimes deviate from such standards. The title of a movie, song, game or any creation can be an arbitrary form like a long and/or general phrase (e.g., Spielberg’s movie “catch me if you can”, the Beatles’ song “let it be”)2. memorable phrase (e.g., Steve Jobs’s phrase “stayA hungry, stay foolish”) can also be a bursty phrase on microblogs. Even numbers and symbols can be potentially bursty phrases (e.g., “1984” can be a novel, “!!!” can be an artist). Any filtering rule such as stop word removal, part-of-speech (POS) tag restrictions, or length limit can mistakenly fil- ter out bursty phrases. Extracting irregularly-formed bursty phrases as described in the previous paragraph is difficult since no restriction can be used anymore to fil- ter out incomplete N-grams. However, they are rare and little influence the overall accuracy even if they are correctly extracted. Not only that, tack- ling such difficult and rare cases easily leads to extracting many incomplete N-grams and deteri- orating the accuracy. Almost all existing work has therefore ignored difficult and rare cases, and con- centrated on extracting simple phrases (e.g., uni- grams, bi-grams, tri-grams, or noun phrases iden- tified by POS taggers). By sacrificing minorities, …

Content truncated to 500 words