Categories
经济、IT观察与思考

一些观察

随便写写,随便看看。

1. 关于研究方向。

读的paper多了,发现大多数人的研究路数无非两种:

  • 一种是锚定一个问题,然后用尽各种办法来看哪种可解。换个通俗的就是,车坏了,找出一堆工具来看看怎么可以修好。
  • 另一种则是,沿袭一套方法论的路数,试图解决越来越多的问题。通俗的讲,就是木工不满足于打打家具,还要去试试电工水工装修工。

你说孰优孰劣?没有高下之分。谁也说不好一篇好的研究到底是问题导向的还是方法论导向的。不过鉴于一般来讲方法论比较容易训练出来,所以有的时候看似包装的很漂亮的paper可能正是这个方法灵了然后倒回头来包装问题本身。

本以为这个只是看paper时候的感觉。后面发现,工作其实也不外乎如此。有的人凭着一门专业技能,比如编程,就可以在不同部门之间切换来切换去,反正总有需要用到编程的地方。有的人有一些具体问题,然后就广撒网找来各种背景的人帮忙解决。前者最后进化为技术专家,后者进化为大BOSS。

2. 关于建模

说到模型,反正上来都是那句至理名言:

没有模型是正确的,只有一些是有用的。

所以一切试图证明自己是真理的模型都是无用功。如果是真理,搞成体系那就叫他理论,可以慢慢证明就叫做定理,不证自明那就叫公理好了。反正我觉得说某个模型是正确的这种言论都是挺无聊的。

基于这一条,在实际商业环境中建模,就不要一开始给自己摆太高的期望。就跟上面说的,很多时候问题都是第一类人发现的,他们只是寻求有着不同技能的第二类人帮忙看一下,实践中谁好用就用谁。所以一群第二类人内部争来争去,什么机器学习流派啊、数理统计流派啊、计量帮啊、物理统计帮啊还是算命仙人这些其实都不那么重要...比如最近世界杯大家都在预测,那么不管你是章鱼还是小丸子还是霍金,只有预测对了大家才信你。

所以在学校里被某个流派洗脑洗的深入骨髓的,可以醒醒了。不要一上来就摆出自己是真理这样的架势。每个人在象牙塔里都是这么教的。

3. 关于统计建模

如果大家笃定就要用统计的方法了,那么要解决的问题就无非是:搜集数据(变量)、选择模型、修改参数以达到最优。

具体到项目,搜集数据这个肯定是大头。每个学过统计的都被教导过“garbage in, garbage out”。只可惜大部分老师讲完这句话之后,学生并没有多少机会实际的去搜集数据,或者更直接的去想要怎么搜集数据。大部分学校里面的训练(尤以网上数据挖掘竞赛之时)都是,数据集给定,怎么找个更好的模型来预测/评估/解释。真到了项目上需要搜集数据了,大部分人的做法无非就是先找张纸把想到的变量都分门别类列出来,然后把所有可能拿到的数据都扔进去试试,从简单的线性回归或者分类器开始,到非线性的各种模型都扔进去跑一遍,反正这年头计算能力不是瓶颈,总有合适的模型自己可以去做变量选择。

听到这里,貌似也挺好啊。是啊确实没什么不好,如果大家都有充足的时间慢慢玩的话。可惜的就是这种无脑流在大多数情况下都是受制约于时间的。于是为了省时间,要么就某些麻烦的数据不搜集了,要么就某些计算复杂的模型不去跑了。差不多就好了。解决问题了么?可能也差不多解决了70%-80%。

与此同时还有一类业务流派。这类人特别像医生似的,是某个具体领域的专家,专到什么程度呢?基本上他熟悉的地儿有个风吹草动都逃不过他的眼睛。直觉很准,或者说经验实在是太丰富了。跟这个流派的人一起工作很好玩,他们想到一个问题大概的给你指一个方向,大部分情况下八九不离十,差不多就可以把问题解决了。就算事后需要稍微建建数理模型多做一些分析和验证,基本也不会太麻烦。每当此时,不禁大呼一声畅快,瞬间觉得自己以前的思路真实的麻烦爆了。嗯,爽归爽,不过这种流派需要在一个领域浸淫比较长的时间,逃出他的领域就比较难说了。

4. 关于这些碎碎念

基本上就是想说,容易训练出来的都是不重要的...那些东西都进化很快,学术界不是白白养了一群人浪费的(虽然也挺浪费的),所以长江后浪一定会把前浪拍死在沙滩上。

与此同时,业务知识也不是那么重要的。经济环境变化太快,谁也不知道明天这个世界会变成什么样子。

那既然都是以不变应万变,那还是选一条比较开心的路子。总是需要合作的,这个世界已经复杂到没有可以一个人解决的问题了。

Categories
读书有感

社会网络中的社群识别(Community Discovery)概述

最近一直在看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.

嗯,到总结了~前面一直在说的就是计算、计算、计算。

  • 可扩展的算法(scalable algorithms):这里主要是牵扯到分布式计算。multi-level类的算法是有分布式的潜力的,然后GPU和多核计算貌似也能对流算法(streaming algorithms)帮上忙。
  • 群落和其进化的可视化:可视化主要是可以帮我们更直观的理解动态网络的变化、提供分析的直觉、以及帮助验证分析结果。
  • 结合业务知识:这个也不仅仅是对这些群落识别算法啦,任何一个机器学习的算法都离不开基本的业务知识吧。
  • 排序和加总:基本上还是缺乏对于得到的群落之间的排序(打分)、加总的研究。

好了,到此为止~继续看其他paper去了。