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

文章來源：https://zhuanlan.zhihu.com/p/161058660

嵌入與Hash Trick

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

在高維特征情況下（如ID類特征、單詞特征、數量可能高達千萬級甚至上億），上述編碼方式在接入深度學習網絡（如DNN）存下以下問題：

• 上述編碼方式生成的Vector，其長度為總特征數，接入全連接層存在參數爆炸的問題。

• 通常一個樣本對應的特征數量有限，遠遠小于總特征數。特征稀疏，每次更新只有極極極少數權重更新->網絡收斂非常慢，有限樣本情況下訓練不充分。

• 上述編碼方式，特征之間的關系始終保持獨立，“非此即彼”，無法挖掘特征間的相似性。

嵌入技術是將一個數學結構經映射包含到另一個結構中。嵌入技術有以下幾點好處：

• 高維結構，低維表示

• 蘊含信息豐富

• 存儲較傳統編碼方式大大減少

• 可直接對接神經網絡訓練

特征嵌入技術是將特征用一個低維的向量來表示。對于給定一個特征ID，我們可以通過查表的方式獲得這個特征的向量表達。由此構建了一個|V|*dim的Embedding Matrix，|V|表示總特征數，dim表示向量的維度。

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

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

• 從減少特征維度來講，通過人工剔除無用特征（如詞匯中去除停用詞、罕見詞），或者根據entropy或topK去詞/保留詞。這種裁剪的方法效果因人而異，比較繁瑣。

• 從壓縮特征來講，可以用Hash Trick。

Hash Trick是將原始的unique ID映射在一個[0,B]區間的一個數，?而B<<|V|從而達到降低計算參數和內存的目的。

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

Hash沖突理論

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

接下來給出哈希沖突理論和實驗以及對應結論。

• Hash沖突理論

定義哈希函數 ?

碰撞概率 ? ?表示一個待哈希對象經過哈希之后與其他對象發生碰撞的概率 ?

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

則發生碰撞的個數理論值為 ?

當使用 ? ?個不同的哈希函數，則多哈希映射會擴大 ?

，則碰撞概率變為 ?

• Hash沖突簡單實驗

數據集是利用Xorshift偽隨機算法生成reps個uint64位隨機數，再通過比特位翻轉構造隨機數據，構造三個不同量級的數據集，簡單實驗后結果如下：

• Hash沖突結論

無壓縮情況下，碰撞概率值均在0.63左右，這與理論值相當。

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

但因內存受限，不能一味增加B，且后續embedding matrix 的大小 為 ?，即網絡需要訓練 ? ?個參數；

增加k會大幅度減小碰撞概率，可以看到當k=3時壓縮10倍、壓縮100倍在10^6 以上量級中實驗不存在碰撞情況（理論值也巨小）。但是k的增加使得網絡參數計算速度變慢。

結論1：采用2個哈希函數就可以大幅度地減小碰撞；

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

Sign Hash

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

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

針對中文搜索短語的分詞編碼

Hash2Vec

https://arxiv.org/abs/1608.08940

隨機編碼

原先一個特征只有一個特征id，現在一個特征對應6個特征id，任意兩個特征中最多允許有3個1重疊。

掛靠編碼

Hash Embedding

一個特征由K個id對應的embedding加權求和表示，具體權重參數是通過神經網絡訓練得到。

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

小結

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統計學習方法》的代碼復現專輯 AI基礎下載機器學習的數學基礎專輯獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/662nyZF本站qq群1003271085。加入微信群請掃碼進群（如果是博士或者準備讀博士請說明）：

總結

以上是生活随笔為你收集整理的⾼维特征的哈希技巧总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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