Numpy数组
1. 概述
ndarray 数组要求数据类型一致，默认数据类型为 np.float64；显式更改数据类型需要使用 dtype 关键字。
2. axis 轴
Numpy 中 axis = n 对应 ndarray 的第 nnn 层 []，从最外层的 axis = 0，逐渐往内层递增。
3. 数组大小 & 维度
ndarray 数组维度元组 shape 为从最外层到最里层逐层的大小；从最外层到最里层，对应 ndarray 数组的 axis 依次从 0 开始依次编号。
ndarray.ndim ：数组维度数目
ndarray.size ：数组所有元素数目 = 所有维度大小乘积
ndarray.shape ：数组各个维度大小
4. 广播机制
Numpy 两个数组的相加、相减以及相乘都是对应元素之间的操作，当两个数组的形状并不相同时，Numpy 采用广播机制扩展数组使得二者形状相同。Numpy 广播机制原则：
数组维度不同，后缘维度（从末尾开始算起的维度）的轴长相符
数组维度相同，其中一个轴长为 1
5. 常用函数
ndarray.max() ： ...
误差函数
1. 平方误差
对于单个数据来说，其平方误差为
E=12∑k(yk−tk)2\begin{array}{c}
E = \frac{1}{2} \sum_{k} (y_k - t_k)^2
\end{array}
E=21∑k(yk−tk)2
其中，yky_kyk 表示神经网络的输出，tkt_ktk 表示监督数据（ttt 采用 one-hot 编码），kkk 表示数据的维度。
对于所有训练数据来说，其平方误差为
E=12N∑n∑k(ynk−tnk)2\begin{array}{c}
E = \frac{1}{2N} \sum_n \sum_k (y_{nk} - t_{nk})^2
\end{array}
E=2N1∑n∑k(ynk−tnk)2
2. 交叉熵误差
对于单个数据来说，其交叉熵误差为
E=−∑ktklogyk\begin{array}{c}
E = - \sum_{k} t_k \log y_k
\end{array}
E=−∑ktklogyk
其中，yky_kyk 表示神经网络的输出，tkt_ktk 表示监督数据（ttt ...
MoorePenrose伪逆
1. 简介
Moore-Penrose 伪逆常用于求解或简化非一致线性方程组的最小范数最小二乘解。其在实数域和复数域上都是唯一的，并且可以通过奇异值分解求得。
2. 定义
矩阵 AAA 的伪逆定义为
A+=limα→0(ATA+αI)−1AT\begin{array}{c}
A^+ = \lim_{\alpha \rightarrow 0}(A^T A + \alpha I)^{-1} A^T
\end{array}
A+=limα→0(ATA+αI)−1AT
实际计算往往使用以下公式
A+=VD+UT\begin{array}{c}
A^+ = V D^+ U^T
\end{array}
A+=VD+UT
其中，矩阵 UUU、DDD、VVV 分别是矩阵 AAA 奇异值分解后得到的矩阵。
【注】对角矩阵 DDD 的伪逆 D+D+D+ 是其非零元素取倒数之后转置得到的。
3. 性质
当矩阵 AAA 的列数多于行数时，x=A+y
x = A^+ y
x=A+y 是方程所有可行解中欧几里得范数 ∣x∣2|x|_2∣x∣2 最小的。
当矩阵 AAA 的行数多于列数时，x=A+ ...
范数
1. 向量范数
1.1 LpL_pLp 范数
LpL_pLp 范数是向量空间中的一组范数。
1.1.1 定义
Lp(x⃗)=∣x⃗∣p=(∑i=1n∣xi∣p)1p\begin{array}{c}
L_p(\vec{x}) = |\vec{x}|_p = (\sum_{i=1}^n |x_i|^p)^{\frac{1}{p}}
\end{array}
Lp(x)=∣x∣p=(∑i=1n∣xi∣p)p1
其中， p≥1p \geq 1p≥1，x⃗={x1,x2,⋯ ,xn}
\vec{x} = \{x_1,x_2,\cdots,x_n\}
x={x1,x2,⋯,xn} 。
1.1.2 分类
p=−∞:∣x⃗∣∞=limp→−∞(∑i=1n∣xi∣p)1p=mini∣xi∣\displaystyle
p = -\infty: |\vec{x}|_{\infty} = \lim_{p \rightarrow -\infty}(\sum_{i=1}^n |x_i|^p)^{\frac{1}{p}} = \min_i |x_i|
p=−∞:∣x∣∞=p→−∞lim ...
条件数
1. 简介
数值分析中，函数的条件数衡量的是输入参数的微小变化可以使函数的输出值变化多少，用来测量函数输出对于输入的微小变化的敏感程度，或者说一个问题的条件数是该数量在数值计算中容易程度的衡量。一个低条件数的问题称为良置的，而高条件数的问题称为病态（非良置）的。
2. 定义
给定问题 fff，输入 xxx 以及用于求解问题的算法 f~\tilde{f}f~，则绝对误差定义为
E(f~(x))=∣f(x)−f~(x)∣\begin{array}{c}
E(\tilde{f}(x)) = |f(x) - \tilde{f}(x)|
\end{array}
E(f~(x))=∣f(x)−f~(x)∣
相对误差定义为
RE(f~(x))=E(f~(x))∣f(x)∣=∣f(x)−f~(x)∣∣f(x)∣\begin{array}{c}
RE(\tilde{f}(x)) = \frac{E(\tilde{f}(x))}{|f(x)|} = \frac{|f(x)-\tilde{f}(x)|}{|f(x)|}
\end{array}
RE(f~(x))=∣f(x)∣E(f~(x))= ...
正负定矩阵
1. 正定矩阵
1.1 定义
在实数域下，一个 n×nn \times nn×n 的实对称矩阵 MMM 是正定的，当且仅当对于所有的非零实系数向量 zzz 都有 zTMz>0z^T M z \gt 0zTMz>0 。
在复数域下，一个 n×nn \times nn×n 的埃尔米特矩阵 MMM 是正定的当且仅当对于每个非零的复向量 zzz 都有 z∗Mz>0z^* M z \gt 0z∗Mz>0。
1.2 性质
对于 n×nn \times nn×n 的埃尔米特矩阵 MMM，下列性质与「MMM 是正定矩阵」等价：
矩阵 MMM 的所有特征值 λi\lambda_iλi 都是正的。由于 MMM 必然与一个实对角 DDD 相似，即 M=P−1DP
M = P^{-1}DP
M=P−1DP，则 MMM 是正定矩阵当且仅当 DDD 的对角线上的元素都是正的。
MMM 的所有顺序主子式都是正的。
存在唯一的下三角矩阵 LLL，其主对角线上的元素全是正的，使得：M=LL∗M = L L^*M=LL∗。其中，L∗L^*L∗ 是 LLL 的共轭转置。这个 ...
激活函数
常见激活函数及其导数：
1. Sigmoid 函数
【注】Sigmoid 型函数是指一类 S 型曲线函数，为两端饱和函数。常用的 Sigmoid 型函数有 Logistic 函数和 Tanh 函数。
1.1 Logistic 函数
定义：σ(x)=11+e−x\sigma(x) = {1 \over 1 + e^{-x}}
σ(x)=1+e−x1
Logistic 函数常用来产生伯努利分布中的参数。
性质：
σ(x)=exex+1\sigma(x) = {e^x \over e^x + 1}σ(x)=ex+1ex
ddxσ(x)=σ(x)(1−σ(x)){d \over dx} \sigma(x) = \sigma(x)(1 - \sigma(x))dxdσ(x)=σ(x)(1−σ(x))
1−σ(x)=σ(−x)1 - \sigma(x) = \sigma(-x)1−σ(x)=σ(−x)
1.2 Tanh 函数
定义：
tanh(x)=ex−e−xex+e−x\tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}
...
数字世界中常见函数
1. 狄利克雷函数
英文名称为「Dirac Delta Function」。
1.1 简介
狄利克雷函数在除零以外的点取值均为 0，但在整个定义域上的积分为 1。δ\deltaδ 函数可以看作是在原点处无限高、无限细，但总面积为 1 的一个尖峰。
1.2 定义
δ(x)={+∞x=00x≠0∫−∞+∞δ(x)dx=1\begin{array}{c}
\delta(x) = \begin{cases}
+\infty & x = 0 \\
0 & x \ne 0
\end{cases} \\
\int_{-\infty}^{+\infty} \delta(x) dx = 1
\end{array}
δ(x)={+∞0x=0x=0∫−∞+∞δ(x)dx=1
【注】狄利克雷函数并不是一个严格意义上的函数，更严谨地来说，其定义为分布或者测度或者广义函数。
2. 克罗内克函数
2.1 简介
克罗内克函数在除零以外的点取值均为 0，在零处取值为 1 。
2.2 定义
δ(x)={1x=00x≠0\begin{array}{c}
\delta(x) =
\ ...
快速傅里叶变换
【注】参考自算法导论。
1. 简介
快速傅里叶变换（FFT）是实现离散傅里叶变换（DFT）和离散傅里叶逆变换（IDFT）的快速算法，其时间复杂度为 O(nlogn)O(n \log n)O(nlogn)。DFT 在实际生活中有很多应用，比如通过离散傅里叶变换，可以将系数表示的多项式转为点值表示的多项式，从而使得多项式的乘法的复杂度由 O(n2)O(n^2)O(n2) 降为 O(n)O(n)O(n) 。
2. 实现
快速傅里叶变换涉及到离散傅里叶变换的知识，FFT 能够实现的基础在于折半定理，折半定理提供了求大整数的 DFT 的一种思路：即通过将大整数不断划分为两部分，然后分别求出两部分的 DFT，最后在合并，本质是一种分治的思想。
3. 代码
3.1 快速傅里叶变换模板
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 ...
离散余弦变换
1. 简介
离散余弦变换类似于离散傅里叶变换，但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换。
2. 定义
离散余弦变换是一个线性的可逆函数 F:Rn→RnF: R^n \rightarrow R^nF:Rn→Rn，其中 RRR 是实数集。
2.1 DCT-1
fm=12(x0+(−1)mxn−1)+∑k=1n−2xkcos(πn−1mk)\begin{array}{c}
f_m = {1 \over 2}(x_0 + (-1)^m x_{n-1}) + \sum_{k=1}^{n-2} x_k cos({\pi \over n-1}mk)
\end{array}
fm=21(x0+(−1)mxn−1)+∑k=1n−2xkcos(n−1πmk)
边界条件：xkx_kxk 相对于 k=0k = 0k=0 点偶对称，并且相对于 k=n−1k = n-1k=n−1 点偶对称；对 fmf_mfm 的情况也类似。
【注】DCT-1 不适用于 n<2n \lt 2n<2 的情况，其他 DCT 类型都适用于所有的整数 nnn 。
2.2 DCT ...
柯西主值积分
1. 简介
柯西主值积分是以特殊方式定义的反常积分，其值又称为柯西主值。
2. 定义
2.1 第一类反常积分（无穷积分）
设函数 f(x)f(x)f(x) 在 (−∞,+∞)(-\infty,+\infty)(−∞,+∞) 上连续且可积，则定义第一类反常积分：
∫−∞+∞f(x)dx=limu→−∞∫ucf(x)dx+limv→+∞∫cvf(x)dx\begin{array}{c}
\int_{-\infty}^{+\infty} f(x) dx = \lim_{u \rightarrow -\infty} \int_u^c f(x)dx + \lim_{v \rightarrow +\infty} \int_c^v f(x) dx
\end{array}
∫−∞+∞f(x)dx=limu→−∞∫ucf(x)dx+limv→+∞∫cvf(x)dx
其中，ccc 是区间上任意一点。
上式右边式子中两个极限皆收敛，则左式的反常积分才收敛；上式右边式子任意其一发散，则左式的反常积分发散。
定义第一类反常积分的柯西主值：
PV∫−∞+∞f(x)dx=limR→+∞ ...
数组中第K小的数
1. 简介
查找一个序列中的最大/最小值时间复杂度均为 O(N)O(N)O(N)，而查询一个序列中第 K(K=0⋯N−1)K(K = 0 \cdots N-1)K(K=0⋯N−1) 大的数时间复杂度最坏情况下即为排序的最好时间复杂度 O(NlogN)O(N \log N)O(NlogN)（只考虑比较排序），但利用快排的 PartitionPartitionPartition 思想也可以达到期望 O(N)O(N)O(N) 的时间复杂度，最坏情况下 O(N2)O(N^2)O(N2) 的时间复杂度。
2. 思想
沿用快排中的 PartitionPartitionPartition 思想，选择一个枢轴，然后将小于枢轴的数都交换到枢轴左边，大于枢轴的数都交换到枢轴右边。
然后判断：
如果枢轴左边小于等于枢轴的序列大小等于 KKK，则说明第 KKK 小的数即为枢轴。
如果枢轴左边小于等于枢轴的序列大小大于 KKK，则说明第 KKK 小的数一定在枢轴左边的序列。
如果枢轴左边小于等于枢轴的序列大小小于 KKK，则说明第 KKK 小的数一定在枢轴右边的序列。
【注】同样，在快排中 ...
