首页
关于
Search
1
同步本地Markdown至Typecho站点
88 阅读
2
微服务
41 阅读
3
苍穹外卖
32 阅读
4
JavaWeb——后端
25 阅读
5
消息队列MQ
20 阅读
后端学习
项目
杂项
科研
论文
默认分类
登录
找到
9
篇与
论文
相关的结果
2025-09-20
deepwalk
DeepWalk DeepWalk 的最终目标是—— 把图中的每个节点，用一个低维向量表示（embedding）出来，使得结构相似的节点在向量空间中也接近。 也就是说，如果两个节点在图上经常“一起出现”（相连、同社群等），那它们的 embedding 也应该相似。 主要思想 将图结构转化为“序列语料”： 在图上做 随机游走（random walks），生成顶点序列，类似于自然语言中的“句子”。 将随机游走得到的序列输入 Skip-Gram 模型，学习节点的低维嵌入表示。 学到的嵌入能捕捉到 邻居相似性、社区结构，可用于分类、聚类、链路预测等任务。 输入 & 输出 输入：图结构 $G=(V,E)$，随机游走参数（步长 $t$，次数 $\gamma$，窗口大小 $w$），嵌入维度 $d$。 输出：节点嵌入矩阵 $\Phi \in \mathbb{R}^{|V|\times d}$。 关键公式与目标 随机游走生成“句子”： 从某个顶点 $v_i$ 出发，采样一个长度为 $t$ 的随机游走序列： $$ W_{v_i} = (v_i, v_{i+1}, \dots, v_{i+t}) $$ 生成的序列 $W_{v_i}$ 就是一句“话”，用来训练 Skip-Gram 模型。在这些序列中，如果两个节点经常在相邻位置出现，就表示它们关系密切。 ["A", "B", "C", "D"] Skip-Gram 目标函数： 现在我们用 Word2Vec 的思想：对于一句话 ["A", "B", "C", "D"]，假设窗口大小 $w = 1$，也就是每个节点只看它的邻居。那么训练样本是这样的： 中心节点 它要预测的邻居 A B B A, C C B, D D C 模型要学的是： “给我节点 B，我要能预测出 A 和 C。” “给我节点 C，我要能预测出 B 和 D。” 于是就有这个公式，给定中心节点 $v_i$，最大化其上下文窗口内邻居节点的条件概率： $$ \max_{\Phi} \sum_{i=1}^{|V|} \sum_{u \in \mathcal{N}_w(v_i)} \log Pr(u \mid \Phi(v_i)) $$ 其中 $\mathcal{N}_w(v_i)$ 表示在随机游走序列中，窗口大小 $w$ 内的上下文节点。 我希望模型能学到这样一种 embedding：中心节点 $v_i$ 能够高概率预测出它周围的邻居 $u$。 优化形式（负对数似然）： 就是把上面的最大化目标，改写成一个最小化损失函数。 最大化“好事”（邻居出现的概率）= 最小化“坏事”（邻居预测错误的概率） $$ \min_{\Phi} - \log Pr\big( {v_{i-w},\dots,v_{i+w}} \mid \Phi(v_i) \big) $$ 概率建模（Hierarchical Softmax 或 Negative Sampling）： $$ Pr(u \mid \Phi(v_i)) = \frac{\exp\big( \Phi(u) \cdot \Phi(v_i) \big)}{\sum_{v \in V} \exp\big( \Phi(v) \cdot \Phi(v_i) \big)} $$ 这相当于用 Softmax 把所有节点的相似度转成概率分布。 其中： 分子：中心节点和邻居节点的相似度（点积越大越相似）； 分母：所有节点的相似度和（用来归一化成概率）。 如果 $u$ 是 $v_i$ 的邻居，那么 $\Phi(u)$ 与 $\Phi(v_i)$ 的点积就应更大。 例子 想象你是个“社交分析师”： 你观察到小明每天都和小红、小刚一起出现； 而小明几乎从不和小李在一起； 那你自然会说：小明和小红、小刚的关系更近。 DeepWalk 就是通过“随机游走 + 预测邻居”这个机制， 自动学出“谁跟谁关系近”的数值表示。 训练逻辑 1）加载 10+1 张图 A_list = [A100, A101, ..., A110] 我们取前 10 张作为输入，最后一张作为真实标签。 2）对每一个时间步的图做 DeepWalk for t in range(100, 110): emb_t = DeepWalk(A_t) 每张图 $A_t$ 都独立训练一个 节点 embedding（比如 400×64）。 400是节点数，64是嵌入维数 embedding 就是每个节点在这一时刻的“语义坐标”。 训练目标是：让在图里常相邻的节点在 embedding 空间也靠得近。 可以理解成： DeepWalk 把图结构变成“节点的向量表示”。 3）拼接成时间序列特征（10步） 对每对节点 (i, j)，你把过去10个时间步的 embedding 拿出来，计算每步的 Hadamard积（元素乘）： feats = [emb100[i]*emb100[j], emb101[i]*emb101[j], ..., emb109[i]*emb109[j]] X_ij = concatenate(feats) 每个节点对 (i, j) → 一个 10×64 = 640 维的特征； 这 640 维包含了它俩“过去10步的相似度变化轨迹”。 白话理解： 这个特征就像是“节点对关系的时间切片”。 如果两人（节点）经常靠得近 → 向量相似； 如果逐渐靠近 → 特征会呈现变化趋势。 4）第11步图作为真实答案（标签） A_target = A110 y_ij = 1 if 节点i和j在第110步相连 else 0 每个节点对 (i, j) 的标签就是第11步的真相； 如果在第11步有边 → 正样本； 没边 → 负样本。 5）平衡样本（1:1） 因为稀疏图中没连边的太多： 原来是 9,237 个正样本 vs 70,563 个负样本； 现在我们随机保留同样数量的负样本； 所以训练时正负样本平衡：9,237 : 9,237。 ✅ 这样模型不会再“全猜没边”。 6）训练 MLP 来做预测 MLP(X) → 输出每个节点对在第110步连边的概率 输入：每个节点对的 640 维特征； 输出：一个 [0,1] 概率； Loss：二分类交叉熵（BCELoss）； 优化器：Adam。 🧠 白话解释： MLP 在学“什么样的历史关系轨迹会导致下一步产生连接”。 7）用真实 A110 对照预测结果 模型预测完后： 它给每对节点一个连边概率； 我们用阈值 0.5 分成「有边/无边」； 然后与真实的 $A_{110}$ 比较，得到： 指标 含义 AUC=0.8279 模型能区分哪些节点会连边、哪些不会（非常好） ACC=0.7223 有约 72% 的节点对被正确分类（相对平衡后的准确率） （1）静态图版本 你只有一张图，比如社交网络的当前关系： DeepWalk 学出 embedding； 然后用 MLP 或逻辑回归，预测那些“目前没边但 embedding 很接近”的节点对； 这些就是「潜在朋友」→ 即未来可能建立连接的边。 📘 所以静态链路预测其实是： 用当前结构的 embedding 相似度，预测将来是否可能连边。 （2）动态图版本 你有多帧图，比如第100~109步（连续的10个时间片）： 每一步都用 DeepWalk 得到 embedding； 然后把每个节点对的“10帧特征”拼起来； 喂给 MLP 预测第110步是否连边。 📘 动态版本其实是： 把「节点关系的历史轨迹」作为输入， 预测下一个时间步的关系变化。 DeepWalk 的本质： 是一个 图嵌入算法（Graph Embedding Method）， 输入图结构，输出节点的向量表示（embedding）。 也就是说： 每次运行 DeepWalk，相当于重新学习节点的 embedding； embedding 本身就是最终结果，不需要“恢复模型状态”去推理； 它不具备像神经网络那样“泛化到新数据”的功能。 所以： ✅ DeepWalk 的输出 = checkpoint ✅ DeepWalk 的 embedding = 可直接保存 / 复用的结果 ❌ 不需要保存训练中间的模型权重
论文
zy123
9月20日
0
2
0
2025-09-20
移动模型
移动模型 RWP（Random Waypoint，随机路标） 空间与时间： 在一个正方形活动区域 $[0,R]\times[0,R]$ 内，离散为 steps 个时间步。 节点运动规则： 初始位置：每个节点在区域内均匀随机选一个起点。 选目标点：从区域内均匀随机再选一个目标点（下一路标）。 速度：对该段路程，从区间 $[v_{\min}, v_{\max}]$ 均匀采样一个速度（以“每步移动的距离”计）。 运动轨迹：用直线匀速插值从当前点走到目标点，按需要的步数填充每个时间步的坐标。 停留：到达目标后，停留 pause_steps ~ U[pause_min, pause_max]（整数步）。 循环：停留结束后再选一个新的随机目标点，重复 3–5。 输出轨迹： 把每个时间步所有节点的 $(x,y)$ 位置拼成矩阵 $Y\in\mathbb{R}^{\text{steps}\times 2N}$。 邻接生成（通讯图）： 对每个时间步，任意两节点距离 $\le$ 通讯半径 comm_radius 则记为一条无向边（1），否则为 0，得到一组对称的 0/1 邻接矩阵序列。 要点：RWP 的目标点在区域内+“可停留”，因此轨迹呈 跳点—直线—驻留的节奏。 RW（Random Walk，随机游走） 空间与时间： 活动区域仍是边长 $R$ 的正方形（或你实现里也支持圆形采样作为初始点）。离散 steps。 节点运动规则： 初始位置：在活动区域内随机取一个点作为起点。 目标点：每次从一个随机边界点或区域内随机点中挑一个当目标（你的实现是 5 种可能：四条边上的均匀点或区域内随机点）。 速度：每段从 $[v_{\min}, v_{\max}]$ 均匀采样一个速度。 运动轨迹：按直线匀速插值走向目标。 无停留：到达目标立即选择下一目标继续走（不驻留）。 循环：重复 2–4。 邻接生成： 与 RWP 相同，以 comm_radius 做阈值逐步形成 0/1 邻接矩阵。 要点：RW 版本不设停留，且目标点常在边界，轨迹更“连续流动”，在边界附近来回穿梭的概率更高。 RD（Random Direction，随机方向） 空间与时间： 同样是正方形区域与离散时间。 节点运动规则： 初始位置：从边界上均匀随机选一个起点（四条边等概率）。 目标点：每段都从边界再均匀随机选一个新的边界点当目标（边界→边界）。 速度：每段速度 $[v_{\min}, v_{\max}]$ 均匀采样。 运动轨迹：直线匀速插值到目标。 停留：到达目标后停留 pause_steps ~ U[pause_min, pause_max] 步。 循环：继续从目标（边界点）出发，选下一个边界点为新目标。 邻接生成： 同上，按 comm_radius 阈值逐步构造邻接矩阵序列。 要点：RD 强化了边界—边界往返与停留，节点会频繁在边缘聚集、驻留，再切换到另一边。 Gaussian Markov Mobility（高斯-马尔科夫移动模型） 空间与时间： 在矩形区域 $[x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]$ 内，离散为多个时间步。 节点运动规则： 初始状态：每个节点随机生成位置 $(x,y)$，速度 $v \sim U(0.5, v_{\max})$，方向 $\theta \sim U(0,2\pi)$。 速度更新： $v_t = \alpha v_{t-1} + (1-\alpha)\mu_v + \sqrt{1-\alpha^2},\varepsilon_v,$ 其中 $\mu_v$ 是全局平均速度，$\varepsilon_v \sim \mathcal{N}(0,\sigma_v^2)$。 方向更新： $\theta_t = \alpha \theta_{t-1} + (1-\alpha)\mu_\theta + \sqrt{1-\alpha^2},\varepsilon_\theta,$ 其中 $\mu_\theta$ 是平均方向，$\varepsilon_\theta \sim \mathcal{N}(0,\sigma_\theta^2)$。 位置更新： $x_t = x_{t-1} + v_t \cos\theta_t, \quad y_t = y_{t-1} + v_t \sin\theta_t$ 边界处理：若节点越界，则进行反射，即位置镜像回区域内，同时方向在对应维度取反。 循环：重复步骤 2–5，生成连续轨迹。 邻接生成： 同前，设定通信半径 comm_radius，每个时间步任意两节点距离 ≤ 半径则连边，得到动态邻接矩阵序列。 要点： 参数 $\alpha$ 决定轨迹的平滑度/惯性： $\alpha \to 1$：路径接近直线，有明显惯性； $\alpha \to 0$：路径接近随机游走，更“抖动”。 和 RWP / RW / RD 不同，这里没有“目标点”概念，节点轨迹完全由马尔科夫更新的速度与方向决定，生成的运动更自然连续。 维度 RWP（随机路标） RW（随机游走，你实现：边界/内点混合目标、无停留） RD（随机方向，你实现：边界→边界+停留） GMM（高斯-马尔科夫） 空间密度 中心更密集（运动段偏向中心），若有停留：总体=中心偏移 + 均匀停留的混合 经典“各向同性反射随机游走”→近似均匀；但你的实现中目标多在边界，会带来轻微“边界增密” 边界显著增密（目标与停留都在边界，停留时间把概率质量“挂”在边缘） 近似均匀（无目标点偏好、速度/方向马尔科夫更新 + 反射），边界处可能有很弱的反射效应 速度（时间加权） 若每段速度 ~ U[v_min, v_max]：时间加权后的稳态速度分布偏向慢速（慢速段逗留时间更长 → 采样更容易采到），称“速度衰减/偏置” 同 RWP 的现象（段速均匀抽样 + 时间加权 → 偏慢） 同 RWP；另外停留会拉高“0 速度”的占比 受 α 与噪声控制，接近截断的高斯/稳态马尔科夫分布；无“路标段速”偏置 运动连续性 “跳点—直线—停留”—再跳点，方向变化较大 无停留、持续移动，方向由目标决定（混合边界/内点），变化连贯 “边界—直线—边界—停留”，方向常大幅改变；停留让轨迹呈块状 最平滑（速度/方向自相关），拐弯更自然 节点度/连边分布（给定 comm_radius） 中心密度更高 → 中心平均度更大，边缘更稀疏；有停留则在路标点附近形成“团” 近似均匀（你的实现可能边界稍高）；总体度分布较均衡 边界平均度更高（节点停在边上形成热点），内部相对稀疏 近似均匀；由于轨迹平滑，同伴保持时间更长，度变化更缓 链路时长（LET）/SNR波动 停留时链路更稳定；运动段因频繁“折返”方向，LET 方差较大 持续移动且无停留→链路更易“断续”，LET 略短、波动更频繁 停留导致边界链路长时存在，离开边界后链路更快变化，两极分化 速度/方向相关性高 → 链路更平稳、LET 较长；SNR 梯度/方差更小 相遇/再相遇（contact / inter-contact） 中心高密 → 相遇更频繁；停留会带来重入热点 近似均匀；若边界目标占比高 → 边界再相遇概率升高 边界热点相遇/再相遇概率高；内部穿越时短暂接触 平滑惯性 → 更连续的相遇时段、再相遇概率↑（沿相近方向“并走”的时间更长） 链路预测效果： RWP：有停留 → 形成稳定链路，便于预测。中心偏置 → 形成热点区域，链路模式较明显。 RW：持续移动，没有停留 → 链路变化更快，能训练出短时预测能力。效果稍差 RD：节点停留在边界时，链路超稳定 → 预测很容易。 GMM：轨迹平滑，链路断开/形成有更明显的惯性。LET 分布更长，预测任务难度适中（比 RW 稳定，比 RWP 更连续）。最贴近“真实连续移动”的模型。
论文
zy123
9月20日
0
5
0
2025-08-29
草稿
非常好的问题 💡 你抓住了 FMI 的一个关键弱点：它对类不平衡（尤其是“大簇 vs 小簇”）敏感。 我给你一个非常直观的小例子（带数字），让你一步就理解为什么大簇会“主导”FMI 的结果。 🧩 一、背景 FMI 衡量“延迟聚类是否正确识别真实的同簇节点对”。 它在计算时看的是： $\text{Precision} = \frac{TP}{TP + FP}, \quad \text{Recall} = \frac{TP}{TP + FN}$ 其中 TP、FP、FN 都是在节点对级别计算的。 而节点对的数量和簇大小密切相关！ 一个簇有 $n$ 个节点，它内部的节点对数量是： n(n−1)2\frac{n(n-1)}{2} 也就是说，大簇里的“同簇节点对”远远多于小簇。 所以 大簇错误一点点，FMI 会掉很多；小簇错一大片，FMI 变化反而不大。 🧮 二、具体例子：两种簇结构 假设我们有 10 个节点： 簇类型 节点 簇大小 内部节点对数 大簇 A, B, C, D, E, F, G, H 8 $\frac{8×7}{2} = 28$ 小簇 I, J 2 $\frac{2×1}{2} = 1$ 总同簇节点对 — — 29 对 可见： 👉 只有 1/29 ≈ 3.4% 的“真实同簇节点对”来自小簇。 🚀 三、聚类情况对比 我们比较两种延迟聚类结果： ✅ 情况 1：只错了小簇 延迟聚类： (A–H 在一起)，(I)、(J) 也就是： 大簇 8 个节点保持完美； 小簇被拆散成两个单独节点。 统计： TP（正确识别的同簇节点对）= 28（全部来自大簇） FN（漏掉的同簇节点对）= 1（小簇 I–J） FP（错误合并的节点对）= 0 计算： $Precision = 28/(28+0)=1.0, \quad Recall = 28/(28+1)=0.9655$$FMI = \sqrt{1.0 × 0.9655} ≈ 0.9826$ → FMI ≈ 0.98，非常高！ 尽管你其实完全错了小簇。 ❌ 情况 2：大簇错了一点 延迟聚类： (A–E 在一起)，(F–H)、(I,J) 也就是： 大簇被拆成两部分； 小簇正确。 统计： 大簇内部正确识别的节点对： A–E：$10$ 对 F–H：$3$ 对 实际大簇原有 $28$ 对 → 漏掉 $15$ 对 TP = 10 + 3 + 1(小簇)=14 FN = 15（漏掉的大簇内部关系） FP = 0（没有错误合并） 计算： $Precision = 14/(14+0)=1.0, \quad Recall = 14/(14+15)=0.4827$$FMI = \sqrt{1.0 × 0.4827} ≈ 0.694$ → FMI ≈ 0.69，骤降！ 虽然你只是把大簇分裂了一点点。 📊 四、比较结果 情况 错误类型 FMI 实际错误影响 ✅ 情况 1 小簇完全错 0.98 几乎没影响 ❌ 情况 2 大簇拆错一半 0.69 FMI 急剧下降 💡 五、结论直觉化 观察 含义 大簇内部有很多节点对（比如 28 对） → 错一部分会影响大量 TP/FN 计数 小簇内部节点对极少（1 对） → 即使错了也几乎不影响 FMI FMI 是基于“所有节点对”的全局比例 → 大簇权重大，小簇权重极小 所以我们说： FMI 对类不平衡（簇大小差异）敏感。 FMI 的高低主要反映“大簇聚类的一致性”，小簇的错误被“淹没”。 ✅ 六、一句话总结 在 FMI 中，大簇内部节点对的数量多得多， 导致它们在计算中权重更大。 因此 FMI 更能反映“大簇聚类的好坏”， 而忽略“小簇是否聚错”。 是否希望我帮你扩展这个例子写成一段 Python 演示代码？ 我可以打印出每种情况下的 TP/FP/FN/FMI，让你直接运行看到这两个场景 FMI 变化的数值差异。
论文
zy123
8月29日
0
6
0
2025-06-17
强化学习
强化学习 Q-learning 核心更新公式 $$ \boxed{Q(s,a) \gets Q(s,a) + \alpha\left[r + \gamma\,\max_{a'}Q(s',a') - Q(s,a)\right]} $$ - $s$：当前状态 - $a$：当前动作 - $r$：执行 $a$ 后获得的即时奖励 - $s'$：执行后到达的新状态 - $\alpha\in(0,1]$：学习率，决定“这次新信息”对旧值的影响力度 - $\gamma\in[0,1)$：折扣因子，衡量对“后续奖励”的重视程度 - $\max_{a'}Q(s',a')$：新状态下可选动作的最大估值，表示“后续能拿到的最大预期回报” 一般示例 环境设定 状态集合：${S_1, S_2}$ 动作集合：${a_1, a_2}$ 转移与奖励： 在 $S_1$ 选 $a_1$ → 获得 $r=5$，转到 $S_2$ 在 $S_1$ 选 $a_2$ → 获得 $r=0$，转到 $S_2$ 在 $S_2$ 选 $a_1$ → 获得 $r=0$，转到 $S_1$ 在 $S_2$ 选 $a_2$ → 获得 $r=1$，转到 $S_1$ 超参数：$\alpha=0.5$，$\gamma=0.9$ 初始化：所有 $Q(s,a)=0$ 在 Q-Learning 里，智能体并不是“纯随机”地走，也不是“一开始就全凭 Q 表拿最高值”——而是常用一种叫 $\epsilon$-greedy 的策略来平衡： 探索（Exploration）：以概率 $\epsilon$（比如 10%）随机选一个动作，帮助智能体发现还没试过、可能更优的路径； 利用（Exploitation）：以概率 $1-\epsilon$（比如 90%）选当前状态下 Q 值最高的动作，利用已有经验最大化回报。 下面按序进行 3 步“试—错”更新，并在表格中展示每一步后的 $Q$ 值。 步骤 状态 $s$ 动作 $a$ 奖励 $r$ 到达 $s'$ $\max_{a'}Q(s',a')$ 更新后 $Q(s,a)$ 当前 Q 表 初始 — — — — — — $Q(S_1,a_1)=0,;Q(S_1,a_2)=0$ $Q(S_2,a_1)=0,;Q(S_2,a_2)=0$ 1 $S_1$ $a_1$ 5 $S_2$ 0 $0+0.5,(5+0-0)=2.5$ $Q(S_1,a_1)=2.5,;Q(S_1,a_2)=0$ $Q(S_2,a_1)=0,;Q(S_2,a_2)=0$ 2 $S_2$ $a_2$ 1 $S_1$ $到达S_1状态后选择最优动作：$$\max{2.5,0}=2.5$ $0+0.5,(1+0.9\cdot2.5-0)=1.625$ $Q(S_1,a_1)=2.5,;Q(S_1,a_2)=0$ $Q(S_2,a_1)=0,;Q(S_2,a_2)=1.625$ 3 $S_1$ $a_1$ 5 $S_2$ $\max{0,1.625}=1.625$ $2.5+0.5,(5+0.9\cdot1.625-2.5)\approx4.481$ $Q(S_1,a_1)\approx4.481,;Q(S_1,a_2)=0$ $Q(S_2,a_1)=0,;Q(S_2,a_2)=1.625$ 第1步：从 $S_1$ 选 $a_1$，立即回报5，更新后 $Q(S_1,a_1)=2.5$。 第2步：从 $S_2$ 选 $a_2$，回报1，加上对 $S_1$ 后续最优值的 $0.9$ 折扣，得到 $1+0.9\times2.5=3.25$，更新后 $Q(S_2,a_2)=1.625$。 第3步：再一次在 $S_1$ 选 $a_1$，这次考虑了 $S_2$ 的最新估值，最终把 $Q(S_1,a_1)$ 提升到约 4.481。 通过这样一步步的“试—错 + 贝尔曼更新”，Q-Learning 能不断逼近最优 $Q^*(s,a)$，从而让智能体在每个状态都学会选出长期回报最高的动作。 训练结束后，表里每个状态 $s$ 下各动作的 Q 值都相对准确了，我们就可以直接读表来决策： $$ \pi(s) = \arg\max_a Q(s,a) $$ 即“在状态 $s$ 时，选 Q 值最高的动作”。 状态 \ 动作 $a_1$ $a_2$ $S_1$ 4.481 0 $S_2$ 0 1.625 DQN 核心思想：用深度神经网络近似 Q 函数来取代表格，在高维输入上直接做 Q-learning，并通过 经验回放（写进缓冲区 + 随机抽样训练”） + 目标网络（Target Network） 两个稳定化技巧，使 时序差分（TD ）学习在非线性函数逼近下仍能收敛。 TD 学习 = 用“即时奖励 + 折扣后的未来估值”作为目标，通过 TD 误差持续修正当前估计。 训练过程 1. 初始化 主网络（Online Network） 定义一个 Q 网络 $Q(s,a;\theta)$，随机初始化参数 $\theta$。 目标网络（Target Network） 复制主网络参数，令 $\theta^- \leftarrow \theta$。 目标网络用于计算贝尔曼目标值，短期内保持不变。 经验回放缓冲区（Replay Buffer） 创建一个固定容量的队列 $\mathcal{D}$，用于存储交互样本 $(s,a,r,s')$。 超参数设置 学习率 $\eta$ 折扣因子 $\gamma$ ε-greedy 探索率 $\epsilon$（初始值） 最小训练样本数阈值 $N_{\min}$ 每次训练的小批量大小 $B$ 目标网络同步频率 $C$（梯度更新次数间隔） 2. 与环境交互并存储经验 在每个时间步 $t$： 动作选择 $$ a_t = \begin{cases} \text{随机动作} & \text{以概率 }\epsilon,\ \arg\max_a Q(s_t,a;\theta) & \text{以概率 }1-\epsilon. \end{cases} $$ 环境反馈 执行动作 $a_t$，得到奖励 $r_t$ 和下一个状态 $s_{t+1}$。 （需预先定义奖励函数） 存入缓冲区 将元组 $(s_t, a_t, r_t, s_{t+1})$ 存入 Replay Buffer $\mathcal{D}$。 如果 $\mathcal{D}$ 已满，则丢弃最早的样本。 3. 批量随机采样并训练 当缓冲区样本数 $\ge N_{\min}$ 时，每隔一次或多次环境交互，就进行一次训练更新： 随机抽取小批量 从 $\mathcal{D}$ 中随机采样 $B$ 条过往经验： $$ {(s_i, a_i, r_i, s'i)}{i=1}^B $$ 计算贝尔曼目标 对每条样本，用目标网络 $\theta^-$ 计算： $$ y_i = r_i + \gamma \max_{a'}Q(s'_i, a'; \theta^-) $$ 算的是：当前获得的即时奖励 $r_i$，加上“到了下一个状态后，做最优动作所能拿到的最大预期回报” 预测当前 Q 值 将当前状态-动作对丢给主网络 $\theta$，得到预测值： $$ \hat Q_i = Q(s_i, a_i;\theta) $$ 算的是：在当前状态 $s_i$、选了样本里那个动作 $a_i$ 时，网络现在估计的价值 构造损失函数 均方误差（MSE）损失： $$ L(\theta) = \frac{1}{B}\sum_{i=1}^B\bigl(y_i - \hat Q_i\bigr)^2 $$ 梯度下降更新主网络 $$ \theta \gets \theta - \eta \nabla_\theta L(\theta) $$ 4. 同步/软更新目标网络 硬同步（Fixed Target）： 每做 $C$ 次梯度更新，就执行 $$ \theta^- \gets \theta $$ （可选）软更新： 用小步长 $\tau\ll1$ 平滑跟踪： $$ \theta^- \gets \tau \theta + (1-\tau) \theta^-. $$ 5. 重复训练直至收敛 重复步骤 2-4 直至满足终止条件（如最大回合数或性能指标）。 训练过程中可逐步衰减 $\epsilon$（ε-greedy），从更多探索过渡到更多利用。 示例 假设设定 动作空间：两个动作 ${a_1,a_2}$。 状态向量维度：2 维，记作 $s=(s_1,s_2)$。 目标网络结构（极简线性网络）： $$ Q(s;\theta^-) = W^-s + b^-, $$ $W^-$ 是 $2\times2$ 的权重矩阵 （行数为动作数，列数为状态向量维数） $b^-$ 是长度 2 的偏置向量 网络参数（假定已初始化并被冻结）： $$ W^- = \begin{pmatrix} 0.5 & -0.2\ 0.1 & ;0.3 \end{pmatrix},\quad b^- = \begin{pmatrix}0.1\-0.1\end{pmatrix}. $$ 折扣因子 $\gamma=0.9$。 样本数据 假设我们抽到的一条经验是 $$ (s_i,a_i,r_i,s'_i) = \bigl((0.0,\;1.0),\;a_1,\;2,\;(1.5,\,-0.5)\bigr). $$ 当前状态 $s_i=(0.0,1.0)$，当时选了动作 $a_1$ 并得到奖励 $r_i=2$。 到达新状态 $s'_i=(1.5,-0.5)$。 计算过程 前向计算目标网络输出 $$ Q(s'_i;\theta^-) = W^-,s'_i + b^- \begin{pmatrix} 0.5 & -0.2\ 0.1 & ;0.3 \end{pmatrix} \begin{pmatrix}1.5\-0.5\end{pmatrix} + \begin{pmatrix}0.1\-0.1\end{pmatrix} \begin{pmatrix} 0.5\cdot1.5 + (-0.2)\cdot(-0.5) + 0.1 \[4pt] 0.1\cdot1.5 + ;0.3\cdot(-0.5) - 0.1 \end{pmatrix} \begin{pmatrix} 0.75 + 0.10 + 0.1 \[3pt] 0.15 - 0.15 - 0.1 \end{pmatrix} \begin{pmatrix} 0.95 \[3pt] -0.10 \end{pmatrix}. $$ 因此， $$ Q(s'_i,a_1;\theta^-)=0.95,\quad Q(s'_i,a_2;\theta^-)= -0.10. $$ 取最大值 $$ \max_{a'}Q(s'_i,a';\theta^-) = \max{0.95,,-0.10} = 0.95. $$ 计算目标 $y_i$ $$ y_i = r_i + \gamma \times 0.95 = 2 + 0.9 \times 0.95 = 2 + 0.855 = 2.855. $$ 这样，我们就得到了 DQN 中训练主网络时的"伪标签" $y_i=2.855$，后续会用它与主网络预测值 $Q(s_i,a_i;\theta)$ 计算均方误差，进而更新 $\theta$。 改进DQN： 一、构造 n-step Transition 维护一个长度为 n 的滑动队列 每步交互（状态 → 动作 → 奖励 → 新状态）后，都向队列里添加这条"单步经验"。 当队列中积累到 n 条经验时，就可以合并成一条"n-step transition"了。 合并过程（一步一步累加） 起始状态：取队列里第 1 条记录中的状态 $s_t$ 起始动作：取第 1 条记录中的动作 $a_t$ 累积奖励：把队列中前 n 条经验的即时奖励按折扣因子 $\gamma$ 一步步加权累加： $$ G_t^{(n)} = r_t + \gamma,r_{t+1} + \gamma^2,r_{t+2} + \cdots + \gamma^{n-1}r_{t+n-1} $$ 形成一条新样本 最终你得到一条合并后的样本： $$ \bigl(s_t,;a_t,;G_t^{(n)},;s_{t+n},;\text{done}_{t+n}\bigr) $$ 然后把它存入主 Replay Buffer。 接着，把滑动队列的最早一条经验丢掉，让它向前滑一格，继续接收下一步新经验。 二、批量随机采样与训练 随机抽取 n-step 样本 训练时，不管它是来自哪一段轨迹，都从 Replay Buffer 里随机挑出一批已经合好的 n-step transition。 每条样本就封装了"从 $s_t$ 出发，执行 $a_t$，经历 n 步后所累积的奖励加 bootstrap"以及到达的末状态。 计算训练目标 对于每条抽出的 n-step 样本 $(s_t,a_t,G_t^{(n)},s_{t+n},\text{done}_{t+n})$， 如果 $\text{done}{t+n}=\text{False}$，则 $$ y = G_t^{(n)} + \gamma^n,\max{a'}Q(s_{t+n},a';\theta^-); $$ 如果 $\text{done}_{t+n}=\text{True}$，则 $$ y = G_t^{(n)}. $$ 主网络给出预测 把样本中的起始状态-动作对 $(s_t,a_t)$ 丢给在线的 Q 网络，得到当前估计的 $\hat{Q}(s_t,a_t)$。 更新网络 用"目标值 $y$"和"预测值 $\hat{Q}$"之间的平方差，构造损失函数。 对损失做梯度下降，调整在线网络参数，使得它的预测越来越贴近那条合并后的真实回报。 VDN 核心思路：将团队 Q 函数写成各智能体局部 Q 的线性和 $Q_{tot}=\sum_{i=1}^{N}\tilde{Q}_i$，在训练时用全局奖励反传梯度，在执行时各智能体独立贪婪决策。 CTDE 指 Centralized Training, Decentralized Execution —— 在训练阶段使用集中式的信息或梯度（可以看到全局状态、联合奖励、各智能体的隐藏变量等）来稳定、加速学习；而在执行阶段，每个智能体只依赖自身可获得的局部观测来独立决策。 采用 CTDE 的好处： 部署高效、可扩展：运行时每个体只需本地观测，无需昂贵通信和同步，适合大规模或通信受限场景。 降低非平稳性：每个智能体看到的“环境”里不再包含 其他正在同时更新的智能体——因为所有参数其实在同一次反向传播里被一起更新，整体策略变化保持同步；对单个智能体而言，环境动态就不会呈现出随机漂移。 避免“懒惰智能体”：只要某个行动对团队回报有正贡献，它在梯度里就能拿到正向信号，不会因为某个体率先学到高收益行为而使其他个体“无所事事”。 核心公式与训练方法 值分解假设 $$ Q\bigl((h_1,\dots,h_d),(a_1,\dots,a_d)\bigr);\approx;\sum_{i=1}^{d},\tilde{Q}_i(h_i,a_i) $$ 其中 $h_i$ 为第 $i$ 个智能体的历史观测，$a_i$ 为其动作。每个 $\tilde{Q}_i$ 只使用局部信息；训练时通过对联合 $Q$ 的 TD 误差求梯度，再"顺着求和"回传到各 $\tilde{Q}_i$ 。这样既避免了为各智能体手工设计奖励，又天然解决了联合动作空间呈指数爆炸的问题。 Q-learning 更新 $$ Q_{t+1}(s_t,a_t);=;(1-\eta_t),Q_{t}(s_t,a_t);+;\eta_t\bigl[r_t+\gamma\max_{a}Q_{t}(s_{t+1},a)\bigr] $$ 论文沿用经典 DQN 的 Q-learning 目标，对 联合 Q 值 计算 TD 误差，然后按上式更新；全局奖励 $r_t$ 会在反向传播时自动分摊到各 $\tilde{Q}_i$ 。 训练过程 使用LSTM:让智能体在「只有局部、瞬时观测」的环境中记住并利用过去若干步的信息。 1. 初始化 组件 说明 在线网络 为每个智能体 $i=1\ldots d$ 建立局部 $Q$ 网络 $\widetilde Q_i(h^i,a^i;\theta_i)$。最后一层是 值分解层：把所有 $\widetilde Q_i$ 相加得到联合 $Q=\sum_i\widetilde Q_i$ 目标网络 为每个体复制参数：$\theta_i^- \leftarrow \theta_i$，用于计算贝尔曼目标。 经验回放缓冲区 存储元组 $(h_t, \mathbf a_t, r_t, o_{t+1}) \rightarrow \mathcal D$，其中 $\mathbf a_t=(a_t^1,\dots,a_t^d)$。 超参数 Adam 学习率 $1\times10^{-4}$，折扣 $\gamma$，BPTT 截断长度 8，Eligibility trace $\lambda=0.9$ ；小批量 $B$、目标同步周期 $C$、$\varepsilon$-greedy 初始值等。 网络骨架：Linear (32) → ReLU → LSTM (32) → Dueling (Value + Advantage) 头产生 $\widetilde Q_i$ 。 2. 与环境交互并存储经验 局部隐藏状态更新（获得 $h_t^i$） 采样观测 $o_t^i \in \mathbb R^{3\times5\times5}$（RGB × 5 × 5 视野） 线性嵌入 + ReLU $x_t^i = \mathrm{ReLU}(W_o,\text{vec}(o_t^i)+b_o),; W_o!\in!\mathbb R^{32\times75}$ 递归更新 LSTM $h_t^i,c_t^i = \text{LSTM}{32}(x_t^i,;h{t-1}^i,c_{t-1}^i)$ （初始 $h_0^i,c_0^i$ 置零；执行期只用本体状态即可） 动作选择（分散执行） $$ a_t^i=\begin{cases} \text{随机动作}, & \text{概率 } \varepsilon,\ \arg\max_{a}\widetilde Q_i(h_t^i,a;\theta_i), & 1-\varepsilon. \end{cases} $$ 环境反馈：执行联合动作 $\mathbf a_t$，获得单条 团队奖励 $r_t$ 以及下一组局部观测 $o_{t+1}^i$。 重要：此处不要直接把 $h_{t+1}^i$ 写入回放池，而是存下 $(h_t^i, a_t^i, r_t, o_{t+1}^i)$。 之后在训练阶段再用同样的“Step 0” 方式，离线地把 $o_{t+1}^i\rightarrow h_{t+1}^i$。 这样可避免把梯度依赖塞进经验池。 写入回放池：$(h_t, \mathbf a_t, r_t, o_{t+1}) \rightarrow \mathcal D$。 3. 批量随机采样并联合训练 对缓冲区达到阈值后，每次更新步骤： 采样 $B$ 条长度为 $L$ 的序列。 假设抽到第 $k$ 条序列的第一个索引是 $t$。 依次取出连续的 $(h_{t+j}, a_{t+j}, r_{t+j}, o_{t+j+1}), j=0, \ldots, L-1$。 先用存储的 $o_{t+j+1}$ 离线重放"Step 0"得到 $h_{t+j+1}$，这样序列就拥有 $(h_{t+j}, h_{t+j+1})$ 前向计算 $$ \hat Q_i^{(k)} = \widetilde Q_i(h^{i,(k)}_t,a^{i,(k)}t;\theta_i), \quad \hat Q^{(k)}=\sum{i}\hat Q_i^{(k)} . $$ 贝尔曼目标（用目标网络） $$ y^{(k)} = r^{(k)} + \gamma \sum_{i}\max_{a}\widetilde Q_i(h^{i,(k)}_{t+1},a;\theta_i^-). $$ 损失 $$ L=\frac1B\sum_{k=1}^{B}\bigl(y^{(k)}-\hat Q^{(k)}\bigr)^2 . $$ 梯度反传（自动信用分配） 因为 $\hat Q=\sum_i\widetilde Q_i$，对每个 $\widetilde Q_i$ 的梯度系数恒为 1， 整个 团队 TD 误差 直接回流到各体网络，无需个体奖励设计 。 参数更新：$\theta_i \leftarrow \theta_i-\eta\nabla_{\theta_i}L$。 4. 同步 / 软更新目标网络 硬同步：每 $C$ 次梯度更新后执行 $\theta_i^- \leftarrow \theta_i$。 软更新：可选 $\theta_i^- \leftarrow \tau\theta_i+(1-\tau)\theta_i^-$。 5. 重复直到收敛 持续循环步骤 2–4，逐步衰减 $\varepsilon$。 训练完成后，每个体只需本地 $\widetilde Q_i$ 就能独立决策，与中心最大化 $\sum_i\widetilde Q_i$ 等价 。
论文
zy123
6月17日
0
4
0
2025-05-05
动态图神经网络
动态图神经网络 如何对GAT的权重（$W$）和注意力参数（$a$）进行增量更新（邻居偶尔变化） 1. 核心思想 局部更新：邻居变化的节点及其直接邻域的权重和注意力参数需要调整，其他部分冻结。 梯度隔离：反向传播时，仅计算受影响节点的梯度，避免全局参数震荡。 2. 数学实现步骤 (1) 识别受影响的节点 设邻居变化后的新邻接矩阵为 $\tilde{A}$，原邻接矩阵为 $A$，受影响节点集合 $\mathcal{V}_{\text{affected}}$ 包括： 新增或删除边的两端节点（直接受影响）。 这些节点的1-hop邻居（间接受影响，根据GAT层数决定）。 (2) 损失函数局部化 仅对 $\mathcal{V}_{\text{affected}}$ 中的节点计算损失： $$ \mathcal{L}_{\text{incremental}} = \sum_{i \in \mathcal{V}_{\text{affected}}} \ell(y_i, \hat{y}_i) $$ 其中 $\ell$ 为交叉熵损失，$y_i$ 为标签，$\hat{y}_i$ 为模型输出。 (3) 梯度计算与参数更新 梯度掩码： 反向传播时，非受影响节点的梯度强制置零： $$ \nabla_{W,a} \mathcal{L}{\text{incremental}} = \left{ \begin{array}{ll} \nabla{W,a} \ell(y_i, \hat{y}i) & \text{if } i \in \mathcal{V}{\text{affected}} \ 0 & \text{otherwise} \end{array} \right. $$ 参数更新： 使用优化器（如Adam）仅更新有梯度的参数： $$ W \leftarrow W - \eta \nabla_W \mathcal{L}{\text{incremental}}, \quad a \leftarrow a - \eta \nabla_a \mathcal{L}{\text{incremental}} $$ 其中 $\eta$ 为较小的学习率（防止过拟合）。 (4) 注意力权重的动态适应 GAT的注意力机制会自动适应新邻居： $$ \alpha_{ij} = \text{softmax}\left(\text{LeakyReLU}\left(a^T [W h_i \| W h_j]\right)\right) $$ 由于 $W$ 和 $a$ 已局部更新，新邻居 $j \in \tilde{\mathcal{N}}(i)$ 的权重 $\alpha_{ij}$ 会重新计算。 3. 适用场景 低频变化：如社交网络每天新增少量边、论文引用网络月度更新。 局部变化：每次变化仅影响图中少量节点（<10%）。 若邻居高频变化（如秒级更新），需改用动态GNN（如TGAT）或时间序列建模。 EvolveGCN EvolveGCN-H 1. EvolveGCN-H核心思想 EvolveGCN-H 通过 GRU（门控循环单元） 动态更新 GCN 每一层的权重矩阵 $W_t^{(l)}$，将权重矩阵视为 GRU 的 隐藏状态，并利用当前时间步的 节点嵌入（特征） 作为输入来驱动演化。 关键特点： 输入依赖：利用节点嵌入 $H_t^{(l)}$ 指导权重更新。 时序建模：通过 GRU 隐式捕捉参数演化的长期依赖。 2. 动态更新流程（以第 $l$ 层为例） 输入： 当前节点嵌入矩阵 $H_t^{(l)} \in \mathbb{R}^{n \times d}$： 上一时间步的权重矩阵 $W_{t-1}^{(l)} \in \mathbb{R}^{d \times d'}$： 邻接矩阵 $A_t \in \mathbb{R}^{n \times n}$： 输出： 更新后的权重矩阵 $W_t^{(l)} \in \mathbb{R}^{d \times d'}$。 下一层节点嵌入 $H_t^{(l+1)} \in \mathbb{R}^{n \times d'}$。 3. 动态更新示意图 Time Step t-1 Time Step t +-------------------+ +-------------------+ | Weight Matrix | | Weight Matrix | | W_{t-1}^{(l)} | --(GRU更新)--> | W_t^{(l)} | +-------------------+ +-------------------+ ^ ^ | | +-------------------+ +-------------------+ | Node Embeddings | | Node Embeddings | | H_t^{(l)} | --(GCN计算)--> | H_t^{(l+1)} | +-------------------+ +-------------------+ ^ ^ | | +-------------------+ +-------------------+ | 邻接矩阵 A_t | | 邻接矩阵 A_{t+1} | | (显式输入) | | (下一时间步输入) | +-------------------+ +-------------------+ $$ \begin{align*} W_t^{(l)} &
论文
zy123
5月5日
0
17
0
1
2
下一页
