# Bounding Function

將 Break Point K 跟 N 連結起來的一個函數，通常記為：

$$
B(N,K)
$$

這個東西是成長函數的上限。

## 性質

$$
B(N,K)=B(N-1,K)+B(N-1,K-1)
$$

## 公式

從上面的規則可以推得：

$$
B(N,K)=\sum_{i=0}^{k-1}\binom{N}{i}
$$

而最高次的項為 $N^{k-1}$，當帶回 Hoeffding 的時候，我們可以知道只要 N 夠大，就會被 EXP 給壓下來。

---

# Vapnik-Chervonenkis (VC) bound:

經過一連串神奇的步驟，我們最終的不等式長的像：

$$
\mathbb{P}[\exists h \in \mathcal{H} \ s.t.|E_{in}(h)-E_{out}(h)|>\epsilon]\le 4m_{\mathcal{H}}(2N)e^{-\frac{1}{8}\epsilon^{2}N}
$$

大致經過這三個步驟：

- 將 $E_{out}$ 替換成 $E_{in}^{'}$
- 將 $\mathcal{H}$ 從「多少可能」降解為「有幾種」
- 使用「取後不放回的」Hoeffding

詳細過程待補......。