本文是第三十四屆神經信息處理系統大會(NeurIPS 2020)入選論文《非誠實拍賣中效用與均衡的學習問題(Learning Utilities and Equilibria in Non-Truthful Auctions)》的解讀。
近年來不少文章(如[3, 4, 5])研究了非完美信息拍賣中的樣本復雜性問題。然而,大部分工作考慮的都是賣家收益最大化的樣本復雜性,鮮有工作研究買家收益最大化。而且,大部分現有工作都關注誠實拍賣,不涉及非誠實的報價策略。[6]是一個特例:他們研究了非誠實拍賣中一位買家誠實報價的效用與非誠實報價的效用至多相差多少。與本文一樣,[6]也采用了“采樣->估計”的思路。但他們沒有解決如何找到一組同時最大化所有買家的效用的策略(即納什均衡)的問題,而這正是本文的貢獻之一。
最佳論文獎
1. No-Regret Learning Dynamics for Extensive-Form Correlated Equilibrium
地址: //www.zhuanzhi.ai/paper/1cede84d4fe70b6f36d5df9acb3076e7
獲獎理由:
人們的決定會影響到他人。為了保證合理的行事方式,我們需要通過這種「相互依賴」達到經濟學家所說的「均衡」(equilibrium)。創建能夠找出均衡點的自動程序是非常困難的任務。這篇論文提供了首個解決方法——利用學習方法為通用交互尋找「相關均衡」(correlated equilibria,CE)。
相關均衡要求一個受信任的外部調停者為決策者提供決策建議,典型案例就是紅綠燈,紅綠燈告訴車輛前進這一行為是否安全。即使在相關法律缺失的情況下,我們仍然應該遵循紅綠燈的推薦結果,因為我們知道每個人都可以推斷出這是最好的選擇,闖紅燈是危險的行為。
這篇論文表明,此類均衡可以通過完全獨立執行的學習算法來實現,無需外部交通工程師,甚至在決策涉及多個步驟、決策者對于世界的狀態一知半解時也是如此。也就是說,存在此類 regret-minimizing 算法使 CE 在更廣泛的博弈類別中實現收斂,即擴展形式的博弈。這一結果解決了博弈論、計算機科學和經濟學領域中長期存在的開放性問題,并對涉及調停者的博弈產生顯著影響,如通過導航 app 高效制定交通路線。
2. Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystrom method
獲獎理由:
從大型矩陣中選擇小規模且具代表性的列向量子集是一個困難的組合問題,基于基數約束行列式點過程的方法可以給出實用的近似解。這篇論文推導出近似解近似因子的新型上下界。由于這些近似方法在機器學習領域中廣泛應用,因此這篇論文可能帶來巨大影響,并為核方法、特征選擇和神經網絡的雙下降現象提供新的理解方式。
隨著更多大型數據集變得可用,人們越來越依賴以簡明扼要的形式總結復雜數據。數據總結(data summarization)是識別數據中重要的樣例及屬性以高效表示數據的過程。它能夠用于從遺傳學數據集中選擇具有代表性的基因變體子集,也可用于從文本數據庫中選擇最具信息量的文檔。
此前的研究表明,數據總結是一個棘手的問題,對于有些數據集,不存在能夠在合理的時間范圍內很好地總結數據的算法。而這篇論文表明,這些分析過于悲觀。實際上,對于現實世界中的數據而言,生成可解釋總結的成本要低得多。該研究表明,未來的系統將能夠創建準確、可解釋且高效生成的數據總結,從而極大地提高我們吸收和處理復雜數據集的能力。
3. Language Models are Few-Shot Learners
獲獎理由:
用于估計序列中下一個詞概率的人工智能系統叫做「語言模型」。語言模型首次出現在 1950 年代,是連接自然語言與當時的新領域——信息論的理論構架。OpenAI 的這篇論文提出了 GPT-3——有史以來最大也最復雜的語言模型。這項研究表明,如果你使用史無前例的大量算力和數據讓語言模型獲得足夠的準確率,它也就獲得了無需額外訓練,僅使用簡單的自然語言提示即可解決大量任務的能力。比如回答簡單的問題、生成文章、確定電影評論是否積極,以及英法互譯等。
論文作者表明,GPT-3 在一些任務中的能力勝過其他模型,并用大量篇幅探討這項技術的優缺點。論文作者還考慮了這項技術的潛在有害影響,如低成本生成難以檢測的假新聞,模型因訓練數據偏見在種族、性別和宗教等敏感話題上產生傾向性。
我們研究在一種新穎實際的設定下對圖神經網絡的黑盒攻擊,我們限制攻擊者只能獲得部分節點的信息并且只能修改其中小部分的節點。在這樣的設定下,如何選擇節點變得愈發重要。我們證明圖神經網絡的結構歸納偏差能成為有效的黑盒攻擊源頭。具體來說,通過利用圖神經網路的向后傳播與隨機游走之間的聯系,我們表明基于梯度的常見白盒攻擊可以通過梯度和與PageRank類似的重要性分數之間的聯系而推廣到黑盒攻擊。在實踐中,我們發現基于這個重要性分數上確實很大的程度地增加了損失值,但是不能顯著提高分類錯誤的比率。我們的理論和經驗分析表明,損失值和誤分類率之間存在差異,即當受攻擊的節點數增加時,后者會呈現遞減的回報模式。因此,考慮到收益遞減效應,我們提出了一種貪心算法來校正這一重要性得分。實驗結果表明,所提出的選點程序在無需訪問模型參數或預測的前提下可以顯著提高常用數據集上常見GNN的誤分類率。
原文地址://arxiv.org/abs/2006.05057
我們研究在一種新穎實際的設定下對圖神經網絡的黑盒攻擊,我們限制攻擊者只能獲得部分節點的信息并且只能修改其中小部分的節點。在這樣的設定下,如何選擇節點變得愈發重要。我們證明圖神經網絡的結構歸納偏差能成為有效的黑盒攻擊源頭。具體來說,通過利用圖神經網路的向后傳播與隨機游走之間的聯系,我們表明基于梯度的常見白盒攻擊可以通過梯度和與PageRank類似的重要性分數之間的聯系而推廣到黑盒攻擊。在實踐中,我們發現基于這個重要性分數上確實很大的程度地增加了損失值,但是不能顯著提高分類錯誤的比率。我們的理論和經驗分析表明,損失值和誤分類率之間存在差異,即當受攻擊的節點數增加時,后者會呈現遞減的回報模式。因此,考慮到收益遞減效應,我們提出了一種貪心算法來校正這一重要性得分。實驗結果表明,所提出的選點程序在無需訪問模型參數或預測的前提下可以顯著提高常用數據集上常見GNN的誤分類率。
基于記憶的元學習是一種強大的技術,可以構建能夠快速適應目標分布中的任何任務的agents。之前的一項理論研究認為,這種顯著的表現是因為元訓練方案激勵agent以貝葉斯最優的方式行為。我們通過一些預測和敲詐任務對這一主張進行了實證研究。在理論計算機科學的啟發下,我們發現元學習和貝葉斯最優agent不僅行為相似,而且在某種意義上,它們甚至共享相似的計算結構,即一個agent系統可以近似地模擬另一個。此外,我們證明貝葉斯最優agent是元學習動態的不動點。我們的研究結果表明,基于記憶的元學習可以作為一種通用技術,用于數值逼近貝葉斯最優agent,也就是說,甚至對于我們目前沒有可處理模型的任務分布也是如此。
在“學習到學習”的范式中,基于記憶的元學習是一種創建代理的強大技術,它能快速適應從目標分布中抽取的任何任務。此外,有人聲稱元學習可能是創建泛化到看不見的環境的系統的關鍵工具。計算神經科學的研究也部分支持了這一觀點,其中對人類的實驗研究表明,快速的技能適應依賴于任務的變化。因此,理解元學習agent如何獲得它們的表征結構并執行它們的計算是至關重要的,因為它可以為架構選擇、訓練任務的設計提供信息,并解決人工智能中的泛化和安全性問題。
以前的理論工作認為,充分優化元學習目標的agent是通過構造的貝葉斯最優,因為元學習目標是貝葉斯最優目標的蒙特卡羅近似。這是令人震驚的,因為貝葉斯最優agent通過最優地權衡勘探和開發來實現收益最大化(或損失最小化)。該理論還提出了一個更強的、結構化的主張:即經過元訓練的agent在幕后執行貝葉斯更新,其中計算是通過嵌入在內存動態中的狀態機實現的,該狀態機跟蹤解決任務類所需的不確定性的充分統計信息。
在這里,我們著手實證綜述元學習agent的計算結構。然而,這帶來了不小的挑戰。人工神經網絡以其難以解釋的計算結構而臭名昭著:它們在具有挑戰性的任務中取得了卓越的表現,但這種表現背后的計算仍然難以捉摸。因此,盡管可解釋機器學習的許多工作集中在I/O行為或記憶內容上,只有少數通過仔細的定制分析來研究引起它們的內部動態(見例[12 18])。
為了應對這些挑戰,我們調整了理論計算機科學與機器學習系統的關系。具體來說,為了在計算級別[19]上比較agent,我們驗證它們是否可以近似地相互模擬。仿真的質量可以根據原始和仿真之間的狀態和輸出相似度來評估。
因此,我們的主要貢獻是研究基于RNN的元學習解決方案的計算結構。具體地說,我們比較元學習代理的計算和貝葉斯最優agent的計算,在他們的行為和內部表示的一套預測和強化學習任務已知的最優解決方案。我們在這些任務中展示了這一點:
元學習代理的行為類似貝葉斯最優agent(第4.1節)。也就是說,元學習agent做出的預測和行動實際上與貝葉斯最優agent無法區分。
在元訓練過程中,元學習者收斂于貝葉斯最優(第4.2節)。我們的經驗表明,貝葉斯最優策略是學習動態的不動點。
元學習代理代表像Bayes-optimal代理這樣的任務(第4.3節)。具體來說,計算結構對應于嵌入在(歐幾里得)內存空間中的狀態機,其中狀態編碼任務的充分統計信息并產生最優操作。我們可以用貝葉斯最優agent執行的計算來近似地模擬元學習代理執行的計算。
平移的不變性為卷積神經網絡注入了強大的泛化特性。然而,我們通常無法預先知道數據中存在哪些不變性,或者模型在多大程度上應該對給定的對稱組保持不變。我們展示了如何通過參數化增強分布和同時優化網絡參數和增強參數的訓練損失來學習不變性和等方差。通過這個簡單的過程,我們可以在一個很大的擴充空間中,僅在訓練數據上,恢復圖像分類、回歸、分割和分子性質預測上的正確不變量集和范圍。
【導讀】機器學習頂會 NeurIPS 2020, 是人工智能領域全球最具影響力的學術會議之一,因此在該會議上發表論文的研究者也會備受關注。據官方統計,今年NeurIPS 2020 共收到論文投稿 9454 篇,接收 1900 篇(其中 oral 論文 105 篇、spotlight 論文 280 篇),論文接收率為 20.1%。近期,所有paper list 放出,小編發現**對比學習(Contrastive Learning)**相關的投稿paper很多,這塊研究方向這幾年受到了學術界的廣泛關注,并且在CV、NLP等領域也應用頗多。
為此,這期小編為大家奉上NeurIPS 2020必讀的七篇對比學習相關論文——對抗自監督對比學習、局部對比學習、難樣本對比學習、多標簽對比預測編碼、自步對比學習、有監督對比學習
NeurIPS 2020 Accepted Papers://neurips.cc/Conferences/2020/AcceptedPapersInitial
1. Adversarial Self-Supervised Contrastive Learning
作者: Minseon Kim, Jihoon Tack, Sung Ju Hwang
摘要: 現有的對抗性學習方法大多使用類別標簽來生成導致錯誤預測的對抗性樣本,然后使用這些樣本來增強模型的訓練,以提高魯棒性。雖然最近的一些工作提出了利用未標記數據的半監督對抗性學習方法,但它們仍然需要類別標簽。然而,我們真的需要類別標簽來進行反向的深度神經網絡的健壯訓練嗎?本文提出了一種新的針對未標記數據的對抗性攻擊,使得該模型混淆了擾動數據樣本的實例級身份。此外,我們還提出了一種自監督對比學習(Contrastive Learning)框架來對抗性地訓練未標記數據的魯棒神經網絡,其目的是最大化數據樣本的隨機擴充與其實例對抗性擾動之間的相似度。我們在多個基準數據集上驗證了我們的方法-魯棒對比學習(RoCL),在這些數據集上,它獲得了與最新的有監督對抗性學習方法相當的魯棒準確率,并且顯著地提高了對黑盒和不可見類型攻擊的魯棒性。此外,與單獨使用自監督學習相比,RoCL進一步結合有監督對抗性損失進行聯合微調,獲得了更高的魯棒精度。值得注意的是,RoCL在穩健的遷移學習方面也顯示出令人印象深刻的結果。
網址:
2. Contrastive learning of global and local features for medical image segmentation with limited annotations
作者: Krishna Chaitanya, Ertunc Erdil, Neerav Karani, Ender Konukoglu
摘要: 有監督深度學習成功的一個關鍵要求是一個大的標記數據集——這是醫學圖像分析中難以滿足的條件。自監督學習(SSL)可以在這方面提供幫助,因為它提供了一種用未標記的數據預訓練神經網絡的策略,然后用有限的樣本標注對下游任務進行微調。對比學習是SSL的一種特殊變體,是一種學習圖像級表征的強大技術。在這項工作中,我們提出了一種策略,通過利用領域內一些特點,在標注有限的半監督場景下來擴展volumetric 醫療圖像分割的對比學習框架。具體地,我們提出了:(1)新穎的對比策略,它利用volumetric 醫學圖像之間的結構相似性(領域特定線索);(2)對比損失的局部信息來學習對每個像素分割有用的局部區域的獨特表示(問題特定線索)。我們在三個磁共振成像(MRI)數據集上進行了廣泛的評估。在有限的標注環境下,與其他的自監督和半監督學習技術相比,本文提出的方法有了很大的改進。當與簡單的數據增強技術相結合時,該方法僅使用兩個標記的MRI體積用于訓練,達到基準性能的8%以內,相當于用于訓練基準的訓練數據ACDC的4%。
網址:
3. LoCo: Local Contrastive Representation Learning
作者: Yuwen Xiong, Mengye Ren, Raquel Urtasun
摘要: 深度神經網絡通常執行端到端反向傳播來學習權重,該過程在跨層的權重更新步驟中創建同步約束(synchronization constraints),并且這種約束在生物學上是不可信的。無監督對比表示學習的最新進展指出一個問題,即學習算法是否也可以是局部的,即下層的更新不直接依賴于上層的計算。雖然Greedy InfoMax分別學習每個塊的局部目標,但我們發現,在最新的無監督對比學習算法中,可能是由于貪婪的目標以及梯度隔離,會一直損害readout的準確性。在這項工作中,我們發現,通過重疊局部塊堆疊在一起,我們有效地增加了解碼器的深度,并允許較高的塊隱式地向較低的塊發送反饋。這種簡單的設計首次縮小了局部學習算法和端到端對比學習算法之間的性能差距。除了標準的ImageNet實驗,我們還展示了復雜下游任務的結果,例如直接使用readout功能進行對象檢測和實例分割。
網址:
4. Hard Negative Mixing for Contrastive Learning
作者: Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, Diane Larlus
摘要: 對比學習已成為計算機視覺中自監督學習方法的重要組成部分。通過學習將同一圖像的兩個增強版本相互靠近地圖像嵌入,并將不同圖像的嵌入分開,可以訓練高度可遷移的視覺表示。最近的研究表明,大量的數據增強和大量的負樣本集對于學習這樣的表征都是至關重要的。同時,無論是在圖像層面還是在特征層面,數據混合策略都通過合成新的示例來改進監督和半監督學習,迫使網絡學習更健壯的特征。在這篇文章中,我們認為對比學習的一個重要方面,即hard negatives的影響,到目前為止被忽視了。為了獲得更有意義的負樣本,目前最流行的對比自監督學習方法要么大幅增加batch sizes大小,要么保留非常大的內存庫;然而,增加內存需求會導致性能回報遞減。因此,我們從更深入地研究一個表現最好的框架開始,并展示出證據,為了促進更好、更快的學習,需要更難的難樣本(harder negatives)。基于這些觀察結果,并受到數據混合策略成功的激勵,我們提出了特征級別的難例混合策略,該策略可以用最小的計算開銷在運行中進行計算。我們在線性分類、目標檢測和實例分割方面對我們的方法進行了詳盡的改進,并表明使用我們的難例混合過程提高了通過最先進的自監督學習方法學習的視覺表示的質量。
代碼:
網址:
5. Multi-label Contrastive Predictive Coding
作者: Jiaming Song, Stefano Ermon
摘要: 變量互信息(mutual information, MI)估計器廣泛應用于對比預測編碼(CPC)等無監督表示學習方法中。MI的下界可以從多類分類問題中得到,其中critic試圖區分從潛在聯合分布中提取的正樣本和從合適的建議分布中提取的(m?1)個負樣本。使用這種方法,MI估計值超過log m,因此有效下界可能會嚴重低估,除非m非常大。為了克服這一局限性,我們引入了一種新的基于多標簽分類問題的估計器,其中critic需要同時聯合識別多個正樣本。我們證明了在使用相同數量的負樣本的情況下,多標簽CPC能夠超過log m界,同時仍然是互信息的有效下界。我們證明了所提出的方法能夠帶來更好的互信息估計,在無監督表示學習中獲得經驗上的改進,并且在13個任務中超過了最先進的10個知識提取方法。
網址:
6. Self-paced Contrastive Learning with Hybrid Memory for Domain Adaptive Object Re-ID
作者: Yixiao Ge, Feng Zhu, Dapeng Chen, Rui Zhao, Hongsheng Li
摘要: 域自適應目標Re-ID旨在將學習到的知識從已標記的源域轉移到未標記的目標域,以解決開放類(open-class)的重識別問題。雖然現有的基于偽標簽的方法已經取得了很大的成功,但是由于域的鴻溝和聚類性能的不理想,它們并沒有充分利用所有有價值的信息。為了解決這些問題,我們提出了一種新的具有混合記憶的自適應對比學習框架。混合存儲器動態地生成用于學習特征表示的源域類級、目標域簇級和未聚類實例級監督信號。與傳統的對比學習策略不同,該框架聯合區分了源域類、目標域簇和未聚類實例。最重要的是,所提出的自適應方法逐漸產生更可靠的簇來提煉混合記憶和學習目標,這被證明是我們方法的關鍵。我們的方法在目標 Re-ID的多域適配任務上的性能優于現有技術,甚至在源域上不需要任何額外的標注就能提高性能。在Market1501和MSMT17數據上,我們的無監督目標Re-ID的通用版本分別比最先進的算法高出16.7%和7.9%。
代碼:
網址:
7. Supervised Contrastive Learning
作者: Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, Dilip Krishnan
摘要: 交叉熵是圖像分類模型監督訓練中應用最廣泛的損失函數。在本文中,我們提出了一種新的訓練方法,該方法在不同的體系結構和數據增強的監督學習任務中始終優于交叉熵。我們修正了批量對比損失,它最近被證明在自監督環境下學習強大的表示是非常有效的。因此,我們能夠比交叉熵更有效地利用標簽信息。屬于同一類的點簇在嵌入空間中被拉在一起,同時推開來自不同類的樣本簇。除此之外,我們還利用了大的batch sizes和標準化嵌入等關鍵因素,這些因素已被證明有利于自監督學習。在ResNet-50和ResNet-200上,我們的性能都比交叉熵高出1%以上,在使用 AutoAugment數據增強的方法中創造了78.8%的新技術水平。在校準和準確度方面,這一損失也顯示出在標準基準上對自然損壞的穩健性有明顯的好處。與交叉熵相比,我們的監督對比損失對諸如優化器或數據增強等超參數設置更穩定。
網址:
我們考慮這樣一個問題:你如何為對比學習抽取好的負樣本例子?我們認為,與度量學習一樣,學習對比表示法受益于硬負樣本(即,點很難與錨點區分)。使用硬負樣本的關鍵挑戰是對比方法必須保持無監督,使得采用現有的使用標簽信息的負樣本抽樣策略不可行。作為回應,我們開發了一種新的無監督的方法來選擇硬負樣本,在那里用戶可以控制硬負樣本的數量。這種抽樣的極限情況會導致對每個類進行緊密聚類的表示,并將不同的類推到盡可能遠的地方。該方法提高了跨模態的下游性能,只需要少量的額外代碼來實現,并且沒有引入計算開銷。