?維特征的哈希技巧總結(jié)

“?本文首先介紹嵌入技術(shù)，引出Hash Trick；其次分析就Hash沖突給出理論和實(shí)驗(yàn)證明，給出一個(gè)減少?zèng)_突的方案；接著就具體的場(chǎng)景給出減少特征Hash沖突或者在有限的參數(shù)空間內(nèi)盡可能地表示高維特征的技巧；最后給出簡(jiǎn)單結(jié)論。”

文章來(lái)源：https://zhuanlan.zhihu.com/p/161058660

嵌入與Hash Trick

在嵌入技術(shù)（Embedding）被廣泛使用前，常用的特征編碼方式有One-Hot Encoding和CountVectorizer：

在高維特征情況下（如ID類特征、單詞特征、數(shù)量可能高達(dá)千萬(wàn)級(jí)甚至上億），上述編碼方式在接入深度學(xué)習(xí)網(wǎng)絡(luò)（如DNN）存下以下問(wèn)題：

• 上述編碼方式生成的Vector，其長(zhǎng)度為總特征數(shù)，接入全連接層存在參數(shù)爆炸的問(wèn)題。
• 通常一個(gè)樣本對(duì)應(yīng)的特征數(shù)量有限，遠(yuǎn)遠(yuǎn)小于總特征數(shù)。特征稀疏，每次更新只有極極極少數(shù)權(quán)重更新->網(wǎng)絡(luò)收斂非常慢，有限樣本情況下訓(xùn)練不充分。
• 上述編碼方式，特征之間的關(guān)系始終保持獨(dú)立，“非此即彼”，無(wú)法挖掘特征間的相似性。

嵌入技術(shù)是將一個(gè)數(shù)學(xué)結(jié)構(gòu)經(jīng)映射包含到另一個(gè)結(jié)構(gòu)中。嵌入技術(shù)有以下幾點(diǎn)好處：

• 高維結(jié)構(gòu)，低維表示
• 蘊(yùn)含信息豐富
• 存儲(chǔ)較傳統(tǒng)編碼方式大大減少
• 可直接對(duì)接神經(jīng)網(wǎng)絡(luò)訓(xùn)練

特征嵌入技術(shù)是將特征用一個(gè)低維的向量來(lái)表示。對(duì)于給定一個(gè)特征ID，我們可以通過(guò)查表的方式獲得這個(gè)特征的向量表達(dá)。由此構(gòu)建了一個(gè)|V|*dim的Embedding Matrix，|V|表示總特征數(shù)，dim表示向量的維度。

特征數(shù)量(詞匯、ID)龐?導(dǎo)致模型需要訓(xùn)練的參數(shù)非常多，通常Embedding參數(shù)占據(jù)所有參數(shù)的90%以上。

為了較少參數(shù)量，可以有以下幾種方案：

• 從減少特征維度來(lái)講，通過(guò)人工剔除無(wú)用特征（如詞匯中去除停用詞、罕見詞），或者根據(jù)entropy或topK去詞/保留詞。這種裁剪的方法效果因人而異，比較繁瑣。
• 從壓縮特征來(lái)講，可以用Hash Trick。

Hash Trick是將原始的unique ID映射在一個(gè)[0,B]區(qū)間的一個(gè)數(shù)，?而B<<|V|從而達(dá)到降低計(jì)算參數(shù)和內(nèi)存的目的。

對(duì)于任意?個(gè)特征，我們用Hash函數(shù)找到對(duì)應(yīng)哈希表的位置，然后將該特征對(duì)應(yīng)的值(為?便可以理解為word對(duì)應(yīng)的詞頻)累加到該哈希表位置。

Hash沖突理論

有損壓縮必存在特征沖突。所謂特征hash沖突，即兩個(gè)不同的特征經(jīng)映射后得相同的特征id，進(jìn)而得到相同的嵌入向量。

接下來(lái)給出哈希沖突理論和實(shí)驗(yàn)以及對(duì)應(yīng)結(jié)論。

• Hash沖突理論

定義哈希函數(shù) ?

碰撞概率 ? ?表示一個(gè)待哈希對(duì)象經(jīng)過(guò)哈希之后與其他對(duì)象發(fā)生碰撞的概率 ?

對(duì)于大的壓縮值B，我們可以做以下的近似 ?

則發(fā)生碰撞的個(gè)數(shù)理論值為 ?

當(dāng)使用 ? ?個(gè)不同的哈希函數(shù)，則多哈希映射會(huì)擴(kuò)大 ?

• Hash沖突簡(jiǎn)單實(shí)驗(yàn)

數(shù)據(jù)集是利用Xorshift偽隨機(jī)算法生成reps個(gè)uint64位隨機(jī)數(shù)，再通過(guò)比特位翻轉(zhuǎn)構(gòu)造隨機(jī)數(shù)據(jù)，構(gòu)造三個(gè)不同量級(jí)的數(shù)據(jù)集，簡(jiǎn)單實(shí)驗(yàn)后結(jié)果如下：

• Hash沖突結(jié)論

無(wú)壓縮情況下，碰撞概率值均在0.63左右，這與理論值相當(dāng)。

為了降低碰撞沖突，有兩種解決方法，一種是增大B，還有一種是增大k。

但因內(nèi)存受限，不能一味增加B，且后續(xù)embedding matrix 的大小 為 ?，即網(wǎng)絡(luò)需要訓(xùn)練 ? ?個(gè)參數(shù)；

增加k會(huì)大幅度減小碰撞概率，可以看到當(dāng)k=3時(shí)壓縮10倍、壓縮100倍在10^6 以上量級(jí)中實(shí)驗(yàn)不存在碰撞情況（理論值也巨小）。但是k的增加使得網(wǎng)絡(luò)參數(shù)計(jì)算速度變慢。

結(jié)論1：采用2個(gè)哈希函數(shù)就可以大幅度地減小碰撞；

結(jié)論2：特征空間的大小在一定程度上可以指導(dǎo)B的選取，（如百萬(wàn)量級(jí)特征中，100倍壓縮的碰撞率在1%左右，而千萬(wàn)量級(jí)中，100倍壓縮碰撞率為0.04%）。

Sign Hash

使用原始的Hash Trick存在?個(gè)問(wèn)題，有可能兩個(gè)原始特征的哈希后位置在一起導(dǎo)致詞頻累加特征值突然變?，為解決這個(gè)問(wèn)題，ICML’09 提出hash Trick的變種signed hash trick，即除了原始的均勻哈希函數(shù)外，再增加了一個(gè)Binary Hash Function，來(lái)消除原始hash kernel的偏估計(jì)。

https://arxiv.org/pdf/0902.2206.pdf

Word Hash

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/cikm2013_DSSM_fullversion.pdf

Char-ngrams + hash

https://arxiv.org/abs/1607.04606

針對(duì)中文搜索短語(yǔ)的分詞編碼

Hash2Vec

https://arxiv.org/abs/1608.08940

隨機(jī)編碼

原先一個(gè)特征只有一個(gè)特征id，現(xiàn)在一個(gè)特征對(duì)應(yīng)6個(gè)特征id，任意兩個(gè)特征中最多允許有3個(gè)1重疊。

掛靠編碼

Hash Embedding

一個(gè)特征由K個(gè)id對(duì)應(yīng)的embedding加權(quán)求和表示，具體權(quán)重參數(shù)是通過(guò)神經(jīng)網(wǎng)絡(luò)訓(xùn)練得到。

https://github.com/YannDubs/Hash-Embeddingshttps://github.com/dsv77/hashembeddinghttps://papers.nips.cc/paper/7078-hash-embeddings-for-efficient-word-representations.pdf

小結(jié)