正则化（Regularization）是机器学习中常用的技术，它可以控制模型的复杂度，减少模型的过拟合。最基本的正则化方法是在代价函数中添加对参数$w$的惩罚项：
\tilde{J}(w; X, y) = J(w; X, y) + \alpha\Omega(w)其中$J(w; X, y)$是原来的代价函数，$\alpha\Omega(w)$是正则化添加的惩罚项。比较常见的$\Omega(w)$函数有$L_1$范数和$L_2$范数，即：
\begin{gathered}
L_1: \Omega(w) = \|w\|_1 = \sum_i |w_i| \\
L_2: \Omega(w) = ...
DropoutDropout是一种防止神经网络过拟合的技术，它是指神经网络在训练的过程中，里面的节点会以概率p失活。所以Dropout相当于同时训练了很多个子网络，最后的结果是多个模型平均的结果，增强了模型的泛化能力，因此能够解决过拟合问题。
对于Dropout层，假设其中的神经元被保留的概率是p，比较直观的实现是：对于训练过程，根据概率p生成一个与输入向量X大小相同的符合伯努利分布的向量mask（里面都是0和1），然后将X与mask相乘；对于测试过程，因为测试过程没有神经元失活，所以对于某一层，其在测试过程的输出会比在训练过程大很多，所以需要进行rescale，常见的做法就是将这一层的...
前段时间春招都陆陆续续开始了，我也投了一些公司，反馈都比较慢，反而之后投的微软安排很快，两周之内就收到了onsite面试通知，当然是选择接受。投递的岗位是微软官网挂出来的Data Mining/Algorithm/Machine Learning Scientist Intern，因为秋招想找算法岗，所以实习也想找一找相关的，奈何现在又缺乏拿得出手的算法经历，不过好在听说微软面试只问算法题，这也是我投递微软的一个原因吧。
辗转到了苏州之后，直奔微软。在旁边随便找了家餐厅解决了午饭，随后随便逛了逛，看时间差不多就去微软前台报到了，随后面试官下来带我去面试房间。第一面是一个非常和蔼可亲的小哥...
最近在做机器学习比赛的时候，遇到了Target Encoding。所谓Target Encoding，是一种特征工程方式，根据训练集中的标签信息生成特征，来提高模型的性能。比较常见的是对于二分类问题（即需要预测的标签是0和1），根据训练集中的某一列特征对训练集进行groupby操作，然后计算每个分组内标签的均值，作为新的特征。
例如下图中，根据原始特征id，生成了id_target_mean这一列均值特征。
上图展示的是最朴素的一种办法，这种办法非常直观，但是常常不work，带来的最明显的问题就是过拟合，训练集分数会飙升，而验证集的分数会剧烈下降。但Target Encoding确实是一...
在上一篇博客中主要整理了支持向量机的数学原理，本文主要致力于用SMO算法来求解支持向量机最后的凸二次规划问题。
SMO算法SMO算法的全称是Sequential minimal optimization，又名序列最小最优化算法，是用于快速求解支持向量机凸二次规划问题的算法。其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了，因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，进行求解。SMO不断将原问题分解为子问题进行求解。整个SMO算法包括两个部分，求解两个变量二次规划的解析方法和选...
支持向量机是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
拉格朗日对偶性支持向量机的求解过程用到了拉格朗日对偶性。考虑原始的带约束的最优化问题，具有如下形式：
\begin{aligned}
\min_w \quad & f(w) \\
s.t. \quad & g_i(w) \leq 0, \, \, i=1,\cdots,k \\
& h_i(w) = 0, \, \, i=1,\cdots,l...
相关概念随机变量X的熵定义为：
H(X) = -\sum_{i=1}^n p_i \log p_i因为随机变量X的熵与X的取值没关系，只取决于X的分布，所以也可以记作$H(p)$。如果对数以2为底，此时熵的单位是比特；如果对数以e为底，此时熵的单位是奈特。
条件熵：
H(Y|X) = \sum_{i=1}^n p_i H(Y|X=x_i)信息增益：特征A对训练数据集D的信息增益$g(D,A)$，定义为集合D的经验熵$H(D)$与特征A给定条件下D的经验条件熵$H(D|A)$之差，即
g(D, A) = H(D) - H(D|A)熵$H(D)$与条件熵$H(D|A)$之差也称为互信息。设训...
\begin{gathered}
f(x) = sign(w \cdot x + b) \\
sign(x) = \begin{cases} +1, x \geq 0 \\ -1, x < 0 \end{cases}
\end{gathered}感知机是一种线性分类模型，属于判别模型。几何解释：$w \cdot x + b = 0$可以看成是一个超平面，其中$w$是超平面的法向量，$b$是超平面的截距，这个超平面把特征空间划分为两部分。
学习策略因为感知机是一个线性分类器，所以学习的目标是求得能将两类点分离的超平面。这需要定义一个损失函数，并且将损失函数极小化。直观来说，损失函数可以定义...
最近一直在写动态规划相关的算法题，遇到了很多背包问题的变种问题，解法也很精彩，趁着中秋有空，记录于此。
基本的背包问题背包问题的定义：
有N种物品，对于第i种物品，其体积是$V_i$，价值是$W_i$，数量是$M_i$。现有容量为C的背包，要求从这N种物品中选择一定数量的物品放入背包，使得背包所装的物品价值总和最大。
根据物品数量的不同，又可以把背包问题分为以下三种类型：
每种物品的数量都是1，这时称为01背包问题；
每种物品的数量都是无限，这时称为完全背包问题；
每种物品的数量都是1个或多个，这时称为多重背包问题。
01背包最简单的是01背包问题，这里简单定义$f(i,j)...
树状数组常用于高效求解前缀和、区间和，复杂度都在$O(logn)$，同时支持单点更新。但是区间更新效率低下，朴素的实现需要对区间内的每一个元素实行单点更新，时间复杂度在$O(n)$。可以通过维护两个数组，来高效地实现区间更新。
假设目前有一列数据$a_1, a_2, a_3, …, a_n$，用两个树状数组来高效进行这些数据的区间更新与求和。令sum(bit, i)是树状数组bit的前i项和，构建两个树状数组bit0和bit1，并且假设数列${a_i}$的前i项和为
\Sigma_{j = 1} ^ {i} a_j = sum(bit1, i) * i + sum(bit0, i)其中树...
