​​【信息科学与工程学】【数据科学】数据科学领域 第十二篇 大数据主要算法08

大数据算法531-540编号算法名称算法类型算法/模型名称算法逐步推理思考的数学方程式/核心逻辑关联知识复杂度数据类型应用场景和应用方法531局部线性嵌入​无监督学习局部线性嵌入1. 算法目标保持数据局部线性结构将高维数据映射到低维空间。2. 局部重建权重计算对每个数据点x_i找到其k个最近邻N(i)。最小化重建误差min_W Σ_ix_i - Σ{j∈N(i)} W{ij} x_j²约束Σ{j∈N(i)} W{ij}1。通过求解局部协方差矩阵C{jk}(x_i-x_j)ᵀ(x_i-x_k)然后解线性方程组Σ_k C{jk} W_{ik}1得到权重。3. 低维嵌入计算固定权重W寻找低维表示{y_i}最小化Φ(Y)Σ_i532拉普拉斯特征映射​无监督学习拉普拉斯特征映射1. 构建邻接图用k近邻或ε邻域构建图边权重W_{ij}exp(-x_i-x_j²/t)或简单二值权重。2. 计算拉普拉斯矩阵度矩阵D为对角阵D{ii}Σ_j W{ij}。拉普拉斯矩阵LD-W。3. 广义特征值问题求解LfλDf的广义特征值问题。取最小的d个非零特征值对应的特征向量f₁,...,f_d。4. 低维嵌入第i个样本的低维坐标为(y_i1,...,y_id)(f₁(i),...,f_d(i))。5. 数学原理最小化目标函数Σ{i,j} W{ij}533高斯混合模型​无监督学习高斯混合模型1. 模型定义p(xθ)Σ_{k1}^K π_k N(xμ_k,Σ_k)其中π_k为混合系数Σ_k π_k1N为高斯分布。2. 隐变量引入隐变量zz_k∈{0,1}Σ_k z_k1表示样本属于哪个分量。完全数据似然p(x,zθ)Π_k π_k^{z_k} N(xμ_k,Σ_k)^{z_k}。3. EM算法E步计算后验γ(z_{nk})p(z_k1534谱聚类​无监督学习谱聚类1. 构建相似度矩阵计算样本间相似度S_{ij}exp(-x_i-x_j²/2σ²)或k近邻。2. 构建拉普拉斯矩阵常用对称归一化拉普拉斯L{sym}I-D^{-1/2}SD^{-1/2}或随机游走归一化L{rw}I-D^{-1}S。3. 特征分解计算L的前k个最小特征值对应的特征向量u₁,...,u_k构成矩阵U∈ℝ^{n×k}。4. 行归一化将U的行归一化得到矩阵Tt{ij}u{ij}/(Σ_j u{ij}²)^{1/2}。5. K-means聚类对T的行向量用k-means聚类得到簇划分C₁,...,C_k。6. 数学原理谱聚类最小化图割问题。RatioCut目标min{A₁,...,A_k} Σ{i1}^k cut(A_i,Āi)/535主成分分析​无监督学习主成分分析1. 数据中心化x_i x_i - μ其中μ1/n Σ_i x_i。2. 协方差矩阵C1/n Σ_i x_i x_iᵀ 1/n XᵀX假设X每行一个样本。3. 特征值分解Cv_i λ_i v_iλ₁≥λ₂≥...≥λ_d。特征向量v_i为主成分方向。4. 降维取前k个特征向量构成投影矩阵W[v₁,...,v_k]∈ℝ^{d×k}。降维后数据YXW∈ℝ^{n×k}。5. 最大方差解释PCA最大化投影后方差max_W tr(WᵀCW) s.t. WᵀWI。解为C的前k个特征向量。6. 最小重建误差最小化重建误差X-XWWᵀ_F²同样得到相同解。7. 奇异值分解XUΣVᵀ则主成分V的前k列得分矩阵UΣ的前k列。536独立成分分析​无监督学习独立成分分析1. 问题模型观测信号xAs其中s为独立源信号A为混合矩阵。目标找到分离矩阵W使yWx近似s。2. 预处理中心化x白化zVx使E[zzᵀ]IV通常为协方差矩阵的特征值分解得到。3. 独立性度量使用负熵近似J(y)∝[E(G(y))-E(G(v))]²其中v为标准高斯G为非二次函数如tanh。4. FastICA算法- 初始化权重向量w。- 更新w←E{zg(wᵀz)}-E{g(wᵀz)}w其中g为G的导数。- 正交化w←w/w若多个分量用Gram-Schmidt正交化。- 重复直到收敛。5. 数学原理最大化非高斯性作为独立性度量。中心极限定理表明混合信号更高斯分离信号应非高斯。537t-分布随机邻域嵌入​无监督学习t-SNE1. 高维相似度对高维数据点x_i,x_j计算条件概率p_{j|i}exp(-x_i-x_j²/2σ_i²)/Σ_{k≠i}exp(-538自编码器​无监督学习自编码器1. 网络结构编码器f_θ: ℝ^d→ℝ^h解码器g_φ: ℝ^h→ℝ^dhd。2. 目标函数最小化重建误差L(θ,φ)1/n Σ_ix_i-g_φ(f_θ(x_i))²。3. 编码过程h_if_θ(x_i)σ(Wx_ib)σ为激活函数。4. 解码过程x̂_ig_φ(h_i)σ(Wh_ib)。5. 正则化为防止恒等映射可加稀疏约束L_sparseΣ_j KL(ρ539深度信念网络​无监督学习深度信念网络1. 结构多层受限玻尔兹曼机堆叠。2. RBM能量函数E(v,h)-aᵀv-bᵀh-vᵀWh其中v为可见层h为隐层W为权重a,b为偏置。3. 联合概率p(v,h)exp(-E(v,h))/ZZ为配分函数。4. 条件概率p(h_j1|v)σ(b_jΣ_i W{ij}v_i)p(v_i1|h)σ(a_iΣ_j W{ij}h_j)。5. 对比散度训练- 输入v⁽⁰⁾计算h⁽⁰⁾~p(h|v⁽⁰⁾)。- 采样h⁽⁰⁾计算v⁽¹⁾~p(v|h⁽⁰⁾)。- 计算h⁽¹⁾~p(h|v⁽¹⁾)。- 更新参数ΔWη(v⁽⁰⁾h⁽⁰⁾ᵀ-v⁽¹⁾h⁽¹⁾ᵀ)类似更新a,b。6. 逐层训练训练第一层RBM后其隐层作为下一层RBM的可见层重复。最后用反向传播微调。生成模型、对比散度、RBMO(n * 2^{vh}) 精确计算CD近似二值数据场景图像生成、特征学习、协同过滤。方法逐层无监督预训练有监督微调。540生成对抗网络​无监督学习生成对抗网络1. 博弈框架生成器G(z;θ_g)映射噪声z到数据空间判别器D(x;θ_d)输出x为真实数据的概率。2. 目标函数min_G max_D V(D,G)E{x~p_data}[log D(x)]E{z~p_z}[log(1-D(G(z)))]。3. 判别器更新最大化V梯度上升∇{θ_d} 1/m Σ_i [log D(x⁽ⁱ⁾)log(1-D(G(z⁽ⁱ⁾)))]。4. 生成器更新最小化log(1-D(G(z)))梯度下降∇{θ_g} 1/m Σ_i log(1-D(G(z⁽ⁱ⁾)))。实践中用最大化log D(G(z))避免梯度消失。5. 最优解当p_gp_data时达到纳什均衡此时D(x)1/2。6. 损失函数生成器损失L_G-E{z~p_z}[log D(G(z))]判别器损失L_D-E{x~p_data}[log D(x)]-E_{z~p_z}[log(1-D(G(z)))]。7. 训练技巧使用Adam优化器标签平滑小批量判别等。生成模型、博弈论、最小最大博弈O(n * (d_g d_d))图像、文本等场景图像生成、数据增强、风格迁移。方法生成器和判别器对抗训练生成器学习数据分布。大数据算法551-560关联规则、序列模式、图模式挖掘编号算法名称算法类型算法/模型名称算法逐步推理思考的数学方程式/核心逻辑关联知识复杂度数据类型应用场景和应用方法551GCT算法​关联规则挖掘广义闭合项集树算法1. 基本思想通过构建闭合项集树来挖掘频繁闭合项集。2. 闭合项集定义项集X是闭合的当且仅当不存在X的超集Y使得support(Y) support(X)。3. 闭包运算closure(X) {i ∈ I |support(X ∪ {i}) support(X)}。闭合项集X满足closure(X) X。4. 算法步骤- 扫描数据库计算所有频繁1-项集的支持度。- 构建闭合项集树根节点为空集每个节点表示一个闭合项集。- 从根节点开始对每个节点X考虑添加一个项ii不在X中且大于X中所有项计算Y closure(X ∪ {i})。如果Y是闭合的且频繁则将Y作为X的子节点并记录支持度。- 递归构建子树。5. 剪枝利用闭合项集的性质如果一个项集不是闭合的则不需要扩展其超集。6. 数学原理所有闭合项集构成了一个完备格可以通过闭包运算生成。闭合项集、闭包运算、格结构O(2^m) 最坏m为项数事务数据场景频繁闭合项集挖掘用于压缩频繁项集表示。方法通过闭包运算构建闭合项集树避免生成大量非闭合项集。552CARMA​关联规则挖掘连续关联规则挖掘算法1. 算法目标在数据流中挖掘关联规则适应数据分布的变化。2. 滑动窗口使用时间窗口W只考虑窗口内的事务。3. 潜在频繁项集维护一个潜在频繁项集集合PL包含所有可能在未来成为频繁的项集。对每个项集X维护其支持度计数count(X)和最大可能误差max_error(X)。4. 更新策略新事务到达时更新PL中所有子项集的计数。旧事务过期时减少相应计数。同时更新max_error(X) count(X) 新事务数自X加入PL后。5. 剪枝如果一个项集X的max_error(X) min_sup * |W|则从PL中删除。6. 规则生成定期检查PL中的项集如果count(X) ≥ min_sup * |W|则输出X为频繁项集并生成规则。7. 数学公式设当前窗口大小为N最小支持度阈值s则频繁条件为count(X) ≥ sN。max_error(X) count(X) Δ其中Δ是自X加入PL后进入窗口的事务数。数据流挖掘、滑动窗口、误差边界O(PL) 每事务553WAP-Tree​序列模式挖掘Web访问模式树1. 树结构WAP-Tree将序列数据库压缩存储在一棵树中。每个节点包含项名、计数和子节点指针。根节点为空。2. 构建树扫描序列数据库对每个序列按顺序插入到树中共享相同前缀的路径合并节点计数增加。3. 头表维护一个项头表包含每个项的支持度和指向树中第一个节点的指针。4. 条件模式基对每个项i通过头表遍历树收集从根到i的路径形成条件序列数据库但只包含i的前缀。5. 条件树用条件序列数据库构建条件WAP-Tree递归挖掘。6. 算法步骤- 扫描数据库删除非频繁项序列按支持度降序排列。- 构建WAP-Tree。- 对每个频繁项i构建i的条件模式基然后构建条件WAP-Tree递归挖掘。7. 数学优化WAP-Tree的规模通常远小于原数据库特别是当序列共享大量前缀时。前缀树、条件模式基、序列压缩O(nL) 构建树n为序列数L为平均长度Web访问序列场景Web日志挖掘、用户点击流分析。方法将序列数据库压缩到树中通过递归投影挖掘模式。554TS-PrefixSpan​序列模式挖掘带时间约束的PrefixSpan1. 时间约束引入最大间隔max_gap、最小间隔min_gap和窗口大小window。2. 投影调整在构建投影数据库时需要考虑时间约束。给定前缀α在序列β中寻找α的投影时需要检查时间戳是否满足约束。3. 投影定义设α (a1, a2, ..., ak)在序列β中α的投影位置是一组时间戳(t1, t2, ..., tk)满足- 对于每个iai在时间ti出现。- t1 t2 ... tk。- 对于每个iti1 - ti 在 [min_gap, max_gap] 内或者如果ai和ai1在同一个项集中则间隔为0。- 整个α的持续时间 ≤ window如果指定。4. 投影数据库对每个序列找出所有满足约束的投影取投影位置之后的后缀作为投影序列。5. 递归挖掘在投影数据库上递归挖掘更长的序列模式。6. 支持度计算一个序列在数据库中的支持度是包含该序列满足时间约束的序列数。时间约束、投影调整、序列模式比PrefixSpan复杂取决于约束带时间戳的序列场景生物序列分析、带有时间间隔的事件序列。方法在PrefixSpan基础上加入时间约束挖掘符合时间关系的序列模式。555SPIRIT算法​序列模式挖掘基于正则表达式的序列模式挖掘1. 问题定义给定一个正则表达式R在序列数据库中挖掘满足R的频繁序列模式。2. 正则表达式例如R A(B|C)D表示以A开头D结尾中间是B或C的任意序列。3. 算法思想利用R对搜索空间进行剪枝。只有可能扩展为满足R的序列才被考虑。4. 自动机构建将R转换为一个非确定性有限自动机NFA或确定性有限自动机DFA。5. 状态跟踪对数据库中的每个序列跟踪自动机状态。在挖掘过程中每个候选序列对应自动机的一个状态集。6. 候选生成从频繁1-序列开始只生成那些在自动机状态下可能转移的项作为扩展。7. 支持度计算计算每个候选序列的支持度即有多少序列的自动机运行可以到达接受状态。8. 剪枝*如果一个序列对应的状态集不包含任何接受状态则剪枝。正则表达式、有限自动机、约束挖掘取决于正则表达式的复杂性序列数据场景模式匹配、生物序列模式发现、日志分析。方法将用户提供的正则表达式作为约束引导序列模式挖掘。556gSpan算法​图模式挖掘图模式挖掘1. 问题在图数据库中挖掘频繁子图模式。2. DFS编码将图表示为DFS编码即通过深度优先搜索遍历图得到的边序列。每个边表示为五元组(i, j, l_i, l_e, l_j)其中i, j为节点序号l_i, l_e, l_j为节点i的标签、边标签、节点j的标签。最小DFS编码作为图的规范表示。3. 子图扩展通过添加边来扩展子图。右扩展在DFS树中新边的节点序号都小于等于最大节点序号且新边连接到最右路径上的节点。前向扩展添加新节点。4. 搜索空间通过DFS编码树组织搜索空间。每个节点对应一个子图模式其子节点通过边扩展得到。5. 剪枝利用支持度进行剪枝。如果一个子图不频繁则其超图也不频繁。6. 支持度计算使用嵌入列表embedding list记录子图在数据库每个图中的匹配位置。支持度是包含该子图的图的数量。7. 算法步骤- 找出所有频繁边1-边子图。- 对每个频繁边以其最小DFS编码为根进行深度优先搜索扩展挖掘更大的频繁子图。- 利用最小DFS编码进行同构检测避免重复生成相同子图。子图挖掘、DFS编码、最小DFS编码指数级但实际中可处理中等规模图图数据场景化学化合物分析、社交网络模式挖掘。方法通过DFS编码将图映射为序列利用序列模式挖掘的思想进行子图挖掘。557CloseGraph算法​图模式挖掘闭合频繁子图挖掘1. 闭合子图子图g是闭合的如果不存在g的超图g使得support(g) support(g)。2. 算法基础基于gSpan但在挖掘过程中检查闭合性。3. 闭合检查对每个发现的频繁子图g检查是否存在g的超图g使得support(g) support(g)。如果存在则g不是闭合的。4. 剪枝如果一个子图不是闭合的则其扩展子图也不可能是闭合的因为支持度不会增加可以剪枝。5. 算法步骤- 使用gSpan挖掘频繁子图但保留所有发现的频繁子图及其支持度。- 在挖掘过程中对每个新发现的频繁子图g检查已发现的闭合子图集中是否有g的子图与g支持度相同如果有则g不是闭合的。- 如果g是闭合的则将其加入闭合子图集并移除那些被g包含且支持度相同的子图。6. 优点闭合子图集通常比所有频繁子图集小得多且保留了支持度信息。闭合子图、gSpan扩展、剪枝同gSpan但输出更少图数据场景压缩频繁子图挖掘结果如蛋白质相互作用网络。方法在gSpan基础上只输出闭合频繁子图减少冗余。558SPIN算法​图模式挖掘基于投影的图模式挖掘1. 投影思想类似PrefixSpan将图数据库投影到频繁子图上递归挖掘。2. 投影定义给定一个频繁子图g在数据库图G中g的投影是G中与g同构的子图位置。投影数据库是g在所有数据库图中的投影的集合。3. 扩展在投影数据库中通过添加边扩展g。新边必须连接到g的节点后向扩展或新节点前向扩展。4. 支持度计算在投影数据库中计算扩展子图的支持度。5. 算法步骤- 找出所有频繁边。- 对每个频繁边e构建e的投影数据库。- 在投影数据库中递归扩展子图挖掘更大的频繁子图。6. 剪枝如果一个子图不频繁则其所有扩展都不频繁。7. 优点投影数据库通常比原数据库小提高了效率。图投影、递归扩展、支持度计数取决于投影数据库大小图数据场景频繁子图挖掘特别是稠密图。方法通过投影将图数据库分解在子图上进行扩展。559GASTON算法​图模式挖掘图/树/路径挖掘的统一框架1. 层次结构将图模式分为路径、树、图三个层次逐层挖掘。2. 算法步骤- 挖掘频繁路径路径是最简单的图结构通过扩展边生成路径。- 挖掘频繁树在路径的基础上通过添加边形成树但避免形成环。- 挖掘频繁图在树的基础上通过添加边形成图允许形成环。3. 扩展操作路径扩展在路径的一端添加新边。树扩展在树的节点上添加新边连接到新节点或现有节点但不能形成环。图扩展在图的节点上添加新边可以形成环。4. 支持度计算使用嵌入列表记录模式在数据库中的匹配支持度计算为包含该模式的图的数量。5. 剪枝使用支持度进行剪枝如果一个模式不频繁则其扩展也不频繁。6. 优点先挖掘简单结构再逐步复杂化可以减少同构检查的次数。路径、树、图、层次挖掘指数级但实际中高效图数据场景化学信息学、XML文档挖掘。方法从简单到复杂挖掘图模式提高效率。560Subdue算法​图模式挖掘基于压缩的子结构发现1. 评价标准使用最小描述长度MDL原则。一个好的子结构应该能压缩数据库的描述长度。2. 描述长度数据库的描述长度L(D) L(S) L(D|S)其中L(S)是子结构的描述长度L(D|S)是用子结构描述数据库的剩余部分的长度。3. 算法目标寻找能最小化L(D)的子结构。4. 算法步骤- 从所有单节点子结构开始计算描述长度增益。- 选择增益最大的子结构将其作为候选模式。- 扩展候选模式通过添加相邻的边或节点扩展子结构计算扩展后的增益。- 选择增益最大的扩展重复直到增益不再增加或达到规模限制。- 用发现的子结构压缩数据库然后递归地在压缩后的数据库中寻找新的子结构。5. 扩展方式后向扩展添加连接到子结构内部节点的边。前向扩展添加连接到子结构边界节点的边和新节点。6. 数学公式增益 L(D) - L(S) - L(D|S)。最小描述长度、压缩、子结构扩展启发式多项式时间图数据场景图数据压缩、模式发现、知识发现。方法基于MDL原则寻找能压缩数据库的频繁子结构。大数据算法深度学习、推荐系统、强化学习编号算法名称算法类型算法/模型名称算法逐步推理思考的数学方程式/核心逻辑关联知识复杂度数据类型应用场景和应用方法571Transformer​深度学习/推荐系统Transformer模型1. 自注意力机制给定查询矩阵Q、键矩阵K、值矩阵V注意力计算为Attention(Q,K,V)softmax(QK^T/√d_k)V其中d_k为键的维度。2. 多头注意力MultiHead(Q,K,V)Concat(head_1,...,head_h)W^O其中head_iAttention(QW_i^Q, KW_i^K, VW_i^V)。3. 位置编码PE(pos,2i)sin(pos/10000^{2i/d_model})PE(pos,2i1)cos(pos/10000^{2i/d_model})其中pos为位置i为维度索引。4. 前馈网络FFN(x)max(0,xW_1b_1)W_2b_2。5. 编码器层由多头自注意力和前馈网络组成每层有残差连接和层归一化xLayerNorm(xMultiHead(x,x,x))xLayerNorm(xFFN(x))。6. 解码器层比编码器多一个编码器-解码器注意力层且自注意力层是掩码的防止看到未来信息。7. 输出层线性变换加softmax得到输出概率分布。自注意力、位置编码、残差连接O(n^2·d) 自注意力序列数据场景机器翻译、文本生成、序列推荐。方法完全基于注意力机制并行计算可捕捉长距离依赖。572BERT​深度学习/推荐系统双向编码表示Transformer1. 输入表示Input Token Embedding Segment Embedding Position Embedding。2. 掩码语言模型随机掩盖输入序列中15%的token其中80%用[MASK]替换10%用随机token替换10%保持不变。模型预测被掩盖的token。3. 下一句预测二分类任务判断句子B是否是句子A的下一句。4. 损失函数L L_MLM L_NSP其中L_MLM是交叉熵损失L_NSP是二分类交叉熵。5. 微调在特定任务上将BERT的输出[CLS]位置的表示或序列表示输入任务特定的层进行端到端微调。6. 预训练任务MLM损失L_MLM -∑_{i∈M} log P(x_ix_{\M})其中M是被掩盖的位置集合。双向编码、掩码语言模型、迁移学习预训练O(n^2·d·L)L为层数文本数据573GPT​深度学习/推荐系统生成式预训练Transformer1. 模型架构使用Transformer解码器掩码自注意力确保只能看到左侧上下文。2. 预训练最大化似然L ∑_i log P(x_ix{i-k},...,x{i-1}; Θ)其中k为上下文窗口大小。3. 微调在标注数据集C上最大化似然L(C) ∑_{(x,y)} log P(yx)。通常将语言模型损失与辅助损失结合L_total L_C λ·L_ML其中L_ML是语言模型损失。4. 文本生成自回归生成每一步基于已生成序列生成下一个token。5. 零样本/少样本学习通过设计提示prompt让模型完成任务无需或只需少量示例。自回归、生成模型、提示学习预训练O(n^2·d·L)574MoE​深度学习/推荐系统混合专家模型1. 模型架构由多个专家网络和一个门控网络组成。给定输入x门控网络输出权重g(x)每个专家网络输出y_i最终输出y ∑i g_i(x)·E_i(x)。2. 门控网络通常使用softmaxg(x) softmax(W_g x)。3. 稀疏门控为了计算效率只激活top-k个专家。设激活的专家索引为TopK(g(x))则输出y ∑{i∈TopK(g(x))} g_i(x)·E_i(x)。4. 负载均衡引入辅助损失确保专家负载均衡。设每个batch中每个专家的负载为f_i ∑{x∈B} g_i(x)辅助损失L_balance ∑i f_i·log f_i。5. 总损失L L_task α·L_balance。6. 参数共享专家之间可共享部分参数如底层嵌入。条件计算、专家网络、负载均衡计算与激活的专家数相关大规模模型场景大规模推荐系统、语言模型需要处理多样化输入。方法将大模型分解为多个专家每个输入只激活部分专家平衡计算和模型容量。575DPR​深度学习/推荐系统双塔检索模型1. 模型架构查询编码器E_Q和文档编码器E_D将查询q和文档d分别映射为向量v_q E_Q(q)和v_d E_D(d)。2. 相似度sim(q,d) v_q^T v_d。3. 训练目标对比学习给定查询q正样本文档d^负样本文档d^-使用InfoNCE损失L -log exp(sim(q,d^)) / [exp(sim(q,d^)) ∑_{d^-} exp(sim(q,d^-))]。4. 负采样使用批量负采样同一个batch中的其他文档作为负样本和难负例挖掘。5. 索引用FAISS等工具为文档向量构建索引实现快速近似最近邻搜索。6. 训练技巧使用in-batch负采样、温度参数τ调节softmax平滑度。双塔模型、对比学习、近似最近邻训练O(batch_size·d)检索O(log N)查询-文档对场景搜索引擎、推荐系统召回阶段。方法将查询和文档编码为向量用向量相似度匹配适合大规模检索。576ColBERT​深度学习/推荐系统上下文化晚期交互BERT1. 模型架构使用BERT编码查询和文档得到每个token的嵌入。查询Q的嵌入矩阵E_Q∈ℝ^{m×d}文档D的嵌入矩阵E_D∈ℝ^{n×d}。2. 相似度计算对查询的每个token嵌入q_i计算与文档所有token嵌入的最大相似度然后求和S(Q,D) ∑{i1}^m max{j1}^n q_i^T d_j。3. 训练使用对比学习与DPR类似但相似度计算不同。4. 索引为文档的每个token嵌入建立索引检索时对查询的每个token进行最大相似度计算然后聚合。5. 压缩可使用量化或降维减少索引大小。6. 优点比双塔模型更精细的交互比交叉编码器更快。细粒度交互、最大相似度聚合、对比学习索引O(n·d)检索O(m·n·d)但优化查询-文档对场景搜索引擎、开放域问答需要细粒度匹配。方法在token级别进行交互平衡了精度和速度。577Poly-Encoder​深度学习/推荐系统多编码器1. 模型架构用Transformer编码候选文档用另一个Transformer编码查询但查询编码器输出多个向量通过多个可学习的编码向量称为code。2. 编码候选文档编码为向量c。查询编码用m个可学习的编码向量code与查询的token嵌入进行注意力聚合得到m个查询向量q_1,...,q_m。3. 交互计算每个查询向量与候选文档向量的注意力权重α_i softmax(q_i^T c)然后用这些权重对查询向量加权求和得到最终的查询表示q ∑_i α_i q_i。4. 相似度sim(q,c) q^T c。5. 训练对比学习类似DPR。6. 优点比双塔模型更强大比交叉编码器更快适合召回和粗排。多向量表示、注意力聚合、对比学习编码O((nm)·d^2)交互O(m·d)查询-文档对场景对话系统、推荐系统需要中等复杂度的交互。方法用多个向量表示查询与候选文档进行轻量级交互。578Deep Q-Network​强化学习/推荐系统深度Q网络1. Q学习Q(s,a) r γ max{a} Q(s,a)。用神经网络近似Q函数参数θ。2. 损失函数L(θ) E{(s,a,r,s)}[(r γ max_{a} Q(s,a;θ^-) - Q(s,a;θ))^2]其中θ^-为目标网络参数。3. 经验回放存储转移(s,a,r,s)到回放缓冲区训练时随机采样打破相关性。4. 目标网络使用另一个网络参数θ^-计算目标Q值定期更新θ^-θ。5. 探索使用ε-greedy策略以ε概率随机选择动作否则选择最大Q值的动作。6. 训练步骤- 初始化回放缓冲区D容量N。- 用随机权重初始化Q网络目标网络权重θ^-θ。- 每个episode初始化状态s。- 每个时间步以ε概率选择随机动作a否则aargmax_a Q(s,a;θ)。执行a得到r,s存储(s,a,r,s)到D。从D中采样一批数据用损失函数更新θ。每C步更新θ^-θ。Q学习、经验回放、目标网络训练取决于环境交互状态-动作-奖励场景游戏AI、机器人控制、动态推荐。方法用深度网络近似Q函数通过经验回放和目标网络稳定训练。579Policy Gradient​强化学习/推荐系统策略梯度1. 目标最大化期望回报J(θ)E_τ[R(τ)]其中τ为轨迹R(τ)为累积奖励。2. 策略梯度定理∇θ J(θ)E_τ[∑{t0}^{T-1} ∇_θ log π_θ(a_ts_t) Q^{π_θ}(s_t,a_t)]其中Q^{π_θ}是状态-动作值函数。3. REINFORCE算法使用蒙特卡洛采样估计Q值∇θ J(θ) ≈ ∑t ∇_θ log π_θ(a_ts_t) R_t其中R_t是t步后的累积奖励。4. 基线为减少方差引入基线b(s)常用状态值函数V(s)。∇θ J(θ) ≈ ∑t ∇_θ log π_θ(a_ts_t) (R_t - b(s_t))。5. 演员-评论家用神经网络近似策略演员和价值函数评论家。演员更新用策略梯度评论家更新用时序差分误差。6. 优势函数A(s,a)Q(s,a)-V(s)用估计的优势函数代替Q值。蒙特卡洛、基线、演员-评论家580PPO​强化学习/推荐系统近端策略优化1. 目标函数L(θ)E_t[min(r_t(θ)A_t, clip(r_t(θ),1-ε,1ε)A_t)]其中r_t(θ)π_θ(a_ts_t)/π_{θ_old}(a_ts_t)A_t是优势函数估计。2. 优势估计使用广义优势估计GAEA_t ∑{l0}^{∞} (γλ)^l δ{tl}其中δ_t r_t γV(s_{t1}) - V(s_t)。3. 价值函数损失L_V(θ) (V_θ(s_t) - V_t^{target})^2其中V_t^{target}是目标价值。4. 熵奖励增加策略熵鼓励探索L_total L_PPO - c_v L_V c_e H(π_θ)其中H是熵。5. 训练步骤- 用当前策略收集一批轨迹。- 计算优势估计和价值目标。- 对目标函数进行多轮小批量随机梯度上升。- 更新价值函数网络。6. 裁剪限制策略更新幅度确保新策略不偏离旧策略太远。信赖域、裁剪、广义优势估计每次迭代需收集完整轨迹以上是10个深度学习、推荐系统和强化学习算法的详细描述。接下来可以继续补充其他领域的算法如无监督学习、关联规则等。您希望继续补充哪些算法