变态家族

用MDP（马尔可夫决策过程）来搜索iPod Shuffle里面的歌

Filed at 5:12 am under 科学家们研究的东西 by biantaishabi

Peter Norvig 和我一样， 都是Markov的fans， 不同的是他有我这个贫下中农没有的iPod Shuffle。 Shuffle其实应该就是iPod的简化版本吧， 硬盘小， 而且不能显示。 这样， 从里面找歌就比较麻烦。 他的这个帖子 就讲到了这个问题。 他的朋友 Martin的找歌的办法是这样的， 先在iTune里面讲shuffle里面的歌按照歌名或者歌手名排列。 先用shuffle mode随机播放， 当你觉得当前的歌离你要找的歌比较近的时候， 可以在顺序播放模式下， 按前进或者后退按钮， 这样就可以找到你的目标了。

但是一个Shuffle里面的歌几百首， 应该怎么样才能比较快的找到歌呢。 Peter想到了大胡子Markov， 是一个叫MDP（Markov Decision Process）的方法。 如果有250首歌， 其实就是250个状态， 按随机播放就是在这些状态中跳来跳去， 实际是一个Markov过程–他和前面的选择没有关系。 Markov过程引入决策， 再引入我们的目标——尽快地找到歌， 也就是cost，或者是他的负值即报酬， 就是一个MDP过程了。 这是五十年代就有数学家研究的一个问题， 后来理论发展得比较完善， 但是由于那个时候的计算机比较菜， 生成处理比较大的状态转移矩阵都很不容易， 所以一直没有很好的运用的实际中去。 最近计算机牛起来了， 这个方法在实际中也多起来。

在MDP中， 定义如下：

• 状态空间S： 在Shuffle这个例子里面， 1G的歌大概有250首， 这样状态空间的大小就是250。
• 策略空间A： 在某个属于状态空间的状态i可以采取的策略。 这里Peter定义的两种策略是随机播放和顺序播放， 这里的顺序播放不是按一下next或者preivous键， 而是一直按这两键之一到找到歌为止， 将一连串的动作定义为一个策略。
• 状态转移矩阵P：和一般Markov过程中的状态转移矩阵一样， 具有Markov的特性。 及与T时刻之前的状态无关， 只与当前的状态有关。 或者也可以同教科书里面说的那样， 叫做无后效性。
• 报酬R：别的地方一般叫cost， 这个地方叫报酬， 当然是因为决策都是想带来报酬的。
• 准则：Peter没有写这样， 因为这里很简单， 即让设定的cost即时间最小即可。 和我们所知道的目标方程相同， 用来判断策略的优劣。

一般还会有的东西是折扣。 这个很好理解， 现在的预期总是最重要的， 没有到来的东西就要打上折扣。 可以用通货膨胀来理解， 现在的钱总是比未来的钱要值钱， 经济学里面都这样算。 而且如果是无限步的决策过程的话， 加上折扣才能使之收敛。 折扣模型是几十年来MDP中被研究得最完善的模型， 所以一般的应用都会有。 在这里Peter开始就没有用到折扣， 后来经别人提醒用到了Bellman的折扣方程， 发现收敛的速度大大的加快了。

再重新看一下我们要做什么， 我们是要在一个行动的全过程中–这里是找到我们要找的歌， 每次根据当前的状态作出决策，让系统(这里是你的shuffle) 走到转移矩阵定下的下一个状态， 经过一系列的决策， 达到目标。 这里我们要选择最优的决策， 让我们得到的报酬最大， 或者惩罚最小。 在这里是让找歌的时间最短。 对， 这就是我为什么这么关心这个我没有的shuffle的原因， 因为它和优化有关。

这里的cost实际上是每个状态的cost的期望值的平均， 但是问题在这里， 现在状态的的期望值和下一个状态有关， 而下一个状态的期望值又和其他的状态有关。 大家相互关联。 在这里， 我们可以猜测一个初值， 然后再去迭代， 直到最后值稳定为止。 我们可以看看Peter的实现， 他用了最简单的值迭代的方法， 让整个过程收敛。 假设目标在列表的中间， 由于实际上歌的排列是一个环形， 这个假设并不会影响一般性。 假设顺序找歌的时间是1秒， 而随机是3秒。 cost是现在的歌到目标歌曲的距离。 这是他的code， 用Python实现 。

def valueiteration(N, T, epsilon=0.001):
    t = N/2
    states = range(N)
    V1 = [abs(s-t) for s in states]
    V2 = [0.0 for s in states]
    while max([abs(V2[s]-V1[s]) for s in states]) > epsilon:
        shufflecost = T + avg([V1[r] for r in states])
        for s in states:
            V2[s] = min(abs(s-t), shufflecost)
        V1, V2 = V2, V1
    return V2

应该感谢数学家， 因为有数学家已经证明， 这个最优策略集肯定是存在的， 这个值迭代也肯定会是收敛的。 除了值迭代， 还有策略迭代。 还有上面说过， 如果用Bellman的折扣方程， 及将下一次的期望乘上一个小于1大于零的折扣， 下下次的期望乘上这个折扣的平房，以此类推。 收敛就会快一些。

接下来只要写一个简单的avg平均函数， 和一个print的主函数就行了。 这是他的结果。

T=1 (N=250) ==> shuffle when 15 or more away
Mean: 14.8, Median: 15.8; Max: 15.8

T=5 (N=250) ==> shuffle when 35 or more away
Mean: 30.4, Median: 35.4; Max: 35.4

T=10 (N=250) ==> shuffle when 50 or more away
Mean: 40.0, Median: 50.0; Max: 50.0

T是假设的shuffle的时间， N是歌曲的数量， 这就是让你在各个T下能最快找到歌的最优策略。

这就是一个MDP的 例子， 对于Markov的fans还有有shuffle的人倒是很有意思。 一些都很完美， 不是吗？ 模型建的很漂亮， code也很简单。

但是发现一个问题没有？ 我至少第一次是没有看懂这个最后的结果的。 因为我觉得这个Shuffle when 15 or more away根本不像是一个策略。 因为正常人是没有办法在一个没有显示的shuffle上知道你到底离目标歌曲是15还是18还是20的， 即使是 Google 的AI专家Peter估计也没有这个本事。 我觉得人不能为了解决一个问题而赋予自己超能力， 所以决定写信告诉Peter超人还没有出生。 实际上250首歌不会平均的分配在26个字母里面， 所以说很难知道歌的准确距离。 事实上， 他的朋友Martin找歌的时侯估计会看当前歌名的首字母， 再根据目标歌名的首字母， 去估计cost。 为了更准确， 还可以给歌名比较多的首字母加上更大的权重。 这样， 收敛估计会比较慢， 因为没有用到peter假设的根本不可能知道的信息， 增加了不确定性。 但是肯定还是可以得到这种情况下的最优策略集的。

 一天以后， Peter就回了信， 承认他错了， 他说确实一个人需要无敌的记忆力才能知道那个值迭代里面写的abs（t-s）的值。 从AI的角度说， 应该修改这个期望值的计算方法的。 还应该在这个帖子里面再作一些讨论。

马氏过程的应用很广， 机器人路径计划， 自动飞行器导航， 电梯计划， 网络交换和路由， 银行客户保有等等。 似乎和优化有关的就能用到它，只要Markov过程能和 决策还有报酬有关的就能用上它。 说不定我的layout也能用上它。

这个故事告诉我们 ， 建模列方程的时候要假设自己没有超能力。

一些关于MDP的链接：

12 comments »