参考：https://zhuanlan.zhihu.com/p/623557803https://www.bilibili.com/video/BV1TecTeoErXChain of Thought1 提出论文地址：https://arxiv.org/abs/2201.11903最早提出是在2022年5月谷歌发表的《Chain-of-Thought Prompting Elicits Reasoning in Large Language Models》文章中。论文的提出方法的出发点是：大语言模型扩大规模 能带来性能的提高，但是在 算术、思维推理等具有挑战性的任务上 难以实现高性能。推理技术可以通过生成自然语言推理过程 (retionales) 来帮助得出最终答案。前人的工作：赋予模型生成自然语言中间步骤的能力方法：从头开始训练或微调或使用形式语言的方法缺点：创建大规模高质量的推理过程代价昂贵通过 prompting 提供了上下文少样本学习方式 (few-shot learning)缺点：推理能力表现不佳论文的思路：避免这些局限性同时结合两者优势。方法：chain-of-thought prompting。考虑人类在解决复杂推理任务时候的思维过程，比如在解决多步骤的数学文字问题，我们通常会 将问题分解为多个中间步骤，逐个解决，最后得出答案。After Jane gives 2 flowers to her mom she has 10... then after she gives 3 to her dad she will have 7... so the answer is 7.论文的目标：赋予语言模型生成类似于人类思考的思维链 (chain of thought)论文探索 语言模型 在推理任务中的少样本提示能力，并采用 由三元组组成的提示：(input, chain of thought, output)。chain of thought 思维链 是一系列 通向最终输出 的中间自然语言推理步骤论文具体实现的方法：在样本提示中，包含带有少量思维链的示例，就可以 引发大型语言模型进行思维链推理，无需对模型进行额外的训练或微调。论文给出的示例：问题：需要精心设计带有中间推理步骤的提示示例，增加了人力成本。2 方法介绍参考：《大模型基础》(https://github.com/ZJU-LLMs/Foundations-of-LLMs)在心理学上，System-1 任务和 System-2 任务分别代表两种不同的思维方式所处理的任务类型：System-1：思考过程快速、自动且无意识，主要依靠直觉和经验判断，不需要刻意的思考。System-2：思考过程比较缓慢，需要集中注意力，运用逻辑分析、计算和有意识的思考来解决问题。随着 大模型参数量、算力开销、数据量协同增长，在标准提示下，其在 System-1 任务上性能显著增强。然而，在 System-2 任务上，大模型表现出了 "Flat Scaling Curves" 现象——即模型规模增长未带来预期性能提升。面对 System-1 问题，如 常识回答、情感分类、意图识别 等，随规模变大，大模型性能显著提升面对 System-2 问题，如 复杂数学计算、逻辑推理 等，大模型性能 提升缓慢甚至停滞不前。思维链：通过在提示中嵌入一系列 中间推理步骤，引导大语言模型模拟人类解决问题时的思考过程，以提升模型处理 System2任务的能力。在标准的 CoT 方法上，出现了许多扩展的方法：按部就班、三思后行、集思广益。按部就班：在按部就班模式中，模型一步接着一步地进行推理，推理路径形成了一条逻辑连贯的链条。以 CoT、Zero-Shot CoT、Auto-CoT 等方法为代表。强调：逻辑的连贯性和步骤的顺序性Zero-Shot CoT：使用两阶段回答问题：第一阶段，在问题后面跟上一句“让我们一步一步思考”作为 CoT 的提示触发词，来指示大语言模型先生成中间推理步骤，再生成最后的答案第二阶段，把原始的问题以及第一阶段生成的推理步骤拼接在一起，在末尾加上一句“因此，最终答案为”，把这些内容输给大语言模型，让它输出最终的答案标注成本低，算法性能差Auto-CoT：利用聚类技术从问题库中筛选出与用户提问位于一个簇中的问题借助 Zero-Shot CoT 的方式，为筛选出的问题生成推理链，形成示例。在这些示例基础上， 引导大语言模型生成针对用户问题的推理链和答案。三思后行：每一步都停下来评估当前的情况，然后从多个推理方向中选择出下一步的前进方向。以 ToT、GoT 等方法为代表。Tree of Thoughts (ToT)：将推理过程视为一棵思维树，从拆解、衍生、评估、搜索 四个方面进行构造：拆解：把复杂问题拆分成多个简单子问题，每个子问题的解答过程对应一个思维过程。衍生：模型需要根据子问题 生成可能的下一步推理方向。衍生有两种模式：样本启发和命令提示。评估：利用模型评估推理节点合理性。有投票和打分两种评估模式。搜索：从一个或多个当前状态出发，搜索通往问题解决方案的路径。根据任务特点选择不同的搜索算法。Graph of Thoughts (GoT)：通过特定提示，自动化构造 一步一步推理 回答问题的例子，在 ToT 基础上，将树拓展为有向图，具有思维自我反思、思维聚合的能力。集思广益：同时生成多条推理路径并得到多个结果，然后整合这些结果，得到一个更为全面和准确的答案。以 Self-Consistency 等方法为代表。Self-Consistency：引入多样性的推理路径，从中提取并选择最一致的答案，从而提高了模型的推理准确性。Self-Consistency 不依赖于 特定的 CoT 形式，可以与其他 CoT 方法兼容，共同作用于模型的推理过程。推理路径生成：在随机采样策略下，使用 CoT 或 Zero-Shot CoT 的方式来引导大语言模型针对解决问题生成一组多样化的推理路径汇总答案：收集最终答案，统计每个答案在所有推理路径中出现的频率选择答案：选择出现 频率最高 的答案作为最终的、最一致的答案Universal Self-Consistency：利用 LLMs 自身选择最一致答案，支持更多种任务，无需答案提取过程。在多任务中性能良好且输出匹配度更高、对顺序鲁棒。3 应用3.1 大语言模型 - DeepSeek《DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning》（https://arxiv.org/abs/2501.12948）在 DeepSeek R1 中，充分展示了 大语言模型 的 推理能力。利用 强化学习 ，让模型探索 思维链 (CoT) 以解决复杂问题，由此开发出 DeepSeek-R1-Zero，该模型具有 自我验证、反思和 生成长思维链 的能力。缺点：在可读性差和语言混杂等挑战上表现不佳。基于 DeepSeek-V3-Base 开发 DeepSeek-R1 的流程：Cold Start，构建一部分 长思维链数据 微调模型，使其作为 初始 RL actor大规模强化学习训练：增强模型的推理能力，特别是 编程、数学、科学和逻辑推理等需要推理的任务。监督微调(Supervised Fine-Tuning, SFT)：增强模型在写作、角色扮演和其他通用任务中的能力。 使用推理数据和非推理数据对模型进行两轮微调。强化学习：使模型与人类偏好保持一致。知识蒸馏 (Distillation)3.2 多模态大语言模型的视觉思维链 Visual CoT论文地址：https://arxiv.org/abs/2403.16999研究出发点：多模态大语言模型在各种视觉问答任务中表现出色。然而，它们往往 缺乏可解释性，并且在处理复杂的视觉输入时表现不佳。目的：提高 MLLM 的准确性和适应性，所以需要提出能够处理 多轮、动态聚焦视觉输入 的方法，同时提供 更具可解释性 的推理阶段困难：现有的视觉问答数据集缺乏中间视觉链式思维监督流行的 MLLM pipeline 依赖于静态的图像上下文输入研究提出：大规模 Visual CoT 数据集：每个数据项 由 一个问题、一个答案、一个中间边界框。一些数据项同时包含 细节的推理步骤。multi-turn processing pipeline：动态地关注 视觉输入 并 提供可解释的思考过程。visual CoT MLLM framework: "VisCoT"VisCoT pipeline:在问题中添加 提示 "Please provide the bounding box coordinate of the region that can help you answer the question better. "，让模型识别图像中信息量最大的区域。根据边界框坐标确定该区域并生成其边界框训练阶段，使用真实的边界框来提取视觉信息利用原始图像和边界框， visual sampler 提取包含详细信息的局部图像。MLLM 使用 {原始图像 visual token, 局部图像 visual token} 来提供更精确和全面的答案。visual CoT banckmark：评估 在需要聚焦特定局部区域的场景下 MLLMs 的表现。3.3 基于定位的思维链 GCoT论文地址：https://arxiv.org/abs/2502.08092研究出发点：现有的多模态大语言模型 容易受到 视觉幻觉 (visual hallucination) 的影响。在面向 MLLM 的 CoT 领域，最近的研究主要集中于视觉解释或知识推理。这些方法并没有验证每个推理步骤是否是正确的视觉证据。以前的视觉定位工作旨在 定位 给定问题中所提到的所有对象。GCoT 则侧重于分析问题，形成基于定位的推理步骤，并最终给出正确答案。方法：从 视觉空间推理 (visual-spatial reasoning) 的角度研究 这个问题，提出 Grounded Chain-of-Thought (GCoT)。GCoT 帮助 MLLM 逐步 识别并定位 相关视觉线索，从而 将定位坐标作为直觉基础 来预测正确答案。GCoT 旨在培养 MLLM 的视觉和空间感知能力，使它们能够为正确回答问题打好基础。构建一个 数据集：multimodal grounded chain-of-thought (MM-GCoT)。用于现有 MLLM 的 SFT 调优。所有样本分为 Attribute、Judgment、Object 三种类型。引入一个综合一致性评估系统，包括 answer accuracy、grounding accuracy 以及 answer-grounding consistency 三个指标。3.4 自回归图像生成模型的思维链应用 - Autoregressive Model在图像生成领域，Diffusion Model 占据主导地位，最近，Autoregressive Model 的研究也取得了一定的进展：VAR：《Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction》："next-image-token prediction" => "next-scale(next-resolution) prediction"。（https://arxiv.org/abs/2404.02905）llamaGen：《Autoregressive Model Beats Diffusion: Llama for Scalable Image Generation》："next-token prediction" 架构。（https://arxiv.org/abs/2406.06525）由于上述图像生成模型结构和大语言模型相似，因此有研究探索 CoT 应用于 图像生成模型中。《Can We Generate Images with CoT? Let’s Verify and Reinforce Image Generation Step by Step》首次系统地探讨了将 “思维链”（CoT）推理策略应用于自回归图像生成的潜力。（https://arxiv.org/abs/2501.13926）在 结果奖励模型 (Outcome Reward Model) 和 过程奖励模型 (Process Reward Model) 的基础之上提出了 Potential Assessment Reward Model (PARM)。Potential Assessment Reward Model判断 哪一步生成的图像 足够清晰 以 进行评估。评估 当前步骤 是否有潜力生成高质量的最终图像。对剩余的 最终路径 进行评分 以选择最佳路径。增强版本 PARM++：在 PARM 基础上，增加一种 反思机制，使自回归模型能够优化其先前生成的图像。图像生成模型的自我修正 依赖于 文本提示 作为输入，仅输出图像模态。因此，反思能力必须由 一个外部 奖励模型 来处理，负责识别 不一致 并 提供解释。此外，图像生成模型本身也需要进行微调，以有效理解和回应这些反思文本以实现自我修正。PARM++：在 N' 个图像候选中选出最佳输出后，检查最终图像与输入文本之间的一致性。如果一致，直接作为最终输出图像；如果不一致，则提供不一致的详细分析，将三个输入反馈给生成模型，以自我修正其图像输出，包括 原始文本提示、之前生成的次优图像 和 识别的不一致原因。（如此反复多次）3.5 RPG-Diffusion论文地址：https://arxiv.org/abs/2401.11708问题：扩散模型在处理复杂文本提示的时候面临困难。现有基于布局或者注意力的方法 只能 提供粗略和次优的空间指导，并且难以处理重叠物体。基于反馈的方法需要收集高质量的反馈并产生额外的训练成本。方法：提出一种 training-free text-to-image generating/editing framework，称为 Recaption, Plan and Generate (RPG)。利用 MLLM 的链式推理能力，增强文本到图像扩散模型的组合性 (compositionality)。RPG 中三个核心策略：Multimodal Recaptioning使用 LLMs 将 text prompt 拆分为 单独的 subprompt，然后对它们进行 更详细的描述。使用 MLLM 自动对 输入图像进行 recaption，从而识别 生成图像 和 目标提示 之间的语义差异。recaption 主要指 重新生成或优化图像的文本描述（caption）Chain-of-Thought Planning将图像空间划分为互补的 子区域，不同子区域 分配 不同的 subprompt。精心设计任务指令和上下文示例，利用 MLLM 的 思维链推理能力 实现更高效的 区域划分。Complementary Regional Diffusion在 指定的矩形 子区域，根据 subprompt 生成图像内容，随后通过 缩放和拼接 的方式将它们进行空间合并。扩展：通过基于轮廓的区域扩散（Contour-based Regional Diffusion），精准修改目标区域的不一致内容。3.6 增强文本-图像生成上下文推理能力的思维链应用 ImageGen-CoT论文地址：https://arxiv.org/abs/2503.19312问题：统一多模态大语言模型 (unified MLLM) 在 Text-to-Image In-Context Learning (T2I-ICL) 场景的 上下文推理 仍然存在困难。方法：在生成图像之前纳入了一种称为 ImageGen-CoT 的思维过程，有助于 unified MLLM 更好地理解 上下文并生成更连贯的输出。为了避免生成 无结构的无效推理步骤 => 开发了一个自动化流程来构建高质量的 ImageGen-CoT 数据集。=> 使用数据集对 MLLM 进行微调来增强它们的上下文推理能力。流程主要包括三个阶段：收集 T2I-ICL instructions。使用 MLLMs 生成 step-by-step reasoning。通过 MLLMs 生成图像描述，以便 Diffusion Model 来生成图像。为了进一步提高数据集质量，采用了迭代精炼过程：模型首先生成多个文本提示和相应的图像，选择最佳的一个，对生成的图像进行评析，并迭代地优化提示直到到达最大轮次。随后，使用该数据集对模型进行微调。研究探索了三种 test-time scale-up strategies (测试时扩展策略)：Multi-Chain：生成多个 ImageGen-CoT 链，每个链生成一张图像Single-Chain：从一个 ImageGen-CoT 创建多个图像变体Hybrid：结合上述两种方法——多个推理链，每个推理连生成多个图像变体。ImageGen-CoT 框架：two-stage inference protocolprompt the model to generate the ImageGen-CoT reasoning chain $R$combine the original input $X$ with the generated ImageGen-CoT $R$构建数据集：自动化迭代过程，MLLM 作为 Generator, Selector, Critic 以及 Refiner 来生成高质量 ImageGen-CoT 和 对齐图像。训练过程：在 ImageGen-CoT 数据集基础上 微调 unified MLLM 来增强 上下文推理和图像生成能力。ImageGen-CoT 数据集分成两部分：$[X, p_{\text{cot}}] → \text{ImageGen-CoT} $$[X, \text{ImageGen-CoT}, p_{\text{image}}] → \text{image}$Test time scale up
参考：https://www.bilibili.com/video/BV1TecTeoErX随着大模型参数量、算力开销、数据量协同增长，在标准提示下，其在 System-1 任务上性能显著增强。然而，在 System-2 任务上，大模型表现出了 "Flat Scaling Curves" 现象——即模型规模增长未带来预期性能提升。面对 System-1 问题，如 常识回答、情感分类、意图识别 等，随规模变大，大模型性能显著提升面对 System-2 问题，如 复杂数学计算、逻辑推理 等，大模型性能 提升缓慢甚至停滞不前。思维链：通过在提示中嵌入一系列 中间推理步骤，引导大语言模型模拟人类解决问题时的思考过程，以提升模型处理 System2任务的能力。在标准的 CoT 方法上，出现了许多扩展的方法：按部就班、三思后行、集思广益按部就班：在按部就班模式中，模型一步接着一步地进行推理，推理路径形成了一条逻辑连贯的链条。以 CoT、Zero-Shot CoT、Auto-CoT 等方法为代表。强调：逻辑的连贯性和步骤的顺序性Zero-Shot CoT：使用两阶段回答问题：第一阶段，在问题后面跟上一句“让我们一步一步思考”作为 CoT 的提示触发词，来指示大预言模型先生成中间推理步骤，再生成最后的答案第二阶段，把原始的问题以及第一阶段生成的推理步骤拼接在一起，在末尾加上一句“因此，最终答案为”，把这些内容输给大语言模型，让它输出最终的答案标注成本低，算法性能差Auto-CoT：利用聚类技术从问题库中筛选出与用户提问位于一个簇中的问题借助 Zero-Shot CoT 的方式，为筛选出的问题生成推理链，形成示例。在这些示例基础上， 引导大语言模型生成针对用户问题的推理链和答案。三思后行：每一步都停下来评估当前的情况，然后从多个推理方向中选择出下一步的前进方向。以 ToT、GoT 等方法为代表。Tree of Thoughts (ToT)：将推理过程视为一棵思维树，从拆解、衍生、评估、搜索 四个方面进行构造：拆解：把复杂问题拆分成多个简单子问题，每个子问题的解答过程对应一个思维过程。衍生：模型需要根据子问题生成的可能的下一步推理方向。衍生有两种模式：样本启发和命令提示。评估：利用模型评估推理节点合理性。有投票和打分两种评估模式。搜索：从一个或多个当前状态出发，搜索通往问题解决方案的路径。Graph of Thoughts (GoT)：通过特定提示，自动化构造一步一步推理回答问题的例子。集思广益：同时生成多条推理路径并得到多个结果，然后整合这些结果，得到一个更为全面和准确的答案。以 Self-Consistency 等方法为代表。Self-Consistency：引入多样性的推理路径，从中提取并选择最一致的答案，从而提高了模型的推理准确性。Self-Consistency 不依赖于特定的 CoT 形式，可以与其他 CoT 方法兼容，共同作用于模型的推理过程。推理路径生成：在随机采样策略下，使用 CoT 或 Zero-Shot CoT 的方式来引导大语言模型针对解决问题生成一组多样化的推理路径汇总答案：收集最终答案，统计每个答案在所有推理路径中出现的频率选择答案：选择出现频率最高的答案作为最终的、最一致的答案Universal Self-Consistency：利用 LLMs 自身选择最一致答案，支持更多种任务，无需答案提取过程。在多任务中性能良好且输出匹配度更高、对顺序鲁棒。
1 DeepSeek LLMScaling Laws问题：早期关于最优模型/数据扩大分配策略的研究展示了不同的结论，引发了对规模定律普遍适用性的质疑。此外，这些研究通常缺乏对超参数设置的完整描述，无法确定在不同计算预算下模型是否达到了最佳性能。工作：建立了超参数的缩放规律，为确定最佳超参数提供了一个经验框架。采用 FLOPs/token M 表示模型规模，得到更准确的最优模型/数据扩展分配策略，并更好地预测大规模模型的泛化损失。预训练数据的质量影响最优模型/数据扩展配置策略。数据质量越高，越应该将增加的计算预算分配给模型（model）扩展。Alignment对齐流程包含两个阶段：Supervised Fine-TuningDirect Perference Optimization Algorithm2 DeepSeek-V2MoE 语言模型，经济的训练 和 高效的推理创新的架构：Multi-head Latent Attention(MLA) 和 DeepSeekMoE进一步工作：Supervised Fine-Tuning (SFT) 和 Reinforcement Learning (RL) 充分释放模型潜能Multi-Head Latent Attention: Boosting Inference Efficiency问题：常规的 transformer 模型通常采用 Multi-Head Attention (MHA)，但是在生成过程中，其 庞大的 Key-Value cache 成为限制推断效率的瓶颈为了减少 KV cache，可以采用 Multi-Query Attention (MQA) 和 Grouped-Query Attention (GQA)，它们需要更少的 KV cache，但是性能有所降低方法：Multi-head Latent Attention，采用了 low-rank key-value joint compression。标准的 Multi-Head Attentionembedding dimension: dthe number of attention heads: $n_h$the dimension per head: $d_h$$\mathbf{h}_t \in \mathbb R^d$ 为第 t 个 token 在注意力层的输入。$$ \begin{gather} \mathbf{q}_t = W^Q \mathbf{h}_t,\\ \mathbf{k}_t = W^K \mathbf{h}_t,\\ \mathbf{v}_t = W^V \mathbf{h}_t, \end{gather} $$$\mathbf{q}_t, \mathbf{k}_t, \mathbf{v}_t$ 被切分为 $n_h$ heads以进行 multi-head attention computation:$$ \begin{gather} [\mathbf{q}_{t,1};\mathbf{q}_{t,2};\cdots;\mathbf{q}_{t,n_h}] = \mathbf{q}_{t},\\ [\mathbf{k}_{t,1};\mathbf{k}_{t,2};\cdots;\mathbf{k}_{t,n_h}] = \mathbf{k}_{t},\\ [\mathbf{v}_{t,1};\mathbf{v}_{t,2};\cdots;\mathbf{v}_{t,n_h}] = \mathbf{v}_{t},\\ \mathbf{o}_{t,i} = \sum_{j=1}^t \text{Softmax}_j(\cfrac{\mathbf{q}_{t,i}^T\mathbf{k}_{j,i}}{\sqrt{d_h}})\mathbf{v}_{j,i},\\ \mathbf{u}_{t} = W^O[\mathbf{o}_{t,1};\mathbf{o}_{t,2};\cdots;\mathbf{o}_{t,n_h}] \end{gather} $$在推理过程中，所有的 key 和 value 需要被缓存以加速推理，因此，MHA 需要为每个 token 缓存 $2n_hd_hl$ 个元素，在模型部署中，KV cache 成为限制 最大 batch size 和 序列长度 的重要瓶颈。Low-Rank Key-Value Joint CompressionMLA 的核心是对 keys 和 values 进行 low-rank joint compression，以减少 KV cache：$$ \mathbf{c}_{t}^{KV} = W^{DKV}\mathbf{h}_t,\\ \mathbf{k}_t^C = W^{UK}\mathbf{c}_{t}^{KV},\\ \mathbf{v}_t^C = W^{UV}\mathbf{c}_{t}^{KV}, $$$\mathbf{c}_t^{KV} \in \mathbb R^{d_c}$ 是 keys 和 values 的 compressed latent vector$d_c(\ll d_hn_h)$ 表示 KV compression dimension$W^{DKV}\in \mathbb R^{d_c\times d}$ 是降维矩阵$W^{UK}, W^{UV}\in \mathbb R^{d_hn_h\times d_c}$ 则分别是 key 和 value 的升维矩阵推理过程中，MLA 只需缓存 $\mathbf{c}_t^{KV}$ ，因此其 KV cache 只有 $d_cl$ 个元素，其中 $l$ 表示层数。此外，推理期间，由于 $W^{UK}$ 可以被吸收到 $W^Q$ 中，而 $W^{UV}$ 可以被吸收到 $W^O$ 中，我们不需要为注意力计算 key 和 value。为了在训练期间减少激活内存，对 queries 进行 低秩压缩：$$ \begin{gather} \mathbf{c}_{t}^{Q} = W^{DQ}\mathbf{h}_t,\\ \mathbf{q}_t^C = W^{UQ}\mathbf{c}_{t}^{Q},\\ \end{gather} $$其中，$\mathbf{c}_{t}^{Q}\in \mathbb R^{d_c'}$ 是查询的 压缩潜在变量，$d_c'(\ll d_hn_h)$ 表示查询压缩维度，$W^{DQ}\in \mathbb R^{d_c'\times d}$,$W^{UQ}\in \mathbb R^{d_hn_h\times d_c'}$ 是查询的下投影和上投影矩阵。【推导思路】参考：https://www.bilibili.com/video/BV1DxK7e6EYT/矩阵乘法角度理解标准MHA：$$ \begin{aligned} H_{1:t} &= [\mathbf{h}_1, \mathbf{h}_2,\cdots,\mathbf{h}_t]\\ Q_{1:t} &= [\mathbf{q}_1, \mathbf{q}_2,\cdots,\mathbf{q}_t]\\ K_{1:t} &= [\mathbf{k}_1, \mathbf{k}_2,\cdots,\mathbf{k}_t]\\ V_{1:t} &= [\mathbf{v}_1, \mathbf{v}_2,\cdots,\mathbf{v}_t]\\ \mathbf u_t &= W^O(O_t) = W^O\left(\text{Softmax}\left( \cfrac{Q^T_{1:t} K_{1:t}}{\sqrt{d_h}} \right)V_{1:t}\right)\\ & = W^O\left(\text{Softmax}\left( \cfrac{(W^QH_{1:t})^T (W^KH_{1:t})}{\sqrt{d_h}} \right)(W^VH_{1:t})\right) \end{aligned} $$一个矩阵 $W$ 可以分解为两个低秩矩阵的成绩：$W_{h_1\times h_2} = W^D_{h_1\times d}W^U_{d\times h_2}$，$W^D$ 看作降维矩阵，$W^U$ 看作升维矩阵。对 $W^K$ 和 $W^V$ 进行 低秩分解：$$ W^K = W^{DK}W^{UK},W^V = W^{DV}W^{UV} $$为了简化，$W^{DK} = W^{DV} = W^{DKV}$，使得 key 和 value 共享潜在变量 $\mathbf{c}^{KV}$：$$ \begin{gather} \mathbf{c}^{KV} = W^{DKV}\mathbf{h}\\ \mathbf{k}^C = W^{UK}\mathbf{c}^{KV}, \mathbf{v}^C = W^{UV}\mathbf{c}^{KV} \end{gather} $$同理，取潜在变量 $\mathbf{c}^Q$ ，有：$\mathbf{c}^{Q} = W^{DQ}\mathbf{h}_t,\mathbf{q}_t^C = W^{UQ}\mathbf{c}^{Q}$矩阵吸收：$$ \mathbf u_t = W^O\left(\text{Softmax}\left( \cfrac{H^T(W^Q)^TW^{UK}C^{KV}}{\sqrt{d_h}} \right)(W^{UV}C^{KV}H)\right) $$$W^O$ 和 $W^{UV}$ 合并$(W^Q)^T$ 和 $W^{UK}$ 合并Decoupled Rotary Position Embedding使用 Rotary Position Embedding (RoPE)，然而，RoPE 与 low-rank KV compression 不兼容。方法：解耦 RoPE 策略 (decoupled RoPE strategy)，该策略使用额外的 multi-head queries $\mathbf{q}_{t,i}^R\in \mathbb R^{d_h^R}$ 和一个 共享key $\mathbf{k}_{t,i}^R\in \mathbb R^{d_h^R}$ 来承载 RoPE，其中 $d_h^R$ 表示解耦 query 和 key 的 per-head dimension。在配备 解耦RoPE策略后，MLA执行以下计算：$$ \begin{align} [\mathbf{q}_{t,1}^R;\mathbf{q}_{t,2}^R;\cdots;\mathbf{q}_{t,n_h}^R] = \mathbf{q}_{t}^R &= \text{RoPE}(W^{QR}\mathbf{c}^Q_t),\\ \mathbf k_t^R &= \text{RoPE}(W^{KR}\mathbf h_t),\\ \mathbf q_{t,i} & = [\mathbf q_{t,i}^C; \mathbf q_{t,i}^R],\\ \mathbf k_{t,i} & = [\mathbf k_{t,i}^C; \mathbf k_{t}^R], \\\mathbf{o}_{t,i}& = \sum_{j=1}^t \text{Softmax}_j(\cfrac{\mathbf{q}_{t,i}^T\mathbf{k}_{j,i}}{\sqrt{d_h + d_h^R}})\mathbf{v}_{j,i}^C,\\ \mathbf{u}_{t} &= W^O[\mathbf{o}_{t,1};\mathbf{o}_{t,2};\cdots;\mathbf{o}_{t,n_h}] \end{align} $$完整的计算过程：$$ \begin{align} {\color{blue}\mathbf{c}_{t}^{Q}} &= W^{DQ}\mathbf{h}_t,\\ [\mathbf{q}_{t,1}^C;\mathbf{q}_{t,2}^C;\cdots;\mathbf{q}_{t,n_h}^C] = \mathbf{q}_t^C &= W^{UQ}\mathbf{c}_{t}^{Q},\\ [\mathbf{q}_{t,1}^R;\mathbf{q}_{t,2}^R;\cdots;\mathbf{q}_{t,n_h}^R] = \mathbf{q}_t^R &= \text{RoPE}(W^{QR}\mathbf{c}_{t}^{Q}),\\ \mathbf q_{t,i} &=[\mathbf q_{t,i}^C; \mathbf q_{t,i}^R],\\\\ {\color{blue}{c_t^{KV}}} & = W^{DKV}\mathbf h_t,\\\\ [\mathbf{k}_{t,1}^C;\mathbf{k}_{t,2}^C;\cdots;\mathbf{k}_{t,n_h}^C] = \mathbf{k}_t^C &= W^{UK}\mathbf{c}_{t}^{KV},\\ \mathbf{k}_t^R &= \text{RoPE}(W^{KR}\mathbf{h}_{t}),\\ \mathbf k_{t,i} &=[\mathbf k_{t,i}^C; \mathbf k_{t}^R],\\\\ [\mathbf{v}_{t,1}^C;\mathbf{v}_{t,2}^C;\cdots;\mathbf{v}_{t,n_h}^C] = \mathbf{v}_t^C &= W^{UV}\mathbf{c}_{t}^{KV},\\\\ \mathbf{o}_{t,i}& = \sum_{j=1}^t \text{Softmax}_j(\cfrac{\mathbf{q}_{t,i}^T\mathbf{k}_{j,i}}{\sqrt{d_h + d_h^R}})\mathbf{v}_{j,i}^C,\\ \mathbf{u}_{t} &= W^O[\mathbf{o}_{t,1};\mathbf{o}_{t,2};\cdots;\mathbf{o}_{t,n_h}] \end{align} $$原始公式需要 恢复 $\mathbf k_t^C$ 和 $\mathbf v_t^C$ ，但是由于矩阵乘法的结合律，可以将 $W^{UK}$ 吸收进 $W^{UQ}$ ，将 $W^{UV}$ 吸收进 $W^{O}$，不需要为每个查询计算 key 和 value。DeepSeekMoE关键思想：将专家细分为更精细的粒度，以提高专家的专业化和更准确的知识获取以提高专家的专业化和更准确的知识获取具体内容：https://blog.carolineworld.cn/index.php/archives/63/$$ \begin{align} \mathbf{h}_t' &= \mathbf{u}_t+{\sum_{i=1}^{N_s}\text{FFN}_i^{(s)}(\mathbf{u}_t)} + \sum_{i=1}^{N_r}g_{i,t}\text{FFN}_i^{(r)}(\mathbf{u}_t) \\ g_{i,t} &= \begin{cases} s_{i,t},&s_{i,t}\in\text{Topk}(\{s_{j,t}|1\leqslant j \leqslant N_r\}, K_r),\\ 0,&\text{otherwise} \end{cases}\\ s_{i,t} &= \text{Softmax}_i({\mathbf{u}_t}^T\mathbf{e}_i) \end{align} $$Device-Limited Routing对每个 token，其与 MoE 相关的通信频率与其目标专家覆盖的设备数成正比。由于 DeepSeekMoE 中细粒度专家分段，激活的专家数量可能会很大，因此如果我们应用专家并行性，MoE 相关的通信成本将会更高。方法：首先选择在其上具有最高亲和度评分的 M 个设备，然后，在这 M 个设备上的专家进行前 K 选择。Auxiliary Loss for Load Balance设计三种辅助损失：Expert-Level Balance Loss：$$ \begin{align} \mathcal L_{\text{ExpBal}}& = \alpha_1\sum_{i=1}^{N_r} f_iP_i,\\ f_i& = \cfrac{N_r}{K_rT}\sum_{t=1}^T\mathbb 1(\text{Token }t\text{ selects Expert } i),\\ P_i &=\cfrac1T\sum_{t=1}^T s_{i,t} \end{align} $$$\alpha_1$ 为超参数，$\mathbb1(\cdot)$ 是 indicator function，$T$ 为 token 的数量Device-Level Balance Loss：$$ \begin{align} \mathcal L_{\text{DevBal}} &= \alpha_2 \sum_{i=1}^D f_i'P_i',\\ f_i'& = \cfrac{1}{|\mathcal E_i|}\sum_{j\in \mathcal E_i}f_j,\\ P_i' &= \sum_{j\in \mathcal E_i}P_j \end{align} $$$\alpha_2$ 为超参数Communication Balance Loss：确保每个设备的通信是平衡的$$ \begin{align} \mathcal L_{\text{CommBal}}& = \alpha_3\sum_{i=1}^{D} f_i''P_i'',\\ f_i''& = \cfrac{D}{MT}\sum_{t=1}^T\mathbb 1(\text{Token }t\text{ is sent to Device } i),\\ P_i'' &= \sum_{j\in \mathcal E_i} P_j \end{align} $$$\alpha_3$ 是超参数Token-Dropping Strategy为了进一步减少因负载不平衡导致的计算浪费， 在训练期间引入了设备级的 Token-Dropping Strategy：首先计算每个设备的平均计算预算在每个设备上丢弃具有最低亲和力分数的 token，直到达到计算预算。AlignmentReinforcement Learning优化方法：Group Relative Policy Optimization, GRPOTraining Strategy 两阶段的强化学习策略：① 进行推理对齐 ② 进行人类偏好对齐第一阶段的推理对齐中：为代码和数学推理任务训练一个 奖励模型，并通过 奖励模型 的反馈优化策略模型第二阶段，用户偏好对齐：采用一种多奖励框架，有 基于有用性的奖励模型、基于安全性的奖励模型、基于规则性的奖励模型。DeepSeek-V3架构创新：负载平衡策略：auxiliary-loss-free strategy训练目标：Multi-Token Prediction (MTP) objective预训练：FP8 mixed precision training framework通过算法、框架和硬件的共同设计，克服了跨节点 MoE 训练中的通信瓶颈，实现了近乎平面的计算-通信重叠。后训练：Knowledge Distillation将推理能力从 (Chain-of-Thought, CoT) 模型，提炼到标准的大型语言模型。Auxiliary-Loss-Free Load Balancing为每个专家引入一个偏置项 $b_i$ 并将其添加到相应的亲和度分数 $s_{i,t}$ 中，以确定前 K 个路由：$$ g_{i,t}' = \begin{cases} s_{i,t},& s_{i,t} + b_i \in \text{Topk}(\{s_{j,t} + b_j|1\leqslant j \leqslant N_r \}, K_r),\\ 0,&\text{otherwise} \end{cases} $$偏置项仅用于路由器。每个步骤结束时，如果其对应专家过载，我们将偏置项减少 $\gamma$ ，如果其对应的专家负载不足，我们将其增加 $\gamma$，其中 $\gamma$ 是一个超参数，称为 bias update speed。Complementary Sequence-Wise Auxiliary Loss为了防止任何单个序列内的极端不平衡，采用 complementary(互补) sequence-wise balance loss：$$ \begin{align} \mathcal L_{\text{Bal}} &= \alpha\sum_{i=1}^{N_r}f_iP_i\\ f_i &= \cfrac{N_r}{K_rT} \sum_{t=1}^T\mathbb1(s_{i,t}\in\text{Topk}(\{s_{j,t}|1\leqslant j\leqslant N_r\}, K_r))\\ s_{i,t}' &= \cfrac{s_{i,t}}{\sum_{j=1}^{N_r}s_{j,t}},\\ P_i &= \cfrac1T\sum_{t=1}^T s_{i,t}', \end{align} $$$\alpha$ 是超参数，$\mathbb1(\cdot)$ 是 indicator function。No Token-Dropping 由于有效的负载均衡策略，DeepSeek-V3 在整个训练过程中保持了良好的负载均衡。因此，在训练期间，DeepSeek-V3 不会丢弃任何 token。Multi-Token Prediction多标记预测：将预测范围扩展到每个位置的 multiple future tokens。MTP objective 密集化了训练信号能够预先规划其 representations 以更好地预测 future tokens。MTP 的实现中：顺序地预测额外的 token，并再每个预测深度保持完整的因果链。MTP Modules：实现使用 D 个顺序模块来预测 D 个额外 token第 $k$ 个 MTP 模块由 一个 shared embedding layer $\text{Emb}(\cdot)$ 、一个 shared output head $\text{OutHead}(\cdot)$ 、一个 Transformer block $\text{TRM}_k(\cdot)$ 、一个投影矩阵 $M_k\in \mathbb R^{d\times 2d}$ 。第 $i$ 个输入 token $t_i$ ，在第 $k$ 个预测深度，我们首先将第 $(k-1)$ 个深度 $\mathbf h_i^{k-1}\in \mathbb R^d$ 的第 $i$ 个 token 和 第 $(i+k)$ 个 token 的 embedding $\text{Emb}(t_{i+k})\in \mathbb R^d$ 通过 线性投影 进行组合：$$ \mathbf h_i'^{k} = M_k[\text{RMSNorm}(\mathbf h_i^{k-1});\text{RMSNorm}(\text{Emb}(t_{i+k}))] $$$[\cdot;\cdot]$ 表示拼接。当 $k=1$ 时，$\mathbf h_i^{k-1}$ 指的是 Main Model 给出的 representation。每个 MTP module 的 embedding layer 和 main model 共享。组合后的 $\mathbf{h}_i'^k$ 作为第 k 层 Transformer 块的输入，用于生成当前输出的 representation $\mathbf h_i^k$ ：$$ \mathbf h_{1:T-k}^k = \text{TRM}_k(\mathbf h_{1:T-k}'^k) $$$T$ 表示输入序列长度，而 $ _{i:j}$ 表示切片操作（包括 左右边界）。最后，以 $\mathbf h_i^k$ 作为输入，shared output head 将会计算第 $k$ 个额外预测 token $p_{i+1+k}^k\in \mathbb R^V$ 的概率分布，其中 $V$ 是词汇大小：$$ p_{i+k+1}^k = \text{OutHead}(\mathbf h_i^k) $$output head $\text{OutHead}(\cdot)$ 将 representation 线性映射到 logits，然后应用 $\text{Softmax}(\cdot)$ 函数来计算第 $k$ 个额外 token 的预测概率。此外，对于每个 MTP 模块，其输出头与 main model 共享。MTP Training Object对于每个预测深度，我们计算交叉熵损失 $\mathcal L_{\text{MTP}}^k$：$$ \mathcal L_{\text{MTP}}^k = \text{CrossEntropy}(P_{2+k:T+1}^k,t_{2+k:T+1}) = -\cfrac1T\sum_{i=2+k}^{T+1}\log P_i^k[t_i] $$$T$ 表示输入序列的长度，$t_i$ 表示第 $i$ 个位置的真实 token，$P_i^k[t_i]$ 表示由第 $k$ 个 MTP 模块给出的 $t_i$ 的相应预测概率。整体 MTP 损失 $\mathcal L_{\text{MTP}}$ ：作为 DeepSeek-V3的额外训练目标$$ \mathcal L_{\text{MTP}} = \cfrac\lambda D\sum_{k=1}^D \mathcal L_{\text{MTP}}^k $$D 为最大深度，$\lambda$ 为权重因子MTP in Inference推断期间，直接丢弃 MTP 模块，主模块可以独立且正常地运行。可以使用这些 MTP 模块重新用于 预测解码，降低生成延迟。DeepSeek-R1通过大规模强化学习训练的模型在强化学习前纳入了 multi-stage training 和 cold-start data。Reinforcement Learning AlgorithmGroup Relative Policy Optimization该方法省略了通常与 策略模型大小 相同的评估模型，而是从群组得分中估计 基线 baseline。对于每个问题 $q$，GRPO 从旧策略 $\pi_{\theta_{old}}$ 中随机抽取一组输出 $\{o_1, o_2, \cdots, o_G\}$ ，然后通过最大化以下目标来优化策略模型 $\pi_\theta$ ：$A_i$ 是优势，通过与每个组内的输出对应的奖励 (reward) 组 $\{r_1, r_2, \cdots, r_G\}$ 计算得出：$$ A_i = \cfrac{r_i - \text{mean}(\{r_1,r_2, \cdots, r_G\})}{\text{std}(\{r_1, r_2, \cdots, r_G\})} $$奖励是训练信号的来源，决定了强化学习的优化方向。训练 DeepSeel-R1-Zero 采用了一个基于规则的奖励系统，主要由两种类型的奖励组成：准确性奖励格式奖励：要求模型将其思考过程放在 <think> 和 </think> 标签之间。### Cold Start对于 DeepSeek-R1，构建并收集了一小部分 long CoT 数据，以微调模型作为初始 RL actor。收集了数千条冷启动数据，以微调 DeepSeek-V3-Base 作为强化学习的起点。
监督学习（分类与回归，感知机、逻辑回归；神经网络、反向传播、CNN、RNN）；非监督学习（K-means）；强化学习（MDP定义、状态值函数和动作值函数、Q学习及SARSA、DQN）决策树例子：打网球例如 , 分类结果：No决策树概念：表示一个函数，该函数将属性值的向量作为输入，并返回一个“决策”（单个输出值）通过执行一系列测试来做出决策。节点：用属性标记边：用属性值标记叶子：用决策标记决策树表示：决策树表示属性值约束的合取的析取上例中的决策树：(Outlook = Sunny ∧ Humidity = Normal) ∨ (Outlook = Overcast) ∨ (Outlook = Rain ∧ Wind = Weak)任何布尔函数都可以写成决策树通过把真值表中的每一行对应树中的路径通常可以使用小树，然后，有些函数需要指数大的树决策树学习：目标：找到一棵与训练样例一致的小树思路：选择“最重要”属性作为（子）树的根信息论我们将使用 信息增益（information gain）的概念，它是用信息论的基本概念——熵（entropy）来定义的熵，是对随机变量不确定性的度量；信息的获取对应于 熵的减少只有一个值的随机变量没有确定性，其熵被定义为零抛一枚公平的硬币具有 “1 bit” 的熵扔一枚公平的四边形骰子 有 2 bits 的熵，因为需要 2 位来描述4个同样可能的结果之一。熵以概率 $P(v_k)$ 取值 $v_k$ 的随机变量 $V$ 的熵：$$ \mathrm{H}(V) = -\sum_k P(v_k) \log_2 P(V_k) $$以概率 $q$ 为真的布尔随机变量的熵：$$ \mathrm{B}(q) = -(q\log_2 q + (1-q)\log_2(1-q)) $$如果一个训练集熵包含 p 个正例和 n 个负例，那么目标属性在整个训练集上的熵为$$ \mathrm{H}(Goal) = \mathrm{B}(\cfrac{p}{p + n}) $$信息增益具有 d 个不同值的属性 A 将训练集 E 划分为子集 $E_1$ ，...，$E_d$每个子集 $E_k$ 具有 $p_k$ 个正例和 $n_k$ 个负例因此，测试属性 A 后剩余的期望熵为$$ \mathrm{Remainder}(A) = \sum_{k = 1}^d \cfrac{p_k + n_k}{p+n}\mathrm{B}(\cfrac{p_k}{p_k + n_k}). $$对 A 的属性测试的信息增益 (IG) 是熵的期望减少：$$ \mathrm{Gain}(A) = \mathrm{B}(\cfrac{p}{p+n}) - \mathrm{Remainder}(A) $$选择 IG 最大的属性例题：餐厅选择：比较属性 Patron(Pat) 和 属性 Type ：对于训练集， $p = n = 6, \mathrm{B}(\cfrac{6}{12})$$\mathrm{Gain}(Pat) = 1-[\cfrac2{12}\mathrm{B}(\cfrac02) + \cfrac4{12}\mathrm{B}(\cfrac44) + \cfrac6{12}\mathrm{B}(\cfrac26)] \approx 0.541 $$\mathrm{Gain}(Type) = 1-[\cfrac2{12}\mathrm{B}(\cfrac12) + \cfrac4{12}\mathrm{B}(\cfrac24) + \cfrac4{12}\mathrm{B}(\cfrac24) + \cfrac2{12}\mathrm{B}(\cfrac12)] = 0$所以，Pat 是一个更好的分裂属性。事实上，Pat 具有任何属性中的最大增益，并被 DTL 算法选择为根从上述 12 个样例中学到的决策树：Gini 指数熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点如果一个数据集 D 包含来自 n 个类的样本，那么基尼指数定义如下：$$ \mathrm{Gini}(D) = \sum_{i=1}^n p_i(1-p_i) = 1 - \sum_{i=1}^n p_i^2 $$其中，$p_i$ 是 类 $i$ 在 D 中的相对频率基尼指数 反映了 数据集中个随机抽取两个样例，其类别标记不一致的概率基尼指数越小，则数据集纯度越高如果 n = 2, $ \mathrm{Gini}(D) = 2p(1-p)$基于 Gini 指数的属性选择假设属性 A 的取值将 D 划分为 $D_1, ..., D_m$$$ \mathrm{Gini}(D|A) = \sum_{i = 1}^m \cfrac{|D_i|}{|D|} \mathrm{Gini}(D_i) $$具有最小 $\mathrm{Gini}(D|A)$ 的属性被选为分裂节点的属性针对上面餐厅的例题：$$ \begin{aligned} & Patron: D_1:\text{None}, D_2:\text{Some}, D_3: \text{Full} \\ & \mathrm{Gini}(D_1) = 0, \mathrm{Gini}(D_2) = 0, \mathrm{Gini}(D_3) = 2\times \cfrac13\times\cfrac23 = \cfrac49,\\ & \mathrm{Gini}(D|Pat) = \cfrac2{12}\times0 + \cfrac4{12}\times0 + \cfrac6{12}\times \cfrac49 = \cfrac29\\ & Type: \mathrm{Gini}(D_1) = \mathrm{Gini}(D_2) = \mathrm{Gini}(D_3) = \mathrm{Gini}(D_4) = 2\times \cfrac12\times \cfrac12 = \cfrac12\\ & \mathrm{Gini}(D|Type) = (\cfrac2{12} + \cfrac2{12} + \cfrac4{12} + \cfrac4{12}) \times \cfrac12 = \cfrac12 \end{aligned} $$所以 Pat 是一个更好的分裂属性。例题：K 近邻分类给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最近邻的 $k$ 个实例，这k 个实例的多数属于某个类，就把该输入实例分类到这个类中。示例有两类不同样本数据，分别用 蓝色的小正方形 和 红色的小三角形 表示，而图正中间哪个绿色的圆表示待分类的数据：若 k = 3，分类结果为红色；若 k = 5，分类结果为蓝色。距离的度量：两个 $n$ 维向量 $x = (x_1, x_2, ..., x_n)$ 与 $y = (y_1, y_2, ..., y_n)$ 间的闵可夫斯基距离定义为$$ L_p(x, y) = (\sum_{i = 1}^n |x_i - y_i|^p)^{\small{\cfrac1p}} $$当 $p = 2$ 时，称为 欧氏距离（Euclidean distance），即$$ L_2(x, y) = (\sum_{i = 1}^n |x_i - y_i|^2)^{\small{\cfrac12}} $$当 $p = 1$ 时，称为 曼哈顿距离（Manhattan distance），即$$ L_1(x, y) = \sum_{i = 1}^n |x_i - y_i| $$当 $p = \infty$ 时，它是各个坐标距离的最大值，即$$ L_{\infty}(x, y) = \max_i|x_i - y_i| $$归一化最近邻对不同特征的范围是敏感的。可以计算每个维度上的平均值 $\mu_i$ 和 标准差 $\sigma_i$ ，然后取$$ x_i' = \cfrac{x_i - \mu_i}{\sigma_i} $$$k$ 过小：可能过拟合，即对训练数据中的随机特性敏感$k$ 过大：可能欠拟合，即不能捕捉训练数据中的重要的规律$k$ 的最优选择取决于 训练集 的大小 $n$经验公式：一般取 $k = \sqrt{n}$可以使用验证集来选择 $k$$k$ 是一个超参数，不是由学习算法本身来设定的我们可以使用验证集来调优超参数维数灾难可以使用 k-d 树 来加速贝叶斯学习、预测假设 H：关于世界的概率理论$h_1$$h2$...数据 D：关于世界的证据$d_1$$d_2$...贝叶斯学习先验：$Pr(H)$先验概率是在没有任何其他条件或信息的情况下，某个事件发生的概率。在贝叶斯推断中，先验概率通常是我们对某个事件或类别的初始认知或假设。证据：$d = \langle d_1, d_2, ..., d_n\rangle$似然性：$Pr(d|H)$ 似然度（likelihood）是指给定一些模型参数和观测数据时，观测数据出现的概率。简单来说，似然度描述的是模型和数据之间的关系，它是一种在已知模型参数的情况下，描述数据的概率。使用贝叶斯定理计算后验：$$ Pr(H|d) = \alpha Pr(d|H) Pr(H) $$贝叶斯预测假设我们想对未知量 $X$ 进行预测：$$ P(X|d) = \sum_i P(X|d, h_i) P(h_i|d) = \sum_{i} P(X|h_i) P(h_i|d) $$预测是单个假设预测的加权平均值假设是原始数据和预测之间的“中介”示例【糖果】最喜欢的糖果有两种口味：樱桃（cherry），酸橙（lime）。两种口味的包装相同。以不同的比例的袋子出售：100% 樱桃75% 樱桃 + 25% 酸橙50% 樱桃 + 50% 酸橙25% 樱桃 + 75% 酸橙100% 酸橙你买了一袋糖果，但不知道它的口味比例。吃了 $k$ 个糖果后：这个袋子的口味比例是多少？下一个糖果会是什么口味？分析：---->假设 H：$h_1$：100% 樱桃$h_2$：75% 樱桃 + 25% 酸橙$h_3$：50% 樱桃 + 50% 酸橙$h_4$：25% 樱桃 + 75% 酸橙$h_5$：100% 酸橙假设先验 $P(H) = \langle 0.1, 0.2, 0.4, 0.2, 0.1 \rangle$假设糖果是 i.i.d. (独立同分布，identically and independently distributed), i.e.，$P(d|h) = \prod_j P(d_j|h)$假设前 10 个糖果都有 酸橙味：$P(d|h_5) = 1^{10} = 1,$$P(d|h_3) = 0.5^{10} = 0.00097$$P(d|h_1) = 0^{10} = 0$贝叶斯预测示例：---->假设 $d_1 = \langle lime \rangle$ ，$d_2 = \langle lime, lime \rangle$假设$h_1$$h_2$$h_3$$h_4$$h_5$$P(lime\vert h_i)$00.250.50.751$P(h_i)$0.10.20.40.20.1$P(d_1\vert h_i)$00.250.50.751$P(d_2\vert h_i)$0$0.25^2$$0.5^2$$0.75^2$1$P(d_1) = \sum_i P(d_1|h_i) P(h_i) = 0.5$$P(lime|d_1) = \sum_iP(lime|h_i) P(h_i|d_1) = \cfrac1{P(d_1)} \sum_i P(lime | h_i) P(d_1|h_i) P(h_i) = 0.65$$P(h_i|d_1) = \cfrac{P(d_1 | h_i) P(h_i)}{ P(d_1)}$$P(d_2) = \sum_i P(d_2|h_i) P(h_i) = 0.5$$P(lime|d_2) = \cfrac1{P(d_2)} \sum_i P(lime | h_i) P(d_2|h_i) P(h_i) = 0.654$贝叶斯网络的参数学习简单的 ML 示例假设 $h_\theta$ ：$P(\text{cherry}) = \theta$, $P(\text{lime}) = 1-\theta$数据 $d$： $c$ 个樱桃 和 $l$ 个酸橙$P(d|h_\theta) = \theta^c(1-\theta)^l$$\log P(d|h_\theta) = c\log \theta + l \log(1-\theta)$$\cfrac{\mathrm{d}(\log P(d|h_\theta))}{\mathrm{d}\theta} = \cfrac{c}{\theta} - \cfrac{l}{(1-\theta)}$$\cfrac{c}{\theta} - \cfrac{l}{(1-\theta)} = 0 \rightarrow \theta = \cfrac{c}{c+l}$更复杂的 ML 参数学习假设 $h_{\theta, \theta_1, \theta_2}$：$P(F = \text{cherry}) = \theta, P(W = \text{red} | \text{cherry}) = \theta_1, P(W = \text{red} | \text{lime}) = \theta_2$数据 $d$ ：$c$ 个 樱桃：$g_c$ 个绿的 和 $r_c$ 个红的$l$ 个酸橙：$g_l$ 个绿的 和 $r_l$ 个红的$P(\langle \text{lime}, \text{red} \rangle | h_{\theta, \theta_1, \theta_2}) = P(\text{lime}| h_{\theta, \theta_1, \theta_2}) P(\text{red}|\text{lime}, h_{\theta, \theta_1, \theta_2}) = (1-\theta)\theta_2$$P(d|h_{\theta, \theta_1, \theta_2}) = \theta^c(1-\theta)^l \theta_1^{r_c}(1-\theta_1)^{g_c}\theta_2^{r_l}(1-\theta_2)^{g_l}$$\cfrac{c}{\theta} - \cfrac{l}{(1-\theta)} = 0 \rightarrow \theta = \cfrac{c}{c+l}$$\cfrac{r_c}{\theta_1} -\cfrac{g_c}{1-\theta_1} = 0 \rightarrow \theta_1 = \cfrac{r_c}{r_c + g_c}$$\cfrac{r_l}{\theta_2} -\cfrac{g_l}{1-\theta_2} = 0 \rightarrow \theta_2 = \cfrac{r_l}{r_l + g_l}$Laplace 平滑当没有特定结果的样本时，就会发生过拟合的情况例如，目前为止没有吃到樱桃。就会导致 $P(\text{cherry}) = \theta = \cfrac{c}{c+l} = 0$零概率是危险的，它们排除了结果解决方案： Laplace 平滑 => 加1所有的计数加1$P(\text{cherry}) = \theta = \cfrac{c + 1}{c + l + 2} > 0$朴素贝叶斯模型要基于属性 $A_1, ..., A_n$ 预测类 $C$参数：$\theta = P(C = \text{true})$$\theta_{i1} = P(A_i = \text{true} | C = \text{true})$$\theta_{i2} = P(A_i = \text{true} | C = \text{false})$假设：给定 $C$ 下 $A_i$ 之间是独立的符号：$p = \#(c), n = \#(-c), p_i^+ = \#(c, a_i), n_i^+ = \#(c, -a_i),$$ p_i^- = \#(-c, a_i), n_i^- = \#(-c, -a_i)$$P(d|h) = \theta^p(1-\theta)^n \prod_i \theta_{i1}^{p_i^+}\theta_{i2}^{p_i^-}(1-\theta_{i1})^{n_i^+} (1-\theta_{i2})^{n_i^-}$$\theta = \cfrac{p}{p + n}, \theta_{i1} = \cfrac{p_i^+}{p_i^+ + n_i^+ }, \theta_{i2} = \cfrac{p_i^-}{p_i^- + n_i^-}$$P(C|a_1, ..., a_n) = \alpha P(C) \prod_i P(a_i | C)$选择最可能的类别没有决策树准确例题：利用西瓜数据集3.0 训练一个朴素贝叶斯分类器，对测试1 进行分类：线性和逻辑回归人工神经网络模拟大脑进行计算组成：节点（也称单位）对应于神经元连接对应于突触计算：节点间传送的数值信号对应于神经元之间的化学信号节点对数值信号进行修改对应于神经元激活率当输入的线性组合超过某个阈值时，神经元“激活”激活函数应该是非线性的否则网络仅仅表示一个线性函数用以模拟神经元的激活对于“正确的”输入，单元应该是“激活的”：输入接近 1对于“错误的”输入，单位应该是“静息的”：输入接近 0常用的激活函数：双曲正切函数（tanh）$\mathrm{tanh}(x) = \cfrac{e^x - e^{-x}}{e^x + e^{-x}} = \cfrac{2}{1+e^{-2x}} - 1 = 2\mathrm{g}(2x) - 1$ $\mathrm{tanh}'(x) = 1-\mathrm{tanh}^2(x)$修正线性单元 Rectified linear units$\mathrm{ReLU}(x) = \max(0, x)$ 梯度为 0 或 1Soft 版本：$\mathrm{softplus}(x) = \log(1 + e^{-x})$ $\mathrm{softplus}'(x) = \mathrm{sigmoid}(x)$网络结构前馈网络（Feed-forward network）有向非循环图没有内部状态简单从输入计算输出循环网络（Recurrent network）有向循环图具有内部状的动态系统可以记忆信息示例：简单网络，有两个输入，一个具有两个单元的隐藏层，一个输出单元$$ \begin{aligned} a_5 & = \mathrm{g}(w_{3, 5} a_3 + w_{4, 5} a_4)\\ & = \mathrm{g}(w_{3, 5} \mathrm{g}(w_{1, 3} a_1 + w_{2, 3} a_2) + w_{4, 5} \mathrm{g}(w_{1, 4} a_1 + w_{2, 4} a_2)) \end{aligned} $$单层的前馈网络：线性分离器下图有两类数据点决策边界（decision boundary）是一条直线、一个平面或者更高维的面，它将两类数据分离图中决策边界是一条直线。线性决策边界也被称为线性分离器（linear separator）有线性分离器的数据称为线性可分的（linear separable）阈值感知假设空间分类假设 $h_w$ ：$w\cdot x \geq 0 \rightarrow 1,\ w\cdot x<0 \rightarrow 0$即，$h_w(x) = \mathrm{Threshold}(w\cdot x)$ 例如，$-4.9 + 1.7x_1 - x_2 \geq 0 \rightarrow 1$，令 $x_0 = 1$，可表示为 $\mathrm{Threshold}(w\cdot x)$，其中，$w = \langle -4.9, 1.7, -1 \rangle$不是所有的布尔门都是线性可分的，例如异或运算。Sigmoid 感知机表示 “软的”线性分离器分类假设 $h_w(x) = \mathrm{Sigmoid}(w\cdot x)$ 输出是一个 0~1 的数字，可以解释为标签类为 1 的概率。假设在输入空间中形成一个软化边界，对位于该边界中心的输入，该概率为 0.5，随着数据原理边界而接近 0 或 1。损失函数损失函数 $L(x, y, y')$ 定义为当正确答案为 $f(x) = y$，预测 $h(x) = y'$ 的效用损失量通常使用一个简单的版本 $L(y, y')$，它独立于 $x$三个常用的损失函数：绝对值损失：$L_1(y, y') = |y - y'|$平方误差损失：$L_2(y, y') = (y - y')^2$0/1 损失：$L_{0/1}(y, y') = 0$ 如果 $y = y'$ ，否则 $=1$令 $E$ 为样例集，总损失 $L(E) = \sum_{e\in E} L(e)$线性回归给定含有 $N$ 个输入-输出对 样例的训练集 $(x_1, y_1), ..., (x_N, y_N)$每个 $x_j$ 是一个 $n$ 元向量假设为线性函数 $h_w(x) = w_0 + w_1 x_1 + ... + w_nx_n$ 引入一个哑输入属性 $x_0$ ，其值总为 1.因而，$h_w(x) = w\cdot x = \sum_i w_i x_i$找到最匹配这些数据的线性函数 $h_w$梯度下降通过逐步修改参数来搜索连续的权重空间目标是，将损失最小化 —— 梯度下降对权重做任意初始化在每一步，在最陡峭的下坡方向移动一小步，即与函数偏导成比例减少每个权重$$ w_i \gets w_i - \alpha\cfrac{\partial\ \mathrm{Loss}(w)}{\partial\ w_i} $$$\alpha$ 称为学习率（learning rate）重复这一过程，直到收敛到权重空间上某一点位置线性回归公式推导$h_w(x) = w\cdot x = \sum_i w_i x_i$ 平方误差损失：$\mathrm{Loss}(w) = (y - h_w(x))^2$ 求导链式法则：$\cfrac{\partial\ g(f(x))}{\partial\ x} = g'(f(x)) \cfrac{\partial\ f(x)}{\partial\ x}$ $\cfrac{\partial\ \mathrm{Loss}(w)}{\partial\ w_i} = -2(y-h_w(x)) x_i$ $w_i \leftarrow w_i + \alpha(y-h_w(x))x_i$ 梯度下降的变种批梯度下降（batch gradient descent, BGD）极小化在所有训练样例上的损失$w_i \leftarrow w_i + \alpha\sum_j(y_j-h_w(x_j))x_i, j$随机梯度下降（stochastic gradient descent, SGD）在每一步中随机选择少量训练样例感知器算法假设函数是阈值感知器，选择权重 $w$ 以最小化损失函数无法使用梯度下降，因为几乎所有地方的梯度都是零，但仍存在一个简单的权重更新规则。当数据是线性可分的，收敛到一个线性分离器。与线性回归的权重更新规则相同：$w_i \leftarrow w_i + \alpha(y-h_w(x))x_i$ 若输出是正确的，那么权重将不会改变每一次更新随机选择一个样例逻辑回归 Logistic regression假设函数是线性函数的 sigmoid 函数$g(x) = \cfrac{1}{1+e^{-x}}$ $h_w(x) = g(w\cdot x)$ $g' = g(1-g)$ $\mathrm{Loss}(w) = (y - h_w(x))^2$ $\cfrac{\partial \mathrm{Loss}(w)}{\partial w_i} = -2(y-h_w(x))g'(w\cdot x)x_i = -2(y - h_w(x)) h_w(x)(1-h_w(x))x_i$ $w_i \leftarrow w_i + \alpha(y - h_w(x)) h_w(x)(1-h_w(x))x_i$多层前馈神经网络感知器只能表示线性分离器多层网络，可以表示任意函数多层网络把两个平行但具有反向峭壁的 sigmoid 单元相加形成一个山脊把两个交叉的山脊相加形成一个山包通过把不同高度的山包拼接在一起，可以逼近任意函数例子：表示布尔函数的神经网络布尔函数：$x_1 \land \lnot x_2 \lor x_2 \land x_3$ 任意布尔函数可以转换为合取范式（CNF）或析取表达式（DNF），因而可以用具有一个隐藏层的神经网络表示权重训练一个样例集合，每个样例由输入向量 $x$ 和 输出向量 $y$ 组成平方误差损失：$\mathrm{Loss} = \sum_k \mathrm{Loss}_k, \mathrm{Loss}_k = (y_k - a_k)^2$ ，其中 $a_k$ 是神经网络的第 k 个输出权重更新公式：$w_{ij} = w_{ij} - \alpha\cfrac{\partial \mathrm{Loss}}{\partial w_{i,j}}$ 给定任意的网络结构，如何高效地计算梯度：反向传播算法前向阶段:把输入向前传播以计算每个单元的输出$a_j$ 是单元 j 的输出：$a_j = g(in_j)$，其中，$in_j = \sum_i w_{ij} a_i$反向阶段：把误差反向传播输出单元 $j$ ：$\Delta_j = g'(in_j) (y_j - a_j)$隐藏层单元 $i$ ：$\Delta_i = g'(in_i)\sum_j w_{ij}\Delta_j$多层网络的后向传播算法输出层：$$ \begin{aligned} \cfrac{\partial \mathrm{Loss}_k}{\partial w_{j,k}} &= -2(y_k - a_k)\cfrac{\partial a_k}{\partial w_{j, k}} = -2(y_k - a_k)\cfrac{\partial g(in_k)}{\partial w_{j, k}}\\ &= -2(y_k - a_k)g'(in_k)\cfrac{\partial in_k}{\partial w_{j, k}} = -2(y_k - a_k) g'(in_k)\cfrac{\partial (\sum_j w_{j,k}a_j)}{\partial w_{j, k}}\\ &= -2(y_k - a_k)g'(in_k)a_j = -2a_j \Delta_k \end{aligned} $$隐藏层：$$ \begin{aligned} \cfrac{\partial \mathrm{Loss}_k}{\partial w_{i,j}} &= -2(y_k - a_k)\cfrac{\partial a_k}{\partial w_{i,j}} = -2(y_k - a_k)\cfrac{\partial g(in_k)}{\partial w_{i,j}}\\ &= -2(y_k - a_k)g'(in_k)\cfrac{\partial in_k}{\partial w_{i,j}} = -2\Delta_k \cfrac{\partial (\sum_j w_{j, k}a_j)}{\partial w_{i,j}}\\ &= -2\Delta_k w_{j,k} \cfrac{\partial a_j}{\partial w_{i,j}} = -2\Delta_k w_{j,k}\cfrac{\partial g(in_j)}{\partial w_{i,j}}\\& = -2\Delta_k w_{j,k}g'(in_j)\cfrac{\partial in_j}{\partial w_{i,j}}\\ &= -2\Delta_k w_{j,k} g'(in_j) \cfrac{\partial (\sum_{i} w_{i,j} a_i)}{\partial w_{i,j}} = -2\Delta_k w_{j,k} g'(in_j)a_i \end{aligned} $$如果，上面的公式针对的是 一个隐藏层的神经网络（就是后面的例题的那样），那么上面的推导应该没有问题，但是原ppt的最后一步有点问题，我觉得最后一步的的公式应该是：$$ \sum_k \cfrac{\partial \mathrm{Loss}_k}{\partial w_{i, j}} = -2a_i\Delta_j $$前向和后向阶段：前向阶段：把输入向前传播以计算每个单元的输出$a_j$ 是单元 j 的输出：$a_j = g(in_j)$，其中，$in_j = \sum_i w_{ij} a_i$后向阶段：反向传播误差 Propagate errors backward对于 输出单元 j：$$ \Delta_j = g'(in_j)(y_j - a_j) = a_j(1-a_j)(y_j - a_j) $$对于隐藏层单元 i：$$ \Delta_i = g'(in_i)\sum_j w_{ij}\Delta_j = a_i(1-a_i)\sum_j w_{ij}\Delta_j $$权重更新：$$ w_{ij} \gets w_{ij} + \alpha a_i \Delta_j $$网络结构给定数值：前向传递过程：$$ \begin{aligned} in_{h_1} &= w_1 i_1 + w_2 i_2 + b_1 = 0.05\times0.15 + 0.10\times0.20 + 0.35 = 0.3775\\ out_{h_1} &= g(in_{h_1}) = \frac{1}{1 + e^{-0.3775}} = 0.593269992 \\ out_{h_2} &= 0.596884378\\ in_{o_1} &= w_5 out_{h_1} + w_6 out_{h_2} + b_2 = 1.105905967\\ out_{o_1} &= g(in_{o_1}) = \cfrac{1}{1 + e^{-1.105905967}} = 0.75136507\\ out_{o_2} &= 0.772928465 \end{aligned} $$反向传递过程：假设$\alpha = 0.5$$$ \begin{aligned} \Delta_{o_1} &= g(in_{o_1})(1-g(in_{o_1}))(y_{o_1}-g(in_{o_1}))\\& = 0.75136507(1-0.75136507)(0.01-0.75136507) = -0.138498562\\ w_5^+ &= w_5 + \alpha \cdot out_{h_1}\cdot \Delta_{o_1} = 0.5 - 0.5\times 0.593269992\times 0.138498562 = 0.35891648 \\ w_6^+ &= w_6 + \alpha \cdot out_{h_2} \cdot \Delta_{o_1} = 0.408666186\\ \Delta_{o_2} &= g(in_{o_2})(1-g(in_{o_2}))(y_{o_2}-g(in_{o_2})) = 0.0380982366\\ w_7^+ &= w_7 + \alpha \cdot out_{h_1}\cdot \Delta_{o_2} = 0.511301270\\ w_8^+ &= w_8 + \alpha \cdot out_{h_2}\cdot \Delta_{o_2} = 0.561370121\\ \Delta_{h_1} &= g'(in_{h_1})(w_5 \Delta_{o_1} + w_7\Delta_{o_2}) = g(in_{h_1})(1-g(in_{h_1}))(w_5 \Delta_{o_1} + w_7\Delta_{o_2})\\ &= -0.241300709\times0.036350306\\ w_1^+ &= w_1 + \alpha \cdot i_1 \cdot \Delta_{h_1} = 0.15-0.5\times0.05\times0.241300709\times0.036350306 \\&=0149780716\\ w_2^+ &= 0.19956143\\ w_3^+ &= 0.24975114\\ w_4^+ &= 0.29950229 \end{aligned} $$深度神经网络定义：具有许多隐藏层的神经网络高表达能力挑战：如何训练深度神经网络如何避免过拟合深度神经网络，经常受到梯度消失的影响避免梯度消失：修正线性单元（Rectified Linear Units, ReLU）和最大化单元（Maxout Units）Sigmoid 单元$g(x) = \cfrac{1}{1-e^{-x}}$$g' = g(1-g)$避免过拟合：Dropout（随机失活）卷积神经网络 神经元的三维体积ConvNet 层中的神经元以三维方式排列：宽度、长度、深度例如：对于一个 100*100 的输入图像，输入体积的尺寸是 $100\times 100\times3$CNN 的每一层接受一个输入的 3D 体积，并将其转换为一个输出的 3D 体积。有三个超参数控制输出体积的大小：深度、步长和零填充输出体积的深度对应于滤波器（即卷积核）的数量，每个特征对应一个滤波器步长：滤波器滑动的距离零填充：在输入体积的边界周围填充零的大小卷积层接受一个大小为 $W_1 \times H_1 \times D_1$ 的体积需要 四个超参数：滤波器数量 K它们的空间大小 F步长 S零填充的数量 P产生尺寸为 $W_2 \times H_2 \times D_2$ 的体积，其中：$W_2 = \cfrac{W_1 - F + 2P}{S} + 1$$W_2 = \cfrac{H_1 - F + 2P}{S} + 1$$D_2 = K$在输出体积中，第 d 个深度切片通过对输入体积进行 第 d 个滤波器的卷积运算得到，然后再加上第 d 个偏置项池化层在连续的卷积层之间经常会插入池化层它的作用是使用最大值操作表示的空间尺寸，以减少网络中的参数和计算量，从而控制过拟合。池化层对输入的每个深度切片进行独立操作，因而深度维度保持不变。输入-输出：接受一个大小为 $W_1 \times H_1 \times D_1$ 的体积需要两个超参数：空间大小 F步长 S产生尺寸为 $W_2 \times H_2 \times D_2$ 的体积，其中：$W_2 = \cfrac{W_1 - F}{S} + 1$$W_2 = \cfrac{H_1 - F}{S} + 1$$D_2 = D_1$强化学习强化学习与其他学习范式的不同之处？没有监督者，只有奖励信号。反馈是延迟的，不是即时的。时间非常重要（顺序性、非独立同分布数据）智能体的行动影响影响其接收到的后续数据。经典规划：给定一个初始状态和一组具有确定效果的动作，确定一个动作序列以实现目标不确定规划：初始状态和动作效果是不确定的，可能需要概率建模规划：给定环境的模型，智能体对模型进行计算而改进其策略，不与环境交互强化学习：初始时，环境是未知的，智能体通过与环境交互而改进策略基础知识状态state s，当前环境的状态行动 action a，智能体 Agent 做出的行动以超级玛丽为例：决策 policy π根据环境决定 agent 的行动policy 定义为一个概率函数：$\pi(a|s) = \mathbb{P}(A = a | S = s)$ 观察状态 state S = s 之后，智能体根据决策以一定概率做出一个行动 action A。奖励 reward R以超级玛丽游戏为例：选择一个硬币： R = 1胜利：R = 100000游戏结束：R = -100000无事发生：R = 0状态转移 state transition旧状态，根据智能体做出的行动，发生状态的改变，得到新状态状态转移，一般认为是随机的，随机性来自环境。把状态转移用 $\Bbb{P}$ 函数表示：$p(s'|s, a) = \Bbb{P}(S' = s|S = s, A = a)$强化学习的随机性：给定状态 s，行动可以是随机性状态转移的随机性使用 AI 玩游戏观察画面（状态 $s_1$）做出行动 action $a_1$观察新的画面（状态 $s_2$）和奖励 $r_1$做出行动 action $a_2$...最后得到游戏的轨迹(state, action, reward) trajectory:$s_1, a_1, r_1, s_2, a_2, r_2, ···, s_T, a_T, r_T$返回 Return定义：回报Return(未来的累计奖励 cumulative future reward)$U_t = R_t + R_{t+1} + R_{t+2} + R_{t+3} + \cdots$ 定义：折扣回报 Discounted return (cumulative discounted future reward)折扣率 $\gamma$ ：$U_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \cdots$ （常用的）在时间步 $t$ ，回报 $U_t$ 是随机的，随机性来源于 动作随机性，状态转移随机性。对任意 $i\geqslant t$，奖励 $R_i$ 依赖于 $S_i$ 和 $A_i$行动价值函数 Action-Value Function $Q(s, a)$ 定义：决策 $\pi$ 的行动价值函数 Action-Value Function for policy $\pi$$Q_{\pi}(s_t, a_t) = \Bbb{E}[U_t | S_t = s_t, A_t = a_t]$回报 $U_t$ 依赖于行动 $A_t, A_{t+1}, A_{t+2},...$ 和状态 $S_t, S_{t+1}, S_{t+2},...$由于 $U_t$ 是随机变量，不知道具体的 $U_t$ 是什么，但是可以对 $U_t$ 求期望，把里面的随机性都用积分得到期望。这个期望，是状态 $S_t$ 和 行动 $A_t$ 的函数。行动是随机的：$\Bbb{P}[A = a | S = s] = \pi(a|s)$ （决策函数 policy function）状态是随机的：$\Bbb{P}[S' = s' | S = s, A = a] = p(s'|s, a)$ （状态转移 State transition）上面两个是行动和状态的概率密度函数，变量为 $a_t$ 和 $s_t$，而其他的 $a_{t+T}, s_{t+T}$ 都可以通过概率密度函数利用积分公式除去，$a_t$ 和 $s_t$ 没有被积分积掉，而是被当作随机变量，期望依赖于这两个变量，根据这两个变量的数值得到相应的Q值。动作价值函数与决策 policy $\pi$ 有关。定义：最优动作价值函数 Optimal action-value function$$ Q^* (s_t, a_t) = \max_\pi Q_\pi(s_t, a_t) $$此时，由于是改变 $\pi$ 得到的最大化值，所以消除了变量 $\pi$ ，因为不管 $\pi$ 如何优化，都不会超过这个值。因此，动作价值函数的值就只与 $s_t$ 和 $a_t$ 有关又由于当前状态 $s_t$ 已知，所以动作价值函数 $Q^* (s_t, a_t)$ 可以用来判定行动 action 的价值。所以 智能体 可以根据 最优动作价值函数 得到期望最大的行动定义：状态价值函数 Action Value Function$$ V_\pi(s_t) = \Bbb{E}_A [Q_\pi (s_t, A)] $$$V_\pi$ 可以告诉我们当前状态好不好，这里的期望是关于随机变量 A （$A\sim \pi(\cdot|s_t)$）求的。如果动作是离散的：$$ V_\pi(s_t) = \Bbb{E}_A [Q_\pi (s_t, A)] = \sum_a \pi(a|s_t) \cdot Q_\pi (s_t, a) $$如果动作是连续的：$$ V_\pi(s_t) = \Bbb{E}_A [Q_\pi (s_t, A)] = \int \pi(a|s_t) \cdot Q_\pi (s_t, a) \mathrm{d} a $$动作价值函数 Action-value function:$Q_{\pi}(s_t, a_t) = \Bbb{E}[U_t | S_t = s_t, A_t = a_t]$对于 策略 $\pi$ ，$Q_\pi(s, a)$ 评估在当前状态 s 下，做出动作 a 的价值状态价值函数 State-value function：$V_\pi(s_t) = \Bbb{E}_A [Q_\pi (s_t, A)]$是把 $Q_\pi(s, a)$ 对 $a$ 求期望以消除变量 $a$，所以状态价值函数与动作无关对于给定 $\pi$，$V_\pi(s)$ 用来评估当前状态 $s$ 的好坏如何利用 AI 控制智能体？假设我们有一个好的策略 $\pi(a|s)$ 【策略学习】观察状态 $s_t$随机采样：$a_t \sim \pi(\cdot, s_t)$假设我们直到最优动作价值函数 $Q^*(s, a)$ 【价值学习】观察状态 $s_t$选择动作使得 最优动作价值函数最大：$a_t = \mathrm{argmax}_a Q^*(s_t, a)$DQN就是利用神经网络近似 $Q^*(s, a)$ 函数目标：赢得游戏（最大化最终的奖励）问题：如果我们知道 $Q^*(s, a)$ ，什么是最好的动作？显然，最好的动作是 $a^* = \mathrm{argmax}_a Q^*(s,a)$ 挑战：我们不知道 $Q^*(s, a)$解决：Deep Q Network(DQN)使用 神经网络 $Q(s, a; w)$ 去近似 $Q^*(s, a)$DQN 结构：输入大小：可以是屏幕的大小（超级玛丽游戏画面）输出大小：动作的维度示例：Temporal Difference learning（TD learning ）$$ Q(s_t, a_t; \mathbf{w}) \approx r_t + \gamma\cdot Q(s_{t+1}, a_{t+1}; \mathbf{w}) $$$r_t$ 真实观测的值$Q(s_{t+1}, a_{t+1}; \mathbf{w})$ 是预测的值$U_t = R_t + \gamma \cdot U_{t+1}$ TD learning for DQN：DQN 的输出，$Q(s_{t}, a_{t}; \mathbf{w})$，是 $\Bbb{E}[U_t]$ 的估计DQN 的输出，$Q(s_{t+1}, a_{t+1}; \mathbf{w})$，是 $\Bbb{E}[U_{t+1}]$ 的估计因此，$Q(s_{t}, a_{t}; \mathbf{w}) \approx \Bbb{E}[R_t + \gamma\cdot ]Q(s_{t+1}, a_{t+1}; \mathbf{w})$ $Q(s_{t}, a_{t}; \mathbf{w})$ 是 t-1 时刻，对 t 时刻的估计。到了 t 时刻，奖励 $r_t$ 被观测出来了。使用 TD learning 训练 DQN：预测：$Q(s_{t}, a_{t}; \mathbf{w}_t)$TD target：$$ \begin{aligned} y_t & = r_t + \gamma \cdot Q(s_{t+1}, a_{t+1}; \mathbf{w}_t) \\ & = r_t + \gamma \cdot \max_\alpha Q(s_{t+1}, a; \mathbf{w}_t) \end{aligned} $$损失函数 Loss：$L_t = \cfrac12[Q(s_{t}, a_{t}; \mathbf{w}) - y_t]^2$梯度下降：$\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \cdot \cfrac{\partial L_t}{\partial \mathbf{w}} |_{\mathbf{w} = \mathbf{w}_c}$折扣回报 Discounted Return$$ \begin{aligned} U_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t+3} + \gamma^4 R_{t+4} + \cdots \\ &= R_t + \gamma (R_{t+1} + \gamma^1 R_{t+2} + \gamma^2 R_{t+3} + \gamma^3 R_{t+4} + \cdots) \\ & = R_t + \gamma \cdot U_{t+1} \end{aligned} $$计算 TD Target假设 $R_t$ 依赖于 $(S_t, A_t, S_{t+1})$$$ \begin{aligned} Q_\pi(s_t, a_t) &= \Bbb{E} [U_t | s_t, a_t]\\ & = \Bbb{E} [R_t + \gamma \cdot U_{t+1}| s_t, a_t]\\ & = \Bbb{E} [R_t | s_t, a_t] + \gamma \cdot \Bbb{E} [U_{t+1} | s_t, a_t]\\ & = \Bbb{E} [R_t | s_t, a_t] + \gamma \cdot \Bbb{E} [Q_\pi(S_{t+1}, A_{t+1}) | s_t, a_t]\\ \end{aligned} $$$Q_\pi(s_t, a_t) = \Bbb{E} [R_t + \gamma \cdot Q_\pi(S_{t+1}, A_{t+1}) ]$ ，对于所有的 $\pi$期望很难计算，因此，选择近似。$R_t$ 近似为 观测值 $r_t$$Q_\pi(S_{t+1}, A_{t+1})$ 中，以观测值 $s_{t+1}, a_{t+1}$ 代替：$Q_\pi(s_{t+1}, a_{t+1})$得到 TD Target：$y_t = r_t + \gamma \cdot Q_\pi(s_{t+1}, a_{t+1})$TD learning：希望 $Q_\pi(s_t, a_t)$ 不断接近 $y_t$$Q_\pi(s_t, a_t)$ 完全是估计值$y_t$ 包含有一定的真实值，可以直接看成真实值让 $Q_\pi(s_t, a_t)$ 逼近总结定义：最优动作价值函数 Optimal action-value function $Q^*(s_t, a_t) = \max_\pi \Bbb{E}[S_t = s_t, A_t = a_t]$ 实际上，我们并没有 $Q^*$ 函数，基于价值的强化学习就是训练近似一个 $Q^*$ 函数DQN：用一个神经网络 DQN 近似 $Q^*$ 函数$Q(s, a; \mathbf{w})$ 是一个使用参数 $\mathbf{w}$ 的神经网络输入：观察到的状态 $s$输出：每个动作 $a\in \mathcal{A}$ 的分数初始状态的 DQN 是随机， Agent 根据 DQN 的指导不断尝试，有时获得正奖励，有时获得负奖励。通过奖励来更新模型的参数，让模型越来越好。使用 TD learning 来利用奖励更新模型。算法：TD learning 的一次迭代过程：观察状态 $S_t = s_t$ 和 已经执行的动作 $A_t = a_t$把 状态和动作作为DQN的输入，让 DQN 为动作打分，把输出作为 $q_t = Q(s_t, a_t; \mathbf{w}_t)$用反向传播对 DQN 求导：$\mathbf{d}_t = \cfrac{\partial\ Q(s_t, a_t, \mathbf{w})}{\partial \ \mathbf{w}}\big|_{\mathbf{w}=\mathbf{w}_t}$环境更新 新的状态$s_{t+1}$ 和 奖励 $r_t$计算 TD target： $y_t = r_t + \gamma \cdot \max_a Q(s_{t+1}, a; \mathbf{w}_t)$梯度下降，更新参数：$\mathbf{w}_{t+1} = \mathbf{w}_t - \alpha \cdot (q_t - y_t)\cdot \mathbf{d}_t$强化学习问题形式化：单个智能体的强化学习问题可以被归结为 马尔可夫决策过程。马尔可夫决策过程是 顺序决策 的数学模型，用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报。单智能体强化学习问题可以形式化定义为马尔可夫决策过程MDP六元组 $(S， A， R， T， P_0,\gamma)$ 。S 表示状态空间A 表示动作空间R = R(s, a) 表示奖励函数T: $S\times A \times S \rightarrow [0,1]$ 表示状态转移函数$P_0$ 表示初始状态分布$\gamma$ 是折扣因子马尔可夫决策过程（MDP）MDP(Markov Decision Process) 包括：状态集合 S动作集合 AP(s'|s,a) 指定了智能体处于状态 s 并执行动作 a 时转移到状态 s' 的概率R(s, a, s') 是智能体处于状态 s，执行动作 a 并最终进入状态 s' 时所获得的预期奖励。$0\leqslant \gamma \leqslant 1$ 是折扣因子马尔可夫过程具有马尔可夫性质的有限随机状态序列$S_1,S_2,...$ ：$P(S_{t+1}|S_t) = P(S_{t+1}|S_1, ..., S_t)$ 当前状态只会由上一个状态过程。转移概率：状态之间转化的概率马尔可夫奖励过程 = 马尔可夫过程 + 奖励（随状态转移而产生）强化学习的形式化：给定一个环境 $MDP(S, A, P, R, \gamma)$ ，其中 P 和 R 对于智能体是未知的，寻找一个最大化 $V_\pi(s_0)$ 和 策略 $\pi$ 强化学习的主要方法：基于值(Value-Based)基于策略(Policy-Based)演员-评论家(Actor-Critic)Sarsa 算法表格形式 Tabular Version我们想要学习 $Q_\pi(s, a)$假设 状态和动作的数量是有限的画一张表格，学习每一项Sarsa(tabular version)观察一个 transition $(s_t, a_t, r_t, s_{t+1})$采样 $a_{t+1} \sim \pi(\cdot|s_{t+1})$ ，$\pi$ 是一个策略函数TD target：$y_t = r_t + \gamma\cdot Q_\pi(s_{t+1}, a_{t+1})$$r_t$ 是真实得到的奖励，$Q_\pi(s_{t+1}, a_{t+1})$ 是预测值，是表格对应的值TD error：$\delta_t = Q_\pi(s_t, a_t) - \gamma_t$更新 $Q_\pi(s_t, a_t) \leftarrow Q_\pi(s_t, a_t) - \alpha\cdot \delta_t$ （就是表格中 对应的值）Sara 的名字：使用 $(s_t, a_t, r_t, s_{t+1}, a_{t+1})$ 更新 $Q_\pi$State-Action_Reward-State-Action神经网络版本 Neural Network Version利用 价值网络 $q(s, a; \mathbf{w})$ 近似 $Q_\pi(s, a)$ 价值网络$q$ 和 $Q_\pi$ 函数都和 策略 $\pi$ 有关价值网路 $q(s, a; \mathbf{w})$ ，输入是状态 $s$ ，输出所有动作的价值。TD target: $y_t = r_t + \gamma \cdot q(s_{t+1}, a_{t+1}; \mathbf{w})$TD error：$\delta_t = q(s_t, a_t; \mathbf{w}) - y_t$Loss：$\cfrac{\delta_t^2}{2}$对损失函数关于 $\mathbf{w}$ 求梯度，Gradient：$\cfrac{\partial \delta_t^2 /2}{\partial \mathbf{w}} = \delta_t \cdot \cfrac{\partial q(s_t, a_t; \mathbf{w})}{\partial \mathbf{w}}$做梯度下降更新 $\mathbf{w}$ Gradient descent：$\mathbf{w} = \mathbf{w} - \alpha\cdot \delta_t \cdot \cfrac{\partial q(s_t, a_t; \mathbf{w})}{\partial \mathbf{w}}$总结：学习 动作价值函数 $Q_\pi$表格形式 Tabular version（直接学习 $Q_\pi$）有限状态和动作画一个表格，使用 sarsa 更新表格价值网路版本 Value Network version（函数近似）使用 价值网络 $q(s, a; \mathbf{w})$ 近似 $Q_\pi$ 函数使用 Sarsa 更新参数 $\mathbf{w}$应用 actor-critic methodQ learningQ-learning 用来训练最优动作价值函数 optimal action-value function $Q^*(s, a)$TD target：$y_t = r_t + \gamma \cdot \max_a Q^*(s_{t+1}, a)$使用 Q-learning 更新 DQN已证明：对于所有的 $\pi$，$Q_\pi(s_t, a_t) = \Bbb{E}[R_t + \gamma\cdot Q_\pi(S_{t+1}, A_{t+1})]$假设 $\pi$ 是最优策略 $\pi^*$ ，则：$$ Q_{\pi^*}(s_t, a_t) = \Bbb{E}[R_t + \gamma\cdot Q_{\pi^*}(S_{t+1}, A_{t+1})] $$$Q_{\pi^*}$ 和 $Q^*$ 都是 最优动作价值函数 optimal action-value function.$$ Q^*(s_t, a_t) = \Bbb{E}[R_t + \gamma\cdot Q^*(S_{t+1}, A_{t+1})] $$动作 $A_{t+1}$ 通过$$ A_{t+1} = \mathrm{argmax}_a Q^*(S_{t+1}, a) $$计算得到，即给定状态 $S_{t+1}$，选择最优动作价值函数值最高的动作 $A_{t+1}$因此：$Q^*(S_{t+1}, A_{t+1}) = \max_a Q^*(S_{t+1}, a)$ ，因为 $A_{t+1}$ 是最优动作，所以可以最大化 $Q^*$ 函数。$$ Q^*(s_t, a_t) = \Bbb{E}[R_t + \gamma\cdot \max_a Q^*(S_{t+1}, a)] $$由于期望很难计算，所以直接使用观测值 $r_t$ 代替 $R_t$ ,$s_{t+1}$ 代替 $S_{t+1}$ 于是得到期望的蒙特卡洛近似：$$ \Bbb{E}[R_t + \gamma\cdot \max_a Q^*(S_{t+1}, a)] \approx r_t + \gamma\cdot \max_a Q^*(s_{t+1}, a) \rightarrow \text{TD target } y_t $$Q-learning(tabular version)观察一个 transition $(s_t, a_t, r_t, s_{t+1})$TD target：$y_t = r_t + \gamma\cdot \max_a Q^*(s_{t+1}, a)$TD error：$\delta_t = Q^*(s_t, a_t) - y_t$更新：$ Q^*(s_t, a_t) \leftarrow Q^*(s_t, a_t) - \alpha\cdot \delta_t$Q-learning(DQN version)使用 DQN，$Q(s, a; \mathbf{w})$ 神经网络的输入是 状态 s，输出是对所有动作的打分DQN 可以控制 agent ：$a_t = \mathrm{argmax}_a Q(s_t, a; \mathbf{w})$ 让 agent 执行 最优动作 $a_t$利用收集到的 transitions 跟新 DQN观察一个 transition $(s_t, a_t, r_t, s_{t+1})$TD target：$y_t = r_t + \gamma\cdot \max_a Q(s_{t+1}, a; \mathbf{w})$TD error：$\delta_t = Q^*(s_t, a_t; \mathbf{w}) - y_t$利用梯度下降更新 $\mathbf{w}$ ：$\mathbf{w} \leftarrow \mathbf{w} - \alpha \cdot \delta_t \cdot \cfrac{\partial Q(s_t, a_t; \mathbf{w})}{\partial \mathbf{w}}$基于值的方法给定一个策略 $\pi$ ：$Q_\pi(s, a)$$V_\pi(s)$最优策略的值：$Q^*(s, a)$$V^*(s)$ ：在状态 s 下遵循最优策略的期望值$Q^*$ 和 $V^*$ ：$Q^*(s, a) = \sum_{s'} P(s'|a, s)(R(s, a, s') +\gamma V^*(s'))$ $V^*(s) = \max_a Q^*(s, a)$ $\pi^*(s) = \mathrm{argmax}_a Q^*(s, a)$贝尔曼方程（Bellman equations）$$ V^*(s) = \max_a \sum_{s'} P(s' | a, s) (R(s, a, s') + \gamma V^* (s'))\\ Q^*(s, a) = \sum_{s'} P(s'|a, s)(R(s, a, s') + \gamma \max_{a'} Q^*(s', a'))) $$我的想法：可以先求 $Q^*(s, a)$ ，然后利用 $V^*(s) = \max_a Q^*(s, a)$ 求得 $V^*(s)$ 值迭代如果有 n 个状态，那么就会有 n 个贝尔曼方程，每个状态对应一个方程线性代数技术 可以快速求解线性方程。然而这些方程不是非线性的，因为 max 操作符不是线性操作符。可以使用一种迭代的方法。我们可以从任意的初始值开始计算效用。令 $V_i(s)$ 表示第 i 次迭代时 状态 $s$ 的值使用贝尔曼更新：$$ V^*(s) = \max_a \sum_{s'} P(s' | a, s) (R(s, a, s') + \gamma V^* (s')) $$如果我们无限次使用贝尔曼更新，我们保证会达到一个均衡点，在这种情况下，最终的效用值必须是贝尔曼方程的解。异步值迭代不要对所有状态进行扫描，而是逐个更新每个状态的值函数。如果在极限情况下，每个状态和动作都会被无限次访问，则会收敛到最优值函数可以存储 V[s] 或 Q[s, a]无限重复以下步骤：选择状态 s$V[s] \gets \max_a\sum_{s'} P(s'|s, a) (R(s, a, s') + \gamma V[s'])$无限重复以下步骤：选择状态 s，动作 a$Q[s, a] \gets \sum_{s'} P(s'|s, a) (R(s, a, s') + \gamma \max_{a'} Q[s', a'])$异步值迭代比值迭代收敛更快。经验异步值迭代：$Q[s, a] \gets r + \gamma \max_{a'} Q[s', a']$
第一章绪论人工智能的定义、概况； 人工智能主要学派及主要观点。人工智能的定义人工智能（AI）是研究理解和模拟人类智能、智能行为及其规律的一门学科。主要任务：建立智能信息处理理论，进而设计可以展现某些近似人类智能行为的计算系统。主要学派逻辑学派（符号主义方法）认知基元是符号，智能行为通过符号操作来实现，以 Robinson 提出的归结原理为基础，以 LISP 和 Prolog 语言为代表。着重问题求解中启发式搜索和推理过程，在逻辑思维的模拟方面取得成功，如自动定理证明和专家系统。人工智能源于数理逻辑数理逻辑的形式化方法和计算机科学不谋而合。正是数理逻辑对计算的追根寻源，导致了第一个计算的数学模型 图灵机 的诞生，它被公认为现代数字计算机的祖先。仿生学派（连接主义方法）人的思维基元是神经元，把智能理解为相互连结的神经元竞争与协作的结果，以人工神经网络为代表。其中，反向传播网络模型（BP神经网络）和 Hopfield 网络模型 更为突出着重结构模拟，研究神经元特征、神经元网络拓扑，学习规则、网络的非线性动力学性质和自适应的协同行为。认为 人工智能源于仿生学，特别是对人脑的研究。MP 模型，开创了用电子装置模仿人脑结构和功能的新途径。它从神经元开始进而研究神经网络模型和脑模型，开辟了人工智能的又一发展道路。控制论学派（行为主义方法）认为 人工智能源于控制论。控制论把神经系统的工作原理与信息理论、控制理论、逻辑以及计算机联系起来。反馈是控制论的基石，没有反馈就没有智能。通过目标与实际行为之间的误差来消除此误差的控制策略。控制论导致机器人研究，机器人是 “感知-行为”模式，没有知识的智能；强调系统与环境的交互，从运行环境中获取信息，通过自己的动作对环境施加影响。代表工作：强化学习，演化算法，Brooks 的六足行走机器人第二章 知识表示和推理命题逻辑语法、语义；谓词逻辑语法、语义；谓词推理规则（等价式、永真蕴含式）以及应用；命题及谓词逻辑归结推理（子句、子句集、置换与合一、答案提取）命题——具有真假意义的陈述句。命题有两种类型：原子命题复合命题——由联结词、标点符号和原子命题等复合构成的命题。所有这些命题都应具有确定的真值。当命题变元P用一个特定的命题取代时，P才能确定真值，这时也称为对P进行指派。当命题变元表示原子命题时，该变元称为原子变元。命题逻辑语法、语义命题逻辑的符号命题常元：True(T) 和 False(F)命题符号：P、Q、R 等；联结词：¬（否定）；∧（合取）；∨（析取）； →（蕴含）；↔（等价）。括号：()语义复合命题的意义是命题组成成份的函数。联结词的语义可以定义如下：¬P为真，当且仅当P为假。P∧Q为真，当且仅当P和Q都为真。P∨Q为真，当且仅当P为真，或者Q为真。P→Q为真，当且仅当P为假，或者Q为真。P↔Q为真，当且仅当P→Q为真，并且Q→P为真。公式A称为永真式或重言式(tautology)，如果对任意指派α，α均弄真A，即α(A)=T。公式A称为可满足的(satisfiable)，如果存在指派α使α(A)=T，否则称A为不可满足的(unsatisfiable)，或永假式。设A为含有命题变元p的永真式，那么将A中p的所有出现均代换为命题公式B，所得公式(称为A的代入实例)仍为永真式。合取范式：命题公式 B 称为公式 A 的 合取范式，如果 B ↔ A，且 B 呈如下形式：$C_1∧C_1∧\cdots ∧ C_m$ ，其中 $C_i$ (i=1,2,...,m) 形如 $L_1∨L_2∨\cdots∨L_n$ ，$L_j$ 为原子公式或原子公式的否定，称 $L_j$ 为文字。析取范式：命题公式 B 称为公式 A 的 合取范式，如果 B ↔ A，且 B 呈如下形式：$C_1∨C_1∨\cdots ∨ C_m$ ，其中 $C_i$ (i=1,2,...,m) 形如 $L_1∧L_2∧\cdots∧L_n$ ，$L_j$ 为原子公式或原子公式的否定，称 $L_j$​ 为文字。任一命题公式φ有其对应的合取 (析取)范式。主合取（主析取）范式：命题公式B称为公式A的 主合取(或主析取)范式，如果：(1) B是A的合取(或析取)范式。(2) B中每一子句均有A中命题变元的全部出 现，且仅出现一次。命题演算形式系统三条公理模式：A1：A → (B → A)A2：(A → (B → C)) → ((A → B) → (A → C))A3：(¬ A → ¬ B) → (B → A)一条推理规则（分离规则）：$r_{mp}$ ：A, A → B => B定义 称下列公式序列为公式A在PC中的一个证明(proof)：$A_1, A_2, \cdots, A_m( = A)$ ，其中 $A_i$（i=1,2,...,m）或者是 PC 的公理，或者是 $A_j$（j<i） ，或者是由 $A_j$，$A_k$ （j, k < i） 使用分离规则所导出，而 $A_m$ 即公式 $A$​ 。定义 称 A 为 PC 中的定理，记为 $├_{PC}$ A ，如果 公式 A 在 PC 中有一个证明。定义 设 $Γ$ 为一公式集，称以下公式序列为公式A的、以 $Γ$ 为前提的演绎：$A_1, A_2, \cdots, A_m( = A)$ ，其中 $A_i$（i=1,2,...,m）或者是 PC 的公理，或者是 $Γ$ 的成员，或者是由 $A_j$，$A_k$ （j, k < i） 使用分离规则所导出，而 $A_m$ 即公式 $A$ 。定义 称A为前提Γ的演绎结果，记为 $Γ├_{PC}$ A，如果 公式A 有以$Γ$为前提 的演绎。若 $Γ$={B}，则用B$├_{PC}$ A表示 $Γ├_{PC}$ A。若B$├_{PC}$ A，A$├_{PC}$​ B则记为A├┤B。(演绎定理) 对PC中任意公式集 $Γ$ 和公式A，B， $Γ$ ∪{A}$├_{PC}$ B 当且仅当 $Γ$ $├_{PC}$ A→B谓词逻辑逻辑符号（固定含义和用法）：标点符号：(、)连接符和量词：=，¬，∧，∨，∀，∃变量：$x, x_1, x_2, \cdots, x', x'', \cdots, y, \cdots, z, \cdots$非逻辑符号（和 领域domain 相关的含义和用法）：谓词符号arity：参数的数量函数符号项和公式每个变量是一个项如果 $t_1, \cdots, t_n$ 是项，$f$ 是一个n元函数，则 $f(t_1, \cdots, t_n)$ 是一个项如果 $t_1, \cdots, t_n$ 是项，$P$ 是一个n元谓词符号，则 $P(t_1, \cdots, t_n)$ 是一个原子公式如果 $t_1$ 和 $t_2$ 是项，则 $(t_1 = t_2)$ 是一个原子公式如果 $\alpha$ 和 $\beta$ 是公式，$v$ 是变量，则 $¬ \alpha, (\alpha \land \beta), (\alpha \lor \beta), ∃ v.\alpha, ∀v.\alpha$ 是公式谓词逻辑的应用【例】“某些患者喜欢所有医生。没有患者喜欢庸医。所以没有医生是庸医。”【解】P(x)表示“x是患者”， D(x)表示“x是医生”， Q(x)表示“x是庸医”， L(x,y)表示“x喜欢y”。则有：F1: (∃x)(P(x) ∧ ∀y(D(y) →L(x, y))), F2: (∀ x)(P(x) → (∀y)(Q(y) → ¬L(x, y)))，G: (∀x)(D(x)→¬Q(x))等价关系$(\alpha \rightarrow \beta)$ 和 $(¬ \alpha ∨ \beta)$$(\alpha \leftrightarrow \beta)$ 和 $(\alpha \to \beta) \land (\beta \to \alpha)$变量范围自由变量和约束变量一个句子：没有变量的公式替换：$\alpha[v/t]$ 表示，在公式 $\alpha$ 中，$v$ 的所有自由出现都替换称 项$t$通常，$\alpha[v_1/t_1, \cdots, v_n/t_n]$解释一个解释是 一个二元组 $M = \langle D, I \rangle$$D$ 是 域，可以是任何非空集$I$ 是 谓词和函数符号集合的映射如果 $P$ 是一个 n 元谓词，$I(P)$ 是 $D$ 中的一个 n 元关系，即 $I(P) ⊆ D^n$​ 如果 $p$ 是一个 0 元谓词符号，即命题符号，那么 $I(p) ∈ \{\text{true}, \text{false}\}$。如果 $f$ 是一个n元的函数符号，那么 $I(f)$ 是 $D$ 上的一个 n 元函数，即 $I(f) : D^n → D$。如果 $c$ 是一个 0 元函数符号，即常量符号，那么 $I(c) ∈ D$。项的指派项 可以指派为 定义域中的元素一个变量赋值 $\mu$ 是从 变量集合 到 域$D$​ 中的映射$\| v\|_{M,\mu} = \mu(v)$​$\| f(t_1, \cdots, t_n)\|_{M, \mu} = I(f)(\|t_1\|_{M, \mu},\cdots, \|t_n\|_{M, \mu})$【例】D={Ann,Bob,Dan,Jack}, I(ann) = Ann I(spouse) = {(Ann,Bob),(Bob,Ann)}, I(father) = {(Ann,Jack),(Bob,Dan)}, 则有 ‖father(spouse(ann))‖= Dan满足：原子公式$M, \mu \models \alpha$ ，称为 “$M, \mu$ 满足 $\alpha$ ”$M, \mu \models P(t_1, ..., t_n)$ 当且仅当 $\langle \| t_1\|_{M, \mu}, ..., \|t_n\|_{M, \mu} \rangle \in I(P)$$M, \mu \models (t_1=t_2)$ 当且仅当 $ \| t_1\|_{M, \mu}=\|t_2\|_{M, \mu}$满足：命题联结词$M, \mu \models \lnot \alpha$ 当且仅当 $M, \mu \not\models \alpha$$M, \mu \models (\alpha \land \beta)$ 当且仅当 $M, \mu \models \alpha$ 同时 $M, \mu \models \beta$$M, \mu \models (\alpha \lor \beta)$ 当且仅当 $M, \mu \models \alpha$ 或者 $M, \mu \models \beta$满足：量词$\mu[v\mapsto d]$ 记为一个变量赋值 $\mu$ ，把 v 映射到 d$M, \mu \models ∃ v.\alpha$ 当且仅当 对于一些 $d \in D$，$M, \mu[v \mapsto d] \models \alpha$$M, \mu \models \forall v.\alpha$ 当且仅当 对于所有 $d \in D$，$M, \mu[v \mapsto d] \models \alpha$设 $\alpha$ 是一个句子。那么 $M, \mu \models \alpha$ 是否成立与 $\mu$ 无关。 此时，我们简单地写作 $M \models \alpha$。可满足性假设 $S$ 是一个句子的集合如果对于所有的 $\alpha \in S, M\models \alpha$，则有 $M \models S$ ，称 M 满足 S。如果 $M \models S$ ，我们称 $M$ 是 $S$ 的一个模型如果存在 $M$ 使得 $M \models S$ ，则 $S$​ 是可满足的逻辑蕴含$S\models \alpha$ 当前仅当 对所有的 $M$ ，如果 $M\models S$ 则 $M\models a$​$S\models \alpha$​ 称为：S 蕴含 α 或 α 是 S 的逻辑推论。一个特殊的例子：$\varnothing \models \alpha$，简写 $\models \alpha$，称 $\alpha$ 是有效的注意到 $\{\alpha_1, ..., \alpha_n\} \models \alpha$ 当且仅当 $\alpha_1 \land ... \land \alpha_n \to \alpha$ 是有效的 当且仅当 $\alpha_1 \land ... \land \alpha_n \to \alpha \land \lnot \alpha$ 是不可满足的。$\alpha \iff \beta$ ($\alpha$ 和 $\beta$ 逻辑等价) 如果对于所有的 $M$，$M\models \alpha$ 当且仅当 $M\models \beta$自然演绎推理自然演绎推理：从一组已知为真的事实出发，运用经典逻辑的推理规则推出结论的过程。推理规则：假言推理：$P, P\to Q \implies Q$取拒式推理：$P\to Q, \lnot Q \implies \lnot P$化简规则：$P\land Q \implies P, P\land Q \implies Q$附加规则：$P \implies P\lor Q, Q\implies P\lor Q$析取三段论：$\lnot P, P\lor Q \implies Q$假言三段论：$P\to Q, Q \to R \implies P\to R$二难推理：$P \lor Q, P\to R, Q\to R \implies R$全程特化：$(\forall x) P(x) \implies P(y)$存在特化：$(∃ x)P(x) \implies P(c)$ ，c 为个体域中某一个可以使 P(c) 为真的个体谓词逻辑的应用【例】 每个去临潼游览的人或者参观秦始皇兵马俑，或者参观华清池，或者洗温泉澡。凡去临潼游览的人，如果爬骊山就不能参观秦始皇兵马俑，有的游览者既不参观华清池，也不洗温泉澡。因而有的游览者不爬骊山。【解】定义G（x）表示“x去临潼游览”；A（x）表示“x参观秦始皇兵马俑”；B（x）表示“x参观华清池”；C（x）表示“x洗温泉澡”；D（x）表示“x爬骊山”。前提：(∀x)(G(x) → A(x) ∨ B(x) ∨ C(x)) (1)(∀x)(G(x) → (D(x) → ¬A(x))) (2)(∃x)(G(x) ∧ ¬B(x) ∧ ¬C(x)) (3)结论：(∃x)(G(x) ∧ ¬D(x))推导：(4) G(a) ∧ ¬B(a) ∧ ¬C(a) 由(3)(5) G(a) 由(4)(6) ¬B(a) ∧ ¬C(a) 由(4)(7) G(a) → A(a) ∨ B(a) ∨ C(a) 由(1)(8) A(a) ∨ B(a) ∨ C(a) 由(5), (7)(9) A(a) ∨ ¬(¬B(a) ∧ ¬C(a)) 由(8)(10) A(a) 由(6), (9)(11) G(a) → (D(a) → ¬A(a)) 由(2)(12) D(a) → ¬A(a) 由(5), (11)(13) ¬D(a) 由(10), (12)(14) G(a) ∧ ¬D(a) 由(5), (13)(15) (∃x)(G(x) ∧ ¬D(x)) 由(14)基于归结的推理过程我们需要一个机制去判断 $KB \models \alpha$ 是否成立，这个机制就是 推理过程。常见的推理规则：假言推理：$\phi \to \psi, \phi \models \psi$假言三段论：$\phi \to \psi, \psi \to \eta \models \phi \to \eta$析取三段论：$\phi \lor \psi, \lnot \phi \models \psi$全称实例化：$\forall x P(x) \models P(c)$全程一般化：$P(x) \models ∃ x P(x)$基于归结的推理规则归结是一种推理规则基于归结的推理过程：反演子句形式一个 文字 是一个原子公式或者它的否定，例如，p, ¬p一个 子句 是文字的析取，记为 文字的集合：例如，p ∨ ¬r ∨ s，记为 (p, ¬ r, s)一个特殊情况：空子句()，代表 False一个公式 是 子句的合取，写为 子句集合的形式推理的归结规则两个子句集 $\{p\} \cup c_1$ 和 $\{¬p\}\cup c_2$ 推导出子句 $c_1\cup c_2$$c_1\cup c_2$ 被称为相对于原子 p 的输入子句的归结式。定理 如果 $S├ c$ ，则 $S\models c$ 。反之不一定成立。定理 $S\vdash()$ 当且仅当 $S\models ()$ 当且仅当 $S$ 是不可满足的的。$KB\models \alpha$ 当且仅当 $KB ∧ ¬\alpha$ 是不可满足的。因此如果要判断 $KB\models \alpha$ 是否成立，需要：将 $KB$ 和 $\lnot \alpha$ 转化为 子句形式 之后得到 $S$检查 $S \vdash ()$ 是否成立例题1 谓词逻辑的归结原理和过程在谓词逻辑中应用归结法时，首先需要：将所有谓词公式（包括知识库 KB 和查询 $\alpha$ ）化为子句集通过合一，对含有变量的子句进行归结① ∀x(∀y P(x, y) → ¬∀y(Q(x, y) → R(x, y)))谓词公式化为子句集的步骤：消去蕴含和等价符号（→ 和↔ 联结词）P → Q ⇔ ¬P ∨ Q，P ↔ Q ⇔ (P ∧ Q) ∨ (¬P ∧ ¬Q)① ⇔ ∀x(¬∀y P(x,y) ∨ ¬∀y(¬Q(x,y) ∨ R(x,y))) ②内移否定符号 ¬，将其移到紧靠谓词的位置上。双重否定率：¬(¬P) ⇔ P德摩根律：¬(P ∧ Q) ⇔ ¬P ∨ ¬Q，¬(P ∨ Q) ⇔ ¬P ∧ ¬Q量词转换率：¬∃x P ⇔ ∀x ¬P，¬∀x P ⇔ ∃x ¬P② ⇔ ∀x(∃y ¬P(x,y) ∨ ∃y (Q(x,y) ∧ ¬R(x,y))) ③量词标准化。对变量做必要的换名，每个量词只约束一个唯一的变量名。∃x P(x) ≡ ∃y P(y)，∀x P(x) ≡ ∀y P(y)③ ⇔ ∀x(∃y ¬P(x,y) ∨ ∃z (Q(x,z) ∧ ¬R(x,z))) ④消去存在量词（Skolemize）。对于待消去的存在量词，若不在任何全称量词辖域之内，则用 Skolem 常量代替公式中存在量词约束的变量；若受全称量词约束，则要用 Skolem 函数代替存在量词约束的变量，然后消去存在量词。Skolemize ：对于一般情况：$$ \forall x_1 \forall x_2 \cdots\forall x_n \exist y P(x_1, x_2, \cdots,x_n, y) $$存在量词 $y$ 的 Skolem 函数为 $y = f(x_1, x_2, \cdots, x_n)$ Skolem 化，用 Skolem 函数代替存在量词约束的变量的过程。④ y = f(x), z = g(x) ⇔ ∀x(¬P(x,f(x)) ∨ (Q(x,g(x)) ∧ ¬R(x,g(x)))) ⑤化为前束式 = (前缀){母式}。其中，前缀为全称量词串，母式为不含量词的谓词公式。把母式化成合取范式。反复使用结合律和分配律，将母式表达成 合取范式的 Skolem 标准形。Skolem 标准形：$\forall x_1\forall x_2\cdots\forall x_n M$ M：子句的合取式，称为 Skolem 标准形的母式。$$ P∧ (Q∨ R) \iff (P∧Q)∨ (P∧R)\\ P∨ (Q∧R) \iff (P∨ Q)∧(P∨ R)\\ $$⑤ ⇔ ∀x((¬P(x,f(x)) ∨ Q(x,g(x))) ∧( ¬P(x,f(x)) ∨ ¬R(x,g(x)))) ⑥略去全称量词。由于母式的变量均受全称量词的约束，因此可以省略掉全称量词。⑥ ⇔ (¬P(x,f(x)) ∨ Q(x,g(x))) ∧( ¬P(x,f(x)) ∨ ¬R(x,g(x)))把母式用子句集表示。把母式中的每一个合取元称为一个子句，省去合取联结词，这样就把母式写成集合的形式表示，每一个元素就是一个子句。⑦ ⇔ {(¬P(x, f(x)), Q(x, g(x))), (¬P(x, f(x)), ¬R(x, g(x)))}子句变量标准化。对某些变量重新命名，使任意两个子句不会有相同的变量出现。这是因为在使用子句集进行证明推理的过程中，有时需要例化某一个全称量词约束的变量，该步骤可以使公式尽量保持其一般化形式，增加了应用过程的灵活性。【例】将下列谓词公式化为不含存在量词的前束型：∃x∀y(∀z (P(z) ∧ ¬Q(x, z)) → R(x, y, f(a)))∃x∀y(∀z (P(z) ∧ ¬Q(x, z)) → R(x, y, f(a)))⇔ ∀y(∀z (P(z) ∧ ¬Q(b, z)) → R(b, y, f(a)))⇔ ∀y(¬∀z (P(z) ∧ ¬Q(b, z)) ∨ R(b, y, f(a)))⇔ ∀y(∃z (¬P(z) ∨ Q(b, z)) ∨ R(b, y, f(a)))⇔ ∀y(¬P(g(y)) ∨ Q(b, g(y)) ∨ R(b, y, f(a)))【例】将下列谓词公式化为子句集∀x{[¬P(x) ∨ ¬Q(x)] → ∃y[S(x, y) ∧ Q(x)]} ∧ ∀x[P(x) ∨ B(x)]【解】(1)消去蕴含和等价符号：∀x{¬[¬P(x) ∨ ¬Q(x)] ∨ ∃y[S(x, y) ∧ Q(x)]} ∧ ∀x[P(x) ∨ B(x)](2)内移否定符号：∀x{[P(x) ∧ Q(x)] ∨ ∃y[S(x, y) ∧ Q(x)]} ∧ ∀x[P(x) ∨ B(x)](3)量词标准化：∀x{[P(x) ∧ Q(x)] ∨ ∃y[S(x, y) ∧ Q(x)]} ∧ ∀z[P(z) ∨ B(z)](4)消去存在量词：∀x{[P(x) ∧ Q(x)] ∨ [S(x, f(x)) ∧ Q(x)]} ∧ ∀z[P(z) ∨ B(z)](5)化为前束式：∀x∀z{[[P(x) ∧ Q(x)] ∨ [S(x, f(x)) ∧ Q(x)]]∧ [P(z) ∨ B(z)]} (6)把母式化成合取范式：∀x∀z{ [P(x) ∨ S(x, f(x))] ∧ Q(x) ∧ [P(z) ∨ B(z)]} (7)略去全称量词：[P(x) ∨ S(x, f(x))] ∧ Q(x) ∧ [P(z) ∨ B(z)](8)把母式用子句集表示：{(P(x), S(x, f(x))), Q(x), (P(z), B(z))}(9)子句变量标准化：{Q(x), (P(y), S(y, f(y))), (P(z), B(z))}归结过程若 S 中两个子句间有相同互补文字的谓词，但它们的项不同，则必须找出对应的不一致项；进行变量置换，使得它们对应项一致求归结式能否推导出空子句合一（Unify）：在谓词逻辑的归结过程中，寻找项之间合适的变量置换使表达式一致，这个过程称为合一。一个表达式的项可以是常量符号、变量符号 或 函数式。表达式的例(instance) 是指在表达式中用置换项置换变量后得到的一个特定的表达式。用 $\sigma = \{v_1/t_1, v_2/t_2, ..., v_n/t_n\}$ 来表示任一置换。$v_i/t_i$ 表示表达式中的变量 $v_i$ 以项 $t_i$ 来替换，且不允许 $v_i$ 用与 $v_i$ 有关的项 $t_i$ （但是 $t_i$ 中可以包含其他变量）作替换。可记为 $\sigma = \{v_1=t_1, v_2=t_2, ..., v_n=t_n\}$用 $\sigma$ 对表达式 $E$ 作置换后记为 $E\sigma$例如：P(x, g(y, z)){x = y, y = f(a)} ⇒ P(y, g(f(a), z))注意：置换是同时进行的，而不是先后进行的。可以对表达式多次置换，如果用 $\theta$ 和 $\sigma$ 依次对 $E$ 进行置换，记为 ($E\theta$)$\sigma$ 。其结果等价于先将这两个置换合成（组合）为一个置换，即 $\theta \sigma$ ，在用合成置换对 $E$ 进行置换，即 $E(\theta\sigma)$$\theta = \{x_1=s_1, x_2=s_2, ..., x_m=s_m\}$，$\sigma = \{y_1=t_1, y_2=t_2, ..., y_k=t_k\}$合成置换 $\theta\sigma$ 的组成：(1) $\theta$ 的置换对，只是 $\theta$ 被 $\sigma$ 作了置换。(2) $\sigma$ 中与 $\theta$ 变量不同的那些变换对。合成置换 $\theta\sigma$ 的步骤：得到 $S = \{x_1=s_1\sigma, x_2=s_2\sigma, ..., x_m=s_m\sigma,y_1=t_1, y_2=t_2, ..., y_k=t_k\}$删除任何形如 $y_i = s_i$的等式，其中 $y_i$ 等于$\theta$中的某个 $x_j$。删除任何同一恒等式，即形如 $v = v$ 的等式。【例】$\theta = \{x = f(y), y = z\}, \sigma = \{x = a, y = b, z = y\}$令 $S = {x = f(b), y = y, x = a, y = b, z = y}删除 x = a, y = b删除 y = y$\theta\sigma = S = \{x = f(b), z = y\}$ 这样的合成法可使$(E\theta)\sigma = E(\theta\sigma)$ ，即可结合。但置换是不可交换的，即 $\theta\sigma \not= \sigma\theta$ 空置换 $\epsilon = \{\}$ 也是一个置换，且 $\theta\epsilon = \theta$ 合一项（Unifiers）两个公式 f 和 g 的合一项（unifier）是使 f 和 g 语法上相同的一个替换 σ。请注意，并不是所有公式都能被合一，替换只影响变量。例如，P(f(x), a) 和 P(y, f(w)) 不能被合一，因为没有办法通过替换使 a = f(w)。最一般合一项 MGU两个公式 f 和 g 的替换 σ 是最一般合一项（MGU, Most General Unifier），如果：σ 是一个合一项。对于 f 和 g 的任何其他合一项 θ，必须存在第三个替换 λ，使得 θ = σλ。这表明每个其他合一项都比 σ “更具体”。一对公式 f 和 g 的最一般合一项（MGU）在重命名的意义下是唯一的。【例】P(f(x), z) 和 P(y,a) σ ={y=f(a),x = a,z = a} 是一个合一项, 但不是一个 MGU θ ={y=f(x),z = a} 是一个 MGU σ =θλ, 其中 λ = {x = a}计算 MGU最一般合一项（MGU）是使带有变量的原子公式匹配的“最不具体”的方法。我们可以计算出最一般合一项（MGUs）。直观上，我们将两个公式对齐，并找到它们第一个不一致的子表达式。它们 首次不一致的子表达式对 称为差异集（disagreement set）。该算法通过逐项修正差异集，直到两个公式在语法上完全相同为止。步骤：给定两个原子公式 f 和 g设定 σ = {}; S = {f, g}如果 S 包含一对相同的公式，则停止并返回 σ 作为 f 和 g 的最一般合一项（MGU）。否则，找到 S 的差异集 D = {e1, e2}如果 e1 = V 是一个变量，且 e2 = t 是不包含 V 的项（或反之），则令 σ = σ{V = t}; S = S{V = t}; 转到步骤 2否则，停止，f 和 g 不能被合一。注意：为了更新 σ，我们必须将 σ 与 {V = t} 进行合成。一个常见的错误是只是将 V = t 添加到 σ 中。【例】P(f(a), g(x)) 和 P(y, y)：不可合一P(a, x, h(g(z))) 和 P(z, h(y), h(y))最一般合一项（MGU）：{z = a, x = h(g(a)), y = g(a)}P(x, x) 和 P(y, f(y))：不可合一归结示例(P(x), Q(g(x)))(R(a), Q(z), ¬P(a))R[1a, 2c]{x = a} (Q(g(a)), R(a), Q(z))“R” 表示归结步骤。“1a” 表示第一个子句中的第一个（a 个）文字：P(x)。“2c” 表示第二个子句中的第三个（c 个）文字：¬P(a)。1a 和 2c 是“冲突”文字。 {x = a} 是应用的最一般合一项（MGU）。【例】证明 ∃y ∀x P(x, y) |= ∀x ∃y P(x, y)∃y ∀x P(x, y) ⇒ 1. P(x, a)¬∀x∃y P(x, y) ⇔ ∃x∀y ¬P(x, y) ⇒ 2. ¬ P(b, y)R[1, 2] {x = b, y = a}练习：证明∀x P(x) ∨ ∀x Q(x) |= ∀x (P(x) ∨ Q(x))∀x P(x) ∨ ∀x Q(x) ⇒ 1. (P(x), Q(y))¬∀x (P(x) ∨ Q(x)) ⇒ {¬P(a), ¬Q(a)} ⇒ 2. ¬ P(a) 3. ¬Q(a)R[1a, 2]{x = a} Q(y)R[3, 4]{y = a} ()∃x(P(x) ∧ Q(x)) |= ∃x P(x) ∧ ∃x Q(x)∃x(P(x) ∧ Q(x)) ⇒ 1. P(a) 2.Q(a))¬(∃x P(x) ∧ ∃x Q(x)) ⇒ 3. (¬P(x), ¬Q(y))R[1, 3a] {x = a} ¬Q(y)R[2, 4] {y = a} ()【例】KB：∀x(GradStudent(x) → Student(x))，∀x(Student(x)→HardWorker(x))，GradStudent(sue)证明：KB |= HardWorker(sue)∀x(GradStudent(x) → Student(x)) ⇔ ∀x(¬GradStudent(x) ∨ Student(x)) ⇒ {(¬GradStudent(x), Student(x))}；∀x(Student(x)→HardWorker(x)) ⇔ ∀x(¬Student(x) ∨ HardWorker(x)) ⇒ {(¬Student(y), HardWorker(y))}；总的子句集：{(¬GradStudent(x), Student(x)), (¬Student(y), HardWorker(y)), GradStudent(sue), ¬HardWorker(sue)}(¬GradStudent(x), Student(x))(¬Student(y), HardWorker(y))GradStudent(sue)¬HardWorker(sue)R[1a, 3]{x = sue} Student(sue)R[2a, 5]{y = sue} HardWorker(sue)R[4, 6] ()【例】已知：（1） 会朗读的人是识字的， （2） 海豚都不识字， （3） 有些海豚是很机灵的。证明：有些很机灵的东西不会朗读。【解】把问题用谓词逻辑描述如下， 已知：(1) ∀x(R(x) → L(x)) (2) ∀x (D(x) → ¬L(x)) (3) ∃x(D(x) ∧ I(x))。求证：∃x(I(x) ∧ ¬R(x))前提化简，待证结论取反化为子句形式：(¬R(x), L(x))(¬D(y), ¬L(y))D(a)I(a)(¬I(z), R(z))证明：R[2a, 3]{y = a} ¬L(a)R[1b, 6]{x = a} ¬R(a)R[5b, 7]{z = a} ¬I(a)R[4, 8] ()【例】答案提取应用归结原理求解问题(1) 已知前提 $F$ 用谓词公式表示，并化为子句 $S$ (2) 把待求解的问题 $P$ 用谓词公式表示，并否定 $P$ ，再与 answer 构成析取式(¬P ∨ answer)(3) 把 (¬P ∨ answer) 化为子句集，并入到子句集 S 中，得到子句集 S'(4) 把 S' 应用归结原理进行归结(5) 若得到归结式 answer，则答案就在 answer 中KB：Student(John)，Student(Jane)，Happy(John)Q：∃x(Student(x) ∧ Happy(x))¬P ⇔ ¬∃x(student(x) ∧ Happy(x)) ⇔ ∀x(¬student(x) ∨ ¬Happy(x)) ⇒ (¬student(x), ¬Happy(x))¬P ∨ A ⇒ (¬student(x), ¬Happy(x), A(x)) KB：Student(john)，Student(jane)，Happy(john) ∨ Happy(jane)Query：∃x[Student(x) ∧ Happy(x)]第3章：搜索技术盲目搜索（深度搜索、宽度搜索、迭代加深搜索）；启发式搜索（最好优先搜索、A*搜索）；博弈树搜索（极大极小过程、alpha-beta剪枝）。盲目搜索深度搜索宽度搜索迭代加深搜索通过扩展深度受限搜索，解决了深度优先和广度优先的问题从深度限制L=0开始，我们迭代增加深度限制，对每个深度限制执行深度受限搜索如果找到解，或者深度受限搜索失败且没有因为深度限制而剪掉任何节点，则停止如果没有节点被剪掉，则搜索考查了状态空间中的所有路径但没有找到解，因此无解。标准宽度优先搜索深度优先搜索迭代加深搜索时间$b^d$$b^m$$b^d$空间$b^d$bmbd最优性是否是完备性是否是注：b 是分支系数，d 是解答深度，m 是搜索树的最大深度宽度优先搜索需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。迭代加深搜索对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样是适中的。启发式搜索（启发式搜索）如果在选择节点时能 充分利用与问题有关的特征信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以便求得最优解。用来评估节点重要性的函数称为 评估函数。评估函数为 $f(x) = g(x) + h(x)$$g(x)$，表示 从初始节点 S0 到节点 x 的 实际代价$h(x)$ ，表示 从 $x$ 到目标节点 $S_g$ 的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，$h(x)$ 称为 启发式函数启发式方法把问题状态的描述转换成了对问题解决程度的描述，这一程度用评估函数的值来表示。通用图搜索算法图搜索算法只记录状态空间中那些被搜索过的状态，它们组成一个搜索图 GG 由两种节点组成：Open 节点，如果该节点已经生成，而且启发式函数值 $h(x)$ 已经算出，但是它还没有拓展。这些节点也称为未考察节点。Closed 节点，如果该节点已经扩展并生成了其子节点。Closed 节点是已经考察过的节点。可以给出两个数据结构 OPEN 和 CLOSED 表，分别存放 Open 节点 和 Closed 节点。节点 x 的费用函数 f(x)，f(x) = g(x) + h(x)生成费用 g(x) 可以比较容易得到，入，如果节点 x 是从初始节点经过 m 步得到，则 g(x) 节点是从初始节点经过 m 步得到，则 g(x) 应给和 m 成正比（或者就是 m）h(x) 只是个预测值。上述图搜索算法生成一个明确的图G（称为搜索图）和一个G的子集T（称为搜索树），图G中的每一个节点也在树T上。搜索树是由返回指针来确定的。G中的每一个节点（除了初始节点S0）都有一个指向G中一个父辈节点的指针。该父辈节点就是树中那个节点的唯一父辈节点。最好优先搜索搜索是从 最有希望的节点 开始，并且生成其所有的子节点。计算每个节点的性能（合适性），选择最有希望的节点进行扩展，而不是仅仅从当前节点所生成的子节点中进行选择。如果在早期选择了一个错误的节点，最好优先搜索就提供了一个修改的机会。最好优先搜索算法并没有显式地给出如何定义启发式函数，它不能保证当从起始节点到目标节点的最短路径存在时，一定能够找到它。特点是：每次选择全局最优的节点进行拓展如果最好优先搜索算法中的 f(x) 被实例化为 f(x) = g(x) + h(x)，则称为 A 算法。由于对启发函数h 没有任何限制，A 算法不能保证找到最优解。A*搜索A* 算法是 A 算法的改进，对启发式函数做出了限制。评估函数 $f^*(n) = g^*(n) + h^*(n)$$g^*(n)$ 为起始节点到节点 n 的最短路径的代价$h^*(n)$ 是从 n 到目标节点的最短路径把估价函数$f (n)$ 和 $f^*(n)$相比较，$g (n)$ 是对 $g^*(n)$的估价。$h (n)$是对$h^* (n)$的估价。$g(n)$ 是对 $g^*(n)$ 的估计，且 $g(n) >0 $$h(n)$ 是 $h^*(n)$ 的下界，即对任意节点 n 均有 $h(n)\leqslant h^*(n)$ 。这样得到的算法为 A* 算法IDA 算法：迭代加深 A 算法。对启发函数用做深度的限制，而不是选择拓展节点的排序。博弈树搜索极大极小过程极小极大策略构建完整的博弈树（所有叶子节点都是终结节点）根节点是起始状态，边表示可能的移动等用效用值标记终结节点将 值 向树上回溯U(t) 定义在所有终结节点上（作为输入的一部分）如果 n 是一个极小节点，则 U(n) = min {U(c) : c 是 n 的子节点}如果 n 是一个极大节点，则 U(n) = max {U(c) : c 是 n 的子节点}极小极大算法的深度优先实现def DFMiniMax(n, Player): #返回在给定玩家为 MIN 或 MAX 时状态 n 的效用值 if n is TERMINAL: return V(n) #返回终结状态的效用值 #(V 是游戏的一部分) #应用玩家的移动获取后继状态 ChildList = n.Successors(Player) if Player == MIN: return min(DFMiniMax(c, MAX) for c in ChildList) else: # Player 是 MAX return max(DFMiniMax(c, MIN) for c in ChildList)alpha-beta剪枝实际上，我们不需要考查整个树来做出正确的极小极大决策假设树是以深度优先生成的在仅为 n 的一些子节点生成值之后，我们可以证明在极大极小策略中我们永远不会达到 n所以我们不需要再生成 n 的其他子结点有两种类型的剪枝极大结点的剪枝（α-cuts）极小节点的剪枝（β-cuts）Alpha-beta 值在一个 Max结点 n 处，令 α 为 n 的已检查的子节点的最大值（随已检查的子节点变化而变化）在一个 Min 结点 n 处，令 β 为 n 的已检查的子节点的最小值（随已检查的子节点变化而变化）α 剪枝在 Max 结点 n 处，如果 α 变得 ≥ 父亲 Min 结点的 β 值，则我们可以停止扩展 n这是因为 Min 不会选择 n 而是选择 n 的某个低值兄弟节点一般来说，在 Max 节点 n 处，如果 α 变得 ≥ 某个祖先 Min 节点的 beta 值，则我们可以停止扩展 nβ 剪枝在 Min 节点 n 处，如果 β 变得 ≤ 父亲 Max 节点的 α 值，则我们可以停止扩展 n这是因为 Max 不会选择 n 而是选择 n 的某个高值兄弟节点一般来说，在 Min 节点 n 处，如果 β 变得 ≤ 某个祖先 Max 节点的 α实现Alpha-Beta剪枝def AlphaBeta(n, Player, alpha, beta): # 返回状态 n 的效用值 if n is TERMINAL: return V(n) # 返回终结状态的效用值 ChildList = n.Successors(Player) if Player == MAX: for c in ChildList: alpha = max(alpha, AlphaBeta(c, MIN, alpha, beta)) if beta <= alpha: break return alpha else: # Player == MIN for c in ChildList: beta = min(beta, AlphaBeta(c, MAX, alpha, beta)) if beta <= alpha: break return beta跟踪 α-β 剪枝过程对 Max 节点标记 α值 的变化，对 Min 节点标记 beta 值的变化在 Max 节点上，每当当前值 ≥ 某个祖先 Min 节点的值时，做 α 剪枝在 Min 节点上，每当当前值 ≤ 某个祖先 Max 节点的值时，做 β 剪枝例题1例题2第4章：高级搜索爬山法（基本思想）；遗传算法（基本操作）。爬山法基本思想：一直向值增加的方向持续移动，将会在到达一个“峰顶”时终止，并且在相邻状态中没有比它更高的值。这个算法不维护搜索树，因此当前节点的数据结构只需要记录当前状态和它的目标函数值。爬山法不会预测与当前状态不直接相邻的那些状态的值。遗传算法遗传算法，是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。个体是染色体（chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。需要从表现型到基因型的映射（编码）简化基因编码，如二进制编码。初代种群产生之后，按照 适者生存 和 优胜劣汰 的原理，逐代(generation）演化产生出越来越好的近似解。在每一代，根据 问题域 中 个体的适应度（fitness）大小挑选 个体，并借助于 自然遗传学的遗传算子 进行 组合交叉 和 变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后代种群比前代更加适应于环境，末代种群 中的 最优个体 经过 解码，可以作为问题近似最优解遗传算法的过程开始时，种群随机地初始化，并计算每个个体的适应度函数，初始代产生了如果不满足优化准则，开始产生新一代的计算为了产生下一代，按照适应度选择个体，父代进行基因重组（交叉）而产生子代所有子代按一定概率变异，然后子代的适应度又重新被计算，子代被插入到种群将父代取而代之，构成新的一代循环，直到满足优化准则遗传算法：自组织，自适应，自学习性遗传算法的本质并行性遗传算法不需要求导或其他辅助只是遗传算法强调概率转换规则遗传算法可以更加直接地应用遗传算法对给定问题，可以产生许多潜在解。遗传算法的基本操作选择选择，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。首先计算适应度：(1) 按比例的适应度计算(2) 基于排序的适应度计算适应度计算之后是实际的选择，按照适应度进行父代个体的选择可选的算法：① 轮盘赌选择 ② 随机变量抽样 ③ 局部选择 ④ 截断选择 ⑤ 锦标赛选择交叉或基因重组基因重组，是结合来自父代交配种群中的信息产生新的个体。根据个体编码表示方法的不同，可以有以下的算法：① 实值重组：离散重组，中间重组，线性重组，扩展线性重组② 二进制交叉：单点交叉，多点交叉，均匀交叉，洗牌交叉，缩小代理交叉变异 mutation交叉之后，子代经历的变异，实际上是 子代基因 按小概率扰动产生的变化。根据个体编码表示方法的不同，可以采用以下算法：① 实值变异 ② 二进制变异考察：二进制编码的轮盘赌选择、单点交叉和变异操作。个体适应度，按比例转化为 选中概率，将轮盘分为 10 个扇区：因为要进行 10 次选择，所以产生 10 个 [0, 1] 之间的随机数相当于转动 10 次转盘，获得 10次转盘停止时 指针位置，指针停在某一扇区。扇区代表的个体即被选中。假设产生随机数序列为0.070221, 0.545929, 0.784567, 0.44693, 0.507893, 0.291198, 0.71634, 0.272901, 0.371435, 0.854641，将该随机序列与计算获得的累积概率比较，则依次序号为1,8,9,6,7,5,8,4,6,10个体被选中。适应度高的个体被选中的概率大，而且可能被选中，而适应度低的个体很可能被淘汰在第一次生成竞争考验中，序号为 2 的个体（0101111001）和3的个体（0000000101）被淘汰，代之以适应度较高的个体8和6, 这个过程被称为再生。交叉：以单点交叉为例，任意挑选经过选择操作后种群中 两个个体作为交叉对象，即两个父个体经过染色体交换重组产生两个子个体。随机产生一个交叉点位置，父个体1 和父个体2在交叉点位置的右边部分基因码互换，形成子个体1和子个体2：为避免过早收敛，有必要在进化过程中加入具有新遗传基因的个体。效仿自然界生物变异：模仿生物变异的遗传操作，对于二进制的基因码组成的个体种群，实现基因码的小概率反转，即达到变异的目的。 变异：以小概率决定第 4 个遗传因子翻转。遗传算法的进化过程：初始种群经过选择操作适应度较高的 8 号和 6号个体分别复制 2 个。适应度较低的 2 号 和 3 号遭到淘汰按一定概率选择了 3 对父个体分别完成交叉操作，在随机确定"|" 的位置实行单点交叉生成 3 对子个体。按小概率选中某个个体的基因码位置，产生变异生成了第一代的群体循环遗传算法流程图第一步：随机产生初代群体，个体数目一定，每个个体表示为染色体的基因编码第二步：计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算，否则转向第三步。第三步：依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰。第四步：按照一定的交叉概率和交叉方法，生成新的个体第五步：按照一定的变异概率和变异方法，生成新的个体第六步：由交叉和变异产生新一代的种群，返回第二步第5章：不确定知识表示和推理贝叶斯网络定义及表示、联合概率表示、构建方法、朴素贝叶斯方法、独立性判断D分离；贝叶斯网络边缘概率及条件概率计算。概率概率是定义在一个事件集 U（通常被称为事件的全域）上的函数。给定每个事件的 $e\in U$，赋值 $Pr(e) \in [0, 1]$ 。通过对事件集 $F$ 的成员的概率求和为该集合赋值：$Pr(F) = \sum_{e\in F} Pr(e)$因此，$Pr(U) = 1, Pr(\varnothing) = 0$$Pr(A \cup B) = Pr(A) + Pr(B) - Pr(A \cap B)$特征向量上的概率我们将处理有特征向量组成的全域。我们有：变量集合 $V_1, V_2, ..., V_n$每个变量的有限域：$\mathrm{Dom}[V_1], \mathrm{Dom}[V_2], ..., \mathrm{Dom}[V_n]$事件的全域 U 是变量值的所有向量的集合。事件的空间大小为 $\prod_i |\text{Dom}[V_i]|$ ，即论语大小的乘积例如，如果 $|\text{Dom}[V_i]| = 2$，则有 $2^n$ 个不同的原子事件。通过指定某些变量的值可以方便地说明 U 的一些子集。例如：{$V_1 = a$} 表示 $V_1 = a$ 的所有事件的概率{$V_1 = a, V_3 = d$} 表示 $V_1 = a$ 并且 $V_3 = d$​ 的所有事件的集合如果我们有每个原子事件（变量的完整实例化）的概率，就可以计算出任何集合的概率。例如：$$ Pr(\{V_1 = a\}) = \sum_{x_2\in D[V_2]}\cdots \sum_{x_n\in D[V_2]} Pr(V_1 = a, V_2 = x_2, ..., V_n = x_n) $$条件概率假设 A 是一个事件的集合，有 $Pr(A) > 0$那么可以定义关于事件 A 的条件概率：$Pr(B|A) = \cfrac{Pr(B\cap B)}{Pr(A)}$以 A 为条件，对应于将注意力限制在 B 中的事情上。性质和集合集合 $A\cup B$集合 $A\cap B$集合 $U-A$​求和规则如果 $B_1, B_2, ..., B_k$ 形成 U 的划分。则 $\mathrm{Pr}(A) = \mathrm{Pr}(A \cap B_1) + ... + \mathrm{Pr}(A\cap B_k )$ 独立性如果 $Pr( B|A) = Pr(B)$​ ，称 B 和 A 是独立的如果 $Pr(A \cap B) = Pr(A) \cdot Pr(B)$ ，则 A 和 B 是独立的条件独立性给定 A，如果 $Pr(B| A\cap C) = Pr(B | A)$ ，则 B 和 C 条件独立给定 A，则 B 和 C 是条件独立的，则 $Pr(B\cap C | A) = Pr(B|A)\cdot Pr(C|A)$贝叶斯规则$$ \mathrm{Pr}(Y|X) = \cfrac{\mathrm{Pr}(X|Y)\mathrm{Pr}(Y)}{\mathrm{Pr}(X)} $$链式规则$$ \mathrm{Pr}(A_1 \cap A_2 \cap ... \cap A_n) = \mathrm{Pr}(A_1 | A_2 \cap ... \cap A_n) \cdot \mathrm{Pr}(A_2|A_3 \cap A_4 \cap ... \cap A_n)\cdot ... \cdot \mathrm{Pr}(A_{n-1}|A_n) \cdot \mathrm{Pr}(A_n) $$变量独立给定变量 Z，两个变量 X 和 Y 是条件独立的，如果对所有的 $x\in \mathrm{Dom}(X), y\in \mathrm{Dom}(Y), z \in \mathrm{Dom}(Z)$，给定 $Z = z$, 有 $X = x$ 和 $Y = y$ 是条件独立的，即$$ \mathrm{Pr}(X = x ∧ Y = y | Z = z) = \mathrm{Pr}(X = x | Z = z) \cdot \mathrm{Pr}（Y= y| Z = z) $$对变量 X，$\mathrm{Pr}(X)$ 是指 X 上的（边缘）分布。它对所有的 $d\in \text{Dom}[X]$ 指定 $\mathrm{Pr}(X = d)$$\sum_{d\in \text{Dom}[X]} \mathrm{Pr}(X = d) = 1$且 $\mathrm{Pr}(X = d_1 ∧X = d_2) = 0, d_1, d_2\in \text{Dom}[X], d_1 \not= d_2$$\mathrm{Pr}(X|Y)$ 指 $X$ 上的条件分布族，对每个 $y\in \text{Dom}[Y]$ 都有一个条件分布。对每个 $d\in\text{Dom}[Y]$，$\mathrm{Pr}(X|Y = d)$ 说明 $X$ 指上的一个分布。把 $\mathrm{Pr}(X)$ 看作是一个函数，它接受任何 $x\in \text{Dom}[X]$ 作为参数，并返回 $\mathrm{Pr}(X = x)$ 。把 $\mathrm{Pr}(X|Y)$ 看作是一个函数，它接受任何 $y\in \text{Dom}[Y]$ 并返回 $\mathrm{Pr}(X|Y = y)$贝叶斯网络利用条件独立性考虑一个故事：如果 Craig 起的太早（E），Craig 可能需要咖啡（C）如果 C，它可能会生气（A）如果 A，血管破裂的几率会增加（B）如果 B，Craig 很可能住院（H）如果你知道了 E、C、A 或 B 中的任何一个，你对 Pr(H) 的评估就会改变。所以 H 不独立于 E, C, A 或 B但是如果你知道 B 的值（真或假），知道了 E、C 或 A 不会影响 Pr(H)。这些因素对 H 的影响是由它们对 B 的影响传递的。Craig 不会因为生气而被送去医院，他被送去是因为他血管破了。因而给定 B，H 独立于 E，C 和 A类似地，给定 A，B 独立于 E 和 C；给定 C，A 独立于 E这意味着：$\mathrm{Pr}(H|B, \{A, C, E\}) = \mathrm{Pr}(H|B)$$\mathrm{Pr}(B|A, \{C, E\}) = \mathrm{Pr}(B|A)$$\mathrm{Pr}(A|C, \{E\}) = \mathrm{Pr}(A|C)$$\mathrm{Pr}(C|E)$ 和 $\mathrm{Pr}(E)$ 不能简化。利用条件独立性：根据链式规则（对于 H, ..., E 的任何实例化）：$\mathrm{Pr}(H, B, A, C, E) = \mathrm{Pr}(H|B, A, C, E) \mathrm{Pr}(B|A, C, E) \mathrm{Pr}(A|C, E)\mathrm{Pr}(C|E) \mathrm{Pr}(E)$根据我们独立性假设：$\mathrm{Pr}(H, B, A, C, E) = \mathrm{Pr}(H|B) \mathrm{Pr}(B|A) \mathrm{Pr}(A|C)\mathrm{Pr}(C|E) \mathrm{Pr}(E)$​由此可通过说明 5 个局部的条件分布来说明完全的联合分布示例量化其中一半的数值是 “1 减去”其他数值，因此，说明完全的联合分布只需要 9 个参数计算 $\mathrm{Pr}(a)$ ：$$ \begin{aligned} \mathrm{Pr}(a) &= \sum_{c_i \in \text{Dom}(C)} \mathrm{Pr}(a|c_i)\mathrm{Pr}(c_i)\\ &= \sum_{c_i \in \text{Dom}(C)} \mathrm{Pr}(a|c_i)\sum_{e_i \in \text{Dom}(E)} \mathrm{Pr}(c_i|e_i) Pr(e_i) \end{aligned} $$$\mathrm{Pr(A)}$ 的具体计算：$$ \begin{aligned} \mathrm{Pr}(c) &= \mathrm{Pr}(c|e)\mathrm{Pr}(e) + \mathrm{Pr}(c|\lnot e)\\ &= 0.9\times 0.7 + 0.5 \times 0.3 = 0.78 \\ \mathrm{Pr}(\lnot c) &= \mathrm{Pr}(\lnot c | e) \mathrm{Pr}(e) + \mathrm{Pr}(\lnot c | \lnot e) \mathrm{Pr}(\lnot e) = 0.22 \\ &= 1- \mathrm{Pr}(c)\\ \mathrm{Pr}(a) &= \mathrm{Pr}(a|c)\mathrm{Pr}(c) + \mathrm{Pr}(a| \lnot c) \mathrm{Pr}(\lnot c)\\ & = 0.3\times 0.78 + 1.0 \times 0.22 = 0.454 \\ \mathrm{Pr}(\lnot a) &= 1- \mathrm{Pr}(a) \end{aligned} $$上面的结构就是一个贝叶斯网络。BN 是对一组变量的直接依赖关系的图形表示，以及一组条件概率表（CPTs），用于量化这些影响的强度。贝叶斯网络推广了上述例子中的思想，从而得到不确定性下表示和推理的有效方法。贝叶斯网路变量 $\{X_1, X_2, \cdots, X_n\}$ 上的一个 BN 包括：一个 DAG(directed acyclic graph，有向无环图)，节点为变量一个 CPTs（conditional probability tables，条件概率表）的集合：$\mathrm{Pr}(X_i | \mathrm{Par}(X_i))$ 对每个 $X_i$关键概念：节点的父节点：$\mathrm{Par}(X_i)$ ，节点的子节点，节点的后代，节点的祖先。家族：由 $X_i$ 及其父节点组成的节点集。示例只显示了若干 CPTs显示表示联合分布需要 $2^{11}-1 - 2047$ 个参数BN 只需要 27 个参数（列出了每个 CPT 的大小）贝叶斯网络的语义贝叶斯网络说明了网络中变量的联合分布可以写成下面的乘积分解。$\mathrm{Pr}(X_1, X_2, ..., X_n) = \mathrm{Pr}(X_n|Par(X_n)) \cdot \mathrm{Pr}(X_{n-1}|Par(X_{n-1})) \cdot ...\cdot\mathrm{Pr}(X_1|Par(X_1))$这个等式对于变量 $X_1, X_2, ..., X_n$ 的任何取值 $d_1, d_2, ..., d_n$ 都成立例如：我们有 $X_1, X_2, X_3$，每个具有论域 $\mathrm{Dom}[X_i] = \{a, b, c\}$，并且 $\mathrm{Pr}(X_1, X_2, X_3) = \mathrm{Pr}(X_3|X_2)\mathrm{Pr}(X_2)\mathrm{Pr}(X_1)$ 则 $\mathrm{Pr}(X_1 = a, X_2=a, X_3=a) = \mathrm{Pa}(X_3=a|X_2=a)\mathrm{Pr}(X_2=a)\mathrm{Pr}(X_1=a)$对于上面的示例网络，有：$$ \begin{aligned} \mathrm{Pr}(A, B, C, D, E, F, G, H, I, J, K) & = \mathrm{Pr}(A) \times \mathrm{Pr}(C|A) \times \mathrm{Pr}(D|A, B)\times \mathrm{Pr}(E|C)\\ & \ \ \ \ \ \times\mathrm{Pr}(F|D) \times \mathrm{Pr}(G) \times \mathrm{Pr}(H|E, F)\\ & \ \ \ \ \ \times \mathrm{Pr}(I|F,G) \times \mathrm{Pr}(J|H, I)\times\mathrm{Pr}(K|I) \end{aligned} $$例题：构建贝叶斯网络总是可以构造一个贝叶斯网络来表示变量 $X_1, X_2, ..., X_n$ 上的任意分布，使用变量的任意顺序。步骤1：使用变量的任意顺序应用链式法则。步骤2：对于每个 $X_i$ ，遍历它的条件 $X_1, X_2, ..., X_{i-1}$ ，并迭代地删除所有变量 $X_j$ 使得给定剩余变量，$X_i$ 条件独立于 $X_j$ 步骤2 将产生乘积分解：$$ \mathrm{Pr}(X_n|\text{Par}(X_n))\mathrm{Pr}(X_{n-1}|\text{Par}(X_{n-1}))...\mathrm{Pr}(X_1) $$步骤3：创建一个有向无环图(DAG) 使得每个变量是一个节点，且变量 $X_i$ 的条件集 $\text{Par}(X_i)$ 是 DAG 中 $X_i$​ 的父节点集合。步骤4：为每一个家族（变量及其父节点集合）指定条件概率表（CPT）。通常我们将 CPT 表示为一个表，将 $\{X_i, \text{Par}(X_i)\}$ 的每个赋值映射到：给定 $\text{Par}(X_i)$ 中的变量具有其指定的值时，$X_i$ 取其值的概率。如果每个变量有 $d$ 个不同的值，我们将需要一个大小为 $d^m$ 的表，其中 $m = |\{X_i, \text{Par}(X_i)\}|$ 与父节点集合的大小成指数关系。变量排序的影响——因果直觉BN 可以用变量的任意顺序构造。然后，一些排序会产生具有非常大的父节点集合的 BNs从经验和概念上讲，构造 BN的一个好方法是使用基于因果关系的pai'xu贝叶斯网络中的独立性：BN 的结构意味着：给定其父节点集合，每个 $X_i$ 都条件独立于它所有的非后代：$$ \mathrm{Pr}(X_i|S\cup \mathrm{Par}(X_i)) = \mathrm{Pr}(X_i|\mathrm{Par}(X_i)) $$对于 $X_i$ 的任何非后代集合 $S$给定 Alarm，JohCalls 和 Earthquake 是独立的D-分离一组变量 D-分离 X 和 Y，如果它阻塞了 BN 中 X 和 Y 之间的每条无向路径。如果证据 D-分离 X 和 Y，则给定证据，X 和 Y 是条件独立的。令 Path 是 BN 中从 X 到 Y 的一条无向路径，则 E 是一个 变量的集合。我们说 E 阻塞路径 Path，如果在路径上有某个节点 Z 使得：情况 1：P 上的一条边进入 Z，一条边离开 Z，并且 Z ∈ E情况 2：P 上的两条边都离开 Z，并且 Z ∈ E情况 3：P 上的两条边都进入 Z，并且 Z 和它的任何后代 都不在 E 中D-分离示例：坐地铁 和 温度升高 不是独立的但是在给定 流感 时，坐地铁 和 温度升高 是独立的疼痛 和 发烧 不是独立的但是，给定 流感 时，疼痛 和 发烧 是独立的流感 和 疟疾 是独立的：发烧 阻塞了这条路径，因为它不在证据中，其后代体温升高也不在证据中给定发烧，流感 和 疟疾 不是独立的：现在路径没有被阻塞。直觉是：如果知道 John 患有流感，这解释了发烧，从而降低了患疟疾的可能性，反之亦然。坐地铁 和 国外旅行 是独立的给定 温度升高，它们不是独立的，因为 情况3 不成立但是给定 温度升高 和 疟疾，它们是独立的示例给定 J，A 和 M 不独立给定 A，M 和 B 是独立的J 和 M 是不独立的，但在给定 A 的情况下是独立的B 和 E 是独立的给定 A/J/M，B 和 E 是不独立的变量消除示例（二值变量）：给定上一页中的贝叶斯网络：$$ \begin{aligned} \mathrm{Pr}(A, B, C, D, E, F, G, H, I, J, K) & = \mathrm{Pr}(A)\times \mathrm{Pr}(B) \times \mathrm{Pr}(C|A) \times \mathrm{Pr}(D|A, B)\\ & \ \ \ \ \ \times \mathrm{Pr}(E|C)\times\mathrm{Pr}(F|D) \times \mathrm{Pr}(G) \times \mathrm{Pr}(H|E, F)\\ & \ \ \ \ \ \times \mathrm{Pr}(I|F,G) \times \mathrm{Pr}(J|H, I)\times\mathrm{Pr}(K|I) \end{aligned} $$并提供了以下证据：$$ E = \{H = \text{true}, I = \text{false}\}，i.e. E = \{h, - i\} $$想知道 $\mathrm{Pr}(D|h, -i)$ （1）写成每个 D 值（即 d 和 ¬d）的总和$$ \sum_{A, B, C, E, F, G, J, K} \mathrm{Pr}(A, B, C, d, E, F, G, h, -i, J, K)\\\sum_{A, B, C, E, F, G, J, K} \mathrm{Pr}(A, B, C, -d, E, F, G, h, -i, J, K) $$（2）现在计算 $\mathrm{Pr}(h, -i)$ $\mathrm{Pr}(h, -i) = \mathrm{Pr}(d, h, -i) + \mathrm{Pr}(-d, h, -i)$（3）最后计算 $\mathrm{Pr}(D|h, -i)$ ：$\mathrm{Pr}(d|h, -i) = \cfrac{\mathrm{Pr}(d, h, -i)}{\mathrm{Pr}(h, -i)}$​ $\mathrm{Pr}(-d|h, -i) = \cfrac{\mathrm{Pr}(-d, h, -i)}{\mathrm{Pr}(h, -i)}$ 为了计算 $\mathrm{Pr}(D|h, -i)$ ，我们只需要计算 $\mathrm{Pr}(-d|h, -i)$ ，然后归一化得到我们想要的条件概率。变量消除变量消除使用乘积分解，以及求和规则从网络中已有信息（CPTs）计算后验概率一个实例之前示例的(1)中，有 $\mathrm{Pr}(d, h, -i) = \sum_{A, B, C, E, F, G, J, K} \mathrm{Pr}(A, B, C, d, E, F, G, h, -i, J, K)$使用贝叶斯网络乘积分解，我们有：$$ \begin{aligned} & \sum_{A, B, C, E, F, G, J, K} \mathrm{Pr}(A, B, C, d, E, F, G, h, -i, J, K) \\ & \ \ \ \ \ = \mathrm{Pr}(A)\times \mathrm{Pr}(B) \times \mathrm{Pr}(C|A) \times \mathrm{Pr}(d|A, B)\times \mathrm{Pr}(E|C)\times\mathrm{Pr}(F|d) \times \mathrm{Pr}(G) \\ & \ \ \ \ \ \ \ \ \ \ \times \mathrm{Pr}(h|E, F) \times \mathrm{Pr}(-i|F,G) \times \mathrm{Pr}(J|h, -i)\times\mathrm{Pr}(K|-i) \end{aligned} $$变量消除 （VE）一般来说，在每个阶段 VE 将计算一个表，表中的每个数值 对应于 求和式中 变量的不同实例化。这些表格的大小和求和式中出现的变量个数成指数关系，例如：$$ \sum_F \mathrm{Pr}(F|D)\mathrm{Pr}(h|E, F)t(F) $$依赖于 D 和 E 的值，因此我们将得到 由 $|\mathrm{Dom}[D]||\mathrm{Dom}[E]|$ 个不同的数组成的表。因子（Factor）一个因子是一些变量的一个函数，例如，$\mathrm{Pr}(C|A) = f(A, C)$ ：它将其参数的每个值映射到一个数值。表格表示的大小与因子中变量的个数成指数关系。注意原始的 CPTs 也是值的表。因此，我们也称它们为因子。记号：$f(\textbf{X}, \textbf{Y})$ 表示 变量 $\textbf X\cup\textbf Y$ 上的一个因子（其中 $\textbf X$ 和 $\textbf Y$ 是变量的集合）因子上有不同的操作。两个因子的乘积设 $f(\textbf{X}, \textbf Y)$ 和 $g(\textbf{Y}, \textbf Z)$ 是两个因子，有共同的变量集 $\textbf Y$f 和 g 的乘积，记为 $h = f\times g$ （或 $h = fg$），定义为对因子在一个变量上求和令 $f(X, \textbf Y)$ 是一个具有变量 X 的因子（$\textbf Y$ 是一个集合）从 $f$ 中对变量 X 求和，产生一个新的因子 $h = \sum_X f$ ，定义为：$$ h(\textbf Y) = \sum_{x\in \mathrm{Dom}(X)} f(x, \textbf Y) $$例如：这里的 $f(A, B)$，不是 $\mathrm{Pr}(AB)$ ，而是 $\mathrm{Pr}(B|A)$限制一个因子令 $f(X, \textbf Y)$ 是一个具有变量 X 的因子（$\textbf Y$ 是一个集合）我们通过将 X 设置为 值a 并“删除”f 论域中不一致的元素，将因子 f 限制到 X = a。将$h = f_{X = a}$ 定义为 $h(\textbf Y) = f(a, \textbf Y)$例如：VE 算法给定一个带有 CPTs F 的贝叶斯网络，查询变量 Q，证据变量集合 $\textbf E$（观察到有值 e），和其余变量 Z。计算 $\mathrm{Pr}(Q|\textbf E)$将提到 $\textbf E$ 中的变量的每个因子 $f\in F$ 替换为 其限制 $f_{\textbf E=e}$ （这可能产生一个“常数”因子）将每个 $Z_j$ 按照给定顺序 消除 $Z_j \in \textbf Z$ 如下：令 $f_1, f_2, ..., f_k$ 是 F 中包含 $Z_j$ 的因子计算新因子 $g_i = \sum_{Z_j}f_1\times f_2\times ... \times f_k$从 F 中删除因子 $f_i$ 并在 F 中添加新的因子 $g_j$剩余的因子仅提到查询变量 Q。取它们的乘积，并归一化得到 $\mathrm{Pr}(Q|\textbf E)$VE：示例Factor：$f_1(A)f_2(B)f_3(A, B, C)f_4(C, D)$Query：P(A) ?Evidence：D = dElim. Order：C, B限制：使用 $f_5(C) = f_4(C, d)$ 代替 $f_4(C, D)$ Step 1：消除 C：计算和加入 $f_6(A, B) = \sum_C f_5(C)f_3(A, B, C)$ 移除：$f_3(A, B, C)$，$f_5(C)$ Step2：消除 B：计算和加入 $f_7(A) = \sum_B f_6(A, B)f_2(B)$ 移除：$f_6(A,B)$，$f_2(B)$ 最后的因子：$f_7(A), f_1(A)$，乘积 $f_1(A)\times f_7(A)$ 是没有归一化的，需要归一化得到最后的结果：$$ P(A|d) = \cfrac{f_1(A)\times f_7(A)}{\sum_A f_1(A)f_7(A)} $$数值示例.jpg)第7章：机器学习监督学习（分类与回归，感知机、逻辑回归；神经网络、反向传播、CNN、RNN）；非监督学习（K-means）；强化学习（MDP定义、状态值函数和动作值函数、Q学习及SARSA、DQN）