精华内容
下载资源
问答
  • 2021-04-13 12:37:49

    谁能告诉我这科的理论在哪可以实用呀?搞不懂,只能收藏一下包不挂科

    知识点总结

    第一章:

    软件工程定义

    1968年10月,Fritz Bauer 首次提出了“软件工程”的概念,并将“软件工程”定义为:为了经济地获得能够在实际机器上有效运行的可靠软件,而建立并使用的一系列工程化原则。

    1993年IEEE对软件工程的定义:软件工程是将系统化的、规范化的、可度量的途径应用于软件的开发、运行和维护的过程,即将工程化应用于软件的方法的研究。

    软件工程原则:

    抽象与自顶向下,逐层细化  信息隐蔽和数据封装 模块化 局部化 确定性 一致性和标准化 完备性和可验证性

    瀑布模型:

    开发活动的特征:(1)以上一项活动方产生的工作对象为输入(2)利用这一输入,实施本项活动应完成的内容(3)给出该项活动的工作结果,作为输出传给下一项活动(4)对实施该项活动的工作结果进行评审,若其工作得到确认,则继续进行下一项活动,否则返回前项,甚至更前项的活动进行返工

    瀑布模型的优点:

    (1)可强迫开发人员采用规范化的方法

    (2)严格地规定了每个阶段必须提交的文档

    瀑布模型的缺点

    (1)由于瀑布模型几乎完全依赖于书面的规格说明,很可能导致最终开发出的软件产品不能真正满足用户的需要。如果需求规格说明与用户需求之间有差异,就会发生这种情况(2)瀑布模型只适用于项目开始时需求已确定的情况。总地来说,瀑布模型是一种应付需求变化能力较弱的开发模型,因此,很多在该模型基础上开发出来的软件产品不能够真正满足用户需求

    第二章:

    可行性研究的过程:

    1. 复查系统规模和目标

    复查系统定义,改正含糊或不确切的叙述,清晰地描述对目标系统的一切限制和约束

    1. 研究目前正在使用的系统

    现有的系统是信息的重要来源。若一个软件是对旧系统的改造,那开发新系统时,要充分了解老系统存在的问题,需要增加的功能,新系统实际上是老系统的部分功能加上一些新增功能形成的系统

    1. 导出新系统的高层逻辑模型
    2. 重新定义问题

    新系统的逻辑模型实质上表达了分析员对系统必须做什么的看法,得到新系统的高层逻辑模型之后,可能会发现前面问题定义的范畴过大,分析员还要和用户一起再复查问题定义,对问题进行重新定义和修正。

    1. 导出和评价供选择的解法

    分析员应该从系统逻辑模型出发,研究问题的几个组成部分,细化各功能点,导出若干个较高层次的物理解法供比较和选择

    1. 推荐行动方针
    2. 草拟开发计划

    任务分解 进度规划 财务预算 风险分析及对策

    1. 书写文档提交复查

    第三章:

    一.软件需求的定义:

    以清晰、简单、一致且无二义性的方式,描述用户对目标软件系统在功能、行为、性能、设计约束等方面的期望,是在开发过程中对软件系统的约束。

    二.需求分析的任务

    1. 业务需求:是客户对于软件系统的高层次目标要求,定义了项目的远景和范围
    2. 用户需求:从用户角度描述软件系统的功能需求与非功能需求,通常只涉及系统的外部行为。
    3. 功能需求:功能需求描述软件系统应该提供的功能或务,通常涉及用户或其他外部系统与目标系统之间的交互,不考虑目标系统内部的实现细节
    4. 非功能需求:非功能需求即性能需求,反映了客户对软件系统质量和性能的额外要求
    5. 约束条件: 约束条件是软件系统设计和实现时必须满足的限制条件
    6. 业务规则: 业务规则是对某些功能的可执行性成内部执行速制的一些限定条件
    7. 外部接口需求:    外部接口需求是描述目标系统与外部环境之间的交互接口
    8. 数据定义:当用户描达一个数据项或一个复杂的业务数据结构的格式或缺省值时,正在进行数据定义

    第四章:

    启发规则

    启发规则是软件结构设计优化准则,软件概要设计的任务就是软件结构的设计,为了提高设计的质量,必须根据软件设计原理设计软件,利用启发规则优化软件结构。

    1.改进软件结构提高模块独立性2.模块规模适中3.适当控制深度、宽度、扇出、扇入

    4.模块的作用域应该在控制域之内5.力争降低模块接口的复杂程度

    6.设计单入口单出口的模块7.模块功能可预测

    第五章:

    详细设计的过程

    软作详细设计是软件工程的重要阶段,在详细设计过程中,细化了高层的体系结构设计,将软件结构中的主要部件划分为能独立编码、编译和测试的软件单元,并进行软件单元的设计,同时确定了软件单元和单元之间的外部接口。

    一.详细设计的基本任务

    1. 算法设计:用某种图形、表格、语言等工具将每个模块处理过程的详细算法描述出来
    2. 数据结构设计:对于需求分析,概要设计确定的概念性的数据类型进行确切的定义
    3. 物理设计: 对数据库进行物理设计,即确定数据库的物理结构
    4. 其他设计

    a.代码设计:为了提高数据的输入、分类、存储及检索等操作的效率,对数据库中的某些数据项的值要进行代码设计b.输入/输出格式设计c.人机对话设计

    1. 编写详细设计说明书  6 . 评审:对处理过程的算法和数据库的物理结构要进行评审

    .详细设计方法:

    1. 自顶向下,逐步求精  2.具有单入、单出的控制结构 3. 五种控制结构:顺序结构,选择,先判断型循环结构,后断型循环结构,多选择分支结构

    第七章:

    一.测试用例设计:

    白盒测试是对软件的过程细节做细致的检查。这一方法把测试对象看作 个打开的盒子,允许测试人员利用程序内部的逻辑结构及有关信息设计或选择测试用例,对程序所有逻辑路径进行测试。通过在不同点检查程序的状态,确定实际的状态是否与期望的状态一致。

    覆盖标准

    1. 语句覆盖

    含义:就是选择足够多的测试用例,运行被测程序,使得程序中每条语句至少执行一次。

    1. 判定覆盖

    含义:又称为分支覆盖,在设计测试用例,针对程序中具有分支结构的部分,为了测试所有的可能结果,需要将每个分支都至少执行一次,查看相应的语句执行情况和结果

    (1)a=2,b=0,x=4,覆盖RACBDE

    (2)a=3,b=1,x=1覆盖 RABE

    1. 条件覆盖

    条件覆盖是指设计测试用例时,除了保证每条语句执行一次,还要使判定表达式的每个条件的各种可能取值都至少执行一次,为了实现条件覆盖,保证各种可能的条件都取值,即保证

    第一个判断有以下取值:a>1,a<=1,b=0,b≠0

    第二个判断有以下取值:a=2,a≠2,x>1,x<=1

    选择两组测试用例:

    (1)a=2,b=2,x=2(满足a>1,b≠0,a=2,x>1的条件),执行路径为 RABDE

    (2)a=1,b=0,x=0(满足a<=1,b=0,a≠2,x<=1的条件),执行路径为RABE

    1. 判定/条件覆盖

    单独使用判定覆盖和条件覆盖测试结果都不够全面, 若将两种覆盖结合,就会相互补充,判定/条件覆盖就是设计足够多的测试用例,使得每个判定表达式中的每个条件都取到各种可能的值,并且使每个判断语句的所有判断结果至少出现一次。

    (1)a=2,b=0,x=2(满足a>1,b=0,a=2,x>1的条件),执行路径RACBDE

    (2)a=1,b=1,x=1(满足a<=1,b≠0,a≠2,x<=1的条件),执行路径RABE

    1. 条件组合覆盖

    条件组合覆盖就是设计足够多的测试用例,使得每个判定表达式中条件取值的各种组合都至少出现一次。根据每个判定表达式情况,列出如下条件组合

    (1)a>1,b=0,A表达式为真;(2)a>1,b≠0,A表达式为假;(3)a<=1,b=0,A表达式为假

    (4)a<=1,b≠0,A表达式为假;(5)a=2,x>1,B表达式为真(6)a=2,x<=1,B表达式为真;

    (7)a≠2,x>1,B表达式为真;(8)a≠2,x<=1,B表达式为假。

    选择以下四组测试用例

    选择条件a=2,b=0,x=2,(1)、(5)组合,执行路径 RACBDE

    选择条件a=2,b=1,x=1,(2)、(6)组合,执行路径 RABDE

    选择条件a=1,b=0,x=2,(3)、(7)组合,执行路径 RABDE

    选择条件a=1,b=1,x=1,(4)、(8)组合,执行路径 RABE

    1. 路径覆盖

    就是选取足够多的用例,保证程序的所有路径都至少执行一次,如果存在环形结构,也要保证此环的所有路径都至少执行一次。

    (1)a=1,b=1,x=1(满足a<=1,b≠0,a≠2,x<=1的条件),执行路径为RABE

    (2)a=2,b=0,x=2(满足a>1,b=0,a=2,x>1的条件),执行路径为 RACBDE

    (3)a=2,b=1,x=2(满足a>1,b≠0,a=2,x>1的条件),执行路径为 RABDE;

    (4)a=3,b=0,x=1(满足a>1,b=0,a≠2,x<=1的条件),执行路径为 RACBE

    二.测试的步骤:

    1. 单元测试

    a.单元测试的主要任务

    单元测试针对每个模块,主要解决五个方面的问题:(1)模块接口(2)局部数据结构(3)路径测试 (4)过界条件 (5)出错处理

    b.单元测试的执行过程

    1. 集成测试

    a.非增式集成测试方法 b. 增式集成测试方法

    1. 确认测试

    确认测试的标准  配置审查的内容  Alpha Beta 测试  

    1. 系统测试

    方法:恢复测试方法   安全测试方法  强度  性能

    第八章:

    一.软件维护的概念

    软件维护是指在软件运行或维护阶段对软件产品所进行的修改,这些修改可能是改

    正软件中的错误,也可能是增加新的功能以适应新的需求,但是一般不包括软件系统结

    构上的重大改变。根据软件维护的不同原因,软件维护可以分成四种类型

    (1)改正性维护

    在软件交付使用后,由于开发时测试得不彻底或不完全,在运行阶段会暴露一些开

    发时未能测试出来的错误,为了识别和纠正软件错误,改正软件性能上的缺陷,避免实

    施中的错误使用,应当进行的诊断和改正错误的过程,这就是改正性维护

    (2)适应性维护

    随着计算机技术的飞速发展和更新换代,软件系统所需的外部环境或数据环境可能

    会更新和升级,如操作系统或数据库系统的更换等。为了使软件系统适应这种变化,需

    要对软件进行相应的修改,这种维护活动称为适应性维护

    (3)完善性维护

    在软件的使用过程中,用户往往会对软件提出新的功能与性能要求,为了满足这些

    要求,需要修改或再开发软件,以扩充软件功能、增强软件性能、改进加工效率、提高软件

    的可维护性,这种情况下进行的维护活动叫作完善性维护,完善性维护不一定是救火

    式的紧急维修,而可以是有计划的一种再开发活动

    4)预防性地护

    这类维护是为了提高软件的可维护性,可靠性等,为以后进一步改进软件打下良好

    的基础的维护活动,具体来讲,就是采用先进的软件工程方法对需要维护的软件或软件中的某一部分重新设计、编码和测试的活动。

    二.软件维护的特点

    1.软件维护受开发过程影响大

    2.软件维护困难多

    3.软件维护成本高

    三.软件维护的步骤

    软件维护工作包括建立维护组织、报告与评估维护申请、实施维护流程等步骤。

    在影响分析和版本规划的过程中,不同的维护类型需要采用不同的维护策略

    (1)改正性维护:首先应该评价软件错误的严重程度,对于十分严重的错误,维护

    员应该立即实施维护对于一般性的错误,维护人员可以将有关的维护工作与其他开发

    任务一起进行现划。在有些情况下,有的错误非常严重,以致不得不临时放弃正常的维

    护控制工作程序,既不对修改可能带来的副作用作出评价,也不对文档作相应的更新,而

    是立即进行代码的修改。这是一种救火式的改正性维护,只有在非常紧急的情况下才使

    用,这种维护在全部维护中只占很小的比例。应当说明的是,救火式不是取消,只是推迟

    了维护所需要的控制和评价。一旦危机取消,这些控制和评价活动必须进行,以确保当

    前的修改不会增加更为重要的问题

    (2)适应性维护:首先确定软件维护的优先顺序,再与其他开发任务一起进行规划

    (3)定善性维护,根据商业的需求和软件的发展,有些完善性维护可能不会被接受。对于被接受的维护中请,应该确定其优先次序井现划其开发工作

    第九章

    质量保证

    产品的生命,不论生产何种产品,质量都是极端重要的。软件产品开发周期长,耗费巨大的人力和物力,更必须特别注意保证质量。

    软件质量:概括地说,软件质量就是“软件与明确地和隐含地定义的需求相一致的程度”。更具体地说,软件质量是软件与明确地叙述的功能和性能需求、文档中明确描述的开发标准以及任何专业开发的软件产品都应该具有的隐含特征相一致的程度。

    软件质量因素的定义:

    正确性:系统满足规格说明和用户目标的程度,即,在预定环境下能正确地完成预期功能的程度

    建壮性:在硬件发生故障、输人的数据无效或操作错误等意外环境下,系统能做出适当响应的程度

    完整性(安全性):对未经授权的人使用软件或数据的企图,系统能够控制(禁止)的程度

    效率:为了完成预定的功能,系统需要的计算资源的多少

    可用性:系统在完成预定应该完成的功能时令人满意的程度

    风险:按预定的成本和进度把系统开发出来,并且为用户所满意的概率

    可理解性:理解和使用该系统的容易程度

    可维修性:诊断和改正在运行现场发现的错误所需要的工作量的大小

    灵活性(适应性):修改或改进正在运行的系统需要的工作量的多少

    可测试性:软件容易测试的程度

    可移植性:把程序从一种硬件配置和(或)软件系统环境转移到另一种配置和环境时,需要的工作量多少,有一种定量度量的方法是:用原来程序设计和调试的成本除移植时需用的费用

    可再用性:在其他应用中该程序可以被再次使用的程度(或范围)

    互运行性:把该系统和另一个系统结合起来需要的工作量的多少

    软件质量保证的措施主要有:基于非执行的测试(也称为复审或评审),基于执行的测试(即以前讲过的软件测试)和程序正确性证明。

    复审主要用来保证在编码之前各阶段产生的文档的质量;基于执行的测试需要在程序编写出来之后进行,它是保证软件质量的最后一道防线;程序正确性证明使用数学方法严格验证程序是否与对它的说明完全一致

    技术复审的必要性:

    正式技术复审的显著优点是,能够较早发现软件错误,从而可防止错误被传播到软件过程的后续阶段。

    正式技术复审是软件质量保证措施的一种,包括走查和审查等具体方法。走查的步骤比审查少,而且没有审查正规。

    走查主要有下述两种方式。

    (1) 参与者驱动法。参与者按照事先准备好的列表,提出他们不理解的术语和认为不正确的术语。文档编写组的代表必须回答每个质疑,要么承认确实有错误,要么对质疑做出解释。

    (2) 文档驱动法。文档编写者向走查组成员仔细解释文档。走查组成员在此过程中不时针对事先准备好的问题或解释过程中发现的问题提出质疑。这种方法可能比第一种方法更有效,往往能检测出更多错误。经验表明,使用文档驱动法时许多错误是由文档讲解者自己发现的。

    审查步骤:

    (1) 综述。由负责编写文档的一名成员向审查组综述该文档。在综述会结束时把文档分发给每位与会者。

    (2) 准备。评审员仔细阅读文档。最好列出在审查中发现的错误的类型,并按发生频率把错误类型分级,以辅助审查工作。这些列表有助于评审员们把注意力集中到最常发生错误的区域。

    (3) 审查。评审组仔细走查整个文档。和走查一样,这一步的目的也是发现文档中的错误,而不是改正它们。通常每次审查会不超过90分钟。审查组组长应该在一天之内写出一份关于审查的报告。

    (4) 返工。文档的作者负责解决在审查报告中列出的所有错误及问题。

    (5) 跟踪。组长必须确保所提出的每个问题都得到了圆满的解决(要么修正了文档,要么澄清了被误认为是错误的条目)。必须仔细检查对文档所做的每个修正,以确保没有引入新的错误。如果在审查过程中返工量超过5%,则应该由审查组再对文档全面地审查一遍。

    程序正确性证明:

    测试可以暴露程序中的错误,因此是保证软件可靠性的重要手段;但是,测试只能证明程序中有错误,并不能证明程序中没有错误。因此,对于保证软件可靠性来说,测试是一种不完善的技术,人们自然希望研究出完善的正确性证明技术。

     

     

    软件工程一测

     

    1. 软件工程三要素:______________、_________________、_________________
    2. 获取愿景的三部曲:
    3. 愿景_______(是/否)功能。
    4. 愿景必须指出__________
    5. 迭代与增量的定义
    6. UML静态图包括(4个)
    7. UML动态图包括(5个)
    8. 为什么使用UML语言
    9. ______________是软件成功的基础。

     

     

    答案:

    1. 工具(系统)、方法(技能)、开发过程(框架)
    2. 第一步:找到软件项目的“老大”;第二步:得到“老大”对项目的期望(愿景);第三步:描述出愿景的度量指标。
    3. 度量指标
    4. 迭代是反复求精,增量是逐块建造
    5. 类图、对象图、组件图、部署图
    6. 时序图、协作图、状态图、活动图、用例图
    7. 主要用于交流,有利于清晰,有利于精确
    8. 需求

     

     

    软件工程二测

     

    1. 在项目失败的因素中,与      相关的比例最高。
    2.       是解决需求噩梦的手段。
    3. 简要分析项目开发过程中,公司老板、中层经理、一线员工的需求分别有什么特点。
    4. ICONIX过程从把需求文档变成可运作的代码过程只需四步,需要使用哪四张UML图?
    5. 若某公司设有公司老总、市场总监与财务总监,实现强化客户管理功能、提升财务效率功能、优化公司资源功能的三种软件,“老大”分别是谁?

     

    答案:

    1.需求

    2.需求工程

    3.公司老板:企业战略、开源节流(定于愿景)

      中层经理:简化管理、优化流程(业务建模)

      一线员工:工作简单(用例分析)

    4.用例图、序列图、类图、健壮性图

    5.强化客户管理:市场总监

      提升财务效率:财务总监

      优化公司资源:公司老总

     

     

     

    软件过程三测

     

    1. 业务建模序列图阶段要注意什么?
    2. 业务序列图中,alt表示(           ),loop表示(              ),opt表示(         );
    3. Alt和opt在使用的时候有什么区别?
    4. 业务序列图中,消息的名字表示什么?
    5. 业务序列图中,消息的方向表示什么?
    6. 把(        )看作特殊的业务实体。
    7. 业务建模结果复核目的有两点,分别是什么?

     

     

     

     

    答案:

    1. 本阶段不要考虑要实现什么系统
    2. 分支,循环,可选分支
    3. Alt表示分支,是需要条件的;opt表示可选分支,没有条件,有选择性。
    4. 代表责任和目的
    5. 责任委托,不是数据流动
    6. 时间
    7. 一是完善业务建模成果,寻找是否有遗漏或错误的地方进行修正,如果问题明显,就需要迭代回去继续做业务建模工作;

    二是关键干系人在信息和意见上达成一致,并共同签字确认,作为下一阶段启动的标志。

     

     

     

     

     

     

    软件工程四测

     

    1. 业务建模要求我们把视角从_______,以达到清晰准确地“诊断”,对症“开方”

    答案:软件系统转向客户组织,站在客户角度看问题

    2、业务建模三步骤:

    1、___________2、____________3、____________

    答案:

    1. 明确我们为谁服务(选定愿景要改进的组织)。
    2. 要改进的组织是什么现状(业务用例图、现状业务序列图)。
    3. 我们如何改进(改进业务序列图)。

    3、了解组织现状:

       (1)从外部看:组织是____的集合,用业务用例图来建模

       (2)从内部看:组织是____的集合

    答案:价值、系统

    4、业务用例图帮助我们从______了解组织的______。

    答案:高层次 、业务构成

    5、业务执行者是在业务组织之外,与其交互,享受其价值的_______

    答案:人或组织

    6、业务用例是业务组织为业务执行者提供的______.

    答案:价值

    7、业务序列图帮助我们从______了解组织的______。

    答案:细节上、 业务流程

    8、业务序列图详细描述________、_______、________之间如何交互,以完成某个业务用例的实现流程

    答案:业务执行者、业务工人、业务实体

    9、举个简单的例子并识别其中的业务对象:业务执行者、业务工人、业务实体

    答案:自由发挥

    10、我们如何改进(改进业务序列图)

    答案:了解业务组织现状的目的——发现流程中的改进点:

    • 信息自动流转
    • 封装复杂业务逻辑
    • 职责转移
    • 访问和操作业务对象

    其他……

     

    软件过程五测

    1. 域建模_____不等于_____(等于或不等于)数据模型
    2. ___用例分析________前做域建模
    3. 需求分析的主流分析方法有___原型法____、______用例法_______
    4. 绘制系统用例图的步骤

    1. 确定系统边界

    2. 识别系统执行者

    3. 识别系统用例

    4. 确定用例间的关系

    1. 怎样区别主执行者和辅执行者

      主执行者:

    1.用例发起者;

    2.用例为其实现有价值的目标;

    辅执行者:

    1.用例支持者;

    2.用例的完成需要与其交互,得到其支持

    1. 如何找到执行者

      谁使用该系统?

    • 谁改变系统的数据?

    • 谁从系统获取信息?

    • 谁负责维护、管理并保持系统正常运行?

    • 系统需要应付哪些硬件设备?

    • 系统需要和那些外部系统交互?

    • 谁对系统运行产生的结果感兴趣?

    • 有没有自动发生的事件?

    1. 系统用例是执行者通过系统____达到某个目标______
    2. 用例的关系____泛化____、_____包含_______、______扩展__________
    3. 先发现执行者还是先发现用例?为什么?

       执行者比用例明显。

    • 执行者的个数远比用例的个数少。

    • 找到一个执行者,就可以找到一堆用例。

    • 执行者是系统外部人物的代表,所以当然是要先找到执行者,才能够从执行者的角度去寻找用例。

    1. 用例命名的三个条件是什么?

     用例名称必须是动宾短语。

    • 采用域建模中的名词术语。

    • 慎用弱动词弱名词——会掩盖真正的业务

    1. 用例_____不等于______功能,用例____不等于______步骤

     

    软件过程六测

    1. 每个用例必须对应有___愿景目标______
    2. 用例描述的基本组成__干系人利益_____________、_____基本路径____________、________扩展路径_______、_______业务规则_______________
    3. _________用例_______是干系人利益的平衡点。
    4. 基本路径的书写要求。

      以主动语态、“名词-动词-名词”格式来书写。

      主语只能是执行者或系统。

    1. 基本路径与扩展路径是否要分开。

      要

     

    更多相关内容
  • 如果面试问起,就说底层主要靠volatileCAS操作实现的。 五.CAS机制 Compare And Swap CAS操作是一个原子操作,由一条CPU指令完成,使用了3个基本操作数,内存地址V,旧的预期值A ,要修改的新值B 需要更新一个...

    可以说,学姐给我的这份文档真的把我的知识查漏补缺,面试问到了好多,值得收藏。

    并发编程

    .Executor

    为什么使用线程池:手动创建线程耗费性能,不利于管理。

    首先创建线程池有两种方式:使用Executors工厂来创建ThreadPoolExecutor这类自定义线程池。

    1. 使用Executors工厂来创建

    Executors是一个类,用来创建线程池,常用的有四种线程池

    1.newFixedThreadPool 创建一个可重复固定的线程数的线程池

    2.newCachedThreadPool 创建一个可缓存的线程池,调用execute将重复用以前构造的线程(如果当前线程可用)。如果没有可用线程则创建新的线程并加入到池中。终止并从缓存中移除那些已有60s未被使用的线程。

    3.newSingleThreadExecutor创建一个单线程化的线程池,它只会用唯一的工作线程来执行任务,保证所有任务按照指定顺序(FIFO, LIFO, 优先级)执行

    4. newScheduledThreadPool 创建一个支持定时及周期性的任务执行的线程池,多数情况下可用来替代Timer类。

    使用示例:

     

     

     

    2. 使用ThreadPoolExecutor这个类自定义创建线程池

     

     

    .ThreadLocal

    https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/6782674c-1bfe-4879-af39-e9d722a95d39.png

     

    .中断线程

    1.线程执行完毕会自动结束

    2.在线程处于阻塞,期限等待火无期限等待时,调用线程的interrupt()会抛出interruptedException异常从而提前终止线程

    3.若没有处于阻塞状态,调用interrupte()将线程标记为中断,此时在调用interrupted()判断线程是否处于中断状态,来提前终止线程。

    4.线程池调用shutdown()等待所有线程执行完毕之后关闭

     

     

    .Volatile关键字的理解

    两层语义:1.保证不同线程对该变量的内存可见线

              2.禁止进行指令重排序

     

    内存语义:

    读这个变量的时候,JMM会把本地内存中的变量设置为无效,从主内存中取;

    写这个变量的时候,JMM会把本地内存变量刷新到主内存当中

    实现:添加Volatile关键字会在汇编代码中多处一个kock前指令,也就是内存屏障

     

    .Synchronized关键字

    1synchronizedJava中的关键字,是一种同步锁。它修饰的对象有以下几种:

        1. 修饰一个代码块,被修饰的代码块称为同步语句块,其作用的范围是大括号{}括起来的代码,作用的对象是调用这个代码块的对象;

        2. 修饰一个方法,被修饰的方法称为同步方法,其作用的范围是整个方法,作用的对象是调用这个方法的对象;

        3. 修饰一个静态的方法,其作用的范围是整个静态方法,作用的对象是这个类的所有对象;

    4. 修饰一个类,其作用的范围是synchronized后面括号括起来的部分,作用主的对象是这个类的所有对象。

     

    2Synchronized的作用主要有三个:(1)确保线程互斥的访问同步代码(2)保证共享变量的修改能够及时可见(3)有效解决重排序问题。

    3Synchronized 原理

        在编译的字节码中加入了两条指令来进行代码的同步。

        monitorenter :

        每个对象有一个监视器锁(monitor)。当monitor被占用时就会处于锁定状态,线程执行monitorenter指令时尝试获取monitor的所有权,过程如下:

        1.如果monitor的进入数为0,则该线程进入monitor,然后将进入数设置为1,该线程即为monitor的所有者。

        2.如果线程已经占有该monitor,只是重新进入,则进入monitor的进入数加1.

        3.如果其他线程已经占用了monitor,则该线程进入阻塞状态,直到monitor的进入数为0,再重新尝试获取monitor的所有权。

        monitorexit:

        执行monitorexit的线程必须是objectref所对应的monitor的所有者。

        指令执行时,monitor的进入数减1,如果减1后进入数为0,那线程退出monitor,不再是这个monitor的所有者。其他被这个monitor阻塞的线程可以尝试去获取这个 monitor 的所有权。

         通过这两段描述,我们应该能很清楚的看出Synchronized的实现原理,Synchronized的语义底层是通过一个monitor的对象来完成,其实wait/notify等方法也依赖于monitor对象,这就是为什么只有在同步的块或者方法中才能调用wait/notify等方法,否则会抛出java.lang.IllegalMonitorStateException的异常的原因。

    4Synchronized的优化

    (4)synchronized与Lock的区别

        lock是一个类,主要有以下几个方法:

        lock():获取锁,如果锁被暂用则一直等待

        unlock():释放锁

        tryLock(): 注意返回类型是boolean,如果获取锁的时候锁被占用就返回false,否则返回true

    tryLock(long time, TimeUnit unit):比起tryLock()就是给了一个时间期限,保证等待参数时间

    https://note.youdao.com/yws/public/resource/cc25598bbaff18a55569c256de4cf1c6/xmlnote/10A95AB8238442569108FC93755C91FF/1701

     

        (1)Lock的加锁和解锁都是由java代码实现的,而synchronize的加锁和解锁的过程是由JVM管理的。

        (2)synchronized能锁住类、方法和代码块,而Lock是块范围内的。

        (3)Lock能提高多个线程读操作的效率;

    (4)Lock:Lock实现和synchronized不一样,后者是一种悲观锁,它胆子很小,它很怕有人和它抢吃的,所以它每次吃东西前都把自己关起来。而Lock底层其实是CAS乐观锁的体现,它无所谓,别人抢了它吃的,它重新去拿吃的就好啦,所以它很乐观。如果面试问起,你就说底层主要靠volatile和CAS操作实现的。

    .CAS机制

    Compare And Swap

    CAS操作是一个原子操作,由一条CPU指令完成,使用了3个基本操作数,内存地址V,旧的预期值A ,要修改的新值B

    需要更新一个变量的时候,只有当内存地址V中的值和预期值A相等的时候才会修改为新值B ,如果失败则自旋,重新尝试

    问题:

    1.ABA 解决办法,加一个版本号,只有当版本号和预期值都符合的时候才修改

    2.不能保证代码块的原子性,CAS机制知识保证一个变量的原子操作

    .JMM的理解

    JMM的核心是找到一个平衡点,在保证内存可见性的前提下,尽量的放松对编译器和处理器重排序的限制。

     

    可能会产生缓存一致性的问题:

    1.总线锁定

    2.缓存一致性协议

     

    三大特性:原子性,可见性,有序性

     

     

     

    .JVM的锁优化

    1.自旋锁和自适应自旋锁

    线程挂起和恢复都需要很大的性能开销,很多共享数据的锁定状态只持续很短的时间,为这段时间挂起恢复不值得,所以可以让现场进入一个自旋状态,但仍占用cpu的时间,默认是10次,超过10次则采用传统的方式挂起线程。自适应自旋锁会根据上次在这个锁上自旋的时间调整自选次数

     

    2.锁消除

    检测到对局部变量加锁,会自动将锁消除,如在一个方法里面有sb = s1 + s2 + s3以前会转化为StringBuffer(线程安全,有加锁)的append操作,优化之后会转换成StringBuilder的sppend操作

     

    3.锁粗化

    对一个对象反复加锁解锁,如上述的append方法,编译器会优化,只在最外层加一个锁

     

    4.轻量级锁

    对象有一个对象头,对象头分两部分区域,一部分存储子树的hashcode,GC分代年龄,锁标志位等,官方成为mark word,另一部分用于存储指向方法区对象类型的指针;

    轻量级锁的执行过程是代码进入同步块的时候,如果当前对象没有被锁定(锁标志为是01)则先在线程的栈帧中建立一个锁记录空间(lock record)将对象的mark word拷贝过来,然后利用cas操作尝试将对象的markword更新为指向lock record,如果成功则当前线程拥有该对象锁,并且将锁标志位从01改为00,如果更新失败则会检查当前对象markword是否指向当前线程的栈帧,如果是则直接进入同步块执行否则说明当前的对象锁已经被其他线程占有。如果有两条以上的线程竞争这个锁,那就会膨胀成重量级锁,锁标志为变成10;

     

    5.偏向锁

    锁对象第一次被线程获取的时候,会将当前的锁标志设置为偏向锁01状态,并使用cas操作将当前线程的id记录在markword当中,如果成功那么在以后的操作当中不需进行任何操作就可以进入同步代码块,当有另外一个线程获取当前锁的时候,偏向模式就宣告结束,撤销偏向锁之后恢复到未锁定或者轻量级锁状态

     

    JAVA基础

    String

    1.string s1 = “aaa” 与 String s1 = new String(aaa);

    前者会在Stringpool中创建一个对象,如果Stringpool中已经有了,则直接引用

    后者会在Stringpool和堆中分别创建一个对象,如果StringPool中已经有了则只创建一个对象

     

    2.调用s1.integer()方法,可以将字符串放入StringPool中,如果已经存在则直接返回这个对象

     

     

    继承

    1.几种修饰符的访问权限范围

     

    2. ==  equals  hashcode的关系

    1.==是比较两个对象的地址是否相等

    2.equals默认和 == 一样也是比较地址,也可以根据自己的需求来重写什么叫做相等

    3.hashcode 是根据对象的地址来返回一串int型数字,如果对象不一样的话返回的值也不一样

     

    3.为什么重写equals的同时也要重写hashcode

    首先必须满足如果equals相同,那么hashcode也必须相同,如果hashcode不相同,那么equals必须不相同的原则,否则会导致该类无法与基于散列值的集合类(hashmap , hashset ,hashtable)结合正常运行

     

    因为对于这些集合在进行重复性判断时,是先用hashcode判断,如果相同在用equals判断

     

     

    4.hash冲突的解决方法

    1.开放地址法(线性探测法,二次探测法)

    2.在散列函数法

    3.链地址法

     

    5.hashtablehashmap的区别

    1.hashmap线程不安全,hashtable线程安全

    2.hashmap最多允许一个键为null,而hashtable不允许

    3.hashtable中默认的hash数组大小为11,增加的方式是old*2+1,而hashmap默认是16,肯定是2的指数

    4.计算hash的方法不一样,hashtable是直接用hashcode,而hashmap使用了key的高16位和低16位做异或运算

     

    Linkedhashmap继承于hashmap,可以按顺序读取,底层使用的是双向链表

    TreeMap实现了sortmap接口,可以对元素进行排序,底层使用的红黑树

     

    7.java BIO NIO AIO 序列化

    字节操作:使用inputStream和outPutSream实现,字节是传输和存储的最小单位

    字符操作:inputStreamReader:将字节流解码成字符流

    OutPutStramWriter:将字符流编码成字节流

    对象操作:序列化就是将对象转换成字节序列,方便存储和运输,两个用途:

    1.把对象的字节序列永久地保存到硬盘中,通常存放在一个文件里

    2.在网络上传送对象的字节序列

    在很多应用中,需要对某些对象进行序列化,让他们离开内存空间,入住到物理磁盘方便长期保存,比如session对象,当有大量用户并发访问的时候可能会出现10万个session对象,内存吃不消,此时就需要将这些session先序列化到硬盘中,等要用的时候在把对象还原到内存中。

    当两个进程在进行远程通信的时候,彼此可以发送各种类型的数据,无论是何种类型的数据,都会以二进制的序列在网络上传送。发送方需要把这个java对象转换成字节序列,才能在网络上传送;接收方则需要把字节序列恢复成java对象。

    Io与NIO的区别:

    1.NIO是非阻塞的

    2.NIO是面向缓冲区的,IO是面向流的

     

    AIO:异步非阻塞

     

     

     

    8.static关键字的作用

    一.修饰变量:

    1.静态变量在类加载的时候被创建并初始化,只被创建一次(类加载只进行一次),可以修改

    2.静态变量属于整个类而不属于某个对象。

     

    二.修饰方法

    1.可以通过类名来访问,不需要创建对象来访问,可以用来实现单例模式

    2.静态方法只能调用静态方法和静态变量

     

    三.修饰静态代码块

    在类加载的时候执行,且只执行一次

     

    9.单例模式

    实现:

    1.为什么要用判断双重:
    因为可能有两个线程都执行完了第一个if语句,如果没有第二重判断,那么当其中有个线程执行完synchronized里面的语句之后,另外一个线程跟着也会执行,这样就达不到单例模式的效果

     

    2.第一重判断去掉也可以实现,为什么不去掉

    这个设计性能问题,因为

    参考:https://qinjiangbo.com/mechanism-of-double-locking-check.html

     

    10.this与super关键字


     

     

    9.java中的多态

    分为两种:

    1.编译时多态:体现在重载(方法名相同而参数不同),在编译时期就根据传入的参数确定好调用哪个方法;

    2.运行时多态:体现在方法的重写。在运行时期判断引用类型的实际类型根据实际的类型调用其相应的方法;

    当父类对象引用变量引用子类对象时,被引用对象的类型决定了调用谁的成员方法,引用变量类型决定可调用的方法。如果子类中没有覆盖该方法,那么会去父类中寻找。

     

    参考链接:https://www.runoob.com/w3cnote/java-polymorphism.html

     

    10.接口类和抽象类的异同

    区别:

    1.抽象类可以有非抽象方法,但接口只能有抽象方法

    2.接口中的成员变量默认修饰为public static final(高度抽象的模版,所以这些都是提取出来的不变特征),方法默认修饰为public abstract。抽象类中的成员变量可以被不同的修饰符来修饰

    3.类可以实现多个接口但只能继承一个抽象类

     

    相同:

    1.不能被实例化

    2.派生类都必须实现未实现的方法

     

    11.instanceof

    用来判断一个对象是否是一个类的实例

    12.各种排序算法复杂度及稳定性

    1.java底层如何实现排序的

    Java中Arrays.sort使用了两种排序方法,快速排序和优化归并排序。

    快速排序主要针对基本的数据类型(int short long)排序,而归并排序用于对象类型的排序

     

    如果数据量小于60会使用插入排序,插入排序是稳定的

     

    13.java中的堆和栈

    栈:主要用于存储局部变量和对象的引用变量,每个线程都有一个独立的栈空间,所以线程之间是不共享数据的;

    栈的特点是存取速度快,但所存数据的大小和生存期必须是确定的(编译后就已经确定大小)

     

    堆:堆中主要存储实例化的对象和数组。线程共享。堆的优势是可以动态的分配内存大小,生存期也不必事先告诉编译器,但缺点是存取速度较慢

     

     

    Linux基本面试题:

    Ls:用于显示指定工作目录下的类容,不会列出详细信息

    Ll:会列出当前文件目录的详细信息,含有时间,权限,大小等

    Cd:用于切换到目标目录

    Mkdir:用于简历当前目录的子目录

    rm-r 删除的文件或者目录,需确认

    rm –rf同上但无需确认

    cp:复制文件 若复制目录则必须加上-r

    数据库MySQL

    .索引

    1.B树,B+树,以及两者的区别

    B树是一种多路平衡查找树,其每一个节点都存储Key和data

    B+树是B树的一个变种,叶子节点存储data,非叶子节点只存储key,B+树的叶子节点增加了顺序访问指针,每一个叶子节点都可以访问到他的下一个叶子节点

     

     

    区别:

    1.B+树种只有叶子节点会带有全部信息,非叶子节点只起到索引的作用,二B树的所有节点都带有全部信息,B+树的每一层节点都会再次出现在下一层节点上

    2.B+树种所有叶子节点都是通过指针连在一起,B树则没有

     

    2.索引的优点和缺点

    优点:可以加大检索速度

    缺点:创建和维护索引需要耗费时间

     

    3.Mysql为什么选择B+

    Mysql数据本质上是放在外部存储的,B+树是为了加快读取速度二设计的一种数据结构

    1.可以减少i/o次数,只有叶子节点才存储数据,非叶子节点存储索引,这样一次读取到内存的关键字增多,相对i/o次数也就减少(根据区别一

    2.能够提供稳定高效的范围扫描,因为所有的叶子节点都互相连接(根据区别二

     

    4.索引越多越好吗?

    索引可以提高select的效率,但是也降低了insert和updata的效率,因为插入和更新的时候可能会重建索引,索引怎么建索引要慎重考虑。

     

    5.索引分类

    1.B+树索引:以b+树作为数据结构的索引

    2.hash索引:能以O(1)的时间复杂度查找,但失去了有序性,innodb有一个自适应哈希索引,当这个索引值被频繁使用时会在b+树上创建一个哈希索引

    3.全文索引:用于查找文本的关键词,中文需要由中文分词插件

    . MySQL优化

    一.MySQL的优化,主要分为索引的的优化,sql语句的优化,表的优化。同时可以使用缓存增加效率

    1.索引的优化

    只要列中含有null,最好不要再此列设置索引

    对于经常在where语句中使用的列,最好设置一个索引

    对于like语句,以%或者-开头的不会使用索引,以%结尾会使用索引

     

    二.sql语句的优化

    查询优化要尽量避免全表扫描

    查询时能不用*就不用*,尽量写字段名

    . MySQL常问问题

    1.数据库如何应对大规模的写入和读取

    (1)使用NoSQL,通过降低数据的安全性,减少对事物的支持,减少复杂查询的支持来获取性能的提升;但有些场合NoSQL无法满足要求

    (2)分库分表:

    水平切分:不修改数据库的表结构,通过对表中的数据拆分而达到分片的目的,一般水平切分在查询的时候可能会用到union操作(多个结果并)

    可以根据hash或者日期来进行分表

     

    垂直切分:修改表结构,按照访问的差异将某些列拆分出去,一般查询数据的时候可能会用到join操作;把常用的字段放在一个表中,不常用的放在一个表中;把字段比较大的比如text字段拆出来放在一个表中。

     

    分库:分表能够解决数据量过大带来的查询效率下降问题,但是却无法给数据库的并发处理能力带来质的提升;分库可以对关键字取模的方式来对数据访问进行路由;https://note.youdao.com/yws/public/resource/96920e055ee2c654ada64b031cefec78/xmlnote/4A29F29BE4E14CFBB1B746D67A6018AC/9130

     

     

     

    (3)读写分离

    读写分离是在主服务器上修改数据,数据也会同步到从服务器上,从服务器只能提供读取,不能写入,实现备份的同时也实现了数据库的性能优化

    https://note.youdao.com/yws/public/resource/96920e055ee2c654ada64b031cefec78/xmlnote/747008E97868421DA096C6672EBDE002/9136

    如何保证数据一致性:

    (1)主节点

    保证事务每次提交之后,要确保binlog都能刷新到磁盘中,只要有了binlog,innoDB就有方法恢复数据,不至于导致主从复制的数据丢失

    (2)从节点

        开启 relay log 自动修复机制,发生 crash 时,会自动判断哪些 relay log 需要重新从master 上抓取回来再次应用,以此避免部分数据丢失的可能性。

     

    2.数据库事务及其隔离级别

    事务的特性:ACID

     

    事务在并发的时候,隔离性很难保证主要可能出现下面这些问题

    脏读:一个事务读了另外一个事务未提交的数据,如果另一个事务回滚则会发生脏读

    不可重复读:一个事务前后读取同一行数据,如果在这个过程中有其他事务修改了此数据则会发生不可重复读

    幻读:一个事务前后读取范围的时候

     

     

     

    事务隔离级别:

    MySQL实现事务是基于undo/redo日志实现的:
    undo日志记录修改前的状态,ROLLBACK基于UNDO日志实现;

    REDO日志记录修改后的状态,事务的持久性基于REDO日志实现

     

    两种解决脏读、不可重复读、幻读的方案:

    MVCC(性能较高,但读的可能是历史版本)

    1.版本链:对于每一行的数据,在undo日志中,总会记录每个版本记录以及对应的事务id,

    2.readView:

    核心问题:当前版本链中哪个版本对当前事务可见

    Readview包含的内容:{当前活跃的事务id,下一个应该分配的事务id,当前自己的事务id},根据当前读的版本事务id和这个readview对比,如果是活跃的或者大于下一个应该分配的事务id则说明当前版本对此事务不可见,应该前读一个版本,依次类推直到找到可见的版本

    提交读:每次读取数据前都会生成一个readview

    可重复读:在第一次读取时句时生成一个readview

     

     

    锁(性能不高,但读的是最新版本):

     

     

     

    MyISAM和innoDB的区别

    1.innodb支持行锁,myisam不支持行锁

    2.innodb支持事务,myisam不支持事务

    3.innodb支持回滚和安全回复,myisam不支持

    4.innodb的索引就是数据,myisam的索引只存储了主键和行号,还需要根据行号去查找相应的记录

    5.innodb更适合写密集的表,myisam更适合读密集的表

    计算机网络

    1.tcp和udp的区别:

    Udp:无连接,尽最大可能交付,没有拥塞控制流量控制

    Tcp:面向连接,可靠交付,有拥塞控制和流量控制

     

    2.输入一条url,整个过程:

    1.DNS解析,获取ip地址(本机,本地域名服务器,根域名服务器,顶级域名服务器,权限域名服务器)

    2.建立TCP连接

    3.浏览器发出http请求

    4.服务器进行响应

    5.TCP连接释放

    6.浏览器渲染

     

    3.为什么是三次握手,四次挥手

    三次握手:防止之前滞留的连接请求再次到达服务端

    四次挥手:因为tcp是全双工模式,客户端停止发送请求之后,服务端也要停止发送请求

     

    4.time_wait存在的原因,时间是多少(两倍的报文最大存活时间)

    1.确保客户端发送的最后一个报文能被收到,服务端可以正常关闭。

    2.让所有报文都在网络中消失,时间是两倍的最大报文存活时间。

     

    5.tcp的可靠传输靠什么:

    超时重传:如果已经发送的报文在超过时间内没有被确认,那么就重新发送这个报文

     

    6.Tcp的滑动窗口

    发送方和接收方都有一个滑动窗口

     

    7.TCP流量控制

    流量控制是为了控制发送方的发送速率,保证接收方来得及接收

    通过滑动窗口来控制,根据报文知道对方窗口的大小,然后根据窗口大小来控制发送速率

     

     

     

    8.TCP拥塞控制

    如报文过多,会导致超时重传,又会导致网络更加阻塞

    https://cs-notes-1256109796.cos.ap-guangzhou.myqcloud.com/910f613f-514f-4534-87dd-9b4699d59d31.png

    1.慢开始和拥塞避免:

    慢开始:设置初始的报文数量为1;

    拥塞避免:设置一个阈值,当报文数超过这个阈值的时候每次,报文每次加一,如果出现超时领阈值等于当前报文的一半,重新执行慢开始

     

    快重传:如果收到3个确认报文,则重传丢失的那个报文

    快恢复:这种情况令阈值等于当前报文的一半,并令当前发送的报文数等于阈值,因为没有出现网络阻塞

     

     

    http各个版本的区别

    http0.9 : 仅支持GET请求,仅能访问html资源

    http 1.0 :增加了post和head请求

    http1.1 : 增加了长连接,一个tcp连接可以发送多个http请求,新增了put,patch,delete请求

    http2.0 : 增加了双工模式,不仅客户端能发送多个请求,服务端也能处理多个请求

    Redis

    1.redis的数据淘汰策略

    当redis内存数据大小达到一定的大小时,就会施行数据淘汰策略,主要有六种策略

     

    2.数据库和缓存的数据一致性

    2.1 mySQL里有2000w数据,redis中只存20w的数据,如何保证redis中的数据都是热点数据

    根据数据淘汰策略,先算一下这20W的数据大概占多少内存,然后设置redis的内存,启用从所有数据集中挑选最近最少使用的淘汰策略

     

    2.2 redis缓存和mysql数据库同步

     

     

     

    3.Redis持久化

    1.RDB持久化(redis默认方式)

    将某个时间点的所有数据都存在硬盘中,如果发生故障将丢失最后一次创建快照的数据

    触发RDB快照的条件:在指定的时间间隔内,执行指定次数的写操作

    2.AOF持久化

    所执行的每一条指令,都会记录到appendonly.aof文件中,redis会按照策略将指令存入硬盘中。当redis重启的时候会根据日志文件的内容将写指令从前到后执行一次完成数据恢复的功能

     

     

    Java异常体系

    http://assets.tianmaying.com/md-image/c887bccaa4b144622c82685097908f3d.png

    Error:主要是虚拟机产生,与代码编写者无关,例如:outOfMemoryError

     

    Exception:主要有运行时异常和io异常

    运行时异常:数组越界,空指针异常

    Io异常:找不到文件

     

    发生oom的可能区域:

    除了程序计数器都有可能发生

    虚拟机栈:当jvm尝试去扩展栈空间失败时可能会抛出oom异常

    堆:堆中对象堆积起来无法释放

    方法区

     

     

    四种引用类型:

    主要体现在对象不可达性和对垃圾回收的影响:
    强引用:只要有强引用指向一个对象,就表面对象还活着,垃圾回收期不会碰这种对象

    软引用:只有当jvm认为内存不足的时候才会去试图回收这些对象

    弱引用:不能使对象豁免垃圾回收,只是提供一种对象的访问途径

    虚引用:不能提供他访问对象,仅仅提供一种确保对象呗finalize之后做某些事情的机制

     

     

     

    JAVA虚拟机是如果加载类的

    1.加载:主要是用类加载器(启动类加载器,扩展类加载器,应用类加载器)来查找对应类的字节流

    双亲委派的好处:由于类随着类加载器一起有一种优先级的层级关系,从而使基础类得到统一

     

    2.链接

    验证:确保字节流的安全性,不会对虚拟机造成危害

    准备:为类的静态字段分配内存

    解析:将符号引用解析成实际引用

     

    3.初始化:调用<clinit>方法,为静态变量赋与实际的值,执行静态代码块

    运行时数据区域:

     

     

     

    运行时内存区域

    1.程序计数器:记录正在执行虚拟机字节码的指令地址

    2.java虚拟机栈:主要存储局部变量表

    3.本地方法栈

    4.堆:存储对象的地方,有新生代和老年代

    5.方法区:存储类信息,常量,静态变量等信息

     

    内存分配策略:

    1.对象优先在eden区域分配

    2.大对象直接进入老年代

    3.长期存活的对象进入老年代:会有一个年龄计数器,达到指定的阈值就会进入老年代

     

    FullGC触发条件:

    1.调用system.gc()

    2.老年代空间不足

    3.minor GC时老年代空间分配担保失败

    展开全文
  • 【权限专栏】谁允许你访问了?

    千次阅读 2021-10-20 17:50:29
    【背景】 作为一种去中心化的分布式系统,区块链系统...鉴权指的是用户访问受限资源时通过特定机制凭证校验用户是否具有访问能力的过程。 区块链系统中的权限体系,会根据受保护资源对系统的影响范围被划分成若干层

    【背景】
    作为一种去中心化的分布式系统,区块链系统在生产环境中会受到网络条件、节点规模、监管政策等多方面因素的影响,因此系统需要解决运维与合规问题,以保证分布式系统线上运行的安全与稳定。

    在计算机系统中,广义上的权限体系一般包括三个部分:授权、鉴权及受保护资源。受保护资源指的是访问需要受到一定条件约束的资源;授权指的是用户主动或被动获取访问受限资源能力的过程;鉴权指的是用户访问受限资源时通过特定机制和凭证校验用户是否具有访问能力的过程。

    区块链系统中的权限体系,会根据受保护资源对系统的影响范围被划分成若干层级。每个层级又可以细分出不同的受保护资源。不同的受保护资源可具有截然不同的权限管理机制。

    【权限层级】
    总体上,在区块链系统中,权限体系所保护的资源一般可以从资源对区块链系统的影响层级范围的维度划分成四类:对整个链运转产生影响的链级权限、对单个智能合约运行产生影响的合约权限、对区块链上单个账号产生影响的账号权限及只对区块链系统中单个节点产生影响的节点权限。

    ▲链级权限
    链级资源:区块链系统中需要所有节点保持一致的参数配置集合。
    链级资源的访问:在区块链系统中对上述配置进行统一变更的操作。
    链级权限就是保护链级资源的权限机制。链级资源一般在区块链系统创世时就稳定地存在于区块链系统中,一般需要通过特殊的交易来访问,保证节点间的一致性;其访问必须在一定程度上受限,不可以轻易被访问,一旦被随意访问,容易导致功能的混乱,进而整个系统受到不可逆的损害。

    ▲合约权限
    合约权限:业务智能合约操作接口的访问控制。
    受保护的操作包括智能合约的维护与调用。智能合约的维护一般指的是智能合约代码的更新、智能合约的状态变更等,其维护权限默认赋予智能合约的部署者。

    不论是智能合约的维护还是调用,都需要通过特定的标识符来指向所访问的合约,基于智能合约的标识符,在区块链执行器层面可以提供黑白名单的机制对智能合约的接口进行整体保护。

    ▲账号权限
    在区块链账本上的主体,除了智能合约一般还包括区块链账号。账号权限核心就是保护区块链账本上的账号,使其不会被随意使用,它既包含了交易发起方的验证,又包含了发起方是否有权限向交易接收方发起操作的验证。

    ▲节点权限
    上述三类权限受保护的主体,不论是链级参数、合约接口或区块链账号,都是一个区块链系统中全局的概念,因此上述三类权限控制机制在区块链系统中所有的节点上,都是以相同的方式运作的。

    节点权限相比上述三类权限来说,是一个单点的概念。理论上一个区块链系统中的节点只需要满足特定的协议,可以用不同的方式来实现,也可以对客户端提供不同的接口。节点权限所保护的资源对象就是实现区块链节点协议的服务器端对其客户端暴露的接口,确保接口不可以被随意访问。

    【权限管理模型】
    介绍了权限体系所保护的资源,下面将介绍权限管理模型:如何进行授权和鉴权。

    目前在区块链系统中使用权限管理模型有多种,例如基于公钥密码学的权限管理模型、基于链下多重签名的权限管理模型、基于提案投票的权限管理模型、基于角色的权限管理模型等,在实际区块链系统设计和实现中,往往会使用多个权限管理模型组合形成其权限体系,此处主要介绍基于提案投票的权限管理模型。

    ▲基于提案投票的权限管理模型
    基于提案投票的权限管理模型:通过在内置智能合约或在业务智能合约中设计一套提案投票机制来保护特定资源的机制。在整个体系中包含两方面要素,参与者管理与提案投票管理。

    参与者管理:管理有哪些用户可以参与提案投票管理,此处则是基于角色的权限管理模型来对参与者进行管理的;

    提案投票管理则:访问受保护资源必须以提案的形式发起交易,然后由参与者发起投票交易,通过投票来决定提案是否能够被执行。

    基于提案投票的权限管理模型初始化时,需要初始化投票系统的状态,并且记录在区块链账本上。

    首先,要进行的是参与者的初始化,包括初始化所有可以参与投票的参与者的标识符和参与者的投票权重。

    然后是投票机制参数的初始化,包括同意票阈值、反对票阈值、提案失效条件等。一般来说,提案需要一个最长有效期,这个有效期可以通过区块高度或交易打包时间来规定,也就是说,一个提案在账本上成功创建之后,在高度小于一定值或打包时间小于一定值的区块内才允许被投票或执行。

    最后就是资源访问接口的初始化,一般来说,最通用的做法是将资源的访问接口以类似RPC接口注册的方式注册为一个可以通过提案投票机制调用的接口。值得注意的是,通常可以将参与者与提案投票的参数变更接口注册为提案可访问的资源,实现系统的自维护。

    基于提案投票的权限管理模型的授权鉴权流程如下图所示,访问系统资源主要有以下三个需要用户操作的环节:
    在这里插入图片描述
    基于提案投票的权限管理模型的授权鉴权流程

    1)提案
    提案环节,一般需要结合数字签名来证明提案的发起者在参与者列表中。此外,发起提案需要将资源接口调用所需要的参数全部包含在交易参数中发到区块链系统上。提案交易执行时,一般会嵌入检查条件来检查是否能够进行提案创建。通过检查后,调用参数将包含在提案数据中存放在区块链账本上,供后续使用。当提案产生之后,可以通过多种交互机制来通知所有参与者,如消息队列或客户端轮询等。

    2)投票
    提案创建之后,参与者通过各自的手段获取到提案信息,并根据自己对调用的认可情况来选择是否使用密钥签署投票交易,对提案发起同意票或反对票。区块链系统执行时会在账本上记录参与者的投票信息。

    3)执行
    当提案的同意票达到要求的阈值,参与者就可以使用密钥签署执行交易来使提案生效了。具体方法是从账本上读出资源调用参数,然后进行调用。

    上述环节描述了基于提案投票的权限管理模型初始化和运作的一般机制,具体在区块链系统实现中,一般基于该模型做一定程度的简化或扩展。例如,可能会合并其中的投票和请求执行的步骤,以实现自动执行;还可以根据对提案执行顺序的要求引入一些顺序保障机制等。在该模型中,授权涉及初始化、提案、投票三个过程;鉴权则是通过执行提案时检查同意票是否达到阈值来进行。

    【小结】
    本文从权限体系的三个部分入手,根据权限体系受保护资源对区块链系统的影响层级范围,介绍了在区块链系统中不同范围的受保护资源,并阐述了一种用于授权和鉴权的权限管理模型——基于提案投票的权限管理模型。后续我们还会对基于提案投票的权限管理模型是如何对链级权限进行管理的进行详细介绍。

    作者简介
    刘明美
    趣链科技基础平台部 区块链网络研究小组

    参考文献
    [1] 《区块链技术指南》

    展开全文
  • 条件随机场(CRF)

    万次阅读 多人点赞 2018-08-24 16:58:27
    当时全网搜中文资料,陆续失望地发现竟然真的没有讲得清楚的博文,发现基本是把李航老师书里或CRF tutorial等资料的文字论述公式抄来抄去的。当然,没有说别人讲的是错的,只是觉得,要是没有把东西说的让读者看...

    作者:Scofield
    链接:https://www.zhihu.com/question/35866596/answer/236886066
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
     

    so far till now, 我还没见到过将CRF讲的个明明白白的。一个都没。就不能不抄来抄去吗?
    我打算搞一个这样的版本,无门槛理解的。
    ——20170927

    陆陆续续把调研学习工作完成了,虽然历时有点久,现在put上来。评论里的同学也等不及了时不时催我,所以不敢怠慢啊……

    总结的还算比较体系化,蛮长的,请读者慢慢看,肯定有收获的。

    (好痛苦,这么多公式都要在知乎上重输;是在MD上写的,在知乎上没想到格式这么难看……)

    ——20180129


    概率图模型学习笔记:HMM、MEMM、CRF


    一、Preface

    二、Prerequisite

    2.1 概率图

    2.1.1 概览
    2.1.2 有向图 vs. 无向图
    2.1.3 马尔科夫假设&马尔科夫性
    2.2 判别式模型 vs. 生成式模型
    2.3 序列建模

    三、HMM

    3.1 理解HMM
    3.2 模型运行过程
    3.2.1 学习过程
    3.2.2 序列标注(解码)过程
    3.2.3 序列概率过程

    四、MEMM

    4.1 理解MEMM
    4.2 模型运行过程

    4.2.1 学习过程
    4.2.2 序列标注(解码)过程
    4.2.3 序列概率过程
    4.3 标注偏置?

    五、CRF

    5.1 理解CRF
    5.2 模型运行过程
    5.2.1 学习过程
    5.2.2 解码过程
    5.2.3 序列概率过程
    5.3 CRF++分析
    5.4 LSTM+CRF

    六、总结

    Referrence


    一、Preface

    之前刚接触NLP时做相关的任务,也必然地涉及到了序列处理任务,然后自然要接触到概率图模型。当时在全网搜中文资料,陆续失望地发现竟然真的没有讲得清楚的博文,发现基本是把李航老师书里或CRF tutorial等资料的文字论述和公式抄来抄去的。当然,没有说别人讲的是错的,只是觉得,要是没有把东西说的让读者看得懂,那也是没意义啊。或者有些吧,就是讲了一大堆的东西,貌似也明白了啥,但还是不能让我很好的理解CRF这些模型究竟是个啥,完了还是有一头雾水散不开的感觉。试想,一堆公式扔过来,没有个感性理解的过渡,怎么可能理解的了。我甚至觉得,如果博客让人看不懂,那说明要么自己没理解透要么就是思维不清晰讲不清楚。所以默想,深水区攻坚还是要靠自己,然后去做调研做research,所以就写了个这个学习记录。

    所以概率图的研究学习思考列入了我的任务清单。不过平时的时间又非常的紧,只能陆陆续续的思考着,所以时间拖得也真是长啊。

    这是个学习笔记。相比其他的学习模型,概率图貌似确实是比较难以理解的。这里我基本全部用自己的理解加上自己的语言习惯表达出来,off the official form,表达尽量接地气。我会尽量将我所有理解过程中的每个关键小细节都详细描述出来,以使对零基础的初学者友好。包括理论的来龙去脉,抽象具象化,模型的构成,模型的训练过程,会注重类比的学习。

    根据现有资料,我是按照概率图模型将HMM,MEMM,CRF放在这里一起对比学习。之所以把他们拿在一起,是因为他们都用于标注问题。并且之所以放在概率图框架下,是完全因为自己top-down思维模式使然。另外,概率图下还有很多的模型,这儿只学习标注模型。

    正儿八经的,我对这些个概率图模型有了彻悟,是从我明白了生成式模型与判别式模型的那一刻。一直在思考从概率图模型角度讲他们的区别到底在哪。

    另外,篇幅略显长,但咱们不要急躁,好好看完这篇具有良好的上下文的笔记,那肯定是能理解的,或者就多看几遍。

    个人学习习惯就是,要尽可能地将一群没有结构的知识点融会贯通,再用一条树状结构的绳将之串起来,结构化,就是说要成体系,这样把绳子头一拎所有的东西都能拿起来。学习嘛,应该要是一个熵减的过程,卓有成效的学习应该是混乱度越来越小!这个思维方式对我影响还是蛮大的。

    在正式内容之前,还是先要明确下面这一点,最好脑子里形成一个定势:

    统计机器学习所有的模型(个别instant model和优化算法以及其他的特种工程知识点除外)的工作流程都是如此:
    a.训练模型参数,得到模型(由参数唯一确定),
    b.预测给定的测试数据。
    拿这个流程去挨个学习模型,思路上会非常顺畅。这一点可参见我 另一篇文字介绍。

    除此之外,对初学者的关于机器学习的入门学习方式也顺带表达一下(empirical speaking):

    a.完整特征工程竞赛
    b.野博客理论入门理解
    c.再回到代码深入理解模型内部
    d.再跨理论,查阅经典理论巨作。这时感性理性都有一定高度,会遇到很多很大的理解上的疑惑,这时3大经典可能就可以发挥到最大作用了。

    很多beginer,就比如说学CRF模型,然后一上来就摆一套复杂的公式,什么我就问,这能理解的了吗?这是正确的开启姿势吗?当然了,也要怪那些博主,直接整一大堆核心公式,实际上读者的理解门槛可能就是一个过渡性的细枝末节而已。没有上下文的教育肯定是失败的(这一点我又想吐槽国内绝大部分本科的院校教育模式)。所以说带有完整上下文信息以及过程来龙去脉交代清楚才算到位吧。

    而不是一上来就死啃被人推荐的“经典资料”,这一点相信部分同学会理解。好比以前本科零基础学c++ JAVA,上来就看primr TIJ,结果浪费了时间精力一直在门外兜圈。总结方法吸取教训,应该快速上手代码,才是最高效的。经典最好是用来查阅的工具书,我目前是李航周志华和经典的那3本迭代轮询看了好多轮,经常会反复查询某些model或理论的来龙去脉;有时候要查很多相关的东西,看这些书还是难以贯通,然后发现有些人的博客写的会更容易去理解。所以另外,学习资料渠道也要充分才行。

    最后提示一下,请务必按照标题层级结构和目录一级一级阅读,防止跟丢。

     

    二、Prerequisite

    2.1 概率图

    之前刚接触CRF时,一上来试图越过一堆繁琐的概率图相关概念,不过sad to say, 这是后面的前驱知识,后面还得反过来补这个点。所以若想整体把握,系统地拿下这一块,应该还是要越过这块门槛的。

    当然了,一开始只需略略快速看一篇,后面可再返过来补查。

    2.1.1 概览

    在统计概率图(probability graph models)中,参考宗成庆老师的书,是这样的体系结构(个人非常喜欢这种类型的图):

    在概率图模型中,数据(样本)由公式 G=(V,E) 建模表示:

    • V 表示节点,即随机变量(放在此处的,可以是一个token或者一个label),具体地,用 Y = (y_{1}, {\cdots}, y_{n} ) 为随机变量建模,注意 Y 现在是代表了一批随机变量(想象对应一条sequence,包含了很多的token), P(Y) 为这些随机变量的分布;
    • E 表示边,即概率依赖关系。具体咋理解,还是要在后面结合HMM或CRF的graph具体解释。

    2.1.2 有向图 vs. 无向图

    上图可以看到,贝叶斯网络(信念网络)都是有向的,马尔科夫网络无向。所以,贝叶斯网络适合为有单向依赖的数据建模,马尔科夫网络适合实体之间互相依赖的建模。具体地,他们的核心差异表现在如何求 P=(Y) ,即怎么表示 Y=(y_{1},\cdots,y_{n}) 这个的联合概率。

    1. 有向图

    对于有向图模型,这么求联合概率: P(x_{1}, {\cdots}, x_{n} )=\prod_{i=0}P(x_{i} | \pi(x_{i}))

    举个例子,对于下面的这个有向图的随机变量(注意,这个图我画的还是比较广义的):

    应该这样表示他们的联合概率:

    P(x_{1}, {\cdots}, x_{n} )=P(x_{1})·P(x_{2}|x_{1} )·P(x_{3}|x_{2} )·P(x_{4}|x_{2} )·P(x_{5}|x_{3},x_{4} )

    应该很好理解吧。

    2. 无向图

    对于无向图,我看资料一般就指马尔科夫网络(注意,这个图我画的也是比较广义的)。

    如果一个graph太大,可以用因子分解将 P=(Y) 写为若干个联合概率的乘积。咋分解呢,将一个图分为若干个“小团”,注意每个团必须是“最大团”(就是里面任何两个点连在了一块,具体……算了不解释,有点“最大连通子图”的感觉),则有:

     

    P(Y )=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} )

     

    , 其中 Z(x) = \sum_{Y} \prod_{c}\psi_{c}(Y_{c} ) ,公式应该不难理解吧,归一化是为了让结果算作概率。

    所以像上面的无向图:

    P(Y )=\frac{1}{Z(x)} ( \psi_{1}(X_{1}, X_{3}, X_{4} ) · \psi_{2}(X_{2}, X_{3}, X_{4} ) )

    其中, \psi_{c}(Y_{c} ) 是一个最大团 C 上随机变量们的联合概率,一般取指数函数的:

    \psi_{c}(Y_{c} ) = e^{-E(Y_{c})} =e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)}

    好了,管这个东西叫做势函数。注意 e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} 是否有看到CRF的影子。

    那么概率无向图的联合概率分布可以在因子分解下表示为:

    P(Y )=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c} ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)}

    注意,这里的理解还蛮重要的,注意递推过程,敲黑板,这是CRF的开端!
    这个由Hammersly-Clifford law保证,具体不展开。

    2.1.3 马尔科夫假设&马尔科夫性

    这个也属于前馈知识。

    1. 马尔科夫假设

    额应该是齐次马尔科夫假设,这样假设:马尔科夫链 (x_{1},\cdots,x_{n}) 里的 x_{i} 总是只受 x_{i-1} 一个人的影响。
    马尔科夫假设这里相当于就是个1-gram。

    马尔科夫过程呢?即,在一个过程中,每个状态的转移只依赖于前n个状态,并且只是个n阶的模型。最简单的马尔科夫过程是一阶的,即只依赖于器哪一个状态。

    2. 马尔科夫性

    马尔科夫性是是保证或者判断概率图是否为概率无向图的条件。

    三点内容:a. 成对,b. 局部,c. 全局。

    我觉得这个不用展开。

    2.2 判别式(discriminative)模型 vs. 生成式(generative)模型

    在监督学习下,模型可以分为判别式模型与生成式模型。

    重点来了。上面有提到,我理解了HMM、CRF模型的区别是从理解了判别式模型与生成式模型的那刻,并且瞬间对其他的模型有一个恍然大悟。我记得是一年前就开始纠结这两者的区别,但我只能说,栽在了一些烂博客上,大部分都没有自己的insightful理解,也就是一顿官话,也真是难以理解。后来在知乎上一直琢磨别人的答案,然后某日早晨终于豁然开朗,就是这种感觉。

    好了,我要用自己的理解来转述两者的区别了below。

    先问个问题,根据经验,A批模型(神经网络模型、SVM、perceptron、LR、DT……)与B批模型(NB、LDA……),有啥区别不?(这个问题需要一些模型使用经验)应该是这样的:

    1. A批模型是这么工作的,他们直接将数据的Y(或者label),根据所提供的features,学习,最后画出了一个明显或者比较明显的边界(具体怎么做到的?通过复杂的函数映射,或者决策叠加等等mechanism),这一点线性LR、线性SVM应该很明显吧。

    2. B批模型是这么工作的,他们先从训练样本数据中,将所有的数据的分布情况摸透,然后最终确定一个分布,来作为我的所有的输入数据的分布,并且他是一个联合分布 P(X,Y) (注意 X 包含所有的特征 x_{i}Y 包含所有的label)。然后我来了新的样本数据(inference),好,通过学习来的模型的联合分布 P(X,Y) ,再结合新样本给的 X ,通过条件概率就能出来 Y
    P(Y|X) = \frac{P(X,Y)}{P(X)}

    好了,应该说清楚了。

    1. 判别式模型

    那么A批模型对应了判别式模型。根据上面的两句话的区别,可以知道判别模型的特征了,所以有句话说:判别模型是直接对 P(Y|X)建模,就是说,直接根据X特征来对Y建模训练。

    具体地,我的训练过程是确定构件 P(Y|X) 模型里面“复杂映射关系”中的参数,完了再去inference一批新的sample。

    所以判别式模型的特征总结如下:

    1. P(Y|X) 建模
    2. 对所有的样本只构建一个模型,确认总体判别边界
    3. 观测到输入什么特征,就预测最可能的label
    4. 另外,判别式的优点是:对数据量要求没生成式的严格,速度也会快,小数据量下准确率也会好些。

    2. 生成式模型

    同样,B批模型对应了生成式模型。并且需要注意的是,在模型训练中,我学习到的是X与Y的联合模型 P(X,Y) ,也就是说,我在训练阶段是只对 P(X,Y)建模,我需要确定维护这个联合概率分布的所有的信息参数。完了之后在inference再对新的sample计算 P(Y|X) ,导出 Y ,但这已经不属于建模阶段了。

    结合NB过一遍生成式模型的工作流程。学习阶段,建模: P(X,Y)=P(X|Y)P(Y) (当然,NB具体流程去隔壁参考),然后 P(Y|X) = \frac{P(X,Y)}{P(X)}
    另外,LDA也是这样,只是他更过分,需要确定很多个概率分布,而且建模抽样都蛮复杂的。

    所以生成式总结下有如下特点:

    1. P(X,Y) 建模
    2. 这里我们主要讲分类问题,所以是要对每个label( y_{i} )都需要建模,最终选择最优概率的label为结果,所以没有什么判别边界。(对于序列标注问题,那只需要构件一个model)
    3. 中间生成联合分布,并可生成采样数据。
    4. 生成式模型的优点在于,所包含的信息非常齐全,我称之为“上帝信息”,所以不仅可以用来输入label,还可以干其他的事情。生成式模型关注结果是如何产生的。但是生成式模型需要非常充足的数据量以保证采样到了数据本来的面目,所以速度相比之下,慢。

    这一点明白后,后面讲到的HMM与CRF的区别也会非常清晰。
    最后identity the picture below:

    2.3 序列建模

    为了号召零门槛理解,现在解释如何为序列问题建模。

    序列包括时间序列以及general sequence,但两者无异。连续的序列在分析时也会先离散化处理。常见的序列有如:时序数据、本文句子、语音数据、等等。

    广义下的序列有这些特点:

    • 节点之间有关联依赖性/无关联依赖性
    • 序列的节点是随机的/确定的
    • 序列是线性变化/非线性的
    • ……

    对不同的序列有不同的问题需求,常见的序列建模方法总结有如下:

    1. 拟合,预测未来节点(或走势分析):

    a. 常规序列建模方法:AR、MA、ARMA、ARIMA

    b. 回归拟合

    c. Neural Networks

    2. 判断不同序列类别,即分类问题:HMM、CRF、General Classifier(ML models、NN models)

    3. 不同时序对应的状态的分析,即序列标注问题:HMM、CRF、RecurrentNNs

    在本篇文字中,我们只关注在2. & 3.类问题下的建模过程和方法。

     

    三、HMM

    最早接触的是HMM。较早做过一个项目,关于声波手势识别,跟声音识别的机制一样,使用的正是HMM的一套方法。后来又用到了kalman filter,之后做序列标注任务接触到了CRF,所以整个概率图模型还是接触的方面还蛮多。

    3.1 理解HMM

    在2.2、2.3中提序列的建模问题时,我们只是讨论了常规的序列数据,e.g., (X_{1},\cdots,X_{n}) ,像2.3的图片那样。像这种序列一般用马尔科夫模型就可以胜任。实际上我们碰到的更多的使用HMM的场景是每个节点 X_{i} 下还附带着另一个节点 Y_{i} ,正所谓隐含马尔科夫模型,那么除了正常的节点,还要将隐含状态节点也得建模进去。正儿八经地,将 X_{i} 、 Y_{i} 换成 i_{i} 、o_{i} ,并且他们的名称变为状态节点、观测节点。状态节点正是我的隐状态。

    HMM属于典型的生成式模型。对照2.1的讲解,应该是要从训练数据中学到数据的各种分布,那么有哪些分布呢以及是什么呢?直接正面回答的话,正是HMM的5要素,其中有3个就是整个数据的不同角度的概率分布:

    • N ,隐藏状态集 N = \lbrace q_{1}, \cdots, q_{N} \rbrace , 我的隐藏节点不能随意取,只能限定取包含在隐藏状态集中的符号。
    • M ,观测集 M = \lbrace v_{1}, \cdots, v_{M} \rbrace , 同样我的观测节点不能随意取,只能限定取包含在观测状态集中的符号。
    • A ,状态转移概率矩阵,这个就是其中一个概率分布。他是个矩阵, A= [a_{ij}]_{N \times N} (N为隐藏状态集元素个数),其中 a_{ij} = P(i_{t+1}|i_{t}), i_{t} 即第i个隐状态节点,即所谓的状态转移嘛。
    • B ,观测概率矩阵,这个就是另一个概率分布。他是个矩阵, B = [b_{ij}]_{N \times M} (N为隐藏状态集元素个数,M为观测集元素个数),其中 b_{ij} = P(o_{t}|i_{t}), o_{t} 即第i个观测节点, i_{t} 即第i个隐状态节点,即所谓的观测概率(发射概率)嘛。
    • π ,在第一个隐状态节点 i_{t} ,我得人工单独赋予,我第一个隐状态节点的隐状态是 N 中的每一个的概率分别是多少,然后 π 就是其概率分布。

    所以图看起来是这样的:

    看的很清楚,我的模型先去学习要确定以上5要素,之后在inference阶段的工作流程是:首先,隐状态节点 i_{t} 是不能直接观测到的数据节点, o_{t} 才是能观测到的节点,并且注意箭头的指向表示了依赖生成条件关系, i_{t} 在A的指导下生成下一个隐状态节点 i_{t+1} ,并且 i_{t}B 的指导下生成依赖于该 i_{t} 的观测节点 o_{t} , 并且我只能观测到序列 (o_{1}, \cdots, o_{i})

    好,举例子说明(序列标注问题,POS,标注集BES):

    input: "学习出一个模型,然后再预测出一条指定"

    expected output: 学/B 习/E 出/S 一/B 个/E 模/B 型/E ,/S 然/B 后/E 再/E 预/B 测/E ……

    其中,input里面所有的char构成的字表,形成观测集 M ,因为字序列在inference阶段是我所能看见的;标注集BES构成隐藏状态集 N ,这是我无法直接获取的,也是我的预测任务;至于 A、B、π ,这些概率分布信息(上帝信息)都是我在学习过程中所确定的参数。

    然后一般初次接触的话会疑问:为什么要这样?……好吧,就应该是这样啊,根据具有同时带着隐藏状态节点和观测节点的类型的序列,在HMM下就是这样子建模的。

    下面来点高层次的理解:

    1. 根据概率图分类,可以看到HMM属于有向图,并且是生成式模型,直接对联合概率分布建模 P(O,I) = \sum_{t=1}^{T}P(O_{t} | O_{t-1})P(I_{t} | O_{t}) (注意,这个公式不在模型运行的任何阶段能体现出来,只是我们都去这么来表示HMM是个生成式模型,他的联合概率 P(O,I) 就是这么计算的)。
    2. 并且B中 b_{ij} = P(o_{t}|i_{t}) ,这意味着o对i有依赖性。
    3. 在A中, a_{ij} = P(i_{t+1}|i_{t}) ,也就是说只遵循了一阶马尔科夫假设,1-gram。试想,如果数据的依赖超过1-gram,那肯定HMM肯定是考虑不进去的。这一点限制了HMM的性能。

    3.2 模型运行过程

    模型的运行过程(工作流程)对应了HMM的3个问题。

    3.2.1 学习训练过程

    对照2.1的讲解,HMM学习训练的过程,就是找出数据的分布情况,也就是模型参数的确定。

    主要学习算法按照训练数据除了观测状态序列 (o_{1}, \cdots, o_{i}) 是否还有隐状态序列 (i_{1}, \cdots, i_{i}) 分为:

    • 极大似然估计, with 隐状态序列
    • Baum-Welch(前向后向), without 隐状态序列

    感觉不用做很多的介绍,都是很实实在在的算法,看懂了就能理解。简要提一下。

    1. 极大似然估计

    一般做NLP的序列标注等任务,在训练阶段肯定是有隐状态序列的。所以极大似然估计法是非常常用的学习算法,我见过的很多代码里面也是这么计算的。比较简单。

    • step1. 算A

    \hat{a_{ij}} = \frac{A_{ij}}{\sum_{j=1}^{N}A_{ij}}

    • step2. 算B

    \hat{b_{j}}(k) = \frac{B_{jk}}{\sum_{k=1}^{M}B_{jk}}

    • step3. 直接估计 π

    比如说,在代码里计算完了就是这样的:

     

    2. Baum-Welch(前向后向)

    就是一个EM的过程,如果你对EM的工作流程有经验的话,对这个Baum-Welch一看就懂。EM的过程就是初始化一套值,然后迭代计算,根据结果再调整值,再迭代,最后收敛……好吧,这个理解是没有捷径的,去隔壁钻研EM吧。

    这里只提一下核心。因为我们手里没有隐状态序列 (i_{1}, \cdots, i_{i}) 信息,所以我先必须给初值 a_{ij}^{0}, b_{j}(k)^{0}, \pi^{0} ,初步确定模型,然后再迭代计算出 a_{ij}^{n}, b_{j}(k)^{n}, \pi^{n} ,中间计算过程会用到给出的观测状态序列 (o_{1}, \cdots, o_{i}) 。另外,收敛性由EM的XXX定理保证。

    3.2.2 序列标注(解码)过程

    好了,学习完了HMM的分布参数,也就确定了一个HMM模型。需要注意的是,这个HMM是对我这一批全部的数据进行训练所得到的参数。

    序列标注问题也就是“预测过程”,通常称为解码过程。对应了序列建模问题3.。对于序列标注问题,我们只需要学习出一个HMM模型即可,后面所有的新的sample我都用这一个HMM去apply。

    我们的目的是,在学习后已知了 P(Q,O) ,现在要求出 P(Q|O) ,进一步

    Q_{max} = argmax_{allQ}\frac{P(Q,O)}{P(O)}

    再直白点就是,我现在要在给定的观测序列下找出一条隐状态序列,条件是这个隐状态序列的概率是最大的那个。

     

    具体地,都是用Viterbi算法解码,是用DP思想减少重复的计算。Viterbi也是满大街的,不过要说的是,Viterbi不是HMM的专属,也不是任何模型的专属,他只是恰好被满足了被HMM用来使用的条件。谁知,现在大家都把Viterbi跟HMM捆绑在一起了, shame。

    Viterbi计算有向无环图的一条最大路径,应该还好理解。如图:

    关键是注意,每次工作热点区只涉及到t 与 t-1,这对应了DP的无后效性的条件。如果对某些同学还是很难理解,请参考这个答案下@Kiwee的回答吧。

    3.2.3 序列概率过程

    我通过HMM计算出序列的概率又有什么用?针对这个点我把这个问题详细说一下。

    实际上,序列概率过程对应了序列建模问题2.,即序列分类。
    在3.2.2第一句话我说,在序列标注问题中,我用一批完整的数据训练出了一支HMM模型即可。好,那在序列分类问题就不是训练一个HMM模型了。我应该这么做(结合语音分类识别例子):

    目标:识别声音是A发出的还是B发出的。
    HMM建模过程:
    1. 训练:我将所有A说的语音数据作为dataset_A,将所有B说的语音数据作为dataset_B(当然,先要分别对dataset A ,B做预处理encode为元数据节点,形成sequences),然后分别用dataset_A、dataset_B去训练出HMM_A/HMM_B
    2. inference:来了一条新的sample(sequence),我不知道是A的还是B的,没问题,分别用HMM_A/HMM_B计算一遍序列的概率得到 P_{A}(S)、P_{B}(S) ,比较两者大小,哪个概率大说明哪个更合理,更大概率作为目标类别。

     

    所以,本小节的理解重点在于,如何对一条序列计算其整体的概率。即目标是计算出 P(O|λ) 。这个问题前辈们在他们的经典中说的非常好了,比如参考李航老师整理的:

    • 直接计算法(穷举搜索)
    • 前向算法
    • 后向算法

    后面两个算法采用了DP思想,减少计算量,即每一次直接引用前一个时刻的计算结果以避免重复计算,跟Viterbi一样的技巧。

    还是那句,因为这篇文档不是专门讲算法细节的,所以不详细展开这些。毕竟,所有的科普HMM、CRF的博客貌似都是在扯这些算法,妥妥的街货,就不搬运了。

     

    四、MEMM

    MEMM,即最大熵马尔科夫模型,这个是在接触了HMM、CRF之后才知道的一个模型。说到MEMM这一节时,得转换思维了,因为现在这MEMM属于判别式模型。

    不过有一点很尴尬,MEMM貌似被使用或者讲解引用的不及HMM、CRF。

    4.1 理解MEMM

    这里还是啰嗦强调一下,MEMM正因为是判别模型,所以不废话,我上来就直接为了确定边界而去建模,比如说序列求概率(分类)问题,我直接考虑找出函数分类边界。这一点跟HMM的思维方式发生了很大的变化,如果不对这一点有意识,那么很难理解为什么MEMM、CRF要这么做。

    HMM中,观测节点 o_{i} 依赖隐藏状态节点 i_{i} ,也就意味着我的观测节点只依赖当前时刻的隐藏状态。但在更多的实际场景下,观测序列是需要很多的特征来刻画的,比如说,我在做NER时,我的标注 i_{i} 不仅跟当前状态 o_{i} 相关,而且还跟前后标注 o_{j}(j \neq i) 相关,比如字母大小写、词性等等。

    为此,提出来的MEMM模型就是能够直接允许“定义特征”,直接学习条件概率,即 P(i_{i}|i_{i-1},o_{i}) (i = 1,\cdots,n) , 总体为:

    P(I|O) = \prod_{t=1}^{n}P(i_{i}|i_{i-1},o_{i}), i = 1,\cdots,n

    并且, P(i|i^{'},o) 这个概率通过最大熵分类器建模(取名MEMM的原因):

    P(i|i^{'},o) = \frac{1}{Z(o,i^{'})} exp(\sum_{a})\lambda_{a}f_{a}(o,i)

    重点来了,这是ME的内容,也是理解MEMM的关键: Z(o,i^{'}) 这部分是归一化; f_{a}(o,i)特征函数,具体点,这个函数是需要去定义的; λ 是特征函数的权重,这是个未知参数,需要从训练阶段学习而得。

    比如我可以这么定义特征函数:

    \begin{equation} f_{a}(o,i) = \begin{cases} 1& \text{满足特定条件},\\ 0& \text{other} \end{cases} \end{equation}

    其中,特征函数 f_{a}(o,i) 个数可任意制定, (a = 1, \cdots, n)

     

    所以总体上,MEMM的建模公式这样:

    P(I|O) = \prod_{t=1}^{n}\frac{ exp(\sum_{a})\lambda_{a}f_{a}(o,i) }{Z(o,i_{i-1})} , i = 1,\cdots,n

     

    是的,公式这部分之所以长成这样,是由ME模型决定的。

    请务必注意,理解判别模型定义特征两部分含义,这已经涉及到CRF的雏形了。

    所以说,他是判别式模型,直接对条件概率建模。 上图:

    MEMM需要两点注意:

    1. 与HMM的 o_{i} 依赖 i_{i} 不一样,MEMM当前隐藏状态 i_{i} 应该是依赖当前时刻的观测节点 o_{i} 和上一时刻的隐藏节点 i_{i-1}
    2. 需要注意,之所以图的箭头这么画,是由MEMM的公式决定的,而公式是creator定义出来的。

    好了,走一遍完整流程。

    step1. 先预定义特征函数 f_{a}(o,i)
    step2. 在给定的数据上,训练模型,确定参数,即确定了MEMM模型
    step3. 用确定的模型做序列标注问题或者序列求概率问题。

    4.2 模型运行过程

    MEMM模型的工作流程也包括了学习训练问题、序列标注问题、序列求概率问题。

    4.2.1 学习训练过程

    一套MEMM由一套参数唯一确定,同样地,我需要通过训练数据学习这些参数。MEMM模型很自然需要学习里面的特征权重λ。

    不过跟HMM不用的是,因为HMM是生成式模型,参数即为各种概率分布元参数,数据量足够可以用最大似然估计。而判别式模型是用函数直接判别,学习边界,MEMM即通过特征函数来界定。但同样,MEMM也有极大似然估计方法、梯度下降、牛顿迭代发、拟牛顿下降、BFGS、L-BFGS等等。各位应该对各种优化方法有所了解的。

    嗯,具体详细求解过程貌似问题不大。

    4.2.2 序列标注过程

    还是跟HMM一样的,用学习好的MEMM模型,在新的sample(观测序列 o_{1}, \cdots, o_{i} )上找出一条概率最大最可能的隐状态序列 i_{1}, \cdots, i_{i}

    只是现在的图中的每个隐状态节点的概率求法有一些差异而已,正确将每个节点的概率表示清楚,路径求解过程还是一样,采用viterbi算法。

    4.2.3 序列求概率过程

    跟HMM举的例子一样的,也是分别去为每一批数据训练构建特定的MEMM,然后根据序列在每个MEMM模型的不同得分概率,选择最高分数的模型为wanted类别。

    应该可以不用展开,吧……

    4.3 标注偏置?

    MEMM讨论的最多的是他的labeling bias 问题。

    1. 现象

    是从街货上烤过来的……

    用Viterbi算法解码MEMM,状态1倾向于转换到状态2,同时状态2倾向于保留在状态2。 解码过程细节(需要会viterbi算法这个前提):

    P(1-> 1-> 1-> 1)= 0.4 x 0.45 x 0.5 = 0.09 ,
    P(2->2->2->2)= 0.2 X 0.3 X 0.3 = 0.018,
    P(1->2->1->2)= 0.6 X 0.2 X 0.5 = 0.06,
    P(1->1->2->2)= 0.4 X 0.55 X 0.3 = 0.066

    但是得到的最优的状态转换路径是1->1->1->1,为什么呢?因为状态2可以转换的状态比状态1要多,从而使转移概率降低,即MEMM倾向于选择拥有更少转移的状态。

    2. 解释原因

    直接看MEMM公式:

    P(I|O) = \prod_{t=1}^{n}\frac{ exp(\sum_{a})\lambda_{a}f_{a}(o,i) }{Z(o,i_{i-1})} , i = 1,\cdots,n

    ∑ 求和的作用在概率中是归一化,但是这里归一化放在了指数内部,管这叫local归一化。 来了,viterbi求解过程,是用dp的状态转移公式(MEMM的没展开,请参考CRF下面的公式),因为是局部归一化,所以MEMM的viterbi的转移公式的第二部分出现了问题,导致dp无法正确的递归到全局的最优。

    \delta_{i+1} = max_{1 \le j \le m}\lbrace \delta_{i}(I) + \sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i) \rbrace

     

    五、CRF

    我觉得一旦有了一个清晰的工作流程,那么按部就班地,没有什么很难理解的地方,因为整体框架已经胸有成竹了,剩下了也只有添砖加瓦小修小补了。有了上面的过程基础,CRF也是类似的,只是有方法论上的细微区别。

    5.1 理解CRF

    请看第一张概率图模型构架图,CRF上面是马尔科夫随机场(马尔科夫网络),而条件随机场是在给定的随机变量 X (具体,对应观测序列 o_{1}, \cdots, o_{i} )条件下,随机变量 Y (具体,对应隐状态序列 i_{1}, \cdots, i_{i} 的马尔科夫随机场。
    广义的CRF的定义是: 满足 P(Y_{v}|X,Y_{w},w \neq v) = P(Y_{v}|X,Y_{w},w \sim v) 的马尔科夫随机场叫做条件随机场(CRF)。

    不过一般说CRF为序列建模,就专指CRF线性链(linear chain CRF):

    在2.1.2中有提到过,概率无向图的联合概率分布可以在因子分解下表示为:

    P(Y | X)=\frac{1}{Z(x)} \prod_{c}\psi_{c}(Y_{c}|X ) = \frac{1}{Z(x)} \prod_{c} e^{\sum_{k}\lambda_{k}f_{k}(c,y|c,x)} = \frac{1}{Z(x)} e^{\sum_{c}\sum_{k}\lambda_{k}f_{k}(y_{i},y_{i-1},x,i)}

    而在线性链CRF示意图中,每一个( I_{i} \sim O_{i} )对为一个最大团,即在上式中 c = i 。并且线性链CRF满足 P(I_{i}|O,I_{1},\cdots, I_{n}) = P(I_{i}|O,I_{i-1},I_{i+1})

    所以CRF的建模公式如下:

    P(I | O)=\frac{1}{Z(O)} \prod_{i}\psi_{i}(I_{i}|O ) = \frac{1}{Z(O)} \prod_{i} e^{\sum_{k}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)} = \frac{1}{Z(O)} e^{\sum_{i}\sum_{k}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)}

    我要敲黑板了,这个公式是非常非常关键的,注意递推过程啊,我是怎么从 ∏ 跳到 e^{\sum} 的。

    不过还是要多啰嗦一句,想要理解CRF,必须判别式模型的概念要深入你心。正因为是判别模型,所以不废话,我上来就直接为了确定边界而去建模,因为我创造出来就是为了这个分边界的目的的。比如说序列求概率(分类)问题,我直接考虑找出函数分类边界。所以才为什么会有这个公式。所以再看到这个公式也别懵逼了,he was born for discriminating the given data from different classes. 就这样。不过待会还会具体介绍特征函数部分的东西。

     

    除了建模总公式,关键的CRF重点概念在MEMM中已强调过:判别式模型特征函数

    1. 特征函数

    上面给出了CRF的建模公式:

    P(I | O)=\frac{1}{Z(O)} e^{\sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)}

    • 下标i表示我当前所在的节点(token)位置。
    • 下标k表示我这是第几个特征函数,并且每个特征函数都附属一个权重 \lambda_{k} ,也就是这么回事,每个团里面,我将为 token_{i} 构造M个特征,每个特征执行一定的限定作用,然后建模时我再为每个特征函数加权求和。
    • Z(O) 是用来归一化的,为什么?想想LR以及softmax为何有归一化呢,一样的嘛,形成概率值。
    • 再来个重要的理解。 P(I|O) 这个表示什么?具体地,表示了在给定的一条观测序列 O=(o_{1},\cdots, o_{i}) 条件下,我用CRF所求出来的隐状态序列 I=(i_{1},\cdots, i_{i}) 的概率,注意,这里的I是一条序列,有多个元素(一组随机变量),而至于观测序列 O=(o_{1},\cdots, o_{i}) ,它可以是一整个训练语料的所有的观测序列;也可以是在inference阶段的一句sample,比如说对于序列标注问题,我对一条sample进行预测,可能能得到 P_{j}(I | O)(j=1,…,J)J条隐状态I,但我肯定最终选的是最优概率的那条(by viterbi)。这一点希望你能理解。

    对于CRF,可以为他定义两款特征函数:转移特征&状态特征。 我们将建模总公式展开:

    P(I | O)=\frac{1}{Z(O)} e^{\sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)}=\frac{1}{Z(O)} e^{ [ \sum_{i}^{T}\sum_{j}^{J}\lambda_{j}t_{j}(O,I_{i-1},I_{i},i) + \sum_{i}^{T}\sum_{l}^{L}\mu_{l}s_{l}(O,I_{i},i) ] }

     

    其中:

    • t_{j} 为i处的转移特征,对应权重 \lambda_{j} ,每个 token_{i} 都有J个特征,转移特征针对的是前后token之间的限定。
      • 举个例子:

    \begin{equation} t_{k=1}(o,i) = \begin{cases} 1& \text{满足特定转移条件,比如前一个token是‘I’},\\ 0& \text{other} \end{cases} \end{equation}

    • sl为i处的状态特征,对应权重μl,每个tokeni都有L个特征
      • 举个例子:

    \begin{equation} s_{l=1}(o,i) = \begin{cases} 1& \text{满足特定状态条件,比如当前token的POS是‘V’},\\ 0& \text{other} \end{cases} \end{equation}

     

    不过一般情况下,我们不把两种特征区别的那么开,合在一起:

    P(I | O)=\frac{1}{Z(O)} e^{\sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)}

     

    满足特征条件就取值为1,否则没贡献,甚至你还可以让他打负分,充分惩罚。

    再进一步理解的话,我们需要把特征函数部分抠出来:

    Score = \sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i)

     

    是的,我们为 token_{i} 打分,满足条件的就有所贡献。最后将所得的分数进行log线性表示,求和后归一化,即可得到概率值……完了又扯到了log线性模型。现在稍作解释:

    log-linear models take the following form:
    P(y|x;\omega) = \frac{ exp(\omega·\phi(x,y)) }{ \sum_{y^{'}\in Y }exp(\omega·\phi(x,y^{‘})) }

    我觉得对LR或者sotfmax熟悉的对这个应该秒懂。然后CRF完美地满足这个形式,所以又可以归入到了log-linear models之中。

    5.2 模型运行过程

    模型的工作流程,跟MEMM是一样的:

    • step1. 先预定义特征函数 f_{a}(o,i)
    • step2. 在给定的数据上,训练模型,确定参数 \lambda_{k}
    • step3. 用确定的模型做序列标注问题或者序列求概率问题

    可能还是没做到100%懂,结合例子说明:

    ……

    5.2.1 学习训练过程

    一套CRF由一套参数λ唯一确定(先定义好各种特征函数)。

    同样,CRF用极大似然估计方法、梯度下降、牛顿迭代、拟牛顿下降、IIS、BFGS、L-BFGS等等。各位应该对各种优化方法有所了解的。其实能用在log-linear models上的求参方法都可以用过来。

    嗯,具体详细求解过程貌似问题不大。

    5.2.2 序列标注过程

    还是跟HMM一样的,用学习好的CRF模型,在新的sample(观测序列 o_{1}, \cdots, o_{i} )上找出一条概率最大最可能的隐状态序列 i_{1}, \cdots, i_{i}

    只是现在的图中的每个隐状态节点的概率求法有一些差异而已,正确将每个节点的概率表示清楚,路径求解过程还是一样,采用viterbi算法。

    啰嗦一下,我们就定义i处的局部状态为 \delta_{i}(I) ,表示在位置i处的隐状态的各种取值可能为I,然后递推位置i+1处的隐状态,写出来的DP转移公式为:

    \delta_{i+1} = max_{1 \le j \le m}\lbrace \delta_{i}(I) + \sum_{i}^{T}\sum_{k}^{M}\lambda_{k}f_{k}(O,I_{i-1},I_{i},i) \rbrace

    这里没写规范因子 Z(O) 是因为不规范化不会影响取最大值后的比较。

    具体还是不展开为好。

    5.2.3 序列求概率过程

    跟HMM举的例子一样的,也是分别去为每一批数据训练构建特定的CRF,然后根据序列在每个MEMM模型的不同得分概率,选择最高分数的模型为wanted类别。只是貌似很少看到拿CRF或者MEMM来做分类的,直接用网络模型不就完了不……

    应该可以不用展开,吧……

    5.3 CRF++分析

    本来做task用CRF++跑过baseline,后来在对CRF做调研时,非常想透析CRF++的工作原理,以identify以及verify做的各种假设猜想。当然,也看过其他的CRF实现源码。

    所以干脆写到这里来,结合CRF++实例讲解过程。

    有一批语料数据,并且已经tokenized好了:

    Nuclear
    theory
    devoted
    major
    efforts
    ……

    并且我先确定了13个标注元素:

    B_MAT
    B_PRO
    B_TAS
    E_MAT
    E_PRO
    E_TAS
    I_MAT
    I_PRO
    I_TAS
    O
    S_MAT
    S_PRO
    S_TAS

    1. 定义模板

    按道理应该是定义特征函数才对吧?好的,在CRF++下,应该是先定义特征模板,然后用模板自动批量产生大量的特征函数。我之前也蛮confused的,用完CRF++还以为模板就是特征,后面就搞清楚了:每一条模板将在每一个token处生产若干个特征函数。

    CRF++的模板(template)有U系列(unigram)、B系列(bigram),不过我至今搞不清楚B系列的作用,因为U模板都可以完成2-gram的作用。

    U00:%x[-2,0]
    U01:%x[-1,0]
    U02:%x[0,0]
    U03:%x[1,0]
    U04:%x[2,0]

    U05:%x[-2,0]/%x[-1,0]/%x[0,0]
    U06:%x[-1,0]/%x[0,0]/%x[1,0]
    U07:%x[0,0]/%x[1,0]/%x[2,0]
    U08:%x[-1,0]/%x[0,0]
    U09:%x[0,0]/%x[1,0]

    B

    所以,U00 - U09 我定义了10个模板。

    2. 产生特征函数

    是的,会产生大量的特征。 U00 - U04的模板产生的是状态特征函数;U05 - U09的模板产生的是转移特征函数。

    在CRF++中,每个特征都会try每个标注label(这里有13个),总共将生成 N * L = i * k^{'} * L 个特征函数以及对应的权重出来。N表示每一套特征函数 N= i * k^{'} ,L表示标注集元素个数。

    比如训练好的CRF模型的部分特征函数是这样存储的:

    22607 B
    790309 U00:%
    3453892 U00:%)
    2717325 U00:&
    2128269 U00:'t
    2826239 U00:(0.3534
    2525055 U00:(0.593–1.118
    197093 U00:(1)
    2079519 U00:(1)L=14w2−12w−FμνaFaμν
    2458547 U00:(1)δn=∫−∞En+1ρ˜(E)dE−n
    1766024 U00:(1.0g
    2679261 U00:(1.1wt%)
    1622517 U00:(100)
    727701 U00:(1000–5000A)
    2626520 U00:(10a)
    2626689 U00:(10b)
    ……
    2842814 U07:layer/thicknesses/Using
    2847533 U07:layer/thicknesses/are
    2848651 U07:layer/thicknesses/in
    331539 U07:layer/to/the
    1885871 U07:layer/was/deposited
    ……(数量非常庞大)

    其实也就是对应了这样些个特征函数:

    func1 = if (output = B and feature="U02:一") return 1 else return 0
    func2 = if (output = M and feature="U02:一") return 1 else return 0
    func3 = if (output = E and feature="U02:一") return 1 else return 0
    func4 = if (output = S and feature="U02:一") return 1 else return 0

    比如模板U06会从语料中one by one逐句抽出这些各个特征:

    一/个/人/……
    个/人/走/……

    3. 求参

    对上述的各个特征以及初始权重进行迭代参数学习。

    在CRF++ 训练好的模型里,权重是这样的:

    0.3972716048310705
    0.5078838237171732
    0.6715316559507898
    -0.4198827647512405
    -0.4233310655891150
    -0.4176580083832543
    -0.4860489836004728
    -0.6156475863742051
    -0.6997919485753300
    0.8309956709647820
    0.3749695682658566
    0.2627347894057647
    0.0169732441379157
    0.3972716048310705
    0.5078838237171732
    0.6715316559507898
    ……(数量非常庞大,与每个label的特征函数对应,我这有300W个)

    4. 预测解码

    结果是这样的:

    Nuclear B TAS
    theory E
    TAS
    devoted O
    major O
    efforts O
    ……

    5.4 LSTM+CRF

    LSTM+CRF这个组合其实我在知乎上答过问题,然后顺便可以整合到这里来。

    1、perspectively

    大家都知道,LSTM已经可以胜任序列标注问题了,为每个token预测一个label(LSTM后面接:分类器);而CRF也是一样的,为每个token预测一个label。

    但是,他们的预测机理是不同的。CRF是全局范围内统计归一化的条件状态转移概率矩阵,再预测出一条指定的sample的每个token的label;LSTM(RNNs,不区分here)是依靠神经网络的超强非线性拟合能力,在训练时将samples通过复杂到让你窒息的高阶高纬度异度空间的非线性变换,学习出一个模型,然后再预测出一条指定的sample的每个token的label。

    2、LSTM+CRF

    既然LSTM都OK了,为啥researchers搞一个LSTM+CRF的hybrid model?

    哈哈,因为a single LSTM预测出来的标注有问题啊!举个segmentation例子(BES; char level),plain LSTM 会搞出这样的结果:

    input: "学习出一个模型,然后再预测出一条指定"
    expected output: 学/B 习/E 出/S 一/B 个/E 模/B 型/E ,/S 然/B 后/E 再/E 预/B 测/E ……
    real output: 学/B 习/E 出/S 一/B 个/B 模/B 型/E ,/S 然/B 后/B 再/E 预/B 测/E ……

    看到不,用LSTM,整体的预测accuracy是不错indeed, 但是会出现上述的错误:在B之后再来一个B。这个错误在CRF中是不存在的,因为CRF的特征函数的存在就是为了对given序列观察学习各种特征(n-gram,窗口),这些特征就是在限定窗口size下的各种词之间的关系。然后一般都会学到这样的一条规律(特征):B后面接E,不会出现E。这个限定特征会使得CRF的预测结果不出现上述例子的错误。当然了,CRF还能学到更多的限定特征,那越多越好啊!

    好了,那就把CRF接到LSTM上面,把LSTM在timestep上把每一个hiddenstate的tensor输入给CRF,让LSTM负责在CRF的特征限定下,依照新的loss function,学习出一套新的非线性变换空间。

    最后,不用说,结果还真是好多了呢。

    LSTM+CRF codes, here. Go just take it.

     

    六、总结

    1. 总体对比

    应该看到了熟悉的图了,现在看这个图的话,应该可以很清楚地get到他所表达的含义了。这张图的内容正是按照生成式&判别式来区分的,NB在sequence建模下拓展到了HMM;LR在sequence建模下拓展到了CRF。

    2. HMM vs. MEMM vs. CRF

    将三者放在一块做一个总结:

    1. HMM -> MEMM: HMM模型中存在两个假设:一是输出观察值之间严格独立,二是状态的转移过程中当前状态只与前一状态有关。但实际上序列标注问题不仅和单个词相关,而且和观察序列的长度,单词的上下文,等等相关。MEMM解决了HMM输出独立性假设的问题。因为HMM只限定在了观测与状态之间的依赖,而MEMM引入自定义特征函数,不仅可以表达观测之间的依赖,还可表示当前观测与前后多个状态之间的复杂依赖。
    2. MEMM -> CRF:
    • CRF不仅解决了HMM输出独立性假设的问题,还解决了MEMM的标注偏置问题,MEMM容易陷入局部最优是因为只在局部做归一化,而CRF统计了全局概率,在做归一化时考虑了数据在全局的分布,而不是仅仅在局部归一化,这样就解决了MEMM中的标记偏置的问题。使得序列标注的解码变得最优解。
    • HMM、MEMM属于有向图,所以考虑了x与y的影响,但没讲x当做整体考虑进去(这点问题应该只有HMM)。CRF属于无向图,没有这种依赖性,克服此问题。

     

    3. Machine Learning models vs. Sequential models

    为了一次将概率图模型理解的深刻到位,我们需要再串一串,更深度与原有的知识体系融合起来。

    机器学习模型,按照学习的范式或方法,以及加上自己的理解,给常见的部分的他们整理分了分类(主流上,都喜欢从训练样本的歧义型分,当然也可以从其他角度来):

    一、监督:{
    
    1.1 分类算法(线性和非线性):{
    
        感知机
    
        KNN
    
        概率{
            朴素贝叶斯(NB)
            Logistic Regression(LR)
            最大熵MEM(与LR同属于对数线性分类模型)
        }
    
        支持向量机(SVM)
    
        决策树(ID3、CART、C4.5)
    
        assembly learning{
            Boosting{
                Gradient Boosting{
                    GBDT
                    xgboost(传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题);xgboost是Gradient Boosting的一种高效系统实现,并不是一种单一算法。)
                }
                AdaBoost
            }   
            Bagging{
                随机森林
            }
            Stacking
        }
    
        ……
    }
    
    1.2 概率图模型:{
        HMM
        MEMM(最大熵马尔科夫)
        CRF
        ……
    }
    
    
    1.3 回归预测:{
        线性回归
        树回归
        Ridge岭回归
        Lasso回归
        ……
    }
    
    ……  
    }
    
    
    二、非监督:{
    2.1 聚类:{
        1. 基础聚类
            K—mean
            二分k-mean
            K中值聚类
            GMM聚类
        2. 层次聚类
        3. 密度聚类
        4. 谱聚类()
    }
    
    2.2 主题模型:{
        pLSA
        LDA隐含狄利克雷分析
    }
    
    2.3 关联分析:{
        Apriori算法
        FP-growth算法
    }
    
    2.4 降维:{
        PCA算法
        SVD算法
        LDA线性判别分析
        LLE局部线性嵌入
    }
    
    2.5 异常检测:
    ……
    }
    
    三、半监督学习
    
    四、迁移学习
    

     

    (注意到,没有把神经网络体系加进来。因为NNs的范式很灵活,不太适用这套分法,largely, off this framework)

    Generally speaking,机器学习模型,尤其是有监督学习,一般是为一条sample预测出一个label,作为预测结果。 但与典型常见的机器学习模型不太一样,序列模型(概率图模型)是试图为一条sample里面的每个基本元数据分别预测出一个label。这一点,往往是beginner伊始难以理解的。

    具体的实现手段差异,就是:ML models通过直接预测得出label;Sequential models是给每个token预测得出label还没完,还得将他们每个token对应的labels进行组合,具体的话,用viterbi来挑选最好的那个组合。

     

    over

     

     

    有了这道开胃菜,接下来,读者可以完成这些事情:完善细节算法、阅读原著相关论文达到彻底理解、理解相关拓展概念、理论创新……

     

    hope those hlpe!

    欢迎留言!

    有错误之处请多多指正,谢谢!

     

    Referrences:

    《统计学习方法》,李航

    《统计自然语言处理》,宗成庆

    《 An Introduction to Conditional Random Fields for Relational Learning》, Charles Sutton, Andrew McCallum

    《Log-Linear Models, MEMMs, and CRFs》,ichael Collins

     

    如何用简单易懂的例子解释条件随机场(CRF)模型?它和HMM有什么区别?

    【中文分词】最大熵马尔可夫模型MEMM - Treant - 博客园

    【中文分词】最大熵马尔可夫模型MEMM - Treant - 博客园

    timvieira/crf

    shawntan/python-crf

    Log-linear Models and Conditional Random Fields

    如何轻松愉快地理解条件随机场(CRF)?

    条件随机场CRF(三) 模型学习与维特比算法解码

    crf++里的特征模板得怎么理解?

    CRF++代码分析-码农场

    CRF++源码解读 - CSDN博客

    CRF++模型格式说明-码农场

    标注偏置问题(Label Bias Problem)和HMM、MEMM、CRF模型比较<转>

    展开全文
  • 牛逼!Java 从入门到精通,超全汇总版

    万次阅读 多人点赞 2021-05-06 19:40:33
    但是我认为,如果市面上这些资料、书籍都啃的差不多,所有的 Java 程序员中跻身前 0.1% 的话,就可以达到"精通" 这个阶段了,因为没人比强了,当然是精通了。 所以,我还是选择罗列一些知识点推荐给...
  • 数字化成熟度评估模型一文读尽

    千次阅读 2022-03-03 16:26:53
    傅一平评语: 虽然纯“打分”的数字化成熟度评分对...近两年数字化转型非常热,大家关注的问题都集中:有哪些数字化转型的方法技术?企业如何成功实现数字化转型?数字化转型过程如何避免踩坑?数字化转型有没有
  • 说你懂计算机网络,那这些都知道吗

    万次阅读 多人点赞 2019-12-11 21:43:49
    今天的因特网无疑是有史以来由人类创造...随着5G时代的到来,万物互联也越来越称为可能,这里推荐一下 尤瓦尔·赫拉利 的《未来简史》,这个人的格局很高,他书中描述的未来也越来越成为现实,他写的文字能让感觉...
  • 电流集中导体的“皮肤”部分,也就是说电流集中导体外表的薄层,越靠近导体表面,电流密度越大,导线内部实际上电流较小。 结果使导体的电阻增加,使它的损耗功率也增加。这一现象称为趋肤效应。 1.2 原因:可...
  • 中国计算机学会(英文名为China Computer Federation,简称CCF),是由从事计算机及相关科学技术领域的科研、教育、开发、生产、管理、应用服务的个人及单位自愿结成、依法登记成立的全国性、学术性、非营利学术...
  • 目前,高端光刻机全球范围内只有荷兰的阿斯麦公司可以生产,而配套的光刻胶也几乎完全由日本公司生产。另一方面,即使拥有设备,也还需要与之配套的工艺流程,好的工艺需要时间的打磨,这同样需要一代又一代人的...
  • 作者主页:不吃西红柿 简介:CSDN博客专家、信息技术智库公号作者✌ 简历模板、PPT模板、学习资料、面试题库、技术互助【关注我,都给】 欢迎点赞 收藏 ⭐留言 耗时1年整理,硬核文章目录:...
  • 这些天,抽空读了一下人工智能基础(高中版),觉得作为高中科普教材,还是非常不错的,五星好评推荐。 下面会针对每一章的内容,依据兴趣等...这是medium.com上发布的文章列表,habr.comjqr.com。图标是可点击...
  • 为什么我不建议通过 Python 去找工作?

    万次阅读 多人点赞 2020-05-23 08:46:18
    二哥,你好,我是一名大专生,学校把 Python 做为主语言教给我们,但是我也去了解过,其实 Python 门槛挺高的,所以我自学 Java,但是我现在并不清楚到底要不要全心的去学 Java,学校里的课程也越来越繁重,而学 ...
  • 信息技术应用能力提升培训心得体会两篇篇一:本月,我进行了“教师信息技术应用能力提升工程”的学习,学习过程中的每一天我都过得非常充实。这次的培训我学习到了很多,每一个视频的内容都非常有意义、有价值。所以...
  • 自动驾驶技术发展的5个阶段现状

    千次阅读 2020-07-27 15:13:45
    作为整个自动驾驶的第一个量产玩家,奥迪尽管已经走了行业最前沿,但目前实现的还是3级的自动驾驶,也就是说这是一种限定环境条件下,需要驾驶员始终有接管能力的自动驾驶,距离无限条件无需...
  • 管理是一门水到渠成的学问,用不着从0开始拼命去追求,需要做的是35岁左右训练自己的情商、交际能力、带队能力,把自己的人际关系再扩大稳固一些,慢慢从纯技术路线转变成“技术+管理”的路线,最出名的莫过于...
  • redis——相关问题汇总

    万次阅读 多人点赞 2019-10-16 10:09:19
    Redis 本质上是一个 Key-Value 类型的内存数据库, 整个数据库加载内存当中进行操作, 定期通过异步操作把数据库数据 flush 到硬盘上进行保存。 因为是纯内存操作, Redis 的性能非常出色, 每秒可以处理超过 10 ...
  • 当面试官问为什么需要有三次握手、三次握手的作用、讲讲三次三次握手的时候,我想很多人会这样回答: 首先很多人会先讲下握手的过程: 1、第一次握手:客户端给服务器发送一个 SYN 报文。 2、第二次握手:服务器...
  • 概述 了解基础设施系统的状态对于确保服务的可靠性稳定性至关重要。...本文中,我们将讨论什么是指标,监控警报。我们将讨论它们为何重要,一般情况下需要关注哪些类型的指标以及您可能希望跟...
  •  交换机的背板带宽,是交换机接口处理器或接口卡数据总线间所能吞吐的最大数据量。背板带宽标志了交换机总的数据交换能力,单位为Gbps,也叫交换带宽,一般的交换机的背板带宽从几Gbps到上百Gbps不等。一台交换机...
  • 文章目录前言一定要看python入门python缩进Python注释Python 变量1. 定义理解2. 变量名命名3. 分配多个值4. 输出变量5.... 前言一定要看 python能干什么?...不管是国内的菜鸟教程还是我这里的翻译,至少
  • JDK 16 2020-12-10 第一次提案冻结 2021-01-14 第二次提案冻结 ... Java 平台中对于任何基于值的类实例进行同步的错误尝试,会予以警告。推动这一努力的是Valhalla 项目,该项目正在以原始类的形式对 Jav..
  • 企业经营运营过程中,如何获取挖掘企业经营数据中的有用价值,并用于企业管理层分析决策?SAP中,可以试用获利能力分析模块(Controlling Profit Analysis下文简称COPA )作为对应的解决方案,本章将介绍重点...
  • MySQL - 如何提高SQL的查询效率(where条件优化)

    千次阅读 多人点赞 2018-11-25 22:37:40
    前面 35条优化规则 总结 说前面 整天说SQL优化,SQL优化,到底怎么才算是SQL优化呢,下面从百度总结了一些关于Oracle里常用的一些有效的优化方法。仅供参考,文章内容来源于网络。 35条优化规则 (1)...
  • MySQL八股文连环45问,能坚持第几问?

    万次阅读 多人点赞 2022-04-05 05:24:59
    注意字符集设置: 为了避免新旧对象字符集不一致的情况,配置文件将字符集校验规则设置为旧版本的字符集比较规则。 2.密码认证插件变更: 为了避免连接问题,可以仍采用 5.7 的 mysql_native_password 认证插件...
  • 阿里做了5年技术Leader,我总结出这些套路!

    千次阅读 多人点赞 2019-04-23 07:10:14
    之前分享的文章《如何成为优秀的技术主管?》中,阿里巴巴高级技术专家云狄从开发规范、开发流程、技术规划与管理三个角度,分享对技术 TL 的理解与思考。 今天的文章,他将继续深入探讨这一话题,从管理的角度...
  • Kudu是对HDFSHBase功能上的补充,能提供快速的分析实时计算能力,并且充分利用CPUI/O资源,支持数据原地修改,支持简单的、可扩展的数据模型 2. 新的硬件设备 RAM的技术发展非常快,它变得越来越便宜,容量也...
  • 程序员必知的 89 个操作系统核心概念

    万次阅读 多人点赞 2020-03-31 19:13:39
    操作系统(Operating System,OS):是管理计算机硬件与软件资源的系统软件,同时也是计算机系统的内核与基石。操作系统需要处理管理与配置内存、决定系统资源供需的优先次序、... 过去,它是类似 Unix 的系统上...
  • 某Java大佬地表最强Java企业(阿里)面试总结

    万次阅读 多人点赞 2020-08-23 19:48:06
    面试题真的是博大精深,也通过这个面试题学到了很多...Hashtable 中的方法是Synchronize的,而HashMap中的方法缺省情况下是非Synchronize的。 HashMap把Hashtable的contains方法去掉了,改成containsValuecontains.
  • 平时使用手机连接无线网络的时候,一定看到过这样的安全提示:不要连接陌生的 Wi-Fi。也一定看过很多这样的报道:某先生 / 女士因为使用了...但是,工作中,员工服务器通常接入的也是同一个网络,那员工是不是就.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 146,565
精华内容 58,626
关键字:

在你能力和条件允许的范围