11 月 13 日，微軟研究院（Microsoft Research）和普林斯頓大學(xué)研究人員，提出了一個通用框架，用于設(shè)計無監(jiān)督學(xué)習(xí)問題的有效算法，如高斯分布和子空間聚類的混合。

研究人員所提的框架在解決噪聲問題上，使用了一種下界學(xué)習(xí)計算公式的元算法。這是建立在 Garg、Kayal 和 Saha (FOCS ’20) 最近的工作基礎(chǔ)上的，他們設(shè)計了這樣一個框架，用于在沒有任何噪音的情況下學(xué)習(xí)算術(shù)公式。元算法的一個關(guān)鍵要素是針對稱為“穩(wěn)健向量空間分解”的新問題的有效算法。

研究證明，當(dāng)某些矩陣具有足夠大的最小非零奇異值時，元算法效果很好?！拔覀兺茰y這個條件適用于我們問題的平滑實例，因此我們的框架將為平滑設(shè)置中的這些問題產(chǎn)生有效的算法?！?/span>

該研究以《在存在噪聲的情況下學(xué)習(xí)算術(shù)公式：無監(jiān)督學(xué)習(xí)的通用框架和應(yīng)用》（Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning）為題，于 11 月 13 日發(fā)布在 arXiv 預(yù)印平臺上。

無監(jiān)督學(xué)習(xí)涉及發(fā)現(xiàn)數(shù)據(jù)中隱藏的模式和結(jié)構(gòu)，而不使用任何標簽或直接的人類監(jiān)督。

在這里，研究人員考慮具有良好數(shù)學(xué)結(jié)構(gòu)或從數(shù)學(xué)上明確定義的分布生成的數(shù)據(jù)。前者的一個例子是，可以根據(jù)某些相似性模式將數(shù)據(jù)點分組為有意義的集群，并且目標是找到底層集群。后者的一個例子是混合建模，它假設(shè)數(shù)據(jù)是由簡潔描述的概率分布（例如高斯分布）的混合生成的，目標是從樣本中學(xué)習(xí)這些分布的參數(shù)。

解決許多無監(jiān)督學(xué)習(xí)問題的通用框架是矩方法，它利用數(shù)據(jù)的統(tǒng)計矩來推斷模型的底層結(jié)構(gòu)或底層參數(shù)。對于許多無監(jiān)督學(xué)習(xí)問題場景，其中基礎(chǔ)數(shù)據(jù)具有一些很好的數(shù)學(xué)結(jié)構(gòu)，數(shù)據(jù)的矩是參數(shù)的明確定義的函數(shù)。啟發(fā)式論證表明，相反的情況通常應(yīng)該成立，即結(jié)構(gòu)/分布的參數(shù)通常由數(shù)據(jù)的一些低階矩唯一確定。在這個大方向上，主要的挑戰(zhàn)是設(shè)計算法來（近似地）從（經(jīng)驗）力矩中恢復(fù)潛在的參數(shù)。

我們還希望該算法高效、耐噪聲（即，即使僅近似而不是精確地知道矩，也能很好地工作），甚至是異常容忍度(即，即使少數(shù)數(shù)據(jù)點不符合底層結(jié)構(gòu)/分布也能很好地工作)。但即使是該領(lǐng)域最簡單的問題也往往是 NP 困難的，并且即使沒有噪聲和異常值也仍然如此。

因此，人們實際上不能指望一種具有可證明的最壞情況保證的算法。但人們可以希望算法能夠保證通常運行良好，即對于隨機問題實例，或者更理想的是對于以平滑方式選擇的實例。因此，針對無監(jiān)督學(xué)習(xí)中的每個此類問題設(shè)計了許多不同的算法，具有不同水平的效率、噪聲容忍度、離群值容忍度和可證明的保證。

在這項工作中，研究人員給出了一個適用于許多此類無監(jiān)督學(xué)習(xí)問題的元算法。該研究的出發(fā)點是觀察到許多此類問題都歸結(jié)為學(xué)習(xí)算術(shù)公式的適當(dāng)子類的任務(wù)。