Nyaggin'

自动约束网络

在实际的项目开发中,有时会碰到一组相互有约束关系的变量。 我们希望在修改其中一个变量的值时,其余的变量也自动变化,以满足这些约束。

例如,若欲制作一个支持开氏、摄氏、华氏三种温标的转换工具,则需要在输入一种温标下的数值时,计算并更新其他两者的数值。 这个同步是无向的,对于相关联的一对变量,修改任何一个都应当导致另一个变化,并且会连锁牵扯到后者关联的其他变量。

对于这个例子,如果要手动实现所有转换函数,最多只需要写 $2\times\binom{3}{2}=6$ 个即可; 但是就更复杂的应用场合来说,这样做是不现实的,有时甚至是不可能的。

我现提出一种上面这类问题的通用解决方案,以及其基于 NodeJS 的实现


如果把变量当作节点、约束关系当作边的话,所有变量可以构成一张无向图。 以前面说的温标转换工具为例:

当我们改动 $k$ 的值时,由于 $c$ 和 $f$ 的约束都是显函数的形式,它们可以直接计算出来; 但是,如果修改的是 $f$,我们发现不管是 $k$ 和 $c$ 哪一个,都没有办法凭约束直接计算(当然这对于人来说很简单,但对于计算机来说这需要一套符号计算引擎,并且不是所有约束都是可以显式写出其逆的,有些甚至不是双射)。 所以,我们必须开发另一套方法来解出非显式约束下的变量值(当然这方法也应该能解出显式的)。

我的思路是:把约束写成损失函数的形式,这样就可以对待更新的变量施梯度下降法了。 比如这里 $f$ 和 $c$ 之间的惩罚函数可以写成: $$P(f,c)=\left|1.8\times c+32-f\right|,$$ 于是 $c$ 的迭代公式如下: $$c\leftarrow c-\alpha,P'_f(c),$$ $f$ 的迭代公式也是类似的: $$f\leftarrow f-\alpha,P'_c(f).$$

OK,这个朴素的迭代法对于两个实变量和一个简单的约束来说完全足够用了。 现在让我们来看看更复杂的情况(处于演示的目的,我将不再给出约束的具体形式):

在这个例子里,我们需要将一组欧拉角(三维实向量)转换为一个四元数,表示空间中的朝向。 不单是简单的转换,我们还要求转换后的四元数处在一定范围内(考虑关节的活动限制); 如果超出了限制范围,就取最接近之前值的朝向。

这次我们发现: 变量不再是实数了,迭代公式里「减去偏导」这个操作不再有意义了。 所以,如何补救?

为了让梯度下降法能够应用于更广的场景,我们做这样的要求:

  • 所有涉及到的目标约束变量都是流形上的元素。
  • 所有约束对其相关变量均(局部)可微。

目的在于,流形的局部同胚于欧氏空间(称为流形的「坐标卡」),而在后者里可以很方便地讨论坐标和采样的概念; 于是我们可以先把待更新的变量“提升”成坐标卡里的向量,对其邻域采样计算出惩罚函数场的梯度,以之作为梯度下降的方向求出新的向量,最后再还原到流形里作为更新后的值。

我们用 $\varphi_x:\mathrm{Manifold}\mapsto\mathbb{R}^{n}$ 表示包含流形上 $x$ 的图卡,它将流形局部里的元素映射成向量;以及定义 $\overrightarrow{x}:=\varphi_{x}(x)$ 的语法糖。 根据图卡的不同,这样的映射可能有很多个,我们只需要取任意一个即可。

对于任意两个相关联的变量 $x_1\in\mathbb{X}_1, x_2\in\mathbb{X}_2$ 和惩罚函数 $P:(\varphi\mathbb{X}_1,\varphi\mathbb{X}_2)\mapsto[0,\infty)$, 变量的迭代公式是: $$x_1\leftarrow\varphi_{x_1}^{-1}\left( \overrightarrow{x_1}-\alpha\nabla P_\overrightarrow{x_2}(\overrightarrow{x_1}) \right).$$

这本质上就是把计算放到了同胚的空间里去做。 当然,如果变量本身就是欧氏空间的元素,那么就不用遭转换的麻烦了。

其中 $\nabla$ 是梯度算符,可以由(至少完备的)一组基上的差分来近似(因为有约束可微的假设)。

调查发现这玩意 2013 年有人做了……才十年不到啊,血亏。。