# AI & ML Lecture Notes: Full LLM Context > Lecture notes for Artificial Intelligence & Machine Learning (AI & ML) course @ 2025-2026 Fall, Glasgow College, UESTC. Source website: https://cateds.github.io/AI-MachineLearning.md/ LLM index: https://cateds.github.io/AI-MachineLearning.md/llms.txt Source repository: https://github.com/Cateds/AI-MachineLearning.md This generated file is intended for NotebookLM or other tools that prefer a single reference source. It contains the homepage body and all lecture Markdown files in sidebar order. Local Markdown document links have been rewritten to absolute course URLs, and local asset links have been rewritten to raw GitHub source URLs where possible. Each source document starts at an H2 heading so horizontal rules in the original notes remain ordinary content. ## Contents - [Artificial Intelligence & Machine Learning (AI & ML) Lecture Notes @ 2025-2026 Fall](https://cateds.github.io/AI-MachineLearning.md/) - [AI 介绍](https://cateds.github.io/AI-MachineLearning.md/Part.0/lecture1.html) - [优化的基本概念](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture2.html) - [Lec.3 遗传算法](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html) - [Lec.4 约束和多目标优化](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture4.html) - [Lec.5: Combinatorial Optimization (组合优化)](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture5.html) - [机器学习 (Machine Learning)](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture7.html) - [机器学习及数据预处理](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture8.html) - [特征选择](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture9.html) - [支持向量机 (Support Vector Machine, SVM)](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture10.html) - [人工神经网络入门](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture11.html) - [Lecture 01 - Introduction to AI](https://cateds.github.io/AI-MachineLearning.md/Addon/Introduction/introduction.html) - [Lecture 02 - Fundamental Concepts in Optimization](https://cateds.github.io/AI-MachineLearning.md/Addon/Evolutionary_Computation/lecture2.html) ## Artificial Intelligence & Machine Learning (AI & ML) Lecture Notes @ 2025-2026 Fall Source: https://cateds.github.io/AI-MachineLearning.md/ Repository path: lectures/index.md > Lecture notes for Artificial Intelligence & Machine Learning (AI & ML) course @ 2025-2026 Fall, Glasgow College, UESTC. 原仓库 GitHub 地址： 如果有帮助的话，欢迎在 GitHub 上给本项目点个 Star ⭐️ **PDF 下载 (GitHub Releases)：** - Introduction to AI 1. [AI 介绍](https://cateds.github.io/AI-MachineLearning.md/Part.0/lecture1.html) - Evolutionary Computation (进化计算) 1. [优化的基本概念](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture2.html) 2. [遗传算法](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html) 3. [约束和多目标优化](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture4.html) 4. [组合优化](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture5.html) - Machine Learning (机器学习) 1. [机器学习概述](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture7.html) 2. [模型训练及数据预处理](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture8.html) 3. [特征选择](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture9.html) 4. [支持向量机](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture10.html) 5. [人工神经网络入门](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture11.html) 还有 Pull Request 上来的额外内容： - 知识点总结和习题解析 - [Lec.0: AI 介绍](https://cateds.github.io/AI-MachineLearning.md/Addon/Introduction/introduction.html) - [Lec.1: 优化的基本概念](https://cateds.github.io/AI-MachineLearning.md/Addon/Evolutionary_Computation/lecture2.html) > 我觉得今年的内容量已经算得上是每章塞爆了，结果你说今年相比去年砍了很多内容是什么意思？ ### 给 LLM / NotebookLM 使用 如果你是一个 LLM，或者想把这份讲义添加为 LLM 参考源，请使用以下链接： - [llms.txt](./llms.txt)：给 LLM 发现和索引本站内容的轻量入口。 - [llms-full.txt](./llms-full.txt)：包含首页和全部讲义 Markdown 的全文文件，适合直接添加到 NotebookLM。 ### 许可证 除非另有说明，本仓库的原创课程笔记内容与导出的 PDF 采用 [CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/) 许可证发布。 ## AI 介绍 Source: https://cateds.github.io/AI-MachineLearning.md/Part.0/lecture1.html Repository path: lectures/Part.0/lecture1.md ### AI 的定义 智能 (Intelligence) 在韦氏词典里的解释是学习或理解或英语新的情况的能力；推理，或者熟练地使用推理。也就是说，我们如果要说一个东西是有智能的，它需要有这么几种能力 - 认知能力： 处理信息，从经验中学习，在新的情况中运用知识 - 适应能力： 根据环境的变化调整自己的行为 - 解决问题能力： 分析情况，然后生成解决方案并评估最优方案 而人工智能 (Artificial Intelligence, AI) 则是一门新兴的技术科学，研究并开发用于模拟、延伸和增强人类智能以及其他自然的智能的理论、方法、技术和应用系统。 ### AI 的历史 #### 1950 年代 ![1766567291078](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.0/lecture1.assets/1766567291078.png) AI 最早诞生于 1956 年，达特茅斯会议 (Dartmouth Conference) 上，约翰·麦卡锡 (John McCarthy) 提出了“人工智能”这个术语，并与其他研究人员一起探讨了如何让机器模拟人类智能的可能性。 之后，1952 年，Arthur Samuel 开发了一个可以学习下棋的程序，这被认为是机器学习的早期实例。 1955 年，Allen Newell 和 Herbert A. Simon 开发了逻辑理论家 (Logic Theorist)，这是第一个能够证明数学定理的计算机程序。 1957 年，Allen Newell 和 Herbert A. Simon 开发了通用问题求解器 (General Problem Solver, GPS)，这是一个能够解决各种问题的程序。 在当时，AI 发展极其迅速，人们对 AI 的未来有了极度乐观的想法 - Herbert Simon 预测：“在二十年内，机器将能够做任何人类能做的工作。” - Marvin Minsky 预测：“在十年内，人工智能的问题将被解决。” - Claude Shannon 预测：“我设想这样一个时代：我们对于机器人就像狗对于人类一样，我支持机器” > 预测：我要给机器当狗 > > 实际:【“我是狗？”邪恶科学家 Vedal 和他的走狗牛肉】 然而，过了比预料还久的时间后，在 1997 年，IBM 的深蓝 (Deep Blue) 击败了当时的国际象棋世界冠军加里·卡斯帕罗夫 (Garry Kasparov)，这标志着 AI 在特定领域取得了重大突破。 在 1966 年，ALPAC (Automatic Language Processing Advisory Committee, 自动语言处理咨询委员会) 报告发布后，美国政府大幅削减了对自然语言处理 (NLP) 研究的资助，导致了第一次 AI 冬天 (AI Winter)。 --- 在早期，AI 研究确实有过很多困难，比如当时算力不足，数据和存储资源有限，算法和理论有限，当时的计算机成本也很高，同时信息也有限。这些时代的局限性都限制了 AI 的发展。 但是，早起的发展也为后来的 AI 研究奠定了基础。其贡献了基础算法的发展，开创了自然语言处理，同时引入了机器学习的概念。 #### 1970 年代 - 1980 年代 这一年代的 AI 发展主要有两个特征 1. 基于知识的系统的发展 2. 基于规则的专家系统的成功 在 1970 年代，DENDRAL 系统被开发出来，用于化学分子结构的自动推理和识别。这是首个基于规则的专家系统。 MYCIN 系统在 1970 年代后期被开发出来，用于诊断血液感染并推荐合适的抗生素治疗。MYCIN 系统展示了基于规则的专家系统在医疗领域的潜力。 XCON 系统在 1980 年代被开发出来，用于将客户订单转化为详细的零件规格，每年为数字设备公司节省四千万美元。 这一年代创造出了首个对行业产生重大影响的实际应用，其中知识发挥了关键作用。但是，知识并非基于确定性规则，需要考虑不确定性；创建和维护这些规则需要大量人工劳力，难以持续。 在 1987 年底，Lisp 机器市场崩溃，导致了第二次 AI 冬天 (AI Winter)。 #### 人工神经网络 人工神经网络 (Artificial Neural Networks, ANN) 的概念最早可以追溯到 1943 年，当时 Warren McCulloch 和 Walter Pitts 提出了一个数学模型，模拟了神经元的工作原理。这被认为是人工神经网络的早期基础。 感知机 (Perceptron) 是由 Marvin Minsky 和 Seymour Papert 在 1958 年提出的，这是一个简单的神经网络模型，能够进行二分类任务。然而，他们在 1969 年的著作《感知机》中指出，单层感知机无法解决非线性可分的问题（如 XOR 问题），这导致了对神经网络研究的兴趣下降。 多层感知机 (Multi-Layer Perceptron, MLP) 和反向传播 (Backpropagation) 是 Geoffrey Hinton、David Rumelhart 和 Ronald Williams 在 1986 年提出的，这使得训练多层神经网络成为可能，重新点燃了对神经网络的兴趣。神经网络理论上可以逼近任意函数，反向传播算法在多层网络训练中发挥了关键作用。 卷积神经网络 (Convolutional Neural Networks, CNN) 是由 Yann LeCun 在 1990 年代初提出的，最著名的应用是手写数字识别（如 LeNet）。这项工作是卷积神经网络实际应用中的一个重要里程碑。 --- 之后，进入到了深度学习 (Deep Learning) 的时代。 AlexNet 在 2012 年被 Alex Krizhevsky、Ilya Sutskever 和 Geoffrey Hinton 提出，并在 ImageNet 图像分类竞赛中取得了显著的成功，标志着深度学习在计算机视觉领域的突破。 AlphaGo 在 2016 年由 Google DeepMind 开发，击败了围棋世界冠军李世石，展示了深度强化学习在复杂策略游戏中的潜力。 ChatGPT 在 2022 年由 OpenAI 发布，其推进了自然语言理解与生成，变革了人机交互，在各个领域展现出了重要应用。 --- 现在，人工智能已经成为了一门多学科交叉的领域，涵盖了计算机科学、数学、统计学、认知科学等多个学科。AI 技术已经广泛应用于各个领域，如医疗、金融、交通、娱乐等，极大地改变了我们的生活方式。 ![1766569472730](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.0/lecture1.assets/1766569472730.png) 但是，现在的人工智能仍然没有发展成人类那样的通用智能 (Artificial General Intelligence, AGI)，它们通常只能在特定任务上表现出色，而在其他任务上则表现不佳。机器需要依赖大量的数据而完成简单的任务，而人类只需要少量的示例就能学会新的技能。 ### 现在的 AI 研究以及应用 现在的 AI 已经广泛的应用到了各个领域，如 - 电脑游戏 - 有的角色会内置 AI - 语音合成、识别和理解 - 在有限词汇量的情况下表现良好 - 无约束的语音理解问题尚未完全理解，但是 ChatGPT 和 Bard 等大语言模型已经在这方面取得了显著的进展 - 银行 - 自动支票阅读机、签名验证 - 自动化贷款申请分类 - 数码相机 - 人脸识别对焦 - 邮局 - 自动地址识别和邮件分类 - 客户服务 - 自动语音识别 - 网络服务 - 自动风险识别 - 智能广告推送 在科学和工程领域，AI 也有广泛的应用 - 预测性维护 - 故障检测和诊断 - 集成电路设计自动化 - 信号处理 - 人工智能驱动的天线设计 ![1766569922664](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.0/lecture1.assets/1766569922664.png) ### 课程总览 ![1766569960925](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.0/lecture1.assets/1766569960925.png) AI 的分支如下 - 符号主义人工智能 (Symbolic AI) - 棋类 - 聊天机器人 - 专家系统 - 进化算法 (Evolutionary Algorithms) - 机器学习 (Machine Learning) - 基于统计的方法 - 支持向量机 - 人工神经网络 - 卷积神经网络 - 深度学习 - 决策树 这门课主要教后两部分的其中一部分内容。 ## 优化的基本概念 Source: https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture2.html Repository path: lectures/Part.1/lecture2.md > 虽然说是基本概念，但是其实是后续几章内容的概述。 ### 定义 优化 (Optimization) 指的是寻找一个最好的解的过程。对于求解问题，可以使用普通的优化方法或者基于 AI 的优化方法——在大多数情况下基于 AI 的优化算法更易于使用。 #### 引入 1: 旅行商问题 一个典型的优化问题是旅行商问题 (Traveling Salesman Problem, TSP)， 即一个旅行商需要访问若干个城市，并且每个城市只能访问一次，最后回到出发点。目标是找到一条路径，使得总的旅行距离最短。 我们先用这种方式表示走过的路径： $p=\{p(1), p(2), \ldots, p(n), p(1)\}$ ，其中 $p(i)$ 表示第 $i$ 个城市。这条路径就指的是从 1 到 2，到 3，直到最后回到 1 的路径。 这个问题可以换一种方式进行表达：如果我们把旅行家的总距离用函数 $L(p)$ 来表示，其中 $p$ 是一个城市的排列，那么我们需要找到一个 $p$ 使得 $L(p)$ 最小。也就是： $$ \begin{aligned} & \min_p L(p) \\ &p \in \Omega \quad \Omega: \text{所有城市的排列} \end{aligned} $$ 这就是一个优化问题，其中目标函数是 $L(p)$ ，解空间是所有城市的排列 $\Omega$ 。 旅行商问题在很多场景下都有应用，比如一个机械臂的路径规划问题，或者一个送货员需要规划送货路线的问题。一个机械臂有多个目标点需要访问，如何规划路径使得机械臂的运动距离最短？这就是一个典型的优化问题。 #### 引入 2: 二次函数优化 (Quadratic Function Optimization) 一个场景是，有 n 个站点，需要派遣 n 个专家去访问这些站点，每个专家访问一个站点，目标是最小化总的访问成本。 ![1764939093191](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764939093191.png) 给定了不同站点之间的距离以及专家访问不同站点的成本，如途中 Site 1 和 2 之间的距离是 $d_{12} = 5$ ，专家的成本系数如 $f_{12} = 1$ 。我们认为每种部署方式就是这个优化问题的一个解，用 $p=(p(1), p(2), p(3)) = (2,3,1)$ 表示，即专家 1 访问站点 2，专家 2 访问站点 3，专家 3 访问站点 1。最终可以写成这样： $$ \begin{aligned} & \min_p \sum^{n-1}_{i=1} \sum^{n}_{j=i+1} f_{ij} \cdot d_{p(i)p(j)} \\ & p \in \Omega: \text{所有站点的排列} \end{aligned} $$ #### 引入 3: 背包问题 ![1764939426088](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764939426088.png) 背包问题是一个经典的组合优化问题，假设有 n 个物品，每个物品有一个重量和一个价值，还有一个背包，背包有一个容量限制。目标是将物品放入背包中，使得总价值最大，同时背包的重量不超过其容量。 在这个情况中，解是一串二进制变量，表示每个物品是否被放入背包。目标函数是总价值，约束条件是背包的重量不能超过其容量。 #### 引入 4: 连续优化问题 ![1764939552090](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764939552090.png) 图中是一个典型的双变量优化问题，目标是找到 $(x, y)$ 使得函数 $f(x, y)$ 最小。这个问题的解空间是连续的二维平面。 ![1764939561823](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764939561823.png) ![1764939648754](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764939648754.png) 这个是与实际工程相结合的优化问题，需要找到一个 Resonator（谐振腔）的最佳设计参数，使得其性能指标达到最优。设计参数可以是谐振腔的长度、宽度等，目标是找到最小化和最大化的 $|S11|$ 性能指标。 ### 目标和约束 对于普通的优化问题，一共有三个部分需要关注：决策变量，目标函数和约束条件。 对于一个标准的优化问题，如下所示： $$ \begin{aligned} & \min f(x) = -(x-1)^2\\ & \mathrm{s.t.} \ g(x) = x-1.5 \geq 0 \end{aligned} $$ 这里，需要求最小值的函数 $f(x)$ 称为目标函数 (Objective Function)，而 $g(x) \geq 0$ 称为约束条件 (Constraint Condition)。目标变量 $x$ 称为决策变量 (Decision Variable)。 其中，可行的解指的是满足约束条件的解，称为可行解 (Feasible Solution)；否则称为不可行解 (Infeasible Solution)。所有的可行解组成的集合称为可行域 (Feasible Space)。 不同的解之间通常会有优劣之分，一般会比较其目标函数值，目标函数值更优的解称为更优解 (Better Solution)。在所有可行解中，目标函数值最优的解称为最优解 (Optimal Solution)。可行解和不可行解之间，认为可行解是更优的。两个不可行解之间，则比较其违反约束的程度，违反约束较少的解更优。 有些问题会有更加复杂的约束条件，比如这个例子： ![1764940681651](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764940681651.png) 目标是最小化功率，有多个目标变量（每个晶体管的 W 和 L），而约束条件很多，如 DC 增益、频率响应等。最终根据这些约束条件，找到一个可行解，使得功率最小。 ### 多目标优化 之前提到的优化函数都只有一个目标函数，但在实际应用中，往往会有多个目标需要同时优化，这就是多目标优化 (Multi-objective Optimization)。如： $$ \begin{aligned} & \max f_1(x_1, x_2, \ldots, x_n)\\ & \max f_2(x_1, x_2, \ldots, x_n)\\ & x = (x_1, x_2, \ldots, x_n) \in D, D\subseteq R^n \end{aligned} $$ 这种情况下，决策变量是 $x$ ，目标函数有两个，分别是 $f_1$ 和 $f_2$ 。在多目标优化中，通常不存在一个解能够同时使得所有目标函数达到最优，因此需要引入帕累托最优 (Pareto Optimal) 的概念。 帕拉特最优，指的是没有其他解在所有目标上都优于该解。换句话说，如果一个解在某个目标上更优，但在另一个目标上更差，那么它就是帕累托最优的。对于任意两个解，一共有三种关系： 1. 一个解在所有目标上都优于另一个解； 2. 一个解在所有目标上都劣于另一个解； 3. 一个解在某些目标上优于另一个解，在其他目标上劣于另一个解； 对于前两个情况，我们说较好的解支配 (dominates) 较差的解；对于第三种情况，我们说这两个解互不支配 (non-dominated)。 最终，帕累托最优解组成的集合称为帕累托前沿 (Pareto Front)。 ![1764942248674](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764942248674.png) 在帕累托前沿上，每个解都是帕累托最优的，无法再通过优化某一个目标而不损害其他目标来改进。帕累托前沿是对最终的目标函数值来说的，这些函数值对应的决策变量的集合称为帕累托集 (Pareto Set)。 换句话说，Pareto Front 和 Pareto Set 的关系是: $$ PF = F(PS) $$ ### 全局和局部优化 #### 全局最优解 对于一个优化问题 $$ \begin{aligned} & \max f(x) \\ & x \in \Omega \end{aligned} $$ 最终得到一个全局最优解 $x^*$ ，满足对于所有 $x \in \Omega$ ，都有 $f(x^*) \geq f(x)$ 。 #### 邻域 一个解 $x$ 的邻域 (Neighborhood) 指的是在某个距离范围内的解集合，比如在连续优化问题中，我们认为距离小于 $0.1$ 的解都属于 $x$ 的邻域，就有 $\Omega = \{x_1 x_2\} | (x_1- x)^2 + (x_2 - y)^2 \leq 0.1^2$ 。 对于其他的问题有不同的定义方式，如如果决策变量是一个排列 $p = (p(1), p(2), \ldots, p(n))$ ，那么可以定义邻域为通过交换两个位置得到的所有排列组成的集合。 #### 局部最优解 如果一个解在它的邻域内有着最好的目标函数值，那么它就是一个局部最优解 (Local Optimal Solution)。也就是说，对于一个解 $x^*$ ，如果对于所有 $x$ 属于 $x^*$ 的邻域 $\mathcal{N}(x^*)$ ，都有 $f(x^*) \geq f(x)$ ，那么 $x^*$ 就是一个局部最优解。 全局最优解一定是局部最优解，但局部最优解不一定是全局最优解。换句话说，全局最优解在整个解空间中是最好的，而局部最优解只是在其邻域内是最好的。 ![1764943819223](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764943819223.png) 通常，寻找局部最优解会制定一个起始点，然后在其邻域内搜索更优的解，直到找不到更优的解为止。而全局优化可以不需要起始点，直接在整个解空间中搜索最优解。 目标函数可以分为单模态 (Unimodal) 和多模态 (Multimodal) 两种类型。单模态函数只有一个全局最优解，而多模态函数有多个局部最优解和一个全局最优解。 ![1764943949170](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764943949170.png) ### 将工程问题建模成优化问题 这一部分注重的是实际的数学建模过程。通常，工程问题可以通过以下步骤建模成优化问题： 1. 确定要求 2. 分析要求中的目标和约束 3. 定义决策变量和参数 4. 确定搜索空间 5. 确定是否有起始点 6. 确定怎么获得期望函数值和约束 ![1764944119031](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764944119031.png) 以这个项目为例子，这几个过程分别是这样的： 1. 确定要求 - 操作频率范围：3.3 GHz ~ 7.3 GHz；通带：4 GHz ~ 7 GHz - 两个阻带：3.3 GHz ~ 3.92 GHz 和 7.08 GHz ~ 7.3 GHz - 通带性能要求（例如）：通带内最大 |S11| 要尽可能小（常用阈值示例：|S11| ≤ -10 dB） - 阻带性能要求（例如）：阻带内抑制应达到设计要求（常用阈值示例：阻带衰减 ≥ 20 dB） - 其它工程约束：器件尺寸、制造公差、插损及带内群延迟等 2. 分析要求中的目标和约束 - 目标：最小化通带内的最大 |S11|（即提高匹配/降低反射） - 约束：满足两个阻带的抑制要求、物理和制造约束（如尺寸、最小线宽、间距） - 说明问题类型：这是一个单目标（受约束）优化问题，若同时考虑插损/尺寸可转成多目标问题 3. 定义决策变量和参数 - 决策变量：12 个几何参数（如每段的长度、宽度、耦合间距等） - 固定参数/环境参数：基板介电常数、厚度、金属厚度、馈入位置、制造公差等 4. 确定搜索空间 - 为每个几何变量给出上下界（由制造能力或电磁学可行性限定），例如 $$ l_i \in [l_\min, l_\max], \quad w_i \in [w_\min, w_\max] $$ - 决定连续还是离散（本例通常采用连续实值搜索空间） 5. 确定是否有起始点 - 有：可用等效电路或经验设计给出初始解，加速局部优化收敛 - 若无：采用随机/拉丁超立方/均匀采样等策略生成初始种群 6. 确定怎么获得期望函数值和约束 - 使用电磁仿真软件（提取 S-parameters）计算目标函数（如通带最大 |S11|）和约束（阻带抑制、插损等） - 可结合快速等效电路或 surrogate 模型（代理模型）降低仿真开销 - 最终结果需用高精度 EM 仿真或实验测量验证 在完成上述步骤后，可以使用 MATLAB 的 Toolbox 或 Python 的 SciPy 等工具来实现优化算法，求解该优化问题。在这个问题上，最终得到了这样的结果： ![1764944931945](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764944931945.png) ![1764944936860](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764944936860.png) ![1764944947277](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture2.assets/1764944947277.png) ### 案例分析 1 ~ 4 > 这一块具体是使用四个工程案例来说明如何将工程问题建模成优化问题，略过不表。 > > 这四个案例分别是： > > 1. 微波偶极子天线设计 > 2. 天线阵列设计 > 3. 人体动作识别 > 4. 网络切片资源分配 > > 每个案例都按照前面提到的六个步骤进行建模，并给出了具体的数学表达式和优化目标。有些在 Lab 中已经提及。 ## Lec.3 遗传算法 Source: https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html Repository path: lectures/Part.1/lecture3.md ### 介绍 遗传算法 (Genetic Algorithm, GA) 是一种模拟自然选择和遗传机制的优化算法。它通过模拟生物进化过程中的选择、交叉和变异等操作，逐步改进解的质量，以找到问题的最优解或近似最优解。GA 用户用于优化问题，通常易于实施，能够求解复杂的优化问题，在计算机算力逐渐上升的趋势中，GA 的应用越来越广泛。 这种算法属于计算智能 (Computational Intelligence) 的范畴（如神经网络、进化计算），从自然界中获取解决问题的方案的思路。从自然界中的生物进化，我们可以提取出这样的特征 - 个体 (Individual) - 问题的一个解 - 用染色体 (Chromosome) 来表示 - 种群 (Population) - 一些个体的集合 - 选择 (Selection)：适者生存 - 一个个体的性能越好，就更可能成为亲代，产生下一代 - 交叉 (Crossover)：基因重组 - 子代的染色体由它的两个亲代的染色体组合而成 - 变异 (Mutation)：基因突变 - 个体的染色体在某些位置上发生随机变化 ![1758116029487](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758116029487.png) ### 算法流程 进行遗传算法的过程，就是模拟生物进化的过程。 - 首先，有一个种群 - 经过选择之后形成交配池 (Mating Pool) - 亲代发生交叉和变异后形成新的种群 - 用新的种群替代原本的种群，重复以上操作 - 如果到达了停止条件，则结束优化过程，输出结果 ![1758122923351](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758122923351.png) 首先需要考虑的是如何表示一个个体或者一组解，以满足我们需要后续操作的特质，如交换、变异等。常见的编码方式有以下几种 - 二进制字符串 (Binary String) - 整个字符串相当于个体，每一位相当于基因 - 可以通过二进制和十进制的转换来表示整数 - 实数编码 (Real-valued Encoding) - 每个基因是一个实数，适合实值优化问题 - 排列编码 (Permutation Encoding) - 每个个体是一个给定元素的某种排列 - 适合表示排列问题，如旅行商问题 - 整数编码 (Integer Encoding) - 每个基因是一个整数，适合整数规划问题 #### 初始化种群 初始化种群是遗传算法的第一步，通常是随机生成一组个体。需要关注的重要参数主要有两个：种群数量 (Population Size) 和初始化方法 (Initialization Method)。 种群数量影响算法的多样性和收敛速度，通常需要根据具体问题进行调整。初始化方法可以是完全随机生成，也可以结合一些启发式方法，以提高初始解的质量。 #### 选择操作决定哪些个体可以进入交配池 选择操作模拟自然界中“适者生存”的过程。选择操作决定哪些个体可以进入交配池，同时更优秀的个体有更高的概率被选择。判定优秀与否的标准是适应度函数 (Fitness Function)，它衡量个体的质量。 常见的选择操作有： - 比例选择 (Proportional Selection) 根据个体的适应度值按比例选择 比如，对于优化问题 $$ \max G(x) = -(x-8)^2 + 65, x \in [0,15] \& x \in \mathbb{N} $$ 一个个体进入交配池的概率正比于它的适应度 (Fitness) $$ \mathrm{prob}(x_i) = \frac{G(x_i)}{\sum_{j=1}^{N} G(x_j)} = \frac{ 它的适应度 }{ 全部个体的适应度之和 } $$ ![1758119088987](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758119088987.png) - 轮盘赌选择 (Roulette Wheel Selection) 将个体的适应度值映射到一个轮盘上，适应度越高的个体占据的区域越大，随机旋转轮盘选择个体 ![1758118994431](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758118994431.png) 具体实现方法可以是生成一个随机数，根据随机数落在的区间选择对应的个体 - 锦标赛选择 (Tournament Selection) 随机选择若干个体，选出其中最优秀的个体 - 截断选择 (Truncation Selection) 选择适应度最高的一部分个体 | | 最优性 (Optimality) | 多样性 (Diversity) | | ---------- | ------------------------ | ------------------ | | 交配池数量 | 多于前代种群数量 | 少于前代种群数量 | | 选择的作用 | 将搜索导向更有前途的部分 | 减少不同种类的数量 | #### 交叉 (Crossover) 和变异 (Mutation) 交叉和变异是生成新的种类的个体/解的方法。它们直接作用在个体上，通常在选择过程之后进行操作。在大多数情况下，交叉和变异的过程是和个体的适应度相互独立的。 交叉操作指的是两个解的基因重组，交换各自染色体的一部分。其可以分为单点交叉 (Simple Crossover / One-Point Crossover)、K 点交叉 (K-Point Crossover) 等 ![1758123144579](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758123144579.png) - 单点交叉 - 从交配池中随机选择两个亲代 - 在染色体上随机选择一个交换位点 - 交换两个亲代在该位点之后的基因，生成两个子代 - K 点交叉 - 同理选择两个亲代 - 在染色体上随机选择 k 个交换位点 - 交叉这些位点之间的基因，生成两个子代 同样重要的是发生交叉的改率，成为交叉率 (Crossover Rate)，其表示任意从交配池中选择的两个亲代发生交叉的改率，表示为 $P_c$。如果两个亲代没有发生交叉，则直接复制到下一代。典型的交叉率在 $0.6$ 到 $0.9$ 之间。 在程序实现上，通常是每个个体生成一个随机数 $R_c$，当满足 $R_c \le P_c$ 时，才进行交叉操作。 交叉操作可能会增加或者减小子代的平均适应度，但是会增加种群的多样性。在某些情况下，交叉操作不会生成新的个体，比如两个亲代完全相同，或者交换的位点在染色体的末尾，这种情况下选择和交叉操作无法解决问题。可以引入变异 (Mutation) 来增加种群的多样性。 对于每一个子代个体，有一个概率可以发生变异，记作 $P_m$，典型值为 $0.001$ 到 $0.01$ 之间。发生变异时会改变个体的某些基因值，进而产生新的个体。 #### 停止条件 如果停止条件没有满足，则持续进行选择、交叉和变异，生成新的种群，替代原本的种群，直到满足停止条件为止。常见的停止条件有： - 达到最大迭代次数 - 种群收敛 - 达到预期的适应度水平 ### 优缺点 - 优点 - GA 是一个通用的优化算法，和应用的领域无关 - 多种情况可以并行计算，提高计算效率 - 可以获得多种最优解，适合多目标优化问题 - 易于实现 - 缺点 - 可能不能获得全局最优解 - 参数选择对结果影响较大 - 计算资源消耗较大，计算不够快 ### 使用遗传算法 要使用 GA 算法，需要先明确需要求解的问题和 GA 的各个参数的对应 - 求解的是什么问题 - 搜索空间是什么？有什么约束？ - 如何设计适应度函数？ - [如何表示一个解](#如何表示一个解) - [如何初始化种群](#怎么样初始化种群) - [如何合适的交叉和变异](#如何合适的交叉或变异) - [如何选择作为亲代的个体](#如何选择作为亲代的个体) - [怎么用新的种群替代原本的种群](#怎么用新的种群替代原本的种群) - [选择什么样的停止条件](#选择什么样的停止条件) #### 如何表示一个解 表示一个解的方式有很多种，通常根据求解问题的特性来选择合适的编码方式，如搜索空间是连续的还是离散的，解的维度是多少等。 [常见的编码方式](#算法流程)有二进制编码、实数编码、排列编码和整数编码等。选择合适的编码方式可以影响算法的效率和效果。 #### 怎么样初始化种群 [初始化种群](#初始化种群)的目标是从搜索空间中均匀地采样，确保种群的多样性。常见的方法有随机生成和启发式生成。 - 对于二进制编码，可以随机生成二进制字符串，每一位是 0 或 1 的概率都是 0.5 - 对于实数编码，可以在每个维度上的取值范围内均匀随机采样 - 有一些其他的更试验性的方法 基于这样的采样方法，产生 N 个个体，组成初始种群。 #### 如何合适的交叉或变异 ##### 变异 合适的变异操作需要保证 1. 可以访问到搜索空间中的所有区域 2. 变异的频率需要合适 3. 变异后的结果应该是可行的解 4. 如果对于特定问题有更合适的变异操作，可以优先使用 对于不同的编码方式，变异的操作也不同，常见的有 - 对于二进制编码，可以随机选择某一位进行翻转 - ![1758201903614](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758201903614.png) - 对于实数编码，可以是对某一位加一个正态分布的随机数 - $y_i = x_i + N(0,\sigma_i)$ - 对于排列，可以选择两个不同的位置进行交换 - ![1758201916876](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758201916876.png) ##### 交叉 对于交叉，合适的交叉操作需要保证： 1. 生成的子代同时继承两个亲代的特征 2. 交叉后的结果应该是可行的解 3. 如果对于特定问题有更合适的交叉操作，可以优先使用 对于不同的编码方式，交叉的操作也不同，常见的有 - [单点交叉](#交叉-crossover-和变异-mutation) - 在染色体上随机选择一个交换位点 - 交换两个亲代在该位点之后的基因，生成两个子代 - 适用于二进制编码和实数编码 - [K 点交叉](#交叉-crossover-和变异-mutation) - 在染色体上随机选择 k 个交换位点 - 交叉这些位点之间的基因，生成两个子代 - 适用于二进制编码和实数编码 - m 亲本交叉 - 从 m 个亲本中选择基因，生成两个子代 - 适用于二进制编码和实数编码 - ![1758202218364](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758202218364.png) - 均匀交叉 (Uniform Crossover) - 每个基因随机选择来自两个亲代中的一个 - 适用于二进制编码和实数编码 - 算术交叉 (Intermediate Crossover / Arithmetic Crossover) - 对实数编码，生成子代为两个亲代的加权平均 $$ \begin{align*} \text{Child}_1 & = \alpha \cdot \text{Parent}_1 + (1 - \alpha) \cdot \text{Parent}_2 \\ \text{Child}_2 & = (1 - \alpha) \cdot \text{Parent}_1 + \alpha \cdot \text{Parent}_2 \end{align*} $$ - $\alpha$ 是一个在 $[0,1]$ 之间的随机数 - $\alpha$ 取 0.5 时即为取平均值 - ![1758202518563](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758202518563.png) - 有序交叉 (Order Crossover, OX) - ![1758202568577](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758202568577.png) - 适用于排列编码 - 从一个亲本中选择一部分排列，复制到它的第一个子代中 - 把剩余的元素按照另一个亲本的顺序排序 - 从已有排列之后开始填充剩余的数字，遇到染色体尾时回绕 - 交换两个亲本角色，产生第二个子代 #### 如何选择作为亲代的个体 更优秀的个体有更高的概率被选择作为亲代，但是弱小的个体也应该有一定的概率被选择，因为他们可能会产生更优秀的后代。 ##### 比例选择 (Proportional Selection) 使用[比例选择](#选择操作决定哪些个体可以进入交配池)的情况，用 $N$ 表示交配池的容量 $\mathrm{Pop\_Size}$，有这样的公式： $$ \frac{f_i}{\sum_{j=1}^{N} f_j} \cdot N = \frac{f_i \cdot N}{\sum_{j=1}^{N} f_j} = \frac{f_i}{\overline{f}} $$ - $f_i$ 指的是个体 $i$ 的适应度 - $\overline{f} = \frac{\sum_{j=1}^{N} f_j}{N}$ 是种群的平均适应度 - $N$ 是交配池的容量 $\mathrm{Pop\_Size}$ 使用比例选择可能会引入一些问题 - **过早收敛 (Premature Convergence)** - 如果某个个体的适应度远高于其他个体，它可能会主导种群，导致多样性降低 - 在适应度相近时，选择压力较小，可能导致收敛速度变慢 为了解决这些问题，可以选择对适应度函数进行一些调整，但是仍要满足适应函数的要求：调整前后不会造成个体之间的相对顺序变化，同时，调整后的适应度值都为正数。一个典型的方法是使用线性映射 $f_{\mathrm{new}} = a \cdot f_{\mathrm{old}} + b$，其中 $a$ 和 $b$ 是常数。因为适应度一般只在意相对大小而不是绝对大小，此处的系数 $a$ 一般不会调整，保持为 $1$。 $$ f_{\mathrm{new}} = f_{\mathrm{old}} + b $$ 这样调整后就可以解决上述提到的问题： - 出现一个个体的适应度远胜于其他个体时，取合适的 $b (b>0)$，可以增大其他个体的适应度，减小选择压力 - 出现所有个体的适应度都很接近时，取合适的 $b (b<0)$，可以增大选择压力，增大不同个体之间的相对差异 ##### 基于排名的选择 (Rank-Based Selection) 首先先计算出每个个体的适应度，根据适应度对每个个体进行排序，分配一个排名 (Rank)，然后根据排名来决定个体被选择的概率。本质上也是一个对适应度函数的映射。 ![1758285861476](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758285861476.png) 根据排名得到新的适应度值 $f_{\mathrm{new}}$ 后使用比例选择进行后续操作。 ##### 锦标赛选择 (Tournament Selection) 随机选择 $k$ 个个体，选出其中适应度最高的个体作为亲代。$k$ 是一个预先设定的参数，称为锦标赛大小 (Tournament Size)。增大 $k$ 会增加选择压力，减小 $k$ 会增加种群的多样性。 ![1758285904346](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758285904346.png) #### 怎么用新的种群替代原本的种群 - 完全替代 (Full Replacement) - 用新生成的种群完全替代原本的种群 - 简单易行，但可能会丢失一些优秀的个体 - 部分替代 (Partial Replacement) - 幼崽和父母一起竞争进入下一代，更优秀的个体保留 #### 选择什么样的停止条件 - 获得问题的最优解 - 根据 CPU 资源决定 - 最大迭代次数 - 根据用户耐心决定 - 达到预期的适应度水平 - 若干代内最优解没有变化 --- - **Exploration** vs. **Exploitation** - Exploration：探索，寻找新的解空间 - 更多的探索会带来更多的多样性 - 不容易收敛 - 交叉主要起探索的作用 - Exploitation：利用，优化当前的解 - 更多的利用可能会陷入局部最优解 - 选择主要起利用的作用 - 需要在两者之间找到平衡 ### 在 MATLAB 中使用遗传算法 #### 性能测试 在正式使用一个算法解决问题之前，常常需要通过性能测试 (benchmark) 来评估一个算法的性能。为了评估算法的性能，我们会通常会使用已知答案的测试函数进行测试 - 测试函数包括许多不同特点 - 如可以是单模型、多模型、多变量等 - 用于评估算法在不同情况下的表现 - 已知测试函数的全局最优解 - 可以验证算法是否能够找到全局最优解 - 通常易于计算 - 便于快速评估算法的性能 - 有在已知的算法下的表现 - 可以与其他算法进行比较 通过性能测试，我们可以评估算法的收敛速度、稳定性和鲁棒性等性能指标，帮助我们选择合适的算法来解决实际问题。 一个常见的测试函数是 `Rastrigin` 函数: $$ f(x) = 10d + \sum_{i=1}^d (x_i^2 - 10\cos(2\pi x_i)),\quad x \in \R^d $$ ![1758286788721](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758286788721.png) 这个函数的特点是有多个局部最优解，但只有一个全局最优解，适合用来测试优化算法的性能。其全局最优解为 $f([0,...,0]) = 0$。 ![1758287010764](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287010764.png) 在只限定维度是 2 的情况下，得到的解和全局的最优解有一定距离。 ![1758287047103](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287047103.png) ![1758287122015](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287122015.png) 给每个维度添加了取值范围 $[-5,5]$ 的限制后，得到的解接近于全局最优解。 ![1758287197578](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287197578.png) 这里设置了 `intcon` 参数为 `[1]`，表示第一个维度是整数类型。得到的解满足约束，且在全局最优解附近。 ![1758287287794](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287287794.png) 在获得局部最优解的变量取值时可以同时获得目标函数值。 #### 偶极天线问题 ![1758287366055](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287366055.png) 需要设计一个偶极天线，它的幅度 $S_{11}$ 在 1.8 GHz 到 2.2 GHz 之间小于 -10 dB。天线长度 $l$ 在 60 mm 到 80 mm 之间，天线半径 $r$ 在 0.1 mm 到 0.5 mm 之间。用数学形式写出来即： $$ \min \sum_{i=1}^K||S_{11}(x, f_i)|_{\mathrm{dB}}+10|^* \\ \quad f_i \in [1.8, 2.2] \mathrm{GHz}, i=1,2,...,K \\ s.t. \begin{cases} x = [l, r] \\ l \in [60, 80] \mathrm{mm} \\ r \in [0.1, 0.5] \mathrm{mm} \\ |...|^* \text{表示计数大于0的个数} \end{cases} $$ 转换成 matlab 代码 ![1758287770859](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287770859.png) ![1758287798373](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287798373.png) 经过 GA 算法优化后得到结果 ![1758287816940](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture3.assets/1758287816940.png) 于是，得到了 $l = 0.0725 \mathrm{m}, r = 0.0005 \mathrm{m}$ 的天线设计方案。在这个方案下，采样范围内一共有 $0$ 个频率点的 $S_{11}$ 大于 -10 dB。 ## Lec.4 约束和多目标优化 Source: https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture4.html Repository path: lectures/Part.1/lecture4.md ### 约束优化 (Constrained Optimization) 这里以一个优化问题为例子： $$ \begin{aligned} \min\quad & f(x) = (x-1)^2 - 1 \\ \mathrm{s.t.}\quad & g(x) = x - 1.5 \ge 0 \end{aligned} $$ ![1758289362411](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758289362411.png) 这就是一个典型的约束优化问题，其中 $f(x)$ 是目标函数，$g(x) \ge 0$ 是约束条件。很明显，此处的约束条件和目标函数有着不同的作用 - **目标函数** - 用来衡量解的优劣 - 目标是最小化 (或最大化) 目标函数的值 - **约束条件** - 用来限制解的范围 - 只关心解是否满足约束条件，可行 (feasible) 或不可行 - 可行的解被认为是一样的 - 不可行的解被认为有不同的优劣 由此，一个很明显的问题就出来了：在有约束的情况下，要选择哪个解？————也就是如何比较不同解之间的优劣关系。一般有这么样的原则： - **可行优于不可行** - 所有可行解都比任何不可行解要好 - 可行解之间，比较目标函数 - 目标函数值更小的解更好（如果是最小化问题） - 不可行解直接，比较违反的约束 - 违反约束更少的解更好 这个标准下，我们就需要对 “违反约束的程度” 进行量化以便于比较，但是不同约束之间的程度可能不能直接比较，同时不同约束可能有不同的优先度————有的约束比其他的更重要。为了解决这个问题，可以用 **加权和** 的方式计算总的违反程度。 $$ \begin{aligned} \min \quad & f(x) \\ \mathrm{s.t.}\quad & g(x) \le c \end{aligned} $$ 这是原本的约束优化问题，它被转换成了下面的形式 $$ \begin{aligned} \min \quad & f(x) + k\cdot h(g(x), c) \\ \mathrm{where}\quad & h(g(x), c) = \max \{0, g(x) -c\} \end{aligned} $$ 其中，$k$ 是惩罚系数 (penalty coefficient)，是一个标量，用于控制违反约束时乘法的强度。 $h(g(x), c)$ 是乘法函数，其量化了违反约束的程度。一个解越违反约束，$h(g(x), c)$ 的值就越大，从而使得目标函数的值增大，降低该解被选择的概率。 一种执行上述方法的经验过程是 1. 选择一个可以接受的违规程度 $\epsilon$ 2. 设计一个最优函数值 $\tilde{f}$，这个值预期可以得到，但不一定是最优值 3. 设计一个惩罚系数 $k$，使得 $k \cdot \epsilon$ 大约是 50 倍的 $\tilde{f}$ $$ k \cdot\epsilon = 50 \tilde{f} \Rightarrow k = \frac{50\tilde{f}}{\epsilon} $$ 对于我们最开始提到的问题，使用类似的方法： ![1758290655930](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758290655930.png) 可以看到，违反了约束的解会被惩罚，进而旧的不符合约束的最优解 $x=1$ 不再是最优解。 --- 如果一个约束优化问题有多个约束，应该怎么做？ $$ \begin{aligned} \min \quad & f(x) \\ \mathrm{s.t.}\quad & \begin{cases} g_1(x) \ge c_1 \\ g_2(x) \le c_2 \\ g_3(x) \le c_3 \\ ... \end{cases} \end{aligned} $$ 首先，先把所有的约束化成相同的形式，也就是一个小于等于符号连接的不等式： $$ \begin{aligned} \min \quad & f(x) \\ \mathrm{s.t.}\quad & \begin{cases} -g_1(x) \le -c_1 \\ g_2(x) \le c_2 \\ g_3(x) \le c_3 \\ ... \end{cases} \end{aligned} $$ 之后，把所有的约束按照单约束情况下的方法独立处理————也就是每个约束都有一个自己的惩罚系数 $k_i$ $$ \begin{aligned} \min \ f(x) & + k_1 h(-g_1(x), -c_1) \\ & + k_2 h(g_2(x), c_2) \\ & + k_3 h(g_3(x), c_3) \\ & + \dots \end{aligned} \\ $$ 之后，按照类似的方式 $k_i = \frac{50 \tilde{f}}{\epsilon_i}$ 计算出每个惩罚系数 $k_i$ 的值，其中 $\epsilon_i$ 是每个约束可以接受的违规程度。 --- 如果求解的问题是最大化问题而不是最小化问题呢？ 很明显 $\max f(x)$ 等价于 $\min -f(x)$，所以可以把最大化问题转换成最小化问题来处理。之后的操作就跟之前提到的是一样的了。 --- 在进行这样的转换之后，原本的约束优化问题被转换成了无约束优化问题，并且每个解都可以被比较，符合之前提到的原则： - 可行优于不可行 - 可行解之间，比较目标函数 - 不可行解之间，比较违反的约束 ### 背包问题 (Knapsack Problem) 背包问题是一个经典的约束优化问题。假设有一个背包，它有一个容量限制 $C$，并且有 $n$ 个物品，每个物品有一个重量 $w_i$ 和一个价值 $v_i$。目标是选择一些物品放入背包，使得总重量不超过容量限制，并且总价值最大化。 ![1758444409969](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758444409969.png) 按照之前提到的方式，我们可以把这个问题表示为一个约束优化问题： 1. 首先，把这个最大化问题改成最小化问题 ![1758444487663](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758444487663.png) 2. 然后把每个约束改成相同的小于等于的形式 ![1758444499609](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758444499609.png) 3. 之后，把每个约束独立处理，乘上惩罚系数，加到目标函数上 ![1758444548510](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758444548510.png) ![1758444569552](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758444569552.png) 4. 之后对这个无约束优化问题进行求解 ```matlab function fitness = knapsack_pfm(values, weights, maxWeight, w_penalty, volumes, maxVolume, v_penalty, population) % fitness evaluator for the knapsack problem, where the constraints are processed by the penalty function method fitness = -values*population.'; % convert the problem to minimization w_const= weights*population.'; % compute the weight constraint v_const= volumes*population.'; % compute the volume constraint fitness = fitness + w_penalty* max(maxWeight-w_const, 0); fitness = fitness + v_penalty* max(maxVolume-v_const, 0); end ``` ### 多目标优化 (Multi-objective Optimization) 多目标优化是指在一个优化问题中，有多个目标函数需要同时优化。 $$ \begin{aligned} \min\quad & f_1(x_1, x_2, ..., x_n) \\ \min\quad & f_2(x_1, x_2, ..., x_n) \\ & ... \\ \min\quad & f_m(x_1, x_2, ..., x_n) \\ \mathrm{s.t.}\quad & x = (x_1, x_2, ..., x_n)^T \in D \subseteq R^n \end{aligned} $$ - $x$ 是决策变量 (decision variable) - $D$ 是决策空间 (decision space) - $f_i(x)$ 是第 $i$ 个目标函数 - $n$ 是决策变量的维度 - 目标函数也可能是包含 $\max$ 的最大化问题 通常，这些目标函数之间可能存在冲突，也就是说，优化一个目标函数可能会导致另一个目标函数的性能下降。我们需要找到一个平衡点，使得所有目标函数都能得到较好的优化。 这种情况下，不同的解很难相互比较。我们先定义可以比较的情况： **优势 (Dominance)**: 对于两个解 $x$ 和 $y$，如果 $x$ 在所有目标函数上都不比 $y$ 差，并且在至少一个目标函数上比 $y$ 好，那么我们说 $x$ 优势于 $y$ 那么，对于任意两个解 $x$ 和 $y$，可能存在三种情况： - $x$ 优势于 $y$ - $y$ 优势于 $x$ - $x$ 和 $y$ 无法比较 > Dominance 除了优势的说法，还有支配的说法，在[最开始](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture2.html#多目标优化)提到过，当时说的就是支配。 根据这样的不完全可比性，我们可以定义 **帕累托最优 (Pareto Optimality)**: **帕累托最优 (Pareto Optimality)**: 无法被任何其他解优势的解被称为帕累托最优解 (Pareto Optimal Solution)，它们组成的集合叫做帕累托集 (Pareto Set)。所有帕累托最优解的目标函数值组成的集合称为帕累托前沿 (Pareto Front)。 ![1758445414489](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758445414489.png) 帕累托前沿可能有不同的形状或者有不同的分布： ![1758445438549](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758445438549.png) 求解多目标优化问题的目标是找到帕累托前沿上的解。而最终优化的结果是一个解的集合，而不是单一的解。 ### MOEA 算法 (Multi-objective Evolutionary Algorithm) MOEA 是一种用于求解多目标优化问题的进化算法。它通过模拟自然选择和遗传变异的过程，逐步改进解的质量，最终得到一组近似的帕累托最优解。 #### MOEA 算法的基本流程 ![1758445984888](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758445984888.png) 这是一个在 [Lec.3](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html) 中提到的基本进化算法的过程，包含种群、选择、交叉、变异等。对于 MOEA 算法， 它生成一系列的解去估计帕累托前沿，为决策者提供一些其他有用的信息，比如不同目标如何相互妥协。这是一种在多标准决策分析 (Multi-Criteria Decision Analysis, MCDA) 中常用的方法。 经过 MOEA 算法后，我们希望得到有限个等距排列的位于帕累托前沿上的解，进而可以根据这些解描绘出帕累托前沿的形状。 ![1758446343138](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758446343138.png) 得到的解集也可以获得更多样的信息 ![1758447025125](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758447025125.png) 根据这张图，我们可以知道： - 目标函数 $f_1$ 比 $f_2$ 更容易优化 - 在蓝色箭头附近可能不存在帕累托最优解 - 绿色的解 $x^*$ 可能是一个“关键 (key)”解，因为它在两个目标函数上都有较好的性能 #### 常见的 MOEA 算法 - **MOEA/D**: Decomposition-based MOEA - 将多目标优化问题分解为多个单目标优化子问题 - 通过求解这些子问题来近似帕累托前沿 - **NSGA-II**: Dominance-based MOEA - 基于支配关系进行选择 - 使用非支配排序和拥挤距离来维护种群的多样性 - **IBEA**: Indicator-based MOEA - 基于对性能指标的贡献来选择 - 通过指标来评估解的质量 #### MOEA/D 算法 对于 MOEA/D ，它在种群数量较小的情况下可以得到更好的分布以及更高的优化质量。分解的思想让它有了更加均匀的分布，最终在较小的种群数量下得到了比 **NSGA-II** 更好的结果。 ![1758447525522](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758447525522.png) 这一结果是由于 MOEA/D 的两个核心思想： - 分解 (Decomposition) - 从传统优化算法中借鉴 - 将多目标优化问题分解为多个子问题 - 每个子问题通常是单目标优化问题 - 合作 (Collaboration) - 从进化算法中借鉴 - 使用了多个智能体，每个智能体负责求解一个子问题 - 这些 N 个子问题是相互关联的，N 个智能体可以以协作的方式解决这些子问题 要进行 MOEA/D 算法，首先要把多目标优化问题分解成多个子问题，而一个子问题的常见结构是： $$ \begin{aligned} \min\quad & g(x) \\ \mathrm{Inputs:}\ &\begin{cases} 分解问题 g(x) \\ 偏好向量 \lambda \\ 可能的参照点 z^* \\ 搜索空间 D \\ 目前最好的解 x^* \\ \end{cases} \end{aligned} $$ 对于分解，常用的有两种方法： - **加权和 (Weighted Sum)**: 通过给每个目标函数分配一个权重，将多个目标函数合并成一个单一的目标函数 - **Tchebycheff 方法**: 通过最小化目标函数与一个理想点之间的最大距离来处理多个目标函数 ##### 加权和 以加权和为例。比如，原本有两个目标函数 $f_1(x)$ 和 $f_2(x)$，我们可以把它们分解成一个加权和的形式： $$ \begin{aligned} g(x) = &\lambda_1 f_1(x) + \lambda_2 f_2(x) = \lambda \cdot F(x) \\ \mathrm{s.t.}\quad & \lambda_1 + \lambda_2 = 1,\\ & \lambda_1, \lambda_2 \ge 0 \end{aligned} $$ 这样，一个子问题就变成了一个单目标优化问题，可以使用之前提到的进化算法来求解。 使用不同的权重，可以得到不同的子问题，从而覆盖整个帕累托前沿。 ![1758453265716](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758453265716.png) ![1758453274202](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758453274202.png) 使用加权和时，可以发现 $g(x)$ 的值对应着 $f_1(x)$ 和 $f_2(x)$ 的线性组合，其在二维上是一条直线，找到的最优解对应着这条直线与帕累托前沿的切点。不同的权重对应着不同的直线斜率，从而找到不同的最优解。 ![1758457001275](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457001275.png) ##### 切比雪夫方法 切比雪夫法 (Tchebycheff Method) 也是一种常用的分解方法。它通过最小化目标函数与一个理想点之间的最大距离来处理多个目标函数。 ![1766735529898](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1766735529898.png) 切比雪夫法的原理是：对于某一个位于帕拉托前沿上的解 $x^*$ ，应该存在一个系数 $\lambda$，使得这个解 $x^*$ 在这个子问题上是最优的。 此时这个多目标优化问题转化为的子问题是这样的： $$ \begin{aligned} \min \quad & g^T (x|\lambda, z^*)\\ \mathrm{where}\quad & g^T (x|\lambda, z^*) = \max \{ \lambda_1 |f_1(x) - z_1^*|, \lambda_2 |f_2(x) - z_2^*| \} \\ & z^* = (z_1^*, z_2^*) \end{aligned} $$ 这里，$g^T (x|\lambda, z^*)$ 是切比雪夫函数，指的是在系数 $\lambda$ 和参照点 $z^*$ 下的目标函数。$z^*$ 是一个理想点 (Utopian Point)，它的每个分量 $z_i^*$ 是第 $i$ 个目标函数的最小值。也就是说，有 $$ \begin{aligned} z_1^* < \min f_1\\ z_2^* < \min f_2 \end{aligned} $$ 用更通俗的话来解释切比雪夫方法的过程，就是先用目前所有的目标函数的最小值来构造一个理想点 $z^*$，给每个目标函数赋予不同的权重大小，组成权重向量 $\lambda$。之后，优化目标就变成了 **最小化每个目标函数距离理想点的距离的最大值**，也就是 $\min(\max(\mathrm{dist}))$ 这样的东西。通过调整权重向量 $\lambda$，可以得到不同的子问题，从而覆盖整个帕累托前沿。 --- **近邻 (Neighborhood)** 定义的是子问题之间的关系。如果两个子问题的权重向量相近，则它们被认为是近邻子问题。近邻子问题大概率有着相似的目标函数和相似的最优解。 ![1758457134751](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457134751.png) 可以在近邻问题之间进行交换来得到更好的解。比如这张图，上面两个染色体是两个子问题的目前的最优解，使用交换产生了新的解，进而可能得到更好的解。 ![1758457187208](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457187208.png) 对于每一代，MOEA/D 算法的主要步骤是： - **选择交配池** - 选择目前问题的最优解和目前问题的近邻问题的最优解作为交配池 - **繁殖 (Reproduction)** - 使用交叉和变异操作生成新的解 - **替换 (Replacement)** - 将旧的解和新的解进行比较，选择更好的解作为新的最优解 - 把新的解给予近邻问题，替换成更好的解 ![1758457411566](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457411566.png) ![1758457652164](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457652164.png) > [!NOTE] > > MATLAB 代码实现见 Moodle 上的附件 > > ![1758457769409](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture4.assets/1758457769409.png) ## Lec.5: Combinatorial Optimization (组合优化) Source: https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture5.html Repository path: lectures/Part.1/lecture5.md ### 定义 组合优化指的是从一个有限的对象集中寻找最优解的问题。通常，这些对象集是离散的，并且问题通常涉及选择、排列或分配这些对象以最大化或最小化某个目标函数。 | | 组合优化 (CO) | 实值优化 (RO) | | ------ | -------------------------------- | ------------- | | 目标 | 离散 | 连续 | | 解空间 | 有限 | 无限 | | 目标 | 在有限集合里寻找最好的组合或排列 | 寻找最好的解 | 常见的组合优化问题包括 - **背包问题 (Knapsack Problem)** - **旅行商问题 (Traveling Salesman Problem)** ### 背包问题 (KP) 背包问题 (Knapsack Problem, KP) 指的是如何在一个给定了承载重量上限的背包中，选择物品以最大化总价值的问题。每个物品都有一个重量和一个价值，目标是选择一组物品，使得它们的总重量不超过背包的承载能力，同时总价值最大。 ![1758091349227](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758091349227.png) 一个表示求解变量的方式是使用二进制编码，即对于 n 个物品，解是一个 n 维的二进制向量，其中每个元素表示对应物品是否被选择（1 表示选择，0 表示不选择）。 这里的情况，一共有 5 个物品可以选择，故使用一个五位的二进制数代表所有的选择情况，每一个二进制位对应一个物品，1 代表选择该物品，0 代表不选择该物品。 #### 修复法 (Repairment Method) 为了方便求解，我们先计算出每个物品对应的单位重量价值，记作 $v2w$ ![1758458696856](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758458696856.png) 然后，我们使用单位重量价值而不是总价值对每个物品进行排序。比如 - 如果我们目前的二进制解是 01011， 总重量是 9 kg， 超过了 7 kg 的限制 - 通过单位重量价值排序，扔掉单位重量价值最低的物品，直到重量不超过限制 这样，在每一次迭代后都能产生新的保证可行的解。 #### 惩罚函数法 (Penalty Function Method) 和 [Lec.4](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture4.html#约束优化-constrained-optimization) 里提到的方法类似，我们把约束条件转化成惩罚项，加入到目标函数中，数学形式如下： $$ \begin{aligned} f_{new}(x) = & f(x) - p \cdot h(x) \\ \mathrm{where}\quad & h(x) = \begin{cases} w(x) - c , \mathrm{if}\ w(x) > c \\ 0, \mathrm{otherwise} \end{cases} \end{aligned} $$ - $f(x)$ 是原始的目标函数（总价值） - $w(x)$ 是当前选择的物品的总重量 - $c$ 是背包的最大承载重量 - $p$ 是一个大的正数，表示惩罚的强度 确定 $p$ 的值的过程和 [Lec.4](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture4.html#约束优化-constrained-optimization) 里提到的方法类似，都是按照 $p=\frac{50 \tilde{f}}{\epsilon}$ 的计算方法计算。 这里 $\tilde{f}$ 是一个对原始目标函数 $f(x)$ 的估计，取 \$10000； $\epsilon$ 是能够容忍的最大违反约束，这里取 1kg，计算出 $p = 500000$。 使用上述方法，我们可以将背包问题转化为一个无约束优化问题，然后使用遗传算法或其他优化方法来求解。使用遗传算法求解得到这个问题的解是 10101，对应的最优目标函数是 \$7k。 ![1758459518560](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758459518560.png) #### 在 MATLAB 中求解背包问题 > [!NOTE] > > 在 MATLAB 中的对应实现在 Moodle 上的附加文件中，此处略过 > > ![1758462846719](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462846719.png) > > ![1758462862673](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462862673.png) > > ![1758462869369](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462869369.png) > > ![1758462875479](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462875479.png) > > ![1758462882914](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462882914.png) > > ![1758462989554](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462989554.png) > > 这里使用了[锦标赛选择 (Tournament Selection)](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html#锦标赛选择-tournament-selection) 方法来选择交配池，在 Lec.3 里有介绍 > > ![1758462979713](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758462979713.png) ### 旅行商问题 (TSP) 旅行商问题 (Traveling Salesman Problem, TSP) 是一个经典的组合优化问题，目标是在给定的一组城市中找到一条最短的巡回路径，使得每个城市恰好访问一次，并且最终返回到起始城市。 根据问题的性质，我们知道每个解应该是给定城市的排列————每个城市出现一次，不同的顺序代表访问城市的顺序。 按照这个编码，我们就像在 [Lec.3](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html#交叉) 里提到的一样，我们不太可能使用普通的单点交叉进行交叉操作————它可能会破坏排列的性质，导致某些城市被访问多次，而其他城市则未被访问。 ![1758463495612](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463495612.png) 所以，这里使用[有序交叉 (Order Crossover, OX)](https://cateds.github.io/AI-MachineLearning.md/Part.1/lecture3.html#交叉)进行对应的交叉操作。 > 标准的 OX1 交叉是把提供顺序的亲本剩下的元素按顺序填充到子代切点之后，这里从第一个开始填充是一种简化版本的有序交叉。 ![1758463546294](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463546294.png) 对于变异，则使用交换变异 (Swap Mutation)，即随机选择两个位置的城市并交换它们的位置。 ![1758463567845](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463567845.png) 接下来就是典型的遗传算法流程了。 ![1758463607085](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463607085.png) #### 在 MATLAB 中求解旅行商问题 > [!NOTE] > > 在 MATLAB 中的对应实现在 Moodle 上的附加文件中，此处略过 > > ![1758463624912](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463624912.png) > > ![1758463686749](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463686749.png) > > ![1758463693367](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463693367.png) > > ![1758463700091](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463700091.png) > > ![1758463705725](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463705725.png) > > ![1758463711826](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463711826.png) > > ![1758463718207](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463718207.png) > > ![1758463725091](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.1/lecture5.assets/1758463725091.png) ## 机器学习 (Machine Learning) Source: https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture7.html Repository path: lectures/Part.2/lecture7.md ### 什么是机器学习 在传统方法下，如果需要实现一个目的，需要准备输入的数据，并且编写一个程序来处理这些数据，从而得到想要的输出结果。 但是在机器学习中，我们不需要编写程序，而是通过准备输入数据和对应的输出结果，让计算机自己去学习如何从输入映射到输出。这就是机器学习的核心思想。 ![1760528853132](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760528853132.png) 对于机器学习，有 3 个主要的类型： - 监督学习 (Supervised Learning) - 给定输入数据和对应的输出结果，让计算机学习如何从输入映射到输出。 - 无监督学习 (Unsupervised Learning) - 只给定输入数据，没有对应的输出结果，让计算机自己去发现数据中的模式和结构。 - 半监督学习 (Semi-Supervised Learning) - 给定部分输入数据和对应的输出结果，让计算机利用这些信息去学习如何从输入映射到输出。 ![1760529036232](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760529036232.png) 这里的输入数据和输出结果指的是训练过程中需要的数据。数据的集合叫数据集(dataset)，数据集中的每一个数据叫样本(sample)。在监督学习中，每一个样本由输入数据和对应的输出结果组成。一个数据集可以表现为 $D = \{ d^1, d^2, \ldots, d^n \}$，其中 $N$ 是样本的数量。 用于训练的数据集被称为训练集 (training dataset)，用于评估模型的数据集被称为测试集 (test dataset)。在机器学习的整个过程中的数据集由这两个部分组成，通常训练集更多，测试集较少。 ![1760529245127](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760529245127.png) 机器学习的结果我们称之为模型 (model)，模型指的是从数据中学习到的特定的映射关系。在经过训练之后，模型可以用于对新的输入数据进行预测，得到对应的输出结果。 数据中可以测量的特征叫做特征 (feature)，特征是用来描述数据的属性。每一个样本可以有多个特征，这些特征可以是数值型的，也可以是类别型的。特征是模型的输入。多个特征可以组成一个特征向量 (feature vector)，写作 $f = (f_1, f_2, \ldots, f_m)$，其中 $m$ 是特征的数量。 数据集中的输出部分叫标签 (label)，标签是用来描述数据的类别或结果。标签可以是离散的，也可以是连续的。标签是模型的输出。一个数据集可能没有标签（无监督学习），也可能有多个标签（多标签学习）。 ### 机器学习的种类 #### 监督学习 监督学习指的是训练过程中使用的数据集包含输入数据和对应的输出结果，即有标签的数据集。对于这种情况，数据集为 $D = \{ d^1, d^2, \ldots, d^N \}$，其中 $d^i = (x^i, y^i)$，$x^i$ 是输入数据，$y^i$ 是对应的输出结果。 训练过程指的是机器学习算法从数据集中学习映射关系的过程。训练的目标是找到一个函数 $f$，使得对于每一个输入数据 $x^i$，函数 $f(x^i)$ 的输出结果尽可能接近对应的输出结果 $y^i$。这个函数 $f$ 就是我们所说的模型。 测试过程指的是使用训练好的模型对新的输入数据进行预测的过程。测试的目标是评估模型在未见过的数据上的表现。对于一个新的输入数据 $x^{new}$，我们使用模型 $f$ 进行预测，得到输出结果 $y^{pred} = f(x^{new})$。 ##### 监督学习：分类 一个典型的监督学习任务是分类 (classification)。分类任务的目标是将输入数据分配到预定义的类别中。分类任务可以是二分类 (binary classification)，也可以是多分类 (multi-class classification)。这种任务的特点是输出结果是离散的类别标签。 ![1760529821958](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760529821958.png) 一个典型的例子是手写数字识别 ![1760530117771](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760530117771.png) ##### 监督学习：回归 回归 (regression) 是另一种典型的监督学习任务。回归任务的目标是预测一个连续的数值输出。回归任务的特点是输出结果是连续的数值。典型的应用是财务预测 #### 半监督学习 半监督学习 (semi-supervised learning) 是介于监督学习和无监督学习之间的一种学习方法。它利用了大量的未标记数据和少量的标记数据来训练模型。半监督学习的目标是通过结合标记数据和未标记数据，提高模型的性能。他的训练过程是： - 使用标记数据进行初步训练，得到一个初始模型。 - 使用初始模型对未标记数据进行预测，得到伪标签。 - 将伪标签与未标记数据结合，形成新的训练集。 - 使用新的训练集进行进一步训练，优化模型。 ![1760530292773](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760530292773.png) #### 无监督学习 无监督学习 (unsupervised learning) 指的是训练过程中使用的数据集不包含输入数据的对应输出结果，即没有标签的数据集。对于这种情况，数据集为 $D = \{ d^1, d^2, \ldots, d^N \}$，其中 $d^i = x^i$，只有输入数据，没有对应的输出结果。通常，无监督学习更加困难，因为没有明确的目标来指导学习过程。 ![1760530378232](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760530378232.png) ### 机器学习的过程 机器学习的过程通常有以下几个步骤： - 数据表示：将原始数据转换为适合机器学习算法处理的形式。 - 选择模型：选择适合任务的机器学习算法和模型结构。 - 训练模型：使用训练集对模型进行训练，调整模型参数。 - 评估模型：使用测试集对模型进行评估，计算模型的性能。 ![1760530992108](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760530992108.png) #### 数据表示 数据表示 (data representation) 是机器学习中的一个重要概念。数据表示指的是如何将原始数据转换为适合机器学习算法处理的形式。良好的数据表示可以提高模型的性能和泛化能力。这个表示的过程叫做数据编码 (data encoding)，数据编码的目标是将原始数据转换为数值形式，以便机器学习算法能够处理。 在机器学习中数据有多种形式： ##### 数值数据 (Numerical Data) 数值数据是最常见的数据形式，通常表示为实数或整数。数值数据可以直接用于机器学习算法。可以直接进行算术运算。 - 连续数据 (Continuous Data) - 连续数据是可以取任意值的数据，例如温度、身高、体重等。 - 离散数据 (Discrete Data) - 离散数据是只能取特定值的数据，例如人数、物品数量 ##### 类别数据 (Categorical Data) 表示为名称或者标签的数据，通常表示为字符串或者整数。类别数据不能直接进行算术运算，需要进行编码处理。 - 二进制数据 (Binary Data) - 二进制数据是只有两个可能取值的数据，例如性别（男/女）、是否（是/否）等。 - 名义数据 (Nominal Data) - 名义数据是没有顺序关系的类别数据，例如颜色（红、绿、蓝）、城市（北京、上海、广州）等。 - 有序数据 (Ordinal Data) - 有序数据是有顺序关系的类别数据，例如评级（好、中、差）、教育水平（小学、初中、高中、大学）等。 - 通常会按照顺序进行编码，例如小学=0，初中=1，高中=2，大学=3。编码通常从 0 开始。 - 独热编码 (One-Hot Encoding) - 将每个类别表示为一个独立的二进制特征。例如，颜色有红、绿、蓝三种类别，可以表示为三个二进制特征：红=(1,0,0)，绿=(0,1,0)，蓝=(0,0,1)。 - 这种编码的特点是只有一个特征为 1，其他特征为 0。 - 或者写作 $v = (v_1, v_2, \ldots, v_k)$，其中 $k$ 是类别的数量，并且有对于第 $d$ 个 $v_d = 1$，$v_j = 0$ 对于 $j \neq d$。 - 虚拟变量编码 (Dummy Encoding) - 类似于单热编码，但是少一个特征。例如，颜色有红、绿、蓝三种类别，可以表示为两个二进制特征：红=(1,0)，绿=(0,1)，蓝=(0,0)。 - 这种编码的特点是可以节省一个特征，但是需要注意解释模型的结果时需要考虑缺失的类别。 ![1760531328848](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760531328848.png) ![1760531602122](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760531602122.png) #### 模型选择 ##### 参数化模型 参数化模型 (Parametric Model) 把模型简化成了一只形式的函数，这种函数定义了输入和输出之类的关系，比如线性回归、逻辑回归、神经网络等。 - 优点 - 易于解释训练结果 - 通常学习速度很快 - 只需要少量的数据 - 缺点 - 形式被给定的函数所限制 - 更适合简单问题 - 可能现有问题无法匹配底层映射函数 ###### 线性回归 线性回归 (Linear Regression) 是一种用于回归任务的参数化模型。线性回归假设输入特征和输出结果之间存在线性关系。线性回归的目标是找到一组参数，使得对于每一个输入特征向量 $x^i$，线性函数 $f(x^i) = a x^i + b$ 的输出结果尽可能接近对应的输出结果 $y^i$。其中，$a$ 是权重向量，$b$ 是偏置项。 线性回归是一个从数值输入到数值输出的映射函数，适用于回归任务。比如财务预测。 - 优点 - 在线性可分的情况下表现良好 - 更易于实现，训练效率高 - 缺点 - 只适用于线性可分的问题 - 对异常值敏感 ##### 非参数化模型 非参数化模型没有固定的函数形式，不对模型的形态进行强假设，而是通过数据来定义模型的结构，比如决策树、支持向量机、K 近邻 (KNN)等。 - 优点 - 更加灵活，可以适应复杂的模式 - 可能有更高的性能 - 缺点 - 在训练时通常需要更多数据和训练时间 ###### K 近邻 (KNN) KNN 是一种用于分类和回归任务的非参数化模型。KNN 假设相似的输入特征对应相似的输出结果。KNN 的目标是通过计算输入特征向量 $x^{new}$ 与训练集中所有输入特征向量 $x^i$ 之间的距离，找到距离最近的 $k$ 个邻居，然后根据这些邻居的输出结果来预测新的输出结果 $y^{pred}$。 KNN 的特征是 - 惰性学习 (Lazy Learning) - KNN 在训练过程中不进行显式的学习，而是将训练数据存储起来，直到需要进行预测时才进行计算。 - 非参数化 (Non-Parametric) - KNN 不对数据的分布做任何假设，而是通过数据本身来定义模型的结构。 常用的应用场景有手写识别、人脸识别、文本分类等。 KNN 的过程是 - 选择 $K$ 的值 - 计算每个训练样本与新样本之间的距离 - 选择距离最近的 $K$ 个样本 - 通常使用欧几里德距离进行计算， $d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$ - 根据邻居中最多的类别进行投票，确定新样本的类别 其中， $K$ 是一个超参数 (hyperparameter)，意思是在训练过程中需要手动设置的参数，而不是通过训练数据学习到的参数。选择合适的 $K$ 值对于 KNN 的性能有很大的影响。通常，较小的 $K$ 值会导致模型对噪声敏感，而较大的 $K$ 值会导致模型过于平滑，无法捕捉数据的细节。选择 $K$ 的大小有一些经验法则 1. K 不应该太小也不应该太大 - 太小会导致模型对噪声敏感 - 太大则会导致模型过于平滑 2. K 通常选择为奇数，避免投票时出现平局 3. 在决定 K 值时可以参考领域知识 4. 通常，把 K 设置为 $\sqrt{N}$，其中 $N$ 是训练样本的数量 ![1760532915528](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760532915528.png) #### 模型评估 预测 (Prediction) 是机器学习中的一个重要概念。预测指的是使用训练好的模型对新的输入数据进行预测，得到对应的输出结果。预测的目标是评估模型在未见过的数据上的表现。预测的表现是通过预测误差 (Prediction Error)来评判的，其指的是预测结果与真实结果之间的差异。 ![1760533005109](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture7.assets/1760533005109.png) ### 使用 Python 和 MATLAB 的机器学习 > 包含使用 MATLAB 哈 Python 的机器学习的例子，见代码文件夹和原 PPT ## 机器学习及数据预处理 Source: https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture8.html Repository path: lectures/Part.2/lecture8.md ### 模型的训练 ![1760596818837](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760596818837.png) 根据上节课的内容，我们知道了模型训练的过程。具体而言，模型训练指的是通过优化算法 (Optimization Algorithm) 来调整模型的参数，使得模型在训练数据上的预测结果尽可能接近真实结果。模型的参数分为两种： - 超参数 (Hyperparameter)：在训练之前设置的参数 - 比如 KNN 中的 K 值 - 模型参数 (Model Parameter)：通过训练数据学习得到的参数 - 比如线性回归中的权重和偏置 #### 损失函数 通常我们使用损失函数来衡量模型的预测结果与真实结果之间的差距。损失函数计算出来的值叫做损失 (loss)。有很多种损失函数的形式 - 均方误差 (Mean Squared Error, MSE)：用于回归任务，计算预测值与真实值之间的平方差的平均值。 - $\mathrm{MSE} = \frac{1}{N} \sum_{i=1}^{N} (y_i - \hat{y}_i)^2$ - MSE 总是凸函数并且可微，因此易于优化 - 对异常值敏感，因为平方项会放大较大的误差 - 均绝对误差 (Mean Absolute Error, MAE)：用于回归任务，计算预测值与真实值之间的绝对差的平均值。 - $\mathrm{MAE} = \frac{1}{N} \sum_{i=1}^N | y_i - \hat{y}_i |$ - MAE 对异常值更不敏感，因为它使用绝对值而不是平方 - MAE 在某些点不可微，可能会导致优化困难 - 交叉熵损失 (Cross-Entropy Loss)：用于分类任务，衡量预测的概率分布与真实类别之间的差异。 - 二进制交叉熵 (Binary Cross Entropy) - $l = -\frac{1}{N}\sum_{i=1}^N (y_i\log\hat{y}_i + (1 - y_i)\log(1 - \hat{y}_i))$ - 适用于二分类任务 - 多类交叉熵 (Categorical Cross Entropy) - $l = -\sum_{i=1}^N \sum_{j=1}^K y_{i,j} \log(\hat{y}_{i,j})$ - 可微，因此易于优化 - 有多个局部极值，可能会导致优化困难 在模型训练的过程中，首先需要选择使用哪种损失函数，之后在训练过程中最小化损失函数的值，最终得到一套最优的模型参数。比如，对于线性模型 $y=ax+b$ ， $l(a,b) = \frac{1}{N}\sum\_{j=1}^N(y_j - ax_j - b)^2$ ，训练的目标则是选择合适的参数得到 $\min l(a,b)$ 。 可以发现此时 $l(a,b)$ 是一个连续、可微的凸函数，因此可以使用梯度下降法 (Gradient Descent) 来进行优化。 #### 梯度下降 梯度下降法是一种通过一阶导数和迭代法来寻找函数的局部最小值的办法。它的迭代方程是 $$ x_{k+1} = x_k - a_k \nabla f(x_k) $$ 其中， $x_k$ 是第 $k$ 次迭代的参数， $a_k$ 是学习率 (Learning Rate)， $\nabla f(x_k)$ 是函数 $f$ 在 $x_k$ 处的梯度。 使用梯度下降法来优化时，通常会先确定一个初始点 $x_0$ ，然后计算该点的梯度 $\nabla f(x_0)$ ，接着根据学习率 $a_0$ 来更新参数，得到新的参数 $x_1$ 。重复这个过程，直到满足停止条件，比如达到最大迭代次数或者梯度足够小。 ![1760597997173](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760597997173.png) 在梯度下降算法中，我们需要计算梯度。有这么几种方式： - Batch Gradient Descent (BGD) - 每次使用所有训练数据来计算梯度，然后通过均值来更新参数 - 优点：梯度计算准确，收敛稳定 - 缺点：计算量大，内存消耗高 - Stochastic Gradient Descent (SGD) - 每次随机选择一个训练样本来计算梯度，然后更新参数 - 优点：计算量小，内存消耗低 - 缺点：梯度计算不准确，收敛不稳定，更多次的模型更新和更多的计算量 - Mini-Batch Gradient Descent - 每次随机选择一小批训练样本来计算梯度，然后更新参数 - 优点：在计算效率和梯度准确性之间取得平衡 - 缺点：需要选择合适的批量大小 - 这也是一个超参数，更小的值会类似 SGD，更大的值会类似 BGD - 通常选择 32 ### 模型的测试 在上节课提到，模型使用训练集进行训练，使用测试集进行测试。测试集是从原始数据集中划分出来的一部分数据。在测试集中，预测的值和实际的值之间的误差叫预测误差 (Prediction Error)。 $$ \mathrm{Err} = \mathrm{Bias}^2 + \mathrm{Var} + \mathrel{Noise} $$ - Bias：偏差，指的是模型预测值的期望与真实值之间的差异。 - 偏差反映了模型对训练数据的拟合程度。高偏差通常意味着模型过于简单，无法捕捉数据的复杂模式，导致欠拟合 (Underfitting)。 - 其与模型自身和训练过程都有关。 - Var：方差，指的是模型预测值的变化程度。 - 方差反映了模型对训练数据的敏感程度。 - 高方差通常意味着模型过于复杂，容易受到训练数据中噪声的影响，导致过拟合 (Overfitting)。 - 其主要和训练过程有关。 - Noise：噪声，指的是数据中不可预测的随机误差。 - 噪声是数据本身固有的，无法通过模型来消除。 > 英国知名主播 Vedal 解释什么是过拟合.mp4 : > > #### 偏差 (Bias) 高偏差的模型会导致在训练集和测试集中都会出现的高预测误差。这会导致模型对训练数据有很强的假设，以及欠拟合。 欠拟合指的是模型既不能很好地拟合训练数据，也不能很好地泛化到测试数据。 ![1760598686765](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760598686765.png) ![1760598697225](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760598697225.png) ![1760599465582](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599465582.png) 其典型特征是在训练集和测试集上市都有很差的表现，可以通过更换机器学习算法，以及提高训练时间来改善。 #### 方差 (Variance) 方差指的是使用不同的训练数据，最终得到的模型预测结果的变化的量。高方差的模型会在测试集上出现很高的误差，通常是算法对于噪声过于敏感导致的，从而导致过拟合。过拟合指的是模型能够很好地拟合训练数据，但不能很好地泛化到测试数据。 ![1760598867652](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760598867652.png) ![1760599487202](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599487202.png) 其典型特征是预测误差在训练集和测试集上差异很大，在训练集上表现更好。可以通过增加训练数据，减少不相关的特征以及提前停止训练来改善。 #### 估计方差和偏差 K 折交叉验证 (K-Fold Cross Validation) 是一种用于评估机器学习模型性能的技术。其过程是将数据集划分为 K 个子集，然后进行 K 次训练和测试。在每次迭代中，选择一个子集作为测试集，剩余的 K-1 个子集作为训练集。最终的模型性能是 K 次测试结果的平均值。 ![1760599213659](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599213659.png) 在 K 折交叉验证后，可以得到 k 个不同的预测误差 $e_1, e_2, \ldots, e_k$ ，得到 $\overline{e} = \frac{1}{k}\sum_{i=1}^k e_i$ ，以及标准差 $\sigma = \sqrt{\frac{1}{k}\sum_{i=1}^k(e_i - \overline{e})^2}$ 。得到的数据就是模型的偏差和方差的估计。 通常，偏差和方差是互相制约的。降低偏差通常会增加方差，反之亦然。这种权衡被称为偏差-方差权衡 (Bias-Variance Tradeoff)。在模型选择和调优过程中，需要在偏差和方差之间找到一个平衡点，以获得最佳的模型性能。 ![1760599411788](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599411788.png) #### 泛化 (Generalization) 泛化指的是模型将从训练集中学习到的内容应用到没有被学习过的数据上的能力。一个好的模型应该能够很好地泛化到新的数据，而不是仅仅记住训练数据。 ![1760599671454](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599671454.png) ### 数据预处理 ![1760599812051](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1760599812051.png) 数据准备指的是没有结构的数据被转换成可以被机器学习算法使用的结构化数据的过程。数据准备通常包括 - 数据清理 (Data Cleaning) - 处理缺失值 - 处理异常值 - 处理重复数据 - 处理不一致的数据 作用： - 提高数据质量 - 移除噪声、不一致性、错误 - 提高模型性能 - 让模型更快的收敛，更准确 - 处理缺失数据 - 使用插值或者删除防止模型产生偏差 - 减少过拟合 - 特征选择和降维可以减小模型的复杂度 - 编码类别数据 - 将类别数据转换为数值数据，便于模型处理 - 平衡类别分布 - 解决不平衡数据集问题，防止模型偏向多数类 - 确认数据一致性 - 对特征进行标准化，便于统一处理 - 节约计算资源 - 预处理后的数据减少了计算量，提高效率 #### 缺失值处理 缺失值有三种 - 完全随机缺失 (Missing Completely at Random, MCAR) - 缺失值的出现与数据的其他特征无关 - 例子：问卷调查中，某些受访者随机跳过某些问题 - 判断方式：Little's MCAR Test (使用统计检验来判断数据是否符合 MCAR 假设) - 条件随机缺失 (Missing at Random, MAR) - 缺失值的出现与数据的其他特征有关，但与缺失值本身无关 - 例子：在医疗数据中，某些患者的某些检查结果缺失，这可能与患者的年龄或性别有关 - 判断方式：使用逻辑回归来预测缺失值的出现 - 非随机缺失 (Missing Not at Random, MNAR) - 缺失值的出现与缺失值本身有关 - 例子：在收入调查中，收入较高的人可能更倾向于不报告他们的收入 - 判断方式：通过领域知识和数据分析来识别 通常有两种处理方法： - 数据移除 - 当数据样本缺少某个数据时，删除样本 - 损失值比例须小于 5% - 易于操作，但是可能会对 MAR 和 MNAR 的缺失引入偏差 - 值估计 - 当数据样本缺少某个数据时，用估计值填充 - 填充方法有：使用统计数据估计（如均值/中位数/众数），或者使用机器学习模型预测（如 KNN） - 可以充分利用数据，但是可能会产生错误的数据 #### 极端值处理 极端值指的是在数据集中显著偏离其他数据点的值。通常，极端值的检测可以分为两种方法： - 使用 Z 得分 (Z-Score) - 使用于高斯分布和近似高斯分布的数据 - 使用 四分位距 (Interquartile Range, IQR) - 使用于高斯和非高斯分布的数据 高斯分布指的就是正态分布 (Normal Distribution)。它的概率分布的特征是数据接近其均值，且数据在均值两侧对称分布。它的概率密度函数 (Probability Density Function, PDF) 是 $$ f(x) = \frac{1}{\sigma \sqrt{2\pi}} \exp(-\frac{(x - \mu)^2}{2\sigma^2}) $$ ![1765439075321](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765439075321.png) 数据偏度 (Data Skewness) 指的是数据分布的非对称性。正偏态 (Right Skewed) 指的是数据分布的右侧尾巴较长，负偏态 (Left Skewed) 指的是数据分布的左侧尾巴较长。对称的分布没有偏态，而正态分布是对称的。 ![1765439222661](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765439222661.png) ![1765440549468](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765440549468.png) 极端值可能是由于测量错误、数据输入错误或者真实的异常现象引起的。极端值可能会对模型的训练产生负面影响，因此需要进行处理。通常的处理方式是纠正极端值或者直接移除。数据预处理的一个重要任务就是鉴定极端值。 ##### Z 得分法 Z 得分法是一种基于统计学的方法，用于检测数据集中的极端值。其基本思想是计算每个数据点的 Z 得分，然后根据设定的阈值来判断是否为极端值。Z 得分表示一个数据点与均值的偏离程度，计算公式为： $$ z=\frac{x-\mu}{\sigma} $$ 其中， $x$ 是数据点的值， $\mu$ 是数据集的均值， $\sigma$ 是数据集的标准差。 z 得分描述了数据点与均值的偏离程度。计算出的 z 得分越大，则表示数据点越偏离均值，更容易被认为是极端值。 对于一个正态分布，有 99.7%的数据点位于区间 $[\mu - 3\sigma, \mu + 3\sigma]$ 之内。因此，通常将 z 得分的绝对值大于 3 的数据点视为极端值。 ![1765440869932](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765440869932.png) - 优点 - 计算非常高效 - 在大多数情况下，结果是正确的 - 缺点 - 只适用于正态分布或者近似正态分布 - 计算要求有足够多的数据点来准确估计均值和标准差 ##### 四分位距法 四分位距法是一种基于统计学的方法，用于检测数据集中的极端值。其基本思想是计算数据集的四分位数，然后根据设定的阈值来判断是否为极端值。四分位数将数据集分为四个部分： ![1765443456791](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765443456791.png) 四分位距的计算方式是: $$ \mathrm{IQR} = Q_3 - Q_1 $$ 其中， $Q_1$ 是第一四分位数， $Q_3$ 是第三四分位数。我们认为在范围 $[Q_1 - 1.5 \times \mathrm{IQR}, Q_3 + 1.5 \times \mathrm{IQR}]$ 之外的数据点是极端值。 - 优点 - 不要求数据符合正态分布，使用于各种分布类型 - 对干扰有高度抗性，对极端值不敏感 - 缺点 - 有些依赖于人类经验的参数（指 1.5 倍 IQR） - 对于高维数据无法使用 --- 还有其他的基于机器学习的极端值检测方法，比如孤立森林 (Isolation Forest)、K-Means 聚类 (K-Means Clustering), DBSCAN 聚类，随机森林 (Random Forest) 等等。这些方法通常需要更多的计算资源和时间，但在某些情况下可能会提供更好的检测效果。 #### 数据重复 数据重复指的是在数据集中存在多个相同的数据点的情况。 ![1765453194750](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765453194750.png) 数据重复可能会破坏数据的平衡性，可能会导致数据集中在某些特定的类别或者一系列特定的特征，让训练出来的模型对这一部分数据更加敏感，而忽略其他的重要的部分。以及，重复的数据可能会导致重复的计算，去除重复数据可以减少计算量和内存占用。 #### 数据不一致 数据不一致指的是在数据集中存在冲突或者矛盾的数据点的情况。 ![1765453202625](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765453202625.png) 数据不一致通常有这么几个形式 - 不一致的格式 - 如日期 "2023/01/01" 和 "01-Jan-2023" - 不一致的单位 - 如温度 "25°C" 和 "77°F" - 不一致的命名 - 如 "New York City" 和 "New York" - 不一致的逻辑 - 如年龄 "105" 和 "-5" - 不一致的值 - 如同一个人有不同的年龄记录 为了避免数据不一致对模型训练的影响，通常需要进行数据清理，确保每条记录都是唯一且一致的。可以通过以下方法来处理数据不一致： - 消除噪声与错误：清理测量错误、录入错误或异常值，降低训练数据中的随机干扰，提高模型性能与稳定性。 - 避免冲突信息：统一重复或矛盾记录（如同一人有不同年龄），保证每条样本只反映一个一致事实，防止模型学习到错误关联。 - 统一计算标准：规范单位、刻度和计算方法（如货币、时间格式、归一化规则），确保特征间可直接比较和组合，减少偏差来源。 - 避免维度灾难：通过合并同类特征或去除无关冗余，防止高维稀疏或类别爆炸，降低模型复杂度和过拟合风险。 - 提升泛化能力：一致且高质量的数据让模型学习到普遍规律而非噪声，从而在未见样本上表现更好。 - 确保逻辑一致性：维护字段间的逻辑关系（如出生日期与年龄匹配、订单状态与时间顺序），避免引入违背常识的训练样本。 > 这页 PPT 到底讲的是人话吗，写的是 impact 实际是 method ？ #### 数据变换 数据变换 (Data Transform) 指的是把数据转换成类正态分布或者其他的形式以便于模型处理的过程。常见的数据变换方法有： - 数据标准化 (Data Standardization) - 数据归一化 (Data Normalization) - 幂变换 (Power Transformation) ##### 数据标准化/归一化 在机器学习中，不同的特征可能有完全不同的数据范围，如年龄和收入。在不进行标准化/归一化的情况下，模型训练会出现这样的现象： - 梯度下降拟合过慢 - 不同方向上的步长不一致，导致收敛速度变慢 - 偏离的距离/相似度计算 - 距离计算中，范围较大的特征会主导距离的计算，导致模型无法正确捕捉数据的结构 - 模型权重不平衡 - 范围较大的特征会导致模型权重过大，影响模型的稳定性和泛化能力 而对数据归一化，则是将数据缩放到一个固定的范围内，通常是 $[0, 1]$ 。 ![1765480332491](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765480332491.png) 只有模型学习的数据是连续的数值时才有必要进行标准化。测试集的标准化需要用训练集的均值和标准差来进行以保证一致性。同时可以防止数据泄露。 而相对的，类型数据以及文本数据是不需要进行标准化/归一化的。类型需要用编码的方法来进行处理（之前提到的离散编码，如热编码，见[Lec7](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture7.html#类别数据-categorical-data)），文本另说。 ###### Z 得分标准化 在数据分布是正态分布的情况下，一种可行的标准化方法是 Z 得分标准化 (Z-Score Standardization)： $$ X_{norm} = \frac{X - \mu}{\sigma} $$ 其中， $X$ 是原始数据， $\mu$ 是数据的均值， $\sigma$ 是数据的标准差。 ![1765480836486](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765480836486.png) 这样的变换可以让数据的分布变为一个均值为 0，标准差为 1 的标准正态分布。这是我们大多数情况下使用的方法。但是，虽然大部分（真的是绝大部分）的数据都落在了 $[-3, 3]$ 的范围内，但是数据并没有被缩放到一个固定的范围内。 ###### 最小-最大归一化 在数据并不是正态分布的情况下，一种可行的归一化方法是最小-最大归一化 (Min-Max Normalization)： $$ X_{norm} = \frac{X - X_{min}}{X_{max} - X_{min}} $$ 其中， $X$ 是原始数据， $X_{min}$ 是数据的最小值， $X_{max}$ 是数据的最大值。 ![1765480972370](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765480972370.png) 可以很明显的看出，这个算法世纪上是把数据线性的映射到了 $[0, 1]$ 的范围内。 这样做的好处是所有的数据都在一个固定的范围内，避免了上面提到的问题。但是只有在数据接近均匀分布的情况下才适合使用，否则会导致数据集中在某个小范围内，影响模型的训练效果。以及，这种算法对极端值很敏感，如果出现一个极端值，整个数据的范围就会被拉大，导致大部分数据都集中在一个很小的范围内。 ![1765481086317](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765481086317.png) ###### Robust 标准化/归一化 Robust 标准化/归一化 (Robust Scaling) 是一种对极端值不敏感的数据变换方法。它使用中位数和四分位距来进行标准化/归一化。 $$ \begin{aligned} & X_{norm} = \frac{X - \mathrm{Median}}{\mathrm{IQR}} \\ & \mathrm{IQR} = Q_3 - Q_1 \end{aligned} $$ 其中， $X$ 是原始数据， $\mathrm{Median}$ 是数据的中位数， $\mathrm{IQR}$ 是数据的四分位距。 它的优势是因为中位数和四分位距对极端值不敏感，因此这种方法对极端值有很好的稳定性。但是缺点在于在某些情况下计算相对复杂。 --- | Method | Advantages | Disadvantages | | -------------------- | ------------------ | -------------------------------- | | 最小-最大归一化 | 数据限定在特定范围 | 适用于近似均匀分布；对极端值敏感 | | Z 得分标准化 | 适用于大多数情况 | 在正态分布下最佳；输出范围不固定 | | Robust 标准化/归一化 | 对极端值不敏感 | 计算相对复杂 | ##### 幂变换 幂变换是一系列的数据变换操作，通常使用的是单调的幂函数，如 $$ f(x) = a x^b $$ ![1765529307833](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765529307833.png) 经过幂变换后，数据可以 - 稳定方差大小，移除数据偏度 - 减少极端值的影响 - 不同区间内的方差一致，而不是随着数值增大而增大 - 使数据更接近正态分布 - 便于使用基于正态分布假设的模型 ### 数据集构造 数据集构造通常有这样的几种方式 - 单次训练/测试集（Hold-out）：把数据一次性划分为训练集和测试集（如 70/30）。 - K 折交叉验证（K-fold CV）：将数据分成 K 份，轮流用 K-1 份训练、1 份验证，取平均性能（常用 K=5 或 10）。 - 留一法交叉验证（Leave-One-Out, LOOCV）：把每个样本单独作为一次验证集（等于 K=N） - 考虑分层（Stratification）：在划分数据时保持类别（标签）比例一致，常用于类别不平衡时（如少数类很少）。 #### 构造训练集和测试集 ##### 简单划分 一个简单的划分方式是直接按比例随机划分原始数据集为两块：训练集和测试集。比如 80% 的数据作为训练集，20% 的数据作为测试集。之后用训练集来训练模型，用测试集来评估模型的性能。 ![1765531769919](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765531769919.png) 这种方式的优点是测试集是完全独立于训练集的，可以有效评估模型的泛化能力，避免模型过拟合。具体而言就是 `sklearn.model_selection.train_test_split` 。 ##### 分层抽样 对于多种类型的数据，一种方案是分层抽样。也就是在划分数据集时，保持各类别（标签）在训练集和测试集中的比例一致。这样避免样本的偏差，降低模型的方差。 ![1765531918071](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765531918071.png) #### 交叉验证 ##### K 折交叉验证 K 折交叉验证 (K-Fold Cross Validation) 是一种用于评估机器学习模型性能的技术。其过程是将数据集划分为 K 个子集，然后进行 K 次训练和测试。在每次迭代中，选择一个子集作为测试集，剩余的 K-1 个子集作为训练集。最终的模型性能是 K 次测试结果的平均值。 ![1765531974387](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765531974387.png) 这种方法的优点是 - 可以消除数据集划分的随机误差 - 对于性能评估更稳定可靠 - 可以最大化利用数据集，尤其适用于小数据集 但是，缺点是计算开销较大，因为需要训练 K 次模型，同时实现的复杂度也会上升。 对应的是 `sklearn.model_selection.cross_val_score` 。 ![Python Impls](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/image.png) ##### 留一法交叉验证 留一法交叉验证 (Leave-One-Out Cross Validation, LOOCV) 是 K 折交叉验证的一种特殊情况，其中 K 等于数据集的样本数量 N。也就是说，每次迭代中，选择一个样本作为测试集，剩余的 N-1 个样本作为训练集。这个过程重复 N 次，每个样本都被用作一次测试集。 ![1765532175030](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765532175030.png) 对应的是 `sklearn.model_selection.LeaveOneOut` 。 ![1765532196874](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture8.assets/1765532196874.png) ## 特征选择 Source: https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture9.html Repository path: lectures/Part.2/lecture9.md ### 更高阶的预处理和特征选择 特征选择指的是辨别和选择最相关、最有信息量的特征，以提升模型性能和减少计算复杂度的过程。在机器学习中，特征选择是一个关键步骤，因为它可以帮助我们去除冗余或无关的特征，从而提高模型的泛化能力。 ![1761035668126](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1761035668126.png) 优点 - 加速训练 - 模型不需要区学习不相关的特征 - 减少过拟合 - 避免模型从不相关的数据中学习到噪声 - 提高可解释性 - 更少的特征使得模型更容易理解和解释 但是，特征选择也存在隐患 - 数据泄露 (Data Leakage) - 在特征选择过程中使用了测试集的信息，导致模型在测试集上表现异常好，但在实际应用中表现不佳。 - 多重共线性 (Multicollinearity) - 当两个或多个特征高度相关时，可能会导致模型不稳定，影响模型的性能和解释性。 - 目标泄漏 (Target Leakage) - 训练特征中包含了与目标变量直接相关的信息，导致模型在训练时表现过于理想，但在实际应用中效果不佳。 - 忽略特征关系 - 某些特征可能单独看起来不重要，但与其他特征结合时可能具有重要意义。简单的特征选择方法可能会忽略这些复杂的关系。 常用的特征选择方法有 - 过滤法 (Filter Methods) - 基于统计指标（如相关系数、卡方检验等）来评估每个特征与目标变量的关系，选择得分最高的特征。 - 快速且易于实现，但可能忽略特征之间的相互关系。 - 包装法 (Wrapper Methods) - 使用特定的机器学习算法作为评估标准，通过递归特征消除（RFE）等方法，选择最优特征子集。 - 能够考虑特征之间的相互关系，但计算成本较高。 - 嵌入法 (Embedded Methods) - 在模型训练过程中进行特征选择，如 Lasso 回归中的 L1 正则化，可以自动选择重要特征。 - 综合了过滤法和包装法的优点，效率较高。 ### 过滤法 (Filter Methods) 常用的过滤法有 - 方差阈值法 (Variance Threshold) - 移除方差低于阈值的特征，他们被视为常数特征或近似常数特征 - 数据首先需要标准化 - 单变量统计检验 - 包括：卡方检验 (Chi-Squared Test)，F 检验 (F-test) - 可以做到模型无关 - 易于计算，适用于高阶数据的初步过滤 - 不能捕捉特征之间的相互作用，可能会丢失一些有用的信息 - 相互信息法 (Mutual Information) #### 卡方检验 卡方检验是一种用于评估两个分类变量之间关联强度的统计方法。在特征选择中，卡方检验可以用来评估每个分类特征与目标变量之间的关系，从而选择最相关的特征。 1. 确定零假设和备择假设 - 零假设 (H0)：特征与目标变量之间没有关联 - 备择假设 (H1)：特征与目标变量之间存在关联 2. 计算卡方统计量 $$ \chi^2 = \sum \frac{(O_{ij} - E_{ij})^2}{E_{ij}} $$ - 其中， $O_{ij}$ 是观察频率， $E_{ij}$ 是期望频率 3. 更高的卡方值表示特征与目标变量之间的关联更强，根据给定的显著性水平 (如 0.05) 来决定是否拒绝零假设 在卡方检验中实现特征选择方法的步骤是： - 连续变量分箱 (Binning) - 将连续变量转换为分类变量 - 每个区间内的期望频率应足够大（通常至少为 5） - 测试统计量计算 - 计算每个特征与目标变量之间的卡方统计量 - 根据预设条件进行特征选择 - 可以对测试统计量排序，选择前 k 个特征或根据显著性水平选择特征 - 可以设置显著性水平 (如 0.05) 来决定是否保留特征 #### F 检验 F 检验是一种用于比较多个组之间均值差异的统计方法。在特征选择中，F 检验可以用来评估每个数值特征与分类目标变量之间的关系，从而选择最相关的特征。 1. 确定零假设和备择假设 - 零假设 (H0)：不同类别的均值相等 - 备择假设 (H1)：至少有一个类别的均值不相等 2. 计算 F 统计量 $$ F = \frac{MSB}{MSW} = \frac{SSB/(k-1)}{SSW/(N-k)} $$ - 其中， $MSB$ 是组间均方 (Mean Square Between)， $MSW$ 是组内均方 (Mean Square Within)，$SSB$ 是组间平方和 (Sum of Squares Between)，$SSW$ 是组内平方和 (Sum of Squares Within) - $MSB = \frac{SSB}{df_B} = \frac{SSB}{k-1}$ ， $MSW = \frac{SSW}{df_W} = \frac{SSW}{N-k}$ - $k$ 是类别数， $N$ 是总样本数 - $SSB = \sum n_i(\overline{X}_i - \overline{X})^2$ ， $SSW = \sum \sum (X_{ij} - \overline{X}_i)^2$ - 其中， $n_i$ 是第 $i$ 类的样本数， $\overline{X}_i$ 是第 $i$ 类的均值， $\overline{X}$ 是总体均值 3. 根据给定的显著性水平确定检验的临界值，比较计算得到的 F 统计量与临界值，决定是否拒绝零假设 实现 F 检验方法的具体步骤是 - 连续数据分箱 - 将连续变量转换为分类变量 - 每个箱子的预期频率应足够大（通常至少为 5） - 检验统计量计算 - 计算每个特征与目标变量之间的 F 统计量 - 特征选择 - 对检验统计量进行排序，选择前 k 个特征或根据显著性水平选择特征 - 可以设置显著性水平 (如 0.05) 来决定是否保留特征 #### 相互信息法 相互信息 (Mutual Information) 是一种衡量两个随机变量之间相互依赖关系的度量。在特征选择中，相互信息可以用来评估每个特征与目标变量之间的信息共享程度，从而选择最相关的特征。 $$ I(X; Y) = \sum_{x \in X} \sum_{y \in Y} p(x, y) \log \left( \frac{p(x, y)}{p(x)p(y)} \right) $$ - 其中， $I(X; Y)$ 是特征 $X$ 与目标变量 $Y$ 之间的相互信息 - $p(x, y)$ 是 $X$ 和 $Y$ 的联合概率分布 - $p(x)$ 和 $p(y)$ 分别是 $X$ 和 $Y$ 的边际概率分布 在物理意义上，这个公式表示通过知道变量 $X$ 的值，我们可以减少对变量 $Y$ 不确定性的程度。相互信息越高，说明特征与目标变量之间的关系越强。 使用特征选择方法的步骤： - 连续概率分箱 - 同上 - 计算特征和目标之间的相互信息 - 根据相互信息值进行特征选择 - 对相互信息值进行排序，选择前 k 个特征 - 根据设定的阈值选择特征 ### 包装法 (Wrapper Methods) 常用的包装方法有 - 前向选择 (Forward Selection) - 后向消除 (Backward Elimination) - 递归特征消除 (Recursive Feature Elimination, RFE) 包装法的优缺点为： - 优点 - 基于模型的性能进行特征选择，通常能获得更好的结果 - 模型无关。方法只与模型的输出结果有关，可以应用于各种模型 - 缺点 - 高算力需求 - 需要多次训练模型，计算成本较高 - 过拟合风险 - 可能会选择在训练集上表现良好的特征，但在测试集上表现不佳 #### 前向选择 (Forward Selection) 前向选择是一种递归特征选择方法，从一个空特征集开始，逐步添加特征，直到达到预定的停止条件。具体步骤如下： - 初始化 - 初始化一个空的集合 $S$ 来存储已选择的特征，一个未选择的特征集合 $F$ 包含所有特征，一个评估指标 - 在特征中迭代 - 对于每个未选择的特征 $f$ 在集合 $F$ 中 - 将特征 $f$ 添加到当前选择的特征集合 $S$ 中，形成新的特征集合 $S' = S \cup \{f\}$ - 使用特征集合 $S'$ 训练模型，并评估模型性能，记录评估结果 - 选择最优特征 - 根据训练结果，选择最佳的特征 $f^*$ ，即使得模型性能最优的特征 - 更新集合 - 把最优特征添加到已选择的特征集合 $S$ 中，并从未选择的特征集合 $F$ 中移除 - 重复直到结束条件 - 如特征集合达到预定大小，或模型性能不再显著提升（提升值小于某个阈值） 其优缺点为: - 优点 - 模型需要反复训练，计算量仍然比其他的方法小 - 缺点 - 和贪心算法类似，忽略了特征之间的相关性，可能得到的特征集合不是最优的。 #### 后向消除 (Backward Elimination) 后向消除是一种递归特征选择方法，从包含所有特征的集合开始，逐步移除不重要的特征，直到达到预定的停止条件。具体步骤如下： - 初始化 - 初始化一个选择的特征集合 $S$ 包含所有特征，一个评估指标 - 训练模型 - 使用当前选定的特征集合来训练模型并获得评估结果 - 评估特征重要性 - 使用特征集删去每个特征 $f$ ，形成新的特征集合 $S' = S \setminus \{f\}$ ，并使用 $S'$ 训练模型，评估模型性能，记录评估结果 - 更新选择特征集合 - 找到移除后使模型性能提升或下降最小的特征 $f^*$ ，将其从选择的特征集合 $S$ 中移除 - 重复直到结束条件 - 如特征集合达到预定大小，或模型性能不再显著下降 其优缺点为： - 优点 - 更好的找到了效率和效果之间的平衡，适用于高维数据 - 缺点 - 依赖模型能力，模型必须从给定数据中全面且正确的学习，否则可能会移除重要特征 #### 递归特征消除 (Recursive Feature Elimination, RFE) 递归特征消除 (RFE) 是一种基于模型的特征选择方法，通过递归地训练模型并移除最不重要的特征，直到达到预定的特征数量。具体步骤如下： - 初始化 - 选择一个基模型（如线性回归、决策树等），设定目标特征数量 $k$ - 初始化特征集合 $S$ 包含所有特征 - 一个评估指标 - 训练基模型 - 使用当前选择的特征集合 $S$ 训练基模型 - 评估特征重要性 - 根据基模型的特征重要性评分，识别出最不重要的 - 更新特征集合 - 移除最不重要的特征 $f^*$ ，更新特征集合 $S = S \setminus \{f^*\}$ - 重复直到达到终止条件 - 直到特征集合 $S$ 的大小等于目标特征数量 $k$ - 所有特征都被迭代过了 - 优点 - 高效，只需要一个小型的基础模型，不用反复训练复杂模型。 - 能够模型无关地捕获相关性 - 缺点 - 依赖模型的可解释性，基础模型需要是可解释的，以便评估特征重要性 ### 嵌入法 (Embedded Methods) 嵌入法是一种在模型训练过程中进行特征选择的方法。它将特征选择过程嵌入到模型训练过程中，通过正则化等技术来选择重要的特征。 常用的嵌入法有 - 线性回归：正则化方法 - 树模型：决策树特征重要性 因为嵌入法将特征选择过程与模型训练过程结合在一起，因此它通常比过滤法和包装法更高效。嵌入法能够自动选择重要的特征，同时考虑特征之间的相互关系，从而提高模型的性能和泛化能力。如 - 深度学习：注意力机制 - 优点 - 高效率 - 模型只用训练一次，因为选择过程和训练过程结合在一起 - 更好的模型适应性 - 特征选择依赖于特定算法，不同模型可能会有不同的特征子集 - 缺点 - 缺少可解释性 - 复杂模型的特征重要性结果难以解释 - 难以检测错误 - 特征的重要性并没有被显式地给出，只能通过模型表现判断特征是否被正确的使用。 #### 线性回归：正则化方法 给定两个集合 $X_i = {x_1, x_2, \ldots, x_n}$ 和 $Y_i = {y_1, y_2, \ldots, y_n}$ ，线性回归的目标是找到一组参数，使得方程 $\hat{y}_k = \beta_0 \sum_{i=1}^n \beta_i x_i + \varepsilon$ 能够最好地拟合数据，即 $\min_\beta \frac{1}{2n} \sum_{k=1}^n (\hat{y}_k - y_k)^2$ 。 L1 正则化指的是在正则化中添加一个附加项，也就是 $\min_\beta \left[ \frac{1}{2n}\sum_{k=1}^n (\hat{y}_k - y_k)^2 + \lambda \sum_{j=1}^p |\beta_j| \right]$ ，其中 $\lambda$ 是正则化参数，在取 $0$ 时表示没有正则化。接下来的步骤是 - 将所有样本标准化，确定值范围的一致性 - 确定一个合适的正则化参数 $\lambda$ ，通过消融实验进行调整 - 使用新的优化目标来训练模型，系数不为 $0$ 的特征即为被选择的特征 正则化分析能实现特征选择的原因是，当原始目标的轮廓线和正则化项的轮廓线相切时，最优解往往出现在坐标轴上，从而导致某些系数变为零。 ![1761039292210](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1761039292210.png) - 优点 - 自动特征选择，不需要额外的特征选择步骤 - 高计算效率，适用于高维数据 - 提供了系数的可解释性 - 缺点 - 对于高度相关的特征，可能只能随机选择一个 - 需要对数据归一化 - 只适用于线性模型 #### 树模型：决策树特征重要性 决策树指的是一种基于树形结构进行决策的模型。它通过对数据进行递归划分，形成一个树状结构，每个节点表示一个特征，每个分支表示一个特征值的取值范围，叶子节点表示最终的预测结果。 1. 选择一个特征来分割数据 有多种方法，比如 ID3，CART，MSE 2. 在满足预设条件时终止 典型的条件是样本数量小于阈值，所有样本属于同一类别或者树达到了最大深度 3. （可选）剪枝 通过移除一些不必要的节点来简化树结构，防止过拟合 特征重要性是指在决策树模型中，每个特征对模型预测结果的贡献程度。常用的计算方法有基尼重要性 (Gini Importance) 和信息增益 (Information Gain)。这里使用基尼不纯度 (Gini Impurity) 来计算特征重要性 $$ \mathrm{Gini}(D) = 1 - \sum_{i=1}^P p_i^2 $$ 其中， $D$ 是数据集， $P$ 是类别数， $p_i$ 是类别 $i$ 在数据集 $D$ 中的比例。此时，特征重要性被定义为 $$ F = \frac{\sum_D \Delta_F \mathrm{Gini}(D)}{ \sum_F \sum_D \Delta_F \mathrm{Gini}(D) } $$ 其中， $\Delta_F \mathrm{Gini}(D)$ 是在节点 $D$ 上使用特征 $F$ 进行划分所带来的基尼不纯度的减少。如果一个特征没有被用于任何划分，则其重要性为 $0$ 。 此时，通过特征的重要性值来选择特征，通常选择重要性值较高的特征。或者选择前 k 个重要性值最高的特征。 - 优点 - 自动捕捉非线性关系 - 易于计算 - 缺点 - 对相关性敏感 - 倾向于高基数特征 ### 降维 (Dimension Reduction) 降维指的是通过数学或者统计的方法把一个高维度的数据转换成低维度的表示方法。它的目的是尽可能的保留原始数据的关键信息，同时降低数据的复杂性，提高计算效率，提升模型性能。 特征选择方法也可以实现降维，但那是通过直接抛弃特征实现的。如果所有的原始特征都很重要，特征选择方法会导致显著的性能下降。这时，降维方法就派上用场了。 ![1765533944119](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765533944119.png) 降维方法的作用有 1. 缓解“维度灾难” (Curse of Dimensionality) - 高维数据的特征是距离计算失效、样本稀疏，易过拟合 - 降维可以让数据更加密集，提升泛化能力 2. 提高计算效率 - 低维的数据计算量显著减少 - 优化算法在低维空间更高效 3. 去除噪声和荣誉 - 去除无关特征并合并相关特征 4. 提高可视化能力 - 三维以上的数据无法直接可视化 - 降维到二维或三维，便于可视化分析 5. 增强模型可解释性 - 低维特征更容易理解 #### 维度灾难 如果把每一个特征都看作一个维度，随着维度数目的增加，不同的样本之间更容易区分开来。 但是，如果样本数量不跟着增加，维度越高则样本越稀疏，训练出来的模型越容易过拟合。 引入过多的特征会导致过拟合，这就是“维度灾难” (Curse of Dimensionality)。 ![1765534223050](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765534223050.png) #### 降维的基本概念 > 不禁令人反思……我真的上过线代吗？ 对于一个实对称矩阵 $A$ （ $A = A^T$ ），存在正交特征分解 (eigen-decomposition)： $$ A = Q \Lambda Q^T $$ 其中 $Q$ 为正交矩阵（ $Q^T Q = I$ ），列向量为 $A$ 的特征向量； $\Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \ldots, \lambda_n)$ 为对角矩阵，对角元为 $A$ 的特征值。若 $A$ 为正定，则所有 $\lambda_i > 0$ 。 > 注意：特征值分解要求 $A$ 为方阵；若 $A$ 不对称则一般不能用正交矩阵对角化。 计算特征值的方法是求解特征方程： $$ \det(\Sigma - \lambda I) = 0 $$ 其中 $I$ 为单位矩阵。最终得到的 $\lambda$ 值即为特征值，对应的特征向量 $v_i$ 满足 $(A - \lambda_i I)v_i = 0$ 。 --- 对于一个 $m \times n$ 的矩阵 $A$ ，存在奇异值分解 (Singular Value Decomposition, SVD)： $$ A = U \Sigma V^T $$ 其中 $U$ 为 $m\times m$ 的正交矩阵，列向量为 $A A^T$ 的特征向量； $V$ 为 $n\times n$ 的正交矩阵，列向量为 $A^T A$ 的特征向量。 $\Sigma$ 为 $m\times n$ 的“对角”矩阵，主对角线上为非负奇异值 $\sigma_1\ge\sigma_2\ge\cdots\ge 0$ （数量 ≤ min(m,n)）。奇异值满足 $\sigma_i^2 = \lambda_i(A^T A)$ ，即 $\sigma_i$ 为 $A^T A$ 的特征值的平方根。SVD 对任意实矩阵都存在，可用于低秩近似、伪逆等。 ![1765535908495](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765535908495.png) --- 对于一个随机变量 $X=(x_1, x_2, \ldots, x_n)^T$ ，其协方差矩阵定义为 $$ \mathrm{Cov}(X) = E[(X - E[X])(X - E[X])^T] $$ 写成矩阵形式为: $$ \left[ \begin{matrix} \sigma(x_1, x_1) & \sigma(x_1, x_2) & \cdots & \sigma(x_1,x_n) \\ \sigma(x_2,x_1) & \sigma(x_2,x_2) & \cdots & \sigma(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots \\ \sigma(x_n,x_1) & \sigma(x_n,x_2) & \cdots & \sigma(x_n,x_n) \end{matrix} \right] $$ 这里， $\sigma(x_i,x_j)$ 表示 $x_i$ 和 $x_j$ 的协方差，衡量它们的线性相关性。协方差矩阵是对称的，且正定（若变量线性无关）。 #### 降维评估 降维评估指的是在降维过程中，评估降维效果的好坏。常用的评估指标有: - 保留方差比例 (Retained Variance Ratio) - 衡量降维后数据中保留的原始数据方差比例 $$ \frac{Var(X)}{Var(X_r)} $$ - 其中， $X$ 是原始数据， $X_r$ 是降维后的数据 - 重构误差 (Reconstruction Error) - 衡量降维后数据重构回原始数据时的误差 $$ \begin{aligned} & Z = \mathrm{Encoder}(X) \\ & \hat{X} = \mathrm{Decoder}(Z) \\ & \mathrm{Error}(X, \hat{X}) \end{aligned} $$ - 其中， $X$ 是原始数据， $\hat{X}$ 是重构后的数据, $\mathrm{Error}$ 是误差函数（如均方误差 MSE, 平均绝对误差 MAE 等） - 下游任务性能 - 评估依赖于降维数据的下游任务（如分类、回归等）的性能相比于原数据的降低幅度 > 降维一定会提升模型性能吗？ > > - 不一定，降维也会导致准确率下降，只提高计算效率 > > 降维后保留的主成分可以直接解释吗？ > > - 降维保留的特征可能也无法直接解释 #### 线性与非线性降维 线性降维 (Linear Dimensionality Reduction) 指的是通过找到原始特征空间的线性变换方法来将数据映射到低维度的子空间。如主成分分析法 (PCA)，线性判别分析 (LDA)，奇异值分解 (SVD) 等。 非线性降维 (Non-linear Dimensionality Reduction) 指的是使用非线性变换对数据进行建模或映射，从而实现低维度空间的数据表示。如 核 PCA，局部线性嵌入 (LLE)，t 分布随机邻域嵌入 (t-SNE)，变分自编码器 (VAE) 等。 #### 线性降维 ##### 主成分分析 (PCA) ![1765539863287](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765539863287.png) 主成分分析 (Principal Component Analysis, PCA) 是一种常用的线性降维方法，通过线性变换将高维数据映射到低维空间，同时最大化保留数据的方差。其基本思想是找到数据中方差最大的方向作为新的坐标轴，从而实现降维。 其大致过程为： - 计算出数据在各个维度上的方差大小 - 按照方差大小对维度进行排序 - 方差越小对维度，通常数据范围越小，提供了更少的特征 - 选择最大的 k 个特征作为新的特征子空间，移除方差较小的特征 --- 具体的操作步骤如下： 1. **归一化** 原本的数据 $X$ 是一个 $n\times p$ 的矩阵，有 $n$ 个样本和 $p$ 个特征。其均值为 $\mu = \frac{1}{n} \sum_{i=1}^n X_i$ 。 $$ X_{centered} = X - \mu $$ ![1765540275241](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765540275241.png) 目的是消除不同特征维度和偏差的影响，使 PCA 能够真正捕捉方差而非均值 2. **计算协方差矩阵** $$ \Sigma = \frac{1}{n-1} X_{centered}^T X_{centered} $$ 协方差矩阵是一个 $p \times p$ 的矩阵，其对角线元素是各个特征的方差，非对角线元素是特征之间的协方差。 因为标准化过程中已经把所有的数据都中心化了，所以协方差矩阵可以简化为上面的形式。 3. **特征值分解** 对协方差矩阵进行特征值分解 $$ \Sigma = Q \Lambda Q^T $$ > 背到这里的时候表情 be like: $Q \Lambda Q^T$ Q 是一个 $p \times p$ 的正交矩阵，列向量为协方差矩阵的特征向量； $\Lambda$ 是一个对角矩阵，对角线元素为协方差矩阵的特征值，按从大到小排序。特征向量和特征值是一一对应的。 4. **选择主成分** 降所有的特征值以及对应的特征向量进行排序。特征值表示该特征向量方向上的方差大小。计算每个成分的解释方差比 (Explained Variance Ratio, EVR)： $$ \mathrm{EVR}_j = \frac{\lambda_j}{\sum_{i=1}^p \lambda_i} $$ 选择前 $k$ 个特征值对应的特征向量作为主成分，构成降维后的特征子空间。 - 如果需要固定输出维度数，则选择纬度数个特征值对应的特征向量。 - 如果指定原始方差保留比例，则选择前 $k$ 个特征值，使得 $\sum_{j=1}^k \mathrm{EVR}_j \geq \text{指定比例}$ 。 - 也可以选择画一个折线图，选择拐点处的特征值个数 5. **映射数据** 使用选定的特征向量构造一个映射矩阵 $W_k$ ，形状为 $p\times k$ : $$ Z = X_{centered} W_k $$ 最后得到的 $Z$ 是一个 $n\times k$ 的矩阵，表示降维后的数据。 --- 这种方法的优势在于 - 降噪：较少的主成分通常和噪声有关，通过去除这部分特征可以提高信噪比 - 避免冗余：所有主成分方向互相垂直，新的特征完全无关 但是，PCA 也有一些局限性 - 降低可解释性：主成分是原始特征的线性组合，物理意义不明确 - 依赖方差：倾向于保留方差较大的特征，可能忽略对任务重要但方差较小的特征 ##### 线性判别分析 (LDA) 线性判别分析 (Linear Discriminant Analysis, LDA) 指的是寻找一条线，满足 - 最大化类间分离：不同类别的样本在该线上的投影距离尽可能大 - 最小化类内散布：同一类别的样本在该线上的投影距离尽可能小 用这种方法来最大化不同类别数据的区分度 ![1765541419126](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765541419126.png) --- 具体的操作步骤如下： 1. **计算均值** 和 PCA 类似， $X$ 是一个 $n\times p$ 的矩阵，有 $n$ 个样本和 $p$ 个特征。其总体均值为 $m = \frac{1}{n} \sum_{i=1}^n X_i$ ，每个类别的均值为 $m_i$ 。 2. **计算散布矩阵 (Scatter Matrices)** 计算两种散布矩阵。对于同一类型，计算类内散布矩阵 (Within-class Scatter Matrix)： $$ S_W = \sum_{i=1}^c S_i = \sum_{i=1}^c \sum_{x \in D_i} (x - m_i)(x-m_i)^T $$ 对于不同类型，计算类间散布矩阵 (Between-class Scatter Matrix)： $$ S_B = \sum_{i=1}^c N_i (m_i - m)(m_i - m)^T $$ 其中， $c$ 是类别数， $D_i$ 是第 $i$ 类的样本集合， $N_i$ 是第 $i$ 类的样本数量。 3. **计算目标函数** $$ S = S_W^{-1} S_B $$ 得到的 $S$ 是一个 $p \times p$ 的矩阵，用于衡量类间分离和类内散布的比值。 4. **特征值分解** 在矩阵 $S$ 上进行特征值分解： $$ S = Q \Lambda Q^T $$ 得到一系列的特征值 $\lambda_i$ 和对应的特征向量 $q_i$ 。 5. **选择投影方向** 将特征值以大小降序排列，选择前 $k$ 个特征值对应的特征向量作为投影方向，构成投影矩阵 $W_k$ 。这里 $k \leq c-1$ ，因为 LDA 最多只能找到 $c-1$ 个有意义的投影方向，类间散布矩阵的秩最大为 $c-1$ 。 6. **映射数据** $$ Z = X W_k $$ 最后得到的 $Z$ 是一个 $n\times k$ 的矩阵，表示降维后的数据。 7. _(可选) 基于新数据分类_ 一种典型的方法是计算每种类别的投影中心点 $m_i'$ ，然后对于新的样本 $x_{new}$ ，先计算它的投影 $z_{new} = x_{new}^T W_k$ ，然后用分类器（如最近中心分类器）来预测类别： $$ \mathrm{argmin}_i || z_{new} - m_i' ||^2 $$ 这里的 $\mathrm{argmin}$ 表示选择距离最小的类别作为预测结果。 --- 这种方法的优势在于 - 监督信息：利用类别标签信息，通常比无监督方法有更好的降维效果 - 可解释性：特征向量代表了最具区分度的特征组合 LDA 的局限性在于 - 高斯分布：假定数据服从高斯分布，可能不适用于非高斯数据 - 对异常值敏感：均值和散布矩阵受异常值影响较大 --- 对比一下 PCA 和 LDA 的优势和差异，可以得到这样的总结： | **角度** | **PCA** | **LDA** | | -------- | ---------------------------- | -------------------------------- | | 学习类型 | 无监督学习 | 监督学习（有标签） | | 优化目标 | 最大化数据方差，保留最多信息 | 最大化类间区分度 | | 降维限制 | 可以降维到任意维度 | 降维到 $c-1$ 维度， $c$ 是类别数 | | 应用重点 | 通用降维、去噪、可视化 | 分类任务的特征提取、降维 | | 效果 | 数据全局结构更清晰 | 类别分离性增强 | ##### 奇异值分解 (SVD) ![1765542721758](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765542721758.png) 任何矩阵都可以提供一种特定的数据视角，而奇异值分解 (Singular Value Decomposition, SVD) 则是一种强大的矩阵分解技术，目标是找到一组更本质的正交基，来重新描述数据，发现其内部结构。 --- 具体的操作步骤如下： 1. **归一化** $X$ 是一个 $n \times p$ 的矩阵，有 $n$ 个样本和 $p$ 个特征。其均值为 $\mu = \frac{1}{n} \sum_{i=1}^n X_i$ 。 $$ A = X - \mu $$ ![1765542839931](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765542839931.png) 和 PCA 类似，目标是消除不同特征维度和偏差的影响，使 SVD 能够真正捕捉数据的方差而非均值 2. **奇异值分解** $$ A = U \Sigma V^T $$ 其中， $U$ 是一个 $n \times n$ 的正交矩阵，列向量为 $A A^T$ 的特征向量； $\Sigma$ 是一个 $n \times p$ 的“对角”矩阵，主对角线上为奇异值。 构造 $U$ 和 $V$ 的方法是对 $A A^T$ 和 $A^T A$ 分别进行特征值分解，得到它们的特征向量。而奇异值就是得到的特征值的平方根。 3. **选择目标维度数量** 计算奇异值的平方和与总平方和的比值。奇异值 $\sigma_i$ 的平房就是矩阵 $A^T A$ 的特征值，表示了方差的大小。 $$ \mathrm{EVR}_j = \frac{\sigma_j^2}{\sum_{i=1}^{\min(n,p)} \sigma_i^2} $$ 通常 $k$ 的选择方法是选择累加的解释方差比达到某个阈值（如 95%）时的 $k$ 值大小，如 95% 和 99%。 另一种方法是使用折线图，选择拐点处的特征值个数 ![1765543277115](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture9.assets/1765543277115.png) 4. **映射数据** 有两种方法可以达成映射数据的目的： 1. 使用右侧的奇异矩阵进行投影（在特征空间降维） $$ Z = A V_k = (U_k \Sigma_k V_k^T) V_k = U_k \Sigma_k $$ 这里， $V_k$ 是前 $k$ 列的奇异向量， $\Sigma_k$ 是前 $k$ 个奇异值构成的对角矩阵。 Z 的每一行是一个样本在新 k 维特征空间中的坐标。新特征通常是原始特征的线性组合。 这是最常用的方法。 2. 直接使用左侧的奇异矩阵以及奇异值 $$ Z = U_k \Sigma_k $$ 这里， $U_k$ 是前 $k$ 列的奇异向量, $\Sigma_k$ 是前 $k$ 个奇异值构成的对角矩阵。 最终得到的结果和方法 1 是完全一样的。 --- 奇异值分解的优势在于 - 数值稳定性：这是解决线性代数问题的最稳定可靠的方法 - 强通用性：适用于任何矩阵，不要求方阵或对称矩阵，不要求满秩 - 最佳逼近：Eckart-Yong-Mirsky 定理表明了截断 SVD 在 Frobenius 范数下提供了最佳低秩近似 > ……这句话是人话吗？ 其劣势在于 - 高计算成本：大型矩阵的完整奇异值分解计算成本高，但是存在计算截断 SVD 的高效随机算法 - 低可解释性：新的特征通常是原始特征的线性组合，物理意义不直观 - 线性假设：只能捕捉数据的线性结构，无法处理复杂的非线性关系 ##### SVD 和 PCA 的差异 以这个数据为例子：一个二维的样本，共有三个样本两个特征： $$ X = \left[\begin{matrix} 10 & 0 \\ 10 & 1 \\ 10 & -1 \\ \end{matrix} \right] $$ 其样本主要落在了 $(10, 0)$ 附近，特征一有较大的均值，特征二有较大的方差。 如果对未中心化的数据进行 SVD 分解： $$ X^T X = \left[\begin{matrix} 300 & 0 \\ 0 & 2 \\ \end{matrix} \right] $$ 最大的特征值为 $300$ ，特征向量为 $[1, 0]$ ,第一个右奇异向量指向了特征一的方向。这是因为 SVD 分解的是未中心化的数据矩阵，特征一的均值较大，导致其在协方差矩阵中占主导地位。 也就是说，SVD 更关注的是第一列的数值大小，将其视为了主要方向。 --- 同样的数据，如果先对数据进行中心化处理，之后进行分解： $$ X_c = X - \mu = \left[\begin{matrix} 0 & 0 \\ 0 & 1 \\ 0 & -1 \\ \end{matrix} \right] $$ 然后协方差矩阵为： $$ C = \frac{1}{n-1}X^T_c X_c = \left[\begin{matrix} 0 & 0 \\ 0 & 1 \\ \end{matrix} \right] $$ 主特征向量是 $[0, 1]$ ，指向了特征二的方向。这是因为 PCA 分解的是中心化后的数据矩阵，特征二的方差较大，导致其在协方差矩阵中占主导地位。 也就是说，PCA 更关注的是数据的方差大小，将其视为了主要方向。 --- 总结一下，在数据已经中心化的情况下，对矩阵 $A$ 进行 SVD 操作，右侧的奇异值矩阵 $V$ 等价于 PCA 操作中的特征向量矩阵，其降维数据 $Z = A V_k$ 也等价于 PCA 降维数据。 它们主要的区别在于，SVD 可以适用于任何矩阵，而 PCA 只适用于协方差矩阵。 ## 支持向量机 (Support Vector Machine, SVM) Source: https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture10.html Repository path: lectures/Part.2/lecture10.md ### 基本概念 分类 (Classification) 是机器学习中的一个重要任务，旨在将数据点分配到预定义的类别中。比如这个图，一个模型有了不同的水果的图片和标签，然后训练出一个分类器，来区分苹果和橘子。 ![1765558346055](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765558346055.png) 支持向量机 (SVM) 是一种强大的监督学习算法，广泛应用于分类和回归任务。SVM 的核心思想是找到一个最佳的超平面 (hyperplane)，将不同类别的数据点分开，同时最大化类别之间的间隔 (margin)。 ![1765558422447](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765558422447.png) 图上是不同的划分两种类的方式，其中，不能正确的分离两个种类的点的线是错误的，能够正确的分离两种类型的点的线是可以接受的，而我们期望找到的是所有的点距离这条线都尽量远的线，这样的线就是最佳超平面。 SVM 的用途很广，如 | 应用场景 | 输入 | 标签 | | -------- | ------------------ | -------------- | | 推荐系统 | 评分, 点击, 或喜欢 | 偏好评分 | | 欺诈检测 | 账户交易历史 | 是否为洗钱账户 | | 肿瘤诊断 | 医疗图片 | 是否存在肿瘤 | | 手写识别 | 手写图像 | 数字 | | … | … | … | ### SVM 概览 支持向量机 (Support Vector Machine, SVM) 指一种常用并且有效的分类算法。它有坚实的理论基础，是通过超平面来划分不同类别的数据点。 ![1765877135304](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765877135304.png) 超平面 (Hyperplane) 是一个决策边界，分开了两个不同种类的数据点，并以此数据分为两类。它是一个一系列的点的集合，这些点满足一个线性方程: $$ h(x) = w^T x + b = 0 $$ 其中，$w$ 是这个超平面的法向量，决定了超平面的方向；$b$ 是偏置项，决定了超平面与原点的距离。 ![1765877211517](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765877211517.png) 对于任意的一个数据点，可以带入 $h(x)$ 来判断它属于哪一类。如果结果是 $h(x) = 0$，那么这个点就在超平面上；如果 $h(x) > 0$，那么这个点属于一类；如果 $h(x) < 0$，那么这个点属于另一类。 --- 在 SVM 中，一个超平面可以把整个样本空间划分成两个部分，也就是说这个超平面的维度比样本空间的维度少一维。例如，在二维空间中，超平面是一个直线；在三维空间中，超平面是一个平面。 ![1765877591387](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765877591387.png) 训练 SVM 的目的是找到最好的超平面，其满足：能把不同类别的数据点正确分类，并且最大化类别之间的间隔 (margin)。 通常来讲，间隔越大，模型的泛化能力越强，在测试集上的表现也会更好，最终得到的分类器的置信度也会更高。 ![1765877651430](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765877651430.png) 支持向量 (Support Vectors) 指的是哪些距离超平面最近的数据点。在 SVM 中，分类器只与这些支持向量有关，而与其他数据点无关。换句话说，支持向量决定了超平面的最终位置和方向。这也是 SVM 名称的由来。 ### SVM 分类 SVM 主要分为这么几类： - 线性 SVM (Linear SVM) - 硬间隔分类器 (Hard Margin Classifier) - 软间隔分类器 (Soft Margin Classifier) - 非线性 SVM (Non-linear SVM) - 多类型 SVM (Multi-class SVM) 其中，硬间隔分类器适用于数据集是完全线性可分的，可以通过一个超平面完全把两种数据分开来。但是这种方法也有很明显的局限性：只适用于很完美的数据集，无法处理极端值、非线性分布、多类型问题。 ![1765878245681](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765878245681.png) 软间隔分类器解决的是极端值的问题。它适用于数据集接近线性可分的情况，但是允许一定的错误分类，通过引入惩罚项来平衡分类的准确性和间隔的大小。 ![1765878288581](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765878288581.png) 非线性 SVM 适用于数据并不是线性可分的数据集，通常是将低维度的不线性可分的数据映射到高维度的空间中，使其在高维空间中线性可分。这个过程通常通过核函数 (Kernel Function) 来实现。 ![1765878323264](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765878323264.png) 最后，上述的所有 SVM 都只适用于二分类问题 (Binary Classification)，而多类型 SVM 则是将二分类 SVM 扩展到多分类问题中。 ![1765878367814](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765878367814.png) #### 线性 SVM ##### 硬间隔分类器 对于线性的 SVM，优化目标是最大化间隔 (margin)，同时确保所有的数据点都被正确分类。基于这个目的，我们需要先定义一下一个数据点到超平面的距离 ![1765878939817](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765878939817.png) 现有一个数据 $x^i$。如果它在超平面上，则很明显，距离是 $\mathrm{dis}^i=0$。 如果这个点不在超平面上，则距离的计算公式为： $$ \begin{aligned} \mathrm{dis}^i &= \frac{\max(0, |w^T x^i+b|)}{||w||}\\ ||w|| &= \sqrt{w_1^2 + \dots + w_d^2} \end{aligned} $$ > 喜报：这个公式是 Optional 的，不用背 --- 对于一个数据集 $D=\{(x^1,y^1),\dots,(x^n,y^n)\}$，其中每个数据点是 $(x^i,y^i)$，$x^i$ 是特征向量，$y^i \in \{-1,1\}$ 是对应的标签。那么，SVM 的间隔的大小就是这个数据集中所有的数据点到超平面的距离的最小值： $$ m(w,b) = \min_{1\leq i \leq n} \mathrm{dis}^i $$ 这就把 SVM 的训练过程转化成了一个优化问题，找到一个 $(w,b)$，使得间隔 $m(w,b)$ 最大化，同时满足所有的数据点都被正确分类。 ![1765879153449](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765879153449.png) --- 通常，进行 SVM 训练的过程是： 1. 定义直线 $wx+b=0$, 认为有 $wx^i + b \leq -1$ 时，$x^i$ 属于类别 A；有 $wx^i + b \geq 1$ 时，$x^i$ 属于类别 B。 2. 找到直线 $wx+b=-1$，这条直线经过某个类别 A 的数据点，同时正确分类的所有样本。之后，找到和它平行的直线 $wx+b=1$，这条直线经过某个类别 B 的数据点，同时正确分类的所有样本。 这两条直线之间的间隔是 $d = \frac{2}{||w||}$。 ![1765883639715](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765883639715.png) 然后，这个训练过程就等效于这个优化问题，接下来的训练就等同于求解这个优化问题： $$ \begin{aligned} \min_{w,b} \quad & \frac{1}{2} ||w||^2 \\ \text{s.t.} \quad & y^i (w^T x^i + b) \geq 1, \quad i=1,2,\dots,n \end{aligned} $$ 3. 寻找不同的 $w$ 和 $b$，使得间隔 $d$ 最大化，同时满足所有的数据点都被正确分类。通常的方法有二次规划和梯度下降等方法 4. 最终找到一条最佳直线 $wx+b=0$，作为分类的决策边界。 ![1765883761557](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765883761557.png) 因为这个训练过程是依赖于数据点的标签的，所以 SVM 属于监督学习算法。 > 一个常见的数据集是 Iris 数据集，它包含了三种不同类型的鸢尾花 (Iris flower) 的数据。这是用这个数据集训练的通过 Sepal Length 和 Sepal Width 来区分 Iris Setosa 和 Iris Versicolor 的 SVM 分类器的例子： > > ![1765884004807](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765884004807.png) > > ![1765884009102](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765884009102.png) ##### 软间隔分类器 通常大多数数据集并没有那么完美的数据，会有几个极端值 (Outliers)，这些极端值会影响到超平面的选择，导致分类器的性能下降。软间隔分类器就是来解决这个问题的。它允许错误分类，用给予惩罚来处理错误分类的数据点。它的目标是在最大化间隔和最小化错误分类之间找到一个平衡。 对于可以完全分离的数据集，只有一种支持向量，位于间隔边界上；但是对于无法完全分离的数据集，一共有三种可能的支持向量： 1. 在间隔边界上 2. 在间隔边界里，但是是在正确的一边 3. 在错误的一边 ![1765884335139](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765884335139.png) 软间隔分类器的解决方法是引入一个松弛变量 (Slack Variable)，在优化问题内允许违反间隔边界和错误分类。其原本的训练过程的优化问题是 $$ \begin{aligned} \min_{w,b} \quad & \frac{1}{2} ||w||^2 \\ \text{s.t.} \quad & y^i (w^T x^i + b) \geq 1, \\ & i=1,2,\dots,n \end{aligned} $$ 在引入后变成了 $$ \begin{aligned} \min_{w,b,\zeta}\quad & \frac{1}{2} ||w||^2 + C\sum_{i=1}^n \zeta^i \\ \mathrm{s.t.} \quad & y^i(w^Tx^i+b)\geq 1-\zeta^i, \\ & \zeta^i \geq 0 \\ & i = 1, \dots, n \end{aligned} $$ 其中， $C$ 是惩罚参数，控制着间隔的大小和错误分类的权衡。$\zeta^i$ 是松弛变量，表示第 $i$ 个数据点违反间隔边界的程度。整个 $C\sum_{i=1}^n \zeta^i$ 项表示所有违反间隔边界的数据点的总惩罚。 $C$ 是一个超参数，用来控制是更关注于得到一个更大的间隔，还是更少的错误分类。较大的 $C$ 值会导致模型更关注于减少错误分类，而较小的 $C$ 值则会导致模型更关注于最大化间隔。 --- > **喜报：以下内容为 Optional** > > 上面和下面的更详细的得出过程： > > 之前提到的带松弛变量的优化问题可以通过解决它的对偶问题来解决，原问题和对偶问题是等价的: $$ \begin{aligned} \min_\alpha \quad &\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n a^i a^j y^i y^j (x^i \cdot x^j) - \sum_{i=1}^n a^i \\ \text{s.t.} \quad & \sum_{i=1}^n a^i y^i = 0 \\ & 0 \leq a^i \leq C \\ & i = 1, \dots, n \end{aligned} $$ 这里的 $a$ 是对偶变量 (dual variable)。这个优化问题有 n 个变量，而原来的优化问题有 $n + d + 1$ 个变量 (其中 $d$ 是特征的维度，$n$ 是样本数量)。因此，对偶问题通常更易于求解。 对于对偶问题，每个变量的范围都是一个固定的区间 (box constraint)，这使得使用诸如序列最小优化 (Sequential Minimal Optimization, SMO) 之类的算法来求解对偶问题变得更加容易。 ![1765885518402](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765885518402.png) > 这里略过点乘的定义，这个不是 optional： > > $(x^i \cdot x^j) = (x^i)^T x^j = \sum_{k=1}^d x_k^i x_k^j$ --- 类似的，用老熟人 Iris 数据集来演示软间隔分类器的效果： ![1765885543379](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765885543379.png) 更小的 $C$ 值允许更多的错误分类，从而得到一个更宽的间隔。更大的 $C$ 值则会减少错误分类，但可能会导致间隔变窄。当 $C\to \infty$，则回归到硬间隔分类器。 #### 非线性 SVM ##### 核方法 线性 SVM 的限制是只能处理可以或者近似可以线性分割的数据集，但是对于非线性分布的数据分类就很难解决了，比如下图 ![1765885653202](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765885653202.png) 这个时候，需要用到核方法 (kernel trick)。核方法的核心是核 (kernel)，或者说核函数。核函数是一类将数据映射成需要的形式的函数，通常是把数据映射到更高维度的空间中，让数据呈现出线性可分的形式，之后数据就可以使用线性 SVM 来进行分类了。 核函数将输入空间 (input space) 映射到特征空间 (feature space)。输入空间指的是原始的数据空间，而特征空间则是通过核函数映射后的高维空间。比如下图，一维线上的点的分布经过了核函数后变成了二维平面上的点的分布，同时出现了线性可分的特征： ![1765885850566](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765885850566.png) 类似的，从二维映射到三维 ![1765885880299](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765885880299.png) ##### 非线性的优化 回到我们熟悉的对偶优化问题： $$ \begin{aligned} \min_a \quad &\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n a^i a^j y^i y^j (x^i \cdot x^j) - \sum_{i=1}^n a^i \\ \text{s.t.} \quad & \sum_{i=1}^n a^i y^i = 0 \\ & 0 \leq a^i \leq C \\ & i = 1, \dots, n \end{aligned} $$ 根据上面的思想，我们知道其实就是把输入套一层映射。具体而言，是这样： $$ \begin{aligned} x^i & \rightarrow \Phi(x^i)\\ x^j & \rightarrow \Phi(x^j)\\ (x^i \cdot x^j) & \rightarrow \Phi(x^i) \cdot \Phi(x^j) \end{aligned} $$ 这里的 $\Phi$ 就是映射函数。比如说可以是这样的映射 $$ [x_1, x_2] \xrightarrow{,\Phi} [x_1^2, \sqrt{2}x_1x_2, x_2^2] $$ 所以这个优化问题就成了： $$ \begin{aligned} \min_\alpha \quad &\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n a^i a^j y^i y^j (\Phi(x^i) \cdot \Phi(x^j)) - \sum_{i=1}^n a^i \\ \text{s.t.} \quad & \sum_{i=1}^n a^i y^i = 0 \\ & 0 \leq a^i \leq C \\ & i = 1, \dots, n \end{aligned} $$ 这样的计算的话，需要把每个数据点都经过一次 $\Phi$ 映射，计算量会非常大，然后每个 $\Phi(x^i) \cdot \Phi(x^j)$ 也需要计算，而输出空间的维度数目通常远大于输入空间，所以整个过程非常耗费时间和内存，显然需要优化。 上述方案的问题在于，显式的计算 $\Phi(x^i)$ 和 $\Phi(x^j)$ 以及它们的点积是非常低效的。可以使用核技巧 (kernel trick) 来避免显式地计算映射后的向量： - 不显式定义 $\Phi$ - 不显式的计算点积 - 只需要定义核函数 $k(x^i, x^j)$ 这里，核函数输入参数是两个数据点，输出内容是他们特征空间映射后的点积，也就是 $\Phi(x^i) \cdot \Phi(x^j)$。进而简化计算。比如说对于之前我们提到的映射，可以等效为: $$ k(x^i, x^j) = (x^i \cdot x^j)^2 = (x^i_1 x^j_1 + x^i_2 x^j_2)^2 $$ ##### 核函数 常用的核有: - 线性核函数 (Linear Kernel): $$ k(x,z) = x^T z $$ - 二次核函数 (Quadratic Kernel): $$ k(x,z) = (x^T z)^2 $$ - 多项式核函数 (Polynomial Kernel): $$ \begin{aligned} & k(x,z) = (x^T z )^q\\ \mathrm{or} \quad & k(x,z) = (x^T z + 1)^q \end{aligned} $$ - 径向基函数核 (Radial Basis Function, RBF Kernel) $$ k(x,z) = \exp(-\gamma ||x-z||^2) $$ - 高斯核函数 (Gaussian Kernel): $$ k(x,z) = \exp\left(-\frac{||x-z||^2}{2\sigma^2}\right) $$ 那么突然收获了这么多看不懂的核函数，该怎么选择核函数进行训练呢？ - 首先，要基于问题的特性以及数据的规律来选择核函数 - 线性核函数更多的被用于文字分类问题，在较大的数据集上表现良好 - 高斯核函数在数据没有额外信息的情况下有较好的结果 - 不确定的话使用[交叉验证](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture8.html#交叉验证) (Cross Validation) 来选择核函数 --- 交叉验证，之前提到过，就是先把数据集分成多个小块，每次用其中一块作为验证集，其他块作为训练集，训练模型，然后在验证集上测试模型的性能。重复这个过程多次，最后把所有的测试结果平均起来，得到一个更稳定的性能评估。 ![1765887798233](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765887798233.png) 这里的方式类似，使用不同的核函数进行训练，然后在验证集上测试模型的性能。 常用的核函数主要是线性、高斯和 RBF，这三种，也就是选用这三种进行三次交叉训练。对于一个 K 折交叉验证，每个核函数得到了 $k$ 个预测准确率，计算均值，然后通过均值来选择核函数。 ![1765887972499](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765887972499.png) #### 多类型 SVM 众所周知，SVM 是一个二分类的分类器，不原生支持多个种类的分类，但是有很多问题都是多分类问题，比如声音识别和手写数字识别等等。所以，需要在现有的 SVM 上搭建一些扩展来实现多分类的功能。 一种扩展的方法是把多分类问题拆分成多个二分类问题来解决。常用的方法有两种： - 一对一 (One-vs-One)，找出分割一个种类和另一个种类的分类器。 - 一对多 (One-vs-Rest)，找出分割一个种类和其他所有种类的分类器。 ![1765888113514](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765888113514.png) ##### 一对多 对于一个一共要划分 $N$ 个种类的问题，一对多的方法需要训练出 $N$ 个 SVM 分类器出来，分别对应区分是某个种类和不是某个种类。 对于一个新的样本的预测，先通过训练出来的 SVM 来进行分类，然后找到这个点在正类区域 (Positive Region)，也就是被认为是某个种类中的距离分类器最远的那个类别，作为最终的预测结果。 比如下图，数据点同时被认为可能是蓝色和绿色，但是因为距离蓝色的分类器更远，所以最终被预测为蓝色。红色因为是负类区域，所以不会被考虑。 ![1765888411764](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765888411764.png) ##### 一对一 对于一个一共要划分 $N$ 个种类的问题，一对一的方法需要训练出 $\frac{N(N-1)}{2}$ 个 SVM 分类器出来，分别对应区分某两个种类。很明显，需要训练的分类器数量可能会更多。 每个分类器的作用是区分某两个种类的数据点。 对于一个新的数据点的预测，首先先将点带入所有的分类器中，得到每个分类器的预测结果。之后，将这些分类器的结果进行投票，计算出得票数量最高的类别，作为最终的预测结果。 ![1765888600199](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture10.assets/1765888600199.png) 比如上图，三个分类器得出的结果分别是蓝色、绿色、蓝色，所以最终的预测结果是蓝色。 ### Python 实现和案例 > 这里讲述的是使用 `sklearn.svm` 这个模块实现的 SVM 分类器，之后是基于 Iris 数据集的案例分析，包括硬间隔分类器和软间隔分类器的实现，以及非线性 SVM 的实现。 > > 之后是两个 SVM 的自学案例分析，这里略过。 ## 人工神经网络入门 Source: https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture11.html Repository path: lectures/Part.2/lecture11.md ### 基本概念 人工神经网络 (Artificial Neural Networks, ANN)，或者叫神经网络 (Neural Networks, NN / Neural Nets)，通常的结构是这样的： ![1765890536545](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765890536545.png) 其分为输入层(Input Layer)、隐藏层(Hidden Layer)和输出层(Output Layer)。 在[之前的 SVM 章节](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture10.html)，我们如果让 $w^T x + b = 0$ 的 $b=0$，分类器就会变成 $w^T x = 0$，也就是一个没有偏置项的线性分类器。如果其是二维的向量，那么这个分类过程就如下图 ![1765890708394](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765890708394.png) 在这个基础上，我们可以重新加上偏置 $b$，之后在输出的值上加一个非线性函数来适配更复杂的数据，也可以加入更多的神经元。 ![1765892387271](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892387271.png) 这就是人工神经网络的基本架构。它通常的用途是分类和回归，分别适配离散和连续的范围的任务。 也有一些更复杂的神经网络结构，适配更复杂的任务 - 卷积神经网络 (Convolutional Neural Nets, CNN)，适用于图片识别或者人脸识别 - 循环神经网络 (Recurrent Neural Nets, RNN)，适用于股市预测 - Transformer，适用于自然语言处理 (NLP)，如 ChatGPT 在这个课程中我们主要关注基础的神经网络，如多层感知机 (Multilayer Perceptron, MLP)。 多层感知记的结构如下图所示： ![1765892719582](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892719582.png) - 从输入层接入输入 - 把输入和提取到的特征传递到隐藏层 - 在输出层输出结果 图中是一个训练用来分类的 MLP，识别出了图片的内容是狗。 ### 神经网络结构 神经网络的结构主要是这么几个要素： - 输入层 - 隐藏层 - 输出层 - 层与层之间的连接 ![1765892872879](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892872879.png) 这几个要素决定了神经网络的结构和数据流向，输入数据根据结构在不同的神经元之间传递 --- 每个神经元的结构是有三部分： - 权重 (Weights) - 偏置 (Bias) - 激活函数 (Activation Function) 也就是说，计算后的结果会经过一个激活函数。激活函数的特性是 **非线性的**，常用的激活函数有： - Sigmoid 函数： $$ \sigma(x) = \frac{1}{1 + e^{-x}} $$ ![1765892949512](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892949512.png) - 双曲正切函数 (Tanh)： $$ \tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}} $$ ![1765892956676](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892956676.png) - ReLU 函数 (Rectified Linear Unit)： $$ \text{ReLU}(x) = \max(0, x) $$ ![1765892961358](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765892961358.png) > 这些激活函数都是非线性的。非线性的必要性在于，如果神经网络的每一层都是线性的，那么无论有多少层，最终的输出仍然是输入的线性组合，无法捕捉复杂的模式和关系。通过引入非线性激活函数，神经网络能够学习和表示复杂的非线性关系，从而更好地适应各种任务。 数据在一个神经元中的计算过程实际上是: $$ \mathrm{Output} = \text{Activation Function}(w^T x + b) $$ ### 模型训练 #### 正向传播 (Forward Propagation) 正向传播过程指的是数据从输入层经过隐藏层传递到输出层的过程。在这个过程中，每个神经元会根据输入数据和其权重、偏置进行计算，并通过激活函数生成输出。 换句话说，正向传播过程是模型进行预测的过程。 ![1765893178116](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765893178116.png) 这里使用的非线性激活函数是 $sigmoid$ 函数，计算过程如下： $$ \sigma(x) = \frac{1}{1 + e^{-x}} $$ 以隐藏层第一个神经元为例子，其值的大小为： $$ \begin{aligned} h_1 & = (1+\exp(-0.35\times 0.1 - 0.9 \times 0.8))^{-1} \\ & = \frac{1}{1+ e^{-0.755}} \approx 0.68 \end{aligned} $$ #### 反向传播 (Backward Propagation) ##### 损失函数 (Loss Function) 为了模型训练，我们需要衡量现有神经元预测到结果是否正确。比如对于下图中的神经元，在这个输入下的期望值为 1，但是输出的值是 $o_1 = 0.579$，那么我们就需要调整神经元的权重和偏置，使得输出更接近期望值。 ![1765893305093](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765893305093.png) 首先，需要量化输出值和期望值之间的差距。常用计算方法为: - 均绝对误差 (Mean Absolute Error, MAE)： $$ E = \frac{1}{n} \sum_{n} |o_i - t| $$ - 均方误差 (Mean Squared Error, MSE)： $$ E = \frac{1}{n} \sum_{n} (o_i - t)^2 $$ - 根均方误差 (Root Mean Squared Error, RMSE)： $$ E = \sqrt{\frac{1}{n} \sum_{n} (o_i - t)^2} $$ 计算得到的误差值，我们称之为损失 (Loss) 。得到损失的函数，称之为损失函数 (Loss Function) ，通常也叫做错误函数 (Error Function) 或者代价函数 (Cost Function) 。 --- 接下来，回到我们之前的正向传播过程： ![1765893572607](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765893572607.png) 根据模型在输入下输出的结果和预期的结果的差异，我们计算出了模型的损失值。 > 这里把均方误差乘上了系数 $\frac{1}{2}$，是为了在后续计算梯度时，能够简化导数的表达式。 ##### 梯度下降 ![1765893680335](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765893680335.png) 对于一个函数上的点，其向任意方向移动，其中函数值下降速度最快的方向一定是该点的梯度的反方向。借用这个原理，我们找到损失函数梯度的反方向，就能以最高的速度降低损失值。 通常，每一步对于决策变量的更新量需要手动确定，由参数学习率 (Learning Rate) 控制。学习率决定了每次更新的步长大小。步长大小的计算公式为： $$ \Delta w = - \eta \frac{\partial E(w)}{\partial w} $$ --- ![1765894096519](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765894096519.png) 还是回到反向传播过程，我们已经得到了输出的损失值的大小，接下来需要更新输出层的参数，比如 $w_5$，首先要确定 $w_5$ 对损失值的影响程度，即计算损失函数对 $w_5$ 的偏导数： $$ \frac{\partial E}{\partial w_5} = \frac{\partial E}{\partial o_1} \cdot \frac{\partial o_1}{\partial io_1} \cdot \frac{\partial io_1}{\partial w_5} $$ 这里的 $io_n$ 是第 $n$ 个输出到输出层的神经元的值。使用链式法则展开这个偏导数之后，每个部分都可以单独计算： $$ \begin{aligned} \frac{\partial E}{\partial o_1} & = o_1 - \mathrm{target} \\ \frac{\partial o_1}{\partial io_1} & = o_1(1-o_1)\\ \frac{\partial io_1}{\partial w_5} & = h_1 \end{aligned} $$ > 这里使用了 sigmoid 函数的导数性质 $\sigma'(x) = \sigma(x)(1-\sigma(x))$ 。 > > 这个性质在平移后也适用，即对于任意的 $a$，都有 $\frac{d}{dx} \sigma(x+a) = \sigma(x+a)(1-\sigma(x+a))$ 。 其中的参数都在正向传播过程中被运算过了，带入后计算出偏导数的值，之后就可以使用梯度下降法更新 $w_5$ 的值： $$ w_5 = w_5 - \Delta w_t = w_5 - \eta \frac{\partial E}{\partial w_5} $$ 类似的，可以给每个权重参数 $w_n$ 都进行一次梯度下降运算，完成一次反向传播过程。其中，越接近输入层的权重参数，计算偏导数时需要经过更多的链式法则展开，比如 $w_1$ 的偏导数为： $$ \frac{\partial E}{\partial w_1} = \frac{\partial E}{\partial o_1} \cdot \frac{\partial o_1}{\partial io_1} \cdot \frac{\partial io_1}{\partial h_1} \cdot \frac{\partial h_1}{\partial ih_1} \cdot \frac{\partial ih_1}{\partial w_1} $$ 这里的 $ih_n$ 是第 $n$ 个隐藏层神经元的输入值。可以发现，这里有些偏导数的中间值在更新更接近输出层的权重参数时已经计算过了，可以进行缓存以提高计算效率。 之后，更新所有参数，可以发现损失值下降，输出值更接近预测值。重复这个过程，直到损失值足够小，模型训练完成。 #### 更多训练方法 ##### 批次梯度下降 (Batch Gradient Descent) 通常，我们把一次训练中用来训练的样本数量称为批次大小 (Batch Size) 。根据批次大小的不同，训练方法可以分为以下几种： - 单样本梯度下降 (Stochastic Gradient Descent, SGD)：每次只使用一个样本进行训练，更新参数。 - 小批次梯度下降 (Mini-batch Gradient Descent, MBGD)：每次使用一个小批次的样本进行训练，更新参数。 - 批量梯度下降 (Batch Gradient Descent, BGD)：每次使用所有样本进行训练，更新参数。 考虑到效率和效果的平衡，MBGD 是最常用的训练方法。 通常，MBGD 的批次大小 $M$ 是一个固定的数量，需要提前设定，是一个超参数 (Hyperparameter) 。当 $M=1$ 时，MBGD 退化为 SGD；当 $M=N$ （$N$ 为样本总数）时，MBGD 退化为 BGD。其在训练前需要慎重考虑，较大会类似于 BGD，训练时间较长，但收敛效果较好；较小则类似于 SGD，训练时间较短，但收敛效果不稳定。推荐的默认值是 $32$。 其训练过程为： - 将数据集分为多个小批次 - 从训练集中的小批次中取出一个小批次 - 使用该小批次的数据进行正向传播，计算损失值 - 使用该小批次的数据进行反向传播，更新参数 - 重复上述过程，直到所有小批次都被使用过，完成一个训练周期 (epoch) 训练周期 (epoch) 指的是使用完整个训练集进行一次训练的过程。通常需要多个训练周期才能让模型收敛。 和 BGD, SGD 相比，MBGD 具有以下优点： - 可以在一定程度上避免局部最小值 - 更节省内存占用 - 训练速度更快，收敛更快 ##### 优化器 (Optimizer) 在 GD 的过程中，学习率是恒定且不变的，但是在实际过程中，单一的学习率可能无法适配所有的参数更新需求。参数远离最优解时，较大的学习率可以加快收敛速度；参数接近最优解时，较小的学习率可以避免震荡。因此，优化器 (Optimizer) 被引入来动态调整学习率。 ![1765901488727](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765901488727.png) 常用的有 Adam 优化器 (Adam Optimizer)，它通过梯度的一阶矩估计和二阶矩估计来动态调整学习率，从而提高训练效率和效果。成效显著。 ### 模型训练的困难 #### 梯度消失和梯度爆炸 当某一层距离输出层过于远的时候，可能会出现梯度消失 (Vanishing Gradient) ，也就是梯度值变得非常小，导致参数更新缓慢，训练过程变得非常困难。在训练的过程中，还可能会出现梯度值过大，导致参数更新过度，训练过程不稳定的情况，这被称为梯度爆炸 (Exploding Gradient) 。 解决这些问题的方法有： - **权重初始化（Weight initialization）**：合理初始化权重可以避免初始梯度过小或过大，常用方法有 Xavier/Glorot 和 He 初始化。 - **梯度裁剪（Gradient clipping）**：当梯度过大导致梯度爆炸时，裁剪梯度可以限制更新步长，保持训练稳定。 - **激活函数（Activation function）**：选择合适的激活函数（如 ReLU、Leaky ReLU、ELU）有助于缓解梯度消失问题。 - **批量归一化（Batch normalization）**：对层输入做归一化可以加速收敛并减少内部协变量偏移。 - **跳跃连接（Skip / Residual connection）**：通过短路连接改善梯度传递，使深层网络更易训练（例如 ResNet）。 - **学习率与调度（Learning rate / Scheduler）**：合理设置学习率并采用学习率衰减或自适应优化器（如 Adam）能提高收敛稳定性。 #### 欠拟合和过拟合 > 英国知名主播 Vedal 解释什么是过拟合.mp4: > > ![1765903268732](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765903268732.png) 欠拟合 (Underfitting) 指的是模型没能成功的学习到训练集中的数据的模式，最终没能成功的在训练集上取得好的效果。过拟合 (Overfitting) 指的是模型过于专注于训练集中的微小模式，最终在训练集上取得了很好的效果，但是在测试集上表现很差。 在损失函数上，其表现为: | | 过拟合 | 拟合良好 | 欠拟合 | | ---------- | ------ | -------- | ------ | | 测试集损失 | 高 | 低 | 高 | | 训练集损失 | 低 | 低 | 高 | #### 解决欠拟合 欠拟合通常是因为模型过于简单，无法捕捉数据中的复杂模式。导致欠拟合的原因可能是： - 训练集多样性不足 - 解决方法时增加训练数据量，更能反映大部分样本 - 特征稀缺或不相关 - 解决方法是进行数据处理和特征选择，提取更多有用的特征 - 不合适的超参数设置 - 解决方法是调整模型的超参数，如增加隐藏层数量、增加神经元数量、调整学习率等 - 训练迭代数不足 - 解决方法是增加训练周期数，让模型有更多机会学习数据中的模式 - 模型复杂度不足 - 解决方法是使用更复杂的模型结构，如增加隐藏层或神经元数量 #### 解决过拟合 过拟合通常是因为： - 训练集样本量不足 - 解决方法是增加训练数据量，或者使用数据增强技术 - 不平衡的数据 - 对不平衡的数据进行加权决策 - 数据泄露 - 确保训练集和测试集之间没有数据泄露 - 不合理的超参数设置 - 解决方法是调整模型的超参数，如减少隐藏层数量、减少神经元数量、调整学习率等 - 缺少正则化 (Regularization) - 解决方法是使用正则化技术，如 L1 正则化、L2 正则化、Dropout 等 - 模型复杂度过高 - 解决方法是使用更简单的模型结构，或者减少隐藏层或神经元数量 ##### 正则化方法 [正则化方法](https://cateds.github.io/AI-MachineLearning.md/Part.2/lecture9.html#嵌入法-embedded-methods) (Regularization Methods) 是一种防止过拟合的有效手段，指的是在惩罚函数中加入对模型复杂度的惩罚项，从而限制模型的复杂度，防止过拟合。 $$ \min_f \sum_i E(f(x_i), y_i) + \lambda R(f) $$ 其中，$E(f(x_i), y_i)$ 是损失函数，$R(f)$ 是正则化项，$\lambda$ 是正则化参数。 过拟合的原因是模型在训练过程中直接记住了训练数据的噪声和细节，而不是学习到数据的潜在模式。通过正则化，可以限制模型的复杂度，使其更关注数据的整体趋势，而不是个别样本的细节，从而提高模型的泛化能力。 ![1765903942704](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765903942704.png) ###### L1 正则化 L1 正则化 (L1 Regularization) 通过在损失函数中加入权重的绝对值之和作为惩罚项，鼓励模型产生稀疏的权重矩阵，从而减少过拟合。L1 正则化又称为 Lasso 回归 (Lasso Regression)。 对于 L1 正则化，惩罚项定义为： $$ R(f) = \sum_{j} |\beta_j| $$ 这里的 $\beta_j$ 是模型的权重参数。 ![1765904158294](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765904158294.png) 红色的线是损失函数的等高线，图中的 $\hat{\beta}$ 是没有正则化时的最优解，而绿色的菱形是 L1 约束的可行域。最终得到的最优解是登高下拟合绿色菱形的交点，此处落在了总坐标轴上，导致了系数 $\beta_1$ 直接变成了 0。这就是 L1 正则化导致稀疏解的原因。 ###### L2 正则化 类似的，还有 L2 正则化 (L2 Regularization)，通过在损失函数中加入权重的平方和作为惩罚项，鼓励模型产生较小的权重值，从而减少过拟合。L2 正则化又称为 Ridge 回归 (Ridge Regression)。 $$ R(f) = \sum_{j} \beta_j^2 $$ ![1765904671992](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765904671992.png) 绿色的圆形是 L2 约束的可行域。最终得到的最优解是登高下拟合绿色圆形的交点，此处落在了圆形上。最终的效果是，L2 正则化会把 $\beta$ 均匀的向 0 压缩，进而最小化过拟合 ##### 训练-验证-测试集划分 之前，对于数据集的划分，我们提到过训练集 (Training Set) 和测试集 (Test Set) 。实际上，通常还会划分出验证集 (Validation Set) 。 ![1765904846517](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765904846517.png) 新的划分是按照随机取样的方式划分出训练集、验证集、测试集。训练集用于训练模型参数，验证集用于在训练的时候评估模型的表现，最终训练完成后，在测试集上评估模型的泛化能力。常见的划分比例有 - $8:1:1$ - $7:1.5:1.5$ - $6:2:2$ - $7:2:1$ - $\dots$ 如果在训练过程中，验证的误差保持不变或者开始上升，那么说明模型开始过拟合了，可以停止训练。 ###### 过拟合-训练曲线 ![1765905155074](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Part.2/lecture11.assets/1765905155074.png) 图中的是训练误差和验证误差随训练周期变化的曲线。当训练误差和验证误差都较高时，说明模型欠拟合；当训练误差较低而验证误差较高时，说明模型过拟合。 可以发现，训练集的误差随着训练周期的增加而不断下降，而验证集的误差在开始时下降，之后开始上升。这是因为模型在训练集上学习到了更多的模式，而这些模式并不适用于验证集，导致验证误差上升。选择在验证误差最低时的模型参数，可以获得较好的泛化能力。 ### 使用 Python 实现 ANN > 竟然是用 `sklearn` 和 `tersorflow` 写，太学院派了 > > 包含两个样例，一个是从飞机的一系列参数推算声压级，一个是糖尿病诊断预测，这里就不放了 ## Lecture 01 - Introduction to AI Source: https://cateds.github.io/AI-MachineLearning.md/Addon/Introduction/introduction.html Repository path: lectures/Addon/Introduction/introduction.md ### 1. Exam Focus（真题对齐） - High-frequency (A 档)： - 2022-2023 Q1(a): Relationship between AI and Machine Learning (subset / interchangeable / unrelated / AI ⊂ EC trap) - Medium (B 档)： - Definition-style questions (often used as MCQ/short answer): - What is intelligence? (keywords: learn/adapt/problem-solve) - What is AI? (simulate/extend/enhance intelligence) - Low (C 档)： - AI history timeline / AI winter / expert systems / deep learning milestones (background knowledge, rarely a direct scoring point) - AI applications examples (only for “give 1-2 examples” type questions) - Scoring checklist： - [ ] Can instantly pick “ML ⊂ AI” in MCQ and reject traps (“AI=ML”, “AI ⊂ ML”, “AI ⊂ EC”, “AI and ML unrelated”) - [ ] Can write 3 keywords for intelligence (learn/adapt/problem-solving) in bullet form - [ ] Can write 1-sentence AI definition (simulate/extend/enhance intelligence) - [ ] Can state: EC and ML are approaches/branches within AI, not the superset ### 2. Key Concepts（知识点） #### A 档（必会） - AI vs ML relationship (exam MCQ trap-proof) - Correct: Machine Learning is a subset of AI - Incorrect traps: - AI and ML are unrelated - AI and ML are interchangeable - AI is a subset of ML - AI is a subset of evolutionary computation #### B 档（可能考） - What is Intelligence? (write 3 bullets) - Cognitive abilities (learn from experience + apply to new situations) - Adaptation (adjust strategies in different contexts) - Problem-solving (analyze → generate solutions → evaluate → implement) - Definition of AI (1 sentence) - AI studies and develops theories/methods/technologies/systems for simulating, extending, and enhancing intelligence. #### C 档（不太可能考） - AI timeline / AI winter / expert systems / deep learning milestones (know only “one-line summary”) - AI applications (be able to give 1–2 examples) ### 3. Must-know Formulas / Algorithms（公式/算法模板） > This lecture has no required formulas. Use these answer templates: - Template A (MCQ / True-False: AI vs ML relationship) 1. Identify the statement type: subset / interchangeable / unrelated 2. Use the rule: AI is the broader field; ML is one approach inside AI 3. Choose: “ML is a subset of AI” 4. Reject traps: “AI=ML”, “AI ⊂ ML”, “AI ⊂ EC”, “unrelated” - Template B (Short answer: define intelligence) - Write 3 bullets: learn / adapt / problem-solving - Each bullet: 1 short phrase (no long story) - Template C (Short answer: define AI) - One sentence: simulate + extend + enhance intelligence ### 4. Worked Examples（例题与解答） #### A1. AI vs ML relationship ##### Problem 1 (MCQ-style) Which statement is correct? A. ML is a subset of AI B. AI and ML are unrelated C. AI and ML are interchangeable D. AI is a subset of ML E. AI is a subset of evolutionary computation **Solution** : - AI is a broad field aiming to build intelligent behavior. - ML is one approach inside AI (learning from data). - Therefore ML ⊂ AI. - All other statements contradict the subset relationship or invert it. **Final Answer** : A ##### Problem 2 (True/False) (1) AI is a subset of machine learning. (2) Evolutionary computation is one approach within AI. (3) AI and machine learning are interchangeable. **Solution** : (1) False. The subset direction is reversed. ML ⊂ AI. (2) True. EC is an approach used in AI for optimization/search. (3) False. ML is only a part of AI. **Final Answer** (1) × (2) ✓ (3) × #### B1. Definitions **Problem** Answer in ≤4 sentences: (1) What is intelligence? (≥3 keywords) (2) What is AI? (1 sentence) **Solution** (1) Intelligence: learn from experience, adapt strategies to context, and solve problems (analyze → generate → evaluate → implement). (2) AI: studies and develops theories/methods/technologies/systems for simulating, extending, and enhancing intelligence. **Final Answer** Use the two lines above. ### 5. Common Mistakes（易错点） (ordered by importance) 1. Treating “AI = ML” as correct. 2. Picking “AI is a subset of ML” by reversing the subset direction. 3. Falling for the trap “AI is a subset of evolutionary computation”. 4. Writing definition answers with no keywords (e.g., “intelligence is being smart”). 5. Writing AI definition as “AI is machine learning”. 6. Giving long history stories instead of scoring points (keywords + structure). 7. Not using bullet points in definition questions (hard to award keyword marks). 8. Mixing up “approach/branch within AI” vs “superset of AI”. 9. Memorizing all AI application examples instead of knowing 1–2. 10. Answering without justification when the question asks “why” (loses explanation marks). ### 6. Quick Review（考前 10 分钟速记） - One-liner: **ML is a subset of AI**. Reject: “AI=ML”, “AI ⊂ ML”, “AI ⊂ EC”, “AI and ML unrelated”. - Intelligence keywords: **learn / adapt / problem-solving**. - AI definition keywords: **simulate / extend / enhance intelligence**. - Course focus: **evolutionary computation + machine learning** (EC=optimization/search, ML=prediction/classification). ## Lecture 02 - Fundamental Concepts in Optimization Source: https://cateds.github.io/AI-MachineLearning.md/Addon/Evolutionary_Computation/lecture2.html Repository path: lectures/Addon/Evolutionary_Computation/lecture2.md ### 1. Exam Focus（真题对齐） #### High-frequency (A 档) - **Engineering problem formulation (6-step procedure)** - 2022-2023 Q2(a): formulate antenna design into an optimization problem - 2023-2024 Q1(a): list objectives (if any) and constraints (if any) for filter design - 2024-2025 Q2(a): define decision variables (how many? type? range?) for a defense optimization tool - **Objectives vs constraints; feasible/infeasible; comparing solutions (constraint violations)** - 2022-2023 Q1(d): concepts of objectives/constraints/feasible solutions - 2023-2024 Q1(a)(b): objectives/constraints + integrate them (integration handled later, but classification is from this lecture) - 2024-2025 Q1(a)(b): number of objectives/constraints; integrate constraints into a single function - **Multi-objective optimization: domination, non-dominated, PF/PS (PF = F(PS)); compare Pareto fronts** - 2022-2023 Q1(e): Pareto optimal / PS vs PF / non-dominated - 2023-2024 Q2(a)(b): choose multiobjective vs constrained single objective; compare two PFs - 2024-2025 Q2(b): compare PFs (minimization) - **Decision-variable representation (continuous / binary / permutation) + search space** - 2024-2025 Q2(a): “m or n variables?”, “continuous/binary/permutation?”, “range?” - 2023-2024 Q2(c): delivery plan solutions are permutations (representation is prerequisite) #### Medium (B 档) - **Global vs local optimum; local vs global optimization; neighborhood** - 2022-2023 Q1(b): hill climbing is local search (ties to local optimum & neighborhood) - **Unimodal vs multimodal** - 2022-2023 Q1(h): multimodal means >1 local optimum #### Low (C 档) - Engineering case study details (antenna array, network slicing, etc.) - Usually not directly examined; used as modeling examples. #### Scoring checklist（本节课拿分点清单，可直接背） - Can write the generic optimization form: variables + objective(s) + constraint(s) + search space - Can apply the **6-step procedure** to translate text specs → math model - Can correctly distinguish **objective vs constraint** - Can rank solutions: feasible（可行解） > infeasible（不可行解）; infeasible vs infeasible uses violation - Can define domination (min/max), identify non-dominated set, and explain PF/PS (+ PF=F(PS)) - Can compare two Pareto fronts using **convergence + diversity/coverage** - Can state decision-variable representation (continuous/binary/permutation) and ranges --- ### 2. Key Concepts（知识点） #### A 档（必会） ##### (A1) 6-step procedure: formulate engineering problems into optimization problems 1. Identify requirements 2. Classify requirements to objectives and constraints 3. Identify decision variables and their properties (type: continuous（连续）/binary（二项分布）/permutation（排列）/...) 4. Identify search space (ranges / feasible domain) 5. Identify if there is a starting point 6. Identify how to obtain objective and constraint values (simulation/measurement) ![1764944931945](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764944931945.png) ![1764944936860](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764944936860.png) ![1764944947277](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764944947277.png) ##### (A2) Objectives vs constraints; feasible space; comparing solutions - **Decision variables** : (X) - **Objective** : optimize (min/max) - **Constraints** : must satisfy (feasible/infeasible) - **Feasible space** : set of all solutions satisfying constraints - **Comparing solutions (PPT rule)** 1. Two feasible: compare objective 2. Feasible vs infeasible: feasible is better 3. Two infeasible: compare constraint violations (smaller violation is better) ![1764940681651](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764940681651.png) ##### (A3) Multi-objective optimization; domination; Pareto front / Pareto set - Multiobjective form: $$ \max/\min\ f_1(\mathbf{x}),\ \max/\min\ f_2(\mathbf{x}),\quad \mathbf{x}\in D $$ - Domination (example for maximization; for minimization flip the inequalities): $$ \mathbf{x}\prec \mathbf{y}\iff (\forall k,\ f_k(\mathbf{x})\ge f_k(\mathbf{y}))\ \land\ (\exists k,\ f_k(\mathbf{x})> f_k(\mathbf{y})) $$ - Pareto-optimal (non-dominated): not dominated by any other solution - Pareto set (PS): Pareto-optimal solutions in decision space - Pareto front (PF): objective vectors of PS in objective space $$ PF = F(PS) $$ ![1764942248674](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764942248674.png) ##### (A4) Decision-variable representation + search space - **Binary** : $x_i\in\{0,1\}$ (feature selection / knapsack selection) - **Permutation** : $\mathbf{p}$ is a permutation of $\{1,\dots,n\}$ (TSP/QAP) - **Continuous** : $\mathbf{x}\in\mathbb{R}^n$, each with bounds $[l_i,u_i]$ --- #### B 档（可能考） ##### (B1) Global vs local optimum; neighborhood - Global optimum (max case): $$ x^* \text{ is global optimal }\iff \forall x\in\Omega,\ f(x^*)\ge f(x) $$ - Neighborhood $\mathcal{N}(x)$: points considered "close" (definition depends on problem: Euclidean/Hamming/swap) - Local optimum: best within \(\mathcal{N}(x)\) (Old-note image preserved) ![1764943819223](https://raw.githubusercontent.com/Cateds/AI-MachineLearning.md/main/lectures/Addon/Evolutionary_Computation/lecture2.assets/1764943819223.png) ##### (B2) Unimodal vs multimodal - Unimodal: single optimum basin - Multimodal: multiple local optima (local search can get stuck) --- #### C 档（低频） - Case-study-specific domain details (antenna/network slicing/radar features): know they are _examples of modeling_, not memorization targets. --- ### 3. Must-know Formulas / Algorithms（公式/算法模板） #### 3.1 Constrained optimization template（可抄） $$ \begin{aligned} \min /\max \quad & f(\mathbf{x}) \\ \mathrm{s.t.}\quad & g_i(\mathbf{x})\ge 0, \quad i=1,\dots m;\\ & \quad h_j(\mathbf{x})=0, \quad j=1,\dots,r \\ & \mathbf{x}\in\Omega \end{aligned} $$ #### 3.2 Comparing solutions in constrained optimization（PPT rule） 1. Feasible vs feasible: compare objective value 2. Feasible vs infeasible: feasible is always better 3. Infeasible vs infeasible: compare constraint violation (smaller is better) (Optional violation scalar you can write if needed) $$ v(\mathbf{x})=\sum_i \max(0,-g_i(\mathbf{x})) $$ #### 3.3 Domination & Pareto (2-objective) - (Max case) domination: $$ \mathbf{x}\prec \mathbf{y}\iff (\forall k,\ f_k(\mathbf{x})\ge f_k(\mathbf{y}))\land(\exists k,\ f_k(\mathbf{x})> f_k(\mathbf{y})) $$ - PF/PS relation: $$ PF = F(PS) $$ #### 3.4 6-step procedure（流程编号，答题直接写） 1. Requirements list 2. Objective(s) + constraint(s) 3. Decision variables + type 4. Search space/ranges 5. Starting point? 6. How to compute objective/constraints (simulation/measurement) --- ### 4. Worked Examples（例题与解答） > Note: These are “exam-style” and aligned to past papers’ wording. #### A1 Example 1 — Filter design (formulation) **Problem** Given passband and two stopbands specs with S11(dB), formulate min problem with objective & constraints, define $\mathbf{x}\in\mathbb{R}^{12}$, search space $\Omega$, and evaluation method. **Solution** : - Variables: $\mathbf{x}=(x_1,\dots,x_{12})\in\mathbb{R}^{12}$ - Objective: $$ \min f(\mathbf{x})=\max_{f\in[4,7]}|S11(\mathbf{x},f)| $$ - Constraints: $$ \begin{aligned} & \min_{f\in[3.3,3.92]}|S11(\mathbf{x},f)|\ge -3,\\ & \min_{f\in[7.08,7.3]}|S11(\mathbf{x},f)|\ge -3 \end{aligned} $$ - Search space: $$ \mathbf{x}\in\Omega=\prod_{i=1}^{12}[l_i,u_i] $$ - Evaluation: EM simulation → extract S-parameters → take max/min over bands **Final Answer** Write the above min/s.t. + $\mathbf{x}\in\Omega$ + simulation-based evaluation. --- #### A1 Example 2 — Antenna design (formulation) **Problem** Band 1.1–1.7 GHz: require $\max|S11|\le -14$ and $\max AR\le 3$. Minimize size $S(\mathbf{x})$. **Solution** : $$ \begin{aligned} \min \quad & S(\mathbf{x})\\ \text{s.t. } \quad & \max_{band}|S11(\mathbf{x})|\le -14,\\ & \max_{band}AR(\mathbf{x})\le 3,\ \mathbf{x}\in\Omega \end{aligned} $$ **Final Answer** Objective = size; constraints = two band-max specs; $\mathbf{x}$ continuous with bounds; simulation gives curves then max over band. --- #### A2 Example 1 — Compare solutions (feasible > infeasible) **Problem** $\min f(x)=-(x-1)^2$, s.t. $g(x)=x-1.5\ge 0$. Candidates: 0.5, 1, 1.5, 2. **Solution** Compute $g(x)$: only 1.5 and 2 are feasible. Compare feasible by objective: $f(1.5)=-0.25,\ f(2)=-1\Rightarrow 2$ is best. **Final Answer** Best solution: $x=2$. --- #### A2 Example 2 — Rank by constraint violations **Problem** Min problem with $g_1,g_2\ge0$. A: $g_2<0$, B: feasible, C: both <0. Rank. **Solution** Feasible beats infeasible ⇒ B best. Among infeasible, compare violation sum $v(\mathbf{x})=\sum\max(0,-g_i)$: smaller $v$ is better ⇒ A better than C. **Final Answer** B > A > C. --- #### A3 Example 1 — Find PF (minimization) **Problem** Given several (f1,f2) points, find non-dominated set. **Solution** Use min-domination: $x\prec y$ if $f_1(x)\le f_1(y)$ and $f_2(x)\le f_2(y)$ and one strict. Remove dominated points. **Final Answer** Remaining points are PF. --- #### A3 Example 2 — Compare two PFs (8-mark style) **Problem** Two algorithms produce two PFs (min). Compare. **Solution** : - Convergence: closer to left-bottom is better - Diversity: wider coverage + more uniform spacing is better Write 3–5 sentences using these keywords. **Final Answer** A complete comment must mention both convergence and diversity/coverage. --- #### A4 Example 1 — Representation & ranges **Problem** Feature selection / TSP / network slicing: specify variable type and range. **Solution** : - Feature selection: $x_i\in\{0,1\}$ - TSP: permutation of $\{1,\dots,n\}$ - Network slicing: continuous $\beta\in[0,1]$ **Final Answer** State variable count (n), type, and range. --- #### A4 Example 2 — Swap neighborhood (permutation) **Problem** For $x=(2,3,4,1)$, list neighbors by one swap. **Solution** There are $\binom{4}{2}=6$ swaps; list all 6 resulting permutations. **Final Answer** (3,2,4,1), (4,3,2,1), (1,3,4,2), (2,4,3,1), (2,1,4,3), (2,3,1,4) --- ### 5. Common Mistakes（易错点，扣分点 ≥10，按重要性排序） 1. 把“必须满足的规格”误写成目标（却不说明多目标/不写处理方式） 2. 忘写搜索空间 $\mathbf{x}\in\Omega$ 或变量范围（缺“可优化的域”） 3. 频段指标是向量却没写“max/min over band”（缺“向量 → 标量聚合”） 4. 可行/不可行比较规则写反（应：feasible > infeasible） 5. 两个不可行解不比违约程度，反而比目标值（规则错） 6. Domination 忘了“至少一项严格更好” 7. min/max 方向搞反，导致 PF 全错 8. 把 Pareto set 当 Pareto front（PS 在决策空间，PF 在目标空间） 9. PF 比较只写“算法 2 更好”不给依据（必须写 convergence + diversity/coverage） 10. TSP/QAP 误用二进制/实数表示且不加可行性约束（表示法错误） 11. 邻域定义混乱（swap vs adjacent swap；欧氏 vs Hamming） 12. 把 multimodal 误解成“多变量/多目标”，而不是“多个局部最优” --- ### 6. Quick Review（考前 10 分钟速记） #### 6.1 必背模板（3 行写完建模） $$ \begin{aligned} \min/\max \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x})\ge0,\ \mathbf{x}\in\Omega \end{aligned} $$ - 先写：变量（个数/类型/范围） - 再写：目标（越大越好 or 越小越好 + 频段用 max/min 聚合） - 最后写：约束（必须满足的规格） #### 6.2 6-step procedure（背到能默写） 1. Requirements 2. Objective(s) + constraint(s) 3. Variables + type 4. Search space/ranges 5. Starting point? 6. Evaluation method (simulation/measurement) #### 6.3 Constrained ranking（PPT 原规则一句话） - feasible > infeasible；feasible 之间比目标；infeasible 之间比违约 #### 6.4 Pareto（两句拿满分） - domination：所有目标不差 + 至少一个更好 - PF：所有非支配点集合；PS 在决策空间，PF 在目标空间，且 $PF=F(PS)$ #### 6.5 PF 对比（8 分关键词） - **Convergence**（更靠近理想点） + **Diversity/Coverage**（覆盖更宽、更均匀、不扎堆）