檢視容錯學習問題的原始碼

{| class="wikitable" style="float:right; margin: -10px 0px 10px 20px; text-align:left"
|<center>'''容錯學習問題'''<br><img src="https://img-blog.csdnimg.cn/20181029205310785.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmNpanVuMTY2Ng==,size_16,color_FFFFFF,t_70" width="280"></center><small>[https://www.itread01.com/content/1543280174.html 圖片來自itread01]</small> 
|}

'''容错学习问题''' （通常称'''LWE问题'''，是 Learning with errors 的缩写）是一个[[机器学习]]领域中的怀疑难解问题。由 Oded Regev 在2005年提出，他因此赢得2018年[[哥德尔奖]]<ref>[https://www.zhihu.com/question/315836412/answer/637462354 哥德尔奖]，zhihu</ref>。这是一个极性学习问题的一般形式。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>。误差的引入，导致如果你用高斯消元，那么所有的式子加到一起之后误差也加了起来，噪音过大，导致你无法从噪音中读取任何信息。这就是此问题的精华。

== 參考文獻 == 
{{reflist}}
[[Category: 310 數學總論]]