- Reservoir Sampling เป็นเทคนิคที่มีเอกลักษณ์และมีประสิทธิภาพสำหรับการเลือก ตัวอย่างแบบสุ่ม อย่างยุติธรรมเมื่อไม่ทราบขนาดของข้อมูล
- สามารถนำไปใช้ในหลายด้าน เช่น การเก็บรวบรวมล็อกแบบเรียลไทม์ เพราะช่วยแก้ปัญหาสถานการณ์ที่วิธีดั้งเดิมไม่รองรับได้อย่างมีประสิทธิภาพ
- แนวคิดหลักคือทุกครั้งที่มี องค์ประกอบใหม่เข้ามา จะอัปเดตพื้นที่จัดเก็บด้วยความน่าจะเป็น 1/n เพื่อให้ทุกองค์ประกอบมีโอกาสถูกเลือกเท่ากัน
- หากต้องการเลือกหลายตัวอย่าง ก็ขยายความน่าจะเป็นเป็น k/n และแทนที่ตัวอย่างเดิมแบบสุ่มตามความน่าจะเป็นนั้น
- อัลกอริทึมนี้รับประกัน การสุ่มตัวอย่างอย่างยุติธรรม ได้แม้ใช้หน่วยความจำเพียงเล็กน้อย และช่วยเพิ่มประสิทธิภาพกับความน่าเชื่อถือของการประมวลผลแบบเรียลไทม์
แนวคิดและความจำเป็นของ Reservoir Sampling
- Reservoir Sampling เป็นเทคนิคที่มีประสิทธิภาพสำหรับการดึงตัวอย่างอย่างยุติธรรมจากชุดข้อมูลที่ไม่ทราบขนาดทั้งหมด
- โดยทั่วไป หากรู้ขนาดข้อมูลอยู่แล้ว การสุ่มดัชนีจะเป็นวิธีที่มีประสิทธิภาพ แต่ถ้าไม่รู้ขนาด วิธีนี้จะใช้ไม่ได้
- ในข้อมูลปริมาณมากที่เข้ามาแบบลำดับต่อเนื่อง (เช่น สตรีมล็อก) จำเป็นต้องจำกัดการใช้หน่วยความจำ ขณะเดียวกันก็ต้องให้ข้อมูลแต่ละรายการมีโอกาสถูกเลือกเท่ากัน
การสุ่มตัวอย่างในกรณีที่รู้ขนาด
- ในชุดข้อมูลที่มีขนาดจำกัด (เช่น ไพ่ 10 ใบ) วิธี shuffle โดยสับทุกองค์ประกอบแล้วเลือกจากด้านหน้าตามจำนวนที่ต้องการ เหมาะสำหรับการรับประกันความยุติธรรม
- หากใช้โครงสร้าง array ของคอมพิวเตอร์ ก็สามารถเลือกดัชนีแบบสุ่มได้โดยตรงเพื่อดึงตัวอย่างอย่างรวดเร็ว
- แต่ในทางปฏิบัติ วิธีนี้ไม่มีประสิทธิภาพเมื่อข้อมูลมีจำนวนหลายล้านรายการหรือเป็นสตรีมที่ไม่รู้ขนาด
การสุ่มตัวอย่างในกรณีที่ไม่รู้ขนาด: ปัญหาและความจำเป็น
- ในความเป็นจริง มักมีสถานการณ์ที่รับข้อมูลเข้ามาทีละ 1 รายการ เก็บไว้ได้เพียง 1 รายการ และไม่สามารถย้อนกลับไปดูข้อมูลที่ผ่านไปแล้วได้
- ในระบบเก็บรวบรวมล็อก อาจเกิดทราฟฟิกพุ่งสูงขึ้นอย่างกะทันหัน ทำให้จำเป็นต้องส่งไปเพียงบางส่วนเพื่อป้องกัน เซิร์ฟเวอร์โอเวอร์โหลด
- วิธีที่เลือกแค่ข้อมูลช่วงแรกแบบตามใจชอบจะไม่ให้โอกาสเท่ากันกับทุกรายการ จึงทำให้เกิดปัญหาขาด ความยุติธรรม
หลักการของอัลกอริทึม Reservoir Sampling
- ทุกครั้งที่ข้อมูลใหม่เข้ามา ให้คำนวณจำนวนรายการที่รับมาจนถึงตอนนั้นเป็น n แล้วกำหนดให้ข้อมูลใหม่ถูกเลือกด้วยความน่าจะเป็น 1/n
- ข้อมูลรายการแรกจะถูกเลือกเสมอ และหลังจากนั้นข้อมูลใหม่แต่ละรายการจะเข้ามาแทนข้อมูลเดิมด้วยความน่าจะเป็นที่ค่อย ๆ ลดลง เพื่อรักษา ความน่าจะเป็นในการถูกเลือกให้เท่ากัน
- เมื่อจบกระบวนการ ข้อมูลที่ถูกเก็บไว้สุดท้ายจะมีโอกาสเป็นรายการใดก็ได้ในทั้งหมดอย่างเท่าเทียม
- ไม่ได้ใช้วิธีโยนเหรียญ แต่ใช้ความน่าจะเป็น 1/n เพื่อ รับประกันว่าแต่ละข้อมูลมีโอกาสอย่างยุติธรรม
สัญชาตญาณทางคณิตศาสตร์ (อธิบายด้วยตัวอย่างไพ่)
- ข้อมูลลำดับที่ 1: ถูกเลือกแน่นอน (ความน่าจะเป็น 1/1)
- ข้อมูลลำดับที่ 2: ถูกเลือกด้วยความน่าจะเป็น 1/2 ส่วนข้อมูลเดิมจะเหลืออยู่ด้วยความน่าจะเป็น 50%
- ข้อมูลลำดับที่ 3: ข้อมูลใหม่ถูกเลือกด้วย 1/3 ส่วนข้อมูลเดิมจะมีความน่าจะเป็นรอดสะสมตามค่าที่เหลือจากความน่าจะเป็นนั้น
- เมื่อนำไปสู่กรณีทั่วไป จนถึงข้อมูลลำดับที่ n ข้อมูลทุกตัวจะมีความน่าจะเป็น 1/n เท่ากันเสมอ
การขยายไปสู่การเลือกหลายตัวอย่าง (k-out-of-n)
- หากต้องการเลือกตัวอย่าง k รายการ ให้ ข้อมูลใหม่มีโอกาสถูกเลือกเป็น k/n และเมื่อถูกเลือก ก็แทนที่หนึ่งในรายการที่เก็บไว้ปัจจุบันแบบสุ่ม
- วิธีนี้ยังคงทำให้ทุกข้อมูลที่ถูกเก็บมีโอกาสเหลืออยู่ในตัวอย่างเท่ากัน
- สามารถดึงหลายตัวอย่างจากสตรีมข้อมูลขนาดใหญ่ได้อย่างยุติธรรม โดย ใช้หน่วยความจำคงที่เพียงเท่ากับ k
การนำ Reservoir Sampling ไปใช้ในบริการเก็บรวบรวมล็อก
- จากล็อกที่ไหลเข้ามาทุกวินาที ให้เลือกได้สูงสุด k รายการ (เช่น 5 รายการ) ด้วยเทคนิค Reservoir Sampling แล้วส่งเฉพาะตัวอย่างเหล่านั้นไปยังเซิร์ฟเวอร์
- เมื่อข้อมูลมีน้อย ล็อกทั้งหมดจะถูกส่งโดยไม่เกิดการสูญหาย และแม้ทราฟฟิกจะพุ่งสูง ก็จะไม่ส่งเกิน k รายการ จึงช่วย รับประกันเสถียรภาพของบริการ
- การส่งตัวอย่างเป็นช่วงเวลาสม่ำเสมออาจมี ดีเลย์ เล็กน้อยในแง่ความเป็นเรียลไทม์ แต่โดยรวมช่วยด้านเสถียรภาพและความคุ้มค่าด้านต้นทุนได้
การประยุกต์เพิ่มเติมและแหล่งข้อมูลอ้างอิง
- หากข้อมูลบางประเภท (เช่น error log) สำคัญกว่าประเภทอื่น ก็สามารถใช้รูปแบบ Weighted Reservoir Sampling ที่ใส่น้ำหนักได้
- แนวคิดเชิงลึกมีอธิบายอยู่ในแหล่งข้อมูลภายนอกอย่าง Wikipedia แต่หลักการพื้นฐานยังคงเป็นการรักษาความยุติธรรม
บทสรุป
- Reservoir Sampling เป็น อัลกอริทึมที่ทั้งสวยงามและใช้งานได้จริง สำหรับการสุ่มตัวอย่างอย่างยุติธรรมจาก สตรีมข้อมูลที่ไม่รู้ขนาด โดยใช้หน่วยความจำอย่างมีประสิทธิภาพ
- ด้วยข้อดีด้านความรวดเร็ว ความสม่ำเสมอ และการใช้ทรัพยากรต่ำในการประมวลผลข้อมูลแบบเรียลไทม์ จึงมีคุณค่าในการประยุกต์ใช้ในหลายสาขา
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ตอนเด็ก ๆ ผมเคยอยู่ชนบท และเพื่อนของพ่อคนหนึ่งมีหน้าที่ต้องวัดจำนวนประชากรของ ptarmigan (ไก่ป่าหิมะ) ในภูเขาทุกปีในฐานะงานอาชีพ
วิธีการคือเดินตามเส้นทางที่กำหนดไว้ แล้วทำให้นกตกใจบินขึ้นเป็นระยะ ๆ ตามช่วงเวลา จากนั้นก็นับจำนวน
แล้วส่งตัวเลขนั้นให้สำนักงานที่รับผิดชอบ ซึ่งจะนำไปใช้ประมาณจำนวนประชากรทั้งหมด
ปีหนึ่งเพื่อนคนนั้นอยู่ต่างประเทศ เลยอธิบายวิธีการอย่างละเอียดให้เพื่อนอีกคนช่วยทำแทน
แต่พอถึงวันสำรวจจริง เพื่อนคนนั้นกลับลืมไปเสียสนิท และเพราะมันยุ่งยากจึงส่งตัวเลขที่แต่งขึ้นแบบพอดูน่าเชื่อถือไป
ปีถัดมาหนังสือพิมพ์ท้องถิ่นขึ้นพาดหัวหน้า 1 ว่า “จำนวน ptarmigan เพิ่มขึ้นเป็นประวัติการณ์”
ที่การเปลี่ยนแปลงฉับพลันแบบนี้กลายเป็นข่าวก็เพราะตัวเลขนี้ถูกใช้เป็นเกณฑ์ในการออกใบอนุญาตล่าสัตว์ แต่เพื่อนคนนั้นไม่ได้คิดถึงเรื่องนี้
ก่อนหน้านี้ผมเคยทำงานกับระบบจองของสกีรีสอร์ตขนาดใหญ่ และต้องปิดรายงานสถิติอย่างเป็นทางการเพื่อส่งภาครัฐ (เช่น จำนวน guest nights)
ตอนนั้นเวลาไม่พอจนต้องทำงานทั้งคืน และข้อมูลสถิติของปีนั้นก็แตกต่างจากค่าจริงมาก
สวัสดีครับ! o/
ผมคือผู้เขียนบทความนี้เอง ยินดีรับคำถามหรือฟีดแบ็กครับ
โค้ดของทุกโพสต์เปิดให้ใช้ภายใต้สัญญาอนุญาต MIT ที่ https://github.com/samwho/visualisations ใช้ได้ตามสบายครับ
ผมคิดว่าเป็นโพสต์ที่ดีมาก
ในอีกแนวทางหนึ่งของการเพิ่มประสิทธิภาพ Reservoir sampling แทนที่จะสุ่มทุกครั้งเพื่อตรวจว่าแต่ละไอเท็มจะถูกแทนที่หรือไม่ ก็สามารถสุ่มจำนวนที่ต้องข้ามจากการแจกแจงแบบ Geometric ได้
น่าสนใจมากเวลาเจอสื่ออย่าง tape drive ที่ข้ามหลายรายการได้ในต้นทุนต่ำ (แม้จะไม่รู้ความยาวเทปล่วงหน้า แต่ระหว่างข้ามก็ปล่อยให้ระบบส่วนใหญ่อยู่ในโหมดสลีปได้)
ถ้าจะสุ่มตัวอย่าง k ชิ้นจากทั้งหมด n ชิ้น จะต้องสุ่มและข้ามเพียงประมาณ O(k * log(n/k)) ครั้ง
อีกแนวคิดที่ผมชอบคือให้ลำดับความสำคัญแบบสุ่มกับการ์ดแต่ละใบเมื่อมาถึง แล้วเก็บเฉพาะ k อันดับบนสุดไว้
ปัญหาที่เกี่ยวข้องกันคือการเลือกเฉพาะ k ไอเท็มบนสุดจากสตรีมที่ไม่รู้ความยาว โดยใช้เวลา O(n) และพื้นที่ O(k)
วิธีคือใส่ทุกอย่างลงในบัฟเฟอร์แบบไม่เรียงขนาด 2*k และเมื่อเต็มก็ใช้ randomized quickselect หรือ median-of-medians เพื่อตัดให้เหลือเฉพาะ k อันดับบนสุด
ทำแบบนี้ครบ n ครั้งก็ใช้เวลา O(n)
อีกเทคนิคที่เกี่ยวข้องและน่าสนใจก็คือ rendezvous hashing
และถ้าสนใจ alias method บทความนี้ช่วยได้: https://www.keithschwarz.com/darts-dice-coins/
สงสัยว่าวิธีนี้สามารถนำไปซ้อนกันได้ไหม
เช่น ถ้าผมทำ reservoir sampling ในบริการของผม แล้วบริการเก็บ log ก็ทำ reservoir sampling อีกชั้นหนึ่ง ผลจะเท่ากับใช้เฉพาะตัวเก็บ log เพียงชั้นเดียวหรือเปล่า
ผมชอบแอนิเมชันและคำอธิบายมากเป็นพิเศษ
โดยเฉพาะการโต้ตอบอย่างการสับ 100 ครั้งในกราฟนั้นน่าประทับใจมาก
ตอนแรกผมงงนิดหน่อยตรงที่เริ่มจากการเลือก 3 ใบจาก 10 ใบหรือ 436,234 ใบ แล้วอยู่ ๆ ก็เปลี่ยนไปเป็นตัวอย่างที่ดูทีละ 1 ใบและเลือกเพียง 1 ใบ
ตรงช่วง “ตอนนี้เราจะโยนโค้งเข้าไป!” ถ้ามีตัวคั่นส่วนสักอันน่าจะช่วยให้เข้าใจง่ายขึ้น
ตอนนี้เรากำลังสมมติว่าเราถือไพ่ไว้แค่ 1 ใบ และไม่รู้ขนาดของสำรับด้วย
ผมชอบดีไซน์ของเว็บมากเป็นพิเศษ
ทั้งการโต้ตอบ ตัวละครสุนัข ฟอนต์ โทนสี และเลย์เอาต์โดยรวม ล้วนดีมาก
ทั้งบล็อกให้ความรู้สึกเหมือนขุมทรัพย์
ดีใจที่ได้ค้นพบ
ผมชอบกราฟิกมาก
แต่ยังไม่แน่ใจว่าวิธีนี้มีความถูกต้องทางสถิติอย่างสมบูรณ์หรือไม่ แม้ log ทั้งหมดในช่วงเวลาหนึ่งจะมีโอกาสถูกเลือกเท่ากัน แต่ผมกังวลว่า log ที่เกิดใน “ช่วงช้า” อาจถูกเก็บมากเกินจริงในสถิติรวม
ตัวอย่างเช่น ถ้าต้องการหา endpoint ที่ใช้ CPU มากที่สุดในทั้งระบบเพื่อจะได้ปรับปรุงให้ดีขึ้น log ของ endpoint ที่ทราฟฟิกพุ่งสูงชั่วคราวอาจถูกเก็บน้อยเกินไป จนประเมินผิดว่า endpoint ไหนถูกใช้งานมากที่สุดจริง ๆ หรือเปล่า
หรือในงานวางแผนความจุแยกตามบริการ ก็รู้สึกว่าบริการที่มี burst traffic น่าจะถูกแทนค่าน้อยเกินจริง
เลยอยากรู้ว่า Reservoir sampling เหมาะกับงานแบบไหน และการวิเคราะห์ทางสถิติประเภทใดที่ทำได้ด้วยวิธีนี้
เป็นบทความที่ดีมาก คณิตศาสตร์หรือสถิติควรถูกสอนแบบนี้ถึงจะเรียนได้สนุก
มันให้ความรู้สึกคล้าย https://distill.pub/
ประโยค “Sometimes the hand of fate must be forced” สะดุดใจมาก
ผมชอบวิธีการโต้ตอบมากเป็นพิเศษ
ผมคิดว่าดีไซน์เว็บไซต์และวิธีการสอนนั้นงดงามมาก ขอบคุณจริง ๆ
สงสัยว่าบล็อกนี้มี RSS feed ไหม
เป็นโพสต์ที่ชัดเจนมากและมีภาพประกอบดีเยี่ยม
ถ้าจะต่อยอดไปขั้นสูงกว่านี้ ก็ยังมีอัลกอริทึมที่คำนวณจำนวนที่จะข้ามทีละหลายรายการ แทนวิธีพื้นฐานด้วย
รายละเอียดดูได้ที่ https://richardstartin.github.io/posts/reservoir-sampling
บทความและคำอธิบายดีมาก
สำหรับการเก็บ log จริง ผมแนะนำให้ลองหลายวิธีก่อน แล้วค่อยใช้ความเป็นธรรม (fairness) เป็นทางเลือกสุดท้าย
เช่น กำหนดลำดับความสำคัญของ log แล้วทิ้ง log ที่ priority ต่ำกว่า (หรือมี verbosity สูงกว่า) ก่อน
log ที่รวมกันเป็นกิจกรรมเดียวกันในเชิงความหมาย ก็ควรลด log ซ้ำระหว่างทาง และเก็บไว้เฉพาะจุดเริ่ม จุดจบ และการเปลี่ยนสถานะสำคัญ
ถ้าเอา log ที่คล้ายกันหรือซ้ำกันมาสรุปรวมแล้วเก็บเป็นสรุป ก็จะช่วยลดปริมาณรวมและทำให้ดูเทรนด์ได้ง่ายขึ้น
ช่วงนี้ผมกำลังศึกษาเรื่อง observability เยอะพอสมควร วิธีที่พูดถึงนี้คือแนวผสมระหว่าง head/tail sampling
ดูคำอธิบายเพิ่มเติมได้ที่ https://docs.honeycomb.io/manage-data-volume/sample/
ในบทความก็พูดถึงส่วนนี้เหมือนกัน
จริง ๆ แล้วแทนที่จะทิ้ง log priority ต่ำทั้งหมด สิ่งสำคัญคือการใช้แนวคิดเรื่อง “งบประมาณ” เพื่อจำกัดปริมาณ
จำนวน log ทั้งหมดก็สามารถถูกจำกัดด้วยงบประมาณระดับบนอีกชั้นหนึ่งได้
Reservoir sampling จัดการข้อจำกัดแบบนี้ได้ดีเช่นกัน
บทความและคำอธิบายดีมาก
ในงานวิจัยของ Vitter มีการอธิบาย “Algorithm R” ซึ่งเป็นวิธีแบบ reservoir sampling
อ่านได้ที่ https://www.cs.umd.edu/~samir/498/vitter.pdf
งานวิจัยก่อนหน้าของ Vitter ที่ https://dl.acm.org/doi/10.1145/358105.893 อ้างอิง Knuth TAOCP เล่ม 2 แต่ Knuth เองก็ไม่ได้ให้ที่มาชัดเจนเช่นกัน
เรียบเรียงได้ดีมาก และถ้าสนใจ weighted reservoir sampling ก็มีคำอธิบายที่ https://gregable.com/2007/10/reservoir-sampling.html
ยังมีวิธีที่นำไปใช้กับสภาพแวดล้อมแบบกระจายด้วย map-reduce ได้ง่าย และมีวิธีที่ง่ายมากคือจับคู่แต่ละไอเท็มกับค่าสุ่มแล้วเก็บ Top N ไว้
วิธีพื้นฐานที่ให้สุ่มลำดับความสำคัญของแต่ละไอเท็มด้วย POW(RANDOM(), 1.0 / weight) แล้วเลือก Top N นั้น จะมีปัญหาเรื่องเสถียรภาพเชิงตัวเลขเมื่อค่า weight ใหญ่มากหรือเล็กมาก
อีกทั้งผลลัพธ์ที่ได้อาจไม่ได้สะท้อนการกระจายของประชากรทั้งหมดเดิมอย่างเพียงพอ โดยเฉพาะเมื่อ weight ส่วนใหญ่กระจุกอยู่กับไอเท็มจำนวนน้อย
ถึงอย่างนั้น ในสถานการณ์ส่วนใหญ่ก็ยังถือว่าเป็นการประมาณที่ดีพอ
รายละเอียดดูได้ที่ https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
บทความนี้ทำให้ผมนึกถึงวิธีที่ฝ่ายสัมพันธมิตรในสงครามโลกครั้งที่ 2 ใช้อนุมานจำนวนการผลิตรถถังเยอรมันจากหมายเลขซีเรียล
ตอนนั้นเจ้าหน้าที่ภาคสนามประเมินว่าสูงกว่าความจริงราว 5 เท่า แต่การใช้หมายเลขซีเรียลให้ความแม่นยำเกิน 90%
เป็นโพสต์ที่ยอดเยี่ยม และงานภาพก็น่าประทับใจมาก
ในระบบจริง เราใช้รูปแบบดัดแปลงที่คล้ายกันเพื่อประมาณค่า percentile ที่เปลี่ยนแปลงอยู่ตลอดแบบเรียลไทม์จากสตรีมขนาดใหญ่มาก
ค่า percentile จะเปลี่ยนเป็นครั้งคราว แต่โดยมากจะคงอยู่เป็นเวลานานมากในหลายรอบซ้ำ ข้อมูลพื้นฐานมีลักษณะ quasi-stationary
หากใช้ splay tree เป็นตัวช่วยสำรอง ก็จะประมาณได้ในเวลา Amortized O(1) แม้ช่วงความคลาดเคลื่อนต่อ RAM จะกว้างกว่าวิธีอื่น
และยังปรับความน่าจะเป็นในการแทนที่เพื่อกำหนด ‘half-life’ ของข้อมูลได้ด้วย กล่าวคือทำให้ค่าประมาณเอนเอียงไปทางข้อมูลใหม่มากขึ้น
จากมุมมองของ data science ผมคิดว่าปริมาณข้อมูลเองก็เป็นข้อมูลสำคัญ ดังนั้นควรบันทึกอัตราการสุ่มตัวอย่างไว้เสมอ
เช่น ถ้า sampling rate คือ 10% ก็ให้บันทึกค่า 10 ไว้กับแต่ละตัวอย่าง เพื่อให้สามารถกู้คืนและประมาณค่ารวม ผลรวม หรือค่าเฉลี่ยได้อย่างถูกต้อง
โพสต์นี้แสดงให้เห็น trade-off ของการเก็บ telemetry (trace, log, metrics) ได้ดีมาก
งานวิเคราะห์ข้อมูลลักษณะนี้มีอุปสรรคในการเข้าถึงสูง และเป็นพื้นที่ที่นักพัฒนาจำนวนมากมักมองข้าม
ข้อมูลที่ดูเหมือนกันอาจให้กราฟที่สังเกตเห็นต่างกันโดยสิ้นเชิงขึ้นอยู่กับว่าสุ่มตัวอย่างอย่างไร และหลายคนก็มองข้ามประเด็นนี้