สัปดาห์ที่แล้ว GPT-5.6 และ Claude Fable ดูเหมือนว่าจะสามารถตอบคำถามเชิงทฤษฎีที่ยังไม่มีคำตอบในสาขาการสื่อสารไร้สาย ซึ่งเป็นคำถามที่มีการศึกษาอย่างเข้มข้นตั้งแต่ปี 2000 ถึงช่วงทศวรรษ 2010 และผมเคยทำงานเกี่ยวกับมันช่วงสั้น ๆ ตอนเป็นนักศึกษาปริญญาเอกปีแรกที่เต็มไปด้วยความกังวล คำตอบมาถึงในที่สุด บางทีอาจเป็นเพราะผมเป็นหนึ่งในไม่กี่คนสุดท้ายที่ถามคำถามนี้ และเป็นคนแรกที่สั่งให้เครื่องจักรแก้มัน 😊
ผลลัพธ์: คุณส่ง N บิตผ่านช่องสัญญาณไร้สายแบบเกาส์เซียนขนาด N×N และผู้รับต้องกู้คืน ทั้งหมด ให้ถูกต้องแม่นยำ เป็นที่รู้จักกันมาตั้งแต่ยุค 2000 ว่ามีความเป็นไปได้ในเชิงทฤษฎีสารสนเทศที่จะทำได้เมื่ออัตราส่วนสัญญาณต่อสัญญาณรบกวนอย่างน้อย 2 log N แต่วิธีเดียวที่รู้จักในการไปถึงจุดนั้นคืออัลกอริทึมการค้นหาแบบเอ็กซ์โปเนนเชียล ตอนนี้มีบทพิสูจน์แล้วว่าอัลกอริทึมแบบง่ายที่ใช้เวลาพหุนามประสบความสำเร็จที่ เกณฑ์เดียวกันเป๊ะ
ให้ผมเล่าเพิ่มเติมอีกนิดเกี่ยวกับเรื่องนี้
ในปี 2009 ผมทำงานในงานวิจัยชิ้นแรกกับ Alex Dimakis (@AlexGDimakis) ซึ่งไม่นานหลังจากนั้นก็กลายเป็นที่ปรึกษาปริญญาเอกของผม (ไม่ใช่เพราะงานวิจัยชิ้นนั้นนะ):
งานวิจัยชิ้นนั้นเป็นหนึ่งในความพยายามมากมายที่จะเสนอวิธีแก้ปัญหาแบบพหุนามสำหรับการตรวจจับ MIMO
คุณอาจถามว่า MIMO detection คืออะไร?
เครื่องส่งส่งเวกเตอร์ของบิต N ตัวผ่านช่องสัญญาณไร้สายที่มีเสาอากาศส่ง N ตัวและรับ N ตัว ช่องสัญญาณจะผสมบิตทั้งหมดเข้าด้วยกันและเพิ่มสัญญาณรบกวน ผู้รับซึ่งรู้เมทริกซ์ช่องสัญญาณต้องหาว่าบิตใดถูกส่งไป
ตัวรับที่เหมาะที่สุดในแง่ความคลาดเคลื่อนแบบบล็อก หรือที่รู้จักกันว่า ตัวตรวจจับแบบ maximum likelihood (ML) แก้ปัญหานี้ได้อย่างแม่นยำโดยหาเวกเตอร์ที่เป็นไปได้มากที่สุดที่อาจถูกส่งออกมา เมื่อกำหนดสัญญาณที่ได้รับ ในกรณีนี้ การตรวจจับแบบ ML ลดรูปเป็นการแก้ปัญหากำลังสองน้อยที่สุดแบบไม่ต่อเนื่องพื้นฐานนี้:
น่าเสียดาย เช่นเดียวกับปัญหาดี ๆ ทั้งหลายในชีวิต… การตรวจจับแบบ ML เป็นปัญหา NP-hard
แต่เราไม่ใช่พวกมองโลกในแง่ร้ายสายทฤษฎีคอมพิวเตอร์ (TCS) และช่องสัญญาณไร้สายก็ไม่ใช่กรณีแย่ที่สุด พวกมันเป็นแบบสุ่ม และวงการวิจัยก็ทำงานกับคำถามต่อไปนี้มาตั้งแต่ช่วงต้นยุค 2000:
เมื่อการกู้คืนบิตที่ส่งไปมีความเป็นไปได้ในเชิงสถิติ เราจะทำมันในเวลาพหุนามได้ไหม?
เราไม่ได้ความคืบหน้ามากนักกับคำถามนั้นในงานวิจัยปี 2010 ข้างต้น และแม้จะมีงานมากมายในพื้นที่นี้ เท่าที่ผมเข้าใจ ปัญหานี้ยังคงเปิดอยู่ ตั้งแต่ปี 2001… หรือเรียกว่า หนึ่งในสี่ศตวรรษ เพื่อให้ฟังดูดราม่าหน่อย
จนกระทั่งสัปดาห์ที่แล้ว และคำตอบสุดท้ายก็ออกมาว่า
ใช่! เมื่อใดก็ตามที่การตรวจจับที่สมบูรณ์แบบเป็นไปได้ในเชิงสถิติ คุณสามารถทำมันได้ในเวลาพหุนาม
ปัญหา MIMO ถูกแก้แล้ว; จบ
แต่ใครจะสนล่ะ? เดี๋ยวเราจะกลับมาที่จุดนี้อีก
ผมแนบ เอกสาร มาด้วย และผมใช้เวลามากกว่า 5 วันในการโต้ตอบกับโมเดลไปมาเพื่อทำให้บทพิสูจน์และคำอธิบายง่ายขึ้น (ซึ่งตอนแรกมันหายนะมาก) กระบวนการนี้ใช้เวลานานกว่าบทพิสูจน์เริ่มต้นที่ GPT สร้างขึ้นมาก (ซึ่งใช้เวลาประมาณ 30 นาที) บทพิสูจน์ยาว แต่ค่อนข้างพื้นฐาน ผมตรวจสอบทุกอย่างแล้ว และเท่าที่ความสามารถในการตรวจพิสูจน์ของผมจะทำได้ มันถูกต้อง
ทีนี้ให้ผมพูดถึงปัญหาและประวัติของมันอีกสักหน่อย และว่าทำไมผมถึงคิดว่ามันน่าเขียนถึง แม้ว่าวงการจะขยับไปจากมุมเฉพาะของทฤษฎีการตรวจจับ MIMO นี้แล้วก็ตาม
การตั้งค่าของปัญหา
ดังนั้นคุณส่งเวกเตอร์ไบนารี x ใน {±1}^N และได้รับ
y=SNRNHx+w{\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}
โดยที่ H เป็นเมทริกซ์ N×N และทั้ง H และ w มีสมาชิกแบบ iid N(0,1) โดยทั้งหมดเป็นอิสระต่อกัน ผู้รับรู้ H และสถิติของสัญญาณรบกวน แต่ไม่รู้ w และต้องการ x คืนจาก y ผลเฉลยที่เหมาะที่สุดแบบบล็อกเออร์เรอร์สำหรับปัญหาการกู้คืนมีค่าเท่ากับ
อีกอย่างหนึ่ง การหาค่าเหมาะที่สุดนี้ยังปรากฏในรูปแบบอื่น ๆ ด้วย: MIMO detection, CDMA multi-user detection, integer least squares, closest vector in a lattice ฯลฯ
และเมื่อ SNR = ∞ (กล่าวคือ สัญญาณรบกวนประสิทธิผลเป็น 0) ปัญหากลายเป็นเรื่องง่าย: เมทริกซ์ช่องสัญญาณ H สามารถหาตัวผกผันได้ด้วยความน่าจะเป็น 1 คุณจึงอินเวิร์สมัน แล้วกู้คืน x ที่แม่นยำด้วย inv(H)*y ในทางตรงกันข้าม เมื่อ SNR = 0 ไม่มีอะไรให้ตรวจจับจากสัญญาณรบกวนได้ และการตรวจจับแบบ ML ก็ล้มเหลว
แต่ในช่วงระหว่าง 0 ถึงอนันต์ การตรวจจับแบบ ML ประสบความสำเร็จ และมันสำเร็จที่ SNR = 2 log N พอดี นั่นหมายความว่าการแก้ปัญหาการหาค่าเหมาะที่สุดข้างต้นช่วยให้คุณกู้คืนบิตทั้งหมดของลำดับ N บิตที่ส่งไปได้อย่างสมบูรณ์ ด้วยความน่าจะเป็นที่เข้าใกล้ 1 และต่ำกว่านั้น (ขึ้นกับเทอมบวก loglogN) ความน่าจะเป็นในการกู้คืนแบบบล็อกจะเข้าใกล้ 0
ดังนั้นเมื่อเหนือ 2logN สัญญาณที่ส่งไปเป็นจุดเหมาะที่สุดของปัญหาการหาค่าเหมาะที่สุดแบบ ML แต่การแก้มันดูเหมือนต้องค้นหาอย่างละเอียดถี่ถ้วนเหนือลำดับ N บิตที่เป็นไปได้ทั้งหมด คำถามที่เราสนใจตอนนี้คือ:
อัลกอริทึมเวลาพหุนามสามารถกู้คืน x ที่ส่งไปได้ไหมเมื่อ ML ประสบความสำเร็จ?
**
ประวัติโดยย่อพร้อมดราม่านิดหน่อย
คำถามเรื่องการแก้ได้ของปัญหา integer least squares เก่าแก่พอ ๆ กับปี 1989 เมื่อ Verdú พิสูจน์ ว่ามันเป็น NP-hard ในกรณีทั่วไป แต่ความ NP-hard เป็นข้อความเกี่ยวกับกรณีแย่ที่สุด และอินสแตนซ์ของเราไม่ใช่แบบนั้น
Hassibi และ Vikalo ในปี 2001 เป็นคนแรก—เท่าที่ผมรู้—ที่โต้แย้งว่ามีความหวังสำหรับคำตอบแบบเวลาพหุนามในกรณีเฉลี่ย อัลกอริทึมที่พวกเขาวิเคราะห์เป็นวิธีที่ได้รับความนิยมในขณะนั้น คือ Sphere Decoder (SD) ซึ่งย้อนกลับไปถึง Fincke และ Pohst ในปี 1985 Sphere Decoder น่าสนใจเป็นพิเศษเพราะ 1) มันเป็นอัลกอริทึม ML ที่ แม่นยำ กล่าวคือ ให้ผลลัพธ์เป็นตัวหาค่าต่ำสุดเสมอ และ 2) ในทางปฏิบัติมันดูเหมือนเร็วกว่าเวลาเอ็กซ์โปเนนเชียลมาก
ดังนั้นความหวังคือเราอาจพิสูจน์ได้จริง ๆ ว่า SD ทำงานในเวลาพหุนาม นี่คือสิ่งที่ H&V อธิบายไว้ในเอกสารของพวกเขา: พวกเขาคำนวณ สูตรสำหรับความซับซ้อนที่คาดหวังของ Sphere Decoder โดยเฉลี่ยเหนือช่องสัญญาณและสัญญาณรบกวน และแสดงว่ามันดูเป็นพหุนาม ถ้านั่นเป็นจริง คำถามก็ถูกปิดลง นั่นดูเหมือนผลลัพธ์ที่เหลือเชื่อ
จากนั้น Jaldén และ Ottersten ในปี 2005 แสดงว่าการตีความเชิงเส้นกำกับนั้นไม่ค่อยถูกต้อง: ที่ SNR คงที่ เท่าใดก็ได้ ไม่ว่าจะใหญ่แค่ไหน ความซับซ้อนที่คาดหวังของ sphere decoding แท้จริงแล้วเป็นแบบเอ็กซ์โปเนนเชียลในมิติของปัญหา
เนื่องจากวิธีที่แม่นยำและเร็วนั้นใช้ไม่ได้ วงการจึงทุ่มเทความพยายามอย่างมากในการหาค่าประมาณสำหรับปัญหาการหาค่าเหมาะที่สุดแบบ ML Semidefinite relaxations พร้อมการรับประกันการประมาณ และ เงื่อนไขความแน่นที่ SNR สูง แต่ไม่มีเกณฑ์ที่คมชัด Bit-flipping local search ดูเหมือนจะตรงกับ ML ในการจำลอง แต่ไม่มีบทพิสูจน์เต็มรูปแบบว่าตรงกับเกณฑ์การกู้คืนของ ML วรรณกรรม AMP ระบุลักษณะความคลาดเคลื่อน ต่อบิต อย่างเข้มงวด ที่ SNR คงที่ ซึ่งการกู้คืนแบบบล็อกเป็นไปไม่ได้ ฟิสิกส์สถิติสร้างวิธีการเวลาพหุนามที่ คาดการณ์ ว่าตามรอย ML แบบแม่นยำ โดยใช้ข้อโต้แย้งระดับ replica แต่เท่าที่ผมเข้าใจ ไม่มีบทพิสูจน์ และงานวิจัยกับ Babak และ Alex จากปี 2010 ข้างต้นวิเคราะห์วิธี MCMC ที่พิสูจน์ว่าหลังจากการ mix แล้ว การแจกแจงแบบ stationary วางมวลที่ไม่หายไปบนคำตอบที่ถูกต้อง แต่ไม่ได้พิสูจน์อะไรเกี่ยวกับ mixing time ซึ่งเป็นส่วนที่ยาก
ตลอดหลายปีนั้น เท่าที่ผมเห็น มี วิธีการเวลาพหุนาม เพียงวิธีเดียวเท่านั้นที่มาพร้อมกับการรับประกันการกู้คืนแบบบล็อกอย่างเข้มงวดที่ระดับ SNR ใด ๆ: box relaxation ในปี 2020 ซึ่งแสดงให้เห็นว่าสามารถกู้คืนบล็อกได้เมื่อ SNR สเกลประมาณ 4 log N และพิสูจน์ได้ว่าไม่ต่ำกว่านั้น อีกอย่างหนึ่ง มันค่อนข้างน่าสนใจที่เครื่องมือทางความน่าจะเป็นที่จำเป็นในการวิเคราะห์เทคนิคแบบนี้เพิ่งเติบโตเต็มที่ในช่วงปลายทศวรรษ 2010 ซึ่งส่วนใหญ่เป็นช่วงที่วงการได้ขยับไปแล้วและแยกย้ายกันไปแล้ว
และตั้งแต่นั้นมา… ก็ไม่มีความเคลื่อนไหวมากนัก
พูดสั้น ๆ ก็คือ ช่องว่างระหว่างสิ่งที่ ML ทำได้กับสิ่งที่วิธีการเวลาพหุนามใด ๆ สามารถทำได้ อย่างพิสูจน์ได้ ไม่เคยถูกปิด
**
GPT กับ Claude ทำอะไร และเราได้บทพิสูจน์ที่ผม ดิมิทริส ตรวจสอบได้อย่างไร?
ด้วยแรงบันดาลใจจาก ความสำเร็จ ที่ไม่น่าเชื่อ เมื่อไม่นานมานี้ ของโมเดลระดับแนวหน้าในงานคณิตศาสตร์ที่ยาก ผมจึงตัดสินใจกลับไปหาปัญหาที่หลอกหลอนผมตอนเป็นนักศึกษาปริญญาโท (ผมเคยทำงานด้านทฤษฎีสารสนเทศและโค้ดดิ้ง) และเริ่มเล็งดาวมรณะไปที่พวกมัน นี่คือสิ่งที่รู้สึกจริง ๆ เมื่อถามคำถามคณิตศาสตร์ที่ยากแล้วให้ GPT แก้แบบ zero shot:
GIF
แต่ผมรู้ว่ามีปัญหาอยู่หน่อย ๆ ถึงแม้ผมจะได้คำตอบเต็มรูปแบบสำหรับคำถามที่ผมถามกลับมา ผมก็จะติดคออยู่ที่การต้องตรวจสอบมัน ถ้าผมอยากเผยแพร่มันในวงกว้าง หนึ่ง เพราะผมไม่อยากทำตัวน่าอายถ้ามันกลายเป็นว่าผิด และสอง เพราะการแบ่งปันคือเหตุผลหลักที่เราถามคำถามและทำวิทยาศาสตร์อยู่แล้ว
ดังนั้นผมจึงตัดสินใจเลือกคำถามที่รู้สึกว่าทะเยอทะยานที่สุดข้อหนึ่งที่รบกวนผมในช่วงต้นของปริญญาเอก และเป็นคำถามที่สื่อสารได้ชัดเจนและยังไม่มีคำตอบ ผมจึงถาม GPT-5.6 และ Claude Fable 5 ว่าการตรวจจับ MIMO แบบ ML สามารถแก้ได้ในเวลาพหุนามเมื่อใด
ทั้งคู่สร้างบทพิสูจน์สำหรับอัลกอริทึมที่แตกต่างกัน โดยระบุอย่างมั่นใจว่าไม่มีช่องว่าง! มีอัลกอริทึมเวลาพหุนามที่ประสบความสำเร็จที่ SNR สูงกว่า 2 log N ตรงกับเกณฑ์การกู้คืนของ ML พอดี (ขึ้นกับเทอมบวก loglog แต่ใครจะสนล่ะ)
แต่มันมีปัญหาเล็กน้อย 😊 อัลกอริทึมของ GPT เป็น AMP variant และผมเกลียด AMP มาก ๆ เพราะผมไม่เข้าใจการวิเคราะห์มันเลยสักนิด ผมจึงบอกให้มันลองพิสูจน์ผลลัพธ์เดียวกันใหม่ ถ้าเป็นไปได้ สำหรับอัลกอริทึมที่ง่ายกว่า และแน่นอน GPT ก็สร้างอัลกอริทึมอีกตัวที่ผมก็รู้สึกขัดกับสัญชาตญาณ และเป็นอัลกอริทึมที่ผมไม่เคยเห็นใครใช้มาก่อน!
ส่วน Fable กลับสร้างสิ่งที่ผมชอบมาก:
signed LMMSE แล้วตามด้วย greedy bit flips อัลกอริทึมที่เคยถูกนำเสนอในอดีตและใช้งานจริงในทางปฏิบัติ
แต่ยังมีอีกปัญหา! ตามที่ GPT กล่าว บทพิสูจน์ของ Fable ส่วนใหญ่ผิด.. แต่ยังกู้ได้ ผมจึงตัดสินใจยึดอัลกอริทึมที่ Fable แนะนำ และขอให้ GPT เอาบทพิสูจน์ของ Fable ไปแก้ไข และมันก็ทำได้!
แต่ก็ยังมีอีกปัญหา บทพิสูจน์ใหม่นี้อ่านไม่รู้เรื่อง: กำแพงของสัญลักษณ์ ตัวแปรที่ชี้ไปยังตัวแปรที่ชี้ไปยังอัตราส่วนของตัวแปรที่นิยามตัวแปรอื่น เครื่องมือวิเคราะห์เมทริกซ์และความน่าจะเป็นที่แปลกประหลาด อะไรทำนอง Marchenko–Pastur ที่ทำให้ผมเป็นลมพิษ และสิ่งงดงามอื่น ๆ อีกมากมาย
ดังนั้นประมาณ 4-5 วัน ผมจึงวนไปมาระหว่างโมเดลทั้งสอง และขอให้พวกมันให้ชุดขั้นตอนที่ ง่ายที่สุดเท่าที่จะเป็นไปได้ สำหรับแต่ละองค์ประกอบใหญ่ที่จำเป็นต่อการทำให้บทพิสูจน์สำเร็จ ผมบอกพวกมันอย่างชัดเจนว่าขอบเขตและค่าคงที่แย่ลงได้ ไม่เป็นไร ตราบใดที่เกณฑ์ 2 log N ยังคงอยู่ ทั้งหมดเพื่อความเรียบง่าย
สิ่งที่ผมต้องการคือบทพิสูจน์ที่ไดโนเสาร์แก่ ๆ อย่างผมที่มีสมาธิสั้นสามารถย่อยได้โดยไม่ร้องไห้
จริง ๆ แล้วผมขอให้ GPT และ Claude แชร์ข้อความที่ผมบ่นมากที่สุดกลับมาให้ดู ฮ่า ๆ
อันที่ผมชอบที่สุด:
ทำไมผมถึงยืนกรานเรื่องขั้นตอนที่ง่ายมาก ๆ? เพราะผมต้องการตรวจสอบสิ่งนี้ด้วยตัวเอง ตั้งแต่ต้นจนจบ และไม่ ผมไม่อยากใช้ Lean มันไม่ได้แก้ปัญหาของผม การตรวจสอบแบบเป็นทางการแค่ย้ายระดับนามธรรมไปที่อื่น!! คุณยังต้องตรวจสอบว่าภาษาอังกฤษของบทตั้ง (lemma) แปลไปเป็น Lean อย่างซื่อสัตย์ ซึ่งเป็นภาษาที่ผมไม่เข้าใจ
ช่างมันเถอะ ผมไม่ชอบ Lean ขอโทษนะ
แต่ผมเข้าใจพีชคณิตเชิงเส้นพื้นฐานและความน่าจะเป็น และผมเชื่อใจตัวเองในการตรวจสอบขั้นตอนแบบนั้น ดังนั้นนั่นคือระดับของบทพิสูจน์ที่ผมต้องการ
จากนั้นก็ใช้เวลาหลายวันในการพรอมพ์แล้วพรอมพ์แล้วพรอมพ์ โดยให้โมเดลช่วยทำให้ข้อโต้แย้งของกันและกันง่ายขึ้น ขณะที่ผมก็บ่นและปฏิเสธอะไรก็ตามที่ผมตามไม่ทัน
และสุดท้ายมันก็สำเร็จ! เราได้บทพิสูจน์ที่ผมเข้าใจอย่างถ่องแท้ และตอนนี้ผมได้ตรวจสอบมันทีละบรรทัดแล้ว
การพิสูจน์มันใช้เวลา 30 นาที และการทำให้ผมตรวจสอบได้ใช้เวลาประมาณ 5 วัน นั่นคืออัตราส่วนที่บ้าไปหน่อย แต่มันก็เป็นอย่างนั้น และผลลัพธ์: อัลกอริทึมง่าย ๆ ทำงานได้เมื่อใดก็ตามที่ maximum likelihood ทำงานได้ ในเวลาพหุนาม ไม่มีช่องว่างเชิงคำนวณ-สถิติในปัญหานี้
ปัง!
**
ภาพรวมระดับสูงของบทพิสูจน์คืออะไร?
อัลกอริทึมมันง่ายจนแทบจะเขิน แต่ทำไมมันถึงได้ผล? LMMSE ตามด้วยการปัดเศษ ทำให้คุณอยู่ในระยะห่างแฮมมิงที่เศษเสี้ยวเล็กจิ๋วจากสัญญาณที่ส่งไป กล่าวคือห่างจากความจริงแค่ o(N)
จากนั้น greedy bit-flipping จะติดกับดักไม่ได้ เพราะกำไรจากการลดค่าในแต่ละขั้น (นั่นคือ ต้นทุนดีขึ้นเท่าไร) ถูกควบคุมโดยปริมาณแบบเกาส์เซียน และสมบัติความเข้มข้นแบบสม่ำเสมอของมันยืนยันว่าเวกเตอร์ทุกตัวที่ไม่ใช่คำตอบจริงภายในบอลหนึ่ง ๆ มีบิตฟลิปที่ทำให้ดีขึ้นอย่างเคร่งครัดในขนาดที่รับประกันได้ หมายความว่าไม่ว่าคุณจะทำอะไร คุณจะดีขึ้นในปริมาณที่ห่างจากศูนย์อย่างแน่นอน
อย่างไรก็ตาม การที่ต้นทุนดีขึ้นในทุกขั้นของ greedy ไม่ได้หมายความว่าระยะห่างแฮมมิงถึงความจริงจะดีขึ้นในทุกขั้น จริง ๆ แล้วมันอาจแย่ลงชั่วคราว แต่ไม่แย่ลงมากนัก เพราะฟังก์ชันต้นทุนเพิ่มขึ้นเมื่อคุณเพิ่มระยะห่างแฮมมิงจากความจริง นั่นหมายความว่าจุดใดก็ตามที่ไกลพอจะมีต้นทุนสูงกว่าจุดที่อัลกอริทึมเริ่มต้นมาก และเส้นทางที่ต้นทุนลดลงอย่างเดียวไม่สามารถไปถึงจุดนั้นได้ อัลกอริทึมแบบ greedy อาจเดินไปมาในบอลของระยะห่างแฮมมิง แต่มันถูกจำกัดด้วย "กำแพงต้นทุน" ซึ่งทำให้เส้นทางของมันอยู่ในบอล
ดังนั้น 1) ทุกขั้นจะปรับปรุงต้นทุนในปริมาณที่ห่างจากศูนย์ และ 2) ต้นทุนเริ่มต้นไม่ได้สูงกว่าจุดเหมาะที่สุดมากนัก ด้วยเหตุนี้ การรันแบบ greedy ต้องหยุดในที่สุด และการหารปริมาณหนึ่งด้วยอีกปริมาณหนึ่ง จะให้จำนวนขั้นที่มันต้องใช้ ซึ่งก็คือ NlogN
ยิ่งไปกว่านั้น greedy ไม่สามารถจบที่อื่นได้นอกจากคำตอบจริง: ทุกจุดอื่นภายในบอล ยังมีบิตฟลิปบางตัวที่ทำให้ดีขึ้น และอัลกอริทึมไม่ได้รับอนุญาตให้หยุดตรงนั้น จุดเดียวที่หยุดได้คือเวกเตอร์ที่ถูกส่งไป
นี่คือภาพประกอบที่สวยงามของข้อโต้แย้งสำคัญ
มันสำคัญไหม?
วงการไร้สายได้ขยับไปแล้ว และผมก็ด้วย แต่นี่เป็นคำถามที่สำคัญจริง ๆ ผมคาดเดาได้ว่าผลลัพธ์นี้จะมีความหมายอย่างไรในช่วงปี 2010: รางวัลบทความยอดเยี่ยมของ ISIT หรือ CommSoc/IT Society และอาจรวมถึงการสัมภาษณ์งานที่ MIT, Berkeley และ Stanford ผมพูดได้อย่างมั่นใจว่าในฐานะนักศึกษาปริญญาเอก นั่นคงเป็นผลลัพธ์ระดับจอกศักดิ์สิทธิ์ และเป็นไฮไลต์ของอาชีพนักทฤษฎีสารสนเทศอันสั้นของผม
แต่.. วงการก็ได้ขยับไปแล้วเป็นส่วนใหญ่😊
มีปัญหามากมายแบบนี้ที่เคยสำคัญ และวงการทั้งหมดใช้เวลาหลายทศวรรษกับมัน จากนั้นค่อย ๆ ไม่สำคัญอีกต่อไปเมื่อสาขางานวิจัยขยับไป และถูกทิ้งให้เปิดค้างอยู่ตามลำพัง ไม่ใช่เพราะมันเป็นไปไม่ได้ แต่เพราะผู้คนค่อย ๆ เลิกสนใจ
ดังนั้น เมื่อผู้คนพูดว่า "ปัญหาเก่า N ปีถูกแก้โดย AI" ผมจะพยายามตีความว่ามันหมายถึงอะไร
แต่ยังมีอะไรที่เจ๋งสุด ๆ เกี่ยวกับทั้งหมดนี้: ตอนนี้คุณสามารถกลับไปหาปัญหาที่คุณเคยใส่ใจตอนเด็ก ๆ และเล็งดาวมรณะไปที่พวกมันได้ คำถามที่เคยยืนหยัดต่อสู้กับพลังเต็มกำลังของวงการวิจัยทั้งหมด ซึ่งตอนนี้นั่งอยู่อย่างเงียบ ๆ โดยไม่มีใครป้องกัน ตามมุมที่ถูกทอดทิ้งของจักรวาลวรรณกรรม รอคอยให้ดาวมรณะยิงใส่พวกมัน และค่าใช้จ่ายคือ 200 ดอลลาร์/เดือน
ยุคสมัยที่บ้าคลั่ง..
เอาล่ะ ผมจะโพสต์ ร่างปัจจุบัน ลง arXiv แต่ไม่แน่ใจว่าจะส่งไปนำเสนอที่งานประชุมหรือวารสารหรือไม่ (ไม่แน่ใจด้วยซ้ำว่าตอนนี้ที่ไหนจะเหมาะสม) ผมไม่อยากให้ใครเสียเวลาเปล่า แต่ถ้าคุณอ่านแล้วเจอข้อผิดพลาด ผมยินดีรับฟังมาก ๆ 😊
และตอนนี้เราก็รู้แล้วว่า:
การตรวจจับ MIMO แบบ ML เป็นเรื่องง่ายเมื่อใดก็ตามที่มันเป็นไปได้!
ไชโย…
**
ภาคผนวก
มีสิ่งที่มีประโยชน์ควรสังเกตเกี่ยวกับบทพิสูจน์ข้างต้น: ไม่มีการคิดค้นคณิตศาสตร์ใหม่เลย
ไม่มีอสมการ เทคนิค หรือวัตถุทางคณิตศาสตร์ใหม่ใดที่ไม่มีอยู่ในปี 2010 บทพิสูจน์ยาว แต่มัน พื้นฐาน ดังนั้นความยากจึงไม่ใช่เชิงแนวคิด แต่เกี่ยวกับความพยายามที่ต้องใช้ในการประกอบยี่สิบหน้าของขั้นตอนมาตรฐานในระดับรายละเอียดที่เหมาะสมและเวลาที่เหมาะสมเพื่อให้มันประกอบเข้ากันได้อย่างสมบูรณ์
ผมคิดว่าถ้าเรานำความคิดนี้ไปอีกขั้น มันก็ให้คำนิยามของปัญหาประเภทหนึ่ง ซึ่งการแก้ต้องใช้คณิตศาสตร์ใหม่เป็นศูนย์ แค่ประกอบไอเดียที่รู้จักเข้าด้วยกันด้วยลำดับยาว ๆ ซึ่งใช้โทเคนหรือเวลามากกว่าที่ใครจะยอมทุ่มเท ปัญหาเหล่านี้จะตกเป็นของ AI อย่างรวดเร็ว เพราะการลองอะไรหลาย ๆ อย่างจนกว่าจะมีอะไรเข้าเค้าคือสิ่งที่ AI ถนัดสุด ๆ และบางที "ไม่มีใครลองสิ่งที่รู้จักอยู่นานพอ" อาจอธิบายปัญหาที่เปิดอยู่หลายข้อมากกว่าที่เราคิด
จากประเด็นนี้ ขอลองทำการทดลองทางความคิด: สมมติว่าคุณสามารถพา GPT-5.6 หรือ Fable ย้อนกลับไปปี 2005 โดยใช้ RL flops เท่าเดิม แต่ข้อมูล pretraining ที่มีอยู่แค่นั้น พวกมันจะยังแก้ปัญหาได้หรือไม่?
ผมไม่รู้ มันยากที่จะจำลองเหตุการณ์ย้อนกลับ แต่ถึงแม้เครื่องมือหลายอย่างอาจมีอยู่ในปี 2005 แล้ว แรง "ดึงดูด" ไปสู่เทคนิคที่โมเดล "รู้สึกว่าถูกต้อง" อาจพึ่งพาความนิยมของวิธีการหนึ่ง ๆ และสัญชาตญาณร่วมของเราอย่างมาก ตามที่ถูกบันทึกในความถี่ของการใช้ไอเดียหนึ่งในบริบทเฉพาะ การ pretrain แบบปี 2005 อาจประสบปัญหา ไม่ใช่เพราะขาด RL flops แต่เพราะขาดแรงดึงดูดจาก pretraining ไปสู่ชุดไอเดียที่ถูกต้อง ซึ่งหมายความว่าโมเดลเหล่านี้เป็นอะไรที่น่าสนใจยิ่งกว่าออราเคิลทางคณิตศาสตร์แห่งความจริงมาก เราอาจมองพวกมันเป็นสิ่งที่กลั่นจากสัญชาตญาณที่สั่งสมมาของเรา แล้วถูกทำให้คมขึ้นอีกด้วย RL
ความคิดสุดท้ายแล้วผมจะจบด้วยสิ่งนี้:
สมมติว่าผมสามารถย้อนเวลาไปบอกตัวผมในปี 2009 ที่เต็มไปด้วยความกังวลว่า "น้องชาย ใจเย็น ๆ อีก 17 ปีข้างหน้าพี่จะได้มีส่วนร่วมในการปิดคำถามเรื่องการแก้ได้ของการตรวจจับ MIMO แบบ ML" และไม่พูดอะไรอีก ตัวผมในอดีตคงจะคลั่งไปเลย และเมื่อพยายามหาว่าเขาจะไปถึงจุดนั้นได้อย่างไร เขาก็จะสรุปได้ทางเดียวที่มีเหตุผลในเวลานั้น: ผมต้องอยู่ในทฤษฎีสารสนเทศต่อไปอีกสิบห้าปี อาจจะบดอยู่กับ MIMO detection หรือในกรณีที่ดีที่สุดคือ integer optimization และไม่ทางใดก็ทางหนึ่ง ในช่วงปี 2026 binary least squares ในที่สุดก็แตกภายใต้น้ำหนักของสติปัญญาอันยิ่งใหญ่ของผม
ให้ตายเถอะ… ความภูมิใจแบบ a-priori ที่ผมคงจะรู้สึก
ถ้าเพียงแต่ดิมิทริสตัวน้อยจะรู้ว่าระยะห่างแฮมมิงระหว่างบิตของจักรวาลนั้นกับจักรวาลปัจจุบันของเรามันใหญ่โตมหาศาล และสำหรับสิ่งนั้น เราต้องขอบคุณความก้าวหน้าของอีกสิ่งหนึ่งที่เรียกว่า ML…
