如何將經(jīng)典算法與人工智能結(jié)合？NeurIPS 2021

點(diǎn)擊下方“AI算法與圖像處理”，一起進(jìn)步！
重磅干貨，第一時(shí)間送達(dá)

目前的監(jiān)督學(xué)習(xí)模型是基于label作為學(xué)習(xí)目標(biāo)，那么是否可以添加經(jīng)典算法（如排序）來作為約束？

深度學(xué)習(xí)可以不斷優(yōu)化，很重要的一點(diǎn)是有“反饋”，通過梯度回傳不斷優(yōu)化，那么本文的大部分內(nèi)容在將如何在加入經(jīng)典算法之后，如何利用數(shù)學(xué)方法轉(zhuǎn)換，讓模型同樣擁有“反饋”的能力?。。?/p>

文章很長，共一萬多字。花了三個(gè)晚上才完成，希望能幫忙轉(zhuǎn)發(fā)一下，謝謝啦

本文是來自 NeurIPS 2021 上的工作介紹，具體的報(bào)告視頻已上傳到 B 站

https://www.bilibili.com/video/BV1sb4y187YV/

下面的內(nèi)容我也是第一次見到，試著翻譯成人話，理解有誤的地方還請(qǐng)見諒

論文：https://arxiv.org/pdf/2110.05651.pdf

代碼：https://github.com/Felix-Petersen/algovision

標(biāo)題：Learning with Algorithmic Supervision via Continuous Relaxations

摘要

最近，將算法組件集成到神經(jīng)體系結(jié)構(gòu)中得到了越來越多的關(guān)注，因?yàn)樗?strong>允許使用新形式的監(jiān)督（如排序約束或輪廓）來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，而不是使用grouth真值標(biāo)簽。該領(lǐng)域的許多方法關(guān)注于特定任務(wù)的持續(xù)放松，并在這方面顯示出有希望的結(jié)果。但對(duì)單個(gè)任務(wù)的關(guān)注也限制了所提出概念在狹窄應(yīng)用范圍內(nèi)的適用性。在這項(xiàng)工作中，我們基于這些想法提出了一種方法，允許將算法集成到基于離散條件的一般近似的端到端可訓(xùn)練神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中。為此，我們?cè)诳刂平Y(jié)構(gòu)（如條件語句、循環(huán)和索引）中放寬這些條件，以便生成的算法是平滑可微的。為了獲得有意義的梯度，通過logistic分布對(duì)每個(gè)相關(guān)變量進(jìn)行擾動(dòng)，并近似該擾動(dòng)下的期望值。我們?cè)谒膫€(gè)挑戰(zhàn)性任務(wù)上評(píng)估了所提出的連續(xù)松弛法模型，并表明它能夠跟上為每個(gè)單獨(dú)任務(wù)專門設(shè)計(jì)的放松。

1、簡介

人工神經(jīng)網(wǎng)絡(luò)已顯示出其解決各種問題的能力，從計(jì)算機(jī)科學(xué)中的經(jīng)典任務(wù)（如機(jī)器翻譯[1]和目標(biāo)檢測(cè)[2]）到科學(xué)中的許多其他主題（如蛋白質(zhì)折疊[3]）。同時(shí)，存在經(jīng)典算法，其通?；诮o定輸入和預(yù)定義控制結(jié)構(gòu)（例如排序、最短路徑計(jì)算等）來解決預(yù)定義任務(wù)。最近，通過將算法概念集成到神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中，研究開始將這兩個(gè)要素結(jié)合起來。這些方法允許使用替代監(jiān)督策略訓(xùn)練神經(jīng)網(wǎng)絡(luò)，例如通過可微渲染器學(xué)習(xí)3D表征[4]，[5]或使用排序信息訓(xùn)練神經(jīng)網(wǎng)絡(luò)[6]，[7]。我們將這些將算法整合到訓(xùn)練目標(biāo)中的替代監(jiān)督策略統(tǒng)一為算法監(jiān)督：

定義 1 （Algorithmic Supervision）

在算法監(jiān)督中，將算法應(yīng)用于模型的預(yù)測(cè)，并監(jiān)督算法的輸出。相反，在直接監(jiān)督中，模型的預(yù)測(cè)是直接監(jiān)督的。這如圖1所示。

一般來說，為了允許使用集成算法對(duì)神經(jīng)架構(gòu)進(jìn)行端到端訓(xùn)練，挑戰(zhàn)在于估計(jì)各個(gè)算法的梯度，例如，通過可微近似。

在這里，大多數(shù)解決方案都是針對(duì)特定問題定制的，例如，可微排序或渲染。但最近也提出了更通用的框架，用于估計(jì)組合優(yōu)化器的梯度。此類方法的示例包括Vlastelica等人[8]提出的黑盒組合解算器的微分，以及Berthat等人[9]提出的通過隨機(jī)擾動(dòng)輸入來微分優(yōu)化器。這兩種方法都集中于一個(gè)問題，即需要估計(jì)算法的梯度，以便對(duì)包括它在內(nèi)的神經(jīng)結(jié)構(gòu)進(jìn)行端到端的訓(xùn)練。為了解決這個(gè)問題，Vlastelica等人[8]通過一步線性化方法估計(jì)優(yōu)化器的梯度，該方法考慮了與優(yōu)化器輸出相關(guān)的梯度，從而可以集成任何現(xiàn)成的組合優(yōu)化器。Berthet等人[9]通過隨機(jī)噪聲干擾離散解算器的輸入來估計(jì)梯度。

在此背景下，我們提出了一種使算法可微并估計(jì)其梯度的方法。具體來說，我們提出了不同算法概念的連續(xù)松弛（continuous relaxations），如比較器、條件語句、有界和無界循環(huán)以及索引。為此，我們?cè)陔x散算法中通過logistic分布擾動(dòng)這些變量，我們要計(jì)算梯度。這使我們能夠估計(jì)算法輸出采樣自由和封閉形式的預(yù)期值，例如，與通過蒙特卡羅采樣方法（例如[9]）近似分布的方法相比。為了保持計(jì)算的可行性，我們通過在條件塊序列中合并每個(gè)條件塊之后的計(jì)算路徑來近似期望值。對(duì)于嵌套的條件塊，我們計(jì)算準(zhǔn)確的期望值，而不合并條件情況。這種折衷允許定期合并路徑，從而減少了跟蹤所有可能路徑組合的需要。當(dāng)我們?cè)谠L問變量時(shí)對(duì)其擾動(dòng)進(jìn)行建模時(shí)，所有分布都是獨(dú)立的，這與建模輸入擾動(dòng)的情況形成對(duì)比，在這種情況下，所有計(jì)算路徑都必須單獨(dú)處理。

為了演示實(shí)際方面，我們將所提出的方法應(yīng)用于四項(xiàng)任務(wù)中，這四項(xiàng)任務(wù)利用算法監(jiān)督來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，即排序監(jiān)督[6]、[7]、[10]、最短路徑監(jiān)督[8]、[9]、輪廓監(jiān)督（可微渲染）[4]、[5]、[11]，最后是Levenshtein距離監(jiān)控。雖然前三個(gè)設(shè)置基于該領(lǐng)域現(xiàn)有的基準(zhǔn)，但我們介紹了第四個(gè)實(shí)驗(yàn)，以展示該思想在可微動(dòng)態(tài)規(guī)劃領(lǐng)域的新算法任務(wù)中的應(yīng)用。在后者中，來自EMNIST數(shù)據(jù)集[12]的兩個(gè)串聯(lián)字符序列之間的Levenshtein距離受到監(jiān)督，而單個(gè)字母保持無監(jiān)督狀態(tài)。我們表明，所提出的系統(tǒng)能夠在排序監(jiān)督方面優(yōu)于當(dāng)前最先進(jìn)的方法，而在最短路徑監(jiān)督和輪廓監(jiān)督方面則具有可比性。

2、相關(guān)工作

在下文中，我們將重點(diǎn)關(guān)注那些為本工作中考慮的任務(wù)提供“放松（relaxations）”的工作。最后，我們回顧了一些關(guān)于平滑程序解釋的早期工作。

Sorting Supervision

Grover等人首先提出了用分類監(jiān)督訓(xùn)練神經(jīng)網(wǎng)絡(luò)的任務(wù)[6]。在這種情況下，給出了一組基于串聯(lián)MNIST數(shù)字[29]的四位數(shù)，任務(wù)是找到從圖像到標(biāo)量的保序映射。這里，CNN應(yīng)該為n個(gè)四位數(shù)中的每一個(gè)預(yù)測(cè)一個(gè)標(biāo)量，這樣它們的順序在預(yù)測(cè)的標(biāo)量中保持不變。對(duì)于訓(xùn)練，僅以輸入圖像的grouth真值順序的形式給出排序監(jiān)督，而其絕對(duì)值保持無監(jiān)督。Grover等人[6]通過將置換矩陣放松為雙隨機(jī)矩陣來解決這一問題。Cuturi等人[7]在基準(zhǔn)測(cè)試中發(fā)現(xiàn)了這一點(diǎn)，并通過使用正則化最優(yōu)傳輸算法近似排序問題，提出了一種可微指標(biāo)。

Silhouette Supervision

計(jì)算機(jī)視覺中的一項(xiàng)工作是三維無監(jiān)督三維重建的可微渲染器。在這里，最近的方法已經(jīng)提出了可微渲染器，用于在13類ShapeNet數(shù)據(jù)集[30]上僅使用二維輪廓監(jiān)督的三維網(wǎng)格重建[4]，[5]。Kato等人[5]提出了一種渲染器，在該渲染器中，光柵化的代理梯度被近似化，以通過輪廓監(jiān)控以及3D樣式轉(zhuǎn)換執(zhí)行3D網(wǎng)格重建。Liu等人[4]通過使用可微聚合過程，提出了一種無代理梯度的可微渲染器，并將其應(yīng)用于三維網(wǎng)格重建以及姿勢(shì)/形狀優(yōu)化。

Shortest-Path Supervision

Vlastelica等人[8]和Berthet等人[9]提出的兩項(xiàng)工作提出了估算現(xiàn)成優(yōu)化器梯度的方法。在這種情況下，Vlastelica等人[8]提出了一個(gè)最短路徑監(jiān)控實(shí)驗(yàn)，在該實(shí)驗(yàn)中，針對(duì)每種類型的地形，以不同的代價(jià)給出地形圖像，任務(wù)是預(yù)測(cè)從左上角到相反角的最短路徑。將最短路徑算法集成到神經(jīng)結(jié)構(gòu)中，可以使神經(jīng)網(wǎng)絡(luò)生成最短路徑算法用于預(yù)測(cè)最短路徑的地形的成本嵌入。Vlastelica等人[8]通過發(fā)現(xiàn)Dijkstra算法的線性化[31]來解決這一問題，他們可以對(duì)其進(jìn)行區(qū)分。Berthat等人[9]研究了這個(gè)問題，通過隨機(jī)擾動(dòng)最短路徑優(yōu)化問題的輸入，為Dijkstra算法生成梯度估計(jì)。

Smooth Interpretation

在計(jì)算機(jī)輔助驗(yàn)證領(lǐng)域的另一項(xiàng)工作中，Chaudhuri等人[32]，[33]提出了一種基于高斯分布隨機(jī)擾動(dòng)程序輸入的程序平滑方法。這里，通過程序變換傳播初始高斯擾動(dòng)，并通過高斯混合近似擾動(dòng)輸出的最終分布。然后使用無梯度Nelder-Mead優(yōu)化方法對(duì)平滑函數(shù)進(jìn)行優(yōu)化。我們的方法的主要區(qū)別在于，我們用邏輯分布擾動(dòng)所有相關(guān)變量（而不是輸入），并將其用于基于梯度的優(yōu)化。

3、方法

為了不斷放松算法，從而使其可微，我們放松了所有想要微分的值為logistic分布。我們選擇logistic分布，因?yàn)樗峁┝藘蓚€(gè)獨(dú)特的特性，使其特別適合于手頭的任務(wù)：

（1）logistic分布比正態(tài)分布有更大的尾部，這允許更大的概率質(zhì)量，因此當(dāng)兩個(gè)比較值彼此遠(yuǎn)離時(shí)，有更大的梯度。

（2） logistic分布的累積密度函數(shù)（CDF）是logistic-sigmoid函數(shù)，可解析計(jì)算，其梯度易于計(jì)算。這與正態(tài)分布的CDF形成對(duì)比，正態(tài)分布沒有閉合形式，通常通過多項(xiàng)式近似

具體地說，我們“放松“任何值 x（想要計(jì)算梯度的值）， 是通過添加一個(gè)服從logistic 分布的隨機(jī)變量方式：

其中β是逆溫度參數(shù)，對(duì)于

基于此，我們可以放松一個(gè)離散條件語句，例如，基于條件x<c和常數(shù)c∈ R、 詳情如下:

式中，σ是logistic(sigmoid)函數(shù)σ（x）=1/（1+e）^?xβ）。在本例中，隨著x的增加，結(jié)果從y平滑過渡到z。因此，結(jié)果的導(dǎo)數(shù)wrt。x定義為

因此，如果if案例減少了損失，梯度下降法可以影響條件（?x<c）保持，或者如果else案例減少了損失函數(shù)，則影響條件失敗。

在本例中，y和z不僅可以是標(biāo)量值，還可以是算法的結(jié)果或算法本身的一部分。這引入了松弛程序流的遞歸形式，其中算法的部分通過凸組合進(jìn)行組合：

其中，f和g表示函數(shù)、算法或語句序列，這些函數(shù)、算法或語句通過值調(diào)用對(duì)所有變量集s進(jìn)行操作，并返回所有變量集s。此操作的結(jié)果可能會(huì)覆蓋所有變量集（s:=[…]），也可能會(huì)在嵌套的條件語句中使用。

在引入上述if-else語句之后，我們將這一思想擴(kuò)展到循環(huán)，從而將松弛程序流的形式主義擴(kuò)展到圖靈完整性。在固定循環(huán)中，即具有預(yù)定義迭代次數(shù)的循環(huán)中，由于只有一條計(jì)算路徑，因此不需要松弛，因此，可以通過展開來處理固定循環(huán)。

更復(fù)雜的情況是條件無界循環(huán)，即While循環(huán)，只要條件成立就執(zhí)行。為此，讓我∈N是應(yīng)用i乘以循環(huán)內(nèi)容后所有變量的序列。也就是說，對(duì)于所有變量s的初始集，s0=s，并且si=f（si?1） ，其中f是循環(huán)的內(nèi)容，即函數(shù)、算法或語句序列。設(shè)a，b分別表示s的訪問變量，即s[a]，s[b]。通過遞歸地應(yīng)用if-else語句的規(guī)則，我們獲得了無界循環(huán)的以下規(guī)則：

這里，（a）是達(dá)到第i次迭代的概率，（b）是不超過i次迭代的概率。（a）和（b）合在一起是指在應(yīng)用i乘以f（即si）之后，有i次迭代對(duì)所有變量的狀態(tài)進(jìn)行加權(quán)的概率。在計(jì)算上，我們?cè)u(píng)估無窮級(jí)數(shù)，直到執(zhí)行概率（a）在數(shù)值上變得可以忽略，或者達(dá)到預(yù)定義的最大迭代次數(shù)。同樣，結(jié)果可以覆蓋所有變量集（s:=[…]），也可以用于嵌套的條件語句中。

Complexity and Merging of Paths

為了計(jì)算一個(gè)算法在其變量的logistic擾動(dòng)下的精確期望值，必須單獨(dú)計(jì)算所有計(jì)算路徑，以考慮依賴性。然而，這將導(dǎo)致指數(shù)復(fù)雜性。因此，我們計(jì)算嵌套條件塊的精確期望值，但對(duì)于連續(xù)條件塊，我們?cè)诿總€(gè)塊的末尾合并計(jì)算路徑。這使得順序條件塊的數(shù)量具有線性復(fù)雜性，而只有嵌套條件塊的最大深度才具有指數(shù)復(fù)雜性。請(qǐng)注意，順序條件塊的數(shù)量通常遠(yuǎn)大于條件塊的深度，例如，數(shù)百或數(shù)千個(gè)順序塊，最大深度僅為2? 在我們的實(shí)驗(yàn)中。依賴關(guān)系的一個(gè)例子是表達(dá)式a:=（f（x），如果i<0，則為g（x））；b:=（如果a<0，則為0；如果a<0，則為a2），它包含兩個(gè)連續(xù)條件塊之間的依賴關(guān)系，這在我們的近似中引入了誤差。一般來說，我們的形式主義也支持對(duì)順序條件塊之間的依賴關(guān)系進(jìn)行建模，但實(shí)際上，對(duì)于整個(gè)算法來說，它可能變得很難處理。此外，如果算法依賴于特定的依賴關(guān)系，則可以明確地考慮相關(guān)的依賴關(guān)系。

Perturbations of Variables vs. Perturbations of Inputs

注意，變量擾動(dòng)建模與輸入擾動(dòng)建模不同。差異變得明顯的一種情況是，例如，（?x<x）。在對(duì)輸入擾動(dòng)進(jìn)行建模時(shí)，該條件將具有很強(qiáng)的隱式條件依賴性，其計(jì)算概率為0%。然而，在這項(xiàng)工作中，我們沒有對(duì)輸入的擾動(dòng)進(jìn)行建模，而是在每次訪問變量時(shí)對(duì)變量的擾動(dòng)進(jìn)行建模，以便兩次訪問一個(gè)變量是獨(dú)立同分布的（iid）。因此，（?x<x）的概率為50%。為了最小化松弛的近似誤差，僅應(yīng)松弛需要梯度的變量。

3.1 Relaxed Comparators

到目前為止，我們只考慮了比較器 <. > 通過交換參數(shù)進(jìn)行跟蹤

Relaxed Equality

對(duì)于相等算子＝，我們考慮兩個(gè)分布 a? ～ Logistic(a, 1/β) 和b? ～ Logistic(b, 1/β) ，我們要檢查相似性/相等性。給定值a，我們計(jì)算a是來自 b? 而不是 a? 的樣本的可能性。如果a從a和b中提取的可能性相等，則a和b相等。如果a不太可能從b中提取，則a和b是不相等的。為了計(jì)算a從 b?和 a?中提取的可能性是否相等，我們?nèi)從b?中提取的概率（flog（a；b，1/β））和a從a?中提取的概率（flog（a；a，1/β））之間的比率：

這些松弛比較器如圖2所示。為了計(jì)算合取概率（即and）或析取概率（即or），我們分別使用乘積或概率和。這對(duì)應(yīng)于獨(dú)立事件的交集/并集。式9的另一種推導(dǎo)是?（a<b）和?（a>b）的歸一化連接。

Relaxed Maximum

為了比較兩個(gè)以上的元素并放松arg max函數(shù)，我們使用多項(xiàng)式logistic分布，也稱為softmax分布。

為了放松max操作，我們使用arg max/softmax的乘積和相應(yīng)的向量。

Comparing Categorical Variables

比較分類概率分布 X ∈ [0, 1]^n 具有分類概率分布y，我們考慮兩種情況：如果y∈ {0，1}^n，即Y是one-hot，我們可以使用X和Y的內(nèi)積來獲得它們的聯(lián)合概率。然而，如果Y /∈ {0, 1}^n,，即Y不是one-hot，即使X=Y內(nèi)積也不能是1，但如果X=Y，則希望概率為1。因此，我們（L2）在取內(nèi)積之前對(duì)X和Y進(jìn)行歸一化，內(nèi)積對(duì)應(yīng)于余弦相似性。比較分類概率分布的應(yīng)用示例見第4.4節(jié)中的Levenshtein距離實(shí)驗(yàn)。

3.2 Relaxed Indexing

由于向量、數(shù)組和張量對(duì)于算法和機(jī)器學(xué)習(xí)是必不可少的，我們還將松弛索引形式化。為此，我們介紹了實(shí)值索引和分類索引。

Real-Valued Indexing

在松弛算法中，指數(shù)可以從實(shí)數(shù)集合中提取，因?yàn)樗鼈兛梢允怯?jì)算的凸組合或?qū)嵵递斎搿＿@是一個(gè)挑戰(zhàn)，因?yàn)樗枰诙鄠€(gè)值之間進(jìn)行插值。直接方法是網(wǎng)格采樣，使用雙線性或雙三次插值來插值。例如，神經(jīng)圖靈機(jī)使用線性插值進(jìn)行實(shí)值索引[35]。然而，在雙線性或雙三次插值中，超出陣列中直接（或下一個(gè)）鄰域的關(guān)系不建模，也不建模邏輯擾動(dòng)。因此，我們用i值索引n維張量A∈ R n通過logistic擾動(dòng)，通過應(yīng)用與logistic濾波器g的卷積，得到結(jié)果為(g ? A)(i)  。張量a與邏輯濾波器g的卷積（不要與神經(jīng)網(wǎng)絡(luò)中的離散卷積混淆）產(chǎn)生在點(diǎn) i 處計(jì)算的函數(shù)t i ∈ R^n。我們選擇logistic濾波器而不是雙線性和雙三次濾波器，因?yàn)槲覀儗?duì)logistic擾動(dòng)進(jìn)行建模，另外，因?yàn)殡p線性和雙三次濾波器只有緊支撐，而logistic濾波器提供無限支撐。這使得建模關(guān)系超越了下一個(gè)鄰居，并且更靈活，因?yàn)槟鏈囟圈驴梢葬槍?duì)各自的應(yīng)用進(jìn)行調(diào)整。為了穩(wěn)定性，我們對(duì)用于插值各個(gè)索引值的系數(shù)進(jìn)行歸一化，使其總和為1：

式中，j是張量A的所有有效指數(shù)。為了防止優(yōu)化算法利用混疊效應(yīng)，我們僅在前向傳遞中將系數(shù)除以其和，但在后向傳遞（梯度計(jì)算）中忽略這一點(diǎn)。實(shí)值索引顯示在圖3中，將其與硬索引進(jìn)行比較

Relaxed Categorical Indexing

如果給出了索引上的分類概率分布，例如，由argmax或其松弛softmax計(jì)算，則可以使用分類索引。這里，邊緣分類分布被用作索引張量的權(quán)重

請(qǐng)注意，實(shí)值索引假設(shè)索引數(shù)組遵循語義順序，例如時(shí)間序列、圖像或網(wǎng)格中的位置。相反，如果數(shù)組包含分類信息（如圖的節(jié)點(diǎn)），則應(yīng)使用分類索引對(duì)值進(jìn)行索引，因?yàn)樗鼈兊泥徲蚴侨我獾摹?/span>

3.3 Complexity and Runtime Considerations

在運(yùn)行時(shí)間方面，必須注意，運(yùn)行時(shí)間優(yōu)化算法（例如Dijkstra）通常不會(huì)改善松弛的運(yùn)行時(shí)間，因?yàn)閷?duì)于建議的連續(xù)松弛，必須執(zhí)行算法中的所有情況。因此，減少計(jì)算成本的附加條件不會(huì)改善運(yùn)行時(shí)，因?yàn)閮煞N（所有）情況都會(huì)執(zhí)行。相反，如果一個(gè)算法以一個(gè)固定的執(zhí)行順序來解決一個(gè)問題，它將變得非常有益。另一方面，針對(duì)運(yùn)行時(shí)優(yōu)化算法會(huì)導(dǎo)致在最快的執(zhí)行路徑之間進(jìn)行插值。這種優(yōu)化不能改善梯度，而是降低梯度，因?yàn)樗且环N額外的近似，并產(chǎn)生與運(yùn)行時(shí)啟發(fā)式相關(guān)的梯度。例如，當(dāng)放松Dijkstra最短路徑算法時(shí)，在訪問節(jié)點(diǎn)的不同順序之間存在插值，這是使Dijkstra快速的啟發(fā)式方法。然而，如果我們必須遵循所有路徑（計(jì)算松弛度），它可能導(dǎo)致組合爆炸。此外，通過在這些可選順序之間插值，引入了大量的不確定性，并且梯度也將取決于訪問節(jié)點(diǎn)的順序，這兩者都是不可取的。此外，執(zhí)行相當(dāng)嚴(yán)格的算法可以在GPU上并行執(zhí)行，這樣它們可以比CPU上運(yùn)行時(shí)優(yōu)化的順序算法更快。因此，從運(yùn)行時(shí)和梯度質(zhì)量的角度來看，我們更喜歡執(zhí)行結(jié)構(gòu)基本固定且沒有運(yùn)行時(shí)優(yōu)化的簡單算法。

4、實(shí)驗(yàn)

我們?cè)诟鞣N算法監(jiān)督實(shí)驗(yàn)中評(píng)估了所提出的方法，其概述如圖4所示。對(duì)于每個(gè)實(shí)驗(yàn)，我們首先簡要描述任務(wù)和各自的輸入數(shù)據(jù)以及使用的松弛算法。為了允許應(yīng)用于各種任務(wù)，我們需要為每個(gè)算法找到合適的逆溫度β。作為啟發(fā)，我們從β =√k，其中k是算法中松弛變量的出現(xiàn)次數(shù)，這是良好近似和充分松弛之間的平衡，以獲得良好的梯度估計(jì)。對(duì)于每個(gè)任務(wù)，我們?cè)隍?yàn)證集上調(diào)優(yōu)此參數(shù)。所有算法的偽代碼以及關(guān)于松弛和逆溫度參數(shù)的附加信息可在補(bǔ)充材料中找到。

4.1 Sorting Supervision

在排序監(jiān)督實(shí)驗(yàn)中，給出了一組基于級(jí)聯(lián)MNIST數(shù)字[29]的四位數(shù)字，任務(wù)是找到從圖像到標(biāo)量的保序映射。CNN學(xué)習(xí)為n個(gè)四位數(shù)中的每一個(gè)預(yù)測(cè)一個(gè)標(biāo)量，這樣它們的順序在預(yù)測(cè)的標(biāo)量中保持不變。為此，僅以輸入圖像的基本真值順序的形式提供排序監(jiān)督，而其絕對(duì)值保持無監(jiān)督。這遵循Grover等人[6]和Cuturi等人的協(xié)議。

舉個(gè)例子：

使用我們的方法，我們放松了成熟的穩(wěn)定排序算法Bubble sort[37]，該算法通過迭代遍歷列表并交換任意兩個(gè)相鄰元素（如果它們的順序不正確），直到在一次迭代中不再有交換操作為止。我們包含一個(gè)變量，如果發(fā)生交換操作，通過將輸入序列設(shè)置為true來跟蹤輸入序列的順序是否正確。由于松弛，該變量是一個(gè)介于0和1之間的浮點(diǎn)數(shù)，對(duì)應(yīng)于預(yù)測(cè)正確排序的概率（在變量擾動(dòng)下）。我們用這個(gè)概率作為損失函數(shù)。該變量等于不需要交換操作的概率，因此L=1? Q p∈P（1）? p） 對(duì)于每個(gè)潛在交換p的概率p∈ P.這樣，訓(xùn)練目標(biāo)就變成對(duì)輸入序列進(jìn)行排序，因此，神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)的分?jǐn)?shù)對(duì)應(yīng)于監(jiān)督偏序。事實(shí)上，冒泡排序中的交換數(shù)對(duì)應(yīng)于肯德爾τ系數(shù)，它指示序列的排序程度。請(qǐng)注意，例如，快速排序沒有此屬性，因?yàn)榧词剐蛄幸雅判?，它也?huì)執(zhí)行交換。

我們強(qiáng)調(diào)，經(jīng)過訓(xùn)練的神經(jīng)網(wǎng)絡(luò)的任務(wù)不是對(duì)序列進(jìn)行排序，而是預(yù)測(cè)每個(gè)元素的得分，從而使排序/排名與監(jiān)督排序/排名相對(duì)應(yīng)。雖然松弛算法可以正確排序輸入，但在評(píng)估時(shí)，在[6]和[7]設(shè)置之后，我們使用argsort方法測(cè)試神經(jīng)網(wǎng)絡(luò)產(chǎn)生的輸出是否符合基本真值偏序。我們使用與[6]和[7]相同的網(wǎng)絡(luò)體系結(jié)構(gòu)。這里，我們只對(duì)n=5的逆溫度進(jìn)行優(yōu)化，得到β=8，并對(duì)所有其他n進(jìn)行修正。對(duì)于培訓(xùn)，我們使用學(xué)習(xí)率為10的Adam優(yōu)化器[38]?4用于1.5·105和1.5·106之間的迭代。

我們使用與Grover等人[6]和Cuturi等人[7]相同的網(wǎng)絡(luò)體系結(jié)構(gòu)和評(píng)估指標(biāo)，針對(duì)最先進(jìn)的手工放松排序操作，評(píng)估我們的方法。如選項(xiàng)卡中所示。1，我們的一般公式優(yōu)于state-of-the-art  的手工放松分揀操作，用于排序監(jiān)督。

4.2 Shortest-Path Supervision

對(duì)于2D地形上的最短路徑監(jiān)控，我們遵循Vlastelica等人[8]和Berthet等人[9]的設(shè)置，并使用10000塊大小為96×96的魔獸世界地形（代表大小為12×12的地形網(wǎng)格）的數(shù)據(jù)集。給定地形圖像（例如，圖5第一），目標(biāo)是根據(jù)隱藏成本矩陣（例如，圖5第三）預(yù)測(cè)最短路徑（例如，圖5第三）。為此，監(jiān)督最短路徑的12×12二元矩陣，而隱代價(jià)矩陣僅用于確定最短路徑。在他們的工作中，Vlastelica等人[8]和Berthet等人[9]表明，集成和區(qū)分最短路徑算法可以通過允許神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)成本矩陣來改進(jìn)結(jié)果，通過該算法可以計(jì)算最短路徑。這比ResNet基線的性能要好得多，在ResNet基線中，最短路徑只能由神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)（見表2）。

對(duì)于這項(xiàng)任務(wù)，我們將Bellman-Ford算法[39]放松為8鄰域、節(jié)點(diǎn)權(quán)重和路徑重建，補(bǔ)充材料中給出了詳細(xì)信息。對(duì)于監(jiān)督最短路徑和松弛Bellman-Ford算法產(chǎn)生的路徑之間的損失，我們使用`2損失。為了說明通過我們的方法創(chuàng)建的最短路徑，并將其與Berthet等人[9]通過擾動(dòng)優(yōu)化器創(chuàng)建的最短路徑進(jìn)行比較，我們?cè)趫D5中顯示了兩個(gè)反向溫度的追溯最短路徑示例（從中到右）。

我們使用與Vlastelica等人[8]和Berthet等人[9]相同的ResNet網(wǎng)絡(luò)體系結(jié)構(gòu)，并且還訓(xùn)練50個(gè)epoch，batch大小為70。我們使用β=25的逆溫度。

如選項(xiàng)卡中所示。2，我們的松弛在預(yù)測(cè)到的最優(yōu)最短路徑的成本比上優(yōu)于所有基線，并且在最短路徑精確匹配精度上達(dá)到了僅次于擾動(dòng)優(yōu)化器的次優(yōu)結(jié)果

4.3 Silhouette Supervision

從單個(gè)二維圖像重建三維模型是計(jì)算機(jī)視覺中的一項(xiàng)重要任務(wù)。最近的工作[4]，[5]采用可微渲染器，通過反饋重建輪廓是否與輸入圖像匹配來訓(xùn)練三維重建網(wǎng)絡(luò)。具體而言，最近的工作已經(jīng)在ShapeNet[30]的13個(gè)對(duì)象類的數(shù)據(jù)集上進(jìn)行了基準(zhǔn)測(cè)試[4]、[5]、[11]，這些對(duì)象類是從24個(gè)方位角以64×64[5]的分辨率渲染的。對(duì)于輪廓監(jiān)督學(xué)習(xí)，單個(gè)圖像由神經(jīng)網(wǎng)絡(luò)處理，神經(jīng)網(wǎng)絡(luò)返回3D網(wǎng)格。該網(wǎng)格的輪廓由可微渲染器從兩個(gè)視點(diǎn)渲染，渲染網(wǎng)格和預(yù)測(cè)網(wǎng)格之間的交集過并用作更新神經(jīng)網(wǎng)絡(luò)的訓(xùn)練目標(biāo)[4]，[5]。對(duì)于訓(xùn)練，我們也使用與Kato等人[5]和Liu等人[4]相同的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。請(qǐng)注意，雖然渲染器可以渲染完整的RGB圖像，但在這些實(shí)驗(yàn)中，只有輪廓用于監(jiān)督三維幾何體重建。具體而言，[4]、[5]的公共實(shí)現(xiàn)僅使用輪廓監(jiān)視。

對(duì)于這項(xiàng)任務(wù)，我們放松了兩種輪廓渲染算法。算法按如下方式柵格化3D網(wǎng)格：對(duì)于網(wǎng)格的每個(gè)像素和每個(gè)三角形，如果像素位于三角形內(nèi)，則輸出圖像中像素的值設(shè)置為1。像素是否位于三角形內(nèi)的條件以兩種可選方式進(jìn)行檢查：（1）通過三個(gè)嵌套的if條件檢查像素位于每條邊的哪一側(cè)。（2） 通過檢查像素和三角形之間的有向歐幾里德距離是否為正。注意，通過使用我們的框架放松這些算法，我們獲得了非常接近（1）的Pix2Vex[40]和（2）的SoftRas[4]的可微渲染器。圖6中顯示了松弛輪廓渲染的示例和來自數(shù)據(jù)集的示例圖像。

由于簡單輪廓渲染器沒有任何優(yōu)化，例如丟棄遠(yuǎn)離三角形或被其他三角形遮擋的三角形的像素，因此效率不高。因此，由于資源有限，我們只能以2的最大批量進(jìn)行培訓(xùn)，而以前的工作使用64的批量。因此，為了進(jìn)行公平比較，我們僅在2個(gè)批次上復(fù)制了Liu等人[4]最近表現(xiàn)最好的作品。對(duì)于有向歐氏距離，我們使用β=2000的逆溫度；對(duì)于三條邊，β=10000。

我們?cè)诒?中報(bào)告平均值和類級(jí)3D IoU結(jié)果。3.我們的松弛性能優(yōu)于Yan等人[11]的檢索基線，即使我們使用的批次大小僅為2。與批量大小為2的SoftRas渲染器直接比較，我們的松弛實(shí)現(xiàn)了13個(gè)對(duì)象類中5個(gè)的最佳精度。然而，平均而言，我們的方法雖然沒有表現(xiàn)出比SoftRas更好的性能，但顯示出可比的性能，僅下降1%。值得注意的是，有向歐幾里德距離方法的性能優(yōu)于三邊方法。由于計(jì)算有向歐幾里德距離比三個(gè)嵌套if子句（即使在寬松的情況下）更昂貴，因此三邊方法的速度要快3倍

4.4 Levenshtein Distance Supervision

在Levenshtein距離監(jiān)督實(shí)驗(yàn)中，我們通過只監(jiān)督長度為32的兩個(gè)手寫字符串之間的編輯距離來監(jiān)督手寫EMNIST字母的分類器[12]。作為編輯距離，我們使用Levenshtein距離LD，其定義為：

我們使用經(jīng)典的動(dòng)態(tài)規(guī)劃算法放松Levenshtein距離。圖7顯示了示例Levenshtein距離矩陣及其松弛。

為了便于學(xué)習(xí)，給出了32個(gè)手寫字符a、b的圖像串對(duì)以及地面真值Levenshtein距離LD（ya、yb）。我們從2個(gè)或4個(gè)字符的字母表中抽取一對(duì)字符串a(chǎn)、b。對(duì)于給定第一個(gè)字符串的第二個(gè)字符串的采樣，我們統(tǒng)一選擇兩個(gè)或四個(gè)插入和刪除操作。因此，使用兩個(gè)不同字符的字符串的平均編輯距離為4.25，四個(gè)字符的平均編輯距離為5。我們使用CNN處理每個(gè)字母，CNN返回字母的分類分布，然后將其反饋給算法?；趝a，C，G，T}的一對(duì)字符串的示例是and。我們的培訓(xùn)目標(biāo)是最大限度地減少預(yù)測(cè)距離和grouth真實(shí)距離之間的l 2損失：

表4表明，在所有情況下，我們的方法在這兩個(gè)指標(biāo)上都始終優(yōu)于基線。字符組合AB、BC、CD、DE和EF是隨機(jī)組合的標(biāo)準(zhǔn)選擇。IL所代表的字符是兩個(gè)字母最難的組合，因?yàn)樗鼈兩踔两?jīng)常被有監(jiān)督的神經(jīng)網(wǎng)絡(luò)所混淆[12]，人類也無法區(qū)分。字符OX代表了最簡單的情況，因?yàn)橛斜O(jiān)督的分類器可以在測(cè)試數(shù)據(jù)集上完全區(qū)分它們[12]。對(duì)于兩個(gè)字母組合，我們?cè)?7%（IL）和96%（OX）之間實(shí)現(xiàn)了頂級(jí)精度。即使是四個(gè)字母組合（ACGT和OSXL），我們也能達(dá)到最高48.7%的頂級(jí)精度。注意，當(dāng)我們使用長度為32的字符串時(shí)，在Levenshtein算法中，超過1000條語句被放松。

5、結(jié)論

我們提出了一種算法的連續(xù)松弛方法，允許將其集成到端到端可訓(xùn)練神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中。為此，我們使用平滑函數(shù)參數(shù)化的算法執(zhí)行路徑的凸組合。我們證明了我們提出的通用框架可以在各種算法監(jiān)督任務(wù)上與特定算法的SOTA連續(xù)松弛以及梯度估計(jì)方法競爭。此外，我們證明了我們的公式成功地放松了即使是最短路徑算法或渲染器等復(fù)雜算法。我們希望激勵(lì)研究界在我們的框架基礎(chǔ)上進(jìn)一步探索算法監(jiān)控和算法增強(qiáng)神經(jīng)網(wǎng)絡(luò)架構(gòu)的潛力。

交流群

歡迎加入公眾號(hào)讀者群一起和同行交流，目前有美顏、三維視覺、計(jì)算攝影、檢測(cè)、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競賽等微信群

個(gè)人微信（如果沒有備注不拉群！）
請(qǐng)注明：地區(qū)+學(xué)校/企業(yè)+研究方向+昵稱



下載1：何愷明頂會(huì)分享

在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：何愷明，即可下載。總共有6份PDF，涉及 ResNet、Mask RCNN等經(jīng)典工作的總結(jié)分析

下載2：終身受益的編程指南：Google編程風(fēng)格指南

在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：c++，即可下載。歷經(jīng)十年考驗(yàn)，最權(quán)威的編程規(guī)范！


下載3 CVPR2021

在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：CVPR，即可下載1467篇CVPR 2020論文 和 CVPR 2021 最新論文