टेक्स्ट classification में Gzip और KNN, Transformers से बेहतर प्रदर्शन करते हैं

 (twitter.com/LukeGessler)
2 पॉइंट द्वारा GN⁺ 2023-07-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • gzip जैसे सरल compressor और k-nearest neighbors (kNN) classifier को मिलाकर एक non-parametric टेक्स्ट classification तरीका प्रस्तावित
  • training parameters बिल्कुल नहीं होने के बावजूद हल्का और general-purpose, और DNN की तुलना में computational cost कम
  • pretrained नहीं किए गए deep learning तरीकों की तुलना में 6 in-distribution datasets पर प्रतिस्पर्धी नतीजे हासिल
  • 4 low-resource languages सहित सभी 5 OOD (out-of-distribution) datasets पर BERT से बेहतर प्रदर्शन
  • labeled data की कमी के कारण DNN training कठिन होने वाले few-shot environments में भी उत्कृष्ट performance

पृष्ठभूमि और समस्या

  • DNN का इस्तेमाल उच्च accuracy के कारण टेक्स्ट classification में व्यापक रूप से होता है
  • लेकिन इन्हें लाखों parameters और बड़ी मात्रा में labeled data चाहिए, जिससे computational cost अधिक होती है
  • इसके चलते usage, optimization, और OOD (out-of-distribution) situations में transfer व्यावहारिक रूप से महंगे काम बन जाते हैं

प्रस्तावित तरीका

  • DNN के विकल्प के रूप में एक आसान, हल्का और general-purpose non-parametric तरीका पेश
  • gzip जैसे सरल compressor और k-nearest neighbors classifier को मिलाने वाली संरचना
  • इसका मुख्य feature है कि इसमें training parameters बिल्कुल नहीं हैं

प्रयोगों के नतीजे

  • 6 in-distribution datasets पर pretrained नहीं किए गए deep learning तरीकों से प्रतिस्पर्धी स्तर का performance
  • 4 low-resource languages सहित सभी 5 OOD datasets पर BERT से बेहतर प्रदर्शन
  • labeled data बहुत कम होने के कारण DNN को प्रभावी ढंग से train करना कठिन होने वाले few-shot environments में भी मजबूत प्रदर्शन

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-15
Hacker News टिप्पणियाँ

  • पेपर का सीधा लिंक: https://aclanthology.org/2023.findings-acl.426.pdf
    सहज रूप से मुख्य बात यह है कि जब दस्तावेज़ x1, x2 और नया दस्तावेज़ x दिया हो, तो अगर x की सांख्यिकीय नियमितता x2 की तुलना में x1 के अधिक करीब है, तो len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)) होगा। यहाँ cat का मतलब जोड़ना/साथ रखना है, और compress gzip जैसे compressor को दर्शाता है
    शाब्दिक रूप से len(compress(cat(x1,x))) - len(compress(x)) x की सांख्यिकीय नियमितता दिए जाने पर x1 की सांख्यिकीय नियमितता को compress करने के लिए अतिरिक्त रूप से आवश्यक bytes की संख्या है। x1 और x जितने अधिक समान होंगे, केवल x को compress करने की तुलना में cat(x1,x) को compress करने के लिए उतने ही कम अतिरिक्त bytes लगेंगे
    लेखकों ने इस विचार पर आधारित Normalized Compression Distance (NCD) नामक distance function का उपयोग करके compressed documents पर k-nearest neighbors (kNN) लागू किया। NCD, information, Shannon entropy, और Kolmogorov complexity के बीच संबंधों पर भी चर्चा की गई है
    हैरानी की बात है कि यह सरल और सहज तरीका कई zero-shot classification कार्यों में BERT से बेहतर निकलता है। हालाँकि इसका यह मतलब नहीं है कि यह ज़रूरी तौर पर बड़े और नए Transformer models को भी हरा देता है

    • यह तरीका केवल out-of-distribution data में और तब बेहतर काम करता है जब tokens overlap करते हों। इसमें semantic understanding नहीं है, नतीजे सही हो सकते हैं लेकिन शीर्षक भ्रमित करने वाला है
    • केवल दस्तावेज़ों को जोड़ने की बजाय अगर zstd compression dictionary support का उपयोग किया जाए तो शायद थोड़े बेहतर परिणाम मिलें
      यानी दस्तावेज़ को compression dictionary की तरह इस्तेमाल करने पर और न करने पर compression size की तुलना की जाए। zstd कम-से-कम 20+ levels पर gzip की तुलना में बहुत अधिक compression ratio देता है, इसलिए अगर gzip में अच्छा काम करने का कारण Kolmogorov complexity approximation है, तो यह और बेहतर काम कर सकता है
    • अगर हल की जाने वाली समस्या आखिरकार “x, x1 और x2 में से किसके अधिक समान है” जैसी है, तो यह LLM द्वारा हल की जाने वाली समस्या से अलग लगती है, इसलिए इसका बेहतर प्रदर्शन करना इतना चौंकाने वाला नहीं है
      अगर x1 अंग्रेज़ी में है और x उसी दस्तावेज़ का Hebrew अनुवाद है, तो शायद LLM बेहतर करेगा
    • तकनीकी रूप से यह zero-shot नहीं बल्कि few-shot है। अब भी reference के लिए training prototypes के एक set की ज़रूरत होती है
    • क्या यही तरीका images पर भी लागू हो सकता है, यह जानने की जिज्ञासा है
      हाल में images के साथ काम करते हुए JPEG output देखा, और पाया कि एक ही base pixels से भी बहुत अलग-अलग images निकल सकती हैं। यह दिलचस्प है कि image जितनी अधिक noisy और random जैसी होती है, JPG file size उतना बढ़ता है, और उलटे जितनी photo जैसी दिखती है, JPG size उतना छोटा हो जाता है

  • अगर आपको AI और compression की समतुल्यता में रुचि है, तो Hutter Prize देखना अच्छा रहेगा :) http://prize.hutter1.net/
    Large Text Compression Benchmark भी देखने लायक है http://mattmahoney.net/dc/text.html - इस समय दुनिया का सर्वश्रेष्ठ compressor ffmpeg और QEMU बनाने वाले प्रसिद्ध Fabrice Bellard का neural network है
    मुझे इन पेजों की उपयुक्त text-only style भी सचमुच बहुत पसंद है

    • खासकर arithmetic coding आधारित compression algorithms, जो आगे आने वाली सामग्री का अनुमान लगाकर interval weights समायोजित करते हैं, बहुत समान लगते हैं
      वे arithmetic coding(https://en.wikipedia.org/wiki/Arithmetic_coding) को उस context के अनुसार समायोजित करते हैं जिसमें अगला byte/bit अनुमानित किया जाना है, इसलिए जितना अधिक सटीक अनुमान होगा, encoding उतनी ही efficient होगी। यह काम स्वयं GPT जैसे Transformer से काफ़ी मिलता-जुलता है
      perfect prediction में arithmetic interval छोटा नहीं होता, इसलिए अतिरिक्त storage cost लगभग नहीं के बराबर होती है, और परिणामस्वरूप bits भी संग्रहित नहीं होते। लेकिन निष्पक्ष benchmark के लिए decompressor का आकार भी गिनना चाहिए
    • गणित में गहराई तक जाएँ तो बहुत-सी चीज़ें मूल रूप से एक जैसी हो जाती हैं। super-resolution दरअसल आकर्षक पैकेजिंग में deconvolution है, single-layer perceptron एक linear-kernel SVM भी है और logistic regression भी, और FFT मूलतः सिर्फ factorization है
    • यह महत्वपूर्ण है कि लेखक Normalized Compression Distance (NCD) का उपयोग करते हैं। NCD, Kolmogorov complexity का approximation करने का एक तरीका है
      यह काफ़ी पुराना विचार है, [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 भी जोड़ने चाहिए
    • इस तरह का “compression” मूल रूप से physics theories जैसी theory through understanding के क़रीब है
      theory उस कहानी जैसी होती है जो एक ही “characters” से बहुत-सी चीज़ें समझा देती है। यहाँ characters का अर्थ concepts से अधिक है, उदाहरण के लिए atoms इस पर फिट बैठते हैं

  • मैं यह बताना चाहूँगा कि इस तरीके की मज़बूती news तक सीमित है
    Yahoo Questions में यह सर्वोत्तम प्रदर्शन नहीं देता। यह मानना अनुचित नहीं है कि news एक जैसे ढंग से लिखी जाती है और कभी-कभी उसके हिस्से कॉपी भी हो जाते हैं, इसलिए common words अधिक होते हैं
    Yahoo Questions एक forum है, इसलिए शब्दों में विविधता अधिक होगी, लेकिन शब्दों के बीच semantic similarity भी होती है
    यानी gzip तब मज़बूत है जब शब्दों में बहुत overlap हो (gzip compression के दौरान size में बढ़ोतरी कम होती है), और जहाँ semantic similarity महत्वपूर्ण हो, वहाँ DNN हमेशा जीतता है
    नतीजे दिलचस्प हैं, लेकिन मेरी नज़र में वे सुनने में जितने दिलचस्प लगते हैं उतने नहीं हैं

    • अगर semantic similarity अलग चीज़ है, तो वह काम कैसे करती होगी? मुझे लगता है कि training के दौरान semantic रूप से समान representations को समूहित करने की समस्या भर है

  • यह बहुत महत्वपूर्ण है कि यह नतीजा out-of-distribution data से आया है। उदाहरण के लिए, यह ‘Kinyarwanda, Kirundi, Pinyin’ जैसी भाषाओं की ख़बरें हैं
    ज़्यादा सामान्य सेटिंग्स में BERT अब भी भारी बढ़त से जीतता है
    यह अच्छा है कि इतनी सरल विधि बेहद प्रभावी हो सकती है, लेकिन इसे बढ़ा-चढ़ाकर नहीं बेचना चाहिए

    • इस बात पर सच में और ज़ोर दिया जाना चाहिए। सिर्फ़ शीर्षक पढ़ने पर यह ऐसा चौंकाने वाला लगा जैसे किसी ने पहले से अज्ञात और अब तक अस्पष्ट किसी भौतिक नियम, इस मामले में भाषावैज्ञानिक नियम, का सबूत संयोग से खोज लिया हो
      लेकिन बताए गए हालात देखें तो यह काफ़ी सहज लगता है। ऐसी भाषा के टेक्स्ट को वर्गीकृत करना जिसे आप बिल्कुल नहीं जानते, इसका मतलब क्या है? अगर आपसे Kirundi टेक्स्ट को वर्गीकृत करने को कहा जाए, तो आप उसका अर्थ बिल्कुल नहीं जानते होंगे, और आप जो सबसे अच्छा कर सकते हैं वह है शब्दों या अक्षर अनुक्रमों की आवृत्ति ढूँढना और मिलती-जुलती आवृत्ति-छाप वाले टेक्स्ट को एक साथ समूहित करना
      आप अब भी वास्तविक अर्थ नहीं जानते, लेकिन यह रैंडम से बेहतर हो सकता है, और वास्तव में ऐसा होता भी है। अच्छी बात यह है कि gzip+kNN ठीक यही करता है, यही इसका असली काम है और इसी के लिए यह मौजूद है
      इस टेक्स्ट को पढ़कर समझने या अगला अक्षर अनुमान लगाने की कोशिश करने से ज़्यादा कुछ हासिल नहीं होगा। कोई सामान्य इंसान भाषा नहीं जानता हो तो शुरू से ऐसा करने की कोशिश भी नहीं करेगा। दुर्भाग्य से BERT ठीक वही करता है। क्योंकि BERT को मूलतः वही एक काम आता है। फिर भी, एक सामान्य इंसान, शायद असामान्य इंसान से भी ज़्यादा उपयोगिता निकाल लेना, बधाई के लायक है

  • यह वास्तव में बहुत चतुर है और सहज रूप से समझ आता है
    अगर आप मिलते-जुलते टेक्स्ट के दो हिस्से जोड़ दें, तो वे अलग-अलग टेक्स्ट के दो हिस्से जोड़ने की तुलना में बेहतर compress होंगे

    • यह ज्ञात तो है, लेकिन कुछ हद तक कम-ज्ञात तकनीक है। यहाँ मुख्य योगदान formalization और measurement है

  • यह इस विधि की जीत से ज़्यादा deep learning-based similarity के लिए एक नकारात्मक संकेत जैसा लगता है
    LLM के इस उछाल के बीच, यह सच है कि LLM प्रभावशाली हैं, लेकिन लगता है बहुत से लोग मान लेते हैं कि pure text similarity के लिए embedding layer में भी वैसी ही प्रगति हुई होगी
    इसी वजह से हर तरह के embedding database का बूम आया, लेकिन मेरी नज़र में उसे समर्थन देने वाले सबूत बहुत कम हैं

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

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      दिलचस्प बात: query-document similarity को vector से नहीं बल्कि साधारण TF-IDF से हैंडल किया गया। जब retrieved documents की संख्या 45 से ऊपर गई, तो इसने vector search से बेहतर प्रदर्शन किया, और वास्तव में 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 से similarity measurement के लिए text embeddings बनाते समय कौन-सी layer इस्तेमाल की जाती है? input layer? input layer+positional encoding? hidden layer? output layer?

  • लिंक को पेपर PDF https://aclanthology.org/2023.findings-acl.426.pdf की ओर जाना चाहिए

  • compression algorithm जगह, यानी bits और bytes की बचत/संपीड़न है। machine learning models, ख़ासकर generative models, इंसानी अभिव्यक्ति और सोच की बचत/संपीड़न हैं
    text classification, इंसानी अभिव्यक्ति के ऊपर compression का एक प्रकार है। क्या इंसानी भाषा और डेटा की कोई बुनियादी विशेषता हो सकती है जो समझाए कि machine learning tasks में कौन-सा तरीका बेहतर होगा?
    कभी न कभी अगर ऐसी कोई theory आकार लेती है, तो शायद यह चौंकाने वाली बात नहीं होगी कि compressed bits/bytes की encoding और compressed human expression किसी space में काफ़ी क़रीब से जुड़े हों और दोनों किसी न किसी तरह से संबंधित हों। वास्तव में, ऐसी theory, जैसे entropy-based या physics-based theory, यह चुनने में मदद कर सकती है कि मानव अभिव्यक्ति के किसी ख़ास प्रकार के compression के लिए compression algorithm इस्तेमाल करें या machine learning model
    डेटा-केंद्रित नज़रिये से देखें, तो ऐसे कौन-से hard negative examples होंगे जो इस तरह के algorithm को कमज़ोर बनाते हों? फ़िलहाल शायद हम ऐसी theory का सिर्फ़ अनुमान ही लगा सकते हैं, वह भी अलग-अलग तरह के मानवीय टेक्स्ट डेटा के संदर्भ में। उदाहरण के लिए, statistical topic model से मिश्रण का अनुमान लगाना academic text पर अच्छा काम करता है, लेकिन internet text पर कठिनाई आती है
    क्या Wolfram Physics के अलावा कोई और भी ऐसी theory पर काम कर रहा है?

    • Ted Chiang का विवादास्पद लेख ChatGPT Is a Blurry JPEG of the Web याद आता है। याद पड़ता है कि HN पर इसे ज़्यादा पसंद नहीं किया गया था, लेकिन इसने कुछ अच्छे बिंदु उठाए थे
      https://www.newyorker.com/tech/annals-of-technology/chatgpt-...

  • यह पूरी तरह समझ में आता है। compression “समझ” के बारे में है, यानी input को इस तरह represent करना कि उसे पहचाना और label किया जा सके
    अगर पहचाने गए bits label से बड़े हो जाएँ, तो लीजिए, compression हो गया। यह चौंकाने वाली बात नहीं कि gzip इस काम में DNN से बेहतर हो सकता है

    • तब यह सोचने वाली बात है कि क्या दूसरे compression algorithms और बेहतर कर सकते हैं
    • मैं compression को understanding का subset मानता हूँ। जब कोई बच्चा व्याकरण की दृष्टि से सही बोलना शुरू करता है, तो वह सामने आए सभी language patterns को grammar rules में compress कर चुका होता है
      इसे subset इसलिए कह रहा हूँ क्योंकि understanding ज़्यादा सामान्य है। कोई विशिष्ट compression algorithm floating-point numbers पर अच्छा काम कर सकता है। इसके उलट, दिमाग और artificial neural networks शायद प्रदर्शन में कमज़ोर हों, फिर भी वे किसी भी input pattern को compress कर सकते हैं

  • मुझे समझ नहीं आता कि gzip “not” जैसे शब्दों को कैसे संभाल सकता है जो पूरे वाक्य का अर्थ उलट देते हैं
    कोई समझता है?

    • जैसा Twitter पर कुछ टिप्पणियों में भी कहा गया है, यह topic modeling के लिए है। negation, sentiment analysis जैसे कामों की तुलना में यहाँ कम महत्वपूर्ण हो सकता है