Heuristic & Adversarial Search, Supervised Machine Learning

Yuze-L
  2023-10-24 17:24:26 2023-10-24 17:24:26 Created   2024-07-15 11:38:38 2024-07-15 11:38:38 Updated      3.1k Words  10 Mins  

记录时间:2023-10-24
基于鹤翔万里 的笔记补充细节而来
公式好像有些显示问题，再说吧

Lecture 3: proning, A*, MCTS

启发式搜索

  • 利用一些能够辅助算法做出决策的额外信息的搜索算法称为启发式搜索（heuristic search），或有信息搜索（informed search）
  • 提供的这些辅助信息称为启发信息
  • 启发信息通常形式化为一个关于结点的函数 ，其用于估计结点 距离达到目标还需付出多少代价，这个函数称为启发函数（heuristic function）
    • 启发函数通常是非负的
    • 常见用法是用来更改前面的 pick_from 函数来规定挑选结点的顺序
  • 对于任意结点 ，决定了搜索算法扩展结点 的优先度的函数 称为评价函数（evaluation function）
    • 评价函数值越小，被挑选的优先级越高
    • 深度优先搜索中 可被定义为该结点深度的倒数
    • 广度优先搜索中 可被定义为该结点深度
  • 贪婪最佳优先搜索
    • 即 greedy best-first search，GBFS
    • 优先扩展距离目标近的结点，即令
    • 不排除环路的贪婪最佳优先搜索算法是不完备的
    • 排除环路的贪婪最佳优先搜索是完备的，但不一定最优
    • 最坏情况下的时间复杂度和空间复杂度均为
      • 为分支因子（每个结点最大的分支数目）
      • 为最大深度，也就是搜索树中路径的最大可能长度
  • 智能体不唯一，解决信息确定、全局可观察、轮流行动、输赢收益零和的博弈问题，求解这样问题的算法称为对抗搜索（adversarial search）或博弈搜索（game search）
  • 智能体会选择最大化自身利益、最小化对手利益的策略
  • 形式化描述：
    • 状态：状态 包括当前游戏局面和当前行动的智能体，初始状态 为游戏开始时的状态。 表示状态 下行动的智能体
    • 动作：动作是指 在当前局面下可以采取的操作 ，记动作集合为
    • 状态转移：状态转移函数 表示在状态 下采取动作 后的下一个状态
    • 终局状态测试：终局状态测试函数 用于测试游戏是否在状态 下结束
    • 终局得分：终局得分函数 表示在状态 下玩家 的得分
      • 对于二人零和博弈，只需要记录其中一人的终局得分即可

最大最小搜索

  • 最大最小搜索（minimax search）是求解对抗搜索问题的基本算法
  • 该算法假设两名玩家在决策时总是理性地倾向于最大化自己的得分（最小化对方得分）
  • 算法过程
    • 假设以最大化得分为目标的玩家为 MAX，以最小化得分为目标的玩家为 MIN
    • 某一层由 MAX 玩家行动，则其会选择得分最大的子树进行行动
    • 某一层由 MIN 玩家行动，则其会选择得分最小的子树进行行动
    • 递归地进行上述过程，直到达到终局状态
    • （子树的得分由所有它的子树的得分取最大或最小得到）

  • 最大最小搜索的时间复杂度为 ，空间复杂度为

Alpha-Beta 剪枝

  • 如果搜索树极大，则最大最小搜索的开销巨大，无法在合理时间内返回结果

  • Alpha-Beta 剪枝算法的思想如下：

    • 上式中 肯定小于 2，而外面一层求最大值又有 3 比它大
    • 所以就没有必要去搜索 对应的子树得到具体的 值，可以将这两个动作剪枝掉

蒙特卡洛树搜索

贪心算法

→ -贪心算法(存在一定的概率使得随机尝试，但是比较没有目的性)

$$
l_t = \begin{cases} \mathrm{argmax}i\bar x{i,T_{(i,t-1)}}, &p=1-\epsilon \mathrm{random} ; i \in {1,2,…,K}， &p = \epsilon \end{cases}
$$

→ UCB1(Upper Confidence Bounds)

  • UCB1的基本思想

    • 有限探索不确定度高的动作
    • 忽略极端平均值偏低（即使不确定度高）

    → 优先采用估计范围上限较高的动作

  • 如何计算奖励期望的估计范围？

    假设算法在过去 次中，对动作 探索了 次，执行动作 的收益分数均值为 . 根据Hoeffding’s Inequality:

    这个Hoeffding’s Inequality实际上给出的是奖励期望 与 存在偏差为 的概率的上界. 那么当不等式右侧的概率足够小, 我们可以认为 是奖励期望的上限.

    → 找到一个快速趋近0的函数

  • 四个步骤

    • 选择（selection）：算法从搜索树的根节点开始，向下递归选择子节点直到到达叶子结点或者到达还具有未被扩展的子节点的节点 L，向下递归选择的过程可由 UCB1 算法来实现，在递归选择过程中记录下每个节点被选择的次数和每个节点得到的奖励均值
    • 扩展（expansion）：如果节点 L 还不是一个终止节点，则随机扩展它的一个未被扩展过的后继边缘节点 M
    • 模拟（simulation）：从节点 M 出发，模拟扩展搜索树，直到找到一个终止节点
    • 反向传播（back propagation）：用模拟所得结果回溯更新模拟路径中 M 及以上节点的奖励均值和被访问次数

Lecture 4: Machine Learning: Supervised

机器学习基本概念

  • 机器学习的目标是从原始数据中提取特征，学习一个映射函数 f 将上述特征（或原始数据）映射到语义空间，寻找数据和任务目标之间的关系
  • 机器学习种类
    • 监督学习
      • 给定带有标签信息的训练集合，学习从输入到输出的映射(从数据 和标签 中学习映射 )
      • 一般被应用在回归或分类的任务中
    • 无监督学习
      • 最大特点是数据无标签
      • 一般被应用在聚类或若干降维任务中
      • 半监督学习依赖于部分被标注的数据
    • 强化学习
      • 一种序列数据决策学习方法
      • 从与环境交互中学习，通过回报值（reward）让智能体（agent）学习到在不同状态（state）下如何选择行为方式（action）

机器学习的目标

  • 从原始数据中提取特征
  • 学习映射函数
  • 通过映射函数 将原始数据映射到语义任务空间，即寻找数据和任务目标之间的关系

监督学习中的重要元素

  • 标注数据(学什么)
  • 学习模型(怎么学)
  • 损失函数(学到否)

监督学习

  • 在训练过程中希望映射函数在训练数据集上得到所有样本的“损失和”最小 →

  • 损失函数就是在计算预测值 和真实值 之间的差异函数

  • 损失函数包括 0-1 损失函数（相等为 0，反之为 1），平方损失函数，绝对损失函数，对数损失函数（对数似然函数）

  • 监督学习一般包含三个部分内容：

    • 从训练数据集中学习得到映射函数
    • 在测试数据集上测试映射函数
    • 在未知数据集上测试映射函数 （投入使用）

  • 训练及中产生的损失一般称为经验风险（empirical risk），越小对训练集拟合效果越好

    经验风险的定义为:

  • 测试集中加入从真实数据分布采样的样本时，测试集上的损失会不断逼近期望风险（expected risk），越小模型越好

    期望风险的定义为:

  • 机器学习的目标是追求期望风险最小化, 但是经验风险最小值→无法反应全量数据, 期望风险最小值→仅反映了局部数据

  • 结构风险最小化（structural risk minimization）：防止过学习，基于过学习时参数值通常都较大这一发现，在经验风险上加上表示模型复杂度的正则化项（regularizer）或惩罚项（penalty term），在最小化经验风险与降低模型复杂度之间寻找平衡

  • 主要的监督学习方法：

    • 判别方法（discriminative approach）
      • 直接学习判别函数 或者条件概率分布 作为预测的模型
      • 关心给定数据下, 预测该数据的输出是什么
      • 典型判别模型包括回归模型、神经网络、支持向量机和 Ada boosting
    • 生成方法（generative approach）
      • 从数据中学习联合概率分布 （通过似然概率 和类概率 乘积来求）
      • 生成模型典型方法为贝叶斯方法、隐马尔可夫链
      • 难点在于联合分布概率或似然概率很难求

回归分析

一元线性回归

→ 最简单的监督学习

梯度下降

  • 梯度下降是最常见的一种函数最小化算法，不仅适用于线性回归代价函数的最小化，也广泛地应用于机器学习的众多领域，优化其他的函数。

  • 对于函数 , 求

  • 优化思路：

    • 设置一组初始的参数，作为优化的起点
    • 不断改变 ，使 减小，直到到达最小值

  • 计算原理和步骤

    Repeat Until Convergence{

    , for and

    }

    • : 学习率(控制迈步的大小)
    • : 偏导数(迈步的方向)
    • 赋值的整个过程: 迈出一步

  • 在线性回归模型中, 代价函数实际上就是

  • 在梯度下降的每一步使用整个训练集的全部样本的方法被称为批量梯度下降（Batch Gradient Descent, BGD), 每次只使用一个样本的随机梯度下降（Stochastic Gradient Descent, SGD）和每次使用一部分样本的小批量梯度下降（Mini-batch Gradient Descent, MBGD）

    • 批量梯度下降最为精确，但当训练样本数大时，训练过程将会很慢。
    • 随机梯度下降，速度最快，但相对不准确。
    • 小批量梯度下降为两者的折中，在实际应用中最为常见。

多元线性回归

  • 有 个训练数据 ${(\mathbf{x}i, y_i)}{i=1}^m其中\mathbf{x}i = [x{i,1},x_{i,2},…,x_{i,D}] \in \mathbb{R}^DD是数据特征的维度要找到参数\mathbf{a}，使线性函数f(\mathbf{x}_i)=a_0+\mathbf{a}^\intercal\mathbf{x}_i$

  • 最小化均方误差函数

    其中 ,

  • 对均方误差函数求导得 ，令其为 0 解得

逻辑回归

  • 研究某一事件发生概率与若干因素之间的关系→二分类问题

  • Logit 函数/逻辑变换

    人们通常把的某个函数假设为变量的函数形式，取

逻辑斯蒂回归/对数几率回归

  • 线性回归对离群点非常敏感，导致模型不稳定，为了缓解这个问题(尤其是在二分类场景中)可以考虑逻辑斯蒂回归（logistic regression）

  • 在回归模型中引入 sigmoid 函数，逻辑斯蒂回归模型

    因此可以表示为

    化简为

    其中 是输入数据, 和 是回归函数的参数

  • 回归系数

    • 优势比(Odds Ratio): 发生与不发生的概率之比

  • 逻辑斯蒂回归函数的输出具有概率意义，一般用于二分类问题(表示输入数据 属于正例,表示输入数据 属于反例)

  • 逻辑斯蒂回归是一个线性模型，在预测时可以计算线性函数 取值是否大于 0 来判断输入数据的类别归属

  • 求解参数的典型做法是最大化对数似然（log likelihood）函数

    • 似然函数定义为 , 假设所管测的每一个样本都是独立同分布的,那么

      取对数可以得到

      等价于

  • 最大似然估计目的是计算似然函数的最大值，而分类过程是需要损失函数最小化，常用梯度下降法（gradient descent）：批量梯度下降、随机梯度下降、小批量梯度下降

  • 只能用于解决二分类问题

  • 多分类可以将其推广为多项逻辑斯蒂回归模型，即 softmax 函数

  • Title: Heuristic & Adversarial Search, Supervised Machine Learning
  • Author: Yuze-L
  • Created at : 2023-10-24 17:24:26
  • Updated at : 2024-07-15 11:38:38
  • Link: https://yuze-l.github.io/2023/10/24/AI_INTRO-1/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
Heuristic & Adversarial Search, Supervised Machine Learning
  1. Lecture 3: proning, A*, MCTS
    1. 启发式搜索
    2. 最大最小搜索
    3. Alpha-Beta 剪枝
    4. 蒙特卡洛树搜索
  2. Lecture 4: Machine Learning: Supervised
    1. 机器学习基本概念
    2. 机器学习的目标
    3. 监督学习中的重要元素
    4. 监督学习
    5. 回归分析
      1. 一元线性回归
      2. 梯度下降
      3. 多元线性回归
    6. 逻辑回归
      1. 逻辑斯蒂回归/对数几率回归