基于条件随机场的中文科研论文信息抽取.pdf

华 南 理 工 大 学 学 报 自 然 科 学 版 第 35卷 第 9期Journal of South China University of Techno logyVo l 35 No 9 2007年 9月 Natural Science Edition Septe mber 2007 文章编号 1000 565X 2007 09 0090 05 收稿日期 2006 11 27 基金项目 教育部博士点基金资助项目 20050007023 作者简介 于江德 1971 男 博士生 主要从事自然语言 处理 信息抽取和信息检索方面的研究 E mai ljangder bit edu cn 基于条件随机场的中文科研论文信息抽取 于江德 樊孝忠 尹继豪 北京理工大学 计算机科学技术学院 北京 100081 摘 要 科研论文头部信息和引文信息对基于域的论文检索 统计和引用分析是必不可 少的 由于隐马尔可夫模型不能充分利用对抽取有用的上下文特征 因此文中提出了一种 基于条件随机场的中文科研论文头部和引文信息抽取方法 该方法的关键在于模型参数 估计和特征选择 实验中采用 L BFGS算法学习模型参数 并选择局部 版面 词典和状态 转移 4类特征作为模型特征集 在信息抽取时先利用分隔符 特定标识符等格式信息对文 本进行分块 在分块基础上用条件随机场进行指定域的抽取 实验表明 该方法抽取性能 明显优于基于隐马尔可夫模型的方法 且加入不同的特征集对抽取性能提升作用不同 关键词 信息抽取 条件随机场 引文信息 论文头部信息 中图分类号 TP391 文献标识码 A 随着科学研究的快速发展和信息更新速度的加 快 全世界发表的科研论文越来越多 这使得人们对 科研论文的检索 统计 分析技术要求越来越高 而 科研论文的头部信息和引文信息对基于域 如标 题 作者 关键词 的论文检索 论文信息统计和引 用分析是不可缺少的 论文的头部信息包括论文标 题 作者 作者隶属单位 摘要和关键词等十几个域 引文信息是包括作者 标题 期刊名 期次和页码等信 息的引文格式表述 通过获取科研论文的头部信息和 引文信息 不仅可以有效地组织和管理这些论文 提 高用户检索论文的效率 而且还能够进行大量的统计 工作 如论文主题分析 1 及相关论文统计 对期刊 科 研单位 某篇论文或某个学者进行引用分析以及发现 研究热点和研究趋势等 所以 从科研论文中自动抽 取头部信息和引文信息有着重要的研究价值 国内外对该问题进行了大量的研究和实验 文 献 2 用一个隐马尔可夫模型 HMM 对计算机科 研论文头部信息的所有域进行抽取 取得了 9219 的抽取精度 林亚平等 3 用基于最大熵的 HMM 对 科研论文头部信息和学术报告信息进行抽取 刘云 中等 4 用 HMM模型及文本排版格式 分隔符等信 息 对科研论文头部信息进行抽取 张玲等 5 采用 基于符号特征提取的 HMM 结构学习方法 进行引 文信息抽取 文献 6 采用支持向量机 SVM 从论 文的头部信息中抽取元数据 这些研究都把该问题 看成序列标注或分类问题 并采用序列标注模型或 分类器来实现 尤其以 HMM模型居多 作为一种生 成模型 尽管 HMM被广泛用于序列标注 但它并不 是最合适的模型 HMM 通过定义标记序列 S和观察 序列 O的联合概率 P S O 来搜索最佳的标记序 列 定义这样的联合概率意味着所有可能的观察序 列都应该被枚举出来 这个任务是很困难的 当观察 元素间具有长距离依赖性时尤其如此 所以 为了保 证推导的正确性 HMM 给出两个独立性假设 1 假设每个状态仅仅依赖于它的前一时刻状态 2 假设 t时刻的观察值仅仅依赖于 t时刻的状态 这两 个假设简化了推导 但同时也降低了标注性能 事实 上 真实的序列数据不仅存在长距离依赖性 而且观 察序列中各种有利于提升标注性能的上下文特征对 标注意义重大 针对 HMM 的这一缺点 文中提出了一种基于 条件随机场 CRFs 的中文科研论文头部信息和引 文信息抽取方法 CRFs是 Lafferty等 7 于 2001年提 出的一种用于序列数据标注的条件概率模型 是一 种判定性模型 CRFs通过定义标记序列和观察序列 的条件概率 P SO 来预测最可能的标记序列 不 仅能够将丰富的上下文特征整合到模型中 而且还 克服了其他非产生性模型 如最大熵马尔可夫模 型 的标注偏差问题 7 应用 CRFs抽取科研论文头 部信息和引文信息的关键是模型参数估计和特征选 择 文 中采用 L BFGS L i m ited memory BFGS 算 法 8 对模型参数进行估计 并选择 4类特征作为模 型特征集 在抽取中文科研论文信息时先利用分隔 符 特定标识符等格式信息对文本进行分块 在分块 基础上用 CRFs模型进行指定域的抽取 实验结果 表明 该方法抽取性能明显优于 HMM 模型 1 条件随机场 条件随机场是一种以给定的输入节点值为条件 来预测输出节点值概率的无向图模型 用于模拟序 列数据标注的 CRFs是一个简单的链图或线图 图 1 所示是一种最简单且最重要的 CRFs 称为线链 CRFs 线链 CRFs假设在各个输出节点之间存在一 阶马尔可夫独立性 其输出节点被无向边连接成一 条线性链 图 1 线链 CRFs的图形结构 Fig 1 Graphical structure of linear chain CRFs 设 O o1 o2 oT 表示被观察的输入数据 序列 如头部信息的词序列 S s1 s2 sT 表示 被预测的状态序列 每一个状态均与一个标记 如 标题等 相关联 这样 在一个输入序列给定的情况 下 对于参数为 l1 l2 lK 的线链 CRFs 其 状态序列的条件概率为 P S O 1 ZO exp E T t 1 E K k 1 lkfk st 1 st o t 1 式中 归一化因子 ZO确保所有可能的状态序列的 条件概率和为 1 是所有可能的状态序列的 得分 0 之和 即 ZO E S exp E T t 1 E K k 1 lkfk st 1 st o t 2 fk st 1 st o t 是一个任意的特征函数 通常是一个 二值表征函数 lk是一个需要从训练数据中学习的 参数 是相应特征函数 fk st 1 st o t 的权重 给定一个由式 1 定义的条件随机场模型 在 已知输入数据序列 O的情况下 最可能的标记序列 可以由式 3 S argmax S P S O 3 通过类似于 HMM 中的韦特比算法动态规划求出 而状态转移概率的计算也可以用类似于 HMM 中的 前向后向算法求得 1 1 参数估计 建立 CRFs模型要解决的两个关键问题是参数 估计和特征选择 参数估计是从训练数据集学习每 个特征的权重参数 即求解向量 l1 l2 lK 的过程 这个过程通过最大对数似然估计实现 将训 练数据集表示为 D O i S i N i 1 其中 O i o i 1 o i 2 o i T 是第 i个输入数据序列 S i s i 1 s i 2 s i T 是相应的输出数据序列 在训练数据集 D 下对数似然为 L E N i 1 lgP S i O i 4 将条件概率公式 1 代入式 4 可得 L E N i 1 E T t 1 E K k 1 lkfks i t 1 s i t o i t lgZ O i 5 为了避免对大量参数估计时出现的过拟合问 题 对数似然经常需要将参数作先验分布调整 采用 高斯先验调整后 式 5 变为 L E N i 1E T t 1E K k 1 lkfks i t 1 s i t o i t E N i 1 lgZO i E k l 2 K 2R 2 6 其中最后一项是用于进行调整的特征参数的高斯先 验值 R 2 表示先验方差 优化式 6 需要一个迭代的 过程 传统办法是 Della P ietra等在 GIS算法 Gene ralized Iterative Scaling Algorithm 9 基础上提出的 IIS算法 I mproved Iterative Scaling A lgorithm 10 IIS算法或基于 IIS的算法的最大缺点是计算量大 求解速度慢 文中采用 L BFGS算法 8 对 CRFs的参 数进行估计 L BFGS算法的训练速度比 IIS算法 11 快 它是一种充分利用以前的梯度和修正值来近似 曲率值的二阶方法 可以避免准确的 H essian矩阵 的逆矩阵计算 因而使用 L BFGS算法进行 CRFs训 练只要求提供似然函数的一阶导数 训练数据集的 对数似然函数的一阶导数为 91 第 9期于江德 等 基于条件随机场的中文科研论文信息抽取 9L 9 lk E N i 1 E T t 1 fks i t 1 s i t o i t E N i 1 E T t 1 E s sc fks sc o i t Ps sc O i lk R 2 7 式中 第一项为特征 fk在经验分布下的期望值 第 二项为特征 fk在模型 下的期望值 对于它们的计 算 可采用动态规划高效实现 1 2 特征选择 特征选择就是如何针对特定的任务为模型选择 合适的特征集 针对从科研论文中抽取信息这一任 务 在详细分析输入文本上下文信息的基础上 文中 将特征分成 4类 局部特征 版面特征 外部词典特 征和状态转移特征 1 2 1 局部特征 局部特征是指输入序列的局部 可以是一个 词 一个抽取域 所特有的拼写 字符形式上的特 征 这些特征是最基本的特征 例如 邮政编码包含 且仅包含六位数字 姓名包含 2 4个汉字等 文中 用到的部分局部特征如表 1所示 表 1 局部特征列表 Table 1 List of local features 特征函数特征含义描述特征函数特征含义描述 ALLCHINES E所有字符都是汉字CONTAINSDOTS 至少包含一个 0 CONTAI NS DIGITS包含数字SINGLECHAR仅仅一个字母 ALLDIGITS所有字符都是数字NAM E包含 2 4个汉字 SIXDIGITS包含仅包含 6个数字BIGLENGTH超过 40个汉字 1 2 2 版面特征 版面特征主要指要分析预测的对象在输入序列 中所处的版面位置 字体格式等与排版相关的特征 文中用到的版面特征如表 2所示 表 2 版面特征列表 Table 2 L ist of layout features 特征函数特征含义描述特征函数特征含义描述 LI NE START一行的开始BI G SIZE大字体 L I NE I N一行的中间BOLD粗体 LI NE END一行的末尾I TALI C斜体 1 2 3 外部词典特征 外部词典特征是指要分析的对象中的一些字 词 是某类特征词 这些字 词是某个外部词典中的一条 记录 这些外部词典有 中国人名姓氏字典 中国人名 常用字词典 中国地名词典 单位名称特征词词典和 论文标题高频词词典等 例如 姓名域中的第一个字 在姓氏词典中 单位域中有 大学0 学院 0等词条出 现在相应词典中等 部分外部词典特征如表 3所示 表 3 外部词典特征列表 Table 3 List ofLexicon features 特特征征函函数数特特征征含含义义描描述述 FAM ILYNAME在姓氏词典中 AFFILI AT I ON包含 大学0 学院0等词条 TITLE包含 基于0 研究0等词条 CLCNUMBER在中图分类号中 ADDRESS在地名词典中 1 2 4 状态转移特征 在条件随机场中 特征函数 fk st 1 st o t 既能 整合输入数据序列的特征 也能整合状态转移的特 征 例如 当 st 1标记 标题0 st标记 作者0 并且 ot 中第一个字在姓氏词典中时 特征函数应取值为 10 这样 CRFs模型将状态转移 st 1y st整合到特 征函数中 2 基于 CRFs的科研论文信息抽取 科研论文的头部信息可以看成是一个语义块序 列 这些语义块分别属于标题 作者 隶属单位 邮编 等不同的抽取域 例如 一篇中文计算机科研论文 1 的头部信息如下 1 该论文见5电子学报62003年 11期 基于最大熵模型的汉语句子分析 徐延勇 周献中 井祥鹤 郭忠伟 南京理工大学自动控制系 江苏南京 210094 摘 要 文中运用浅层句法分析理论 把 关键词 自然语言处理 最大熵模型 组块 中图分类号 TP391 1 文献标识码 A 文章编号 037222112 2003 1121608205 对不同期刊的大量论文头部信息分析后 文中 将抽取域固定在标题 作者 单位 地址 邮编 摘要 关键词 中图分类号 文献标识码共 9个抽取域 利 用 CRFs从论文头部抽取信息时 每个状态和要抽 取的一个域相关联 在抽取时充分利用逗号 分号 空格 括号和回车等分隔符将输入数据序列划分成 语义块 以这些可观察的语义块序列为条件预测每 个状态相关联的域 详细抽取过程描述如下 1 对论文头部进行预处理 主要是依据回车 和逗号 分号等分隔符对头部信息进行语义块切分 然后在语义块基础上进行信息抽取 另外 还要根据 摘要0 中图分类号 0 关键词0等特定标签将相 应抽取域标记 92华 南 理 工 大 学 学 报 自 然 科 学 版 第 35卷 2 采用 L BFGS算法从标注好的训练数据集 D O i S i N i 1学习 CRFs模型的参数 即各特 征函数的权重向量 3 在给定 CRFs模型 下 结合式 1 和 3 用韦特比算法动态规划预测出最可能的状态序列 即 语义块相关联的域 然后按关联情况抽取各个域 利用 CRFs对引文信 息的抽取过 程与利用 CRFs模型对论文头部信息的抽取过程类似 这里不 再赘述 3 实验及结果分析 文献 2 4 6 用于科研论文头部信息和引文信 息抽取的语料是英文语料 都是基于美国卡内基梅 隆大学 C MU 的两个数据集 935篇计算机科研论 文头部信息数据集和 500条引文信息数据集 进行 实验和研究 这两个数据集来源于 http Mwww cs cmu edu kseymore ie ht m l 文中使用的中文实验 数据集是从中国期刊网 CNKI 全文数据库和引文 数据库中检索计算机方面的论文整理标注而得到 的 这些论文来源于计算机类中文核心期刊 其中科 研论文头部信息数据 600篇 引文数据 1500条 这 些数据都采用 TXT 格式保存 实验中 对论文头部 信息数据集 随机抽取其中的 500篇作为训练语料 剩下的 100篇作为测试语料 对论文引文信息数据 集 随机把其中的 1 200条作为训练语料 剩下的 300条作为测试语料 在从训练数据集构建 CRFs模 型时 采用 10重交叉验证方法来获取最优的模型 即训练集被随机划分为 10个不相交的组 对模型训 练 10次 每次留出一组作为验证集用于评价推广误 差 其他 9组作为训练集用于调整模型参数 最终得 到的模型有最低的推广误差 在对抽取性能进行评估时 采用常用的 3个评 测指标 准确率 P 召回率 R 综合指标 F 值 F P 和 R 的计算公式如下 P 准确抽取的信息条数 抽取出的所有信息条数 8 R 准确抽取的信息条数 应该返回的信息条数 9 实际评估时 应同时考虑 P 和 R 但同时比较两个数 值 很难做到一目了然 所以通常采用综合两个值 综合指标 F值 进行评价 其计算公式 12 如下 F B 2 1 PR B 2P R 10 式中 B表明对 P 侧重还是对 R 侧重 通常设定为 1 2或 1 2 文中 B取值为 1 即对二者一样重视 首先在公认的测试数据集 卡内基梅隆大学的 两个英文数据集 上对基于 CRFs的方法进行了实 验 头部和引文信息抽取的平均 F 值分别为 9516 和 9617 对头部信息抽取的性能略高于 SVM 法 平均 F 值为 9511 6 然后分别采用 CRFs和 HMM 模型在相同的中 文实验数据集上进行头部信息和引文信息的抽取实 验 其中 CRFs模型使用了前面提到的全部 4类特 征集 结果如表 4和表 5所示 表 4 中文科研论文头部信息抽取结果 Table 4 Extraction results of paper header infor mation from Chinese research papers 抽取域 CRFsHMM PRFPRF 标题0 9710 9180 9440 9150 8480 880 作者0 9860 9460 9660 9220 8350 875 单位0 9770 9180 9470 9210 8370 877 地址0 9760 9360 9560 9310 8510 889 邮编0 9960 9790 9870 9580 9160 937 摘要0 9841 0000 9920 9790 9880 984 关键词0 9690 9370 9530 9290 9050 917 中图分类号0 9830 9630 9730 9670 9390 953 文献标识码0 9970 9960 9970 9780 9850 985 表 5 中文科研论文引文信息抽取结果 Table 5 Extraction results of citation infor mation from Chinese research papers 抽取域 CRFsHMM PRFPRF 作者0 9890 9700 9790 9070 8640 885 标题0 9840 9360 9590 8980 8260 860 刊名0 9570 9350 9460 8710 8450 858 卷号0 9620 8260 8890 8760 8680 872 年0 9820 9590 9700 9780 9320 954 页码0 8910 8750 8830 8390 8620 850 从表 4和表 5可以看出 在抽取头部信息和引 文信息方面 基于 CRFs的性能明显优于基于 HMM 的性能 CRFs对所有抽取域的综合指标 F 值都高 于 HMM 图 2比较了基于 CRFs和 HMM 的中文科 研论文头部信息的抽取结果 从图 2可以看到 这两 种方法对有特定标识符的抽取域 如摘要 中图分 类号等 的抽取性能差别不大 这主要是特定标识 符在这两种方法中起重要作用所致 而对于其他域 基于 CRFs的抽取性能明显优于 HMM 这进一步说 明上下文特征对标注意义重大 93 第 9期于江德 等 基于条件随机场的中文科研论文信息抽取 图 2 CRFs和 HMM 的中文科研论文头部信息抽取结果比较 F ig 2 Co mparison of extraction results bet ween CRFs andHMM 1 作者 2 标题 3 单位 4 地址 5 邮编 6 摘要 7 关键词 8 中图分类号 9 文献标识码 为了比较不同特征集对抽取性能的影响 在基 于 CRFs的实验中 起先只使用局部特征集 A 然 后再加入版面特征 B 词典特征 C 和状态转移 特征 D 并观察不同特征空间对信息抽取性能的 影响 结果如表 6所示 从表 6可以看出 版面特征 对抽取性能的影响不大 加入版面特征后 F 平均值 从原来的 9119 提升为 9219 词典特征对抽取性 能的影 响较大 加入词 典特 征后 F 平 均值从 9119 提升为 9415 加入状态转移特征后抽取性 能也有一定的提升 表 6 使用不同特征集时中文科研论文的头部信息抽取结果 Table 6 Extraction results of paper header infor mation fro m Chinese research papers using different features 特征集P 平均值R 平均值F 平均值 A0 9240 9160 919 A B0 9390 9220 929 A C0 9570 9380 945 A D0 9370 9180 928 A B C D0 9820 9550 968 4 结语 随着科研论文资源的日益增多 如何高效地检 索科研论文并进行相关统计是人们急需解决的问 题 这使得准确抽取论文头部信息和引文信息非常 必要 文中针对 HMM 不能充分利用对标注有用的 上下文特征这一问题 提出了一种基于条件随机场 的中文科研论文头部信息和引文信息抽取方法 并 探讨了应用 CRFs时的两个关键问题 CRFs的参数 估计与特征选择 实验结果表明 基于 CRFs的中文 科研论文信息抽取性能要明显优于基于 HMM 的性 能 目前 CRFs的参数训练和特征选择归纳还存在 速度慢的问题 今后将进一步研究能够提升参数估 计和特征选择归纳速度的算法 参考文献 1 赵英环 郭贵锁 基于主题词迭代提取的信息检索算 法 J 华南理工大学学报 自然科学版 2004 32 增 刊 77 80 Zhao Y ing huan Guo Gu i suo An infor mation retrieval a l gorithm based on the iterative extraction of keyphrases J Journal of South China University of Technology Natural Science Edition 2004 32 Suppl 77 80 2 Sey more K M cCallum A Rosenfeld R Learning hidden M arkov model structure for infor mation extraction C M Proc of theAAA I9 9W orkshop onM achine Learning for Infor mation Extraction Orlando AAAI Press 1999 37 42 3 林亚平 刘云中 周顺先 等 基于最大熵的隐马尔可 夫模型文本信息抽取 J 电子学报 2005 33 2 236 240 L in Ya ping LiuYun zhong Zhou Shun xian et a l Using hiddenM arkovmodel for text infor mation extraction based onmax i mum entropy J Acta Electronica Sinica 2005 33 2 236 240 4 刘云中 林亚平 陈治平 基于隐马尔可夫模型的文本 信息抽取 J 系统仿真学报 2004 16 3 507 510 L iuYun zhong L inYa ping Chen Zh iping Text infor ma tion extraction based on hiddenM arkov model J Jour nal of System Si mulation 2004 16 3 507 510 5 张玲 黄铁军 高文 基于隐马尔可夫模型的引文信息 提取 J 计算机工程 2003 29 20 33 34 Zhang Ling Huang T ie jun G ao W en Citation extraction based on hidden M arkov model J Co mputer Enginee ring 2003 29 20 33 34 6 HanH G iles C M anavoglu E et a l Automatic document metadata extraction using support vectormachines C M Proc of Joint Conf on Digital L ibraries Houston IEEE Press 2003 37 48 7 Lafferty J Pereira F M c Callum A Conditional random fields probabilisticmodels for seg menting and labeling se quence data C M Proc of 18th Int Conf on M achine Learning San Francisco AAAI Press 2001 282 289 8 Byrd R H Nocedal J Schnabel R B Representations of quas iN e wton matrices and their use in li mited me mory methods J M athematical Progra mming 1994 63 2 129 156 9 Darroch J N Ratcliff D Generalized iterative scaling for log linearmodels J Annals ofM athematicalStatistics 1972 43 5 1470 1480 10 Della P ietra S Della P ietra V Lafferty J Inducing fea tures of rando m fields J I EEE Transactions on Pattern Analysis andM achine Intelligence 1997 19 4 380 393 11 Sha F Pereira F Shallo w parsing w ith conditional ran do m fields C M Proc ofHuman Language Technology NAACL Edmonton ACL Press 2003 213 220 下转第 106页 94华 南 理 工 大 学 学 报 自 然 科 学 版 第 35卷 Scheduling of FlexibleM anufacturing System Based on CooperativeGame Liu Jian guo 1 LiQing song 2 WangN ing sheng 1 1 CI MS Engineering Research Centre Nanjing Univ ofAeronautics and Astronautics Nanjing 210016 Jiangsu China 2 Faculty ofComputer NanchangHangkong Univ N anchang 330063 Jiangx i China Abstract For adapting to the agilemanufacturing an effective and rea l ti memanufacturing scheduling isnecessary to the flexiblem anufacturing syste m w ithmult imachining andmult i asse mble equip m en t aswell asw ithm anym a chining and asse mbly processes This paper brings for ward a new scheduling algorithm to decompose the assembly structure of the products obtain si mple proble m s easy to schedule and for m the corresponding Agents Then by applying the cooperative game theory the i mportance and restriction of eachAgent are taken into account to obtain an order of si mple scheduling problem In this order the scheduling of sub questions can be i mplemented in term of rules and the al most opti mal scheduling resultsmeeting the restriction can be obtained Experi mental results f i nally verify the effectiveness of the proposed scheduling algorithm Key words flexiblemanufacturing system scheduling cooperative game Agent 上接第 94页 12 李保利 陈玉忠 俞士汶 信息抽取研究综述 J 计 算机工程与应用 2003 39 10 1 5 L iBao l i Chen Yu zhong Yu Sh iwen Research on in for mation extraction a survey J Computer Enginee ring and Applications 2003 39 10 1 5 Information Extraction from ChineseResearch Papers Based on ConditionalRandom Fields Yu Jiang de Fan Xiao zho