基于图神经网络的布尔公式边缘概率预测

来源 :吉林大学 | 被引量 : 0次 | 上传用户:bobogu
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
布尔公式的边缘概率是指所有使布尔逻辑公式可满足的指派中,目标变量赋值为真的概率。获取布尔公式的边缘概率非常有意义,例如,如果我们能对公式中的变量进行准确的随机抽样,那么就可以通过边缘概率推导出模型计数;如果我们能准确计算出公式中所有变量的边缘概率,那么就能快速生成公式的一个可满足的指派。图神经网络是指将图与神经网络结合进行端到端的计算,以便于处理结构化的数据。尽管用于求解布尔公式边缘概率的图神经网络方法尚未有人提出,越来越多的研究人员将图神经网络用于布尔命题公式相关问题的研究。Selsam等人提出了基于图神经网络的SAT求解消息传递模型;Abboud等人提出了用图神经网络求解模型计数的方法。本文创新性的提出了将图神经网络应用于求解布尔公式边缘概率的模型MargPred。该模型将布尔命题公式的合取范式表示成图,分别建立公式、子句和文字层节点,发挥了图神经网络在处理结构化数据上的优势。模型在相邻节点的消息传递中学习公式的隐含依赖关系,这种对公式逻辑结构的学习有助于网络对问题的求解方法的学习。通过设置网络的学习目标为概率区间,而不是具体概率,问题得到简化,网络才能表现出有使用价值的性能。不仅如此,本文提出了标识目标变量的方法,它解决了只使用公式嵌入计算概率分布导致模型学习偏差的问题,通过引入指定变量的文字嵌入,模型能够学习到求解边缘分布的目标,获得更好的预测结果。MargPred融合了多种流行神经网络优化方式,引入了梯度裁剪、学习率衰减、l2正则化和Adam优化器来防止模型在训练时过拟合。本文还提出了生成布尔公式的一个模型的方法ModelGen,该方法使用MargPred计算公式中所有变量的边缘概率,从中挑选边缘概率最大或最小的变量赋值并化简公式,该过程将重复直到公式被完全化简得到一个指派,或当前变量赋值已经使公式不可满足。化简公式的算法选用了布尔约束传播算法,该算法遵从单元子句规则,能减少近一半的公式变量赋值搜索空间。最后得到一组指派,并验证该指派是否是公式的一个模型。为了验证模型MargPred的有效性,本文将MargPred与4种适应公式的边缘分布预测这一问题的模型进行比较,MargPred的预测准确率明显优于其他模型。本文还在鲁棒性、问题规模泛化能力、更多的概率区间分类和消息传递次数的影响等问题上进行了消融实验,验证了模型的鲁棒性并探索如何发挥模型的最佳性能。对于生成公式的一个模型这个问题,本文将ModelGen方法与另一种神经网络方法进行对比,结果证明ModelGen远优于其他神经网络方法,在较为简单的问题上甚至可达100%的准确率。
其他文献
教育公平是国家制定和实施教育政策的基本原则,是现代文明的价值体现,也反映了人们对教育均衡发展的追求。习近平总书记考察北京市八一学校时提到,教育公平是社会公平的重要基础,要不断促进教育发展成果更多更公平惠及全体人民,以教育公平促进社会公平正义。李克强总理在政府工作报告中提出,推动教育公平发展和质量提升,要稳定教育投入,优化投入结构,缩小城乡、区域、校际差距,让教育资源惠及所有的家庭和孩子,让他们能够
学位
在科技创新和产业升级的迅猛势头下,知识产权领域的竞争变成了一场没有硝烟的战役,但却逐渐成为市场主体竞争甚至区域间竞争的核心。经过了几轮机构改革后,Q县市场监管局承担着商标专利等行政保护工作,在行政保护和司法保护“双轨制”模式的基础上,知识产权行政保护要释放保护面广和保护效率高的特点,市场监管局要依托市场监管职能,在知识产权行政保护改革破冰中,破除知识产权保护与发展的阻力,健全知识产权完备的保护机制
学位
<正> 祖国医学的针灸疗法,发源最古。到秦汉时,已经形成为一种独立的学科。在现存的我国最古的一部经典著作“黄帝内经”里就有很大一部分是讲述针灸疗法的。到了晋代皇甫谧,又作了一番整理工作,编成了一部针灸甲乙经,给针灸疗法的学说,打下了良好的基础。由晋至唐,针灸疗法的专著,竟如雨后春笋,层出不穷(根据日本丹波元胤中国医籍考的记载,约有70
期刊
随着我国发展模式的不断转变,经济结构的逐步优化,治理能力现代化水平的不断提高,财政收入呈现增长趋势,财政资金支出需求也与日俱增,各地区的财政收支矛盾也成为财政改革进程中的重要问题,如何提升财政资金的使用效益,优化资源配置是政府管理中面临的重大难题。在国家治理的过程中财政作为核心基础和重要支撑,也急需不断进行制度的深化改革来适应社会经济的高速发展,不断推进完善资金管理体系。党的十九大报告中提出了“建
学位
随着时代的进步和科技的发展,现代社会的生活方式已经有了翻天覆地的变化,在我们日常生活的各个角落,信息技术和互联网都起到了重要的作用。各级政府部门也在“互联网+政务服务”的背景下探索了更多的服务途径,社会保险在保障民生方面具有社会稳定器的重要作用。然而,随着社会的发展,传统的社会保险服务平台已经无法满足群众多样化的社会保险经办需求,为保障社会保险经办领域服务质量,提升参保群众对社会保险服务平台的满意
学位
济南,作为城市的发展,始终是在北纬36度附近按照太阳运行的轨迹而拓展。所以,这个城市永远有着金色的城际线、光辉的道路。在现在市区东部的几十公里范围内,众多历史遗存密集遍布。尤其是两座汉代古墓的开掘,更见证了2000多年前这座城市的繁华和辉煌。
期刊
在如今的信息时代,互联网相关技术已应用于诸多领域。知识图谱技术是其中一项用于表示海量信息及其关系的重要技术。为了保持知识图谱中知识的固有结构并且便于计算,人们提出了知识图谱嵌入技术,用嵌入向量表示知识图谱中的实体和关系。知识图谱子图是知识图谱的一部分,一般是在给定知识图谱上按照一定策略构建的,其具体大小可根据实际需要来设定。相比于原知识图谱,对于知识图谱子图的研究,有如下优势:1、对于较为庞大的知
学位
2007年以来,大学生职业发展与就业指导课程开发工作受到教育部及社会各界的高度重视,相关的课程体系建设及成效也备受社会关注。本课题组通过对生涯教育体系的问卷调查,分析了课程体系的实施效果,以期在实践基础上为进一步完善这一课程体系提供参考。
期刊
目的 探讨低钙腹膜透析液对肾衰竭患者钙磷代谢及肾功能的影响。方法 选取我院2013年1月-2015年12月收治20例肾衰竭腹膜透析患者,依据透析液钙离子浓度差异分为低钙组(n=10,钙离子浓度1.25 mmol/L)和对照组(n=10,钙离子浓度1.75 mmol/L)。比较两组治疗前后血钙、血磷、尿素氮(BUN)。结果 两组治疗后血钙、血磷下降且低钙组低于对照组;两组治疗后BUN下降且低钙组低于
期刊
近些年来,以黑色素瘤等为例的皮肤癌发病率不断上升,严重危害了人类的生命健康安全。对此类疾病的尽早发现和治疗是提高患者生活质量的重要途径。皮肤镜凭借其无创、简便和能提高检测准确性的优点,在对黑色素瘤等皮肤病变的诊断中得以广泛应用。然而,即使是专业的皮肤科临床医生,在皮肤镜图像上进行人工诊断时也可能发生漏检和错诊的情况。计算机辅助医生进行皮肤镜图像的病变分析,提高皮肤病变诊断的准确率和效率,对于提升患
学位