Loading... # 2021.9.6 周记 ## 上一周的学习内容 ### 1. 计算学习理论 计算学习理论研究的是关于通过计算来进行学习的理论, 目的是分析结果指导算法设计. #### PAC学习 计算学习理论最基本的是**概率近似正确(PAC)**学习理论. PAC: 给定训练集 $D$, 希望学习的算法 $\mathcal{L}$ 学习到的模型所对应的假设 $h$ 尽可能接近目标概念 $c$. - $c$ - 表示概念(concept), 是从样本空间 $\mathcal{X}$ 到 $\mathcal{Y}$ 的映射, 决定示例 $x$ 的真实标记 $y$. 若对任意样例 $(x, y)$ 有 $c(x)=y$ 成立, $c$ 称为目标概念. - $h$ - 学习算法 $\mathcal{L}$ 所考虑所有的概念的集合称为假设空间 $\mathcal{H}$, $h \in \mathcal{H}$, 因为无法确定他是否为真的目标概念, 称为假设(hypothesis). $h$ 也是从样本空间 $\mathcal{X}$ 到 标记空间 $\mathcal{Y}$ 的映射. PAC学习中一个关键因素是假设空间 $H$ 的复杂度, $H$ 包含了学习算法 $\mathcal{L}$ 所有可能输出的假设. - 恰PAC可学习(properly PAC learnable): 学习中假设空间与概念类完全相同($\mathcal{H} = \mathcal{C}$) 恰PAC可学习是不实际的. 更重要是研究假设空间与概念类不同的情形 ($\mathcal{H} \neq \mathcal{C}$) #### 有限假设空间 - 可分情形: 可分情形意味着目标概念 $c$ 属于假设空间 $\mathcal{H}$ (i.e. $c \in \mathcal{H}$) 有限假设空间 $\mathcal{H}$ 都是可学习的, 所需样例 $m \geq \frac{1}{\epsilon}(\ln |\mathcal{H}|+\ln \frac{1}{\delta})$, 输出假设 $h$ 的泛化误差随样例数目的增多而收敛到 $0$, 收敛速率 $O(\frac{1}{m})$ - 不可分情形: 对较为困难的学习问题, 目标概念 $c$ 通常不存在与假设空间 $\mathcal{H}$ 中 (i.e. $c \not \in \mathcal{H}$) #### VC维 现实学习任务所面临的通常是无限假设空间, 需要度量假设空间的复杂度. 常见的方法是考虑假设空间的**VC维(Vapnik-Chervonenkis dimension)**. VC维: 一个假设空间 $\mathcal{H}$ 的VC维, 是这个 $\mathcal{H}$ 最多能够shatter掉的点的数量, 记为$d_{VC}(H)$. 1. 假设空间可以看作模型的复杂度 2. shatter指不管数据分布如何, $\mathcal{H}$ 都要把它区分开 3. 关注的是不管数据是怎样分布的, $\mathcal{H}$ 最多能区分多少个数据. 越是复杂的 $\mathcal{H}$ 能够区分的数据点就越多, VC维也就越大 #### Rademacher复杂度 基于VC维的泛化误差界是分布无关、数据独立的, 对任何数据分布都成立. 虽然具有普适性, 但是没有考虑到一些数据自身存在坏分布的问题. Rademacher复杂度是另一种刻画假设空间复杂度的途径. #### 稳定性 基于VC维和Rademacher复杂度所得到的结果都与具体学习算法无关. 能够使人们能够脱离具体学习算法的设计来考虑学习问题本身的性质. 如果希望获得与算法有关的分析结果则需要分析**稳定性**: 考察的是算法在输入发生变化时, 输出是否会随之发生较大的变化. ### 2. 强化学习 #### 基础概念 **强化学习(Reinforcement Learning, RL)** 讨论的问题是一个智能体(agent)怎么在一个复杂不确定的环境 (environment)里面去极大化它能获得的奖励. - **State**: 状态, 对整个世界的完整描述, 并不会隐藏信息. - **Observation**: 观测, 对状态的部分描述, 可能会存在遗漏一些信息. - **Actor**: 不明确的function, 在`让机器人自动打游戏` 这个场景中, actor指人 - **Action**: 动作, action=f(observation), 在`让机器人自动打游戏` 这个场景中, action指做出的操作 - **Reward**: 奖励, 由环境给的一个标量的反馈信号, 显示了智能体在某一步采取了某个策略的表现如何 RL依然可以视为符合传统ML框架的三个阶段, 但是模型存在随机性, 在训练过程中的优化方法有所不同. > actor, env, reward都是黑盒 #### Policy Gradient RL与传统ML分类问题的区别: 1. 当前动作会影响到之后的环境以及后续rewards; 2. Reward delay, 有时候需要牺牲短期利益换取长期收益. 训练RL有几种思路: 1. 直接用当前action在当前state下带来的reward作为label进行训练. 但这种方法无法考虑长期策略. 2. 使用cumulated reward而非仅考虑当前步骤的reward. 这种方法过多强调了早期action的重要性. 3. 在计算cumulated reward的时候不是单纯加和而是加入discount factor, 逐步减少早期action的重要性. 4. 对cumulated reward进行标准化, 比如所有值都减去一个参数b, 让最终值有正有负 - On-policy Learning: 在policy gradient的训练过程中, 需要同步收集数据, 每更新模型就需要收集一次数据. On-policy Learning模型训练十分耗时. - Off-policy Learning: 收集数据时的actor和训练中的actor不同. 经典的方法是**PPO(Proximal Policy Optimization)** #### Critic Critc: 评估actor的好坏. 有一个value function, 根据当下的情景预估可能会得到的reward. 训练critic的方法: 1. 蒙特卡洛: 直接完成整轮拿到结果, 训练vvalue function; 2. temporal-difference: 将输入第一个画面得到的预测reward与输入第二个画面得到的reward(*权重)相减, 需要与这一次action得到的实际reward越接近越好. 两种方式的假设不同: 蒙特卡洛将每一次事件都当作独立的, 而TD则认为事件之间有关联关系. 3. DQN #### Reward Shaping 当存在数据极度不平衡的情况下, 无论如何执行action, 也无法训练actor. > 比如: > > - reward很少, 大部分都是0 > - 下围棋直到最后一步落子才能获取reward Reward Shaping: 可以额外增加一些reward的方式, 引导agent学习. #### 没有Reward的情况 通常有些环境存在没有Reward的情况, 需要让机器自己来定义Reward, 从示范中学习到Reward Function: 通过expert的数据并结合环境, 反推出Reward Functioin. 基本概念是: Teacher is always the best. 可以将过程类比成GAN模型: actor - generator, reward function - discriminaor. ### 3. 代码实现 1. 学习了一些数据预处理的方法 2. 数据特征分析的一些常用操作 3. 完成了 California-house-prices 数据预处理和数据特征分析的代码 4. k-fold Cross-Validation的实现 ## 本周学习计划 1. 周志华 《机器学习》 Ch.13 半监督学习 2. 李宏毅2021春机器学习课程 Life Long Learning 3. 完成上一周 California-house-prices 的模型和训练代码 最后修改：2021 年 09 月 06 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏