组和分组卷积

对称

考虑一个正方形。它是对称的吗?它是如何对称的?它有多少对称性?它有什么样的对称性?

这些问题甚至意味着什么?

如果你问别人,他们可能会告诉你,一个正方形是旋转对称(rotational symmetry)的。如果将方块旋转90°,形状仍然相同。不能给某个角下准确定义,知道那个角是哪个角(如直角三角形中无论怎样旋转,仍然可知哪个角为原来的那个直角),看起来和以前完全一样。你可以把它抬起来,翻转它,然后放下来,它将覆盖完全相同的空间。

我们称之为旋转变换r。准确地说,r 将正方形顺时针旋转90°。例如,

你也可能会被告知,一个正方形具有水平对称(horizontal symmetry)垂直对称(vertical symmetry)。你可以水平或垂直翻转一个正方形,仍然有一个正方形。现在我们来关注一下水平对称。我们称之为横向翻转变换ss在通过正方形中间的垂直线上进行反射。例如,

我们现在有两个变换,r s,将正方形变换为另一个相同形状的正方形。事实证明,这两个变换构成了所有其他变换的“基础”。通过以某种模式使用它们,您可以构建其他变换,例如垂直翻转变换。

从我们原来的正方形开始 原始图像(正向的F)在左下角,下图显示了使用rs以不同的方式组合生成的多种变换。rs由不同颜色的箭头表示。r箭头是蓝色和s 箭头是红色的。

我们可以使用图来模拟如果我们执行一系列转换会发生什么。例如,如果我们旋转,翻转然后再旋转会发生什么?那么,我们从左下角原始的正向F方块开始,并进行如下变换:

最后,我们只剩下原来的只是水平翻转版本:

如果我们想表达这个令人惊讶的事实,我们可以使用乘法符号:

如果我们想要更抽象地思考我们的图,我们可以将所有的方块表示为由r变换的原始方块rs。例如:

在这里,e身份转换,根本不转换对象。例如:

(为什么有e如果它什么都不做呢?这很像是数字零。)

我们可以进一步。原始的正向F方块,在下式中似乎有点不必要:

为什么不直接说 rsr=s ?无论是在方程式还是在我们的图表中,我们都可以放弃分解该方块。

现在,这是基本的实现:rs可能是其他的东西,我们用完全相同的图表。r可以是顺时针方向旋转90°。s可能是垂直翻转。或许我们可以改用一个完全不同的对象,但这根本不重要,重要的是rs之间的关系,他们如何相互作用。我们在方块上看到的只是这个图形的一种表现形式,这个抽象的图案可能以多种形式出现在现实世界中。

数学家称这些抽象模式组(groups)。有一个专门给他们的整个数学领域。组和像正方形这样的对象之间的连接称为组操作(group actions)

但是...什么是组?

并非所有图形都是组。只有一个非常特殊的图形是。(我们不会在这里给出一个正式的定义,但是我们会引导您对它产生一个较好的大致印象。)

首先,图是有指向的(边是箭头)并具有彩色边缘。在每个顶点,只有一个给定颜色的箭头出来,一个进入。

但是这些图的关键属性更加微妙。我们从一个原始的正向F方块开始创建我们的图。但是,如果我们说原来的方块是什么,已经被变换的方块再变换回来么?

我们所说的哪个位置是“初始”位置是任意的。不管你认为哪个位置是最初的位置,图形都是一样的。从某种意义上说,图形是完全对称的。1想象一下,边缘是可以走路的不同颜色的路径,而您站在其中一个节点上:从您的角度来看,无论您站在哪个节点上,图形都是一样的。无论你在哪个节点上,采取一条红色的路径,一条蓝色的路径,然后一条红色的路径,然后再一条蓝色的路径,将带你回到你开始的地方。

在欧几里德空间,我们通过它们相对于原点的相对位置来推断出点。同样,在我们的组中,我们选择一些起源(例如原始的正向F方块),并通过他们的相对位置谈论点。我们称之为相对位置(如rs,或r^3s),他们都是该组的元素(elements)

就像我们可以添加点的差异向量一样,我们可以一起“加”一个组的元素。当然,这不是实际上的加,而是将这个群体的元素结合起来是一种自然的方式。有时我们通过加法和写两个元素ab来作为a + b的类比来讨论它,而其他时候我们做类似的乘法,写作a⋅b

“加”或“相乘”两组元素实际上与矢量相加非常相似。我们决定图上的一个点是我们的标识元素(原始位置),并找到我们想要增加的两个元素,一个a和b。我们选择从标识到ab的一个路径。然后我们将路径a的起始位置移动到到b的结尾,把我们带到a+ba⋅b的终点处(取决于所选的符号)。

代数视角

(选读部分)

从传统的角度来看,以上几乎是不可分辨的群体理论。通常我们把群体看作是一种抽象。

有很多种数学对象,当你看着更多的数学对象时,一个生物就会看到模式。例如,在算术中,我们看到a\!\cdot\!(b+c) ~=~ a\!\cdot\! b ~+~ a\!\cdot\! c和在集理论,我们看到A\cap (B \cup C) = A\cap B ~\cup~ A\cap C。这个模式还有很多其他的例子,还有很多其他的模式。

人们还注意到,对于一大类物体来说,许多重要的结果是正确的,而且出于同样的原因,它们都是真实的。他们是真的,因为所有的对象都遵守特定的模式。知道一个数学对象服从这个模式就足以证明结果是成立的。

所以,我们将这些模式形式化为我们所说的数学结构2很多人,你可以找到一个很长的维基百科上的代数人的名单。我们可以研究一个数学结构,并且证明这个结构的任何实例的结果。(程序员和计算机科学家可以把这看作是使数学变得多态3

现在我们可以给出一个组的经典定义。如果您遇到问题,请不要担心。

定义: A组 G = (S, ~\cdot~)是集合S配备二进制运算 (~\cdot~),一个将组元素映射到组元素的函数,具有以下属性:

  • 存在一个身份元素,e \in S,使得e\cdot x ~=~ x \cdot e ~=~ x,对所有x \in S
  • 所有元素x \in S中,存在逆元x^{-1} \in S使得x\cdot x^{-1} = x^{-1}\cdot x = e
  • 操作(~\cdot~)是联想的。即 (a\cdot b)\cdot c ~=~ a\cdot (b\cdot c),对所有a,b,c \in S

为什么这些规则?为什么不多或少?那么,我们可以定义一个组或多或少的要求。如果它较弱,要求较少,那么更多种类的对象就会成为群体,我们对群体所作的证明的结果将更为广泛地适用。如果它更强大,有更多的要求,我们会谈论一个更具体的对象,可以证明更多关于它们。在数学中,人们经常像这样平衡普遍性和特异性。

数学家研究弱小和强壮的小组。但是,不知何故,团体是特别的。他们不是太热,他们不太冷,他们是对的。

这看起来有些武断。为什么这些特定的规则是一个特别好的收集?有一件事情我觉得非常有帮助和激励,他们意识到他们和我们把组织当作图表的想法是一样的。标识相当于有一个起始点,逆向可逆向箭头,结合性等同于图的完美对称性。4

三张牌组

考虑三张牌,分别为1,2,3。有一些自然适用于他们的转换。我们将调用前两张卡的切换操作(12)。同样,我们将调用切换第二张牌(23 )的操作。所以,

这两个操作一起产生一个组,3个符号上的对称组S_3

每个组元都是重新排列卡片的一种特殊方式,一种排列。

洗牌

一个有趣的想法是洗牌。当我们洗牌时,我们试图把它们随机排列,随机排列。这意味着我们创建一个概率分布在整个组。

理想情况下,我们的洗牌会给我们一个统一的分配 - 每一个排列都是相同的可能性。但是我们很容易想象一个不完美的洗牌,其中一些排列比其他排列更可能。

当然,如果第一次洗牌没有随机化,我们可以再次洗牌!

一般来说,重复洗牌会导致概率质量扩散,使我们更接近均匀分布。

这应该与“ 理解卷积”文章中的落球示例类似。从根本上说,它们是相同的东西:卷积。

组卷积

在排列上的概率分布的早期可视化是一种混乱。可视化的自然方法是在凯莱图上!

让我们考虑一个非常简单的概率分布。我们应用操作(12)的时间有40%,把我们的卡片换成2,1,3。我们60%

的时间应用操作(23),把我们的卡片换成 1,3,2。这是一个可怕的洗牌,但很容易思考。

为了更清楚一点,让我们把我们描述为在未经调整的卡上的所有概率密度开始1,2,3三张牌(即标识),然后我们应用我们非常愚蠢的洗牌。

当我们洗牌,我们品尝这种分配,得到一些置换一a以概率f(a)

当我们再次洗牌时会发生什么?

好了,我们第一次洗牌,我们得到了一个置换一a以概率f(a)。我们第二次洗牌,我们会得到另一个排列bb以概率g(b)。这两个行为发生概率f(a)g(b)结果是排列c = b\cdot a

为了得到c的实际概率,然而,仅仅看一对让我们变成c的排列是不够的。相反,我们需要总结所有可能的排列组合。这是gf的卷积 (就像功能构成一样,右边先走)。

(g\ast f)(c) = \sum_{b \cdot a = c} g(b)f(a)

代入b = ca^{-1},我们得到:

(g\ast f)(c) = \sum_{a} g(ca^{-1})f(a)

这可以很好地被认为是中间排列的总和,a,看看中间排列的概率,以及把我们带到c所需的排列概率c 从那里。

或者,我们可以替代a = b^{-1}c 要得到:

(g\ast f)(c) = \sum_{b} g(b)f(b^{-1}c)

组卷积的传统定义。(如果让团体操作加成,这就是卷积的正常定义。)

卷积的进一步推广

(这部分是可选的,并且假定比本文其余部分更强的背景,较少的数学倾向的读者可能希望跳过本节。)

卷积的传统定义要求你能够取反,并把每一个元素乘以每一个其他元素。这意味着你需要在一个小组或一个准群体上工作。

但如果切换到定义(g\ast f)(c) = \sum_{b \cdot a = c} g(b)f(a),这似乎更自然,卷积是有意义的几乎任何代数结构与二元算子。当然,你可以谈论monoids,groupoids和类别的卷积。据我所知,没有人真的考虑过这些。6

关于这个的一个可爱的事情是,卷积经常继承被卷积的函数域的代数性质。例如,如果您将函数在关联域上进行卷积,则卷积运算是关联的:

((A\ast B) \ast C)(x) = \sum_{a \cdot b \cdot c = x} A(a)B(b)C(c) = (A\ast (B \ast C))(x)

同样,如果域是可交换的,卷积也是如此。如果它有身份,卷积也是一样。可悲的是,如果域反转,卷积不会得到逆,所以平行于Abelian单变量。

如果数学计算得很好,你可能会怀疑是否有什么理由可以使用这些数据。那么,在“不能倒退”的情况下,monoids的卷积看起来很自然。卷积类别允许一种状态。事实上,我认为你可以非常自然地用分类卷积来描述概率自动机。

结论

这篇文章对群体理论提出了不同寻常的看法。Cayley图已经存在了很长一段时间,但据我所知,作为一种基础,作为一种基础方法,认真对待它们是最近的一个想法,由Nathan Carter在他的著作《Visual Group Theory》中编写。有兴趣的读者可以看看他的书。

群组卷积为讨论涉及概率的许多情况提供了优雅的语言。但是,由于这是一系列关于卷积神经网络的博客帖子,您可能会怀疑我还有其他兴趣。那么,你猜对了。卷积组自然而然地扩展了卷积神经网络,所有的东西都很好地融合在一起。由于卷积神经网络是现在机器学习中最强大的工具之一,这非常有趣。在下一篇文章中,我们将探索这些网络。

下一篇文章在这个系列

这篇文章是关于卷积神经网络及其概括的系列文章的一部分。前两个岗位是熟悉深度学习的人员,而后面的人员应该对每个人都感兴趣。要获取更新,请订阅我的RSS提要

请在下面或旁边评论。拉请求可以在github上进行

致谢

我很感谢Yomna Nasser,Harry de Valence,Sam Eisenstat和Sebastian Zany花时间阅读和评论这篇文章的草稿 - 他们的反馈改进了很多!

我也感谢Guillaume Alain,Eliana Lorch,Dario Amodei,Aaron Courville,Yoshua Bengio和Michael Nielsen讨论群卷积及其在神经网络中的潜在应用。

  1. 请注意,图嵌入不一定是对称的。
  2. 通常人们会谈论代数结构,从代数抽象的数学结构。其他领域也有类似的抽象数学结构,特别是在分析中。例如:度量空间拓扑空间和度量空间(http://en.wikipedia.org/wiki/Measure_(mathematics%29)。但是,它们很少像代数结构一样混在一起。
  3. 这实际上是一个非常深刻的比喻。在编程中,我们经常尝试编写可以处理多种对象的多态函数。在数学中,我们试图对不同类型的数学对象进行多态的证明。该柯里-霍华德同构形式化的程序和证据之间的联系。 (一些程序设计语言,比如Haskell,甚至有类的公共代数结构的实现!) 同样值得注意的是,正如大多数编程中多态的方法给我们提供了子类和超类,代数结构也有“子结构”和“超结构”。
  4. 关联部分有点棘手,特别是因为我们从来没有严格定义我们的“组图”的“完美对称性”。 一个定义是,给定一个循环始于e在图上,((bc)d)... = e,同样的序列也是一个循环,如果它开始于一个点一个a,即(((ab)c)d)... = a。看到这是从相关性来看是非常简单的,但是另一个方向呢? 那么,我们要证明所有的a,b,c,即a(bc) = (ab)c。令d = (bc)^{-1},路径bc取反。那么(bc)d = e是一个循环。由图对称,((ab)c)d = a。我们现在右对齐d^{-1} = (bc)得到(ab)c = a(bc),这是相关性。
  5. 你有多少次洗牌才能真正随机?这个问题是由数学家Persi Diaconis探讨的。
  6. 我不能真正找到人们将这些卷积作为独立的东西来讨论的情况,但是这个操作似乎被隐含地构造在研究这些结构的对象上。就像乘法群环是组卷积,乘法幺半环是幺卷积,乘法广群代数的广群卷积和乘法分类代数是类卷积。

本文的版权归 abtion 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

比较不同的对单细胞转录组数据聚类的方法

背景介绍 聚类之前必须要对表达矩阵进行normalization,而且要去除一些批次效应等外部因素。通过对表达矩阵的聚类,可以把细胞群体分成不同的状态,解释为什...

85012
来自专栏封碎

当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

2152
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4164
来自专栏数据结构与算法

2853 方格游戏(三维棋盘)

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 菜菜看到了...

3586
来自专栏数说工作室

机器学习/深度学习代码速查:6大工具库 &27种神经网络图览

Kailash Ahirwar,Mate Lab 联合创始人,Github的一位资深作者,也是一位活雷锋,近日在其Github个人主页上发表了一个机器学习/深度...

5095
来自专栏潇涧技术专栏

Numerical Methods using Matlab

内容包括:基本幂法,逆幂法和移位幂法,QR分解,Householder变换,实用QR分解技术,奇异值分解SVD

1022
来自专栏张善友的专栏

EMA算法的C#实现

EMA表示的是指数平滑移动平均,其函数的定义为Y=EMA(X,N) 则Y=[2*X+(N-1)*Y']/(N+1), 其中Y'表示上一周期Y值。 求X的N日指数...

4295
来自专栏机器之心

EMNLP 2018 | 结合通用和专用NMT的优势,CMU为NMT引入「语境参数生成器」

神经机器翻译(NMT)无需单独训练或调整系统的任何部分就可以直接建模源语言到目标语言的映射。这使得 NMT 快速发展,并在许多大规模环境中成功应用 (Wu et...

1321
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(六)No.57

照例甩一波链接。 大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.5...

2036
来自专栏刘望舒

算法(一)时间复杂度

前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的...

1948

扫码关注云+社区

领取腾讯云代金券