第7章 概率图模型ppt课件.pptx

《第7章 概率图模型ppt课件.pptx》由会员分享，可在线阅读，更多相关《第7章 概率图模型ppt课件.pptx（98页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、章 节 目 录 7.1 7.1 贝叶斯网络贝叶斯网络 7.2 7.2 马尔可夫随机场马尔可夫随机场 7.3 7.3 隐马尔可夫模型隐马尔可夫模型 7.4 7.4 马尔可夫链蒙特卡罗马尔可夫链蒙特卡罗 7.5 LDA7.5 LDA主题提取模型主题提取模型 7.6 7.6 概率图模型应用概述概率图模型应用概述 7.7 7.7 案例分析案例分析什么是概率图模型？什么是概率图模型？ 概率图模型是指一种用图结构来描述多元随机变量之间条件独立关系的概率模型。 图中的每个结点都对应一个随机变量，可以是观察变量、隐变量或是未知参数等；每条边表示两个随机变量间的概率相关关系。概率图模型概率图模型贝叶斯网络概述贝

2、叶斯网络概述贝叶斯基本公式贝叶斯基本公式 条件概率 联合概率贝叶斯基本公式贝叶斯基本公式 全概率公式贝叶斯基本公式贝叶斯基本公式贝叶斯基本公式贝叶斯基本公式 极大后验假设（ Maximum a Posteriori ，MAP）贝叶斯基本公式贝叶斯基本公式 极大似然（ Maximum Likehood, ML）假设朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器朴素贝叶斯分类器贝叶斯网络的拓扑结构贝叶斯网络的拓扑结构 贝叶斯网络能够利用简单的图定性地表示事件之间复杂的因果关系或概率关系，在给定某些先验信息后，还可以定量地表示这些关系

3、。网络的拓扑结构通常是根据具体的研究对象和问题来确定的。下图是一个简单的贝叶斯网络模型。下雪A1堵车A2摔跤A3迟到A4骨折A5条件独立性假设条件独立性假设先验概率的确定和网络推理算法先验概率的确定和网络推理算法 有了条件独立性假设就可以大大简化网络推理计算。与其他形式的不确定性推理方法一样，贝叶斯网络推理仍然需要给出许多先验概率先验概率，他们是根节点的概率值和所有子节点在其母节点给定下的条件概率值。 与其他算法一样，贝叶斯网络推理算法也可分为精确算法和近似算法两大类。理论上，所有类型的贝叶斯网络都可以用精确算法来进行概率推理。但Cooper指出，贝叶斯网络中的精确概率推理是一个N-P难问题。

4、对于一个特定拓扑结构的网络，其复杂性取决于节点数。 所以，精确算法一般用于结构较为简单的单联网络。对于解决一般性的问题，我们不希望他是多项式次复杂。因而，许多情况下都采用近似算法。它可以大大简化计算和推理过程，虽然它不能提供每个节点的精确概率值。案例分析案例分析 下图所示为一个简单的贝叶斯网络，有盗贼闯入或地震发生都会触发警报，警报触发之后，John或者Mary会给你打电话，每个事件之间的概率关系均已给出，已知一个事件e=JohnCalls=true,and MaryCalls=true，试问出现盗贼的概率是多少？案例分析案例分析案例分析案例分析案例分析案例分析马尔可夫随机场马尔可夫随机场 随

5、机场当给定每一个位置中按照某种分布随机赋予相空间的一个值之后，其全体就叫做随机场。 其中，两个重要的概念是“位置”和“相空间”。“位置”好比是一亩亩农田；“相空间”好比是种的各种庄稼。我们可以给不同的地种上不同的庄稼，这就好比给随机场的每个“位置”赋予相空间里不同的值。所以，俗气点说，随机场就是在哪块地里种什么庄稼的事情。马尔可夫随机场马尔可夫随机场 马尔可夫随机场(Markov Random Field，MRF) 具有马尔可夫特性的随机场。 拿种地打比方，如果任何一块地里中的庄稼种类仅仅与它邻近的地里种的庄稼的种类有关，与其他地方的庄稼的种类都无关，那么这些地里种的庄稼的集合，就是一个马尔可

6、夫随机场。马尔可夫特性马尔可夫特性 马尔可夫特性马尔可夫特性 马尔可夫特性马尔可夫特性 概率无向图模型概率无向图模型 有了上面的基础，我们就可以定义概率无向图模型：设有联合概率分布P(X)，由无向图G=(V,E)表示，在图G中，节点表示随机变量，边表示随机变量之间的依赖关系，如果联合概率分布P(X)满足成对的、局部的或全局的马尔可夫性，就称此联合概率分布为概率无向图模型或马尔可夫随机场。MRFMRF的因式分解的因式分解 在MRF中，多个变量之间的联合概率分布能基于团分解为多个因子的乘积，每个因子仅与一个团相关，称为MRF的因式分解。 团无向图G中任何两个节点均有边连接的节点子集称为团； 极大团

7、若C是无向图G的一个团，并且不能再加进任何一个G的节点使其成为一个更大的团，则称C为极大团； 最大团在所有极大团中，节点最多的称为最大团。MRFMRF的因式分解的因式分解MRFMRF的因式分解的因式分解MRFMRF的因式分解的因式分解案例分析案例分析 下图是一个简单的马尔可夫随机场，直接找出它的团、极大团和最大团，并写出联合概率分布的表达式。隐马尔可夫模型隐马尔可夫模型隐马尔可夫模型隐马尔可夫模型隐马尔可夫模型的三个问题隐马尔可夫模型的三个问题案例分析案例分析 假设某个赌徒赌博时经常会用自己制作的两个“作弊骰子”来替换赌场中的正常骰子，赌徒在赌博时切换骰子的概率可描述为矩阵A。 假设正常骰子与

8、“作弊骰子”出现各点数可用矩阵B来表示：案例分析案例分析 由上述信息我们可以画出状态转移概率图和输出观测概率图状态转移概率 输出观测概率案例分析案例分析马尔可夫链蒙特卡罗马尔可夫链蒙特卡罗 马尔可夫链蒙特卡罗方法(Markov Chain Monte Carlo，MCMC)是在贝叶斯理论框架下，通过计算机进行模拟的蒙特卡罗方法(Monte Carlo，MC)。 M CMC是一种通用的计算方法，通过迭代地对生成的样本进行求和代替复杂的数学推理，主要解决两个基本问题：计算目标函数的最优解和计算统计学习问题的后验分布。这两种情况下的状态空间都可能非常大，MCMC方法处理复杂高维问题比较有用。 我们首

9、先了解蒙特卡罗积分（Monte Carlo integration）和马尔可夫链（Markov chains）。 蒙特卡罗积分蒙特卡罗积分蒙特卡罗积分蒙特卡罗积分 随机过程（stochastic process）是一组随机变量Xt的集合，其中t属于一个索引（index）集合T。 索引集合T 可以定义在时间域或者空间域。 在随机过程中，马尔可夫性质（Markov property）是指一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。马尔可夫过程马尔可夫过程马尔可夫链马尔可夫链马尔可夫链马尔可夫链马尔可夫链马尔可夫链 下图为马尔可夫链的简单表示：马尔可夫链

10、蒙特卡罗马尔可夫链蒙特卡罗 MCMC的目标是设计一个马尔可夫链，该马尔可夫链的平稳分布就是我们要采样的分布，这就是所谓的目标分布。换句话说，我们希望从马尔可夫链的状态中采样等同于从目标分布中取样。这个想法是用一些方法设置转移函数，使无论马尔可夫链的初始状态是什么最终都能够收敛到目标分布。 MCMC方法使用过程中，构造转移核是至关重要的，往往不同的MCMC方法（也就是转移核）的构造方法也不同，在这里我们只讨论Metropolis Sampling，Metropolis Hastings和 Gibbs sampling。马尔可夫链蒙特卡罗马尔可夫链蒙特卡罗Metropolis SamplingMe

11、tropolis SamplingMetropolisMetropolis采样器步骤采样器步骤MetropolisMetropolis采样步骤：采样步骤：Metropolis-HastingMetropolis-Hasting SamplingSamplingMHMH采样步骤采样步骤GibbsGibbs SamplingSampling Gibbs方法采样得到所有的样本都被接受，从而提高了计算效率。另外一个优点是，研究人员不需要指定一个建议分布，这在MCMC过程中留下一些猜想。 然而，Gibbs sampler只能用于我们熟知的情况下，其特点是需要知道所有变量的联合概率分布，比如在多元分布中，

12、我们必须知道每一个变量的联合条件分布，在某些情况下，这些条件分布是未知的，这时就不能使用Gibbs sampling。然而在很多贝叶斯模型中，都可以用Gibbs sampling对多元分布进行采样。GibbsGibbs采样步骤采样步骤LDALDA主题提取模型主题提取模型 隐含狄利克雷分布 (Latent Dirichlet Allocation, LDA)模型是一种文档主题生成模型，也称为一个三层贝叶斯概率模型，包含词、主题和文档三层结构。 所谓生成模型，就是说，我们认为一篇文章的每个词都是通过“以一定概率选择了某个主题，并从这个主题中以一定概率选择某个词语”这样一个过程得到。文档到主题服从多

13、项式分布，主题到词服从多项式分布。LDALDA主题提取模型主题提取模型 LDA是一种非监督机器学习技术，可以用来识别大规模文档集（document collection）或语料库（corpus）中潜藏的主题信息。 它采用了词袋（bag of words）的方法，这种方法将每一篇文档视为一个词频向量，从而将文本信息转化为了易于建模的数字信息。 但是词袋方法没有考虑词与词之间的顺序，这简化了问题的复杂性，同时也为模型的改进提供了契机。 每一篇文档代表了一些主题所构成的一个概率分布，而每一个主题又代表了很多单词所构成的一个概率分布。算法流程算法流程算法：提取文档主题Unigram ModelUnig

14、ram Model概率模型概率模型 最简单的文本生成模型就是，确定文本的长度为N，然后选出N个词来。选词的过程与我们仍骰子一模一样，无非就是这个骰子的面比较多，但其仍然服从多项分布。这个简单的文本生成模型就叫做Unigram Model。 当然少不了贝叶斯估计，每一个面朝上的概率也会有一个先验分布为Dirichlet分布，表示为 ，而我们也可以根据样本信息 来估计后验分布 ，其概率图模型可以表示为Unigram Model概率模型图PLSA ModelPLSA Model概率模型概率模型 上面讲的文本生成模型足够简单，但是对文本的表达能力还是不够，且不太符合我们日常的写作习惯。 试想，我们写一

15、篇文章的时候，肯定都会事先拟定一个主题，然后再从这个主题中去寻找相应的词汇，因此这么来看，只扔一个有N面的骰子似乎还不够，我们似乎应该提前再准备m个不同类型的骰子，作为我们的主题，然后确定了主题以后，再选中那个骰子，来决定词汇。 由此，便引申出了我们的主题模型，在此之前我们先介绍一个简单的PLSA模型。PLSA ModelPLSA Model概率模型概率模型PLSA Model图LDALDA概率模型概率模型LDA图计算机视觉及语音识别计算机视觉及语音识别 由于视觉及语音信息处理中存在大量的不确定性，概率图模型在计算机视觉领域有着广泛的应用，备受广大学者的关注。最近二十年中，计算机视觉发展最鲜明

16、的特征就是机器学习与概率模型的广泛应用。视觉中常用的概率图模型有三类：贝叶斯网络、马尔可夫随机场和因子图。 这三种概率图模型在视觉信息处理领域具有各自不同的应用范围。 贝叶斯网络最适合于表达因果关系或前一时刻对后一时刻的影响，所以广泛地应用于识别理解、目标跟踪等方面。计算机视觉及语音识别计算机视觉及语音识别 马尔可夫随机场可表达相邻像素之间的关系，由此构成节点数量巨大的马尔可夫随机场，其求解依赖于图像分割（Graph Cut，GC）算法和置信传播（Belief Propagation，BP）算法。 因子图是三者中表达能力最强的，许多视觉问题都可以转化为因子图来求解，但由于引入了局部函数节点，因

17、子图的求解比较困难。 近年来，基于马尔可夫随机场的视觉信息处理受到了很大的关注，在图像分割、图像还原以及目标跟踪、目标检测、立体视觉等方面提出了很多有效的算法，得到了广泛的应用。另外，隐马尔可夫模型是语音识别的支柱模型。自然语言处理自然语言处理 图模型把图论和统计方法结合起来，把基于图的推理应用到概率统计框架中，为描述自然语言中各种复杂的约束关系提出了一种可行的思路。 图模型定义在一组与问题相关的随机变量上，每个变量对应于图中的一个节点，节点之间的约束关系用边表示，通过因子图的定义把图的结构和指数概率分布族联系起来，以特征的方式把语言知识或现象采用统一的方式整合到概率分布中，用于解决各种自然语

18、言处理任务。自然语言处理自然语言处理 在文本分类中，LDA作为一种无监督文本表示模型，其本身并不能直接判断文本类别，必须集成到合适的分类模型中协同工作。 在最初利用LDA模型的分类过程中，LDA对给定训练集中所有文档进行特征降维，将文本训练集表示成主题的概率分布，在得到的主题文本矩阵上选择一种分类算法进行训练，构造出文本分类器。 假设同一类别的文档共享同一类主题，不同类别的主题之间是独立的，因此每个类别的文档都将对应一个LDA子模型。在判断新文本类别时，将训练得到的每一个LDA子模型对新文本进行主题推断，计算出此文档的主题概率分布，之后根据分类算法判别新文本属于哪一个类别。自然语言处理自然语言

19、处理 在文本聚类中，由于传统的聚类方法完全依靠词频等基本特征作为聚类分析依据，忽略了文本语义信息，聚类效果并不明显。 人们开始考虑引入主题模型对文本建模，按照语义关系对文本进行聚类分析，每一聚簇内文本共享同一主题，使聚类更符合文本语义特征，提高了文本聚类的准确性。自然语言处理自然语言处理 在摘要抽取中，LDA模型可建立多文档之间的语义联系，排除文档间的冗余成分，提高了多文档摘要抽取的准确性。 韩冰等人在LDA模型基础上提出了一种融合显著信息的LDA 方法(LDA with saliencyinformation,简称SI-LDA)，利用极光图像的谱残差(spectral residual，简称

20、SR)显著信息生成视觉字典，加强极光图像的语义信息，并将其用于极光图像的特征表示。风险控制风险控制 概率图模型能够评估未知量取值的可能性，对不同取值的概率给出量化的估计，这在涉及风险的决策系统中非常重要。 在综合考虑数据有缺失、数据相关性、因果分析等方面的问题时，可基于贝叶斯理论将针对连续数据的概率主成分分析(Probabilistic Principle Componets Analysis， PPCA)和针对离散数据的贝叶斯网络方法结合为概率图模型，打造统一的风险控制模型，在模型解释性、模型预测能力上以求达到最佳的平衡。风险控制风险控制 在针对反欺诈类型的问题时依旧可以选择概率图模型，蚂蚁

21、金服在SIGKDD 2018上的一篇投稿将无监督模型应用在信用卡欺诈检测中，在国际信用卡欺诈检测场景下，使用autoencoder模型对比规则，实现召回率提升约3倍，准确率提升约40%，模型效果优于规则，且维护成本比规则低。社交网络挖掘社交网络挖掘 在社交网络用户相似性预测中，为了有效描述社交网络用户间复杂的相关性及不确定性，并提高海量社交网络用户相似性发现的准确度，利用基于贝叶斯网络的概率图模型，结合网络拓扑结构和用户之间的依赖程度，发现用户相似度。 情感分析方面，彭云等人提出语义关系约束的主题模型SRC-LDA（semantic relation constrained LDA），用来实现

22、语义指导下LDA的细粒度主题词提取。由于SRC-LDA改善了标准LDA对于主题词的语义理解和识别能力，从而提高了相同主题下主题词分配的关联度和不同主题下主题词分配的区分度，可以更多地发现细粒度特征词、情感词及其之间的语义关联性。医学医学 2017年10月26日，科学期刊Science上刊发了Vicarious公司的一项最新研究，该研究通过提出一种新型生成式组成模型：Recursive Cortical Network (RCN)，使用小样本学习，在CAPTCHA（Completely Automated Public Turing Test to Tell Computers and Huma

23、ns Apart）上获得突破性的成果。RCN的成功表明，在推动人工智能发展的道路上，生成式组成模型，特别是上下文相关概率语法图模型和自底向上/自顶向下联合推理算法，取得了一个重要的阶段性成果。医学医学而另一项概率图模型贝叶斯网络，最早的应用之一是奥尔堡大学开发的MUNIN专家系统, 用于辅助肌电图的诊断, 通过对人类神经肌肉系统建模, 能够处理多1000个变量之间的关系学习。同期开发的Hugin专家系统则通过比较直观和易于使用的界面利用BN进行医疗诊断，MUNIN和Hugin系统极大推动了概率图模型的发展, 是BN在很多其他领域成功应用的基础。马尔可夫网络在基因网络建模中也十分热门。Wei和L

24、i利用离散马尔科夫随机场为基因网络建模, 而Wei和Pan把基因网络表达为高斯马尔科夫随机场。Wei P等人对马尔可夫网络在基因表达中的不同应用进行了比较。朴素贝叶斯进行垃圾邮件过滤朴素贝叶斯进行垃圾邮件过滤 使用朴素贝叶斯对电子邮件进行分类的步骤：1）收集数据：提供文本文件。2）准备数据：将文本文件解析成词条向量。3）分析数据：检查词条确保解析的正确性。4）训练算法：使用我们之前建立的trainNB0()函数。5）测试算法：使用classifyNB()，并构建一个新的测试函数来计算文档集的错误率。6）使用算法：构建一个完整的程序对一组文档进行分类，将错分的文档输出到屏幕上。朴素贝叶斯进行垃圾

25、邮件过滤朴素贝叶斯进行垃圾邮件过滤 对于一个文本字符串，可以使用Python的string.split()方法将其切分。 如果某些文件包含一些URL(http:/docs.goog bin/answer.pyhl=en&answer=66343)，例如ham下的6.txt，那么切分文本时就会出现很多单词，如py、hl，很显然这些都是没用的，所以我们在程序最后一行只输出长度大于2的词条。朴素贝叶斯进行垃圾邮件过滤朴素贝叶斯进行垃圾邮件过滤 测试朴素贝叶斯分类器，并进行交叉验证。随机选择10封电子邮件，并计算其上的分类错误率。因为是随机的，所以每次输出结果可能有些差别。本例中，我们的运行结果为“错

26、误率：10.00%”。如果想要更好地估计错误率，就需要多次重复求平均值。 这里一直出现的错误是将垃圾邮件误判为正常邮件。相比之下，将垃圾邮件误判为正常邮件比将正常邮件误判为垃圾邮件好。 前向后向算法求观测序列概率前向后向算法求观测序列概率盒子盒子1234红球数红球数5368白球数白球数5742 盒子与球模型：假设有4个盒子，每个盒子内都装有红色和白色两种球若干个，盒子内的红白球数如下： 从4个盒子中等概率地选取一个盒子，从这个盒子中随机抽取一个球，记录颜色后放回，然后转移到下一个盒子。规则是：当前盒子为盒子1时，那么下一个盒子一定是盒子2，当前盒子为2或3时，分别以0.4和0.6的概率转移到左

27、边或右边的盒子，当前盒子为盒子4时，则以0.5的概率留在盒子4或转移到盒子3。前向算法前向算法 算法：前向算法，用于计算HMM观测序列的概率 。后向算法后向算法 算法：后向算法，用于计算HMM观测序列的概率 。建模建模 马尔可夫链蒙特卡罗方法预测睡眠质量马尔可夫链蒙特卡罗方法预测睡眠质量 如下图所示，为Garmin Vivosmart 手表根据心率和运动情况追踪的睡眠和起床状况。借助该睡眠数据创建一个模型，通过把睡眠看作时间函数，而确定睡眠的后验概率。建模建模其中， 和 是我们在 MCMC 过程中必须学习的模型参数。具有不同参数的 logsitic 函数图像如下所示。建模建模 我们不能直接构建

28、 logistic 分布，所以，我们为函数的参数（ 和 ）生成了上千个值被称为样本从而创造分布的近似值。MCMC 背后的思想是，当我们生成更多的样本时，我们的近似值越来越接近实际的真实分布。下图显示了我们的问题使用正常先验后的参数空间。 显然，我们无法一一尝试图像中的每一个点。但是通过对较高概率区域（红色区域）进行随机抽样，我们可以为问题建立最可能的模型。建模建模 为了绘制 和 的随机值，我们需要假设这些值的先验分布。由于我们对参数没有任何提前的假设，我们可以使用正态分布。正态分布也称高斯分布，它由均值和方差定义，分别显示数据的位置以及扩散情况。下图是具有不同均值和方差的几种正态分布：建模建模

29、 马尔可夫链蒙特卡罗方法在我们的问题当中基本步骤如下：1)为logistic函数选择一组初始参数 和 。2)根据当前状态，把新的随机值分配给 和 。3)检查新的随机值是否与观察结果一致： 如果一致，则接受这些值，将其作为新的当前状态 如果不一致，拒绝这些随机值并返回前一个状态 4) 对指定的迭代次数重复执行步骤 2 和 3。 该算法将返回它为 和 生成的所有值。然后，我们可以使用这些值的平均值作为 logistc 函数中 和 的最终可能值。MCMC 无法返回真实值，它给出的是分布的近似值。给定数据的情况下，最终输出的睡眠概率模型将是具有 和 均值的 logistic 函数。建模建模 查看模型运

30、行过程中生成的 和 的所有值：它们被称为轨迹图。我们可以看到，每个状态都与之前的状态有关（马尔可夫链），但是这些值波动显著（蒙特卡罗采样）。建模建模 最终建立并运行模型之后，我们将最后 5000 个 和 样本的平均值作为参数最可能的值，这就让我们能够创建一条曲线，建模睡眠后验概率： 该模型能很好地反映数据的结果。此外，它捕捉了睡眠模式当中的固有变化。该模型给出的不是一个简单的是非答案，而是一个概率。 建模建模 我们可以通过该模型找到在给定时间我们睡着的概率，并能找到睡眠概率经过 50% 的时间：1）9:30 PM probability of being asleep: 4.80%2）10:0

31、0 PM probability of being asleep: 27.44%3）10:30 PM probability of being asleep: 73.91%4）The probability of sleep increases to above 50% at 10:14 PM 由此可以看到，入睡时间在10:14 PM时的概率超过50%，说明睡眠质量不错。利用利用LDALDA对文本进行主题提取对文本进行主题提取1. Human machine interface for lab abc computer applications2. A survey of user opini

32、on of computer system response time3. The EPS user interface management system4. System and human system engineering testing of EPS5. Relation of user perceived response time to error measurement6. The generation of random binary unordered trees7. The intersection graph of paths in trees8. Graph min

33、ors IV Widths of trees and well quasi ordering9. Graph minors A survey 自制以下文本，通过LDA算法对以上文档提取主题。利用利用LDALDA对文本进行主题提取对文本进行主题提取 首先，将这个文件读进来并对每行的文档进行分词，去掉停用词。 然后，构建字典，计算每个文档中的TF-IDF值。根据字典，将每行文档都转换为索引的形式。转换后还是每行一篇文章，只是原来的文字变成了（索引，1）的形式，这个索引根据的是字典中的（索引，词）。打印结果如下：(0,1),(1,1),(2,1),(3,1),(4,1),(5,1),(6,1)(4,

34、1),(7,1),(8,1),(9,1),(10,1),(11,1),(12,1)(6,1),(7,1),(9,1),(13,1),(14,1)(5,1),(7,2),(14,1),(15,1),(16,1)(9,1),(10,1),(12,1),(17,1),(18,1),(19,1),(20,1)(21,1),(22,1),(23,1),(24,1),(25,1)(25,1),(26,1),(27,1),(28,1)(25,1),(26,1),(29,1),(30,1),(31,1),(32,1),(33,1),(34,1)(8,1),(26,1),(29,1)利用利用LDALDA对文本进

35、行主题提取对文本进行主题提取 接着，对每篇文档中的每个词都计算TF-IDF值，此时仍然是每一行一篇文档，只是上面一步中的1的位置，变成了每个词索引所对应的TF-IDF值了。 最后，我们使用每篇文章的TF-IDF值来作为特征输入进LDA模型，得到各文档的主题，结果如下：(0, 0.25865201763870671), (1, 0.7413479823612934), (0, 0.6704214035190138), (1, 0.32957859648098625), (0, 0.34722886288787302), (1, 0.65277113711212698), (0, 0.64268836524831052), (1, 0.35731163475168948), (0, 0.67316053818546506), (1, 0.32683946181453505), (0, 0.37897103968594514), (1, 0.62102896031405486), (0, 0.6244681672561716), (1, 0.37553183274382845), (0, 0.74840501728867792), (1, 0.25159498271132213), (0, 0.65364678163446832), (1, 0.34635321836553179)