---
tags: deeplearning, cs224n
---
CS224n L1 note review
https://hackmd.io/wARI4jJ9TJuKzh3m1l8cmA
# CS224N (2019) Lecture 2 Word Vectors and Word Senses

## Word2Vec


# $p(o|c) = \frac{exp(u_{w}^{T}v_{c})}{{\sum_{w\in{V}}exp(u_{w}^{T}v_{c})}}$


* 維度轉換
${n}\times{d}\cdot{d}\rightarrow{1}\rightarrow{n}\times{1}\rightarrow^{softmax}{n\times{1}}$

* 每個row 代表一個word vector
* 透過$softmax$取得映射後的機率分布,分布方式與上下文位置無關
* the, and, that, of等詞出現會產生預測影響
* 盡量去除the, and, that, of等word vector 效果會更好

## Gradient Descent

* 尋找最佳解
$\theta^{new}= \theta^{old}-\alpha\bigtriangledown_{\theta}{J(\theta)}$

${J(\theta)}$ 在corpus中所以計算 window的function
corpus越大相對於 $\bigtriangledown_{\theta}{J(\theta)}$ 的計算成本也會相對成長
ex: 數億個center words 相對也要計算contex words 經過${softmax}$後取得的機率

* **Solution**:
使用 Stochastic gradients Descent
只針對sample window進行計算與更新parameters
***benfit***: minimun of the function orders and magnitude quickly

* Mini-batch
approximately 32 or 64
***advantage***:透過平均值減少梯度計算的noise 與 透過GPU進行分散運算

## Stochastic gradients with word vectors
Stochastic Gradient Descent 每次只對每個樣本進行更新
$\bigtriangledown_{\theta}{J(\theta)}\rightarrow{sparse \ matrix}$
***ex:***
mini-batch size = 32
window size = 10
total 100-150 different words in mini-batch
corpus has ${1/4}$ million words

* **Solution**
1. 更新特定矩陣${U}跟{V}$ rows
2. 保留 word vector hash

另外corpus內擁有 millions of word vectors 進行分散運算則不用一直大量更新

## More Details

* why two vectors

**benfit**:
* 容易表示計算
* 在運算最後都取平均值 容易優化
* 每個詞可以只用一個vector

Skip-grams(SG)$\rightarrow$輸入center word 預測 context word
Continuous Bag of Words(CBOW)$rightarrow$輸入context word 預測center word

## The skip-gram model with negative sampling

為什麼要用negative sampling

$p(o|c) = \frac{exp(u_{w}^{T}v_{c})}{{\sum_{w\in{V}}exp(u_{w}^{T}v_{c})}}$)

透過$softmax$計算${\sum_{w\in{V}}exp(u_{w}^{T}v_{c})}$時計算成本過高,模型肥大

1. 將模型中常見的單詞組合（word pairs）或者詞組作為單個字詞「words」來處理。
2. 對高頻次單詞進行抽樣來減少訓練樣本的個數。
3. 在最佳化過程中採用「negative sampling」，使每個訓練樣本只會更新一小部分的模型權重，從而降低計算負擔。
4. negative sampling降低計算量負擔，同時也提高了詞向量的訓練品質。

ref: [negative sampling](python5566.wordpress.com/2018/03/17/nlp-筆記-negative-sampling/)

原文中的objective function

$J(\theta)=\frac{1}{T} \sum_{t=1}^{T} J_{t}(\theta)$
$J_{t}(\theta)=\log \sigma\left(u_{o}^{T} v_{c}\right)+\sum_{i=1}^{k} \mathbb{E}_{j \sim P(w)}\left[\log \sigma\left(-u_{j}^{T} v_{c}\right)\right]$

作業的 objective function
$J_{\text {neg-sample}}\left(\boldsymbol{o}, \boldsymbol{v}_{c}, \boldsymbol{U}\right)=-\log \left(\sigma\left(\boldsymbol{u}_{o}^{\top} \boldsymbol{v}_{c}\right)\right)-\sum_{k=1}^{K} \log \left(\sigma\left(-\boldsymbol{u}_{k}^{\top} \boldsymbol{v}_{c}\right)\right)$

***purpose***:
k = negative samples(prob)
context word 與 center word 機率最大化
center word 與 隨機詞 機率最小化

抽樣分布
$P(w)=U(w)^{3 / 4} / Z$

$U(w)\in{Unigram \ Distribution}$
${Z}\in{Normal \ Distribution}$

詞被選作negative sample的機率與該詞出現的頻率有關
出現頻率越高越容易被選作為negative word

## why not capture co-occurrence counts directly?

**Co-occurence matrix**
1. windows
2. full document

* windows 與 Word2Vec相似
* Word-document $\rightarrow$ LSA(潛在語意分析)

使用Co-occurence matrix衡量詞的相似性
會隨著詞量增加 matrix也隨之增加
matrix也需要更多空間來儲存並存在aparse問題
並必須透過降低維度獲得25-1000D的稠密向量

### Method 1:Dimensionality Reduction on X

**[SVD](https://molecular-service-science.com/2014/07/16/eigen-value-singular-value-decomposition-principal-component-analysis/)**(Singular Value Decomposition)

將Matrix X分解為$U \Sigma V^{\top}$
$\Sigma$為對角矩陣 $U,V$為正交關係
但對於大型矩陣而言 計算代價昂貴

### Hacks to X

依比例調整counts是有效的
1. 針對出現頻率高的詞進行縮放
***${}^\cdot{}_\cdot{}^\cdot$syntax影響***
* $min(X, t), t \approx 100$
* 使用 $\log$
* 全部忽視
2. 依照與center word的距離衰減
4. 使用[Pearson Correlation](https://www.yongxi-stat.com/pearson-correlation/)

## Count based vs. direct prediction

## Encoding meaning in vector differences
### ***GloVe***
Ratios of co-occurrence probabilities can encode
meaning components
重點在於比例 其中蘊含著meaning component

### How can we capture ratios of co-occurrence probabilities as linear meaning components in a word vector space?

$w_{i}$和$w_{j}$的詞向量乘積代表$w_{i}$在$w_{j}$周圍出現的機率
$w_{a}-w_{b}$ 值越大 代表 x 與 a 關係越高
$P({x}|{a})$表示 $w_{a}$出現在 $w_{x}$周圍的機率 類似LSA

#### GloVe Objective Function
$J=\sum_{i, j=1}^{V} f\left(X_{i j}\right)\left(w_{i}^{T} \tilde{w}_{j}+b_{i}+\tilde{b}_{j}-\log X_{i j}\right)^{2}$

${X_{ij}}$ = Co-occurence matrix

假設模型函數為
$F(w_{i},w_{j},\tilde{w}_{k}) = {\dfrac{P_{ik}}{P_{jk}}}$
${w_{i}}$ 與 ${w_{j}}$ 分別代表要比較的兩個詞
${\tilde{w}_{k}}$代表 context vector

將函數限定在線性空間內
$F(w_{i}-w_{j},\tilde{w}_{k}) = {\dfrac{P_{ik}}{P_{jk}}}$

轉化成矢量形式
$F((w_{i}-w_{j})^{T}\tilde{w}_{k}) = {\dfrac{P_{ik}}{P_{jk}}}$

要先滿足 相似度

$F((w_{i}-w_{j})^{T}\tilde{w}_{k}) = {\dfrac{(w_{i}^{T}\tilde{w}_{k})}{(w_{j}^{T}\tilde{w}_{k})}}$

解為 $F={\exp}$ 與 $F((w_{i}-w_{j})^{T}\tilde{w}_{k}) = {\dfrac{P_{ik}}{P_{jk}}}$
相比較 則
$F({w_{i}^{T}}\tilde{w}_{k}) = P_{ik} = {\dfrac{X_{ik}}{X_{i}}}$

所以 ${w_{i}^{T}}\tilde{w}_{k} = \log(P_{ik}) = \log(X_{ik})-\log{X_{i}}$

為了平衡對稱性 加入${w}_{i}$ 的bias ${w_{i}}$ 與 ${b}_{i}$ 的bias $\tilde{b}_{k}$
得到 $w_{i}^{T}\tilde{w}_{k} + {b}_{i} + \tilde{b}_{k}=\log(X_{ik})$
並加入$X_{ij}$ 來做weighted least squares regression模型，即為 $J=\sum_{i, j=1}^{V} f\left(X_{i j}\right)\left(w_{i}^{T} \tilde{w}_{j}+b_{i}+\tilde{b}_{j}-\log X_{i j}\right)^{2}$

使用$f(x)$對常見單字進行限制

advantage:
* 訓練快速
* 可擴展至大型corpus
* 小的corpus和vector 都有不錯得表現

## Evaluate word vectors
NLP評估方式
* 內在
* 特定或中間子任務評估
* 計算快速
* 理解系統
* 不確定是否真的有作用
* 外在
* 對真實任務評估
* 計算精確度需要大量時間
* 不確定問題所在
* 子系統替換另一個子系統可以提高精確度

### Intrinsic word vector evaluation

$d=\arg \max _{i} \frac{\left(x_{b}-x_{a}+x_{c}\right)^{T} x_{i}}{\left\|x_{b}-x_{a}+x_{c}\right\|}$


OO之於XX的概念

### Linear Algebraic Structure of Word Senses, with Applications to Polysemy

$v_{\text { pike }}=\alpha_{1} v_{\text { pike }_{1}}+\alpha_{2} v_{\text { pike }_{2}}+\alpha_{3} v_{\text { pike }_{3}} \\ \alpha_{1}=\frac{f_{1}}{f_{1}+f_{2}+f_{3}}$

加權平均就得到良好的效果

## Reference
[CS224n Lecture2 PDF](http://web.stanford.edu/class/cs224n/slides/cs224n-2019-lecture02-wordvecs2.pdf)
[Lecture 2 note](http://web.stanford.edu/class/cs224n/readings/cs224n-2019-notes02-wordvecs2.pdf)