?PaperWeekly 原創 ·?作者｜蘇劍林

單位｜追一科技

研究方向｜NLP、神經網絡

最近，筆者入了一個新坑：基于離散優化的思想做一些文本生成任務。簡單來說，就是把我們要生成文本的目標量化地寫下來，構建一個分布，然后搜索這個分布的最大值點或者從這個分布中進行采樣，這個過程通常不需要標簽數據的訓練。

由于語言是離散的，因此梯度下降之類的連續函數優化方法不可用，并且由于這個分布通常沒有容易采樣的形式，直接采樣也不可行，因此需要一些特別設計的采樣算法，比如拒絕采樣（Rejection Sampling）、MCMC（Markov Chain Monte Carlo）、MH 采樣（Metropolis-Hastings Sampling）、吉布斯采樣（Gibbs Sampling），等等。

有些讀者可能會覺得有些眼熟，似乎回到了讓人頭大的學習 LDA（Latent Dirichlet Allocation）的那些年？沒錯，上述采樣算法其實也是理解 LDA 模型的必備基礎。本文我們就來回顧這些形形色色的采樣算法，它們將會出現在后面要介紹的豐富的文本生成應用中。

明確目標

很多時候，我們需要根據一些特定的信息 來生成目標文本 ，用數學的話說就是條件語言模型 ，不過我們無法得到足夠多的語料對 去直接監督訓練一個條件語言模型，而是只能訓練一個無條件的語言模型 ，但我們又可以人為地設計一個指標來定量描述 和 之間的聯系。

那么在這種情況下，如何根據無條件的語言模型 和 之間的聯系來做有條件的文本生成，便成為了我們的研究對象。我們可以稱之為“受限文本生成（Constrained Text Generation）”

舉例來說，用關鍵詞造句，那么 就是關鍵詞的集合，我們可以定義示性函數：

繼而定義：

保證了生成句子的流暢性， 保證了生成句子包含所要求的關鍵詞，那么問題就可以變成最大化操作 或采樣操作 。當然，這里的 還不是概率分布，要完成歸一化后才是真正的概率分布：

但分母通常是難以顯式計算出來的。那也就是說，我們對待采樣分布也只了解到它正比于某個函數 ，而不知道精確的分布表達式。

類似的例子并不少，比如說文本摘要。什么是文本摘要呢？其實就是用更少的文字 盡可能表達出跟原文 一樣的意思，這時候我們可以定義：

這里的 是某個文本相似度函數，而 是長度的示性函數，即 的長度在某個范圍（可能依賴于 ）內，它就為 1，否則為 0。此時我們同樣得到了一個未歸一化的概率分布 ，需要最大化它或者從它里邊采樣。

很明顯，這個目標就意味著我們要得到一段跟原文語義盡可能相似的、長度滿足一定約束的文字，這不就是摘要的存在意義嗎？所以，這套思路的核心出發點就在于：我們要把自己要生成的目標定量地捋清楚，然后再去執行下一步操作。

困難分析

所以，拋開前面的背景不說，現在我們面臨的問題就是有一個分布 ，我們只知道 ，即：

中的分母我們無法顯式計算出來。在本系列文章中， 代表文本，即一個離散元素的序列，但后面的推論同樣也適用于 是連續型向量的場景。現在我們要搜索最大位置 或進行采樣 ，后面我們將會看到，搜索最大值其實也可以看成是采樣的特例，因此我們主要關心采樣方式。

前面說了，之所以需要設計一些特別的算法來完成采樣，是因為直接從 中采樣是困難的，而我們需要理解采樣的困難所在，才能真正理解后面所設計的采樣算法的關鍵之處。困難在哪？

如果 的候選值空間不大，哪怕有 100 萬個候選值，我們都可以把每個 都算出來，然后按照普通的類別采樣來進行。然而，一般 的候選值空間遠遠不止 100 萬，假如 有 10 個分量，每個分量有 1 萬個選擇（對應于候選字數目），那么總的排列就有 種了，不可能事先算好每一種排列的概率然后依概率采樣。

那怎么辦呢？所謂“不積硅步，無以至千里”，那就只能一步步來了，也就是說，我沒法直接實現 選 1，那我做 10 次“ 選 1”可以嗎？這就對應著所謂的“自回歸生成”：

這樣我們就可以先從 采樣一個 ，然后從 中采樣一個 ，依此遞歸了。但是，自回歸生成只是對應于無條件的語言模型或者是有監督訓練的 Seq2Seq 模型，而如果希望像前面舉的例子那樣，往無條件語言模型的生成過程中加點約束，那么對應出來的模型就不再是自回歸的了，也就無法按照這樣的遞歸采樣了。

所以，我們就不得不需要后面介紹的各種采樣算法了，它也是“一步步來”的思想，但所使用的分布形式更加廣泛一些。

重要采樣

在《從采樣看優化：可導優化與不可導優化的統一視角》[1] 、《如何劃分一個跟測試集更接近的驗證集？》[2] 等文章里，我們介紹過“重要性采樣”的概念，即如果我們想估計期望 ，但是 又不是易于采樣的分布，那么我們可以找一個跟 相近的、易于采樣的分布 ，然后根據下述變換：

轉化為從 采樣來算 的期望了，也就是用 對每個樣本進行加權，所以它被稱為“重要性采樣（Importance Sampling）”。如果只知道 ，那么重要性采樣也是可以進行的，這是因為：

所以：

這樣一來，我們發現上式只依賴于 的相對值，不依賴于它的絕對值，所以把 換成跟它成正比的 也是可以的，最終簡化成：

拒絕采樣

上一節的重要性采樣實現了將復雜分布期望轉化為簡單分布期望，但這還不是我們的真正目的，我們要實現的是把樣本從分布 中采樣出來，而不是估算它的某個期望。思想依然跟重要性采樣一樣，引入易于采樣的分布 ，然后從中隨機地篩掉某些樣本，使得剩下的樣本服從分布 。

具體來說，假設有函數 ，我們按照如下流程進行采樣（即“拒絕采樣”）：

從 采樣一個樣本 ，從 中采樣一個隨機數 ，若 則接受該樣本，否則拒絕并重新按照此流程采樣。

那么，此時采樣出來的 真正的概率分布是什么呢？其實也不難，由于樣本 被保留下來的概率是 ，因此它的相對概率就是 ，我們只需要將它重新歸一化：

就得到拒絕采樣對應的真正的概率分布了，從這個形式也可以看出，將接受率乘以一個 0 到 1 之間的數，理論上拒絕采樣對應的分布是不變的。

這個過程啟示我們，拒絕采樣可以讓我們實現從正比于 的分布中采樣，那么根據，我們可以讓 作為接受概率，來進行從 出發的拒絕采樣，結果就相當于從 采樣了。

當然，還沒那么簡單，根據概率的歸一化性質，除非 恒等于 ，否則 不可能一直都在 內。但這不要緊，只要 有上界，那么我們就可以選擇一個足夠大的常數 M，使得 ，此時以 為接受概率即可，剛才我們說了，乘以一個常數不會影響拒絕采樣對應的分布。換句話說，也就是這個過程同樣不依賴于完全精確的 ，可以將 換成跟它成正比的 。

關于接受率 ，盡管理論上只要求它 就行了，但實際上還是以 為好，這是因為過小的接受率會導致拒絕太多（幾乎來一個拒絕一個），采樣效率太低，生成一個合理的樣本的成本過大了。

類似地，盡管理論上對 的要求只是易于采樣并且 有上界，但實際上 與 仍然是越相近越好，否則依然可能造成接受率過低而導致采樣成本大到難以接受。所以，盡管拒絕采樣看上去提供了一種幾乎能從任意分布 中進行采樣的方案，但實際應用時近似分布 的設計依然是一個不小的難題。

本文小結

從本文開始，我們開了個新坑，試圖從離散優化的角度來完成某些文本生成任務（受限文本生成）。它通過確定一個定量的評估目標，然后通過最大化這個目標或者從中采樣就可以得到我們想要的輸出，而不需要標簽數據監督訓練新模型。

在這個過程中，所要用到的工具是一些主要是采樣算法，本文先介紹了其中很基本的重要性采樣和拒絕采樣，后面將會繼續完善該系列文章，敬請大家期待。

參考文獻

[1] https://kexue.fm/archives/7521

[2] https://kexue.fm/archives/7805

更多閱讀

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發，請在投稿時提醒并附上所有已發布鏈接?

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的​搜出来的文本：从文本生成到搜索采样的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。