# 3.4 Discriminant Functions

前面我們講到 classification，對於分類這件事，我們也可以把它想成去 implement 一個 <font color = "snake">discriminat functions</font> 的 set，在這個 set 之中有 $k$ 個 functions：

\begin{equation}
g_i(x) \qquad i=1,...,k
\end{equation}

也就是我們對每個 class（共 $k$ 個），都給一個對應的 function 去計算出某個值來，然後挑算出來最大的值，來讓我們把一個 input 分類到對應的 class。

寫成數學式如下：


所以如果要用這樣的方式來表示一個 Bayes' classifier，那我們可以把 discriminant function $i$ 定義成分類到 class $i$ 的 expected risk 乘上 $-1$：
> 這也就會使得當選某個 class 的 expected risk 越高，我們的 discriminant function map 到的值就越小，就越不會去選擇去分類到這個 class。
>
> $\max$ discriminant function $\leftrightarrow$ $\min$ conditional risk


接著，如果我們假設用的是 $0/1$ loss function，那麼我們的 $R(\alpha_i|x)$ 也等同於 $1-P(C_i|x)$
> 忘記可參考前一節： 3.3 Losses and Risks

帶入之後：

\begin{equation}
g_i(x) = -(1-P(C_i|x)) = P(C_i|x) -1
\end{equation}

因為我們是要對這 $k$ 個 discriminant functions 去做比較，所以當大家都有 $-1$ 時，可直接捨棄，於是我們會得到：

\begin{equation}
g_i(x) = P(C_i|x)
\end{equation}

根據 Bayes' rule：

\begin{equation}
P(C|x) = \frac{P(C)P(x|C)}{P(x)}
\end{equation}

其中，$P(x)$ 其實是拿來 normalize，使我們的 probability 總和為 $1$ 的，所以如果我們不要 normalize，則原式可改寫為：

\begin{equation}
g_i(x) = P(C_i)P(x|C_i)
\end{equation}

## feature space

接著，下面會用到 feature space 這個名詞，但課本實際上沒有明確定義，我查了一些資料，來源放在下方參考資料處。

先解釋一下 feature space：

在過去我們在講分類車子的例子，或是其他例子時，我們都會把我們的 instance 的 features 寫成一個向量表示：

\begin{equation}
x = [x_1,x_2,...,x_n]^T
\end{equation}

舉例來說，分類車子時考量的因素如果是「價格」、「引擎動力」，那我們的 $x$ 可能就是一個二維的向量 $x=[x_1,x_2]^T$，其中 $x_1$ 代表價格， $x_2$ 代表引擎動力。

也就是說：
:::warning
每個 feature 可以被看作我們在處理的問題的一個 dimension。
$\rightarrow$ 每個 instance 也就可以被視為這個 $n$-dimensional feature space 裡的一個點。
:::

> 我們的 input 每個都是 input space 裡的一個點，透過這些 input 的 features 作為 parameters，我們利用一個 mapping function $\Phi$ 把它們送到 feature space 中。
>
> 如果每個 input 有 $n$ 個 features，那我們的 feature space 就是 $n$ 維，劃分這個 feature space 讓我們能夠進行分類的 hyperplane 則是 $n-1$ 維。
> - 參考資料的 ppt 裡有其他例子和更詳盡的說明。

有了這樣的概念之後，我們就能知道：

:::warning
每次我們用 feature vector 來描述我們的 learning problem 時，我們都創造了一個一個 feature space。

$\rightarrow$ 那些 learning algorithms 也就是在用某種方式去操縱這個 feature space，進而去 label 新的 instances。
:::

### decision tree & feature space

在我們分類時，我們其實是在想辦法透過各個 feature 來做出不同的 decision，例如價格在多少以下的車就分到某一類，以上就分到另一類。那麼，整個分類問題其實也就對應到了一個 decision tree。

decision tree 和 feature space 有什麼關聯呢？

回顧一下，我們剛剛說：

++每個 feature 都是 feature space 裡的一個 dimension。++

:::warning
$\rightarrow$ decision tree 就是每次根據一個 feature， recursively 在 split 這些 feature space 裡的 points。
:::

也就是說，decision tree 是每次在 feature space 裡的某個 dimension 裡畫 dividing line，然後再沿著其他 dimension 再去 recursively subdivide。

每條 dividing line 會跟該 dimension 的 axis 平行，因此我們說：

:::warning
decision trees 產生 ++axis-parallel splits++
:::

---

回到原本的內容，在我們把 discriminant function 訂成 $g_i(x) = P(C_i)P(x|C_i)$ 的同時，我們也就是透過這些 functions 把 feature space 分割成 $k$ 個 <font color = "snake">decision regions</font> ==$R_1,...,R_k$==，其中：

\begin{equation}
R_i = \{x| g_i(x) = \max_k g_k(x)\}
\end{equation}
> 意思也就是我們的 $i$ th region 會包含的是某些特定的 instance $x$，這些 $x$ 滿足當它代入各個 discriminant function，代到 $i$ th discriminant function $g_i()$ 會產生最大值。
>
> $\rightarrow$ 代表分到 $i$ th region expected risk 最小， probability 最大。

那麼對這 $k$ 個 regions 來說，它們彼此之間由 <font color = "snake">decision boundaries</font> 區隔開來，也就是下圖例子中的 $C_1, C_2, C_3$ 的三個邊界：

> 中間寫著 reject 的部分代表發生不同的 discriminant function map 到的值平手，因此我們無法挑出值最大的那個。

## 特例：兩個 classes 的 discriminant function

當我們只有兩個 classes 時，我們可以定義一個 discriminant function 就好：

\begin{equation}
g(x) = g_1(x) - g_2(x)
\end{equation}

然後選擇

\begin{cases}
\ C_1 \qquad \text{if} \ g(x)>0 \\
\ C_2 \qquad \text{otherwise}
\end{cases}
> 因為當一個 input $x$ 被分類到 $C_1$ 的 probability 較大時，我們把 $x$ 帶入我們的兩個 discriminant function，根據我們對 discriminant function 的定義， $g_1(x)$ 的值就會大於 $g_2(x)$，因此相減得到的 $g(x)$ 值為正。

例如當我們遇到一個 two-class learning problem 的時候，我們就能把：

- positive example 作為 $C_1$
- negative example 作為 $C_2$

## 名詞：dichotomizer, polychotomizer

當我們的 $k$，也就是 class 總數／region 總數／discriminant function 總數為特定的值時，我們對這樣的 classification system 有不同的稱呼：

$k=2 \rightarrow$ <font color = "snake">dichotomizer</font>
> dichotomizer 也就是一個 model / algorithm，用來將 data 區分成兩個 class（例如說區分 spam / not spam 的 dichotomizer）
>
> dichotomizer 會先產生 decision boundary 來將 data 分成兩個 regions（分別對應兩個 classes），其中， decision boundary 可能是 linear 也可能是 nonlinear，之後，當我們給新的 input 時， dichotomizer 就能 predict 它屬於哪個 class。

$k\ge 3 \rightarrow$ <font color = "snake">polychotomizer</font>
> poluchotomizer 也和 dichotomizer 的運作方式類似。

# 參考資料

關於 feature spaces：
- [wisc cs lecture ppt](https://pages.cs.wisc.edu/~bsettles/cs540/lectures/16_feature_spaces.pdf)
> 推薦一看，寫得很清楚。