Reference:

导航定位的本质：状态估计问题
常见求解方法

  • 递归式估计：Kalman滤波
  • 批量式估计：图优化算法

图优化实现形式：最优估计 -> 最大后验估计 -> 残差误差最小化

什么是图？图是由一系列顶点和若干连结顶点集合内两个顶点的边组成的数据结构。数学意义上的图，指的是由一系列点与边构成的集合，这里我们只考虑有限集。通常我们用G=(V,E)表示一个图结构，其中V表示点集，E表示边集。

首先讲优化。从直观上来说，就是沿着梯度下降的方向去找到使误差(代价函数)最小化的优化变量。非线性优化，自然就是误差函数和需要优化的变量之间不是简单的线性关系，而是非线性的。求解它常用的库有ceres。
再讲图优化。图优化的本质还是优化，只不过是用图的方式去表达。把优化变量当做顶点，约束当做边，也是用梯度下降的方法去使误差最小化。那图优化有什么好处呢？因为slam的特性，图是稀疏的，因此可以用图理论去进行边缘化，消元，加速计算。常用的库有g2o。再讲因子图优化。和前者不同的是，它的重点在因子图。它的优化落脚点不再是最小二乘理论了，而是最大后验概率理论了。其实常用库有gtsam位姿图优化和BA优化都是slam中的具体问题，可以用上述理论来解决。它们的不同点在于，ba优化中，路标点和位姿都是不确定的，都是优化变量。而位姿图优化，假设路标点是确定的，优化变量只有位姿，路标点成了约束2。

Introduce

在概率图中，求某个变量的边缘分布是常见的问题。这问题有很多求解方法，其中之一就是把贝叶斯网络或马尔科夫随机场转换成因子图，然后用sum-product算法求解。换言之，基于因子图可以用sum-product算法（也称为信念传播算法）高效的求各个变量的边缘分布1。

将一个具有多变量的全局函数因子分解，得到几个局部函数的乘积，以此为基础得到的一个双向图叫做因子图（Factor Graph）。

对于函数$g(X1,…,Xn)$，有以下式子成立：

$g(X_1, \ldots, X_n) = \prod_{j=1}^{m}f_{j}(S_j)$. 其中，$S_j \subseteq { X_1, \ldots, X_n }$

  • $X = { X_1, \ldots, X_n }$ 变量结点（variable vertices）

  • $F = {f_1, \ldots, f_m }$ 表示因子结点（factor vertices）

  • $E$ 为边的集合，如果某一个变量结点 $X_k$ 被因子结点 $f_j$ 的集合 $S_j$ 包含，那么就可以在 $X_k$ 和 $f_j$ 之间加入一条无向边。

Example

现在有一个全局函数$g(x_1, \cdots, x_5)$，其因式分解方程为:

​ 其中，各函数表述变量间的关系，可以是条件概率或者其他关系（例如在马尔科夫随机场中的势函数）。

则其对应的因子图如下图所示。

因子图示例

也可以等价于：

因子图示例

在因子图中，所有的顶点不是变量结点就是因子结点，边表示它们之间的函数关系。

3. 有向图、无向图和条件随机场

接下来，我们再来了解一下概率图模型中的有向图、无向图，及其其对应的各类模型结构。

  • 有向图模型，又称作贝叶斯网络（Directed Graphical Models, DGM, Bayesian Network）

贝叶斯网络的有向图模型

  • 但在某些情况下，强制加入结点的边方向是不合适。无向图模型（Undirected Graphical Model, UGM），又称作马尔科夫随机场或者马尔科夫网络（Markov Random Field, MRF or Markov Network）

马尔科夫随机场的无向图模型

  • 设$X=(X_1,…,X_n)$和$_Y=(Y_1,…,Y_m)$都是联合随机变量，若随机变量$Y$构成一个无向图$G=(V,E)$表示的马尔科夫随机场，则条件概率分布$P(Y∣X)$称之为条件随机场（Conditional Random Field, CRF）。

线性链条件随机场的无向图模型

4. 因子图的转换

4.1 贝叶斯网络示例

给出上面图中的贝叶斯网络，根据各个变量间的关系，我们可以得到

$p(u,w,x,y,z) = p(u)p(w)p(x \mid u,w)p(y \mid x)p(z \mid x)$

表示为因子图，以下两种形式皆可：

线性链条件随机场的无向图模型

由上述例子总结出由贝叶斯网络构造因子图的方法：

  • 贝叶斯网络中的一个因子（可以理解为函数）对应因子图中的一个结点
  • 贝叶斯网络中的每一个变量在因子图上对应边或者半边
  • 结点$g$和边$x$相连当且仅当变量$x$出现在因子$g$中。

4.2 马尔科夫链示例

以下是一个马尔科夫链转换的示例：

线性链条件随机场的无向图模型

其对应的全局函数可以表示为：

4.3 隐马尔可夫模型示例

其对应的全局函数可以表示为：

$p(X_0, \ldots, X_n, Y_1, \ldots, Y_n) = p(X_0)\prod_{k=1}^{n}p(X_k \mid X_{k-1})p(Y_{k} \mid X_{k-1})$

5. Sum-product算法

有了因子图，我们可以利用Sum-product算法，根据联合概率分布求出边缘概率分布（先验分布）。

5.1 边缘概率的求解

  • 联合概率表示两个事件共同发生的概率，如A和B共同发生的概率为$P(A \cap B)$
  • 边缘概率是某个事件发生的概率
    • 边缘概率是通过边缘化（marginalization）得到的：在联合概率中，把最终结果中不需要的那些事件合并成其事件的全概率而消失（对离散随机变量用求和得全概率，对连续随机变量用积分得全概率）

某个随机变量$x_k$的边缘概率可由$x_1,…,x_n$的联合概率求得：

fk¯(xk)=△∑x1,…,xn except xkf(x1,…,xn)

$\overline{f_k}(x_k) \overset{\triangle}{=} \sum\limits_{x_1, \ldots, x_n~\text{except}~x_k}f(x_1, \ldots, x_n)$

假定现在我们需要计算如下式子的结果：

$\overline{f_3}(x_3) \overset{\triangle}{=} \sum\limits_{x_1, \ldots, x_7~\text{except}~x_3}f(x_1, \ldots, x_7)$

Ceres是图优化的求解器

因子图优化可以认为和图优化没区别，本质都是大规模稀疏最小二乘法。

ceres只是诸多求解器的一种

卡尔曼滤波是单步最优因子图，图优化，把最优估计问题转化为贝叶斯网络的求解问题。突破了平滑和滤波的界限，是最优估计领域的深度学习技术。投身于这个技术吧 这是改变行业和世界的技术。现在是2018年，这个技术的状态，相当于2012年的深度学习，2011年的区块链

作者：图状态空间
链接：https://www.zhihu.com/question/48878602/answer/416034400
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：图状态空间
链接：https://www.zhihu.com/question/54729486/answer/538203642
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

因子图是什么？gta和瑞士人的论文已经介绍的比较清楚了，就是一种矩阵和概率模型的组织方式。这方面的东西如果想深入研究，可以看gtsam和isam相关的文献。中文版的书籍因子图，翻译的是kaess和dellaert的论文，质量非常高，做到了信达雅。sum-product算法是从一组相关的概率密度分布中，把一个单点的概率分布 求出来的原理。当然，这个只是原理，具体要实现还是要靠因子图和稀疏矩阵的方法。HMM是一种模型，隐式马尔科夫模型。其原理是当前状态只与上一个时刻的状态相关。当然这种模型的应用非常多。卡尔曼滤波是一种算法，是传感器建模领域和自动控制领域的王者算法，穿越了摩尔定律的整个周期。因子图是一种更通用的计算语言，可以千变万化，可小至卡尔曼滤波，中至滑动窗口滤波，大到无线维度的isam。我们以最简单的卡尔曼滤波为例，说明因子图的情况。x0时刻的分布，记为factor 0x0到x1时刻的状态转移情况，可以用factor 1来表示。如果用c++实现，factor0 和factor1，都被push_back到用向量vector表示的因子图中。这个时候，如果是窗口滤波，可以继续pushback，直到窗的size，如果是isam则不停的push_back。而因子图的优势是，无论是数据压入多少维度，解法是一样的。他强任他强，数据多长我都是一招排山倒海。。

非线性优化，图优化，因子图优化是三种优化理论，类似于学习到的教程：
非线性优化，强推ceres库，对用户极其友好，文档和注释都很不错；
图优化，强推g2o，没文档，几乎没注释，如果能搞透对图优化理解肯定会深刻了；
因子图优化，强推gtsam，可以看看预积分那套理论并且实践下，对理解会有很大帮助。

位姿图优化和BA优化是具体的问题了，也就是说需要用上面学习到的教程来解决这些具体问题：
位姿图优化，只优化位姿，路标点只作为优化过程中的约束；
BA优化，联合优化位姿和路标点。

作者：祯卿
链接：https://www.zhihu.com/question/389810365/answer/1309412482
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

$p\left(x_{1}, \ldots, x_{N}\right)=\frac{1}{Z} \prod_{j=1}^{m} f_{j}\left(x_{f_{j}}\right)$

1. 因子图介绍 ↩
2. 图优化 ↩