Reservoir Sampling

Customer service का एक model उन संदेशों पर सीखता है जो एक के बाद एक आते हैं। आप उनमें से कुछ को बाद में दोहराने के लिए बचाना चाहते हैं, लेकिन memory में सिर्फ़ चार जगहें हैं। आपको यह भी नहीं पता कि अभी कितने संदेश और आएँगे: बीस या बीस लाख।

पहले चार रख लें? तब memory सिर्फ़ शुरुआत को जानती है। हमेशा आख़िरी चार रखें? तब वह सिर्फ़ अंत को जानती है। "पूरे में से चार" का निष्पक्ष यादृच्छिक चुनाव करने के लिए या तो सब कुछ सँभालकर रखना पड़ता, या संदेशों की संख्या पहले से मालूम होनी चाहिए। सवाल यह है: जगहों की संख्या तय हो और stream की लंबाई मालूम न हो, तो हर संदेश को बराबर मौक़ा कैसे दिया जाए?

Reservoir Sampling ऐसे data पर, जिसकी संख्या हमें पहले से मालूम नहीं, एक ही बार गुज़रते हुए तय आकार का यादृच्छिक नमूना बनाए रखने का तरीका है। हर नए संदेश के बाद memory में, जिसे यहाँ reservoir कहा जाता है, अब तक आई हर चीज़ का एक निष्पक्ष यादृच्छिक नमूना होता है। सबसे सरल रूप, Algorithm R, का वर्णन Vitter, Random Sampling with a Reservoir, §2 में है, जो इसका श्रेय Alan Waterman को देते हैं।

दो क़दमों का नुस्ख़ा

1. पहले चार संदेश बिना किसी यादृच्छिक चुनाव के memory में जाते हैं।
2. संदेश संख्या $t$ (पाँचवाँ, छठा और उसके बाद का हर संदेश) $4/t$ की संभावना से memory में जाता है। अगर वह गया, तो बचाए गए चार में से यादृच्छिक रूप से चुने गए किसी एक की जगह लेता है।

यानी पाँचवाँ संदेश 4/5 की संभावना से अंदर जाता है, सौवाँ 4/100 की संभावना से। नए संदेशों के अंदर जाने की संभावना घटती जाती है, लेकिन पुराने संदेश पहले ही कई बार निकाले जाने के ख़तरे से गुज़र चुके होते हैं, और ये दोनों असर एक-दूसरे को ठीक-ठीक बराबर कर देते हैं। पाँचवें संदेश के बाद इसे जाँच लेते हैं। वह 4/5 की संभावना से अंदर जाता है। पहला संदेश तभी बाहर होता है जब पाँचवाँ अंदर गया (4/5) और ठीक उसी की जगह पर पड़ा (1/4), यानी 1/5 की संभावना से। वह 4/5 की संभावना से बना रहता है: ठीक उतनी, जितनी पाँचवें की है। $t$ संदेशों के बाद उनमें से हर एक $4/t$ की संभावना से memory में होता है।

बराबर मौक़ा गारंटी नहीं है

प्रयोग में stream में 20 संदेश हैं। अठारह डिलीवरी के बारे में हैं, और दो, नौवाँ और पंद्रहवाँ, वापसी के बारे में। हर बार चलाने पर ऐसी stream 2000 बार गुज़ारी जाती है और गिना जाता है कि कोई स्थान आख़िर में कितनी बार memory में बचा। यादृच्छिक चुनाव असली हैं, इसलिए नतीजे हर बार प्रतिशत के एक अंश जितने अलग होते हैं।

Reservoir Sampling में हर bar करीब 20% का होता है, यानी 4/20। साथ ही ज़्यादातर runs में वापसी वाले दोनों संदेशों में से कोई भी memory में नहीं बचता। सटीक मान 3060/4845 है, यानी करीब 63%: 20 संदेशों में से चुने गए सभी चौकों में से इतने सिर्फ़ डिलीवरी वाले अठारह संदेशों से बने होते हैं। यह तरीका अलग-अलग संदेशों के साथ निष्पक्ष है, लेकिन इस बात का ध्यान नहीं रखता कि हर श्रेणी का कोई प्रतिनिधि मौजूद रहे।

यह कहाँ मायने रखता है

दोहराव वाली training में Reservoir Sampling कभी-कभी buffer में लिखने का तरीका होता है: न stream की लंबाई मालूम होनी चाहिए, न tasks के बीच की सीमाएँ। Chaudhry et al., Continual Learning with Tiny Episodic Memories, §2, algorithm 2 इसे ठीक इसी तरह इस्तेमाल करते हैं। Image tasks पर उनके प्रयोगों में यह अच्छा चला, सिवाय बहुत छोटी memories के, जहाँ buffer से पहले की classes ग़ायब हो जाती थीं; तब वे रणनीतियाँ बेहतर रहीं जो classes के बराबर प्रतिनिधित्व का ध्यान रखती हैं (§4.4)। यह image classification का नतीजा है, LLM का नहीं।

Algorithm अपने आप में machine learning के बारे में नहीं है। Vitter का 1985 का पेपर अनजानी लंबाई वाले magnetic tape से records के यादृच्छिक चुनाव का वर्णन करता है और तेज़ रूप सुझाता है, जो हर record पर यादृच्छिक चुनाव करने की जगह यह निकालते हैं कि कितने records छोड़ने हैं। ग्राहकों के संदेश और 20 स्थानों वाली stream हमारा अपना उदाहरण हैं।

• Experience Replay को पुराने उदाहरणों वाला buffer चाहिए; Reservoir Sampling यह तय करने के तरीकों में से एक है कि उसमें क्या जाए।
• Continual Learning सीमित memory के साथ data की stream से सीखना मानकर चलता है, यानी ऐसी स्थिति जिसमें सब कुछ बचाकर नहीं रखा जा सकता।
• Catastrophic Forgetting [Polski] तब और बढ़ सकता है जब छोटी memory से किसी पुरानी श्रेणी के सारे उदाहरण निकल जाएँ।

पाठ और चित्र AI की मदद से तैयार किए गए हैं। संदेशों की stream और demonstration सिखाने के लिए बनाया गया मेरा अपना सरल उदाहरण हैं; चित्र एक रूपक है, algorithm का आरेख नहीं।