Deutch, Daniel, et al. "T-REx: Table repair explanations."?Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020.

摘要：數(shù)據(jù)修復(fù)是當(dāng)今許多框架中關(guān)鍵的一步，因?yàn)閼?yīng)用程序可能使用來自不同來源和不同可信度級(jí)別的數(shù)據(jù)。因此，這一步一直是許多人關(guān)注的焦點(diǎn)工作提出許多不同的方法。為了幫助用戶了解這樣的數(shù)據(jù)修復(fù)算法的輸出，我們提出了T-REx一個(gè)系統(tǒng)，通過Shapley值提供數(shù)據(jù)修復(fù)解釋。該系統(tǒng)是通用的，并不特定于給定的修復(fù)算法或方法：它將算法視為黑盒。給定由用戶選擇的特定表格單元格，T-REx采用Shapley值來解釋每個(gè)約束和每個(gè)表格單元格在修復(fù)感興趣的單元格中的重要性。然后，T-REx根據(jù)約束和表格單元在修復(fù)該單元中的重要性對(duì)約束和表格單元進(jìn)行排序。此解釋允許用戶理解修復(fù)過程，以及基于此知識(shí)采取行動(dòng)，以修改影響最大的約束或原始數(shù)據(jù)庫。

Deutch, Daniel, et al. "Explanations for data repair through shapley values."?Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.

數(shù)據(jù)修復(fù)，即識(shí)別和修復(fù)數(shù)據(jù)中的錯(cuò)誤是數(shù)據(jù)科學(xué)周期的核心組成部分。大量的研究工作已經(jīng)致力于自動(dòng)化的修復(fù)過程。然而，它仍然需要數(shù)據(jù)科學(xué)家大量的手工勞動(dòng)，調(diào)整和優(yōu)化修復(fù)模塊（根據(jù)調(diào)查，高達(dá)80%的時(shí)間）。

為此，我們?cè)诒疚闹刑岢隽艘粋€(gè)新的框架，用于解釋任何數(shù)據(jù)修復(fù)模塊的結(jié)果。解釋涉及到識(shí)別對(duì)過程有最大影響的表單元格和數(shù)據(jù)庫約束。反過來，通過Shapley值的博弈論概念來量化影響，Shapley值通常用于解釋機(jī)器學(xué)習(xí)分類器結(jié)果。主要的技術(shù)挑戰(zhàn)是Shapley值的精確計(jì)算導(dǎo)致指數(shù)時(shí)間。因此，我們?cè)O(shè)計(jì)和優(yōu)化新的近似算法，并從理論和經(jīng)驗(yàn)上分析它們。我們的研究結(jié)果表明，我們的方法的效率相比，適應(yīng)現(xiàn)有的Shapley值計(jì)算技術(shù)的數(shù)據(jù)修復(fù)設(shè)置的替代方案。

研究目的與問題定義

Shapley值的概念最初是在博弈論的背景下提出的，作為量化合作博弈中每個(gè)參與者貢獻(xiàn)的一種度量。它后來被機(jī)器學(xué)習(xí)（ML）領(lǐng)域采用，作為評(píng)估模型中每個(gè)特征貢獻(xiàn)的工具[4]。給定修復(fù)的單元，T-REx計(jì)算并呈現(xiàn)已經(jīng)影響該修復(fù)的DC和表單元的Shapley值。本文的方法直接評(píng)估輸入的貢獻(xiàn)，而不是由特定算法使用的隱藏特征的貢獻(xiàn)。這允許系統(tǒng)的解決方案將修復(fù)算法視為黑盒，并且僅查詢它以計(jì)算DC和細(xì)胞的Shapley值。 對(duì)DC對(duì)修復(fù)的影響的解釋可以幫助用戶校正它們并使它們適應(yīng)特定數(shù)據(jù)和修復(fù)算法，而關(guān)于數(shù)據(jù)單元的影響的解釋可以幫助理解修復(fù)算法本身并改變特定單元以使修復(fù)更準(zhǔn)確 。

以下圖為例是一組否定依賴的例子，否定依賴最左側(cè)就是在這個(gè)修復(fù)下各個(gè)約束的shapley值。

對(duì)應(yīng)的數(shù)據(jù)表如下圖所示：

示例的一個(gè)簡(jiǎn)單的處理算法如下圖所示，思路就是分別對(duì)每個(gè)否定依賴進(jìn)行修復(fù)，修復(fù)的值用不違法該約束下最頻繁的屬性值替代。

下面對(duì)Shapley 值（下面可能稱作貢獻(xiàn)值）計(jì)算方法進(jìn)行說明：

1.對(duì)約束貢獻(xiàn)值進(jìn)行分析

• 考慮第五行中的 "Country" 單元格，用 t5[Country] 表示。為了簡(jiǎn)化問題，假設(shè)我們有一個(gè)名為 "Algorithm 1" 的樸素（簡(jiǎn)單）修復(fù)算法。T-REx 計(jì)算了每個(gè)數(shù)據(jù)約束（DC，可能是"Data Constraint"的縮寫）的貢獻(xiàn)并按照貢獻(xiàn)進(jìn)行了排名，其中 C3 是最具影響力的數(shù)據(jù)約束。C3 的貢獻(xiàn)最大，因?yàn)樵谄渌齻€(gè)元組中，"League" 屬性的值為 'La Liga'，并且與 "Country" 屬性的值 'Spain' 相對(duì)應(yīng)。C1 和 C2 各自的貢獻(xiàn)相等，因?yàn)槭紫?C1 導(dǎo)致了 "Capital" 屬性的值從原來的值變?yōu)?'Madrid'，然后 C2 導(dǎo)致了 "Country" 單元格的值發(fā)生了變化。C4 在修復(fù)中沒有參與，因此它的貢獻(xiàn)為 0。

• 總之，"Algorithm 1" 的簡(jiǎn)單修復(fù)算法被用來修復(fù)第五行中的 "Country" 單元格。通過計(jì)算每個(gè)數(shù)據(jù)約束的貢獻(xiàn)，并將其進(jìn)行排名，T-REx（可能是一個(gè)算法或工具）確定了各個(gè)數(shù)據(jù)約束對(duì)修復(fù)的影響。在此情景中，C3 對(duì)修復(fù)的影響最大，C1 和 C2 的影響相等，而 C4 并未參與修復(fù)。

2.對(duì)單元格貢獻(xiàn)值進(jìn)行分析

• 在給定 "Algorithm 1" 的情況下，注意到 t1[P lace] 的值對(duì) t5[Country] 的修改沒有影響 — 因?yàn)?t1 與 t5 沒有沖突，并且在 "Algorithm 1" 中，屬性 P lace 對(duì) Country 沒有影響。然而，我們?nèi)绾未_定相對(duì)于 t6[City] 來說，t5[League] 對(duì)修復(fù)的影響是更大還是更小的呢？直觀地說，t5[League] 比 t6[City] 更具影響力。這是因?yàn)槿绻?t5[League] 具有不同的值，那么根據(jù) C3，元組 t5 就不會(huì)有任何沖突。而如果 t6[City] 具有不同的值，那么根據(jù) C1，在 t3 和 t6 之間將會(huì)存在沖突，這將會(huì)被 "Algorithm 1" 修復(fù)。因此，T-REx 將會(huì)比較 t5[League] 和 t6[City]，將更高的貢獻(xiàn)分配給 t5[League]。

• 總之，通過比較不同數(shù)據(jù)元素對(duì)約束的違規(guī)情況，可以判斷它們?cè)谛迯?fù)中的相對(duì)影響力。在這個(gè)特定情景中，t5[League] 對(duì)修復(fù)的影響被認(rèn)為比 t6[City] 更大，因?yàn)?t5[League] 的值在滿足 C3 時(shí)可以消除沖突，而 t6[City] 的值在滿足 C1 時(shí)可以解決沖突。

總結(jié)

T-REx 接受算法本身和其輸入作為輸入，該輸入包括一組數(shù)據(jù)約束（DCs，可能是 "Data Constraints" 的縮寫）和一個(gè)臟數(shù)據(jù)數(shù)據(jù)庫表。 該系統(tǒng)的另一個(gè)輸入是一個(gè)特定感興趣的表格單元格，其修復(fù)需要解釋。系統(tǒng)隨后根據(jù)這個(gè)感興趣的單元格的 Shapley 值，對(duì)影響力較大的數(shù)據(jù)約束和表格單元格進(jìn)行排名。通常情況下，計(jì)算 Shapley 值與數(shù)據(jù)約束/表格單元格數(shù)量呈指數(shù)關(guān)系，因此 T-REx 使用不同的算法來計(jì)算數(shù)據(jù)約束的 Shapley 值以及表格單元格的 Shapley 值。對(duì)于數(shù)據(jù)約束，樸素的方法是可行的，因?yàn)閿?shù)據(jù)約束的數(shù)量通常較小。相反，表格中的單元格數(shù)量可能非常大，因此 T-REx 使用基于 [7] 的采樣算法。為了計(jì)算 Shapley 值，該系統(tǒng)會(huì)反復(fù)更改修復(fù)算法的輸入并查詢它，因此不依賴于特定算法的組件或方法。

[7] E. Strumbelj and I. Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowl. Inf. Syst., 41(3):647–665, 2014.

總之，T-REx 是一個(gè)系統(tǒng)，用于解釋和排名對(duì)特定表格單元格的修復(fù)影響，并使用 Shapley 值來衡量影響的大小。系統(tǒng)使用不同的算法來計(jì)算數(shù)據(jù)約束和表格單元格的 Shapley 值，以適應(yīng)不同的約束和單元格數(shù)量。它通過多次改變修復(fù)算法的輸入并進(jìn)行查詢來計(jì)算 Shapley 值，以獲得影響排名。

方法與實(shí)施方案

• T-REx基于Shapley值為數(shù)據(jù)修復(fù)解釋提供了一個(gè)新穎的系統(tǒng)。Shapley值最初是在合作博弈論的背景下提出的，作為量化合作博弈中每個(gè)玩家貢獻(xiàn)的一種方法。它后來被機(jī)器學(xué)習(xí)社區(qū)采用，作為評(píng)估模型中每個(gè)特征貢獻(xiàn)的工具。給定一個(gè)已修復(fù)的單元格，T-REx計(jì)算并呈現(xiàn)已影響此修復(fù)的DCs和表格單元格的Shapley值。[Page 1]

• T-REx的輸入是修復(fù)算法本身及其輸入，即一組DCs和一個(gè)臟數(shù)據(jù)庫表。系統(tǒng)然后根據(jù)它們對(duì)感興趣的單元格的Shapley值對(duì)影響DCs和表格單元格進(jìn)行排序。

• T-REx的實(shí)現(xiàn)使用Python 3.6和底層的PostgreSQL 10.6數(shù)據(jù)庫引擎。其基于Web的GUI使用JavaScript、CSS和HTML構(gòu)建。

理解Shapley值:
在合作博弈論中，Shapley值是一種分配每個(gè)玩家的貢獻(xiàn)的方法，假設(shè)他們合作。設(shè) (??) 是玩家的有限集合，而 (??: 2^?? → ?) 是一個(gè)特征函數(shù)，其中 (??(?) = 0)。這個(gè)函數(shù)將玩家的集合映射到他們根據(jù)游戲生成的聯(lián)合價(jià)值。玩家 (??) 對(duì)聯(lián)盟 (??) 的貢獻(xiàn)由于 (??) 的加入而導(dǎo)致 (??) 的變化來定義，即 (??(?? ∪ {??}) - ??(??))。玩家 (??) 的Shapley值是這種貢獻(xiàn)在可以形成的不同排列中的平均值。

直觀地說，對(duì)于任何玩家 (??)，這個(gè)值是 (??) 對(duì)任何可能的聯(lián)盟中 (??) 的變化的貢獻(xiàn)的總和，由聯(lián)盟的大小加權(quán)，這樣中等大小的聯(lián)盟（存在更多的這樣的聯(lián)盟）的貢獻(xiàn)會(huì)更低。

公式:
$$
\phi_??(??, ??, ??) = \sum_{??????{??}} \frac{|??|!(|??|-|??|-1)!}{|??|!} (??(?? ∪ {??}) - ??(??))
$$
偽代碼：

使用Shapley值，我們可以計(jì)算每個(gè)單元格對(duì)錯(cuò)誤值的修復(fù)貢獻(xiàn)。

實(shí)驗(yàn)設(shè)置

1. 使用的數(shù)據(jù)集：用戶研究使用了兩個(gè)數(shù)據(jù)集：

• Hospital：該數(shù)據(jù)集有 21K 個(gè)單元和 19 個(gè)拒絕約束 (DC)。

• MAS：這個(gè)數(shù)據(jù)集更大，有 2M 個(gè)單元和 11 個(gè) DC。

2. 參與者：該研究涉及 20 位用戶。所有參與者都獲得了每個(gè)問題修復(fù)過程中使用的數(shù)據(jù)庫和約束。他們還了解了該研究、相關(guān)符號(hào)和所使用的數(shù)據(jù)集。用戶分為兩組：

• 一組可以訪問T-Rex的輸出。

• 另一組無法訪問T-Rex的輸出。

本文展示了 T-Rex 的一個(gè)測(cè)試，重點(diǎn)關(guān)注用戶研究中的Q4 和Q5。此用例演示了 T-Rex 如何快速查明 MAS 數(shù)據(jù)集中的問題?？紤]了具有大約 2M 個(gè)單元和一組 11 個(gè)函數(shù)依賴性的 MAS 數(shù)據(jù)庫實(shí)例。Q1-Q5如下：

結(jié)果：

1. T-Rex可用性：

• 結(jié)果凸顯了T-Rex解釋的優(yōu)勢(shì)。例如，在問題 Q3 中，所有 10 位有權(quán)訪問 T-Rex 的用戶都回答正確，而只有 2 位沒有訪問權(quán)限的用戶回答正確。

• 無法訪問 T-Rex 的用戶無法回答 Q1、Q2、Q4、Q5。相比之下，至少有 7 位有權(quán)訪問 T-Rex 的用戶可以回答這些問題。

• 所有有權(quán)訪問 T-Rex 的用戶都正確回答了問題 4，而所有沒有訪問權(quán)限的用戶都未能回答問題。

• 對(duì)于Q5，60%的 T-Rex 用戶建議了正確的修復(fù)方案，2 人提供了部分修復(fù)方案。

• 該研究展示了用戶如何使用 T-Rex 輕松識(shí)別修復(fù)過程中的錯(cuò)誤并實(shí)現(xiàn)更好的修復(fù)。

2. 結(jié)果：

• 比較了不同數(shù)據(jù)集的運(yùn)行時(shí)間與數(shù)據(jù)庫大小的函數(shù)關(guān)系。它表明 T-Rex 對(duì)于較大的表大小可以更好地?cái)U(kuò)展，特別是對(duì)于 MAS 數(shù)據(jù)集。

• 比較了文章中描述的優(yōu)化的不同設(shè)置。

• 顯示了 T-Rex 用戶研究的結(jié)果

總體而言，實(shí)驗(yàn)結(jié)果強(qiáng)調(diào)了 T-Rex 系統(tǒng)在為數(shù)據(jù)修復(fù)過程提供解釋方面的實(shí)用性和效率。用戶研究結(jié)果特別強(qiáng)調(diào)了該系統(tǒng)在幫助用戶理解和改進(jìn)維修過程方面的有效性。

心得啟發(fā)

1.通過Shapley值解釋修復(fù)有助于理解修復(fù)過程，并且通過計(jì)算shapley的值，可以判斷約束和單元格對(duì)修復(fù)的貢獻(xiàn)情況，這種方法對(duì)數(shù)據(jù)清洗重要性采樣很有幫助。

2.在交互式系統(tǒng)中，可以通過把單元貢獻(xiàn)度和約束貢獻(xiàn)度給用戶參考，達(dá)到交互式清洗的目的。