有句话怎么说的来着，当你无聊的时候，就去背英语单词吧。
于是乎，曾经特别无聊，直接自己写了个R程序帮自己背单词。基本就是一个伪装在Rstudio里面的gre单词选择器。大致原理就是，死记硬背。每次显示一个单词和对应的四个选项，然后记录一下选没选对。下一次，自动优先没有选对的词，提高其出现的频率。大致就是一个简单的机器学习模型来预测我对于一个单词可能的出错率。
至于为啥要在r里面做这件事...因为我天天上班用r啊，成功地伪装在rstudio的界面里面，就没有人知道我是在摸鱼还是在正经工作了呢。当然，这都是陈年往事了...现在已经不需要背单词了，而且很多单词死记硬背其实没啥效果，最后不会用还是不会用。阅读量上来的词汇才是真的记住了。
不过死记硬背也大概是某个阶段不可避免的吧。不能读一篇文章一直查单词去了。所以这段代码我准备留着，说不定二十年后自己的孩子还能用到呢？谁知道呢对吧。
截图一张留念吧
前几天有提到，十二月份的时候去NeurIPS 2019晃了一圈。除了开篇那个演讲之外，那周我还去围观了不少其他的东西。NeurIPS开到如今，万人大会，熙熙攘攘地其实挺难甄别信息的。第一次去这种顶级的计算机会议，经验不足，只能按图索骥般地一点点拾遗。
好在，我目标相对明确，并不是一味的去凑热闹的。那些火到爆的GAN之类的，我就只能远远地围观一眼，然后不明觉厉，去找自己相对更能看懂的东西去了。于是，我就很无聊的，去看了两个主题：因果推断相关的，以及隐私相关的。
因果推断这块儿，能到NeurIPS自然是被选择过的，不会是太纯理论的这种。跟机器学习相关的自然是要跳出简单的线性回归了，否则大家写什么呢？其次呢，就是跳出随机试验的框架，否则哪里用得到那么多高深的预测模型呢？七七八八看了不少poster论文，大部分都是各种花样繁杂的算法。努力地去理解他们的做法，然而却哀叹一声，浮沙筑高台，又有多少可以大浪淘沙始见金。（插曲：后面那个causal inference workshop，直接就是Susan-fest...哎，她也算是扛起来一面大旗了。）
隐私相关的，其实是加密+分布式的结合，基本要实现的是在客户端进行计算而不是需要把原始的隐私数据传递到服务器端。于是乎，我们看到了各种基于分布式算法的演化，加一些随机的因素在里面，就得到了一些隐私友好的算法。也挺好玩的，有助于想清楚一些分布式算法的设计。
笔记本身是用英文整理的，直接在这里贴一份好了。
今儿跑代码的百无聊赖的时间，看了一下昨天收藏的周志华老师的一个演讲：Boosting 25周年。链接在这里：
对Adaboost之类的我已经忘得差不多了，还好有当年ESL的笔记可以翻翻。看周老师这张slide，基本上是总结了一下集成学习（ensemble learning）的大概思路。
按照这个思路，Boosting类和bagging以及random forests这种都算作ensemble learning了。然后在简单的回顾了adaboost的前世今生之后，抛出来一个有趣的问题：
理论上我们证明了，Adaboost在多轮学习之后会过拟合，可是为什么实践中很少看到过拟合的现象呢？
嗯...然后就是边界理论和统计观点的两种解释...我就不赘述了，大家去看周老师的slides就好。我好奇的其实是，overfitting本身是怎么可以用一个理论的方法来证明的呢...感觉不那么直观呢...好好奇啊，想找点相关的paper来看看，可又怕是另外一个大坑，上周那个实验设计的大坑还没填平或者弃坑呢。
由于近些年常常跟搞数据分析的人混迹在一起，所以很多时候说话方式有点偏向机器学习了...顺便心里暗暗的忧伤一下当年的心路历程（不知道我的基本轨迹的可以先去看看CV..）。这里聊作一二记录，讲讲我所认识的“最小二乘法”（下称最小二乘君）。那个，语言稍显浮夸，大家随便看看哈，别较真。
是写小说的时候大家都兴先来个“锲子”么。7年前，我还是一个年幼无知的大学新生儿。当时我们系开了两门传说中各挂50%的数学课：微积分和线性代数。同学们大都学的死去活来，我也学的死去活来，一度开始怀疑自己的智商...其实现在想想，我也不知道当年为什么学的那么痛苦，现在随手用个微积分貌似都很水到渠成的样子。嗯，可能是老师授课方式不够好吧。那年直到期末考试，我也不知道我学了一年的微积分有什么用处，除了背下来少数的几个证明推导和学会了一堆算微积分的“技巧”之外。
挂了很多人的高树...
线性代数也是一样的。当年翻看某本计算机类入门书（可能是算法与数据结构），前言一开始就是一行金字，大意是“矩阵论是当代计算机基础×××”。然后翻翻后面的果然看不懂，于是默默的去图书馆把这本书还了，然后借了一本黄皮的泛着金光《矩阵论》回来。同样悲催的，啥也没看懂，然后默默的放弃了我在这个领域深修的打算，乖乖的回去上必修课了。（所以我当年学习高级计算机知识的一腔热情就被这么无情的浇灭了哇！果断考完当时的计算机等级考试——C语言和数据库就扔掉编程了...）
线性代数一直学到最后，我还是以为这东西就是来替代“高斯消元法”解联立方程式的...什么特征根啊，奇异值分解啊，格拉姆－施密特正交化啊，直到最后我也没明白是干嘛用的，除了会算几个数之外...没想到，那日一别，重逢已是花落花开好几轮之后...当真是良辰美景虚设！只是万万没有想到，他乡遇旧友，而这厮竟和日后的最小二乘君紧密相连，难分难舍。
良辰美景虚设
最近一直在看Community Discovery这一块儿的论文，深深的感觉现在就是一个矿工，不断的想方设法挖出来更有价值的信息。而且不是一个点一个点的突破，而是需要寻找出一种脉络，串联起所有的信息来。头痛。
最近的情况是，有一个well-connected的网络，然后我想把它稀疏化、打散成一个个独立的community的感觉。这样就可以分别识别每个community的特征什么的。所以厚着脸皮找施老师讨了几篇papers。而主要的问题是，数据太大了...11M nodes， 20 M edges，还是directed weighted network...我直接放弃了把这些数据从SQL Based data source中挪出来的想法，还是先努力的减少一些edges吧。
先罗列几个相关的术语：community discovery, graph partitioning, network clustering, network sparsification, modularity。了解一个领域最好的方法大概就是去读literature review了，所以乖乖的要了一篇:
Srinivasan Parthasarathy, Yiye Ruan and Venu Satuluri. "Community Discovery in Social Networks: Applications, Methods and Emerging Trends", in Social Network Data Analytics 2011. (NS, DM)
最契合我的想法的就是cut类方法——remove some edges to disconnect the network, then （drop isolated nodes with degree = 1 (could be added back later as auxiliaries to each community)。
那么就先从这一类方法开始说。比较经典的算法呢，是希望砍掉一条边以后，community内部的凝聚力不变，外部连接变差。基本上常用的就是Ncut（normalized）和Conductance、KL object、Modularity这些指标。比如KL算法，就是从二分图开始，不断迭代的去寻找如果交换某两个点所属community就可以减少edge cut的边。可惜的是，这些最优化问题都是NP-hard....随着数据的增大算起来会异常吃力。KL算法本身迭代也是相当考验计算能力的（贪心搜寻）。
然后就是凝聚（或者切分）类算法。凝聚就是先各自为家，然后附近的相互结合在一起，直到理想数量的社群结成；切分则是先从一个整体开始，然后每一步都切成两份这样。这些都算是层次聚类，最后可以给出一个长得像二分树的系统树图。这一类算法有Girvan和Newman切分法：每一步先计算每条边的betweeness score，然后把得分最高的边砍掉，然后再重复这个步骤。嗯，问题依旧是这样的迭代很耗时间。
频谱类算法（spectral algorithms)。听这个名字一股经典风就袭面而来。基本上这类方法就是仰仗特征向量（eigenvector)，比如adjacency matrix的特征向量，然后top k特征向量就定义出来一个k维的特征空间，然后就可以用传统的比如k-means这样的方法来聚类了。说白了就是降维、降维。可惜这种方法依然算起来很消耗资源，光算那个特征向量就是O(kM(m))的复杂度...基本在大矩阵下就投降了。一个概率的方法就是Graclus算法，基本的直觉就是基于加权的normal cut measures再做加权核k-means便可以给出基于特征向量聚类一样的结果，而计算消耗相对少一些。
多层次图分割(Multi-level graph partitioning)。这个就是相比而言快速有效的方法了。基本的想法就是，先压缩原始图像到一个小的图像、分割这个图，然后再映射回原来的图。毕竟小图分割起来就要快的多嘛。这类的方法除了上面说到的Graclus，还有Metis（以KL object作为measurement），以及MLR-MCL。
马尔可夫聚类（Markov Clustering，MCL）。基本的想法就是，两点之间的信息传递是随机流（stochastic flow）。MCL对随机矩阵会做两个操作，扩张（expand）和膨胀（inflate）。前者就是简单的矩阵平方，后者则是用一个膨胀参数（非线性）来撑大彼此之间的差距，最后再重新normalize。这两个步骤交替进行。这样的话，原本community中紧密相连=的两个点则会更紧密的相连，而不同cluster之间的连接则被弱化。这样最后每个community之内的点都会流向某个attractor（吸引点），从而我们可以识别各个cluster。感觉这里有点收敛到一些不动点的意思。MCL的弱点也是计算消耗。矩阵乘法在开始边的权重没有弱化的时候是非常消耗时间的，此外MCL倾向于产生不平衡的群落，尤其是可能产生一堆很小的群落或者一个很大的群落。
MCL的改良主要是在引入惩罚项（regularized MCL）和加入多层次（multi-level regularized MCL），以减少不平衡的clusters和解决MCL难以scalable的问题。后者也简称为MLR-MCL，就是刚才多层次分割里面有提到的那个。
局部聚类(local graph clustering)。局部方法基本上就是从一个给定的顶点(seed)出发，寻找符合条件的群落，而并不关心整个graph的情形（除非所有的群落需要覆盖全图）。计算上就是利用随机游走（random walk），从一个群落的内部开始，一点点的向外扩张（有没有很像page rank的感觉？）。最早的Spielman and Teng就是这样的基于顶点随机游走的算法。后面Andersen and Lang改进了这类方法，可以从一堆seed sets出发而不是单单一个顶点。此外，Andersen还试图在随机游走之上加入re-start(即个性化的pagerank)。
再需要提及的就是在动态网络(dynamic network)之上的community discovery——不同于静态网络，动态网络是本身一直在变化的，正如我们一直在用的facebook、twitter这般。还有异质网络（heterogeneous network）和有向网络(directed network)。呃，这部分我就没细看了，貌似蛮复杂的样子...就是其中有一个Community-User-Topic（CUT）model看起来蛮有意思的，准备明天去找这篇paper读一下：
D. Zhou, E. Manavoglu, J. Li, C.L. Giles, and H. Zha. Probabilistic models for discovering e-communities. In WWW ’06: Proceedings of the 15th international conference onWorldWideWeb, page 182. ACM, 2006.
嗯，到总结了~前面一直在说的就是计算、计算、计算。
好了，到此为止~继续看其他paper去了。