2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

间接互惠与合作演化的若干问题研究进展

张艳玲 刘爱志 孙长银

陈旭, 万九卿. 基于结构化预测的细胞跟踪方法. 自动化学报, 2017, 43(3): 376-389. doi: 10.16383/j.aas.2017.c160039
引用本文: 张艳玲, 刘爱志, 孙长银. 间接互惠与合作演化的若干问题研究进展. 自动化学报, 2018, 44(1): 1-12. doi: 10.16383/j.aas.2018.c170200
CHEN Xu, WAN Jiu-Qing. Cell Tracking Using Structured Prediction. ACTA AUTOMATICA SINICA, 2017, 43(3): 376-389. doi: 10.16383/j.aas.2017.c160039
Citation: ZHANG Yan-Ling, LIU Ai-Zhi, SUN Chang-Yin. Development of Several Studies on Indirect Reciprocity and the Evolution of Cooperation. ACTA AUTOMATICA SINICA, 2018, 44(1): 1-12. doi: 10.16383/j.aas.2018.c170200

间接互惠与合作演化的若干问题研究进展

doi: 10.16383/j.aas.2018.c170200
基金项目: 

国家自然科学基金 61520106009

中央高校基础科研业务费 FRF-TP-15-116A1

国家自然科学基金 61603036

国家自然科学基金 61533008

中国博士后科学基金 2015M580989

详细信息
    作者简介:

    张艳玲北京科技大学自动化学院师资博士后.2014年获得北京大学一般力学与力学基础专业博士学位.主要研究方向为演化博弈动力学.E-mail:yanlzhang@ustb.edu.cn

    刘爱志北京科技大学博士研究生.2014年获得北京科技大学硕士学位.主要研究方向为复杂系统建模和演化博弈动力学.E-mail:ustb_laz@xs.ustb.edu.cn

    通讯作者:

    孙长银东南大学自动化学院教授.主要研究方向为人工智能, 神经网络, 智能控制理论与方法, 模式识别.本文通信作者.E-mail:cysun@seu.edu.cn

Development of Several Studies on Indirect Reciprocity and the Evolution of Cooperation

Funds: 

National Natural Science Foundation of China 61520106009

Fundamental Research Funds for the Central Universities FRF-TP-15-116A1

National Natural Science Foundation of China 61603036

National Natural Science Foundation of China 61533008

China Postdoctoral Science Foundation 2015M580989

More Information
    Author Bio:

    The teachers postdoctoral at the School of Automation and Electrical Engineering, University of Science and Technology Beijing. She received her Ph. D. degree from Peking University in 2014. Her research interest covers evolutionary game dynamics

    Ph. D. candidate at the School of Automation and Electrical Engineering, University of Science and Technology Beijing. He received his master degree from University of Science and Technology Beijing in 2014. His research interest covers complex system modeling and evolutionary game dynamics

    Corresponding author: SUN Chang-Yin Professor at the School of Automation, Southeast University. His research interest covers artiflcial intelligence, neural networks, theory and design of intelligent control systems, and pattern recognition. Corresponding author of this paper
  • 摘要: 2005年Science杂志指出"合作行为如何进化"是21世纪最关键的25个科学问题之一.间接互惠如何促进合作演化的研究已吸引了包括经济学家、社会学家和演化生物学家等众多学者的关注.这是由于:人类社会道德的形成、社会化分工、语言的出现、人类大脑的进化等都和间接互惠密不可分;随着经济全球化和网络时代的到来,依赖声望和信誉的陌生个体间的交易日益频繁,局部信息条件下个体的信任被利用的"道德风险"逐渐增大.本文所关注的间接互惠是以声望为核心的"下游互惠",具体而言,个体通过帮助他人建立自己在群体中的好声望,从而期待未来获得他人的帮助.可见,声望是"下游互惠"发挥作用的关键.声望的建立引发了两方面的研究:1)如何评价个体声望的好与坏,焦点是何种声望评估准则能够促进合作的演化;2)个体的声望如何在群体中快速、准确、广泛地传播,使得陌生个体间能够获得彼此的声望信息,其中八卦这种声望传播方式成为间接互惠的研究热点之一.基于声望的间接互惠研究前景广阔,未来可能的研究方向主要有复杂网络上的间接互惠、声望传播系统的鲁棒性、声望共享系统的建立和间接互惠在P2P网络中的应用.
  • 在计算机视觉和模式识别领域, 输入数据的维数过高会增加计算的复杂度, 使得对数据的处理变得困难.为了降低数据的维数, 通常采用矩阵分解的方法.矩阵分解的方法将数据矩阵分解成多个矩阵的形式, 其中一个矩阵可以很好地逼近原始矩阵, 在保留原始信息的条件下, 同时可以从高维到低维的映射, 学习更好的特征描述方法.这样这种矩阵分解的方法有多种, 如SVD (Singular value decomposition)、QR分解、NMF (Nonnegative matrix factorization)等.

    NMF可以将原始数据分解为基矩阵和系数矩阵的乘积.基矩阵的作用类似人脸的各个不同局部块的描述, 系数矩阵为原始数据在这些基向量的线性组合的权重.对于给定的数据矩阵$X$, 在学习到对应的基矩阵$U$之后, 对应的系数矩阵$V$便可以描述原始矩阵.最近的研究表明, NMF在人脑识别等领域已经超过基于SVD的方法[1-3].

    虽然单视图的NMF提高了原始数据的有效性, 但是图像可以从不同的视图进行描述.这些视图可以是不同的数据集, 也可以是侧重于不同角度的特征提取方法, 所以, 这些视图具有多种特征:有的是视觉底层特征、有的是视觉美学特征, 甚至有中层语义特征.这些特征往往可以互补地描述图像[4], 因此, 多视图学习相比较于单视图的方法能更有效地利用视图之间的互补信息.而在实例检索[5]任务上, Multi的思想[6]也被用于获得更加精确的检索效果.目前, 利用多视图来进行聚类分析的方法主要有两种:多视图谱聚类和多视图K均值聚类.其中, 多视图谱聚类有文献[7-11]等.虽然这些方法性能的相比单视图的谱聚类有所提高, 但是多视图谱聚类需要为每一个视图都计算亲和矩阵, 视图越多, 计算的复杂度也更大.相比之下, 多视图K均值聚类不需要计算亲和矩阵, 只需要利用原始特征即可.多视图K均值聚类又分为基于指示矩阵的方法和基于NMF矩阵分解的方法.基于指示矩阵的方法有RMKMC[12]和DEKM (Discriminatively emmbedded K-means)[13]等, 这种方法是从样本角度来形成聚类质心, 且这种方法的准确率依赖于指示矩阵的初始值.而基于NMF矩阵分解的方法是从维数的角度来进行降维, 从而形成聚类质心.具体地, 关于矩阵分解多视图学习方面的研究有很多:在文献[14]中, Kumar等利用全局和局部2种视图的特征, 提高了单视图NMF在人脸识别问题上的准确率; 文献[15]利用稀疏编码框架来对多视图特征学习进行研究; 文献[16]中, Akata等提出Collective-NMF算法令多种特征数据共享相同的系数矩阵, 这等同于先串联各种特征然后进行NMF分解.然而Liu等认为这种共享系数矩阵具有太强的约束, 提出一种弱化的约束, 旨在保证每种特征的一致性, 即视角间的一致性保持[17].

    但是, 以上这些方法没有考虑相同样本在不同视角中的空间结构关系, 这种局部空间结构在半监督学习、流形学习等多个领域的方法中具有重要的意义.典型的计算空间局部结构约束的方法有Locality preserving projection (LPP)[18]和Spectral Regression[19]等. Cai等在文献[19]的算法中, 通过引入局部结构约束达到了大幅度提高实验准确率的效果.

    因此, 本文提出了一种基于局部结构约束的多视图特征学习方法, 称之为MultiGNMF.这种方法的主要目标是相似的数据在每个视图都有相近的相似性.因此, 我们通过构建亲和矩阵来将每个视图的空间结构加入到目标函数中, 并提出迭代规则来解决这个优化问题.然而, MultiGNMF等多视图学习方法要求特征矩阵的值是非负的, 而实际中并不能总是保证这一限制条件.为了消除这一限制条件, 本文又提出了一种基于多视图学习的MultiGSemiNMF算法.

    文章主要结构分为4个部分:在第1节, 简要回顾一下基于矩阵分解的特征学习方法, 并将局部结构约束引入多视图学习框架中, 提出基于局部结构约束的多视图NMF分解算法—MultiGNMF; 在第2节, 针对MultiGNMF等多视图学习方法只适用于非负矩阵的缺点, 提出MultiGSemiNMF算法, 并对其进行详细介绍; 第3节对所提的算法进行实验验证和分析; 最后, 第4节对本文的工作进行总结.

    在这一节, 我们首先介绍基于NMF分解的单视图特征学习方法.然后, 考虑到多视图特征比单视图特征能更好地描述图像, 且分解后的系数矩阵应与原始特征据的空间结构相似, 我们提出了基于局部结构约束的多视图特征学习方法—MultiGNMF.下面将分别介绍NMF和MultiGNMF这两种特征学习算法.

    下面介绍NMF的求解过程.

    定义${X=[X_{\mathit{\boldsymbol{.}}, 1}, \cdots, X_{\mathit{\boldsymbol{.}}, N}] \in\, {\bf R}^{M\times N}}$为输入数据矩阵, 每一列都描述的是一个数据, ${U\in\, {\bf R}^{M\times K}}$为基矩阵, ${V\in\, {\bf R}^{N\times K}}$为系数矩阵, 即新的描述子, 两者的乘积是对原始矩阵的逼近, 如式(1)所示, 其中$K$是一个变量, 它决定了特征最终学习的特征维数.

    $ \begin{equation} X\approx UV^\mathit{\boldsymbol{T}}, \qquad U\geq0, V\geq0, X\geq0 \end{equation} $

    (1)

    如果从每一列的视图来观察这个表达式, ${X_j\approx U{(V_{j, \mathit{\boldsymbol{.}}})}^{\rm T}=\sum_{k=1}^K {U_{\mathit{\boldsymbol{.}}, k} V_{j, k}}}$, $U_{\mathit{\boldsymbol{.}}, k}$表示矩阵的第$k$列, $V_{j, \mathit{\boldsymbol{.}}}$代表矩阵的第$j$行, 我们称这两个向量为基向量和系数向量.这样可以很清晰地看到, 一个样本数据($X$的列向量)是基矩阵的各个基向量($U_{{\rm .}, k}$)的线性累加了.度量矩阵分解的误差的方法有很多种, 在欧氏空间中一般采用$l_F$范数来度量矩阵之间的距离.这样整个NMF求解便变成如下的有约束优化问题.

    $ \begin{equation} \min\limits_{U, V} {\parallel{X-UV^{\rm T}}\parallel}_{\rm F}^2, \qquad {\rm s.\, t.}\quad\, U\geq0, V\geq0 \end{equation} $

    (2)

    采用KKT (Karush-Kuhn-Tucher)条件, 分别引入拉格朗日因子$\Psi$和$\Phi$将$U\geq0, V\geq0$这两个约束条件变成无约束优化问题, 如式(3)所示.

    $ \begin{equation} L={\parallel{X-UV^{\rm T}} \parallel}_{\rm F}^2 +{\rm tr}(\Psi U^{\rm T} )+{\rm tr}(\Phi V^{\rm T} ) \end{equation} $

    (3)

    对于同时满足$U$和$V$的条件下对于式(3)这种无约束优化问题是非凸优化问题, 没有精确的求解方法.文献[19]提出了乘子更新法则来迭代求解上述最小化约束问题.迭代过程如式(4)和(5)所示.

    $ \begin{align*} \frac{\partial L}{\partial U}=\, &UV^{\rm T}V-XV+\Psi \Rightarrow \\ &U_{j, k}=U_{j, k}\times \frac {{(XV)}_{j, k}}{(UV^{\rm T}V)_{j, k}} \end{align*} $

    (4)

    $ \begin{align*} \frac{\partial L}{\partial V}=\, &VU^{\rm T}U-X^{\rm T}U+\Phi \Rightarrow\\ & V_{j, k}=V_{j, k}\times \frac{{(X^{\rm T}U)}_{j, k}}{(VU^{\rm T}U)_{j, k}} \end{align*} $

    (5)

    NMF是基于单视图的特征学习方法, 然而, 对同一个样本而言, 不同视图的多种特征往往可以互补地描述图像.基于此, 文献[17]提出了对每种特征保持弱化的一致性约束的多视图学习方法—MultiNMF.现将MultiNMF介绍如下.定义$X$为$G$个视图的输入特征数据矩阵, ${X^f=[X^f_{\mathit{\boldsymbol{.}}, 1}, \cdots, X^f_{\mathit{\boldsymbol{.}}, N}]\in {{\bf R}^{M_f\times N}}, (f\in {[1, G]}}$)为第$f$个视图的特征矩阵.其中, $M_f$为第$f$个视图的特征维数, $N$为样本数据的数量.对应地, 定义基矩阵${U={U^1, \cdots, U^G}}$和系数矩阵${V={V^1, \cdots, V^G }}$, ${U^f\in R^{M_f\times K}, V^f\in R^{N\times K}}$.其中, $K$为定义的新特征维数. Liu在文献[17]中提出Soft-regularization的方法认为, 对每个视图映射后的特征$V^f$需要保持一致性的约束, 但是允许存在差异性, 差异的大小采用欧氏空间中的$l_F$范数来度量.于是, 可以得到Liu的方法定义的损失函数如下式(6)所示.

    $ \min\limits_{U^f, V^f, V^\ast}\sum\limits_{f=1}^G\parallel X^f-U^f{V^f}^{\rm T}\parallel_{\rm F}^2+\lambda_f{\parallel{V^f-V^\ast}\parallel}_{\rm F}^2\\ \quad {\rm s.t.}~\, X^f\geq0, U^f\geq0, V^f\geq0, V^\ast\geq0\\ \quad {\parallel{U_{\ast, k}^f}\parallel}_1=1, \, {k=1, \cdots, K}, \, {f=1, \cdots, G} $

    (6)

    方程的解需要采用乘子更新法则来进行迭代求得, 具体过程这里不再赘述.

    局部空间结构约束的思想主要是保持样本的局部空间结构不变(近似不变), 这种局部空间结构在多个领域的方法中具有重要的意义.而MultiNMF没有考虑相同样本的原始数据与降维之后数据的空间结构关系, 因此, 本文提出了基于NMF矩阵分解的局部结构正则化约束多视图学习方法, 称之为MultiGNMF.下面对MultiGNMF方法进行详细介绍.

    1.3.1   局部结构正则化约束

    局部空间结构近似不变的具体含义就是:如果两个样本$x_i$和$x_j$在原始空间中相似, 那么我们认为它们在映射后的空间中(分别用$V_{i, \mathit{\boldsymbol{.}}}$和$V_{j, \mathit{\boldsymbol{.}}}$表示)也应该有近似的相似程度, 即原始数据与映射后的数据有相似的局部结构关系.

    根据以往文献的考察, 我们采用数据的亲和矩阵$W$来表征局部结构关系.计算亲和矩阵的方法很多, 在没有监督信息的前提下, 一般采用数据之间的欧氏距离构建亲和矩阵$W$.定义一个正整数变量$k$, 一个样本$i$与其他样本的权重可以如此计算:对所有样本与该样本的距离进行从小到大的排序, 如果样本$j$在前$k$个, 那么$W_{ij}=1$; 否则, $W_{ij}=0$.还有其他的方法不采用0/1值作为权值, 而是直接用数据之间的核函数值作为权值.典型的核函数有高斯核$W_{ij}={\rm e}^\frac{-{\parallel{x_i-x_j}\parallel} ^2}{\sigma}$, 线性核$W_{ij}={x_i}^{\rm T} x_j$等.不同的计算方法适应于不同的研究内容, 在文档特征中采用线性核表现更好, 在图像视觉特征中高斯核可能更适合.在和其他的方法比较的过程中, 我们采用比较通用的高斯核函数值作为权值, 从而就可以得到原始数据的亲和矩阵$W$.但是, 这些方法的性能受参数的影响较大.最近, Nie等[20]提出了一种无参数构建亲和矩阵$W$的方法, 该方法不需要任何参数, 很好地解决了构图过程需要反复调节参数的问题.但本文提出的MultiGSemiNMF和MultiGNMF算法直接应用无参数构图后缺乏普适性, 因此本文仍然使用高斯核函数来构建亲和矩阵, 在以后的工作将深入研究无参数构图和本文方法的结合.对于经过映射后的数据$V_{i, \mathit{\boldsymbol{.}}}$和$V_{j, \mathit{\boldsymbol{, }}}$, 仍用欧氏距离来度量它们之间的相似程度, 如式(7)所示.利用亲和矩阵$W$, 我们便可以构造用于约束局部结构的平滑惩罚因子.对于第$f$个视图的平滑惩罚因子$R^f$, 公式如下:

    $ \begin{equation} \mathcal {D}(V_{i, \mathit{\boldsymbol{.}}}, V_{j, \mathit{\boldsymbol{.}}} )={\parallel{V_{j, \mathit{\boldsymbol{.}}}^f-V_{i, \mathit{\boldsymbol{.}}}^f}\parallel}^2 \end{equation} $

    (7)

    $ \begin{align*} R^f&=\sum\limits_{i, j=1}^N{\parallel{V_{j, \mathit{\boldsymbol{.}}}^f-V_{i, \mathit{\boldsymbol{.}}}^f }\parallel}^2 W_{ij}^f=\\ &{\rm tr}((V^f )^{\rm T} D^f V^f )-{\rm tr}((V^f )^{\rm T} W^f V^f )= \\ &{\rm tr}((V^f )^{\rm T} L^f V^f ) \end{align*} $

    (8)

    其中, $L=D-W$为拉普拉斯矩阵, $D$是一个对角矩阵$D_{(j, j)} =\sum_iW_{i, j} $.

    1.3.2   目标方程的构建及求解

    将平滑惩罚因子引入多视图特征学习MultiNMF的框架中, 我们得到MultiGNMF方法的目标函数如下:

    $ \begin{align*} \min\limits_{U^f, V^f, V^\ast}\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f{\parallel{V^f-V^\ast}\parallel}_{\rm F}^2+\\ & \mu\lambda_f {\rm tr}((V^f)^{\rm T}L^fV^f))\\ {\rm s.\, t.}~\, X^f\geq0,& U^f\geq0, V^f\geq0, V^\ast\geq0\\ &{\parallel{U_{\ast, k}^f}\parallel}_1=1, \, {k=1, \cdots, K}, \, {f=1, \cdots, G} \end{align*} $

    (9)

    Liu在文献[17]中建议用对角阵$Q$归一化$U$和$V$, 即$UV^{\rm T}=UQ^{-1} QV^{\rm T}$.其中, $Q_f$定义如下:

    $ \begin{equation} Q_f:= {\rm diag}{\left(\sum\limits_{m=1}^MU_{m, 1}^f, \cdots, \sum\limits_{m=1}^MU_{m, K}^f \right)} \end{equation} $

    (10)

    diag$(\cdot)$表示对角矩阵.这样, 经过归一化后, ${\parallel{U_{*, i} \parallel}_1=1}$.因此, 式(9)可以改写成:

    $ \begin{align*} \min\limits_{U^f, V^f, V^\ast}\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f\parallel V^fQ^f-\\ &V^\ast\parallel_{\rm F}^2+\mu\lambda_f Tr((V^f)^{\rm T}L^fV^f))\\ {\rm s.\, t.}~\, &X^f\geq0, U^f\geq0, V^f\geq0, V^\ast\geq0 \end{align*} $

    (11)

    由此, 我们可以得到整体的损失函数定义如式(12)所示.

    $ \begin{align*} L_G=\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f\parallel V^fQ^f-\\ &V^\ast\parallel_{\rm F}^2+\mu\lambda_f {\rm tr}((V^f)^{\rm T}L^fV^f)) \end{align*} $

    (12)

    MultiGNMF在$U^f\geq0, V^f\geq0$的约束下最小化$L_G$是一个带约束的优化问题.采用迭代的方法求解.引入拉格朗如因子后, MultiGNMF的第$f$种特征损失函数为式(13).

    $ \begin{align*} L_1=\, &{\parallel{X-UV^{\rm T}} \parallel}_{\rm F}^2+\lambda_f{\parallel{VQ-V^\ast}\parallel}_{\rm F}^2+\\ &{\rm tr}(\Phi V^{\rm T} )+ \mu\lambda_f{\rm tr}(V^{\rm T}LV)+{\rm tr}(\Psi U^{\rm T} ) \end{align*} $

    (13)

    $L_1$分别对$U$和$V$求导, 求导结果如下:

    $ \begin{align*} \frac{\partial L_1}{\partial U}&=UV^{\rm T}V-XV+\Psi+\lambda_fP \\ \frac{\partial L_1}{\partial V}&=VU^{\rm T}U-X^{\rm T}U+\Phi+\lambda_f{(V-V^\ast+\mu LV)} \end{align*} $

    (14)

    其中, $P:={(\sum_{m=1}^MU_{m, k}\sum_{n=1}^NV_{n, k}^2-\sum_{n=1}^NV_{n, k}V_{n, k}^\ast)}$.采用KKT条件${\Psi_{j, k}U_{j, k}=0}$和${\Phi_{j, k}V_{j, k}=0}$得到$U$和$V$的迭代式如下:

    $ \begin{eqnarray*} U_{j, k}\leftarrow U_{j, k}\times\frac{{(XV)}_{j, k}+\lambda_f \sum\limits_{n=1}^NV_{n, k}V_{n, k}^\ast}{{(UV^{\rm T}V)}_{j, k}+\lambda_f \sum\limits_{n=1}^NV_{n, k}^2}\\ V_{j, k}\leftarrow V_{j, k}\times\frac{{({X^{\rm T}U}+\lambda_fV^\ast+\mu\lambda_fWV)}_{j, k}}{{({VU^{\rm T}U}+\lambda_fV+\mu\lambda_fDV)}_{j, k}} \end{eqnarray*} $

    (15)

    根据文献[17], 我们在每次迭代得到$U$和$V$之后, 按照式(10)进行归一化处理, 即:

    $ \begin{equation} U^f\leftarrow U^f{(Q^f)}^{-1}, \, V^f\leftarrow V^fQ^f \end{equation} $

    (16)

    在优化$U$和$V$之后, 将它们视为常量, 对$L_1$求导得到$V^\ast$的更新表达式如下所示:

    $ \begin{equation} V^\ast=\dfrac{\sum\limits_{f=1}^G\lambda_fV^f}{\sum\limits_{f=1}^G\lambda_f} \end{equation} $

    (17)

    NMF和MultiGNMF都要求$U\geq0, V\geq0, X\geq0$.这种非负性约束来源于在现实世界中大部分数据是非负的, 系数的累加也是非负的.然而, 实际情况中, 我们提取到的图像特征往往存在负数, 这就使得以上两种特征学习方法存在局限性.为了消除这个局限, 我们提出一种对负数特征也适用的多视图特征学习方法—ṀultiGSemiNMF, 我们将在下一节对其进行详细介绍.

    在第1节中我们分析了各种基于NMF矩阵分解的特征学习方法的优越表现, 不过这些方法有一个重要的约束:所有数据都必须是非负的.在物理世界中可能大部分数据保持这个特性, 但是, 在图像处理中有些特征, 如由小波变换得到的三分法特征、结构特征等, 并没有保持非负性的条件, 如果强制向正数方向映射, 往往含有一定的失真.这就使得基于NMF的特征学习方法有一定的局限性.如何将NMF算法拓展到对负数矩阵也适用, 文献[13]中进行了详细探究.其中一种方法是SemiNMF, 下面我们对其进行介绍, 并由此引出本文所提算法—ṀultiGSemiNMF.

    SemiNMF中的数据与NMF中的数据一致, 但是, SemiNMF算法对原始数据$X$和基矩阵$U$不带有非负性约束, 只需系数矩阵$V\geq0$.由此, 我们可以得到SemiNMF的目标方程和损失函数分别如式(18)和(19)所示:

    $ \min\limits_{U, V} {\parallel{X-UV^{\rm T}}\parallel}_{\rm F}^2, \quad {\rm s.\, t.}\, V\geq0 $

    (18)

    $ L_{semi}={\parallel{X-UV^{\rm T}}\parallel}_{\rm F}^2= \\ \ \ \ \ \ \ \ \ \ \ \ {\rm tr}{(XX^{\rm T}-2X^{\rm T}UV^{\rm T}+VU^{\rm T}UV^{\rm T})} $

    (19)

    SemiNMF在$V\geq0$的约束下最小化$L_{semi}$是一个带约束的优化问题.采用迭代的方法求解, 求解过程我们将在第2.2节具体介绍.

    SemiNMF这种方法具有很好的描述性, 同时相对NMF有较大使用范围和较高性能.于是, 为了克服基于NMF的各种特征学习方法只适用于非负数据的缺点, 本文提出基于SemiNMF的多视图特征学习算法, 我们称之为MultiGSemiNMF.下面将对这种方法做详细的介绍.

    2.2.1   目标方程

    多视图学习过程中我们需要遵守几个准则: 1)每个视图学习的新特征需要保持一致性; 2)在学习前的特征和学习后的特征对样本之间的局部结构进行度量, 需要保持这种结构的一致性.于是, 我们得到弱化的一致性约束项${{\parallel V^f-V^\ast \parallel}_{\rm F}^2}$和局部结构正则化约束项${{\rm tr}((V^f )^{\rm T}L^f V^f)}$.我们将多视图学习的准则应用到SemiNMF, 于是, 我们可以得到MultiGSemiNMF算法的目标函数如式(20)所示.

    $ \begin{align*} \min\limits_{U^f, V^f, V^\ast}\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f\parallel V^fQ^f-\\ &V^\ast\parallel_{\rm F}^2+\mu\lambda_f {\rm tr}((V^f)^{\rm T}L^fV^f))\\ \quad {\rm s.t.}\quad &V^f\geq0, V^\ast\geq0 \end{align*} $

    (20)

    其中, $Q^f$的引进是为了使方程满足${{\parallel{U_{\ast, k}^f}\parallel}_1=1}$的约束条件.而${{\parallel{U_{\ast, k}^f}\parallel}_1=1}$的约束条件是为了每一种特征的数据归一化处理, 那么对应的系数矩阵也变得归一化, 具有比较性.又因为${\parallel X\parallel}={\parallel \sum_jX_j\parallel} \approx \sum_{k=1}^K{\parallel {U_{i, k}\sum_jV_{j, k}}}\parallel =\sum_{k=1}^K{\parallel {\sum_jV_{j, k}\parallel}}= \parallel V\parallel$.所以, 在$U$归一化之后如果对$X$也进行归一化处理, $V$便也达到归一化的目的.而$X$为原始数据我们能更好的操作, 故在求解过程中只需要在每次迭代$U$之后对其进行归一化即可.所以, 式(20)可以简写成(21), 但是我们需要求解前对原始数据$X$进行归一化操作, 在每次迭代后对$U$进行归一化.

    $ \begin{align*} \min\limits_{U^f, V^f, V^\ast}\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f\parallel{V^fQ^f-}\\ &V^\ast\parallel_{\rm F}^2+\mu\lambda_f {\rm tr}((V^f)^{\rm T}L^fV^f)\\ \quad {\rm s.\, t.}\quad &V^f\geq0, V^\ast\geq0 \end{align*} $

    (21)

    由此, 我们可以得到MultiGSemiNMF算法的整体损失函数如下所示:

    $ \begin{align*} L_{GSemi}=\sum\limits_{f=1}^G&{\parallel{X^f-U^f{(V^f)}^{\rm T}}\parallel}_{\rm F}^2+\lambda_f\parallel{V^f-}\\ &V^\ast\parallel_{\rm F}^2+\mu\lambda_f {\rm tr}((V^f)^{\rm T}L^fV^f)) \end{align*} $

    (22)

    其中, $L=D-W$为拉普拉斯矩阵, $D$是一个对角矩阵${D_{(j, j) }=\sum_iW_{i, j}}$, $W$为样本在原始空间关系的亲和矩阵.各变量的具体含义及计算方法详见第1.3节.

    2.2.2   方程求解

    MultiGSemiNMF在${V^f\geq0}$的约束下最小化$L_{GSemi}$是一个带约束的优化问题.对于每个视图的特征, 引入拉格朗日因子后, MultiGSemiNMF的第$f$个视图特征的损失函数为

    $ \begin{align*} L_2=&{\parallel{X-UV^{\rm T}} \parallel}_{\rm F}^2+\lambda_f{\parallel{V-V^\ast}\parallel}_{\rm F}^2+\\ &{\rm tr}(\Phi V^{\rm T} )+ \mu\lambda_f{\rm tr}(V^{\rm T}LV) \end{align*} $

    (23)

    损失函数在变量$U$和$V$下不是一个凸优化问题没有精确的数值解, 采用迭代优化方法求解, 具体计算步骤如下:

    1) 对$V$取随机矩阵或者采用K-means算法得到的系数矩阵.

    2) 固定$V$更新$U$.将$L_2$中只有变量$U$, 变成一个无约束优化问题, 对其求导${\frac{\partial L_2}{\partial U}=UV^{\rm T}V-XV=0}$, 获得$U$的解析解.其中${V^T V\in {\bf R}^{K\times K}}$在一般情况下是一个半正定的矩阵, 在不可逆的情况下, 用伪逆矩阵来代替(Matlab中的pinv函数).

    $ \begin{equation} U=XV{(V^{\rm T}V)}^{-1} \end{equation} $

    (24)

    3) 固定$U$更新$V$.将$U$固定, $L_2$中只有变量$V$, 对其求导${\frac{\partial L_2}{\partial V}=VU^{\rm T}U-X^{\rm T}U+\Phi+\lambda_f{(V-V^\ast+\mu LV)}}$ ${=0}$, 采用KKT条件$\Phi_{j, k}V_{j, k}=0$获得式(25)的优化问题.

    $ \begin{align*} &{(VU^{\rm T}U-X^{\rm T}U+\lambda_f(V-V^\ast+\mu LV))}_{ik}V_{ik}=\\ &\qquad\beta_{ik}V_{ik}=0 \end{align*} $

    (25)

    式(25)是一个典型的定点等式问题, 求解${f(x)=0}$, 可以变成${x=g(x)}$的形式, 迭代式子$x_{i+1}=g{(x_i)}$由于存在$V\geq0$的约束条件, 式(25)中的各项需要保持绝对的非负性.所以, 我们采用拆分的方法.通过拆分, ${X^{\rm T}U={(X^{\rm T}U)}^+-{(X^{\rm T}U)}^-, U^{\rm T}U={(U^{\rm T}U)}^+}$ ${-{(U^{\rm T} U)}^-}$, 其中的拆分函数定义如式(26)所示.这样式(25)便变成多个非负矩阵之间的线性组合.

    $ \begin{equation} A_{ik}^+=\frac {\mid{A_{ik}\mid}+A_{ik}}{2}, \, A_{ik}^-=\frac {\mid{A_{ik}\mid}-A_{ik}}{2} \end{equation} $

    (26)

    $ V_{ik}=V_{ik}\times \\ {\sqrt{\frac {{X^{\rm T}U}_{j, k}^++{[V{(U^{\rm T}U)}^-]}_{j, k}+\lambda_f{(\mu WV+V^\ast)}_{j, k}}{{X^{\rm T}U}_{j, k}^-+{[V{(U^{\rm T}U)}^+]}_{j, k}+\lambda_f{(\mu WV+V)}_{j, k}}}} $

    (27)

    文献[21]提出一种满足定点等式的${x=g(x)}$形式, 将式(27)所示, 代入到式(25)中${{(VU^{\rm T}U-X^{\rm T}U+\lambda_f(V-V^\ast+\mu LV))}_{ik}V_{ik} =0}$, 由于KKT条件约束${\beta_{ik}V_{ik}=0}$, 当${V_{ik}\neq0}$时, 必然存在$(VU^{\rm T}U-X^{\rm T}U+\lambda_f(V-V^\ast+\mu LV))_{ik} =0$, 式(27)满足式(25);反之, 当$V_{ik}=0$也满足.综合考虑, 式(27)满足KKT条件.迭代式(27)的收敛性证明方法可以详见文献[21-22].

    4) 交替迭代第2)步和第3)步, 直到损失函数值小于阈值或损失函数值变化小于阈值.

    5) 在优化$U$和$V$之后, 将它们视为常量, 利用式(17)更新${V^\ast}$. MultiGSemiNMF与MultiGNMF的不同之处在于缺少了${U^f\geq0}$的约束, 因此不仅适用于特征矩阵非负的情况, 在特征矩阵中存在负数时, 也表现良好.式(28)是各种变量的迭代方程.

    $ \ \ \ U_{j, k}\leftarrow U_{j, k}\times\frac{{(XV)}_{j, k}+\lambda_f \sum\limits_{n=1}^NV_{n, k}V_{n, k}^\ast}{{(UV^{\rm T}V)}_{j, k}+\lambda_f \sum\limits_{n=1}^NV_{n, k}^2}\\ V_{ik}\leftarrow V_{ik}\times \\ {\sqrt{\frac {{X^{\rm T}U}_{j, k}^++{[V{(U^{\rm T}U)}^-]}_{j, k}+\lambda_f{(\mu WV+V^\ast)}_{j, k}}{{X^{\rm T}U}_{j, k}^-+{[V{(U^{\rm T}U)}^+]}_{j, k}+\lambda_f{(\mu WV+V)}_{j, k}}}} $

    (28)

    为了验证MultiGNMF算法和MultiGSemiNMF算法的有效性, 我们在4个公共的图像数据库中和其他几种多特征学习算法比较图像聚类效果.下面分别从实验设置、评估指标和实验结果及分析这三部分作详细介绍.

    3.1.1   数据库

    实验中所用的数据库为CMU PIE人脸数据库、UCI手写体数字图像数据库、3-Sources文本数据库和ORL人脸库.表 1详细介绍这4个数据库的统计特性.具体介绍如下:

    表 1  4个数据库的资料
    Table 1  The information of four databases
    数据库 数量 视图个数 聚类个数
    CMU PIE 2 856 2 68
    UCI Digit 2 000 2 10
    3-Sources 169 3 6
    ORL 400 2 40
    下载: 导出CSV 
    | 显示表格

    CMU PIE人脸数据库包含41 368张$32\times 32$像素的人脸图像, 这些数据是68个人按照指定的13种姿势角度和43种不同光照条件下采集人脸的图像.在实验中, 我们从每个人的一个角度中随机选择42幅图像, 构成2 856幅人脸图像.如果按照人脸作为聚类中心的话, 那么数据可以分成68个集群.在本次实验中, 我们用图像的像素值(二维图像按行展开)和HOG (Histogram of oriented gradient)特征作为CMU PIE的两个视图.

    UCI手写体数字数据库有UCI大学构建数字0$\, \sim\, $ 9的手写体图像, 数据库包含2 000个样本.我们利用手写体图像的低频傅里叶变换和原始像素值作为不同的视图.

    3-Sources文本数据库包含BBC、Reuters和Guardian三种流行的网上新闻资源.其中, 有169条新闻被这三个新闻网报道过.我们选取这169条新闻作为测试样本, 这三个新闻网分别作为三个视图来进行聚类分析.这些新闻的主题包含商业、娱乐、健康、政治、运动和科技, 我们将其作为我们聚类的标签.

    ORL (Olivetti research laboratory)人脸库是英国剑桥大学Olivetti研究所制作的人脸数据库, 它共包含400张的人脸图像.这些数据是40个人在不同的时间、变化的光线、面部表情(张开/合拢眼睛、微笑/不微笑)和面部细节(戴眼镜/不戴眼镜)下拍摄的.所有的图像为实验者的正脸, 带有一定程度的朝上下左右的偏转或倾斜, 相似的黑暗同质背景.所有图像的大小均为$28\times 23$像素.在本次实验中, 我们用图像的像素值(二维图像按行展开)和低频傅里叶变换系数值作为ORL的两个视图.

    3.1.2   对比算法

    为了更全面地评估本文提出的算法, 我们比较了近期多种典型的多视图学习算法.下面对它们进行描述.

    1) 单视图算法(BSV和WSV):我们对每个视图利用NMF算法进行特征学习, 将学习的系数矩阵作为特征.统计每个视图的效果, 我们取每个视图该算法对应的最好效果为BSV和最差效果为WSV.

    2) ConcatNMF:这是一种前向融合的学习方法.其算法可以简单理解为, 首先将每个视图的特征串联成一个向量(矩阵)作为数据新的特征, 然后利用非负矩阵分解算法进行特征学习, 所有算法流程和度量标准与单视图的方法一致.

    3) ColNMF:一种多视图学习方法, 采用一致性准则, 如式(29)所示, 所有的视图共享相同的系数矩阵.与ConcatNMF类似, 不过每个视图添加了权重和归一化约束.

    $ \begin{equation} \min\limits_{U^f, V}\sum\limits_{f=1}^G{\parallel {X^f-U^f{(V)}^{\rm T}}\parallel}_{\rm F}^2 \end{equation} $

    (29)

    4) Co-reguSC:一种改进的谱聚类算法, 在文献[23]中被Kumar等提出.每个视图采用谱聚类学习作为基本的聚类学习算法, 与MultiNMF算法相似的是, 在视图之间采用弱一致性准则约束各个视图的映射矩阵之间的关系, 如式(30)所示.在实验中我们采用高斯核核函数, 该算法的详细介绍可以参考文献[23].

    $ \begin{align} &\max\limits_{U^v, U^\ast}\sum\limits_{v=1}^m{\rm tr}{((U^v )^{\rm T}L^v U^v)}+\nonumber\\ &\qquad\sum\limits_v\alpha_v{\rm tr}{(U^v{(U^v)}^{\rm T}U^\ast {(U^\ast)}^{\rm T})} \end{align} $

    (30)

    5) MultiNMF:本文算法的基准算法, 采用弱一致性约束的多视图NMF学习方法.

    6) Sc-ML:是一种改进的Co-reguSC算法. Dong等在文献[24]中提出, 利用格拉斯曼流行距离中的一种投影距离来定义不同视图学习的子空间之间一致性准则.

    7) MMSC:是一种多模态的谱聚类方法.不同的模态(也就是图像特征)共享一个相同的图拉普拉斯矩阵, 也就是最后的聚类指示矩阵$G$.该算法的详细介绍可以参考文献[10].

    $ \begin{align} &\min\limits_{G\geq0, G^{\rm T}G=I, G_i}\sum\limits_i({\rm tr}(G^i)^{\rm T}L^i G^i+\nonumber\\ &\qquad\alpha {\rm tr}{(G-G^i)}^{\rm T}\times(G-G^i)) \end{align} $

    (31)

    8) AMGL:是一种多视图谱聚类方法.但是不同视图所占的权重是自动学得的, 不需要有额外的参数来指导训练.该算法的详细介绍可以参考文献[11].

    本文采用以往文献中的经典评估方法: AC (精确度)和NMI (归一化互信息)来度量图像数据聚类的评估指标.给定一幅图像, 定义为图像的标签类别, 为图像对应的聚类中心的类别标签, AC可以用如下式(31)来定义.其中$n$为所有的测试图像数量, 是一个脉冲函数, 函数中两个参数相同则返回1, 否则返回0.是一种将聚类中心的标签映射到图像集已知的对等标签, 其中我们采用Kuhn-Munkres[25]的映射方法.

    $ \begin{equation} AC=\frac {\sum\limits_{i=1}^n\delta{(\alpha_i, map(l_i))}}{n} \end{equation} $

    (31)

    给定两个数据集的所有聚类中心, 它们之间的互信息可以用式(32)计算.

    $ \begin{equation} MI{(\mathcal {C}, \mathcal {C}')} = \sum\limits_{c_i \in \mathcal {C}, {c_j}'\in {\mathcal {C}'}}p{(c_i, c_j')}\cdot {\rm log}_2{\frac {p{(c_i, c_j')}}{p(c_i )p(c_j')}} \end{equation} $

    (32)

    其中, $p(c_i)$和${p(c_j' )}$表示在所有测试图像中被分到各自对应聚类中心的概率, 在这里我们用数量比率代表概率, ${p(c_i, c_j')}$表示一个图像被同时分到这两个聚类中心$c_i$和${c_j'}$的概率, 同样我们用数量比代替概率(注意在这里聚类算法计算得到的聚类中心的编号可以为任意的顺序).在实验中, 第一个聚类中心集为图像的已知类别标签, 同一个标签的图像为一个聚类中心, 第二个聚类中心集为聚类算法得到的标签, 标签可以为任意的顺序标签.归一化的互信息为互信息除以最大的聚类标签熵, 其中${H(\mathcal {C})=-\sum_ip(c_i) {\rm log}_2p(c_i)}$, ${p(c_i)}$指属于聚类中心${c_i}$的图像数量比率.

    $ \begin{equation} NMI(\mathcal {C}, \mathcal {C}')=\frac {MI(\mathcal {C}, \mathcal {C}' )}{\max(H({\mathcal {C}}), H(\mathcal {C}' ))} \end{equation} $

    (33)
    3.3.1   聚类的准确性验证

    在本文提出的方法需要计算各个数据之间的局部结构关系, 我们采用高斯核函数值作为权值, 即${W_{ij}={\rm e}^{-\frac {\parallel {x_i-x_j} \parallel ^2} {\sigma }}}$.变量${k=5}$, 这种参数设置在非大量样本数据库中使用的较多.在式(12)中所有的变量我们设定为${\lambda_f=0.01\, (f=1, \cdots, G), \mu =10}$, 与算法MultiNMF和MultiGNMF保持一致.

    在定义了参数之后, 计算每个视图图像之间的亲和矩阵, 每种方法我们都运行20次, 取所有次数运行结果的平均值和方差作为最终的算法效果评估值.经过20次的实验运行, 我们统计了各种算法在4个数据库上的AC和NMI值, 如表 2表 3所示.

    表 2  不同方法在4个数据库中的AC值
    Table 2  The AC values by different methods in four databases
    算法 UCI Digit CMU PIE 3-Sources ORL
    BSV ${68.5\pm.05}$ ${55.2\pm.02}$ ${60.8\pm.01}$ ${51.8\pm.02}$
    WSV ${63.4\pm.04}$ ${47.6\pm.01}$ ${49.1\pm.03}$ ${42.8\pm.05}$
    ConcatNMF ${67.8\pm.06}$ ${51.5\pm.00}$ ${58.6\pm.03}$ ${66.8\pm.02}$
    ColNMF ${66.0\pm.05}$ ${56.3\pm.00}$ ${61.3\pm.02}$ ${66.3\pm.04}$
    Co-reguSC ${86.6\pm.00}$ ${59.5\pm.02}$ ${47.8\pm.01}$ ${70.5\pm.02}$
    MultiNMF ${88.1\pm.01}$ ${64.8\pm.02}$ ${68.4\pm.06}$ ${67.3\pm.03}$
    SC-ML ${88.1\pm.00}$ ${72.3\pm.00}$ ${54.0\pm.00}$ ${70.8\pm.00}$
    MMSC ${89.4\pm.38}$ ${61.6\pm.06}$ ${69.9\pm.04}$ ${70.7\pm.06}$
    AMGL ${82.6\pm.74}$ ${63.6\pm.19}$ ${68.3\pm.12}$ ${64.2\pm.10}$
    MultiGNMF ${95.1\pm.10}$ ${72.5\pm.02}$ ${73.4\pm.00}$ ${73.5\pm.00}$
    MultiGSemiNMF ${95.6\pm.02}$ ${77.2\pm.12}$ ${79.3\pm.00}$ ${76.2\pm.00}$
    下载: 导出CSV 
    | 显示表格
    表 3  不同方法在4个数据库中的NMI值
    Table 3  The NMI values by different methods in four databases
    算法 UCI Digit CMU PIE 3-Sources ORL
    BSV ${63.4\pm.03}$ ${74.1\pm.00}$ ${53.0\pm.01}$ ${69.8\pm.01}$
    WSV ${60.3\pm.03}$ ${69.1\pm.02}$ ${44.1\pm.02}$ ${65.4\pm.04}$
    ConcatNMF ${60.3\pm.03}$ ${70.5\pm.00}$ ${51.7\pm.03}$ ${85.1\pm.01}$
    ColNMF ${62.1\pm.03}$ ${68.3\pm.00}$ ${55.2\pm.02}$ ${84.5\pm.03}$
    Co-reguSC ${77.0\pm.00}$ ${80.5\pm.01}$ ${41.4\pm.01}$ ${80.5\pm.01}$
    MultiNMF ${80.4\pm.01}$ ${82.2\pm.02}$ ${60.2\pm.06}$ ${87.6\pm.01}$
    SC-ML ${87.6\pm.00}$ ${85.1\pm.00}$ ${45.5\pm.00}$ ${85.3\pm.00}$
    MMSC ${88.0\pm.05}$ ${80.3\pm.01}$ ${66.3\pm.09}$ ${85.9\pm.01}$
    AMGL ${84.9\pm.33}$ ${81.8\pm.10}$ ${56.9\pm.11}$ ${81.9\pm.02}$
    MultiGNMF ${90.1\pm.04}$ ${90.2\pm.01}$ ${65.4\pm.00}$ ${88.5\pm.00}$
    MultiGSemiNMF ${91.2\pm.01}$ ${93.8\pm.05}$ ${73.4\pm.00}$ ${89.9\pm.00}$
    下载: 导出CSV 
    | 显示表格

    表 2表 3中我们可以看到本文提出的算法在聚类分析中相比较其他多视图学习算法在准确度和归一化互信息两个指标下都有较好的表现.同时我们注意到Co-reguSC和SC-ML算法也采用了局部结构约束的条件(谱聚类算法是一种基于数据样本图结构的算法), MMSC也采用了一致性约束, 本文算法同样超过该类算法.在比较本文提出的算法MultiGSemiNMF和MultiGNMF算法中, 我们发现基于MultiGSemiNMF的算法相对于MultiGNMF算法聚类效果上也有提升, 即使所有特征并没有负数或零, 这证明在特征学习中MultiGSemiNMF算法比MultiGNMF算法在一些应用场景中具有更好的表现, 且MultiGSemiNMF消除了MultiGNMF算法要求所有特征非负的限制, 因此也有着更为广阔的应用平台.

    3.3.2   参数对算法性能的影响

    在式(12)中有$G$个参数变量$\lambda_f$, 它的物理意义是不同视图对学习过程的重要性进行权衡.如果我们具有一些先验知识, 带有噪声的视图特征可以适当减少权重, 被认为重要的视图如文本标签信息等可以适当增加权重.在我们的实验中没有先验知识, 同时数据已经归一化处理, 所以所有的$\lambda_f$定义为相同的数.但是$\lambda_f$的大小会影响聚类效果, $\lambda_f$越小则对系数矩阵的一致性约束越松弛, 反之, $\lambda_f$为无穷大的话所有系数矩阵为相同的数值.

    下面我们在两个数据库CMU PIE和UCI Digit上用MultiNMF、MultiGNMF和MultiSemiNMF三个算法做聚类分析, 准确率AC作为指标度量不同的$\lambda_f$值对实验的影响.我们设定$\lambda_f$为0.001, 0.005, 0.002, 0.01, 0.02, 0.05, 0.1, 图 1图 2描述了对应的聚类效果.

    图 1  在UCI Digit数据库中参数$\lambda$对本文算法的影响
    Fig. 1  The influences of $\lambda$ on UCI Digit database
    图 2  在CMU PIE数据库中参数$\lambda$对本文算法的影响
    Fig. 2  The influences of $\lambda$ on CMU PIE database

    图 1图 2中我们可以看到, 在MultiNMF、MultiGNMF和MultiSemiNMF三个算法中, MultiGSemiNMF算法的准确率最高, 且受参数影响很小, 在较小或者较大的值均能有稳定的表现. MultiGNMF算法最不稳定, 但是在大部分实验中仍能超过基准算法MultiNMF.三种算法均在${\lambda=0.01}$时有较高的表现.

    本文提出的算法MultiGSemiNMF和MultiGNMF需要构建一个样本亲和矩阵, 在损失函数其中有一个参数$k$, $k$值越大样本的局部结构约束越多, 反之局部结构约束越少.不同的$k$值对聚类效果有一定影响, 在与其他算法的比较中, 我们采用其他算法一样的$k$值, 在这里我们另外分析$k$值对本文提出算法的影响.在UCI Digit数据总库, 我们选取${k = 5, 10, 15, 20}$构建亲和矩阵(${\lambda=0.01}$), 用聚类的准确率AC来评估算法效果, 如图 3所示.

    图 3  在UCI Digit中参数$k$对本文提出算法的影响
    Fig. 3  The influences of $k$ on UCI Digit database

    图 3我们看到参数$k$对本文算法有一定的影响, $k$值越大虽然能更充分地保留样本之间的局部空间结构关系, 但是从图中的结果来看聚类准确度随着$k$的变大有降低的趋势.过度的保留空间结构关系并不能提升算法的效果, 反而可能产生过度拟合的副作用, 因为样本的结构关系是基于原始特征的距离计算得到, 而原始特征并不能充分描述样本信息, 其中或多或少含有冗余和噪声.同时, 也可以看出, 无论参数$k$取何值时, MultiGSemiNMF算法的性能都优于MultiGNMF算法.

    本文提出了两种多视图学习的方法: MultiGNMF算法和MultiGSemiNMF算法. MultiGNMF和MultiGSemiNMF算法都是基于样本局部结构空间约束的非负矩阵分解多视图学习方法.

    本文首先介绍了一种单视图学习方法: NMF矩阵分解.然后, NMF算法的基础之上, 在以往多视图学习的框架准则下, 本文提出了基于样本局部结构空间约束的非负矩阵分解多视图学习方法MultiGNMF.但是, MultiGNMF方法只适用于非负的特征矩阵. MultiGSemiNMF算法则不限于此.

    为了验证本文提出的多视图学习算法的性能, 我们在公有的图像数据库中做聚类分析.实验中和以往的算法比较, 实验结果表明本文提出的算法相对于其他基于矩阵分解的多视图学习方法有更好的表现.同时实验中分析了算法中的参数变化对算法性能的影响, 实验结果表明MultiGSemiNMF对参数变化具有很好的鲁棒性.在未来的工作中, 我们将探索一种新的基于局部结构约束的多视图学习方法.


  • 本文责任编委 张化光
  • 图  1  间接互惠的三种形式

    Fig.  1  Three kinds of indirect reciprocity

    图  2  博弈模型及收益矩阵

    Fig.  2  Games and their payoff matrices

    图  3  经典的间接互惠模型

    Fig.  3  Representative model about indirect reciprocity

    图  4  声望信息传播的两种方式

    Fig.  4  Two ways of reputation dispersal

    表  1  声望评估准则

    Table  1  Reputation evaluation criterion

    声望评估准则 定义 数量(种) 典型的例子
    "一阶评估" 考虑捐助者行为 $2^2=4$ "形象分数"
    "二阶评估" 同时考虑捐助者行为和接受者声望 ${(2^2)}^2=16$ "温和准则"、"严苛准则"
    "三阶评估" 同时考虑捐助者行为和声望及接受者声望 ${({(2^2)}^2)}^2=256$
    下载: 导出CSV

    表  2  典型的"二阶评估"

    Table  2  Representative "second-order evaluation"

    捐助者行为/接受者声望
    捐助/好 捐助/坏 不捐助/好 不捐助/坏
    "温和准则"
    "严苛准则"
    下载: 导出CSV

    表  3  8种促进合作演化的声望评估准则

    Table  3  Eight reputation evaluation criterions which favor the evolution of cooperation

    捐助者声望/接受者声望
    好/好 好/坏 坏/好 坏/坏
    捐助者捐助 未知 未知
    捐助者不捐助 未知
    下载: 导出CSV
  • [1] Darwin C. On the origin of species by means of natural selection. Science, 1963, 71(6):354-357 http://www.gutenberg.org/ebooks/1228
    [2] McDonald D B. Cooperation among animals:an evolutionary perspective. Lee Alan Dugatkin. The Quarterly Review of Biology, 1998, 73(3):387-388 doi: 10.1086/420391
    [3] Nowak M A, Sigmund K. Evolutionary dynamics of biological games. Science, 2004, 303(5659):793-799 doi: 10.1126/science.1093411
    [4] Clutton-Brock T. Cooperation between non-kin in animal societies. Nature, 2009, 462(7269):51-57 doi: 10.1038/nature08366
    [5] Darwin C. The Works of Charles Darwin, Volume 15:On the Origin of Species 1859. New York:New York University Press, 2010. 69-83
    [6] Axelrod R, Axelrod D E, Pienta K J. Evolution of cooperation among tumor cells. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(36):13474-13479 doi: 10.1073/pnas.0606053103
    [7] Smith E A. Communication and collective action:language and the evolution of human cooperation. Evolution and Human Behavior, 2010, 31(4):231-245 doi: 10.1016/j.evolhumbehav.2010.03.001
    [8] Tuyls K, Parsons S. What evolutionary game theory tells us about multiagent learning. Artificial Intelligence, 2007, 171(7):406-416 doi: 10.1016/j.artint.2007.01.004
    [9] Hardin G. The tragedy of the commons. Science, 1968, 162(3859):1243-1248 doi: 10.1126/science.162.3859.1243
    [10] Milinski M, Sommerfeld R D, Krambeck H J, Reed F A, Marotzke J. The collective-risk social dilemma and the prevention of simulated dangerous climate change. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(7):2291-2294 doi: 10.1073/pnas.0709546105
    [11] Requejo R J, Camacho J. Evolution of cooperation mediated by limiting resources:connecting resource based models and evolutionary game theory. Journal of Theoretical Biology, 2011, 272(1):35-41 doi: 10.1016/j.jtbi.2010.12.005
    [12] Zhang Y, He J H. Research on the mobile net business knowledge sharing strategy of fraud evade. Applied Mechanics and Materials, 2014, 631-632:1171-1173 https://www.researchgate.net/publication/272113750_Research_on_the_Mobile_Net_Business_Knowledge_Sharing_Strategy_of_Fraud_Evade
    [13] Pennisi E. How did cooperative behavior evolve? Science, 2005, 309(5731):93 doi: 10.1126/science.309.5731.93
    [14] Smith J M, Price G R. The logic of animal conflict. Nature, 1973, 246(5427):15-18 doi: 10.1038/246015a0
    [15] Fu F. Evolutionary Games and Evolution of Cooperation[Ph.D. dissertation], Peking University, China, 2009.
    [16] Chen X J. Evolutionary Dynamics of Cooperation in Complex Networks[Ph.D. dissertation], Peking University, China, 2010.
    [17] Wu B. Evolutionary Game Dynamics in Finite Populations[Ph.D. dissertation], Peking University, China, 2011.
    [18] Wang J. Evolutionary Game Dynamics in Populations[Ph.D. dissertation], Peking University, China, 2011.
    [19] Zhang C Y. Cooperation in Evolutionary Games on Networks of Agents[Ph.D. dissertation], Peking University, China, 2012.
    [20] Zhang J L. Cooperation Mechanisms in Evolutionary Games[Ph.D. dissertation], Peking University, China, 2013.
    [21] Wu T. Evolutionary Cooperation Dynamics[Ph.D. dissertation], Peking University, China, 2013.
    [22] Yang Z H. Evolutionary Games and Evolutionary Cooperation Dynamics in Complex Networks[Ph.D. dissertation], Xidian University, China, 2014.
    [23] Zhang Y L. Two Theoretical Methods upon the Evolution of Cooperation in Finite Populations and the Applications[Ph.D. dissertation], Peking University, China, 2015.
    [24] Cong R. Coevolutionary Games on Complex Networks[Ph.D. dissertation], Xidian University, China, 2014.
    [25] Du J M. Evolutionary Game Dynamics in Complex Systems[Ph.D. dissertation], Xidian University, China, 2016.
    [26] Li K. Evolutionary Dynamics in Collective Behavior[Ph.D. dissertation], Peking University, China, 2016.
    [27] 王龙, 伏锋, 陈小杰, 王靖, 李卓政, 谢广明, 楚天广.复杂网络上的演化博弈.智能系统学报, 2007, 2(2):1-10 http://d.old.wanfangdata.com.cn/Periodical/xdkjyc200702001

    Wang Long, Fu Feng, Chen Xiao-Jie, Wang Jing, Li Zhuo-Zheng, Xie Guang-Ming, Chu Tian-Guang. Evolutionary games on complex networks. CAAI Transactions on Intelligent Systems, 2007, 2(2):1-10 http://d.old.wanfangdata.com.cn/Periodical/xdkjyc200702001
    [28] 王龙, 伏锋, 陈小杰, 王靖, 武斌, 楚天广, 谢广明.复杂网络上的群体决策.智能系统学报, 2008, 3(2):95-108 http://www.docin.com/p-1440573413.html

    Wang Long, Fu Feng, Chen Xiao-Jie, Wang Jing, Wu Bin, Chu Tian-Guang, Xie Guang-Ming. Collective decision-making over complex networks. CAAI Transactions on Intelligent Systems, 2008, 3(2):95-108 http://www.docin.com/p-1440573413.html
    [29] 王龙, 王靖, 武斌.量子博弈:新方法与新策略.智能系统学报, 2008, 3(4):294-304 http://www.cnki.com.cn/Article/CJFDTotal-JSJA201410056.htm

    Wang Long, Wang Jing, Wu Bin. Quantum games:new methodologies and strategies. CAAI Transactions on Intelligent Systems, 2008, 3(4):294-304 http://www.cnki.com.cn/Article/CJFDTotal-JSJA201410056.htm
    [30] 王龙, 吴特, 张艳玲.共演化博弈中的反馈机制.控制理论与应用, 2014, 31(7):823-836 https://www.wenkuxiazai.com/doc/5b517652f12d2af90342e609.html

    Wang Long, Wu Te, Zhang Yan-Ling. Feedback mechanism in coevolutionary games. Control Theory & Applications, 2014, 31(7):823-836 https://www.wenkuxiazai.com/doc/5b517652f12d2af90342e609.html
    [31] Boccabella A, Natalini R, Pareschi L. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4(1):187-213 https://arxiv.org/abs/1112.3663?context=cond-mat.stat-mech
    [32] Salimi Sartakhti J, Manshaei M H, Sadeghi M. MMP-TIMP interactions in cancer invasion:an evolutionary game-theoretical framework. Journal of Theoretical Biology, 2017, 412:17-26 doi: 10.1016/j.jtbi.2016.09.019
    [33] Perc M, Jordan J J, Rand D G, Wang Z, Boccaletti S, Szolnoki A. Statistical physics of human cooperation. Physics Reports, 2017, 687:1-51 doi: 10.1016/j.physrep.2017.05.004
    [34] Wang Z, Jusup M, Wang R W, Shi L, Iwasa Y, Moreno Y, Kurths J. Onymity promotes cooperation in social dilemma experiments. Science Advances, 2017, 3(3):Article No.e1601444 doi: 10.1126/sciadv.1601444
    [35] Allen B, Lippner G, Chen Y T, Fotouhi B, Momeni N, Yau S T, Nowak M A. Evolutionary dynamics on any population structure. Nature, 2017, 544(7649):227-230 doi: 10.1038/nature21723
    [36] Taylor C, Nowak M A. Transforming the dilemma. Evolution, 2007, 61(10):2281-2292 doi: 10.1111/evo.2007.61.issue-10
    [37] Rand D G, Nowak M A. Human cooperation. Trends in Cognitive Sciences, 2013, 17(8):413-425 doi: 10.1016/j.tics.2013.06.003
    [38] Nowak M A. Five rules for the evolution of cooperation. Science, 2006, 314(5805):1560-1563 doi: 10.1126/science.1133755
    [39] Zaggl M A. Eleven mechanisms for the evolution of cooperation. Journal of Institutional Economics, 2014, 10(2):197-230 doi: 10.1017/S1744137413000374
    [40] Boyd R, Richerson P J. The evolution of indirect reciprocity. Social Networks, 1989, 11(3):213-236 doi: 10.1016/0378-8733(89)90003-8
    [41] Wedekind C. Give and ye shall be recognized. Science, 1998, 280(5372):2070-2071 http://www.sciencemag.org/content/280/5372/2070.2.summary?related-urls=yes&legid=sci;280/5372/2070b
    [42] Ferriére R. Evolutionary biology:help and you shall be helped. Nature, 1998, 393(6685):517-519 doi: 10.1038/31102
    [43] Nowak M A, Sigmund K. Evolution of indirect reciprocity by image scoring. Nature, 1998, 393(6685):573-577 doi: 10.1038/31225
    [44] Nowak M A, Sigmund K. The dynamics of indirect reciprocity. Journal of Theoretical Biology, 1998, 194(4):561-574 doi: 10.1006/jtbi.1998.0775
    [45] Nowak M A, Sigmund K. Evolution of indirect reciprocity. Nature, 2005, 437(6685):1291-1298 https://www.unil.ch/files/live/sites/dee/files/shared/textes/Nowak_Sigmund_Nature_2005.pdf
    [46] Wedekind C, Braithwaite A V A. The long-term benefits of human generosity in indirect reciprocity. Current Biology, 2002, 12(12):1012-1015 doi: 10.1016/S0960-9822(02)00890-4
    [47] Gardenfors P. Games, Actions and Social Software. Berlin:Springer-Verlag, 2012. 164-183
    [48] Resnick P, Kuwabara K, Zeckhauser R, Zeckhauser R, Friedman E. Reputation systems. Communications of the ACM, 2000, 43(12):45-48 doi: 10.1145/355112.355122
    [49] Bolton G E, Katok E, Ockenfels A. How effective are electronic reputation mechanisms? An experimental investigation. Management Science, 2004, 50(11):1587-1602 doi: 10.1287/mnsc.1030.0199
    [50] Resnick P, Zeckhauser R, Swanson J R, Lockwood K. The value of reputation on eBay:a controlled experiment. Experimental Economics, 2006, 9(2):79-101 doi: 10.1007/s10683-006-4309-2
    [51] Geunes J, Akçali E, Pardalos P M, Romeijn H E, Shen Z J M. Applications of Supply Chain Management and E-Commerce Research. Boston:Springer-Verlag, 2005. 195-216
    [52] Lucking-Reiley D, Bryan D, Prasad N, Reeves D. Pennies from eBay:the determinants of price in online auctions. The Journal of Industrial Economics, 2007, 55(2):223-233 doi: 10.1111/joie.2007.55.issue-2
    [53] Greiner B, Levati M V. Indirect reciprocity in cyclical networks:an experimental study. Journal of Economic Psychology, 2003, 26(5):711-731 https://www.sciencedirect.com/science/article/pii/S0167487005000334
    [54] Pfeiffer T, Rutte C, Killingback T, Taborsky M, Bonhoeffer S. Evolution of cooperation by generalized reciprocity. Proceedings of the Royal Society B, 2005, 272(1568):1115-1120 doi: 10.1098/rspb.2004.2988
    [55] Chiong R, Kirley M. Promotion of cooperation in social dilemma games via generalised indirect reciprocity. Connection Science, 2015, 27(4):417-433 doi: 10.1080/09540091.2015.1080226
    [56] Nowak M A, Roch S. Upstream reciprocity and the evolution of gratitude. Proceedings of the Royal Society B, 2007, 274(1610):605-610 doi: 10.1098/rspb.2006.0125
    [57] Iwagami A, Masuda N. Upstream reciprocity in heterogeneous networks. Journal of Theoretical Biology, 2010, 265(3):297-305 doi: 10.1016/j.jtbi.2010.05.010
    [58] Roberts G. Partner choice drives the evolution of cooperation via indirect reciprocity. PLoS One, 2015, 10(6):Article No.e0129442 doi: 10.1371/journal.pone.0129442
    [59] Swakman V, Molleman L, Ule A, Egas M. Reputation-based cooperation:empirical evidence for behavioral strategies. Evolution and Human Behavior, 2016, 37(3):230-235 doi: 10.1016/j.evolhumbehav.2015.12.001
    [60] dos Santos M, Plací S, Wedekind C. Stochasticity in economic losses increases the value of reputation in indirect reciprocity. Scientific Reports, 2015, 5:Article No.18182 https://www.researchgate.net/publication/286897806_Stochasticity_in_economic_losses_increases_the_value_of_reputation_in_indirect_reciprocity
    [61] Berger U, Grüne A. On the stability of cooperation under indirect reciprocity with first-order information. Games and Economic Behavior, 2016, 98:19-33 doi: 10.1016/j.geb.2016.05.003
    [62] Tian L L, Li M C, Wang Z. Cooperation enhanced by indirect reciprocity in spatial prisoner's dilemma games for social P2P systems. Physica A:Statistical Mechanics and its Applications, 2016, 462:1252-1260 doi: 10.1016/j.physa.2016.07.004
    [63] Wedekind C, Milinski M. Cooperation through image scoring in humans. Science, 2000, 288(5467):850-852 doi: 10.1126/science.288.5467.850
    [64] Leimar O, Hammerstein P. Evolution of cooperation through indirect reciprocity. Proceedings of the Royal Society B, 2001, 268(1468):745-753 doi: 10.1098/rspb.2000.1573
    [65] Milinski M, Semmann D, Bakker T C M, Krambeck H J. Cooperation through indirect reciprocity:image scoring or standing strategy? Proceedings of the Royal Society B, 2001, 268(1484):2495-2501 doi: 10.1098/rspb.2001.1809
    [66] Panchanathan K, Boyd R. A tale of two defectors:the importance of standing for evolution of indirect reciprocity. Journal of Theoretical Biology, 2003, 224(1):115-126 doi: 10.1016/S0022-5193(03)00154-1
    [67] Fehr E, Gächter S. Altruistic punishment in humans. Nature, 2002, 415(6868):137-140 doi: 10.1038/415137a
    [68] Suzuki S, Akiyama E. Evolution of indirect reciprocity in groups of various sizes and comparison with direct reciprocity. Journal of Theoretical Biology, 2007, 245(3):539-552 doi: 10.1016/j.jtbi.2006.11.002
    [69] Tanabe S, Suzuki H, Masuda N. Indirect reciprocity with trinary reputations. Journal of Theoretical Biology, 2013, 317:338-347 doi: 10.1016/j.jtbi.2012.10.031
    [70] Berger U. Learning to cooperate via indirect reciprocity. Games and Economic Behavior, 2011, 72(1):30-37 doi: 10.1016/j.geb.2010.08.009
    [71] Ohtsuki H, Iwasa Y, Nowak M A. Indirect reciprocity provides only a narrow margin of efficiency for costly punishment. Nature, 2009, 457(7225):79-82 doi: 10.1038/nature07601
    [72] Whitaker R M, Colombo G B, Allen S M, Dunbar R I M. A dominant social comparison heuristic unites alternative mechanisms for the evolution of indirect reciprocity. Scientific Reports, 2016, 6:Article No.31459 doi: 10.1038/srep31459
    [73] Espín A M, Exadaktylos F, Neyse L. Heterogeneous motives in the trust game:a tale of two roles. Frontiers in Psychology, 2016, 7:Article No.728 doi: 10.3389/fpsyg.2016.00728/full
    [74] Burks S V, Carpenter J P, Verhoogen E. Playing both roles in the trust game. Journal of Economic Behavior & Organization, 2003, 51(2):195-216 https://www.sciencedirect.com/science/article/pii/S0167268102000938
    [75] Wu J H, Balliet D, Van Lange P A M. Gossip versus punishment:the efficiency of reputation to promote and maintain cooperation. Scientific Reports, 2016, 6:Article No.23919 doi: 10.1038/srep23919
    [76] Eckel C C, Grossman P J. Altruism in anonymous dictator games. Games and Economic Behavior, 1996, 16(2):181-191 doi: 10.1006/game.1996.0081
    [77] Bardsley N. Dictator game giving:altruism or artefact? Experimental Economics, 2008, 11(2):122-133 doi: 10.1007/s10683-007-9172-2
    [78] Engel C. Dictator games:a meta study. Experimental Economics, 2011, 14(4):583-610 doi: 10.1007/s10683-011-9283-7
    [79] Deng X Y, Liu Q, Sadiq R, Deng Y. Impact of roles assignation on heterogeneous populations in evolutionary dictator game. Scientific Reports, 2014, 4:Article No.6937
    [80] Schank J C, Smaldino P E, Miller M L. Evolution of fairness in the dictator game by multilevel selection. Journal of Theoretical Biology, 2015, 382:64-73 doi: 10.1016/j.jtbi.2015.06.031
    [81] Strang S, Grote X, Kuss K, Park S Q, Weber B. Generalized negative reciprocity in the dictator game-how to interrupt the chain of unfairness. Scientific Reports, 2016, 6:Article No.22316 doi: 10.1038/srep22316
    [82] Piazza J, Bering J M. Concerns about reputation via gossip promote generous allocations in an economic game. Evolution and Human Behavior, 2008, 29(3):172-178 doi: 10.1016/j.evolhumbehav.2007.12.002
    [83] Milinski M, Semmann D, Krambeck H J. Reputation helps solve the 'tragedy of the commons'. Nature, 2002, 415(6870):424-426 doi: 10.1038/415424a
    [84] Hauert C, De Monte S, Hofbauer J, Sigmund K. Replicator dynamics for optional public good games. Journal of Theoretical Biology, 2002, 218(2):187-194 doi: 10.1006/jtbi.2002.3067
    [85] Brandt H, Hauert C, Sigmund K. Punishment and reputation in spatial public goods games. Proceedings of the Royal Society B, 2003, 270(1519):1099-1104 doi: 10.1098/rspb.2003.2336
    [86] Hauert C. Replicator dynamics of reward & reputation in public goods games. Journal of Theoretical Biology, 2010, 267(1):22-28 doi: 10.1016/j.jtbi.2010.08.009
    [87] Li A M, Wu T, Cong R, Wang L. One step memory of group reputation is optimal to promote cooperation in public goods games. EPL, 2013, 103(3):Article No.30007 doi: 10.1209/0295-5075/103/30007
    [88] Feinberg M, Willer R, Schultz M. Gossip and ostracism promote cooperation in groups. Psychological Science, 2014, 25(3):656-664 doi: 10.1177/0956797613510184
    [89] Sigmund K. Moral assessment in indirect reciprocity. Journal of Theoretical Biology, 2012, 299:25-30 doi: 10.1016/j.jtbi.2011.03.024
    [90] Fehr E, Fischbacher U. Social norms and human cooperation. Trends in Cognitive Sciences, 2004, 8(4):185-190 doi: 10.1016/j.tics.2004.02.007
    [91] Ohtsuki H, Iwasa Y. How should we define goodness?——reputation dynamics in indirect reciprocity. Journal of Theoretical Biology, 2004, 231(1):107-120 doi: 10.1016/j.jtbi.2004.06.005
    [92] Brandt H, Sigmund K. The logic of reprobation:assessment and action rules for indirect reciprocation. Journal of Theoretical Biology, 2004, 231(4):475-486 doi: 10.1016/j.jtbi.2004.06.032
    [93] Ohtsuki H, Iwasa Y. The leading eight:social norms that can maintain cooperation by indirect reciprocity. Journal of Theoretical Biology, 2006, 239(4):435-444 doi: 10.1016/j.jtbi.2005.08.008
    [94] Ohtsuki H, Iwasa Y. Global analyses of evolutionary dynamics and exhaustive search for social norms that maintain cooperation by reputation. Journal of Theoretical Biology, 2007, 244(3):518-531 doi: 10.1016/j.jtbi.2006.08.018
    [95] Pacheco J M, Santos F C, Chalub F A C C. Stern-judging:a simple, successful norm which promotes cooperation under indirect reciprocity. PLoS Computational Biology, 2007, 2(12):Article No.e178 https://www.researchgate.net/publication/6604852_Stern-Judging_A_Simple_Successful_Norm_Which_Promotes_Cooperation_under_Indirect_Reciprocity
    [96] Ohtsuki H. Reactive strategies in indirect reciprocity. Journal of Theoretical Biology, 2004, 227(3):299-314 doi: 10.1016/j.jtbi.2003.11.008
    [97] Dawes R M, Messick D M. Social dilemmas. International Journal of Psychology, 2000, 35(2):111-116 doi: 10.1080/002075900399402
    [98] Fehr E, Fischbacher U. The nature of human altruism. Nature, 2003, 425(6960):785-791 doi: 10.1038/nature02043
    [99] Suzuki S, Akiyama E. Three-person game facilitates indirect reciprocity under image scoring. Journal of Theoretical Biology, 2007, 249(1):93-100 doi: 10.1016/j.jtbi.2007.07.017
    [100] Berger U, Grüne A. Evolutionary Stability of Indirect Reciprocity by Image Scoring, Department of Economics Working Papers, WU Vienna University of Economics and Business, Vienna, 2014. 1-22
    [101] Uchida S, Sigmund K. The competition of assessment rules for indirect reciprocity. Journal of Theoretical Biology, 2010, 263(1):13-19 doi: 10.1016/j.jtbi.2009.11.013
    [102] Ding H, Cao L, Ren Y Z, Choo K K R, Shi B Y. Reputation-based investment helps to optimize group behaviors in spatial lattice networks. PLoS One, 2016, 11(9):Article No.e0162781 doi: 10.1371/journal.pone.0162781
    [103] Dunbar R I M. Gossip in evolutionary perspective. Review of General Psychology, 2004, 8(2):100-110 doi: 10.1037/1089-2680.8.2.100
    [104] Foster E K. Research on gossip:taxonomy, methods, and future directions. Review of General Psychology, 2004, 8(2):78-99 doi: 10.1037/1089-2680.8.2.78
    [105] Anderson C, Shirako A. Are individuals' reputations related to their history of behavior? Journal of Personality and Social Psychology, 2008, 94(2):320-333 doi: 10.1037/0022-3514.94.2.320
    [106] Uchida S. Effect of private information on indirect reciprocity. Physical Review E, 2010, 82(2):Article No.036111 https://www.sciencedirect.com/science/article/pii/S0960077913001598
    [107] Nakamura M, Masuda N. Indirect reciprocity under incomplete observation. PLoS Computational Biology, 2011, 7(7):Article No.e1002113 doi: 10.1371/journal.pcbi.1002113
    [108] Ohtsuki H, Iwasa Y, Nowak M A. Reputation effects in public and private interactions. PLoS Computational Biology, 2015, 11(11):Article No.e1004527 doi: 10.1371/journal.pcbi.1004527
    [109] Brandt H, Sigmund K. Indirect reciprocity, image scoring, and moral hazard. Proceedings of the National Academy of Sciences of the United States of America, 2005, 102(7):2666-2670 doi: 10.1073/pnas.0407370102
    [110] Számadó S, Szalai F, Scheuring I. Deception undermines the stability of cooperation in games of indirect reciprocity. PLoS One, 2016, 11(1):Article No.e0147623 doi: 10.1371/journal.pone.0147623
    [111] Nakamaru M, Kawata M. Evolution of rumours that discriminate lying defectors. Evolutionary Ecology Research, 2004, 6(2):261-283 https://www.researchgate.net/publication/276295304_Evolution_of_rumours_that_discriminate_lying_defectors
    [112] Seki M, Nakamaru M. A model for gossip-mediated evolution of altruism with various types of false information by speakers and assessment by listeners. Journal of Theoretical Biology, 2016, 407:90-105 doi: 10.1016/j.jtbi.2016.07.001
    [113] Franks H, Griffiths N. Robust reputation in decentralized markets. Computational Intelligence, 2015, 31(4):569-592 doi: 10.1111/coin.v31.4
    [114] Suzuki S, Kimura H. Indirect reciprocity is sensitive to costs of information transfer. Scientific Reports, 2013, 3:Article No.1435 doi: 10.1038/srep01435
    [115] Sommerfeld R D, Krambeck H J, Semmann D, Milinski M. Gossip as an alternative for direct observation in games of indirect reciprocity. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(44):17435-17440 doi: 10.1073/pnas.0704598104
    [116] Sommerfeld R D, Krambeck H J, Milinski M. Multiple gossip statements and their effect on reputation and trustworthiness. Proceedings of the Royal Society B, 2008, 275(1650):2529-2536 doi: 10.1098/rspb.2008.0762
    [117] Lorenz J, Rauhut H, Schweitzer F, Helbing D. How social influence can undermine the wisdom of crowd effect. Proceedings of the National Academy of Sciences of the United States of America, 2011, 108(22):9020-9025 doi: 10.1073/pnas.1008636108
    [118] Giardini F, Norling E. Multi-Agent-Based Simulation XV. Switzerland:Springer-Verlag, 2014. 104-118
    [119] Wu J H, Balliet D, Van Lange P A M. Reputation management:why and how gossip enhances generosity. Evolution and Human Behavior, 2016, 37(3):193-201 doi: 10.1016/j.evolhumbehav.2015.11.001
    [120] Wu J H, Balliet D, Van Lange P A M. When does gossip promote generosity? Indirect reciprocity under the shadow of the future. Social Psychological and Personality Science, 2015, 6(8):923-930 doi: 10.1177/1948550615595272
    [121] Wu J H, Balliet D, Van Lange P A M. Reputation, gossip, and human cooperation. Social and Personality Psychology Compass, 2016, 10(6):350-364 doi: 10.1111/spc3.v10.6
    [122] Hess N H, Hagen E H. Psychological adaptations for assessing gossip veracity. Human Nature, 2006, 17(3):337-354 doi: 10.1007/s12110-006-1013-z
    [123] Giardini F, Vilone D. Evolution of gossip-based indirect reciprocity on a bipartite network. Scientific Reports, 2016, 6:Article No.37931 doi: 10.1038/srep37931
    [124] Giardini F. Deterrence and transmission as mechanisms ensuring reliability of gossip. Cognitive Processing, 2012, 13(S2):465-475 doi: 10.1007/s10339-011-0421-0
    [125] Pfeiffer T, Tran L, Krumme C, Rand D G. The value of reputation. Journal of the Royal Society Interface, 2012, 9(76):2791-2797 doi: 10.1098/rsif.2012.0332
    [126] Antonioni A, Sánchez A, Tomassini M. Cooperation survives and cheating pays in a dynamic network structure with unreliable reputation. Scientific Reports, 2016, 6:Article No.27160 doi: 10.1038/srep27160
    [127] Zhang Y L, Fu F, Wu T, Xie G M, Wang L. A tale of two contribution mechanisms for nonlinear public goods. Scientific Reports, 2013, 3:Article No.2021 doi: 10.1038/srep02021
    [128] Zhang Y L, Wu T, Cheng X J, Xie G M, Wang L. Mixed strategy under generalized public goods games. Journal of Theoretical Biology 2013, 334:52-60 doi: 10.1016/j.jtbi.2013.05.011
    [129] Zhang Y L, Fu F, Wu T, Xie G M, Wang L. Inertia in strategy switching transforms the strategy evolution. Physical Review E, 2011, 84(6):Article No.066103 http://adsabs.harvard.edu/abs/2011PhRvE..84f6103Z
    [130] Lieberman E, Hauert C, Nowak M A. Evolutionary dynamics on graphs. Nature, 2005, 433(7023):312-316 doi: 10.1038/nature03204
    [131] Ohtsuki H, Hauert C, Lieberman E, Nowak M A. A simple rule for the evolution of cooperation on graphs and social networks. Nature, 2006, 441(7092):502-505 doi: 10.1038/nature04605
    [132] Nowak M A, Tarnita C E, Antal T. Evolutionary dynamics in structured populations. Philosophical Transactions of the Royal Society of London, 2009, 365(1537):19-30 https://scholar.princeton.edu/sites/default/files/philtrans10_0.pdf
    [133] Hauert C, Imhof L A. Evolutionary games in deme structured, finite populations. Journal of Theoretical Biology, 2012, 299:106-112 doi: 10.1016/j.jtbi.2011.06.010
    [134] Vilone D, Giardini F, Paolucci M. Partner selection supports reputation-based cooperation in a Public Goods Game. Social Science Electronic Publishing, 2014. http://www.pnas.org/content/113/45/E7003.full
    [135] Efferson C, Lalive R, Fehr E. The coevolution of cultural groups and ingroup favoritism. Science, 2008, 321(5897):1844-1849 doi: 10.1126/science.1155805
    [136] Perc M, Szolnoki A. Coevolutionary games——a mini review. Biosystems, 2010, 99(2):109-125 doi: 10.1016/j.biosystems.2009.10.003
    [137] Fehl K, Van der Post D J, Semmann D. Co-evolution of behaviour and social network structure promotes human cooperation. Ecology Letters, 2011, 14(6):546-551 doi: 10.1111/j.1461-0248.2011.01615.x
    [138] Wang J, Suri S, Watts D J. Cooperation and assortativity with dynamic partner updating. Proceedings of the National Academy of Sciences of the United States of America, 2012, 109(36):14363-14368 doi: 10.1073/pnas.1120867109
    [139] Jordan J J, Rand D G, Arbesman S, Fowler J H, Christakis N A. Contagion of cooperation in static and fluid social networks. PLoS One, 2013, 8(6):Article No.e66199 doi: 10.1371/journal.pone.0066199
    [140] Zhang Y L, Liu A Z, Sun C Y. Impact of migration on the multi-strategy selection in finite group-structured populations. Scientific Reports, 2016, 6:Article No.35114 doi: 10.1038/srep35114
    [141] Zhang Y L, Su Q, Sun C Y. Intermediate-range migration furnishes a narrow margin of efficiency in the two-strategy competition. PLoS One, 2016, 11(5):Article No.e0155787 doi: 10.1371/journal.pone.0155787
    [142] Zhang Y L, Fu F, Chen X J, Xie G M, Wang L. Cooperation in group-structured populations with two layers of interactions. Scientific Reports, 2015, 5:Article No.17446 doi: 10.1038/srep17446
    [143] Fu F, Hauert C, Nowak M A, Wang L. Reputation-based partner choice promotes cooperation in social networks. Physical Review E, 2008, 78(2):Article No.026117 https://dash.harvard.edu/handle/1/4686797?show=full
    [144] Peleteiro A, Burguillo J C, Chong S Y. Exploring indirect reciprocity in complex networks using coalitions and rewiring. In:Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems. Paris, France:ACM, 2014. 669-676
    [145] Ding H, Huang J Y, Chen Y F, Ren Y Z. Don't speak to strangers:the suspicious strategy can help to improve cooperation in spatial donation game. In:Proceedings of the 2015 IEEE International Conference on Computer and Information Technology; Ubiquitous Computing and Communications; Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing (CIT/IUCC/DASC/PICOM). Liverpool, Britain:IEEE, 2015. 1954-1959
    [146] Phelps S. Emergence of social networks via direct and indirect reciprocity. Autonomous Agents and Multi-Agent Systems, 2013, 27(3):355-374 doi: 10.1007/s10458-012-9207-8.pdf
    [147] Han X, Shen Z S, Wang W X, Lai Y C, Grebogi C. Reconstructing direct and indirect interactions in networked public goods game. Scientific Reports, 2016, 6:Article No.30241 doi: 10.1038/srep30241
    [148] Kamvar S D, Schlosser M T, Garcia-Molina H. The eigentrust algorithm for reputation management in P2P networks. In:Proceedings of the 12th International Conference on World Wide Web. Budapest, Hungary:ACM, 2003. 640-651
    [149] Xiong L, Liu L. PeerTrust:supporting reputation-based trust for peer-to-peer electronic communities. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(7):843-857 doi: 10.1109/TKDE.2004.1318566
    [150] Yu Y L, Li K Q, Jin Y W, Zhang Y. A trust management model for service-oriented distributed networks. Concurrency and Computation:Practice and Experience, 2013, 25(14):2098-2111 doi: 10.1002/cpe.v25.14
    [151] Resnick P, Zeckhauser R. Trust among strangers in internet transactions:empirical analysis of eBay's reputation system. The Economics of the Internet and E-Commerce. Amsterdam:Emerald Group Publishing Limited, 2002. 127-157
    [152] Josang A, Ismail R. The beta reputation system. In:Proceedings of the 15th Bled Electronic Commerce Conference e-Reality:Constructing the e-Economy. Bled, Slovenia, 2002. 2502-2511
    [153] Zhou R F, Hwang K. PowerTrust:a robust and scalable reputation system for trusted peer-to-peer computing. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(4):460-473 doi: 10.1109/TPDS.2007.1021
    [154] Buragohain C, Agrawal D, Suri S. A game theoretic framework for incentives in P2P systems. In:Proceedings of the 3rd International Conference on Peer-To-Peer Computing. Washington DC, USA:IEEE, 2003. 48-56
    [155] Feldman M, Lai K, Stoica I, Chuang J. Robust incentive techniques for peer-to-peer networks. In:Proceedings of the 5th ACM Conference on Electronic Commerce. New York, USA:ACM, 2004. 102-111
    [156] Liu Y, Xiong N, Park J H, Yang C, Xu K. Fair incentive mechanism with pyramidal structure for peer-to-peer networks. IET Communications, 2010, 4(1):1-12 doi: 10.1049/iet-com.2008.0702
    [157] Ma R T B, Lee S C M, Lui J C S, Yau D K Y. Incentive and service differentiation in P2P networks:a game theoretic approach. IEEE/ACM Transactions on Networking, 2006, 14(5):978-991 doi: 10.1109/TNET.2006.882904
    [158] Gupta R, Somani A K. Game theory as a tool to strategize as well as predict peers' behavior in peer-to-peer networks. In:Proceedings of the 11th International Conference on Parallel and Distributed Systems. Fukuoka, Japan:IEEE, 2005. 244-249
    [159] Mortazavi B, Kesidis G. Cumulative reputation systems for peer-to-peer content distribution. In:Proceedings of the 40th Annual Conference on Information Sciences and Systems. Princeton NJ, USA:IEEE, 2006. 1546-1552
    [160] Mejia M, Peña N, Muñoz J L, Esparza O, Alzate M A. A game theoretic trust model for on-line distributed evolution of cooperation inMANETs. Journal of Network and Computer Applications, 2011, 34(1):39-51 doi: 10.1016/j.jnca.2010.09.007
    [161] Zhao B Q, Lui J C S, Chiu D M. Analysis of adaptive incentive protocols for P2P networks. In:Proceedings of the 2009 IEEE INFOCOM. Rio de Janeiro, Brazil:IEEE, 2009. 325-333
    [162] Zuo F, Zhang W. An evolutionary game-based mechanism for routing P2P network flow among selfish peers. Journal of Networks, 2014, 9(1):10-17 https://www.researchgate.net/publication/274663775_An_Evolutionary_Game-Based_Mechanism_for_Routing_P2P_Network_Flow_among_Selfish_Peers
    [163] Wang Y F, Nakao A, Vasilakos A V, Ma J H. P2P soft security:on evolutionary dynamics of P2P incentive mechanism. Computer Communications, 2011, 34(3):241-249 doi: 10.1016/j.comcom.2010.01.021
    [164] Cui G H, Li M C, Wang Z, Ren J K, Jiao D, Ma J H. Analysis and evaluation of incentive mechanisms in P2P networks:a spatial evolutionary game theory perspective. Concurrency and Computation:Practice and Experience, 2015, 27(12):3044-3064 doi: 10.1002/cpe.v27.12
    [165] Lu K, Wang J L, Li M C. An Eigentrust dynamic evolutionary model in P2P file-sharing systems. Peer-to-Peer Networking and Applications, 2016, 9(3):599-612 doi: 10.1007/s12083-015-0416-1
    [166] Chen Z D, Qiu Y H, Liu J J, Xu L. Incentive mechanism for selfish nodes in wireless sensor networks based on evolutionary game. Computers & Mathematics with Applications, 2011, 62(9):3378-3388 https://www.researchgate.net/publication/220513393_Incentive_mechanism_for_selfish_nodes_in_wireless_sensor_networks_based_on_evolutionary_game
    [167] Zhu J, Jiang D D, Yuan Y H, Fang W L. An evolutionary game theory-based channel access mechanism for wireless multimedia sensor network with rate-adaptive applications. Multimedia Tools and Applications, 2016, 75(22):14329-14349 doi: 10.1007/s11042-016-3403-5
    [168] Zhao S S, Zhu Q, Zhu H B. Evolutionary game theoretical approach to dynamic spectrum sharing. Journal of Computational Information Systems, 2012, 8(10):4225-4232 https://www.researchgate.net/publication/290229044_Evolutionary_game_theoretical_approach_to_dynamic_spectrum_sharing
    [169] Jiang C X, Chen Y, Gao Y, Liu K J R. Joint spectrum sensing and access evolutionary game in cognitive radio networks. IEEE Transactions on Wireless Communications, 2013, 12(5):2470-2483 doi: 10.1109/TWC.2013.031813.121135
    [170] Wu D, Liu H, Bi Y R, Zhu H S. Evolutionary game theoretic modeling and repetition of media distributed shared in P2P-based VANET. International Journal of Distributed Sensor Networks, 2014, 4(6):Article No.718639 https://www.researchgate.net/publication/275065915_Evolutionary_Game_Theoretic_Modeling_and_Repetition_of_Media_Distributed_Shared_in_P2P-Based_VANET
    [171] 张慧, 王坤峰, 王飞跃.深度学习在目标视觉检测中的应用进展与展望.自动化学报, 2017, 43(8):1289-1305 http://www.aas.net.cn/CN/abstract/abstract19104.shtml

    Zhang Hui, Wang Kun-Feng, Wang Fei-Yue. Advances and perspectives on applications of deep learning in visual object detection. Acta Automatica Sinica, 2017, 43(8):1289-1305 http://www.aas.net.cn/CN/abstract/abstract19104.shtml
    [172] 游科友, 谢立华.网络控制系统的最新研究综述.自动化学报, 2013, 39(2):101-118 http://www.aas.net.cn/CN/abstract/abstract17806.shtml

    You Ke-You, Xie Li-Hua. Survey of recent progress in networked control systems. Acta Automatica Sinica, 2013, 39(2):101-118 http://www.aas.net.cn/CN/abstract/abstract17806.shtml
    [173] 王丽媛, 郭戈, 庄严.网络控制系统发送功率分配问题研究.自动化学报, 2017, 43(8):1350-1357 http://www.aas.net.cn/CN/abstract/abstract19109.shtml

    Wang Li-Yuan, Guo Ge, Zhuang Yan. Transmission power allocation for networked control systems. Acta Automatica Sinica, 2017, 43(8):1350-1357 http://www.aas.net.cn/CN/abstract/abstract19109.shtml
    [174] 胡艳艳, 金增旺, 薛晓玲, 孙长银.基于异步IMM融合滤波的网络化系统故障诊断.自动化学报, 2017, 43(8):1329-1338 http://www.aas.net.cn/CN/abstract/abstract19107.shtml

    Hu Yan-Yan, Jin Zeng-Wang, Xue Xiao-Ling, Sun Chang-Yin. Fault diagnosis for networked systems by asynchronous IMM fusion filtering. Acta Automatica Sinica, 2017, 43(8):1329-1338 http://www.aas.net.cn/CN/abstract/abstract19107.shtml
  • 加载中
  • 图(4) / 表(3)
    计量
    • 文章访问数:  2130
    • HTML全文浏览量:  468
    • PDF下载量:  1237
    • 被引次数: 0
    出版历程
    • 收稿日期:  2017-04-14
    • 录用日期:  2017-09-06
    • 刊出日期:  2018-01-01

    目录

    /

    返回文章
    返回