By Long Luo

Kalman Filter¹ 是贝叶斯滤波器的一种特殊实现。

Kalman Filter 1D | 一维卡尔曼滤波器

一维卡尔曼滤波器如下图所示：

在线动画展示：http://www.longluo.me/projects/kalman/

By Long Luo

在数学、物理学、工程和计算机领域中，泰勒公式¹ 是一种广泛使用的分析方法，用来计算函数的近似值。在实践中，很多函数非常复杂，而且某些函数是不可积的，想求其某点的值，直接求无法实现。

泰勒公式可以将复杂的函数近似地表达为简单的多项式函数，用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)。注意在逼近的时候一定是从函数图像上的某个点展开。

下图所示就是不同项数的泰勒公式对 \(\sin x\) 的逼近：

泰勒级数的定义为：

\[ f(x) = \sum _{n=0}^{\infty}{\frac{f^{(n)}(a)}{n!}}(x-a)^{n} = f(a) + {\frac {f'(a)}{1!}}(x - a) + {\frac {f''(a)}{2!}}(x - a)^{2} + {\frac {f'''(a)}{3!}}(x - a)^{3} + \cdots \]

这里，\(n!\) 表示 \(n\) 的阶乘，而 \(f^{(n)}(a)\) 表示函数 \(f\) 在点 \(a\) 处的 \(n\) 阶导数。如果 \(a = 0\) ，这个级数也被称为麦克劳林级数(Maclaurin series)² 。

泰勒展开式有很多，那么如何记忆呢？首先我们需要明白，泰勒公式之间都是有相互关联的，我们可以通过推导来理解性记忆这些公式。泰勒公式的具体推导过程可以参考数学分析教材或者网络³ 。

下面我们就推导这些公式，以便更好的记忆⁴ ！

几何级数 Geometric series

对于 \(-1 < x < 1\) 的情况，几何级数⁵ 由等比数列求和公式可得：

\[ \frac{1}{1 - x} = \sum _{n=0}^{\infty}x^{n} = 1 + x + x^{2} + \cdots + x^{n} \]

用 \(-x\) 代入 \(x\) 上式，则：

\[ \frac{1}{1 + x} = \sum _{n=0}^{\infty}(-1)^nx^{n} = 1 - x + x^{2} - x^3 + \cdots + (-1)^n x^{n} \]

用 \(x^2\) 替代 \(x\) , 由于 \(\arctan x = \int_{0}^{x} \dfrac{1}{1 + x^2} \mathrm{d}x\) ，对于 \(-1 \le x \le 1, x \neq \pm i\) ，

\[ \arctan x = \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n + 1}}x^{2n + 1} = x - {\frac {x^3}{3}} + {\frac {x^5}{5}} - \cdots + \frac{(-1)^n}{2n + 1}x^{2n + 1} \]

因为 \(\dfrac{1}{(1 - x)^2} = (\dfrac{1}{1 - x})'\) ，则：

\[ \begin{aligned} \frac {1}{(1-x)^2} & = \sum _{n=1}^{\infty }n x^{n-1} \\ & = 1 + 2x + 3x^2 + \cdots + n x^{n-1} \end{aligned} \]

同 \(\dfrac{1}{(1 - x)^3} = \dfrac{1}{2} (\dfrac{1}{(1 - x)^2})'\) ，则有：

\[ \frac {1}{(1 - x)^3} = \sum _{n=2}^{\infty }{\frac {n(n - 1)}{2}}x^{n - 2} \]

指数函数 Exponent function

由于 \(\dfrac{\mathrm{d} e^x}{\mathrm{d} x} = e^x\) ，\(e^0 = 1\) 那么：

\[ e^x = \sum _{n=0}^{\infty }{\frac{x^n}{n!}} = 1 + x + {\frac{x^2}{2!}} + {\frac {x^3}{3!}} + \cdots + {\frac{x^n}{n!}} \]

很明显：

\[ \begin{aligned} (e^x)' &= (\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)' \\ e^x &= 0+1+\frac{x}{1}+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots \\ &= 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \end{aligned} \]

对于普通指数函数 \(a^x\) , 由于 \(a^x=e^{x \ln a}\) ，如果将 \(x\) 换为 \(x \ln a\) ，那么 \(a^x\) 的泰勒展开式：

\[ \begin{aligned} a^x &= e^{x \ln a} \\ &= 1 + x \ln a + \frac{(x \ln a)^2}{2!} + \frac{(x \ln a)^3}{3!} + \cdots + \frac{(x \ln a)^n}{n!} \\ \end{aligned} \]

By Long Luo

昨天在B站看到一个数学视频¹，比较 \(2^{100!}\) 和 \(2^{100}!\) 的大小。直观感受就是这 2 个数都非常非常大，但哪个更大无法一眼看出来。

虽然指数爆炸，但阶乘实际上增长的速度比指数更快，如下图 1 所示：

可以看出阶乘图像 \(y = x!\) 实际上比指数 \(y = e^x\) 要快很多，而 \(y = x^x\) 是最快的。

但具体哪个更大呢？

这个问题有很多种方法，这里展示了4种方法。

对数放缩法

由于对数² 函数 \(y = \log_{a}{b}\) 当 \(a > 1\) 是单调递增函数，所以比较两个数大小时，可以通过比较两者对数值来实现大小比较。

两边同取对数 \(\log_{2}{x}\) ，

左边：

\[ A = \log_{2}{(2^{100!})} = 100! \]

右边：

\[ B = \log_{2}{2^{100}!}= \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0 \]

共有 \(2^{100}\) 项，值从 \(0\) 到 \(\log_{2}{2^{100}} = 100\) ，所以

\[ B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107} \]

综合上式，我们只需要比较 \(100!\) 和 \(2^{107}\) 的大小即可。

\(100!\) 至少有 \((100 - 64 + 1) = 37\) 项是大于等于 \(64 = 2^6\) ，也就是 \((2^6)^{37}=2^{222}\) 。

显然可得 \(100! \gg 2^{222} \gg 2^{107}\) 。

故有虽然两个数都非常大，但 \(2^{100!}\) 仍然远远大于 \(2^{100}!\) 。

斯特林公式 (Stirling’s Approximation)

由于存在阶乘，我们可以使用斯特林公式(Stirling’s Approximation)³ 来估计。

\[ n! \sim \sqrt{2 \pi n}(\frac{n}{e})^n = \sqrt{2 \pi} n^{\frac{n + 1}{2}}e^{-n} \]

两边同取对数：

\[ \ln{n!} \sim \frac{1}{2} ln(2 \pi) + (n+\frac{1}{2}) ln(n) - n \]

根据上式，可见 \(n\) 足够大时，斯特林公式可以近似为：

\[ \ln(n!) \sim n(ln(n) - 1) \]

则有：

\[ \begin{array}{l} A = ln(2^{100!}) = 100! ln(2) \\ B = ln(2^{100}!) \sim 2^{100}(ln(2^{100}) - 1) = 2^{100}(100 ln(2) - 1) \end{array} \]

由于 \(2^{10} = 1024 \approx 10^3\) ，则有 \(2^{100} \approx 10^{30}\) , 那么 \(B \approx 10^{32} ln(2)\) 。

很明显 \(100! \gg 10^{32}\) ，因此

\[ 2^{100!} \gg 2^{100}! \]

By Long Luo

袁哥在微博上发布了一道 数学挑战题 ：

计算 \((3+ \sqrt{5})^n\) 的整数末三位数，给出能口算或者可以用计算器计算的算法的第一个人，免费给一个价值 1000 元的 A9 投资分享群入群名额。

最开始看到这道题目时，我觉得很简单啊，于是给出了下面的解答：

令 \(y = (3+ \sqrt{5})^n\) ，两边同取对数，\(\log_{10}{y} = n \log_{10}{(3+\sqrt5)}\) ， \(y = 10^{n\log_{10}{5.23607}}\) ，\(lg5 \approx 0.7\) ，所以 \(y \approx 10^{0.7n}\) 。

但问题没有这么简单，因为上述解答只在 \(n = 1\) 是正确的，\(n = 2\) , \(y = 10^{1.4} = 25\) 就不对了，因为精度不够！

之外，根据评论中其他人给的思路，分析得出这个是周期性的，所以又提交了下面的答案：

但问题仍然没有这么简单，因为即使循环周期 \(k = 100\) , \(\log_{10}{(3+\sqrt5)}\) 取的位数再多仍然会出现精度不够的问题。

之后袁哥发布了 解答 ，图片太大，这里放 链接 。

袁哥的题解省略了很多东西，很多人可能看不太明白。我重新写了题解，重新整理了思路及缺失的步骤，外加证明，有高一数学水平即可看懂。

问题 :

对于任意 \(n \subset N\) , 求 \((3 + \sqrt{5})^n\) 整数部分最后 \(3\) 位。

Solution

设 \(a^n = (3 + \sqrt{5})^n , b^n = (3 - \sqrt{5})^n\) ，

\[ f(n) = a^n + b^n \]

证明 1: \(f(x)\) 为整数。 根据项展开式: \(f(n)=2 \cdot \sum_{k=0}^{n / 2} C_n^{2 k} \cdot 3^{n-2 k} \cdot 5^k\langle(\rangle\)奇次项相消, 证毕!

\[ \begin{aligned} & \text { 方法 }\left\langle 27 \text { 根据 } A^{n+1}+B^{n+1}=(A+B)\left(A^n+B^n\right)-A B\left(A^{n-1}+B^{n-1}\right)\right. \\ & \text { 代入 } A=3+\sqrt{5}, B=3-\sqrt{5}, A B=9-5=4 \\ & \text { 可得: } f_{n+1}=6 f_n-4 f_{n-1}, n \geqslant 1 \quad \ldots . \text { 《2 } \\ & f_0=2, f_1=6, f_2=28, \text { 递推 } f_n C Z^{+} \text {证毕 } \\ & \text { 由 } 0<3-\sqrt{5}<1,0<b^n<1, f_n=N, \end{aligned} \]

\(\Rightarrow N-k a^n<N\) ，故题目转化为求 \(f_n\) 最后 3 位， fn \(\% 1000\) 。根据结果 ans \(=f_n \%\). 1000 , 证明ans是周期性。

证明: \(\because f_n=6 f_n-4 f_{n-1}\), 考虑以下数值对: 模运算法则: \((a * b) \% p=(a \% p * b \% p) \% p\)

\[ a^b \% p=\left((a \% p)^b\right) \% p \]

证明 1: 为整数。 根据项展开式: 奇次项相消, 证毕!

方法根据代入可得《递推证毕由 ，故题目转化为求 最后 3 位， fn 。根据结果 ans . 1000 , 证明ans是周期性。 证明: , 考虑以下数值对: 模运算法则:

后来通过搜索，发现这道题是 Google CodeJam¹ 编程竞赛题，原题如下：

By Long Luo

从古到今，人类一直希望机器能够像人一样，代替人们从事各种工作。

机器学习（Machine Learning）是一门引人入胜的领域，通过模拟人脑神经网络，使计算机能够从数据中学习和改进，以完成各种任务。

深度学习(Deep Learning)

神经网络(Neutral Network)

3Blue1Brown 的 深度学习之神经网络的结构 Part 1 。

在当今数字化的时代，机器学习和神经网络成为了引领人工智能发展的核心技术。其中，手写数字识别作为机器学习领域的一个经典问题，为我们深入探索神经网络的原理提供了绝佳的案例。

这篇文章将首先介绍什么是神经网络，神经网络的实现原理，之后以经典的手写数字识别为例来加强对机器学习的理解。

什么是神经网络？

神经系统的工作方式与身体的其他器官完全不同。在身体的许多器官中，同类型的细胞执行同样的功能，单个细胞的工作就代表整个器官的功能，器官的功能也就是其中每个细胞功能的总和。例如肝脏中的每个肝细胞都执行同样的化学合成和解毒功能，小肠上皮细胞都执行同样的吸收营养的功能，每条肌肉中的肌肉细胞都执行同样的收缩功能等。它们的功能状态受整体器官的控制，细胞之间的信息交换比较少。

与此相反，神经系统以网络的方式进行工作，神经细胞之间有频繁和复杂的信息传递，每个神经细胞的状态都根据其在网络中的位置不同而与其它神经细胞不同，单个神经细胞功能也不能代表整个神经系统的功能。

人脑神经网络是由大量的神经元组成，通过突触连接形成复杂的网络。机器学习通过人脑神经网络的启发，构建人工神经网络模型。人工神经网络由节点（神经元）和连接它们的权重组成。权重表示神经元之间的连接强度，信息通过这些连接在网络中传递和处理。

神经网络是如何工作的？

首先，让我们了解一下神经网络的基本结构。神经网络由输入层、隐藏层和输出层组成。输入层接收手写数字的像素值作为输入，隐藏层则负责提取输入特征，输出层给出最终的识别结果。每个神经元都与上一层的所有神经元连接，并带有权重，这些权重决定了每个神经元对信息的贡献程度。

为了训练神经网络，我们需要大量的手写数字样本作为训练数据。训练过程中，神经网络会根据输入数据的真实标签与预测标签之间的误差，通过反向传播算法来更新神经元之间的权重，从而逐渐提高准确性。反向传播算法通过计算每个神经元的梯度，根据梯度的大小来调整权重，使得预测结果与真实标签更加接近。

对于手写数字识别问题，隐藏层的神经元可以学习到不同笔画、曲线等特征，输出层的神经元则对应0到9的数字标签。通过大量的样本和迭代训练，神经网络可以逐渐学习到正确的特征提取和数字分类规则，从而实现准确的手写数字识别。

除了神经网络的结构和训练方法外，还有一些优化技术可以提高手写数字识别的性能。例如，卷积神经网络（Convolutional Neural Networks，CNN）能够有效地利用图像的空间结构特征，提高了识别的准确性和效率。另外，激活函数的选择、正则化技术的应用以及适当的优化算法等都对神经网络的性能起到重要作用。

神经网络是一种受到人脑神经元启发的算法模型，通过多个层次的神经元组成，可以进行复杂的数据处理和模式识别。在手写数字识别中，我们希望机器能够通过训练学习，准确地识别手写的数字。接下来，我们将揭开神经网络的奥秘。

\[ S(x) = {\frac {1}{1 + e^{-x}}} = {\frac {e^{x}}{e^{x} + 1}} = 1 - S(-x) \]