Gzip และ KNN เหนือกว่า Transformers ในงานจำแนกข้อความ

 (twitter.com/LukeGessler)
2 คะแนน โดย GN⁺ 2023-07-15 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เสนอวิธีจำแนกข้อความแบบไม่อิงพารามิเตอร์ (non-parametric) ที่ผสานตัวบีบอัดแบบง่ายอย่าง gzip เข้ากับ ตัวจำแนก k-nearest neighbors (kNN)
  • แม้ไม่มีพารามิเตอร์สำหรับการเรียนรู้เลย แต่ก็ เบาและใช้งานได้ทั่วไป พร้อมภาระต้นทุนการคำนวณต่ำกว่า DNN
  • เมื่อเทียบกับวิธี deep learning ที่ไม่ได้ผ่านการ pretrain ให้ผลลัพธ์ที่แข่งขันได้บน ชุดข้อมูล in-distribution 6 ชุด
  • เหนือกว่า BERT ใน ชุดข้อมูล OOD (out-of-distribution) ทั้งหมด 5 ชุด ซึ่งรวมถึง ภาษาทรัพยากรต่ำ 4 ภาษา
  • ทำงานได้ดีแม้ใน สภาพแวดล้อมแบบ few-shot ที่มีข้อมูลมีป้ายกำกับไม่เพียงพอจนทำให้การฝึก DNN ทำได้ยาก

ภูมิหลังและประเด็นปัญหา

  • DNN ถูกใช้อย่างแพร่หลายในการจำแนกข้อความด้วยความแม่นยำสูง
  • อย่างไรก็ตาม ต้องใช้ พารามิเตอร์หลายล้านตัว และข้อมูลมีป้ายกำกับจำนวนมาก ทำให้มีต้นทุนการคำนวณสูง
  • ส่งผลให้การใช้งาน การปรับให้เหมาะสม และ การถ่ายโอนไปยังสถานการณ์ OOD (out-of-distribution) กลายเป็นงานที่มีต้นทุนสูงในทางปฏิบัติ

วิธีที่เสนอ

  • นำเสนอวิธีแบบไม่อิงพารามิเตอร์ที่ ง่าย เบา และใช้งานได้ทั่วไป เพื่อเป็นทางเลือกแทน DNN
  • โครงสร้างที่ผสานตัวบีบอัดแบบง่ายอย่าง gzip เข้ากับ ตัวจำแนก k-nearest neighbors
  • จุดเด่นสำคัญคือ ไม่มีพารามิเตอร์สำหรับการเรียนรู้เลย

ผลการทดลอง

  • มีประสิทธิภาพในระดับที่แข่งขันได้กับวิธี deep learning ที่ไม่ได้ผ่านการ pretrain บน ชุดข้อมูล in-distribution 6 ชุด
  • เหนือกว่า BERT ใน ชุดข้อมูล OOD ทั้งหมด 5 ชุด ซึ่งรวมถึงภาษาทรัพยากรต่ำ 4 ภาษา
  • มีจุดแข็งแม้ใน สภาพแวดล้อมแบบ few-shot ที่ข้อมูลมีป้ายกำกับมีน้อยเกินไปจนยากต่อการฝึก DNN อย่างมีประสิทธิภาพ

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

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

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

  • ลิงก์ไปยังงานวิจัยโดยตรง: https://aclanthology.org/2023.findings-acl.426.pdf
    โดยสัญชาตญาณแล้ว แก่นสำคัญคือเมื่อมีเอกสาร x1, x2 และเอกสารใหม่ x ถ้าความเป็นแบบแผนทางสถิติของ x ใกล้กับ x1 มากกว่า x2 ก็จะได้ว่า len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)) โดยที่ cat คือการนำมาต่อกัน และ compress คือเครื่องมือบีบอัดอย่าง gzip
    พูดตรงตัวก็คือ len(compress(cat(x1,x))) - len(compress(x)) คือจำนวนไบต์เพิ่มเติมที่ต้องใช้ในการบีบอัดความเป็นแบบแผนทางสถิติของ x1 เมื่อกำหนดความเป็นแบบแผนทางสถิติของ x ไว้แล้ว ยิ่ง x1 กับ x คล้ายกันมากเท่าไร จำนวนไบต์เพิ่มที่ต้องใช้ในการบีบอัด cat(x1,x) เทียบกับการบีบอัด x อย่างเดียวก็จะยิ่งน้อยลง
    ผู้เขียนใช้ฟังก์ชันระยะทางชื่อ Normalized Compression Distance (NCD) ที่อิงกับแนวคิดนี้ แล้วนำ k-nearest neighbors (kNN) ไปใช้กับเอกสารที่ถูกบีบอัด นอกจากนี้ยังกล่าวถึงความสัมพันธ์ระหว่าง NCD กับข้อมูล, Shannon entropy และ Kolmogorov complexity
    น่าประหลาดที่วิธีซึ่งเรียบง่ายและเข้าใจได้ตามสัญชาตญาณนี้เอาชนะ BERT ได้ในงาน zero-shot classification หลายงาน อย่างไรก็ตาม ไม่ได้หมายความว่าจะชนะ Transformer ที่ใหญ่กว่าและใหม่กว่าทุกตัวเสมอไป

    • วิธีนี้ทำได้ดีกว่าเฉพาะกับ ข้อมูลนอกการกระจาย และในกรณีที่โทเคนทับซ้อนกันเท่านั้น มันไม่มีความสามารถในการเข้าใจความหมาย ผลลัพธ์อาจถูกต้อง แต่พาดหัวชวนให้เข้าใจผิด
    • สงสัยว่าถ้าใช้การรองรับ compression dictionary ของ zstd แทนการต่อเอกสารเข้าด้วยกันตรงๆ จะได้ผลดีกว่านี้เล็กน้อยไหม
      แนวคิดคือเปรียบเทียบขนาดหลังบีบอัดเมื่อใช้เอกสารเป็น compression dictionary กับเมื่อไม่ใช้ อย่างน้อยในระดับ 20+ นั้น zstd ให้สัดส่วนการบีบอัดดีกว่า gzip มาก ดังนั้นถ้าเหตุผลที่มันได้ผลกับ gzip มาจากการเป็นค่าประมาณของ Kolmogorov complexity ก็อาจจะทำงานได้ดีกว่าเดิม
    • ถ้าปัญหาที่ต้องการแก้สุดท้ายคือ “x คล้าย x1 หรือ x2 มากกว่ากัน” มันก็ดูเป็นปัญหาคนละแบบกับที่ LLM แก้ ดังนั้นถ้ามันทำได้ดีกว่าก็ไม่น่าแปลกใจ
      ถ้า x1 เป็นภาษาอังกฤษ และ x เป็นคำแปลภาษาฮีบรูของเอกสารเดียวกัน ก็น่าจะเป็น LLM ที่ทำได้ดีกว่าไม่ใช่หรือ
    • ถ้าพูดอย่างเคร่งครัด นี่ไม่ใช่ zero-shot แต่เป็น few-shot มากกว่า เพราะยังต้องมีชุดต้นแบบสำหรับการเรียนรู้เพื่อใช้อ้างอิงอยู่ดี
    • สงสัยว่าวิธีเดียวกันนี้จะใช้กับภาพได้ไหม
      ไม่นานมานี้ลองทำกับภาพและให้มันสร้าง JPEG ออกมา พบว่าแม้ใช้พิกเซลพื้นฐานชุดเดียวกันก็ยังได้ภาพที่หลากหลายมาก ยิ่งภาพมี noise มากและดูสุ่มมากขึ้น ขนาดไฟล์ JPG ก็ยิ่งใหญ่ขึ้น ในทางกลับกัน ยิ่งดูเหมือนภาพถ่าย ขนาดไฟล์ JPG ก็ยิ่งเล็กลง ซึ่งน่าสนใจดี

  • ถ้าสนใจความเท่าเทียมกันระหว่าง AI กับการบีบอัด ลองดู Hutter Prize ได้ :) http://prize.hutter1.net/
    Large Text Compression Benchmark ก็น่าดูเช่นกัน http://mattmahoney.net/dc/text.html - ตอนนี้เครื่องมือบีบอัดที่ดีที่สุดในโลกคือโครงข่ายประสาทของ Fabrice Bellard ผู้มีชื่อเสียงจากการสร้าง ffmpeg และ QEMU
    ชอบมากกับ สไตล์สำหรับข้อความล้วน ที่เหมาะเจาะของหน้าเหล่านี้

    • โดยเฉพาะอย่างยิ่ง อัลกอริทึมการบีบอัดที่อิงกับ arithmetic coding ซึ่งปรับ น้ำหนักของช่วง โดยการคาดเดาสิ่งที่จะมาถัดไปนั้นคล้ายกันมาก
      มันปรับ arithmetic coding (https://en.wikipedia.org/wiki/Arithmetic_coding) ตามบริบทของไบต์/บิตที่จะทำนาย ดังนั้นยิ่งทำนายสิ่งที่จะตามมาได้แม่นยำ การเข้ารหัสก็ยิ่งมีประสิทธิภาพ งานนี้เองก็คล้ายกับ Transformer อย่าง GPT มาก
      การทำนายที่สมบูรณ์แบบทำให้ช่วงเชิงคณิตศาสตร์ไม่เล็กลง จึงแทบไม่มีต้นทุนการเก็บข้อมูลเพิ่ม และจึงไม่ต้องเก็บบิตเพิ่มด้วย อย่างไรก็ตาม ถ้าจะ benchmark อย่างยุติธรรม ก็ต้องนับขนาดของตัวถอดบีบอัดด้วย
    • ถ้าขุดคณิตศาสตร์ลงลึกมากพอ หลายสิ่งก็กลายเป็นเรื่องเดียวกันในระดับพื้นฐาน super-resolution ก็คือ deconvolution ที่ถูกห่อให้ดูดี, single-layer perceptron ก็คือ SVM แบบ linear kernel และ logistic regression, ส่วน FFT ก็เป็นแค่การแยกตัวประกอบ
    • จุดสำคัญคือผู้เขียนใช้ Normalized Compression Distance (NCD) NCD เป็นวิธีประมาณค่า Kolmogorov complexity
      นี่เป็นแนวคิดที่ค่อนข้างเก่าแล้ว ดูได้จาก [1,2] แม้จะเก่าแต่ก็ยังมีประโยชน์มากเหมือน perceptron
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard เป็นตำนานที่ยังมีชีวิตจริงๆ ควรเพิ่ม QuickJS, jslinux, tcc และ TinyGL เข้าไปในรายชื่อนั้นด้วย
    • “การบีบอัด” ประเภทนี้โดยแก่นแท้แล้วใกล้เคียงกับ ความเข้าใจผ่านทฤษฎี แบบทฤษฎีทางฟิสิกส์
      ทฤษฎีก็คล้ายเรื่องเล่าที่ใช้อธิบายหลายสิ่งได้ด้วย “ตัวละคร” ชุดเดิม โดยที่ตัวละครในที่นี้ใกล้เคียงกับแนวคิดมากกว่า เช่น อะตอมก็เข้ากับคำอธิบายนี้

  • อยากชี้ว่าที่วิธีนี้แข็งแกร่งกว่านั้นจำกัดอยู่กับ ข่าว เท่านั้น
    บน Yahoo Questions มันไม่ได้ให้ประสิทธิภาพดีที่สุด ข่าวมักเขียนในรูปแบบคล้ายกันและบางครั้งก็มีการคัดลอกบางส่วน จึงไม่เกินเลยที่จะมองว่ามีคำร่วมกันจำนวนมาก
    Yahoo Questions เป็นฟอรัม จึงน่าจะมีความแปรผันของคำสูงกว่า แต่ระหว่างคำเหล่านั้นก็ยังมีความคล้ายคลึงกันทางความหมาย
    กล่าวคือ gzip แข็งแกร่งเมื่อมีคำซ้ำกันมาก (ขนาดที่เพิ่มขึ้นระหว่างบีบอัดด้วย gzip มีน้อย) แต่ถ้าความคล้ายคลึงกันทางความหมายสำคัญ DNN ก็ชนะเสมอ
    ผลลัพธ์น่าสนใจ แต่ผมคิดว่ามันไม่ได้น่าสนใจเท่าที่ฟังดู

    • ถ้าความคล้ายคลึงกันทางความหมายต่างออกไป มันทำงานอย่างไรกันแน่? รู้สึกว่าสุดท้ายแล้วก็เป็นเพียงปัญหาการจัดกลุ่ม representation ที่มีความหมายคล้ายกันระหว่างการฝึกไม่ใช่หรือ

  • ต้องให้ความสำคัญมากว่าผลลัพธ์นี้มาจาก ข้อมูลนอกการกระจาย ตัวอย่างเช่นเป็นข่าวในภาษาอย่าง ‘Kinyarwanda, Kirundi, Pinyin’
    ในการตั้งค่าที่ทั่วไปกว่านี้ BERT ยังชนะขาดอยู่ดี
    มันน่าทึ่งที่วิธีง่าย ๆ แบบนี้มีประสิทธิภาพได้มาก แต่ก็ไม่ควรโหมขายเกินจริง

    • ประเด็นนี้ควรถูกเน้นให้มากกว่านี้จริง ๆ ตอนอ่านแค่พาดหัว ฉันถึงกับทึ่งเหมือนไปเจอหลักฐานของกฎฟิสิกส์ที่ไม่เคยรู้มาก่อนและยังอธิบายไม่ได้ หรือในกรณีนี้คือกฎทางภาษาศาสตร์ โดยบังเอิญ
      แต่พอดูเงื่อนไขที่ยกมา มันกลับค่อนข้างตรงไปตรงมามากกว่า การจัดหมวดหมู่ข้อความในภาษาที่ไม่รู้จักเลยหมายความว่าอย่างไร? ถ้าให้จัดหมวดหมู่ข้อความ Kirundi โดยที่เราไม่เข้าใจความหมายเลย สิ่งที่ดีที่สุดที่ทำได้ก็คือหาความถี่ของลำดับคำหรืออักขระ แล้วจัดกลุ่มข้อความที่มีลายนิ้วมือความถี่คล้ายกันเข้าด้วยกัน
      เรายังไม่รู้ความหมายจริงอยู่ดี แต่ก็ดีกว่าสุ่ม และในทางปฏิบัติมันก็เป็นแบบนั้น ข่าวดีก็คือนี่คือสิ่งที่ gzip+kNN ทำอยู่พอดี และเป็นงานหลักรวมถึงเหตุผลที่มันมีอยู่
      ต่อให้อ่านข้อความนี้แล้วพยายามทำความเข้าใจหรือทำนายอักขระถัดไป ก็แทบไม่ได้อะไรเพิ่ม คนปกติถ้าไม่รู้ภาษา ก็คงไม่คิดจะลองทำตั้งแต่แรก น่าเสียดายที่ BERT ทำสิ่งนั้นพอดี เพราะนั่นคือสิ่งเดียวที่ BERT ทำเป็น ถึงอย่างนั้นก็น่ายกย่องที่มันยังดึงประโยชน์ได้มากกว่ามนุษย์ทั่วไป หรืออาจมากกว่ามนุษย์ที่ไม่ทั่วไปเสียอีก

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

    • เป็นเทคนิคที่มีคนรู้จักอยู่ แต่ก็ยังไม่ค่อยเป็นที่รู้จักนัก สิ่งที่มีส่วนสำคัญหลัก ๆ ที่นี่คือ การทำให้เป็นกรอบนิยามและการวัดผล

  • ดูเหมือนนี่จะไม่ใช่ชัยชนะของวิธีนี้เท่าไร แต่เป็นสัญญาณเชิงลบต่อ ความคล้ายคลึงแบบดีปเลิร์นนิง มากกว่า
    ท่ามกลางกระแส LLM แม้ LLM จะยอดเยี่ยมจริง แต่ดูเหมือนหลายคนจะสมมติว่าความก้าวหน้าแบบเดียวกันเกิดขึ้นกับชั้น embedding สำหรับความคล้ายคลึงของข้อความล้วน ๆ ด้วย
    เลยเกิดกระแสฐานข้อมูล embedding เต็มไปหมด แต่เท่าที่ฉันเห็น แทบไม่มีหลักฐานมารองรับเลย

    • https://twitter.com/eugeneyan/status/1678060204943097863

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      เกร็ดที่น่าสนใจ: ความคล้ายคลึงระหว่างคิวรีกับเอกสารถูกจัดการด้วย TF-IDF แบบง่าย ๆ ไม่ใช่เวกเตอร์ มันทำได้ดีกว่าการค้นหาแบบเวกเตอร์เมื่อจำนวนเอกสารเกิน 45 รายการ และในทางปฏิบัติพวกเขาใช้ 50 รายการ
      https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa...
      This case illustrates that in-domain effectiveness does not necessarily transfer to an out-of-domain zero-shot application of the model. Generally, as observed on the BEIR dense leaderboard, dense embeddings models trained on NQ labels underperform the BM25 baseline across almost all BEIR datasets.

    • ช่วยตอบคำถามหนึ่งข้อได้ไหม เวลาใช้ LLM เพื่อสร้าง text embedding สำหรับวัดความคล้ายคลึง เขาใช้ชั้นไหนกัน? ชั้นอินพุต? อินพุต+position encoding? ชั้นซ่อน? หรือชั้นเอาต์พุต?

  • ลิงก์ควรชี้ไปที่ PDF ของงานวิจัย https://aclanthology.org/2023.findings-acl.426.pdf

  • อัลกอริทึมการบีบอัดคือการ ประหยัด/บีบอัด พื้นที่ นั่นคือบิตและไบต์ ส่วนโมเดลแมชชีนเลิร์นนิง โดยเฉพาะโมเดลเชิงกำเนิด คือการประหยัด/บีบอัดการแสดงออกและความคิดของมนุษย์
    การจัดหมวดหมู่ข้อความคือการบีบอัดชนิดหนึ่งบนชั้นของการแสดงออกของมนุษย์ มีคุณสมบัติพื้นฐานบางอย่างของภาษามนุษย์และข้อมูลหรือไม่ ที่อาจอธิบายได้ว่าอะไรจะทำงานได้ดีกว่าในงานแมชชีนเลิร์นนิง?
    ถ้าวันหนึ่งทฤษฎีแบบนั้นเริ่มเป็นรูปเป็นร่าง ก็อาจไม่ใช่เรื่องน่าแปลกใจที่การเข้ารหัสของบิต/ไบต์ที่ถูกบีบอัด กับการแสดงออกของมนุษย์ที่ถูกบีบอัด จะมีความเกี่ยวข้องกันอย่างใกล้ชิดในปริภูมิบางแบบ จนทั้งสองอย่างเชื่อมโยงกันได้ไม่ทางใดก็ทางหนึ่ง ที่จริงแล้ว ทฤษฎีลักษณะนี้ เช่น ทฤษฎีบนฐานเอนโทรปีหรือฐานฟิสิกส์ อาจช่วยเลือกได้ว่าในการบีบอัดการแสดงออกของมนุษย์บางประเภท ควรใช้อัลกอริทึมบีบอัดหรือใช้โมเดลแมชชีนเลิร์นนิง
    ถ้ามองจากฝั่งข้อมูล ตัวอย่างเชิงลบที่ยากซึ่งทำให้อัลกอริทึมแบบนี้ทำงานได้ไม่ดีคืออะไร? ตอนนี้เราอาจทำได้เพียงประมาณทฤษฎีนั้นผ่านมุมมองของชนิดข้อมูลข้อความมนุษย์ที่หลากหลาย เช่น การทำนายส่วนผสมด้วย statistical topic model ทำได้ดีในข้อความวิชาการ แต่กลับมีปัญหากับข้อความบนอินเทอร์เน็ต
    มีใครศึกษาเรื่องทฤษฎีแบบนี้บ้างไหม นอกจาก Wolfram Physics?

    • ทำให้นึกถึงบทความชวนถกเถียงของ Ted Chiang เรื่อง ChatGPT Is a Blurry JPEG of the Web จำได้ว่าใน HN ไม่ค่อยชอบกันเท่าไร แต่ก็มีประเด็นที่ดีอยู่
      https://www.newyorker.com/tech/annals-of-technology/chatgpt-...

  • ฟังดูสมเหตุสมผลทั้งหมด การบีบอัดเกี่ยวข้องกับ “ความเข้าใจ” นั่นคือการแทนอินพุตในรูปแบบที่สามารถจดจำและติดป้ายกำกับได้
    ถ้าบิตที่จดจำได้มีขนาดใหญ่กว่าป้ายกำกับ ก็ปิ๊งเลย นั่นคือการบีบอัด จึงไม่น่าแปลกที่ gzip อาจทำงานนี้ได้ดีกว่า DNN

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

  • ฉันไม่เข้าใจว่า gzip จะจัดการกับคำอย่าง “not” ที่กลับความหมายของทั้งประโยคได้อย่างไร
    มีใครเข้าใจไหม?

    • อย่างที่มีคนพูดในคอมเมนต์บางส่วนบน Twitter นี่เป็นงานสำหรับ topic modeling คำปฏิเสธอาจสำคัญน้อยกว่าที่เป็นในงานอย่าง sentiment analysis