数值计算的误差
误差来源
模型误差： 将实际问题时出现的误差。因为实际问题转化为数学模型时会省略很多东西，因此难免会有误差。
观测误差： 在测量一些物理量（长度等）时产生的误差。
截断误差： 求近似解产生的误差。例如泰勒公式使用若干项进行求解就会舍去后面的项
舍入误差： 使用计算机计算时，由于计算机表达位数有限，因此会产生舍入误差
误差和有效数字假设x为准确值， $x^$为x的一个近似值，$e^ = x^ - x$为近似值的*绝对误差，简称误差。
通常我们不知道准确值，但是我们有时候我们可以估计出一个上限，记作$\varepsilon^$，称为*误差限
即 $|x^ - x| \le \varepsilon^$
相对误差： 绝对误差与真实值的比值,记作$e_r^*$
e_r^* = \frac{e^*}{x^*} = \frac{x^* - x}{x}通常情况下我们无法获得x，因此相对误差可以写成$\frac{x^ - x}{x^ }$
相对误差也有误差限，记作$\varepsilon_r^$,即$\varepsilon_r^ = \frac{\varepsilon^}{x^}$
有效数字定义 ...
数值积分
基础概念首先需要知道积分的含义： 在二重积分中，积分可以粗略的认为是求面积。由于我们是离散的点，因此常见的做法是使用矩形或梯形来逼近这块面积，如果采样点无限多，那么通过这种方法得出的结果就是精确的。
但是这种方法计算代价过大，我们可以利用这些点做插值来拟合曲线，再对插值函数进行积分得到更好的结果。
代数精度定义： 如果某个求积公式对于次数不超过m的多项式均能准确的成立，但对于m+1次的多项式不能准确的成立，则称该求积公式有m次的代数精度
这也就要求$\sum A_k = x^k$
也就是要求下式都成立
\left\{\begin{matrix}
\sum A_k & = & b-a\\
\sum A_k x_k & = & \frac{1}{2}(b^2 - a^2 )\\
\vdots & &\\
\sum A_k x_k^m & = & \frac{1}{m+1} (b^{m+1} - a^{m+1})
\end{matrix}\right.余项定义：
\begin{aligned}
R[f] &= \int_a^b f(x) dx - \sum_{k=0}^{n}A_ ...
上下文无关语言
上下文无关文法 上下文无关文法(CFG)是一个四元组(V, $\sum$, R, S)
V是变元
$\sum$是终结符
R: 规则，每条规则都由左边的变元和右边变元和终结符组成的字符串构成
S： 起始节点
例如： S -> aSb | SS | $\varepsilon$
二义性二义性指的是一个字符串可能有多种解析方式
.
导致二义性的原因：
解析顺序不同，可能最后生成的解析树是相同的。
最后生成的解析树不同
为了消除第一种导致二义性的可能，可以使用最左推导，即每次都从最左边的变元开始解析。
二义性定义： 一个字符串可以被两个乃至更多的最左推导生成。
乔姆斯基范式一个上下文无关语言的乔姆斯基范式的形式为：
A -> BC
B -> a
S -> $\varepsilon$
证明任何上下文无关文法都可以转换成乔姆斯基范式
一个上下文无关文法可以转换成乔姆斯基范式的上下文无关文法
转换分为四个步骤：
添加一个起始变量 添加一个$S_0$和一条规则$S_0 -> S$,其中S是原来的起始变量。这条规则是为了让起始变量不出现在右边
消除 ...
三维观察
三维观察是将一个三维物体投影到二维平面上的过程。一般需要经过建模变换、观察变换、投影变换、规范化变换和裁剪、视口变换
观察变换
观察坐标就是人眼观察事物的坐标，我们可以使用n作为z轴正向向量，v作为眼睛上方向量也就是y，u是视线的右方也就是x。
观察变换的目的就是把物体从世界坐标系转换到观察坐标系
可以进行如下两个步骤实现转换
将世界坐标的参考原点由世界坐标系原点平移到相机坐标系原点
进行旋转，使nuv分别对应zyx轴
第一步可以使用矩阵：
M_1 = \begin{bmatrix}
1 & 0 & 0 & -x_0\\
0 & 1 & 0 & -y_0\\
0 & 0 & 1 & -z_0\\
0 & 0 & 0 &1
\end{bmatrix}第二步可以使用矩阵：
M_2 = \begin{bmatrix}
x_u & y_u & z_u & 0\\
x_v & y_v & z_v & 0\\
x_n & y_n & v_n & 0\\
0 & 0 & 0 &1
\end{bmatrix}其中的分量都是nuv向量在xyz轴上的分量
综合可以得到最终的变换 ...
频率域图像增强
引入空间角度的图像增强是非常直观且符合我们认知的，但是图像如何引入频率呢？
在图像中频率可以看成是图像变换速率。频率越大图像强度（亮度/灰度）变换越快，因此有日常所说的高频信息和低频信息。
傅里叶变换傅里叶变换可以将空间上的信息转化为频率上的信息，也就是他可以捕获变化的剧烈程度。
连续变换及反变换公式：
可以得出离散形式的变换和反变换公式：
根据欧拉公式$e^{ix} = cos(x) + i \, sin(x)$可得：
求解出每个u的函数后可以把它划分成实部和虚部，然后进行一些处理
例：假设采样点为$x_0 = 0.5 , x_1 = 0.75 , x_2 = 1.00 , x_3 = 1$
\begin{aligned}
F(0) &= \frac{1}{4} \sum_{x_0}^{3} f(x) e^0\\
&= \frac{1}{4} [f(0) + f(1) + f(2) + f(3)] = 3.25\\
F(1) &= \frac{1}{4} \sum_{x_0}^{3} f(x) e^{\frac{-i 2 \pi x}{4}}\\
&= \frac{1}{ ...
马尔可夫模型
定义系统中有若干个状态S1, S2, …, Sn. 随着时间推移，系统会从一个状态转移到另一个状态，马尔可夫模型认为后一个状态和前面若干个状态有关系。
例如天气和前面若干天的天气之间有关系，假如近两天天晴明天天晴的可能性就比较大。
形式化描述：
马尔可夫模型可以表示为一个五元组$\lambda = (S, O, A, B, \pi)$
状态集合S: S = {S1, S2, S3} 描述了模型所有可能的状态，例如上例中{下雨，天晴，刮风…}或{N, V, A, D, P, T, Y}
输出符号集合O: 所有状态输出的集合。例如上面不同颜色的小球
状态转移矩阵A = $a_{ij}$ 。它决定下一个状态。
可观察符号的概率分布矩阵B = $b_j (k)$: 表示在状态j输出符号为k的概率。它决定在当前状态输出什么符号
初始状态概率分布$\pi$: 最开始可能位于什么状态.
两个假设
齐次马尔可夫假设
也就是说当前状态只和前一个状态有关,和其他状态和观测无关，形式化描述为：
P(s_t | s_{t-1} o_{t-1} ... s_1 o_1 ) = P(s_t | s_{t ...
链路层
概念
节点： 运行链路层协议的设备，例如主机、路由器等
链路： 将信息传输到相邻节点的通信信道
链路层帧： 数据报封装在链路层帧中
链路层提供的服务有：
链路接入： 媒体访问控制（MAC）协议规定了帧在链路上的传输规则，还协调了多个节点共享当个链路时的问题。
可靠交付： 和TCP协议一样，这里的可靠交付也是通过差错检测和重发保证的。
差错检测
链路层的主题是在网络适配器中实现的，也叫网络接口卡。
差错检测技术奇偶校验假设发送的信息中有d比特，那么发送方只需要附加上一个比特使得1的个数为偶数即可。接收方接收时检查是否有偶数个1那么就可以得知是否有差错。
但是这种检测方式检测出错的可能性很大，达到50%，因此需要一种更健壮的检测方式。
另一种方法时把这些比特划分成i行j列的矩阵，每一行每一列都有一个检验比特，这样不仅可以检测出错误还可以在出错时纠正他。
检验和方法在运输层中使用了这个技术
循环冗余检测（CRC）该检测方法的基本思路为： 在d位比特后加上r位校验比特，使得他可以被G正好整除。公式为：
D * 2^r XOR R = nG\\
D * 2^r = nG XOR R\ ...
空间域图像增强
基本灰度变换
反转变换： 也就是图中的反比。作用是将黑图变白，白图变黑，这样可以显示出原来一些比较隐蔽的信息
对数变换： 对数变换可以将一些较暗的图像变亮，并且对图像整体没有太大影响
幂次变换； 幂次变换可以自由选择将亮的图片变暗或者将暗的图片变亮。并且他可以达到和对数变换类似的效果。一个典型的应用是$\gamma$矫正 $\gamma$矫正是对于摄像机来说的，摄像机拍摄后的图像和真实情况往往会有一个转换。假设入射光强度为r,输出电压为v,则有:$v = C r^{\gamma}$ 因此预先乘一个$\frac{1}{\gamma}$就可以避免光电效应，而$\gamma$值由摄像机的参数决定
分段线性变换： 输入和输出之间是一个分段函数，例如：
直方图处理直方图就是统计每一种像素出现的数目，然后根据直方图进行一些处理。根据经验我们可以得出直方图分布比较均衡的图像更清楚（有对比度），例如： 其中第四个图像就显得更清楚。
计算归一化直方图的公式为：
其中$n_j$是第j个灰度出现的次数，n是像素的总数。
直方图均衡化直方图均衡化也就是让直方图像素分布尽可能平均。
max(r ...
决策树算法
基本结构决策树是一个类似流程图的树形结构：其中，每个节点表示在一个属性上的测试。每个分支表示一个输出，每个树叶节点代表类或类的分布。
上面这个例子中play和don’t play是结果，表示玩还是不玩。然后不是叶结点的节点都有一个问号，例如第一个outlook询问的是天气，后面还有湿度和是否刮风。通过这些条件得到了叶节点，叶结点都是只包含一种情况，要么是play要么是don’t play。
我们可以把OUTLOOK，HUMIDITY等称为属性，把其中的每一个选项称为类
现在问题的关键是如何确定进行划分的属性
决策树归纳算法（ID3）决策树适合小规模，类别比较少的数据集。
确定属性的基础就是信息熵，这可以用来表示我们可以获得信息的多少，信息增益多我们就可以认为它对我们有帮助。
我们以此图为例来讲解求解过程。首先最后一行是我们想要知道的答案
首先期望获得的信息可以由以下公式给出
\begin{aligned}
I(s_1 ,s_2 ,s_3 ..., s_m ) = -\sum_i p_i \log_2 (p_i )
\end{aligned}上述公式中$s_m$是结果中的第几 ...
卷积神经网络
基础卷积神经网络的基本形式
整体结果为：
卷积层
如图所示，左边是输入，中间是卷积核，右边是输出。
如果输入为3通道，输出为2通道，那么卷积核需要6个，每三个卷积核卷积再求和可以得到一个输出
非线性激活函数种类：
其中现在最常使用的是ReLU函数，因为求导简单且不容易造成梯度消失
降采样层降采样层的作用是增大感受野，并且对形变不敏感。
max pooling: 在几个候选结果中选择最大值，例如4$\times$4到2$\times$2 也就是说原来4个映射到了现在的一个，映射规则为选取4个中的最大值
average pooling: 选取候选结果中的平均值
LeNet-5结构
C1的通道数为6，卷积核大小为5$\times$5
S2降采样层，28$\times$28降为14$\times$14
C3卷积层，卷积核$5 \times 5$，通道数16
CNN的问题和发展CNN的问题主要有过拟合、难收敛、计算代价大三点
AlexNetAlexNet是12年ImageNet比赛的冠军，当时其他人都适用概率的方法，AlexNet首次使用深度学习的方法比其他队高了十多个百分点，掀起了 ...