0Rapporteurs before defense:0Thomas Schiex Research director at INRIA MIAT0Audine Subias Lecturer at LAAS-CNRS0Composition of the Jury: President: Céline Rouveirol Professor of universities at LIPN0Examiner: Benoit Delahaye Lecturer at LS2N0Invited member: Jean-Lou Farges Engineer at ONERA0Thesis supervisor: Philippe Leray Professor of universities at LS2N0Thesis supervisor: Romain Kervarc Engineer at ONERABehaviour Recognitionon Noisy Data-streams Constrainedby Complex Prior KnowledgeJury0T hesis0in order to obtain the degree of0Doctor of the University ofNantes in computer science0prepared at the National Office for AerospaceStudies and Research0under the doctoral school Mathematicsand Information and CommunicationTechnologies0presented and publiclydefended by Romain R incé0November 7, 20180Céline R ouveirol Professor of universities President of the Jury0Thomas S chiex Research director Reviewer0Audine S ubias Lecturer Reviewer0Benoit D elahaye Lecturer Examiner0Jean-Lou F arges Engineer ONERA Invited member0Philippe L eray Professor of universities Thesis director0Romain K ervarc Doctor engineer ONERA Supervisor0It is better to mobilize one's intelligence on bullshit0than to mobilize one's bullshit on intelligent things.0Shadok proverb50Acknowledgments0Although this thesis is the culmination of three years of personal work, its0achievement would not have been possible without the technical and scientific assistance of many individuals-0ness and the moral support of those around me during this whole period.0If the smooth running of a thesis is influenced by many factors, it is undeniable0that supervisors play a preponderant role in it. In this respect, I can only thank my0thesis director, Philippe L eray , for his availability and responsiveness to all my questions0as well as my supervisor at ONERA, Romain K ervarc , for his listening, understanding0and the corrections of articles oozing with red. Together, I would like to thank them for0the trust and great freedom they have given me throughout my work. Thank you for0giving me the opportunity to initiate a thesis and for accompanying me to its conclusion.0I would also like to thank the members of my thesis monitoring committee: Céline R ou -0veirol , who was also the president of my jury, and Karim T abia . Although I did not have the chance0to exchange with them than episodically, they have been, on each occasion, a source of encouragement0and advice. The last chapter of this thesis would undoubtedly not have existed without them.0I would like to express my gratitude to the other members of my defense jury: Jean-0Lou F arges , who agreed to be part of it and who followed most of my work, Benoit0D elahaye , who also took the time to reread and comment on my manuscript, and more parti-0particularly Thomas S chiex and Audine S ubias who agreed to be the reviewers0我要向他们花费的时间致以敬意，他们阅读了我的论文并提供了大量的评论。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0我要真诚地感谢MIDL团队的成员们将我纳入他们的团队。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0我要对Stéphanie Lala表示衷心的感谢，她花时间审阅和评论我的论文，但更重要的是她的善良和关心。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0我要对Stéphanie Lala表示衷心的感谢，她花时间审阅和评论我的论文，但更重要的是她的善良和关心。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。60我对Stéphanie Lala对我的研究课题给予的支持表示衷心的感谢。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0她对我非常友善，给予了我很大的帮助。尽管她没有直接参与我的研究，但她对我非常友善。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0他们总是心情愉快和理解，工作效率高。0我要特别感谢MichaëlLienhardt，尽管他来得很晚，但他给予了我很大的帮助。0没有提到的人。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0游戏之夜、逃生游戏、星期五下午疲惫的咖啡休息，或者...0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0保持我的良好心态。我向那些我没有提到的人表示歉意。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0无论它们是短暂的还是长久的。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0F layac，尽管他总是在“找麻烦”，但经常来参观。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0他有时候会在他兄弟的两个生日之间抽空来ONERA。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0来自他们隔壁办公室的噪音，以及我们之间的许多严肃和愉快的讨论，无论它们是短暂的还是长久的。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0他们在背后默默无闻的态度下展现出的聪明才智和尖锐精神，我很荣幸能够与他们一起工作。0最后，我想向那些在这个过程中给予我支持的人们致以感谢。尽管他们的存在并不明显，但他们的...0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0这个项目的提前结束。0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0这个特殊的合作办公室和坚定的支持。我们在科学、技术和生活的各个方面的交流时刻都是如此...0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0这项工作可能带来的沮丧情绪。虽然我们的争吵是史诗般的，但它们并没有...0我要特别感谢Michaël Lienhardt，尽管他来得很晚，但他给予了我很大的帮助。0我还要感谢Georgia E ffgen S antos，尽管与他们的距离相距甚远，却带来了一些沮丧的情绪。虽然我们的争吵是史诗般的，但它们并没有...0在这段时间里，尽管我们之间有超过8000公里的距离，她是我生活中最亲近的人之一。0多年来，她一直支持着我，帮助我度过了这段时间。0在我一直讨厌的城市里，她对我的支持是不可否认的。毫无疑问，如果没有她，这篇论文将不会70除了抑郁之外，我对她非常感激，尽管无法弥补她给予我的一切，我希望她知道她将永远0永远感激她。虽然我永远无法弥补她给予我的一切，但我希望她知道她将永远在我心中。0我和我的家人热烈欢迎她。0最后，我认为自然而然地感谢我的父母Anabel和Manuel，0在各个方面，比这几个简单的字更长时间地支持着我。0这几年的博士学位。我不希望这些简单的话语成为我的感谢的结束语。0由于它们可能具有的令人难以置信的平凡性，它们的价值被低估，如果我只能提到两个0如果有人需要感谢，那只能是他们。我欠他们一切，我爱他们。91.1Main goals of Complex Event Processing . . . . . . . . . . . . . . . . . .181.1.2Interesting properties of CEP systems . . . . . . . . . . . . . . . .201.2.1Event calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.2.2SASE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231.2.3TESLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271.3Drone model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331.3.2Problem model: telecommand and radio losses . . . . . . . . . .352.1Understanding uncertainty on Complex Event Processing . . . . . . . .422.1.2Pattern uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . .44ing under uncertainty . . . . . . . . . . . . . . . . . . . . . . . . .462.2.1Event calculus using Markov Logic Networks . . . . . . . . . . .482.2.3Ad-hoc approaches . . . . . . . . . . . . . . . . . . . . . . . . . . .532.3Bayesian network approaches . . . . . . . . . . . . . . . . . . . . . . . . .560目录0引言 1301 复杂事件处理简介 1701.1.1 语义学 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1801.2 关于复杂事件处理的简要现状 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2101.2.4 ONERA编年史 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2901.3.1 无人机飞行过程中三个代理之间的通信丢失 3402 复杂事件处理中的不确定性 4102.1.1 数据不确定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4202.1.3 对复杂事件处理目标和概念的理解-02.2 Markov逻辑方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4802.2.2 区间方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 5102.2.4 Markov逻辑网络方法总结 . . . . . . . . . . . . . . . . . . . . . . . . . . . 542.4Automaton-based methods. . . . . . . . . . . . . . . . . . . . . . . . . .602.4.2Automaton-based representations from Albanese et al. and its2.4.3Automaton-based representation from Fazzinga et al. and its ex-tensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .662.5Other approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .682.5.1ProbLog method . . . . . . . . . . . . . . . . . . . . . . . . . . . .692.5.2HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .692.5.3Petri-net approaches . . . . . . . . . . . . . . . . . . . . . . . . . .712.5.4Grammar approaches. . . . . . . . . . . . . . . . . . . . . . . . .722.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .753Background773.1Markov Logic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . .783.1.1Markov network . . . . . . . . . . . . . . . . . . . . . . . . . . . .783.1.2Markov Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .793.1.3Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .813.1.3.1MAP inference . . . . . . . . . . . . . . . . . . . . . . . .813.1.3.2Conditional inference . . . . . . . . . . . . . . . . . . . .833.2ProbLog. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .863.3Non-homogeneous Markov models. . . . . . . . . . . . . . . . . . . . .903.3.1Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .903.3.2Construction of the NHM . . . . . . . . . . . . . . . . . . . . . . .914Chronicle representation with uncertainty using Markov logic networks934.1Chronicles expressed with logical rules . . . . . . . . . . . . . . . . . . .944.1.1Chronicle semantic in Markov logic . . . . . . . . . . . . . . . . .954.1.2Data stream structure and LLEs dependencies . . . . . . . . . . .964.1.3Chronicle rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . .974.1.4Operator rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . .984.1.5Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1014.2Specific logical structures leading to intractable problems for WalkSAT1024.2.1A first example of unexpected behaviour with MC-SAT inference 1024.2.2WalkSAT efficiency analysis on specific problems . . . . . . . . .1044.3Consequences of WalkSAT inference on the chronicle model for MLNs .1154.4Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .117010 目录02.4.1 SASE方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 610扩展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Contents115Exact computation of uncertainty for chronicles using ProbLog1195.1Difference in semantic interpretation with Markov logic networks. . .1205.2A chronicle representation with ProbLog . . . . . . . . . . . . . . . . . .1235.2.1Event uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . .1235.2.2Chronicle representation . . . . . . . . . . . . . . . . . . . . . . . .1245.2.3Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1265.3Instantiation of models under uncertainty using the ProbLog chroniclemodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1265.3.1The hurricane model . . . . . . . . . . . . . . . . . . . . . . . . . .1275.3.2The drone model . . . . . . . . . . . . . . . . . . . . . . . . . . . .1305.4Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1326Chronicle inference on complex systems using Markov chains and automata 1336.1Uncertainty estimation using Markov chains . . . . . . . . . . . . . . . .1346.1.1Initial approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1346.1.2Application on a toy example . . . . . . . . . . . . . . . . . . . . .1356.1.3Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1386.2Expressing high-level constraints using chronicles . . . . . . . . . . . . .1396.2.1Evidence behaviours expressed as sub-streams. . . . . . . . . .1406.2.2Graph representations of constraint sub-streams . . . . . . . . . .1426.2.3Sampling using constraint graphs . . . . . . . . . . . . . . . . . .1446.2.4Finding the set of constraint sub-graphs for a chronicle . . . . . .1456.2.5Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1476.3Speeding up inference computation . . . . . . . . . . . . . . . . . . . . .1486.3.1Precisions about the chronicle representation . . . . . . . . . . . .1486.3.2Model-checking approach for chronicle inference . . . . . . . . .1496.3.3Fast computation of the automaton of a chronicle evidence . . .1516.4Probability Estimation of a Behaviour of the Drone Model . . . . . . . .1516.4.1Drone model to NHM . . . . . . . . . . . . . . . . . . . . . . . . .1516.4.2Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . .1536.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .156Conclusion159A Definition of chronicle with the Markov logic semantic163A.1 Binary operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .164A.2 Unary operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16412ContentsBDrone model in ProbLog167B.1Temporal part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .167B.2Subsystems part: Exemple from the RPS system . . . . . . . . . . . . . .168B.3Uncertainty part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .174Bibliography177Acronyms190List of Tables191List of Figures19313IntroductionSince the rise of the Information Age, the number of communication ex-change in the world increased continuously, and exploded with mas-sive computerisation and the expansion of Internet. Data is flourishingthrough every aspect of our society. More than 200 000 SMS are sent every second,administration procedure are replaced by HTML forms, fast-trading is supplantingany trader, more than 100 000 planes take off every day, data centers use more than 5%of the worldwide consumption. Data is everywhere, but data is chaotic. Produced bybillions of agents continuously, understanding and extracting sense from this data isa necessity for efficiency and security reasons. For instance, cyberattacks are a serious0对企业或国家来说是一个关注的问题，但很难被检测到，需要检测0在大量数据中发现复杂模式。0数据分析是一个广泛的领域，涵盖了许多方法和概念。神经网络0例如，神经网络在识别数据之间的关系和生成推理方面非常高效。0从中推导出结论，但缺乏解释其决策的技术。在0相比之下，复杂事件处理（CEP）是一个试图识别行为的领域0使用逻辑模型描述它们的数据。大多数情况下，数据是有组织的。0时间上和行为上的描述具有特定的小可观察活动的组织。0活动命名为事件。这个数据分析领域得到了很好的覆盖，但通常不会0不考虑系统上收集的数据可能是错误的、缺失的或损坏的。0不幸的是，错误的数据可能对识别0通过在数据上缺失它们的出现或检测到虚假行为来检测行为。0可能是不可取或危险的。例如，未能检测到入侵0对公司的计算机系统进行攻击可能导致信息被盗。同样，0检测到不存在的行为可能会激活对抗措施0可能会导致严重后果。例如，在0战争情况可能导致不合理的报复措施。014 内容0本论文发生在这种数据不完全可靠但仍然0有必要对其进行分析以确定特定的行为。此外，本论文旨在0扩展特定的CEP表示，称为编年史[Pie14]，以使其对0不确定性。关于CEP中数据不确定性的文献可能会关注两个不同的方面。0第一种方法考虑数据值的不确定性，而第二种方法考虑0考虑数据中的信息存在。例如，假设一个雷达0检测到一辆车以高速通过，第一种方法将考虑车速的不确定性0第一种方法将关注车速的值，而第二种方法将关注确定0如果一辆车确实通过了。这两个方面通常分别称为0属性和事件的不确定性可能是相关的，但不一定是。在这篇论文中，0我们关注事件的不确定性，因为编年史表示的一个主要方面是0关注事件之间的相对位置，这意味着这些事件的存在0事件对于使用编年史识别行为是一个重要的要求。0对于这项工作，我们的目标是为编年史系统提供一个扩展，允许0不确定性表示和识别的估计，关于提供的数据0三个属性作为目标：0可扩展性 该扩展应该能够应用于可能的现实场景0可能在数据上提供大量事件，具有现实的编年史0识别。最理想的情况是，不确定性计算应该在线进行。0计算的精度。该扩展应该断言编年史识别0概率在模型上是正确的，或者至少能够选择0评估的精度。0高级先验信息 通常，数据（事件）中提供的信息是0相对较低级别的信息足够容易识别和捕捉。这个信息0这个信息必然会影响chronicle识别的概率计算0然而，在推理之前，能够定义规则是有用的0应该被断言的事实。例如，可能可以知道已知的0数据生产过程中发生的行为，但不一定需要0但不一定知道它发生的确切时间。0第一章的第一部分是对CEP的简要介绍，以及其特点和行为0目标，并同时介绍了社区使用的共同词汇。0第二部分介绍了一些CEP表示，这些表示被选择为其对不确定性的扩展0除了我们打算扩展的chronicle模型之外的不确定性的主要0介绍了本论文中使用的无人机模型的案例研究tably a model-checking approach for chronicle inference. Finally, last part details theapplication of this method to the drone model and discusses the issues remaining withsuch method.0目录 150第二章介绍了CEP中的不确定性的主要概念，并介绍了不同方面和常见表示0介绍了文献中出现的不确定性的不同方面和常见表示。0然后详细介绍了关于不同类型方法的现状，如马尔可夫逻辑网络（MLN）0逻辑网络（MLN）、贝叶斯网络或基于自动机的方法。0第三章介绍了用于不同方法和工具的不同方法和工具0本工作中不确定性表示的不同方法和方法。0第四章介绍了chronicle表示的第一次实验0第一部分是基于MLNs的不确定性的chronicle表示。0马尔可夫逻辑语义以及不确定性表示。第二部分0第二部分讨论了推理中获得的结果不一致性，并调查了0关于导致这些结果的可能解释的讨论。特别是一组实验0在WalkSAT算法上进行了一系列实验，该算法是用于0使用MLNs进行推理，以评估其在与我们相关的特定问题上的效率0chronicle表示的核心算法。0第五章介绍了解决chronicle数据不确定性的第二种方法0由于MLNs使用基于随机局部搜索的方法提供可满足的解决方案0基于穷举搜索的方法来解决一阶逻辑（FOL）问题的不确定性表示0用于SAT问题的方法。这种方法需要使用特定的表示，如二进制0决策图（BDDs）来解决问题。从逻辑问题到一阶逻辑（FOL）问题的转换0使用ProbLog对这种表示进行了问题转换。本章的最后一部分0将该表示应用于无人机模型0最后，第六章在第一部分介绍了一种基于原创的特殊方法0使用非齐次马尔可夫模型（NHMs）的马尔可夫链蒙特卡罗（MCMC）0解决可能出现的ProbLog可扩展性问题。该方法将0计算chronicle识别概率的不确定性模型0将数据作为表示系统的马尔可夫模型的约束0第三部分详细介绍了如何使用chronicle表达高级约束0通过将chronicles转换为约束子图来获取先验知识。0第三部分介绍了加速计算的方法扩展，以及17CHAPTER1Complex event processing in thenutshellContents1.1Main goals of Complex Event Processing. . . . . . . . . . . . . . . .1
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
