思维之海

——在云端,寻找我的星匙。

机器学习进阶

本文主要围绕机器学习/统计学习方法进行深层次展开。主要内容覆盖常见机器学习理论和方法。本文注重数理基础和整体观,以期更好的效果。本文是机器学习进阶过程的个人笔记。

References

课程

机器学习,唐杰/朱军

高级机器学习,唐杰

统计学习理论与应用,朱军

10-708 Probabilistic Graphical Models Fall 2008,CMU

【课程】CMU 10-708: 概率图模型 (2020 春 | 英字)

Stanford - CS228

斯坦福大学Coursera公开课——带字幕版《概率图模型》

Coursera - 概率图模型 专项课程

Stanford - CS228t

Upenn - CIS620 - ADVANCED TOPICS IN ARTIFICIAL INTELLIGENCE

机器学习课程,徐亦达

参考书

模式识别和机器学习 / PRML》,Christopher M. Bishop

深度学习 / Deep Learning》,“花书”

《概率图模型 / Probabilistic Graphical Models

机器学习》,周志华

目前已出版《机器学习理论导引

统计学习方法(第二版)》,李航

《动手学深度学习》 深度学习进阶

《Machine Learning: a Probabilistic Perspective》,Kevin Patrick Murphy(cs228t的主讲)

顶级会议

  • IJCAI(International Joint Conference on Artificial Intelligence)
  • AAAI(AAAI Annual Conference)

顶级期刊

  • JMLR(Journal of Machine Learning Research)
  • MLJ(Machine Learning)
  • PAMI(IEEE Trans. on Pattern Recognition and Machine Intelligence)
  • Artificial Intelligence
  • JAIR(Journal of Artificial Intelligence Research)
  • IJCV(International Journal of Computer Vison)

原理篇

A Few Useful Things to Know about Machine Learning

人工智能

“路漫漫其修远兮,吾将上下而求索”。

A Brief History of AI

History of artificial intelligence

通用人工智能

迈向第三代人工智能,张钹* , 朱军, 苏航

领域通用智能的可能技术路径,刘康、黄高、沈华伟、张家俊

模式识别

模式识别:从数据中获得规律/模式/特征

数据 = 模式 + 噪声

机器学习

机器学习:为了寻找更好数据表示的自动搜索

统计学习要素

模型:构建从输入到输出的一类映射,从而产生假设空间。

策略:按什么样的准则在假设空间中学习最优的模型。

算法:学习模型的具体计算方法。

短见定理

短见定理:过拟合无法彻底避免。

反证:(基本假设:P $\neq$ NP)

  • 机器学习通常面临着NP-Hard问题(甚至更难),而有效的学习算法必然在多项式时间内运行完毕。
  • 若可以彻底避免过拟合,则通过经验误差最小化就能获得最优解,意味着我们构造性地证明了“P=NP”。矛盾

机器学习是短视、贪心的。

午餐定理

午餐定理:对完全随机问题,任意学习算法的期望性能一致。(no free lunch

简单证明:(考虑二分类问题)

积分解耦(分部积分)的原理:

$P(x)表示从非训练集中选取样本x的概率,$(古典概型)

  • $显然与f和h无关$

$P(h|X,a)表示基于训练集X和学习算法a时,产生假设h的概率,$

  • $显然与真实问题f无关$

$\mathbb{I}(h(x)\neq f(x))表示基于样本x时假设h与真实f不吻合的布尔判断$,

  • 这是一个纯判断,不含概率,因此可以首先积分
  • 当我们引入了对$f$的积分之后,对特定问题的积分被解耦

$\sum _{f}\mathbb{I}(h(x)\neq f(x))相当于求{0,1}^{|\chi|}$(幂集)

  • 若$f$均匀分布,则一半的f对x的预测与h(x)不一致,因此要乘上1/2

NFL定理实际上构想了一个纯粹幻想空间。
完全随机的问题等价于一个没有任何模式(Pattern)的问题,机器学习不可能从真随机之中获得规律。

通过幻想学的蛋形图来直观感受一下短见定理和午餐定理的约束:(More

由直观的图像我们可以看出:

  • 极端的欠拟合导致午餐现象
  • 不考虑误差,过拟合和欠拟合的泛化能力与它们的名义是相反的(过拟合的泛化能力小,欠拟合的泛化能力大)
    若考虑误差,过拟合和欠拟合产生的误差类型是不同的(过拟合对变错,欠拟合错变对)
  • 显然,增大数据集能有效解决短视(过拟合)现象
  • 机器学习的过程是从想界到数据边界的收缩过程,其目标是尽可能与实界重合
  • 如果增加收缩能力(即学习能力,比如根据多个复杂原理进行收缩),则能有效解决欠拟合现象

注:一般认为想界和实界是固定的。

聚类分布律

聚类分布律:自然界中同一类别的高维数据,往往集中在某个低维流形附近。

The bless of dimension.

流形分布律

流形分布律:不同的类对应着流形上的不同概率分布,这些分布之间的距离大到足够将这些类区分。

极大似然律

极大似然律:给定概率模型,调参,使得样本空间的概率最大化。

最大熵原理

最大熵原理:给定概率模型,调参,使得模型的熵最大化。

最大熵模型| PLM’s Notes | 好好学习,天天笔记

最大熵模型| Kubi Code’Blog

监督学习

  • 分类(classification)
  • 回归(regression)

最早的决策机可以追溯到1936年Fisher设计的线性discriminator。

Log-ratio of two Gaussians

1962年Rosenblatt设计了感知机(Perceptron)。

1980年前后,神经网络的反向传播,决策树方法出现。

1990年前后,SVM出现。

2010年前后,DNN深度学习出现……

K-NN

KNN和K-mean有什么不同? - 知乎(但感觉k-means完还是要kNN一下才能输出预测结果 anyway。。)

KNN是非参数的监督学习方法。

KNN的性质

  • 简单
  • 强一致性的结果 strong consistency results
    • 对于无限的数据,K-NN的error rate也最多只是最优error rate的两倍(Bayes error rate)

Note: Bayes error rate – the minimum achievable error rate given the distribution of the data

KNN的问题

  • 对大数据集的计算量敏感
    • 尤其是高维空间
    • Clever nearest neighbor search helps(最近邻搜索
  • K值的选择(超参)
  • 距离度量的选择
    • Aware of the metric learning field(学习一个合适的度量)

KNN用于回归

选定在x坐标上的意义上最近的N个点,然后根据这N个点插值出预测点。

KNN分类算法

因为是监督学习的方法。所以存在事先标注好的大量数据分布于空间中。

给定一个未标注的点,我们计算K个与它最近的点的类别,并将其中统计的点的数量最多的类别,作为该未标注点的预测类别。这是一个非常简单明了的算法。

参数方法 Parametric Method

我们已经知道KNN是一种非参数的方法,在监督学习过程中并不需要学习出任何参数。

对于二分类问题,我们也可以采用参数化的直线作为决策边界。这样的方法称为参数方法。

SVM

最优线性分类器

如何选择最优的线性分类器(图中的直线)?

最靠近超平面的样本点被称为支持向量(support vectors)。支持向量形成支持超平面。

间距(Margin)$ ρ $ 是支持超平面之间的距离。

最大化这个margin是最好的,这由直觉和PAC理论共同支持。

这也暗示了只有支持向量才matters;其他所有的样本都可以被忽略。

线性SVM

拉格朗日乘子法

Dual Hard SVM

线性不可分问题

硬间隔SVM假设了样本集是线性可分的。(硬约束 $y_iW^TXi>0$ 必须被满足。)

但是数据可能出现线性不可分的情况,我们可以采用以下措施:

  • 使用新特征构造高维空间,并让样本空间线性可分
  • 使用软间隔SVM,而不是硬间隔SVM

SVM用于回归

核技巧 Kernel Trick

朴素贝叶斯

逻辑回归

高维空间易过拟合。

感知机

机器学习-神经网络基础-感知机有基础介绍。

决策树

无监督学习

K-means

请问如何用数学方法证明K-means是EM算法的特例?

高维空间欧式距离度量失效。

半监督学习

少样本学习 Few-shot

零次学习 Zero-shot

自监督学习

生成式学习 Generative Methods

GPT-2/3, VQ-VAE, ……

模型从参数中生成数据。

鉴别式模型 Discriminative Model

模型从数据中输出判断。

对比式学习 Contrastive Methods

SimCLR, MoCo, ……

对比式学习。

深度学习

https://vel.life/深度学习笔记/

深度学习是一种机器学习技术,它采用神经网络的方法抽取模式/特征。

反向传播算法

卷积神经网络 CNN

常用CNN架构

循环神经网络 RNN

RNN is a directive graph model.

强化学习

https://vel.life/强化学习/

表示学习

一切学习算法都是在学习数据的一种更好的表示。因此表示学习是机器学习的本质,也是核心。

表示学习(Feature learning / Representation learning):

图学习

https://vel.life/GNN学习笔记/

图嵌入

DeepWalk

使用随机游走生成的多条路径作为输入序列,从而可以采用词嵌入方法(词嵌入的本质是对语言序列关系的分布式表示)。

对DeepWalk的改进通常集中在如何生成更好的序列上。

node2vec

采用从节点出发的有限BFS、DFS(带有额外策略)生成的序列。

metapath2vec

针对异质网络(Heterogeneous网络中的节点有不同的实体类别)。不同的实体类别之间可能存在偏斜问题,metapath就是解决这种偏斜集问题。

在生成路径时,保证序列中出现的各类元素平衡。

NetMF

Network Embedding $\longleftrightarrow$ Matrix Factorization

可以证明各种random walk算法的本质都是在做矩阵分解(Matrix Factorization)。

NetMF跳过了random walk的序列生成步骤,而是直接做矩阵分解。

但是,直接做矩阵分解的算力消耗比random walk更多。

图卷积 GCN

预训练

迁移学习

自动机器学习

学习模型的性能表现常常是超参数敏感的。

AutoML: true end2end learning.

Meta-level learning & optimization.


Random Search works better than grid search. 更容易收敛到最优值。

Bayesian optimization: 利用期望和方差综合选择最优的下一个超参数集。

Tree of Parzen Estimators (TPE).

Population-based methods. (基因算法、进化算法、模拟退火……)


为了加快超参训练,可以引入超参数的梯度下降;可以预测模型的学习曲线,从而提前结束效果不好的训练;利用一个小的子样本集近似代表训练性能(Successive Halving, SH)。

Hyperband: 层次化的超参选择,不同层次用不同的加速方法……

Hyperband加速效果很好 / 收敛快,Bayesian optimization最终效果很好,两者在不同的训练阶段综合起来(先H后B),就可以同时兼具效率和性能了。

Network morphisms. One-shot. 超级高效的训练速度。

元学习

multi-task learning & ensemble learning

MAML: train the model’s initial parameters

首先在一个任务集上进行采样训练,获得一个良好的初始参数,对于一个新任务可以快速地收敛(少量的梯度调整)并获得性能

和预训练模型类似。但是MAML关心的是训练的潜力(只需要经过少量调整,它就能在多个任务上获得良好性能),预训练直接关心训练的性能,并不能保证模型在训练之后还能变得更好、在每个任务都能达到最优。

Reptile:在一个task上计算多步,然后根据获得的总梯度方向,更新元参数

对抗学习

White-box Attack

Black-box Attack: random samples

Graph Model Attack

There is a contest in KDDCUP 2020

Defense

Defense is possible but hard in real life.

data augmentation

GAN