参数估计

• 矩估计：建立参数和总体矩的关系，求解参数

  • 除非参数本身即为样本矩，否则基本无应用价值
  • 应用场合
    • 均值：对应二次损失 $\arg\min{\mu} \sum{i=1}^N (x_i - \mu)^2$
    • 方差：对应二次损失?

• 极大似然估计：极大化似然函数，求解概率上最合理参数

  • 需知道（假设）总体 概率分布形式
  • 似然函数形式复杂，求解困难
    • 往往无法直接给出参数的解析解，只能求数值解
  • 应用场合
    • 估计回归参数：对数损失 $\mathop{\arg\min}{\beta} \sum{i=1}^N lnP(y_i|x_i, \beta)$

• 损失函数估计：极小化损失函数，求解损失最小的参数

  • 最泛用的参数求解方法
    • 适合求解有大量参数的待求解的问题
    • 往往通过迭代方式逐步求解
  • 特别的
    • 线性回归使用 MSE 作为损失函数时，也被称为最小二乘估计
    • 极大似然估计同对数损失函数

• 参数估计都可以找到合适损失函数，通过迭代求解损失最小化

随机模拟估计参数

• 需要设计随机模拟实验估计参数
• 应用场合
  • 蒙特卡洛类似算法：随机化损失

迭代求解参数

• 损失函数定义不同

  • 包含样本量数量不同
  • 惩罚项设置不同

• 异步更新参数

  • 同时求解参数数量：全部、部分、单个
  • 参数升维

• 更新方向

  • 梯度
  • 海瑟矩阵
  • 次梯度

• 更新方式

  • 叠加惯性
  • 动态学习率

Loss Models

模型（目标函数）在样本整体的损失：度量模型整体预测效果

• 代表模型在整体上的性质，有不同的设计形式

• 可以用于 设计学习策略、评价模型

  • 风险函数
  • 评价函数

• 有时在算法中也会使用整体损失

Expected Risk / Expected Loss / Generalization Loss

期望风险（函数）：损失函数 $L(Y, f(X))$（随机变量）期望

• $P(X, Y)$：随机变量 $(X, Y)$ 遵循的联合分布，未知

• 风险函数值度量模型预测错误程度

  • 反映了学习方法的泛化能力
  • 评价标准（监督学习目标）就应该是选择期望风险最小

• 联合分布未知，所以才需要学习，否则可以直接计算条件分布概率，而计算期望损失需要知道联合分布，因此监督学习是一个病态问题

Empirical Risk / Empirical Loss

经验风险：模型关于给定训练数据集的平均损失

• $\theta$：模型参数
• $D_i$：样本损失权重，常为 $\frac 1 N$，在 Boosting 框架中不同

• 经验风险损失是模型 $f(x)$ 的函数

  • 训练时，模型是模型参数的函数
  • 即其为模型参数函数

• 根据大数定律，样本量容量 $N$ 趋于无穷时，$R{emp}(f)$ 趋于 $R{exp}(f)$

  • 但是现实中训练样本数目有限、很小
  • 利用经验风险估计期望常常并不理想，需要对经验风险进行矫正

• 例子

  • maximum probability estimation：极大似然估计
    • 模型：条件概率分布（贝叶斯生成模型、逻辑回归）
    • 损失函数：对数损失函数

Structual Risk / Structual Loss

结构风险：在经验风险上加上表示 模型复杂度 的 regularizer（penalty term）

• $J(f)$：模型复杂度，定义在假设空间$F$上的泛函
• $\lambda$：权衡经验风险、模型复杂度的系数

• 结构风险最小化
  • 添加 regularization（正则化），调节损失函数（目标函数）
• 模型复杂度 $J(f)$ 表示对复杂模型的惩罚：模型 $f$ 越复杂，复杂项 $J(f)$ 越大
• 案例
  • maximum posterior probability estimation：最大后验概率估计
    • 损失函数：对数损失函数
    • 模型复杂度：模型先验概率对数后取负
    • 先验概率对应模型复杂度，先验概率越小，复杂度越大
  • 岭回归：平方损失 + $L2$ 正则化 $\mathop{\arg\min}{\beta} \sum_{i=1}^N (y_i - f(x_i, \beta))^2 + |\beta|$
  • LASSO：平方损失 + $L1$ 正则化 $\mathop{\arg\min}{\beta} \sum_{i=1}^N (y_i - f(x_i, \beta))^2 + |\beta|_1$

Generalization Ability

泛化能力：方法学习到的模型对未知数据的预测能力，是学习方法本质、重要的性质

• 测试误差衡量学习方法的泛化能力不可靠，其依赖于测试集，而测试集有限
• 学习方法的泛化能力往往是通过研究泛化误差的概率上界进行

Generalization Error Bound

泛化误差上界：泛化误差的 概率 上界

• 是样本容量函数，样本容量增加时，泛化上界趋于 0
• 是假设空间容量函数，假设空间容量越大，模型越难学习，泛化误差上界越大

泛化误差

• 根据 Hoeffding 不等式，泛化误差满足

  $$\begin{align*} & \forall h \in H, & P(|E(h) - \hat E(h)| \geq \epsilon) \leq 2 e^{-2 N \epsilon^2} \\ \Rightarrow & \forall h \in H, & P(|E(h) - \hat E(h)| \leq \epsilon) \geq 1 - 2|H|e^{-2N\epsilon^2} \end{align*}$$

  • $H$：假设空间
  • $N$：样本数量
  • $E(h) := R_{exp}(h)$
  • $\hat E(h) := R_{emp}(h)$

• 证明如下：

  $$\begin{align*} P(\forall h \in H: |E(h) - \hat E(h)| \leq \epsilon|) & = 1 - P(\exists h \in H: |E(h) - \hat E(h)| \geq \epsilon) \\ & = 1 - P((|E(h_1) - \hat E(h_1) \geq \epsilon) \vee \cdots \vee (|E(h_{|H|}) - \hat E_{|H|}| \geq \epsilon)) \\ & \geq 1 - \sum_{i=1}^{|H|} P(|E(h_i) - \hat E(h_i)| \geq \epsilon) \\ & \geq 1 - 2|H|e^{-2N \epsilon^2} \end{align*}$$

• 对任意 $\epsilon$，随样本数量 $m$ 增大， $|E(h) - \hat E(h)| \leq \epsilon$ 概率增大，可以使用经验误差近似泛化误差

二分类泛化误差上界

• 由 Hoeffding 不等式

  $$\begin{align*} P(E(h) - \hat E(h) & \geq \epsilon) \leq exp(-2N\epsilon^2) \\ P(\exists h \in H: E(h) - \hat E(h) \geq \epsilon) & = P(\bigcup_{h \in H} \{ E(h) - \hat E(h) \geq \epsilon \}) \\ & \leq \sum_{h \in H} P(E(h) - \hat E(h) \geq \epsilon) \\ & \leq |H| exp(-2 N \epsilon^2) \end{align*}$$

• 则 $\forall h \in H$，有

  $$P(E(h) - \hat E(h) < \epsilon) \geq 1 - |H| exp(-2 N \epsilon)$$

  则令 $\sigma = |H| exp(-2N\epsilon^2)$，则至少以概率 $1-\sigma$ 满足如下，即得到泛化误差上界

  $$\begin{align*} E(h) & \leq \hat E(h) + \epsilon(|H|, N, \sigma) \\ \epsilon(|H|, N, \sigma) & = \sqrt {\frac 1 {2N} (log |H| + log \frac 1 {\sigma})} \end{align*}$$

Probably Approximate Correct 可学习

PAC 可学习：在短时间内利用少量（多项式级别）样本能够找到假设 $h^{‘}$，满足

• 即需要假设满足两个 PAC 辨识条件

  • 近似条件：泛化误差 $E(h^{‘})$ 足够小
  • 可能正确：满足近似条件概率足够大

• 同等条件下

  • 模型越复杂，泛化误差越大
  • 满足条件的样本数量越大，模型泛化误差越小

• PAC 学习理论关心能否从假设空间 $H$ 中学习到好的假设 $h$

  • 由以上泛化误差可得，取 $\sigma = 2|H|e^{-2N\epsilon^2}$，则样本量满足 $N = \frac {ln \frac {2|H|} \sigma} {2 \epsilon^2}$ 时，模型是 PAC 可学习的

Regularization

正则化：（向目标函数）添加额外信息以求解病态问题、避免过拟合

• 常应用在机器学习、逆问题求解

  • 对模型（目标函数）复杂度惩罚
  • 提高学习模型的泛化能力、避免过拟合
  • 学习简单模型：稀疏模型、引入组结构

• 有多种用途

  • 最小二乘也可以看作是简单的正则化
  • 岭回归中的 $\mathcal{l_2}$ 范数

模型复杂度

模型复杂度：经常作为正则化项添加作为额外信息添加的，衡量模型复杂度方式有很多种

• 函数光滑限制

  • 多项式最高次数

• 向量空间范数

  • $\mathcal{L_0} - norm$：参数个数
  • $\mathcal{L_1} - norm$：参数绝对值和
  • $\mathcal{L_2}$- norm$：参数平方和

$\mathcal{L_0} - norm$

• $\mathcal{l_0} - norm$ 特点
  • 稀疏化约束
  • 解 $\mathcal{L_0}$ 范数正则化是 NP-hard 问题

$\mathcal{L_1} - norm$

• $\mathcal{L_1} - norm$ 特点

  • $\mathcal{L_1}$ 范数可以通过凸松弛得到 $\mathcal{L_0}$ 的近似解
  • 有时候出现解不唯一的情况
  • $\mathcal{L_1}$ 范数凸但不严格可导，可以使用依赖次梯度的方法求解极小化问题

• 应用

  • LASSO

• 求解

  • Proximal Method
  • LARS

$\mathcal{L_2} - norm$

• $\mathcal{L_2} - norm$ 特点
  • 凸且严格可导，极小化问题有解析解

$\mathcal{L_1 + L_2}$

• $\mathcal{L_1 + L_2}$ 特点

  • 有组效应，相关变量权重倾向于相同

• 应用

  • Elastic Net

稀疏解产生

稀疏解：待估参数系数在某些分量上为 0

$\mathcal{L_1} - norm$ 稀疏解的产生

• $\mathcal{L_1}$ 范数在参数满足 一定条件 情况下，能对 平方损失 产生稀疏效果

• 在 $[-1,1]$ 内 $y=|x|$ 导数大于 $y=x^2$（除 0 点）

  • 则特征在 0 点附近内变动时，为了取到极小值，参数必须始终为 0
  • 高阶项在 0 点附近增加速度较慢，所以 $\mathcal{L_1} - norm$ 能产生稀疏解是很广泛的
  • $mathcal{L_1} - norm$ 前系数（权重）越大，能够容许高阶项增加的幅度越大，即压缩能力越强

• 在 0 附近导数 “不小”，即导数在 0 点非 0

  • 对多项式正则化项
    • $\mathcal{L_1} - norm$ 项对稀疏化解起决定性作用
    • 其他项对稀疏解无帮助
  • 对“非多项式”正则化项
    • $e^{|x|}-1$、$ln(|x|+1)$ 等在0点泰勒展开同样得到 $\mathcal{L_1} - norm$ 项
    • 但是此类正则化项难以计算数值，不常用

$\mathcal{L_1} - norm$ 稀疏解推广

• 正负差异化：在正负设置权重不同的 $\mathcal{L_1}$，赋予在正负不同的压缩能力，甚至某侧完全不压缩

• 分段函数压缩：即只要保证在 0 点附近包含 $\mathcal{L_1}$ 用于产生稀疏解，远离 0 处可以设计为常数等不影响精确解的值

  • Smoothly Clipped Absolute Deviation

    $$R(x|\lambda, \gamma) = \left \{ \begin{array} {l} \lambda|x| \qquad & if |x| \leq \lambda \\ \frac {2\gamma\lambda|x| - x^2 - {\lambda}^2 } {2(\gamma - 1)} & if \gamma< |x| <\gamma\lambda \\ \frac { {\lambda}^2(\gamma+1)} 2 & if |x| \geq \gamma\lambda \end{array} \right.$$

  • Derivate of SCAD

    $$R(x; \lambda, \gamma) = \left \{ \begin{array} {l} \lambda \qquad & if |x| \leq \gamma \\ \frac {\gamma\lambda - |x|} {\gamma - 1} & if \lambda < |x| < \gamma\lambda \\ 0 & if |x| \geq \gamma\lambda \end{array} \right.$$

  • Minimax Concave Penalty

    $$R_{\gamma}(x;\lambda) = \left \{ \begin{array} {l} \lambda|x| - \frac {x^2} {2\gamma} \qquad & if |x| \leq \gamma\lambda \\ \frac 1 2 \gamma{\lambda}^2 & if |x| > \gamma\lambda \end{array} \right.$$

• 分指标：对不同指标动态设置 $\mathcal{L_0}$ 系数

  • Adaptive Lasso：$\lambda \sum_J w_jx_j$

稀疏本质

稀疏本质：极值、不光滑，即导数符号突然变化

• 若某约束项导数符号突然变化、其余项在该点处导数为 0，为保证仍然取得极小值，解会聚集（极小）、疏远（极大）该点（类似坡的陡峭程度）

  • 即此类不光滑点会抑制解的变化，不光滑程度即导数变化幅度越大，抑制解变化能力越强，即吸引、排斥解能力越强
  • 容易构造压缩至任意点的约束项
  • 特殊的，不光滑点为 0 时，即得到稀疏解

• 可以设置的多个极小不光滑点，使得解都在不连续集合中

  • 可以使用三角函数、锯齿函数等构造，但此类约束项要起效果，必然会使得目标函数非凸
    • 但是多变量场合，每个变量实际解只会在某个候选解附近，其邻域内仍然是凸的
    • 且锯齿函数这样的突变非凸可能和凸函数具有相当的优秀性质
  • 当这些点均为整数时，这似乎可以近似求解 整数规划

Early Stopping

Early Stopping：提前终止（训练）

• Early Stopping 也可以被视为是 regularizing on time
  • 迭代式训练随着迭代次数增加，往往会有学习复杂模型的倾向
  • 对时间施加正则化，可以减小模型复杂度、提高泛化能力

Optimizer

1
2
3
4
5
6
7
8
9
10
11

class tf.train.GradientDescentOptimizer:

class tf.train.AdagradOptimizer:

class tf.train.MomentumOptimizer:

class tf.train.AdamOptimizer:

class tf.train.FtrlOptimizer:

class tf.train.RMSPropOptmizer:

结构

Catalyst优化器：利用Scala模式匹配和quasiquotes机制构建的 可扩展查询优化器

• SparkSQL Pipeline的中间核心部分

Parser模块

Parser模块：将SQL语句切分为token，根据一定语义规则解析为AST

• Spark1.x使用Scala原生Parser Combinator构建的词法、语法 分析器

• Spark2.x使用采用第三方语法解析器工具ANTLR4

  • ANTLR4根据语法文件SqlBase.g4自动解析生成两个Java类 ，将sql语句解析成ParseTree的语法结构

    • SqlBaseLexer：词法解析器
    • SqlBaseParser：语法解析器

  • 随后ParsePlan过程，使用AstBuilder.scala将ParseTree 转换为catalyst表达式逻辑计划Unresovled Logical Plan

    • Unsolved Relation
    • Unsolved Function
    • Unsolved Attribute

Analyzer模块

Analyzer模块：使用Analysis Rules，借助数据元数据 （session catalog、hive metastore）将ULP解析为 Logical Plan

• ULP虽然具备基本骨架，但是系统对表的字段信息不清楚，需要 基本元数据信息表达ULP中token

• 遍历整个AST，对树上每个结点进行数据类型绑定、函数绑定， 得到LP

Schema Catalog

元数据信息：表的模式信息

• 表的基本定义：表名、列名、数据类型
• 表的数据格式：json、text、parquet、压缩格式
• 表的物理位置

Optimizer模块

Optimizer模块：使用Optimization Rules对LP进行合并、列 裁剪、过滤器下推等优化工作，生成等价Optimized Logical Plan

• 分为RBO、CBO两种优化策略，是catalyst核心

Spark Planner

Spark Planner模块：将OLP转换为spark能够理解的 Physical Plan

• 将逻辑上可行的执行计划变为Spark真正可以执行的物理计划
• 物理计划实际上是逻辑计划中耗时最小的算法实现

Join

Join类型

SparkSQL目前支持三种join算符

• shuffle hash join
• broadcast hash join
• sort merge join

Broadcast Hash Join

broadcast hash join：将小表广播分发到大表所在的结点上， 并行在各节点上进行hash join

• 适合小表很小，可以直接广播的场合

  • spark.sql.autoBroadcastJoinThreshold设置广播小表 大小上限

• broadcast阶段：将所小表广播分发到大表所在的所有主机

  • driver分发
  • p2p分发

• hash join结点：各结点独立并行hash join

  • 小表构建hash表
  • 各结点本地大表试探

Shuffle Hash Join

shuffle hash join：按照join key分区，在每个结点独立并行 进行hash join

• 类似分布式GHJ，不同块位于不同结点

• shuffle阶段：将表按照join key分区，将具有相同join key 的记录重分布到同一结点

• hash jon阶段：各结点使用本地数据独立并行hash join

Sort Merge Join

SMJ：按照join key分区，在各节点独立并行SMJ

• shuffle阶段：将表按照join key分区，将具有相同join key 的记录重分布到同一结点

• sort阶段：各节点并行对本地数据排序

  • spark当前shuffle算法使用sort-based shuffle算法
  • 理论上shuffle过后各分区数据已经排序完毕，无需再次 sort，效率很高

• merge阶段：各节点对排序好表数据执行join操作

Join Reorder

• 基于CBO的join重排序优化：用统计信息预估的基修正join顺序

• 使用动态规划算法，考虑所有可能组合，选择代价最小的方案

  • 单个join操作成本，join树的成本是所有中间join成本总和

    $$cost = weight * cardinality + (1 - weight)*size$$

    • carinality：对应CPU成本
    • size：对应IO成本

  • 没有任何join条件同时包含左、右子树时，修剪笛卡尔积 减少搜索范围

Statistics Collection Framework

CBO依赖统计细节信息优化查询计划

• CBO自下而上遍历LP，统计信息可以随之传播到上层算子

统计信息类型

• Numeric、Date、Timestamp

  • Distinct Count
  • Max
  • Min
  • Null Count
  • Average Length：定长
  • Max Length：定长

• String、Binary

  • Distinct Count
  • Null Count
  • Average Length
  • Max Length

统计方式

• 扫描全表：简单、统计信息准确，代价大
• 抽样统计：

应用

Filter Selectivity

过滤选择率：估计应用谓词表达式过滤的选择率

逻辑运算符

• AND：左侧过滤条件选择率、右侧过滤条件选择率之积

  $$fs(a AND b) = fs(a) * fs(b)$$

• OR：左侧、右侧过滤条件选择率之和，减去其乘积

  $$fs(a OR b) = fs(a) + fs(b) - fs(a) * fs(b)$$

• NOT：1减去原始过滤条件选择率

  $$fs(NOT a) = 1.0 - fs(a)$$

比较运算符

• =：等于条件

  • 若常数取值在当前列取值范围之外，则过滤选择率为0
  • 否则根据柱状图、均匀分布得到过滤选择率

• <：小于条件

  • 若常数取值小于当前列最小值，则过滤选择率为0
  • 否则根据柱状图、均匀分数得到过滤选择率

Join Carinality

联接基：估计联接操作结果的基

• inner：其他基估计值可由inner join计算

  $$num(A IJ B) = \frac {num(A) * num(B)} {max(distinct(A.k), distinct(B.k))}$$

  • num(A)：join操作前表A的有效记录数
  • distinct(A.k)：表A中列k唯一值数量

• left-outer：取inner join、左表中基较大者

  $$num(A LOJ B) = max(num(A IJ B), num(A))$$

• right-outer：取inner join、右表中基较大者

  $$num(A ROJ B) = max(num(A IJ B), num(B))$$

• full-outer

  $$num(A FOJ B) = num(A ROJ B) + num(A ROJ B) - num(A IJ B)$$

B)

$$