初雪 2018-4-4 晚
找了近一个月的时间都没有找到一款合适的笔记，最终我选择了Visual Code + Vim + Markdown + Mega。笔记内容链接在个人描述页面
忽然想学一波大数据方面的东西，但是我不想搞人工智能，例如NLU, CV等，这些对于人来说很简单的事。关于人工智能，我仍然坚持当前基于统计的方法无法实现真正的人工智能，不如花时间来玩一玩大数据的东西。以下内容参考李航的«统计学习方法»，重在理解。
基础
我眼中的统计学习
三要素(模型，策略，方法)就不说了，死扣定义没什么意思，提一下我理解的统计学习。由于放弃了许多数学上标准的定义，所以在描述上会存在偏差。
-
目标 预测，从一堆数据中预测出某些具有价值的东西。
-
本质 设想一个座标系中，给定一系列点$ (x, y) $，寻找一个函数$ f(x) $ 使 $ y = f(x) $，不仅对于已给出的点满足，对于尚未给出的点同样满足。 高中人教版数学中提到的最小二乘法即时最简单的统计学习，这个方法中，我们知道$ y = kx + b $，在真正的统计学习方法中，我们是不知道这些内容的，只有一系列点$ (x, y) $，而且座标系不一定是平面直角座标系，即 $$ x = \left[\begin{matrix}x_1 & x_2 & x_3 \cdot \cdot \cdot x_n\end{matrix} \right] $$，同时f(x)不再是标准的函数，由于x的输入或者测量误差，可能对于某些x并不满足f(x)。
概念
虽然概念重在理解，但是将一个概念用清除的数学公式表示出来还是有必要的。许多科学家厉害就厉害在将人们脑海中某些定性的概念定量的表示出来。记不住这些公式，看书都很困难。
- 指示函数 $$ f(x) = \begin{cases} 1 & \text{x = y} \ 0 & x \neq y \end{cases}$$
- 符号函数 $$ f(x) = sign(x) = \begin{cases} 1 & \text{x > 0} \ 0 & x = 0 \ -1 & x < 0 \end{cases}$$
- 风险函数 寻找f(x)，由于f(x)可能不唯一，所以我们要找出最好的f(x)来，什么是最好呢，这里用一个定量值来表示。 $$ \mathop{\min}\limits_{f \in F}\frac{1}{N} \sum_{i=1}^NL(y_i, f(x_i))$$ 其中L为损失函数，常用的有如下几个
- 0-1损失函数 即指示函数
- 平方损失函数 $$ L(Y, f(X)) = (Y - f(X))^2 $$
- 绝对损失函数 $$ L(Y, f(X)) = |Y - f(X)|$$
- 对数损失函数 $$ L(Y, f(X)) = -logP(Y|X) $$
- 过拟合
当样本容量很小的时候，容易产生过拟合现象。
假设二维直角座标系中，对于给定的n个点$(x, y)$，可以唯一确定一个n-1阶的方程$ f(x) = kx^{n-1} + …$，使所有给定的点都在此曲线上。这就会产生过拟合现象。
过拟合本质是将给出的点中的一些共有却不必要的特征当作某个共性，例如给出了5个白人，计算机寻找用于判断是否为人的f(x)的时候，错将肤色白当成人的一个共性。
所以，在过拟合的基础上，将风险函数升级成如下方程。
$$ Rsrm(f) = \frac{1}{N}\sum_{i=1}^NL(y_i, f(x_i)) + \lambda J(f)$$
J(f)为模型的复杂度，模型越复杂，复杂度越高。
复杂度可以简单的认为x的阶数。
感知机
设想在一维的座标轴中有两堆点，可以用一个点将这两堆点分开，求满足此要求的点。将一维的座标轴推广到n维，就是感知机问题。本质是一个分类问题，对于不同的x，y的值只有两个1或者-1。即 $ y = sign(f(x)) $，现在求f(x)。
假设x是二维的, $ x = (x^{(1)}, x^{(2)}) $，有如下图
此图不同与二维直角座标系，二维直角座标系中x是一维的，现在x是二维的，所以y的值并没有在座标中体现，仅仅用不同的点表示。 我们的目标是求一条直线，将点分开。看图即可知道直线并不是唯一的。 对于此座标系中的任一条直线，有$$ w \cdot x + b = 0 $$，对于二维的向量来说$$ w \cdot x = w^{(1)} * x^{(1)} + w^{(2)} * x^{(2)} $$ 所以我们的目标即求$ w $ 和 $ b $。
现在定义损失函数，损失函数的选择是误分类点到此直线的距离。在此座标系中，x到此直线的距离为 $$ \frac {1}{\left|W\right|} |w \cdot x_0 + b| $$ $||W||$是$w$的$L_2$范数。
对于误分类的点 $-y_i(w \cdot x_i + b) > 0$ 所有误分类点到超平面即f(x)距离之和为$$ -\frac{1}{\left|w\right|}\sum_{x_i \in {M}} y_i (w \cdot x_i + b)$$ 不考虑$\frac{1}{\left|w\right|}$，得到损失函数 $$ L(w, b) = -\sum_{x_i \in {M}}y_i (w \cdot x_i + b)$$
损失函数是非负的，如果没有误分类点，损失函数值为0，即最小值为0。
算法
输入: $ T = {(x_1, y_1), (x_2, y_2), \cdot \cdot \cdot, (x_N, y_N)}$ 输出: $ w, b$ 目的: $$ minL(w, b) = min-\sum_{x_i \in {M}} y_i (w \cdot x_i + b)$$
由于$ minL(w, b) = 0 $，所以本质即找到一个超平面将所有点正确分类。现在假设这群点是可分的，所以一定存在这个超平面。正实例点集构成的凸壳和负实例点集构成的凸壳不相交是线性可分的充分必要条件。
为求$w,b$，给出一种迭代方法。 任选$w_0, b_0$，得到超平面，$w_0 \cdot x + b = 0$ 从给定的点集合中，选出一个误分类的点 $(x, y)$ 令$$ w \gets w + \eta y_ix_i $$ $$ b \gets b + \eta y_i $$ 其中 $ \eta $为步长，又称为学习率。
现在证明此种方法可以得到需要的$w, b$。以下为独立思考所得，未经验证。
(1) 证明: 对于误分类点$(x_1, y_1)$，设原$(w ,b)$为$(w_0, b0)$经过有限次迭代后，可以将误分类点正确分类。
$$ a_0 = y_1(w_0 \cdot x_1 + b) < 0 $$ $$w_1 \gets w_0 + \eta y_1x_1 $$ $$ b_1 \gets b_0 + \eta y_1 $$ 所以 $$ a_1 = y_1(w_1 \cdot x_1 + b) = a_0 + \eta y_1^2{(x_1^2 + 1)}$$ 如果 $$ a_1 > 0 $$得解，否则对于$a_k$得解。
(2) 证明: 如果对于某个误分类点可以通过次方法将其正确分类，则对于所有误分类点运用此方法，可以得到正确的$(w,b)$。 此迭代法的本质是将$w$更改，$w$即为此超平面的法向量，对于所有误分类的点，$w$更改的方向是一致的，因为不可能对于同一堆点，在此超平面两侧都有误分类的点。同理，对于不同堆的点，即$y_i > 0$中误分类的点和$y_i < 0$误分类的点应该在分布在此直线的两侧。
对偶形式
对偶形式: 将 (w) 和$b$表示为$(x_i, y_i)$的线性组合，即\w = f(x, y), b = f(x, y) 假设$w, b$初始值均为0，根据上面的迭代算法，假设对于误分类点$(x_i, y_i)$经过了$n$次迭代，共有N个误分类点则最终(\varphi = \dfrac{1+\sqrt5}{2}= 1.6180339887…) $$ w = \sum_{i=1}^{N}a_iy_ix_i$$ $$ b = \sum_{i=1}^Na_iy_i $$ 这里 $ a_i = n_i \eta $
所以 对偶形式的算法如下。 输入: $ T = {(x_1, y_1), (x_2, y_2), \cdot \cdot \cdot, (x_N, y_N)}$ 输出: $a, b$ 其中 $a = (a_1, a_2, \cdot \cdot \cdot, a_N)^T $ 目的: $f(x) = sign( \sum_{j=1}^Na_jy_jx_j \cdot x+b)$ (1) $a \gets 0$, $b \gets 0$ (2) 选取数据$(x_i, y_i)$ (3) 如果$y_i(\sum_{j=1}^{N}a_jy_jx_j \cdot x_i + b) \le 0 $ $$ a_i \gets a_i +n $$ $$ b \gets b + \eta y_i $$ (4) 转至(2)直到无误分类数据。