# Homework3
###### tags: `homework/lab`

::: danger
4/17 課堂作業3
Deadline: 4/24 8:55 am
Extended to: 4/30(Thur) 8:55 am
:::

### Homework2 的 Feedback:
* 請同學們之後作業要記得**敘述**，如果回答問題錯誤又沒有敘述就會扣掉全部分數，但如果有敘述部分正確那就算錯了，也會給部分分數。

### Discussion Forum
以下開放提問

> Homework 4 的作業內容是什麼?
>> 還沒有HW4, 目前是HW3。作業內容見E3 Homework3 附檔。[name=Joy][color=#cc4d5c]

> reading clustering 的部份是指讀課本 14 章 clustering 全部嗎？看起來課文好像沒有講太多如何用分群 improve NLP job，而是花比較多篇幅介紹分群演算法，還是如何 improve 本來就是我們要自己想的？
>> 讀課本14.1.13，不是整個14章。[name=Joy][color=#cc4d5c]

> 想請問一下第一部分中 How about geometric distance? 的具體問題是想問什麼？ 課堂上沒聽清楚~
>> Is geometric distance monotonic?
[name=Joy][color=#cc4d5c]

> 想詢問有關第一部份的問題，參考及課本上的14.4式及Table 14.2的notation，好像沒有給予$\left| c_j \right|$明確的定義。
> $\begin{split}
> S\left(c_j\right)=\frac{1}{\left|c_j\right|\left(\left|c_j\right|-1\right)}\sum_{\vec{x} \in c_j}\sum_{\vec{x} \neq \vec{y} \in c_j}sim\left(\vec{x}, \vec{y}\right)
> \end{split}$
> 我一開始是想說$c_j$是一個集合，所以直覺認為$\left| c_j \right|$應該是指集合裡的個數。
> 但參考課本14.5式，卻是表達成$c_j$集合中所有的向量長度和。（第三及第四列的最後一項）
> $\begin{split}
> &\vec{s}\left(c_j\right) \cdot \vec{s}\left(c_j\right) = \sum_{\vec{x} \in c_j} \vec{x} \cdot \vec{s}\left(c_j\right) \\
> &= \sum_{\vec{x} \in c_j} \sum_{\vec{y} \in c_j}\vec{x} \cdot \vec{y} \\
> &= \left| c_j \right| \left(\left| c_j \right| - 1\right)S\left(c_j\right) + \sum_{\vec{x} \in c_j} \vec{x} \cdot \vec{x} \\
> &= \left| c_j \right| \left(\left| c_j \right| - 1\right)S\left(c_j\right) + \left| c_j \right|
> \end{split}$
> ~~我有試著用「集合裡的個數」及「集合中所有的向量長度和」來代表$\left| c_j \right|$去證明monotonic，都可以證出結果。~~(0423更新我發現我有地方證錯XD)
> 但還是想問$\left| c_j \right|$是否有明確的定義？
> 或者其實集合中的向量都有先normalize過？（那這樣「集合裡的個數」及「集合中所有的向量長度和」就會等價）
[name=0860911]
>> 參考 https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.linkage.html
>> 會是集合裡的個數 [name=Joy][color=#cc4d5c]
>>> 如果$\left|c_j\right|$是個數的話
>>> 那根據NCTU.nlp.lecture4-a(4.17).pdf第19頁及第21頁的式子
>>> $\begin{split}\vec{s}\left(c_j\right) = \sum_{\vec{x} \in c_j}\vec{x}\end{split}$
>>> $\begin{split}S\left(c_j\right)=\frac{\vec{s}\left(c_j\right) \cdot \vec{s}\left(c_j\right) - \left| c_j \right|}{\left| c_j \right|\left(\left| c_j \right| - 1\right)}\end{split}$
>>> 如果今天$c_j$中有兩個向量分別為$[1, 2]^\mathrm{T}, [3, 4]^\mathrm{T}$則
>>> $\begin{split}\vec{s}\left(c_j\right) = [1, 2]^\mathrm{T} + [3, 4]^\mathrm{T} = [4, 6]^\mathrm{T}\end{split}$
>>> $\begin{split}S\left(c_j\right) = \frac{[4, 6][4, 6]^\mathrm{T} - 2}{2\left(2 - 1\right)}=\frac{52-2}{2}=25\end{split}$
>>> 這樣算出來$c_j$的群內average similarity會超過1，應該是不合理的。
>>> 那現在重新假設$c_j$中有所有向量都有先經過normalize則
>>> $\begin{split}\vec{s}\left(c_j\right) = \sum_{\vec{x} \in c_j}\vec{x}\end{split}$
>>> $\begin{split}S\left(c_j\right)=\frac{\vec{s}\left(c_j\right) \cdot \vec{s}\left(c_j\right) - \left| c_j \right|}{\left| c_j \right|\left(\left| c_j \right| - 1\right)}\end{split}$
>>> $\begin{split}=\frac{\sum_{\vec{x} \in c_j} \left|\vec{x} \right|^2 + \sum_{\vec{x} \in c_j}\sum_{\vec{x} \neq \vec{y} \in c_j}2\vec{x} \cdot \vec{y} - \left| c_j \right|}{\left| c_j \right|\left(\left| c_j \right| - 1\right)}\end{split}$
>>> $\begin{split}=\frac{\left| c_j \right| + \sum_{\vec{x} \in c_j}\sum_{\vec{x} \neq \vec{y} \in c_j}2\vec{x} \cdot \vec{y} - \left| c_j \right|}{\left| c_j \right|\left(\left| c_j \right| - 1\right)}\end{split}$
>>> $\begin{split}=\frac{\sum_{\vec{x} \in c_j}\sum_{\vec{x} \neq \vec{y} \in c_j}2\vec{x} \cdot \vec{y}}{\left| c_j \right|\left(\left| c_j \right| - 1\right)}\end{split}$
>>> 若$c_j$所有的向量兩兩不重複內積的話共會有$\frac{\left| c_j \right|\left(\left| c_j \right| - 1\right)}{2}$，因此所有向量若都互相垂直的話，則會導致$S\left(c_j\right)=0$，而若所有向量都彼此平行的話$S\left(c_j\right)=1$
>>> 所以若$\left|c_j\right|$是個數的話，則應該隱含了說群內的向量都應該先經過normalize？ [name=0860911]
>>>> 根據課本14.1.2敘述，的確有假設向量已normalized
>>>> 
>>>> [name=某個路人][color=#F2B836]

> 根據課本上的解釋，monotonic不是針對similarity measure而是針對similarity function，題目問的是similarity measure好像和課本有些出入
>> 老師的回覆：因為你要說明monotone，所以會將推導公式拆開成真正的similarity計算方式，至於兩種similarity計算方式帶入後會不會影響有沒有關係，在推導中就應該會說明出來。
>> 助教的回覆：分別討論、證明在3種不同similarity function中，用cosine similarity 和 geometirc distance measurement 是否monotinc.
>> 如果對clustering還是不太清楚，可以參考：https://www.youtube.com/watch?v=XJ3194AmH40&t=437s
>> [name=Joy][color=#cc4d5c]

> Geometric distance 直接 google 好像沒有這個 term，是指 Euclidean distance 嗎?
>> 是, or L2 norm[name=Joy][color=#cc4d5c]

> 想問monotonicity的明確的數學定義？
> 根據課本14.2式monotonicity的定義
> $\begin{split} \forall c, c^{'}, c^{''} \subseteq S: \mathrm{min}\left(\mathrm{sim}\left(c, c^{'}\right), \mathrm{sim}\left(c, c^{''}\right)\right) \geq \mathrm{sim}\left(c, c^{'} \cup c^{''}\right)\end{split}$
> 我理解的概念是，它是透過第三個cluster（$c$）去針對欲合併的$c^{'}$及$c^{''}$評估兩個cluster合併後的similarity。根據monotonicity的定義是表示合併後不應比合併前大。
>
> 但今天老師上課用那張圖說明的方式比較像是表達
> $\begin{split} \forall c^{'}, c^{''} \subseteq S: \mathrm{min}\left(\mathrm{sim}\left(c^{'}\right), \mathrm{sim}\left(c^{''}\right)\right) \geq \mathrm{sim}\left(c^{'} \cup c^{''}\right)\end{split}$
> 這個式子的概念是表達若合併兩個cluster，則合併後cluster內的similarity必定不會大於合併前原先兩個cluster自己本身的similarity。
>
> 參考NCTU.nlp.lecture4-a(4.17).pdf第18頁是有說明一個cluster如何計算average similarity
> $\begin{split} S(c_j) = \frac{1}{\left|c_j\right| \left(\left|c_j\right| - 1\right)}\sum_{\vec{x} \in c_j}\sum_{\vec{x} \neq \vec{y} \in c_j}\mathrm{sim}\left(\vec{x}, \vec{y}\right)\end{split}$
> 會這樣問是因為老師的投影片沒有放上monotonicity的數學定義，以及我先前說我證錯是因為我證成後者的定義，但前者跟後者我證明出來的結果會不相同XD[name=0860911]
>> 助教認為課本上monotonicity 這個數學定義比較容易造成混淆，參考
>> https://nlp.stanford.edu/IR-book/pdf/17hier.pdf
>>
>> Monotonic means that if s1
,s2, . . . ,sK−1 are the combination similarities
of the successive merges of an hierarchical agglomerative clustering, then s1 ≥ s2 ≥ . . . ≥ sK−1 holds. 這裡s為一個cluster的similartiy, k為merging step.
可以通過這個定義去證明。這個定義也跟老師課上解釋的相符[name=Joy][color=#cc4d5c]