Hughui's Blog
0%

Posted on Edited on In

参考书：[Introduction to Linear Algebra]

概念汇总

这一节内容真实非常奇妙啊，简直是线代精华，用线代可以描述世间万物。空间、基、坐标表示、线性变换这四个术语息息相关，这里来阐述其关系。

  • 空间
    这个很好理解，从小我们就知道：点，线，面，体。这就对应着`0维、1维、2维、3维`空间，我们所处的就是三维空间。**（PS:三体中的二向箔，莫非就是说明了宇宙是数字化出来的，歌者实则为编程人员，其甩出的二向箔，就是对宇宙(矩阵表示)的一部分进行了三维到二维的一个线性变化: linear transformation? interesting…）**
  • 基
    既然我们有了空间的概念，那么我们如何表示这个空间呢？`基(basis)`就此出现了，可以理解为：**空间的基础**，即空间的任何一个位置，我们都可以用`基的线性组合`来表示。比如在我们三维空间里面，一个`standard basis`就是`b1(1,0,0) b2(0,1,0) b3(0,0,1)`,任何一个位置`v`我们都可以用`v = α*b1 + β*b2 + Γ*b3`来表示。**需要注意的是，我们对基的选择是非常自由的，如我们将列向量作为基写成矩阵ANxN，R(A)=N，那么这些列向量就可以作为这个N维空间的基。**
  • 坐标表示
    我们平时所画的那个三维坐标轴x,y,z笛卡尔坐标系。常用3个数字来表述一个位置，如`p1=(12,34,56)`。这实则用完整的语言表述是：**p1点，在基`b1(1,0,0) b2(0,1,0) b3(0,0,1)`所表示的三维空间下的坐标为(12,34,56)**，用矩阵的表述语言如。**同一空间下相同的点，在不同的基下其坐标表示会不一样。**
  • 线性变换 (Linear Transformation)
    线性变换的定义就不再赘述了，[1](https://raw.githubusercontent.com/GiganticRay/lei.Blog.File/master/Picture/Linear_Transformation/%E5%9D%90%E6%A0%87%E4%B8%8E%E5%9F%BA.png)中`P405`提出：**任何从V=Rn到W=Rm的线性变换，都对应着其矩阵表达。**(V是n维输入空间，W是m维输出空间。)

    • 既然我们有了空间的概念，那么我们如何表示这个空间呢？基(basis)就此出现了，可以理解为：空间的基础，即空间的任何一个位置，我们都可以用基的线性组合来表示。比如在我们三维空间里面，一个standard basis就是b1(1,0,0) b2(0,1,0) b3(0,0,1),任何一个位置v我们都可以用v = α*b1 + β*b2 + Γ*b3来表示。需要注意的是，我们对基的选择是非常自由的，如我们将列向量作为基写成矩阵ANxN，R(A)=N，那么这些列向量就可以作为这个N维空间的基。

    线性变换的定义就不再赘述了，1中P405提出：任何从V=Rn到W=Rm的线性变换，都对应着其矩阵表达。(V是n维输入空间，W是m维输出空间。)

    思考问题：
    从V=Rn到W=Rm的线性变换的矩阵表达A是唯一的吗？
    answer: 不是唯一的，变换肯定是在空间中进行的，而无关于基的选择。基的选择会确定该变换矩阵表达A。
    解释：我们用顺时针旋转90度来举例子，V=R2到W=R2，那么，不管我们怎么选择V=(v1,v2)与W=(w1,w2)，顺时针旋转90。始终表示顺时针旋转。。只是我们对基的选择，会决定该变换的矩阵表达A。

  • 基变换矩阵
    这个其实相当于特殊的线性变换，即**Basisin -> Basisout的identitic transformation**。说人话就是，我们只变换一下空间的基的表示而已。我们以[1](https://raw.githubusercontent.com/GiganticRay/lei.Blog.File/master/Picture/Linear_Transformation/%E5%9D%90%E6%A0%87%E4%B8%8E%E5%9F%BA.png)中**p412**举例。


  • 如何选择**好的基**，使得该变换T在这组input basis与output basis下的矩阵表示比较简单？
    待续…

    • 待续…

    Posted on Edited on In

    K近邻算法 简介

    这一部分就不赘述了，挺基本的。

    为啥需要KD-Tree

    KD-Tree是存储训练数据的一种结构，因为K近邻算法没有显示的学习过程，所以每次对目标点进行分类的时候，都需要借助已知的训练数据。而类似感知机这种具有显示的学习过程的算法，会根据训练数据，得出一个模型sign(<w,x>+B)，后续预测直接用训练好的模型进行预测就行了。
    因为这个特性，所以如果不采取特殊的数据结构对数据进行存储，那么每一次分类目标点的时候，都要遍历所有的训练数据，时间不可控。对此，KD-Tree就出来了，其实KD-Tree听名字就是一棵树，可以参考二分查找的过程。

    什么是KD-Tree

    这里先给出一颗KD-Tree的例子，后续再对KD-tree的Construction与Searching进行论述。
    每一个节点对应着一个划分(就是一个大饼被刀切了)，如图所示，根节点(30,40)对应了整个输入空间（整个饼），根节点将整个输入控件分为了两类，分别是x<30, x>30，由其两个分支表示。（解释为啥是x，这与选择的特征有关，看图根节点左边是选的x，所以对比x）。这样不断往下划分，最终得到了整个输入空间的划分（左边），对应的数据结构如右边所示。
    闲话：其实通过上面描述应该就知道KD-Tree存储的什么东西了，它将数据的信息（具体特征的数值大小）表示在了结构上。其与排序二叉树十分类似嘛。

    KD-Tree’s Construction

    • 数据描述：(5,25) (10, 12) (30, 40) (35, 45) (50, 30) (70, 70)，输入空间为整个二维平面。即每个样本点，有两个特征，我们假定为(x, y)。我们先展示整个构造过程，再解释构造细节。
    1. 随机选择一点(30, 40)，作为`根节点`，x<30的(5,25) (10, 12)位于根节点左子树上。大于的就位于右子树。
    2. 在左子树中，随机选择一点作为`左子树的根节点`，这里选择了(5, 25)。然后y<25的位于其左子树，y>25的位于右子树
    3. 这样不断迭代，最终形成了树的模样。
    4. 根据构造出来的树画图：根据`判别条件`画垂直的线。如根节点，根据x来判别的，那么就在这一点上，垂直与x轴，将其代表的`划分`(根节点是整个输入空间嘛)，一分为二。

    ** 由上可知，整个过程中存在着3个问题尚未解决：我们在划分时应该选取哪个维度？划分时我们应该选择哪一个值来划分？什么时候停止划分？ **

  • 应该选择哪一个维度？
    一般是交叉维度来进行选择，如有n个维度，那么依次选择(1, 2, 3…n, 1, 2…n…)这样子。上述例子中就是交叉选择(x,y,x,y…)来进行的
  • 维度确定了我们应该选择哪一个点当作划分点？
    这个其实理论上来说当然是选择搜索路径最短的那个点，但是这好像不是很容易达到。《统计学习方法》中采用的方法是`采用中位数当作划分点`，这样可以保证整个树是平衡的。如上述第一步骤中，x的中位数是(30, 40) **(以左边为基准的话)**。那么根节点就是(30, 40)。
  • 我们什么时候停止划分?
    这是我们自己设定阈值，我们知道，每一个点对应一个划分区域，那么我们可设定 `threshold = 10`，表示如果这个划分区域中， 
    1
    2
    if num(point_In_Split) < threshold
    	End Spliting.

    • 这个其实理论上来说当然是选择搜索路径最短的那个点，但是这好像不是很容易达到。《统计学习方法》中采用的方法是采用中位数当作划分点，这样可以保证整个树是平衡的。如上述第一步骤中，x的中位数是(30, 40) (以左边为基准的话)。那么根节点就是(30, 40)。

    KD-Tree’s Searching

    这个我懒得描述了，看李航老师《统计学习方法》上就有。需要更正的一点是**（我觉得其算法3.3漏了一个判别步骤）**，算法3.3的(1)中，强调的是“直到子节点为叶节点为止”，但是有可能搜索结束后发现结束的那个节点并不是叶节点，如(50,30)，那么就要在(50, 30)下添加一个空节点，然后以该空节点作为"包含目标点x的叶节点"。

    Posted on Edited on In

    1. 奇异值分解：A=UΣV^T, 其中，U是AA^T的特征向量，Σ^2是AA^T的特征值，V是A^TA的特征向量，目的即将图片weights x heights分解为矩阵表达，这样存储时仅仅存储矩阵表达即可，从而达到压缩的效果。代码如下所示。

    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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    import numpy as np
    from PIL import Image


    if __name__ == "__main__":
        # psuedo Code
        # 1. 加载图片成width x height的数组A
        # 2. 计算A^TA，算出其lambda^2, lambda是SIGMA, 对应特征向量是V1，V2；再根据(1):解AA^T的eigen vector作为U；（2）或者解AV/SIGMA得出U。
        # 3. 从大到小排列SIGMA以及对应U，V得出分解内容。
        # 4. 分析结论

        # 1. 得出矩阵A_TA
        Img = Image.open('./test.jpg')
        Img_array = np.array(Img)
        A = Img_array[:,:,0]
        A_T = A.transpose()
        A_TA = np.dot(A_T, A)

        # 2. 计算出对应特征值及对应特征向量，并排好序（in order of importance）
        eigenvalues,eigenVectors = np.linalg.eig(A_TA)
        tmp = np.column_stack((eigenvalues, eigenVectors))
        tmp = tmp[np.argsort(-(tmp[:,0]))]
        singularValues, singularVectorsV = np.nan_to_num(np.power(tmp[:, 0], 0.5)), tmp[:, 1:]

        # 用AV/SIGMA = U 计算U
        singularVectorsU = np.dot(A, singularVectorsV)/singularValues

        # 设置阈值为99%
        threshold = 0.99
        SigmaSum = np.sum(singularValues)
        tmp = singularValues[0]
        i = 1
        while(tmp/SigmaSum &lt;= threshold):
            tmp += singularValues[i]
            i += 1

        reConstructImgArray = np.dot(
            np.dot(singularVectorsU[:, 0:i+1], np.diag(singularValues[0:i+1])), 
            np.transpose(singularVectorsV[:, 0:i+1]))

        reConstructImg = Image.fromarray(reConstructImgArray)
        reConstructImg.show()
        # 结果为i=1257, 即压缩为了1257*(1980+2640), 原图是1980*2640, 这样压缩保留了99%的信息
        print("good luck")

    2. 左为重构，右为原图

    3. 结果说明

    > 原图大小是 198026403(带color channel)，现经过SVD压缩为了(1257(1980+2640)3)(代码中为了简单表明过程，只计算了一个color channel上的)。上述例子表明，在保存图片信息99%的情况下，压缩率为90%。

    Posted on Edited on In

    参考书目章节

    1. Introduction to linear algebra: P239, The Factorization A = QR
  • Iterative Methods for Sparse Linear systems: **P11**, Gram-schmidt

    [](#一：Gram-Schmidt)一：Gram-Schmidt

    Interesting: gilbert strang said:”i don’t know what schmidt did in this greatful process”
    在很多工作中，我们需要用到一组向量空间的正交基来简化计算（如简化求解Ax=b的最小二乘解的过程）。Gram-Schmidt就是**正交化**一种经典方法，掌握了**投影**后，gram-schmidt就很好理解了。

    • Interesting: gilbert strang said:”i don’t know what schmidt did in this greatful process”
    在很多工作中，我们需要用到一组向量空间的正交基来简化计算（如简化求解Ax=b的最小二乘解的过程）。Gram-Schmidt就是正交化一种经典方法，掌握了投影后，gram-schmidt就很好理解了。

    prerequisite: A的column space’s projection matrix is

    [](#1-首先以二维为例)1. 首先以二维为例

    `(x1, x2)`是线性无关的列向量，现需找出`orthonormal的(q1, q2)`来表示(x1,x2)的`列空间`。第一步:`q1=x1/norm2(x1)`。问题是如何依据x2找到q2使`<q1, q2> = 0`。 如图所示，`x2`在`q1`上的投影`p=<q1, x2>q1`，而我们需要的部分是`e(error) = x2-p`(# 注为啥叫error在投影那一章节有记录)。从而令`q2 = e/norm2(e)`。**用人话**来说就是，第n维的目标向量`(qn)`是第n维的已知向量`(xn)`依次减去其在`q1 -> qn-1`上的投影，最后单位化。

    [](#2-三维图示)2. 三维图示

    由此可推到出Gram_Schmidt的公式：

    [](#3-Pseudo-Code-of-Gram-Schmidt)3. Pseudo Code of Gram-Schmidt

    2. 三维图示

    二：A=QR与Gram-Schmidt的关系

    实际上这也是A=QR的第一种推理方式，即从Gram-Schmidt的推理过程得出A=QR。现假设我们已经通过Gram-Schmidt得到了前j个q(q1,q2...qj)，这样我们就可以得到,即将xj分解至每一个正交基上。用矩阵的语言进行表达，即X=QR,X=[x1, x2...,xr],Q=[q1,q2,...,qr]。如下图所示

    三：从行列空间规律得出A=QR

    这是A=QR的第二种推理方式，C(A)是independent的，在Gram-Schmidt中，我们的目的是找出orthonormal的Q，从目的而言，Q与A的列向量代表的向量空间肯定是一样的，即C(A) = C(Q)，根据线代的基础知识我们知道，肯定存在一个矩阵R，使得A=QR(A与Q的列向量空间相同)。若A is Square，那么A and Q both are invertiable。从而R=Q^(-1)A，又Q is orthonormal，so Q^(-1) = Q^T，so R = Q^TA，这样就求出了R，如下图所示。

    四：A=QR的应用

    gilbert Strang教授在书上说过："the matrix factorization is of most importance in linear algebra",A=QR作为一种矩阵分解，可以把线性独立的矩阵，分解成QR，Q是orthonormal,R又是upper triangle，特别是orthonormal给计算提供了很好的性质，目前接触到的就是在least square solution中的投影矩阵部分，逆的那一块直接为单位矩阵了，大大节约了计算时间成本。