机器学习实战笔记 – 朴素贝叶斯(Naive Bayesian)

Intro

朴素贝叶斯算法通过输入向量在已经在样本中且属于某一个分类的条件概率来进行分类即:

$$ p(c_{i}|x, y)$$

本算法通过选取最大的概率\(p\)来确定输入所属的分类。

在本节中,我们将以一个垃圾邮件过滤器为例,通过朴素贝叶斯来对一封邮件是否属于垃圾邮件进行分类。而对于一封邮件是否属于垃圾邮件,我们通过计算条件概率:\(p(BAD|WORDS)\)与\(p(GOOD|WORDS)\)后比大小来进行判定。

为了计算\(p(BAD|WORDS)\),我们需要用到贝叶斯准则:

$$p(BAD|WORDS) = \frac{p(WORDS)p(BAD)}{p(WORDS)}$$

首先对训练集中的所有邮件构建词表,即构造一个\(n\)维向量,其中\(n\)为训练集中所有邮件出现过的单词的数量(重复不计)。

其中,\(p(BAD)\)为训练集所有邮件中垃圾邮件的出现概率,而\(p(WORDS)\)表示训练集中每一封邮件的词向量中每一个词在所有邮件的词向量出现的概率,需要注意的是\(p(WORDS)\)是一个向量。这里用到了条件独立性假设,即假设所有词出现的概率都相互独立,所以对于\(p(WORDS)\),可以通过计算\(p(WORD_i)\)得到。而对于\(p(WORDS|BAD)\),可以通过训练集中类别为垃圾邮件的词向量集合累加在除以总次数得到。

在本问题中,我们无需计算\(p(WORDs)\),因为对于垃圾邮件的是非,他们的\(p(WORD)\)是相同的。

最后我们通过输入向量与\(p(WORDS) × p(BAD/GOOD)\)相乘,然后比较大小,从而选择较大概率的分类作为结果。

朴素贝叶斯具有以下特点:

优点:数据较少时仍然有效,可以处理多类别问题。

缺点:对输入数据非常敏感。

适用数据类型:标称型。

Algorithm

  1. 数据预处理,建立独立特征表,将训练集数据处理为特征表长度维度的向量。
  2. 对于每个标签,分别求该标签的概率\(p^{C_i}\)与训练集中属于该标签的向量每个独立特征的概率\(p^{c_i}_i\)。
  3. 将输入与\(p^{c_i}_i\)和\(p^{C_i}\)相乘,选择较大的作为分类结果。

Code

def train(training_set, labels):

    training_set_size = len(training_set)

    vector_size = len(training_set[0])

    bad_probability = np.sum(labels) / float(len(labels))

    # For performance, we use ones(vector_size) to replace zeros(vector_size)

    vector_of_every_words_sum_bad = np.ones(vector_size)

    vector_of_every_words_sum_good = np.ones(vector_size)

    # For performance, we use 2.0 to replace 0.0

    word_vectors_sum_bad = 2.0

    word_vectors_sum_good = 2.0

    for index in range(training_set_size):

        if labels[index] == 1:
            
            vector_of_every_words_sum_bad += training_set[index]

            word_vectors_sum_bad += np.sum(training_set[index])

        if labels[index] == 0:

            vector_of_every_words_sum_good += training_set[index]

            word_vectors_sum_good += np.sum(training_set[index])

    # For accuracy, we use log to replace direct divide into ln(x)

    vector_of_every_word_and_bad_probability = np.log(vector_of_every_words_sum_bad / word_vectors_sum_bad)

    vector_of_every_word_and_good_probability = np.log(vector_of_every_words_sum_good / word_vectors_sum_good)

    return vector_of_every_word_and_bad_probability, vector_of_every_word_and_good_probability, bad_probability


def classify(vector, p0, p1, p):

    # For accuracy, we use ln(x) to raplace origin bad probability

    aye = np.sum(vector * p0) + np.log(p)

    nay = np.sum(vector * p1) + np.log(1 - p)

    return 1 if aye > nay else 0

Summary

以上是对朴素贝叶斯算法在机器学习实战中的总结,在下一节我们将介绍Logistic回归。

机器学习实战笔记 – 决策树(Decision Tree)

Intro

决策树的核心算法有多种实现,如在机器学习技法介绍的C&RT,以及未涉及的C4.5,以及本书中介绍的ID3。

对于ID3,我们首先定义某个符号或者分类\(x_i\)的信息如下:

$$l(x_i) = -\log_{2}{p(x_i)}$$

其中,\(p(x_i)\)为某符号或者分类在训练集\(D_{train}\)中在所有的符号或者分类中出现的频率,接着我们定义信息熵\(H\):

$$H = – \sum^{n}_{i=1} p(x_i) \log_{2}{p(x_i)}$$

可以看出,信息熵\(H\)其实是求所有符号或分类的期望。

在本节中,决策树的构建算法将选择一个特征及其取值对训练集进行分割,使用该特征及其取值分割训练集可以使得分割后的\(n\)子训练集集信息熵相对于原信息熵增益最大,然后再递归地对子训练集使用该算法,直到训练集特征归一,即无法继续分割。

决策树算法具有如下特点:

优点:计算复杂度低、图形化表示后具有树形结构易于理解、对数据缺失不敏感。

缺点:如果没有Regularization,会出现Overfitting。

适用数据类型:数值型、标称型。

Algorithm

  1. 数据预处理,本算法只支持标称型数据,需要将所有的数值型数据转化为标称型;
  2. 构建决策树根节点,计算原始信息熵,初次选择最佳分割特征,存储最佳分割特征索引;
  3. 根据最佳分割特征及其取值分割训练集,得到的子训练集将原最佳特征列移除;
  4. 对于每一个得到的子训练集重复步骤2到步骤4,直到没有特征可以分割;
  5. 返回决策树;

Code

由于函数与变量名严格按照Objective-C风格命名,表意清晰,故将注释略去。

def create_decision_tree(data_set, tags):

    labels = [vector[-1] for vector in data_set]

    if labels.count(labels[0]) == len(labels):
        return labels[0]

    if len(data_set[0]) == 1:
        return classify(labels)

    best_split_feature_index = get_index_of_best_split_feature(data_set)

    best_split_feature_tag = tags[best_split_feature_index]

    decision_tree = {best_split_feature_tag: {}}

    del(tags[best_split_feature_index])

    best_split_features = [vector[best_split_feature_index] for vector in data_set]

    best_split_features_set = set(best_split_features)

    for best_split_feature in best_split_features_set:

        sub_tags = tags[:]

        sub_data_set = split_data_set(data_set, best_split_feature_index, best_split_feature)

        sub_decision_tree = create_decision_tree(sub_data_set, sub_tags)

        decision_tree[best_split_feature_tag][best_split_feature] = sub_decision_tree

    return decision_tree

Summary

以上是对决策树算法在机器学习实战中的总结,在下一节我们将介绍朴素贝叶斯。

机器学习实战笔记 – k-近邻算法(K Nearest Neighbors)

Intro

k-近邻算法通过计算输入向量与训练集向量的距离来进行分类,在本书中我们使用欧式距离(Euclidean Distance):

$$d_{12} = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2 + (z_1 – z_2)^2}$$

本算法将输入向量与训练集中所有向量的欧氏距离从小到大排序,通过对比前k个训练集中的向量的标签,选择出现次数较多的标签,作为分类结果。

优点:精度高、鲁棒性好、只需要做简单的预处理。

缺点:时间、空间复杂度高。

适用数据类型:数值型、标称型。

在本节中,作者通过一部电影中出现打斗镜头和接吻镜头的的次数来判定一部电影是否是动作片还是爱情片。

Algorithm

  • 数据预处理,对于数值型问题,首先需要对输入向量与训练集进行归一化处理(Normalize),防止较大的数据对欧氏距离的结果造成干扰;
  • 计算输入向量与训练集中所有向量的欧氏距离;
  • 将计算结果从小到大排序;
  • 选取前k个样本集中的向量,统计每个向量所对应的标签在k个标签中出现的频率。
  • 返回出现频率最高的标签作为分类结果。

Code

def classify(x, training_set, training_labels, k):

    rows, columns = training_set.shape                              # 获取训练集矩阵的行、列数

    offset_matrix = tile(x, (rows, 1)) - training_set               # 将输入向量复制 rows 行,并与训练集矩阵相减

    square_offset_matrix = offset_matrix ** 2                       # 对结果矩阵中每一组行向量求平方

    offset_sum = square_offset_matrix.sum(axis=1) ** 0.5            # 求每一组行向量的和并开方

    sorted_index_of_offset_sum = offset_sum.argsort()               # 对欧氏距离数组的索引从小到大排序

    label_count = {}                                                # 创建标签字典,键为标签名,值为标签出现次数

    for i in range(k):
        label = training_labels[sorted_index_of_offset_sum[i]]      # 获得第k个索引对应的向量的标签
        label_count[label] = label_count.get(label, 0) + 1          # 将第k个索引对应的向量的标签出现次数+1并存储在标签字典

    sorted_class_count = sorted(label_count.iteritems(),            # 对标签字典的值(标签出现次数)逆序排序
                                key=operator.itemgetter(1),
                                reverse=True)

    return sorted_class_count[0][0]                                 # 输出出现次数最大的键值

Summary

以上是对k-近邻算法在机器学习实战中的总结,在下一节我们将介绍决策树。

机器学习技法笔记 – Matrix Factorization(矩阵分解)

Linear Network Hypothesis

一言以概之,Matrix Factorization是一种提取数据集隐藏特征的技术。

对于一些已有特征是类别(Categorical)的机器学习问题,我们通常需要对这些特征进行编码。

例如我们有关于用户信息的数据集,其输入为例如ID、血型、生日、爱好,输出则是某一个用户对多部电影的评分。

我们希望预测:对于一个数据集样本外的用户,他可能对现有的多部电影如何评分。

我们将以一个\(N-\tilde{d}-M\)的网络来说明Matrix Factorization是如何工作的:

可以看到,该网络具有一个输入层,一个隐含层,一个输出层。

我们用\(V^T\)与\(W\)表示每层网络的权重,在本问题中,输入X是一个\(N\)维列向量(\(N×1\)),因为该网络是一个\(N-\tilde{d}-M\)的网络,易知\(V^T\)是维度为\(\tilde{d}×N\),而\(W\)的维度为\(M×\tilde{d}\)

则输出层具有以下形式:

$$h(x) = W^TVx$$

为了简化问题,我们假设在本问题中只有一个特征(性别)需要被编码,那么对于输入\(x\)来说,这个列向量矩阵是非常稀疏的,它可能具有以下形式:

$$x = \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix}^T$$

试想,这样一个稀疏向量对矩阵\(V\)进行线性组合,结果显而易见地将是仅有在向量\(x\)中不为零的列\(n\)将会在矩阵\(V\)中保留下来,所以我们的\(h(x)\)可以进行如下简化:

$$h(x) = W^Tv_{n}$$

其中,\(v_n\)是矩阵\(V\)的第\(n\)列。

Basic Matrix Factorization

对于Matrix Factorization,我们希望:

$$y ≈ h(x) = W^Tv_{n} = W^TVx$$

在本问题中,输出\(y\)是一个\(M×1\)的列向量,代表了用户对每部电影的评分。

同时我们知道\(v_{n}\)是一个\(\tilde{d}×1\)的列向量,而\(W^T\)是\(M×\tilde{d}\)的矩阵,那么对于某一部电影的评分则有以下形式:

$$y_{m} = w_{m}^Tv_{n}$$

其中,\(w_m^T\)是矩阵\(W\)的第\(m\)行。

而\(W^TV\)与\(w_{m}^Tv_{n}\)的关系则有下图:

我们认为,\(W\)与\(v_n\)分别描述了电影的特征与用户的特征。

一个直观的结论即是,当\(v_n\)在对\(W\)做线性组合时,如果在用户特征矩阵(列向量)\(v_n\)与在电影特征矩阵\(W\)的第\(m\)行的内积,即是用户\(n\)对电影\(m\)的评分。

这个分数直观的反映了用户的某些特征对电影的某些特征的“接近程度”。

所以,Matrix Factorization的学习过程即最优化\(w_m^T\)与\(v_n\)的过程。

定义Matrix Factorization的Error Function如下:

$$E_{in}({w_m}, {v_n}) = \sum_{m = 1}^{M} \left( \sum\left( y_{nm} – w_m^T v_n \right)^2\right)$$

问题转化为了一个具有两个变量的最优化问题。

与上节在RBF Network中介绍的k-Means的最优化问题相同,我们首先为\(W\)与\(V\)设置初始值,然后固定一个优化另一个。

每一个优化过程都是一个Linear Regression的过程,最终他们将收敛于\(E_{in} = 0\)

这种算法被称为Alternating Least Squares,其具体流程如下:

我们可以发现,Matrix Factorization与Linear AutoEncoder具有相似和不同之处:

相对于Linear AutoEncoder而言,其最优解是一个全局的最优解,而对于Matrix Factorization而言,其最优解是一个局部的最优解。

它们都是一种网络的模型,用于提取数据集的隐藏特征。

Stochastic Gradient Descent

除了Alternating Least Squares,SGD同样可以用于求解Matrix Factorization的局部最优解。

同时SGD可能在一些情况相对于Alternating Least Squares而言具有更好的性能,同时由于实现简单,在实际问题在更常使用。

对于原Error Function:

$$err(v_n, w_m) = \left( y_{nm} – w_m^T v_n \right)^2$$

分别对\(v_n\)与\(w_m\)求其梯度:

$$\nabla_{v_n}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)w_m\\ \nabla_{w_m}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)v_n$$

我们可以发现\(w_m\)的梯度值正比于\(v_n\),反之亦然。

我们可以通过这一性质简化SGD的过程,我们通过计算下式:

$$\tilde{y}_{nm} = (y_{nm} – w^T_{m}v_{n})$$

然后通过下式更新变量:

$$v_n^{new} ← v_n^{old} + \eta ·  \tilde{y}_{nm} w_{m}^{old} \\ w_m^{new} ← w_m^{old} + \eta ·  \tilde{y}_{nm} v_{n}^{old}$$

从而通过SGD来做Matrix Factorization的训练过程。

Summary of Extraction Models

某种意义上,Feature Transform(特征转换)即是一种Extraction Models,截至目前,我们已经介绍了多种Aggregation Model,每种Aggregation Model都具有自己的Extraction Models,下图是一个简略的总结:

我们可以看到,各个Aggregation Model用于提取数据模型特征的方法不尽相同,具体的每一个方法,我们在前几章均已经做了详细的介绍。

最后我们将Neural Network、RBF Network、Matrix Factorization做一个简单的整理:

对于这三种非线性的模型,他们的优点是明显的,即他们足够强大,如果数据量足够大、隐含层足够多,他们的泛化能力将会非常强大。

但是缺点也显而易见,即这些模型面对的问题本身可能是非凸的,即可能本身没有一个最优解,同时我们需要时刻注意Regularization与Validation,以避免Overfitting的发生。

以上是对Matrix Factorization在台湾大学机器学习技法课程的笔记总结。

至此,所有课程中相关的机器学习技法已经全部介绍完毕了。

在下一篇文章中,我们将会对机器学习技法做最后的总结。

 

机器学习技法笔记 – Radial Basis Function Network(RBF Network)

RBF Network Hypothesis

一言以概之的说,RBF Network是一种根据RBF的线性组合。

其中每一个RBF用于描述了某个数据点与某个聚类的相似度,然后将他们进行线性组合而成的网络,即是RBF Network。

它和使用了Gaussian Kernel的SVM具有相似之处,即某种意义上它们都是通过计算某个数据点与样本中某个点的相似度来进行分类或者预测的。

在SVM中,用于参与计算的通常是那些支撑向量:

而在RBF Network中我们的\(h(x)\)通常具有以下形式:

$$h(x) = sign(\sum^{M}_{m=1} \beta_{m}RBF(x, \mu_{m}) + b)$$

其中\(\beta_{m}\)是每个RBF的权重,其中\(\mu_{m}\)通常是某个聚类算法生成的簇中某个代表点。

不同于神经网络通过多权重和多个隐含层计算下层输入与输出,RBF Network通常具有以下图像化的描述:

RBF Network Learning

那么如何训练RBF Network Learning呢?

我们首先介绍一种简单的方法,即Full RBF Network。

在Full RBF Network中,在上节的\(h(x)\)中,\(M=N\),即RBF的数量即数据集的大小,而\(\mu_m=x_m\),即对于每一个RBF,它的代表点即是\(x_m\),而令\(\beta_m=1 · y_m\),即每个RBF平权,则Full RBF Network具有以下形式:

$$g_{uniform}(x) = sign(\sum^{M}_{m=1} y_{m}exp(-\gamma \Vert{x-x_{m}}\Vert^2))$$

Full RBF Network也被称为Nearest Neighbor,观察上式,可以发现上式中\(g(x)\)正是在寻找某个与\(x_m\)距离最近的\(x\),其中:

$$exp(-\gamma \Vert{x-x_{m}}\Vert^2)$$

根据\(\gamma\)的取值与指数函数的性质,与代表点距离越近的点使得函数值越接近\(1\),而偏离的点衰减很快。

我们可以通过寻找数据集中\(k\)个最具代表性的点,来组成具有\(k\)个RBF构成的RBF Network。

这又被称之为k Nearest Neighbor(k近邻)。

回到Full RBF Network的话题,无论是采用全部数据作为代表点还是前\(k\)个代表点,如何最优化\(\beta\)矩阵也是一个重要话题。

此时的RBF Network某种意义上可以类比于一个Linear Blending Model,我们可以添加Regularizer后通过解Linear Regression的问题得到最优的\(beta\)矩阵,它具有以下形式:

$$\beta = (Z^TZ + \lambda I)^{-1}Z^Ty$$

但是显然\(E_{in} = 0\)与Full RBF并不是我们想要的,它显然可能会导致Overfitting,接下来我们将介绍k-means算法,来解决这个问题。

k-Means Algorithm

无论是采用Full RBF Network还是K Nearest Neighbor,我们都可能遇到这种情况,如果\(x_1 ≈ x_2\), 如果\(x_1, x_2\)都作为代表点参与RBF Network,这显然是冗余的。

我们可以将\(N\)个数据点通过聚类分成\(M\)个簇,为每一个簇选择最具代表性的\(\mu_m\),通过这种方法将产生\(M\)个RBF。

这种算法被称为k-Means Algorithm,它的具体工作方式总是希望最小化下式:

不过显然可以预见的是,上式因为具有两组变量需要最优化,我们必须先固定一组变量进行最优化。

我们首先假设\(M\)个簇已经确定,即有\(S_1, ···, S_M\),我们首先固定了\(S_m\),来优化\(\mu_m\),对原式求梯度得:

由于判断数据点是否属于\(S_m\)的布尔运算,所以将有右式的结果。

令原式等于\(0\),可以发现:

$$\mu_m = \frac{-2 · \underset{x_n∈S_m}{\sum x_n}}{\vert{S_m}\vert}$$

但是在实际的k-Means算法中,我们通常先初始化\(\mu_m\),然后优化\(S_m\),然后重复上述步骤,直至收敛(\(E_{in} = 0\)):

这就是k-Means算法。

将k-Means结合RBF Network,则有以下步骤:

我们首先通过k-Means获得\(M = k\)个\(\mu_m\),然后得到\(M\)个RBF,然后再通过Linear Blending得到RBF Network:

k-Means and RBF Network in Action

以下分别是k-Means与Full RBF Network的运行效果图:

以上是对Radial Basis Function Network在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Matrix Factorization。

 

机器学习技法笔记 – Deep Learning(深度学习)

Deep Neural Network

一言以概之的说,Deep Learning(深度学习)通常也指Deep Neural Network(深度神经网络),也即DNN。

DNN通常设计并使用了多层神经网络,相对于浅层神经网络,他们通常分别具有如下特点:

对于浅层神经网络,它通常具有训练速度快、层次结构简单、泛化能力强。

而对于深度神经网络,它通常较难训练、层次结构复杂、泛化能力非常强,对于一些特定问题中使用的特定的深度神经网络模型,如CNN时,它可能还具有一定的物理意义,例如下图用于手写数字识别的DNN:

可以看出,在该DNN中,第二层的神经元分别都只专注于原始图像的某一块区域,这使得在这种问题,特别是图像处理问题中,赋予了这些神经元以物理意义。

而对于上文提到的DNN存在的较难训练、层次结构复杂等问题,随着硬件软件的进步带来的性能提升,已经逐渐不再是主要的问题。

我们在上节提到,对于Neural Network而言,不同的\(w^{(l)}_{ij}\)的Initialization(初始化)与Regularization可能会带来非常不同的局部最优解。

所以在本节,我们将更专注于训练DNN时的Regularization与Initialization问题上。

AutoEncoder

所谓Initialization也即是Pre-training。接下来我们介绍一种在实际中非常流行的Pre-training技术,称之为AutoEncoder。

AutoEncoder使用了一种被称之为Information-Preserving Encoding的思想。

对于\(l+1\)层第\(j\)个神经元的输入\(s^{(l+1)}_{ij}\),它们本质上第\(l\)层的输入\(x^{(l)}_{i}\)向量左乘了一个权重矩阵\(w^{(l+1)}_{ij}\)得到的。

Information-Preserving Encoding认为,一个好的\(w^{(l+1)}_{ij}\)应该尽可能使得:

$$tanh(s^{(l+1)}_{ij}) =w^{(l+1)}_{ij} ·x^{(l)}_{i} ≈ x^{(l)}_{i}$$

而AutoEncoder即是这样一种技术:

某种意义上,AutoEncoder训练出的每层权重,更像是一个Approximating Identity Function(近似恒等函数),它的作用如下:

即对于Supervised Learning(监督式学习)来说,Identity Function可以用于发现某些数据集隐藏的具有代表性的特征,而对于Unsupervised Learning(非监督式学习)来说,某些时候可以用于孤立点检测。

对于Basic AutoEncoder(一种最基本的AutoEncoder),它的Error Function具有如下形式:

$$e = \sum^{d}_{i=1} (g_{i}(x) – x_i)^2$$

使用Basic AutoEncoder用于Pre-training过程如下:

  • 利用AutoEncoder与反向传播算法逐层训练神经网络。
  • 使用\(w^{(1)}_{ij} =w^{(2)}_{ji}\)用于Regularization。

Denoising AutoEncoder

本节将会介绍一种用于对抗噪声的AutoEncoder,一言以概之,即是在Pre-training的时候主动添加人工噪声,通过这样被称之为Denoising AutoEncoder的方式进行Pre-training后,在之后的训练中,将具有更强的鲁棒性:

截至目前,我们已经有了四种Regularization的方法,他们分别是:Structural Constraints(结构化约束)、L1、L2 Regularizer(权重衰减正则化)、Early Stopping(提前停止)。

Principal Component Analysis

在本节中,我们将从最优化理论角度来分析为什么使用AutoEncoder来做Pre-training可以使得最终的DNN表现更好。

为了简化问题,我们假设某DNN的第\(k\)层输出\(h(x)\)具有如下形式:

$$h_k(x) = \sum^{\widetilde{d}}_{j=0} w_{kj}(\sum^{d}_{i=1} w_{ij}x_{i})$$

同时约定:

  • 移除\(x_0\)偏置项
  • 以\(w^{(1)}_{ij} = w^{(2)}_{ji} =w_{ij}\)作为Regularizer
  • 假设输出维度\( \tilde{d}\)远小于输入维度\(d\):

同时,将\(h_{k}(x)\)写成矩阵乘法形式如下:

$$\mathbf{h(x) = \color{red}{W}\color{blue}{W^{T}}X}$$

在上式中:

  • \(X\)是\(d×1\)的矩阵
  • \(\color{blue}{W^T}\)是\(\tilde{d} × d\)的矩阵
  • \(\color{blue}{W^T}X\)是\(\tilde{d}×1\)的矩阵
  • \(\color{red}{W}\)是\(1×\tilde{d}\)的矩阵
  • \(\color{red}{W}\color{blue}{W^T}X\)是实数

其Error Function具有如下形式:

$$E_{in}(W) = \frac{1}{N} \sum^{N}_{n=1} \begin{Vmatrix}X_n – \color{red}{W}\color{blue}{W^{T}}X_n \end{Vmatrix}^2$$

为了最小化\(E_{in}\),回忆线性代数的知识,我们首先对\(\color{red}{W}\color{blue}{W^{T}}\)做特征分解:

$$\color{red}{W}\color{blue}{W^{T}} =\color{red}{V}\Gamma\color{blue}{V^{T}}$$

其中,\(V\)为\(\Gamma\)矩阵中每个特征值对应的特征向量构成的矩阵,\(\Gamma\)为特征值构成的对角矩阵。

我们令:

$$X_n = \color{red}{V}I\color{blue}{V^{T}}X_n$$

则可以将原式改写为以下形式:

$$\min\limits_{v}\min\limits_{\Gamma} \frac{1}{N} \sum^{N}_{n=1} \begin{Vmatrix}\color{red}{V}I\color{blue}{V^{T}}X_n – \color{red}{V}\Gamma\color{blue}{V^{T}}X_{n} \end{Vmatrix}^2$$

首先最优化\(\Gamma\),此时\(V\)可以视为常数,通过观察上式,我们可以发现原函数值只与\(I – \Gamma\)有关,其中\(\Gamma\)是对角矩阵,它的秩小于等于\(\tilde{d}\),我们希望\(I – \Gamma\)的值越小越好,即\(\Gamma\)越接近单位矩阵\(I\)越好。

所以,我们将最优化的\(\Gamma\)记作:

$$\begin{bmatrix} I_{\tilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}$$

然后我们将\(\Gamma\)视为常数,最优化\(V\),此时原函数可以改写为以下形式:

$$\min\limits_{V} \sum^{N}_{n=1} \begin{Vmatrix} \begin{bmatrix} 0 & 0 \\ 0 &I_{d- \widetilde{d}} \\ \end{bmatrix}V^{T}X_{n} \end{Vmatrix}^2$$

我们通过替换\(I_{d-\tilde{d}}\)为\(I_{\tilde{d}}\)改变了原函数的符号,将最小化问题替换为最大化问题:

$$\max\limits_{V} \sum^{N}_{n=1} \begin{Vmatrix} \begin{bmatrix}I_{\widetilde{d}} & 0 \\ 0 & 0 \\ \end{bmatrix}V^{T}X_{n} \end{Vmatrix}^2 $$

我们甚至可以通过观察发现,我们希望\(V\),即由特征向量组成的矩阵越大越好。

我们首先考察一种简单的情况,即\(\tilde{d}=1\),则原函数可由矩阵形式改写回原形式:

$$\begin{align} \max\limits_{V} \sum^{N}_{n=1} v^{T}x_{n}x^{T}_{n}v  && \text{subject to } v^{T}v = 1 \end{align}$$

上式是一个等式约束的最优化问题,回忆拉格朗日乘数法:即原函数的梯度与约束条件的梯度平行且方向相反,通过解其Lagrange Function来求得最优解:

$$\nabla{E_{in}} = \sum^{N}_{n=1} x_{n}x^{T}_{n}v – \lambda v = 0$$

而最优解的\(v\)正是在约束\(v^Tv=1\)下矩阵\(X^TX\)(输入数据集构成的\(n×n\)矩阵)的最大的一组特征向量。

而对于更一般\(\tilde{d}\),因为\(I_{\tilde{d}}\)是对角矩阵且有可能非满秩,即存在特征值为\(0\)为行列,所以对于每一个非零的特征值\(\gamma_j\),都存在一个最大的\(v_j\)与之对应,他们都是\(X^TX\)的特征向量。

求出了矩阵\(\Gamma\)与矩阵\(V\),则原矩阵\(\color{red}{W}\color{blue}{W^{T}}\)即为所求。

即我们得到了第\(k-1\)层各个输入与\(k\)层各个输入的特征转换关系,然后通过反向传播算法,进而计算出各个层的最佳权重,从而完成Pre-training。

以上是对Deep Learning在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Radial Basis Function Network。

机器学习技法笔记 – Neural Network(神经网络)

Motivation

一言以概之,Neural Network(神经网络)是一种Non-Linear Aggregation,我们首先从一个Perceptron(感知机)的Linear Aggregation开始,对Neural Network的工作原理做一个简单的介绍。

原始问题我们设定为分类问题,假设我们已经训练出了\(d\)个Perceptrons,并对其做Linear Blending,其\(G(x)\)具有以下形式:

若以Neural Network的角度,进行图像化的描述,则\(G(x)\)具有以下形式:

这样的\(G(x)\)即是最基础最简单的Neural Network(神经网络)模型了,它具有输入层,一层隐含层,输出层。

通过这样的单层Neural Network,我们可以实现\(AND(x_1, x_2)\)这样的数学运算:

它的\(G(x)\)具有以下形式:

用图形化的描述,以上Neural Network具有以下形式:

显然,我们可以通过更多,甚至无穷多的\(g_t\)进行Linear Blending,这种通过线性超平面经过无穷多组合后,甚至可以表示非线性的超平面:

但是这样并不是无代价的,其代价就是\(d_{vc}→∞\),在机器学习基石课程中曾经提到了\(d_{vc}\),\(d_{vc}\)是成长函数的Break Point,越大的\(d_{vc}\)意味着更强大泛化能力,但是也可能带来Overfitting与复杂的Model Complexity:

同时,单一层的Neural Network模型具有局限性,这样的Neural Network甚至不可以用来运算\(XOR(x_1, x_2)\),但是通过使用多层(多个隐含层),即可用来运算\(XOR(x_1, x_2)\),这某种意义上也是一种Feature Transform:

Neural Network Hypothesis

接下来为了后续问题的讨论,我们将用一些符号对Neural Network的一些基本概念做一些抽象化的定义。

对于一个如下形式的Neural Network:

其中,最左侧的\(x_0, x_1, x_2, … , x_d\)被称之为输入层,即输入的数据集。

而图中每一个节点被称之为一个神经元。

中间的两层被称之为隐含层,隐含层将其上层的输出\(s^{(l)}_j\)经过\(tanh(x)\)运算后作为下层的输入,其中\(s^{(l)}_j\)的计算公式如下:

$$s^{(l)}_j = \sum^{d^{(l-1)}}_{i=0} w^{(l)}_{ij}x^{(l-1)}_i$$

其中\(l\)是第\(l\)层,\(j\)是第\(j\)个神经元。

所以第\(l\)层的第\(j\)个神经元的输入计算公式如下:

$$x^{(l)}_j = \begin{cases}tanh(s^{(l)}_j) & \text{if l < L}\\ s^{(l)}_j & \text{if l = L} \end{cases}$$

其中\(tanh(x)\)的函数图像与解析式如下:

$$tanh(s) = \frac{exp(s)-exp(-s)}{exp(s)+exp(-s)} = 2\theta(2s)-1$$

\(tanh(x)\)在Neural Network模型中是一种流行的选择,因为它兼具线性函数与符号函数的特性。

夹在每一层中的\(w^{(l)}_{ij}\)被称之为权重,这也是我们后续需要优化的对象。

而最右侧层称之为输出层,即最终的结果。

梳理上述符号如下图:

对于每一层所有的神经元,他们的输入可以又以下矩阵表示:

Neural Network Learning

在Neural Network中,我们的目标是训练出每一层的所有\(w^{(l)}_{ij}\),使得最后的\(G(x)\)的\(E_{in}\)最小,我们定义Neural Network的Error Function如下:

$$e_n = (y_n – NNet(x_n))^2$$

接下来我们将介绍一种被称之为BackPropagation的算法来最小化\(e_n\):

我们首先考虑一个只有一个输出神经元的Neural Network,然后在输出层将\(e_n\)展开:

$$\begin{align} e_n & = (y_n – NNet(x_n))^2 = (y_n – s^{(L)}_1)^2 \\ & = (y_n – \sum^{d^{(L-1)}}_{i=0} w^{(L-1)}_{i1}x^{(L-1)}_i)^2 \end{align}$$

为了最小化\(L-1\)层权重\(w^{(L-1)}_{i1}\),我们对上式求偏微分,注意:

$$s^{(L)}_1 = \sum^{d^{(L-1)}}_{i=0} w^{(L)}_{i1}x^{(L-1)}_i$$

则原始关于\(w^{(L-1)}_{i1}\)偏微分具有如下形式:

$$\begin{align} \frac{\partial{e_n}}{\partial{w^{(L)}_{i1}}} & =\frac{\partial{e_n}}{\partial{s^{(L)}_{1}}} · \frac{\partial{s^{(L)}_1}}{\partial{w^{(L)}_{i1}}} \\ & =-2(y_n – s^{(L)}_1) · (x^{(L-1)}_{i}) \end{align}$$

然后我们可以通过Gradient Descent或者Stochastic Gradient Descent训练出一个最优的\(w^{(L)}_{i1}\),使得\(e_{n}\)最小,注意上式的\(w^{(L)}_{i1}\)隐含在\(s^{(L)}_1\)中。

我们令:

$$\delta^{(L)}_{1} = -2 (y_n – s^{(L)}_{1})$$

更一般地,对于任意层\(l\),其权重\(w^{(l)}_{ij}\)与\(e_n\)的偏微分关系如下:

$$\frac{\partial{e_n}}{\partial{w^{(l)}_{ij}}} =\frac{\partial{e_n}}{\partial{s^{(l)}_{j}}} ·\frac{\partial{s^{(l)}_{j}}}{\partial{w^{(l)}_{ij}}} =\delta^{(l)}_{j} · (x^{(l-1)}_i)$$

我们首先观察第\(l\)层第\(j\)个节点的\(\delta^{(l)}_{j}\)与\(e_n\)的关系:

$$s^{(l)}_{j} \stackrel{tanh}\Rightarrow x^{(l)}_{j} \stackrel{w^{(l+1)}_{jk}}\Rightarrow \begin{bmatrix}s^{(l+1)}_{1} \\ ··· \\ s^{(l+1)}_{k} \\ ··· \end{bmatrix}\Rightarrow ···\Rightarrow e_n$$

所以第\(l\)层第\(j\)个节点的\(\delta^{(l)}_{j}\)的计算公式如下:

$$\begin{align} \delta^{(l)}_{j} & =\frac{\partial{e_n}}{\partial{s^{(l)}_{j}}} \\ & = \sum^{d^{(l+1)}}_{k=1} \frac{\partial{e_n}}{\partial{s^{(l+1)}_{k}}} · \frac{\partial{s^{(l+1)}_{k}}}{\partial{x^{(l)}_{j}}} · \frac{\partial{x^{(l)}_{j}}}{\partial{s^{(l)}_{j}}} \\ & = \sum_{k} (\delta^{(l+1)}_{k}) (w^{(l+1)}_{jk}) (tanh'(s^{(l)}_{j})) \end{align}$$

通过计算上式,我们可以发现一个重要的事实:

即第\(l\)层的第\(j\)个节点的\(\delta^{(l)}_{j}\)可以通过第\(l+1\)层的\(k\)个\(\delta^{(l+1)}_{k}\)来表示。

如果假设本问题中的Neural Network只有一个输出节点,而我们已知:

$$\delta^{(L)}_{1} = -2 (y_n – s^{(L)}_{1})$$

然后,我们正向逐层计算\(x^{(l)}_{i}\),然后反向逐层计算所有\(\delta^{(l)}_{j}\),然后根据\(x^{(l)}_{i}\)与\(\delta^{(l)}_{j}\)更新梯度,从而最小化所有\(w^{(l)}_{ij}\),从而达到最小化\(e_n\)的目的。

这种算法被称之为BackPropagation Algorithm(反向传播算法),它的基本步骤如下:

通常步骤1到3会分多次,分多批并行进行,这种方式我们称之为mini-batch:

Optimization and Regularization

对于Neural Network的\(E_{in}\):

$$E_{in}(w) = \frac{1}{N}\sum^{N}_{n=1} err(( tanh(\sum_{i} w^{(l)}_{ij}x_{n, j})), y_n)$$

但是遗憾的是,多数情况下,Neural Network模型对应的\(E_{in}\)很可能不是凸函数(non-convex),所以多数情况下,我们可能无法找到所有的全局最优\(w^{(l)}_{jk}\),所以更多的情况我们可能会使用GD/SGD通过BackPropagation得到局部的最优。

通常情况下,不同的\(w^{(l)}_{jk}\)初始值决定了最后的局部最优解:

在下一节,我们将会介绍一种被称之为auto-encoder的方法,用于初始化\(w^{(l)}_{jk}\)。

接下来我们从VC Dimension的角度考察一下Neural Network,Neural Network的\(d_{vc} = O(V · D)\),其中\(V\)是神经元的数量,而\(D\)是各个神经元的权重。

我们可以看出,通过合理控制\(V\),我们可以得到Model Complexity与\(E_{in}和\)latex E_{out}$分别都在容忍范围的结果。

那么如何做Regularization呢?

一个基础的选择即是使用Weight-Decay L2的Regularizer:

$$\Omega(w) = \sum(w^{(l)}_{ij})^2$$

但是L2 Regularizer通常情况下带来的解释稠密的,为了避免这个问题,在Neural Network问题中一个更流行的Weight-Elimination Regularizer具有如下形式:

$$\sum \frac{(w^{(l)}_{jk})^2}{1+(w^{(l)}_{jk})^2}$$

这样的Regularizer具有L2 Regularizer的特性,同时等比缩放了每一个权重,一定程度避免了局部存在的较大权重带来的Overfitting。

同时,Early Stopping也是在Neural Network中常用的Regularization方法。

Early Stopping顾名思义即是提早停止,即在使用GD/SGD训练Neural Network时按适当的时机多次停止,并使用Validation验证Neural Network,并分别考察数次停止训练出的\(NNet(x)\),从而起到Regularization的效果。

为什么这样做可以起到Regularization呢?因为VC Dimension:

在机器学习基石的课程中我们曾有过结论,适当的\(d_{vc}\)通常是我们的最佳选择,而不是\(E_{in}=0\)的\(d_{vc}\)。

以上是对Neural Network在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Deep Learning。

机器学习技法笔记 – Gradient Boosted Decision Tree(GBDT)

Adaptive Boosted Decision Tree

一言以概之,Gradient Boosted Decision Tree简称GBDT,即AdaBoost与Decision Tree的Aggregation:

如果说Random Forest是在数据集上通过Bagging的方式,以数据集的随机性获得训练出决策树\(g_t\)的差异性。

那么对对于GBDT,则是通过Re-weighted的数据集,来训练出差异化的决策树\(g_t(t)\),最后将他们做Blending,来得到\(G(x)\):

接下来我们介绍一种被称之为Weighted Decision Tree Algorithm的算法,用于训练GBDT。

对于Re-weighted权重的最佳化问题,我们需要最小化下式:

接下来训练出\(u^t_n\)权重对应的\(g_t\),然后计算出Blending时该\(g_t\)的权重:

然后重复上述步骤\(T\)次,最后做Blending,得到\(G(x)\)。

但是这样做存在一些问题,对于一颗未经剪枝的决策树,它的\(E_{in}=0\),这非常可怕,这会导致错误率\(\epsilon_t=0\),这会导致\(\alpha_t=∞\),那么Blending也就显得毫无意义了,这样显然是不行的:

所以剪枝是必要的,在训练GBDT时,我们通常采用的决策树剪枝方法称之为Extremely-Pruned Tree,这种特殊的决策树的高度只有\(1\),是一种非常弱的决策树:

这种决策树又被称之为AdaBoost-Stump。

Optimization View of AdaBoost

接下来的内容,是对AdaBoost的一些数学上的理论分析,这一小节的理论分析,将会对\(\alpha_t=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon_t}})\)这一结论做详细的解释。

对于AdaBoost的Re-weighted,其\(u^{(T+1)}_n\)有以下计算方式:

以分类问题为例,在上式中,无论是乘以或者除以\(♦︎_t\),都可以简化为\(♦︎^{-y_ng_t(x_n)}_t\),然后添加\(exp(x)\),在指数中补一个\(\alpha_t\),从而进一步整理上式如下:

上式将连乘替换为连加,值得注意的是,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是\(G(x)\),所以我们有以下结论:

值得注意的是,对于下式:

与SVM中的Margin:

具有一些联系,可以看出,\(\sum^{T}_{t=1} \alpha_tg_t(x_n)\)即是为正规化的\(margin\),在SVM中,我们希望\(margin\)越大越好,在AdaBoost中也恰恰反映为如果\(\sum^{T}_{t=1} \alpha_tg_t(x)\)足够大,就会使得\(u^{(T+1)}_n\)足够小,从而达到Re-weighted的目的。

接下来我们介绍AdaBoost Error Function,对于AdaBoost,我们总希望\(u^{(T+1)}_n\)越小越好,所以我们希望\(\sum^{N}_{n=1} u^{(t)}_n\)越小越好,故AdaBoost Error Function具有以下形式:

对比\(err_{0/1}\)与\(err_{ada}\),我们可以发现\(err_{ada}\)是\(err_{0/1}\)上界:

接下来我们通过Gradient Descent(梯度下降)最小化\(\sum^{N}_{n=1} u^{(t)}_n\),注意\(h(x_n)\)是自变量:

通过观察,可以发现\(\frac{1}{N}exp(-y_n\sum^{t-1}_{\tau} \alpha_{\tau}g_{\tau}(x_n))\)可以进一步改写为\(u^{(t)}_n\),因此可以将原始进一步改写为以下形式:

上式是一个指数函数,回忆指数函数的麦克劳林泰勒展开:

$$e^x = \sum^{∞}_{n=0} \frac{x^n}{n!}$$

对上式做一阶泰勒展开:

由于:

$$\sum^{N}_{n=1} u^{(t)}_n = E_{in}$$

到此为止,回忆梯度下降的基本形式:

所以有:

$$v^T▽E_{in}(w_t) = \sum^{N}_{n=1} u^{(t)}_ny_nh(x_n)$$

需要注意的是,由于\(h(x_n)\)是函数,这里没有办法像在解Linear Regression或者Logistics Regression时,先对Error Function求梯度,再将\(x_n\)带入梯度函数后求值,同时乘以\(\eta\),然后迭代\(T\)次或者直到梯度值收敛到\(0\),所以进行了不同的处理。

回到原问题,最后问题转化为最小化下式:

以分类问题为例,上式的取值具有以下可能:

将等式右边进行如下改写:

回忆\(E_{in} · N = u^{(t)}_n\),所以上式可以继续改写:

那么谁来最小化\(E^{u^{(t)}}_{in}\)呢?回忆AdaBoost的工作过程,很容易发现是每一次根据\(u^{(t)}_n\)来训练\(g_t\)的过程。

那么最有步长\(\eta\)又该如何确定呢?这里同样与解Linear Regression或者Logistics Regression时不同,无法通过经验直接给定一个例如值为\(0.001\)的步长。

在AdaBoost每次根据当前权重训练出\(g_t\)时,回顾Error Function:

我们可以发现,除了\(\eta\),其他参数都是已知的,所以原问题转化为了一个最小化\(\eta\)的问题。

对于分类问题:

\(exp(-y_n{\eta}g_t(x_n))\)的取值可能有如下情况:

所以将原始进行一下改写:

最后令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\),最后求解得出\(\eta=ln(\sqrt{\frac{1-\epsilon_t}{\epsilon}})=\alpha_t\),即最佳步长。

小结一下上述推导:通过理论分析,我们证明了在使用AdaBoost时,通过梯度下降最小化\(u^{(t)}_n\)时,其最速下降方向\(h(x)\)即是每一次根据\(u^{(t)}_n\)来训练出\(g_t\),而最佳步长则是在训练出\(g_t\)后,令\(\frac{\partial{\widehat{E}_{ADA}}}{\partial{\eta}}=0\)后求解得出。

以上数学的推导即是AdaBoost在最佳化理论上的支撑。

Gradient Boosting

对于AdaBoost,其Error Function具有如下形式:

而所谓Gradient Boosting,它的Error Function则不再需要具体的形如指数函数这样的某一函数,它可以是任意函数:

如果将Gradient Boosting用于Regression问题,则可以使用平方误差函数:

对上式进行一阶泰勒展开:

与AdaBoost的情况类似,Regression问题在最小化\(h(x)\)时,最后经过化简,最终变成了最小化\(\sum^{N}_{n=1} h(x_n) · 2(s_n-y_n)\)的问题。

但是没有约束的\(h(x_n)\)有可能会使得\(h(x_n)=-∞\),如果是一个\(-∞\)的\(h(x_n)\),则步长\(\eta\)将无法约束下降步长,梯度下降也就无从谈起了。

所以Regularization是必要的,我们通过添加\(h(x_n)\)的平方项,再通过配方,将原式做以下改写:

我们可以发现,在\(y_n, s_n\)已知的情况下,求解\(h(x_n)\)即是求解一个Linear Regression问题。

最后确定最佳步长\(\eta\):

在各项已知的情况下,易求出\(\eta\)。

最后对Gradient Boosting做一下小结:

首先根据Gradient Boosting Error Function最小化\(g_t\),然后求出最佳化步长\(\eta\),也即Blending时的\(\alpha\),然后更新\(s_n\),重复\(T\)次,最后Blending,得出\(G(x)\)。

Summary of Aggregation Models

最后对所有的Aggregation方法做一个总结。

对于在训练完差异化的\(g_t\)后再进行Blending的方式:

对于一边训练出差异化的\(g_t\),一边进行Blending的方式:

以上是对Gradient Boosted Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Neural Network。

机器学习技法笔记 – Random Forest(随机森林)

Random Forest Algorithm

一言概之,随机森林即Bagging与Decision Tree的Aggregation:

其中,Bagging是指通过bootstrap的方式从数据集\(D\)中,随机抽选\(N\)组数据,重复\(T\)次,每次得到的数据集称之为\(\widetilde{D}_t\),然后通过C&RT等方法在\(\widetilde{D}_t\)上生成决策树,得到\(g_t\),最后通过Blending的方式对\(g_t\)线性组合,得到最后的\(G(x)=Uniform(g_t)\):

这里简要的回顾一下决策树与C&RT算法:

即在原始数据集\(D\)上通过Decision Stump训练出不纯度最低的\(b(x)\),再将数据集一分为二,然后将一分为二的数据集视为原始数据集,递归的训练重复上述步骤,直到不纯度为\(0\)或者数据集不可再分,最后进行剪枝。

值得注意的是,在Random Forest中,训练每一个决策树\(g_t(x)\)的过程是可以并行化的,因为每一个Bagging与Bootstrap操作与C&RT算法的执行互相独立。

Random Forest中对于每一颗由C&RT生成决策树来说,由于Bagging而从数据集的差异性上获得了\(g_t\)的差异性。

但是在实际应用中,Random Forest通常还会使用被称之为Feature Projection或者Feature Expansion的方法强化训练数据集的差异性,从而使得训练出的\(g_t\)经过Blending后表现更好。

所谓Feature Projection,即在\(n\)维数据集\(D\)中每次并非选取\(n\)维的数据,而是选取更低维度的数据,这种选取方式等效于对\(d’\)维向量\(x\)乘以一个对角线上部分为latex 0$的单位对角矩阵:

通过Feature Projection得到的Random Forest可以由以下形式概括:

而所谓Feature Expansion,是在经过Feature Projection操作后得到的\(d’\)维数据集\(\widetilde{D}\)的\(x\)向量的某一或多个维度上再乘以矩阵\(x\),得到一些具有新特征的向量:

通过FeatureExpansion得到的Random Forest可以由以下形式概括:

Out-Of-Bag Estimate

回顾Random Forest的Bagging过程,对于每一颗训练出的决策树\(g_t\),与数据集\(D\)有如下关系:

对于星号的部分,即是没有选择到的数据,称之为Out-of-bag(OOB)数据,当数据足够多,对于任意一组数据\((x_n, y_n)\)是OOB的概率为:

对于这些OOB数据,可以用来验证Random Forest最后的\(G(x)\):

当用于验证\(G(x)\),其Cost Function具有以下形式:对于Random Forest,通常使用上式评价其表现。

Feature Selection

对于一个\(N\)维向量\(x\),即\(x\)向量具有\(N\)个特征,但是并不是每一个维度的特征都和最终的\(G(x)\)是相关的。

这一点非常重要,特征提取是一个重要话题,当原始数据集\(D\)的维度非常大时,在使用某种机器学习算法前,特征提取是必要的,这样可以很大程度减少后续训练的时间与空间复杂度。

在Random Forest中,我们使用一种被称之为Permutation Test的方法来做Feature Selection,它具有以下形式:

其中,\(performance(D)\)是Random Forest在原始数据集\(D\)上的表现,而\(performance(D^{(p)})\)是将原始数据集\(D\)上的第\(x_i\)维度与\(x_j\)调换位置后得到的\(D^{(p)}\)上的表现,所以\(importance(i)\)即描述了\(x_i\)的重要程度,更进一步的,所谓\(performance(D)\)即\(E_{oob}(D)\):

上式也说明了我们使用OOB数据做Permutation Test。

Random Forest in Action

下图是21颗决策树组成的随机森林在二位数据上的表现:

以上是对Random Forest在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Gradient Boosted Decision Tree。

机器学习技法笔记 – Decision Tree(决策树)

Decision Tree Hypothesis

在上一章中,我们介绍了通过Re-weighted思想来差异化\(u^{(t)}_n\)(权重)训练出不同的\(g_t(x)\)然后做Aggregation的AdaBoost。

AdaBoost本质上是一种non-uniform的Bagging Aggregation方法。

在本章中,我们将介绍一种conditional的Bagging Aggregation方法,称之为Decision Tree(决策树)

首先,我们从下图在视觉上初步认识一下决策树:

上图是一个形象化的例子,通过树形图的方式描述了“要不要上课”这一条件决策流程。

其公式化的描述如下:

需要注意的是这是一种递归的描述,其中,\(G(x)\)是一颗生成树,是整颗决策树的入口,\(b(x)\)是判断是否要进入当前分支\(c\)的Branching Criteria Function,\(G_c(x)\)是子树的入口。

接下来,将介绍生成决策树的算法。

Decision Tree Algorithm

生成决策树具有很多著名的算法,在本文中我们介绍C&RT(Classification and Regression Tree),这个算法的主要思路如下:

即对于决策树函数,对于输入的数据集\(D\),如果递归至叶子节点,则输出叶子节点的\(g_t(x)\)对于数据集\(D\)中\((x_n, y_n)\)的值,否则,在当前数据集\(D\)上训练\(b(x)\),然后在将数据集\(D\)一分为二,递归调用决策树函数。

在C&RT中,如何训练\(b(x)\)是非常重要的话题。

其中,\(b(x)\)具有以下形式:

对于每一个\(b(x)\),最小化\(\sum^{2}_{c=1} \vert h(D_c) \vert · impurity(h(D_c))\),可以看出\(c=2\),即\(b(x)\)的输入是被分为两份的数据集\(D\),表现在数据结构上,即是二叉树,而\(impurity(h(D_c))\)是不纯度。

通常,对于回归问题,其\(impurity(h(D_c))\)通常有以下定义:

而对于分类问题,\(impurity(h(D_c))\)则有以下定义:

对于基础的Base Hypothesis,我们依然选择Decision Stump(决策桩),它具有以下形式:

通过最小化\(impurity(h(D_c))\),可以求出最佳的\(\theta\),接下来我们将给出完整的C&RT算法。

Decision Tree Heuristics in C&RT

一个完整的C&RT算法如下:

当\(impurity(h(D_c))=0\),或者\(D_c\)不可再分,则C&RT算法结束。

需要注意的是,C&RT算法生成的决策树如果没有任何的Regularization操作,放任子树生长,会使得\(E_{in}=0\),即会带来Overfitting,所以我们需要为C&RT算法加上Regularization项来避免Overfitting的发生,这个过程也称之为剪枝。

通常可以通过对叶子节点剪枝来做Regularization:

而Regularization项具有以下形式:

具体过程如下:

  • 首先通过C&RT生成决策树
  • 随机剪枝一个或多个叶子节点,重复多次,得到\(N\)个\(G(x)\)
  • 对所有\(G(x)\)在数据集\(D\)做Validation,选取\(E_{in}\)最小的\(G(x)\)

决策树不仅可以用在Numerical Features中,也可以用于Categorical Features:

对于数据集中不分数据的缺失,也可以通过训练多个\(b_n(x)\),来做最佳\(b(x)\)的近似。

Decision Tree in Action

下图是一个C&RT与AdaBoost算法的对比,通常情况下C&RT具有更高的效率:

最后对C&RT做一个总结:

C&RT具有诸多优点,例如对于人类易于解释,易于处理多分类问题,对于有缺失的数据集也可以应对,易于处理非线性分类或者预测问题。

以上是对Decision Tree在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Random Forest。