可扩展机器学习——概述

注：这是一份学习笔记，记录的是参考文献中的可扩展机器学习的一些内容，英文的PPT可见参考文献的链接。这个只是自己的学习笔记，对原来教程中的内容进行了梳理，有些图也是引用的原来的教程，若内容上有任何错误，希望与我联系，若内容有侵权，同样也希望告知，我会尽快删除。

可扩展机器学习系列主要包括以下几个部分：

• 概述
• Spark分布式处理
• 线性回归(linear Regression)
• 梯度下降(Gradient Descent)
• 分类——点击率预测(Click-through Rate Prediction)
• 神经科学

一、Overview

1、处理大规模数据集

对于不断扩大的数据规模主要有两种不同的处理方法：

• 向上扩展(Scale-up)：采用更大规模的机器，如下图所示

优点：对于中等规模的问题速度会很快

缺点：1、特定硬件的价格会比较贵；2、通过升级硬件的方法会达到一个上限。

• 向外扩展(Scale-out)：采用分布式的计算方法，如下图所示

优点：仅利用一些常用的硬件便能解决大规模问题

缺点：1、需要处理网络通信的问题；2、增加了一些软件的复杂度。

2、机器学习

2.1、机器学习的定义

机器学习是一种构建和学习的方法，从数据中学习并通过数据进行预测。

Constructing and studying methods that learn from and make predictions on data.

2.2、机器学习的应用

• 人脸识别(Face Recognition)
• 链路预测(Link Prediction)
• 文本分类(Text Classification)
• 蛋白质结构预测(Protein Structure Prediction)
• ……

2.3、机器学习中的术语

在机器学习中有一些专业的术语，常见的如下：

• 观测数据：主要是用于训练和测试机器学习算法的样本
• 特征：用于表征观测数据的一些属性
• 标签：给观测样本标记的数值或者类别
• 训练和测试数据：用于训练和评估算法的观测样本

2.4、机器学习算法的分类

在各种机器学习算法中，主要可以分为监督学习(Supervised Learning)和非监督学习(Unsupervised Learning)。

• 监督学习：从带有标签的观测样本学习。监督学习算法通过观测样本学习到从样本到标签之间的映射。根据label是离散的还是连续的，监督学习又可以分为：分类(Classification)和回归(Regression)。
• 非监督学习：从不带标签的观测样本学习。非监督学习主要是学习数据中隐藏的结构以及隐藏的模式。非监督学习又可以分为：聚类(Clustering)和降维(Dimensionality Reduction)。

2.5、典型的机器学习流程

2.5.1、监督学习的过程

在监督学习中，主要包括获取数据、特征提取、监督学习、评价和预测。过程可见下图：

学习的目的是为了学习到模型用于预测，而评价的目的是为了学习到较好的模型。对于一个具体的分类问题，如垃圾邮件的分类，欺诈检测，人脸识别，链路预测，点击率预估等等。

2.5.2、无监督学习的过程

对于无监督学习，无需通过样本标签训练模型，主要包括获取数据、特征提取和无监督学习过程，具体无监督学习过程如下所示：

2.5.3、垃圾邮件的分类问题

下面是垃圾邮件的分类问题。

• Obtain Raw Data：获取包括一组带标签的观测样本

• Feature Extraction：特征提取是指利用一组向量，向量是由实数组成，通常称为属性，去表示观测样本。

对于机器学习算法来说，成功与否通常取决于对观测样本的表示，即如何选择较好的特征表示。

如在垃圾邮件的分类任务中(文本分类)，可以使用Bag of Words。简单来讲，Bag of Words是将文本使用一串向量表示，每一个位置上表示的是字典(Vocabulary)中的每个词，若该词在文本中出现，则在该位置上标记为11，否则标记为00。

词袋模型中的向量长度取决于字典的大小。

具体的过程可由下图表示：

• Supervised Learning：在监督学习阶段是通过训练数据训练一个模型，主要的监督学习算法包括：Logistic回归(Logistic Regression, LR)，支持向量机(Support Vector Machine, SVM)，决策树(Decision Tree, DT)，随机森林(Random Forest, RF)等等。对于大规模的数据集，学习的过程通常需要迭代计算。
• Evaluation：评价一个分类器是否是一个好的分类器是指该分类器是否能够在未知的数据集上表现得较好，这便称为泛化能力(Generalization ability)。通常，我们将样本分为训练数据集(Training Data Set)和测试数据集(Testing Data Set)，训练数据集主要用于训练模型，测试数据集主要用于评价模型的好坏。

在这个过程中，要避免模型的过拟合(overfitting)，过拟合是指训练出来的模型较为复杂，能够在训练数据集上表现的很好，这种情况下极容易发生过拟合的情况，一般，我们希望模型要尽可能的简单，这样能够具有更好的泛化能力，复杂的模型与简单的模型如下图所示：

• Prediction：将训练好的模型应用于新的数据。

2.5.4、分类算法的流程

对于一个具体的分类问题，为了构建一个分类学习算法，首先需要对数据集进行分类，分为训练集合测试集，训练集用于训练分类算法模型，测试集用于测试训练好的分类学习算法的性能，对于训练好的分类算法，我们的最终目的是将该算法应用在具体的任务中，因此对于新的数据集的预测是构建分类算法的根本目的，对于分类算法的具体的流程可由下图表示：

3、度量时间和空间复杂度的大OO标记

3.1、大OO标记的概念

大OO标记表示的是算法对问题规模的响应，主要包括两个方面，即处理时间个空间需求，通常与复杂度是一个概念。

对于一个问题，假设有下式成立：

|f(x)|≤C|g(x)|

left | fleft ( x right ) right |leq Cleft | gleft ( x right ) right |

上式表示的意思是ff增长的速度没有gg快，利用大OO记法，可以表示为：

f(x)=O(g(x))

fleft ( x right )=Oleft ( gleft ( x right ) right )

3.2、集中常见的复杂度形式

3.2.1、O(1)Oleft ( 1 right )复杂度

O(1)Oleft ( 1 right )复杂度是指的是常数复杂度，对于时间，则为每次执行时，算法都执行了相同的数量的操作；对于空间，则为在每次执行的过程中，需要固定大小的存储空间。

3.2.2、O(n)Oleft ( n right )复杂度

O(n)Oleft ( n right )复杂度是指的是线性复杂度

3.2.3、O(n2)Oleft ( n^2 right )复杂度

O(n2)Oleft ( n^2 right )复杂度指的是平方复杂度

3.2.4、矩阵的计算时间和空间复杂度

对于nn维向量的内积，需要O(n)Oleft ( n right )的时间复杂度去计算nn对元素的相乘，需要O(1)Oleft ( 1 right )的空间复杂度存储最终的结果。

对于n×nntimes n矩阵的求逆，需要O(n3)Oleft ( n^3 right )的时间复杂度，需要O(n2)Oleft ( n^2 right )的空间复杂度存储最终的结果。

对于n×mntimes m矩阵和m×1mtimes 1维向量的乘积问题，需要O(nm)Oleft ( nm right )的时间复杂度和O(n)Oleft ( n right )的空间复杂度。

对于n×mntimes m矩阵和m×pmtimes p矩阵的乘积问题，需要O(npm)Oleft ( npm right )的时间复杂度和O(np)Oleft ( np right )的空间复杂度。

若需要PDF版本，请关注我的新浪博客@赵_志_勇，私信你的邮箱地址给我。

参考文献

scalable-machine-learning