Knowledge

1.2.1. Probability space

1.2.2. Entropy

1.3.1. 参考资料

2.1.1. STL常用容器

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
int main() {
    // vector
    std::vector<int> x_vector = {1, 2, 3};
    x_vector.pop_back(); x_vector.emplace_back(4);
    cout << "vector member (random access): " << x_vector[1] << endl;
    cout << "vector first member: " << x_vector.front() << endl;
    cout << "vector last member: " << x_vector.back() << endl;
    // list
    std::list<int> x_list = {1, 2, 3};
    x_list.pop_front(); x_list.emplace_front(0);
    x_list.pop_back(); x_list.emplace_back(4);
    cout << "list first member: " << x_list.front() << endl;
    cout << "list last member: " << x_list.back() << endl;
    // stack
    std::stack<int> x_stack({1, 2, 3});
    x_stack.pop(); x_stack.emplace(4);
    cout << "stack member: " << x_stack.top() << endl;
    // queue
    std::queue<int> x_queue({1, 2, 3});
    x_queue.pop(); x_queue.emplace(4);
    cout << "queue front member: " << x_queue.front() << endl;
    cout << "queue back member: " << x_queue.back() << endl;
    // set
    std::set<int> x_set = {1, 2, 3};
    x_set.emplace(4);
    if (x_set.count(4)) cout << "set count test" << endl;
    // map
    std::map<int, int> x_map({{1, 11}, {2, 22}, {3, 33}});
    x_map.emplace(4, 44);
    if (x_map.count(4)) cout << "map count test" << endl;
    return 0;
}

3.1.1. 介绍

相比于以SVN为代表的集中式版本控制系统，Git所代表的分布式版本控制系统的主要优势体现在不存在“中央服务器”来进行版本记录，每个客户端都保存完整的版本库。

3.1.2. 用法

1. 基本操作
   
   Listing 1: 检视操作

   git status
   git log
   

   Listing 2: 修改操作

   # 添加工作区的某个修改至暂存区
   git add foo.txt
   # 将暂存区提交至本地仓库
   git commit -m "msg"
   # 将本地仓库提交至远程仓库
   git push
   

2. 版本回退
   

   # 回退一次提交
   git reset HEAD^
   # 回退两次提交
   git reset HEAD^^
   # 回退1000次提交
   git reset HEAD~1000
   

3. 放弃修改
   

   1. 如果修改还未加入暂存区

      git checkout -- foo.txt
      

   2. 如果已经加入暂存区但是未提交至本地分支

      # 将修改从暂存区拉回至工作区，之后就是上一种情况了
      git reset HEAD foo.txt
      

   3. 如果已经提交到了本地分支，那么可以通过回退至上一个版本来实现放弃更改。

      git reset HEAD^
      

4. 修改历史
   

   历史提交的修改通常是用rebase操作来进行的：

   Listing 3: 展示提交记录

   # 交互式地展示最近三次提交记录
   git rebase -i HEAD~3
   # 交互式地展示所有历史提交记录
   git rebase -i --root
   

   在rebase界面下我们可以很方便地对提交进行修改，注意某些修改可能会造成冲突，需要手动解决。

   • 改变提交历史对应行的顺序可以直接反映到提交的历史上。
   • 将 pick 修改为 d 以删除某次提交。
   • 将 pick 修改为 r 以修改某次提交信息。
   • 将 pick 修改为 e 可以暂时进入指定的提交进行修改。

   Listing 4: 修改完毕或放弃修改后需要回到原head。

   # 完成本次修改并继续rebase操作
   git rebase --continue
   # 放弃本次修改
   git rebase --abort
   

5. 标签
   

   # 打上标签
   git tag tagName
   # 将标签更新至远程仓库
   git push --tags
   # 删除本地标签
   git tag -d tagName
   # 删除远程仓库标签
   git push --delete origin tagName
   

3.5.1. 基本配置

set imap_user = "name@aol.com"
set imap_pass = "your-password"
set smtp_url = "smtp://name\@aol.com@smtp.aol.com:587/"
set smtp_pass = "your-password"
set folder = "imaps://imap.aol.com:993"
set spoolfile = "+INBOX"

3.5.2. 发送邮件

mutt -s "Subject here" -a foo.png bar.jpg -- recipient1@gmail.com recipient2@gmail.com < foo.txt

3.5.3. 操作邮件

4.1.1. Dired

4.1.2. Speedbar

4.2.1. 可配置选项

4.2.2. 寄存器

5.1.1. Huffman tree

5.2.1. Quicksort

def quickSort(s):
    if len(s) <= 1: return s
    left = []
    right = []
    for x in s[1:]:
        if x <= s[0]: left.append(x)
        else: right.append(x)
    return quickSort(left) + [s[0]] + quickSort(right)

5.2.2. Mergesort

def mergeSort(s):
    # merge two sorted lists to one
    def merge(s1, s2):
        s = []
        i = 0; j = 0
        while i < len(s1) and j < len(s2):
            if s1[i] < s2[j]:
                s.append(s1[i])
                i += 1
            else:
                s.append(s2[j])
                j += 1
        return s + s1[i:] + s2[j:]
    if len(s) <= 1: return s
    m = len(s) // 2
    left = mergeSort(s[:m])
    right = mergeSort(s[m:])
    return merge(left, right)

5.2.3. Heapsort

def heapSort(s):
    # max_heapify
    def siftDown(start, end):
        root = start
        while True:
            child = 2 * root + 1
            # left child
            if child > end:
                break
            # right child
            if child + 1 <= end and s[child] < s[child + 1]:
                child += 1
            if s[root] < s[child]:
                s[root], s[child] = s[child], s[root]
                root = child
            else:
                break
    n = len(s) - 1
    # build max heap
    for start in range(n // 2, -1, -1):
        siftDown(start, n)
    # heapsort
    for end in range(n, 0, -1):
        s[0], s[end] = s[end], s[0]
        siftDown(0, end - 1)
    return s

5.2.4. Bubble sort

void bubbleSort(vector<int>& nums) {
    int n = (int) nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            if (nums[j] > nums[j+1]) swap(nums[j], nums[j+1]);
        }
    }
}

5.2.5. Selection sort

void selection_sort(int * arr, int len) {
    int i, j;
    int tmp;
    for (i = 0; i < len - 1; i++) {
        int min = i;
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        tmp = arr[min];
        arr[min] = arr[i];
        arr[i] = tmp;
    }
}

5.2.6. Tree sort

data Tree a = Leaf | Node (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x Leaf = Node Leaf x Leaf
insert x (Node t y s)
    | x <= y = Node (insert x t) y s
    | x > y  = Node t y (insert x s)

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Node t x s) = flatten t ++ [x] ++ flatten s

treesort :: Ord a => [a] -> [a]
treesort = flatten . foldr insert Leaf

5.2.7. Insertion sort

def insertionSort(s):
    if len(s) <= 1: return s
    for i in range(1, len(s)):
        for j in range(i, 0, -1):
            if s[j] < s[j-1]:
                s[j], s[j-1] = s[j-1], s[j]
            else:
                break
    return s

5.2.8. Shell sort

void shell_sort(int arr[], int len) {
    int gap, i, j;
    int tmp;
    for (gap = len >> 1; gap > 0; gap >>= 1) {
        for (i = gap; i < len; i++) {
            tmp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > tmp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = tmp;
        }
    }
}

5.2.9. Bucket sort

def bucket_sort(datalist):
    buckets = [0] * ((max(datalist) - min(datalist)) + 1)
    for i in range(len(datalist)):
        buckets[datalist[i] - min(datalist)] += 1
    B = []
    for i in range(len(buckets)):
        if buckets[i] != 0:
            B += [i + min(datalist)] * buckets[i]
    return B

5.2.10. Radix sort

import math
def radix_sort(l, radix = 10):
    k = int(math.ceil(math.log(max(l) + 1, radix)))
    for i in range(1, k+1):
        bucket = [[] for _ in range(radix)]
        for v in l:
            bucket[v%(radix**i) // (radix**(i-1))].append(v)
        l = []
        for e in bucket:
            l.extend(e)
    return l

5.2.11. Counting sort

def counting_sort(a):
    k = max(a)
    n = len(a)
    b = [0 for i in range(n)]
    c = [0 for i in range(k + 1)]
    for j in a:
        c[j] = c[j] + 1
    for i in range(1, len(c)):
        c[i] = c[i] + c[i-1]
    for j in a:
        b[c[j] - 1] = j
        c[j] = c[j] - 1
    return b

6.3.1. Principal component analysis

6.3.2. Canonical correlation analysis

6.4.1. Ordinary least squares

1. Approach 1: vector calculus
   

   我们把损失函数看成是一种投影\(L: \mathbb{R}^2 \rightarrow \mathbb{R}\)， 如果它是连续可微的，那么就存在局部最优的一个\(\boldsymbol{w}^{\ast}\)满足 \(\nabla L(\boldsymbol{w}^{\ast}) = \boldsymbol{0}\)，为了求得这个局部最优点:

   \begin{equation*} \begin{split} L(\boldsymbol{w}) &= \|\boldsymbol{X}\boldsymbol{w} - \boldsymbol{y}\|^2_2 \\ &= (\boldsymbol{X}\boldsymbol{w} - \boldsymbol{y})^{\top}(\boldsymbol{X}\boldsymbol{w} - \boldsymbol{y}) \\ &= (\boldsymbol{X}\boldsymbol{w})^{\top}\boldsymbol{X}\boldsymbol{w} - (\boldsymbol{X}\boldsymbol{w})^{\mathrm{T}}\boldsymbol{y} - \boldsymbol{y}^{\mathrm{T}}\boldsymbol{X}\boldsymbol{w} + \boldsymbol{y}^{\mathrm{T}}\boldsymbol{y} \\ &= \boldsymbol{w}^{\top}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{X}\boldsymbol{w} - 2\boldsymbol{w}^{\mathrm{T}}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} + \boldsymbol{y}^{\mathrm{T}}\boldsymbol{y} \end{split} \end{equation*}

   对其求微分：

   \begin{equation*} \begin{split} \nabla L(\boldsymbol{w}) &= \nabla_{\boldsymbol{w}}(\boldsymbol{w}^{\top}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{X}\boldsymbol{w} - 2\boldsymbol{w}^{\mathrm{T}}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} + \boldsymbol{y}^{\mathrm{T}}\boldsymbol{y}) \\ &= \nabla_{\boldsymbol{w}}(\boldsymbol{w}^{\top}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{X}\boldsymbol{w}) - 2\nabla_{\boldsymbol{w}}(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{y}) + \nabla_{\boldsymbol{w}}(\boldsymbol{y}^{\mathrm{T}}\boldsymbol{y}) \\ &= 2\boldsymbol{X}^{\top}\boldsymbol{X}\boldsymbol{w} - 2\boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} \end{split} \end{equation*}

   注意这里的\(\boldsymbol{X}^{\top}\boldsymbol{X}\)是对称矩阵，所以其二次型 （quadratic form）的微分很容易求得。令\(\nabla L(\boldsymbol{w}) = 0\)，得 到最优点\(\boldsymbol{w}^{\ast}\)满足:

   \begin{equation*} \boldsymbol{X}^{\top}\boldsymbol{X}\boldsymbol{w}^{\ast} = \boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} \end{equation*}

   到这里，如果\(\boldsymbol{X} \in \mathbb{R}^{n \times d}\)是列满秩的（因为 我们假设\(n \geq d\)，所以列满秩的含义其实就是列向量线性无关），那么可 以推出\(\boldsymbol{X}^{\top}\boldsymbol{X} \in \mathbb{R}^{d \times d}\)是满 秩的，那么我们就可以得到最优点:

   \begin{equation*} \boldsymbol{w}^{\ast} = (\boldsymbol{X}^{\top}\boldsymbol{X})^{-1}\boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} \end{equation*}

   该最优点能成为全局最小值点（因为微分为零的点可能是局部最优点，也可能是 最大值点，也可能是鞍点）是由目标函数\(L\)的凸（convex）来保证的，为了 证明\(L\)的凸性，可以计算它的海森矩阵（Hessian）:

   \begin{equation*} \nabla^2 L(\boldsymbol{w}) = 2\boldsymbol{X}^{\top}\boldsymbol{X} \end{equation*}

   由于:

   \begin{equation*} \forall \boldsymbol{w}, \boldsymbol{w}^{\top}(2\boldsymbol{X}^{\mathrm{T}}\boldsymbol{X})\boldsymbol{w} = 2(\boldsymbol{X}\boldsymbol{w})^{\mathrm{T}}\boldsymbol{X}\boldsymbol{w} = 2\|\boldsymbol{X}\boldsymbol{w}\|^2_2 \geq 0 \end{equation*}

   也就是说\(L\)的海森矩阵是半正定的（positive semi-definite），这就证明 了\(L\)是凸的，也就证明了局部极值点\(\boldsymbol{w}^{\ast}\)就是全局最小值 点。注意，因为海森矩阵是半正定而非正定，所以一旦海森矩阵存在零特征值， 那么\(\boldsymbol{X}^{\top}\boldsymbol{X}\)就不可逆，在这种情况下，不代表全局 最优解（最小值）不存在，\(\boldsymbol{X}^{\top}\boldsymbol{X} \boldsymbol{w}= \boldsymbol{X}^{\top}\boldsymbol{y}\)的解总是存在的，只不过只有当海森矩阵为正 定的时候这个解才是唯一的，如果是半正定的，那么解就有无穷多个。

2. Approach 2: Orthogonal projection
   

   我们先把最小二乘放一放，来看一下正交投影（orthogonal projections）。

   如果\(S\)是一个内积空间（inner product space）\(V\)的子空间，那么对于\(\forall \boldsymbol{v} \in V\)，总可以有唯一的分解形式：\(\boldsymbol{v} = \boldsymbol{v}_S + \boldsymbol{v}_{\perp}\)，其中\(\boldsymbol{v}_S \in S\)，\(\boldsymbol{v}_{\perp} \in S^{\perp}\).

   基于以上分解，可以定义内积空间\(V\)在其子空间\(S\)上的正交投影：\(P_S\)，它有一个重要性质：

   \begin{equation*} \|\boldsymbol{v} - \boldsymbol{s}\| \geq \|\boldsymbol{v} - P_S\boldsymbol{v}\|, \, \forall \boldsymbol{s} \in S \end{equation*}

   等号只在\(\boldsymbol{s} = P_S \boldsymbol{v}\)的时候取得，即有：

   \begin{equation} \label{org3e141c2} P_S\boldsymbol{v} = \operatorname*{arg\,min}_{\boldsymbol{s} \in S}\|\boldsymbol{v} - \boldsymbol{s}\| \end{equation}

   该性质证明如下：

   根据毕达哥拉斯定理（Pythagorean theorem），有

   \begin{equation*} \|\boldsymbol{v} - \boldsymbol{s}\|^2 = \|\boldsymbol{v} - P_S\boldsymbol{v} + P_S\boldsymbol{v} - \boldsymbol{s}\|^2 = \|\boldsymbol{v} - P_S\boldsymbol{v}\|^2 + \|P_S\boldsymbol{v} - \boldsymbol{s}\|^2 \geq \|\boldsymbol{v} - P_S\boldsymbol{v}\|^2 \end{equation*}

   等号只在\(\boldsymbol{s} = P_S\boldsymbol{v}\)时取得。两边求平方根即得到\(\|\boldsymbol{v} - \boldsymbol{s}\| \geq \|\boldsymbol{v} - P_S\boldsymbol{v}\|\).

   我们回到最小二乘问题：

   \begin{equation*} \boldsymbol{w}^{\ast} = \operatorname*{arg\,min}_{\boldsymbol{w}}\|\boldsymbol{X}\boldsymbol{w} - \boldsymbol{y}\|^2_2 \end{equation*}

   稍做变换：

   \begin{equation*} \begin{split} \boldsymbol{w}^{\ast} &= \operatorname*{arg\,min}_{\boldsymbol{w} \in \mathbb{R}^d} \|\boldsymbol{X}\boldsymbol{w} - \boldsymbol{y}\|^2_2 \\ &= \operatorname*{arg\,min}_{\boldsymbol{X}\boldsymbol{w} \in range(\boldsymbol{X})}\|\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}\| \end{split} \end{equation*}

   结合等式\eqref{org3e141c2}，上式可以看作\(\boldsymbol{y}\)所在空间在\(\boldsymbol{X}\boldsymbol{w}\)所在空间（即\(range(\boldsymbol{X})\)）上的正交投影，考虑等号成立条件，得到：

   \begin{equation*} \boldsymbol{X}\boldsymbol{w}^{\ast} = P_{range(\boldsymbol{X})}\boldsymbol{y} \end{equation*}

   再结合定理1，可以推出\(\boldsymbol{y} - P_{range(\boldsymbol{X})} \boldsymbol{y} \perp range(\boldsymbol{X})\)，也就是\(\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}^{\ast} \in null(\boldsymbol{X}^{\top})\). ⁴ 即可以推出：

   \begin{equation*} \begin{aligned} \boldsymbol{X}^{\top} (\boldsymbol{y} - \boldsymbol{X}\boldsymbol{w}^{\ast}) = \boldsymbol{0} \\ \boldsymbol{X}^{\top}\boldsymbol{X}\boldsymbol{w}^{\ast} = \boldsymbol{X}^{\mathrm{T}}\boldsymbol{y} \end{aligned} \end{equation*}

6.4.2. Ridge regression

6.4.3. Maximum likelihood estimation

6.4.4. Maximum a posteriori

6.5.1. Naive Bayes

6.5.2. Support Vector Machines

1. 从函数间隔到几何间隔
   

   首先考虑线性可分的情况。定义带有参数\(\boldsymbol{w},b\)的超平面\(\boldsymbol{w}^{\top}\boldsymbol{x} + b\)，给定第\(i\)个测试样本\((\boldsymbol{x}^{(i)}, y^{(i)})\)，那么其到该平面到函数间隔（Functional Margin）为：

   \[ \hat{\gamma}^{(i)} = y^{(i)}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)} + b) \]

   可以发现，如果对超平面对参数\(\boldsymbol{w}, b\)等比例地放大缩小，其实际作用不变（即不影响分类结果），但是函数间隔会随之变化，所以用如此定义的函数来衡量样本点到某分类超平面的“距离”并不可靠。因此，考虑将超平面等式归一化，因此就有了：

   \[ \gamma^{(i)} = y^{(i)}((\frac{\boldsymbol{w}}{\left\|\boldsymbol{w}\right\|})^{\top}\boldsymbol{x}^{(i)} + \frac{b}{\left\|\boldsymbol{w}\right\|}) \]

   这个经归一化后的函数间隔被成为几何间隔（Geometric Margin），其可以很好地衡量样本点到某分类超平面到“距离”。

2. 最优化问题
   

   有了对样本点到超平面的“距离”的定义（可以理解成某样本点被正确分类的信心），就可以通过使离分类超平面最近的点到分类超平面的距离最大来求得一个最佳的分类超平面，于是就有了下面的最优化问题：

   \begin{equation*} \begin{aligned} \max_{\gamma, \boldsymbol{w}, b} \;& \gamma \\ \text{s.t.} \;& y^{(i)}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)} + b) \geq \gamma , \; i = 1,\dots, m \\ \;& \left\|\boldsymbol{w}\right\| = 1. \end{aligned} \end{equation*}

   再进一步转化（个人感觉从归一化函数间隔的角度上来理解的话可以直接得到下面的形式）：

   \begin{equation*} \begin{aligned} \max_{\hat{\gamma}, \boldsymbol{w}, b} \;& \frac{\hat{\gamma}}{\left\|\boldsymbol{w}\right\|} \\ \text{s.t.} \;& y^{(i)}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)} + b) \geq \hat{\gamma}, \; i = 1, \dots, m. \end{aligned} \end{equation*}

   由于函数间隔可以任意缩放而不影响结果，因此不妨设\(\hat{\gamma} = 1\)，则优化目标变为了\(\max_{\boldsymbol{w}, b}\,\frac{1}{\left\|\boldsymbol{w}\right\|}\)，为方便后续求解，一般写成如下形式：

   \begin{equation*} \begin{aligned} \min_{\boldsymbol{w}, b} \;& \frac{1}{2}{\left\|\boldsymbol{w}\right\|}^2 \\ \text{s.t.} \;& y^{(i)}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)} + b) \geq 1, \; i = 1,\dots,m. \end{aligned} \end{equation*}

   可以证明，该最优化问题的解是存在且唯一的。

3. 松弛变量
   

   由于在实际情况下样本可能无法做到线性可分，于是便引入了松弛变量（slack variables），其思想即是允许某些点到分类超平面的距离小于最优的分类间隔（甚至误分类），具体的优化问题可以表示成：

   \begin{equation*} \begin{aligned} \min_{\boldsymbol{w}, b} \;& \frac{1}{2}{\left\|\boldsymbol{w}\right\|}^2 + C\Sigma_{i=1}^m \xi^{(i)} \\ \text{s.t.} \;& y^{(i)}(\boldsymbol{w}^{\top}\boldsymbol{x}^{(i)} + b) \geq 1 - \xi^{(i)}, \; \xi^{(i)} \geq 0. \end{aligned} \end{equation*}

   其中\(\xi^{(i)}\geq 0\)即松弛变量，其允许某些样本点不满足严格的间隔约束（此时\(0 \leq \xi^{(i)} \leq 1\)）或被误分类（此时\(\xi^{(i)} > 1\)）。而参数\(C > 0\)用于控制“最大化间隔”与“最小化松弛量”之间的权重。

4. 核函数
   

   除了采用线性分类器（即由线性函数定义的分类超平面），SVM还可以通过把数据点映射到高维空间以得到在原始空间中的非线性分类器。而不管在何种空间，我们定义分类器需要的都是点与面的距离而不是具体的映射函数，前者可以通过空间中的点积求得。我们定义从原始空间\(\mathcal{X}\)到特征空间\(\mathcal{F}\)的非线性映射\(\phi: \mathcal{X} \to \mathcal{F}\)，于是可以定义核函数（kernel function）以接收原始空间中的点为输入来计算其在特征空间中的点积：

   \[ K(\boldsymbol{x}, \boldsymbol{x}^\prime) = \phi(\boldsymbol{x})^{\top}\phi(\boldsymbol{x}^\prime). \]

   举例来说，以下分别为多项式核（polynomial kernel）及高斯核函数(Gaussian kernel)：

   \[ K_{\text{polynomial}}(\boldsymbol{x}, \boldsymbol{x}^\prime) = (\boldsymbol{x}^{\top}\boldsymbol{x}^{\prime} + 1)^d \]

   \[ K_{\text{Gaussian}}(\boldsymbol{x}, \boldsymbol{x}^{\prime}) = \exp(-\gamma\left\|\boldsymbol{x} - \boldsymbol{x}^{\prime}\right\|^2) \]

6.5.3. Random Forests

1. 参考资料
   
   • Random Forests for Complete Beginners

6.6.1. K-means