Practical

Concise and clear explanation of context-free grammar

CFG

Reference:

@inproceedings{yang2015robot,
title={Robot Learning Manipulation Action Plans by” Watching” Unconstrained Videos from the World Wide Web.},
author={Yang, Yezhou and Li, Yi and Ferm{\”u}ller, Cornelia and Aloimonos, Yiannis},
booktitle={AAAI},
pages={3686–3693},
year={2015}
}

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就只固定看某一個範圍內的輸入訊號,所以就被稱為”有限”脈衝濾波器。