半监督学习算法的收敛性及其在人脸识别中的应用.pdf

第 3 1卷第 1 期 2 0 1 1年 1月 河北大 学学报 自然科 学版 J o u r n a l o f He b e i Un i v e r s i t y Na t u r a l S c i e n c e Ed i t i o n Vo 1 31 N0 1 J a n 2 0 1 1 半监督学 习算法 的收敛性及其在人脸识别 中的应用 李 凯 马红艳 1 河北大学 数学与计算机学 院 河北 保定O 7 杨楠 陈新 勇 1 0 0 2 2 河北大学 工商学 院 河北 保定0 7 1 0 0 2 摘 要 研 究 了半监督 学 习的一致性 学 习算法及 其 变形 通过 引入 圆盘 定理 证 明 了一 致性 学 习算法 收 敛 的条件 针 对 变形学 习算法 给 出了使 用 变形矩 阵的合理 性 解释 最后 将 一致 性 学 习算 法及 其 变形 应 用予 人脸识 别 问题 对该 算法 中的参数 以及 变形矩 阵进 行 了实验研 究 并与 支持 向 量机 方 法进行 了性 能比较 关 键词 半 监督学 习 一致 性方 法 收敛 人脸识 别 中图分类 号 TP 1 8 1 文献 标志码 A 文章编 号 1 0 0 0 1 5 6 5 2 0 1 1 0 1 0 0 9 2 0 6 Co nv e r g e n c e o f S e mi s u p e r v i s e d Le a r ni ng Al g o r i t h m a n d I t s Ap p l i c a t i o n t o Fa c e Re c o g ni t i o n LI Ka i MA Ho n g y a n YANG Na n CHE N Xi n y on g 1 C o l l e g e o f Ma t h e ma t i c s a n d C o mp u t e r S c i e n c e He b e i Un i v e r s i t y B a o d i n g 0 7 1 0 0 2 Ch i n a 2 Col l e ge of I n du s t r i a l a nd Co mm e r c i a l He be i U n i v e r s i t y Ba od i n g 07 1 0 0 2 Chi n a Ab s t r a c t Cons i s t e nc y me t h od a nd i t s v a r i a n t s i n s e mi s u pe r v i s e d l e a r ni n g a r e s t u d i e d By i nt r o duc i ng c i r c l e di s k t h e o r e m c o nd i t i on f or c o ns i s t e nc y m e t ho d S c o nv e r ge n c e i s pr o v e d i n d e t a i l A i me d a t c o ns i s t e n e y me t h o d S v a r i a n t s wh i c h u s e v a r i a n t ma t r i x t h e v a l i d e x p l a i n a t i o n i s g i v e n Fi n a l l y c o n s i s t e n c y me t h od a nd i t s va r i a n t s a r e a pp l i e d t o f a c e r e c og ni t i o n Ex pe r i me nt a l s t u dy i s c o n du c t e d o n t he p a r a me t e r s a n d t h e t r a n s f o r ma t i o n ma t r i x i n v o l v e d i n c o n s i s t e n c y me t h o d Me a n wh i l e t h i s a l g o r i t h m a n d i t s v a r i a n t s pe r f o r ma nc e a r e c o m p a r e d wi t h t ha t o f s u p po r t ve c t o r ma c h i ne me t ho d Ke y wo r ds s e mi s u pe r vi s e d l e a r n i ng c o ns i s t e n c y me t h od c o nv e r g e n c e f a c e r e c o gn i t i on 机 器学 习是人工 智能 的重要研 究方 向 主要包 括监 督学 习 无 监督 学 习 与半监 督 学 习 给定 一个 数 据集 Y Y 其 中 2 7 一 为 第 i 个样本 的属性 向量 元 素 z 为第 i 个样本 的第 个属 性 值 该 属性 既可 以为 离散值 也可 以为连续值 3种学 习方法 的主要 不 同在 于 系统 是否 具有 先验 知识 及具 有 先验 知识量 的程度 当 N 个 样本点 的所有 1 2 N 值 已知或 未知 则分别 为监督 学 习或无 监督 学 习 然而 在现实生活中 由于获取有标号数据是非常困难的 再加上获取它们花费的费用较高及所需时间较 多 同时 无 标号数 据却 是容易 获得 而 这部分 数据却很 少使 用 即所谓 的半监督 分类 学 习 1 也就是 说 当 N 收稿 日期 2 0 1 0 0 6 3 O 基金项目 国家 自然科学基金资助项 目 6 0 7 7 3 0 6 2 6 1 0 7 3 1 2 1 河北 省 自然科学基金资助项 目 F 2 O O 9 0 0 0 2 3 6 第一作者 李凯 1 9 6 3 一 男 河北满城人 河北大学教授 博士 主要从事机 器学 习 计算智能 模式识别 数据挖掘 神经网 络等方 向研究 E ma i l l i k a i h b u e d u c n 第 1 期 李 凯 等 半监督学习算法 的收敛性 及其在人脸识别 中的应用 个样本 点 的很 少一 部分 样本 的 Y 值 已知 则 为 半监 督学 习 半 监 督 分类 学 习 的 主要 目标 是 如何 利 用 少量 标 号 数据 与大量 无标 号 数据 提高 系统 的泛 化能 力 最 近 研 究人 员 针对 半监 督学 习提 出 了许多 学 习方法 E 在 本文 中 主要针 对 一致 性学 习 算法 C M c o n s i s t e n c y me t h o d 进行 了研究 详 细 证 明 了 C M 收敛 的 重要 条件 将 C M 应 用 于人脸 识别 问题 实验 研究 了该 算 法 的性 能 1 一致性 学习算法 已 知数 据集 X lz H 其 中 R 且 Y 1 c 需 要 注意 的是 集合 X 中点z 一 没 有标 号 学 习的 目标是 预测 无标 号 数据 件 一 的类 别 通 常 z 远小 于 7 即 z 令 F表 示元 素为 F非 负矩 阵 的集合 F E FT F F对应 于数 据 集 X 的一 个分 类结 果 通过 对矩 阵 F 中 每一 行取 最 大值 可 以得 到 每个 数据 点 的最后 标 号 即 一 a r g ma x F 另外 定义 f 矩阵 y F 其 中该 f l I V 一7 一 矩阵元素是按照如下方式取值 Y 一 针对这种问题 Z h o u 给出了如下的 C M算法 3 I U ot he rw l S e S t e p 1 计 算任 意 2点 问 的相似 性 形 成 相似 矩 阵 W 一 w 其 中 W j J e x p 一 1 2c i 川 2 0 z J S t e p 2 权矩 阵 的归 一化 构造 矩 阵 S D wD 其 中矩 阵 D d i a g D 是一 个对 角矩 阵 对角线 元素 D W 即 矩阵 W 对应行 上 元素 之和 一 1 2 表示 矩 阵 D 中元 素 的平方 根 的倒数 S t e p 3 按 照下 面 的迭代 公式 进行 迭代 直 至收 敛 F t 1 一 a S F t 1一 口 y 其 中 a O 1 是一 个参 数 S t e p 4 令 F 表示 序 列 F 的极 限 按 照 下 面方法 确定 每个 数据 点 的类标 号 y z ar g 2 一致性学 习算法及其 变形 的收敛性 引 理 Ge r s c h g o r i n 圆盘 定理 设 A是 阶复 矩 阵 则 它 的特征 值 至少满 足下 列 不等式 之 一 1 一口 l l i l 2 1 J 证 明 设 是 A 的一 个特 征值 a一 是它 的一 个特 征 向量 则 A a A a 即 a1 l lz1 4 l 2 2 4 al lz 1 a2 1 l 4 a2 2 2 4 a 2 72 A x 2 a l 1 4 2 2 4 4 口枷 一 令 I ma I J 则 o 将第 个方 程改写 为 n 一 n 两 边取 模得 l J n 州 I Il l l n ll l l z I n f 所以I n l l a 1 1 J J 卅 1 J 声 卅 l t 在 文献 E 3 3中 Z h o u给 出 了 C M 算 法并 对该 算 法 的收敛 性 给 出了一个 证 明框 架 然而 在该 算法 中 对 S 矩 阵 的特征 值 的绝对 值 为什 么小 于 1 并 未给 出证 明 为此 本 文详 细给 出了它 的证 明过程 命 题 1 矩 阵 s D 1 WD 的特征值 在 一 1 1 中 证 明 因 为 D W D S D 令 P D W 所 以矩 阵 P与 s相 似 根 据 相似 矩阵 具有 相 同的特 征值 知 矩阵 s的特征值与矩阵P的特征值相同 下面只要证明 P的特征值在 一 1 1 之间即可 9 4 河北大学学报 自然科学版 2 0 1 1 年 由 P 一 W 知 P o W 1 2 W l 3 W 1 O 0 O 1 W W W 一W 1一 W W W 埘 一 t W W z W 一 1 可 以看 到 矩 阵 P的第 i 行元 素之 和记 为 P 有如 下表达 式 0 W 1 W 2 0 W 1 2 W l 3 W l O P 一 W i l 瓶 W n W 2 W 1 W W w 2 W 自 鱼 一 W d W W W W 2 V n十 W f2十 十 一 1 W 计 l W 一1 1十 十 十 由盖尔圆盘定理知 矩阵 P的特征值在 一1 1 之间 也就是 S矩阵的特征值在 一 1 1 之间 命题 2 t 设 F 为 目标 函数 针 对分类 问题 有 F 一 卜 口 S Y 证 明 由迭代 公式 F t 1 一 a S F f 1 一a y 有 F a S l y 1一 a a S i y 石 因为 0 口 1 并且 S的特征值是 一1 1 由命题 1 知 所以有 l i ra r S 一 0 a S一 由 2 式 知道 3 式可 以写为 l i ra a S t一 J a S 一o 将式 2 与式 4 代 人式 1 可得 F 一 l i mF t 一 1一 口 J a S 一Y 对 于分类 问题来 说 5 式 可 以等价为 下式 1 2 3 4 5 F 一 I d S Y 命 题 3 已知 P为 的相似 随机矩 阵 P D W D S D 则 F 一 卜一 a S Y可 近似 表示 为 F 一 r一 口 P 一Y 证明 因为 P D W D S D 在方程两端分别左乘 D 和右乘 D 得到 S D P D 门 将 s 带 入 目标 函数 F 一 a S Y得 F 一 PD 一 一Y 6 可 以把 6 式 的 J 用 D D 叫 来代 替 则 6 式变 为 F 一 D D一 DI 2 PD一 一 Y 7 对 7 式 同时左 提 D 和右提 D 则 7 式 变为 F 一 D f a P D一 Y 8 F D J a P 2 Y 9 第 1 期 李凯 等 半监督学 习算法 的收敛性及其在人脸识别 中的应用 因为 D a P D 相似 于 j a P 所 以式 9 可近似 表 为 F 一 J 一 口 P Y 命 题 4 已 知 P 为 S的 相 似 随 机 矩 阵 P D W D S D 则 F 一 卜一 P F 一 P Y 证 明 由 P D S D 知 将该 式 两边求 转 置得 P 一 D S D 即 P 一 D S D一 因 为 D 为对 角矩 阵 所 以有 D 一 D D 1 一 D 则 式 1 0 可 变为 y近 似 表 为 1 O P 一 D S D 一 1 1 由 S D WD 且 D 为 对 角 矩 阵 得 到 S 一 D W D 又 因 为 W 是 一 个 对 称 矩 阵 所 以 S D wD 由此可 得 S 一 s 这 样 式 1 1 变 为 P 一 D S D 则 S D P D 将 S代 入 F 一 一a S Y 则 目标 函数 变 为 F 一 j a D P D Y 将 单位 矩 阵 J 用 D D 来代 替 则上 式 变 为 F 一 D D 一 一 P D 一 Y F 一 D一 一 a P D Y F 一 D一 J a P D Y 因为 D I 一口 P DV 与 I a P 相 似 由此 可得 F 一 卜一口 P Y 3 人 脸 识 别 实 验 及 分 析 通过 人脸 数据 库对 C M 算 法 C M 算法 的变 形及 所 涉及参 数进 行 实验研 究 为此 选取 了 Or l 与 Y a l e 人脸 数据 库 Or 1 人 脸数据 库包 括 4 0人 且 每人有 1 O幅不 同的 图像 每 幅 图像 的大 小为 u 2 9 2 每 幅图像 中的 人 脸都 是 向前或 稍微 有些 倾斜 但 是灯 光 脸 部 表情 和细 节却 有所 不 同 而 Ya l e 人脸 数据 库包 括 1 5 人且 每人有 1 1 幅人脸 像 每 幅图像 的大小 为 1 0 0 1 0 0 每 幅人 脸 图像有 不 同 的遮 挡 且 光 照变 化 明 显 部 分人 脸 图像见 图 1 a b所示 h a r 1 人 脸 数 据 厍 b Ya l e人 脸 数 据 厍 图 1 Or l 与 Ya l e人 脸 库 中 部 分 图 像 Fi g 1 Pa r t f a c e i m a g e s f o r Or l a nd Ya l e 对指 数 函数 中尺度 因子 d s i g ma 进 行 了 实验 分 别 选 取 S 1 0 1 5 S 2 0 2 5 S 3 0 3 5 S 4 0 4 5 S 5 0 5 5 S 6 0 6 5 S 7 0 7 5 S 8 0 8 5与 S 9 0 9 5共 9 个 数值 在 半监 督学 习方 法 中 针对 人脸 数据 库 对 每个 人选 择 了具有 类 标号 的样 本个 数分 别 为 1 1 O 与 1 1 1 间的整 数 对 每个 数 值 进行 了 1 O次 实 验 取 1 O次实 验 中具有 相 同尺度 因子 时 的平均 值 另外 为 了进行 比较 选 取 了 U B S VM 工具 对 人脸 数据 库也进 行 了实 验研 究 针对 Or 1 人脸 库 其训 练 数 据 集 分别 为 4 O 8 0 1 2 O 1 6 0 2 O O 2 4 0 2 8 0 3 2 0 3 6 0和 4 0 0 剩余 的人脸 做测 试集 其 中训 练数 据集 个数 为 4 0 0时 测 试 数据 集 与 训 练 数据 集 相 同 而对 Ya l e 人 脸 库 其训 练 数据 集分 别 为 1 5 3 0 4 5 6 O 7 5 9 0 1 0 5 1 2 0 1 3 5 1 5 0和 1 6 5 剩 余 的人脸 做 测试 集 其 中训练 数 据集 个 数为 1 6 5 时 测试 数 据集 与训 练数 据集 相 同 在 支 持 向 量 机 中 选 择 的核 为 径 向基 函数 其 他 参数 采 用 了默认 值 针 对支持 向量机 分类 器 共进行 了 1 O次实 验 图 中给 出的是 1 O次实验 的平 均值 实 验结 果如 图 2 3所 示 9 6 河北大学学报 自然科学版 2 0 1 1 年 1 0 8 斟 0 6 善0 4 0 2 O 0 9 7 0 5 O 3 1 1 瓣 0 9 器 o 7 o 5 OI 3 1 0 褂 0 8 髂 0 6 0 4 一 S1 S 2 S 6 s 7 乏 一 母 一一 一 l 2 3 4 5 6 7 8 9 1 O 样本数 J 一 毒 卜斗 一 二 一一 一 l1 1 2 3 4 5 6 7 8 9 l 0 样本 数 一 1 2 3 4 5 6 7 8 9 1 0 样本 数 a C s 3 一 S 4 S 5 S8一S 9 0 9 祷 0 7 嚣 0 5 0 3 O 9 褂 0 7 器 0 5 O 3 1 0 瓣0 8 器 0 6 0 4 一 墨 口 叼 爱 r l l l I j I l 2 3 4 5 6 7 8 9 l O l 1 样本 数 罄 舞童 晕 回 1 2 3 4 5 6 7 8 9 l 0 l 1 样本 数 J 一 J 一 1 2 3 4 5 6 7 8 9 1 0 l 样本 数 a c e C MS C MP与 C MP T方法在 Or 1 人脸库的测试结果 b d f CMS CMP与 C MP T方法在 Y a l e 人脸库 的测试结果 图 2不 同类 标 号 数 目与 正 确 率 闯 的关 系 Fi g 2 Re l a t i o n b e t we e n nu mb e r o f di f f e r e nt l abel e d s a mp l e s a n d a c c u r a c y 豫C MS C MP 口C MPT 口SVM l 2 3 4 5 6 7 8 9 l O 样本数 1 O 0 8 髅 卜0 6 器 0 4 0 2 0 0 b d 1 2 3 4 5 6 7 8 9 1 0 l 1 样本数 a Or 1 人 脸 测 试 结 果 b Ya l e人 脸 测 试 结 果 图 3 S V M 方法与 C M 算 法及 变形 的实验结果 比较 Fi g 3 Co m p a r i s i o n o f e xp e r i me nt al r e s ul t s wi t h S VM CM a n d i ts v ar i a n ts b 第 l期 李凯 等 半监督学 习算 法的收敛性及其在人脸识别 中的应用 在 图 2中 a c 与 e图是 针对 Or 1 人 脸库 的 实验 结 果 而 b d与 f 图是 针 对 Ya l e 人 脸 库 的 实验 结 果 其 中 a与 b是针 对标 准 CM 算法 记为 C MS算法 的实 验结 果 而 c与 d e与 f 分 别 是 C M 算 法 的变 形 分 别 记 为 C MP与 C MP T算 法 也 就 是说 它们 分别 是将 C M 算 法 中 的 S用 P 与 P 替 换 后 的 实验 结 果 从 图 2 中 可 以看 到 用矩 阵 替 换 s矩 阵 变 化 不 大 而 用 P替 换 s矩 阵 后测 试 正 确 率 有 较 大 的起 伏 特别 是 当 S 9 0 9 5时变 化 比较 明显 另外 对 于尺 度 因子 取 值不 同 C M 算法 的测 试正 确率 也有 较大 的不 同 尤 其 是 在 已知 类标 号个 数较 少 的样 本时 对 尺度 因子 d 取 值 比较敏 感 为 了表 明 C M 算 法 的性能 使用 支持 向量 机 分类 器 进 行 了人 脸 识 别 通 过 选 取不 同个 数 的人 脸样 本 进 行 训练 然 后对 其余 的人脸 进 行测试 实 验结 果 如 图 3 a与 3 b所示 其 中 图 3 a 是 针对 or 1 人 脸 库 的实验 结 果 而 图 3 b是 针 对 Y a l e人 脸 库 的 实 验 结 果 可 以 看 到 C M 算 法 的 性 能 优 于 S VM 算 法 同时 C MS与 C MP T方 法 的性能 相 当 而 C MS与 C MP方法 的结 果有 较 大 的偏差 笔 者认 为 C MS与 C MP算法 的实验 结 果 有较 大 的偏差 主要 在 于 P矩 阵并不 是对 称矩 阵 4 结论 研究 了一 致性 学 习算法 及其 变形 给 出 了 C M 算 法 收敛 的重 要 条 件 的 详 细 证 明 另外 也研 究 了该 算 法 几 种变形 的 收敛性 证 明 了 C M 算 法 中使 用 变 形 矩 阵 的 合 理性 最后 通 过人 脸 识 别 问 题 实 验 研 究 了 C MS 算法 C MP算 法 以及 C MP T算 法所 涉及 的参 数对 分类 的影响 同 时与基 于支 持 向量机 的人脸 识 别 方法 进 行 了 比较 参 考 文 献 1 Z HU Xi a o j i n S e mi s u p e r v i s e d l e a r n i n g l i t e r a t u r e s u r v e y R Ma d i s o n Un i v e r s i t y o f W i s c o n s i n 2 0 0 8 2 C HA P E l I E O Z I E N A S e mi s u p e r v i s e d c l a s s i f i c a t i o n b y l o w d e n s i t y s e p a r a t i o n Z T h e 1 0 t h i n t e r n a t i o n a l w o r k s h o p on ar t i f i c i a l i n t e l l i g e nc e an d s t a t i s t i c s Ba r b a do s 20 05 3 Z HOU D e n g y o n g B OUS Q UE T O T HO MA S N I e t a 1 L e a r n i n g w i t h l o c a l a n d g l o b a l c 0 n s i s t e n c y C THR UN S SAUI L SCH I KOPF B Adv a nc e s i n n e ur a l i nf o r ma t i on p r oc e s s i n g s y s t e ms Ca mbr i dge M I T p r e s s 2 0 04 3 2I一 32 8 E 4 3 Z H u Z h i h u a Z HAN D e c h u a n Y ANG Qi a n g S e mi s u p e r v i s e d l e a r n i n g wi t h v e r y f e w l a b e l e d t r a i