longer95479@home:~$

Archive

About

Categories

Tags

RSS

Transformer is a clustering machines

2012    2015    2018 2019 2020  2022        2023
Alex    Res     GPT  GPT2 GPT3  chatGPT     GPT4
                BERT            Chinchilla  Llama2
                                            Claude2

ResNets

$x_0$ 可以是图片像素强度向量，经过多层网络后，学习到特征 $x_L$ (Learned representation)，该特征相比于原始图像更利于图像分类。

\[x_0 \rightarrow x_1 \rightarrow \dots \rightarrow x_L\] \[L = \# layers\]

将学习到的特征放入到传统的机器学习分类器（Classical ML step）中进行分类（例子为 logistic regression）：

\[x_L \rightarrow y = \sigma (\beta^T x_L)\]

在 2012 年以前，人们会将 $x_L$ 直接作为原始图片，放入到传统的分类器当中。

如果把神经网络看成一个整体，那么神经网络便是一个映射：

\[x_L = f_{\theta}(x_0)\]

$\theta$ 是可训练的参数。$f_{\theta}$ 可以通过多个函数的嵌套组合来得到：

\[x_{k+1} = x_k + \sigma(W_k x_k + b_k),\ k = 0,\dots, L-1\]

$W_k x_k + b_k$ 是仿射变换。$\sigma$ 是逐元素操作的非线性函数，例如 $\mathrm{max}(\cdot, 0)$。更详细一些，如果有一个向量 $x = [1,-2,3]$，应用 ReLU 函数（$f(x) = \max(\cdot,0)$）则得到 $f(x) = [\max(0,1), \max(0,-2), \max(0,3)] = [1,0,3]$

这就是传统的前馈神经网络，也称为多层感知器。

Neural ODEs:

\[\begin{align} x_{k+1} &= x_k + \sigma(W_k x_k + b_k) \\ & \downarrow \mathrm{Continuous\ time}\\ \dot x(t) &= \sigma(W_t x(t) + b_t) \end{align}\]

此时，我们得到一个关于 $x$ 的动态系统，因此可以用动态理论和控制理论进行分析。需要与神经网络中常提到的“训练的动态系统”作区分，训练的动态系统关心的是训练的过程中参数的演进，且只考虑一层（本文并不关注 参数 的动态系统）：

\[\dot \theta (t) = - \nabla_{\theta} \sum_{i=1}^n (Y_i - f_{\theta(t)}(X_i))^2,\ \theta \in \mathbb{R}^N,\ N \rightarrow \infty\]

NN 可以理解为一种流动映射（flow map, a NN is a compact representation of a funtion that can be represented as a flow map）：

\[\mathrm{NN = Flow Map}\] \[f_{\theta}: x(0) \mapsto x(T); \mathbb{R}^d \to \mathbb{R}^d\]

这似乎是在说，NN 不是直接参数化函数本身（有一个表格直接告诉你 f(x) 的值），而是参数化了某条曲线，它将会通过动力学告诉你如何从一个点到达另一个点。

Transformer

Prompt 可以是文本:

\[\begin{align} & \mathrm{\boxed{The}\ \boxed{quick}\ \boxed{bro}\boxed{wn}\ \boxed{fox}\ \boxed{jumps}\ \boxed{over}\ \boxed{the}\ \boxed{lazy}\ \boxed{dog}} \\ & \downarrow \hspace{6.5em} \mathrm{position + random map} \hspace{6.5em} \downarrow \\ & x_1 \hspace{10.5em} \cdots \hspace{11em} x_n \end{align}\]

也可以是图片（整张图片被分割成多个图像块，每个图像块会被编码，附加上以某种顺序读取图片块的位置编码）：

 -------             ------- 
|       |           |   |   |
|       |   ---->   |-------|
|       |           |   |   |
 -------             -------
whole picture       pitches

因为 tokens 已经作了位置编码，因此可以将输入视为一个集合，而不考虑顺序（e.g. $n=512,\ d=200$），之后将集合视为经验测量得到的概率分布:

\[\{x_1 \cdots x_n\} \in \mathbb{R}^d: \mathrm{tokens}\] \[\{x_1 \cdots x_n\} \iff \frac1n \sum_{i=1}^n \delta_{x_i}\]

promp = input = probability measure on tokens （likehood of token being next）

output = probability measure on tokens （empirical dist. of tokens in prompt）

输入给 transformer 的是关于 tokens 的概率测量。而输出则是给定这个句子（经验分布）后下一个 token 的似然概率分布。

虽然输入和输出中的 probability 含义不同，但在数学上看是相同的，或者说是属于同一个集合内的，因此可以套用 ResNet 中 Map flow 的概念。

\[\mathrm{Transformer = Flow map}\] \[f_{\theta}: \mu(0) \mapsto \mu(T); \mathcal{P}(\mathbb{R}^d) \to \mathcal{P}(\mathbb{R}^d)\]

其中，$\mathcal{P}(\mathbb{R}^d)$ 是指 $\mathbb{R}^d$ 上的概率分布的空间/集合。

此时，我们可以给出 $\mu(0)$：

\[\mu(0) = \frac1n \sum_{i=1}^n \delta_{x_i}\]

那么动力学方程应该是什么呢？我们该如何移动给出的概率分布呢？

\[\partial_t \mu(t) = ?\]

我们可以通过移动点的位置来改变概率分布。而对于 Transformer，它实际上是在实现一个在平均场下的相互作用粒子系统（Mean-Field interacting particle system）:

\[\dot x_i(t) = X_t [ \mu(t) ](x_i(t)),\ i = 1,\cdots, n\]

在此，粒子是 token，它的速度由向量场 $X_t$决定，而向量场受粒子的位置 $x_i(t)$ 以及当前时刻所有粒子/tokens 的分布（以一种整体的方式）。

知道了每个粒子（token）如何移动后，我们想知道分布 $\mu(t)$ 如何移动？

Mean-Field interacting particle siystem => Continuity equation

\[\dot x_i(t) = X_t [ \mu(t) ](x_i(t))\] \[\Downarrow\] \[\partial_t \mu(t) + \mathrm{div} (\mu(t)X_t[\mu(t)]) = 0\]

Self-attention dynamics

Self-attention dynamics = Spacial choice of $X_t [ \mu(t) ] (\cdot)$

\[X_t [\mu(t)](x) = V_t \frac{\int y e^{<Q_t x, K_t y>} \mu(t) (\mathrm{d}y)}{\int e^{<Q_t x, K_t y>} \mu(t) (\mathrm{d}y)} = V_t \mathbb{E}_{\hat{\mu_x}}[Y_t]\]

因为

\[\mu(t) = \frac1n \sum_{i=q}^n \delta_{x_i(t)}\]

把分布带入速度场，可得

\[X_t [\mu(t)](x_i(t)) = V_t \left( \sum_{j=1}^n P_{ij}(t) x_j(t) \right)\]

其中，$P_{ij}(t)$ 是横向的随机矩阵

Layer Normalization

LayerNorm (prevent explosion)

\[\dot{x_i}(t) = \mathrm{Proj}_{\tau_{x_i(t)}S^{d-1}} V_t \left( \sum_{j=1}^n P_{ij}(t) x_j(t) \right)\]

参考

【MIT Philippe Rigollett】数学视角下的Transformer



Equivalence between Kalman Filter and Factor graph

本文将因子图优化和卡尔曼滤波联系起来：卡尔曼滤波等价于因子图优化在线性系统下只优化最新状态。

我们最根本的目标，是在给定测量值 $z$，找出使得联合概率密度函数 $p(x, z)$ 最大的 $x$。而 $p(x, z)$ 可以进行分解，以便我们写出具体的形式：

\[p(x,z) = p(z|x)p(x)\]

假如我们考虑两个状态 $x_1, x_2$，以及一个测量 $z$（对 $x_2$ 的测量）,则联合概率密度函数可以写为：

\[p(x_2, x_1, z) = p(z | x_2) p(x_2 | x_1) p(x_1)\]

可以看到，联合概率密度函数被分解成了三个概率密度函数的乘积，而这正好对应了卡尔曼滤波里的三个阶段：先验、预测、更新。

  • 先验（prior）：$x_1$ 的先验分布，据此可以求出 $x_1$ 的最优值及其协方差。
\[x_1^* = \underset{x_1}{\mathrm{arg\ min}}\ p(x_1)\]
  • 预测（prediction）：从 $x_1$ 和 $x_2$ 的联合概率密度函数得到 $x_2$ 单独的概率密度函数，并求 $x_2$ 的最优值，绕过对 $x_1$ 的优化的同时又利用了 $x_1$ 的先验信息。
\[x_2^- = \underset{x_2}{\mathrm{arg\ min}}\ p(x_2)\] \[\begin{align} p(x_2) &= \int p(x_2 , x_1) \mathrm{d} x_1 \\ &= \int p(x_2 | x_1) p(x_1) \mathrm{d} x_1 \end{align}\]
  • 更新（update）：在利用了 $x_1$ 的先验信息基础上，利用对 $x_2$ 的直接测量信息。
\[x_2^* = \underset{x_2}{\mathrm{arg\ min}}\ p(x_2|z_2)\] \[p(x_2 | z_2) \propto p(x_2, z_2) = p(z_2 | x_2) p(x_2)\]

线性系统的预测和测量模型如下：

\[x_{k+1} = Fx_k + Bu_k + w\] \[z_k = Hx_k + v\] \[\ w \sim N(0, Q),\ \ v \sim N(0, R)\]

接下来写出先验、预测、更新的概率密度函数的具体形式：

  • 先验
\[p(x_1) \propto \exp({-\frac12 ||x_1 - \mu_1||^2_{\Sigma_1}})\]
  • 预测
\[p(x_2 | x_1)p(x_1) \propto \exp ({-\frac12 ||x_2 - (Fx_1 + Bu)||^2_Q}) \cdot \exp (-\frac12 ||x_1 - \mu_1||^2_{\Sigma_1})\]
  • 更新
\[p(z_2 | x_2)p(x_2) \propto \exp (-\frac12 ||Hx_2 - z_2||^2_R) \cdot \int p(x_2, x_1) \mathrm{d} x_1\]

预测

为了求极值对应的自变量，我们只需考虑指数部分：

\[\begin{align} & ||x_2 - (Fx_1 + Bu)||^2_Q + ||x_1 - \mu_1||^2_{\Sigma_1} \\ &= \begin{bmatrix} Q^{-1/2}(x_1 - Fx_1 - Bu) \\ \Sigma^{-1/2} (x_1 -\mu) \end{bmatrix} ^T \begin{bmatrix} Q^{-1/2}(x_1 - Fx_1 - Bu) \\ \Sigma^{-1/2} (x_1 -\mu) \end{bmatrix} \\ &= \left\| \begin{bmatrix} Q^{-1/2} & \bf{0} \\ \bf{0} & \Sigma_1^{-1/2} \end{bmatrix} ( \begin{bmatrix} I & -F \\ \bf{0} & I \end{bmatrix} \begin{bmatrix} x_2 \\ x_1 \end{bmatrix} + \begin{bmatrix} -Bu \\ - \mu_1 \end{bmatrix} ) \right\|^2 \\ &= \left\| \begin{bmatrix} I & -F \\ \bf{0} & I \end{bmatrix} \begin{bmatrix} x_2 \\ x_1 \end{bmatrix} + \begin{bmatrix} -Bu \\ -\mu_1 \end{bmatrix} \right\| ^2 _{ \begin{bmatrix} Q & \bf{0} \\ \bf{0} & \Sigma_1 \end{bmatrix} } \\ &= \left\| Ax + b \right\|_{\Sigma} \\ &= \left\| x + A^{-1}b \right\| _ {(A^T \Sigma^{-1} A)^{-1}} \\ &= \left\| \begin{bmatrix} x_2 \\ x_1 \end{bmatrix} + \begin{bmatrix} -Bu - F \mu_1 \\ - \mu _1 \end{bmatrix} \right\| _{ \begin{bmatrix} Q+F\Sigma_1 F^T & -F \Sigma_1 \\ -\Sigma_1 F^T & \Sigma_1 \end{bmatrix} } \end{align}\]

此时，可以很方便地把 $x_1$ 边缘化，只需要把对应部分的均值和方差抽离出来即可：

\[X_2 \sim N(F\mu_1 + Bu, F\Sigma_1F^T + Q)\] \[\boxed{ \mu_1 \leftarrow F\mu_1 + Bu }\] \[\boxed{\Sigma_1 \leftarrow F\Sigma_1F^T + Q}\]

其中，$A^{-1}b$，$(A^T \Sigma^{-1} A)^{-1}$ 计算如下：

\[\begin{align} A^{-1}b &= \begin{bmatrix} I & -F \\ \bf 0 & I \end{bmatrix} ^{-1} \begin{bmatrix} -Bu \\ - \mu_1 \end{bmatrix} \\ &= \begin{bmatrix} I & F \\ \bf 0 & I \end{bmatrix} \begin{bmatrix} -Bu \\ - \mu_1 \end{bmatrix} \\ &= \begin{bmatrix} -Bu - F \mu_1 \\ - \mu _1 \end{bmatrix} \end{align}\] \[\begin{align} (A^T \Sigma^{-1} A)^{-1} &= A^{-1} \Sigma A^{-T} \\ &= \begin{bmatrix} I & -F \\ \bf 0 & I \end{bmatrix} \begin{bmatrix} Q & \bf 0 \\ \bf 0 & \Sigma_1 \end{bmatrix} \begin{bmatrix} I & \bf 0 \\ -F^T & I \end{bmatrix} \\ &= \begin{bmatrix} Q+F\Sigma_1 F^T & -F \Sigma_1 \\ -\Sigma_1 F^T & \Sigma_1 \end{bmatrix} \end{align}\]

更新

令

\[\Sigma_2 = R\]

只考虑指数部分

\[\begin{align} & (x_2- \mu_1)^T \Sigma_1^{-1} (x_2 - \mu_1) + (Hx_2 - z_2)^T\Sigma_2^{-1}(Hx_2 - z) \\ &= \left\| \Sigma^{-1/2}_1 x_2 - \Sigma_1^{-1/2}\mu_1 \right\|^2 + \left\| \Sigma_2^{-1/2}Hx_2 - \Sigma_2^{-1/2}z \right\|^2 \\ &\ \ \downarrow \scriptsize{ A_1 = \Sigma_1^{-1/2},\ A_2 = \Sigma_2^{-1/2}H,\ b_1 = -\Sigma_1^{-1/2}\mu_1,\ b_2 = -\Sigma^{-1/2}_2 z } \\ &= (A_1x+b_1)^T(A_1x+b_1) + (A_2x+b_2)^T(A_2x+b_2) \\ &\ \ \downarrow \scriptsize { A = (A_1^TA_1 + A_2^TA_2)^{1/2},\ b = (A_1^TA_1 + A_2^TA_2)^{-T/2} (A_1^Tb_1 + A_2^Tb_2) } \\ &= (Ax+b)^T(Ax+b) + \mathrm{const} \\ &= (x+A^{-1}b)^TA^TA(x+A^{-1}b) + \mathrm{const} \\ &\ \ \downarrow \scriptsize{\Sigma = (A^TA)^{-1},\ \mu = -\Sigma^{-1/2}b} \\ &= (x - \mu) \Sigma^{-1}(x - \mu) + \mathrm{const} \end{align}\]

所以

\[\Sigma = (\Sigma_1^{-1} + H^T\Sigma_2^{-1}H)^{-1},\ \mu = (\Sigma_1^{-1} + H^T\Sigma_2^{-1}H)^{-1}(\Sigma_1^{-1} + H^T\Sigma_2^{-1}z_2)\]

展开 $\Sigma$：

\[\begin{align} \Sigma &= (\Sigma_1^{-1} + H^T\Sigma_2^{-1}H)^{-1} \\ &\ \ \downarrow \scriptsize{ (A-BD^{-1}C)^{-1} = A^{-1} + A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} }\\ &= \Sigma_1 + \Sigma_1 H^T(-\Sigma_2^{-1} - H \Sigma_1 H^T)^{-1}H\Sigma_1 \\ &= [I - \Sigma_1 H^T(\Sigma_2 + H \Sigma_1 H^T)^{-1}H] \Sigma_1 \\ &\ \ \downarrow \scriptsize{ G = \Sigma_1 H^T(\Sigma_2 + H \Sigma_1 H^T)^{-1} } \\ & \boxed{\Sigma = [I - GH]\Sigma_1} \end{align}\]

展开 $\mu$ :

\[\begin{align} \mu &= (I - GH)\Sigma_1(\Sigma_1^{-1}\mu_1 + H^T\Sigma_2^{-1}z_2) \\ &= (I - GH)(\mu_1 + \Sigma_1 H^T \Sigma_2^{-1} z_2) \\ &= (I-GH)\mu_1 + (I-GH) \Sigma_1 H^T \Sigma_2^{-1} z_2\\ &\ \ \downarrow \scriptsize{ (I-GH) \Sigma_1 H^T \Sigma_2^{-1} = G }\\ &= (I-GH)\mu_1 + Gz_2\\ & \boxed{\mu = \mu_1 + G(z_2 - H\mu_1)} \end{align}\]

附录

1

\[\begin{align} & \ \ \ \ \ (A_1x+b_1)^T(A_2x+b_2) \\ &= x^T(A_1^TA_1 + A_2^TA_2)x + 2 (b_1^TA_1 + b_2 ^TA_2)x + (b^T_1b_1 + b_2^Tb_2) \\ &\ \ \ \ \scriptsize { \downarrow A = (A_1^TA_1 + A_2^TA_2)^{1/2},\ b = (A_1^TA_1 + A_2^TA_2)^{-T/2} (A_1^Tb_1 + A_2^Tb_2) } \\ &= x^TA^TAx + 2b^TAx + \mathrm{const}\\ &= (Ax+b)^T(Ax+b) + \mathrm{const} \\ &\ \ \ \ \scriptsize { \downarrow \Sigma = (A^TA)^{-1},\ \mu = -A^{-1}b } \\ &= (x - \mu)^T \Sigma^{-1} (x-\mu) + \mathrm{const} \end{align}\]

2

\[\begin{bmatrix} I & F \\ \bf0 & I \\ \end{bmatrix} ^{-1} = \begin{bmatrix} I & -F \\ \bf0 & I \\ \end{bmatrix}\] \[\begin{bmatrix} I & \bf0 \\ F & I \\ \end{bmatrix} ^{-1} = \begin{bmatrix} I & \bf0 \\ -F & I \\ \end{bmatrix}\]

3

\[(A-BD^{-1}C)^{-1} = A^{-1} + A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}\]

可使用舒尔补辅助证明。

4

如果

\[G = \Sigma_1 H^T(\Sigma_2 + H \Sigma_1 H^T)^{-1}\]

则

\[(I-GH) \Sigma_1 H^T \Sigma_2^{-1} = G\]

可使用反证法证明。



AirSLAM Code Reading

代码实现

首先看一下 airslam 代码的整体思路。

对于视觉惯性里程计，其核心是三个并行的线程： ->(处理msg)->(前端)->(后端)->

使用 生产者-消费者 的框架实现数据的有向流动。例如 map_builder.AddInput(data) 往里加数据，然后另外开一个线程消耗数据，提取特征，最后再开一个线程进行特征追踪匹配和后端优化。

参数的初始化

对于参数的配置，airslam 在 read_config.h 内定义了许多结构体，其中有三个最顶层的结构体，对应 airslam 的三大模块的参数，分别是：

  • VisualOdometryConfigs
  • MapRefinementConfigs
  • RelocalizationConfigs

在这三大结构体内，还有许多子结构体，对应于一些子模块/子功能需要配置的参数。这些大结构体都有构造函数，在构造函数内:

  • 读取总的 yaml 配置文件
  • 之后将获取的配置信息分发给各个子config，也就是各个子config存储了相应配置
  • 其他 非config 的模块初始化的时候会传入config结构体的实例，在其构造函数内将子 config 存储的参数赋值给成员变量，从而实现参数的传递。

以 VisualOdometryConfigs 为例，其内部声明了一系列子 config：

struct VisualOdometryConfigs{
  ...
  PLNetConfig plnet_config;
  SuperPointConfig superpoint_config;
  PointMatcherConfig point_matcher_config;
  LineDetectorConfig line_detector_config;
  KeyframeConfig keyframe_config;
  OptimizationConfig tracking_optimization_config;
  OptimizationConfig backend_optimization_config;
  RosPublisherConfig ros_publisher_config;
  RosSubscriberConfig ros_subscriber_config;    
  ...

在它的构造函数里 ` VisualOdometryConfigs(const std::string& config_file_, const std::string& model_dir_)`，会调用 yaml-cpp 的接口获取所有的键值对：

YAML::Node file_node = YAML::LoadFile(config_file_);
...
ros_publisher_config.Load(file_node["ros_publisher"]);
...

每个子 config 都有一个 Load 成员函数，在获取键值对后，每个子 config 成员均会调用各自的 Load 函数，传入上面声明的变量 file_node。每个 Load 函数本质上是对 yaml-cpp 接口的封装，以 plnet_config.Load() 为例：

  void Load(const YAML::Node& plnet_node){
    use_superpoint = plnet_node["use_superpoint"].as<int>();

    max_keypoints = plnet_node["max_keypoints"].as<int>();
    keypoint_threshold = plnet_node["keypoint_threshold"].as<float>();
    remove_borders = plnet_node["remove_borders"].as<int>();

    line_threshold = plnet_node["line_threshold"].as<float>();
    line_length_threshold = plnet_node["line_length_threshold"].as<float>();
  }

是否使用 imu，参数值在 camera 的配置文件里给出

特征检测器

主要文件：feature_detector.h 和 feature_detector.cc

类 FeatureDtector，有 6 个 Detector() 成员函数的重载，这 6 个重载可以由两类属性组合得到：

  • 相机个数：2 种
    • 单目
    • 双目
  • 特征类型：3 种
    • 点特征
    • 点特征、线特征
    • 点特征、线特征、线端点

2 * 3 = 6 种

根据 Detector() 和 以下的类构造函数可以看到，其调用了更底层的模块 plnet，因此如果需要修改特征检测方法，可以从此处入手。

  FeatureDetectorPtr feature_detector = std::shared_ptr<FeatureDetector>(new FeatureDetector(plnet_config));

增加 rosbag 支持

原始的 airslam 仅支持 ASL 格式的数据集，也就是图片文件形式的数据集，没有读取 rostopic 的接口，因此无法实时运行，也无法跑 rosbag 格式的数据集。

为了适配 rosbag 的功能，需要增加的代码包括：

  • 某帧图像对应的 imu batch 合成代码
  • 话题的订阅 read_configs.h
  • 新线程用于读取 msg，处理后得到给特征提取的
  • 新数据集的内外参配置

imu 数据 和 img 数据的频率有差异，imu 数据频率高，因此需要对两帧图像帧间的imu数据进行缓存打包，用于后续的预积分。差异如下：

img	  +  +   +  +
imu	***************

airslam 的 imu 预积分用的数据与 vins 有所不同，相比 vins 多用了一个数据，每两个相邻的 imu batch 都有图像前后两个imu数据的重叠,如下图：

imu_batch

如果某个图像帧，在其之前无任何 imu 数据，则会丢弃该图像帧，因为无 imu 可以用于预积分。



Total views. cowboys. Hits