निर्णय वृक्ष – नेस्टेड decision rules की हैरान करने वाली ताकत

• डेटा को वर्गीकृत करने के लिए feature space को बार-बार विभाजित करने वाली संरचना, जिसमें हर चरण पर सबसे अधिक information gain देने वाला विभाजन चुना जाता है
• Entropy का उपयोग करके डेटा की purity मापी जाती है, और इसी के आधार पर Information Gain की गणना की जाती है
• ID3 algorithm parent node और child node की entropy के अंतर की गणना करके सबसे उपयुक्त split point ढूँढता है और tree को recursively विस्तार देता है
• Entropy की जगह Gini impurity का भी उपयोग किया जा सकता है, और दोनों तरीके अधिकांश मामलों में मिलते-जुलते परिणाम देते हैं, हालांकि उनकी computational efficiency अलग होती है
• अत्यधिक विभाजन overfitting और instability पैदा कर सकता है, इसलिए pruning या Random Forest से इसे कम किया जाता है

---

निर्णय वृक्ष की बुनियादी अवधारणा

• निर्णय वृक्ष डेटा को ऊपर से नीचे की ओर विभाजित करता है, और हर चरण में conditional rules लागू करके डेटा को अच्छी तरह अलग होने वाले क्षेत्रों में बाँटता है
  • हर विभाजन डेटा के किसी खास feature और threshold value के आधार पर तय होता है
  • लक्ष्य यह है कि classification के समय ऐसे pure nodes बनाए जाएँ जिनमें classes स्पष्ट रूप से अलग हों

Entropy की परिभाषा और गुण

• Entropy सूचना की अनिश्चितता को मापने वाला एक मानक है, और probability (p_i) के लिए इसे (H = -\sum p_i \log_2(p_i)) के रूप में परिभाषित किया जाता है
• मुख्य गुण
  1. जब केवल एक घटना की probability 1 हो और बाकी सभी 0 हों, तब (H=0), यानी कोई अनिश्चितता नहीं
  2. जब सभी घटनाओं की probabilities समान हों, तब entropy अधिकतम होती है और यह सबसे अधिक impure स्थिति को दर्शाती है
  3. probabilities जितनी अधिक समान होती जाती हैं, entropy उतनी बढ़ती है
• इसलिए pure node की entropy 0 होती है, जबकि mixed node की entropy अधिक होती है

Information Gain और ID3 algorithm

• Information Gain को विभाजन से पहले और बाद की entropy के अंतर से निकाला जाता है, और यह डेटा विभाजन की दक्षता को दर्शाता है
  • सूत्र: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
• ID3 algorithm के चरण
  1. हर feature की entropy की गणना
  2. अलग-अलग splitting criteria के आधार पर dataset को बाँटना और information gain की गणना
  3. सबसे अधिक information gain वाले विभाजन को चुनकर decision node बनाना
  4. जब आगे विभाजन संभव न हो, तब leaf node बनाना
  5. सभी subsets पर recursion चलाना, लेकिन यदि सभी elements एक ही class के हों तो रुक जाना
• उदाहरण के तौर पर, Diameter ≤ 0.45 शर्त का information gain 0.574 सबसे अधिक था, इसलिए इसे पहले विभाजन के रूप में चुना गया

Gini impurity और वैकल्पिक मापन

• Gini impurity entropy का एक विकल्प है, जो सूचना की impurity मापने का एक दूसरा तरीका है
  • इसमें logarithm की गणना नहीं होती, इसलिए गणना की गति तेज होती है
  • imbalanced datasets में entropy कभी-कभी अधिक सावधानीपूर्ण विकल्प हो सकता है
• दोनों तरीके सामान्यतः समान प्रकार के परिणाम देते हैं

Overfitting और instability की समस्या

• ID3 algorithm entropy को न्यूनतम करने के लिए लगातार विभाजन करता रहता है, इसलिए tree बहुत अधिक गहरा हो सकता है
  • इससे overfitting होता है और नए डेटा पर generalization performance घट जाती है
• साथ ही डेटा में छोटे बदलाव से भी tree structure बहुत बदल सकता है, जिसे instability (high variance) की समस्या कहा जाता है
  • उदाहरण: training data के 5% में हल्का Gaussian noise जोड़ने पर भी पूरी तरह अलग tree बन सकता है
• समाधान के रूप में pruning के जरिए tree की depth, leaf की संख्या, minimum sample count आदि सीमित किए जा सकते हैं

Random Forest तक विस्तार

• एकल निर्णय वृक्ष की instability कम करने के लिए कई trees को अलग-अलग data samples पर train करके उनकी predictions को मिलाने का तरीका इस्तेमाल किया जाता है
  • यही तरीका Random Forest कहलाता है, जो अधिक stability और बेहतर generalization performance देता है
• यह निर्णय वृक्ष की कमियों की भरपाई करता है और आज तक के सबसे सफल machine learning algorithms में से एक माना जाता है

निष्कर्ष और आगे की सीख

• निर्णय वृक्ष ऐसा model है जिसे समझना आसान है, जिसकी training तेज है, और जिसकी preprocessing सरल है
• लेकिन overfitting और instability की समस्याओं को हल करने के लिए pruning या ensemble techniques की आवश्यकता होती है
• लेख में regression trees, end-cut preference, hyperparameters आदि पर चर्चा नहीं की गई है, और संबंधित सामग्री के जरिए आगे सीखने की सलाह दी गई है

[GN⁺]

Hacker News टिप्पणियाँ

• जब मैं classifiers सीख रहा था, तो मेरे लिए बहुत अच्छा काम करने वाला एक secret weapon यह था कि पहले एक अच्छा linear classifier train किया जाए
  फिर उस linear classifier के non-threshold output value को एक अतिरिक्त feature dimension की तरह इस्तेमाल करके decision tree train किया जाए, और उसे एक boosted tree system से wrap किया जाए
  इससे decision tree की कमजोरियों को linear model पूरा कर देता है, और linear model जिन हिस्सों में संघर्ष करता है, उन्हें tree संभाल लेता है
  data rotation या axis normalization पर भी विचार किया जा सकता है, लेकिन ज़्यादातर मामलों में इसकी ज़रूरत नहीं पड़ी
  हाँ, जब features बहुत sparse हों, तब tree के लिए split point ढूँढना मुश्किल हो जाता है

  • सोचें तो यह reinforcement learning में इस्तेमाल होने वाले एक मिलते-जुलते approach जैसा है
    raw state में अतिरिक्त computation जोड़कर observed state बनाया जाता है और उसी पर training होती है
    उदाहरण के लिए, Snake game में सिर्फ़ साँप के coordinates ही नहीं, बल्कि escape paths की संख्या जैसे derived features भी निकालकर training की जाती है
  • decision tree की Achilles' heel आखिरकार feature engineering ही है
    अगर data को साफ़ न किया जाए और features अच्छी तरह design न किए जाएँ, तो इसका नतीजा neural network जैसे black-box models से काफ़ी खराब आ सकता है
    विडंबना यह है कि neural networks ऐसे latent features खुद ढूँढ लेते हैं, लेकिन वे ऐसा कैसे करते हैं, इसे समझना मुश्किल है
  • अलग-अलग उद्देश्यों के लिए tree के कई variants हैं
    Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), Hierarchical Mixture of Experts (HME) इसके उदाहरण हैं
  • “equi-label क्षेत्रों की एक partitioned structure होती है” इस अभिव्यक्ति का ठीक-ठीक मतलब क्या है, यह जानना चाहता हूँ
  • यह विचार Arjovsky और Bottou आदि के IRM paper के मूल विचार से भी मिलता-जुलता लगता है

• 2010 के आसपास जब मैं CERN में काम कर रहा था, तब Boosted Decision Tree सबसे लोकप्रिय classifier था
  इसकी वजह explainability और expressive power के बीच का संतुलन था, और उस समय physics analysis में neural network का इस्तेमाल करने से सांस्कृतिक रूप से हिचक थी
  अब समय काफ़ी बदल चुका है

  • यह बदलाव थोड़ा चिंताजनक लगता है
    physics में सिर्फ़ curves को अच्छी तरह fit करना पर्याप्त नहीं होता, causal mechanism को समझना ज़्यादा महत्वपूर्ण है
    जैसे Ptolemy का epicycle सिस्टम खगोलीय गतियों को बेहतर fit करता था, लेकिन कारण की व्याख्या नहीं करता था
  • मैं भी physics (theory) background से हूँ, और दूसरे क्षेत्रों में decision tree इस्तेमाल करने पर लगा कि “explainability” कुछ हद तक overvalued है
    depth थोड़ा भी बढ़ जाए तो यह लगभग uninterpretably jungle बन जाता है
    neural network में भी internal operations को trace तो किया जा सकता है, लेकिन आखिर उसने वह निर्णय क्यों लिया, यह फिर भी नहीं पता चलता
  • क्या Boosted Decision Tree और Boosted Random Forest एक ही चीज़ हैं?

• उसी साइट पर Random Forest की व्याख्या भी है → mlu-explain/random-forest

  • दूसरे resources भी हैं → mlu-explain पूरी सूची

• एक दिलचस्प बात: single-bit neural network असल में लगभग decision tree ही है
  सिद्धांत रूप से ज़्यादातर neural networks को if-else chain में “compile” किया जा सकता है, लेकिन यह कब अच्छी तरह काम करता है, यह अभी भी साफ़ नहीं है

  • मैंने “neural networks are decision trees” वाला paper (arXiv:2210.05189) पढ़ा है, लेकिन व्यवहार में tree बहुत विशाल हो जाता है
    यह concept को extend करने जैसा ज़्यादा लगता है, सीधे mapping जैसा कम
    इसलिए यह किस अर्थ में कहा गया है, इस पर और स्पष्टीकरण अच्छा होगा
  • क्या ऐसा करने वाला कोई software या paper है? weekend project के रूप में यह मज़ेदार हो सकता है

• decision tree का सबसे बड़ा फ़ायदा उसकी speed है
  low-latency environment में tree-based classifier को छोटे neural network से बदलने की कोशिश की, लेकिन neural network की accuracy थोड़ी बेहतर होने के बावजूद inference latency 100 गुना से भी ज़्यादा थी

  • साथ ही, single decision tree को सीधे edge device पर port करना आसान होता है
    जबकि boosted या bagged trees जटिल हो जाते हैं, और दूसरे classical ML algorithms की portability भी कम होती है

• किसी ML textbook (शायद ESL) में decision tree का वर्णन कुछ ऐसे किया गया था
  “interpretable, fast, कई तरह के data पर अच्छा काम करता है, scaling के प्रति insensitive है, tuning parameters भी कम हैं... लेकिन अच्छा काम नहीं करता”
  हालाँकि bagging या boosting से इस कमी को कुछ हद तक पूरा किया जा सकता है, लेकिन उस प्रक्रिया में इसके मूल फ़ायदों का एक हिस्सा खो जाता है

• मुझे decision tree वास्तव में बहुत पसंद हैं। यह मेरा सबसे पसंदीदा classical ML algorithm है
  मैंने GNU Guile में इसका एक pure functional parallel implementation बनाया है → code link
  लेकिन Guile में NumPy या DataFrame जैसी चीज़ें नहीं हैं, इसलिए data representation inefficient हो जाती है

  • मैं जानना चाहता हूँ कि NumPy या DataFrame, Guile की तुलना में किन मायनों में बेहतर हैं
    Guile tree manipulation के लिए उपयुक्त है, इसलिए decision tree implementation के लिए स्वाभाविक लगता है
    हालाँकि अगर इसे machine code में compile किया जाए, तो यह और अधिक efficient होगा
    संदर्भ के लिए Lush(https://lush.sourceforge.net/) या aiscm(https://wedesoft.github.io/aiscm/) भी देखने लायक हैं

• विशेषज्ञों के अस्पष्ट निर्णय-निर्माण को भी अक्सर सरल decision tree या decision chain से model किया जा सकता है
  विशेषज्ञ खुद सोचते हैं कि उनका निर्णय बहुत जटिल है, लेकिन वास्तव में एक साधारण tree कई बार बेहतर explanation देता है
  पहले regression या distance-based clustering ज़्यादा sophisticated लगते थे, लेकिन tree कहीं अधिक प्रभावी है
  इससे जुड़ी बात Oxford Handbook of Expertise के अध्याय 7 में विस्तार से दी गई है

  • मैंने पहले एक visualization देखा था जिसमें निर्णयों को 2D plane में space partitioning के रूप में दिखाया गया था
    अंततः decision tree, kD-Tree की तरह possibility space को बाँटता है और हर क्षेत्र को एक action सौंप देता है
    विशेषज्ञ के सूक्ष्म निर्णय boundary surfaces की बारीकी से आते हैं, लेकिन tree भी काफ़ी अच्छा approximation देता है

• साइट दिलचस्प थी और presentation भी अच्छी थी
  लेकिन कुछ text में color contrast कम था, इसलिए पढ़ना मुश्किल हुआ

  • मैं भी सहमत हूँ। Firefox Reader View बहुत मददगार है
    accessibility सिर्फ़ दिव्यांग लोगों के लिए नहीं, बल्कि readability बढ़ाने का एक बुनियादी तत्व है

• आज के deep learning era में decision trees को कम आंका जा रहा है
  लेकिन वे अब भी interpretable, तेज़ और काफ़ी practical हैं
  मैंने website analysis के लिए एक scoring system tree-based तरीके से बनाया था,
  जो “क्या meta description है?”, “क्या 3 सेकंड के भीतर load होता है?”, “क्या mobile-friendly है?” जैसी शर्तों का मूल्यांकन करता है
  user तुरंत समझ सकता है कि उसे वह score क्यों मिला
  neural network ने 73 points क्यों दिए, यह समझाना लगभग असंभव है, लेकिन tree के साथ यह आसान है

  • आप सच में प्राचीन परंपरा को आगे बढ़ा रहे हैं
    इसकी शुरुआत लगभग 1000 ईसा पूर्व के Esagil-kin-apli के diagnostic tree से हुई थी