0001 2020-07-06 The Representati

作者: yuerxiaoshui | 来源:发表于2020-07-05 22:20 被阅读0次

【论文精读】DeepFirearm: Learning Disc
What is AI ?
2018 · NAACL · BP · Deep Context
Ruby完成FizzBuzz
Unsupervised Visual Representati
[Word2Vec系列] Negative Sampling
一个整数变成最小2几次方
BERT模型学习与分析
recalcitrant 顽固的
Binary Representation

2020.07.06 开始翻译
代号 0001
The Representation and Matching of Pictorial Structures
Martin A. Fischler & Robert A. Elschlager

术语：
参考图像 (reference image)：需要匹配的物体，目标
场景图像 (scene image)：图像
嵌入 (embedding)：候选区域

摘要

本论文解决的原初问题如下。
给出一个视觉目标的某些描述，然后在真实图片中找出该类目标。
这个问题的部分解决方法是：对描述方案进行说明 (the specification to a description scheme)，并给出一个度量用于衡量匹配与检测“好的”程度。

我们提供了一个组合的描述方案和决策度量，该方案是通用的、符合直觉的，并取得了令人满意的实验效果。我们也提出了一个算法，该算法采用上述的描述方案 (使用一个亮度值矩阵来表示图像)，在矩阵中找到描述的目标。该算法使用了与动态规划相似的过程来减少不必要的计算。

这个方法有一个令人满意的特点 --- 通用性。我不需要为每个新的描述设计程序，相反地，我们只需要对描述进行说明 ---以一个特定集合的原语与参数的形式 (one just specifies descriptions in terms of a certain set of primitives and parameters)。

我们的方法可以运用到许多领域，包括：场景分析和描述，用于导航和向导的地图匹配，光学跟踪，三维场景解析 (stereo compilation)，和图像变化检测。事实上，对几乎所有图像处理任务来说，描述、匹配和记录场景的能力都是非常基础的能力。

索引术语：动态规划，启发式优化，图片描述，图片匹配，图片处理，表示。

引言

本论文解决的原初问题如下。
给出一个视觉目标的某些描述，然后在真实图片中找出该类目标。
一方面，目标也许是简单的，例如线条，也许是复杂的，例如海浪；另一方面，描述可以是语言的、图像的、过程性的，等等。
图片被称为“感知场景” --- 一个二维的灰度值阵列，同时，正在寻找的目标被称为“参考”。

在感知场景中找到参考的能力，或等价的，在两个场景中匹配或记录图像的能力，对几乎所有图像处理任务来说都是基础的能力。
这些任务包括：场景分析和描述，用于导航和向导的地图匹配，光学跟踪，三维场景解析，和图像变化检测。

这儿有两种基本的方法用于解决以上描述的图像匹配问题。

如果我们拥有一个对噪声和失真过程的精确描述（该过程定义了参考和感知场景图像间的映射），那么我们就可以应用统计决策理论的方法来设计一个图像匹配的程序（改程序优化一些目标方程，例如最小化错误或风险用于确定感知场景中的最优嵌入参考）。
这种分析的典型结果是利用一个类似相关性匹配的程序。
然而，在大多数真实问题场景中，所需的噪声和失真模型要么无法获得，要么试图构建它相当困难。
例如，我们可以将所有人脸看做一个理想或参考人脸的扰动版本。然而，试图为该场景定义一个完整的有效的噪声和失真模型是毫无希望的。

第二种方法，也是更为通用的方法（为解决图像匹配问题），是绕过噪声和失真模型，转而采用一种嵌入的度量（该度量不需要被证明其等价于最小误差或风险过程）。
事实上，若不采用噪声和失真模型，这里没有其它的理论上有效的方法可以来设计或预测：某个我们选择的程序对其真实应用是最优的。
在这篇文章中，我们主要关注第二种方法。

我们提供了对嵌入度量的两组准则（该度量不是理论地，在错误表现的基础上进行推导得到的）。
第一组准则，该嵌入度量必须在应用上取得成功（即，其获得的错误表现必须是可以接受的），其必须是符合直觉的（从而我们有信心其有能力处理未知应用），同时还要是通用的（从而可以将其应用于大量的问题而不需要对其进行重大修改）。
第二组准则，根据该嵌入度量，我们可以设计 (specify) 一个计算可行的决策算法用于找到合适的嵌入。（嵌入度量与其对应决策算法的结合被称作嵌入模型。）
在这篇文章接下来的部分里，我们将提出一个嵌入度量与其对应的决策算法，给出该嵌入模型在一些不同问题领域应用的例子，同时说明该嵌入模型是如何与场景表示、图像匹配问题联系到一起的。

一个嵌入度量

为了引入我们嵌入度量的一般形式，并建立其直觉的有效性，让我们首先考虑以下过程。
假设参考是透明橡胶板上的一幅图像。我们将该橡胶板在感知场景中随处移动，同时，我们拉伸或压缩该橡胶板，使获得最佳的匹配（在橡胶板上的参考图像与感知场景下的图像之间）。
我们对每个这样的嵌入进行评估，包括两方面，一方面是关于我们能够获得的对应 (correspondence) 有多好，另一方面是关于我们为了获得该对应需要多少努力来对其进行拉伸和压缩。

我们现在考虑上述过程的一个离散版本，从实现的角度来看，更加准确更加合理的版本。
在一个具体的应用中，我们也许拥有一些信息，这些信息有关参考与场景图像间的可允许失真范围。
例如，出现在场景图像中的一些项目子集总是保持着它们的内部关系，即使它们的相对位置可能会因为它们在参考场景中的位置而变化。
进一步地，在这些相对位置可能变化的位置，我们可以限制这类变化的幅度；并且，最后，我们也可以将变量“损失”赋予不同类型的变化，包括相对位置的变化或一些非几何性质的相对变化。

为了实现这些功能，我们将橡胶板用一个参考图像替换，这个参考图像由一些刚性片段（部件）通过弹簧一起组合而成。
参考图像的一个刚性片段可以小到一个分辨率单元，也可以大到整个参考图像，其对应于参考图像中一个单一的连贯实体。
连接这些刚性片段的弹簧既用于限制它们的移动又用于衡量它们被拉伸了多少的移动“损失”。（特别地，弹簧在行为上展现出高度地非线性。）
为了决定一个嵌入的损失，我们对每个弹簧的“张力”进行衡量（张力可以是方向的函数，也可以是拉伸的函数，甚至可以是某些局部定义性质的相对变化），同时也对每个连贯片段作为一个独立实体嵌入地多好进行一个局部的衡量。 $\color{red}{这个弹簧，不仅可以是位置的弹簧，也可以是性质的弹簧。}$

上面的模型允许两个有趣的二分。
第一个二分是句法 (syntactic) 与语义 (semantic) 的二分。
语义信息，其依赖于应用的，具体表现在将参考仔细的划分为连续的片段、赋予弹簧的位置和损失函数、和与连贯片段的独立嵌入相关的损失函数。
句法信息，其相对独立于特定的应用，定义了算法可以处理的描述类别。这些数据体现在参考分解的极限值（例如，片段的数量和最大尺寸等等）；用来指定全局约束和损失的格式；用以评估全局拟合度的嵌入度量形式。
语义与句法信息的分离对于：在广泛的问题领域进行建模的同时却不用对实现做重大的修改，是基础的。

第二个二分是局部与全局评价函数的分离。
全局评价函数，与前面描述的连续片段的相对位置相关联，在形式上有着强大的句法控制，可以将这种位置关系直接集成到决策算法中。
这很重要，因为全局评价会导致极其严重的组合问题。
一个局部评价函数，与一个给定的连贯片段独立嵌入的多么好相关，可以在不同问题之间轻易的变化（基于问题相关的考虑 based on problem-dependent consideration）而不需要核心算法的任何改变。
因此，一个局部评价函数的形式可以是一个具有图参考组件 (pictorial reference component) 的（常规的）相关函数，或者是一个具有参考组件的形式化描述的语言学概念^[1]，甚至可以是由人类评价者相互式的插入的一系列猜想。
对于一个给定的问题，局部评价函数从核心算法中的分离，使得评价函数的修改或提高有着大量的灵活性，这灵活性在问题的切换间依然保持。
进一步的由于上述的分离，算法的表现（包括局部和全局）可以以一种直接、直觉上显然的方式进行独立的评价。这种评价可以通过选择性的在问题依赖的选项间变更来迭代式的提高效果。

我们现在正式地给出所提出的嵌入度量的描述。
假设参考由 $p$ 个组件组成（即， $p$ 个连贯的或原初的片段）。
对每个片段 $1\le i\le p$ ， $x_i$ 是一个变量，其变化范围为感知场景中所有位置的集合，其代表第 $i$ 个组件的位置。
假设这里有一套机制，或者一个计算机程序，或者一个人，或者一些机械装置，对第 $i$ 个组件的位置 $x_i$ ，其能输出一个数值 $l_i(x_i)$ ，该值表示第 $i$ 个组件在感知场景的 $x_i$ 位置的适应度。 $l_i(x_i)$ 越小，适应度越高。

虽然没有正式地要求， $l_i(x_i)$ 所度量的第 $i$ 个组件在感知场景 $x_i$ 位置出现的强度是独立于其它组件的任何位置知识的。 $\color{red}{这个假设有问题，显然地对人脸来讲，就不独立。}\color{blue}{就是因为这样假设，所以才能将损失分为两部分。}$
即， $l_i(x_i)$ 是一个纯粹局部的、可能不精确的对第 $i$ 个组件在 $x_i$ 位置出现的度量。

在纯粹的局部度量 $l_i, 1\le i\le q$ 之外，我们还需要考虑：1）不同的组件之间对与所需的空间关系有多符合；2）组件间的属性值如何获得其相对于感知场景属性值的相对值（例如，我们也许想要表明第 $i$ 个组件比第 $j$ 个组件更绿且更厚）。
上述描述不满足的程度体现在对应组件之间的弹簧的拉伸程度上。

感知图片中的每个位置与一个二维向量相关（例如，向量的成员可以是感知场景中位置的行列号）。
在这种情况下， $x_i-x_j$ （普通向量减法）是一个从 $x_j$ 指向 $x_i$ 的向量。
现在令 $g_{ij}(x_i,x_j)=g_{ij}(x_i-x_j)$ 为连接第 $i$ 个与第 $j$ 个组件的弹簧的损失。
如果组件之间没有弹簧连接，那么 $g_{ij}$ 为 $0$ 。

如果我们在 $i=j$ 时设置 $g_{ij}(x_i,x_j)=l_i(x_i)$ ；并且令 $X_i=\{x_1,x_2,\dots,x_i\}$ ，则在位置 $X_p$ 嵌入 $p$ 个组件的总损失为
$G(X_p)=\sum_{i=1}^p\sum_{j=1}^i g_{ij}(x_i,x_j)\quad (1)$
表达式（1）也可被写为
$G(X_p)=\sum_{i=1}^p h_i(X_i)\quad (2)$
其中
$h_i(X_i)=\sum_{j=1}^i g_{ij}(x_i,x_j)$
$h_i(X_i)$ 可以被看做是在由 $X_i$ 给出前 $i-1$ 个组件的位置的条件下，将第 $i$ 个组件嵌入到位置 $x_i$ 的损失。

计算过程

在文章的这个部分里，我们将介绍：基于上述嵌入度量，从一幅图像中定位一个合适的嵌入的计算过程。
这个部分还包括对动态规划算法（DP）的讨论，该算法以适当的角度包含在我们提出的算法中（linear embedding algorithm, LEA）。
特别地，一个用于解决嵌入问题的通用（但计算上不实际的）方法是DP的某种形式。
我们的嵌入度量的具体形式是对一般 DP 公式的简化，并且 LEA 是作为这个受限的 DP 公式在计算上可行的近似。
这个部分还包括一个图论的解释，该解释提供了一个对 LEA 与 DP 的关系的更好的更符合直觉的理解。

让我们假设感知图像（简写为 SM）由 $M$ 个分辨率元素构成；而参考（简写为 RM），由 $P$ 个图形式定义的组件（连贯片段）构成，且一共拥有 $N=\sum_{i=1}^P n_i$ 个分辨率元素，其中 $n_i$ 是第 $i$ 个组件的分辨率元素数量。

定位一个最佳嵌入的最直接的过程是：从 SM 选择组合的 $N$ 个分辨率元素，判断这个选择是否满足连贯性的（组件内部）和全局的（组件间）的约束，一旦符合约束，计算该选择的嵌入度量。
显然地，这种方法即使对小图片也不实用。
例如，一个 50×30 的SM（ $M=1500$ ）和一个 5×5 的RM（ $N=25$ ）需要超过 $10^{64}$ 次选择和评价，一个无望的巨大数字。
如果我们假设连贯性与关系约束给我们提供 $P=6$ 个非覆盖组件，每个组件被限制到 $w=10$ 个位置（相对于其原初组件放置的位置），我们仍然需要执行 $1500×10^5=1.5*10^8$ $\color{blue}{这个式子对的}$ 次评价。
假设我们每次评价花费 $10^{-3}s$ ，我们需要 $1.5×10^5s$ （等价于两天）的计算时间。
显然地，我们需要一个更有效率的技术。

动态规划
使用形式化的表示方式，对典型图像的嵌入度量的评价会导致一个非线性的、整数规划的问题，该问题具有不同于全局最优的局部最优点（即没有特别的规律性，例如单峰性）。
在上述条件下寻找全局最优的唯一可行计算方法（除了前面讨论的暴力搜索技术）常常被称作动态规划。
动态规划是一个多阶段的或迭代的优化过程，其通用的术语描述见下文（见文献 [6] 和 [7]）。
我们希望找到
$\min\limits_X G(X)=\sum_{i\in I}h_i(X^i)\quad (3)$
其中 $X=\{x_1,x_2,\dots,x_p\}$ ， $I=\{1,2,\dots,p\}$ ， $X^i$ 是 $h_i$ 所依赖的变量集合（ $X$ 的子集）。 $h_i, 1\le i\le p$ ，是一个给定的实值函数的集合^[2]。

令 $|X^i|$ 等于 $X^i$ 中变量的数量，对每个 $x_i, 1\le i\le p$ ，其在 $M$ 个值中变化。则每个组件的损失函数 $h_i(X^i)$ 可以通过一个 $|X^i|+1$ 列 $M^{|X^i|}$ $\color{blue}{是的}$ 行的表格来描述。

解决方案如下。我们选择一个变量 $y_1\in X$ 并计算下列的表达式（给出了关于 $y_1$ 的最小的 $G$ ）
$f_1(\Gamma(y_1))=\min\limits_{y_1}\sum_{i\in I_1}h_i(X^i) \quad (4)$
$y_1^*(\Gamma(y_1))= \mathtt{the\ value\ of\ y_1\ which\ minimizes\ expression\ (4)} \quad (5)$
其中 $\Gamma(y_1)$ 是所有变量的集合（除掉 $y_1$ ），该集合是所有包含 $y_1$ 的 $X^i$ 的并集。换句话说， $\Gamma(y_1)$ 是所有与 $y_1$ 相互作用的变量的集合。
$I_1$ 是所有 $i$ 的集合，满足 $X^i$ 包含 $y_1$ 。
$y_1^*$ 代表最优的 $y_1$ 值，其（ $y_1^*$ ）是一个以 $\Gamma(y_1)$ 为变量的函数。
$\color{blue}{大概意思就是，变量\ y_1\ 有多个可能的取值，我们依次将其固定为某一值，然后算出该取值情况下，其余变量组合之后}$
$\color{blue}{取得的最小值，然后再挑选出使得这些最小值中的最小值所对应的\ y_1\ 的值，即为最终\ y_1\ 的值，即所谓\ y_1\ 的消去}$

由公式（4）所描述的操作叫做变量 $y_1$ 的消去，其导致公式（3）的如下变换：
$\min\limits_XG(X)=\min\limits_{X-{y_1}}\left[f_1(\Gamma(y_1))+\sum_{i\in\left[I-I_1\right]}h_i(X^i)\right] \quad (6)$
表达式（6）与（3）有相同的形式，但是不包含 $y_1$ 。因而，我们通过顺序地消去所有变量来为 $X$ 找到最优的赋值，然后可以通过 $y_i^*(\Gamma(y_i))$ 存储表来回溯（其中 $\Gamma(y_i)$ 只包含 $j>i$ 的 $y_i$ ）。
即，我们最后会到一个阶段，对某些 $s$ ：
$\bigcup_{j=1}^sI_j=I$
从而表达式（6）可以写为：
$\min_XG(X)=\min_{y_{s+1},\dots,y_p}\left[f_s(\underbrace{y_{s+1},\dots,y_p}_{{}=\Gamma(y_s)})\right] \quad (7)$

从公式（7）我们可以直接确定 $G$ 的全局最小损失并同时优化 $Y=(y_s,y_{s+1},\dots,y_p)$ 的值。
给出 $Y$ 的值，我们可以从 $y_{s-1}^*(\Gamma(y_{s-1}))$ 存储表中确定 $y_{s-1}^*$ 的值，正如表达式（5）所指出的那样。
这个反向递归过程可以一直执行一直到我们为 $X$ 找到所有的最优赋值。

动态规划方法计算的可行性依赖于存储与计算时间。
对一个给定的目标方程（在我们这里，即嵌入度量），存储和计算时间的需求是一个变量消去顺序[3]，[7]与每个消去变量维度的函数。
变量 $y_i$ 的维度记为 $|\Gamma(y_i)|$ ，即 $|\Gamma(y_i)|$ 是集合 $\Gamma(y_i)$ （据表达式（4）和（5）所定义）中变量的数量。
对我们考虑的问题而言，所有变量的维度基本都是固定的（即，固定数量的弹簧与每个组件相连并且形成一个对称的互连拓扑），同时该维度独立于变量消去的顺序。
让我们将变量的维度与嵌入方程关联起来，使用 $D(G)$ 来表示在给定消去顺序的情况下，消去变量的最大维度。

在给定消去顺序和所有变量维度固定的情况下，这个嵌入过程需要迭代的应用表达式（4）和（5） $[p-D(G)]$ 次，用于计算 $G$ 的 $p$ 个参数（对应于 $p$ 个组件的嵌入）。
在第 $k$ 次迭代中^[3]，我们计算并保存一个关于 $f_k$ 与 $y_k^*$ 的表。
用以构建第 $k$ 个表的索引项与该表行的数量^[4] $[M^{D(G)}]$ 成正比，并且对每一行，变量的有限数量的可能位置被消除了（用 $w_k$ 表示，其中 $w_k\le M$ ）。
因此，我们每个表只需要 $2\cdot M^{D(G)}$ 个元素（每一行中的两项分别保存 $f_k$ 与 $y_k^*$ 的值），并且需要的计算量至多 $M^{D{G}+1}$ 索引项（与对每个索引项一次或多次的相加和比较）。

如果对所有的 $k$ ， $w_k=w$ ，并且所有的变量都有 $D(G)$ 维，则整个嵌入过程需要的计算正比于
$[p-D(G)](w)[M^{D(G)}]\ 索引项\quad (8)$
临时存储（快速存储）的容量正比于：
$2\cdot[M^{D(G)}]\ 项\quad (9)$
并且静态存储（二阶段存储）的容量（用于在获得最小全局损失之后回溯 $y_i$ 的选择）正比于：
$[p-D(G)][M^{D(G)}]\ 项\quad (10)$

注意我们现在进一步的泛化组件 (component) 的概念。它不再指图中定义的刚性实体，而是可以指任何信息结构或决策过程，这些信息结构或决策过程可以被用于定义一个实值函数，其中，这个实值函数的定义域是感知图像中所有位置的集合。 ↩
公式（2）中定义的 $\{h_i\}$ 独立于所有的 $x_j$ （对所有的 $j>i$ ）；在通用的动态规划算法中定义的 $\{h_i\}$ 可以是任何 $x_j$ 的函数。 ↩
在明确给出 $\Gamma(y_k)$ 中的变量与组件相关嵌入的情况下，第 $k$ 次迭代评价第 $k$ 个组件在 $y_k^*$ 处的嵌入损失。这个嵌入对应于 $y_k$ 的消去。 ↩
相关的限制可以减少可行的行的数量到一个值得注意的值，与不受限制的情形相比。然而，计算问题，试图利用这些减少的行是被禁止的。 ↩

【论文精读】DeepFirearm: Learning Disc
DeepFirearm: Learning Discriminative Feature Representati...
What is AI ?
algorithms enabled by constraints exposed by representati...
2018 · NAACL · BP · Deep Context
2018 · NAACL · BP · Deep Contextualized Word Representati...
Ruby完成FizzBuzz
题目要求 Write a program that outputs the string representati...
Unsupervised Visual Representati
这篇文章的思想是利用self-supervise的思想去运用一些互联网规模的数据集（人工的annotation很难...
[Word2Vec系列] Negative Sampling
http://papers.nips.cc/paper/5021-distributed-representati...
一个整数变成最小2几次方
输入一个数，找出这个数最小的2 n次方比如： 0000 0001 0001 0001 00010001 0001...
BERT模型学习与分析
前段时间Google推出了重磅的模型BERT(Bidirectional Encoder Representati...
recalcitrant 顽固的
title: recalcitrantdate: 2020-07-06 11:14:17NO_sents: 331...
Binary Representation
Binary Representation 今天还是一道有关数学计算的题目，Binary Representati...