统计学习方法札记

统计学习方法概论

统计学习方法其实就是学习已有的大量数据（输入空间）用模型来总结出规律（特征空间），并对未知类似事件做出预测（输出空间）的一个过程（不知道自己的这个理解有没有问题）。主要的问题包括分类问题和回归问题，核心的步骤其实就是：模型+策略+算法=方法。

相对于非监督学习，现在应用较为广泛的为监督学习，监督学习的模型为条件概率分布或者决策函数。对于模型需要考虑的几点包括：损失函数、泛化能力以及防止过拟合。模型选择的方法包括：正则化和交叉验证。正则化是结构风险最小化的实现，而交叉验证在数据集较多时把数据分为训练集、验证集和测试集，验证集用于对训练得到的多个模型进行选择而测试集用于评估。对于数据集较小时可采用

  • 简单交叉验证 直接将数据集分为训练集和测试集，并在各种条件下进行训练，根据测试集选择最终模型
  • S-fold交叉验证 将数据集切分为S份，然后每次都选不同的S-1个作为训练，另一个作为测试，重复S次。当S=N的时候，就是留一交叉验证

监督学习方法包括生成方法（对应生成模型）、判别方法（对应生成模型和判别模型）。生成模型包括朴素贝叶斯和隐式马尔科夫模型，判别模型包括K近邻法、感知机、决策树、logistic回归模型、svm以及提升方法和条件随机场。

对于分类问题有方法：K近邻法、感知机、朴素贝叶斯、决策树、决策列表、logistic回归模型、svm、提升网络、贝叶斯网络、神经网络和Winnow等。标注问题的方法有：隐式马尔科夫模型、CRF（用于信息抽取及自然语言处理），回归问题主要就是最小二乘法等。这里重点说一下二分类问题中的准确率和召回率，先定义分类器的预测情况：TP为正预测为正、FN正预测负、FP负预测正、TN负预测负，然后准确率P和召回率R分别定义为：

$$P = \frac{TP}{TP+FP}$$ $$R = \frac{TP}{TP+FN}$$

线性回归

对一个问题的结果y与k个因素有关，可以建立多变量线性模型，例如可作假设函数\(h_\theta(x)\)，x表示k维向量

$$h_\theta(x) = \theta_0 + \theta_1 x_1 + ... + \theta_k x_k$$

其对应的损失函数\(J(\theta)\) 如下，m为输入训练数据的量，i表示第i个数据

$$J(\theta) = \frac{1}{2m} \sum_{i=1}^{m}(h_\theta(x_i) - y_i)^2$$

利用梯度下降的思想损失函数对参数求梯度如下

$$\frac{\partial J}{\partial \theta} = \frac{1}{2m} \sum_{i=1}^{m} 2(h_\theta(x_i) - y_i)*(1,x_{i1},x_{i2},...x_{ik})$$

所以对于参数\(\theta\)的学习过程为

$$\theta_{new} = \theta - \alpha \frac{\partial J}{\partial \theta}$$ 
class LinearRegression(object):
    def __init__(self, train_x, train_y, need_normalized = 0):
        self.n,self.k = np.shape(train_x)
        self.need_normalized = need_normalized
        self.train_x,self.train_y = train_x,train_y
        if self.need_normalized == 1:
            self.normalized_value = []
            for i in range(self.k):
                minxi = np.min(self.train_x[:,i])
                maxxi = np.max(self.train_x[:,i])
                self.train_x[:,i] = (self.train_x[:,i] - minxi)/(maxxi-minxi)
                self.normalized_value.append([minxi, maxxi])
        self.train_x = np.concatenate((np.ones([self.n,1]), train_x), axis=1) # there is a theta0
        self.theta = np.array(np.ones(self.k+1))

    def hypothesis(self):
        return np.dot(self.train_x, self.theta.T)

    def loss(self):
        return np.sum((self.hypothesis() - self.train_y) ** 2) / 2*self.n

    def gratitude(self):
        delta = np.array(self.hypothesis() - self.train_y)
        return np.dot(delta.T, self.train_x) / self.n

    def train(self,iteration, alpha):
        cost_list = []
        for i in range(iteration):
            self.theta -= alpha * self.gratitude()
            cost_list.append(self.loss())
        return cost_list

    def predict(self, x):
        x = np.array(x, dtype = float)
        if self.need_normalized == 1:
            for i in range(self.k):
                minxi,maxxi = self.normalized_value[i]
                print(minxi, maxxi)
                x[:,i] = (x[:,i] - minxi)/(maxxi-minxi)
        x = np.concatenate((np.ones([1,1]), x), axis=1)
        return np.dot(x, self.theta.T)

线性回归完整代码

感知机

输入空间为\(\chi\subseteq R^n\)，输出空间为1或-1时，输入的x表示实例的特征向量，对应特征空间的一个点，输出为实例的类别。感知机就是对输入实例的特征向量进行二分类的线性分类模型，这里其实就相当于超平面为 \(w*x+b\) ，损失函数就对应误分类点到超平面的总距离。符号函数如下：

$$f(x) = sign(w*x+b)$$

感知机损失函数两种表示如下：

$$L(w,b) = - \sum_{x_i\in M} y_i*(w*x_i+b)$$ $$J(\theta) = - \sum_{x_i\in M} y_i(\theta_0 + \theta_1 x_{i1} + ... + \theta_k x_{ik})$$

利用梯度下降的思想损失函数对参数求梯度如下

$$\frac{\partial J}{\partial \theta} = - \sum_{x_i\in M} y_i (1,x_{i1},x_{i2},...x_{ik})$$

感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，当数据集线性可分时，感知机学习算法收敛。

def hypothesis(self):
    return np.dot(self.train_x, self.theta.T)

def loss(self):
    cost = 0
    h = self.hypothesis()
    for i in range(self.n):
        if self.train_y[i] * h[i] <  0:
            cost += -1 * self.train_y[i] * h[i]
    return cost

def gratitude(self):
    delta = np.zeros([1,self.k+1])
    h = self.hypothesis()
    for i in range(self.n):
        if self.train_y[i] * h[i] <  0:
            delta+= -1*self.train_y[i]*self.train_x[i]
    return delta

感知机完整代码

K近邻法

k近邻法的三个基本要素包括：k值的选择、距离度量及分类决策规则。其输入为特征向量输出为实例的类别，方法主要为根据给定的距离度量在训练集T中找到与x最近的k个点记作\(N_k(x)\)，然后根据如下分类决策规则来决定x的类别，如下为预测时y的取值，其中\(i=1,...,N\)，和\(j=1,...,K\)

$$y = arg \max_{c_j} \sum_{x_i\in N_k(x)}{I(y_i = c_j)}$$

其中I为指示函数，当\(y_i = c_j\)时I才为1，否则为0。 若要考虑如果快速搜索这k个最近点，可以使用kd树。

朴素贝叶斯法

朴素贝叶斯是典型的生成学习方法，由训练数据学习联合概率分布\(P(X,Y)\)，然后求得后验概率\(P(Y|X)\)，朴素贝叶斯的基本假设是条件独立性，可以使用极大似然估计或贝叶斯估计来获得联合概率分布

$$y = arg \max_{c_k} P(Y=c_k)\prod_{j=1}^n{P(X_j=x^{(j)}|Y=c_k)}$$

简单来说就是将输入的x分到后验概率最大的那个y，后验概率最大等价于0~1损失函数时的期望风险最小化

在算法的实现过程中，我主要使用了one-hot的思想，对于每一个可能出现的特征值都给其一个维度，这样以一个0或1的多维向量来表示一个分类样本，朴素贝叶斯的一个特点就是可以多次更新或者说增加训练的样本数据，这里使用feed来进行数据的增加，在predict之前需要进行一些参数的计算，所以需要调用feed_end来更新。这里采用加1平滑，并且利用log求对数来避免概率为0。

def feed(self, train_x, train_y):
    self.num_training += len(train_x)
    for i in range(len(train_x)):
        self.num_y_dict[train_y[i]] += 1
        self.sum_xvec_dict[train_y[i]] += train_x[i]
        self.hot_sum_dict[train_y[i]] += sum(train_x[i])

def feed_end(self):
    self.py_dict = {}
    self.regularized_xvec_dict = {}
    for l in self.labels:
        self.py_dict[l] = np.log(float(self.num_y_dict[l]) / self.num_training)
        self.regularized_xvec_dict[l] = np.log(self.sum_xvec_dict[l] / self.hot_sum_dict[l])

def predict(self, inputx):
    """
    make sure you call feed_end before predict
    """
    x = np.array(inputx)
    result = {}
    for l in self.labels:
        px = sum(self.regularized_xvec_dict[l] * x)
        result[l] = self.py_dict[l] + px # use log so here is +
    return sorted(result, key=lambda x:result[x])[-1] # return max

决策树

学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型，预测时，对新的数据利用决策树模型进行分类。决策树学习通常包括：特征选择、决策树生成和决策树修剪。特征选择的目的在于选取对训练数据能够分类的特征，常用的准则有：信息增益和基尼指数（CART），由于生成的决策树存在过拟合问题，所以需要进行剪枝，可以使用CART剪枝算法。

logistic回归与最大熵模型

关于最大熵模型，吴军在《数学之美》中浅出的解释过，就是要保留全部的不确定性，将风险降到最小，也就是要满足全部已知条件，而对位置情况不作任何假设。logistic回归模型和最大熵模型都属于对数线性模型，若离散随机变量的概率分布为\(P(X)\)，则其熵为：

$$H = -\sum_{x}{P(x)log P(x)}$$

logistic分布则为：

$$F(x) = P(X \leq x)=\frac{1}{1+e^{-(x-\mu)/\gamma}}$$

逻辑函数其实是一个一层的人工神经网络，对于NLP领域，需要训练的参数很多，类似于最大熵模型的训练，可以采用 GIS/IIS 等方式训练。logistic回归在广告系二分类问题中，两种类别的概率分别可以表示为：统中得到很好的应用，可以在《数学之美》中了解。

logistic二分类模型

首先用\(z = -(x-\mu)/\gamma\)来表示线性部分，可以进一步表示为，这里k表示输入x数据的维度，\(\theta_0\)则表示bias，也就是b

$$z = \theta_0 + \theta_1 x_1 + ... + \theta_k x_k$$

二分类问题中，两种类别的概率，也就是对应的hypothesis分别可以表示为：

$$P(Y=1|x) = \frac{e^z}{1+e^z} = sigmoid(z)$$ $$P(Y=0|x) = \frac{1}{1+e^z} = 1-sigmoid(z)$$

对于目标函数，表示为样本的概率之间的乘积，对于二分类可以用0和1来表示样本类型，将上述概率合并在一起，我们要学习的目的就是使得对于训练样本下面的object目标都越大越好，将指数问题取对数可以简化计算

$$object(x,y) = (P(Y=1|x))^y(P(Y=0|x))^{1-y}$$ $$object(x,y) = y\log(sig(z)) + (1-y)\log(1-sig(z))$$

所以对于整个训练样本的目标函数为J，可以用-J来表示损失函数

$$J(\theta) = \sum_{i=1}^mobject(x_i, y_i)$$

然后就可以用梯度下降算法更新参数\(\theta\)，损失函数对\(\theta\)求偏导完后可以得到梯度gradient为

$$gradient = (sigmoid(z) - y)x$$

这里可以看出来logistic回归二分类模型与线性回归和感知机有着几乎完全相同的梯度形式，因为他们在本质上是可以等价的，都是用已有的样本来训练一条最优直线

def gradient(self):
    delta = np.array(self.hypothesis() - self.train_y)
    return np.dot(delta.T, self.train_x)

def train(self,iteration, alpha):
    """use gradient to move steps

    Args:
        iteration
        alpha

    Returans:
        a list of loss
    """
    cost_list = []
    for _ in range(iteration):
        self.theta -= alpha * self.gradient()
        cost_list.append(self.loss())
    return cost_list

logistic多分类模型

logistci多分类模型在二分类的基础上变得复杂不少，但是核心的思想是相同的，考虑样本的概率连乘为目标函数，目标函数越大越好，主要考虑的是对于多分类问题不同类型的样本的概率的表示是不同的，对于随机变量Y设其取值为\(k \in {1,2\cdots,K}\)，对于K种Y只需要对应的K-1个\(\theta\)种参数就可以进行分类，也就是对应K-1条分类直线

则当\(k=1,2,\cdots K-1\)的时候，其概率表示为：

$$P(Y=k|x) = \frac{e^{z_k}}{1+\sum_{k=1}^{K-1}e^{z_k}}$$

当k=K-1的时候，概率为

$$P(Y=K|x) = \frac{1}{1+\sum_{k=1}^{K-1}e^(z_k)}$$

由于前k-1个的概率表示与第K种的概率表示是不同的，所以在写hypothesis函数的时候也要进行区分，就跟二分类的时候一个为sigmoid，一个为1-sigmoid一样，另外求偏导的时候也要进行区分。

目标函数可以表示为

$$J(\theta) = \sum_{i=1}^m\log(h_y(z))$$

目标函数求偏导，注意这里的z指的是一系列的z，因为有k-1个\(\theta\)，所以就有对应的这么多个z

$$\frac{\partial J}{\partial \theta} = \frac{1}{h_y(z)} \frac{\partial h_y}{\partial z} \frac{\partial z}{\partial \theta}$$

当样本的k==K时，有如下偏导，注意这里的S表示多个z对应的指数然后求和

$$\frac{\partial h}{\partial z_i} = - \frac{1}{(1+S)^2}$$

当样本的k

如下为样本为第k种的目标函数对\(z_k\)求偏导

$$\frac{\partial h}{\partial z_k} = \frac{e^{z_k}(1+S) - e^{2z_k}}{(1+S)^2}$$

对\(z_i\)且\(i!=k\)求偏导

$$\frac{\partial h}{\partial z_k} = \frac{e^{z_k}e^{z_i}}{(1+S)^2}$$

对于多分类的logistic回归模型，如吴军在《数学之美》中所说，等价于一个一层的人工神经网络，所以神经网络其实与线性模型比较相近，多分类logistic是求各种类对应的权重\(\theta\)，而将每一种类的\(\theta\)叠加起来就构成了一个简单的神经网络。

def feed(self, input_x, input_y, iteration=100, alpha=0.01):
    """use gradient to move steps

    Args:
        iteration
        alpha
    Middle Variables:
        train_x: the dimension here is k+1
        train_y: input_y

    Returans:
        cost_list &  theta_list
    """
    train_x = np.concatenate((np.ones([len(input_x),1]), input_x), axis=1) # there is a theta0
    train_y = input_y

    cost_list,theta_list = [],[]
    for ite in range(iteration):
        real_alpha = (40.0 / (ite+1) + 1) * alpha
        theta_list.append(self.label_theta[self.labels[0]].copy())
        for i in range(len(train_x)):
            x,label = train_x[i], train_y[i]
            S = 0
            expzlist = {}
            for l in self.labels[:-1]:
                expzlist[l] = np.exp(np.dot(self.label_theta[l].T, x))
                S += expzlist[l]
            h = self.hypothesis(label, x)
            # h_z_partial = {}
            if label == self.labels[-1]:
                for l in self.labels[:-1]:
                    delta = -1*expzlist[l] /pow(1+S, 2)
                    self.label_theta[l] += (1/h) * real_alpha * delta * x # update theta
            else:
                for l in self.labels[:-1]:
                    if label == l:
                        delta = (expzlist[l]*(1+S) - pow(expzlist[l],2)) / pow(1+S, 2)
                    else:
                        delta = -1*(expzlist[l]*expzlist[label]) / pow(1+S, 2)
                    self.label_theta[l] += (1/h) * real_alpha * delta * x # update theta
        cost_list.append(self.loss(train_x,train_y))
    return cost_list,theta_list

二分类和多分类logistic回归的完整代码

我使用这个多分类logistic回归模型对部分搜狗的中文数据进行分类，取得了比较好的效果

支持向量机

支持向量机是一种二分类模型，是定义在特征空间上间隔最大的线性分类器，间隔最大这一点使它有别于感知机，svm模型可分为：线性可分支持向量机、线性支持向量机以及非线性支持向量机。

当训练集线性可分时，存在无穷多个分离超平面可以将两类数据分开，这是线性可分支持向量机通过间隔最大化来求最优超平面，这个超平面就是唯一的，表示为\(w^* * x+b^*\) ，对应的分类决策函数为

$$f(x) = sign(w^* * x+b^*)$$

对于线性支持向量机，数据不能完全可分时，可采用引入噪声及松弛变量。对于非线性支持向量机，要考虑核函数的选取，核函数关键在于空间变换，将非线性空间映射到线性空间。

隐马尔可夫模型 HMM

隐马尔可夫模型即hidden Markov model，是可用于标注问题的模型，描述由隐藏的马尔可夫链随机生成观测序列的过程。先介绍一下Markov链，就是满足Markov性质的状态及状态转移性质，而Markov性质指的是每一个节点的状态产生的概率只跟它的上一个节点的状态有关。马尔可夫模型在语音识别和自然语言处理中应用广泛，如中文分词，在jieba分词中就有是否使用HMM的选项。

关于HMM的解释，参考知乎问题：

知乎上一位答主使用战士的三种隐藏战斗形态的转换过程的例子非常生动形象，直观的描述了HMM。而吴军在《数学之美》中以通信为引来解释HMM则拉近了HMM与自然语言处理的距离。生活中最普通的信息，包括图像、声音和文字几大类，图像信息由于其本身像素的组成很容易由数学的矩阵来描述故而较为容易处理，而现在图像处理已经发展很快了。对于语言的处理，无论是语音识别还是文本的处理，都可以看成是一个信息的编码与解码的过程。正是因为信息的抽象性，使得无论是象形文字汉字还是拉丁文英法等文字，都可以用类似于HMM这样的统计模型进行处理。

以中文分词为例，很显然，这是一个中文分词是一个上下文相关的事情，并且同一个句子可能有多种分词方式，以HMM的方式来处理的话，就是要找到产生序列概率最大的那种分词方式。HMM中需要满足的一个条件是一个状态的概率只跟上一个状态相关，这一点在NLP中需要扩展到跟之前几个状态相关，这里就涉及到了NLP中的多元文法了，这样并不会产生问题，至于选择跟前面的几个状态相关，那就是在计算量和准确率之间做tradeoff了。

隐马尔可夫模型的三个基本问题：

  • 1.给定一个model，如何计算某个特定输出序列的概率，Forward-Backward算法
  • 2.给定一个model和某个特定输出序列，如何找到最可能产生这个输出的状态序列，Viterbi算法
  • 3.给定足够量的观测数据，如何估计隐马尔可夫模型的参数

对于第三个问题，也就是隐马尔科夫模型的训练方法，一般来说对于模型的训练如kNN、SVM等都采用监督学习方法，对于HMM就是利用大量的人工标注数据来训练状态转移概率，而HMM的应用场景决定了这种方式很难实现，无论是语音识别还是中英文机器翻译，都很难产生这种对于每一个状态转移都进行人工标注的数据。所以就产生了无监督的训练方法，主要就是鲍姆-韦尔奇算法。

李航的《统计学习方法》中给出了鲍姆-韦尔奇算法的具体公式，而吴军在《数学之美》中则描述了这个算法的原理。对于一组输出序列O，首先找到一组模型参数（例如概率均匀分布的模型肯定满足）使其能够输出序列O，然后根据这个model和输出序列，可以找到模型产生O的所有可能的路径以及这些路径的概率，而这些路径实际上是记录了状态的变换过程，可以将其看做是“标注好的训练数据”，用来计算出一组新的更好的模型参数，然后不断迭代。鲍姆-韦尔奇算法的每一次迭代都是一个估计新的模型参数的过程，称为期望值最大化（Expectation-Maximization），简称为EM过程，能够收敛到一个局部最优点，但不能保证找到全局最优点。

Reference