【随机化算法】

随机化算法（Randomized Algorithms）在密码学中具有核心作用。因此，在密码学中讨论“高效计算”时，不能只考虑确定性多项式时间模型，还需要考虑概率多项式时间（Probabilistic Polynomial Time）模型

引入：随机化算法实例

【基本思想】

在计算复杂性理论中，P 与 NP 都是复杂性类（Complexity Classes），它们不是单个问题，而是由一类判定问题构成的集合

为了形式化地讨论判定问题，通常将判定问题表示为语言（Language）。设 $\Sigma$ 为一个有限字母表，则 $\Sigma^{*}$ 表示由 $\Sigma$ 中字符组成的所有有限长度字符串的集合。如果 $L\subseteq \Sigma^{*}$，则称 $L$ 是 $\Sigma$ 上的一个语言

【概述】

密码学（Cryptography）一直与设计和分析加密方案的问题相关，即通过不安全通信媒介提供秘密通信的方案。自 20 世纪 70 年代以来，诸如构建不可伪造的数字签名、设计容错协议等问题也被视为密码学范畴。事实上，密码学可被视为一门研究如何设计任何需要抵御恶意滥用企图的系统的学科

单向函数（One-way Function）是在密码学中具重要意义的函数，其是一个单射函数，对于每一个输入 $x$，可以在多项式时间内计算出函数值 $f(x)$，但是给定一个函数值 $y$，要找到一个输入 $x$ 使得 $f(x)=y$ 在计算上是困难的

【概述】

随着机器学习、深度学习的发展，语音、图像、自然语言处理逐渐取得了很大的突破，语音、图像、文本都是简单的序列或网格数据，深度学习很擅长处理该类的结构化数据

但现实世界中并非所有事物都是结构化数据，即并非都可以表示为一个序列或者一个网络，例如社交网络、知识图谱、复杂的文件系统等

【概述】

对于 DDPM 来说，一个最大的缺点是需要设置较长的扩散步数才能得到好的效果，这导致了生成样本的速度较慢，比如扩散步数为 $1000$ 的话，那么生成一个样本就要模型推理 $1000$ 次

为此 Jiaming Song 等学者在《Denoising Diffusion Implicit Models》 中针对 DDPM 进行了改进，提出了去噪扩散隐式模型（Denoising Diffusion Implicit Models，DDIM），不再限制前向和反向过程必须是马尔卡夫链，在不牺牲质量的情况下，允许更少的采样步数来加速反向生成过程

【概述】

2020 年 6 月，Jonathan Ho 等学者在《Denoising Diffusion Probabilistic Models》中对之前的扩散概率模型进行了简化，并通过变分推断，将后验问题转为优化问题进行建模，提出了经典的去噪扩散概率模型（Denoising Diffusion Probabilistic Model，DDPM），将扩散概率模型的思想用于图像生成，目前所说的扩散模型，大多是基于该模型进行改进

简单来说，DDPM 包含两个过程：

【概述】

扩散概率模型（Diffusion Probabilistic Models，DPM）于 2015 年 《Deep Unsupervised Learning using Nonequilibrium Thermodynamics》提出，其目的是消除对训练图像连续应用的高斯噪声，可以将其视为一系列去噪自编码器，是扩散模型的起源，但是没有真正应用于 CV，NLP 任务

其基本思想是使用马尔可夫链利用扩散过程将一个简单的已知分布（例如高斯分布）逐渐转换为目标分布（例如数据分布）