image caption with X

Image Captioning方面的工作可以总结为“Image Captioning with X”，其中的 X 可以是 Visual Attention, Visual Attributes, Entity Recognition, Dense Caption 和 Reinforcement Learning等模块。

Visual Attention

注意力包括软注意力(soft attention)和强注意力

软注意力的关键点在于，这种注意力更关注区域或者通道，而且软注意力是确定性的注意力，学习完成后直接可以通过网络生成，最关键的地方是软注意力是可微的，这是一个非常重要的地方。可以微分的注意力就可以通过神经网络算出梯度并且前向传播和后向反馈来学习得到注意力的权重。

强注意力与软注意力不同点在于，首先强注意力是更加关注点，也就是图像中的每个点都有可能延伸出注意力，同时强注意力是一个随机的预测过程，更强调动态变化。当然，最关键是强注意力是一个不可微的注意力，训练过程往往是通过增强学习(reinforcement learning)来完成的。

attention是学出一个权重分布，再拿这个权重分布施加在原来的特征之上。简单来说：

这个加权可以是保留所有分量均做加权（即soft attention）；也可以是在分布中以某种采样策略选取部分分量（即hard attention）。
这个加权可以作用在原图上，也就是RAM和DRAM；也可以作用在特征图上，如后续的好多文章（例如image caption)。
这个加权可以作用在空间尺度上，给不同空间区域加权；也可以作用在channel尺度上，给不同通道特征加权；甚至特征图上每个元素加权。
这个加权还可以作用在不同时刻历史特征上，如Machine Translation。

Reinforcement Learning

强化学习（Reinforcement Learning，简称RL）是机器学习的一个重要分支。在强化学习中，包含两种基本的元素：状态与动作，在某个状态下执行某种动作，这便是一种策略，学习器要做的就是通过不断地探索学习，从而获得一个好的策略。例如：在围棋中，一种落棋的局面就是一种状态，若能知道每种局面下的最优落子动作，那就攻无不克/百战不殆了~

若将状态看作为属性，动作看作为标记，易知：监督学习和强化学习都是在试图寻找一个映射，从已知属性/状态推断出标记/动作，这样强化学习中的策略相当于监督学习中的分类/回归器。但在实际问题中，强化学习并没有监督学习那样的标记信息，通常都是在尝试动作后才能获得结果，因此强化学习是通过反馈的结果信息不断调整之前的策略，从而算法能够学习到：在什么样的状态下选择什么样的动作可以获得最好的结果。

强化学习和监督学习最大的区别是它没有监督学习已经准备好的训练数据输出值。强化学习只有奖励值，但是这个奖励值和监督学习的输出值不一样，它不是事先给出的，而是延后给出的。同时，强化学习的每一步与时间顺序前后关系紧密。而监督学习的训练数据之间一般都是独立的，没有这种前后的依赖关系。
强化学习和非监督学习的区别。也还是在奖励值这个地方。非监督学习是没有输出值也没有奖励值的，它只有数据特征。同时和监督学习一样，数据之间也都是独立的，没有强化学习这样的前后依赖关系。

基本概念

强化学习任务通常使用马尔可夫决策过程（Markov Decision Process，简称MDP）来描述，具体而言：机器处在一个环境中，每个状态为机器对当前环境的感知；机器只能通过动作来影响环境，当机器执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据潜在的奖赏函数反馈给机器一个奖赏。综合而言，强化学习主要包含四个要素：状态、动作、转移概率以及奖赏函数。

状态（X）：机器对环境的感知，所有可能的状态称为状态空间；
动作（A）：机器所采取的动作，所有能采取的动作构成动作空间；
转移概率（P）：当执行某个动作后，当前状态会以某种概率转移到另一个状态；
奖赏函数（R）：在状态转移的同时，环境给反馈给机器一个奖赏。

因此，强化学习的主要任务就是通过在环境中不断地尝试，根据尝试获得的反馈信息调整策略，最终生成一个较好的策略π，机器根据这个策略便能知道在什么状态下应该执行什么动作。常见的策略表示方法有以下两种：

确定性策略：π（x）=a，即在状态x下执行a动作；
随机性策略：P=π（x,a），即在状态x下执行a动作的概率。

一个策略的优劣取决于长期执行这一策略后的累积奖赏，换句话说：可以使用累积奖赏来评估策略的好坏，最优策略则表示在初始状态下一直执行该策略后，最后的累积奖赏值最高。长期累积奖赏通常使用下述两种计算方法：

K摇臂赌博机

首先我们考虑强化学习最简单的情形：仅考虑一步操作，即在状态x下只需执行一次动作a便能观察到奖赏结果。易知：欲最大化单步奖赏，我们需要知道每个动作带来的期望奖赏值，这样便能选择奖赏值最大的动作来执行。若每个动作的奖赏值为确定值，则只需要将每个动作尝试一遍即可，但大多数情形下，一个动作的奖赏值来源于一个概率分布，因此需要进行多次的尝试。

单步强化学习实质上是K-摇臂赌博机（K-armed bandit）的原型，一般我们尝试动作的次数是有限的，那如何利用有限的次数进行有效地探索呢？这里有两种基本的想法：

仅探索法：将尝试的机会平均分给每一个动作，即轮流执行，最终将每个动作的平均奖赏作为期望奖赏的近似值。
仅利用法：将尝试的机会分给当前平均奖赏值最大的动作，隐含着让一部分人先富起来的思想。

可以看出：上述两种方法是相互矛盾的，仅探索法能较好地估算每个动作的期望奖赏，但是没能根据当前的反馈结果调整尝试策略；仅利用法在每次尝试之后都更新尝试策略，符合强化学习的思维，但容易找不到最优动作。因此需要在这两者之间进行折中。

折中1： ε-贪心

ε-贪心法基于一个概率来对探索和利用进行折中，具体而言：在每次尝试时，以ε的概率进行探索，即以均匀概率随机选择一个动作；以1-ε的概率进行利用，即选择当前最优的动作。ε-贪心法只需记录每个动作的当前平均奖赏值与被选中的次数，便可以增量式更新。

折中2： Softmax

Softmax算法则基于当前每个动作的平均奖赏值来对探索和利用进行折中，Softmax函数将一组值转化为一组概率，值越大对应的概率也越高，因此当前平均奖赏值越高的动作被选中的几率也越大。Softmax函数如下所示：

有模型学习

若学习任务中的四个要素都已知，即状态空间、动作空间、转移概率以及奖赏函数都已经给出，这样的情形称为“有模型学习”。假设状态空间和动作空间均为有限，即均为离散值，这样我们不用通过尝试便可以对某个策略进行评估。

策略评估

前面提到：在模型已知的前提下，我们可以对任意策略的进行评估（后续会给出演算过程）。一般常使用以下两种值函数来评估某个策略的优劣：

状态值函数（V）：V（x），即从状态x出发，使用π策略所带来的累积奖赏；
状态-动作值函数（Q）：Q（x,a），即从状态x出发，执行动作a后再使用π策略所带来的累积奖赏。

根据累积奖赏的定义，我们可以引入T步累积奖赏与r折扣累积奖赏：

折扣累计奖励： $\gamma$是奖励衰减因子，在[0，1]之间。如果为0，则是贪婪法，即价值只由当前延时奖励决定，如果是1，则所有的后续状态奖励和当前奖励一视同仁。大多数时候，我们会取一个0到1之间的数字，即当前延时奖励的权重比后续奖励的权重大。含义是虽然当前动作会给一个延时奖励$r_t$，即使当前奖励很高，但到了$t+1、t+2$等时刻，后续的延时奖励不一定也高。比如下象棋，我们可以某个动作可以吃掉对方的车，这个延时奖励是很高，但是接着后面我们输棋了。此时吃车的动作奖励值高但是价值并不高。

由于MDP具有马尔可夫性，即现在决定未来，将来和过去无关，我们很容易找到值函数的递归关系：

关于上面的推导：

π（x，a）指的是在x状态下执行a动作的概率
执行a动作后达到的状态不是唯一的，也是一个概率，所以$P^a_{x\rightarrow x^{‘}}$指的是执行a动作后到达x状态的概率
以上的公式可以理解为，T步的累计奖励分为第一步的奖励和后T-1步的累积奖励
- 后T-1步的奖励为$V^π_{T-1}(x^{‘})$，权重为$\frac{T-1}{T}$
- 第一步的奖励为$R^a_{x\rightarrow x^{‘}}$
- 最后需要在外面考虑执行a动作的概率和执行a动作后到达$x^{‘}$状态的概率
类似地，对于r折扣累积奖赏可以得到：

易知：当模型已知时，策略的评估问题转化为一种动态规划问题，即以填表格的形式自底向上，先求解每个状态的单步累积奖赏，再求解每个状态的两步累积奖赏，一直迭代逐步求解出每个状态的T步累积奖赏。算法流程如下所示：

对于状态-动作值函数，只需通过简单的转化便可得到：

策略改进

理想的策略应能使得每个状态的累积奖赏之和最大，简单来理解就是：不管处于什么状态，只要通过该策略执行动作，总能得到较好的结果。因此对于给定的某个策略，我们需要对其进行改进，从而得到最优的值函数

最优Bellman等式改进策略的方式为：将策略选择的动作改为当前最优的动作，而不是像之前那样对每种可能的动作进行求和。易知：选择当前最优动作相当于将所有的概率都赋给累积奖赏值最大的动作，因此每次改进都会使得值函数单调递增。

策略迭代：初始策略，策略评估，然后策略改进……不断迭代

将策略评估与策略改进结合起来，我们便得到了生成最优策略的方法：先给定一个随机策略，现对该策略进行评估，然后再改进，接着再评估/改进一直到策略收敛、不再发生改变。这便是策略迭代算法，算法流程如下所示：

可以看出：策略迭代法在每次改进策略后都要对策略进行重新评估，因此比较耗时。

值迭代：策略改进与值函数的改进是一致的，因此可以将策略改进视为值函数的改善

若从最优化值函数的角度出发，即先迭代得到最优的值函数，再来计算如何改变策略，这便是值迭代算法，算法流程如下所示：

免模型学习

蒙特卡罗强化学习

在现实的强化学习任务中，环境的转移函数与奖赏函数往往很难得知，因此我们需要考虑在不依赖于环境参数的条件下建立强化学习模型，这便是免模型学习。蒙特卡罗强化学习便是其中的一种经典方法。

由于模型参数未知，状态值函数不能像之前那样进行全概率展开，从而运用动态规划法求解。一种直接的方法便是通过采样来对策略进行评估/估算其值函数，蒙特卡罗强化学习正是基于采样来估计状态-动作值函数：对采样轨迹中的每一对状态-动作，记录其后的奖赏值之和，作为该状态-动作的一次累积奖赏，通过多次采样后，使用累积奖赏的平均作为状态-动作值的估计，并引入ε-贪心策略保证采样的多样性。

在上面的算法流程中，被评估和被改进的都是同一个策略，因此称为同策略蒙特卡罗强化学习算法。引入ε-贪心仅是为了便于采样评估，而在使用策略时并不需要ε-贪心，那能否仅在评估时使用ε-贪心策略，而在改进时使用原始策略呢？这便是异策略蒙特卡罗强化学习算法。

参考：周志华《Machine Learning》强化学习

井字棋实例

来自： https://www.cnblogs.com/pinard/p/9385570.html

代码：github

首先看第一个要素环境的状态$S$。这是一个九宫格，每个格子有三种状态，即没有棋子(取值0)，有第一个选手的棋子（取值1），有第二个选手的棋子（取值-1）。那么这个模型的状态一共有$3^9=1968339=19683$个

接着我们看个体的动作$A$，这里只有9个格子，每次也只能下一步，所以最多只有9个动作选项。实际上由于已经有棋子的格子是不能再下的，所以动作选项会更少。实际可以选择动作的就是那些取值为0的格子。

第三个是环境的奖励$R$，这个一般是我们自己设计。由于我们的目的是赢棋，所以如果某个动作导致的改变到的状态可以使我们赢棋，结束游戏，那么奖励最高，反之则奖励最低。其余的双方下棋动作都有奖励，但奖励较少。特别的，对于先下的棋手，不会导致结束的动作奖励要比后下的棋手少。