一种基于FPGA的新的SVM硬件实现方法 .pdf

第 3 1 卷第 10 期 2010 年 1O 月 仪 器 仪 表 学 报 C hi n ese Jou rnal of S c i enti fi c Instrum ent V o1 3 1 N o 1O O c t 20 10 一 种 基 于 FPG A 的新 的 SV M硬 件 实现 方 法 刘 涵 王博 尹 嵩 刘 丁 西安理工大学 自动化 与信息工程学院西安7 10048 摘要 提 出了一种基于递归神经 网络 的实现最小二乘支持 向量机 的 FPG A 串行计算方法 与 已有 的并行计算 方法相 比 该方 法利用 r 递归神经网络的并行性及最小二乘支持 向量机简 化的约束条件的优点 在保证计算 速度 的同时 明显 提高 了 FPG A 的 硬件资源利用效率 能够适应大规模训练样本的情况 实验结果表明 由于该方法具有灵活的串行计算 并行传输的特点 在较 少使用 FPG A 硬件资源的 同时 计算速 度不会 有明显变化 可有效地用 硬件实现支持向量机 关键词 串行计算方法 最小二乘支持 向量机 递 归神 经网络 中图分类号 TN 911 7 文献标识码 A 国家标准学科分类代码 520 2040 N ew seri a l i m p l em en ta ti o n m eth o d fo r su p p o rt v ec to r m a c h i n es u si n g F P G A L i u H a n W a n g B o Y i n S on g L i u D i n g Sc hool of Autom atio n and Inform ati on E ngi neeri ng Xi an Uni versi ty of Tec hnol ogy X i an 710048 Chi na A b strac t A new F P G A seri al c om putati onal m ethod for i m pl em enti ng l east sq uares support vec tor m ac hi n es based on rec urrent neural n etw ork i s p resented i n thi s paper C om pared w i th exi sti ng paral l el c om putati onal m ethod the new m eth od c om bi nes the paral l el c h arac ter of rec urrent neu ral netw ork w i th si m p l i c i ty of l east squares support vec tor m ac h i ne c an get a good perf orm anc e w i th l ess hardw are resourc es w hi l e m ai ntai ni ng th e c om putati onal speed and al so c an adapt to l arge sc al e trai ni ng sam p l es E xperi m ent resul ts show that du e to the flexi bl e seri al c om putati onal and paral l el transm i ssi on c harac teri sti c s the c onsu m pti on of F P G A spac e c oul d be reduc ed effec ti vel y w hi l e th e c on puti ng speed w i l l not drop obvi ousl y In c onc l u si on the fu nc ti on of supp ort vec tor m ac hi nes c oul d be i m pl em ented on FP G A pl atform usi ng th e proposed m ethod effec ti vel y K ey w ords seri al c om p utati onal m eth od L S SV M rec u rrent neu ral netw ork 1 引 言 支持 向量机 support vec tor m ac hi nes SVM 作 为 20 世纪 80 年代初 由 Vapni k 提 出的统计学 习理论 的主要 内 容 由于其 良好的推广 能力 以及在模式识别领域 成功 的应用 越来越被人们所接受 已成为机器学 习研究的 热点领域 对 SVM 的求解需要求解二次凸优化 问题 其计算 复 杂度会随着样本集合 的增大迅速增加 在许 多工程应用 收稿 日期 20 10 04 R ec ei ved D ate 20 10 04 基金项 目 陕西省教 育厅专项基金 09JK632 资助项 目 领域 往往需要用 SV M 对数据 进行实时处理 因此 实现 SVM 的并行和分布式计算显得十分必要 文献 3 将 支 持向量机的训练问题转化 为递归 神经网络的计 算问题 在此基础上文献 4 12 分别完成 了基 于硬件 电路 的支 持向量 机和 最小 二乘 支持 向量机 1east squares support vec tor m ac hi nes LS SV M 的并行计算结 构 随着 FPGA fi el d program mabl e gate array 技术 的发展 FPGA 的并行 性和快速重构的特点也 被应用 于实现神经网络结构 FP GA 已逐渐 成为实现人工神经 网络 的一种有效方 式 j 在 FPGA 中采用 VHDL 语言来描述神经网络结构 具有较 学兔兔 w w w x u e t u t u c o m 2236 仪器仪表学报 第 3 1 卷 强的灵活性 并且可以较好地保留神经网络的并行性 既 保证了处理速度 又适合于实现大规模复杂的网络结构 本文提出 了基于递 归神经 网络 的 LS SVM 的 FPGA 串行计算方法 相 比已有的并行实现方法 该方法具有 灵活的串行计算 并行传输的特点 可 以在大幅减 少 FP GA 使用资源 的同时 保证计算速度 可有效地硬件实现 L S S V M 2基于递归神经 网络的 L S SV M计算方法 在 SVM 求解过程 中的凸优化问题需要通过二 次规 划方法来解决 而求解二次规划问题需要计算核函数矩 阵 其计算量与训练样本数的立方成正 比 当处理大规 模数据时 计算量比较大 内存占用量较多 LS SVM 可 以在一定程度上 解决 SVM 的计算 复杂 性 的问题 它将 SV M 优化 问题 的不 等式 约束变 为等式 约束 训练 Ls SVM 仅仅需要求 解一个线性方程组 因此 一 SVM 具有 更简单的结构 更易于实现 在使用 FPGA 实现时 能 更有效地利用片内资源 对于 LS SVM 的分类问题 设给定分类训练集 x Y i l 2 其中x R N为训练样本 而 Y 一1 1 为样本相对应的类别 其分类决策面可以表示为 X W b 式 中 w 为权值矩阵 b为偏移量 表示从输入空间 到特征空问的非线性 映射 LS SVM 分类学 习即为求解 下面的受约束 的最优化问题 1 m i n J w e 寺 w 1 e s t Y W b 1 一e i 1 2 式 中 e为误差 常数 0 它控制对超 误差的样本的 惩罚的程度 具有分类功能的 LS SVM 的神经网络结构 如图 l所示 q lt I y I q N1 q NN Y l v J 6 图 1 实现最小 二乘支持 向量机功能的递归神经网络结构 图 Fi g 1 Sc hem e of the p rop osed rec urrent n eu rM netw ork f0r LS SV M c l assi fic ati on l earn i ng 该网络 的连续动态方程如下 OJ Y 1 一 1 一by 一 0 q y 2 d 式 中 为Lagrange乘 子 q Yi Yj 定义为核 函数 可以看出 与 SVM 的计算 结构相比较 该 LS SVM 结构没有非线性单元 由于 FPGA 不能直接 实现一个连续 的微分方程 所 以必须对 式 1 2 进行离散化处理 6 AT f 6 f 3 O i t AT aT 1 6 t y 一 一 Ot t t 4 式 中 A T 为采样周期 图 1所示递归神经网络的渐进稳 定性的证明详见文献 4 11 3 SV M的 FP G A 硬件实现方法 3 1 串行计算结构的实现方法 在实现带 约束 的二次 优化 问题 3 4 时 文献 15 提出了 FPGA 环境下 的并行计算结构与实现方法 其核心计算部分如图 2 所示 图 3 为图2 中的 neuro单元 结构 其中 Q q 图 2 并行计算结构 图 Fi g 2 The p ral l el c om puti ng struc ture c hart for SV M l earni ng 图 3 并行计算结 构各个神经元 内部结构 F i g 3 T he i ntern al struc ture of neurons 学兔兔 w w w x u e t u t u c o m 第 10 期 刘涵 等 一种基于 FPG A 的新的 SV M 硬 件实现方法 2237 此算法的思想是并行计算 m 个 oL 同时依据 o 值计 算 b 值 这时计算 中所 占用 的硬件资源与样本数 m 有着 直接的关系 当样本数增加时 该结构所实现的 LS SVM 将大量消耗 FPG A 的资源 并且使结构 的复杂程度增加 假设需要的样本数为 m 个 对 每个样本进行 训练需 要 占 用的 FPGA 资源为 Ji2 那么 m 个样本总共 要占用 FPGA 里 m x 的资源 这样很容易造成资源利用超 实际资 源总量 的问题 将大大限制其在实际巾的应用 因此 本文对图 1 结构进行优化和改变 使其以 串行 结构的方式计 算 如图 4 所示 该 串行结构避免 了实际 电路与样本数 的直接关联 可以在不改变实 际电路 的情 况下完成实际样本数未定 的训练工作 其核心算法 结构 如 图5 所示 由图 5 可看 出 每次先循环计算 n 个 13 值 后再计算 b 值 避免 了原来 建立多个单元训 练 OL值 造成 的硬件资源浪费 因为本次计算的 值只与上个周 期计 算 的 n 个 Og值有关 当然 需 要根据 FPGA 的资源 来设 定一个最大的训练样本数 只要训练样本数不 超过这个 设定的范围 通过 串行的计算方法 反复利 用同一单元 使得 FPGA 硬件资源的使用减少 图4实现最小二乘支持向量机功能的串行计算结构图 F i g 4 S erial c om putati on al stru c ture sc h em e for LS SV M c l assi fic ati on l earni ng 图 5 串行计算 结构流程图 F i g 5 Seri al c om p utati on flow c h art 图 4 的串行计算结构 和并行计算 结构相 比 学 习速 率会有所 降低 因此需要 将数据 的传输与 计算分 开设 计 将计算与传输流水化 在计算的同时将上一 步的计算 结果传递给其它模块 这 时在 总体上 采用串行计算 结构 的速度并不会受 明显影响 3 2 串行计算结构 的 FPG A 实现 3 2 1 总体框图 图 6 为 LS SVM 的 FPGA 实现串行计算框图 整个框 图的结构可以分为 3 个基础 的功能单元 图 6 LS SV M 的 FPG A 实现 串行计算框图 F i g 6 Seri al c om p utati onal stru c tu re fo r L S S V M based on F PG A 1 Load 单元 在整个 LS SV M 开始学习时 Start端 口 的信号变成高电平 首先通过 datai n 端 口输入矩阵 Q 和 样本 目标 值 Y LS SVM 将它们保存在 2 个 ROM 中 实 际上 为了操作方便并具有针对性 直接把矩阵 Q 保存在 一 个 R OM 中 方便 随时读 取 这 里矩阵 Q 的数 据必须 严格按行或按列寄存在 ROM 里 2 Leam单元 在 Load 单 元执行 完毕后 开始 执行 Learn 单元 Learn 单元是整个 I S SV M 的核心部分 完成 计算 Ot和 b 具体细节在下节 中将给予介绍 在学习训练 完毕后 ready 端口变为高电平 进入下一个 Output单元 3 Output单元 在 Lssvm a 和 bi as模块训练完毕后 将训练好 的 b 一 Ot 输出 以上 3 个 基 本功 能 单元 主要 由图 6 中 的 Control C ou nter L ssvm a 和 Bi a s 模块 4 个模块组成 其 中 Lssvm a 完成 的计算 Bi as 完成 b 值的计算 所有 控制信号 由 Contm l 模块通过 Contm l b118来传递给其他模块 时钟信号 通过 Counter bus 来传递 模块 间数据 由 Data bus 传 递 A ddress b US 主要负责读取所有 RO M 及 RA M 的数据 3 2 2 模块介绍 1 Lssvm a 模块 该模块执行图5 中算法的 Ot部分 其硬件结构如图7 所示 首先矩阵 Q 保存在 ROM 中 M AC 为乘累加单元 学兔兔 w w w x u e t u t u c o m 2238 仪器仪表学报 第 3 1 卷 用来计算 aj t q 其巾权值要与0 相对应 3 个 乘法器 M ul 分别计算 by t 和最后的 与 l一 b t r 一 g y Ol 的乘积 ADD 为另一个累 加单元 由于对式 3 进行离散化处理后 最后的积分单 元变为了一个累加单元 因此 A DD 用来 将本次得 l叶 J的 值及上一组得到的 值进行 累加 并将更新 的值存 入 RA M 单元中 由于计算 和 比较过程需要用到上一步 的向量 所 以利用 RA M 和 R AM 1 来保存本次计算 的 一 组 值和上次计算 的一组 值 为了方便 比较和 累加运算 根据计算每个 值 的周期 将上一组的 值 临时保存在 A i n 中 南于计算采用的是定点运算 冈此 shi ft单元用来将数据 限制在指定的范周内 本文 限制的 范围为 一15 15 在计算完第 n 1 步 值后 下来计 算第 n 1 步 直到计算完 个 值 k 为训练样本 数 这就完成了串行计算方式 图 7 l ssvm a 模块结构图 F i g 7 T he l ssvm a m od ul e 2 Bi as模块 Bi as模块用来计算 b 值 并根据 Control 模块的信号 将 更新的b 值送入下一循环阶段的 Lssvm a 模块中参与计算 3 Control 模块 Control 模块是整个 LS SVM 的控制模块 它将控制 各个模块并产生各模块所需 的信号 其控制信号并行传 输给各个模块 图 8 为 Control l er的内部状态机 图 8 c ontrol 模块状态机 Fi g 8 FS M of th e c on trol m od ul e 整个学习过程中 需要输入运算 矩阵 Q 以及样本 目 标值 随后进入正式的训练学习过程 先使用初始的 值 和 b 值 其分别存放于 Ram 和 Bi as 中 之后通过 Lssvm a 对 值进行循环计算训练 以计算完 n 个 t3t 值为一个周 期 在每个周期结束时计算 b 值 之后对上次循环的 值 和本次所得 值进行比较 当 2 个周期 的所有 值 的误 差小于允许的范同时 得 所要的 值和 b 值 4 C ounter 模块 Counter模块是整个运算的计数模块并产 生时序 其 中的行列计数器分别产 生读取行列 的时序序列 并通过 Control 模块对 RO M 及 RAM 进行读取 数据 Control 模 块也将根据 Counter模块产生 的选择信号进行各个功能 单元之问的切换及工作 4 实验结果及分析 根据上述提 出的串行计算 的 LS SVM 结构 本文通 过 2 个实验来测试其性能 并与文献 15 的并行计算结 构进行比较 实验所 用到 的计算机 配置为 Penti um R 4 CPU 3 20 GH z 3 20 GH z 1 Gb 内存 硬件平 台为 XILINX 的 Vi rtexl I Pro 系列 FPG A 软件平 台是 ISE 编 译环境及 VH DL 硬件编程语言 实验 1 在 R 空 间上 有 7 个 线性 可分的样 本点 z 3 1 z 3 2 3 3 5 1 z 5 2 5 3 z 5 1 5 相对应的类别 为 1 1 1 一1 一1 一1 一1 从直观上看 显 然最优超平面应该为 4 本例 中选择 y 0 5 核 函数选择高斯函数 其中 O 1 图 9 为参数 的 FPGA 串行结构实现结果 ram i ni ti a l 0 rai n i n i ti al 6 分别代表参数 0 6 从图中可以 学兔兔 w w w x u e t u t u c o m 第 10 期 刘涵 等 一种基于 FPG A 的新的SV M 硬件实现方法 2239 看 出参数 的收 敛 时间为 3 182 10 s 图 10 为 由 FPGA 串行结构得到参数 of b 绘制的分类超平 面 图 11 为参数 在应用 并行结 构时的结果 aft i nO al f i n6 分 别代表参数 O 从 图中可 以看出参数 的收敛 时间 为 2 346 10 一S 网 12 为由 FPG A 并行结 构得到参数 b 绘制的分类超平面 从 图 10 和图 l 2 的结果 比较可 以看出 串行结构 的 LS SVM 计算 方法 同样可 以很 好 的 解决实验 1 的分类问题 从参数 O 的收敛时间看 计算速 度没有收到明显的影 响 因此这种方法对解 决线性可分 分类问题是可行的 怒 I嚣 i 318 200 3184O0 318 6oo 3l g 800 319 oq0 9l 1 r 葛礴赫耩 蔼礴 鞭瞬嚣囊罐鞴耩鞲嘴裱鞴搿秽鞲鞴簿鞴 糍戮 禚鞲挥 一 i I i P 喇 b 嘲 嚣嚣嚣 豁 嗍 一 j 茔 鬻端镄 a 瓣 n 孽 惭 嚣嚣鬻 嗍 咿 i 蕊I 寸 蕊糍臻 帅 蝴 i 嗣 h 啊 蝴 黼 霸嚣嚣 瓣 嗍嘲 蝴獬 确 3 紫 嘲 端高麓秽 棚 喇 一 酥 一 中 嘣 掰镤臻 嘲 图 9 实验 1 FPG A 串行计 算结构计算结果 Fi g 9 T h e c ompu tati on resu l t of serial stru c ture wi th F P GA i n exp erim en t 1 l l Z I 图 10 实验 1 的串行计算 结构的分类情况 Fi g 10 Dec i si on su rfac e for serial struc tu re 图 11实验 1 FPG A 并行计算结构计算结果 F i g 1 1 T he c om pu tati on resu l t of p aral l el stru c tu re w i th F PG A i n ex perim en t 1 实验 2选取 20 个线性不可分的样本点 y l 4 7 4 5 4 9 4 0 4 6 3 3 3 9 3 5 4 2 5 1 4 5 6 3 5 8 5 3 5 5 6 7 6 9 4 9 4 8 6 4 1 6 5 1 6 1 3 1 8 1 O 1 4 1 O 1 5 1 8 1 7 1 8 1 8 1 9 2 1 2 2 2 3 2 0 1 8 2 0 相对应 的类 另 0为 一 1 一 1 一 1 一 1 一 1 一 1 一 l 一 1 一 1 一 1 1 1 1 1 1 1 1 1 1 1 该样本点全部来 自植物数据集 i ri s data set 中的不可分两类样本 0 629 364 013 671 88exp 一 Z1 3 z2 1 2 20 5 一 0 020 904 541 015 63 0 2 5 2 1 5 1 0 5 0 1 一 一 一 一 一 一 j 图 12实验 1 的并行计算结构 的分类情况 F i g 1 2 Dec i si on surfac e for paral l el stru c tu re 图 l 3 为参数 的串行计算结果 参数 的收敛时间 为 1 294 8 10 S 图 l 4 为参数 b 绘制 的分类超平 面 从图中可以看 出两线性不可分类点 已经被决策超平 面分开 图 15 为参数 of 的并行计算结果 参数 的收敛 时间为 2 366 10 S 图 16 为相应 的参数 b绘制的分 类超平面 从图 l 4 和图 16 的结果 比较可 以看 出 对 于 线性不可分问题 串行结 构的计算方法也 同样可 以实现 LS SVM 的分类功能 从参数 的收敛时间看 计算速度 没有受到明显的影 响 因此 对于解决线性不可分分类 问 题也是可行的 图 13 实验 2 FPGA 串行 计算 结构计算 结果 F i g 13 T h e c om pu tati on resu l t of serial struc ture w i th F PG A i n experi m ent 2 学兔兔 w w w x u e t u t u c o m 仪器仪表学报 第 3 1 卷 图 14 实验 2 的串行计算结构分类情况 F i g 14 D ec i si on surfac e for serial struc ture i n exp eri ment 2 图 15实验 2 FPG A 并行计算结构计算结果 F i g 15 T he c omp utati on resul t of paral l el struc ture w i th F P GA i n exp erim ent 2 0 092exp 一 4 7 Cv 1 6 2 ff 138 73 0 图 16 实验 2 的并行结构计算分类情况 F i g 16 Dec i si on surfac e for paral l el struc ture i n experi m ent 2 由表 1 可以看出 在实验 1 中 7 个训练样本时 串行 计算结构的资源占用率很低 25 而并行计算结构的 资源利用 已经超 出了资源使用范围 103 W TBZ 实 验 2 中使用了 20 个训练样本 虽然样本数增加 了很多 但由于串行计算结构的优势 其资源 占用仍维持在较低 水平 37 而对 于并行结构 其 资源已远远超 出了硬 件适用范围 达到了284 W T BZ 虽然 串行结构在时问 上要比并行结构稍慢 但其有效的提高了硬件资源利用 效率 表 1 两个实验的收敛时间及资源 占用率 T ab l e 1 C on vergen c e ti m e an d resou rc e al l oc atio n ra ti o i n two exp eri m en ts 5 结 论 本文在已有 SV M 并行计算实现方法的基础上 提出 了一种新的 LS SVM 硬件实现的串行计算结构 该结构 在样本数量增加的情况下 仍然有较高 的硬件资源利用 效率和计算速度 实验结果表 明 基于 串行计算结构 的 支持向量机实现方法 能够准确地分类线性可分 线性不 可分数据 而且能够 比已有的并 行计算 结构节省更多 的 硬件资源 证明了所提 出的方法是有效 的 为 SV M 在实 际应用中的硬件实现提供了新的思路 参考文献 1 V A PN IK V Stati sti c al l earni ng theory M New York Wi l ey P ress 199 8 2 CR ISTIA NIN I N SH A V E TA Y LO R J A n i ntroduc ti on to suppo vec tor m ac hi nes M C am bri dge Cam bri dge Uni versi ty Press 2000 3 PE RFET H R RICC I E A nal og neural network for sup port vec tor m ac hi ne l earn i ng J IEEE Transac ti ons on Neural N etw ork 2006 17 4 1085 1091 4 LIU H LIU D A neural network approac h for l east squares support vec tor m ac hi nes l earni ng C 48th IEEE Confe enc e on Deci si on and C ontrol Shanghai C hi na 2OO9 7297 7302 5 CO X C E B LA N Z E c A NG L10 N A fast fi el d pro gram m abl e gate array i m p l em entati on of a c onnec ti oni st c l assi fi er J IE EE Journal of Sol i d State Ci rc ui ts 1992 28 3 288 299 学兔兔 w w w x u e t u t u c o m 第 1O 期 刘涵 等 一 种基 于 FPGA 的新的 SV M 硬件实现方法 224 1 6 7 8 9 1O 11 12 BE R T H E 1 OT F NOUVE L F H0U Z ED D P arti al an d dyn ami c rec onfigurati on of F P GA s A top down desi gn m ethodol ogy for an autom ati c i m pl em entati on C IE EE C om puter S oc i ety A n nu al sym posi um on em ergi n g V I SI T ec hnol ogi es and A rc hi tec tu re s Kad sru he G erm an y 2 00 6 4 36 4 37 李海森 陈宝伟 么彬 等 多子阵高分辨海底地形探 测算法及其 FPG A 和 D SP 阵列 实现 J 仪器 仪表学 报 2010 31 2 281 286 IJI H S C ttE N B W YAO B et a1 Im pl em entati on of h i gh resol uti on sea bottom terrai n detec ti on meth od b ased on FPGA and D SP array J Chi nese Journal of Sc i enti G i c Instrum ent 20 10 31 2 281 286 A N G U IT A D B O N I A R ID E L L A S A di gi tal arc hi tec tu re for sup port vec tor m ac h i nes T heory al gori thm a d FPG A i m pl em entati on J 1 IE EE Transac ti ons on N eural N etworks 2003 14 5 993 1009 M A T H 1A S M C H E R IE T M M od el sel ec ti on for th e I5 一 SV M appl i c ati on to handwri ti ng rec ogni ti on J Pattern Rec ogni ti on 2009 42 12 3264 3270 S U Y K E N S J A K V A N D E W A L L E J R ec urr en t l east squares support vec tor m ac hi nes J IE EE Transac ti ons on Ci rc ui ts and System s 2000 47 7 1109 1114 刘涵 叶平 基于递归 神经 网络 的 LS SV M 硬件 实现 与实验 研 究 J 仪 器 仪 表 学 报 2009 30 8 1745 175 L IU H Y E P H ard w are i m p l em entati on an d experi m ent researc h of l east sq uare sup port vec to r m ac h i ne base d on rec urrent neural network J Chi nese Journal of Sc i enti f i c Instrum