学位论文 > 优秀研究生学位论文题录展示

赋值代数分裂算法与隐性半环赋值研究

作　者: 韩邦合
导　师: 李永明
学　校: 陕西师范大学
专　业: 基础数学
关键词: 半环赋值代数计量逻辑学约束满足问题自动机软约束文法约束软集
分类号: O153.3
类　型: 博士论文
年　份: 2011年
下　载: 20次
引　用: 0次
阅　读: 论文下载

内容摘要

当今正处于信息爆炸时代,信息具有数据量大,来源广,不确定等新特点.一方面,需要将多种信息进行有效的融合,另一方面需要提取关系到特定角度的信息.赋值代数是有关信息处理的一种公理化数学模型.它来源于对概率论中变量的条件独立性结构和证据理论中信任函数的抽象,并且还能够涵盖关系代数,专家系统,命题逻辑,贝叶斯网络推理和约束满足问题等多个研究领域.赋值代数中的联合运算和边缘化运算是其处理信息的两个工具,它的局部计算模型是其有效工作的保证.赋值代数公理化的研究方法有助于对问题本质的把握,减少不必要的重复工作,因而对赋值代数公理化的研究始终是该领域研究的核心内容之一.本文提出的分裂算法使得赋值代数理论更加丰富,让局部计算的本质更加清晰.分裂算法基于自上而下的处理方式,可以应用到命题逻辑计量化研究和软约束满足问题求解中.在赋值代数中,半环值赋值是重要的类型.本文在半环值赋值中总结出一类隐性赋值.由于某些原因这些赋值的定义并不是鲜明的.例如在一些基本显性约束上,通过逻辑联结词构成的新的隐性约束；由命题结构诱导的半环赋值；还有近几年来学者们提出的文法约束和软集等都可以诱导半环值赋值.所以,隐性赋值显性化是赋值代数领域中重要的研究内容之一.另一方面,对于半环赋值,进行隐性化表示是处理大规模问题的重要技巧,例如经典约束满足问题的自动机自动机表示.本文给出了具体隐性赋值实例及其性质,讨论了隐性赋值及其运算显性化方法和自动机隐性表示等问题.全文共分5章.第一章介绍了有关半环,计量逻辑学,约束满足问题,软约束,文法约束,软集与赋值代数理论的基本知识,这些知识是后续内容所必须的.第二章主要给出了赋值代数中的Markov联合公理与分裂算法.首先在带标记的赋值代数,无标记赋值代数,信息代数和半环值约束满足问题中给出了Markov联合公理,讨论了它在变元消去,空扩展,转移运算和同态映射中的形式,提出它和条件独立性的关系.接着基于Markov联合公理给出t划分,t分解,t分裂和传递t分裂的概念,提出了分裂算法.讨论了分裂算法与收集算法的关系.然后给出了动态分裂算法.利用覆盖联合树表明了动态过程.最后讨论了分裂算法在赋值代数近似计算中的应用.第三章主要讨论了隐性半环赋值及其实例.主要有5节组成.第一节给出隐性半环赋值的概念.第二节由逻辑命题诱导出命题半环值赋值,给出二值命题的投射真度的概念及其性质,指出同一公式的投射真度与投射论域成单调递减的关系.第三节由文法结构诱导出隐性半环值文法约束满足问题模型.第四节首先给出了半环值软集的概念,运算以及决策方法.半环值软集的提出为已有的软集模型提供了个统一的框架,特别是约束型半环为软集决策提供了有力的工具.然后在半环值软集的结构基础上讨论了半环值软集与赋值代数的四种关系.第5节主要介绍了经典约束的自动机表示思想和方法,为第四章半环值约束满足问题自动机表示做好准备.第四章主要讨论了分裂算法的应用.主体有两部分组成.第一部分,结合命题半环值赋值以及计量逻辑学,利用分裂算法讨论了计量逻辑学中真度的计算问题.基于分裂算法分别给出了二值命题真度.D-真度,多值命题逻辑公式真度,绝对真度以及命题公式对应语义函数最值的求解方法.最后给出了计量逻辑学关于真度的若干结论,这些结论可以用以指导命题真度的计算.第二部分,基于分裂算法给出了半环值约束满足问题的自动机表示方法,该方法能够使半环值约束满足问题自动机表示的工作量降低.第五章讨论了隐性半环赋值的投射运算和联合运算求解问题.全章主要有两节.第一节首先给出了半环值文法约束模型的单投射问题求解方法.分别基于CYK,可分解否定范式(DNNF)和赋值否定范式(VNNF)给出了三种解决思路.后两种方法利用编译转化的思想,将半环值文法约束单投射问题转化为命题逻辑领域的相关问题来处理.这种做法的好处其一在于针对不同的应用要求可提供统一的计算模式,其二在于减少运算,避免用户无必要的等待.其三在于方便文法约束和命题约束的融合及推理.接着讨论了半环值文法约束与关系约束的合取问题.给出了可满足性和广义弧相容算法.算法思想是将关系约束嵌入到文法约束的求解过程中.最后引入文法约束序列的概念,提出了一种基于泵引理的文法约束序列可满足性算法.第二节研究了不完备半环值软集赋值决策问题.首先讨论了不完备度及其性质.接着给出了完备概念,必然最优解和可能最优解及其完备刻画.然后基于若干预序关系提出了基本的决策方法.最后从付费角度讨论了不完备经典软集决策的启发式诱导方法.

全文目录

摘要  3-5
Abstract  5-12
前言  12-18
第1章基本理论  18-36
  1.1 半环  18-20
  1.2 二值命题逻辑  20-23
    1.2.1 二值命题逻辑基本知识  20-21
    1.2.2 二值命题逻辑L中的计量逻辑学理论  21-23
  1.3 图,二部图,连通分量  23-24
  1.4 约束满足问题  24-27
    1.4.1 经典的约束满足问题  24-25
    1.4.2 半环值约束满足问题与软约束  25-26
    1.4.3 文法约束  26-27
  1.5 软集理论  27-29
  1.6 赋值代数  29-36
    1.6.1 赋值代数的定义与实例  29-33
    1.6.2 赋值代数中的计算问题与算法  33-36
第2章赋值代数中的Markov联合公理与分裂算法  36-68
  2.1 Markov联合公理  36-44
    2.1.1 各种赋值代数中的Markov联合公理  36-41
    2.1.2 Markov联合公理的若干性质  41-44
  2.2 基于Markov联合公理的分裂算法  44-59
    2.2.1 Markov联合公理在降低计算工作量中的作用  44-46
    2.2.2 t划分,t分解,t分裂,传递t分裂  46-54
    2.2.3 分裂算法  54-59
  2.3 动态分裂算法  59-64
  2.4 分裂算法在赋值代数近似推理中的应用  64-66
  2.5 总结  66-68
第3章隐性半环值赋值概念与实例  68-88
  3.1 隐性半环值赋值  68-70
  3.2 隐性半环值赋值实例一:由命题逻辑诱导的半环值赋值  70-74
  3.3 隐性半环值赋值实例二:由文法约束诱导的半环值赋值  74-76
  3.4 隐性半环值赋值实例三:由软集结构诱导的半环值赋值  76-84
    3.4.1 半环值软集  76-80
    3.4.2 半环值软集诱导的半环值赋值  80-84
  3.5 隐性半环值赋值实例四:经典约束满足问题的自动机隐性表示  84-86
  3.6 总结  86-88
第4章分裂算法在隐性半环赋值中的应用  88-104
  4.1 分裂算法在命题赋值投射真度计算中的应用  88-96
    4.1.1 二值命题公式真度的计算方法  88-92
    4.1.2 值命题D真度的计算方法以及τ_n(A)求法  92-96
  4.2 分裂算法在半环值约束自动机隐性表示中的作用  96-101
  4.3 总结  101-104
第5章隐性半环值赋值投射与联合问题求解  104-128
  5.1 隐性半环值文法约束赋值的投射与联合问题  104-118
    5.1.1 基于CFGC的半环值文法约束单投射问题  104-107
    5.1.2 基于DNNF和VNNF隐性表示的解决方案  107-113
    5.1.3 半环值文法约束分别与关系约束和文法约束的联合:可满足性及广义弧相容算法  113-118
  5.2 隐藏变量型不完备软约束中的优化问题  118-126
    5.2.1 不完备度及其性质  118-119
    5.2.2 不完备软集的完备化,必然最优解和可能最优解  119-123
    5.2.3 不完备软集论域U上的若干关系及其性质和应用  123-124
    5.2.4 基于付费角度的启发式诱导算法  124-126
  5.3 总结  126-128
总结  128-130
参考文献  130-140
致谢  140-142
个人简历、在读研期间的科研成果  142

赋值代数分裂算法与隐性半环赋值研究

内容摘要

全文目录

相似论文