数据与知识工程

教师：常亮 E-mail: 办公室电话: 2291071 手机: 13481395869,数据与知识工程,欢迎参加,本课程的开设背景,智能： 智能行为依赖于知识 知识： 是构成智能的基础 把有关信息关联在一起形成的信息结构 由信息提炼出来的产物，反映了一些基本的规律 信息： 计算学科：对描述和变换信息的算法过程进行的系统研究。 收信人事先不知道的报道 (辞海) 信息就是信息，不是物质，也不是能量 (Norbert Wiener) 数据的语义 数据： 信息的载体和表示 对于计算机而言，信息处理就是数据处理,本课程的开设背景,智能： 智能行为依赖于知识 知识： 把有关信息关联在一起形成的信息结构 由信息提炼出来的产物，反映了一些基本的规律 是构成智能的基础 信息： 数据的语义 收信人事先不知道的报道 (辞海) 信息就是信息，不是物质，也不是能量 (Norbert Wiener) 计算学科：对描述和变换信息的算法过程进行的系统研究。 数据： 信息的载体和表示 对于计算机而言，信息处理就是数据处理,本课程的开设背景,信息时代/知识时代 农业社会 工业/机械社会：由机械化、电气化和自动化带来的人类体力扩展的结果。 机械社会 信息/知识社会：由信息化、网络化和智能化带来的人类智力扩展的结果。 一个标志：万维网(Web)的普及 信息化和网络化带来的形形色色的海量信息和内容理解问题，向计算机科学和人工智能提出了艰巨的挑战。 语义Web Web技术 语义(本体/逻辑),知识表示与知识推理,数据挖掘 & 知识发现,本课程的目的,了解人工智能领域关于知识表示、知识推理、知识发现的研究历史； 掌握典型的知识表示方法（尤其是基于一阶谓词逻辑和基于描述逻辑的知识表示方法）； 掌握典型的知识推理方法（尤其是基于消解原理的推理方法和基于Tableau的推理方法）； 掌握典型的知识发现方法； 了解语义Web的基本思想、技术现状和发展趋势； 了解Web知识表示模型和语言（主要包括RDF、OWL、RIF和SPARQL）； 了解语义Web背景下关于知识表示、知识推理、和知识发现的研究现状。,本课程的内容 ,基于一阶谓词逻辑(FOL)的知识表示和推理 基于FOL的知识表示 基于消解法的知识推理 基于tableau算法的知识推理 Horn逻辑与产生式系统 Horn逻辑 逻辑程序设计 产生式系统 基于描述逻辑(DL)的知识表示和推理 基于DL的知识表示 基于tableau算法的知识推理 非单调知识表示和推理 CWA；限制逻辑；默认逻辑；自认知逻辑 对动作的表示、推理以及规划 STRIPS系统；情景演算；流演算；PDL,知识表示能力 vs. 推理能力 tradeoff,本课程的内容 ,数据挖掘与知识发现 基于证据理论的数据挖掘方法 基于神经网络的数据挖掘方法 基于遗传算法的数据挖掘方法 基于粗糙集的数据挖掘方法 其他数据挖掘方法 KDD的挖掘模式 关联模式 分类模式 聚类模式 回归模式 序列模式,本课程的内容 ,语义Web的研究路线 资源描述框架RDF Web本体语言OWL Web规则标记语言RIF Web查询语言SPARQL 典型应用 Web服务 软件配置/产品协同制造 信息系统 知识共享/协同工作 语义Web背景下知识表示、知识推理和知识发现, 教材 Brachman R, Levesque H. Knowledge Representation and Reasoning. Morgan Kaufmann Press, 2004. Antoniou G, Harmelen F. A Semantic Web Primer. Second Edition. Cambridge, Mass.: MIT Press, 2008. (Antoniou G, Harmelen F.著, 陈小平等译. 语义网基础教程(第1版). 机械工业出版社, 2008.) 胡运发. 数据与知识工程导论. 清华大学出版社, 2003. 参考书 1. Baader F, Calvanese D, McGuinness D, Nardi D, and Patel-Schneider P. F. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, 2003. 2. Bell J. L., Machover M. A Course in Mathematical Logic. North-Holland Publishing Company, 1977. 3. Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techinques. Second Edition. 机械工业出版社, 2007.,教材及参考书,作者介绍,Ron Brachman Ph.D, 1977 Harvard ACM Fellow President of AAAI (2003) 雅虎全球研究运营副总裁 Hector Levesque Ph.D 1981, University of Toronto Conference Chair of IJCAI (2001) founder farthers of DL Franz Baader Chair for Automata Theory of the Institute for Theoretical Computer Science Faculty of Computer Science at TU Dresden,课程要求,按时到课，重视课堂学习； 对布置的思考题和讨论题进行认真准备； 按进度完成平时作业。 评分方式： 总评成绩 = 平时成绩20 期末考试成绩80 平时成绩 = 课堂主题报告 课堂讨论 重视课堂讨论 使自己的疑问得到及时解答 可以帮助有相似疑问的同学 可以使教师及时了解教学效果 在讨论中产生有价值的学术火花 多动笔；到证明的第一现场去,第1部分 概述,主要内容： 人工智能及其三个学派 符号主义 本领域的杰出人物 本领域的顶级国际会议 知识表示与知识推理 数据挖掘与知识发现,图灵和图灵测试,阿兰麦席森图灵(Alan Mathison Turing) 1912.6.23-1954.6.7 英国数学家、逻辑学家 1936年： On Computable Numbers, with an Application to the Entscheidungs problem (论可计算数及其在判定问题上的应用) 图灵机 (Turing Machine) 停机问题 vs. FOL的不可判定问题 1950年： Computing Machinery and Intelligence (计算机器与智能) 图灵测试 (Turing Test) 人工智能之父,人工智能的诞生,Dartmouth会议： 1956年，美国的Dartmouth College，一个长达2个月的暑期研讨班。 与会者有包括C.Shannon在内的数学家、逻辑学家、认知学家、心理学家、神经生理学家、计算机科学家等10人。 Marvin Minsky的神经网络模拟器、John McCarthy的搜索法、以及Herbert Simon和Allen Newell的“逻辑理论家”成为会上的3个亮点，分别讨论如何穿过迷宫、如何搜索推理、以及如何证明数学定理。 在会议上，John McCarthy正式提出“人工智能” (Artificial Intelligence)这一术语。 人工智能是相对人的自然智能而言，即用人工的方法和技术,模仿、延伸和扩展人的智能，研制具有感知、推理、学习、联想、决策等思维活动的计算系统，解决需要人类专家才能处理的复杂问题。,人工智能的发展,1958年，Newell和Simon的四个预测 十年内，计算机将成为世界象棋冠军 十年内，计算机将发现或证明有意义的数学定理 十年内，计算机将能谱写优美的乐曲 十年内，计算机将能实现大多数的心理学理论 1959年，MIT AI Lab正式成立（Minsky和McCarthy） 在专家系统、机器人、自然语言处理、知识工程等领域取得了长足的发展。 1981年，日本政府宣布日本五代机（first-generation computer）计划（即智能计算机）。 1992年，日本政府宣布五代机计划失败。人工智能进入一个低谷。 随着信息/知识社会的到来，人工智能领域再次兴旺起来。,Gartner 技术成熟度曲线,“深蓝”与卡斯帕罗夫之战,1997年5月初，IBM公司研制的并行计算机“深蓝”与国际象棋冠军卡斯帕罗夫交战，以两胜一负三平获胜。 “深蓝”：由256个专为国际象棋比赛设计的微处理器组成，每秒可计算2亿步棋。,另一场人机大战,1997年，“深蓝”在棋盘上击败国际象棋大师卡斯帕罗夫，本质是使用穷举战略： 每秒计算2亿次可能的“招数”， 在相同的时间内，卡斯帕罗夫只能粗略地计划两步。 在其后的10年里，计算能力猛增：到2007年，那台1.4吨的巨型计算机的处理能力已经可以放进一个大拇指盖大小的“细胞（Cell）”微处理器中。 在这十年内，晶体管数量已经从英特尔奔腾上的750万个跳跃到“细胞”上的2.34亿个。 但是要让计算机理解人类语言、像人类一样思考比下棋难多了。 更高级别的挑战？,“沃森”参战“危险边缘(Jeopardy!)”,“危险边缘(Jeopardy!)”：美国家喻户晓的电视智力竞赛节目。1964年创立，竞赛问题涉及地理、政治、历史、体育、娱乐等。 2011年2月1416日，IBM 沃森参加了“危险边缘”电视节目的竞赛，战胜了该节目有史以来最优秀的两位人类冠军Ken Jennings和Brad Rutter。,IBM“沃森”系统,以IBM创始人托马斯J沃森的名字命名。 2006年开始设计。 是由90台IBM 750服务器组成的群集系统，每台服务器采用Power 7处理器（8核芯片，每核4个线程），相当于有2880个核在运行。 内存是16TB的RAM。 采用的软件有SUSE Linux Enterprise Server 11操作系统、IBM DeepQA软件、Apache UIMA（ 非结构化信息管理体系结构） 框架等。,IBM“沃森”系统,使用了上百种的技术来分析自然语言、识别资源、寻找并产生假设、寻找证据并评分、对假设进行聚集和分级，因此它是专门设计的、具有学习能力的机器。 能储存大量信息，相当于100万本书籍和2亿页资料。 还可以从经验中学习如何提高性能； 能使用自然语言回答问题。 世界各地的研究人员历时四年共同完成了这个系统。 应用前景广泛，可以高速分析大量数据，用来帮助政府部门解答公众疑问，帮助医生评估药物疗效。 核心技术：自然语言处理、机器学习,Leslie Gabriel Valiant (1949-),2010年图灵奖获得者 英国皇家学会会员/美国科学院院士 哈佛大学教授 主要贡献： 机器学习领域：提出PAC模型 使20世纪50年代诞生的机器学习领域第一次有了坚实的数学基础，从而清除了学科发展的障碍， 这不仅对人工智能学科领域产生了巨大影响，而且促使IBM公司制造出沃森（Watson）这样智能而神奇的机器。 计算复杂性领域：表明即使可满足赋值数很小，SAT这个NP完备问题仍然是很难的问题。 计算神经学领域：为大脑设计了一个数学模型，并将它与复杂的认知功能建立了关联。,人工智能的不同学派,符号主义 连接主义 行为主义,符号主义（symbolism）,又称为逻辑主义、心理学派、计算机学派 以Newell和 Simon提出的物理符号系统假说（physical symbol system hypothesis）为基础。 符号主义认为： 人的认知基元是符号，认知过程就是符号操作过程； 人是一个物理符号系统，计算机也是一个物理符号系统，因此就能够用计算机来模拟人的智能行为，即用计算机的符号操作来模拟人的认知过程。 知识是信息的一种形式，是构成智能的基础；人工智能的核心问题是知识表示、知识推理和知识运用。知识可以用符号表示，也可以用符号进行推理，因而可能建立起基于知识的人类智能和机器智能的统一理论体系。 符号主义曾长期一支独秀，为人工智能的发展作出了重要贡献。在其他学派出现之后，符号主义仍然是人工智能的主流学派。,连接主义/联结主义(connectionism),又称为仿生学派、生理学派 其原理主要是神经网络以及神经网络间的连接机制和学习算法。 连接主义认为：人工智能源于仿生学，特别是人脑模型的研究。认为思维的基元是神经元；把智能理解为相互联结的神经元竞争与协作的结果。 连接主义研究非程序的、适应性的、大脑风格的信息处理的本质和能力。人们也称它为神经计算。 20世纪60-70年代，以感知机为代表的脑模型的研究。 1986年，Rumelhart等提出多层网络中的反向传播算法（BP算法）；此后，连接主义势头大振。 近年来迅速发展；大量的神经网络的机理、模型、 算法不断地涌现出来。,行为主义(actionism),又称为进化主义、控制论学派 其原理为控制论以及感知-动作型控制模型。 行为主义强调智能系统与环境的交互，从运行的环境中获取信息（感知），通过自己的动作对环境施加影响。 行为主义认为：智能只能在与环境的交互作用中表现出来。认为智能不需要知识、不需要表示、不需要推理。,弱AI vs.强AI,美国哲学家约翰西尔勒（J.R.Searle）根据人们在研究人工智能模拟人类认知能力方面的不同观点，将有关人工智能的研究划分为强人工智能（Strong Artificial Intelligence，简称强AI）和弱人工智能（Soft Artificial Intelligence，简称弱AI）两个派别。 人工草皮 & 人工调料 在研究意识方面， 弱AI认为计算机的主要价值在于它为我们提供了一个强大的工具； 强AI的观点则是，计算机不仅是一个工具，形式化的计算机是具有意识的。 1980年，西尔勒设计了一个“中文屋子(Chinese Room)”的假想试验来反驳强AI的观点。,智能科学: 脑科学+认知科学+人工智能+,人脑是巨系统 神经元: 胞体、突起(树突,轴突),智能科学: 脑科学+认知科学+人工智能+,人脑是巨系统 神经元: 胞体、突起(树突,轴突) 整个人脑神经元的数量约为1011 (千亿) 一只成年老鼠的脑由2100万个称为神经元 在大脑皮层的一个神经元上, 突触的数目可达3万以上。整个脑内突触的数目约在1014-1015(百万亿千万亿)之间。,智能科学: 脑科学+认知科学+人工智能+,2011年8月18日，美国IBM公司，可以模拟人脑处理信息方式的认知计算机芯片。 已研发出两个芯片； 没有任何生物成分，完全由硅电路组成； 每个都含有256个“神经元”， 其中一块有超过26万个可控制的“神经突触”，另一块有6万多个学习型“神经突触”。 在这两块芯片的基础上，研究人员成功让计算机实现导航、机器视觉、模式识别、联系记忆及分类等功能。 研究人员的长期目标是建立一个有100亿个“神经元”和100万亿个“神经突触”的芯片系统，容量不超过两升，每小时耗电只有1度。 最终建立在这种芯片上的计算机，将可以从经验中学习，找到联系，建立假设，模拟人脑的结构及弹性功能。,本领域的杰出人物,目前为止共56名图灵奖获得者(1966-1999:40名,2000-2009:16名) Marvin Minsky（1969年） 框架理论的创立者 世界上最早的能模拟人的活动的机器人Robot C John Mccarthy（1971年） Lisp语言 限制逻辑 情景演算,本领域的杰出人物,Herbert Simon和Allen Newell（1975年） 符号主义学派的创始人 (物理符号系统假说) 开发了世界上最早的启发式程序“逻辑理论家”，应用其证明了数学名著数学原理一书第二章52个定理中的38个定理 开发了最早的下棋程序之一MATER (Simon)发展和完善了语义网络 Edward Feigenbaum和Raj Reddy（1994年） 大规模人工智能系统的设计和实现的先驱 合力开发了第一个专家系统DENDRAL (Feigenbaum)专家系统之父 (1977年) (Raj Reddy) John McCarthy指导的 第一个博士；李开复的博士生导师(CMU),本领域的传奇人物,Herbert Simon 1975年图灵奖获得者 符号主义学派的创始人 建立了机器证明数学定理的启发式搜索法 提出有限理论对经济决策活动的影响 1978年诺贝尔经济学奖获得者 1943年在匹兹堡大学获得政治学博士学位 1969年由于在心理学上的贡献而获得美国心理学会的“杰出科学贡献奖” 1986年因为在行为科学上的出色贡献而荣获美国全国科学奖章,本领域杰出的中国学者,吴文俊 几何定理自动证明领域的突破 “吴方法”在国际机器证明领域产生了巨大影响，当前国际流行的主要符号计算软件都实现了吴文俊教授的算法 获得首届国家自然科学一等奖(1956) Herbrand自动推理杰出成就奖(1997) 首届国家最高科学技术奖(2000) 吴文俊之路,本领域的顶级会议,IJCAI International Joint Conference on Artificial Intelligence 1969年召开第一届；每两年开一次 AAAI AAAI Conference on Artificial Intelligence AAAI: American Association for Artificial Intelligence(1979年成立)， 2007年改名为Association for the Advancement of Artificial Intelligence 1980年召开第一届；每年开一次 KR International Conference on Principles and Knowledge Representation and Reasoning 1989年召开第一届；每两年开一次,本领域的顶级会议,WWW International Conference on World Wide Web 1994年召开第一届；每年开一次 ISWC International Semantic Web Conference 2002年召开第一届；每年开一次,本领域的顶级会议,SIGMOD ACM SIGMOD Conference on Management of Data SIGKDD ACM SIGKDD Conference on Knowledge Discovery and Data Mining ICDE IEEE International Conference on Data Engineering ICDM IEEE International Conference on Data Mining,本领域的顶级会议,SIGKDD ACM SIGKDD Conference on Knowledge Discovery and Data Mining 1995年召开第一届；每年开一次 ICDM IEEE International Conference on Data Mining 2001年召开第一届；每年开一次,CCF推荐的国际学术会议和期刊目录, 计算机体系结构与高性能计算、计算机网络、网络与信息安全、计算机科学理论、软件工程/系统软件/程序设计语言、数据库/数据挖掘/内容检索、计算机图形学与多媒体、人工智能与模式识别、交叉学科、综合类。 分为A、B、C三档。 A类：国际上极少数的顶级刊物和会议，鼓励我国学者去突破； B类：国际上著名和非常重要的会议、刊物，代表该领域的较高水平，鼓励国内同行投稿； C类：国际上重要的、为国际学术界所认可的会议和刊物。,知识表示和推理,“知识是信息的一种形式，是构成智能的基础；人工智能的核心问题是知识表示、知识推理和知识运用。” 智能行为的基础是知识。 人类的智能行为对于知识的依赖主要表现在对于知识的利用，即利用已经具有的知识进行分析、猜测、判断、预测等等。人类利用知识可以预测未来，由已知的情况推测未知的情况、由发生的事件预测还未发生的事件等等。 当人们希望计算机具有智能行为时，除了告诉计算机如何像人一样地利用知识以外（对于知识进行推理），一个更为基础和先行的工作是如何使计算机具有知识（对于知识进行表示），即在计算机上如何表达人类的知识。,常用的知识表示方法,基于逻辑的形式系统 基于命题逻辑 基于一阶谓词逻辑 基于模态逻辑 基于时序逻辑 基于动态逻辑 基于模糊逻辑 基于描述逻辑 等等 非逻辑的表示系统 状态空间表示法 语义网络 框架 脚本 ,涉及到知识表示和推理的研究领域,智能搜索引擎 专家系统 机器翻译和自然语言理解 数据挖掘和知识发现 智能控制 计算机视觉和图像处理 虚拟人 / 仿生感知 / 人工生命 智能主体 智能诊断 自动规划 ,数据挖掘与知识发现,目的：从海量数据中找出有用的知识。 大体上看，数据挖掘可以视为机器学习和数据库的交叉； 利用机器学习界提供的技术来分析海量数据， 利用数据库界提供的技术来管理海量数据。,Thanks！,Question!,下回预告,基于一阶谓词逻辑的知识表示和推理 命题逻辑：语法、语义 FOL：语法、语义 （Ch2） 基于FOL的知识表示 （Ch3） 基于消解法的推理（包括命题逻辑推理和FOL推理） （Ch4） 基于tableau的命题逻辑推理 基于tableau的FOL推理,