机器学习中有哪些形式简单却很巧妙的idea？
AI论文中，有哪些像GAN这种形式简单却功能强大的idea。 dummy class做多元分类的时候，加1-3个假类别。比如做3分类，output弄成4分类，那个虚拟出来的假类别（dummy class）不需要训练数据什么，input层面不用管他，只需要output里面写成4分类这么简单。结果会比单纯3分类同样条件下好几个点。 我斗胆来回答一下吧，我看到貌似没有人提及到这个trick，就是在做图像的多类别分类的时候，把两张图片按照随机比例加起来，然后把label定义成两张图片的类别的比率，然后直接训练就好了，在部分模型上可以提大约5个点左右
我觉得满足了形式简单，巧妙和有效这三个点了 当然是2017年获得NeurIPS Test of the Time Award的Random Fourier Feature。
分类问题经常会用把数据project到高维，再做correlation，即计算 https://www.zhihu.com/equation?tex=%5Clangle+%5Cphi%28%5Ctextbf%7Bx%7D%29%2C%5Cphi%28%5Ctextbf%7By%7D%29+%5Crangle 。但是由于lifting function https://www.zhihu.com/equation?tex=%5Cphi%28%29+ 会把数据投到很高维，使得计算内积变得十分昂贵，所以人们发明了kernel trick，即用一个positive definite的function https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D%2C%5Ctextbf%7By%7D%29 , 使得 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D%2C%5Ctextbf%7By%7D%29+%3D+%5Clangle+%5Cphi%28%5Ctextbf%7Bx%7D%29%2C+%5Cphi%28%5Ctextbf%7By%7D%29%5Crangle ,这样就避免了计算两个高维向量的内积。但是kernel trick需要计算数据的gram matrix，即 https://www.zhihu.com/equation?tex=%5Ctextbf%7BX%7D%5Ctextbf%7BX%7D%5E%7B%5Ctop%7D%2C+%5Ctextbf%7BX%7D+%5Cin+%5Cmathbb%7BR%7D%5E%7Bn%5Ctimes+d%7D 。如果你有一百万条数据的话，计算gram matrix几乎是不可承受的开销。
于是Ali Rahimi 和 Ben Recht在2007年提出了一种randomized 的feature， 即寻找一种mapping https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29%3A+%5Cmathbb%7BR%7D%5Ed+%5Crightarrow+%5Cmathbb%7BR%7D%5ED , 使得 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29%5E%7B%5Ctop%7D+z%28%5Ctextbf%7By%7D%29+%5Capprox+k%28%5Ctextbf%7Bx%7D%2C+%5Ctextbf%7By%7D%29 。
虽然这也需要计算内积，但是 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29+ 的维数远小于 https://www.zhihu.com/equation?tex=%5Cphi%28%7B%5Ctextbf%7Bx%7D%7D%29 的维数。比如常用的Gauss Kernel，其对应的lifting function会把数据map到无穷维，而 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29 的维度D大概只需要 https://www.zhihu.com/equation?tex=D%3DO%28d%5Cepsilon%5E%7B-2%7Dlog%5Cfrac%7B1%7D%7B%5Cepsilon%5E2%7D%29 , 其中 https://www.zhihu.com/equation?tex=%5Cepsilon 是 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29%5E%7B%5Ctop%7Dz%28%5Ctextbf%7By%7D%29 和 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D%2C+%5Ctextbf%7By%7D%29 的误差。
这种approximation既避免了计算gram matrix，又不需要计算无穷维向量的内积，而且它还和真实值偏差不大。那么这种好用又实惠的mapping https://www.zhihu.com/equation?tex=z%28%29 怎么寻找呢？数学原理是这样的，先做个傅里叶变换：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29+%3D+%5Cint_%7B%5Cmathbb%7BR%7D%5Ed%7Dp%28%5Comega%29e%5E%7Bj%5Comega%27%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29%7Dd%5Comega++++++++%5Cqquad+++++%5Cqquad++%281%29+%5Cend%7Bequation%7D
对，就是找到一个function https://www.zhihu.com/equation?tex=p%28%5Comega%29 , 使得https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29 是它的傅里叶变换（对 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29 做逆变换即可找到 https://www.zhihu.com/equation?tex=p%28%5Comega%29 ）。神奇的地方来了，Bochner's theorem 告诉我们，
当且仅当一个连续函数是一个非负测度的傅里叶变换时，这个函数是positive definite function。
这个theorem很拗口，翻译成人话就是如果 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29 是positive definite(这个我们在前面已经保证过了)的，那么 https://www.zhihu.com/equation?tex=p%28%5Comega%29 就一定是一个d维的概率分布。现在我们再来看(1)式，其实就是 https://www.zhihu.com/equation?tex=e%5E%7Bj%5Comega%27%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29%7D 这个随机变量的期望啊。如果我们定义 https://www.zhihu.com/equation?tex=%5Cxi_%7B%5Comega%7D%28%5Ctextbf%7Bx%7D%29+%3D+e%5E%7Bj%5Comega%5Ctextbf%7Bx%7D%7D ，那(1)式就等价于 https://www.zhihu.com/equation?tex=%5Cmathbb%7BE%7D_%7B%5Comega%7D%5B%5Cxi_%7B%5Comega%7D%28%5Ctextbf%7Bx%7D%29%5Cxi_%7B%5Comega%7D%28%5Ctextbf%7By%7D%29%5E%2A%5D 。由于这些量都是实数，我们可以舍弃虚部，只保留cos项，于是我们可以定义 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29+%3D+%5Csqrt%7B2%7Dcos%28%5Comega%5E%7B%5Ctop%7D%5Ctextbf%7Bx%7D%2Bb%29 ,最终得到 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29+%3D+%5Cmathbb%7BE%7D%5Bz_%7B%5Comega%7D%28%5Ctextbf%7Bx%7D%29%5E%7B%5Ctop%7Dz_%7B%5Comega%7D%28%5Ctextbf%7By%7D%29%5D 。
于是我们可以通过sample D个 https://www.zhihu.com/equation?tex=%5Comega+%5Csim+p%28%5Comega%29%2C+b+%5Csim+U%280%2C2%5Cpi%29 , 带入 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7Bx%7D%29 和 https://www.zhihu.com/equation?tex=z%28%5Ctextbf%7By%7D%29 ,得到2个D维的向量，再用他们做内积，效果和计算 https://www.zhihu.com/equation?tex=k%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29 是“几乎”一样好的。（不要忘了之前我们可是得用俩无穷维的向量做内积的- -）
那么问题来了，这个"几乎一样好"大概有多大概率呢？其实通过随机变量的concentration不难证明：
https://www.zhihu.com/equation?tex=Pr%5B%5Csup_%7Bx%2Cy+%5Cin+%5Cmathcal%7BM%7D%7D%7Ck%28%5Ctextbf%7Bx%7D-%5Ctextbf%7By%7D%29-z%28%5Ctextbf%7Bx%7D%29%5E%7B%5Ctop%7Dz%28%5Ctextbf%7By%7D%29%7C%5Cgeq+%5Cepsilon%5D+%5Cleq+2%5E8%28%5Cfrac%7B%5Csigma_p+diam%28%5Cmathcal%7BM%7D%29%7D%7B%5Cepsilon%7D%29exp%28-%5Cfrac%7BD%5Cepsilon%5E2%7D%7B4%28d%2B2%29%7D%29
式子很长，但主要就说了一件事，就是random fourier feature“玩砸”的概率，会随着投影维数D的增大，而指数般的减小。当D趋向无穷时，random fourier feature完全等价kernel trick。
PS. 话说Ali Rahimi就是当年在NIPS上怼深度学习是“炼金术”的那个人，后来还和Lecun在twitter上大战。。 有一个idea，它匪夷所思，简单粗暴，却效果惊人。
它不仅仅是一个idea，它还在机器学习各个领域的坑都填的差不多的今天，又挖开了一个天坑，开创了一个新的领域，引来了无数填坑的人，不知道又要拯救多少无法毕业的学生。
它就是：
Federated Averaging Algorithm
故事发生在冬天，那一年冬天，阴雨连绵，同样阴沉的，是人的心情。
“什么？不能上传用户的数据，那怎么训练模型？！“ 研究员老A的手离开了键盘，抬得老高，继续说到：
“怎么就他们要求这么多，现在的机器学习功能，哪个不是先建一个收集数据的pipeline，有了海量数据以后，再训练模型。没有数据，怎么训练？！“
“没办法啊，现在社会对数据隐私的要求越来越高了，欧盟的GDPR，只是个开始。作为大公司，肯定要在这方面当先行者。“ 产品经理老C也很无奈。
众人也是面面相觑，不过并不是所有人都丧失信心，至少研究员老F和他的实习生小Y不是。
“就算不上传数据，也不是不可以训练啊“ 老F思忖了一下，继续说道。“你仔细想一想，SGD算法是怎么个流程？”
“先随机选取一个batch的数据，更新梯度，再换下一个batch，再更新。模型收敛以后，就停止训练“ 实习生小Y自信的说到。
研究员老F点点头：“你看，这不是一回事吗，不一定需要一个集中的数据中心嘛。你把一批用户的数据想像成一个batch。“
“哦，对啊！在每个用户的手机里训练模型，然后上传更新的梯度。之后再换下一批用户，再更新一次梯度，直到收敛为止。“ 实习生小Y抢道。
“对嘛。小伙子很聪明嘛。“ 研究员老F的眼里充满了慈爱。“我们就叫它FederatedSGD算法吧。”
“那不对啊“ 实习生小Y好像发现了什么。 “在数据中心里训练，不需要考虑上传梯度的传输问题啊。但是在用户的手机和服务器之间，有大量的数据上传，手机流量铁定用没了。”
“不光是流量的问题。这每个batch都要上传一次模型的梯度，要收敛可能要几万个batch，那就是说训练一次模型要上传几万次。移动数据网络的带宽有多少？多久能完成一次训练？“ 老F思考了一会儿，继续说道：
“要不我们试试这样行不行，先在用户的手机上训练，训练到差不多收敛了，再上传模型。我们把所有获得的模型相加取平均，就是我们最终的模型。这样大大减少了对带宽的需求。“
“这能行吗，没听说过谁这么训练啊“ 小Y很怀疑，“不过我也没啥事做，试试呗。”
“好的，你试试看，然后告诉我结果。“ 老F安排完任务，就继续工作了。
过了几天，办公室的某个角落，传来了小Y的惊呼：“我去，这都可以！”
“怎么回事？“ 老F问？
“您上次让我试的方法，居然work了！“
“噢，我看看。“ 老F和小Y讨论了一会儿实验，确认了这个结果，并且将这个算法命名为Federated Averaging。
随后的一段时间，大家都很兴奋，针对这个idea提了很多意见以及后续的实验方案，并且也花了很多精力增加了对这个结果的理论支持。
其实，这个idea也不能照抄到所有的应用场景。在一些现实场景中，不同用户的数据分布可能差异很大，数据可能不均衡，这个idea并不能适用于所有的机器学习算法。
不管怎样，基于Federated Averaging算法，一个崭新的机器学习领域 - Federated Learning 诞生了。这个领域还非常非常年轻，很多基础的工作还没有完成。欲知这个大坑里有哪些小坑，且听我下回分解。 异常检查算法Isolation Forest(孤立森林）
原理超简单，但检测效果可以说是state of the art. 对一个空间进行二分，早划分「孤立」出来的就是很可能异常的。「孤立」指的是这一边只有这一个数据点。因为是二分，我们可以构建一颗二叉树。例如下图的一棵树，第一次二分，左边有数据的a,b,c,右边只有d，那么d大概率就是异常点。为啥？想想你画一条线，把一把米分成了两边，左边只有一粒，那左边那粒很可能是离其他米粒很远。
http://picx.zhimg.com/v2-6ffd14aebb5112d7981e348781433ca7_r.jpg?source=1940ef5c
为了更直观，有更多一步了解，请看下图，直觉上我们就知道 https://www.zhihu.com/equation?tex=x_i 是普通点， https://www.zhihu.com/equation?tex=x_0 是异常点。那么用Isolation tree怎么解释呢？
http://pica.zhimg.com/v2-5648464d3a8a9ca95d7cc1ef532a1118_r.jpg?source=1940ef5c
如果要把 https://www.zhihu.com/equation?tex=x_i 孤立出来，需要很11次划线，而 https://www.zhihu.com/equation?tex=x_0 需要的次数要少很多。所以 https://www.zhihu.com/equation?tex=x_0 比https://www.zhihu.com/equation?tex=x_i 更可能是异常点。
一棵树不够可信？没事，记得随机森林random forest不？没错，这里也引进一堆树。如果多数的树都在前几次分割时分出同一个点，那么这个点是异常点的概率就非常高了。
http://picx.zhimg.com/v2-1e2227658dcaa2c2187c86533be229b3_r.jpg?source=1940ef5c
可以看到，树的数量（横轴）超过10时，平均分割次数（纵轴）就收敛了。从这个图我们可以看出，某个点 https://www.zhihu.com/equation?tex=x_0 被「孤立」前，平均分割次数低于5，那么 https://www.zhihu.com/equation?tex=x_0 就是异常点。
原理是不是超级简单呢。如果想了解更多数学上的原理，可以参考下面的参考文献。
参考文献：
https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf
页:
[1]