এই পর্বে যা পাবেন
- Array-এর shape, broadcasting, memory আর groupby-র ফল আগেই হাতে বলে দেওয়া
- Norm, cosine, chain rule আর gradient descent-এর এক-দুই ধাপ
- Conditional probability, Bayes, binomial, Poisson, z, t-interval, entropy, KL আর information gain
- BFS, DFS, UCS, greedy, A*, minimax, alpha-beta, AC-3, hill climbing, resolution আর chaining-এর trace
- Bayesian network, Markov chain, Viterbi, expected utility, VPI আর value iteration
- k-NN, normal equations, logistic step, ridge, metric, ROC AUC, k-means, PCA, TF-IDF, perceptron, backprop, attention, MRR, fairness আর PSI
১ · পাতার নিয়ম, ভাগের মানচিত্র আর খাতার কৌশল
মডিউল ১৪-এ স্বাগতম। চায়ের দোকানের মালিক হিসাব খাতায় শুধু “লাভ হয়েছে” লেখেন না; কত কাপ, কত টাকা, সব লেখেন। AI-তেও “A* ভালো” বলা যথেষ্ট নয়; কোন node আগে খুলবে, কোন ধাপে কত মান, তা হিসাব করে দেখাতে পারা দরকার। বিশ্ববিদ্যালয়ের Artificial Intelligence, Machine Learning বা Data Science কোর্সের পরীক্ষায়, চাকরির লিখিত পরীক্ষায় আর data বা ML ইন্টারভিউতে এ ধরনের ছোট, হাতে করা হিসাব প্রায়ই আসে। এই পাতা সেগুলো এক জায়গায় অনুশীলন করায়।
কোন ভাগে কী, কোন পর্ব ঝালাবেন
| ভাগ | কী আছে | মূল পর্ব |
|---|---|---|
| ২ | Shape, axis, broadcasting, nbytes, groupby-তে NaN | ১৩, ১৫, ১৬, ১৯, ২৪ |
| ৩ | Norm, dot, cosine, দূরত্ব, chain rule, gradient descent | ১৭, ৩৩, ৩৪ |
| ৪ | Conditional, Bayes, binomial, Poisson, z, t-interval, entropy, KL, information gain | ৩৫–৩৮, ৫০ |
| ৫ | BFS, DFS, UCS, greedy, A*, minimax, alpha-beta, AC-3, hill climbing | ৩৯–৪৪ |
| ৬ | Truth table, CNF, resolution, forward ও backward chaining | ৪৫–৪৭ |
| ৭ | Bayesian network, Markov chain, Viterbi, expected utility, value iteration | ৫০, ৫২–৫৪ |
| ৮ | k-NN, normal equations, logistic-এর এক ধাপ, bias–variance, ridge | ৫৭–৫৯, ৬১ |
| ৯ | Confusion matrix, ROC AUC, k-means, PCA, TF-IDF | ৬০, ৬৫, ৬৭ |
| ১০ | Perceptron, backprop, attention, recall@k, MRR, fairness, PSI | ৬৮–৭০, ৭২, ৭৪ |
এই পাতার নিয়ম — প্রশ্নে অন্য কিছু না বললে
| বিষয় | নিয়ম |
|---|---|
| log | Entropy, cross-entropy, KL আর information gain-এ log2 (একক bit). Loss, TF-IDF আর PSI-তে ln (স্বাভাবিক log), যেমন কোর্সের পর্বগুলোতে |
| দশমিক | মাঝের ধাপে ৪ ঘর রাখুন, শেষ উত্তর প্রশ্ন যত ঘর চায়। আগেভাগে কাটলে শেষে পার্থক্য আসে |
| সমান মান (tie) | Search-এ সমান খরচ বা f হলে বর্ণক্রমে আগের node আগে; প্রতিবেশীও বর্ণক্রমে |
| Variance | “নমুনার variance” মানে n − ১ দিয়ে ভাগ (Bessel); “population” বললে n দিয়ে |
| Memory | MB = ১০৬ byte, MiB = ২২০ byte; NumPy-র nbytes শুধু ডেটার byte, Python object-এর খরচ নয় |
| Gradient | “এক ধাপ” মানে θ ← θ − η × gradient, যেখানে η (eta) হলো learning rate |
১. দেওয়া তথ্য এক লাইনে। “n = ৬, x̄ = ৫, s = ২.১৯” লিখে নিলে পরের ধাপে ভুল সংখ্যা বসানোর সম্ভাবনা কমে।
২. নিয়ম আগে ঘোষণা করুন। “goal test expand-এর সময়”, “tie বর্ণক্রমে”, “log2”. একই প্রশ্নে নিয়ম বদলালে উত্তরও বদলায়, আর পরীক্ষক আপনার নিয়মটি দেখে নম্বর দেন।
৩. সূত্র আগে, মান পরে। হিসাবে ভুল হলেও সূত্র দেখে যুক্তি বোঝা যায়।
৪. একটি দ্রুত যাচাই। সম্ভাবনার যোগ ১ কি না, softmax-এর ওজনের যোগ ১ কি না, A*-এর খরচ UCS-এর সমান কি না। এক লাইনের যাচাই অনেক ভুল ধরে।
৫. উত্তরের অর্থ এক লাইনে। “P = ০.২৭” লিখেই থামবেন না; বলুন, “সতর্কবার্তা পাওয়া চারটির প্রায় তিনটিই আসলে নির্দোষ।”
২ · NumPy আর pandas — shape, broadcasting, memory আর groupby
ঝালিয়ে নিন: পর্ব ১৩ · NumPy array (shape, dtype), পর্ব ১৫ · Vectorization আর broadcasting, পর্ব ১৬ · aggregation আর axis, পর্ব ১৯ · NumPy-র গতি (memory, view), পর্ব ২৪ · Groupby.
size = shape-এর সব সংখ্যার গুণফল। axis=k-তে যোগ করলে shape থেকে k নম্বর ঘরটি মুছে যায়। Broadcasting: shape দুটি ডান দিক থেকে মেলান; প্রতিটি জোড়ায় মান সমান বা একটি ১ হলে চলে, ছোটটির বাঁয়ে দরকারমতো ১ বসে। nbytes = size × itemsize (float64 ৮, float32 ৪, int8/uint8 ১ byte). Groupby-তে size সব সারি গোনে, count শুধু NaN-ছাড়া মান; sum আর mean NaN বাদ দেয়।
২.১(সহজ) a = np.arange(24).reshape(2, 3, 4). (ক) a.shape, a.ndim, a.size কত? (খ) a.sum(axis=0), a.sum(axis=(0, 2)), a[:, 1, :] আর a.T-এর shape কী? (গ) a[1, 2, 3]-এর মান কত? (ঝালিয়ে নিন: পর্ব ১৩, ১৬)
(a) shape (2, 3, 4), ndim 3, size 2 x 3 x 4 = 24
(b) sum(axis=0) : drop position 0 -> (3, 4)
sum(axis=(0, 2)) : drop 0 and 2 -> (3,)
a[:, 1, :] : integer index removes axis 1 -> (2, 4)
a.T : reverse all axes -> (4, 3, 2)
(c) flat index = 1 x (3 x 4) + 2 x 4 + 3 = 12 + 8 + 3 = 23 -> value 23
(গ)-র কৌশল: arange দিয়ে বানানো array-তে মান আর সমতল অবস্থান (row-major ক্রমে) একই, তাই সূচক থেকে stride গুনলেই মান। যাচাই: সূচক (০, ০, ০) থেকে (১, ২, ৩) পর্যন্ত মোট ২৪টি ঘর, শেষটি ২৩. ফাঁদ: a[:, 1, :] আর a[:, 1:2, :] এক নয়; slice axis রেখে দেয়, তাই দ্বিতীয়টির shape (২, ১, ৪)।
২.২(মাঝারি) x = np.array([[1], [2], [3]]) আর y = np.array([10, 20, 30, 40]). (ক) x * y-এর shape, তার সারি ১ (শূন্য থেকে গোনা) আর সব ঘরের যোগফল কত? (খ) shape (৮, ১, ৬) আর (৭, ১) মিলে কী হয়? (গ) (৫, ৪) + (৫,) আর (২, ৩) + (৩, ২) চলবে কি? (ঘ) ১০০টি সারি, ৩টি column-এর X থেকে প্রতিটি সারির গড় বিয়োগ করতে X - X.mean(axis=1) লিখলে কী হয়? (ঝালিয়ে নিন: পর্ব ১৫)
(a) (3, 1) with (4,) -> (3, 1) with (1, 4) -> (3, 4)
row 1 = 2 x [10, 20, 30, 40] = [20, 40, 60, 80]
sum = (1 + 2 + 3) x (10 + 20 + 30 + 40) = 6 x 100 = 600
(b) (8, 1, 6) with (1, 7, 1) -> (8, 7, 6)
(c) (5, 4) with (1, 5): 4 vs 5 -> error
(2, 3) with (3, 2): 3 vs 2 -> error
(d) (100, 3) - (100,) -> (100, 3) with (1, 100): 3 vs 100 -> error
fix: X - X.mean(axis=1, keepdims=True) # (100, 1)
যোগফলের শর্টকাট: প্রতিটি ঘর xi × yj, তাই সব ঘরের যোগ = (∑x)(∑y). (ঘ) সবচেয়ে প্রচলিত বাস্তব ভুল; সারি ৩ হলে আর column ৩ হলে কোড ভুল জিনিস বিয়োগ করেও চলে যেত, error ছাড়াই। তাই keepdims=True অভ্যাস করুন।
২.৩(সহজ) (ক) ১,০০০ × ১,০০০ array float64, float32 আর int8-এ কত byte? float64-এ কত MiB? (খ) ২৮ × ২৮ পিক্সেলের ৬০,০০০টি ধূসর ছবি uint8-এ কত byte, আর float64-এ বদলালে? (গ) ৩২টি ২২৪ × ২২৪ রঙিন (৩ channel) ছবির uint8 batch? (ঘ) float64 array b = a[::2] (a ১,০০০ × ১,০০০) বানালে নতুন কত byte ডেটা কপি হয়? (ঝালিয়ে নিন: পর্ব ১৮, ১৯)
(a) 1,000,000 x 8 = 8,000,000 B (= 8 MB = 7.63 MiB)
1,000,000 x 4 = 4,000,000 B ; x 1 = 1,000,000 B
(b) 60,000 x 28 x 28 = 47,040,000 values
uint8 : 47,040,000 B (about 44.9 MiB)
float64: 47,040,000 x 8 = 376,320,000 B (about 358.9 MiB)
(c) 32 x 224 x 224 x 3 = 4,816,896 B (about 4.6 MiB)
(d) basic slicing gives a view: 0 new data bytes
(b.nbytes still reports 500 x 1000 x 8 = 4,000,000)
(খ) দেখায় কেন ছবির dataset অনেক সময় uint8-এ রেখে batch ধরে float-এ বদলানো হয়: পুরোটা একবারে float64 করলে memory আট গুণ। (ঘ)-র ফাঁদ: nbytes view-এর আকার বলে, নতুন বরাদ্দ নয়; np.shares_memory(a, b) True দেয়।
২.৪(মাঝারি) বাজারঘরের ৮টি অর্ডার (district, category, qty, price): (ঢাকা, চাল, ২, ১২০), (চট্টগ্রাম, ডাল, ১, ১৫০), (ঢাকা, ডাল, ৩, ১৪০), (খুলনা, চাল, ৫, ১১০), (চট্টগ্রাম, চাল, ২, ১২৫), (ঢাকা, চাল, ১, NaN), (খুলনা, ডাল, ২, ১৪৫), (চট্টগ্রাম, ডাল, ৪, ১৫০)। amount = qty * price. (ক) groupby("district")["amount"]-এ প্রতিটি জেলার size, count, sum আর mean কত? (খ) NaN-কে আগে ০ বসিয়ে গড় নিলে ঢাকার গড় কত? (গ) groupby(["district", "category"])-এ কয়টি দল? (ঝালিয়ে নিন: পর্ব ২৩, ২৪)
amount: 240, 150, 420, 550, 250, NaN, 290, 600
(a) Khulna : 550, 290 -> size 2, count 2, sum 840, mean 420.00
Chattogram: 150, 250, 600 -> size 3, count 3, sum 1000, mean 333.33
Dhaka : 240, 420, NaN -> size 3, count 2, sum 660, mean 660/2 = 330.00
(b) fillna(0): (240 + 420 + 0) / 3 = 220.00
(c) pairs: Dhaka-rice, Dhaka-lentil, Ctg-lentil, Ctg-rice, Khulna-rice,
Khulna-lentil = 6 groups
যাচাই: তিন জেলার sum ৮৪০ + ১,০০০ + ৬৬০ = ২,৫০০, আর NaN বাদে আটটির যোগও ২,৫০০. (ক) আর (খ)-র পার্থক্যটিই আসল শিক্ষা: অজানা দামকে ০ ধরা মানে “বিনা পয়সায় বিক্রি” বলা, আর তাতে ঢাকার গড় ৩৩০ থেকে ২২০-এ নামে। pandas দল সাজায় key-এর Unicode ক্রমে, তাই খুলনা (খ) আগে, ঢাকা (ঢ) শেষে।
import numpy as np
import pandas as pd
a = np.arange(24).reshape(2, 3, 4) # ২.১
print("2.1", a.shape, a.ndim, a.size, a.sum(axis=0).shape,
a.sum(axis=(0, 2)).shape, a[:, 1, :].shape, a.T.shape, a[1, 2, 3])
x = np.array([[1], [2], [3]]); y = np.array([10, 20, 30, 40]) # ২.২
print("2.2", (x * y).shape, (x * y)[1], (x * y).sum(),
np.broadcast_shapes((8, 1, 6), (7, 1)))
for s1, s2 in [((5, 4), (5,)), ((2, 3), (3, 2))]:
try: np.broadcast_shapes(s1, s2)
except ValueError: print(" ", s1, "+", s2, "-> error")
for dt in ["float64", "float32", "int8"]: # ২.৩
print("2.3", dt, np.zeros((1000, 1000), dtype=dt).nbytes)
nb = lambda shape, dt: int(np.prod(shape)) * np.dtype(dt).itemsize # array না বানিয়েই
print(" 60000x28x28", nb((60000, 28, 28), np.uint8), nb((60000, 28, 28), np.float64),
"| 32x224x224x3", nb((32, 224, 224, 3), np.uint8))
df = pd.DataFrame({ # ২.৪
"district": ["ঢাকা", "চট্টগ্রাম", "ঢাকা", "খুলনা", "চট্টগ্রাম", "ঢাকা", "খুলনা", "চট্টগ্রাম"],
"category": ["চাল", "ডাল", "ডাল", "চাল", "চাল", "চাল", "ডাল", "ডাল"],
"qty": [2, 1, 3, 5, 2, 1, 2, 4],
"price": [120, 150, 140, 110, 125, np.nan, 145, 150]})
df["amount"] = df["qty"] * df["price"]
g = df.groupby("district")["amount"]
print(pd.DataFrame({"size": g.size(), "count": g.count(), "sum": g.sum(),
"mean": g.mean().round(2), "mean_fill0": df["amount"].fillna(0)
.groupby(df["district"]).mean().round(2)}))
print("2.4 groups:", df.groupby(["district", "category"]).ngroups)প্রথম লাইন 2.1 (2, 3, 4) 3 24 (3, 4) (3,) (2, 4) (4, 3, 2) 23 ২.১-এর সব উত্তর। 2.2 (3, 4) [20 40 60 80] 600 (8, 7, 6) আর দুটি -> error লাইন ২.২। 2.3 float64 8000000, float32 4000000, int8 1000000, তারপর 60000x28x28 47040000 376320000 | 32x224x224x3 4816896; বড় array বানানো হয়নি, শুধু shape × itemsize গোনা, কারণ browser-এ ৩৫৯ MiB বরাদ্দ ঝুঁকির। ঢাকার সারি 3 2 660.0 330.00 220.00: size, count, sum, mean আর ০ বসানো গড়। শেষ লাইন 2.4 groups: 6.
৩ · Vector, derivative আর gradient descent
ঝালিয়ে নিন: পর্ব ১৭ · NumPy-তে linear algebra, পর্ব ৩৩ · Vector আর similarity, পর্ব ৩৪ · Derivative আর gradient descent.
L1 = ∑|ui|, L2 = √(∑ui2), L∞ = সবচেয়ে বড় |ui|। Dot u·v = ∑uivi; cosine = u·v ÷ (‖u‖‖v‖)। দুটি একক-দৈর্ঘ্যের vector-এ ‖u − v‖2 = ২ − ২cos. Chain rule: (f(g(x)))′ = f′(g(x)) × g′(x). Gradient descent: x ← x − η f′(x).
৩.১(সহজ) u = (৩, ৪, ০), v = (৪, ০, ৩)। (ক) u-এর L1, L2 আর L∞ norm. (খ) u·v, cosine similarity আর দুটির মাঝের কোণ। (গ) Euclidean আর Manhattan দূরত্ব। (ঝালিয়ে নিন: পর্ব ১৭, ৩৩)
(a) L1 = 3 + 4 + 0 = 7 ; L2 = sqrt(9 + 16 + 0) = 5 ; Linf = 4
(b) u.v = 12 + 0 + 0 = 12 ; |v| = sqrt(16 + 0 + 9) = 5
cos = 12 / (5 x 5) = 0.48 ; angle = arccos(0.48) = 61.3 deg
(c) u - v = (-1, 4, -3)
euclid = sqrt(1 + 16 + 9) = sqrt(26) = 5.099
manhattan = 1 + 4 + 3 = 8
যাচাই: L∞ ≤ L2 ≤ L1 (৪ ≤ ৫ ≤ ৭) সবসময় সত্য, উল্টো এলে হিসাব ভুল। Cosine ০.৪৮ মানে দিক আংশিক মেলে; দৈর্ঘ্য সমান (৫ আর ৫) হলেও দিক আলাদা।
৩.২(মাঝারি) একটি query vector q = (১, ১) আর তিনটি পণ্যের vector a = (২, ২), b = (১, ০), c = (৫, ৪)। (ক) Cosine similarity অনুযায়ী মিলের ক্রম কী? (খ) Euclidean দূরত্বে কাছের ক্রম কী? (গ) সবগুলোকে আগে L2 দিয়ে একক দৈর্ঘ্যে আনলে Euclidean ক্রম কী হয়, কেন? (ঝালিয়ে নিন: পর্ব ৩৩, ৬৯)
|q| = sqrt(2) = 1.4142
(a) cos(q,a) = 4 / (1.4142 x 2.8284) = 1.0000
cos(q,b) = 1 / (1.4142 x 1) = 0.7071
cos(q,c) = 9 / (1.4142 x 6.4031) = 0.9939
order: a > c > b
(b) |q-a| = sqrt(2) = 1.4142 ; |q-b| = 1 ; |q-c| = sqrt(16 + 9) = 5
order: b, a, c
(c) unit vectors: d = sqrt(2 - 2 cos)
a: 0.0000 ; c: sqrt(2 - 1.9878) = 0.1106 ; b: sqrt(2 - 1.4142) = 0.7654
order: a, c, b (same as cosine)
শিক্ষা: Euclidean দৈর্ঘ্য দেখে, cosine শুধু দিক। c দিকের দিক থেকে q-এর কাছাকাছি কিন্তু “বড়”, তাই Euclidean-এ সবচেয়ে দূরে। Embedding খোঁজায় তাই আগে normalize করে নেওয়া হয়; তখন দুটি মাপ একই ক্রম দেয়।
৩.৩(সহজ) (ক) f(x) = (৩x2 + ১)3 হলে x = ১-এ f′ কত? (খ) sigmoid σ(z) = ১ ÷ (১ + e−z)-এর derivative σ(১ − σ); z = ০-তে মান কত? (গ) এক বিন্দুর loss L(w) = (wx − y)2, x = ২, y = ৫, w = ১ হলে dL/dw কত, আর w বাড়াতে হবে না কমাতে? (ঝালিয়ে নিন: পর্ব ৩৪)
(a) outer: 3 u^2 with u = 3x^2 + 1 ; inner: du/dx = 6x
f'(x) = 3 (3x^2 + 1)^2 x 6x
f'(1) = 3 x 4^2 x 6 = 3 x 16 x 6 = 288
(b) sigma(0) = 0.5 -> 0.5 x 0.5 = 0.25 (the largest possible value)
(c) dL/dw = 2 (wx - y) x = 2 (2 - 5) x 2 = -12
negative slope -> increasing w lowers L
যাচাই (ক): f(১.০০১) − f(০.৯৯৯) কে ০.০০২ দিয়ে ভাগ করলে প্রায় ২৮৮ আসে; চেকারে 288.0. (খ)-র ০.২৫ মনে রাখার মতো: sigmoid-এর ঢাল কখনো ০.২৫ ছাড়ায় না, তাই অনেক স্তরে গুণ হতে হতে gradient ছোট হয়ে যায় (vanishing gradient).
৩.৪(মাঝারি) (ক) f(x) = x2 − ৪x + ৫, শুরু x0 = ০. Learning rate η = ০.১-এ তিন ধাপের x আর f(x3) কত? η = ১.০ আর ১.১ হলে কী হয়? (খ) f(x, y) = x2 + ১০y2, শুরু (১, ১)। η = ০.০৫ আর ০.১-এ দুই ধাপ কোথায় নেয়? কোন η-এর নিচে y-দিক স্থির থাকে? (ঝালিয়ে নিন: পর্ব ৩৪, ৫৮)
(a) f'(x) = 2x - 4 ; minimum at x = 2
x1 = 0 - 0.1 x (0 - 4) = 0.4
x2 = 0.4 - 0.1 x (0.8 - 4) = 0.72
x3 = 0.72 - 0.1 x (1.44 - 4) = 0.976 ; f(x3) = 2.0486
gap to 2 shrinks by (1 - 2 eta): 2 -> 1.6 -> 1.28 -> 1.024
eta = 1.0: factor -1 -> 4, 0, 4 (bounces forever)
eta = 1.1: factor -1.2 -> 4.4, -0.88, 5.456 (diverges)
(b) grad = (2x, 20y)
eta 0.05: (1,1) -> (0.9, 0) -> (0.81, 0)
eta 0.1 : (1,1) -> (0.8, -1) -> (0.64, 1) y bounces
y factor = 1 - 20 eta ; stable when |1 - 20 eta| < 1 -> eta < 0.1
যাচাই: f(০.৪) = ৩.৫৬, f(০.৭২) = ২.৬৩৮৪, f(০.৯৭৬) = ২.০৪৮৬, প্রতি ধাপে কমছে, সর্বনিম্ন f(২) = ১-এর দিকে। (খ) দেখায়, খাড়া দিকটিই (এখানে y, বক্রতা ২০) η-এর সীমা ঠিক করে; চ্যাপ্টা x-দিক তখন ধীরে এগোয়। Feature scaling কেন দরকার, তার সংখ্যায় উত্তর এটিই।
import numpy as np
np.set_printoptions(precision=4, suppress=True)
u, v = np.array([3, 4, 0]), np.array([4, 0, 3]) # ৩.১
cos = u @ v / (np.linalg.norm(u) * np.linalg.norm(v))
print("3.1 L1", np.abs(u).sum(), "L2", np.linalg.norm(u), "Linf", np.abs(u).max(),
"| dot", u @ v, "cos", round(cos, 4), "angle", round(np.degrees(np.arccos(cos)), 1))
print(" euclid", round(np.linalg.norm(u - v), 4), "manhattan", np.abs(u - v).sum())
q = np.array([1, 1]); docs = {"a": [2, 2], "b": [1, 0], "c": [5, 4]} # ৩.২
for k, d in docs.items():
d = np.array(d)
c = q @ d / (np.linalg.norm(q) * np.linalg.norm(d))
un = q / np.linalg.norm(q) - d / np.linalg.norm(d)
print("3.2", k, "cos", round(c, 4), "euclid", round(np.linalg.norm(q - d), 4),
"euclid(unit)", round(np.linalg.norm(un), 4))
f = lambda x: (3 * x**2 + 1) ** 3 # ৩.৩
h = 1e-6
print("3.3 f'(1) numeric", round((f(1 + h) - f(1 - h)) / (2 * h), 3), "| formula", 3 * 16 * 6)
sig = lambda z: 1 / (1 + np.exp(-z))
print(" sigma'(0)", sig(0) * (1 - sig(0)), "| dL/dw", 2 * (1 * 2 - 5) * 2)
for eta in [0.1, 1.0, 1.1]: # ৩.৪ (ক)
x, path = 0.0, []
for _ in range(3):
x = x - eta * (2 * x - 4); path.append(round(x, 4))
print(f"3.4 eta={eta}", path, "f(x3)=", round(x**2 - 4 * x + 5, 4))
for eta in [0.05, 0.1]: # ৩.৪ (খ)
p = np.array([1.0, 1.0]); path = []
for _ in range(2):
p = p - eta * np.array([2 * p[0], 20 * p[1]]); path.append(p.round(4).tolist())
print(f" 2D eta={eta}", path)3.1 L1 7 L2 5.0 Linf 4 | dot 12 cos 0.48 angle 61.3 আর euclid 5.099 manhattan 8 ৩.১. ৩.২-এর তিন লাইনে c-এর জন্য cos 0.9939 euclid 5.0 euclid(unit) 0.1106: কাঁচা দূরত্বে সবচেয়ে দূরে, একক vector-এ দ্বিতীয়। 3.3 f'(1) numeric 288.0 | formula 288 সংখ্যায় করা derivative দিয়ে chain rule যাচাই। 3.4 eta=0.1 [0.4, 0.72, 0.976] f(x3)= 2.0486, eta=1.0 [4.0, 0.0, 4.0], eta=1.1 [4.4, -0.88, 5.456]; শেষ দুই লাইনে [[0.9, 0.0], [0.81, 0.0]] আর [[0.8, -1.0], [0.64, 1.0]].
৪ · সম্ভাবনা, পরিসংখ্যান আর information
ঝালিয়ে নিন: পর্ব ৩৫ · AI-এর জন্য সম্ভাবনা, পর্ব ৩৬ · Distribution আর sampling, পর্ব ৩৭ · ডেটার পরিসংখ্যান (SE, t-interval), পর্ব ৩৮ · Entropy আর information, পর্ব ৫০ · Bayes-এর উপপাদ্য.
P(A | B) = P(A ∩ B) ÷ P(B). Bayes: P(H | E) = P(E | H)P(H) ÷ P(E); গণনার সহজ পথ natural frequency, অর্থাৎ ১০,০০০ জন ধরে গোনা। Binomial: P(X = k) = C(n, k) pk(১ − p)n−k, গড় np, variance np(১ − p). Poisson: P(X = k) = e−λλk ÷ k!. z = (x − μ) ÷ σ. SE = s ÷ √n; t-interval = x̄ ± t০.৯৭৫, n−১ × SE. Entropy H(p) = −∑p log2p; cross-entropy H(p, q) = −∑p log2q; KL(p‖q) = H(p, q) − H(p). Information gain = H(মূল) − ∑(ni ÷ n)H(শাখা i).
৪.১(সহজ) বাজারঘরের ২০০টি অর্ডারের ১২০টি ক্যাশ অন ডেলিভারি (COD), ৮০টি আগাম পরিশোধ। COD-এর ১৮টি আর আগাম পরিশোধের ৪টি ফেরত এসেছে। (ক) P(ফেরত), P(ফেরত | COD), P(ফেরত | আগাম) কত? (খ) একটি ফেরত অর্ডার COD হওয়ার সম্ভাবনা কত? (গ) ফেরত আর পরিশোধের ধরন কি স্বাধীন? (ঝালিয়ে নিন: পর্ব ৩৫)
(a) P(R) = (18 + 4) / 200 = 22 / 200 = 0.11
P(R | COD) = 18 / 120 = 0.15
P(R | pre) = 4 / 80 = 0.05
(b) P(COD | R) = 18 / 22 = 0.8182
(c) independent would need P(R | COD) = P(R): 0.15 != 0.11 -> not independent
check: P(R) = 0.6 x 0.15 + 0.4 x 0.05 = 0.09 + 0.02 = 0.11
(খ) আর (ক)-র দ্বিতীয়টি গুলিয়ে ফেলা সবচেয়ে প্রচলিত ভুল: “COD হলে ফেরত” ১৫%, কিন্তু “ফেরত হলে COD” ৮২%. দুটি আলাদা প্রশ্ন। সতর্কতা: এই সম্পর্ক কারণ প্রমাণ করে না; COD-এর ক্রেতারা অন্য দিক থেকেও আলাদা হতে পারেন।
৪.২(মাঝারি) বাজারঘরের অর্ডারের ২% প্রতারণা (fraud). একটি নিয়ম প্রতারণার ৯০% ধরে (sensitivity), আর সৎ অর্ডারের ৫%-কেও ভুলে সতর্ক করে (false positive rate). (ক) ১০,০০০টি অর্ডারে কয়টি সতর্কবার্তা পায়, তার কয়টি আসলে প্রতারণা? P(প্রতারণা | সতর্ক) কত? (খ) একই ধরনের, স্বাধীন আরেকটি নিয়মও সতর্ক করলে সম্ভাবনা কত হয়? (ঝালিয়ে নিন: পর্ব ৩৫, ৫০)
(a) fraud : 10,000 x 0.02 = 200 -> flagged 200 x 0.90 = 180
honest : 9,800 -> flagged 9,800 x 0.05 = 490
P(F | flag) = 180 / (180 + 490) = 180 / 670 = 0.2687
(b) odds after first = 180 : 490 = 0.3673
likelihood ratio = 0.90 / 0.05 = 18
new odds = 0.3673 x 18 = 6.612 -> P = 6.612 / 7.612 = 0.8686
৯০% নির্ভুল শুনে “সতর্ক মানেই প্রতারণা” ভাবা base rate উপেক্ষার ভুল: প্রতারণা বিরল, তাই সৎ অর্ডারের ছোট ৫%-ও সংখ্যায় বড় (৪৯০)। প্রথম সতর্কবার্তার পরের সম্ভাবনা দ্বিতীয় প্রমাণের prior হয়ে যায়। (খ)-র “স্বাধীন” শর্তটি বাস্তবে প্রায়ই সত্য নয়; দুটি নিয়ম একই সংকেত দেখলে এত বড় লাফ আসে না।
৪.৩(মাঝারি) (ক) প্রতিটি অর্ডার স্বাধীনভাবে ১০% সম্ভাবনায় ফেরত আসে। ১০টি অর্ডারে ঠিক ০টি, ঠিক ২টি আর অন্তত ২টি ফেরতের সম্ভাবনা কত? গড় আর variance? (খ) ঘণ্টায় গড়ে ৩টি অভিযোগ আসে (Poisson). এক ঘণ্টায় ০টি, ঠিক ২টি, সর্বোচ্চ ২টি আর অন্তত ৪টির সম্ভাবনা কত? দুই ঘণ্টায় একটিও না আসার সম্ভাবনা? (ঝালিয়ে নিন: পর্ব ৩৬)
(a) P(0) = 0.9^10 = 0.3487
P(1) = 10 x 0.1 x 0.9^9 = 0.3874
P(2) = C(10,2) x 0.1^2 x 0.9^8 = 45 x 0.01 x 0.4305 = 0.1937
P(X >= 2) = 1 - P(0) - P(1) = 1 - 0.3487 - 0.3874 = 0.2639
mean = np = 1 ; var = np(1 - p) = 0.9
(b) e^-3 = 0.0498
P(0) = 0.0498 ; P(1) = 3 x 0.0498 = 0.1494 ; P(2) = 4.5 x 0.0498 = 0.2240
P(X <= 2) = 0.0498 + 0.1494 + 0.2240 = 0.4232
P(3) = 4.5 x 0.0498 = 0.2240 -> P(X <= 3) = 0.6472
P(X >= 4) = 1 - 0.6472 = 0.3528
two hours: lambda = 6 -> P(0) = e^-6 = 0.00248
“অন্তত” প্রশ্নে পরিপূরক (১ − বাকিগুলো) দিয়ে করা দ্রুত আর নিরাপদ। Poisson-এ সময়ের দৈর্ঘ্য বদলালে λ-ও একই অনুপাতে বদলায়; দুই ঘণ্টার উত্তর (০.০৪৯৮)2-ও, কারণ দুই স্বাধীন ঘণ্টাই খালি।
৪.৪(সহজ) ঢাকার ভেতরে ডেলিভারির সময় normal, গড় ৪৮ ঘণ্টা, standard deviation ৮ ঘণ্টা। (ক) ৬০ ঘণ্টার z কত, আর ৬০ ঘণ্টার বেশি লাগার সম্ভাবনা? (খ) ৪০ থেকে ৫৬ ঘণ্টার মধ্যে পৌঁছানোর সম্ভাবনা? (গ) ৯৫% অর্ডার কত ঘণ্টার মধ্যে পৌঁছায় (Φ−১(০.৯৫) = ১.৬৪৫)? (ঝালিয়ে নিন: পর্ব ৩৬, ৩৭)
(a) z = (60 - 48) / 8 = 1.5 ; P(Z > 1.5) = 1 - 0.9332 = 0.0668
(b) z = -1 to +1 -> 0.8413 - 0.1587 = 0.6827
(c) x = 48 + 1.645 x 8 = 48 + 13.16 = 61.16 hours
(খ) “৬৮–৯৫–৯৯.৭” নিয়মের প্রথম সংখ্যা। বাস্তবে ডেলিভারির সময় সাধারণত ডান দিকে লম্বা লেজের (skewed) হয়, তাই normal ধরে ৯৫তম শতাংশ বের করলে কম আসতে পারে; আসল ডেটা থাকলে সরাসরি quantile(0.95) নেওয়াই ভালো।
৪.৫(মাঝারি) ছয়টি অর্ডারের ডেলিভারি দিন: ২, ৪, ৪, ৫, ৭, ৮. (ক) Mean, population variance আর নমুনার variance কত? (খ) নমুনার standard deviation s আর SE কত? (গ) গড়ের ৯৫% t-interval কত (t০.৯৭৫, ৫ = ২.৫৭০৬)? (ঝালিয়ে নিন: পর্ব ৩৭)
(a) mean = 30 / 6 = 5
deviations: -3, -1, -1, 0, 2, 3 ; squares: 9, 1, 1, 0, 4, 9 -> 24
population var = 24 / 6 = 4.0 ; sample var = 24 / 5 = 4.8
(b) s = sqrt(4.8) = 2.1909 ; SE = 2.1909 / sqrt(6) = 0.8944
(c) margin = 2.5706 x 0.8944 = 2.2992
CI = 5 - 2.30 to 5 + 2.30 = (2.70, 7.30) days
যাচাই: বিচ্যুতির যোগ (−৩ − ১ − ১ + ০ + ২ + ৩) = ০ হতেই হবে। ফাঁদ দুটি: n − ১-এর বদলে n দিয়ে ভাগ, আর ছোট নমুনায় t-এর বদলে z = ১.৯৬ বসানো, যাতে interval ভুলভাবে সরু হয় (৫ ± ১.৭৫)। “৯৫%” মানে পদ্ধতিটির দীর্ঘমেয়াদি সফলতার হার, এই নির্দিষ্ট interval-এ গড় থাকার ৯৫% সম্ভাবনা নয়।
import numpy as np
from scipy import stats
cod, pre, ret_cod, ret_pre = 120, 80, 18, 4 # ৪.১
print("4.1 P(R)", (ret_cod + ret_pre) / 200, "P(R|COD)", ret_cod / cod,
"P(R|pre)", ret_pre / pre, "P(COD|R)", round(ret_cod / (ret_cod + ret_pre), 4))
N, prev, sens, fpr = 10000, 0.02, 0.90, 0.05 # ৪.২
tp, fp = N * prev * sens, N * (1 - prev) * fpr
post1 = tp / (tp + fp)
odds2 = post1 / (1 - post1) * (sens / fpr)
print("4.2 flagged", round(tp), "+", round(fp), "P(F|flag)", round(post1, 4),
"| two flags", round(odds2 / (1 + odds2), 4))
b = stats.binom(10, 0.1) # ৪.৩ (ক)
print("4.3 binom P0", round(b.pmf(0), 4), "P1", round(b.pmf(1), 4), "P2", round(b.pmf(2), 4),
"P(X>=2)", round(b.sf(1), 4), "mean,var", b.mean(), round(b.var(), 2))
p = stats.poisson(3) # ৪.৩ (খ)
print(" poisson P0", round(p.pmf(0), 4), "P2", round(p.pmf(2), 4), "P(X<=2)",
round(p.cdf(2), 4), "P(X>=4)", round(p.sf(3), 4), "| 2h P0", round(stats.poisson(6).pmf(0), 5))
nd = stats.norm(48, 8) # ৪.৪
print("4.4 z(60)", (60 - 48) / 8, "P(X>60)", round(nd.sf(60), 4), "P(40<X<56)",
round(nd.cdf(56) - nd.cdf(40), 4), "p95", round(nd.ppf(0.95), 2))
x = np.array([2, 4, 4, 5, 7, 8]) # ৪.৫
s, se = x.std(ddof=1), x.std(ddof=1) / np.sqrt(len(x))
t = stats.t.ppf(0.975, df=len(x) - 1)
print("4.5 mean", x.mean(), "var(pop)", x.var(), "var(sample)", round(x.var(ddof=1), 2),
"s", round(s, 4), "SE", round(se, 4), "t", round(t, 4),
"CI", round(float(x.mean() - t * se), 2), round(float(x.mean() + t * se), 2))
lo, hi = stats.t.interval(0.95, df=5, loc=x.mean(), scale=se)
print(" scipy interval", round(float(lo), 2), round(float(hi), 2))4.1 P(R) 0.11 P(R|COD) 0.15 P(R|pre) 0.05 P(COD|R) 0.8182 আর 4.2 flagged 180 + 490 P(F|flag) 0.2687 | two flags 0.8686. scipy.stats থেকে 4.3 binom P0 0.3487 P1 0.3874 P2 0.1937 P(X>=2) 0.2639 mean,var 1.0 0.9 আর poisson P0 0.0498 P2 0.224 P(X<=2) 0.4232 P(X>=4) 0.3528 | 2h P0 0.00248. 4.4 z(60) 1.5 P(X>60) 0.0668 P(40<X<56) 0.6827 p95 61.16. শেষ দুই লাইনে s 2.1909 SE 0.8944 t 2.5706 CI 2.7 7.3, আর scipy-র নিজের t.interval-ও 2.7 7.3 দিয়েছে।
৪.৬(মাঝারি) রিভিউয়ের তিন শ্রেণি (ভালো, মাঝারি, খারাপ)-এর আসল বণ্টন p = (০.৫, ০.২৫, ০.২৫), একটি model-এর অনুমান q = (০.৮, ০.১, ০.১)। (ক) H(p) আর H(q) কত bit? (খ) H(p, q), KL(p‖q) আর KL(q‖p) কত? (গ) একটি রিভিউয়ের আসল শ্রেণিতে model ০.৮ সম্ভাবনা দিলে cross-entropy loss (ln-এ) কত, আর ০.১ দিলে? (ঝালিয়ে নিন: পর্ব ৩৮)
log2: 0.5 -> -1, 0.25 -> -2, 0.8 -> -0.3219, 0.1 -> -3.3219
(a) H(p) = 0.5 x 1 + 0.25 x 2 + 0.25 x 2 = 1.5 bits
H(q) = 0.8 x 0.3219 + 0.1 x 3.3219 + 0.1 x 3.3219 = 0.9219 bits
(b) H(p,q) = 0.5 x 0.3219 + 0.25 x 3.3219 + 0.25 x 3.3219 = 1.8219
KL(p||q) = 1.8219 - 1.5 = 0.3219 bits
H(q,p) = 0.8 x 1 + 0.1 x 2 + 0.1 x 2 = 1.2
KL(q||p) = 1.2 - 0.9219 = 0.2781 bits (not equal: KL is not symmetric)
(c) -ln 0.8 = 0.2231 ; -ln 0.1 = 2.3026
যাচাই: H(p, q) ≥ H(p) সবসময়, সমান শুধু q = p হলে; KL কখনো ঋণাত্মক নয়। (গ) দেখায় কেন cross-entropy loss আত্মবিশ্বাসী ভুলকে কঠোর শাস্তি দেয়: ০.৮ থেকে ০.১-এ নামলে loss দশ গুণের বেশি।
৪.৭(কঠিন) ১২টি অর্ডারের ৪টি ফেরত, ৮টি নয়। পরিশোধ দিয়ে ভাগ: COD ৬টি (৩টি ফেরত), আগাম ৬টি (১টি ফেরত)। জেলা দিয়ে ভাগ: ঢাকা ৮টি (২টি ফেরত), বাইরে ৪টি (২টি ফেরত)। (ক) মূল entropy কত? (খ) দুটি feature-এর information gain কত, decision tree প্রথমে কোনটিতে ভাগ করবে? (ঝালিয়ে নিন: পর্ব ৩৮)
(a) H(4/12) = -(1/3) log2(1/3) - (2/3) log2(2/3) = 0.9183
(b) payment : COD H(3/6) = 1.0 ; prepaid H(1/6) = 0.6500
weighted = 6/12 x 1.0 + 6/12 x 0.6500 = 0.8250
IG = 0.9183 - 0.8250 = 0.0933
district: Dhaka H(2/8) = 0.8113 ; outside H(2/4) = 1.0
weighted = 8/12 x 0.8113 + 4/12 x 1.0 = 0.8742
IG = 0.9183 - 0.8742 = 0.0441
split on payment first (0.0933 > 0.0441)
যাচাই: IG কখনো ঋণাত্মক নয়, আর মূল entropy-র বেশি হতে পারে না। ফাঁদ: শাখার entropy-গুলো ওজন ছাড়া গড় করা; এখানে জেলার দুটি শাখা ৮ আর ৪, তাই ওজন ২/৩ আর ১/৩. বড় সংখ্যক মানের feature (যেমন অর্ডার নম্বর) IG-কে কৃত্রিমভাবে বাড়ায়; সেজন্য gain ratio-র মতো সংশোধন আছে।
import numpy as np
from scipy.stats import entropy
H = lambda p: -sum(x * np.log2(x) for x in p if x > 0) # bit-এ entropy
CE = lambda p, q: -sum(a * np.log2(b) for a, b in zip(p, q) if a > 0)
p, q = [0.5, 0.25, 0.25], [0.8, 0.1, 0.1] # ৪.৬
print("4.6 H(p)", round(H(p), 4), "H(q)", round(H(q), 4),
"H(p,q)", round(CE(p, q), 4), "H(q,p)", round(CE(q, p), 4))
print(" KL(p||q)", round(CE(p, q) - H(p), 4), "KL(q||p)", round(CE(q, p) - H(q), 4),
"| scipy", round(float(entropy(p, q, base=2)), 4), round(float(entropy(q, p, base=2)), 4))
print(" H(0.9,0.1)", round(H([0.9, 0.1]), 4), "| -ln 0.8 =", round(-np.log(0.8), 4),
"| -ln 0.1 =", round(-np.log(0.1), 4))
def ig(parent, children): # ৪.৭: (হ্যাঁ, না) গোনা
Hc = lambda c: H([c[0] / sum(c), c[1] / sum(c)])
n = sum(parent)
rest = sum(sum(c) / n * Hc(c) for c in children)
return [round(float(v), 4) for v in (Hc(parent), rest, Hc(parent) - rest)]
print("4.7 payment (H, weighted, IG):", ig((4, 8), [(3, 3), (1, 5)]))
print(" district (H, weighted, IG):", ig((4, 8), [(2, 6), (2, 2)]))
print(" H(1/6) =", round(H([1 / 6, 5 / 6]), 4), "H(1/4) =", round(H([0.25, 0.75]), 4))4.6 H(p) 1.5 H(q) 0.9219 H(p,q) 1.8219 H(q,p) 1.2; নিজের সূত্রের KL আর scipy-র entropy(p, q, base=2) একই: KL(p||q) 0.3219 KL(q||p) 0.2781 | scipy 0.3219 0.2781. পরের লাইনে -ln 0.8 = 0.2231 আর -ln 0.1 = 2.3026. ৪.৭: payment (H, weighted, IG): [0.9183, 0.825, 0.0933] আর district (H, weighted, IG): [0.9183, 0.8742, 0.0441]; শেষ লাইনে শাখার entropy H(1/6) = 0.65 H(1/4) = 0.8113.
৫ · Search আর খেলা — BFS থেকে A*, alpha-beta, AC-3 আর hill climbing
ঝালিয়ে নিন: পর্ব ৩৯ · সমস্যাকে search হিসেবে দেখা, পর্ব ৪০ · BFS, DFS আর uniform cost, পর্ব ৪১ · Heuristic আর A*, পর্ব ৪২ · minimax আর alpha-beta, পর্ব ৪৩ · Constraint satisfaction, পর্ব ৪৪ · Local search. Graph-এর মৌলিক তত্ত্ব DSA · Graph-এ।
BFS: FIFO frontier, সবচেয়ে কম ধাপের পথ। DFS: LIFO, প্রথম যে পথ মেলে। UCS: সবচেয়ে ছোট g আগে। Greedy: সবচেয়ে ছোট h আগে। A*: f = g + h সবচেয়ে ছোট আগে; h admissible (কখনো আসল খরচের বেশি নয়) হলে পথ সর্বোত্তম, consistent হলে h(u) ≤ c(u, v) + h(v) প্রতিটি রাস্তায়। Alpha-beta: α ≥ β হলেই বাকি ভাইবোন ছাঁটাই।
৫.১ থেকে ৫.৩ একই রাস্তার মানচিত্রে। বাজারঘরের রাইডার গুদাম S থেকে গ্রাহক G-এর কাছে যাবেন; রাস্তা দুই দিকেই চলে, সংখ্যাগুলো মিনিটে খরচ, আর প্রতিটি মোড়ের নিচে h, G পর্যন্ত আনুমানিক মিনিট। সব প্রশ্নে প্রতিবেশী বর্ণক্রমে, সমান মানে বর্ণক্রমে আগেরটি, আর একই node দুবার frontier-এ ঢোকে না (graph search).
৫.১–৫.৩-এর মানচিত্র — রাস্তার খরচ আর heuristic
Edge costs in minutes; h under each node = estimated minutes to G
৫.১(সহজ) ছবি ৭৫.১-এর মানচিত্র: রাস্তা S–A ২, S–B ৫, A–B ২, A–C ৬, B–C ২, B–D ৪, C–G ৩, D–G ২ (দুই দিকেই)। (ক) BFS-এ (goal test node তৈরির সময়) কোন ক্রমে node expand হয়, কোন পথ আর খরচ কত? (খ) DFS-এ (প্রতিবেশী বর্ণক্রমে, দেখা node আর নয়) কোন পথ? (গ) প্রতিবেশী উল্টো বর্ণক্রমে নিলে DFS কোন পথ দেয়? (ঝালিয়ে নিন: পর্ব ৪০)
(a) BFS: expand S -> generate A, B
expand A -> B seen, generate C
expand B -> C seen, generate D
expand C -> generate G: goal!
expanded: S, A, B, C ; path S-A-C-G ; cost 2 + 6 + 3 = 11 (3 edges)
(b) DFS: S -> A -> B -> C -> G ; cost 2 + 2 + 2 + 3 = 9
(c) reverse: S -> B -> D -> G ; cost 5 + 4 + 2 = 11
BFS সবচেয়ে কম রাস্তার সংখ্যার পথ দেয় (তিনটি), সবচেয়ে কম খরচের নয়। (খ)-তে DFS ভাগ্যক্রমে সর্বোত্তম পথ পেয়েছে, শুধু বর্ণক্রমের কারণে; (গ)-তে ক্রম উল্টালেই ১১. তাই “DFS সর্বোত্তম” কখনো লিখবেন না।
৫.২(মাঝারি) একই মানচিত্রে (ক) Uniform-cost search (goal test expand-এর সময়)-এ expand-এর ক্রম, প্রতিটির g, পথ আর খরচ কী? (খ) শুধু h দেখে greedy best-first search-এ? (ঝালিয়ে নিন: পর্ব ৪০, ৪১)
(a) UCS (pop smallest g):
S(0) -> A g=2, B g=5
A(2) -> B improved to 2+2 = 4, C g=8
B(4) -> C improved to 4+2 = 6, D g=8
C(6) -> G g=9
D(8) -> G via D = 10, not better
G(9) -> goal. path S-A-B-C-G, cost 9
(b) greedy (pop smallest h):
S(7) -> A(6), B(4) ; B(4) -> C(3), D(2) ; D(2) -> G(0) ; G
path S-B-D-G, cost 11
UCS-এ G তৈরি হয় C expand-এর সময় (g = ৯), কিন্তু তখনই থামলে চলে না; D (৮) তখনো সস্তা, তাই আগে D খোলে। Goal test expand-এর সময় রাখার কারণ এটিই: frontier-এ সস্তা পথ থাকতে পারে। Greedy মাত্র চারটি node খুলেছে, কিন্তু খরচ ১১; দ্রুত, তবে সর্বোত্তম নয়।
৫.৩(কঠিন) একই মানচিত্রে h: S ৭, A ৬, B ৪, C ৩, D ২, G ০. (ক) h কি admissible আর consistent? (খ) A*-এ expand-এর ক্রম, প্রতিটির f, পথ আর খরচ কী? (গ) UCS-এর চেয়ে কয়টি node কম খুলল? (ঝালিয়ে নিন: পর্ব ৪১)
(a) true cost to G: G 0, D 2, C 3, B min(2+3, 4+2) = 5, A 2+5 = 7, S 9
h <= true: 7<=9, 6<=7, 4<=5, 3<=3, 2<=2 -> admissible
every edge |h(u) - h(v)| <= cost: S-A 1<=2, A-B 2<=2, C-G 3<=3, ... -> consistent
(b) S f=0+7=7 -> A f=2+6=8, B f=5+4=9
A f=8 -> B f=4+4=8 (improved), C f=8+3=11
B f=8 -> C f=6+3=9 (improved), D f=8+2=10
C f=9 -> G f=9+0=9
G f=9 is smaller than D f=10 -> pop G -> goal
expanded S, A, B, C, G ; path S-A-B-C-G ; cost 9
(c) UCS expanded 6 nodes, A* 5: D was never opened
A* আর UCS একই খরচ (৯) দিয়েছে, যা admissible h-এর প্রতিশ্রুতি। A আর B দুটিরই f = ৮ হলে বর্ণক্রমে A আগে। নিচের stepper-এ প্রতিটি ধাপের frontier দেখুন।
expand S (f = 0 + 7 = 7)
frontier: A f=8 (g2), B f=9 (g5)
expand A (f = 8)
B: g 5 -> 4, f = 4 + 4 = 8
C: g 8, f = 8 + 3 = 11
frontier: B f=8, C f=11
expand B (f = 8)
C: g 8 -> 6, f = 9
D: g 8, f = 8 + 2 = 10
frontier: C f=9, D f=10
expand C (f = 9)
G: g 6 + 3 = 9, f = 9
frontier: G f=9, D f=10
pop G (f = 9) -> goal test passes
path S-A-B-C-G
cost 9 ; D never expanded
- শুরু। A-এর f = ২ + ৬ = ৮, B-এর ৫ + ৪ = ৯; ছোটটি A.
- A খোলা। A হয়ে B-তে g = ৪, আগের ৫-এর চেয়ে কম, তাই B-এর f ৮. C আসে f = ১১ নিয়ে।
- B খোলা। B হয়ে C-তে g = ৬, তাই C-এর f ৯. D নতুন, f = ১০.
- C খোলা। G তৈরি হয় f = ৯ নিয়ে; goal test খোলার সময়, তাই এখনো থামা নয়।
- G খোলা। সবচেয়ে ছোট f এখন G (৯), goal test সফল। খরচ ৯; D খোলার দরকার পড়েনি।
import heapq, collections; G = {}
E = {"SA": 2, "SB": 5, "AB": 2, "AC": 6, "BC": 2, "BD": 4, "CG": 3, "DG": 2}
for (u, v), c in E.items(): G.setdefault(u, {})[v] = c; G.setdefault(v, {})[u] = c
h = {"S": 7, "A": 6, "B": 4, "C": 3, "D": 2, "G": 0}; cost = lambda p: sum(G[a][b] for a, b in zip(p, p[1:]))
def bfs(): # goal test node তৈরির সময়
fr, seen, order = collections.deque([["S"]]), {"S"}, []
while fr:
p = fr.popleft(); order.append(p[-1])
for n in sorted(G[p[-1]]):
if n == "G": return order, p + [n], cost(p + [n])
if n not in seen: seen.add(n); fr.append(p + [n])
def dfs(p, seen, rev=False): # বর্ণক্রমে (rev=True হলে উল্টো)
if p[-1] == "G": return p, cost(p)
for n in sorted(G[p[-1]], reverse=rev):
if n in seen: continue
seen.add(n); r = dfs(p + [n], seen, rev)
if r: return r
def best_first(f): # goal test expand-এর সময়
fr, best, order = [(f(0, "S"), "S", 0, ["S"])], {"S": 0}, []
while fr:
_, n, g, p = heapq.heappop(fr)
if g > best[n]: continue # পুরোনো, বেশি দামি entry
order.append(f"{n}({f(g, n)})")
if n == "G": return order, p, g
for m in sorted(G[n]):
if m not in best or g + G[n][m] < best[m]:
best[m] = g + G[n][m]; heapq.heappush(fr, (f(best[m], m), m, best[m], p + [m]))
print("5.1 BFS", bfs(), "\n DFS", dfs(["S"], {"S"}), "| reverse", dfs(["S"], {"S"}, True))
print("5.2 UCS ", best_first(lambda g, n: g), "\n GBFS", best_first(lambda g, n: h[n]))
print("5.3 A* ", best_first(lambda g, n: g + h[n]))কোনো package নেই, শুধু heapq আর collections. 5.1 BFS (['S', 'A', 'B', 'C'], ['S', 'A', 'C', 'G'], 11), তারপর DFS (['S', 'A', 'B', 'C', 'G'], 9) | reverse (['S', 'B', 'D', 'G'], 11). UCS লাইনে ['S(0)', 'A(2)', 'B(4)', 'C(6)', 'D(8)', 'G(9)'], GBFS লাইনে ['S(7)', 'B(4)', 'D(2)', 'G(0)'] আর খরচ 11, আর A* লাইনে ['S(7)', 'A(8)', 'B(8)', 'C(9)', 'G(9)'], পথ S–A–B–C–G, খরচ 9. একটি best_first() শুধু অগ্রাধিকার (g, h বা g + h) বদলে তিনটিই চালায়।
৫.৪(মাঝারি) একটি খেলার গাছ: মূলে MAX, তার দুই সন্তান MIN (B, C), প্রতিটির দুই সন্তান MAX (B-এর D, E; C-এর F, G), আর প্রতিটি MAX-এর দুটি পাতা। বাঁ থেকে ডানে পাতার মান: D: ৩, ৫; E: ৬, ৯; F: ১, ২; G: ০, −১. (ক) Minimax-এ প্রতিটি node-এর মান আর মূলের সেরা চাল কী? (খ) বাঁ থেকে ডানে alpha-beta চালালে কোন পাতাগুলো দেখা হয় না? (ঝালিয়ে নিন: পর্ব ৪২)
(a) D = max(3, 5) = 5 ; E = max(6, 9) = 9 ; F = max(1, 2) = 2 ; G = max(0, -1) = 0
B = min(5, 9) = 5 ; C = min(2, 0) = 0 ; root = max(5, 0) = 5 -> move to B
(b) B: D sees 3, 5 -> 5 ; B's beta = 5
E (alpha -inf, beta 5): leaf 6 -> 6 >= 5 -> prune leaf 9
root alpha = 5
C: F (alpha 5): leaves 1, 2 -> F = 2 ; C's beta = 2 <= alpha 5
-> prune whole G (leaves 0, -1)
leaves seen: 3, 5, 6, 1, 2 ; pruned: 9, 0, -1 (3 of 8)
যাচাই: ছাঁটাইয়ের পরেও মূলের মান ৫, minimax-এর সমান; alpha-beta উত্তর বদলায় না, শুধু কাজ কমায়। ছাঁটাই হওয়া node-এর “মান” লিখতে হলে সীমা লিখুন: E ≥ ৬, C ≤ ২. Ordering ভালো হলে, অর্থাৎ সেরা চাল আগে এলে, ছাঁটাই আরও বাড়ে।
৫.৪-এর গাছ — alpha-beta-তে কোন পাতা বাদ পড়ে
MAX (▲) – MIN (▼) – MAX; grey dashed leaves are pruned
৫.৫(মাঝারি) তিনটি ডেলিভারি স্লট X, Y, Z, প্রতিটির domain {১, ২, ৩}, শর্ত X < Y আর Y < Z. AC-3 queue শুরু হয় (X,Y), (Y,X), (Y,Z), (Z,Y) ক্রমে; কোনো domain থেকে মান মুছলে তার অন্য প্রতিবেশীর arc (queue-তে আগে থেকে না থাকলে) শেষে যোগ হয়। প্রতিটি revise-এর পরে domain কী, মোট কয়টি revise, আর search ছাড়াই উত্তর পাওয়া যায় কি? (ঝালিয়ে নিন: পর্ব ৪৩)
1. (X,Y): X=3 has no Y > 3 -> X = {1, 2}
2. (Y,X): Y=1 has no X < 1 -> Y = {2, 3} ((Z,Y) already queued)
3. (Y,Z): Y=3 has no Z > 3 -> Y = {2} add (X,Y)
4. (Z,Y): Z=1, 2 have no Y < Z -> Z = {3} (Z has no other neighbour)
5. (X,Y): X=2 has no Y > 2 -> X = {1}
queue empty after 5 revisions: X=1, Y=2, Z=3 (no search needed)
এখানে arc consistency একাই সমাধান দিয়েছে, কারণ শর্তগুলো একটি শিকলের মতো। সাধারণভাবে AC-3 শুধু domain ছোট করে, তারপর backtracking লাগে; কোনো domain খালি হলে বোঝা যায় সমাধানই নেই।
৫.৬(মাঝারি) ৪-রানি সমস্যায় অবস্থা লেখা হয় কলাম ০ থেকে ৩-এ রানির সারি দিয়ে (সারি ০–৩)। h = পরস্পরকে আক্রমণ করা রানির জোড়া (একই সারি বা কর্ণ)। (ক) অবস্থা (২, ০, ০, ২)-এর h কত? (খ) একটি রানিকে নিজের কলামে সরালে কয়টি প্রতিবেশী, আর সেরা প্রতিবেশীর h কত? (গ) (৩, ১, ২, ০)-এর h কত, আর steepest-ascent hill climbing সেখানে কী করে? (ঝালিয়ে নিন: পর্ব ৪৪)
(a) pairs (col i, col j): attack if same row or |row diff| = j - i
(0,1) 2,0 diff 2 dist 1 no (0,2) 2,0 diff 2 dist 2 yes
(0,3) 2,2 same row yes (1,2) 0,0 same row yes
(1,3) 0,2 diff 2 dist 2 yes (2,3) 0,2 diff 2 dist 1 no -> h = 4
(b) neighbours = 4 columns x 3 other rows = 12
best h = 2: move col 0 to row 3 -> (3,0,0,2), or col 3 to row 3 -> (2,0,0,3)
(c) (3,1,2,0): (0,3) rows 3,0 diff 3 dist 3 yes
(1,2) rows 1,2 diff 1 dist 1 yes ; other 4 pairs no -> h = 2
all 12 neighbours have h >= 2 -> no strictly better move: stuck
(local minimum / plateau)
(গ)-র অবস্থা সমাধান নয় (h ≠ ০), তবু কোনো এক চালে উন্নতি হয় না। এখান থেকে বাঁচার উপায় পর্ব ৪৪-এ দেখেছেন: sideways move-এর অনুমতি, random restart বা simulated annealing.
import itertools, math
leaves, seen = [3, 5, 6, 9, 1, 2, 0, -1], [] # ৫.৪: MAX-MIN-MAX, বাঁ থেকে ডানে
def ab(i, depth, a, b, is_max): # i = এই subtree-র প্রথম পাতা
if depth == 0: seen.append(leaves[i]); return leaves[i]
v, w = (-math.inf if is_max else math.inf), 2 ** (depth - 1)
for k in range(2):
x = ab(i + k * w, depth - 1, a, b, not is_max)
v = max(v, x) if is_max else min(v, x)
a, b = (max(a, v), b) if is_max else (a, min(b, v))
if a >= b: break # বাকি ভাই-বোন ছাঁটাই
return v
print("5.4 root", ab(0, 3, -math.inf, math.inf, True), "| leaves seen", seen,
"| pruned", len(leaves) - len(seen))
D = {v: {1, 2, 3} for v in "XYZ"} # ৫.৫: X < Y, Y < Z
ok = {("X", "Y"): lambda x, y: x < y, ("Y", "X"): lambda y, x: x < y,
("Y", "Z"): lambda y, z: y < z, ("Z", "Y"): lambda z, y: y < z}
queue, step = [("X", "Y"), ("Y", "X"), ("Y", "Z"), ("Z", "Y")], 0
while queue:
xi, xj = queue.pop(0); step += 1
gone = {a for a in D[xi] if not any(ok[(xi, xj)](a, b) for b in D[xj])}
D[xi] -= gone
new = [(xk, xi) for (xk, t) in ok if t == xi and xk != xj and (xk, xi) not in queue] if gone else []
queue += new
print(f" {step}. ({xi},{xj}) remove {sorted(gone)} -> {xi}={sorted(D[xi])} add {new}")
h = lambda s: sum(s[i] == s[j] or abs(s[i] - s[j]) == j - i
for i, j in itertools.combinations(range(4), 2))
for s in [(2, 0, 0, 2), (3, 1, 2, 0)]: # ৫.৬: কলাম ০–৩-এ রানির সারি
nb = [(h(s[:c] + (r,) + s[c + 1:]), c, r) for c in range(4) for r in range(4) if r != s[c]]
best = min(nb)[0]; print("5.6", s, "h", h(s), "| neighbours", len(nb), "best h", best,
[(c, r) for hh, c, r in nb if hh == best])5.4 root 5 | leaves seen [3, 5, 6, 1, 2] | pruned 3: ছাঁটাই সমেত মূলের মান ৫, দেখা পাতা পাঁচটি। AC-3-এর পাঁচ লাইন হাতের trace-এর সাথে হুবহু: 3. (Y,Z) remove [3] -> Y=[2] add [('X', 'Y')] থেকে 5. (X,Y) remove [2] -> X=[1] add []. শেষ দুই লাইন ৫.৬: (2, 0, 0, 2) h 4 | neighbours 12 best h 2 [(0, 3), (3, 3)], আর (3, 1, 2, 0) h 2 | neighbours 12 best h 2, অর্থাৎ সেরা প্রতিবেশীও h = ২, উন্নতি নেই।
৬ · Logic — truth table, CNF, resolution আর chaining
ঝালিয়ে নিন: পর্ব ৪৫ · Propositional logic (truth table, CNF, resolution), পর্ব ৪৬ · First-order logic, পর্ব ৪৭ · Rule-based আর expert system (forward ও backward chaining).
n টি চলকে truth table-এ ২n সারি। P → Q ≡ ¬P ∨ Q; P ↔ Q ≡ (P → Q) ∧ (Q → P). CNF-এ যাওয়ার ক্রম: ↔ আর → সরান, ¬ ভেতরে ঠেলুন (De Morgan), তারপর ∧-এর ওপর ∨ ছড়ান। Resolution: (A ∨ x) আর (B ∨ ¬x) থেকে (A ∨ B); KB ⊨ α প্রমাণ করতে KB ∧ ¬α থেকে empty clause বের করুন। KB ⊨ α মানে KB যেখানে সত্য, α-ও সেখানে সত্য।
৬.১(সহজ) (ক) (P ∨ Q) → R-এর truth table-এ কয়টি সারি, তার কয়টিতে বাক্যটি সত্য? (খ) (P → Q) ∨ (Q → P) কি valid? (গ) KB = {P ∨ Q, ¬P ∨ R}. KB কয়টি model-এ সত্য, আর KB ⊨ Q ∨ R কি? (ঝালিয়ে নিন: পর্ব ৪৫)
(a) 2^3 = 8 rows ; false only when (P v Q) = T and R = F
(P v Q) = T in 3 of the 4 (P,Q) rows -> 3 false rows -> 8 - 3 = 5 true
(b) if Q = T then (P -> Q) = T ; if Q = F then (Q -> P) = T -> true in 4 of 4: valid
(c) KB true: P Q R
T T T, T F T (P = T needs R = T)
F T T, F T F (P = F needs Q = T)
4 models ; Q v R is true in all 4 -> KB entails Q v R
(গ) আসলে resolution-এর একটি ধাপ: (P ∨ Q) আর (¬P ∨ R) থেকে (Q ∨ R). Model গুনে আর resolution করে একই উত্তর আসা যাচাই হিসেবে চমৎকার।
৬.২(মাঝারি) CNF-এ লিখুন: (ক) P ↔ (Q ∨ R); (খ) ¬(A → (B ∧ C)). প্রতিটিতে কয়টি clause? (ঝালিয়ে নিন: পর্ব ৪৫)
(a) (P -> (Q v R)) ^ ((Q v R) -> P)
= (~P v Q v R) ^ (~(Q v R) v P)
= (~P v Q v R) ^ ((~Q ^ ~R) v P)
= (~P v Q v R) ^ (~Q v P) ^ (~R v P) -> 3 clauses
(b) ~(~A v (B ^ C))
= A ^ ~(B ^ C)
= A ^ (~B v ~C) -> 2 clauses
যাচাই: আটটি সারিতে মূল বাক্য আর CNF-এর মান মিলিয়ে দেখুন; নিচের চেকার দুটিতেই True দেয়। ফাঁদ: ¬(B ∧ C)-কে ¬B ∧ ¬C লেখা; De Morgan-এ ∧ বদলে ∨ হয়।
৬.৩(মাঝারি) A = “ক্রেতা বিকাশে টাকা দিয়েছেন”, B = “ক্রেতা কার্ডে টাকা দিয়েছেন”, C = “অর্ডার নিশ্চিত”। KB: A ∨ B, A → C, B → C. Resolution দিয়ে প্রমাণ করুন KB ⊨ C; প্রতিটি ধাপে কোন দুটি clause থেকে কী পেলেন লিখুন। (ঝালিয়ে নিন: পর্ব ৪৫)
clauses: 1. A v B 2. ~A v C 3. ~B v C 4. ~C (negated goal)
5. from 2 + 4 (on C): ~A
6. from 3 + 4 (on C): ~B
7. from 1 + 5 (on A): B
8. from 7 + 6 (on B): EMPTY -> contradiction, so KB entails C
এটি “ক্ষেত্রভেদে প্রমাণ”: দুই পথেই C, আর অন্তত একটি পথ সত্য। চার ধাপের resolution-এ শেষ clause খালি। চেকার আটটি model গুনেও (model checking) একই রায় দেয়।
৬.৪(কঠিন) নিয়ম (ক্রমসহ): R1: A ∧ B → C; R2: C → D; R3: B ∧ D → E; R4: E → G; R5: F → G; R6: A ∧ H → F. Fact: A, B. (ক) Forward chaining-এ প্রতি পাসে নিয়মগুলো ক্রমে দেখা হয়, শর্ত মিললে আর ফল নতুন হলে নিয়ম চলে; পাস চলে যতক্ষণ নতুন কিছু আসে। কোন ক্রমে কোন নিয়ম চলে, কয়টি পাস, শেষে কোন fact? (খ) লক্ষ্য G-এর জন্য backward chaining-এ (G-এর নিয়মগুলো ক্রমে, শর্ত বর্ণক্রমে) কোন কোন লক্ষ্য ডাকা হয়? R5 কি দেখা হয়? (ঝালিয়ে নিন: পর্ব ৪৭)
(a) pass 1: R1 (A,B) -> C ; R2 (C) -> D ; R3 (B,D) -> E ; R4 (E) -> G
R5 needs F (unknown) ; R6 needs H (unknown)
pass 2: nothing new -> stop (2 passes)
facts: A, B, C, D, E, G (F never derived)
(b) G? -> R4: need E
E? -> R3: need B, D
B? fact
D? -> R2: need C
C? -> R1: need A, B -> facts
goals called: G, E, B, D, C, A, B ; R4 succeeds so R5 is never tried
একই KB, দুই কৌশল। Forward chaining সব জানা fact থেকে যা বের করা যায় সব করে (এখানে G-ও, কিন্তু প্রশ্ন না থাকলেও); backward chaining লক্ষ্য থেকে শুধু দরকারি নিয়ম খোঁজে, তাই R5, R6 ছোঁয় না। পাস গোনায় সতর্কতা: “কিছু নতুন এল না” বোঝাতেই শেষ পাসটি লাগে।
from itertools import product
imp = lambda a, b: (not a) or b
rows = list(product([True, False], repeat=3))
print("6.1 (PvQ)->R true rows:", sum(imp(p or q, r) for p, q, r in rows), "of", len(rows))
print(" (P->Q)v(Q->P) true:", sum(imp(p, q) or imp(q, p) for p, q in product([1, 0], repeat=2)), "of 4")
kb = [(p, q, r) for p, q, r in rows if (p or q) and ((not p) or r)]
print(" KB models", len(kb), "| Q v R true in all of them:", all(q or r for p, q, r in kb))
cnf1 = all((p == (q or r)) == (((not p) or q or r) and ((not q) or p) and ((not r) or p))
for p, q, r in rows)
cnf2 = all((not imp(a, b and c)) == (a and ((not b) or (not c))) for a, b, c in rows)
print("6.2 P<->(QvR) CNF equal:", cnf1, "| not(A->(B^C)) CNF equal:", cnf2)
res = lambda c1, c2, x: sorted((set(c1) | set(c2)) - {x, "~" + x}) # x আর ~x বাদ
c3 = res(["~A", "C"], ["~C"], "C"); c4 = res(["~B", "C"], ["~C"], "C")
c5 = res(["A", "B"], c3, "A"); c6 = res(c5, c4, "B")
print("6.3 resolvents:", c3, c4, c5, c6 or "EMPTY")
print(" model check:", all(imp((a or b) and imp(a, c) and imp(b, c), c) for a, b, c in rows))
rules = [("R1", {"A", "B"}, "C"), ("R2", {"C"}, "D"), ("R3", {"B", "D"}, "E"),
("R4", {"E"}, "G"), ("R5", {"F"}, "G"), ("R6", {"A", "H"}, "F")]
facts, fired, changed, trace = {"A", "B"}, [], True, []
while changed: # ৬.৪ forward: প্রতি পাসে নিয়ম ক্রমে
changed = False
for name, pre, post in rules:
if pre <= facts and post not in facts:
facts.add(post); fired.append(f"{name}:{post}"); changed = True
print("6.4 forward fired", fired, "| facts", sorted(facts))
def bc(goal): # backward: প্রথম মেলা নিয়ম আগে
trace.append(goal)
if goal in {"A", "B"}: return True
return any(all(bc(p) for p in sorted(pre)) for _, pre, post in rules if post == goal)
print(" backward G:", bc("G"), "| calls:", " ".join(trace))6.1 (PvQ)->R true rows: 5 of 8, (P->Q)v(Q->P) true: 4 of 4 আর KB models 4 | Q v R true in all of them: True. 6.2 P<->(QvR) CNF equal: True | not(A->(B^C)) CNF equal: True: আটটি সারিতেই মান মিলেছে। 6.3 resolvents: ['~A'] ['~B'] ['B'] EMPTY হাতের ধাপ ৫–৮, আর model check: True. শেষ দুই লাইন: forward fired ['R1:C', 'R2:D', 'R3:E', 'R4:G'] আর backward G: True | calls: G E B D C A B.
৭ · অনিশ্চয়তায় যুক্তি — Bayesian network, Markov, Viterbi আর সিদ্ধান্ত
ঝালিয়ে নিন: পর্ব ৫০ · Bayes-এর উপপাদ্য, পর্ব ৫২ · Bayesian network, পর্ব ৫৩ · Markov chain আর HMM, পর্ব ৫৪ · অনিশ্চয়তায় সিদ্ধান্ত (expected utility, MDP).
Bayesian network-এ joint = প্রতিটি node-এর P(node | parents)-এর গুণফল; query = দরকারি সারিগুলোর joint যোগ করে normalize (enumeration). Markov chain: n ধাপ পরে বণ্টন x0Tn; stationary π-তে πT = π, ∑π = ১. Viterbi: vt(s) = maxs′ vt−১(s′) P(s | s′) × P(ot | s), সঙ্গে পেছনের pointer. EU(a) = ∑ P(s)U(a, s); VPI = (তথ্যসহ প্রত্যাশিত মান) − (তথ্য ছাড়া সেরা EU). Value iteration: V(s) ← maxa ∑ P(s′ | s, a)[R + γV(s′)]।
৭.১(মাঝারি) একটি Bayesian network: বৃষ্টি (R) আর যানজট (J) দুটোই ডেলিভারি দেরি (D)-র parent, আর D হলো অভিযোগ (C)-এর parent. P(R) = ০.৩, P(J) = ০.৪; P(D | R, J): (সত্য, সত্য) ০.৯, (সত্য, মিথ্যা) ০.৬, (মিথ্যা, সত্য) ০.৫, (মিথ্যা, মিথ্যা) ০.১; P(C | D) = ০.৭, P(C | ¬D) = ০.০৫. (ক) P(R, ¬J, D, C) কত? (খ) P(D) আর P(R | D)? (গ) Enumeration দিয়ে P(R | C)? (ঘ) পুরো joint table-এ কয়টি স্বাধীন সংখ্যা লাগত, আর network-এ কয়টি? (ঝালিয়ে নিন: পর্ব ৫২)
(a) 0.3 x 0.6 x 0.6 x 0.7 = 0.0756
(b) P(D) = 0.3x0.4x0.9 + 0.3x0.6x0.6 + 0.7x0.4x0.5 + 0.7x0.6x0.1
= 0.108 + 0.108 + 0.140 + 0.042 = 0.398
P(R | D) = (0.108 + 0.108) / 0.398 = 0.5427
(c) P(D | R) = 0.4 x 0.9 + 0.6 x 0.6 = 0.72
P(C | R) = 0.72 x 0.7 + 0.28 x 0.05 = 0.518 -> P(R, C) = 0.3 x 0.518 = 0.1554
P(C) = 0.398 x 0.7 + 0.602 x 0.05 = 0.2786 + 0.0301 = 0.3087
P(R | C) = 0.1554 / 0.3087 = 0.5034
(d) full joint: 2^4 - 1 = 15 ; network: R 1 + J 1 + D 4 + C 2 = 8
প্রমাণ যত দূরের, বিশ্বাসের হালনাগাদ তত দুর্বল: সরাসরি দেরি দেখলে বৃষ্টির সম্ভাবনা ০.৩ থেকে ০.৫৪, শুধু অভিযোগ দেখলে ০.৫০. যাচাই: P(R | D) > P(R), কারণ দেরি বৃষ্টির পক্ষে প্রমাণ।
৭.২(মাঝারি) (ক) আবহাওয়ার Markov chain, অবস্থা (রোদ, মেঘ, বৃষ্টি), transition-এর সারিগুলো: রোদ (০.৬, ০.৩, ০.১), মেঘ (০.৩, ০.৪, ০.৩), বৃষ্টি (০.২, ০.৩, ০.৫)। আজ রোদ; কাল আর পরশুর বণ্টন কী? (খ) একজন ক্রেতা এক সপ্তাহে কিনলে পরের সপ্তাহে কেনেন ০.৭ সম্ভাবনায়, না কিনলে ০.২ সম্ভাবনায়। এই সপ্তাহে কিনলে দুই সপ্তাহ পরে কেনার সম্ভাবনা কত? দীর্ঘমেয়াদে কত ভাগ সপ্তাহে কেনেন? (ঝালিয়ে নিন: পর্ব ৫৩)
(a) day 1 = row "sun" = (0.6, 0.3, 0.1)
day 2 = 0.6 x (0.6,0.3,0.1) + 0.3 x (0.3,0.4,0.3) + 0.1 x (0.2,0.3,0.5)
= (0.36+0.09+0.02, 0.18+0.12+0.03, 0.06+0.09+0.05) = (0.47, 0.33, 0.20)
(b) T = [[0.7, 0.3], [0.2, 0.8]] (buy, not)
P(buy after 2 | buy) = 0.7 x 0.7 + 0.3 x 0.2 = 0.49 + 0.06 = 0.55
stationary: pi_buy x 0.3 = pi_not x 0.2 and pi_buy + pi_not = 1
-> pi_buy = 0.2 / (0.3 + 0.2) = 0.4 ; pi_not = 0.6
check: 0.4 x 0.7 + 0.6 x 0.2 = 0.28 + 0.12 = 0.40
যাচাই: প্রতিটি বণ্টনের যোগ ১ (০.৪৭ + ০.৩৩ + ০.২০)। দুই-অবস্থার শর্টকাট “যত বেরোয় তত ঢোকে”: πকেনা × ০.৩ = πনা × ০.২. শুরু যা-ই হোক, দীর্ঘমেয়াদে ৪০% সপ্তাহে কেনা, এই ধরনের chain-এ শুরুর অবস্থা ধীরে ধীরে ভুলে যাওয়া হয়।
৭.৩(সহজ) ঈদের আগে বাড়তি আম মজুত করবেন কি না। চাহিদা বেশি হওয়ার সম্ভাবনা ০.৪. লাভ (হাজার টাকায়): বাড়তি মজুত — চাহিদা বেশি হলে +৫০, কম হলে −২০; সাধারণ মজুত — বেশি হলে +১০, কম হলে +৫. (ক) দুই সিদ্ধান্তের expected utility, কোনটি নেবেন? (খ) নিখুঁত পূর্বাভাসের মূল্য (VPI) কত? (ঝালিয়ে নিন: পর্ব ৫৪)
(a) EU(extra) = 0.4 x 50 + 0.6 x (-20) = 20 - 12 = 8
EU(normal) = 0.4 x 10 + 0.6 x 5 = 4 + 3 = 7 -> choose extra (8)
(b) with a perfect forecast: high -> extra (50), low -> normal (5)
value = 0.4 x 50 + 0.6 x 5 = 20 + 3 = 23
VPI = 23 - 8 = 15 (thousand taka)
অর্থ: একটি নিখুঁত চাহিদার পূর্বাভাসের জন্য সর্বোচ্চ ১৫ হাজার টাকা দেওয়া যুক্তিসংগত, তার বেশি নয়। আর বাস্তবের পূর্বাভাস নিখুঁত নয়, তাই তার মূল্য আরও কম। EU ৮ বনাম ৭ খুব কাছাকাছি; সম্ভাবনা সামান্য বদলালেই সিদ্ধান্ত উল্টে যায়, তাই sensitivity দেখা দরকার। লাভের সংখ্যাগুলো কাল্পনিক।
import numpy as np
from itertools import product
pR, pJ = 0.3, 0.4 # ৭.১: R → D ← J, D → C
pD = {(1, 1): 0.9, (1, 0): 0.6, (0, 1): 0.5, (0, 0): 0.1}
pC = {1: 0.7, 0: 0.05}
P = lambda v, p: p if v else 1 - p
def joint(r, j, d, c): return P(r, pR) * P(j, pJ) * P(d, pD[(r, j)]) * P(c, pC[d])
print("7.1 P(R,~J,D,C) =", round(joint(1, 0, 1, 1), 4))
W = list(product([1, 0], repeat=4))
pd_ = sum(joint(*w) for w in W if w[2]); pc = sum(joint(*w) for w in W if w[3])
print(" P(D) =", round(pd_, 4), "| P(R|D) =", round(sum(joint(*w) for w in W if w[0] and w[2]) / pd_, 4),
"| P(C) =", round(pc, 4), "| P(R|C) =", round(sum(joint(*w) for w in W if w[0] and w[3]) / pc, 4))
T = np.array([[0.6, 0.3, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]]) # ৭.২ রোদ, মেঘ, বৃষ্টি
x0 = np.array([1.0, 0, 0])
print("7.2 after 1:", x0 @ T, "after 2:", (x0 @ np.linalg.matrix_power(T, 2)).round(4))
T2 = np.array([[0.7, 0.3], [0.2, 0.8]]) # কেনেন, কেনেন না
vals, vecs = np.linalg.eig(T2.T)
pi = np.real(vecs[:, np.argmax(np.real(vals))]); pi = pi / pi.sum()
print(" 2-state stationary:", pi.round(4), "| check pi@T =", (pi @ T2).round(4),
"| B after 2 from B:", (np.array([1.0, 0]) @ T2 @ T2)[0].round(4))
pH = 0.4 # ৭.৩: চাহিদা বেশি
U = {"extra": (50, -20), "normal": (10, 5)} # (বেশি, কম), হাজার টাকা
EU = {a: pH * u[0] + (1 - pH) * u[1] for a, u in U.items()}
perfect = pH * max(u[0] for u in U.values()) + (1 - pH) * max(u[1] for u in U.values())
print("7.3 EU", {a: round(v, 2) for a, v in EU.items()}, "| with perfect info", round(perfect, 2),
"| VPI", round(perfect - max(EU.values()), 2))7.1 P(R,~J,D,C) = 0.0756, তারপর ষোলোটি সারির enumeration থেকে P(D) = 0.398 | P(R|D) = 0.5427 | P(C) = 0.3087 | P(R|C) = 0.5034. 7.2 after 1: [0.6 0.3 0.1] after 2: [0.47 0.33 0.2 ]; দুই অবস্থার chain-এ eigenvector থেকে stationary: [0.4 0.6], আর pi@T-ও একই, অর্থাৎ সত্যিই স্থির; B after 2 from B: 0.55. শেষ লাইন 7.3 EU {'extra': 8.0, 'normal': 7.0} | with perfect info 23.0 | VPI 15.0.
৭.৪(কঠিন) একটি ডেলিভারি হাবের লুকানো অবস্থা ব্যস্ত (B) বা শান্ত (Q). শুরু: B ০.৬, Q ০.৪. Transition: B→B ০.৭, B→Q ০.৩, Q→B ০.৪, Q→Q ০.৬. পর্যবেক্ষণ: P(দেরি | B) = ০.৮, P(দেরি | Q) = ০.২ (বাকিটা সময়মতো)। তিন দিনে দেখা গেল: দেরি, সময়মতো, দেরি। Viterbi দিয়ে সবচেয়ে সম্ভাব্য অবস্থার ধারা আর তার সম্ভাবনা বের করুন। (ঝালিয়ে নিন: পর্ব ৫৩)
t=1 (late) : B 0.6 x 0.8 = 0.48 ; Q 0.4 x 0.2 = 0.08
t=2 (ontime): B max(0.48x0.7, 0.08x0.4) = 0.336 (from B) x 0.2 = 0.0672
Q max(0.48x0.3, 0.08x0.6) = 0.144 (from B) x 0.8 = 0.1152
t=3 (late) : B max(0.0672x0.7, 0.1152x0.4) = max(0.04704, 0.04608)
= 0.04704 (from B) x 0.8 = 0.037632
Q max(0.0672x0.3, 0.1152x0.6) = 0.06912 (from Q) x 0.2 = 0.013824
best end: B (0.03763) -> back: B <- B <- B
path B, B, B ; probability 0.03763
ফাঁদ: প্রতিটি দিনে আলাদাভাবে বড় মানটি বেছে নেওয়া। t = ২-তে Q-এর মান (০.১১৫২) বড়, তবু সেরা পুরো পথ সেখানে B দিয়ে যায়, কারণ t = ৩-এ B-তে পৌঁছানোর হিসাবে B থেকে আসা পথটি সামান্য এগিয়ে (০.০৪৭০৪ বনাম ০.০৪৬০৮)। এজন্যই pointer রেখে শেষ থেকে পেছনে যেতে হয়।
B: 0.6 x 0.8 = 0.48
Q: 0.4 x 0.2 = 0.08
B: 0.48x0.7 = 0.336 -> x0.2 = 0.0672 (from B)
Q: 0.48x0.3 = 0.144 -> x0.8 = 0.1152 (from B)
B: max(0.04704 via B, 0.04608 via Q)
-> 0.04704 x 0.8 = 0.037632 (from B)
Q: max(0.02016 via B, 0.06912 via Q)
-> 0.06912 x 0.2 = 0.013824 (from Q)
end: B 0.037632 > Q 0.013824
t3 B <- t2 B <- t1 B
path B, B, B
- প্রথম দিন। শুরু × দেরির সম্ভাবনা: B ০.৪৮, Q ০.০৮.
- দ্বিতীয় দিন, সময়মতো। দুটির সেরা উৎসই B; সময়মতো ডেলিভারি শান্ত হাবের পক্ষে, তাই এখন Q (০.১১৫২) এগিয়ে।
- তৃতীয় দিন, দেরি। B-তে পৌঁছানোর দুই পথ প্রায় সমান (০.০৪৭০৪ বনাম ০.০৪৬০৮); B থেকে আসা পথ জেতে।
- পেছনে ফেরা। শেষে বড় মান B; pointer ধরে B, B. দ্বিতীয় দিনে একা দেখলে শান্ত এগিয়ে ছিল, তবু পুরো পথে ব্যস্ত।
৭.৫(কঠিন) একটি ছোট MDP: অবস্থা A, B আর শেষ অবস্থা G (মান সবসময় ০), γ = ০.৯. A-তে “go”: ০.৮ সম্ভাবনায় B, ০.২-এ A-তেই থাকা, দুই ক্ষেত্রেই পুরস্কার −১; “wait”: A-তে থাকা, পুরস্কার ০. B-তে “go”: ০.৮-এ G, পুরস্কার +১০; ০.২-এ B-তে, পুরস্কার −১; “wait”: B-তে থাকা, পুরস্কার ০. V0 = ০ থেকে দুটি synchronous sweep করুন; প্রতিটি sweep-এ Q-মান, V আর policy কী? (ঝালিয়ে নিন: পর্ব ৫৪)
Q(s,a) = sum P(s'|s,a) [R + 0.9 V(s')]
sweep 1 (V0 = 0 everywhere):
A: go = 0.8(-1 + 0) + 0.2(-1 + 0) = -1.0 ; wait = 0 -> V1(A) = 0 (wait)
B: go = 0.8(10 + 0) + 0.2(-1 + 0) = 7.8 ; wait = 0 -> V1(B) = 7.8 (go)
sweep 2 (uses V1: A 0, B 7.8):
A: go = 0.8(-1 + 0.9x7.8) + 0.2(-1 + 0) = 0.8 x 6.02 - 0.2 = 4.616
wait = 0 + 0.9 x 0 = 0 -> V2(A) = 4.616 (go)
B: go = 0.8(10 + 0) + 0.2(-1 + 0.9x7.8) = 8 + 1.204 = 9.204
wait = 0 + 0.9 x 7.8 = 7.02 -> V2(B) = 9.204 (go)
Sweep ১-এর পরে A-তে “wait” সেরা দেখায়, কারণ তখনো G-এর পুরস্কারের খবর A পর্যন্ত পৌঁছায়নি; প্রতি sweep-এ মূল্য এক ধাপ পেছনে ছড়ায়। Synchronous মানে sweep ২-এর সব হিসাবে V1-এর মান, নতুন V2(B) নয়। আরও sweep দিলে মানগুলো স্থির বিন্দুর দিকে যায়।
S = ["Busy", "Calm"] # ৭.৪: লুকানো অবস্থা
start = {"Busy": 0.6, "Calm": 0.4}
trans = {"Busy": {"Busy": 0.7, "Calm": 0.3}, "Calm": {"Busy": 0.4, "Calm": 0.6}}
emit = {"Busy": {"late": 0.8, "ontime": 0.2}, "Calm": {"late": 0.2, "ontime": 0.8}}
obs = ["late", "ontime", "late"]
v = [{s: start[s] * emit[s][obs[0]] for s in S}]; back = [{}]
for o in obs[1:]:
row, ptr = {}, {}
for s in S:
prev = max(S, key=lambda p: v[-1][p] * trans[p][s])
row[s] = v[-1][prev] * trans[prev][s] * emit[s][o]; ptr[s] = prev
v.append(row); back.append(ptr)
for t, row in enumerate(v): print(f"7.4 t={t + 1}", {s: round(p, 5) for s, p in row.items()})
last = max(S, key=lambda s: v[-1][s]); path = [last]
for ptr in reversed(back[1:]): path.insert(0, ptr[path[0]])
print(" best path", path, "prob", round(v[-1][last], 5))
gamma, V = 0.9, {"A": 0.0, "B": 0.0, "G": 0.0} # ৭.৫: G শেষ অবস্থা
model = {"A": {"go": [(0.8, "B", -1), (0.2, "A", -1)], "wait": [(1.0, "A", 0)]},
"B": {"go": [(0.8, "G", 10), (0.2, "B", -1)], "wait": [(1.0, "B", 0)]}}
for sweep in (1, 2): # একসাথে (synchronous) হালনাগাদ
Q = {s: {a: sum(p * (r + gamma * V[s2]) for p, s2, r in out) for a, out in acts.items()}
for s, acts in model.items()}
V = {**V, **{s: max(q.values()) for s, q in Q.items()}}
print(f"7.5 sweep {sweep}", {s: {a: round(x, 3) for a, x in q.items()} for s, q in Q.items()},
"V", {s: round(x, 3) for s, x in V.items() if s != "G"})Viterbi-র তিন সারি: t=1 {'Busy': 0.48, 'Calm': 0.08}, t=2 {'Busy': 0.0672, 'Calm': 0.1152}, t=3 {'Busy': 0.03763, 'Calm': 0.01382}, আর best path ['Busy', 'Busy', 'Busy'] prob 0.03763. Value iteration: sweep 1 {'A': {'go': -1.0, 'wait': 0.0}, 'B': {'go': 7.8, 'wait': 0.0}} থেকে V {'A': 0.0, 'B': 7.8}; sweep 2-এ 'A': {'go': 4.616, ...}, 'B': {'go': 9.204, 'wait': 7.02}, V {'A': 4.616, 'B': 9.204}. Code-এ অবস্থার নাম ইংরেজিতে, শুধু পড়ার সুবিধার জন্য।
৮ · ML-এর ভিত্তি — k-NN, normal equations, logistic-এর এক ধাপ আর ridge
ঝালিয়ে নিন: পর্ব ৫৭ · k-Nearest Neighbors, পর্ব ৫৮ · Linear regression (closed form), পর্ব ৫৯ · Logistic regression, পর্ব ৬১ · Overfitting, bias আর variance.
k-NN: সবচেয়ে কাছের k টির ভোট; distance-weighted-এ ওজন ১ ÷ d. Normal equations: (XᵀX)θ = Xᵀy, X-এর প্রথম column-এ ১ (intercept). ২ × ২-এর উল্টো: [[a, b], [c, d]]−১ = (১ ÷ (ad − bc))[[d, −b], [−c, a]]. Logistic: p = σ(wx + b); গড় log loss-এর gradient ∂/∂w = mean((p − y)x), ∂/∂b = mean(p − y). Bias–variance: প্রত্যাশিত test MSE = bias2 + variance + noise. Ridge, এক feature, intercept ছাড়া: w = ∑xy ÷ (∑x2 + λ)।
৮.১(সহজ) প্রশিক্ষণের বিন্দু: শ্রেণি A — (১, ১), (২, ১), (১, ২); শ্রেণি B — (৪, ৪.৫), (৫, ৪), (৪, ৫), (৩, ৩)। নতুন বিন্দু (৩, ২)। Euclidean দূরত্বে (ক) সব দূরত্ব, (খ) k = ১, ৩ আর ৫-এ সাধারণ ভোটের রায়, (গ) k = ৩-এ distance-weighted ভোটের রায় কী? (ঝালিয়ে নিন: পর্ব ৫৭)
(a) (1,1) A sqrt(4+1) = 2.236 (2,1) A sqrt(1+1) = 1.414
(1,2) A sqrt(4+0) = 2.000 (4,4.5) B sqrt(1+6.25) = 2.693
(5,4) B sqrt(4+4) = 2.828 (4,5) B sqrt(1+9) = 3.162 (3,3) B 1.000
sorted: (3,3)B 1.000, (2,1)A 1.414, (1,2)A 2.000, (1,1)A 2.236, (4,4.5)B 2.693
(b) k=1: B ; k=3: B, A, A -> A ; k=5: B, A, A, A, B -> A (3 to 2)
(c) weights 1/d: B 1/1 = 1.000 ; A 1/1.414 + 1/2 = 0.707 + 0.5 = 1.207 -> A
k = ১-এ একটিমাত্র কাছের বিন্দু (৩, ৩) রায় দেয়, যা noise-এর প্রতি সংবেদনশীল; k বাড়ালে রায় স্থির হয়, কিন্তু খুব বড় k-তে বড় শ্রেণি জিতে যায়। দুই শ্রেণিতে বিজোড় k নিলে ভোটে টাই হয় না।
৮.২(মাঝারি) বিজ্ঞাপনের খরচ x (হাজার টাকা) আর বিক্রি y (লাখ টাকা): (১, ২), (২, ৩), (৩, ৫)। y = θ0 + θ1x. (ক) XᵀX আর Xᵀy, (খ) θ, (গ) তিনটির residual, SSE আর R2. (ঝালিয়ে নিন: পর্ব ৫৮)
X = [[1,1],[1,2],[1,3]] , y = [2,3,5]
(a) XtX = [[3, 6], [6, 14]] ; Xty = [2+3+5, 2+6+15] = [10, 23]
(b) det = 3 x 14 - 6 x 6 = 6
inv = (1/6) [[14, -6], [-6, 3]]
theta = (1/6) [14x10 - 6x23, -6x10 + 3x23] = (1/6) [2, 9] = [0.3333, 1.5]
(c) predictions 1.8333, 3.3333, 4.8333
residuals 0.1667, -0.3333, 0.1667 (sum = 0)
SSE = 0.0278 + 0.1111 + 0.0278 = 0.1667
mean y = 10/3 ; SST = 1.7778 + 0.1111 + 2.7778 = 4.6667
R2 = 1 - 0.1667 / 4.6667 = 0.9643
যাচাই: intercept থাকলে residual-এর যোগ শূন্য, আর রেখাটি (x̄, ȳ) = (২, ৩.৩৩৩) বিন্দু দিয়ে যায় (০.৩৩৩ + ১.৫ × ২ = ৩.৩৩৩)। তিনটি বিন্দু থেকে কারণ-সম্পর্ক বলা যায় না, আর R2 এত ছোট ডেটায় সহজেই বড় আসে।
৮.৩(মাঝারি) Logistic regression, এক feature: (x = ২, y = ১), (x = ০, y = ০), (x = ১, y = ১)। শুরু w = ০, b = ০, η = ০.৫. (ক) গড় log loss-এর gradient আর এক ধাপ পরের w, b কত? (খ) তিনটির নতুন p আর গড় loss আগে-পরে কত (ln)? (ঝালিয়ে নিন: পর্ব ৫৯)
(a) p = sigma(0) = 0.5 for all
p - y = -0.5, 0.5, -0.5
dw = mean((p - y) x) = (-0.5x2 + 0.5x0 - 0.5x1) / 3 = -1.5 / 3 = -0.5
db = mean(p - y) = (-0.5 + 0.5 - 0.5) / 3 = -0.1667
w = 0 - 0.5 x (-0.5) = 0.25 ; b = 0 - 0.5 x (-0.1667) = 0.0833
(b) p(x=2) = sigma(0.5833) = 0.6418 ; p(x=0) = sigma(0.0833) = 0.5208
p(x=1) = sigma(0.3333) = 0.5826
loss before = ln 2 = 0.6931
loss after = (-ln 0.6418 - ln(1 - 0.5208) - ln 0.5826) / 3
= (0.4434 + 0.7357 + 0.5403) / 3 = 0.5731
ঋণাত্মক gradient মানে w বাড়ালে loss কমে, তাই বিয়োগ করলে w ধনাত্মক হয়েছে। লক্ষ করুন x = ০-এর বিন্দুর p ০.৫ থেকে ০.৫২-এ উঠেছে, অর্থাৎ ওই একটির loss বেড়েছে; gradient descent গড় loss কমায়, প্রতিটি বিন্দুর নয়।
৮.৪(কঠিন) (ক) একটি model-কে পাঁচটি আলাদা training set-এ শেখানো হলো; একটি বিন্দু x0-এ পাঁচটির অনুমান ৪, ৬, ৫, ৭, ৩. আসল মান f(x0) = ৬, আর noise-এর variance ১. Bias2, variance আর প্রত্যাশিত test MSE কত? (খ) এক feature, intercept ছাড়া, x = (১, ২, ৩), y = (২, ৪, ৭)। Ridge-এ λ = ০, ১ আর ১৪-এ w কত? (ঝালিয়ে নিন: পর্ব ৬১)
(a) mean prediction = (4 + 6 + 5 + 7 + 3) / 5 = 5
bias^2 = (5 - 6)^2 = 1
variance = (1 + 1 + 0 + 4 + 4) / 5 = 2 (spread around 5)
expected test MSE = 1 + 2 + 1 = 4
check: mean (p - 6)^2 = (4 + 0 + 1 + 1 + 9) / 5 = 3 = bias^2 + variance
(b) sum xy = 2 + 8 + 21 = 31 ; sum x^2 = 1 + 4 + 9 = 14
lambda 0 : 31 / 14 = 2.2143 (ordinary least squares)
lambda 1 : 31 / 15 = 2.0667
lambda 14: 31 / 28 = 1.1071
(ক)-তে variance-এ n দিয়ে ভাগ, কারণ এটি পাঁচটি model-এর পুরো সংগ্রহ। Noise কোনো model কমাতে পারে না, তাই ৪-এর নিচে নামা অসম্ভব এই বিন্দুতে। (খ)-তে λ যত বড়, w তত শূন্যের দিকে; λ = ∑x2 হলে w ঠিক অর্ধেক। Ridge সামান্য bias বাড়িয়ে variance কমায়; সঠিক λ বাছতে হয় validation দিয়ে, test দিয়ে নয়।
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LinearRegression, Ridge
X = np.array([[1, 1], [2, 1], [1, 2], [4, 4.5], [5, 4], [4, 5], [3, 3]]) # ৮.১
y = np.array(["A", "A", "A", "B", "B", "B", "B"]); q = [[3, 2]]
print("8.1 dist", np.linalg.norm(X - q[0], axis=1).round(3))
for k in (1, 3, 5):
m = KNeighborsClassifier(n_neighbors=k, algorithm="kd_tree").fit(X, y)
w = KNeighborsClassifier(n_neighbors=k, algorithm="kd_tree", weights="distance").fit(X, y)
print(f" k={k}", m.predict(q)[0], "| distance-weighted", w.predict(q)[0])
x, t = np.array([1.0, 2, 3]), np.array([2.0, 3, 5]) # ৮.২
A = np.c_[np.ones(3), x]
theta = np.linalg.solve(A.T @ A, A.T @ t); lr = LinearRegression().fit(x[:, None], t)
pred = A @ theta; sse = ((t - pred) ** 2).sum()
print("8.2 XtX", (A.T @ A).tolist(), "Xty", (A.T @ t).tolist(), "theta", theta.round(4),
"| sklearn", round(lr.intercept_, 4), lr.coef_.round(4), "| SSE", round(sse, 4),
"R2", round(lr.score(x[:, None], t), 4))
xs, ys = np.array([2.0, 0, 1]), np.array([1, 0, 1]) # ৮.৩
sig = lambda z: 1 / (1 + np.exp(-z))
loss = lambda w, b: -np.mean(ys * np.log(sig(w * xs + b)) + (1 - ys) * np.log(1 - sig(w * xs + b)))
p = sig(0 * xs + 0); dw, db = np.mean((p - ys) * xs), np.mean(p - ys)
w1, b1 = 0 - 0.5 * dw, 0 - 0.5 * db
print("8.3 dw", round(dw, 4), "db", round(db, 4), "-> w", round(w1, 4), "b", round(b1, 4),
"| loss", round(loss(0, 0), 4), "->", round(loss(w1, b1), 4))
xr, yr = np.array([1.0, 2, 3]), np.array([2.0, 4, 7]) # ৮.৪ (খ)
for lam in (0, 1, 14):
print(f"8.4 ridge lambda={lam}", round((xr @ yr) / (xr @ xr + lam), 4), "| sklearn",
Ridge(alpha=lam, fit_intercept=False).fit(xr[:, None], yr).coef_.round(4) if lam else "-")8.1 dist [2.236 1.414 2. 2.693 2.828 3.162 1. ] আর তিন লাইনে k=1 B, k=3 A, k=5 A; distance-weighted-ও একই। algorithm="kd_tree" দেওয়া, কারণ ডিফল্ট পথে browser-এর Python একটি অপ্রাসঙ্গিক সতর্কবার্তা ছাপে। 8.2 XtX [[3.0, 6.0], [6.0, 14.0]] Xty [10.0, 23.0] theta [0.3333 1.5 ], LinearRegression-ও 0.3333 [1.5], SSE 0.1667 R2 0.9643. 8.3 dw -0.5 db -0.1667 -> w 0.25 b 0.0833 | loss 0.6931 -> 0.5731. Ridge-এর তিন লাইন 2.2143, 2.0667, 1.1071, আর Ridge(alpha=λ, fit_intercept=False)-ও একই সংখ্যা দেয়। (ক)-র variance ২ মেলাতে np.var([4, 6, 5, 7, 3]) চালান।
৯ · মূল্যায়ন, clustering, PCA আর TF-IDF
ঝালিয়ে নিন: পর্ব ৬০ · মূল্যায়ন (precision, recall, ROC), পর্ব ৬৫ · Clustering আর PCA, পর্ব ৬৭ · বাংলা লেখার ডেটা (TF-IDF).
Precision = TP ÷ (TP + FP), recall = TP ÷ (TP + FN), F1 = ২PR ÷ (P + R), specificity = TN ÷ (TN + FP). ROC AUC = (ধনাত্মক-ঋণাত্মক জোড়ার মধ্যে ধনাত্মকের score বেশি এমন জোড়া + ½ × সমান জোড়া) ÷ মোট জোড়া। k-means: প্রতিটি বিন্দু কাছের centroid-এ, তারপর centroid = দলের গড়; inertia = দূরত্বের বর্গের যোগ। Explained variance ratio = λi ÷ ∑λ. TF-IDF (scikit-learn-এর ডিফল্ট): idf = ln((১ + n) ÷ (১ + df)) + ১, ওজন = tf × idf, তারপর সারির L2 দৈর্ঘ্য ১.
৯.১(সহজ) ১,০০০টি অর্ডারে প্রতারণা ধরার model: TP ৪০, FN ১০, FP ৬০, TN ৮৯০. (ক) Accuracy, precision, recall, F1 আর specificity কত? (খ) “সব অর্ডার সৎ” বলা model-এর accuracy কত, আর তা কী বলে? (ঝালিয়ে নিন: পর্ব ৬০)
(a) accuracy = (40 + 890) / 1000 = 0.93
precision = 40 / (40 + 60) = 0.40
recall = 40 / (40 + 10) = 0.80
F1 = 2 x 0.4 x 0.8 / (0.4 + 0.8) = 0.64 / 1.2 = 0.5333
specificity = 890 / (890 + 60) = 0.9368
(b) all honest: (890 + 60) / 1000 = 0.95 > 0.93 of the real model
যাচাই: ৪০ + ১০ + ৬০ + ৮৯০ = ১,০০০. (খ) শ্রেণির ভারসাম্যহীনতার ক্লাসিক ফাঁদ: কোনো প্রতারণা না ধরা “model” accuracy-তে জেতে। Precision ০.৪ মানে সতর্ক হওয়া পাঁচটির তিনটিই সৎ ক্রেতা, তাই সতর্কবার্তার পরে মানুষের যাচাই দরকার।
৯.২(মাঝারি) চারটি ফেরত-আসা অর্ডারের (ধনাত্মক) model score: ০.৯, ০.৮, ০.৫৫, ০.৪; পাঁচটি না-ফেরার (ঋণাত্মক): ০.৭, ০.৫৫, ০.৩, ০.২, ০.১. জোড়া গুনে ROC AUC বের করুন। (ঝালিয়ে নিন: পর্ব ৬০)
pairs = 4 x 5 = 20
pos 0.9 : beats all 5 -> 5
pos 0.8 : beats 0.7, 0.55, 0.3, 0.2, 0.1 -> 5
pos 0.55: beats 0.3, 0.2, 0.1 ; ties 0.55 (0.5) ; loses to 0.7 -> 3.5
pos 0.4 : beats 0.3, 0.2, 0.1 ; loses to 0.7, 0.55 -> 3
AUC = (5 + 5 + 3.5 + 3) / 20 = 16.5 / 20 = 0.825
অর্থ: এলোমেলোভাবে একটি ফেরত আর একটি না-ফেরত অর্ডার নিলে ৮২.৫% ক্ষেত্রে model ফেরতটিকে বেশি score দেয়। AUC কোনো threshold বাছে না আর score-এর মাপ (calibration) দেখে না, শুধু ক্রম দেখে। ফাঁদ: সমান score-কে পুরো জয় বা পুরো হার ধরা।
সাধারণ ভুল: metric training ডেটায় মাপা। উপরের সব metric অর্থবহ শুধু তখনই, যখন সংখ্যাগুলো model-এর না-দেখা test বা validation ডেটা থেকে আসে। Training ডেটায় k = ১-এর k-NN-এর accuracy প্রায় সবসময় ১, কারণ প্রতিটি বিন্দুর সবচেয়ে কাছের প্রতিবেশী সে নিজেই (পর্ব ৫৬)।
৯.৩(মাঝারি) ছয়টি বিন্দু: (১, ১), (২, ১), (১, ২), (৫, ৪), (৬, ৫), (৫, ৬)। k = ২, শুরুর centroid c1 = (১, ১), c2 = (২, ১)। (ক) প্রথম assignment আর তখনকার inertia, (খ) নতুন centroid আর একই দলে নতুন inertia, (গ) পরের assignment-এ কোন বিন্দু দল বদলায়? (ঝালিয়ে নিন: পর্ব ৬৫)
(a) squared distances to c1, c2:
(1,1): 0, 1 -> c1 (2,1): 1, 0 -> c2 (1,2): 1, 2 -> c1
(5,4): 25, 18 -> c2 (6,5): 41, 32 -> c2 (5,6): 41, 34 -> c2
inertia = 0 + 0 + 1 + 18 + 32 + 34 = 85
(b) c1 = mean((1,1),(1,2)) = (1, 1.5)
c2 = mean((2,1),(5,4),(6,5),(5,6)) = (18/4, 16/4) = (4.5, 4)
inertia = 0.25 + 0.25 + 15.25 + 0.25 + 3.25 + 4.25 = 23.5
(c) (2,1): to c1 1 + 0.25 = 1.25 ; to c2 6.25 + 9 = 15.25 -> moves to c1
labels: {(1,1),(2,1),(1,2)} and {(5,4),(6,5),(5,6)}
খারাপ শুরু (দুটি centroid পাশাপাশি) এক ধাপেই অনেকটা সেরে উঠেছে; প্রতিটি ধাপে inertia কমে বা সমান থাকে, বাড়ে না। বাস্তবে k-means++ শুরু আর কয়েকবার চালানো (n_init) খারাপ local minimum এড়ায়।
৯.৪(সহজ) (ক) পাঁচটি feature-এর covariance matrix-এর eigenvalue: ৪.৫, ২.০, ১.০, ০.৩, ০.২. প্রতিটি component-এর explained variance ratio, ক্রমযোজিত যোগ, আর ৯০% ধরতে কয়টি component লাগে? (খ) Covariance [[৫, ২], [২, ২]]-এর eigenvalue কত, প্রথম component কত শতাংশ ধরে? (ঝালিয়ে নিন: পর্ব ৬৫)
(a) total = 4.5 + 2.0 + 1.0 + 0.3 + 0.2 = 8.0
ratio : 0.5625, 0.25, 0.125, 0.0375, 0.025
cumulative : 0.5625, 0.8125, 0.9375, 0.975, 1.0
90% needs 3 components (0.8125 < 0.90 <= 0.9375)
(b) trace = 7, det = 10 - 4 = 6 -> l^2 - 7l + 6 = 0 -> l = 6, 1
PC1 = 6 / 7 = 85.7% ; direction (2, 1)/sqrt(5)
২ × ২-এর শর্টকাট: eigenvalue-গুলোর যোগ = trace, গুণফল = determinant. Standardize করা ডেটায় (correlation matrix) eigenvalue-গুলোর যোগ feature-এর সংখ্যার সমান, তাই সেখানে “১-এর বেশি eigenvalue” একটি প্রচলিত হাতের নিয়ম। Scale না করলে বড় এককের feature (যেমন টাকায় দাম) PCA-কে দখল করে নেয়।
৯.৫(মাঝারি) চারটি রিভিউ: d1 “দাম কম দাম ভালো”, d2 “ডেলিভারি ভালো”, d3 “দাম বেশি”, d4 “ডেলিভারি দেরি দেরি”। tf = কাঁচা গণনা, idf = ln((১ + n) ÷ (১ + df)) + ১. (ক) d1-এর তিনটি শব্দের idf আর tf-idf, (খ) L2 normalize করার পরে d1-এ “দাম”-এর ওজন কত? (ঝালিয়ে নিন: পর্ব ৬৭)
n = 4 ; df: dam 2, kom 1, bhalo 2
(a) idf(dam) = ln(5/3) + 1 = 0.5108 + 1 = 1.5108 ; tf 2 -> 3.0217
idf(kom) = ln(5/2) + 1 = 0.9163 + 1 = 1.9163 ; tf 1 -> 1.9163
idf(bhalo) = ln(5/3) + 1 = 1.5108 ; tf 1 -> 1.5108
(b) length = sqrt(3.0217^2 + 1.9163^2 + 1.5108^2)
= sqrt(9.1306 + 3.6722 + 2.2826) = sqrt(15.0854) = 3.8840
dam = 3.0217 / 3.8840 = 0.7780 ; kom = 0.4934 ; bhalo = 0.3890
“কম” একবারই এসেছে, তবু idf বেশি বলে ওজন “ভালো”-র চেয়ে বেশি: যে শব্দ কম রিভিউয়ে থাকে, সে বেশি পার্থক্য করে। যাচাই: ০.৭৭৮2 + ০.৪৯৩৪2 + ০.৩৮৯2 ≈ ১. ফাঁদ: পাঠ্যবইয়ের log(n ÷ df) সূত্র আর scikit-learn-এর smooth সূত্র আলাদা সংখ্যা দেয়; প্রশ্নে কোনটি বলা আছে দেখুন।
import numpy as np
from sklearn.metrics import roc_auc_score
from sklearn.feature_extraction.text import TfidfVectorizer
TP, FN, FP, TN = 40, 10, 60, 890 # ৯.১
P, R = TP / (TP + FP), TP / (TP + FN)
print("9.1 acc", (TP + TN) / 1000, "prec", P, "rec", R, "F1", round(2 * P * R / (P + R), 4),
"spec", round(TN / (TN + FP), 4), "| all-negative acc", (TN + FP) / 1000)
pos, neg = [0.9, 0.8, 0.55, 0.4], [0.7, 0.55, 0.3, 0.2, 0.1] # ৯.২
wins = sum((p > n) + 0.5 * (p == n) for p in pos for n in neg)
print("9.2 pairs", len(pos) * len(neg), "wins", wins, "AUC", wins / 20,
"| sklearn", roc_auc_score([1] * 4 + [0] * 5, pos + neg))
pts = np.array([[1, 1], [2, 1], [1, 2], [5, 4], [6, 5], [5, 6]], dtype=float) # ৯.৩
C = np.array([[1, 1], [2, 1]], dtype=float)
lab = np.argmin(((pts[:, None] - C) ** 2).sum(-1), axis=1)
inertia = lambda c, l: ((pts - c[l]) ** 2).sum()
C2 = np.array([pts[lab == k].mean(0) for k in range(2)])
lab2 = np.argmin(((pts[:, None] - C2) ** 2).sum(-1), axis=1)
print("9.3 labels", lab, "inertia", inertia(C, lab), "-> centroids", C2.tolist(),
"inertia", round(inertia(C2, lab), 4), "| next labels", lab2)
ev = np.array([4.5, 2.0, 1.0, 0.3, 0.2]) # ৯.৪
print("9.4 ratio", (ev / ev.sum()).round(4), "cum", np.cumsum(ev / ev.sum()).round(4),
"| 2x2 eig", np.linalg.eigvalsh(np.array([[5.0, 2], [2, 2]])))
docs = ["দাম কম দাম ভালো", "ডেলিভারি ভালো", "দাম বেশি", "ডেলিভারি দেরি দেরি"] # ৯.৫
vec = TfidfVectorizer(token_pattern=r"[^\s]+")
Xt = vec.fit_transform(docs).toarray(); vocab = vec.get_feature_names_out()
idf = {w: round(float(v), 4) for w, v in zip(vocab, vec.idf_)}
print("9.5 idf", idf)
print(" d1 normalised", {w: round(float(Xt[0][i]), 4) for i, w in enumerate(vocab) if Xt[0][i]})9.1 acc 0.93 prec 0.4 rec 0.8 F1 0.5333 spec 0.9368 | all-negative acc 0.95. 9.2 pairs 20 wins 16.5 AUC 0.825 | sklearn 0.825: হাতে গোনা জোড়া আর roc_auc_score একই। k-means এখানে NumPy দিয়ে হাতে লেখা (browser-এর Python-এ scikit-learn-এর KMeans একটি অপ্রাসঙ্গিক সতর্কবার্তা ছাপে): labels [0 1 0 1 1 1] inertia 85.0 -> centroids [[1.0, 1.5], [4.5, 4.0]] inertia 23.5 | next labels [0 0 0 1 1 1]. 9.4 ratio [0.5625 0.25 ...] cum [0.5625 0.8125 0.9375 0.975 1.] আর 2x2 eig [1. 6.]. TfidfVectorizer-এর idf_: দাম, ভালো, ডেলিভারি 1.5108, কম, বেশি, দেরি 1.9163; d1-এর normalize করা ওজন {'কম': 0.4934, 'দাম': 0.778, 'ভালো': 0.389}. বাংলা শব্দের জন্য token_pattern=r"[^\s]+" দিতে হয়েছে, পর্ব ৬৭-এ যেমন দেখেছেন।
১০ · Neural network আর আধুনিক AI — perceptron, backprop, attention, retrieval, fairness আর drift
ঝালিয়ে নিন: পর্ব ৬৮ · Neural network-এর ধারণা (perceptron, backprop), পর্ব ৬৯ · Embedding আর vector search (recall@k, MRR), পর্ব ৭০ · LLM কীভাবে কাজ করে (attention), পর্ব ৭২ · দায়িত্বশীল AI-এর অভ্যাস (fairness), পর্ব ৭৪ · AI প্রকল্পের জীবনচক্র (PSI).
Perceptron: y(w·x + b) ≤ ০ হলে w ← w + ηyx, b ← b + ηy (y ∈ {+১, −১})। Backprop: শেষ থেকে শুরু পর্যন্ত chain rule; sigmoid স্তরে গুণক h(১ − h). Attention: ওজন = softmax(q·k ÷ √dk), ফল = ওজনসহ value-গুলোর যোগ। Recall@k = প্রথম k-এ প্রাসঙ্গিক ÷ মোট প্রাসঙ্গিক; MRR = প্রথম প্রাসঙ্গিকের ১ ÷ rank-এর গড়। Demographic parity: দলভেদে selection rate; equal opportunity: দলভেদে TPR. PSI = ∑(a − e) ln(a ÷ e).
১০.১(সহজ) Perceptron, শুরু w = (০, ০), b = ০, η = ১. ডেটা ক্রমে: x1 = (২, ১), y = +১; x2 = (−১, −১), y = −১; x3 = (১, −২), y = −১. নিয়ম: y(w·x + b) ≤ ০ হলে হালনাগাদ। দুটি পাসে কোথায় কোথায় হালনাগাদ হয়, শেষ w, b কী? (ঝালিয়ে নিন: পর্ব ৬৮)
pass 1:
x1: 1 x (0 + 0) = 0 <= 0 -> update w = (2, 1), b = 1
x2: -1 x (-2 - 1 + 1) = 2 > 0 -> ok
x3: -1 x (2 - 2 + 1) = -1 <= 0 -> update w = (2,1) - (1,-2) = (1, 3), b = 0
pass 2:
x1: 1 x (2 + 3) = 5 ; x2: -1 x (-1 - 3) = 4 ; x3: -1 x (1 - 6) = 5 -> no update
final w = (1, 3), b = 0 (2 updates; all margins positive: converged)
শুরুতে w = ০ হলে প্রথম বিন্দুর মান ঠিক ০, আর “≤ ০” নিয়মে সেটিও ভুল ধরা হয়; “< ০” লিখলে প্রথম হালনাগাদই হতো না। ডেটা রেখা দিয়ে আলাদা করা যায় বলে perceptron সসীম ধাপে থামে; XOR-এর মতো ডেটায় কখনো থামত না।
১০.২(কঠিন) একটি খুদে network: ইনপুট x → লুকানো h = σ(w1x + b1) → আউটপুট ŷ = w2h + b2, loss L = ½(ŷ − y)2. x = ১, y = ১, w1 = ০.৫, b1 = ০, w2 = ১, b2 = ০, η = ০.৫. (ক) Forward pass-এ h, ŷ, L. (খ) চারটি gradient. (গ) এক ধাপ পরের weight আর নতুন L. (ঝালিয়ে নিন: পর্ব ৬৮)
(a) z = 0.5 ; h = sigma(0.5) = 0.6225 ; y_hat = 0.6225
L = 0.5 x (0.6225 - 1)^2 = 0.5 x 0.1425 = 0.07127
(b) dL/dy_hat = y_hat - y = -0.37754
dL/dw2 = -0.37754 x h = -0.23500 ; dL/db2 = -0.37754
dL/dh = -0.37754 x w2 = -0.37754 ; dh/dz = h(1 - h) = 0.23500
dL/dz = -0.37754 x 0.23500 = -0.08872
dL/dw1 = -0.08872 x x = -0.08872 ; dL/db1 = -0.08872
(c) w2 = 1 + 0.5 x 0.23500 = 1.1175 ; b2 = 0 + 0.5 x 0.37754 = 0.1888
w1 = 0.5 + 0.5 x 0.08872 = 0.5444 ; b1 = 0.0444
new h = sigma(0.5888) = 0.6431 ; y_hat = 1.1175 x 0.6431 + 0.1888 = 0.9074
new L = 0.5 x (0.9074 - 1)^2 = 0.00429
যাচাই: dL/dw1-কে সংখ্যায় (w1-কে ±০.০০০০০১ সরিয়ে) মাপলেও −০.০৮৮৭২ আসে; একে gradient check বলে। লুকানো স্তরের gradient আউটপুটের চেয়ে প্রায় চার গুণ ছোট, কারণ h(১ − h) = ০.২৩৫ দিয়ে গুণ; এভাবেই গভীর sigmoid network-এ gradient ক্ষয়ে যায়।
১০.৩(মাঝারি) তিনটি token-এর key k1 = (১, ০), k2 = (০, ১), k3 = (১, ১), value-ও একই তিনটি vector; dk = ২. Query q = (১, ০)। (ক) Scaled score, softmax ওজন আর আউটপুট vector. (খ) ভবিষ্যৎ ঢাকার causal mask-এ q যদি token ২-এর হয়, কোন key-গুলো দেখা যায়? (ঝালিয়ে নিন: পর্ব ৭০)
(a) q.k = 1, 0, 1 ; / sqrt(2) -> 0.7071, 0, 0.7071
exp: 2.0281, 1.0000, 2.0281 ; sum 5.0562
weights: 0.4011, 0.1978, 0.4011 (sum 1)
output = 0.4011 (1,0) + 0.1978 (0,1) + 0.4011 (1,1) = (0.8022, 0.5989)
(b) token 2 sees keys 1 and 2 only (key 3 is in the future)
√dk দিয়ে ভাগ না করলে score ১, ০, ১ থেকে ওজন ০.৪২২, ০.১৫৫, ০.৪২২ হতো, অর্থাৎ বেশি একপেশে; মাত্রা বড় হলে এই প্রভাব অনেক বাড়ে। আউটপুট কোনো একটি value নয়, তিনটির মিশ্রণ।
১০.৪(সহজ) তিনটি খোঁজ; প্রাসঙ্গিক নথি আর ফল (ক্রমে): Q1 {d2, d5} — d2, d7, d5, d1, d3; Q2 {d4} — d1, d3, d6, d4, d2; Q3 {d1, d6, d8} — d9, d6, d1, d3, d8. প্রতিটির recall@৩, গড় recall@৩, reciprocal rank আর MRR কত? (ঝালিয়ে নিন: পর্ব ৬৯)
recall@3: Q1 {d2, d5} in top 3 -> 2/2 = 1.0
Q2 d4 is 4th -> 0/1 = 0.0
Q3 d6, d1 in top 3 -> 2/3 = 0.6667
mean = (1 + 0 + 0.6667) / 3 = 0.5556
RR : Q1 rank 1 -> 1 ; Q2 rank 4 -> 0.25 ; Q3 rank 2 -> 0.5
MRR = (1 + 0.25 + 0.5) / 3 = 0.5833
দুটি metric দুই প্রশ্নের উত্তর দেয়: recall@k বলে “প্রাসঙ্গিকগুলোর কত ভাগ ওপরে এল”, MRR বলে “প্রথম ভালো ফলটি কত ওপরে”। RAG-এ model শুধু ওপরের কয়েকটি নথি পড়ে, তাই Q2-এর মতো চতুর্থ স্থানের নথি কার্যত হারিয়ে যায়।
১০.৫(মাঝারি) COD সুবিধা অনুমোদনের একটি model, দুই দলে ১০০ জন করে আবেদনকারী। দল ক: ৬০ জন আসলে নির্ভরযোগ্য; model ৫০ জনকে অনুমোদন দেয়, তার ৪৫ জন নির্ভরযোগ্য। দল খ: ৫০ জন নির্ভরযোগ্য; model ৩০ জনকে অনুমোদন দেয়, তার ২৭ জন নির্ভরযোগ্য। (ক) Selection rate, demographic parity-র পার্থক্য আর অনুপাত, চার-পঞ্চমাংশ নিয়মে রায়। (খ) TPR, FPR আর precision দলভেদে। (ঝালিয়ে নিন: পর্ব ৭২)
(a) selection: ka 50/100 = 0.50 ; kha 30/100 = 0.30
difference = 0.20 ; ratio = 0.30 / 0.50 = 0.60 < 0.8 -> flag
(b) TPR : ka 45/60 = 0.75 ; kha 27/50 = 0.54 -> gap 0.21
FPR : ka 5/40 = 0.125 ; kha 3/50 = 0.06
precision: ka 45/50 = 0.90 ; kha 27/30 = 0.90 (equal)
একই model এক সংজ্ঞায় “ন্যায্য” (precision সমান) আর অন্য দুটিতে নয় (selection rate আর TPR আলাদা)। Base rate আলাদা হলে (৬০% বনাম ৫০%) সব সংজ্ঞা একসাথে মেলানো সাধারণত সম্ভব নয়; কোনটি গুরুত্বপূর্ণ, তা প্রসঙ্গ ঠিক করে। দল খ-এর নির্ভরযোগ্য আবেদনকারীদের ৪৬% প্রত্যাখ্যাত, এটিই এখানে সবচেয়ে বড় ক্ষতি। চার-পঞ্চমাংশ একটি প্রাথমিক ইঙ্গিত, আইনি রায় নয়।
১০.৬(সহজ) একটি feature-এর তিন bin-এ reference (প্রশিক্ষণের সময়) অনুপাত ০.২, ০.৫, ০.৩; এই মাসে ০.১, ০.৪, ০.৫. (ক) PSI কত, আর প্রচলিত নিয়মে (০.১-এর কম স্থির, ০.১–০.২৫ নজরে রাখুন, ০.২৫-এর বেশি বড় পরিবর্তন) রায় কী? (খ) কোনো bin-এ এই মাসের অনুপাত ০ হলে কী সমস্যা? (ঝালিয়ে নিন: পর্ব ৭৪)
(a) bin 1: (0.1 - 0.2) ln(0.1/0.2) = (-0.1)(-0.6931) = 0.0693
bin 2: (0.4 - 0.5) ln(0.4/0.5) = (-0.1)(-0.2231) = 0.0223
bin 3: (0.5 - 0.3) ln(0.5/0.3) = (0.2)(0.5108) = 0.1022
PSI = 0.0693 + 0.0223 + 0.1022 = 0.1938 -> "watch" (0.1 to 0.25)
(b) ln(0 / e) = -infinity -> PSI is undefined; replace 0 by a small epsilon
(for example 0.0001) or merge bins
প্রতিটি পদ শূন্য বা ধনাত্মক, কারণ (a − e) আর ln(a ÷ e)-এর চিহ্ন একই; তাই কোনো পদ ঋণাত্মক এলে হিসাব ভুল। সীমাগুলো চর্চা থেকে আসা হাতের নিয়ম; drift ধরা পড়লে প্রথম প্রশ্ন “কেন”, যেমন ঈদের মাসে পরিবর্তন প্রত্যাশিত হতে পারে।
import numpy as np
X, y, w, b = np.array([[2, 1], [-1, -1], [1, -2]]), np.array([1, -1, -1]), np.zeros(2), 0.0 # ১০.১
for ep in (1, 2):
for xi, yi in zip(X, y):
if yi * (w @ xi + b) <= 0: w, b = w + yi * xi, b + yi; print(f"10.1 pass {ep} update -> w {w}, b {b}")
print(" final margins", (y * (X @ w + b)).tolist())
sig = lambda z: 1 / (1 + np.exp(-z)) # ১০.২: x → h=σ(w1·x+b1) → ŷ=w2·h+b2
x, t, w1, b1, w2, b2, eta = 1.0, 1.0, 0.5, 0.0, 1.0, 0.0, 0.5
def fwd(w1, b1, w2, b2): h = sig(w1 * x + b1); return h, w2 * h + b2
h, yh = fwd(w1, b1, w2, b2); L = 0.5 * (yh - t) ** 2
d = yh - t; g = {"w2": d * h, "b2": d, "w1": d * w2 * h * (1 - h) * x, "b1": d * w2 * h * (1 - h)}
num = (0.5 * (fwd(w1 + 1e-6, b1, w2, b2)[1] - t) ** 2 - 0.5 * (fwd(w1 - 1e-6, b1, w2, b2)[1] - t) ** 2) / 2e-6
w1n, b1n, w2n, b2n = w1 - eta * g["w1"], b1 - eta * g["b1"], w2 - eta * g["w2"], b2 - eta * g["b2"]
print("10.2 h", round(h, 4), "y_hat", round(yh, 4), "L", round(L, 5), "| grads", {k: round(float(v), 5) for k, v in g.items()})
print(" numeric dL/dw1", round(num, 5), "| new L", round(0.5 * (fwd(w1n, b1n, w2n, b2n)[1] - t) ** 2, 5))
q, K = np.array([1.0, 0]), np.array([[1.0, 0], [0, 1], [1, 1]]); V = K.copy() # ১০.৩
s = K @ q / np.sqrt(2); a = np.exp(s) / np.exp(s).sum()
print("10.3 scores", s.round(4), "weights", a.round(4), "output", (a @ V).round(4))
ranked = [["d2", "d7", "d5", "d1", "d3"], ["d1", "d3", "d6", "d4", "d2"], ["d9", "d6", "d1", "d3", "d8"]]
rel = [{"d2", "d5"}, {"d4"}, {"d1", "d6", "d8"}] # ১০.৪
rk = lambda r, s, k: len(set(r[:k]) & s) / len(s)
rr = [1 / (next(i for i, d in enumerate(r) if d in s) + 1) for r, s in zip(ranked, rel)]
print("10.4 recall@3", [round(rk(r, s, 3), 4) for r, s in zip(ranked, rel)], "mean",
round(np.mean([rk(r, s, 3) for r, s in zip(ranked, rel)]), 4), "| RR", rr, "MRR", round(np.mean(rr), 4))
grp = {"ka": dict(n=100, good=60, appr=50, tp=45), "kha": dict(n=100, good=50, appr=30, tp=27)}
sr, tpr, fpr = ({g: f(v) for g, v in grp.items()} for f in (lambda v: v["appr"] / v["n"], # ১০.৫
lambda v: v["tp"] / v["good"], lambda v: (v["appr"] - v["tp"]) / (v["n"] - v["good"])))
print("10.5 sel", sr, "ratio", round(sr["kha"] / sr["ka"], 2), "| TPR", tpr, "| FPR", fpr)
e, a_ = np.array([0.2, 0.5, 0.3]), np.array([0.1, 0.4, 0.5]); terms = (a_ - e) * np.log(a_ / e) # ১০.৬
print("10.6 PSI terms", terms.round(4), "PSI", round(terms.sum(), 4))Perceptron-এর দুই হালনাগাদ 10.1 pass 1 update -> w [2. 1.], b 1.0 আর w [1. 3.], b 0.0; পাস ২-এ কোনো লাইন নেই, আর final margins [5.0, 4.0, 5.0] সবই ধনাত্মক। 10.2 h 0.6225 y_hat 0.6225 L 0.07127 | grads {'w2': -0.235, 'b2': -0.37754, 'w1': -0.08872, 'b1': -0.08872}, তারপর numeric dL/dw1 -0.08872 | new L 0.00429. 10.3 scores [0.7071 0. 0.7071] weights [0.4011 0.1978 0.4011] output [0.8022 0.5989]. 10.4 recall@3 [1.0, 0.0, 0.6667] mean 0.5556 | RR [1.0, 0.25, 0.5] MRR 0.5833. 10.5 sel {'ka': 0.5, 'kha': 0.3} ratio 0.6 | TPR {'ka': 0.75, 'kha': 0.54} | FPR {'ka': 0.125, 'kha': 0.06}. শেষে 10.6 PSI terms [0.0693 0.0223 0.1022] PSI 0.1938.
সাধারণ ভুল: log-এর ভিত্তি গুলিয়ে ফেলা। Entropy ১.৫ bit আর ১.০৪ nat একই অনিশ্চয়তা (১.৫ × ln ২ = ১.০৪)। প্রশ্নে log2 না ln, দেখে নিন; scikit-learn-এর log_loss, TF-IDF আর PSI ln ব্যবহার করে, আর scipy-র entropy ডিফল্টে ln, তাই base=2 দিতে হয়।
শেষ মুহূর্তের সূত্র-তালিকা আর সাধারণ ভুল
পরীক্ষার আগে এই এক টেবিলই যথেষ্ট; তৃতীয় কলামের ভুলগুলো মনে রাখাই বেশি কাজের।
| বিষয় | সূত্র | সাধারণ ভুল | পর্ব |
|---|---|---|---|
| Shape, axis | size = shape-এর গুণফল; axis=k-তে যোগে k নম্বর ঘর বাদ | integer index আর slice-এর shape এক ভাবা | ১৩, ১৬ |
| Broadcasting | ডান থেকে মেলান; সমান বা ১ | (n, d) − (n,) লেখা; keepdims ভুলে যাওয়া | ১৫ |
| Memory | nbytes = size × itemsize | view-কে নতুন কপি ভাবা; MB আর MiB গোলানো | ১৯ |
| Groupby | size সব সারি, count NaN বাদে; mean NaN বাদে | NaN-কে ০ বসিয়ে গড় | ২৪ |
| Cosine | u·v ÷ (‖u‖‖v‖); একক vector-এ d2 = ২ − ২cos | Euclidean আর cosine-এর ক্রম এক ভাবা | ৩৩ |
| Gradient descent | x ← x − ηf′(x); x2-এর মতো বক্ররেখায় স্থির যদি η < ২ ÷ বক্রতা | gradient যোগ করা; বড় η-তে দোলা | ৩৪ |
| Bayes | ১০,০০০ জনে গুনুন; P(H | E) = সত্যিকারের ধরা ÷ সব ধরা | base rate বাদ; P(A | B) আর P(B | A) গোলানো | ৩৫, ৫০ |
| Binomial, Poisson | C(n, k)pkqn−k; e−λλk ÷ k! | “অন্তত”-তে পরিপূরক না নেওয়া; সময় বদলালে λ না বদলানো | ৩৬ |
| t-interval | x̄ ± t × s ÷ √n, df = n − ১ | n দিয়ে ভাগ; ছোট n-এ ১.৯৬ | ৩৭ |
| Entropy, KL | −∑p log2p; KL = H(p, q) − H(p) | KL-কে প্রতিসম ভাবা; ln আর log2 | ৩৮ |
| Information gain | H(মূল) − ∑(ni ÷ n)Hi | ওজন ছাড়া গড় | ৩৮ |
| BFS, UCS | BFS কম ধাপ; UCS কম g, goal test expand-এ | BFS-কে কম খরচের ভাবা; G তৈরি হতেই থামা | ৪০ |
| A* | f = g + h; admissible h ≤ আসল খরচ | frontier-এ g হালনাগাদ ভুলে যাওয়া | ৪১ |
| Alpha-beta | α ≥ β হলে ছাঁটাই; মান minimax-এর সমান | ছাঁটাই করা subtree-র মান লেখা | ৪২ |
| AC-3 | domain কমলে প্রতিবেশীর arc ফেরত | arc আবার যোগ না করা | ৪৩ |
| Logic | ২n সারি; →, ↔ সরিয়ে De Morgan, তারপর ছড়ানো | ¬(B ∧ C) = ¬B ∧ ¬C লেখা | ৪৫, ৪৭ |
| Bayesian network | joint = ∏P(x | parents) | সব সারি যোগ না করে একটি সারি নেওয়া | ৫২ |
| Markov, Viterbi | x0Tn; πT = π; v = max × transition × emission | Viterbi-তে প্রতিদিন আলাদা সর্বোচ্চ বাছা | ৫৩ |
| EU, VPI, VI | ∑P × U; VPI = তথ্যসহ − তথ্য ছাড়া; Q = ∑P[R + γV] | synchronous sweep-এ নতুন মান ব্যবহার | ৫৪ |
| Regression | (XᵀX)θ = Xᵀy; ridge w = ∑xy ÷ (∑x2 + λ) | intercept-এর ১-এর column ভুলে যাওয়া | ৫৮, ৬১ |
| Logistic | ∂w = mean((p − y)x) | (y − p) লিখে উল্টো দিকে হাঁটা | ৫৯ |
| Metric, AUC | P, R, F1; AUC = জোড়ায় জয় ÷ জোড়া | ভারসাম্যহীন ডেটায় accuracy; tie-কে ০ বা ১ | ৬০ |
| k-means, PCA | গড় centroid; λi ÷ ∑λ | scale না করে PCA | ৬৫ |
| TF-IDF | tf × (ln((১ + n) ÷ (১ + df)) + ১), তারপর L2 | সূত্রের ধরন না দেখা | ৬৭ |
| Backprop, attention | chain rule; softmax(q·k ÷ √dk) | √dk বাদ; sigmoid-এর h(১ − h) বাদ | ৬৮, ৭০ |
| Retrieval, fairness, PSI | recall@k, MRR; selection rate, TPR; ∑(a − e)ln(a ÷ e) | একটি সংজ্ঞাকেই “ন্যায্যতা” ভাবা; ০-এর bin | ৬৯, ৭২, ৭৪ |
সাধারণ ভুল: সমাধানে নিয়ম না লেখা। Search, chaining আর AC-3-এর উত্তর নিয়মের ওপর নির্ভর করে: প্রতিবেশীর ক্রম, tie, goal test কখন, arc কোন ক্রমে। প্রশ্নে না থাকলে খাতার শুরুতে নিজের নিয়মটি এক লাইনে লিখুন; তাহলে ভিন্ন ক্রমের সঠিক উত্তরও পরীক্ষক মেলাতে পারেন।
২০ মিনিটের মিনি-সেট — ঘড়ি ধরে করুন
আটটি ছোট প্রশ্ন, প্রতিটিতে আড়াই মিনিট। Calculator চলবে, চেকার নয়। শেষ হলে নিচের উত্তর খুলে নম্বর দিন: ৭–৮ ঠিক হলে প্রস্তুত, ৫–৬ হলে সংশ্লিষ্ট ভাগ আবার, ৪-এর কম হলে ভাগ ২ থেকে আবার শুরু করুন।
- Shape (৪, ১, ৩) আর (৫, ১)-এর broadcasting ফল কী?
- (১, ২, ২) আর (২, ১, ২)-এর cosine similarity কত?
- একটি রোগ ১% মানুষের; test অসুস্থের ৯০% ধরে, সুস্থের ১০%-কে ভুলে ধনাত্মক বলে। ধনাত্মক ফলে অসুস্থ হওয়ার সম্ভাবনা কত?
- চারটি সমান সম্ভাব্য ফলের entropy কত bit?
- TP ৩০, FP ১০, FN ২০: precision, recall, F1?
- Score (২, ১, ০)-এর softmax?
- f(w) = (w − ৩)2, w = ০, η = ০.২৫: এক ধাপ পরে w?
- ঘণ্টায় গড়ে ২টি অর্ডার বাতিল হয় (Poisson). এক ঘণ্টায় একটিও না হওয়ার আর অন্তত ২টি হওয়ার সম্ভাবনা?
উত্তরমিনি-সেটের উত্তর আর এক লাইনের কারণ (নিজে করার পরে খুলুন)
1. (4,1,3) with (1,5,1) -> (4, 5, 3)
2. dot 2 + 2 + 4 = 8 ; norms 3 and 3 -> 8 / 9 = 0.8889
3. 0.9 x 0.01 = 0.009 ; 0.1 x 0.99 = 0.099 -> 0.009 / 0.108 = 0.0833
4. log2 4 = 2 bits
5. P = 30/40 = 0.75 ; R = 30/50 = 0.60 ; F1 = 0.9 / 1.35 = 0.6667
6. e^2, e^1, e^0 = 7.389, 2.718, 1 ; sum 11.107 -> 0.6652, 0.2447, 0.0900
7. f'(0) = 2(0 - 3) = -6 ; w = 0 - 0.25 x (-6) = 1.5
8. P(0) = e^-2 = 0.1353 ; P(X >= 2) = 1 - e^-2 (1 + 2) = 0.5940
সবচেয়ে বেশি ভুল হয় ৩ নম্বরে: ৯০% শুনে উত্তর ০.৯ লেখা, অথচ ধনাত্মক ফলের মাত্র ৮% আসলে অসুস্থ। ৭-এ ফাঁদ চিহ্ন; gradient −৬ বিয়োগ করলে w বাড়ে।
AI-এর যুগে — AI-এর হিসাব আর কোড যাচাই
AI সহকারীকে A*-এর trace বা AUC-এর অঙ্ক দিলে পরিষ্কার, আত্মবিশ্বাসী উত্তর আসে। তাতে প্রায়ই নিয়ম চুপচাপ বদলে যায় (goal test কখন, tie কীভাবে), log-এর ভিত্তি গুলিয়ে যায়, বা পুরোনো library-র কোড আসে। ভুলগুলো চেনা:
| AI-এর ভুল | পরিণাম | কীভাবে ধরবেন |
|---|---|---|
পুরোনো API: pandas-এর append, NumPy-র np.float, বা LogisticRegression-এ বাদ পড়া parameter | AttributeError, TypeError বা সতর্কবার্তা | নিজের version-এর মূল docs দেখুন, তারপর চালান |
| না থাকা function বা parameter বানানো | কোড চলেই না, বা চুপচাপ অন্য কিছু করে | help() বা docs-এ নামটি খুঁজুন |
| Scaling বা TF-IDF পুরো ডেটায় fit, তারপর split | Data leakage, ফোলানো score | আগে split, তারপর pipeline-এ fit (পর্ব ৫৬, ৬৪) |
| Training ডেটায় metric জানানো, বা baseline ছাড়া | “৯৫% accuracy” যা সব-না বলা model-ও পায় | Test-এ মাপুন, সরল baseline-এর সাথে তুলনা করুন |
| Search বা Viterbi-তে নিয়ম বদলে ফেলা, বা প্রতিদিন আলাদা সর্বোচ্চ বাছা | দেখতে ঠিক, কিন্তু ভুল trace | নিয়ম আগে লিখে দিন; ছোট চেকার চালান |
সতর্কবার্তা চাপা দিতে warnings.filterwarnings("ignore") | আসল সমস্যা লুকানো | সতর্কবার্তা পড়ুন, কারণ ঠিক করুন |
| বিশ্বাসযোগ্য কিন্তু ভুল পরিসংখ্যান: n − ১ বাদ, ছোট নমুনায় z, KL উল্টো | ভুল interval বা সিদ্ধান্ত | scipy দিয়ে আবার হিসাব; শর্তগুলো জিজ্ঞেস করুন |
AI-কে উত্তরদাতা নয়, যাচাইকারী হিসেবে ব্যবহার করুন। ক্রেতার নাম, ফোন নম্বর বা প্রতিষ্ঠানের গোপন ডেটা prompt-এ দেবেন না; সংখ্যাগুলো নিজের বানানো উদাহরণে বদলে নিন।
যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
প্রতিটি প্রশ্নে খাতায় হিসাব করে তবে উত্তর বাছুন। সব তথ্য প্রশ্নের ভেতরেই আছে।
ক্রমএকটি feature-এর information gain বের করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- মূল দলে প্রতিটি শ্রেণির সংখ্যা গোনা
- মূল দলের entropy বের করা
- Feature-এর মান ধরে দলকে শাখায় ভাগ করে প্রতিটিতে শ্রেণি গোনা
- প্রতিটি শাখার entropy বের করা
- শাখার আকার দিয়ে ওজন দিয়ে entropy-গুলোর গড় নেওয়া
- মূল entropy থেকে সেই গড় বিয়োগ করা
(সহজ) np.zeros((500, 200), dtype=np.float32).nbytes কত?
- ৪,০০,০০০
- ৮,০০,০০০
- ১,০০,০০০
- ২,০০,০০০
(মাঝারি) একটি অবস্থা ১% মানুষের; test অসুস্থের ৯৯% ধরে আর সুস্থের ১%-কে ভুলে ধনাত্মক বলে। ধনাত্মক ফলে অসুস্থ হওয়ার সম্ভাবনা কত?
- ০.৫০
- ০.৯৯
- ০.০১
- ০.০১৯৮
(সহজ) আট পিঠের একটি নিরপেক্ষ ছক্কার entropy কত bit?
- ৮
- ২.০৮
- ৩
- ১
(মাঝারি) A*-এর frontier-এ তিনটি node: P (g = ৪, h = ৬), Q (g = ৬, h = ২), R (g = ৩, h = ৮)। পরের expand কোনটি?
- R
- Q
- P
- তিনটি সমান, বর্ণক্রমে P
(সহজ) ¬(P ∨ Q)-এর সমতুল্য কোনটি?
- ¬P ∨ ¬Q
- P ∨ Q
- ¬P ∧ Q
- ¬P ∧ ¬Q
(মাঝারি) দুই অবস্থার Markov chain: অবস্থা ১ থেকে ১-এ ০.৯, ২-এ ০.১; অবস্থা ২ থেকে ১-এ ০.৫, ২-এ ০.৫. Stationary বণ্টনে অবস্থা ১-এর সম্ভাবনা কত?
- ০.৯০
- ০.৫০
- ০.৮৩৩৩
- ০.১৬৬৭
(মাঝারি) TP ২০, FP ৫, FN ৩০, TN ৯৪৫. Recall কত?
- ০.৪০
- ০.৮০
- ০.৯৬৫
- ০.৫৩৩
(মাঝারি) ধনাত্মক দুটির score ০.৮ আর ০.৪, ঋণাত্মক দুটির ০.৬ আর ০.৩. ROC AUC কত?
- ০.৫০
- ০.৭৫
- ১.০০
- ০.২৫
(সহজ) PCA-তে চারটি eigenvalue ৩, ১, ০.৫, ০.৫. প্রথম দুটি component মিলে কত শতাংশ variance ধরে?
- ৬০%
- ৮০%
- ৭৫%
- ১০০%
(কঠিন) একটি query-র দুই key-এর সাথে dot product ২ আর ০, dk = ৪. Scaled dot-product attention-এ প্রথম key-এর ওজন কত?
- ০.৭৩১১
- ০.৮৮০৮
- ০.৫০০০
- ০.৬২২৫
(মাঝারি) দুই দলের selection rate ০.৬০ আর ০.৪২. চার-পঞ্চমাংশ নিয়মে কী রায়?
- পার্থক্য ০.১৮ < ০.২, তাই ঠিক আছে
- অনুপাত ১.৪৩, তাই ঠিক আছে
- অনুপাত ০.৭০, সতর্কতা
- TPR ছাড়া বলা যায় না
(সহজ) তিনটি খোঁজে প্রথম প্রাসঙ্গিক ফল এসেছে ১, ৩ আর ২ নম্বরে। MRR কত?
- ২.০০
- ০.৫০
- ১.০০
- ০.৬১১১
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- নিয়ম আগে, হিসাব পরে: প্রতিবেশীর ক্রম, tie, goal test কখন, log-এর ভিত্তি, n না n − ১. অর্ধেক মতভেদ এখানেই।
- গুনে দেখুন, অনুভবে নয়: Bayes-এ ১০,০০০ জন, AUC-তে জোড়া, Viterbi-তে ছক। সংখ্যা ছোট রাখলে হাতেই হয়।
- যাচাইয়ের এক লাইন: সম্ভাবনার যোগ ১, residual-এর যোগ ০, A*-এর খরচ UCS-এর সমান, alpha-beta-র মান minimax-এর সমান।
- একটি সংখ্যা পুরো গল্প নয়: accuracy-র পাশে precision ও recall, precision-এর পাশে দলভেদে TPR, PSI-এর পাশে “কেন বদলাল”।
- চেকার দিয়ে মেলান: হাতে করে তারপর কোড; কোড আগে চালালে ভুল ধাপটি শেখা হয় না।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৭৬ · MCQ প্রশ্নব্যাংক — AI-এর ভিত্তি আর Python for AIপরবর্তী পর্বসব মডিউল থেকে ২৬৯টি MCQ, প্রতিটি option-এর ব্যাখ্যাসহ।
- AI-এর ভিত্তি আর Python for AI · কোর্স হোম৭৯টি পর্বপরের পর্ব ৭৬, MCQ প্রশ্নব্যাংক, আর পুরো রোডম্যাপ এখান থেকে।
- পর্ব ৪১ · Heuristic আর A*আবার পড়ুনAdmissible আর consistent heuristic, A*-এর trace আর তুলনা।
- পর্ব ৫০ · Bayes-এর উপপাদ্যআবার পড়ুনNatural frequency, odds আর ধারাবাহিক হালনাগাদ।
- পর্ব ৬০ · মূল্যায়নআবার পড়ুনPrecision, recall, F1, ROC আর PR curve, threshold-এর খরচ।
- পর্ব ৬৮ · Neural network-এর ধারণাআবার পড়ুনPerceptron থেকে ছোট network, NumPy-তে backprop.
- DSA · Trace আর complexity অনুশীলনপাশের ট্র্যাকGraph traversal আর algorithm-এর হাতে-করা trace.
- সাইবার নিরাপত্তা · Numerical অনুশীলনপাশের ট্র্যাকEntropy, সম্ভাবনা আর ঝুঁকির অঙ্ক।
- DBMS ও SQL · আউটপুট অনুশীলনপাশের ট্র্যাকGROUP BY আর aggregation-এর ফল আগেই বলা।