{ "cells": [ { "cell_type": "markdown", "id": "f121bb3d", "metadata": {}, "source": [ "# 六种方法的动态实验（牛顿法含求根与优化）\n", "按顺序运行。依赖：numpy、matplotlib、IPython。所有算法代码都包含在本 notebook 内，无需本地导入。\n", "\n", "若缺少依赖，取消下一格安装语句的注释。每个动画使用 FuncAnimation 与 HTML(ani.to_jshtml()) 渲染。" ] }, { "cell_type": "code", "execution_count": 1, "id": "3169e16e", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:26.734091Z", "iopub.status.busy": "2026-10-02T12:51:26.734091Z", "iopub.status.idle": "2026-10-02T12:51:26.743088Z", "shell.execute_reply": "2026-10-02T12:51:26.742088Z" } }, "outputs": [], "source": [ "# %pip install numpy matplotlib ipython" ] }, { "cell_type": "code", "execution_count": 2, "id": "4d323360", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:26.746089Z", "iopub.status.busy": "2026-10-02T12:51:26.745088Z", "iopub.status.idle": "2026-10-02T12:51:27.542433Z", "shell.execute_reply": "2026-10-02T12:51:27.542433Z" } }, "outputs": [], "source": [ "\"\"\"Six reproducible animations. Run in Jupyter; requires numpy, matplotlib, IPython.\"\"\"\n", "import math\n", "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from matplotlib.animation import FuncAnimation\n", "from IPython.display import HTML, display\n", "\n", "\n", "def taylor_sin(x, degree, center=0.0):\n", " \"\"\"Degree means polynomial degree, not number of nonzero sine terms.\"\"\"\n", " x = np.asarray(x, dtype=np.float64)\n", " result = np.zeros_like(x)\n", " power = np.ones_like(x)\n", " derivatives = [np.sin(center), np.cos(center), -np.sin(center), -np.cos(center)]\n", " for k in range(degree + 1):\n", " result += derivatives[k % 4] * power\n", " power *= (x - center) / (k + 1)\n", " return result\n", "\n", "\n", "def newton_states():\n", " states = []\n", " x = 3.0\n", " for k in range(6):\n", " next_x = x - (x*x - 2)/(2*x)\n", " states.append(dict(k=k, x=x, next=next_x, error=abs(x*x-2)))\n", " x = next_x\n", " return states\n", "\n", "\n", "def objective(p):\n", " x, y = p\n", " return (1-x)**2 + 100*(y-x*x)**2\n", "\n", "\n", "def gradient(p):\n", " x, y = p\n", " return np.array([-2*(1-x)-400*x*(y-x*x), 200*(y-x*x)])\n", "\n", "\n", "def newton_opt_states():\n", " \"\"\"Newton applied to f'(x)=0 for f(x)=x^4/4+x^2/2.\"\"\"\n", " states = []\n", " x = 2.5\n", " for k in range(9):\n", " value, grad, hess = x**4/4 + x*x/2, x**3+x, 3*x*x+1\n", " next_x = x-grad/hess\n", " states.append(dict(k=k, x=x, next=next_x, value=value, grad=grad, hess=hess))\n", " if abs(grad) < 1e-12:\n", " break\n", " x = next_x\n", " return states\n", "\n", "\n", "def bfgs_states():\n", " p = np.array([-1.2, 1.0], dtype=np.float64)\n", " H = np.eye(2)\n", " states = [dict(p=p.tolist(), value=float(objective(p)), alpha=0.0)]\n", " for _ in range(80):\n", " g = gradient(p)\n", " if np.linalg.norm(g) < 1e-7:\n", " break\n", " direction = -H @ g\n", " alpha = 1.0\n", " # Armijo backtracking prevents an oversized step up the steep valley wall.\n", " while objective(p + alpha*direction) > objective(p) + 1e-4*alpha*(g @ direction):\n", " alpha *= 0.5\n", " if alpha < 1e-14:\n", " raise RuntimeError('Line search failed')\n", " q = p + alpha*direction\n", " s, y = q-p, gradient(q)-g\n", " curvature = float(y @ s)\n", " if curvature > 1e-12:\n", " rho = 1/curvature\n", " V = np.eye(2) - rho*np.outer(s, y)\n", " H = V @ H @ V.T + rho*np.outer(s, s)\n", " p = q\n", " states.append(dict(p=p.tolist(), value=float(objective(p)), alpha=alpha))\n", " return states\n", "\n", "\n", "def boost_states(histogram=False, rounds=16):\n", " \"\"\"Educational squared-error GBDT: exact/depthwise versus binned/leafwise.\n", "\n", " These are small transparent implementations, not the xgboost/lightgbm libraries.\n", " Loss is 0.5*(prediction-target)**2, g=prediction-target, h=1.\n", " Both use lambda=1, gamma=0, eta=0.3, min_samples_leaf=3.\n", " \"\"\"\n", " x = np.linspace(-3, 3, 72, dtype=np.float64)\n", " target = np.sin(1.5*x) + 0.35*x + 0.12*np.cos(11*x)\n", " prediction = np.full_like(x, target.mean())\n", " thresholds = (np.linspace(x.min(), x.max(), 13)[1:-1] if histogram\n", " else (x[:-1]+x[1:])/2)\n", " states = [dict(pred=prediction.tolist(), tree=np.zeros_like(x).tolist(),\n", " residual=(target-prediction).tolist(), mse=float(np.mean((target-prediction)**2)),\n", " leaves=1, splits=[], gains=[])]\n", " for _ in range(rounds):\n", " residual = target-prediction\n", " g = prediction-target\n", " leaves = [dict(ids=np.arange(len(x)), depth=0)]\n", " splits, gains = [], []\n", "\n", " def best_split(leaf):\n", " ids = leaf['ids']\n", " best = None\n", " for threshold in thresholds:\n", " left = ids[x[ids] <= threshold]\n", " right = ids[x[ids] > threshold]\n", " if min(len(left), len(right)) < 3:\n", " continue\n", " gain = 0.5*(g[left].sum()**2/(len(left)+1)\n", " + g[right].sum()**2/(len(right)+1)\n", " - g[ids].sum()**2/(len(ids)+1))\n", " if gain > 1e-12 and (best is None or gain > best[0]):\n", " best = (float(gain), float(threshold), left, right)\n", " return best\n", "\n", " while True:\n", " candidates = [(i, best_split(leaf)) for i, leaf in enumerate(leaves)\n", " if histogram or leaf['depth'] < 2]\n", " candidates = [(i, b) for i, b in candidates if b is not None]\n", " if not candidates or (histogram and len(leaves) >= 4):\n", " break\n", " # Depthwise chooses the shallowest available node; leafwise chooses gain.\n", " index, best = (max(candidates, key=lambda item: item[1][0]) if histogram\n", " else min(candidates, key=lambda item: (leaves[item[0]]['depth'], item[0])))\n", " gain, threshold, left, right = best\n", " depth = leaves[index]['depth'] + 1\n", " leaves[index:index+1] = [dict(ids=left, depth=depth), dict(ids=right, depth=depth)]\n", " splits.append(threshold)\n", " gains.append(gain)\n", " tree = np.zeros_like(x)\n", " for leaf in leaves:\n", " ids = leaf['ids']\n", " tree[ids] = -g[ids].sum()/(len(ids)+1)\n", " prediction = prediction + 0.3*tree\n", " states.append(dict(pred=prediction.tolist(), tree=tree.tolist(), residual=residual.tolist(),\n", " mse=float(np.mean((target-prediction)**2)), leaves=len(leaves),\n", " splits=splits, gains=gains))\n", " return dict(x=x.tolist(), target=target.tolist(), states=states)\n", "\n", "\n", "def make_animation(method):\n", " \"\"\"Return a retained FuncAnimation; render with HTML(ani.to_jshtml()).\"\"\"\n", " fig, axes = plt.subplots(1, 2, figsize=(11, 4.4))\n", " fig.subplots_adjust(wspace=0.30, bottom=0.17, top=0.83)\n", " if method == 'newton':\n", " states = newton_states()\n", " elif method == 'newton_opt':\n", " states = newton_opt_states()\n", " elif method in ('taylor', 'maclaurin'):\n", " states = list(range(20))\n", " elif method == 'bfgs':\n", " states = bfgs_states()\n", " elif method in ('xgboost', 'lightgbm'):\n", " data = boost_states(method == 'lightgbm')\n", " states = data['states']\n", " else:\n", " raise ValueError('Unknown method')\n", "\n", " def animate(frame):\n", " a, b = axes\n", " for ax in axes:\n", " ax.clear()\n", " ax.grid(alpha=0.18)\n", " state = states[frame]\n", " if method == 'newton':\n", " grid = np.linspace(0, 3.3, 400)\n", " x, q = state['x'], state['next']\n", " a.plot(grid, grid**2-2, color='#176b64', label='f(x)=x^2-2')\n", " a.plot(grid, x*x-2+2*x*(grid-x), '--', color='#c45632', label='tangent')\n", " a.scatter([x, q], [x*x-2, 0], color='#c45632')\n", " a.axhline(0, color='gray', lw=0.7)\n", " a.set(xlim=(0, 3.3), ylim=(-3, 9), xlabel='x', ylabel='f(x)')\n", " b.semilogy(range(frame+1), [max(s['error'], 1e-16) for s in states[:frame+1]], 'o-')\n", " b.set(xlim=(0, 5), ylim=(1e-16, 10), xlabel='iteration k', ylabel='|f(x_k)|')\n", " title = f'Newton k={frame}, x={x:.8f}, next={q:.8f}'\n", " elif method == 'newton_opt':\n", " grid = np.linspace(-1, 2.8, 400)\n", " x, q = state['x'], state['next']\n", " model = state['value'] + state['grad']*(grid-x) + 0.5*state['hess']*(grid-x)**2\n", " a.plot(grid, grid**4/4+grid**2/2, color='#176b64', label='objective f(x)')\n", " a.plot(grid, model, '--', color='#c45632', label='quadratic model')\n", " a.scatter([x, q], [state['value'], q**4/4+q*q/2], color='#c45632', label='current / next on f')\n", " a.scatter([q], [state['value']-state['grad']**2/(2*state['hess'])], marker='x', color='#c45632', label='model minimum')\n", " a.set(xlim=(-1,2.8), ylim=(-2,21), xlabel='x', ylabel='objective / model')\n", " b.plot(grid, grid**3+grid, color='#176b64', label=\"f'(x)\")\n", " b.plot(grid, state['grad']+state['hess']*(grid-x), '--', color='#c45632', label=\"tangent of f'\")\n", " b.scatter([x,q], [state['grad'],0], color='#c45632')\n", " b.axhline(0, color='gray', lw=0.7)\n", " b.set(xlim=(-1,2.8), ylim=(-5,26), xlabel='x', ylabel='derivative')\n", " b.legend(fontsize=8)\n", " title = f\"Newton optimization k={frame}, f={state['value']:.3g}, |gradient|={abs(state['grad']):.3g}\"\n", " elif method in ('taylor', 'maclaurin'):\n", " center = 1.0 if method == 'taylor' else 0.0\n", " grid = np.linspace(-2*np.pi, 2*np.pi, 500, dtype=np.float64)\n", " approx = taylor_sin(grid, frame, center)\n", " a.plot(grid, np.sin(grid), '--', color='gray', label='sin(x)')\n", " a.plot(grid, approx, color='#c45632', label='polynomial')\n", " a.scatter([center], [np.sin(center)], color='#176b64')\n", " a.set(xlim=(-2*np.pi, 2*np.pi), ylim=(-2, 2), xlabel='x', ylabel='value (clipped to +/-2)')\n", " b.semilogy(grid, np.maximum(abs(approx-np.sin(grid)), 1e-16), color='#176b64')\n", " b.set(xlim=(-2*np.pi, 2*np.pi), ylim=(1e-16, 1e4), xlabel='x', ylabel='absolute error (floor 1e-16)')\n", " title = f'{method}: center={center}, degree={frame}'\n", " elif method == 'bfgs':\n", " xx, yy = np.meshgrid(np.linspace(-1.6, 1.6, 180), np.linspace(-0.6, 2, 160))\n", " a.contour(xx, yy, (1-xx)**2+100*(yy-xx*xx)**2, levels=[0.1,1,4,10,50,100,400], alpha=0.45)\n", " path = np.array([s['p'] for s in states[:frame+1]])\n", " a.plot(path[:, 0], path[:, 1], 'o-', ms=3, color='#c45632', label='BFGS path')\n", " a.scatter([1], [1], marker='*', s=110, color='#176b64')\n", " a.set(xlim=(-1.6, 1.6), ylim=(-0.6, 2), xlabel='x', ylabel='y')\n", " b.semilogy(range(frame+1), [max(s['value'], 1e-16) for s in states[:frame+1]])\n", " b.set(xlim=(0, len(states)-1), ylim=(1e-16, 100), xlabel='iteration', ylabel='objective')\n", " title = f'BFGS k={frame}, f={state[\"value\"]:.3g}, alpha={state[\"alpha\"]:.3g}'\n", " else:\n", " x, target = np.array(data['x']), np.array(data['target'])\n", " a.scatter(x, target, s=10, color='gray', label='training target')\n", " a.step(x, state['pred'], where='mid', color='#176b64', label='ensemble')\n", " a.set(xlim=(-3,3), ylim=(-2.3,2.3), xlabel='feature x', ylabel='prediction')\n", " b.scatter(x, state['residual'], s=10, color='gray', label='residual before this tree')\n", " b.step(x, state['tree'], where='mid', color='#c45632', label='new tree (before eta)')\n", " for split in state['splits']:\n", " b.axvline(split, color='#c45632', lw=0.7, alpha=0.3)\n", " b.set(xlim=(-3,3), ylim=(-2.3,2.3), xlabel='feature x', ylabel='residual / leaf weight')\n", " b.legend(fontsize=8)\n", " title = f'{method} teaching model: round={frame}, MSE={state[\"mse\"]:.4f}, leaves={state[\"leaves\"]}'\n", " a.legend(loc='upper left', fontsize=8)\n", " fig.suptitle(title)\n", " return tuple(axes)\n", "\n", " # Axes and labels change each frame, so blit=False is intentional.\n", " ani = FuncAnimation(fig, animate, frames=len(states), interval=650, blit=False, repeat=False)\n", " plt.close(fig) # Suppress the extra static image in Jupyter.\n", " return ani\n", "\n", "\n", "# Jupyter example:\n", "# ani = make_animation('newton')\n", "# HTML(ani.to_jshtml())\n", "# Other names: newton_opt, taylor, maclaurin, bfgs, xgboost, lightgbm.\n" ] }, { "cell_type": "markdown", "id": "e587bb73", "metadata": {}, "source": [ "## 牛顿法 · 求根\n", "用切线寻找零点\n", "\n", "`xₖ₊₁ = xₖ − f(xₖ) / f′(xₖ)，f(x)=x²−2`\n", "\n", "### 观察与理解\n", "观察动画时，先找到曲线上的当前点，再沿该点的切线走到横轴，交点的横坐标就是下一次迭代值。这里从三开始求解平方根二，前几次移动明显，靠近根以后，两个点几乎重合，但右侧对数误差图仍能展示精度的快速提升。每一帧同时显示当前位置与下一位置，因此不要把切线与横轴的交点误认为已经更新后的曲线点。牛顿法的本质是用当前点附近的一阶线性模型替代原函数，再求这个简单模型的零点。对于足够光滑的函数，如果目标是单根、导数不为零而且初值足够接近根，通常可以获得局部二次收敛。不过，这并不表示任意起点都能成功：导数很小时可能产生极大的步长，复杂函数还可能发生循环或者收敛到另一个根。这个例子选择了稳定的正初值，所以主要展示快速收敛，而不是所有失败情形。图中的误差是函数残差绝对值，并非横坐标与真实根的距离；两者在简单根附近相关，但概念不能混用。" ] }, { "cell_type": "code", "execution_count": 3, "id": "2004ee4c", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:27.544434Z", "iopub.status.busy": "2026-10-02T12:51:27.544434Z", "iopub.status.idle": "2026-10-02T12:51:28.991393Z", "shell.execute_reply": "2026-10-02T12:51:28.991393Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_newton = make_animation('newton')\n", "HTML(ani_newton.to_jshtml())" ] }, { "cell_type": "markdown", "id": "81f04bb5", "metadata": {}, "source": [ "## 泰勒展开\n", "围绕非零中心建立局部模型\n", "\n", "`Pₙ(x) = Σₖ₌₀ⁿ f⁽ᵏ⁾(a)(x−a)ᵏ/k!，a=1`\n", "\n", "### 观察与理解\n", "这组动画把正弦函数放在展开中心一附近观察，橙色曲线随着最高次数增加而变化。零次多项式只保留中心处的函数值，一次多项式再匹配斜率，二次及更高次数则逐渐补充弯曲程度等局部信息。最值得留意的是，中心附近往往先贴近真实函数，而较远的位置需要更多项才能改善。左图固定纵轴在负二到二之间，因此某些低阶曲线在边缘会被截断，不能把曲线离开画面解释为函数没有定义；右侧误差图用于补充这种信息。对于正弦函数，泰勒级数在任意有限实数处都收敛，但有限阶近似的误差仍然与距离和阶数有关。一般函数不能直接照搬这个结论：有的级数只有有限收敛半径，还有光滑函数不等于自己的泰勒级数。这里使用最高次数作为帧编号，包含从零次到该次数的所有项，避免把次数与非零项数混淆。理解泰勒展开时，应同时关注展开中心、截断阶数以及考察区间，而不能只凭某一点的吻合程度判断整个区间上的近似质量。" ] }, { "cell_type": "code", "execution_count": 4, "id": "9d72c4c3", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:28.995393Z", "iopub.status.busy": "2026-10-02T12:51:28.994393Z", "iopub.status.idle": "2026-10-02T12:51:33.619122Z", "shell.execute_reply": "2026-10-02T12:51:33.619122Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_taylor = make_animation('taylor')\n", "HTML(ani_taylor.to_jshtml())" ] }, { "cell_type": "markdown", "id": "05c7319b", "metadata": {}, "source": [ "## 麦克劳林展开\n", "泰勒展开在原点的特例\n", "\n", "`sin x = x − x³/3! + x⁵/5! − …，a=0`\n", "\n", "### 观察与理解\n", "麦克劳林展开就是把泰勒展开的中心固定为零，因此它不是与泰勒展开相互独立的另一套原理。对于正弦函数，原点处所有偶数阶导数都为零，所以动画在偶数次数与前一个奇数次数之间可能完全不动。这种停顿是数学结构的真实反映，而不是播放故障。例如三次多项式和四次多项式相同，都等于一次项减去三次项除以六。随着奇数次项加入，近似逐渐从原点附近扩展到更远的位置；然而某个有限位置上的绝对误差不一定每增加一次就严格下降，因为截断项之间存在抵消。用户给出的参考程序用非零项数控制循环，本演示则统一用最高次数控制帧，所以十九次对应十个非零项，并不等于十九个非零项。计算时输入被转换为浮点数组，并递推生成幂与阶乘的比值，减少整数幂溢出以及直接计算大阶乘的问题。右图的误差设置了浮点显示下限，接近这个下限时应理解为数值舍入已经影响结果，而不是计算机证明了无限精度的相等。" ] }, { "cell_type": "code", "execution_count": 5, "id": "4e52fa66", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:33.634118Z", "iopub.status.busy": "2026-10-02T12:51:33.634118Z", "iopub.status.idle": "2026-10-02T12:51:37.819069Z", "shell.execute_reply": "2026-10-02T12:51:37.819069Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_maclaurin = make_animation('maclaurin')\n", "HTML(ani_maclaurin.to_jshtml())" ] }, { "cell_type": "markdown", "id": "61d2847b", "metadata": {}, "source": [ "## 拟牛顿法 · BFGS\n", "从梯度变化学习曲率\n", "\n", "`pₖ = −Hₖ∇f(xₖ)，sₖ = xₖ₊₁−xₖ，yₖ = ∇f(xₖ₊₁)−∇f(xₖ)`\n", "\n", "### 观察与理解\n", "这里选择狭长弯曲谷底的 Rosenbrock 函数，目标最小点位于一与一。背景等高线展示地形，橙色折线记录 BFGS 的真实迭代路径。开始时方向可能跨向陡峭谷壁，因此程序使用 Armijo 回溯线搜索缩短步长；进入谷底以后，路径逐渐转弯并逼近最优点。拟牛顿法的关键并不是每轮计算真实海森矩阵，而是利用相邻两步的位置变化与梯度变化来更新曲率近似。本例的 H 表示逆海森矩阵的近似，初值取单位阵，所以最初方向与负梯度一致，后续方向则逐渐包含过去观测到的曲率信息。与前面的求根牛顿法相比，这里解决的是多元函数最小化问题，二者相关却不能直接混为同一个任务。动画中目标值下降并不保证每个坐标都单调靠近一，弯曲路径恰好说明耦合变量需要共同调整。只有曲率内积满足正值阈值时才进行矩阵更新，以减少数值不稳定；线搜索也并不意味着所有非凸问题都能找到全局最优解。右图展示目标函数值，便于把几何移动与优化进展对应起来。" ] }, { "cell_type": "code", "execution_count": 6, "id": "8bc7cddb", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:37.832066Z", "iopub.status.busy": "2026-10-02T12:51:37.831066Z", "iopub.status.idle": "2026-10-02T12:51:44.361702Z", "shell.execute_reply": "2026-10-02T12:51:44.360192Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_bfgs = make_animation('bfgs')\n", "HTML(ani_bfgs.to_jshtml())" ] }, { "cell_type": "markdown", "id": "9c718bab", "metadata": {}, "source": [ "## XGBoost 核心机制\n", "二阶目标与逐轮加树\n", "\n", "`w* = −G/(H+λ)，Gain = ½[Gᴸ²/(Hᴸ+λ)+Gᴿ²/(Hᴿ+λ)−G²/(H+λ)]−γ`\n", "\n", "### 观察与理解\n", "左图灰点是固定训练样本，绿色阶梯线是当前所有树的累加预测。每推进一轮，右图先展示这一轮加树之前的残差，再用橙色阶梯线展示新树的叶子输出；真正加到总预测上的数值还要乘以零点三的学习率。这里使用平方损失的一半，因此梯度等于预测减目标，海森量恒为一。每个叶子的输出由梯度和海森量的聚合值计算，并通过正则参数一收缩，分裂则根据二阶目标的增益选择。这比只说新树拟合错误更能解释 XGBoost 的核心数学结构。本演示采用相邻样本中点作为精确候选阈值，并按深度优先生长到最大深度二，最多得到四个叶子；页面还给出实际分裂次序和各次增益。需要注意，现代 XGBoost 也支持直方图算法以及其他生长策略，精确分裂与按层生长不是它独有或必须的属性。右图残差属于更新前，页面均方误差属于更新后，所以两者观察时要对准时间。训练误差下降只能说明对当前样本拟合更好，不能证明泛化改善；这个小实验没有验证集，也不用于比较生产模型性能。" ] }, { "cell_type": "code", "execution_count": 7, "id": "f4fff084", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:44.401305Z", "iopub.status.busy": "2026-10-02T12:51:44.401305Z", "iopub.status.idle": "2026-10-02T12:51:48.297955Z", "shell.execute_reply": "2026-10-02T12:51:48.297955Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_xgboost = make_animation('xgboost')\n", "HTML(ani_xgboost.to_jshtml())" ] }, { "cell_type": "markdown", "id": "e62e07aa", "metadata": {}, "source": [ "## LightGBM 核心机制\n", "直方图候选与最佳叶子优先\n", "\n", "`候选阈值来自分箱边界；每次分裂当前增益最大的叶子`\n", "\n", "### 观察与理解\n", "这一页与前一页使用相同的训练点、初始均值、学习率和正则参数，因此可以把注意力放在树如何生长。连续特征先被划分为十二个等宽箱，分裂只允许发生在内部箱边界上，减少候选阈值数量。程序再从所有可分裂叶子中选取增益最大的一个继续分裂，达到四个叶子或没有正增益时停止。右图的竖线标明这一轮选中的阈值，下面按顺序列出增益，可以观察计算资源如何优先用于当前最能降低目标的位置。这种叶子优先生长允许不同分支具有不同深度，因此与最大深度二的树即使同样最多四个叶子，也可能形成不同的分段结构。不过当前小数据不保证每轮都出现不对称树，更不保证任一方法总是误差更低。这里为便于理解，直接在分箱边界汇总样本梯度与海森量，结果体现直方图分裂的数学含义，但没有实现实际库里的高效直方图缓存和差分构建。LightGBM 的分箱策略也不必是等宽箱；其他优化如特征捆绑与梯度采样没有在本例启用，不能从动画推断它们的作用。叶子数限制有助于控制复杂度，但真实任务仍需要验证集、早停及最小叶样本数等约束。" ] }, { "cell_type": "code", "execution_count": 8, "id": "10838a3c", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:48.307954Z", "iopub.status.busy": "2026-10-02T12:51:48.306954Z", "iopub.status.idle": "2026-10-02T12:51:52.304398Z", "shell.execute_reply": "2026-10-02T12:51:52.304398Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_lightgbm = make_animation('lightgbm')\n", "HTML(ani_lightgbm.to_jshtml())" ] }, { "cell_type": "markdown", "id": "a4f23db1", "metadata": {}, "source": [ "## 牛顿法 · 优化\n", "对导数求根，用二次模型寻找极小值\n", "\n", "`xₖ₊₁ = xₖ − f′(xₖ)/f″(xₖ)；f(x)=x⁴/4+x²/2，f′(x)=x³+x，f″(x)=3x²+1`\n", "\n", "### 观察与理解\n", "牛顿优化法可以从求根法直接推导：令新的求根函数为原目标的一阶导数，对这个导数函数应用牛顿公式，分母就成为原目标的二阶导数。因此不是简单把二阶导数随意代入原公式，而是同时把分子换成一阶导数，把分母换成二阶导数。右图专门展示这一步：绿色曲线是一阶导数，橙色虚线是它在当前点处的切线，切线与横轴交点给出下一个位置。左图从优化角度展示同一更新：用目标函数在当前点处的二阶泰勒多项式建立局部抛物线，该抛物线的最低点横坐标恰好也是下一位置。注意抛物线上的最低点不一定落在真实函数上，左图的圆点显示真实目标值，叉号才表示二次模型的最低点。随着位置靠近零，导数和目标值一起下降，模型与目标在局部更加接近。本例二阶导数始终大于零，因此目标严格凸，唯一驻点零就是全局最小点。但一般非凸函数的驻点也可能是极大点或其他类型的平稳点；二阶导数为零时公式不可直接使用，为负时二次模型甚至没有极小值。实际优化常结合阻尼、线搜索或曲率修正来改善稳定性。多元形式则需要用海森矩阵求解牛顿方向，拟牛顿法正是通过近似曲率来降低这部分计算成本。" ] }, { "cell_type": "code", "execution_count": 9, "id": "2666c124", "metadata": { "execution": { "iopub.execute_input": "2026-10-02T12:51:52.312414Z", "iopub.status.busy": "2026-10-02T12:51:52.312414Z", "iopub.status.idle": "2026-10-02T12:51:54.226125Z", "shell.execute_reply": "2026-10-02T12:51:54.226125Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "
\n", " \n", "
\n", " \n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", " \n", " \n", " \n", " \n", " \n", " \n", "
\n", "
\n", "
\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ani_newton_opt = make_animation('newton_opt')\n", "HTML(ani_newton_opt.to_jshtml())" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.2" } }, "nbformat": 4, "nbformat_minor": 5 }