端口映射

远程端口映射到本地

config文件里可以配置

1
2
3
4

Host {{name}}
    HostName {{remote-ip}}
    User {{username}}
    LocalForward {{local-ip}}:{{local-port}} {{remote-ip}}:{{remote-port}}

引入

SVM是一种常用的分类模型，其目标是寻找一个能将所有样本点准确划分的分离超平面（即分离超平面的两侧分别对应两个类别），优化目标是最大化几何间隔。为了能够应对线性不可分的数据集，引入了核技巧，其核心是将样本点映射到一个高维空间，认为低维空间不可分的数据集总能在高维空间中找到一个分离超平面将他们区分开来。

原理

假定我们有如下数据集， \[ D=\lbrace (x_{11}, x_{12}, \cdots, x_{1d}, y_1), \cdots, (x_{n1}, x_{n2}, \cdots, x_{nd}, y_n) \rbrace \] 数据集中每个样本\(i\)都有\(d\)个特征，\(y_i\)表示样本\(i\)所属的类别。简单起见，我们以二分类问题为例，此时有\(y_i\in \lbrace0, 1\rbrace\)。

函数间隔和几何间隔

我们用\(\vec w\cdot \vec x+b\)来表示一个分离超平面，并作如下规定：若\(y_i=+1\)，则\(\vec w\cdot \vec x_i+b > 0\)；若\(y_i=-1\)，则\(\vec w\cdot \vec x_i+b < 0\)。

显然，对于任意的\(\vec x_i\)，都有\(y_i(\vec w\cdot \vec x_i+b) > 0\)。这里，\(y_i(\vec w\cdot \vec x_i+b)\)就是函数间隔。函数间隔描述了两件事情：

1. 函数间隔前的符号反映了样本是否被正确分类。如果大于0，那么这个样本就被正确分类了；
2. 函数间隔的绝对值描述了这个样本属于当前类的确信度，绝对值越大确信度越高。

因此，我们可以用函数间隔来评价分离超平面的优劣，更进一步，我们用数据集中的最小函数间隔来评价分离超平面的优劣。我们希望找到最小函数间隔尽可能大的分离超平面。

但是函数间隔有一个问题，当我们成倍扩大\(\vec w\)和\(b\)时，函数间隔也会随之变大，这显然不是我们想要的，所以引入几何间隔的概念： \(\frac{y_i(\vec w\cdot \vec x_i+b)}{||\vec w||_2}\)。可见，相比于函数间隔，几何间隔用\(\vec w\)的2范数做了归一化。（在几何意义上，\(\frac{|\vec w\cdot \vec x_i+b|}{||\vec w||_2}\)表示样本点到分离超平面的距离，这大概就是几何间隔的由来）。

给定数据集D，我们定义分离超平面关于数据集D的几何间隔为所有样本点距离分离超平面的最小几何间隔，即 \[ \gamma = \min_{i=1,2,\cdots,N}{\frac{y_i(\vec w\cdot \vec x_i + b)}{||\vec w||_2}} \]

决策函数

如果我们找到了想要的超平面，即 \[ (\vec w^*, b^*) = \underset{\vec w, b}{\operatorname{argmin}}\gamma \] 那么决策函数可以写成\(sign(\vec w^*\cdot \vec x_i+b^*)\)

支持向量和间隔

令\(\beta > 0\)，如果存在样本点\(\vec x_j\)使得下式中的等号成立 \[ \left \lbrace \begin{align*} \vec w\cdot \vec x_a+b &\ge \beta,\ y_a = 1 \\ \vec w\cdot \vec x_b+b &\le -\beta,\ y_b = -1 \end{align*} \right . \] 那么这些样本点对应的特征向量就被称之为支持向量。间隔定义为两个异类支持向量到分离超平面的距离，即 \[ \gamma = \frac{2\beta}{||\vec w||_2} \]

间隔最大化

间隔最大化意味着，找到的分离超平面能以最大的确信度将样本集分为两类。我们的优化目标可以表示为 \[ \begin{align*} \max_{\vec w,b}\ &\frac{2\beta}{||\vec w||_2} \\ s.t.\ &y_i(\vec w\cdot \vec x_i+b) \ge \beta\ \ i = 1,2,\cdots,N \end{align*} \] 显然，\(\beta\)的取值和优化目标无关，上式可以重写为 \[ \begin{align*} \min_{\vec w,b}\ &{\frac{1}{2}||\vec w||^2} \\ s.t.\ &y_i(\vec w\cdot \vec x_i+b) \ge 1\ \ i = 1,2,\cdots,N \end{align*} \]

对偶问题

应用拉格朗日乘子法，将约束写入到目标函数中，得到 \[ L(\vec w,b,\vec \alpha) = \frac{1}{2}||\vec w||^2 + \sum_i^N{\alpha_i(1 - y_i(\vec w\cdot \vec x_i+b))} \tag{1} \] 原问题的解等价于 \[ \max_{\alpha}{\min_{\vec w,b}\ {L(\vec w,b,\vec \alpha)}} \] 首先求解极小化问题，得： \[ \begin{align*} \triangledown L_\vec w = \vec w - \sum_i^N{\alpha_i y_i \vec x_i} \\ \triangledown L_b = -\sum_i^N{\alpha_i y_i} \end{align*} \] 极值一定在一阶导数导数为零处取到，因此令上式为零后，得 \[ \begin{align*} 0 = \triangledown L_b &= -\sum_i^N{\alpha_i y_i} \\ 0 = \triangledown L_\vec w &= \vec w - \sum_i^N{\alpha_i y_i \vec x_i} \\ \vec w &= \sum_i^N{\alpha_i y_i \vec x_i} \end{align*} \] 将\(\vec w = \sum_i^N{\alpha_i y_i \vec x_i}\)和\(0= \sum_i^N{\alpha_i y_i}\)带入(1)得 \[ \begin{align*} L(\vec w,b,\vec \alpha) &= \frac{1}{2}||\sum_i^N{\alpha_i y_i \vec x_i}||^2 + \sum_i^N{\alpha_i(1 - y_i(\sum_j^N{\alpha_j y_i \vec x_j}\cdot \vec x_i+b))} \\ &= \frac{1}{2}||\sum_i^N{\alpha_i y_i \vec x_i}||^2 + \sum_i^N{\alpha_i} -\sum_i^N{\alpha_i y_i(\sum_j^N{\alpha_j y_j \vec x_j}\cdot \vec x_i+b))} \\ &= \frac{1}{2}||\sum_i^N{\alpha_i y_i \vec x_i}||^2 + \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i y_i \alpha_j y_j \vec x_j\cdot \vec x_i}}+ b\sum_i^N{\alpha_i y_i} \\ &= \frac{1}{2}||\sum_i^N{\alpha_i y_i \vec x_i}||^2 + \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i \alpha_j y_i y_j \vec x_i\cdot \vec x_j}} \tag{2} \end{align*} \] (2)最后第一项和第三项，应该是不能直接合并的。当\(i \ne j\)时，该项存在于第三项中但是第一项里没有。但从求极值的角度来说，(2)等价于 \[ \begin{align*} &\max_{\alpha}\ L(\vec w,b,\vec \alpha) \\ \Leftrightarrow &\max_{\alpha}\ \frac{1}{2}||\sum_i^N{\alpha_i y_i \vec x_i}||^2 + \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i \alpha_j y_i y_j \vec x_i\cdot \vec x_j}} \\ \Leftrightarrow &\max_{\alpha}\ \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i \alpha_j y_i y_j \vec x_i\cdot \vec x_j}} \tag{3} \\ &\ \ s.t.\ \sum_i^N{\alpha_i y_i} = 0 \end{align*} \]

参数计算

由KKT条件可知，当 \[ \alpha_i(1 - y_i(\vec w \cdot \vec x_i+b)) = 0 \] 时，对偶问题和原问题取到极值。由于\(\alpha_i > 0\)，所以当且仅当\(1 - y_i(\vec w \cdot \vec x_i+b) = 0\)时上式等号成立，即\(\vec x_i\)为支持向量时等号成立。因此，线性SVM的解为 \[ \vec w = \sum_{i\in SV}^N{\alpha_i y_i \vec x_i} \tag{4} \] 将(4)带入\(1 - y_i(\vec w \cdot \vec x_i+b) = 0\)，考虑到$y_i -1, 1 $，所以\(1 / y_i = y_i\)，得到\[ b = y_i - \vec w \cdot \vec x_i = y_i - \sum_{i\in SV}^N{\alpha_i y_i \vec x_i} \cdot \vec x_i \] 实践中用所有支持向量算出来的b的均值作为最终解。

核技巧

假设样本是线性不可分的，那么线性SVM就无法找到分离超平面，此时就需要使用核技巧，简答来说就是将样本的特征空间向高维空间做映射。假设我们使用函数\(\Phi\)对样本的特征空间做映射\(R^d \rightarrow R^{\hat{d}}\)，那么(3)可表示为 \[ \begin{align*} &\max_{\alpha}\ \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i \alpha_j y_i y_j \Phi(\vec x_i)\cdot \Phi(\vec x_j) }} \\ &\ \ s.t.\ \sum_i^N{\alpha_i y_i} = 0 \end{align*} \tag{5} \] 从(5)中可知，即使我们不知道映射函数\(\Phi\)的具体形式，只需要算出\(\Phi(\vec x_i)\cdot \Phi(\vec x_j)\)即可。假设我们能找到函数\(\kappa\)满足 \[ \kappa(\vec x_i\cdot \vec x_j) = \Phi(\vec x_i)\cdot \Phi(\vec x_j) \] 那么我们就能用函数\(\kappa\)实现向高维空间映射的同时还维持计算复杂度依然是\(O(d)\)。那么(5)就可写为 \[ \begin{align*} &\max_{\alpha}\ \sum_i^N{\alpha_i} -\sum_i^N{\sum_j^N{\alpha_i \alpha_j y_i y_j \kappa(\vec x_i\cdot \vec x_j) }} \\ &\ \ s.t.\ \sum_i^N{\alpha_i y_i} = 0 \end{align*} \tag{5} \] 常见的核函数有

引入

逻辑斯特回归的输入是样本的特征，输出是样本属于正例的概率，可见他的输出是连续值。设定一个阈值之后，逻辑斯特回归就可以作为一个分类模型来使用。

原理

形式

假定我们有如下数据集， \[ D=\lbrace (x_11, x_12, \cdots, x_1d, y_1), \cdots, (x_n1, x_n2, \cdots, x_nd, y_n) \rbrace \] 数据集中每个样本\(i\)都有\(d\)个特征，\(y_i\)表示样本\(i\)所属的类别。简单起见，我们以二分类问题为例，此时有\(y_i\in \lbrace0, 1\rbrace\)。

连续值的离散化

考虑线性回归模型\[w^Tx+b\]，模型输出为连续值，值域为\(R\)，显然无法直接得到分类结果，因此我们需要对连续值做离散化处理。

离散化处理的一种方式是使用阶跃函数，但是阶跃函数的问题在于难以优化，导致很难找到一个合适的参数\(w\)。

如果我们可以找到一个自变量的定义域且值域为\((0,1)\)为\(R\)的可微凸函数，那么我们就可以用这个函数来将线性回归模型的输出映射到\((0,1)\)中，并认为映射后的值为某一个事件发生的概率。满足这个条件的其中一个函数为逻辑斯特函数，即 \[ y=\frac{1}{1+e^{-x}} \]

几率

将逻辑斯特函数和线性回归模型组合在一起，得到 \[ y=\frac{1}{1+e^{-(w^Tx+b)}} \] 令\(y=P(Y=1|x)\)，即\(y\)表示样本\(x\)属于类别1的概率，两边同取对数得 \[ \begin{align} y&=\frac{1}{1+e^{-(w^Tx+b)}} \\ ln\frac{y}{1-y}&=w^Tx+b \end{align} \] 几率定义为事件发生的概率比上事件不发生的概率。可见，线性模型的输出表示的是对数几率。

损失函数

极大似然估计

想要求得参数\(w\)，那么可以用极大似然估计法得到对数似然函数。令\(p(x_i)=P(Y=1|x_i)\)，那么\(1-p(x_i)=P(Y=0|x_i)\)，则有 \[ \begin{align} L(w)&=\prod_i^n{p(x_i)^{y_i}(1-p(x_i))^{1-y_i}}\\ ln(L(w))&=\sum_i^n{(y_ip(x_i)+(1-y_i)(1-p(x_i)))} \end{align} \] 可见，对数似然函数和我们熟悉的交叉熵损失互为相反数，所以最小化交叉熵损失和最大化对数似然函数是一致的，最小化交叉熵损失就是在做极大似然估计。至于优化方法，可以用梯度下降、牛顿法、拟牛顿法等常见优化方法。

其他

均方差函数

具体推导过程可参考Why not Mean Squared Error(MSE) as a loss function for Logistic Regression?，总计来说就是使用交叉熵可以保证优化目标是个凸函数（因此局部最优解就是局部最优解），但是用均方差函数得到的优化目标是个非凸函数，往往会陷入到局部最优解中。

其他

Noise2Noise

数据库

计算机网络

操作系统

基础知识和面试题

姿态检测的各项指标定义和计算