文章：LIME：Why Should I Trust You?

本文結合文章 “Why Should I Trust You?” Explaining the Predictions of Any Classifier 主要闡述一下内容：

1. LIME 算法意義
2. LIME 算法原理
3. LIME 算法效果

原文參見：https://arxiv.org/pdf/1602.04938v1.pdf

一、LIME 算法意義

LIME 是解釋模型的算法，目的為了解模型的預測原理。是以 LIME 算法意義即為解釋模型的意義。

1. 信任模型及其預測結果

信任問題涉及到兩個方面：1. 信任模型，2. 信任預測結果。我們可以通過驗證集來評估模型整體的預測精度，但卻無法判定模型對測試集中特定樣本的預測是否準确。而在如醫療診斷等許多領域中，誤判所帶來的風險太大，隻知道模型的預測精度是不足夠的，從業者還需要知道每次預測的判據是什麼，來分析預測結果是否可靠。是以即使模型預測準确率達到95%，許多領域的從業者也是不敢使用的。是以，解釋模型可以令使用者信任模型及其預測結果，有助于算法、模型的推廣。

2. 提高判斷模型優劣的準确性

一方面，由于諸多因素限制，訓練集、驗證集、測試集往往都是有偏的，但卻難以被察覺。另一方面，訓練集與驗證集、測試集之間可能存在一定程度的無意的資料洩露，即驗證集、測試集中包含一部分訓練集。是以在驗證集和測試集上效果良好的模型未必在實際應用中也效果良好。同時，由于模型中計算和優化的名額（如準确性）與實際關注的名額之間可能是不比對的。是以，僅通過預測精度來判斷模型的優劣是不充分的，還需要了解模型的預測原理，根據先驗知識，選擇在實際應用中可能效果更優的模型。

例1：下圖展示了用 LIME 算法對不同模型預測同一樣本的結果的分析。兩個模型均是由 SVM 算法在 20 個新聞討論區資料集上做訓練得到的分類器，用于區分文章主題是 “基督教” 還是 “無神論” 。條形圖的長短表示特征（單詞）對預測結果的貢獻，越長說明貢獻越大；顔色表明了特征對預測結果類别的貢獻，紫紅色表明該單詞的出現有助于模型預測文章的主題是 “無神論”，而綠色則表明 “基督教”。

Algorithm 2 模型在測試集上的準确度為 94%，而 Algorithm 1 的準确度較低。如果隻以準确度作為評判模型優劣的标準，那麼 A2 優于 A1。但我們在知曉模型的預測原理後發現，A2 中對預測有幫助的特征都是與 “基督教” 或 “無神論” 無關的詞，如 Posting，Host，Re。經研究發現，訓練集中有 22% 的樣本包含 Posting，而其中 99% 是 “無神論” 标簽，是以 A2 學到了特征 Posting。相對的，A1 則找到的最重要的單詞是 GOD，這使得使用者更願意相信低精度的 A1 在實際中會有更好的表現。從本例中可以看出，通過對模型預測結果的分析，不僅可以選擇出更優秀的模型，同時能發現訓練集是有偏的。

3. 提高模型預測精度

對于如預測植物株高、産量等這類預測任務，由于經費問題，生物學資料面臨着魚和熊掌不可兼得的問題：資料多樣性與排除無關變量無法兼得。若測定的樣本集中于一個群體，則變量控制的好，無種群結構，但訓練出來模型的遷移能力差，難以預測其他群體樣本的表型；若測定的樣本集多樣性高，如以種質庫作為訓練集，則訓練出來的模型遷移能力強，但由于無法排除無關變量，預測精度不高且找到的可能是與群體結構相關的SNP位點。是以需要研究者通過先驗知識手動去除被模型重用的無關變量，重新訓練，提高模型的預測精度。

4. 挖掘重要特征，研究現象形成的内在原因

二、LIME 算法原理

LIME 全稱 Local Interpretable Model-Agnostic Explanations，是以使用者可了解（Interpretable）的方式解釋（Explanations）任何類型（Model-Agnostic）的模型的預測結果（Local）的算法。可以發現，LIME 算法隻提到了如何解釋模型的預測結果，而沒有提及如何解釋模型。作者通過次模采樣的方法，以樣本代表總體的思路，完成對模型整體的解釋。下面分别對 LIME 的可了解、模型無關、局部吻合和次模采樣進行介紹。

1. 可了解（Interpretable）

首先，對模型預測結果的解釋能被人們所了解。由于人類了解能力有限，LIME 通過以下 4 個方面達到模型及預測結果可被了解的目的

1. 模型足夠簡單，如線性模型，各項之間是加性關系，每項的重要性以權重展現，易于了解。
2. 特征足夠簡單。無論特征在模型中如何被使用，如詞嵌入，LIME 隻用 “存在” 或 “不存在” 表示特征并解釋預測結果。若樣本 x 在原模型中的值域為 x ∈ Rd，則在 LIME 算法建構出的新模型中 x′ ∈ {0,1}d′。其中 d、d′ 表示次元，x ∈ Rd 表示 x 是 d 維向量，各次元的值域為實數 R，x′ ∈ {0,1}d′ 表示 x′ 是 d′ 維向量，各次元的值域為 {0,1}。注意，由于模型 f 内部對特征的利用未必是人們容易了解的特征，而 LIME 使用人們友善了解的形式來解釋預測結果，是以 d 可能 ≠ d′。如處理文本時，f 使用詞嵌入加工輸入特征進行預測，d = 詞嵌入的次元，而 LIME 對預測結果進行解釋時，使用的是文章中包含哪些單詞，d′ = 訓練集中總單詞數（相同單詞隻計數一次），參見 fig 1。
3. 特征數足夠少，特征之間的關系足夠簡單。假設預測結果由100個特征所構成，部分特征之間還存在相關性，建構出來的線性模型有幾百項，那麼對于使用者來說也是難以了解的。是以 LIME 隻解釋決定樣本預測結果的 K 個重要特征，非重要特征不予呈現。
4. 樣本數足夠少。LIME 算法是用有代表性的樣本來代表總體，使用者通過對有代表性樣本的預測結果的解釋，來判斷模型對這些有代表性樣本的預測是否正确，進而判斷模型是否正确。如果需要分析的樣本過多，無疑會增加使用者的負擔，提高了解模型的難度。是以 LIME 通過次模采樣，隻提供 B 個樣本的預測結果的解釋，其餘樣本不予呈現。

由于人類了解能力有限，或者說人腦算力有限，複雜的基因組、轉錄組、代謝組、蛋白組網絡及他們之間的互動網絡，即使清晰的呈現在人類面前，人類是否能夠加以合理利用？是以我認為，生物組學分析最終必須借用機器的算力來完成。

2. 模型無關（Model-Agnostic）與局部吻合（Local）

LIME 算法可以用于解釋任何機器學習算法所建構出的模型，具體算法如下：

1. 設待解釋的模型為 f，f 的輸入為 x，x ∈ Rd
2. 設 G 為簡單模型集合，簡單模型包含線性回歸、決策樹等，g 為集合 G 中的一個簡單模型，在本論文中 g 均為線性模型，設 g 的權重為 wg，有 g(x) = wg · x
3. 對樣本 xi 建構簡單模型 gi，為使 gi 便于了解，gi 的輸入不再是 xi，而是 x′i，x′i ∈ {0,1}d′，其中 x → x′ 是通過特定的函數完成的映射。令 gi(x′i) 逼近于 f(xi)，進而實作用簡單模型 gi 解釋任何複雜模型 f 對樣本 xi 的預測結果 f(xi)。 由于簡單模型 gi 是針對于特定樣本 xi 所建構出來的，是以 g 是對 f 特定位點的拟合，即 g 是 f 的局部最優拟合而非全局最優。
4. 對 x′i 中非 0 特征随機賦 0，得到新樣本 z′i，将 z′i 重新映射為 zi，得到 f(zi)，視 〈z′i, zi, f(zi)〉 為對 x′i 和 xi 的一次附近采樣，存入集合 Zi 中，如此總共進行 N 次附近采樣。
5. 以集合 Zi 中 z′i 為自變量，f(zi) 為因變量，用 K-Lasso 算法（詳見文末注釋）求解 gi 中的 wgi ，算法的僞代碼見下圖 Algorithm 1。注：K-Lasso 算法有關知識參見 附：K-Lasso 算法簡介。

   

6. 設函數 L(f, gi, πxi) = ∑zi∈Z,z′i∈Z′i πxi(zi) ( f(zi) − g(z′i) )2，其中 g(z′i) = wgi · z′i，( f(zi) − g(z′i) )2 表示用 g(z′i) 拟合 f(zi) 的損失 ，πxi (zi) = exp( −D(xi, zi)2 / σ2 )，D(x, z) 為計算 x，z 之間距離的函數，即πx (z) 表示 x，z 之間的距離并作為 ( f(zi) − g(z′i) )2 的權重，表示距離 x 越近的取樣 z 所對應的損失越重要，是以函數 L(f, gi, πxi) 表示模型 g 在 xi 處對 f 的拟合效果
7. 設函數 ξ(xi) = argmingi∈G L(f, gi, πxi) + Ω(gi)，其中 argmingi∈G L(f, gi, πxi) 表示函數 L(f, gi, πxi) 取最小值時 gi 的值。Ω(gi) 表示模型 g 的複雜度（複雜度越高的模型 g 越難以被人所了解），為函數 L 添加了正則化向，若 ‖wgi‖0 > K，Ω(gi) = ∞，若 ‖wgi‖0 ≤ K，Ω(gi) = ‖wgi‖0，其中 ‖wgi‖0 表示 wgi 的 0 範數（ 0 範數表示向量中非零元素的個數，即為其稀疏度）。LIME 通過令函數 ξ(xi) 最小，實作 g 在精确度與複雜度之間的平衡。

下圖簡單展示了 LIME 用簡單模型 g 拟合複雜模型 f。複雜黑箱模型 f 由藍色/粉紅色背景表示，可以看出用簡單線性模型難以在全局角度很好的拟合 f，是以使用局部拟合。亮紅色的十字表示采樣 xi，暗紅色十字和圓點表示對 xi 進行附近采樣得到的樣本 zi，構成集合 Zi。十字和圓點大小表示 zi 與 xi 的接近程度 πxi ，用于權重。虛線為通過集合 Zi，運用 K-Lasso 算法 拟合出的簡單線性模型 g。

3. 次模采樣（Submodular Pick）

LIME 算法是通過對大量樣本預測結果的解釋，進而判斷整體模型的好壞，即通過大量的局部情況反映總體情況。又由于人的了解能力、時間有限，是以要通過盡可能少的樣本預測，反映盡可能多的模型情況。論文作者通過次模采樣達到上述目的。

次模是指邊際效應遞減，其中邊際效應是指現狀态的效益和前一個狀态的內插補點。次模采樣是指邊際效應遞減的采樣方法：從空集開始，每次都選擇使得邊際收益最大的元素加入集合S。Nemhauser 等人證明了次模采樣能夠達到 (1-1/e) · f(OPT)，其中 OPT 表示該問題的最優集合，1-1/e 約為 63%。在本論文中 OPT 表示最能反映模型整體的樣本集合。可以看出，次模采樣是貪心算法解決 NP-hard 問題的一種應用。

下面說明了 SP-LIME 的具體算法：

1. 設模型 f 的訓練集為 X，使用者在有限的時間、精力下願意通過至多 B 個樣本的預測結果分析來了解模型 f 的整體預測原理。
2. 對 X 中所有樣本的預測結果進行 LIME 算法分析，得到 m × d′ 維的權重矩陣 W，其中 m 表示 X 中的樣本數量。由上一節對 LIME 算法的描述可知，W 的每行中隻有 K 個元素不為 0。
3. 設 Ij 表示特征 j 的全局重要性，Ij 2 = ∑i Wij
4. 設函數 c(V, W, I) = ∑j 1[∃i∈V:Wij>0]Ij 表示采樣得到的樣本的特征覆寫度，其中 V 表示從 X 采樣得到集合， 1[∃i∈V:Wij>0]Ij 表示：若采樣集合 V 裡存在樣本 xi，其預測結果對應的模型 g 中特征 j 的權重 Wij > 0，有 1 · Ij = Ij，認為 V 中包含特征 j；否則為 0 · Ij = 0，認為 V 中不包含特征 j。
5. 通過次模采樣，令每次采樣使得 c(V∪ {i}, W, I) − c(V, W, I) 最大，直至 V 中樣本數等于 B 或 V 覆寫了所有特征時采樣結束，得到集合 V。算法僞代碼見下圖 Algorithm 2。

   

6. 設函數 Pick(W, I) = argmaxV,|V|≤B c(V, W, I)，表示希望通過盡可能少的樣本（≤ B）覆寫盡可能多的特征，反映盡可能完整的模型時的采樣集合 V 所包含的 W、I。

三、LIME 算法效果

1. 對模型預測結果的解釋是否準确？

資料集為書評和影評，兩個資料集各有 2000 條評論，使用決策樹算法（DT）和 L2 正則的線性回歸算法（Sparse LR）分别訓練模型，這兩種算法可以直覺反映模型預測時所依據的特征。用 LIME、parzen、greedy、random 四種算法解釋模型預測時所依據的特征，并模型真正使用的特征作比較，計算準确率，結果如圖 Figure 6、Figure 7。

PS：(i) 所有算法均隻使用 10 個特征解釋預測結果，即 K = 10；(ii) greedy 算法是指通過逐個移除對原模型預測結果影響最大的特征，直至移除特征達到 10 個；(iii) random 算法是指從總特征中随機挑選 10 個用于解釋預測結果；(iiii) 圖中縱坐标為 Recall 指解釋算法得到的 10 個特征中被真正用于原模型預測的比例的平均值。

在不同資料集合不同算法下，LIME 對結果解釋的準确性有一定波動，但都維持在 90% 以上，即 LIME 找到的 10 個特征中有至少 9 個是真實被模型使用的。雖然 90% 的準确率很高，但 需要注意：此例中 LIME 解釋的是如線性模型、決策樹等簡單模型，是以準确率偏高。

上面實驗隻說明了 LIME 找到的特征與模型 f 預測時使用的特征契合度高，但比重 wij 未必正确。為了說明 wij 正确，即在 f 和 g 中對特定樣本的預測結果的貢獻相同，作者通過删除某些共有的特征後觀察 f 與 g 的預測結果是否同時改變來證明。作者設計了如下實驗：在上個實驗的基礎上，從總特征中随機選擇 25% 的特征标記為 “不可靠特征”，其餘特征标記為 “可靠特征”，随機選取 “不可靠特征” 的目的是為了讓模型 f、g 預測任意樣本 xi 時，所用到的特征中都會或多或少的包含一定數量的 “不可靠特征”；然後移除樣本 xi 中所有 “不可靠特征”，若移除後模型 f 的預測結果改變，說明樣本 xi 中的 “不可靠特征” 對預測結果重要，将樣本 xi 标記為 “不可靠樣本”，若結果不變，則樣本 xi 标記為 “可靠樣本”；同理移除 g 中在 f、g 中均出現的 “不可靠特征”，并根據預測結果是否改變對樣本 xi 進行标注；計算 xi 在不同模型 f、g 中标簽的吻合度，結果見下表 Table 1。注意：由于 greedy 算法導緻移除 “不可靠特征” 不會改變預測結果，是以改為出現 “不可靠特征” 即将樣本标注為 “不可靠樣本”。

從結果可以看出，LIME 解釋線性回歸（LR）、近鄰分類（NN）、随機森林（RF）和支援向量機（SVM）四種算法時生成的簡單模型 g 中的權重 W 都是很準确的。雖然 90% 的準确率很高，但 需要注意：此例中 LIME 解釋的都是簡單模型，是以準确率偏高。

2. 用局部代替總體的效果怎樣？

我們知道 SP-LIME 算法是用局部代表總體，是以我們必須了解局部代替總體的效果。如果局部代替總體的效果越好，則通過對不同模型 B 個樣本預測結果的解釋以找到最優模型的機率就越高。作者通過比較不同方法的采樣、解釋下，選擇最優模型的機率來評判局部代替總體的效果。設計實驗如下：

1. 将資料集中 1280 條評論作為訓練集，320 條評論作為驗證集，400 條評論作為測試集。
2. 人工生成 10 個噪音特征，向訓練集和測試集中 10% 的樣本中添加噪音特征，向驗證集中 20% 的樣本中添加噪音特征。
3. 在訓練集上用随機森林算法模組化，生成多組由 30 棵樹構成的随機森林模型，直到找到兩組在驗證集上預測精度差小于 0.1% 、在測試集上預測精度差大于 5% 的模型，這一對模型無法通過準确率判斷模型優劣。
4. 從驗證集中采樣出 B 個樣本并檢視其預測結果的解釋，如果解釋中包含噪音特征，則認為此預測結果不可信。選擇不可信樣本較少的模型作為最優模型，若最優模型在測試集上的預測精度較高，則标記為選擇正确。
5. 重複步驟 2-4 800 次，計算最優模型選擇的正确率，結果見下圖 Figure 8。

   

   從結果中可以看出，LIME 的選擇正确率始終優于 greedy，次模采樣（SP）優于随機采樣（random pick，RP），B = 10 時基本達到選擇正确率的上限，說明 SP-LIME 算法用局部代替整體效果較好。

3. 是否能夠用于提高模型的預測精度？

LIME 算法可以解釋模型預測樣本結果時所使用的特征，是否可以通過去除模型中使用的無關特征（噪音）而提高模型的預測精度？作者設計實驗如下：

1. 訓練集和待解釋模型與 例一 中一緻，由于 20 新聞討論區資料集是有偏的，是以訓練得到的模型會使用很多與 “基督教” 和 “無神論” 語義無關的詞語（即無關特征）。測試集為作者從 819 個 “基督教” 和 “無神論” 網站中下載下傳的文章。
2. 通過 SP-LIME、RP-LIME（K = 10，B = 10）算法将模型的預測原理呈現給受試者，受試者選擇出預測結果中與“基督教” 和 “無神論” 語義無關的詞語，程式會将這些詞語在下一輪訓練前從訓練集樣本中删除。注：受試者均不了解機器學習和特征工程的相關知識。
3. 首先将同一模型在不同算法采樣下的預測結果解釋交給 10 位受試者，受試者根據自己的知識對特征進行篩選。由于不同受試者判斷存在差異，是以在第一輪互動後會訓練生成 10 個模型。再将這 10 個模型交給 5 位受試者，在第二輪互動後訓練生成 50 個模型。最後将 50 個模型再交給這 5 位受試者，在第三輪互動後訓練生成 250 個模型。模型在測試集上的預測精度如下圖。

   

   圖中淺色的線表示 10 個模型在每輪互動後預測精度的均值，如第二輪時表示 5 個模型的精度均值，第三輪時表示 25 個模型的精度均值；深色的線表示模型總預測精度的均值，如第二輪表示 50 個模型的精度均值，第三輪表示 250 個模型的精度均值。從圖中可以看出，雖然不同受試者對模型的優化程度存在差異，但總體上模型預測精度都在随着無關特征的篩除而不斷上升，其中 SP-LIME 算法尤為明顯。說明 SP-LIME 能夠用于提高模型的預測精度。

附：K-LASSO 算法簡介

Lasso 是 Least Absolute Shrinkage and Selection Operator 的簡稱，是一種采用了L1正則化（L1-regularization）的線性回歸方法。采用了L1正則會使得部分學習到的特征權值為0，進而達到稀疏化和特征選擇的目的。

首先，一般的線性回歸問題為：給定 n 個樣本點 {(x1, y1), (x2, y2), …, (xn, yn)} ，其中 xi ∈ Rd，yi ∈ R，根據觀察到的樣本點找到一個映射 f：Rd → R，使得誤差平方和最小。此時優化目标為：

其中， β ∈ Rd，β0 ∈ R 是需要優化的系數。一般來說 β0 可以看作是一個偏置 (bias)，固定住 β 的值，那麼利用一階導數求最優 β0，得到：

将得到的結果代入原優化目标得到：

從上面式子可以看出，假如我們事先對資料進行标準化（中心化），即每個樣本資料減去均值，進而得到零均值的資料樣本，此時做線性回歸就可以不使用偏置。下面假定給定的 n 個樣本點是零均值的，即 Σ xi = 0，那麼線性回歸的優化目标就可以記為：

上面也可以表示為矩陣形式，記 X = [x1; x2; …; xn]T，這裡把每個資料點 xi 當作列向量，則有 X ∈ Rn*d；記 y = (y1, y2, …, yn)T；由于平方和可以寫成 L2 範數形式，|| x ||2 = √ Σ xi2，那麼矩陣形式的優化目标為：

一般來說，回歸問題是一個函數拟合的過程，我們希望模型不要太複雜，否則很容易發生過拟合現象，是以我們要加入正則化項。不同的正則化項就産生了不同的回歸方法，其中以 Ridge Regression (嶺回歸）和 Lasso最為經典，前者是加入了 L2 正則化項，後者加入的是 L1 正則化項。下面分别給出其優化目标。

Lasso 的優化目标為：

Ridge Regression 的優化目标為：

當我們對正則化項施加限制時，如本論文的 K-Lasso 中要求使用的使用的特征數 ≤ K，即 || β ||1 ≤ K。我們可以将正則化項從目标函數中移除，轉變為限制條件。

Lasso 的優化目标變為：

Ridge Regression 的優化目标為：

為了說明限制條件與優化目标之間的關系，設 d = 2，有 β = (w1, w2)T。此時 L2 正則化與 L1 正則化的不同見下圖。

圖中左邊解釋的是 L1 正則化的幾何意義，右邊是 L2 正則化。圖中橢圓形的彩色線是優化目标關于參數 β = (w1, w2)T 的等高線。假設沒有限制條件，那麼最小值是橢圓的中心點，但是由于加入了正則化項，相當于是對參數 β 施加了限制，其中左邊 L1 正則化将參數限制在一個菱形中，而 L2 正則化則将參數限制在一個圓形區域中。那麼從圖中可以看出，L1 正則化施加的限制會使得最優值在菱形頂點處取得，即 w1 = 0；而右邊L2 正則化項則沒有這種傾向。

上面的圖從幾何意義上解釋了 L1 與 L2 正則化的差別，同時這也解釋了 L1 與 L2 最大的不同：L1 可以帶來稀疏的結果，即 L1 會使得部分參數為零。一方面，可以用來選擇特征，一方面可以用來降維壓縮資料等等。L1 正則化是和稀疏挂鈎，與 L2 正則化挂鈎的則是權值衰減（Weight Decay）。簡單地說，嶺回歸傾向于在相關特征之間均勻分布權重，Lasso 則傾向于從相關特征中選取出一個，其餘特征權值為零。另外，正則化的目的也可以了解為使模型權重之間的方差較小

上述内容摘自 https://zhuanlan.zhihu.com/p/46999826

有關 Lasso 中參數的解法，也可參見 https://www.cnblogs.com/pinard/p/6018889.html