Stay hungry. Stay foolish

題目連結

這講所介紹的資料結構 (Heap, BST, Hash Table)，用途在為了保證 container 存在某些性質 時使用。

這個系列主要會整理一些自己刷 judge 常使用到的 STL 用法，cppreference 好是好，但就是有點太詳細了XD，首篇介紹的 vetor 和 pair，絕對是我最常用到的 STL 資料結構 XD !

前面提過 Boolearn Search 的其中一個問題在於， machine 是無腦地回傳文本，其回傳的順序並沒有任何意義 (可以試想一下使用 Google 搜尋時，一次動輒 $10^6$ 數量級以上的文本量，如果無序的話，你想要檢閱查找相關文件是一件多痛苦的事，那麼這個 IR system 有跟沒有是差不多的😅)。因此，我們引進 ranked retrieval 的概念，目標是讓文本能以其跟搜尋 query 的關聯性大小來做排序。

在做 Indexing 之前，我們需要將文本從各方來源中抽取出來，這些來源的 格式 相當多元(像是 html, md 等等 markup 或是與圖片相雜的 data ，可能還需要處理 encoding 的問題)，反正就是挺亂的，需要做一些 processing 後，才可以用強大的 NLP tool 來統一處理。

前面幾講的討論中，我們都假設有一個 ground truth function $f$ 去 generate data，且我們所拿到的 $\mathcal{D}$ 是乾淨的，然而在真實世界中，無可避免地會遇到 noise 加在 data 上，如此情況下 learning 是否還是可行？ (VC bound 是否還是 work ?) 另外，前方討論時，我們都以 0/1-error 作為衡量 model 好壞的 metric，如果換成不同的 metric 呢？

這個系列主要會紀錄自己在 KTH 修習 Information Retrieval System 的一些筆記，備忘用，不會像之前的 Post 那麼詳細，但還是會加點自己的 remark 這樣。

於前一講中，我們證明了 growth function 為 POLY(N) iff break point 存在，而這件事可以說明在 training data 上的表現不會和 testing data 差的太多 $E_i(h) \approx E_o(h)$ (if 數據點夠多 $N$ )。而這一講中，我們由 break point 引進 VC Dimension $d \scriptscriptstyle VC$ ，來當作衡量 $\mathcal{H}$ 複雜度的一個指標。

前一講中講述了 break point 的存在，壓制了 growth function $m_H(N)$ 的成長速度，於這一講中，我們想嚴格地說明只要存在 break point ，$m_H(N)$ 便會是 POLY(N) 。