本学位论文报告了统计物理方法在图模型统计预测问题中的应用。这些图模型包括纠错码，逆伊辛问题和伊辛感知器监督学习问题。我们主要利用无序系统研究中启发的思想和方法，比如复本技术、空腔方法和种群动力学模拟等，为这些计算机科学或统计物理问题发展低计算复杂度的高效算法，并且对它们的典型性质进行研究。本论文研究的问题对信息论、计算机科学、离散数学、计算生物学亦有所启发。　　 在第一章我们将对自旋玻璃的平均场理论，约束满足问题的基本概念、研究方法和研究思想作简要的介绍。接下来的三章将分别阐述我们的工作对三个统计物理与计算机科学、信息论交叉领域的贡献：　　 第二章研究了纠错码中与统计物理最相关的的一种-Sourlas码的典型性质和解码算法设计。我们考虑有限编码率的稀疏Sourlas码，利用空腔方法计算了其有限温自由能，导出了有限温信任度传递算法；零温极限对应的是警告传递算法，但仅考虑了基态能量的贡献，我们基于空腔方法将空腔场展开到温度的一阶项，导出了渐失空腔场传递方程，从而将基态熵的信息包含到解码过程中来。单个实例的解码实验验证了渐失空腔场传递算法的高效性，并且与种群动力学模拟的平均场结果吻合。与警告传递算法相比，在高信道噪声水平情况下，它能提高两体构造码的解码率8％，三体构造码的3％。我们的结果显示在信息系统中考虑基态熵的效应是很重要的，并且将有助于我们提高传统算法的解码性能。　　 第三章研究了最近被广泛关注的逆伊辛问题。逆伊辛问题在计算机科学中也称为玻耳兹曼机器学习或学习图模型。它是用自旋玻璃伊辛模型来拟合实验数据(来自蒙特卡罗采样或真实生物实验)，以使伊辛模型的磁化强度和两点关联与实验对应值相吻合。这一方面是由于最大熵方法(伊辛玻耳兹曼分布)被证明能够反映大多数真实神经网络的大部分关联活动，而且对基因网络，蛋白质相互作用网络重构依然十分有效。因此，对于高维数据，我们只需预测参数(hi，Jij)，即外场和耦合参数。为简单起见，我们选择已经被充分研究的Hopfield模型，我们利用简单的Glauber动力学对相空间进行采样，分析了快速平均场算法，即简单平均场近似，独立自旋对近似，Sessak-Monasson近似，和逆Thouless-Anderson-Palmer方程，对Hopfield网络重构的性能。我们的工作表明，作为逆问题，顺磁相往往对网络重构起到十分重要的作用，当取样数据来源于顺磁相时，我们能够很准确的获得网络的原有拓扑信息。而在存储相，我们尽管能够利用简单局域动力学回忆某个模式，但我们却丢失了系统原有的拓扑信息，这个结论无论对完全网络还是稀疏网络都成立。另外，我们还分析了流行的消息传递算法的性能，我们发现与平均场算法相比，它能更好的预测网络的拓扑信息，即便在低温情形。当然，随着温度的降低，给定抽样数目的数据将高度磁化，这将导致该算法不收敛，直到凝固数据(至少有两个磁化强度的绝对值为+1)的出现，消息传递算法将不能工作。更重要的一点是，网络重构对态空间取样过程的敏感性往往被忽略，我们的研究表明当态取样过程允许态跃迁时，这种形式的抽样能够大大降低重构误差，这也解释了低温重构误差呈现样本间大涨落的现象。我们在这一章也提出了利用逆伊辛问题来估计大量实验数据背后的模型(或者系统)的状态的数目(熵)的方法，该估算的准确性不仅依赖于所提供的数据，而且依赖于对消息传递算法迭代过程动力学行为的把握，为了较为可靠的得出合适的熵值，我们对于算法不收敛情形提出在最大的收敛比例估算的判据，对真实神经网络状态数目的估算与已有值较为吻合，它们都给出真实值的上限。　　 在第四章，我们研究了伊辛感知器的监督学习问题，发展了用于该问题的权重空间局域搜索算法。训练一个伊辛感知器，即通过调整二元权重值以使感知器能完成随机模式集的正确分类任务，是一个NP完备问题。我们定义模式数目P与权重数目Ⅳ之比为学习阈值α，而理论学习阈值为αs()0.833，在这个阈值之下，权重空间是非空的。最近的研究表明该空间由少数大的解簇和大量小的解簇平分主导。这里我们定义互连的解的集合为解簇，于是，我们设计了权重空间随机行走算法，亦即序列学习过程，在这个过程当中，权重构型是随着模式的添加而动态调整的，每一步调整相当于在权重空间随机行走了一步，但是必须保证不能忘记先前所学的随机模式。每一步随机行走通过单权重翻转或双权重翻转完成，直到新加的当前模式被记住。我们的实例模拟结果显示，在N≤1000量级，我们的平均实际学习阈值可达α≥0.4。值得注意的是，这种随机行走策略的性能随Ⅳ的增大呈幂率下降α∝N-γ。为了进一步提高单个随机行走的学习性能，我们设计了两个互相通信的随机行走，“通信”是指这两个随机行走是由它们之间的汉明距离和各自的能量函数引导的。这里，我们把模式集拆分成不同部分，先让两个随机行走各自完成相同数目的模式(仅是整个模式集的一部分)的学习，这些模式虽然数目相同但未必完全一样。然后两个随机行走开始在各自的权重空间通过通信的方式寻找对应整个模式集的最终的解。我们的数值实验支持了该机制的高效性，并且汉明距离和能量函数与简单的退火计算大致吻合。　　 我们在最后一章给出总结与展望，期望我们的研究方法能够进一步促进人们对于图模型统计预测问题的理解，并启发更多的基于统计物理分析的实用算法。