如何用通俗的語言解釋CTR和推薦系統中常用的Feature Hashing技術以及其對應的優缺點？

01-13

附：為什麼Feature Hashing不會大幅損失特徵信息？

謝邀

先回答附的問題：如果hash的目標空間足夠大，並且hash函數本身足夠散列，不會損失什麼特徵信息。

feature hashing簡單來說和kernal的思想是類似的，就是把輸入的特徵映射到一個具有一些我們期望的較好性質的空間上去。在feature hasing這個情況下我們希望目標的空間具有如下的性質：

與樣本無關的維度大小，因為當在線學習，或者數據量非常大，提前對數據觀察開銷非常大的時候，這可以使得我們能夠提前給演算法分配存儲和切分pattern。大大提高演算法的工程友好性。
這個空間一般來說比輸入的特徵空間維度小很多。
另外我們假設在原始的特徵空間里，樣本的分布是非常稀疏的，只有很少一部分子空間是被取值的。
保持內積的無偏（不變肯定是不可能的，因為空間變小了），否則很多機器學習方法就沒法用了。

假設輸入特徵是一個N維的0/1取值的向量x。

那麼在這種情況下，這裡又有很多種構造feature hasing的方法。一種方法是簡單取

一個N-&>M的哈希函數h。

那麼 $phi_j=sum_{h(i)=j}{x_i}$

其實就是比如x的第i個元素為1，並且h(i)=j，那麼變換後的向量第j個元素加1，以此類推。有時為了讓這個函數有一些好的性質，還會再套個哈希函數進行修正等等。

那麼feature hasing的好處和壞處都是比較明顯的：

好處

從某種程度上來講，使得訓練樣本的特徵在對應空間里的分布更均勻了。這個好處對於實際訓練過程是非常大的，某種程度上起到了shuffle的作用
特徵的空間變小了，而且是一個可以預測的大小。比如說加入輸入特徵里有個東西叫做user_id，那麼顯然你也不知道到底有多少userid的話，你需要先掃描一遍並且分配足夠的空間給到它不然學著學著oom了。你也不能很好地提前優化分片。
對在線學習非常友好。

壞處

會給debug增加困難，為了debug你要保存記錄h計算的過程數據，否則如果某個特徵有毛病，你怎麼知道到底是哪個原始特徵呢？
沒選好哈希函數的話，可能會造成碰撞，如果原始特徵很稠密並且碰撞很嚴重，那可能會帶來壞的訓練效果。

感謝評論區提醒，CTR的特徵往往是高維稀疏的特徵，自然語言處理領域的n詞短語（ngram）也是高維稀疏的。所以我從ngram的背景來講解一下特徵哈希吧，與CTR中對特徵哈希的應用應該是吻合的。

一段話總結，特徵哈希就是將高維稀疏的解空間壓縮到低維稠密的空間。壓縮到的維度越低，越容易發生碰撞，此時可通過使用多個哈希函數維護多張哈希表來減少碰撞造成的信息損失。啰嗦的講解如下：

0. 背景知識

首先，詞向量（word vector/embedding）的概念就不啰嗦啦，簡單說就是用一個低維實向量來表示單詞，這也是現代NLP方法的基石。

基於詞向量，可以使用神經網路進而得到短語向量表示，進而得到整個文本的向量表示。這個向量就可以看作是這段文本的特徵向量，基於這個特徵向量，我們就可以後接全連接神經網路等分類器來完成文本分類任務。完成文本表示的方法有很多，最簡單和最好理解的就是基於卷積神經網路（CNN）的方法。

由於文本（比如說句子）中的每個單詞都是一個向量，那麼整個句子就是一個矩陣：

在基於CNN的方法中，我們設置好卷積核的尺寸和數量後，通過卷積操作可以得到各個短語的向量表示。比如卷積核的尺寸設置為2（如上圖，默認寬度為詞向量維度，即矩陣寬度，2為高度），那麼可以得到短語"wait for"，「do n"t「等短語的表示。進而通過池化策略得到整個文本的表示進而分類。

試想，當我們將一個卷積神經網路訓練完成後，這時各個短語的向量表示也都是確定的了（在不同的句子中對「wait」和「for」進行卷積操作一定得到相同的向量表示），因此我們其實沒有必要再一次次的去干這種卷積詞向量的體力活，因此不妨將已經計算過的各個短語的向量表示直接存儲下來，在一段新的文本中就直接取出來用就好啦，可以大大提升計算效率。

1. 短語向量的存儲方案-標號組合 vs 哈希映射

假如在我們的訓練集中，詞典大小是V=1萬，2詞短語的數量是50萬。我們要求為短語向量存儲完畢後，取出任何一個短語向量的時間複雜度為O(1)。

一個很自然的想法是基於詞向量字典的標號的組合：例如"wait"的標號是2，"for「的標號是6，那麼短語」wait for「的標號就是」(2,6)「。顯然這樣的話，我們就要預先為每一個可能的2詞短語的標號來開闢存儲空間。

那麼2詞短語的標號的理論數量是多少呢？當然就是 $V^2$ =1億。3詞短語的呢？當然就是 $V^3$ =1萬億。也就是說，將每個n詞短語看作特徵的話，那麼全部的n詞短語表示成向量就是一個極度高維的。顯然這個「標號組合」的思路的空間複雜度太可啪了，去哪裡搬這麼多內存條呢。

我們想，既然辭彙表是1萬，但是語料庫中的2詞短語只有50萬，說明標號組合方案中的短語向量還是高度稀疏的（大部分隨便組合的短語比如」is was"幾乎不可能出現）因此一個很明智的做法就是建立一個規模可接受的哈希表。比如我們建立一個規模為100萬的哈希表（這樣規模一下子比傳統存儲思路減小了兩個數量級）。這時，我們將遇到過的2詞短語的向量表示都通過哈希函數映射到這個表裡，而沒有遇到過的哈希函數則不考慮。顯然，這樣就達到了空間複雜度可接受而且元素讀取複雜度為O(1)的要求。這就是該應用場景下的Feature hashing。

2. 特徵哈希的缺點與緩解方法

優點上面已經說過了，即在特徵讀取複雜度要求為O(1)的情況下，大大降低空間複雜度。

缺點也很容易想到，那就是哈希表裡的碰撞問題。在短語向量的特徵哈希問題上，其實碰撞問題也不嚴重，因為哪怕是在語料庫中出現過的2詞短語，其中的大部分也是沒有意義的，例如句子「I am a lovely girl"中，"lovely girl"確實是個很有信息量的短語，但是"a lovely「, "am a", "I am"的短語語義大部分情況下並沒有多少信息量，因此哈希表中哪怕發生了碰撞，那麼撞掉的大部分也是這些本身就沒有多少意義的短語，掉就掉了吧 =,= 。

但是，完美主義者的我們怎麼能這麼沒追求呢。萬一兩個很有信息量的短語撞了呢？所以，一個想法是 @周開拓的回答中提到的要用好的哈希函數，但是比如我們這個任務下，很難理性的去決定哪個函數更優哪個更差，因此一個工程上更靠譜的方法是選用多個哈希函數維護多張哈希表，然後讀取時對這多張哈希表取出的向量取均值或者中值。這樣在一個哈希表中該元素髮生碰撞的情況下，其他哈希表可以力挽狂瀾的和諧掉這個碰撞。

如果碰撞都被和諧掉了，那麼當然沒有任何信息損失啦（回應題主的附）。在本文基於的任務場景中，碰撞掉的大概率也是信息量不大的特徵，因此也不會有明顯的信息量損失。當然，如果你的哈希表的規模取得過小，比如語料庫里有50萬特徵，然而你的哈希表只有5萬大小，那顯然信息量的損失是極大的。

因此一般來說，哈希表規模選好，並且使用多個哈希函數維護多張哈希表，信息損失問題就可以忽略了。

在CTR預估中，一種做法是採用人工來做feature engineering，將一些非線性的feature轉換為線性的feature，然後餵給LR之類的線性model來做在線學習，在這個過程中，對於一些categorical feature，比如user_id，advertisement_id，直接做one-hot encoding（一般還會對feature做笛卡爾積）會導致維度爆炸，hashing trick通過對feature先做hash之後取模降低維度，緩減這一問題。

具體來說：假設原始特徵向量 $xin R^{N}$ ，我們希望將他降為 $M$ 維( $M$ &<&< $N$ )，定義一個hash function $h:N ightarrow left { 1,...,m ight }$ ，一般為了保證內積的無偏，會再定義一個hash function $xi :N ightarrow left { pm 1 ight }$ ，最終對於 $x$ 有：

$phi _{i}^{(h,xi )}left ( x ight )=sum_{j:h(j)=i)}xi (j)x_{j}$

$and$ $left langle x,{x}$

其實在做feature hashing的時候，很少會直接去寫哈希函數，現有的package裡面都定好了哈希函數的，可以調的參數基本就是最終的維度 $M$ ，一般為了將特徵均勻的映射到列上，需要使用2的冪作為參數，然後再看模型評價指標來確定最終的值。

優點：

1.相比較與one-hot encoding，不需要預先維護一個變數表。

2.在線學習方便，在模型訓練的時間和空間複雜度上降低。

缺點：

1.hash衝突，一般來說這個影響不會很大，很多實驗表明並不太會影響模型的精度。個人覺得這可能是產生衝突的那些值本身就比較「相似」，所以才對精度影響不大。

2.失去了feature的解釋性，沒有辦法從hash之後的向量找到原始的feature。

最後分享一些自己看過覺得比較好的相關資料吧：

Feature Hashing for Large Scale Multitask Learning https://alex.smola.org/papers/2009/Weinbergeretal09.pdf

Collaborative Email-Spam Filtering with the Hashing-Trick http://www.cs.cornell.edu/~kilian/papers/ceas2009-paper-11.pdf

Feature Engineering - Getting most out of data for predictive models - TDC 2017 from Gabriel Moreira

個人見解：

一般而言這類技術是為了解決兩個問題：一是將categorical的特徵編碼為模型可理解的格式，二是儘可能在保留有效信息的基礎上降低訓練和預測過程的時間複雜度。
以上兩個問題中，一是基礎問題。One-Hot Serializing就可以達到這個效果，例如將訓練樣本中出現過的的每個deviceid按順序遞增編號（比如deviceid@xxx:1 -&> feature@10000:1）。缺點是：1）這個映射表需要傳遞給引擎端，在prediction的時候照著再查一遍，數據量大且數據結構設計不好的時候很費時間；2）有些頻次很低的特徵置信度不高，單獨出現對模型無益（甚至over-fitting）。這時候可以使用按頻次截斷技術進行降維。比如微軟在deep crossing中提到的特徵工程方法：只保留曝光最多的10k個campaign id編碼為0-9999，其餘的id全部編碼為10000，但輔以poCTR等連續特徵作為輔助。事實上這是一種手工的Hashing方法。
自動Hashing方法的好處是：只要訓練和預測時使用的hashing方法一致，對同一個特徵的編碼結果即一致，因此引擎預測或提供數據dump的時候無需查找編碼表。所以其最大優點在於數據一致性和速度提升，這在極大規模特徵和在線學習中至關重要。
我們說的Hashing演算法一般而言均特意設計為低碰撞率。因此一般hashing演算法本身不會大幅降低特徵維度，自然也不會大幅損失特徵信息。真正可能存在問題的是hashing之後的降維過程。一個非常常見的陷阱是string哈希到int64後取模m，試圖將特徵壓縮至m維one-hot空間。在這種情況下，對於不知情的隨機hashing過程，不同特徵的碰撞率為1/m。舉個例子，對於「性別」特徵，將male哈希為一個int64，female哈希為另一個int64，很難發生碰撞；但如果你試圖使用mod2將其壓縮，如果你的演算法哈希出的這兩個int64奇偶性相同，則會導致特徵失效。在你有很多feature需要哈希而又不清楚hashing演算法細節的情況下，這在概率意義上是很容易發生的。
因此我們會更傾向於所謂的embedding演算法，例如將70萬維的userid通過weight embedding到32維的連續值特徵上（不同於傳統hashing的低維離散值特徵）。這意味著訓練過程更加複雜（有更多的weight需要optimize）；但對於預測過程，其特徵性能十分良好且時間複雜度得以降低。同時，由於連續值特徵空間的表達能力大幅高於離散值特徵空間，整個模型的表達能力並不會明顯下降，也基本不會發生離散hashing的碰撞問題。（當然，如果是FM這類傾向於接受離散值的模型，手工serializing+精心設計的hashing是較好的選擇。）

總結：

優點（相對於One-hot Serialization）：

訓練和預測的時間複雜度大幅降低；
數據的一致性強，不存在同一個特徵今天編碼成這個、明天編碼成那個的情況，便於跟蹤單特徵效果；
對new feature可以直接編碼並加入訓練，無需等待編碼表統計並反饋；
降低feature space大小，（精心設計可以）降低over-fitting的幾率。

缺點：

在不清楚hashing function細節的情況下，容易導致特徵碰撞失效，且難以排查；
難以通過hashing出的特徵反推源特徵；
embedding會降低模型的可解釋性。

抱歉…我真的不懂…幫頂吧，hhh