请选择 进入手机版 | 继续访问电脑版

大唐名人网

 找回密码
 暂停注册
大唐名人网 门户 IT 查看内容

欲把传统CPU挑下马,概率芯片是如何计算的?

2016-5-3 13:29| 发布者: admin| 查看: 314| 评论: 0

  顾险峰 (纽约州立大学石溪分校终身教授,清华大学丘成桐数学科学中心访问教授,计算共形几何创始人)

  4月20日,Intel宣布计划裁员1.2万人,公司接下来将进行费用高达12亿美元的重组,这一消息震惊了整个芯片产业,同时宣告了芯片产业中不可逆转的趋势:随着以深度学习为代表的人工智能技术走向主流,占据市场几十年的CPU可能被拉下王座;成本更低的FPGA、能够以更快速度处理数据的GPU、能够以更大并行度进行计算的概率芯片和其他更多采用全新架构的(专用)处理器争夺市场的时代即将来临。这里,我们简要介绍一下概率芯片的数学基础,比较一下基于传统CPU的算法和概率算法的异同。我们用常见的偏微分方程算法为例来说明。

欲把传统CPU挑下马,概率芯片是如何计算的?

图1. 黎曼映照,保持布朗运动

  1 经典算法

  从理论上而言,几乎所有物理规律的终极形式都是偏微分方程,现代几何中的基本定理也是依赖于微分方程。工程上,许多问题都是以微分方程为基本工具。例如,计算数学家Stanley Osher学派提出了用偏微分方程来做图像处理的水平集法(Level Set Method),应用广泛,影响深远。

欲把传统CPU挑下马,概率芯片是如何计算的?

  图2. 泊松图像编辑

  例如Photoshop中的抠图和贴图功能就是基于椭圆型偏微分方程-泊松方程。如图2所示,我们用表示前景图片,表示背景图片。是前景图片中的一个区域,例如人物覆盖的区域。泊松图像编辑的方法是将前景图像的梯度信息和背景图像的边缘信息相融合,生成新的图像,满足如下的泊松方程:

  这里拉普拉斯微分算子定义为:

  根据经典的偏微分方程理论,泊松方程解法如下。首先我们定义区域关于拉普拉斯算子的特征根和特征函数:

  这里特征根构成区域的谱

,

  由此我们构成区域的热核

  ,

  在初始时刻,热核实际上是狄拉克函数,

  热核关于时间的积分给出了格林函数

,

  泊松方程的解由格林函数给出:

  一般情形,格林函数并没有简单的显式表达。如果区域为单位圆盘,格林函数具有显式形式。我们首先构造辅助函数:

  格林函数为

  一般平面区域,存在黎曼映照将区域保角映到单位圆盘。黎曼映照保持角度不变,但是使得面元发生畸变。我们可以直接证明,保角变换保持泊松方程形式不变,从而我们可以写下显式解。

欲把传统CPU挑下马,概率芯片是如何计算的?

  图3. 一般的微分同胚,不保持布朗运动

  但是,在实际应用中,黎曼映照无法显式表达,我们只能使用数值逼近方法。在传统的有限元方法中,我们将平面区域三角剖分,然后将函数用分片线性函数逼近,拉普拉斯算子用稀疏正定矩阵近似,泊松方程被转换成线性方程组。我们再用线性代数方法求解线性方程。这一计算框架非常适合传统的CPU系统结构,但是数据结构和算法设计复杂而困难。

欲把传统CPU挑下马,概率芯片是如何计算的?

图4. 泊松点云重建曲面

  在几何处理领域,现实生活中的曲面经过扫描被转换成三维点云,点云融合后再被三角剖分,生成封闭的曲面。从点云重建曲面也是依赖于求解泊松方程。我们可以不夸张地说,椭圆型偏微分方程在工程领域中随处可见。

  2 概率算法

  概率算法的思路和经典的偏微分方程解法迥然不同。从物理角度而言,热力学的宏观现象由线性椭圆型偏微分方程来描述,微观现象可以用布朗运动来解释,因此通过模拟布朗运动,我们可以解偏微分方程。这正是所谓蒙特卡洛方法的核心想法。

  布朗运动具有如下的特征:我们假设有一个粒子在直线上做布朗运动,在时刻粒子的位置为,那么

  1.   在时刻0,粒子的位置在原点,;

  2.   增量独立性:如果,那么和随机过程相互独立;

  3.   增量正态分布:随机变量正态分布;

  4.   路径连续:以概率1为时间 的连续函数。

  如果粒子在高维空间中运动,每个分量为一维的布朗运动,则粒子的运动被称为是高维布朗运动。

  布朗运动的一个本质特征是各向同性:在每一刹那,粒子向各个方向前进的概率相同。观察图2的黎曼映照,我们可以得出共形(保角)映射将无穷小圆映成无穷小圆,局部上共形映射就是相似变换,换言之共形映射诱导的切空间之间的线性映射是相似变换。因此,共形变换将二维布朗运动映成布朗运动,但是时间参量会发生相应变化。

  我们考察下面的实例: 假设是平面区域,是区域边界上的一段弧,粒子从内点出发做布朗运动,粒子首次到达边界的概率为。根据布朗运动的性质,我们取一个小圆围绕内点,从p出发的布朗运动以等概率到达小圆上的任意一点,然后再从小圆上的点到达边界,这两段布朗运动彼此独立。由此,我们得到:

,

  这意味着概率满足均值条件,因此必为调和函数,我们可以将其表述成狄里克雷问题:

  。

欲把传统CPU挑下马,概率芯片是如何计算的?

  图5. 布朗运动

  如果应用布朗运动共形不变性,我们可以计算黎曼映照,将p点映到圆心,将映到,则根据对称性所求概率为的长度除以,即。

欲把传统CPU挑下马,概率芯片是如何计算的?

  图6. 曲面由三角网格逼近

  如果我们直接模拟布朗运动,则算法如下。首先,我们将平面区域三角剖分,然后在三角网格上模拟随机行走。我们为每条边配上权重,假设一条边连接两个顶点和, 同时此边与两个面和相邻,则其权重定义为

  粒子在三角网格上作随机行走,假设在时刻粒子停留在顶点处,在时刻,粒子经过一条边到达的一个相邻顶点, 其概率正比于边上的权重:

  在计算过程中,每一步我们只需要生成一个均匀分布的随机数,然后决定走哪一条边,就可以模拟随机行走。我们可以模拟n条从p点出发的随机行走,如果m条到达,那么所求概率近似为

  由此,我们得到了狄里克雷问题的概率解法。

  从经典偏微分方程理论中,我们可以看出求解椭圆型和抛物型偏微分方程的关键在于构造热核,热核具有概率解释:从点p出发的随机行走在时刻t到达点q的概率。因此,从理论上讲,如果我们能够模拟随机行走,则我们能够计算热核,从而求解椭圆型和抛物型偏微分方程。

  物联网应用

  我们再来看物联网领域的一个应用:追查网络造谣者。假设平面区域上分布一些传感器,传感器可以彼此近距离通讯,从而构成通讯网络。假设网络内部有一个谣言制造者,不停地散布谣言,谣言在网络中传播。为了隐藏自己的位置,这个造谣者采用随机行走的路由策略。每一个传感器得到消息后,随机地将消息传递给自己的一个邻居。人们一直以为这种随机路由是安全的,可以完美地隐藏造谣者的位置信息。其实,这种盲目乐观的看法是错误的,我们可以用如下的方法找出造谣者的位置:假设造谣者位于点p,网络边缘被监控,我们可以得到从p点出发到达网络边缘q点的频率即概率,记为,可以证明点p的坐标等于随机行走到达边缘点位置的期望值,

  因此,用随机路由,我们可以轻易找到造谣者的位置。

  几何应用

  热核由黎曼度量所决定,不同的黎曼度量将会改变三角剖分中边上的权重。反过来,黎曼度量的所有信息都由热核反映出来,任意两点间的测地距离可以由热核计算

  这意味着等距映射保持热核。因此随机行走完全决定了热核,从而决定了黎曼度量

  我们来看如何用随机行走计算图1中的映照。首先我们将人脸边缘映到单位圆盘上;然后通过模拟随机行走计算从一个内点p到达任意一个边界点q的概率,那么调和映照由卷积给出:

  如果背景空间是二维曲面并且无穷大, 我们考察从原点出发的随机行走。这一随机行走有可能一去不复返,也有可能不停地故地重游。这取决于背景空间的曲率,一去不复返的空间被称为是暂态的,故地重游的空间被称为是常返的。暂态的空间曲率为负,常返的空间曲率为零。由此,随机行走的渐进行为反映了无穷大背景空间的弯曲。例如图7,我们看到空间被天使和恶魔周期性地覆盖。我们把每个周期视作一个点,相邻的周期间加一条边,从而得到无限大的图(Cayley Graph)。随机行走在左图中是常返的,在右图中是暂态的,这意味着左图的空间曲率为非负,右图的空间曲率为负。

欲把传统CPU挑下马,概率芯片是如何计算的?

  图7. 常返空间和暂态空间

  同经典的有限元方法相比,随机行走的概率方法具有很多优点:算法逻辑异常简单,不需要复杂的数据结构,不需要数值代数计算;计算精度可以通过模拟不同数目的随机行走自如控制;不同的随机行走相互独立,可以大规模并行模拟;模拟过程中,不需要全局信息,只需要网络的局部信息。相比于传统的数值偏微分方程方法,空间中的随机行走非常容易用计算机编程模拟,例如蒙特卡洛方法。因此用简单的算法,我们可以得到复杂的几何信息。但是,这一类方法的收敛速度相对较慢,为了提高10倍的精度,我们需要增加到100倍随机行走。

  用经典的CPU体系结构进行概率运算,相当于用高射炮打蚊子,一方面大材小用,另一方面笨拙臃肿。为了不同的应用,例如图像处理,而设计的概率芯片可以极大地发挥概率算法简单并行的特点,极大地提高系统性能。依随Intel的重组,我们再次体会到山雨欲来风满楼的紧迫感:传统CPU体系机构独霸江山的时代将一去不复返,概率芯片和其他更多采用全新架构的专用处理器分庭抗礼的时代即将来临!

延伸阅读

  ①纯粹数学的雪崩效应:庞加莱猜想何以造福了精准医疗?

  Magic Leap 核心技术揭秘

  ③ 纯粹数学走出象牙塔:丘成桐和三维科技有何关系?

  投稿、提供新闻线索、转载授权请联系:iscientists@126.com

  商务合作事宜请联系:dll2004@163.com

  更多精彩文章:您可以回复"年份+月份",如201510即可获取月度文章,或返回主页点击子菜单获取最新文章、往期文章或直达赛先生微博。谢谢!

微信号:iscientists


相关阅读

投稿、合作、联系:admin2#tangedu.cn| 小黑屋|网站地图|大唐名人网 |京ICP备07504790号|

GMT+8, 2022-1-28 00:43 , Processed in 0.114393 second(s), 23 queries .

Powered by Discuz!

© 2001-2015 Comsenz Inc.

返回顶部