2017年11月7日 星期二

Why use Bounding Function

我們有了Hypothesis Set的Growth Function,為何還要定義一個Bounding Function呢?

這是因為我們想用Bounding Function對Hypothesis Set分類,就像之前我們用Dichotomy將Hypothesis歸類,Definition of Dichotomy,目的是一樣。

複習一下4種Hypothesis Set (圖片來源:Machine Learning Foundations)



我們發現,不同的Hypothesis Set,有各自的Growth Function。有的Hypothesis Set甚至尚未找到Growth Function,如2D perceptrons。如果Growth Function的樣子長的不一樣,甚至有些不知道它的樣子,我們要如何用簡單的方法,來描述Growth Function的特性?

程序員的思考方式是,花繁為簡,整理出下面表格




第1行為Perceptron的名稱。第2行為每個Perceptron的Breakpoint。第3行為每個Perceptron的成長函數。我們知道前面4個Perceptron的成長函數,最後一個2D Perceptrons的成長函數,不知道,但肯定不會超過2N

第4行,我們希望用一個簡單的方法來代替成長函數。就是用演算法所學的Big O,並且用k標示break point。

第5行,就是將第4行的描述,用Bouding Function表達。Positive Intervals和1D Perceptrons,雖然O裡的內容不一樣,但都以表達為 B(N, 3)。因為它的Bounding的原故。

如此一來,問題就簡化為,不管Perceptron長什麼樣子,只要知道它的Breakpoint在那裡,我們就可以用Bounding Function來表達它的上限。

-Count

沒有留言:

張貼留言