像追美劇一樣追課程！
大資料文摘已獲得斯坦福大學深度學習課程cs224d的翻譯授權，重磅啟動“斯坦福深度學習課程cs224d”的翻譯工程，所有譯文将會免費釋出，計劃每周釋出1篇。期待你的加入，加入要求見文末，報名請點選文末“閱讀原文”。
大資料文摘作品，轉載需授權 作者|寒小陽 && 龍心塵 感謝@fantzy同學的幫助
大資料文摘“機器學習”專欄介紹
本文為大資料文摘機器專欄推出的【資料科學/機器學習】學習分享項目啟動篇，我們将以stanford、harvard等優秀高校的前沿資料科學課程為主線的學習與分享，将資料科學普及給更多國内的讀者，也通過互相學習和交流加深對資料領域知識的了解認識。
課堂筆記：第一部分
春季2016
關鍵詞：自然語言處理（nlp）.詞向量（word vectors）.奇異值分解(singular value decomposition). skip-gram. 詞組的持續爆（cbow）,負采樣樣本（negative sampling）
這是本課程的第一節，我們會先介紹自然語言處理（nlp）的概念和nlp現在所面對問題；然後開始讨論用數學向量代表自然語言詞組的設想。最後我們會讨論現行的詞向量構造方法。
在最開始咱們先說說什麼是nlp。nlp的目的是設計出算法，讓計算機“懂得”人類的自然語言，進而為人類執行任務。這些任務分為幾個難度等級，例如
容易的任務：
文法檢查
關鍵詞搜尋
查找同義詞
中等難度的任務：
從網站，檔案或其他來源中提取資訊
比較有挑戰的任務：
機器翻譯（例如：中譯英）
語意分析（提問者說的意思是什麼）
指代分析（例如. “他”或“它”在一個特定檔案中指的是什麼）
回答問題（例如.回答“jeopardy questions”一種涉及人類社會各個方面的綜藝問答）
在處理所有nlp任務的時候，我們首先需要解決非常重要的一個問題(可能是最重要的)：用什麼方式将詞組輸入到模型中去。簡單的nlp問題可能并不需要将詞組作為獨立個體對待（atomic symbols），但現在的問題絕大多數需要這樣一個預處理，來展現詞組之間關聯/相似性和差別。是以我們引入詞向量的概念，如果把詞編碼成詞向量，我們很容易從向量的角度去衡量不同的詞之間的關聯與差異（常用的距離測度法，包括jaccard, cosine, euclidean等等，注：距離測度法，即用一個可觀測度量的量來描述一個不能直接觀測度量的量）。
我們拿英文舉例:
英語中大約有1300萬個詞組（token，自定義字元串，譯作詞組），不過他們全部是獨立的嗎？并不是哦，比如有一些詞組，“feline貓科動物”和“cat貓”，“hotel飯店“和”motel汽車旅館”，其實有一定的關聯或者相似性在。是以，我們希望用詞向量編碼詞組，使它代表在詞組的n維空間中的一個點（而點與點之間有距離的遠近等關系，可以展現深層一點的資訊）。每一個詞向量的次元都可能會表征一些意義（實體含義），這些意義我們用“聲明speech”來定義。例如，語義次元可以用來表明時态（過去與現在與未來），計數（單數與複數），和性别（男性與女性）。
說起來，詞向量的編碼方式其實挺有講究的。咱們從最簡單的看起，最簡單的編碼方式叫做one-hot vector：假設我們的詞庫總共有n個詞，那我們開一個1*n的高維向量，而每個詞都會在某個索引index下取到1，其餘位置全部都取值為0.詞向量在這種類型的編碼中如下圖所示：
這種詞向量編碼方式簡單粗暴，我們将每一個詞作為一個完全獨立的個體來表達。遺憾的是，這種方式下，我們的詞向量沒辦法給我們任何形式的詞組相似性權衡。例如:
（注：這裡w−1是w的逆矩陣，它們有關系：w−1∗w=1，注意到hotel和motel是近義詞）
究其根本你會發現，是你開了一個極高次元的空間，然後每個詞語都會占據一個次元，是以沒有辦法在空間中關聯起來。是以我們可能可以把詞向量的次元降低一些，在這樣一個子空間中，可能原本沒有關聯的詞就關聯起來了。
3.基于svd的方法
這是一種構造詞嵌入（即詞向量）的方法，我們首先會周遊所有的文本資料集，然後統計詞出現的次數，接着用一個矩陣x來表示所有的次數情況，緊接着對x進行奇異值分解得到一個usvt的分解。然後用u的行（rows）作為所有詞表中詞的詞向量。對于矩陣x，我們有幾種選擇，咱們一起來比較一下。
最初的想法是，我們猜測互相關聯的詞組同時出現在相同的檔案中的機率很高。例如，“銀行”、“債券”、“股票”、“錢”等都可能出現在一起。但是，“銀行”、“章魚”、“香蕉”和“曲棍球”可能不會一直一起出現。基于這個想法，我們建立一個詞組文檔矩陣x，具體是這麼做的：周遊海量的檔案，每次詞組i出現在檔案j中時，将xij的值加1。不過大家可想而知，這會是個很大的矩陣r|v|×m，而且矩陣大小還和文檔個數m有關系。是以咱們最好想辦法處理和優化一下。
我們還是用一樣的邏輯，不過換一種統計方式，把矩陣x記錄的詞頻變成一個相關性矩陣。我們先規定一個固定大小的視窗，然後統計每個詞出現在視窗中次數，這個計數是針對整個語料集做的。可能說得有點含糊，咱們一起來看個例子，假定我們有如下的3個句子，同時我們的視窗大小設定為1（把原始的句子分拆成一個一個的詞）：
1. i enjoy flying.
2. i like nlp.
3. i like deep learning.
由此産生的計數矩陣如下：
然後我們對x做奇異值分解，觀察觀察奇異值（矩陣的對角元素），并根據我們期待保留的百分比來進行階段（隻保留前k個次元）：
然後我們把子矩陣u1:|v|,1:k視作我們的詞嵌入矩陣。也就是說，對于詞表中的每一個詞，我們都用一個k維的向量來表達了。
對x采用奇異值分解
通過選擇前k個奇異向量來進行降維：
這兩種方法都能産生詞向量，它們能夠充分地編碼語義和句法的資訊，但同時也帶來了其他的問題：
矩陣的次元會經常變化（新的詞語經常會增加，語料庫的大小也會随時變化）。
矩陣是非常稀疏的，因為大多數詞并不同時出現。
矩陣的次元通常非常高（≈106×106）
訓練需要o(n2)的複雜度（比如svd）
需要專門對矩陣x進行特殊處理，以應對詞組頻率的極度不平衡的狀況
當然，有一些辦法可以緩解一下上述提到的問題：
忽視諸如“he”、“the” 、“has”等功能詞。
應用“傾斜視窗”（ramp window），即:根據檔案中詞組之間的距離給它們的共現次數增加相應的權重。
使用皮爾森的相關性（pearson correlation），将0記為負數，而不是它原來的數值。
不過緩解終歸隻是緩解，咱們需要更合理地解決這些問題，這也就是我們馬上要提到的基于疊代的方法。
4.基于疊代的方法
現在我們退後一步，來嘗試一種新的方法。在這裡我們并不計算和存儲全局資訊，因為這會包含太多大型資料集和數十億句子。我們嘗試建立一個模型，它能夠一步步疊代地進行學習，并最終得出每個單詞基于其上下文的條件機率。
詞語的上下文：
一個詞語的上下文是它周圍c個詞以内的詞。如果c=2，句子"the quick brown fox jumped over the lazy dog"中單詞"fox"的上下文為 {"quick", "brown", "jumped", "over"}.
我們想建立一個機率模型，它包含已知和未知參數。每增加一個訓練樣本，它就能從模型的輸入、輸出和期望輸出（标簽），多學到一點點未知參數的資訊。
在每次疊代過程中，這個模型都能夠評估其誤差，并按照一定的更新規則，懲罰那些導緻誤差的參數。這種想法可以追溯到1986年（learning representations by back-propagating errors. david e. rumelhart, geoffrey e. hinton, and ronald j.williams (1988)），我們稱之為誤差“反向傳播”法。
首先，我們需要建立一個能給“分詞序列”配置設定機率的模型。我們從一個例子開始：
"the cat jumped over the puddle."（貓 跳 過 水坑）
一個好的語言模型會給這句話以很高的機率，因為這是一個在文法和語義上完全有效的句子。同樣地，這句”stock boil fish is toy”（股票 煮 魚 是 玩具）就應該有一個非常低的機率 ，因為它是沒有任何意義的。在數學上，我們可以令任意給定的n個有序的分詞序列的機率為：
我們可以采用一進制語言模型。它假定詞語的出現是完全獨立的，于是可以将整個機率拆開相乘：
看到這裡，肯定很多同學就要噴了，這不對，詞和詞之間沒有關聯嗎？确實，我們知道一句話中每一個詞語都跟它前面的詞語有很強的依賴關系，忽略這一點的話，一些完全無意義的句子，可能會有很高的機率。咱們稍微改一改，讓一個詞語的機率依賴于它前面一個詞語。我們将這種模型稱作bigram（2-gram，二進制語言模型），表示為：
看起來還是有點簡單？恩，也對，我們隻考慮一個詞語依賴于其相鄰的一個詞語的關系，而不是考慮其依賴整個句子的情況。别着急，接下來将會看到，這種方法能讓我們有非常顯著的進步。考慮到前面 “詞-詞”矩陣的情況，我們至少可以算出兩個詞語共同出現的機率。但是，舊話重提，這仍然要求儲存和計算一個非常的大資料集裡面的全部資訊。
現在我們了解了“分詞序列”的機率（其實就是n-gram語言模型啦），讓我們觀察一些能夠學習到這些機率的例子。
有種模型是以{“the”, “cat”, ’over”, “the’, “puddle”}為上下文，能夠預測或産生它們中心的詞語”jumped”，叫做連續詞袋模型。
上面是最粗粒度的描述，咱們來深入一點點，看點細節。
首先，我們要建立模型的一些已知參數。它們就是将句子表示為一些one-hot向量，作為模型的輸入，咱們記為x(c)吧。模型的輸出記為y(c)吧。因為連續詞袋模型隻有一個輸出，是以其實我們隻需記錄它為y。在我們上面舉的例子中，y就是我們已經知道的（有标簽的）中心詞（如本例中的”jumped”）。
好了，已知參數有了，現在我們一起來定義模型中的未知參數。我們建立兩矩陣，v∈rn∗|v|和u∈r|v|∗n 。其中的n是可以任意指定的，它用來定義我們“嵌入空間”（embedding space）的次元。v是輸入詞矩陣。當詞語wi（譯注：wi是隻有第i維是1其他維是0的one-hot向量）作為模型的一個輸入的時候，v的第i列就是它的n維“嵌入向量”（embedded vector）。我們将v的這一清單示為vi。類似的，u是輸出矩陣。當wj作為模型輸出的時候，u的第j行就是它的n維“嵌入向量”。我們将u的這一行表示為uj。要注意我們實際上對于每個詞語wi學習了兩個向量。（作為輸入詞的向量vi，和作為輸出詞的向量uj）。
連續詞袋模型（cbom）中的各個記号：
wi:單詞表v中的第i個單詞
v∈rn∗|v|：輸入詞矩陣
vi：v的第i列，單詞wi的輸入向量
u∈r|v|∗n：輸出詞矩陣
ui：u的第i行，單詞wi的輸出向量
那這個模型是如何運作的呢？我們把整個過程拆分成以下幾步：
對于m個詞長度的輸入上下文，我們産生它們的one-hot向量（x(c−m),⋯,x(c−1),x(c+1),⋯,x(c+m)）。
我們得到上下文的嵌入詞向量（vc−m+1=vx(c−m+1),⋯,v_{c+m}=vx^{(c+m)}）
将這些向量取平均v^=vc−m+vc−m+1+⋯+vc+m2m
産生一個得分向量 z=uv^
将得分向量轉換成機率分布形式y^=softmax(z)
我們希望我們産生的機率分布 ,與真實機率分布y^相比對。而y剛好也就是我們期望的真實詞語的one-hot向量。
用一幅圖來表示就是下面這個樣子：
通過上面說的種種步驟，我們知道有了矩陣u、v整個過程是如何運作的，那我們怎樣找到u和v呢？——我們需要有一個目标函數。通常來說，當我們試圖從已知機率學習一個新的機率時，最常見的是從資訊論的角度尋找方法來評估兩個機率分布的差距。其中廣受好評又廣泛應用的一個評估差異/損失的函數是交叉熵：
結合我們當下的例子，y隻是一個one-hot向量，于是上面的損失函數就可以簡化為：
我們用c表示y這個one-hot向量取值為1的那個次元的下标。是以在我們預測為準确值的情況下y^c=1。于是損失為 −1 log(1) = 0。是以對于一個理想的預測值，因為預測得到的機率分布和真實機率分布完全一樣，是以損失為0。現在讓我們看一個相反的情況，也就是我們的預測結果非常不理想，此時y^c=0.01。計算得到的損失為−1 log(0.01) ≈ 4.605，損失非常大，原本這才是标準結果，可是你給了一個非常低的機率，是以會拿到一個非常大的loss 。可見交叉熵為我們提供了一個很好的衡量兩個機率分布的差異的方法。于是我們最終的優化函數為：
我們用梯度下降法去更新每一個相關的詞向量uc和vj 。
很上面提到的模型對應的另一種思路，是以中心的詞語”jumped”為輸入，能夠預測或産生它周圍的詞語”the”, “cat”, ’over”, “the”, “puddle”等。這裡我們叫”jumped”為上下文。我們把它叫做skip-gram 模型。
這個模型的建立與連續詞袋模型（cbom）非常相似，但本質上是交換了輸入和輸出的位置。我們令輸入的one-hot向量（中心詞）為x（因為它隻有一個），輸出向量為y(j)。u和v的定義與連續詞袋模型一樣。
skip-gram 模型中的各個記号：
對應到上面部分，我們可以把skip-gram 模型的運作方式拆分成以下幾步：
生成one-hot輸入向量x。
得到上下文的嵌入詞向量vc=vx。
因為這裡不需要取平均值的操作，是以直接是v^=vc。
通過u=uvc産生2m個得分向量uc−m,⋯,uc−1,uc+1,⋯,u(c+m)。
将得分向量轉換成機率分布形式y=softmax(u)。
我們希望我們産生的機率分布與真實機率分布yc−m,⋯,yc−1,,yc+1⋯,yc+m 相比對，也就是我們真實輸出結果的one-hot向量。
用一幅圖來表示這個過程如下：
像連續詞袋模型一樣，我們需要為模型設定一個目标/損失函數。不過不同的地方是我們這裡需要引入樸素貝葉斯假設來将聯合機率拆分成獨立機率相乘。如果你之前不了解它，可以先跳過。這是一個非常強的條件獨立性假設。也就是說隻要給出了中心詞，所有的輸出詞是完全獨立的。
我們可以用随機梯度下降法去更新未知參數的梯度。
我們再次觀察一下目标函數，注意到對整個單詞表|v|求和的計算量是非常巨大的，任何一個對目标函數的更新和求值操作都會有o(|v|)的時間複雜度。我們需要一個思路去簡化一下，我們想辦法去求它的近似。
對于每一步訓練，我們不去循環整個單詞表，而隻是抽象一些負面例子就夠了！我們可以從一個噪聲分布(pn(w))中抽樣，其機率分布與單詞表中的頻率相比對。為了将描述問題的公式與負面抽樣相結合，我們隻需要更新我們的：
目标函數
梯度
更新規則
mikolov et al.在他的《distributed representations of words and phrases and their compositionality》中提出了負面抽樣。雖然負面抽樣是基于skip-gram 模型，它實際上是對一個不同的目标函數進行最優化。考慮一個“詞-上下文”對（w,c），令p(d = 1|w, c)為(w, c)來自于語料庫的機率。相應的，p(d = 0|w, c) 則是不來自于語料庫的機率。我們首先對p(d = 1|w, c)用sigmoid函數模組化：
現在我們需要建立一個新的目标函數。如果(w, c)真是來自于語料庫，目标函數能夠最大化p(d = 1|w, c)。反之亦然。我們對這兩個機率采用一個簡單的最大似然法。（這裡令θ為模型的參數，在我們的例子中，就是對應的u和v。）
注意這裡的d˜表示“錯誤的”或者“負面的”語料庫，像句子”stock boil fish is toy”就是從這樣的語料庫來的。不自然的句子應該有比較低的發生機率，我們可以從詞庫中随機采樣來産生這樣的“負面的”語料庫。我們的新目标函數就變成了：
在這裡{u˜k|k=1,⋯,k}是從(pn(w))中抽樣取到的。需要多說一句的是，雖然關于怎麼樣最好地近似有許多讨論和研究，但是工作效果最好的似乎是指數為3/4的一進制語言模型。至于為什麼是3/4，下面有幾個例子來幫助大家感性地了解一下：
你看，經過3/4這樣一個指數處理，”bombastic”(少見)被采樣的機率是之前的3倍，而“is”這個詞(多見)被采樣的機率隻是稍微增長了一點點。
原文釋出時間為：2016-06-06
本文來自雲栖社群合作夥伴“大資料文摘”，了解相關資訊可以關注“bigdatadigest”微信公衆号