第 2 章 机器学习的数学基础

第 2 章 机器学习的数学基础

机器学习用户需要对相关概念和算法有一定的理解。数学是机器学习的重要方面之一。我们通过熟悉编程语言的基本概念和结构来学习编程。类似地,我们需要借助数学来理解机器学习的相关概念和算法,从而解决复杂的计算问题,以及理解众多计算机科学概念。对于掌握理论概念和选择正确的算法,数学起着根本性作用。本章会介绍机器学习相关的线性代数微积分的基础知识。

本章覆盖的内容如下:

  • 线性代数
  • 环境配置
    • 配置IntelliJ Scala环境
    • 配置命令行Scala环境
  • 向量
    • 向量空间
    • 向量类型
      • 密集向量
      • 稀疏向量
      • Spark中的向量
    • 向量操作
    • 超平面
    • 机器学习中的向量
  • 矩阵
    • 简介
    • 矩阵类型
      • 密集矩阵
      • CSC矩阵(列压缩矩阵)
      • Spark中的矩阵
    • 矩阵操作
    • 行列式
    • 特征值和特征向量
    • 奇异值分解
    • 机器学习中的矩阵
  • 函数
    • 定义
    • 函数类型
      • 线性函数
      • 多项式函数
      • 恒等函数
      • 常数函数
      • 概率分布函数
      • 高斯函数
    • 函数组合
    • 假设
    • 梯度下降
    • 先验概率、似然和后验概率
  • 微积分
    • 可微微分
    • 积分
    • 拉格朗日乘子
  • 可视化

2.1 线性代数

线性代数研究对由线性方程和变换组成的系统求解。其基本工具为向量、矩阵和行列式。下面会借助Breeze来分别学习它们。Breeze是一个用于数值计算的线性代数库。相应的Spark对象实际是对Breeze的封装,并以公开接口方式供调用。这使得即便Breeze内部有更改,仍然能保证Spark ML 库的一致性。

2.1.1 配置IntelliJ Scala环境

编写Scala代码时,最好能借助如IntelliJ这样的IDE,它们提供了更快的开发工具和代码协助。代码自动完成和检查能加快和简化编码和调试过程,从而让你专注在学习机器学习相关的数学这一最终目标上。

IntelliJ 2016.3以Scala插件的形式对Akka、Scala.meta、内存检视、Scala.js和Migrators提供了支持。让我们按如下步骤来配置IntelliJ Scala的开发环境。

(1) 点选 Preferences | Plugins,确认Scala插件已安装。SBT是一种Scala构建工具,采用默认配置,如下图所示。

(2) 点选File | New | Project from Existing resources | $GIT_REPO/Chapter_02/breeze or $GIT_REPO/Chapter_02/spark。其中,$GIT_REPO是读者克隆本书代码的代码库路径。

(3) 选择SBT来导入项目,如下图所示。

(4) 保留SBT默认配置,并点击Finish。

(5) 等待SBT从build.sbt导入相关引用,如下图所示。

(6) 最后,点击鼠标右键选择源文件,然后点击Run ‘Vector’,如下图所示。

2.1.2 配置命令行Scala环境

可通过如下步骤来配置一个本地开发环境。

(1) 进入Chapter 2的根目录,然后选择相应的文件夹。

$ cd /PATH/spark-ml/Chapter_02/breeze

另外,也可选择:

$ cd /PATH/spark-ml/Chapter_02/spark

(2) 编译代码:

$ sbt compile

(3) 运行编译后的代码,并选择相应的程序来运行(根据sbt run是在breeze还是spark目录下执行,输出的类名会不同)。

$ sbt run

Multiple main classes detected, select one to run:
...

Enter number:

2.1.3 域

域是数学中以不同形式定义的基本结构。下面会介绍一些常见的基本类型。

  1. 实数

    实数包含我们所能想到的任意数字。它包括整数(0、1、2、3)、有理数(2/6、0.768、0.222...、3.4)和无理数(π、3的平方根)。实数可以是正数、负数或0。虚数则是另一种数,比如-1的平方根。注意,极数(无穷大或无穷小)不是实数。

  2. 复数

    我们通常的理解是,一个数的平方不可能为负数。那如何求解x^2=-9 ?不难想到数学中有 i 这个概念能够求解,即x=3{\rm i}。诸如 i、-i、3i和2.27i这样的数称为虚数。一个实数加一个虚数构成了一个复数。

    复数 = 实数部 + 虚数部 i

    下面的例子展示了如何使用Breeze进行复数的数学表示:

    import breeze.linalg.DenseVector
    import breeze.math.Complex
    val i = Complex.i
    // 加法
    println((1 + 2 * i) + (2 + 3 * i))
    // 减法
    println((1 + 2 * i) - (2 + 3 * i))
    // 除法
    println((5 + 10 * i) / (3 - 4 * i))
    // 乘法
    println((1 + 2 * i) * (-3 + 6 * i))
    println((1 + 5 * i) * (-3 + 2 * i))
    // 取反
    println(-(1 + 2 * i))
    // 多项加法
    val x = List((5 + 7 * i), (1 + 3 * i), (13 + 17 * i))
    println(x.sum)
    // 多项乘法
    val x1 = List((5 + 7 * i), (1 + 3 * i), (13 + 17 * i))
    println(x1.product)
    // 多项排序
    val x2 = List((5 + 7 * i), (1 + 3 * i), (13 + 17 * i))
    println(x2.sorted)

    对应的结果如下:

    3.0 + 5.0i
    -1.0 + -1.0i
    -1.0 + 2.0i
    -15.0 + 0.0i
    -13.0 + -13.0i
    -1.0 + -2.0i
    19.0 + 27.0i
    -582.0 + 14.0i
    List(1.0 + 3.0i, 5.0 + 7.0i, 13.0 + 17.0i)
  3. 向量

    向量是一组有序数字的数学表示。它与集合类似,但是各数是有序的。其中的数均为实数。n维向量在几何上表示为n维空间中的一个点。向量的起点(原点)从零开始。

    比如:

    [2, 4, 5, 9, 10]
    [3.14159, 2.718281828, -1.0, 2.0]
    [1.0, 1.1, 2.0]
  4. 向量空间

    线性代数是向量空间的代数表示。实数域或复数域中的各向量可相加,或通过与标量\alpha相乘而成倍变化。

    向量空间是若干可相加和相乘的向量构成的集合。在向量空间中,两个向量可结合生成第三个向量或其他对象。向量空间的公理具有诸多有用的性质。向量空间中的空间定义有助于物理空间属性的学习,比如,确认一个物体的远近。三维欧几里得(Euclidean)空间中的向量集合便是向量空间的一个例子。向量空间V在域F上具有如下性质。

    • 向量加法:表示为\boldsymbol{v}+\boldsymbol{w},其中\boldsymbol{v}\boldsymbol{w}是空间V中的元素。
    • 标量乘法:表示为\alpha~^*~\boldsymbol{v},其中\alphaF中的元素。
    • 结合律:表示为\boldsymbol{u}+(\boldsymbol{v}+\boldsymbol{w})=(\boldsymbol{u}+\boldsymbol{v})+\boldsymbol{w},其中\boldsymbol{u}\boldsymbol{v}\boldsymbol{w}均为空间V中的元素。
    • 交换律:表示为\boldsymbol{v}+\boldsymbol{w}=\boldsymbol{w}+\boldsymbol{v}
    • 分配律:表示为\alpha~^*~(\boldsymbol{v}+\boldsymbol{w})=\alpha~^*~\boldsymbol{v}+\alpha~^*~\boldsymbol{w}

    在机器学习中,特征对应向量空间的维度。

  5. 向量类型

    在Scala编程中,我们使用Breeze库来表示向量。向量可表示为密集向量和稀疏向量。

  6. Breeze中的向量

    Breeze使用两种基本的向量类型来表示上述两种向量,即breeze.linalg.DenseVectorbreeze.linalg.SparseVector

    DenseVector是对支持数值运算的数组的一种封装。下面先看下密集向量的计算。首先借助Breeze创建一个密集向量对象,然后更新索引为3的元素的值。

    import breeze.linalg.DenseVector
    
    val v = DenseVector(2f, 0f, 3f, 2f, -1f)
    v.update(3, 6f)
    println(v)

    其结果为:DenseVector(2.0, 0.0, 3.0, 6.0, -1.0)

    SparseVector表示多数元素为0且支持数值运算的向量,即稀疏向量。下面的代码先借助Breeze创建了一个稀疏向量,然后对其中的各值加1:

    import breeze.linalg.SparseVectorval
    sv:SparseVector[Double] = SparseVector(5)()
    sv(0) = 1
    sv(2) = 3
    sv(4) = 5
    val m:SparseVector[Double] = sv.mapActivePairs((i,x) => x+1)
    println(m)

    其结果为:SparseVector((0,2.0), (2,4.0), (4,6.0))

  7. Spark中的向量

    Spark MLlib使用Breeze和jblas来处理底层线性代数运算。它自定义了org.apache.spark.mllib.linalg.Vector经工厂模式来创建和表示向量。本地向量的索引为从0开始递增的整数。其中各值以双精度表示。本地向量存储在单个节点中,且不能分发到其他节点。Spark MLlib支持密集型和稀疏型两种本地向量,它们通过工厂模式创建。

    如下代码片段展现了如何在Spark中创建上述两种向量:

    val dVectorOne: Vector = Vectors.dense(1.0, 0.0, 2.0)
    println("dVectorOne:" + dVectorOne)
    // 稀疏向量(1.0, 0.0, 2.0, 3.0)对应非零条目
    val sVectorOne: Vector = Vectors.sparse(4, Array(0, 2,3),
      Array(1.0, 2.0, 3.0))
    // 创建一个稀疏向量(1.0, 0.0, 2.0, 2.0) 并指定其非零条目
    val sVectorTwo: Vector = Vectors.sparse(4, Seq((0, 1.0), (2, 2.0), (3, 3.0)))

    对应的结果如下:

    dVectorOne:[1.0,0.0,2.0]
    sVectorOne:(4,[0,2,3],[1.0,2.0,3.0])
    sVectorTwo:(4,[0,2,3],[1.0,2.0,3.0])

    Spark提供了多种方式来访问和查看向量数值,比如:

    val sVectorOneMax = sVectorOne.argmax
    val sVectorOneNumNonZeros = sVectorOne.numNonzeros
    val sVectorOneSize = sVectorOne.size
    val sVectorOneArray = sVectorOne.toArray
    val sVectorOneJson = sVectorOne.toJson
    println("sVectorOneMax:" + sVectorOneMax)
    println("sVectorOneNumNonZeros:" + sVectorOneNumNonZeros)
    println("sVectorOneSize:" + sVectorOneSize)
    println("sVectorOneArray:" + sVectorOneArray)
    println("sVectorOneJson:" + sVectorOneJson)
    val dVectorOneToSparse = dVectorOne.toSparse

    其输出如下:

    sVectorOneMax:3
    sVectorOneNumNonZeros:3
    sVectorOneSize:4
    sVectorOneArray:[D@38684d54
    sVectorOneJson:{"type":0,"size":4,"indices":[0,2,3],"values": [1.0,2.0,3.0]}
    dVectorOneToSparse:(3,[0,2],[1.0,2.0])
  8. 向量操作

    向量可两两相加、相减或与标量相乘。其他操作包括求平均值、正则化、比较和几何表示。

    • 加法:下面的代码展示了两个向量进行逐元素相加。

      // 向量元素相加
      val v1 = DenseVector(3, 7, 8.1, 4, 5)
      val v2 = DenseVector(1, 9, 3, 2.3, 8)
      def add(): Unit = {
        println(v1 + v2)
      }

      该代码的结果为:DenseVector(4.0, 16.0, 11.1, 6.3, 13.0)

    • 乘法和点乘:这种代数运算以等长度的两个数组为输入,输出一个数值。代数上,它是两个数组的乘积之和。其数学表示如下。

      \boldsymbol{a}~\cdot~\boldsymbol{b}=|\boldsymbol{a}|\times|\boldsymbol{b}|\times\cos(\theta)\boldsymbol{a}~\cdot~\boldsymbol{b}=ax\times bx+ay\times by

      import breeze.linalg.{DenseVector, SparseVector}
      val a = DenseVector(0.56390, 0.36231, 0.14601, 0.60294, 0.14535)
      val b = DenseVector(0.15951, 0.83671, 0.56002, 0.57797, 0.54450)
      println(a.t * b)
      println(a dot b)

      对应的结果为:

      0.9024889161, 0.9024889161

      又如:

      import breeze.linalg.{DenseVector, SparseVector}
      val sva = SparseVector(0.56390,0.36231,0.14601,0.60294,0.14535)
      val svb = SparseVector(0.15951,0.83671,0.56002,0.57797,0.54450)
      println(sva.t * svb)
      println(sva dot svb)

      对应的结果为:

      0.9024889161, 0.9024889161
    • 求平均值:该操作返回第一个元素个数不为1的维度对应的各个元素的平均值。其数学表示为:

      import breeze.linalg.{DenseVector, SparseVector}
      import breeze.stats.mean
      val mean = mean(DenseVector(0.0,1.0,2.0))
      println(mean)

      对应的输出为:

      1.0

      又如:

      import breeze.linalg.{DenseVector, SparseVector}
      import breeze.stats.mean
      val svm = mean(SparseVector(0.0,1.0,2.0))
      val svm1 = mean(SparseVector(0.0,3.0))
      println(svm, svm1)

      对应的输出为:

      (1.0,1.5)
    • 正则化:每个向量都有大小,它通过毕达哥拉斯定理定义为|\boldsymbol{v}|={\rm sqrt}(x^2+y^2+z^2)。该大小是从原点到向量对应点的距离。正则向量的大小为1。向量正则化表示对向量进行改变,以使得其长度为1,但保持其从原点出发所指向的方向不变。因而,正则向量是方向与原向量相同,但范数(norm,即长度)为1的向量。它表示为\boldsymbol{\hat X}并定义如下:

      \boldsymbol{\hat X}=\frac{\boldsymbol{X}}{|\boldsymbol{X}|}

      其中,|\boldsymbol{X}|表示\boldsymbol{X}的范数。该向量也称为单位向量。

      import breeze.linalg.{norm, DenseVector, SparseVector}
      import breeze.stats.mean
      val v = DenseVector(-0.4326, -1.6656, 0.1253, 0.2877, -1.1465)
      val nm = norm(v, 1)
      
      // 正则化向量,使其范数为1.0
      val nmlize = normalize(v)
      
      // 最后检查下正则向量的范数是否为1.0
      println(norm(nmlize))

      对应的输出如下:

      Norm(of dense vector) = 3.6577
      
      Normalized vector is = DenseVector(-0.2068389122442966,
        -0.7963728438143791, 0.05990965257561341, 0.1375579173663526,
        -0.5481757117154094)
      
      Norm(of normalized vector) = 0.9999999999999999
    • 输出向量中的最大和最小元素:

      import breeze.linalg._
      val v1 = DenseVector(2, 0, 3, 2, -1)
      println(argmin(v1))
      println(argmax(v1))
      println(min(v1))
      println(max(v1))

      对应的结果为:

      4, 2, -1, 3
    • 比较:比较两个向量的大小。

      import breeze.linalg._
      val a1 = DenseVector(1, 2, 3)
      val b1 = DenseVector(1, 4, 1)
      println((a1 :== b1))
      println((a1 :<= b1))
      println((a1 :>= b1))
      println((a1 :< b1))
      println((a1 :> b1))

      对应的结果为:1

      BitVector(0)
      BitVector(0, 1)
      BitVector(0, 2)
      BitVector(1)
      BitVector(2)
    • 向量的几何表示(见下图)。

  9. 超平面

    n大于3时,实数向量难以可视化。可以用常见的概念,如线和面,来(组合)表示任意n维空间。从向量\boldsymbol{v}开始,经过向量\boldsymbol{u}代表的点P所对应的线条L可表示为:

    L={\boldsymbol{u}+t\boldsymbol{v}~|~t\in R\}

    已知两个非零向量\boldsymbol{u}\boldsymbol{v},若它们不在一条线上,且其中一个向量不为另一向量的标量倍数,则它们确定一个平面。两个向量的加法通过将向量某一端首尾相连构成的三角形来实现。如果\boldsymbol{u}\boldsymbol{v}在一个平面内,则其和也在同一平面内。由两个向量\boldsymbol{u}\boldsymbol{v}表示的平面可定义为:

    {P+s\boldsymbol{u}+t\boldsymbol{v}~|~s,~t\in R\}

    进而,一个n维平面可由一个由向量\boldsymbol{x}_i构成的集合XP表示,其中i\leqslant n

    (P+X,X=\sum^n_1\lambda_i\boldsymbol{v}_i~|~\lambda_i\in R)

  10. 机器学习中的向量

    在机器学习中,特征用n维向量表示。在机器学习中,数据对象需要以数值形式表示,以便进行处理和统计分析,比如用像素向量来表示图像。

1其结果为符合比较条件的各对应元素的索引。——译者注

2.1.4 矩阵

F域中的矩阵是指由F域中的元素构成的二维数组。比如实数域中的一个矩阵可为:

\begin{matrix}~1&~2&~3\\10&20&30\end{matrix}

上述矩阵有2行3列,被称为2×3矩阵。人们通常用数字来指代行和列。行1是(1 2 3),行2是(10 20 30);列1是(1 10),列2是(2 20),列3是(3 30)。通常,一个mn列的矩阵称为m\times n矩阵。对于给定矩阵\boldsymbol{A},其元素(i,j)定义为第i行第j列的元素,并通过\boldsymbol{A}_{i,j}\boldsymbol{A}_{ij}来表示。后续内容将会经常采用Python风格,即\boldsymbol{A}[i,j]。行i是向量(\boldsymbol{A}[i,0],\boldsymbol{A}[i,1],\boldsymbol{A}[i,2],\cdots,\boldsymbol{A}[i,m-1]),列j则是向量(\boldsymbol{A}[0,j],\boldsymbol{A}[1,j],\boldsymbol{A}[2,j],\cdots,\boldsymbol{A}[n-1,j])

  1. 矩阵类型

    后续Scala代码将使用Breeze库来表示矩阵。矩阵可表示为密集矩阵或CSC(列压缩稀疏)矩阵。

    • 密集矩阵:密集矩阵通过调用构造函数来创建。其元素可被访问或更新。其以列优先(column major)模式存储,且能转为行优先模式。

      val a = DenseMatrix((1,2),(3,4))
      println("a : n" + a)
      val m = DenseMatrix.zeros[Int](5,5)
      
      // 各列可以Dense Vector方式访问,而行则可作为Dense Matrix来访问
      
      println( "m.rows :" + m.rows + " m.cols : " + m.cols)
      m(::,1)
      println("m : n" + m)
    • 矩阵转置:矩阵转置(transposition)是指将矩阵的行和列进行调换。对于一个P\times Q矩阵,其转置\boldsymbol{MT}是一个Q\times P矩阵,其中\boldsymbol{MT}_{i,j}=\boldsymbol{M}_{j,i},对于任意i\in P,j\in Q。向量的转置则生成一个行矩阵。

      m(4,::) := DenseVector(5,5,5,5,5).t
      println(m)

      上述代码的输出为:

      a :
      1 2
      3 4
      Created a 5x5 matrix
      0  0  0  0  0
      0  0  0  0  0
      0  0  0  0  0
      0  0  0  0  0
      0  0  0  0  0
      m.rows :5 m.cols : 5
      First Column of m :
        DenseVector(0, 0, 0, 0, 0)
        Assigned 5,5,5,5,5 to last row of m.
      
      0  0  0  0  0
      0  0  0  0  0
      0  0  0  0  0
      0  0  0  0  0
      5  5  5  5  5
    • CSC矩阵即列压缩稀疏(compressed sparse columns)矩阵。其每一列对应一个稀疏向量。CSC矩阵支持所有矩阵运算,并通过Builder来创建。

      val builder = new CSCMatrix.Builder[Double](rows=10, cols=10)
      builder.add(3,4, 1.0)
      // 等等
      val myMatrix = builder.result()
  2. Spark中的矩阵

    Spark中的本地矩阵的行列索引为整数,而元素值为双精度(double)型。所有值均存储在单个节点上。MLlib支持如下矩阵类型。

    • 密集矩阵:其各元素以列优先顺序存储在单个双精度数组中。
    • 稀疏矩阵:其各非零元素以列优先顺序存储为CSC格式。比如,如下大小为(3, 2)的密集矩阵存储在一维数组[2.0, 3.0, 4.0, 1.0, 4.0, 5.0]中:

      2.0 3.0
      4.0 1.0
      4.0 5.0

    以下例子说明了这两种矩阵的创建:

    val dMatrix: Matrix = Matrices.dense(2, 2, Array(1.0, 2.0, 3.0, 4.0))
    println("dMatrix: \n" + dMatrix)
    
    val sMatrixOne: Matrix = Matrices.sparse(3, 2, Array(0, 1, 3),
      Array(0, 2, 1), Array(5, 6, 7))
    println("sMatrixOne: \n" + sMatrixOne)
    
    val sMatrixTwo: Matrix = Matrices.sparse(3, 2, Array(0, 1, 3),
      Array(0, 1, 2), Array(5, 6, 7))
    println("sMatrixTwo: \n" + sMatrixTwo)

    其输出如下:

    [info] Running linalg.matrix.SparkMatrix
    dMatrix:
    1.0  3.0
    2.0  4.0
    sMatrixOne:
    3 x 2 CSCMatrix
    (0,0) 5.0
    (2,1) 6.0
    (1,1) 7.0
    sMatrixTwo:
    3 x 2 CSCMatrix
    (0,0) 5.0
    (1,1) 6.0
    (2,1) 7.0
  3. Spark中的分布式矩阵

    分布式矩阵的行列索引为长整数(long)型,元素值为双精度型,且分布式地存储在一个或多个RDD上。Spark中包含了四类分布式矩阵,它们均为DistributedMatrix的子类,如下图所示。

    • RowMatrix:该类矩阵是以行优先模式存储的分布式矩阵,但没有有意义的行索引。(在行优先的矩阵里,每一行的相邻元素在内存中也是相邻存储的。)RowMatrix实现为其各行的一个RDD。每一行是一个本地向量。其列的数目必须小于等于2^{31} ,以便单个本地向量可同驱动程序通信,也使其能在单个节点上保存或进行操作。

      如下代码演示了如何从Vector类创建一个行矩阵(密集型和稀疏型):

      val spConfig = (new SparkConf).setMaster("local")
        .setAppName("SparkApp")
      val sc = new SparkContext(spConfig)
      val denseData = Seq(
          Vectors.dense(0.0, 1.0, 2.1),
          Vectors.dense(3.0, 2.0, 4.0),
          Vectors.dense(5.0, 7.0, 8.0),
          Vectors.dense(9.0, 0.0, 1.1)
        )
      val sparseData = Seq(
          Vectors.sparse(3, Seq((1, 1.0), (2, 2.1))),
          Vectors.sparse(3, Seq((0, 3.0), (1, 2.0), (2, 4.0))),
          Vectors.sparse(3, Seq((0, 5.0), (1, 7.0), (2, 8.0))),
          Vectors.sparse(3, Seq((0, 9.0), (2, 1.0)))
        )
      val denseMat = new RowMatrix(sc.parallelize(denseData, 2))
      val sparseMat = new RowMatrix(sc.parallelize(sparseData, 2))
      
      println("Dense Matrix - Num of Rows :" + denseMat.numRows())
      println("Dense Matrix - Num of Cols:" + denseMat.numCols())
      println("Sparse Matrix - Num of Rows :" + sparseMat.numRows())
      println("Sparse Matrix - Num of Cols:" + sparseMat.numCols())
      sc.stop()

      其输出如下:

      Using Spark's default log4j profile: org/apache/spark/log4j defaults.properties
      16/01/27 04:51:59 INFO SparkContext: Running Spark version 1.6.0
      Dense Matrix - Num of Rows :4
      Dense Matrix - Num of Cols:3
      ...
      Sparse Matrix - Num of Rows :4
      Sparse Matrix - Num of Cols :3
    • IndexedRowMatrix:与RowMatrix类似,但以行而非列为索引。该索引可用于检索行以及执行连接(join)操作。如下代码演示了创建一个带相应行索引的4×3的IndexedMatrix方法。

      val data = Seq(
        (0L, Vectors.dense(0.0, 1.0, 2.0)),
        (1L, Vectors.dense(3.0, 4.0, 5.0)),
        (3L, Vectors.dense(9.0, 0.0, 1.0))
        ).map(x => IndexedRow(x._1, x._2))
      val indexedRows: RDD[IndexedRow] = sc.parallelize(data, 2)
      val indexedRowsMat = new IndexedRowMatrix(indexedRows)
      println("Indexed Row Matrix - No of Rows: " + indexedRowsMat.numRows())
      println("Indexed Row Matrix - No of Cols: " + indexedRowsMat.numCols()

      上述代码的输出如下:

      Indexed Row Matrix - No of Rows: 4
      Indexed Row Matrix - No of Cols: 3
    • CoordinateMatrix:该类矩阵以坐标表(COO,coordinated list)格式将各元素分布式地存储在一个RDD中。

      COO保存了一个(row, column, value)三元组的列表。各元素依次按行索引和列索引排序过,以提升随机访问性能。当需要增量式增删来构建一个矩阵时,这种格式很有优势。

      val entries = sc.parallelize(Seq(
            (0, 0, 1.0),
            (0, 1, 2.0),
            (1, 1, 3.0),
            (1, 2, 4.0),
            (2, 2, 5.0),
            (2, 3, 6.0),
            (3, 0, 7.0),
            (3, 3, 8.0),
            (4, 1, 9.0)), 3).map { case (i, j, value) =>
            MatrixEntry(i, j, value)
          }
      val coordinateMat = new CoordinateMatrix(entries)
      println("Coordinate Matrix - No of Rows: " + coordinateMat.numRows())
      println("Coordinate Matrix - No of Cols: " + coordinateMat.numCols())

      其输出如下:

      Coordinate Matrix - No of Rows: 5
      Coordinate - No of Cols: 4
  4. 矩阵操作

    矩阵支持的操作有多种。

    • 按元素加法。已知两个矩阵\boldsymbol{a}\boldsymbol{b},将它们相加,(\boldsymbol{a}+\boldsymbol{b}),意味着将两个矩阵相同位置好的元素相加。

      在Breeze中代码为:

      val a = DenseMatrix((1,2),(3,4))
      val b = DenseMatrix((2,2),(2,2))
      val c = a + b
      println("a: \n" + a)
      println("b: \n" + b)
      println("a + b : \n" + c)

      其输出为:

      a:
      1  2
      3  4
      b:
      2  2
      2  2
      a + b :
      3  4
      5  6
    • 按元素乘法。即将两个矩阵各相同位置上的元素相乘。

      在Breeze中代码为:

      a :* b
      val d = a*b
      println("Dot product a*b : \n" + d)

      其输出为:

      Dot product a*b :
      6   6
      14  14
    • 按元素比较。比较两个矩阵相同位置上的元素。

      在Breeze中代码为:

      val d = a :< b
          println("a :< b \n" + d)

      其输出为:

      a :< b
      false  false
      false  false
    • 原位加法。这意味着给矩阵的各个元素增加某个数值(比如1)。

      在Breeze中代码为:

      val e = a :+= 1
      println("Inplace Addition : a :+= 1 \n" + e)

      其输出为:

      Inplace Addition : a :+= 1
      2  3
      4  5
    • 求元素和。这意味着将矩阵的各个元素相加。

      在Breeze中代码为:

      val sumA = sum(a)
      println("sum(a): \n" + sumA)

      其输出为:

      sum(a):
      14
    • 求元素最大值。寻找矩阵中值最大的元素:

      在Breeze中代码为:

      a.max
      println("a.max: \n" + a.max)

      其输出为:

      a.max:
      5
    • 寻找上述最大值元素的位置。

      在Breeze中代码为:

      println("argmax(a):\n" + argmax(a))

      其输出为:

      argmax(a):
      (1,1)
    • 向上取整(ceiling)。找寻比元素大的最小整数。

      在Breeze中代码为:

      val g = DenseMatrix((1.1, 1.2), (3.9, 3.5))
      println("g: \n" + g)
      val gCeil = ceil(g)
      println("ceil(g) \n " + gCeil)

      其输出为:

      g:
          1.1  1.2
          3.9  3.5
      
      ceil(g)
          2.0  2.0
          4.0  4.0
    • 向下取整(floor)。找寻比元素小的最大整数。

      在Breeze中代码为:

      val gFloor =floor(g)
      
      println("floor(g) \n" + gFloor)

      其输出为:

      floor(g)
      1.0  1.0
      3.0  3.0
  5. 行列式

    {\rm tr}(\boldsymbol{M})表示矩阵\boldsymbol{M}的迹(trace)。它是主对角线上各元素的和。迹通常用来衡量矩阵的大小。行列式{\rm det}(\boldsymbol{M})则为对角线上各元素的乘积,如下所示。

    {\rm det}\begin{bmatrix}a&b\\c&d\end{bmatrix}=ad-bc

    行列式主要用于线性方程系统中;它能表示各列是否线性相关,并有助于找出矩阵的逆(inverse)。对于大矩阵而言,其行列式由拉普拉斯展开式(Laplace expansion)求出。

    val detm: Matrix = Matrices.dense(3, 3, Array(1.0, 3.0, 5.0, 2.0, 4.0, 6.0, 2.0, 4.0, 5.0))
    print(det(detm))
  6. 特征值和特征向量

    \boldsymbol{Ax}=b是源于静态问题的一个线性方程。特征值(eigenvalue)则用于求解动态问题。假设\boldsymbol{A}是一个矩阵且\boldsymbol{x}为一个向量,下面考虑如何求解线性代数中的新方程,\boldsymbol{Ax}=\lambda\boldsymbol{x}

    \boldsymbol{A}乘以\boldsymbol{x}时,向量\boldsymbol{x}改变了它的方向。但存在若干与\boldsymbol{Ax}同方向的向量,即特征向量(eigenvector),它们满足如下等式:

    \boldsymbol{Ax}=\lambda\boldsymbol{x}

    在上述等式中,向量\boldsymbol{Ax}等于\lambda乘以向量\boldsymbol{x}\lambda被称为特征值。特征值\lambda表明向量的方向是反转还是保持不变。

    \boldsymbol{Ax}=\lambda\boldsymbol{x}还表明{\rm det}(\boldsymbol{A}-\lambda\boldsymbol{I})=0,其中\boldsymbol{I}为单位矩阵(identity matrix)。这确定了特征值的个数n

    特征值问题定义如下:

    \begin{aligned}&\boldsymbol{Ax}=\lambda\boldsymbol{x}\\&\boldsymbol{Ax}-\lambda\boldsymbol{x}=0\\&\boldsymbol{Ax}=\lambda\boldsymbol{Ix}=0\\&(\boldsymbol{A}-\lambda\boldsymbol{I})\boldsymbol{x}=0\end{aligned}

    如果\boldsymbol{x}非零,上述方程仅当|\boldsymbol{A}-\lambda\boldsymbol{I}|=0时有一个解。通过该方程,我们可找到各特征值:

    val A = DenseMatrix((9.0,0.0,0.0),(0.0,82.0,0.0),(0.0,0.0,25.0))
    val es = eigSym(A)
    val lambda = es.eigenvalues
    val evs = es.eigenvectors
    println("lambda is : " + lambda)
    println("evs is : " + evs)

    上述代码的结果如下:

    lambda is : DenseVector(9.0, 25.0, 82.0)
    evs is : 1.0 0.0 0.0
    0.0  0.0  1.0
    0.0  1.0  -0.0
  7. 奇异值分解

    矩阵\boldsymbol{M}的奇异值分解(SVD,singular value decomposition)定义为:m\times n(实数或复数)是形如\boldsymbol{U}Σ \boldsymbol{V}^*的因式分解,其中\boldsymbol{U}为一个m\times R矩阵,Σ 是一个R\times R的矩形对角矩阵(rectangular diagonal matrix)且对角线上无负实数,\boldsymbol{V}是一个n\times r酉矩阵(unitary matrix),r等于矩阵\boldsymbol{M}的秩。

    Σ 的各对角元素 Σi,i 被称为\boldsymbol{M}的奇异值。\boldsymbol{U}\boldsymbol{V}的列则分别称为\boldsymbol{M}的左奇异向量和右奇异向量。

    如下是Apache Spark中SVD的一个例子:

    package linalg.svd
    
    import org.apache.spark.{SparkConf, SparkContext}
    import org.apache.spark.mllib.linalg.distributed.RowMatrix
    import org.apache.spark.mllib.linalg.{
      Matrix, SingularValueDecomposition, Vector, Vectors
    }
    
    object SparkSVDExampleOne {
      def main(args: Array[String]) {
        val denseData = Seq(
          Vectors.dense(0.0, 1.0, 2.0, 1.0, 5.0, 3.3, 2.1),
          Vectors.dense(3.0, 4.0, 5.0, 3.1, 4.5, 5.1, 3.3),
          Vectors.dense(6.0, 7.0, 8.0, 2.1, 6.0, 6.7, 6.8),
          Vectors.dense(9.0, 0.0, 1.0, 3.4, 4.3, 1.0, 1.0)
        )
        val spConfig = (new SparkConf).setMaster("local").setAppName("SparkSVDDemo")
        val sc = new SparkContext(spConfig)
        val mat: RowMatrix = new RowMatrix(sc.parallelize(denseData, 2))
        // 计算前20个奇异值和对应的奇异向量
        val svd: SingularValueDecomposition[RowMatrix, Matrix] =
          mat.computeSVD(7, computeU = true)
        val U: RowMatrix = svd.U // U因子为一个RowMatrix
        val s: Vector = svd.s // 各奇异值保存在一个本地密集向量中
        val V: Matrix = svd.V // V因子为一个本地密集矩阵
        println("U: \n" + U)
        println("s: \n" + s)
        println("V: \n" + V)
        sc.stop()
      }
    }
  8. 机器学习中的矩阵

    在实际的机器学习任务中,如人脸或文字识别、医学成像、主成分分析和数值精度等,矩阵作为数学对象来表示图像和数据集。

    这里以特征分解为例。通过分解为构成部件或找寻其一般属性,能更好地理解许多数学对象。

    如同整数可分解为质因数,矩阵分解称为特征分解。后者将一个矩阵分解为若干特征向量和特征值。

    矩阵\boldsymbol{A}的特征向量\boldsymbol{v}满足与\boldsymbol{A}的乘仅仅改变\boldsymbol{v}的倍数,即:

    \boldsymbol{Av}=\lambda\boldsymbol{v}

    标量\lambda被称为该特征向量的特征值。\boldsymbol{A}的特征分解表示为:

    \boldsymbol{A}=\boldsymbol{V}{\rm diag}(\lambda)\boldsymbol{V}-1

    矩阵的特征分解和与矩阵本身的许多特质对应。当且仅当某个矩阵的任意特征值都为0时,该矩阵是奇异的。实数对称矩阵的特征分解可用于二次表达式的优化和其他问题。特征向量和特征值也用于主成分分析中。

    如下例子展示了如何使用一个DenseMatrix来求特征值和特征向量:

    // 数据
    val msData = DenseMatrix(
         (2.5,2.4), (0.5,0.7), (2.2,2.9), (1.9,2.2), (3.1,3.0),
         (2.3,2.7), (2.0,1.6), (1.0,1.1), (1.5,1.6), (1.1,0.9))
    def main(args: Array[String]): Unit = {
        val pca = breeze.linalg.princomp(msData)
        print("Center" , msData(*,::) - pca.center)
        // 数据的协方差矩阵
        print("covariance matrix", pca.covmat)
        // 该协方差矩阵排好序的特征值
        print("eigen values",pca.eigenvalues)
        // 特征向量
        print("eigen vectors",pca.loadings)
          print(pca.scores)
    }

    其结果如下:

    eigen values = DenseVector(1.2840277121727839, 0.04908339893832732)
    eigen vectors = -0.6778733985280118  -0.735178655544408

2.1.5 函数

要定义一个如函数这样的数学对象,需要先明白什么是集合(set)。

集合是若干无序对象的集,比如S={-4,4,-3,3,-2,2,-1,1,0\}。如果集合S并非无限,则用|S|来表示其元素的个数,即集合的势(cardinality)。如果AB都是有限集合,则有|A\to B|=|A|\to|B|,即笛卡儿积(Cartesian product)。

对于A中的每一个输入元素,一个函数会将其对应到另一集合B中的某一个输出元素。A称为函数的定义域(domain),B则称为值域(codomain)。函数是若干(x,y)对的集合,其中x各不相同。

比如,定义域为{1,2,3,\cdots\}的函数,其两倍输入操作对应的集合为{(1,2),(2,4),(3,6),\cdots\}

又如,输入变量数为2且定义域均为{1,2,3,\cdots\}的函数,其对应的集合为{((1,1),1),((1,2),2),\cdots,((2,1),2),((2,2),4),((2,3),6),\cdots,((3,1),3),((3,2),6),((3,3),9),\cdots\}

给定输入对应的输出称为该输入的映射。q在函数f上的映射表示为f(q)。如果f(q)=s,则称qf映射为s ,写作q\to s。包含所有输出的集合称为值域。

可用f:D\to F来表示函数f是一个定义域和值域分别为DF的函数。

  1. 函数类型

    • 过程与函数

      过程是对计算的描述,给定一个输入,生成一个输出。

      函数或计算问题并不表明如何从给定输入计算相应输出。

      对于同样的输入输出,可能有多种计算方法。

      在一个计算问题里,同一个输入可能对应多个输出。

      我们借助Breeze库来编写各种过程;通常它们被称为函数,但这里用该词表示特定的数学对象。

    • 单射函数(one to one function)

      f:D\to F是单射,如果f(x)=f(y)意味着x=y,也就是说xy都位于D中。

    • 满射函数(onto function)

      f:D\to F是满射,如果对于F的每一个元素z,在D中存在一个元素a使得f(a)=z成立。

    若一个函数同时单射且满射,则该函数为可逆函数。

    • 线性函数:线性函数的图形表示是一条直线(见下图),其定义形如z=f(x)=a+bx。线性函数只有一个自变量和一个因变量。自变量为x,因变量为z

      {%}

    • 多项式函数:该类函数仅涉及x的非负整数指数,比如平方、三次方、四次方等。我们可给出多项式函数的一般定义和它的阶。一个n阶多项式可定义为f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0,其中a的值均为实数,也称为多项式的系数。

      比如,f(x)=4x^3-3x^2+2(见下图):

      {%}

    • 恒等函数:对于任意定义域DidD:D\to D总是将每个定义域元素d映射为d本身(见下图)。

      {%}

    • 常数函数:一类特殊的函数,其图形表示为一条水平线(见下图)。

      {%}

    • 概率分布函数:用于定义某次实验中得到不同结果的相对可能性。它为每个可能的结果都分配一个概率。所有可能结果的概率之和必为1。通常来说,概率分布是均匀分布,即各个可能结果的概率都相同。当掷骰子时,可能的结果为1、2、3、4、5、6,它们的概率为\Pr(1)=\Pr(2)=\Pr(3)=\Pr(4)=\Pr(5)=\Pr(6)=1/6

    • 高斯函数:当实验次数很多时,可用高斯函数来描述该类实验。高斯分布是连续函数,也称正态分布。正态分布的平均值等于中位值,概率分布关于中心对称。
  2. 函数组合

    已知函数f:{\rm A}\to{\rm B}g:{\rm B}\to{\rm C},函数fg的组合为(g~\circ~f):{\rm A}\to{\rm C},记作(g~\circ~f)(x)=g(f(x))。比如,如果f:{1,2,3\}\to\{{\rm A,B,C,D}\}g:{{\rm A,B,C,D}\}\to\{4,5\},则g(y)=2yf(x)=x+1的组合为(g~\circ~f)=2(x+1)

    函数的组合是将一个函数的结果作为另一个函数的输入。因此,在(g~\circ~f)(x)=g(f(x))中,先计算f(),再计算g()。有些函数可被分解为两个或多个更简单的函数。

  3. 假设

    X为输入变量,也称输入特征,y为要预测的输出或目标变量。(x,y)对称为训练样本,用于学习的数据集为由m个训练样本构成的列表,{(x,y)\}表示训练集。X也用来表示输入变量的值的空间,Y则表示输出变量的值的空间。给定一个训练集,用它来学习一个函数h,使得h:X\to Y,其中h(x)y值的预测函数。这样的函数h称为假设(hypothesis)。

    当要预测的目标变量是连续的时,该学习问题称为回归问题。当y的取值为少数离散变量时,则称为分类问题。

    假设我们用x的线性函数来近似求解y

    该假设函数可定义为:

    h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2

    在上述假设函数中,各\theta称为参数,即权重。它们确定了从X映射到Y的线性函数所在的空间。为简化书写,可引入变量x_0=1(称为截距),并将上述等式表示为:

    h(x)=\sum^n_{i=0}\theta_ix_i=\theta^{{\rm T}}x

    表达式右边的\thetax可视为向量,而n则是输入变量的个数。

    在继续学习之前,需要注意我们将从数学基础过渡到学习算法上。优化代价函数和学习\theta是理解各种机器学习算法的基础。

    给定一个训练数据集,如何学习参数集\theta?一种可能的方法是使得h(x)足够近似给定训练集中的y。这就需要定义一个函数来量化对于某个\thetah(x(i))与相应的y有多接近。这样的函数被定义为一个代价函数:

    J(\theta)\frac{1}{2}\sum^m_{i=1}(h_{\theta}(x^{(i)})-y^{(i)})^2

2.2 梯度下降

梯度下降法中的随机梯度下降法会对数据样本进行简单的分布式抽样。损失是优化问题的一部分,因此是一个二级梯度。

\frac{1}{n}\sum^n_{i=1}L(\boldsymbol{w};\boldsymbol{x}_i,y_i)

这需要访问整个数据集,而这不是最优的。

\frac{1}{n}\sum^n_{i=1}L'_{\boldsymbol{w},i}

参数miniBatchFraction指定了整个数据集中用于训练的数据的百分比。这部分子集对应的平均梯度为:

\frac{1}{|S|}\sum_{i\in S}L'_{\boldsymbol{w},i}

它是一个随机梯度。其中S是抽样子集,大小为|S|= miniBatchFraction

如下代码展示了如何在一个小批量数据上使用随机梯度下降法来计算权重和损失。该程序的输出为一个权重向量和损失值。

object SparkSGD {

  def main(args: Array[String]): Unit = {
    val m = 4
    val n = 200000
    val sc = new SparkContext("local[2]", "")
    val points = sc.parallelize(0 until m, 2)
      .mapPartitionsWithIndex { (idx, iter) =>
        val random = new Random(idx)
        iter.map(i => (1.0, Vectors.dense(Array.fill(n)(random.nextDouble()))))
      }.cache()
    val (weights, loss) = GradientDescent.runMiniBatchSGD(
      points,
      new LogisticGradient,
      new SquaredL2Updater,
      0.1,
      2,
      1.0,
      1.0,
      Vectors.dense(new Array[Double](n)))
    println("w:" + weights(0))
    println("loss:" + loss(0))
    sc.stop()
  }

2.3 先验概率、似然和后验概率

贝叶斯定理可表述为:

后验概率 = 先验概率 * 似然

它可表示为P(A~|~B)=(P(B~|~A)~^*~P(A))/P(B), 其中P(A~|~B)为给定BA的概率,即后验概率。

  • 先验概率:其概率分布表示在观察到某个数据对象之前,对该数据对象的了解或不确定性。
  • 后验概率:其概率分布表示在观察到某个数据对象之后,可能参数的条件概率分布情况。
  • 似然:事件归为某一类别的概率。

这可表示如下:

p(\theta~|~y)=\frac{p(y~|~\theta)p(\theta)}{p(y)}=\frac{p(y~|~\theta)p(\theta)}{\int p(y~|~\theta')p(\theta'){\rm d}\theta'}

2.4 微积分

微积分是一种可用来研究事情如何变化的数学工具。它提供了对内部有变动的系统进行建模的框架,并能推断出该模型的预测。

2.4.1 可微微分

导数是微积分的核心。它定义为给定函数的函数值随其某个变量的变化而改变的瞬时变化率。找寻导数的方法称为微分。几何上,如果函数的导数存在且在给定点上有定义,则该点上的导数为函数在该点上正切线的斜率。

微分是积分的逆向过程,有着广泛的应用。比如在物理上,位移对时间的导数为速度,而速度对时间的导数则是加速度。导数常用于求解函数的极大值或极小值。

机器学习所涉及的函数,其变量或特征的维度成百上千。我们会分别计算函数在每个变量维度上的导数,然后将这些偏导数合并到一个向量中。这样的向量就构成了一个梯度。类似地,一个梯度的二阶导数是一个矩阵,称为黑塞(Hessian)矩阵。

理解梯度和黑塞矩阵有助于定义下降的方向和速率,从而获知如何在函数空间中变动,以移动到最底端那个点,进而最小化该函数的值。

下面列出了一个简单的线性回归的目标函数,其中Wb为待定系数。

J(W,b)=\frac{1}{2}||Wx-b||^2

拉格朗日乘子法是微积分中用于在有条件约束时求函数最大化或最小化值的一种标准方法。

2.4.2 积分

积分(integral calculus)将小片段合并到一起来求总数,也称为反微分(anti-differential),而微分(differential)表示划分成小的片段并研究其如何改变。

2.4.3 拉格朗日乘子

在数学的优化问题中,拉格朗日乘子(Lagrange multiplier)是一种在给定等式约束下求解函数局部极大值或极小值的方法。在给定约束下,求解最大熵分布便是一个例子。

最好用例子来辅助说明。假设我们要最大化K(x,y)=-x^2-y^2,但y=x+1

约束函数为g(x,y)=x-y+1=0,则L乘子变为:

L(x,y,\lambda)=-x^2-y^2+\lambda(x-y+1)

xy\lambda分别做微分并设为0可得:

\begin{aligned}&\frac{\partial L}{\partial x}(x,y,\lambda)=-2x+\lambda x=0\\&\frac{\partial L}{\partial y}(x,y,\lambda)=-2y+\lambda x=0\\&\frac{\partial L}{\partial x}(x,y,\lambda)=x-y+1=0\end{aligned}

解上述方程便可得到x=-0.5y=0.5以及\lambda=-1

2.5 可视化

本节介绍如何使用Breeze从DenseVector创建简单的线图。

Breeze借用了Scala绘图工具的大部分功能,但API有所不同。下面的例子中会创建两个带某些值的向量x1y,然后绘制一条线,并将其保存到一个PNG文件里:

package linalg.plot

import breeze.linalg._
import breeze.plot._

object BreezePlotSampleOne {
  def main(args: Array[String]): Unit = {
    val f = Figure()
    val p = f.subplot(0)
    val x = DenseVector(0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8)
    val y = DenseVector(1.1, 2.1, 0.5, 1.0, 3.0, 1.1, 0.0, 0.5, 2.5)
    p += plot(x, y)
    p.xlabel = "x axis"
    p.ylabel = "y axis"
    f.saveas("lines-graph.png")
  }
}

上述代码会生成如下线图:

{%}

Breeze也支持直方图。下面的代码生成了100 000个样本,然后将这些正态分布的随机数划分到100个区间里(见下图)。

package linalg.plot

import breeze.linalg._
import breeze.plot._

object BreezePlotGaussian {
  def main(args: Array[String]): Unit = {
    val f = Figure()
    val p = f.subplot(2, 1, 1)
    val g = breeze.stats.distributions.Gaussian(0, 1)
    p += hist(g.sample(100000), 100)
    p.title = "A normal distribution"
    f.saveas("plot-gaussian-100000.png")
  }
}

100个元素对应的高斯分布如下图所示:

2.6 小结

本章讲解了线性代数的基础知识,它对于机器学习很有用,还讲解了向量和矩阵等基本结构。也介绍了如何使用Spark和Breeze在这些结构上执行基本操作。我们提到了一些技巧,如用SVD来变换数据。另外还分析了线性代数中函数类型的重要性。最后学习了如何使用Breeze绘制基本的图表。下一章将概述机器学习系统、组件和架构。

目录

  • 版权声明
  • 前言
  • 第 1 章 Spark的环境搭建与运行
  • 第 2 章 机器学习的数学基础
  • 第 3 章 机器学习系统设计
  • 第 4 章 Spark上数据的获取、处理与准备
  • 第 5 章 Spark构建推荐引擎
  • 第 6 章 Spark构建分类模型
  • 第 7 章 Spark构建回归模型
  • 第 8 章 Spark构建聚类模型
  • 第 9 章 Spark应用于数据降维
  • 第 10 章 Spark高级文本处理技术
  • 第 11 章 Spark Streaming实时机器学习
  • 第 12 章 Spark ML Pipeline API