5. Monte Carlo Methods

蒙特卡洛方法简介

使用蒙特卡洛方法不需要像DP一样，对环境要有完整的知识，而是通过经验去学习。所谓经验就是对状态、动作、奖励的采样（sample sequence）。

用sample的均值去近似期望。

使用蒙特卡洛通常需要完整的episode，因此蒙特卡洛的更新方式更像是episode-by-episode，而不是像DP的step-by-step。

4. Dynamic Programming

DP方法简介

• 由于其大量的计算损耗，已经不实用，但理论上非常重要。
• 本书后续的所有方法可以看做想要取得和DP类似的效果；只不过是减少了计算或者假设没有完美的环境模型。
• 假设解决的问题是有限的MDP，即给定动作a，状态s，和奖励r，可以通过$p(s’,r|s,a)$描述动态变化。

Policy Evaluation

评估一个策略的好坏。

3. Finite Markov DecisionProcesses

Agent和Environment的交互

• 学习者和决策者称为agent。
• agent交互的对象，外部环境，称为Environment。
• 在时刻t，agent的所处的环境用状态：$S_t \in S$表示，$S$是可能的状态集。假设agent采用了动作$A_t\in A(S_t)$，$A(S_t)$代表在状态$S_t$下可能的动作集。
• 到了下一个时刻t+1，agent收到了一个奖励：$R_{t+1} \in R$，并且发现自己处在一个新的state中：$S_{t+1}$。

什么是有限

2. Multi-armed Bandits

k-armed Bandit Problem，K臂老虎机

问题描述：重复面临有k种选择的情况，每一次选择之后，都会收到一个reward。这个reward服从一个跟你的选择相关的分布。你的目标是，在选择t次后，找到最大的期望reward。

为什么叫K臂老虎机：有K个单臂老虎机，每个时间节点，你可以选择K个中任意一个老虎机选择按下它的臂，然后获得一个奖励。目标自然是多次选择之后的累计奖励最大。

形式化定义：假设时刻$t$的动作是$A_t$，reward是$R_t$，定义价值函数：$q_*(a) = E[R_t|A_t=a]$。

1. Introduction

书本介绍

Reinforcement Learning

作者: Richard S. Sutton / Andrew G. Barto

最近在一个项目中大量使用正则表达式，对各种用法做个梳理。

简介

正则表达式的作用是检查一个字符串是否与某种模式匹配。Python中的re模块提供正则匹配相关的方法。

语法

Python正则表达式测试网站：https://pythex.org/

动机

其实差不多半年之前就想吐槽Tensorflow的seq2seq了（后面博主去干了些别的事情），官方的代码已经抛弃原来用静态rnn实现的版本了，而官网的tutorial现在还是介绍基于静态的rnn的模型，加bucket那套，看这里。

看到了吗？是legacy_seq2seq的。本来Tensorflow的seq2seq的实现相比于pytorch已经很复杂了，还没有个正经的tutorial，哎。
好的，回到正题，遇到问题解决问题，想办法找一个最佳的Tensorflow的seq2seq解决方案！

学习的资料

• 知名博主WildML给google写了个通用的seq2seq，文档地址，Github地址。这个框架已经被Tensorflow采用，后面我们的代码也会基于这里的实现。但本身这个框架是为了让用户直接写参数就能简单地构建网络，因此文档没有太多参考价值，我们直接借用其中的代码构建自己的网络。
• 俄罗斯小伙ematvey写的：tensorflow-seq2seq-tutorials，Github地址。介绍使用动态rnn构建seq2seq，decoder使用raw_rnn，原理和WildML的方案差不多。多说一句，这哥们当时也是吐槽Tensorflow的文档，写了那么个仓库当第三方的文档使，现在都400+个star了。真是有漏洞就有机遇啊，哈哈。

概率无向图模型

回顾一下之前讲解的概率无向图模型：https://applenob.github.io/machine_learning/graph.html

总结一下：

• 最大团：无向图$G$中任何两个结点都有边连接的结点子集称为团（clique）。若团$C$不能在加入任何一个结点使其称为一个更大的团，则称$C$为图$G$的一个最大团。
• 概率无向图模型的联合概率分布可以表示成其最大团上的随机变量的函数的乘积形式。这也被称为概率无向图模型的因子分解。
• $P(Y) = \frac{1}{Z}\prod_C\psi_C(Y_C)$，其中，$Z$是规范化因子，$Z = \sum_Y\prod_C\psi_C(Y_C)$，$\psi_C(Y_C)$称为势函数，要求势函数是严格正的（因为涉及到累乘）。

条件随机场

模型推导

最大熵是选择最优模型的一个准则，即，首先要满足已有的事实（约束条件），然后在没有更多信息的情况下，那些不确定的部分都是“等可能的”。“等可能”本身不容易操作，熵是一个可以优化的数值目标。

这里最大熵最大化的，是条件熵$H(Y|X)$。

$$H(Y|X)=-\sum_{x,y}\hat{P}(x)P(y|x)logP(y|x)$$

具体的关于信息熵的文章，可以看colah的这篇博客，里面对信息熵/互信息/条件熵的物理意义做很好的解释。

这篇博客中，我通过学习hankcs的Java版本，自己试着做一个简单的Python版本，用于学习和理清思路。

思路

所谓生成式句法解析是指生成一些列依存句法树，挑出概率最大的一棵。

这里的实现考虑了词性信息+词汇信息，使用最大生成树Prim算法搜索最终结果，实现一个简单的汉语依存句法分析器。

具体：