ทำความแม่นยำ 78% บน MNIST ได้ด้วยโค้ดไม่ถึง 10 บรรทัดด้วย GZIP

 (jakobs.dev)
1 คะแนน โดย GN⁺ 2023-09-21 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เป็นการทดลองที่ดันความแม่นยำของการจำแนกตัวเลขลายมือ MNIST ไปได้ถึงประมาณ 78% โดยใช้เพียง การบีบอัด GZIP และ k-nearest neighbors (k-NN) แสดงให้เห็นว่าสามารถใช้การบีบอัดเป็นเครื่องมือจำแนกแบบไร้โมเดลได้
  • คำนวณ Normalized Compression Distance (NCD) จากการดูว่าความยาวเปลี่ยนไปมากแค่ไหนเมื่อบีบอัดตัวอย่างภาพสองภาพรวมกัน แล้วใช้ค่านี้เป็นตัวชี้วัดความคล้ายคลึงระหว่างภาพ
  • แต่ละตัวอย่างทดสอบจะถูกเปรียบเทียบกับตัวอย่างฝึก 100 ตัวอย่าง และใช้เสียงข้างมากของ เพื่อนบ้าน k=5 ที่ใกล้ที่สุดเป็นค่าทำนาย
  • เนื่องจากต้นทุนการคำนวณ จึงวัดความแม่นยำจาก เพียงบางส่วนของภาพทดสอบ ไม่ใช่ทั้งชุด และหากใช้ทั้งชุด การประเมินอาจแม่นยำยิ่งขึ้น
  • ตัวอย่างสาธารณะที่เผยแพร่ยังมี ข้อผิดพลาดจากการรีแฟกเตอร์ ที่สร้างแคชความยาวที่บีบอัดแล้วแต่ไม่ได้นำไปใช้ในการคำนวณ NCD จริง จึงควรลบแคชออกหรือสะท้อนให้ compute_ncd ใช้งานแคชดังกล่าว

จำแนก MNIST ด้วย GZIP + k-NN

  • การทดลองนี้จำแนกชุดข้อมูลตัวเลขลายมือ MNIST ด้วยการผสาน GZIP + k-NN
  • ตัวอย่างโค้ดสั้นใช้ความยาวของผลลัพธ์จาก gzip.compress(z.tobytes()) เป็นความยาวหลังการบีบอัด จากนั้นคำนวณ NCD แล้วเลือกค่าป้ายกำกับที่พบบ่อยที่สุดจากเพื่อนบ้านที่ใกล้ที่สุด 5 ตัว
  • ตัวอย่างที่รันได้มีอยู่ใน Jupyter Notebook
  • เป้าหมายไม่ใช่การทำความแม่นยำสูงสุด แต่เป็นการตรวจสอบไอเดียอย่างง่ายว่า การบีบอัดสามารถนำมาใช้เป็น เครื่องมือจำแนกแบบไร้โมเดล ได้
  • โค้ดไม่ถึง 10 บรรทัดไม่ใช่แก่นสำคัญของการทดลองนัก แต่ใกล้เคียงกับองค์ประกอบแบบ code golf เพื่อความสนุกมากกว่า

การคำนวณความคล้ายคลึงและขั้นตอนการจำแนก

  • NCD วัด ความคล้ายคลึง โดยทำการนอร์มัลไลซ์ว่าต้นทุนในการบีบอัดจุดข้อมูลสองจุดร่วมกันแตกต่างจากการบีบอัดแยกกันมากเพียงใด
  • ความยาวที่บีบอัดคำนวณได้ในรูปแบบต่อไปนี้
    • Cx1 = len(gzip.compress(x1.tobytes()))
    • Cx2 = len(gzip.compress(x2.tobytes()))
    • Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
  • สูตร NCD มีรูปแบบเป็น (Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)
  • การจำแนกจะคำนวณระยะห่างระหว่างภาพทดสอบแต่ละภาพกับภาพฝึก จัดเรียงจากใกล้ไปไกล แล้วใช้การโหวตเสียงข้างมากของ 5 ตัวที่ใกล้ที่สุด
  • ในการทดลองนี้ใช้ตัวอย่างฝึก 100 ตัวอย่างเป็นฐานในการเปรียบเทียบ และเนื่องจากต้นทุนการคำนวณ ชุดทดสอบก็ใช้เพียงบางส่วนเช่นกัน

แนวคิดอ้างอิงและข้อควรระวังในโค้ด

  • แนวทางนี้ได้แรงบันดาลใจจากบทความ text generation from data compression และงานวิจัย parameter free text classification
  • หลังจากเขียนบทความแล้ว ผู้เขียนยังพบโพสต์ MNIST by ZIP ของ Andreas Kirsch จากปี 2019 ซึ่งใช้แนวทางคล้ายกัน
  • โค้ดตัวอย่างสร้าง แคชความยาวหลังการบีบอัด ของตัวอย่างฝึกไว้ แต่ในลูปจริงกลับไม่ได้ใช้ค่าแคชดังกล่าว
    • ทั้งเวอร์ชันปกติและเวอร์ชันที่ทำให้อ่านยากต่างก็สร้าง compressed_lengths หรือ cls แต่ไม่ได้นำความยาวที่แคชไว้มาคำนวณ NCD
    • หากลบแคชออกแล้วใช้ training_set โดยตรง หรือปรับให้ compute_ncd ใช้ค่าแคช ก็จะทำให้เจตนาของโค้ดสอดคล้องกับการติดตั้งใช้งานจริง

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-09-21
ความคิดเห็นจาก Hacker News

  • ลองเปลี่ยนฟังก์ชันระยะทางในโค้ดเป็นมาตรวัดที่เรียบง่ายกว่าแล้วพบว่า ในการจำแนก MNIST ระยะทาง GZIP มีความแม่นยำต่ำกว่าและใช้การคำนวณมากกว่ามาก
    ระยะทาง Gzip: ประมาณ 3 นาที, ความแม่นยำ 78% / ระยะทาง Euclidean: ประมาณ 0.5 วินาที, 93% / ระยะทาง Jaccard: ประมาณ 0.7 วินาที, 94% / Dice dissimilarity: ประมาณ 0.8 วินาที, 94%
    Jaccard และ Dice วัดหลังจากทำให้ภาพเป็นไบนารีแล้ว
    ผมไม่คุ้นกับอัลกอริทึม GZIP นัก แต่ก็น่าสนใจที่ผลออกมาต่ำขนาดนี้ และสงสัยว่าถ้าใช้อัลกอริทึมบีบอัดที่เน้นภาพเป็นหลักจะดีกว่านี้ไหม
    ตัวบทความเองสร้างสรรค์ และโค้ดกับคำอธิบายก็ดี แต่ผมคิดว่า baseline ข้างต้นช่วยเพิ่มบริบทให้คะแนนของ gzip

    • ผลลัพธ์ที่ดีที่สุดที่ผมพบคือ normalized mutual information ได้ 95% และแม้จะซับซ้อนกว่าเล็กน้อย แต่คำนวณได้ค่อนข้างเร็วบนภาพไบนารี
      NMI skimage: ประมาณ 30 วินาที, ความแม่นยำ 95% / NMI numba: ประมาณ 0.6 วินาที, ความแม่นยำ 95%
      ใช้โค้ด numba ที่ ChatGPT ให้มาเพื่อคำนวณ 2x2 joint count, entropy และ normalized mutual information
    • รู้ว่า MNIST เป็นงานง่าย แต่ไม่คิดว่าจะง่ายถึงขนาดนี้ ถ้าแชร์ชิ้นโค้ดที่ใช้มาก็น่าจะเหมาะมากสำหรับใช้เป็น baseline
      ส่วนตัวสนใจการเทรน CIFAR10 แบบเร็ว ๆ เลยคิดว่าแนวทางแบบนี้อาจมีประโยชน์พอสมควรในโดเมนอื่นด้วย
    • การใช้งาน kernel method ของ ben recht ทำได้ 98% ใน 10 บรรทัด
      https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
    • ลองบีบอัดด้วย PNG แล้วเหมือนกัน จริง ๆ ดีกว่าเล็กน้อย โดย PNG ได้ความแม่นยำ 83% ในประมาณ 15.1 วินาที
      ลองใส่ zstandard ด้วย พบว่า Zstd(level=3) ได้ความแม่นยำ 88% ในประมาณ 3.5 วินาที เร็วกว่า gzip มาก
      ตอนคำนวณ Cx1x2 ถ้าใช้ (x1-x2)*2 แทน x1+x2 zstd จะขึ้นไปถึงความแม่นยำ 93%
      ถ้าไม่บวกสองอาร์เรย์ แต่เอามาซ้อนกันบนล่าง ประสิทธิภาพจะพังหมดเหลือต่ำกว่า 20% แต่น่าสนใจที่วิธีนั้นดูเหมือนจะใช้ได้ดีในการจำแนกสตริง
    • วิธี gzip เท่ก็จริง แต่สุดท้ายดูเหมือนเป็นการได้ ผลลัพธ์ต่ำลงด้วยขั้นตอนที่มากขึ้น

  • ถ้าเทียบกับเทคนิคอื่น Linear SVC ได้ 92%, SVC เคอร์เนล RBF ได้ 96.4%, SVC เคอร์เนลพหุนามได้ 94.5%, logistic regression ได้ 89%, naive Bayes ได้ราว 81%
    ที่มา: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
    ดูจากบทความออนไลน์แล้ว แค่ใช้ K-NN อย่างเดียว ก็น่าจะได้ผลดีกว่ามาก จนเหมือนผู้เขียนทำให้เรื่องยากขึ้นด้วยการใช้ gzip

    • หลายคนไม่รู้ว่า logistic regression ทำความแม่นยำบน MNIST ได้ราว 90%
      ผมชอบเริ่มจากโมเดลง่าย ๆ แล้วค่อยเพิ่มความซับซ้อนทีหลัง แต่ก็มักได้ยินคนพูดว่า “logistic regression ใช้ไม่ได้” แม้กับปัญหาที่จริง ๆ แล้วมันทำงานได้ดี
      ถ้าถามว่าคิดว่า baseline performance บน MNIST น่าจะอยู่ประมาณไหน หลายคนมักเดาว่า 20~30%
      แม้แต่คนที่ทำแมชชีนเลิร์นนิงก็มักประเมินต่ำไปว่า ผลตอบแทนที่ลดลง จะมาถึงเร็วแค่ไหนเมื่อเพิ่มความซับซ้อนของโมเดลมาก ๆ
      จากประสบการณ์ ถ้าโมเดลง่าย ๆ ทำผลงานได้ไม่ดี ก็มักยากที่จะได้ผลงานยอดเยี่ยมจากโมเดลที่ซับซ้อนกว่า
    • บล็อกนั้นไม่ได้แสดงผลลัพธ์ระดับ state-of-the-art ล่าสุด แต่ใกล้เคียงกับการเปรียบเทียบ การใช้งาน SVM ที่ค่อนข้างเรียบง่าย
      แม้แต่งานวิจัยต้นฉบับที่แนะนำชุดข้อมูล MNIST ก็ทำความแม่นยำได้ราว 98% และโครงข่ายประสาทยุคนี้ไปถึงความแม่นยำ 99.87% แล้ว
      https://paperswithcode.com/sota/image-classification-on-mnis...
    • ประเด็นหลักไม่ใช่การทำให้ดีกว่า แต่คือการแสดงว่าแม้หลังการบีบอัดก็ยังมีข้อมูลเหลือเพียงพอให้ได้สัญญาณขนาดใหญ่
      การบีบอัดมีไว้เพื่อทำให้ปัญหาเดิมยากขึ้น และในความเป็นจริงมันก็ยังทำงานแบบนั้นอยู่
    • เท่ดีที่สิ่งนี้ทำงานได้ แต่เมื่อ MNIST ง่ายเกินไปแล้ว ก็อยากให้ เลิกใช้เป็น benchmark เสียที
    • แปลว่ามีอัลกอริทึมบีบอัดที่เหมาะสมกว่าสำหรับความสัมพันธ์ระหว่างอินพุตกับเอาต์พุตของ MNIST
      โมเดลอื่น ๆ มักมีแนวโน้มจะเติม noise ลงไปที่ใดที่หนึ่ง เลยสงสัยว่าถ้าใส่ feature engineering ก่อน gzip จะเป็นอย่างไร
      เช่น อาจใช้ Gaussian blur และ convolution ก่อน แล้วค่อยใช้ deep learning สำหรับ feature selection

  • โค้ดอาจจะสวยและสั้น แต่ ความแม่นยำ 78% บน MNIST ถือว่าแย่มาก
    แม้แต่โมเดล dummy ที่ทำด้วย TensorFlow ก็แตะความแม่นยำ 90% ได้ง่าย ๆ และโมเดลที่ดีที่สุดอยู่ที่ 99.87%
    Benchmark: https://paperswithcode.com/sota/image-classification-on-mnis...

    • ผมคิดว่าจุดที่บทความเน้นนั้นผิด
      ส่วนที่น่าสนใจคือสามารถใช้ การบีบอัด เพื่อการจำแนกได้โดยไม่ต้องเทรนโมเดล
      นั่นทำให้ถามต่อได้ว่า มาตรวัดเชิงทฤษฎีสารสนเทศแบบอื่นที่ถูกกว่าและมีการสูญเสียข้อมูล จะใช้ได้ไหม
      To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
      [https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
    • เป้าหมายไม่ใช่การสร้างโค้ดที่ “สวยและสั้น” แต่คือการแสดงความอยากรู้อยากเห็นที่น่าสนุก ส่วนการทำให้ได้ใน 10 บรรทัดก็เหมือนเป็นโจทย์ท้าทายเพิ่มเติมเท่านั้น
      สิ่งที่น่าสนใจไม่ใช่ว่า GZip จะไปถึงประสิทธิภาพระดับ state-of-the-art หรือไม่ แต่คือ ข้อเท็จจริงที่ว่ามันจำแนกได้พอใช้
      คล้ายกับสิ่งที่น่าทึ่งไม่ใช่ว่าหมีเล่น Mozart ได้สมบูรณ์แบบหรือไม่ แต่คือมันเล่นเปียโนได้เลยต่างหาก
    • นี่ไม่ใช่ความพยายามทำลายสถิติ แต่เป็นตัวอย่างที่แสดงด้านที่น่าสนใจของการบีบอัด
      ถึงอย่างนั้นก็ยังดีกว่า baseline ถึง 8 เท่า และแสดงให้เห็นว่า การบีบอัดสามารถ เรียนรู้ representation ได้

  • หากเปลี่ยน compute_ncd เป็นระยะทางแบบยูคลิด ความแม่นยำในการทดสอบจะ เพิ่มขึ้น 15 จุดเปอร์เซ็นต์ และปริมาณการคำนวณก็ลดลงมากด้วย
    แค่เปลี่ยนเป็นแบบ distances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths] ก็พอ

  • หนังสือที่พูดถึงความเชื่อมโยงเชิงลึกระหว่างทฤษฎีสารสนเทศ การบีบอัด และอัลกอริทึมการเรียนรู้ เล่มที่ดีที่สุดสำหรับผมคือ MacKay
    สำหรับคนที่ได้รับการศึกษามาอย่างเป็นระบบ เรื่องนี้อาจเป็นความรู้ทั่วไป แต่ในฐานะคนที่เรียนแมชชีนเลิร์นนิงสายปฏิบัติด้วยตัวเอง พอเห็นว่าหัวข้อนี้เชื่อมโยงไปถึงสาขาอย่างฟิสิกส์อนุภาคและจักรวาลวิทยา ก็รู้สึกเหมือนมีช่วงเวลา “อ๋อ!” ที่แรงมาก
    ฝากไว้ด้วยความหวังว่าจะมีแม้สักคนได้พบความเข้าใจแบบเดียวกัน

    • ผมใส่ MacKay ไว้ในรายการสิ่งที่ต้องทำแล้ว
      ตอนรู้ว่า การบีบอัด Lempel-Ziv ดั้งเดิม ซึ่งเป็นหนึ่งในรากฐานของ gzip ไม่ได้มาจากความพยายามแค่จะลดขนาดเท่านั้น แต่เกิดจากการศึกษา “ความซับซ้อนของลำดับจำกัด” นี่ค่อนข้างน่าประทับใจ
      https://ieeexplore.ieee.org/document/1055501

  • ถ้าพูดอย่างเป็นธรรม แค่เอา MNIST ผ่าน UMAP ก็แยกได้เกือบสมบูรณ์แล้ว
    ทุกวันนี้ถ้าจะทำผลงานบน MNIST ให้แย่คงต้องพยายามพอสมควร
    https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
    ตอนนี้น่าจะถึงเวลาปลดระวางชุดข้อมูลนี้แล้ว และผมคิดว่าชุดข้อมูลอย่าง QuickDraw มีเหตุผลกว่ามาก

    • ในฐานะผู้เขียน เห็นด้วยอย่างยิ่ง
      มันคงไม่ใช่ความสำเร็จใหญ่โตในตัวเอง แต่การได้เห็นว่ามันทำงานได้ก็ยังน่าสนใจ
      กลับถึงบ้านแล้วจะเพิ่มในบทความว่า การแก้ MNIST นั้นค่อนข้างง่าย
    • ในมุมมองการวิจัย MNIST เป็นปัญหาที่แทบจะแก้ได้หมดแล้ว และผมคิดว่าประสิทธิภาพปัจจุบันน่าจะดีกว่ามนุษย์ด้วยซ้ำ
      ถึงอย่างนั้น อัลกอริทึมที่เรียบง่ายและสมเหตุสมผลส่วนใหญ่ก็ไปถึงความแม่นยำ 97% ได้ จึงยังมีคุณค่าในฐานะเครื่องมือการสอนหรือ ชุดข้อมูล Hello world
      ต่อให้สร้างเครื่องมือเองตั้งแต่ต้นก็ยังอยู่ในขนาดงานการบ้าน และเป็นโจทย์ที่มีประโยชน์ซึ่งใคร ๆ ก็เข้าใจได้ อย่าง “การรู้จำตัวเลขบนไปรษณีย์”
    • gzip ไม่ใช่ “ของสมัยนี้” แต่เป็นเทคโนโลยีที่เก่ากว่า UMAP และแม้แต่ตัว MNIST เองมาก
      ถ้าเข้าใจการบีบอัด แนวทางนี้ก็เป็นไอเดียที่เรียบง่ายมาก จนสามารถเขียนได้ตั้งแต่วันแรกที่ MNIST เปิดเผย และก็น่าจะยังได้ความแม่นยำ 78%
      ตรงนี้แหละที่รู้สึกค่อนข้างน่าทึ่ง
    • ถึงขั้นทำให้คนเสียมารยาทที่บ่นเรื่องตัวย่อดูมีเหตุผลขึ้นมาได้เลย
      รีโพซิทอรีก็ไม่ได้นิยาม UMAP ไว้ แต่ถ้าเชื่อ ChatGPT แล้ว UMAP ย่อมาจาก Uniform Manifold Approximation and Projection เป็น เทคนิคการลดมิติและการทำภาพประกอบข้อมูล ที่ใช้ในแมชชีนเลิร์นนิงและการวิเคราะห์ข้อมูล

  • ผมรู้เรื่องสายนี้แค่ระดับงานอดิเรก แต่ข้อมูลที่ถูกบีบอัดอย่างหนักน่าจะมี เอนโทรปีสูง เหมือนข้อมูลที่เข้ารหัสหรือเปล่า
    ถ้าหาแพตเทิร์นในข้อมูลที่บีบอัดแล้วรู้ตัวเลขต้นฉบับได้ ก็น่าจะเอาแพตเทิร์นนั้นไปใช้กับการบีบอัดที่ดีกว่าได้ไม่ใช่หรือ

    • เดโมนี้ไม่ได้จัดประเภทจากการมองข้อมูลที่ถูกบีบอัด แต่จัดประเภทจากว่า ข้อมูลถูกบีบอัดได้ดีแค่ไหน
      แนวคิดคือ “7 7” ควรถูกบีบอัดได้ดีกว่า “7 3” และภาพแรสเตอร์ของ “7 7” ก็น่าจะถูกบีบอัดได้ดีกว่า “7 3” เช่นกัน
    • ข้อมูลที่เข้ารหัสอย่างอุดมคติควรบีบอัดไม่ได้
      ความบีบอัดไม่ได้เป็นคุณลักษณะของการดำเนินการเข้ารหัสที่มีประสิทธิภาพ
      ดูส่วนการบีบอัดในเอกสาร Kolmogorov complexity: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
      แนวคิดหนึ่งในเรื่องการบีบอัดที่ผมชอบคือ หลักช่องนกพิราบ ซึ่งบอกว่าในอัลกอริทึมการบีบอัดทุกแบบ จะต้องมีเอาต์พุตบางตัวที่ใหญ่กว่าอินพุตเสมอ
      เพย์โหลดเข้ารหัสที่ออกแบบมาดีก็ลองบีบอัดได้ แต่โดยเฉลี่ยเอาต์พุตจะใหญ่กว่าอินพุต ทำให้การบีบอัดไม่มีประโยชน์ เราจึงเรียกว่า “บีบอัดไม่ได้”
      https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...

  • เหมือนเคยมีกรณีเมื่อหลายปีก่อนที่ใช้ ขนาด ของภาพ MNIST เป็น “เมตาฟีเจอร์” แต่ตอนนี้หาไม่เจอทันที
    เท่าที่จำได้ แค่ฟีเจอร์เดียวนี้โดยไม่ต้องดูภาพเลยก็ได้ความแม่นยำคร่าว ๆ แถว 90%

    • หลายปีก่อนผมเคยทำโปรเจกต์สร้างลายนิ้วมือจากสกรีนช็อตเว็บเพจ และแค่ขนาดของภาพที่บีบอัดแล้วก็ทำงานได้ดีพอ ๆ กับวิธีลายนิ้วมือบางแบบที่ใช้เปรียบเทียบความคล้ายกันระหว่างสกรีนช็อต
    • สงสัยว่า “ขนาด” ตรงนี้หมายถึงอะไร
      หมายถึงขนาดที่บีบอัดด้วย gzip หรือเปล่า? ถ้าดูแค่ว่าภาพ MNIST มืดแค่ไหน หรือก็คือสัดส่วนพิกเซลสีเข้ม จะได้ความแม่นยำประมาณ 20% ซึ่งดีกว่าการเดาสุ่มสองเท่า แต่ยังห่างไกลจาก 90% มาก

  • ผมคิดว่าผู้เขียนเปเปอร์นั้นอาจทำพลาดจนผลลัพธ์พุ่งขึ้นไปอยู่แถวบนของเบนช์มาร์ก
    หลังเหตุการณ์นั้นผมมองว่าทฤษฎีไม่ค่อยสอดคล้องกัน แต่ถึงอย่างไร ความแม่นยำ 78% ด้วย GZIP อย่างเดียวก็น่าประทับใจ

    • น่าจะนึกถึงบทความนี้: https://kenschutte.com/gzip-knn-paper/
    • นี่เป็นความแม่นยำ 78% จากระยะทางการบีบอัดที่อิง Gzip กับ KNN ดังนั้นจึงดูแย่กว่าการจับ KNN เข้ากับมาตรวัดระยะทางอื่นแทบทุกแบบที่นึกออก

  • ไม่ว่าปัญหานี้จะเหมาะกับทริกการบีบอัดหรือไม่ คนที่ทดลองอยู่ควรเลิกใช้ gzip แล้วใช้ zlib ดีกว่า
    ถ้าเปลี่ยนบรรทัดแรกจาก gzip.compress เป็น zlib.compress จะได้ประสิทธิภาพการจำแนกเหมือนเดิม แต่เร็วขึ้น 3 เท่า