Decision Trees and Random Forests

জিনিসটা কী, কেন দরকার

Bank এর loan officer পরপর কয়েকটা প্রশ্ন করেন। "মাসে 30 হাজারের কম আয়?" হ্যাঁ হলে: "একই চাকরিতে দুই বছরের কম?" প্রতিটা answer application কে একটা শাখায় পাঠায়, শেষে গিয়ে একটা সিদ্ধান্ত। এটাই decision tree, আর বেশিরভাগ model এর মতো না, এটা print করে পড়া যায়।

Tree মিশ্র data সামলায় (আয়, চাকরির বছর, জেলা) scaling ছাড়াই, interaction ধরে ("আয় কম হলেও চলবে যদি চাকরি স্থির হয়"), আর দ্রুত। দুর্বলতা: একটা tree যদি ভাগ করতেই থাকে, তাহলে noise মুখস্থ করে ফেলে। সমাধানটা অবাক করার মতো সহজ: একটু আলাদা আলাদা অনেকগুলো tree বানাও আর তাদের vote দিতে দাও। এটাই random forest। এটা আর এর ভাই gradient-boosted tree, industry তে table আকারের data তে এখনো প্রথম চেষ্টা।

ভেতরে কীভাবে চলে

প্রশ্ন বাছাই। প্রতিটা node এ tree প্রতিটা feature আর প্রতিটা threshold চেষ্টা করে, আর সেই ভাগটা নেয় যেটা দুই পাশকে সবচেয়ে pure রাখে: এক পাশে সবাই শোধ করেছে, অন্য পাশে সবাই করেনি। Purity মাপা হয় Gini impurity দিয়ে:

gini = 1 − p² − (1 − p)²       p = share of "repaid" in the group

Gini 0 মানে দলের সবার label একই। Gini 0.5 মানে একদম 50/50 মিশ্রণ। ভাগের score হলো দুই পাশের Gini এর গড়, যে পাশে যত row তত weight; যত কম তত ভালো। (Entropy আরেকটা common মাপ; সাধারণত একই ভাগই বাছে।)

বড় করা। ভাগ করো, তারপর প্রতিটা পাশ আবার ভাগ করো, যতক্ষণ না node pure হয় বা maximum depth এ পৌঁছায়। Leaf এ যে row গুলো এসে পড়েছে তাদের বেশিরভাগের label ই leaf এর prediction।

একটা tree কেন overfit করে। Depth এর সীমা না থাকলে tree ভাগ করতেই থাকে যতক্ষণ না প্রতিটা training row নিজের একটা pure leaf পায়, noise ওয়ালা উল্টাপাল্টা row গুলোও। Training data তে 100%, নতুন data তে খারাপ।

Random forest। অনেকগুলো গভীর tree train করো, প্রতিটা:

1. একটা bootstrap sample এ: training set এর সমান সংখ্যক row, তোলা হয় ফেরত রেখে রেখে, তাই প্রতিটা tree একটু আলাদা dataset দেখে (একে বলে bagging);
2. প্রতিটা ভাগে শুধু একটা random feature এর subset বিবেচনা করে, যাতে সব tree একই প্রথম প্রশ্ন না করে।

প্রতিটা tree নিজের মতো করে overfit করে। তাদের vote মেলালে noise এর অনেকটা কাটাকাটি হয়ে যায়, আর আসল pattern টা থেকে যায়।

আগে অনুমান করো

একটা দলে 6 টা loan শোধ হয়েছে আর 2 টা হয়নি। এর Gini impurity কত?

0.3750.250.50

ছবিতে দেখো

Play

Code এ tree আর forest

শূন্য থেকে একটা tree আর একটা forest, 24 টা loan application এর উপর (চারটা pattern মানে না, আসল data যেমন)। Code টা depth 1, 2 আর 8 এর tree বানায়, তারপর 25 টা গভীর tree এর forest, আর প্রতিটাকে 12 টা লুকানো application এ check করে। এটা শুধু Python এ: forest এ random sampling লাগে, আর Python আর Go এর random generator আলাদা সংখ্যা দেয়।

"""A decision tree and a small random forest, written from scratch with the standard library."""
import random

# Loan applications: (monthly income in thousand taka, years at current job) -> repaid (1) or not (0).
TRAIN = [(25, 1, 0), (30, 4, 1), (45, 2, 1), (18, 6, 0), (60, 1, 1), (22, 3, 0), (35, 5, 1),
         (28, 2, 0), (50, 7, 1), (20, 8, 1), (40, 1, 0), (33, 3, 1), (15, 2, 0), (55, 4, 1),
         (26, 6, 1), (38, 2, 1), (24, 1, 0), (42, 6, 1), (31, 1, 0), (19, 4, 0),
         (37, 5, 0), (22, 2, 1), (48, 1, 0), (27, 7, 0)]  # the last four don't follow the pattern: real data is noisy
TEST = [(29, 5, 1), (21, 2, 0), (47, 3, 1), (34, 1, 0), (23, 7, 1), (16, 5, 0),
        (36, 4, 1), (23, 3, 0), (52, 2, 1), (39, 6, 1), (17, 1, 0), (44, 1, 0)]

def gini(rows):
    if not rows:
        return 0.0
    p = sum(r[-1] for r in rows) / len(rows)
    return 1 - p * p - (1 - p) * (1 - p)   # 0 = pure, 0.5 = a perfect 50/50 mix

def best_split(rows, features):
    best = None
    for f in features:
        for t in sorted({r[f] for r in rows}):
            left = [r for r in rows if r[f] < t]
            right = [r for r in rows if r[f] >= t]
            if not left or not right:
                continue
            score = (len(left) * gini(left) + len(right) * gini(right)) / len(rows)
            if best is None or score < best[0]:
                best = (score, f, t, left, right)
    return best

def build(rows, depth, max_depth, features, rng=None):
    majority = int(sum(r[-1] for r in rows) * 2 >= len(rows))
    if depth == max_depth or gini(rows) == 0:
        return majority
    feats = rng.sample(features, 1) if rng else features   # a forest tree sees one random feature per split
    split = best_split(rows, feats)
    if split is None:
        return majority
    _, f, t, left, right = split
    return (f, t, build(left, depth + 1, max_depth, features, rng), build(right, depth + 1, max_depth, features, rng))

def predict(node, x):
    while isinstance(node, tuple):
        f, t, left, right = node
        node = left if x[f] < t else right
    return node

def show(node, indent=""):
    names = ["income", "years"]
    if not isinstance(node, tuple):
        print(f"{indent}-> {'repaid' if node else 'default'}")
        return
    f, t, left, right = node
    print(f"{indent}{names[f]} < {t}?")
    print(f"{indent}  yes:"); show(left, indent + "    ")
    print(f"{indent}  no:"); show(right, indent + "    ")

def acc(fn, rows):
    return sum(fn(r) == r[-1] for r in rows) / len(rows)

print(f"gini of all training rows: {gini(TRAIN):.3f}")
shallow = build(TRAIN, 0, 2, [0, 1])
show(shallow)
for depth in (1, 2, 8):
    tree = build(TRAIN, 0, depth, [0, 1])
    print(f"tree depth {depth}: train {acc(lambda r: predict(tree, r), TRAIN):.0%}, test {acc(lambda r: predict(tree, r), TEST):.0%}")

# Random forest: 25 deep trees, each on a bootstrap sample (rows drawn with replacement), majority vote.
def forest(seed, n_trees=25):
    rng = random.Random(seed)
    trees = []
    for _ in range(n_trees):
        sample = [rng.choice(TRAIN) for _ in TRAIN]
        trees.append(build(sample, 0, 8, [0, 1], rng))
    return lambda r: int(sum(predict(t, r) for t in trees) * 2 >= len(trees))

scores = [acc(forest(seed), TEST) for seed in range(10)]
print(f"forest of 25, 10 different seeds: test {min(scores):.0%} to {max(scores):.0%}, average {sum(scores) / len(scores):.0%}")

Output:

gini of all training rows: 0.500
income < 30?
  yes:
    years < 8?
      yes:
        -> default
      no:
        -> repaid
  no:
    years < 2?
      yes:
        -> default
      no:
        -> repaid
tree depth 1: train 71%, test 67%
tree depth 2: train 83%, test 83%
tree depth 8: train 100%, test 83%
forest of 25, 10 different seeds: test 83% to 92%, average 87%

কী দেখলাম:

• Print করা depth-2 tree টা rule হিসেবে পড়া যায়: আয় 30 হাজারের কম হলে চাকরিতে 8+ বছর লাগবে; 30 হাজার বা বেশি হলে 2+ বছরই যথেষ্ট। এটা একজন loan officer এর হাতে দিয়ে দেওয়া যায়।
• Depth 1 বেশি সহজ (train 71%, test 67%)। Depth 2 দুইটাতেই 83%।
• Depth 8 চারটা উল্টাপাল্টা row কে আলাদা leaf দিয়ে training data তে perfect fit করে, 100%, কিন্তু লুকানো row এ depth 2 এর চেয়ে ভালো করে না। Training এর বাড়তি 17% ছিল মুখস্থ করা noise।
• 25 টা গভীর tree এর forest random seed ভেদে 83% থেকে 92% পায়, গড়ে 87%। একই গভীর tree, কিন্তু vote প্রতিটার মুখস্থ জিনিস মসৃণ করে দেয়। মাত্র 12 টা test row, তাই প্রতিটা row 8% এর সমান, সংখ্যাগুলো একটু ঢিলেঢালাভাবে নাও; বড় data তেও যা টেকে সেটা হলো pattern টা।

Production এ যা মাথায় রাখবে

• Table এর data তে tree ই default। Row আর column এর problem এ (fraud, churn, credit, pricing) gradient-boosted tree (XGBoost, LightGBM, CatBoost) সাধারণত neural network কে হারায়, CPU তে কয়েক মিনিটে train হয়, tune ও কম লাগে। Deep learning এর আগে এগুলো চেষ্টা করো।
• ব্যাখ্যা করার সীমা আছে। একটা অগভীর tree পড়া যায়। 500 টা গভীর tree এর forest পড়া যায় না, যদিও প্রতিটা tree আলাদাভাবে পড়া যায়। Forest ব্যাখ্যা করতে feature importance বা SHAP value নাও, আর মনে রেখো এগুলো model কে বর্ণনা করে, বাস্তব দুনিয়ার কারণ না।
• Tree নিজের দেখা range এর বাইরে যেতে পারে না। একটা leaf তার ভেতরের training row গুলোর গড় বলে। 2,000 sqft পর্যন্ত flat এ train করা ভাড়ার model 2,500 আর 10,000 sqft এ একই ভাড়া বলবে। Linear model trend টা টেনে নেয়; tree সমান হয়ে যায়।
• Memory আর latency। Forest মানে শত শত tree; প্রতিটা prediction সবগুলোর ভেতর দিয়ে হাঁটে। দ্রুতই (microsecond), কিন্তু model file শত MB হতে পারে। Validation score যতটা সত্যিই বাড়ে, depth আর tree এর সংখ্যা ততটুকুতেই রাখো।
• Random seed fix করো। Output এ দেখলে, seed ভেদে forest বদলায়। Fix করে রাখো যাতে আবার train করলে একই model আসে, আর model তুলনা করো কয়েকটা seed এ, একটা ভাগ্যবান run এ না।

এক কথায়

Decision tree বারবার সেই প্রশ্নটা করে যেটা data কে সবচেয়ে pure দলে ভাগ করে; গভীর tree noise মুখস্থ করে, আর random forest সেটা ঠিক করে bootstrap sample আর random feature দিয়ে অনেকগুলো tree train করে তাদের vote নিয়ে।

নিজে করে দেখো

Forest কে 25 টা tree থেকে 1, 5 আর 100 টায় বদলাও (seed 0 রেখে)। Test accuracy কীভাবে বদলায়? তারপর প্রতিটা tree কে প্রতিটা ভাগে একটা random feature এর বদলে দুইটা feature ই দেখতে দাও। Forest এর কী হয়, আর কেন?

Answer

1 টা tree হলে forest মানে bootstrap sample এ একটাই গভীর tree, তাই depth-8 tree এর মতো বা তার চেয়ে খারাপ করে। Tree বাড়ালে accuracy সাধারণত বাড়ে, তারপর সমান হয়ে যায়: কয়েক ডজনের পরে বাড়তি tree খরচ বাড়ায় কিন্তু accuracy তেমন বাড়ায় না। প্রতিটা tree দুইটা feature ই দেখলে tree গুলো অনেক বেশি একরকম হয়ে যায় (সবাই একই শক্তিশালী প্রথম ভাগ বাছে), তাই তাদের ভুলগুলোও একসাথে হয়, আর vote কম noise কাটে। Random feature বাছাইটাই tree গুলোকে যথেষ্ট আলাদা রাখে, যাতে vote কাজে লাগে।