Stay hungry. Stay foolish

上一講提到了在 hypothesis set $\mathcal{H}$ 為有限，且sample size $|\mathcal{D}|$ 足夠大的情況下，是 PAC-learnable 的。但當 $|\mathcal{H}| , \rightarrow , \infty$的時候呢？ (e.g 2D linear perceptron)

這一講要討論的是機器學習真的是可行的嗎？能推廣到所有 scenerio 嗎？或是只有部份？是否需要某些假設才能證明可行呢？

這講建構了一個大略的 ML 世界觀。

於前一講講述了 ML 的 framework ，於這一講中，我們會利用一個簡單的 learning model ， 去解決 binary classification 的問題。

其實是大一升大二的暑假，閒來無事找的開放式課程，那時也做了一些筆記，沒想到兩三年過後，自己做專題也走向了這個領域XD，於是順手把它整理上來囉！

題目連結

題目連結

在 第一講中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 $\mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)})$ ，而這一講想討論的是，如果今天我們手上有兩個 hash function (from same $\mathcal{H}$)可以選，每次我們就看哪一個 $h$ 回傳的 slot 中元素比較少，就將 element hash 到 slot，那麼現在 $\mathbb{E}[, \text{max num of elements in any slots} , ]$ ?

Hashing 的一個 criteria 是希望儘可能不要發生 collision (也就是 Worst Case 也在 $\mathcal{O}(1)$ lookup)，今天假設我們已知元素的個數，該如何設計一個 hash function 使得不會有任何 collition 發生？

前面提到過一個較為複雜的優化問題， Metric Facility Location Problem ，並給出了一個 4-Approx. Algorithm ，於這講中，我們要來利用前面提到的 Primal-Dual method 來設計演算法。