วิทยาศาสตร์เป็นสิ่งที่ดีสำหรับนวัตกรรมและปรับปรุงชีวิตของเรา แต่ยอมรับเถอะ มีบางสิ่งที่เราค่อนข้างจะผิดหวัง เช่น คุณคงไม่คาดหวังว่าเราจะสามารถปรับปรุงบางอย่างอย่างเช่น... เช่น การนับได้
ดังนั้นจึงเป็นเรื่องน่าประหลาดใจที่นักวิทยาศาสตร์คอมพิวเตอร์กลุ่มหนึ่งได้ทำสิ่งนั้น: พบวิธีใหม่ในการแก้ปัญหาเก่าแก่หลายทศวรรษที่ถามว่าเมื่อมองดูภายนอกแล้ว ดูเหมือนจะเป็นปัญหาธรรมดามาก – มีกี่ข้อที่แตกต่างกันออกไป ข้างหน้าฉันมีของอยู่เหรอ?
มันเป็นปัญหาที่ยากกว่า – และเป็นวิธีแก้ปัญหาที่ชาญฉลาดกว่า – มากกว่าที่คุณคิด
ปัญหาองค์ประกอบที่แตกต่าง
คอมพิวเตอร์สามารถฉลาดมากได้ แต่ก็สามารถ... ไม่ฉลาดมากเช่นกัน เพียงดูการระเบิดของแชทบอท AI เมื่อเร็ว ๆ นี้เพื่อดูหลักฐานว่าพวกมันเป็นเช่นนั้นยอดเยี่ยมในการฟังดูฉลาดแต่นำพวกเขาไปทดสอบและคุณอาจจะแค่พบตัวคุณเองในouroboros ของเรื่องไร้สาระ-
และบางครั้งสิ่งที่ดูเหมือนง่ายจนแทบจะน่าหัวเราะสำหรับมนุษย์นี่แหละที่ทำให้เกิดปัญหามากที่สุด ยกตัวอย่างเช่น การนับ โดยเฉพาะการนับวัตถุที่แตกต่างกัน สำหรับเรา มันง่ายมาก เราดูที่การสะสมของวัตถุ และสมองของเราจะจัดเรียงมันออกเป็นกลุ่มโดยอัตโนมัติให้เรา เราแทบจะไม่ต้องทำงานเลย
ในทางกลับกัน สำหรับคอมพิวเตอร์ มันเป็นปัญหาพื้นฐานที่มีมานานหลายทศวรรษ และเป็นสิ่งที่จำเป็นต้องได้รับคำตอบจริงๆ เนื่องจากการใช้งานในโลกสมัยใหม่ครอบคลุมทุกอย่างตั้งแต่การวิเคราะห์การรับส่งข้อมูลเครือข่าย ลองนึกถึง Facebook หรือ Twitter ที่คอยติดตามจำนวนคนที่เข้าสู่ระบบในช่วงเวลาใดก็ตาม ไปจนถึงการตรวจจับการฉ้อโกง ชีวสารสนเทศศาสตร์ ไปจนถึงการวิเคราะห์ข้อความ และอีกมากมาย
เห็นได้ชัดว่า ตอนนี้เราสามารถทำสิ่งเหล่านั้นได้มาระยะหนึ่งแล้ว และนั่นเป็นเพราะคำถามนับนี้ – ที่รู้จักกันในนามปัญหาองค์ประกอบที่แตกต่าง – มีคำตอบ พวกเขาไม่ใช่คนดีมากนัก
“อัลกอริธึมที่รู้จักก่อนหน้านี้ทั้งหมดเป็นแบบ 'การแฮช' และคุณภาพของอัลกอริธึมนั้นขึ้นอยู่กับคุณภาพของฟังก์ชันแฮชที่อัลกอริธึมเลือก” Vinodchandran Variyam ศาสตราจารย์จาก University of Nebraska–Lincoln's School of Computing อธิบายในคำแถลงปีที่แล้ว
แต่ร่วมกับเพื่อนร่วมงาน Sourav Chakraborty จาก Indian Statistical Institute และ Kuldeep Meel จากมหาวิทยาลัยโตรอนโต เขาได้ค้นพบวิธีที่จะทำให้ปัญหาง่ายขึ้นอย่างมาก: “อัลกอริทึมใหม่ใช้กลยุทธ์การสุ่มตัวอย่างเท่านั้น และการวิเคราะห์คุณภาพสามารถทำได้โดยใช้เทคนิคเบื้องต้น ”
มันทำงานอย่างไร?
วิธีการใหม่นี้ นับตั้งแต่ตั้งชื่ออัลกอริธึม CVM เพื่อเป็นเกียรติแก่นักประดิษฐ์ ช่วยลดความต้องการหน่วยความจำลงอย่างมาก ซึ่งเป็นข้อได้เปรียบที่สำคัญในยุคข้อมูลขนาดใหญ่ยุคใหม่นี้ และใช้วิธีการดังกล่าวโดยใช้กลอุบายของทฤษฎีความน่าจะเป็น เพื่ออธิบายแนวคิดนี้ ให้พิจารณาตัวอย่างที่ศึกษาโดยวาริยามและเพื่อนร่วมงานของเขา เช่นเดียวกับบทความล่าสุดในนิตยสารควอนต้า: ลองจินตนาการว่าคุณกำลังนับจำนวนคำที่ไม่ซ้ำกันในเช็คสเปียร์แฮมเล็ตแต่คุณมีหน่วยความจำเพียงพอที่จะจัดเก็บได้ครั้งละ 100 คำเท่านั้น
ขั้นแรก คุณทำสิ่งที่ชัดเจน: คุณบันทึกคำศัพท์ที่ไม่ซ้ำกัน 100 คำแรกที่คุณเจอ ตอนนี้คุณไม่มีที่ว่างแล้ว ดังนั้นคุณจึงหยิบเหรียญและพลิกมันสำหรับแต่ละคำ หัวหน้า มันยังคงอยู่; ก้อย คุณลืมมันซะ
เมื่อสิ้นสุดกระบวนการนี้ คุณจะมีคำที่ไม่ซ้ำกันประมาณ 50 คำในรายการของคุณ คุณเริ่มกระบวนการใหม่จากเมื่อก่อน แต่คราวนี้ ถ้าคุณเจอคำที่อยู่ในรายการแล้ว คุณจะพลิกเหรียญอีกครั้งเพื่อดูว่าจะลบมันหรือไม่ เมื่อคุณมีคำศัพท์ครบ 100 คำแล้ว คุณจะต้องดูรายการอีกครั้ง โดยพลิกเหรียญสำหรับแต่ละคำ แล้วลบหรือเก็บคำนั้นไว้ตามที่ได้รับแจ้ง
ในรอบที่สอง สิ่งต่างๆ จะซับซ้อนขึ้นเล็กน้อย แทนที่จะมีหัวเดียวเพื่อเก็บคำไว้ในรายการ คุณจะต้องมีสองหัวติดต่อกัน อย่างอื่นเป็นอย่างอื่น จากนั้นคำนั้นก็จะถูกลบทิ้งไป ในทำนองเดียวกัน ในรอบที่สาม คุณจะต้องได้หัวสามตัวติดต่อกันเพื่อให้มันอยู่ได้ รอบที่สี่จะต้องมีสี่ครั้งติดต่อกัน และต่อไปเรื่อยๆ จนกว่าจะถึงจุดสิ้นสุดของหมู่บ้านแฮมเล็ต
ความบ้าคลั่งมีวิธีต่างๆ และมันก็เป็นวิธีที่ฉลาดเช่นกัน เมื่อพิจารณาข้อความเช่นนี้ คุณมั่นใจได้ว่าทุกคำในรายการมีความน่าจะเป็นเท่ากัน: 1/2เค, ที่ไหนเคคือจำนวนครั้งที่คุณต้องทำงานผ่านรายการ สมมติว่าคุณต้องใช้เวลาหกรอบกว่าจะถึงจุดสิ้นสุดของ Hamlet และคุณเหลือรายการคำศัพท์ที่แตกต่างกัน 61 คำ จากนั้นคุณสามารถคูณ 61 ด้วย 2 ได้6เพื่อจะได้ประมาณจำนวนคำ
เราจะช่วยคุณประหยัดเวลาในการเปิดแอปเครื่องคิดเลข คำตอบคือ 3,904 และจากข้อมูลของ Variyam and co คำตอบที่แท้จริงคือ 3,967 (ใช่ นับไว้ด้วย) หากคุณมีหน่วยความจำที่สามารถเก็บคำศัพท์ได้มากกว่า 100 คำ ความแม่นยำก็จะเป็นไป ยิ่งไปกว่านั้น ด้วยความสามารถในการจัดเก็บคำได้ 1,000 คำ อัลกอริธึมจึงประมาณคำตอบไว้ที่ 3,964 ซึ่งแทบจะไม่เป็นข้อผิดพลาดในการปัดเศษเลย และ “แน่นอน” วาริยามบอกกับ Quanta “ถ้า [หน่วยความจำ] มีขนาดใหญ่มากจนพอดีกับคำศัพท์ทั้งหมด เราก็จะได้รับความแม่นยำ 100 เปอร์เซ็นต์”
วิธีการง่ายๆ
ดังนั้นจึงมีประสิทธิภาพ แต่สิ่งที่ทำให้อัลกอริธึมน่าสนใจยิ่งขึ้นก็คือความเรียบง่าย “อัลกอริธึมใหม่นี้เรียบง่ายอย่างน่าอัศจรรย์และใช้งานง่าย” Andrew McGregor ศาสตราจารย์ในวิทยาลัยสารสนเทศและวิทยาการคอมพิวเตอร์จากมหาวิทยาลัยแมสซาชูเซตส์ แอมเฮิร์สต์ กล่าวกับ Quanta “ฉันจะไม่แปลกใจถ้านี่กลายเป็นวิธีเริ่มต้นในการแก้ไขปัญหา [องค์ประกอบที่แตกต่าง] ในทางปฏิบัติ”
อันที่จริง นับตั้งแต่โพสต์ในเดือนมกราคม 2023 และในระหว่างนี้ ยกเว้นเรื่องเล่นๆ และข้อบกพร่องเล็กๆ น้อยๆ เล็กน้อย อัลกอริทึมดังกล่าวได้รับความสนใจและชื่นชมจากนักวิทยาศาสตร์คอมพิวเตอร์คนอื่นๆ มากมาย นั่นหมายความว่าในขณะที่กระดาษไม่มีรายละเอียดเกี่ยวกับอัลกอริทึม ได้รับการตรวจทานโดยผู้ทรงคุณวุฒิในความหมายอย่างเป็นทางการ และได้รับการตรวจทานโดยผู้ทรงคุณวุฒิอย่างแน่นอน อันที่จริง โดนัลด์ คนุธ ผู้เขียนศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์และสิ่งที่เรียกว่า “บิดาแห่งการวิเคราะห์อัลกอริธึม” เขียนไว้บทความยกย่องอัลกอริธึมย้อนกลับไปในเดือนพฤษภาคม 2023: “นับตั้งแต่ฉันเห็นมัน […] ฉันไม่สามารถต้านทานการพยายามอธิบายแนวคิดนี้ให้ทุกคนที่ฉันพบรู้จัก” เขาแสดงความคิดเห็น
ในขณะเดียวกัน ทีมงานต่างๆ เช่น Chakraborty, Variyam และ Meel ได้ใช้เวลาในปีที่แล้วเพื่อตรวจสอบและปรับแต่งอัลกอริทึม Variyam กล่าวว่าบางคนกำลังสอนเรื่องนี้ในหลักสูตรวิทยาการคอมพิวเตอร์อยู่แล้ว
“เราเชื่อว่านี่จะเป็นอัลกอริธึมกระแสหลักที่ได้รับการสอนในหลักสูตรวิทยาการคอมพิวเตอร์หลักสูตรแรกเกี่ยวกับอัลกอริธึมทั่วไปและอัลกอริธึมความน่าจะเป็นโดยเฉพาะ” เขากล่าว Knuth เห็นด้วย: "เหมาะอย่างยิ่งสำหรับการสอนนักเรียนที่กำลังเรียนรู้พื้นฐานของวิทยาการคอมพิวเตอร์" เขาเขียนในรายงานประจำเดือนพฤษภาคม “ฉันค่อนข้างแน่ใจว่าเรื่องแบบนี้จะกลายเป็นหัวข้อในหนังสือเรียนมาตรฐานในที่สุด”
แล้วอัลกอริธึมที่ก้าวหน้าเช่นนี้หลบเลี่ยงการแจ้งเตือนมานานได้อย่างไร? ตามคำกล่าวของ Variyam มันไม่น่าเป็นไปได้อย่างที่คิด
“น่าแปลกใจที่อัลกอริธึมง่ายๆ นี้ไม่เคยถูกค้นพบมาก่อน” เขากล่าว “ไม่ใช่เรื่องแปลกในทางวิทยาศาสตร์ที่ความเรียบง่ายหายไปหลายปี”
กระดาษถูกโพสต์บนอาร์เอ็กซ์และปรากฏในรายงานการประชุมครั้งที่ 30ไทยการประชุมวิชาการยุโรปประจำปีเกี่ยวกับอัลกอริทึม (ESA 2022)
