Timezone: »
Machine learning models are often deployed in settings where they must be constantly updated in response to the changes in class definitions while retaining high accuracy on previously learned definitions. A classical use case is fraud detection, where new fraud schemes come one after another. While such an update can be accomplished by re-training on the complete data, the process is inefficient and prevents real-time and on-device learning. On the other hand, efficient methods that incrementally learn from new data often result in the forgetting of previously-learned knowledge. We define this problem as Learning with Dynamic Definition (LDD) and demonstrate that popular models, such as the Vision Transformer and Roberta, exhibit substantial forgetting of past definitions. We present the first practical and provable solution to LDD. Our proposal is a hash-based sparsity model\textit{RIDDLE} that solves evolving definitions by associating samples only to relevant parameters. We prove that our model is a universal function approximator and theoretically bounds the knowledge lost during the update process. On practical tasks with evolving class definition in vision and natural language processing, \textit{RIDDLE} outperforms baselines by up to 30\% on the original dataset while providing competitive accuracy on the update dataset.
Author Information
Zichang Liu (Rice University)
Benjamin Coleman (Rice University)
Tianyi Zhang (Rice University)
Anshumali Shrivastava (Rice University / ThirdAI Corp.)
More from the Same Authors
-
2021 Spotlight: Practical Near Neighbor Search via Group Testing »
Joshua Engels · Benjamin Coleman · Anshumali Shrivastava -
2021 : PISTACHIO: Patch Importance Sampling To Accelerate CNNs via a Hash Index Optimizer »
Zhaozhuo Xu · Anshumali Shrivastava -
2022 : Adaptive Sparse Federated Learning in Large Output Spaces via Hashing »
Zhaozhuo Xu · Luyang Liu · Zheng Xu · Anshumali Shrivastava -
2022 Poster: The trade-offs of model size in large recommendation models : 100GB to 10MB Criteo-tb DLRM model »
Aditya Desai · Anshumali Shrivastava -
2022 Poster: Graph Reordering for Cache-Efficient Near Neighbor Search »
Benjamin Coleman · Santiago Segarra · Alexander Smola · Anshumali Shrivastava -
2021 Poster: Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures »
Zhaozhuo Xu · Zhao Song · Anshumali Shrivastava -
2021 Poster: Practical Near Neighbor Search via Group Testing »
Joshua Engels · Benjamin Coleman · Anshumali Shrivastava -
2021 Poster: Locality Sensitive Teaching »
Zhaozhuo Xu · Beidi Chen · Chaojian Li · Weiyang Liu · Le Song · Yingyan Lin · Anshumali Shrivastava -
2021 Poster: Raw Nav-merge Seismic Data to Subsurface Properties with MLP based Multi-Modal Information Unscrambler »
Aditya Desai · Zhaozhuo Xu · Menal Gupta · Anu Chandran · Antoine Vial-Aussavy · Anshumali Shrivastava -
2020 Poster: Adaptive Learned Bloom Filter (Ada-BF): Efficient Utilization of the Classifier with Application to Real-Time Information Filtering on the Web »
Zhenwei Dai · Anshumali Shrivastava -
2020 Session: Orals & Spotlights Track 03: Language/Audio Applications »
Anshumali Shrivastava · Dilek Hakkani-Tur -
2019 Poster: Fast and Accurate Stochastic Gradient Estimation »
Beidi Chen · Yingchen Xu · Anshumali Shrivastava -
2019 Poster: Extreme Classification in Log Memory using Count-Min Sketch: A Case Study of Amazon Search with 50M Products »
Tharun Kumar Reddy Medini · Qixuan Huang · Yiqiu Wang · Vijai Mohan · Anshumali Shrivastava -
2018 Poster: Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements »
Ankush Mandal · He Jiang · Anshumali Shrivastava · Vivek Sarkar -
2016 Poster: Simple and Efficient Weighted Minwise Hashing »
Anshumali Shrivastava -
2014 Poster: Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) »
Anshumali Shrivastava · Ping Li -
2014 Oral: Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) »
Anshumali Shrivastava · Ping Li -
2013 Poster: Beyond Pairwise: Provably Fast Algorithms for Approximate $k$-Way Similarity Search »
Anshumali Shrivastava · Ping Li -
2011 Poster: Hashing Algorithms for Large-Scale Learning »
Ping Li · Anshumali Shrivastava · Joshua L Moore · Arnd C König