Notes on Machine Learning
重要名词解释Important Expressions
训练集train set： 用于模型训练的数据集
验证集validation set：用于进行模型评估和模型选择的数据集
测试集test set：用来评估模型在实际使用中的泛化能力
形象上来说训练集就像是学生的课本，学生 根据课本里的内容来掌握知识，验证集就像是作业，通过作业可以知道 不同学生学习情况、进步的速度快慢，而最终的测试集就像是考试，考的题是平常都没有见过，考察学生举一反三的能力。
错误率error rate:分类错误的样本数占样本总数的比例
精度accuracy：分类正确的样本数占样本总数的比例
线性模型Linear Model
线性判别分析Linear Discriminant Analysis,LDA:用于解决二分类问题的经典线性学习方法。主要思想：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。
多分类学习的基本思路是“拆解法”，即将多分类任务拆为若干个二分类任务求解。
最经典的拆分策略有三种：“一对一”（One vs One, OvO)，“一对其余”（One vs Rest，OvR) 和 “多对多”（Many vs Many，MvM）
类别不平衡问题class-imbalance:指分类任务中不同类别的训练样例数目差别很大的情况。三类处理方案，第一类是欠采样（under sampling)即去除训练集中数目较多类别的样例；第二类是过采样（over sampling)即增加训练集中数目较少类别的样例；第三类是直接基于原始训练集进行训练，但在使用分类器进行预测时修改决策过程，进行“阈值移动”（threshold moving)。
决策树Decision Tree
决策树的划分目标：决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。
神经网络Neural Networks
多层前馈神经网络（multi-layer feedforward neural networks)：每层神经元与下一层神经元全互连，神经元之间不存在同层连接，也不存在跨层连接，这样的神经网络称之为多层前馈神经网络。
神经网络的学习过程，就是根据训练数据来调整神经元之间的“连接权”（connection weight）以及每个功能神经元的阈值；换言之。神经网络学到的东西，蕴含在连接权与阈值中。
常见的神经网络：
- RBF(Radial Basis Function，径向基函数)网络，这是一种单隐层前馈神经网络，它使用径向基函数作为隐层神经元激活函数，而输出层则是对隐层神经元输出的线性组合。
- ART（Adaptive Resonance Theory， 自适应谐振理论）网络，它采用竞争型学习（一种常用的无监督学习策略）的策略，由比较层、识别层、识别阈值和重置模块构成。
- SOM（Self-Organizing Map，自组织映射）网络，这是一种竞争学习型的无监督神经网络，它能将高位输入数据映射到低维空间（通常是二维）,同时保持输入数据在高维空间的拓扑结构，即将高维空间中相似的样本点映射到网络输出层中的邻近神经元。
- 级联相关网络（cascade-correlation) 是结构自适应的神经网络。
- Elman网络是递归神经网络。与前馈神经网络不同，递归神经网络（recurrent neural networks)允许网络中出现环形结构，从而可以让一些神经元的输出反馈回来作为输入信号。
- Boltzmann机：这是一种“基于能量的模型”（energy-based model)。神经网络中有一类模型是为网络状态定义一个“能量”（energy），能量最小化时网络达到理想状态，而网络的训练就是在最小化这个能量函数。
深度学习deep learning：典型的深度学习模型就是很深层的神经网络。对于神经网络模型，提高容量的一个简单办法就是增加隐层数目，然而多隐层神经网络难以直接使用经典算法（比如标准BP算法）进行训练，因为误差在多隐层内逆传播时，往往会“发散”（diverge）而不能收敛到稳定状态，所以无监督逐层训练（unsupervised layer-wise training)是多隐层网络训练的有效手段，即采用预训练+微调的做法对多隐层网络进行训练，这样可以有效地节省了训练开销。
另一种节省训练开销的策略是”权共享（weight sharing)”，即让一组神经元使用相同的连接权，这个策略在卷积神经网络(Convolutional Neural Network)发挥了重要作用。
贝叶斯分类Bayes Classifier
*朴素贝叶斯分类器（naive Bayes classifier) *：朴素贝叶斯分类器采用了属性条件独立假设（attribute conditional independence assumption)，即对已知类别，假设所有属性相互独立，换言之，假设每个属性独立地对分类结果发生影响。之所以使用朴素贝叶斯分类器，是因为贝叶斯分类器难以从有限的训练样本中直接估计所有属性上的联合概率。
EM(Expectation-Maximization)算法：是一种迭代式的方法，用于计算参数隐变量，其基本思想是：若参数Θ已知，则可以根据训练数据推断出最优隐变量Z的值（E步）；反之，若Z的值已知，则可以方便地对参数Θ做最大似然估计（M步）。
集成学习Ensemble Learning
*集成学习(ensemble learning) *：通过构建并结合多个学习器来完成学习任务，也被称为多分类器系统（multi-classifier system)。根据个体学习器的生成方式，目前的集成学习方法大致可分为两类，即个体学习器间存在强依赖关系、必须串行生成的序列化方法，代表算法是Boosting；另一类是个体学习器之间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和随机森林（Random Forest)。
Boosting：这是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
Bagging：这是一种并行式集成学习方法，它直接基于自助采样法（Bootstrap sampling)。给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过m次随机采样操作，我们得到m个样本的采样集。其中初始训练集中约有63.2%的样本出现在采样集中。照这样可以采样出T个含m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这就是Bagging的基本流程。
随机森林(Random Forest，RF)：RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，传统的决策树在选择划分属性时实在当前结点的属性集合（假设有d个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最有属性用于划分，这里的参数k控制了随机性的引入程度。
结合策略：平均法，投票法和学习法（通过另一个学习器来结合个体学习器，即通过次级学习器来结合初级学习器）。
聚类Clustering
聚类(clustering)：聚类算法是无监督学习（unsupervised learning)，训练样本的标记信息未知，通过聚类，试图将数据集中的样本划分为若干个通常不相交的子集，每个子集称为一个“簇”（cluster)。聚类过程仅能自动形成簇结构，而簇所对应的概念语义需要使用者来进行命名和把握。聚类算法涉及的两个基本问题是性能度量和距离计算。
性能度量(validity index)：性能度量大致有两类：
一类是将聚类结果与某个参考模型（reference model)比较，称为“外部指标”（external index），常用的外部指标有Jaccard系数（Jaccard Coefficient, JC），FM指数（Fowlkes and Mallows Index, FMI)和Rand指数（Rand Index,RI)。这些指数越大说明聚类效果越好。
另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”（Internal index)，常用的内部指标有DB指数（Davies-Bouldin Index, DBI）和Dunn指数（Dunn Index,DI)。内部指标中DBI的值越小越好，而DI的值越大越好。
密度聚类（density-based clustering）：通常情形下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。DBSCAN是一种著名的密度聚类算法。
层次聚类（hierarchical clustering）：这种聚类算法试图在不同层次对数据集进行划分，从而形成树形的聚类结构。AGNES是一种采用自底向上聚合策略的层次聚类算法。
半监督学习Semi-supervised Learning
半监督学习（semi-supervised learning)：让学习器不依赖外界交互，自动利用未标记样本来提升学习性能。
半监督支持向量机（semi-supervised support vector machine, S3VM)：这是支持向量机在半监督学习上的推广。
半监督聚类（semi-supervised clustering)：聚类是典型的无监督学习任务，但现实的聚类任务中，我们往往能获取到一些额外的监督信息，这些信息大致有两类，一类是必连（指样本必属于同一个簇）与勿连（指样本必不属于同一个簇）约束，另一类是少量的标记样本。利用这些监督信息，我们可以通过半监督聚类来获得更好的聚类效果。
规则学习Rule Learning
规则学习（rule learning)：规则学习是从训练数据中学习出一组能用于对未见示例进行判别的规则。
序贯覆盖（sequential covering)：即逐条归纳，在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为“分治”（separate-and-conquer)策略。
一阶规则学习，FOIL算法（First-Order Inductive Learner)：FOIL是著名的一阶规则学习算法，它遵循序贯覆盖框架并且采用自顶向下的规则归纳策略，由于逻辑变量的存在，FOIL在规则生成时需要考虑不同的变量组合。
归纳逻辑程序设计（Inductive Logic Programming，ILP）：归纳逻辑程序设计在一阶规则学习中引入了函数和逻辑表达式嵌套。
强化学习Reinforcement Learning
强化学习：强化学习的学习目的就是要找到能使长期累积奖赏最大化的策略。强化学习中没有标记样本，即没有人直接告诉机器在什么状态下应该做什么动作，只有等到最终结果揭晓，才能通过“反思”之前动作是否正确来进行学习，因此，强化学习在某种意义上可看作具有“延迟标记信息”的监督学习问题。
探索与利用(Exploration and Exploitation)：探索（“估计摇臂的优劣”）和利用（“选择当前最优摇臂”）这两者是矛盾的，因为尝试次数有限，加强了一方则会自然削弱另一方，这是强化学习所面临的“探索利用窘境”（Exploration-Exploitation dilemma)。显然，想要强化学习累积奖赏最大，需要在探索和利用之间达到较好的折中。
模仿学习（imitation learning)：在强化学习的经典任务设置中，机器所能获得的反馈信息仅有多步决策后的累计奖赏，但在现实任务中，往往能得到人类专家的决策过程范例，从这样的范例中学习，称为“模仿学习”（imitation learning）。