看到一個有趣的網站
裡面有個東西叫世界時鐘(world clock)
這不是一般的時鐘
上面顯示了許多統計資訊
比如說人口資訊
世界: 68億
中國: 13.5億
印度: 11.8億
歐洲: 5.1億
美國: 3.1億
該網站還有很多有趣的統計數字 可上去逛逛
Saturday, May 8, 2010
Friday, May 7, 2010
Markov chain model (馬可夫鍊模型) 與求解演算法 forward/backward algorithm
在電腦科學中，graphical model 是一個用來定義機率模型的好工具
而馬可夫鍊模型是graphical mode中常見的一個機率模型
最近看了 Mark Schmidt 所寫的 Matlab 函式庫和教學文件
覺得作者的講解很清楚
只要有基本的機率知識就能夠了解
有興趣的人可以看一看
首先推薦其中一篇說明 Markov chain model 教學文件
以 computer science 學生畢業後的出路為範例
每個人在他畢業後的60年內
每一年都會處於七種狀態之一
[業界, 唸博士, 玩電玩, 業界(有博士學位), 學界(有博士學位), 玩電玩(有博士學位), 離開電腦科學]
請問一個人在畢業後的第n年處於某一個狀態的機率是多少?
以下是我個人的心得
Markov chain 模型中所要描述的為一組隨機變數的機率
令這些隨機變數為 `X=X_1,X_2,...,X_N`
這些隨機變數的 joint probability 可以用一個機率函數 表示
`p(x)=p(x_1)p(x_2|x_1)p(x_3|x_2)...p(x_N|x_{N-1})`
而這個函式可以用更一般化的形式來表示
`p(x)=\frac{1}{Z}f_1(x_1,x_2)f_2(x_2,x_3)...f_{N-1}(x_{N-1},x_N)` (1)
由於加上了常數 Z , 此處的 f 不再限定是機率函數
以上的形式表現出Markov chain的性質:
由於每個隨機變數只和他相鄰的隨機變數相關
所以機率函式可以被分解為多個函數相乘
對於 `p(x)` 我們通常會感興趣的是某一個隨機變數處於某個狀態的機率
比如說 `x_2`=業界 (狀態為1)
以機率的術語來說就是 marginal probability
由於我們只考慮 `x_2` 的狀態
因此要把其他的變數的所有可能性都加總起來
`p(x_2=1)=\sum_{x_1,x_3,x_4,...)\frac{1}{Z}f_1(x_1,x_2)f_2(x_2,x_3)...f_{N-1}(x_{N-1},x_N)`
乍看之下其餘 N-1 個變數有 `2^{N-1}` 種可能
所以要計算這個總和需要非常大量的計算
但實際上卻是很容易計算的
關鍵就在於
分配律
先看一個簡單的例子
`a_1b_1+a_1b_2+a_2b_1+a_2b_2=(a_1+a_2)(b_1+b_2)`
左邊:先乘後加 -- 需要四個乘法和三個加法
右邊:先加後乘 -- 需要一個乘法和兩個加法
可以看出先加後乘在計算上比較有效率
是當變數增加的時候更為明顯
再回頭看(1)
可以發現是很相似的情況
先做 N-2 個乘法再加起來
除了一點不同:函數 f_i 牽涉到兩個變數
並無法把 `\sum_{x_1,\cdots \x_N}` 拆開
不過 當任何一個變數的值被限定時
就可以拆解開來
以上面的例子來說
令 `x2=1`
則我們可以把乘積分成兩段
`p(x_2=1)=\frac{1}{Z} [\sum_{x_1}f_1(x_1,x_2=1)][\sum_{x_3,...x_N}f_2(x_2=1,x_3)...f_{N-1}(x_{N-1},x_N)]`
到此已經解開最困難的關鍵
我們只需要分別計算以下兩個數字即可
`\sum_{x_1}f_1(x_1,x_2=1)` (3)
`\sum_{x_3,...x_N}f_2(x_2=1,x_3)...f_{N-1}(x_{N-1},x_N)` (4)
其中用來計算(3)的方法便稱之為 forward algorithm 為一種動態規劃的技巧 (dynamic programming)
forward algorithm
現在來計算 (3)
令 `Z_{i,j}` 為 `\sum_{x_1,...\x_{i-1}}f_1(x_1,x_2)f_2(x_2,x_3)...f_{i-1}(x_{i-1},x_i=j)` (3)
如此可以利用遞回的定義來計算
`Z_{i,j}=\sum_k Z_{i-1,k}f_i(k,j)`
`Z_{0,j}` 為常數 需要先定義好
有了`Z_{i,j}`之後
要計算 `p(x_i)` 便很容易
`p(x_i=j) = \frac{Z_{i,j}}{\sum_k Z_{i,k}}`
實務技巧
`Z_{i,j}`的值可能會非常大或非常小 此時難以用一般的變數來表示
比如說浮點述的精確度可能會不足
解決的方法在於加上兩個輔助的變數 `\kappa_i`, `a_{i,j}`
令 `Z_{i,j} = a_{i,j}\prod_{k=1}^i \kappa_k`
`\kappa_i` 的設定方式為使得 `\sum_k a_{i,k}=1`
如此一來 `a_{i,j}` 的範圍必定在 1 以內
此外計算 `p(x_i)` 時 `\kappa_i` 的值可以省去:
`p(x_i=j) = \frac{Z_{i,j}}{\sum_k Z_{i,k}}`
`p(x_i=j) = \frac{a_{i,j}\prod_{k=1}^i \kappa_k}{\sum_k a_{i,k}\prod_{k=1}^i \kappa_k}`
`p(x_i=j) = \frac{a_{i,j}}{\sum_k a_{i,k}}`
backward algorithm
和 forward algorithm 相似 差別只在於是從右邊算過來
在此就不贅述
經過以上的說明 有興趣的人可以看 Mark Schmidt 所寫的 Matlab 函式庫和教學文件
有完整的程式 可以實際動手玩玩看
而馬可夫鍊模型是graphical mode中常見的一個機率模型
最近看了 Mark Schmidt 所寫的 Matlab 函式庫和教學文件
覺得作者的講解很清楚
只要有基本的機率知識就能夠了解
有興趣的人可以看一看
首先推薦其中一篇說明 Markov chain model 教學文件
以 computer science 學生畢業後的出路為範例
每個人在他畢業後的60年內
每一年都會處於七種狀態之一
[業界, 唸博士, 玩電玩, 業界(有博士學位), 學界(有博士學位), 玩電玩(有博士學位), 離開電腦科學]
請問一個人在畢業後的第n年處於某一個狀態的機率是多少?
以下是我個人的心得
Markov chain 模型中所要描述的為一組隨機變數的機率
令這些隨機變數為 `X=X_1,X_2,...,X_N`
這些隨機變數的 joint probability 可以用一個機率函數 表示
`p(x)=p(x_1)p(x_2|x_1)p(x_3|x_2)...p(x_N|x_{N-1})`
而這個函式可以用更一般化的形式來表示
`p(x)=\frac{1}{Z}f_1(x_1,x_2)f_2(x_2,x_3)...f_{N-1}(x_{N-1},x_N)` (1)
由於加上了常數 Z , 此處的 f 不再限定是機率函數
以上的形式表現出Markov chain的性質:
由於每個隨機變數只和他相鄰的隨機變數相關
所以機率函式可以被分解為多個函數相乘
對於 `p(x)` 我們通常會感興趣的是某一個隨機變數處於某個狀態的機率
比如說 `x_2`=業界 (狀態為1)
以機率的術語來說就是 marginal probability
由於我們只考慮 `x_2` 的狀態
因此要把其他的變數的所有可能性都加總起來
`p(x_2=1)=\sum_{x_1,x_3,x_4,...)\frac{1}{Z}f_1(x_1,x_2)f_2(x_2,x_3)...f_{N-1}(x_{N-1},x_N)`
乍看之下其餘 N-1 個變數有 `2^{N-1}` 種可能
所以要計算這個總和需要非常大量的計算
但實際上卻是很容易計算的
關鍵就在於
分配律
先看一個簡單的例子
`a_1b_1+a_1b_2+a_2b_1+a_2b_2=(a_1+a_2)(b_1+b_2)`
左邊:先乘後加 -- 需要四個乘法和三個加法
右邊:先加後乘 -- 需要一個乘法和兩個加法
可以看出先加後乘在計算上比較有效率
是當變數增加的時候更為明顯
再回頭看(1)
可以發現是很相似的情況
先做 N-2 個乘法再加起來
除了一點不同:函數 f_i 牽涉到兩個變數
並無法把 `\sum_{x_1,\cdots \x_N}` 拆開
不過 當任何一個變數的值被限定時
就可以拆解開來
以上面的例子來說
令 `x2=1`
則我們可以把乘積分成兩段
`p(x_2=1)=\frac{1}{Z} [\sum_{x_1}f_1(x_1,x_2=1)][\sum_{x_3,...x_N}f_2(x_2=1,x_3)...f_{N-1}(x_{N-1},x_N)]`
到此已經解開最困難的關鍵
我們只需要分別計算以下兩個數字即可
`\sum_{x_1}f_1(x_1,x_2=1)` (3)
`\sum_{x_3,...x_N}f_2(x_2=1,x_3)...f_{N-1}(x_{N-1},x_N)` (4)
其中用來計算(3)的方法便稱之為 forward algorithm 為一種動態規劃的技巧 (dynamic programming)
forward algorithm
現在來計算 (3)
令 `Z_{i,j}` 為 `\sum_{x_1,...\x_{i-1}}f_1(x_1,x_2)f_2(x_2,x_3)...f_{i-1}(x_{i-1},x_i=j)` (3)
如此可以利用遞回的定義來計算
`Z_{i,j}=\sum_k Z_{i-1,k}f_i(k,j)`
`Z_{0,j}` 為常數 需要先定義好
有了`Z_{i,j}`之後
要計算 `p(x_i)` 便很容易
`p(x_i=j) = \frac{Z_{i,j}}{\sum_k Z_{i,k}}`
實務技巧
`Z_{i,j}`的值可能會非常大或非常小 此時難以用一般的變數來表示
比如說浮點述的精確度可能會不足
解決的方法在於加上兩個輔助的變數 `\kappa_i`, `a_{i,j}`
令 `Z_{i,j} = a_{i,j}\prod_{k=1}^i \kappa_k`
`\kappa_i` 的設定方式為使得 `\sum_k a_{i,k}=1`
如此一來 `a_{i,j}` 的範圍必定在 1 以內
此外計算 `p(x_i)` 時 `\kappa_i` 的值可以省去:
`p(x_i=j) = \frac{Z_{i,j}}{\sum_k Z_{i,k}}`
`p(x_i=j) = \frac{a_{i,j}\prod_{k=1}^i \kappa_k}{\sum_k a_{i,k}\prod_{k=1}^i \kappa_k}`
`p(x_i=j) = \frac{a_{i,j}}{\sum_k a_{i,k}}`
backward algorithm
和 forward algorithm 相似 差別只在於是從右邊算過來
在此就不贅述
經過以上的說明 有興趣的人可以看 Mark Schmidt 所寫的 Matlab 函式庫和教學文件
有完整的程式 可以實際動手玩玩看
Wednesday, May 5, 2010
當科技遇上漫畫
我不是學藝術出生 不過我相當喜愛看漫畫
適巧由於接觸了電腦視覺的研究領域
便想到能否將一些技術應用在製作漫畫上呢?
尋找了一些資料後 發現果然有人做了這方面的研究
而且成果還發表在知名的 SIGGRAPH 呢
此為傑出的女性為 Yingge Qu (屈穎歌) 目前為香港中文大學的博士研究員
他的研究中有兩項特別令我注目
1. Manga Colorization (漫畫著色)
2. Richness Preserving Manga Screening (將相片轉成漫畫場景)
有興趣的人可以進入他的專題網頁看看
我改天再來介紹
適巧由於接觸了電腦視覺的研究領域
便想到能否將一些技術應用在製作漫畫上呢?
尋找了一些資料後 發現果然有人做了這方面的研究
而且成果還發表在知名的 SIGGRAPH 呢
此為傑出的女性為 Yingge Qu (屈穎歌) 目前為香港中文大學的博士研究員
他的研究中有兩項特別令我注目
1. Manga Colorization (漫畫著色)
2. Richness Preserving Manga Screening (將相片轉成漫畫場景)
有興趣的人可以進入他的專題網頁看看
我改天再來介紹
Sunday, April 25, 2010
靜音手機
坐捷運或公車的時候
難免會遇到人大聲講手機
這時如果有能安靜使用的手機就好了
最高的境界是用腦波直接發話
不過在這種技術出現之前
是否可以用簡單一點的方法
比如說利用講悄悄話的時候
喉嚨只會發出氣音
如果能辨識這種語音
再還原回正常的聲音
也是一種不錯的方法吧
難免會遇到人大聲講手機
這時如果有能安靜使用的手機就好了
最高的境界是用腦波直接發話
不過在這種技術出現之前
是否可以用簡單一點的方法
比如說利用講悄悄話的時候
喉嚨只會發出氣音
如果能辨識這種語音
再還原回正常的聲音
也是一種不錯的方法吧
Friday, April 16, 2010
學習的王道 -- The Art of Learning: A Journey in the Pursuit of Excellence
"一位西洋棋高手轉練太極拳的故事"
"在台灣舉行的世界盃太極拳推手比賽"
這本書我去年在誠品時隨手翻了一下
簡單的說
書如其名 "學習的藝術"(中譯翻得怪怪的)
是作者的心路歷程
並非教人下棋或是練拳
如果是抱持著這種心態去看的人
大概會大失所望吧
再亞馬遜的書評上有看到幾篇書評
就是因此理由只給兩顆星
看這種書是蠻有趣
不過若說要學到甚麼
就如同我前幾篇提到的
此類教人成功的書
大概只能用來和作者相互印證
如果你的經歷和作者相同
那你很可能已經成功 或是即將成功
如果不同 那也不代表你的道路有誤
謹此而已
"在台灣舉行的世界盃太極拳推手比賽"
這本書我去年在誠品時隨手翻了一下
簡單的說
書如其名 "學習的藝術"(中譯翻得怪怪的)
是作者的心路歷程
並非教人下棋或是練拳
如果是抱持著這種心態去看的人
大概會大失所望吧
再亞馬遜的書評上有看到幾篇書評
就是因此理由只給兩顆星
看這種書是蠻有趣
不過若說要學到甚麼
就如同我前幾篇提到的
此類教人成功的書
大概只能用來和作者相互印證
如果你的經歷和作者相同
那你很可能已經成功 或是即將成功
如果不同 那也不代表你的道路有誤
謹此而已
Thursday, April 15, 2010
評估鍵盤使用效率 -- 鍵鼠比
長使用電腦工作的人會發現，手在滑鼠和鍵盤之間來回切換，是一件費時費力的事情。
因此我想用一個公式來表式切換的頻繁程度
首先想到的如下
每按10000次鍵字數內手在鍵盤滑鼠間的切換次數 = 切換次數 / 10000
切換的定義為
(假設以右手為操作滑鼠)
"當右手鍵被觸發後，緊接的下一個行為為滑鼠動作"
說明
1. 將鍵盤上的按鍵分為兩區，其中一區的按鍵稱為右手鍵，表示這些按鍵是由右手去按
2. 滑鼠動作包含移動滑鼠和按下任意滑鼠鍵
要給個縮寫的話就是
SKMR = switching between keyboard and mouse ratio
考慮寫個小程式來收集資料
因此我想用一個公式來表式切換的頻繁程度
首先想到的如下
每按10000次鍵字數內手在鍵盤滑鼠間的切換次數 = 切換次數 / 10000
切換的定義為
(假設以右手為操作滑鼠)
"當右手鍵被觸發後，緊接的下一個行為為滑鼠動作"
說明
1. 將鍵盤上的按鍵分為兩區，其中一區的按鍵稱為右手鍵，表示這些按鍵是由右手去按
2. 滑鼠動作包含移動滑鼠和按下任意滑鼠鍵
要給個縮寫的話就是
SKMR = switching between keyboard and mouse ratio
考慮寫個小程式來收集資料
Sunday, March 14, 2010
教人讀書的書
這次春節回外婆家玩
在表弟的書櫃上看到了不少教人讀書的書
我認為這類書籍的意義
就像是聖經的見證分享一般
讀書的方法從古就被人研究著
時至今日
配合心理學的理論基礎
現代的讀書理論可說已經確立
雖說將來必定會有新的發展
但是此刻來說
幾乎所有的書提到的東西都相同 只是有所取捨
換句話說
可以看作是作者本人的"讀書的成功經驗"
我認為目前這類書中的"聖經"
How to Be a Successful Student, 1998
一共只有30頁 每頁一個主題
不過
換個角度來看這些書也可以得到有趣的想法
"為什麼明明是類似的內容,卻還是有人會買呢?"
藉由觀察作者是如何安排書籍內容
使得讀者願意購買
在表弟的書櫃中
我認為有兩本書覺得可以稍微瀏覽一下
大量 & 重複 & 快速
也就是足夠的內容加上多次重複學習(對抗遺忘)加上縮短學習間隔(對抗遺忘)
扣除其餘的知識, 以一本書的程度來闡述這三個基本道理
是一個很能抓住人心的寫法
第二本書使用了方程式作為全書的摘要
數學的方程式給人很強的理論感
是相當漂亮的手法
在此我節錄一下
總合起來就可以達到16倍的成果
結論是看這些書的最大好處
就是自己成功以後也能出一本來騙錢激勵莘莘學子啊
在表弟的書櫃上看到了不少教人讀書的書
我認為這類書籍的意義
就像是聖經的見證分享一般
讀書的方法從古就被人研究著
時至今日
配合心理學的理論基礎
現代的讀書理論可說已經確立
雖說將來必定會有新的發展
但是此刻來說
幾乎所有的書提到的東西都相同 只是有所取捨
換句話說
可以看作是作者本人的"讀書的成功經驗"
我認為目前這類書中的"聖經"
How to Be a Successful Student, 1998
一共只有30頁 每頁一個主題
不過
換個角度來看這些書也可以得到有趣的想法
"為什麼明明是類似的內容,卻還是有人會買呢?"
藉由觀察作者是如何安排書籍內容
使得讀者願意購買
在表弟的書櫃中
我認為有兩本書覺得可以稍微瀏覽一下
- 超快速讀書法
- 我這樣考上東大和哈佛-百試百中的16倍速學習法
大量 & 重複 & 快速
也就是足夠的內容加上多次重複學習(對抗遺忘)加上縮短學習間隔(對抗遺忘)
扣除其餘的知識, 以一本書的程度來闡述這三個基本道理
是一個很能抓住人心的寫法
第二本書使用了方程式作為全書的摘要
數學的方程式給人很強的理論感
是相當漂亮的手法
在此我節錄一下
＜成功學習方程式＞作者在書中說明如何對四個變數各自提升一倍
學習成果＝「資質」×「策略」×「時間」×「效率」
◎「資質」＝每個人頭腦天生的能力。就像「○○同學的頭腦好清晰啊」「他腦袋不好，不管怎麼念書都沒用啦」這樣的天生能力
◎「策略」＝針對學習的目的、目標，徹底思考應該採取何種學習方式
◎「時間」＝學習的時間
◎「效率」＝學習的效率，每單位時間的學習效果
總合起來就可以達到16倍的成果
結論是看這些書的最大好處
就是自己成功以後也能出一本來
Subscribe to:
Posts (Atom)