# HW3 Reference Solution

**Question:**
使用cosine similarity 或 geometric distances做為similarity measurement是否為monotonic?

**Statement**:
無論使用何種similarity measurement *(用$f(.)$表示)*，single-link, complete-link與group-average這三種similarity function *(用$sim(.)$表示)* 均能保持monotonic。

**Prove**:
在merge的過程中，依照similarity function的規則會依序合併，$S_0$表示所有待合併nodes的集合，$S_1$表示經過1次合併後，所產生的node set，以此類推直到全部合併完畢。

> 簡單的圖示說明：
> 
>
> $S_0=\{a,b,c\}$
> $S_1=\{d,b\}, d=\{a,c\}$, => 合併$a,c$，similarity value為0.97，sim(b)=sim(a,c)=0.97
> $S_2=\{e\}, e=\{b,d\}$, => 合併$b,d$，similarity value為0.94，sim(e)=sim(b,d)=0.94

首先定義monotonicity：在merge的過程中，similarity value均會持續下降，即合併 node set中任意兩nodes，所產生的similarity value都小於前面合併時所產生的similarity values。$sim(c_1,c_2)$表示合併$c_1,c_2$時產生的similarity value，而$sim(c_3)$則表示形成$c_3$時產生的similarity value，用以下式子表示：

$sim(c_1,c_2)\le sim(c_3)$, $\forall$ $c_1,c_2,c_3\in S_k$ (式一)

假設存在nodes，使得**第k+1次**merge時的similarity高於前面所產生的similarity values(違反式一)：

$\exists \ c_1,c_2,c_3\in S_{k+1} \ \text{s.t.}\ sim(c_1,c_2)\gt sim(c_3)$ (式二)

若我們能夠證明無論第k+1次的合併發生在哪一個位置(e.g. $c_1,c_2,c_3$)，上式均不會成立，則可得假設錯誤，即不存在nodes會違反monotoncity。

令$c'$為$c_i,c_j$的合併，其中$c_i,c_j\in S_k$，k+1$^{th}$ merge step可能會發生在以下三種情況
1. $c'=c_1$：$sim(c_1,c_2)=sim(\{c_i,c_j\},c_2)$ (式三)
因為$c_i,c_j,c_2,c_3\in S_k$，故
$$
\left\{
\begin{array}{**lr**}
sim(c_i,c_2)\le sim(c_3) & \\
sim(c_j,c_2)\le sim(c_3)
\end{array}
\right.
$$
(1)$sim(.)$為single-link：(式三)$=max[f(c_i,c_2),f(c_j,c_2)]$,
若$f(c_i,c_2)\ge f(c_j,c_2)$, $sim(c_1,c_2)=sim(c_i,c_2)\le sim(c_3)$，與式二矛盾；
若$f(c_j,c_2)\ge f(c_i,c_2)$, $sim(c_1,c_2)=sim(c_j,c_2)\le sim(c_3)$，與式二矛盾。
(2)$sim(.)$為complete-link：(式三)$=min[f(c_i,c_2),f(c_j,c_2)]$,
若$f(c_i,c_2)\ge f(c_j,c_2)$, $sim(c_1,c_2)=sim(c_j,c_2)\le sim(c_3)$，與式二矛盾；
若$f(c_j,c_2)\ge f(c_i,c_2)$, $sim(c_1,c_2)=sim(c_i,c_2)\le sim(c_3)$，與式二矛盾。
(3)$sim(.)$為group-average：(式三)$=avg[f(c_i,c_2),f(c_j,c_2)]\le sim(c_3)$，與式二矛盾。
且無論$f(.)$為何，矛盾均存在。

2. $c'=c_2$：交換$c_1,c_2$，與case 1同理。

3. $c'=c_3$：$sim(c_1,c_2)\le sim(c_3)=sim(c_i,c_j)$ $\forall c_1,c_2,c_i,c_j\in S_k$
但若$sim(c_1,c_2)$比$sim(c_i,c_j)$小，則第k次的合併應合併$c_i,c_j$而非$c_1,c_2$，與merge rule矛盾。

因為以上三種情況均存在矛盾，故假設不成立，且無論similarity measurement為何，均不影響single-link, complete-link與group-average的monotonicity。