容錯學習問題
 |
容錯學習問題 （通常稱LWE問題，是 Learning with errors 的縮寫）是一個機器學習領域中的懷疑難解問題。由 Oded Regev 在2005年提出，他因此贏得2018年哥德爾獎[1]。這是一個極性學習問題的一般形式。Regev同時證明了LWE問題至少比幾個最壞情況下的格問題要難。這個問題在最近被用作一種難度假設以創建公鑰密碼系統，例如 Peikert 提出的環學習時出錯密鑰交換。
目錄
密碼學上的應用
A是一個m x n矩陣，s是一個n維向量，e是一個m維向量。我們定義LWEA(s,e) := b := As + e。由此可以構造一個對稱加密算法。加密算法定義如下:
- s作為密鑰k使用；
- (A,e)這一組數據在加密時隨機生成；
- 由s, A, e所求得的值b作為一次性密碼本的密鑰使用，同密文m進行亦或操作。
這一算法和傳統對稱密鑰加密算法的區別的關鍵在於，加密方不將誤差數據e傳送給解密方，導致解密方所解得明文存在一個小的誤差。
量子計算
2018年10月，斯坦福研究院的學生利用LWE問題作為基礎解決了經典計算機如何驗證量子計算機是否進行了量子計算這一問題。
簡述
雖然來自機器學習領域，但是學習時出錯問題實際上是理論計算機科學中的計算複雜度問題。用簡單易懂的方式來說，問題如下。
14 \cdot s_{1} + 15 \cdot s_{2} + 5 \cdot s_{3} + 2 \cdot s_{4} \approx 8 mod 17
13 \cdot s1 +14 \cdot s2 +14 \cdot s3 +6 \cdot s4 \approx 16 mod 17
6 \cdot s1 +10 \cdot s2 +13 \cdot s3 +1 \cdot s4 \approx 3 mod 17
我提供類似的許多的線性多項式，讓你來求s_{1} \cdots s_{4}。這就是容錯學習問題。這一問題的關鍵就在於每個等式都是約等於，有一定誤差（所謂的「出錯」）。這個誤差可以遵循一個離散隨機分布，例如，有的時候左邊比右邊大1，有的時候左邊比右邊小1，還有的時候兩邊相等。如果假設所有式子都是直等，那這個問題就太簡單了。只要有足夠的式子，那麼使用常見的高斯消元法，在多項式時間內就能輕易求出<math>s_{1} \cdots s_{4}</math>。誤差的引入，導致如果你用高斯消元，那麼所有的式子加到一起之後誤差也加了起來，噪音過大，導致你無法從噪音中讀取任何信息。這就是此問題的精華。