博士资格考核述职报告 大家好，以下是我的述职报告。 各位老师、同学，大家好，我今天要报告的内容是“面向RDF数据集的浏览与查询生成技术”.

简述 课程情况 已有成果 On Coherent Indented Tree Visualization of RDF Graphs. accepted by APWeb 2015 (CCF-C), first author. Generating Characteristic Summaries of Entity Descriptions. submitted to TKDE (CCF-A), major revision, first student author. NaviTree: a Query Construction Tool for SPARQL Endpoint (online system). 其他 两次担任助教： 数据库概论 (博一上）、离散数学（博一下） 首先，简要介绍下基本情况： 三门博士课程均已修完，成绩良好； 三项已有成果： 第一个工作已被C类会议APWeb录用；//一个是关于将RDF图可视化为缩进树的一致性问题的研究，已被C类会议APWeb录用； 另一个是与老师合作的期刊，投了A类期刊TKDE；//另一个是关于生成实体描述的特征性摘要，投了A类期刊TKDE,正在等待第二轮评审结果； 第三个是一个用于对SPARQL Endpoint构建查询的在线系统； 这些都会在后面详细介绍； 另外，两学期助教任务均已完成。 关于将RDF图可视化为缩进树的一致性问题的研究；The 17th Asia-Pacific Web Conference 第17届亚太网络会议，已录用； 特征性实体摘要的生成；IEEE Transactions on Knowledge and Data Engineering IEEE知识和数据工程学报，正等待第二轮评审结果； SPARQL Endpoint查询构建系统；

研究工作-目录 RDF数据的呈现技术 面向RDF数据浏览的查询构建技术 问答系统中基于RDF数据的问句理解技术 RDF图的根树表示 实体摘要 NaviTree在线系统 问答系统中基于RDF数据的问句理解技术 未来工作 接下来，我将从三个方面对我的研究工作进行介绍，它们都与RDF数据处理紧密相关。 首先是关于RDF数据呈现技术的两个工作。 //其中，前两项提供的技术积累，将在后续工作中起到支持作用；

RDF图的根树表示 背景 结构转化问题 一些应用场景需要将图转化为树 同一图可转化为不同形式的根树 图到根树的最优结构转化问题 边的一一映射，点的可重复呈现 传统方法：基于BFS、DFS的简单方法 我们的方法：用确定性算法求解优化问题 优化目标：一致性 James_Cameron Stanley_Kubrick Steven_Spielberg influenced Gale_Anne_Hurd spouse producer made Titanic_(1997_film) director “English” language Aliens_(film) Michael_Bay 第一个工作关于RDF图的根树表示： RDF数据模型本质上是一种点和边均带标签的有向图； 一些应用场景需要将图以树的形式表示,例如本工作中，图的缩进树呈现，这一应用场景； 而同一图的转化结果可能不同。 传统的呈现方式简单基于BFS或DFS进行转换； 而我们认为边的方向在呈现中是有重要意义的，边的反向呈现将影响用户的阅读体验。因此，我们提出了“一致性”的概念，要求在转化结果中反向边数尽可能少。

例子 James_Cameron Stanley_Kubrick Steven_Spielberg is influenced of influenced Gale_Anne_Hurd spouse director Titanic_(1997_film) made “English” language Aliens_(film) Michael_Bay producer COH James_Cameron Stanley_Kubrick Steven_Spielberg influenced Gale_Anne_Hurd spouse producer made Titanic_(1997_film) director “English” language Aliens_(film) Michael_Bay Edmonds’ algorithm James_Cameron Stanley_Kubrick Steven_Spielberg Gale_Anne_Hurd Titanic_(1997_film) “English” Aliens_(film) Michael_Bay 1 cost graph 例如对图中这个RDF图进行转化，可以得到这样两个不同的树，上面的是用我们的方法得到的，虚线边表示反向边，显然我们的方法得到的反向边数更少。 我们的方法主要基于Edmonds’s算法，得到代价图的最小生成树，再根据它得到最终结果，该树的边权就等于最终树状表示中反向边数。 理论证明，给定条件下，我们的方法得到的树的反向边数是最少的，也就是具有最优的一致性。 James_Cameron Stanley_Kubrick Steven_Spielberg is influenced of Aliens_(film) is spouse of is producer of Titanic_(1997_film) is director of made “English” language influenced Michael_Bay Gale_Anne_Hurd BFS

RDF图的根树表示 结论 COH方法得到的树状表达的一致性最高 树状表达的一致性对用户体验有正面影响 实验也表明，我们的方法总能得到一致性最高的树状表达； 并且用户实验也说明一致性更高的树表示，得到的用户体验更好； tripleNum: 2k<90ms;4k<295ms; 1w<1.5s

实体摘要 组合优化问题 对比方法 给定长度约束下的最具特征性的摘要 描述集的特征性：被观察到的可能性尽可能小 建模：0-1背包问题 扩展条件 最大化自信息（self-Information） 建模：0-1背包问题 扩展条件 高实用性 （INFO+Utility） 低冗余（INFO+Redundancy） 逻辑冗余 文本冗余 对比方法 NAIVE：集合覆盖 RELIN [ISWC’11]：基于描述内容之间的关联性和信息量 DIVERSUM [JIIS’13] ：基于属性的多样性 关于RDF数据呈现的另一个工作是实体摘要。 一个实体通常由一系列“属性-值”对（三元组）所描述，这些“属性-值”对数量可能很多， 但在浏览、搜索应用中，需要在给定的篇幅下提供部分数据，帮助用户了解所呈现的实体，这就需要生成摘要。 除了要满足长度约束，生成的摘要要有尽可能高的区分度，我们通过最大化（所包含“属性-值”对的）自信息来体现这一要求。 这样，各条“属性-值”对是否被选入摘要的问题，可以建模为0-1背包问题。 另外我们还考虑了摘要的实用性（也就是可读性），和低冗余上的要求，逐步进行改进。 实验表明，相比于几个经典方法，我们得到摘要最接近于标准答案，并且当所有条件同时考虑时，效果最好。 self-information: si(f)=log_2(eNum/totalENum),即logp,其中p为该feature出现在一个实体描述中的概率； 实用性=可读性； INFO-U(famility weighted); INFO-R(多背包）：不允许存在冗余的描述被同时选中。 集合覆盖：选取cost最小的，不包含于任一其他实体描述中的，描述子集；每个feature对应的不含该feature的实体构成一个集合，对于多个feature，用这些集合来覆盖，除了当前实体外的所有实体构成的集合（NP-hard）。求解方法：贪心，每次选取（单位cost下，加入后能够过滤掉的实体个数）最多的feature； //一个摘要越能够将当前实体与其他所有实体区分开来，我们就认为它特征性越强，所以优化的目标就是选择，指定长度限制下，被观察到的可能性最小的描述集合。这也等价于对各条描述自信息之和的最大化。 //这样就将实体摘要问题建模为0-1背包问题进行求解。 //另外我们还考虑了摘要的实用性（也就是可读性），和低冗余上的要求，对算法进行了改进。 //最终在与其他几个经典算法的比较中，可以得出，我们的方法选出的摘要最接近于人工构建的标准答案，并且当所有条件同时考虑时，效果最好。 G. Cheng, T. Tran, and Y. Qu, ”RELIN: Relatedness and Informativeness-based Centrality for Entity Summarization,” Proc. 10th Int’l Semantic Web Conf. (ISWC ’11), pp. 114-129, Oct. 2011, doi:10.1007/978-3-642-25073-6 8. M. Sydow, M. Pikuła, and R. Schenkel, ”The Notion of Diversity in Graphical Entity Summarisation on Semantic Knowledge Graphs,” J. Intelligent Information Systems, preprint, Mar. 2013, doi:10.1007/s10844-013-0239-6.

面向RDF数据浏览的查询构建技术 NaviTree系统 有指导的SPARQL endpoint图形化查询构建系统 查询图、结果图均以树型呈现 结果集可扩展，并可向已有查询添加约束 第三个工作，研究在RDF数据浏览的场景下，如何辅助用户构建SPARQL查询。 为此，我们实现了一个原型系统。逐步提供当前可用的候选模式，帮助用户扩展性地构造SPARQL查询。 其中，查询和结果均采用缩进树的形式表示，帮助用户了解查询的结构； 另外，在结果的呈现中，用户可以进行扩展性浏览，并用扩展出的模式来更新原有查询。 //这一技术主要面临两个问题： //一是用户可能对结构化查询的使用并不熟练； //二是用户很可能对数据的模式完全不了解，从而无法适当表达自己的查询需求；

问答系统中基于RDF数据的问句理解技术 问句理解 语义解析 实体链接（Entity Linking）：确定文本短语到实体的映射关系（实体 消岐） 语义解析（Semantic Parsing）：查询意图的理解（谓词消岐） 语义解析 背景 基于bag of words的理解方式不足以反映复杂的查询需求 核心任务：将自然语言转化为逻辑形式（logical form） 使查询需求可支持自动推理or可执行 传统做法 基于特定Semantic Grammar以及标注语料 主要困难 依赖于已标记的逻辑形式语料（用于监督学习）[EMNLP’13] 根据句子本身提供的信息 How many Golden Globe awards did the husband of Katie Holmes win? (QALD-4.track3.training4) λ-calculus: count(λx. [x=GoldenGlobeAward]∧∃y.win(y,x)∧husband(KatieHolmes, y)) 在浏览的场景中，用户一般没有太明确的查询需求，而如果用户需要迅速表达明确的查询需求（并得到结果），NL是最为直接的表达方式。 这就来到了问答系统的场景。它的任务之一是对问句的理解。 这种理解包括两个方面：实体链接，和 语义解析； 这里，我们主要介绍语义解析。 语义解析的核心任务，是将NL转化为逻辑形式，从而能够支持推理甚至可以直接执行； 传统的做法主要利用特定文法和标注语料，只根据句子本身的文本和逻辑形式的对应来进行解释； 凯蒂·赫尔姆斯（美国著名电影演员） 中文：相比于英文，【zoulei 2014】 ①承担语法功能的一些结构与其词性之间没有直接关系，导致处理英文的启发式方法无法在中文中直接使用，例如，英语中谓词一般都由动词构成，而汉语里，作为谓词的可以是形容词、动词、名词。 ②中文类似WordNet的资源较少，且覆盖面小； FREE917 requires logical forms; WebQuestions: question-answer pairs， from non-experts; 传统逻辑形式 基于谓词逻辑： 一阶、高阶[AFIPS’71] 基于模糊逻辑：PRUF[JMMS’78] 基于组合语义：CCG[CLJ’00, EMNLP’10’11], DCS[ACL’11, CLJ’13] 基于λ演算：λ-DCS[arXiv’13] 标注语料：如某个logical form与某些短语相对应的映射表；

问答系统中基于RDF数据的问句理解技术 基于RDF数据的语义解析 构造查询图 提供模式层（schema）数据 提供事实（fact）数据 提供类型信息：可用于实体类型的识别 提供属性的domain、range信息：可用于动词的选择倾向判断，谓词消岐 提供事实（fact）数据 扩展性理解：利用核心实体在事实数据中的相关信息，对查询逐步扩展 同义替换：替换具有相同or相似含义的模式 以图模型表示数据 用于构造查询图 构造查询图 查询图 可作为对问句理解的图状表示：描述查询中的实体关系 易于得到可执行的SPARQL查询语句 构造方法 线性结构（自然语言）到图结构（查询图）的转化 借助句法分析（短语结构树、依存关系图） ?x Katie Holmes husbandOf win Golden Globe awards Tom Cruise 当考虑RDF数据的参与时，我们希望能够提升语义解析的效果。 首先，RDF知识库能够提供模式层数据，可以辅助对类型、和谓词的识别。 其次，RDF数据能提供大量事实数据，使得问句的理解不再局限于问句提供的文本本身，还可以借助知识库中实体的相关信息，进行扩展性理解，或者对查询进行替换性优化，（使得查询与知识库的耦合更为紧密）； 另外，RDF的图状特性，使得问句理解可看做是生成对应图模式的过程，我们之为查询图。 （用于查询RDF数据的）SPARQL查询语言也是基于图模式，因此通过构造查询图，我们可以很方便地得到可执行的SPARQL查询，（进而得到查询结果）； 查询图的构造过程，可以理解为将知识表示，从自然语言的线性结构，转化为RDF的图结构，这样一个结构转化过程，//该过程中可以借助已有的句法分析工具。 选择倾向(可用于句子结构消岐、词义推断）:例如eat的宾语倾向于食物类（有点像property的domain、range）《统》P179; 同义替换：处理句子中模式与KB中模式不同的情况； 可通过图匹配算法直接获得问题的答案

问答系统中基于RDF数据的问句理解技术 相关工作 机遇与挑战 Natural Language Question Answering over RDF—A Graph Data Driven Approach, SIGMOD 2014. 将问句理解延迟到结合KB的问题求解过程中进行 Semantic Parsing via Staged Query Graph Generation- Question Answering with Knowledge Base, ACL 2015. 将查询图分解为 核心路径+约束条件 两部分 仅考虑单核心路径的树型查询 机遇与挑战 数据不完整性、异构性 传统基于文本的NLP技术局限性 多元关系的合理表达 近年的一些工作开始体现类似的思路， 其中SIGMOD 2014年的这篇文章（邹磊，北大）将通常分为“问句理解+求解”的两步工作，借助知识库，结合为一步进行； ACL 2015年的这篇，同样将问句理解为查询图，并且将查询图分解为由“核心路径+约束条件”这两部分构成。但是其查询的复杂度有限，（只考虑了只含一条核心路径的树型查询，（对于复杂带圈的查询则尚未考虑））； 基于RDF数据的问句理解将是我未来研究的重心，相关工作中常见的问题主要来自三个方面： 一是由数据的不完整性、异构性导致的错误，对于异构性，我们可以考虑借助本体匹配来解决； 其次是由浅层NL处理带来的错误，可以考虑结合RDF数据进行改进； 另外是对于多元关系（、自然语言中介词短语）的解释，需要结合RDF数据模型，考虑更为合理的表示方式； EMNLP 2013_Semantic Parsing on Freebase from Qestion-Answer Pairs_QA_freebase_stanford_berant SIGMOD 2014_Natural Language Question Answering over RDF—A Graph Data Driven Approach_p313-zouLei.pdf (和RDF graph类似） ACL 2015_Semantic Parsing via Staged Query Graph Generation- Question Answering with Knowledge Base_microsoft_Yih Semantic Parsing on Freebase from Qestion-Answer Pairs, EMNLP 2013. 借助知识库，通过对question-answer pairs的学习 QALD

参考文献 Gong Cheng, Thanh Tran, Yuzhong Qu: RELIN: Relatedness and Informativeness-Based Centrality for Entity Summarization. International Semantic Web Conference 2011:114-129 Marcin Sydow, Mariusz Pikula, Ralf Schenkel: The notion of diversity in graphical entity summarisation on semantic knowledge graphs. J. Intell. Inf. Syst. (JIIS) 41(2):109-149 (2013) Jonathan Berant, Andrew Chou, Roy Frostig, Percy Liang: Semantic Parsing on Freebase from Question-Answer Pairs. EMNLP 2013:1533-1544 Lei Zou, Ruizhe Huang, Haixun Wang, Jeffrey Xu Yu, Wenqiang He, Dongyan Zhao: Natural language question answering over RDF: a graph data driven approach. SIGMOD 2014:313-324 Jonathan Berant, Percy Liang: Semantic Parsing via Paraphrasing. ACL 2014. Wen-tau Yih, Ming-Wei, Xiaodong He, Jianfeng Gao:Semantic Parsing via Staged Query Graph Generation- Question Answering with Knowledge Base. ACL 2015. 以上就是我的报告，这里列出了部分参考文献 EMNLP’13: microsoft; SIGMOD’14: data driven; ACL’15: core inferential chain; ACL’14: 生成logical form（λ-DCS）的权威NL；

谢谢！