閱讀筆記-計(jì)算廣告第十章-基礎(chǔ)知識(shí)準(zhǔn)備

計(jì)算廣告并不是一門獨(dú)立的學(xué)科蜓氨，它更應(yīng)該被看成是一個(gè)工業(yè)界的具體問題聋袋。

在進(jìn)入具體的廣告技術(shù)和算法之前穴吹，先概要性的介紹幾個(gè)相關(guān)領(lǐng)域的技術(shù)和算法幽勒，為后面的算法章節(jié)做鋪墊。

1. 信息檢索

1.1 倒排索引

倒排索引是現(xiàn)代搜索引擎的核心技術(shù)之一港令，其核心目的是將從大量文檔中查找某些詞的文檔集合這一任務(wù)啥容，用o（1）或o（logn）的時(shí)間復(fù)雜度完成。

假設(shè)有如下幾篇文檔：

D0=“谷歌地圖之父跳槽Facebook”
D1=“谷歌地圖之父加盟Facebook”
D2=“谷歌地圖創(chuàng)始人離開谷歌加盟Facebook”
D3=“谷歌地圖創(chuàng)始人跳槽Facebook與Wave項(xiàng)目取消有關(guān)”
D4=“谷歌地圖創(chuàng)始人拉斯加盟社交網(wǎng)絡(luò)Facebook”

對(duì)每篇文檔都進(jìn)行分詞顷霹、去除’與’這樣的沒有實(shí)際表意作用的停止詞咪惠，之后建立一個(gè)倒排索引，也就是所有關(guān)鍵詞的倒排鏈集合泼返。表示如下：

谷歌->{D0,D1,D2,D3,D4}
地圖->{D0,D1,D2,D3,D4}
之父->{D0,D1}
跳槽->{D0,D3}
……

倒排索引最基本的操作有兩項(xiàng)：一是向索引中加入一個(gè)新文檔硝逢，二是給定一個(gè)由多個(gè)關(guān)鍵詞組成的查詢時(shí)，返回對(duì)應(yīng)的文檔集合。

1.2 向量空間模型

向量空間模型考慮將文檔向量化表示渠鸽，是度量文檔相似度的主要方法之一叫乌，向量空間模型的核心主要有兩點(diǎn)，文檔的表示方法和相似度計(jì)算方法徽缚。這里使用詞袋(bag of words,BoW)假設(shè)憨奸，
對(duì)每個(gè)關(guān)鍵詞，可以采用TF-IDF表示凿试。

TF-IDF = TF*IDF排宰，其中（圖片取自維基百科）

IDF

文檔可以表示為

文檔矢量

采用BoW的文檔表示方法，在計(jì)算兩個(gè)文檔相似度時(shí)那婉，一般采用其對(duì)應(yīng)矢量的余弦距離：

向量的余弦矩陣

基于上述內(nèi)容板甘，可以建立起對(duì)海量文檔進(jìn)行檢索的基本方案。在離線索引階段详炬，對(duì)文檔集合進(jìn)行分詞盐类，并按照BoW模型表示得到每個(gè)文檔的TF-IDF矢量，對(duì)分此后的文檔集合建立倒排索引呛谜。當(dāng)在線查詢到來時(shí)在跳，也進(jìn)行分詞，從倒排索引中查出所有符合要求的文檔候選隐岛，并對(duì)其中的每個(gè)候選評(píng)價(jià)其與查詢的與仙居路猫妙，按距離由小到大進(jìn)行排序。

2. 最優(yōu)化方法

比上面的向量空間模型更加有效的計(jì)算廣告方案聚凹，一般就要涉及到與數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)相關(guān)的算法問題割坠，這一類都可以歸為最優(yōu)化問題。

最優(yōu)化問題討論的是元践，給定某個(gè)確定的目標(biāo)函數(shù)韭脊，以及該函數(shù)自變量的一些約束條件，求解該函數(shù)的最大或最小值的問題单旁，這樣的問題可以表示為下面的一般形式：

最優(yōu)化問題的一般形式

其中f(x)是關(guān)于自變量的目標(biāo)函數(shù)，而g(x)和h(x)為x的矢量函數(shù)饥伊。對(duì)應(yīng)著一組不等式和等式約束約束條件象浑。

根據(jù)約束條件以及目標(biāo)函數(shù)的性質(zhì)不同，最優(yōu)化問題求解的思路也有很大的不同琅豆。其中無約束優(yōu)化問題的方法是基礎(chǔ)愉豺，而帶約束優(yōu)化問題則在一定條件下可以轉(zhuǎn)化為無約束優(yōu)化問題來求解，以下對(duì)優(yōu)化方法進(jìn)行一個(gè)梳理茫因。（涉及方法較多蚪拦，這里不詳細(xì)展開）

帶約束優(yōu)化方法
- 拉格朗日法和凸優(yōu)化
無約束優(yōu)化方法
- 不可導(dǎo)或代價(jià)極大
  - 下降單純形法（又稱阿米巴變形蟲法）
- 可導(dǎo)
  - 梯度下降法
    - 批梯度下降
    - 隨機(jī)梯度下降
    - 動(dòng)量Momentum
    - AdaGrad
擬牛頓法（快速最優(yōu)化）

3. 統(tǒng)計(jì)機(jī)器學(xué)習(xí)

這里很抱歉關(guān)于最大熵和EM算法筆者并沒有看得太懂，以后有時(shí)間會(huì)補(bǔ)齊這個(gè)部分。

3.1 最大熵與指數(shù)族分布

最大熵原理：在某些約束條件下選擇統(tǒng)計(jì)模型時(shí)驰贷，盡可能選擇滿足這些條件的模型中不確定性最大的那個(gè)盛嘿。

3.2 混合模型和EM算法

EM算法是為了解決有隱變量存在時(shí)的最大似然估計(jì)問題的，每個(gè)迭代可以分為E-step和M-step：在E-step階段括袒，我們將參數(shù)變量和觀測變量都固定次兆，得到隱變量的后驗(yàn)分布；而在M-step階段锹锰，我們將用得到的隱變量的后驗(yàn)分布和觀測變量再去更新參數(shù)變量芥炭。

4.統(tǒng)計(jì)模型分布式優(yōu)化框架

略

5.深度學(xué)習(xí)

深度神經(jīng)網(wǎng)絡(luò)并不是近年才有的新模型，要讓復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)發(fā)揮優(yōu)勢恃慧，一定要有大量的數(shù)據(jù)才行园蝠。目前開源的神經(jīng)網(wǎng)絡(luò)工具軟件主要有tensorflow、caffe痢士、mxnet等砰琢。

5.1 MLP（多層感知機(jī)）

MLP多層感知機(jī)示意圖

輸入層的每一個(gè)節(jié)點(diǎn)代表一個(gè)已知的輸入變量，在隱藏層中良瞧，每個(gè)節(jié)點(diǎn)接受前一級(jí)的輸入陪汽，通過一個(gè)神經(jīng)元的非線性變換（稱為激活函數(shù)），將其映射為一個(gè)新變量褥蚯，經(jīng)過多層的映射后挚冤，輸出層負(fù)責(zé)將最后一個(gè)隱藏層的變量加工為最終的輸出變量，輸出變量有可能是一個(gè)赞庶，也可能是多個(gè)训挡。

5.2 卷積神經(jīng)網(wǎng)絡(luò)（CNN）

卷積層

卷積神經(jīng)網(wǎng)絡(luò)是一種常見的深度神經(jīng)網(wǎng)絡(luò)，主要用于圖像處理領(lǐng)域歧强。

圖像處理主要有兩個(gè)特點(diǎn)：

局部感知澜薄。在圖像上提取編譯、發(fā)現(xiàn)物品等操作摊册，往往只需要聚焦在圖上的一個(gè)局部范圍中肤京。
參數(shù)共享。視覺元素的特征與位置無關(guān)茅特，因此忘分，在同一層中的不同神經(jīng)元，可以共享一樣的輸入變量的權(quán)重白修。

卷積神經(jīng)網(wǎng)絡(luò)交替采用采樣和卷積對(duì)原圖像進(jìn)行變換妒峦，從而獲得越來越抽象的圖像理解能力。假設(shè)最后的輸出矢量為兵睛，

image.png

其softmax映射結(jié)果可以表示為：

image.png

神經(jīng)網(wǎng)絡(luò)整體優(yōu)化的損失函數(shù)為：

image.png

5.3 循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）：

循環(huán)神經(jīng)網(wǎng)絡(luò)主要用于處理時(shí)間序列數(shù)據(jù)的建模肯骇，典型例子是語音識(shí)別和機(jī)器翻譯窥浪。

下面是RNN的網(wǎng)絡(luò)結(jié)構(gòu)

循環(huán)神經(jīng)網(wǎng)絡(luò)

可以看出，RNN在每個(gè)t時(shí)刻的局部結(jié)構(gòu)是遞歸重復(fù)的笛丙、為了便于表達(dá)漾脂，也可以將其表達(dá)為圖左側(cè)的形式，其中的黑色方塊表示該條邊是到下一個(gè)時(shí)間單元相應(yīng)位置的輸入若债。在每一個(gè)時(shí)刻符相，其更新公式為：

image.png

由于RNN自身的特性，有時(shí)會(huì)導(dǎo)致反向傳播的梯度過大也有可能會(huì)導(dǎo)致梯度極小蠢琳，這會(huì)導(dǎo)致優(yōu)化識(shí)別啊终，因此為了解決這些問題，推出了長短時(shí)記憶LSTM以及GRU傲须。

5.4 生成對(duì)抗網(wǎng)絡(luò)（GAN）：

生成對(duì)抗網(wǎng)絡(luò)GAN

一般來說蓝牲，雖然發(fā)生擾動(dòng)但人眼可能識(shí)別不出來會(huì)導(dǎo)致誤分類的樣本稱為對(duì)抗樣本，利用這種樣本可以得到對(duì)抗網(wǎng)絡(luò)泰讽，模型既訓(xùn)練正常的樣本也訓(xùn)練這種自己造的對(duì)抗樣本例衍，從而改進(jìn)模型的泛化能力。

對(duì)抗網(wǎng)絡(luò)通常包含一個(gè)生成模型G和一個(gè)判別模型D已卸，生成模型用噪聲數(shù)據(jù)生成一個(gè)類似真實(shí)訓(xùn)練數(shù)據(jù)的樣本佛玄，追求效果是盡可能像真實(shí)樣本，D是一個(gè)二分類器累澡，估計(jì)一個(gè)樣本來自訓(xùn)練數(shù)據(jù)（而非生成數(shù)據(jù)）的概率梦抢。

訓(xùn)練時(shí)，通過固定一個(gè)模型的參數(shù)愧哟，更新另一個(gè)模型的參數(shù)奥吩，交替迭代，使對(duì)方的錯(cuò)誤最大化蕊梧。最后的目標(biāo)是使G能準(zhǔn)確描述出樣本數(shù)據(jù)的分布霞赫。

章節(jié)相關(guān)名詞

VSM 向量空間模型 vector space model
BoW 詞袋 bag of words
CNN 卷積神經(jīng)網(wǎng)絡(luò) Convolutional Neural Network
RNN 遞歸神經(jīng)網(wǎng)絡(luò) Recursive Neural Network
GAN 生成對(duì)抗網(wǎng)絡(luò) Generative Adversarial Net
IR 信息檢索 Information Retrieval