基于Hebb规则的分布神经网络学习算法

第 30 卷 　第 8 期 2007 年 8 月 计 　　算 　　机 　　学 　　报 CHIN ESE J OU RNAL OF COMPU TERS Vol. 30 No. 8 Aug. 2007 　 收稿日期 :2007203207 ;修改稿收到日期 :2007205218. 本课题得到国家自然科学基金 (60573128)和教育部高校博士点基金 (20060183043) 资助. 田大新 ,男 ,1980 年生 ,博士研究生 ,主要研究方向为计算机网络安全与网络 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 、机器学习、人工神经网络. E2mail : daxin222 @ 163. com. 刘衍珩 (通信联系人) ,男 ,1958 年生 ,博士 ,教授 ,博士生导师 ,主要研究领域为计算机通信与网络、移动 IP、网络服务质量. E2mail : lyh_lb_lk @yahoo . com. cn. 李　宾 ,女 ,1960 年生 , 副教授 , 主要研究方向为人工智能、数据挖掘. 基于 Hebb 规则的分布神经网络学习算法 田大新1) ,2) 　刘衍珩1) ,2) 　李　宾3) 　吴　静1) ,2) 1) (吉林大学计算机科学与技术学院　长春　130012) 2) (吉林大学符号计算与知识工程教育部重点实验室　长春　130012) 3) (吉林大学数学学院　长春　130012) 摘 　要 　随着知识发现与数据挖掘领域数据量的不断增加 ,为了处理大规模数据 , scaling up 学习成为 KDD 的热 点研究领域.文中提出了基于 Hebb 规则的分布式神经网络学习算法实现 scaling up 学习. 为了提高学习速度 ,完 整数据集被分割成不相交的子集并由独立的子神经网络来学习 ;通过对算法完整性及竞争 Hebb 学习的风险界的 分析 ,采用增长和修剪策略避免分割学习降低算法的学习精度. 对该算法的测试实验首先采用基准测试数据 circle2 in2the2square 测试了其学习能力 ,并与 SVM ,ARTMA P 和 BP 神经网络进行比较 ;然后采用 UCI 中的数据集 US2 Census1990 测试其对大规模数据的学习性能. 关键词 　scaling up ;数据分割 ; Hebb 规则 ;分布式学习 ;竞争学习 中图法分类号 TP183 Distributed Neural Net work Learning Algorithm Based on Hebb Rule TIAN Da2Xin1) ,2) 　L IU Yan2Heng1) ,2) 　L I Bin3) 　WU Jing1) ,2) 1) ( College of Com puter Science and Technology , J i lin Universit y , Changchun 　130012) 2) ( Key L aboratory of S y mbolic Com putation and Knowled ge Engineering of Minist ry of Education , J ilin University , Changchun 130012) 3) ( College of M at hematics , J i l in Universit y , Changchun　130012) Abstract 　 In t he fields of knowledge discovery and data mining t he amount of data available for building classifiers or regression models is growing very fast . Therefore , t here is a great need for scaling up inductive learning algorit hms that are capable of handling very2large dataset s and , sim2 ultaneously , being comp utationally efficient and scalable. In t his paper a dist ributed neural net2 work based on Hebb rule is p resented to improve t he speed and scalability of inductive learning. The speed is improved by doing t he algorit hm on disjoint subset s instead of t he entire dataset . To avoid t he accuracy being degraded as compared to running a single algorit hm wit h t he entire data , a growing and pruning policy is adopted , which is based on t he analysis of completeness and risk bounds of competitive Hebb learning. In t he experiment s , t he accuracy of t he algorit hm is tested on a small benchmark (circle2in2t he2square) and compared wit h SVM , A R TMA P and BP neural network. The performance on the large dataset ( U SCensus1990Data) is evaluated on t he data f rom UCI repository. Keywords 　scaling up ; data partition ; Hebb rule ; dist ributed learning ; competitive learning 1 　引　言 随着商业、政府、科研等领域信息数据的不断增 加 ,知识发现和数据挖掘 ( KDD) 领域的科研人员通 过对已有的机器学习、数据挖掘、模式识别等方法进 行扩展以使其能够应用于大规模数据集 ,提出了 scaling up 归纳学习方法和许多实现技术. Scaling up 学习方法关心的不仅仅是提高学习算法速度的 问题 ,更关心的是扩展学习算法能否从大规模数据 中有效地学习到知识. 传统学习算法研究的重点是 在有限 (小规模)样本环境下如何使学习算法具有较 好的推广 (泛化) 能力 ,面临的主要问题是过学习 (overfit ting)问题 ;而在大规模数据集下由于时间和 空间的约束有可能无法对所有样本进行学习 ,从而 产生了欠学习 ( underfit ting) 问题. 研究人员提出的 scaling up 学习实现技术按大类分包括 : 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 快速 的算法、利用关系表达和对数据进行分割等. 快速算 法的研究包括降低渐进复杂性、优化搜索和表示、利 用问题自身的并行特征等[123 ] ;关系表达主要研究的 是充分利用知识的内在关系[ 425 ] ;数据分割技术的研 究包括将数据分割成子集、采样数据集、属性选择 等[628 ] . 基于数据分割的 scaling up 归纳学习的主要过 程是首先按分割规则 R 将完整数据集分割成子集 ; 然后采用学习算法 L 对子集进行学习 ;最后采用合 并机制 C将学习结果组合得到最终的知识模型. 在 该领域研究人员通过对上述过程中 R , L , C 研究的 侧重点不同 ,设计出了不同的 scaling up 学习算法. 一类方法侧重对分割规则 R 的研究 ,其主要思想是 从大规模数据集中采样出包含完整数据特征的小规 模数据集 ,并对小规模数据进行学习从而在不改变 传统学习算法的前提下实现对大规模数据的学习. 为了降低采样对学习性能的影响 ,研究人员提出了 递增采样机制 ,其对应的分割规则 R 是将样本 D 分 割成 D = { D0 , D1 , ⋯, Dn } ,其中 D i < D j ( i < j ) . 按 子集增长比例的不同研究人员提出了算术采样[9 ]和 几何采样[10 ] . 为了判断采样子集多大时合适 ,通常 采用学习曲线方法[11 ] . 上述方法存在的主要问题是 通过对采样的样本进行学习得到模型可能无法完整 描述数据中暗含的知识 ,因为有可能部分知识包含 在没有被采样的样本中. 即使通过学习曲线方法能 有效提高系统的准确率 ,但其有可能导致采样样本 不断增加而使学习算法仍然面临大规模数据处理的 难题. 基于统计学的平衡样本数量和错误率的理论 分析[12 ]以及增量学习算法[13214 ] 的研究是克服上述 难题的重要途径. 另一类研究重点放在学习算法 L 和合并机制 C 上. 这类 scaling up 归纳学习方法的分割规则 R 非 常简单 ,只是将数据集 D 随机、均匀分割成 n 个互 不相交的子集{ D0 , D1 , ⋯, Dn} ,每个子集 D i采用学 习算法 L i对样本进行学习并通过合并机制 C 得到 最终描述系统的知识模型 (规则集) . 各个子集对应 的学习算法既可以相同也可以不同 ,如元学习算法 采用不同的学习算法训练各个子集[15216 ] . 合并机制 C解决的主要问题是如何将各个子集的学习结果合 并起来组合成最终决策. 除了常用的投票、加权投票 法[17 ]外 , 元学习采用组合、仲裁法[18 ] , SCANN 方 法[19 ]综合叠加[20 ] 、一致性分析和最近邻方法. 合并 机制也是模块神经网络[21 ] 、神经网络集成[22 ] 、学习 委员会机[23 ]研究的重点. 此领域的研究出发点是将 一个复杂任务分解成较简单的一系列子任务 ,每个 子任务用一个神经网络 (子模块) 来完成 ,或是通过 多个专家利用 Boo sting/ AdaBoost 方法提高系统的 准确率. 由于其学习过程仍然是集中的 ,因此如何将 上述方法应用于大规模数据尚无有效机制. 通过上 述合并方法 ,即使各个子集的学习结果具有较大的 误差 ,合并后的学习结果仍可以有效地提高系统的 准确率. 但是在如下情况下合并方法的性能与集中 学习会有较大差距 : ①当存在大量冗余且学习结果 并不精确的子集时 ; ②当准确地预测或分类结果存 在于某一子集中时. 利用相同或不同学习算法对互不相交子集分别 进行学习并对学习结果进行组合的方法 ,既提高了 对大数据集进行处理的速度又能保证学习结果的准 确率. 但目前用于解决大数据集问题的方法主要集 中在决策树类学习算法[24225 ] ,这主要是因为决策树 规则能够将各个子集得到的规则通过合并、剪枝等 方法[26227 ]将局部知识组合成全局知识 ,从而有利于 避免上述两种造成合并方法产生较大误差情况的出 现. 模块神经网络、神经网络集成、学习委员会机等 神经网络方法尽管其体系结构也是多个神经网络对 样本进行学习 ,但现有方法无法有效地应用于大规 模数据处理的原因包括 : ①其学习过程仍是集中式 的 ,即所有或采样样本需提交给每个子神经网络 (模 块、专家) ,然后通过门网、投票等机制来将任务、输 入空间进行分割 ,从而提高系统的准确率 ; ②神经 网络是一种黑箱式系统 ,其知识存储在权重矩阵中 , 不同的神经网络学习算法的权重矩阵含义和应用方 法不同 ,因此无法像合并决策树规则那样通过合并 权重矩阵来组合各个子神经网络的学习结果. 本文 提出了基于 Hebb 规则的分布神经网络学习算法 , 让多个独立的神经网络同时处理随机分割的部分数 据并将所得知识通过集中学习进行组合 ,这样在发 挥单个神经网络并行处理能力的同时使其可以对分 布存储的大规模数据集进行学习. 0831 计 　　算 　　机 　　学 　　报 2007 年 2 　分布神经网络学习算法 神经网络的两个重要特征是分布和并行. 分布 是指一个知识描述分布在多个处理节点中 ;并行是 指计算以并行的方式在分布的处理节点中进行. 尽 管每个独立的神经网络以并行方式处理数据 ,但让 多个分布的神经网络合作处理一个任务则是一个难 点. 因为神经网络的学习过程 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 把所有的样本数 据都提交给神经网络进行训练直至其在一次或多次 循环训练后稳定. 这种机制使得当数据量非常大以 至内存空间无法满足时学习无法进行. 本文提出的 分布神经网络学习算法 ,利用 Hebb 规则的局部学习 特征 ,通过增长、修剪机制实现对大规模数据的处理. 211 　学习过程 学习算法的主要过程如图 1 所示 ,其主要步骤 如下. 1 . 将大块数据集分割成小块 ,然后将小块数据提交给 各个独立的神经网络 ; 2 . 各个神经网络对其分得的子数据集进行学习直至 稳定 ; 3 . 利用各个神经网络的学习结果生成新的数据集 ,该 数据集远小于各个子数据集之和 ; 4 . 对新的数据集进行学习直至稳定. 图 1 　分布神经网络学习过程 每个子神经网络在接收第一个样本向量 x0后 , 添加第一个神经元 w0并置初始值为 x0 ;在后续提交 样本进行训练时 ,首先判断学习是否结束 ,若否 ,则 计算相似度值 , 然后由竞争函数计算出竞争获胜的 神经元 ;若获胜神经元的相似度小于等于相似度门 限值 ,则根据学习算法修正神经元权重值 ,否则添加 新的神经元并将新添加的神经元的权重值置为该次 提交的样本向量 xi . 整个过程包括两个学习阶段 :分布学习和集中 学习. 分布学习的样本为子数据集 ,学习算法既要保 证学习到子数据集中的完整知识 ,又不能丢弃因分 割产生的部分知识 ;集中学习的样本为由各个子神 经网络学习结果组成的新数据集 ,该数据集不仅包 含各子数据集的知识而且样本数量远小于原始数据 集. 一个稳定的 Hebb 神经网络学习到的知识存储 在权重矩阵 W( m ×n) 中 ,其中 m 为神经元的个数 , n 为 每个神经元的维数. 在上述学习过程中每个分布学 习的神经网络中神经元的维数 n 等于每个样本 x (1 ×n) 的维数 ,当神经网络稳定后 ,其权重矩阵 W 的 每一行为从子数据集中学习得到的知识. 例如 ,原始 数据集 X 含有 p ×q 个样本 ,数据集 X 被分割成 p 个子数据集 ( i) X ( i = 1 ,2 , ⋯, p) ,每个子数据集含有 q个样本. 当对 ( i) X 进行学习的神经网络学习稳定 后其权重矩阵 ( i) W 含有 ( i) r 行 ( ( i) r ν q) ,由所有 ( i) W 中的 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 生成新的样本数据集 ŽX 远小于原始数 据集 X. 212 　Hebb 规则 上述学习过程可以通过基于 Hebb 规则类神经 网络学习算法实施是因为该类神经网络具有如下两 个特征 : ①Hebb 学习是一种局部学习 ; ②该类神经 网络的权重向量代表了知识点. 这两个特征确保了 即使代表某类知识的训练样本被分割到多个子集中 也能在分布学习时被保留并在集中学习后被抽取出 来 ,从而避免了当存在大量冗余且学习结果并不精 确的子集时分割学习误差较大的问题. 而其它学习 算法因无法同时具备上述特征而无法采用上述学习 过程对大规模数据进行学习. 如 BP 类学习算法是 一种全局优化过程 ,因此分布学习过程中各子 BP 神经网络会尽最大可能对子集进行学习 ,这种方式 可能会丢弃包含在子集中的不完整的知识点 ;此外 , BP 神经网络的学习结果存储于权重矩阵中 ,权重矩 阵对外界来说是一个黑盒 ,其可用的信息只是针对 某一输入各子 BP 网络给出的分类或回归结果 ,因 此集中学习过程只能采用投票类方法得出最优的结 论 ,而无法通过集中学习对学习结果进一步学习从 而避免子集学习准确率低或某一结论只存在于某一 子集的问题. RBF 类学习算法具备第一类特征 ,但 其第二层网络的权重矩阵也是一个黑盒 ,因此集中 学习时仍面临与 BP 网络同样的问题. 根据 Hebbian 假设 , 可用能量函数表示一个 Hebb 神经元的学习规则 18318 期 田大新等 : 基于 Hebb 规则的分布神经网络学习算法 E(w) = - ψ(wT x) + α2 w 2 2 (1) 其中 , w是突触权重向量 , x 是输入样本向量 ,ψ( ) 为 可微函数 ,αΕ 0 为遗忘系数. 神经元的输出为 y = dψ( v)dv = f ( v) (2) 其中 , v = wT x 是神经元的活跃系数. 通过快速下降 法导出连续时间的学习规则 dw d t = - μ¨w E (w) (3) 其中 ,μ> 0 为学习速度系数 , ¨w E ( w) = 9 E ( w) /9w ,则式 (1) 的梯度为¨w E (w) = - f ( v) 9 v9w +αw = - y x +αw (4) 由此可得单神经元的学习规则为 dw d t = μ[ y x - αw ] (5) 则离散时间的学习规则为 w( t + 1) = w( t) +μ[ y ( t + 1) x( t + 1) - αw ( t) ] (6) 　　在竞争学习中 ,神经网络中的输出神经元彼此 通过竞争来成为活跃的 ,正是这个特性使竞争学习 适合于发现统计上的突出特征. 传统的竞争机制为 胜者全得 ,即每次只有一个神经元是激活的 ,在基于 Hebb 规则的神经网络里 ,除采用胜者全得机制的 AR T[28 ] 、PCA [29 ]等外 ,也有若干输出神经元同时处 于激活状态的 SOM[30 ] 、RPCL [31 ] 等. 为了克服竞争 学习中竞争层神经元个数固定导致无法适用于事先 不知道类别数目、数据提交的顺序和学习速度等参 数的选择会导致类别中心来回振荡以及神经元数目 过多从而导致神经网络过度拟合数据等问题. 除了 上述经典神经网络采用基于 Hebb 规则的竞争学习 算法外 ,还有很多类似的学习算法 ,如 RPCL [31 ] 的 思想是在每次学习中 ,与输入最为相似的神经元得 到学习 ,同时对第二相似的神经元进行惩罚 ,使其中 心远离输入样本 ; D GNN [32 ] 、L TCL [33 ] 对所有神经 元根据竞争的结果实施不同级别的奖励和惩罚. 213 　完整性分析 神经网络学习算法是一个从预测函数集{ L ( y , f W ( x) ) }中选择一个适当的函数 f W 3 ( x) ,使预测期 望风险 R ( f W ( x) ) =∫L ( y , f W ( x) ) d p ( x , y) (7) 最小的过程 ,其中 L ( y , f W ( x) ) 为由于用 f W ( x) 对 y 进行预测造成的损失. 通常概率分布 p ( x , y) 是未知 的 ,无法直接最小化风险泛函 , 但得到了依 d ( xi , W j ) Φλ独立地随机抽取出的观测样本 ( x1 , y1 ) , ( x2 , y2 ) , ⋯, ( xn , y n) (8) 因此采用 经验 班主任工作经验交流宣传工作经验交流材料优秀班主任经验交流小学课改经验典型材料房地产总经理管理经验 风险泛函 Remp ( f W ( x) ) = 1 n ∑ n i = 1 L ( y i , f W ( xi ) ) (9) 来逼近式 (7) 定义的风险泛函. 分布式学习算法对随机分割的数据进行学习的 结果如果等价于对完整数据的学习结果 ,则说明分 布式学习算法具备完整性. 从式 (8) 中的有限数据点 恢复其背后隐含的函数 f ( x , w) 是一个反问题 ,因而 往往是不适定的 ,为此 Tikhonov 提出了正则化方 法解决不适定问题. 正则化理论要求的最小化泛 函为 R (w) = Rs (w) +λR c (w) (10) 其中 Rs (w) 为实际风险项 , Rc ( w) 为正则化项 ,λ为 正则化参数. 正则化的基本思想是通过某些含有解 的先验知识的非负的辅助泛函来使解稳定. 分析结 果表明 ,本文提出的分布式学习方法与采用正则化 理论的学习方法等价. 定理 1 . 　基于 Hebb 规则的分布神经网络学 习算法等价于正则化方法. 证明. 　分布学习得到的权重矩阵 ( i) W 的每一 个行向量 ( i) W j为一部分样本的邻域函数中心 ,因此 对于该部分样本中的一个样本 ( i) Xk , ( i) W j = ( i) Xk + Ak (11) 在新数据集 ( i) ŽX 中 , ( i) ŽXl = ( i) W j + Bm (12) 其中| Aki | Φβ, | Bmi | Φβ合并式 (11) 和式 (12) 得到 ( i) ŽXl = ( i) Xk + Ak + Bm (13) 对于局部风险最小化模型中的误差函数 L ( y , f w ( x) ) 在新数据集 ŽX 中为 L y , f w x + a + b ,将 f w x + a + b 按泰勒级数展开得 f w ( x + a + b) = f w ( x) + ¨ f w ( x + a + b) T ( a + b) + 　12 ( a + b) T ¨2 f w ( x + a + b) ( a + b) + ⋯ = f w ( x) +Δg ( x) (14) 其中| ai + bi | Φ2β, ¨ f ( z) 为 n 元函数 f ( z) = f ( z1 , z2 , ⋯, z n) 的梯度 , ¨2 f ( z) 为赫森矩阵. L ( y , f w ( x) ) 取最小二乘法 ,则 R (w) =∫( y - f w ( x + a + b) ) 2 d p ( x , y) =∫( y - f w ( x) ) 2 d p ( x , y) + 2831 计 　　算 　　机 　　学 　　报 2007 年 ∫( ( y - f w ( x) )Δg ( x) +Δg ( x) 2 ) d p ( x , y) (15) 由式 ( 15) 可以发现分布式学习即为在风险泛函 ∫( y - f w ( x) ) 2 d p ( x , y) 的基础上增加惩罚项∫( ( y - f w ( x) )Δg ( x) +Δg ( x) 2 ) d p ( x , y) ,这种方法在均衡 神经网络的偏置与方差[34 ] 中普遍采用 ,因此在β控 制在一定小的范围下[35 ]等价于正则化方法. 证毕. 214 　局部学习风险界分析 通过分析上述 Hebb 规则可以发现其特征是首 先通过竞争选出与样本 xi距离在一定范围内的神 经元 W j ,即 d ( xi ,W j ) Φλ,然后按着 Hebb 规则修正 W j的值. 这种学习过程的本质是不同 W j 对其周围 的样本最小化风险 ,所以该学习过程是一种局部学 习[36 ] ,但与文献[37 ]中定义的局部风险最小化模型 不同的是邻域中心为竞争获胜的预测函数 L ( y , f W 3 ( x) ) ,因此本文定义如下最小化风险模型. 定义 1 . 　竞争函数 C( x ,W ,λ) ,对于 AR T 类学 习算法 C( x ,W ,λ) = 1 , d ( x ,W j ) Φλ 0 , 其它 (16) 当 d ( x ,W j ) >λ时谐振发生 ;对于 SOM 类学习算法 C( x ,W ,λ) = exp - d ( x ,W j )λ (17) 在典型 SOM 学习中λ随学习过程逐渐缩小. 定义 2 . 　基于 Hebb 规则的竞争学习算法的 风险泛函 R C ( f W ( x) ,λ) =∫C( x ,W ,λ) L ( y , f W ( x) ) d p ( x , y) (18) 　　定义 3 . 　基于 Hebb 规则的竞争学习算法的 经验风险泛函 RCemp ( f W ( x) ,λ) = 1 n ∑ n i = 1 C( xi ,W ,λ) L ( y , f W ( xi ) ) (19) 　　为了估计经验风险最小化的推广能力和学习过 程的收敛速度 ,按照统计学习理论需估计风险泛函 R C( f W ( x) ,λ) 所能达到的风险值和这一风险值接近 于最小可能风险值的程度. 定理 2 . 包含 r 个有限元素的函数集{ C ( x , W , λ) L ( y , f W ( x) ) }和随机抽取出的 n个观测样本 ,对于 最小化经验风险 R Cemp ( f W ( x) ,λ) 的函数 ( fαW ( x) , λα) 不等式 R C( fαW ( x) ,λα) Φ R Cemp ( fαW ( x) ,λα) + ln 2 r - lnμ2 n (20) 依至少 1 - μ的概率成立. 证明. 　由 Glivenko2Cantelli 定理可知对于任 何给定的概率测度 P 和任何给定的β> 0 ,则 P sup | P( A) - vn ( A) | >β → n→∞ 0 (21) 其中 vn ( A) 为在 n 次独立随机试验中事件 A 出现的 频率. Glivenko2Cantelli 定理说明当试验次数 n 趋 于无穷大时频率收敛于概率. Chernoff 不等式 P{ sup ( P( A) - vn ( A) ) >β} Φ 2exp{ - 2β2 n} (22) P{ sup ( vn ( A) - P( A) ) >β} Φ 2exp{ - 2β2 n} (23) 给出了收敛速率.对于指示函数风险泛函 R C( f W ( x) , λ) 定义了概率 ,经验泛函 R Cemp ( f W ( x) ,λ) 定义了频 率 ,所以根据式 (22) 可以得到 P{ sup 1 Φ j Φ r( RC ( f W j ( x) ,λj ) - RCemp ( f W j ( x) ,λj ) ) >β}Φ ∑rj = 1 P{ ( RC ( f W j ( x) ,λj ) - RCemp ( f W j ( x) ,λj ) ) >β}Φ 2 rexp{ - 2β2 n} (24) 若定义 μ = 2 rexp{ - 2β2 n} (25) 则求出 β = ln2 r - lnμ2 n (26) 由不等式 ( 24) 可得对于函数集 { C ( x , W ,λ) L ( y , f W ( x) ) }中的所有 r 个函数 ,不等式 　　R C( f W j ( x) ,λj ) - R Cemp ( f W j ( x) ,λj ) Φβ (27) 依 1 - μ的概率成立. 因此对于最小化经验风险 R Cemp ( f W ( x) ,λ) 的函数 ( fαW ( x) ,λα) ,不等式 (27) 同 样成立 ,将式 (26) 代入不等式 (27) 得到不等式 (20) 依至少 1 - μ的概率成立. 证毕. 对于最小化风险 R C( f W ( x) ,λ) 的函数 ( fεW ( x) , λε) ,由不等式 (23) 可得 P{ ( R Cemp ( fεW ( x) ,λε) - R C ( f ε W ( x) ,λε) ) >β1 } Φ 　　　　　2exp{ - 2β21 n} (28) 令 2exp - 2β21 n =μ,则 β1 = ln2 - lnμ2 n (29) 由不等式 (28) 可得不等式 R C ( fεW ( x) ,λε) Ε RCemp ( fεW ( x) ,λε) - ln2 - lnμ2 n (30) 38318 期 田大新等 : 基于 Hebb 规则的分布神经网络学习算法 依 1 - μ的概率成立. 因为 ( fαW ( x) ,λα) 最小化经验风 险 R Cemp ( f W ( x) ,λ) ,所以 RCemp ( fεW ( x) ,λε) Ε RCemp ( fαW ( x) ,λα) (31) 由定理 2 和不等式 (30) , (31) 可推出不等式 RC ( fαW ( x) ,λα) - RC ( f ε W ( x) ,λε) Φ 　　 ln2 r - lnμ2 n + ln2 - lnμ 2 n (32) 依至少 1 - 2μ的概率成立. 对于包含无穷多个元素的函数集 { L ( y , f W ( x) ) } , Vap nik 证明了对于随机抽取出的 2 n 个 观测样本和任何给定的β> 0 P sup R ( f W ( x) ) - Remp ( f W ( x) ) R ( f W ( x) ) > β Φ 　　4exp Hann 2 n n - β2 4 n (33) Hann ( n) 为指示函数集在大小为 n 的样本集上的退 火熵 Hann ( n) = ln EN ( ( x1 , y1 ) , ( x2 , y2 ) , ⋯, ( xn , y n) ) (34) N ( ( x1 , y1 ) , ( x2 , y2 ) , ⋯, ( xn , y n ) ) 为函数集 { f W ( x) }分离样本的分法数目 , E 为 N 的期望值. 由于 R C( f W ( x) ,λ) 是由两个函数集 C( x ,W ,λ) 和 L ( y , f W ( x) ) 共同决定的 ,若 C( x ,W ,λ) 的退火熵 为 HCann , L ( y , f W ( x) ) 的退火熵为 HLann , 则 C( x , W , λ) L ( y , f W ( x) ) 的退火熵 HCLann Φ HCann + HLann . 定理 3 . 　包含无穷多个元素的函数集{ C ( x , W ,λ) L ( y , f W ( x) ) } 和随机抽取出的 2 n 个观测样 本 ,对于最小化经验风险 R Cemp ( f W ( x) ,λ) 的函数 ( fαW ( x) ,λα) 不等式 RC fαW ( x) ,λα Φ RCemp fαW ( x) ,λα + 2 Hμ n + 　　2 Hμ n RCemp fαW ( x) ,λα + Hμ n (35) 依至少 1 - μ的概率成立 , 其中 Hμ = HCann 2 n + HLann 2 n + ln4 - lnμ. 证明. 　由不等式 (33) 可得 P sup RC f W ( x) ,λ - RCemp f W ( x) ,λ R C f W ( x) ,λ > β 　 Φ 4exp HCLann 2 n n - β2 4 n 　 Φ 4exp HCann 2 n + HLann 2 n n - β2 4 n (36) 令 4exp H C ann 2 n + HLann 2 n n - β2 4 n =μ,则 β2 = 4 n HCann 2 n + HLann 2 n + ln4 - lnμ = 4 Hμ n (37) 由不等式 (36) 可推出对于函数集中的所有函数 ,不 等式 RC f W ( x) ,λ - RCemp f W ( x) ,λ R C f W ( x) ,λ Φβ (38) 依至少 1 - μ的概率成立 ,由不等式 (38) 可得 RC f W ( x) ,λ 2 - 2 RCemp f W ( x) ,λ +β2 · 　RC f W ( x) ,λ + RCemp f W ( x) ,λ 2 Φ 0 (39) 要使不等式 (39) 成立 , R C( f W ( x) ,λ) 应同时满足如 下条件 : RC f W ( x) ,λ Εβ2 - β 4 RCemp f W ( x) ,λ +β2 2 + RCemp f W ( x) ,λ (40) RC f W ( x) ,λ Φβ2 +β 4 RCemp f W ( x) ,λ +β2 2 + RCemp f W ( x) ,λ (41) 由于不等式 (41) 对函数集{ C( x ,W ,λ) L ( y , f W ( x) ) } 中的所有函数都成立 , 所以对于最小化经验风险 R Cemp f W ( x) ,λ 的函数 fαW ( x) ,λα 不等式 RC fαW ( x) ,λα Φ RCemp fαW ( x) ,λα +β22 + 　　 12 4 RCemp f α W ( x) ,λα +β2 β2 (42) 依至少 1 - μ的概率成立 ,将式 (37) 代入不等式 (42) 定理得证. 证毕. 由于不等式 ( 41) 对函数集 { C ( x , W ,λ) L ( y , f W ( x) ) }中的所有函数都成立 ,所以对于最小化风 险 R C( f W ( x) ,λ) 的函数 ( fεW ( x) ,λε) 不等式 RC ( fεW ( x) ,λε) Ε RCemp ( fεW ( x) ,λε) +β22 - 　　 12 4 RCemp f ε W ( x) ,λε +β2 β2 (43) 依至少 1 - μ的概率成立. 由定理 3 ,不等式 ( 31) , (43) 可推出 RC fαW ( x) ,λα - RC f ε W ( x) ,λε Φ 　 12 4 RCemp f α W ( x) ,λα +β2 β2 + 　 12 4 RCemp f ε W ( x) ,λε +β2 β2 (44) 依至少 1 - 2μ的概率成立. 由定理 2 ,3 可知实际风险由经验风险和置信区 间两部分组成. 通常学习方法是首先通过选择模型 来固定置信区间 ,然后通过最小化经验风险泛函来 4831 计 　　算 　　机 　　学 　　报 2007 年 求最小风险 ,因为缺乏对置信区间的认识 ,这种选择 往往是依赖于先验知识和经验进行的. 为此 , Vap2 nik 提出结构风险最小化原则 ,即选择最小经验风 险与置信区间之和最小的子集 ,这个子集中使经验 风险最小的函数为所求的最优函数. 在分布式学习 中为了防止被分割的知识丢失 ,在分布学习阶段没 有采用结构风险最小化原则 ,而在集中学习阶段采 用后修剪算法实现结构风险最小化. 215 　学习算法 学习算法的主体学习过程可描述如下. 初始化学习速度系数μ,相似度门限值 ; ; 1 . 接收第一个样本向量 x ,添加第一个神经元 w0 并置 初始值为 x; 2 . 判断学习是否结束 :若否 ,则从样本空间中接收一个 样本向量 ,并计算相似度值 di ; 3 . 由竞争函数判断获胜神经元 j ,若 d j > ; ,则添加新 的神经元并使其突触权值为 x ,返回步 2 ,否则继续 ; 4 . 按式 (6) 更新突触权值 , 返回步 2. 由于完整数据集是被随机地分割成不相交的子 集 ,因此描述某些知识点的样本可能被分割到不同 的子集 ,为了避免因这类知识点被忽略而降低准确 率 ,在分布学习阶段各个子神经网络采用不断增长 的学习方式 ,即当一个样本与当前知识点具有较低 的相似度时该样本将成为一个新的知识点并被增加 到权重矩阵 ,并且该阶段相似度门限值 ; 较大. 在分 布学习结束后 ,各个分割数据的学习结果中包含了 一些较完整的知识点和一些没有完全学习到并被分 割表示的知识点. 因此 ,需要通过集中学习对这些中 间结果构成的样本空间进行再学习从而形成完整的 知识. 上述过程在解决了样本被分割后一些知识点 可能被丢弃的问题的同时也降低了学习结果的泛化 能力 ,因为样本数据中一些特征有可能被重复表示 从而导致过学习. 因此采用后修剪算法来实现结构 风险最小化原则. 后修剪算法以训练后的每一个神 经元为修剪的候选对象 ,将相似的神经元合并为一 个神经元或多个 (总数比合并前少) 神经元. 修剪后 新神经元的计算公式为 　　Wnew = Wold1 ×t1 + Wold2 ×t2 / t1 + t2 (45) 其中 , t1为神经元 Wold1的学习次数 , t2为神经元 Wold2 的学习次数. 某个神经元学习的次数越多 ,其信息在 新神经元中占的比例越大. 3 　实　验 实验测试首先采用 Circle2in2t he2square 基准测 试数据集测试了算法的学习能力 ,然后采用 UCI 中 的数据集 U SCensus1990Data 测试了其对大规模数 据的学习性能. 311 　Circle2in2the2square Circle2in2t he2square 是美国国防部高级研究计 划署 (DARPA)人工神经网络技术 (ANN T) 计划采 用的基准测试问题. 该问题要求神经网络能准确分 辨出一单位正方形的点中位于一圆内和圆外的点 , 该圆位于正方形中且面积为单位正方形的一半. 文 献[38 ]用 22n21BP 神经网络对该基准测试进行了 分析. 实验分别测试了当隐层神经元数 n 从 5 增加 到 100 ,权向量个数从 21 增加到 401 ,训练集从 150 增加到 14000 时的学习能力 ,最后得出当隐层神经 元个数为 20～40 个时 ,经过 5000 个周期的训练 ,神 经网络辨别的准确率在 90 %左右. Fuzzy AR T2 MA P[28 ]的测试结果表明当 A R Ta的神经元数从 12 增加到 121 ,训练集从 100 增加到 100000 时其错误 率从 1114 %降低到 210 %. 测试使用文献 [28 ]的基 准测试数据 , 该数据集可从 CEL EST Technology Website ( ht tp :/ / p rof usion. bu. edu/ techlab/ mod2 ules)下载. 数据集 cis_t rain2. t xt 中包含 1000 个样 本数据 ,为了测试分布式学习算法的学习能力 ,将数 据集按图 2 进行分割 ,其中 A1 , A2 组成 A 块数据 集 , B1 , B2 组成 B 块数据集. 将上述 A , B , C 块数据 分别分发给三个神经网络按分布式学习算法进行学 习 ,分布学习的结果见图 3～5 ,最终的学习结果见 图 6 . 图 2 　分割数据的分布情况 采用 SVM 对上述样本进行训练 ,核函数采用 ‘rbf’,交叉验证采用‘HoldOut’时的训练和识别结 果见图 7 和图 8 ,其准确率在 94143 %～97133 %之 间. 当相似度门限值 0105 增加到 0108 时 ,神经网络 的训练次数 ,神经元数和准确率与其他方法的比较 列在表 1 中. 对于分布式学习 ,其训练次数为分布学 习中训练次数最多的神经网络的训练次数加上集中 58318 期 田大新等 : 基于 Hebb 规则的分布神经网络学习算法 学习的训练次数. 在训练的一个周期中 ,若谐振发 生 ,某个样本可能被多次学习 ,所以分布式学习的训 练次数等价于其它方法的训练周期乘以样本数 ,从 学习结果可以看出分布学习并没有丢弃被分割的知 识 ,学习结果能较好地分辨出点所在的区域. 表 1 　Circle2in2the2square 测试结果 训练次数 正确率/ % 神经元数 分布神经网络 518～621 96～98 91～196 AR TMAP (1 ×100) ～ (1 ×100000) 881 6～98 12～121 BP (5000 ×150) ～ (5000 ×14000) 90 21～401 312 　USCensus1990Data 上面实验结果表明 ,即使样本中的知识点包含 在分割的子样本集中 ,分布神经网络算法也能有效 地学习到并与单个神经网络学习具有等价的性能. 对于大数据集的测试 ,本文采用了 UCI 中的 U S2 Census1990Data ,这个 352Megabytes 数据集包含 了由 68 个属性组成的 2458285 条记录. 实验中将数 据集按记录顺序分割成 12 个不相交子集 ,前 11 个 子集每个包含 200000 条记录 ,最后一个子集包含最 后的 258285 条记录. 实验测试了在分布学习下各个 子神经网络的神经元个数和集中学习后神经元个数 6831 计 　　算 　　机 　　学 　　报 2007 年 及总共消耗的时间 ,并将其与采用一个神经网络对 全部样本进行学习的结果进行了比较. 实验中分布学习时的门限值为 15 ,集中学习时 的门限值为 10 ,单个神经网络学习的门限值为 18 . 学习后的神经元个数和消耗时间情况见表 2 . 其中 分布学习阶段前 11 个子神经网络消耗时间在 12 分 钟左右 ,第 12 个子神经网络耗时较多是因为其训练 样本比其它子集多了 58285 条. 由上述结果可知分 布神经网络消耗的总时间为 1618 + 015 = 1713min , 而单个神经网络消耗的时间是其 6 倍多. 表 2 　USCensus1990Data 测试结果 消耗时间 / min 神经元数 / 个 消耗时间 / min 神经元数 / 个 分布 1 121 3 217 分布 8 1314 242 分布 2 121 2 221 分布 9 1118 210 分布 3 121 3 212 分布 10 1119 213 分布 4 121 4 215 分布 11 1217 229 分布 5 121 8 231 分布 12 1618 232 分布 6 111 9 208 集中 01 5 125 分布 7 121 1 215 单个 1051 1 147 4 　结　论 为了对大规模数据进行归纳学习 , KDD 研究人 员提出了对数据进行采样学习 ,将数据分割后分布\ 并行学习等 Scaling up 学习方法. Scaling up 学习在 面临着学习算法过学习难题的同时更面临着因数据 量巨大导致的欠学习难题. 数据分割后对数据进行 分布\ 并行处理面临的主要问题是如何将各个子数 据集的学习结果进行合并 ,从而使分散的知识组合 成最终的知识模型. 本文提出了基于 Hebb 规则的 分布神经网络学习方法 , Hebb 规则的局部学习特 征使被分割到各个子集的部分知识能够在分布学习 阶段得到保留并在集中学习阶段被提取出来. 对 Circle2in2t he2square 的实验证明了该分布神经网络 的准确性与单个神经网络相当. 通过 U SCen2 sus1990Data 实验表明该学习方法通过分布学习不 仅解决了大规模数据样本学习时的空间约束问题 , 如即使在 1 GB 的内存容量下 Matlab 都无法装载完 全部的 U SCensus1990Data 样本数据 ,而且分布处 理大大提高了系统的整体学习速度. 参 考 文 献 [1 ] Wei C P , Lee Y H , Hsu C M. Empirical comparison of fast partitioning2based clustering algorit hms for large data set s. Expert Systems wit h Applications , 2003 , 24 (4) : 3512363 [ 2 ] Peter W , Chiochet ti J , Giardina C. New unsupervised cluste2 ring algorit hm for large dataset s/ / Proceedings of t he 9t h ACM SIGKDD International Conference on Knowledge Dis2 covery and Data Mining. Washington D. C. , 2003 : 6432648 [ 3 ] Gursoy A. Data decomposition for parallel k2means cluste2 ring/ / Proceedings of t he 5t h International Conference on Parallel Processing and Applied Mat hematics. Czestochowa , Poland , 2003 : 2412248 [ 4 ] Ceglar A , Roddick J F. Association mining. ACM Compu2 ting Surveys , 2006 , 38 (2) : 1242 [ 5 ] Part hasarat hy S , Zaki M J , Ogihara M , Li W. Parallel data mining for association rules on shared2memory systems. Knowledge and Information Systems , 2001 , 3 (1) : 1229 [ 6 ] Jia C Y , Gao X P. Multi2scaling sampling : An adaptive sam2 pling met hod for discovering approximate association rules. Journal of Computer Science and Technology , 2005 , 20 (3) : 3092318 [ 7 ] Tuv E , Borisov A , Torkkola K. Best subset feat ure selection for massive mixed2t ype problems/ / Proceedings of t he 7t h In2 ternational Conference on Intelligent Data Engineering and Automated Learning. Burgos , Spain , 2006 : 104821056 [ 8 ] Tang W Y , Mao K Z. Feature selection algorit hm for data wit h bot h nominal and continuous features/ / Proceedings of t he 9t h Pacific2Asia Conference on Knowledge Discovery and Data Mining. Hanoi , Vietnam , 2005 : 6832688 [ 9 ] John G , Langley P. Static versus dynamic sampling for data mining/ / Proceedings of t he 2nd International Conference on Knowledge Discovery and Data Mining. Portland , Oregon , 1996 : 3672370 [ 10 ] Provost F , J ensen D , Oates T. Efficient progressive sam2 pling/ / Proceedings of t he 5t h ACM SIGKDD International Conference on Know