Timezone: »

 
Poster
Online L1-Dictionary Learning with Application to Novel Document Detection
Shiva Kasiviswanathan · Huahua Wang · Arindam Banerjee · Prem Melville

Mon Dec 03 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor
in Poster Session and Reception »

Given their pervasive use, social media, such as Twitter, have become a leading source of breaking news. A key task in the automated identification of such news is the detection of novel documents from a voluminous stream of text documents in a scalable manner. Motivated by this challenge, we introduce the problem of online L1-dictionary learning where unlike traditional dictionary learning, which uses squared loss, the L1-penalty is used for measuring the reconstruction error. We present an efficient online algorithm for this problem based on alternating directions method of multipliers, and establish a sublinear regret bound for this algorithm. Empirical results on news-stream and Twitter data, shows that this online L1-dictionary learning algorithm for novel document detection gives more than an order of magnitude speedup over the previously known batch algorithm, without any significant loss in quality of results. Our algorithm for online L1-dictionary learning could be of independent interest.

[ PDF] 

Author Information

Shiva Kasiviswanathan (Amazon)
Huahua Wang (University of Minnesota, Twin Cites)
Arindam Banerjee (Univ. of Minnesota)
Prem Melville (Millennium Management)

More from the Same Authors