Why Floyd–Warshall algorithm works

Question Thrown

All we know that Floyd–Warshall algorithm is a dynamic programming algorithm aims to solve the all-pairs shortest path problem. the code itself is simple as follows:

1
2
3
4
5
6
7
8
9

for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

Shown already in the most common blogs that k standards for the intermediate node. dist[i][j] = dist[i][k] + dist[k][j]; updates the shortest path from i to j through k. Now a natural question is why this works since dist[i][k] and dist[k][j] are not necessarily the shortest path from i to k and k to j respectively.

Takeaway

The above thought k stands for the intermediate node is nearly correct. It actually stands for all [0, k] can be taked as the intermediate nodes to get the dist[i][j]. so when we traverse to the final k, aka k = n - 1, dist[i][j] would be updated with the meaning: the shortest path from i to j through all nodes [0, n - 1].

Analysis

• Initial step: the left pic
• while k == 0: updates all pairs through A. since the in-degree of A equals to 0, so we do not show the pic.
• while k == 1: Since we’ve already passed step2, so implicitly this steps actually updates all pairs through B (and A). Shown in pic2.
• while k == 2: Similarly to step3, Updating all pairs through C (and A, B)

  More about final step. Take A->D as example. The corrosponding updating code: dist[A][D] = dist[A][C] + dist[C][D];. Answering to the first question in the first of the article. dist[A][C] has already been updated by dist[A][B] + dist[B][C] which means dist[A][C] in this time have already considered the info of A, B, C.

Conditional Number of Matrix

In This post, I will comb the inference of the conditional number of Matrix

WHAT

不得不说，咱们语言文化的博大精深。所谓“千里之堤，溃于蚁穴”，则正是条件数的表示，旨在对某件事物进行轻微的扰动，那么其会产生巨大的影响。

Defenition

所以对于方程组 ， 如果我们给一个轻微的扰动，其解x变化仍在我们可接受的范围之内的话，那么就说这个矩阵是良好的矩阵(Well Done!)，否则，它就是一个病态的矩阵。

针对上述定义，我们引出两个问题

所谓轻微的扰动，并不是指整个矩阵中所有元素变化量的大小，而是说变化元素的个数。通常，我们用

来表示仅在位置的元素为，其余位置为的矩阵。而轻微扰动，即在的基础之上 append 一些的元素。

下面进行条件数的推导。

Inference of the Conditional Number

Neumann Series

在这里只能说诺伊曼牛逼, If , 那么就是非奇异的，并且

这个直接相乘即可验证出来了，诺伊曼给了我们一个估算的级数，太棒了。

Perturbation Term

现在我们假设给予矩阵一些轻微的扰动， 即，现在来考虑的解，与的解的gap。因为可逆，且是轻微扰动，所以说是可逆的，所以

从而，我们仅要看与的差异即可。下面由诺伊曼级数进行导出。

假设，(这个其实很好满足嘛，直觉上只要不要太大就好，因为是轻微扰动项，所以说本身很小很小的，这样说不太严谨，但是intuitive)。

为了方便起见，我们仅考虑其一阶估计

可见，右边儿的第二项就是扰动项：。

扰动项 => 条件数

首先我们先得到的上界

这肯定是上界嘛，因为只估算到了一阶。那么，只要这个上界足够小，那么其误差就可能大。

由于解本身有大有小，所以我们不能直接用其差值进行误差的估量，进而采用

其中，由于B是扰动，所以 本身很小，所以其上界如果很大，那么肯定是出了问题。

我们称为矩阵的条件数。如果很小，那么其差值上界定然小，如果很大，那么其差值上界就很大，从而其真实的差值就可能大，就是病态矩阵。（注意定然和可能）。

至于这个“小”还是“大”，因为已经经过模的规范化了，所以不同矩阵之间也可以比较。

条件数为多少时才是凉态的？

这里其实可以做一个实验，编写代码画图，构造一些指定条件数的矩阵出来，观察其轻微扰动之后的差值。给出网友的结论：（第一步骤实验！）

首先奇异和病态没有必然的联系，良态、病态、条件数都要针对求解的问题而言，比如说矩阵求逆的性态和矩阵求特征值的性态就完全是两码事 　在2-范数扰动的意义下，矩阵求逆或者解线性方程组的时候奇异矩阵可以认为是最病态（无限病态）的矩阵，因为它有零奇异值（注意，这个问题的性态体现在奇异值而不是特征值） 　至于什么样的矩阵算病态，没有绝对的标准，因为大和小是相对的概念 　通常病态与否也与实际计算的机器精度有关，比如IEEE单精度下K=10^4算比较病态了，但在IEEE双精度下就算比较良态

Fourier

从基础数学的角度理解傅里叶变换

Foundamental Mathematics

以下来自 https://betterexplained.com/

- 自然数E是所有增量的[**基数**](https://betterexplained.com/articles/an-intuitive-guide-to-exponential-functions-e/)，如果指数为虚数即表示旋转。
1. [**Euler’s Formula**](https://betterexplained.com/articles/intuitive-understanding-of-eulers-formula/)表示的含义是啥，即分别从**增量**的形式，**grid**的形式，描述**圆周运动**。 $$\begin{equation}\label{1} e^{ix}=\cos{(x)} + i\sin{(x)} \end{equation}$$

   [](#傅里叶变换是干啥的)傅里叶变换是干啥的

   先阅读以下[这里](https://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/)，用一句表示就是，我们可以借助傅里叶变换将收集到的信号分离成频率为(0hz,1hz…N-1hz)的正弦波。

   [](#手写推导)手写推导

1. 自然数E是所有增量的基数，如果指数为虚数即表示旋转。

About Matrix

About Algorithm Design

Abstract

听君一席话，在下如拨云见日，茅塞顿开啊（\狗头，可怜的楚团长）.本文符号记法随前文。上回提到，任何一个从空间的线性变换T，在给定的基之后，都有其矩阵表示。现我们给出约束：

- 输入空间**等于**输出空间：。 - 输入空间的基**等于**输出空间的基：。
那么，如果在的矩阵为，在的矩阵为，记则

而我们知道，**对角矩阵**就是线性代数的神，其拥有很多良好的性质，所以我们可不可以选择一组基，使得该线性变换的矩阵为对角矩阵呢？

Invariant Subspaces

Definition

给定， ，是上的线性算子，如果

我们就称是中下的不变子空间。说人话就是，作用在中的任一元素后，结果仍然在中。

Restricted Operator

有了不变子空间的定义后我们很自然地可以引入restricted operator，由于作用在上与中的其他元素无关，那么就好像是一个baby ，我们定义一个只作用在上的作用相同的变换。此即restricted operator。

[](#The-matrix-representation-of-restricted-operator)The matrix representation of restricted operator

The matrix of involved

如果我们把的基作为输入基的一部分，那么此时的的形式是怎样的呢？emm..interesting.
令是的一组基，那么，

由于是不依赖于后面的的，所以
\begin{equation}\label{5}
\begin{matrix}
T(x_j)=\sum_{i=1}^{r}\alpha_{ij}x_i &
[T(x_j)]B = \begin{pmatrix}
\alpha{1j}\
···\
\alpha{rj}\
0\
···\
0
\end{pmatrix}\end{matrix}
\end{equation}

\begin{equation}\label{6}
\begin{matrix}
T(y_j)=\sum_{i=1}^{r}\beta_{ij}x_i + \sum_{i=1}^{q}\gamma_{ij}y_i &
[T(y_j)]B = \begin{pmatrix}
\beta{1j}\
···\
\beta_{rj}\
\gamma_{1j}\
···\
\gamma_{qj}
\end{pmatrix}\end{matrix}
\end{equation}

从而，可得出：
\begin{equation}\label{7}
[T]B =
\begin{pmatrix}
\alpha{11} & ··· & \alpha_{1r} & \beta_{11} & ··· & \beta_{1q}\
·& ··· & · & · & ··· & ·\
\alpha_{r1} & ··· & \alpha_{rr} & \beta_{r1} & ··· & \beta_{rq}\
0& ··· & 0 & \gamma_{11} & ··· & \gamma_{1q}\
·& ··· & · & · & ··· & ·\
0& ··· & 0 & \gamma_{q1} & ··· & \gamma_{qq}
\end{pmatrix}
\end{equation}
左上角部分即为$[T_{/\chi}]{B{\chi}}$。

联想到特征向量以及特征空间

上面我们已经得出一般形式，不难发现，的n个特征向量**（前面我们的约束），都是下的不变子空间，那么有意思的来了，把这n个特征向量作为的基，那么的形式就是一个对角矩阵**了，对角线元素为特征值，interesting。

Notation

1. 表示，以为输入、输出基下，变换的矩阵表示
2. 表示分别以为输入、输出基下，变换的矩阵表示。
3. 表示这个object在下的坐标表示。上述

Abstract

关于基变换算子的一些理解，(秃头进行中…)基变换算子是什么，我们可以用基变换算子干嘛？

• 用基变换算子，当然是对物体object进行基变换的鸭
• 探索对于同一个线性变换，在给定不同的输入基以及输出基下，其对应的矩阵有什么联系

什么是基变换算子

这一点是我学习时非常困扰的一点，把一切抛之于脑后，不去想基变换，就把它看成是一种变换，这样就好解释了。首先我们说明：基变换是一种线性变换，这个自己验证即可，而一个从的线性变换是客观存在的，只有当我们给定的一组基后，这个线性变换的矩阵表示才被确定下来。
我们知道，给定空间的一组基从空间的任意线性变换，都对应着一个矩阵表示。现在我们引出一个问题：基变换也是线性变换，那么我们给定一组基,基变换是从基，请问与之间都是基，那他们有什么联系呢？
这是我学习时非常非常困惑的一点，按照我的理解，这两者没有任何联系，他们所表示的内容是两个不同的概念：
把基变换算子就抽象出一个变换，其输入空间与输出空间都是（管它什么基变换不变换的，就看成是一个变换），而一个线性变换要在给定输入空间的一组输入基、输出空间的一组输出基下，才能给出其唯一的矩阵表示。上面的输入、输出基，即是。那么可能就有人问了：“那是啥呢？”，我们只要把****看作是这个线性变换里边儿的元素就可以了。
对应，李老师直接给出线性变换的定义：给定两个基。把变换为的T表示为

tips：上述定义之中的基是T要变换的东西，而不是T所在的基，好绕啊…

基变换算子的作用之一

假设是一个基变换算子的矩阵表示$P=[T]{BB’}$，x是一个object，其在下的坐标表示为$[x]{B}B’[x]{B’}[x]{B’}=P·[x]_{B}$。

基变换算子的矩阵表示是啥

不给定输入基与输出基谈变换的矩阵表示都是耍流氓，上述我们给出了基变换算子的定义，却并未给出该变换输入空间的输入基，输出空间的输出基。来看一下这个表达式

\begin{equation}\label{2}
P=[T]{BB}=[T]{B’B’}=[I]{BB’}=([x_1]{B’}|[x_2]{B’}|···|[x_n]{B’})
\end{equation}

我个人觉得的就是，由于基变换算子太饶了，而我们可以用一个简单的形式来等价表示，即$[I]{BB’}[I]{BB’}$来表示从B到B’的线性变换的矩阵了。

Prove Equation 3

根据定义，我们可以得到：

即表示这个object，在下的坐标表示，即。现在，我们同时考虑对等式3左右两边同时进行T变换：

这个式子很有趣啊，表示在下的坐标表示也为，即，结合等式3，那么就是

这样我们可以得到如下：

\begin{equation}\label{6}
[T]_b = ([T(x_1)]_B,[T(x_2)]B···[T(x_n)]B) = ([x_1]{B’},[x_2]{B’}···,[x_n]B’) = [T]{B’}
\end{equation}

证明与他们相等也很简单

\begin{equation}\label{7}
[I]{BB’}=[[I(x_n)]{B’},[I(x_2)]{B’}···,[I(x_n)]{B’}]=[[x_1]{B’},[x_2]{B’}···,[x_n]{B’}]=[T]{B’}
\end{equation}

我靠，这也太神奇了，从而，研究从的基变换算子，我们就可以研究这个矩阵了。

基变换算子的作用之二

考虑这样一种情况，是在上的一个线性算子(linear operator)，分别是的两组基，那么$[A]B[A]{B’}$这两个矩阵既然表示同样线性变换，那么它们有什么联系呢？

\begin{equation}\label{8}
[A]B = P^{-1}[A]{B’}P
\end{equation}

where ，这个很好理解嘛，我们把两边都乘以，即

\begin{equation}\label{9}
[A]_B[x]B = P^{-1}[A]{B’}P[x]_B
\end{equation}

学废了吗？因为这个东西，所以如果我们已知一个线性变换的矩阵表示$[A]B[A]{B’}$，这样在特定情况下就可以方便问题求解了。（一定要注意：线性变换是客观存在的，上述讨论的只是线性算子，即输入空间、输出空间是一样的。并且仅考虑输入空间、输出空间的基也是一样的。就相当于控制变量嘛，有同学可能要问了，那诸如投影算子这些呢，它们输入、输出空间肯定不一样鸭。这种情况不在我们的

Abstract

我在上篇文章中复现了李老师的证明：“在给定基下，任意线性变换都有其对应的矩阵表示”。然后关于这个矩阵表示是啥就没有写了，近些日子有些盆友(大妹子！)来问小雷同学，想着还是写出来吧，矩阵表示也蛮trivial的，just as a remainder。

Notation

令、的基分别是{B = u₁, u₂,…,u_n}、{B’=v₁, v₂,…,v_m}。(tips: 即object u在基B下的坐标表示)。是从的一个线性变化。目的: 需要求给定基下，该变换的矩阵表示。

得出过程

换句话说，即一个Object在下坐标，左乘后$A[u]BuTV[u]{B’} = (\sigma_1, \sigma_2…\sigma_m)^T$。

我们知道

···

因为是线性变换，所以

根据线性变化，把它提出来，然后再展开，可以得到

以提出公因式

的系数即是变换后的object在上的系数，写成矩阵形式，其系数为

$

$

左边这个矩阵就是这个啦。
再次强调，里面的始终表示的对象，同理，等式右边也是对象。注意我sigma下标的定义，后面自然就明白了。

abstract

今天上完liao(致敬)李保滨老师的矩阵分析课程，对线性变换有了更进一步的理解，李老师与Gilbert的课程还是有差异的，个人感觉Gilbert老师的18.06对线代的基础（4个基本子空间）讲的更透彻，而李老师再线性变换处更明了

prerequisite

矩阵乘法AB=C的意义、C的行列与A、B行列的关系、线性变换、向量空间。这要搞清楚，这里不展开。

基本概念

首先我们想一个问题，如何表示一个物体，其实小时候大家都做过这样的数学题，在坐标轴**（笛卡尔棒棒）上对一些坐标标点，最后把这些点连起来，最终就会得到一个可爱的猫猫啦。可见，坐标可以用来描述物体。但是，仅仅是坐标就足够了吗。look, here’s the deal（poor Biden…），当然不是的，题目给出坐标时，默认了我们都在空间的标准基(standard basis)里。所以，除了坐标之外，我们还需要空间的基。
比如说，我们说一点(object)的coordinate是c = (1,2,3)，实际上我们默认是在说这个object = c1*e1 + c2*e2 + c3*e3。只是我们选择的基太tricky了，所以可以用coordinate stand for that object directly(important)。
这样，用基和坐标,就可以表述出我们的猫猫（客观物体object）了。
tips：Gilbert的书中貌似有点说不清楚object与coordinate的关系(当然是我太菜了)**，李老师证明了：在给定基下，每一个线性变换都有其矩阵表示。

Prove: 在给定基下，每一个线性变换都有其矩阵表示

证明思路：联想到普通情况，令{e1, e2, e3}为$R^3$的基，我们如何证明在$R^3$空间中的任一目标，都能表示出来呢？obviously，令一个系数向量C(3x1)代表坐标，一个矩阵代表基B(3x3)，那么，BC就可以唯一表示这个object了。同理，李老师的证明过程如下：

1. $U$与$V$分别代表两个向量空间$U=R^n$, $V=R^m$，把从U->V的所有线性变换放到一个集合里，记作L(U, V)，那么L(U, V)是一个向量空间。
2. 令$U$、$V$的基分别是B={u₁, u₂,…,u_n}、B'={v₁, v₂,…,v_m}。定义$T_{ji}(u)=\xi_jv_i$，$(\xi_1, \xi_2…\xi_n)^T=[u]_B$(tips: 即object u在基B下的坐标表示)`，那么，我们可以得出下面结论3:
3. $ T_L = \left { T_{ji}\right }_{j=1…n}^{i=1…m} $是L(U, V)的一组基。
4. 如果有了结论3，那么得证。 即给定空间U、V的基，任意一个从U -> V的线性变换，我们都可以用这组基$T_L$来表示，而表示的坐标coordinate，即是：在U、V的给定基下，从U -> V线性变换T的矩阵表示。

证明$ T_L = \left { T_{ji}\right }_{j=1…n}^{i=1…m} $是L(U, V)的一组基

证明思路：1.$T_L$是线性无关的。2.$L(U, V)$中的任意一个元素，都能用$T_L$中的元素表示。

1.根据定义即证明$\sum_{j,i}\eta_{ji}T_{ji} = 0$中的所有$\eta_{ji}只能等于0$。这个鬼东西怎么证明呢，用到了一个小trick**（tips:我这非数学专业就不去想那些老头子怎么想出来的了）**
\begin{equation}\label{1}
T_{ji}(u_k) = \left{\begin{matrix}
v_i & j=k\
0 & j≠k
\end{matrix}\right.
\end{equation}

现在把要证的等式两端同时乘以$u_k$，即基组$U$的第k个基，得到
\begin{equation}\label{2}
(\sum_{j,i}\eta_{ji}T_{ji})(u_k) = 0
\end{equation}
去括号，相当于把$u_k$做${T_{ji}}$变换。
\begin{equation}\label{3}
\sum_{j,i}\eta_{ji}T_{ji}(u_k) = 0
\end{equation}
结合公式1，即可得出
\begin{equation}\label{4}
\sum_{i=1}^{m}\eta_{ki}v_i = 0
\end{equation}
因为${v_1,v_2,v_3..v_m}$是输出空间空间$V$的一组基底，所以所有 $\eta$ 都等于0，得证。

要证第二个，首先要搞清楚$L(U, V)$中的元素是什么,exactly。这个集合里面存放的是：从$U$ -> $V$的所有线性变换。

现从$L(U,V)$中任取一个元素$T’$，now, enjoying this formulation,hahaha
\begin{equation}\label{5}
T(u) = T(\sum_{j=1}^{n}\xi_ju_j) = \sum_{j=1}^{n}\xi_jT(u_j) = \sum_{j=1}^{n}\xi_j \sum_{i=1}^{m}\alpha_{ij}v_i = \sum_{i, j}\alpha_{ij}\xi_jv_i = \sum_{i, j}T_{ji}(u)
\end{equation}
非常漂亮的过程。

现在，我们想证明的都证明完了，就可以说, 在给定输入空间$U$、输出空间$V$，以及他们自个的基$B$、$B’$下，每一个从$U$到$V$的线性变换都有其矩阵表示。

Brain Expansion

上述表述有一个flaw我没有提，你看那个第3点，为什么我们要把$T_{ji}(u)=\xi_jv_i$, $(\xi_1, \xi_2…\xi_n)^T=[u]B$, $ T_L = \left { T{ji}\right }{j=1…n}^{i=1…m} $作为L(U, V)的一组基呢，它代表着啥含义。这点老师上课也没有讲(or 我走神了?)下面我简单分析一下
首先我们看一下这个表达式
\begin{equation}\label{6}
T{ji}(u_k) = \left{\begin{matrix}
v_i & j=k\
0 & j≠k
\end{matrix}\right.
\end{equation}
将上面三个带入就发现这是成立的，即经过$T_{ki}$变换，$u_k$变换成了$v_i$，并且这个$T_{ki}$将其他的基$u_z(z≠k)$变成了0。穷举法，任意一个变换可能将原来空间的基$u_{1,2…n}$，变换成任意一个输出空间基的倍数$v_{1,2…m}$。所以，将这mxn朴素变换(我瞎说的词)进行线性组合，既可以组合成任意在给定输入空间$U$、输出空间$V$，以及他们自个的基$B$、$B’$下，从$U$到$V$的线性变换。想出这个证明的人，我愿称之为现代王！

再往下延拓就是如何将这个变换用矩阵表示出来了，具体做法也很简单，这里就不说了

Summary

我在读Gilbert的setction 8的时候，总是分不清其表达式$T(u)=u$的这两个u到底是代表的object还是coordinate。但是李老师讲解的过程$T(u)$很明确，就是说对object u 进行 $T$变换。不过遗憾的是，李老师这堂课的视频并没有放出来，我上面的东西估计只有我自己能看懂hhh，(tips: 大家不妨试试@一下UCAS的教务处^-^)。（再tips:上课已一月有余，北京的冷空气让我的厚衣服屁用都没有了)。

参考章节目录

- Iteriative Methods for Sparse Linear Systems P12 - MATH 5330: Computational Methods of Linear Algebra—Lecture Note 10: Householder Transformation—Xianyi Zeng—Department of Mathematical Sciences, UTEP

Abstract

关于A=QR的分解，有三种方法：Gram、Givens、Householder，Givens我不熟悉、但好像和旋转有关、可以保留A’s columns的长度。HouseHolder也有这个优点。

大致了解

Gram-Schmidt的方法是通过一步一步地将新的列A_j，减去其在已正交化的q₁，q₂，q_(j-1)的投影从而得到新的正交项以此构成Q，HouseHolder采取了另外一种完全的方法，其一步一步地将待分解矩阵A，分解成Echelon matrix，当然这个分解过程不是简单的Gaussian Decomposition，而是用了HouseHolder算子，下面翻译一下参考书目1中的分解步骤

什么是Householder算子（Householder矩阵的几何表示）

Householder算子是一个矩阵，其形式是P = I - 2ww^T，这里我一般记作P_w，因为P是由w决定的，后续我们也是针对待分解矩阵的每一列来构造对应的w，从而得出针对每一列的P。
易证，P是Ortogonal矩阵、且是Symmetric矩阵：P^T=P，P^TP=I。
注意，我们后续在选择w的时候，要让其是2-norm unity的向量。
从几何上来看，Px表示的就是x,关于空间{w}^⊥的镜像。画图表示就是

v就是上文中的w、H_v就是上文中的P_w。

如何为每一列Xj构造每一个HouseHolder矩阵Pj

至此、我们就用通过x、求得了一个w，使得x在P_w的作用下可以变换至||x||e₁，w的表达式如下

现在我们看一下第k次HouseHolder变换的情况，操作对象当然是已经完成k-1次的矩阵了鸭。表达式如下：

矩阵在列k-1前是一个上三角矩阵。进行下一步时，前k-1列保持不变，根据第k列的向量x_k，确定一个w，然后生成P。w的形状是1至k-1个元素都是0，这样才保证了前k-1列不变。P_k的推导如下

当k=0时，即第一次变换的P，此时的β=αe₁，符合上文的描述。

构造A=QR

到这里，我们就描述完了整个X的分解过程，使得x可以分解成

这里仅需要一小步、就可以将上式变成A=QR的美丽式子了鸭。(下面这个过程，即将R那部分中的0，转移到P中去，形成Q).我们将1.22表示成下面的式子1.23，R是mxm的矩阵。

我们在前面给出了P_i是对称、且正交的，所以我们把P放到右边:

我们用**E_m**表示I的前m列，shape=(n,m)。可表示如下

令Q=P^TE_m，这表示取P^T的前m列。我们可以验证：

所以，Q是我们想要的Q(Orthonomal)。分解成功！

Pseudo Code

参考书籍：《统计学习方法》

参考网络资源：信息增益比details/82317369

熵的意义

书中P60描述，熵是表示随机变量不确定性的度量。that’s right，经常看见什么：“宇宙是熵增的”这种句子，实际上是在说，宇宙的发展过程，是慢慢从有序的状态，发展至无序的状态。这里熵的定义，就不难理解了，一个随机变量越随机，它的熵就越大。聪明的Rudolf Clausius归纳了这样一个表达式（将可见的现象，用抽象的数学公式表达出来，厉害）

关于这个表达式，承认就是了，书上P60给了一个很直观的例子，即随机变量X只有两个取值，每个取值的概率都是1/2的情况。很好理解

关于H(X)这个符号的解释

H(X)，X是一个随机变量，我们可以看作是一个集合。由于H(X)表示该集合的混乱程度，换句话说即从某种意义上表示了X的分布，所以可以用H(p)来表示。

关于条件熵表达式H(Y|X)的解释。

集合Y中的元素有很多个特征，每个特征的取值决定了集合中个体的类别。H(Y|X)就表示，我们在已经知道特征X的取值情况以后，集合Y的混乱程度。数学表达式为

解释：这个p_i即p(x=x_i)，如上所示，整个表达式表达的意思是，我们已经知道了X特征的分布情况下Y的混乱程度。

信息增益

信息增益就很简单啦，集合D的个体，有很多个特征，特征A对训练数据D的信息增益即：“集合D原来的熵、减去已知A的分布后集合D的熵”

信息增益比

决策树对应有几个经典的算法，区别就是他们采用的计算**“信息增益”的方式不一样，c4.5采用的就是信息增益比的方式。
这里我们要承认一点：信息增益的方法，存在偏向于选择取值较多的特征的问题。如上文的例子中，如果以日期作为候选特征，那么它的信息增益很大（一想就通嘛，每天一个日期，就分出来了一个分支，分支下只有一个样本，那肯定是有序的啊），但是很明显，这样划分并没有什么用。造成这个的原因就是： 日期这个特征，可选择的取值较多。
解决办法：增加一个惩罚项。通常来说，增加一个惩罚项是用加法嘛，比如取值越多的特征，就给其信息增益减去一个数值。信息增益比这里用了除法。
惩罚原则：首先还是要保持要选择能够增益信息较大的特征**，同时特征可选择的值越多，那么惩罚越大，把惩罚放到分母上，即分母越小。惩罚项是**“A的内部信息(intrinsic information of an attribution)”**，在我看来，这个惩罚项可以用D关于A的条件熵来替代吧，因为A的可取值选择越多、理应H(D|A)越小（即在A的帮助下D变得不再凌乱了）。或许只是H(D|A)计算麻烦才没有使用罢了。

参考书：[Introduction to Linear Algebra]

概念汇总

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

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

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

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

待续…