Jian Shuo Wang is heading to San Jose on June 5, and will return on June 11, 20006.

Ticket information:

I am a big fan of technical details, abbr. and the secret codes used on the airline ticket. Here are all printed information on my ticket. I enjoy dig into details to find out meaning behind these characters.

NON REF/CHANGE FEE APPLIES VA
LID ON UA ONLY PENALTY/CHANGES31MAY06
WANG/JIANSHUO

SHASHA
W(LB1I/qG
SHA MERCHANTS INTL
RANS / GDSL
SHANG HAI CN
08306115/04 /0

SHANGHAI PVGUA 858T 05JUN 1245
SAN FRANCISCO IUA 857H
SHANGHAI PVG

CPN 1
AIRLINE CODE 016
FORM 9415
SERIAL NUMBER 361 305
CK 4

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的链接：

RSS

在超星里面搜索“马尔可夫 决策”或者“马氏决策”， 可以找到很多这个方面的中文书。

Here comes……

Suppose we use dominoes to tile an infinite strip of height 2. In a typical tiling what fraction of the dominoes will be oriented vertically?  Typical can be defined rigorously by considering all possible tilings of a 2*n rectangle and then letting n go to infinity.

賴昌星的案件終於在香港時間今天凌晨一點有了結果,法庭接納他的上訴,主要原因是考慮到賴昌星的辯護律師提出的,擔心他回到中國之後有不穩定的結果.這樣的話,案件需要幾個月甚至一年的時間來審理,賴昌星說,會和律師商討下一步.

賴昌星涉及的是官商勾結的貪污問題,而台灣第一家庭以及第一親家的弊案,在台灣島內掀起的波瀾,也引發了國際社會的關注,美聯社就從這次事件展開,寫了一篇報導,主題就是要證明,貪污,正是華人政治的特質.

不過國民黨主席馬英九並不同意,他以新加坡為例子,指出,只要領導人有政治決心,有好的體制,貪污腐敗行為是可以被減少到最低限度的.

認同馬英九的看法,其實在華人社會裡面,不單單是新加坡,我所生活的香港就是一個很好的懲治貪污腐敗的例子.六十年代的香港,貪污腐敗成為香港普遍的現象,已經成為民眾生活的一部分,到醫院看病,要給利市,為了好一點點的醫療,打開門做生意,要打點黑白兩道,不然的話,根本沒有生存空間.也正是因為這樣,香港出現了像韓森這樣的身價上億的華人探長,那個時候,黑社會要在社會上混,首先要擺平這個探長,而那個時候,一個香港市民的收入,每個月也就是幾十港元.

不過隨著七十年代香港廉政公署的成立,像韓森這樣的人最終為了逃避法律的制裁,只能夠走避台灣,客司異鄉,而他在香港的產業也被政府凍結,知道這個星期,也是轟動香港的新聞,廉政公署和韓森的後人達成協議,收回價值一點四億,屬於韓森名下的財產.這樣的結果,對於廉政公署來說是打了一支強心針,到不是因為追討回來的金額巨大,而是向社會顯示出廉政公署打擊貪污的決心,即使貪污犯逃到了海角天涯,即使貪污犯已經離開人間,他們還要為自己的違法行為付出代價.

香港的廉政公署在剛剛成立的時候,並沒有得到市民的信任,因為之前警隊內部也有反貪污小組,但是由於涉及到自己人查自己人,調查往往沒有結果,而廉政公熟之所以能夠有效率的強力打擊貪污,和它的權利監察和制衡架構有關.廉政公署直接向行政長官負責,在調查的過程當中,不必受到其他政府部門的影響.正如馬英九所說,這正是領導人的政治決心的體現.廉政專員定期向行政會議匯報,爾立法會則作為制衡的角色,立法會可以要求廉政專員出席立法會會議,解答有關廉政公署的政策以及經費的問題,並且有賦予或廢除廉政公署的權力.

在台灣弊案頻生的時候,有台灣的立法會議員就認為,台灣缺乏的,就是像香港這樣的獨立的反貪機構,所以在調查弊案的時候,仍然存在不透明,並且可能產生不公正的情況.事實上,香港的廉政公署的工作模式,這些年,也正在為內地的反貪機構所借鑑,而且在香港回歸之後,和內地有關的貪污案件出現上升趨勢,這使得香港廉政公書這些年加強了和內地的合作.而在廉政公署的通缉名單上,剛剛在上海被釋放出獄的周正毅就在上面,不過,由於內地和香港沒有引渡協議,因此,廉政公署表示,只要周正毅不回香港,就很難將他即拿歸案.

西方社會認為,貪污是華人政治的特性,這是因為,在台灣也好,大陸也好,官商勾結,貪污腐敗的案件還是很多,但是他們卻忽視了,在一個良好的機制下面,就不會形成貪污腐敗的溫床.體制的漏洞百出,才會產生貪污腐敗的可能.

當然,民眾對於貪污的看法,教育非常的重要.在香港,廉政公署一直致力於公民的教育,三十二年來,在社會上形成一種觀念,那就是貪污必定會受到法律的制裁,民眾變的自覺,因為看到太多的例子,即使身為高官,或者家財萬貫,都可能被廉政公署請去喝一杯咖啡,接受調查,而香港成為世界上最廉潔的城市之一,有廉政公署的功勞,但是民眾的支持和覺悟更加重要.