3 most important points
- 马尔科夫链：建立概率自动机
- 应用 1：基于概率自动机通过多次独立实验得到复杂问题的近似解（蒙特卡洛方法），例如原子弹（得到中子个数和原材料质量）和 Google 搜索算法（得到每个网页被访问的概率）
- 应用 2：基于概率自动机预测下一个状态（语言模型）
5 thoughts
- 有哪些常见的深度学习算法是基于马尔科夫链的？
- 概率自动机在日常生活中还有什么应用场景？
- 哪些系统不可以用马尔科夫链建模？（比如说正反馈系统，相当于有无数个状态）
- 所以，在状态个数时有限的时候，就可以使用马尔科夫链？
Notes
- 大数定理：平均结果随着越来越多独立实验逐渐接近期望值
- 马尔科夫链
马尔科夫和他的对家 battle，为了证明大数定理不止在独立事件上应用，建立了一个关于句子中单词开头是元音还是辅音的模型
- 统计元音/辅音出现的概率和元音辅音组合出现的概率，得到模型：
下图中的 0.13=0.06/0.43 - 从 V 出发，通过随机数模拟重复多次实验后，元音与辅音的概率趋近于统计值：
- 统计元音/辅音出现的概率和元音辅音组合出现的概率，得到模型：
- 优势
- 对于一个复杂的系统，只需要关注当前状态，这种“无记忆性”使人们能将复杂的系统大大简化，却仍能做出有意义的预测
- 应用
- 原子弹
- 核裂变
- 原理：中子撞击原子核随机弹出新的 2~3 个中子
- 问题：至少需要多少原材料能制作原子弹
- 难点：过程随机难以通过计算分析得到解析解
- 解法：依照马尔科夫链，建立不同结果的模型，通过大量模拟得到结果
- 蒙特卡洛方法
- 解决原子弹制作难点的这种模拟方法被称为蒙特卡洛方法 蒙特卡洛是一家赌场
- 通过对大量随机样本进行统计分析来获得问题的近似解
- 核裂变
- 搜索引擎
- Yahoo
- 原理：搜索顺序按关键词计数排行
- 优势：大量营销
- Google
- 原理：马尔科夫链——假设 A 网页只链接到 B 网页，那么转移概率就是 100%，而 B 链接到 ACD，转移概率各为 33%，以此类推；为了避免未被链接的网页不能被搜索到，模拟中 15%的时间进行随机跳转
- 优势：搜索结果好且准确 因此 Google 吸引了大量用户使用，最终取代 Yahoo
- 原理：马尔科夫链——假设 A 网页只链接到 B 网页，那么转移概率就是 100%，而 B 链接到 ACD，转移概率各为 33%，以此类推；为了避免未被链接的网页不能被搜索到，模拟中 15%的时间进行随机跳转
- Yahoo
- 语言模型
- 原理：以单词或词元（Token，可能是单词，也可能是字母、标点、短语等）为节点构造马尔科夫链，即可预测下一个词元
- 改进：引入了注意力机制，通过上下文赋予词元更多含义
- 隐患：通过合成数据训练，生成结果会变得非常稳定，这是我们不希望看到的
- 原子弹