2018年的“最佳論文獎”和“最佳論文提名獎”的論文分享

機器學習頂會ICML 2018將于7月10日在瑞典斯德哥爾摩舉辦，今年會議共收到2473篇投遞論文，比去年的1676篇提高47.6%，增幅顯著。最終入圍的論文一共621篇，接受率25%，和去年的26%基本持平。

今天，會議官網(wǎng)公布了2018年的“最佳論文獎”和“最佳論文提名獎”：

最佳論文獎（Best Paper Awards）

Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples

Anish Athalye (MIT), Nicholas Carlini (UCB), David Wagner(UCB)

Delayed Impact of Fair Machine Learning

Lydia Liu, Sarah Dean, Esther Rolf, Max Simchowitz, Moritz Hardt (全員UCB)

最佳論文提名獎（Best Paper Runner Up Awards）

The Mechanics of n-Player Differentiable Games

David Balduzzi (DeepMind), Sebastien Racaniere (DeepMind), James Martens (DeepMind), Jakob Foerster (Oxford), Karl Tuyls (DeepMind), Thore Graepel (DeepMind)

Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices

Zengfeng Huang (復旦大學)

Fairness Without Demographics in Repeated Loss Minimization

Tatsunori Hashimoto (Stanford), Megha Srivastava (Stanford), Hongseok Namkoong (Stanford), Percy Liang (Stanford)

其中，復旦大學的論文Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices十分引人注目，這篇斬獲“最佳提名獎”的論文由大數(shù)據(jù)學院副教授黃增峰獨立完成，研究的是流模型（streaming model）中的協(xié)方差情況。文章提出了一種新型空間優(yōu)化算法，把流模型運行時間縮短到極致。

下面是對兩篇最佳論文的編譯概述：

最佳論文：Obfuscated Gradients Give a False Sense of Security

GitHub：github.com/anishathalye/obfuscated-gradients

基于神經(jīng)網(wǎng)絡的分類器通常被用于圖像分類，它們的水平通常接近人類。但是，這些相似的神經(jīng)網(wǎng)絡特別容易受到對抗樣本和細微的干擾輸入的影響。下圖是一個典型的對抗樣本，對原圖增加一些肉眼看不見的擾動后，InceptionV3分類器把貓分類成了鱷梨醬。根據(jù)Szegedy等人2013年的研究顯示，這種“愚蠢的圖像”僅用梯度下降法就能合成，這類發(fā)現(xiàn)為物體檢測研究敲響了警鐘。

在這篇論文中，作者評估了ICLR 2018接受的9篇論文，并測試了它們面對對抗樣本的穩(wěn)健性。實驗結(jié)果證實，在8篇有關(guān)對抗樣本的防御機制的論文中，有7篇的防御機制都抵擋不住論文提出的新型攻擊技術(shù)，防御水平有限。

簡介

雖然人們對對抗樣本已經(jīng)有了更多了解，甚至找到了抵御攻擊的方法，但卻還沒有一個徹底的解決方案能讓神經(jīng)網(wǎng)絡不受對抗樣本的干擾。據(jù)我們所知，目前發(fā)表的對抗樣本防御系統(tǒng)在強大的優(yōu)化攻擊面前同樣非常脆弱

經(jīng)過研究，我們認為防御系統(tǒng)能在受到迭代攻擊時仍然保持較強的魯棒性的共同原因是“混淆梯度”（obfuscated gradients）的存在。沒有良好的梯度信號，基于優(yōu)化的方法就不能成功。我們定義了三種混淆梯度——破碎梯度（shattered gradients）、隨機梯度（stochastic gradients）以及消失/爆炸梯度（vanishing/exploding gradients），同時針對這三種現(xiàn)象分別提出了解決方案。

混淆梯度

上文中我們提到了防御機制造成混淆梯度的三種方式，接下來讓我們一一介紹各種情況。

破碎梯度（shattered gradients）是當防御不可微分時產(chǎn)生的，它會引起數(shù)值不穩(wěn)定或者導致真正的梯度信號發(fā)生錯誤。造成梯度破碎的防御措施往往是通過引入可微分的操作無意產(chǎn)生的，但實際上剃度并不指向最大化分類損失的方向。

隨機梯度（stochastic gradients）是由隨機防御引起的，其中要么網(wǎng)絡本身是隨機的，要么輸入的內(nèi)容是隨機的。多次評估梯度會得到不同的結(jié)果，這可能會產(chǎn)生單步方法（single-step methods）以及優(yōu)化方法，即利用單個隨機樣本錯誤地估計真正的梯度方向，并且無法收斂到隨機分類器的最小值。

爆炸和消失梯度（Exploding & Vanishing gradients）通常是由多次迭代的神經(jīng)網(wǎng)絡評估構(gòu)成的防御造成的。因為這可以看作是一個非常深的神經(jīng)網(wǎng)絡評估，很容易看出為什么梯度會爆炸或消失。

找到混淆梯度（identifying obfuscated gradients）

在一些情況下，防御機制包含著不可微的操作，但是在其他情況下，可能不會立即找到。以下是幾種檢查混淆機制的幾種方法，也許不一定適用于每種情況，但是我們發(fā)現(xiàn)每個含有混淆梯度的防御機制都至少有一個無法通過的測試。

檢查迭代攻擊比單步方法更好。在白盒中應用基于優(yōu)化的迭代攻擊應明顯強于單步攻擊，并且表現(xiàn)得必須相當好。如果單步方法的性能優(yōu)于多不方法，那么多步攻擊有可能陷入局部最小值的最優(yōu)搜索中。

證明白盒攻擊比黑盒效果好。黑盒威脅模型是白盒威脅模型的子集，所以百合設置中的攻擊應該表現(xiàn)得更好。然而，如果防御正在混淆梯度，那么不需要梯度信號的黑盒通常比白盒攻擊的效果好。

確保攻擊達到100%的成功。如果對圖片無限進行干擾，任何分類器應該對對抗樣本有0%的魯棒性（只要分類器不是一個常數(shù)函數(shù)）。如果攻擊沒有達到100%的成功率，這表明防御機制正在以微妙的方式打敗攻擊，實際上可能不會增加魯棒性。

暴力隨機抽樣。識別混淆梯度的最后一個簡單方法是在每張圖像的某個ε-球內(nèi)暴力搜索對抗樣本。如果用優(yōu)化方法進行的隨機搜索沒有找到對抗樣本，防御很可能是混淆梯度。

攻擊混淆梯度的技術(shù)

既然已經(jīng)找到了混淆梯度，那么應該用什么方法解除樣本的防御系統(tǒng)呢？通過基于優(yōu)化的方法產(chǎn)生對抗樣本的例子需要通過反向傳播獲取有用的梯度。因此，許多防御有意或無意地造成梯度下降，最終失敗。我們討論了一些技術(shù)，能解決混淆梯度的問題。

后向傳遞可微近似（Backward Pass Differentiable Approximation）：破碎的梯度可能是無意產(chǎn)生的（如數(shù)值不穩(wěn)定）或者有意產(chǎn)生的（使用不可微分的操作）。為了攻擊那些梯度不易獲得的防御，我們引入后向傳遞可微近似（BPDA）的技術(shù)。

對隨機性求導：使用隨機分類器之前對輸入使用隨機變換時會產(chǎn)生隨機梯度，當對采用這些技術(shù)的防御系統(tǒng)進行基于優(yōu)化的攻擊時，有必要估計隨機函數(shù)的梯度。

重新調(diào)整參數(shù)：針對梯度消失或爆炸，我們通過重新調(diào)整參數(shù)來解決。

案例研究：ICLR 2018中的防御機制

為了了解混淆梯度的影響，我們研究了ICLR 2018接收的論文中研究白盒威脅模型中魯棒性（穩(wěn)健性）的成果。我們發(fā)現(xiàn)除了一篇之外，其他論文中的防御機制都依賴于這一現(xiàn)象來保證對抗樣本的魯棒性，而且我們的技術(shù)可以使那些依賴于混淆梯度的技術(shù)失效。下表總結(jié)了實驗結(jié)果：

雖然Madry等人的方法不會生成混淆梯度的三種情況。但是，我們發(fā)現(xiàn)了這種方法的兩個重要特征：

對抗性在訓練在ImageNet上有困難；

只在l∞對抗樣本上進行的訓練只在其他干擾的度量下對對抗樣本提供有限的魯棒性。

除此之外，其他七篇論文或多或少地都依賴于混淆梯度。

最佳論文：Delayed Impact of Fair Machine Learning

機器學習的基礎(chǔ)理念之一是用訓練減少誤差，但這類系統(tǒng)通常會因為敏感特征（如種族和性別）產(chǎn)生歧視行為。其中的一個原因可能是數(shù)據(jù)中存在偏見，比如在貸款、招聘、刑事司法和廣告等應用領(lǐng)域中，機器學習系統(tǒng)會因為學習了存在于數(shù)據(jù)中的歷史偏見，對現(xiàn)實中的弱勢群體造成傷害，因而受到批評。

在這篇論文中，我們探討了近期BAIR將機器學習系統(tǒng)決策和長期社會福利目標結(jié)合起來的工作。和銀行的信用評分系統(tǒng)類似，這些系統(tǒng)通常會生成一個統(tǒng)計個人信息的分數(shù)，然后依據(jù)這個分數(shù)對他們做出決策。我們提出了一種名為“結(jié)果曲線”的模型，它為系統(tǒng)的公平性提供了直觀的檢測手段，下面是以銀行貸款為例的說明。

如下圖所示，任何一批人在信用評分上都有特定分布。每個圓點代表一個客戶，深色的按時還貸，淺色的有違約記錄；信用分越高，客戶還貸幾率越高。

圖一 信用評分和還貸分布

通過定義一個閾值，信用評分可被用來執(zhí)行決策，比如銀行會為超過分數(shù)閾值的客戶發(fā)放貸款，而拒絕低于閾值的客戶的貸款申請。這種決策規(guī)則被稱為閾值策略（threshold policy）。

從機器學習角度看，這個分值可以被看作是對客戶違約概率的編碼。例如，在信用評分為650的群體中，客戶愿意按時貸款的比例高達90%，銀行就能通過向這批人貸款來預測自己期望獲得的利潤。同理，信用評分越高，銀行利率的預測越準確，風險也越小。

圖二 貸款閾值和營收結(jié)果

如果沒有其他考慮因素，銀行總是把利潤最大化放在第一位的。就貸款來看，銀行的利潤取決于它從按時還貸中得到的利息和在拖欠貸款中損失的金額之比。在上圖中，這個利息和損失的比率范圍是1到-4，由于客戶違約帶來的損失比客戶守約帶來的利息更高，銀行發(fā)放貸款會更謹慎，貸款閾值也更高。我們把這部分信用評分高于貸款閾值的客戶比例稱為選擇率（selection rate）。

結(jié)果曲線

貸款決策影響的不只是金融機構(gòu)，它對個人也有一定影響。如果借款人未能償還貸款，這類違約事件不僅降低了銀行利潤，也惡化了借款人信用評分。相反地，如果借款人按時還貸，對人對己這是種雙贏的選擇。在我們的示例中，借款人信用評分的變化區(qū)間是-2到1，-2表示拖欠貸款，1表示已還貸。

閾值策略的結(jié)果，也就是客戶信用評分預期變化，可以被作為選擇率函數(shù)中的一個參數(shù)。我們把這個函數(shù)稱為結(jié)果曲線（outcome curve）。不同的選擇率會導致不同的結(jié)果，而這個結(jié)果不僅取決于客戶還款的可能性（閾值），也取決于銀行貸款決策的成本和收益（選擇率）。

圖三

上圖顯示的是典型人群的結(jié)果曲線。如果一批人中有足夠多的人獲得了銀行貸款，并且能按時還款，這批人的信用評分會增加，這是由銀行利潤最大化驅(qū)動的（實線黃色區(qū)域）。如果這時我們開始偏離利潤最大化而向更多人發(fā)放貸款，這批人的平均信用評分會達到一個最高值，也就是曲線最高點，我們把這個點稱為利他最優(yōu)（altruistic optimum）（藍色區(qū)域）。

我們也可以調(diào)整選擇率，讓平均信用評分保持在低于最高值，但同樣可以獲得貸款的水平（虛線黃色區(qū)域）。因為分數(shù)確實是降低了，我們稱這里的選擇率正在導致相對危害（relative harm）。最后，如果太多借款人沒有能力還貸，這批人的信用評分會一起下降（紅色區(qū)域）。

圖四 貸款閾值和結(jié)果曲線

不同群體

那么這些給定的閾值策略是怎么影響到不同群體中的個人的呢？信用評分分布不同的兩組人會有不同的結(jié)果。

設存在兩個信用評分分布不同的小組，其中第一組人數(shù)少，我們可以認為這個群體是一個歷史上處于弱勢地位的少數(shù)群體。我們把它表示為藍色，目標是確保銀行貸款策略不會對它構(gòu)成歧視。

圖五 不同群體的貸款策略

可以看出，為了公平起見，銀行可以為這兩個小組劃分不同的貸款閾值，但這其實產(chǎn)生了另一種歧視，而且涉嫌違法。

剩下的方法是改進藍色小組的信用評分分布。正如我們之前提到的，如果不加約束，銀行策略肯定會朝著利潤最大化發(fā)展：計算一個盈虧持平的閾值，超過閾值發(fā)放貸款，低于閾值拒絕貸款。事實上，兩組的利潤最大化閾值（信用評分580）是相同的。

公平標準

對于具有不同分布的小組，它們的結(jié)果曲線也不同。作為利潤最大化的替代方案，我們可以考慮添加公平性約束（fairness constraints），使小組間的決策相對于某個目標函數(shù)相等，從而保護弱勢群體。通過結(jié)果模型，我們現(xiàn)在可以具體回答這些公平性約束是否真的造成了實際上的積極影響。

圖六 用公平性約束模擬貸款決策

在貸款問題中，一個最常見的公平標準是人口平等（demographic parity）。它要求銀行以同樣的選擇率向兩個小組提供貸款。根據(jù)這一要求，銀行將盡可能地繼續(xù)實現(xiàn)利潤最大化。另一個公平標準則是機會均等（equality of opportunity），即使兩個組的真實盈利率（true positive rates）相等，要求銀行依據(jù)每個組按時償還貸款的客戶比例分別制定選擇率。

盡管這些公平標準是考慮均衡靜態(tài)決策的一種自然方式，但他們經(jīng)常忽略這些策略對人口結(jié)果的未來影響。與最大利潤相比，人口平等和機會均等都降低了銀行利率，同時也沒有真正改善藍色小組的弱勢地位。

利潤最大化

人口平等

機會均等

如果采用公平標準的目標是增加或平衡所有人群的長期福祉，上述圖已經(jīng)表明，有時候公平標準實際上違背了這一目標。換句話說，公平性限制也會減少已經(jīng)處于不利地位的人群的福利。構(gòu)建一個準確的模型來預測決策對人口結(jié)果的影響可能有助于緩解應用公平標準可能造成的未預料到的危害。