该笔记是对李航统计学习方法和All of Statics做的学习笔记，简单进行相关算法实验，加强理解，查缺补漏等，内容尽量精炼

概念

生成模型与判别模型

generative model和discriminative model$（以下分别表示为G和D）$
$G\ $常见的有朴素贝叶斯，隐马尔科夫模型，高斯混合、 LDA、 Restricted Boltzmann Machine等
$D\ $有Kmeans，感知机，决策树，最大熵模型，Logistic回归、SVM、 boosting、条件随机场、神经网络等
两者的本质区别及特点：
$G\ $的流程是学习X和Y的联合概率分布$P(x,y)$得出$P(y|x)$最直接的例子就是Naive Bayes，由于生成的结果是联合分布$P(x,y)$，可以计算边缘分布$P(x)$进行异常值检测，若$P(x)$太小，就判定可能不适合这一类样本所代表的数据。
$D\ $的流程是直接由给定的X，Y学习决策函数或$P(y|x)$，是一种黑盒操作，准确率高，可以将允许对问题进行抽象处理，最熟悉的例子就是Neural Network

分类问题和回归问题

分类用CrossEntropy，回归用Mean Square Error等等

范数 norm

$L1范数 \sum{|x_i|}$
$L2范数 \sqrt{x_{1}^{2} + x_{2}^{2} + … + x_{n}^{2}}$
$L_\infty无穷范数MAX{|x_i|}$
范数理论推论$L1\geq{L2\geq{L_\infty}}$
对于numpy的线性代数库，有几种求范数的方法，主要就是求这三种

1
np.linalg.norm(x, ord=None, axis=None, keepdims=False)

axis=0表示对矩阵x的每一列求范数，axis=1表示对矩阵的每一行求范数， keeptdims=True表示结果保留维度，keepdims=False表示结果不保留维度

最小二乘

是解决曲线拟合问题、最小化cost的优化方法，使求得的数据与实际数据之间的误差平方和最小，应用范围非常广泛。
$设(x,y)为一组观测量，x=[x_0,x_1,…,x_n]^T,寻找一个函数y=f(x,w)$ ，使$尽可能逼近曲线(x,y),其中w=[w_0,w_1,…,w_n]^T$，为待估计参数，求解
使残差函数$$L(y,f(x,w))=\sum{[y_i-f(x_i,w_i)]^2}$$得到全局最小值的$w$,直观上就是每个点与拟合曲线的欧氏距离的平方和。

与梯度下降的区别：
最小二乘法是指对$\Delta$求导找出函数全局最小的w，梯度下降是先给定一个w（初始化），经过N次梯度下降后找到的使函数局部最小的w。相对的，梯度下降适用于大规模数据，最小二乘适用于较小样本，不过梯度下降的缺点是到最小点的时候收敛速度变、对初始点的选择极为敏感两个方面。

感知机 perceptron

属于$Discriminative \ Model$的线性分类模型，输入是表示一个Instance的特征向量，求出分离特征的超平面，公式表示为：
$f(x) = sign(w*x+b)$
$\begin{eqnarray}
sign(x)= \begin{cases}
1,&x\geq{0} \cr
-1 ,&x<0
\end{cases}
\end{eqnarray}$
这种perceptron叠起来就相当于是全连接的MLP(Multi-Layer Perceptron)

n多个线性函数叠加，对应矩阵运算$W\cdot x + B$，$W是w权重矩阵，B是bias的列向量，激活函数对应单个感知机的sign函数$

k-近邻 k nearest neighbor

还是属于$Discriminative \ Model$的模型，复杂度为$O(n^2)$，由三个基本要素组成：距离度量、k值、分类规则
距离度量，设有向量x1和x2，则：
欧氏距离np.sqrt(np.sum(np.square(x1 - x2)))
或直接np.linalg.norm(x1-x2)（用numpy的线性代数库求L2范数，但后者较慢）
曼哈顿距离np.sum(x1 - x2)

1
2
3
4
5
6
7
8
9
input:px,k
return:bestx
# get N(x):涵盖最近的k个点的邻域，即KList
distList = []
for x in X:
	distList.append(np.sqrt(np.sum(np.square(px - x))))
KList = np.argsort(np.array(distList))[:k]
# 决策规则I:由KList得出bestx，以类别分类问题为例，选N(x)最多类别为结果
X(np.argmax(np.bincount(X(i))))

如果要求多个最大值索引
np.where(a == np.amax(a))[0]，或者np.argwhere(a == np.amax(a))

kd tree

存储k维空间数据的树结构，实现如下

1
2


朴素贝叶斯 Naive Bayes

属于$Generative \ Model$一类，给的是联合分布$P(x,y)$，学过概率论的应该都会，普通的算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
input:
先验概率分布P__y : P(Y=c)，条件概率分布P_x_y : P(X=x|Y=c)，dim_f:特征维度
c_num：分类数目，data:数据list，label:标签list，以[0,1,...,9]为例
return:max P

#求出先验分布，并对数化，经常使用的对乘法处理的方式
P__y = [[(np.sum(label == np.asarray(i)))/(len(label))] \
				for i in range(c_num)]
P__y = np.log(P__y)
#求出条件分布
P_x_y = np.zeros((c_num, dim_f, 2))  
#对标记集进行遍历  
for i in range(len(label)):  
    #获取当前循环所使用的标记  
	c = label[i]  
    #获取当前要处理的样本
	x = data[i]  
    #对该样本的每一维feature进行遍历
	for j in range(dim_f):  
        #先在矩阵中对应位置加1
		P_x_y[c][j][x[j]] += 1  

	for c in range(c_num):
		for j in range(dim_f):  
			P_x_y0 = P_x_y[c][j][0]  
			P_x_y1 = P_x_y[c][j][1]  
			P_x_y[c][j][0] = np.log((P_x_y0 + 1) / (P_x_y0 + P_x_y1 + 2))
			P_x_y[c][j][1] = np.log((P_x_y1 + 1) / (P_x_y0 + P_x_y1 + 2))
# pick up最大Probability
P = [0] * c_num
for i in range(c_num):
	for j in range(dim_f):
		sum += P_x_y[i][j][x[j]]  
	P[i] = sum + P__y[i] 
res = P.index(np.amax(P))

决策树 Decision Tree 及剪枝

决策树是经常在kaggle以及实际应用中很广泛且有效的算法，决策树通常包括3个步骤:特征选择、构造、剪枝，无内鬼，直接进行一个sklearn.tree的import，sklearn的tree里封装了BaseDecisionTree，在此基础上进一步封装了DecisionTreeClassifier和DecisionTreeRegressor：分类器和回归器，做kaggle是确实好用。

特征选择：特征选择的准则是信息增益（information gain）或信息增益比。

$设离散型X的概率分布P(X =x_i)=p_i$
$Entropy的定义为H(X)=\sum{p_i\log{p_i}}$

决策树构造

ID3

各个节点用信息增益H(D)准则选择特征，递归构建决策树。
ID3算法的核心是在决策树各个结点上用信息增益选择特征，递归地构建决策
树。具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益， 选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归调用该方法，直到所有feature被用完或剩余feature的信息增益很小或少于自己设置的阈值，决策树建立完成，缺点是只生成了树，没有【】容易过拟合。

C4.5

各个节点用信息增益比选择特征，递归构建决策树，递归函数流程和ID3一样，只是评估标准换成了H(D|A)

CART

对回归树用平方最小误差原则，对分类树用基尼指数最小化原则进行特征选择。

剪枝

去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

但是自己还是得从0实现一个决策树，以后用的时候心里有点B数。
数据用colab的sampledata里california_housing那个

1
2


Logistic Regression

熟悉的Logistic回归，以二分类任务为例，就是用sigmoid函数把结果映射到(-1,1)；多分类任务下，将该二分类任务的sigmoid推广到了softmax函数 ，就是我们熟悉的softmax激活函数。
$$Sigmoid(z) = \frac{1}{1+exp(-z)},z=w^T\cdot x,(alias\ Sigmoid(z)=h_w(x))$$
$$gradient\ descent:
\Delta = x_i \cdot y_i - \frac{np.exp(w\cdot x_i) * x_i)}{ ( 1 + np.exp(w\cdot x_i))}then, \ w=w+lr\cdot\Delta$$
或者
$$LikelihoodFunc:J(w) =-\frac{1}{m}\sum\limits_{i=1}^{m}{[y_ilog(h_w(x_i))+(1-y_i)log(1-h_w(x_i))]}$$

$$partial:\frac{\partial J\left(w \right)}{\partial {w}}=\frac{1}{m}\sum\limits_{i=1}^{m}{(h_w(x_i)-{y_i})x_i}$$
代码例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#gradient descent
x = data # feature array,default(n,m), gradient dimension is m
y = label # result/ ground truth
w = np.zeros(x.shape[1])
iter_num = 1000
lr = 1e-4
for one_iter in range(iter_num):
	for index in len(data):
		# 下面xiyi赋值是看着方便，实际上用的时候直接用index取list元素
		x_i = data[index]
		y_i = label[index]
		# 用上面的公式，求partial
		gradient = x_i*(1/(1+np.exp(np.dot(w,x_i)))-y_i)
		w+=gradient*lr
print("final w:",w)

最大熵模型 Max Entropy Model

复杂度超高，做分类慢的一批，一般用来衡量预测效果的好坏，其实一般也不用。主要是记录一下最大熵模型的思想：将分类等问题作为约束最优化问题，下面的SVM和Adaboost等算法都是采用的约束最优化思想完成的。

支持向量机 Support Vector Machines

间隔最大化的学习策略，可形式化为求解凸二次规划问题/正则化的合页损失函数的最小化问题
训练数据线性可分，通过硬间隔最大化（hard margin maximization）学习线性可分SVM/硬间隔SVM
数据近似线性可分，通过软间隔最大化（soft margin maximization）学习线性SVM/软间隔SVM
数据线性不可分时，通过核函数+软间隔最大化，学习非线性SVM：核函数表示将输入从输入空间映射到特征空间得到的特征向量的内积(点乘)，可以抽象成在高维空间里学习一个线性SVM

线性SVM

函数间隔、约束最优化问题

  • 函数间隔：对于给定数据和超平面wx+b：
    关于样本点(x,y)的函数间隔为$\gamma_f=y(wx+b)$
    关于数据集的函数间隔为，所有样本点的最小值，$\gamma_{min}=min(\gamma_f)$
  • 几何间隔：归一化函数间隔，在法向量正向的几何间隔为$\gamma_g=y(\frac{w}{||w||}\cdot{x}+\frac{b}{||w||}),其中||w||是法向量w的L_2范数$
    两者关系是$\gamma_f=\gamma_g*||w||$
  • 间隔最大化，我们为使SVM分类样本点的置信度更大，需要将超平面关于数据集的几何间隔最大化，即求最大几何间隔的超平面，数学描述为：
    $$max\ \frac{\gamma_f}{||w||}\\ s.t.\ y(wx+b)\geq \gamma_{min}$$
    由于等式两边在尺度上是一致的，用一下无敌的“不妨设”$\gamma_f = 1$，那么优化目标为w的L2范数的最小值，即
    $$max\ \frac{\gamma_f}{||w||}等价于求\min{\frac{||w||^2}{2}}\\ s.t.\ y(wx+b)\geq{1}$$
    那么这个转化为二次规划的非线性规划如何求解呢？
    使用拉格朗日对偶性求解对偶问题得到以上问题的解，以这个线性可分问题为例，引入N个拉格朗日乘子，$\alpha$，对应N维特征和N维法向量w：
    $$构建拉格朗日函数L(w,b,\alpha)=\frac{||w||^2}{2}-\sum\limits_{i=1}^N{\alpha_iy_i(wx_i+b)}+\sum\limits_{i=1}^N{\alpha_i}$$
    原始问题的对偶问题转化为$\max\limits_{\alpha}\min\limits_{w,b}L,下面推导一下$
    Derivatives:
    $$\frac{\partial{L(w,b,\alpha)}}{\partial{w}}=w-\sum\limits_{i=1}^N{\alpha_ix_iy_i}=0\\ \frac{\partial{L(w,b,\alpha)}}{\partial{b}}=\sum\limits_{i=1}^N{\alpha_iy_i}=0$$
    Then we turn to:
    $$max:L(w,b,\alpha)=\sum\limits_{i=1}^N{\alpha_i}-\frac{1}{2}\sum\limits_{i,j=1}^N{y_iy_j\alpha_i\alpha_jx_i^Tx_j}\\ s.t\ \sum\limits_{i=1}^N{\alpha_iy_i}=0$$

这化简为只有拉格朗日乘子alpha的L极大值问题了，到这一步，我们可以直接进行SMO求解（从这里可以直接跳到下一节）
于是我们可以引入软间隔的线性SVM，对每个样本点引进一个松弛变量$\xi\geq0$，再引进一个惩罚参数C，那么我们的问题由$求min\frac{||w||^2}{2}转化为min(\frac{||w||^2}{2}+C\sum\limits_{i=1}^N{\xi_i})$
$$L(w,b,\xi,\alpha,\mu)=\frac{||w||^2}{2}+C\sum\limits_{i=1}^N{\xi_i}-\sum\limits_{i=1}^N{\alpha_iy_i(wx_i+b)}+\sum\limits_{i=1}^N{\alpha_i(1-\xi_i)}-\sum\limits_{i=1}^N{\mu_i\xi_i},\\
s.t.\ y(wx+b)\geq1-\xi,\xi\geq0$$
Derivatives:
$$\frac{\partial{L}}{\partial{w}}=w-\sum\limits_{i=1}^N{\alpha_ix_iy_i}=0\\
\frac{\partial{L}}{\partial{b}}=-\sum\limits_{i=1}^N{\alpha_iy_i}=0\\
\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0$$
以上求出关于$w,b,\xi$的极小后
turn to :
$$max:L(w,b,\xi,\alpha,\mu)=\sum\limits_{i=1}^N{\alpha_i}-\frac{1}{2}\sum\limits_{i,j=1}^N{y_iy_j\alpha_i\alpha_jx_i^Tx_j}\\
s.t.\ \sum\limits_{i=1}^N{\alpha_iy_i}=0,\\
C-\alpha_i-\mu_i=0$$
由以上结果可以看出，如果将目标函数的max转化为求min(改正负号)，均得到对应的对偶问题，其满足KKT条件，经过求解对偶问题，得出alpha，带入解得w和b，$$w=\sum\limits_{i=1}^N{\alpha_ix_iy_i}\\
b=y_j-\sum\limits_{i=1}^N{}y_i\alpha_i(x_ix_j)$$即得到超平面，wx+b=0
以上两种线性的SVM可以直接由上面的推导将一个求最大间隔的原始问题转化为求一个超平面的对偶问题，进而求得

非线性SVM

核函数用来将两个样本点实例$x,z$通过映射函数$\Phi(x),\Phi(z)$从输入空间映射到特征空间内，核函数表示为K，即$K(x,z)=\Phi(x)^T\Phi(z)$，一般不写出映射函数$\Phi$，而是在Kernel函数中隐式给出：
在这记录一下高斯核Gaussian kernel(radial basis function,RBF kernel):
$$K(x,z)=exp(-\frac{||x-z||^2}{2\sigma^2})$$和sigmoid核：
$$K(x,z)=tanh(ax^Tz+c)\\ tanh(b)=\frac{1-e^{-2b}}{1+e^{-2b}}$$
“SVM with a sigmoid kernel is equivalent to a 2-layer perceptron”，一个结论，显式的证明就不用写了，其实在看到拉格朗日乘子alpha时，我们就可以直观的联想到拉格朗日乘子相当于感知机场景下对feature的权重。

序列最小最优化算法，sequential minimal optimization,SMO alg.

引入核函数的非线性转化为线性（甚至是可分）的凸二次规划问题：
$$\min\limits_{\alpha}:\frac{1}{2}\sum\limits_{i,j=1}^N{y_iy_j\alpha_i\alpha_jx_i^Tx_j}-\sum\limits_{i=1}^N{\alpha_i},\\
s.t.\ \sum\limits_{i=1}^N{\alpha_iy_i}=0$$
非线性引入Gaussian核的SVM实现如下：

1
def SVM():

概念补充

supprot vector:线性不可分情况下，对偶问题的解$\alpha=(a_1,a_2…a_N)^T中a_i对应的样本点(x_i,y_i)就是支持向量。$
凸优化问题：设$f:F\rightarrow{R}为$凸函数，则求$\min\limits_{x\in{F}}{f(x)}为$凸优化问题
凸优化有如下几个定理

1
2
3
凸优化任意局部最优解即全局最优解
凸优化最优解集为凸集
若函数f为非空凸集上的严格凸函数，且凸优化问题存在全局最优解，那么全局最优解唯一

在条件$f_i(x)\leq0,1,a_i^T\cdot x = b_i$最小化$f_0(x)$，
凸集指一个集合空间内部两点间连线所覆盖的点都在集合空间内，
凸二次规划（convex quadratic programming）指目标函数为凸二次函数，形如
$$min f(x)= \frac{1}{2}x^TQx+C^Tx,\\
s.t.\ Ax\leq{b}，其每一行对应一个约束$$
Karush-Kuhn-Tucker condition:
$\alpha_i\geq{0}\\
y_i(wx_i+b)\geq{1}\\
\alpha_i(y_i(w_ix+b)-1)=0$

随机森林，梯度提升决策树

梯度提升决策树（GBDT）对于输入的一个样本实例，首先会赋予一个初值，然后会遍历每一棵决策树，每棵树都会对预测值进行调整修正，最后得到预测的结果

随机森林减少模型方差，提高性能
GBDT减少模型偏差，提高性能