INCOMING TRANSMISSION

序言 极大似然估计与贝叶斯估计是统计中两种对模型的参数确定的方法，两种参数估计方法使用不同的思想。 前者来自于频率派，认为参数是固定的，我们要做的事情就是根据已经掌握的数据来估计这个参数；而后者属于贝叶斯派，认为参数也是服从某种概率分布的，已有的数据只是在这种参数的分布下产生的。 所以，直观理解上，极大似然估计就是假设一个参数 \(θ\) ，然后根据数据来求出这个 \(θ\) . 而贝叶斯估计的难点在于 \(p(θ)\) 需要人为设定，之后再考虑结合MAP（maximum a posterior）方法来求一个具体的 \(θ\) . 所以极大似然估计与贝叶斯估计最大的不同就在于是否考虑了先验，而两者适用范围也变成了：极大似然估计适用于数据大量，估计的参数能够较好的反映实际情况；而贝叶斯估计则在数据量较少或者比较稀疏的情况下，考虑先验来提升准确率。 预知识 为了更好的讨论，本节会先给出我们要解决的问题，然后给出一个实际的案例。这节不会具体涉及到极大似然估计和贝叶斯估计的细节，但是会提出问题和实例，便于后续方法理解。 问题前提 首先，我们有一堆数据...

k-d树（k-dimensional树的简称），是一种分割k维数据空间的数据结构。主要应用于 多维空间关键数据的搜索 （如：范围搜索和最近邻搜索）。 应用背景 SIFT算法中做特征点匹配的时候就会利用到k-d树。而特征点匹配实际上就是一个通过距离函数在高维矢量之间进行相似性检索的问题。针对如何快速而准确地找到查询点的近邻，现在提出了很多高维空间索引结构和近似查询的算法，k-d树就是其中一种。 索引结构中相似性查询有两种基本的方式：一种是范围查询（range searches），另一种是K近邻查询（K-neighbor searches）。范围查询就是给定查询点和查询距离的阈值，从数据集中找出所有与查询点距离小于阈值的数据；K近邻查询是给定查询点及正整数K，从数据集中找到距离查询点最近的K个数据，当K=1时，就是最近邻查询（nearest neighbor searches）。...

PCA PCA的思想 PCA顾名思义，就是找出数据里最主要的方面，用数据里最主要的方面来代替原始数据。具体的，假如我们的数据集是 \(n\) 维的，共有 \(m\) 个数据 \((𝑥(1),𝑥(2),...,𝑥(𝑚))\) 。我们希望将这 \(m\) 个数据的维度从 \(n\) 维降到 \(n'\) 维，希望这 \(m\) 个 \(n'\) 维的数据集尽可能的代表原始数据集。我们知道数据从 \(n\) 维降到 \(n'\) 维肯定会有损失，但是我们希望损失尽可能的小。那么如何让这 \(n'\) 维的数据尽可能表示原来的数据呢？ 我们先看看最简单的情况，也就是 \(n=2\) ， \(n'=1\) ,也就是将数据从二维降维到一维。数据如下图。我们希望找到某一个维度方向，它可以代表这两个维度的数据。图中列了两个向量方向， \(u_1\) 和 \(𝑢_2\) ，那么哪个向量可以更好的代表原始数据集呢？从直观上也可以看出， \(𝑢_1\) 比 \(𝑢_2\) 好。 为什么 \(𝑢_1\) 比 \(𝑢_2\)...

模型介绍 Logistic Regression 虽然被称为回归，但其实际上是分类模型，并常用于二分类。Logistic Regression 因其简单、可并行化、可解释强深受工业界喜爱。 Logistic 回归的本质是：假设数据服从这个分布，然后使用极大似然估计做参数的估计。 Logistic 分布 Logistic 分布是一种连续型的概率分布，其 分布函数 和 密度函数 分别为： \[F(x)=P(X\le x)=\frac{1}{1+e^{-(x-\mu)/\gamma}}\\ f(x)=F^{'}(x)=\frac{e^{-(x-\mu)/\gamma}}{\gamma(1+e^{-(x-\mu)/\gamma})^2}\] 其中， \(\mu\) 表示位置参数， \(\gamma\) 为形状参数。我们可以看下其图像特征： Logistic 分布是由其位置和尺度参数定义的连续分布。Logistic 分布的形状与正态分布的形状相似，但是 Logistic 分布的尾部更长，所以我们可以使用 Logistic...

什么是自组织映射？ 一个特别有趣的无监督系统是基于 竞争性学习 ，其中输出神经元之间竞争激活，结果是在任意时间只有一个神经元被激活。这个激活的神经元被称为 胜者神经元（winner-takes-all neuron） 。这种竞争可以通过在神经元之间具有 横向抑制连接 （负反馈路径）来实现。其结果是神经元被迫对自身进行重新组合，这样的网络我们称之为 自组织映射（Self Organizing Map，SOM） 。 拓扑映射 神经生物学研究表明，不同的感觉输入（运动，视觉，听觉等）以 有序的方式 映射到大脑皮层的相应区域。 这种映射我们称之为 拓扑映射 ，它具有两个重要特性： 在表示或处理的每个阶段，每一条传入的信息都保存在适当的上下文（相邻节点）中 处理密切相关的信息的神经元之间保持密切，以便它们可以通过短突触连接进行交互 我们的兴趣是建立人工的拓扑映射，以神经生物学激励的方式通过自组织进行学习。 我们将遵循 拓扑映射形成的原则 ：“拓扑映射中输出层神经元的空间位置对应于输入空间的特定域或特征”。 建立自组织映射 SOM的主要目标是将任意维度的输入信号模式 转换...

集成学习主要分为以下几类：Bagging，Boosting以及Stacking。 传统机器学习算法 (例如：决策树，人工神经网络，支持向量机，朴素贝叶斯等) 的目标都是寻找一个最优分类器尽可能的将训练数据分开。集成学习 (Ensemble Learning) 算法的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类器。集成算法可以说从一方面验证了中国的一句老话：三个臭皮匠，赛过诸葛亮。 Thomas G. Dietterich 指出了集成算法在统计，计算和表示上的有效原因： 统计上的原因 一个学习算法可以理解为在一个假设空间 H 中选找到一个最好的假设。但是，当训练样本的数据量小到不够用来精确的学习到目标假设时，学习算法可以找到很多满足训练样本的分类器。所以，学习算法选择任何一个分类器都会面临一定错误分类的风险，因此将多个假设集成起来可以降低选择错误分类器的风险。 计算上的原因 很多学习算法在进行最优化搜索时很有可能陷入局部最优的错误中，因此对于学习算法而言很难得到一个全局最优的假设。事实上人工神经网络和决策树已经被证实为是一 个NP...

从GBDT到XGBoost 作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化： 一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以选择很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是我们后面讨论的重点。 二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。 三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。...

GBDT (Gradient Boosting Decision Tree) 是另一种基于 Boosting 思想的集成算法，除此之外 GBDT 还有很多其他的叫法，例如：GBM (Gradient Boosting Machine)，GBRT (Gradient Boosting Regression Tree)，MART (Multiple Additive Regression Tree) 等等。GBDT 算法由 3 个主要概念构成：Gradient Boosting (GB)，Regression Decision Tree (DT 或 RT) 和 Shrinkage。 Decision Tree：CART回归树 首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是 梯度值...

分类问题 Adaboost 是 Boosting 算法中有代表性的一个。原始的 Adaboost 算法用于解决二分类问题，因此对于一个训练集 \[T = \{\left(x_1, y_1\right), \left(x_2, y_2\right), ..., \left(x_n, y_n\right)\}\] 其中 \(x_i \in \mathcal{X} \subseteq \mathbb{R}^n, y_i \in \mathcal{Y} = \{-1, +1\}\) ，，首先初始化训练集的权重 \[\begin{aligned} D_1 =& \left(w_{11}, w_{12}, ..., w_{1n}\right) \\ w_{1i} =& \dfrac{1}{n}, i = 1, 2, ..., n \end{aligned}\] 根据每一轮训练集的权重 \(D_m\) ，对训练集数据进行抽样得到 \(T_m\) ，再根据 \(T_m\) 训练得到每一轮的基学习器 \(h_m\) 。通过计算可以得出基学习器 \(h_m\) 的误差为 \(e_m\) \[e_m =...

EM算法也称期望最大化（Expectation-Maximum,简称EM）算法，它是一个基础算法，是很多机器学习领域算法的基础，比如隐式马尔科夫算法（HMM）， LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。 EM算法要解决的问题 我们经常会从样本观察数据中，找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。 但是在一些情况下，我们得到的观察数据有未观察到的隐含数据， 此时我们未知的有隐含数据和模型参数，因而无法直接用极大化对数似然函数得到模型分布的参数 。怎么办呢？这就是EM算法可以派上用场的地方了。 EM算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们 可以先猜想隐含数据（EM算法的E步），接着基于观察数据和猜测的隐含数据一起来极大化对数似然，求解我们的模型参数（EM算法的M步)...

介绍如何将Kernel Trick引入到Logistic Regression，以及LR与SVM的结合 SVM与正则化 首先回顾Soft-Margin SVM的原始问题: \[\begin{aligned}\min\limits_{b,\mathbf{w}, \xi} \quad &\frac{1}{2} \mathbf{w}^T\mathbf{w} + C \cdot \sum\limits_{n=1}^{N}\xi_n \\ s.t. \quad & y_n(\mathbf{w}^T\mathbf{z}^n+b) \geq 1-\xi_n, for \ all\ n \end{aligned}\] 其中 \(ξ_n\) 是训练数据违反边界的多少，没有违反的话， \(ξ_n=0\) ，反之 \(ξ_n>0\) ，换句话说，目标函数的第二项就可以表示模型的损失。现在换一种方式来写，将二者结合起来: \(ξ_n=max(1−y_n(w^Tz^n+b),0)\) ，这一个等式就代表了上面的约束条件，这样上述问题，就与下面的无约束问题等价 \[\begin{aligned} &...

正则化 正则化是一个通用的算法和思想，所有会产生过拟合现象的算法都可以使用正则化来避免过拟合。 在经验风险最小化的基础上（也就是训练误差最小化），尽可能采用简单的模型，可以有效提高泛化预测精度。如果模型过于复杂，变量值稍微有点变动，就会引起预测精度问题。正则化之所以有效，就是因为其降低了特征的权重，使得模型更为简单。 正则化一般会采用 L1 范式或者 L2 范式，其形式分别为 \(\Phi(w)=||x||_1\) 和 \(\Phi(w)=||x||_2\) 。 L1正则化 LASSO 回归，相当于为模型添加了这样一个先验知识： \(w\) 服从零均值拉普拉斯分布。 首先看看拉普拉斯分布长什么样子： \[f(w|\mu,b)=\frac{1}{2b}exp(-\frac{|w-\mu|}{b})\] 由于引入了先验知识，所以似然函数这样写：...