Practical

Great resources of learning MDP, POMDP

MDP

  1. UC Berkeley’s lecture on MDP
  2. My article introducing MDP (in Chinese)

POMDP

  1. Prof. Nikolaidis’s post about POMDP
  2. GaTech’s course about Reinforcement Learning – Lesson 9 POMDP
Advertisements
Practical

Paper reading – The naïve utility calculus: Joint inferences about the costs and rewards of actions

前言

今天讀的論文是 The naïve utility calculus: Joint inferences about the costs and rewards of actions,key insight 是把人類其實有能力去推算別人為了達成目標,所得到的 reward、跟所需耗費的 cost 大致是什麼。

以前的 work 大致都著重在人類的行為是為了完成目標,得到不同 reward,卻忽略了不同人做同一件事其實 cost 不同。

重要的人類行為

條列一些之前的發現:

  1. 人類的行為是為了某個 goal
  2. 人類會盡量採取(自認為)有效率的方式去達成目標

在這前提之下,我們就可以大致推得在 goal 是 G 的時候,採取行為 A 的機率有多高。越能有效率達到 G 的 A,被採取機率就越高。

我們用L(A|G)來表示這個可能性(likelihood)。

擷取.JPG

在這種 formulation 之下,我們可以將人類的決策行為當成一個 Markov decision process ,所以就可以:

  1. Forward: 推算出人類在某個 state 會採取什麼行為
  2. Backward: 從人類行為推算出他的 goal

擷取擷取2

這篇論文的 key insight 

上面提到的方法看起來很有趣,用基本的條件機率和貝氏定理就可以描述如何 infer 人的 action或 inverse infer 人的 goal,但如果你仔細用心就會發現,每一個 action 的成本其實不一樣,我們怎麼能只用夠不夠有效率來推論人會不會這樣做呢?(甚至可能有資訊不足的問題,例如完成 goal G 有 100 種方法,但我只聽過 5 種)

所以這篇 paper 才提出應該要用同時考慮 action 的 cost。

擷取擷取2

如何用數學和程式實作出這篇論文的概念?

這邊我也還不是很懂,看來應該是需要先讀懂他們 2009 年的那篇論文:

Baker, Chris L., Rebecca Saxe, and Joshua B. Tenenbaum. “Action understanding as inverse planning.” Cognition 113.3 (2009): 329-349.

等我懂了再寫出來分享。

擷取.JPG

Practical

超讚的學科大地圖

今天 Youtube 突然推薦我一個看起來超讚的影片 – The Map of Mathematics:

裡面把各種數學的定位都給出來了,要是以前學數學就有這個大地圖該有多好,就可以在學習微積分、線性代數、微分方程、機率與統計、複變等這些科目時就有完整的概念,也更有機會把學習過的東西都串起來並真正應用在實際的問題上。

順便附上 Computer Science 的大地圖:

祝看到的各位都能運用數學來解決實際上遇到的問題,不斷體會到數學的美好!

Practical

數位濾波器的學習筆記

因為濾波器的應用實在太廣了,趁著有空之餘,來學習一些基礎知識,順便將自己的筆記分享出來。

首先談一下濾波器的基本觀念。如果大家仔細觀察,就會發現,在我們的世界裡,訊號是無所不在的,你現在看到的這段文章就是透過光的訊號傳遞、你說的話是聲音訊號、你上網是透過網路訊號、甚至你腦中所想的一切都是電訊號,這些訊號是濾波器想要處理的對象,所以你可以想像濾波器是一個黑盒子,吃進訊號、輸出訊號。由此可知,這個黑盒子的潛力超大,因為有各式各樣的訊號需要處理。而濾波器這個黑盒子一定有做一些事情,讓輸出的訊號比輸入的訊號”好”,不然就不需要這個濾波器了,所以接下來要談談到底會怎麼個變好法。

數位濾波器分成兩種類型 – IIR (Infinite Impulse Response) 跟 FIR (Finite Impulse Response)。

首先來看一下相對簡單的FIR,推薦一個youtube上的影片,裡面有一張圖片滿清晰地說明了FIR的基本觀念:

fir

左上方的訊號就是原始的訊號,右邊是我們希望可以取出的訊號,如果說左邊訊號中所顯示的一些凹陷是由雜訊造成的,那右邊的訊號相對起來就是比較好的,因為不受雜訊干擾。從理論上比較簡單的想法是先做傅立葉轉換得到頻率域的成分,接著套一個low-pass filter就可以把主要的sine成分取出來,最後再做反轉換得到右邊的訊號。而FIR在做的事就可以達到跟以上過程一樣的效果。

FIR的作法在上圖的左下角呈現,在這個例子中,一次處理訊號中的4個點,每個都乘上一個係數f,最後再加總起來,得到一個新的訊號點輸出。所以可以想像成我吃進4個原始訊號的點,只對應到右邊輸出訊號的一個點而已。

假設這 4 個點的係數都是 0.25,那直觀上就可以理解成是一個取平均的 filter,當然就是一個 low-pass filter 啦。

看到這邊,你應該就可以發現 FIR 設計的兩個重點:

  1. 我要使用幾個輸入訊號點來產生一個輸出訊號點?
  2. 我的係數 f 要怎麼設計?

這個部分就看你的應用中想要用濾波器來做什麼事情,可以自行調整這兩個變數來測試濾出來的訊號是否符合你的要求。

以上是layman’s term的講法,幫助理解最簡單的概念,如果你想繼續深入,可以來看看理論的說明(來自陽明大學盧家鋒老師的教學影片,講得很清楚)。

接下來看一下IIR,推薦這部影片,裡面畫了一張圖清晰地把IIR的概念呈現出來:

cmpr.jpg

看了上圖應該可以比較 清楚的比較出,FIR用來產出輸出訊號的”原料”只有輸入訊號;而IIR用來產生輸出訊號的原料除了輸入訊號之外、還包含了更早之前的輸出訊號。

最後附上幾張用比較數學的方式來呈現FIR跟IIR概念的圖結束這回合: (來自盧家鋒老師的投影片)

io

上面這張表示我們只需要設計a和b這兩組係數,就可以設計出一個濾波器,而這個濾波器在時間域對訊號的作用方式由第二個式子表示。

firr

FIR就只用到b這組係數,由時間域的式子可以看出,產生一個訊號的輸出點,只會用到K個輸入訊號點,所以這也是為什麼被稱作”有限”的原因。

iir

IIR會用到a的係數,所以輸出的訊號點y(n)還會包含到前面的輸出訊號點y(n-l),會持續用到整段訊號,這種不斷使用到前面訊號的特性,有一種不斷輪迴的感覺,所以被稱作”無限”脈衝濾波器。相對來說,FIR就只固定看某一個範圍內的輸入訊號,所以就被稱為”有限”脈衝濾波器。

Practical, Robotics

邊緣偵測

UCB有一個網站比較了目前最state-of-the-art的演算法,好的邊緣偵測對於物體辨識很有幫助。

https://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/bench/html/algorithms.html

先記下來好用的學習資源:

投影片:

http://www.cs.cmu.edu/~efros/courses/LBMV09/presentations/GlobalPb.pdf

詳細實作:

http://www.multimedia-computing.de/mediawiki/images/d/dc/MA2012_ChristianEggert.pdf

https://github.com/vrabaud/gPb