# 5.7 Discrete Features

## binary features

在一些應用裡，我們的 attributes（即 features）為 discrete，為 $n$ 種不同的值中的其中一種。

舉例來說，某種 attribute 可能會是：

- $\text{color} \in \{\text{red, blue, green, black}\}$
- $\text{pixel} \in \{\text{on, off}\}$

我們來假設一個 attribute $x_j$ 是 binary（Bernoulli）的情形：
> 關於 binary（Bernoulli）distribution 的簡單介紹，可參考筆記「[A.3.1 Bernoulli Distribution](https://hackmd.io/@pipibear/rkGGbs9VA)」。

並且，我們令 $x_j=1$ 的 probability density conditioned on $C_i$ 以 $p_{ij}$ 表示，如下：


如果我們再進一步假設 $x_j$：independent，我們會發現根據定義，其實這樣等同在說我們的 model 是 naive Bayes model：
> 關於 naive Bayes model，可參考筆記「[5.5 Multivariate Classification](https://hackmd.io/@pipibear/ByBQVbqKR)」中，「estimate discriminant function 裡的 parameters」$\Rightarrow$ 「shared, axis-aligned: Naive Bayes Model」小節的內容。


並且，把 conditional density $p(\vec{x}|C_i)$ 的式子代入 discriminant function，就會得到下圖的結果：


我們發現為了要去利用 $g_i(\vec{x})$ 來判斷 $\vec{x}$ 是否屬於 class $i$，我們需要去估計這個式子裡 $p_{ij}$ 的值。

因此，又回到前面 estimate paramters 的方式，我們的 estimator for $p_{ij}$ 以 ==$\hat{p}_{ij}$== 表示，計算方式如下：


## document categorization

上述這樣的做法到底可以運用在哪裡呢？
什麼樣的情境下我們的 input features 之間彼此獨立，且每個 feature 的值只會是零或一？

其中一種答案是 <font color = "snake">document categorization</font>，也就是我們想要把新聞報導分到好幾種分類裡，比如說政治、體育、流行⋯⋯。

### Bag of Words (BoW)

在自然語言處理裡面，有一種 model 叫做 <font color = "snake">bag of words (BoW)</font>，這種方法可以用很簡單的方式將一段文字轉換成用向量表示。做法是：

首先我們挑出一個包含 $d$ 個 words 的集合，我們相信這 $d$ 個 words 能夠提供我們關於 class 的資訊。

舉例來說，在分類新聞的時候像是「導彈」、「運動員」、「時裝」⋯⋯，這樣的字就很適合，但一些模糊的字像是 "runway"（我們沒辦法分辨是在說時裝秀在走的那條路，還是飛機的跑道）就不適合。

這樣一來，我們就能夠把我們的每一份文件轉換成一個 $d$-dimensional 的 binary vector，其中如果一開始選好的第 $j$ 個 word 有出現在這份文件裡，那這個 binary vector 中的 attribute $x_j=1$。
> 其實課本這種方法只是 BoW 的一種形式
>
> $\rightarrow$ 也有做法是將整個 dataset 裡有出現過的 unique words ，每個作為向量中的一個 dimension。不過這種做法會產生的問題是：當每個 text document 被轉換成向量時，大部分的 text 都變成了 sparse vector（很多 dimensions 為零），這樣就會導致 ++overfit++。
>
> $\rightarrow$ 課本在這裡用的是 binary 版的 BoW，但更常見的做法是將 $x_j$ 代表 $j$th word 出現在一份文件裡的++次數++（而非只分有出現／沒出現，雖然這種作法在某些情境下也有它的用途。）

按照課本的定義，看個例子就很清楚了：

> 不過從這個例子也看不出來是否為 binary 的，畢竟每個 word 在每一行 text 中確實只出現一次，不過 binary BoW 本來就比較少用，圖比較難找，就免強用這個 XD

如果不是 binary 的版本，而是讓 $x_j$ 代表在一份文件裡的出現次數，就會變成像下圖這樣：


- Note：不管是上面哪一種方式，BoW 都會++失去 ordering++ 的資訊，因為在轉為透過向量表示以後，每個 dimension 只會表示對應的 word 是否存在我們的文章中（或出現幾次），並不會記錄出現的順序和位置，這也是為什麼我們稱作 "bag" of words。

如同我們前面講到的，為了去形成我們的 model，對未知的 parameter $p_{ij}$，我們有一個 $p_{ij}$ 的 estimator $\hat{p}_{ij}$；放到現在的例子裡，我們想要藉由 training 來得到的 $\hat{p}_{ij}$，代表的意義就是去++估計 word $j$ 出現在 document $i$ 中的機率++。

$\rightarrow$ 如果有一個 word，它出現在不同的 classes 中的機率都差不多，這樣的話這個 word 就沒辦法帶給我們什麼有用的訊息；我們想找的 word 是它出現在某個（或某些） class 中的機率遠高於出現在其他 classes 中的機率。為了挑選出這樣的 words，我們就會去做 <font color = "snake">feature selection</font>，這部分會在之後的第六章說明。
> 前面我們說另一種 BoW 的方式會將整個 dataset 中的 unique words 都視為一個 dimension，使得每個 text 都是 sparse vector，這種情況下我們也可以利用 feature selection 來降低過多的維度。

>[!Note] 關於 BoW 有一點點補充，我會放在這篇筆記的最後面。

### spam filtering

另外一個 document categorization 的應用叫作 <font color = "snake">spam filtering</font>，也就是字面上的意思，我們將 email 歸類到兩個 classes，分別是 spam 和 legitimate。

課本就講到這 XD 但大概的流程如下圖：


從左邊開始看：

1. 首先我們對 email 先做 preprocessing，通常是去掉空格、標點符號、"and, the..." 等等無用的資訊，然後把整份文字拆成一個個 word。
2. 接著在 feature extraction 的步驟，我們會用像是剛剛說到的 BoW，把 text 轉換成每一個 word 出現與否或出現次數的 vector；或者其他方式像是 Word2vec，可以將 words map 到一個 continuous vector space，使得意思相近的 words 有比較近的距離。除了這兩種以外還有許多方法，但總體來說，這個階段就是將 email 轉換成向量（變成 vector expression）。因為以數值表示以後，我們才能進一步去做 training / testing。
3. 被拿來做 training set 的部分 email，會先被 label 是否為 spam，然後拿來訓練並形成我們的 model。隨著 data 的數量越多，model 就能越被 improve，藉由找出 feature 的 patterns 來區分是否為 spam，使得最後 classifier 能夠透過這個 model 來讓我們能夠在未來去預測新的、沒看過的 email。

## general case: multinomial features

前面我們假設每個 feature $x_j$ 為 binary 的，但是拓展到 general case，我們令 $x_j$ 為 multinomial，也就是說：

\begin{equation}
x_j \in \{v_1,v_2,...,v_{n_j}\}
\end{equation}

> 為什麼我們說 binary 的 general case 會是 multinomial？
>
> Recall：
> - binary distribution 代表的意義是當我們的 outcome 只有兩種時，執行一次 experiment，outcome 分佈的情形。
> - binomial distribution 代表的意義是如果一樣，我們的 outcome 只有兩種，但是 experiment 執行 $N$ 次，產生的 $N$ 個 outcomes 的分佈情形。
> - multinomial distribution 代表的意義是再去拓展我們的可能性，變成 outcome 可以有 $K$ 種的情況下，experiment 執行 $N$ 次，outcomes 分佈的情形。
>
> $\rightarrow$ 因此如果我們令可能的 outcome 數為 $K$，experiment 執行的次數為 $N$，那麼 binary 就是當 $K=2, N=1$、binomial 是當 $K=2, N>1$、multinomial 是當 $K>2, N>1$。

因為現在 $x_j$ 的值有多種（共 $n_j$ 種）可能，所以我們另外令一個 dummy variable 來表示 $x_j$ 到底是這 $n_j$ 個裡的哪一個：


前面我們有 $p_{ij}$ 來表示屬於 class $i$ 的情況下，feature $j$ 為一的機率；而現在我們也想要再令一個 parameter 來表示屬於 class $i$ 的情況下，feature $j$ 為 $v_k$ 的機率：


訂完 $p_{ijk}$，我們就能用它來表示 $p(\vec{x}|C_i)$，來讓我們在下一步能夠去表示 discriminant function。我們一樣假設這些 attributes 為 independent：


其實 discriminant function 也和上面的作法一樣，把剛剛求完的 $p(\vec{x}|C_i)$ 代入，然後因為我們取了 $\log$ 來簡化計算，所以指數可以搬下來，乘法全部轉換成加法，只是符號太多看起來比較雜亂而已：


最後一樣，我們要來求 $p_{ijk}$ 的 MLE（maximum likelihood estimator）==$\hat{p}_{ijk}$==：


有了 $\hat{p}_{ijk}$ 以後，我們就能代入 discriminant function $g_i(\vec{x})$ 來預測新的 input 了！

## 補充：BoW

>[!Note] 這部分的內容完全出自一篇文章，連結則放在最後的參考資料！

BoW 是一種用來 model text data 的 feature extraction 技術，更精準的來說，它是一種對一個 text document 裡面所有已知的 words 的 unstructured 分類，而這個分類不考慮單字出現的順序或脈絡，單純只由它們出現的頻率定義。

在 BoW approach 裡，每個 individual word 變成向量空間裡的一個獨立的 dimension（或是 axis），因此如果我們的 text 有 $n$ 個 words，那會 map 到的向量空間就是 $n$ 維的，每一個維度都是 text set 中的一個 unique word。

接著，我們的 model 將每個 text document 標為這個 $n$ 維向量空間中的一個點。這個點沿著某個軸的位置，代表這份 text document 中，這個軸對應的 word 出現幾次。

舉例來說，假設我們的 text set 裡面有兩個 documents：


因為三維以上的空間比較難用圖像來想像，所以我們就取一個 set 為：

\begin{equation}
\{\text{red, rose, violet}\}
\end{equation}

這三個 words 分別為我們的三維向量空間中的一個軸：


在 document $1$ 中，red, rose, violet 分別出現一次，所以它的座標為這個三維空間中的點 $\{\text{red, rose, violet}\} = \{1,1,1\}$。

在 document $2$ 中，red 出現兩次、rose 出現一次、violet 沒出現，所以它的座標為 $\{\text{red, rose, violet}\} = \{2,1,0\}$。


### limitations of BoW

關於 BoW 的 limitations，除了上面我們有稍微提到的當轉換出來的 vector 是 sparse 時，會造成 overfitting 的問題，另一個和我們之前學過的概念相關的是 BoW 並沒有將 ++words 之間的 correlation++ 考慮進去。

我們可以回想前面不管是 binary 或是更 general 的 multinomial 的情況，我們在推導 $p(\vec{x}|C_i)$ 時，之所以可以直接把 $p_{ij} / p_{ijk}$ 之間直接相乘，都是因為我們假設 features $x_j$：independent。在 BoW 的情境裡，每個 feature 是一個 word，所以假設 features independent，就等同於在說一個 text document 裡，一個字的出現並不會影響另個字出現的機率。

但是我們知道，BoW 這種假設一個 document 裡面 word 和 word 之間彼此互相獨立的 model，其實和我們的現實狀況不相符。比如說，假設我們在一篇新聞報導裡面看到「選舉」，我們會預期在同一篇新聞裡，出現「總統」的機率應該要比出現「詩人」來得高。

既然 BoW 並不會去考慮文字使用上 word 和 word 之間的 correlations，只是將每個 word 只被視為一個獨立的 feature，而這個 word 出現的次數作為它的 weight，那麼這就會導致的是我們之前有稍微提過的 ++multicollinearity++ 的問題。

什麼意思呢？

舉例來說，假設一樣是要去為新聞報導分類的情境，我們知道「選舉」、「總統」、「選民」這些 words 有著很高的 correlation，有其中一個字出現的情況下，另外兩個字出現的機率也會很高。

在這樣的情況下，如果我們還是讓我們的 features 同時包含這三個 words，也就是它們在我們的向量空間裡佔了三個 dimension，可以想像當和政治有關的報導被轉換成向量時，它在這個向量空間中的座標就會同時傾向這三個維度的方向。

這會導致的問題是一來我們的 model 在做出 prediction 時，如果一則報導被歸類到政治，我們很難去說到底是因為「選舉」這個字的出現，還是因為有「總統」出現在文章裡；二來是既然這些 features 帶來的是類似的資訊，產生出來的 model 就會變的不必要的複雜。

最後就是像我們前面幾節在講 regression 時所提到的，multicollinearity 會使我們的 model ++unstable++，只要 data 有一點改變，就會造成 model 的係數大幅變動，進而使得我們的 estimates unreliable。

---

除了上述這些 limitations，下面參考資料的文章也有提到一些其他的問題，也有針對這些 limitations 可以去做的 modification 介紹，還有很多其他的相關內容，文章寫得很簡單，推薦去看看！就能對 BoW 有基本的認識！

因為課本也沒多講，那麼我就結束在這裡。

# 參考資料

- [IBM: What is bag of words?](https://www.ibm.com/topics/bag-of-words)