Convexity — কেন কিছু loss সহজ আর কিছু কঠিন

AI-এর ভিত্তি কোর্সের পর্ব ৩৪-এ gradient descent দেখেছেন, আর শুনেছেন যে সে local minimum বা saddle-এ আটকে যেতে পারে; পর্ব ৪৪-এ সেই আটকে যাওয়া এড়াতে simulated annealing-এর মতো কৌশল এসেছিল। এই পর্বের প্রশ্ন উল্টো দিক থেকে: কোন সমস্যায় আটকে যাওয়ার ভয়ই নেই, আর সেটি আগে থেকে কীভাবে জানবেন? উত্তরের নাম convexity. চালানো যায় এমন চারটি ব্লক পাতাতেই চলে (ব্রাউজারের Python আর NumPy); প্রথমবার প্যাকেজ নামতে কয়েক সেকেন্ড লাগে।

১ · কেন convexity — একটি বাটি বনাম পাহাড়ি এলাকা

ML-এ “মাঠ” হলো loss L(w), আর “পায়ের ঢাল” হলো gradient. প্রায় সব optimizer শুধু স্থানীয় তথ্য দেখে: এখনকার মান, ঢাল, বড়জোর বাঁক। তাই একটি মৌলিক প্রশ্ন ওঠে: স্থানীয় তথ্য থেকে পাওয়া উত্তর কি সারা মাঠের সেরা উত্তর? Local minimum মানে আশেপাশের সবার চেয়ে নিচু বিন্দু; global minimum মানে সারা মাঠের সবচেয়ে নিচু। Convex function-এ এই দুটি সবসময় এক, আর এজন্যই convex সমস্যাকে “সহজ” বলা হয়: optimizer যেখানে থামে, সেটিই উত্তর, আর সেটি যাচাইও করা যায়।

সহজ মানে কিন্তু সস্তা নয়। কোটি সারির logistic regression convex, তবু চালাতে সময় লাগে; আর গতি নির্ভর করে বাটিটি কতটা সরু বা চ্যাপ্টা তার ওপর (অংশ ৭)। আবার কঠিন মানে অসম্ভবও নয়: neural network-এর loss non-convex, তবু সেগুলো প্রতিদিন train হয়। এই পর্ব দুই জগতের সীমারেখা স্পষ্ট করে, আর পরের পাঁচটি পর্বের ভিত্তি গড়ে: পর্ব ১৩ (Gradient descent-এর পরিবার — batch, SGD, mini-batch আর learning-rate schedule) আর পর্ব ১৪ (Momentum, RMSProp আর Adam — derive করে আর তুলনা করে) convex বাটিতে গতির হিসাব দেবে, পর্ব ১৫ (Second-order পদ্ধতি — Newton, L-BFGS আর line search) বাঁক ব্যবহার করবে, পর্ব ১৬ (Constraint-সহ optimization — Lagrange multiplier আর KKT) convex set-এর ওপর কাজ করবে, আর পর্ব ১৭ (Regularization-এর তত্ত্ব — L1/L2-এর জ্যামিতি, MAP আর early stopping) এখানকার strong convexity-কে কাজে লাগাবে।

২ · Convex set আর convex function — সংজ্ঞা আর ছবি

Convex set: একটি বিন্দুর সমষ্টি C-কে convex set বলে, যদি C-এর যেকোনো দুটি বিন্দু a, b নিলে তাদের যোগ করা সরলরেখার প্রতিটি বিন্দুও C-এর ভেতরে থাকে। সরলরেখার বিন্দুগুলো লেখা হয় t·a + (1 − t)·b আকারে, যেখানে t হলো ০ থেকে ১-এর মধ্যে একটি সংখ্যা; t = ১-এ a, t = ০-এ b, t = ০.৫-এ ঠিক মাঝখান। এমন ওজনের যোগফলকে বলে convex combination. উদাহরণ: পুরো ℝⁿ, একটি বল ‖w‖ ≤ r, একটি half-space aᵀw ≤ b, আর কয়েকটি convex set-এর ছেদ (যেমন বাজেটের কয়েকটি সীমা একসঙ্গে)। Non-convex উদাহরণ: একটি বলয় বা অর্ধচন্দ্রের আকার, যেখানে দুই প্রান্ত যোগ করা রেখা বাইরে দিয়ে যায়।

Convex function: f-কে convex বলে, যদি তার domain একটি convex set হয় আর সব a, b এবং সব t ∈ [০, ১]-এ:

f(t·a + (1 − t)·b) ≤ t·f(a) + (1 − t)·f(b)

বাঁ দিকটি দুই বিন্দুর মাঝের কোনো জায়গায় f-এর আসল মান; ডান দিকটি (a, f(a)) আর (b, f(b)) যোগ করা জ্যার ওপর সেই জায়গার উচ্চতা। অর্থাৎ জ্যা কখনো লেখচিত্রের নিচে নামে না। অসমতা উল্টো হলে (জ্যা সবসময় নিচে) function-টিকে বলে concave, যেমন log বা √. আর a ≠ b আর ০ < t < ১-এ অসমতা কঠোর (<) হলে বলে strictly convex. আরেকটি সমান সংজ্ঞা: f convex হয় ঠিক তখনই, যখন তার epigraph, অর্থাৎ লেখচিত্রের ওপরের পুরো এলাকা {(w, s) : s ≥ f(w)}, একটি convex set. এই সেতুটিই set আর function-এর দুই সংজ্ঞাকে জোড়ে।

নিচের stepper সংজ্ঞাটি দুটি function-এ হাতে চালায়। লক্ষ করুন, convex হওয়ার দাবি “সব a, b, t”-এর ওপর, আর ভাঙার জন্য একটি উদাহরণই যথেষ্ট।

৩ · স্পর্শক নিচে আর Hessian PSD — প্রথম ও দ্বিতীয় ক্রমের শর্ত

জ্যা-পরীক্ষা সংজ্ঞা, কিন্তু অসীম সংখ্যক a, b, t-এ যাচাই করা অসম্ভব। f differentiable হলে দুটি সমান আর বেশি কাজের শর্ত আছে।

Hessian PSD কীভাবে পরীক্ষা করবেন (eigenvalue, leading minor, Cholesky) তা পর্ব ১০-এ, আর least squares-এর 2XᵀX ও logistic-এর XᵀSX Hessian derive করা হয়েছে পর্ব ১১-এ। এখানে নতুন কথাটি শব্দ “প্রতিটি x-এ”। পর্ব ১০-এর পরীক্ষা একটি বিন্দুর আশেপাশের আকার বলে; convexity একটি সার্বিক দাবি। Quadratic function-এ Hessian সব জায়গায় একই, তাই একবারের পরীক্ষাই যথেষ্ট; কিন্তু logistic বা neural network-এ Hessian বিন্দুভেদে বদলায়। Logistic-এর ক্ষেত্রে XᵀSX সব w-এ PSD, তাই প্রমাণ হয়ে যায়। Neural network-এ কিছু বিন্দুতে Hessian-এর ঋণাত্মক eigenvalue থাকে, তাই একটি বিন্দুতে “এখানে বাটির মতো” দেখে সারা loss-কে convex বলা যায় না।

নিচের ব্লক পাঁচটি function-কে ছবিতে দেখায়: ওপরে এক চলকে দুটি স্পর্শক, নিচে দুই চলকে contour (সমান মানের রেখা)। কোনো স্পর্শক লেখচিত্রের কতটা ওপরে ওঠে, তার সবচেয়ে বড় মাপও ছাপা হয়।

import numpy as np
import matplotlib.pyplot as plt

rng = np.random.default_rng(42)
X = rng.normal(size=(40, 2))
y = (X @ [1.5, -1.0] + rng.normal(0, 0.8, 40) > 0).astype(float)

f_cvx = lambda w: np.logaddexp(0, -w) + 0.1 * w**2          # 1-D log loss + ছোট L2
d_cvx = lambda w: -1 / (1 + np.exp(w)) + 0.2 * w
f_ncv = lambda w: (w**2 - 1)**2 + 0.3 * w                   # দুটি খাদ
d_ncv = lambda w: 4 * w * (w**2 - 1) + 0.3

w = np.linspace(-2, 2, 200)
fig, ax = plt.subplots(2, 2, figsize=(9, 7))
for a, f, d, x0s, name in [(ax[0, 0], f_cvx, d_cvx, [-1.0, 1.2], "convex: log loss + L2"),
                           (ax[0, 1], f_ncv, d_ncv, [0.0, 1.2], "non-convex: double well")]:
    a.plot(w, f(w), "k", lw=2)
    for x0 in x0s:
        a.plot(w, f(x0) + d(x0) * (w - x0), "--", label=f"tangent at w={x0}")
        print(f"{name:24} x0={x0:4}: min(f - tangent) = {np.min(f(w) - f(x0) - d(x0)*(w - x0)):7.3f}")
    a.set_ylim(-1.5, 4); a.set_title(name); a.set_xlabel("w"); a.legend(fontsize=8)

g = np.linspace(-2.5, 2.5, 120)
W1, W2 = np.meshgrid(g, g)
Z = X @ np.stack([W1.ravel(), W2.ravel()])
L_log = np.mean(np.logaddexp(0, Z) - y[:, None] * Z, axis=0).reshape(W1.shape) + 0.05 * (W1**2 + W2**2)
L_qrt = (W1**2 - 1)**2 + W2**2
for a, L, name in [(ax[1, 0], L_log, "log loss + L2, 40 orders"), (ax[1, 1], L_qrt, "(w1^2-1)^2 + w2^2")]:
    a.contour(W1, W2, L, levels=15, cmap="viridis")
    i = np.unravel_index(np.argmin(L), L.shape)
    a.plot(W1[i], W2[i], "r*", ms=14)
    a.set_title(name); a.set_xlabel("w1"); a.set_ylabel("w2")
ax[1, 1].plot([-1, 1], [0, 0], "r*", ms=14)
fig.subplots_adjust(hspace=0.35, wspace=0.25)
plt.show()

convex: log loss + L2    x0=-1.0: min(f - tangent) =   0.000
convex: log loss + L2    x0= 1.2: min(f - tangent) =   0.000
non-convex: double well  x0= 0.0: min(f - tangent) =  -1.000
non-convex: double well  x0= 1.2: min(f - tangent) =   0.000

৪ · কেন convex সমস্যায় খারাপ local minimum নেই

অংশ ৩-এর স্পর্শক-যুক্তি দেখিয়েছে, ঢাল শূন্যের বিন্দু global minimum. কিন্তু hinge বা lasso-র মতো ভাঁজওয়ালা loss-এ ঢাল সব জায়গায় নেই। তাই একটি আরও সাধারণ যুক্তি দরকার, যা শুধু জ্যার সংজ্ঞা ব্যবহার করে। এটি পরীক্ষা আর ইন্টারভিউতে প্রায়ই প্রমাণ করতে বলা হয়।

একই যুক্তি থেকে আরও দুটি দরকারি ফল আসে। প্রথম: convex f-এর সব minimizer মিলে একটি convex set. দুটি সর্বনিম্ন বিন্দু থাকলে তাদের মাঝের পুরো রেখাও সর্বনিম্ন; সর্বনিম্ন “ছড়ানো” থাকতে পারে (যেমন কলাম নির্ভরশীল হলে least squares-এর অসংখ্য সমাধান), কিন্তু কখনো আলাদা আলাদা দ্বীপে নয়। দ্বিতীয়: strictly convex f-এর সর্বনিম্ন বিন্দু বড়জোর একটি। “বড়জোর” কথাটি জরুরি: e^w strictly convex, কিন্তু তার কোনো সর্বনিম্ন বিন্দু নেই, শুধু w → −∞-এ মান ০-এর দিকে যায়। Separable ডেটার logistic regression-এ ঠিক এটিই ঘটে (প্রশ্ন ০৩)।

এবার এই তত্ত্ব সংখ্যায়। নিচের ব্লক gradient descent ২০টি এলোমেলো শুরু থেকে চালায়, দুটি function-এ: convex log loss (সঙ্গে L2, λ = ০.১), আর f(w) = (w₁² − 1)² + (w₂² − 1)² + 0.3w₁ + 0.2w₂, যার চারটি খাদ, প্রতিটির গভীরতা আলাদা। শেষ বিন্দুগুলো তিন দশমিকে গোল করে আলাদা কয়টি, তা গোনা হয়।

import numpy as np

rng = np.random.default_rng(42)
X = rng.normal(size=(40, 2))                  # একই কাল্পনিক বাজারঘর ডেটা
y = (X @ [1.5, -1.0] + rng.normal(0, 0.8, 40) > 0).astype(float)
lam = 0.1

def loss_cvx(w):                               # log loss + (lam/2)|w|^2: convex
    z = X @ w
    return np.mean(np.logaddexp(0, z) - y * z) + lam / 2 * w @ w
def grad_cvx(w):
    p = 1 / (1 + np.exp(-(X @ w)))
    return X.T @ (p - y) / len(y) + lam * w

loss_ncv = lambda w: (w[0]**2 - 1)**2 + (w[1]**2 - 1)**2 + 0.3*w[0] + 0.2*w[1]
grad_ncv = lambda w: np.array([4*w[0]*(w[0]**2 - 1) + 0.3, 4*w[1]*(w[1]**2 - 1) + 0.2])

def run(loss, grad, eta, steps=400, starts=20):
    ends = []
    for w in rng.uniform(-2, 2, (starts, 2)):
        for _ in range(steps):
            w = w - eta * grad(w)
        ends.append(np.round(w, 3))
    uniq, count = np.unique(np.array(ends), axis=0, return_counts=True)
    print(f"{len(uniq)} distinct endpoint(s) from {starts} starts")
    for u, c in zip(uniq, count):
        print(f"   w = {u}   loss = {loss(u):.4f}   reached {c:2d} times")

print("convex log loss + L2:");  run(loss_cvx, grad_cvx, eta=1.0)
print("non-convex 4-well   :");  run(loss_ncv, grad_ncv, eta=0.05)

convex log loss + L2:
1 distinct endpoint(s) from 20 starts
   w = [ 1.004 -0.606]   loss = 0.5534   reached 20 times
non-convex 4-well   :
4 distinct endpoint(s) from 20 starts
   w = [-1.036 -1.024]   loss = -0.5079   reached  5 times
   w = [-1.036  0.974]   loss = -0.1080   reached  5 times
   w = [ 0.96  -1.024]   loss = 0.0917   reached  4 times
   w = [0.96  0.974]   loss = 0.4916   reached  6 times

৫ · ML-এর কোন loss convex, কোনটি নয়

প্রথমে একটি সূক্ষ্ম কিন্তু জরুরি কথা: convexity সবসময় “কোন চলকের সাপেক্ষে” প্রশ্ন। ML-এ আমরা parameter w বদলাই, ডেটা স্থির; তাই প্রশ্ন হলো L(w) w-এ convex কি না। Squared error (y − ŷ)² অনুমান ŷ-এ convex; linear model-এ ŷ = xᵀw হলে w-এও convex থাকে। কিন্তু neural network-এ ŷ হলো w-এর একটি জটিল, বহুস্তর function, তাই একই squared error w-এ non-convex হয়ে যায়। Loss-এর সূত্র একই, model বদলালে উত্তর বদলায়। AI-এর ভিত্তি কোর্সের পর্ব ৫৯-এ log loss আর পর্ব ০২-এ ছয়টি loss-এর আকার দেখেছেন; এবার তাদের parameter-এর সাপেক্ষে শ্রেণিবিন্যাস।

Non-convexity-র একটি সাধারণ উৎস প্রতিসাম্য। k-means-এ দুটি কেন্দ্র (c₁, c₂) = (−১.৫, ১.৫) একটি সমাধান হলে (১.৫, −১.৫)-ও একই loss দেয়, কারণ কোন কেন্দ্রের নাম “১” তাতে কিছু আসে যায় না। কিন্তু তাদের মাঝখান (০, ০) মানে দুটি কেন্দ্রই এক জায়গায়, যা অনেক খারাপ। দুটি সমান ভালো বিন্দুর গড় খারাপ: জ্যার সংজ্ঞার সরাসরি লঙ্ঘন। Neural network-এ hidden neuron-গুলোর ক্রম অদলবদল, আর mixture model-এ component-এর লেবেল অদলবদল একই কাজ করে।

এখন অংশ ২ আর ৩-এর তিনটি সংজ্ঞাকে একটি ছোট সংখ্যাগত convexity-পরীক্ষকে পরিণত করা যাক। দুটি পরীক্ষা: (১) ২০০০টি এলোমেলো জ্যা, বাক্স [−৩, ৩]²-এর ভেতরে; কতবার জ্যার নিচে লেখচিত্র নামে নয়, ওপরে ওঠে, আর সবচেয়ে বড় লঙ্ঘন কত। (২) ১১ × ১১ grid-এ finite difference দিয়ে Hessian বানিয়ে তার সবচেয়ে ছোট eigenvalue. পাঁচটি function: squared loss, log loss আর hinge (বাজারঘরের ৪০টি কাল্পনিক অর্ডারে, দুটি ওজন), quartic (w₁² − 1)² + w₂², আর ৩০টি এক-মাত্রার মানে দুটি কেন্দ্রের k-means objective.

import numpy as np

rng = np.random.default_rng(42)
X = rng.normal(size=(40, 2))                 # কাল্পনিক বাজারঘর: ৪০টি অর্ডার, ২টি feature
y = (X @ [1.5, -1.0] + rng.normal(0, 0.8, 40) > 0).astype(float)   # ফেরত হয়েছে কি না
pts = np.r_[rng.normal(-1.5, 0.5, 15), rng.normal(1.5, 0.5, 15)]  # k-means: ১-D ৩০টি মান

losses = {
    "squared":  lambda w: np.mean((X @ w - y) ** 2),
    "log loss": lambda w: np.mean(np.logaddexp(0, X @ w) - y * (X @ w)),
    "hinge":    lambda w: np.mean(np.maximum(0, 1 - (2*y - 1) * (X @ w))),
    "quartic":  lambda w: (w[0]**2 - 1)**2 + w[1]**2,
    "k-means":  lambda c: np.mean(np.min((pts[:, None] - c) ** 2, axis=1)),
}

def chord_test(f, n=2000, box=3.0):            # সংজ্ঞা: f(ta+(1-t)b) <= t f(a)+(1-t) f(b)?
    a, b = rng.uniform(-box, box, (2, n, 2))
    t = rng.uniform(0, 1, n)
    gap = [f(ti*ai + (1-ti)*bi) - ti*f(ai) - (1-ti)*f(bi) for ai, bi, ti in zip(a, b, t)]
    return np.sum(np.array(gap) > 1e-9), max(gap)

def hessian_test(f, h=1e-3):                   # ১১ × ১১ grid-এ finite-difference Hessian
    E, worst = np.eye(2) * h, np.inf
    for u in np.linspace(-2.5, 2.5, 11):
        for v in np.linspace(-2.5, 2.5, 11):
            p = np.array([u, v])
            H = [[(f(p+E[i]+E[j]) - f(p+E[i]-E[j]) - f(p-E[i]+E[j]) + f(p-E[i]-E[j]))
                  / (4*h*h) for j in range(2)] for i in range(2)]
            worst = min(worst, np.linalg.eigvalsh(np.array(H)).min())
    return worst

print("loss      chord fails  worst gap   min Hessian eig")
for name, f in losses.items():
    bad, gap = chord_test(f)
    print(f"{name:9} {bad:5d}/2000  {gap:9.4f}   {hessian_test(f):10.4f}")

loss      chord fails  worst gap   min Hessian eig
squared       0/2000    -0.0001       0.8638
log loss      0/2000    -0.0000       0.0194
hinge         0/2000     0.0000      -0.0000
quartic      70/2000     0.7612      -4.0000
k-means     526/2000     2.4028   -5071.2636

৬ · Convexity রক্ষা করে যে অপারেশন — ছোট টুকরো থেকে প্রমাণ

বাস্তবে কেউ জ্যা বা Hessian দিয়ে প্রতিটি loss-এর convexity প্রমাণ করে না। বরং কয়েকটি পরিচিত convex টুকরো নিয়ে, convexity রক্ষা করে এমন নিয়মে জোড়া লাগানো হয়। Boyd ও Vandenberghe-এর Convex Optimization (২০০৪) বইয়ের অধ্যায় ৩ এই নিয়মগুলোর মানসম্মত তালিকা দেয়:

সতর্ক থাকুন: দুটি convex function-এর গুণফল বা সর্বনিম্ন সাধারণত convex নয়। k-means-এর min, আর neural network-এর ওজনের গুণ (W₂·ReLU(W₁x)) ঠিক এই দুই জায়গায় convexity হারায়। নিচের stepper এই নিয়মে L2-সহ logistic loss-এর convexity ধাপে ধাপে প্রমাণ করে, তারপর composition-এর ফাঁদটি দেখায়।

৭ · Strong convexity, smoothness আর condition number κ

Convexity বলে “আটকে যাবেন না”, কিন্তু বলে না “কত দ্রুত পৌঁছাবেন”। গতির হিসাবের জন্য দুটি সংখ্যাগত মাপ লাগে, বাটির সবচেয়ে চ্যাপ্টা দিক আর সবচেয়ে খাড়া দিক।

এদের মানে বাটির আকারে ভাবুন। κ = ১ মানে গোল বাটি: সব দিকে সমান খাড়া, gradient সোজা তলার দিকে দেখায়। κ = ১০০০ মানে একটি লম্বা সরু নালার মতো উপত্যকা: আড়াআড়ি দিকে খুব খাড়া, লম্বালম্বি দিকে প্রায় সমতল। Gradient descent-এর ধাপ η খাড়া দিকের কারণে ছোট রাখতে হয় (পর্ব ১৩ দেখাবে, quadratic-এ η < 2/L না হলে ধাপ লাফিয়ে বাইরে যায়), কিন্তু সেই ছোট ধাপে চ্যাপ্টা দিকে এগোতে বহু সময় লাগে। মোটা দাগে, μ-strongly convex আর L-smooth f-এ η = 1/L দিয়ে gradient descent প্রতি ধাপে f(w) − f* -এর ব্যবধানকে অন্তত (1 − μ/L) গুণে কমায়; তাই নির্দিষ্ট নির্ভুলতায় পৌঁছাতে মোটামুটি κ-এর অনুপাতে ধাপ লাগে। পুরো প্রমাণ, zig-zag পথের ছবি আর learning-rate-এর পছন্দ পর্ব ১৩-এর বিষয়।

Strong convexity কোথা থেকে আসে? Least squares-এ μ হলো XᵀX/n-এর সবচেয়ে ছোট eigenvalue, যা কলাম প্রায় নির্ভরশীল হলে শূন্যের কাছে। Ridge বা L2 শাস্তি সরাসরি μ-তে λ যোগ করে। আর শুধু log loss (শাস্তি ছাড়া) strongly convex নয়: w বড় হলে p(1 − p) শূন্যের দিকে যায় (অংশ ৫-এর পরীক্ষকে ০.০১৯৪), আর separable ডেটায় সর্বনিম্ন বিন্দুই নেই। L2 যোগ করলেই সমস্যাটি সুসংজ্ঞায়িত হয়; scikit-learn-এর LogisticRegression default-এ L2 শাস্তি (C = 1.0) রাখে, যার একটি কারণ এটি। কোন সংখ্যা দিয়ে μ আর L মাপবেন, আর feature-এর একক κ-কে কতটা বদলায়, তা অংশ ৮-এর শেষের ব্লক একটি কাল্পনিক regression-এ দেখায়।

৮ · Jensen-এর অসমতা — গড়ের function বনাম function-এর গড়

জ্যার সংজ্ঞায় দুটি বিন্দু আর দুটি ওজন t ও 1 − t. বিন্দু বেশি হলে, বা ওজনগুলো একটি সম্ভাবনা বণ্টন হলে, একই কথার নাম Jensen-এর অসমতা; ডেনমার্কের গণিতবিদ Johan Jensen ১৯০৬ সালে এটি সাধারণ রূপে প্রকাশ করেন। convex f আর যেকোনো random variable X-এর জন্য (প্রত্যাশিত মান থাকলে):

f(E[X]) ≤ E[f(X)], আর concave f-এ উল্টো: E[log X] ≤ log E[X]

ML-এ Jensen অন্তত তিন জায়গায় সরাসরি কাজ করে। (১) Ensemble: loss অনুমানে convex হলে (squared error, log loss), কয়েকটি model-এর অনুমানের গড়ের loss তাদের নিজ নিজ loss-এর গড়ের চেয়ে বেশি হয় না। এটি পর্ব ৩৭ (Stacking, blending আর voting — ensemble কখন সত্যিই সাহায্য করে)-এর একটি তাত্ত্বিক ভিত্তি। (২) KL divergence ≥ ০: −log concave নয়, convex; Jensen দিয়ে KL(p‖q) = E_p[−log(q/p)] ≥ −log E_p[q/p] = −log ১ = ০. AI-এর ভিত্তি কোর্সের পর্ব ৩৮-এ ফলটি দেখেছেন, এখানে তার প্রমাণ। (৩) নিচের সীমা: EM algorithm আর variational inference-এ log-likelihood-এর একটি নিচের সীমা Jensen দিয়েই বানানো হয়; এটি পর্ব ৩৯ (Gaussian mixture আর EM algorithm — নরম clustering) আর পর্ব ৪৮ (Variational inference-এর ধারণা — ELBO আর approximation)-এ আসবে।

নিচের ব্লক দুটি কাজ করে। প্রথমে ২০০ জন কাল্পনিক গ্রাহকের কাঁচা feature (অর্ডারের সংখ্যা আর ঝুড়ির আকার, শত টাকায়) দিয়ে least squares loss f(w) = ‖Xw − y‖²/(2n)-এর Hessian XᵀX/n থেকে μ, L আর κ বের করে, তারপর ১০০০টি এলোমেলো বিন্দু-জোড়ায় অংশ ৭-এর দুই সীমা মিলিয়ে দেখে, আর standardize করার পর κ কত হয় তা ছাপে। তারপর ১০,০০০টি কাল্পনিক অর্ডারের মূল্যে Jensen-এর দুই দিক যাচাই করে।

import numpy as np

rng = np.random.default_rng(42)
np.set_printoptions(suppress=True)
n = 200                                          # কাল্পনিক বাজারঘর: ২০০ জন গ্রাহক
orders = rng.poisson(6, n).astype(float)         # গত ৬ মাসে অর্ডার
basket = rng.normal(9, 2.5, n)                   # গড় ঝুড়ি, শত টাকায়
X = np.column_stack([np.ones(n), orders, basket])
y = 3 + 1.2 * orders + 0.45 * basket + rng.normal(0, 1.5, n)

f = lambda w: np.sum((X @ w - y) ** 2) / (2 * n)     # quadratic loss
g = lambda w: X.T @ (X @ w - y) / n
ev = np.linalg.eigvalsh(X.T @ X / n)                 # Hessian সব w-এ একই
mu, L = ev[0], ev[-1]
print("Hessian eigenvalues:", np.round(ev, 4))
print(f"mu = {mu:.4f}   L = {L:.2f}   kappa = L/mu = {L / mu:.0f}")

held_mu = held_L = 0
for _ in range(1000):                                # দুই দিকের সীমা এলোমেলো জোড়ায়
    a, b = rng.normal(0, 3, (2, 3))
    lin, d2 = f(a) + g(a) @ (b - a), (b - a) @ (b - a)
    held_mu += f(b) >= lin + mu / 2 * d2 - 1e-9
    held_L += f(b) <= lin + L / 2 * d2 + 1e-9
print(f"lower bound (mu) held {held_mu}/1000, upper bound (L) held {held_L}/1000")

Z = (X[:, 1:] - X[:, 1:].mean(0)) / X[:, 1:].std(0)  # standardize করলে?
Xs = np.column_stack([np.ones(n), Z])
ev_s = np.linalg.eigvalsh(Xs.T @ Xs / n)
print(f"after standardizing: kappa = {ev_s[-1] / ev_s[0]:.2f}")

v = rng.lognormal(np.log(900), 0.6, 10_000)          # অর্ডারের মূল্য, টাকা
print(f"Jensen, f=x^2 : E[f(V)] = {np.mean(v**2):,.0f} >= f(E[V]) = {np.mean(v)**2:,.0f}")
print(f"Jensen, f=log : E[log V] = {np.mean(np.log(v)):.4f} <= log E[V] = {np.log(np.mean(v)):.4f}")

Hessian eigenvalues: [  0.0588   5.4873 123.7122]
mu = 0.0588   L = 123.71   kappa = L/mu = 2103
lower bound (mu) held 1000/1000, upper bound (L) held 1000/1000
after standardizing: kappa = 1.26
Jensen, f=x^2 : E[f(V)] = 1,690,966 >= f(E[V]) = 1,172,901
Jensen, f=log : E[log V] = 6.8054 <= log E[V] = 6.9875

৯ · Non-convex জগতে কী করা হয়

Convex model সুন্দর, কিন্তু সব সমস্যা convex নয়। Non-convex সমস্যায় ব্যবহারিক কৌশলগুলো চারটি ভাগে পড়ে, আর প্রত্যেকটির সীমাও আছে।

• বহু শুরু আর ভালো শুরু: অংশ ৪-এর মতো কয়েকবার চালিয়ে সবচেয়ে কম loss নেওয়া। k-means-এ k-means++ (Arthur ও Vassilvitskii, ২০০৭) শুরুর কেন্দ্র এমনভাবে বাছে যে প্রত্যাশিত objective সর্বোত্তমের O(log k) গুণের মধ্যে থাকে। AI-এর ভিত্তি কোর্সের পর্ব ৬৫-এ k-means চালিয়েছেন।
• পর্যায়ক্রমে convex অংশ: k-means-এ কেন্দ্র স্থির রাখলে বিন্দু ভাগ করা সহজ, ভাগ স্থির রাখলে কেন্দ্র (গড়) একটি convex সমস্যার সমাধান। Lloyd-এর পদ্ধতি, EM আর matrix factorization-এর alternating least squares এভাবেই চলে; প্রতি ধাপে loss বাড়ে না, কিন্তু global minimum-এর নিশ্চয়তা নেই।
• Convex relaxation: কঠিন শর্তকে কাছাকাছি একটি convex শর্তে বদলানো। সবচেয়ে বিখ্যাত উদাহরণ: “কয়টি ওজন অশূন্য” (L0) গোনা non-convex, তার জায়গায় ‖w‖₁ নিলে lasso, যা convex. 0-1 loss-এর জায়গায় hinge বা log loss বসানোও একই ভাবনা, যাকে পর্ব ০২-এ surrogate loss বলা হয়েছে।
• Neural network-এ অভিজ্ঞতার ওপর ভরসা: ভালো initialization, SGD-এর noise, momentum আর অনেক বেশি parameter মিলে বাস্তবে সাধারণত ভালো সমাধান মেলে। কিন্তু এটি পর্যবেক্ষণ আর আংশিক তত্ত্ব, convex-এর মতো সাধারণ নিশ্চয়তা নয় (প্রশ্ন ০২)।

১০ · AI-এর যুগে — convexity-র দাবি আর optimizer-এর পরামর্শ যাচাই

AI assistant “এই loss convex, তাই যেকোনো optimizer চলবে” ধরনের কথা আত্মবিশ্বাসের সঙ্গে বলে। প্রায়ই কথাটি অর্ধেক সত্য: loss অনুমানে convex, কিন্তু parameter-এ নয়; বা composition-এর শর্ত বাদ পড়েছে। নিচের ছকে সাধারণ ভুল আর ধরার উপায়।

AI-এর দেওয়া convexity-র দাবি হাতে পেলে — যাচাইয়ের চেকলিস্ট

• কোন চলকের সাপেক্ষে convex, তা স্পষ্ট লিখেছি (অনুমান না parameter)
• প্রতিটি ধাপ অংশ ৬-এর একটি নিয়মের সঙ্গে মিলিয়েছি, composition-এ অ-হ্রাসমান শর্তসহ
• একটি সংখ্যাগত জ্যা-পরীক্ষা চালিয়েছি; কোনো লঙ্ঘন পেলে দাবিটি বাতিল
• Optimizer-এর পরামর্শে learning rate বা solver নিজের library version-এর docs থেকে মিলিয়েছি, পুরোনো বা বানানো parameter আছে কি না দেখেছি
• Non-convex model-এর ফল কয়েকটি seed-এ চালিয়ে তুলনা করেছি, একটি run-কে চূড়ান্ত ধরিনি
• ডেটা আগে ভাগ করেছি, test set তালা দেওয়া, আর একটি সরল baseline-এর সঙ্গে তুলনা করেছি
• কোনো আসল গ্রাহকের ব্যক্তিগত ডেটা AI-তে পেস্ট করিনি