量子那些事儿 关注
手机版

量子人工智能笔记之量子深度学习

  1. 云栖社区>
  2. 量子那些事儿>
  3. 博客>
  4. 正文

量子人工智能笔记之量子深度学习

雪花又一年 2018-05-15 15:03:34 浏览275 评论0

摘要: 这是系列文章的第一篇,主要介绍weibe 基于经典玻尔兹曼机的工作。 Quantum Deep Learning (arxiv:1412.3489) 原问题 量子计算机和量子算法的出现会给机器学习领域带来什么样的变革,为什么会带来这样的变革?原理是什么?的回答以及后续更新就在这里写了。

这是系列文章的第一篇,主要介绍weibe 基于经典玻尔兹曼机的工作。 Quantum Deep Learning (arxiv:1412.3489)


原问题 量子计算机和量子算法的出现会给机器学习领域带来什么样的变革,为什么会带来这样的变革?原理是什么?的回答以及后续更新就在这里写了。

之前有段时间在看实验实现有没有可能,找了老师讨论后来发现现在还做不了。Quantum Deep Learning 里其实是介绍的是Boltzman Machine(以后简称BM)的训练方法, 用量子的训练方法代替经典算法中的CD-k(contrastive divergence,对比散度)算法在时间复杂度上有了很好的提升, 使得大规模训练全连接的BM有了可能. 作者也在后面模拟了用这两个算法训练全连接网络。当然了, 并不能像Shor算法一样带来令人振奋的指数加速...但是这个复杂度的优化应该也是很好的了。


首先先简单介绍一下BM来凑个字数吧。BM是一种概率型神经网络,它来自于物理学中的Ising模型,是组成深度可信网络的单元。它在分类(比如用于Netflix的视频分类中有着比较好的效果 Restricted Boltzmann Machines for Collaborative Filtering)等领域里都有很好的应用。

最初利用类似于模拟退火的方法进行抽样来完成训练,它的目标是通过训练获得一种分布从而使得能量O_{ML}最低,其中某一种状态(v,h)出现的概率为

P(v,h) = e^{-E(v,h)}/Z

其中

E(v,h) = -\sum_{i} v_i b_i -\sum_{j} h_j d_j - \sum_{i,j}\omega_{i,j}^{vh}v_i h_j - \sum_{i,j}\omega_{i,j}^{v} v_i v_j -\sum_{i,j} \omega_{i,j}^{h} h_i h_j

Z是配分函数,我们的训练目标是使得这个函数最小:


O_{ML} := \frac{1}{N_{train}}\sum_{v\in train}\log(\sum_{h=1}^{n_h}P(v,h))-\frac{\lambda}{2}\omega^T\omega

(v,h)代表这个系统的某个状态(每个unit的某一种赋值),这里P是某个状态出现的概率。

传统的算法是想办法或得这个梯度然后用类似于梯度下降的方法来达到极值,量子算法的思路也差不多。所以参数更新的公式就是

\frac{\partial O_{ML}}{\partial \omega_{ij}} = \langle v_i h_j \rangle_{data} - \langle v_i h_j\rangle_{model}-\lambda \omega_{ij}

最原始的方法是用类似于模拟Ising模型的方法(通过Gibbs抽样)来训练,但是这样的性能很差,后来有了CD-k,PCD算法。但是以上算法都因为性能原因无法非常有效地计算全连接的玻尔兹曼机。于是就有了RBM(受限玻尔兹曼机),就是将一些单元之间的连接人为地去掉,这样训练起来就快了不少。

用量子比特来表示玻尔兹曼机思路上并不复杂,因为玻尔兹曼机实际上来自于物理中的Ising模型,所以利用本身就是以一定概率出现0和1的量子比特来表示玻尔兹曼机的单元(unit)是再合适不过的了。

然后从Nathan的文章里盗个表出来, 看看到底优化到什么程度:

5ca9f124245dfba5b1ef1935cfc438b4_hd.jpg


解释一下, 那个\epsilon 和精度相关. n_h是指hidden unit的个数, n_v是指visible unit的个数,l是网络的层数,E是边的数目. 这个算法并没有改BM的结构, 只是加速了训练方法. 当然这个东西还跑不起来, 比特数要求有点高. 以后实验上就很难做了。

这个算法是在最原始的BM训练方法Gibbs抽样的基础上改进的,并且CEQS和CEQAE两种算法都是exact的。也就是误差(error)的来源只有抽样(sampling),对比特数目和物理资源的需求也没有出现指数增长。比较吸引人的一点可能在于算法本身的时间复杂度与层数无关(没有l),所以在用来训练深层网络的时候表现可能会很好,而常用的CD-k算法的时间复杂度会随着网络层数上升。当然目前这个算法离实验实现还很远,比特数目还不够用。

为什么说没有改变BM的结构呢。因为要优化的函数没变还是上面的这个函数
O_{ML} := \frac{1}{N_{train}}\sum_{v\in train}\log(\sum_{h=1}^{n_h}P(v,h))-\frac{\lambda}{2}\omega^T\omega

但是我们的训练目标是获得这样一个量子态

\sum_{v,h}\sqrt{P(v,h)}|v\rangle|h\rangle

而Nathan的算法就是给出了一种近似计算出前面这个振幅的算法。它可以被量子计算机在多项式时间内算出来。

上一次写到了经典的玻尔兹曼机。这一篇继续往下写。因为主要是定理什么的这一章感觉主要就是在翻译了,我稍微调整了一下顺序。欢迎讨论~

如何训练出目标的概率分布,也就是目标的量子态\sum_{v,h}\sqrt{P(v,h)}|v\rangle |h\rangle呢?

首先想要直接获得\sum_{v,h}\sqrt{P(v,h)}|v\rangle |h\rangle是很困难的,因为P = \frac{e^{-E(v,h)}}{Z},而下面这个Z,也就是配分函数是很难计算的(需要把可能的状态都加起来)。于是Nathan使用了平均场近似大法,来获得一个好算一些的分布函数Q,使得我们可以用其它量来近似计算目标量子态。

平均场近似是这样的(注意这里的v\upsilon不是一个东西...一个是visible unit的值还有一个是平均场近似的参数):

对分布

Q(v,h)=(\prod_i \mu_i^{v_i}(1-\mu_i)^{1-v_i})(\prod_j \upsilon_j^{h_j}(1-\upsilon_j)^{1-h_j})

其中\mu_iv_j是使得下面这个式子(KL(Q||P))最小的数。参数\mu_iv_j被称为平均场系数。

\begin{aligned} KL(Q||P) &= \sum_{v,h}-Q(v,h)\ln(P(v,h))+Q(v,h)\ln(Q(v,h))\\ &=\sum_{v,h}Q(v,h)(\sum_i v_i b_i +\sum_j h_j d_j +\sum_{i,j}\omega_{i,j}v_i h_j +\ln{Z})\\ &=\sum_{i}\mu_ib_i+\sum_{j}v_jd_j+\sum_{i,j}\omega_{i,j}\mu_i v_j+\ln(Z)\\ &\quad\quad\quad + \sum_i \mu_i\ln(\mu_i)+(1-\mu_i)\ln(1-\mu_i)+\sum_{j}v_j \ln(v_j)+(1-v_j)\ln(1-v_j) \end{aligned}

这个函数的最小值在\mu_i = \sigma(-b_i-\sum_j \omega_{i,j}v_j)\\ v_j = \sigma(-d_j-\sum_i \omega_{i,j}\mu_i)

处取到

定义一

于是有了Q,我们就可以定义由Q所得到的配分函数,定义

Z_Q := \sum_{v,h} Q(v,h)\log(\frac{e^{E(v,h)}}{Q(v,h)})

然后对和训练集连接的节点(也就是训练数据接入的那个节点),有

Z_{x,Q}:=\sum_h(x,h)\log(\frac{e^{-E(x,h)}}{Q_x(x,h)})

不过呢,为了用量子算法来通过平均场近似的分布函数Q获得真正的分布P,我们还需要知道这个配分函数带来的近似在Q中占的比例

定义二

记常数\kappa>0,并且对所有可见和不可见的结构(configurations)(v,h)都有

\frac{e^{-E(v,h)}}{Z_Q}\leq \kappa Q(v,h)

同样还可以对训练集定义

定义三

记常数\kappa_x>0,并且对所有的隐藏结构(hidden configurations) h 和 x\in x_{train} 满足

\frac{e^{-E(x,h)}}{Z_Q}\leq \kappa_x Q_x(x,h)

从这几个定义可以推出这样几个引理,具体证明就不记了,证明也挺短的,对学物理的来说也许结论更有用一点

引理一

P(v,h)\leq \frac{e^{-E(v,h)}}{Z_Q}\leq \kappa Q(v,h)

引理二

玻尔兹曼机可以以\frac{Z}{\kappa Z_Q}的概率制备出来。这个还是需要看一下证明的:

证明:

假设我们已经获得了平均场近似的参数\mu_i\upsilon _j。那么就确定了平均场分布Q。通过一系列的单比特旋转,我们就可以获得这样一个量子态(Q可以用来获得P)

|\psi_Q\rangle:= \prod_i R_y (2 \arcsin(\sqrt{\mu_i}))|0\rangle \prod_j R_y (2\arcsin(\sqrt{\upsilon_j}))|0\rangle = \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle

然后容易看出来

\sum_{v,h}\sqrt{Q(v,h)\mathbf{P}(v,h)}|v\rangle|h\rangle = \sqrt{\frac{Z}{\kappa Z_Q}}\sum_{v,h}\sqrt{\frac{e^{-E(v,h)}}{Z}}|v\rangle|h\rangle=\sqrt{\frac{Z}{\kappa Z_Q}}\sum_{v,h}\sqrt{\mathbf{P}(v,h)}|v\rangle |h\rangle

下面就剩下用rejection sampling (应该翻译成拒绝抽样?),记(知乎上没找到打花体P的命令mathscr不能用的说,用加粗代替了...)

\mathbf{P}(v,h) := \frac{e^{-E(v,h)}}{\kappa Z_Q Q(v,h)}

因为QZ_Q都能被有效计算出来(参看前面,在量子计算机里都不是指数增长的操作数),所以这里的\mathbf{P}也能被有效地计算出来。并且引理一也保证了0\leq \mathbf{P}(v,h)\leq 1。然后思路大致就是增加一个辅助比特和一个寄存比特,假如能有\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle|0\rangle那么就可以通过对最后的辅助比特做一个控制旋转操作(类似于CNOT的一个东西),就能得到

\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle|0\rangle\rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle(\sqrt{1-\mathbf{P}(v,h)}|0\rangle+\sqrt{\mathbf{P}(v,h)}|1\rangle)

而后面那个东西就是我们要的东西咯,于是对辅助比特进行测量,扔掉结果为0的量子态,就可以获得目标的量子态了。而这个的成功概率就是\frac{Z}{\kappa Z_Q}

然后类似地,我们也知道了如何获得(x,h)的玻尔兹曼机的目标量子态。


铺垫差不多结束了,下面是写具体的算法。


我们来看数据是具体怎么参与到它的训练中去的。这一章也有不少部分会翻译自Nathan的原始文献,如果觉得翻译的不好可以去读一下原文,然后给我留言。我会学习一下然后修改的,因为伪代码里有公式,并不能用知乎的代码格式,所以手机显示可能没有源码代码里的对齐。。。

第一个算法是生成model state的算法

首先平均场近似的系数可以通过前面的方法算出来(参见平均场近似),然后就有Q:

Q(v,h)=(\prod_i \mu_i^{v_i}(1-\mu_i)^{1-v_i})(\prod_j \upsilon_j^{h_j}(1-\upsilon_j)^{1-h_j})

这样我们就可以计算引理里的Z_Q。下面是获得模型态的伪代码:

# 输入是几个玻尔兹曼机的基本参数,模型的权重矩阵是omega,可见单元偏移(biases) b,隐藏单元的偏移 d, 边集合E,和\kappa
function qGenModelState(\omega,b,d,E,\kappa)

# 通过输入的参数来计算平均场的系数
mu, v = gen_meanfield_para()
# 计算平均场近似后的配分函数
Z_Q = meanfield_partition(mu,v)
# 制备初态

\sum_{v,h} \sqrt{Q(v,h)}|v\rangle|h\rangle := (\prod_{i=1}^{n_v} e^{-i\sqrt{\mu_i} Y}|0\rangle)(\prod_{j=1}^{n_h}e^{-i\sqrt{v_j}Y}|0\rangle)

# 添加寄存比特用来寄存能量值,并且初始化为 0

\sum_{v,h} \sqrt{Q(v,h)} |v\rangle |h\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |0\rangle

# 后面一系列循环都是为了将来通过测量辅助比特来获得我们在引理里提到的要获得的玻尔 # 兹曼机态,注意他是怎么把概率幅给导出一个带有配分函数的形式的,最后要用到前文提 # 到的控制旋转,参见 量子深度学习笔记(二)或者原文的Lemma 2,这里的辅助比特也 # 需要不止一个,所以实验上就很难做了

for i = 1 : n_v

\sum_{v,h} \sqrt{Q(v,h)} |v\rangle |h\rangle |E(v,h)\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |E(v,h)+v_i b_i +\ln (\mu_i^{v_i} (1-\mu_{i})^{1-v_i})\rangle

end

for j = 1:n_h

\sum_{v,h} \sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)\rangle \rightarrow\sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |E(v,h)+h_j d_j +\ln (\mu_i^{v_i}(1-\mu_i)^{1-h_j})\rangle

end

for (i,j)\in E

\sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle|E(v,h)\rangle\rightarrow\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)+v_i h_j \omega_{i,j}\rangle

end

# 最后总的来讲我们最后制备出了这样一个态\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle|E(v,h)\rangle (\sqrt{\frac{e^{-E(v,h)}}{Z_{Q}\kappa}}|1\rangle+\sqrt{1-\frac{e^{-E(v,h)}}{Z_Q\kappa}}|0\rangle)

end

然后对data state,也是用同样的方法(把\kappa换成\kappa_x,可见单元的值用x代替即可),我们叫这个函数为 qGenDataState

然后我们知道,梯度是这么算的:

\frac{\partial O_{ML}}{\partial \omega_{i,j}} = \langle v_ih_j\rangle_{data}-\langle v_ih_j\rangle_{model}-\lambda\omega_{i,j}

注意这个式子和经典的玻尔兹曼机完全一样,套用就好了,所以我们最终的训练算法是这样的

for i = 1:N_train

success = 0

while success = 0

|\psi\rangle = qGenModelState(\omega,b,d,E,\kappa)

# 测量辅助比特

success = measure_ancilla_qubit(|\psi\rangle)

 end

modelVUnits[i] = 测量可见比特的结果

modelHUnits[i] = 测量隐藏比特的结果

success = 0

while success = 0

|\psi\rangle = qGenDataState(\omega,b,d,E,\kappa,x[i])

success = measure_ancilla_qubit(|\psi\rangle) # 测量的是最后一个辅助比特,那个前面带了 分布函数的

end

dataVUnits[i] = 测量可见比特的结果

dataHUnit[i] = 测量隐藏比特的结果

end

最后逐个计算梯度

for (i,j) in v,h # 对每个可见和隐藏节点

gradMLw[i,j] = r(\frac{1}{N_{train}}\sum_{k=1}^{N_{train}} (dataVUnits[k,i]dataHUnits[k,j]-modelVUnits[k,i]modelVUnits[k,i]modelHUnits[k,j]-\lambda\omega_{i,j})

gradMLb[i] = r(\frac{1}{N_{train}}\sum_{k=1}^{N_{train}}(dataVUnits[k,i]-modelVUnits[k,i]))

gradMLd[j] = r(\frac{1}{N_{train}}\sum_{k=1}^{N_{train}}(dataHUnits[k,i]-modelHUnits[k,i]))


end


有了梯度以后,其余的就可以在经典的环境下进行了。所以我们可以看到这个算法并没有对玻尔兹曼机进行修改,所以作者也就没有称为量子玻尔兹曼机(这是另外一个工作),这个工作需要有一个量子的RAM,也就是类似于内存的东西来寄存能量数值,于是对于实验实现的要求很大。

因为个人时间的原因,后面可能会继续更一下算法的代码实现,不过大约会拖到很久以后了...


原文发布时间为: 2016-11-13
本文作者:罗秀哲
本文来源:创见,如需转载请联系原作者。

用云栖社区APP,舒服~

【云栖快讯】云栖社区技术交流群汇总,阿里巴巴技术专家及云栖社区专家等你加入互动,老铁,了解一下?  详情请点击

网友评论

雪花又一年
文章1320篇 | 关注25
关注
阿里云机器学习是基于阿里云分布式计算引擎的一款机器学习算法平台。用户通过拖拉拽的方式可视化的... 查看详情
是基于语音识别、语音合成、自然语言理解等技术,为企业在多种实际应用场景下,赋予产品“能听、会... 查看详情
用于实时预测用户对物品偏好,支持企业定制推荐算法,支持A/B Test效果对比 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
建站4折

建站4折