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