数学基础
高等数学
数列与级数
数列和级数是数学学科的基础内容，在高中数学和大学数学中都有涉及：
- 数列：数列是有序数的排列，可以表示为$a_1,a_2,a_3,…,a_n,…$，其中$a_n$ 表示数列的第n项。常见的数列有等差数列、等比数列等，例如等差数列1,3,5,7,9,11，其公差d=2，通项公式为$a_n=a_1+(n-1)d$, 这里 $n$ 代表数列中的项数，$a_1$ 代表第一项。
- 级数：级数是数列中所有项的和，表示为$S_n=a_1+a_2+…+a_n$，其中$S_n$代表前n项的和。常见的级数有调和级数、等比级数等。例如：调和级数$H_n=1+1/2+1/3+…+1/n$是一个无限延伸的级数，在$n$越来越大的情况下，级数的和$H_n$会趋近于$\ln n$。
- 收敛和发散：对于给定的数列或级数，它们可能把所有项加起来得到一个有限值，该数列或级数称为收敛；或者可能随着项的增加而无限变大，这时该数列或级数称为发散。例如：级数$\sum_{n=0}^{+\infty} \frac{1}{2^n}$ 是一个收敛的等比数列，其和为2；级数 $\sum_{n=0}^{+\infty} 1$ 是一个发散的级数。
- 通项公式：对于一个数列，如果能找到一个公式，能够计算任意一项，这个公式叫做通项公式。通项公式可以帮助我们计算数列中任何一项的数值。例如：等比数列$1,2,4,8,16,…$的通项公式是$a_n=2^{n-1}$，其中n代表数列中的项数。
极限和连续性
极限和连续性是高等数学中的核心概念。它们是微积分、实分析和函数论等分支学科的基础，在各种应用场合中都有广泛的应用。
- 极限：当某个量趋于某些特定的值时，另一个量将会保持在可接受的范围内，这种关系可以表示为极限，通常用$\lim$来表示。例如，$\lim\limits_{x\to 0} \frac{\sin x}{x}=1$，其中x趋于0时，函数$\frac{\sin x}{x}$的极限等于1。
- 连续性：在某一区间内，如果函数的极限值等于该点的函数值，就称该函数在该点是连续的。连续性是指函数的平滑性和连贯性，若函数的任何点中只要有一个点不连续，则整个函数都是不连续的。例如，函数$f(x)=\sin x$在区间$[0,\pi]$上是一个连续的函数。
- 极值问题：极限和连续性理论的应用包括了数学中的极值问题，如寻找函数在某一区间内的最大值或最小值。一些计算问题，如函数的导数，都可以通过极限和连续性理论来解决。
- 应用领域：极限和连续性在工程学、经济学、物理学、计算机科学等领域都有广泛的应用，如气象学中的天气预测、机械制造中的机械设计、计算机图形学中的图形处理等。
微积分
微积分是数学的一个分支，研究的是函数的导数和积分，是求解变化率和面积等问题的重要工具。以下是微积分的核心知识：
- 导数和微分：导数是函数的变化率，表示函数在某点的瞬时变化率，通常表示为$f’(x)$或$\frac{df(x)}{dx}$。而微分指函数的微小变化，可以表示为$df=f’(x)dx$。求解导数和微分是微积分中最基础的问题之一，它们有广泛的应用，如在物理学中描述物体的运动和加速度等。
- 积分和不定积分：积分是求函数在某一区间上的面积，通常表示为$\int_{a}^{b}f(x)dx$。不定积分则是求函数的原函数，通常表示为$\int f(x)dx$。积分和不定积分是求面积和求函数的原函数的重要方法，它们可以应用于各种应用问题中，如统计和概率论等领域。
- 微分方程和常微分方程：
- 微分方程是描述函数与函数导数之间关系的方程，包括一阶、二阶及高阶微分方程，通常存在一个或多个未知函数和这些未知函数的导数。以下是一个简单的例子：$\frac{dy}{dx}+y = 2x$，这是一个一阶常微分方程，其中y是未知函数。它可以被写成标准形式：$\frac{dy}{dx}=2x-y$。
- 常微分方程是仅包含一个自变量的微分方程，其未知函数是一个关于该自变量的函数。因此，常微分方程只涉及到一元函数和它的导数，通常可以用解析解或数值方法来计算。以下是一个简单的例子：$y’’+2y’+y=0$，这是一个二阶常微分方程，其中$y$是未知函数，是关于$x$的函数。它可以被写成标准形式：$y’’+2y’+y=0$。通过代入$y=e^{rx}$，解出$y$的特征根为$r_1=-1$和$r_2=-1$。因此，方程的一般解为$y=c_1e^{-x}+c_2xe^{-x}$，其中$c_1$和$c_2$是任意常数。这个方程的一类通解可以用$y=c_1e^{-x}+c_2xe^{-x}$来表示，其中$c_1$和$c_2$是任意常数。因此，当我们得到一组特定的初始条件时，我们可以计算$c_1$和$c_2$的值，从而得到特定函数$y(x)$作为该微分方程的解。这个微分方程的意义是：欧拉（Euler）发现了这个ODE的解法是$
- 多元微积分是研究多元函数的微积分学科，涉及到多元函数的极限、导数、积分、曲线、曲面、积分定理等内容。多元函数指的是有多个自变量的函数。与一元函数不同，多元函数的导数不能用常规的导数计算方法，需要用偏导数。
- 在多元微积分中，极限的定义与一元函数的极限相同，都是当自变量趋近于某个值时，函数值趋近于某个数的情形。不同的是，多元函数的极限需要考虑所有自变量同时趋近于某个值的情况。
- 导数是多元微积分中的重要概念。多元函数的导数可以通过偏导数计算，偏导数是指在其他自变量不变的情况下，对一个自变量求导数。另外，多元函数的方向导数是指在一个给定方向上的导数，可以用来研究函数在不同方向上的变化趋势。
- 积分是多元微积分中的另一个重要概念。多元函数的积分需要考虑不同维的区域，可以通过对每个自变量分别积分的方法求解。曲线积分可以用来计算向量场沿曲线的积分，而曲面积分可以用来计算向量场沿曲面的积分。
- 多元微积分还涉及到一些重要的定理，如格林公式和斯托克斯定理等。这些定理可以用来简化多元函数的计算和分析过程，具有重要的理论和应用价值。
- 格林公式：格林公式是多元微积分中的一个重要定理，用于计算曲线和曲面积分。它以向量场和曲线或曲面的边界有关，公式如下：$\oint\limits_{C}\left(Pdx+Qdy\right)=\iint\limits_{D}\left(\dfrac{\partial Q}{\partial x}-\dfrac{\partial P}{\partial y}\right)dxdy$，其中，左边是向量场沿曲线C的环路积分，右边是向量场在曲线C所围成的区域D上的二重积分，$\frac{\partial P}{\partial y}$和$\frac{\partial Q}{\partial x}$分别表示向量场$F(x,y)=(P(x,y),Q(x,y))$的偏导数。举个例子，考虑计算向量场$F(x,y)=(x^2,y)$沿矩形$D=[1,2]\times[0,2]$的周长C的环路积分。首先，通过格林公式，我们将环路积分转化为曲面积分：$\oint\limits_{C}(x^2dy)=\iint\limits_{D}\dfrac{\partial}{\partial x}(x^2)dxdy=\int_{0}^{2} \left[\dfrac{x^3}{3}\right]_{1}^{2} dy=\dfrac{7}{3}$
- 斯托克斯定理：斯托克斯定理是多元微积分中的另一个重要定理，用于计算曲线和曲面积分。它以向量场和曲面的边界有关，公式如下：$\oint\limits_{\partial S}F\cdot dr=\iint\limits_{S}(\nabla\times F)\cdot dS$，其中，左边是向量场沿曲面$S$的边界$\partial S$的环路积分，右边是向量场$F$的旋度在曲面$S$上的通量，$\nabla\times F$表示向量场$F$的旋度。
- 应用领域：微积分的应用领域非常广泛，包括物理学、工程学、经济学、计算机科学等，许多科学和工程问题都可以通过微积分来求解。如在物理学中，微积分可以用于解决反应速率、流动和波动等问题。
线性代数
- 矩阵的基本概念: 矩阵是一个矩形的数表，由行和列组成。其中，行数和列数分别称为矩阵的行数和列数，矩阵中的元素是实数或复数。
- 向量&矩阵&张量：一种组织数据的方式，如：类别、语音信号、图像、视频等。
- 矩阵的代数运算: 矩阵的代数运算包括矩阵的加法、数乘和矩阵乘法等。其中，矩阵加法和数乘与普通向量的加法和数乘类似，矩阵乘法是指把一个$m\times n$的矩阵和一个$n\times p$的矩阵相乘得到一个$m\times p$的矩阵。
- 范数：度量单个向量的大小；p-范数：当p为0时，范数值为非零元素个数；p为1时，范数值为各个元素的绝对值之和，p为2时，范数值为常见的欧几里得长度；p为无穷时，范数值为各个元素的最大值；即p越大时，绝对值越大的元素起到的作用越大。
- 内积：两个向量之间的关系。
- 矩阵运算是一种线性变换，既可以看成是对数据（向量进行变换），也可以看成是对坐标系进行变换。
- 矩阵计算和坐标轴变换有很大的关系。矩阵变换是指将一个向量或者点通过矩阵进行变换，从而达到坐标系变换的目的。我们可以从以下几个角度来理解矩阵变换：
- 矩阵运算角度
我们可以把向量和矩阵看做是一个矩阵乘法运算，即通过矩阵将向量进行变换。例如，对于向量，我们可以通过矩阵对其进行变换，得到新的向量。这相当于将原始向量$x$和$y$按照矩阵的方式组成一个新的向量，然后通过矩阵乘法运算进行变换。 - 坐标系视角
我们可以把矩阵变换看做是一个坐标系变换，通过矩阵将原坐标系转换成新的坐标系。例如，对于二维平面上的点$(x,y)$，我们可以通过矩阵对其进行坐标系变换，得到新的点$(x’,y’)$。这相当于将原始坐标系中的点$(x,y)$转换为新的坐标系中的点$(x’,y’)$。 - 几何变换角度
我们可以把矩阵变换看做是一个几何变换，例如移动、旋转、缩放等变换。不同的矩阵对应不同的几何变换。
- 矩阵运算角度
- 矩阵的特征值和特征向量: 一个$n\times n$的矩阵A的特征值和特征向量是指一个非零的向量$x$和实数$\lambda$，使得$Ax=\lambda x$。矩阵的特征值和特征向量是矩阵理论的基本概念，广泛应用于线性代数和数学物理。
- 矩阵的特征向量表示线性变换的方向，从左（右）特征向量的方向变换到右（左）特征向量的方向；
- 特征值则代表了具体某个方向变换的伸缩系数。
- 矩阵的行列式: 矩阵的行列式是一个$n\times n$的矩阵所构成的一个数值，表示这个矩阵的行向量（或列向量）之间的线性独立性。行列式是计算矩阵的各种性质和运算的基础，如矩阵的逆、矩阵的秩等。
- 矩阵分解: 矩阵分解是指把一个矩阵分解成多个简单矩阵的乘积的过程，常见的矩阵分解有LU分解、QR分解、SVD分解等。这些分解可用于求解线性方程组、最小二乘问题、主成分分析等。
- 矩阵的应用: 矩阵论在实际应用中有广泛的应用，如数据分析、信号处理、网络分析、最优化问题等。在机器学习和人工智能领域中，矩阵论被广泛应用于矩阵分解、矩阵乘法、矩阵求逆等方面。
概率&统计
| 概率 | 统计 | |
|---|---|---|
| 集中趋势 | 分布期望 | 样本均值、中位数、众数 |
| 分散度 | 分布方差/标准差、分位点 | 样本方差/标准差、全距、四分距 |
基本概念
统计模型
- $p(x;\theta)$：随机变量$x$受参数$\theta$影响；
随机样本
- 从统计模型中独立同分布的生成的实例；
统计集中趋势
- 均值：为这批数据找到它们的“代表”
- 局限：把众多的数据用一个数据表示出来必然会丢失许多信息，如：数据分布情况会因异常值而产生巨大偏离。（张家有钱一千万，邻居九个穷光蛋，平均各个张百万）
- 中位数：中点数，中值；是按顺序排列的一组数据中居于中间位置的数。
- 局限：当数据有多个不同的部分组成时，中位数也没有太多的代表性。
- 众数：样本观测值在频数分布表中频数最多的那一组的组中值。
统计分散度
平均数可以表征一批数据的典型值，但是仅凭平均数还不能给我们提供足够的信息，平均数无法表征一组数据的分散程度。
- 全距=max-min：也叫极差。它是一组数据中最大值与最小值之差。可以用于度量数据的分散程度。
- 局限：全距虽然求解方便快捷，但是它的局限性在于数据中存在异常值的情况，会产生偏差。比如只是增加了一个异常值，数据的全距就会有很大变化。
- 四分位数：所有观测值从小到大排序后四等分，处于三个分割点位置的数值就是四分位数：Q1，Q2和Q3。
- 迷你距：也叫四分位距；一组数据中较小四分位数与较大四分位数之差；迷你距= 上四分位数 - 下四分位数。
- 全距，四分位距，箱形图可以表征一组数据极大和极小值之间的差值跨度，一定程度上反应了数据的分散程度，但是却无法精准的告诉我们，这些数值具体出现的频率；我们度量每批数据中数值的“变异”程度时，可以通过观察每个数据与均值的距离来确定，各个数值与均值距离越小，变异性越小数据越集中，距离越大数据约分散，变异性越大。
- 方差：方差是度量数据分散性的一种方法，是数值与均值的距离的平方数的平均值。
- 标准差：方差的开方。
- 标准分：$Z=\frac{X-\mu}{\sigma}$，表征了距离均值的标准差的个数，可以用于有不同均值和不同标准差的多个数据集之间的数据比较。
概率&似然
- 概率是描述在确定分布下某个事件发生可能性的大小；
- 似然是描述在发生某些事件的情况下分布取某组参数的可能性。
P-value
- 一个事件的P-value不是这个事件的概率值，而是所有概率小于等于该事件概率值得概率和（积分），即反应该事件发生的稀有程度。
划分
- 互斥且并集为整个样本空间的一组事件称为样本空间的一个划分
条件概率
- 在事件A发生时事件B发生的条件概率为：事件A和事件B共同发生时的联合概率除以事件A发生的概率；
- 当事件A和事件B独立时，其联合概率等于各自发生概率的乘积，因此事件B发生的条件概率也等于事件B本身的概率。
全概率公式
- 一个事件的概率可以分为在一个划分下不同事件的概率与该在该事件下的条件概率乘积的和。
矩
- 即一种关于随机变量的期望；
- 原点矩：n阶原点矩就是随机变量的n次方的期望，如期望是一阶原点矩；
- 中心距：即随机变量通过期望去中心化后的期望，如方差是二阶中心距；
不相关&独立
- 不相关：$E(x,y)=E(x)E(y)$，主要是指没有线性关系，统计上的没有关系。
- 独立：$P(x,y)=\frac{P(x,y)P(y)}{P(y)}=P(x|y)P(y)=P(x)P(y)$，没有任何关系，一个事件的情况不影响另一个事件的概率。
自变量/协变量/因变量
- 在函数$y=f(x,b)$中$x$和$b$都可以影响$y$，我们操纵$x$作为输入，而$b$独立存在不控制；称$x$为自变量，$b$为协变量，$y$为因变量；
概率分布
- 随机事件发生的概率符合一定分布；
- 期望、方差等是描述分布的指标，但不等于分布；
- $分布=分布描述+参数$，分布描述如：高斯分布、二项分布等，分布描述决定分布的基本属性，参数决定分布的具体细节；
- 连续分布：高斯分布、指数分布；离散分布：0-1/伯努利分布、二项分布、几何分布、泊松分布；
高斯分布
- 一维：$P(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{1}{2}(\frac{x-\mu}{\sigma})^2}$
- 高维：$P(x)=\frac{1}{\sqrt{(2\pi)^d|\Sigma|}}e^{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)}$
- 其中$\Sigma$是对称的协方差矩阵，所以一定可以相似对角化，得到几个不相关的高斯分布；
- 等密度点为超椭球形；
- 边缘分布与条件分布都是高斯分布
- 高斯分布的不相关等于独立
- 高斯分布的线性变换/组合仍然是高斯分布；
伯努利分布
- $P(x=1;\theta)=\theta,P(x=0;\theta)=1-\theta$
指数分布族
- 意义：保凸性
- 基本形式：$p(x;\theta)=h(x)e^{\eta(\theta)T(x)-A(\theta)}$
- 伯努利分布：$p(x;\theta)=e^{I(x=1)ln(\theta)+I(x=0)ln(1-\theta)}$
凸优化
凸优化问题
- 凸函数在凸集上优化
- 凸集要求：
- 等式约束：仿射函数
- 仿射函数：最高次数为1的多项式函数。
- 常数项为零的仿射函数称为线性函数。
- 不等式约束为:凸函数<=0 或 凹函数>=0
- 等式约束：仿射函数
- 具体形式如下：
$$min_{\vec{w}}f(\vec{w})$$
$$s.t.\qquad g_j(\vec{w})\le0,j=1,2,…,J\qquad h_k(\vec{w})=0,k=1,2,…,K$$ - 其中$f(\vec{w})$和$g_j(\vec{w})$都是$R^n$上的连续可微凸函数；$h_k(\vec{w})$是仿射函数。
拉格朗日乘子法
- 可以将带约束求极值的问题转化为无约束求极值问题
- 通过引入松弛变量$\lambda\ge0$和拉格朗日乘子$\mu$可设计函数：
$$L(\vec{w},\lambda,\mu)=f(\vec{w})+\sum_j\lambda_jg_j(\vec{w})+\sum_k\mu_kh_k(\vec{w})$$ - 同时由于一种奇妙的性质：
$$max_{\lambda,\mu}L(\vec{w},\lambda,\mu)={f(\vec{w}),\vec{w}满足约束 \atop \infty,\vec{w}不满足约束}$$ - 使得原问题转化为了无约束的问题：
$$min_{\vec{w}}max_{\lambda,\mu}L(\vec{w},\lambda,\mu)$$ - 对偶问题即通过交换极小、极大地顺序而来,通过对偶问题往往能降低难度：
$$max_{\lambda,\mu}min_{\vec{w}}L(\vec{w},\lambda,\mu)$$ - 弱对偶性：
$$max_{\lambda,\mu}min_{\vec{w}}L(\vec{w},\lambda,\mu)\le min_{\vec{w}}max_{\lambda,\mu}L(\vec{w},\lambda,\mu)$$ - 强对偶性：
$$max_{\lambda,\mu}min_{\vec{w}}L(\vec{w},\lambda,\mu)=min_{\vec{w}}max_{\lambda,\mu}L(\vec{w},\lambda,\mu)$$ - 对于满足强对偶性的情况，对偶问题得到的解就是原问题的解；对于不满足强对偶性，对偶问题的解不一定是原问题的解。
- 对于凸优化问题，KKT条件与强对偶性互为充要；对于非凸优化问题，KKT条件是强对偶性的必要条件，还需要加上二阶导数正定判断。
KKT条件原理
- KKT条件为：
- $\nabla_{\vec{w}}{L(\vec{w},\lambda,\mu)}=0$
- $\lambda_j\ge 0,j=1,2,…,J$
- $\lambda_jg_j(\vec{w})=0,j=1,2,…,J$
- $g_j(\vec{w})\le0,j=1,2,…,J$
- $h_k(\vec{w})=0,k=1,2,…,K$
- 对于等式约束：
- 等同于将可行域限定在等式约束所代表的超平面上；
- 如果极值点处的梯度与超平面不垂直，则此处还有优化空间，即此处不是极值点；
- 所以极值点处函数的梯度一定与超平面垂直，即函数的梯度一定与超平面的梯度共线；
- 如果有多个等式约束，则函数的梯度在各个超平面梯度组成的子空间中。
- 由此可以得到等式约束极值必要条件（第一条）。
- 对于不等式约束（统一采用小于或等于）
- 可以将约束分成起作用的约束和不起作用的约束；
- 对于起作用的不等式约束，分析方法同等式约束，即函数的梯度一定与约束函数的梯度反向（不仅要共线，因为如果梯度同向则此约束暂时不起作用）
- 如果多个不等式约束同时作用，则函数的负梯度一定在各个约束的梯度正向子空间内，即加权系数一定要是正的。
- 对于不起作用的约束，加权系数为0。
- 由此分析可以得到不等式约束极值必要条件KKT条件（前三条）（凸优化时是充要条件）
- 另外加上原约束条件和极值的正定约束条件，可得全部条件；
- 等式约束要求梯度一定共线但不要求同反向，不等式约束不起作用不要求，起作用必反向；
- 等式约束可以看成是两个不等式约束来分析，此时必起作用。
机器学习基本知识
基本概念
模式
- 存在于时间和空间中可以观察的事物，如果可以用来区分它们是否相同或相似，就可以称为模式，模式不是事物本身，而是从事物中获得的信息。
- 世界上的事物都具有特殊性，不存在绝对的相同，但是人们为了认识世界，必须对事物加以分类，以更好地研究各个类别的规律。
- 每一个事物都可以看成是一些模式/特性的集合，机器学习就是找到这些模式和事物的模式表达。
机器学习
- 对象：具有一定统计规律的数据。
- 过程：找出数据中有泛化能力的模式/规律，以应用在新的场景下。
适用场景
- 数学/映射关系复杂；
- 难以编程实现；
- 有足够的数据。
模式识别
- 将带有空间、时间分布的事物的信息向类别映射。
- 可以分为统计模式识别方法和结构模式识别方法。
- 统计模式识别使用计算机对数据进行建模和分类，包括：数据获取，特征提取，分类器设计，系统实现
机器学习任务类型：
- 监督学习是在有明确的标签的数据上进行的，属于预测模型。
- 其中分类问题输出离散的类别标签，包括图片分类、诊断等等；
- 回归问题输出连续的回归值，包括股市预测、气温预测、点击率预估等等。
- 而无监督学习使用没有标签的数据，属于描述模型，揭示数据内在规律。其中包括聚类、降维。
- 半监督学习任务：用大量的未标记训练数据和少量的已标记数据来训练模型。
- 强化学习任务：从系统与环境的大量交互知识中训练模型。
机器学习算法类型：
- 传统统计学习：基于数学模型的机器学习方法。包括SVM、逻辑回归、决策树等。
- 这一类算法基于严格的数学推理，具有可解释性强、运行速度快、可应用于小规模数据集的特点。
- 深度学习：基于神经网络的机器学习方法。包括前馈神经网络、卷积神经网络、循环神经网络等。
- 这一类算法基于神经网络，可解释性较差，强烈依赖于数据集规模。这类算法在语音、视觉、自然语言等领域非常成功。
- 集成学习：将多种机器学习方法结合使用的策略，包括：bagging、boosting、stacking等。
- 一些常见的使用形式：随机森林（决策树+bagging）、adaboost、梯度提升树等。
可解释性
- 可解释性与问题难度本身就是矛盾的，当一个问题有明确的规则可以解决时，本身就具有可解释性，就不需要用机器学习；所以不是机器学习、深度学习可解释性差，而是它们能够应对可解释性差的问题；可解释性好的问题就是人提前在数据中挖掘出了信息、于是就可以用简单模型。
没有免费的午餐定理：
- 对于一个学习算法A，如果在某些问题上它比算法B好，那么必然存在另一些问题，在那些问题中B比A更好。
- 因此不存在这样的算法：它在所有的问题上都取得最佳的性能。因此要谈论算法的优劣必须基于具体的学习问题。
- 每一个模型都是在学习一个分布，当分布变化时，模型自然不能取得更好的效果。
拒绝策略
在判决结果置信度低时，在实际中有必要使用拒绝决策，即不对数据的类别进行判定或预测。
信息论
信息
- 从不太可能发生的事件中能学到更多的有用信息。
- 发生可能性较大的事件包含较少的信息，发生可能性较小的事件包含较多的信息;
- 独立事件包含额外的信息。
自信息self-information
- 对于事件 ，定义自信息self-information为该事件发生概率的负对数，即概率越大的事件信息越少。
- 自信息仅仅处理单个输出，但是如果计算自信息的期望，它就是熵。
熵函数
- 用来对q这个分布的不确定性进行编码所需的信息量；
相对熵（KL散度）
- 给定分布q之后，还需要多少信息来编码分布p；
- 假如两个分布完全一样，相对熵就是0；
- 两个分布不一样时相对熵增加至无穷大；
交叉熵
- 度量两个分布的距离，在分类问题中对应最大似然估计。范围为真实分布的熵到无穷大；
- p与q的交叉熵=p的熵+p与q的相对熵。
特征
特征提取
原始数据（如文章、图像）的维度、特征数往往极高，为了实现有效地识别，需要从数据中找到有效特征。
特征空间
- 输入空间：所有输入的可能取值；
- 输出空间：所有输出的可能取值。
- 特征空间：经过特征工程处理过的输入空间
- 特征向量表示每个具体的输入，所有特征向量构成特征空间。
- 特征空间的每一个维度对应一种特征。
- 可以将输入空间等同于特征空间，但是也可以不同。绝大多数情况下，输入空间等于特征空间。
- 模型是定义在特征空间上的。
泛化
- 更加一般、更加普遍的规律、特征；如PCA分解时，对应奇异值/方差越大的分量是越普遍的分量，也越具有泛化性。
- 越具有泛化能力的信息越具有普适性，也越是机器学习和人学习的重点。
- 泛化特征与所研究问题有关，如不同的分类问题中，同一个特征的重要程度不一样。
假设空间
- 代表模型的函数集合。这也称作模型的表示容量representational capacity。
- 不同的模型（算法）有不同的假设空间（函数空间），因此需要考虑所需要的找到的假设函数是不是在假设空间中；
- 由于额外的限制因素（比如优化算法的限制），模型的有效容量effective capacity一般会小于模型的表示容量。
- 通常在模型的假设空间中找出最佳的函数是非常困难的优化问题，实际应用中只是挑选一个使得训练误差足够低的函数即可。
分布
独立同分布
- 机器学习中的训练数据和测试数据要求是在同一个分布中进行独立同分布产生。
- 学习过程中，假定这个分布存在，但是具体参数未知。
参数模型&非参数模型
- 参数模型假设总体服从某个分布，这个分布可以由一些参数确定，如正态分布由均值和标准差确定，在此基础上构建的模型称为参数模型；
- 非参数模型对于总体的分布不做任何假设或者说是数据分布假设自由，只知道其分布是存在的，所以就无法得到其分布的相关参数，只能通过非参数统计的方法进行推断。
- 参数模型和非参数模型中的“参数”并不是模型中的参数，而是数据分布的参数。
- 常见的参数机器学习模型有：
- 逻辑回归（假设数据服从伯努利分布）
- 线性成分分析
- 感知机
- 简单的神经网络
- 常见的非参数机器学习模型有：
- 决策树
- 支持向量机
- 朴素贝叶斯
- 复杂的神经网络
生成模型&判别模型
区别在于有没有显式计算分布。
- 判别模型是得到决策边界，判断样本为不同类别的概率，不显式计算分布，隐式学习到数据分布信息；
- 生成模型是显式计算样本数据与类别的分布信息，判别时计算样本为哪一类的概率更大。
偏差-方差分解
- 误差可以分解为偏差、方差和噪声之和
- 偏差：描述模型对于特定数据（训练集）的拟合效果,度量了学习算法的期望预测与真实结果之间的偏离程度，刻画了学习算法本身的拟合能力。
- 方差：描述模型在不同数据（训练集与测试集）上拟合效果的差别，度量了训练集的变动所导致的学习性能的变化，刻画了数据扰动造成的影响。
- 噪声：度量了在当前任务上任何学习算法所能达到的期望泛化误差的下界，刻画了学习问题本身的难度。
- 偏差-方差分解表明：泛化性能是由学习算法的能力、数据的充分性以及学习任务本身的难度共同决定的。
- 偏差-方差分解中，噪声也可以称作最优误差或者贝叶斯误差。如：在图像识别的问题中，人眼识别的错误率可以视作最优误差。
- 欠拟合：高偏差，低方差；
- 过拟合：低偏差，高方差。
优化
机器学习三要素：
- 模型：机器学习的目的，通过少的模型参数去表征大量数据的信息；
- 策略：评价模型的好坏，如：极大似然、最大后验等，具体到神经网络中就是损失函数；
- 算法：如何更好的去优化、训练模型，降低时间空间复杂度。
经验风险最小化&结构风险最小化&奥卡姆剃刀原理
- 机器学习的目标是期望风险最小化，也就是让模型拟合真实分布；
- 但真实分布无法完全得到，只能获得分布的一些数据，经验风险最小化的目的是使模型更好地拟合数据样本；
- 有限的采样数据与真实分布之间存在gap，结构风险是在经验风险最小的基础上加入先验知识，使得模型往更加合理的方向优化；
- 结构风险最小化策略符合奥卡姆剃刀原理的先验观点：能够很好地解释已知数据，且十分简单才是最好的模型。
参数估计
- 极大似然估计就是经验风险最小化的例子，拟合样本，使得在样本固定时，参数的似然值极大；
- 神经网络优化时，分类问题采用交叉熵损失，因为假设分类问题的类别服从伯努力分布；回归问题采用均方损失函数，因为假设回归问题的输出服从高斯分布。
- 最大后验估计就是结构风险最小化的例子，考虑到不同参数的先验概率不一样，用参数的先验概率乘以似然值得到后验概率，并最大化后验概率。
- L1、L2正则化先验的假设参数值应该不大。
过拟合
- 过拟合的原因是：将训练样本本身的一些特点当作了所有潜在样本都具有的一般性质，这会造成泛化能力下降。
- 过拟合无法避免，只能缓解，因为没有办法得到总体分布的全部信息，有限的样本中总是会有噪声。
缓解过拟合
- 正则化：通过加入先验知识，限制不合适的假设空间，如权重衰减，对应加入贝叶斯先验后的最大后验概率估计；
- 数据集增广：通过人工规则产生虚假数据来创造更多的训练数据，新产生出来的数据包含正确的重要信息，同时次要信息相互抵消。
- 噪声注入：包括输入噪声注入、输出噪声注入、权重噪声注入。将噪声分别注入到输入/输出/权重参数中。
- 早停：当验证集上的误差没有进一步改善时，算法提前终止。
PAC&&VC维
- PAC理论认为如果精度可以无限小称为强可学习，如果仅比猜测好一点则是弱可学习，集成学习boosting证明强可学习与弱可学习等价。
- 训练误差与泛化误差之间差异的上界随着模型容量增长而增长，随着训练样本增多而下降；因为随着模型容量增加，会把更多噪声识别成特征，而随着样本增加，噪声会被平滑。
- VC维理论对于机器学习算法有很好的指导作用，但是它在深度学习很难应用。因为边界太宽泛，且难以确定深度学习的容量。由于深度学习模型的有效容量受限于优化算法，因此确定深度学习模型的容量特别困难。
评估
泛化能力评估
- 留出法：直接将数据切分为三个互斥的部分（也可以切分成两部分，此时训练集也是验证集），然后在训练集上训练模型，在验证集上选择模型，最后用测试集上的误差作为泛化误差的估计。
- K折交叉验证法：数据随机划分为K个互不相交且大小相同的子集，利用K-1个子集数据训练模型，利用余下的一个子集测试模型。
- 留一法：假设数据集中存在N个样本，令K=N则得到了K折交叉验证的一个特例。
- 自助采样法：放回采样，随机森林选用此策略，会改变数据分布。
性能度量
- 混淆矩阵
| 真实/预测 | 正类 | 反类 |
|---|---|---|
| 正类 | TP | FN |
| 反类 | FP | TN |
准确率 (accuracy)：$A=\frac{TP+TN}{TP+TN+FP+FN}$，正确预测样本的占比；
查准率(precision)：$P=\frac{TP}{TP+FP}$，预测的正例的有多大比例是正例；
查全率(recall):$R=\frac{TP}{TP+FN}$，正例有多大比例被预测出来；
$F_1$分数：$F_1=2*\frac{P * R}{P+R}$，对查准率和查全率进行一个调和；
$F_\beta$分数：$F_\beta=(1+\beta^2)\frac{P * R}{\beta^2*P+R}$，可以调整查准率和查全率的权重，$\beta$越大时，查全率权重越大。
查准率和查全率都是越大越好；但是对于已有模型，这两个值是一对负相关的；他们的大小由区分正反类的阈值确定，阈值设得越高时模型越倾向于预测为反类，此时recall下降，precision上升，反之亦然。
P-R曲线
调整阈值可以得到不同的precision-recall对，进而得到P-R曲线。
- P-R曲线从左上角(0,1) 到右下角(1,0) 。
- 开始时第一个样本（最可能为正例的）预测为正例，其它样本都预测为负类。此时：查准率很高，几乎为1；查全率很低，几乎为0，大量的正例没有找到；
- 结束时所有的样本都预测为正类。此时：查全率很高，正例全部找到了，查全率为1；查准率很低，大量的负类被预测为正类。
ROC曲线
正确报警率（真正例率）：$TPR=\frac{TP}{TP+FN}$
误警率（假正例率）：$FPR=\frac{FP}{FP+TN}$
ROC曲线从左下角$(0,0)$到右上角$(1,1)$。
开始时第一个样本（最可能为正例的）预测为正例，其它样本都预测为负类。此时：真正例率很低，几乎为0，因为大量的正例未预测到；假正例率很低，几乎为0，因为此时预测为正类的样本很少，所以几乎没有错认的正例；
结束时所有的样本都预测为正类。此时：真正例率很高，几乎为1，因为所有样本都预测为正类；假正例率很高，几乎为1，因为所有的负样本都被错认为正类。
对角线对应于随机猜想模型。点$(0,1)$对应于理想模型；通常ROC曲线越靠近点$(0,1)$越好。
P-R曲线和ROC曲线上的每一个点都对应了一个阈值的选择，该点就是在该阈值下的(查准率，查全率) /(真正例率，假正例率) 。
相对P-R曲线，ROC曲线在正负样本变化时更加稳定，因为ROC曲线的两个指标是分开使用正样本和负样本的数据，因此当比例发生变化时，每一个指标使用的比值不变。
深度学习基础知识
基础
人工智能发展
- 人工智能：泛指与智能有关的技术
- 规则学习：硬编码知识。计算机不需要从数据中学习知识。
- 机器学习：不用显式编程的学习
- 经典的机器学习：人工设计特征。计算机从数据中学习到了“特征–>label”之间的映射。
- 特征学习：机器从数据中自动学习到特征，然后学习到了“特征 –> label”之间的映射。
- 深度学习：机器从数据中自动学习到了多层特征（深层特征由浅层特征来表达），然后学习到了“特征 –> label”之间的映射。
- 深度学习是端到端学习，自动学习特征和映射，不用像以前一样进行手工的特征设计。但目前的发展程度还很低，人工设计网络结构一定程度上还是属于特征设计，还是需要通过先验信息来限定特征结构、模型容量。
- 通过组合简单的概念（concept）来构建复杂的概念。如：在图片识别任务中，通过比较相邻像素的亮度，则容易地识别边缘；通过识别边的集合，则容易识别角和轮廓；通过识别轮廓和角的特点集合，则容易识别物体整体。
数据集&参数量
- 在大的数据集（数据中信息多）上，训练更大的网络更有可能得到更好的效果，而在小数据集上，模型的发挥空间小，效果更多取决于特征工程（人工先验知识）的能力。
- 数据量有限的情况下，模型容量并非越大越好；因为数据可以看成是用冲激函数在原分布上采样，随着模型容量的增大，一定会学到更多的噪声。
- 随着数据集的增大，一方面是数据提供的信息更多了，有利于提升泛化性能；另一方面是使得优化曲面更加平滑，降低优化难度。直观理解一个样本对于优化平面带来的是一个冲击，样本多了之后可以相互平滑，从数学上看，代价函数是多个样本的loss的平均，样本数越多时代价函数曲面更平滑，更有利于优化，但一个batch的样本数适当少一点可以加快收敛速度和提供随机性。
- 现在深度模型的参数量越来越大，但并不是参数越多越好，应该和数据量、场景相匹配，尽量用更少的参数达到相同的效果以增加模型的泛化能力。
可辨识性
- 如果一个训练集可以唯一确定一组模型参数，则该模型称作可辨认的。
- 带有隐变量的模型通常是不可辨认的。因为可以批量交换隐变量，从而得到等价的模型。如：交换隐单元和的权重向量。也可以放大权重和偏置倍，然后缩小输出倍，从而保持模型等价。
- 模型可辨认性问题意味着：
神经网络的代价函数具有非常多、甚至是无限多的局部极小解。
由可辨认性问题产生的局部极小解都具有相同的代价函数值，它并不是代价函数非凸性带来的问题。
假如存在一组参数使得模型、数据达到全局最小，可以通过一些变换得到无数组全局最优参数。
神经网络
激活函数
- 对输入做非线性变换，如果神经网络中没有非线性变换，则最终退化为简单线性变换（矩阵运算）；
- 一般解释sigmoid函数在深度学习上的劣势通常是从梯度消失的角度来解释，也可以尝试另一个角度：sigmoid函数就不是为深度学习而生的，它原本就是在浅层模型（逻辑斯蒂回归）中将数值从无穷区间映射到0-1之间的工具。现在这一工作基本由softmax替代，所以替代sigmoid函数的不是relu，而是softmax，另外softmax本身就是对sigmoid的扩展。Tanh几乎在所有场合都优于sigmoid函数，除非要求输出0-1，否则需要考虑sigmoid的时候完全可以用tanh取代。
- Relu函数虽然有一半的输出处于0导数，但却并不是说会有一半的神经元处于未激活的状态，因为对于不同的样本可能函数输入会很不相同，有的样本输入大于0，有的样本输入小于0，这样就不能算未激活。
- 每一个神经元都是一个特征学习器，因此怎样的激活函数更好也可以从这个角度展开分析。所以前馈网络的隐单元更适合relu，而tanh（sigmoid）用在需要限制输出的地方，如循环神经网络中防止梯度爆炸。
先验
- MLP就可以表达各种特征，之所以需要设计、发展各种结构，一方面是直接用MLP会参数爆炸；另一方面是在平衡困难：直接用MLP的话是把困难都推给了优化过程，因为对模型不加限制会使得很难训练到想要的参数，而设计各种结构是通过加入先验信息来限制模型能力，使得模型往想要的方向前进。
- MLP之于神经网络，就如同高斯分布之于分布，是在没有额外先验知识时的选择，当有额外先验知识时，就应该加入先验知识，以使得模型更加符合实际。
- 学到的参数就是在表征一些模式，神经网络不同的层结构（全连接、卷积…）是不同的特征学习器，它们有着不同的先验假设，适合学习不同的特征。
- 从计算图上看，权重衰减的正则化也是一种直连，但是并没有通过权重衰减建立与标签信息的联系，只是建立与一些先验信息的联系。
优化
反向传播
- 反向传播是对多元微分的一种实现。利用动态规划的思想，用空间换时间，存储中间结果，避免链式法则中的大量重复计算。
局部极值
- 在极高维的时候，鞍点出现的概率要远远大于极小点，所以神经网络优化不下去很可能不是因为极小值点。
- 可以绘制梯度范数随着时间的变化：
- 如果梯度范数没有缩小到一个很小的值，则问题的原因既不是局部极小值引起的，也不是其他形式的临界点（比如鞍点）引起的。
- 如果梯度范数缩小到一个很小的值，则问题的原因可能是局部极小值引起的，也可能是其他原因引起的。
- 当位于函数值较低的区间时，黑塞矩阵的特征值为正的可能性更大。这意味着：
- 具有较大函数值的临界点更可能是鞍点，因为此时黑塞矩阵的特征值可能既存在正值、也存在负值。
- 具有较小函数值的临界点更可能是局部极小值点，因为此时黑塞矩阵的特征值更可能全部为正值。
- 具有极高函数值的临界点更可能是局部极大值点，因为此时黑塞矩阵的特征值更可能全部为负值。
- 使用海森矩阵的优化算法需要更大的batch-size，因为海森矩阵的条件数过高，对于偏差的容忍度差。
牛顿法
- 梯度下降法不能保证代价函数一定下降，牛顿法更不能。
- 梯度下降法利用一阶泰勒展开，下降要求在小领域内；
- 牛顿法利用二阶泰勒展开，试图直接跳到极值点，在凸二次函数下可以一步达到最优，在其它凸优化情况下也可以较快达到最优，但是在非凸问题时没有保证，它的目标是尽快把每个参数都送到极值点，因此在多参数的时候大概率会跳到鞍点处，因为鞍点出现的概率要远远大于极大值点和极小值点。
- 所以牛顿法不适合非凸优化。
- 牛顿法要应用在非凸优化时需要正则化使得海森矩阵正定，这只适合负特征值绝对值较小时，另外海森矩阵的边长等于参数量，所以在参数量极大的深度学习应用中，牛顿法的巨大计算和存储代价也是致命缺点。
超参数调优
- 网格搜索；随即搜索：重要的超参数用网格搜索，不重要的超参数用随机选择，以降低复杂度；
- 动态资源分配：类似于多臂老虎机问题，选择出最优的臂；目的是使得效果不好的组合可以快速被淘汰掉，随着优化的进行，不确定性减小，就可以淘汰掉更多的臂；
- 对$n$组超参数组合，进行一定程度优化；
- 保留效果最好的前一半的组合，淘汰其它；依次循环得到最优的参数组合；
- 贝叶斯优化：认为超参数存在某种分布，可以利用已经尝试的超参数对分布进行估计，进而预测收益最大的组合，进而减少实验次数；
FTRL
- 出发点是在线学习与模型稀疏性；在线学习应对工程场景下大模型、大数据量更新代价大的问题；稀疏性应对特征量极大的场合（推荐系统），减少特征使用量；
- 直接的解决方案是SGD+L1正则化，但是SGD的随机性无法保证在全局应该稀疏的特征在每次更新的时候都稀疏；
- FTRL与SGD+L1正则化几乎等价，可以看成是一种优化版本；
- $w_{t+1}=argmin_w(\sum^t_{s=1}g_sw+\frac{1}{2}\sum^t_{s=1}\delta_s||w-w_s||^2_2+\lambda||w||_1)$
训练技巧
- 模型是非线性的，也无法直接求解出最优解，所以大的方向是通过梯度下降，贪心地逼近更好的解；各种策略都是服务于这个贪心的过程。
- 深度学习的方法都显得非常技巧，一个原因是因为深度学习研究的是高度非线性的系统，所以往往无法通过个别高度概括性的工具应对各种问题。所以研究深度学习需要理论结合实际，不能纸上谈兵。
学习率
- 基于梯度的优化算法中，每个参数都有一个最佳的学习率范围，但实际中不可能给每个参数都设置一个学习率超参数，而一个学习率又无法满足所有的参数。这个时候就有了很多的优化角度：
- 对数据做归一化缩放操作、加批次归一化层以改善参数的一致性；
- 自适应调整学习率；
- 动量法自适应调整梯度（动量）等。
- 第k步的学习率记做$ϵ_k$ ：
- $\sum_k ϵ_k=\infty$：保证无论多远，梯度都可以更新到；
- $\sum_k ϵ_k^2<\infty$：保证更新过程稳定收敛；
- 在随机梯度下降中，学习率固定，因此随着梯度大小变化，参数更新量可能为任意数。而RMSProp动量法通过自适应的方式将参数更新量从无穷区间映射到了大约$[-ϵ,ϵ]$（定性得到的大约区间，不一定）。
- batch size大时，优化曲面更加稳定，可以设置更大的学习率；反之batch size小时，学习率要设置的小一些；
- 周期性得让学习率随轮次减小以适应新的优化情况：
- 指数衰减：$\mu=\mu_0e^{-k}$
- 反比衰减：$\mu=\frac{\mu_0}{1+k}$
- 大的梯度容易跳出局部极值，但是只能学到简单的pattern，小的梯度不容易跳出局部极值，但是有利于学到复杂的pattern。在训练过程中，学习率一般是要逐步减小的，但是在陷入局部极值的时候增大学习率或许可以帮助跳出。
- 判断学习率大小，随着轮次，损失函数：
- 下降缓慢：学习率太小，梯度下降慢；
- 下降适中、平稳：学习率合适；
- 下降快但很快停止下降：学习率偏大，梯度更新震荡，无法进一步下降；
- 上升：学习率过大，梯度更新发散；
- scheduler：对学习率进行管理；
- 学习率衰减：有单因子、多因子、多项式、指数、余弦等方式
- 预热：开始的学习率太大会使得模型发散，太小又会使得整个训练过程变慢，因此可以使用预热的方式，让学习率逐步增加到一定程度，然后再进入衰减阶段。
- AdaGrad：将参数历次梯度的斜边的倒数用来自适应调整学习率；梯度大的参数学习率小；很容易还没优化好就停止了；
- RMSProp：在AdaGrad的基础上，将累计求和的部分改成了指数滑动，避免自适应学习率快速衰减的问题，自适应学习率可以根据需要变大和变小；
- AdaDelta：在RMSProp的基础上，在分子上加入参数变化量的指数滑动斜边，进一步调和，让更新大的参数的学习率可以不太小，缓解自适应学习率的波动；
- Adam：在RMSProp的基础上，加入动量法，然后对动量、斜边进行一些调和，改善早期的偏差；
- 各个优化算法都是从两个方面进行调整：
- 动量方面，平滑梯度、动量
- 斜边方面，对梯度、动量进行正则化，最终使得各个参数的优化值比较均匀、一致。
- 所以最后的优化方向并非是梯度下降最快的方向，或者说梯度下降最快的方向并不是和合适的方向
早停
- 随着训练的进行，模型基本学习了数据中的有效信息，开始拟合数据中的噪声，此时应该及时停止训练，降低过拟合；
- 随着训练的进行，泛化/测试误差先下降，后上升，在谷底时即是早停的最好时机；
随机/批次梯度下降
- 样本中的信息存在冗余，大量样本都对梯度做出了非常相似的贡献，使用更多样本来估计梯度的方法的收益是低于线性的；
- batch随机梯度下降中，只要没有重复使用样本，它就是真实泛化误差梯度的无偏估计；
- 计算开销更小；
- shuffle和小批次提供一定随机性，有利于跨过局部极值
- iteration：更新一次梯度
- epoch：所有样本用一遍
梯度截断
- 对梯度按阈值截断或按模截断，以避免梯度爆炸；
特征scaling
- 对每一个特征，将数据减去该特征的均值并除以标准差，改善不同参数的一致性，使得超曲面更加均匀一些。
动量Momentum
- 使用动量更新参数而不是直接用梯度，动量与上一次的动量和现在的梯度相关，或者说现在和以前的梯度共同决定；
- 通过这种方式可以调和不同参数的更新值，方向相同的梯度会变大以加快更新速度，方向反复变化的梯度会变小以降低震荡；
- Nesterov加速梯度：先用历史动量更新参数，然后计算梯度并更新，调整先后顺序；
正则化/权重衰减/weight decay
- 通过加入先验知识，避免参数值处于不合理的区间：
- L2正则化：先验假设参数取值服从均值为0的高斯分布，越大的参数被打压得越多；
- L1正则化：先验假设参数取值服从均值为0的指数分布，大小参数一起打压，可以带来参数稀疏性；
- 同时加入L1和L2，调和两种的效果
Dropout
- 做法：训练时，在Dropout层按一定概率随机将一部分神经元置0，未置0的神经元值除以保留的概率；
- 原理类似：bagging+子模型参数共享；
- 未置0神经元的处理是为了使数据无偏；
权值初始化
- 权重初始化应该尽量保证前向传播和反向传播过程中的值得分布不发生变化，分布中的均值大都为0，而方差应该尽量不变，否则深层网络的连乘会导致梯度消失或爆炸，以及饱和等问题。
- 初始化到0无法学到任何东西，因为导致大量参数的同质，应该采用随机初始化。
- Xavier的初始化可以保证线性全连接层传递后的方差不变，但是这样对relu这样的激活函数不好，因为relu有一半的是没有值，所以方差应该大一些；
局部正则化/Local Response Normalize
- $b_i=\frac{a_i}{k+\beta\sum_ia_i}$；
- 引入竞争，更可解释，同时稳定数据分布，类似Batch Norm等标准化层效果。
残差连接
- 深度网络难以训练有许多原因，除了容易梯度爆炸和梯度消失外，还包括参数的依赖，高层参数靠近输出相对容易学习但是高层参数又依赖底层参数，底层参数优化不好，高层参数也无法优化；残差连接可以降低特征学习难度；
- 利于梯度回流，缓解梯度消失；
数据增广
- 可以看成增加模型的等变性，也可以看成抑制数据中的噪声；
- 图像的数据增广方式包括基本的旋转平移等外，还可以通过风格增广；
门结构
- 有助于底层信息直通
其它
- 各种类型的网络层与层之间的参数不应该缩减太快，因为后面的后面神经元学习的特征很难有效利用前面的众多特征。
- 参数共享也是促使模型学习主要模式，同时也可以起到抑制过拟合的作用，因为有限的参数要尽量满足主要特征，就自然忽略了噪声。
标准化层
- 一说可以防止数据分布的变化（内部协变量偏移）带来性能下降；
- 另一说模型的优化曲面发生变化，变得更加平滑，非凸性减弱，使得训练变得容易，即利普希茨系数严格降低；
Batch Norm
Batch Norm：在对一个通道内，对一批次数据的每个特征，减均值除标准差，同时再加入一对可学习的均值方差参数。
- 如果不是卷积网络，Batch Norm也可以是对于单个神经元的;
- 训练过程使用的减均值除方差是通过一批的训练数据计算得到均值、标准层，测试的时候是通过训练过程的指数滑动平均得到;
- 通过Batch Norm，深度模型更好地收敛训练，即使对于比较大的学习率也有较好的效果;
- Batch Norm高度依赖于mini batch的大小，batch size较大的时候，Batch分布与整体分布类似，Batch Norm的效果往往好于Other Norm；反之不适合batch size 较小的场景，如：在线学习（batch size=1 ）；
- 不适合RNN网络，因为不同样本的sequence的长度不同，因此RNN的深度是不固定的。同一个batch中的多个样本会产生不同深度的RNN，因此很难对同一层的样本进行归一化；
理解Batch Norm层的一个角度：
- 原来的网络就像一大段代码叠在一起，可读性差（层与层之间相互依赖，难以训练）；
- 加上Batch Norm层之后就像把以前的代码分割成了一个个子程序，依此调用，程序之间有清晰的接口，因此阅读和调试都更加容易；
- 这就像是一种解耦操作，让各个层专注自己的任务（特征学习）。
- 同时也是在改善参数的一致性。
在激活函数之前、还是之后进行Batch Norm都可，在激活函数之前进行的更常见；
Batch Norm层前的全连接层一般不需要带偏差项，因为偏差项会被吸走，卷积层可以带。
Layer Norm
- 因为BN是在批次维度进行，所以叫批次标准化，还可以在其他维度进行，得到不同种类的标准化。
- Layer Norm不依赖于batch size，适合在线学习，也适合于RNN网络。
Instance Norm
- 对于GAN、风格迁移这类任务上，Instance Norm效果要优于BN，因为每张图片自己的风格比较独立，不应该与batch中其它图片产生太大联系。
- Instance Norm也不依赖于batch size，适合在线学习，也适合于RNN网络。
卷积神经网络
卷积层
- 在MLP的基础上增加了两个先验：
- 局部性连接
- 参数共享
- 这两个先验假设使得卷积网络相对于MLP的参数量大减，泛化能力更加强，可以更好地学习到图像数据中的重要模式（主要指像素之间的变化关系、组合关系，所以非常适合计算视觉领域，当然也可以用在同样具有类似重要特征组合方式的领域）。
- 卷积和互相关都是由函数到函数的算子，其中卷积包括反转和求和两个过程，互相关只有求和；所以卷积神经网络是披着卷积外衣的互相关网络。
- 卷积核的大小也会影响卷积核的表达能力，参数量小的卷积核所能产生的可能性也少。
- 每个卷积核得到一个通道的输出，增加卷积核数量，可以从更多角度进行特征提取
- 等变性：$f(T(x))=T(f(x))$，卷积层参数共享带来一定的平移等变性，等变性可以看成是对数据噪声的一种抑制，如图片分类中无论物体在图片的中央还是边缘，都应该得到一样的结果，这种位置信息就是和分类无关的噪声；
- 卷积核参数均值影响特征图亮度，值相加和为1时处理之后的图像与原始图像的亮度相比几乎一致，小于1时减小，大于1时增大；
填充&&步幅
以二维输入为例，输入的高宽分别为$n_h$，$n_w$，卷积核的高宽分别为$k_h$，$k_w$，填充的高宽分别为$p_h$，$p_w$，步幅的高宽分别为$s_h$，$s_w$，则输出形状为：
$$
\lfloor(n_h-k_h+p_h+s_h)/s_h\rfloor \times \lfloor(n_w-k_w+p_w+s_w)/s_w\rfloor
$$
当步幅为1时，设置$p_h=k_h-1, p_w=k_w-1$，输出的形状与输入的形状一致。
pooling层
- 池化层：降低数据量；
- max pooling
- mean pooling
- 全局平均池化：提供平移不变性，丢失很多细节
- 不变性：$f(T(x))=f(x)$，池化层带来一定不变性；
经典网络
- LeNet：最早最简单的卷积网络
- AlexNet：它是第一个在大规模视觉竞赛中击败传统计算机视觉模型的大型神经网络；
- 使用重复块的网络（VGG）：它利用许多重复的神经网络块；
- 网络中的网络（NiN）：它重复使用由卷积层和1*1卷积层（用来代替全连接层，相当于是按照像素做全连接）来构建深层网络;增加非线性，降低参数量；最后的通道数等于分类的类别数，全局平均池化得到类别概率。
- 含并行连结的网络（GoogLeNet）：它使用并行连结的网络
- 通过多尺度卷积核利用不同窗口大小的卷积层和最大汇聚层来并行抽取信息，学习不同尺度特征；
- 分支训练：网络分叉，可以将梯度信息更好的传递到底层，防止梯度消失。
- 残差网络（ResNet）：它通过残差块构建跨层的数据通道，是计算机视觉中最流行的体系架构；
- 稠密连接网络（DenseNet）：计算成本很高，同时也带来了更好的效果。
其它策略
- 1*n卷积：降低参数量；
- Dropout：类似bagging，集成学习的效果，降低方差；
- 数据增广：变相增加数据量，抵消不重要信息，加强核心成分，避免模型学偏；
- 空洞卷积：多尺度+减少参数量；
- BN：应对数据分布漂移，避免数据整体进入饱和区，进而缓解梯度消失和梯度爆炸的问题；
循环神经网络
- RNN在MLP的基础上加上（不同时刻/序列点）参数共享的先验。
- RNN在前向传播和反向传播的时候都有矩阵乘幂，序列略长就必然崩溃，实用性非常低，主要是思想重要。
- 双向循环神经网络假设上下文都会对当下有影响，因此从两个方向传递信息；时序数据中，后面时刻的数据对前面时刻的数据没有因果关系，但是可以有相关关系；
- LSTM在RNN上加入门控逻辑（遗忘、输入、输出），选择性遗忘和更新信息，可以应用在序列不太长的情况；
- GRU整合门数量（更新、复位）并进一步减少计算量（不区分cell和h），优化结构。
- LSTM、GRU一般不会用很深，往往2层最常见
- attention机制可以解决长时间依赖的问题：不再去记录中间信息，而是学习捕获数据间的联系，因此不受长序列信息丢失的影响；
- 循环神经网络中sigmoid的0～1区间用于模拟门的开闭；tanh用于信息激活函数，线性区间大于sigmoid，同时防止relu可能带来的信息爆炸；
- 编码-解码架构可以应对seq2seq问题中输入输出序列长度不一致的情况；
图神经网络
图
- 图的组成：顶点，边
- 有向图：边有方向。
- 无向图：边没有方向，可以看成有向图的边成对出现。
- 带权图：边有权重。
度
- 有向图度：
- 入度：指向自己的边数
- 出度：自己发出的边数
- 无向图度：连接边的数量
邻接矩阵&临接表
- 邻接矩阵是方阵，宽度等于节点数，元素为1代表节点之间有边连接，邻接矩阵浪费空间；每一行相当于一个节点的onehot编码
- 无向图的邻接矩阵是对称阵，有向图不一定。
- 邻接表节省空间但效率低，cache不友好。
子图
节点和边都是一个大图的子集。
连通性
- 连通图：无向图中所有节点都可以连接在一起。
- 连通分量：连通子图数称，连通图的连通分量为1。
- 强连通图：有向图任意节点可以相互到达
- 弱连通图：有向图不是强连通图，但是作为无向图时是连通图。
最短路径
- 两个节点之间的最短距离，可能是边数，如果边权重不一样就是最短的边的和。
- 图直径：图所有节点的最短路径的最大值
节点重要性
- 度中心性：节点度数/(n-1)；即度越高，度中心性越高。
- 特征向量中心性：对邻接矩阵求特征值、特征向量，最大特征值对应的特征向量就是各个节点的特征向量中心性。
- 不只看边数，还可以反映连接节点的重要性。
- 中介中心性：经过自己的最短路径数/总的最短路径数
- 如果有的节点对最短路径可以有多种走法，则分数平均。
- 连接中心性：(n-1)/该节点到其它节点的最短路径之和。
- 即节点越靠中心，分母越小，值越大。
PageRank
- 边的PageRank值为源节点的PageRank除以出度，节点的PageRank值等于入边的PageRank值之和；交替计算直至稳定。
import networkx as nx # 可以从其它的数据结构中导入，如pandas邻接表 G = nx.from_..() nx.degree(G) nx.connected_components(G) ...... nx.pagerank(G) ......
拉普拉斯矩阵
- $L=D-A$，其中$A$为图的邻接矩阵，$D$为图的度矩阵（对角）；对拉普拉斯矩阵进行特征值分解可以得到一系列特征值和对应的特征向量。
图卷积
- 卷积是将数据从一个域转换到另一个域中，如信号处理领域中从时域到频域，图像处理中从图片到特征图，图领域中从图到对应特征向量；图像中的每一个特征图是对图像的一种分解，图中的特征向量也是对图连接关系的一种分解。
- DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in neural information processing systems. 2016: 3844–3852.
- 在图结构的数据上进行特征提取，数据挖掘；GCN是CNN在图数据上的扩展，将卷积特征提取方式从欧几里得空间迁移到非欧几里得空间。
- BATTAGLIA P W, HAMRICK J B, BAPST V, 等. Relational inductive biases, deep learning, and graph networks[J]. arXiv preprint arXiv:1806.01261, 2018.
- BRONSTEIN M M, BRUNA J, LECUN Y, 等. Geometric deep learning: going beyond euclidean data[J]. IEEE Signal Processing Magazine, IEEE, 2017, 34(4): 18–42.
数据预处理&特征工程
数据预处理
数据标准化
- 将各个维度的数据变化范围变换到一个相近的区间，便于梯度下降等场景；
- 有的算法不必要，如决策树；
- 划分的训练集、测试集等需要使用相同的标准进行处理。
z-score标准化
中心化（zero-centered）+缩放（scale），减均值除标准差
min-max标准化
减$min$，除$|max-min|$。
数据正则化
- 对每个样本将p范数放缩到1，以便于求样本相似度等运算
- 标准化是对特征的操作，正则化是对样本的操作
唯一属性
- 有一些特征如id是每个样本都不同，这样的特征对于刻画样本自身属性没有帮助，应该直接删掉；
- 有的场合，如推荐中，id特征也可以保存一些信息，按需要可以保留。
缺失值
- 直接使用带缺失值的样本，如决策树类的少量算法可以直接将缺失值作为一种情况进行处理。
- 直接删除有缺失值的样本，简单，数据纯净，但是浪费了一些信息，在缺失值较多的场合不适用。
- 数据量较多是使用的策略，因为其它数据中已经有冗余信息，而缺失数据带有噪声；
- 数据量非常不足时不适合使用该策略。
- 缺失值补全，可以尽量全面的利用信息，但是补全方式不恰当时效果适得其反；相当于加入先验。
- 均值插补：连续特征用均值，离散特征用众数；
- 同类均值插补：按类别进行均值插补。
- 建模预测：建立模型预测，缺点是，如果预测的特征没有关联那预测的结果就没有意义，如果有关联预测出来的信息也是冗余的，也没有意义，所以用的不多。
特征编码
特征二元化
将数值型特征转化成布尔型特征，通过一个阈值超参数划分特征
独热码
- 可以处理非数值特征；
- 降低单个特征的重要性；
- 对于有大小关系的数值变量，用独热码表示会丢失信息；
离散化
- 分桶
特征选择
- 特征选择的时候并不是选择最好的一组特征，因为特征之间往往存在耦合性。
- 可以使用贪心算法，每次增加一个能给效果提升最大的特征。
不进行特征选择的坏处
- 相对样本量小，维度灾难，模型泛化能力弱
- 计算量大
- 无关特征误导训练方向
稀疏表示和字典学习
- 对样本 $x_{i}$, 通过交替寻优的方式学习字典 $\mathbf{B}$ 和稀疏表示$\alpha_{i}$，优化目标为：$\min_{\alpha_{i}}||x_{i}-B\alpha_{i}||{2}^{2}+\lambda\sum{i=1}^{N}||\alpha_{i}||_{1}$
多分类问题
将二分类模型用于多分类问题：
- 一对多，为每一个类别训练一个分类器，非常容易陷入样本不平衡；
- 一对一，为每一对类别训练一个分类器，计算量太大；
- 多对多，每次都将若干个类作为正类，若干个其他类作为反类。
类别不平衡问题
- 对多的样本欠采样，可能丢失一些重要信息，常用方法是将反类划分成若干个集合供不同学习器使用，这样对每个学习器来看都是欠采样，但是全局来看并不会丢失重要信息。
- 对少的样本过采样，SMOTE方法：对于一个样本，从其同类近邻中随机选取一个点，在这两个点之间随机插值。
- 极不平衡时将问题看作单分类问题或异常检测。
聚类
- 通过一些方式将数据划分为多个簇（类），让簇内的数据尽量相似，簇间的数据尽量不相似。
- 聚类往往是其它工作的预工作，而不是最终结果。
相似度量
- 很大程度上决定了聚类效果。
- 不同特征的数值不一定适合直接计算距离。
距离基本要求：非负性、对称性、三角不等式。
p范数：
- 0范数（非0数）、1范数（曼哈顿距离）、2范数（欧氏距离）、无穷范数（最大值）。
- p值越大时，绝对值大的维度起到的作用越大，反之亦然。
- 各个维度独立计算。
马氏距离：广义距离
各个维度不再独立计算，而考虑到它们之间的联系，通过数据的协方差矩阵来联系。
也可以不使用协方差矩阵，而通过学习得到联系矩阵。
原型聚类
对数据分布有一个先验的假设，然后去计算出分布的参数，如K-means、混合高斯分布。求解参数的过程常常是使用EM期望最大的思想，交替寻优得到。
K-means
- 选取K个样本作为K个簇初始中心，根据距离远近将其他样本硬划分到各个簇中；
- 根据簇中的样本计算的中心/重心作为新的簇中心；
- 循环执行前两步，至簇中心稳定，常用手肘法判断。
- K-means可以看成C-means的特殊情况，在区分类别上一硬一软。
混合高斯分布
是K-means更加一般的情况，每个样本不是硬的属于每个簇，而是以一定概率属于各个簇；每个簇有均值、方差、权重。
- 初始化K个簇的均值、方差、权重，计算每个样本有多大比重/概率属于各个簇；
- 根据样本的归属，重新计算各个簇的均值、方差、权重，
- 循环执行前两步，至取值稳定。
谱聚类
将数据点看成一张图，然后对图进行切分，使得子图内部连接程度高，子图间连接程度低。
定义数据点的相似度/边，构建拉普拉斯矩阵$L=D-W$，也可以对拉普拉斯矩阵进行规范化；
对拉普拉斯矩阵进行特征分解，取对应特征值最小的几个特征向量，可以构建出数据新的表示；
用该表示用其它方法（常见的K-means）对数据进行聚类。
- 特征分解后，每一个特征向量代表一种连接模式，大特征值的特征向量代表比较普遍的连接模式，区分度较低，因此优先选用小特征值的特征向量。
- 同PCA对比，这体现了聚类和降维的区别，降维是找共同模式，聚类是找特殊模式。
层次聚类
密度聚类
分布聚类
生成模型
EM算法
EM算法可以看成极大似然估计在数据有缺失时的推广：
- 数据属性完整的时候知道完整的数据信息，直接估计分布的参数，即求极大似然；
- 缺失数据信息的时候，需要交替寻优，即交替求极大似然和极大概率。
分布学习-数据生成
常见的方式包括VAE和GAN，这两种方式，这两种方式的异同可以从许多角度来看.
| 角度 | VAE | GAN |
|---|---|---|
| train stage | one stage | two stage |
| distribution learning | 对正例样本进行泛化，得到分布，正则化系数越大，泛化程度越高 | 用生成器得到负例，负例逼近正例共同得到分布 |
| distribution feature | 比较稳定，受限于样本feature，发挥空间相对较小 | 不确定性大，每次得到的分布可能很不一样，可能得到正样本中完全没有的feature |
| 优化角度 | 通过分布变换并重构正样本来使得编码器和解码器学到分布 | 通过对抗方式，共同进化 |
| loss组成 | 重构误差 + 先验分布误差 | 生成得分误差 & 判别误差 |
| loss粒度 | pointwise loss | 分布匹配loss |
| 对抗部分 | 重构与正则（泛化） | 生成器与判别器 |
| 对抗方式 | 重构数据与增加泛化性 | 生成接近正样本的数据与判别出假数据 |
| 生成数据质量 | 像素维度控制，比较稳定，倾向于局部信息，图片质量低 | 整体控制，容易跑偏，图片更清晰 |
变分自编码器
变分自编码器本质上是希望学习数据的分布，编码器将原始数据分布映射到某个标准分布（如：正太分布、均匀分布），解码器再将标准分布映射到数据分布，最终编码器和解码器就都学习到了原数据分布的信息。其中解码器可以用于生成新数据。
- 变分自编码器不是直接让隐变量Z符合标准正太分布，而是让每个样本生成的均值方差接近标准正太分布（均值接近0，方差接近1）
- 重参数技巧是为了解决采样过程无法求导
- KL散度相当于正则项的作用，让编码器得到的量以及重参数后的隐向量尽量接近标准正太分布。
- 当decoder还没有训练好时（重构误差远大于KL loss），就会适当降低噪声（方差）这会使KL loss增加，使得拟合起来容易一些（重构误差开始下降）；反之，如果decoder训练得还不错时（重构误差小于KL loss），这时候噪声就会增加（KL loss减少），使得拟合更加困难了（重构误差又开始增加），这时候decoder就要想办法提高它的生成/泛化能力了。
- 重构的过程是希望没噪声的，而KL loss则希望有高斯噪声的，两者是对立的。所以VAE内部其实是包含了一个对抗的过程，只不过它们两者是混合起来，共同进化的。
- 变分：对泛函求极值
注：
泛函：函数到数值的映射，如：KL散度
算子：函数到函数的映射，如：梯度
生成对抗网络
降维
维度灾难
- 随着特征数的增加，特征空间变得越来越稀疏，需要极多的数据才能有较好的估计效果。即增加维度有利于可分性，但不利于了解数据分布属性。
- 在样本不变的情况下，特征维度的增加会使得样本的分布越来越稀疏，虽然容易分开，但数据分布的可信度越来越低，越来越难以得到置信结论。
降维思路
- 各种降维都是在原空间中找一些重要的方向，使得数据在这些方向上的信息能够尽量代表整体信息；
- 寻找重要方向的过程往往都涉及矩阵的特征值分解，不同降维方法使用的矩阵不同，因此得到的方向不同。
PCA降维
- 寻找数据方差最大的几个方向保留下来；
- 使用到的是数据的协方差矩阵。
- 核心优化目标：$J(w)=w^T S w$
- 换一个角度：将每个样本放成一行，得到矩阵，做奇异值分解，右奇异矩阵就是各个成分，左奇异矩阵与奇异值的乘积就是各个样本在各个成分上的分量。
奇异值分解（SVD）
- 将矩阵分解为左奇异矩阵+奇异值+右奇异矩阵；
- 是一种能够从非常本质的层面展现矩阵信息的工具；
- 左奇异矩阵：将原矩阵的行看作特征，列看作样本，得到投影方差降序递减方向向量，也是空间的一组标准正交基。
- 右奇异矩阵：将原矩阵的列看作特征，行看作样本，得到投影方差降序递减方向向量，也是空间的一组标准正交基。
- 奇异值：对应向量的方差。
- 矩阵运算就是做空间转换，例如：右乘向量就是对向量按右奇异矩阵的方向分解，并投影到对应的左奇异矩阵方向，同时乘以相应权重（奇异值）。
有监督降维
LDA
- 在知道数据类别的时候进行降维，目标是使得类间方差尽量大，类内方差尽量小；
- 使用到的是类间协方差矩阵和类内协方差矩阵。
核心优化目标：$J(w)=\frac{w^T S_b w}{w^T S_w w}$
非线性降维
自动编码器
- 通过重构误差最小来自动学习低维表示；
- 可以看成PCA的推广，当只有一个中间层，且不使用激活函数时，等价于PCA。
ISOMAP
- 计算流形上的相似度（最短路径），然后用MDS（多维缩放）来映射到低维；
- 效果受限于最近邻的计算。
LLE
获取样本局部嵌入信息，并使低维表示保持这一信息。
集成学习
- 集成学习与深度学习有异曲同工之妙，如：bagging类似于广度网络（dropout机制），boosting类似于深度残差网络，同时每一层都直连到输出。
- 许多模型如决策树、SVM、神经网络等都可以通过增加参数量等方式持续降低训练误差，但这种训练误差下降一般伴随着方差的明显增大，因为越往后会更多的拟合噪声；而集成学习的策略每次训练新的基学习器都会优先拟合重要特征，每个基学习器的参数量有限。
boosting
- 相比深度学习，集成学习boosting的训练过程类似于逐层预训练，在优化上的困难要小得多，因此数据集适合集成学习时，集成学习比深度学习更有优势。同时集成学习的参数量往往要小得多，充分利用了参数的能力，且参数相互制衡，因此往往不容易过拟合。当然boosting不容易过拟合的一个重要保障是要用一些简单的模型作为基模型。
- 同时集成学习同时利用所有学习器的结果，类似于深度学习中的直连，将所有层都直接和输出连接。
bagging
bagging可以抑制过拟合、降低方差，提高模型稳定性，因此适合使用偏差小、方差大的模型（或者说能力比较强的模型）作为子模型。
Adaboost
- 训练新的分类器以降低训练误差，每次调整样本权重；
- Adaboost（Adaptive Boosting）集成分类中，错误率越高的分类器，占最终分类器的比重越小，同时对于样本权重的调整越小，反之亦然。
- Adaboost每一步都是计算前向分步算法的最优解：
$(\beta_m, \gamma_m)=argmin_{\beta,\gamma}\sum^N_{i=1} L(y_i,f_{m-1}(x_i)+\beta B(x_i|\gamma))$ - 每次增加新的学习器，训练误差严格下降。
随机森林
- bagging+决策树+自助采样法+随机子空间；
- 随机子空间：每一棵树随机采样一部分特征来使用，增加多样性，避免模型总是使用最强的几个特征，将数据解释限制在狭窄的范围内；
梯度提升树（GBT）
提升树（BT）：
- boosting+决策树；
- 训练新的决策树来拟合现在模型的残差；
- 可以看成是将Adaboost中的分类器系数置为1.
梯度提升树：
- 新的决策树拟合负梯度而不是残差，限制更少，应用场景更加广泛，损失函数选择范围更大；
- 负梯度和残差除了形式不同，也更加灵活，选择不同的损失函数可以调整优化偏好，如：平方损失函数倾向于先降低大的训练误差，绝对值损失函数倾向于带来样本训练误差的稀疏性；
梯度提升树的正则化
- 学习率：可以加入学习率控制学习进度；不直接使用新训练的树来更新模型，而是会加上一个较小的学习率来提高泛化误差。
- 子集采样：从原始数据集中不放回采样一个一个子集，引入随机性，虽然不是自助采样，但也是起到bagging效果；
- 最小叶节点样本数：限制叶节点至少有的样本数量，低于该数量事直接停止训练，降低过拟合；
- Adaboost在训练结束前都可以保证训练误差下降，梯度提升树则不一定。
xgboost
相对于基本的梯度梯度提升树：
- 将目标函数进行二阶泰勒展开，而非只使用一阶信息；
- 使用结构风险最小化，考虑节点数量和节点值大小；
分解结点
基本思路
循环遍历所有特征的所有分裂点，计算能够带来的增益，选择增益最大的情况对结点进行分裂，如果增益都不大于0则停止。
近似算法（优化）——分桶：
减少分裂次数，连续特征按连续值百分位分桶，离散特征按离散值分桶；
全局模式：
- 在算法开始时，对每个维度分桶一次，后续的分裂都依赖于该分桶并不再更新。
- 优点是：只需要计算一次，不需要重复计算。
- 缺点是：在经过多次分裂之后，叶结点的样本有可能在很多全局桶中是空的。
局部模式：
- 除了在算法开始时进行分桶，每次拆分之后再重新分桶。
- 优点是：每次分桶都能保证各桶中的样本数量都是均匀的。
- 缺点是：计算量较大。
正则化
- 学习率
- 随机选取特征
计算速度提升
预排序
- 在程序开始的时候对数据在每个特征，按数据的大小进行排序，这样在训练的时候就不用排序，可以避免大量重复劳动，同时因为每个特征之间是独立的，因此在寻找划分点的时候就可以并行执行。
LightGBM
优势
GBT的缺点
- 在构建子决策树时为了获取分裂点，需要在所有特征上扫描所有的样本，从而获得最大的信息增益。当样本的数量很大，或者样本的特征很多时，效率非常低。
- 同时GBT也无法使用类似mini batch方式进行训练。
xgboost的缺点
- 每轮迭代都需要遍历整个数据集多次。
- 如果把整个训练集装载进内存，则限制了训练数据的大小。如果不把整个训练集装载进内存，则反复读写训练数据会消耗非常大的IO时间。
- 空间消耗大。预排序（pre-sorted）需要保存数据的feature值，还需要保存feature排序的结果（如排序后的索引，为了后续的快速计算分割点）。因此需要消耗训练数据两倍的内存。
- 时间消耗大。为了获取分裂点，需要在所有特征上扫描所有的样本，从而获得最大的信息增益，时间消耗大。
- 对cache优化不友好，造成cache miss 。预排序后，feature对于梯度的访问是一种随机访问，并且不同feature访问的顺序不同，无法对cache进行优化。
LightGBM的优点
- 更快的训练效率；
- 低内存使用；
- 更高的准确率；
- 支持并行化学习；
- 可处理大规模数据。
代价优化策略：
减少训练样本的数量和减少样本的训练特征数量。
Gradient-based One-Side Sampling(GOSS)
基于梯度的采样。该方法用于减少训练样本的数量。
- 传统采样方法采用随机丢弃的策略，而GOSS方法保留梯度较大的样本，随机丢弃梯度较小的样本。
- 为了不改变原数据的分布，GOSS在保留下来的小梯度样本上乘一个放大系数，以弥补被丢弃的小梯度样本。
Exclusive Feature Bundling(EFB)
基于互斥特征的特征捆绑。该方法用于减少样本的特征。
- 传统特征选取方法基于PCA的原理，认为许多特征包含重复信息，并以此选择重要特征或使用新特征，但实际场景往往难以使用。
- EFB根据特征间的互斥性来将互斥的特征打包成一个新的，信息密度更大的特征。具体的如果对于所有样本，两个特征都不会同时为非零值，即认为两个特征互斥，实际中如果只有少量样本不满足也可以认为互斥。
其它优化策略
直方图
- 优点：
- 节省空间：需要存储的信息更少
- 节省时间：分割点减少，也不用预排序
- 可能还自带正则化效果
- 缺点：分割点不是很精确
leaf-wise生长策略
- 相对level-wise可以避免很多不必要的分裂；
- 容易过拟合一些，需要限制最大深度。
直方图做差加速
- 通常构造直方图，需要遍历该叶子上的所有数据。但是事实上一个叶子的直方图可以由它的父亲结点的直方图与它兄弟的直方图做差得到。
- LightGBM在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。
直接支持categorical特征
元学习
概念
元学习（meta-learning）是一种机器学习的方法，它旨在让模型能够快速适应新的任务，而不需要大量的数据或训练时间。元学习的基本思想是，模型不仅要学习特定任务的知识，还要学习如何学习，即学习一种通用的学习策略，可以应用到不同的任务上。元学习的优势在于，它可以让模型具有更强的泛化能力和更高的效率，从而解决传统机器学习面临的数据稀缺、过拟合、迁移困难等问题。
元学习的方法可以分为三类：基于优化的元学习、基于模型的元学习和基于度量的元学习。
- 基于优化的元学习是指利用优化算法来更新模型的参数或超参数，使得模型在新任务上表现更好。例如，MAML（Model-Agnostic Meta-Learning）算法就是一种基于优化的元学习方法，它通过在多个任务上交替训练模型，找到一个能够在少量梯度更新后达到最佳性能的初始参数。
- 基于模型的元学习是指利用一个元模型来生成或调整目标模型，使得目标模型能够适应新任务。例如，RNN（Recurrent Neural Network）就是一种常用的元模型，它可以根据任务的输入和输出序列来动态地调整目标模型的参数或结构。
- 基于度量的元学习是指利用一个度量函数来比较不同任务之间或不同样本之间的相似性，使得模型能够根据相似性来进行分类或回归。例如，Siamese Network就是一种基于度量的元学习方法，它通过一个双分支网络来计算两个输入样本之间的距离，然后根据距离来判断它们是否属于同一类别。
元学习是机器学习领域中一个非常有前景和挑战性的研究方向，它可以为实现人工智能提供更强大和灵活的工具。本文介绍了元学习的概念、方法和应用，希望能够对感兴趣的读者有所启发和帮助。
元学习和机器学习的区别
元学习（meta-learning）是一种机器学习（machine learning）的高级形式，它的目标是让机器能够自动地从不同的任务和数据中学习如何学习，从而提高机器学习的效率和泛化能力。元学习的核心思想是利用已有的知识和经验来指导新的学习过程，而不是从零开始。
机器学习是一种人工智能（artificial intelligence）的分支，它的目标是让机器能够从数据中自动地学习规律和模式，从而实现特定的任务，如分类、回归、聚类等。机器学习的核心思想是利用数学和统计的方法来构建模型和算法，以及优化参数和损失函数。
元学习和机器学习的区别可以从以下几个方面来看：
- 学习目标：元学习的目标是学习如何学习，即找到一种通用的学习策略，可以适应不同的任务和数据；机器学习的目标是学习特定的任务，即找到一种特定的模型和算法，可以解决特定的问题。
- 学习过程：元学习的过程是一个双层的循环，即在外层循环中，根据不同的任务和数据来更新元参数（meta-parameters），在内层循环中，根据元参数来更新模型参数（model parameters）；机器学习的过程是一个单层的循环，即根据固定的任务和数据来更新模型参数。
- 学习效果：元学习的效果是一个快速适应（fast adaptation）的能力，即在遇到新的任务或数据时，只需要少量的样本或迭代就可以达到较好的性能；机器学习的效果是一个稳定收敛（stable convergence）的能力，即在给定足够多的样本或迭代后，可以达到最优或接近最优的性能。
元学习和机器学习之间并不是对立或替代的关系，而是互补或融合的关系。元学习可以为机器学习提供更好的初始点、更快的收敛速度、更强的泛化能力等优势；机器学习可以为元学习提供更丰富的任务、更多样的数据、更有效的模型等基础。元学习和机器学习共同推动了人工智能领域的发展和创新。
基于优化MAML
基于优化的元学习方法MAML是什么？为什么它是一种强大的机器学习技术？本文将用通俗易懂的方式介绍一下MAML的原理和应用。
MAML是Model-Agnostic Meta-Learning的缩写，意思是不依赖于特定模型的元学习。元学习是指让机器学习算法能够从多个不同的任务中学习通用的知识和技能，从而能够在新的任务上快速适应和泛化。MAML的核心思想是通过优化一个参数初始化，使得在任何一个任务上，只需要少量的梯度更新就能达到很好的性能。
具体来说，MAML首先定义了一个任务分布，即一系列相关但不同的任务，比如分类不同类别的图片，或者控制不同形状的机器人。然后，MAML随机采样一些任务，并在每个任务上训练一个初始模型，得到一个更新后的模型。接着，MAML计算更新后的模型在每个任务上的损失，并将这些损失相加，得到一个总损失。最后，MAML根据总损失对初始模型的参数进行反向传播和更新，得到一个新的初始模型。这个过程重复多次，直到初始模型收敛。
MAML的优点是它可以适用于任何可以用梯度下降优化的模型，比如神经网络、支持向量机、决策树等。它也可以适用于任何形式的任务，比如监督学习、无监督学习、强化学习等。MAML可以有效地利用多任务之间的相似性和差异性，从而提高模型在新任务上的泛化能力。MAML也可以节省计算资源和时间，因为它只需要少量的数据和更新就能在新任务上达到很好的性能。
MAML已经在许多领域和应用中展示了其强大的效果，比如图像分类、自然语言处理、机器人控制、医疗诊断等。例如，在图像分类方面，MAML可以在只看到几张图片的情况下，就能识别出新类别的图片。在自然语言处理方面，MAML可以在只看到几个句子的情况下，就能理解新语言或新领域的文本。在机器人控制方面，MAML可以在只进行几次尝试的情况下，就能掌握新环境或新任务的动作。
总之，MAML是一种基于优化的元学习方法，它可以让机器学习算法从多个不同的任务中学习通用的知识和技能，并在新任务上快速适应和泛化。MAML是一种不依赖于特定模型的方法，它可以适用于任何可以用梯度下降优化的模型和任何形式的任务。MAML已经在许多领域和应用中证明了其强大的效果和潜力。
基于度量
基于度量的元学习方法是一种利用数据之间的相似性来快速适应新任务的机器学习技术。下面是这种方法的基本思想、优势和应用。
基于度量的元学习方法是一种实现元学习的方式，它的核心思想是利用数据之间的相似性来度量模型在新任务上的表现。具体来说，这种方法首先在一个大规模的数据集上训练一个特征提取器，用于将输入数据转换为一个低维的向量表示，然后在每个新任务上，根据少量的标注数据（也称为支持集）计算出一个任务相关的度量函数，用于衡量不同数据之间的距离或者相似度，最后根据这个度量函数对未标注的数据（也称为查询集）进行分类或者回归。
基于度量的元学习方法有以下几个优势：
- 它可以有效地利用少量的标注数据来适应新任务，因为它只需要计算出一个简单的度量函数，而不需要对特征提取器进行显著的更新或者微调。
- 它可以处理多种类型和形式的数据，因为它只依赖于特征提取器和度量函数，而不需要针对每种数据设计特定的模型结构或者损失函数。
- 它可以实现快速和在线的学习，因为它可以在每次接收到新数据时动态地更新度量函数，而不需要重新训练整个模型。
经典机器学习算法
KNN
通过在全局中找到待测样本最近的K个训练样本来得到待测样本的类别或预测值
- 严格来说不算机器学习，因为没有学习的过程，而是记忆所有训练样本，没有得到泛化信息；
- 预测时的复杂度高
- KNN是非参数化的局部模型，消极（懒惰）学习，性能取决于K的大小和距离度量选择。
- KNN的模型复杂度和K成反比，K越小越复杂，K越大时平均程度越明显，即正则化力度越大。
- KNN中距离度量的选择是一个问题，连续数据常见的欧氏距离、曼哈顿距离、马氏距离等。
KD树
在原始KNN的基础上加入了学习过程
- 训练：通过垂直于坐标轴的超平面不断对训练样本进行二分的划分，得到一颗KD决策树；
- 测试：将待测样本的值在KD树上进行比较，逐步找到最近邻的样本；
- 平均计算复杂度为$O(log(N))$，大部分时候只需要较少的比较就可以得到最近邻；
- 当训练样本分布较糟糕时，需要遍历几乎所有节点。
压缩KNN
从训练样本中找出对于分类/决策比较重要的样本，类似SVM中的支持向量
- 训练：
- 选择一个样本放入样本集；
- 循环所有样本，如果分类正确则不取，分类错误则放入样本集，直到所有样本都分类正确。
- 测试：使用训练得到的样本集进行测试，而非所有样本。
线性模型
优点
- 模型简单；
- 可解释性强，权重向量直观地表达了各个特征在预测中的重要性；
- 很多功能强大的非线性模型可以在线性模型的基础上通过引入层级结构和非线性映射得到。
线性模型&非线性模型
- 分类模型关键看决策面是否是线性的，逻辑回归所回归的概率值与输入是非线性关系（几率值与输入是指数线性关系），但通过概率值得到的分类决策面是线性的，所以作为分类模型，逻辑回归是线性的。
线性回归
- 线性一方面是输入特征与其它参数的数学组合方式，另一方面是它所提供的决策边界（回归线）是线性的。
- 优势是：简单、解释性强、可以通过一些策略（kernel、层叠）简单转化为非线性模型。
模型：$y= \vec{x}^T\vec{w}$
数据：${ X,\vec{y} }$
损失函数：$L=(\vec{y}-X^T\vec{w})^2$
闭式解：$\vec{w}=(XX^T)^{-1}X\vec{y}$
- 当数据量小的时候$XX^T$不满秩，没有唯一解，可以加入L1、L2等正则化方式来获得唯一解
- 也可以用梯度下降来求解。
逻辑斯蒂回归
- 线性回归+sigmoid函数，广义线性模型；
- 将线性回归的值域从无穷映射到$[0,1]$区间，并将其解释为样本为某一类的概率；因此逻辑回归是概率模型，用于分类问题。
- 逻辑回归学习的是决策边界，而不是数据分布，因此是判别模型。
感知机
- 线性回归+符号函数
- 优化目标是感知准则而非误分类率：
- 误分类率：分段常数函数，每一种分类结果的分类边界都不唯一，无法给出优化方向；
- 感知准则：自适应，适合动态学习；
概率图
朴素贝叶斯
- 贝叶斯定理+特征条件独立假设；
- 朴素贝叶斯的基础是贝叶斯定理，即通过贝叶斯定理计算样本为各个类别的后验概率；
- 朴素贝叶斯朴素在特征条件独立假设，通过该假设，极大地降低参数量（将参数量从指数级降为线性级）。
贝叶斯公式
- 角度一：条件概率+全概率公式
- 角度二：用先验概率和具体事件表出后验概率
朴素贝叶斯分类器
- 利用贝叶斯定理来实现分类任务，先验得知道各类（输出）的概率以及在各类下事件（输入）的概率，就可以得到在发生事件（输入）时，各类（输出）的概率。
- 由于数据样本的数量与特征维度往往不匹配，参数量指数级，无法有效得到各类下事件（输入）的概率，因此朴素贝叶斯对条件概率做了特征独立性假设。
- 这意味着在分类确定的条件下，用于分类的特征是条件独立的。
- 该假设使得朴素贝叶斯法变得简单，参数量由指数级变为线性级，但是可能牺牲一定的分类准确率。
- 准确率牺牲的程度依赖实际特征的关联程度。
优点
- 性能相当好，它速度快，可以避免维度灾难。
- 支持大规模数据的并行学习，且天然的支持增量学习。
缺点
- 输出概率不一定准确；
贝叶斯网络
- 在众多的随机变量中，通过条件独立性假设来降低参数量，得到随机变量的有向无环图；
- 可以用于因果推断；
- 有向边表示依赖关系，入度为0的节点事件不受其他随机变量影响，入度不为0的节点概率为条件概率的形式；
马尔科夫网络
- 无向图，可以对关系进行建模，不能用于因果推断
决策树
树的每一个根节点通过一个特征对样本进行区分，叶节点的数据归为一类或一个输出值。
信息熵是用来衡量信息不确定性的指标:
对于分布$p(y)$， 信息熵为$H(y)=-\sum_y p(y)\log{p(y)}$
在具体数据集$D$上，经验分布熵为$H(D)=-\sum^{K}_{k=1}\frac{N_k}{N}\log{\frac{N_k}{N}}$
也可以用基尼系数$1-\sum_y{p(y)}^2$
条件熵：加入条件（如某个数据的特征），当条件取值不同时，数据子集有不同的信息熵，其期望就是条件熵。
$H(y|A)=\sum_A p(A)H(y|A)=-\sum_A[p(A)\sum_{y_A} p(y_A)\log{p(y_A)}]$
经验条件熵：$H(D|A)=-\sum_A[\frac{N_A}{N}\sum^{K_A}_{k=1}\frac{N_k}{N_A}\log{\frac{N_k}{N_A}}]$
信息增益:
- 通过加入特征使得数据分布更加确定，即该特征为分布带来了信息增益：$g(D,A)=H(D)-H(D|A)$；
- ID3使用信息增益作为特征选择策略。
信息增益比:
- 直接使用信息增益会倾向于使用取值较多的特征，如ID特征，信息增益比是在信息增益的基础上用特征取值的信息熵来标准化：$g_r(D,A)=\frac{g(D,A)}{H_A(D)}=\frac{H(D)-H(D|A)}{H_A(D)}$；
- C4.5使用信息增益作为特征选择策略。
基尼系数
- $gini(y)=1-\sum_yy^2$：也常用来代替信息熵，趋势以及计算值与信息熵都非常类似；
回归树方差：
- 前面的指标运用于分类问题中的信息不确定度计算，在回归问题中可以使用方差来表示不确定性，对应的有方差、条件方差、方差增益。
决策树&贝叶斯定理&朴素贝叶斯分类器
- 决策树的判定方式也可以解释为是用贝叶斯定理（后验概率），与朴素贝叶斯分类器的条件概率特征独立性假设不同的是，决策树依据最优特征选择，使用部分特征来计算后验概率。
SVM
- 支持向量机：间隔、对偶、核技巧
- SVM支持向量机抛开概率视角，化繁为简，从几何的角度来看待问题。
- 机器学习最终是看泛化误差而不是训练误差，最大化间隔就是从几何角度尝试最大化泛化误差。
- 支持向量机的误差包括两个部分：一个是分界面的不置信度，几何间隔越小越不置信；另一个是训练误差，越多的点被误分类训练误差越大。硬间隔要求后者为0，所以只包含前者。
- SVM通过对偶问题来求解最优边界，交换最大最小过程。
- 梅塞尔定理：只要满足对称和半正定的条件就可以作为核函数。
- 平稳核函数：值只与两个点的差（相对位置）有关。
- 径向基核函数：值与两个点的方向也无关，只与差的范数有关，如高斯核函数。
- 核函数的本质在于相似度计算，找出几何上决定边界的样本点（支持向量），对于新的样本点，就计算它们同支持向量的相似度，进而决定应该属于那个类别。
- 将核函数用于概率密度函数估计就是核密度估计方法。
特征空间维度
- 因为核技巧隐藏了映射的细节，只知道内积运算，所以特征空间是希尔伯特空间，维度是无限的。
- 但是仅从决策函数看，也可以说特征空间的维度是有限的且等于训练样本的数量，每一个支持样本对应一个维度，决策时计算出测试点在各个维度上的得分累加进行分类。
- 非线性SVM可以看成是一种特殊的神经网络，即输入层对应输入空间，隐藏层对应特征空间，判决分数对应输出层。各层神经元个数分别为输入数据维度、训练样本（或支持向量）维度、1。如果核函数选的合适就是一个广度网络。
- 另外希尔伯特空间本身就是去掉维度的概念，所以也可以说是没有维度。
理论上SVM的目标函数可以使用梯度下降法来训练。但存在三个问题
- 合页损失函数部分不可导。这可以通过sub-gradient descent 来解决。
- 收敛速度非常慢。
- 无法得出支持向量和非支持向量的区别。
常用核函数
- 多项式核函数；
- 高斯核函数；
支持向量机的优点
- 有严格的数学理论支持，可解释性强。
- 能找出对任务至关重要的关键样本（即：支持向量）。
- 采用核技巧之后，可以处理非线性分类/回归任务。
支持向量机的缺点
- 训练时间长。
- 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为平方。
- 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
- 因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。
SVM vs KNN
- 使用核函数的SVM同KNN类似，SVM可以看成特殊的KNN，最后预测都是计算待测样本到一些点的距离然后判断类别；不同的是KNN是懒惰的学习，或没有学习，因此预测的时候要从所有的样本计算最近的样本加以判别，而SVM在训练的过程中就找出了支持向量，因此判决过程更简单，SVM是不同支持向量的软的加权，不是离散地、硬的计数。
- KNN也有压缩近邻法，也可以看成是在寻找支持向量；方法是将分错的样本留下以保证其它样本都还可以分对，最后的效果是保留下来的样本点主要是决策边界附近的点。
深度学习算法
Graph embedding
从图总提取信息，用一个向量来表示一个节点。
DeepWalk
- 随机游走： 对每个节点在图上进行随机游走，生成图上的序列，通过Word2vector的方式生成embedding。
LINE
- 一阶相似性：相互连接的节点相似；一条边的两节点embedding內积求sigmoid作为联合概率分布，不同边的联合概率分布按边权重加权作为loss。
- 二阶相似性：相邻接点相似的节点相似；已知一个节点时，计算其它节点的条件概率，按边的权重加权作为loss。
- 将一阶和二阶embedding直接拼接得到最终的embedding。
node2vector
- 同质性：相近的节点相似
- 结构等价性：连接结构相似的节点相似
- 按一定概率游走，调整参数使模型倾向于学习不同信息；设置p、q的值，控制游走的方向倾向于在附近游走还是在远处游走。
struc2vector
- 两个节点的相似性通过两个节点的n-hop邻居的度的相似性的判断，也就是两个节点的结构。
