【NLP】CS224N课程笔记|词向量I: 简介, SVD和Word2Vec
NewBeeNLP原創出品
公眾號專欄作者@Ryan?
知乎?|?機器學習課程筆記
CS224N課程筆記系列，持續更新中?
課程主頁：??http://web.stanford.edu/class/cs224n/
1、Introduction to Natural Language Processing
1.1 What is so special about NLP?
人類的語言有什么特別之處?人類語言是一個專門用來表達意義的系統，而不是由任何形式的物理表現產生的。在這方面上，它與視覺或任何其他機器學習任務都有很大的不同。
大多數單詞只是一個超語言實體的符號：單詞是一個映射到所指(想法或事物)的能指。
例如，“rocket”一詞指的是火箭的概念，因此可以引申為火箭的實例。當我們使用單詞和字母來表達符號時，也會有一些例外，例如“whoompaa”的使用。最重要的是，這些語言的符號可以被 encoded 成幾種形式：聲音、手勢、文字等等，然后通過連續的信號傳輸給大腦，大腦本身似乎也能以一種連續的方式對這些信號進行 encode。語言哲學和語言學已經做了大量的工作來使人類語言概念化，并區分單詞和它們的指代、意義等。
1.2 Examples of tasks
自然語言處理有不同層次的任務，從語音處理到語義解釋再到論述處理。自然語言處理的目標是通過設計算法使得計算機能夠“理解”語言，從而能夠執行某些特定的任務。不同的任務的難度是不一樣的：
「Easy」
拼寫檢查
關鍵詞檢索
同義詞查找
「Medium」
解析來自網站、文檔等的信息
「Hard」
機器翻譯
語義分析
指代消解
問答系統
1.3 How to represent words?
在所有的NLP任務中，第一個也是可以說是最重要的共同點是我們如何將單詞表示為任何模型的輸入。在這里我們不會討論早期的自然語言處理工作是將單詞視為 atomic symbols。為了讓大多數的自然語言處理任務能有更好的表現，我們首先需要了解單詞之間的相似和不同。有了詞向量，我們可以很容易地將其 encode 到向量本身中。
2、Word Vectors
大約一共有1千3百萬個英語單詞，它們都是沒有關系的嗎？例如 “feline” 和 “cat”，“hotel” 和 “motel” 是有關系的。因此，我們希望用詞向量 encode 單詞使它代表在詞組空間中的一個點。重要的原因有很多，但最直觀的原因是，實際上可能存在 N 維空間（例如 ），這足以 encode 我們語言的所有語義。每個維度都會 encode 一些使用言語傳達的意思。例如，語義維度可能表示時態（過去、現在和未來），計數（單數和復數）和性別（男性和女性）。
我們從最簡單的 「one-hot 向量」的來表示詞向量方法開始：每個詞都是一個 向量，其中除了該單詞所在的索引為 1 外其他索引都是 0。在這個定義下， 是詞匯表的大小。這時詞向量的可以表示為
我們將每個單詞表示為完全獨立的實體。我們之前討論過，這樣的單詞表示沒有給出任何直接相似的概念，例如，
也許我們可以嘗試降低維度，從 減少到更小以此來找到一個低維度的子空間來 encode 詞之間的關系。
3、SVD Based Methods
這是一類找到詞嵌入的方法（即詞向量），我們首先遍歷一個很大的數據集和統計詞的共現計數矩陣 X，然后對矩陣 X 進行 SVD 分解得到 。然后我們使用 U 的行來作為字典中所有詞的詞向量。我們來討論一下矩陣 X 的幾種選擇。
3.1、Word-Document Matrix
我們最初的嘗試，我們猜想相關連的單詞在同一個文檔中會經常出現。例如，“banks”，“bonds”，“stocks”，“moneys”等等，出現在一起的概率會比較高。但是“banks”，“octopus”，“banana”，“hockey”不大可能會連續地出現。我們根據這個情況來建立一個詞-文檔矩陣，X 是按照以下方式構建：遍歷數億的文檔和當詞 i 出現在文檔 j，我們對 加一。這顯然是一個很大的矩陣（ ），它的規模是和文檔（M）成正比關系。因此我們可以嘗試更好的方法。
3.2、Window based Co-occurrence Matrix
同樣的邏輯也適用于這里，但是矩陣 X 存儲單詞的共現，從而成為一個關聯矩陣。在這種方法中，我們計算每個單詞在感興趣單詞的附近特定大小的窗口中出現的次數。我們按照這個方法對語料庫中的所有單詞進行統計。我們在下面展示了一個例子。讓我們的語料庫是僅僅由三句話組成和窗口的大小是 1：
1. I enjoy flying.
2. I like NLP.
3. I like deep learning.
計數矩陣的結果如下所示：
3.3、Applying SVD to the cooccurrence matrix
然后我們對矩陣 X 使用 SVD，觀察奇異值（矩陣 S 上對角線上元素），根據期望的捕獲方差百分比截斷，留下前 k 個元素：
然后我們取子矩陣 作為詞嵌入矩陣。這就給出了詞匯表中每個詞的 k 維表示。
對矩陣 X 使用 SVD
「通過選擇前 k 個奇異向量來降低維度：」
這兩種方法都讓我們的詞向量 encode 充分的語義和句法（詞性標注）的信息，但是這些方法會存在許多問題：
矩陣的維度會經常發生改變（經常增加新的單詞和語料庫的大小會改變）。
矩陣會非常的稀疏，因為很多詞不會共現。
矩陣的維度一般會非常高（ ）。
基于 SVD 的方法的計算復雜度一般為 。
需要在 X 上加入一些技巧處理來解決詞頻的極劇的不平衡。
對上述討論中存在的問題存在以下的解決方法：
忽略功能詞，例如 “the”，“he”，“has” 等等。
使用 ramp window - 即基于在文檔中詞與詞之間的距離給共現計數加上一個權值。
使用皮爾遜相關系數將負數的計數設為 0，而不是使用原始的計數。
在下一部分，基于迭代的方法可以以更為優雅的方式解決大部分上述的問題。
4、Iteration Based Methods - Word2vec
這里我們嘗試一個新的方法。我們可以嘗試創建一個能夠一次學習一個迭代，并最終能夠對給定上下文的單詞的概率進行 encode 的模型，而不是計算和保留一個巨大的數據集的全局信息（可能含有數億個句子）。
這個想法是設計一個模型，該模型的參數就是詞向量。然后根據一個目標函數訓練模型，在每次模型的迭代計算誤差，并遵循一些更新規則，該規則具有懲罰造成錯誤的模型參數的作用，從而可以學習到詞向量。這個方法可以追溯到 1986年，我們稱這個方法為誤差“反向傳播”，這個方法簡化的模型和任務并使得訓練模型的速度更快。
已經很多人按照這個思路測試了不同的方法。[Collobert et al., 2011] 設計的模型首先將每個單詞轉換為向量，對每個特定的任務（命名實體識別、詞性標注等等），他們不僅訓練模型的參數，同時也訓練單詞向量，并取得了很好的 performance 和計算出了非常好的詞向量。
在這里，我們介紹一個非常有效的概率模型：Word2vec。Word2vec 是一個軟件包實際上包含：
「兩個算法」：continuous bag-of-words（CBOW）和 skip-gram。CBOW 是根據中心詞周圍的上下文單詞來預測該詞的詞向量。skip-gram 則相反，是根據中心詞預測周圍上下文的詞的概率分布。
「兩個訓練方法」：negative sampling 和 hierarchical softmax。Negative sampling 通過抽取負樣本來定義目標，hierarchical softmax 通過使用一個有效的樹結構來計算所有詞的概率來定義目標。
4.1、Language Models (Unigrams, Bigrams, etc.)
首先，我們需要創建一個模型來分配一個概率在一系列的單詞上。我們從一個例子開始：
“The cat jumped over the puddle”
一個好的語言模型會給這個句子很高的概率，因為在句法和語義上這是一個完全有效的句子。相似地，句子“stock boil fish is toy”會得到一個很低的概率，因為這是一個無意義的句子。在數學上，我們可以稱為對給定 n 個詞的序列的概率是：
我們可以使用 unary 語言模型方法，通過假設單詞的出現是完全獨立來將概率分開：
但是我們知道這是不大合理的，因為下一個單詞是高度依賴于前面的單詞序列的。如果使用上述的語言模型，會讓一個無意義的句子可能會具有很高的概率。所以也許我們讓序列的概率取決于序列中的單詞和其旁邊的單詞的成對概率。我們稱之為 bigram 模型：
但是，這個方法還是有點簡單，因為我們只關心一對鄰近的單詞，而不是針對整個句子來考慮。但是我們將看到，這個方法會有顯著的提升。考慮在詞-詞共現矩陣中，共現窗口為 1，我們基本上能得到這樣的成對的概率。但是，這又需要計算和存儲大量數據集的全局信息。
現在我們知道我們能夠如何考慮一個序列單詞的概率，讓我們了解一些可以計算這些概率的模型。
4.2、Continuous Bag of Words Model (CBOW)
一個方法是把 {"The","cat","over","the","puddle"} 作為上下文和從這些詞中能夠預測或者生成中心詞“jumped”。這樣的模型我們稱之為 continuous bag-of-words（CBOW）模型，它是從上下文中預測中心詞的方法，在這個模型中的每個單詞，我們希望學習兩個向量：v（輸入向量）當詞在上下文中；u（輸出向量）當詞是中心詞。
我們討論 CBOW 模型的更對的細節。首先我們設定已知參數。令我們模型的已知參數是 one-hot 形式的詞向量表示。輸入的 one-hot 向量或者上下文我們用 表示輸出用 表示。在 CBOW 模型中，因為我們只有一個輸出，因此我們把 y 稱為是已知中心詞的的 one-hot 向量。現在讓我們定義模型的未知參數。
首先我們對 CBOW 模型作出以下定義：
：詞匯表 V 中的單詞 i。
：輸入詞矩陣。
： 的第 i 列，單詞 的輸入向量表示。
：輸出詞矩陣。
： 的第 i 行，單詞 的輸出向量表示。
我們創建兩個矩陣， 和 。其中 n 是嵌入空間的任意維度大小。 是輸入詞矩陣，使得當其為模型的輸入時， ) 的第 i 列是詞 的 n 維嵌入向量。我們定義這個 的向量為 。相似地， 是輸出詞矩陣。當其為模型的輸入時， 的第 j 行是詞 的 n 維嵌入向量。我們定義 的這行為 。注意實際上對每個詞 我們需要學習兩個詞向量（即輸入詞向量 和輸出詞向量 ）。
我們將這個模型分解為以下步驟：
我們為大小為 m 的輸入上下文生成一個 one-hot 詞向量： 。
我們從上下文 得到嵌入詞向量。
對上述的向量求平均值 。
生成一個分數向量 。當相似向量的點積越高，就會令到相似的詞更為靠近，從而獲得更高的分數。
將分數轉換為概率 。這里 softmax 是一個常用的函數。它將一個向量轉換為另外一個向量，其中轉換后的向量的第 i 個元素是 。因為該函數是一個指數函數，所以值一定為正數；通過除以 來歸一化向量（ ）得到概率。
我們希望生成的概率， ，與實際的概率匹配， ，這是剛好實際的詞就是這個 one-hot 向量。
下圖是 CBOW 模型的計算圖示：
如果有 和 ，我們知道這個模型是如何工作的，那我們如何學習這兩個矩陣呢？這需要創建一個目標函數。一般我們想從一些真實的概率中學習一個概率，信息論提供了一個度量兩個概率分布的距離的方法。這里我們采用一個常見的距離/損失方法，交叉熵 。
在離散情況下使用交叉熵可以直觀地得出損失函數的公式：
上面的公式中，y 是 one-hot 向量。因此上面的損失函數可以簡化為：
c 是正確詞的 one-hot 向量的索引。我們現在可以考慮我們的預測是完美并且 的情況。然后我們可以計算 。因此，對一個完美的預測，我們不會面臨任何懲罰或者損失。現在我們考慮一個相反的情況，預測非常差并且 。和前面類似，我們可以計算損失 。因此，我們可以看到，對于概率分布，交叉熵為我們提供了一個很好的距離度量。因此我們的優化目標函數公式為：
我們使用 SGD 來更新所有相關的詞向量 和 。SGD 對一個窗口計算梯度和更新參數：
4.3、Skip-Gram Model
另外一個創建模型的方法是給定中心詞“jumped”，模型可以預測或者生成中心詞附近的詞語 “The”,“cat”,“over”,“the”,“puddle”。這樣的模型我們稱之為 Skip-Gram 模型。
首先我們對 Skip-Gram 模型作出以下定義：
：詞匯表 V 中的單詞 i。
：輸入詞矩陣。
： 的第 i 列，單詞 的輸入向量表示。
：輸出詞矩陣。
： 的第 i 行，單詞 的輸出向量表示。
我們現在來討論一下 Skip-Gram 模型。Skip-Gram 和 CBOW 大體上是一樣的，但是我們基本上交換了我們的 x 和 y，即 CBOW 中的 x 現在是 y，y 現在是 x。輸入的 one-hot 向量（中心詞）我們表示為 x，輸出向量為 。我們定義的 和 是和 CBOW 一樣的。
我們將這個模型分解為以下步驟：
我們生成中心詞的 one-hot 向量 。
我們對中心詞 得到詞嵌入向量。
生成分數向量 。
將分數向量轉化為概率， 。注意 是每個上下文詞觀察到的概率。
我們希望我們生成的概率向量匹配真實概率 ，one-hot 向量是實際的輸出。
下圖是 Skip-Gram 模型的計算圖示：
和 CBOW 模型一樣，我們需要生成一個目標函數來評估這個模型。與 CBOW 模型的一個主要的不同是我們引用了一個樸素的貝葉斯假設來拆分概率。如果你之前沒有了解過，這里可以先放下，這是一個很強（樸素）的條件獨立假設。換而言之，給定中心詞，所有輸出的詞是完全獨立的。
通過這個目標函數，我們可以計算出與未知參數相關的梯度，并且在每次迭代中通過 SGD 來更新它們。
注意
其中 是向量 的概率和 one-hot 向量 之間的交叉熵。
4.4、Negative Sampling
讓我們再回到目標函數上。注意對 的求和計算量是非常大的！任何的更新或者對目標函數的評估都要花費 的時間復雜度。一個簡單的想法是不去直接計算，而是去求近似值。
在每一個訓練的時間步，我們不去遍歷整個詞匯表，而僅僅是抽取一些負樣例！我們對噪聲分布（ ）“抽樣”，這個概率是和詞頻的順序相匹配的。我們將負抽樣放到問題中，我們只需要更新：
目標函數
梯度
更新規則
Mikolov 在論文《Distributed Representations of Words and Phrases and their Compositionality.》中提出了「負采樣」。雖然負采樣是基于 Skip-Gram 模型，但實際上是對一個不同的目標函數進行優化。考慮一對中心詞和上下文詞 。這詞對是來自訓練數據集嗎？我們通過 表示 是來自語料庫。相應地， 表示 不是來自語料庫。首先，我們對 用 sigmoid 函數建模：
現在，我們建立一個新的目標函數，如果中心詞和上下文詞確實在語料庫中，就最大化概率 ，如果中心詞和上下文詞確實不在語料庫中，就最大化概率 。我們對這兩個概率采用一個簡單的極大似然估計的方法（這里我們把 作為模型的參數，在我們的例子是 和 ）。
注意最大化似然函數等同于最小化負對數似然：
注意 是“假的”或者“負的”語料。例如我們有句子類似“stock boil fish is toy”，這種無意義的句子出現時會得到一個很低的概率。我們可以從語料庫中隨機抽樣出負樣例 。
對于 Skip-Gram 模型，我們對給定中心詞 c 來觀察的上下文單詞 c-m+j 的新目標函數為
對 CBOW 模型，我們對給定上下文向量 來觀察中心詞 的新的目標函數為
在上面的公式中， 是從 中抽樣。有很多關于如何得到最好近似的討論，從實際效果看來最好的是指數為 3/4 的 Unigram 模型。那么為什么是 3/4？下面有一些例如可能讓你有一些直觀的了解：
“Bombastic”現在被抽樣的概率是之前的三倍，而“is”只比之前的才提高了一點點。
4.5、Hierarchical Softmax
Mikolov 在論文《Distributed Representations of Words and Phrases and their Compositionality.》中提出了 hierarchical softmax，相比普通的 softmax 這是一種更有效的替代方法。在實際中，hierarchical softmax 對低頻詞往往表現得更好，負采樣對高頻次和較低維度向量表現得更好。
Hierarchical softmax 使用一個二叉樹來表示詞表中的所有詞。樹中的每個葉結點都是一個單詞，而且只有一條路徑從根結點到葉結點。在這個模型中，沒有詞的輸出表示。相反，圖的每個節點（根節點和葉結點除外）與模型要學習的向量相關聯。
在這個模型中，給定一個向量 的下的單詞 w 的概率 ，等于從根結點開始到對應 w 的葉結點結束的隨機漫步概率。這個方法最大的優勢是計算概率的時間復雜度僅僅是 ，對應著路徑的長度。
下圖是 Hierarchical softmax 的二叉樹示意圖：
讓我們引入一些概念。令 為從根結點到葉結點 w 的路徑中節點數目。例如，上圖中的 為 3。我們定義 為與向量 相關的路徑上第 i 個結點。因此 是根結點，而 是 w 的父節點。現在對每個內部節點 n，我們任意選取一個它的子節點和定義為 （一般是左節點）。然后，我們可以計算概率為
其中
和 是 函數。
這個公式看起來非常復雜，讓我們細細梳理一下。
首先，我們將根據從根節點 到葉節點 的路徑的形狀來計算相乘的項。如果我們假設 一直都是 n 的左節點，然后當路徑往左時 的值返回 1，往右則返回 0。
此外， 提供了歸一化的作用。在節點 n 處，如果我們將去往左和右節點的概率相加，對于 的任何值則可以檢查，
歸一化也保證了 ，和在普通的 softmax 是一樣的。
最后我們計算點積來比較輸入向量 對每個內部節點向量 的相似度。下面我們給出一個例子。以上圖中的 為例，從根節點要經過兩次左邊的邊和一次右邊的邊才到達 ，因此
我們訓練模型的目標是最小化負的對數似然 。不是更新每個詞的輸出向量，而是更新更新二叉樹中從根結點到葉結點的路徑上的節點的向量。
該方法的速度由構建二叉樹的方式確定，并將詞分配給葉節點。Mikolov 在論文《Distributed Representations of Words and Phrases and their Compositionality.》中使用的是赫夫曼樹，在樹中分配高頻詞到較短的路徑。
本文參考資料
[1]
Abigail See: https://link.zhihu.com/?target=https%3A//cs.stanford.edu/people/abisee/%23one
[2]cs224n: https://link.zhihu.com/?target=http%3A//web.stanford.edu/class/cs224n/
[3]Word Vectors I: Introduction, SVD and Word2Vec: https://link.zhihu.com/?target=http%3A//web.stanford.edu/class/cs224n/readings/cs224n-2019-notes01-wordvecs1.pdf
-?END?-
總結
以上是生活随笔為你收集整理的【NLP】CS224N课程笔记|词向量I: 简介, SVD和Word2Vec的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python工程能力进阶、数学基础、经典
- 下一篇： 【Python基础】当变量有值时，为什么