論文摘要
任何給定的人工智能系統都不能被接受，除非它的可信度被證明。值得信賴的人工智能系統的一個重要特征是沒有算法偏見。“個體歧視”存在于給定個體與另一個體僅在“受保護屬性”（如年齡、性別、種族等）上不同，但是它們會從給定的機器學習（ML）模型中得到不同的決策結果。目前的工作是解決給定 ML 模型中存在的個體歧視問題。在黑盒環境下，個體歧視的檢測是測試密集型的，這對于非平凡的系統是不可行的。我們提出了一種自動生成測試用例進行輸入的方法，用于檢測個體歧視的任務。我們的方法結合了兩種成熟的技術——符號執行和局部可解釋性，以實現有效的測試案例生成。我們實證表明，與所研究的最著名的基準系統相比，我們生成測試用例的方法是非常有效的。
論文介紹
模型的偏見。這十年隨著人工智能（AI）的復蘇，AI 模型已經開始在很多系統中承擔關鍵性的決策--從招聘決策、審批貸款到設計無人駕駛汽車。因此，為了確保人工智能系統被廣泛接受，人工智能模型的可靠性是最重要的?？煽康?AI 系統的一個重要方面是確保其決策的公平性。偏見可能以多種方式存在于決策系統中。它可以以群體歧視的形式存在，即兩個不同的群體（例如，基于性別/種族等“受保護的屬性”）獲得不同的決策。需要注意的是，歧視感知系統需要經過訓練，以避免對敏感的特征進行歧視，這些特征被稱為“受保護的屬性”。受保護的屬性是特定于應用的。年齡、性別、種族等特征是一些經常出現的例子，許多應用實際都將其作為受保護屬性。
個體歧視。在本文中，我們討論了機器學習模型中檢測個體歧視的問題。我們在本文中使用的個體公平性/偏見的定義是一種簡化的、非概率的反事實公平性，這也符合 Dwork 的個體公平性框架。如本工作所述，如果對于任何兩個僅在受保護屬性上有差異的有效輸入，總是被分配到相同的類別，那么系統就被稱為是公平的（如果對于某對有效輸入，產生了不同的分類，那么就被稱為存在偏差）。這樣的偏差情況在之前的模型中已經被注意到了，并對模型生成者造成了不利的后果。因此，檢測這類情況是最重要的。需要注意的是，從訓練數據中刪除受保護的屬性并不能消除這種偏見，因為由于受保護屬性和非受保護屬性之間可能存在的共同關系，個體歧視可能仍然存在，就像成人人口普查收入數據中的種族（受保護）和郵編（非受保護）一樣。因此，我們面臨的挑戰是，如何評估和找到非保護和保護屬性的所有值，讓模型顯示出這種個體歧視行為。
現有技術及其缺點。衡量個體歧視需要進行詳盡的測試，這對于一個非平凡的系統來說是不可行的?，F有的技術能生成一個測試套件來確定模型中是否存在個體歧視以及個體歧視的程度。THEMIS 從域中選擇所有屬性的隨機值，以確定系統是否在個體之間進行歧視。AEQUITAS 分兩個階段生成測試用例。第一階段通過對輸入空間進行隨機采樣來生成測試用例。第二階段開始時，將第一階段產生的每個判別輸入作為輸入，并對其進行擾動，以產生更多的測試用例。這兩種技術的目的都是為了產生更多的測試輸入。盡管上述這兩種技術適用于任何黑盒系統，但我們的實驗表明，它們會遺漏許多這樣的非保護屬性值組合，而這些組合可能存在單獨的判別。我們還希望覆蓋模型更多樣化的路徑，以生成更多的測試輸入。
我們的方法。我們的目的是對特征空間進行系統化搜索，以覆蓋更多的空間，而不需要太多的冗余。存在基于符號評估的技術，通過系統地探索程序中的不同執行路徑來自動生成測試輸入。這種方法避免了生成多個輸入，因為這些輸入傾向于探索相同的程序路徑。這類技術本質上是白盒技術，利用約束求解器的能力來自動創建測試輸入。符號執行從一個隨機輸入開始，分析路徑生成一組路徑約束條件（即輸入屬性的條件），并迭代地切換（或否定）路徑中的約束條件，生成一組新的路徑約束條件。然后，它使用約束求解器對所得的路徑約束進行求解，以生成一個新的輸入，這個輸入可能會把控制帶到新的路徑上。我們的想法是使用這種動態符號執行來生成測試輸入，這有可能導致發現 ML 模型中的個體歧視。然而，現有的這種技術已經被用來生成可解釋程序的程序輸入。我們的主要挑戰是如何將這種技術應用于不可解釋的機器學習模型。
- 限制條件?？梢允褂矛F成的局部解釋器來生成路徑的線性近似。從一個這樣的解釋器中得到的線性約束可以用于符號評價，這將不需要任何專門的約束求解器。
- 數據驅動。我們的算法可以利用已知的數據，這些數據可以作為種子數據開始搜索。
- 全局和局部搜索。一旦找到一個單獨的判別，我們就進行局部搜索，以發現許多輸入組合，從而發現更多的判別。否則，我們使用符號執行進行全局搜索，以覆蓋模型中的不同路徑。
- 優化。局部解釋器呈現與謂詞相關的置信度。我們的算法根據約束條件的置信度得分來執行對其進行切換的選擇。
- 可擴展性。我們的算法通過切換特征相關的約束來系統地遍歷特征空間中的路徑。這使得它具有可擴展性，不像其他技術那樣考慮基于結構的覆蓋標準。
貢獻：我們的貢獻如下。
- 我們提出了一種新的技術來尋找模型中的個體歧視。
- 我們開發了一種新的動態符號執行和局部解釋的組合，以生成非可解釋模型的測試用例。我們相信，局部解釋器的使用將為黑盒 AI 模型的基于路徑的分析開辟許多途徑。
- 我們在幾個具有已知偏差的開源分類模型上展示了我們技術的有效性。我們將我們的技術與現有的算法即 THEMIS、AEQUITAS 進行了實證比較，并展示了我們的方法比這些先前的工作所帶來的性能改進。
算法
我們將我們的算法分為兩種不同的搜索算法，分別稱為全局搜索和局部搜索。
下面是我們想通過設計的測試用例生成技術達到兩個優化標準。有效的測試用例生成：給定一個模型 M，一組領域約束條件 C 和受保護屬性集 P，目的是生成測試用例，以最大限度地提高|Succ|/|Gen|的比率，其中 Gen 是算法生成的非受保護屬性值組合的集合，Succ ⊆Gen 可導致歧視，即 Succ 中的每個實例對不同的受保護屬性值組合至少產生一個不同的決定。下面是關于這個標準的幾個指標：
- 測試用例。每個測試用例不被視為所有屬性值的集合，而只被視為非保護屬性的集合。這確保了多個判別性測試用例不會被計入相同的非保護屬性值組合。
- 領域約束。我們假設應用領域約束 C 可以過濾掉不真實的測試用例。
- 生成和判別測試的順序。優化標準并沒有規定所有的測試用例是否一次生成，也沒有規定檢查判別和生成是否可以同時進行。這樣測試用例的生成也可以依賴于判別檢查。
在軟件測試領域，存在一些預定義的覆蓋標準。在最近關于機器學習的著作中也定義了許多這樣的覆蓋標準。接下來，我們定義路徑覆蓋標準，使其適用于不同類型的模型。
覆蓋標準：請注意，為任何黑盒模型定義路徑覆蓋標準都不是簡單的?？梢愿鶕煌愋偷哪Ｐ偷牟僮魈攸c來定義其路徑。例如，可以根據神經元的激活來定義神經網絡中的路徑，也可以定義決策樹分類器中的決策路徑。
我們將覆蓋標準定義如下。給定一個分類模型 M 和一組測試用例 T，我們將 T 的覆蓋率定義為 M 的決策區域被 T 執行的數量。
在本文中，我們使用決策樹分類器來逼近模型 M 的行為，我們生成高精度的決策樹模型來逼近 M 的決策區域，我們測試用例生成技術的目的是最大化路徑覆蓋率和個體歧視檢測。
在實踐中，自動測試用例生成過程總是有一個極限，在這個極限范圍內，需要完成這兩個目標的最大化。在我們的案例中，我們考慮了兩個這樣可能的限制：1）生成測試用例的數量 2）生成時間。
路徑覆蓋率最大化是通過利用符號執行算法的能力來實現的，該算法迎合了對不同執行路徑的系統探索。。最大化路徑覆蓋率是在全局搜索模塊中完成的，正如我們在最終算法所提到的。
符號執行和局部模型近似路徑的思想的直接應用有三大挑戰。前兩者的產生是由于局部模型中存在的固有近似，而符號執行則是第三種的原因。
- 近似。決策樹路徑根據可解釋的特征近似于實際執行路徑。由于這樣的近似，可以生成實際程序路徑的重復。
- 可信度。決策樹路徑有一個與所有組成的謂詞相關聯的置信度得分（而程序路徑則不是這樣）。因此，挑戰在于設計一種方法來使用這個置信度分數來更好地探索路徑。
- 程序測試中的符號執行存在路徑爆炸問題，尤其是在深度優先搜索方式下。它可以一直探索程序樹深度的路徑，而不探索程序其他部分的路徑。研究者們已經探索出各種技術來解決這個問題——應用需求驅動或定向技術，向著程序中的某個特定位置生成測試用例，以及組合技術，試圖分別分析各種功能模塊，然后再將它們組合起來，在整個程序中生成更長的路徑。所有這些技術都利用了被測程序的結構。
最大限度地提高歧視檢測效率
檢查個體歧視。首先，讓我們考慮一下檢查個體歧視的情況，如算法 2 所示。該算法按照個體歧視的定義來執行檢查。如果一個測試用例保持其非保護屬性集的值不變，但通過嘗試各種可能的組合來改變其保護屬性集的值，從而產生不同的類標簽，那么這個測試用例被認為是具有個體歧視性的。
本地搜索。如前文所討論的符號執行，試圖找到測試輸入以最大化路徑覆蓋率。我們把這樣的符號搜索策略稱為全局搜索。通過種子數據或符號執行產生的一些測試輸入將具有鑒別性。為了增加歧視性測試用例的可能性，我們利用了這樣一個事實：我們可以執行測試用例并檢查它們是否具有判別性，然后根據這一點，生成更多的測試用例。
一旦發現了一個具有歧視性的測試用例，比如說 t，我們就嘗試進一步生成更多的測試輸入，這可能會導致個體歧視。關鍵思想是否定 t 的決策樹的非保護屬性約束，以生成更多的測試輸入。通過切換一個與非保護屬性相關的約束，并生成一個解決結果約束的輸入，算法試圖探索判別路徑 p 的鄰域，這種形式的符號執行就是我們所說的局部搜索，因為它傾向于搜索判別測試案例的局部性。這種方式之所以有效，是因為機器學習模型固有的對抗性魯棒性屬性，它證明了輸入的微小擾動會導致分類器決策的改變。
粘性解決方案。局部搜索和全局搜索的目的是遍歷盡可能多的路徑。局部搜索集中在探索判別路徑附近的路徑，即由判別輸入產生的路徑。因此，我們只能得到一個約束的解。但是，為了照顧到局部線性模型可能引起的相似情況，我們使用與前一個約束（與判別輸入有關）的解接近的約束求解器的解。我們把這樣的解稱為粘性解。由于粘性，如果我們否定了一個謂詞，那么對于剩下的謂詞，它就會趨向于取與前一個解相同的值。
本地搜索和全局搜索的排序。在綜合算法 2 中，提出了三個參考等級，即 Rank1、Rank2 和 Rank3，分別為種子輸入、本地搜索和全局搜索各一個。這些等級的設置方式是：根據其發現引起歧視的輸入的能力，給予本地搜索最高的優先級，其次是種子輸入，進一步是全局搜索（見算法 2 的第 3、18、32 行）。
實驗評估
基線特征。我們對表 1 所列的 8 個不同來源的開源公平性基線進行了實驗。
配置。我們的代碼是用 Python 寫的，用 Python 2.7.12 執行。所有的實驗都是在運行 Ubuntu 16.04 的機器上進行的，有 16GB 內存，2.4Ghz 的 CPU，運行 Intel Core i5。我們使用了 LIME 來進行局部解釋。我們使用 K-means 對輸入的種子數據進行聚類。由于我們的用例需要在較少的時間內生成更多的測試用例，K-means 是最簡單和最快的聚類算法之一，被證明是一個合理的選擇。事實上，用于運行我們的實驗的數據集具有兩個或四個真正的類標簽，這推動了將聚類數設置為 4 的邏輯假設。 這一點使用散點圖進一步驗證，如圖 2 所示，它清楚地描繪了種子數據中的四個不同的聚類。
與 THEMIS 的比較。我們從他們的 GitHub 倉庫中獲取了 THEMIS 的代碼，在仔細分析他們的代碼后，我們發現了開放源碼中的一個意外行為。THEMIS 實際上生成了重復的測試用例，他們報告的實驗統計也包含了這些重復的測試用例。這是隨機測試用例生成帶來的問題之一，因為它會產生重復的測試用例。我們對 THEMIS 的代碼進行了修改，以去除重復的測試案例，用于我們的實驗評估。
與 AEQUITAS 比較。AEQUITAS 算法在兩個搜索階段運行--全局和局部。全局階段考慮測試用例數量的限制，并通過對輸入空間的隨機抽樣來生成測試用例。在所有這些生成的測試用例中，有少數測試用例具有鑒別性。然后，局部階段開始將全局搜索階段確定的每個判別性輸入作為輸入，并對其進行擾動，以進一步生成更多的測試用例。這個階段就像之前的全局搜索一樣，考慮了對生成的測試用例數量的限制。他們應用了三種不同類型的擾動，導致算法的三種不同變化。
全球搜索比較。表 5 是 SG 與 AEQUITAS 在全局搜索策略方面的比較。我們的全局搜索方法使用聚類種子數據和符號執行，而他們的策略則使用輸入空間的隨機采樣。從統計結果可以看出，一般來說，我們的算法生成的輸入有更多的判別性。
我們進行了一個實驗來比較我們的全局搜索和基于隨機數據的搜索的路徑覆蓋率?；陔S機數據的搜索已經被應用于 THEMIS 和 AEQUITAS。因此，本實驗提出了與現有相關工作的比較。為了進行路徑覆蓋，我們學習了一個精度為 85%-95%的決策樹模型，對每個基準使用 5 倍交叉驗證來測量，并將每個生成的測試輸入映射到決策樹模型的路徑上。表 7 的結果顯示，在所有的基準中，SG 的平均路徑覆蓋率是隨機數據的 2.66 倍。這個結果表明，在路徑覆蓋率指標上，我們優于其他算法。因此，我們的算法將能夠在模型的各個不同地方找到偏見性的輸入。這一點很重要，因為在一次實驗中，如果我們使用測試用例進行再訓練，我們可以對模型的多個部分進行去偏見。
論文總結
在本文中，我們提出了一種測試用例生成算法，用于識別機器學習模型中的個體歧視問題。我們的方法結合了符號評價的概念，它為任何程序系統地生成測試輸入，并使用線性和可解釋的模型來近似模型中的執行路徑的局部解釋。我們的技術還提供了一個額外的優勢，因為它是黑盒性質的。我們的搜索策略主要橫跨兩種方法，即全局搜索和局部搜索。全局搜索迎合了路徑覆蓋率的要求，有助于發現初始的判別輸入集。為了實現這一點，我們使用種子數據與符號執行，同時考慮本地模型中存在的近似，并智能地使用與本地模型中獲取的路徑約束相關的置信度。此外，局部搜索的目的是尋找越來越多的判別性輸入。它從初始的可用判別路徑集開始，并生成屬于附近執行路徑的其他輸入，從而系統地進行局部解釋，同時依靠對抗性魯棒性屬性。我們的實驗評估清楚地表明，我們的方法比所有現有的工具表現得更好。
致謝
本文由南京大學軟件學院 2019 級碩士郭子琛翻譯轉述。
